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

2012.323技术应用关联规则中Apriori算法的研究与改进宋小小陈晓辉刘冲桂林理工大学广西541004摘要：关联规则反映了大量数据中项集间的相互依存性和关联性。Apriori算法是关联规则挖掘中的经典算法，目前已有很多的改进版本，但大多存在多次扫描数据库，项集生成瓶颈和模式匹配频繁的问题，算法效率比较低。本文深入的分析研究关联规则Apriori算法，改进候选频繁项目集的连接和剪枝策略，改进对事务的处理方式，减少模式匹配所需的时间开销，并给出了改进算法。关键词：数据挖掘；关联规则；Apriori；频繁项集0引言数据挖掘是一门新兴起的交叉学科，主要研究事务数据库、关系数据库中的数据项之间潜在有用的新颖的规律。它的主要方法包括：分类、关联规则、聚类、特征、回归分析、变化和偏差分析等。关联规则挖掘就是从海量的数据中寻找数据项间的关联关系，它是数据挖掘领域中研究的热点问题。关联规则表示数据库中一组对象之间具有某种关联关系的规则，其主要挖掘对象是事务数据库。这种数据库大量的应用在零售业，而条形码技术的发展使得数据的收集变得更加方便、更加完整。关联规则就是在这些交易项目中去寻找某种关联关系。1993年，Agrawal等人首先提出了挖掘顾客交易项目中项集间的关联规则问题，此后诸多的研究人员对关联规则挖掘问题进行了大量的研究与改进。1Apriori算法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算法的基本原理性质1K项数据项目集是频繁项目集的必要条件是它的所有k-1项子集均是频繁项目集。性质2K频繁项目集的所有K–1维非空子集均是频繁项目集。定理1若K维数据项目集X={i1,i2，…，ik}中，存在一个jX，使得|L1k(j)|k–1，则X不是频繁项目集。作者简介：宋小小(1987-)，男，桂林理工大学信息科学与工程学院硕士研究生，研究方向：数据库，数据挖掘。陈晓辉(1963-)，男，副教授，研究方向：网络数据库，人工智能，数据挖掘。刘冲(1986-)，男，硕士研究生，研究方向：数据库，数据挖掘。2012.324技术应用其中，|L1k(j)|表示(K–1)维频繁项目集的集合L1k中包含j的个数。证明假设X是K维频繁项目集，根据性质1，X的k个(k–1)项目子集都在L1k中，其中每一个项目pL均出现k–1次，故∀pL，均有|L1k(p)|k–1，这与条件矛盾，故X不是频繁项目集。推论1如果k–1维频繁项集集合L1k中包含单个项目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算法描述如下：输入事务数据库D，昀小支持度min_sup。输出所有的频繁项目集。Begintran_num=0；//统计事务的数量T[i]=0；//按顺序排序的事务集合L1=f_getL1(D,min_sup)；for(k=2；L1k；k++){ForeachitemiinL1kForeachsubitemjinij.count++；//由推论1,去除L1k中不可能为k频繁项目集中项的项remove(L1k|j.countk-1)；ForeachitemsetxinL1k{ForeachitemsetyinL1kif(x1=y1x2=y2…x2k=y2kx1ky1k){itemset_num=0；For(i=1,j=1；i|Tx|,j|Ty|；)if(Tx[i]Ty[j])i++；elseif(Tx[i]Ty[j])j++；else{itemset_num++；Txy=Txy{Tx[i]}；i++；j++；}}if(itemset_numtran_nummin_sup){Lk=Lk{xy}}}}End//获取频繁1-项目集Algorithm：f_getL1(D,min_sup)Input：事务数据库D，昀小支持度min_supOutput：频繁1-项目集Beginitemset=get_item(D)；ForeachtransactiontinD{tran_num++；Foreachitemiint{2012.325技术应用i.count++；puttidintoT[i]；}}L1={i|iitemseti.counttran_nummin_sup}；Remove(T[i]|i.counttran_nummin_sup)；End3实验与结果分析与经典的Apriori挖掘算法相比,改进后的挖掘算法有如下优点：(1)算法只在计算频繁1–项目集时需要对整个数据库进行访问，在计算候选k项目集的支持度时，仅需要数据库中频繁k–1项集信息。而随着k的增大，频繁项目集的数目不断减少。(2)算法采用垂直对应数据库结构，通过该数据库结构很容易计算候选项目集的支持度。(3)算法在生成一个候选项目集后就计算其频繁度，避免了模式匹配，减少内存的使用。为了进一步验证算法的有效性，实验在内存为512MB，CUP主频为1.7GHZ，操作系统为WindowsXP2的环境下进行，并用VC++6.0分别实现了经典Apriori算法和本改进算法。数据由笔者随机生成，有2800个数据，90个项集，昀小支持度为15%，实验结果如表1所示。表1两种算法在不同项集个数下的运行时间执行时间/s项集个数Apriori算法改进Apriori算法503.112.03603.922.56705.023.32806.284.01907.464.83从表中可以看出，经过改进的Apriori算法在执行速度上有了较大的提高。4结语本文通过深入分析经典Aprior算法的优缺点，在此基础上提出了改进的Apriori关联规则挖掘算法，并给出了详细的算法描述。经实验证明，改进的Apriori算法比经典的Apriori算法有着更好的频繁项集的提取速率。参考文献[1]陈应霞,陈艳.关联规则中的Apriori挖掘算法改进[J].长江大学学报(自然科学版).2008.[2]徐章艳,刘美玲,张师超等．Apriori算法的三种优化方法[J].计算机工程与应用.2004.[3]李云峰,陈建文,程代杰,关联规则挖掘的研究及对Apriori算法的改进[J].计算机工程与科学.2002.[4]曾万聪,周绪波,戴勃等.关联规则挖掘的矩阵其法[J].计算机工程.2006.[5]AgrawlR,ShaferJ．ParallelMingingofAssociationRules:Design，Implementation，andExperience[P].USA:CA95120.1996．[6]K1einbergJ，PapadimitriouC，RaghavanP．SegmentationProblems[A]Proceedingsofthe30thAnnualSymposiumontheTheoryofComputing[C].NewYork:ACMPress.1998．[7]毛国君,段立娟,王实,石云.数据挖掘原理与方法.北京:清华大学出版社.2007.[8]刘君强,孙晓莹,潘云鹤.关联规则挖掘技术研究的新进展[J].计算机科学.2004.[9]王伟勤,郑海.Apriori算法的进一步改进[J].计算机与数字工程.2009．[10]杨启昉,马广平.关联规则挖掘Apriori算法的改进.计算机应用[J].2008.[11]马盈仓.挖掘关联规则中Apriori算法的改进.计算机应用与软件[J].2004．[12]BrinS，MotwaniR，SilversteinC．BeyondMarketBaskets：GenerlizingAssociationRulestoCorrelations[A].ProceedingsoftheACMSIGMOD[C]NewYork:ACMPress.1996．ResearchandimprovementonApriorialgorithmofassociationruleSongXiaoxiao,ChenXiaohui,LiuChongGuilinUniversityofTechnology,Guangxi,541004,ChinaAbstract:Becauseofscanningthedatabasemanytimesandfrequentlyusingthepatternmatching,theclassicApriorialgorithmproducesalargenumberofcandidateitemsets,whichresultsinlowefficiency.TheApriorialgorithmhasbeenimprovedfromnextthreeaspects:firstly,thestrategyofthejoinandprunestepwasimproved;secondly,themethodofdealingwithcondidateitemsetswasimprovedtodecreasethetimeofpatternmatching;intheend,themethodofdealingwithdatabasewasimproved.Accordingtotheseimprovements,animprovedalgorithmwasintroduced.Theexperimentalresultsoftheimprovedalgorithmshowthattheimprovedalgorithmismoreefficientthantheoriginal.Keywords:datamining;associationrule;Apriori;frequentitemsets