謝娟英，周 穎

（陜西師范大學計算機科學學院，陜西西安710119）

一種新聚類評價指標

謝娟英＊，周 穎

（陜西師范大學計算機科學學院，陜西西安710119）

用于發(fā)現(xiàn)數(shù)據(jù)集類簇數(shù)k的常用內(nèi)部評價指標DB（Davies Bouldin）和BWP（Between－within Proportion）等需要先確定一個搜索范圍kmax，使數(shù)據(jù)集的類簇數(shù)滿足k≤kmax，但如何確定kmax尚無理論指導。針對這一問題，提出一個新F統(tǒng)計量Fr，將Fr作為新聚類有效性準則，以判斷聚類算法收斂與否，自適應地確定數(shù)據(jù)集類簇數(shù)；將Fr應用于快速K－medoids算法的收斂性判斷，并以基于最小生成樹的測地距離，即樣本對在最小生成樹上的路徑長度，代替其間的直接歐氏距離度量樣本相似性，得到一種自適應的快速K－medoids聚類算法，解決了K－medoids算法需要人為給定類簇數(shù)和不能發(fā)現(xiàn)任意形狀簇的問題。UCI機器學習數(shù)據(jù)庫數(shù)據(jù)集和人工模擬數(shù)據(jù)集實驗測試表明，本文提出的Fr指標是一種有效的聚類算法評價指標，基于該指標和測地距離的K－medoids算法不僅能發(fā)現(xiàn)任意形狀的簇，還可以自適應地確定數(shù)據(jù)集的類簇數(shù)，且對噪音數(shù)據(jù)有很好的魯棒性。

F統(tǒng)計量；內(nèi)部評價指標；類簇數(shù)；K－medoids聚類算法；最小生成樹

聚類評價指標是聚類效果好壞的常用評價方法，通常包括內(nèi)部有效性評價指標和外部有效性評價指標。內(nèi)部評價指標常被用來確定數(shù)據(jù)集類簇數(shù)［1－3］，常用的內(nèi)部評價指標包括：DB（Davies－Bouldin）［4］，BWP（Between－within Proportion）［3，56］，SIL（Silhouette）［7］，IGP（In－Group Proportion）［8］等。這些指標用于發(fā)現(xiàn)數(shù)據(jù)集類簇k時，需要先確定一個搜索范圍，即設定一個kmax，數(shù)據(jù)集的類簇數(shù)k滿足k≤kmax，如何確定kmax目前尚無理論指導［6］。模糊聚類分析中，F(xiàn)統(tǒng)計量常作為內(nèi)部指標［9－11］來度量聚類結(jié)果是否滿足了“簇內(nèi)緊密，簇間分離”的特征，但F統(tǒng)計量不能用來發(fā)現(xiàn)數(shù)據(jù)集的合理類簇數(shù)。

K－medoids算法是一種經(jīng)典的基于劃分的聚類分析方法，其代表是PAM（Partitioning Around Medoids）算法［12－13］。PAM算法時間復雜度較高，適用于規(guī)模較小的聚類問題?？焖貹－medoids聚類算法［14］從初始類簇中心選擇與迭代過程更迭方法兩方面改進PAM算法，取得了很好的聚類效果。但是，快速K－medoids算法同傳統(tǒng)K－medoids算法一樣需要事先給定類簇數(shù)k，且不能發(fā)現(xiàn)任意形狀的簇［12，15－18］，聚類結(jié)果依賴初始聚類中心［15］。

最小生成樹（Minimum Spanning Tree，MST）聚類算法根據(jù)樣本間距離建立最小生成樹，通過剪斷最小生成樹的k－1條邊，得到k個類簇，能識別任意形狀類簇，但MST聚類算法對噪音敏感［16－19］。

針對F統(tǒng)計量不能準確識別數(shù)據(jù)集類簇數(shù)問題，提出改進的F統(tǒng)計量Fr作為聚類準則函數(shù)；以Fr為聚類準則函數(shù)，以樣本對在最小生成樹MST上的測地距離［20］代替樣本對間的歐氏距離，提出一種自適應的快速K－medoids算法（MST＿K－medoids），解決了常用內(nèi)部指標用于發(fā)現(xiàn)數(shù)據(jù)集類簇數(shù)時，需要設定搜索范圍，以及經(jīng)典K－medoids算法需要事先給定類簇數(shù)和不能識別任意形狀簇的問題。使用Fr指標的MST＿K－medoids算法在文中被稱為MST＿Fr算法。UCI數(shù)據(jù)集和經(jīng)典人工模擬數(shù)據(jù)集的實驗測試結(jié)果表明，MST＿Fr算法不僅能夠發(fā)現(xiàn)任意形狀的簇，且能夠自動識別數(shù)據(jù)集類簇數(shù)，并對噪音數(shù)據(jù)具有良好的魯棒性。

1 相關理論及概念

1.1 最小生成樹

生成樹是一個無環(huán)子圖，包含了原圖全部n個頂點和連接這些頂點的n－1條邊。一個帶權圖的最小生成樹是具有最小邊權之和的生成樹［21］。

經(jīng)典最小生成樹算法包括普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法，分別適用于計算邊稠密圖和邊稀疏圖的最小生成樹。

1.2 快速K－medoids算法

快速K－medoids算法從初始聚類中心選擇、迭代過程類簇中心更新方法兩方面對PAM算法進行改進［14，21］，基本思想如下：

（1）計算數(shù)據(jù)集中每個樣本的密度，選擇前k個位于樣本分布密集區(qū)域的樣本為初始聚類中心，將其余樣本分配到距離最近的類簇中心，產(chǎn)生初始聚類結(jié)果；

（2）在每個類簇內(nèi)部找一個新中心，使該簇非中心樣本到中心樣本距離之和最小，得到k個新中心；

（3）以距離最近原則，重新分配所有非中心樣本到最近類簇中心，如果本次迭代所得聚類結(jié)果與前一次不同，則轉(zhuǎn)至（2）進行下一次迭代，否則算法停止。

1.3 新F統(tǒng)計量Fr

設數(shù)據(jù)集U＝｛x1，x2，…，xn｝，每個樣本xi有m維特征，即xi＝（xi1，xi2，…，xim），i＝1，2，…n。

定義1 任意兩個樣本間的歐氏距離定義為

定義2 數(shù)據(jù)集中每個數(shù)據(jù)對象xi的密度［22］Density（xi）定義為

定義3 F統(tǒng)計量［9］定義為

其中，nj為第j簇的樣本數(shù)，k為類簇數(shù)，ˉx（j）為第j簇的質(zhì)心，ˉx為數(shù)據(jù)集全部樣本的質(zhì)心，‖ˉx（j）－ˉx‖為ˉx（j）與ˉx間的距離，‖x（j）i－ˉx（j）‖為第j類簇的第i個樣本x（j）i與第j簇的質(zhì)心ˉx（j）的距離，稱（3）式為F統(tǒng)計量，它服從自由度為（k－1，n－k）的F分布。（3）式的分子表征類簇間的距離，分母表征類簇內(nèi)樣本與該簇質(zhì)心的距離，因此，F(xiàn)值越大，表明聚類效果越好。

分析（3）式可知，F(xiàn)統(tǒng)計量的局限性在于：當k偏?。ń咏?）或者偏大（接近于n）時，F(xiàn)統(tǒng)計量的值會出現(xiàn)極大、極小兩個極端值。該現(xiàn)象會導致以F統(tǒng)計量極大值確定的類簇數(shù)出現(xiàn)過小情況。為此，提出改進的F統(tǒng)計量Fr，定義如下：

Fr＝F·lg k。 （4）（4）式中，對F乘以因子lg k，用來調(diào)節(jié)當k值偏小時F值偏大的情況。通常類簇數(shù)k≥2，因此lg k＞0，故Fr的變化趨勢同F(xiàn)統(tǒng)計量相同，具有相同性質(zhì)，即Fr值越大，則聚類效果越好。圖1以UCI機器學習數(shù)據(jù)庫Iris數(shù)據(jù)集為例展示了F統(tǒng)計量曲線和Fr統(tǒng)計量曲線。從圖1可以看出Fr能用來識別Iris數(shù)據(jù)集的類簇數(shù)k＝3，此時Fr取得其最大值，與數(shù)據(jù)集的真實類簇數(shù)相同。

圖1 Iris數(shù)據(jù)集上F與Fr值的變化曲線Fig.1 The curve of Fand Fron Iris dataset

2 本文K－medoids算法

2.1 數(shù)據(jù)預處理

（1）數(shù)據(jù)標準化：為了避免不同量綱影響聚類結(jié)果，采用極差變換方法對數(shù)據(jù)集進行標準化［23］。

（2）計算樣本對距離矩陣distance：樣本數(shù)為n，則distance是一個對角線為0的n×n對稱矩陣。

（3）根據(jù)（2）式計算數(shù)據(jù)集中每個數(shù)據(jù)對象xi的密度值Density（xi），并依據(jù)Density（xi）值將樣本升序排序為U＝｛xs1，xs2，…，xsn｝；

（4）根據(jù)distance矩陣，運用Prim或Kruskal算法構造MST；

（5）計算樣本對在MST上的測地距離，得到距離矩陣path。

2.2 本文MST＿Fr算法

輸入：數(shù)據(jù)集U（n個樣本點，m維特征）及樣本對距離矩陣distance。

輸出：數(shù)據(jù)集U的k個類簇及max＿Fr值。算法步驟：

（1）初始化：令初始變量Fr（1）＝0，j＝2。

（2）選擇當前初始類簇中心，并初始化準則函數(shù)值Fr（j）：

a）令當前類簇中心集M＝?；

b）選擇U中前j個Density（xi）最小的樣本，即處于最密集區(qū)域的樣本xs1，xs2，…，xsj作為當前初始類簇中心，即令M＝M∪｛xs1，xs2，…，xsj｝，同時令U＝U－｛xs1，xs2，…，xsj｝；

c）令Fr（j）＝0。

（3）分配樣本，更新類簇中心，計算聚類準則函數(shù)Fr（j）：

a）根據(jù)測地距離矩陣path，分配樣本到最近簇中心，根據(jù)（3）—（4）式計算當前聚類準則函數(shù)Fr（j）值。若Fr（j）值增大，執(zhí)行下一步b）更新簇中心，否則轉(zhuǎn)（4）；

b）為每個類簇尋找一個新中心，使新中心到該簇其他樣本的測地距離長度之和最短，轉(zhuǎn)（3）繼續(xù)迭代；

（4）若Fr（j）＞Fr（j－1），則j＝j+1，轉(zhuǎn)（2）；若Fr（j）≤Fr（j－1），則算法停止，記max＿Fr＝Fr（j－1），k＝j－1，得到數(shù)據(jù)集類簇劃分和類簇數(shù)k。

2.3 算法時間復雜度

PAM算法的時間復雜度是O（k（n－k）2）；快速K－medoids算法的時間復雜度是O（nk）［3］。對比快速K－medoids算法和本文MST＿Fr算法，其主要差別在于本文MST＿Fr算法增加了外層根據(jù)新F統(tǒng)計量Fr確定數(shù)據(jù)集合理類簇數(shù)，因此，MST＿Fr算法的時間復雜度分析為O（nk2）。盡管生成MST的時間復雜度為O（n2）（Prim算法）或O（nlog n）（Kruskal算法），計算樣本對測地距離的時間復雜度為O（n3），但如同快速K－medoids算法將樣本間距離計算（時間復雜度為O（n2））放在所有循環(huán)之外，本文MST＿Fr算法將樣本間測地距離計算移至所有循環(huán)之外，測地距離只需要計算一次，以后的使用只需要調(diào)用即可，可以大大減少算法運行的時間消耗。

上述分析可見，快速K－medoids算法比PAM算法高效。MST＿Fr算法與快速K－medoids算法相比多了根據(jù)聚類準則函數(shù)Fr確定數(shù)據(jù)集類簇數(shù)的循環(huán)。

3 實驗結(jié)果與分析

實驗數(shù)據(jù)包括UCI機器學習數(shù)據(jù)庫［24］數(shù)據(jù)集和人工模擬數(shù)據(jù)集，其中人工模擬數(shù)據(jù)包括隨機生成的含噪音數(shù)據(jù)集以及經(jīng)典人工模擬數(shù)據(jù)集［25］。實驗環(huán)境為Intel（R）Core（TM）i5－2400CPU＠3.10GHz，4G內(nèi)存，Win7操作系統(tǒng)，Matlab R2012a應用軟件。

實驗比較了本文提出的MST＿Fr算法與現(xiàn)有的PAM算法、快速K－medoids算法以及將本文MST＿Fr算法的MST測地距離替換為樣本間直接歐氏距離的K－medoids算法（ED＿K－medoids算法）的聚類性能。

3.1 UCI數(shù)據(jù)集實驗

使用8個經(jīng)典UCI數(shù)據(jù)集對本文提出的聚類有效性評價準則Fr和基于MST測地距離的樣本相似性度量方法進行測試。所用8個經(jīng)典UCI數(shù)據(jù)集的描述如表1所示。

表1 UCI數(shù)據(jù)集描述Tab.1 The descriptions of UCI datasets

3.1.1 本文Fr指標性能的驗證性實驗 為了驗證本文提出的Fr準則的有效性，對表1所示8個UCI數(shù)據(jù)集分別采用聚類有效性指標DB、BWP、SIL、IGP、F、Fr來確定其最佳類簇數(shù)，聚類算法是MST＿K－medoids，實驗結(jié)果如表2所示。加粗字體和加下劃線表示相應指標確定類簇數(shù)與數(shù)據(jù)集真實類簇數(shù)一致。

表2 6種聚類有效性指標通過MST＿K－medoids算法在UCI數(shù)據(jù)集上確定的最佳類簇數(shù)Tab.2 The optimal number of clusters determined by six different criteria on UCI datasets via MST＿K－medoids

從表2實驗結(jié)果可知，SIL、DB和IGP指標分別在3／8個數(shù)據(jù)集上得到了正確類簇數(shù)，BWP和F指標分別在5／8、4／8個數(shù)據(jù)集上得到了正確類簇數(shù)，本文提出的聚類有效性新指標Fr在6／8個實驗數(shù)據(jù)集上得到了正確類簇數(shù)。

F與Fr指標確定最佳類簇數(shù)時的詳細變化如表3所示，其中F和Fr指標確定的最佳類簇數(shù)以下劃線形式標出，以加粗字體標出確定的最佳類簇數(shù)與真實類簇數(shù)一致。表中空白表示無相應值。

由表2、3可見，MST＿Fr算法對Iris、Wine、Seeds、Ionosphere、WDBC和CMC數(shù)據(jù)集發(fā)現(xiàn)的類簇數(shù)與各數(shù)據(jù)集真實類簇數(shù)一致，但對Haberman數(shù)據(jù)集確定的類簇數(shù)是3，而不是真實的類簇數(shù)2。對比Haberman數(shù)據(jù)集的真實數(shù)據(jù)分布得知，MST＿Fr算法是將Haberman的第一個類簇（乳腺癌病人術后生活5年或更長時間）分成了2個類簇，即生活5年和更長時間2個類簇。

Segmentation數(shù)據(jù)集有7個類簇，分別是墻面磚、天空、樹葉、水泥、窗戶、路徑和草。MST＿Fr算法對Segmentation數(shù)據(jù)集確定的最佳類簇數(shù)是5，而不是真實的類簇數(shù)7。對比該數(shù)據(jù)集樣本的真實分布得知，MST＿Fr算法是將Segmentation的第一類（墻面磚）的全部樣本和第五類（窗戶）的部分樣本劃分到一個類簇，第二類（天空）和第六類（路徑）的全部樣本與第四類（水泥）部分樣本劃分為一個類簇，第三類（樹葉）的部分樣本和第七類（草）的全部樣本劃分為一個類簇，而第四類（水泥）和第五類（窗戶）的部分樣本劃分到一個類簇，第五類（窗戶）的剩余樣本獨成一個類簇，一共形成了5個類簇。

以上實驗結(jié)果的詳細分析表明，F(xiàn)r指標比F指標更適于發(fā)現(xiàn)數(shù)據(jù)集的合理類簇數(shù)。

表3 MST＿K－medoids算法在UCI數(shù)據(jù)集上確定的最佳類簇數(shù)對應Fr以及F指標值Tab.3 The Frand Fof the optimal number of clusters on UCI datasets by MST＿K－medoids

3.1.2 本文新樣本相似性度量方法驗證 本小節(jié)將驗證本文提出的樣本間相似性度量方法的有效性，以說明采用樣本在最小生成樹MST上的測地距離度量樣本相似性，優(yōu)于采用樣本間直接歐氏距離度量樣本相似性。實驗比較了PAM算法、快速K－medoids算法（圖中用Fast表示）、ED＿K－medoids算法（圖中表示為ED）、MST＿Fr算法在表1所示8個UCI數(shù)據(jù)集的聚類準確率。4種K－medoids算法的聚類準確率如圖2所示。

圖2 4種K－medoids算法的聚類準確率曲線Fig.2 The clustering accuracy of four K－medoids algorithms

由圖2可見，MST＿Fr算法除了在Seeds數(shù)據(jù)集的聚類準確率略低于快速K－medoids算法外，在其他7個數(shù)據(jù)集均具有最高的聚類準確率，且顯著高于其他三種K－medoids算法?？焖貹－medoids算法的聚類準確率高于PAM算法。ED＿K－Medoids算法在Seeds、Segmentation、WDBC三個數(shù)據(jù)集的聚類準確率不如其他三個K－medoids算法，在其余五個UCI數(shù)據(jù)集的聚類準確率介于快速K－medoids和MST＿Fr算法之間。

以上4種K－medoids算法聚類準確率分析揭示，本文提出的采用樣本在MST的測地距離度量樣本相似性是一種非常有效的樣本相似性度量方法。

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

采用隨機生成的帶噪音人工模擬數(shù)據(jù)集和測試聚類算法的經(jīng)典人工模擬數(shù)據(jù)集來驗證本文MST＿Fr算法對噪音的魯棒性和其發(fā)現(xiàn)任意形狀類簇的能力。

3.2.1 本文MST＿Fr算法魯棒性驗證實驗 采用4個人工模擬數(shù)據(jù)集M1，M2，M3和M4來測試本文MST＿Fr算法的魯棒性。這4個人工模擬數(shù)據(jù)集的生成參數(shù)如表4所示。每個數(shù)據(jù)集包含3個類簇，每一類簇的樣本數(shù)分別為50、50、200、200，因此4個數(shù)據(jù)集的規(guī)模分別為150、150、600、600。其中M2的第3個類簇帶有3個噪音點，M4的第3個類簇帶有30個噪音點。

隨機生成50組滿足表4生成參數(shù)的4個人工模擬數(shù)據(jù)集，在每一組的4個數(shù)據(jù)集上分別運行本文提出的MST＿Fr算法，采用統(tǒng)計方法確定數(shù)據(jù)集的最終類簇數(shù)，實驗結(jié)果如表5所示。

表4 人工模擬數(shù)據(jù)集生成參數(shù)Tab.4 The generated parameters of synthetic datasets

表5 本文MST＿Fr算法確定的人工模擬數(shù)據(jù)集的類簇數(shù)Tab.5 The number of clusters of synthetic datasets determined by MST＿Fr

由表5所示的50組數(shù)據(jù)的統(tǒng)計實驗結(jié)果可以看出，MST＿Fr算法發(fā)現(xiàn)的數(shù)據(jù)集類簇數(shù)與其真實類簇數(shù)一致，且在規(guī)模較大數(shù)據(jù)集的實驗結(jié)果很好；含噪音數(shù)據(jù)集M2和M4的實驗結(jié)果揭示，本文MST＿Fr算法對噪音具有很好的魯棒性。

3.2.2 本文MST＿Fr算法對任意形狀類簇識別能力驗證實驗 為了驗證本文MST＿Fr算法可以發(fā)現(xiàn)任意形狀的類簇，本小節(jié)分別在3個經(jīng)典人工模擬數(shù)據(jù)集Flame、Pathbased1、Spiral［25］上運行PAM、快速K－medoids、ED＿K－medoids和MST＿Fr算法，其中PAM算法和快速K－medoids算法需要事先給定類簇數(shù)k，后兩種K－medoids算法自動確定類簇數(shù)。3個經(jīng)典人工模擬數(shù)據(jù)集的原始分布如圖3所示。對該3個經(jīng)典人工模擬數(shù)據(jù)集，使用4種K－medoids算法的聚類結(jié)果分別如圖4—6所示，對應的聚類準確率如表6所示。

圖3 3個人工數(shù)據(jù)集的原始分布圖Fig.3 The original pattern of three synthetic datasets

圖4 4種K－medoids聚類算法對Flame數(shù)據(jù)集的聚類結(jié)果Fig.4 The clusterings of four K－medoids algorithms on Flame dataset

由圖4實驗結(jié)果可見，前3種K－medoids算法可以識別球狀類簇，但不能識別非球狀簇。原因是：前3種K－medoids算法的樣本相似性度量均采用歐氏距離度量，因此導致其不能識別Flame數(shù)據(jù)集的月牙形簇。本文MST＿Fr算法以樣本在MST的測地距離代替樣本間的直接歐氏距離度量樣本相似性，從而正確識別了Flame數(shù)據(jù)集的類簇分布。

圖5所示4種K－medoids算法在Pathbased1數(shù)據(jù)集的實驗結(jié)果揭示：本文提出的MST＿Fr算法可以識別Pathbased1數(shù)據(jù)集的類簇分布，其他3個 K－medoids算法均不能正確識別該數(shù)據(jù)集的類簇分布。但是ED＿K－medoids算法可以識別出Pathbased1數(shù)據(jù)集的類簇數(shù)是3。這也進一步說明了本文提出的改進F統(tǒng)計量Fr，是非常有效的聚類有效性評價準則，能用來確定數(shù)據(jù)集的類簇數(shù)。

圖6實驗結(jié)果顯示，對于完全帶狀分布的數(shù)據(jù)集，前3種K－medoids算法完全不能識別該數(shù)據(jù)集的類簇分布，且ED＿K＿medoids將Spiral數(shù)據(jù)集的類簇數(shù)識別為7個。本文提出的MST＿Fr算法可以發(fā)現(xiàn)帶狀分布，但錯將內(nèi)部兩個類簇識別為同一個類簇。因此，本文提出的基于MST測地距離和新聚類準則Fr的K－medoids算法（即MST＿Fr算 法）還有進一步改進和提升的空間。

圖5 4種聚類算法對Pathbased1數(shù)據(jù)集的聚類結(jié)果Fig.5 The clusterings of four K－medoids algorithms on Pathbased1 dataset

圖6 4種聚類算法在Spiral數(shù)據(jù)集上的實驗結(jié)果Fig.6 The clusterings of four K－medoids algorithms on Spiral dataset

表6聚類準確率比較揭示：對Flame數(shù)據(jù)集本文MST＿Fr算法的聚類準確率為100%，快速K－medoids和PAM算法的聚類準確率相同，均為83.75%，ED＿K－medoids的聚類準確率最差，只有63.75%。對Pathbased1數(shù)據(jù)集，本文MST＿Fr算法的聚類準確率達到96.33%，是4種K－medoids算法中最高的，ED＿K－medoids在該數(shù)據(jù)的聚類準確率排第二，PAM算法的效果最差。對Spiral數(shù)據(jù)集，盡管本文MST＿Fr算法沒有完全正確地識別出該數(shù)據(jù)集的每個類簇，但其聚類準確率依然是4種K－medoids算法中最高的，其他3種K－medoids算法的聚類準確率遠不如本文MST＿Fr算法，其中ED＿K－medoids算法最差，PAM算法排第二，這也說明本文采用MST上的測地距離度量樣本相似性是非常有效的。

表6 4種K－medoids算法對經(jīng)典人工數(shù)據(jù)集的聚類準確率Tab.6 The clustering accuracy on 3 popular synthetic datasets by 4 algorithms %

由表6聚類準確率比較明顯可見：本文MST＿Fr算法在這3個經(jīng)典的帶有一定難度的人工模擬數(shù)據(jù)集的聚類效果最好，且遠優(yōu)于其他3種K－me－doids算法的性能。

以上經(jīng)典人工模擬數(shù)據(jù)集的實驗分析表明，使用歐氏距離度量樣本相似度容易受噪聲影響，且只能識別球狀類簇。本文MST＿Fr算法可以識別任意形狀的簇，抗干擾性能好，且聚類準確率高。

4 結(jié) 論

針對常用聚類有效性判斷內(nèi)部指標用于識別數(shù)據(jù)集類簇數(shù)時，需要給定搜索范圍上限kmax問題，提出了改進的F統(tǒng)計量Fr，將Fr作為聚類有效性指標，自動發(fā)現(xiàn)數(shù)據(jù)集類簇數(shù)；并用樣本對在MST的測地距離代替其間歐氏距離度量樣本相似性，以Fr作為聚類準則函數(shù)，提出了一種新穎的快速K－medoids聚類算法——MST＿Fr。

UCI數(shù)據(jù)集和人工模擬數(shù)據(jù)集實驗測試表明，本文提出的新F統(tǒng)計量Fr是一種非常有效的聚類有效性度量指標；提出的采用MST上的測地距離度量樣本相似性是一種非常有效的樣本相似性度量方法；提出的MST＿Fr算法對噪音數(shù)據(jù)有很好魯棒性，能夠自適應地發(fā)現(xiàn)數(shù)據(jù)集類簇數(shù)，且能發(fā)現(xiàn)任意形狀的簇，有效解決了現(xiàn)有聚類有效性內(nèi)部評價指標在確定數(shù)據(jù)集類簇數(shù)時的問題，以及現(xiàn)存快速K－medoids聚類算法需要人為給定類簇數(shù)和不能識別任意形狀簇的問題。但是，經(jīng)典人工模擬數(shù)據(jù)集Spiral上的實驗結(jié)果揭示：本文MST＿Fr算法對于多個環(huán)狀分布的簇還不能完全正確識別其環(huán)數(shù)，即該數(shù)據(jù)集的正確類簇數(shù)，因此本文MST＿Fr算法還有進一步提升的空間，這是我們需要進一步研究的問題。

［1］周開樂，楊善林，丁帥，等.聚類有效性研究綜述［J］.系統(tǒng)工程理論與實踐，2014，34（9）：2417－2431.

［2］王開軍，李曉.基于有效性指標的聚類算法選擇［J］.四川師范大學學報：自然科學版，2011，34（6）：145－148.

［3］謝娟英，馬箐，謝維信.一種確定最佳類簇數(shù)的新算法［J］.陜西師范大學學報：自然科學版，2012，40（1）：13－18.

［4］David L Davies，Donald W Bouldin.A cluster separation measure［J］.Transactions on Pattern Analysis and Machine Intelligence，1979，4：224－227.

［5］周世兵，徐振源，唐旭清.K－means算法最佳聚類數(shù)確定方法［J］.計算機應用，2010，30（8）：1995－1998.

［6］周世兵，徐振源，唐旭清.新的K－means算法最佳聚類數(shù)確定方法［J］.計算機工程與應用，2010，46（16）：27－31.

［7］Chuanhao Wan，Peter de B Harrington.Self－configuring radial basis function neural networks for chemical pattern recognition［J］.Journal of Chemical Information and Computer Sciences，1999，39：1049－1056.

［8］Amy V Kapp，Robert Tibshirani.Are clusters found in one dataset present in another dataset？［J］.Biostatistics，2007，8（1）：9－31.

［9］謝季堅，劉承平.模糊數(shù)學方法及其應用［M］.2版.武漢：華中科技大學出版社，2000.

［10］Gao Xinbo，Li Jie，Tao Dacheng，et al.Fuzziness measurement of fuzzy sets and its application in cluster validity analysis［J］.International Journal of Fuzzy System，2007，9（4）：188－197.

［11］Zhexue Huang，Michael K Ng.A fuzzy k－modes algorithm for clustering categorical data［J］.IEEE Transactions on Fuzzy Systems，1999，4（7）：446－452.

［12］Jiawei Han，Kamber M.Data mining concepts and techniques［M］.Second Edition.Beijing：China Ma－chine Press，2006.

［13］孫吉貴，劉杰，趙連宇.聚類算法研究［J］.軟件學報，2008，19（1）：48－61.

［14］Park H S，Jun C H.A simple and fast algorithm for K－medoids clustering［J］.Expert Systems with Applications，2009，36（2）：3336－3341.

［15］Mohanmmad S，Zadegan R，Mirzaie M，et al.Ranked kmedoids：A fast and accurate rank－based partitioning algorithm for clustering large datasets［J］.Knowledgebased Systems，2013，39：133－143.

［16］王小樂，劉青寶，陸昌輝，等.一種最小生成樹聚類算法［J］.小型微型計算機系統(tǒng)，2009，30（5）：877－882.

［17］李翔宇，王開軍，郭躬德.基于網(wǎng)格最小生成樹的聚類算法選擇［J］.模式識別與人工智能，2013，26（1）：34－41.

［18］歐陽浩，陳波，黃鎮(zhèn)謹，等.基于K－means的最小生成樹聚類算法［J］.組合機床與自動化加工技術，2014，4：41－52.

［19］Oleksandr Grygorash，Yan Zhou，Zach Jorgensen.Minimum spanning tree based clustering algorithms［C］∥Proceedings of the 8th Nordic Signal Processing Symposium，2006.

［20］Joshua B Tenenbaum，Vin de Silva，John C Langford. A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290（5500）：2319－2323.

［21］嚴蔚敏，吳偉明.數(shù)據(jù)結(jié)構［M］.2版.北京：清華大學出版社，2012.

［22］謝娟英，郭文娟，謝維信.基于鄰域的K中心點聚類算法［J］.陜西師范大學學報：自然科學版，2012，40（4）：16－22.

［23］李美娟，陳國宏，陳衍泰.綜合評價中指標標準化方法研究［J］.中國管理科學，2004，12：45－48.

［24］Lichman，M.UCI Machine Learning Repository［EB／OL］.http：／／archive.ics.uci.edu／ml，2015－03－02.

［25］Joensuu.datasets［EB／OL］.http：∥cs.joensuu.fi／sipu／datasets／，2015－03－18.

〔責任編輯 宋軼文〕

A new criterion for clustering algorithm

XIE Juanying＊，ZHOU Ying
（School of Computer Science，Shaanxi Normal University，Xi'an 710119，Shaanxi，China）

The internal evaluation criteria，such as DB and BWP et al，need the upper bound of kmaxto be given in advance when these criteria are used to determine the number of clusters of a dataset，so that the number of clusters of kin a dataset satisfies k≤kmax.However，there is not so far a theory about how to find the upper bound of kmax.Aiming at this problem，a new F－statistics Fris proposed in this paper.Frcan be used as a new criterion to judge whether a clustering algorithm is converged or not，so that the number of clusters of a dataset can be found automatically without the upper bound of kmaxto be given in advance.In addition，F(xiàn)ris applied to the fast K－medoids clustering algorithm as its criterion to judge whether its iterations continues or not，and the geodesic distance between samples on the minimum spanning tree（MST），that is the length of the path between samples on MST，is introduced to instead of the direct Euclidean distance between them to measure their similarities，so that an adaptive fast K－medoids algorithm is obtained.The adaptive K－medoids algorithm avoids the deficiencies of the available K－medoids algorithms which need the number of clusters to be given in advance and cannot detect the clusters with any arbitrary shape.The power of the proposed criterion Frand the power of the adaptive fast K－medoids algorithm are tested in real world datasets from UCI machine learning repository and in the synthetic datasets.All the experimental results demonstrate that our proposed criterion Fris a valid clustering criterion，and the adaptive fast K－medoids algorithm based on the Frand geodesic distance can recognize the clusters with arbitrary shape，and can detect the number of clusters automatically，and is robust to noises as well.

F－statistics；internal evaluation criterion；the number of clusters；K－medoids clustering algorithm；minimum spanning tree

68T05

TP181.1

：A

1672－4291（2015）06－0001－08

10.15983／j.cnki.jsnu.2015.06.161

2015－05－22

國家自然科學基金（31372250）；陜西省科技攻關項目（2013K12－03－24）；中央高?；究蒲袠I(yè)務費專項資金（GK201503067）

＊通信作者：謝娟英，女，副教授，主要從事機器學習、數(shù)據(jù)挖掘、大數(shù)據(jù)分析方面的研究。E－mail：xiejuany＠snnu.edu.cn