摘 要:数据挖掘中的关联规则挖掘近些年一直是人们研究的热点。但是关联规则挖掘的经典算法Apriori存在着挖掘效率低、系统开销大等问题。AprioriTid、DIC等算法，也仅从某一方面进行了改进。针对上述问题，提出了一种新的改进算法，新算法从三大方面对原有的算法进行了改进，以此提高算法的效率，降低系统的开销。
关键词:数据挖掘;关联规则; Apriori; AprioriTid; DIC
数据库中大量的数据与数据之间存在着某种联系，这种数据之间的联系就属于一种重要的知识，也是进行数据挖掘的对象，即关联规则挖掘[1]。在众多的关联规则挖掘算法中最著名的是Apriori算法[2]。它的基本思想是使用一种逐层搜索的迭代算法。但是Apriori算法也有明显的缺点：每次都会产生大量的候选频繁项集，而且候选频繁项集呈指数级增长。每产生一个频繁项目集就需要扫描一次完整的数据库。这些都需要耗费巨大的系统资源而且算法的执行速度、效率也比较低。因此人们提出了许多改进的Apriori算法，本文吸取前人的经验提出了一种新的改进Apriori算法，称为Apriori-Evo算法。
1 Apriori算法分析
Apriori算法的基本步骤是：首先扫描事务数据库D中的事务，统计各个项目出现的次数来产生频繁项目集L1,然后由L1×L1进行连接运算生成候选2-项集C2，扫描数据库统计各个候选2-项集出现的次数,确定其中的频繁2-项集L2。再由L2×L2进行连接运算产生候选3-项集C3，一直反复进行这个过程生成频繁k-项集Lk，直到无法再生成频繁项目集为止。
代码中apriori_gen( )函数[3]主要完成两个动作：连接和剪枝运算。Lk-1与Lk-1进行连接生成候选频繁项集。然后剪枝部分利用Apriori的性质删除掉包含非频繁子集的候选。
Apriori算法的主要缺点是会产生大量的候选项集，如果频繁1-项集有10 000个，则候选2-项集的个数将超过10 000 000个，算法实现时，大量的候选2-项集都被存放在哈希树中，对它们的统计和测试所需要的开销会很大;每产生一个频繁项目集就需要将整个事务数据库扫描一遍，大大降低了系统I/O效率。
2 对Apriori算法的改进
关联规则具有如下性质：
(1)对于项目集X和它的任意子集Y，如果X是频繁的，则它的子集Y一定也是频繁的。
(2)对于项目集X和它的任意子集Y，如果Y是非频繁项目集，则X也一定不是频繁项目集。
(3)X是k维项目集，如果频繁项目集Lk-1中包含的X的子集个数小于k,则X不可能是频繁项目集。
利用它的性质对Apriori算法从以下三方面进行了改进。
(1)在剪枝阶段减少扫描Lk-1的次数
进行剪枝的工作原理是：根据关联规则的性质，Ck中的一个项集如果是频繁项集，那么它一定有K个k-1项频繁子集，且这K个k-1项频繁子集一定都在Lk-1当中。因此以往的对Ck的剪枝过程都是先取出一个候选k项集，然后产生它的K个k-1项子集，再扫描一次Lk-1查看这K个k-1项子集是否都在Lk-1中，如果不是则剪掉这个候选k项集，如此循环。如果产生m条候选k项集，就需扫描Lk-1项集m次。然而频繁项集具有性质3[4]。所以不需要扫描Lk-1次。首先进行Lk-1×Lk-1的连接运算生成所有的候选项集Ck,然后取出Lk-1中的第一个频繁k-1项集，查看该k-1项集是Ck中哪些k项集的子集，如果是子集，则对相应的k项集进行计数。然后再从Lk-1中取出第二个频繁k-1项集，再到Ck中去查看它是哪些k项集的子集，直到Lk-1中的各个项集都比对完成。最后，查看Ck中的每个k项集，如果它的计数小于k，则它不可能是频繁k项集，需要删除。因为频繁k项集一定有k个k-1项子集存放在Lk-1中。这样整个剪枝步骤只需要扫描Lk-1一次，提高了剪枝步骤的效率和开销。
(3)对用于连接的频繁项目集进行精简，减少无用候选的产生。
对于产生的频繁项目集Lk-1,Apriori算法直接用它连接产生候选频繁项目集Ck。但实际上Lk-1中的有些项目集已经对产生Lk不起作用了，包含这些项目集的候选k-项集一定不是频繁的，因此可以对频繁项目集Lk-1进行精简。
根据频繁项集的性质[7],当要用Lk-1连接产生Ck时，首先统计Lk-1中各个项目出现的次数，如果该项目出现的次数小于k-1，则该项目所在的项目集不用来链接生成Ck[8]。
实验结果表明，改进的Apriori-Evo算法确实在关联规则数据挖掘的速度和效率方面有很大的提高，而且随着事务数据的增多，提升效果更加明显。
新的算法从三个方面对原有的算法进行了改进，减少了产生的候选频繁项集Ck中项集的数据，也减少了剪枝过程中的运算次数，在统计支持度阶段减少了需要扫描的数据库中的事务数。而且计算机进行向量运算和位运算速度更快，程序也会更容易实现。实验证明，新算法在系统的开销和时间效率上都有很大的提高。
参考文献
[1] HAN J,KAMBER M.数据挖掘:概念与技术[M]. 范明，孟小峰,译.北京:机械工业出版社，2001.
[2] AGRAWAL R, IMIEL NSKI T , SWAM I A. Mining association rules between sets of items in large database[A]. In Proc. of the ACM SIGMOD Intl Conf. on Management of Data[C]. Washington D. C. , 1993:207-216.
[3] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules[C].Morgan Kaufmann, San Francisco, CA: Proceedings of the 24th International Conference on Very Large Databases,1998:478-499.
[4] 李绪成，王保保. 挖掘关联规则中Apriori 算法的一种改进[J]. 计算机工程，2002，7(28)：104-105.
[5] 罗芳，李志亮.一种基于压缩矩阵的Apriori改进算法[J]. 科技资讯，2010(4):19.
[6] 刘以安，羊斌.关联规则挖掘中对Apriori算法的一种改进研究[J].计算机应用，2007，27（2）:418-420.
[7] 盛立，刘希玉，高明.挖掘关联规则中AprioriTid算法的改进[J].山东师范大学学报（自然科学版），2005，20（4）: 20-22.
[8] 叶福兰，施忠兴.Apriori算法的改进及应用[J].现代计算机，2009(9):95-126.