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

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

關(guān)鍵詞：K-means；最佳聚類數(shù)；聚類有效性指標；聚類

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

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

1 K-means算法

1.1 K-means算法介紹

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

輸入：數(shù)據(jù)集和該數(shù)據(jù)集的聚類個數(shù)k；

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

1）選擇k個數(shù)據(jù)對象作為初始質(zhì)心；

2）Repeat

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

4）重新計算每個類的質(zhì)心點；

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

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

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

2 聚類有效性指標

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

2.1 聚類有效性指標

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

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

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

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

其中，X，Y分別屬于類[Ci]，[Cj]中的數(shù)據(jù)對象，k為此時數(shù)據(jù)集DB被劃分的聚類個數(shù)。代入歐式距離公式再做簡單的變換，[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表示數(shù)據(jù)集DB被劃分的聚類個數(shù)，[xj]表示類[Ci]中的數(shù)據(jù)對象，[Ci]表示類[Ci]中數(shù)據(jù)對象的個數(shù)。我們可以得到：[Scat（C）]的值越小，說明類內(nèi)數(shù)據(jù)對象越緊湊；[Sep（C）]越大，說明類與類間隔越大。一般采用式5來平衡[Sep（C）]和[Scat（C）]之間的差異：

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

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

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

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

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

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

2.2最佳聚類數(shù)的確定

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

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

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

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

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

2.3 異常點的消除過程

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

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

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

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

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

3 最佳聚類數(shù)確定算法

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

3.1 聚類數(shù)K搜索范圍的確定

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

3.2 最佳聚類數(shù)確定算法（COKS）

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

輸入：數(shù)據(jù)集和數(shù)據(jù)集中數(shù)據(jù)對象的個數(shù)n；

輸出：有效性指標值及所對應(yīng)的聚類數(shù)和最佳聚類數(shù)。

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

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

a）調(diào)用K-means算法進行劃分；

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

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

3）根據(jù)式（8）獲取數(shù)組A中最小的聚類指標值以及所對應(yīng)的聚類劃分；

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

4 實驗驗證與分析

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

4.1實驗中的數(shù)據(jù)集

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

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

表1 測試數(shù)據(jù)集的屬性表

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

4.2實驗結(jié)果

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

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

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

圖1 數(shù)據(jù)集聚類結(jié)果圖

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

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

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

在實驗中，因為每個數(shù)據(jù)集要在每個算法運行多次。我們?nèi)∵@些時間的平均值則所用的時間如表3所示。

表3 不同算法運行時間

[數(shù)據(jù)集＼&運行時間（秒）＼&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可知，數(shù)據(jù)集結(jié)構(gòu)比較標準、且分布比較集中，三個聚類算法所用時間相當，而當數(shù)據(jù)集的維度比較高時，可以得出該算法所處理的時間比較少，效率比較高。同其它聚類算法相比，該算法的時間效率較高?？傊?，算法COKS具有較高的準確率和時間效率。

5 結(jié)束語

需要用戶根據(jù)先驗知識提供聚類劃分個數(shù)K，但在具體應(yīng)用中，聚類個數(shù)k往往是事先無法準確確定，這就限制傳統(tǒng)K-means算法的使用。該文采用了基于數(shù)據(jù)集的幾何結(jié)構(gòu)而提出了有效性指標函數(shù)，并和K-means算法結(jié)合在一起使用，獲取數(shù)據(jù)集的最佳聚類個數(shù)。理論研究和實驗結(jié)果表明本文所提出的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-均值算法最佳聚類數(shù)確定方法[J].計算機工程與應(yīng)用， 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].軟件學(xué)報，2008，19（1）：48-61.

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

[6] 陳黎飛，姜青山，王聲瑞. 基于層次劃分的最佳聚類數(shù)確定方法[J].軟件學(xué)報， 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] 于劍，程乾生.模糊聚類方法中的最佳聚類數(shù)的搜索范圍[J]，中國科學(xué)（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.