DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法，能够发现任意形状的簇，并将低密度区域的孤立点识别为噪声，无需预先指定簇的数量。它由慕尼黑大学团队于 1996 年提出，并凭借对含噪声空间数据的卓越处理能力，于 2014 年荣获 KDD 时间检验奖。

DBSCAN 用两个参数 ε（邻域半径）和 MinPts（最小样本数）定义密度，将所有点分为三类：

• 核心点（Core Point）：ε 邻域内至少含 MinPts 个点，是簇的骨干
• 边界点（Border Point）：自身邻域不满足密度要求，但落在某核心点的 ε 邻域内
• 噪声点（Noise Point）：既非核心点也非边界点，被视为离群值（scikit-learn 中标签为 -1）
• 密度可达（density-reachable）：从核心点出发，沿核心点链可到达的点属于同一个簇
• 簇的形成过程是「种子核心点→扩展邻域→合并连通区域」的递归迭代

算法只需一次数据集扫描即可完成聚类，步骤简洁：

• 遍历未访问点，计算 ε 邻域内的邻居数量
• 若邻居数 ≥ MinPts，则标记为核心点并以此创建新簇
• 递归地将所有密度可达点加入当前簇（包括新发现的核心点的邻域）
• 无法归入任何簇的点标记为噪声
• 使用空间索引（如 k-d 树 或 Ball Tree）时，时间复杂度为 O(n log n)；不使用索引时退化为 O(n²)

相较于 K-Means 等基于形心的算法，DBSCAN 具有多项独特优势：

• 无需预设簇数：算法自动确定簇的数量，适合探索性分析
• 任意形状簇：可发现月牙形、螺旋形等非凸簇，K-Means 对此无能为力
• 内置噪声识别：直接输出离群点标签，无需后处理
• 对初始化不敏感：结果具有确定性，不依赖随机初始值
• 适用于地理信息系统（GIS）、异常检测、图像分割等场景

DBSCAN 存在若干已知缺陷，使用时需注意：

• 不同密度的簇：单一全局 ε/MinPts 参数难以同时适配密度差异大的多簇数据
• 维度灾难：维度升高时距离失去区分度，ε 邻域几乎覆盖所有点或接近为空，聚类效果急剧下降
• 参数敏感性：ε 与 MinPts 的选取对结果影响显著，通常需借助 k-distance 图（肘部法）辅助调参
• 内存与索引开销：大规模高维数据中空间索引失效，时间复杂度回升至 O(n²)

合理设置 ε 和 MinPts 是使用 DBSCAN 的关键：

• MinPts 选取：通常建议 MinPts ≥ 数据维度 + 1，低维数据常取 4
• ε 选取：绘制所有点到其第 k 近邻（k = MinPts）的距离排序曲线，取「肘部」对应距离值
• 标准化：不同量纲的特征应先归一化，否则 ε 的含义因特征尺度而异
• sklearn 接口：sklearn.cluster.DBSCAN 支持 algorithm 参数切换 ball_tree / kd_tree 以加速邻域查询
• 高维数据建议先用 UMAP 或 PCA 降维，再运行 DBSCAN

DBSCAN 诞生后催生了一系列密度聚类方法的演进：

• 1996：Martin Ester、Hans-Peter Kriegel、Jörg Sander、Xiaowei Xu（均来自慕尼黑大学）在 KDD 大会发表原始论文
• 1999：OPTICS 算法提出，通过「可达距离」排序曲线解决多密度问题
• 2013：HDBSCAN 发表，将层次聚类与密度估计结合，可自动选取稳定簇，适合密度差异大的数据
• 2014：DBSCAN 原论文获 KDD Test of Time Award，确立其在数据挖掘领域的里程碑地位
• 2023：HDBSCAN 集成进 scikit-learn 1.3，与 UMAP 组合用于高维嵌入聚类的范式日趋主流