龙源期刊网 http://www.qikan.com.cn
关联规则挖掘算法分析与探讨
作者：刘晓玲 郭龙
来源：《软件导刊》2013年第07期
摘要：关联规则挖掘算法是数据挖掘领域的主要研究方向之一。对几种经典的关联规则挖掘算法进行了分析、探讨和比较，给出了一种基于支持矩阵的、不需要产生候选项目集的算法设计思想。算法为事务数据库中的每个项目设置二进制向量，利用逻辑与运算构造支持矩阵来挖掘频繁项目集，极大地节省了存储空间，提高了算法运行效率。 关键词：关联规则；候选项目集；频繁项目集；支持度
中图分类号：TP312 文献标识码：A 文章编号：16727800（2013）007006603 0 引言
关联规则挖掘在商业等领域中的成功应用，使其成为数据挖掘中最活跃、最主要、最成熟的研究课题之一。通过对关联规则的挖掘，可以得到隐藏在海量数据集中的有趣的、有价值的信息。自从Agrawal等人[1]提出关联规则挖掘的概念和经典的关联规则挖掘算法-Apriori算法以来，众多国内外研究者对关联规则挖掘算法进行了广泛深入的研究，提出了许多在运行效率及伸缩性等方面均有进一步提高的改进算法。本文首先给出了关联规则的基本概念，然后对几种经典的关联规则挖掘算法进行了分析比较，最后提出了一种改进的关联规则挖掘算法的设计思想。 1 基本概念
关联规则挖掘的目标是从事务数据库D中挖掘出所有满足用户事先给定的最小支持度阈值和最小可信度阈值的关联规则，也可以说是挖掘出所有的强关联规则。关联规则挖掘的过程最终都可以归纳为两步：
（1）找出事务数据库D中的所有频繁项目集，根据定义1.4，找出的这些项目集出现的频率至少和用户给定的最小支持度阈值一样。
（2）根据频繁项目集和最小可信度阈值产生所有有用的强关联规则。
如何提高频繁项目集的挖掘效率是关联规则挖掘的核心任务。因此，目前几乎所有的关联规则挖掘算法都是针对第一步提出的。 2 经典的关联规则挖掘算法 2.1 Apriori算法
龙源期刊网 http://www.qikan.com.cn
Apriori算法能比较有效地产生关联规则，挖掘和识别所有的频繁项目集是该算法的核心。但Apriori算法存在两个致命的性能瓶颈：一是算法扫描事务数据库次数过多，产生每个侯选k项集C＼-k都需要扫描事务数据库一次；二是当事务数据库或候选项目集规模太大时将会产生庞大的候选项目集，由L＼-＼{k1＼}产生侯选项目集C＼-k的数量是指数增长的，这对于时间和主存空间来说都是一种挑战。另外，由于事务数据库太大或支持度、可信度阈值设置太低，算法会产生太多的冗余规则。所以，Apriori算法不能直接用于关系数据库的关联规则挖掘，也不适用于海量数据环境下的关联规则挖掘。 2.2 基于Apriori的改进算法
为了克服Apriori算法存在的缺陷，研究者提出了许多基于Apriori算法的改进算法，以期能够找出更高效、更可靠的频繁项目集挖掘算法。下面讨论了一些有代表性的变形算法。 （1）基于散列技术的算法。Park等人提出的DHP算法采用了基于散列的技术对候选项目集进行修剪达到提高关联规则挖掘效率的目的。该算法利用散列函数将候选项目集映射到散列表结构的不同桶中，并设置对应的桶计数。在散列表中对应的桶计数小于最小支持度阈值的候选项目集都不可能是频繁项目集，所以应当从候选项目集中删除。这种基于散列的技术极大地压缩了要考察的候选项目集，尤其是对候选2项集数量的控制特别突出。DHP算法的关键是构造一个有效的散列函数。散列函数直接影响着候选项目集在散列表中的计数效率，也就是说，散列表的大小直接影响算法的运行效率。
DHP算法仍然存在许多缺点，例如，在散列表中存放项目集计数值的桶计数与存放候选项目集的桶内容之间存在内存争用的问题；不同的候选项目集映射到散列表中，映射的桶地址相同时如何处理的问题。此外，DHP算法属于宽度优先算法，所以仍然存在需要生成大量候选项目集，需要多次扫描事务数据库的问题。
（2）基于划分技术的算法。A.Savasere等人提出的Partition算法和S.Brin等人提出的DIC算法都属于基于划分技术的算法。这类算法为了节省访问外存时的I/O开销，从逻辑上将事务数据库D中的事务划分为n个非重叠的部分，然后将其分别存放在内存中进行处理。 Partition算法只需要扫描数据库两次，第一遍扫描事务数据库时，将所有事务划分为n个数据块，分别找出局部于每个数据块的频繁项目集（称为局部频繁项目集），再利用这些局部频繁项目集合并形成全局候选项目集；然后再次扫描数据库，计算全局候选项目集的支持度，找出其中的全局频繁项目集。
DIC算法也是将事务数据库划分为若干个数据块，在遍历每个数据块的过程中计算每个项目集出现的次数，同时找出所有可能的频繁项目集，形成候选项目集。所有数据块遍历结束后，再重复执行算法，直到确定出所有项目集的出现次数。DIC算法扫描数据库的次数比Apriori算法要少，如果数据块的划分正好合适时，DIC算法仅需扫描数据库两次就能够找出所有的频繁项目集。
龙源期刊网 http://www.qikan.com.cn
基于划分技术的算法其主要瓶颈是算法执行的时间，生成的候选项目集有可能会非常庞大，同时找出的频繁项目集的精度也不是很高，但是这类算法具有高度的并行性，减少了扫描数据库的次数，大大减少了I/O操作，从而达到提高算法效率的目的。
（3）基于选样的算法。Toivonen提出的Sampling算法利用样本减少了对事务数据库的扫描次数。该算法主要思想是：从事务数据库D中随机选取样本集形成一个能够调入内存的数据库子集S，然后用一个小于用户给定的最小支持度阈值在S中搜索找出所有可能成立的规则生成频繁项目集，并用数据库的剩余部分验证这个结果，最后得到实际的频繁项目集。由于Sampling算法只需要在内存中对S进行一次扫描搜索频繁项目集而不是在D中，使得它在很大程度上降低了数据库扫描的时间开销，但同时也存在丢失一些全局频繁项目集的可能，所以它适用于对挖掘效率要求较高而对挖掘精度要求不太高的环境。 2.3 FPgrowth算法
Han等人提出的FPGrowth算法是一种从本质上不同于Apriori算法的经典算法。该算法只需扫描数据库两次，是一种不产生候选项目集而直接生成频繁项目集的频繁模式增长算法，能有效地产生关联规则。算法采用了“分而治之”的策略，第一遍扫描事务数据库将找到的频繁1项集压缩到一棵频繁模式树（FPtree）中，同时仍然保留其中的关联信息；然后再将FPtree分化成一些条件模式库分别进行挖掘得到所有的频繁项目集。
与基于Apriori的算法相比，FPgrowth算法只需扫描数据库两次且不需要产生庞大的候选项目集，大大缩小了挖掘的搜索空间，减少了数据模式匹配的开销，提高了时空效率。但FPgrowth算法在FPtree中搜索频繁项目集的过程中，不能根据层次数据的特点去除无用的关联规则，从而产生大量冗余的关联规则，另外该算法对于处理庞大且稀疏的数据库的扩展性也不佳。
3 一种改进的关联规则挖掘算法
基于频繁项目集支持矩阵的思想，本文提出了一种利用矩阵挖掘频繁项目集的算法，只需要进行一次数据库扫描并且不需要产生候选项目集就可以生成最终的频繁项目集。算法的实施过程可以划分为三步完成：首先生成频繁1项集并记录相关信息；然后构造出频繁2项集支持矩阵；最后生成频繁k项集。 3.1 生成频繁1项集
在算法第一步中，首先为每个项目设置一个二进制向量，设项目i对应的二进制向量为SM＼-i，向量长度为数据库中包含的事务总数。对事务数据库进行扫描，如果项目i在第j个事务中出现，则SM＼-i的第j位置1，否则置0。由此可知，SM＼-i中“1”的总和就是包含项目i的事务数，即项目i的支持度，根据用户给定的最小支持度阈值即可得到频繁1项集。 4 结语