Apriori算法的优化方法

第19卷第g期计算机技术与发展Vol.19 No.6june 20092009年6月COMPUTER TECHNOILO;Y ANI)IEVFEL( PMENTJuneApriori算法的优化方法|:陈伟(淮南联合大学计算机系,安徽淮南232038)摘要:关联规则是数据挖掘的主要技术之一,是指从-一个大型的数据集中发现有趣的关联或相关关系,即从数据集中识别出频繁项集,然后再利用这些频繁集创建描述关联规则的过程。频繁项集挖掘是关联规则挖掘的主要步骤,在频繁项集挖掘中,需要大量进行两个操作:判断两个k -项集是否是前k- 1项相同且最后一项不同，即连接步;判断一个项集是否为另-个项集的子集,即剪枝步,通过臧少连接操作和剪枝操作的循环次数,以此来提高Aprioni算法的效率。关键词:关联规则;Aprion算法;濒繁项集中围分类号:1IP301.6文献标识码:A文章编号:1673 - 629(2009)06 - 0080-04Method of Apriori Algorithm OptimizationCHEN Wei(Dept. of Computer,Huainan Union University,Huainan 232038 ,China)Abstnact:Association rule is one of the key technologies ol deta mining to hnd the funny ssocitio or relationship from the given dataset,it is to say, asociation nule is to extract frequent item set from the dataset at first, and then establish the process of description of associa-tion nule acording to frequent item. The frequent iemsets mining is the main steps of association rule mining. In the frequent itermsetsmining,need to carry out a lange number of two operations:judge the twok - iten sets of whether the formerk - 1 of the same and thelast dfferent,that is step - by - step connection;to determine whether an item set for another subsetof the set, that is step- by- steppruning.can reduce the times of cycle the∞net operation and the pruning oqperation, in order to improve the eficiency of Apriori algo-nithm.Key words: saciationo rule;Apriori algorithm;freqvent itemsets0引言重要、最活跃的研究内容。在Aprioni算法中需要大量进行这样两个操作:判-般地,关联规则挖掘是指从一个大型的数据集断两个k -项集中是否前k- l项相同且最后一项不(Dataset)中发现有趣的关联(Association)或相关(Cor-同,即连接步;判断- -个k-项候选集的所有k-1子relaion)关系,即从数据集中识别出频繁出现的属性值集是否都是k -项频繁集,即剪枝步。假定事务数据库集(Sets of Attribute Values) ,也称为频繁项集(Fre-中各记录的项目均已按字典排序。可以利用项集之间quent Itermsets, 简称频繁集),然后再利用这些频繁集有序的特点,从减少算法中这两个操作的执行次数的创建描述关联规则的过程。角度来达到优化算法的目的。关联规则可形式化定义为:设1= {i,i,.",iml 是由m个不同的项组成的集合。给定一一个事务数据库D,其中每- -个事务T是I1关联规 则的简单描述关联规则是描述数据库中一组数据项之间的某种中-组项的集合,即T∈I,T有一个唯一的标示符潜在关系的规则。关联规则形式简洁、易于解释和理TID。若项集X∈I且XS T,则事务T包含项集X。解,并可以有效地捕捉数据间的重要关系,从大型数据关联规则是形如X => Y的蕴涵式,其中XS .库中挖掘关联规则问题已成为数据挖掘中最成熟、最T,YST,并且X∩Y= 0,如果D中事务包含X∪Y的百分比为S .则称s为关联规则X => Y的支持收稿日期:2008-09-21;修回日期:2009-01 -04度,中国煤化工包含X的事务同时基金项目:2007年安徽省高校青年教师资助计划项目(200g1197)也包YHCN M H G关联规则X=> Y作者简介:陈伟(1975 - ),女,安徽六安人,讲师，研究方向为数据的置信度,它是条件概率P(Y/X)。习惯上将关联规库敷据挖掘。则表示为X => Y(S% ,C% )。关联规则的发现任务第6期陈伟:Apriori 算法的优化方法81或问题就是在事务数据库D)中找出所具有用户给定选k-项集*/的最小支持度阈值(min.sup)和最小置信度阈值(4)For all transactionst∈D do begin(min. cof) 的关联规则,即这些关联规则的支持度和置(5)C, = subset(C;,t);/*候选集C中提取包含信度分别不小于最小支持度和最小置信度。在事务t中的候选k-项集*/如果项集的支持度满足最小支持度min. sup,则(6)For all CandidatesC∈C, do它称之为频繁项集(Frequent Itemse)川。(7)C.Count ++;所以关联规则的挖掘- -般分为以下两个过程:(8)End(1)找出所有的频繁项集,也就是找出事务数据库(9)L={C∈C | C.Conut≥min. supl;中所有大于等于用户指定的最小支持度的数据项集,(10)End即具有最小支持度的数据项集。(11)retumL = ULk;(2)由频繁项集产生强关联规则:根据定义,这些函数Apriori. gen按如下方式分两步进行工作:规则必须满足最小支持度和最小置信度。●连接步在上述两个步骤中,第一步是挖掘关联规则的关Procedure aprioni_ gen( Lk-1 ;min. sup)键步骤。关联规则挖掘的总体性能由该步骤的性能所1)for each itemset L∈L2-1 .决定。所以,现有的研究都集中在第-一个步骤上 ,也就2)for each itemset L2∈L-1是对频繁项集的挖掘处理上。3)if((L[1]= L2[1]) ^ (L[2]= L2[2]) A...^ (L[k-2]= L2[k-2])^(L[k-1]< L2[k-2 Apriori 算法1]) )then{关联规则挖掘有多种分类方法:单维、单层和布尔4)C= L1田L2;关联规则挖掘。它们都是最简单形式的关联规则挖5)if has- infrequent. subset(C, L-1)then掘,最著名、最有影响的关联规则挖掘算法是R. A-6)delete C;grawal等人提出的Apriori算法,该算法是一种挖掘布7)else add C to C;尔关联规则频繁项集的算法。算法基于频繁项集性质8)}的先验知识,使用--种称为逻层搜索的迭代方法来找9)reum Ck;出所有的频繁项集。●剪枝步Aprioni算法通过对数据库D的多趟扫描来发现Procedure has- infrequent. sube(C,L-)所有的频繁项目集.在第一趟扫描数据库时,对项集11)for each(k- 1)- subsetsof C中的每一个数据项计算其支持度,确定出满足最小支2)ifs氏L2-1 then持度的频繁1项集的集合L1,然后,L用于找频繁23)retum true;项集的集合L2, 如此下去....在后续的第k趟扫描4)retumn false;中,首先以k- 1趟扫描中所发现的含k- 1个元素的C,中的成员可以是频繁的也可以是不频繁的,但频繁项集的集合La-1 为基础,生成所有新的候选项目所有的频繁k-项集都包含在C中。如果确定C中每集Ck(Candidate ltemsets) ,即潜在的频繁项目集,然后个候选的计数,从而确定L,,那么涉及的计算量就很扫描数据库D,计算这些候选项目集的支持度,最后从大。为压缩搜索空间,可以用Aprioni性质:任何非频繁候选集Ck中确定出满足最小支持度的频繁k项集的的(k- l)-项集都不可能是频繁k -项集的子集。因集合Lx,并将L,作为下一趟扫描的基础。重复上述过此,如果一个候选k -项集的(k- l)-项集不在L2-1程直到再也发现不了新的频繁项目集(2]。中,则该候选也不可能是频繁的,从而可以从C中删Aprioni算法的基本描述如下;除。输入:事务数据库D; .下面来举例说明以上阐述的过程。设事务数据库.最小支持度计数阈值min. sup。D,见表输出:D中的频繁项集L。中国煤化工,Apriori 算法执行(1)L1 = find. frequent- 1 - itemses(D); .过程TMYHCNMHG(2)For(k = 2;Lx-1≠0;k + +)do begin(1)算法第一次扫描数据库,确定候选1-项集及(3)Ck = aprioni- gen( Lx-1,min. sup);/*生成候各项集的支持度计数C;,如图1所示。●82.计算机技术与发展第19卷表1事务数据库3减少连 接步骤的执行次数TIDItem由于已经设定各事务项目按字典排序,其中的任1,3.4一个k-项集L,有L[1]< L[2]<.< L[k]。所以2,3,5对于两个(k-1)-项频繁集L。和L6(a< b),若L。和1,2,3,5L,不符合连接条件,则La 与Lo之后的所有(k-1)-2,5项集都不能满足连接条件。所以只要La与L。不能连(2)利用L田L来产生候选2-项集C2,由C2接,就不需要再判断L。与L。之后的所有(k-1)-项确定频繁2-项集,如图2所示。集是否能连接,从而减少循环的次数[3.4]。改进算法:(3) 利用L2田L2进行连接操作,获得候选3-项Procedure aprioi. gen (L_-1 ;minL sup)集C3= {2,3,5|。根据Apriorni性质:一个频繁项集的for each itemnetL。∈La-1 .所有子集也是频繁的,{2,3,5}的2项子集是{2,3},for each itemset Lo∈L2-1{2,5}和{3,5} ,所有2项子集都是L2的元素,因此是i((L。[1]= L。[1]) ^(L.[2]= Lo[2])A... A(L[k-2]频繁的。结果如图3所示。= L6[k-2]) ^ (L。[k-1]< Lo[k - 1]))then|C= L。由Ls;C:候选项集厶:频管项集if has. infrequent. sube(C,项集支持度计敷Lx ,)then扫捕数据库{1)2与最小支持度计delete C;D,获得候选数比较后的1-频(1else addC to C;1.项集2}繁项集{233}else break;{3retum C;4)155}4减少剪枝步骤的执图1产生1频繁项集行次数L:频繁项集对于--个k-项候选集支持度计数的任意一个子集(k-1)-项与最小支持度集L。和一个(k-l)-项频繁由L产生候计数比较后的{I, 2}选2-项集2-频繁项集集L,若L。[i]= L6[i],则{2, 3}(I, 3}L。是频繁的，结束判断;若{1, 5}1{2, 5)L。[i]> Lo[i], 则继续和下(3, 5}一个(k-l)-项频繁集比较,如此下去;若La[i]<{2.5}L[i],由于各事务项目按字{3, 5}典排序,则L。与L,后的所有围2产生2频繁项集(k- l)-项频繁集都不会相G:候选项集同。所以只要L。[i]< L6[i], .与最小支持度。计數比较后的「就不需要再判断L。是否与L。选3-项集3-频繁项集后的(k- 1)一项集相同。由(2.3, 5}(2. 3, 5}此就能判定La 不是频繁项.集。由Apriori算法性质:频繁困3产生3频繁项集项集的所有非空子集都必须是频繁的,所以该k -项(4)利用L3田L3进行连接操作得到C4,根据候选中国煤化工。该步操作中大大Apriori性质可知C = 0 ,算法至此结束。在Aprioni算法中连接步和剪枝步是频繁操作的减少|YHC N M H G否是频繁项集的执两个步骤,以下就从这两个步骤人手,来提高算法的效行次数一”。改进的算法为:Procedure has infrequent. subset(C,La-1)率。第6期陈伟:Apriuni 算法的优化方法， 83for eachL6∈L&-16结束语fL。CC then//L[iJ∈L。 andLo[li]∈L6以上的改进方法用VFP6.0已进行了验证。关联lif (L。[i门]= L[i])then规则的应用很广泛,而它的经典算法Aprioni 算法中的{ La∈L-;break;|频繁项集求解是耗时最多的工作,那么提高了频繁项else i(L[i]> Lo[i])then集的求解速度,也就加快了关联规则的求解速度。continue;dise break;参考文献:ifL。氏4-1 then[1] 陈文伟,黄金才.数据仓库与敷据挖掘[M].北京:人民邮retum true; retum false;电出版社,004.[2] Agrawal R, lmielinsksi T, Swami A. Mining asociation rules5举例between sets of items in large dabases([C]Predings of下面举例说明8.9]。the ACM SIGMOD Conference on Manageament of data(ACMSIGMOD'93). Washington, USA:[s. n. ],1993:207 - 216.(1)连接步:假设有6个2-项频繁集:L1 = {1,[3] 袁万莲,郑诚,翟明清. -种改进的Aprioni算法[J].计算2},L2= {1,3}, Lg= {1,5},L4= {2,3}, Ls= {2,机技术与发展2008,18(5):52 -53.4},L6= {2,5}。L1和L2、L1和L3满足连接条件,可[4]何中胜 ,庄燕滨.基于Apriori&Fp - growth的频繁项集发以连接。L和L4不满足连接条件,不能连接。依照改现算法[J].计算机技术与发展2008,18(7):46 -47.进的算法,L1和L4之后的所有频繁项集都不满足连[5]吴志丹， 赵大宇,唐恒永.一种改进的关联规则挖掘算法接条件,从而减少了L1和Ls、L1和L6的判断。[].沈阳师范大学学报:自然科学版2006(3):258 - 259.(2)剪枝步:假设有一一个3-项候选项集:C={1，[6] Agrawal R,Sikant R.Fast Aegritirs for Mining AociationRules in Large Databe([C]/Proceding of the 20th Interma-3,5},4个2-项频繁集:L] = {1,3},L2= {2,3},Lstional Conference σn Very Large Databases. Santiago, Chile:= {2,5},L4= {3,5}.C的2-项子集为:C1= {1,3},[s. n. ],1994:487-499.C2= {1,5|,Cj= {3,5|。第一步在2 -项频繁集中寻7] 胡吉明,鲜学丰.挖掘关联规则中Aprioni算法的研究与改找C,首先C1和L1比较:C[1]= L[1],C[2] =进[J].计算机技术与发展,2006,16(4):99- 101.L[2],所以C1= L1。第二步在2-项频繁集中寻找[8] Cheung D W,Han J,Ng V,et al.A fast ditribured AlgoichmC2,首先Cz和L1比较:C2[1] = L[1], C2[2] >for mining asociation nuls[C]//n:Proe 1996 Int Conf Par-L[2],接着Cr和L2比较:C2[1]< L2[1],按照改进allel and Distributed Information Systems. Miami Beach, FL:[s.n. ],1996:31 -44.的算法,以后的都不用比较,也就确定该候选项集C9] 郭有强.一种高效的关联规则维护算法研究与实现[J].计的子集C2不是频繁项集,由Aprioni算法性质确定该候算机技术与发展,2007,17(10);123- 126.选项集C也不是频繁项集,所以删除它。(上接第79页)[28] Osher s, Sethian J. Fronts propegating with curvaturede分割方法[J].中国图象图形学报, 2006, 11(9): 1312 -pendespeed:algorithms based on the HaniltonJacobi formula-1316.tion[J]. Joumnal of Computational Physics, 1988,79(1):12 -[34]秦昆,徐敏.基于云模型和FCM聚类的遥感囝像分割l9.方法[J].地球信息科学,2008,10(3):302 - 307.[29]陈波,赖剑煌,马建华.一种耦合的活动轮廓模型及其在[35]郑洪英.数据挖掘聚类算法的分析和应用研究[D].重庆:图像分割中的应用[].中国图象图形学报2007,12(3):重庆大学,2002.444- 449.[36]邵锐,巫兆聪,钟世明.基于粗糙集的K-均值聚类算法[30]谢勤彬.罗代升.基于改进活动轮廓模型的超声图像分割在图像分割中的应用[J].测绘信息与工程,2005, 30(5):1[J].科学技术与工程,2007,7(8):1638 - 1641.[31] 陈波,赖剑煌. 用于图像分割的话动轮廓模型综述[J]. [37] 许海洋.王万森基于SOM神经网和K-均值算法的图像中国图象囝形学报,2007,12(1):11 -20.中国煤化工:1):38-40.[32] Bezdek J C. Pattem reognion with fuzzy objecive function[38]!聚类神经网络的图像algonithms [M]. Norwell, MA, USA: Kluwer AcademicYHC N M H S320)93-95.Publishers, 1981.[39]薛岚燕,郑胜林,潘保昌,等.基于神经网络的灰度图像阏[33刘华军,任明武,杨静宇.-种改进的基于模糊聚类的图像值分割方法[J].广东工业大学学报2005,22(4):67 - 72.