本文主要是介绍聚类算法指标整理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• 前言
• 纯度(purity)
• • 纯度的计算Python代码
• 标准互信息(NMI)
• • 熵
  • 互信息
  • 标准互信息
  • MI 和 NMI的计算实现 Python 版
• 调整互信息(AMI)
• • 示例代码
• 兰德系数(Rand Index)
• • 示例代码
• 调整兰德系数(Adjusted Rand index)
• • 示例代码

前言

本文主要介绍聚类算法的一些常见评测指标。

假设某一种算法得到聚类结果为:

A = [ 1 2 1 1 1 1 1 2 2 2 2 3 1 1 3 3 3 ] \mathrm{A}=\left[\begin{array}{lllllllll} 1 & 2 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 3 & 1 & 1 & 3 & 3 & 3 \end{array}\right] A=[1​2​1​1​1​1​1​2​2​2​2​3​1​1​3​3​3​]

标准的聚类结果为：
B = [ 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 ] \mathrm{B}=\left[\begin{array}{llllllll} 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 3 \end{array}\right] B=[1​1​1​1​1​1​2​2​2​2​2​2​3​3​3​3​3​]

那么如何评价该算法的聚类效果？

纯度(purity)

把每个簇中最多的类作为这个簇所代表的类，然后计算正确分配的类的数量，然后除以总数：

纯度计算如下：

 purity  = (  cluster  A +  cluster  B +  cluster  C )  total  = ( 4 + 5 + 4 ) 18 = 0.722 \text { purity }=\frac{(\text { cluster } A+\text { cluster } B+\text { cluster } C)}{\text { total }}=\frac{(4+5+4)}{18}=0.722  purity = total ( cluster A+ cluster B+ cluster C)​=18(4+5+4)​=0.722

一般而言，纯度随着clusters数量的增加而增加。例如，将每个样本结果分为一个单独的簇，此时纯度为1。鉴于此，不能简单用纯度来衡量聚类质量与聚类数量之间的关系。

纯度的计算Python代码

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)

熵

标准互信息(Normalized mutual information, NMI)这个指标源自信息论，所以需要先了解熵(entropy)的概念。熵这个概念是用于量化不确定性，熵的定义如下：
H ( p ) = − ∑ i p i log ⁡ 2 ( p i ) H(p)=-\sum_{i} p_{i} \log _{2}\left(p_{i}\right) H(p)=−i∑​pi​log2​(pi​)

其中 P i P_i Pi​表示label为 i i i的概率。延续上述示例，可以计算其熵。
class A ： 6 / 18
class B ：7 / 18
class C ：5 / 18

 entropy = − ( ( 6 18 ) ⋅ log ⁡ ( 6 18 ) ) − ( ( 7 18 ) ⋅ log ⁡ ( 7 18 ) ) − ( ( 5 18 ) ⋅ log ⁡ ( 5 18 ) ) \text { entropy}=-\left(\left(\frac{6}{18}\right) \cdot \log \left(\frac{6}{18}\right)\right)-\left(\left(\frac{7}{18}\right) \cdot \log \left(\frac{7}{18}\right)\right)-\left(\left(\frac{5}{18}\right) \cdot \log \left(\frac{5}{18}\right)\right)  entropy=−((186​)⋅log(186​))−((187​)⋅log(187​))−((185​)⋅log(185​))
其值为 1.089。需要注意的是：当类别或标签分布均匀时，熵值比较高。

熵随着不确定性的减小而减小。假设我们有两个类，其中类A中有9个数据点，类B中有1个数据点。在这种情况下，如果我们要预测一个随机选择的数据点的类别，我们会比之前的情况更确定。这是因为此时熵计算如下，结果值为0.325：
 entropy  = − ( ( 9 10 ) ⋅ log ⁡ ( 9 10 ) ) − ( ( 1 10 ) ⋅ log ⁡ ( 1 10 ) ) \text { entropy }=-\left(\left(\frac{9}{10}\right) \cdot \log \left(\frac{9}{10}\right)\right)-\left(\left(\frac{1}{10}\right) \cdot \log \left(\frac{1}{10}\right)\right)  entropy =−((109​)⋅log(109​))−((101​)⋅log(101​))

以上即为熵的概念。

互信息

互信息是用以衡量数据分布之间的相关性。互信息越高，相关性也越高。两个离散随机变量 X X X 和 Y Y Y的互信息定义如下：

M I ( X , Y ) = ∑ x = 1 ∣ X ∣ ∑ y = 1 ∣ Y ∣ P ( x , y ) log ⁡ ( P ( x , y ) P ( x ) P ( y ) ) M I(X, Y)=\sum_{x=1}^{|X|} \sum_{y=1}^{|Y|} P(x, y) \log \left(\frac{P(x, y)}{P(x) P(y)}\right) MI(X,Y)=x=1∑∣X∣​y=1∑∣Y∣​P(x,y)log(P(x)P(y)P(x,y)​)

其中 p ( x , y ) p(x,y) p(x,y) 是 X X X 和 Y Y Y 的联合概率分布函数，而 p ( x ) p(x) p(x)和 p ( y ) p(y) p(y)分别是 X X X 和 Y Y Y 的边缘概率分布函数。 ∣ X ∣ 和 ∣ Y ∣ |X|和|Y| ∣X∣和∣Y∣ 分别表示两个变量的取值集合范围。

以决策树为例，特征A对训练数据集D的信息增益，定义为集合D的经验熵 H ( D ) H(D) H(D)与特征A给定条件下D的经验条件熵 H ( D ∣ A ) H(D|A) H(D∣A)之差，这2者的差值即为互信息。换句话说，熵 H ( Y ) H(Y) H(Y)与条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X)之差称为互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

以背景问题为例，可以进行如下计算。

首先计算上式分子中联合概率分布 P ( i , j ) = ∣ X i ∩ Y j ∣ N P(i, j)=\frac{\left|X_{i} \cap Y_{j}\right|}{N} P(i,j)=N∣Xi​∩Yj​∣​。PS: X i X_i Xi​等同于 x x x, Y j Y_j Yj​等同于 y y y。

其中红色线框表示 P ( 1 , 1 ) P(1,1) P(1,1)，即预测结果为类别1，标准为类别1。依次类推，可以得到全部的 P ( i , j ) P(i,j) P(i,j)值。

P ( 1 , 1 ) = 5 / 17 , P ( 1 , 2 ) = 1 / 17 , P ( 1 , 3 ) = 2 / 17 P ( 2 , 1 ) = 1 / 17 , P ( 2 , 2 ) = 4 / 17 , P ( 2 , 3 ) = 0 P ( 3 , 1 ) = 0 , P ( 3 , 2 ) = 1 / 17 , P ( 3 , 3 ) = 3 / 17 \begin{aligned} &P(1,1)=5 / 17, P(1,2)=1 / 17, P(1,3)=2 / 17 \\ &P(2,1)=1 / 17, P(2,2)=4 / 17, P(2,3)=0 \\ &P(3,1)=0, P(3,2)=1 / 17, P(3,3)=3 / 17 \end{aligned} ​P(1,1)=5/17,P(1,2)=1/17,P(1,3)=2/17P(2,1)=1/17,P(2,2)=4/17,P(2,3)=0P(3,1)=0,P(3,2)=1/17,P(3,3)=3/17​

再计算分母中概率函数 P ( i ) = X i / N , P ( i ) P(i)=X_{i} / N, P(i) P(i)=Xi​/N,P(i) 为 i i i 的概率分布函数, P ( j ) P(j) P(j) 为 j j j 的概率分布函数：

对于 P ( i ) P(i) P(i) ：
P ( 1 ) = 8 / 17 , P ( 2 ) = 5 / 17 , p ( 3 ) = 4 / 17 P(1)=8 / 17, P(2)=5 / 17, p(3)=4 / 17 P(1)=8/17,P(2)=5/17,p(3)=4/17
即统计算法预测结果中，各个类别的占比。

对于 P ( j ) : P(j): P(j):
P ( 1 ) = 6 / 17 , P ( 2 ) = 6 / 17 , P ( 3 ) = 5 / 17 P(1)=6 / 17, P(2)=6 / 17, P(3)=5 / 17 P(1)=6/17,P(2)=6/17,P(3)=5/17
即统计标准结果中，各个类别的占比。

据此，可以计算得到互信息 MI = 0.5654
M I = P ( 1 , 1 ) ∗ log ⁡ P ( 1 , 1 ) P ( i = 1 ) P ( j = 1 ) + P ( 1 , 2 ) ∗ log ⁡ P ( 1 , 2 ) P ( i = 1 ) P ( j = 2 ) + P ( 1 , 3 ) ∗ log ⁡ P ( 1 , 3 ) P ( i = 1 ) P ( j = 3 ) + P ( 2 , 1 ) ∗ log ⁡ P ( 2 , 1 ) P ( i = 2 ) P ( j = 1 ) + P ( 2 , 2 ) ∗ log ⁡ P ( 2 , 2 ) P ( i = 2 ) P ( j = 2 ) + P ( 2 , 3 ) ∗ log ⁡ P ( 2 , 3 ) P ( i = 2 ) P ( j = 3 ) + P ( 3 , 1 ) ∗ log ⁡ P ( 3 , 1 ) P ( i = 3 ) P ( j = 1 ) + P ( 3 , 2 ) ∗ log ⁡ P ( 3 , 2 ) P ( i = 3 ) P ( j = 2 ) + P ( 3 , 3 ) ∗ log ⁡ P ( 3 , 3 ) P ( i = 3 ) P ( j = 3 ) MI = P(1,1)*\log \frac{P(1, 1)}{P(i=1)P(j=1)} + P(1,2)*\log \frac{P(1, 2)}{P(i=1)P(j=2)} + P(1,3)*\log \frac{P(1, 3)}{P(i=1)P(j=3)} + \\ P(2,1)*\log \frac{P(2, 1)}{P(i=2)P(j=1)} + P(2,2)*\log \frac{P(2, 2)}{P(i=2)P(j=2)} + P(2,3)*\log \frac{P(2, 3)}{P(i=2)P(j=3)} + \\ P(3,1)*\log \frac{P(3, 1)}{P(i=3)P(j=1)} + P(3,2)*\log \frac{P(3, 2)}{P(i=3)P(j=2)} + P(3,3)*\log \frac{P(3, 3)}{P(i=3)P(j=3)} MI=P(1,1)∗logP(i=1)P(j=1)P(1,1)​+P(1,2)∗logP(i=1)P(j=2)P(1,2)​+P(1,3)∗logP(i=1)P(j=3)P(1,3)​+P(2,1)∗logP(i=2)P(j=1)P(2,1)​+P(2,2)∗logP(i=2)P(j=2)P(2,2)​+P(2,3)∗logP(i=2)P(j=3)P(2,3)​+P(3,1)∗logP(i=3)P(j=1)P(3,1)​+P(3,2)∗logP(i=3)P(j=2)P(3,2)​+P(3,3)∗logP(i=3)P(j=3)P(3,3)​

PS: 以下证明了互信息和熵之间的关系

I ( X ; Y ) = ∑ x , y p ( x , y ) log ⁡ p ( x , y ) p ( x ) p ( y ) = ∑ x , y p ( x , y ) log ⁡ p ( x , y ) p ( x ) − ∑ x , y p ( x , y ) log ⁡ p ( y ) = ∑ x , y p ( x ) p ( y ∣ x ) log ⁡ p ( y ∣ x ) − ∑ x , y p ( x , y ) log ⁡ p ( y ) = ∑ x p ( x ) ( ∑ y p ( y ∣ x ) log ⁡ p ( y ∣ x ) ) − ∑ y log ⁡ p ( y ) ( ∑ x p ( x , y ) ) = − ∑ x p ( x ) H ( Y ∣ X = x ) − ∑ y log ⁡ p ( y ) p ( y ) = − H ( Y ∣ X ) + H ( Y ) = H ( Y ) − H ( Y ∣ X ) \begin{aligned} I(X ; Y) &=\sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x) p(y)} \\ &=\sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x)}-\sum_{x, y} p(x, y) \log p(y) \\ &=\sum_{x, y} p(x) p(y \mid x) \log p(y \mid x)-\sum_{x, y} p(x, y) \log p(y) \\ &=\sum_{x} p(x)\left(\sum_{y} p(y \mid x) \log p(y \mid x)\right)-\sum_{y} \log p(y)\left(\sum_{x} p(x, y)\right) \\ &=-\sum_{x} p(x) H(Y \mid X=x)-\sum_{y} \log p(y) p(y) \\ &=-H(Y \mid X)+H(Y) \\ &=H(Y)-H(Y \mid X) \end{aligned} I(X;Y)​=x,y∑​p(x,y)logp(x)p(y)p(x,y)​=x,y∑​p(x,y)logp(x)p(x,y)​−x,y∑​p(x,y)logp(y)=x,y∑​p(x)p(y∣x)logp(y∣x)−x,y∑​p(x,y)logp(y)=x∑​p(x)(y∑​p(y∣x)logp(y∣x))−y∑​logp(y)(x∑​p(x,y))=−x∑​p(x)H(Y∣X=x)−y∑​logp(y)p(y)=−H(Y∣X)+H(Y)=H(Y)−H(Y∣X)​
关系如下图所示：

标准互信息

互信息 I ( X ; Y ) I(X ; Y) I(X;Y)用于衡量当得知算法聚类结果是什么时(Y)，关于分类的已知知识(X)会增加的信息量。如果聚类相对于已知的分类是无关的，那么 I ( X ; Y ) I(X ; Y) I(X;Y)的最小值为0。此时，知道文本在特定的簇中不会给我们提供关于它类别的新信息。当聚类数量=样本数量，即每个文本都在一个类中时，会达到最大互信息值。所以，互信息有着和纯度同样的问题：不惩罚聚类的细分聚类结果。为此，需要引入其他条件相同的时候，簇越少越好。为更好的比较不同聚类结果，提出了标准化互信息(Normalized mutual information，NMI) 的概念， 标准化互信息有几个不同的版本，大体思想都是相同的，都是用熵做分母将MI值调整到0与1之间，一个比较常见的实现如下所示：

N M I ( X , Y ) = M I ( X , Y ) ( H ( X ) + H ( Y ) ) / 2 N M I(X, Y)=\frac{M I(X, Y)}{(H(X)+H(Y))/2} NMI(X,Y)=(H(X)+H(Y))/2MI(X,Y)​

上式分母 ( H ( X ) + H ( Y ) ) / 2 (H(X)+H(Y))/2 (H(X)+H(Y))/2通过标准化解决了这个问题。为何分母要选择这种特殊的形式，原因是 ( H ( X ) + H ( Y ) ) / 2 (H(X)+H(Y))/2 (H(X)+H(Y))/2是 M I ( X , Y ) M I(X, Y) MI(X,Y)的一个紧上界。同时这可以确保NMI的值始终介于0与1之间。

N M I ( X , Y ) = 2 M I ( X , Y ) H ( X ) + H ( Y ) N M I(X, Y)=\frac{2 M I(X, Y)}{H(X)+H(Y)} NMI(X,Y)=H(X)+H(Y)2MI(X,Y)​

对上面的背景示例计算各自的熵如下：

H ( X ) = P ( 1 ) log ⁡ 2 ( P ( 1 ) ) + P ( 2 ) log ⁡ 2 ( P ( 2 ) ) + P ( 3 ) log ⁡ 2 ( P ( 3 ) ) H ( Y ) = P ′ ( 1 ) log ⁡ 2 ( P ′ ( 1 ) ) + P ′ ( 2 ) log ⁡ 2 ( P ′ ( 2 ) ) + P ′ ( 3 ) log ⁡ 2 ( P ′ ( 3 ) ) \begin{aligned} &H(X)=P(1) \log _{2}(P(1))+P(2) \log _{2}(P(2))+P(3) \log _{2}(P(3)) \\ &H(Y)=P^{\prime}(1) \log _{2}\left(P^{\prime}(1)\right)+P^{\prime}(2) \log _{2}\left(P^{\prime}(2)\right)+P^{\prime}(3) \log _{2}\left(P^{\prime}(3)\right) \end{aligned} ​H(X)=P(1)log2​(P(1))+P(2)log2​(P(2))+P(3)log2​(P(3))H(Y)=P′(1)log2​(P′(1))+P′(2)log2​(P′(2))+P′(3)log2​(P′(3))​

PS: 这里为了区分2个变量的概率分布分别用 P P P 和 P ′ P^{\prime} P′ 来表示。

综上，即可计算NMI的值。

MI 和 NMI的计算实现 Python 版

import math
import numpy as np
from sklearn import metrics


def NMI(A, B):
    # 样本点数
    total = len(A)
    A_ids = set(A)
    B_ids = set(B)
    # 互信息计算
    MI = 0
    eps = 1.4e-45
    for idA in A_ids:
        for idB in B_ids:
            idAOccur = np.where(A == idA)  # 输出满足条件的元素的下标
            idBOccur = np.where(B == idB)
            idABOccur = np.intersect1d(idAOccur, idBOccur)  # Find the intersection of two arrays.
            px = 1.0 * len(idAOccur[0]) / total
            py = 1.0 * len(idBOccur[0]) / total
            pxy = 1.0 * len(idABOccur) / total
            MI = MI + pxy * math.log(pxy / (px * py) + eps, 2)
    print("MI=", MI)
    # 标准化互信息
    Hx = 0
    for idA in A_ids:
        idAOccurCount = 1.0 * len(np.where(A == idA)[0])
        Hx = Hx - (idAOccurCount / total) * math.log(idAOccurCount / total + eps, 2)
        Hy = 0
    for idB in B_ids:
        idBOccurCount = 1.0 * len(np.where(B == idB)[0])
        Hy = Hy - (idBOccurCount / total) * math.log(idBOccurCount / total + eps, 2)
    NMI = 2.0 * MI / (Hx + Hy)  # 标准化互信息
    print("NMI=", NMI)
    # return NMI


if __name__ == '__main__':
    A = np.array([1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3])
    B = np.array([1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 3, 3, 3])
    NMI(A, B)
    print("metrics.normalized_mutual_info_score=", metrics.normalized_mutual_info_score(A, B))

运行结果如下：

MI= 0.565445018842856
NMI= 0.3645617718571898
metrics.normalized_mutual_info_score= 0.36456177185718985

调整互信息(AMI)

上述的NMI对于随机的分类结果，并不会给出一个近似0的得分，为此提出 调整互信息(Adjusted mutual information，AMI)。AMI对于随机的聚类结果会给出接近于0的得分。

A M I = M I − E [ M I ] mean ⁡ ( H ( Y ) , H ( X ) ) − E [ M I ] \mathrm{AMI}=\frac{\mathrm{MI}-E[\mathrm{MI}]}{\operatorname{mean}(H(Y), H(X))-E[\mathrm{MI}]} AMI=mean(H(Y),H(X))−E[MI]MI−E[MI]​

互信息(MI)和标准互信息(NMI)的值都会受到聚类的类别数K的影响，而AMI则不会受到干扰，取值范围为-1到1，数值越大，两种聚类结果越接近。更多关于定义的细节可以参考scikit中AMI的计算

示例代码

>>> from sklearn.metrics.cluster import adjusted_mutual_info_score
>>> adjusted_mutual_info_score([0, 0, 1, 1], [0, 0, 1, 1])
... 
1.0
>>> adjusted_mutual_info_score([0, 0, 1, 1], [1, 1, 0, 0])
... 
1.0

>>> adjusted_mutual_info_score([0, 0, 0, 0], [0, 1, 2, 3])
... 
0.0

兰德系数(Rand Index)

理想情况下，当且仅当两个文本相似时，将这两者分在同一个簇里。真实的划分存在以下4种情况：

Positive:

• TP： 将两篇相似文本归入一个簇 (同 – 同)
• TN： 将两篇不相似的文本归入不同的簇 (不同 – 不同)

Negative:

• FP： 将两篇不相似的文本归入同一簇 (不同 – 同)
• FN： 将两篇相似的文本归入不同簇 (同- 不同)

小结下：

• 真阳性（TP）：将两个相似的文本分配在同一个簇中
• 真阴性（TN）：将两个不相似的文本分配在不同的簇中
• 假阳性（FP）：将两个不相似的文本分配在同一个簇中
• 假阴性（FN）：将两个相似的文本分配在不同的簇中

兰德系数（Rand Index，RI）衡量在这些决策中，正确决策的百分比，即准确度（accuracy）。RI取值范围为[0,1]，值越大意味着聚类结果与真实情况越吻合。RI的定义如下：

R I = (number of agreeing pairs) / (number of pairs) R I = T P + T N T P + F P + T F + F N = T P + T N C N 2 RI = \text{(number of agreeing pairs)} / \text{(number of pairs)} \\ R I=\frac{T P+T N}{T P+F P+T F+F N}=\frac{T P+T N}{C_{N}^{2}} RI=(number of agreeing pairs)/(number of pairs)RI=TP+FP+TF+FNTP+TN​=CN2​TP+TN​

示例代码

>>> from sklearn.metrics.cluster import rand_score
>>> rand_score([0, 0, 1, 1], [1, 1, 0, 0])
1.0

>>> rand_score([0, 0, 1, 2], [0, 0, 1, 1])
0.83...

调整兰德系数(Adjusted Rand index)

对于随机结果，RI并不能保证分数接近零。为了实现“在聚类结果随机产生的情况下，指标应该接近零”，调整兰德系数（Adjusted rand index）被提出，它具有更高的区分度：

ARI = (RI - Expected_RI) / (max(RI) - Expected_RI)

ARI取值范围为[-1,1]，值越大意味着聚类结果与真实情况越吻合。从广义的角度来讲，ARI衡量的是两个数据分布的吻合程度。

示例代码

from sklearn.metrics.cluster import adjusted_rand_score
print(adjusted_rand_score([0, 0, 1, 1], [0, 0, 1, 1]))  # 1.0
print(adjusted_rand_score([0, 0, 1, 1], [1, 1, 0, 0]))  # 1.0

print(adjusted_rand_score([0, 0, 1, 2], [0, 0, 1, 1]))  # 0.57

print(adjusted_rand_score([0, 0, 0, 0], [0, 1, 2, 3]))  # 0, 当聚类结果各自独立

这篇关于聚类算法指标整理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！