聚類數(shù)" title="最佳聚類數(shù)" target="_blank">最佳聚類數(shù)的判定通常采用一種基于迭代的trial-and-error過程[1]進行，該過程是在給定的數(shù)據(jù)集上，使用不同的參數(shù)（通常是聚類數(shù)k）,運行特定的聚類算法,對數(shù)據(jù)集進行不同的劃分，然后計算每種劃分的指標值。通過比較各個指標值，其中符合預(yù)定條件的指標值所對應(yīng)的聚類個數(shù)被認為是最佳的聚類數(shù)。實際上，trial-and-error過程存在兩個不足之處:(1)聚類數(shù)k值的確定對于缺乏豐富聚類分析經(jīng)驗的用戶來說是難以準確確定的[2]，這需進一步提出尋找更合理的聚類數(shù)k的方法; (2)目前提出的許多檢驗聚類有效性的指標，如Vxie指標[3]、Vwsj指標[1]等，但這些指標都是基于某個特定聚類算法提出的，在實際應(yīng)用中受到了極大限制。鑒于上述兩種情況，本文借鑒層次聚類的思想一次性地生成所有可能的聚類劃分，并計算其對應(yīng)的有效性指標，然后選擇指標值最小的聚類劃分來估計數(shù)據(jù)集的最佳聚類數(shù)，這樣可以避免對大型數(shù)據(jù)集的反復聚類，而且該過程不依賴于特定的聚類算法。

1 聚類有效性指標
    本文采用的是一個不依賴于具體算法的有效性指標Q(C)來評估數(shù)據(jù)集的聚類效果。該有效性指標主要是通過類內(nèi)數(shù)據(jù)對象的緊湊度以及類間數(shù)據(jù)對象的分離度[4]衡量聚類質(zhì)量。


1.3 噪聲點與孤立點的消除
    基于數(shù)據(jù)集中存在的噪聲點與孤立點對聚類結(jié)果的影響，本文認為單獨利用有效性指標所得出的聚類數(shù)為最佳聚類數(shù)k*的結(jié)論并不成立。根據(jù)參考文獻[4-6]，采用基于MDL(Minimal Description Length)的剪枝方法對結(jié)果進行處理。具體處理方法如下：

    兩個數(shù)據(jù)對象樣本間的相似系數(shù)等于d個屬性間相似系數(shù)之和，每對屬性間的相似系數(shù)等于每對屬性的曼哈頓距離加1的倒數(shù)。式(9)把兩個數(shù)據(jù)對象間的每個屬性的相似系數(shù)都映射到(0,1)的區(qū)間,可以得到,當s(xi,xj)的值越大，則數(shù)據(jù)對象xi和xj越相似。
2.2 最佳聚類數(shù)確定算法(COBH)
    本文介紹的最佳聚類數(shù)確定算法(COBH)主要是借鑒層次聚類的思想。該算法是在初始化時，使得數(shù)據(jù)集的聚類個數(shù)k為數(shù)據(jù)對象的個數(shù)n，再根據(jù)式(9)計算數(shù)據(jù)集中的任意兩個數(shù)據(jù)對象的相似度s(i,j)，并將它們存儲在一個一維數(shù)組D中,將數(shù)組D的元素從大到小排序；對數(shù)組D中的當前元素，首先判斷這兩個數(shù)據(jù)對象是否已被合并到類中,如果沒有，則將這兩個數(shù)據(jù)對象合并成一個類，如果其中一個數(shù)據(jù)對象已被合并到某一個類中，則將另一個對象也合并到那個類中；如果它們已分別被合并到兩個不同的類，則將它們所在的那兩個類合并成一個類，如果它們已經(jīng)屬于同一個類，則放棄此次合并。此時，根據(jù)式(6)計算聚類有效性指標Q(C)的值，連同此時的聚類劃分情況一起保存在數(shù)組A中，此時數(shù)據(jù)集的聚類個數(shù)k=k-1；然后取D中的下一個元素繼續(xù)進行判斷與計算，直到數(shù)據(jù)集的聚類個數(shù)為1時結(jié)束；根據(jù)獲取數(shù)組A中最小的聚類指標值以及所對應(yīng)的聚類劃分；將所選擇的最小聚類指標值以及所對應(yīng)的聚類劃分情況，按式(7)的過程對其中被識別為噪聲點與孤立點所組成的類進行剔除，最后獲得最佳的聚類數(shù)kopt,并且得到該算法的時間復雜度為O(n2)。
3 實驗與分析
     為了驗證COBH算法的性能與有效性。本文選用5個數(shù)據(jù)集，分別來自人工合成與UCI的標準數(shù)據(jù)集庫。為了驗證該算法所采用的有效性指標在進行運算時具有較高的效率與性能，本文選擇了基于數(shù)據(jù)樣本幾何結(jié)構(gòu)的兩種具有代表意義的指標Vxie[3]和Vwsj[1]作對比,這兩種指標都是基于FCM聚類算法。并選擇新近提出基于層次劃分的最佳聚類數(shù)確定算法(COPS)也做為對比對象。
     實驗所使用的PC機為CPU 2.80 GHz,內(nèi)存為2 GB，算法采用VC6.0進行實現(xiàn)。
3.1數(shù)據(jù)集的選擇
    第一類數(shù)據(jù)集是人工合成的數(shù)據(jù)集。實驗采用2個人工合成的數(shù)據(jù)集，分別為數(shù)據(jù)集DB1和DB2。數(shù)據(jù)集DB1由中心分別為(0,0)和(40,40)的二維高斯分布數(shù)據(jù)對象組成，數(shù)據(jù)樣本均為400個。主要特征是兩個聚類之間屬性差別比較大。數(shù)據(jù)集DB2是以(0,0)、(40,40)和(60,60)為中心點的人工合成的數(shù)據(jù)集，它是一個二維三個類的數(shù)據(jù)集，其主要結(jié)構(gòu)特征為輕微重疊、松散的、和帶有少量噪聲點的聚類結(jié)構(gòu)。
   第二類數(shù)據(jù)集為標準數(shù)據(jù)集。本實驗采用3個來自UCI的標準數(shù)據(jù)集，分別是IRIS、Wiconsin breast cancer和Vowel recognition。在本文中的數(shù)據(jù)集代號分別表示為DB3、DB4和DB5。
3.2實驗結(jié)果
    本次實驗分兩組進行，第一組是驗證算法COBH在數(shù)據(jù)集的最佳聚類數(shù)確定方面的有效性。分別運行所選擇的5個數(shù)據(jù)集得到的聚類數(shù)與有效性指標值的關(guān)系，如圖1所示。

    由圖1得出,由于數(shù)據(jù)集中的數(shù)據(jù)對象分布以及幾何結(jié)構(gòu)不同，算法COBH對數(shù)據(jù)集處理效果也有所不同。對于數(shù)據(jù)集DB1，由于該數(shù)據(jù)集是在合成過程中保持了類與類之間較大的差異性，而且分布比較集中、幾何結(jié)構(gòu)比較標準，所以該方法通過處理得到的指標值能更好地反應(yīng)出最佳聚類數(shù)，如圖1(a)所示。當聚類數(shù)為2時所對應(yīng)的有效性指標值與其他指標值差別比較明顯，而且此時其有效性指標最小。對于數(shù)據(jù)集DB2，由于其存在噪聲點，所以在剛開始時，其指標值變化特別明顯，然而當聚類數(shù)達到15以上時，指標值變化趨于平穩(wěn)，如圖1(b)所示。對于數(shù)據(jù)集DB3，由于其數(shù)據(jù)對象個數(shù)比較少，而且還包含兩個重疊的簇，算法也能得到準確的結(jié)果，說明該算法能夠有效地區(qū)分重疊的簇,如圖1(c)所示。數(shù)據(jù)集DB4如圖1(d)所示，當其聚類數(shù)由3降到2時,其有效性指標值差異很小，但算法COBH也能夠做出正確的區(qū)分。而對于數(shù)據(jù)集維數(shù)比較高的DB5，該算法能夠識別出正確的聚類數(shù)，而當聚類個數(shù)達到20時,其有效性指標值逐漸趨近于平穩(wěn)，說明算法COBH對數(shù)據(jù)集DB5處理的結(jié)果比較優(yōu)良,如圖1(e)所示。
    第二組主要是驗證算法COBH的性能與時間效率。本文采用參考文獻[1,3]中基于FCM算法的有效性指標Vxie和Vwsj作為對比對象。在實驗中，設(shè)置FCM聚類算法的模糊因子m為2;另外本文也選擇參考文獻[4]所提出的COPS算法作為對比,不同算法所獲得的最佳聚類數(shù)情況如表1所示。在實驗中，每個數(shù)據(jù)集要在每個算法中運行多次并記錄每次運行時間，取這些時間的平均值作為該算法處理該數(shù)據(jù)集所用的時間，如表2所示。

    由表2可以得出，對于結(jié)構(gòu)比較標準、分布比較集中的數(shù)據(jù)集DB1，4種算法運行的時間幾乎相似。而當數(shù)據(jù)集的個數(shù)、維度不斷增加時，算法COBH和COPS表現(xiàn)的效率更佳。特別當數(shù)據(jù)對象的維度較高時，算法COBH的效率會更高，且在時間上要比其他算法快。COPS算法首先確定單個維度上的相似數(shù)據(jù)對象，進而確定高維空間中的相似數(shù)據(jù)對象，其計算量比較大。而算法COBH則是通過新的相似判定方法將數(shù)據(jù)對象從整體進行相似性判定。所以隨著數(shù)據(jù)對象的維數(shù)增加，其效率明顯提高。
    通常確定數(shù)據(jù)集的最佳聚類數(shù)的方法，一般需要用戶根據(jù)先驗知識提供準確的聚類數(shù)k并運行某個特定的算法，這樣就使其應(yīng)用受到了限制。本文提出了新的確定數(shù)據(jù)集的最佳聚類數(shù)的算法(COBH)，該算法借鑒了層次算法的思想，彌補了傳統(tǒng)算法的缺點，同時能獲得較好的聚類結(jié)果。理論研究和實驗結(jié)果證明,本文所提出的算法具有良好的性能及較高的時間效率。
參考文獻
[1] SUN H, WANG S, JIANG Q. FCM-Based model selection algorithms for determining the number of cluster[J].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[J].IEEE Trans, on Pattern Analysis and Machine Intelligence, 1991,13(8):841-847.
[4] 陳黎飛,姜青山,王聲瑞. 基于層次劃分的最佳聚類數(shù)確定方法[J]. 軟件學報, 2008,19(1):62-72.
[5]     FOSS A, ZAIANE O R. A parameterless method for efficiently discovering clusters of arbitrary shape in large data sets[C]. Proc. of the ICDM, Los Alamitos: IEEE Computer Society Press, 2002.
[6] AGRAWAL R, GEHRKE J, GUNOPULOS D, et al. Automate subspace clustering of high dimensional data[J]. Data Mining and Knowledge Discovery, 2005,11(1):5-33.
[7] 孟佳娜,鄧俐伶,等.一種改進的k均值聚類算法[J].大連民族學院學報,2011,13(3):274-276.