鮑黎明，黃 剛

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

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

鮑黎明，黃 剛

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

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

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

0 引 言

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

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

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

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

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

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

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

1 基本思想

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

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

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

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

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

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

2 算法的簡單性描述

基本定義：

定義1：簇質心的計算公式為：

(1)

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

圖1 算法思想示意

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

d(Ii,Ij)=

(2)

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

定義3：簇中所有的數據點到簇質心的距離的平均值定義為簇內相似度[9]，計算公式為：

inner=

(3)

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

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

ext=min‖Wi-Wj‖=

(4)

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

基本步驟為：

(1)確定初始聚類數k并隨機選取初始質心(見圖1(a))。

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

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

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

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

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

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

分裂標準：算法在分裂階段如何正確選擇該分裂的簇進行分裂是一個難題，因此算法需要一個簇內相似度閾值來判斷哪些簇該分裂。

(5)

(6)

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

分裂算法過程：

輸入：簇inner；

輸出：分裂的兩個簇。

Begin

(2)k=k+1

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

repeat

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

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

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

End

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

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

合并標準如下：

兩個簇要合并需依次滿足三個標準才可進行：所謂依次是指滿足了標準一，才可以去看是否滿足標準二，進而標準三。

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

標準二：滿足ext最大的兩個簇，滿足標準二說明簇間相似度較大，且相鄰。

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

3 基于多叉樹的數據結構模型

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

Static intk;

Class Node{

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

Int *k=k;

Int inner，ext；

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

Node *L_child=L;

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

}

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

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

4 算法具體分析

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

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

輸入：包含n個對象的數據集及簇的數目k；

輸出：簇的集合。

Begin

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

Repeat

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

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

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

⑦當簇滿足合并標準時合并簇

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

⑩計算目標函數Ew

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

End

5 實 驗

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

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

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

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

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

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

橫向比較實驗結果見表1。

表1 橫向比較結果

分析以上結果，可以得到如下結論：

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

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

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

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

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

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

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

圖3 實驗結果圖

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

最后實驗使用外部數據集Wine data和Iris data對算法A與算法B進行了對比，結果見表2。

表2 對比實驗

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

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

6 結束語

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

[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].大連:大連理工大學,2007.

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

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

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

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

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

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

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

[14] 孫吉貴，劉 杰，趙連宇．聚類算法研究[J].軟件學報，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 網絡出版時間：2017-03-13

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

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

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