基于網(wǎng)格服務的分布式數(shù)據(jù)挖掘

摘要:闡述網(wǎng)格計算概念及其與傳統(tǒng)分布式計算的區(qū)別。介紹了一種分布式關聯(lián)規(guī)則挖掘算法，并對其進行了幾點改進，最后用網(wǎng)格服務實現(xiàn)了該算法。實驗測試結(jié)果表明，使用網(wǎng)格服務可以合并若干臺計算機的計算能力來減少算法的運行時間。

關鍵詞:分布式;數(shù)據(jù)挖掘;網(wǎng)格;ODAM;關聯(lián)規(guī)則

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)36-10211-02

Distributed Data Mining on Grid Service

CHEN Xue-zhao

(Yongzhou Vocational and Technical College， Yongzhou 425100， China)

Abstract: In this paper， the definitions of grid computing and the difference with traditional distributed computing architecture are listed. A distributed Association rule algorithm is introduced， and based on it， two improved methods are proposed and implemented by grid service. Experiments show that using of grid service can incorporate the computing capability of several computers to reduce the execute time of the algorithm.

Key words: distributed; data mining; grid; ODAM; association rule

網(wǎng)格是構筑在Internet上的一組新興技術和基礎設施，實現(xiàn)互聯(lián)網(wǎng)上所有資源的全面連通，包括計算資源、存儲資源、通信資源、軟件資源、信息資源等，其目標是在動態(tài)變化的、廣域分布的異構虛擬組織間實現(xiàn)協(xié)同資源共享，多領域的科學和工程的問題求解[1]。網(wǎng)格計算技術是解決復雜海量科學數(shù)據(jù)的計算、訪問、存儲、組織和管理的一種有效技術。建立在數(shù)據(jù)網(wǎng)格基礎上的數(shù)據(jù)挖掘結(jié)合網(wǎng)格計算的思想及其技術的優(yōu)點，能夠?qū)V域分布的海量數(shù)據(jù)進行高效的處理、分析和挖掘，給科學研究領域，經(jīng)濟領域和社會生活帶來新的發(fā)現(xiàn)和巨大的價值。由于這種需求的存在，網(wǎng)格技術應運而生。

1 網(wǎng)格數(shù)據(jù)挖掘

網(wǎng)格數(shù)據(jù)挖掘的特點:1) 超級計算能力。從理論上講，網(wǎng)格可以利用所有連接在Internet上的所有閑置計算機資源形成一個超級的計算能力，并提供給科學計算領域和社會經(jīng)濟生活領域。2) 具有分布性和動態(tài)性，數(shù)據(jù)分布范圍廣。在網(wǎng)格計算環(huán)境中，廣域分布的各種資源都是動態(tài)創(chuàng)建和刪除的。因此，網(wǎng)格的數(shù)據(jù)挖掘系統(tǒng)具備分布性和動態(tài)性[2]。正是網(wǎng)格的這些特點及其分布式環(huán)境，使得網(wǎng)格的數(shù)據(jù)挖掘系統(tǒng)既不同于傳統(tǒng)的集中式數(shù)據(jù)挖掘系統(tǒng)，也不同于分布式數(shù)據(jù)挖掘系統(tǒng)，而是和網(wǎng)格一樣具有分布性、動態(tài)性和自適應性。網(wǎng)格的數(shù)據(jù)挖掘系統(tǒng)采用分布式的組件架構和自適應的分布技術，由一系列的組件集成，組件之間可以實現(xiàn)互相通信和數(shù)據(jù)交換。這種基于分布式組件技術的體系結(jié)構允許更大的彈性，包括集成不同的協(xié)議、應用程序接口、應用程序、操作系統(tǒng)和硬件，能夠提供多級的抽象能力、高可靠性、可擴充性和安全性。

2 網(wǎng)格服務

網(wǎng)格數(shù)據(jù)挖掘是通過網(wǎng)格服務體系結(jié)構來實現(xiàn)的，開放式網(wǎng)格服務體系結(jié)構(OGSA，Open Grid Service Architecture)是在網(wǎng)格計算和Web Services技術融合的基礎上提出的一套規(guī)范和標準。在OGSA體系結(jié)構中一切都被抽象為服務，包括計算機、軟件、數(shù)據(jù)以及設備等?？紤]到網(wǎng)格環(huán)境的特點，存在著大量的臨時性服務，OGSA在原來的Web服務基礎上提出了Grid Service的概念，用于解決服務的發(fā)現(xiàn)、動態(tài)服務的創(chuàng)建、服務的生命周期管理等與臨時服務有關的問題。

Web服務是Grid服務的基礎，它與CORBA，EJB，RMI等技術類似，是一種分布式計算技術，可以使用Web服務來解決異構的分布式計算問題。Web服務與其他分布式技術相比，其優(yōu)點是:1) Web服務是平臺/語言獨立的，使用標準的XML作為協(xié)議語言。2) Web服務使用HTTP協(xié)議進行通信，可以方便地穿過防火墻。Web服務也有其自身的缺點:Web服務使用XML傳輸文本數(shù)據(jù)獲得了高移植性，可是與傳輸二進制數(shù)據(jù)的技術相比失去了高效率性，所以不能將Web服務技術應用于實時系統(tǒng)中。3) Web服務目前只支持幾種有限的服務調(diào)用方式，而Grid服務將提供更多的服務，如:Persistency，Notification，Lifecycle management，Transaction等。Web服務是無狀態(tài)的，不能保留中間結(jié)果，多個客戶端共享一個Web服務的實例。Grid服務擴展了Web服務，添加了Factory(工廠)的概念，客戶端與Factory進行通信，由Factory來管理和維護Grid服務實例。一個客戶端既可以擁有一個Grid服務實例，也可以多個客戶端共享一個Grid服務實例。除此之外，Grid服務在服務實例的生命周期管理、服務數(shù)據(jù)、通知等方面進行了改進。

3 關聯(lián)規(guī)則挖掘算法ODAM及改進

3.1ODAM算法

ODAM(Optimized Distributed Association Rule Mining )是一個針對地理分布的數(shù)據(jù)集的分布式關聯(lián)規(guī)則挖掘算法，減少了事務、數(shù)據(jù)集、信息交換的的平均長度。算法如下:

NF={Non-frequent global 1-itemset}

for all transaction t∈D

{

for all 2-subsets s of t

if(s∈C2) s.sup++;

t′=delete_nonfrequent_items(t);

Table.add(t′);

Send_to_receiver(C2);

/*在receiver處計算全局支持度*/

F2=recerve_from_receiver(fg);

C3={candidate itemset};

T=Table.getTransactions(); k=3;

While(Ck≠{}){

For all transaction t∈T

For all k-subsets s of t

If(s∈Ck) s.sup++;

K++;

Send_to_receiver(Ck);

/*產(chǎn)生k+1項侯選集 */

Ck+1={candidate itemset};

}

3.2 改進

ODAM算法是對Apriori算法的改進。它在挖掘中逐漸減少數(shù)據(jù)集的大小，同時對站點之間的信息交換進行了大幅度的優(yōu)化[4]。其他方面基本上是一個分布式的Apriori算法。本文對ODAM進行下列優(yōu)化。

3.2.1 在生成侯選集之前判斷挖掘是否可以結(jié)束

在準備生成n侯選集之前，如果n-1項全局頻繁集的個數(shù)小于n，則挖掘結(jié)束，而不用先生成n項侯選集，然后再查找判斷其n個n-1項子集是否都是頻繁集來判斷該n項集可以作為侯選集。最后判斷n項侯選集的集合是否為空來決定挖掘是否結(jié)束?？梢赃M行這種改進的原因是n項集的n-1項子集有n個。這種方法適用于數(shù)據(jù)集較小，事務長度較大的情況。

3.2.2 根據(jù)事務的最大長度，判斷是否進入下一輪挖掘

在掃描單項集后，記錄下最大的事務長度TLenMax。在挖掘n項集前，判斷n是否大于TLenMax，如果是，則結(jié)束挖掘;否則，繼續(xù)。原因是事物數(shù)據(jù)庫中的沒有長度為n的事務，所有n項侯選集合的支持度都為零。這種方法適合于數(shù)據(jù)集較大，而事務最大長度較小的數(shù)據(jù)源。如下面的雷達源識別數(shù)據(jù)集就是一個事務長度最小為3，最大為6，而有5000條樣本的數(shù)據(jù)集。

4 展望

網(wǎng)格數(shù)據(jù)挖掘可以通過多臺處理器協(xié)作工作來提高工作效率。但這也產(chǎn)生了新問題:如何分解數(shù)據(jù)挖掘任務以及子任務間的協(xié)調(diào)。以及某個資源(計算機)意外失敗而引起的任務重新劃分問題。

參考文獻:

[1] 胡敏，顧君忠.Globus網(wǎng)格體系結(jié)構及其服務的實現(xiàn)[J].計算機工程，2003(9).

[2] 侯文國，傅秀芬.網(wǎng)格的數(shù)據(jù)挖掘[J].計算機應用研究，2004(2).

[3] The Globus Project[EB/OL].http://www.globus.org.

[4] Ashrafi M Z，Taniar D.ODAMAn Optimized Distributed Association Rule Mining[J].Algorithm IEEE DISTRIBUTED SYSTEMS，2004(5).

[5] 陳文偉，黃金才.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘[M].北京:人民郵電出版社，2004:1.