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

《关联规则中的Apriori挖掘算法改进》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、长江大学学报(自然科学版)2008年12月第5卷第4期:理工JournalofYangtzeUniversity(NatSciEdit)Dec12008,Vol15No14:Sci&Eng·341·关联规则中的Apriori挖掘算法改进陈应霞(长江大学计算机科学学院,湖北荆州434023;上海理工大学计算机与电气工程学院,上海200237)陈艳(长江大学计算机科学学院,湖北荆州434023;华东理工大学信息学院,上海200237)[摘要]关联规则挖掘是数据挖掘研究的一项重要内容。然而基于候选集的Apriori算法效率低下。针对此缺陷,提出了一种NApriori算法,该算法利用

2、频繁1项集重新组织事务数据库来挖掘关联规则。此方法仅需扫描数据库2次,且避免了Apriori算法繁琐的连接和删除步骤,从而提高了挖掘效率。[关键词]关联规则;数据挖掘;算法;数据库[中图分类号]TP311113[文献标识码]A[文章编号]167321409(2008)042N341203[1]经典的Apriori关联规则算法在大量数据的挖掘过程中,必须经过逐层的重复连接与运算步骤,才能找出所有的频繁项集。它在每一层中都会先产生大量的候选项集,而每一个候选项集又都必须与数据库中的每一笔事务记录做比较,不断地扫描数据库以找出所有符合最小支持度限制的频繁项集,直到找出所有频繁项集或

3、无法再继续产生新的候选项集,而后再利用这些频繁项集探讨事务之间的关系,推导出所有的关联法则。因为反复与数据库中的事务记录比较,要耗费大量的时间与内存空间,所以Apriori效率较低。针对Apriori算法的不足,提出一种新的优化Apriori算法:NApriori。1Apriori算法的改进思想111修剪频繁集[2]为了提高按层次搜索并产生相应频繁项集的处理效率,Apriori算法利用了以下几个重要性质:性质1一个频繁项目集的任一非空子集必定也是频繁项目集。性质2k项数据项目集是频繁项目集的必要条件是它的所有k-1项子集均是频繁项目集。从Apriori算法可以看出,生成Lk的

4、过程中产生了过多的候选项集,特别是22项集尤其多,如何减少候选项集的数量是个问题。根据关联规则的定义,可以得到下面的性质:性质3如果k-1维频繁项集集合Lk-1中包含单个项目i的个数小于k-1,则i不可能包含在频繁k2项集中。在第k步中,根据k-1步生成k-1维频繁项目集来产生k维候选项目集,由于在产生k-1维频繁项目集时,可以实现对该集中出现项目的个数进行计数处理。因此对某项目而言,若它的计数不到k-1的话,可以事先删除该项目,从而排除了由该项目引起的大规模所有组合,减少了候选项目的数量。这是因为对某一个项目要成为k维项目集的一个元素的话,该项目k-1阶频繁项目集中的计数个

5、数必须达到k-1个,否则不可能生成k维项目集。例1:假设L2={{1,2},{1,3},{1,5},{1,6},{2,3},{2,5},{3,5}},求C3。由性质3及上述思想可得到:L2(1)=4,L2(2)=3,L2(3)=3,L2(4)=3,L2(5)=3,L2(6)=1,由于L2(6)=1<2,故去掉L2中所有包含6项目的频繁项目集得到:L′2={{1,2},{1,3},{1,5},{2,3},{2,5},{3,5}}。112优化连接在对Apriori算法的分析中发现Apriori算法需要大量进行的操作是判断两个k2项集是否与前k-1项相同且最后一项不同。这项操作占了

6、程序运行的较多时间。如果能减少这项操作执行的次数,就可以[3]提高Apriori算法的运行效率。因此提出又一新的优化策略:优化连接策略。[收稿日期]2008209223[作者简介]陈应霞(19792),男,2003年大学毕业,助教,硕士生,现主要从事软件开发、数据挖掘方面的研究工作。·342·长江大学学报(自然科学版)2008年12月在进行L2连接时,若某个频繁12项集的支持度越大,那么该项集与其它频繁12项集连接生成的22项集成为频繁项集的可能性越大。所以在找出了频繁12项集后,可以对其中的项按支持度由小到大进行排序,使得支持度小的项排在前面,那么在L2连接生成候选集并采用

7、支持度剪枝后,结果使得支持度小的频繁22项集排在前面,依此类推。另一方面,在由k-1项集生成k项集时,当作自身连接时,若两个项集的前k-2项不同,则放弃该两个项集的连接运算。因为产生的项集不是重复的就是非频繁项目集,这样可减少计算量。下面通过一个示例数据库进行说明。例2:表1是某一商店的事务数据库D,数据库中有9个事务,5种表1事务集表项,即I1、I2、I3、I4、I5。(最小支持度为22%,即最小支持计数为TID项2)。如果项集按每项在数据库中出现的频率升序排序,则1I1I2I5L2={{I5、Il}