第3章关联规则挖掘理论和算法(new)课件

1、基本概念与解决方法 经典的频繁项目集生成算法分析 Apriori算法的性能瓶颈问题Apriori的改进算法对项目集格空间理论的发展关联规则挖掘中的一些更深入的问题第三章 关联规则挖掘理论和算法基本概念与解决方法 第三章 关联规则挖掘理论和算法关联规则挖掘是数据挖掘研究的基础关联规则挖掘（Association Rule Mining）是数据挖掘中研究较早而且至今仍活跃的研究方法之一。最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物篮分析（Basket Analysis）问题提出的，其目的是为了发现交易数据库（Transaction Database）中不同商品之间的联系规

2、则。关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘（Parallel Association Rule Mining）以及数量关联规则挖掘（Quantitive Association Rule Mining）等。关联规则挖掘是数据挖掘的其他研究分支的基础。 基本概念与解决方法关联规则挖掘是数据挖掘研究的基础关联规则挖掘（Associa事务数据库 设I= i1，i2，im 是一个项目(Item)集合，事务数据库D= t1，t2，tn 是由一系列具有唯一标识TID(事务号)的事务组成，每个事务ti（i=1，2，n）都对应 I 上的一个子集

3、。一个事务数据库可以用来刻画：购物记录： I是全部物品集合， D是购物清单，每个元组 ti 是一次购买物品的集合（它当然是 I 的一个子集）。如I= 物品1，物品2，物品m ;事务数据库D= t1，t2，tn 是事务数据库中关联规则的挖掘 t1物品2物品6物品9 t2物品3物品8物品16 tn物品1物品12物品34 事务数据库 设I= i1，i2，im 是一个项目(I支持度、频繁项目集、可信度、强关联规则 定义（项目集的支持度） 给定一个全局项目集I和数据库D，一个项目集 I1I 在D上的支持度（Support）是包含 I1 的事务在D中所占的百分比： support（ I1 ）=| t D

4、| I1 t | / | D|定义（频繁项目集） 给定全局项目集I和数据库D ，D中所有满足用户指定的最小支持度（Minsupport）的项目集，即大于或等于最小支持度的 I 的非空子集，称为频繁项目集（Frequent Itemsets）。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集（ Maximum Frequent Itemsets）。支持度、频繁项目集、可信度、强关联规则 定义（项目集的支持度定义（规则的可信度） 一个定义在I和D上的形如 I1I2 的关联规则通过满足一定的可信度(Confidence)来给出。所谓规则的可信度是指包含 I1 和I2的事务与包含

5、 I1 的事务之比： Confidence(I1I2)=| Support(I1I2) / Support(I1) 其中I1 ,I2 I ; I1I2=定义（强关联规则）。D 在 I 上满足最小支持度和最小可信度的关联规则称为强关联规则。 通常所说的关联规则一般指上面定义的强关联规则。定义（规则的可信度） 一个定义在I和D上的形如 I1I2关联规则挖掘基本过程关联规则挖掘问题就是根据用户指定的最小支持度和最小可信度来寻找强关联规则。关联规则挖掘问题可以划分成两个子问题：1.发现频繁项目集:通过用户给定最小支持度，寻找所有频繁项目集或者最大频繁项目集。2.生成关联规则:通过用户给定最小可信度，在

6、频繁项目集中，寻找关联规则。第1个子问题是近年来关联规则挖掘算法研究的重点。关联规则挖掘基本过程关联规则挖掘问题就是根据用户指定的最小支项目集格空间理论 Agrawal等人建立了用于事务数据库挖掘的项目集格空间理论（1993, Appriori 属性）。其理论核心的原理是：频繁项目集的所有非空子集都是频繁项目集非频繁项目集的所有超集都是非频繁项目集（相关定理及其证明略。）经典的频繁项目集生成算法分析项目集格空间理论 Agrawal等人建立了用于事务数据库挖掘Apriori算法是通过项目集元素数目不断增长来完成频繁项目集发现的。首先产生1_频繁项目集L1，然后产生2_频繁项目集L2，直到不能再扩

7、展频繁项目集的元素数目为止。下面给出一个样本事务数据库，并对它实施Apriori算法。TIDItemset1001，3，42002，3，53001，2，3，54002，5经典的发现频繁项目集算法 1994年，Agrawal 等人提出了著名的Apriori 算法。Apriori算法是通过项目集元素数目不断增长来完成频繁项目Apriori算法例子Database DC1L1L2C2Scan DL3Scan DC3Scan DC4Scan DScan DL4Minsupport=50% C1：1-候选集 L1：1-频繁项目集C2：2-候选集 L2：2-频繁项目集C3：3-候选集 L3：3-频繁项目集

8、C4：4-候选集 L4：4-频繁项目集L3是最大频繁项目集Apriori算法例子Database DC1L1L2C2SApriori算法（发现频繁项目集）（1） L1 = large 1-itemsets; /所有1-项目频集（2） FOR （k=2; Lk-1; k+） DO BEGIN（3） Ck=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）

9、 END（9） Lk=cCk |c.countminsup_count（10） END（11） L= Lk; （1） L1 = large 1-itemsets;Apriori-gen过程算法Apriori中调用了Apriori-gen(Lk-1)，是为了通过(k-1)-频集产生K-侯选集。has_infrequent_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.

10、itemk-1 1） THEN /generate rules with subsets of xm-1 as antecedents（7） genrules（lk， xm-1）;（8） END（9）END； 算法-递归测试一个频集中的关联规则genrules（lk: Rule-generate算法例子Minconfidence=80%序号lkxm-1ConfidenceSupport规则（是否是强规则）1235267%50%235（否）2235367%50%325（否）3235567%50%523（否）423523100%50%235（是）52352567%50%253（否）62353510

11、0%50%352（是）包含2,35的事务与包含2的事务的比值,即2:3同时满足支持度和可信度Rule-generate算法例子MinconfidenceApriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。Apriori算法有两个致命的性能瓶颈:1多次扫描事务数据库，需要很大的I/O负载对每次k循环，侯选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如有一个频繁大项目集包含10个项的话，那么就至少需要扫描事务数据库10遍。2可能产生庞大的侯选集由Lk-1产生k-侯选集Ck是指数增长的，例如104个1-频繁项目集就有可能产生接近107个元素的2-侯选集。如

12、此大的侯选集对时间和主存空间都是一种挑战。Apriori算法的性能瓶颈Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有 一些算法虽然仍然遵循Apriori 属性，但由于引入了相关技术，在一定程度上改善了Apriori算法适应性和效率。主要的改进方法有：基于数据分割（Partition）的方法：基本原理是“在一个划分中的支持度小于最小支持度的k-项集不可能是全局频繁的”。基于散列（Hash）的方法：基本原理是“在一个hash桶内支持度小于最小支持度的k-项集不可能是全局频繁的”。基于采样（Sampling）的方法：基本原理是“通过采样技术，评估被采样的子集中，并依次来估计k-项集的全

13、局频度”。其它方法，如动态删除没有用的事务：“不包含任何Lk的事务对未来的扫描结果不会产生影响，因而可以删除”。Apriori算法的改进技术 一些算法虽然仍然遵循Apriori 属基于数据分割的方法Apriori算法在执行过程中是先生成候选集再剪枝，可是生成的候选集并不都是有效的。候选集的产生需要花费很大的代价。把数据分割技术应用到关联规则挖掘中，可以改善关联规则挖掘在大数据集中的适应性。其基本思想：首先将大数据集从逻辑上分成互不相交的块，每块应用挖掘算法（如Apriori算法）生成局部的频繁项目集，然后将这些局部的频繁项目集作为全局候选频繁项目集，通过测试他们的支持度来得到最终的全局频繁项目

14、集。其可在以下两方面改善Apriori关联规则挖掘算法的性能：1合理利用主存空间：数据分割将大数据集分成小的块，为块内数据一次性导入主存提供机会。2支持并行挖掘算法：每个分块的局部频繁项目集是独立生成的，因此提供了开发并行数据挖掘算法的良好机制。基于数据分割的方法Apriori算法在执行过程中是先生成候选定理 设数据集D被分割成分块D1， D2， ， Dn，全局最小支持度为minsupport，假设对应的全局最小支持数为minsup_count。如果一个数据分块Di 的局部最小支持数记为minsup_counti (i=1，2，n)，则局部最小支持数minsup_counti按照如下方法生成：

15、 minsup_counti = minsup_count *|Di| / |D|可以保证所有的局部频繁项目集涵盖全局频繁项目集。定理 设数据集D被分割成分块D1， D2， ， Dn，全基于散列的方法1995，Park等发现寻找频繁项目集的主要计算是在生成2-频繁项目集上。因此，Park等利用了这个性质引入散列技术来改进产生2-频繁项目集的方法。例：桶地址 =（10 x + y）mod 7；minsupport_count=3 TID Items1 I1，I2，I52 I2，I43 I2，I34 I1，I2，I45 I1，I36 I2，I37 I1，I38 I1，I2，I3，I59 I1，I2

16、，I3L2=(I2，I3) ，(I1，I2) ，(I1，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 I2，I4 I2，I5 I1，I2 I1，I3容 I2，I3 I1，I2 I1，I3 I2，I3 I1，I2 I1，I3基于散列的方法1995，Park等发现寻找频繁项目集的主要计随着数据库容量的增大，重复访问数据库（外存）将导致性能低下。因此，探索新的理论和算法来减少数据库的扫描次数和侯选集空间占用，已经成为近年来关联规则挖掘研究的热点

17、之一。两个典型的方法：Close算法 FP-tree算法 项目集格空间理论的发展随着数据库容量的增大，重复访问数据库（外存）将导致性能低下。Close算法对应的原理一个频繁闭合项目集的所有闭合子集一定是频繁的；一个非频繁闭合项目集的所有闭合超集一定是非频繁的。什么是一个闭合的项目集？一个项目集C是闭合的，当且仅当对于在C中的任何元素，不可能在C中存在小于或等于它的支持度的子集。例如，C1=AB3，ABC2是闭合的； C2=AB2，ABC2不是闭合的； Close算法对应的原理一个频繁闭合项目集的所有闭合子集一定CLOSS算法的基本思路：利用频繁闭合i_项目集FCi，生成频繁闭合i+1 _项目集

18、FCi+1（i1）。 首先找出候选频繁闭合1_项目集FCC1，通过扫描数据库得到候选闭合项目集，再经修剪得到频繁闭合项目集FC1项目集。用FC1产生候选频繁闭合2_项目集FCC2，再经修剪得到频繁闭合项目集FC2项目集。在用FC2推出FC3 ，如此继续直到某个FCCr 为空时停止。CLOSS算法的基本思路：利用频繁闭合i_项目集FCi，生成Close算法的例子扫描数据库得到:FCC1=(A,3), (B,5), (C,4), (D,3), (E,3)； 相应闭合项目集为: FCl(A)=ABC,3(计算A的闭合过程:第一项包含A,首先得到A的闭合为ABCD,第三项也包含A, 故取ABCD与第三

19、项的交ABC作为A的闭合，第五项也包含A, 故取ABC与第五项的交ABC作为A的闭合,这时到了最后一项,计算完毕)。同理，FCl(B)=B,5，FCl(C)=BC,4，FCl(D)=BD,3，FCl(E)=BE,3 ；FCC2=(AB,3), (AC,3), (BC,4), (BD,3), (BE,3)； 相应闭合项目集为:FC2 (AB)=ABC,3, FC2 (AC)=ABC,3 ； L3，L4，L5不用测，于是频繁大项集为ABC 。下面是Close算法作用到右表数据集的执行过程（假如minsup_count=3）：TIDItemset1A，B，C，D2B，C，E3A，B，C，E4B，D，

20、E5A，B，C，D样本数据库Close算法的例子扫描数据库得到:下面是Close算法作用FP-tree算法的基本原理 2000年Han等提出了一个称为FP-Tree（频繁模式树）的算法，该算法只进行 2 次数据库扫描，不使用侯选集，直接压缩数据库成一个FP-Tree ，然后通过该树生成关联规则。构造FP-Tree的过程如下 ：按Apriori算法，扫描数据库一次生成1-频繁项目集，并按频度降序排序，放入L列表中；创建根结点，标志为null，扫描数据库一次，当得到数据库的一个项目（元组）时，就把其中的元素按L表中的次序排列，然后通过递归实现FP-Tree的增长；FP-tree算法的基本原理 20

21、00年HanFP-tree算法的基本原理样本数据库下面看一个例子来说明FP-Tree的增长过程,最小支持度阈值为3。TIDItemset1f,a,c,d,g,i,m,p2a,b,c,f,l,m,o3b,f,h,j,o4b,c,k,s,p5a,f,c,e,l,m,p, nItemfrequencyf4c4a3b3m3p3L扫描数据库一次生成1-频繁项目集（在数据库中出现3次或3次以上的），并按频度降序排序，放入L列表中；TIDItemset1f,c,a,m,p2f,c,a,b,m3f,b4c,b,p5f,c,a,m,p(1-频繁项目集)FP-tree算法的基本原理样本数据库下面看一个例子来说明F

22、FP-tree算法的基本原理样本数据库TIDItemset1f,c,a,m,p2f,c,a,b,m3f,b4c,b,p5f,c,a,m,pItem(fre)f4c4a3b3m3p3LT1T2T3T4扫描数据库,依次增长FP-tree，并改变支持数f:1c:1a:1m:1NULLp:1f:2c:2a:2m:1NULLb:1p:1m:1f:3c:2a:2m:1NULLb:1p:1m:1b:1f:3c:2a:2m:1NULLb:1p:1m:1b:1c:1b:1p:1f:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5FP-tree算法的基本原理样本数据库TIDItemset

23、1FP-tree算法的基本原理Item(fre)f4c4a3b3m3p3L建立索引f:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5FP-tree算法的基本原理Item(fre)f4c4a3b 用FP-Tree挖掘频繁集的基本思想是分而制之，即使用FP-Tree 递归增长频繁集的方法：对每个项，生成其条件模式库，然后生成其条件FP-Tree；对每个新生成的条件FP-Tree，重复此步骤；直到结果FP-Tree为空，或只含唯一的一个路径，此路径的每个子路径对应的项目集都是频繁集。 用FP-Tree挖掘频繁集的基本思想是分而制从FP-Tree建立条件模式库对应的条件模式

24、库Item条件模式库cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1FP-treeItem(fre)f4c4a3b3m3p3Lf:4c:3a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5从FP-Tree建立条件模式库对应的条件模式库Item条件模用条件模式库建立对应的条件FP-Treem-条件模式库Item条件模式库cf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1pfcam:2, cb:1f:3c:3a:3NULLm-条件FP-TreeItem(fre)f4c4a3b3m3p3Lf:4c:3

25、a:3m:2NULLb:1p:2m:1b:1c:1b:1p:1T5用条件模式库建立对应的条件FP-Treem-条件Item条件Item条件模式库条件FP-Treep(fcam:2),(cb:1)(c:3)|pm(fca:2),(fcab:1)(f:3,c:3,a:3)|mb(fca:1),(f:1),(c:1)Emptyafc:3(f:3,c:3)|acf:3(f:3|cfEmptyEmptym-条件FP-Treec:3NULLf:3c:3a:3NULLNULLf:3c:3NULLf:3NULLp-条件FP-Treec-条件FP-Treea-条件FP-Treeb-条件FP-TreeNULLf-

26、条件FP-TreeItem条件模式库条件FP-Treep(fcam:2),(用条件FP-Tree挖掘频繁项集m-条件FP-Treec:3NULLf:3c:3a:3NULLNULLf:3c:3NULLf:3NULLp-条件FP-Treec-条件FP-Treea-条件FP-Treeb-条件FP-TreeNULLf-条件FP-Tree得到的频繁项目集合，用条件FP-Tree挖掘频繁项集m-条件FP-Treec:3多层次关联规则挖掘根据规则中涉及到的层次，多层次关联规则可以分为：同层关联规则：如果一个关联规则对应的项目是同一个粒度层次，那么它是同层关联规则。如“牛奶面包”和“羽绒服酸奶”都是同层关联规

27、则;关联规则挖掘中的一些更深入的问题日用品服装食品夏季服装冬季服装面包牛奶羽绒服大衣品牌1品牌2鲜奶酸奶品牌3品牌4层间关联规则：如果在不同的粒度层次上考虑问题，那么可能得到的是层间关联规则。如“夏季服装酸奶”都是层间关联规则;多层次关联规则挖掘根据规则中涉及到的层次，多层次关联规则可以多层次关联规则挖掘多层次关联规则挖掘的度量方法可以沿用 “支持度-可信度”的框架。不过，多层次关联规则挖掘有两种基本的设置支持度的策略：统一的最小支持度：算法实现容易，而且很容易支持层间的关联规则生成。但是弊端也是显然的：不同层次可能考虑问题的精度不同、面向的用户群不同对于一些用户，可能觉得支持度太小，产生了过多不感兴趣的规则。而对于另外的用户来说，又认为支持度太大，有用信息丢失过多。多层次关联规则挖掘多层次关联规则挖掘的度量方法可以沿用 “支不同层次使用不同的最小支持度：每个层次都有自己的最小支持度。较低层次的最小支持度相对较小，而较高层次的最小支持度相对较大。这种方法增加了挖掘的灵活性。但是，也留下了许多相关问题需要解决：首先，不同层次间的支持度应