[AI] Clustering決定分群數的方法

7 min readJul 9, 2019

Some methods to decide clustering numbers

估計法(通常沒人用):

一個非常快速的，拍腦袋的方法是將樣本量除以2再平方出来的值作為K值，具體公式為:

Elbow method:

如下圖左所示，此種方法適用於K值相對較小的情況，當選擇的k值小於真正的時，k每增加1，cost值就會大幅的減小；當選擇的k值大於真正的K時，k每增加1，cost值的變化就不會那麼明顯。這樣，正確的k值就會在這個轉捩點，類似elbow的地方:

缺點: 並不是所有的問題都可以通過畫肘部圖來解決，有的問題如右邊的那個圖，肘點位置不明顯（肘點可以是3，4，5），這時就無法確定K值了

公式：

Gap statistic:

這裡我們要繼續使用上面的。GapStatistic的定義為:

這裡指的是的期望。這個數值通常通過蒙特卡洛類比產生，我們在樣本裡所在的矩形區域中（高維的話就是立方體區域）按照均勻分佈隨機地產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本做K-Means，從而得到一個。如此往復多次，通常20次，我們可以得到20個。對這20個數值求平均值，就得到了的近似值。最終可以計算GapStatisitc。而Gap statistic取得最大值所對應的K就是最佳的K。

Gap Statistic的基本思路是：引入參考的測值，這個參考值可以有Monte Carlo采样的方法获得。

B是sampling的次數。為了修正MC帶來的誤差，我們計算sk也即標準差來矯正GapStatistic。

選擇滿足的最小的k作為最優的聚類個數。下圖闡釋了GapStatistic的過程。

Python code:

Silhouette score:

Silhouette method會衡量物件和所屬簇之間的相似度 — — 即內聚性（cohesion）。該對比通過silhouette值來實現，後者在[-1, 1]范圍內。Silhouette 值接近1，說明物件與所屬簇之間有密切聯繫；反之則接近-1。若某模型中的一個資料簇，生成的基本是比較高的silhouette 值，說明該模型是合適、可接受的。

•方法：

•1）計算樣本i到同簇其他樣本的平均距離a(i)。a(i)越小，說明樣本i越應該被聚類到該簇。將a(i)稱為樣本i的簇內不相似度。簇C中所有樣本的a(i)均值稱為簇C的簇不相似度。

•2）計算樣本i到其他某簇C(j)的所有樣本的平均距離b(ij)，稱為樣本i與簇C(j)的不相似度。定義為樣本i的簇間不相似度：b(i) =min{bi1, bi2, …, bik}，b(i)越大，說明樣本i越不屬於其他簇。

•3）根據樣本i的簇內不相似度ai和簇間不相似度b i，定義樣本i的輪廓係數：

•4）判斷：

•s(i)接近1，則說明樣本i聚類合理

•s(i)接近-1，則說明樣本i更應該分類到另外的簇

•若s(i)近似為0，則說明樣本i在兩個簇的邊界上

•所有樣本的s(i)的均值稱為聚類結果的輪廓係數。但是，其缺陷是計算複雜度為O(n²)，那麼當資料量上到百萬，計算開銷會非常巨大。

sklearn.silhouette

Canopy:

肘部法則（ElbowMethod）和輪廓係數（SilhouetteCoefficient）來對k值進行最終的確定，但是這些方法都是屬於“事後”判斷的，而Canopy演算法的作用就在於它是通過事先粗聚類的方式，為k-means演算法確定初始聚類中心個數和聚類中心點。

與傳統的聚類演算法(比如K-Means)不同，Canopy聚類最大的特點是不需要事先指定k值(即clustering的個數)，因此具有很大的實際應用價值。與其他聚類演算法相比，Canopy聚類雖然精度較低，但其在速度上有很大優勢，因此可以使用Canopy聚類先對資料進行“粗”聚類，得到k值，以及大致的k個中心點，再使用K-Means進行進一步“細”聚類。所以Canopy+K-Means這種形式聚類演算法聚類效果良好。