分布式環境基于相似度的關聯規則挖掘模型的研究

摘要：介紹了關聯規則挖掘的基本原理和方法，詳細分析了分布式關聯規則挖掘算法并給出其模型；提出一種充分考慮數據源異構性、基于相似度的的分布式數據挖掘方法。實驗證明該模型提高了挖掘的準確率。

關鍵詞：數據挖掘；關聯規則；相似度；分布式系統

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2008)03－0695－03

在分布式技術處理日益成熟的今天，網絡數據的處理量也在不斷增長。由于這些數據很多時候都是分散在不同的地方，挖掘大量分布式數據就需要研究出一種有效的分布式算法。分布式數據庫系統關聯規則的挖掘有其自身的特點，對其進行關聯規則的挖掘需要專門的挖掘算法來實現。國際上的數據挖掘研究者已經對此作了一些研究。目前已有的數據挖掘算法包括Kargupta等人[1]提出的集體數據挖掘、Yamanishi[2]提出的分布式協作貝葉斯學習策略、Cheung等人[3]提出的分布式數據庫中的有效挖掘關聯規則。這些已有的DDM技術還有許多局限性：雖然目前的很多DDM(distributed data mining)技術使用各種標準和方法，將來自分布式數據源的原模型盡量優化，而且在同構數據挖掘方面已經相當成熟，但對于分布式數據源的異構性仍然不夠成熟。本文提出一種基于相似度的分布式關聯規則挖掘模型作為新的數據挖掘模型。其基本思想是：充分考慮到分布式數據的異構性，首先通過計算相似度將得到的數據集按照相似度進行分組；然后在分布式環境下使用已有的關聯規則挖掘方法得到更加有效準確的關聯規則。

1關聯規則挖掘的基本概念及改進的apriori算法

1．1關聯規則挖掘

關聯規則挖掘就是從大量的數據中挖掘出有價值的描述數據項之間相互聯系的有關知識。它是數據挖掘中最基礎也是最流行的一種數據挖掘方法。假設I={I1，I2，…，Im}是一組數據集，對于給定的事務數據庫D，其中的每個事務對應一個惟一的事務標志和一組項目集itemsets（Iitemsets）。關聯規則是如下形式的一種蘊涵：XY。其中itemsetsX，itemsetsY，且X∩Y=。

在這種表示規則下，其支持度、可信度、期望可信度、作用度可定義如下：

a)支持度。規則XY的支持度定義為事務數據庫中同時包含項目集X和Y的事務百分數。即若事務數據庫D中有s%的事務同時支持項目集X和Y，則s%就稱為規則XY的支持度。支持度描述的是項目集X和Y的并集在事務數據庫中出現的概率。

b）可信度。規則XY的可信度定義為在包含項目集X的事務中，同時也包含項目集Y的事務的百分數。即若在包含項目集X的事務中有c%的事務也同時包含了項目集Y，則c%就稱為規則XY的可信度。可信度指出了在出現項目集X的事務中，項目集Y同時出現的概率有多大。

c）期望可信度。規則XY的期望可信度定義為事務數據庫中包含項目集Y的事務的百分數。即若在事務數據庫D中，如果有e%的事務支持項目集Y，則e%就稱為規則XY的期望可信度。期望可信度描述的是在沒有任何條件影響時，項目集Y在所有事務中出現的概率有多大。

d）作用度。規則的作用度定義為可信度和期望可信度的比值。它描述的是項目集X的出現對Y的出現有多大的影響。作用度越大，說明項目集Y受X的影響越大。

1．2Apriori算法

關聯規則的挖掘問題就是在事務數據庫D中找出具有用戶給定的最小支持度和最小可信度的關聯規則。Apriori算法主要任務是找出存在于事務數據庫中的所有頻繁項目集。

1．3改進的AprTidRec算法

針對apriori算法中一些不足之處，目前提出了許多優化方法來改進算法，包括AprioriTid和AprioriHybrid等。這些優化算法主要從三個方面來提高算法的執行效率：減少掃描數據庫的次數；減少生成候選項目集個數或不生成候選項目；采用新的存儲結構。

在本文中主要采用第三種方法，即通過采用一個記錄的存儲結構來減少需要掃描數據庫的次數，從而達到優化算法的目的。它的基本思想與apriori算法相似，不同之處在于后者在生成頻繁集時包括連接步和剪枝步，而前者只需連接步即可。先對每個候選項集定義一個tidRec的記錄結構，項集I的tidRec由數據庫中包含I的交易的TID組成，用I.tidRec表示項集I的tidRec。1項集的tidRec可通過搜索事務數據庫得到。算法中記錄的結構為〈I，tidRec，count〉。用I.count來表示項集的支持度；count的值等于tidRec的長度，即count=|tidRec|。由頻繁k-1項集生成候選頻繁k項集時，只需對兩個k-1項集的tidRec求交集，即可得到候選k項集的tidRec及其支持度。

2分布式關聯挖掘基本原理和方法

針對目前數據庫中數據存儲的規模日益增大，采用分布式數據庫系統是進行關聯規則挖掘的一種解決方案，而且分布式數據庫系統還可以在很大程度上解決集中式數據庫系統中央數據庫過于龐大的問題。分布式關聯挖掘的重點在于算法。分布式算法具有高度的適應性、可伸縮性、低性能損耗和容易連接等特性。分布式數據挖掘算法主要分為兩類，即數據分布(data distribution，DD)算法和計數分布(count distribution，CD)算法。

CD算法是一種典型的基于apriori的并行算法。在第一階段，每個分區獨立地進行數據庫掃描，計算出各個候選集的支持度；然后將各候選集的支持度進行相加得到全局支持度，相加后的支持度若大于minsup，則認為該項集是全局大的。CD 算法在每一次掃描結束后需要一個同步點，然后再進行下一次分區的掃描。隨著節點數的增多，CD算法的通信量將迅速增加，因此CD算法不能作為一種擴展性好的分布式算法。

DD算法的基本思路是將候選項集在各個節點之間進行均勻分布，這樣隨著節點增加時每遍掃描的候選項集數目的減少，從而提高算法的并行效率。其缺點是各個節點之間的數據要進行傳遞，這樣在各個節點數據量較大的情況下會降低算法的效率。因此DD算法只能作為一種非分布式環境下的并行關聯規則數據挖掘算法。

為了減少各個分區間的通信量，D.W.Cheung揭示了分散數據集與集中數據集之間的一些有價值的關系，提出了一個快速的基于分布式系統的關聯規則挖掘算法FDM。其分布式環境如圖1所示。

該算法首先在每個分區中運行apriori算法找出每個分區局部大的項集；然后在每個節點全局大的項集之間進行支持度合計數交換。通過生成數量較少的候選數據集，大大減少了在挖掘關聯規則時需要處理的數據量。分布式挖掘符號如表1所示。

算法包括以下幾個步驟：

a)FDM候選數據集的生成。在頻繁集與分布式數據庫中的節點之間有一個關系：每個全局頻繁集必定在某個地點是局部頻繁集。如果一個數據集X在地點Si既是全局頻繁集，又是局部頻繁集，可稱X在地點Si是全局大的。一個地點所有全局大的數據集作為該地點的候選數據集的源數據集。每個地點的源數據集是FDM算法計算的起點。

局部頻繁集和全局大的頻繁集具有兩個特征：如果一個數據集X在節點Si是局部大的，那么它的所有子集在節點Si也是局部大的；如果一個數據集X在節點Si是全局大的，那么它的所有子集在節點Si也是全局大的。

b)FDM候選數據集的局部剪枝。它的基本思想是在每一個節點Si，如果一個數據集在節點Si并不是全局大的，也就沒有必要計算出它的全局大的支持合計數來決定它是否是全局大的。因此每一層迭代均可以按照以下步驟計算出在節點Si的全局大的k數據集。

第一階段候選集的生成：根據在節點Si經過k-1次迭代生成的全局大的數據集基礎上，利用改進的AprTidRec算法生成k候選數據集。由于采用了改進的AprTidRec算法，本文中省去了本地剪枝。

第二階段支持合計數交換：將生成的局部大的k數據集中的候選元向其他節點廣播，以收集支持合計數，計算出全局的支持合計數，并得出在節點Si所有全局大的k數據集。

第三階段廣播挖掘結果：將計算得出的全局大的k數據集向其他節點廣播。

c)FDM候選數據集的全局剪枝。經過局部剪枝并將局部支持合計數及全局支持合計數向所有節點廣播后，就可以在以后的迭代中對候選數據集進行全局剪枝。

假設在每一次迭代結束后，如果發現某一候選數據集是全局大的，系統自動將每一個候選元的局部合計數向其他節點廣播。假設X是一個在k次迭代結束后大小為k的候選數據集，則在每一個節點都已收到所有X的大小為k-1的子集的局部支持合計數。對于一個分支數據庫DBi，用maxsupi(X)來表示X的所有大小為k-1的子集的最小局部支持合計數，根據父集與子集之間的關系，maxsupi(X)就是局部支持合計數X.supi的上界函數。因此所有分支數據庫中的這類上界函數的和用maxsup(X)來表示X.sup的上界，即X.sup≤maxsup(X)=∑maxsupi(X)。如果maxsup(X)

d）合計數輪流檢測。在剪枝階段(包括局部剪枝和全局剪枝)結束后，FDM在每一個節點Si按照如下步驟進行合計數輪流檢測。

第一階段將候選元送往各輪詢節點。假設在節點Si，對于每一輪詢地址Sj找到所有屬于集合LLi(k)且其輪詢地址為Sj的候選元，并將它們存儲在集合LLi， j(k)中，各候選數據集的局部支持合計數也同樣存放在集合LLi， j(k)中，然后送往各自相應的輪詢地址Sj。

第二階段輪流檢測并收集支持合計數。如果Si是一個輪詢地址，那么Si將接收所有來自其他節點的集合LLi， j(k)。對于每一個接收到的候選數據集X， Si首先找到送出X的原始節點列表；然后對每一個不在列表上的節點廣播輪詢請求，以收集它們的支持合計數。

第三階段計算全局大的數據集。Sj從其他節點接收支持合計數，并為其每一個候選元計算支持數合計；然后找到全局大的數據集；最后Sj向其他節點廣播找到的全局支持合計數。

3基于相似度的分布式關聯挖掘模型

在分布式系統中，對于同構性的數據庫系統而言，如上的分布式關聯規則挖掘能得到相當正確的關聯挖掘規則，為應用系統中其他模塊的實現提供有價值的信息。但目前仍有很大一部分數據庫系統是非同構性的，這就為分布式關聯數據挖掘帶來了很多麻煩，而基于相似度的分布式關聯規則挖掘恰好能解決上面提到的問題。

3．1相似度概念及算法

相似度是數據挖掘和知識發現中的一個重要概念。為了得到數據之間的規律性，就需要描述兩個數據對象之間的差異性。過去的幾年也有過計算數據對象的一些方法，如屬性相似度和數據庫相似度等。本文采用一種新的相似度方法，即采用計算信息熵的方法通過計算分布式關聯規則的支持度來實現優化模型。假設項集A是頻繁的且沒有包含A的項集B也是頻繁的，則表示A是一個最大頻繁項集，記為MFA。

設定A和B為兩個同類數據集，則

3．2實驗驗證

本文中假定某個系統由三個分布節點將一個數據庫系統DB分為DB1、DB2、 DB3。該數據庫中的數據包含150個事務，三個局部數據庫各自包含50個事務；同時假定最小支持度s=10%，并且假定大的1數據集（經過一層迭代計算所得）為L(1)={A，B，C，D，E，F，G，H}。其中A、B和C在節點S1是局部大的，也就是說{A}，{B}，{C}是在節點S1處的局部1頻繁集。同理在節點S2處B、C和D是局部大的，E、F、G、H在節點S3處是局部大的。

經過第二次迭代后在節點S1生成的候選集為CG1(2)= {AB，BC，AC}，在節點S2生成的候選集為CG2(2)={BC，AD，CD}，在節點S3生成的候選集為CG3(2)={EF，EG，FG，FH，GH}。然后在計算全局大的2候選集之前，先計算局部的支持合計數。表2為所得的計算結果。

最后經過全局剪枝和合計數交換后，最終得到的非空子集為{B}，{C}，{E}，{F}，{BC}，{CD}，{EF}，得到如表8所示的全局關聯規則。

從表2~4中可以發現，S1與S2之間相似度很高，與此同時S1與S3和S2與S3的相似度卻很低，而通過3.1節中的相似度公式也驗證了上面的結論。因此可以先將節點S1和節點S2分成一組，S3作為另外一組；然后重復FDM算法，得到了經過相似度處理后的關聯規則，如表9所示。

通過表8和9的比較可以發現，新的關聯規則較原先的準確率有了一定的提高，這為今后在各個領域中挖掘精確度要求較大的信息提供了新方法。

4結束語

數據挖掘技術是隨著大型數據庫的普及和數據量的迅速膨脹而不斷發展起來的，關聯規則的挖掘是數據挖掘技術的一個非常重要的方面。隨著分布式系統的發展和分布式數據庫的應用，在分布式環境下進行關聯規則的挖掘是目前關聯規則應用領域的一個非常重要的方面。針對分布式環境下數據庫的異構性，本文提出了一種基于相似度的分布式關聯規則挖掘數據模型。該模型充分考慮到了異構數據集對關聯規則中支持度的影響，首先通過計算相似度分離彼此相似度很小的數據集，而將相似的數據集合在一起，通過關聯規則挖掘得到最后的關聯規則。

參考文獻：

［1］KARGUPTA H，PARK B，HERSHBERGER D，et al.Collective data mining:a new perspective toward distributed data mining [C]//Proc of Advanced in distributed data mining.[S.l.]:AAAI/MIT， 2000:133184.

[2]YAMANISHI K.Distributed cooperative Bayesian learning strategies[C]//Proc of COLT.New York:ACM Press，1997:250－262.

[3]CHEUNG D W，NG V T，FU A W，et al.Efficient mining of association rules in distributed databases [J].

IEEE Trans on Knowledge and Data Engineering，1996，8（6）:911－922.

[4]TAO Li，ZHU Shenghuo，OGIHARA M.A new distributed data mining model based on similarity[C]//Proc of ACM Symposium on Applied Computing.New York:ACM Press，2003:432－436.

[5]談冉，康瑞華. 物流信息系統之分布式數據設計[J].武漢理工大學學報:信息與管理工程版，2006，28(8):38－41.

[6]朱明.數據挖掘[M].合肥:中國科學技術大學出版社，2002.

[7]鄒麗.分布式系統下關聯規則挖掘的研究與實現[D]. 大連：大連交通大學，2005.

[8]王越.分布式關聯規則挖掘的方法研究[D].重慶:重慶大學，2003.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”