如何評估聚類有效性

常見的聚類目標函數希望形成一個簇內高相似度而簇間低相似度的結果，拿文檔舉例，相同簇內的文檔更為相似，而不同簇之間的文檔各不相似。這類目標函數是作為聚類質量的內部標準，但是，內部標準得到一個不錯的分數，不代表在實際的應用中也能得到良好的效果。比如，為了給搜索結果選擇一個最佳的聚類演算法，我們可能需要調查當使用各個演算法時，用戶找到它們所希望的內容所需的用時。但是這通常需要很大的投入。

作為用戶判斷的替代，我們使用一組類作為Benchmark，這也被稱之為黃金標準（Gold Standard）。Benchmark基於人工判斷製作。在有了這個Benchmark後，我們就可以定義出外部標準，通過簇和黃金標準之間類別的匹配的程度來評估聚類結果的好壞。舉個例子，當我們在搜索引擎上搜索「jaguar」的時候，我們可能希望結果包含三個類別：汽車、動物或是操作系統。在這個例子的評估中，我們只用到了Benchmark里提供的劃分標準，而不是它的類別標籤。

這篇文章介紹評估聚類質量的四個外部標準：純度（Purity）是一種簡單而透明的評估手段；標準化互信息（NMI, Normalized Mutual Information）是從信息理論方面來評估；蘭德指數（RI, Rand Index）能度量聚類過程中的假陽性和假陰性結果的懲罰；F值（F measure）支持調整這兩種錯誤懲罰的權重。

為了計算純度（Purity），我們把每個簇中最多的類作為這個簇所代表的類，然後計算正確分配的類的數量，然後除以 。形式化表達如下：

其中， 是聚類結果的集合， 是原始分類的集合。

在圖1中我們給出了一個計算純度的例子，錯誤的聚類純度會接近0，而一個完美聚類的純度是1。在表1中有純度與其他三個本文中介紹的指標進行比較。

# 圖1中例子的python表示，label表示原有分類，result表示聚類結果# 0, 1, 2分別表示叉、圈和菱形label = [0, 0, 1, 0, 0, 0, 0, 1, 2, 1, 1, 1, 0, 2, 2, 2, 0]result = [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

當簇的數量很多的時候，容易達到較高的純度——特別是，如果每個文檔都被分到獨立的一個簇中，那麼計算得到的純度就會是1。因此，不能簡單用純度來衡量聚類質量與聚類數量之間的關係。

def purity(result, label): # 計算純度 total_num = len(label) cluster_counter = collections.Counter(result) original_counter = collections.Counter(label) t = [] for k in cluster_counter: p_k = [] for j in original_counter: count = 0 for i in range(len(result)): if result[i] == k and label[i] == j: # 求交集 count += 1 p_k.append(count) temp_t = max(p_k) t.append(temp_t) return sum(t)/total_num

能讓我們權衡這個的指標被稱作標準化互信息（NMI）：

在式（2）中的 被稱為互信息：

其中， 、 以及 分別是文檔在聚類簇k、原始分類j以及同時是簇k和分類j的概率。對於概率的最大似然估計（即，每個概率的估計是對應的相對頻率），式（3）和式（4）是等價的。

是熵（entropy）：

同樣地，（6）式是基於概率最大似然估計。

def NMI(result, label): # 標準化互信息 total_num = len(label) cluster_counter = collections.Counter(result) original_counter = collections.Counter(label) # 計算互信息量 MI = 0 eps = 1.4e-45 # 取一個很小的值來避免log 0 for k in cluster_counter: for j in original_counter: count = 0 for i in range(len(result)): if result[i] == k and label[i] == j: count += 1 p_k = 1.0*cluster_counter[k] / total_num p_j = 1.0*original_counter[j] / total_num p_kj = 1.0*count / total_num MI += p_kj * math.log(p_kj /(p_k * p_j) + eps, 2) # 標準化互信息量 H_k = 0 for k in cluster_counter: H_k -= (1.0*cluster_counter[k] / total_num) * math.log(1.0*cluster_counter[k] / total_num+eps, 2) H_j = 0 for j in original_counter: H_j -= (1.0*original_counter[j] / total_num) * math.log(1.0*original_counter[j] / total_num+eps, 2) return 2.0 * MI / (H_k + H_j)

在式（3）中， 用于衡量當我們被告知聚類是什麼時，我們關於分類的已知知識會增加的信息量。如果聚類相對於已知的分類是隨機的，那麼 的最小值為0。在這種情況下，知道文檔在特定的簇中不會給我們提供關於它類別的新信息。而互信息的最大值將在 完美再現這些類的聚類的時候達成，不過 中的聚類被進一步細分成更小的聚類時也是如此。特別的，當聚類數量 ，即每篇文檔都在一個類中時，也會達到最大互信息量。所以，互信息有著和純度同樣的問題：它不會懲罰聚類的大基數。同樣沒有把我們的偏好——其他條件相同的時候，簇越少越好——形式化。

式（2）的分母 通過標準化解決了這個問題。因為熵會隨著簇的數量增加而增加。例如，當聚類數量 時， 會達到它的最大值 ，這確保了對於 的情況，NMI值會比較低。因為NMI的標準化，我們便可以用它來比較具有不同數量簇的聚類結果。至於為何分母要選擇這種特殊的形式，原因是 是 的一個緊上界。這可以確保NMI的值始終介於0與1之間。

另一種對於聚類的分析方式是將其看成一系列決策。對於全部文檔中的 個文檔對都有一個決策。理想情況下，當且僅當兩個文檔相似時，我們把它們分在同一個簇里。真陽性（TP）決策將兩個相似的文檔分配在同一個簇中，真陰性（TN）決策將兩個不相似的文檔分配在不同的簇中。同時也存在著兩種錯誤。假陽性（FP）決策將兩個不相似的文檔分配在同一個簇中。假陰性（FN）決策將兩個相似的文檔分配在不同的簇中。蘭德指數（Rand Index）衡量在這些決策中，正確決策所佔的百分比。換句話說，這就是簡單的準確度（accuracy）。

我們還是來計算圖1所表示的聚類的RI作為例子。首先我們計算 。這三個簇分別包含6個、6個和5個數據。所以同一個簇中文檔對的總數，也就是「陽性」的數量為：

其中，簇1中的叉狀對，簇2中的圈狀對，簇3中的菱形對和叉狀對是真陽性的：

那麼， 。

和 的計算方式同理，結果如下：

然後可以計算

def contingency_table(result, label): total_num = len(label) TP = TN = FP = FN = 0 for i in range(total_num): for j in range(i + 1, total_num): if label[i] == label[j] and result[i] == result[j]: TP += 1 elif label[i] != label[j] and result[i] != result[j]: TN += 1 elif label[i] != label[j] and result[i] == result[j]: FP += 1 elif label[i] == label[j] and result[i] != result[j]: FN += 1 return (TP, TN, FP, FN)def rand_index(result, label): TP, TN, FP, FN = contingency_table(result, label) return 1.0*(TP + TN)/(TP + FP + FN + TN)

使用蘭德指數時，假陽性和假陰性有著同等的重要性。但是在實際情況中，把相似的文檔分開比把不同的文檔放在一個簇里更糟糕。我們可以使用F值，通過讓參數 來讓假陰性比假陽性獲得更多的懲罰，也就是說，給召回（Recall）更大的權重。

根據上表中的數字， ， 。當 時計算得到 ，當 時計算得到 。在信息檢索領域，由於研究者都很熟悉F值，所以傾向於使用它來評估聚類。

def precision(result, label): TP, TN, FP, FN = contingency_table(result, label) return 1.0*TP/(TP + FP)def recall(result, label): TP, TN, FP, FN = contingency_table(result, label) return 1.0*TP/(TP + FN)def F_measure(result, label, beta=1): prec = precision(result, label) r = recall(result, label) return (beta*beta + 1) * prec * r/(beta*beta * prec + r)

翻譯自Christopher D. Manning, Prabhakar Raghavan & Hinrich Schütze的Introduction to Information Retrieval第16章第3節Evaluation of clustering

Python部分代碼是我自己寫的，盡量避免了使用外部庫，儘管用numpy可以把代碼實現改得更接近公式的直接表達，不過因為我自己的使用環境不便，還是選擇了不用它。唯一需要導入的兩個包都是Python 3內置的，如下：

import collectionsimport math

這兩天自己做有關聚類的驗證，各種博客論文看了一圈，感覺就沒有能講的明白的。要說寫的好還是斯坦福這本書講的明白。雖然很多博客都提到了這個，但是也沒能找到看起來舒服的翻譯版本，索性自己翻譯一遍，並附上Python的實現，然後留著之後有用了查。