提到聚类，大多数人第一个想到的是 K-Means。但 K-Means 有两个绕不开的硬伤：必须先指定分几类（k），而且只擅长"圆球形、大小相近"的簇。遇到环形、长条形的簇，或者数据里混着离群点，它就力不从心了。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）换了个思路——按密度聚类：哪里点挨得密，哪里就是一个簇；稀疏的孤立点，直接判为噪声。它不需要预先指定簇数，还能识别任意形状的簇。这篇文章把 eps、minPts、三类点的定义、BFS 扩展过程和 C++ 实现一次讲透。（个人主页：https://wobuhuang.com）

一、它解决什么问题

给定一堆二维点，自动把"挨得密"的点聚成一簇，并把孤立的离群点识别为噪声——事先不用告诉它分几类。这就是无监督密度聚类要干的活：既不需要标签，也不需要你猜 k。

二、核心思想：eps 与 minPts

整套算法只靠两个参数：

• eps（邻域半径）：以某点为圆心、半径 eps 画个圆，圆内的点就是它的"邻居"。
• minPts（最少点数）：邻居数量 ≥ minPts，这个点就够"密"，称为核心点。
  

三、三类点：核心点、边界点、噪声点

由 eps 和 minPts，把所有点分成三类：

1. 核心点：eps 邻域里点数 ≥ minPts。它能"带头"组建一个簇。
2. 边界点：自己不是核心点，但落在某个核心点的邻域里，于是被拉进那个簇。
3. 噪声点：既不是核心点，也不在任何核心点邻域内——孤立的离群点，可视化里始终保持灰色。

可视化用的数据是 28 个点：3 个密集簇 + 4 个离群噪声点，外加几个"靠簇但本身不够核心"的边界点，eps=42、minPts=3，过程清晰可复现。

四、扩展过程（BFS 滚雪球）

DBSCAN 的扩展本质是一个 BFS：

for 每个未访问的点 p:
  标记 p 已访问
  N = p 的 eps 邻域
  if |N| < minPts:
     p = 噪声（暂定，之后可能被拉成边界点）
  else:
     新建一个簇，把 p 设为核心点
     把 N 里的点排队，BFS 向外扩展：
       队列里每个点 o 加入本簇；
       若 o 也是核心点，把 o 的邻域也排进队，继续扩张

对应动画里发生的事：一开始所有点都是灰色；扫到一个核心点，它和邻域里的点一起被染上同一种颜色，一个新簇诞生；然后从邻域里的核心点继续向外扩张，颜色像滚雪球一样蔓延到密集区边缘；扩张停在密度不足的地方，边界点被染色但不再向外带人；那些孤立的灰点始终没被碰到，最后就是噪声。

五、C++ 参考实现

void dbscan(vector<Point>& pts, double eps, int minPts) {
  int cid = 0;                                  // 当前簇编号
  for (auto& p : pts) {                         // 遍历每个点
    if (p.visited) continue;                    // 访问过就跳过
    p.visited = true;
    auto nb = neighbors(pts, p, eps);           // eps 邻域内的点
    if (nb.size() < minPts) { p.cls = NOISE; continue; } // 不够核心 → 噪声
    p.cls = ++cid;                              // 成核心点，新建簇
    queue<Point*> q(nb);                        // 邻域入队，准备扩展
    while (!q.empty()) {                        // BFS 向外扩张
      Point* o = q.front(); q.pop();
      if (o->cls == NOISE) o->cls = cid;        // 噪声其实是边界点
      if (o->visited) continue;
      o->visited = true; o->cls = cid;
      auto nb2 = neighbors(pts, *o, eps);
      if (nb2.size() >= minPts) push_all(q, nb2); // o 也是核心 → 继续扩展
    }
  }
}

六、复杂度

朴素实现每个点都要扫一遍找邻域，是 O(n²)；用 KD-Tree / R-Tree / 网格索引加速邻域查询，可降到约 O(n·log n)。空间 O(n)。

七、必须知道的坑

• 参数敏感：eps 太大，相邻的簇会被连成一团；太小，又会把好多点误判成噪声。
• 密度不均：数据里既有稠密又有稀疏的簇时，一组 (eps, minPts) 很难同时照顾，可考虑 OPTICS / HDBSCAN。
• 高维失效：维度一高，点之间距离趋于接近（维度灾难），eps 难选。
• 要归一化：不同特征量纲差太大时，距离会被大尺度特征主导，先做标准化。
• 边界点归属可能依赖访问顺序（先被哪个核心点碰到）。

八、小结

DBSCAN = eps 邻域 + minPts 阈值 + 核心点带头 + BFS 滚雪球扩展。它不用指定簇数、能识别任意形状的簇、还能单独把噪声揪出来，是密度聚类里最经典的基线。想直观看到核心点染色、向外扩张、噪声留灰的全过程，可以在「码路星球」看这套逐行代码高亮 + 动画的可视化讲解，完全免费，做任务还能得成长币。使用方式看主页。（个人主页：https://wobuhuang.com）

DBSCAN / 密度聚类 / 机器学习 / 无监督学习 / 聚类算法 / 核心点 / 噪声点 / C++ / 算法可视化 / 码路星球