机器学习数学推导（十八）：聚类算法

本文要解决什么#

面对一百万条没有标签的客户记录，能否自动找出有意义的分组？这就是 聚类——无监督学习中最基础的任务。与分类不同，聚类首先要回答一个棘手的问题：“相似”到底是什么意思？每种聚类算法本质上都是对这个问题的不同回答：它们从几何、概率或图论的角度，对“群组”施加了不同的先验假设。

你将学到：

1. K-means 如何被看作离散-连续混合目标上的坐标下降；Lloyd 算法为何总能收敛；以及 K-means++ 如何巧妙化解初始化难题。
2. 层次聚类 作为一种贪心合并过程，其链接准则如何控制簇的形状。
3. DBSCAN 基于密度连通性，为何能发现非凸簇并显式标记噪声。
4. 谱聚类 作为归一化割（NCut）的连续松弛，图拉普拉斯矩阵如何承担核心计算。
5. 高斯混合模型（GMM） 作为 K-means 的概率推广——你获得了什么（软分配、椭球协方差），又为此付出了什么代价。
6. 如何在无标签情况下评估聚类质量（轮廓系数、肘部法则），以及如何选择 $K$ 。

前置知识：线性代数（特征分解）、基础概率，以及第十三篇中介绍的 EM 算法。

聚类问题的数学表达#

什么样的聚类才算好？#

输入：数据集 $\mathbf{X} = \{\mathbf{x}_1, \dots, \mathbf{x}_N\}$ ，其中每个点 $\mathbf{x}_i \in \mathbb{R}^d$ 。

输出：分配结果 $\{c_1, \dots, c_N\}$ ，每个 $c_i \in \{1, \dots, K\}$ 。

两个相互制衡的原则：

• 高内聚：同一簇内的点应尽可能相似。
• 低耦合：不同簇之间的点应尽可能不相似。

我们后续写下的每一个目标函数，本质上都是对这两者的某种权衡。K-means、DBSCAN 与谱聚类之间的分歧，根源就在于它们对“相似”的度量方式各不相同。

距离与相似度的选择#

实操建议：所有距离度量对特征尺度都极为敏感。除非你的特征已在可比尺度上，否则务必先标准化再聚类。

无标签时如何评估聚类效果？#

其中 $a(i)$ 是点 $i$ 到同簇其他点的平均距离，$b(i)$ 是它到最近其他簇的平均距离。若 $s(i)$ 接近 1，说明该点稳稳地位于簇内部；接近 0 则处于边界；若为负值，则很可能被错误分配。对全数据集求平均 $s(i)$ ，即可得到一个无需真实标签的聚类质量评分。

K-means：以质心为中心的聚类#

目标函数#

这是一个同时优化离散分配 $\{c_i\}$ 和连续质心 $\{\boldsymbol{\mu}_k\}$ 的联合问题，一般属于 NP-hard。Lloyd 算法采用坐标下降策略：交替固定一组变量，优化另一组。

Lloyd 算法#

为何收敛？ 每一步都不会增加 $J$ 。第一步是最优的，因为每个点都被分到了最近的质心；第二步也是最优的，因为簇内均值是平方误差的唯一最小值（二阶导 $2|C_k|\mathbf{I}$ 正定）。由于 $J \geq 0$ 且单调递减，迭代必然在有限步内终止于某个局部最小值——实际数据中通常只需几十次迭代。如上图所示：质心从糟糕的初始位置逐渐漂移，决策区域随之重塑，$J$ 迅速下降并趋于稳定。

注意：局部最优陷阱。Lloyd 算法只能找到某个局部最小值，而非全局最优。糟糕的初始化可能导致两个质心挤在同一个真实簇内，而第三个质心却试图覆盖两个真实簇。标准对策是多次随机重启并保留 $J$ 最小的结果；更聪明的做法是使用 K-means++。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import numpy as np

def kmeans(X, K, max_iter=100):
    """朴素的 Lloyd 算法实现"""
    N = X.shape[0]
    centroids = X[np.random.choice(N, K, replace=False)]
    for _ in range(max_iter):
        dists = np.linalg.norm(X[:, None] - centroids[None, :], axis=2)
        labels = np.argmin(dists, axis=1)
        new_centroids = np.array(
            [X[labels == k].mean(axis=0) for k in range(K)]
        )
        if np.allclose(centroids, new_centroids):
            break
        centroids = new_centroids
    return labels, centroids

K-means++ 初始化#

思路很简单：让初始质心彼此远离——每次按点到已有质心的平方距离成比例地采样新质心。

1. 从 $\mathbf{X}$ 中均匀随机选取 $\boldsymbol{\mu}_1$ 。
2. 对 $k = 2, \dots, K$ ：计算 $D(\mathbf{x}_i)^2 = \min_{j < k} \|\mathbf{x}_i - \boldsymbol{\mu}_j\|^2$ ，然后以概率 $D(\mathbf{x}_i)^2 / \sum_l D(\mathbf{x}_l)^2$ 选取 $\boldsymbol{\mu}_k = \mathbf{x}_i$ 。

理论保证（Arthur & Vassilvitskii, 2007）：K-means++ 的期望目标值至多为 $8(\ln K + 2) \cdot J_{\text{opt}}$ ——这是一个关于 $K$ 的对数级近似，而且甚至不需要后续运行 Lloyd 迭代就能成立。

选 $K$ ：轮廓系数与肘部法则#

K-means 要求预先指定 $K$ 。下图展示了两种最常用的选择方法。

轮廓系数曲线通常在正确的 $K$ 处达到峰值，两侧则逐渐下降。肘部法则从另一个角度讲述同样的故事：

WCSS 随 $K$ 增大而严格递减（更多质心总能拟合得更好），因此我们要找的是拐点——在此之后增加簇数带来的收益急剧减少。一种稳健的启发式方法是：取曲线上距首尾两点连线垂直距离最大的点作为肘部。

局限#

层次聚类#

凝聚法#

自底向上构建一棵树状图（dendrogram）：

1. 起始时有 $N$ 个单点簇。
2. 合并距离最近的两个簇。
3. 重复此过程，直至只剩一个簇（或达到目标簇数 $K$ ）。

结果是一棵二叉树，每次合并的高度表示当时的簇间距离。若需扁平划分，只需在树上画一条水平线——被切断的每个分支即为一个簇。

链接准则#

合并规则取决于链接（linkage），即如何定义两个点集之间的距离：

对于大多数数值型数据，Ward 是默认选择，因其目标恰好对应 WCSS 的减少。

何时使用#

• 不知道 $K$ ，希望直观观察数据的自然粒度。
• 需要一个层次结构（如商品分类、基因家族）。
• 数据规模 $N$ 为中小级别（朴素实现复杂度 $O(N^3)$ ；使用优先队列可优化至 $O(N^2 \log N)$ ）。

DBSCAN：基于密度的聚类#

核心概念#

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）摒弃了“每个点必属某簇”的假设，转而采用密度规则。它依赖两个参数：邻域半径 $\epsilon$ 和最小点数 $\text{MinPts}$ 。

• $\epsilon$ -邻域：$N_\epsilon(\mathbf{x}) = \{\mathbf{x}' \in \mathbf{X} : \|\mathbf{x} - \mathbf{x}'\| \leq \epsilon\}$ 。
• 核心点：若 $|N_\epsilon(\mathbf{x})| \geq \text{MinPts}$ ，则 $\mathbf{x}$ 为核心点——位于稠密区域。
• 边界点：非核心点，但位于某个核心点的邻域内。
• 噪声点：既非核心也非边界，DBSCAN 显式将其标记为离群点。

密度可达性#

DBSCAN 通过核心点链式扩展簇：

• 直接密度可达：$\mathbf{x}'$ 在 $\mathbf{x}$ 的邻域内，且 $\mathbf{x}$ 是核心点。
• 密度可达：存在一条由直接密度可达关系组成的链，从 $\mathbf{x}$ 到达 $\mathbf{x}'$ 。
• 密度连通：两点均可从某个共同第三点密度可达。

一个簇是密度连通点的最大集合。正因如此，DBSCAN 能处理任意形状的簇——无需凸性假设、无需等半径、无需预设 $K$ 。

上图清晰展示了这一逻辑。高亮的核心点周围琥珀色圆圈内至少包含 $\text{MinPts}=5$ 个邻居，满足核心点条件。任何落入此类圆圈的点都会加入同一簇，并通过密度可达关系沿“月亮”形状向外传播。低密度区域的零散点无法积累足够邻居，最终被标记为噪声。

如何选择 $\epsilon$ ：K-距离图#

对每个点，计算其到第 $k$ 近邻的距离（取 $k = \text{MinPts}$ ），将这些距离降序排列后绘图。曲线会在“稠密”到“稀疏”的过渡处出现一个“膝盖”，此处的值即为 $\epsilon$ 的合理选择。

优势与局限#

优势：无需指定 $K$ ；能发现任意形状簇；显式识别噪声；对离群点鲁棒。

局限：两个参数 $\epsilon$ 与 $\text{MinPts}$ 相互耦合，调参困难；当簇间密度差异极大时表现不佳（此时可用 HDBSCAN）；在高维空间中，欧氏距离趋于集中，性能下降。

谱聚类：图论视角#

从数据到图#

为提升可扩展性，通常用 $k$ -近邻图或 $\epsilon$ -球图进行稀疏化。

图拉普拉斯矩阵#

换言之，$\mathbf{L}$ 衡量函数 $\mathbf{f}$ 在图边上的变化程度。在强连接节点间变化平缓的函数（即“光滑”函数）具有较小的拉普拉斯二次型，它们恰好对应 $\mathbf{L}$ 的最小特征值所对应的特征向量。

归一化割（NCut）目标#

其中 $\text{cut}(A,B) = \sum_{i \in A, j \in B} W_{ij}$ ，$\text{vol}(A) = \sum_{i \in A} D_{ii}$ 。除以体积可防止“切出单点”的平凡解。该组合优化问题是 NP-hard，但通过连续松弛（允许簇指示变量取实数值），可得到闭式解——这正是 $\mathbf{L}_{\text{sym}}$ 的特征值问题。

完整算法#

1. 构建相似度矩阵 $\mathbf{W}$ 。
2. 计算对称归一化拉普拉斯矩阵 $\mathbf{L}_{\text{sym}}$ 。
3. 求出对应最小特征值的 $K$ 个特征向量。
4. 将其按列堆叠为矩阵 $\mathbf{U} \in \mathbb{R}^{N \times K}$ 。
5. 对 $\mathbf{U}$ 的每一行进行单位长度归一化。
6. 对归一化后的行向量运行 K-means，得到离散簇标签。

为何有效？ 第 3 步将数据映射到低维嵌入空间，在此空间中，图上连通的簇变为线性可分的点云。K-means 在原始非凸数据上失败，但在该嵌入空间中却能成功。

复杂度：构建 $\mathbf{W}$ 为 $O(N^2)$ ，特征分解为 $O(N^3)$ 。对大规模 $N$ ，可使用稀疏 $k$ -NN 图配合 Lanczos 或 Nyström 近似。

高斯混合模型：带概率的 K-means#

生成模型#

通过 EM 算法拟合（见第十三篇）：

• E 步：计算后验责任 $\gamma_{ik} = \pi_k \mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k) / \sum_j \pi_j \mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_j, \boldsymbol{\Sigma}_j)$ 。
• M 步：加权更新 $\boldsymbol{\mu}_k = \sum_i \gamma_{ik} \mathbf{x}_i / \sum_i \gamma_{ik}$ ，协方差 $\boldsymbol{\Sigma}_k$ 与权重 $\pi_k$ 类似更新。

GMM 如何推广 K-means#

K-means 是 GMM 在 $\boldsymbol{\Sigma}_k = \sigma^2 \mathbf{I}$ 且 $\sigma \to 0$ 时的极限情形：方差趋近于零时，软后验 $\gamma_{ik}$ 坍缩为 one-hot 向量，M 步退化为质心均值计算。因此，K-means 本质上是 GMM 加上了两个强假设：球形等半径簇、硬分配。

GMM 放宽了这两点——它允许椭球协方差（可旋转、拉伸的簇）和软隶属度（一点可同时属于多个簇，如 70% A、30% B）。代价是参数更多、收敛更慢。

上图生动展示了差异。面对拉伸且倾斜的簇，K-means 的 Voronoi 单元以错误角度切割，将一个真实簇拆分给两个质心；而 GMM 的椭圆与数据协方差对齐，成功还原了真实划分。

综合运用：何时该用什么#

不同先验，各有胜场。下图对比了 K-means、DBSCAN 与谱聚类在三种经典数据形状上的表现：

解读如下：

• Blobs（第一行）：三者均成功——这是最简单的情形，K-means 速度最快。
• Moons（第二行）：K-means 将每个“月亮”从中切开（其凸性先验与非凸数据冲突）；DBSCAN 与谱聚类均能正确沿曲线划分。
• Circles（第三行）：K-means 再次因同样原因失败；DBSCAN 通过密度链区分内外环；谱聚类则利用图结构完成正确划分。

经验法则：

成本与复杂度对比#

上述五种算法的成本跨度达四个数量级。选错算法处理你的数据规模，是我见过最常见的错误——比如有人对百万点数据使用谱聚类，结果机器直接卡死。

实战中的关键数字：K-means 处理 100 万点 × 128 维 × 10 簇 × 30 次迭代，约需 $4 \times 10^{10}$ 次运算——现代 CPU 上约 30 秒。同样问题用层次聚类，仅存储 $10^{12}$ 项的距离矩阵（float32）就需 4 TB 内存。DBSCAN 配合 KD-tree 可在几分钟内完成；无索引则直接崩溃。谱聚类在 10 万点上，亲和矩阵已需 $10^{10}$ 字节内存——显然不可行。

这正是 mini-batch K-means 与 Nyström 近似谱聚类存在的原因：并非原算法有误，而是其常数项对现代数据规模而言过大。

生产环境中反复踩的坑#

在余弦相似的 embedding 上跑 K-means。若你的特征是 L2 归一化的文本或图像 embedding，欧氏距离等价于角度距离。但 K-means 通过欧氏平均计算质心，结果是非单位向量。下一轮分配时，“到单位向量的距离”与“到非单位向量的距离”混杂，悄然破坏几何结构。解决方法：每次 M 步后重新归一化质心（即 spherical K-means），或接受该偏差。

K-means 的“肘部”很少是真正的肘部。簇内平方和 $J(K)$ 随 $K$ 单调递减，眯眼任何曲线都像有肘。真实数据中曲线通常平滑，无明显拐点。建议改用 silhouette score 或 gap statistic——它们在正确 $K$ 处有最大值，而非仅拐点。更佳做法是让下游任务决定所需 $K$ ，而非完全依赖数据驱动。

DBSCAN 的 eps 高度依赖数据。这是聚类中最难调的超参。太小则全为噪声；太大则全归一簇。标准启发式是 k-distance 图：按每个点到其第 $k$ 近邻距离排序（$k = $ min_samples），取“膝盖”值为 eps。此法在 2–3 维效果良好，但在高维因最近邻距离集中而迅速失效。

GMM 在高维数据上使用 covariance_type='full'。每个成分有 $D(D+1)/2$ 个协方差参数。当 $D = 768$ （如 BERT embedding）且 $K = 50$ 时，协方差参数达 1400 万——几乎必然超过样本量。应改用 covariance_type='diag'，或先用 PCA 降至 $D = 50$ 。同样警告适用于 LDA、QDA 等需估计每类完整协方差的模型。

簇标签在不同运行间是任意的。K-means 两次运行可能得到相同划分，但标签编号不同。若需跨版本比较，应先用匈牙利算法对齐标签，或使用 adjusted Rand index 等标签无关指标。我曾见过整个仪表盘仅因重训后标签错位而“崩溃”。

练习题#

习题 1：K-means 收敛性 证明更新步骤在分配固定时能使 WCSS 最小化。

解 对 $\sum_{i \in C_k}\|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2$ 关于 $\boldsymbol{\mu}_k$ 求导并令导数为零，得 $\boldsymbol{\mu}_k = \tfrac{1}{|C_k|}\sum_{i \in C_k}\mathbf{x}_i$ 。Hessian 矩阵为 $2|C_k|\mathbf{I} \succ 0$ ，故为全局最小值。

习题 2：DBSCAN 设 $\text{MinPts} = 3$ ，$\epsilon = 0.5$ ，点 $\mathbf{x}$ 在半径 0.5 内有 2 个邻居。问 $\mathbf{x}$ 是否为核心点？

解 $\epsilon$ -邻域包含 $\mathbf{x}$ 自身及 2 个邻居，共 3 点。因 $3 \geq 3$ ，故 $\mathbf{x}$ 是核心点。（若 $\text{MinPts} = 4$ ，则为边界或噪声点。）

习题 3：GMM vs K-means 何时应选择 GMM 而非 K-means？

解 当簇呈椭圆形（各方向方差不同）、需要软分配（如下游贝叶斯推理）、或需可采样的生成模型时，选 GMM。若簇近球形、$N$ 极大、或需快速迭代，则用 K-means。

习题 4：链接准则 为何单链接在噪声数据上常失败？

解 单链接基于最小成对距离合并，故单个噪声点若连接两簇，即可引发“链式效应”将其合并。全链接与 Ward 链接使用聚合距离，对此类“桥接”更鲁棒。

习题 5：轮廓系数 已知 $a(i) = 2$ ，$b(i) = 5$ ，求 $s(i)$ 。

解 $s = (5 - 2)/\max(2, 5) = 3/5 = 0.6$ 。这是一个不错的分数：点 $i$ 到最近他簇的距离约为到自身簇距离的两倍。

下一步#

到此为止，传统机器学习的核心算法我都过了一遍——线性、树、核、贝叶斯、隐变量、序列、降维、聚类。但有一个共同点：它们的表达力都受限于人工设计的特征空间或核函数。下一章是这种限制的彻底突破——神经网络与反向传播。

神经网络让"特征"变成了和参数一起被学出来的东西：每一层都是上一层的非线性变换，训练就是用梯度下降同时优化所有层的权重。反向传播只是链式法则在计算图上的高效实现——它本身没有任何神秘成分，但它让"端到端学习"成为可能。我会把万能逼近定理、反向传播的雅可比形式、深度的指数表达力优势、损失景观为什么"看起来非凸但实际可优化"这几条主线推到底。读完之后，你会发现现代深度学习几乎全部是这一章思想的工程化外推。

参考文献#

[1] Lloyd, S. (1982). Least squares quantization in PCM. IEEE Trans. Info. Theory, 28(2), 129-137.

[2] Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. SODA, 1027-1035.

[3] Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. KDD, 226-231.

[4] Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. NIPS, 849-856.

[5] Von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17(4), 395-416.

[6] Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE Trans. PAMI, 22(8), 888-905.

[7] Ward, J. H. (1963). Hierarchical grouping to optimize an objective function. JASA, 58(301), 236-244.

[8] Campello, R. J., Moulavi, D., & Sander, J. (2013). Density-based clustering based on hierarchical density estimates (HDBSCAN). PAKDD, 160-172.

本文是 ML Mathematical Derivations 系列的第 18 章。下一章：第 19 章：神经网络与反向传播 。上一章：第 17 章：降维与主成分分析 。