李紅巖　胡林林　王江波　周紅芳

摘要：確定數據集的最佳聚類數是聚類研究中的一個重要難題。為了更有效地確定數據集的最佳聚類數，該文提出了通過改進K-means算法并結合一個不依賴于具體算法的有效性指標[Q（c）]對數據集的最佳聚類數進行確定的方法。理論分析和實驗結果證明了該方法具有良好的性能和有效性。

關鍵詞：K-means；最佳聚類數；聚類有效性指標；聚類

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）01-0110-05

傳統(tǒng)的獲取最佳聚類數的算法一般是采用的是基于一種迭代的trial-and-error過程[1]，來獲取數據集的最佳聚類數目。由于k-means算法適用于大型數據集的處理，且其效率比較高，特別是當數據集中的數據對象分布呈現類內團聚狀時，所得到的聚類結果往往是比較好的。在實際中，由于用戶缺乏豐富聚類分析的經驗，所以能夠準確地確定數據集的聚類數k的值是一個非常困難的問題[2]，這樣就大大限制的該算法應用，而且確定的k值也往往不能保證是合適的，就需要結合一些有效性指標來確定其最佳聚類數，目前已經提出了一些檢驗聚類有效性的指標，主要代表有[Vxie]指標[3]、[Vwsj]指標[1]等。由于這些指標都是基于其他算法提出的，在k-means算法運用往往得不到比較理想的結果。鑒于此種情況，該文在傳統(tǒng)的k-means算法基礎上，給定一個聚類數目k的范圍，然后再引入一個不依賴于具體算法的有效性指標，把兩者結合在一起來進行最佳聚類數的判定。實驗結果和理論分析都表明，該文提出的算法具有良好的性能與可行性。

1 K-means算法

1.1 K-means算法介紹

傳統(tǒng)的K-means算法需要用戶必須事先給定聚類個數k，并且它能自動地選取k個初始聚類中心，并按最小距離原則將數據對象指派到離其最近的類，然后不停地獲取新的聚類質心并不斷調整各個數據對象所屬的類別，最終達到的結果是各個數據對象到其所屬聚類中心的距離平方之和是最小的。K-means算法主要步驟[4]如下：

輸入：數據集和該數據集的聚類個數k；

輸出：使得某個準則函數最小時的k個類情況。

1）選擇k個數據對象作為初始質心；

2）Repeat

3）計算數據對象與各個類的質心的距離，將對象劃分到距離其最近的類，形成k個類；

4）重新計算每個類的質心點；

5）until 質心點不再發(fā)生變化。

1.2 K-means算法優(yōu)缺點

K-means算法對大型數據集的處理是具有較高的效率[5]和伸縮性，該算法的時間復雜度為[O（nkt）]，其中n為數據集數據成員的個數，k是聚類個數，t是迭代次數。算法主要缺點是必須要求先給定數據集的聚類個數k，不準確的k就會導致聚類的效果[5]。而且對于結構比較復雜的數據集，聚類結果容易受到聚類質心的影響，最終導致聚類效果不理想。

2 聚類有效性指標

為了能夠更好的反映聚類效果，一般是采用類內緊湊度和類間分離度進行衡量，該文在此引用一個不依賴于某些具體算法的有效性指標[Q（C）]來評估聚類的效果。該有效性指標主要是通過衡量數據集中的類內數據對象緊湊度和類間分離度 [6]。下面就大概介紹一下所采用的有效性指標。

2.1 聚類有效性指標

假設給定數據集DB，其中的一個聚類劃分為[Ck={C1，C2，...，Ck}]，在該指標中用[Scat（Ck）]衡量[Ck]的類內緊湊度，[Sep（Ck）]衡量對應[Ck]的類間分離度。[Scat（Ck）]的原理是一個類中的任意兩個數據對象之間的距離的平方和，其具體定義如下：

[Scat（Ck）=i=1kX，Y∈CiX-Y2] （1）

其中，X，Y是類[Ci]中的任意兩個數據對象，k是此時數據集DB被劃分的聚類個數。而[Sep（Ck）]則是將數據類看作是一個比較大的“數據對象”， “數據對象”之間的“距離”是通過類與類之間的點對的平均距離來獲取。這樣，它們在度量上就保持了一致性[6]。

[Sep（Ck）=i=1kj=1，j≠ik1Ci.CjX∈Ci，Y∈CjX-Y2] （2）

其中，X，Y分別屬于類[Ci]，[Cj]中的數據對象，k為此時數據集DB被劃分的聚類個數。代入歐式距離公式再做簡單的變換，[Sep（Ck）]和[Scat（Ck）]可分別表示為：

[Scat（Ck）=2i=1kCiSSi-LSi] （3）

[Sep（Ck）=2k-1i=1kSSiCi-i=1kLSiCi2+i=1kLSi2Ci2] （4）

其中，[SSi=j=1Cix2j]，[LSi=j=1Cixj]，k表示數據集DB被劃分的聚類個數，[xj]表示類[Ci]中的數據對象，[Ci]表示類[Ci]中數據對象的個數。我們可以得到：[Scat（C）]的值越小，說明類內數據對象越緊湊；[Sep（C）]越大，說明類與類間隔越大。一般采用式5來平衡[Sep（C）]和[Scat（C）]之間的差異：

[Q（C）=Scat（C）+β.Sep（C）] （5）

其中，[β]為組合參數，用來平衡[Sep（C）]和[Scat（C）]在取值范圍上存在的差異。該文假設把數據集DB的聚類劃分個數C看作是一個變量，其聚類變量C的范圍為[{C1，C2，....，Cn}]，根據理論分析，我們可以假定[β]為1[7]。

由參考文獻[6]可知，在給定的數據集DB中，[Sep（C）]和[Scat（C）]具有相同的值域范圍，在初始狀態(tài)中，即是當其聚類個數為n時，由公式（1）可知，[Scat（Cn）]為0，而此時設：

[Sep（Cn）=2（n.x∈DBx2-（x∈DBx）2）=M] （6）

因為[Scat（C）]是單調遞增函數，而[Sep（C）]為單調遞減函數[6]。當聚類數k為1時，可以得到[Sep（C1）]=0，而此時[Scat（C1）]=M。所以算法采用的有效性指標函數[Q（C）]可表示為：

[Q（C）=1M（Scat（C）+Sep（C））] （7）

2.2最佳聚類數的確定

有效性指標函數[Q（C）]是反映整個聚類過程中的聚類效果，當類內緊湊度和類間分離度達到一個平衡點時，此時對應的是最佳聚類劃分[1]，有效性指標函數[Q（C）]在數值上反應為取得最小值時。由此可得，有效性指標值越小，則數據集的聚類效果就越好，該文認為聚類有效性指標函數[Q（C）]在取得最小值時所對應的聚類劃分則是最佳的，論文中利用公式（8）來獲得數據集中的最佳的聚類劃分。

[C*=argminCk∈{C1，C2，...，Cn}Q（Ck）] （8）

數據集中往往存在噪聲點或者孤立點等異常點，由于它們對聚類結果影響，由上述過程所得出的聚類數并不一定是最佳的，所以本文采用一直基于MDL剪枝算法[8]來去除異常點，利用公式（9）獲得最佳聚類數。該公式可以被認為是對異常點進行處理的過程。

[kopt=β（C*）] （9）

在以上公式中，[C*]是表示聚類有效性指標函數[Q（C）]的值達到最小時所對應的聚類劃分個數，[kopt]表示獲得的最佳聚類劃分個數。

2.3 異常點的消除過程

由于數據集中往往存在噪聲點或孤立點等異常點，由于它們對聚類結果的影響，所以單獨利用有效性指標函數獲取的聚類個數為最佳聚類數[k*]的結論并不成立。因為異常類也是聚類劃分過程的組成部分，但這些類所包含的數據對象往往比較少[8]。根據參考文獻[6][7]和[8]可知，MDL算法的基本原理是對所使用的數據進行統(tǒng)一編碼，進而選擇具有最短編碼長度的編碼方案。在本文所提出的算法中，所使用的數據是某一時刻聚類劃分中的各個類所包含的數據對象的個數。該文采用基于MDL剪枝的算法來對數據集中的異常點進行去除。大概過程如下：

令[C*={C*1，C*2，......C*k}]，其中[C*i]為類[C*i]包含的數據點的個數。首先把[C*i]按從大到小次序進行排序，此時產生新的序列[C1，C2，.....Ck]，然后將這個新序列以 [Cm] （1

[CL（m）=log2（μSL（m））+1≤j

其中，[μSL（m）=1≤j

通常認為聚類個數比較少的類為異常數據點所在的類，在本算法中，也即是[SR（m）]中所包含的類，在此認為最佳聚類數[kopt]為m。

3 最佳聚類數確定算法

本文中提出了一個算法COKS，為了在該算法中更有效性地利用k-means算法，特對k-means算法的缺點進行必要的改進，使該算法更能準確地對數據集進行聚類分析。首先要確定聚類數k的搜索范圍。

3.1 聚類數K搜索范圍的確定

對于k-means算法中的聚類數k的范圍的確定，由于本算法所采用的聚類有效性指標需要得到在聚類數為1的情況下的[Sep（C1）]和[Scat（C1）]的值，所以，在本文中，設定其的最小聚類數[kmin]為1。至于最大聚類數[kmax]，根據大多數研究者所得出的經驗[9]，最佳聚類數[kopt]應是[kopt≤n]，其中n為數據集中的數據對象的個數。所以在此取最大聚類數[kmax=n]。所以，根據以上分析可以得出本算法中的聚類數k的搜索范圍為[[kmin]，[kmax]]。

3.2 最佳聚類數確定算法（COKS）

算法COKS主要原理是利用改進的k-means算法并結合第2節(jié)所介紹的不依賴于具體算法的聚類有效性指標，進而提出一種獲取最佳聚類劃分個數的聚類算法（COKS）。算法主要步驟歸納如下：

輸入：數據集和數據集中數據對象的個數n；

輸出：有效性指標值及所對應的聚類數和最佳聚類數。

1）選擇聚類數的搜索范圍[[kmin]，[kmax]]；

2）For k = [kmin] to [kmax]

a）調用K-means算法進行劃分；

b）根據式（7）計算此時聚類劃分的有效性指標函數[Q（C）]的值；

c）把獲取的有效性指標值和所對應的聚類劃分個數保存一個數組A中；

3）根據式（8）獲取數組A中最小的聚類指標值以及所對應的聚類劃分；

4）對所步驟3得到的聚類指標值以及對應的聚類劃分，再按式（9）對其中異常點所組成的類進行剔除，最后得到的值則認為是最佳聚類個數[kopt]。

4 實驗驗證與分析

為了驗證COKS算法的有效性以及性能，該文選擇4個數據集并分成兩組進行實驗。在較多的聚類有效性指標中，該文選擇了兩種比較常用的其具有代表的有效性指標[Vxie][3]和[Vwsj][1]作為對比對象。由于這兩種指標是基于FCM聚類算法提出的，所以，該文選擇FCM作為聚類對比算法。其中，[Vxie]是第一個提出并運用“緊湊度”和“分離度”的指標，而[Vwsj]則是改進了線性組合，可以更為有效地處理包含有重疊的類和異常類的數據集。

4.1實驗中的數據集

1） 人工數據集。在本實驗中，采用的兩個人工生成的數據集，其代號分別為數據集DB1和DB2。其中數據集DB1是由中心數據點分別為（10，10），（40，40）的二維高斯分布數據對象組成，其中數據集中以（10，10）為類的樣本個數有500個，而以（40，40）為類的也有500個數據，該數據集的主要特征為兩個聚類的類中心點不同，則兩個類之間屬性差別比較大。而數據集DB2則是一個二維的有三個類別的人工合成數據集，具有松散的、輕微重疊和帶有少量異常點的聚類結構。

2） 標準數據集。本實驗還采用了2個UCI的真實標準數據集，其數據集代號分別為DB3和DB4，名稱分別是IRIS和Wiconsin breast cancer。所采用的4個數據集的屬性以及其參數如表1所示。

表1 測試數據集的屬性表

[數據集代號＼&數據集名稱＼&數據集大?。?數據集維數＼&真實聚類數＼&DB1＼&人工合成＼&1000＼&2＼&2＼&DB2＼&人工合成＼&1600＼&2＼&3＼&DB3＼&IRIS＼&150＼&4＼&3＼&DB4＼&Wiconsin breast cancer＼&699＼&9＼&2＼&]

4.2實驗結果

實驗主要分為兩部分，第一部門主要是驗證算法COKS的性能。把實驗中所采用的4個數據集分別在COKS算法運行，所得到的有效性指標值與聚類劃分個數如圖1所示。

（a）DB1， [kopt]=2 （b） DB2， [kopt]=3

（c） DB3， [kopt]=3 （d） DB4， [kopt]=2

圖1 數據集聚類結果圖

由圖1可知。由于數據集中的數據對象的分布以及幾何結構各不同，算法COKS對每個數據集的處理效果也有所不同。由于數據集DB1在合成過程中，保持了類與類之間具有較大的差異性，并且數據對象分布比較集中、其幾何結構也比較標準，所獲取的有效性指標值能夠更好地反應出最佳聚類劃分情況，由圖1（a）所示，在聚類個數為2時所對應的有效性指標值與其他值差別比較明顯，而且其有效性指標值最小。數據集DB2，由于其中存在異常點和重疊點，獲取的指標值差別不大，當聚類數為15以上時，指標值逐漸趨于平衡，如圖1（b）所示。由于數據集DB3中的數據對象個數比較少，而且包含兩個重疊的簇[11]，如圖1（c）所示，COKS算法能夠比較正確且有效地區(qū)分重疊的類。圖1（d）顯示，對于數據集DB4，當聚類個數由3降到2時，其有效性指標值存在很小的差異，但COKS算法也能獲取最佳的數據值?？傊?，算法COKS能夠正確處理待測數據集并能獲得其數據集的最佳聚類數。

第二部分主要是驗證算法COKS的有效性。為了說明該算法在對數據集的最佳聚類數的確定具有更好的有效性，論文采用參考文獻[1][3]中所述的基于FCM算法的有效性指標[Vxie]和[Vwsj]與指標[Q（C）]對比，其設置FCM模糊因子m為2。不同算法所獲得的最佳聚類數情況如表2所示。

在本次實驗中，根據3.1節(jié)所述，我們把FCM算法中的聚類個數k的范圍設置為[1，12]，這樣可以快速提高FCM的效率。為了使實驗結果的準確性更高，把4個數據集在各個算法上分別運行多次，將聚類個數出現次數最多的聚類結果作為最終聚類劃分數，這樣可以減少由于其他因素對聚類結果造成的誤差。由表2可知，算法COKS能夠正確處理和獲得數據集的最佳聚類數，同其它算法相比，其準確率比較高。

在實驗中，因為每個數據集要在每個算法運行多次。我們取這些時間的平均值則所用的時間如表3所示。

表3 不同算法運行時間

[數據集＼&運行時間（秒）＼&FCM（[Vxie]）＼&FCM（[Vwsj]）＼&COKS＼&DB1＼&0.9＼&0.8＼&0.9＼&DB2＼&0.5＼&0.6＼&0.4＼&DB3＼&0.6＼&0.5＼&0.6＼&DB4＼&2.1＼&2.4＼&1.2＼&]

由表3可知，數據集結構比較標準、且分布比較集中，三個聚類算法所用時間相當，而當數據集的維度比較高時，可以得出該算法所處理的時間比較少，效率比較高。同其它聚類算法相比，該算法的時間效率較高。總之，算法COKS具有較高的準確率和時間效率。

5 結束語

需要用戶根據先驗知識提供聚類劃分個數K，但在具體應用中，聚類個數k往往是事先無法準確確定，這就限制傳統(tǒng)K-means算法的使用。該文采用了基于數據集的幾何結構而提出了有效性指標函數，并和K-means算法結合在一起使用，獲取數據集的最佳聚類個數。理論研究和實驗結果表明本文所提出的COKS算法具有比較好的性能與有效性。

參考文獻：

[1] Sun H， Wang S， Jiang Q. FCM-Based model selection algorithms for determining the number of cluster. Pattern Recognition， 2004，37（10）：2027-2037.

[2] 周世兵，徐振源，唐旭清.新的K-均值算法最佳聚類數確定方法[J].計算機工程與應用， 2010， 46（16）：27-31.

[3] Xie X， Beni G. A validity measure for fuzzy clustering. IEEE Trans， on Pattern Analysis and Machine Intelligence， 1991，13（8）：841-847.

[4] 孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學報，2008，19（1）：48-61.

[5] 周世兵，徐振源，唐旭清.K-means算法最佳聚類數確定方法[J].計算機應用， 2010， 30（8）：1995-1998.

[6] 陳黎飛，姜青山，王聲瑞. 基于層次劃分的最佳聚類數確定方法[J].軟件學報， 2008，19（1）：62-72.

[7] Foss A， Zaiane OR. A parameterless method for efficiently discovering clusters of arbitrary shape in large datasets. In： Kumar V， Tsumoto S， eds. Proc. of the ICDM， Los Alamitos： IEEE Computer Society Press， 2002.179-186.

[8] Agrawal R， Gehrke J， Gunopulos D， Raghavan P. Automate subspace clustering of high dimensional data. Data Mining and Knowledge Discovery， 2005， 11（1）：5-33.

[9] 于劍，程乾生.模糊聚類方法中的最佳聚類數的搜索范圍[J]，中國科學（E輯）， 2002，32（2）：274-280.

[10] Hong Z， Jiang Q， Dong H， Wang S. A new cluster validity index for fuzzy clustering. Computer Science， 2004，31（10）：121-125.

[11] Zhang T， Ramakrishnan R， Livny M. BIRCH： An efficient data clustering method for very large database. In： Jagadish HV， Mumick IS， eds. Proc. of the ACM-SIGMOD. New York： ACM Press， 1996.103-114.

[12] Brecheisen S， Kriegel HP， Pfeifle M. Multi-Step density-based clustering. Knowledge and Information Systems， 2006， 9（3）：284-308.

[13] Sudipio Guha， Rajeev Rastogi， Kyuseok Shim. CURE： an efficient clustering algorithm for large database [J]. Information Systems， 2001， 26（1）：35-58.