# 第 10 章 无监督学习


> 没有标签时，"学习"还能学什么？本章的回答是把数据本身的结构当作监督信号：簇内要紧凑、簇间要分离、密度要足够高、中心要能代表成员。围绕这一个直觉展开 K-Means、层次聚类、DBSCAN、k-medoids 与 GMM 五条技术路线，并给出评价它们好坏的指标。

## 学习目标

读完本章，你应当能够：

1. 写出 K-Means 目标函数，**证明** Lloyd 算法的目标函数单调不增且有下界，从而说明它必收敛，并解释为什么只能收敛到局部最优；
2. 辨析内部指标（手肘法、轮廓系数、Davies-Bouldin、Calinski-Harabasz）与外部指标（ARI、NMI）的适用条件；
3. 写出四种链接准则的数学定义，说明 single-linkage 的链式效应与 complete-linkage 的球形偏好，并给出流式场景的层次聚类工程方案；
4. 严格写出 DBSCAN 的 ε-邻域、核心点、边界点、噪声点与"密度直达/可达/相连"的定义，说明边界点为何可能同属多簇，并用并查集实现；
5. 说明 k-medoids/PAM 与 K-Means 的差别、加权代价函数、swap 局部搜索为何单调收敛，以及浮点同分为何必须用 `EPS` 断号；
6. 写出 GMM 的 Q 函数，说明 EM 的 E 步与 M 步，以及它与 K-Means 的硬/软分配关系。

### 前置知识检查
| 你需要知道 | 在哪一节补齐 |
|---|---|
| 欧氏距离、曼哈顿距离、内积与范数 | 第 2 章 2.1 节 |
| 均值、方差、多元高斯分布与协方差矩阵 | 第 4 章 |
| 对数似然、Jensen 不等式、KL 散度 | 第 4 章 |
| 贪心算法、并查集（路径压缩/按秩合并） | 第 25 章 |
| 复杂度分析方法 | 第 22 章 |
| 浮点误差与 `EPS` 容差 | 第 26 章 |

## 10.1 聚类的基本问题与评价

### 10.1.1 四种结构假设

聚类（clustering）没有唯一正确答案，因为"什么算一个簇"取决于我们采用哪种结构假设：

| 结构假设 | 簇的形状 | 代表算法 |
|---|---|---|
| 中心型 centroid | 凸的、大致球形、大小相近 | K-Means、k-medoids、GMM |
| 连通型 connectivity | 任意形状，靠密度/邻近连起来 | DBSCAN、single-linkage |
| 分布型 distribution | 参数化分布生成的椭球 | GMM |
| 层次型 hierarchical | 嵌套结构，不切分就是一棵树 | AGNES、分裂式层次聚类 |

**这是本章最重要的一条元认知**：说"某算法聚类效果差"之前，先问"它假设的簇结构是否与数据相符"。K-Means 在"两个同心圆"上必然失败，但这不是算法缺陷，而是模型假设不匹配——同心圆是连通型结构。

### 10.1.2 内部指标与外部指标
| 类别 | 是否需要真实标签 | 典型指标 | 用途 |
|---|---|---|---|
| 内部指标 | **不需要** | SSE/Inertia、轮廓系数、Davies-Bouldin、Calinski-Harabasz | 无标签场景下选 K、比较算法 |
| 外部指标 | **需要**真实划分 | ARI（调整兰德指数）、NMI（标准化互信息）、Purity | 离线评测、有标注基准集上的比较 |

外部指标只在有真值时才可用，而聚类的典型场景恰恰没有真值——"用 ARI 选最佳 K"因此是典型错误（真题 `【09-09 选择 Q6】` 的干扰项）。

## 10.2 K-Means

### 10.2.1 目标函数（SSE / Inertia）

给定 `n` 个样本 `{x_i}` 与簇数 `K`，第 `j` 簇的中心记 `μ_j`、簇内样本集记 `C_j`。K-Means 最小化**簇内平方误差和**（Sum of Squared Errors，SSE，sklearn 中叫 inertia）：

```
J = Σ_{j=1}^{K} Σ_{x_i ∈ C_j} ‖x_i − μ_j‖²
```

它回答一个具体问题：**用 K 个代表点去近似全部数据，总误差有多大？** 用平方而不是绝对值，是因为它让"最优代表点"有闭式解（见下）。

### 10.2.2 Lloyd 算法与收敛性证明

Lloyd 算法在两步之间交替：**分配步**固定 `μ_j`，把每个样本分给最近的中心（`C_j = { i : j = argmin_k ‖x_i − μ_k‖² }`）；**更新步**固定 `C_j`，令 `μ_j` 取簇内均值。**为什么更新步是取均值？** 对 `J` 关于 `μ_j` 求导令零：

```
∂J/∂μ_j = Σ_{x_i ∈ C_j} 2(μ_j − x_i) = 0  ⟹  |C_j|·μ_j = Σ_{x_i ∈ C_j} x_i  ⟹  μ_j = 簇内均值
```

**收敛性证明（单调不增 + 有下界）：**

```
① 分配步不增：固定 μ_j 时，把每个点分给"最近的中心"是逐项取最小，
   故重新分配后 Σ_{x_i∈C_j}‖x_i − μ_j‖² 不会变大。
② 更新步不增：固定 C_j 时，簇内均值恰好是 argmin_μ Σ_{x_i∈C_j}‖x_i − μ‖²，
   故把 μ_j 换成均值后目标值也不会变大。
③ 于是 J_0 ≥ J_1 ≥ J_2 ≥ … 单调不增；又 J ≥ 0 有下界 ⟹ 数列收敛。
```

**为什么只能收敛到局部最优？** 两条原因都要说清：

1. `J` 关于（离散划分 `C`，连续中心 `μ`）的**联合优化是非凸的组合优化**，存在大量局部极小；
2. Lloyd 每一步只是"固定一个变量、优化另一个变量"的**坐标下降**（coordinate descent）。坐标下降在凸问题上能到全局最优，在非凸问题上只保证到达坐标方向上的局部极小——换个初始化会得到完全不同的结果。

### 10.2.3 k-means++ 初始化

随机初始化的后果很严重：若两个初始中心落进同一个真实簇，该簇会被强行拆开，另一个真实簇可能被合并——这个错误在坐标下降中**无法自我修复**（分配步只会把点分给更近的中心，不会跨簇跳回）。k-means++ 用"距离越大越容易被选"的策略改善起点，并保证 `E[J] ≤ 8(ln K + 2)·J_opt`。

> [!NOTE]
> k-means++ 只改善**期望**，不保证最优。工程上仍要配合 `n_init` 多次重启，取 SSE 最小的一次。

```text
k-means++ 初始化（伪代码）
  centers ← { 从 points 中均匀随机取 1 个点 }
  while |centers| < k:
      D²(p) ← p 到 centers 的最近平方距离            # 越远越可能被选中
      centers ← centers ∪ { 以概率 D²(p)/Σ_q D²(q) 抽取的点 p }
  选满 k 个中心后，跑标准 Lloyd 迭代
```

### 10.2.4 四个致命弱点
| 弱点 | 原因 | 应对 |
|---|---|---|
| 对特征尺度敏感 | 欧氏距离把各维等同看待，量纲大的特征主导距离 | 先标准化（z-score）再聚类 |
| 对离群点敏感 | 中心是**均值**，被极端值拉动；平方误差又放大了大误差 | 剔除离群点，或改用 k-medoids（10.5 节） |
| 对 K 敏感 | K 是超参，无法从数据自动确定 | 手肘法、轮廓系数（10.2.5 节） |
| 只找凸簇 | 目标函数偏好各向同性球形紧凑簇 | 换 DBSCAN 或谱聚类 |

### 10.2.5 K 值选择与三大内部指标

**手肘法（elbow method）**：画 SSE 随 K 的曲线。**K 增大时 SSE 必然单调下降**（`K = n` 时每点自成一簇、SSE = 0），所以不能取"SSE 最小"；要看的是**下降速度**：当 K 越过真实簇数后，继续增加 K 只能把本来紧凑的簇切开，SSE 的下降速度骤缓，曲线出现形如手肘的拐点，该拐点即为推荐的 K。

> [!IMPORTANT]
> 手肘法观察的指标就是 **SSE / Inertia**（真题 `【09-09 选择 Q6】`）。Davies-Bouldin 与轮廓系数是聚类效果的内部指标，用它们选 K 时看的是**极值**（轮廓最大、DB 最小），不叫手肘法；ARI 是需要真实标签的**外部**指标，K-Means 场景通常无标签可用。

| 指标 | 定义（`𝒞_i` 为 i 所在簇） | 优化方向 | 适用场景 |
|---|---|---|---|
| SSE / Inertia | `Σ_{C∈𝒞} Σ_{x∈C}‖x − μ_C‖²` | 越小越好，但随 K 单调降，故看**拐点** | 中心型簇、选 K |
| 轮廓系数 silhouette | `s(i) = (b(i) − a(i))/max(a(i), b(i))`，`a(i)` = i 到同簇其他点的平均距离，`b(i)` = i 到最近异簇的平均距离 | 最大（`s ∈ [−1,1]`） | 球形与非凸簇都可，但需 `O(n²)` 距离 |
| Davies-Bouldin | `DB = (1/K)·Σ_j max_{k≠j}(σ_j + σ_k)/d(μ_j, μ_k)`，`σ_j` 为簇内平均到中心距离 | 最小 | 偏好紧凑且分离的球形簇，计算便宜 |
| Calinski-Harabasz | `CH = [tr(S_B)/(K−1)]/[tr(S_W)/(n−K)]`，`S_B` 类间散度、`S_W` 类内散度 | 最大 | 方差分析思想，计算最快，偏好球形簇 |

## 10.3 层次聚类

凝聚式（AGNES，agglomerative nesting）**自底向上**：每个样本自成一簇，反复合并最近的两簇直到只剩一簇，最常用。分裂式（DIANA）**自顶向下**：全体样本先在一个簇里，反复挑一个簇劈开，计算量更大，但能在早期拿到粗粒度结构。

### 10.3.1 四种链接准则
簇间距离 `d(A, B)` 不能直接定义（`A`、`B` 是集合），必须靠链接准则归结为点对距离：

| 准则 | 数学定义 | 倾向 | 复杂度 |
|---|---|---|---|
| 单链接 single | `d(A,B) = min_{a∈A, b∈B} d(a,b)` | 擅长**细长/非凸**簇；易产生**链式效应** | 可用最小生成树加速到 `O(n²)` |
| 全链接 complete | `d(A,B) = max_{a∈A, b∈B} d(a,b)` | 倾向**紧凑球形**簇；对离群点敏感 | `O(n²)` ~ `O(n² log n)` |
| 平均链接 average（UPGMA） | `d(A,B) = (1/(\|A\|\|B\|))·Σ_{a∈A}Σ_{b∈B} d(a,b)` | 折中，最稳健 | 与全链接同阶 |
| 质心链接 centroid（UPGMC） | `d(A,B) = d(μ_A, μ_B)` | 计算最省，但可能出现**反转** | 最低 |

> [!NOTE]
> **链式效应（chaining）**：single-linkage 只要求**有一对**点足够近就合并两簇。若数据里有少数点像桥一样把两个本应分开的簇连起来，整条链会被串成一个巨大的簇。反过来，complete-linkage 要求**所有**跨簇点对都足够近，因此会把长条形的真实簇切碎成若干小球——**"优点"与"缺点"是同一个定义的两种表现**。真题 `【09-02 选择 Q9】` 考的就是 single 的定义。

**Lance-Williams 公式思想。** 朴素做法每合并一次都要重算所有簇间距离。Lance-Williams 指出多种准则的新簇距离都能写成旧距离的线性组合：

```
d(A ∪ B, C) = α_A·d(A,C) + α_B·d(B,C) + β·d(A,B) + γ·|d(A,C) − d(B,C)|
```

不同准则只是系数不同：single 取 `α_A = α_B = 1/2, β = 0, γ = −1/2`；complete 取 `γ = +1/2`；average 取 `α_A = |A|/(|A|+|B|)` 等。**它的价值在于把每次合并后 `O(K²)` 的重算降成 `O(K)` 的更新**，这是所有高效 HAC 实现的骨架。

### 10.3.2 复杂度与树状图

朴素 HAC 时间是 `O(n³)`（每轮 `O(n²)` 找最近对，共 n 轮），用优先队列 + Lance-Williams 更新可优化到 `O(n² log n)`；空间 `O(n²)`（要存整个距离矩阵，这是更硬的瓶颈）。因此 HAC **本质是批处理算法**：`n = 10000` 时距离矩阵就要约 800 MB。

树状图（dendrogram）以样本为横轴、**合并时的高度**（即当时的簇间距离）为纵轴。在某一高度横向切一刀，落在同一子树里的样本属于同一簇——**切的位置由业务决定，而且不只能切一刀**：同一棵树可产出从 2 簇到 n 簇的任意粒度划分。

```
高度
1.0 |                    ┌───────┐
    |             ┌──────┘       │
0.6 |      ┌──────┤              │
0.3 |  ┌───┤      │              │
    |──┴───┴──────┴──────────────┴──►  样本 A B C D E F
    在 0.6 高度切一刀 → 2 个簇 {A,B} 与 {C,D,E,F}
```

### 10.3.3 流式数据下的工程方案

朴素 HAC 无法随每条新数据实时重算，工业界的标准做法是**在线离线两级架构**（真题 `【09-02 选择 Q8】`）：

| 层级 | 目标 | 手段 | 代价 |
|---|---|---|---|
| 在线阶段 | 低延迟地把新样本快速归组 | 与已有簇心比阈值、LSH（局部敏感哈希）找近邻、维护微簇统计量 | 近似、有误差 |
| 离线阶段 | 周期性纠正在线阶段的近似误差 | 对累积数据（或微簇摘要）跑完整 HAC，重整/精修并输出层次结构 | 高，但频率低 |

**为什么用两级而不是只留一级？** 只在线会累积漂移，只离线则满足不了实时性；两级把"实时性"与"层次结构的准确性"解耦，各取所需。干扰项辨析：单样本全量重算在 `O(n²)` 空间上不可行；"改成监督学习"需要标签，而聚类本无标签；"丢掉历史簇"会让簇语义漂移并彻底失去层次信息。

## 10.4 DBSCAN

### 10.4.1 四个基本概念

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）用密度定义簇。给定半径 `ε` 与最小点数 `MinPts`：

| 概念 | 严格定义 | 要点 |
|---|---|---|
| ε-邻域 | `N_ε(p) = { q : d(p, q) ≤ ε }` | **包含 `p` 自身**（`d = 0`） |
| 核心点 core | `\|N_ε(p)\| ≥ MinPts` | 邻域够密，能向外"走" |
| 边界点 border | `p` 不是核心点，但存在核心点 `c` 使 `p ∈ N_ε(c)` | 被核心点覆盖，自己却不密 |
| 噪声点 noise | 既非核心点也非边界点 | 不被任何核心点覆盖 |

> [!WARNING]
> **邻域判定包含自身，所以计数器初值是 1 而不是 0。** 漏掉这一条会让每个点的 `Count` 都少 1，全部边界样本判错——这是真题 `【08-05 编程题 1】` 的第一个坑。第二个坑是**必须先确定完整的核心点集合，再标注边界点**：边界点的判据引用"最终核心点集合"，若边扫边判，下标靠前的点在判定时看不到后面尚未确定的核心点，同一组输入会因枚举顺序不同得出不同答案。

### 10.4.2 密度直达、密度可达、密度相连

这三个概念层层放宽，必须分清：

```
密度直达（directly density-reachable）：
   q 由 p 密度直达  ⟺  p 是核心点 且 q ∈ N_ε(p)
   不对称！p 核心、q 边界时 p→q 成立，q→p 不成立。
密度可达（density-reachable）：
   q 由 p 密度可达  ⟺  存在点链 p = p_1, p_2, …, p_m = q，
                        使每个 p_{i+1} 都由 p_i 密度直达。
   由"每步起点都是核心点"可推出：路径上除终点外全是核心点。仍不对称。
密度相连（density-connected）：
   p 与 q 密度相连  ⟺  存在点 o，使 p、q 都由 o 密度可达。
   这一条是对称的 ⟹ 它才是"同一个簇"的等价关系。
```

一句话概括：**直达是最短的一步，可达是沿核心点串起来的若干步，相连是"找到一个共同祖先能同时走到两者"。** 真题 `【09-11 编程题 2】` 的题面正是"存在核心点能走到 `p` 和 `q` 两个"。

### 10.4.3 边界点为什么可能同属多个簇

边界点 `b` 自己不是核心点，**不能作为路径的中间节点**，因此它无法把覆盖它的两个核心点连通。若 `b` 同时落在核心点 `c₁`、`c₂` 的邻域内，而 `c₁`、`c₂` 之间不存在核心点路径，则 `c₁`、`c₂` 分属两簇，而 `b` 通过 `c₁`、`c₂` 与两簇中的点都密度相连：

```
c₁ ∈ 簇1，c₂ ∈ 簇2，b ∈ N_ε(c₁) ∩ N_ε(c₂)
⟹ b 与簇1 的点密度相连，也与簇2 的点密度相连  ⟹ b 同属两簇
```

**这就是"边界点可能同属多个簇"的根源**：它没有能力合并两簇，却有资格与两簇都建立可达关系。因此给每个点只记**一个**簇编号，会在判断"`b` 与另一簇的点是否密度相连"时答错，必须记**簇集合**。

### 10.4.4 用并查集实现

把定义翻译成图论：以核心点为节点，若两个核心点互在对方的 ε-邻域内就连一条边（两端都是核心点，这是一次合法直达）。此时"核心点 `c` 能走到的核心点"恰好是它在图中的**连通块**。连通块用并查集维护：

```
cluster_set(i) = { find(i) }                                若 i 是核心点
               = { find(j) : j ∈ N_ε(i) 且 j 是核心点 }      若 i 是边界点（可含多个代表元）
               = ∅                                          若 i 是噪声点
```

查询 `a`、`b` 是否密度相连 ⟺ `cluster_set(a) ∩ cluster_set(b) ≠ ∅`。`a == b` 且为噪声点时交集为空、自然输出 0，与"噪声点不与任何点密度相连"一致。

```python
def find(parent, x):
    """并查集找根：迭代写法 + 路径减半，避免递归爆栈"""
    while parent[x] != x:
        parent[x] = parent[parent[x]]        # 指向祖父节点，每步把路径缩短一半
        x = parent[x]
    return x


def dbscan(n, points, eps, min_pts):
    """返回邻域表、核心点标记、以及每个点的簇集合"""
    lim = eps * eps + 1e-7                   # 平方比较省去开根号；容差让"恰好等于 ε"不漏判
    nb = [[j for j in range(n) if (points[j][0] - points[i][0]) ** 2
           + (points[j][1] - points[i][1]) ** 2 <= lim] for i in range(n)]
    core = [len(row) >= min_pts for row in nb]          # 邻域含自身，计数天然含自身
    parent = list(range(n))
    for i in range(n):                                   # 只有核心点才能向外迈步
        if core[i]:
            for j in nb[i]:
                if core[j]:                              # 两端都是核心点才连边
                    ri, rj = find(parent, i), find(parent, j)
                    if ri != rj:
                        parent[rj] = ri
    # 核心点只属于自己所在簇；边界点可同时挂在多簇上；噪声点的集合为空
    sets = [({find(parent, i)} if core[i] else
             {find(parent, j) for j in nb[i] if core[j]}) for i in range(n)]
    return nb, core, sets


def density_connected(sets, a, b):
    """两个点的簇集合有交集 ⟺ 存在核心点能同时走到它们"""
    return len(sets[a] & sets[b]) > 0
```

### 10.4.5 参数选择与复杂度
| 问题 | 说明 | 实践做法 |
|---|---|---|
| `MinPts` 怎么定 | 越大越保守，簇内要求更密 | 经验取 `2·d`（`d` 为维度），或按目标噪声比例反推 |
| `ε` 怎么定 | 最关键、最难调；太小则处处噪声，太大则全合成一簇 | k-距离图找拐点，`k = MinPts − 1` |
| 复杂度 | 暴力两两枚举 `O(n²)`；空间索引（KD 树、球树）可降到 `O(n log n)` | `n ≤ 2000` 时直接 `O(n²)` 更简单可靠 |
| 空间 | 邻域表最坏 `O(n²)` | 边算边用可降到 `O(n)` |
| 参数敏感性 | 不同密度区域无法共享同一组 `(ε, MinPts)` | 改用 HDBSCAN、OPTICS 等自适应密度方法 |

DBSCAN 最大的优点是**能发现任意形状的簇并显式给出噪声点**——噪声点不被强行分配，这是 K-Means 做不到的。

## 10.5 k-medoids 与 PAM

### 10.5.1 与 K-Means 的差别
| 维度 | K-Means | k-medoids / PAM |
|---|---|---|
| 中心是什么 | 簇内坐标的**均值**，可落在任意位置 | **必须是真实样本点**（medoid） |
| 目标函数 | `Σ_C Σ_{i∈C}‖x_i − μ_C‖²` | `Σ_C Σ_{i∈C} w_i·d(x_i, m_C)` |
| 距离度量 | 本质依赖平方欧氏距离（均值才最优） | 任意距离（曼哈顿、余弦、路网距离……） |
| 抗离群点 | 弱（均值被拉动） | 强（中心是真实点，不会被拉到空处） |
| 计算量 | 每轮 `O(nKd)` | 每轮 `O(K(n−K)²)`，明显更贵 |
| 可解释性 | 中心是平均出来的点，可能无实体 | 中心是真实样本，可直接指认 |

**加权代价函数**是工程常态：样本带有用户数 `u_i` 或重要性 `w_i` 时，代价要写成 `cost(C, m) = Σ_{i∈C} w_i·d(x_i, m)`。真题 `【09-09 编程题 2】` 的 CDN 选址正是这个口径——`cost(cluster, c) = Σ_{i∈cluster} u_i·d(city_i, city_c)`，一个城市里有多少用户，就贡献多少份距离。

### 10.5.2 Swap 局部搜索与单调收敛

PAM（Partitioning Around Medoids）每轮做两件事：**分配**（把样本分给最近的 medoid）与**换心**（对每个簇 `C_j` 在簇内枚举候选点 `c`，取代价 `cost(C_j, c)` 最小者为新 medoid）。**为什么一定会停？** 与 K-Means 同构的两段论证：

```
① 分配步在 medoid 固定时让总代价最小（逐点取最近 ⟹ 逐项最小）；
② 换心步在簇固定时让总代价最小（簇内枚举取最小值）；
③ 故总代价单调不增；又代价 ≥ 0 有下界；
④ 从 n 个点中选 K 个 medoid 的配置只有有限多种 ⟹ 必在有限轮内稳定。
```

与 K-Means 的**唯一结构性差别**在第 ② 步：K-Means 能用闭式解一步跳到最优均值，PAM 只能在簇内的离散候选里枚举，因为中心必须落在真实点上。

> [!IMPORTANT]
> **浮点同分必须用 `EPS` 断号。** 判据不能写成 `cost < best_cost`：两个候选的代价**数学上相等**时，浮点累加误差（约 `1e−15`）会让谁赢由末位误差决定，与"同分取序号靠前"的规则对不上。正确写法是 `cost < best_cost − EPS`，取 `EPS = 1e−9`——它比累加噪声大一个量级，又远小于真实可分辨的代价间隙。同理，分配步"等距取序号靠前"只需实现为"**只有严格更优才改判**"，先遍历到的自然胜出。其他细节：**空簇**没有候选点、保持原 medoid 不动；覆盖用户数按最终分簇统计；输出前按 `(x, y)` 排序。

## 10.6 GMM 与 EM 算法

### 10.6.1 高斯混合模型与隐变量视角

K-Means 的硬分配（一个点要么完全属于某簇、要么完全不属于）在很多场景过于武断。高斯混合模型（Gaussian Mixture Model, GMM）假设数据由 `K` 个高斯分布混合生成：

```
p(x) = Σ_{k=1}^{K} π_k·N(x | μ_k, Σ_k),     π_k ≥ 0,  Σ_k π_k = 1
```

其中 `π_k` 是第 `k` 个成分的**混合权重**。引入隐变量 `z_i ∈ {1,…,K}` 表示"样本 `i` 由哪个成分生成"，模型变成两层：先按 `π` 抽 `z_i`，再按 `N(μ_{z_i}, Σ_{z_i})` 抽 `x_i`。**这就是"软分配"的来源**——`z_i` 观测不到，只能算它的后验概率（称为**责任度** responsibility）：

```
γ_{ik} = P(z_i = k | x_i) = π_k·N(x_i | μ_k, Σ_k) / Σ_j π_j·N(x_i | μ_j, Σ_j)
```

### 10.6.2 E 步、M 步与单调性

直接最大化对数似然 `ℓ(θ) = Σ_i ln Σ_k π_k N(x_i|μ_k,Σ_k)` 时对数里套着求和，无法解析求解。EM（Expectation-Maximization）用 Jensen 不等式构造一个**下界**并反复抬高它，其 Q 函数为 `Q(θ, θ^(t)) = Σ_i Σ_k γ_{ik}^(t)·[ ln π_k + ln N(x_i | μ_k, Σ_k) ]`。其中 `γ_{ik}^(t)` 由上一轮参数算出（E 步），再对 `Q` 关于 `(π_k, μ_k, Σ_k)` 求导令零（M 步）：

| 步 | 动作 | 更新式 |
|---|---|---|
| E 步 | 固定参数，算责任度 | `γ_{ik} = π_k N(x_i\|μ_k,Σ_k) / Σ_j π_j N(x_i\|μ_j,Σ_j)` |
| M 步 | 固定责任度，最大化 `Q` | `N_k = Σ_i γ_{ik}`；`π_k = N_k/n`；`μ_k = (1/N_k)Σ_i γ_{ik}x_i`；`Σ_k = (1/N_k)Σ_i γ_{ik}(x_i−μ_k)(x_i−μ_k)ᵀ` |

**单调性直觉**：E 步构造出 `ℓ(θ)` 在 `θ^(t)` 处的一个**紧下界**，且 `Q(θ^(t),θ^(t)) = ℓ(θ^(t))`；M 步把 `Q` 抬到最大值。因为下界永不超过真值：

```
ℓ(θ^(t+1)) ≥ Q(θ^(t+1), θ^(t)) ≥ Q(θ^(t), θ^(t)) = ℓ(θ^(t))
```

即**对数似然单调不降**。这解释了 EM 为什么稳定（不会像梯度上升那样来回震荡），也解释了它为什么只到**局部最优**——抬高下界不等于把真值抬到全局最大。

### 10.6.3 与 K-Means 的关系
| 对比项 | K-Means (Lloyd) | GMM + EM |
|---|---|---|
| 分配方式 | 硬分配（0/1），按最近中心 | 软分配（责任度 `γ_{ik} ∈ (0,1)`） |
| 簇形状 | 各向同性球形（隐含等方差） | 任意椭球（`Σ_k` 自由） |
| 目标 | 最小化 SSE | 最大化对数似然 |
| 收敛保证 | SSE 单调不增有下界 | 对数似然单调不降 |
| 极限关系 | 令所有 `Σ_k = σ²I` 且 `σ² → 0`，责任度退化为 0/1 硬分配，EM 退化为 Lloyd | — |

**K-Means 是 GMM 的极限特例**：所有成分共享同一个各向同性协方差、且该方差趋于 0 时，责任度由 `exp(−‖x−μ_k‖²/(2σ²))` 决定；`σ² → 0` 时只有最近的成分责任度为 1、其余为 0，软分配退化为硬分配，EM 也就退化成了 Lloyd。

## 10.7 评价指标的适用矩阵
| 指标 | 内部/外部 | 需要标签 | 对簇形状的假设 | 复杂度 | 什么时候用 |
|---|---|---|---|---|---|
| SSE / Inertia | 内部 | 否 | 球形 | `O(nKd)` | 选 K（看拐点）、同算法不同初始化的比较 |
| 轮廓系数 | 内部 | 否 | 弱（由距离度量决定） | `O(n²)` | 中小数据上比较不同算法 |
| Davies-Bouldin | 内部 | 否 | 球形、大小相近 | `O(nKd)` | 大数据快速比较，偏好紧凑簇 |
| Calinski-Harabasz | 内部 | 否 | 球形 | `O(nKd)` | 快速选 K，结论常与 SSE 一致 |
| ARI / NMI | 外部 | **是** | 无 | `O(n²)` / `O(n + K²)` | 有真值基准上的算法比较 |

> [!TIP]
> **不要用内部指标去证明"业务上正确"。** 内部指标只度量几何结构，而聚类在工程中的价值往往由下游任务决定（如用户分群后的转化率）。实践中用"内部指标筛掉明显不合理的 K + 业务指标定稿"的两段式流程。

## 本章小结
| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| K-Means 目标 | `J = Σ_j Σ_{i∈C_j}‖x_i − μ_j‖²`，更新步取均值是 `J` 的最优解 | 以为中心必须落在样本点上 |
| 收敛性 | 分配步与更新步各自不增，`J ≥ 0` 有下界 ⟹ 必收敛 | 把"收敛"等同于"到全局最优" |
| 局部最优 | Lloyd/EM 都是非凸问题上的坐标下降 | 以为多跑几轮能跳出局部最优 |
| k-means++ | 以正比于 `D(x)²` 的概率选下一个中心，期望意义下有常数倍保证 | 以为它保证最优（仍需 `n_init` 重启） |
| 手肘法 | 看 SSE 随 K 的**拐点** | 把轮廓系数极值称作手肘法 |
| 内部 vs 外部 | 内部（SSE、轮廓、DB、CH）不需标签；ARI/NMI 需要 | 用 ARI 选 K |
| 四种链接 | single = 最近点对，complete = 最远点对，average = 均值，centroid = 中心距离 | 把 single 与 complete 记反 |
| 链式效应 | single-linkage 只要求一对点近就合并两簇 | 以为 single 更适合所有非凸数据 |
| 在线层次聚类 | 在线近似归组 + 离线 HAC 重整的两级架构 | 想到"单样本全量重算" |
| DBSCAN 计数 | 邻域**含自身**，计数初值为 1 | 初值写 0，边界点全判错 |
| 密度相连 | `∃o` 使 `p`、`q` 都由 `o` 密度可达（对称关系） | 与"密度可达"混为一谈 |
| 边界点多簇 | 边界点不能作路径中间节点，故可同属多簇 | 只记一个簇编号 |
| k-medoids | 中心必须是真实样本；代价按权重加权 | 用均值当中心 |
| 同分断号 | 判据写 `cost < best − EPS`，`EPS = 1e−9` | 写 `cost < best`，结果被末位误差决定 |
| GMM/EM | E 步算责任度，M 步闭式更新；对数似然单调不降 | 以为 EM 能保证全局最优 |

## 自测题

**Q1**（证明）证明 K-Means 的 Lloyd 算法一定在有限步内收敛，并说明它为什么只能收敛到局部最优。

<details><summary>答案与解析</summary>
**收敛性**：设第 `t` 轮后的目标值为 `J_t`。
- 分配步：固定中心时把每个点分给最近的簇，是逐项取最小，`J` 不增；
- 更新步：固定划分时，簇内均值是 `argmin_μ Σ_{i∈C}‖x_i − μ‖²`（由 `∂J/∂μ_j = 2Σ(μ_j − x_i) = 0` 得到），`J` 也不增。

因此 `J_0 ≥ J_1 ≥ … ≥ 0`，单调不增且有下界 ⟹ 收敛。又划分方式只有有限多种，一旦划分不再改变、中心也不再改变，故在**有限步**内稳定。
**局部最优**：`J` 关于（离散划分，连续中心）的联合优化是非凸的组合优化，存在大量局部极小；Lloyd 只是坐标下降（固定一个变量优化另一个），在非凸问题上只能到达坐标方向上的局部极小，换初始化会得到不同结果——这正是需要 k-means++ 与多次重启的原因。
</details>

**Q2**（辨析）"手肘法"观察的是哪个指标？为什么不能用 ARI，也不能用轮廓系数的极值代替？

<details><summary>答案与解析</summary>
观察的是 **SSE（簇内样本到各自簇心的平方距离和，sklearn 中叫 Inertia）**。
- **不能用 ARI**：ARI 是外部指标，需要真实标签，而 K-Means 场景通常没有标签；
- **不能用轮廓系数极值代替**：轮廓系数、Davies-Bouldin 是聚类效果的内部指标，用它们选 K 时看的是**极值**（轮廓最大、DB 最小），与"下降速度骤缓的拐点"是两回事，不叫手肘法；
- SSE 随 K 必然单调下降（`K = n` 时 SSE = 0），所以不能取最小值，只能看**下降速度的拐点**。
</details>

**Q3**（定义）写出 DBSCAN 中"密度直达""密度可达""密度相连"的严格定义，指出哪个是对称关系，并解释为什么边界点可能同时属于多个簇。

<details><summary>答案与解析</summary>
- **密度直达**：`q` 由 `p` 密度直达 ⟺ `p` 是核心点且 `q ∈ N_ε(p)`。**不对称**——`p` 核心、`q` 边界时 `p→q` 成立而 `q→p` 不成立。
- **密度可达**：`q` 由 `p` 密度可达 ⟺ 存在点链 `p = p_1, …, p_m = q`，使每个 `p_{i+1}` 都由 `p_i` 密度直达。仍**不对称**（终点可为边界点）。
- **密度相连**：`p` 与 `q` 密度相连 ⟺ 存在点 `o` 使 `p`、`q` 都由 `o` 密度可达。**对称**，它才是"同簇"的等价关系。

**边界点多簇的原因**：边界点自己不是核心点，**不能作为路径的中间节点**，因此无法把覆盖它的两个核心点连通。若 `b` 同时落在核心点 `c₁`、`c₂` 的邻域内而 `c₁`、`c₂` 之间没有核心点路径，则 `c₁`、`c₂` 分属两簇，而 `b` 通过它们与两簇中的点都密度相连，故 `b` 同属两簇。实现上必须给边界点记**簇集合**而非单个簇编号。
</details>

**Q4**（实现/辨析）k-medoids 选址问题中，为什么"严格更优"的判据不能写成 `cost < best_cost`？应该怎么写？还有哪些必须注意的细节？

<details><summary>答案与解析</summary>
两个候选中心的代价可能**数学上完全相等**，但在浮点下累加结果相差约 `1e−15`。若用 `cost < best_cost`，同分时谁胜出取决于末位误差，与题面规定的"选序号靠前"不一致，答案不稳定。

正确写法是 `cost < best_cost − EPS`，取 `EPS = 1e−9`：它比浮点累加噪声大一个量级、能吸收误差，又远小于真实可分辨的代价间隙、不会把"略有优势"误判成同分。分配步"等距取序号靠前"实现为"只有严格更近才改判"即可。

其他细节：**空簇**没有候选城市，保持原址不动；覆盖用户数按**最终分簇**统计；输出前按 `(x, y)` 排序。
</details>

**Q5**（推导）写出 GMM 的 Q 函数与 EM 的 E 步、M 步更新式，说明 EM 为什么单调不降、为什么仍可能只到局部最优。

<details><summary>答案与解析</summary>
`Q(θ, θ^(t)) = Σ_i Σ_k γ_{ik}^(t)·[ ln π_k + ln N(x_i|μ_k,Σ_k) ]`。**E 步**算责任度 `γ_{ik} = π_k N(x_i|μ_k,Σ_k) / Σ_j π_j N(x_i|μ_j,Σ_j)`；**M 步**令 `N_k = Σ_i γ_{ik}`，则 `π_k = N_k/n`、`μ_k = (1/N_k)Σ_i γ_{ik}x_i`、`Σ_k = (1/N_k)Σ_i γ_{ik}(x_i−μ_k)(x_i−μ_k)ᵀ`。

**单调不降**：E 步构造出 `ℓ(θ)` 在 `θ^(t)` 处的**紧下界** `Q`，满足 `Q(θ^(t),θ^(t)) = ℓ(θ^(t))`；M 步把 `Q` 抬到最大。于是 `ℓ(θ^(t+1)) ≥ Q(θ^(t+1),θ^(t)) ≥ Q(θ^(t),θ^(t)) = ℓ(θ^(t))`。

**仍可能局部最优**：抬高下界不等于把真值抬到全局最大；`ℓ(θ)` 因含隐变量而关于 GMM 参数非凸，EM 只保证稳定上升。实践中仍需多次随机初始化取似然最大的一次。
</details>

## 与真题的关联
| 真题 | 考查角度 | 对应本章小节 |
|---|---|---|
| 【09-09 选择 Q6】手肘法 | 手肘法观察 SSE/Inertia 的拐点；DB/轮廓看极值；ARI 需标签 | 10.2.5 |
| 【09-02 选择 Q9】单链接定义 | single-linkage = 两簇中最近样本点的距离 | 10.3.1 |
| 【09-02 选择 Q8】在线层次聚类 | 工业方案 = 在线轻量近似归组 + 离线 HAC 重整的两级架构 | 10.3.3 |
| 【08-05 编程题 1】DBSCAN 点分类 | 邻域含自身、计数初值为 1；必须先定全部核心点再标边界点 | 10.4.1 |
| 【09-11 编程题 2】密度相连与并查集 | 核心点之间才连边；边界点可能同属多簇需记簇集合；距离用平方 + 容差 | 10.4.2、10.4.3、10.4.4 |
| 【09-09 编程题 2】k-medoids 选址 | 加权代价、swap 迭代单调收敛、同分用 `EPS` 断号 | 10.5.1、10.5.2 |

## 延伸阅读

- Hastie, Tibshirani, Friedman. *The Elements of Statistical Learning*, 第 14 章（聚类、GMM/EM）。
- Bishop. *Pattern Recognition and Machine Learning*, 第 9 章（EM 算法与混合模型，含单调性证明）。
- Ester et al. *A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise*（DBSCAN 原文, KDD 1996）。
- Kaufman, Rousseeuw. *Finding Groups in Data: An Introduction to Cluster Analysis*（PAM/k-medoids 的经典出处）。
- Arthur, Vassilvitskii. *k-means++: The Advantages of Careful Seeding*（SODA 2007）。


---

> 作者: [破戒僧](https://onlyblacktea.cn)  
> URL: https://onlyblacktea.cn/book/ai/ch10/  

