聚类算法

K-Means · Hierarchical · DBSCAN · Density-based

问题定义

聚类是一种无监督学习方法，旨在将相似的样本分组到同一个簇中，不同的样本分到不同的簇中。核心问题包括：如何度量样本间的相似度、如何确定簇的数量、如何处理不同形状和密度的簇、如何评估聚类效果。

核心算法

基于距离的聚类

K-Means 算法

通过迭代优化簇中心，最小化簇内样本到中心的距离平方和。适合球形簇，计算效率高，但需要预先指定簇数 K。

优化目标：min Σ_{i=1到K} Σ_{x∈C_i} ||x - μ_i||²
步骤：
1. 初始化 K 个簇中心
2. 分配每个样本到最近的簇中心
3. 更新簇中心为簇内样本均值
4. 重复步骤 2-3 直到收敛

K-Means++

K-Means 的改进版本，通过智能初始化簇中心，减少对初始值的敏感性，提高聚类质量。

层次聚类

凝聚式层次聚类

自底向上构建聚类树，初始每个样本为一个簇，逐步合并最相似的簇，直到形成一个簇。

分裂式层次聚类

自顶向下构建聚类树，初始所有样本为一个簇，逐步分裂最不相似的簇，直到每个样本为一个簇。

距离度量

单链接（最小距离）、全链接（最大距离）、平均链接（平均距离）、沃德链接（平方误差和）。

基于密度的聚类

DBSCAN 算法

基于密度的空间聚类，能够识别任意形状的簇，同时检测噪声点。核心参数包括 eps（邻域半径）和 min_samples（最小样本数）。

OPTICS 算法

DBSCAN 的扩展，通过排序点来反映数据的密度可达性，能够处理不同密度的簇。

基于模型的聚类

GMM（高斯混合模型）

假设数据由多个高斯分布混合生成，通过 EM 算法估计模型参数，支持软聚类。

谱聚类

基于图论的聚类方法，通过构建相似度图，对拉普拉斯矩阵进行特征分解，然后在低维空间中聚类。

开源实现

scikit-learn Clustering

提供 KMeans、HierarchicalClustering、DBSCAN、OPTICS、GaussianMixture、SpectralClustering 等实现。

HDBSCAN

基于密度的层次聚类算法，是 DBSCAN 的改进版本，能够自动确定簇数。

FAISS

Facebook 开发的高效相似性搜索库，支持大规模聚类和最近邻搜索。

UMAP

统一流形近似和投影，结合降维和聚类，适合高维数据可视化。

应用场景

评估指标

内部评估指标

轮廓系数（Silhouette Coefficient）、Calinski-Harabasz 指数、Davies-Bouldin 指数，无需真实标签。

外部评估指标

互信息（MI）、调整兰德指数（ARI）、Fowlkes-Mallows 指数，需要真实标签。

参数调优

K-Means

通过肘部法则、轮廓系数、Gap 统计量等方法选择最优 K 值。

DBSCAN

通过 K-距离图选择 eps 值，根据领域知识设置 min_samples。

层次聚类

通过树状图（Dendrogram）确定最佳聚类数，选择合适的链接方法。

参考文献