Apriori算法改进研究及实现

Apriori算法改进研究及实现摘要:通过对Apriori算法基本原理和性能的研究分析，针对算法存在的不足，提出了一种更高效的基于对频繁项集分组并行的挖掘算法。该算法把频繁k-1项集按照一定规律分组，每组频繁k-1子项集直接产生频繁 k子项集；再把每组产生的频繁k子项集合起来，这样每组不仅在自连接时减少了很多判断连接尝试，而且可以并行处理连接、剪枝行为，减少了等待时间，提高了查找频繁项集的速度。经过实验证实，改进后的算法在性能上有很大的提升。关键词:数据挖掘；关联规则；Apriori算法；分组；并行数据挖掘是指从数据库的大量数据中提取出先前未知的、具有潜在实际价值的、隐含的信息[1]。关联规则挖掘就是从海量的数据中寻找数据项间的关联关系。关联规则挖掘是由Agrawal等人于1993年首先提出[2]，之后又提出了著名的基于频繁项集的Apriori算法[3-4]。关联分析用来发现购物篮数据事务中各项之间的有趣现象，目前主要被应用于如科学数据分析、生物信息学、医疗诊断和网页分析等许多领域 [5]。因此，关联规则挖掘被广泛地研究。为了提高挖掘的效率，近几年国内外学者不断地对基于Apriori算法进行改进和创新，提出了很多优化的改进算法[6-8]。关联规则概念令I={i1,i2,…,id}是所有项的集合，而 T={t1,t2,…,tN}是所有事务的集合。每一个事务ti包含的项集都是I的子集。在关联规则的分析中，包含多个项的集合被称之为项集。例如一个项集包含了k个项，则此项集被称为k-项集[9]。空集是不包含任何项的项集。关联规则表达式XY,其中X和Y是不相交的项集，即XAY=?准。支持度(support)是T中同时包含X和Y的事务占的百分比。置信度 (confidenee)是T中同时包含X和Y的事务占包含X的事务的百分比。项集的出现频率是包含项集的事务数，称为项集的支持度计数。支持度确定规则可以用于给定数据集的频繁程度。如果项集I的支持度计数大于等于最小支持度阈值，可以确定项集I是频繁项集。支持度(s)度量形式为：S(XtY)=N(1)Apriori 算法分析Apriori算法是一种非常具有影响力的关联规则频繁项集的算法。它开创性地通过对最小支持度阈值的设置，系统地控制了候选项数量几何的增长。该算法采用了宽度优先且逐层搜索的迭代方法，即当第 k次迭代时，频繁k-项集通过频繁(k-1)-项集Lk-1来关联查找。第一次运行迭代时,扫描事务数据库所有项目，找出事务数据库中的所有项集构成的候选1-项集C1,然后根据设定的最小支持度阈值，在 C1中筛候选项，并且扫描所有事务数据库集合，度的阈值进一步筛选出符合条件的频繁频繁项集为止。该算法核心方法主要通过连接选出符合条件的项，构成频繁 1-项集L1;第二次运行迭代时，用频繁1-项集L1候选项，并且扫描所有事务数据库集合，度的阈值进一步筛选出符合条件的频繁频繁项集为止。该算法核心方法主要通过连接得到C2中每一个项的支持度值，然后通过最小支持2-项集L2。一直这样循环迭代下去，直到不能再产生(候选项集的产生)和剪枝两个步骤来完成。(1) 连接。由前一次迭代发现的频繁 (k-1)-项集Lk-1直接产生新的候选 k-项集Cko(2)剪枝。候选k-项集Ck是频繁k-项集Lk的超集，且Ck中的项集不确定是否都是频繁集。剪枝一般分为两步来进行。首先，根据 Apriori的性质，任何的非频繁(k-1)-项集都不是频繁k项集的子集。考虑 Ck,即X={i1,i2,…,ik}。该算法首先需确定它所有的真子集X-{i1}(?坌j=1,2，…,k)必须都是频繁的。如果其中一个真子集是非频繁的，则 X将会被每一个候选项的支持度计数，删除支持度计数小于支持度计数阈值的项集，从而得到立即剪枝。这种方法能非常有效地减少在支持度计数过程中所要考虑的候选项集的数量。继而可以得到已经被剪枝处理过的候选项集 Ck'。然后，扫描所有事务数据库集合， 计算Ck'每一个候选项的支持度计数，删除支持度计数小于支持度计数阈值的项集，从而得到Lko由于Apriori算法主要通过这两步来实现，为了能对该算法有更加清楚直观的认识，具体分析这个过程，Lk-1自连接来产生新的Ck'。令所有的项集中的项都按照一定的原则来排序。假设任意11€Lk-1、12€Lk-1、cl€Ck,cl'€Ck。当Lk-1进行自连接时，要判断两个频繁项是否能够连接， 如果I1[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。Apriori算法改进经过对上面的情况深入分析发现,该算法Lk-1大部分的自连接是无用的,且基本上绝大多数的判断连接是不成立的。假设 Lk-1项集大小为N,则需要判断连接的次数 LN为：LN=En(2)假定N=4,根据式(2),得出LN=3+2+仁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+En+…+En(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-项集Lko改进后的Apriori算法流程。其实根据事务数据库实际的需求,还可以在Lk-1分组后,把每组的频繁(k-1)-子项集,再将频繁(k-1)-子项集中每一个频繁项的前第二项相同的分为一组。通过组内再分组的方式,更加细化了频繁项集,使得判断连接次数进一步减少,连接速度加快,继而提高效率。也可以直接把频繁(k-1)-项集中每一个频繁项lk-1中的前第一项和前第二项相同的分为一组,这样也能很好地达到分组的效果。实验验证及性能分析通过对两种算法的分析,显然在理论上改进后的算法在很多方面效率会更高。下面将通过具体实验来验证算法在改进前后的性能比较。本文使用Java语言分别来实现改进前后的两种算法。在相同的实验环境下实现两种

算法的比较,实验所用的具体环境配置为：处理器Intel(R)Core(TM)2DuoCPUP8600,主频2.40GHz、内存4GB（实际可用2.96GB），操作系统Windows7旗舰版，系统类型32位。利用系统上安装的Eclipse开发软件来进行实验数据测试。本文将提供8000条事务数据库,得到在不同最小支持度阈值下两种算法的运行时间。实验结果如表 1和图2所示。由图2可知，在实验环境和事务数据库所有项目不变的前提下，得出了在不同阈值支持度下，两种算法运行时间的值。显然，两种算法在最小支持度阈值变小时，所需要的运行时间都会成几何的增长。通过相互对比，改进后的P-Apriori算法比经典Apriori算法运行时间的增加更缓慢、不迅速。在最小支持度的阈值相同的情况下，改进后的 P-Apriori算法运行时间更少，更加高效。当最小支持度的阈值较小时，特别在阈值为0.15时，改进后的P-Apriori算法效率的提升更加明显。当最小支持度的阈值较大时，由于两种算法运行的时间都比较少，所以在图中难以辨别出来。但根据表1可知，通过实际运行数据比较，还是可以发现改进后的P-Apriori算法运行时间比经典Apriori算法的运行时间要少，只是在图2中不明显。本文通过对经典Apriori算法理论研究和具体分