Kmeans算法最佳聚類數(shù)評價指標(biāo)研究

郭靖+侯蘇

摘要：聚類分析廣泛應(yīng)用于商務(wù)智能、圖像模式識別、Web搜索、生物學(xué)等領(lǐng)域，是一種無指導(dǎo)的觀察式學(xué)習(xí)。然而，絕大多數(shù)聚類分析算法都面臨著一個非常棘手的問題——最佳聚類數(shù)的確定。Kmeans是典型的基于劃分的聚類方法，它需要用戶輸入聚類數(shù)K，但這通常非常困難。聚類數(shù)的確定是決定聚類質(zhì)量的關(guān)鍵因素。雖然有許多被用來估計最優(yōu)聚類數(shù)的聚類評價指標(biāo)，但對于不同的聚類算法，不同的評價指標(biāo)效果差異很大。為確定針對Kmeans聚類算法效果最好的評價指標(biāo)，采用4種典型的不同聚類結(jié)構(gòu)特征的人工模擬數(shù)據(jù)以及來自UCI的真實數(shù)據(jù)集對7種評價指標(biāo)的性能進(jìn)行實驗比較，結(jié)果表明CH指標(biāo)和I指標(biāo)在評估Kmeans算法的最佳聚類數(shù)時效果較好。

關(guān)鍵詞關(guān)鍵詞：聚類指標(biāo)；Kmeans算法；聚類分析；聚類數(shù)

DOIDOI：10.11907/rjdk.171885

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2017）011000504

0引言

聚類分析（Cluster Analysis）是一種無指導(dǎo)的觀察式學(xué)習(xí)，其基本原理是根據(jù)樣本自身屬性，在沒有任何模式可供參考或依循，即沒有先驗知識的情況下，用數(shù)學(xué)方法按照某種相似性或差異性指標(biāo)，計算樣本之間的相似度，并按這種相似度對樣本進(jìn)行聚類。近年來，隨著聚類分析的逐漸成熟，產(chǎn)生了很多聚類算法。根據(jù)基本思想不同，大致可以將聚類算法分為6大類：基于層次的聚類算法（CURE、ROCK、CHAMELEON）、基于劃分的聚類算法（Kmeans、Kmedoids、PCM）、基于密度的聚類算法（DBSCAN、OPTICS、FDC）、基于網(wǎng)格的聚類算法（STING、CLIQUE、OPTIGRID）、基于神經(jīng)網(wǎng)絡(luò)的聚類算法（自組織神經(jīng)網(wǎng)絡(luò)SOM）與基于統(tǒng)計學(xué)的聚類算法（COBWeb、CLASSIT、AutoClass）。Kmeans聚類算法是一種簡潔、高效的基于劃分的聚類算法[1]，它的偽代碼如下所示：

2實驗與比較分析

本文使用Kmeans算法將實驗數(shù)據(jù)集劃分為k個簇，并使用上述7種評價指標(biāo)估計最優(yōu)聚類數(shù)。實驗采用4種典型的不同聚類結(jié)構(gòu)特征的人工模擬數(shù)據(jù)集以及來自UCI[9]的真實數(shù)據(jù)集。k的取值范圍為[2，kmax]，根據(jù)一般經(jīng)驗準(zhǔn)則，k≤n，所以kmax=intn，其中，n是數(shù)據(jù)集的樣本總數(shù)。并且，為使Kmeans算法擁有穩(wěn)定的較好聚類結(jié)果，選擇文獻(xiàn)[10]中的方法選取初始聚類中心，具體方法如下：①首先選擇距離全部樣本中心最近的一個樣本對象作為第1個初始聚類中心Z1；②當(dāng)聚類數(shù)為2時，從剩余所有樣本中選擇距離Z1最遠(yuǎn)的樣本對象作為第2個初始聚類中心Z2；③當(dāng)聚類數(shù)為3時，計算剩余各樣本與Z1、Z2之間的距離，并求出它們之中的最小值di，根據(jù)Dt=max{di}，選擇第t個樣本對象作為第3個初始聚類中心；④當(dāng)聚類數(shù)為k并且k≤kmax時，針對已存在的k-1個初始聚類中心，計算剩余各樣本到各聚類中心的距離dij，并計算出Dr=max{min{di1，di2，…，di（k-1）}}，選擇第r個樣本作為第k個初始聚類中心。

2.1人工模擬數(shù)據(jù)集實驗

人工模擬數(shù)據(jù)集共有4個，包括簡單的和復(fù)雜的聚類結(jié)構(gòu)特征：相距較遠(yuǎn)的完全分離的聚類（特征A）、靠近的完全分離的聚類（特征B）、小的聚類靠近大的聚類（特征C），以及輕微重疊的聚類（特征D），詳細(xì)信息如表1所示。圖1給出了人工模擬數(shù)據(jù)集的二維平面。

表2給出了各種聚類評價指標(biāo)得出最佳聚類數(shù)的結(jié)果，可以看出，CH指標(biāo)最好，I指標(biāo)次之，而其它幾個指標(biāo)的效果不盡如人意。對于相距較遠(yuǎn)的完全分離的聚類（特征A），所有指標(biāo)都可以得到正確的聚類數(shù)，但只要有兩個聚類靠得比較近時，XieBeni指標(biāo)、DB指標(biāo)、Dunn指標(biāo)、BWP指標(biāo)和Sil指標(biāo)就不能得到最佳聚類數(shù)。

2.2UCI真實數(shù)據(jù)集實驗

UCI數(shù)據(jù)集是著名的關(guān)于機(jī)器學(xué)習(xí)的真實數(shù)據(jù)集。此次實驗的4組數(shù)據(jù)集都是來自UCI的常用數(shù)據(jù)集，分別是iris數(shù)據(jù)集、QualitativeBankruptcy（簡稱QB）數(shù)據(jù)集、seeds數(shù)據(jù)集和Vertebral Column（簡稱VC）數(shù)據(jù)集，詳細(xì)信息如表3所示。

表4給出了真實數(shù)據(jù)集的實驗結(jié)果，從中可以看到

CH指標(biāo)和I指標(biāo)效果較好，其它幾個指標(biāo)僅在聚類數(shù)為2時得到正確結(jié)果。真實數(shù)據(jù)集比人工模擬數(shù)據(jù)集的空間結(jié)構(gòu)復(fù)雜得多，因此正確估計真實數(shù)據(jù)集的分類數(shù)是非常困難的。

3結(jié)語

通過對上述7種聚類質(zhì)量評價指標(biāo)的實驗比較分析，可以看到XieBeni指標(biāo)、DB指標(biāo)、Dunn指標(biāo)、BWP指標(biāo)和Sil指標(biāo)僅在評估相距較遠(yuǎn)且完全分離的聚類結(jié)構(gòu)特征的最佳聚類數(shù)時有著較好效果，而對于其它聚類結(jié)構(gòu)特征效果并不好。由于真實數(shù)據(jù)集聚類結(jié)構(gòu)特征的復(fù)雜性，只有CH指標(biāo)和I指標(biāo)效果顯著，XieBeni指標(biāo)、DB指標(biāo)、BWP指標(biāo)和Sil指標(biāo)由于自身的局限性，僅對聚類數(shù)為2的數(shù)據(jù)集效果較好。因此，在評估Kmeans算法的最佳聚類數(shù)時，CH指標(biāo)和I指標(biāo)是兩個不錯的選擇。

參考文獻(xiàn)參考文獻(xiàn)：

[1]FAHIM A， SALEM A E， TORKEY F， et al. An efficient KMeans with good initial starting points[J]. Computer Sciences & Telecommunications，2009.

[2]CALINSKI R B， HARABASZ J. A dendrite method for cluster analysis[J].Communications in Statistics，1974，3（1）：127.endprint

[3]MAULIK U， BANDYOPADHYAY S. Performance evaluation of some clustering algorithms and validity indices[J]. Pattern Analysis and Machine Intelligence，2002（12）：16501654.

[4]XIE X L， BENI G. A validity measure for fuzzy clustering[J].Pattern Analysis and Machine Intelligence，1991（13）：841847.

[5]DAVIES D L， BOULDIN D W. A cluster separation measure[J]. Pattern Anal Machine Intell，1979 （4）：224227.

[6]DUNN J C. A fuzzy relative of the ISODATA process and its use in detecing compact wellseparated clusters[J].Journal Cybernetics，1973，3（3）：3257.

[7]ZHOU S B， ZHENYUAN X U. New method for determining optimal number of clusters in Kmeans clustering algorithm[J]. Journal of Computer Applications，2010，30（8）：19951998.

[8]DUDOIT S， FRIDLYAND J.A prediction based resampling method forestimating the number of clusters in a dataset[J].Genome Biology，2002，3（7）：121.

[9]BLAKE C L，MERZ C J.UCI repository of machine learning databases[EB/OL]. http：//archive.ics.uci.edu/ml/.

[10]周世兵，徐振源，唐旭清.新的K均值算法最佳聚類數(shù)確定方法[J].計算機(jī)工程與應(yīng)用，2010，46（16）：2731.

責(zé)任編輯（責(zé)任編輯：黃健）endprint