最近最遠(yuǎn)得分的聚類性能評(píng)價(jià)指標(biāo)

馮柳偉，常冬霞，鄧勇，趙耀

(1. 北京交通大學(xué) 信息科學(xué)研究所，北京 100044；2. 北京交通大學(xué) 計(jì)算機(jī)與信息科學(xué)學(xué)院，北京 100044； 3.中國(guó)科學(xué)院 軟件研究所，北京 100190)

最近最遠(yuǎn)得分的聚類性能評(píng)價(jià)指標(biāo)

馮柳偉，常冬霞，鄧勇，趙耀

(1. 北京交通大學(xué) 信息科學(xué)研究所，北京 100044；2. 北京交通大學(xué) 計(jì)算機(jī)與信息科學(xué)學(xué)院，北京 100044； 3.中國(guó)科學(xué)院 軟件研究所，北京 100190)

聚類算法是數(shù)據(jù)分析中廣泛使用的方法之一，而類別數(shù)往往是決定聚類算法性能的關(guān)鍵。目前，大部分聚類算法需要預(yù)先給定類別數(shù)，在很多情況下，很難根據(jù)數(shù)據(jù)集的先驗(yàn)知識(shí)獲得有效的類別數(shù)。因此，為了獲得數(shù)據(jù)集的類別數(shù)，本文基于最近鄰一致性和最遠(yuǎn)鄰相異性的準(zhǔn)則，提出了一種最近最遠(yuǎn)得分評(píng)價(jià)指標(biāo)，并在此基礎(chǔ)上提出了一種自動(dòng)確定類別數(shù)的聚類算法。實(shí)驗(yàn)結(jié)果證明了所提評(píng)價(jià)指標(biāo)在確定類別數(shù)時(shí)的有效性和可行性。

最近鄰一致性；最遠(yuǎn)鄰相異性；K-means聚類算法；評(píng)分機(jī)制；評(píng)價(jià)指標(biāo)；層次聚類

聚類算法作為數(shù)據(jù)分析中廣泛使用的主要方法之一，已經(jīng)廣泛應(yīng)用于模式識(shí)別、機(jī)器學(xué)習(xí)、圖像處理和數(shù)據(jù)挖掘等方面[1-4]。簡(jiǎn)單來(lái)說(shuō)，聚類就是根據(jù)數(shù)據(jù)的特征將數(shù)據(jù)劃分為幾類，使得同一類別數(shù)據(jù)間的相似度盡可能大，而不同類別數(shù)據(jù)間的相似度則盡可能小。目前，常用聚類算法可以分為劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法。事實(shí)上，很多聚類算法往往需要預(yù)先知道聚類問(wèn)題的類別數(shù)。然而，在很多實(shí)際情況下，很難根據(jù)數(shù)據(jù)特征獲得有效的類別數(shù)。因此，為了獲得有效的類別數(shù)，很多學(xué)者基于聚類的不同性質(zhì)分別提出了一系列評(píng)價(jià)聚類結(jié)果的評(píng)價(jià)指標(biāo)。對(duì)給定范圍的類別數(shù)依次對(duì)數(shù)據(jù)集進(jìn)行聚類，并采用評(píng)價(jià)指標(biāo)對(duì)每次的聚類結(jié)果進(jìn)行評(píng)價(jià)，然后選擇一個(gè)使評(píng)價(jià)指標(biāo)最優(yōu)的類別數(shù)。目前，常用有效性評(píng)價(jià)指標(biāo)大致可以分為3種類型，分別是基于數(shù)據(jù)集模糊劃分的指標(biāo)、基于數(shù)據(jù)集樣本幾何結(jié)構(gòu)的指標(biāo)和基于數(shù)據(jù)集統(tǒng)計(jì)信息的指標(biāo)。其中，1991年，Xie等[5]利用模糊聚類的目標(biāo)函數(shù)，同時(shí)考慮數(shù)據(jù)集本身的結(jié)構(gòu)和模糊隸屬度的性質(zhì)，提出了Xie-Beni指標(biāo)。之后，很多學(xué)者基于數(shù)據(jù)集模糊劃分提出了一系列改善的評(píng)價(jià)指標(biāo)[6-9]，但這些指標(biāo)不適合對(duì)硬聚類算法的聚類結(jié)果進(jìn)行評(píng)價(jià)。另外一類是基于數(shù)據(jù)集樣本幾何結(jié)構(gòu)的評(píng)價(jià)指標(biāo)[10-16]。1974年，Caliński 和 Harabasz提出了基于全部樣本的類內(nèi)離差矩陣和類間離差矩陣測(cè)度的 Caliński-Harabasz(CH)指標(biāo)[12]。1979年，Davies和 Bouldin提出了基于樣本的類內(nèi)散度與各聚類中心間距離測(cè)度的 Davies-Bouldin(DB)指標(biāo)[13],以及隨后提出的基于最大化類內(nèi)相似度和最小化類間相似度目標(biāo)的Weighted inter-intra(Wint)指標(biāo)[14]、基于樣本類內(nèi)離差矩陣的Krzanowski-Lai(KL)指標(biāo)[15]、周世兵等提出的基于樣本間的最小類間距離與類內(nèi)距離的Between-Within Proportion(BWP)指標(biāo)[16]。但是這些評(píng)價(jià)指標(biāo)均具有一定的局限性，對(duì)數(shù)據(jù)結(jié)構(gòu)無(wú)法完全分離的數(shù)據(jù)集進(jìn)行評(píng)價(jià)得到的結(jié)果并不理想。2007年，Kapp等基于數(shù)據(jù)集統(tǒng)計(jì)的思想，使用類內(nèi)數(shù)據(jù)點(diǎn)的in-group比例來(lái)評(píng)價(jià)聚類結(jié)果，提出了In-Group Proportion(IGP)評(píng)價(jià)指標(biāo)[17]。該評(píng)價(jià)指標(biāo)使用樣本與其最近鄰樣本劃分到同一類的比例來(lái)衡量聚類結(jié)果的質(zhì)量。但是由于IGP只關(guān)注最近鄰一致性，使得IGP指標(biāo)值會(huì)隨著聚類數(shù)的增加而減少，導(dǎo)致在很多實(shí)際情況下，利用IGP指標(biāo)得到的類別數(shù)往往比實(shí)際的類別數(shù)小。針對(duì)這種情況，本文基于最近鄰一致性和最遠(yuǎn)鄰相異性的原則，提出了一種最近最遠(yuǎn)得分指標(biāo)(NFS)，并基于此指標(biāo)，提出了一種基于NFS指標(biāo)自動(dòng)確定類別數(shù)的聚類算法。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提的評(píng)價(jià)指標(biāo)的有效性和可行性。

1 已有評(píng)價(jià)指標(biāo)

眾所周知，很多聚類算法需要用戶根據(jù)先驗(yàn)知識(shí)給出算法所需要的類別數(shù)。但是，在很多實(shí)際應(yīng)用中很難獲得有效的先驗(yàn)知識(shí)，因此，確定聚類問(wèn)題的類別數(shù)成為了聚類分析的一個(gè)研究的熱點(diǎn)。目前傳統(tǒng)的確定類別數(shù)的方法是根據(jù)評(píng)價(jià)指標(biāo)來(lái)確定類別數(shù)。至今提出的評(píng)價(jià)指標(biāo)包括CH指標(biāo)、BWP指標(biāo)和IGP指標(biāo)等。

1.1 Calinski-Harabasz(CH)指標(biāo)

CH指標(biāo)是Caliński和Harabasz提出的確定最佳聚類數(shù)的評(píng)價(jià)指標(biāo)[12]。該指標(biāo)是一種基于樣本的類內(nèi)距離和類間離差矩陣的測(cè)度，其判斷函數(shù)為

式中：n為數(shù)據(jù)集樣本數(shù),K為類別數(shù)。且

CH指標(biāo)值越大表示聚類結(jié)果的類內(nèi)距離越小而類間距離越大，聚類結(jié)果性能越好。但是隨著類別數(shù)搜索范圍的變化，CH指標(biāo)得到的最佳聚類數(shù)會(huì)發(fā)生變化，并且隨著搜索范圍增大，CH指標(biāo)得到的最佳聚類數(shù)有逐漸增大的趨勢(shì)[18]。

1.2 BWP指標(biāo)

BWP指標(biāo)是周世兵等人提出的一種基于樣本的幾何結(jié)構(gòu)設(shè)計(jì)的確定聚類類別數(shù)的評(píng)價(jià)指標(biāo)[16]，該指標(biāo)利用聚類結(jié)果的類內(nèi)緊密性和類間分離性來(lái)衡量聚類結(jié)果。指標(biāo)的最大值對(duì)應(yīng)的類數(shù)作為聚類數(shù)。該指標(biāo)的判斷函數(shù)為

式中：K是類別數(shù)，bwp(i,j)為

式中:b(i,j)是第j類中的第i個(gè)樣本到其他每類中樣本平均距離的最小值，稱為最小類間距；w(i,j)是第j類中的第i個(gè)樣本的類內(nèi)距離。且

BWP指標(biāo)值越大則表示聚類結(jié)果的類內(nèi)越緊密而類間越遠(yuǎn)離，聚類結(jié)果性能越好。但是該評(píng)價(jià)指標(biāo)不適合非完全分離的數(shù)據(jù)集。

1.3 IGP指標(biāo)

IGP指標(biāo)是Kapp提出的評(píng)價(jià)指標(biāo)[17]。此指標(biāo)的設(shè)計(jì)思想是：當(dāng)對(duì)新的樣本進(jìn)行分類時(shí)，新樣本應(yīng)該被劃分到與其最相似的樣本所在類別。因此該指標(biāo)使用樣本與其最近鄰樣本劃分到同一類的比例來(lái)衡量聚類結(jié)果的質(zhì)量。該指標(biāo)的評(píng)價(jià)函數(shù)為

式中：K是類別數(shù)；igp(u,X)表示數(shù)據(jù)集X中的第u類的指標(biāo)值，且

IGP指標(biāo)的值越大表示樣本和其最近鄰劃分到同一類的概率越高，聚類結(jié)果越好。但是IGP指標(biāo)只關(guān)注了最近鄰一致性，使得IGP指標(biāo)值不適合判斷非完全分離的數(shù)據(jù)集。

2 最近最遠(yuǎn)得分評(píng)價(jià)指標(biāo)

為了能準(zhǔn)確地得到聚類問(wèn)題的類別數(shù)，本文在基于最近鄰一致性和最遠(yuǎn)鄰相異性的原則上，提出了最近最遠(yuǎn)得分(nearest and furthest score，NFS)評(píng)價(jià)指標(biāo)。

2.1 相關(guān)概念定義

定義1 最近得分。定義ns(i)是第i個(gè)樣本的最近得分，第j個(gè)樣本是距離其最近的樣本，若樣本i與樣本j屬于同一類別，則第i個(gè)樣本的最近得分值為1；否則其最近得分值為-1，即

式中：sc(i)代表第i個(gè)樣本所屬的類別，sc(j)代表距離樣本i最近的樣本j所屬的類別。

定義2 最遠(yuǎn)得分。定義fs(i)是第i個(gè)樣本的最遠(yuǎn)得分，第l個(gè)樣本是距離其最遠(yuǎn)的樣本，若樣本i與樣本l屬于不同類別，則第i個(gè)樣本的最遠(yuǎn)得分值為1，否則其最遠(yuǎn)得分值-1，即

式中：sc(i)代表第i個(gè)樣本所屬的類別；sc(l)代表距離樣本i最遠(yuǎn)的樣本l所屬的類別。

定義3 樣本得分。定義s(i)是第i個(gè)樣本的得分值，則第i個(gè)樣本的最近得分和最遠(yuǎn)得分的平均值為第i個(gè)樣本的得分，即

定義4 每類的得分。定義cs(j)為第j類的得分，其定義為屬于第j類的所有樣本的得分的平均值，即

式中nj為第j類中的樣本總數(shù)。

定義5 NFS。定義nfs(K)為在類別數(shù)為K下聚類結(jié)果的最近最遠(yuǎn)得分，定義為所有類得分的平均值，即

式中K是類別數(shù)。

2.2 NFS指標(biāo)的分析

NFS指標(biāo)的設(shè)計(jì)原則是每個(gè)樣本應(yīng)該和距離其最近的樣本劃分到同一類別中，而與距離其最遠(yuǎn)的樣本劃分到不同類別中。因此，每個(gè)樣本擁有兩個(gè)影響評(píng)分的因子，分別是最近得分因子和最遠(yuǎn)得分因子。對(duì)于最近得分因子，如果某個(gè)樣本與距離其最近的樣本劃分到同一類中，則得1分，表示對(duì)此聚類結(jié)果的支持，而如果劃分到不同類中，則得-1分，表示對(duì)此聚類結(jié)果的反對(duì)。最遠(yuǎn)得分因子的規(guī)定也是如此。

隨著類別數(shù)的增加，樣本和其最近鄰樣本被劃分到不同類別中的概率將會(huì)增加，從而導(dǎo)致了最近得分累積和的減少；然而隨著類別數(shù)的增加，樣本和其最遠(yuǎn)鄰樣本被劃分到同一類的概率將會(huì)減少，從而導(dǎo)致了最遠(yuǎn)得分累積和的增加。因此，在評(píng)價(jià)聚類結(jié)果時(shí)僅采用最近得分或最遠(yuǎn)得分將很難得到正確的類別數(shù)，需要綜合利用這兩個(gè)得分才能獲得好的聚類結(jié)果。為了說(shuō)明這個(gè)問(wèn)題，我們將利用圖1所示的數(shù)據(jù)集在不同類別數(shù)下的聚類結(jié)果來(lái)說(shuō)明同時(shí)考慮最近得分和最遠(yuǎn)得分的必要性。觀察圖1所示數(shù)據(jù)集，可知此數(shù)據(jù)集的最佳類別數(shù)為4。如果只考慮最近鄰得分時(shí)，如圖1(a)所示，當(dāng)K=2時(shí)，所有樣本和其最近鄰樣本都在同一類中，而如圖1(b)和圖1(c)所示，當(dāng)K=3或K=4 時(shí)，樣本和其最近鄰劃分到不同類的比率就會(huì)增大，聚類結(jié)果的最近得分值會(huì)下降，因此K=2時(shí)，使最近得分值達(dá)到最大，故采用最近得分準(zhǔn)則所得到的最佳類別數(shù)為2。而如果只考慮最遠(yuǎn)得分時(shí)，如圖1(a)所示，當(dāng)K=2時(shí)，樣本和其最遠(yuǎn)鄰樣本被劃分到同一類的比率很大，而如圖1(b)和圖1(c)所示，當(dāng)K=3或K=4 時(shí)，樣本與其最遠(yuǎn)鄰樣本劃分到同一類的比率下降，而且當(dāng)K=3時(shí)，樣本和其最遠(yuǎn)鄰樣本分別劃分到不同類中，此時(shí)聚類結(jié)果的最遠(yuǎn)得分值達(dá)到最大，因此，采用最遠(yuǎn)得分準(zhǔn)則所得到的最佳類別數(shù)為3。為了選擇出正確的類別數(shù)，評(píng)價(jià)指標(biāo)應(yīng)該綜合考慮最近得分和最遠(yuǎn)得分這兩個(gè)因素?；谝陨系睦碚摚贜FS評(píng)價(jià)指標(biāo)中每個(gè)樣本的得分設(shè)計(jì)為最近得分和最遠(yuǎn)得分的均值。

(a)K=2

(b)K=3

(c)K=4圖1 不同聚類數(shù)下的聚類Fig.1 Clustering under different cluster number

NFS指標(biāo)值衡量的是樣本對(duì)聚類結(jié)果的滿意度，NFS指標(biāo)值越大聚類結(jié)果就越好。因此，依據(jù)NFS選取最佳類別數(shù)的公式為

3 基于NFS的自動(dòng)聚類算法

3.1ACNFS算法

基于NFS的自動(dòng)聚類算法(automatic clustering algorithm based on the NFS，ACNFS)主要包括3個(gè)主要步驟。第1步確定類別數(shù)的搜索范圍，第2步計(jì)算在不同類別數(shù)下的NFS評(píng)價(jià)指標(biāo)值，第3步是根據(jù)評(píng)價(jià)指標(biāo)得到使聚類結(jié)果達(dá)到最好的類別數(shù)。該算法具體步驟如下。

① 利用K-means[20]算法對(duì)數(shù)據(jù)集進(jìn)行聚類；

②根據(jù)式(4)～(8)計(jì)算聚類結(jié)果的NFS指標(biāo)值;

③根據(jù)式(9)得到最佳聚類數(shù)Kopt。

ACNFS算法流程如圖2所示。

圖2 ACNFS算法流程圖Fig.2 The flow chart of ACNFS algorithm

3.2ACNFS時(shí)間復(fù)雜度分析

假定數(shù)據(jù)集有n個(gè)樣本，則ACNFS算法的時(shí)間復(fù)雜度分析如下。

2)算法第二步中使用K-means算法進(jìn)行聚類，其時(shí)間復(fù)雜度為O(nKl)，其中l(wèi)為迭代次數(shù)，K為類別數(shù)，且l?n，K?n。

為了獲得類別數(shù)，需要重復(fù)K-means和計(jì)算NFS指標(biāo)值Kmax-Kmin+1次，因此2)和3)的總的時(shí)間復(fù)雜度為O((n2+nkl)×(Kmax-Kmin+1))，且(Kmax-Kmin+1)?n。

4 實(shí)驗(yàn)

為了驗(yàn)證本文所提NFS指標(biāo)和ACNFS算法的有效性，我們進(jìn)行了仿真實(shí)驗(yàn)。在實(shí)驗(yàn)中我們將采用6個(gè)人工數(shù)據(jù)集和4個(gè)UCI真實(shí)數(shù)據(jù)，對(duì)CH指標(biāo)、BWP指標(biāo)、IGP指標(biāo)和NFS指標(biāo)確定類別數(shù)的性能進(jìn)行比較。實(shí)驗(yàn)證明，基于NFS指標(biāo)所提出的ACNFS算法可以有效地確定數(shù)據(jù)集的類別數(shù)，實(shí)現(xiàn)類別中心和類別數(shù)的自動(dòng)估計(jì)。

在仿真實(shí)驗(yàn)中，我們所采用的人工數(shù)據(jù)集如圖3所示，而真實(shí)數(shù)據(jù)集則為UCI數(shù)據(jù)庫(kù)中的IRIS，Balance Scale，Wine以及Soybean-small數(shù)據(jù)集。為了方便，我們將上述所有數(shù)據(jù)集的特征總結(jié)到表1中，其中n表示數(shù)據(jù)集中樣本點(diǎn)的個(gè)數(shù)，K表示數(shù)據(jù)集中樣本點(diǎn)的類別數(shù)，d表示數(shù)據(jù)集中樣本點(diǎn)的特征維數(shù)，最后一列表示各類別中樣本點(diǎn)的個(gè)數(shù)。

(a)Dataset 1

(b)Dataset 2

(c)Dataset 3

(d)Dataset 4

(e)Dataset 5

(f)Dataset 6圖3 人工數(shù)據(jù)集Fig.3 Artificial dataset

Table 1 The characters of the ten data sets used in our experiments

數(shù)據(jù)集nKd每類中樣本點(diǎn)的個(gè)數(shù)Dataset180022400,400Dataset280032400,200,200Dataset380032400,200,200Dataset4110042200,400,200Dataset5100052400,200,200,300Dataset690062200,200,200,200,200Iris15034150,150,150,150,150,150BalanceScale6303450,50,50Wine17831354,288,288Soybean-small4743559,71,48

首先，分別采用CH指標(biāo)、BWP指標(biāo)、IGP指標(biāo)和NFS指標(biāo)估計(jì)人工數(shù)據(jù)集Dataset 1～Dataset 6的類別數(shù)，實(shí)驗(yàn)結(jié)果如表2～7所示。

表2中給出了對(duì)數(shù)據(jù)集Dataset 1采用不同評(píng)價(jià)指標(biāo)得到的類別數(shù)和各類別數(shù)出現(xiàn)的百分比。第2列到第8列的數(shù)據(jù)是百分?jǐn)?shù)值，而百分?jǐn)?shù)值代表算法在運(yùn)行N次，得到相應(yīng)的類別數(shù)的次數(shù)與N的比值。實(shí)驗(yàn)中取N=20。表2中的最后1列表示通過(guò)投票準(zhǔn)則獲得的數(shù)據(jù)集的類別數(shù)。從表2可以看出，對(duì)人工數(shù)據(jù)集Dataset 1采用這4種評(píng)價(jià)指標(biāo)均能得到正確的類別數(shù)，而且評(píng)價(jià)結(jié)果穩(wěn)定，每次都能得到正確類別數(shù)。

表2 Dataset 1的類別數(shù)

表3給出了對(duì)數(shù)據(jù)集Dataset 2采用不同評(píng)價(jià)指標(biāo)得到的類別數(shù)和各類別數(shù)出現(xiàn)的百分比。從Dataset 2的散點(diǎn)分布圖中可以看出，有兩類數(shù)據(jù)無(wú)法完全分離。因此，只有采用NFS指標(biāo)得到的類別數(shù)是正確的類別數(shù)，而且評(píng)價(jià)結(jié)果穩(wěn)定，每次都能得到正確的類別數(shù)；而采用其他的評(píng)價(jià)指標(biāo)卻無(wú)法得到正確的類別數(shù)。

表3 Dataset 2的類別數(shù)

表4給出了對(duì)數(shù)據(jù)集Dataset 3采用不同評(píng)價(jià)指標(biāo)得到的類別數(shù)和各類別數(shù)出現(xiàn)的百分比。由于在數(shù)據(jù)集Dataset 3中，不同類之間是完全可分的，因此采用這4個(gè)評(píng)價(jià)指標(biāo)，均可以得到正確的類別數(shù)，而且評(píng)價(jià)結(jié)果穩(wěn)定。

表4 Dataset 3的類別數(shù)

表5給出了對(duì)數(shù)據(jù)集Dataset 4采用不同評(píng)價(jià)指標(biāo)得到的類別數(shù)和各類別數(shù)出現(xiàn)的百分比。采用NFS指標(biāo)、CH指標(biāo)和BWP指標(biāo)均可以得到正確的類別數(shù)，而采用IGP指標(biāo)卻無(wú)法得到正確的類別數(shù)。從具體情況分析，NFS指標(biāo)和CH指標(biāo)性能較好，評(píng)價(jià)結(jié)果穩(wěn)定，每次都可以得到正確的類別數(shù)；而B(niǎo)WP指標(biāo)差一點(diǎn)，正確率只有71.3%。

表5 Dataset 4的類別數(shù)

表6給出了對(duì)數(shù)據(jù)集Dataset 5采用不同評(píng)價(jià)指標(biāo)得到的類別數(shù)和各類別數(shù)出現(xiàn)的百分比。采用NFS指標(biāo)、CH指標(biāo)和BWP指標(biāo)均可以得到正確的類別數(shù)，而采用IGP指標(biāo)卻無(wú)法得到正確的類別數(shù)。

表6 Dataset 5的類別數(shù)

表7給出了對(duì)數(shù)據(jù)集Dataset 6采用不同評(píng)價(jià)指標(biāo)得到的類別數(shù)和各類別數(shù)出現(xiàn)的百分比。采用四種評(píng)價(jià)指標(biāo)均能得到該數(shù)據(jù)集的正確類別數(shù)。其中NFS指標(biāo)、BWP指標(biāo)和CH指標(biāo)的性能較好，評(píng)價(jià)結(jié)果穩(wěn)定；而IGP指標(biāo)性能差一點(diǎn)，正確率為90%。

表7 Dataset 6的類別數(shù)

由表2～7所示的實(shí)驗(yàn)結(jié)果可如，對(duì)于可分性較好的人工數(shù)據(jù)集，CH指標(biāo)、BWP指標(biāo)和NFS指標(biāo)均能獲得正確的類別數(shù)。下面將采用UCI中的真實(shí)數(shù)據(jù)集IRIS、Balance Scale、Wine以及Soybean-small來(lái)驗(yàn)證CH指標(biāo)、BWP指標(biāo)、IGP指標(biāo)和NFS指標(biāo)在確定類別數(shù)時(shí)的性能。

表8給出了數(shù)據(jù)集Wine在采用不同評(píng)價(jià)指標(biāo)時(shí)，在不同的類別數(shù)下的指標(biāo)值，其中帶下劃線的數(shù)據(jù)是該指標(biāo)下的最大值。NFS指標(biāo)和BWP指標(biāo)在類別數(shù)K=3時(shí)取最大值，而其他指標(biāo)在類別數(shù)K=2時(shí)取最大值，但是由于數(shù)據(jù)集Wine的真實(shí)類別數(shù)為3，因此采用NFS指標(biāo)和BWP指標(biāo)可以得到正確的類別數(shù)，而采用其他評(píng)價(jià)指標(biāo)則無(wú)法得到正確的類別數(shù)。

表8 Wine的指標(biāo)值

表9給出了4組真實(shí)數(shù)據(jù)集分別在采用不同評(píng)價(jià)指標(biāo)下得到的類別數(shù)，這里依然是運(yùn)行多次實(shí)驗(yàn)通過(guò)投票準(zhǔn)則確定最終的類別數(shù)，括號(hào)中的數(shù)據(jù)表示類別數(shù)出現(xiàn)的百分比。參考表1中各數(shù)據(jù)集的真實(shí)類別數(shù)，可以得到如下結(jié)論：采用NFS指標(biāo)可以得到所有真實(shí)數(shù)據(jù)集的正確的類別數(shù)，其中對(duì)于Balance Scale和Wine數(shù)據(jù)集，評(píng)價(jià)結(jié)果穩(wěn)定，效果較好，而對(duì)于IRIS和Soybean-small數(shù)據(jù)集，評(píng)價(jià)結(jié)果差一點(diǎn)，只有60%和45%的正確率；然而采用BWP指標(biāo)只可以得到數(shù)據(jù)集Wine的正確類別數(shù)，而且評(píng)價(jià)結(jié)果穩(wěn)定；但是采用CH指標(biāo)和IGP指標(biāo)則無(wú)法得到數(shù)據(jù)集的正確類別數(shù)。

表9 真實(shí)數(shù)據(jù)集的類別數(shù)

5 結(jié)束語(yǔ)

眾所周知，很多聚類算法需要根據(jù)先驗(yàn)知識(shí)給出算法所需要的類別數(shù)。但是，在很多實(shí)際應(yīng)用中很難獲得有效的先驗(yàn)知識(shí)，因此確定聚類問(wèn)題的類別數(shù)成為了一個(gè)研究的熱點(diǎn)。本文首先基于最近鄰一致性和最遠(yuǎn)鄰相異性的原則，提出了一種最近最遠(yuǎn)得分評(píng)價(jià)指標(biāo)(NFS)，并在此基礎(chǔ)上提出了一種基于NFS自動(dòng)聚類算法，實(shí)現(xiàn)了對(duì)類別數(shù)和類別中心的自動(dòng)估計(jì)。與已經(jīng)提出的評(píng)價(jià)指標(biāo)相比，NFS指標(biāo)是基于數(shù)據(jù)集統(tǒng)計(jì)信息的指標(biāo)，而且NFS指標(biāo)考慮了最近樣本和最遠(yuǎn)樣本兩個(gè)方面，通過(guò)評(píng)分機(jī)制還保證了每個(gè)樣本都對(duì)評(píng)價(jià)指標(biāo)產(chǎn)生影響。從而使NFS指標(biāo)在IRIS等數(shù)據(jù)集中呈現(xiàn)較好的結(jié)果。但是NFS指標(biāo)并不是最完美的，因此還需要繼續(xù)進(jìn)行相關(guān)研究。

[1]劉戀, 常冬霞, 鄧勇. 動(dòng)態(tài)小生境人工魚(yú)群算法的圖像分割[J]. 智能系統(tǒng)學(xué)報(bào), 2015, 10(5): 669-674. LIU Lian, CHANG Dongxia, DENG Yong. An image segmentation method based on dynamic niche artificial fish-swarm algorithm[J]. CAAI transactions on intelligent systems, 2015, 10(5): 669-674.

[2]NIKOLAOU T G, KOLOKOTSA D S, STAVRAKAKIS G S, et al. On the application of clustering techniques for office buildings’ energy and thermal comfort classification[J]. IEEE transactions on smart grid, 2012, 3(4): 2196-2210.

[3]CHANG Hong, YEUNG D Y. Robust path-based spectral clustering with application to image segmentation[C]//Proceedings of the Tenth IEEE International Conference on Computer Vision. Beijing, China, 2005, 1: 278-285.

[4]SHI Jianbo, MALIK J. Normalized cuts and image segmentation[J]. IEEE transactions on pattern analysis and machine intelligence, 2000, 22(8): 888-905.

[5]XIE X L, BENI G. A validity measure for Fuzzy clustering[J]. IEEE transactions on pattern analysis and machine intelligence, 1991, 13(8): 841-847.

[6]PAL N R, BEZDEK J C. On cluster validity for the fuzzy c-means model[J]. IEEE transactions on fuzzy systems, 1995, 3(3): 370-379.

[7]鄭宏亮, 徐本強(qiáng), 趙曉慧, 等. 新的模糊聚類有效性指標(biāo)[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(8): 2166-2169. ZHENG Hongliang, XU Benqiang, ZHAO Xiaohui, et al. Novel validity index for fuzzy clustering[J]. Journal of computer applications, 2014, 34(8): 2166-2169.

[8]岳士弘, 黃媞, 王鵬龍. 基于矩陣特征值分析的模糊聚類有效性指標(biāo)[J]. 天津大學(xué)學(xué)報(bào): 自然科學(xué)與工程技術(shù)版, 2014, 47(8): 689-696. YUE Shihong, HUANG Ti, WANG Penglong. Matrix eigenvalue analysis-based clustering validity index[J]. Journal of Tianjin university: science and technology, 2014, 47(8): 689-696.

[9]卿銘, 孫曉梅. 一種新的聚類有效性函數(shù): 模糊劃分的模糊熵[J]. 智能系統(tǒng)學(xué)報(bào), 2015, 10(1): 75-80. QING Mei, SUN Xiaomei. A new clustering effectiveness function: fuzzy entropy of fuzzy partition[J]. CAAI transactions on intelligent systems, 2015, 10(1): 75-80.

[10]王開(kāi)軍, 李健, 張軍英, 等. 聚類分析中類數(shù)估計(jì)方法的實(shí)驗(yàn)比較[J]. 計(jì)算機(jī)工程, 2008, 34(9): 198-199, 202. WANG Kaijun, LI Jian, ZHANG Junying, et al. Experimental comparison of clusters number estimation for cluster analysis[J]. Computer engineering, 2008, 34(9): 198-199, 202.

[11]王勇, 唐靖, 饒勤菲, 等. 高效率的K-means最佳聚類數(shù)確定算法[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(5): 1331-1335. WANG Yong, TANG Jing, RAO Qinfei, et al. High efficient K-means algorithm for determining optimal number of clusters[J]. Journal of computer applications, 2014, 34(5): 1331-1335.

[13]DAVIES D L, BOULDIN D W. A cluster separation measure[J]. IEEE transactions on pattern analysis and machine intelligence, 1979, PAMI-1(2): 224-227.

[15]KRZANOWSKI W J, LAI Y T. A criterion for determining the number of groups in a data set using sum-of-squares clustering[J]. Biometrics, 1988, 44(1): 23-34.

[16]周世兵, 徐振源, 唐旭清. K-means算法最佳聚類數(shù)確定方法[J]. 計(jì)算機(jī)應(yīng)用, 2010, 30(8): 1995-1998.

ZHOU Shibing, XU Zhenyuan, TANG Xuqing. Method for determining optimal number of clusters in K-means clustering algorithm[J]. Journal of computer applications, 2010, 30(8): 1995-1998.

[17]KAPP A V, TIBSHIRANI R. Are clusters found in one dataset present in another dataset[J]. Biostatistics, 2007, 8(1): 9-31.

[18]周世兵. 聚類分析中的最佳聚類數(shù)確定方法研究及應(yīng)用[D]. 無(wú)錫: 江南大學(xué), 2011. ZHOU Shibing. Research and application on determining optimal number of cluster in cluster analysis[D]. Wuxi: Jiangnan University, 2011.

[19]Gower J C, Ross G J S. Minimum spanning trees and single linkage cluster analysis[J]. Journal of the royal statistical society, 1969, 18(1):54-64.

[20]MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, USA, 1967: 281-297.

A clustering evaluation index based on the nearest and furthest score

FENG Liuwei1,2,3，CHANG Dongxia1,2,3， DENG Yong4， ZHAO Yao1,2,3

(1. Institute of Information Science, Beijing Jiaotong University Beijing 100044, China; 2. School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China; 3. Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)

The clustering algorithm is one of the widely-used methods in data analysis. However, the number of clusters is essential to determine the performance of the clustering algorithm. At present, the number of clusters usually need to be specified in advance. In most cases, it is difficult to obtain the valid cluster number according to a priori knowledge of the dataset. To obtain the number of clusters automatically, a Nearest and Furthest Score (NFS) index was proposed based on the principles of the nearest neighbor consistency and the furthest neighbor difference. Moreover, an Automatic Clustering NFS (ACNFS) algorithm was also proposed, which can determine the number of clusters automatically. The experimental results prove the index is reasonable and practicable to determine the cluster number.

the nearest neighbor consistency; the furthest neighbor difference; K-means clustering algorithm; scoring mechanism; evaluation index; hierarchical clustering

馮柳偉，女，1992年生，碩士研究生，研究方向?yàn)榫垲愃惴ā?/p>

常冬霞，女，1977年生，副教授，碩士生導(dǎo)師，主要研究方向?yàn)檫M(jìn)化計(jì)算、非監(jiān)督分類算法、圖像分割以及圖像分類。發(fā)表學(xué)術(shù)論文10余篇，其中SCI檢索5篇，EI 檢索2篇。

鄧勇，男，1974年生，副研究員，博士，主要研究方向?yàn)橹悄苄畔⑻幚怼?shù)據(jù)庫(kù)系統(tǒng)技術(shù)及應(yīng)用等。 主持和參與國(guó)家“863”計(jì)劃1項(xiàng)，北京市自然科學(xué)基金項(xiàng)目1項(xiàng)。發(fā)表學(xué)術(shù)論文20余篇，其中收錄10余篇。

10.11992/tis.201611007

http://kns.cnki.net/kcms/detail/23.1538.TP.20170227.2211.022.html

2016-11-07.

日期：2017-02-27.

國(guó)家自然科學(xué)基金“重點(diǎn)”項(xiàng)目(61532005).

常冬霞. E-mail：dxchang@bjtu.edu.cn.

TP391

A

1673-4785(2017)01-0067-08

馮柳偉，常冬霞，鄧勇,等.最近最遠(yuǎn)得分的聚類性能評(píng)價(jià)指標(biāo)[J]. 智能系統(tǒng)學(xué)報(bào)， 2017, 12(1): 67-74.

英文引用格式：FENG Liuwei， CHANG Dongxia， DENG Yong，et al. A clustering evaluation index based on the nearest and furthest score [J]. CAAI Transactions on Intelligent Systems, 2017, 12(1): 67-74.