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

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


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

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

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

    由表2可以得出，對(duì)于結(jié)構(gòu)比較標(biāo)準(zhǔn)、分布比較集中的數(shù)據(jù)集DB1，4種算法運(yùn)行的時(shí)間幾乎相似。而當(dāng)數(shù)據(jù)集的個(gè)數(shù)、維度不斷增加時(shí)，算法COBH和COPS表現(xiàn)的效率更佳。特別當(dāng)數(shù)據(jù)對(duì)象的維度較高時(shí)，算法COBH的效率會(huì)更高，且在時(shí)間上要比其他算法快。COPS算法首先確定單個(gè)維度上的相似數(shù)據(jù)對(duì)象，進(jìn)而確定高維空間中的相似數(shù)據(jù)對(duì)象，其計(jì)算量比較大。而算法COBH則是通過(guò)新的相似判定方法將數(shù)據(jù)對(duì)象從整體進(jìn)行相似性判定。所以隨著數(shù)據(jù)對(duì)象的維數(shù)增加，其效率明顯提高。
    通常確定數(shù)據(jù)集的最佳聚類(lèi)數(shù)的方法，一般需要用戶根據(jù)先驗(yàn)知識(shí)提供準(zhǔn)確的聚類(lèi)數(shù)k并運(yùn)行某個(gè)特定的算法，這樣就使其應(yīng)用受到了限制。本文提出了新的確定數(shù)據(jù)集的最佳聚類(lèi)數(shù)的算法(COBH)，該算法借鑒了層次算法的思想，彌補(bǔ)了傳統(tǒng)算法的缺點(diǎn)，同時(shí)能獲得較好的聚類(lèi)結(jié)果。理論研究和實(shí)驗(yàn)結(jié)果證明,本文所提出的算法具有良好的性能及較高的時(shí)間效率。
參考文獻(xiàn)
[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-均值算法最佳聚類(lèi)數(shù)確定方法[J]. 計(jì)算機(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] 陳黎飛,姜青山,王聲瑞. 基于層次劃分的最佳聚類(lèi)數(shù)確定方法[J]. 軟件學(xué)報(bào), 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] 孟佳娜,鄧?yán)?等.一種改進(jìn)的k均值聚類(lèi)算法[J].大連民族學(xué)院學(xué)報(bào),2011,13(3):274-276.