基于置換檢驗的聚類結果評估

谷飛洋,田博,張思萌,陳征,何增有

(大連理工大學 軟件學院， 遼寧 大連 116621)

?

基于置換檢驗的聚類結果評估

谷飛洋,田博,張思萌,陳征,何增有

(大連理工大學 軟件學院， 遼寧 大連 116621)

摘要：對聚類結果，傳統的評估方法不能從統計意義上對結果評估。ECP是一種新穎的基于置換檢驗的評估算法。ECP直接對聚類結果進行置換檢驗從而計算出p-value。為了測試ECP的效果，利用了UCI中的iris, wine, yeast數據集對算法進行評測。實驗結果表明，ECP可以在能夠接受的時間內運算出比較準確的實驗結果。

關鍵詞：聚類；聚類評估; 統計檢驗；置換檢驗

隨著獲得的數據越來越多，利用機器學習、數據挖掘[1-3]等手段從數據中獲取潛在的知識變得越來越重要。然而如何評估挖掘出來的信息，即評估數據挖掘結果的質量是一個十分重要的問題。只有一個好的評估方法，才能保證挖掘算法發現高質量的信息。聚類[4-5]是數據挖掘領域一個很重要的分支。同時，聚類的應用也越來越廣泛。隨著聚類的廣泛應用，如何有效地評估聚類結果的質量[6-7]成為一個重要的研究課題。雖然評估聚類結果的重要性一點不亞于挖掘算法本身，但是評估方面卻沒有受到它應有的重視。

針對聚類，現有的方法主要是用評價函數對聚類結果評估。這種函數一般分3種類型：緊密型、分散型和連接型。常見的評估函數有DB-Index, Sihouette-Index, Dunn-Index等。這些函數能夠評估聚類結果，但是這些函數評估出來的結果往往沒有一個比較好的可以參考的值。即一個評估值計算出來之后得到的只是一個評估值，至于這個值達到什么標準能夠接受并不能確定。利用統計方法評估聚類結果的算法很少，其主要原因是聚類的特殊性與復雜性使傳統的統計方法很難用到聚類質量評估上。近年來有一些利用隨機方法來評估聚類結果的研究，但也存在一定的問題。本文根據存在的問題提出了一種基于置換檢驗的評估方法。

1相關研究

1.1利用簇結構評估聚類質量

該方法先對原始數據聚類，然后將原始數據集按照一定的約束隨機置換抽樣構造新的數據集。抽樣之后用同樣的聚類算法對樣本數據集進行聚類。這樣重復大量的次數后，再用評估函數(如DB-Index)計算每個樣本的函數值。如果原始數據集聚類結果的函數值小于大部分隨機構造的數據集聚類結果的函數值，那么說明挖掘出來的信息是可靠的，否則說明聚類結果不可靠。更通俗一點，如果原來數據集沒有好的簇結構，那么無論怎么聚類，結果都是不好的。代表性的方法有最大熵模型抽樣[8]、矩陣元素交換[9]等。利用數據集簇結構來評估聚類質量[10]的方法能很好地評估出簇結構不好的聚類結果。實驗證實對不同數據集進行聚類，有明顯簇結構數據集的p-value會比沒有明顯簇結構的p-value小很多。但是這種方法并不能準確評估聚類的質量。從某種意義上講，這種方法更適合評估一個數據集是否有好的簇結構。

1.2SigClust

SigClust[11]認為如果一個數據集符合高斯分布，那么對這個數據集的任何分割都是不合理的。因此這個方法的前提假設是：一個單一的簇的元素符合高斯分布。SigClust主要是針對k=2的聚類評估。對于k>2的情況，還沒有比較好的解決辦法。

1.3層次聚類的p-value計算

這種方法主要針對層次聚類的評估[12,13]。層次聚類后會形成一個二叉樹。對二叉樹上的每個節點都進行置換檢驗，算出每個節點劃分對應的p-value。這種算法的空假設為：當前節點的左子樹和右子樹應該屬于一個簇。如果算出p-value 足夠小就說明空假設是一個小概率事件，應該拒絕。該方法是將當前節點的左子樹和右子樹打亂，按照一定的約束隨機分配左子樹和右子樹的元素。抽樣若干次后形成的隨機樣本集按照某種指標與原始劃分對比計算出p-value。這個評估只能針對層次聚類，不能對其他的聚類算法進行評估。另外這樣計算出的p-value只是每個節點上的p-value,并不是全局聚類的p-value。

2基本概念

2.1無監督聚類質量評估函數

如果數據集中的元素沒有類標簽，聚類結果的評價就只能依賴數據集自身的特征和量值。在這種情況下，聚類的度量追求有3個目標：緊密度、分離度和鏈接度。

緊密度簇中的每個元素應該彼此盡可能接近。緊密度的常用度量是方差，方差越小說明緊密度越大。

分離度簇與簇之間應該充分分離。有3種常用方法來度量兩個不同簇之間的距離。單連接：度量不同簇的兩個最近成員的距離。全連接：度量不同簇的兩個最遠成員的距離。質心比較：度量不同簇的中心點的距離。

鏈接度鏈接度指簇中的元素成員至少要跟同一個簇內的元素比較像。這個可以用來評估簇模型不是圓形或者球形的聚類結果，比如DBSCAN的聚類結果。

本文用一種無監督評估聚類質量的方法, Davies-Bouldin Index，即DB_Index。

式中：Si表示第i個簇內的元素與質心的標準方差，Dij表示第i個簇與第j個簇質心間的歐幾里德距離，k表示簇的數目。

DBI的思想是一個高質量的聚類結果需要滿足:同一個簇的各元素間相似度大，不同類之間的相似度小。在DBI中，分子越小意味著簇內元素相似度越大，分母越大意味著簇間相似度越小。

2.2聚類評估的p-value

給一個數據集X，用DB-Index計算聚類結果的函數值為x0x0。數據集X所有可能的聚類結果的函數值為x1,x2,…xNall。置換檢驗的p-value定義為

式中I是一個邏輯函數。當xn≤x0的情況下為1，否則為0。由于要枚舉出所有的聚類方案的復雜度是指數級別的，所以需要采取其他的策略。抽樣出所有情況的一個子集Y，并計算子集Y中所有元素的函數值為x1,x2,…xN,其中N?Nall。這時候置換檢驗的p-value被定義為

一些研究為了避免p-value為0的情況，將p-value的定義修改為

這種方法把分子加1的理由是把x0也看作置換檢驗一個樣本的函數值。這就避免了得到p-value為0的試驗結果。然而這種做法事實上是不太合理的。試想如果抽樣999次沒有發現比x0更小的統計值，這樣草率地得出結論當前置換檢驗的結果為0.001顯然太武斷了。因為可能抽樣99 999次依舊沒有比x0更優的樣本。那么依照這個計算公式p-value又為0.000 01。而實際上p-value的值可能更小。因此本文把p-value的定義為Pperm0Pecdf0。

置換檢驗的準確性取決于抽樣的數目，一般的置換檢驗抽樣的次數都在1 000次以上。為了得到更精確的p-value抽樣的次數越多越好，理想的情況是置換所有的可能。然而對于不同的數據集合，甚至很難預測需要執行多少次置換才能夠得到比較好的結果。往往為了得到更精確的值就會增大抽樣次數，但是增加抽樣次數的代價是增加計算的復雜性。對于普通的數據集往往抽樣次數達到10 000次之后就不太容易提高抽樣次數。而這樣做又產生出了一個問題。如果一個聚類結果真實的p-value為0.000 001。而抽樣的次數只有10 000次的話，那么p-value為就為0了。針對這些問題，本文提出了一種新的聚類評估方法，ECP，該方法能比較好地解決上文提到的問題。

3基于置換檢驗的聚類結果評估

3.1基本思想

本文提出的置換檢驗方法將關注點鎖定在了聚類的結果上。評估聚類結果的本質是看聚類算法對數據集中元素的劃分質量。從這個角度出發，可以枚舉對數據集的劃分，然后用評估函數算出枚舉劃分的函數值。如果絕大部分劃分都沒有要評估的聚類結果質量好的話，那么就說明要評估的聚類結果質量比較好。相反地，就說明要評估的聚類結果質量并不好。

因此對于一個聚類結果，本文定義了零假H0: 當前聚類結果不是一個高質量的聚類。然后計算這個零假設的p-value。如果這個p-value非常小，就認為這個劃分結果可以接受，可以拒絕H0。否則認為這個聚類結果不能接受。

定義數據集X是一個包含n個元素的d維數值型矩陣。首先對數據集聚類，聚成k簇后每個元素都會歸屬于一個簇。我們對每個簇進行標號。標號從0開始，往后依次是1,2, …,k-1。定義CIi為第i個元素所屬的簇標號。比如CI3=2表示第3個元素屬于標號為2的簇。

接下來是抽樣。抽樣要滿足一定約束。本文定義的約束是: 樣本中簇包含元素的數目要與待評估聚類結果中簇中元素的數目保持一致。舉個例子，假設數據集元素數目n為 100。劃分成3簇，劃分簇中的數目分別是40、33、27。那么抽樣出來的樣本也要滿足這些條件，也就是要劃分成3簇，并且簇中元素的數目也必須是40、33、27。具體的抽樣方法: 首先搜集所有元素的簇標號，然后將這些簇標號隨機地分配給每個元素。其實這個過程是洗牌算法。算法1描述了抽樣的過程。

算法1Shuffle(CI,n)

fori← 0 ton-1 do

index ← rand() mod (i+ 1)

swap(CIi,CIindexCIi,CIindex)

可以用數學歸納法進行證明算法1保證了每個元素獲得同一簇標號的概率是一樣的。抽樣的復雜度為O(n)。這樣進行抽樣N次，就得到了N個樣本。然后利用樣本對原始聚類結果進行評估。用DB-Index算出原始聚類的函數值x0與樣本的函數值x1,x2,…，xN。有了這些值就能計算p-value了。具體算法如下。

算法2ECP1

用DB-Index計算聚類結果的函數值x0。

fori← 1 toNdo

Shuffle(CI,n)

用DB-Index計算樣本的函數值xi

計算p-value

一般情況下k?n，因此DB-Index的復雜度為O(n×d)。抽樣一次的復雜度是O(n)，容易算出總體復雜度為O(N×n×d)。這個復雜度還是比較高的。所以需要想一些方法來降低復雜度。N是抽樣次數，期望越大越好。可以看到DB-Index是影響復雜度的主要因素。如果降低DB-Index計算的復雜性，那么就可以在相同的時間內抽取更多的樣本來提高p-value的準確度。本文發現了DB-Index公式的特點，對上文提到的算法做了改進。

3.2加速技巧

首先選取聚類結果作為初始狀態。然后隨機交換一對簇標號不同的元素的簇標號。交換后把此時的劃分作為一個樣本，直接計算DB-Index的函數值。接下來繼續交換一對簇標號不同的元素的簇標號，交換后計算DB-Index的值。這樣迭代N次后就會得到N個樣本的函數值。利用這N個值就可以計算出p-value。整個算法流程如下。

算法3ECP2

用DB-Index計算聚類結果的函數值x0

fori← 1 toNdo

隨機交換一對簇標號不同元素的簇標號

用DB-Index計算抽樣結果的函數值xi

計算p-value

對比ECP1，ECP2只是修改了第3步的抽樣方法。為什么修改了抽樣方法就可以增大抽樣次數？下面將仔細討論DB-Index的計算過程。DB-Index的計算公式為

由Si的定義可以得出:

其中:

因此

可以看出修改一個簇的平方和與平均值復雜度是O(d)的。因此DB-Index的計算復雜度就是O(k×k×d)了。沒有加速的DB-Index的計算復雜度是O(n×d)。一般情況下，k?n。所以這種方法的效率有明顯的提升。

3.3更準確的p-value

上邊提到計算DB-Index的方法的復雜度為O(k×k×d)。雖然相比于原先的計算方法已經優化很多，但是對于p-value非常小的情況，可能依舊由于抽樣數目有限而無法算出精確的p-value。這種情況下算出的p-value就會為0，然而這樣的結果是不準確的。

如果知道了樣本DB-Index函數值的概率分布就可以根據原始聚類結果的函數值算出精確的p-value了[14]。聚類是一種半監督的機器學習，其本質對元素所屬類別的劃分。如果對元素隨機劃分無窮次。那么質量特別高的劃分的比例會很小。同樣的，質量極端差的劃分占的比例也會很小。很大比重的劃分都介于它們之間。而正態分布的特點是：極端概率很小，中間的概率很大。經過對數據的分析，聚類劃分的DB-Index函數值比較符合正態分布。因此可以假設抽樣樣本DB-Index的函數值符合正態分布。實際上正態分布符合很多自然概率分布的指標。下面要做的就是得到正態分布的參數。對于一維的正態分布均值和方差用式(1)和(2)得到：

(1)

(2)

有了概率分布函數，就能將原始聚類結果x0代入概率分布算出p-value了。

這樣估出概率分布函數實現了在整體復雜度沒有增加的前提下用較少的抽樣得到更為精確p-value的目的了。

算法4ECP

抽樣N次，算出每次的函數值xi

統計xi≤x0的數目M

如果M≥Limit利用公式Pperm0計算p-value

否則，擬合正態概率分布算出p-value

其中Limit是ECP的一個參數，是用Pperm0計算出p-value的最低數目限制。ECP不同于很多其他的置換檢驗方法。這種方法實現了用較少的抽樣計算出更為精確p-value的目的，在效率上有了非常大的飛躍。

4實驗

實驗選取了iris、wine和yeast等3個數據集。這3個數據集都來自UCI數據庫[15]。iris、wine和yeast數據集的屬性都是數值型的，并且這3個數據集都帶有類標簽。

4.1利用p-value選擇合適的聚類算法

從聚類這個概念提出以來出現了很多聚類算法。對于一個具體的應用，選擇合適的聚類算法是一個很重要的問題。本文認為對于同一個數據集用不同的算法聚類，p-value小的那個結果更為可靠。為此本文對同一數據集選用多種算法聚類來驗證p-value對選擇聚類算法的有效性。實驗結果如表1。從實驗結果可以看出，對于同一數據集p-value小的聚類算法對應的f-score和accuracy比較大。這說明利用p-value選擇聚類算法是可靠的。本文還計算了p-value與f-score和accuracy的相關系數。本文用k-means對同一數據集聚類100次。通過控制k-means 的迭代次數來控制劃分的質量。這樣就避免了正常k-means聚類只會出現若干個固定情況的問題。

表1不同聚類方法的p-value, f-score, accuracy

Table 1The p-value, f-score, accuracy of different cluster algorithms

數據算法p-valuef-scoreaccuracyIrisRandom0.4562541.1341400.380000HierarchicalClustering0.1005481.6565700.666667DBSCAN0.0428252.7144000.906667k-means0.0427512.6558400.886667WineRandom0.5595881.0954200.410112HierarchicalClustering0.0015741.6664600.657303DBSCAN1.892991e-052.8337500.943820k-means1.818384e-052.8322000.943820YeastRandom0.6881451.0782600.357198HierarchicalClustering0.0038710.8353710.360277DBSCAN0.0007111.3048000.434950k-means7.544556e-051.8819500.480370

針對iris數據集，利用ECP計算出的p-value與f-score的相關系數為-0.578 018，與accuracy的相關系數為-0.699 331。具體的結果如圖1。針對wine數據集，利用ECP計算得到的p-value與f-score的相系數為-0.535 734，與accuracy的相關系數為-0.538 754。具體的結果為圖2。對于yeast數據集，利用ECP計算得到的p-value與f-score的相關系數為-0.500 340，與accuracy的相關系數為-0.167 325。具體結果為圖3。

從實驗結果可以看出用本文方法算出來的p-value是可靠的。需要注意的是yeast的數據集簇結構比較明顯，聚類的結果比較集中。

(a)p-value與f-score的關系

(b)p-value與accuracy的關系圖1　Iris數據集p-value與f-score和accuracy的關系Fig.1　The relationship between p-value and f-score, accuracy of iris dataset

(a)p-value與f-score的關系

(b)p-value與accuracy的關系圖2　Wine數據集p-value與f-score和accuracy的關系Fig.2　The relationship between p-value and f-score, accuracy of wine dataset

(a)p-value與f-score的關系

(b)p-value與accuracy的關系圖3　Yeast數據集p-value與f-score和accuracy的關系Fig.3　The relationship between p-value and f-score, accuracy of yeast dataset

4.2利用p-value決定數據集簇的數目k

很多聚類算法需要預先設定劃分數目k。本文研究了p-value與k的關系。對于同一數據集，選擇不同的k用k-means分別聚類，然后計算對應的p-value。計算結果如表2。

從表2中看出隨著k的增加，p-value 的值變小。因為k越大，對數據集劃分得越細，同一個簇內的元素就會越相似，p-value自然就會越小。然而劃分的越細并不意味著就一定越好。舉個極端的例子，將一個數據量為n的數據集劃分成n個簇是毫無意義的。

本文研究了一種利用p-value 的變化幅度來確定k的新方法。這里給出一個定義:

式中：p(i-1)是當k取i-1時聚類結果的p-value，p(i)是當k取i時的聚類結果的p-value。R(i)的意義是當k增加1時p-value的變化幅度。將表2的結果按照公式計算的結果如表3。

由實驗結果可以看出，對于iris數據集，當k取3的時候，R(3) = 2.538 900最大。事實上iris的類別數目就是3。接著看wine數據集，當i取3的時候R(3)= 97.836 510最大。真實情況wine的類別數目就是3。對于yeast數據集當i取4的時候R(4)= 14.991 890最大，以此來確定簇的數目為4。而事實上yeast的類別數目就是4。

利用本文提出的定義能正確算出數據集中的簇數目k。因此可以說明計算聚類的p-value對于確定聚類數目k也是有一定意義的。不過對于R(i)這個定義還存在一定的問題。根據R的定義，i的取值不小于3。因此對于簇數目為2的情況還不能夠做出合適的處理。

表2　不同k下的p-value

表3　不同k下的R(k)

研究了對于iris、wine和yeast數據集需要多少樣本能保證p-value不會因樣本數目的增加而改變。對于每個數據集用不同數目樣本計算p-value，結果如圖5。

(a)Iris

(b) Wine

(c) Yeast圖4　p-value 穩定性Fig.4　The stability of p-value

(a)Iris

(b) Wine

(c) Yeast圖5　p-value與抽樣次數的關系Fig.5　The relationship between p-value and the number of samples

實驗最多抽取1 000 000個樣本。對于這3個數據集，當抽樣數目達10 000時p-value就基本穩定了。這一結果證實該方法具有很強的可行性。

4.3與相關算法對比

4.3.1ECP與最大熵模型比較

本文重復了最大熵模型的評估方法，這3個數據集算出的p-value都為1/N。這是因為樣本太少，算法把原始聚類結果也當做一個樣本。前文分析了這種做法的不合理性。利用ECP就可以避免這樣的情況。除此之外，本文也嘗試將最大熵方法的抽樣評估值擬合出正態分布。實驗結果如表4。從實驗結果可以看出，對于wine數據集，最大熵方法算出的p-value為0.001，擬合正態后的p-value為0.370 035 2。這兩者差距比較大，這說明將最大熵方法擬合成正態分布是不合適的。這一實驗說明利用ECP評估聚類結果更為可靠。

4.3.2ECP與SigClust對比

SigClust算法是主要針對k為2聚類結果的評估。本文從每個數據集中選出了兩類用k-means進行聚類(比如iris數據集中選出了Setosa、Versicolour兩類進行對比)。為了讓聚類質量有層次的差距，對k-means的聚類結果進行不同程度的破壞。破壞的程度越大，聚類的質量越差。實驗結果如表5。從實驗看SigClust與ECP都能夠區別出很好和很差的聚類。但是可以很明顯地看出，SigClust對聚類質量的區分度不夠大。比如對于iris數據集計算的f1為2和1.8，SigClust算出的p-value都是0，沒有區分開這2個不同劃分的質量。同樣地iris數據集f1為1.36和1.158 65，SigClust算出的p-value都為1。實驗可以看出ECP能很好地區分聚類質量的差距。因此，與SigClust相比，ECP不僅能處理k>2的情況，而且能更好地評估聚類質量。

表4ECP與最大熵方法對比

Table 4The comparison of ECP and maximum entropy method

算法iriswineyeast最大熵0.0010.0010.001最大熵擬合正態4.891817e-050.37003520.002626655ECP0.042742131.988773e-056.937873e-05

表5　ECP與Sigclust對比

4.3.3ECP與ECP1對比

這一部分說明ECP比加速的ECP1在效率上有很大提高。ECP1是未加速的ECP算法。本文將這兩種算法進行了效率上的對比。實驗結果如表6。實驗分別用兩種算法抽樣100 000次并得到對應的統計值。可以看出，對于iris數據集，ECP比ECP1快了60倍。可見ECP在效率上有質的提升。

表6　ECP與ECP1效率對比

5結束語

本文提出了一種新的基于置換檢驗的聚類結果評估方法ECP。為了增大抽樣的數目，利用DB-Index的計算特點減小了對樣本函數值計算的復雜度。為了得到更精確的p-value，根據聚類劃分的特點，假設了DB-Index的函數值是符合高斯分布的，進而可以用較少的抽樣估出更為準確的p-value。從實驗的結果來看，ECP對評估聚類結果有很好的效果，并且具有很強的實用性。

參考文獻:

[1]TAN Pangning, STEINBACH M, KUMAR V. Introduction to data mining[M]. Boston: Addison-Wesley, 2005.

[2]HAN Jiawei, KAMBER M, PEI Jian. Data mining: concepts and techniques[M]. 3rd ed. Burlington, MA, USA: Elsevier, 2012: 1-33.

[3]尹宏偉, 李凡長. 譜機器學習研究綜述[J]. 計算機科學與探索, 2015, 9(12): 1409-1419.

YIN Hongwei, LI Fanzhang. Survey on spectral machine learning[J]. Journal of frontiers of computer science and technology, 2015, 9(12): 1409-1419.

[4]JAIN A K, MURTY M N, FLYNN P J. Data clustering: a review[J]. ACM computing surveys, 1999, 31(3): 264-323.

[5]WU Xindong, KUMAR V, QUINLAN J R, et al. Top 10 algorithms in data mining[J]. Knowledge and information systems, 2008, 14(1): 1-37.

[6]HALKIDI M, BATISTAKIS Y, VAZIRGIANNIS M. On clustering validation techniques[J]. Journal of intelligent information systems, 2001, 17(2-3): 107-145.

[7]HANDL J, KNOWLES J, KELL D B. Computational cluster validation in post-genomic data analysis[J]. Bioinformatics, 2005, 21(15): 3201-3212.

[8]KONTONASIOS K N, VREEKEN J, DE BIE T. Maximum entropy modelling for assessing results on real-valued data[C]//Proceedings of the 11th international conference on data mining. Vancouver, BC, Canada, 2011: 350-359.

[9]OJALA M. Assessing data mining results on matrices with randomization[C]//Proceedings of international conference on data mining. Sydney, Australia, 2010: 959-964.

[10]OJALA M, VUOKKO N, KALLIO A, et al. Randomization methods for assessing data analysis results on real-valued matrices[J]. Statistical analysis and data mining, 2009, 2(4): 209-230.

[11]LIU Yufeng, HAYES D N, NOBEL A, et al. Statistical significance of clustering for high-dimension, low-sample size data[J]. Journal of the American statistical association, 2008, 103(483): 1281-1293.

[12]PARK P J, MANJOURIDES J, BOONETTI M, et al. A permutation test for determining significance of clusters with applications to spatial and gene expression data[J]. Computational statistics & data analysis, 2009, 53(12): 4290-4300.

[13]張剛, 劉悅, 郭嘉豐, 等. 一種層次化的檢索結果聚類方法[J]. 計算機研究與發展, 2008, 45(3): 542-547.

ZHANG Gang, LIU Yue, GUO Jiafeng, et al. A Hierarchical search result clustering method[J]. Journal of computer research and development, 2008, 45(3): 542-547.

[14]KNIJNENBURG T A, WESSELS L F A, REINDERS M J T, et al. Fewer permutations, more accurate p-values[J].

Bioinformatics, 2009, 25(12): i161-i168.

[15]ASUNCION A, NEWMAN D J. UCI machine learning repository[EB/OL]. 2007. http://archive.ics.uci.edu/ml/.

谷飛洋，男，1991年生，碩士研究生，主要研究方向是數據挖掘和生物信息。

田博，女，1992年生，碩士研究生，主要研究方向為數據挖掘和生物信息。

何增有，男，1976年生，副教授，主要研究方向為數據挖掘和生物信息學，學術論文均發表在該領域的頂級期刊或會議上，出版學術專著1部。

中文引用格式：谷飛洋,田博,張思萌,等.基于置換檢驗的聚類結果評估[J]. 智能系統學報， 2016, 11(3): 301-309.

英文引用格式：GU Feiyang, TIAN Bo, ZHANG Simeng, et al. Statistical evaluation of the clustering results based on permutation test[J]. CAAI transactions on intelligent systems, 2016,11(3): 301-309.

Statistical evaluation of the clustering results based on permutation test

GU Feiyang, TIAN Bo, ZHANG Simeng, CHEN Zheng, HE Zengyou

(Software School, Dalian University of Technology, Dalian 116621, China)

Abstract：For the result of clustering, tranditional methods of evalution couldn't assess the result in statistics. We propose a new algorithm called ECP(Statistical evaluation of Clustering based on Permutation test) which uses permutation test to evaluate the result of clustering. To evaluate the performance of the algorithm, we use the data sets, iris, wine, yeast, from UCI datasets. Experimental results show that the performance of the algorithm is good.

Keywords：clustering; clustering evaluation; statistical test; permutation test

作者簡介：

中圖分類號：TP393

文獻標志碼：A

文章編號：1673-4785(2016)03-0301-09

通信作者：何增有. E-mail：zyhe@dlut.edu.cn.

基金項目：國家自然科學基金項目(61572094).

收稿日期：2016-03-19.網絡出版日期：2016-05-13.

DOI:10.11992/tis.201603038

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0925.028.html