关联规则挖掘算法综述

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.

关键词：关联规则挖掘算法综述