3. DBSCAN 算法流程详解：步骤与伪代码

好，咱们直接切入正题。DBSCAN 这个名字听起来唬人，但它的核心逻辑非常直观。说白了，它就是一个“拉帮结派”的算法——谁跟谁挨得近，谁就是一家人；离群太远的，自己一边玩去。

我刚开始接触这个算法的时候，也觉得参数选择有点玄学。但后来在项目中用它处理分子动力学模拟的构象数据，嗯，真香。它的好处是不用预先指定要分多少类，这对我们探索未知构象空间来说太重要了。

咱们先把 DBSCAN 的整个流程拆开来看，我习惯把它分成四个阶段。先上一张流程图，你心里有个谱。

DBSCAN 核心流程 1. 标记核心点 2. 扩展生成簇 密度直达 密度可达 密度相连 3. 输出聚类 噪音点（孤立样本） 不归属任何簇

3.1 核心概念回顾

在聊流程之前，有两个参数你得刻在脑子里：Eps (邻域半径) 和 MinPts (密度阈值)。这是算法的命门。

我按自己的理解给你梳理一下这三个基本角色：

  • 核心点 (Core Point)：在半径为 Eps 的圈圈里，包含的点数 ≥ MinPts。
  • 边界点 (Border Point)：在某个核心点的圈圈里，但它自己圈里的点数 < MinPts。
  • 噪音点 (Noise Point)：既不是核心点，也不在任何一个核心点的圈圈里。这就是我们常说的离群值。
我的小经验： 处理蛋白质构象时，MinPts 我一般设成 2 或 3。设太大容易把罕见但重要的过渡态当成噪音，你想想看，那得多可惜。

3.2 第一步：标记核心点

算法一开始，它会遍历你给的所有数据点。对每一个点，计算它到周围所有点的距离，然后数一数在 Eps 半径内到底有几个。

  • 如果邻居数 ≥ MinPts，好，这个点被标记为核心点。
  • 否则，暂时标记为候选边界点或噪音点。

这个过程说白了就是一次全局扫描。我刚入行时总觉得这步简单，但后来在百万级构象的数据集上跑，才发现计算距离矩阵非常耗时。所以，距离度量方式很重要。对于构象，RMSD 是最常用的。但你要知道，计算开销是 O(n²) 的，数据量大了必须上索引结构，比如 KD-tree 或 Ball tree。

3.3 第二步：基于密度扩展生成簇

这一块是算法的精髓。它定义了三个递进的关系，你感受一下：

  1. 密度直达：一个核心点 P，它的圈圈里有另一个点 Q，就说 Q 从 P 是密度直达的。注意，这关系是单向的。
  2. 密度可达：有一条由核心点连成的链，可以一头走到另一头。比如 P 到 Q 直达，Q 到 R 直达……那么 P 到 R 就是密度可达。
  3. 密度相连：如果存在一个核心点 O，使得 P 和 Q 都从 O 密度可达，那么 P 和 Q 就是密度相连的。这在处理构象合并时特别关键，两个看似不直接重叠的局域构象，可能通过中介态连在一起。

算法会随机选一个未处理的核心点开始，沿着密度可达的路径一路“生长”，把所有密度相连的点都拉进同一个簇。直到这个簇无法再扩张，才去选下一个核心点。

避坑指南： 我曾经遇到过一个情况，两个簇之间有一条极窄的“密度桥梁”，结果算法把它们合并成了一个簇。这就是 Eps 选大了的典型后果。所以选参时，一定要回头检查簇的完整性。

3.4 第三步与第四步：迭代与输出

重复第二步，直到所有核心点都被访问过。最后，那些始终没被任何簇“收留”的点，就被贴上噪音点的标签。在构象分析中，这些通常对应于热力学上不太稳定的高能瞬态构象。

输出结果很清爽：每个原始数据点都有一个簇标签。比如 -1 表示噪音，0 表示第一个簇，1 表示第二个簇，等等。

3.5 伪代码实现

光说不练假把式。这是我手写的伪代码风格，你直接照着这个思路去改写你的 Python 或者 C++ 代码，基本不会跑偏。

算法：DBSCAN(D, Eps, MinPts)
输入：数据点集 D，邻域半径 Eps，密度阈值 MinPts
输出：每个点的簇标签 label[]

1. 初始化所有点的 label = UNCLASSIFIED
2. 初始化当前簇编号 clusterId = 0

3. 对 D 中的每个点 P：
  4. 如果 label[P] != UNCLASSIFIED，则跳过
  5. 查找 P 的 Eps 邻域内的所有点 neighbors = regionQuery(P, Eps)
  6. 如果 |neighbors| < MinPts：
      7. 标记 label[P] = NOISE
  8. 否则：
      9. clusterId++
      10. 标记 label[P] = clusterId
      11. 创建一个种子集合 seeds = neighbors
      12. 对 seeds 中的每个点 Q：
        13. 如果 label[Q] == NOISE：
            14. 标记 label[Q] = clusterId
        15. 如果 label[Q] != UNCLASSIFIED，跳过
        16. 标记 label[Q] = clusterId
        17. 查找 Q 的 Eps 邻域 neighborsQ = regionQuery(Q, Eps)
        18. 如果 |neighborsQ| >= MinPts：
            19. seeds = seeds ∪ neighborsQ
        20. 结束循环

regionQuery(P, Eps):
  21. 返回所有与 P 距离小于等于 Eps 的点索引

注意第14行，我曾经漏掉这一步，结果边界点被重复标记，导致后面的簇扩张乱了套。这是一个经典的坑，填上就好了。

3.6 几个关键点你心里要有数

趁热打铁，我把容易出问题的地方列出来：

环节常见问题我的处理建议
参数初始化Eps 和 MinPts 选不好，聚类效果天差地别先做 k-dist 图找拐点，我常用这个办法
距离计算全量 O(n²) 计算在大数据集上跑不动上 KD-tree 或 Ball tree 索引
噪音点处理构象分析中噪音点往往有物理意义，不能直接丢弃建议留出来做后续分析，或者和专家讨论
边界点归属同一边界点可能被两个核心点争夺DBSCAN 的处理是分配给先到的一个

核心总结：DBSCAN 的全流程其实就两件事——找核心点和串密度链。不管数据集多大，这个骨架不变。你先把这两块写稳了，剩下的都是锦上添花。

← 上一章 📖 返回目录 下一章 →