基于分布式系統的關聯規則挖掘算法

□霍桂利

( 山西建筑職業技術學院，山西 太原 030006)

一、數據挖掘與數據庫

數據庫或數據倉庫可能存儲相當大數量的數據，在現在的大型數據庫中，保存了大量的數據，數據庫自然成為數據挖掘的數據基礎。數據挖掘的發展方向是和數據倉庫相結合。在這樣的數據環境下進行關聯規則的挖掘可能需要充足的處理器資源，分布式系統是一個可能的解決方案。同時許多大型數據庫本來就是分布式的。數以萬計的交易數據很可能存在不同的地點，這種事實使得研究數據庫中挖掘關聯規則的高效分布式算法顯得非常重要，同時帶動并行算法的研究。因為分布式算法具有高度的適應性、可伸縮性、低性能損耗和容易連接等特性，它將可以作為挖掘關聯規則的理想平臺。由于有大量事務數據庫的存在，這些數據庫中存儲海量的數據，很容易想到將一個集中的數據庫進行分割，從而利用分布式系統帶來的高度的可伸縮性，達到提高效率的目的。D.W.Cheung揭示了分散數據集與集中數據集之間的一些有趣關系，并提出了一個快速的基于分布式系統的關聯規則挖掘算法FDM，該算法通過生成數量較少的候選數據集，大大減少了在挖掘關聯規則時需要處理的數據量。

以事務數據庫作為討論對象，而相應的方法可以很容易地擴展到關系數據庫中，該數據庫存儲了大量的交易數據，每一個交易都有一個唯一的交易碼(TID}和一組屬性數據。此外，可以認為該數據庫是“水平”分片的(例如，對交易進行分組)，并且被分配在靠消息傳遞進行通信的分布式系統中?；谝陨霞僭O來考察對關聯的分布式挖掘，挖掘關聯規則的主要代價為對數據庫中大數據集的計算。而對這些大數據集進行分布式計算會遇到一些新的問題。你可以在一個地方很容易地進行計算，但是一個局部的大數據集對于全局來說不一定是大數據集。因為對其他地點廣播全部數據的代價是非常昂貴的，一種可行的做法是像其他地點廣播數據集的聚合數據，而不考慮局部數據量的大小。但是，一個大數據庫可能包括非常多數量的數據集的組合，這樣需要傳輸的信息量也是驚人的。

二、挖掘關聯規則的算法

通過觀察可以發現，在局部大數據集與全局大數據集之間，存在著一些有價值的關聯。只有最大限度地利用這些關聯，就可以減少信息的傳輸量，對需要局部處理的數據進行過濾。如前所述，目前已經存在兩種挖掘關聯規則的并行算法—PDM和計數分布(CD)算法，它們都是基于各自獨立的并行系統的，然而，它們也可以用在分布式環境中。FDM相對于以上提出的兩種算法，有著獨特的特性：(1)候選數據集的生成算法思想與Apriori算法類似。但是，在每個大數據量的重復數據集中生成小數據量的候選數據集的過程中，發現了一些關于局部的大數據集和全局的大數據集的有價值的關系。這樣，就可以利用這些關系減少信息傳送量。(2)在候選數據集被選出以后，在每一個單獨的地點，都可以利用兩種剪枝技術—局部剪枝和全局剪枝對候選數據集進行裁剪。(3)為了決定一個候選集的數據量的大小，利用一個時間復雜度為O(n)的算法來進行聚合數信息交換，n代表整個網絡的節點數。比起對Apriori算法進行直接的改編，其效率要高得多，因為后者的時間復雜度為O(n2)。注意到在FDM算法中可以采用幾種不同的局部剪枝和全部剪枝算法，著重研究了三個FDM的版本：FDM-LP,FDM-LUP,FDM-LPP,它們都具有相似的結構但具有不同的剪枝算法。FDM-LP算法只討論了局部剪枝；FDM-LUP算法討論了局部剪枝和上界剪枝；FDM-PP算法討論了局部剪枝和逐點剪枝。

在分布式環境中考察有關大數據集的某些特殊屬性是非常重要的，因為這些屬性可能被利用來顯著減少在挖掘關聯規則時的網絡信息傳輸量。在大數據集與分布式數據庫中的地點之間又一個重要的關系：每一個全局的大數據集必定在某一個地點是局部大數據集。如果一個數據集X在地點Si既是全局大數據集又是局部大數據集，可以稱X在地點Si是全局大的，一個地點所有的全局大的數據集將作為該地點的候選數據集的源數據集。可以觀察到關于局部大數據集和全局大的數據集的兩個特征：第一，如果一個數據集X在地點Si是局部大的，那么它的所有子集在地點Si也是局部大的。第二，如果一個數據集X在地點Si是全局大的，那么它的所有子集在地點Si也是全局大的。注意到在集中的環境中也有類似的關系，以下給出的是利用在分布式環境中有效生成候選集的技術得出的重要結果。

如果一個數據集X是全局大的，那么存在一個地點Si，X以及它的所有子集在地點Si是全局大的。

證明：如果X在任何地點都不是局部大的，即X.supi

用GLi表示在地點Si的全局大數據集，GLi(k)表示在地點Si的全局大的k-數據集，根據引理3.1 ，如果X∈L(k),那么存在一個地點S(1≤i≤n)i，使得X的所有大小為k-1的子集在地點Si是全局大的，也就是說，它們屬于GLi(k-1)。

三、挖掘關聯規則算法的有效性

假設某個系統中有三個分布地點將一個數據庫系統DB分為DB1，DB2，DB3。并假設大的1-數據集(經過一層迭代計算所得)L(1)={A，B，C，D，E，F，G，H}，其中，A、B是C在地點S1是局部大的，B、C和D在地點S2是局部大的，E、F、G和H在地點S3是局部大的，所以，GL1(1)={A，B，C}，GL2(1)={B，C，D}，GL3(1)={E，F，G，H}，根據定理3.2，在地點S1的大小為2的候選數據集為CG1(2)，CG1(2)= Apriori—gen(GL1(2))={AB，BC，AC}。類似地，CG2(2)={BC,CD,BD}, CG3(2)={EF，EG，EH，FG，FH，GH}，因此，大的2-數據集的候選數據集CG2= CG1(2)∪CG2(2)∪CG3(2)，共有11個候選元。但是，如果對L(1)直接進行Apriori—gen變換，那么候選數據集CA(2)= Apriori—gen(L1)將包含28個元素。這說明利用定理3.2對減少候選數據集中的數據量是很有效的。

在地點Si的局部剪枝中，只用到了在DBi中得到的局部支持合計數對候選集進行剪枝，事實上，在其他地點得到的局部剪枝支持合計數也同樣可以被用來剪枝。利用一種全局的剪枝技術來實施這樣的剪枝，這種技術的要點如下：在每一次迭代結束時，可以得到候選數據集X的所有局部剪枝支持合計數。在一個候選數據集被確認為是全局大的以后，這些局部剪枝支持合計數都可以在以后的迭代中對候選數據集進行一些全局剪枝。

通?？梢栽诜植际江h境中選擇生成一個比直接應用Apriori算法生成的數據集數據量小得多的候選數據集。當候選數據集CG(k)生成成功后，為了得到全局大的數據集，就必須在所有地點之間交換支持合計數的信息，注意到CG(k)中的某些候選數據集在進行合計數交換之前就可利用局部的剪枝技術進行剪枝?？偟乃枷胧牵涸诿恳粋€地點Si，如果一個數據集X∈CGi(k)在地點Si并不是局部大的，也就沒有必要來算出它的全局大的支持合計數來決定它是否是全局大的。這個結論是基于如下原因：如果X是小的(也就是說不是全局大的)，或者它可能在別的地點是局部大的，那么，只有X為局部大的那些地點才有必要計算X的全局支持合計數。所以，為了計算所有的大的k-數據集，在每一個地點Si，候選數據集就可以只限定在數據集X∈CGi(k)，并且在地點Si是局部大的。為了簡略起見，LLi(k)用來表示那些在CGi(k)中的候選集并且在地點Si是局部大的。根據以上的討論，在每一層迭代(共有k次迭代)的過程中，可以按照以下步驟計算出在地點Si全局大的k-數據集：

(1)候選集的生成：根據在地點Si經過k-1次迭代生成的全局大的數據集的基礎上，利用公式CGi(k)=Ariori—gen(GLi(k))生成CGi(k)。(2)本地剪枝：對于每一個數據集X∈CGi(k)，掃描每一個局部數據庫DBi以計算本地支持合計數X.supi。如果X在地點Si不是局部大的，那么將其從候選數據集LLi(k)中刪除。(3)支持合計數交換：將LLi(k)中的候選元向其他地點廣播，以收集支持合計數。計算全局的支持合計數，并得出在地點Si所有全局大的k-數據集。(4)廣播挖掘結果：將計算所得的全局大的k-數據集向其它地點廣播。

在地點Si的局部剪枝中，只用到了在DBi中得到的局部支持合計數對候選集進行剪枝。事實上，在其他地點得到的局部支持合計數也同樣可以被用來剪枝。利用一種全局的剪枝技術來實施這樣的剪枝，這種技術的要點如下：在每一次迭代結束時，可以得到候選數據集X的所有局部支持合計數和全局支持合計數。在一個候選數據集被確認為是全局大的以后，這些局部支持合計數和全局支持合計數都可以向所有地點進行廣播，利用這一信息，就可以在以后的迭代中對候選數據集進行一些全局剪枝。

因為X.supi在局部剪枝后就可以獲得，所以，該上界可以在地點Si被計算出用以對候選數據集進行剪枝。在CD算法中，每一個候選數據集的局部支持合計數被從一個地點向所有其他的地點進行廣播。如果一個候選數據集X在地點Si是局部大的話，那么Si需要o(n)數量級的信息來得到X的支持合計數，通常來說，在所有地點都是局部大的候選數據集是非常少的。所以，FDM算法通常只需少于o(n2)數量級的信息就可以算出每一個候選元，為了確保FDM在任何情況下只需要o(n)數量級的信息就可以算出每一個候選元，對于每一個候選數據集，該技術用到了一個指派函數，假設該函數為作用于X上的函數，將X映射為一個輪詢地址，對應于X的一個輪詢地址與X為局部大的那些地點是毫無關系的，對于每一個候選數據集X，它的輪詢地址是用來計算是否X為全局大的。為了達到這個目的，對應于X的輪詢地址必須向所有其他地點廣播X的輪詢請求，收集局部支持合計數，計算全局支持合計數。因為對應于每一個候選數據集X，有且僅有一個輪詢地址，所以X需要的合計數交換信息數就可以被減少到o(n)數量級。

四、結果的解釋和評價

進行數據挖掘時，首先要從大量數據中取出一個問題相關的樣板數據子集，而不是使用全部數據。通過對數據的取樣，選擇與知識發現任務相關的數據集，從而減少數據處理量，同時又不降低知識發現的精確度。數據預處理主要是接受并理解用戶的發現要求，確定發現任務，抽取與發現任務相關的知識源，根據背景知識中的約束性規則對數據進行合法性檢查，生成供挖掘核心使用的目標數據。在經過預處理的數據基礎上利用人工神經網絡、遺傳算法、決策樹、規則推理等方法，高效地進行關聯規則、序列模式、分類、聚類等各項分析。

數據挖掘的目的在于根據最終用戶的決策目的對提取的信息進行分析。從上述過程中將會得出一系列的分析結果、模式和模型。分析結果一般都是形式化的，這時需要通過可視化等技術手段，用圖表、圖形曲線等為用戶提供清晰、直觀的結果描述。在大多數情況下，對目標問題的描述是多側面的，這時就要綜合它們的規律性，進行進一步的抽象與過濾，提供合理的決策支持信息。

參考文獻：

[1]史忠植，潘謙紅，李威，李云峰.分布式環境下的數據庫知識發現[Z].第六屆全國機器學習研討會會議論文,1998,(6).

[2]王清毅,張波,蔡慶生.前數據挖掘算法的評價[J].小型微型計算機系統,2000 ，(3) .

[3]胡侃,夏紹瑋.基于大型數據倉庫的數據采掘研究綜述[J].軟件學報，1998， (1).

[4]陸建海，劉海峰.數據庫中廣義模糊關聯規則的挖掘[J].工程數學學報,2000，(1).

[5]馬洪文，王萬學，李振江.廣義模糊關聯規則的挖掘[J].黑龍江商學院學報，2000，(2).