鑽石舞台

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

這種情況下，s 變為負數，接近 -1。

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

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

肘部法 The elbow method

輪廓係數的優化 The optimization of the silhouette coefficient

間隔量統計 The gap statistic

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

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

一種這樣的質量指標是inertia（慣性）。這被計算為數據點與其所屬聚類中心之間的平方距離之和。inertia量化了簇內的變化。

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

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

一旦在所有數據點計算 s，s 的平均值就確定了輪廓係數。可以為每個簇單獨計算輪廓係數，也可以為所有數據點計算輪廓係數。接近 1 的輪廓係數表明聚類算法能夠將數據劃分為分離良好的聚類。

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

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

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

輪廓係數可以提供更客觀的方法來確定最佳聚類數。這是通過簡單地計算 k 範圍內的輪廓係數並將峰值識別為最佳 K 來完成的。在 k 範圍內執行 K-Means 聚類，找到產生最大輪廓係數的最佳 K，並根據優化的 K 將數據點分配給聚類。圖 5 顯示了我們提供的示例數據中的輪廓係數圖示例 如圖 1 所示，輪廓係數在 k=6 處達到峰值，因此確定為最佳 K。

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

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

圖 7：原始數據（來自圖 1）與 k 範圍內的隨機數據的慣性如何降低。

在實際計算間隔統計量時，會生成一些隨機樣本，然後在 k 的範圍內進行聚類，並記錄由此產生的慣性。這允許隨機情況下的一些慣性。原始數據集也在k的範圍內聚集，產生一系列慣性。k 個簇的間隙統計量計算為

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

然後找到最優K作為滿足條件的最小k

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

需要注意的是，由間隔量統計方法確定的最優 K 可能不一致。例如，當間隔量統計方法多次應用於演示數據時，得到的最優 K 可能不同（見圖 9）。

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

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

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

圖 12：根據數字數據生成的肘部圖（左）和輪廓係數圖（右）。

圖 13：根據 B=100 次迭代從數字數據生成的間隔量統計圖。最佳 k=12 用紅線表示。

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

圖 14：在 k=9 和 k=12 的數字數據中發現的 K-Means 聚類， t-SNE 投影到 2D 空間。

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

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

引用

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).

作者：Satoru Hayasaka