GT4的聚類分析算法分析

1、【W(wǎng)ord版本下載可任意編輯】 GT4的聚類分析算法分析 1.引言 計算機網(wǎng)絡技術的普及與應用給人們的生活帶來了翻天覆地的變化，同時在網(wǎng)絡上產(chǎn)生了大量雜亂無章的數(shù)據(jù)。而網(wǎng)格技術、Web技術的發(fā)展，為人們從分布的網(wǎng)絡資源中尋找有價值的信息提供了新的技術支持，同時也產(chǎn)生了許多基于網(wǎng)格的數(shù)據(jù)挖掘系統(tǒng)。而數(shù)據(jù)挖掘算法又是決定一個數(shù)據(jù)挖掘系統(tǒng)性能的主要衡量指標。任何軟件系統(tǒng)的設計都離不開算法，數(shù)據(jù)挖掘技術的執(zhí)行效率也與數(shù)據(jù)挖掘算法有關，隨著數(shù)據(jù)庫技術與數(shù)據(jù)挖掘技術的成熟與發(fā)展，像分類、聚類、決策樹、關聯(lián)等等數(shù)據(jù)挖掘算法已相當成熟，可以研究借鑒現(xiàn)有數(shù)據(jù)挖掘方法、數(shù)據(jù)挖掘模式、數(shù)據(jù)挖掘流程，建立一個基于網(wǎng)格

2、的數(shù)據(jù)挖掘系統(tǒng)。筆者以眾多數(shù)據(jù)挖掘算法中的聚類分析算法為例，介紹基于GT4（Globus Tookit 4.0的簡稱，GT4的開發(fā)工具包（Java Web Service Core）的數(shù)據(jù)挖掘算法的設計過程。 聚類分析（Clustering Analysis）是一個應用比較廣泛的數(shù)據(jù)挖掘算法，算法的理論研究與實踐應用都已經(jīng)很成熟，把這一成熟的理論應用于基于網(wǎng)格的分布式系統(tǒng)中，會大大提高數(shù)據(jù)挖掘的效率。本文主要研究如何將聚類分析的CURE（Cluster Using Representation）算法和K-平均方法算法應用于基于GT4數(shù)據(jù)挖掘系統(tǒng)中。 2.系統(tǒng)構造設計 基于GT4數(shù)據(jù)挖掘系統(tǒng)的數(shù)

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

4、，網(wǎng)格平臺下的數(shù)據(jù)挖掘任務由全局數(shù)據(jù)挖掘與局部數(shù)據(jù)挖掘共同完成。 3.算法的Web Service設計 3.1 全局聚類算法的Web Service設計 網(wǎng)格環(huán)境下的全局控制網(wǎng)格節(jié)點與局部網(wǎng)格節(jié)點間的關系我們可以理解為上下層的關系，這樣就可以借鑒基于層次的聚類分析算法，按照層次的自底向上的聚類方式，把全局控制節(jié)點當成是層次聚類的頂層。本課題全局聚類算法借鑒傳統(tǒng)的利用代表點聚類算法CURE. CURE算法將層次方法與劃分方法結合到一起，選用有代表性的、固定數(shù)目的空間點來表示一個聚類。算法在開始時，每個點都是一個簇，然后將距離近的簇結合，一直到簇的個數(shù)為要求的K.首先把每個數(shù)據(jù)點即局部網(wǎng)格節(jié)點看成

5、一個聚類，然后再以一個特定的收縮因子向中心收縮它們。 CURE算法的主要執(zhí)行步驟如下： （1）從數(shù)據(jù)源樣本對象中隨機抽取樣本集，生成一個樣本集合S; （2）將樣本集合S分割為一組劃分，每個劃分大小為S/p; （3）對每個劃分部分開展局部聚類； （4）通過隨機采樣剔除聚類增長太慢的異常數(shù)據(jù)； （5）對局部聚類開展聚類，落在每個新形成的聚類中的代表性點，則根據(jù)用戶定義的收縮因子收縮或移向聚類中心； （6）用相應的標記對聚類中的數(shù)據(jù)標上聚類號。 有了數(shù)據(jù)挖掘算法，就可以完成數(shù)據(jù)挖掘任務了。全局聚類算法的主要功能是響應用戶的數(shù)據(jù)挖掘請求，將對應的請求發(fā)送給局部網(wǎng)格節(jié)點，將局部網(wǎng)格節(jié)點的挖掘結果整理輸出

6、。全局聚類算法Web Service資源的構造包括算法Web Service接口、算法資源屬性文檔、算法功能實現(xiàn)和算法功能發(fā)布四個部分。 利用傳統(tǒng)的聚類算法完成全局的數(shù)據(jù)的并行挖掘重要的一步就是將全局聚類算法部署到GT4中，完成全局聚類算法的Web Service設計要經(jīng)過過以下幾步： 步：用WSDL（Web Service描述語言，是Web Service提供的XLM語言）來描述數(shù)據(jù)挖掘服務接口，該服務接口可以用Java來定義，利用Java-to-WSDL工具把Java定義的接口轉(zhuǎn)為WSDL文件。 第二步：用Java編寫全局聚類算法（CURE）代碼； 第三步：用WSDD配置文件和JNDI（G

7、T4自帶文件）部署文件； 第四步：用Ant工具打包上面的所有文件，生成一個GAR文件； 第五步：向Web Service容器部署全局數(shù)據(jù)挖掘服務。 3.2 局部聚類算法的Web Service設計 局部聚類算法的主要功能是完成局部網(wǎng)格節(jié)點的數(shù)據(jù)挖掘任務，并把數(shù)據(jù)挖掘結果上傳到全局控制節(jié)點。局部網(wǎng)格節(jié)點的數(shù)據(jù)挖掘任務與傳統(tǒng)的單機數(shù)據(jù)挖掘任務類似，本課題局部聚類算法使用傳統(tǒng)的聚類算法K-平均方法，以K為參數(shù)，把N個對象分為K個簇，簇內(nèi)具有較高的相似度，而簇間的相似度較低.本論文的數(shù)據(jù)挖掘任務主要是由局部網(wǎng)格節(jié)點實現(xiàn)的，下面就詳細的介紹K-平均算法的主要執(zhí)行過程如下： （1）從數(shù)據(jù)集中任意選擇K個對

8、象作為各個簇的初始中心。 （2）根據(jù)現(xiàn)有的簇中心情況，利用距離公式計算其他對象到各個簇中心的距離。（可選的距離公式有：歐幾里、行德公式、距離公式、曼哈坦距離公式、明考斯基距離公式）。 （3）根據(jù)所得各個對象的距離值，將對象分配給距離近的中心所對應的簇。 （4）重新生成各個簇的中心。 （5）判斷是否收斂。如果收斂，即簇不在發(fā)生變化，那么停止劃分，否則，重復（2）到（5）。 K-平均算法是一個經(jīng)典的聚類算法，將K-平均算法部署到GT4中，完成局部聚類算法的Web Service設計，部署方法與全局算法相似。 4.結論 基于GT4的數(shù)據(jù)挖掘系統(tǒng)中的數(shù)據(jù)挖掘服務資源有網(wǎng)格的中心控制節(jié)點（即全局節(jié)點）開展統(tǒng)一的管理，在局部網(wǎng)格節(jié)點挖掘過程中，根據(jù)其處理能力分配的數(shù)據(jù)集給局部節(jié)點，從而使整個系統(tǒng)的計算