前言

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

【更多、更及时内容欢迎留意微信公众号： 小窗幽记机器学习 】

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

$$ \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] $$

标准的聚类结果为：
$$ \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] $$

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

纯度(purity)

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

纯度计算如下：

$$ \text { purity }=\frac{(\text { cluster } A+\text { cluster } B+\text { cluster } C)}{\text { total }}=\frac{(4+5+4)}{18}=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)=-\sum_{i} p_{i} \log _{2}\left(p_{i}\right) $$

其中$P_i$表示label为$i$的概率。延续上述示例，可以计算其熵。
class A ： 6 / 18
class B ：7 / 18
class C ：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) $$
其值为 1.089。需要注意的是：当类别或标签分布均匀时，熵值比较高。

熵随着不确定性的减小而减小。假设我们有两个类，其中类A中有9个数据点，类B中有1个数据点。在这种情况下，如果我们要预测一个随机选择的数据点的类别，我们会比之前的情况更确定。这是因为此时熵计算如下，结果值为0.325：
$$ \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) $$

以上即为熵的概念。

互信息

互信息是用以衡量数据分布之间的相关性。互信息越高，相关性也越高。两个离散随机变量 $X$ 和 $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) $$

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

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

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

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

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

$$ \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(i)=X_{i} / N, P(i)$ 为 $i$ 的概率分布函数, $P(j)$ 为 $j$ 的概率分布函数：

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

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

据此，可以计算得到互信息 MI = 0.5654
$$ 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)} $$

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

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

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

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

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

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

$$ \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} $$

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

综上，即可计算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的得分。

$$ \mathrm{AMI}=\frac{\mathrm{MI}-E[\mathrm{MI}]}{\operatorname{mean}(H(Y), H(X))-E[\mathrm{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的定义如下：

$$ 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}} $$

示例代码

>>> 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, 当聚类结果各自独立

【更多、更及时内容欢迎留意微信公众号： 小窗幽记机器学习 】

机器学习系列 | 02：聚类算法指标整理

前言

纯度(purity)

纯度的计算Python代码

标准互信息(NMI)

熵

互信息

标准互信息

MI 和 NMI的计算实现 Python 版

调整互信息(AMI)

示例代码

兰德系数(Rand Index)

示例代码

调整兰德系数(Adjusted Rand index)

示例代码

大数据与机器学习

热门文章

最新文章

相关课程

相关电子书

相关实验场景