聚類算法的評估指標技术頭條網

聚類算法的評估指標

2020-01-22 14:04:00 sandag

在學習聚類算法得時候並沒有涉及到評估指標，主要原因是聚類算法屬於非監督學習，並不像分類算法那樣可以使用訓練集或測試集中得數據計算準確率、召回率等。那麼如何評估聚類算法得好壞呢？好的聚類算法,一般要求類簇具有：

高的類內 (intra-cluster) 相似度
低的類間 (inter-cluster) 相似度

對於聚類算法大致可分為 2類度量標準：

內部評估的方法：通過一個單一的量化得分來評估算法好壞；該類型的方法
外部評估的方法：通過將聚類結果與已經有“ground truth”分類進行對比。要麼通過人類進行手動評估，要麼通過一些指標在特定的應用場景中進行聚類用法的評估。不過該方法是有問題的，如果真的有了label，那麼還需要聚類幹嘛，而且實際應用中，往往都沒label；另一方面，這些label只反映了數據集的一個可能的劃分方法，它並不能告訴你存在一個不同的更好的聚類算法。

內部評價指標

當一個聚類結果是基於數據聚類自身進行評估的，這一類叫做內部評估方法。如果某個聚類算法聚類的結果是類間相似性低，類內相似性高，那麼內部評估方法會給予較高的分數評價。不過內部評價方法的缺點是：

那些高分的算法不一定可以適用於高效的信息檢索應用場景；

這些評估方法對某些算法有傾向性，如k-means聚類都是基於點之間的距離進行優化的，而那些基於距離的內部評估方法就會過度的讚譽這些生成的聚類結果。

這些內部評估方法可以基於特定場景判定一個算法要優於另一個，不過這並不表示前一個算法得到的結果比後一個結果更有意義。這裡的意義是假設這種結構事實上存在於數據集中的，如果一個數據集包含了完全不同的數據結構，或者採用的評價方法完全和算法不搭，比如k-means只能用於凸集數據集上，許多評估指標也是預先假設凸集數據集。在一個非凸數據集上不論是使用k-means還是使用假設凸集的評價方法，都是徒勞的。

SSE(和方差)

該統計參數計算的是擬合數據和原始數據對應點的誤差的平方和，計算公式如下：

SSE越接近於0，說明模型選擇和擬合更好，數據預測也越成功。

<code>#斷崖碎石圖選取最優K值
import pandas as pd
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
'利用SSE選擇k'
SSE = []# 存放每次結果的誤差平方和
for k in range(1,9):
estimator = KMeans(n_clusters=k)# 構造聚類器
estimator.fit(df[['calories','sodium','alcohol','cost']])
SSE.append(estimator.inertia_)
N = range(1,9)
plt.xlabel('k')
plt.ylabel('SSE')
plt.plot(N,SSE,'o-')
plt.show()
/<code>

輪廓係數 Silhouette Coefficient

輪廓係數適用於實際類別信息未知的情況。對於單個樣本，設a是與它同類別中其他樣本的平均距離，b是與它距離最近不同類別中樣本的平均距離，其輪廓係數為：

對於一個樣本集合，它的輪廓係數是所有樣本輪廓係數的平均值。輪廓係數的取值範圍是[-1,1]，同類別樣本距離越相近不同類別樣本距離越遠，分數越高。缺點：不適合基高密度的聚類算法DBSCAN。

<code>from sklearn import metrics
from sklearn.metrics import pairwise_distances
from sklearn import datasets
dataset = datasets.load_iris()
X = dataset.data
y = dataset.target

import numpy as np
from sklearn.cluster import KMeans
kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
labels = kmeans_model.labels_
metrics.silhouette_score(X, labels, metric='euclidean')
/<code>

Calinski-Harabaz Index

在真實的分群label不知道的情況下，Calinski-Harabasz可以作為評估模型的一個指標。Calinski-Harabasz指標通過計算類中各點與類中心的距離平方和來度量類內的緊密度，通過計算各類中心點與數據集中心點距離平方和來度量數據集的分離度，CH指標由分離度與緊密度的比值得到。從而，CH越大代表著類自身越緊密，類與類之間越分散，即更優的聚類結果。

其中m為訓練樣本數，k是類別個數，是類別之間協方差矩陣，是類別內部數據協方差矩陣，為矩陣的跡。也就是說，類別內部數據的協方差越小越好，類別之間的協方差越大越好，這樣的Calinski-Harabasz分數會高。同時，數值越小可以理解為：組間協方差很小，組與組之間界限不明顯。

優點

當 cluster （簇）密集且分離較好時，分數更高，這與一個標準的 cluster（簇）有關。
得分計算很快與輪廓係數的對比，最大的優勢：快！相差幾百倍！毫秒級。

缺點

凸的簇的 Calinski-Harabaz index（Calinski-Harabaz 指數）通常高於其他類型的 cluster（簇），例如通過 DBSCAN 獲得的基於密度的 cluster（簇）。所以不適合基於密度的聚類算法，DBSCAN。

<code>import numpy as np
from sklearn.cluster import KMeans
kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
labels = kmeans_model.labels_
print(metrics.calinski_harabaz_score(X, labels))
/<code>

Compactness(緊密性)(CP)

CP計算每一個類各點到聚類中心的平均距離CP越低意味著類內聚類距離越近。著名的 K-Means 聚類算法就是基於此思想提出的。缺點：沒有考慮類間效果。

Separation(間隔性)(SP)

SP計算各聚類中心兩兩之間平均距離，SP越高意味類間聚類距離越遠。缺點：沒有考慮類內效果。

Davies-Bouldin Index(戴維森堡丁指數)(分類適確性指標)(DB)(DBI)

DB計算任意兩類別的類內距離平均距離(CP)之和除以兩聚類中心距離求最大值。DB越小意味著類內距離越小同時類間距離越大。該指標的計算公式：

其中n是類別個數，是第i個類別的中心，是類別i中所有的點到中心的平均距離；

中心點和之間的距離。算法生成的聚類結果越是朝著類內距離最小（類內相似性最大）和類間距離最大（類間相似性最小）變化，那麼Davies-Bouldin指數就會越小。缺點：因使用歐式距離所以對於環狀分佈聚類評測很差。

<code>from sklearn import datasets 
from sklearn.cluster import KMeans 
from sklearn.metrics import davies_bouldin_score 
from sklearn.datasets.samples_generator import make_blobs 

# loading the dataset 
X, y_true = make_blobs(n_samples=300, centers=4,
 cluster_std=0.50, random_state=0) 

# K-Means 
kmeans = KMeans(n_clusters=4, random_state=1).fit(X) 

# we store the cluster labels 
labels = kmeans.labels_ 

print(davies_bouldin_score(X, labels))
/<code>

Dunn Validity Index (鄧恩指數)(DVI)

DVI計算任意兩個簇元素的最短距離(類間)除以任意簇中的最大距離(類內)。DVI越大意味著類間距離越大同時類內距離越小。

其中

表示類別,之間的距離；

表示類別內部的類內距離：

類間距離可以是任意的距離測度，例如兩個類別的中心點的距離；
類內距離可以以不同的方法去測量，例如類別kk中任意兩點之間距離的最大值。

因為內部評估方法是搜尋類內相似最大，類間相似最小，所以算法生成的聚類結果的Dunn指數越高，那麼該算法就越好。缺點：對離散點的聚類測評很高、對環狀分佈測評效果差。

<code>import pandas as pd 
from sklearn import datasets 
from jqmcvi import base 

# loading the dataset 
X = datasets.load_iris() 
df = pd.DataFrame(X.data) 

# K-Means 
from sklearn import cluster 
k_means = cluster.KMeans(n_clusters=3) 
k_means.fit(df) #K-means training 
y_pred = k_means.predict(df) 

# We store the K-means results in a dataframe 
pred = pd.DataFrame(y_pred) 
pred.columns = ['Type'] 

# we merge this dataframe with df 
prediction = pd.concat([df, pred], axis = 1) 

# We store the clusters 
clus0 = prediction.loc[prediction.Species == 0]  

clus1 = prediction.loc[prediction.Species == 1] 
clus2 = prediction.loc[prediction.Species == 2] 
cluster_list = [clus0.values, clus1.values, clus2.values] 

print(base.dunn(cluster_list))
/<code>

外部評價指標

在外部評估方法中，聚類結果是通過使用沒被用來做訓練集的數據進行評估。例如已知樣本點的類別信息和一些外部的基準。這些基準包含了一些預先分類好的數據，比如由人基於某些場景先生成一些帶label的數據，因此這些基準可以看成是金標準。這些評估方法是為了測量聚類結果與提供的基準數據之間的相似性。然而這種方法也被質疑不適用真實數據。

純度（Purity）

純度（Purity）是一種簡單而透明的評估手段，為了計算純度（Purity），我們把每個簇中最多的類作為這個簇所代表的類，然後計算正確分配的類的數量，然後除以N。形式化表達如下：

其中：

是聚類的集合，表示第k個聚類的集合。
是文檔集合，表示第J個文檔。
表示文檔總數。

上述過程即給每個聚類簇分配一個類別,且這個類別的樣本在該簇中出現的次數最多，然後計算所有 K 個聚類簇的這個次數之和再歸一化即為最終值。Purity值在0～1之間 ,越接近1表示聚類結果越好。

如圖認為x代表一類文檔，o代表一類文檔，方框代表一類文檔。如上圖的purity = ( 3+ 4 + 5) / 17 = 0.71，其中第一類正確的有5個，第二個4個，第三個3個，總文檔數17。

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

<code>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
/<code>

標準化互信息（NMI）

互信息（Normalized Mutual Information）是用來衡量兩個數據分佈的吻合程度。也是一有用的信息度量，它是指兩個事件集合之間的相關性。互信息越大，詞條和類別的相關程度也越大。NMI (Normalized Mutual Information) 即歸一化互信息：

其中,表示互信息(Mutual Information),為熵，當 log 取 2 為底時，單位為 bit，取 e 為底時單位為 nat。

其中,

可以分別看作樣本 (document) 屬於聚類簇, 屬於類別, 同時屬於的概率。第二個等價式子則是由概率的極大似然估計推導而來。

互信息

表示給定類簇信息的前提條件下,類別信息的增加量，或者說其不確定度的減少量。直觀地，互信息還可以寫出如下形式：

互信息的最小值為 0, 當類簇相對於類別只是隨機的, 也就是說兩者獨立的情況下,對於未帶來任何有用的信息.如果得到的與關係越密切, 那麼

值越大。如果完整重現了, 此時互信息最大：

當K=N時,即類簇數和樣本個數相等，MI 也能達到最大值。所以 MI 也存在和純度類似的問題,即它並不對簇數目較大的聚類結果進行懲罰,因此也不能在其他條件一樣的情況下,對簇數目越小越好的這種期望進行形式化。NMI 則可以解決上述問題,因為熵會隨著簇的數目的增長而增大。當K=N時,

會達到其最大值

, 此時就能保證 NMI 的值較低。之所以採用

作為分母是因為它是

的緊上界, 因此可以保證

。

示例：

gnd 是 ground truth 的意思，grps 表示聚類後的 groups. 問題：計算序列 gnd 和 grps 的 NMI.

先計算聯合概率分佈

計算邊際分佈

計算熵和互信息

計算 NMI

代碼實現：

<code>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)
/<code>

sklearn中自帶的方法：

<code>from sklearn.metrics.cluster import normalized_mutual_info_score
print(normalized_mutual_info_score([0, 0, 1, 1], [0, 0, 1, 1]))
/<code>

調整互信息AMI（ Adjusted mutual information）

已知聚類標籤與真實標籤，互信息（mutual information）能夠測度兩種標籤排列之間的相關性，同時忽略標籤中的排列。有兩種不同版本的互信息以供選擇，一種是Normalized Mutual Information（NMI）,一種是Adjusted Mutual Information（AMI）。

假設U與V是對N個樣本標籤的分配情況，則兩種分佈的熵（熵表示的是不確定程度）分別為：

其中：

是從U中隨機選取的對象到類的概率
從V中隨機選取的對象到類的概率

U與V之間的互信息（MI）定義為：

其中

是隨機選擇的對象落入兩個類的概率和。

調整互信息（Adjusted mutual information）定義為：

MI的期望可以用以下公式來計算。在這個方程式中，

為元素的數量，

為元素的數量：

利用基於互信息的方法來衡量聚類效果需要實際類別信息，MI與NMI取值範圍為[0,1]，AMI取值範圍為[-1,1]，它們都是值越大意味著聚類結果與真實情況越吻合。

優點

隨機（統一）標籤分配的AMI評分接近0）
有界範圍 [0, 1]: 接近 0 的值表示兩個主要獨立的標籤分配，而接近 1 的值表示重要的一致性。此外，正好 0 的值表示 purely（純粹）獨立標籤分配，正好為 1 的 AMI 表示兩個標籤分配相等（有或者沒有 permutation）。
對簇的結構沒有作出任何假設: 可以用於比較聚類算法

缺點：

與 inertia 相反， MI-based measures 需要了解 ground truth classes，而在實踐中幾乎不可用，或者需要人工標註或手動分配（如在監督學習環境中）。然而，基於 MI-based measures （基於 MI 的測量方式）也可用於純無人監控的設置，作為可用於聚類模型選擇的 Consensus Index （共識索引）的構建塊。
NMI 和 MI 沒有調整機會。

<code>from sklearn import metrics
labels_true = [0, 0, 0, 1, 1, 1]
labels_pred = [0, 0, 1, 1, 2, 2]

print(metrics.adjusted_mutual_info_score(labels_true, labels_pred))
/<code>

Rand index蘭德指數

蘭德指數 (Rand index, RI), 將聚類看成是一系列的決策過程,即對文檔集上所有N(N-1)/2個文檔 (documents) 對進行決策。當且僅當兩篇文檔相似時,我們將它們歸入同一簇中。

Positive:

TP 將兩篇相似文檔歸入一個簇 (同 – 同)
TN 將兩篇不相似的文檔歸入不同的簇 (不同 – 不同)

Negative:

FP 將兩篇不相似的文檔歸入同一簇 (不同 – 同)
FN 將兩篇相似的文檔歸入不同簇 (同- 不同) (worse)

RI 則是計算「正確決策」的比率(精確率, accuracy)：

RI取值範圍為[0,1]，值越大意味著聚類結果與真實情況越吻合。

<code>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)
/<code>

調整蘭德係數（Adjusted Rand index）

對於隨機結果，RI並不能保證分數接近零。為了實現“在聚類結果隨機產生的情況下，指標應該接近零”，調整蘭德係數（Adjusted rand index）被提出，它具有更高的區分度：

ARI取值範圍為[-1,1]，值越大意味著聚類結果與真實情況越吻合。從廣義的角度來講，ARI衡量的是兩個數據分佈的吻合程度。

優點：

對任意數量的聚類中心和樣本數，隨機聚類的ARI都非常接近於0
取值在［－1，1］之間，負數代表結果不好，越接近於1越好
對簇的結構不需作出任何假設：可以用於比較聚類算法。

缺點：

與 inertia 相反，ARI 需要 ground truth classes 的相關知識，ARI需要真實標籤，而在實踐中幾乎不可用，或者需要人工標註者手動分配（如在監督學習環境中）。然而，ARI 還可以在 purely unsupervised setting （純粹無監督的設置中）作為可用於聚類模型選擇（TODO）的共識索引的構建塊。

<code>from sklearn import metrics
labels_true = [0, 0, 0, 1, 1, 1]
labels_pred = [0, 0, 1, 1, 2, 2]

print(metrics.adjusted_rand_score(labels_true, labels_pred)) 
/<code>

F值方法

這是基於上述RI方法衍生出的一個方法，我們可以 FN 罰更多,通過取

中的大於 1, 此時實際上也相當於賦予召回率更大的權重：

RI方法有個特點就是把準確率和召回率看得同等重要，事實上有時候我們可能需要某一特性更多一點，這時候就適合F值方法。

<code>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)
/<code>

Fowlkes-Mallows scores

Fowlkes-Mallows Scores（FMI） FMI是成對的precision（精度）和recall（召回）的幾何平均數。取值範圍為 [0,1]，越接近1越好。定義為：

代碼實現：

<code>from sklearn import metrics
labels_true = [0, 0, 0, 1, 1, 1]
labels_pred = [0, 0, 1, 1, 2, 2]

print(metrics.fowlkes_mallows_score(labels_true, labels_pred))
/<code>

調和平均V-measure

說V-measure之前要先介紹兩個指標：

同質性（homogeneity）：每個群集只包含單個類的成員。
完整性（completeness）：給定類的所有成員都分配給同一個群集。

同質性和完整性分數基於以下公式得出：

其中

是給定給定簇賦值的類的條件熵，由以下公式求得：

是類熵，公式為：

其中，n是樣本總數，和分別屬於類c和類k的樣本數，而是從類c劃分到類k的樣本數量。條件熵H(K|C)和類熵H(K)，根據以上公式對稱求得。

V-measure是同質性homogeneity和完整性completeness的調和平均數，V-measure取值範圍為 [0,1]，越大越好，但當樣本量較小或聚類數據較多的情況，推薦使用AMI和ARI。公式：

代碼實現：

<code>from sklearn import metrics
labels_true = [0, 0, 0, 1, 1, 1]
labels_pred = [0, 0, 1, 1, 2, 2]

print(metrics.homogeneity_score(labels_true, labels_pred))
print(metrics.completeness_score(labels_true, labels_pred))
print(metrics.v_measure_score(labels_true, labels_pred))
/<code>

優點：

分數明確：從0到1反應出最差到最優的表現；
解釋直觀：差的調和平均數可以在同質性和完整性方面做定性的分析；
對簇結構不作假設：可以比較兩種聚類算法如k均值算法和譜聚類算法的結果。

缺點：

以前引入的度量在隨機標記方面沒有規範化，這意味著，根據樣本數，集群和先驗知識，完全隨機標籤並不總是產生相同的完整性和均勻性的值，所得調和平均值V-measure也不相同。特別是，隨機標記不會產生零分，特別是當簇的數量很大時。
當樣本數大於一千，聚類數小於10時，可以安全地忽略該問題。對於較小的樣本量或更大數量的集群，使用經過調整的指數（如調整蘭德指數）更為安全。
這些指標要求的先驗知識，在實踐中幾乎不可用或需要手動分配的人作註解者（如在監督學習環境中）。