k-means的k值該如何確定？

01-23

比如我對100個樣本快速聚類，可以聚成4類，也可以聚成5類、6類...我應該如何確定到底聚成幾類？如何通過一個與k有關的指標得到k的最優值？

數據的先驗知識，或者數據進行簡單分析能得到
基於變化的演算法：即定義一個函數，隨著K的改變，認為在正確的K時會產生極值。如Gap Statistic（Estimating the number of clusters in a data set via the gap statistic, Tibshirani, Walther, and Hastie 2001），Jump Statistic （finding the number of clusters in a data set, Sugar and James 2003）
基於結構的演算法：即比較類內距離、類間距離以確定K。這個也是最常用的辦法，如使用平均輪廓係數，越趨近1聚類效果越好；如計算類內距離/類間距離，值越小越好；等。
基於一致性矩陣的演算法：即認為在正確的K時，不同次聚類的結果會更加相似，以此確定K。
基於層次聚類：即基於合併或分裂的思想，在一定情況下停止從而獲得K。
基於採樣的演算法：即對樣本採樣，分別做聚類；根據這些結果的相似性確定K。如，將樣本分為訓練與測試樣本；對訓練樣本訓練分類器，用於預測測試樣本類別，並與聚類的類別比較。

專欄最近正在整理K-means相關內容，有興趣可以看看：知乎專欄

法1：(輪廓係數)在實際應用中，由於Kmean一般作為數據預處理，或者用於輔助分聚類貼標籤。所以k一般不會設置很大。可以通過枚舉，令k從2到一個固定值如10，在每個k值上重複運行數次kmeans(避免局部最優解)，並計算當前k的平均輪廓係數，最後選取輪廓係數最大的值對應的k作為最終的集群數目。

法2：(Calinski-Harabasz準則)

其中SSB是類間方差，，m為所有點的中心點,mi為某類的中心點；

SSW是類內方差，；

(N-k)/(k-1)是複雜度；

比率越大，數據分離度越大.

這篇文章里提出了gap test，還提到了其他一些常用的方法

https://web.stanford.edu/~hastie/Papers/gap.pdf

另外，如果給k-mean強加一個covariance，可以算likelihood，然後就能用AIC BIC了。

比較實用的兩種：1 求拐點，即SSE隨著k的變大，增加並不明顯的點。嚴謹的公式是
Gap Statistic公式（匿名用戶提到）。 2.輪廓係數法（arachis提到）。通過計算類內內聚程度和類間分離度來評價。具體的做法請百度。