□霍桂利

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

一、數(shù)據挖掘與數(shù)據庫

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

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

二、挖掘關聯(lián)規(guī)則的算法

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

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

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

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

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

三、挖掘關聯(lián)規(guī)則算法的有效性

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

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

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

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

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

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

四、結果的解釋和評價

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

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

參考文獻：

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

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

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

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

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