基于置換檢驗(yàn)的聚類結(jié)果評(píng)估

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

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

?

基于置換檢驗(yàn)的聚類結(jié)果評(píng)估

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

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

摘要：對(duì)聚類結(jié)果，傳統(tǒng)的評(píng)估方法不能從統(tǒng)計(jì)意義上對(duì)結(jié)果評(píng)估。ECP是一種新穎的基于置換檢驗(yàn)的評(píng)估算法。ECP直接對(duì)聚類結(jié)果進(jìn)行置換檢驗(yàn)從而計(jì)算出p-value。為了測(cè)試ECP的效果，利用了UCI中的iris, wine, yeast數(shù)據(jù)集對(duì)算法進(jìn)行評(píng)測(cè)。實(shí)驗(yàn)結(jié)果表明，ECP可以在能夠接受的時(shí)間內(nèi)運(yùn)算出比較準(zhǔn)確的實(shí)驗(yàn)結(jié)果。

關(guān)鍵詞：聚類；聚類評(píng)估; 統(tǒng)計(jì)檢驗(yàn)；置換檢驗(yàn)

隨著獲得的數(shù)據(jù)越來(lái)越多，利用機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘[1-3]等手段從數(shù)據(jù)中獲取潛在的知識(shí)變得越來(lái)越重要。然而如何評(píng)估挖掘出來(lái)的信息，即評(píng)估數(shù)據(jù)挖掘結(jié)果的質(zhì)量是一個(gè)十分重要的問(wèn)題。只有一個(gè)好的評(píng)估方法，才能保證挖掘算法發(fā)現(xiàn)高質(zhì)量的信息。聚類[4-5]是數(shù)據(jù)挖掘領(lǐng)域一個(gè)很重要的分支。同時(shí)，聚類的應(yīng)用也越來(lái)越廣泛。隨著聚類的廣泛應(yīng)用，如何有效地評(píng)估聚類結(jié)果的質(zhì)量[6-7]成為一個(gè)重要的研究課題。雖然評(píng)估聚類結(jié)果的重要性一點(diǎn)不亞于挖掘算法本身，但是評(píng)估方面卻沒(méi)有受到它應(yīng)有的重視。

針對(duì)聚類，現(xiàn)有的方法主要是用評(píng)價(jià)函數(shù)對(duì)聚類結(jié)果評(píng)估。這種函數(shù)一般分3種類型：緊密型、分散型和連接型。常見(jiàn)的評(píng)估函數(shù)有DB-Index, Sihouette-Index, Dunn-Index等。這些函數(shù)能夠評(píng)估聚類結(jié)果，但是這些函數(shù)評(píng)估出來(lái)的結(jié)果往往沒(méi)有一個(gè)比較好的可以參考的值。即一個(gè)評(píng)估值計(jì)算出來(lái)之后得到的只是一個(gè)評(píng)估值，至于這個(gè)值達(dá)到什么標(biāo)準(zhǔn)能夠接受并不能確定。利用統(tǒng)計(jì)方法評(píng)估聚類結(jié)果的算法很少，其主要原因是聚類的特殊性與復(fù)雜性使傳統(tǒng)的統(tǒng)計(jì)方法很難用到聚類質(zhì)量評(píng)估上。近年來(lái)有一些利用隨機(jī)方法來(lái)評(píng)估聚類結(jié)果的研究，但也存在一定的問(wèn)題。本文根據(jù)存在的問(wèn)題提出了一種基于置換檢驗(yàn)的評(píng)估方法。

1相關(guān)研究

1.1利用簇結(jié)構(gòu)評(píng)估聚類質(zhì)量

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

1.2SigClust

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

1.3層次聚類的p-value計(jì)算

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

2基本概念

2.1無(wú)監(jiān)督聚類質(zhì)量評(píng)估函數(shù)

如果數(shù)據(jù)集中的元素沒(méi)有類標(biāo)簽，聚類結(jié)果的評(píng)價(jià)就只能依賴數(shù)據(jù)集自身的特征和量值。在這種情況下，聚類的度量追求有3個(gè)目標(biāo)：緊密度、分離度和鏈接度。

緊密度簇中的每個(gè)元素應(yīng)該彼此盡可能接近。緊密度的常用度量是方差，方差越小說(shuō)明緊密度越大。

分離度簇與簇之間應(yīng)該充分分離。有3種常用方法來(lái)度量?jī)蓚€(gè)不同簇之間的距離。單連接：度量不同簇的兩個(gè)最近成員的距離。全連接：度量不同簇的兩個(gè)最遠(yuǎn)成員的距離。質(zhì)心比較：度量不同簇的中心點(diǎn)的距離。

鏈接度鏈接度指簇中的元素成員至少要跟同一個(gè)簇內(nèi)的元素比較像。這個(gè)可以用來(lái)評(píng)估簇模型不是圓形或者球形的聚類結(jié)果，比如DBSCAN的聚類結(jié)果。

本文用一種無(wú)監(jiān)督評(píng)估聚類質(zhì)量的方法, Davies-Bouldin Index，即DB_Index。

式中：Si表示第i個(gè)簇內(nèi)的元素與質(zhì)心的標(biāo)準(zhǔn)方差，Dij表示第i個(gè)簇與第j個(gè)簇質(zhì)心間的歐幾里德距離，k表示簇的數(shù)目。

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

2.2聚類評(píng)估的p-value

給一個(gè)數(shù)據(jù)集X，用DB-Index計(jì)算聚類結(jié)果的函數(shù)值為x0x0。數(shù)據(jù)集X所有可能的聚類結(jié)果的函數(shù)值為x1,x2,…xNall。置換檢驗(yàn)的p-value定義為

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

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

這種方法把分子加1的理由是把x0也看作置換檢驗(yàn)一個(gè)樣本的函數(shù)值。這就避免了得到p-value為0的試驗(yàn)結(jié)果。然而這種做法事實(shí)上是不太合理的。試想如果抽樣999次沒(méi)有發(fā)現(xiàn)比x0更小的統(tǒng)計(jì)值，這樣草率地得出結(jié)論當(dāng)前置換檢驗(yàn)的結(jié)果為0.001顯然太武斷了。因?yàn)榭赡艹闃?9 999次依舊沒(méi)有比x0更優(yōu)的樣本。那么依照這個(gè)計(jì)算公式p-value又為0.000 01。而實(shí)際上p-value的值可能更小。因此本文把p-value的定義為Pperm0Pecdf0。

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

3基于置換檢驗(yàn)的聚類結(jié)果評(píng)估

3.1基本思想

本文提出的置換檢驗(yàn)方法將關(guān)注點(diǎn)鎖定在了聚類的結(jié)果上。評(píng)估聚類結(jié)果的本質(zhì)是看聚類算法對(duì)數(shù)據(jù)集中元素的劃分質(zhì)量。從這個(gè)角度出發(fā)，可以枚舉對(duì)數(shù)據(jù)集的劃分，然后用評(píng)估函數(shù)算出枚舉劃分的函數(shù)值。如果絕大部分劃分都沒(méi)有要評(píng)估的聚類結(jié)果質(zhì)量好的話，那么就說(shuō)明要評(píng)估的聚類結(jié)果質(zhì)量比較好。相反地，就說(shuō)明要評(píng)估的聚類結(jié)果質(zhì)量并不好。

因此對(duì)于一個(gè)聚類結(jié)果，本文定義了零假H0: 當(dāng)前聚類結(jié)果不是一個(gè)高質(zhì)量的聚類。然后計(jì)算這個(gè)零假設(shè)的p-value。如果這個(gè)p-value非常小，就認(rèn)為這個(gè)劃分結(jié)果可以接受，可以拒絕H0。否則認(rèn)為這個(gè)聚類結(jié)果不能接受。

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

接下來(lái)是抽樣。抽樣要滿足一定約束。本文定義的約束是: 樣本中簇包含元素的數(shù)目要與待評(píng)估聚類結(jié)果中簇中元素的數(shù)目保持一致。舉個(gè)例子，假設(shè)數(shù)據(jù)集元素?cái)?shù)目n為 100。劃分成3簇，劃分簇中的數(shù)目分別是40、33、27。那么抽樣出來(lái)的樣本也要滿足這些條件，也就是要?jiǎng)澐殖?簇，并且簇中元素的數(shù)目也必須是40、33、27。具體的抽樣方法: 首先搜集所有元素的簇標(biāo)號(hào)，然后將這些簇標(biāo)號(hào)隨機(jī)地分配給每個(gè)元素。其實(shí)這個(gè)過(guò)程是洗牌算法。算法1描述了抽樣的過(guò)程。

算法1Shuffle(CI,n)

fori← 0 ton-1 do

index ← rand() mod (i+ 1)

swap(CIi,CIindexCIi,CIindex)

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

算法2ECP1

用DB-Index計(jì)算聚類結(jié)果的函數(shù)值x0。

fori← 1 toNdo

Shuffle(CI,n)

用DB-Index計(jì)算樣本的函數(shù)值xi

計(jì)算p-value

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

3.2加速技巧

首先選取聚類結(jié)果作為初始狀態(tài)。然后隨機(jī)交換一對(duì)簇標(biāo)號(hào)不同的元素的簇標(biāo)號(hào)。交換后把此時(shí)的劃分作為一個(gè)樣本，直接計(jì)算DB-Index的函數(shù)值。接下來(lái)繼續(xù)交換一對(duì)簇標(biāo)號(hào)不同的元素的簇標(biāo)號(hào)，交換后計(jì)算DB-Index的值。這樣迭代N次后就會(huì)得到N個(gè)樣本的函數(shù)值。利用這N個(gè)值就可以計(jì)算出p-value。整個(gè)算法流程如下。

算法3ECP2

用DB-Index計(jì)算聚類結(jié)果的函數(shù)值x0

fori← 1 toNdo

隨機(jī)交換一對(duì)簇標(biāo)號(hào)不同元素的簇標(biāo)號(hào)

用DB-Index計(jì)算抽樣結(jié)果的函數(shù)值xi

計(jì)算p-value

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

由Si的定義可以得出:

其中:

因此

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

3.3更準(zhǔn)確的p-value

上邊提到計(jì)算DB-Index的方法的復(fù)雜度為O(k×k×d)。雖然相比于原先的計(jì)算方法已經(jīng)優(yōu)化很多，但是對(duì)于p-value非常小的情況，可能依舊由于抽樣數(shù)目有限而無(wú)法算出精確的p-value。這種情況下算出的p-value就會(huì)為0，然而這樣的結(jié)果是不準(zhǔn)確的。

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

(1)

(2)

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

這樣估出概率分布函數(shù)實(shí)現(xiàn)了在整體復(fù)雜度沒(méi)有增加的前提下用較少的抽樣得到更為精確p-value的目的了。

算法4ECP

抽樣N次，算出每次的函數(shù)值xi

統(tǒng)計(jì)xi≤x0的數(shù)目M

如果M≥Limit利用公式Pperm0計(jì)算p-value

否則，擬合正態(tài)概率分布算出p-value

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

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

實(shí)驗(yàn)選取了iris、wine和yeast等3個(gè)數(shù)據(jù)集。這3個(gè)數(shù)據(jù)集都來(lái)自UCI數(shù)據(jù)庫(kù)[15]。iris、wine和yeast數(shù)據(jù)集的屬性都是數(shù)值型的，并且這3個(gè)數(shù)據(jù)集都帶有類標(biāo)簽。

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

從聚類這個(gè)概念提出以來(lái)出現(xiàn)了很多聚類算法。對(duì)于一個(gè)具體的應(yīng)用，選擇合適的聚類算法是一個(gè)很重要的問(wèn)題。本文認(rèn)為對(duì)于同一個(gè)數(shù)據(jù)集用不同的算法聚類，p-value小的那個(gè)結(jié)果更為可靠。為此本文對(duì)同一數(shù)據(jù)集選用多種算法聚類來(lái)驗(yàn)證p-value對(duì)選擇聚類算法的有效性。實(shí)驗(yàn)結(jié)果如表1。從實(shí)驗(yàn)結(jié)果可以看出，對(duì)于同一數(shù)據(jù)集p-value小的聚類算法對(duì)應(yīng)的f-score和accuracy比較大。這說(shuō)明利用p-value選擇聚類算法是可靠的。本文還計(jì)算了p-value與f-score和accuracy的相關(guān)系數(shù)。本文用k-means對(duì)同一數(shù)據(jù)集聚類100次。通過(guò)控制k-means 的迭代次數(shù)來(lái)控制劃分的質(zhì)量。這樣就避免了正常k-means聚類只會(huì)出現(xiàn)若干個(gè)固定情況的問(wèn)題。

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

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

數(shù)據(jù)算法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

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

從實(shí)驗(yàn)結(jié)果可以看出用本文方法算出來(lái)的p-value是可靠的。需要注意的是yeast的數(shù)據(jù)集簇結(jié)構(gòu)比較明顯，聚類的結(jié)果比較集中。

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

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

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

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

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

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

4.2利用p-value決定數(shù)據(jù)集簇的數(shù)目k

很多聚類算法需要預(yù)先設(shè)定劃分?jǐn)?shù)目k。本文研究了p-value與k的關(guān)系。對(duì)于同一數(shù)據(jù)集，選擇不同的k用k-means分別聚類，然后計(jì)算對(duì)應(yīng)的p-value。計(jì)算結(jié)果如表2。

從表2中看出隨著k的增加，p-value 的值變小。因?yàn)閗越大，對(duì)數(shù)據(jù)集劃分得越細(xì)，同一個(gè)簇內(nèi)的元素就會(huì)越相似，p-value自然就會(huì)越小。然而劃分的越細(xì)并不意味著就一定越好。舉個(gè)極端的例子，將一個(gè)數(shù)據(jù)量為n的數(shù)據(jù)集劃分成n個(gè)簇是毫無(wú)意義的。

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

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

由實(shí)驗(yàn)結(jié)果可以看出，對(duì)于iris數(shù)據(jù)集，當(dāng)k取3的時(shí)候，R(3) = 2.538 900最大。事實(shí)上iris的類別數(shù)目就是3。接著看wine數(shù)據(jù)集，當(dāng)i取3的時(shí)候R(3)= 97.836 510最大。真實(shí)情況wine的類別數(shù)目就是3。對(duì)于yeast數(shù)據(jù)集當(dāng)i取4的時(shí)候R(4)= 14.991 890最大，以此來(lái)確定簇的數(shù)目為4。而事實(shí)上yeast的類別數(shù)目就是4。

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

表2　不同k下的p-value

表3　不同k下的R(k)

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

(a)Iris

(b) Wine

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

(a)Iris

(b) Wine

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

實(shí)驗(yàn)最多抽取1 000 000個(gè)樣本。對(duì)于這3個(gè)數(shù)據(jù)集，當(dāng)抽樣數(shù)目達(dá)10 000時(shí)p-value就基本穩(wěn)定了。這一結(jié)果證實(shí)該方法具有很強(qiáng)的可行性。

4.3與相關(guān)算法對(duì)比

4.3.1ECP與最大熵模型比較

本文重復(fù)了最大熵模型的評(píng)估方法，這3個(gè)數(shù)據(jù)集算出的p-value都為1/N。這是因?yàn)闃颖咎?，算法把原始聚類結(jié)果也當(dāng)做一個(gè)樣本。前文分析了這種做法的不合理性。利用ECP就可以避免這樣的情況。除此之外，本文也嘗試將最大熵方法的抽樣評(píng)估值擬合出正態(tài)分布。實(shí)驗(yàn)結(jié)果如表4。從實(shí)驗(yàn)結(jié)果可以看出，對(duì)于wine數(shù)據(jù)集，最大熵方法算出的p-value為0.001，擬合正態(tài)后的p-value為0.370 035 2。這兩者差距比較大，這說(shuō)明將最大熵方法擬合成正態(tài)分布是不合適的。這一實(shí)驗(yàn)說(shuō)明利用ECP評(píng)估聚類結(jié)果更為可靠。

4.3.2ECP與SigClust對(duì)比

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

表4ECP與最大熵方法對(duì)比

Table 4The comparison of ECP and maximum entropy method

算法iriswineyeast最大熵0.0010.0010.001最大熵?cái)M合正態(tài)4.891817e-050.37003520.002626655ECP0.042742131.988773e-056.937873e-05

表5　ECP與Sigclust對(duì)比

4.3.3ECP與ECP1對(duì)比

這一部分說(shuō)明ECP比加速的ECP1在效率上有很大提高。ECP1是未加速的ECP算法。本文將這兩種算法進(jìn)行了效率上的對(duì)比。實(shí)驗(yàn)結(jié)果如表6。實(shí)驗(yàn)分別用兩種算法抽樣100 000次并得到對(duì)應(yīng)的統(tǒng)計(jì)值?？梢钥闯觯瑢?duì)于iris數(shù)據(jù)集，ECP比ECP1快了60倍?？梢?jiàn)ECP在效率上有質(zhì)的提升。

表6　ECP與ECP1效率對(duì)比

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

本文提出了一種新的基于置換檢驗(yàn)的聚類結(jié)果評(píng)估方法ECP。為了增大抽樣的數(shù)目，利用DB-Index的計(jì)算特點(diǎn)減小了對(duì)樣本函數(shù)值計(jì)算的復(fù)雜度。為了得到更精確的p-value，根據(jù)聚類劃分的特點(diǎn)，假設(shè)了DB-Index的函數(shù)值是符合高斯分布的，進(jìn)而可以用較少的抽樣估出更為準(zhǔn)確的p-value。從實(shí)驗(yàn)的結(jié)果來(lái)看，ECP對(duì)評(píng)估聚類結(jié)果有很好的效果，并且具有很強(qiáng)的實(shí)用性。

參考文獻(xiàn):

[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]尹宏偉, 李凡長(zhǎng). 譜機(jī)器學(xué)習(xí)研究綜述[J]. 計(jì)算機(jī)科學(xué)與探索, 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]張剛, 劉悅, 郭嘉豐, 等. 一種層次化的檢索結(jié)果聚類方法[J]. 計(jì)算機(jī)研究與發(fā)展, 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年生，碩士研究生，主要研究方向是數(shù)據(jù)挖掘和生物信息。

田博，女，1992年生，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘和生物信息。

何增有，男，1976年生，副教授，主要研究方向?yàn)閿?shù)據(jù)挖掘和生物信息學(xué)，學(xué)術(shù)論文均發(fā)表在該領(lǐng)域的頂級(jí)期刊或會(huì)議上，出版學(xué)術(shù)專著1部。

中文引用格式：谷飛洋,田博,張思萌,等.基于置換檢驗(yàn)的聚類結(jié)果評(píng)估[J]. 智能系統(tǒng)學(xué)報(bào)， 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

作者簡(jiǎn)介：

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

文獻(xiàn)標(biāo)志碼：A

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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61572094).

收稿日期：2016-03-19.網(wǎng)絡(luò)出版日期：2016-05-13.

DOI:10.11992/tis.201603038

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0925.028.html