如何確定多少個簇？聚類算法中選擇正確簇數(shù)量的三種方法

taotao_2016 2022-02-14

展開全文

聚類是一種無監(jiān)督機器學習方法,，可以從數(shù)據(jù)本身中識別出相似的數(shù)據(jù)點,。對于一些聚類算法，例如 K-means,，需要事先知道有多少個聚類,。如果錯誤地指定了簇的數(shù)量，則結果的效果就會變得很差（參見圖 1）,。

這種情況下,，s 變?yōu)樨摂?shù),，接近 -1。

在許多情況下,，不知道數(shù)據(jù)中有多少個簇,。但是弄清楚有多少簇可能是我們首先要執(zhí)行聚類操作的原因。如果有數(shù)據(jù)集相關的領域內(nèi)知識可能有助于確定簇的數(shù)量,。但是這假設需要知道目標類（或至少有多少類），而在無監(jiān)督學習中無法確認,，所以我們需要一種方法,，它可以在不依賴目標變量的情況下告訴我們簇的數(shù)量。

確定正確的簇數(shù)量的一種可能的解決方案是暴力測試的方法,。我們嘗試不同數(shù)量的簇的聚類算法,。然后找到最優(yōu)的聚類結果，但是這種方式的需要花費大量的資源,。在本文中,，我們首先介紹兩個流行的指標來評估簇質(zhì)量。然后介紹了三種方法來找到最佳簇數(shù)量：

肘部法 The elbow method
輪廓系數(shù)的優(yōu)化 The optimization of the silhouette coefficient
間隔量統(tǒng)計 The gap statistic

聚類結果的質(zhì)量

在使用不同的方法來確定最佳聚類數(shù)之前,，首先要了解如何定量評估聚類結果的質(zhì)量,。想象以下場景，相同的數(shù)據(jù)集分為三個簇（參見圖 2）,。左側的聚類定義良好,，而右側的聚類識別不佳。

這是為什么,？聚類的目標是對聚類中的數(shù)據(jù)點進行分組,，以便 (1) 聚類內(nèi)的點盡可能相似，(2) 屬于不同聚類的點盡可能不同,。這意味著,，在理想的聚類中，簇內(nèi)的變化很小,，而簇間的變化很大,。因此，一個好的聚類質(zhì)量度量應該能夠定量地總結（1）和/或（2）,。

一種這樣的質(zhì)量指標是inertia（慣性）,。這被計算為數(shù)據(jù)點與其所屬聚類中心之間的平方距離之和。inertia量化了簇內(nèi)的變化,。

另一個流行的指標是silhouette coefficient（輪廓系數(shù)）,，它試圖總結簇內(nèi)和簇間的變化。在每個數(shù)據(jù)點,，我們計算到該數(shù)據(jù)點所屬的聚類中心的距離（稱為a）,，以及到次優(yōu)聚類中心的距離（稱為b）。在這里，次好的簇是指不是當前數(shù)據(jù)點簇的最接近的簇,。然后基于這兩個距離 a 和 b,，該數(shù)據(jù)點的輪廓 s 計算為 s=(b-a)/max(a,b)。

在理想聚類下,，距離 a 與距離

一旦在所有數(shù)據(jù)點計算 s,，s 的平均值就確定了輪廓系數(shù)。可以為每個簇單獨計算輪廓系數(shù),，也可以為所有數(shù)據(jù)點計算輪廓系數(shù),。接近 1 的輪廓系數(shù)表明聚類算法能夠?qū)?shù)據(jù)劃分為分離良好的聚類。

肘部法則

inertia是簇數(shù) k 的遞減函數(shù),。它的下降速度在最佳聚類數(shù) K 上下是不同的,。當 k<K 時，inertia迅速下降,，而當 k>K 時,，inertia下降很慢。因此,，通過在 k 范圍內(nèi)繪制inertia,，可以確定曲線在 K 處彎曲或彎頭的位置。圖 4 顯示了圖 1 中示例的慣性圖,。我們可以清楚地看到彎曲或彎頭,，在 k = 6。所以我將inertia翻譯成了慣性是非常貼切的,。

這種方法有些主觀,，因為不同的人可能會在不同的位置識別肘部。在我們圖 4 的示例中,，有些人可能會爭辯說 k=4 是肘部,。此外，肘部可能并不總是很明顯,，我們將在后面看到,。

肘部法的用例可以在自然語言問題中看到，以使用 KNIME 分析平臺確定社交網(wǎng)絡中的最佳主題數(shù)量,。由于沒有 KNIME 節(jié)點來計算inertia,，因此在此示例中使用 Java Snippet 節(jié)點來計算inertia。這是用于計算inertia的代碼片段,。

// Initializing the sum of squaresout_sum_squares = 0.0;/*The first half of columns belong to features of the origin.The second half of columns belong to features of the terminus.The groups of columns have to be in the same order.*/int col_count = getColumnCount();int no_dimensions = col_count / 2;// Loop over the feature columnsfor(int i=0; i < no_dimensions; i++){/*Checking if the feature i from the origin andthe feature i from the terminus (i.e., i+no_dimensions)are not missing, and have similar column names*/if(!isMissing(i) && isType(i, tDouble)&& !isMissing(i+no_dimensions) && isType(i+no_dimensions, tDouble) &&getColumnName(i+no_dimensions).contains(getColumnName(i))){// Calculating the squared distance and adding it to the sumout_sum_squares += Math.pow(getCell(i, tDouble) - getCell(i+no_dimensions, tDouble), 2);}}

輪廓系數(shù)法

輪廓系數(shù)可以提供更客觀的方法來確定最佳聚類數(shù),。這是通過簡單地計算 k 范圍內(nèi)的輪廓系數(shù)并將峰值識別為最佳 K 來完成的。在 k 范圍內(nèi)執(zhí)行 K-Means 聚類,，找到產(chǎn)生最大輪廓系數(shù)的最佳 K,，并根據(jù)優(yōu)化的 K 將數(shù)據(jù)點分配給聚類,。圖 5 顯示了我們提供的示例數(shù)據(jù)中的輪廓系數(shù)圖示例如圖 1 所示，輪廓系數(shù)在 k=6 處達到峰值,，因此確定為最佳 K,。

間隔量統(tǒng)計

為了討論差距統(tǒng)計，讓我們考慮一個沒有任何聚類的隨機數(shù)據(jù)集的聚類,。假設一個隨機數(shù)據(jù)集被聚類為 k 個聚類,，并根據(jù)生成的聚類計算慣性（參見圖 6）。盡管缺乏基本的組織,，但隨著 k 的增加,，簇的隨機數(shù)據(jù)會產(chǎn)生穩(wěn)步下降的慣性（慣性的復數(shù)）。這是因為聚類中心越多,，數(shù)據(jù)點到聚類中心的距離越小就會產(chǎn)生慣性的衰減。正如在圖 4 中已經(jīng)看到的,，在具有簇組織的數(shù)據(jù)集中,，無論 k 是否低于或高于最佳簇數(shù) K，慣性的減少率都會有所不同,。將觀察數(shù)據(jù)和隨機數(shù)據(jù)的慣性繪制在一起時差異變得明顯（參見圖 7）,。間隔量統(tǒng)計是通過比較來自（希望）聚類數(shù)據(jù)集和覆蓋數(shù)據(jù)空間中相同范圍的相應隨機數(shù)據(jù)集的慣性來計算的。

圖 6：均勻分布的隨機數(shù)據(jù)聚集成 k=4（左）,、6（中）和 15（右）簇,。

圖 7：原始數(shù)據(jù)（來自圖 1）與 k 范圍內(nèi)的隨機數(shù)據(jù)的慣性如何降低。

在實際計算間隔統(tǒng)計量時,，會生成一些隨機樣本,，然后在 k 的范圍內(nèi)進行聚類，并記錄由此產(chǎn)生的慣性,。這允許隨機情況下的一些慣性,。原始數(shù)據(jù)集也在k的范圍內(nèi)聚集，產(chǎn)生一系列慣性,。 k 個簇的間隙統(tǒng)計量計算為

其中 Wk(i) 是來自第 i 個隨機樣本 (i=1,2,…,B) 的慣性,，具有 k 個簇，Wk 是來自原始數(shù)據(jù)的慣性具有 k 個簇,，將其標準差計算為

然后找到最優(yōu)K作為滿足條件的最小k

間隔量統(tǒng)計的計算涉及模擬,，所以這里在 R 中計算間隙統(tǒng)計信息。特別是調(diào)用clusGap()函數(shù)計算不同k處的gap統(tǒng)計量,，maxSE()返回滿足上述條件的最優(yōu)K,。圖 8 顯示了圖 1 中示例數(shù)據(jù)集的間隙統(tǒng)計圖，基于每個 k 處的 B=100 次迭代,。紅線代表滿足上述條件的最優(yōu) K,。

需要注意的是,，由間隔量統(tǒng)計方法確定的最優(yōu) K 可能不一致。例如,，當間隔量統(tǒng)計方法多次應用于演示數(shù)據(jù)時,，得到的最優(yōu) K 可能不同（見圖 9）。

MNIST 手寫數(shù)字數(shù)據(jù)示例

現(xiàn)在讓我們在具有簇組織的真實數(shù)據(jù)集上檢查上述三種方法,。 MNIST 數(shù)據(jù)集由 0 到 9 的手寫數(shù)字的灰度圖像組成,。在這個例子中，我們使用了 n=1797 個 8x8 像素的圖像,。圖 10 顯示了數(shù)據(jù)集的一些示例,。

上述三種方法用于確定最佳聚類數(shù)。由于該數(shù)據(jù)集中有 10 個不同的數(shù)字,，因此可以合理地假設有 10 個聚類,，每個聚類對應一個數(shù)字。然而人們可能有多種書寫數(shù)字的方式,，實際上簇的數(shù)量不一定是 10,。數(shù)據(jù)的 2D 散點圖（通過 tSNE 投影到 2D 空間，參見圖 11）顯示一些簇可能與其他簇很好地分離,，而一些簇可能接觸或重疊,。

肘部法的結果尚無定論，因為圖中沒有明顯的肘部（圖 12,，左）,。而圖中有一些微妙的彎曲（例如，9,、12,、20、24 等等）,，并且可以選擇其中任何一個作為聚類的數(shù)量,。

圖 12：根據(jù)數(shù)字數(shù)據(jù)生成的肘部圖（左）和輪廓系數(shù)圖（右）。

圖 13：根據(jù) B=100 次迭代從數(shù)字數(shù)據(jù)生成的間隔量統(tǒng)計圖,。最佳 k=12 用紅線表示,。

輪廓系數(shù)在 k=12 處有一個峰值（圖 12，右）,。根據(jù)間隔量統(tǒng)計方法,，k=12也被確定為最佳聚類數(shù)（圖13）。我們可以直觀地比較 k=9（根據(jù)肘部方法最佳）和 k=12（根據(jù)輪廓和間隙統(tǒng)計方法最佳）的 k-Means 聚類（參見圖 14）,。

圖 14：在 k=9 和 k=12 的數(shù)字數(shù)據(jù)中發(fā)現(xiàn)的 K-Means 聚類,， t-SNE 投影到 2D 空間。

總結

本文展示了選擇最佳聚類數(shù)的三種不同方法,，即肘部法,、輪廓系數(shù)和間隔量統(tǒng)計量,。雖然肘部圖的解釋相當主觀，但輪廓系數(shù)和間隙統(tǒng)計方法都可以精確地確定聚類的數(shù)量,。但是間隔量統(tǒng)計涉及模擬,，它可能并不總是產(chǎn)生相同的結果。

與許多機器學習方法一樣,，此處描述的方法并非在所有場景中都能正常工作,。由于這些方法量化了聚類中心和數(shù)據(jù)點之間的距離，因此它們適用于尋找凸聚類,，例如在 K-Means 聚類中找到的聚類的數(shù)量,。

引用

Robert Tibshirani, Guenther Walther, Trevor Hastie. Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society, Series B, 63: 411–423 (2001).