陳雪兆

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

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

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

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

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

2 網(wǎng)格服務(wù)

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

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

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

3.1ODAM算法

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

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處計(jì)算全局支持度*/

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項(xiàng)侯選集 */

Ck+1={candidate itemset};

}

3.2 改進(jìn)

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

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

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

3.2.2 根據(jù)事務(wù)的最大長(zhǎng)度,判斷是否進(jìn)入下一輪挖掘

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

4 展望

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

參考文獻(xiàn):

[1] 胡敏,顧君忠.Globus網(wǎng)格體系結(jié)構(gòu)及其服務(wù)的實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2003(9).

[2] 侯文國(guó),傅秀芬.網(wǎng)格的數(shù)據(jù)挖掘[J].計(jì)算機(jī)應(yīng)用研究,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ù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘[M].北京:人民郵電出版社,2004:1.