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

郭靖+侯蘇

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

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

DOIDOI：10.11907/rjdk.171885

中圖分類號(hào)：TP301

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

0引言

聚類分析（Cluster Analysis）是一種無(wú)指導(dǎo)的觀察式學(xué)習(xí)，其基本原理是根據(jù)樣本自身屬性，在沒(méi)有任何模式可供參考或依循，即沒(méi)有先驗(yàn)知識(shí)的情況下，用數(shù)學(xué)方法按照某種相似性或差異性指標(biāo)，計(jì)算樣本之間的相似度，并按這種相似度對(duì)樣本進(jìn)行聚類。近年來(lái)，隨著聚類分析的逐漸成熟，產(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)計(jì)學(xué)的聚類算法（COBWeb、CLASSIT、AutoClass）。Kmeans聚類算法是一種簡(jiǎn)潔、高效的基于劃分的聚類算法[1]，它的偽代碼如下所示：

2實(shí)驗(yàn)與比較分析

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

2.1人工模擬數(shù)據(jù)集實(shí)驗(yàn)

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

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

2.2UCI真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

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

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

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

3結(jié)語(yǔ)

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

參考文獻(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ì)算機(jī)工程與應(yīng)用，2010，46（16）：2731.

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