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