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