第十三章 聚类方法
聚类（Clustering）是机器学习中最常用的无监督学习方法之一，其核心目标是将数据集中的样本划分为若干个不相交的子集（称为簇），使得同一个簇内的样本在某种度量下彼此相似，而不同簇之间的样本差异显著。聚类分析不依赖任何先验标签信息，仅根据数据本身的内在结构来完成划分，因此广泛应用于数据挖掘、图像分析、模式识别、文本检索、生物信息学等众多领域。本章系统介绍聚类的基本概念、常用算法、距离度量方式以及聚类质量的评价方法。
13.1 距离度量
在聚类算法中，距离度量是衡量样本之间相似程度的核心工具。距离度量方式的选择直接影响聚类结果的优劣，因此应根据数据特性选择合适的度量标准。
欧氏距离
欧氏距离（Euclidean Distance）是欧几里得空间中两点之间的直线距离，也是聚类分析中最常用的距离度量。设两个样本向量 \(\mathbf{x}_i, \mathbf{x}_j \in \mathbb{R}^n\)，则欧氏距离定义为
欧氏距离的优点是计算简便且具有明确的几何含义，但其缺点在于对量纲敏感，且在高维空间中可能出现“维度灾难”问题，导致所有样本之间的距离趋同。
曼哈顿距离
曼哈顿距离（Manhattan Distance）又称城市街区距离，计算两个向量在各维度上绝对差异之和：
曼哈顿距离相比欧氏距离对异常值更具鲁棒性，因为在曼哈顿距离下，距离的累积不会因为单个维度上的大差异而被主导。
切比雪夫距离
切比雪夫距离（Chebyshev Distance）定义为各维度上绝对差异的最大值：
该度量在某些棋盘类问题（如国际象棋中的王移动距离）中有明确应用，也可用于描述系统性能中的“短板效应”。
闵可夫斯基距离
闵可夫斯基距离（Minkowski Distance）是欧氏距离和曼哈顿距离的统一推广，参数 \(p \geq 1\) 控制距离的计算方式：
当 \(p=1\) 时退化为曼哈顿距离，当 \(p=2\) 时退化为欧氏距离，当 \(p \to \infty\) 时趋近于切比雪夫距离。
马哈拉诺比斯距离
马哈拉诺比斯距离（Mahalanobis Distance）考虑了变量之间的协方差结构，能够消除量纲差异和相关性的影响：
其中 \(\mathbf{\Sigma}\) 为样本的协方差矩阵。当 \(\mathbf{\Sigma}\) 为单位矩阵时，马哈拉诺比斯距离退化为欧氏距离。该度量在处理特征间存在相关性或量纲不一致的数据时具有明显优势。
余弦相似度
余弦相似度（Cosine Similarity）衡量两个向量在方向上的接近程度，而非 magnitude 上的差异：
余弦相似度广泛应用于文本分析领域，因为文本数据的维度通常很高，且余弦相似度对文档长度不敏感。
13.2 层次聚类
层次聚类（Hierarchical Clustering）是一种通过构建聚类树（dendrogram）来组织数据的聚类方法。与划分式聚类（如 k-means）不同，层次聚类不需要预先指定簇的数量，而是根据数据的层次结构进行聚合或分裂。
AGNES 算法（凝聚式层次聚类）
AGNES（Agglomerative Nesting）是最常用的凝聚式层次聚类算法。其基本思想是：首先将每个样本视为一个单独的簇，然后逐步合并最相似的簇，直到所有样本归入同一个簇或达到终止条件。
算法步骤：
1。 初始化：将每个样本作为一个独立的簇，共 \(n\) 个簇。 2。 计算所有两两簇之间的距离矩阵。 3。 合并距离最近的两个簇，形成新簇。 4。 更新距离矩阵，计算新簇与所有剩余簇之间的距离。 5。 重复步骤 3 和 4，直至所有样本归入一个簇或满足终止条件。
簇间距离的计算方法有多种，不同方法会导致不同的聚类结果：
- 最近邻法（Single Linkage）：两个簇之间的距离定义为属于不同簇的两个样本之间的最小距离。
- 最远邻法（Complete Linkage）：两个簇之间的距离定义为属于不同簇的两个样本之间的最大距离。
- 平均法（Average Linkage）：两个簇之间的距离定义为所有跨簇样本对距离的均值。
- Ward 法：两个簇合并导致的误差平方和增量定义为它们之间的距离。
其中 \(\mathbf{m}_{C}\) 为簇 \(C\) 的均值向量。
DIANA 算法（分裂式层次聚类）
DIANA（Divisive Analysis）是与 AGNES 方向相反的分裂式层次聚类算法。其基本思想是：先将所有样本视为一个整体，然后逐步分裂出差异最大的子簇，直到每个样本自成一个簇或达到终止条件。
DIANA 算法的分裂策略通常基于以下原则：首先找到具有最大直径的簇，然后将该簇中与其他样本平均相异度最大的样本作为一个新的单点簇，再将剩余样本中与新簇足够相似的样本划入新簇，重复此过程。
凝聚式聚类的时间复杂度为 \(O(n^2 \log n)\)，空间复杂度为 \(O(n^2)\)；分裂式聚类的复杂度通常更高，但在某些场景下可以更好地发现全局性的层次结构。
13.3 K-Means 算法
K-Means（K均值聚类）是应用最为广泛的划分式聚类算法。其核心思想是：通过迭代优化，将 \(n\) 个样本划分为 \(K\) 个簇，使得每个样本到其所属簇中心的距离平方和最小。
算法描述
设数据集为 \(\mathcal{X} = \{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\}\)，其中 \(\mathbf{x}_i \in \mathbb{R}^d\)。K-Means 算法的目标是最小化总体平方误差（SSE，Sum of Squared Error）：
其中 \(C_i\) 表示第 \(i\) 个簇，\(\mathbf{m}_i = \frac{1}{|C_i|} \sum_{\mathbf{x} \in C_i} \mathbf{x}\) 为簇 \(i\) 的中心，\(\mathbf{U}\) 为样本—簇归属矩阵，\(\mathbf{M} = \{\mathbf{m}_1, \ldots, \mathbf{m}_K\}\) 为簇中心集合。
K-Means 标准算法（ Lloyd 算法）的迭代步骤：
1。 初始化：随机选择 \(K\) 个样本作为初始簇中心 \(\mathbf{m}_1^{(0)}, \ldots, \mathbf{m}_K^{(0)}\)，或使用 K-Means++ 等更优的初始化方法。 2。 分配阶段：对每个样本 \(\mathbf{x}_j\)，将其分配给距离最近的簇中心：
3。 更新阶段：重新计算每个簇的中心，即该簇所有样本的均值：
4。 迭代：重复步骤 2 和 3，直至簇中心不再发生变化或达到最大迭代次数。
算法特性
K-Means 算法具有以下重要特性：收敛性——在每次迭代中，分配阶段和更新阶段都会使目标函数值单调下降或保持不变，因此算法必在有限步内收敛。局部最优性——K-Means 求解的目标函数是非凸的，算法仅能保证收敛到局部最优解，而非全局最优解。不同的初始化可能导致截然不同的聚类结果。时间复杂度——每轮迭代的时间复杂度为 \(O(Knd)\)，其中 \(d\) 为特征维度。假设算法在 \(T\) 轮后收敛，则总时间复杂度为 \(O(TKnd)\)。簇形状偏好——K-Means 倾向于发现大小相近、形状为超球体的簇，因为其使用欧氏距离作为度量标准。
K-Means++ 初始化
K-Means++ 是对标准 K-Means 初始化方法的改进，旨在选择更好的初始簇中心，从而加速收敛并提高聚类质量。K-Means++ 的初始化策略如下：
1。 随机选择一个样本作为第一个簇中心 \(\mathbf{m}_1\)。 2。 对于每个样本 \(\mathbf{x}_j\)，计算其到已有簇中心的最近距离 \(D(\mathbf{x}_j) = \min_{i} \|\mathbf{x}_j - \mathbf{m}_i\|^2\)。 3。 以概率 \(P(\mathbf{x}_j) = \frac{D(\mathbf{x}_j)^2}{\sum_{l=1}^{n} D(\mathbf{x}_l)^2}\) 选择下一个簇中心（即距离越远的样本被选中的概率越大）。 4。 重复步骤 2 和 3，直至选出 \(K\) 个初始簇中心。 5。 使用标准 K-Means 算法进行迭代优化。
K-Means++ 的理论保证是：其期望初始误差（到真实簇中心的距离平方和）不超过 \(O(\log K)\) 倍的最优解。实验表明，K-Means++ 能够显著提升 K-Means 的聚类效果，尤其在数据维度较高或簇结构复杂时优势更为明显。
Arthur 和 Vassilvitskii 的后续研究进一步提出了 K-Means|| 算法（也称为批处理 K-Means++），通过并行化方式在 \(O(K)\) 轮迭代内完成初始化，比原始 K-Means++ 的 \(O(nK)\) 时间复杂度更适合大规模数据集。
13.4 DBSCAN 算法
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法，由 Ester 等人于 1996 年提出。与 K-Means 等划分式聚类方法不同，DBSCAN 能够发现任意形状的簇，并且可以识别并处理噪声点（outliers）。
核心概念
DBSCAN 引入了两个关键参数：邻域半径 \(\epsilon\) 和最小点数 \(\text{MinPts}\)。基于这两个参数，DBSCAN 定义了以下核心概念：
\(\epsilon\)-邻域：样本点 \(\mathbf{x}\) 的 \(\epsilon\)-邻域定义为所有与 \(\mathbf{x}\) 的距离不超过 \(\epsilon\) 的样本集合：
核心点（Core Point）：如果一个样本点的 \(\epsilon\)-邻域中包含至少 \(\text{MinPts}\) 个样本点，则该点被称为核心点：
边界点（Border Point）：如果一个样本点本身不是核心点，但其落在某个核心点的 \(\epsilon\)-邻域内，则该点被称为边界点。
噪声点（Noise Point）：既不是核心点也不是边界点的样本被称为噪声点。
直接密度可达（Directly Density-Reachable）：如果样本点 \(\mathbf{x}\) 是核心点，且样本点 \(\mathbf{y} \in N_{\epsilon}(\mathbf{x})\)，则称 \(\mathbf{y}\) 从 \(\mathbf{x}\) 直接密度可达。
密度可达（Density-Reachable）：如果存在一个样本序列 \(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_m\)，其中 \(\mathbf{x}_{i+1}\) 从 \(\mathbf{x}_i\) 直接密度可达，则称 \(\mathbf{y}\) 从 \(\mathbf{x}_1\) 密度可达。
密度相连（Density-Connected）：如果存在一个核心点 \(\mathbf{o}\)，使得样本点 \(\mathbf{x}\) 和 \(\mathbf{y}\) 都从 \(\mathbf{o}\) 密度可达，则称 \(\mathbf{x}\) 和 \(\mathbf{y}\) 密度相连。
算法流程
DBSCAN 算法的核心思想是：从任意一个核心点出发，通过密度可达关系遍历所有密度相连的样本，形成一个簇；然后继续处理未被访问的样本，重复上述过程。
算法步骤：
1。 标记所有样本为“未访问”。 2。 随机选择一个未访问的样本 \(\mathbf{p}\)。 3。 如果 \(\mathbf{p}\) 是核心点，则创建一个新簇 \(C\)，将 \(\mathbf{p}\) 及其 \(\epsilon\)-邻域内的所有样本加入 \(C\) 的种子集合。 4。 对种子集合中的每个样本 \(\mathbf{q}\)：如果 \(\mathbf{q}\) 未被访问，则标记为已访问并将其 \(\epsilon\)-邻域内的样本加入种子集合（如果是核心点）；如果 \(\mathbf{q}\) 不属于任何簇，则将其加入簇 \(C\)。 5。 重复步骤 2 至 4，直至所有样本均被访问。
算法特性
DBSCAN 具有以下显著优点：能够发现任意形状的簇，这是 K-Means 等基于距离的算法所不具备的能力；可以识别噪声点，将不属于任何稠密区域的样本标记为噪声，这在异常检测场景中非常有用；不需要预先指定簇的数量，簇的数量由数据分布自动决定。
然而 DBSCAN 也有明显缺点：参数 \(\epsilon\) 和 \(\text{MinPts}\) 的选择对结果影响很大，且在不同稠密度的数据集上难以选择一组普适的参数；当数据维度较高时，距离计算可能受到“维度灾难”的影响；DBSCAN 的时间复杂度通常为 \(O(n^2)\)，在处理大规模数据时效率较低。
OPTICS（Ordering Points To Identify the Clustering Structure）是 DBSCAN 的一个重要扩展算法，通过引入可达距离和核心距离的概念，能够同时识别不同密度的簇结构，并在可达图中通过“山谷”位置自动确定簇的边界。
13.5 ISODATA 算法
ISODATA（Iterative Self-Organizing Data Analysis Techniques Algorithm）是一种动态聚类算法，由 Ball 和 Hall 于 1967 年提出。与 K-Means 不同，ISODATA 能够根据聚类过程中的统计信息自动调整簇的数量，因此特别适合类别数未知或变化的数据集。
算法核心思想
ISODATA 在 K-Means 的基础上引入了两个关键机制：簇的合并——当两个簇中心距离过近或样本数过少时，将它们合并为一个簇；簇的分裂——当某个簇的方差过大或样本数过多时，将其分裂为两个子簇。这两种操作交替进行，使得聚类结果能够自适应数据的真实结构。
关键参数
ISODATA 引入了一组额外的控制参数：
- \(K\)：期望的簇数（算法尝试将数据划分为接近 \(K\) 个簇）。
- \(\theta_N\)：每个簇最小样本数阈值，低于此值的簇将被合并。
- \(\theta_S\)：簇内标准差阈值，用于判断是否需要分裂。
- \(\theta_C\)：簇间最小距离阈值，两个簇中心距离小于此值时将被合并。
- \(L\)：每次迭代最多允许合并的簇对数。
- \(I\)：最大迭代次数。
算法流程
ISODATA 算法的基本流程如下：
1。 初始化：设定控制参数 \(K, \theta_N, \theta_S, \theta_C, L, I\)，随机选择 \(K\) 个初始聚类中心。 2。 迭代过程： - 将样本分配到最近的聚类中心（与 K-Means 相同）。 - 如果某个簇的样本数 \(N_i < \theta_N\)，则删除该簇，将其样本重新分配。 - 计算每个簇内各维度的标准差 \(\sigma_{ij}\)，如果 \(\max_j \sigma_{ij} > \theta_S\) 且 \(N_i > 2\theta_N\)，则将该簇分裂为两个簇，新中心为原中心加上和减去该维度的某个增量。 - 计算所有簇中心之间的两两距离，如果某对距离 \(d_{ij} < \theta_C\)，且参与合并的簇数不超过 \(L\)，则将这两个簇合并，新中心为两个簇的加权平均。 3。 如果达到最大迭代次数 \(I\)，则停止；否则返回步骤 2。
与 K-Means 的区别
ISODATA 与 K-Means 的核心区别在于：K-Means 的簇数 \(K\) 是固定不变的，而 ISODATA 通过合并和分裂操作能够自适应地调整簇数；ISODATA 需要设置更多的控制参数，这既增加了算法的灵活性，也增加了参数调优的难度。在实际应用中，当聚类数量难以预先确定时，ISODATA 提供了一种无需过多先验知识即可进行聚类分析的有效手段。
13.6 轮廓系数
轮廓系数（Silhouette Coefficient）是评估聚类质量的一种常用指标，由 Peter Rousseeuw 于 1987 年提出。轮廓系数综合考虑了簇内的凝聚度（Cohesion）和簇间的分离度（Separation），能够对聚类结果给出整体评价。
定义
对于数据集中的每个样本 \(\mathbf{x}_i\)，首先定义两个量：
\(a(i)\)（簇内不相似度）：样本 \(\mathbf{x}_i\) 与其所属簇内所有其他样本的平均距离：
\(b(i)\)（簇间不相似度）：样本 \(\mathbf{x}_i\) 到与其距离最近的另一个簇的平均距离：
则样本 \(\mathbf{x}_i\) 的轮廓系数定义为
从公式可以看出，\(s(i)\) 的取值范围为 \([-1, 1]\)。当 \(s(i)\) 接近 \(1\) 时，说明样本与其所属簇非常接近，而与相邻簇相距较远，聚类效果良好；当 \(s(i)\) 接近 \(0\) 时，说明样本位于两个簇的边界上，聚类边界模糊；当 \(s(i)\) 接近 \(-1\) 时，说明样本更可能被错误地分配到了当前簇，实际上它与相邻簇更为接近。
整体轮廓系数
数据集的整体轮廓系数定义为所有样本轮廓系数的均值：
在实际应用中，整体轮廓系数的参考标准为：\(S > 0.5\) 表示聚类结构合理；\(0.25 < S \leq 0.5\) 表示聚类结构较弱，但仍有参考价值；\(S \leq 0.25\) 表示聚类结构不可靠，需要重新选择算法或参数。
优缺点
轮廓系数的优点在于：它是一个有界的归一化指标，易于理解和比较；它同时考虑了簇内紧密度和簇间分离度，能够全面评估聚类质量；它不需要真实标签信息，适用于无监督场景。
其缺点在于：计算复杂度为 \(O(n^2)\)，在处理大规模数据时开销较大；对于基于密度的聚类算法（如 DBSCAN）产生的非凸形状簇，轮廓系数的评估效果可能不佳，因为其基于距离的定义假设簇是紧凑的；对于噪声点和离群点较多的数据，轮廓系数可能偏低，影响整体评估。
除了轮廓系数之外，常见的聚类评价指标还包括 Calinski-Harabaz 指数（计算簇间方差与簇内方差的比值）、Davies-Bouldin 指数（计算各簇相似性的平均值）、调整兰德指数（ARI，用于有标签数据时）等。
13.7 各类算法比较与公式汇总
不同的聚类算法各有其适用场景和优缺点，在实际应用中需要根据数据特性、任务需求和计算资源选择合适的算法。
层次聚类的优势在于不需要预先指定簇数，能够提供数据的层次结构信息（通过 dendrogram 可视化），且能够发现任意形状的簇。但其计算复杂度较高，不适合大规模数据，且一旦合并或分裂就不能撤销，缺乏全局优化目标。
K-Means以其简洁高效著称，算法复杂度为线性，易于理解和实现，因此在工业界得到广泛应用。但其缺点是需要预先指定 \(K\) 值，只能发现大小相近的球形簇，对初始中心敏感，且容易陷入局部最优。
K-Means++在初始化阶段做了系统性优化，从理论上保证了初始化的质量，能够显著改善 K-Means 的聚类效果和收敛速度，目前已成为 K-Means 的标准初始化方法。
DBSCAN的最大优势在于能够发现任意形状的簇并自动识别噪声，不需要预先指定簇数，对噪声鲁棒。但其对参数 \(\epsilon\) 和 \(\text{MinPts}\) 敏感，在处理多密度数据集时表现不稳定。
ISODATA通过动态调整簇数来适应数据的真实结构，适合类别数未知或变化的应用场景。但其参数众多，参数设置缺乏明确准则，算法行为难以预测，在实际应用中不如 K-Means 和 DBSCAN 普及。
轮廓系数作为聚类评价指标，综合考虑了凝聚度和分离度，取值直观，但计算复杂度较高，且对非凸簇的评估能力有限。
在实际工程中，通常的做法是：先用层次聚类或轮廓系数辅助确定合理的簇数范围；然后尝试 K-Means（配合 K-Means++ 初始化）或 DBSCAN；最后用轮廓系数等指标评估聚类质量，根据评估结果调整算法参数或更换算法。
公式汇总表
| 编号 | 公式名称 | 公式 |
|---|---|---|
| (13.1) | 欧氏距离 | \(d(\mathbf{x}_i, \mathbf{x}_j) = \sqrt{\sum_{k=1}^{n}(x_{ik} - x_{jk})^2}\) |
| (13.2) | 曼哈顿距离 | \(d_1(\mathbf{x}_i, \mathbf{x}_j) = \sum_{k=1}^{n} \|x_{ik} - x_{jk}\|\) |
| (13.3) | 切比雪夫距离 | \(d_{\infty}(\mathbf{x}_i, \mathbf{x}_j) = \max_{k} \|x_{ik} - x_{jk}\|\) |
| (13.4) | 闵可夫斯基距离 | \(d_p(\mathbf{x}_i, \mathbf{x}_j) = \left( \sum_{k=1}^{n} \|x_{ik} - x_{jk}\|^p \right)^{\frac{1}{p}}\) |
| (13.5) | 马哈拉诺比斯距离 | \(d_M(\mathbf{x}_i, \mathbf{x}_j) = \sqrt{(\mathbf{x}_i - \mathbf{x}_j)^{\mathrm{T}} \mathbf{\Sigma}^{-1} (\mathbf{x}_i - \mathbf{x}_j)}\) |
| (13.6) | 余弦相似度 | \(\cos(\mathbf{x}_i, \mathbf{x}_j) = \frac{\mathbf{x}_i^{\mathrm{T}} \mathbf{x}_j}{\|\mathbf{x}_i\| \|\mathbf{x}_j\|}\) |
| (13.7) | 最近邻距离（Single Linkage） | \(d_{\text{single}}(C_i, C_j) = \min_{\mathbf{x} \in C_i, \mathbf{y} \in C_j} d(\mathbf{x}, \mathbf{y})\) |
| (13.8) | 最远邻距离（Complete Linkage） | \(d_{\text{complete}}(C_i, C_j) = \max_{\mathbf{x} \in C_i, \mathbf{y} \in C_j} d(\mathbf{x}, \mathbf{y})\) |
| (13.9) | 平均距离（Average Linkage） | \(d_{\text{average}}(C_i, C_j) = \frac{1}{\|C_i\| \cdot \|C_j\|} \sum_{\mathbf{x} \in C_i} \sum_{\mathbf{y} \in C_j} d(\mathbf{x}, \mathbf{y})\) |
| (13.10) | Ward 距离 | \(d_{\text{ward}}(C_i, C_j) = \sum_{\mathbf{x} \in C_i \cup C_j} \|\mathbf{x} - \mathbf{m}_{C_i \cup C_j}\|^2 - \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \mathbf{m}_{C_i}\|^2 - \sum_{\mathbf{x} \in C_j} \|\mathbf{x} - \mathbf{m}_{C_j}\|^2\) |
| (13.11) | K-Means 目标函数（ SSE ） | \(\min \sum_{i=1}^{K} \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \mathbf{m}_i\|^2\) |
| (13.12) | 簇中心更新公式 | \(\mathbf{m}_i^{(t+1)} = \frac{1}{\|C_i^{(t)}\|} \sum_{\mathbf{x} \in C_i^{(t)}} \mathbf{x}\) |
| (13.13) | K-Means++ 选择概率 | \(P(\mathbf{x}_j) = \frac{D(\mathbf{x}_j)^2}{\sum_{l=1}^{n} D(\mathbf{x}_l)^2}\) |
| (13.14) | DBSCAN \(\epsilon\)-邻域 | \(N_{\epsilon}(\mathbf{x}) = \{ \mathbf{y} \in \mathcal{X} : \|\mathbf{x} - \mathbf{y}\| \leq \epsilon \}\) |
| (13.15) | 轮廓系数（样本级） | \(s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}}\) |
| (13.16) | 轮廓系数（整体） | \(S = \frac{1}{n} \sum_{i=1}^{n} s(i)\) |
| (13.17) | 簇内不相似度 | \(a(i) = \frac{1}{\|C_i\| - 1} \sum_{\mathbf{x}_j \in C_i, j \neq i} d(\mathbf{x}_i, \mathbf{x}_j)\) |
| (13.18) | 簇间不相似度 | \(b(i) = \min_{C_k \neq C_i} \frac{1}{\|C_k\|} \sum_{\mathbf{x}_j \in C_k} d(\mathbf{x}_i, \mathbf{x}_j)\) |