来源：原始 Jupyter Notebook。内容已转换为网页阅读格式；下载原文件。

聚类（clustering） 是一种无监督学习算法（unsupervised learning），训练样本的标记信息通常是未知的，它试图对无标记的训练样本进行学习，找到数据的内在性质和规律，将数据集划分成若干个通常是不相交的子集，这些子集被称为 簇（cluster）。通过这样的划分，每个簇可能对应一个潜在的概念，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇所对应的概念语义需要由使用者把握和命名。

聚类模型的评估

如何评估聚类模型的好坏，也就是如何对聚类的性能进行度量，这也被称为 有效性指标（validity index）。直观上看，我们希望同一簇的样本尽可能的彼此相似，不同簇的样本尽可能的不同，也就是我们常说的 “物以类聚”。

评估方法一般有两种，一种是将聚类结果和某个参考模型（reference model）进行比较，这称作外部指标（external index）；另一种是直接考察聚类结果本身，称作内部指标（internal index）。

外部指标

外部指标的计算首先要定义几个变量，假定通过聚类算法给出的簇划分为 C={C1,C2,...,Ck}C = \{C_1, C_2, ..., C_k\}，而根据参考模型给出的簇划分为 C∗={C1∗,C2∗,...,Cs∗}C^* = \{C_1^*, C_2^*, ..., C_s^*\}，也就是说聚类算法将数据划分为 k 类，参考模型将数据划分为 s 类，一般情况下 k≠sk \neq s。然后将样本两两进行配对得到组合 (xi,xj)(x_i, x_j)，其中 i<ji < j。一共可以得到 m(m−1)/2m(m-1)/2 个组合，并且只会有四种不同的情况：

  • xix_i 和 xjx_j 在 CC 中属于相同簇，在 C∗C^* 中也属于相同簇，一共有 a 个组合
  • xix_i 和 xjx_j 在 CC 中属于相同簇，在 C∗C^* 中属于不同簇，一共有 b 个组合
  • xix_i 和 xjx_j 在 CC 中属于不同簇，在 C∗C^* 中属于相同簇，一共有 c 个组合
  • xix_i 和 xjx_j 在 CC 中属于不同簇，在 C∗C^* 中也属于不同簇，一共有 d 个组合

很显然：

a+b+c+d=m(m−1)/2 a + b + c + d = m(m-1)/2

根据这四个变量，就可以定义出下面这些常用的外部指标：

  • Jaccard 系数（Jaccard Coefficient，简称 JC）
JC=aa+b+c JC = \frac{a}{a+b+c}
  • FM 指数（Fowlkes and Mallows Index，简称 FMI）
FMI=aa+b⋅aa+c FMI = \sqrt {\frac{a}{a+b} \cdot \frac{a}{a+c}}
  • Rand 指数（Rand Index，简称 RI）
RI=2(a+d)m(m−1) RI = \frac{2(a+d)}{m(m-1)}

这些指标值的范围都在 0 - 1 之间，值越大说明聚类结果越准。

内部指标

在定义内部指标之前，也首先定义几个变量，假定通过聚类算法给出的簇划分为 C={C1,C2,...,Ck}C = \{C_1, C_2, ..., C_k\}，样本 xix_i 和 xjx_j 之间的距离记为 dist(xi,xj)dist(x_i, x_j)，可以得到簇内样本间的平均距离：

avg(C)=2∣C∣(∣C∣−1)∑1⩽i⩽j⩽∣C∣dist(xi,xj) avg(C) = \frac{2}{|C|(|C|-1)} \sum_{1 \leqslant i \leqslant j \leqslant |C|} dist(x_i, x_j)

簇内样本间的最远距离：

diam(C)=max1⩽i⩽j⩽∣C∣dist(xi,xj) diam(C) = max_{1 \leqslant i \leqslant j \leqslant |C|} dist(x_i, x_j)

簇 CiC_i 和 簇 CjC_j 最近样本间的距离：

dmin(Ci,Cj)=minxi∈Ci,xj∈Cjdist(xi,xj) d_{min}(C_i, C_j) = min_{x_i \in C_i, x_j \in C_j} dist(x_i, x_j)

簇 C 的中心点：

μ=1∣C∣∑1⩽i⩽∣C∣xi \mu = \frac{1}{|C|} \sum_{1 \leqslant i \leqslant |C|} x_i

簇 CiC_i 和 簇 CjC_j 中心点间的距离：

dcen(Ci,Cj)=dist(μi,μj) d_{cen}(C_i, C_j) = dist(\mu_i, \mu_j)

从而得到下面这些常用的内部指标：

  • DB 指数（Davies-Bouldin Index，简称 DBI）
DBI = \frac{1}{k} \sum_{1}^k \mathop \max _{j \neq i} ( \frac{avg(C_i) + avg(C_j)}{d_{cen}(C_i, C_j)} )
  • Dunn 指数（Dunn Index，简称 DI）
DI = \mathop \min_{1 \leqslant i \leqslant k} \Big \{ \mathop \min_{j \neq i} \Big ( \frac{d_{min}(C_i,C_j)}{\mathop \max_{1 \leqslant l \leqslant k}diam(C_l)} \Big ) \Big \}

距离的度量

聚类的核心概念是 距离（distance）或 相似度（similarity），距离或相似度的定义多种多样，选择合适的距离度量方法是聚类的关键。

  • 闵可夫斯基距离（闵氏距离）
    • 欧式距离
    • 曼哈顿距离
    • 切比雪夫距离
  • 马哈拉诺比斯距离（马氏距离）
  • 相关系数
  • 夹角余弦

参考 kNN 距离度量方法