摘 要:提出一種適用于大型數(shù)據(jù)集的分布式聚類(lèi)算法。該算法以傳統(tǒng)的K-means算法為基礎(chǔ)進(jìn)行合理的改進(jìn)，使之更適用于分布式環(huán)境，并從算法的復(fù)雜度分析，將該算法與傳統(tǒng)的集中式K-means算法及其他分布式算法進(jìn)行比較。實(shí)驗(yàn)表明，該算法在保持了集中式K-means算法所有必要特性的同時(shí)，提高了數(shù)據(jù)處理速度。

關(guān)鍵詞:K-means聚類(lèi)算法; 分布式環(huán)境; 大數(shù)據(jù)集; 復(fù)雜度

中圖分類(lèi)號(hào):TP393 文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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 引 言

傳統(tǒng)聚類(lèi)方法的一個(gè)前提是數(shù)據(jù)集中在一個(gè)站點(diǎn)，需要一次性載入內(nèi)存。然而，在許多環(huán)境中，局域網(wǎng)、廣域網(wǎng)、Internet網(wǎng)將多個(gè)數(shù)據(jù)源連成一個(gè)大型分布式異構(gòu)數(shù)據(jù)庫(kù)，用戶需要處理大量、多計(jì)算節(jié)點(diǎn)、不同地理分布的數(shù)據(jù)，并需要保護(hù)數(shù)據(jù)的隱私和安全[1]。集中式聚類(lèi)算法不能很好地應(yīng)用到分布式環(huán)境中，即使允許集中執(zhí)行大量的數(shù)據(jù)，要么算法崩潰，要么執(zhí)行效率太低，其長(zhǎng)時(shí)間的執(zhí)行，讓用戶難以接受。數(shù)據(jù)存儲(chǔ)方式的變化對(duì)聚類(lèi)算法的并行性和分布化都提出了要求。分布式聚類(lèi)是解決此問(wèn)題的有效方法[2-3]。

分布式聚類(lèi)是基于分布的數(shù)據(jù)源和計(jì)算資源對(duì)大規(guī)模、分布式的數(shù)據(jù)進(jìn)行聚類(lèi)分析的，是聚類(lèi)分析進(jìn)一步進(jìn)化的結(jié)果，體現(xiàn)了并行計(jì)算、分布式計(jì)算和通信日益增長(zhǎng)的趨勢(shì)。它的思想是:首先在個(gè)體站點(diǎn)數(shù)據(jù)執(zhí)行局部聚類(lèi)分析，然后將部分聚類(lèi)結(jié)果作為產(chǎn)出送給其他站點(diǎn)，并聚集成最后的聚類(lèi)結(jié)果。

本文基于分布式聚類(lèi)的思想，以集中式的K-means算法為基礎(chǔ)，提出一種分布式的K-means算法。實(shí)驗(yàn)結(jié)果表明，對(duì)于大規(guī)模數(shù)據(jù)庫(kù)，該算法比集中式的K-means算法具有更高的效率和更低的時(shí)間復(fù)雜度。

1 典型K-means算法

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

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

平方誤差準(zhǔn)則定義如下:

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

式中:E是數(shù)據(jù)庫(kù)中所有對(duì)象平方誤差的總和;p是空間中的點(diǎn)，表示數(shù)據(jù)對(duì)象;mi是簇Cj的平均值(p和mi都是多維的)。聚類(lèi)的目標(biāo)就是用式(1)使E的值達(dá)到最小。

算法1:集中式K-means

輸入:包含N個(gè)對(duì)象的數(shù)據(jù)庫(kù)和K值(K為整數(shù));

輸出:K個(gè)簇，使平方準(zhǔn)則最小。

方法:

(1) 隨機(jī)選取K個(gè)對(duì)象pj∈S作為初始聚類(lèi)中心;

(2) 當(dāng) E 不穩(wěn)定時(shí)，為每個(gè)K計(jì)算距離dij=|p-mi|2(1≤i≤K且 1≤j≤N);

(3) 根據(jù)點(diǎn)到 mi的最小距離將每個(gè)對(duì)象(重新)賦給最類(lèi)似的簇;

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

(5) 計(jì)算 E，直到 E值穩(wěn)定。

K-means算法的復(fù)雜度由O(TKN)表示，其中K是期望的聚類(lèi)簇的個(gè)數(shù)，T是迭代次數(shù)，N是數(shù)據(jù)對(duì)象的個(gè)數(shù)。

2 分布式K-means聚類(lèi)算法

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

2.1 分布式聚類(lèi)算法的過(guò)程

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

中心的計(jì)算是分布式聚類(lèi)算法最重要的特征，也是分布式K-means算法和集中式K-means算法的主要區(qū)別，可以用以下數(shù)學(xué)公式表達(dá)。

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)

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

算法2: 分布式K-means

輸入: 整數(shù)K值和數(shù)據(jù)集合

輸出: K個(gè)簇

begin

for each site Si do in parallel

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

//初始化一組中心，這些中心點(diǎn)稱(chēng)為舊中心{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算法復(fù)雜度分析

對(duì)于任何并行和分布式的聚類(lèi)算法都有2個(gè)方面的復(fù)雜度[6]，即時(shí)間復(fù)雜度Ttime和通信復(fù)雜度Tcomm。在計(jì)算過(guò)程中，主要的計(jì)算步驟是計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)到相應(yīng)中心矢量的距離;在通信過(guò)程中，需要從一個(gè)站點(diǎn)到其他站點(diǎn)傳送數(shù)據(jù)，中心矢量和其他一些相關(guān)的信息[7]。首先分析分布式聚類(lèi)算法在1次重復(fù)步驟中的復(fù)雜度。設(shè)Tdata為1個(gè)數(shù)據(jù)項(xiàng)的實(shí)際通信時(shí)間;Tstart為建立連接所需要的時(shí)間。由于是并行執(zhí)行，只需傳送1次數(shù)據(jù)，因此每步的復(fù)雜度為:

Ttime=Tstart+KTdata

相似的，計(jì)算距離的復(fù)雜度為:

Ttime=KnTdist

式中:Tdist是計(jì)算1個(gè)單一數(shù)據(jù)點(diǎn)距離的時(shí)間;n=N/P?，F(xiàn)在設(shè)T為K-means算法所需的循環(huán)次數(shù)，則整個(gè)算法的復(fù)雜度為:

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

Tcomm=TKnTdist。

由于網(wǎng)絡(luò)發(fā)達(dá)，建立連接的時(shí)間可以忽略不計(jì)。因此，本文算法的復(fù)雜度表達(dá)式可以寫(xiě)成以下形式:

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

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

3 實(shí)驗(yàn)結(jié)果與性能分析

通過(guò)2組實(shí)驗(yàn)對(duì)提出的算法進(jìn)行性能測(cè)試。實(shí)驗(yàn)平臺(tái)配置為100 Mb/s的局域網(wǎng)，4臺(tái)PC機(jī)，配置為Pentium Ⅳ/Intel 1.66 GHz/512 MB，Windows XP (Server版)，80 GB硬盤(pán)。將算法轉(zhuǎn)化為具體的源代碼，在新西蘭懷卡托大學(xué)開(kāi)源平臺(tái)WEKA上對(duì)算法進(jìn)行驗(yàn)證。

實(shí)驗(yàn)包括2部分:第1部分有6組是人工二維數(shù)據(jù)集，大小分別為5 KB，10 KB，50 KB，100 KB，300 KB，500 KB;第2部分采用來(lái)自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)[8]的Iris植物數(shù)據(jù)集[10]，該數(shù)據(jù)集有4個(gè)屬性，3個(gè)類(lèi)別，共150個(gè)樣本。

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

第2個(gè)實(shí)驗(yàn)旨在證明本文提出算法的正確性。實(shí)驗(yàn)數(shù)據(jù)是著名的Iris數(shù)據(jù)集。原始數(shù)據(jù)集的分布圖如圖2所示。站點(diǎn)1，2，3分別反映了全局空間中的某一部分，如圖3~5所示。本文提出的分布式聚類(lèi)算法，從最后聚類(lèi)的結(jié)果(見(jiàn)圖6)來(lái)看，全局中心定位還是相當(dāng)準(zhǔn)確的。

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

圖2 Iris原始數(shù)據(jù)分布

圖3 站點(diǎn)1數(shù)據(jù)分布

圖4 站點(diǎn)2數(shù)據(jù)分布

圖5 站點(diǎn)3數(shù)據(jù)分布

圖6 分布式K-means算法聚類(lèi)結(jié)

4 結(jié) 語(yǔ)

在深入研究集中式K-means聚類(lèi)算法的基礎(chǔ)上，提出了一種新的分布式K-means聚類(lèi)算法，分析了新算法的復(fù)雜度，并通過(guò)實(shí)驗(yàn)證明了新算法在保持集中式K-means聚類(lèi)算法所有特性的同時(shí)，大幅度提高了算法的性能。實(shí)驗(yàn)還表明了本文提出的分布式算法與參考文獻(xiàn)中報(bào)道的算法相比，減小了算法的復(fù)雜度，提高了算法的效率。

參考文獻(xiàn)

[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.