導語：關聯規則挖掘算法探究論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

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

關鍵字關聯規則，支持度，置信度，Apriori

1引言

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

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

2Apriori算法

2.1基本概念

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

關聯規則是形如XÞY的蘊涵式，這里XÌI,YÌI，并且XÇY=F。

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

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

2.2基本思想

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

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

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

通過上述的迭代過程，可以發現項目集I在給定數據庫D中滿足最小支持度的所有頻繁項目集。

2.3算法分析

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

3改進的Apriori算法

3.1改進思想

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

數據庫D中每個交易T都有一個唯一的編號TID。定義K-項集Rk=<Xk，TIDS(Xk)>，其中Xk=(ij1,ij2,…,ijk)，ij1,ij2,…,ijkÎI，j1<j2<…<jk，TIDS(Xk)是數據庫中所有包含Xk的交易T的編號TID的集合，即為：TIDS(Xk)={TID:XkÍT，<TID,T>ÎD}。根據上面的定義k-項目集Rk的支持度可以表示為：support(Rk)=|TIDS(Xk)|/|D|=|{TID:XkÍT，<TID,T>ÎD}|/|D|。Rk的支持數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；否則，不進行連接運算，因為產生的結果不是重復，就是非頻繁項目集，這樣可減少計算量。

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

3.2改進的算法描述

輸入：數據庫D，最小支持數minSupNum

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

算法描述：

①L’1=findFrequentOneItemSets(D);//掃描數據庫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例舉

設數據庫D表1所示，最小支持數minSupNum=4，運行改進的算法的過程如圖所示：

4總結

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

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

參考文獻

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

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