关联规则挖掘研究综述

1、    关联规则挖掘研究综述        刘东波1,2 卢正鼎1 时间:2007年08月20日     字 体: 大 中 小        关键词:<"cblue" " target='_blank'>关联规则<"cblue" " target='_bla

2、nk'>关联规则挖掘<"cblue" " target='_blank'>数据挖掘<"cblue" " target='_blank'>最大<"cblue" " target='_blank'>I/O            摘要：本文首先回顾了<"cblue" &q

3、uot; title="关联规则">关联规则挖掘研究进展情况，然后对关联规则问题进行了形式化描述，最后讨论了<"cblue" " title="关联规则挖掘">关联规则挖掘的处理流程和主要算法。?关键词：<"cblue" " title="数据挖掘">数据挖掘? 关联规则? 支持度? 可信度?关联规则挖掘研究进展数据挖掘是指从大量数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知识和规则的高级处理过程1,2。通过数据挖掘，有价值的知识、规则或高

4、层次的信息就能从数据库的相关数据集合中抽取出来，并从不同角度展现，从而使大型数据库作为一个丰富、可靠的资源为知识的提取服务。?R. Agrawal等人在1993年首先提出在交易数据库中挖掘关联规则3，典型的例子是“多数顾客在购买面包和黄油的同时也会购买牛奶”，找出所有这类规则，对于确定市场策略是很有价值的，例如可用于追加销售、仓储规划，并可根据购买模式对顾客进行划分。?AIS算法是第一个发表的生成事务数据库中所有大项目集的算法3。它集中在增强数据库必要的功能以支持决策支持查询。该算法的目标是发现定性规则。该技术的局限性是结论中只有一个项目。即关联规则是形如XTIj | a的规则，其中X是一个项

5、目集合，Ij是值域I中的单个项目，a是规则的置信度。?AIS算法要对整个数据库进行多次分析。每次分析都要扫描全部事务。第一次分析计算数据库中单个项目的支持度，并确定哪个是大或频繁项目集。对每次分析的大项目集进行扩展以生成候选项目集。扫描一个事务之后，可确定上一次分析的大项目集和该事务项目的公共项目集。这些公共项目集被该事务中的其它项目扩展，生成新的候选项目集。大项目集l只能由在当前事务中的大项目并且按照词典顺序位于l中所有项目之后的项目。为了高效地完成该任务，它采用了一种评估工具和剪枝技术。该评估和剪枝技术通过删除候选集合中不必要的项目集来确定最终的候选集合。然后计算每个候选集合的支持度。支持

6、度大于等于最小支持度阈值的候选集合被选出作为大项目集。这些大项目集继续被扩展以生成下一次分析的候选集合。直到不能发现更多大项目集时该处理过程结束。?STEM算法在4中提出，其目的是用SQL来处理候选大项目集5。在该算法中，大项目集组成的集合的每个成员形如，其中TID是事务的唯一标识符。类似地，候选项目集组成的集合的每个成员形如。与AIS算法类似，SETM算法也要多次分析数据库。?Apriori是对AIS和SETM算法的改进，并且是第一个可扩展的关联规则挖掘算法2,6。当进行初始数据库扫描时Apriori算法搜索大项目集合，然后用该搜索结果作为后续扫描并发现其它达数据集合的种子。支持度大于给定最

7、小值的规则称为大项目集（large itemsets）频繁项目集（frequent itemsets），支持度小于给定最小值规则称为小项目集（small itemsets）7。?简而言之，给定一个数据集合，Apriori算法需要通过初始扫描整个数据集合产生一个支持度不小于指定最小值的项目集合。生成该项目集合（称为1-候选集合）之后，再形成下一个候选集合（称为2-候选集合）。再次扫描数据库来计算2-候选集合的支持度。所有支持度小于最小值的集合将被剪裁掉。当不再生成新的候选集合时算法终止，得到k-候选集合。?该算法基于频繁项目集合的性质，即一个频繁集合的任何子集都是频繁集合；如果一个项目集合不是频

8、繁集合，其所有超集均不是频繁集合8。?有一些Apriori算法的变型，如AprioriTID和AprioriHybrid。AprioriTID的工作原来与Apriori类似，所不同的是它用生成的项目集合计算支持度，取代了通过数据库扫描计算支持度的方法。据报道，只有当AprioriTID生成的项目集合能够放在内存时，AprioriTID才比Apriori效率更高。AprioriHybrid是Apriori和AprioriTID的混合体。该算法用Apriori进行初始扫描，一旦认为生成的集合能够与内存匹配则切换到AprioriTID算法。在大多数情况下AprioriHybrid算法比Apriori

9、算法效率高，但是当进行到最后一次扫描时是个例外。这是因为它花费了过高的代价获取无意义的项目。Apriori算法比其它一些算法（如SETM和AIS）更有效6,9。?此后，研究人员对关联规则挖掘问题进行了深入的研究，通过引入随机采样和并行挖掘等思想，对原有算法进行了优化，以提高挖掘算法的执行效率。?J. S. Park等人指出，Apriori算法的计算开销主要在频繁2项目集的计算上，因此提出了基于Hash技术对生成的候选2项目集进行裁剪的DHP算法10。Apriori算法和DHP算法扫描数据库的次数是和<"cblue" " title="最大"

10、;>最大频繁项目集的长度一致的，但是对大型数据库系统一次数据库扫描的代价是非常昂贵的，所以数据库扫描的次数成为关联规则挖掘算法的一个主要的瓶颈问题。?A. Savasere等人提出了分区（Partition）算法11，该算法将数据库扫描的次数降为两次。Partition算法逻辑上将数据库划分为互不相交的若干个区，算法首先找出每个分区中的局部频繁项目集，然后根据“频繁项目集至少在一个分区中是频繁的”这一性质，合并所有的局部频繁项目集，最后对合并后所有的局部频繁项目集进行全局计数，得到全局频繁项目集。?H. Toivonen等人提出了基于采样的关联规则挖掘算法12，该算法通过数据库的一个随机

11、采样数据生成候选频繁项目集，然后扫描整个数据库对其进行验证。基于采样的算法多数情况下只需扫描一次数据库，最坏的情况下也只需两次扫描，但该算法所获得的高效率是以牺牲挖掘精度来换取的，有可能丢失一些全局频繁项目集。?为了进一步提高算法的有效性，S. Brin等人提出了动态项目集计数（DIC）算法13，该算法将数据库划分为若干分区并且对每个分区的开始做标记，不同于Apriori算法的是，在数据库扫描过程中，DIC算法可以在各个分区的标记点添加候选项目集，而不是像Apriori那样只能在每次完成整个数据库扫描之后添加候选项目集，这样便极大地减少了数据库扫描次数。?J. Han等人提出了一种无需生成候选

12、频繁项目集的算法FP-Growth（频繁模式增长算法）14，该算法首先将数据库压缩成一个高度浓缩的数据结构FP树，随后发现频繁项目集的工作都在该FP树上完成，这样就避免了多次数据库扫描。另外，FP-Growth算法直接在FP树上发现频繁项目集，避免了产生数目庞大的候选频繁项目集，因此FP-Growth算法较Apriori算法的效率有一个量级的提高。?Ei-Hajj等人提出了一种基于反转矩阵（Inverted Matrix）的算法15，它类似于FP-Growth算法，该算法首先将数据库映射为一个基于磁盘的反转矩阵，然后针对该反转矩阵在内存中建立COFI（Co-Ocurrence Frequent

13、 Item）树，利用COFI树发现频繁项目集。实验结果表明，该算法优于Apriori和FP-Growth，对于超大规模数据库和较小支持度的情况，优势更加明显。另外，反转矩阵的结构特点决定了它便于实现并行挖掘算法。?除了上述基本关联规则挖掘算法研究，人们还进行了诸如多层关联规则、量化关联规则、基于约束的关联规则、时态关联规则、空间关联规则等类型关联规则挖掘算法的研究。?Srikant和Agrawal从广义关联规则挖掘的角度研究了多层关联规则挖掘问题16，多层关联规则挖掘利用概念分层的背景知识在更高的抽象层次上挖掘关联规则，从而解决了稀疏数据中关联规则的支持度阈值过低而难以挖掘的问题。?Srika

14、nt等人通过将数值型数据划分为不同区间的方法，在这些区间之上进行定量关联规则的挖掘17。?为了克服Agrawal频集方法的缺陷，人们还提出了一些新的关联规则挖掘方法18,19,20,21,22,23,24。?关联规则问题描述本节给出关联规则挖掘问题的形式描述。?定义2.1 令I = I1, I2, , Im是由m个不同项目（Items）组成的集合，D是由事务T组成的集合（数据库），这里事务T是项目的集合，并且T í I。其中，每个事务T有一个唯一标识，记为TID。关联规则是形如XTY的蕴涵式，其中X í ?I，Y í ?I，而且X ?Y = f。这里，X 称为前提

15、，Y 称为结论。?下面定义关联规则的两个重要测度：支持度S（Support）和可信度C（Confidence）。?定义2.2 关联规则XTY在事务集合D中的支持度是?S(XTY) = |T: XèYíT, T?D| / |D|?其中，|T: XèYíT, T?D|是D中包含X和Y的事务数，|D|是D中所有事务数。?定义2.3 关联规则XTY在事务集合D中的可信度是?C(XTY) = |T: XèYíT, T?D| / |T: XíT，T?D|?其中，|T: XèYíT, T?D|是包含X和Y的事务数，|T

16、: XíT，T?D|是包含X的事务数。?给定一个事务集合（数据库）D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度Smin和最小可信度Cmin的关联规则。?关联规则挖掘算法经典频繁集合方法?Agrawal等人1993年3首先提出挖掘顾客交易数据库中项目集之间关联规则的问题，这是一种基于频繁集合理论的递推方法，它将关联规则挖掘算法分解为两个步骤：?1. 找到所有支持度大于最小支持度Smin的项目集合（Itemsets），这些项集称为频繁集合（Frequent Itemsets)；?2. 使用第1步找到的频繁集合产生期望的规则。?如给定了一个频繁集合Y=I1I2.I

17、k，k32，IjI，产生只包含集合I1，I2，.，Ik中项目的所有规则（最多k个），其中每一个规则的右部只有一项，(即形如Y-IiTIi，'1ik)，这里采用的是13中规则的定义。一旦生成了这些规则，只有那些大于用户给定的最小可信度的规则才被留下来。对于规则右部含两个以上项目的规则，我们将在后面讨论。?为了生成所有频繁集合，使用了递推的方法。其核心算法如下：?(1)? L1 = large 1-itemsets;?(2)? for (k=2; Lk-11F; k+) do begin?(3)? ? Ck=apriori-gen(Lk-1);? /新的候选集?(4)? ? for all

18、 transactions t?D do begin?(5)? ? ?Ct=subset(Ck, t);? /事务t中包含的候选集?(6)? for all candidates c? Ct do?(7)? c.count+;?(8)? ? end?(9)? Lk=c? Ck |c.count 3 Smin?(10)? end?(11)? Answer = èkLk;?首先产生频繁1-项目集L1，然后是频繁2-项目集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项目集的集合Ck，Ck中的每一个项目集是对两个只有一个项不同的属于Lk-1的频繁集合

19、做一个(k-2)-连接来产生的。Ck中的项目集是用来产生频繁集合的候选集，最后的频繁集合Lk必须是Ck的一个子集。Ck中的每个元素需在事务数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的事务数据库，即如果频繁集合最多包含10个项目，那么就需要扫描事务数据库10遍，这需要很大的<"cblue" " title="I/O">I/O开销。?在文献25中，Agrawal等人用剪枝技术（Pruning）来减小候选集Ck的大小，由此可以显著地改进生成所有频繁集合算法的性能。算法中引入的剪枝

20、策略基于这样一个性质：一个项目集是频繁集合当且仅当它的所有子集都是频繁集合。那么，如果Ck中某个候选项目集合有一个(k-1)-子集不属于Lk-1，则这个项目集可以被剪掉不再被考虑，这个剪枝过程可以降低计算所有的候选集合的支持度的代价。文献25中还引入了杂凑树（Hash Tree）方法来有效地计算每个项目集的支持度。?频繁集合算法的几种优化方法?虽然Apriori算法自身已经进行了一定的优化，但是在实际应用中还是存在不令人满意的地方，于是人们相继提出了一些优化方法。?1.?划分方法Savasere等11设计了一个基于划分（partition）的算法，该算法先把数据库从逻辑上分成几个互不相交的块，

21、每次单独考虑一个分块并对它生成所有的频繁集合，然后把产生的频繁集合合并，用来生成所有可能的频繁集合，最后计算这些项目集的支持度。这里，分块的大小要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频繁集合至少在某一个分块中是频繁集合保证的。上面所讨论的算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频繁集合。产生频繁集合的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项目集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频繁集合的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频繁集合。其它

22、关于生成频繁集合的并行方法详见10,26。?2. Hash方法Park等10提出了一种基于杂凑（Hash）方法的算法，可以高效产生频繁集合。通过实验我们可以发现寻找频繁集合主要的计算是在生成频繁2-项目集Lk上，Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项目集的方法。?3. 采样方法基于前一遍扫描得到的信息，对此仔细地进行组合分析，可以得到一个改进的算法，Mannila等27首先考虑到这一点，认为采样是发现规则的一个有效途径。随后又由Toivonen12进一步发展了这个思想，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。

23、Toivonen的算法相当简单并显著地降低了I/O开销，但该算法最大的缺点是产生的结果不精确，存在所谓的数据扭曲(Data Skew)。分布在同一页面上的数据通常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。Lin和Dunham在28中讨论了反扭曲(Anti-skew)算法来挖掘关联规则，在那里他们引入的技术使得扫描数据库的次数少于2次。?Brin等13提出的算法使用比传统算法少的扫描遍数来发现频繁集合，同时比基于采样的方法使用更少的候选集，这些改进了算法在低层的效率。具体的考虑是，在计算k-项目集时，一旦认为某个(k+

24、1)-项目集可能是频繁集合，就并行地计算该(k+1)-项目集的支持度，算法所需的总的扫描次数通常少于最大频繁集合的项目数。?4.?减少事务个数减少用于未来扫描的事务集合的大小。一个基本的原理就是当一个事务不包含长度为k的大项目集，则必然不包含长度为k+1的大项目集。从而我们就可以将这些事务删掉，这样在下一遍的扫描中就可以减少事务的个数。?其它频繁集合挖掘方法?前面介绍的都是基于Apriori的频繁集合方法。即使进行了优化， Apriori方法固有的缺陷仍然无法克服。?（1）Apriori可能产生大量的候选集。当长度为1的频繁集合有10000个时，长度为2的候选集个数将会超过10M。另外，如果要

25、生成一个很长的规则，产生的中间元素的数量也是巨大的。?（2）Apriori无法对稀有信息进行分析。由于频繁集合使用了参数Smin（最小支持度），所以就无法对小于Smin的事件进行分析；而如果将Smin设成一个很低的值，那么算法的效率就会很低。?下面介绍两种方法，分别用来解决上述两个问题。?文献14提到了一种解决问题（1）的FP-growth方法。该方法采用分而治之的策略：在经过第一次扫描之后，把数据库中的频繁集合压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息。随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频繁集合相关。然后再对这些条件库分别进行挖掘。当原始数

26、据量很大的时候，也可以结合划分的方法，使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨大的提高。?文献29中介绍了一种解决问题（2）的方法。该方法基于这样的思想：Apriori算法得出的关系都是频繁出现的，但在实际应用中，我们可能需要寻找一些高度相关的元素，即使这些元素不是频繁出现的。在Apriori算法中，起决定作用的是支持度，而我们现在把可信度放在第一位，挖掘一些具有高可信度的规则。?整个算法大致分成计算特征、生成候选集、过滤候选集三个步骤。在这三个步骤中，关键是在计算特征时Hash方法的使用。在考虑

27、算法的时候，有几个衡量好坏的指标：时空效率、错误率和遗漏率。?基本的方法有两类：?（1）Min_Hashing的基本思想是，将一条记录中的头k个为1的字段的位置作为一个Hash函数。该方法的遗漏率为零，错误率可以由k严格控制，但是时空效率相对较差。?（2）Locality_Sentitive_Hashing的基本思想是，将整个数据库用一种基于概率的方法进行分类，使得相似的列在一起的可能性更大，不相似的列在一起的可能性较小。该算法的遗漏率和错误率是无法同时降低的，但它的时空效率却比较高。?结束语本文回顾了关联规则挖掘研究的进展情况，对关联规则问题进行了形式化描述，最后总结了关联规则挖掘的处理流程

28、和主要算法。?参考文献1 BERRY, M.J. and LINOFF, G. Data Mining Techniques. John Wiley & Sons, New York. 1997.?2 U. M.Fayyad，G. Piatesky-Shapiro，P. Smyth，and R. Uthurusamy Eds. Advances in Know<"innerlink" " title="led">ledge Discovery and Data Mining. AAAI/MIT Press，1996.?3 R

29、. Agrawal, T. Imielinski and A. Swami. Mining Association Rules between Sets of Items in Large Databases. In Proc. 1993 ACM-SIGMOD Int. Conf. Management of Data, Washington, D.C., pages 207216, May 1993.?4 M. Houtsma and A. Swami, Set-Oriented Mining for Association Rules in Relational Databases, Pr

30、oceedings of the 11th IEEE International Conference on Data Engineering, pp. 25-34, Taipei, Taiwan, March 1995.?5 R. Srikant, Fast Algorithms for Mining Association Rules and Sequential Patterns, Ph.D Dissertation, 1996, University of Wisconsin, Madison.?6 R. Agrawal and R. Srikant. Fast algorithms

31、for mining association rules. In Proc. 1994 Int. Conf. Very Large Databases，pages 487-499，Santiago，Chile，September 1994.?7 M. Chen, J. Han and P. Yu. Data mining: An overview from database perspective. IEEE Transactions on Knowledge and Data Eng., pages 866883, December 1996.?8 J. W. Han，Y. Cai and

32、N. Cercone. Knowledge Discovery in Databases: an Attribute-Oriented Approach. Proc. of 18th VLDB，1992:547-559, 1992.?9 J. Hipp, U. Guntzer, and G. Nakaeizadeh. Algorithms for Association Rule Mining - A General Survey and Comparison. In Proc. ACM SIGKDD International Conference on Knowledge Discover

33、y and Data Mining, pages 5864, July 2000.?10 J. S. Park，M. S. Chen，and P. S. Yu. An effective hash-based algorithm for mining association rules. Proceedings of ACM SIGMOD International Conference on Management of Data，pages 175-186，San Jose，CA，May 1995.?11 A. Savasere，E. Omiecinski，and S. Navathe. A

34、n efficient algorithm for mining association rules in large databases. Proceedings of the 21st International Conference on Very large Database，1995.?12 H. Toivonen. Sampling large databases for association rules. Proceedings of the 22nd International Conference on Very Large Database，Bombay，India，Se

35、ptember 1996.?13 S. Brin，R. Motwani，J. D. Ullman，and S. Tsur. Dynamic Itemset counting and implication rules for market basket data. In ACM SIGMOD International Conference On the Management of Data. 1997.?14 J. Han，J. Pei，and Y. Yin.Mining frequent patterns without candidate generation.In Proc.2000

36、ACM-SIGMOD Int.Conf.Management of Data(SIGMOD00)，Dalas，TX，May 2000.?15 Mohammad Ei-Hajj, Osmar R. Za?ane. Inverted Matrix Efficient Discovery of Frequent Items in Large Datasets in the Context of Interactive Mining. SIGKDD03 Washington DC, USA, 2003.?16 R. Srikant，and R. Agrawal. Mining generalized

37、association rules. Proceedings of the 21st International Conference on Very Large Database，1995，pp. 407-419.?17 R. Srikant，and R. Agrawal. Mining quantitative association rules in large relational tables.? Proceedings of the ACM SIGMOD Conference on Management of Data，1996. pp.1-12.?18 E. Omiecinsky

38、, A. Sarasere, and S. Navathe. An efficient Algorithm for Mining Association Rules in Large Databases. In Proc. of the 21st VLDB conference, Zurich, Switzerland, pages 432444, September 1995.?19 Y. Yin, J. Pei, and J. Han. Mining Frequent Patterns Without Candidate Generation. In Proc. 2000 ACM-SIGM

39、OD Int. Conf. Management of Data (SIGMOD00), Dallas, Texas, pages 112, May 2000.?20 M. J. Zaki, S. Parthasarathy, M. Ogihara andW. Li. New Algorithms for Fast Discovery of Association Rules. In Proc. 3rd Intl Conf. Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, California, pages 283286

40、, April 1997.?21 M. Mehta, R. Agrawal, and J. Shafer. Sprint: A scalable parallel classifier for data mining. In Proc. Of the 1996 Int. Conf. Very Large Data Bases, Bombay, India, pages 544555, September 1996.?22 W. Hsu, B. Liu, and Y. Ma. Integrating Classification and Association Rule Mining. In Proc. of the Fourth International Conference on Knowledge Discovery and Data Mining KDD-98, New York, USA, pa