如何評價聚類結果的好壞？

11-24

一直就覺得聚類，甚至是無監督學習結果的評價方法在理論上不那麼令人信服。不像有監督學習那樣可以有一事一有二是二的說這個東西分對了就是分對了，錯了就是錯了。除了用眼睛看之外，有什麼比較靠譜的聚類評價結果嗎？看了兩篇綜述，還不是很被convinced。

沒有靠譜的方法。常規的 index，都是有先驗假設的，能不能用，好不好用，要明白後面的假設，結合對自己數據的理解，來判斷。

可參看這兩篇：

這個是用 set theory 對 clustering 作理論上的定義，我沒看懂。
E.R. Dougherty, M. Brun, A probabilistic theory of clustering, Pattern Recognition 37 (2004) 917–925.

這個是模擬，對常見的評價方法用上文的理論作評估，比較好懂，結果很悲觀：
M. Brun, C. Sima, J. Hua, J. Lowey, B. Carroll, E. Suh, and E. R. Dougherty. Model-based evaluation of clustering validation measures. Pattern Recognition, 40(3):807 – 824, 2007.

利益申報：我參與了後一篇文章的模擬計算工作。

看了下這個問題的回答，除了個別答案，其他都蠻扯淡的。正好今天在一個群里討論了下這個問題，發表下我自己的一點看法：

1. 聚類沒有統一的評價指標

因為不同聚類演算法的目標函數相差很大，有些是基於距離的，比如kmeans，有些是假設先驗分布的，比如GMM，LDA，有些是帶有圖聚類和譜分析性質的，比如譜聚類，還有些是基於密度的

拿譜聚類距離，其中有一種叫 normalized 譜聚類，基於 normlaized Laplacian matrix，它的目標函數裡面已經包含了對類簇間數目的約束( normalized cut )，所以聚類出來的結果天然地能使得類間數目較平均。但你不能拿這個作為評估它結果的指標，否則就因果顛倒了

2. 應該嵌入到問題中進行評價

很多實際問題中，聚類僅僅是其中的一步，可以對比不聚類的情形（比如人為分割、隨機分割數據集等等），所以這時候我們評價『聚類結果好壞』，其實是在評價『聚類是否能對最終結果有好的影響』

基於不同演算法，會有不同指標，通常較通用的應該一定都會有Entropy 熵和 Accuracy, Accuracy 里可以包含了precision, recall, f-measure.
假設我們使用k-means演算法，通常會加上SSE （Sum of squared errors）平方誤差和，其他演算法會有不同指標。
總體思想為一個cluster聚類內的數據點聚集在一起的密度越高，圈子越小，離centroid中心點越近，那麼這個聚類的總體質量相對來說就會越好。

常見的聚類評測指標有純度和 F 值，其中 F 值更為常用。

F 值的更普適的應用是信息檢索的結果，其計算包括了兩個指標：召回率（Recall Rate）和準確率（Precision Rate）。

召回率的定義為：檢索出的相關文檔數和文檔庫中所有的相關文檔數的比率，衡量的是檢索系統的查全率；
準確率的定義為：檢索出相關文檔數與檢索出的文檔總數的比率，衡量的是檢索系統的查准率；F 值為兩者的調和平均值。

如果不知道預定義類與聚類的對應關係，就需要得到每一個預定義類與每一個聚類之間的 F 值，其計算方法如下：

precision[i][j] = 預定義第 i 類並被分配到第 j 個聚類的文檔數 / 第 j 個聚類中的文檔數
recall[i][j] = 預定義第 i 類並被分配到第 j 個聚類的文檔數 / 預定義第 i 類的文檔數
f[i][j] = 2 * precision[i][j] * recall[i][j] / (precision[i][j] + recall[i][j])

這樣就得到了每一個預定義類與每一個聚類之間的 F 值，這在邏輯上構成了二分圖關係，邊權即為 F 值，我們的目標是找到一個二分圖完美匹配使得如下加權平均 F 值最大：

F-measure = sum(f[i][j] * 第 i 個預定義類的文檔數) / 總文檔數

方法為最大費用最大流或者 KM 演算法。如果數據量較小，直接枚舉匹配也是可以接受的方法。

上面的匿名用戶發布的：
ICDM2010年有一篇論文
Yanchi Liu, Zhongmou Li, Hui Xiong, Xuedong Gao, Junjie Wu:
Understanding of Internal Clustering Validation Measures. 911-916

我翻譯了一下，寫在博客了：http://blog.csdn.net/chixujohnny/article/details/51852633

聚類的評估也需要預先標註，把相似的數據放到一個堆（文件）里。演算法完成後再進行測試，主要測試宏觀準確度，宏觀召回率，宏觀混雜度。

我一般都用Davies-Bouldin index，你如果用R的話，可以看看這兩個包：clv, clusterCrit

聚類的結果可以運用以下方法評估。

1. 外部法：根據已知的真實分組評價聚類分析的結果，構造如下的混淆矩陣總結任意一對（兩條）記錄是否屬於同一分組。注意當有m條記錄時，共有m x m對記錄。

其中SS對記錄屬於相同的真實分組和相同的聚類，

SD對記錄屬於相同的真實分組，但不同的聚類，

DS對記錄屬於不同的真實分組，但相同的聚類，

DD對記錄屬於不同的真實分組和不同的聚類。

由上面的混淆矩陣可以計算聚類分析的準確率=

或Jaccard 係數=

另外，可以用純度=

作為評價指標，其中

是屬於第k聚類和真實分組第j 組的記錄數目。顯然，如果聚類分析將同一真實分組中的記錄都歸為一簇，純度達到最大值1。

2. 內部法：當真實分組情況未知時，可以用記錄的特徵向量計算內平方和（Within Sum of Squares, WSS）和外平方和（Between Sum of Squares, BSS）作為評價指標。對於有m條記錄，n個變數的聚類問題來說，WSS和BSS的定義式為

其中，

表示記錄i 的特徵向量，

表示記錄i 所在聚類中心點的特徵向量，

K 聚類總數, $Z_k$ 第k聚類中的記錄數目，

所有記錄中心點的特徵向量，

表示第k聚類中心點的特徵向量。

WSS和BSS分別度量相同聚類內部記錄之間的不相似度和不同聚類間記錄的不相似度。顯然，WSS越小，BSS越大，聚類結果越好。

3. 當只有兩個變數時，可以採用可視化方法評估聚類結果。例如，在R中可以調用ggplot()函數繪製散點圖，標識各個聚類和各自的中心點。一般地，應考慮以下幾個因素：

1) 聚類之間是否較好地相互分離，

2) 是否存在只有幾個點的聚類，

3) 是否存在靠得很近的中心點。

ICDM2010年有一篇論文
Yanchi Liu, Zhongmou Li, Hui Xiong, Xuedong Gao, Junjie Wu:
Understanding of Internal Clustering Validation Measures. 911-916
對11種無ground truth下的評價指標進行了分析，從compactness，noise，subcluster和skewness幾個方面評價了這些指標，最後得出了SDbw完爆其他的結論可以作為參考此外要根據你的數據和聚類的意義來判斷

看一下sklearn裡面聚類結果評價相應的模塊就很清楚了：

2.3. Clustering - scikit-learn 0.18.1 documentation

API Reference - scikit-learn 0.18.1 documentation

這裡有一篇介紹聚類分析效果評測的博客關於聚類分析的效果評測，供參考。

有類別標籤的時候用V-measure，沒有類別標籤的時候用輪廓係數。

1. 通過聚類指標來看
包括RMSSTD，SPRSQ，RSQ，CCC，偽F，偽T等
2. 通過散點圖看，是否聚類的是你想要的。
3. 看每個聚類的各個指標的平均值，如果各個指標的值都很明顯區分，可以業務上解釋，即為聚類效果好。

這是現在正在研究的方面，叫做「Clustering Axioms」，即聚類公理化。主要是依據2002年的論文「an impossible theory of clustering axioms」發展來的。

可以參考周志華《機器學習》的第九章，聚類性能度量外部指標有 Jaccard 係數，FM 指數，Rand 指數；聚類性能度量內部指標有 DB 指數，Dunn 指數。不過實用與否很難說。

看到了這篇博文，感覺不錯，聚類演算法初探（七）聚類分析的效果評測 - peghoty - 博客頻道 - CSDN.NET

剛看到一篇文章里，是用混淆矩陣的條件熵來評估聚類效果的：
Li L, Prakash B A. Time Series Clustering: Complex is Simpler![C]//Proceedings of the 28th International Conference on Machine Learning (ICML-11). 2011: 185-192.

Check out section 4.2 of THIS

可以參考分類的precision和recall來進行評價，使用pair-wised 的方式進行計算，比如任選取兩個結果，看它們是否應該在一起，在一起就是T，不在一起就是F。
其他的方法有Rand Value和Purity，其中Rand Value也是基於pair-wised的。