关联规则挖掘理论和算法

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

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

3、然是 I 的一个子集）。 如I= 物品1，物品2，物品m ;事务数据库D= t1，t2，tn 是,事务数据库中关联规则的挖掘,支持度、频繁项目集、可信度、强关联规则,定义（项目集的支持度） 给定一个全局项目集I和数据库D，一个项目集 I1I 在D上的支持度（Support）是包含 I1 的事务在D中所占的百分比： support（ I1 ）=| t D | I1 t | / | D| 定义（频繁项目集） 给定全局项目集I和数据库D ，D中所有满足用户指定的最小支持度（Minsupport）的项目集，即大于或等于最小支持度的 I 的非空子集，称为频繁项目集（Frequent Itemsets）。

4、在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集（ Maximum Frequent Itemsets）。,定义（规则的可信度） 一个定义在I和D上的形如 I1I2 的关联规则通过满足一定的可信度(Confidence)来给出。所谓规则的可信度是指包含 I1 和I2的事务与包含 I1 的事务之比： Confidence(I1I2)=| Support(I1I2) / Support(I1) 其中I1 ,I2 I ; I1I2= 定义（强关联规则）。D 在 I 上满足最小支持度和最小可信度的关联规则称为强关联规则。 通常所说的关联规则一般指上面定义的强关联规则。,关联规则挖

5、掘基本过程,关联规则挖掘问题就是根据用户指定的最小支持度和最小可信度来寻找强关联规则。 关联规则挖掘问题可以划分成两个子问题： 1.发现频繁项目集:通过用户给定最小支持度，寻找所有频繁项目集或者最大频繁项目集。 2.生成关联规则:通过用户给定最小可信度，在频繁项目集中，寻找关联规则。 第1个子问题是近年来关联规则挖掘算法研究的重点。,项目集格空间理论,Agrawal等人建立了用于事务数据库挖掘的项目集格空间理论（1993, Appriori 属性）。 其理论核心的原理是： 频繁项目集的所有非空子集都是频繁项目集 非频繁项目集的所有超集都是非频繁项目集 （相关定理及其证明略。）,经典的频繁项目集

6、生成算法分析,经典的发现频繁项目集算法,1994年，Agrawal 等人提出了著名的Apriori 算法。 Apriori算法（发现频繁项目集）,（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+;

7、（8） END （9） Lk=cCk |c.countminsup_count （10） END （11） L= Lk;,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.itemk-1 q.itemk-1

8、 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; （8） END （9） Return Ck;,Apriori算法是通过项目集元素数目不断增长来完成频繁项目集发现的。首先产生1_频繁项目集L1，然后产生2_频繁项目集L2，直到不能再扩展频繁项目集的元素数目为止。 下面给出一个样本事务数据库，并对它实施Apriori算法。,Apriori算法例子,Database D,C1,L1,

9、L2,C2,Scan D,L3,Scan D,C3,Scan D,C4,Scan D,Scan D,L4,Minsupport=50% C1：1-候选集 L1：1-频繁项目集 C2：2-候选集 L2：2-频繁项目集 C3：3-候选集 L3：3-频繁项目集 C4：4-候选集 L4：4-频繁项目集,L3是最大频繁项目集,关联规则的生成问题,根据上面介绍的关联规则挖掘的两个步骤，在得到了所有频繁项目集后，可以按照下面的步骤生成关联规则： 对于每一个频繁项目集 l ，生成其所有的非空子集； 对于l 的每一个非空子集x，计算Conference（x），如果Confidence（x）minconfiden

10、ce，那么“ x(l-x) ”成立。 关联规则生成算法: 从给定的频繁项目集中生成强关联规则 该算法的核心是genrules递归过程，它实现一个频繁项目集中所有强关联规则的生成。,Rule-generate（L，minconf） （1） FOR each frequent itemset lk in L （2） genrules（ lk ， lk）;,算法-递归测试一个频集中的关联规则,genrules（lk: frequent k-itemset， xm: frequent m-itemset） （1）X=（m-1）-itemsets xm-1 | xm-1 in xm ； （2）FOR e

11、ach xm-1 in X BEGIN （3） 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；,Rule-generate算法例

12、子,Minconfidence=80%,Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。 Apriori算法有两个致命的性能瓶颈: 1多次扫描事务数据库，需要很大的I/O负载 对每次k循环，侯选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如有一个频繁大项目集包含10个项的话，那么就至少需要扫描事务数据库10遍。 2可能产生庞大的侯选集 由Lk-1产生k-侯选集Ck是指数增长的，例如104个1-频繁项目集就有可能产生接近107个元素的2-侯选集。如此大的侯选集对时间和主存空间都是一种挑战。,Apriori算法的性能瓶颈,一些算法虽然仍然遵循Apri

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

14、据分割的方法,Apriori算法在执行过程中是先生成候选集再剪枝，可是生成的候选集并不都是有效的。候选集的产生需要花费很大的代价。把数据分割技术应用到关联规则挖掘中，可以改善关联规则挖掘在大数据集中的适应性。 其基本思想：首先将大数据集从逻辑上分成互不相交的块，每块应用挖掘算法（如Apriori算法）生成局部的频繁项目集，然后将这些局部的频繁项目集作为全局候选频繁项目集，通过测试他们的支持度来得到最终的全局频繁项目集。 其可在以下两方面改善Apriori关联规则挖掘算法的性能： 1合理利用主存空间：数据分割将大数据集分成小的块，为块内数据一次性导入主存提供机会。 2支持并行挖掘算法：每个分块的

15、局部频繁项目集是独立生成的，因此提供了开发并行数据挖掘算法的良好机制。,定理 设数据集D被分割成分块D1， D2， ， Dn，全局最小支持度为minsupport，假设对应的全局最小支持数为minsup_count。如果一个数据分块Di 的局部最小支持数记为minsup_counti (i=1，2，n)，则局部最小支持数minsup_counti按照如下方法生成： minsup_counti = minsup_count *|Di| / |D| 可以保证所有的局部频繁项目集涵盖全局频繁项目集。,基于散列的方法,1995，Park等发现寻找频繁项目集的主要计算是在生成2-频繁项目集上。因此，Pa

16、rk等利用了这个性质引入散列技术来改进产生2-频繁项目集的方法。 例：桶地址 =（10 x + 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,L2=(I2，I3) ，(I1，I2) ，(I1，I3),随着数据库容量的增大，重复访问数据库（外存）将导致性能低下。因此，探索新的理论和算法来减少数据库的扫描次数和侯选集空间占用，已经成为近年来关联规则挖掘研究的热点之一。 两个典型的方法： Close算

17、法 FP-tree算法,项目集格空间理论的发展,Close算法对应的原理,一个频繁闭合项目集的所有闭合子集一定是频繁的；一个非频繁闭合项目集的所有闭合超集一定是非频繁的。 什么是一个闭合的项目集？ 一个项目集C是闭合的，当且仅当对于在C中的任何元素，不可能在C中存在小于或等于它的支持度的子集。 例如，C1=AB3，ABC2是闭合的； C2=AB2，ABC2不是闭合的；,CLOSS算法的基本思路：利用频繁闭合i_项目集FCi，生成频繁闭合i+1 _项目集FCi+1（i1）。 首先找出候选频繁闭合1_项目集FCC1，通过扫描数据库得到候选闭合项目集，再经修剪得到频繁闭合项目集FC1项目集。用FC1

18、产生候选频繁闭合2_项目集FCC2，再经修剪得到频繁闭合项目集FC2项目集。在用FC2推出FC3 ，如此继续直到某个FCCr 为空时停止。,Close算法的例子,扫描数据库得到: FCC1=(A,3), (B,5), (C,4), (D,3), (E,3)； 相应闭合项目集为: FCl(A)=ABC,3(计算A的闭合过程:第一项包含A,首先得到A的闭合为ABCD,第三项也包含A, 故取ABCD与第三项的交ABC作为A的闭合，第五项也包含A, 故取ABC与第五项的交ABC作为A的闭合,这时到了最后一项,计算完毕)。同理，FCl(B)=B,5，FCl(C)=BC,4，FCl(D)=BD,3，FCl

19、(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）：,样本数据库,FP-tree算法的基本原理,2000年Han等提出了一个称为FP-Tree（频繁模式树）的算法，该算法只进行 2 次数据库扫描，不使用侯选集，直接压缩数据库成一个FP-Tree ，然后通过该树生成关联规则。构造FP-Tree的过程如下 ： 按Aprio

20、ri算法，扫描数据库一次生成1-频繁项目集，并按频度降序排序，放入L列表中； 创建根结点，标志为null，扫描数据库一次，当得到数据库的一个项目（元组）时，就把其中的元素按L表中的次序排列，然后通过递归实现FP-Tree的增长；,FP-tree算法的基本原理,样本数据库,下面看一个例子来说明FP-Tree的增长过程,最小支持度阈值为3。,L,扫描数据库一次生成1-频繁项目集（在数据库中出现3次或3次以上的），并按频度降序排序，放入L列表中；,(1-频繁项目集),FP-tree算法的基本原理,样本数据库,L,T1,T2,T3,T4,扫描数据库,依次增长FP-tree，并改变支持数,T5,FP-t

21、ree算法的基本原理,L,建立索引,用FP-Tree挖掘频繁集的基本思想是分而制之，即使用FP-Tree 递归增长频繁集的方法： 对每个项，生成其条件模式库，然后生成其条件FP-Tree； 对每个新生成的条件FP-Tree，重复此步骤； 直到结果FP-Tree为空，或只含唯一的一个路径，此路径的每个子路径对应的项目集都是频繁集。,从FP-Tree建立条件模式库,对应的条件模式库,FP-tree,L,用条件模式库建立对应的条件FP-Tree,m-条件 模式库,m-条件FP-Tree,L,m-条件FP-Tree,用条件FP-Tree挖掘频繁项集,m-条件FP-Tree,得到的频繁项目集合，,多层次

22、关联规则挖掘,根据规则中涉及到的层次，多层次关联规则可以分为： 同层关联规则：如果一个关联规则对应的项目是同一个粒度层次，那么它是同层关联规则。如“牛奶面包”和“羽绒服酸奶”都是同层关联规则;,关联规则挖掘中的一些更深入的问题,层间关联规则：如果在不同的粒度层次上考虑问题，那么可能得到的是层间关联规则。如“夏季服装酸奶”都是层间关联规则;,多层次关联规则挖掘,多层次关联规则挖掘的度量方法可以沿用 “支持度-可信度”的框架。不过，多层次关联规则挖掘有两种基本的设置支持度的策略： 统一的最小支持度：算法实现容易，而且很容易支持层间的关联规则生成。但是弊端也是显然的： 不同层次可能考虑问题的精度不同、面向的用户群不同 对于一些用户，可能觉得支持度太小，产生了过多不感兴趣的规则。而对于另外的用户来说，又认为支持度太大，有用信息丢失过多。,不同层次使用不同的最小支持度：每个层次都有自己的最小支持度。较低层次的最小支持度相对较小，而较高层次的最小支持度相对较大。这种方法增加了挖掘的灵活性。但是，也留下了许多相关问题需要解决： 首先，不同层次间的支持度应该有所关联，只有正确地刻画这种联系或找到转换方法，才能使生成的关联规则相对客观。 其次，由于具有不同的支持度，层间的关联