11.6 聚类外部评价指标#
经过前面几节内容的介绍，相信各位读者对于聚类算法已经有了一定的了解。不过正如之前介绍的分类算法模型一样，对于聚类算法来讲同样也会通过一些评价指标来衡量聚类结果的优与劣。在聚类任务中，常见的评价指标有纯度（Purity）、兰德系数（Rand Index, RI）、F值（Fscore）和调整兰德系数（Adjusted Rand Index, ARI）等。之所以称之为外部评价指标（External metrics），是因为这样的评价指标在计算结果的时候需要依赖样本的真实标签，在11.8节内容中我们还将介绍只依赖于样本本身的评价方法，即内部评价指标。下面，分别来对这4种指标一一进行介绍。
假设现在有一批文档，一共包含叉形、圆形与菱形3个类别。此时需要对其进行聚类处理，并且现在某聚类算法的聚类结果如图11-11所示。
从图11-11可知，该聚类算法将所有的文本一共划分成了3个簇。面对这样的聚类结果，应该怎样来对其进行评判呢？
11.6.1 聚类纯度#
在聚类结果的评估标准中，一种最简单最直观的方法就是计算它的聚类纯度。别看纯度听起来很陌生，但实际上和分类问题中的准确率有着异曲同工之妙。因为聚类纯度的总体思想也用聚类正确的样本数除以总的样本数，因此它也经常被称为聚类的准确率。只是对于聚类后的结果我们并不知道每个簇所对应的真实类别，因此需要取每种情况下的最大值。具体地，将纯度的计算公式定义为[1]
$$ P=(\Omega ,\mathbb{C})=\frac{1}{N}\sum\limits_{k}{\underset{j}{\mathop{\max }}\,}|{{\omega }_{k}}\bigcap {{c}_{j}}|\tag{11-7} $$其中，$N$表示总的样本数； $\Omega=\{\omega_1,\omega_2,...,\omega_K\}$表每一个聚类后的簇； 而$\mathbb{C}=\{c_1,_2,...c_J\}$表示正确的类别； $\omega _k$表示聚类后第$k$个簇中的所有样本； $c_j$表示第$j$个类别的真实样本数。在这里$P$的取值范围为$[0,1]$，其值越大表示聚类效果越好。
有了式(11-7)以后就可以通过它来计算图11-11中聚类结果的纯度。对于第1个簇来讲，$|{{\omega }_{1}}\bigcap {{c}_{1}}|=5$，$|{{\omega }_{1}}\bigcap {{c}_{2}}|=1$，$|{{\omega }_{1}}\bigcap {{c}_{3}}|=0$，可以看出此时假设$c_1$对应的是叉形、$c_2$对应的是圆形、$c_3$对应的是菱形（这个对应顺序没有任何关系），因此第1个簇聚类正确的样本数为5。同理，按照这样的方法可以计算得到第2个簇和第3个簇聚类正确的样本数分别为4和3，所以对于图11-11所示的聚类结果来讲，其最终的纯度为
$$ P=\frac{5+4+3}{17}\approx 0.706\tag{11-8} $$11.6.2 兰德系数与$\text{F}$值#
在介绍完纯度这一评价指标后，我们再来看一看兰德系数（Rand Index）和$\text{F}$值。虽然兰德系数听起来是一个陌生的名词，但它的计算过程却与准确率的计算过程类似。同时，虽然这里也有一个叫做$\text{F}$值的指标，并且它的计算过程也和分类指标中的$\text{F}$值类似，但是两者却有着本质的差别。讲了这么多，这两个指标到底该怎么算呢？同分类问题中的混淆矩阵类似，这里也要先定义4种情况以便进行计数，然后进行指标的计算。
1. 计算原理
为了说明兰德系数背后的思想，我们这里还是以图11-11中的聚类结果为例进行说明。现在请各位读者想象一下，把这3个簇想象成3个黑色的布袋。对于任意一个布袋来讲： ①如果从里面任取两个样本均是同一个类别，这就表示这个布袋中的所有样本都算作是聚类正确的。②相反，如果取出来后发现存在两个样本不是同一类别的情况，则说明存在着聚类错误的情况。
其次，对于任意两个布袋来讲。③如果任意从两个布袋中各取一个样本后发现两者均是不同类别的，这就表示两个布袋中的样本都被聚类正确了。④相反，如果发现取出来的两个样本存在相同的情况，则说明此时也存在着聚类错误的情况。各位读者想一想，此时应该再也找不出第5种情况了。由此，可以做出如下定义。
TP： 表示两个同类样本点在同一个簇（布袋）中的情况数量，即同簇同类的样本对。
FP： 表示两个非同类样本点在同一个簇中的情况数量，同簇异类的样本对。
TN： 表示两个非同类样本点分别在两个簇中的情况数量，即异簇异类的样本对。
FN： 表示两个同类样本点分别在两个簇中的情况数量，即异簇同类的样本对。
由此，根据图11-11所示的聚类结果便可以得到如表11-3所示的对混淆矩阵（Pair Confusion Matrix）。
其中表11-3里TP=20的含义是在所有簇的任一簇中任取两个样本均是同一类别的情况总数。TN=72则表示在所有簇的任两簇中各取一个样本均不是同一类别的情况总数。
有了上面各种情况的统计值后便可以定义出兰德系数和$\text{F}$值的计算公式为[1]
$$ \text{RI}=\frac{\text{TP}+\text{TN}}{\text{TP}+\text{FP}+\text{FN}+\text{TN}}\tag{11-9} $$$$ \text{Precision}=\frac{\text{TP}}{\text{TP}+\text{FP}}\tag{11-10} $$$$ \text{Recall}=\frac{\text{TP}}{\text{TP}+\text{FN}} \tag{11-11} $$$$ {{\text{F}}_{\beta }}=(1+{{\beta }^{2}})\frac{\text{Precision}\cdot \text{Recall}}{{{\beta }^{2}}\cdot \text{Precision}+\text{Recall}}\tag{11-12} $$从上面的计算公式来看，式(11-9)~式(11-12)从形式上看都非常像分类问题中的准确率与$\text{F}$值，但是有着本质的区别。同时，在这里$\text{RI}$和$\text{F}_{\beta}$ 的取值范围均为$[0,1]$，取值越大表示聚类效果越好。
2. 计算过程
同时，根据式(11-9)~式(11-12)就能够计算得到图11-11中聚类结果的兰德系数和$\text{F}_1$值分别为
$$ \begin{aligned} &\text{RI}=\frac{20+72}{20+20+24+72}\approx 0.68 \\[2ex] &\text{Precision}=\frac{20}{20+20}=0.5 \\[2ex] &\text{Recall}=\frac{20}{20+24}\approx 0.46 \\[2ex] &{{\text{F}}_{1}}=2\times \frac{0.5\times 0.46}{0.5+0.46}\approx 0.48 \end{aligned}\tag{11-13} $$现在最后的结果计算完了，但还有一个疑问没有解决，即表11-3中各个情况下的值到底应该怎么计算。下面我们就来对每个值进行计算。
(1) $\text{TP}$ 表示两个同类样本点在同一个簇中的情况数量，因此根据图11-11中的聚类结果有
$$ \text{TP}=\binom{5}{2}+\binom{4}{2}+\binom{3}{2}+\binom{2}{2}=20\tag{11-14} $$其分别表示的含义是，对于簇1来讲从5个叉形中取2个的情况； 对于簇2来讲从4个圆形中取2个的情况； 对于簇3来讲从3个菱形中取2个及从2个叉形中取2个的情况。
在计算完成$\text{TP}$后，我们发现其他3种情况都无法单独地进行计算，因为都是交叉混合的情况，因此可以同时计算多种组合下的情况数。
(2) 由4种情况的定义可知，$\text{TP}+\text{FP}$表示的是同一簇中任取两个样本点的情况数，即包含了同类和非同类，因此根据图11-11中的聚类结果有
$$ \text{TP}+\text{FP}=\binom{6}{2}+\binom{6}{2}+\binom{5}{2}=40\tag{11-15} $$(3) 同理，$\text{TP}+\text{FN}$表示的是任意两个同类样本点分布在同一簇和非同一簇的所有情况的总和，所以有
$$ \text{TP}+\text{FN}=\binom{8}{2}+\binom{5}{2}+\binom{4}{2}=44\tag{11-16} $$其分别表示的含义是，对于叉形样本来讲从8个中任取2个就包含了任意2个样本点在同一簇中和不在同一簇中的所有情况，其他两个类别的含义类似。
(4) 同时，根据前面的分析可知，对于图11-11聚类后的结果不管是在某一个簇中任取2个样本，还是在任意不同的2个簇中各取1个样本，所有可能出现的情况都只有上面的4种情况，所以有
$$ \text{TP}+\text{FP}+\text{TN}+\text{FN}=\binom{17}{2}=136\tag{11-17} $$由此，根据式(11-14)~式(11-17)便可以分别计算出
$$ \text{TP}=20,\;\text{FP}=20,\;\text{FN}=24,\;\text{TN}=72\tag{11-18} $$当然，计算的思路也不止一种，同样还可以用其他的方法来计算。
11.6.3 调整兰德系数#
调整兰德系数是兰德系数的一个改进版本，其目的是为了去掉随机标签对于兰德系数评估结果的影响。例如对于图11-11中的17个样本，如果随机将每个样本都划到一个簇中（也就是17个簇)，则其计算出来的兰德系数仍旧为0.68，此时的$\text{TP}=0$，$\text{FP}=0$，$\text{FN}=44$，$\text{TN}=92$。因此，需要通过一种方法来消除这种随机性对于聚类结果的影响。调整兰德系数引入了随机模型的期望值来对兰德系数进行校正，减弱了随机性带来的影响，它的基本思想是
$$ \text{ARI}=\frac{\text{RI}-\text{期望值}}{\text{最大值}-\text{期望值}}\tag{11-19} $$其中期望值是基于随机划分计算的结果，即通过减去随机划分下的期望值将结果校正到一个更合理的范围内，使得完全随机的聚类结果接近于0，完全聚类正确的结果接近于1，完全聚类错误的结果接近于-1，所以ARI的取值范围为 [-1,1]。可以看出，$\text{ARI}$ 的计算过程其实就类似于4.2.3节中的标准化方法。同时，这里需要注意的是，式(11-19)分子中的 $\text{RI}$ 并不是根据式(11-9)计算来的结果而是一种新的度量，只是思想上同式(11-9)中的一致。
具体的ARI该怎么计算呢？下面还是以图11-11中的聚类结果为例进行讲解。如图11-12所示，$X$表示聚类算法认为的结果，你可以把它看做一个布袋，算法认为每个布袋里的所有样本都是一个类别；而$Y$表示根据正确标签标记后的结果。换句话说，聚类算法之所以把这些样本划到一个簇中，就是因为算法觉得它们应该在一个簇中，也就是$X$所呈现的结果是站在算法的角度，而$Y$则是站在已知标签的角度，指出了$X$中每个簇哪些样本是划分错误的情况。
因此，根据聚类得结果和真实标签便可以得到如下所示的列联表（Contingency Table），它反映了聚类结果与真实类别标签之间的交叉关系：
如表11-4所示，其中$X=\{X_1,X_2,...,X_r\}$表示聚类得到$r$个簇的集合，而$Y=\{Y_1,Y_2,...,Y_s\}$表示根据正确标签对聚类结果修正后的集合，$n_{ij}$表示$X_i$与$Y_j$相交部分的样本数量即${{n}_{ij}}=|{{X}_{i}}\bigcap {{Y}_{j}}|$，$a_i$ 是真实类别 $i$ 中的样本数，$b_j$ 是聚类簇 $j$ 中的样本数。例如对于图11-12中的结果来说，真实类别中的样本数分别为 $a_1=8$ （叉形）、$a_2=5$ （圆形）、$a_3=4$（菱形），聚类簇重的样本数分别为 $b_1=6$、$b_2=6$、$b_3=5$。
根据式(11-9)中的定义可知，RI考量的是聚类结果中同簇同类和异簇异类样本对的总数在所有样本出现情况中的占比，从另一个角度来说也可以称之为聚类正确的情况数在所有情况中的占比。因此，在构造式(11-19)中RI时可以再从一个新的角度来考量，即考虑所有实际聚类结果和真实类别交叉情况下符合同类关系的样本对数量，即此时有
$$ \text{RI} = \sum_{i}\sum_{j}\binom{n_{ij}}{2}\tag{11-20} $$其表示的便是任意聚类簇 $X_i$ 与真实类别 $Y_j$ 交集下任意两个样本的点均为同一类别的情况总数，可以看作是在从同类样本对出现频次的角度来衡量聚类结果的优劣。
根据上面几种聚类评估指标的介绍可以知道，式(11-20)中计算得到的 $\text{RI}$ 值越大，则表示整个聚类结果越好。例如对于图11-12中的示例来说，假如此时聚类结果完全正确，那么我们将会得到如下列联表。
从表11-5的结果可知，根据式(11-20)，此时$\text{RI}$将取到最大值
$$ \text{RI} = \sum_{i=1}^3\sum_{j=1}^3\binom{n_{ij}}{2}=\binom{8}{2}+0+0+0+\binom{5}{2}+0+0+0+\binom{4}{2}=44\tag{11-21} $$进一步，根据式(11-19)可知计算 $\text{ARI}$ 还需要定义期望值和最大值。在 $\text{ARI}$ 中期望值用来描述随机划分下获得同类对的“平均情况”，用于衡量给定的聚类方案相对于完全随机划分的改进程度，其定义为
$$ \text{期望值}=\frac{ \sum\limits_{i}{\binom{a_i}{2}} }{\binom{n}{2}}\cdot \sum\limits_{j}{\binom{b_j}{2}}\tag{11-22} $$在式(11-22)中，$\sum_i\binom{a_i}{2}$ 和 $\sum_j\binom{b_j}{2}$ 分别表示所有真实类别中的同类样本对数量总和以及所有聚类簇中的样本对数量总和，前者关注的是真实类别内部样本的分布，后者关注的则是聚类簇内部样本的分布。因此可以得出，式(11-22)中第1项计算的是任意两个样本为同一类别的概率，而第2项计算的则是在每个聚类簇中任意两个样本点组合的情况总数，所以两者的乘积表示的便是随机情况下聚类簇中每个簇中任意两个样本为同类样本的期望值。
对于式(11-19)中的最大值来说，它的定义为
$$ \text{最大值}=\frac{1}{2}\left[ \sum_{i}{\binom{a_i}{2}}+\sum_{j}{\binom{b_j}{2}} \right]\tag{11-23} $$根据表11-5和式(11-21)的计算过程可知，当且仅当聚类结果完全正确时 $\sum_i\binom{a_i}{2}$ 和 $\sum_j\binom{b_j}{2}$ 相等，且等于 $\text{RI}$，故其最大值不会超过两者的均值，因此式(11-23)可以作为在任意聚类结果中 $\text{RI}$ 的最大值。
最后，根据式(11-19)、式(11-20)、式(11-22)和式(11-23)可得，$\text{ARI}$ 的计算公式[2] [3]为
$$ \text{ARI}=\frac{\sum\limits_{i}{\sum\limits_{j}{\binom{n_{ij}}{2}}}-\left[ \sum\limits_{i}{\binom{a_i}{2}}\sum\limits_{j}{\binom{b_j}{2}} \right]/\binom{n}{2}}{\frac{1}{2}\left[ \sum\limits_{i}{\binom{a_i}{2}}+\sum\limits_{j}{\binom{b_j}{2}} \right]-\left[ \sum\limits_{i}{\binom{a_i}{2}}\sum\limits_{j}{\binom{b_j}{2}} \right]/\binom{n}{2}}\tag{11-24} $$根据图11-12的结果便能得到如下所示的列联表
根据表11-6可得
$$ \begin{aligned} & \sum\limits_{i}{\sum\limits_{j}{\binom{n_{ij}}{2}}}=\binom{5}{2}+\binom{2}{2}+\binom{4}{2}+\binom{3}{2}=20 \\[1ex] & \sum\limits_{i}{\binom{a_i}{2}}=\binom{8}{2}+\binom{5}{2}+\binom{4}{2}=44 \\[1ex] & \sum\limits_{j}{\binom{b_j}{2}}=\binom{6}{2}+\binom{6}{2}+\binom{5}{2}=40 \end{aligned}\tag{11-25} $$所以有
$$ \text{ARI}=\frac{20-44\times 40\div 136}{0.5\times (44+40)-44\times 40\div 136}=\frac{120}{494}\approx 0.24\tag{11-26} $$同时，式(11-24)的计算过程还可以改写为
$$ \text{ARI}=\frac{2\times (\text{TP}\cdot \text{TN}-\text{FN}\cdot \text{FP})}{(\text{TP}+\text{FN})(\text{FN}+\text{TN})+(\text{TP}+\text{FP})(\text{FP}+\text{TN})}\tag{11-27} $$详细来由各位读者有兴趣可以自行探索。
至此，对于聚类算法中常见评价指标的原理就介绍完了。下面再来看一看如何通过Python编码实现上述计算过程。
11.6.4 聚类指标示例代码#
在介绍完各个指标的计算原理以后，再来看如何进行实现和使用，完整示例代码可参见 AllBooKCode/Chapter11/C08_metrics.py 文件
1. 聚类纯度
对于如何实现聚类纯度的代码，其关键在于： ①找到每个聚类标签所对应的真实样本； ②统计真实样本中每个类别的样本数并取最大值，示例代码如下：
1 def accuracy(labels_true, labels_pred):
2 clusters = np.unique(labels_pred)
3 labels_true = np.reshape(labels_true, (-1, 1))
4 labels_pred = np.reshape(labels_pred, (-1, 1))
5 count = []
6 for c in clusters:
7 idx = np.where(labels_pred == c)[0]
8 labels_tmp = labels_true[idx, :].reshape(-1)
9 count.append(np.bincount(labels_tmp).max())
10 return np.sum(count) / labels_true.shape[0]在上述代码中，第2行用来确定预测结果中的簇数量。第7行用来查找每个聚类标签所对应的真实样本的索引。第8行则用来取对应的真实样本。第9行用来计算当前簇中每个真实类别的样本数并取最大值。
2. 兰德系数与F值
通过11.6.3节内容可知，计算兰德系数、$\text{F}$值和调整兰德系数的关键就在于得到这个对混淆矩阵。不过好在sklearn中已经有了现成的方法，这里直接使用即可，因此3个指标的实现过程示例代码如下：
1 from sklearn.metrics.cluster import pair_confusion_matrix
2 def get_rand_index_and_f_measure(labels_true, labels_pred, beta=1.):
3 (tn, fp), (fn, tp) = pair_confusion_matrix(labels_true, labels_pred)
4 ri = (tp + tn) / (tp + tn + fp + fn)
5 ari = 2.*(tp * tn - fn * fp)/((tp + fn)*(fn + tn)+(tp + fp)*(fp + tn))
6 p, r = tp / (tp + fp), tp / (tp + fn)
7 f_beta = (1 + beta ** 2) * (p * r / ((beta ** 2) * p + r))
8 return ri, ari, f_beta在上述代码中，第1行用来导入sklearn中计算对混淆矩阵的函数。第3行用来计算得到对混淆矩阵。第4~5行分别用来计算兰德系数和调整兰德系数。第6~7行用来计算F值。这样，根据上述代码就能够计算得到相应的聚类评估指标，示例代码如下：
1 if __name__ == '__main__':
2 y_pred = [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2]
3 y_true = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 2, 2, 2, 2, 0, 0]
4 purity = accuracy(y_true, y_pred)
5 ri, ari, f_beta=get_rand_index_and_f_measure(y_true, y_pred, beta=1.)
6 print(f"purity:{purity}\nri:{ri}\nari:{ari}\nf_measure:{f_beta}")
7 # 结果
8 purity:0.7058
9 ri:0.6764
10 ari:0.2429
11 f_measure:0.476111.6.5 小结#
在本节中，我们首先详细介绍了4种常见的聚类评价指标的基本原理和详细的计算步骤，包括纯度、F值、兰德系数和调整兰德系数；然后介绍了如何通过Python代码实现各个评价指标的计算；最后以一个模拟的聚类结果为例，演示了如何调用编写完成的代码来计算各个评估指标。
引用#
[1] https://nlp.stanford.edu/IRbook
[2] https://en.wikipedia.org/wiki/Rand_index
[3] PEDREGOSA.scikitlearn: Machine Learning in Python［J］.JMLR 12,2011: 28252830.