在學(xué)習(xí)聚類算法得時(shí)候并沒有涉及到評(píng)估指標(biāo)，主要原因是聚類算法屬于非監(jiān)督學(xué)習(xí)，并不像分類算法那樣可以使用訓(xùn)練集或測試集中得數(shù)據(jù)計(jì)算準(zhǔn)確率、召回率等。那么如何評(píng)估聚類算法得好壞呢？好的聚類算法,一般要求類簇具有：

• 高的類內(nèi) (intra-cluster) 相似度
• 低的類間 (inter-cluster) 相似度

對(duì)于聚類算法大致可分為 2類度量標(biāo)準(zhǔn)：

• 內(nèi)部評(píng)估的方法：通過一個(gè)單一的量化得分來評(píng)估算法好壞；該類型的方法
• 外部評(píng)估的方法：通過將聚類結(jié)果與已經(jīng)有“ground truth”分類進(jìn)行對(duì)比。要么通過人類進(jìn)行手動(dòng)評(píng)估，要么通過一些指標(biāo)在特定的應(yīng)用場景中進(jìn)行聚類用法的評(píng)估。不過該方法是有問題的，如果真的有了label，那么還需要聚類干嘛，而且實(shí)際應(yīng)用中，往往都沒label；另一方面，這些label只反映了數(shù)據(jù)集的一個(gè)可能的劃分方法，它并不能告訴你存在一個(gè)不同的更好的聚類算法。

當(dāng)一個(gè)聚類結(jié)果是基于數(shù)據(jù)聚類自身進(jìn)行評(píng)估的，這一類叫做內(nèi)部評(píng)估方法。如果某個(gè)聚類算法聚類的結(jié)果是類間相似性低，類內(nèi)相似性高，那么內(nèi)部評(píng)估方法會(huì)給予較高的分?jǐn)?shù)評(píng)價(jià)。不過內(nèi)部評(píng)價(jià)方法的缺點(diǎn)是：

• 那些高分的算法不一定可以適用于高效的信息檢索應(yīng)用場景；
• 這些評(píng)估方法對(duì)某些算法有傾向性，如k-means聚類都是基于點(diǎn)之間的距離進(jìn)行優(yōu)化的，而那些基于距離的內(nèi)部評(píng)估方法就會(huì)過度的贊譽(yù)這些生成的聚類結(jié)果。

這些內(nèi)部評(píng)估方法可以基于特定場景判定一個(gè)算法要優(yōu)于另一個(gè)，不過這并不表示前一個(gè)算法得到的結(jié)果比后一個(gè)結(jié)果更有意義。這里的意義是假設(shè)這種結(jié)構(gòu)事實(shí)上存在于數(shù)據(jù)集中的，如果一個(gè)數(shù)據(jù)集包含了完全不同的數(shù)據(jù)結(jié)構(gòu)，或者采用的評(píng)價(jià)方法完全和算法不搭，比如k-means只能用于凸集數(shù)據(jù)集上，許多評(píng)估指標(biāo)也是預(yù)先假設(shè)凸集數(shù)據(jù)集。在一個(gè)非凸數(shù)據(jù)集上不論是使用k-means還是使用假設(shè)凸集的評(píng)價(jià)方法，都是徒勞的。

該統(tǒng)計(jì)參數(shù)計(jì)算的是擬合數(shù)據(jù)和原始數(shù)據(jù)對(duì)應(yīng)點(diǎn)的誤差的平方和，計(jì)算公式如下：

SSE越接近于0，說明模型選擇和擬合更好，數(shù)據(jù)預(yù)測也越成功。

輪廓系數(shù)適用于實(shí)際類別信息未知的情況。對(duì)于單個(gè)樣本，設(shè)a是與它同類別中其他樣本的平均距離，b是與它距離最近不同類別中樣本的平均距離，其輪廓系數(shù)為：

對(duì)于一個(gè)樣本集合，它的輪廓系數(shù)是所有樣本輪廓系數(shù)的平均值。輪廓系數(shù)的取值范圍是[-1,1]，同類別樣本距離越相近不同類別樣本距離越遠(yuǎn)，分?jǐn)?shù)越高。缺點(diǎn)：不適合基高密度的聚類算法DBSCAN。

from sklearn import metricsfrom sklearn.metrics import pairwise_distancesfrom sklearn import datasetsdataset = datasets.load_iris()X = dataset.datay = dataset.target import numpy as npfrom sklearn.cluster import KMeanskmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)labels = kmeans_model.labels_metrics.silhouette_score(X, labels, metric='euclidean')

在真實(shí)的分群label不知道的情況下，Calinski-Harabasz可以作為評(píng)估模型的一個(gè)指標(biāo)。Calinski-Harabasz指標(biāo)通過計(jì)算類中各點(diǎn)與類中心的距離平方和來度量類內(nèi)的緊密度，通過計(jì)算各類中心點(diǎn)與數(shù)據(jù)集中心點(diǎn)距離平方和來度量數(shù)據(jù)集的分離度，CH指標(biāo)由分離度與緊密度的比值得到。從而，CH越大代表著類自身越緊密，類與類之間越分散，即更優(yōu)的聚類結(jié)果。

其中m為訓(xùn)練樣本數(shù)，k是類別個(gè)數(shù)，是類別之間協(xié)方差矩陣，是類別內(nèi)部數(shù)據(jù)協(xié)方差矩陣，為矩陣的跡。也就是說，類別內(nèi)部數(shù)據(jù)的協(xié)方差越小越好，類別之間的協(xié)方差越大越好，這樣的Calinski-Harabasz分?jǐn)?shù)會(huì)高。同時(shí)，數(shù)值越小可以理解為：組間協(xié)方差很小，組與組之間界限不明顯。

優(yōu)點(diǎn)

• 當(dāng) cluster （簇）密集且分離較好時(shí)，分?jǐn)?shù)更高，這與一個(gè)標(biāo)準(zhǔn)的 cluster（簇）有關(guān)。
• 得分計(jì)算很快與輪廓系數(shù)的對(duì)比，最大的優(yōu)勢：快！相差幾百倍！毫秒級(jí)。

缺點(diǎn)

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

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

SP計(jì)算各聚類中心兩兩之間平均距離，SP越高意味類間聚類距離越遠(yuǎn)。缺點(diǎn)：沒有考慮類內(nèi)效果。

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

其中n是類別個(gè)數(shù)，是第i個(gè)類別的中心，是類別i中所有的點(diǎn)到中心的平均距離；

中心點(diǎn)和之間的距離。算法生成的聚類結(jié)果越是朝著類內(nèi)距離最?。悆?nèi)相似性最大）和類間距離最大（類間相似性最?。┳兓?，那么Davies-Bouldin指數(shù)就會(huì)越小。缺點(diǎn)：因使用歐式距離所以對(duì)于環(huán)狀分布聚類評(píng)測很差。

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

DVI計(jì)算任意兩個(gè)簇元素的最短距離(類間)除以任意簇中的最大距離(類內(nèi))。DVI越大意味著類間距離越大同時(shí)類內(nèi)距離越小。

其中

表示類別,之間的距離；

表示類別內(nèi)部的類內(nèi)距離：

• 類間距離 可以是任意的距離測度，例如兩個(gè)類別的中心點(diǎn)的距離；
• 類內(nèi)距離 可以以不同的方法去測量，例如類別kk中任意兩點(diǎn)之間距離的最大值。

因?yàn)閮?nèi)部評(píng)估方法是搜尋類內(nèi)相似最大，類間相似最小，所以算法生成的聚類結(jié)果的Dunn指數(shù)越高，那么該算法就越好。缺點(diǎn)：對(duì)離散點(diǎn)的聚類測評(píng)很高、對(duì)環(huán)狀分布測評(píng)效果差。

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

純度（Purity）是一種簡單而透明的評(píng)估手段，為了計(jì)算純度（Purity），我們把每個(gè)簇中最多的類作為這個(gè)簇所代表的類，然后計(jì)算正確分配的類的數(shù)量，然后除以N。形式化表達(dá)如下：

其中：

• 是聚類的集合，表示第k個(gè)聚類的集合。
• 是文檔集合，表示第J個(gè)文檔。
• 表示文檔總數(shù)。

上述過程即給每個(gè)聚類簇分配一個(gè)類別,且這個(gè)類別的樣本在該簇中出現(xiàn)的次數(shù)最多，然后計(jì)算所有 K 個(gè)聚類簇的這個(gè)次數(shù)之和再歸一化即為最終值。Purity值在0～1之間 ,越接近1表示聚類結(jié)果越好。

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

當(dāng)簇的數(shù)量很多的時(shí)候，容易達(dá)到較高的純度——特別是，如果每個(gè)文檔都被分到獨(dú)立的一個(gè)簇中，那么計(jì)算得到的純度就會(huì)是1。因此，不能簡單用純度來衡量聚類質(zhì)量與聚類數(shù)量之間的關(guān)系。另外Purity無法用于權(quán)衡聚類質(zhì)量與簇個(gè)數(shù)之間的關(guān)系。

def purity(result, label):    # 計(jì)算純度     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

互信息（Normalized Mutual Information）是用來衡量兩個(gè)數(shù)據(jù)分布的吻合程度。也是一有用的信息度量，它是指兩個(gè)事件集合之間的相關(guān)性?；バ畔⒃酱?，詞條和類別的相關(guān)程度也越大。NMI (Normalized Mutual Information) 即歸一化互信息：

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

其中,

可以分別看作樣本 (document) 屬于聚類簇, 屬于類別, 同時(shí)屬于的概率。第二個(gè)等價(jià)式子則是由概率的極大似然估計(jì)推導(dǎo)而來。

互信息

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

互信息的最小值為 0, 當(dāng)類簇相對(duì)于類別只是隨機(jī)的, 也就是說兩者獨(dú)立的情況下,對(duì)于未帶來任何有用的信息.如果得到的與關(guān)系越密切, 那么

值越大。如果完整重現(xiàn)了, 此時(shí)互信息最大：

當(dāng)K=N時(shí),即類簇?cái)?shù)和樣本個(gè)數(shù)相等，MI 也能達(dá)到最大值。所以 MI 也存在和純度類似的問題,即它并不對(duì)簇?cái)?shù)目較大的聚類結(jié)果進(jìn)行懲罰,因此也不能在其他條件一樣的情況下,對(duì)簇?cái)?shù)目越小越好的這種期望進(jìn)行形式化。NMI 則可以解決上述問題,因?yàn)殪貢?huì)隨著簇的數(shù)目的增長而增大。當(dāng)K=N時(shí),

會(huì)達(dá)到其最大值

, 此時(shí)就能保證 NMI 的值較低。之所以采用

作為分母是因?yàn)樗?/p>

的緊上界, 因此可以保證

。

示例：

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

先計(jì)算聯(lián)合概率分布

代碼實(shí)現(xiàn)：

sklearn中自帶的方法：

from sklearn.metrics.cluster import normalized_mutual_info_scoreprint(normalized_mutual_info_score([0, 0, 1, 1], [0, 0, 1, 1]))

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

假設(shè)U與V是對(duì)N個(gè)樣本標(biāo)簽的分配情況，則兩種分布的熵（熵表示的是不確定程度）分別為：

其中：

• 是從U中隨機(jī)選取的對(duì)象到類的概率
• 從V中隨機(jī)選取的對(duì)象到類的概率

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

其中

是隨機(jī)選擇的對(duì)象落入兩個(gè)類的概率和。

調(diào)整互信息（Adjusted mutual information）定義為：

MI的期望可以用以下公式來計(jì)算。在這個(gè)方程式中，

為元素的數(shù)量，

為元素的數(shù)量：

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

優(yōu)點(diǎn)

• 隨機(jī)（統(tǒng)一）標(biāo)簽分配的AMI評(píng)分接近0）
• 有界范圍 [0, 1]: 接近 0 的值表示兩個(gè)主要獨(dú)立的標(biāo)簽分配，而接近 1 的值表示重要的一致性。此外，正好 0 的值表示 purely（純粹） 獨(dú)立標(biāo)簽分配，正好為 1 的 AMI 表示兩個(gè)標(biāo)簽分配相等（有或者沒有 permutation）。
• 對(duì)簇的結(jié)構(gòu)沒有作出任何假設(shè): 可以用于比較聚類算法

缺點(diǎn)：

• 與 inertia 相反， MI-based measures 需要了解 ground truth classes，而在實(shí)踐中幾乎不可用，或者需要人工標(biāo)注或手動(dòng)分配（如在監(jiān)督學(xué)習(xí)環(huán)境中）。然而，基于 MI-based measures （基于 MI 的測量方式）也可用于純無人監(jiān)控的設(shè)置，作為可用于聚類模型選擇的 Consensus Index （共識(shí)索引）的構(gòu)建塊。
• NMI 和 MI 沒有調(diào)整機(jī)會(huì)。

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

Positive:

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

Negative:

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

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

RI取值范圍為[0,1]，值越大意味著聚類結(jié)果與真實(shí)情況越吻合。

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)

對(duì)于隨機(jī)結(jié)果，RI并不能保證分?jǐn)?shù)接近零。為了實(shí)現(xiàn)“在聚類結(jié)果隨機(jī)產(chǎn)生的情況下，指標(biāo)應(yīng)該接近零”，調(diào)整蘭德系數(shù)（Adjusted rand index）被提出，它具有更高的區(qū)分度：

ARI取值范圍為[-1,1]，值越大意味著聚類結(jié)果與真實(shí)情況越吻合。從廣義的角度來講，ARI衡量的是兩個(gè)數(shù)據(jù)分布的吻合程度。

優(yōu)點(diǎn)：

• 對(duì)任意數(shù)量的聚類中心和樣本數(shù)，隨機(jī)聚類的ARI都非常接近于0
• 取值在［－1，1］之間，負(fù)數(shù)代表結(jié)果不好，越接近于1越好
• 對(duì)簇的結(jié)構(gòu)不需作出任何假設(shè)：可以用于比較聚類算法。

缺點(diǎn)：

• 與 inertia 相反，ARI 需要 ground truth classes 的相關(guān)知識(shí)，ARI需要真實(shí)標(biāo)簽，而在實(shí)踐中幾乎不可用，或者需要人工標(biāo)注者手動(dòng)分配（如在監(jiān)督學(xué)習(xí)環(huán)境中）。然而，ARI 還可以在 purely unsupervised setting （純粹無監(jiān)督的設(shè)置中）作為可用于 聚類模型選擇（TODO）的共識(shí)索引的構(gòu)建塊。

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

中的大于 1, 此時(shí)實(shí)際上也相當(dāng)于賦予召回率更大的權(quán)重：

RI方法有個(gè)特點(diǎn)就是把準(zhǔn)確率和召回率看得同等重要，事實(shí)上有時(shí)候我們可能需要某一特性更多一點(diǎn)，這時(shí)候就適合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)

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

代碼實(shí)現(xiàn)：

說V-measure之前要先介紹兩個(gè)指標(biāo)：

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

同質(zhì)性和完整性分?jǐn)?shù)基于以下公式得出：

其中

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

是類熵，公式為：

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

V-measure是同質(zhì)性homogeneity和完整性completeness的調(diào)和平均數(shù)，V-measure取值范圍為 [0,1]，越大越好，但當(dāng)樣本量較小或聚類數(shù)據(jù)較多的情況，推薦使用AMI和ARI。公式：

代碼實(shí)現(xiàn)：

from sklearn import metricslabels_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))

優(yōu)點(diǎn)：

• 分?jǐn)?shù)明確：從0到1反應(yīng)出最差到最優(yōu)的表現(xiàn)；
• 解釋直觀：差的調(diào)和平均數(shù)可以在同質(zhì)性和完整性方面做定性的分析；
• 對(duì)簇結(jié)構(gòu)不作假設(shè)：可以比較兩種聚類算法如k均值算法和譜聚類算法的結(jié)果。

缺點(diǎn)：

• 以前引入的度量在隨機(jī)標(biāo)記方面沒有規(guī)范化，這意味著，根據(jù)樣本數(shù)，集群和先驗(yàn)知識(shí)，完全隨機(jī)標(biāo)簽并不總是產(chǎn)生相同的完整性和均勻性的值，所得調(diào)和平均值V-measure也不相同。特別是，隨機(jī)標(biāo)記不會(huì)產(chǎn)生零分，特別是當(dāng)簇的數(shù)量很大時(shí)。
• 當(dāng)樣本數(shù)大于一千，聚類數(shù)小于10時(shí)，可以安全地忽略該問題。對(duì)于較小的樣本量或更大數(shù)量的集群，使用經(jīng)過調(diào)整的指數(shù)（如調(diào)整蘭德指數(shù)）更為安全。
• 這些指標(biāo)要求的先驗(yàn)知識(shí)，在實(shí)踐中幾乎不可用或需要手動(dòng)分配的人作注解者（如在監(jiān)督學(xué)習(xí)環(huán)境中）。

該指數(shù)用于量化兩個(gè)數(shù)據(jù)集之間的相似性，該值得范圍為0-1.其中越大表明兩個(gè)數(shù)據(jù)集越相似：

該指數(shù)和近年來的IOU計(jì)算方法一致

該指數(shù)是基于jaccard指數(shù)上將TP的權(quán)重置為2倍。