数据挖掘原理与算法03关联规则挖掘.ppt

《数据挖掘原理与算法03关联规则挖掘.ppt》由会员分享，可在线阅读，更多相关《数据挖掘原理与算法03关联规则挖掘.ppt（31页珍藏版）》请在三一文库上搜索。

1、2019年7月22日星期一,1,第三章 关联规则挖掘理论和算法 内容提要,基本概念与解决方法 经典的频繁项目集生成算法分析 Apriori算法的性能瓶颈问题 Apriori的改进算法,2019年7月22日星期一,2,关联规则挖掘（Association Rule Mining）是数据挖掘中研究较早而且至今仍活跃的研究方法之一。 最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物篮分析（Basket Analysis）问题提出的，其目的是为了发现交易数据库（Transaction Database）中不同商品之间的联系规则。 关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理

2、论、算法设计、算法的性能以及应用推广、并行关联规则挖掘（Parallel Association Rule Mining）以及数量关联规则挖掘（Quantitive Association Rule Mining）等。 关联规则挖掘是数据挖掘的其他研究分支的基础。,3.1 基本概念与解决方法,2019年7月22日星期一,3,3.1 基本概念与解决方法,事务数据库 设I= i1，i2，im 是一个项目集合，事务数据库D= t1，t2，tn 是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，n）都对应I上的一个子集。 一个事务数据库可以用来刻画： 购物记录： I是全部物品集合， D

3、是购物清单，每个元组ti是一次购买物品的集合（它当然是I的一个子集）。 其它应用问题,2019年7月22日星期一,4,支持度与频繁项目集,定义3-1（项目集的支持度）. 给定一个全局项目集I和数据库D，一个项目集I1I在D上的支持度（Support）是包含I1的事务在D中所占的百分比：support（ I1 ）=| t D | I1 t| / | D|。 定义3-2（频繁项目集）.给定全局项目集I和数据库D ，D中所有满足用户指定的最小支持度（Minsupport）的项目集，即大于或等于minsupport的I的非空子集，称为频繁项目集（频集：Frequent Itemsets）或者大项目集（

4、Large Iitemsets）。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集（最大频集： Maximum Frequent Itemsets）或最大大项目集（Maximum Large Iitemsets）。,2019年7月22日星期一,5,可信度与关联规则,定义3-3（关联规则与可信度）.给定一个全局项目集I和数据库D，一个定义在I和D上的关联规则形如I1I2，并且它的可信度或信任度或置信度（Confidence）是指包含I1和I2的事务数与包含I1的事务数之比，即 Confidence（I1I2）= support（I1I2）/ support（I1）， 其中I

5、1，I2I，I1I2=。 定义3-4（强关联规则）. D在I上满足最小支持度和最小信任度（Minconfidence）的关联规则称为强关联规则（Strong Association Rule）。,2019年7月22日星期一,6,关联规则挖掘基本过程,关联规则挖掘问题可以划分成两个子问题： 1. 发现频繁项目集:通过用户给定Minsupport ，寻找所有频繁项目集或者最大频繁项目集。 2生成关联规则:通过用户给定Minconfidence ，在频繁项目集中，寻找关联规则。 第1个子问题是近年来关联规则挖掘算法研究的重点。,2019年7月22日星期一,7,3.2 经典的频繁项目集生成算法分析 项

6、目集空间理论 经典的发现频繁项目集算法 关联规则生成算法,2019年7月22日星期一,8,3.2.1 项目集空间理论,Agrawal等人建立了用于事务数据库挖掘的项目集格空间理论（1993, Appriori 属性）。 定理3-1（ Appriori 属性1）. 如果项目集X 是频繁项目集，那么它的所有非空子集都是频繁项目集。 证明 设X是一个项目集，事务数据库T 中支持X 的元组数为s。对X的任一非空子集为Y，设T中支持Y的元组数为s1。 根据项目集支持数的定义，很容易知道支持X 的元组一定支持Y，所以s1 s，即support（Y） support（X）。 按假设：项目集X 是频繁项目集，

7、即support(X) minsupport， 所以support（Y） support（X） minsupport，因此Y是频繁项目集。 定理3-2（ Appriori 属性2）.如果项目集X 是非频繁项目集，那么它的所有超集都是非频繁项目集。 证明 （略）,2019年7月22日星期一,9,3.2.2 经典的发现频繁项目集算法,1994年，Agrawal 等人提出了著名的Apriori 算法。 算法3-1 Apriori（发现频繁项目集）,（1） L1 = large 1-itemsets; /所有1-项目频集 （2） FOR （k=2; Lk-1; k+） DO BEGIN （3） Ck=

8、apriori-gen（Lk-1）; / Ck是k-候选集 （4） FOR all transactions tD DO BEGIN （5） Ct=subset（Ck，t）; / Ct是所有t包含的候选集元素 （6） FOR all candidates c Ct DO （7） c.count+; （8） END （9） Lk=cCk |c.countminsup_count （10） END （11） L= Lk;,2019年7月22日星期一,10,apriori-gen过程,算法apriori中调用了apriori-gen（Lk-1），是为了通过（k-1）-频集产生K-侯选集。 has_i

9、nfrequent_subset（c， Lk-1），判断c是否加入到k-侯选集中。,（1） FOR all itemset p Lk-1 DO （2） FOR all itemset qLk-1 DO （3） IF p.item1=q.item1， ， p.itemk-2=q.itemk-2， p.itemk-1 q.itemk-1 THEN BEGIN （4） c= pq;/把q的第k-1个元素连到p后 （5） IF has_infrequent_subset（c， Lk-1） THEN （6） delete c;/删除含有非频繁项目子集的侯选元素 （7） ELSE add c to Ck;

10、 （8） END （9） Return Ck;,2019年7月22日星期一,11,发现算法解决的是关联规则挖掘的第一个问题 关联规则分为布尔关联规则和多值规则 多值关联规则都转化为布尔关联规则来解决，因此先介绍布尔关联规则算法 Apriori，AprioriTid,2019年7月22日星期一,12,Apriori算法分析,分为第一次遍历和第k次遍历 第一次遍历计算每个项目的具体值，确定大项目集1项目集L1 第k次遍历利用前一次找到的大项集Lk-1 和Apriori-gen函数产生候选集Ck ，然后扫描数据库，得到Ck 中候选的支持度，剔除了不合格的候选后Ck作为Lk,2019年7月22日星期一

11、,13,例3-1,下表给出一个样本事务数据库，并对它实施Apriori算法。,2019年7月22日星期一,14,Apriori算法例子,Minsupport=40%,2019年7月22日星期一,15,3.2.3 关联规则生成算法,根据上面介绍的关联规则挖掘的两个步骤，在得到了所有频繁项目集后，可以按照下面的步骤生成关联规则： 对于每一个频繁项目集l，生成其所有的非空子集； 对于l 的每一个非空子集x，计算Conference（x），如果Confidence（x）minconfidence，那么“x（l-x）”成立。 算法3-4 从给定的频繁项目集中生成强关联规则 算法3-4的核心是genrul

12、es递归过程，它实现一个频繁项目集中所有强关联规则的生成。,Rule-generate（L，minconf） （1） FOR each frequent itemset lk in L （2） genrules（ lk ， lk）;,2019年7月22日星期一,16,算法-递归测试一个频集中的关联规则,算法3-5 递归测试一个频集中的关联规则 genrules（lk: frequent k-itemset， xm: frequent m-itemset） （1）X=（m-1）-itemsets xm-1 | xm-1 in xm ； （2）FOR each xm-1 in X BEGIN （3

13、） conf = support（lk）/support（xm-1）; （4） IF （conf minconf） THEN BEGIN （5） print the rule “xm-1（ lk-xm-1），with support = support（lk）， confidence=conf”; （6） IF （m-1 1） THEN /generate rules with subsets of xm-1 as antecedents （7） genrules（lk， xm-1）; （8） END （9）END；,2019年7月22日星期一,17,Rule-generate算法例子,Min

14、confidence=80%,序号 lk xm-1 confidence support 规则（是否是强规则） 1 235 23 100% 50% 235（是） 2 235 2 67% 50% 235（否） 3 235 3 67% 50% 325（否） 4 235 25 67% 50% 253（否） 5 235 5 67% 50% 523（否） 6 235 35 100% 50% 352（是）,2019年7月22日星期一,18,3.3 Apriori算法的性能瓶颈问题,Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。 Apriori算法有两个致命的性能瓶颈: 1多次扫

15、描事务数据库，需要很大的I/O负载 对每次k循环，侯选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如有一个频繁大项目集包含10个项的话，那么就至少需要扫描事务数据库10遍。 2可能产生庞大的侯选集 由Lk-1产生k-侯选集Ck是指数增长的，例如104个1-频繁项目集就有可能产生接近107个元素的2-侯选集。如此大的侯选集对时间和主存空间都是一种挑战。,2019年7月22日星期一,19,3.4 Apriori的改进算法 基于数据分割的方法 基于散列的方法,2019年7月22日星期一,20,3.4 提高Apriori算法效率的技术,一些算法虽然仍然遵循Apriori 属性，但

16、是由于引入了相关技术，在一定程度上改善了Apriori算法适应性和效率。 主要的改进方法有： 基于数据分割（Partition）的方法：基本原理是“在一个划分中的支持度小于最小支持度的k-项集不可能是全局频繁的”。 基于散列（Hash）的方法：基本原理是“在一个hash桶内支持度小于最小支持度的k-项集不可能是全局频繁的”。 基于采样（Sampling）的方法：基本原理是“通过采样技术，评估被采样的子集中，并依次来估计k-项集的全局频度”。 其他：如，动态删除没有用的事务：“不包含任何Lk的事务对未来的扫描结果不会产生影响，因而可以删除”。,2019年7月22日星期一,21,基于数据分割的方法

17、,定理3-5 设数据集D被分割成分块D1， D2， ， Dn，全局最小支持数为minsup_count。如果一个数据分块Di 的局部最小支持数minsup_counti （i=1，2，n），按着如下方法生成： minsup_counti= minsup_count *|Di| / |D| 则所有的局部频繁项目集涵盖全局频繁项目集。 作用： 1合理利用主存空间：数据分割将大数据集分成小的块，为块内数据一次性导入主存提供机会。 2支持并行挖掘算法：每个分块的局部频繁项目集是独立生成的，因此提供了开发并行数据挖掘算法的良好机制。,2019年7月22日星期一,22,基于散列的方法,1995，Park等

18、发现寻找频繁项目集的主要计算是在生成2-频繁项目集上。因此，Park等利用了这个性质引入杂凑技术来改进产生2-频繁项目集的方法。 例子：桶地址 =（10x+y）mod 7；minsupport_count=3,TID Items 1 I1，I2，I5 2 I2，I4 3 I2，I3 4 I1，I2，I4 5 I1，I3 6 I2，I3 7 I1，I3 8 I1，I2，I3，I5 9 I1，I2，I3,桶地址 0 1 2 3 4 5 6 桶计数 2 2 4 2 2 4 4 桶内 I1，I4 I1，I5 I2，I3 I2，I4 I2，I5 I1，I2 I1，I3 I3，I5 I1，I5 I2，I3

19、 I2，I4 I2，I5 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3,L2=I2，I3 ， I1，I2 ， I1，I3,2019年7月22日星期一,23,第三章 关联规则挖掘理论和算法 内容提要,3.5 对项目集格空间理论的发展 Close算法 FP-tree算法,2019年7月22日星期一,24,探索新的理论,随着数据库容量的增大，重复访问数据库（外存）将导致性能低下。因此，探索新的理论和算法来减少数据库的扫描次数和侯选集空间占用，已经成为近年来关联规则挖掘研究的热点之一。 两个典型的方法： Close算法 FP-tree算法,2019年7

20、月22日星期一,25,Close算法对应的原理,一个频繁闭合项目集的所有闭合子集一定是频繁的；一个非频繁闭合项目集的所有闭合超集一定是非频繁的。 什么是一个闭合的项目集？ 一个项目集C是闭合的，当且仅当对于在C中的任何元素，不可能在C中存在小于或等于它的支持度的子集。 例如，C1=AB3，ABC2是闭合的； C2=AB2，ABC2不是闭合的；,2019年7月22日星期一,26,Close算法的例子,下面是Close算法作用到表4-1数据集的执行过程（假如minsup_count=3）： 扫描数据库得到L1=(A,3), (B,5), (C,4), (D,3), (E,3)；相应关闭项目集为 C

21、l (A)=ABC,3，Cl (B)=B,5，Cl (C)=BC,4，Cl (D)=BD,3，Cl(E)=BE,3 ； L2=(AB,3), (AC,3), (BC,4), (BD,3), (BE,3)；相应关闭集为C2 (AB)=ABC,3； L3，L4，L5不用测，于是频繁大项集为ABC 。,样本数据库 TID Itemset 1 A，B，C，D 2 B，C，E 3 A，B，C，E 4 B，D，E 5 A，B，C，D,2019年7月22日星期一,27,FP-tree算法的基本原理,进行2次数据库扫描：一次对所有1-项目的频度排序；一次将数据库信息转变成紧缩内存结构。 不使用侯选集，直接压缩

22、数据库成一个频繁模式树，通过频繁模式树可以直接得到频集。 基本步骤是： 两次扫描数据库，生成频繁模式树FP-Tree： 扫描数据库一次，得到所有1-项目的频度排序表T； 依照T，再扫描数据库，得到FP-Tree。 使用FP-Tree，生成频集： 为FP-tree中的每个节点生成条件模式库； 用条件模式库构造对应的条件FP-tree； 递归挖掘条件FP-trees同时增长其包含的频繁集： 如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。,2019年7月22日星期一,28,生成频繁模式树FP-Tree,min_support = 0.5,TID Original Items (or

23、dered) frequent items 100 f, a, c, d, g, i, m, p f, c, a, m, p 200 a, b, c, f, l, m, o f, c, a, b, m 300 b, f, h, j, o f, b 400 b, c, k, s, p c, b, p 500 a, f, c, e, l, p, m, n f, c, a, m, p,2019年7月22日星期一,29,挖掘频集步骤1：生成条件模式库,为每个节点， 寻找它的所有前缀路径并记录其频度，形成CPB,CPB item cond. pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1,2019年7月22日星期一,30,挖掘频集步骤2：构造C-FP-tree,为每一个节点，通过FP-tree构造一个C-FP-tree 例如，m节点的C-FP-tree为：,m-CPB: fca:2, fcab:1,2019年7月22日星期一,31,挖掘频集步骤3：递归构造C-FP-tree,所有频集： m, fm, cm, am, fcm, fam, cam, fcam,单路径可以形成频集,