关联规则挖掘Apriori算法的改进

摘 要：在介绍Apriori算法原理和实现过程的基础上，针对该算法存在的两个缺陷，即多次扫描事务数据库和产生大量的候选集，提出新的算法NewApriori，该算法改变由低维频繁项目集到高维频繁项目集的多次连接运算，直接从1频繁项目集产生高维频繁项目集，克服了Apriori算法的固有缺点，从而提高了运算效率。

关键词：关联规则挖掘；apriori算法；频繁项目集；侯选数据集

中图分类号：TP311 文献标识码：B 文章编号：1004373X(2008)1807803

Improvement of Apriori Algorithm in Association Rule Mining

ZHU Ye,YE Gaoying

(Chengdu University of Information Technology,Chengdu,610225,China)

Abstract：In this paper,the principle and performance of Apriori algorithm is introduced,and two defects of Apriori algorithm:scanning database too much and creating excessive candidate itemsets are analyzed.A new Apriori algorithm has been designed for finding out the highest dimension frequent itemsets from frequent 1itemset directly.A great number of linking operations in finding frequent itemsets dimension by dimension are canceled over all.The algorithm is improved efficiently.

Keywords：association rule mining;Apriori algorithm;frequent itemset;candidate itemset

1 引 言

数据挖据［1］(Data Mining)是一个多学科交叉研究领域，是从大量数据中提取或“挖掘”出未知的、潜在的、有用的知识。从现状来看，数据挖掘的研究仍然处于广泛研究探索阶段，主要包括特征化与比较、关联规则挖掘、分类预测和聚类分析等方法。其中关联规则挖掘(Association Rule Mining)是数据挖掘中最活跃的研究方法之一。

最早由Agrawal等人［2］(1993年)针对购物篮分析(Basket Analysis)问题提出的，其目的是为了发现交易数据库(Transaction Database)中不同商品之间的联系规则。通过关联规则发现算法寻找形如“如果，那么”的规则，这种规则以其简洁性已经多次成功应用到决策支持系统，指导人们在各个领域中的活动。在关联规则挖掘算法的研究中，Agrawal提出的Apriori算法最为经典，但该算法本身固有的缺陷［3］是多次扫描数据库，并产生庞大的候选数据集。

本文从这两个缺陷入手，减少扫描数据库的次数，并省去大量候选集的产生过程，从而提高算法效率。

2 关联规则基本概念

一个事务数据库中的关联规则挖掘可以描述如下［3］：设I={i1,i2,…,im}是一个项目集合，事务数据库D={t1,t2,…,tn}是由一系列具有惟一标识TID的事务组成，每个事务ti(i=1,2,…,n)都对应于I上的子集。

定义1 支持度(Support):

指包含项目集(Itemset)I1(I1∈I)的事务在D中所占的百分比。

定义2 信任度(Confidence):

在形如I1I2的关联规则中(I1∈I，I2∈I)，信任度指包含I1和I2的事务数与包含I1的事务数之比，即在I1发生的情况下，I2也发生的可能性。

定义3 频繁项目集(Frequent Itemset)和最大频繁项目集:

对项目集和事务数据库D，T中所有满足用户指定的最小支持度的项目集称为频繁项目集。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集。

定义4 强关联规则(Strong Association Rule)：

指D在I上满足最小支持度和用户指定的最小信任度的关联规则。

关联规则挖掘问题就是通过最小支持度和最小信任度在一个事务数据库中寻找强关联规则的过程，划分为2个子问题：

(1) 发现最大频繁项目集；

(2) 在最大频繁项目集中生成强关联规则。第一个子问题是本文的研究重点，即提出一种新的算法来发现最大频繁项目集。

3 Apriori算法及缺点分析

1994年Agrawal等人建立用于事务数据库挖掘的项目集的格空间理论［4］：频繁项目集的子集是频繁项目集，非频繁项目集的超集是非频繁项目集。Apriori算法［3］依据此理论进行剪枝。该算法是通过项目集数目不断增长来逐步发现频繁项目集的，算法输入数据集D和最小支持数minsupcount(最小支持度与事务数的乘积)，输出频繁项目集L。算法首先产生1频繁项目L1，然后是2频繁项目集L2，直至不再能扩展频繁项目集的元素数目而算法停止。在第k次循环中，过程先产生k候选项目集的集合Ck，然后通过扫描数据库得到CK的支持度并测试产生k频繁项目集Lk。算法过程［5］是：连接剪枝生成Ck扫描计数比较生成Lk。

从以上分析可以发现，Apriori算法使用逐层搜索的迭代方法，通过低维频繁项目集产生高维频繁项目集［4］。这样，就致使Apriori算法存在2个致命的性能瓶颈：

(1) 多次扫描事务数据库。每次k循环，候选集Ck中的每个元素都必须通过扫描数据库1次来判断其是否加入Lk。如果频繁大项目集包含n项，则至少需要扫描事务数据库n遍，需要很大的I/O负载。

(2) 可能产生庞大的候选集。由Lk-1产生k候选集Ck是呈指数增长的，例如104个1频繁项目集有可能产生接近107个元素的2候选集，如此庞大的候选集对时间和存储空间是一个挑战。

4 改进Apriori算法

Apriori算法使用候选集去找频繁集，算法反复连接、剪枝，导致执行效率低。因此，考虑使用其他方法来取代通过候选集去找频繁集的过程，改变由低维频繁项目集到高维频繁项目集的多次连接运算，这样，既可以避免大量候选集的产生，又可以减少数据库的扫描次数，从而提高算法效率。在介绍具体改进措施之前，引入2条推论：

推论1 如果K频繁项目集Lk中的项目集个数≤K时，则该集合为最大频繁项目集的集合。

证明： 根据项目集格空间理论，假如存在K+1频繁项目集Lk+1，那么对于Lk+1的K+1个K项目子集都是频繁项目集，与题设项目集个数≤K矛盾，所以，如果频繁项目Lk中项目集的个数≤K时，则无法产生K+1频繁项目集Lk+1，因此，该推论成立。

推论2 最大频繁项目集Lk的项目数K小于等于在所有事务中满足支持计数的最大项目数k。对于事务T，若2项集的支持计数为sup2，3项集的支持计数为sup3，…，n-项集的支持计数为supn(n为所有事务中的最大项目数)，其中，supk( Minsupport(2(k(n)且supk+1

证明： (反证法)假设K大于k，则存在频繁项目集Lk满足支持计数，而与满足支持计数的项目数k最大矛盾，因此，最大频繁项目数K不可能大于满足支持计数的最大项目数k，推论得证。

一般地，只关心那些不被其他频繁项目集所包含的最大项目集的集合，在这些频繁项目集中发现关联规则。所以，问题归结为如何高效确定最大频繁项目集。改变通常的做法，应用上述推论，先确定最大频繁项目集的项目数K，然后找出所有频繁项集Lk。算法NewApriori描述如下：

输入：事务数据T；最小支持数minsupcount。

输出：最大频繁项目集L。

(1) C［n］=0; //初始化数组C［n］，n为所有事务中的最大项目数

(2)for each ti∈Tdo begin

(3) i=|ti|;//i为每个事务所含的项目数

(4) C［i］=C［i］+1

(5)end

(6) L1={large 1-itemsets};//所有满足支持计数的1频繁项目集

(7)for i=nto 2do begin

(8)if(C［i］(minsupcount) then begin

(9) k=i;

//根据推论2，k≤i，由于找最大的频繁项集，因此可以假定k=i

(10) Ck={large k-itemsets};//直接从L1中生成Ck

(11) Lk={Ck|Ck.count(minsupcount and Ck.count(k};//根据推论1

(12)if Lk≠hthen

(13)return Lk

(14)end

(15)end

该算法的改进主要体现在以下2方面：

(1) 最大频繁集的产生过程改变为从高维到低维的搜索过程，根据不同项目个数的出现频率，直接从1频繁项目集产生高维频繁项目集，省去多次的连接运算及大量候选集的产生，节约了运行时间和主存空间。

(2) 减少扫描数据库次数，该算法扫描数据库的次数最少可以减少到3次(第1次，计算C\；第2次，得到1频繁项目集；第3次，计算大于支持计数的Lk)，而Apriori算法则需要扫描k次，因此，对于维数较高(k值较大)的频繁项目集的计算，效率提高更明显。

5 实例分析

下面给出一个服装店的20个收款机事务记录，每一事务T代表购买的商品集合，I1-I6分别表示不同的商品，最小支持数minsupcount=3,见表1所示。

根据NewAgriori算法

(1) 计算C［n］，C［1］=4，C［2］=6，C［3］=5，C［4］=4，C［5］=1；

(2) 得到1频繁项目集L1={{I2}，{I3}，{I4}，{I5}，{I6}}；

(3) 由于C［5］minsupcount，则先假定最大频繁项目集的项目数k=4，从L1中产生所有4项目集，共5个，分别是：{I2，I3，I4，I5}，{I2，I3，I4，I6}，{I3，I4，I5，I6}，{I2，I4，I5，I6}，{I2，I3，I5，I6}，扫描数据库计算该5个候选集的支持计数，求得满足最小支持计数的项集为：{I2，I4，I5，I6}，其支持计数=4，根据推论1可知，该频繁项目集即是最大频繁项目集，计算结束。如果使用Apriori算法，则需要扫描4次数据库，并且从1频繁项目集到4频繁项目集的连接计算共需产生24个候选集。而使用NewApriori算法，整个过程共扫描了3次数据库，且只产生5个4项候选集，很明显，无需产生大量的候选集同样可以找到最大频繁项目集，同时减少了扫描数据库的次数。但从上述算法流程不难看出，如果第一次假定的k不是所要求的最大频繁项目集的项目数时，则需要再次寻找符合要求的k值，多一次寻找，就多一次对数据库的扫描，候选集的数量也会随之增多。不过，数据库的扫描次数不会超过k次，为了避免过多冗余的候选集，可以将1频繁项目集按支持计数的大小顺序排列，组合支持计数相对少的项目，及早发现非频繁项目，以减少候选集的产生。因此，该算法特别适合于项目数比较大的最大频繁项目的查找。

6 结 语

Apriori算法作为最经典的关联规则挖掘算法被广泛使用，由于其固有的局限性，出现了大量的改进算法。本文提出的NewApriori算法也针对引起性能瓶颈的缺点而做出的改进，提高了系统运行效率。但不足的是，此算法只能找到项数最大的频繁项目集，也就是说，得到的频繁项目集不够完整，因此，还需要进一步完善。

参 考 文 献

［1］Jiawei Han,Micheline Kamber.数据挖掘概念与技术\.范明,孟小峰，译.北京:机械工业出版社,2001.

［2］Agrawal R,Imielinske T,Swami A.Mining Association Rules between Sets of Items in Large Databases.Proc.of the ACM SIGMOD International Conference on the Management of Data,Washington D.C.,1993:207216.

［3］毛国君,段立娟.数据挖掘原理与算法\.北京:清华大学出版社,2005.

［4］Agrawal R,Srikant R.Fast Algorithms for Mining Association Rules.Proc.1994 Int.Conf.Very Large Database.Santiago,Chile,1994:487499.

［5］李小兵.关联规则挖掘算法的改进与优化研究\.厦门大学学报:自然科学版,2005(7):468471.

［6］谢宗毅.关联规则挖掘Apriori算法的研究与改进\.杭州电子科技大学学报,2006(6):7882.

作者简介 朱 烨 女，1975年出生，陕西榆林人，博士研究生。主要研究方向为数据库与数据挖掘。

叶高英 男，1949年出生，陕西榆林人，研究员，博士生导师。主要研究方向为计算机应用、计算数学。