田 野，彭利標(biāo)

（天津理工大學(xué) 中環(huán)信息學(xué)院，天津 300380）

聚類算法是大規(guī)模數(shù)據(jù)處理應(yīng)用中的一個(gè)非常重要的研究領(lǐng)域，現(xiàn)階段聚類分析算法的應(yīng)用的非常廣泛，其目標(biāo)是在沒有先驗(yàn)知識的前提下，以數(shù)據(jù)對象之間的相似程度為根據(jù)將數(shù)據(jù)聚合成若干不同的簇，使同一個(gè)簇中的數(shù)據(jù)對象盡可能相似，不同簇中的數(shù)據(jù)對象差別盡可能的大[1]。由于聚類算法可以應(yīng)用于事先未知的情況，所以特別適合無需人工干預(yù)的挖掘過程。而且聚類算法作為數(shù)據(jù)挖掘系統(tǒng)中的一個(gè)重要部分，既可以作為一個(gè)單獨(dú)的工具挖掘數(shù)據(jù)庫元素分布的深層信息，也可以作為先進(jìn)數(shù)據(jù)挖掘算法的一個(gè)預(yù)處理步驟[2]。

分布式數(shù)據(jù)挖掘的研究是近幾年提出的一個(gè)新的研究領(lǐng)域，旨在解決當(dāng)前分布式的環(huán)境下，提供從數(shù)據(jù)的海洋中獲取感興趣的知識的有效的途徑，也是目前解決在Internet中發(fā)現(xiàn)知識的最佳方法之一，應(yīng)用前景非常廣闊。從廣義上講，分布式環(huán)境中應(yīng)用的數(shù)據(jù)挖掘都可稱為分布式數(shù)據(jù)挖掘[3]。實(shí)際上，很多研究人員都已經(jīng)展開研究，對分布式的關(guān)聯(lián)規(guī)則算法，分布式分類算法，以及分布式聚類算法等的研究已經(jīng)取得了一些成果。但必須注意到的是，無線和有線通信技術(shù)以及計(jì)算機(jī)技術(shù)的飛速發(fā)展，使分布式計(jì)算環(huán)境在各個(gè)領(lǐng)域廣泛存在，現(xiàn)有的大多數(shù)聚類方法在數(shù)據(jù)量小、集中的情況下是有效的，對于大規(guī)模數(shù)據(jù)的、分布式的數(shù)據(jù)處理不能很好的適應(yīng)。分布式聚類技術(shù)的研究雖然已經(jīng)有了發(fā)展，但現(xiàn)階段分布式聚類的研究還屬于數(shù)據(jù)挖掘領(lǐng)域里一個(gè)比較前沿的新方向，其研究還處于基礎(chǔ)性階段，有很多問題亟待解決。

1 基于代理的分布式聚類模型

從體系架構(gòu)上來講，目前的分布式數(shù)據(jù)挖掘系統(tǒng)采用兩類模型[4]：C/S模型和基于代理（agent-based）模型。其中基于代理的挖掘模型的特點(diǎn)是分布式數(shù)據(jù)挖掘系統(tǒng)的局部數(shù)據(jù)聚類分析需要在每個(gè)數(shù)據(jù)站點(diǎn)使用一個(gè)或多個(gè)代理來進(jìn)行，并與其他的代理進(jìn)行通訊，在該過程中需要一個(gè)具有指導(dǎo)性代理的適配器來協(xié)助整個(gè)挖掘[5]。由于傳統(tǒng)的代理挖掘模型最終仍需要將局部的所有結(jié)果集中到一個(gè)中心站點(diǎn)執(zhí)行，而中心站點(diǎn)的內(nèi)存不一定能滿足龐大數(shù)據(jù)量的要求，即便是滿足足夠內(nèi)存同時(shí)也會帶來較大的通訊開銷。 圖1描述了一個(gè)基于代理的分布式數(shù)據(jù)挖掘模型的結(jié)構(gòu)。這種基于代理的結(jié)構(gòu)能夠?qū)嫶髲?fù)雜的計(jì)算任務(wù)分配給代理系統(tǒng)，客戶端可以從復(fù)雜的邏輯處理中解放出來，只關(guān)心聚類的結(jié)果，而不必去關(guān)心聚類的具體細(xì)節(jié)，大大提高了模型的聚類效率和可移植性。

圖1 基于代理的分布式數(shù)據(jù)挖掘模Fig.1 Agent-based distributed data mining model

目前，在基于代理的聚類模型中存在一種增量集成的分布式數(shù)據(jù)挖掘模型（II DDM），這種模型的本質(zhì)是通過利用增量學(xué)習(xí)的思想，集成兩個(gè)站點(diǎn)的聚類結(jié)果，根據(jù)得出的局部結(jié)果，集成他們的增量。II DDM模型的設(shè)計(jì)思想是基于模型伸縮性的考慮，此模型對于任何數(shù)量的數(shù)據(jù)源都具有較好的伸縮性。典型的模型結(jié)構(gòu)如圖2所示，在該模型中使用多個(gè)移動代理知識集成器增量的組合，得出的每兩個(gè)站點(diǎn)的挖掘結(jié)果，一般而言將小的局部站點(diǎn)聚類結(jié)果遷移到更大的局部站點(diǎn)結(jié)果中去，從而優(yōu)化結(jié)果集[6]。

圖2 典型的II DDM模型Fig.2 II DDM model

增量集成分布式數(shù)據(jù)挖掘模型工作過程一般可分為以下3個(gè)階段。1）準(zhǔn)備階段，首先，客戶端向需要執(zhí)行數(shù)據(jù)聚類任務(wù)的服務(wù)器廣播移動代理數(shù)據(jù)挖掘器和移動代理知識集成器；2）聚類分析階段，在每個(gè)局部站點(diǎn)的數(shù)據(jù)服務(wù)器上執(zhí)行數(shù)據(jù)對象的聚類分析，生成該站點(diǎn)的局部聚類結(jié)果集；3）集成階段，在數(shù)據(jù)服務(wù)器上執(zhí)行增量集成技術(shù)將小的局部站點(diǎn)聚類結(jié)果遷移到更大的局部站點(diǎn)結(jié)果中去，以此來減小局部站點(diǎn)間的結(jié)果遷移代價(jià)。

2 II DDM模型存在的問題

分析II DDM模型，可以知道，該模型不但繼承了一般多代理模型之間可以協(xié)作執(zhí)行任務(wù)、彼此進(jìn)行信息傳遞的特點(diǎn)，從而完成復(fù)雜的大規(guī)模數(shù)據(jù)挖掘任務(wù)。還繼承了移動代理系統(tǒng)的獨(dú)立自主性，這是由移動代理本身的特點(diǎn)決定的。移動代理系統(tǒng)可以在自己的生存周期中自行控制挖掘的起點(diǎn)和終點(diǎn)，實(shí)時(shí)掌握自身的運(yùn)行狀態(tài)，并且能夠在新的節(jié)點(diǎn)中從掛起狀態(tài)自動恢復(fù)并繼續(xù)運(yùn)行。

與傳統(tǒng)的基于移動代理模型不同的是，II DDM模型本質(zhì)上并不是向集成代理傳遞所有獲得的數(shù)據(jù)服務(wù)器局部聚類結(jié)果，而是通過控制服務(wù)器聚類結(jié)果之間不斷的從小到大的遷移，來進(jìn)行增量的集成，直到最后將一次集成得到的結(jié)果傳遞給客戶端?？梢哉f這種方式克服基于傳統(tǒng)移動代理的挖掘模型的不足，它所具備對任意數(shù)量的數(shù)據(jù)站點(diǎn)具有伸縮性的優(yōu)點(diǎn)。

正是由于II DDM模型上述的那些優(yōu)點(diǎn)，使它非常適合應(yīng)用于分布式聚類系統(tǒng)。但是，傳統(tǒng)的基于代理的分布式數(shù)據(jù)挖掘模型，仍然存在著需要將全部的局部站點(diǎn)聚類結(jié)果集中到一個(gè)服務(wù)器上進(jìn)行聚類的缺點(diǎn)，服務(wù)器的性能成為整個(gè)系統(tǒng)的瓶頸。改進(jìn)的II DDM模型雖然在某種程度上緩解了這個(gè)矛盾，但是其實(shí)質(zhì)也是通過個(gè)體式合作方式來進(jìn)行代理間的協(xié)作，且是串行集成的工作模式?？蛻舳艘獔?zhí)行聚類任務(wù)的過程中不可避免的被要求與全部需要執(zhí)行挖掘任務(wù)的服務(wù)器進(jìn)行通信，還要將挖掘代理以及集成代理廣播給所有相應(yīng)的數(shù)據(jù)服務(wù)器，對整個(gè)網(wǎng)絡(luò)的帶寬要求很高，時(shí)間開銷也很大。不僅如此，在挖掘任務(wù)執(zhí)行之后，相應(yīng)的服務(wù)器又需要將結(jié)果集全部反饋給客戶端。經(jīng)過上面的分析，可以想象的到當(dāng)站點(diǎn)數(shù)量非常龐大時(shí)，通訊開銷也會是難以接受的，而且存在響應(yīng)效率大大降低的可能性，可見這種有賴于個(gè)體式的合作方式自身存在一定的不足。

沿著這個(gè)思路，在本章基于II DDM模型的，引入層次的設(shè)計(jì)思想，提出一種新的基于代理的層次式增量集成分布式數(shù)據(jù)挖掘模型，記作HII DDM。該模型是利用分治策略將復(fù)雜的大問題分解成小問題進(jìn)行解決，以此來克服II DDM模型個(gè)體合作方式的不足。在實(shí)際應(yīng)用中可以根據(jù)站點(diǎn)服務(wù)器的分布、局域網(wǎng)絡(luò)帶寬等來將整個(gè)系統(tǒng)劃分為若干子系統(tǒng)。每個(gè)子系統(tǒng)在利用II DDM模型進(jìn)行學(xué)習(xí)之后，生成一個(gè)模型，新的模型將作為整個(gè)系統(tǒng)的數(shù)據(jù)節(jié)點(diǎn)，再利用II DDM模型進(jìn)行學(xué)習(xí)生成最終的模型。用這種層次式的方法生成最終的模型較前面兩種傳統(tǒng)的模型而言具有更好的伸縮性，執(zhí)行起來更加高效，并有效降低網(wǎng)絡(luò)通信。最后，基于本章提出的新模型提出一種新型的分布式聚類算法。為是解決站點(diǎn)數(shù)量龐大的數(shù)據(jù)挖掘問題提供了一個(gè)新的思路。

3 層次式增量集成分布式聚類模型的設(shè)計(jì)與實(shí)現(xiàn)

將分層的思想引入之后，可將層次式增量集成分布式聚類模型整體工作過程劃分為4個(gè)階段。

1）準(zhǔn)備階段，在這個(gè)階段客戶端將移動代理數(shù)據(jù)挖掘器和移動代理知識集成器廣播給每個(gè)子系統(tǒng)，而不是直接分給數(shù)據(jù)服務(wù)器；2）聚類分析階段，在這個(gè)階段每個(gè)子系統(tǒng)選擇合適的聚類算法在節(jié)點(diǎn)間執(zhí)行聚類任務(wù)，生成局部挖掘的結(jié)果；3）子系統(tǒng)集成階段，移動代理知識集成器利用增量集成技術(shù)在各個(gè)子系統(tǒng)上并行進(jìn)行結(jié)果集成，生成子系統(tǒng)的挖掘結(jié)果；4）全局集成階段，移動代理知識集成器利用增量集成技術(shù)集成各個(gè)子系統(tǒng)生成的局部聚類結(jié)果，生成全局聚類模型并傳遞給知識集成器客戶端。其結(jié)構(gòu)圖見圖3所示。

圖3 HII分布式數(shù)據(jù)挖掘模型整體結(jié)構(gòu)圖Fig.3 HII distributed data mining models overall structure

在層次式增量集成分布式數(shù)據(jù)挖掘模型中，第一層為子系統(tǒng)層，該層為每個(gè)子系統(tǒng)設(shè)計(jì)一個(gè)適配器來充當(dāng)子系統(tǒng)的客戶端，向相應(yīng)的子系統(tǒng)中需要進(jìn)行聚類任務(wù)的數(shù)據(jù)服務(wù)器分配數(shù)據(jù)挖掘器；在聚類任務(wù)執(zhí)行完畢后，各個(gè)數(shù)據(jù)服務(wù)器再將得到的局部聚類結(jié)果反饋回適配器。第二層為由小系統(tǒng)組成的大系統(tǒng)層，即全局聚類層，在這一層適配器又充當(dāng)集成服務(wù)器和通信代理的角色，傳遞和集成各子系統(tǒng)的局部聚類結(jié)果，最終將全局的聚類結(jié)果送回給整個(gè)系統(tǒng)的客戶端。

將分層的思想引入基于代理的分布式聚類模型中，是提高分布式聚類模型伸縮性，高效性的有效途徑。但是如何劃分系統(tǒng)的層次才能使整個(gè)系統(tǒng)運(yùn)作更易實(shí)現(xiàn)、更加高效，是一個(gè)非常關(guān)鍵的問題。絕大多數(shù)實(shí)際應(yīng)用中網(wǎng)絡(luò)節(jié)點(diǎn)的地理分布特征不是隨意的分布在不同地方，而是在幾個(gè)地方集中分布，節(jié)點(diǎn)間連接方式多樣化，連接帶寬差異化。例如，用高速的局域網(wǎng)連接在同一個(gè)地點(diǎn)或同一組織中分布的節(jié)點(diǎn)，會比用遠(yuǎn)程網(wǎng)、互聯(lián)網(wǎng)甚至無線網(wǎng)連接的不同地點(diǎn)間或不同組織中分布的節(jié)點(diǎn)，在網(wǎng)絡(luò)傳輸?shù)陌踩?、傳輸?shù)乃俾史矫娓叩亩啵谕ㄐ糯鷥r(jià)方面卻低得多。因此，在設(shè)計(jì)分布式聚類模型時(shí)，應(yīng)該盡量在局域網(wǎng)內(nèi)完成聚類的通訊和計(jì)算，盡可能的減少廣域網(wǎng)間的網(wǎng)絡(luò)通訊。

沿著這個(gè)設(shè)計(jì)思路，將系統(tǒng)劃分的方式定為，分布在一個(gè)地點(diǎn)或若干個(gè)相近地點(diǎn)的節(jié)點(diǎn)作為一個(gè)子系統(tǒng)。這樣，各個(gè)子系統(tǒng)可以高效執(zhí)行聚類運(yùn)算，提高子系統(tǒng)數(shù)據(jù)挖掘的效率，將子系統(tǒng)之間的通信工作交給專業(yè)的、強(qiáng)大的代理系統(tǒng)執(zhí)行，從而使整個(gè)系統(tǒng)的執(zhí)行效率大大提高，通訊代價(jià)最大程度的降低，系統(tǒng)的安全性也得到明顯改善。

假設(shè)一個(gè)分布式系統(tǒng)由P個(gè)節(jié)點(diǎn)組成，全部的P個(gè)節(jié)點(diǎn)在g個(gè)站點(diǎn)間集中分布（這里有一個(gè)隱含的假設(shè)前提是每個(gè)站點(diǎn)內(nèi)部的節(jié)點(diǎn)是由高速局域網(wǎng)連接的），設(shè)在第i個(gè)站點(diǎn)中的節(jié)點(diǎn)數(shù)目為ni，則有個(gè)節(jié)點(diǎn)按照所在站點(diǎn)進(jìn)行劃分，并組成一個(gè)相應(yīng)的子系統(tǒng)，記作S1，S2，…，Sg?；诰W(wǎng)絡(luò)分布、帶寬和安全性方面的實(shí)際考慮，根據(jù)這個(gè)定義對分布式系統(tǒng)進(jìn)行劃分旨在做到子系統(tǒng)內(nèi)的節(jié)點(diǎn)緊耦合，子系統(tǒng)間是松耦合。當(dāng)然這個(gè)劃分規(guī)則不是一成不變的，可以根據(jù)實(shí)際情況靈活選擇。如果某個(gè)子系統(tǒng)的節(jié)點(diǎn)數(shù)量達(dá)到了一定的程度，也可以根據(jù)實(shí)際情況將同一站點(diǎn)的節(jié)點(diǎn)再分為若干子系統(tǒng)；另一方面，如果幾個(gè)站點(diǎn)的節(jié)點(diǎn)數(shù)量足夠的小，且不同站點(diǎn)間的網(wǎng)絡(luò)連接速度足夠的快，也可以將相應(yīng)的幾個(gè)站點(diǎn)的節(jié)點(diǎn)集成一個(gè)子系統(tǒng)。

根據(jù)規(guī)則劃分好子系統(tǒng)之后，采用II DDM模型進(jìn)行聚類分析。模型中的數(shù)據(jù)挖掘算法可以采用DK-Dmeans算法，當(dāng)然也可以根據(jù)實(shí)際情況選取其他的分布式聚類算法，此模型具有很好的靈活性。在各個(gè)子系統(tǒng)上通過一遍遍歷數(shù)據(jù)后根據(jù)增量集成規(guī)則建立子系統(tǒng)模型，如圖4所示。

圖4 HII子系統(tǒng)Sj聚類模型Fig.4 HII subsystem Sj clustering model

在子系統(tǒng)模型建立之前的準(zhǔn)備是根據(jù)客戶端的數(shù)據(jù)挖掘請求來決定需要進(jìn)行聚類的子系統(tǒng)。之后客戶端會將移動代理數(shù)據(jù)挖掘器和移動代理知識集成器發(fā)送給需要進(jìn)行聚類分析的子系統(tǒng)的適配器，再由適配器分發(fā)給其所在系統(tǒng)的服務(wù)器。該子系統(tǒng)中，每個(gè)數(shù)據(jù)服務(wù)器執(zhí)行挖掘任務(wù)，將得到的聚類結(jié)果的聚簇中心點(diǎn)以及相應(yīng)簇的大小反饋給適配器，適配器會對得到的信息進(jìn)行比較，然后發(fā)送控制命令，將較小的聚類結(jié)果遷移到更大聚類結(jié)果的服務(wù)器上，并在更大結(jié)果的服務(wù)器上執(zhí)行集成。迭代執(zhí)行上述步驟，直到所有的聚類結(jié)果被遷移到一個(gè)服務(wù)器上得到最終的聚類結(jié)果。最后這個(gè)服務(wù)器將聚類結(jié)果發(fā)送給適配器。

在本章提出的模型中，全局模型的建立并不是將局部模型的聚類結(jié)果進(jìn)行簡單了累加，由于是分層的思想，所以在整個(gè)系統(tǒng)的第二層，即全局聚類層，也和子系統(tǒng)一樣，通過增量集成模型建立全局模型，與子系統(tǒng)模型不同的是在第二層的聚類模型中，子系統(tǒng)充當(dāng)了數(shù)據(jù)源的角色。這樣就可以明顯的看出，引入分層的思想后，克服了II DDM模型串行的、個(gè)體協(xié)同合作執(zhí)行方式的弊端，在全局聚類的這一層是并行的合作方式。全局聚類的模型如圖5所示。

圖5 HII全局聚類模型Fig.5 The HII global clustering model

全局模型和子系統(tǒng)模型的工作過程幾乎是一樣，只不過在這一層適配器是將將生成結(jié)果大小送給客戶端，由客戶端發(fā)送將小的聚類結(jié)果遷移到大的聚類結(jié)果的適配器上的控制命令，之后在駐留有大的聚類結(jié)果的適配器上執(zhí)行子系統(tǒng)聚類結(jié)果的集成。上述步驟迭代執(zhí)行，直到所有適配器聚類結(jié)果被集成到一個(gè)適配器中。此適配器將最后一次集成的結(jié)果發(fā)送給客戶端。在整個(gè)系統(tǒng)模型的聚類過程中，由于是并行的執(zhí)行，各個(gè)子系統(tǒng)可能由于網(wǎng)絡(luò)帶寬，網(wǎng)絡(luò)延時(shí)等問題造成不能同步完成聚類計(jì)算。這是，整個(gè)系統(tǒng)的聚類就會出現(xiàn)協(xié)同問題，解決這個(gè)問題的方法是，可以在客戶端發(fā)送控制命令的同時(shí)也發(fā)送一個(gè)時(shí)間戳給各個(gè)子系統(tǒng)，這樣就可以保證是同一次迭代的結(jié)果被集成代理進(jìn)行集成了。

4 基于HII模型的分布式聚類算法

在上一節(jié)中完成了HII DDM模型的設(shè)計(jì)和建立，現(xiàn)在在建立好的模型基礎(chǔ)上，來實(shí)現(xiàn)基于該模型的分布式聚類算法。根據(jù)模型的劃分規(guī)則，將分布在多個(gè)站點(diǎn)的數(shù)據(jù)庫劃分為若干子數(shù)據(jù)庫，并且在每個(gè)子數(shù)據(jù)庫中選擇一個(gè)性能好的服務(wù)器充當(dāng)適配器，模型中可以應(yīng)用多種分布式算法，在本節(jié)選擇上一章的DK-Dmeans算法，下面是新算法的描述。

基于HII DDM的分布式聚類算法：

第一層對子系統(tǒng)j：

實(shí)際上，基于HII DDM模型的分布式聚類算法由于采用了層次式增量集成的方式，其算法的開銷也應(yīng)該分為兩層來計(jì)算。根據(jù)模型的工作過程，在子系統(tǒng)聚類層，時(shí)間的開銷包括以下幾個(gè)方面，1）適配器向數(shù)據(jù)服務(wù)器傳送挖掘器和集成器的時(shí)間；2）子系統(tǒng)各個(gè)站點(diǎn)執(zhí)行K-means聚類算法的時(shí)間；3）服務(wù)器之間的通信時(shí)間；4）增量集成的時(shí)間；5）向適配器傳遞最后結(jié)果的時(shí)間。

同子系統(tǒng)時(shí)間開銷的分析過程一樣，全局聚類層的時(shí)間開銷包括以下幾個(gè)方面，1）客戶端發(fā)送挖掘器和集成器的時(shí)間；2）適配器之間的通信時(shí)間；3）增量集成時(shí)間；4）適配器向客戶端最后傳遞結(jié)果的時(shí)間。綜上所述，本算法的時(shí)間開銷=子系統(tǒng)聚類執(zhí)行時(shí)間+全局聚類執(zhí)行時(shí)間。

5 結(jié)束語

本章首先分析了基于代理的II DDM聚類模型的優(yōu)勢與劣勢，在此基礎(chǔ)上將分層思想引入，提出了在基于代理的層次式增量集成的分布式數(shù)據(jù)挖掘模型HII DDM，其核心思想是，將整個(gè)系統(tǒng)劃分為兩層。在子系統(tǒng)層根據(jù)所有數(shù)據(jù)節(jié)點(diǎn)，用II DDM模型生成相應(yīng)子系統(tǒng)的聚類結(jié)果；在全局聚類層，再用II DDM模型生成整個(gè)系統(tǒng)的聚類結(jié)果。分層后克服了原模型個(gè)體合作和串行工作方式的缺點(diǎn)。之后在HII DDM模型的基礎(chǔ)上提出了基于該模型的分布式聚類算法。基于此模型的算法不但繼承了傳統(tǒng)的基于代理模型算法在健壯性和高效性而且還很靈活，文章中是基于兩層模型的算法，但不僅限于兩層，在更大規(guī)?；驍?shù)據(jù)庫更分布的情況下，還可以分為更多層。分層模型是改善超大規(guī)模數(shù)據(jù)集的伸縮性和效率問題的非常有效的途徑。

[1]HAN Jia-wei，Kamber M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，等譯.北京：機(jī)械工業(yè)出版社，2008.

[2]Hand D，Mannila H.數(shù)據(jù)挖掘原理[M].張銀奎，等譯.北京：機(jī)械工業(yè)出版社，2007

[3]Januzaj，Brecheisen S，Kriegel H P，et al.Visually mining through cluster hierarchies[C].Proc.Of SIAM Int’l Conf.on Data Mining Orlando，2011.

[4]Johnson E，Kargupta H.Collective Hierarchical clustering from distributed heterogeneous data[J].Computer Science，2010（1759）：221－244，2010

[5]Kargupta H，Huang W Y，Sivakumar K，et al.Distributed clustering using collective principal component analysis[J].Knowledge and Information Systems，2011，3（4）：422－448.

[6]Charu C，Agrawal，Philip S.Yu.Finding generalized project Clusters in High-dimensional spaces[C].SIGMOD Conference，2010：70－81.