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