基于关联规则的数据挖掘算法研究

石正喜 葛科奇 曹财耀

（宁波城市职业技术学院信息学院浙江宁波315100）

1 引言

数据挖掘，又称为数据库中的知识发现(Know ledge Discovery in Database,KDD),是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程，它是知识发现的关键步骤。关联规则挖掘是数据挖掘中应用最广的算法之一。关联规则挖掘，是指从一个大型的数据集中发现有趣的关联关系，即从数据集中识别出频繁出现的属性值集，也称为频繁项集，简称频繁集，然后利用所得的频繁集创建描述关联规则的过程。简言之，关联规则挖掘就是通过给定的数据库，根据最小支持度和最小置信度来寻找合适关联规则的过程。

美国学者R.Agrawal等人从顾客交易数据库中发现了用户购买模式的相关性问题，于是提出Apriori关联规则算法。目前，Apriori算法已广泛应用于数据分析、商业情报、高层决策等各个领域中。由于经典的Apriori算法需要多次扫描原始数据库，并生成大量的候选集，所以算法的挖掘性能一般，产生的冗余规则也较多。因此，在分析关联规则挖掘算法的基础上，提出一种改进的Apriori关联规则挖掘算法，并进行了相关的检验，结果表明该算法能较好地提取关联规则[1]。

2 Apriori算法

Apriori算法的显著特点是通过多次对数据库D进行扫描进而发现所有的频繁项目集[2]。设k为最长频繁项目集的长度，则Apriori算法对数据库D扫描次数为Sapriori=k。在第一趟扫描数据库时，Apriori算法首先计算出数据库D中所有的单个项目的支持度，并确定出满足最小支持度的1-强项集的集合L1。然后利用L1来挖掘L2，也就是2-强项集；连续不断的如此循环下去，在第n趟扫描中，首先以n-1趟扫描中所发现的含n-1个元素的强项集的集合Ln-1作为种子集，利用该种子集生成新的潜在的n-强项集的集合，即候选集Cn，计算这些候选集的支持度，最后从候选集Cn中确定出满足最小支持度的n强项集的集合Ln。不断重复以上过程，直至没有新的强项集产生为止。

经典的Apriori算法存在明显的不足[3,4]：①需要多次扫描数据库D，输入/输出系统消耗大量的计算机资源，如果最长频繁项目集的长度为k，那么就需要扫描数据库k遍；②产生的候选集是庞大的，由Lk-1产生k-候选集Ck是以指数增长的。总之，Apriori算法比较适用于处理小数据量的数据库，对于具有大量数据的数据库或数据仓库，执行效率会很低。

3 改进的Apriori算法

3.1 改进Apriori算法的思路

改进的Apriori算法为基于可拓理论的Apriori算法。可拓性即事物拓展的可能性，事物的可拓性是事物本身固有的性质，它包括发散性、相关性和蕴含性，它从事物向外、平行、变通和组合分解的角度提供了多条变换的可能途径。给定事物的名称N,它关于特征c的量值v,以有序三元组R=(N,c,v)作为描述事物的基本元,简称为物元。事物的名称N、特征c和量值v称为物元的三要素。如果物元三要素内部结构发生变化，那么物元也会产生变化。物元三要素是物元描述事物可变性的基本工具。物元把事物特征和量值放在一个统一体中考虑,使人们处理问题时，既要考虑事物的量,又要考虑事物的质。

在基于可拓理论的数据挖掘中,关联规则的定义为：对于一个征集X和一个概念描述Y,指定支持度阈值s0和置信度阈值c0,如果s(XyY)Es0并且c(XyY)Ec0,则规则XyY成立。其中,s(XyY)=card(XHY)/card(N),c(XyY)=card(XHY)/card(X)。运算符card(#)是求数据记录对象集中事物的个数,即求事务集中的事务数的个数。card(XHY)表示的同时支持征集X与概念Y的事物的个数,把它也称为支持度计数[5]。

对于一个征集X,如果s(XyY)Es0,则征集X为大征集。一个大征集中的某一征集Xk,如果置信度大于置信度阈值,便可以挖掘出一个可拓关联规则:XkyY,并将该征集Xk删除,以避免冗余规则的产生。一个征集为大征集的必要条件是该征集所描述的所有子句确定的征集为大征集。由此,可以得到基于可拓理论的Apriori算法的2个关键步骤[6]：①大征集的交运算：设X 1,X 2是2个大征集,进行交运算后生成征集的描述X是X 1,X 2中所有子句的合取范式；②征集的删除运算：对k元征集集合中的每一个征集Xk的所有k-1元子句进行检查,如果发现有某个k-1元子句所确定的征集Xk-1不是大征集,便将该征集从该k元集合中删除。

3.2 改进Apriori算法的描述

输入:数据库D，最小支持度阈值s0，最小置信度阈值c0输出:关联规则集R基于可拓理论的Apriori算法描述如下[7-9]:

①扫描整个数据库D，统计每一条记录的每一个元素，得到一个元素集合S；

②以S中每一个元素构成一个集合，形成一元候选集H 1，设置一个元计数单位k，并令k=1；

③对于概念描述Y，依次计算Hk中每一个征集XkyY的支持度s和置信度c，如果Xk的支持度sE s0，则进行如下判断：

a对于给定的置信度阈值c0，如果Xk的置信度cEc0，则输出一条规则XkyY；

b如果Xk的置信度cFc0，则将Xk存入大征集Lk中；

④若Lk中的元素的个数少于2个，则停止；否则，对于Lk中的每一个Xk，对Xk中的所有元素按字典顺序排列；

⑤从Lk中取出2个不同的征集Xki，Xkj，对这2个征集的元素进行逐一比较，如果满足前k-1个元素相同，第k个元素不同，则以Xki所用元素和Xki的第k个元素构成一个新的k+1元征集，并将其存入Hk+1。对Lk中的所有征集两两组合进行此操作，生成k+1候选集；

⑥令k=k+1，返回到③。

4 改进Apriori算法的性能验证

为进一步验证改进的Apriori算法性能，采用VC++实现上述算法，并利用SQLServer2005数据库中的模拟实验数据对改进的Apriori算法及经典的Apriori算法进行了验证。测试数据分别为600、900、1,200条记录，最小支持度分别为0.05，0.07，0.09，0.11，0.13，0.15，0.17，0.19，0.21，实验结果表明，通过Apriori算法挖掘出的规则含有大量的冗余规则，采用改进的Apriori算法得到的规则集既没有冗余规则也没有遗漏规则，但当最小支持度增大或数据库中的数据量增大时，改进算法的运行速度略低于Apriori算法。

5 结束语

分析了Apriori挖掘算法的特点及存在的问题，同时提出了Apriori挖掘算法的改进方法，并对改进前、后的算法进行了实验数据的分析研究。分析结果表明，通过经典的Apriori算法挖掘出的关联规则包含大量的冗余规则，而改进的Apriori算法没有冗余规则的产生,并且产生的规则既没有遗漏又简单明了，但改进的Apriori算法的执行效率略低于经典的Apriori算法。

[1]毛国君,段立娟,王实等.数据挖掘原理与算法[M].清华大学出版社,2005.

[2]谭光明,冯圣中,孙凝晖.一种基于新型的数据挖掘算法研究[J].软件学报,2006,17(7)：1501- 1509.

[3]刘琦.基于关联规则的数据挖掘算法研究[C].杭州:浙江大学,2008.

[4]李新良,陈湘涛.数据挖掘中关联规则算法的研究[J].计算机工程与应用,2007,12(29):111.

[5]李立希,李铧汶,杨春燕.可拓学在数据挖掘中的应用初探[J].中国工程科学,2004,6(7):53- 59.

[6]陈文伟,黄金才.可拓知识与可拓数据挖掘[J].广西师范大学学报(自然科学版),2006,24(4):159- 162.

[7]Jiawei Han,Hong Cheng,Dong Xin,Xifeng Yan.Frequent pattern mining:current status and future directions[J].Data M ining and Know ledge Discovery,2007(15):55- 86.

[8]Alain Deschenes,Kay C.W iese.Using different algorithms for improving the Accuracy of Data M ining Algorithm[J].Simon Fraser University,2004,598- 606.

[9]张玉林.一种无冗余的关联规则算法.计算机工程与应用,2007,43(3):26- 29.