導(dǎo)語：關(guān)聯(lián)規(guī)則挖掘算法探究論文一文來源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要Apriori算法是發(fā)現(xiàn)頻繁項(xiàng)目集的經(jīng)典算法，但是該算法需反復(fù)掃描數(shù)據(jù)庫(kù)，因此效率較低。本文介紹了Apriori算法的思想，并分析了該算法的性能瓶頸。在此基礎(chǔ)上，針對(duì)Apriori算法提出了一種改進(jìn)方法，該方法采用轉(zhuǎn)置矩陣的策略，只掃描一次數(shù)據(jù)庫(kù)即可完成所有頻繁項(xiàng)目集的發(fā)現(xiàn)。與其他經(jīng)典的算法相比，本文提出的算法在項(xiàng)目集長(zhǎng)度較大時(shí)，性能明顯提高。

關(guān)鍵字關(guān)聯(lián)規(guī)則，支持度，置信度，Apriori

1引言

關(guān)聯(lián)規(guī)則挖掘就是在海量的數(shù)據(jù)中發(fā)現(xiàn)數(shù)據(jù)項(xiàng)之間的關(guān)系，是數(shù)據(jù)挖掘領(lǐng)域中研究的熱點(diǎn)問題。1993年Agrawal等人[1]首先提出了交易數(shù)據(jù)庫(kù)中不同商品之間的關(guān)聯(lián)規(guī)則挖掘，并逐漸引起了專家、學(xué)者的重視。關(guān)聯(lián)規(guī)則挖掘問題可以分為：發(fā)現(xiàn)頻繁項(xiàng)目集和生成關(guān)聯(lián)規(guī)則兩個(gè)子問題，其中發(fā)現(xiàn)所有的頻繁項(xiàng)目集是生成關(guān)聯(lián)規(guī)則的基礎(chǔ)。近年來，發(fā)現(xiàn)頻繁項(xiàng)目集成為了關(guān)聯(lián)規(guī)則挖掘算法研究的重點(diǎn)，在經(jīng)典的Apriori算法的基礎(chǔ)上提出里大量的改進(jìn)算法。Savasere等[2]設(shè)計(jì)了基于劃分(partition)的算法，該算法可以高度并行計(jì)算，但是進(jìn)程之間的通信是算法執(zhí)行時(shí)間的主要瓶頸；Park等[3]通過實(shí)驗(yàn)發(fā)現(xiàn)尋找頻集主要的計(jì)算是在生成頻繁2-項(xiàng)集上，利用這個(gè)性質(zhì)Park等引入雜湊（Hash）技術(shù)來改進(jìn)產(chǎn)生頻繁2-項(xiàng)集的方法，該算法顯著的提高了頻繁2-項(xiàng)集的發(fā)現(xiàn)效率；Mannila等[4]提出：基于前一遍掃描得到的信息，對(duì)此仔細(xì)地作組合分析，可以得到一個(gè)改進(jìn)的算法了。針對(duì)Mannila的思想Toivonen[5]進(jìn)一步提出：先使用從數(shù)據(jù)庫(kù)中抽取出來的采樣得到一些在整個(gè)數(shù)據(jù)庫(kù)中可能成立的規(guī)則，然后對(duì)數(shù)據(jù)庫(kù)的剩余部分驗(yàn)證這個(gè)結(jié)果。Toivonen的算法相當(dāng)簡(jiǎn)單并顯著地減少了I/O代價(jià)，但是一個(gè)很大的缺點(diǎn)就是產(chǎn)生的結(jié)果不精確，存在數(shù)據(jù)扭曲(dataskew)。

上述針對(duì)經(jīng)典Apriori算法的改進(jìn)算法在生成頻繁項(xiàng)目集時(shí)都需要多次掃描數(shù)據(jù)庫(kù)，沒有顯著的減少I/O的代價(jià)。本文在分析了經(jīng)典的Apriori算法的基礎(chǔ)上，給出了一種改進(jìn)的方法，該方法采用轉(zhuǎn)置矩陣的策略，只掃描一次數(shù)據(jù)庫(kù)即完成頻繁項(xiàng)目集的發(fā)現(xiàn)，在項(xiàng)目集長(zhǎng)度較大時(shí)，性能明顯提高。

2Apriori算法

2.1基本概念

設(shè)I={i1,i2,…,im}是二進(jìn)制文字的集合，其中的元素稱為項(xiàng)(item)。定義交易(transaction)T為項(xiàng)的集合，并且TÍI，定義D為交易T的集合。設(shè)X是I中若干項(xiàng)的集合，如果XÍT，那么稱交易T包含X。項(xiàng)目集中包含項(xiàng)的個(gè)數(shù)成為項(xiàng)目集長(zhǎng)度。

關(guān)聯(lián)規(guī)則是形如XÞY的蘊(yùn)涵式，這里XÌI,YÌI，并且XÇY=F。

規(guī)則XÞY在交易數(shù)據(jù)庫(kù)D中的支持度（support）是交易集合中包含X和Y的交易數(shù)與所有交易數(shù)之比，記為support(XÞY)，即support(XÞY)=|{T:XÈYÍT，TÎD}|/|D|。

規(guī)則XÞY在交易集中的置信度（confidence）是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比，記為confidence(XÞY)，即confidence(XÞY)=|{T:XÈYÍT，TÎD}|/|{T:XÍT，TÎD}|。給定一個(gè)交易集D，挖掘關(guān)聯(lián)規(guī)則就是找出支持度和置信度分別大于用戶給定的最小支持度(minsup)和最小置信度(minconf)的關(guān)聯(lián)規(guī)則。

2.2基本思想

1994年Agrawal等人在項(xiàng)目集格空間理論的基礎(chǔ)上提出了用于發(fā)現(xiàn)頻繁項(xiàng)目集的Apriori算法。該算法采用“逐層搜索”的迭代方法，用k-項(xiàng)集生成(k+1)-項(xiàng)集。首先，掃描數(shù)據(jù)庫(kù)計(jì)算出頻繁1-項(xiàng)集的集合（記為：L1）；然后，執(zhí)行下面的迭代過程計(jì)算頻繁k-項(xiàng)集，直到生成頻繁k-項(xiàng)集的集合（記為：Lk）為空：

①連接：Lk-1進(jìn)行自連接運(yùn)算,生成候選k-項(xiàng)集的集合（記為：Ck）。所有的頻繁k-項(xiàng)集都包含在Ck集合中。

②剪枝：①生成的Ck是Lk的超集，掃描數(shù)據(jù)庫(kù)計(jì)算Ck中每個(gè)候選項(xiàng)目集的支持度，支持度大于用戶給定最小支持度的候選k-項(xiàng)目集就是頻繁k-項(xiàng)目集。

通過上述的迭代過程，可以發(fā)現(xiàn)項(xiàng)目集I在給定數(shù)據(jù)庫(kù)D中滿足最小支持度的所有頻繁項(xiàng)目集。

2.3算法分析

Apriori算法在執(zhí)行“連接-剪枝”的迭代過程中，需要多次掃描數(shù)據(jù)庫(kù)，如果生成的頻繁項(xiàng)目集中含有10-項(xiàng)集，則需要掃描10遍數(shù)據(jù)庫(kù)，增大了I/O負(fù)載。并且在迭代過程中，候選項(xiàng)目集合Ck是以指數(shù)速度增長(zhǎng)的，Lk-1自連接會(huì)產(chǎn)生大量的候選k-項(xiàng)目集，例如有104個(gè)1-項(xiàng)集，自連接后就可以產(chǎn)生大約107個(gè)候選2-項(xiàng)集。這些都嚴(yán)重影響了Apriori算法的效率。

3改進(jìn)的Apriori算法

3.1改進(jìn)思想

Apriori算法在迭代過程中多次掃描數(shù)據(jù)庫(kù)和產(chǎn)生大量的候選項(xiàng)目集形成了算法的性能瓶頸。為了提高算法的效率本文進(jìn)行如下改進(jìn)：

數(shù)據(jù)庫(kù)D中每個(gè)交易T都有一個(gè)唯一的編號(hào)TID。定義K-項(xiàng)集Rk=<Xk，TIDS(Xk)>，其中Xk=(ij1,ij2,…,ijk)，ij1,ij2,…,ijkÎI，j1<j2<…<jk，TIDS(Xk)是數(shù)據(jù)庫(kù)中所有包含Xk的交易T的編號(hào)TID的集合，即為：TIDS(Xk)={TID:XkÍT，<TID,T>ÎD}。根據(jù)上面的定義k-項(xiàng)目集Rk的支持度可以表示為：support(Rk)=|TIDS(Xk)|/|D|=|{TID:XkÍT，<TID,T>ÎD}|/|D|。Rk的支持?jǐn)?shù)supNum(Rk)=support(Rk)*|D|=|TIDS(Xk)|。L’k表示k-項(xiàng)集的集合。

改進(jìn)的Apriori算法依然采用“逐層搜索”的迭代方法，迭代過程的“連接-剪枝”運(yùn)算定義如下：

①連接：設(shè)兩個(gè)(k-1)-項(xiàng)集：L’k-1(i)=<Xk-1，TIDS(Xk-1)>ÎL’k-1，L’k-1(j)=<Yk-1，TIDS(Yk-1)>ÎL’k-1，i<j。如果Xk-1和Yk-1的前k-2項(xiàng)相等，即：Xk-1[k-2]≡Yk-1[k-2]，則(k-1)-項(xiàng)集連接：L’k-1(i)∞L’k-1(j)=<Xk-1

∪Yk-1,TIDS(Xk-1)∩TIDS(Yk-1)>=<Xk，TIDS(Xk)>=RkÎL’k；否則，不進(jìn)行連接運(yùn)算，因?yàn)楫a(chǎn)生的結(jié)果不是重復(fù)，就是非頻繁項(xiàng)目集，這樣可減少計(jì)算量。

②剪枝：計(jì)算k-項(xiàng)集的支持?jǐn)?shù)，根據(jù)上面的定義supNum(Rk)=|TIDS(Xk)|，該計(jì)算過程不需要再掃描數(shù)據(jù)庫(kù)，避免了I/O操作，提高了算法的效率。如果supNum(Rk)≥minSupNum，則<Xk,|TIDS(Xk)|>ÎL；否則，從集合L’k中刪除Rk。

3.2改進(jìn)的算法描述

輸入：數(shù)據(jù)庫(kù)D，最小支持?jǐn)?shù)minSupNum

輸出：D中的頻繁項(xiàng)目集L

算法描述：

①L’1=findFrequentOneItemSets(D);//掃描數(shù)據(jù)庫(kù)D生成1-項(xiàng)集的集合L’1。

②foreachOneItemSet<X1,TIDS(X1)>ÎL’1//生成頻繁1-項(xiàng)集的集合

if(|TIDS(X1)|≥minSupNum)

L=L∪{<X1,|TIDS(X1)|>};

else

L’1=L’1-{<X1,TIDS(X1)>};

③for(k=2;L’k-1≠Ф;k++)

L’k=L’k-1∞L’k-1;

Foreachk_ItemSet<Xk,TIDS(Xk)>ÎL’k

if(|TIDS(Xk)|≥minSupNum)

L=L∪{<Xk,|TIDS(Xk)|>};

else

L’k=L’k-{<Xk,TIDS(Xk)>};

④returnL;

3.3例舉

設(shè)數(shù)據(jù)庫(kù)D表1所示，最小支持?jǐn)?shù)minSupNum=4，運(yùn)行改進(jìn)的算法的過程如圖所示：

4總結(jié)

改進(jìn)的Apriori算法，只是在生成L’1時(shí)進(jìn)行了一次數(shù)據(jù)庫(kù)掃描，在之后的迭代過程中不需要掃描數(shù)據(jù)庫(kù)。與文獻(xiàn)2，3，4，5中提出的改進(jìn)算法相比，使用本文提出的算法大大降低了I/O負(fù)載，使得頻繁項(xiàng)目集的發(fā)現(xiàn)速度大大提高，尤其是在項(xiàng)目集長(zhǎng)度較大的情況下。算法的迭代過程不需要復(fù)雜的計(jì)算，項(xiàng)目集連接僅僅使用集合的并、交運(yùn)算即可完成，使得該算法易于實(shí)現(xiàn)，相信該算法具有一定的理論與實(shí)用價(jià)值。

但是該算法也有不足：為了減少I/O負(fù)載，要求在第一次掃描時(shí)把所有的信息裝入內(nèi)存，雖然本算法對(duì)數(shù)據(jù)庫(kù)進(jìn)行編碼，以二元組的形式存儲(chǔ)項(xiàng)集，但是數(shù)據(jù)挖掘都是基于海量數(shù)據(jù)的，因此，算法運(yùn)行時(shí)需要大量?jī)?nèi)存，對(duì)此將在今后的研究中進(jìn)行改進(jìn)。

參考文獻(xiàn)

[1]R.Agrawal,T.Imielinski,andA.Swami.Miningassociationrulesbetweensetsofitemsinlargedatabases.ProceedingsoftheACMSIGMODConferenceonManagementofdata,pp.207-216,1993

[2]A.Savasere,E.Omiecinski,andS.Navathe.Anefficientalgorithmforminingassociationrulesinlargedatabases.Proceedingsofthe21stInternationalConferenceonVerylargeDatabase,1995

[3]J.S.Park,M.S.Chen,andP.S.Yu.Aneffectivehash-basedalgorithmforminingassociationrules.ProceedingsofACMSIGMODInternationalConferenceonManagementofData,pages175-186,SanJose,CA,May1995

[4]H.Mannila,H.Toivonen,andA.Verkamo.Efficientalgorithmfordiscoveringassociationrules.AAAIWorkshoponKnowledgeDiscoveryinDatabases,1994,pp.181-192

[5]H.Toivonen.Samplinglargedatabasesforassociationrules.Proceedingsofthe22ndInternationalConferenceonVeryLargeDatabase,Bombay,India,September1996

[6]羅可,賀才望.基于Apriori算法改進(jìn)的關(guān)聯(lián)規(guī)則提取算法.計(jì)算機(jī)與數(shù)字工程.2006,34(4):48-51,55

[7]蔡偉杰，楊曉輝等.關(guān)聯(lián)規(guī)則綜述.計(jì)算機(jī)工程.2001,27(5):31-33,49