基于分布式系統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法

□霍桂利

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、結(jié)果的解釋和評(píng)價(jià)

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

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

參考文獻(xiàn)：

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

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

[3]胡侃,夏紹瑋.基于大型數(shù)據(jù)倉(cāng)庫(kù)的數(shù)據(jù)采掘研究綜述[J].軟件學(xué)報(bào)，1998， (1).

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

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