前言
本文主要介绍聚类算法的一些常见评测指标。
【更多、更及时内容欢迎留意微信公众号： 小窗幽记机器学习 】
假设某一种算法得到聚类结果为:
$$ \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, 当聚类结果各自独立
【更多、更及时内容欢迎留意微信公众号： 小窗幽记机器学习 】
