关联规则中Apriori算法的研究与改进

宋小小 陈晓辉 刘冲

桂林理工大学 广西 541004

0 引言

数据挖掘是一门新兴起的交叉学科，主要研究事务数据库、关系数据库中的数据项之间潜在有用的新颖的规律。它的主要方法包括：分类、关联规则、聚类、特征、回归分析、变化和偏差分析等。关联规则挖掘就是从海量的数据中寻找数据项间的关联关系，它是数据挖掘领域中研究的热点问题。关联规则表示数据库中一组对象之间具有某种关联关系的规则，其主要挖掘对象是事务数据库。这种数据库大量的应用在零售业，而条形码技术的发展使得数据的收集变得更加方便、更加完整。关联规则就是在这些交易项目中去寻找某种关联关系。1993年，Agrawal等人首先提出了挖掘顾客交易项目中项集间的关联规则问题，此后诸多的研究人员对关联规则挖掘问题进行了大量的研究与改进。

1 Apriori算法

1.1 算法简介

Apriori算法是1993年由Agrawal等人提出的一个经典的挖掘关联规则算法，它通过对事务数据库的多趟扫描来发现所有的频繁项目集。

该算法采用“逐层搜索”的迭代方法，利用向下封闭特性，由 k-频繁项目集生成(k+1)-频繁项目集。第一趟扫描数据库计算出 1-频繁项目集集合(记为：L1)；接着，反复行下面的两个步骤计算k-频繁项目集，直到生成k-频繁项目集的集合(记为：Lk)为空：

(1) 连接：(k-1)-频繁项目集集合进行自连接运算，生成候选k-项目集集合。

(2) 剪枝：上一步生成的候选k-项目集集合是k-频繁项目集集合的超集。通过扫描数据库计算候选k-项目集集合中每个候选项目集的支持度，并与给定的最小支持度进行比较，较大的就是k-频繁项目集。

1.2 算法分析

经典的Apriori挖掘算法在执行“连接，剪枝”步骤中，需要多次扫描数据库并生成大量的候选项目集。当数据库太大或者挖掘层次太深时, 算法耗时太多甚至无法完成。在剪枝步，由大量的候选项目集而造成的频繁模式匹配问题，这些都严重影响了Apriori 算法的效率。

1.3 算法的基本原理

性质1 K项数据项目集是频繁项目集的必要条件是它的所有k-1项子集均是频繁项目集。

性质2 K频繁项目集的所有K-1维非空子集均是频繁项目集。

定理1 若K维数据项目集X = { i1, i2，…，ik}中，存在一个j∈X，使得|Lk-1(j)| ＜ k-1，则X不是频繁项目集。

其中，|Lk-1(j)|表示(K-1)维频繁项目集的集合 Lk-1中包含j的个数。

证明 假设X是K维频繁项目集，根据性质1，X的k个(k-1)项目子集都在Lk-1中，其中每一个项目p∈L均出现k-1次，故∀p∈L，均有| Lk-1(p)|≥k-1，这与条件矛盾，故X不是频繁项目集。

推论1 如果k-1维频繁项集集合Lk-1中包含单个项目i的个数小于k-1，则i不可能包含在频繁k-项集中。

2 改进的Apriori算法

Apriori算法中对数据库的处理，目前普遍采用的是水平数据库结构。本文借鉴文献的思想，将水平结构变换为垂直对应关系。经过这样变换，很容易计算1-项目集的支持度，同时很容易计算候选项目集的支持度，并且只在计算1-项目集时需要对整个数据库进行访问。

改进的Apriori算法思路如下：

(1) 首先扫描整个数据库，记录支持每个项目的事务ID号。经过统计后，计算出每个项目的支持度，并与最小支持度进行比较，进而得出1-项目集。

(2) 由1-项目集中的项目进行两两连接，生成候选2-项目集。然后计算候选 2-项目集中每个项目集的事务计数(事务计数等于项目集中的每个项目事务的交集)，与最小支持事务数进行比较，进而得出2-项目集。

(3) 以此类推，生成候选k-项目集。根据定理1和推论1，删除候选k-项目集中不可能为k-项目集的项目，然后计算候选k-项目集中每个项目集的事务计数，与最小支持事务数进行比较，进而得出k-项目集。

(4) 重复步骤3，直到生成K频繁项目集的集合为空。

改进的Apriori算法描述如下：

3 实验与结果分析

与经典的Apriori挖掘算法相比, 改进后的挖掘算法有如下优点：

(1) 算法只在计算频繁1-项目集时需要对整个数据库进行访问，在计算候选k项目集的支持度时，仅需要数据库中频繁k-1项集信息。而随着k的增大，频繁项目集的数目不断减少。

(2) 算法采用垂直对应数据库结构，通过该数据库结构很容易计算候选项目集的支持度。

(3) 算法在生成一个候选项目集后就计算其频繁度，避免了模式匹配，减少内存的使用。

为了进一步验证算法的有效性，实验在内存为512MB，CUP主频为1.7GHZ，操作系统为Windows XP2的环境下进行，并用VC++ 6.0分别实现了经典Apriori算法和本改进算法。数据由笔者随机生成，有2800个数据，90个项集，最小支持度为15%，实验结果如表1所示。

表1 两种算法在不同项集个数下的运行时间

从表中可以看出，经过改进的Apriori算法在执行速度上有了较大的提高。

4 结语

本文通过深入分析经典Aprior算法的优缺点，在此基础上提出了改进的Apriori关联规则挖掘算法，并给出了详细的算法描述。经实验证明，改进的Apriori算法比经典的Apriori算法有着更好的频繁项集的提取速率。

[1]陈应霞,陈艳.关联规则中的 Apriori挖掘算法改进[J].长江大学学报(自然科学版).2008.

[2]徐章艳,刘美玲,张师超等.Apriori算法的三种优化方法[J].计算机工程与应用.2004.

[3]李云峰,陈建文,程代杰,关联规则挖掘的研究及对 Apriori算法的改进[J].计算机工程与科学.2002.

[4]曾万聪,周绪波,戴勃等.关联规则挖掘的矩阵其法[J].计算机工程.2006.

[5]Agrawl R, Shafer J.Parallel Minging of Association Rules:Design，Implementation，and Experience[P].USA: CA95120.1996.

[6]K1einberg J，Papadimitriou C，Raghavan P.Segmentation Problems [A] Proceedings of the 30th Annual Symposiumon the Theory of Computing [C].New York: ACM Press.1998.

[7]毛国君,段立娟,王实,石云.数据挖掘原理与方法.北京:清华大学出版社.2007.

[8]刘君强,孙晓莹,潘云鹤.关联规则挖掘技术研究的新进展[J].计算机科学.2004.

[9]王伟勤,郑海.Apriori算法的进一步改进[J].计算机与数字工程.2009.

[10]杨启昉,马广平.关联规则挖掘Apriori算法的改进.计算机应用[J].2008.

[11]马盈仓.挖掘关联规则中 Apriori算法的改进.计算机应用与软件[J].2004.

[12]Brin S，Motw ani R，Silverstein C.Beyond Market Baskets：Generlizin g Association Rules to Correlations [A].Proceedings of the ACM SIGMOD [C] New Yor k: ACM Press.1996.