DBSCAN 的原理是什么？如何用伪代码描述其聚类过程？｜蚂蚁集团数据分析面经解析

60 秒回答模板

DBSCAN 是基于密度的聚类算法。它先定义两个参数：eps 表示邻域半径，minPts 表示一个点成为核心点所需的邻域最少点数。若某点 eps 邻域内点数达到 minPts，它是核心点；不满足核心点条件但落在某个核心点邻域内的是边界点；既不是核心点也不属于任何核心点邻域的是噪声点。算法从未访问点开始，如果该点不是核心点，先标为噪声；如果是核心点，就新建一个簇，把它 eps 邻域内的点加入队列，遇到新的核心点继续把其邻域并入，直到没有可扩展点。最终所有密度相连的点形成同一个簇。回答时还要补充：DBSCAN 不需要指定 K，适合非球形簇和异常点识别；但 eps、minPts 很关键，不同密度簇和高维数据会让效果变差，实际使用前要做标准化、距离度量选择和参数验证。

考点 密度定义

难度 真实面经题

回答目标 让候选人能用密度、核心点、密度可达和簇扩展完整解释 DBSCAN，并能写出可执行的伪代码，同时说明参数选择、复杂度、优缺点和评估方式。

深入解析

密度聚类直觉

DBSCAN 不假设簇是圆形或高斯分布，而是假设同一个簇内部点足够密集，簇与簇之间由低密度区域隔开。它通过局部邻域密度来决定哪些点可以连成一片，而不是像 K-means 那样围绕中心点迭代。

两个核心参数

eps 控制邻域半径，minPts 控制达到多大密度才算核心区域。eps 太小会把真实簇切碎，噪声点变多；eps 太大会把相邻簇连在一起。minPts 太小容易把噪声连成簇，太大则会漏掉稀疏但真实的簇。

三类点要分清

核心点是 eps 邻域内至少有 minPts 个点的点；边界点不是核心点，但位于某个核心点的 eps 邻域内；噪声点既不是核心点，也不能从任何核心点密度到达。很多实现中 minPts 统计包含点自身，面试时要说明采用的约定。

聚类过程是扩展核心点

算法遍历所有点，遇到未访问核心点就创建新簇，然后把它邻域内的点放入待扩展集合。若集合中的点也是核心点，就继续把它的邻域加入集合；若只是边界点，则归入当前簇但不继续扩展。这个过程本质上是对密度可达关系做 BFS 或 DFS。

噪声不是永远固定

某个点早期被访问时可能因为自身不是核心点而暂时标为噪声，但后续如果它落入某个核心点扩展出的簇中，可以被改标为边界点并加入簇。因此伪代码里要允许 NOISE 点被重新分配。

参数和预处理决定效果

DBSCAN 依赖距离度量，特征尺度不一致会严重影响 eps 邻域，所以通常要标准化或归一化。eps 可以用 k-distance 曲线辅助选择，minPts 常根据维度、样本量和抗噪要求调整。业务数据还要考虑类别变量编码、异常值和距离是否符合业务语义。

复杂度和适用边界

朴素实现每个点都要查全量邻域，复杂度可到 O(n²)。低维空间可用 KD-Tree、Ball Tree、网格索引或数据库空间索引加速。高维数据中距离会变得不稳定，邻域区分度下降，DBSCAN 往往需要降维、换距离度量或改用 HDBSCAN、谱聚类等方法。

评估不能只看簇数

DBSCAN 会输出簇和噪声点，评估时要看簇内紧密度、簇间分离度、噪声比例、参数稳定性和业务可解释性。如果有标签，可看 ARI、NMI、purity 等外部指标；无标签时可以结合 silhouette、Davies-Bouldin、DBCV 或人工抽样核验，但要注意 silhouette 对非凸簇不一定公平。

pseudocode

DBSCAN 聚类伪代码

DBSCAN(D, eps, minPts):
  clusterId = 0

  for each point p in D:
    if p.visited:
      continue

    p.visited = true
    neighbors = regionQuery(D, p, eps)

    if size(neighbors) < minPts:
      p.label = NOISE
    else:
      clusterId = clusterId + 1
      expandCluster(p, neighbors, clusterId, eps, minPts)

expandCluster(p, neighbors, clusterId, eps, minPts):
  p.label = clusterId
  queue = deduplicate(neighbors)

  while queue is not empty:
    q = pop(queue)

    if not q.visited:
      q.visited = true
      qNeighbors = regionQuery(D, q, eps)

      if size(qNeighbors) >= minPts:
        queue = deduplicate(queue union qNeighbors)

    if q.label is UNASSIGNED or q.label is NOISE:
      q.label = clusterId

regionQuery(D, p, eps):
  return all points x in D where distance(p, x) <= eps

这份伪代码默认 minPts 统计包含点自身；如果实现不包含自身，要在阈值解释中保持一致。
NOISE 是可被后续核心点扩展重新吸收的临时标签，不应写成不可修改的终态。
队列合并邻域时要去重，否则实现上可能重复入队并增加无效计算。

易错点

把 DBSCAN 说成需要指定 K 的中心点聚类，混淆了它和 K-means。
只背核心点、边界点、噪声点定义，没有讲清从核心点扩展簇的过程。
忘记边界点不继续扩展，只有核心点会把邻域继续并入队列。
不说明特征标准化和距离度量，直接在原始多量纲特征上使用 eps。
认为噪声点一旦标记就不能再加入任何簇，忽略后续可被核心点吸收。
只说优点，不提参数敏感、不同密度簇和高维距离失效问题。

面试官追问

DBSCAN 和 K-means 最大区别是什么？

K-means 需要预先指定 K，偏好球形、方差相近的簇，并且对离群点敏感；DBSCAN 不需要指定簇数，按密度扩展，可发现非凸形状簇并识别噪声，但参数和密度变化会影响很大。

eps 和 minPts 怎么选？

通常先标准化特征，再用 k-distance 曲线观察拐点选择 eps；minPts 可从维度和抗噪需求出发设置，维度越高或希望越稳健，minPts 往往要更大。最终还要看噪声比例、簇稳定性和业务解释。

边界点如果同时落在两个核心点邻域里怎么办？

标准 DBSCAN 中边界点可能被先扩展到它的簇吸收，结果与遍历顺序有关；核心点之间若密度可达会合并为同一簇。工程上可记录距离或后处理，但要说明规则。

为什么 DBSCAN 不适合密度差异很大的数据？

因为全局只有一组 eps 和 minPts。高密度簇需要小 eps，低密度簇需要大 eps，两者难以同时满足。密度差异明显时可考虑 HDBSCAN、OPTICS 或分层/分场景聚类。

DBSCAN 的时间复杂度如何优化？

朴素 regionQuery 是 O(n)，对每个点做一次会到 O(n²)。低维数据可用 KD-Tree、Ball Tree、R-tree、网格索引等加速邻域查询，但高维下索引效果会下降。