一種分布式的K-means聚類算法

摘 要:提出一種適用于大型數據集的分布式聚類算法。該算法以傳統的K-means算法為基礎進行合理的改進，使之更適用于分布式環境，并從算法的復雜度分析，將該算法與傳統的集中式K-means算法及其他分布式算法進行比較。實驗表明，該算法在保持了集中式K-means算法所有必要特性的同時，提高了數據處理速度。

關鍵詞:K-means聚類算法; 分布式環境; 大數據集; 復雜度

中圖分類號:TP393 文獻標識碼:A

文章編號:1004-373X(2010)10-0011-04

Distributed K-means Clustering Algorithm

LIANG Jian-wu， TIAN Ye

(School of Information Science and Engineering， Central South University， Changsha 410075， China)

Abstract:A distributed clustering algorithmsuit for large data setsis presented. This algorithm is a modified version of the common K-means algorithm with suitable change for making it executable in distributed environment. The algorithm， the traditional serial K-means algorithm and other existing algorithms are compared on the basis of analysing the complexity of the algorithm. Experimental results show that this distributed algorithm maintains all necessary characteristics of the serial K-means algorithm， as well improves the speed of data processing.

Keywords:K-means algorithm; distributed environment; large database; complexity

0 引 言

傳統聚類方法的一個前提是數據集中在一個站點，需要一次性載入內存。然而，在許多環境中，局域網、廣域網、Internet網將多個數據源連成一個大型分布式異構數據庫，用戶需要處理大量、多計算節點、不同地理分布的數據，并需要保護數據的隱私和安全[1]。集中式聚類算法不能很好地應用到分布式環境中，即使允許集中執行大量的數據，要么算法崩潰，要么執行效率太低，其長時間的執行，讓用戶難以接受。數據存儲方式的變化對聚類算法的并行性和分布化都提出了要求。分布式聚類是解決此問題的有效方法[2-3]。

分布式聚類是基于分布的數據源和計算資源對大規模、分布式的數據進行聚類分析的，是聚類分析進一步進化的結果，體現了并行計算、分布式計算和通信日益增長的趨勢。它的思想是:首先在個體站點數據執行局部聚類分析，然后將部分聚類結果作為產出送給其他站點，并聚集成最后的聚類結果。

本文基于分布式聚類的思想，以集中式的K-means算法為基礎，提出一種分布式的K-means算法。實驗結果表明，對于大規模數據庫，該算法比集中式的K-means算法具有更高的效率和更低的時間復雜度。

1 典型K-means算法

K-means算法是一種基于劃分的聚類算法，其任務是把數據集劃分成不相交的點集，使每個集中的點盡可能同質[4]，即給定N個數據點的集合P{p1，p2，...，pN}，聚類劃分的目標是找到K個聚類C{c1，c2，…，cK}，使每一個點pi被分配到惟一的一個聚類Cj。其中，Ci≠，i=1，2，…，K;Ci∩Cj=， i=1，2，…，K， j=1，2，…，K且i≠j;∪Ki=1Ci=S。

該算法的基本思想[5]是:給定一個包含N個數據對象的數據庫以及要生成的簇的數目K，隨機選取K個對象，每個對象的初始代表了1個簇的平均值或中心，然后計算其余各個樣本到每個聚類中心的距離，把該樣本歸到離它最近的那個聚類中心所在的簇，對調整后的新簇使用平均法計算新的聚類中心，如果相鄰2次的聚類中心沒有任何變化，說明樣本調整結束且聚類平方誤差準則函數E收斂，最后所有的數據對象存放在相應的類Cj中。

平方誤差準則定義如下:

E=∑Ki=1∑p∈cK|p-mi|2(1)

式中:E是數據庫中所有對象平方誤差的總和;p是空間中的點，表示數據對象;mi是簇Cj的平均值(p和mi都是多維的)。聚類的目標就是用式(1)使E的值達到最小。

算法1:集中式K-means

輸入:包含N個對象的數據庫和K值(K為整數);

輸出:K個簇，使平方準則最小。

方法:

(1) 隨機選取K個對象pj∈S作為初始聚類中心;

(2) 當 E 不穩定時，為每個K計算距離dij=|p-mi|2(1≤i≤K且 1≤j≤N);

(3) 根據點到 mi的最小距離將每個對象(重新)賦給最類似的簇;

(4) 計算新的平均值mi(1≤i≤K);

(5) 計算 E，直到 E值穩定。

K-means算法的復雜度由O(TKN)表示，其中K是期望的聚類簇的個數，T是迭代次數，N是數據對象的個數。

2 分布式K-means聚類算法

如果仔細觀察K-means算法的過程，不難發現K-means本身就蘊含了分布式思想，其過程是由一個數據集合和一組隨機的聚類中心開始的，在每一次迭代過程中都要將每個對象分配給離它最近的簇。只是這種方式是由單一的處理器執行K-means算法，處理器的內存中必須包含了所有簇的結構，并重復算法步驟直到估算出最終的聚類中心mi。然而分布式的環境中，是通過網絡連接若干處理器(站點)來執行K-means算法的，即假設數據集分布在網絡中的若干個站點上，這些站點的處理過程相互影響。分布式K-means算法要解決的關鍵問題是全局中心的計算，這也是與集中式K-means的最大不同。本文提出了一種分布式K-means中心算法，用于計算全局中心。下面將詳細講述改進后分布式聚類算法的實現過程。

2.1 分布式聚類算法的過程

為了方便描述，先假設初始數據分布是絕對隨機和獨立的。每個站點Si各自任意初始化1組中心向量Mi={mk|k=1，2，…，K}。完成初始化之后，每個站點，并行計算各自的中心點，且在分布式K-means算法的每次迭代過程中局部站點Si都會將各自的局部聚類中心廣播到其他站點。在局部站點進行聚類后，將利用所有已經聚類完畢的局部數據和已經估算出的中心點矢量，記作{m(old)k}，將計算出新的中心點矢量，記作{m(new)k}。在計算新的中心點過程中，為了避免任意一個站點出現空集的情況，已估算出的中心點來作數據項。

中心的計算是分布式聚類算法最重要的特征，也是分布式K-means算法和集中式K-means算法的主要區別，可以用以下數學公式表達。

K-means為:

m(new)k←1nk{∑pj ∈cK(pj)}(2)

本文分布式K-means的中心公式為:

m(new)k←1nk + 1{∑mj∈cK(mj) +m(old)k}(3)

新的中心矢量分布在所有的站點，并以廣播的方式進行操作。每個站點Si通過自己的中心以及從其他站點收到的中心計算平均值，并且用這些新的平均值代替{m(old)k}。很顯然，除了第一步，以后的每一步中所有的站點都有明確的中心。不斷重復以上過程，直到中心矢量穩定。新的中心計算策略使分布式K-means算法和傳統的K-means算法有所不同。以下是分布式K-means算法的描述。

算法2: 分布式K-means

輸入: 整數K值和數據集合

輸出: K個簇

begin

for each site Si do in parallel

initialize a set of center vectors mk for k=1 to K

//初始化一組中心，這些中心點稱為舊中心{m(old)k}

repeat

for each site Si do in parallel

begin

distribute local data in Si into k classes according to minimum distance

from mi for k=1 to K

compute new center vectors{m(new)k} for k=1 to K

considering old centers{m(old)k}as data items

end

for each site Si broadcast{m(new)k}， for k=1 to K to all other sites

for each site Si do in parallel

begin

for k=1 to K do

compute average of {m(new)k} from self and those received other sites and replace {m(old)k} with this average

end

until center vectors are stable

end

2.2 分布式K-means算法復雜度分析

對于任何并行和分布式的聚類算法都有2個方面的復雜度[6]，即時間復雜度Ttime和通信復雜度Tcomm。在計算過程中，主要的計算步驟是計算每一個數據點到相應中心矢量的距離;在通信過程中，需要從一個站點到其他站點傳送數據，中心矢量和其他一些相關的信息[7]。首先分析分布式聚類算法在1次重復步驟中的復雜度。設Tdata為1個數據項的實際通信時間;Tstart為建立連接所需要的時間。由于是并行執行，只需傳送1次數據，因此每步的復雜度為:

Ttime=Tstart+KTdata

相似的，計算距離的復雜度為:

Ttime=KnTdist

式中:Tdist是計算1個單一數據點距離的時間;n=N/P。現在設T為K-means算法所需的循環次數，則整個算法的復雜度為:

Ttime=T{Tstart+KTdata}

Tcomm=TKnTdist。

由于網絡發達，建立連接的時間可以忽略不計。因此，本文算法的復雜度表達式可以寫成以下形式:

Ttime=TKTdata，Tcomm=TKnTdist

為了體現本算法的優越性，在此與Dhillon的分布式聚類算法的復雜度進行了比較。在由Dhillon等[8]提出的分布式算法中，時間復雜度除了Ttime=TKTdata，還要加上傳送計算各個局部站點所有矢量、局部站點元素的個數以及所有局部站點的歐幾里得最小平方誤差和的時間，而通信復雜度除了Tcomm=TKnTdist，還要加上計算各個局部站點所有矢量的時間和。很明顯，在Dhillon的方案中，時間復雜度和通信復雜度在某種程度上都高于本文所敘述的方法，而且在文獻[9]中空簇被視為1個元組進行通信，而在改進后的方法中沒有空的簇。

3 實驗結果與性能分析

通過2組實驗對提出的算法進行性能測試。實驗平臺配置為100 Mb/s的局域網，4臺PC機，配置為Pentium Ⅳ/Intel 1.66 GHz/512 MB，Windows XP (Server版)，80 GB硬盤。將算法轉化為具體的源代碼，在新西蘭懷卡托大學開源平臺WEKA上對算法進行驗證。

實驗包括2部分:第1部分有6組是人工二維數據集，大小分別為5 KB，10 KB，50 KB，100 KB，300 KB，500 KB;第2部分采用來自UCI機器學習數據庫[8]的Iris植物數據集[10]，該數據集有4個屬性，3個類別，共150個樣本。

在第1個實驗中，用6組大小不同的數據集來對比不同聚類算法的執行效率，為了便于理解這幾組數據，本文都采用二維數據集，并且都分為3類。實驗結果如圖1所示，y軸的時間單位是時鐘周期。隨著數據集規模的不斷變大，分布式聚類算法的運行時間明顯小于集中式聚類算法，同時與Dhillon分布式聚類算法相比，運算效率也有所提高。本文提出的分布式聚類算法，其增長速率也比集中式K-means算法得小。

第2個實驗旨在證明本文提出算法的正確性。實驗數據是著名的Iris數據集。原始數據集的分布圖如圖2所示。站點1，2，3分別反映了全局空間中的某一部分，如圖3~5所示。本文提出的分布式聚類算法，從最后聚類的結果(見圖6)來看，全局中心定位還是相當準確的。

圖1 本文算法與集中式K-means算法、Dhillon算法執行效率的比較

圖2 Iris原始數據分布

圖3 站點1數據分布

圖4 站點2數據分布

圖5 站點3數據分布

圖6 分布式K-means算法聚類結

4 結 語

在深入研究集中式K-means聚類算法的基礎上，提出了一種新的分布式K-means聚類算法，分析了新算法的復雜度，并通過實驗證明了新算法在保持集中式K-means聚類算法所有特性的同時，大幅度提高了算法的性能。實驗還表明了本文提出的分布式算法與參考文獻中報道的算法相比，減小了算法的復雜度，提高了算法的效率。

參考文獻

[1]LI Cheng-an. New methods for cluster analysis in distributed environments[D]: Hangzhou:Zhejiang University， 2006.

[2]ANKERST M， BREUNING M M， KRIEGEL H P， et al. Ordering points to identify the clustering structure[C]//Proc. of ACM SIGMOD International Conference on Management of Data. USA: ACM Press， 2008: 213-216.

[3]BRECHEISEN S， KRIEGEL H P， KROGER P， et al. Visually mining through cluster hierarchies[C]. Proc. of SIAM Int′l Conf. on Data Mining Orlando. USA: [s.n.]， 2006.

[4]HAN Jia-wei， KAMBER Micheline. Data mining:concepts and techniques(3)[M].Beijing:China Machine Press， 2008.

[5]KRIEGEL H P， Krger P， PRYAKHIN A， et al. Effective and efficient distributed model-based clustering [C]// Proceedings of 5th IEEE International Conference on Data Mining.USA: [s.n.]， 2005:258-265.

[6]CHEN Jian-mei， ZHU Yu-quan， NI Wei-wei， et al. An efficient algorithm for updating global frequent close item sets[J].Mini-Micro Systems， 2008， 29(7): 1237-1240.

[7]ZHAO Da-wei， XIAO Zhou-fang.Improved K-means clustering algorithm based density and sample size[J].ScienceTechnology information， 2008， 28:171-172.

[8]DHILLON I S， MODHA D S. A data-clustering algorithm on distrbuted memory multiprocessor[J]. Proceedings of KDD-WS on High Performance Data Mining， 2009， 23(9): 123-127.

[9]SANTOS D S. A biologically-indpired distributed clustering algorithm[C] //Proc. of ACM SIGMOD International Conference on Management of Data. USA: ACM Press， 2009:132-137.