Apriori算法的分析與改進(jìn)

第25卷第2期寧波工程學(xué)院學(xué)報Vol.25 No.22013年6月JOURNAL OF NINGBO UNIVERSITY OF TECHNOLOGYJun.2013D0103969/.s.1008 -7109.2013.02.014Apriori算法的分析與改進(jìn)黃超君,范劍波(寧波工程學(xué)院，浙江寧波315000)摘要:在輿論分析系統中,高效 、準確地獲取敏感詞一直是研究的熱點(diǎn)。由于A(yíng)priori 算法能較好地挖掘出事務(wù)之間的關(guān)系,并能快速找出新的敏感詞,所以探索改進(jìn)的Apriori算法顯的更為重要。本文分析了經(jīng)典Aprior算法的不足,提出了改進(jìn)的Apriori算法,優(yōu)化了程序執行的效率。實(shí)驗結果表明:改進(jìn)后的Aprioni 算法的執行效率比經(jīng)典Aprioni算法的執行效率要高。關(guān)鍵詞:數據挖掘;Aprioni算法;優(yōu)化中囝分類(lèi)號:017文獻標識碼:A文章編號:1008- -7109(2013)02 -0064-05引言關(guān)聯(lián)規則挖掘是近年來(lái)數據挖掘研究中的一個(gè)熱門(mén)領(lǐng)域,它反映了事務(wù)數據庫中一個(gè)事務(wù)與其他事務(wù)之間的相互依存性和關(guān)聯(lián)性,關(guān)聯(lián)規則的目的就是為了挖掘出大量數據間隱藏的關(guān)聯(lián),方便決策者對事務(wù)進(jìn)行判斷和決策。為了發(fā)現事務(wù)數據庫中存在的相互關(guān)聯(lián)的重要規則,AgrawalR和SrikantRU12I于 1993年首先提出了挖掘顧客交易數據庫中項集間關(guān)聯(lián)規則的問(wèn)題，其核心方法是基于頻繁項集的遞推方法,并在1994年提出了關(guān)聯(lián)規則挖掘的快速算法;Park J. S.等人[)提出的DHP算法,縮減了事務(wù)數據庫的大小,減小了I/ 0操作時(shí)間，其效率比Apriori算法有了明顯的提高;Shirgaonkar S等人(4)提出了-種應用于大學(xué)圖書(shū)館的Apriori改進(jìn)算法,還有-些作者8.8分別提出了不同的Apriori 改進(jìn)算法。本文結合BBS輿情分析系統的案例,提出了三項改進(jìn)措施,優(yōu)化了Apriori 算法,提高了算法的執行效率。1 Apriori 算法的分析.1.1經(jīng)典Apriori算法的思想假設關(guān)聯(lián)規則挖掘的事務(wù)數據庫記為T(mén)DB = {T,T2, .. ,Tp,.. ,T,T=i,iz, .. ,小(1≤p≤n,),T .稱(chēng)為事務(wù),i稱(chēng)為項目。設I=( i.,,..... ,i.]是TDB中全體項目組成的集合。每一個(gè)事務(wù)T。是1中一組項目的集合,即T,CI,每個(gè)T。有一個(gè)唯- - 的標識符TID。設項集X是1中項目的集合,如果X中有k個(gè)項目,那么稱(chēng)X的長(cháng)度為k,或稱(chēng)為k項集。定義1:設和是項集,且x∩Y=O,規則X=>Y在TDB中具有支持度s就是TDB中包含X和Y的事務(wù)數與TDB中事務(wù)總個(gè)數之比，即:support(X=>Y )=support(XUY )=P(XUY)中國煤化工收稿日期:2013- 04-23作者簡(jiǎn)介:黃超君,男,寧波工程學(xué)院電信學(xué)院計科091班學(xué)生;指導老師:范劍汕.MYHCNMHG授?；痦椖?2012年度浙江省大學(xué)生科技創(chuàng )新活動(dòng)計劃(新苗人才計劃)項目(2012R422005)。黃超君范劍波:Aprioni算法的分析與改進(jìn)65定義2:設和是項集,且XY=,規則XY在TDB中具有置信度c就是TDB中同時(shí)包含和的事務(wù)數與TDB中包含的事務(wù)數之比,即:confdence(X=>Y)= sppor(8U)support(X)如果某個(gè)k項集{i,n,...,在TDB中出現的概率大于或等于最小支持度min.sup,則稱(chēng)為頻繁k項集,記作Fr。經(jīng)典Apriori算法的思想就是將發(fā)現關(guān)聯(lián)規則的過(guò)程分為兩步:第1步是通過(guò)迭代,找出源事務(wù)數據庫TDB中所有的頻繁項集,即支持度不低于用戶(hù)指定的最小支持度min._sup的所有頻繁項集;第2步是根據第1步找出的頻繁項集構造出置信度不低于用戶(hù)指定的最小置信度min._conf的強關(guān)聯(lián)規則。第1步工作的計算量和磁盤(pán)I/0量都很大,幾乎所有的關(guān)聯(lián)規則挖掘算法都是針對第1步提出的。經(jīng)典Apriori算法使用逐層搜索的迭代方法來(lái)產(chǎn)生頻繁項集,每--次迭代包括兩個(gè)步驟:如在第k次迭代中，首先根據頻繁k-1項集F-1通過(guò)自連接產(chǎn)生候選K項集Cr,在其中涉及連接步和剪枝步;然后對候選K項集C.根據最小支持度min. _sup 計數產(chǎn)生頻繁k項集Fr。迭代過(guò)程可以表示為:IC1F1C2F2C3F3C4F4。當然,剪枝步和算法終止的條件均要用到以下Apriori算法的性質(zhì)。性質(zhì):頻繁項集的所有非空子集也必須是頻繁的。1.2經(jīng)典Apriori算法的不足經(jīng)典Apriori算法能夠比較有效地產(chǎn)生頻繁項集,但也存在著(zhù)以下不足:(1)數據庫掃描的次數太多,每次尋找頻繁k項集(k=1,,n)時(shí)都需要掃描數據庫一次來(lái)求得候選項集的支持度,共需要掃描n次。如果遇到海量數據庫,或者n太大時(shí),耗時(shí)太長(cháng),難以滿(mǎn)足實(shí)際應用的需要。(2)經(jīng)典Apriori算法會(huì )產(chǎn)生大量的中間項集,由頻繁k-1項集F-1進(jìn)行連接生成的候選k項集Ck數量巨大,每一次迭代產(chǎn)生的C,是呈指數級別增長(cháng)的。由于C的規模巨大,所以驗證Ck中的項是不是F中的項需要占用算法很多的時(shí)間9。2 Apriori算法的改進(jìn)根據Apriori算法的性質(zhì)以及前面的分析，我們不難得出以下四個(gè)推論。推論1:一個(gè)非頻繁項集的任--超集必定也是非頻繁的。推論2:若候選k項集Cx中某個(gè)k項集的某個(gè)k-1項的子集不在頻繁k-1項集F中,則此k項集是非頻繁的。推論3:若某事務(wù)Tp不支持頻繁k-1項集F_中的每一項集,則T必不支持Cr中的任-項集。推論4:若某事務(wù)Tp不包含候選k-1項集C2-t中的任一項集,則也必不包含候選k項集C中的任一項集。根據前面的分析以及Apriori算法的性質(zhì)和推論,我們提出了Apriori算法的-些改進(jìn)。改進(jìn)1:如果事務(wù)數據庫是來(lái)源于某網(wǎng)站-段時(shí)間內帖子經(jīng)過(guò)分詞后的關(guān)鍵詞,則可以將每-一個(gè)帖子看作是一個(gè)事務(wù),每個(gè)帖子中的每個(gè)關(guān)鍵字看作是-一個(gè)項目’9。由于輿論分析有一定的特殊性,并不.是所有的詞都是敏感詞,所以可以設置--個(gè)完全不敏感詞庫來(lái)減少每個(gè)帖子中關(guān)鍵字的數量,也就是說(shuō)減少每個(gè)事務(wù)中的項目的數量。在候選1項集C.生成時(shí),其成員數可能較多,如果可以與一個(gè)完全不敏感詞庫匹配,則可以在C,中直接去除不可能是敏感詞的關(guān)鍵字,這樣能大大減少L和C成員的數量,從而提高算法執行的效率。中國煤化工改進(jìn)2:根據推論1和2可以得出:如果候選k項集Cr中某個(gè)CNMHG不在頻繁k-1項集F_中,則此k項集是非頻繁的,可以進(jìn)行剪枝。在剪枝的時(shí)nMmn的某個(gè)k6寧波工程學(xué)院學(xué)報2013年第2期項集的某個(gè)k-1項子集去掃描頻繁k-1項集F_,如果C中的頻繁項集過(guò)多,那也會(huì )增加掃描時(shí)間。我們可以將每次生成的候選k-1項集Cu分成頻繁k-1項集和非頻繁k-1項集,如果頻繁k-1項集個(gè)數多于非頻繁k-1項集,則在剪枝過(guò)程中掃描非頻繁k-1項集;如果頻繁k-1項集個(gè)數少于非頻繁k-1項集,則在剪枝過(guò)程中掃描頻繁k-1項集。改進(jìn)3:根據推論3和4,由于任何長(cháng)度為k的事務(wù)都不可能包含k+1項集,所以在對候選k項集C.計數生成頻繁k項集F.后,可以立即刪除長(cháng)度為k的事務(wù)。例如,對原始事務(wù)數據庫中C1計數生成F:后,可以立即刪除長(cháng)度為1的事務(wù),因為這些事務(wù)不會(huì )對后面的F2的生成起作用;在對C2計數生成F2后,可以立即刪除長(cháng)度為2的事務(wù),這樣事務(wù)數據庫就被壓縮了。此方法可以應用到以后的每- -次迭代中,從而能提高算法執行的效率。改進(jìn)和優(yōu)化的Apriori算法描述如下:(1)C1=find_ candidate_ 1-itemsets(TDB);//找 出所有的候選1項集C1(2)C' 1=match. _itemnsets(C1); //匹配完全不敏感詞庫,去除C1中不可能是敏感詞的關(guān)鍵字,//詳見(jiàn)改進(jìn)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-中二個(gè)成員f;和f進(jìn)行連接(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中的每一個(gè)k-1子集sIfs≠FthendeletecelseaddctoC}/進(jìn)行剪枝,詳見(jiàn)改進(jìn)2(14)for each transaction teTDB do(15){//掃描TDB,進(jìn)行事務(wù)壓縮和計數(16)TDB.=reduce(TDBr_); //從TDB_1中得到F_后,可以刪除長(cháng)度為k-1的事務(wù)而//形成TDB,詳見(jiàn)改進(jìn)方法3(17)C-=subset(C,t);//取出事務(wù)t中包含的候選項集(18)for each candidate c∈C // (18- -19)對每一個(gè)候選項集進(jìn)行計數(19)c.count++ }(20)Fr=[c∈Ck | c.count≥min_ sup} I1求出頻繁k項集F(21)}(22)returm F=U[F; /求出 F的并:3算法的實(shí)驗為了證明算法改進(jìn)以后執行的效率，需要分別對經(jīng)典Aproni中國煤化工行了比較和分析。本程序的測試平臺是WindowsXP,測試工具是elipse以HHCN MH C ;測試方法用Java語(yǔ)言編寫(xiě)了2個(gè)類(lèi),一個(gè)是改進(jìn)前的Apriori算法,--個(gè)是改進(jìn)后的Aprioni算法。事務(wù)數據庫黃超君范劍波:Aprion算法的分析與改進(jìn)6來(lái)源于某網(wǎng)站一段時(shí)間內帖子經(jīng)過(guò)分詞后的關(guān)鍵詞,每-一個(gè)帖子作為一個(gè)事務(wù),每個(gè)帖子中的每個(gè)關(guān)鍵字看作是一個(gè)項目9。在數據采集中,分別對每個(gè)帖子的關(guān)鍵詞數進(jìn)行了統計,得到事務(wù)長(cháng)度大約在6到18之間。算法執行的輸人值是一批事務(wù)，下面分4種情況分別進(jìn)行了測試。(1)事務(wù)數少、項目數少(50組事務(wù),事務(wù)平均長(cháng)度為6)表1事務(wù)數少、項目數少時(shí)間(秒)支持度0.20.30.40.50.6.7.8.9算法經(jīng)典Apriori0.101 0.086 0.074 0.067 0.064 0.06 0.057 0.055改進(jìn)的Apriori 0.078 0.07 0.065 0.06 0.054 0.048 0.044 0.043時(shí)間()0.12 T0.經(jīng)典Aprion0.080.060.04改進(jìn)的Aprion0.020.2 03 0.4 0.50.6 0.7 0809支持度圖1事務(wù)數少、項目數少(2)事務(wù)數多、項目數少(1000組事務(wù),事務(wù)平均長(cháng)度為6)表2事務(wù)數多、項目數少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改進(jìn)的Aprioni2.66 1.98 1.53 0.893 0.651 0.54 0.453 0.411時(shí)間國經(jīng)典Apnon0.2 0.3 0.4 0.5 06 0.7 0.8 09支持度圄2事務(wù)數多、項目數少(3)事務(wù)數少、項目數多(50組事務(wù),事務(wù)平均長(cháng)度為18)表3事務(wù)數少、項目數多0.2 0.3 0.4 0.50.6 0.7 0.8 0.9算法~經(jīng)典Apriori 0.174 0.151 0.142 0.132 0.125 0.122 0.112 0.108改進(jìn)的Aprioni 0.164 0.143 0.135 0.122 0.118 0.109 0.101 0.092「 時(shí)間(3)0。0.1641經(jīng)Apnon中國煤化工02030.o506070809支持度MYHCNM HG圍3事務(wù)數少項目數多8寧波工程學(xué)院學(xué)報2013年第2期(4)事務(wù)數多、項目數多(1000組事務(wù),事務(wù)平均長(cháng)度為18)表4事務(wù)數多、項目數多時(shí)間(秒)支持度0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9算法經(jīng)典Apriori 5.312 4.711 3.699 3.13 2.745 2.501 2.431 2.313改進(jìn)的Apriori 3.972 2.973 2.491 2.162 1.971 1.812 1.768 1.649時(shí)間(s)經(jīng)典Aprion，改進(jìn)的Apriori02 0.3 0.4 05 0.6 0.7 08 0.9支持度圍4事務(wù)數多、項目數多.4結束語(yǔ)從算法的實(shí)驗中可以看出,在事務(wù)數相同情況下,事務(wù)平均長(cháng)度越短,改進(jìn)算法的執行效率越高;在事務(wù)平均長(cháng)度相同的情況下,事務(wù)數越多,改進(jìn)算法的執行效率也越高?？傮w上,改進(jìn)Apriori算法的執行效率比經(jīng)典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ìn)算法研究[J].江西師范大學(xué)學(xué)報:自然科學(xué)版，2011, 35(5):498- -502.[6]梅成,周興斌.基于矩陣的Aprioni算法的優(yōu)化[J].南昌大學(xué)計算中心,2008.[7]朱慶,恰汗.合孜爾.一種改進(jìn)的Aprioni算法[J].計算機與數字工,2010,38(4):30 -32.[8]趙明茹,郭鍵,孫媛.基于線(xiàn)性鏈表存儲結構的Apriori 改進(jìn)算法[J].科學(xué)技術(shù)與工程,2011,11(23);5685- -5687.[9]任曉霞,李卓玲,周振柳. Aprioni 算法在BBS輿情分析系統中的應用[J].沈陽(yáng)工程學(xué)院學(xué)報(自然科學(xué)版),2010(7).中國煤化工MHCNMHG下轉第(78)頁(yè)寧波工程學(xué)院學(xué)報2013年第2期CDIO教育理念,構建了建筑工程類(lèi)專(zhuān)業(yè)的理論力學(xué)教學(xué)體系，提出了有效的教學(xué)模式、手段和方法,對提高學(xué)生學(xué)習理論力學(xué)的興趣具有積極意義,希望該做法對同行教學(xué)有所幫助。參考文獻:[1]查建中,何永汕、中國工程教育改革的三大戰略[M].北京:北京理工大學(xué)出版社,2009(1).[2]林建.面向“卓越工程師”培養的課程體系和教學(xué)內容改革[].高等工程教育研究,2011(5).[3]鐘金明,李苑玲.基于CDI0理念的工程教育實(shí)踐教學(xué)改革初探[J].實(shí)驗科學(xué)與技術(shù),2009(12).[4]李望國,張曉東。創(chuàng )新構建基于CDI0工程教育理念“3+1"人才培養模式的研究[J].廣東白云學(xué)院學(xué)刊,2011,18(1).[5]胡志剛,任勝兵,吳斌.構建基于CDIO理念的一體化課程教學(xué)模式[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)頁(yè)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