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

本文要解决什么

一百万条客户记录摆在面前，没有任何标签。能不能自动找出有意义的分组？这就是 聚类——无监督学习中最基础的任务。和分类不同，聚类逼着你先回答一个棘手的问题：“相似” 到底是什么意思？ 每一种聚类算法，本质上都是对这个问题的一种回答——是对"什么是一个群组"提出的某种几何、概率或图论假设。

本文的脉络：

1. K-means：把它视作离散-连续混合目标上的坐标下降；解释 Lloyd 算法为什么必然收敛；用 K-means++ 解决初始化难题。
2. 层次聚类：贪心合并的过程，以及链接准则如何决定簇的形状。
3. DBSCAN：基于密度连通性，能发现非凸簇并显式标出噪声。
4. 谱聚类：NCut 目标的连续松弛，图拉普拉斯矩阵在背后发力。
5. 高斯混合模型（GMM）：K-means 的概率推广——多了软分配和椭圆协方差，代价是更多参数与更慢的收敛。
6. 如何在没有标签时评估聚类质量：轮廓系数、肘部法则，以及如何选 $K$。

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

1. 把聚类问题写成数学

1.1 一个"好"的聚类长什么样

输入：数据集 $\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、谱聚类的所有分歧，归根到底都在于：它们如何度量"相似"。

1.2 距离与相似度

实操提醒：所有距离对特征量纲都敏感。除非特征已经处在可比的尺度上，否则先标准化再聚类。

1.3 没有标签时如何评估

轮廓系数对每个点 $i$ 定义为：

其中 $a(i)$ 是点 $i$ 到同簇其他点的平均距离，$b(i)$ 是它到 最近的另一个簇 的平均距离。$s(i) \approx 1$ 表示该点稳稳待在自己簇里；$s(i) \approx 0$ 表示它在簇边界；负值则说明它八成被分错了。把所有点的 $s(i)$ 求平均，就得到一个无需标签的整体质量指标。

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

2.1 目标函数

K-means 的目标是最小化 簇内平方和（WCSS）：

这是一个对离散的 $\{c_i\}$ 和连续的 $\{\boldsymbol{\mu}_k\}$ 联合优化的问题——一般情形下是 NP 难的。Lloyd 算法用 坐标下降 来近似：交替地固定一组变量、优化另一组。

2.2 Lloyd 算法

步骤 1（分配）：固定质心，把每个点分到最近的那个：

步骤 2（更新）：固定分配，由 $\partial J / \partial \boldsymbol{\mu}_k = 0$ 得到新质心：

为什么必然收敛。每一步都 只能让 $J$ 不增。步骤 1 是最优的，因为每个点都被分到了最近质心；步骤 2 也是最优的，因为簇内均值是平方误差的唯一最小值（二阶导 $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

2.3 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++ 的期望目标函数满足 $\mathbb{E}[J] \leq 8(\ln K + 2) \cdot J_{\text{opt}}$ ——一个对 $K$ 仅是对数因子的近似上界，而且 不需要后续 Lloyd 迭代 就能成立。

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

K-means 必须指定 $K$。下面两张图是最常用的两种选法。

轮廓曲线通常会在正确的 $K$ 处 出现峰值，两侧逐渐衰减。肘部图从另一个角度讲同一个故事：

WCSS 随 $K$ 增加严格下降（更多质心总能拟合得更好），所以我们要找的是 拐点——再加质心也带不来多少收益的位置。一种稳健的找法是：取曲线上"距首尾两点连线垂直距离最大"的那个 $K$。

2.5 局限

3. 层次聚类

3.1 凝聚式做法

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

1. 初始时每个点自成一簇，共 $N$ 个簇。
2. 找出距离最近的两个簇并合并。
3. 重复直到只剩一个簇（或者直到剩 $K$ 个）。

得到的是一棵二叉树，每次合并的高度对应当时的簇间距离。要得到一个扁平的划分，只需在树上画一条水平线——它切断的每根分支就是一个簇。

3.2 链接准则

合并规则取决于 链接（linkage）——也就是怎么定义两 组 点之间的距离：

Ward 是数值数据上的默认选项，因为它的目标本质就是 WCSS 的减少量。

3.3 什么时候用它

• 你不知道 $K$，想 亲眼看看 数据的天然颗粒度。
• 你需要一个 层次结构（比如商品分类、基因家族）。
• $N$ 不太大（朴素复杂度 $O(N^3)$；优先队列下 $O(N^2 \log N)$）。

4. DBSCAN：密度驱动的聚类

4.1 核心概念

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}$，处于稠密邻域。
• 边界点：自身不是核心，但落在某个核心点的邻域里。
• 噪声点：两者都不是——DBSCAN 显式把它当离群点对待。

4.2 密度可达性

DBSCAN 通过核心点之间的链条来生长簇：

• 直接密度可达：$\mathbf{x}'$ 落在 $\mathbf{x}$ 的邻域里，且 $\mathbf{x}$ 是核心点。
• 密度可达：存在一条由直接密度可达环节构成的链，从 $\mathbf{x}$ 到 $\mathbf{x}'$。
• 密度连通：两个点都从某个共同的第三点出发密度可达。

一个簇就是密度连通点的极大集合。这就是 DBSCAN 能处理任意形状簇的原因——不假设凸性，不假设半径相等，不需要预先给 $K$。

这张图把判定逻辑画得很清楚。被高亮的核心点周围的琥珀色圆圈里至少有 $\text{MinPts}=5$ 个邻居，因此它是核心点。任何落入类似圆圈的点都加入同一簇，密度可达关系沿着月亮形状一路传播下去。低密度区的零散点凑不齐邻居，被打上噪声标签。

4.3 选 $\epsilon$：K-距离图

对每个点，计算它到第 $k$ 近邻的距离（取 $k = \text{MinPts}$），把所有这些距离降序排列后画曲线。曲线会在某处出现"膝盖"——从稠密距离到稀疏距离的过渡点，就在这里取 $\epsilon$。

4.4 优势与局限

优势：不需要指定 $K$；能发现任意形状的簇；显式标出噪声；对离群点鲁棒。

局限：两个相互影响的参数（$\epsilon$ 与 $\text{MinPts}$）；当不同簇的密度差异很大时表现差（用 HDBSCAN 解决）；高维下欧氏距离集中，效果衰减。

5. 谱聚类：图论视角

5.1 从数据到图

把每个数据点当作图的节点，节点之间用带权边相连。最常见的相似度是高斯核：

为了可扩展，通常用 $k$ 近邻图或 $\epsilon$ 球图做稀疏化。

5.2 图拉普拉斯矩阵

定义 度矩阵 $D_{ii} = \sum_j W_{ij}$，未归一化拉普拉斯为

它的关键性质是：

也就是说，$\mathbf{L}$ 度量了一个函数 $\mathbf{f}$ 在边上的"波动量"。在图上变化平缓的函数——在强连接节点之间取值相近——拉普拉斯二次型 很小，而它们正是 $\mathbf{L}$ 最小特征值对应的特征向量。

对称归一化拉普拉斯 通过节点度做缩放，避免高度节点主导：

5.3 归一化割（NCut）目标

谱聚类要最小化的是图上的一种割：

其中 $\text{cut}(A,B) = \sum_{i \in A, j \in B} W_{ij}$，$\text{vol}(A) = \sum_{i \in A} D_{ii}$。除以体积可以避免"切下一个孤点"这种平凡解。组合优化版本是 NP 难的，但允许指示变量取实数值的 连续松弛 有闭式解——它正好是 $\mathbf{L}_{\text{sym}}$ 的特征值问题。

5.4 完整算法

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$ 近邻图加 Lanczos / Nyström 近似。

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

6.1 生成模型

GMM 假设每个点是这样产生的：先从类别分布采样一个成分 $z \sim \text{Categorical}(\pi_1, \dots, \pi_K)$，再从对应的高斯采样 $\mathbf{x} \sim \mathcal{N}(\boldsymbol{\mu}_z, \boldsymbol{\Sigma}_z)$。边缘密度为：

用 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$ 同理。

6.2 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 的椭圆与数据协方差对齐，恢复出了正确的划分。

7. 综合：什么时候用什么

不同的假设，不同的胜场。下面这张 3×3 网格在 K-means、DBSCAN、谱聚类和三种典型形状上做了对比：

读图：

• Blobs（第一行）：三种算法都成功——这是简单情形。K-means 最快。
• Moons（第二行）：K-means 把每个月亮拦腰切开（它的先验是凸的，数据不是）。DBSCAN 和谱聚类都正确地沿着曲线分簇。
• Circles（第三行）：同样的原因，K-means 再次失败。DBSCAN 通过密度链条把内外两环分别串起来；谱聚类利用图结构同样得到正确划分。

经验法则：

8. 习题

习题 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 个点，恰好 $\geq 3$，所以 $\mathbf{x}$ 是核心点。（如果 $\text{MinPts}$ 改为 4，它就是边界点或噪声点。）

习题 3：GMM vs 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.

系列导航

• 上一篇：第十七篇 – 降维与主成分分析
• 下一篇：第十九篇 – 神经网络与反向传播
• 查看本系列全部 20 篇文章