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

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

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

1引言

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

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

2Apriori算法

2.1基本概念

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

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

規(guī)則XÞY在交易數(shù)據(jù)庫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}|。給定一個交易集D，挖掘關(guān)聯(lián)規(guī)則就是找出支持度和置信度分別大于用戶給定的最小支持度(minsup)和最小置信度(minconf)的關(guān)聯(lián)規(guī)則。

2.2基本思想

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

①連接：Lk-1進行自連接運算,生成候選k-項集的集合（記為：Ck）。所有的頻繁k-項集都包含在Ck集合中。

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

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

2.3算法分析

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

3改進的Apriori算法

3.1改進思想

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

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

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

①連接：設兩個(k-1)-項集：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項相等，即：Xk-1[k-2]≡Yk-1[k-2]，則(k-1)-項集連接：L’k-1(i)∞L’k-1(j)=<Xk-1

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

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

3.2改進的算法描述

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

輸出：D中的頻繁項目集L

算法描述：

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

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

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ù)據(jù)庫D表1所示，最小支持數(shù)minSupNum=4，運行改進的算法的過程如圖所示：

4總結(jié)

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

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

參考文獻

[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算法改進的關(guān)聯(lián)規(guī)則提取算法.計算機與數(shù)字工程.2006,34(4):48-51,55

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