基于多叉樹確定K值的動態(tài)K-means聚類算法

鮑黎明，黃 剛

(南京郵電大學(xué) 計算機(jī)學(xué)院，江蘇 南京 210003)

基于多叉樹確定K值的動態(tài)K-means聚類算法

鮑黎明，黃 剛

(南京郵電大學(xué) 計算機(jī)學(xué)院，江蘇 南京 210003)

K-means聚類算法是基于劃分的經(jīng)典聚類算法之一，因其簡潔、高效得到了廣泛的應(yīng)用。K-means算法具有容易實現(xiàn)、時間和空間復(fù)雜度較小的優(yōu)點。但該算法的初始聚類數(shù)K通常不能通過有效的手段事先確定，其初始聚類中心往往是隨機(jī)選取的，易收斂于局部最優(yōu)解，造成聚類結(jié)果的不準(zhǔn)確。基于多叉樹確定K值的動態(tài)K-means聚類算法是對傳統(tǒng)算法的改進(jìn)，力求在迭代過程中動態(tài)分裂合并簇來確定最合理的聚類數(shù)，并且能在一定程度上解決聚類結(jié)果收斂于局部最優(yōu)解的問題。文中還探索了相應(yīng)的數(shù)據(jù)模型以支持所改進(jìn)算法的研究，并從橫向與縱向兩方面與二分K-means算法作了對比實驗。實驗結(jié)果表明，改進(jìn)后的K-means算法不依賴于全局?jǐn)?shù)據(jù)集，更適用于分布式平臺運算；算法相對效率隨著數(shù)據(jù)集規(guī)模的增大，特別是在洪量數(shù)據(jù)集下具有明顯的優(yōu)勢。

K-means；聚類；分裂；合并；多叉樹

0 引 言

(1)設(shè)定簇內(nèi)相似度λ和簇間相似度γ兩個閾值。

(2)在所選數(shù)據(jù)集上運行二分K均值聚類算法，得到兩個類C1和C2，計算C1和C2的簇內(nèi)相似度λ'，若λ'>λ，則繼續(xù)運行二分K均值聚類算法，不斷迭代以上過程，直到得到所有的簇內(nèi)相似度都小于λ。

(3)計算所有簇的簇間相似度，將簇間相似度小于γ的簇合并。

(4)得到的聚類個數(shù)即為k值。

該算法通過分裂和合并兩個過程，得到較為準(zhǔn)確的聚類結(jié)果，思想較為簡單。二分K均值聚類算法是改進(jìn)K-means算法思想的來源。

基于多叉樹確定k值的動態(tài)聚類算法是一種不依賴于初始聚類數(shù)、在聚類過程中通過分裂與合并動態(tài)地確定k值的算法?；诙嗖鏄浯_定k值的動態(tài)聚類算法不同于二分K均值聚類算法的最明顯表現(xiàn)是，在迭代開始時可以在2與N之間隨機(jī)指定初始聚類數(shù)，每次迭代可以分裂合并多個類簇。

這樣聚類中心數(shù)即k值在每次迭代后是動態(tài)變化的，隨著聚類中心趨于穩(wěn)定，最終確定的K值即為最終的聚類數(shù)目。實驗結(jié)果表明，基于多叉樹確定k值的動態(tài)聚類算法確定的聚類數(shù)目與實際聚類數(shù)目相同，且算法的聚類準(zhǔn)確性得到了相應(yīng)提高。

1 基本思想

傳統(tǒng)K-means算法[6]的基本步驟為：

(1)選擇k個點作為初始質(zhì)心。

(2)重復(fù)以下過程：將每個點指派到最近的質(zhì)心，形成k個簇；重新計算每個簇的質(zhì)心。

(3)直到質(zhì)心不發(fā)生變化，算法結(jié)束。

基于多叉樹確定k值的動態(tài)K-means聚類算法是對傳統(tǒng)K-means算法的改進(jìn)，但也離不開核心的迭代過程。該算法對于初始聚類數(shù)和初始質(zhì)心的選取要求不高，但是合理地選取初始聚類數(shù)和初始質(zhì)心可以降低算法的運行時間，提高效率。初始質(zhì)心的選取可以采取基于密度的方法[7]來進(jìn)一步提高聚類效率，然而，為凸顯基于多叉樹確定k值的動態(tài)聚類算法的有效性，利用隨機(jī)均勻選擇初始質(zhì)心的方法。改進(jìn)算法的迭代過程是區(qū)別于傳統(tǒng)聚類算法和二分K均值聚類算法的核心所在。

圖1為算法思想的直觀闡述。

2 算法的簡單性描述

基本定義：

定義1：簇質(zhì)心的計算公式為：

(1)

其中，ni為簇Ci內(nèi)數(shù)據(jù)點的個數(shù)；Ii=(ii1,ii2,…,iip)為簇Ci內(nèi)維度為p的數(shù)據(jù)對象。

圖1 算法思想示意

定義2：兩個數(shù)據(jù)對象間的歐氏距離[8]為：

d(Ii,Ij)=

(2)

其中，Ii=(ii1,ii2,…,iip)和Ij=(ij1,ij2,…,ijp)是兩個p維的數(shù)據(jù)對象。

定義3：簇中所有的數(shù)據(jù)點到簇質(zhì)心的距離的平均值定義為簇內(nèi)相似度[9]，計算公式為：

inner=

(3)

其中，ni為簇Ci內(nèi)數(shù)據(jù)點的個數(shù)；I=(i1,i2,…,ip)為簇Ci內(nèi)的數(shù)據(jù)元素；Wi=(wi1,wi2,…,wip)為簇Ci的質(zhì)心。Inner值越小，說明簇間相似性越大；反之，則越小。

定義4：簇質(zhì)心到其他簇質(zhì)心的最小距離定義為簇間相似度[9]，計算公式為：

ext=min‖Wi-Wj‖=

(4)

其中，Wi=(wi1,wi2,…,wip)與Wj=(wj1,wj2,…,wjp)分別為簇Ci與Cj的質(zhì)心。ext的值越大說明簇間相似度越?。环粗?，則越大。

基本步驟為：

(1)確定初始聚類數(shù)k并隨機(jī)選取初始質(zhì)心(見圖1(a))。

(2)將每個點指派到最近的質(zhì)心，指派的標(biāo)準(zhǔn)為歐氏距離，重新計算每個簇的質(zhì)心(見圖1(b))。

(3)分裂簇(見圖1(c))。

(4)重新計算每個簇的質(zhì)心(見圖1(d))。

(5)合并簇(見圖1(e))。

(6)再次重新計算每個簇的質(zhì)心(見圖1(f))。

從算法每一次的迭代步驟中會發(fā)現(xiàn)除了第六步重新計算質(zhì)心外，中間還有兩次需要計算質(zhì)心，這是因為簇的分裂和合并所依賴的簇內(nèi)相似度和簇間相似度都需要明確每個簇的質(zhì)心，關(guān)于分裂與合并簇的標(biāo)準(zhǔn)，下面將會詳細(xì)討論。還會發(fā)現(xiàn)迭代過程是先分裂簇后合并簇，這是因為，分裂后的簇也許會符合合并簇指標(biāo)，先分裂后合并會適當(dāng)減少迭代次數(shù)，提高算法效率。還有一個問題是如何避免已分裂的簇在合并階段又合并在一起的問題，這個問題會讓迭代無限執(zhí)行下去而得不到最終的聚類結(jié)果。因此，分裂后所得到的兩個簇要做標(biāo)識，來避免在合并階段，將分裂的兩個簇合并。

分裂標(biāo)準(zhǔn)：算法在分裂階段如何正確選擇該分裂的簇進(jìn)行分裂是一個難題，因此算法需要一個簇內(nèi)相似度閾值來判斷哪些簇該分裂。

(5)

(6)

圖2 正態(tài)分布圖

分裂算法過程：

輸入：簇inner；

輸出：分裂的兩個簇。

Begin

(2)k=k+1

(3)選擇2個點作為初始質(zhì)心。

repeat

(4)將每個點指派到最近的質(zhì)心，形成K個簇。

(5)重新計算每個簇的質(zhì)心

until質(zhì)心不發(fā)生變化

End

分裂算法具體過程其實就是將需分裂的簇視為一個原始樣本點，在此簇內(nèi)運用原始K-means算法進(jìn)行聚類，唯一不同的是聚類數(shù)的取值為2。當(dāng)然分裂后的兩個簇并不能保證它們是純簇(只包含一類樣本點的簇)，但是基于多叉樹確定k值的動態(tài)聚類算法會在迭代過程中不斷使簇的元素數(shù)據(jù)趨于單一。

因為分裂簇后會造成聚類數(shù)增加1，因此需要在原來k的基礎(chǔ)上加1。

合并標(biāo)準(zhǔn)如下：

兩個簇要合并需依次滿足三個標(biāo)準(zhǔn)才可進(jìn)行：所謂依次是指滿足了標(biāo)準(zhǔn)一，才可以去看是否滿足標(biāo)準(zhǔn)二，進(jìn)而標(biāo)準(zhǔn)三。

標(biāo)準(zhǔn)一：要合并的兩個簇不可以是大簇分裂后形成的兩個簇，下文將討論如何識別兩個簇是否為分裂后的小簇。

標(biāo)準(zhǔn)二：滿足ext最大的兩個簇，滿足標(biāo)準(zhǔn)二說明簇間相似度較大，且相鄰。

因為合并簇后會造成聚類數(shù)減1，因此需要在原來k的基礎(chǔ)上減1。

3 基于多叉樹的數(shù)據(jù)結(jié)構(gòu)模型

因為基于多叉樹確定k值的動態(tài)聚類算法涉及到簇的分裂合并，特殊的簇比如分裂后的簇需要標(biāo)識，來避免在后面合并的部分又讓其合并。此外分裂合并會造成聚類數(shù)的變化，也就是說k值是不斷浮動變化的，因此還需保證k值的實時有效性。綜合多方面考慮，數(shù)據(jù)節(jié)點的結(jié)構(gòu)如下：

Static intk;

Class Node{

Int flag=i;i∈(1,2,…,k)

Int *k=k;

Int inner，ext；

Int P_flag=p;p為父節(jié)點的標(biāo)識，根節(jié)點p為0

Node *L_child=L;

Node *R_child=R; 當(dāng)節(jié)點本身為葉節(jié)點時，即未分裂時L和R為空

}

靜態(tài)全局變量k為聚類數(shù)，這樣可以保證k的唯一性與實時性，因為在分裂時k值要加一，合并要減一，并且下一步迭代依賴于k的真實值。Flag為此質(zhì)心節(jié)點的唯一標(biāo)識。P_flag為父節(jié)點的標(biāo)識，簇分裂后形成的兩個小簇的P_flag的值相同，用來避免合并步驟又重新合成。Inner與ext表示本簇的簇內(nèi)與簇間相似度。

L_child與R_child為指向本簇分裂后所形成的兩個小簇的指針，這里根節(jié)點有所不同，因為初始聚類數(shù)k值并不是2，所以根節(jié)點應(yīng)有初始k個子節(jié)點。

4 算法具體分析

變量定義：k為該算法在數(shù)據(jù)集上輸出的聚類數(shù)量；n為數(shù)據(jù)集對象元素個數(shù)。在初始化時，從數(shù)據(jù)集{I1,I2,…,In}隨機(jī)找出k個{W1,W2,…,Wk}，Wi=Ij，i∈{1,2,…,k}，j∈{1,2,…,n}作為簇的初始均值或中心，對剩余的每個對象，根據(jù)其與各個簇均值(見式(1))的距離(見式(2))，將它指派到最相似的簇，計算每個簇的新均值。執(zhí)行分裂、確定質(zhì)心、合并、確定質(zhì)心、再指派這個過程，不斷反復(fù)，直到準(zhǔn)則函數(shù)Ew收斂，或者分裂與合并停止。

基于多叉樹確定k值的動態(tài)K-means聚類算法的描述如下：

輸入：包含n個對象的數(shù)據(jù)集及簇的數(shù)目k；

輸出：簇的集合。

Begin

初始化k個簇中心{W1,W2,…,Wk}，其中Wi=Ij，i∈{1,2,…,k}，使每一個聚類Cj與簇中心Wj相對應(yīng)

Repeat

For 每一個輸入向量Ij，j∈{1,2,…,n} do ①

②For 每一個聚類Ci,i∈{1,2,…,L}，do ③

⑤For 每一個分裂后的類Cm，其中m指上一步被分裂的簇產(chǎn)生的小簇 do⑥

⑦當(dāng)簇滿足合并標(biāo)準(zhǔn)時合并簇

⑧For 每一個合并后的類Cb，其中b指上一步被合并的簇產(chǎn)生的合簇 do ⑨

⑩計算目標(biāo)函數(shù)Ew

UntilEw不再明顯改變或者聚類的成員不再變化

End

5 實 驗

驗證在不同的數(shù)據(jù)集及不同的初始聚類中心選取數(shù)目和選取方式因素下，實驗算法都能高效地得到準(zhǔn)確的聚類結(jié)果。

影響實驗結(jié)果的因素有數(shù)據(jù)集大小、初始聚類中心選取數(shù)目、初始聚類中心選取方式。為了驗證算法的有效性，實驗選取了數(shù)個規(guī)模不同的先驗數(shù)據(jù)集，在這些數(shù)據(jù)集上分別進(jìn)行了不同初始聚類中心選取數(shù)目和方式的基于多叉樹確定k值的動態(tài)K-means聚類算法(算法A)的實施。為了驗證算法的高效性，與基于二分均值聚類的k值決定方法(算法B)進(jìn)行了對比，通過比較聚類結(jié)果以及聚類時間來驗證實驗的高效性。

實驗需要橫向比較與縱向比較兩大步驟。橫向比較是指在同一數(shù)據(jù)集初始聚類中心選取數(shù)目與選取方式的差異所導(dǎo)致的算法的優(yōu)效比；縱向比較是指在不同規(guī)模數(shù)據(jù)集上的算法優(yōu)效比。

實驗算法的核心是分裂合并兩個步驟，因此這兩個步驟的迭代次數(shù)是算法效率的最直接體現(xiàn)，所以實驗選取分裂合并次數(shù)和聚類時間作為驗證算法優(yōu)劣的參數(shù)。

為了使初始聚類中心選取數(shù)目(K0)的選取具有代表性，K0的選取有較少、適量、較多三個層次。因為所選取數(shù)據(jù)集為先驗數(shù)據(jù)集，K0的適量層次即為準(zhǔn)確的聚類數(shù)K；較少層次首先需要包括1，其余需要從1-K之間均勻選取三個數(shù)值；較多層次需包括最大聚類簇元素數(shù)N，以及K-N之間均勻選取三個數(shù)值。

初始聚類中心選取方式包括局部分布、均勻分布兩種。

橫向比較實驗結(jié)果見表1。

表1 橫向比較結(jié)果

分析以上結(jié)果，可以得到如下結(jié)論：

(1)當(dāng)K0選取過少時，聚類迭代時分裂次數(shù)明顯增加，聚類所需時間明顯增加。

(2)當(dāng)K0選取過多時，聚類迭代時合并次數(shù)有所增加，聚類時間也會相應(yīng)增加，但聚類花費時間明顯小于當(dāng)初始K值過少時的聚類所花費時間。

(3)當(dāng)K0選取合適，但初始聚類中心局部分布時，迭代過程中合并次數(shù)明顯增加，聚類時間明顯增加。

(4)當(dāng)K0選取合適，且均勻分布時，分裂合并次數(shù)在正常范圍內(nèi)，聚類時間最短。

以上四種情況，實驗聚類算法運行正常，聚類結(jié)果正確。

縱向比較實驗結(jié)果：實驗需控制初始聚類中心選取數(shù)目及選取方式兩個變量。實驗初始聚類中心選取數(shù)目K0等于最終聚類數(shù)K，選取方式為均勻分布。實驗結(jié)果如圖3所示。

圖中，橫坐標(biāo)為數(shù)據(jù)集規(guī)模(以最終聚類數(shù)為參數(shù))，縱坐標(biāo)為隨著數(shù)據(jù)集規(guī)模的增長時分裂次數(shù)、合并次數(shù)、聚類時間的量化。

圖3 實驗結(jié)果圖

由圖3可知，隨著聚類規(guī)模的遞增，分裂次數(shù)與合并次數(shù)增長趨勢平緩，呈現(xiàn)非指數(shù)型增長，聚類時間呈線性增長。證明算法在不同規(guī)模數(shù)據(jù)集的時間復(fù)雜度在可接受范圍內(nèi)。

最后實驗使用外部數(shù)據(jù)集Wine data和Iris data對算法A與算法B進(jìn)行了對比，結(jié)果見表2。

表2 對比實驗

實驗結(jié)果表明，基于多叉樹確定k值的動態(tài)K-means聚類算法在Wine data和Iris data數(shù)據(jù)集所用時間分別是基于二分均值聚類的k值決定算法的82.6%和83.1%，說明改進(jìn)算法相較于基于二分均值聚類的k值決定方法的效率有所提高。

以上實驗說明，基于多叉樹確定k值的動態(tài)K-means聚類算法對于各種不同的初始k值選取、不同的聚類中心選取方式，都能在可控時間范圍內(nèi)，得到正確的聚類結(jié)果，并且具有較高的效率。

6 結(jié)束語

K-means算法是廣泛應(yīng)用的聚類算法之一，通過研究分析傳統(tǒng)K-means算法的局限性，用一種新思路對K-means算法進(jìn)行適當(dāng)改進(jìn)，使改進(jìn)算法不再嚴(yán)重依賴初始聚類數(shù)的選取。實驗結(jié)果表明，改進(jìn)算法在聚類準(zhǔn)確性和效率上都有適當(dāng)提升。當(dāng)然，算法還有進(jìn)一步改進(jìn)的可能，比如可在分布式文件系統(tǒng)中實現(xiàn)并行化，如Hadoop平臺可使算法效率進(jìn)一步提高，這是下一步研究的方向。

[1] Han J W，Wen S P.Data mining：concepts and techniques[M].San Francisco：Morgan Kaufmann Publishers，2000.

[2] 楊善林，李永森，胡笑旋，等.K-means算法中的k值優(yōu)化問題研究[J].系統(tǒng)工程理論與實踐，2006，26(2)：97-101.

[3] Wang Aijie，Chai Xuguang.Easy and efficient algorithm todetermine number of clusters[J].Computer Engineering and Applications，2009，45(15)：166-168.

[4] Lai J Z C,Huang T J.Fast global k-means clustering using cluster membership and inequality[J].Pattern Recognition,2010,43(5):1954-1963.

[5] Zhang Zhongping，Steinbach M，Karypis G，et al.A comparison of document clustering techniques[R].USA：University of Minnesota，2000.

[6] 馮 超.K-means聚類算法的研究[D].大連:大連理工大學(xué),2007.

[7] 謝娟英，郭文娟，謝維信，等.基于樣本空間分布密度的初始聚類中心優(yōu)化k-均值算法[J].計算機(jī)應(yīng)用研究，2012，29(3)：888-892.

[8] 宋宇辰，張玉英，孟海東.一種基于加權(quán)歐氏距離聚類方法的研究[J].計算機(jī)工程與應(yīng)用,2007,43(4):179-180.

[9] 元昌安．?dāng)?shù)據(jù)挖掘原理與SPSS Clementine應(yīng)用寶典[M]．北京：電子工業(yè)出版社，2009.

[10] 陸聲鏈,林士敏.基于距離的孤立點檢測研究[J].計算機(jī)工程與應(yīng)用,2004，40(33):73-75.

[11] 蘇錦旗,薛惠鋒,詹海亮.基于劃分的K-均值初始聚類中心優(yōu)化算法[J].微電子學(xué)與計算機(jī),2009,26(1):8-11.

[12] 步媛媛,關(guān)忠仁.基于K-means聚類算法的研究[J].西南民族大學(xué)學(xué)報:自然科學(xué)版,2009,35(1):198-200.

[13] 馬 帥，王騰蛟，唐世渭，等.一種基于參考點和密度的快速聚類算法[J].軟件學(xué)報,2003,14(6):1089-1095.

[14] 孫吉貴，劉 杰，趙連宇．聚類算法研究[J].軟件學(xué)報，2008，19(1):48-61．

A Dynamic Clustering Algorithm ofK-means Based on Multi-branches Tree forK-values

BAO Li-ming，HUANG Gang

(School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

K-means algorithm is the one of most classical clustering algorithms with repartition and has been widely used because it’s really concise and efficient.What’s more,it has advantages such as being easy to be implemented and low cost of complexity in running time and storing space.However,it’s normally initial number calledK-value which cannot be precisely predicted by effective method.The initial clustering center used to be chosen randomly,so that the result usually converges to local optimal solution，which makes the latest clustering results inaccurate.The dynamic clustering algorithm ofK-means based on multi-branches tree to determine theK-value is an improved one.The improved algorithm has been designed to determine the most reasonableK-value by dynamically dividing and merging cluster during the iterative process and partly solved the problem that clustering result converges to local optimal solution.Furthermore,exploration for corresponding data structure model has also been conducted to the investigation of the algorithm mentioned.Horizontal and vertical comparison with the binaryK-means algorithm has been achieved.The comparison and analysis results show that the improvedK-means algorithm is independent of improved global data sets,which makes it more suitable for distributed computing platform and that relative efficiency has been increased with increase of the size of the data set,especially in magnanimity data set.Therefore the improvedK-means algorithm has promoted the clustering performance and can lead to a more stable clustering result.

K-means;clustering;dividing;merging;multi-branches tree

2016-05-13

2016-09-14 網(wǎng)絡(luò)出版時間：2017-03-13

國家自然科學(xué)基金資助項目(61171053)；南京郵電大學(xué)基金(SG1107)

鮑黎明(1990-)，男，研究方向為云計算與大數(shù)據(jù)應(yīng)用；黃 剛，教授，研究方向為計算機(jī)軟件理論及應(yīng)用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170313.1545.008.html

TP301.6

A

1673-629X(2017)06-0041-05

10.3969/j.issn.1673-629X.2017.06.009