Apriori算法的分析与改进

第25卷第2期宁波工程学院学报Vol.25 No.22013年6月JOURNAL OF NINGBO UNIVERSITY OF TECHNOLOGYJun.2013D0103969/.s.1008 -7109.2013.02.014Apriori算法的分析与改进黄超君,范剑波(宁波工程学院，浙江宁波315000)摘要:在舆论分析系统中,高效 、准确地获取敏感词一直是研究的热点。由于Apriori 算法能较好地挖掘出事务之间的关系,并能快速找出新的敏感词,所以探索改进的Apriori算法显的更为重要。本文分析了经典Aprior算法的不足,提出了改进的Apriori算法,优化了程序执行的效率。实验结果表明:改进后的Aprioni 算法的执行效率比经典Aprioni算法的执行效率要高。关键词:数据挖掘;Aprioni算法;优化中囝分类号:017文献标识码:A文章编号:1008- -7109(2013)02 -0064-05引言关联规则挖掘是近年来数据挖掘研究中的一个热门领域,它反映了事务数据库中一个事务与其他事务之间的相互依存性和关联性,关联规则的目的就是为了挖掘出大量数据间隐藏的关联,方便决策者对事务进行判断和决策。为了发现事务数据库中存在的相互关联的重要规则,AgrawalR和SrikantRU12I于 1993年首先提出了挖掘顾客交易数据库中项集间关联规则的问题，其核心方法是基于频繁项集的递推方法,并在1994年提出了关联规则挖掘的快速算法;Park J. S.等人[)提出的DHP算法,缩减了事务数据库的大小,减小了I/ 0操作时间，其效率比Apriori算法有了明显的提高;Shirgaonkar S等人(4)提出了-种应用于大学图书馆的Apriori改进算法,还有-些作者8.8分别提出了不同的Apriori 改进算法。本文结合BBS舆情分析系统的案例,提出了三项改进措施,优化了Apriori 算法,提高了算法的执行效率。1 Apriori 算法的分析.1.1经典Apriori算法的思想假设关联规则挖掘的事务数据库记为TDB = {T,T2, .. ,Tp,.. ,T,T=i,iz, .. ,小(1≤p≤n,),T .称为事务,i称为项目。设I=( i.,,..... ,i.]是TDB中全体项目组成的集合。每一个事务T。是1中一组项目的集合,即T,CI,每个T。有一个唯- - 的标识符TID。设项集X是1中项目的集合,如果X中有k个项目,那么称X的长度为k,或称为k项集。定义1:设和是项集,且x∩Y=O,规则X=>Y在TDB中具有支持度s就是TDB中包含X和Y的事务数与TDB中事务总个数之比，即:support(X=>Y )=support(XUY )=P(XUY)中国煤化工收稿日期:2013- 04-23作者简介:黄超君,男,宁波工程学院电信学院计科091班学生;指导老师:范剑汕.MYHCNMHG授。基金项目:2012年度浙江省大学生科技创新活动计划(新苗人才计划)项目(2012R422005)。黄超君范剑波:Aprioni算法的分析与改进65定义2:设和是项集,且XY=,规则XY在TDB中具有置信度c就是TDB中同时包含和的事务数与TDB中包含的事务数之比,即:confdence(X=>Y)= sppor(8U)support(X)如果某个k项集{i,n,...,在TDB中出现的概率大于或等于最小支持度min.sup,则称为频繁k项集,记作Fr。经典Apriori算法的思想就是将发现关联规则的过程分为两步:第1步是通过迭代,找出源事务数据库TDB中所有的频繁项集,即支持度不低于用户指定的最小支持度min._sup的所有频繁项集;第2步是根据第1步找出的频繁项集构造出置信度不低于用户指定的最小置信度min._conf的强关联规则。第1步工作的计算量和磁盘I/0量都很大,几乎所有的关联规则挖掘算法都是针对第1步提出的。经典Apriori算法使用逐层搜索的迭代方法来产生频繁项集,每--次迭代包括两个步骤:如在第k次迭代中，首先根据频繁k-1项集F-1通过自连接产生候选K项集Cr,在其中涉及连接步和剪枝步;然后对候选K项集C.根据最小支持度min. _sup 计数产生频繁k项集Fr。迭代过程可以表示为:IC1F1C2F2C3F3C4F4。当然,剪枝步和算法终止的条件均要用到以下Apriori算法的性质。性质:频繁项集的所有非空子集也必须是频繁的。1.2经典Apriori算法的不足经典Apriori算法能够比较有效地产生频繁项集,但也存在着以下不足:(1)数据库扫描的次数太多,每次寻找频繁k项集(k=1,,n)时都需要扫描数据库一次来求得候选项集的支持度,共需要扫描n次。如果遇到海量数据库,或者n太大时,耗时太长,难以满足实际应用的需要。(2)经典Apriori算法会产生大量的中间项集,由频繁k-1项集F-1进行连接生成的候选k项集Ck数量巨大,每一次迭代产生的C,是呈指数级别增长的。由于C的规模巨大,所以验证Ck中的项是不是F中的项需要占用算法很多的时间9。2 Apriori算法的改进根据Apriori算法的性质以及前面的分析，我们不难得出以下四个推论。推论1:一个非频繁项集的任--超集必定也是非频繁的。推论2:若候选k项集Cx中某个k项集的某个k-1项的子集不在频繁k-1项集F中,则此k项集是非频繁的。推论3:若某事务Tp不支持频繁k-1项集F_中的每一项集,则T必不支持Cr中的任-项集。推论4:若某事务Tp不包含候选k-1项集C2-t中的任一项集,则也必不包含候选k项集C中的任一项集。根据前面的分析以及Apriori算法的性质和推论,我们提出了Apriori算法的-些改进。改进1:如果事务数据库是来源于某网站-段时间内帖子经过分词后的关键词,则可以将每-一个帖子看作是一个事务,每个帖子中的每个关键字看作是-一个项目’9。由于舆论分析有一定的特殊性,并不.是所有的词都是敏感词,所以可以设置--个完全不敏感词库来减少每个帖子中关键字的数量,也就是说减少每个事务中的项目的数量。在候选1项集C.生成时,其成员数可能较多,如果可以与一个完全不敏感词库匹配,则可以在C,中直接去除不可能是敏感词的关键字,这样能大大减少L和C成员的数量,从而提高算法执行的效率。中国煤化工改进2:根据推论1和2可以得出:如果候选k项集Cr中某个CNMHG不在频繁k-1项集F_中,则此k项集是非频繁的,可以进行剪枝。在剪枝的时nMmn的某个k6宁波工程学院学报2013年第2期项集的某个k-1项子集去扫描频繁k-1项集F_,如果C中的频繁项集过多,那也会增加扫描时间。我们可以将每次生成的候选k-1项集Cu分成频繁k-1项集和非频繁k-1项集,如果频繁k-1项集个数多于非频繁k-1项集,则在剪枝过程中扫描非频繁k-1项集;如果频繁k-1项集个数少于非频繁k-1项集,则在剪枝过程中扫描频繁k-1项集。改进3:根据推论3和4,由于任何长度为k的事务都不可能包含k+1项集,所以在对候选k项集C.计数生成频繁k项集F.后,可以立即删除长度为k的事务。例如,对原始事务数据库中C1计数生成F:后,可以立即删除长度为1的事务,因为这些事务不会对后面的F2的生成起作用;在对C2计数生成F2后,可以立即删除长度为2的事务,这样事务数据库就被压缩了。此方法可以应用到以后的每- -次迭代中,从而能提高算法执行的效率。改进和优化的Apriori算法描述如下:(1)C1=find_ candidate_ 1-itemsets(TDB);//找 出所有的候选1项集C1(2)C' 1=match. _itemnsets(C1); //匹配完全不敏感词库,去除C1中不可能是敏感词的关键字,//详见改进1(3)Fr=find_ frequent_ 1-itemsets(C' );//找出所有的频繁1项集Fi(4)for(k=2; F-≠中; k++)(5){ /* 根据频繁k-1项集F-找出侯选k项集Cx */(6)C=中;(7)for each itemset f∈F-(8)for each itemset f2∈ F-1(9){insert into c // (9 -12)将频繁k-1项集F-中二个成员f;和f进行连接(10)Select f[1],f[2],.. ,f[k-1],&[k-1](11)From Fr_.f,Fu.f2(12)Where f[1]=f[1 ]and-and f[k-2]=f[k- 2]and f[k-1]=f[k-1](13)For each (k-1)children s of c /对连接生成的k项集c中的每一个k-1子集sIfs≠FthendeletecelseaddctoC}/进行剪枝,详见改进2(14)for each transaction teTDB do(15){//扫描TDB,进行事务压缩和计数(16)TDB.=reduce(TDBr_); //从TDB_1中得到F_后,可以删除长度为k-1的事务而//形成TDB,详见改进方法3(17)C-=subset(C,t);//取出事务t中包含的候选项集(18)for each candidate c∈C // (18- -19)对每一个候选项集进行计数(19)c.count++ }(20)Fr=[c∈Ck | c.count≥min_ sup} I1求出频繁k项集F(21)}(22)returm F=U[F; /求出 F的并:3算法的实验为了证明算法改进以后执行的效率，需要分别对经典Aproni中国煤化工行了比较和分析。本程序的测试平台是WindowsXP,测试工具是elipse以HHCN MH C ;测试方法用Java语言编写了2个类,一个是改进前的Apriori算法,--个是改进后的Aprioni算法。事务数据库黄超君范剑波:Aprion算法的分析与改进6来源于某网站一段时间内帖子经过分词后的关键词,每-一个帖子作为一个事务,每个帖子中的每个关键字看作是一个项目9。在数据采集中,分别对每个帖子的关键词数进行了统计,得到事务长度大约在6到18之间。算法执行的输人值是一批事务，下面分4种情况分别进行了测试。(1)事务数少、项目数少(50组事务,事务平均长度为6)表1事务数少、项目数少时间(秒)支持度0.20.30.40.50.6.7.8.9算法经典Apriori0.101 0.086 0.074 0.067 0.064 0.06 0.057 0.055改进的Apriori 0.078 0.07 0.065 0.06 0.054 0.048 0.044 0.043时间()0.12 T0.经典Aprion0.080.060.04改进的Aprion0.020.2 03 0.4 0.50.6 0.7 0809支持度图1事务数少、项目数少(2)事务数多、项目数少(1000组事务,事务平均长度为6)表2事务数多、项目数少0.2 0.3 0.4 0.5 0. ; 0.7.8 0.93.721 3.52 3.194 2.759 2.32 1.72 1.43 1.31改进的Aprioni2.66 1.98 1.53 0.893 0.651 0.54 0.453 0.411时间国经典Apnon0.2 0.3 0.4 0.5 06 0.7 0.8 09支持度圄2事务数多、项目数少(3)事务数少、项目数多(50组事务,事务平均长度为18)表3事务数少、项目数多0.2 0.3 0.4 0.50.6 0.7 0.8 0.9算法~经典Apriori 0.174 0.151 0.142 0.132 0.125 0.122 0.112 0.108改进的Aprioni 0.164 0.143 0.135 0.122 0.118 0.109 0.101 0.092「 时间(3)0。0.1641经Apnon中国煤化工02030.o506070809支持度MYHCNM HG围3事务数少项目数多8宁波工程学院学报2013年第2期(4)事务数多、项目数多(1000组事务,事务平均长度为18)表4事务数多、项目数多时间(秒)支持度0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9算法经典Apriori 5.312 4.711 3.699 3.13 2.745 2.501 2.431 2.313改进的Apriori 3.972 2.973 2.491 2.162 1.971 1.812 1.768 1.649时间(s)经典Aprion，改进的Apriori02 0.3 0.4 05 0.6 0.7 08 0.9支持度围4事务数多、项目数多.4结束语从算法的实验中可以看出,在事务数相同情况下,事务平均长度越短,改进算法的执行效率越高;在事务平均长度相同的情况下,事务数越多,改进算法的执行效率也越高。总体上,改进Apriori算法的执行效率比经典Apriori算法的执行效率要高。参考文献:[1]Agrawal R, Srikant R. Mining association rules between sets o f items in large databases [A]. Proc ACM SICMODInt. Conf Management of data[C]. Washington DC，May 1993. pp207 -216.[2]Agrawal R, Srikant R. Fast algorithms for mining asciation nules[A]. Proc 20th Int. Conf Very Large Database[C].Santiago, Chile, Sept 1994. pp487. 499.[3]Park J S, Chen M s, Yu P S. An efective hash- based algorihm for mining association nules[A]. Proceeding s ofACM SICMOD Intermational Conference On Management of Data[C]. San Jose ,CA, May 1995. pp175- -186.[4]S Shirgaonkar,T Rajkumar,V Singh. Application of Improved Apriori in University Library [A]. InternationalConference and Workshop on Emerging Trends in Technology[C]. Mumbai, India, Feb. 2010, pp535- 540.[5]栗晓聪,滕少华。频繁项集挖掘的Apriori 改进算法研究[J].江西师范大学学报:自然科学版，2011, 35(5):498- -502.[6]梅成,周兴斌.基于矩阵的Aprioni算法的优化[J].南昌大学计算中心,2008.[7]朱庆,恰汗.合孜尔.一种改进的Aprioni算法[J].计算机与数字工,2010,38(4):30 -32.[8]赵明茹,郭键,孙媛.基于线性链表存储结构的Apriori 改进算法[J].科学技术与工程,2011,11(23);5685- -5687.[9]任晓霞,李卓玲,周振柳. Aprioni 算法在BBS舆情分析系统中的应用[J].沈阳工程学院学报(自然科学版),2010(7).中国煤化工MHCNMHG下转第(78)页宁波工程学院学报2013年第2期CDIO教育理念,构建了建筑工程类专业的理论力学教学体系，提出了有效的教学模式、手段和方法,对提高学生学习理论力学的兴趣具有积极意义,希望该做法对同行教学有所帮助。参考文献:[1]查建中,何永汕、中国工程教育改革的三大战略[M].北京:北京理工大学出版社,2009(1).[2]林建.面向“卓越工程师”培养的课程体系和教学内容改革[].高等工程教育研究,2011(5).[3]钟金明,李苑玲.基于CDI0理念的工程教育实践教学改革初探[J].实验科学与技术,2009(12).[4]李望国,张晓东。创新构建基于CDI0工程教育理念“3+1"人才培养模式的研究[J].广东白云学院学刊,2011,18(1).[5]胡志刚,任胜兵,吴斌.构建基于CDIO理念的一体化课程教学模式[J].中国高等教育,2010(22).Reform on CDIO- -based TM- CDIO Teaching of Theoretical MechanicsCHE Jin-ru， QI Hui ，MA Yong - zheng，ZHANG Li- na，CHENG Gui - sheng(Ningbo University of Technology, Ningbo, Zhejiang, 315211, China)Abstracts: The paper, based on the Outstanding Engineers Training Project as well as the CDIOInitiative，constructs the teaching system for Theoretical Mechanics course in the civil engineeringspecialty and proposes effective teaching models and methods.Keywords: outstanding engineer ，CDIO Initiative, engineering education, curriculum system上接第(68)页Aprioni Algorithm Based on Posts Segmentation of WebsiteHUANG Chao-jun， FAN Jian- bo(Ningbo University of Technology, Ningbo, Zhejiang, 315016, China)Abstracts: In the public opinion analysis system， efficient and accurate accessing to sensitive wordhas always been the hot research issue. As Apriori algorithm can well delve into the relationshipbetween transactions and find out the new sensitive words quickly, it is important to explore theoptimized Apriori algorithm. This paper analyses the shortcomings of classic Apriori algorithm,proposes the improved Apriori algorithm to optimize the efficiency of program execution. Theexperimental results show that the improved Apriori algorithm中国煤化Isic Apriorialgorithm in terms of the efficiency of program execution.MYHCNMH GKeywords: data mining, Apriori algorithm, optimization