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

醫(yī)學(xué)數(shù)據(jù)科學(xué) 2020-04-07

展開全文

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

針對(duì)聚類，現(xiàn)有的方法主要是用評(píng)價(jià)函數(shù)對(duì)聚類結(jié)果評(píng)估。這種函數(shù)一般分3種類型：緊密型、分散型和連接型。常見的評(píng)估函數(shù)有DB-Index, Sihouette-Index, Dunn-Index等。這些函數(shù)能夠評(píng)估聚類結(jié)果，但是這些函數(shù)評(píng)估出來的結(jié)果往往沒有一個(gè)比較好的可以參考的值。即一個(gè)評(píng)估值計(jì)算出來之后得到的只是一個(gè)評(píng)估值，至于這個(gè)值達(dá)到什么標(biāo)準(zhǔn)能夠接受并不能確定。利用統(tǒng)計(jì)方法評(píng)估聚類結(jié)果的算法很少，其主要原因是聚類的特殊性與復(fù)雜性使傳統(tǒng)的統(tǒng)計(jì)方法很難用到聚類質(zhì)量評(píng)估上。近年來有一些利用隨機(jī)方法來評(píng)估聚類結(jié)果的研究，但也存在一定的問題。本文根據(jù)存在的問題提出了一種基于置換檢驗(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ù)值，那么說明挖掘出來的信息是可靠的，否則說明聚類結(jié)果不可靠。更通俗一點(diǎn)，如果原來數(shù)據(jù)集沒有好的簇結(jié)構(gòu)，那么無論怎么聚類，結(jié)果都是不好的。代表性的方法有最大熵模型抽樣^[8]、矩陣元素交換^[9]等。利用數(shù)據(jù)集簇結(jié)構(gòu)來評(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ì)比沒有明顯簇結(jié)構(gòu)的p-value小很多。但是這種方法并不能準(zhǔn)確評(píng)估聚類的質(zhì)量。從某種意義上講，這種方法更適合評(píng)估一個(gè)數(shù)據(jù)集是否有好的簇結(jié)構(gòu)。

1.2 SigClust

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

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

這種方法主要針對(duì)層次聚類的評(píng)估^[12, 13]。層次聚類后會(huì)形成一個(gè)二叉樹。對(duì)二叉樹上的每個(gè)節(jié)點(diǎn)都進(jìn)行置換檢驗(yàn)，算出每個(gè)節(jié)點(diǎn)劃分對(duì)應(yīng)的p-value。這種算法的空假設(shè)為：當(dāng)前節(jié)點(diǎn)的左子樹和右子樹應(yīng)該屬于一個(gè)簇。如果算出p-value 足夠小就說明空假設(shè)是一個(gè)小概率事件，應(yīng)該拒絕。該方法是將當(dāng)前節(jié)點(diǎn)的左子樹和右子樹打亂，按照一定的約束隨機(jī)分配左子樹和右子樹的元素。抽樣若干次后形成的隨機(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 無監(jiān)督聚類質(zhì)量評(píng)估函數(shù)

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

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

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

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

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

${\text{DBI}} = \frac{1}{k}\sum\limits_{i = 1}^k {\max \left( {\frac{{{S_i} + {S_j}}}{{{D_{ij}}}}} \right)} .$

式中：S_i表示第i個(gè)簇內(nèi)的元素與質(zhì)心的標(biāo)準(zhǔn)方差，D_ij表示第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ù)值為x₀x₀。數(shù)據(jù)集X所有可能的聚類結(jié)果的函數(shù)值為x₁, x₂, …x_{N_all}。置換檢驗(yàn)的p-value定義為

${P_{perm}} = \frac{{\sum\nolimits_{n = 1}^{{N_{{\text{all}}}}} {I\left( {{x_n} ≤ {x_0}} \right)} }}{{{N_{{\text{all}}}}}}$

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

${P_{perm0}} = \frac{{\sum\nolimits_{n = 1}^N {I\left( {{x_n} ≤ {x_0}} \right)} }}{N}.$

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

${P_{perm1}} = \frac{{1 + \sum\nolimits_{n = 1}^N {1\left( {{x_n} ≤ {x_0}} \right)} }}{{N + 1}}$

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

置換檢驗(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è)問題。如果一個(gè)聚類結(jié)果真實(shí)的p-value為0.000 001。而抽樣的次數(shù)只有10 000次的話，那么p-value為就為0了。針對(duì)這些問題，本文提出了一種新的聚類評(píng)估方法，ECP，該方法能比較好地解決上文提到的問題。

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ù)值。如果絕大部分劃分都沒有要評(píng)估的聚類結(jié)果質(zhì)量好的話，那么就說明要評(píng)估的聚類結(jié)果質(zhì)量比較好。相反地，就說明要評(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開始，往后依次是1, 2, …, k-1。定義CI_i為第i個(gè)元素所屬的簇標(biāo)號(hào)。比如CI₃=2表示第3個(gè)元素屬于標(biāo)號(hào)為2的簇。

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

算法1 Shuffle(CI, n)

for i← 0 to n-1 do

index ← rand() mod (i + 1)

swap(CI_i, CI_indexCI_i, CI_index)

可以用數(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ù)值x₀與樣本的函數(shù)值x₁, x₂, …，x_N。有了這些值就能計(jì)算p-value了。具體算法如下。

算法2 ECP1

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

for i ← 1 to N do

Shuffle(CI, n)

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

計(jì)算p-value

一般情況下k$ \ll $n，因此 DB-Index的復(fù)雜度為O(n×d)。抽樣一次的復(fù)雜度是O(n)，容易算出總體復(fù)雜度為O(N×n×d)。這個(gè)復(fù)雜度還是比較高的。所以需要想一些方法來降低復(fù)雜度。N是抽樣次數(shù)，期望越大越好?？梢钥吹紻B-Index是影響復(fù)雜度的主要因素。如果降低DB-Index計(jì)算的復(fù)雜性，那么就可以在相同的時(shí)間內(nè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ù)值。接下來繼續(xù)交換一對(duì)簇標(biāo)號(hào)不同的元素的簇標(biāo)號(hào)，交換后計(jì)算DB-Index的值。這樣迭代N次后就會(huì)得到N個(gè)樣本的函數(shù)值。利用這N個(gè)值就可以計(jì)算出p-value。整個(gè)算法流程如下。

算法3 ECP2

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

for i← 1 to N do

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

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

計(jì)算p-value

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

${\text{DBI}} = \frac{1}{k}\sum\limits_{i = 1}^k {\max \left( {\frac{{{S_i} + {S_j}}}{{{D_{ij}}}}} \right)} .$

由S_i的定義可以得出:

${S_i} = \sqrt {\frac{{\sum\nolimits_{j = 1}^{{m_i}} {{{\left\| {{z_j} - \bar z} \right\|}^2}} }}{{{m_i}}}} .$

式中m_i是簇zi中元素的數(shù)目。z_j是簇i中第j個(gè)元素的屬性向量，${\bar z}$是簇i質(zhì)心的屬性向量。由于數(shù)據(jù)是d維的，所以‖z_j-${\bar z}$‖²就是各個(gè)維度的平方和。因此可以單獨(dú)對(duì)每一維計(jì)算，然后再把所有維度的平方相加即可:

$\sum\nolimits_{j = 1}^{{m_i}} {{{\left\| {{z_j} - \bar z} \right\|}^2}} = \sum\nolimits_{t = 1}^d {\sum\nolimits_{j = 1}^{{m_i}} {{{\left( {{a_{jt}} - {{\bar a}_t}} \right)}^2}} } , $

式中:a_jt是簇i中第j個(gè)元素的第t個(gè)屬性值, a_t是簇i質(zhì)心的第t個(gè)屬性值。下面直接討論第t維的計(jì)算方法:

$\begin{gathered} \frac{{\sum\nolimits_{j = 1}^{{m_i}} {{{\left\| {{z_j} - \bar z} \right\|}^2}} }}{{{m_i}}} = \frac{{\sum\nolimits_{t = 1}^d {\sum\nolimits_{j = 1}^{{m_i}} {{{\left( {{a_{jt}} - {{\bar a}_t}} \right)}^2}} } }}{{{m_i}}} = \hfill \\ \sum\nolimits_{t = 1}^d {\frac{{\sum\nolimits_{j = 1}^{{m_i}} {{{\left( {{a_{jt}} - {{\bar a}_t}} \right)}^2}} }}{{{m_i}}}} \hfill \\ \end{gathered} $

其中:

$\frac{{\sum\nolimits_{j = 1}^{{m_i}} {{{\left( {{a_{jt}} - {{\bar a}_t}} \right)}^2}} }}{{{m_i}}} = \frac{{\sum\nolimits_{j = 1}^{{m_i}} {{a_{jt}}^2} }}{{{m_i}}} - {{\bar a}_t}^2$

因此

$\frac{{\sum\nolimits_{j = 1}^{{m_i}} {{{\left\| {{z_j} - \bar z} \right\|}^2}} }}{{{m_i}}} = \sum\nolimits_{t = 1}^d {\frac{{\sum\nolimits_{j = 1}^{{m_i}} {{a_{jt}}^2} }}{{{m_i}}}} - {{\bar a}_t}^2$

${\sum\nolimits_{j = 1}^{{m_i}} {{a_{jt}}^2} }$是簇i中所有元素中第t維的平方和，${{\bar a}_t}$是簇i中所有元素第t維的平均值。所以為了計(jì)算S_i，每一維只需要維護(hù)兩個(gè)值就可以了:平方和與平均值。當(dāng)簇標(biāo)號(hào)交換的話，能在O(1)復(fù)雜度內(nèi)修正這兩個(gè)值。修改完每個(gè)維度的這兩個(gè)值后，就可以用DB-Index算出函數(shù)值了。

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

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

上邊提到計(jì)算DB-Index的方法的復(fù)雜度為O(k×k×d)。雖然相比于原先的計(jì)算方法已經(jīng)優(yōu)化很多，但是對(duì)于p-value非常小的情況，可能依舊由于抽樣數(shù)目有限而無法算出精確的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ī)劃分無窮次。那么質(zhì)量特別高的劃分的比例會(huì)很小。同樣的，質(zhì)量極端差的劃分占的比例也會(huì)很小。很大比重的劃分都介于它們之間。而正態(tài)分布的特點(diǎn)是：極端概率很小，中間的概率很大。經(jīng)過對(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)得到：

$\mu = \frac{{\sum\nolimits_{i = 1}^N {{x_i}} }}{N}$

(1)

$\partial = \sqrt {\frac{{{{\left( {{x_i} - \bar x} \right)}^2}}}{{N - 1}}} $

(2)

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

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

本文利用公式P_perm0$\frac{{\sum\limits_{n = 1}^N {I\left( {{y_n} > {x_0}} \right)} }}{N}$計(jì)算p-value實(shí)際上是利用了大數(shù)定律。大數(shù)定律的本質(zhì)是如果有無窮次試驗(yàn)，事件出現(xiàn)的頻率就會(huì)無限趨近于事件發(fā)生的概率。而由于抽樣次數(shù)有限，本文假設(shè)了DB-Index的函數(shù)值符合正態(tài)分布。不過對(duì)于抽樣N次后發(fā)現(xiàn)，已經(jīng)有足夠的樣本可以精確算出p-value的話，就不需要用正態(tài)分布計(jì)算了。然而如果抽樣N次后沒有足夠的樣本可以用大數(shù)定律精確地計(jì)算p-value的話就要擬合正態(tài)概率分布函數(shù)了。對(duì)于有多少個(gè)樣本滿足x_i≤x₀算是足夠呢？這是一個(gè)閾值問題。上邊的過程總結(jié)起來如算法4。

算法4 ECP

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

統(tǒng)計(jì)x_i≤x₀的數(shù)目M

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

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

其中Limit是ECP的一個(gè)參數(shù)，是用P_perm0計(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ù)集都來自UCI數(shù)據(jù)庫(kù)^[15]。iris、wine和yeast數(shù)據(jù)集的屬性都是數(shù)值型的，并且這3個(gè)數(shù)據(jù)集都帶有類標(biāo)簽。

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

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

表 1 不同聚類方法的p-value, f-score, accuracyTable 1 The p-value, f-score, accuracy of different cluster algorithms

數(shù)據(jù)	算法	p-value	f-score	accuracy
Iris	Random	0.456 254	1.134 140	0.380 000
	Hierarchical Clustering	0.100 548	1.656 570	0.666 667
	DBSCAN	0.042 825	2.714 400	0.906 667
	k-means	0.042 751	2.655 840	0.886 667
Wine	Random	0.559 588	1.095 420	0.410 112
	Hierarchical Clustering	0.001 574	1.666 460	0.657 303
	DBSCAN	1.892 991e-05	2.833 750	0.943 820
	k-means	1.818 384e-05	2.832 200	0.943 820
Yeast	Random	0.688 145	1.078 260	0.357 198
	Hierarchical Clustering	0.003 871	0.835 371	0.360 277
	DBSCAN	0.000 711	1.304 800	0.434 950
	k-means	7.544 556 e-05	1.881 950	0.480 370

表選項(xiàng)

針對(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é)果可以看出用本文方法算出來的p-value是可靠的。需要注意的是yeast的數(shù)據(jù)集簇結(jié)構(gòu)比較明顯，聚類的結(jié)果比較集中。

圖 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

圖選項(xiàng)

圖 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

圖選項(xiàng)

圖 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

圖選項(xiàng)

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)?em>k越大，對(duì)數(shù)據(jù)集劃分得越細(xì)，同一個(gè)簇內(nèi)的元素就會(huì)越相似，p-value自然就會(huì)越小。然而劃分的越細(xì)并不意味著就一定越好。舉個(gè)極端的例子，將一個(gè)數(shù)據(jù)量為n的數(shù)據(jù)集劃分成n 個(gè)簇是毫無意義的。

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

$R\left( i \right) = \frac{{p\left( {i - 1} \right)}}{{p\left( i \right)}},$

式中：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最大，以此來確定簇的數(shù)目為4。而事實(shí)上yeast的類別數(shù)目就是4。

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

表 2 不同k下的p-valueTable 2 The p-value of clusters for different k

數(shù)據(jù)	2	3	4	5	6	7
Iris	0.108 518	0.042 742	0.020 435	0.017 261	0.006 991	0.003 208
Wine	0.001 946	1.988 773e-05	7.579 904e-07	2.381 891e-08	2.125 773e-09	1.537 855e-09
Yeast	0.006 911	0.001 040	6.937 873e-05	9.647 412e-06	1.327 582e-06	3.264 579e-06

表選項(xiàng)

表 3 不同k下的R(k)Table 3 The R(k) of clusters for different k

數(shù)據(jù)	3	4	5	6	7
Iris	2.538 900	2.091 640	1.183 870	2.469 150	2.179 010
Wine	97.836 510	26.237 440	31.823 050	11.204 820	1.382 300
Yeast	6.644 860	14.991 890	7.191 430	7.266 900	0.406 660

表選項(xiàng)

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

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

圖選項(xiàng)

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

圖選項(xiàng)

實(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.1 ECP與最大熵模型比較

本文重復(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。這兩者差距比較大，這說明將最大熵方法擬合成正態(tài)分布是不合適的。這一實(shí)驗(yàn)說明利用ECP評(píng)估聚類結(jié)果更為可靠。

4.3.2 ECP與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ì)算的f₁為2和1.8，SigClust算出的p-value都是0，沒有區(qū)分開這2個(gè)不同劃分的質(zhì)量。同樣地iris數(shù)據(jù)集f₁為1.36和1.158 65，SigClust算出的p-value都為1。實(shí)驗(yàn)可以看出ECP能很好地區(qū)分聚類質(zhì)量的差距。因此，與SigClust相比，ECP不僅能處理k>2的情況，而且能更好地評(píng)估聚類質(zhì)量。

表 4 ECP與最大熵方法對(duì)比Table 4 The comparison of ECP and maximum entropy method

算法	iris	wine	yeast
最大熵	0.001	0.001	0.001
最大熵擬合正態(tài)	4.891 817e-05	0.370 035 2	0.002 626 655
ECP	0.042 742 13	1.988 773e-05	6.937 873e-05

表選項(xiàng)

表 5 ECP與Sigclust對(duì)比Table 5 The comparison of ECP and Sigclust

數(shù)據(jù)	p-value/ECP	p-value/Sigclust Sigclust	f-score	accuracy
Iris	0.114 572 8	0	2	1
	0.121 688 1	0	1.8	0.9
	0.157 168 9	1	1.36	0.68
	0.228 296 5	1	1.158 65	0.58
wine	0.001 534 783	0	1.876 81	0.938 462
	0.002 878 496	0.199 2	1.673 66	0.838 462
	0.006 082 356	1	1.430 74	0.715 385
	0.221 656	1	1.011 64	0.546 154
yeast	0.006 761 993	0	1.130 05	0.567 265
	0.010 775 1	1	1.077 86	0.539 238
	0.012 549 87	1	1.073 48	0.536 996
	0.256 406 2	1	1.044 03	0.522 422

表選項(xiàng)

4.3.3 ECP與ECP1對(duì)比

這一部分說明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倍?？梢奅CP在效率上有質(zhì)的提升。

表 6 ECP與ECP1效率對(duì)比Table 6 The comparison of ECP and ECP1

算法	iris	wine	yeast
ECP1	18 s	50 s	56s
ECP	1109 s	734 s	280 m

表選項(xiàng)

5 結(jié)束語

本文提出了一種新的基于置換檢驗(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é)果來看，ECP對(duì)評(píng)估聚類結(jié)果有很好的效果，并且具有很強(qiáng)的實(shí)用性。

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自：醫(yī)學(xué)數(shù)據(jù)科學(xué) > 《數(shù)據(jù)科學(xué)》

舉報(bào)/認(rèn)領(lǐng)