基于GT4的聚類分析算法研究

【摘要】本論文的研究視角是當前比較熱門的兩個問題：網格技術和數據挖掘技術。將網格計算和數據挖掘技術結合起來，開發基于網格的數據系統，借鑒傳統聚類分析算法CLUQ和K_平均值算法，設計基于網格的全局和局部算法的Web Service形式。

【關鍵詞】GT4；Web Service；聚類分析

1.引言

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

聚類分析（Clustering Analysis）是一個應用比較廣泛的數據挖掘算法，算法的理論研究與實踐應用都已經很成熟，把這一成熟的理論應用于基于網格的分布式系統中，會大大提高數據挖掘的效率。本文主要研究如何將聚類分析的CURE（Cluster Using Representation）算法和K-平均方法算法應用于基于GT4數據挖掘系統中。

2.系統結構設計

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

3.算法的Web Service設計

3.1 全局聚類算法的Web Service設計

網格環境下的全局控制網格節點與局部網格節點間的關系我們可以理解為上下層的關系，這樣就可以借鑒基于層次的聚類分析算法，按照層次的自底向上的聚類方式，把全局控制節點當成是層次聚類的頂層。本課題全局聚類算法借鑒傳統的利用代表點聚類算法CURE。

CURE算法將層次方法與劃分方法結合到一起，選用有代表性的、固定數目的空間點來表示一個聚類。算法在開始時，每個點都是一個簇，然后將距離最近的簇結合，一直到簇的個數為要求的K。首先把每個數據點即局部網格節點看成一個聚類，然后再以一個特定的收縮因子向中心收縮它們。

CURE算法的主要執行步驟如下：

（1）從數據源樣本對象中隨機抽取樣本集，生成一個樣本集合S；

（2）將樣本集合S分割為一組劃分，每個劃分大小為S/p；

（3）對每個劃分部分進行局部聚類；

（4）通過隨機采樣剔除聚類增長太慢的異常數據；

（5）對局部聚類進行聚類，落在每個新形成的聚類中的代表性點，則根據用戶定義的收縮因子收縮或移向聚類中心；

（6）用相應的標記對聚類中的數據標上聚類號。

有了數據挖掘算法，就可以完成數據挖掘任務了。全局聚類算法的主要功能是響應用戶的數據挖掘請求，將對應的請求發送給局部網格節點，將局部網格節點的挖掘結果整理輸出。全局聚類算法Web Service資源的結構包括算法Web Service接口、算法資源屬性文檔、算法功能實現和算法功能發布四個部分。

利用傳統的聚類算法完成全局的數據的并行挖掘最重要的一步就是將全局聚類算法部署到GT4中，完成全局聚類算法的Web Service設計要經過過以下幾步：

第一步：用WSDL（Web Service描述語言，是Web Service提供的XLM語言）來描述數據挖掘服務接口，該服務接口可以用Java來定義，利用Java-to-WSDL工具把Java定義的接口轉為WSDL文件。

第二步：用Java編寫全局聚類算法（CURE）代碼；

第三步：用WSDD配置文件和JNDI（GT4自帶文件）部署文件；

第四步：用Ant工具打包上面的所有文件，生成一個GAR文件；

第五步：向Web Service容器部署全局數據挖掘服務。

3.2 局部聚類算法的Web Service設計

局部聚類算法的主要功能是完成局部網格節點的數據挖掘任務，并把數據挖掘結果上傳到全局控制節點。局部網格節點的數據挖掘任務與傳統的單機數據挖掘任務類似，本課題局部聚類算法使用傳統的聚類算法K-平均方法，以K為參數，把N個對象分為K個簇，簇內具有較高的相似度，而簇間的相似度較低[34]。本論文的數據挖掘任務主要是由局部網格節點實現的，下面就詳細的介紹K-平均算法的主要執行過程如下：

（1）從數據集中任意選擇K個對象作為各個簇的初始中心。

（2）根據現有的簇中心情況，利用距離公式計算其他對象到各個簇中心的距離。（可選的距離公式有：歐幾里、行德公式、距離公式、曼哈坦距離公式、明考斯基距離公式）。

（3）根據所得各個對象的距離值，將對象分配給距離最近的中心所對應的簇。

（4）重新生成各個簇的中心。

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

K-平均算法是一個經典的聚類算法，將K-平均算法部署到GT4中，完成局部聚類算法的Web Service設計，部署方法與全局算法相似。

4.結論

基于GT4的數據挖掘系統中的數據挖掘服務資源有網格的中心控制節點（即全局節點）進行統一的管理，在局部網格節點挖掘過程中，根據其處理能力分配最佳的數據集給局部節點，從而使整個系統的計算負載相對均衡。其數據挖掘系統的規模可隨著服務的多少動態伸縮。當系統要增加新的局部挖掘節點時，只需部署局部Web Service資源即可。將網格應用到分布式數據挖掘系統中，建立一個基于網格的數據挖掘系統，必將使其在各個領域都得到廣泛的應用。

參考文獻

[1]薛勝軍，馬廷淮，劉文杰.Globus Tookit 4：Java網格服務編程[M].北京：清華大學出版社，2009.

[2]劉敏娟.基于網格的聚類算法分析研究[D].鄭州：鄭州大學，2007.

[3]陶樹平，錢挺.一種網格平臺數據挖掘服務模式及其算法[J].計算機工程，2005，31（5）：109-111.