基于網格服務的分布式數據挖掘

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

關鍵詞:分布式;數據挖掘;網格;ODAM;關聯規則

中圖分類號: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

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

1 網格數據挖掘

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

2 網格服務

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

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

3 關聯規則挖掘算法ODAM及改進

3.1ODAM算法

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

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);

/*產生k+1項侯選集 */

Ck+1={candidate itemset};

}

3.2 改進

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

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

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

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

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

4 展望

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

參考文獻:

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

[2] 侯文國，傅秀芬.網格的數據挖掘[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] 陳文偉，黃金才.數據倉庫與數據挖掘[M].北京:人民郵電出版社，2004:1.