关联规则挖掘算法综述

摘 要 本文介绍了关联规则的基本概念和分类方法，列举了一些关联规则挖掘算法并简要分析了典型算法，展望了关联规则挖掘的未来研究方向。

1 引言



关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。

关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。

Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题[AIS93b]，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率；对关联规则的应用进行推广。

最近也有独立于Agrawal的频集方法的工作[HPY00]，以避免频集方法的一些缺陷，探索挖掘关联规则的新方法。也有一些工作[KPR98]注重于对挖掘到的模式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。

2 基本概念

设I={i1,i2,..,im}是项集，其中ik(k=1,2,…,m)可以是购物篮中的物品，也可以是保险公司的顾客。设任务相关的数据D是事务集，其中每个事务T是项集，使得TÍI。设A是一个项集，且AÍT。

关联规则是如下形式的逻辑蕴涵：A Þ B，AÌI, AÌI，且A∩B=F。关联规则具有如下两个重要的属性：

支持度: P(A∪B)，即A和B这两个项集在事务集D中同时出现的概率。

置信度: P(B｜A)，即在出现项集A的事务集D中，项集B也同时出现的概率。

同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。给定一个事务集D，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。

3 关联规则种类

1) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。

布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。

数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。

2) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。

在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的。

在多层关联规则中，对数据的多层性已经进行了充分的考虑。

3) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。

在单维关联规则中，我们只涉及到数据的一个维，如用户购买的物品

在多维关联规则中，要处理的数据将会涉及多个维。


4 算法综述

4.1 经典的频集算法

Agrawal等于1994年提出了一个挖掘顾客交易数据库中项集间的关联规则的重要方法 [AS94a, AS94b]，其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。

所有支持度大于最小支持度的项集称为频繁项集，简称频集。



4.1.1 算法的基本思想

首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。

挖掘关联规则的总体性能由第一步决定，第二步相对容易实现。

4.1.2 Apriori核心算法分析

为了生成所有频集，使用了递推的方法。其核心思想简要描述如下：

(1) L1 = {large 1-itemsets};

(2) for (k=2; Lk-1¹F; k++) do begin

(3) Ck=apriori-gen(Lk-1); //新的候选集

(4) for all 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³minsup}

(10) end

(11) Answer=∪kLk;

首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。

可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。


4.1.3 算法的优化

为了提高算法的效率，Mannila等引入了修剪技术来减小候选集Ck的大小[MTV94]，由此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果Ck中某个候选项集有一个(k-1)-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。

4.2 改进的频集算法

4.2.1散列

该算法由Park等在1995年提出[PCY95b]。通过实验发现寻找频繁项集的主要计算是在生成频繁2项集L2上，Park就是利用这个性质引入散列技术来改进产生频繁2项集的方法。

其基本思想是：当扫描数据库中每个事务，由C1中的候选1项集产生频繁1项集L1时，对每个事务产生所有的2项集，将它们散列到散列表结构的不同桶中，并增加对应的桶计数，在散列表中对应的桶计数低于支持度阈值的2项集不可能是频繁2项集，可从候选2项集中删除，这样就可大大压缩了要考虑的2项集。


4.2.2 事务压缩

Agrawal等提出压缩进一步迭代扫描的事务数的方法[AS94b, HF95]。因为不包含任何K项集的事务，不可能包含任何（K+1）项集，可对这些事务加上删除标志,扫描数据库时不再考虑。


4.2.3 杂凑

一个高效地产生频集的基于杂凑的算法由Park等提出[PCY95a]。通过实验我们可以发现寻找频集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。


4.2.4 划分

Savasere等设计了一个基于划分的算法[SON95]，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频集。更多的关于生成频集的并行化方法可以在文献[AS96]中找到。


4.2.5 选样

基本思想是在给定数据的一个子集挖掘。对前一遍扫描得到的信息，仔细地组合分析，可以得到一个改进的算法，Mannila等先考虑了这一点[MTV94]，他们认为采样是发现规则的一个有效途径。随后又由Toivonen进一步发展了这个思想[Toi96]，先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。Toivonen的算法相当简单并显著地减少了I/O代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲(data skew)。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价可能同扫描一遍数据库相近。


4.2.6 动态项集计数

Brin等人给出该算法[BMUT97]。动态项集计数技术将数据库划分为标记开始点的块。不象Apriori仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。该技术动态地评估以被计数的所有项集的支持度，如果一个项集的所有子集以被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori 少。


4.3 FP-树频集算法



针对Apriori算法的固有缺陷，J. Han等提出了不产生候选挖掘频繁项集的方法—FP-树频集算法[HPY00]。采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之apriori算法有巨大的提高。


4.4 多层关联规则挖掘


对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发现一些强关联规则。当我们引入概念层次后，就可以在较高的层次上进行挖掘[HF95, SA95]。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样一种在多个层次上进行挖掘的功能。

多层关联规则的分类：根据规则中涉及到的层次，多层关联规则可以分为同层关联规则和层间关联规则。

多层关联规则的挖掘基本上可以沿用“支持度-可信度”的框架。不过，在支持度设置的问题上有一些要考虑的东西。

同层关联规则可以采用两种支持度策略：

1) 统一的最小支持度。对于不同的层次，都使用同一个最小支持度。这样对于用户和算法实现来说都比较的容易，但是弊端也是显然的。

2) 递减的最小支持度。每个层次都有不同的最小支持度，较低层次的最小支持度相对较小。同时还可以利用上层挖掘得到的信息进行一些过滤的工作。

层间关联规则考虑最小支持度的时候，应该根据较低层次的最小支持度来定。



4.5 多维关联规则挖掘

对于多维数据库而言，除维内的关联规则外，还有一类多维的关联规则。例如：

年龄（X，“20…30”） 职业（X,“学生”）==> 购买(X，“笔记本电脑”)

在这里我们就涉及到三个维上的数据：年龄、职业、购买。

根据是否允许同一个维重复出现，可以又细分为维间的关联规则（不允许维重复出现）和混合维关联规则（允许维在规则的左右同时出现）。

年龄（X，“20…30”） 购买(X，“笔记本电脑”) ==> 购买(X，“打印机”)

这个规则就是混合维关联规则。

在挖掘维间关联规则和混合维关联规则的时候，还要考虑不同的字段种类：种类型和数值型。

对于种类型的字段，原先的算法都可以处理。而对于数值型的字段，需要进行一定的处理之后才可以进行[KHC97]。处理数值型字段的方法基本上有以下几种：

1) 数值字段被分成一些预定义的层次结构。这些区间都是由用户预先定义的。得出的规则也叫做静态数量关联规则。

2) 数值字段根据数据的分布分成了一些布尔字段。每个布尔字段都表示一个数值字段的区间，落在其中则为1，反之为0。这种分法是动态的。得出的规则叫布尔数量关联规则。

3) 数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的因素。得出的规则叫基于距离的关联规则。

4) 直接用数值字段中的原始数据进行分析。使用一些统计的方法对数值字段的值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较从而得出一些有用的规则。得出的规则叫多层数量关联规则。


5 展望

对于关联规则挖掘领域的发展，笔者认为可以在如下一些方向上进行深入研究：在处理极大量的数据时，如何提高算法效率；对于挖掘迅速更新的数据的挖掘算法的进一步研究；在挖掘的过程中，提供一种与用户进行交互的方法，将用户的领域知识结合在其中；对于数值型字段在关联规则中的处理问题；生成结果的可视化，等等。



参考文献

[AIS93b] R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. Proceedings of the ACM SIGMOD Conference on Management of data, p.p. 207-216, May 1993.



[AS94a] R. Agrawal, and R. Srikant. Fast algorithms for mining association rules in large database. Technical Report FJ9839, IBM Almaden Research Center, San Jose, CA, Jun. 1994.



[AS94b] R. Agrawal, and R. Srikant. Fast algorithms for mining association rules. In Proc. 1994 Int. Conf. Very Large Databases(VLDB’94), Sep. 1994.



[AS96] R. Agrawal, and J. Shafer. Parallel mining of association rules: Design, Implementation, and Experience. IEEE Trans. Knowledge and data engineering, 8:962-969, Jan. 1996.



[BMUT97] 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, p.p. 255-264, May 1997.



[HF95] J, Han and Y. Fu. Discovery of multiple-level association rules from large databases. In Proc. 1995 Int. Conf. Very Large Databases(VLDB’95), p.p. 402-431, Sep. 1995.



[HPY00] J.Han,J.Pei, and Y.Yin.Mining. Frequent patterns without candidate generation. In Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’00), p.p. 1-12, May 2000.



[KHC97] M. Kamber, J. Han, J. Chang. Metarule-guided mining of multi-dimensional association rules using data cubes. In Proc. 1997 Int. Conf. Khowledge Discovery and Data Mining(KDD’97), p.p. 207-210, Aug. 1997

[KPR98] J. Kleinberg, C. Papadimitriou, and P. Raghavan. Segmentation problems. Proceedings of the 30th Annual Symposium on Theory of Computing, ACM. Sep. 1998.

[MTV94] H. Mannila, H. Toivonen, and A. Verkamo. Efficient algorithm for discovering association rules. AAAI Workshop on Knowledge Discovery in Databases, p.p. 181-192, Jul. 1994.

[PCY95a] 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, p.p. 175-186, May 1995.

[PCY95b] J. S. Park, M. S. Chen, and P. S. Yu. Efficient parallel data mining of association rules. 4th International Conference on Information and Knowledge Management, Baltimore, Maryland, Nov. 1995.

[SA95] R. Srikant, and R. Agrawal. Mining generalized association rules. Proceedings of the 21st International Conference on Very Large Database, p.p. 407-419, Sep.1995.

[SON95] A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases. Proceedings of the 21st International Conference on Very Large Database, p.p. 432-443, Sep. 1995.

[Toi96] H. Toivonen. Sampling large databases for association rules. Proceedings of the 22nd International Conference on Very Large Database, Bombay, India, p.p. 134-145, Sep. 1996.