---
tags: [AI, 经典机器学习, 聚类, 无监督]
阶段: 03-经典机器学习
难度: ★★☆
created: 2026-10-18
related: "[[PCA与降维]], [[异常检测]], [[模型评估与交叉验证]], [[树模型与集成学习]]"
---

# 无监督学习与聚类

## 定义

**无监督学习**（unsupervised learning）指只给定样本集 $\{\mathbf{x}_i\}_{i=1}^{n}$、不给定标签，要求估计其生成分布或发现其中结构的学习范式；**聚类**（clustering）是在给定样本间距离或相似度的前提下，把样本划分为若干互不相交的子集，使同一子集内样本彼此接近、不同子集间样本彼此远离的过程。

- $\mathbf{X}\in\mathbb{R}^{n\times d}$：样本矩阵，$n$ 为样本数，$d$ 为特征维数。
- $K$：簇的数量，需预先给定（DBSCAN 除外）。
- $C_k$：第 $k$ 个簇的样本下标集合，$|C_k|$ 为其样本数。
- $\boldsymbol{\mu}_k\in\mathbb{R}^{d}$：第 $k$ 个簇的中心（码字）。
- $r_{ik}\in\{0,1\}$：硬指派指示变量，$r_{ik}=1$ 表示 $\mathbf{x}_i$ 属于簇 $k$，且 $\sum_k r_{ik}=1$。
- $J$：K-Means 的目标函数（簇内平方和，也称失真度）。
- $\pi_k$：高斯混合模型中第 $k$ 个分量的混合权重，$\sum_k\pi_k=1$。
- $\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k$：第 $k$ 个高斯分量的均值与协方差矩阵。
- $z_i\in\{1,\dots,K\}$：样本 $i$ 的隐变量，表示其来源分量。
- $\gamma_{ik}=p(z_i=k\mid\mathbf{x}_i,\boldsymbol{\theta})$：**责任度**（responsibility），即样本 $i$ 由分量 $k$ 生成的后验概率。
- $\varepsilon$、$\mathrm{minPts}$：DBSCAN 的邻域半径与核心点的最小邻居数。
- $s(i)$：样本 $i$ 的轮廓系数；$\mathrm{ARI}$、$\mathrm{NMI}$：聚类结果与真实划分之间的一致性指标。

## 为什么重要

- 解决的问题：真实数据中带标签样本稀少，而无标签数据可以大量获得；聚类在没有标签的条件下给出分组、压缩码本与数据结构假设，是探索性分析的第一步。
- 没有它会怎样：无法在无标签条件下评估样本间的结构相似性；K-Means 与 GMM 还是 EM 算法、向量量化与混合模型的原型，缺失它们会使后续的概率建模与表示学习失去基础。
- 与监督学习的差别：监督学习的目标由标签给出，评估指标与目标函数一致；聚类没有唯一正确答案，目标函数的选择（簇内平方和、似然、密度连通）直接决定了划分的形状，因此「算法 + 评估」必须成对讨论。
- 在全书中的位置：前置为 [[PCA与降维]] 的降维与方差分析、[[概率与统计]] 的极大似然；本篇的 K-Means 与 GMM 是 [[异常检测]] 中基于距离与密度方法的直接基础；聚类结果的稳定性检验纳入 [[模型评估与交叉验证]] 的思路。
- 对应能力目标：懂原理要求能证明 Lloyd 算法的单调下降、完成 GMM 的 EM 推导；能复现要求能用 NumPy 实现 K-Means 与 EM；会评估要求能区分内部指标与外部指标，并解释二者结论冲突的原因。

## 原理与推导

```mermaid
flowchart TD
    I["初始化：中心或混合参数"] --> E["E 步：计算指派或责任度"]
    E --> M["M 步：更新中心或参数"]
    M --> C{"目标函数是否不再变化"}
    C -->|"否"| E
    C -->|"是"| O["输出划分或后验概率"]
```

### 1. 无监督问题的设定

设 $\mathbf{x}_1,\dots,\mathbf{x}_n$ 独立同分布于未知分布 $p(\mathbf{x})$。无监督学习的三类典型目标：

1. 密度估计：构造 $\hat p(\mathbf{x})$ 近似 $p$，用于采样、异常评分与似然比较。
2. 降维：寻找低维表示 $\mathbf{z}=g(\mathbf{x})$，保留主要变异，见 [[PCA与降维]]。
3. 聚类：把样本划分为 $K$ 个组，使组内差异小、组间差异大。

聚类没有唯一的数学定义，必须先固定准则。常见的三种准则对应不同的簇形状假设：

| 准则 | 目标函数 | 隐含的簇形状 |
|---|---|---|
| 簇内平方和 | $\sum_i\lVert\mathbf{x}_i-\boldsymbol{\mu}_{c(i)}\rVert^{2}$ | 各向同性、尺寸相近的凸簇 |
| 混合模型似然 | $\sum_i\log\sum_k\pi_k\mathcal{N}(\mathbf{x}_i\mid\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k)$ | 椭圆、可重叠的凸簇 |
| 密度连通 | 邻域内样本数不低于阈值 | 任意形状、可含噪声 |

选择准则即选择归纳偏置。准则与数据结构不匹配时，算法仍会返回划分，但该划分不再具有解释力。

混合模型还存在**可辨识性**问题：交换两个分量的编号不改变似然，因此参数估计只能确定到置换意义下；聚类结果同样只能确定到簇编号的置换。评估指标必须对置换不变，这是 ARI 与 NMI 的设计前提。

### 2. K-Means 的目标函数与 Lloyd 算法

K-Means 求解

$$
\min_{\{r_{ik}\},\{\boldsymbol{\mu}_k\}}\;J=\sum_{i=1}^{n}\sum_{k=1}^{K}r_{ik}\left\lVert\mathbf{x}_i-\boldsymbol{\mu}_k\right\rVert^{2}
\quad\text{s.t.}\quad r_{ik}\in\{0,1\},\;\sum_{k=1}^{K}r_{ik}=1 .
$$

变量分两组：指派 $r_{ik}$ 与中心 $\boldsymbol{\mu}_k$。**Lloyd 算法**交替固定一组、优化另一组。

指派步：固定中心，每个样本独立选择最近中心，

$$
r_{ik}=\mathbb{1}\left[k=\arg\min_{j}\left\lVert\mathbf{x}_i-\boldsymbol{\mu}_j\right\rVert^{2}\right].
$$

更新步：固定指派，目标对 $\boldsymbol{\mu}_k$ 可分离。对第 $k$ 个簇，

$$
\frac{\partial J}{\partial\boldsymbol{\mu}_k}
=-2\sum_{i:\,r_{ik}=1}\left(\mathbf{x}_i-\boldsymbol{\mu}_k\right)=0
\;\Longrightarrow\;
\boldsymbol{\mu}_k=\frac{\sum_{i}r_{ik}\mathbf{x}_i}{\sum_{i}r_{ik}} .
$$

即中心是该簇样本的算术平均。若某簇为空，需重新指定中心或删除该簇，否则更新式分母为零。

单调下降的证明思路。记第 $t$ 次迭代后的目标值为 $J^{(t)}$。指派步在中心固定时对每个样本取最优，故 $J$ 不增；更新步在指派固定时对每个中心取最优，故 $J$ 不增。两步交替得到

$$
J^{(0)}\ge J^{(1)}\ge J^{(2)}\ge\cdots\ge 0 .
$$

$J$ 有下界 $0$；划分的总数是有限的（至多 $K^{n}$ 种），若算法不停机则必有两次迭代落在同一划分上，而确定性算法在同一划分上产生相同的中心与目标值，于是循环重复。因此算法在有限步内停在某个划分上，该划分满足「指派不再变化」，即目标函数的坐标下降不动点。

该不动点只是局部最优。$K$-Means 的全局最优求解是 NP 难的，实践中用多次随机初始化取最优目标值来近似。

单次迭代复杂度为 $O(nKd)$：计算 $n\times K$ 个距离，每个距离 $O(d)$；$T$ 次迭代为 $O(nKdT)$。中心初始化与空簇处理是主要的实现差异来源。

一个常用的等价形式把目标写成簇内两两距离：

$$
\sum_{i\in C_k}\left\lVert\mathbf{x}_i-\boldsymbol{\mu}_k\right\rVert^{2}
=\frac{1}{2|C_k|}\sum_{i\in C_k}\sum_{j\in C_k}\left\lVert\mathbf{x}_i-\mathbf{x}_j\right\rVert^{2},
$$

它说明簇内平方和只依赖簇内样本的两两距离，因此在核空间中把距离替换为 $K(\mathbf{x}_i,\mathbf{x}_i)+K(\mathbf{x}_j,\mathbf{x}_j)-2K(\mathbf{x}_i,\mathbf{x}_j)$ 即可得到核 K-Means。

### 3. 初始化：k-means++

随机选取 $K$ 个样本作为初始中心时，若两个初始中心落在同一个真实簇内，该簇会被永久拆分，算法只能收敛到较差的局部最优。**k-means++** 按距离加权采样，使初始中心尽量分散：

1. 以均匀分布选取第一个中心。
2. 对每个样本计算 $D(\mathbf{x})=\min_{j}\lVert\mathbf{x}-\boldsymbol{\mu}_j\rVert$，即以已选中心为参照的最近距离。
3. 以正比于 $D(\mathbf{x})^{2}$ 的概率选取下一个中心，重复直到选满 $K$ 个。

平方使远离已有中心的样本被显著放大。该策略的期望近似比为 $O(\log K)$，即期望目标值不超过最优值的 $O(\log K)$ 倍。实践中仍会运行多次（`n_init`），取目标值最小的一次，因为近似比只是期望意义下的界。

### 4. 簇数 K 的选择

$J$ 随 $K$ 单调不增，$K=n$ 时 $J=0$，因此不能直接最小化 $J$。常用两种启发式。

**肘部法**：绘制 $J(K)$ 曲线，选择下降速率明显变缓的拐点。拐点没有严格定义，曲线平滑时判断困难。

**轮廓系数**：对样本 $i$，记 $a(i)$ 为其到同簇其他样本的平均距离，$b(i)$ 为其到其他各簇平均距离的最小值，定义

$$
s(i)=\frac{b(i)-a(i)}{\max\left(a(i),b(i)\right)}\in[-1,1],
$$

整体轮廓系数为 $\bar s=\frac{1}{n}\sum_i s(i)$。$s(i)$ 接近 $1$ 表示样本与同簇更近、与最近的其他簇更远；接近 $0$ 表示位于两簇边界；为负表示可能被分错。簇大小为 $1$ 时约定 $s(i)=0$。

两种方法的适用条件不同：肘部法只反映簇内紧致度，轮廓系数同时考虑簇间分离度，但对非凸簇与密度差异大的数据会给出误导性结果。后文代码中，双月数据上 DBSCAN 的 ARI 达到 $1.0$，轮廓系数却只有 $0.3285$，说明内部指标不能替代外部验证。

### 5. GMM：混合模型与隐变量

高斯混合模型假设样本由 $K$ 个高斯分量按权重混合生成：

$$
p(\mathbf{x}\mid\boldsymbol{\theta})=\sum_{k=1}^{K}\pi_k\,\mathcal{N}\left(\mathbf{x}\mid\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k\right),
\qquad
\mathcal{N}(\mathbf{x}\mid\boldsymbol{\mu},\boldsymbol{\Sigma})
=\frac{1}{(2\pi)^{d/2}|\boldsymbol{\Sigma}|^{1/2}}
\exp\left(-\frac{1}{2}(\mathbf{x}-\boldsymbol{\mu})^\top\boldsymbol{\Sigma}^{-1}(\mathbf{x}-\boldsymbol{\mu})\right).
$$

参数为 $\boldsymbol{\theta}=\{\pi_k,\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k\}_{k=1}^{K}$。对数似然为

$$
\ell(\boldsymbol{\theta})=\sum_{i=1}^{n}\log\left(\sum_{k=1}^{K}\pi_k\mathcal{N}\left(\mathbf{x}_i\mid\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k\right)\right).
$$

对数内部有求和，直接求导会得到耦合方程，没有闭式解。引入隐变量 $z_i\in\{1,\dots,K\}$ 表示样本来源分量，完全数据似然为 $\prod_i\pi_{z_i}\mathcal{N}(\mathbf{x}_i\mid\boldsymbol{\mu}_{z_i},\boldsymbol{\Sigma}_{z_i})$，但 $z_i$ 不可观测。

下界构造。对每个样本引入任意分布 $q_i(z)$，由 Jensen 不等式，

$$
\log p(\mathbf{x}_i\mid\boldsymbol{\theta})
=\log\sum_{k=1}^{K}q_i(k)\frac{\pi_k\mathcal{N}(\mathbf{x}_i\mid\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k)}{q_i(k)}
\ge\sum_{k=1}^{K}q_i(k)\log\frac{\pi_k\mathcal{N}(\mathbf{x}_i\mid\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k)}{q_i(k)} .
$$

对 $i$ 求和得到**证据下界**（ELBO）：

$$
\mathcal{L}(q,\boldsymbol{\theta})
=\sum_{i=1}^{n}\sum_{k=1}^{K}\gamma_{ik}\left[\log\pi_k+\log\mathcal{N}(\mathbf{x}_i\mid\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k)-\log\gamma_{ik}\right],
\qquad \gamma_{ik}=q_i(k).
$$

不等式取等的条件是 $\pi_k\mathcal{N}(\mathbf{x}_i\mid\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k)/\gamma_{ik}$ 与 $k$ 无关，即 $\gamma_{ik}$ 正比于该乘积。这也给出 $q_i$ 的最优形式。

**E 步**：固定 $\boldsymbol{\theta}$，取 $q_i$ 为后验，得到责任度

$$
\gamma_{ik}
=\frac{\pi_k\,\mathcal{N}\left(\mathbf{x}_i\mid\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k\right)}
{\sum_{j=1}^{K}\pi_j\,\mathcal{N}\left(\mathbf{x}_i\mid\boldsymbol{\mu}_j,\boldsymbol{\Sigma}_j\right)} .
$$

$\gamma_{ik}$ 满足 $\sum_k\gamma_{ik}=1$，可解释为样本 $i$ 由各分量生成的概率。

**M 步**：固定 $\gamma_{ik}$，对 $\boldsymbol{\theta}$ 最大化 ELBO。记 $N_k=\sum_i\gamma_{ik}$ 为第 $k$ 个分量的有效样本数。

对 $\boldsymbol{\mu}_k$ 求导：

$$
\frac{\partial\mathcal{L}}{\partial\boldsymbol{\mu}_k}
=\sum_{i=1}^{n}\gamma_{ik}\boldsymbol{\Sigma}_k^{-1}\left(\mathbf{x}_i-\boldsymbol{\mu}_k\right)=0
\;\Longrightarrow\;
\boldsymbol{\mu}_k=\frac{1}{N_k}\sum_{i=1}^{n}\gamma_{ik}\mathbf{x}_i .
$$

对 $\boldsymbol{\Sigma}_k$ 求导。利用 $\partial\log|\boldsymbol{\Sigma}|/\partial\boldsymbol{\Sigma}=\boldsymbol{\Sigma}^{-1}$ 与 $\partial\operatorname{tr}(\boldsymbol{\Sigma}^{-1}\mathbf{A})/\partial\boldsymbol{\Sigma}=-\boldsymbol{\Sigma}^{-1}\mathbf{A}\boldsymbol{\Sigma}^{-1}$，令导数为零：

$$
-\frac{N_k}{2}\boldsymbol{\Sigma}_k^{-1}
+\frac{1}{2}\boldsymbol{\Sigma}_k^{-1}\left(\sum_{i}\gamma_{ik}\left(\mathbf{x}_i-\boldsymbol{\mu}_k\right)\left(\mathbf{x}_i-\boldsymbol{\mu}_k\right)^\top\right)\boldsymbol{\Sigma}_k^{-1}=0,
$$

左右乘 $\boldsymbol{\Sigma}_k$ 得

$$
\boldsymbol{\Sigma}_k=\frac{1}{N_k}\sum_{i=1}^{n}\gamma_{ik}\left(\mathbf{x}_i-\boldsymbol{\mu}_k\right)\left(\mathbf{x}_i-\boldsymbol{\mu}_k\right)^\top .
$$

对 $\pi_k$ 求导需处理约束 $\sum_k\pi_k=1$，引入乘子 $\lambda$：

$$
\frac{\partial}{\partial\pi_k}\left[\sum_{i}\sum_{j}\gamma_{ij}\log\pi_j+\lambda\left(1-\sum_j\pi_j\right)\right]
=\frac{N_k}{\pi_k}-\lambda=0
\;\Longrightarrow\;
\pi_k=\frac{N_k}{\lambda}.
$$

由 $\sum_k\pi_k=1$ 得 $\lambda=\sum_k N_k=n$，故

$$
\pi_k=\frac{N_k}{n}.
$$

单调性。记 $\boldsymbol{\theta}^{t}$ 为第 $t$ 轮参数。E 步取 $q$ 为后验，此时 KL 散度为零，有

$$
\mathcal{L}\left(q^{t+1},\boldsymbol{\theta}^{t}\right)=\ell\left(\boldsymbol{\theta}^{t}\right).
$$

M 步最大化下界，故 $\mathcal{L}(q^{t+1},\boldsymbol{\theta}^{t+1})\ge\mathcal{L}(q^{t+1},\boldsymbol{\theta}^{t})$。又由 Jensen 不等式 $\ell(\boldsymbol{\theta}^{t+1})\ge\mathcal{L}(q^{t+1},\boldsymbol{\theta}^{t+1})$。合并得

$$
\ell\left(\boldsymbol{\theta}^{t+1}\right)\ge\ell\left(\boldsymbol{\theta}^{t}\right),
$$

即每一轮对数似然不降。EM 收敛到驻点，可能是局部极大或鞍点，不保证全局最优。

退化与正则化。若某个分量的协方差退化、均值收敛到单个样本，该样本处的密度趋于无穷，似然无上界。实现中通过对角加载 $\boldsymbol{\Sigma}_k\leftarrow\boldsymbol{\Sigma}_k+\epsilon\mathbf{I}$、限制协方差类型（对角、共享、球面）或设置最小簇样本数来避免。

### 6. GMM 与 K-Means 的关系

取各分量协方差相同且为各向同性 $\boldsymbol{\Sigma}_k=\sigma^{2}\mathbf{I}$、权重相同 $\pi_k=1/K$，则责任度为

$$
\gamma_{ik}
=\frac{\exp\left(-\lVert\mathbf{x}_i-\boldsymbol{\mu}_k\rVert^{2}/(2\sigma^{2})\right)}
{\sum_{j}\exp\left(-\lVert\mathbf{x}_i-\boldsymbol{\mu}_j\rVert^{2}/(2\sigma^{2})\right)} .
$$

当 $\sigma^{2}\to0$ 时，最近中心对应的指数项占主导，$\gamma_{ik}\to1$，其余趋于 $0$，责任度退化为硬指派；此时 M 步的加权均值退化为簇内算术平均，正是 Lloyd 的更新步。因此 K-Means 是「各向同性、等权重、方差趋于零」的 GMM 的极限情形。

两者的差别来自三处：GMM 允许各分量有不同协方差，因而能表达椭圆簇与不同尺寸的簇；GMM 给出软指派，样本可以同时以不同概率属于多个分量；GMM 优化似然而非簇内平方和，对离群点的惩罚是对数尺度而非平方尺度。

### 7. DBSCAN

DBSCAN 基于密度连通性定义簇，不需要预先给定 $K$。

- $\varepsilon$-邻域：$N_\varepsilon(\mathbf{x})=\{\mathbf{z}:d(\mathbf{x},\mathbf{z})\le\varepsilon\}$。
- 核心点：$|N_\varepsilon(\mathbf{x})|\ge\mathrm{minPts}$。
- 边界点：非核心点，但落在某个核心点的 $\varepsilon$-邻域内。
- 噪声点：既非核心点也不在任何核心点邻域内的点。
- 直接密度可达：$\mathbf{z}\in N_\varepsilon(\mathbf{x})$ 且 $\mathbf{x}$ 为核心点，称 $\mathbf{z}$ 从 $\mathbf{x}$ 直接密度可达。
- 密度可达：存在点列 $\mathbf{x}=\mathbf{p}_0,\dots,\mathbf{p}_m=\mathbf{z}$，使 $\mathbf{p}_{t+1}$ 从 $\mathbf{p}_t$ 直接密度可达。
- 密度连通：存在点 $\mathbf{o}$，使 $\mathbf{x}$ 与 $\mathbf{z}$ 都从 $\mathbf{o}$ 密度可达。

簇定义为密度连通关系下的极大集合。算法流程：

```text
对每个未访问样本 p：
    标记 p 已访问
    若 |N_eps(p)| < minPts：暂标记为噪声
    否则：
        新建簇 C，把 p 加入 C，队列 Q = N_eps(p)
        当 Q 非空：
            取出 q
            若 q 未访问：
                标记 q 已访问
                若 |N_eps(q)| >= minPts：把 N_eps(q) 并入 Q
            若 q 尚未属于任何簇：把 q 加入 C
```

复杂度取决于邻域查询：使用 KD 树或球树时为 $O(n\log n)$，无索引时为 $O(n^{2})$。$\varepsilon$ 过小会使大量样本成为噪声、簇被拆碎；$\varepsilon$ 过大则不同簇被合并。常用 $k$-距离图选择参数：对每个点计算到第 $\mathrm{minPts}$ 近邻的距离并排序，拐点处取 $\varepsilon$。

优点：能发现任意形状的簇、显式标记噪声、不需要 $K$。缺点：对密度差异大的数据无统一参数；高维下距离集中使 $\varepsilon$ 难以选择；边界点可能同时邻近两个簇，结果依赖处理顺序。

### 8. 层次聚类与连接准则

凝聚式层次聚类从每个样本自成一簇开始，每步合并距离最近的两个簇，得到一棵树（树状图），在所需高度切割即得划分。

簇间距离的定义决定结果：

| 连接准则 | 定义 | 性质 |
|---|---|---|
| 单连接 | $d_{\min}(A,B)=\min_{\mathbf{a}\in A,\mathbf{b}\in B}d(\mathbf{a},\mathbf{b})$ | 能发现长条形簇，易发生链式效应 |
| 全连接 | $d_{\max}(A,B)=\max_{\mathbf{a}\in A,\mathbf{b}\in B}d(\mathbf{a},\mathbf{b})$ | 倾向紧凑的等直径簇，对离群点敏感 |
| 平均连接 | $d_{\mathrm{avg}}(A,B)=\frac{1}{|A||B|}\sum_{\mathbf{a}\in A}\sum_{\mathbf{b}\in B}d(\mathbf{a},\mathbf{b})$ | 折中，计算量较大 |
| Ward | $\Delta(A,B)=\frac{|A||B|}{|A|+|B|}\left\lVert\boldsymbol{\mu}_A-\boldsymbol{\mu}_B\right\rVert^{2}$ | 最小化合并带来的簇内平方和增量，要求欧氏距离 |

Ward 的增量公式：合并前两簇的簇内平方和之和为 $\operatorname{SSE}(A)+\operatorname{SSE}(B)$，合并后为 $\operatorname{SSE}(A\cup B)$，二者之差恰为 $\frac{|A||B|}{|A|+|B|}\lVert\boldsymbol{\mu}_A-\boldsymbol{\mu}_B\rVert^{2}$。因此每步按该增量最小者合并，等价于最小化整体簇内平方和的增长。

合并后新簇与其他簇的距离可用 Lance-Williams 公式递推，无需重算全部两两距离。以平均连接为例，$A$ 与 $B$ 合并为 $A\cup B$ 后

$$
d_{\mathrm{avg}}(A\cup B,C)=\frac{|A|}{|A|+|B|}d_{\mathrm{avg}}(A,C)+\frac{|B|}{|A|+|B|}d_{\mathrm{avg}}(B,C).
$$

朴素实现每次合并后重算距离矩阵，总代价 $O(n^{3})$；使用优先队列与 Lance-Williams 递推可降至 $O(n^{2}\log n)$，但距离矩阵需要 $O(n^{2})$ 内存，因此不适合 $n$ 超过 $10^{5}$ 的数据。

连接准则与 K-Means 的差别在于：层次聚类不假设簇为凸集，且一次运行给出整棵合并树，可通过切割高度控制簇数。代价是无法回溯，早期错误合并不会撤销。

### 9. 聚类评估

**内部指标**只使用样本与划分，不使用真实标签。

轮廓系数已在第 4 节定义。另有簇内平方和、Calinski-Harabasz 指数（簇间平方和与簇内平方和之比）与 Davies-Bouldin 指数（各簇到最相似簇的散度平均值）。

**外部指标**使用真实划分 $U$ 与预测划分 $V$ 计算一致性。设列联表 $n_{ij}=|U_i\cap V_j|$，$a_i=|U_i|$，$b_j=|V_j|$。

调整兰德指数（Adjusted Rand Index, ARI）先定义兰德指数

$$
\mathrm{RI}=\frac{\text{同簇且同类样本对数}+\text{不同簇且不同类样本对数}}{\binom{n}{2}},
$$

再用随机划分的期望做校正：

$$
\mathrm{ARI}=
\frac{\sum_{ij}\binom{n_{ij}}{2}
-\left[\sum_i\binom{a_i}{2}\sum_j\binom{b_j}{2}\right]\Big/\binom{n}{2}}
{\frac{1}{2}\left[\sum_i\binom{a_i}{2}+\sum_j\binom{b_j}{2}\right]
-\left[\sum_i\binom{a_i}{2}\sum_j\binom{b_j}{2}\right]\Big/\binom{n}{2}} .
$$

$\mathrm{ARI}=1$ 表示划分完全一致，$0$ 表示与随机划分的期望相当，负值表示比随机更差。

归一化互信息（Normalized Mutual Information, NMI）先计算互信息

$$
I(U;V)=\sum_{i}\sum_{j}\frac{n_{ij}}{n}\log\frac{n\,n_{ij}}{a_i b_j},
$$

再除以两划分熵的均值（scikit-learn 默认使用算术平均）：

$$
\mathrm{NMI}=\frac{I(U;V)}{\frac{1}{2}\left[H(U)+H(V)\right]} .
$$

NMI 对簇数不惩罚，簇数增加时倾向于上升；ARI 有随机划分的期望校正，更常用于比较不同簇数的结果。

两种指标的用途不同：内部指标用于没有标签时的模型选择，但它编码了几何假设，对非凸簇会失效；外部指标用于有标签的基准数据，反映划分与真实类别的吻合程度，不反映该划分在下游任务中的价值。

## 关键直觉

> [!tip] 机制性直觉
> K-Means 是交替优化指派与中心的坐标下降：固定中心时样本独立取最近中心，固定指派时中心取簇内均值，两步都使目标不增，因此收敛到坐标下降的不动点。GMM 的 EM 是同一结构在概率模型上的版本：E 步用责任度代替硬指派，M 步用加权矩估计代替算术平均，每一步都提高对数似然的下界。当协方差趋于零时责任度退化为指示函数，GMM 退化为 K-Means，这一极限关系把两种算法的定义与推导连接起来。

## 例子与代码

### 手算：6 个样本的 K-Means 两轮迭代

取 $\mathbf{x}_1=(0,0)$、$\mathbf{x}_2=(0,2)$、$\mathbf{x}_3=(1,1)$、$\mathbf{x}_4=(6,6)$、$\mathbf{x}_5=(6,8)$、$\mathbf{x}_6=(7,7)$，$K=2$，初始中心 $\boldsymbol{\mu}_1=(0,0)$、$\boldsymbol{\mu}_2=(1,3)$。

| 轮次 | 指派 $C_1$ / $C_2$ | 更新后中心 | 目标函数 $J$ |
|---|---|---|---|
| 初始指派 | $\{1,3\}$ / $\{2,4,5,6\}$ | — | $0+2+2+34+50+52=140$ |
| 第 1 次更新 | 同上 | $(0.5,0.5)$ / $(4.75,5.75)$ | $0.5+36.625+0.5+1.625+6.625+6.625=52.5$ |
| 第 2 次指派 | $\{1,2,3\}$ / $\{4,5,6\}$ | — | $0.5+2.5+0.5+1.625+6.625+6.625=18.375$ |
| 第 2 次更新 | 同上 | $(1/3,1)$ / $(19/3,7)$ | $1.111+1.111+0.444+1.111+1.111+0.444=5.333$ |

第 2 次更新后再执行指派：$\mathbf{x}_2$ 到 $\boldsymbol{\mu}_1$ 的距离平方为 $(0-1/3)^2+(2-1)^2=1.111$，到 $\boldsymbol{\mu}_2$ 为 $(0-19/3)^2+(2-7)^2=65.111$，仍归入 $C_1$；其余样本的归属不变。指派不再变化，算法停止，$J=5.333$。

过程中 $J$ 从 $140$ 降到 $52.5$，再降到 $18.375$，最后降到 $5.333$，每次下降都由指派步或更新步之一完成，验证了第 2 节的单调性。$\mathbf{x}_2$ 在第 2 次指派中由 $C_2$ 转入 $C_1$，说明更新后的中心会改变样本归属。

### 代码一：NumPy 实现 K-Means 与 k-means++

```python
# 依赖：Python 3.12、NumPy 2.3.5、scikit-learn 1.9.1
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score, adjusted_rand_score

def kmeans_pp(X, k, rng):
    centers = [X[rng.integers(len(X))]]
    for _ in range(1, k):
        # 到最近已选中心的距离平方，作为采样权重
        d2 = np.min(((X[:, None, :] - np.array(centers)[None]) ** 2).sum(-1), axis=1)
        centers.append(X[rng.choice(len(X), p=d2 / d2.sum())])
    return np.array(centers)

def lloyd(X, C, max_iter=100):
    history = []
    for _ in range(max_iter):
        d2 = ((X[:, None, :] - C[None]) ** 2).sum(-1)
        r = d2.argmin(1)                       # 指派步
        history.append(float(((X - C[r]) ** 2).sum()))
        C_new = np.array([X[r == j].mean(0) if np.any(r == j) else C[j] for j in range(len(C))])
        if np.allclose(C_new, C):              # 中心不变即到达不动点
            break
        C = C_new                              # 更新步
    return C, r, history

X, y = make_blobs(n_samples=300, centers=3, cluster_std=0.9, random_state=1)
C0 = kmeans_pp(X, 3, np.random.default_rng(0))
C, r, history = lloyd(X, C0)
print("每轮目标函数值：", [round(v, 4) for v in history])
print("最终中心：\n", np.round(C, 2))
print("轮廓系数：", round(float(silhouette_score(X, r)), 4),
      " ARI：", round(float(adjusted_rand_score(y, r)), 4))
```

预期输出：

```text
每轮目标函数值： [1387.0199, 500.1221, 466.8247]
最终中心：
 [[ -7.03  -8.03]
 [ -1.47   4.41]
 [-10.06  -3.91]]
轮廓系数： 0.748  ARI： 0.99
```

解读：

- 目标函数值单调下降并在第 3 次计算后稳定，与第 2 节的单调性结论一致。由于只有 3 个中心与 300 个样本，2 次迭代即到达不动点。
- 轮廓系数 $0.748$ 与 ARI $0.99$ 都表明划分与真实簇高度一致，但 ARI 使用了标签，轮廓系数没有；两者同时偏高说明该数据满足 K-Means 的凸簇假设。
- 若删去 `kmeans_pp` 改为随机取 $K$ 个样本，部分随机种子会使两个初始中心落在同一簇内，最终 $J$ 明显偏大，这是需要 `n_init` 多次重启的原因。
- 若删去空簇保护（`np.any(r == j)` 分支），当某中心失去全部样本时 `mean` 会产生 `nan`，后续距离计算全部失效。

### 代码二：K-Means、GMM、DBSCAN 的对比

```python
import numpy as np
from sklearn.datasets import make_blobs, make_moons
from sklearn.cluster import KMeans, DBSCAN
from sklearn.mixture import GaussianMixture
from sklearn.metrics import silhouette_score, adjusted_rand_score, normalized_mutual_info_score

def report(name, labels, X, truth):
    mask = labels >= 0                        # DBSCAN 的噪声点标签为 -1
    k = len(set(labels[mask]))
    sil = silhouette_score(X[mask], labels[mask]) if k > 1 else float("nan")
    print(f"{name:8s} 簇数 {k} 噪声 {int((labels < 0).sum()):3d} 轮廓系数 {sil:.4f} "
          f"ARI {adjusted_rand_score(truth, labels):.4f} NMI {normalized_mutual_info_score(truth, labels):.4f}")

X, y = make_blobs(n_samples=300, centers=3, cluster_std=0.9, random_state=1)
report("K-Means", KMeans(3, n_init=10, random_state=0).fit_predict(X), X, y)
report("GMM", GaussianMixture(3, covariance_type="full", random_state=0).fit_predict(X), X, y)
report("DBSCAN", DBSCAN(eps=0.6, min_samples=5).fit_predict(X), X, y)

Xm, ym = make_moons(n_samples=300, noise=0.05, random_state=0)
report("K-Means", KMeans(2, n_init=10, random_state=0).fit_predict(Xm), Xm, ym)
report("GMM", GaussianMixture(2, covariance_type="full", random_state=0).fit_predict(Xm), Xm, ym)
report("DBSCAN", DBSCAN(eps=0.2, min_samples=5).fit_predict(Xm), Xm, ym)
```

预期输出：

```text
K-Means  簇数 3 噪声   0 轮廓系数 0.7480 ARI 0.9900 NMI 0.9830
GMM      簇数 3 噪声   0 轮廓系数 0.7480 ARI 0.9900 NMI 0.9830
DBSCAN   簇数 3 噪声  26 轮廓系数 0.7736 ARI 0.8552 NMI 0.8233
K-Means  簇数 2 噪声   0 轮廓系数 0.4887 ARI 0.2408 NMI 0.1835
GMM      簇数 2 噪声   0 轮廓系数 0.4692 ARI 0.4697 NMI 0.3738
DBSCAN   簇数 2 噪声   0 轮廓系数 0.3285 ARI 1.0000 NMI 1.0000
```

解读：

- 三簇高斯数据上 K-Means 与 GMM 给出几乎相同的划分（轮廓 $0.7480$、ARI $0.99$），因为三个簇近似各向同性且尺寸接近，GMM 的协方差没有带来额外收益。
- DBSCAN 在该数据上把 26 个点判为噪声，ARI 降到 $0.8552$。$\varepsilon=0.6$ 相对于簇的标准差 $0.9$ 偏小，簇边缘的稀疏区域无法连成核心点。
- 双月数据上 K-Means 的 ARI 仅 $0.2408$，GMM 为 $0.4697$，二者都假设凸簇；DBSCAN 在 $\varepsilon=0.2$ 时 ARI 为 $1.0$，因为密度连通性与数据的真实结构一致。
- DBSCAN 在双月数据上的轮廓系数只有 $0.3285$，低于 K-Means 的 $0.4887$，但外部指标完全相反。这说明内部指标衡量的是簇的紧致与分离，不衡量形状是否正确；无标签场景下不能只用轮廓系数判断聚类质量。

### 代码三：NumPy 实现 GMM 的 EM

```python
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.mixture import GaussianMixture

def log_gauss(X, mu, cov):
    # 多元高斯的对数密度；用 slogdet 求 log|Sigma|，避免行列式下溢或上溢
    d = X.shape[1]
    diff = X - mu
    inv = np.linalg.inv(cov)
    _, logdet = np.linalg.slogdet(cov)
    maha = np.einsum("ni,ij,nj->n", diff, inv, diff)
    return -0.5 * (d * np.log(2 * np.pi) + logdet + maha)

def em_gmm(X, K, n_iter=60, seed=3):
    n, d = X.shape
    rng = np.random.default_rng(seed)
    pi = np.full(K, 1.0 / K)
    mu = X[rng.choice(n, K, replace=False)]
    cov = np.array([np.cov(X.T) + 1e-6 * np.eye(d) for _ in range(K)])
    history = []
    for _ in range(n_iter):
        # E 步：计算责任度
        logp = np.column_stack([np.log(pi[k]) + log_gauss(X, mu[k], cov[k]) for k in range(K)])
        mx = logp.max(1, keepdims=True)
        w = np.exp(logp - mx)
        s = w.sum(1, keepdims=True)
        gam = w / s
        history.append(float(np.mean(mx[:, 0] + np.log(s[:, 0]))))
        # M 步：加权矩估计
        Nk = gam.sum(0)
        pi = Nk / n
        mu = (gam.T @ X) / Nk[:, None]
        for k in range(K):
            diff = X - mu[k]
            cov[k] = (gam[:, k][:, None] * diff).T @ diff / Nk[k] + 1e-6 * np.eye(d)
    return pi, mu, cov, gam, history

X, _ = make_blobs(n_samples=300, centers=3, cluster_std=0.9, random_state=1)
pi, mu, cov, gam, history = em_gmm(X, 3)
print("前 8 次对数似然：", [round(v, 4) for v in history[:8]])
print("末次对数似然：", round(history[-1], 4))
print("单调不减：", all(history[i + 1] >= history[i] - 1e-12 for i in range(len(history) - 1)))
print("混合权重：", np.round(pi, 4))
print("均值：\n", np.round(mu, 3))
print("平均最大责任度：", round(float(gam.max(1).mean()), 4))
gm = GaussianMixture(3, covariance_type="full", random_state=0).fit(X)
print("sklearn 均值：\n", np.round(gm.means_, 3))
print("sklearn 对数似然：", round(float(gm.lower_bound_), 4), " sklearn 权重：", np.round(gm.weights_, 4))
```

预期输出：

```text
前 8 次对数似然： [-5.9063, -4.9356, -4.3809, -4.1484, -3.7978, -3.7709, -3.739, -3.7016]
末次对数似然： -3.6682
单调不减： True
混合权重： [0.3355 0.3312 0.3333]
均值：
 [[-10.063  -3.901]
 [ -7.039  -8.021]
 [ -1.474   4.407]]
平均最大责任度： 0.9987
sklearn 均值：
 [[ -1.474   4.407]
 [-10.062  -3.901]
 [ -7.039  -8.021]]
sklearn 对数似然： -3.6682  sklearn 权重： [0.3333 0.3356 0.3311]
```

解读：

- 对数似然逐轮上升，运行 60 轮后的末次值为 $-3.6682$，与 scikit-learn 的结果一致（分量的排列不同，即第 1 节所述的可辨识性）。
- 平均最大责任度 $0.9987$ 接近 $1$，说明该数据的簇高度分离，责任度近似退化为硬指派，GMM 与 K-Means 得到相同划分与第 6 节的极限关系相符。
- 若删去协方差中的 $10^{-6}\mathbf{I}$ 对角加载，某个分量在迭代中可能塌缩到单个样本，协方差奇异，`slogdet` 返回 $-\infty$，对数似然发散。
- 若 M 步忘记除以 $N_k$ 而直接累加 $\gamma_{ik}\mathbf{x}_i$，均值会被放大 $N_k$ 倍，下一次 E 步的距离全部失效。

## 易错点

> [!warning] 常见错误
> - 用簇内平方和 $J$ 选择 $K$。$J$ 随 $K$ 单调不增，$K=n$ 时为 $0$，必须配合肘部法、轮廓系数或外部指标使用。
> - 认为 Lloyd 算法收敛到全局最优。它只保证目标不增并停在坐标下降的不动点；不同初始化可能给出不同的局部最优，k-means++ 也只提供期望近似比。
> - 把责任度与硬指派混用。$\gamma_{ik}$ 是后验概率，样本可以同时以非零概率属于多个分量；用 `predict` 取 argmax 会丢失该信息，评估软聚类时应使用后验或对数似然。
> - 在非凸簇上使用 K-Means 或 GMM，并用轮廓系数证明结果「更好」。轮廓系数编码了凸、紧致的几何假设；双月数据上 DBSCAN 的 ARI 为 $1.0$ 而轮廓系数低于 K-Means，就是反例。
> - 混淆 DBSCAN 的核心点与边界点。核心点要求 $|N_\varepsilon|\ge\mathrm{minPts}$；边界点只在核心点邻域内、自身邻居不足，噪声点两者都不是。把边界点当作新的扩展源会错误地合并相邻簇。
> - 用 ARI 比较不同 $K$ 的结果而不说明基线。ARI 已对随机划分做期望校正，但不同 $K$ 的划分空间大小不同，跨 $K$ 比较仍需固定评估协议。

## 关联笔记

- 前置：[[PCA与降维]] —— 高维数据常先降维再聚类，且 PCA 的方差最大化与 K-Means 的簇内平方和最小化共享平方误差的结构。
- 前置：[[概率与统计]] —— GMM 的极大似然、协方差估计与后验概率是 EM 推导的基础。
- 后续：[[异常检测]] —— 基于距离、密度与似然的方法直接复用本篇的 $\varepsilon$-邻域、责任度与马氏距离。
- 对照：[[树模型与集成学习]] —— 树模型的分裂准则同样以不纯度下降为目标，但使用标签；聚类的不纯度没有标签可依，必须由几何假设替代。
- 应用：[[Embedding与向量检索]] —— 对嵌入做聚类可得到语义分组，聚类中心可作为倒排索引的粗量化码字。

## 达标检测

- [ ] 写出 K-Means 的目标函数与两步更新公式，说明每一步都不使目标增大，并解释算法为何在有限步内停在坐标下降不动点而非全局最优。
- [ ] 写出 k-means++ 的采样概率，并解释为什么使用距离的平方而不是距离。
- [ ] 从 Jensen 不等式构造 ELBO，完成 GMM 的 E 步责任度与 M 步三个参数更新公式的推导。
- [ ] 证明 EM 每轮对数似然不降，并说明该结论为什么不能推出收敛到全局最优。
- [ ] 说明 K-Means 是 GMM 在何种参数限制与极限下的特例，并写出对应的责任度表达式。
- [ ] 运行代码二，把 DBSCAN 的 `eps` 改为 $0.3$ 与 $1.0$，记录簇数、噪声数与 ARI，解释参数敏感性。
- [ ] 给定两个划分的列联表，手算 ARI 并判断该值是否优于随机划分。

## 参考来源

- Hastie, Tibshirani, Friedman, *The Elements of Statistical Learning*, 2009, 第 14 章 无监督学习 —— 对应本篇 K-Means 的簇内平方和目标、GMM 的 EM 推导与层次聚类的连接准则。
- Stanford CS229 课程讲义（Andrew Ng），EM 算法与高斯混合模型部分 —— 对应本篇 ELBO 的构造、责任度公式与 M 步的闭式解。
- d2l.ai《动手学深度学习》，附录 22.7 最大似然与 22.10 统计 —— 对应本篇对数似然、协方差估计与多元高斯密度的计算细节。
- Hastie, Tibshirani, Friedman, *The Elements of Statistical Learning*, 2009, 第 8 章 模型推断与平均（EM 算法一节）—— 对应本篇 EM 的单调性与收敛性讨论。
