聚类算法：从经典方法到前沿实践的系统梳理

聚类（Clustering）是无监督学习的核心任务之一，旨在将样本划分为组，使组内样本相似、组间样本相异。它既是探索性数据分析的重要工具，也是在推荐系统、图像检索、异常检测、生物信息、网络社区发现、嵌入空间分析等场景中的基础能力。本文将系统梳理聚类的定义、发展脉络、原理与数学推导、适用场景与工程实战、最新研究进展与代码实现，并附上进一步学习资源。

一、什么是聚类？

• 定义：给定样本集$X={x_i}{i=1}^n$及相似度/距离度量，找到划分${C_k}{k=1}^K$使得簇内相似、簇间相异。无监督，无需标签。
• 关键要素：
  • 表示与度量：数据表示（特征、嵌入）与相似度（欧式、余弦、马氏、核相似等）。
  • 归纳偏置：几何形状（球状、非凸）、密度假设（簇为高密度区域）、图结构（图割）。
  • 模型复杂度：簇数$K$、密度阈值、图构建参数等。
• 目标：通常最小化某种代价（例如簇内平方和）、最大化某种准则（例如切割的标准化）。

二、发展脉络与方法谱系

• 原型/划分类：k-means、k-medoids、Gaussian Mixture（GMM, EM）、Bregman k-means、Kernel k-means。
• 层次类：凝聚（Agglomerative，单/全/平均/ward链接）、分裂（Divisive）。
• 密度类：DBSCAN、OPTICS、HDBSCAN、Mean Shift。
• 图/谱类：谱聚类（RatioCut/NCut松弛）、社区发现（Louvain/Leiden）。
• 子空间/高维：CLIQUE、PROCLUS、vMF混合、球面k-means。
• 贝叶斯非参数：Dirichlet过程混合（DP-GMM）、层次DP（HDP）。
• 深度聚类：DEC/IDEC、DeepCluster、SCAN、SwAV/DINO等“聚类-表示”联动的自监督方向。
• 大规模/流式：MiniBatch k-means、coreset/sketch、近似近邻加速的密度方法（HNSW+DBSCAN）。

三、距离与相似度：聚类的“地基”

• 常见度量：
  • 欧式$||x-y||_2$：几何直观，受尺度影响。
  • 余弦$1-\frac{x^\top y}{||x||,||y||}$：适合方向相似（文本、嵌入）。
  • 马氏$(x-\mu)^\top\Sigma^{-1}(x-\mu)$：考虑协方差的缩放。
  • Gower：异构特征（数值+分类型）。
• 高维效应（距离集中）：在高维上欧式距离区分度下降，常需归一化、降维（PCA/UMAP）、使用角度/余弦度量或球面建模（vMF）。
• 核相似与隐空间：通过核$k(x,y)=\phi(x)^\top\phi(y)$实现非线性可分的聚类（Kernel k-means、谱聚类）。

四、代表性算法与直观

• k-means：最小化簇内平方和（WSS），对球状、相近方差的簇表现好；快速但对初始化、异常点敏感。
• k-medoids（PAM/CLARA）：用样本作为原型，抗异常更强，适用非欧式距离。
• GMM+EM：软分配，能建模椭球簇与不等方差，提供不确定性与密度估计，便于用AIC/BIC选$K$。
• 层次聚类：无需先验$K$，可视化树状结构；Ward链接倾向球状簇，单链接易链化。
• DBSCAN：基于密度可达，能发现任意形状簇并识别噪声；对$eps$与minPts敏感，密度变化大时失效。
• HDBSCAN：DBSCAN的层次扩展，自动选择稳定簇，适应可变密度。
• Mean Shift：核密度估计的梯度上升，寻找模式个数不需预设；高维代价大、带宽敏感。
• 谱聚类：将数据图切割问题放到特征空间，通过拉普拉斯谱松弛实现；适合非凸结构，需构图与特征分解。
• 子空间/高维方法：在子空间度量结构（CLIQUE、vMF混合、球面k-means），缓解维度灾难。
• 约束/半监督聚类：Must-link/Cannot-link引导（COP-k-means、谱聚类带约束）。

五、数学推导与性质

• k-means目标与Lloyd迭代：
  • 目标：$J({C_k},{\mu_k})=\sum_{k=1}^K\sum_{x_i\in C_k}||x_i-\mu_k||_2^2$
  • 赋值步：$c_i\leftarrow\arg\min_k||x_i-\mu_k||^2$
  • 更新步：$\mu_k\leftarrow\frac{1}{|C_k|}\sum_{x_i\in C_k}x_i$
  • 性质：有限步单调下降，收敛到局部极小；时间复杂度近似$O(nKdI)$。
  • 关系：当簇协方差相同且球形时，k-means≈极大似然的极限；与PCA有联系（$K=1$时等价均值；谱松弛与核k-means相关）。
• Bregman硬聚类：对任意严格凸$F$的Bregman散度$D_F(p,q)=F(p)-F(q)-\langle\nabla F(q),p-q\rangle$，与“均值”更新依然成立（如KL导致质心为经验均值的指数族参数）。
• Kernel k-means：在特征映射$\phi$空间做k-means，目标可用核矩阵$K$表示，避免显式$\phi$。
• GMM的EM：
  • 似然：$p(x_i)=\sum_{k=1}^K\pi_k\mathcal{N}(x_i|\mu_k,\Sigma_k)$
  • E步：$\gamma_{ik}=\frac{\pi_k\mathcal{N}(x_i|\mu_k,\Sigma_k)}{\sum_j\pi_j\mathcal{N}(x_i|\mu_j,\Sigma_j)}$
  • M步：$N_k=\sum_i\gamma_{ik}$，$\mu_k=\frac{1}{N_k}\sum_i\gamma_{ik}x_i$，$\Sigma_k=\frac{1}{N_k}\sum_i\gamma_{ik}(x_i-\mu_k)(x_i-\mu_k)^\top$，$\pi_k=\frac{N_k}{n}$
  • 性质：每步不减小对数似然；可用AIC/BIC选$K$；可扩展到vMF混合（球面）。
• 谱聚类与图割：
  • 图$G=(V,W)$，度矩阵$D$，拉普拉斯$L=D-W$或规范化$L_{sym}=D^{-1/2}LD^{-1/2},L_{rw}=D^{-1}L$
  • NCut松弛将离散指示向量放松为实向量，求$L_{sym}$最小的前$K$个特征向量$U$，再对$U$行做k-means。
  • 性质：对非凸簇有效；复杂度受特征分解限制，可用Nyström/稀疏近似加速。
• Mean Shift：
  • KDE:$\hat{p}(x)=\frac{1}{nh^d}\sum_iK!\left(\frac{x-x_i}{h}\right)$
  • 梯度与Mean-Shift向量：$m(x)=\frac{\sum_ix_i,g(||x-x_i||^2)}{\sum_i g(||x-x_i||^2)}-x$（$g$由核$K$导出）
  • 迭代$x\leftarrow x+m(x)$收敛到模式。
• DBSCAN/HDBSCAN：
  • $N_\varepsilon(x)={y|dist(x,y)\le\varepsilon}$，核心点$|N_\varepsilon(x)|\ge$minPts
  • 密度可达、密度相连定义簇；复杂度$O(n\log n)$（借助索引）。
  • HDBSCAN使用互达距离构造MST，凝缩层次后以稳定性选择簇，更鲁棒于可变密度。

六、模型选择与评估

• 内部指标（无需真值）：
  • 轮廓系数（Silhouette）$s\in[-1,1]$，越大越好。
  • Davies–Bouldin（越小越好）、Calinski–Harabasz（越大越好）、Dunn指数。
  • Gap Statistic：比较观测聚类内离差与参照分布。
• 外部指标（有真值）：
  • ARI（调整兰德指数）、NMI（归一化互信息）、Fowlkes–Mallows。
• 模型选择：
  • k-means肘部法、轮廓系数最优、Gap。
  • GMM用AIC/BIC或Bayes因子；DP-GMM自动推断簇数。
  • 谱聚类可用特征值“eigengap”启发选择$K$。
• 不确定性与稳定性：
  • GMM给软分配与方差；Bootstrap重抽样评估聚类稳定性。
  • 多次随机初始化取最优或共识聚类。

七、适用场景与工程经验

• 数据预处理：
  • 标准化/归一化（尤其对欧式距离）；嵌入向量常进行L2归一化后用余弦或球面k-means。
  • 降维（PCA保结构、UMAP保邻域、t-SNE仅可视化不适合直接聚类）。
  • 异常点处理：稳健尺度、截尾、使用k-medoids/HDBSCAN。
  • 类别特征：k-prototypes或Gower距离。
• 算法选型：
  • 球状簇、速度优先：k-means/MiniBatchKMeans。
  • 椭球簇/软分配：GMM。
  • 任意形状/含噪声：DBSCAN/HDBSCAN。
  • 非凸多流形：谱聚类（配稀疏近邻图）。
  • 高维文本/嵌入：球面k-means、vMF混合、余弦度量。
  • 簇数未知：HDBSCAN、DP-GMM。
• 大规模：
  • 近似NN构图（HNSW）加速DBSCAN/谱聚类。
  • MiniBatchKMeans、coreset、Nyström近似。
  • GPU：RAPIDS cuML、FAISS加速相似度搜索。
• 初始化与稳健性：
  • k-means++显著提升收敛与质量。
  • 多次重启、选择最小WSS/最大Silhouette。
• 嵌入质量至关重要：
  • 使用自监督/对比学习预训练表征，再聚类（DeepCluster、SCAN思路）。
  • 嵌入去均值与白化可减少各向异性。

八、最新进展与趋势

• 深度聚类与自监督融合：
  • DEC/IDEC通过自编码器重构+聚类目标联合优化，提升结构性。
  • DeepCluster/SCAN将“聚类-伪标签-表征更新”闭环，迭代提升。
  • 对比学习+聚类约束（SwAV、DINO）在图像表征上表现突出。
• 图与谱的可扩展性：
  • Nyström/随机特征、近似拉普拉斯求解、图稀疏化提升百万级规模可行性。
• 最优传输与可微聚类：
  • Sinkhorn-KMeans、Wasserstein K-means引入OT正则的平衡/几何约束；端到端可微，融入深度网络。
• 可变密度与层次结构：
  • HDBSCAN在工业上广泛采用；与UMAP结合实现“低维邻域保持+密度聚类”的鲁棒流程。
• 大模型嵌入：
  • 语言/多模态嵌入的聚类需考虑高维各向异性与余弦度量；常结合球面k-means、vMF混合、中心化+白化的预处理。
• 流式与在线：
  • Streaming k-means、DP混合的在线变分推断适应数据流。

九、代码示例：从玩具数据到工程管线

以下示例基于Python生态（scikit-learn、hdbscan、umap-learn）。请根据需要安装依赖。

数据与通用预处理（标准化+PCA降维）：

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

import numpy as np
from sklearn.datasets import make_blobs, make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA

X1, y1 = make_blobs(n_samples=2000, centers=4, cluster_std=[1.0, 2.0, 0.8, 1.5], random_state=42)
X2, y2 = make_moons(n_samples=2000, noise=0.06, random_state=42)

def preprocess(X, n_components=20):
    X = StandardScaler().fit_transform(X)
    if X.shape[1] > n_components:
        X = PCA(n_components=n_components, random_state=42).fit_transform(X)
    return X

Xb = preprocess(X1)
Xm = preprocess(X2)

k-means与评估：

1
2
3
4
5
6

from sklearn.cluster import KMeans, MiniBatchKMeans
from sklearn.metrics import silhouette_score

kmeans = KMeans(n_clusters=4, init='k-means++', n_init='auto', random_state=42).fit(Xb)
labels_km = kmeans.labels_
print("k-means silhouette:", silhouette_score(Xb, labels_km))

GMM（软分配，含簇数选择）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from sklearn.mixture import GaussianMixture
import numpy as np

bics = []
models = []
for k in range(2, 10):
    gmm = GaussianMixture(n_components=k, covariance_type='full', random_state=42).fit(Xb)
    bics.append(gmm.bic(Xb))
    models.append(gmm)
best = models[int(np.argmin(bics))]
labels_gmm = best.predict(Xb)
print("GMM best K by BIC:", best.n_components)

DBSCAN/HDBSCAN（适用于任意形状簇与噪声）：

1
2
3
4
5

from sklearn.cluster import DBSCAN

db = DBSCAN(eps=0.3, min_samples=10, metric='euclidean', n_jobs=-1).fit(Xm)
labels_db = db.labels_  # -1为噪声
print("DBSCAN clusters:", len(set(labels_db)) - (1 if -1 in labels_db else 0))

HDBSCAN与UMAP（稳健管线）：

1
2
3
4
5
6
7

import umap.umap_ as umap
import hdbscan

umap2d = umap.UMAP(n_neighbors=30, min_dist=0.1, n_components=10, random_state=42).fit_transform(Xm)
hdb = hdbscan.HDBSCAN(min_cluster_size=30, min_samples=10, metric='euclidean').fit(umap2d)
labels_hdb = hdb.labels_
print("HDBSCAN clusters:", len(set(labels_hdb)) - (1 if -1 in labels_hdb else 0))

谱聚类（非凸结构）：

1
2
3
4
5

from sklearn.cluster import SpectralClustering

sc = SpectralClustering(n_clusters=2, affinity='nearest_neighbors', n_neighbors=15, random_state=42, n_jobs=-1)
labels_sc = sc.fit_predict(Xm)
print("Spectral silhouette:", silhouette_score(Xm, labels_sc))

球面k-means建议：对嵌入做L2归一化，然后用k-means近似余弦聚类：

1
2
3

from sklearn.preprocessing import normalize
Xe = normalize(Xb)  # 近似在单位球面上聚类
labels_skm = KMeans(n_clusters=4, init='k-means++', n_init='auto', random_state=42).fit_predict(Xe)

大规模加速：

• 使用MiniBatchKMeans替代标准k-means。
• 构图/近邻查询用FAISS/HNSW；GPU上可用RAPIDS cuML。

十、常见坑与排障

• 簇不分明/指标差：检查尺度、降维方式、距离度量；考虑换成余弦或马氏；改用非线性方法（谱/HDBSCAN）。
• k-means初始化导致局部最优：使用k-means++、增大n_init、多次重启取最优。
• DBSCAN参数敏感：用k距离图（第k近邻距离排序）寻找“肘点”选$\varepsilon$；密度差异大改用HDBSCAN。
• t-SNE后聚类不稳定：t-SNE只保局部可视化，聚类建议用PCA/UMAP或在原空间/表征空间进行。
• 高维嵌入聚类失败：先中心化/白化，L2归一化，改用球面k-means或vMF混合。
• 类别/数值混合：选择Gower距离或k-prototypes，避免强行用欧式。

十一、更多延展：理论与实践要点

• 无免费午餐：不同聚类目标彼此不兼容，择法依赖任务归纳偏置与数据几何。
• 一致性与可识别性：在分离度充分条件下，k-means/GMM可一致；谱聚类在随机块模型下有一致性保证。
• 不确定性表达：偏好软分配（GMM、DP混合），对边界点给出置信度，有助于下游人机协作标注。
• 约束聚类与业务知识：加入Must-link/Cannot-link、小量标签或对比约束，常能显著提升质量。

十二、推荐学习资源

• 经典与综述
  • A tutorial on Spectral Clustering（von Luxburg, 2007）[https://arxiv.org/abs/0711.0189]
  • Data Clustering: 50 Years Beyond K-means（Jain, 2010）[https://ieeexplore.ieee.org/document/5289496]
  • Bregman Hard Clustering（Banerjee et al., 2005）[https://jmlr.org/papers/v6/banerjee05a.html]
  • k-means++（Arthur & Vassilvitskii, 2007）[https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf]
• 代表方法论文
  • DBSCAN（Ester et al., 1996）[https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf]
  • HDBSCAN（McInnes et al., 2017）[https://arxiv.org/abs/1705.07321]
  • Kernel k-means（Dhillon et al., 2004）[https://www.cs.cmu.edu/~aarti/Class/10701/readings/kernel-k-means.pdf]
  • Gap Statistic（Tibshirani et al., 2001）[https://statweb.stanford.edu/~gwalther/gap]
  • Dirichlet过程与非参数（Teh, 2010）[https://www.stats.ox.ac.uk/~teh/research/npbayes/Teh2010a.pdf]
  • DEC（Xie et al., 2016）[https://arxiv.org/abs/1511.06335]
  • DeepCluster（Caron et al., 2018）[https://arxiv.org/abs/1807.05520]
  • SCAN（Van Gansbeke et al., 2020）[https://arxiv.org/abs/2005.12320]
  • HNSW近似近邻（Malkov & Yashunin, 2018）[https://arxiv.org/abs/1603.09320]
• 书籍
  • The Elements of Statistical Learning（Hastie/Tibshirani/Friedman）[https://hastie.su.domains/ElemStatLearn/]
  • Pattern Recognition and Machine Learning（Bishop）[http://research.microsoft.com/en-us/um/people/cmbishop/PRML/]
• 工具与库
  • scikit-learn [https://scikit-learn.org/stable/]
  • hdbscan [https://hdbscan.readthedocs.io]
  • umap-learn [https://umap-learn.readthedocs.io]
  • FAISS [https://github.com/facebookresearch/faiss]
  • RAPIDS cuML [https://rapids.ai]

结语

聚类的成败，三分靠算法，七分靠表示与度量。理解各算法的几何假设与优化目标、结合合理的预处理和评估策略，往往比盲目调参更重要。在当下的表示学习浪潮中，“好表征+合适度量+简单聚类”常优于“差表征+复杂聚类”。希望本文的全景梳理能帮助你在实际项目中做出明智选择，并为进一步的研究和工程实践提供坚实起点。