Apriori算法的優(yōu)化方法

第19卷第g期計算機技術(shù)與發(fā)展Vol.19 No.6june 20092009年6月COMPUTER TECHNOILO;Y ANI)IEVFEL( PMENTJuneApriori算法的優(yōu)化方法|:陳偉(淮南聯(lián)合大學(xué)計算機系,安徽淮南232038)摘要:關(guān)聯(lián)規則是數據挖掘的主要技術(shù)之一,是指從-一個(gè)大型的數據集中發(fā)現有趣的關(guān)聯(lián)或相關(guān)關(guān)系,即從數據集中識別出頻繁項集,然后再利用這些頻繁集創(chuàng )建描述關(guān)聯(lián)規則的過(guò)程。頻繁項集挖掘是關(guān)聯(lián)規則挖掘的主要步驟,在頻繁項集挖掘中,需要大量進(jìn)行兩個(gè)操作:判斷兩個(gè)k -項集是否是前k- 1項相同且最后一項不同，即連接步;判斷一個(gè)項集是否為另-個(gè)項集的子集,即剪枝步,通過(guò)臧少連接操作和剪枝操作的循環(huán)次數,以此來(lái)提高Aprioni算法的效率。關(guān)鍵詞:關(guān)聯(lián)規則;Aprion算法;瀕繁項集中圍分類(lèi)號: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引言重要、最活躍的研究?jì)热?。在A(yíng)prioni算法中需要大量進(jìn)行這樣兩個(gè)操作:判-般地,關(guān)聯(lián)規則挖掘是指從一個(gè)大型的數據集斷兩個(gè)k -項集中是否前k- l項相同且最后一項不(Dataset)中發(fā)現有趣的關(guān)聯(lián)(Association)或相關(guān)(Cor-同,即連接步;判斷- -個(gè)k-項候選集的所有k-1子relaion)關(guān)系,即從數據集中識別出頻繁出現的屬性值集是否都是k -項頻繁集,即剪枝步。假定事務(wù)數據庫集(Sets of Attribute Values) ,也稱(chēng)為頻繁項集(Fre-中各記錄的項目均已按字典排序?？梢岳庙椉gquent Itermsets, 簡(jiǎn)稱(chēng)頻繁集),然后再利用這些頻繁集有序的特點(diǎn),從減少算法中這兩個(gè)操作的執行次數的創(chuàng )建描述關(guān)聯(lián)規則的過(guò)程。角度來(lái)達到優(yōu)化算法的目的。關(guān)聯(lián)規則可形式化定義為:設1= {i,i,.",iml 是由m個(gè)不同的項組成的集合。給定一一個(gè)事務(wù)數據庫D,其中每- -個(gè)事務(wù)T是I1關(guān)聯(lián)規 則的簡(jiǎn)單描述關(guān)聯(lián)規則是描述數據庫中一組數據項之間的某種中-組項的集合,即T∈I,T有一個(gè)唯一的標示符潛在關(guān)系的規則。關(guān)聯(lián)規則形式簡(jiǎn)潔、易于解釋和理TID。若項集X∈I且XS T,則事務(wù)T包含項集X。解,并可以有效地捕捉數據間的重要關(guān)系,從大型數據關(guān)聯(lián)規則是形如X => Y的蘊涵式,其中XS .庫中挖掘關(guān)聯(lián)規則問(wèn)題已成為數據挖掘中最成熟、最T,YST,并且X∩Y= 0,如果D中事務(wù)包含X∪Y的百分比為S .則稱(chēng)s為關(guān)聯(lián)規則X => Y的支持收稿日期:2008-09-21;修回日期:2009-01 -04度,中國煤化工包含X的事務(wù)同時(shí)基金項目:2007年安徽省高校青年教師資助計劃項目(200g1197)也包YHCN M H G關(guān)聯(lián)規則X=> Y作者簡(jiǎn)介:陳偉(1975 - ),女,安徽六安人,講師，研究方向為數據的置信度,它是條件概率P(Y/X)。習慣上將關(guān)聯(lián)規庫敷據挖掘。則表示為X => Y(S% ,C% )。關(guān)聯(lián)規則的發(fā)現任務(wù)第6期陳偉:Apriori 算法的優(yōu)化方法81或問(wèn)題就是在事務(wù)數據庫D)中找出所具有用戶(hù)給定選k-項集*/的最小支持度閾值(min.sup)和最小置信度閾值(4)For all transactionst∈D do begin(min. cof) 的關(guān)聯(lián)規則,即這些關(guān)聯(lián)規則的支持度和置(5)C, = subset(C;,t);/*候選集C中提取包含信度分別不小于最小支持度和最小置信度。在事務(wù)t中的候選k-項集*/如果項集的支持度滿(mǎn)足最小支持度min. sup,則(6)For all CandidatesC∈C, do它稱(chēng)之為頻繁項集(Frequent Itemse)川。(7)C.Count ++;所以關(guān)聯(lián)規則的挖掘- -般分為以下兩個(gè)過(guò)程:(8)End(1)找出所有的頻繁項集,也就是找出事務(wù)數據庫(9)L={C∈C | C.Conut≥min. supl;中所有大于等于用戶(hù)指定的最小支持度的數據項集,(10)End即具有最小支持度的數據項集。(11)retumL = ULk;(2)由頻繁項集產(chǎn)生強關(guān)聯(lián)規則:根據定義,這些函數Apriori. gen按如下方式分兩步進(jìn)行工作:規則必須滿(mǎn)足最小支持度和最小置信度?！襁B接步在上述兩個(gè)步驟中,第一步是挖掘關(guān)聯(lián)規則的關(guān)Procedure aprioni_ gen( Lk-1 ;min. sup)鍵步驟。關(guān)聯(lián)規則挖掘的總體性能由該步驟的性能所1)for each itemset L∈L2-1 .決定。所以,現有的研究都集中在第-一個(gè)步驟上 ,也就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{關(guān)聯(lián)規則挖掘有多種分類(lèi)方法:單維、單層和布爾4)C= L1田L(fēng)2;關(guān)聯(lián)規則挖掘。它們都是最簡(jiǎn)單形式的關(guān)聯(lián)規則挖5)if has- infrequent. subset(C, L-1)then掘,最著(zhù)名、最有影響的關(guān)聯(lián)規則挖掘算法是R. A-6)delete C;grawal等人提出的Apriori算法,該算法是一種挖掘布7)else add C to C;爾關(guān)聯(lián)規則頻繁項集的算法。算法基于頻繁項集性質(zhì)8)}的先驗知識,使用--種稱(chēng)為邏層搜索的迭代方法來(lái)找9)reum Ck;出所有的頻繁項集?！窦糁Σ紸prioni算法通過(guò)對數據庫D的多趟掃描來(lái)發(fā)現Procedure has- infrequent. sube(C,L-)所有的頻繁項目集.在第一趟掃描數據庫時(shí),對項集11)for each(k- 1)- subsetsof C中的每一個(gè)數據項計算其支持度,確定出滿(mǎn)足最小支2)ifs氏L2-1 then持度的頻繁1項集的集合L1,然后,L用于找頻繁23)retum true;項集的集合L2, 如此下去....在后續的第k趟掃描4)retumn false;中,首先以k- 1趟掃描中所發(fā)現的含k- 1個(gè)元素的C,中的成員可以是頻繁的也可以是不頻繁的,但頻繁項集的集合La-1 為基礎,生成所有新的候選項目所有的頻繁k-項集都包含在C中。如果確定C中每集Ck(Candidate ltemsets) ,即潛在的頻繁項目集,然后個(gè)候選的計數,從而確定L,,那么涉及的計算量就很掃描數據庫D,計算這些候選項目集的支持度,最后從大。為壓縮搜索空間,可以用Aprioni性質(zhì):任何非頻繁候選集Ck中確定出滿(mǎn)足最小支持度的頻繁k項集的的(k- l)-項集都不可能是頻繁k -項集的子集。因集合Lx,并將L,作為下一趟掃描的基礎。重復上述過(guò)此,如果一個(gè)候選k -項集的(k- l)-項集不在L2-1程直到再也發(fā)現不了新的頻繁項目集(2]。中,則該候選也不可能是頻繁的,從而可以從C中刪Aprioni算法的基本描述如下;除。輸入:事務(wù)數據庫D; .下面來(lái)舉例說(shuō)明以上闡述的過(guò)程。設事務(wù)數據庫.最小支持度計數閾值min. sup。D,見(jiàn)表輸出:D中的頻繁項集L。中國煤化工,Apriori 算法執行(1)L1 = find. frequent- 1 - itemses(D); .過(guò)程TMYHCNMHG(2)For(k = 2;Lx-1≠0;k + +)do begin(1)算法第一次掃描數據庫,確定候選1-項集及(3)Ck = aprioni- gen( Lx-1,min. sup);/*生成候各項集的支持度計數C;,如圖1所示?！?2.計算機技術(shù)與發(fā)展第19卷表1事務(wù)數據庫3減少連 接步驟的執行次數TIDItem由于已經(jīng)設定各事務(wù)項目按字典排序,其中的任1,3.4一個(gè)k-項集L,有L[1]< L[2]<.< L[k]。所以2,3,5對于兩個(gè)(k-1)-項頻繁集L。和L6(a< b),若L。和1,2,3,5L,不符合連接條件,則La 與Lo之后的所有(k-1)-2,5項集都不能滿(mǎn)足連接條件。所以只要La與L。不能連(2)利用L田L(fēng)來(lái)產(chǎn)生候選2-項集C2,由C2接,就不需要再判斷L。與L。之后的所有(k-1)-項確定頻繁2-項集,如圖2所示。集是否能連接,從而減少循環(huán)的次數[3.4]。改進(jìn)算法:(3) 利用L2田L(fēng)2進(jìn)行連接操作,獲得候選3-項Procedure aprioi. gen (L_-1 ;minL sup)集C3= {2,3,5|。根據Apriorni性質(zhì):一個(gè)頻繁項集的for each itemnetL?！蔐a-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產(chǎn)生1頻繁項集行次數L:頻繁項集對于--個(gè)k-項候選集支持度計數的任意一個(gè)子集(k-1)-項與最小支持度集L。和一個(gè)(k-l)-項頻繁由L產(chǎn)生候計數比較后的{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}一個(gè)(k-l)-項頻繁集比較,如此下去;若La[i]<{2.5}L[i],由于各事務(wù)項目按字{3, 5}典排序,則L。與L,后的所有圍2產(chǎn)生2頻繁項集(k- l)-項頻繁集都不會(huì )相G:候選項集同。所以只要L。[i]< L6[i], .與最小支持度。計數比較后的「就不需要再判斷L。是否與L。選3-項集3-頻繁項集后的(k- 1)一項集相同。由(2.3, 5}(2. 3, 5}此就能判定La 不是頻繁項.集。由Apriori算法性質(zhì):頻繁困3產(chǎn)生3頻繁項集項集的所有非空子集都必須是頻繁的,所以該k -項(4)利用L3田L(fēng)3進(jìn)行連接操作得到C4,根據候選中國煤化工。該步操作中大大Apriori性質(zhì)可知C = 0 ,算法至此結束。在A(yíng)prioni算法中連接步和剪枝步是頻繁操作的減少|(zhì)YHC N M H G否是頻繁項集的執兩個(gè)步驟,以下就從這兩個(gè)步驟人手,來(lái)提高算法的效行次數一”。改進(jìn)的算法為:Procedure has infrequent. subset(C,La-1)率。第6期陳偉:Apriuni 算法的優(yōu)化方法， 83for eachL6∈L&-16結束語(yǔ)fL。CC then//L[iJ∈L。 andLo[li]∈L6以上的改進(jìn)方法用VFP6.0已進(jìn)行了驗證。關(guān)聯(lián)lif (L。[i門(mén)]= L[i])then規則的應用很廣泛,而它的經(jīng)典算法Aprioni 算法中的{ La∈L-;break;|頻繁項集求解是耗時(shí)最多的工作,那么提高了頻繁項else i(L[i]> Lo[i])then集的求解速度,也就加快了關(guān)聯(lián)規則的求解速度。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下面舉例說(shuō)明8.9]。the ACM SIGMOD Conference on Manageament of data(ACMSIGMOD'93). Washington, USA:[s. n. ],1993:207 - 216.(1)連接步:假設有6個(gè)2-項頻繁集:L1 = {1,[3] 袁萬(wàn)蓮,鄭誠,翟明清. -種改進(jìn)的Aprioni算法[J].計算2},L2= {1,3}, Lg= {1,5},L4= {2,3}, Ls= {2,機技術(shù)與發(fā)展2008,18(5):52 -53.4},L6= {2,5}。L1和L2、L1和L3滿(mǎn)足連接條件,可[4]何中勝 ,莊燕濱.基于A(yíng)priori&Fp - growth的頻繁項集發(fā)以連接。L和L4不滿(mǎn)足連接條件,不能連接。依照改現算法[J].計算機技術(shù)與發(fā)展2008,18(7):46 -47.進(jìn)的算法,L1和L4之后的所有頻繁項集都不滿(mǎn)足連[5]吳志丹， 趙大宇,唐恒永.一種改進(jìn)的關(guān)聯(lián)規則挖掘算法接條件,從而減少了L1和Ls、L1和L6的判斷。[].沈陽(yáng)師范大學(xué)學(xué)報:自然科學(xué)版2006(3):258 - 259.(2)剪枝步:假設有一一個(gè)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個(gè)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] 胡吉明,鮮學(xué)豐.挖掘關(guān)聯(lián)規則中Aprioni算法的研究與改找C,首先C1和L1比較:C[1]= L[1],C[2] =進(jìn)[J].計算機技術(shù)與發(fā)展,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],接著(zhù)Cr和L2比較:C2[1]< L2[1],按照改進(jìn)allel and Distributed Information Systems. Miami Beach, FL:[s.n. ],1996:31 -44.的算法,以后的都不用比較,也就確定該候選項集C9] 郭有強.一種高效的關(guān)聯(lián)規則維護算法研究與實(shí)現[J].計的子集C2不是頻繁項集,由Aprioni算法性質(zhì)確定該候算機技術(shù)與發(fā)展,2007,17(10);123- 126.選項集C也不是頻繁項集,所以刪除它。(上接第79頁(yè))[28] Osher s, Sethian J. Fronts propegating with curvaturede分割方法[J].中國圖象圖形學(xué)報, 2006, 11(9): 1312 -pendespeed:algorithms based on the HaniltonJacobi formula-1316.tion[J]. Joumnal of Computational Physics, 1988,79(1):12 -[34]秦昆,徐敏.基于云模型和FCM聚類(lèi)的遙感囝像分割l9.方法[J].地球信息科學(xué),2008,10(3):302 - 307.[29]陳波,賴(lài)劍煌,馬建華.一種耦合的活動(dòng)輪廓模型及其在[35]鄭洪英.數據挖掘聚類(lèi)算法的分析和應用研究[D].重慶:圖像分割中的應用[].中國圖象圖形學(xué)報2007,12(3):重慶大學(xué),2002.444- 449.[36]邵銳,巫兆聰,鐘世明.基于粗糙集的K-均值聚類(lèi)算法[30]謝勤彬.羅代升.基于改進(jìn)活動(dòng)輪廓模型的超聲圖像分割在圖像分割中的應用[J].測繪信息與工程,2005, 30(5):1[J].科學(xué)技術(shù)與工程,2007,7(8):1638 - 1641.[31] 陳波,賴(lài)劍煌. 用于圖像分割的話(huà)動(dòng)輪廓模型綜述[J]. [37] 許海洋.王萬(wàn)森基于SOM神經(jīng)網(wǎng)和K-均值算法的圖像中國圖象囝形學(xué)報,2007,12(1):11 -20.中國煤化工:1):38-40.[32] Bezdek J C. Pattem reognion with fuzzy objecive function[38]!聚類(lèi)神經(jīng)網(wǎng)絡(luò )的圖像algonithms [M]. Norwell, MA, USA: Kluwer AcademicYHC N M H S320)93-95.Publishers, 1981.[39]薛嵐燕,鄭勝林,潘保昌,等.基于神經(jīng)網(wǎng)絡(luò )的灰度圖像閼[33劉華軍,任明武,楊靜宇.-種改進(jìn)的基于模糊聚類(lèi)的圖像值分割方法[J].廣東工業(yè)大學(xué)學(xué)報2005,22(4):67 - 72.