第 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 的硬/软分配关系。

前置知识检查

10.1 聚类的基本问题与评价

10.1.1 四种结构假设

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

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

10.1.2 内部指标与外部指标

外部指标只在有真值时才可用，而聚类的典型场景恰恰没有真值——“用 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）：

1

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 求导令零：

1

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

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

1
2
3
4
5

① 分配步不增：固定 μ_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。

1
2
3
4
5
6

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 四个致命弱点

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

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

10.3 层次聚类

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

10.3.1 四种链接准则

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

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

1

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
2
3
4
5
6
7

高度
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】）：

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

10.4 DBSCAN

10.4.1 四个基本概念

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

密度直达（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₂ 与两簇中的点都密度相连：

1
2

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

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

10.4.4 用并查集实现

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

1
2
3

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，与"噪声点不与任何点密度相连"一致。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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 参数选择与复杂度

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

10.5 k-medoids 与 PAM

10.5.1 与 K-Means 的差别

加权代价函数是工程常态：样本带有用户数 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 同构的两段论证：

1
2
3
4

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

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

10.6 GMM 与 EM 算法

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

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

1

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）：

1

γ_{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 步构造出 ℓ(θ) 在 θ^(t) 处的一个紧下界，且 Q(θ^(t),θ^(t)) = ℓ(θ^(t))；M 步把 Q 抬到最大值。因为下界永不超过真值：

1

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

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

10.6.3 与 K-Means 的关系

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

10.7 评价指标的适用矩阵

本章小结

自测题

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

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

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

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

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

与真题的关联

延伸阅读

• 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）。