摘 要: 通过对Apriori算法基本原理和性能的研究分析，针对算法存在的不足，提出了一种更高效的基于对频繁项集分组并行的挖掘算法。该算法把频繁k-1项集按照一定规律分组，每组频繁k-1子项集直接产生频繁k子项集；再把每组产生的频繁k子项集合起来,这样每组不仅在自连接时减少了很多判断连接尝试，而且可以并行处理连接、剪枝行为，减少了等待时间，提高了查找频繁项集的速度。经过实验证实，改进后的算法在性能上有很大的提升。

关键词: 数据挖掘；关联规则；Apriori算法；分组； 并行

       数据挖掘是指从数据库的大量数据中提取出先前未知的、具有潜在实际价值的、隐含的信息[1]。关联规则挖掘就是从海量的数据中寻找数据项间的关联关系。 

       关联规则挖掘是由Agrawal等人于1993年首先提出[2]，之后又提出了著名的基于频繁项集的Apriori算法[3-4]。关联分析用来发现购物篮数据事务中各项之间的有趣现象，目前主要被应用于如科学数据分析、生物信息学、医疗诊断和网页分析等许多领域[5]。因此，关联规则挖掘被广泛地研究。为了提高挖掘的效率，近几年国内外学者不断地对基于Apriori算法进行改进和创新，提出了很多优化的改进算法[6-8]。

       1 关联规则概念

　     令I={i1,i2,…,id}是所有项的集合，而T={t1,t2,…,tN}是所有事务的集合。每一个事务ti包含的项集都是I的子集。在关联规则的分析中，包含多个项的集合被称之为项集。例如一个项集包含了k个项，则此项集被称为k-项集[9]。空集是不包含任何项的项集。

关联规则表达式X→Y,其中X和Y是不相交的项集，即X∩Y=?准。支持度(support)是T中同时包含X和Y的事务占的百分比。置信度(confidence)是T中同时包含X和Y的事务占包含X的事务的百分比。项集的出现频率是包含项集的事务数，称为项集的支持度计数。支持度确定规则可以用于给定数据集的频繁程度。如果项集I的支持度计数大于等于最小支持度阈值，可以确定项集I是频繁项集。支持度(s)度量形式为：

　    　S(X→Y)=N  (1)

       2 Apriori算法分析

　      Apriori算法是一种非常具有影响力的关联规则频繁项集的算法。它开创性地通过对最小支持度阈值的设置，系统地控制了候选项数量几何的增长。

　     该算法采用了宽度优先且逐层搜索的迭代方法，即当第k次迭代时，频繁k-项集通过频繁(k-1)-项集 Lk-1来关联查找。第一次运行迭代时,扫描事务数据库所有项目，找出事务数据库中的所有项集构成的候选1-项集C1，然后根据设定的最小支持度阈值，在C1中筛选出符合条件的项，构成频繁1-项集L1;第二次运行迭代时，用频繁1-项集L1自连接产生候选项，并且扫描所有事务数据库集合，得到C2中每一个项的支持度值，然后通过最小支持度的阈值进一步筛选出符合条件的频繁2-项集L2。一直这样循环迭代下去，直到不能再产生频繁项集为止。

　      该算法核心方法主要通过连接(候选项集的产生)和剪枝两个步骤来完成。

       (1)连接。由前一次迭代发现的频繁(k-1)-项集Lk-1直接产生新的候选k-项集Ck。

　     (2)剪枝。候选k-项集Ck是频繁k-项集Lk的超集，且Ck中的项集不确定是否都是频繁集。剪枝一般分为两步来进行。首先，根据Apriori的性质，任何的非频繁(k-1)-项集都不是频繁k项集的子集。考虑Ck，即X={i1,i2,…,ik}。该算法首先需确定它所有的真子集X-{i1}(?坌j=1,2,…,k)必须都是频繁的。如果其中一个真子集是非频繁的，则X将会被立即剪枝。这种方法能非常有效地减少在支持度计数过程中所要考虑的候选项集的数量。继而可以得到已经被剪枝处理过的候选项集Ck′。然后，扫描所有事务数据库集合，计算Ck′每一个候选项的支持度计数，删除支持度计数小于支持度计数阈值的项集，从而得到Lk。

　     由于Apriori算法主要通过这两步来实现，为了能对该算法有更加清楚直观的认识，具体分析这个过程，Lk-1自连接来产生新的Ck′。令所有的项集中的项都按照一定的原则来排序。假设任意l1∈Lk-1、l2∈Lk-1、c1∈Ck，c1′∈Ck。当Lk-1进行自连接时，要判断两个频繁项是否能够连接，如果l1[i]=l2[i](?坌i=1,2,…,k-2)，则可以连接产生项c1′。根据Apriori的性质，项c1′可以产生(k-1)个(k-1)-项子集，再判断所有的(k-1)-项子集是否都在Lk-1中。若有一个(k-1)-项子集不在Lk-1中，则项c1′为非频繁项，可以忽略此项；反之，项c1′可以被确定为候选项c1。重复进行以上所述的连接过程，直到筛选产生所有候选k-项集Ck′为止。然后再分析Ck′，依次对Ck′逐项扫描事务数据库所有项目进行支持度计算，进一步筛选出频繁k项集Lk。

       3 Apriori算法改进

　     经过对上面的情况深入分析发现，该算法Lk-1大部分的自连接是无用的，且基本上绝大多数的判断连接是不成立的。假设Lk-1项集大小为N，则需要判断连接的次数LN为：

        LN=∑n (2)

　      假定N=4，根据式(2)，得出LN=3+2+1=6(次)。然后再对Ck′逐项扫描事务数据库，计算支持度，这个过程需要排队扫描，花费大量的等待时间。考虑以上问题，本文对Lk-1产生Lk的过程提出一种基于对频繁项集分组并行的改进算法P-Apriori。改进算法是在经典Apriori算法基础上修改提出的，效率上有很大的提升。下面将具体介绍改进后算法的这部分改良方法。

      首先在Lk-1自连接前对Lk-1进行扫描，按照一定规律分组，把Lk-1每一个频繁项中的前第一项相同的分为一组。例如当l1[1]=l2[1]时，可以分为一组。Lk-1自连接时，要判断它们的前(k-2)个项是否相同。如果它们的前第一个项都不相同，那么这个连接肯定就不会成立。由此可以得出，分组后的每组频繁(k-1)-子项集都可以独自进行自连接，且分组后的最多自连接总次数为PLN：   PLN=∑n+∑n+…+∑n  (3)

其中i为频繁(k-1)-项集分组量，ni为每组的频繁(k-1)-子项集长度，n1+n2+…+ni=N。

　     显然分组后自连接总次数被压缩了，即PLN的值要比LN小得多。假定N=4， 分为两组，令两组的频繁(k-1)-子项集长度分别为n1=2、n2=2，则根据式(3)得出分组后的PLN=1+1=2(次)，比原来分组前LN=6(次)少了很多无用连接。当N处于一个较大值，且分组量增加，这种优势将更加明显。由于分组后每组频繁(k-1)-子项集可以并行处理，或者说同步处理，且互不干扰地进行连接、剪枝行为，不仅自连接效率可以进一步提高，同时，把原方法需要逐个根据Apriori性质和扫描事务数据库计算支持度的过程，变成了可以并行进行。如原来只能排成一个队，现在可以排成多个队。显然，分组后效率的提高是可观的。最后把每组频繁(k-1)-子项集直接产生的频繁k-子项集组合起来，即频繁k-项集Lk。改进后的Apriori算法流程如图1所示。

       其实根据事务数据库实际的需求，还可以在Lk-1分组后，把每组的频繁(k-1)-子项集，再将频繁(k-1)-子项集中每一个频繁项的前第二项相同的分为一组。通过组内再分组的方式，更加细化了频繁项集，使得判断连接次数进一步减少，连接速度加快，继而提高效率。也可以直接把频繁(k-1)-项集中每一个频繁项lk-1中的前第一项和前第二项相同的分为一组，这样也能很好地达到分组的效果。

       4 实验验证及性能分析

　     通过对两种算法的分析，显然在理论上改进后的算法在很多方面效率会更高。下面将通过具体实验来验证算法在改进前后的性能比较。

　     本文使用Java语言分别来实现改进前后的两种算法。在相同的实验环境下实现两种算法的比较，实验所用的具体环境配置为：处理器Intel(R)Core(TM)2 Duo CPU P8600,主频2.40 GHz、内存4 GB(实际可用2.96 GB)，操作系统Windows 7 旗舰版，系统类型32位。利用系统上安装的Eclipse开发软件来进行实验数据测试。本文将提供8 000条事务数据库,得到在不同最小支持度阈值下两种算法的运行时间。实验结果如表1和图2所示。

       由图2可知，在实验环境和事务数据库所有项目不变的前提下，得出了在不同阈值支持度下，两种算法运行时间的值。显然，两种算法在最小支持度阈值变小时，所需要的运行时间都会成几何的增长。通过相互对比，改进后的P-Apriori算法比经典Apriori算法运行时间的增加更缓慢、不迅速。在最小支持度的阈值相同的情况下，改进后的P-Apriori算法运行时间更少，更加高效。当最小支持度的阈值较小时，特别在阈值为0.15时，改进后的P-Apriori算法效率的提升更加明显。当最小支持度的阈值较大时，由于两种算法运行的时间都比较少，所以在图中难以辨别出来。但根据表1可知，通过实际运行数据比较，还是可以发现改进后的P-Apriori算法运行时间比经典Apriori算法的运行时间要少，只是在图2中不明显。

       本文通过对经典Apriori算法理论研究和具体分析，在该算法的理论基础上进行了一定修改和改进，提出了基于对频繁项集分组并行的挖掘算法P-Apriori。通过实验表明，改进优化后的P-Apriori算法不仅能并行处理数据，而且可以有效减少频繁项集自连接次数，大大提高了频繁项集生成的效率，其在数据挖掘效率上比经典Apriori算法更加高效实用。并且理论上，随着实验机器性能的提升或者采用分布式计算，改进优化后的P-Apriori算法挖掘效率提升将更加明显。

参考文献

[1] 朱明. 数据挖掘[M]. 合肥: 中国科学技术大学出版社,2007.

[2] AGRAWAL R, IMIELINSKI T, SWAMI A. Database min-ing: a performance perspective[J]. IEEE Transactions on Knowledge and Data Engineering,1993,5(6):914-925.

[3] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules[C].Santiago, Chile: Proceeding of the 20th International Conference on Very Large Databases, 1994:487-499.

[4] AGARWAL C C, YU P S. Mining large itemsets for asso-ciation rules[J].Data Engineering Bulletin,1998,21(1):22-31.

[5] 吴昊, 李军国. 基于关联规则理论的道路交通事故数据挖掘模型[J].电子技术应用, 2009,35(2):139-143.

[6] AGARWAL R C, SHAFER J C. Parallel mining of associ-ation rules[J]. IEEE Transactions on Knowledge and Data Engineering,1998,8(6):962-969.

[7] 徐章艳, 刘美玲. Apriori 算法的三种优化方法[J]. 计算机工程与应用,2004,40(36):190-192.

[8] 肖冬荣, 杨磊. 基于遗传算法的关联规则数据挖掘[J]. 通信技术,2010,43(01):205-207.

[9] TAN P N, STEINBACH M,KUMAR V. 数据挖掘导论(完整版)[M].范明,范宏建,译.北京:人民邮电出版社,