1.引言

計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的普及與應(yīng)用給人們的生活帶來(lái)了翻天覆地的變化，同時(shí)在網(wǎng)絡(luò)上產(chǎn)生了大量雜亂無(wú)章的數(shù)據(jù)。而網(wǎng)格技術(shù)、Web技術(shù)的發(fā)展，為人們從分布的網(wǎng)絡(luò)資源中尋找有價(jià)值的信息提供了新的技術(shù)支持，同時(shí)也產(chǎn)生了許多基于網(wǎng)格的數(shù)據(jù)挖掘系統(tǒng)。而數(shù)據(jù)挖掘算法又是決定一個(gè)數(shù)據(jù)挖掘系統(tǒng)性能的主要衡量指標(biāo)。任何軟件系統(tǒng)的設(shè)計(jì)都離不開(kāi)算法，數(shù)據(jù)挖掘技術(shù)的執(zhí)行效率也與數(shù)據(jù)挖掘算法有關(guān)，隨著數(shù)據(jù)庫(kù)技術(shù)與數(shù)據(jù)挖掘技術(shù)的成熟與發(fā)展，像分類、聚類、決策樹(shù)、關(guān)聯(lián)等等數(shù)據(jù)挖掘算法已相當(dāng)成熟，可以研究借鑒現(xiàn)有數(shù)據(jù)挖掘方法、數(shù)據(jù)挖掘模式、數(shù)據(jù)挖掘流程，建立一個(gè)基于網(wǎng)格的數(shù)據(jù)挖掘系統(tǒng)。筆者以眾多數(shù)據(jù)挖掘算法中的聚類分析算法為例，介紹基于GT4(Globus Tookit 4.0的簡(jiǎn)稱，GT4的核心開(kāi)發(fā)工具包(Java Web Service Core))的數(shù)據(jù)挖掘算法的設(shè)計(jì)過(guò)程。

聚類分析(Clustering Analysis)是一個(gè)應(yīng)用比較廣泛的數(shù)據(jù)挖掘算法，算法的理論研究與實(shí)踐應(yīng)用都已經(jīng)很成熟，把這一成熟的理論應(yīng)用于基于網(wǎng)格的分布式系統(tǒng)中，會(huì)大大提高數(shù)據(jù)挖掘的效率。本文主要研究如何將聚類分析的CURE(Cluster Using Representation)算法和K-平均方法算法應(yīng)用于基于GT4數(shù)據(jù)挖掘系統(tǒng)中。

2.系統(tǒng)結(jié)構(gòu)設(shè)計(jì)

基于GT4數(shù)據(jù)挖掘系統(tǒng)的數(shù)據(jù)源是分布式數(shù)據(jù)源，分布式數(shù)據(jù)源是指在物理上分布而邏輯上集中的數(shù)據(jù)源系統(tǒng)。在該系統(tǒng)中，處在這個(gè)網(wǎng)格中的每臺(tái)計(jì)算機(jī)就是這個(gè)網(wǎng)格的一個(gè)節(jié)點(diǎn)，稱之為網(wǎng)格節(jié)點(diǎn)。在眾多的節(jié)點(diǎn)中，要有一個(gè)網(wǎng)格節(jié)點(diǎn)來(lái)控制和管理其他的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)就叫做網(wǎng)格中心控制節(jié)點(diǎn)，決策支持都是由網(wǎng)格中心控制節(jié)點(diǎn)完成的。如果要完成某個(gè)數(shù)據(jù)挖掘任務(wù)，則可以由空閑的網(wǎng)格節(jié)點(diǎn)先按挖掘需求來(lái)完成本節(jié)點(diǎn)的挖掘任務(wù)，再由網(wǎng)格中心控制節(jié)點(diǎn)來(lái)匯總每個(gè)節(jié)點(diǎn)的數(shù)據(jù)挖掘情況。局部網(wǎng)格節(jié)點(diǎn)管理的信息具有局限性，涉及的范圍較小，主要完成單個(gè)節(jié)點(diǎn)數(shù)據(jù)的管理，對(duì)局部的數(shù)據(jù)挖掘結(jié)果進(jìn)行匯總分析，但是這些局部節(jié)點(diǎn)的數(shù)據(jù)與全局節(jié)點(diǎn)的數(shù)據(jù)又是有一定關(guān)聯(lián)的。根據(jù)以上的分析可知，網(wǎng)格平臺(tái)下的數(shù)據(jù)挖掘任務(wù)由全局?jǐn)?shù)據(jù)挖掘與局部數(shù)據(jù)挖掘共同完成。

3.算法的Web Service設(shè)計(jì)

3.1 全局聚類算法的Web Service設(shè)計(jì)

網(wǎng)格環(huán)境下的全局控制網(wǎng)格節(jié)點(diǎn)與局部網(wǎng)格節(jié)點(diǎn)間的關(guān)系我們可以理解為上下層的關(guān)系，這樣就可以借鑒基于層次的聚類分析算法，按照層次的自底向上的聚類方式，把全局控制節(jié)點(diǎn)當(dāng)成是層次聚類的頂層。本課題全局聚類算法借鑒傳統(tǒng)的利用代表點(diǎn)聚類算法CURE.

CURE算法將層次方法與劃分方法結(jié)合到一起，選用有代表性的、固定數(shù)目的空間點(diǎn)來(lái)表示一個(gè)聚類。算法在開(kāi)始時(shí)，每個(gè)點(diǎn)都是一個(gè)簇，然后將距離最近的簇結(jié)合，一直到簇的個(gè)數(shù)為要求的K.首先把每個(gè)數(shù)據(jù)點(diǎn)即局部網(wǎng)格節(jié)點(diǎn)看成一個(gè)聚類，然后再以一個(gè)特定的收縮因子向中心收縮它們。

CURE算法的主要執(zhí)行步驟如下：

(1)從數(shù)據(jù)源樣本對(duì)象中隨機(jī)抽取樣本集，生成一個(gè)樣本集合S;

(2)將樣本集合S分割為一組劃分，每個(gè)劃分大小為S/p;

(3)對(duì)每個(gè)劃分部分進(jìn)行局部聚類;

(4)通過(guò)隨機(jī)采樣剔除聚類增長(zhǎng)太慢的異常數(shù)據(jù);

(5)對(duì)局部聚類進(jìn)行聚類，落在每個(gè)新形成的聚類中的代表性點(diǎn)，則根據(jù)用戶定義的收縮因子收縮或移向聚類中心;

(6)用相應(yīng)的標(biāo)記對(duì)聚類中的數(shù)據(jù)標(biāo)上聚類號(hào)。

有了數(shù)據(jù)挖掘算法，就可以完成數(shù)據(jù)挖掘任務(wù)了。全局聚類算法的主要功能是響應(yīng)用戶的數(shù)據(jù)挖掘請(qǐng)求，將對(duì)應(yīng)的請(qǐng)求發(fā)送給局部網(wǎng)格節(jié)點(diǎn)，將局部網(wǎng)格節(jié)點(diǎn)的挖掘結(jié)果整理輸出。全局聚類算法Web Service資源的結(jié)構(gòu)包括算法Web Service接口、算法資源屬性文檔、算法功能實(shí)現(xiàn)和算法功能發(fā)布四個(gè)部分。

利用傳統(tǒng)的聚類算法完成全局的數(shù)據(jù)的并行挖掘最重要的一步就是將全局聚類算法部署到GT4中，完成全局聚類算法的Web Service設(shè)計(jì)要經(jīng)過(guò)過(guò)以下幾步：

第一步：用WSDL(Web Service描述語(yǔ)言，是Web Service提供的XLM語(yǔ)言)來(lái)描述數(shù)據(jù)挖掘服務(wù)接口，該服務(wù)接口可以用Java來(lái)定義，利用Java-to-WSDL工具把Java定義的接口轉(zhuǎn)為WSDL文件。

第二步：用Java編寫全局聚類算法(CURE)代碼;

第三步：用WSDD配置文件和JNDI(GT4自帶文件)部署文件;

第四步：用Ant工具打包上面的所有文件，生成一個(gè)GAR文件;

第五步：向Web Service容器部署全局?jǐn)?shù)據(jù)挖掘服務(wù)。

3.2 局部聚類算法的Web Service設(shè)計(jì)

局部聚類算法的主要功能是完成局部網(wǎng)格節(jié)點(diǎn)的數(shù)據(jù)挖掘任務(wù)，并把數(shù)據(jù)挖掘結(jié)果上傳到全局控制節(jié)點(diǎn)。局部網(wǎng)格節(jié)點(diǎn)的數(shù)據(jù)挖掘任務(wù)與傳統(tǒng)的單機(jī)數(shù)據(jù)挖掘任務(wù)類似，本課題局部聚類算法使用傳統(tǒng)的聚類算法K-平均方法，以K為參數(shù)，把N個(gè)對(duì)象分為K個(gè)簇，簇內(nèi)具有較高的相似度，而簇間的相似度較低[34].本論文的數(shù)據(jù)挖掘任務(wù)主要是由局部網(wǎng)格節(jié)點(diǎn)實(shí)現(xiàn)的，下面就詳細(xì)的介紹K-平均算法的主要執(zhí)行過(guò)程如下：

(1)從數(shù)據(jù)集中任意選擇K個(gè)對(duì)象作為各個(gè)簇的初始中心。

(2)根據(jù)現(xiàn)有的簇中心情況，利用距離公式計(jì)算其他對(duì)象到各個(gè)簇中心的距離。(可選的距離公式有：歐幾里、行德公式、距離公式、曼哈坦距離公式、明考斯基距離公式)。

(3)根據(jù)所得各個(gè)對(duì)象的距離值，將對(duì)象分配給距離最近的中心所對(duì)應(yīng)的簇。

(4)重新生成各個(gè)簇的中心。

(5)判斷是否收斂。如果收斂，即簇不在發(fā)生變化，那么停止劃分，否則，重復(fù)(2)到(5)。

K-平均算法是一個(gè)經(jīng)典的聚類算法，將K-平均算法部署到GT4中，完成局部聚類算法的Web Service設(shè)計(jì)，部署方法與全局算法相似。

4.結(jié)論

基于GT4的數(shù)據(jù)挖掘系統(tǒng)中的數(shù)據(jù)挖掘服務(wù)資源有網(wǎng)格的中心控制節(jié)點(diǎn)(即全局節(jié)點(diǎn))進(jìn)行統(tǒng)一的管理，在局部網(wǎng)格節(jié)點(diǎn)挖掘過(guò)程中，根據(jù)其處理能力分配最佳的數(shù)據(jù)集給局部節(jié)點(diǎn)，從而使整個(gè)系統(tǒng)的計(jì)算負(fù)載相對(duì)均衡。其數(shù)據(jù)挖掘系統(tǒng)的規(guī)?？呻S著服務(wù)的多少動(dòng)態(tài)伸縮。當(dāng)系統(tǒng)要增加新的局部挖掘節(jié)點(diǎn)時(shí)，只需部署局部Web Service資源即可。將網(wǎng)格應(yīng)用到分布式數(shù)據(jù)挖掘系統(tǒng)中，建立一個(gè)基于網(wǎng)格的數(shù)據(jù)挖掘系統(tǒng)，必將使其在各個(gè)領(lǐng)域都得到廣泛的應(yīng)用。