十分钟掌握聚类算法的评估指标

这是我参与8月更文挑战的第18天，活动详情查看：8月更文挑战

前言

聚类算法属于非监督学习，它并不像分类算法那样可以使用训练集或测试集中的数据来计算准确率、召回率等。

那么如何评估聚类算法得好坏呢？

好的聚类算法，一般要求类簇具有：

• 簇内 (intra-cluster) 相似度高
• 簇间 (inter-cluster) 相似度底

一般来说，评估聚类质量有两个标准，内部评估评价指标和外部评估指标。

内部评估的方法

内部评估指标主要基于数据集的集合结构信息从紧致性、分离性、连通性和重叠度等方面对聚类划分进行评价。即基于数据聚类自身进行评估的。

轮廓系数（Silhouette Coefficient）

轮廓系数适用于实际类别信息未知的情况。旨在将某个对象与自己的簇的相似程度和与其他簇的相似程度作比较。

对于单个样本，设a是与它同类别中其他样本的平均距离，b是与它距离最近不同类别中样本的平均距离，其轮廓系数为：

对于一个样本集合，它的轮廓系数是所有样本轮廓系数的平均值。

轮廓系数的取值范围是[-1,1]，同类别样本距离越相近，不同类别样本距离越远，值越大。当值为负数时，说明聚类效果很差。

缺点

不适合基于密度的聚类算法（DBSCAN）。

Calinski-Harabaz指数（Calinski-Harabaz Index）

在真实的分群label不知道的情况下，Calinski-Harabasz可以作为评估模型的一个指标。

Calinski-Harabasz指数通过计算类中各点与类中心的距离平方和来度量类内的紧密度，通过计算各类中心点与数据集中心点距离平方和来度量数据集的分离度，CH指标由分离度与紧密度的比值得到。从而，CH越大代表着类自身越紧密，类与类之间越分散，即更优的聚类结果。

优点

• 当簇的密集且分离较好时，分数更高。
• 得分计算很快，与轮廓系数的对比，最大的优势：快！相差几百倍！毫秒级。

缺点

• 凸的簇的CH指数通常高于其他类型的簇。例如，通过 DBSCAN 获得基于密度的簇；所以，不适合基于密度的聚类算法（DBSCAN）。

戴维森堡丁指数（DBI, Davies-Bouldin Index）

DB指数是计算任意两类别的类内距离平均距离之和除以两聚类中心距离求最大值。DB越小，意味着类内距离越小同时类间距离越大。零是可能的最低值，接近零的值表示更好的分区。

其公式为：

其中，
$s_i$表示簇的每个点与该簇的质心之间的平均距离，也称为簇直径。
$d_{ij}$表示聚类i和j的质心之间的距离。

算法生成的聚类结果越是朝着簇内距离最小（类内相似性最大）和簇间距离最大（类间相似性最小）变化，那么Davies-Bouldin指数就会越小。

缺点：

• 因使用欧式距离，所以对于环状分布聚类评测很差。

外部评估的方法

外部有效指标是指当数据集的外部信息可用时，通过比较聚类划分与外部准则的匹配度，可以评价不同聚类算法的性能。即通过将聚类结果与已经有“ground truth”分类进行对比。

要么通过人进行手动评估，要么通过一些指标在特定的应用场景中进行聚类用法的评估。

不过该方法是有问题的，如果真的有了label，那么还需要聚类干嘛，而且实际应用中，往往都没label；另一方面，这些label只反映了数据集的一个可能的划分方法，它并不能告诉你存在一个不同的更好的聚类算法。

兰德指数（RI, Rand index）

兰德指数是将聚类看成是一系列的决策过程，即对文档集上所有
$N(N-1)/2$ 个【文档对】进行决策。当且仅当两篇文档相似时，我们将它们归入同一簇中。

正确决策:

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

错误决策:

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

RI 则是计算「正确决策」的比率(精确率, accuracy)。

其公式为：

其中，C表示实际类别信息，K表示聚类结果，a表示在C与K中都是同类别的元素对数，b表示在C与K中都是不同类别的元素对数，
$C_2^{n_{samples}}$ 表示数据集中可以组成的对数。

RI取值范围为[0,1]，值越大意味着聚类结果与真实情况越吻合。

调整兰德系数（Adjusted Rand index）

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

其公式为：

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

优点：

• 对任意数量的聚类中心和样本数，随机聚类的ARI都非常接近于0。
• 取值在［－1，1］之间，负数代表结果不好，越接近于1越好。
• 对簇的结构不需作出任何假设：可以用于比较聚类算法。。

缺点：

• ARI 需要 ground truth classes 的相关知识，ARI需要真实标签，而在实践中几乎不可用，或者需要人工标注者手动分配（如在监督学习环境中）。

标准化互信息（NMI, Normalized Mutual Information）

互信息是用来衡量两个数据分布的吻合程度。它也是一有用的信息度量，它是指两个事件集合之间的相关性。互信息越大，词条和类别的相关程度也越大。

假设U与V是对N个样本标签的分配情况，则两种分布的熵（熵表示的是不确定程度）分别为：

U与V之间的互信息的表达式为：

其中，
$P(i, j) = |U_i \cap V_j| / N$是随机选取的对象同时属于
$U_i$类和
$V_j$ 类的概率。

它也可以用集合基数公式表示：

标准互信息的表达式为：

利用基于互信息的方法来衡量聚类效果需要实际类别信息，MI与NMI取值范围为[0,1]，它们都是值越大意味着聚类结果与真实情况越吻合。

调整互信息（AMI, Adjusted mutual information）

调整后的互信息是对互信息评分的进行调整。

它考虑到对于具有更大数量的聚类群，通常MI较高，而不管实际上是否有更多的信息共享，它通过调整聚类群的概率来纠正这种影响。

其表达式为：

AMI取值范围为[-1,1]，它们都是值越大意味着聚类结果与真实情况越吻合。

当两个聚类集相同（即完全匹配）时，AMI返回值为1；随机分区（独立标签）平均预期AMI约为0，也可能为负数。

同质性度量和完整性度量的调和平均（V-measure）

两个指标：

• 同质性（homogeneity）：每个群集只包含单个类的成员。
• 完整性（completeness）：给定类的所有成员都分配给同一个群集。

V-measure是同质性homogeneity和完整性completeness的调和平均数。

其表达式为：

V-measure取值范围为 [0,1]，越大越好，但当样本量较小或聚类数据较多的情况，推荐使用AMI和ARI。

Fowlkes-Mallows Scores（FMI）

FMI是Precision（精度）和 Recall（召回）的几何平均数。取值范围为 [0,1]，越接近1越好。

Recall（召回）和 Precision （精度），公式如下

但是其中定义的 TP,FP,TN,FN 和常见的分类任务不太一样，具体定义如下：

• TP：样本对在GT(真实值)中是一个蔟，同时在Pred(预测值)中也是一个蔟
• FP：样本对在Pred中是一个蔟，但是在GT中不是一个蔟
• FN：样本对在GT中是一个蔟，但是在Pred中不是一个蔟
• TN：样本对在GT中不是一个蔟，同时在Pred中也不是一个蔟

对于总样本有 n 个的聚类任务，假如是 
$s_1,…,s_n$ 那么可以组成 
$\frac {(n-1)*n}{2}$个样本对，即
$C_n^2$，而 TP,FP,TN,FN 是定义这些样本对的基础上，在因此有下面的等式成立：

FMI的公式定义为：

总结

一般情况下，主要是对无y值的数据进行聚类操作。如果在评价中用到外部指标，就需通过人工标注等方法获取y值，成本较高，因此内部指标的实际实用性更强。