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

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

最近最遠得分的聚類性能評價指標

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

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

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

最近鄰一致性；最遠鄰相異性；K-means聚類算法；評分機制；評價指標；層次聚類

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

1 已有評價指標

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

1.1 Calinski-Harabasz(CH)指標

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

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

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

1.2 BWP指標

BWP指標是周世兵等人提出的一種基于樣本的幾何結構設計的確定聚類類別數(shù)的評價指標[16]，該指標利用聚類結果的類內緊密性和類間分離性來衡量聚類結果。指標的最大值對應的類數(shù)作為聚類數(shù)。該指標的判斷函數(shù)為

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

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

BWP指標值越大則表示聚類結果的類內越緊密而類間越遠離，聚類結果性能越好。但是該評價指標不適合非完全分離的數(shù)據(jù)集。

1.3 IGP指標

IGP指標是Kapp提出的評價指標[17]。此指標的設計思想是：當對新的樣本進行分類時，新樣本應該被劃分到與其最相似的樣本所在類別。因此該指標使用樣本與其最近鄰樣本劃分到同一類的比例來衡量聚類結果的質量。該指標的評價函數(shù)為

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

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

2 最近最遠得分評價指標

為了能準確地得到聚類問題的類別數(shù)，本文在基于最近鄰一致性和最遠鄰相異性的原則上，提出了最近最遠得分(nearest and furthest score，NFS)評價指標。

2.1 相關概念定義

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

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

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

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

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

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

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

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

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

2.2 NFS指標的分析

NFS指標的設計原則是每個樣本應該和距離其最近的樣本劃分到同一類別中，而與距離其最遠的樣本劃分到不同類別中。因此，每個樣本擁有兩個影響評分的因子，分別是最近得分因子和最遠得分因子。對于最近得分因子，如果某個樣本與距離其最近的樣本劃分到同一類中，則得1分，表示對此聚類結果的支持，而如果劃分到不同類中，則得-1分，表示對此聚類結果的反對。最遠得分因子的規(guī)定也是如此。

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

(a)K=2

(b)K=3

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

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

3 基于NFS的自動聚類算法

3.1ACNFS算法

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

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

②根據(jù)式(4)～(8)計算聚類結果的NFS指標值;

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

ACNFS算法流程如圖2所示。

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

3.2ACNFS時間復雜度分析

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

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

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

4 實驗

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

在仿真實驗中，我們所采用的人工數(shù)據(jù)集如圖3所示，而真實數(shù)據(jù)集則為UCI數(shù)據(jù)庫中的IRIS，Balance Scale，Wine以及Soybean-small數(shù)據(jù)集。為了方便，我們將上述所有數(shù)據(jù)集的特征總結到表1中，其中n表示數(shù)據(jù)集中樣本點的個數(shù)，K表示數(shù)據(jù)集中樣本點的類別數(shù)，d表示數(shù)據(jù)集中樣本點的特征維數(shù)，最后一列表示各類別中樣本點的個數(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每類中樣本點的個數(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指標、BWP指標、IGP指標和NFS指標估計人工數(shù)據(jù)集Dataset 1～Dataset 6的類別數(shù)，實驗結果如表2～7所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表8 Wine的指標值

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

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

5 結束語

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

[1]劉戀, 常冬霞, 鄧勇. 動態(tài)小生境人工魚群算法的圖像分割[J]. 智能系統(tǒng)學報, 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]鄭宏亮, 徐本強, 趙曉慧, 等. 新的模糊聚類有效性指標[J]. 計算機應用, 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]岳士弘, 黃媞, 王鵬龍. 基于矩陣特征值分析的模糊聚類有效性指標[J]. 天津大學學報: 自然科學與工程技術版, 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)學報, 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]王開軍, 李健, 張軍英, 等. 聚類分析中類數(shù)估計方法的實驗比較[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]. 計算機應用, 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]. 計算機應用, 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ù)確定方法研究及應用[D]. 無錫: 江南大學, 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年生，碩士研究生，研究方向為聚類算法。

常冬霞，女，1977年生，副教授，碩士生導師，主要研究方向為進化計算、非監(jiān)督分類算法、圖像分割以及圖像分類。發(fā)表學術論文10余篇，其中SCI檢索5篇，EI 檢索2篇。

鄧勇，男，1974年生，副研究員，博士，主要研究方向為智能信息處理、數(shù)據(jù)庫系統(tǒng)技術及應用等。 主持和參與國家“863”計劃1項，北京市自然科學基金項目1項。發(fā)表學術論文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.

國家自然科學基金“重點”項目(61532005).

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

TP391

A

1673-4785(2017)01-0067-08

馮柳偉，常冬霞，鄧勇,等.最近最遠得分的聚類性能評價指標[J]. 智能系統(tǒng)學報， 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.