关联规则中Apriori算法的创新研究

关联规则中Apriori算法的创新研究

摘要：在关联规则理论的基础上，通过对现有算法的效率分析，在原有Apriori关联规则挖掘算法的基础上，从减少事务数据库中扫描记录量入手，提出一个改进的快速关联规则挖掘算法Fast_Apriori。利用候选项集和频繁项集中的结果对数据库中的记录进行筛选，对不包含候选项集中任何项集的记录和不包含在候选项集中的事物记录直接删除，减少扫描的记录数，提高整个算法的效率。

关键词：关联规则 Apriori算法 候选项集 频繁项集 中图分类号：TP311.13 文献标识码：A 文章编号：1007-9416（2014）04-0133-02

在关联规则的各种挖掘算法研究中，主要集中在产生频繁项集的这一挖掘步骤。在众多算法中，Apriori算法最为著名，它是Agrawal等人在1994年提出的，该算法首次将关联规则挖掘理论运用在现实应用系统中。Apriori算法使用了一种逐层迭代的宽度优先搜索策略，由满足一定频度的项集来构造可能是下一个满足频度的项集的候选项集，根据设定的最小支持度计数筛选出频繁项集。

Apriori算法基本思想就是发现频繁项集，然后找出频繁项集中的关联性更强的规则。找到频繁项集的方法是先找出

所有可能是频繁项集的候选项集。最简单的方法是穷举法，把所有的项集都作为候选项集，然后对它在事务数据库中出现的次数计数，计数满足设定的支持度的阈值时，则为频繁项集。但是穷举法开销较大，通过观察，发现了如下性质。 Apriori性质：一个频繁项集的任一子集也一定是频繁项集[1]。

根据Apriori性质，如果一个项集是非频繁的，则它的超集也是非频繁的，将不作为候选项集。Apriori算法采用逐层迭代的搜索方法，由频繁k-项集来构造可能是频繁的（k+1）-项集的候选项集。在算法实现过程中还需要进一步明确两个问题：第一个是如何计算每个项集的频率，并验证其是否频繁；第二个是如何由Lk产生Ck+1。第一个问题实现方式比较简单。对于给定的候选项集Ck，可以通过对数据库的一次扫描来计算出其中每个候选项集的频率。通常在内存中为每一个候选项集设一个计数器，扫描结束时计算器的值记为候选项集的频度。第二个问题采用先连接后验证的方法解决。主要包含两个步骤：自连接和消减。自连接将大小为k的频繁项集联合成大小为k+1的项集，而消减则是进一步验证联合所生成的项集是否为潜在候选项集。

Apriori算法使用支持度减少了候选项集的数量，使得算法的时间和空间复杂度较小，并可以依据Apriori性质，直接删除不相关的项集，这是其好的方面。但是该算法仍需要大

量的重复扫描事务数据库，对大量的候选项集进行支持度计数，当数据库数据量大部分存储在外部存储器上时，大规模数据的I/O处理操作使得算法的效率受到很大的影响。 Apriori算法的主要缺点在于，每迭代一次就要读一次数据库，对于一个有n个项的数据集来说，最不好的情况需要读取n次数据库。为了提高算法的效率，在Apriori算法基础上，人们相继提出了一些改进方法，从不同角度对Apriori算法进行了优化设计。

Apriori算法通过在内存中为每一个候选项集设置一个计数器来计算它的频度。当候选项集很多时将占据大量内存，导致内存有可能不够用，因此，需要尽可能减少候选项集的数量。Apriori算法在构造Ck+1时利用Lk进行消减，这样已经减少了一部分候选项集的数量。但是，该方法对C2所起的作用不是很大，因为大多数1-项集都是频繁的。PCY算法通过一种基于哈希的技术来减少候选项集的大小，尤其是C2的大小[2]。

PCY算法的整体流程和Apriori算法一样。但是，在计算每个1-项集频度生成L1的时候，PCY算法顺便生成了一个哈希表。哈希表有若干桶组成，每个桶存放一组项集和一个计数器，用来记录通过哈希函数映射到该桶的项集及其频度，函数值相同的项集存放在同一个桶中。之后，在生成C2的时候，PCY算法利用该哈希表的信息对C2做进一步的消

减[3]。

具体来说，第一趟扫描数据库的时候，PCY算法完成了如下事情：

（1）计算所有1-项集的频度。

（2）对每一个交易，将其中的数据项进行两两组合，然后使用哈希算法将每个组合都放到一个桶中，桶计数加1。 （3）扫描结束时，将频度大于最小频度的1-项集放入L1中。

第二趟扫描数据库的时候，PCY算法完成如下事情：由L1生成C2。每一个候选2-项集必须满足两个条件：第一，i在L1中，j在L1中；第二，2-项集（i，j）必须哈希到一个计数值大于最小频度的桶中。

第二个条件正是PCY算法和Apriori算法的不同之处。PCY算法由于该条件的限制进一步减小了所生成的C2的大小。

Apriori算法执行时必须多次扫描数据库。如果大项集的最大长度是k，则需要最多扫描k+1遍数据库。如果数据库的数据量较大，对数据进行挖掘所需要的时间就会比较长。为此，人们提出了减少扫描数据库的几种方法，通过两次或一次扫描数据库来获得所有的频繁项目集。

（1）基于采样的方法[4]。该方法取主存大小的一个数据库的样本，在主存中运行一个Apriori算法，希望从这个样

本数据库能求出真正的频繁项集。应用该方法进行频繁项集挖掘时需要按比例伸缩最小支持度s。例如，如果样本数据库的大小是整个数据库的1%，那么使用s%作为新的最小支持度。对样本数据库进行挖掘后，还需要对整个数据库再进行一次完整的扫描，对由样本数据库求得的频繁项集进行验证。这种方法可能使得那些在全局数据库中频繁但在样本数据库中不频繁的项集被丢掉。为了减少这种丢失，可以将样本数据的最小支持度降低一点，这样在最后扫描全部数据库的时候可以找到更多的候选项集。但这样操作会产生较多的候选项集，占用过多的内存资源。 （2）基于划分的算法[5]。该算法主要分成两大步。首先将交易数据库D划分成n块无交集的子集，D1，D2，……，Dn，用Apriori算法求出Di中的所有频繁项集Li；然后，合并所有的Li，再次完整地扫描一遍数据库，对L中的每一项集进行验证。该算法执行过程中只扫描了两遍数据库，从而提高了算法的效率。

通过对Apriori算法的效率分析，在生成候选项集时，算法每次都需要对事务数据库进行完整扫描，无论数据库中的记录是否包含上一次产生的候选项集中的数据项。这样如果事务数据库中的数据量很大时，花费了很多读取无用数据记录的时间，使得算法的性能大大降低。因此，在原有Apriori关联规则挖掘算法的基础上，从减少事务数据库中扫描记录

量入手，提出一个改进的快速关联规则挖掘算法Fast_Apriori。该算法流程如图1所示。

算法Fast_Apriori在计算各个项集的频度的同时记录包含项集的相应事务记录的记录号，这样以后在计算候选项集中各个项集的频度时，直接删除不包含在候选项集中的各事务，这样就节省了扫描这些不相关数据记录的时间。在扫描数据库中，对不包含候选项集中的任何项集的事务记录也可以同步删除，因为这部分记录对后续计算候选项集的支持度没有任何影响，这样事务数据库中原始记录数目不断减少，为整个算法的运行节省了大部分的扫描数据库的时间，和原有Apriori算法相比，执行效率得到提高。

本文深入研究了关联规则的典型挖掘算法Apriori，在此基础上讨论了算法的性能优化问题，并提出了一种改进的挖掘算法Fast_Apriori。改进后的算法虽然加快了找出规则的速度，但仍需要对数据库进行大量的扫描，在未来的研究中，会不断地完善，使算法得到更好的优化。 参考文献

[1]李杰.关联规则算法在学生成绩分析中的应用[J].信息系统工程，2010，（5）：96-99.

[2]Kumar P，Ananthanarayana V S.Discovery of Weighted Association Rules Mining.Proceedings of the 2nd International Conference on Compunter and Automation Engineering

（ICCAE）， Singapore， 2010：718-722.

[3]姚家奕.数据仓库与数据挖掘技术原理及应用[M].电子工业出版社，2009：119-172.

[4]蒋盛益，李霞，郑琪.数据挖掘原理与实践[M].电子工业出版社，2011：150-172.

[5]王珊，李翠平，李盛恩等.数据仓库与数据分析教程[M].高等教育出版社，2012：110-132.

本文来源：https://www.bwwdw.com/article/6mkp.html