1、Data mining & Business Intelligence 数据挖掘与商务智能 1 2 课程内容 预备知识1 数据挖掘（DM）2 商业智能（BI）3 数据挖掘的含义数据挖掘的含义& &任务任务 数据质量数据质量 数据预处理数据预处理 汇总统计、数据可视化汇总统计、数据可视化&OLAP&OLAP 分类、分类、关联分析、聚类分析、异常检测关联分析、聚类分析、异常检测 各类数据挖掘工具简介各类数据挖掘工具简介 BIBI的含义的含义& &案例案例 数据挖掘技术在数据挖掘技术在BIBI中的应用中的应用 面向服务架构面向服务架构&BI&BI 参考书籍：参考书籍： Introduction to
2、 Data MiningIntroduction to Data Mining 美美P. N. Tan et.al. P. N. Tan et.al. 参考书籍：参考书籍： Materials from the InternetMaterials from the Internet 商务智能与数据挖掘商务智能与数据挖掘Microsoft Microsoft SQL serverSQL server应用，应用， 谢邦昌 课件下载邮箱：课件下载邮箱： gdutwwgdutww Psw: gdutww Psw: gdutww 2 3 2 数据挖掘具体方法 2.3 2.3 关联分析关联分析 怎样进行
3、关联规则挖掘 基本概念 3 4 基本概念：关联规则挖掘 l关 ：关 是形如X-Y的涵表达式，其中X和Y是不相交 的集，即 。 l关 挖掘：从一个数据集中 关 ， 示了定 数据集中常一起出的属性条件元。 Market-Basket 事务集 Example of Association Rules Diaper Beer, Milk, Bread Eggs,Coke, Beer, Bread Milk, 注意：两个事务组相互关联，只是 两者经常同时发生，而并不一定是 两者一定具有因果关系。 2.3.12.3.1 4 5 实例 通 客放入其物中不 同商品之的系，分析客的 。通了解哪些商品繁地被 客同
4、 ，种关的 可以帮 助零售商制定 策略。例如，在同 一次物中，如果客 牛奶的同 ，也 面包（和什么型的面包 ）的可能性有多大？ 种信息可以引 售，可以帮助 零售商有 地 和安排架。例 如，将牛奶和面包尽可能放近一些， 可以一步引客在商店里同 些商品。 Customer buys diaper Customer buys both Customer buys beer “啤酒与尿布”的关联规则 2.3.12.3.1 5 6 一些基本定义 l项集 Q 一个或多个项的集合 如: Milk, Bread, Diaper Q k-项集 包含有k个子项的项集 l支持度计数 () Q 一个项集在事务集中出现
5、的频率 Q E.g. (Milk, Bread,Diaper) = 2 l支持度 Q 包含某个项集的事务数量比例 Q E.g. s(Milk, Bread, Diaper) = 2/5 l频繁项集 Q 支持度高于或等于阈值minsup的项集 2.3.12.3.1 为什么要使用支持度？支持 度是一种重要的度量，因为支持 度很低的规则只是偶然出现，从 商业角度来看，低支持度的规则 多半也不是令人感兴趣的，因为 对顾客很少同时购买的商品进行 促销可能并无益处。 6 7 一些基本定义 Example: l关联规则 Q形如X Y的蕴涵式，其中X 和Y 是项集。 Q例如: Milk, Diaper Bee
6、r l关联规则强度的衡量指标 Q支持度（缩写：s) 同时包含X和Y的事务比例 Q置信度(缩写：c) Y 在包含X 的事务中出现 的频繁程度。 2.3.12.3.1 7 8 怎样进行关联规则挖掘 l给定事务集T, 关联规则挖掘的任务就 是寻找满足以下条件的关联规则。 Q支持度 minsup threshold Q置信度 minconf threshold l一种“原始野蛮”的方法: Q列出所有的规则 Q分别计算每条规则的置信度和支持度 Q剔除未达到 minsup阈值和 minconf阈值的规则 Computationally prohibitive! 2.3.22.3.2 整体上是经常出现的，整
7、体上是经常出现的， 相互的关联度是大的相互的关联度是大的 8 9 怎样进行关联规则挖掘 Example of Rules: Milk,Diaper Beer (s=0.4, c=0.67) Milk,Beer Diaper (s=0.4, c=1.0) Diaper,Beer Milk (s=0.4, c=0.67) Beer Milk,Diaper (s=0.4, c=0.67) Diaper Milk,Beer (s=0.4, c=0.5) Milk Diaper,Beer (s=0.4, c=0.5) Observations: 所有上述规则都是产生于以下项集: Milk, Diaper
8、, Beer 产生于相同项集的规则具有相同的支持度但是不同的置信度。 因此需要区分开置信度和支持度的要求。 2.3.22.3.2 9 10 怎样进行关联规则挖掘 l采用“两步走”的方法: 1. 先产生频繁项集 即找出 support minsup的所有项集 1. 生成规则 从频繁项集中产生具有高置信度的规则，每条规则 本质上其实就是频繁项集的一个划分。 l产生频繁项集的过程运算量仍然是非常大的！ 2.3.22.3.2 10 11 给定d 个项，则可以产 生 2d 个候选项集。 怎样进行关联规则挖掘 2.3.22.3.2 生成频繁项集生成频繁项集 格结构：常常格结构：常常 用来枚举所有用来枚举所
9、有 可能的项集可能的项集 11 12 l原始的方法: Q列出所有可能项集（如右图），即候选的频繁项集 Q扫描事务数据库（左图），计算每个候选项集的支持度。 Q将每个事务与候选项集相匹配，生成关联规则。 Q算法复杂度 O(NMw) = Expensive since M = 2d ! 2.3.22.3.2 怎样进行关联规则挖掘 12 13 算法复杂度 l给定 d 个事务项: Q项集的总数= 2d Q可以生成的规则总数是: If d=6, R = 602 rules 2.3.22.3.2 蕴含式的 左端 蕴含式的 右端 13 14 如何降低产生频繁项集的计算复杂度 l减少候选项集的数目 (M) Q
10、完全的搜索: M=2d Q可以采用一些剪枝的方法减少 M l减少比较次数 (NM) Q可以使用更高级的数据结构存储事务或候选项集 （Hash Tree） Q有些事务和候选项集并不一定需要进行比较。 l减少事务数目 (N) 2.3.22.3.2 14 15 减少候选项集的策略 l先验原理: Q 如果一个项集是频繁的， 则它的所有子集也一定是 频繁的。即： l先验原理成立是因为支持度具 有以下特性: Q 一个项集的支持度决不会 超过其子集的支持度。 Q 这个性质也称为支持度度 量的反单调性。 2.3.22.3.2 15 16 Found to be Infrequent 先验原理应用示例 Prun
11、ed supersets 如果一个项集是如果一个项集是 非频繁的，则它非频繁的，则它 的超集也一定是的超集也一定是 非频繁的非频繁的 2.3.22.3.2 16 17 先验原理应用示例(续) Items (1-itemsets) Pairs (2-itemsets) (No need to generate candidates involving Coke or Eggs) Triplets (3-itemsets) Minimum Support = 3 If every subset is considered, 6C1 + 6C2 + 6C3 = 41 With support-bas
12、ed pruning, 6 + 6 + 1 = 13 2.3.22.3.2 17 18 Apriori算法(频繁项集的生成） lMethod: QLet k=1 Q产生长度为1的频繁项集 Q重复以下过程直到没有新的频繁项集产生 从k 个频繁项集中生成长度为k+1的候选项集 对包含非频繁、且长度为k的子集的候选项集进行 剪枝。 扫描数据库，统计每个候选项集的支持度 剔除非频繁项集，保留频繁项集 2.3.22.3.2 18 19 l给定频繁项集L, 找到所有的非空子集f L 使得规则 f L f 可以满足最小置信度的要求 Q如果A,B,C,D是一个频繁项集,则候选规则有: ABC D, ABD C
13、, ACD B, BCD A, A BCD,B ACD,C ABD, D ABC AB CD,AC BD, AD BC, BC AD, BD AC, CD AB, l如果|L| = k,将有2k 2个候选的关联规则(因为忽略了 L和L) 2.3.22.3.2 Apriori算法(规则的生成） 19 20 l怎样从频繁项集中高效的生成规则？ Q一般而言,置信度并不具有 单调性（这与支持度度量是 不同的） 例如：c(ABCD) can be larger or smaller than c(AB D) Q但如果是由同一个候选项集产生的规则则具有单调性 Q如， L = A,B,C,D: c(ABC
14、D) c(AB CD) c(A BCD) Q因为当 时，显然 2.3.22.3.2 Apriori算法(规则的生成） 20 21 Lattice of rules Pruned Rules Low Confidence Rule 2.3.22.3.2 Apriori算法(规则的生成） 21 22 2.3.22.3.2 Apriori算法(规则的生成） 22 23 2 数据挖掘具体方法 2.4 2.4 聚类分析聚类分析 聚类的经典方法 基本概念 23 24 什么是聚类分析? l聚分析又称“同分”或者“无督的分”，指把 一数据分成不同的“簇”，每簇中的数据相似而不同簇 的数据距离 。 Inter-
15、cluster distances are maximized Intra-cluster distances are minimized 2.4.12.4.1 24 25 聚类分析的应用 l例如： Q 将文档进行聚类以便于浏览 Q 将基因和蛋白质进行聚类以 考察他们之间的相似功能 Q 对波动情况相似的股票进行 聚类以供股民参考； l帮助汇总 Q 减少大规模数据集的数据量 Clustering precipitation in Australia 2.4.12.4.1 25 26 哪些不是聚类分析 l有监督分类 Q已经知道类标签信息，但不知道分类的规则 l简单分割 Q例如：在注册时，根据学生的
16、姓名音序进行分组。 l查询返回的结果 Q这种分组是外部指定的结果。 2.4.12.4.1 26 27 聚类的一些概念可能是模棱两可的 How many clusters? Four Clusters Two Clusters Six Clusters 2.4.12.4.1 27 28 聚类的不同类型 l整个簇集合通常称为聚类 l层次聚类与划分聚类的不同点 Q划分聚类 Q 简单地将数据对象划分成不重叠的子集（簇），使得每个数据 对象恰好在一个子集中。 Q层次聚类 Q 层次聚类是嵌套簇的集簇，组织成一棵有层次的树。 2.4.12.4.1 28 29 划分聚类 Original PointsA Pa
17、rtitional Clustering 2.4.12.4.1 29 30 层次聚类 Traditional Hierarchical Clustering Non-traditional Hierarchical ClusteringNon-traditional Dendrogram Traditional Dendrogram 2.4.12.4.1 30 31 不同的簇类型 l明显分离的簇: Q 每个点到同簇中任意点的距离比到不同簇中所有点的距离更 近。 3个明显分离的簇 2.4.12.4.1 31 32 不同的簇类型 l基于中心的簇 Q 每个点到其簇中心的距离比到其他簇中心的距离更近。
18、 Q The center of a cluster is often a centroid, the average of all the points in the cluster, or a medoid, the most “representative” point of a cluster 4 个基于中心的簇 2.4.12.4.1 32 33 不同的簇类型 l连续簇 (又称为“基于临近的簇”) Q 每个点到该簇中至少一个点的距离比到不同簇中任意点的距离 更近 8个连续簇 2.4.12.4.1 33 34 不同的簇类型 l基于密度的簇 Q 簇是被低密度分开的高密度区域 Q 在簇不规则
19、或缠结的情况下使用，或者当有噪声和离群点出现 的时候使用。 6 density-based clusters 2.4.12.4.1 34 35 聚类算法 & K均值（K-means）算法及其变化版本 l层次聚类算法 l基于密度聚类算法 2.4.22.4.2 35 36 基本的K均值聚类 l每个簇内有一个心centroid (通常定 簇内本点 的平均) l每个本划入离其最近的心所在的簇 lK是先定的 l基本思想是： 首先，随机 k个数据点做聚中心； 然后，算其它点到些聚中心点的距离，通 簇中距离平 均的算，不断改 些聚中心的位置，直到些聚中心 不再化止。 2.4.22.4.2 36 37 K均值
20、聚类 l初始的质心是随机选择的. Q相同样本集上先后聚类，所得的簇往往不一样. l质心通常就是簇内样本点的平均值。 l通常使用Euclidean距离、余弦相似性以及相关性等来 表征样本间的相似度. l在上述相似性度量下，多数K均值聚类算法可以收敛， 并且只需要少数几次迭代即可收敛。 Q算法中的停止条件也可以变成 Until relatively few points change clusters l算法复杂度为 o( n * K * I * d ) Qn =样本总数, K =簇的个数, I =迭代次数, d =属性个数 2.4.22.4.2 37 38 两种不同的聚类结果 Sub-optim
21、al ClusteringOptimal Clustering Original Points 不同初始质心 的情况下所导 致的不同结果 2.4.22.4.2 38 39 具体过程（1） 2.4.22.4.2 39 40 具体过程（1） 2.4.22.4.2 40 41 具体过程（2） 2.4.22.4.2 41 42 具体过程（2） 2.4.22.4.2 42 43 初始点选择的困难性 l假设样本集确实存在K个簇，则恰好从每个簇中选择一个初始质心 的概率其实上也很小。I QK越大时候，机会就越小。 Q简单计算一下，假设每个簇都包含n个样本点，则 Q例如, 加入 K = 10, 则这种概率 = 10!/1010 = 0.00036 Q有时候，在迭代的过程中，算法能朝正确的方向修正初始质心 ，并最终获得正确的聚类，但有的时候算法却无法得到修正初 始质心。 Q以下是一个包含5对簇的例子。 2.4.22.4.2 43 44 例子 Starting with two i
个人主页