隨著獲得的數(shù)據(jù)越來越多，利用機器學習、數(shù)據(jù)挖掘[
1,
2,
3]等手段從數(shù)據(jù)中獲取潛在的知識變得越來越重要。然而如何評估挖掘出來的信息，即評估數(shù)據(jù)挖掘結果的質(zhì)量是一個十分重要的問題。只有一個好的評估方法，才能保證挖掘算法發(fā)現(xiàn)高質(zhì)量的信息。聚類[
4,
5]是數(shù)據(jù)挖掘領域一個很重要的分支。同時，聚類的應用也越來越廣泛。隨著聚類的廣泛應用，如何有效地評估聚類結果的質(zhì)量[
6,
7]成為一個重要的研究課題。雖然評估聚類結果的重要性一點不亞于挖掘算法本身，但是評估方面卻沒有受到它應有的重視。
針對聚類，現(xiàn)有的方法主要是用評價函數(shù)對聚類結果評估。這種函數(shù)一般分3種類型：緊密型、分散型和連接型。常見的評估函數(shù)有DB-Index, Sihouette-Index, Dunn-Index等。這些函數(shù)能夠評估聚類結果，但是這些函數(shù)評估出來的結果往往沒有一個比較好的可以參考的值。即一個評估值計算出來之后得到的只是一個評估值，至于這個值達到什么標準能夠接受并不能確定。利用統(tǒng)計方法評估聚類結果的算法很少，其主要原因是聚類的特殊性與復雜性使傳統(tǒng)的統(tǒng)計方法很難用到聚類質(zhì)量評估上。近年來有一些利用隨機方法來評估聚類結果的研究，但也存在一定的問題。本文根據(jù)存在的問題提出了一種基于置換檢驗的評估方法。
1 相關研究1.1 利用簇結構評估聚類質(zhì)量
該方法先對原始數(shù)據(jù)聚類，然后將原始數(shù)據(jù)集按照一定的約束隨機置換抽樣構造新的數(shù)據(jù)集。抽樣之后用同樣的聚類算法對樣本數(shù)據(jù)集進行聚類。這樣重復大量的次數(shù)后，再用評估函數(shù)(如DB-Index)計算每個樣本的函數(shù)值。如果原始數(shù)據(jù)集聚類結果的函數(shù)值小于大部分隨機構造的數(shù)據(jù)集聚類結果的函數(shù)值，那么說明挖掘出來的信息是可靠的，否則說明聚類結果不可靠。更通俗一點，如果原來數(shù)據(jù)集沒有好的簇結構，那么無論怎么聚類，結果都是不好的。代表性的方法有最大熵模型抽樣[
8]、矩陣元素交換[
9]等。利用數(shù)據(jù)集簇結構來評估聚類質(zhì)量[
10]的方法能很好地評估出簇結構不好的聚類結果。實驗證實對不同數(shù)據(jù)集進行聚類，有明顯簇結構數(shù)據(jù)集的p-value會比沒有明顯簇結構的p-value小很多。但是這種方法并不能準確評估聚類的質(zhì)量。從某種意義上講，這種方法更適合評估一個數(shù)據(jù)集是否有好的簇結構。
1.2 SigClust
SigClust[
11]認為如果一個數(shù)據(jù)集符合高斯分布，那么對這個數(shù)據(jù)集的任何分割都是不合理的。因此這個方法的前提假設是：一個單一的簇的元素符合高斯分布。SigClust主要是針對k=2的聚類評估。對于k>2的情況，還沒有比較好的解決辦法。
1.3 層次聚類的p-value計算
這種方法主要針對層次聚類的評估[
12,
13]。層次聚類后會形成一個二叉樹。對二叉樹上的每個節(jié)點都進行置換檢驗，算出每個節(jié)點劃分對應的p-value。這種算法的空假設為：當前節(jié)點的左子樹和右子樹應該屬于一個簇。如果算出p-value 足夠小就說明空假設是一個小概率事件，應該拒絕。該方法是將當前節(jié)點的左子樹和右子樹打亂，按照一定的約束隨機分配左子樹和右子樹的元素。抽樣若干次后形成的隨機樣本集按照某種指標與原始劃分對比計算出p-value。這個評估只能針對層次聚類，不能對其他的聚類算法進行評估。另外這樣計算出的p-value只是每個節(jié)點上的p-value, 并不是全局聚類的p-value。
2 基本概念2.1 無監(jiān)督聚類質(zhì)量評估函數(shù)
如果數(shù)據(jù)集中的元素沒有類標簽，聚類結果的評價就只能依賴數(shù)據(jù)集自身的特征和量值。在這種情況下，聚類的度量追求有3個目標：緊密度、分離度和鏈接度。
緊密度 簇中的每個元素應該彼此盡可能接近。緊密度的常用度量是方差，方差越小說明緊密度越大。
分離度 簇與簇之間應該充分分離。有3種常用方法來度量兩個不同簇之間的距離。單連接：度量不同簇的兩個最近成員的距離。全連接：度量不同簇的兩個最遠成員的距離。質(zhì)心比較：度量不同簇的中心點的距離。
鏈接度 鏈接度指簇中的元素成員至少要跟同一個簇內(nèi)的元素比較像。這個可以用來評估簇模型不是圓形或者球形的聚類結果，比如DBSCAN的聚類結果。
本文用一種無監(jiān)督評估聚類質(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)} .$
式中：Si表示第i個簇內(nèi)的元素與質(zhì)心的標準方差，Dij表示第i個簇與第j個簇質(zhì)心間的歐幾里德距離，k表示簇的數(shù)目。
DBI的思想是一個高質(zhì)量的聚類結果需要滿足:同一個簇的各元素間相似度大，不同類之間的相似度小。在DBI中，分子越小意味著簇內(nèi)元素相似度越大，分母越大意味著簇間相似度越小。
2.2 聚類評估的p-value
給一個數(shù)據(jù)集X，用DB-Index計算聚類結果的函數(shù)值為x0x0。數(shù)據(jù)集X所有可能的聚類結果的函數(shù)值為x1, x2, …xNall。置換檢驗的p-value定義為
${P_{perm}} = \frac{{\sum\nolimits_{n = 1}^{{N_{{\text{all}}}}} {I\left( {{x_n} ≤ {x_0}} \right)} }}{{{N_{{\text{all}}}}}}$
式中I是一個邏輯函數(shù)。當xn≤x0的情況下為1，否則為0。由于要枚舉出所有的聚類方案的復雜度是指數(shù)級別的，所以需要采取其他的策略。抽樣出所有情況的一個子集Y，并計算子集Y中所有元素的函數(shù)值為x1, x2, …xN, 其中N$ \ll $Nall。這時候置換檢驗的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的理由是把x0也看作置換檢驗一個樣本的函數(shù)值。這就避免了得到p-value為0的試驗結果。然而這種做法事實上是不太合理的。試想如果抽樣999次沒有發(fā)現(xiàn)比x0更小的統(tǒng)計值，這樣草率地得出結論當前置換檢驗的結果為0.001顯然太武斷了。因為可能抽樣99 999次依舊沒有比x0更優(yōu)的樣本。那么依照這個計算公式p-value又為0.000 01。而實際上p-value的值可能更小。因此本文把p-value的定義為Pperm0Pecdf0。
置換檢驗的準確性取決于抽樣的數(shù)目，一般的置換檢驗抽樣的次數(shù)都在1 000次以上。為了得到更精確的p-value抽樣的次數(shù)越多越好，理想的情況是置換所有的可能。然而對于不同的數(shù)據(jù)集合，甚至很難預測需要執(zhí)行多少次置換才能夠得到比較好的結果。往往為了得到更精確的值就會增大抽樣次數(shù)，但是增加抽樣次數(shù)的代價是增加計算的復雜性。對于普通的數(shù)據(jù)集往往抽樣次數(shù)達到10 000次之后就不太容易提高抽樣次數(shù)。而這樣做又產(chǎn)生出了一個問題。如果一個聚類結果真實的p-value為0.000 001。而抽樣的次數(shù)只有10 000次的話，那么p-value為就為0了。針對這些問題，本文提出了一種新的聚類評估方法，ECP，該方法能比較好地解決上文提到的問題。
3 基于置換檢驗的聚類結果評估3.1 基本思想
本文提出的置換檢驗方法將關注點鎖定在了聚類的結果上。評估聚類結果的本質(zhì)是看聚類算法對數(shù)據(jù)集中元素的劃分質(zhì)量。從這個角度出發(fā)，可以枚舉對數(shù)據(jù)集的劃分，然后用評估函數(shù)算出枚舉劃分的函數(shù)值。如果絕大部分劃分都沒有要評估的聚類結果質(zhì)量好的話，那么就說明要評估的聚類結果質(zhì)量比較好。相反地，就說明要評估的聚類結果質(zhì)量并不好。
因此對于一個聚類結果，本文定義了零假H0: 當前聚類結果不是一個高質(zhì)量的聚類。然后計算這個零假設的p-value。如果這個p-value非常小，就認為這個劃分結果可以接受，可以拒絕H0。否則認為這個聚類結果不能接受。
定義數(shù)據(jù)集X是一個包含n個元素的d維數(shù)值型矩陣。首先對數(shù)據(jù)集聚類，聚成k簇后每個元素都會歸屬于一個簇。我們對每個簇進行標號。標號從0開始，往后依次是1, 2, …, k-1。定義CIi為第i個元素所屬的簇標號。比如CI3=2表示第3個元素屬于標號為2的簇。
接下來是抽樣。抽樣要滿足一定約束。本文定義的約束是: 樣本中簇包含元素的數(shù)目要與待評估聚類結果中簇中元素的數(shù)目保持一致。舉個例子，假設數(shù)據(jù)集元素數(shù)目n為 100。劃分成3簇，劃分簇中的數(shù)目分別是40、33、27。那么抽樣出來的樣本也要滿足這些條件，也就是要劃分成3簇，并且簇中元素的數(shù)目也必須是40、33、27。具體的抽樣方法: 首先搜集所有元素的簇標號，然后將這些簇標號隨機地分配給每個元素。其實這個過程是洗牌算法。算法1描述了抽樣的過程。
算法1 Shuffle(CI, n)
for i← 0 to n-1 do
index ← rand() mod (i + 1)
swap(CIi, CIindexCIi, CIindex)
可以用數(shù)學歸納法進行證明算法1保證了每個元素獲得同一簇標號的概率是一樣的。抽樣的復雜度為O(n)。這樣進行抽樣N次，就得到了N個樣本。然后利用樣本對原始聚類結果進行評估。用DB-Index算出原始聚類的函數(shù)值x0與樣本的函數(shù)值x1, x2, …，xN。有了這些值就能計算p-value了。具體算法如下。
算法2 ECP1
用DB-Index計算聚類結果的函數(shù)值x0。
for i ← 1 to N do
Shuffle(CI, n)
用DB-Index計算樣本的函數(shù)值xi
計算p-value
一般情況下k$ \ll $n，因此 DB-Index的復雜度為O(n×d)。抽樣一次的復雜度是O(n)，容易算出總體復雜度為O(N×n×d)。這個復雜度還是比較高的。所以需要想一些方法來降低復雜度。N是抽樣次數(shù)，期望越大越好?？梢钥吹紻B-Index是影響復雜度的主要因素。如果降低DB-Index計算的復雜性，那么就可以在相同的時間內(nèi)抽取更多的樣本來提高p-value的準確度。本文發(fā)現(xiàn)了DB-Index公式的特點，對上文提到的算法做了改進。
3.2 加速技巧
首先選取聚類結果作為初始狀態(tài)。然后隨機交換一對簇標號不同的元素的簇標號。交換后把此時的劃分作為一個樣本，直接計算DB-Index的函數(shù)值。接下來繼續(xù)交換一對簇標號不同的元素的簇標號，交換后計算DB-Index的值。這樣迭代N次后就會得到N個樣本的函數(shù)值。利用這N個值就可以計算出p-value。整個算法流程如下。
算法3 ECP2
用DB-Index計算聚類結果的函數(shù)值x0
for i← 1 to N do
隨機交換一對簇標號不同元素的簇標號
用DB-Index計算抽樣結果的函數(shù)值 xi
計算p-value
對比ECP1，ECP2只是修改了第3步的抽樣方法。為什么修改了抽樣方法就可以增大抽樣次數(shù)？下面將仔細討論DB-Index的計算過程。DB-Index的計算公式為
${\text{DBI}} = \frac{1}{k}\sum\limits_{i = 1}^k {\max \left( {\frac{{{S_i} + {S_j}}}{{{D_{ij}}}}} \right)} .$
由Si的定義可以得出:
${S_i} = \sqrt {\frac{{\sum\nolimits_{j = 1}^{{m_i}} {{{\left\| {{z_j} - \bar z} \right\|}^2}} }}{{{m_i}}}} .$
式中mi是簇zi中元素的數(shù)目。zj是簇i中第j個元素的屬性向量，${\bar z}$是簇i質(zhì)心的屬性向量。由于數(shù)據(jù)是d維的，所以‖zj-${\bar z}$‖2就是各個維度的平方和。因此可以單獨對每一維計算，然后再把所有維度的平方相加即可:
$\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}} } , $
式中:ajt是簇i中第j個元素的第t個屬性值, at是簇i質(zhì)心的第t個屬性值。下面直接討論第t維的計算方法:
$\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維的平均值。所以為了計算Si，每一維只需要維護兩個值就可以了:平方和與平均值。當簇標號交換的話，能在O(1)復雜度內(nèi)修正這兩個值。修改完每個維度的這兩個值后，就可以用DB-Index算出函數(shù)值了。
可以看出修改一個簇的平方和與平均值復雜度是O(d)的。因此DB-Index的計算復雜度就是O(k×k×d)了。沒有加速的DB-Index的計算復雜度是O(n×d)。一般情況下，k$ \ll $n。所以這種方法的效率有明顯的提升。
3.3 更準確的p-value
上邊提到計算DB-Index的方法的復雜度為O(k×k×d)。雖然相比于原先的計算方法已經(jīng)優(yōu)化很多，但是對于p-value非常小的情況，可能依舊由于抽樣數(shù)目有限而無法算出精確的p-value。這種情況下算出的p-value就會為0，然而這樣的結果是不準確的。
如果知道了樣本DB-Index函數(shù)值的概率分布就可以根據(jù)原始聚類結果的函數(shù)值算出精確的p-value了[
14]。聚類是一種半監(jiān)督的機器學習，其本質(zhì)對元素所屬類別的劃分。如果對元素隨機劃分無窮次。那么質(zhì)量特別高的劃分的比例會很小。同樣的，質(zhì)量極端差的劃分占的比例也會很小。很大比重的劃分都介于它們之間。而正態(tài)分布的特點是：極端概率很小，中間的概率很大。經(jīng)過對數(shù)據(jù)的分析，聚類劃分的DB-Index函數(shù)值比較符合正態(tài)分布。因此可以假設抽樣樣本DB-Index的函數(shù)值符合正態(tài)分布。實際上正態(tài)分布符合很多自然概率分布的指標。下面要做的就是得到正態(tài)分布的參數(shù)。對于一維的正態(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ù)，就能將原始聚類結果x0代入概率分布算出p-value了。
這樣估出概率分布函數(shù)實現(xiàn)了在整體復雜度沒有增加的前提下用較少的抽樣得到更為精確p-value的目的了。
本文利用公式Pperm0$\frac{{\sum\limits_{n = 1}^N {I\left( {{y_n} > {x_0}} \right)} }}{N}$計算p-value實際上是利用了大數(shù)定律。大數(shù)定律的本質(zhì)是如果有無窮次試驗，事件出現(xiàn)的頻率就會無限趨近于事件發(fā)生的概率。而由于抽樣次數(shù)有限，本文假設了DB-Index的函數(shù)值符合正態(tài)分布。不過對于抽樣N次后發(fā)現(xiàn)，已經(jīng)有足夠的樣本可以精確算出p-value的話，就不需要用正態(tài)分布計算了。然而如果抽樣N次后沒有足夠的樣本可以用大數(shù)定律精確地計算p-value的話就要擬合正態(tài)概率分布函數(shù)了。對于有多少個樣本滿足xi≤x0算是足夠呢？這是一個閾值問題。上邊的過程總結起來如算法4。
算法4 ECP
抽樣N次，算出每次的函數(shù)值xi
統(tǒng)計xi≤x0的數(shù)目M
如果M≥Limit利用公式Pperm0計算p-value
否則，擬合正態(tài)概率分布算出p-value
其中Limit是ECP的一個參數(shù)，是用Pperm0計算出p-value的最低數(shù)目限制。ECP不同于很多其他的置換檢驗方法。這種方法實現(xiàn)了用較少的抽樣計算出更為精確p-value的目的，在效率上有了非常大的飛躍。
4 實驗
實驗選取了iris、wine和yeast等3個數(shù)據(jù)集。這3個數(shù)據(jù)集都來自UCI數(shù)據(jù)庫[
15]。iris、wine和yeast數(shù)據(jù)集的屬性都是數(shù)值型的，并且這3個數(shù)據(jù)集都帶有類標簽。
4.1 利用p-value選擇合適的聚類算法
從聚類這個概念提出以來出現(xiàn)了很多聚類算法。對于一個具體的應用，選擇合適的聚類算法是一個很重要的問題。本文認為對于同一個數(shù)據(jù)集用不同的算法聚類，p-value小的那個結果更為可靠。為此本文對同一數(shù)據(jù)集選用多種算法聚類來驗證p-value對選擇聚類算法的有效性。實驗結果如表 1。從實驗結果可以看出，對于同一數(shù)據(jù)集p-value小的聚類算法對應的f-score和accuracy比較大。這說明利用p-value選擇聚類算法是可靠的。本文還計算了p-value與f-score和accuracy的相關系數(shù)。本文用k-means對同一數(shù)據(jù)集聚類100次。通過控制k-means 的迭代次數(shù)來控制劃分的質(zhì)量。這樣就避免了正常k-means聚類只會出現(xiàn)若干個固定情況的問題。
表 1 不同聚類方法的p-value, f-score, accuracyTable 1 The p-value, f-score, accuracy of different cluster algorithms
數(shù)據(jù)算法p-valuef-scoreaccuracy
IrisRandom0.456 2541.134 1400.380 000
Hierarchical Clustering0.100 5481.656 5700.666 667
DBSCAN0.042 8252.714 4000.906 667
k-means0.042 7512.655 8400.886 667
WineRandom0.559 5881.095 4200.410 112
Hierarchical Clustering0.001 5741.666 4600.657 303
DBSCAN1.892 991e-052.833 7500.943 820
k-means1.818 384e-052.832 2000.943 820
YeastRandom0.688 1451.078 2600.357 198
Hierarchical Clustering0.003 8710.835 3710.360277
DBSCAN0.000 7111.304 8000.434 950
k-means7.544 556 e-051.881 9500.480 370
表選項針對iris數(shù)據(jù)集，利用ECP計算出的p-value與f-score的相關系數(shù)為-0.578 018，與accuracy的相關系數(shù)為-0.699 331。具體的結果如圖 1。針對wine數(shù)據(jù)集，利用ECP計算得到的p-value與f-score的相系數(shù)為-0.535 734，與accuracy的相關系數(shù)為-0.538 754。具體的結果為圖 2。對于yeast數(shù)據(jù)集，利用ECP計算得到的p-value與f-score的相關系數(shù)為-0.500 340，與accuracy的相關系數(shù)為-0.167 325。具體結果為圖 3。
從實驗結果可以看出用本文方法算出來的p-value是可靠的。需要注意的是yeast的數(shù)據(jù)集簇結構比較明顯，聚類的結果比較集中。
圖 1 Iris數(shù)據(jù)集p-value與f-score和accuracy的關系Fig. 1 The relationship between p-value and f-score, accuracy of iris dataset
圖 2 Wine數(shù)據(jù)集p-value與f-score和accuracy的關系Fig. 2 The relationship between p-value and f-score, accuracy of wine dataset
圖 3 Yeast數(shù)據(jù)集p-value與f-score和accuracy的關系Fig. 3 The relationship between p-value and f-score, accuracy of yeast dataset
4.2 利用p-value決定數(shù)據(jù)集簇的數(shù)目k
很多聚類算法需要預先設定劃分數(shù)目k。本文研究了p-value與k的關系。對于同一數(shù)據(jù)集，選擇不同的k用k-means分別聚類，然后計算對應的p-value。計算結果如表 2。
從表 2中看出隨著k 的增加，p-value 的值變小。因為k越大，對數(shù)據(jù)集劃分得越細，同一個簇內(nèi)的元素就會越相似，p-value自然就會越小。然而劃分的越細并不意味著就一定越好。舉個極端的例子，將一個數(shù)據(jù)量為n的數(shù)據(jù)集劃分成n 個簇是毫無意義的。
本文研究了一種利用p-value 的變化幅度來確定k的新方法。這里給出一個定義:
$R\left( i \right) = \frac{{p\left( {i - 1} \right)}}{{p\left( i \right)}},$
式中：p(i-1)是當k取i-1時聚類結果的p-value，p (i)是當k取i時的聚類結果的p-value。R(i)的意義是當k增加1時p-value的變化幅度。將表 2的結果按照公式計算的結果如表 3。
由實驗結果可以看出，對于iris數(shù)據(jù)集，當k取3的時候，R(3) = 2.538 900最大。事實上iris的類別數(shù)目就是3。接著看wine數(shù)據(jù)集，當i取3的時候R(3)= 97.836 510最大。真實情況wine的類別數(shù)目就是3。對于yeast數(shù)據(jù)集當i取4的時候R(4)= 14.991 890最大，以此來確定簇的數(shù)目為4。而事實上yeast的類別數(shù)目就是4。
利用本文提出的定義能正確算出數(shù)據(jù)集中的簇數(shù)目k。因此可以說明計算聚類的p-value對于確定聚類數(shù)目k也是有一定意義的。不過對于R(i)這個定義還存在一定的問題。根據(jù)R的定義，i的取值不小于3。因此對于簇數(shù)目為2的情況還不能夠做出合適的處理。
表 2 不同k下的p-valueTable 2 The p-value of clusters for different k
數(shù)據(jù)234567
Iris0.108 5180.042 7420.020 4350.017 2610.006 9910.003 208
Wine0.001 9461.988 773e-057.579 904e-072.381 891e-082.125 773e-091.537 855e-09
Yeast0.006 9110.001 0406.937 873e-059.647 412e-061.327 582e-063.264 579e-06
表選項表 3 不同k下的R(k)Table 3 The R(k) of clusters for different k
數(shù)據(jù)34567
Iris2.538 9002.091 6401.183 8702.469 1502.179 010
Wine97.836 51026.237 44031.823 05011.204 8201.382 300
Yeast6.644 86014.991 8907.191 4307.266 9000.406 660
表選項研究了對于iris、wine和yeast數(shù)據(jù)集需要多少樣本能保證p-value不會因樣本數(shù)目的增加而改變。對于每個數(shù)據(jù)集用不同數(shù)目樣本計算p-value，結果如圖 5。
圖 4 p-value 穩(wěn)定性Fig. 4 The stability of p-value
圖 5 p-value與抽樣次數(shù)的關系Fig. 5 The relationship between p-value and the number of samples
實驗最多抽取1 000 000個樣本。對于這3個數(shù)據(jù)集，當抽樣數(shù)目達10 000時p-value就基本穩(wěn)定了。這一結果證實該方法具有很強的可行性。
4.3 與相關算法對比4.3.1 ECP與最大熵模型比較
本文重復了最大熵模型的評估方法，這3個數(shù)據(jù)集算出的p-value都為1/N。這是因為樣本太少，算法把原始聚類結果也當做一個樣本。前文分析了這種做法的不合理性。利用ECP就可以避免這樣的情況。除此之外，本文也嘗試將最大熵方法的抽樣評估值擬合出正態(tài)分布。實驗結果如表 4。從實驗結果可以看出，對于wine數(shù)據(jù)集，最大熵方法算出的p-value為0.001，擬合正態(tài)后的p-value為0.370 035 2。這兩者差距比較大，這說明將最大熵方法擬合成正態(tài)分布是不合適的。這一實驗說明利用ECP評估聚類結果更為可靠。
4.3.2 ECP與SigClust對比
SigClust算法是主要針對k為2聚類結果的評估。本文從每個數(shù)據(jù)集中選出了兩類用k-means進行聚類(比如iris數(shù)據(jù)集中選出了Setosa、Versicolour兩類進行對比)。為了讓聚類質(zhì)量有層次的差距，對k-means的聚類結果進行不同程度的破壞。破壞的程度越大，聚類的質(zhì)量越差。實驗結果如表 5。從實驗看SigClust與ECP都能夠區(qū)別出很好和很差的聚類。但是可以很明顯地看出，SigClust對聚類質(zhì)量的區(qū)分度不夠大。比如對于iris數(shù)據(jù)集計算的f1為2和1.8，SigClust算出的p-value都是0，沒有區(qū)分開這2個不同劃分的質(zhì)量。同樣地iris數(shù)據(jù)集f1為1.36和1.158 65，SigClust算出的p-value都為1。實驗可以看出ECP能很好地區(qū)分聚類質(zhì)量的差距。因此，與SigClust相比，ECP不僅能處理k>2的情況，而且能更好地評估聚類質(zhì)量。
表 4 ECP與最大熵方法對比Table 4 The comparison of ECP and maximum entropy method
算法iriswineyeast
最大熵0.0010.0010.001
最大熵
擬合正態(tài)4.891 817e-050.370 035 20.002 626 655
ECP0.042 742 131.988 773e-056.937 873e-05
表選項表 5 ECP與Sigclust對比Table 5 The comparison of ECP and Sigclust
數(shù)據(jù)p-value/ECPp-value/Sigclust Sigclustf-scoreaccuracy
Iris0.114 572 8021
0.121 688 101.80.9
0.157 168 911.360.68
0.228 296 511.158 650.58
wine0.001 534 78301.876 810.938 462
0.002 878 4960.199 21.673 660.838 462
0.006 082 35611.430 740.715 385
0.221 65611.011 640.546 154
yeast0.006 761 99301.130 050.567 265
0.010 775 111.077 860.539 238
0.012 549 8711.073 480.536 996
0.256 406 211.044 030.522 422
表選項4.3.3 ECP與ECP1對比
這一部分說明ECP比加速的ECP1在效率上有很大提高。ECP1是未加速的ECP算法。本文將這兩種算法進行了效率上的對比。實驗結果如表 6。實驗分別用兩種算法抽樣100 000次并得到對應的統(tǒng)計值?？梢钥闯觯瑢τ趇ris數(shù)據(jù)集，ECP比ECP1快了60倍。可見ECP在效率上有質(zhì)的提升。
表 6 ECP與ECP1效率對比Table 6 The comparison of ECP and ECP1
算法iriswineyeast
ECP118 s50 s56s
ECP1109 s734 s280 m
表選項5 結束語
本文提出了一種新的基于置換檢驗的聚類結果評估方法ECP。為了增大抽樣的數(shù)目，利用DB-Index的計算特點減小了對樣本函數(shù)值計算的復雜度。為了得到更精確的p-value，根據(jù)聚類劃分的特點，假設了DB-Index的函數(shù)值是符合高斯分布的，進而可以用較少的抽樣估出更為準確的p-value。從實驗的結果來看，ECP對評估聚類結果有很好的效果，并且具有很強的實用性。
