Kmeans算法最佳聚類數評價指標研究

郭靖+侯蘇

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

關鍵詞關鍵詞：聚類指標；Kmeans算法；聚類分析；聚類數

DOIDOI：10.11907/rjdk.171885

中圖分類號：TP301

文獻標識碼：A文章編號文章編號：16727800（2017）011000504

0引言

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

2實驗與比較分析

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

2.1人工模擬數據集實驗

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

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

2.2UCI真實數據集實驗

UCI數據集是著名的關于機器學習的真實數據集。此次實驗的4組數據集都是來自UCI的常用數據集，分別是iris數據集、QualitativeBankruptcy（簡稱QB）數據集、seeds數據集和Vertebral Column（簡稱VC）數據集，詳細信息如表3所示。

表4給出了真實數據集的實驗結果，從中可以看到

CH指標和I指標效果較好，其它幾個指標僅在聚類數為2時得到正確結果。真實數據集比人工模擬數據集的空間結構復雜得多，因此正確估計真實數據集的分類數是非常困難的。

3結語

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

參考文獻參考文獻：

[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均值算法最佳聚類數確定方法[J].計算機工程與應用，2010，46（16）：2731.

責任編輯（責任編輯：黃健）endprint