无监督学习聚类算法的评价指标

摘要：确定聚类技术获得的结果的质量是无监督机器学习中的一个关键问题。Jon Kleinberg 建立了聚类的不可能定理。因此，大量的研究提出了评估聚类结果质量的技术，这取决于聚类问题的特征和用于聚类数据的算法技术。

关键词：聚类、无监督学习、评估指标

一、聚类的形式限制

从直观的角度来看，聚类问题有一个非常明确的目标；也就是说，正确地聚类一组未标记的数据。尽管“聚类”的概念具有直观的吸引力，但它无法精确定义，因此已经提出了各种各样的聚类算法。

A. 簇的理想特性

Jon Kleinberg提出了三个公理，强调了一个分组问题应该表现出来的特征，并且可以被认为是“好的”，而不依赖于用于寻找解决方案的算法。这些公理分别是尺度不变性（scale invariance）、一致性（consistency）和丰富性（richness）[3]，下面将详细说明。

定义分组函数为 $S$（$x\ge 2$个点）和点对之间的距离的集合。点的集合为 $S=1,2,\dots ,n$，点之间的距离由距离函数 $d(i,j)$ 给出，其中 $i,j\in S$。距离函数 $d$ 测量点对之间的不相似性。例如，欧几里得距离（Euclidean）、曼哈顿距离（Manhattan）、切比雪夫距离（Chebyshev）和马氏距离（Mahalanobis）等等都可以使用。或者，也可以使用相似函数。

1）尺度不变性（Scale Invariance）

Kleinberg 的第一个公理表明，对于任何距离函数 $d$ 和任何比例因子 $\alpha >0$，$f(d)=f(\alpha \cdot d)$。

这个公理表明，当所有点之间的距离由常数 $\alpha$ 决定时，聚类算法不应该修改其结果。

2）丰富性（Richness）

当 $S$ 的每个划分都是聚类过程的可能结果时，认为聚类过程是丰富的。如果使用 $Range(f)$ 表示所有 $\Gamma$ 分区的集合，使得对于某个距离函数 $d$，$f(d)=\Gamma$，则 $Range(f)$ 等于所有 $S$ 分区的集合。[3]

这意味着聚类函数必须足够灵活，能够产生输入数据集的任意分区/聚类。

3）一致性（Consistency）

设 $d$ 和 $d^{\prime }$ 是两个距离函数。若对每一对 $(i,j)$ 属于同一簇，$d(i,j)\ge d^{\prime }(i,j)$， 且对每一对 $(i,j)$ 属于不同簇，$d(i,j)\le d^{\prime }(i,j)$，则 $f(d)=f(d^{\prime })$。[3]

当簇内距离减小和/或簇间距离增加时，聚类结果不发生变化时，聚类过程是“一致的”。

B. 聚类的一个不可能定理

根据上述三个公理，Kleinberg 证明了以下定理：对于每一个 $n\ge 2$，不存在满足尺度不变性、丰富性和一致性的聚类函数 $f$。[3]

确定一个“好的“聚类并不是一个微不足道的问题。任何聚类过程都不可能满足所有这三个公理。实用的聚类算法必须权衡聚类结果的理想特征。

由于这三个公理不能同时成立，聚类算法可以设计为违背其中一个公理而满足其他两个公理。Kleinberg 通过描述单链接聚类（一种凝聚分层聚类算法）的三种变体来说明这一点：[3]

• $k$-cluster 停止条件：当我们有 k 个簇时停止合并簇（违反丰富性定理，因为算法永远不会返回与 k 不同的簇数量）。
• Distance-$r$ 停止条件：当最近的簇对距离大于 $r$ 时，停止合并簇（违反尺度不变性，因为当 $\alpha$ 较大时，每个簇将包含单个实例，而当 $\alpha \to 0$ 时，单个簇将包含所有数据）。
• Scale-$ϵ$ 停止条件：当最近的簇对距离小于最大成对距离 $\Delta$ 的一小部分时，停止合并簇（满足尺度不变性，但违反一致性）。

聚类算法通常可以通过放宽它们的丰富性来满足尺度不变性和一致性的特性（例如，每当预先建立簇的数量时）。正如我们所看到的，一些算法甚至可以通过放宽第三个公理来满足三个公理中的两个(例如，具有不同停止准则的简单连杆)。

二、聚类评价方法

通常，评估过程包含一个特殊性：执行测量的方式取决于用于获得聚类结果的算法。

在分析聚类结果时，必须考虑几个方面来验证算法结果[4]：

• 确定数据中的聚类趋势（即是否真的存在非随机结构）。
• 确定正确的簇数量。
• 在没有外部信息的情况下评估聚类结果的质量。
• 将所得结果与外界信息进行比较。
• 比较两组聚类以确定哪一组更好。

前三个问题通过内部或无监督验证来解决，因为没有使用外部信息。第四个问题通过外部或监督验证来解决。最后，最后一个问题可以通过监督和非监督验证技术来解决。[4]

Gan 等人[5]提出了一种评估技术分类，包括内部和外部验证方法（参见下图）。

A. 零假设检验

聚类过程的理想特征之一是显示数据是否显示出形成实际聚类的某种趋势。从统计学的角度来看，一个可行的方法是检验数据是否表现出随机行为[6]。在这种情况下，可以使用零假设检验：假设零假设 $H_0$ 是正确的，直到有证据表明并非如此。在这种情况下，零假设是数据的随机性，当零假设被证伪时，我们假设数据不太可能是随机的。[5]

在这种情况下，零假设检验的困难之一是确定随机假设可以被证伪的统计分布。Jain 和 Dubes 提出了三种替代方案[7]：

• 随机图假设 $H_0$：所有 $n\times n$ 阶的邻近矩阵都是等可能的。
• 随机标签假设 $H_0$：$n$ 个对象上标签的所有排列都是等可能的。
• 随机位置假设 $H_0$ ：在 $d$ 维空间的某个区域中，所有 $n$ 个位置的集合都是等可能的。

蒙特卡罗分析和自举等统计技术可用于确定数据中的聚类趋势[7]。

三、内部验证

内部验证方法可以在不访问外部信息的情况下建立聚类结构的质量（即，它们基于用作聚类算法输入的数据提供的信息）。

通常，可以组合使用两种类型的内部验证度量：内聚度量和分离度量。内聚评估同一簇的元素彼此之间的紧密程度，而分离度量量化簇之间的分离程度（参见下图）。这些指标也被称为内部指标，因为它们是在没有任何外部信息的情况下从输入数据中计算出来的[4]。内部指标通常与两种聚类算法结合使用：分层聚类算法和分区聚类算法。[5]

当没有其他可用信息时，使用内部验证。在大多数情况下，评估方法使用的特定指标与聚类算法试图优化的指标相同，这在确定聚类算法的质量方面可能会适得其反，并提供不公平的验证结果。另一方面，在缺乏其他信息来源的情况下，这些指标允许在相同的评估标准下比较不同的算法[8]，但必须注意不要报告有偏差的结果。

内部评价方法通常根据它们所使用的聚类算法的类型进行分类。对于分区（partitional）算法，通常使用基于距离矩阵的度量，以及内聚和分离度量，例如轮廓系数。对于分层算法，相干系数是最常见的（参见下图）。

A. 分区方法（Partitional Methods）

内部簇验证方法使用的一些度量是基于内聚和分离的概念（参见图2）。一般来说，$K$ 个簇的内部验证值可以分解为每个簇的验证值之和[4]：
$$generalvalidity=\sum _{i=1}^K{w}_{i}validity(C_i)$$
这种有效性度量可以是内聚、分离，或者两者的某种组合。通常，前面表达式中出现的权重对应于簇大小。

内聚和分离的个体度量定义如下[4]：
$$cohesion(C_i)=\sum _{x\in C_i,y\in C_i}proximity(x,y)$$

$$separation(C_i,C_j)=\sum _{x\in C_i,y\in C_j}proximity(x,y)$$

内聚性是在簇内测量的（簇内度量），而分离性是在簇之间测量的（簇间度量）。两者都基于一个接近函数，该函数决定了一对示例的相似程度(可以使用相似性，不相似性和距离函数)。

需要注意的是，当邻近函数为欧氏距离的平方时，上述定义的内聚度量等价于聚类的SSE (Sum of Squared Errors)，也称为SSW (Sum of Squared Errors Within cluster)：
$$SSE(C_i)=\sum _{x\in C_i}d(c_i,x{)}^2=\frac{1}{2m_i}\sum _{x\in C_i}\sum _{y\in C_i}d(x,y{)}^2$$
其中 $x$ 为簇中的一个样本，$c_i$ 为簇代表（如其质心），$m_i$ 为簇 $C_i$ 中的样本数。

当使用 SSE 度量时，较小的值表示聚类质量好。显然，在使用基于 SSE 优化的算法（如 k-means）构建的聚类中，该度量是最小化的，但对于使用其他技术（如基于密度的算法 DBSCAN）检测的聚类，该度量显然不是最优的[8]。

同样，我们可以使用分离度量来最大化聚类之间的距离。这种方法可以得到组间平方和（SSB）[4]：
$$SSB=\sum _{i=1}^K{m}_{i}d(c_i,c{)}^2=\frac{1}{2K}\sum _{i=1}^K\sum _{j=1}^K\frac{m}{K}d(c_i,c_j{)}^2$$
其中 $c_i$ 为第 $i$ 个簇的均值，$c$ 为总体均值[4]。与 SSE 度量不同，高 SSB 值给出了良好的聚类质量。如前所述，SSB 偏向于基于最大化聚类质心之间的分离距离的算法。[8]

如上所述，**当簇之间具有高分离性和簇内部具有高内聚性时，被认为是好的聚类[9]。**有几个指标试图在单个度量中量化分离和内聚的水平，而不是单独处理内聚和分离的指标[10]：

• Calisnki-Harabasz 系数 CH，又称方差比准则，是一种基于聚类内部离散度和聚类之间离散度的度量。对于 $M$ 个簇，我们选择使 CH 值最大化的簇数[11]：
  $$CH=\frac{\frac{SS{B}_M}{(M-1)}}{\frac{SS{E}_M}{(M)}}$$

• Dunn 系数是不同簇之间数据的最小距离与最大距离之比。同样，这个比率应该最大化[12]：
  D=min1<i<k{min1<j<k,i≠j{δ(Ci,Cj)max1<l<k{Δ(Cl)}}} D = \underset{1<i<k}{min} \left\{ \underset{1<j<k,i \neq j}{min} \left\{ \frac{\delta(C_i,C_j)}{\underset{1<l<k}{max} \left\{ \Delta(C_l) \right\}}\right\} \right\} D=1<i<kmin​⎩ ⎨ ⎧​1<j<k,i=jmin​⎩ ⎨ ⎧​1<l<kmax​{Δ(Cl​)}δ(Ci​,Cj​)​⎭ ⎬ ⎫​⎭ ⎬ ⎫​

  Δ(Ci)=maxx,y∈ci{d(x,y)} \Delta(C_i) = \underset{x,y \in c_i}{max} \left\{ d(x,y) \right\} Δ(Ci​)=x,y∈ci​max​{d(x,y)}

  δ(Ci,Cj)=minx∈Ci,y∈Cj{d(x,y)} \delta(C_i,C_j) = \underset{x \in C_i,y \in C_j}{min} \left\{ d(x,y) \right\} δ(Ci​,Cj​)=x∈Ci​,y∈Cj​min​{d(x,y)}

• Xie-Beni 系数是为模糊聚类而设计的，但它也适用于硬聚类。与前面的系数一样，它是一个比率，其分子估计同一簇内数据的压缩程度，其分母估计不同簇之间数据的分离程度[13]：
  XB=∑i=1N∑k=1Muik2∥∣xi−Ck∣∥2Nt≠smin{∥∣Ct−Cs∣∥2} XB = \frac{ \sum^N_{i=1} \sum^M_{k=1} u^2_{ik} \Vert\vert x_i-C_k \vert\Vert^2}{N_{t \neq s} min\left\{ \Vert\vert C_t-C_s \vert\Vert^2 \right\}} XB=Nt=s​min{∥∣Ct​−Cs​∣∥2}∑i=1N​∑k=1M​uik2​∥∣xi​−Ck​∣∥2​

• Ball-Hall 系数是基于聚类点相对于其质心的二次距离的色散度量[14]：
  $$BH=\frac{SS{E}_M}{M}$$

• Hartigan 系数基于聚类内平方和与聚类间平方和之间的对数关系[15]：
  $$H=log\left\{\frac{SS{B}_M}{SS{E}_M}\right\}$$

• Xu 系数考虑了数据的维数D，数据样本数N，和 $M$ 个簇的误差平方和 $SS{E}_M$[16]：
  $$Xu=Dlo{g}_2\left(\sqrt{\frac{SS{E}_M}{D{N}^2}}\right)+logM$$

• 轮廓系数是将内聚和分离度量结合在一起的最常见方法。计算特定点的轮廓系数包括以下三个步骤[4]：

  1. 对于每个样本，计算到同一簇中所有样例的平均距离 $a(i)$：
     $$a(i)=\frac{1}{|C_a|}\sum _{j\in C_a,i\ne j}d(i,j)$$

  2. 对于每个样本，该样本与不包含该样本的每个簇中包含的样本之间的最小平均距离 $b(i)$：
     $$b(i)=\underset{C_B\ne C_a}{\min }\frac{1}{|C_b|}\sum _{j\in C_b}d(i,j)$$

  3. 对于每个样本，轮廓系数由下式确定：
     s(i)=b(i)−a(i)max{a(i),b(i)} s(i) = \frac{b(i)-a(i)}{max \left\{ a(i),b(i) \right\}} s(i)=max{a(i),b(i)}b(i)−a(i)​

  4. 对于数据集中的每个样本，轮廓系数定义在区间[−1,1]。全局轮廓系数是每个样本的轮廓系数的平均值：
     $$S=\frac{1}{n}\sum _{i=1}^{n}s(i)$$
     与其他组合评估系数不同，轮廓系数为我们提供了一个简单的限定框架。正值表示簇之间的高度分离。负值表示簇相互混合（即表示重叠簇）。当轮廓系数为零时，表明数据在整个欧几里德空间中均匀分布[8]。

  不幸的是，轮廓系数的主要缺点之一是其计算复杂度很高，为 $O(d{n}^2)$，这使得它在处理庞大的数据集时不切实际[17]。

尽管它们被广泛使用，但内聚和分离度量并不是分割聚类技术唯一可用的验证方法。事实上，在分析基于密度分析的算法得到的结果时，内聚和分离度量的表现并不好。