一種改進的分布式關聯(lián)規(guī)則挖掘算法

曹文梁

一種改進的分布式關聯(lián)規(guī)則挖掘算法

曹文梁

（東莞職業(yè)技術學院 計算機工程系，廣東東莞 523808）

數(shù)據(jù)挖掘本質上是一種新的商業(yè)信息處理技術，通過對數(shù)據(jù)進行統(tǒng)計、分析、綜合和推理，發(fā)現(xiàn)數(shù)據(jù)間的關聯(lián)性、未來趨勢以及一般性的概括知識，用以指導高級商務活動。由于需要，對數(shù)據(jù)間的關聯(lián)性的數(shù)據(jù)挖掘算法模型已成為數(shù)據(jù)庫及相關領域的一個研究熱點，給出了一種基于分布式數(shù)據(jù)庫的挖掘模型及其相應的一種有效的挖掘算法，其由若干個站點集合而成，各個站點擁有各自的數(shù)據(jù)庫、中央處理機、客戶端，以及各自的局部數(shù)據(jù)庫管理系統(tǒng)，依靠通訊網(wǎng)絡連接。采用購物籃分析式關聯(lián)規(guī)則，將各個數(shù)據(jù)庫文件的數(shù)據(jù)合成，從而得到挖掘結果，對挖掘的方法又進一步挖掘，即將不滿足條件的規(guī)則重新傳送到各分布式站點上進行更加精確的挖掘處理，從而避免了頻繁的網(wǎng)絡通訊。該算法在減輕網(wǎng)絡頻繁的通訊負擔，體現(xiàn)并行計算以及異構數(shù)據(jù)挖掘方面具有獨特優(yōu)點。

分布式；關聯(lián)規(guī)則；挖掘模型

數(shù)據(jù)挖掘（DM，Date Mining），也稱數(shù)據(jù)庫中的知識發(fā)現(xiàn)（KDD：Knowledge Discovery in Database），是指從大型數(shù)據(jù)庫的大量原始數(shù)據(jù)中提取人們感興趣的、隱含的、事先未知的潛在有用的信息、是目前解決“數(shù)據(jù)爆炸”和“數(shù)據(jù)豐富而信息貧乏”的一種有效方法。數(shù)據(jù)挖掘在近年來已經(jīng)成為數(shù)據(jù)庫及相關領域的一個研究熱點［1］。

圖1 數(shù)據(jù)倉庫上的分布式挖掘模型

圖2 合成挖掘模型

經(jīng)過十幾年的研究和發(fā)展，數(shù)據(jù)挖掘技術進入了一個更高級的階段，數(shù)據(jù)挖掘算法也已基本成熟、穩(wěn)定，且易于理解和操作的技術［2］。目前數(shù)據(jù)挖掘基本停留在單機的數(shù)據(jù)挖掘上，對于分布式數(shù)據(jù)庫的數(shù)據(jù)挖掘雖然也有一些有關的挖掘技術，但基本停留在對數(shù)據(jù)倉庫的挖掘上，如圖1所示，這種技術的關鍵是將分布式在各個站點上的數(shù)據(jù)庫構建成數(shù)據(jù)倉庫進行數(shù)據(jù)挖掘。雖然基于數(shù)據(jù)倉庫技術的分布式技術也有處理異構數(shù)據(jù)的優(yōu)點，但是現(xiàn)在的數(shù)據(jù)庫一般都有非常龐大的數(shù)據(jù)量，構建數(shù)據(jù)倉庫需要投入很大的人力物力，而且數(shù)據(jù)倉庫技術在這方面存在很大的缺點，比如各分布式站點傳輸大量的數(shù)據(jù)到中心站點，容易造成網(wǎng)絡瓶頸，傳輸錯誤等缺陷；另外，相對于合成龐大的數(shù)據(jù)庫文件資源來說，合成數(shù)據(jù)庫文件的挖掘結果比較容易，如圖2所示。

1 預備知識

1.1 分布式數(shù)據(jù)庫系統(tǒng)

分布式數(shù)據(jù)庫系統(tǒng)是由若干個站點集合而成。每個站點都是一個獨立的數(shù)據(jù)庫系統(tǒng)，它們擁有各自的數(shù)據(jù)庫、中央處理機、客戶端，以及各自的局部數(shù)據(jù)庫管理系統(tǒng)。這些站點依靠通訊網(wǎng)絡連接在一起，它們在物理結構上是分布式的，但是在邏輯上屬于同一系統(tǒng)。分布式數(shù)據(jù)庫系統(tǒng)一般都具有透明訪問、分布式事務完整性、分布式計算、均衡網(wǎng)絡負載和可靠性高的特性［8］。一般來說，根據(jù)站點中數(shù)據(jù)庫管理系統(tǒng)或者設置及文件格式的選擇不同，數(shù)據(jù)庫中包含的數(shù)據(jù)格式以及存儲結構等都會有一定的不同。因此在分布式數(shù)據(jù)庫站點集群結構中，數(shù)據(jù)模型可能是異構的。對于這些數(shù)據(jù)，需要經(jīng)過數(shù)據(jù)清理，數(shù)據(jù)轉換，刪除無關的屬性轉換成一定的格式以便挖掘。

1.2 關聯(lián)規(guī)則

關聯(lián)規(guī)則挖掘用于發(fā)現(xiàn)大量數(shù)據(jù)項集之間有趣的關聯(lián)或相關聯(lián)系。其中一個典型的例子就是購物籃分析，該過程通過發(fā)現(xiàn)顧客放入購物籃中的不同商品之間的關系，分析顧客的購買習慣，例如，某顧客一次去超級市場，他既購買奶粉，又購買糖的可能性有多大，從而有助于零售商有選擇地經(jīng)銷和安排貨架。

設（I=｛i1，i2，…，in｝）是n個不同的項的集合，稱為項集，如集合｛商品，單價｝是一個二項集。給定事務數(shù)據(jù)庫D，其中每個事務T是項集的子集，即T∈I，且T有唯一的標識號Tid。設A是一個項集，事務T包含A，當且僅當A∈T，關聯(lián)規(guī)則是形如A→B的蘊含式，其中A∈I，B∈I，A∩B =Φ。規(guī)則A→B在事務集D中成立，具有支持度S，其中S是D中事務A∪B（即A和B二者）的百分比，它是概率P（A∪B）。規(guī)則A→B在事務中的置信度為c，如果D中包含A的事務同時也包含B的事務的百分比，這是條件概率P（B|A）。即

support（A→B）=P（A∪B）

confidence（A→B）=P（B|A）

圖3 分布式數(shù)據(jù)庫系統(tǒng)模型

基于關聯(lián)規(guī)則的數(shù)據(jù)挖掘分為兩步：

①找出所有頻繁項集 根據(jù)定義，這些項集出現(xiàn)的頻繁性至少和預定義的最小支持度閥值一樣。

②由頻繁項集產(chǎn)生強關聯(lián)規(guī)則 這些規(guī)則必須滿足最小支持度和最小置信度。

1.3 分布式數(shù)據(jù)庫系統(tǒng)模型

分布式數(shù)據(jù)庫系統(tǒng)允許應用程序從本地或者遠程數(shù)據(jù)庫操作數(shù)據(jù)。應用程序只需連接到本地數(shù)據(jù)庫就可以透明地訪問遠程數(shù)據(jù)庫的數(shù)據(jù)，而無需知道遠程數(shù)據(jù)庫的物理位置和類型。數(shù)據(jù)庫鏈接是數(shù)據(jù)庫分布式應用模型的基本對象，它定義了目標數(shù)據(jù)庫和連接用戶、分布式數(shù)據(jù)庫系統(tǒng)通過數(shù)據(jù)庫鏈接進行站點間通信，如圖3。分布式數(shù)據(jù)庫系統(tǒng)可由同種數(shù)據(jù)庫組成，也可由不同種數(shù)據(jù)庫聯(lián)合組成。同類分布式數(shù)據(jù)庫系統(tǒng)的實現(xiàn)比較簡單，一般在本地數(shù)據(jù)庫中建立到遠程數(shù)據(jù)庫的數(shù)據(jù)庫鏈接，遠程數(shù)據(jù)庫的連接用戶必須具有使用者所需的特權，一旦數(shù)據(jù)庫鏈接可用，應用程序就可以通過數(shù)據(jù)庫鏈接操作遠程數(shù)據(jù)庫。

2 數(shù)據(jù)挖掘步驟

2.1 數(shù)據(jù)清理和數(shù)據(jù)轉換

數(shù)據(jù)清理也可稱為數(shù)據(jù)清洗。數(shù)據(jù)清洗是在數(shù)據(jù)中消除錯誤和不一致，并解決對象識別問題的過程。數(shù)據(jù)清洗包括空值處理、噪聲數(shù)據(jù)處理及不一致數(shù)據(jù)處理等。數(shù)據(jù)的不一致性導致數(shù)據(jù)挖掘結果的可信度的降低。數(shù)據(jù)清理去除噪聲或無關數(shù)據(jù)，并處理數(shù)據(jù)中缺失的數(shù)據(jù)域［4，9］。關于數(shù)據(jù)清理和數(shù)據(jù)轉換技術，目前已有很多文章在這方面作了相應的研究，并且提出了很多可行性方案，這里不作具體探討。例如在數(shù)據(jù)清理和數(shù)據(jù)轉換階段主要是去掉一些無關的屬性，保留與數(shù)據(jù)挖掘目標相關的屬性。

2.2 規(guī)則挖掘

這個步驟分為兩步，我們首先從本地的數(shù)據(jù)庫中挖掘關聯(lián)規(guī)則，然后對這些本地的規(guī)則利用一定的算法進行合成，產(chǎn)生最終的目標關聯(lián)規(guī)則。

①本地規(guī)則挖掘這里采用關聯(lián)規(guī)則的算法，如簡單的Apriori算法以及該算法的一些變種［1，4-7］，挖掘的結果是在各個分布式站點上形成關聯(lián)規(guī)則庫。如表1～3所示。

表1 站點1的關聯(lián)規(guī)則庫

表2 站點2的關聯(lián)規(guī)則庫

表3 站點3的關聯(lián)規(guī)則庫

②數(shù)據(jù)挖掘結果合成。關聯(lián)規(guī)則挖掘結果的合成階段，主要由分布式站點挖掘結果所生成的一定格式的數(shù)據(jù)庫文件，將這些數(shù)據(jù)庫文件傳送到合成站點上，轉換成具有統(tǒng)一格式的數(shù)據(jù)庫文件格式，然后通過一定的軟件工具，或者數(shù)據(jù)庫管理系統(tǒng)中的工具，或者算法，將各個數(shù)據(jù)庫文件的數(shù)據(jù)合成，從而得到挖掘結果。但是用這種方法得到的挖掘結果的挖全率通常不可能達到1，即可能會丟失部分滿足最小支持度閥值的規(guī)則。假如用戶需要的結果比較精確時，我們采取第二步挖掘的方法進一步挖掘，即將不滿足條件的規(guī)則重新傳送到各分布式站點上進行更加精確的挖掘處理。因此，挖掘模型在精確度要求上有一定的可擴展性。

符號說明：

DBi：分布式站點i中的事務（關系）數(shù)據(jù)庫（經(jīng)過數(shù)據(jù)清理和數(shù)據(jù)轉換后）；

Di：DBi中的事務（或元組）的數(shù)目；

DBR：各分布式站點中關聯(lián)規(guī)則庫相結合而組成的數(shù)據(jù)庫；

m：DBR中事務（或元組）的數(shù)目；

n：分布之站點的數(shù)目；

Sij：DBR中第i條規(guī)則在第j個站點上的支持度；

Si：DBR中第i條規(guī)則的合成支持度；

λ：預定義的最小支持度閾值；

λ·α：各分布式站點中預定義的最小支持度閾值；

DBr：經(jīng)計算在DBR中暫時不滿足最小支持度，但有可能重新挖掘后復合條件的規(guī)則庫。

預備性質

性質1 如果某一規(guī)則的支持度Si＞λ，則其中至少有一個分布式站點的支持度Sij＞λ。

證明 假設各分布式站點的支持度Sij＜λ，則：

證明 由于性質1，所以

證明 由性質1的證明過程可得：

④主要算法

1）將分布式站點上的挖掘結果（如表1～3）傳送到合成站點上合成關聯(lián)規(guī)則庫。

3）在DBr中將所有滿足Sij=0的第i條規(guī)則返回到各分布式站點j中重新挖掘；

4）將第i條規(guī)則在第j個站點上重新挖掘所得的支持度Sij替換原來值為0的Sij；

5）在更新后的DBr中，利用性質2，若Si≥λ，則將Si加入到DBR中；

6）DBR就是所求的關聯(lián)規(guī)則庫。

3 具體實例

下面就采用表1～3所提供的在三個分布式站點上的挖掘結果作為數(shù)據(jù)源，說明算法的具體實施過程。

令D1=100、D2=200、D3=300、λ=0.75、α=0.80、λ·α=0.60。

①將三個分布式站點的挖掘結果合成數(shù)據(jù)庫DBR；

④將規(guī)則P2、P3重新傳送到第二個分布式站點進行重新挖掘，假定挖掘結果為S62=0.50；

④在DBr中用重新挖掘所得的S62=0.50代替原來的S62=0.00；

⑤重新計算S6，得S6＜λ，不滿足條件；

⑥DBR就是所求的關聯(lián)規(guī)則庫，如表4。

表4 挖掘結果

該方法采用分布式站點挖掘結果，通過進一步挖掘，即將不滿足條件的規(guī)則重新傳送到各分布式站點上進行更加精確的挖掘，傳送到合成站點上合成關聯(lián)規(guī)則庫。實例證明，該算法能夠將挖掘結果有效合成為符合分布式數(shù)據(jù)庫系統(tǒng)模型的關聯(lián)規(guī)則庫，滿足了設定要達到的計算要求。

4 模型與算法評價

該模型及算法適用于分布式數(shù)據(jù)庫的數(shù)據(jù)挖掘，具有如下優(yōu)點：

①將分布式數(shù)據(jù)挖掘的時間開銷和CPU開銷分別分配到各分布式站點執(zhí)行，而頂層站點只負責挖掘結果的合成，從而大大減輕了頂層站點的負擔，體現(xiàn)了并行挖掘的優(yōu)點；

②根據(jù)的模型算法，頂層站點與各分布式站點之間的網(wǎng)絡通信只有一次（挖掘結果合成階段）或三次（重新挖掘階段），從而避免了頻繁的網(wǎng)絡通訊；

④由于該模型算法在數(shù)據(jù)挖掘合成階段只須提供各分布式站點的挖掘結果，因此各分布式站點挖掘結果的數(shù)據(jù)格式可以不同，從而進一步解決了異構數(shù)據(jù)的挖掘問題；

④通過具體實施例分析，該模型算法能夠將挖掘結果有效合成為符合條件的關聯(lián)規(guī)則庫，滿足設定計算要求。

5 結語

本文在已有的分布式數(shù)據(jù)挖掘研究的基礎上，基于實際應用的考慮，對分布式數(shù)據(jù)庫的挖掘算法進行了一些改進，對各局部數(shù)據(jù)庫進行二次挖掘，從而提高了全局模式的挖全率和質量；從應用的角度，提出基于各局部數(shù)據(jù)庫挖出的局部模式對局部數(shù)據(jù)庫進行分類，擴展了分布式數(shù)據(jù)挖掘的實用價值。所提出的算法特別適用于分布式站點數(shù)目較多的大型分布式數(shù)據(jù)庫的數(shù)據(jù)挖掘，更能體現(xiàn)算法的高效性，該模型和算法能夠大大減輕網(wǎng)絡頻繁的通訊負擔，在數(shù)據(jù)挖掘合成階段只須提供各分布式站點的挖掘結果，因此各分布式站點挖掘結果的數(shù)據(jù)格式可以不同，從而進一步解決了異構數(shù)據(jù)的挖掘問題，在并行計算以及異構數(shù)據(jù)挖掘方面能夠體現(xiàn)出獨特的優(yōu)點。

［1］ 劉瓊梅，曾敏.基于關聯(lián)規(guī)則的遙感圖像挖掘的應用研究［J］.湖南科技大學學報：自然科學版，2010，25（2）：94-98.

［2］ 孟曉明.淺談數(shù)據(jù)挖掘技術.計算機應用與軟件［J］.2014，21（8）：34-36.

［3］ 羅建利，沈潔，許有志，等.基于分布式的Web log挖掘模型［J］.計算機應用與軟件，2004，21（7）：30-33.

［4］ 張云濤，龔玲.數(shù)據(jù)挖掘原理與技術［M］.北京：電子工業(yè)出版社，2004.

［5］ 邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法［M］.北京：中國水利水電出版社，2005.

［6］ 林杰斌，劉明德，陳湘.數(shù)據(jù)挖掘與OLAP理論與實務［M］.北京：清華大學出版社，2003.

［7］ 陳鈺芳，王曉峰.基于應用的分布式數(shù)據(jù)庫挖掘算法研究［J］.計算機工程與科學，2009，31（6）：119-120.

［8］ 蘇燕強.Oracle分布式數(shù)據(jù)庫及其應用研究［J］.計算機應用與軟件，2004，21（8）：36-37.

［9］ 楊海濤，劉勝全.基于分布式數(shù)據(jù)庫的挖掘模型［J］.現(xiàn)代計算機，2005，233：8-12.

An Algorithm for Distributed Association Rules Mining

CAO Wen-liang

（Computer Engineering Department，Dongguan Polytechnic，Dongguan 523808，China）

Data mining is a new business information processing technology.Through microcosmic，medium even macroscopic statistic，analysis，synthesizing and inference，it can find the co-relation between data，trends and generality of knowledge in order to guide senior business activities.Data mining algorithm model has been a hot topic in the database and relational field.This paper introduces a mining model based on distributed database and presents an efficient mining algorithm.It includes a few stations，and each station has individual database，CPU，client-side and the manage system of local database，connected by communication internet.Through shopping basket analysis association rule and integrating every database file，it gets a mining result，and then makes a further mining upon the mining method，transports the rules which are not fit with the reruirements back to each distributed station to make a more accurate mining process，thus avoiding the freruent internet communication.This algorithm can reduce freruent communication burden，owning an distinguishing virtue in parallel arithmetic computing and asynchronous operation&heterogeneous mining.

distributed；association rule；mining model

TP31

符：A

1009-0312（2014）03-0035-06

2013-11-15

曹文梁（1980—），男，江西泰和人，副教授，碩士，主要從事數(shù)據(jù)控制與網(wǎng)絡安全研究。