DBSCAN：密度聚类算法

可视化演示

动态演示DBSCAN的核心机制，通过源头/管道/节点/终端四种模式展示关键概念与交互流程。

密度聚类思想

假设你是派对的场务，散场后要把宾客按“朋友圈”分组报销打车费。你手中没有名单，只看得到每人此刻站在哪儿——吧台边围着一大团人，沙发那边拖着一条蜿蜒的人链，窗边还站着两个独自发呆的家伙。你很快发现：想分圈，“谁站在谁旁边、旁边围了多少人”才是最可靠的信息，这就是“密度”。

传统的 K-Means 走的是另一条路：它先随手画几个“圆心”，再让每个人投奔最近的圆心。可圆心模型天然假设簇是圆形的，而真实世界里的“朋友圈”什么形状都有。DBSCAN 换了个工具——它给每个点画一个半径固定的小圆圈（邻域），数一数圆圈里盛了多少人，用局部密度来刻画热闹程度。

正式定义：设数据集为 $D$，对任意点 $p$，它的 $\epsilon$ 邻域是半径 $\epsilon$ 范围内所有点的集合。邻域内点数越多，说明该点越“热闹”；热闹的区域连成片就是簇，冷清的区域自然成为簇与簇之间的隔离带。整个过程不需要任何标签，也不需要预设分成几组——这正是“无监督聚类”的含义。

拿着这个半径固定的“社交圈”在会场走一圈，你根本不用知道派对上有几拨人——人挤人的地方自然连成片，冷清角落自动变成分界线。密度聚类思想的全部起点，就是这么朴素。

三种点类型

有了“社交圈”，宾客立刻分成三种。想象派对上：Tina 身边围了七八个朋友，她是“社交达人”；小明虽然自己只认识两个人，但正站在 Tina 旁边，属于圈子边缘的“安静成员”；角落里的 Bob 谁都不认识，也没人靠近他，是“独行侠”。这三类人对应到 DBSCAN，就是核心点、边界点、噪声点。

判定只靠两件事：这个点周围够不够“热闹”（邻居数是否达到 MinPts），以及它身边有没有核心点。核心点靠自己的“人气”撑起一个簇；边界点虽然人气不足，但沾了核心点的光，也算圈子的一员；噪声点既没人气、又远离所有达人，被排除在一切簇之外。

核心点的判定条件如下：当邻域内点数不小于 MinPts 时，点 $p$ 就是核心点。边界点指邻域内点数不足 MinPts、但落在某个核心点邻域内的点；两者都不是的，就是噪声点。

散场后清点宾客时，正是三类人各司其职：达人负责拉人扩圈，安静成员让圈子连成片、撑满任意形状，独行侠则被自动请出所有圈子。人群划分完成的同时，噪声也顺带被隔离出来了。

eps邻域参数

$\epsilon$ 就是“社交半径”——你愿意走几步去和陌生面孔打招呼。半径太小，连身边的人都够不着，满场都是被孤立的“独行侠”；半径太大，整个会场的人都算熟人，所有圈子糊成一团，谁也分不清谁。这个参数直接决定邻域里的人数，也就决定了哪些点能当核心点，是 DBSCAN 最关键的旋钮。

$\epsilon$ 怎么选才靠谱？业内常用“k-距离图”。做法是：对每个点，算出它到第 $k$ 个最近邻居的距离（$k$ 通常就取 MinPts），然后把这些距离从小到大排序，画成一条曲线。曲线像一只手臂：前半段平缓，说明大多数点周围密度高、邻居很近；到了某个点之后距离开始暴涨，说明进入了稀疏区——那个拐弯处，就是理想的 $\epsilon$。

如同派对前先估算会场密度：多数人 3 米内都有熟人，独行侠 10 米内都碰不到人——把手肘处的 3 米作为“社交半径”，既不漏掉圈子，又不把全场拉成一家。

MinPts阈值

MinPts 是“达人门槛”：一个人周围至少要凑够几个人，才配当核心点？门槛设高了，只有极少数超级人气王能牵头，圈子容易碎掉；门槛设低了，谁都能拉人，噪声也会被裹挟进圈里，聚类失去意义。它和 $\epsilon$ 一起，共同定义了什么叫“密度高”。

直观地，密度就是“单位面积里站了多少人”。把 $\epsilon$ 邻域看成一块圆形区域，密度就等于邻域人数除以圆面积。固定 $\epsilon$ 时，邻域人数越多密度越大，所以“邻域人数 ≥ MinPts”和“密度 ≥ 阈值”本质上是同一件事。

经验法则上，MinPts 通常取特征维度的两倍以上：二维数据至少取 4，高维数据相应增大。相比 $\epsilon$，MinPts 的敏感度更低，一般先定 MinPts，再通过 k-距离图去选 $\epsilon$，调参会顺手很多。

开派对时你也得规定“认识几个人以上算社交达人”：定得太苛刻，大多数圈子没人牵头；定得太宽松，边缘散客也被拉进来充数。合适的门槛配上合适的半径，派对分圈才既完整又不掺水。

密度可达与相连

核心点和参数都齐了，圈子怎么从一个人“长”成一圈人？靠的是介绍。Alice 认识 Bob，Bob 认识 Carol——即使 Alice 和 Carol 离得很远，只要中间有一串人引荐，她们也能进同一个圈子。DBSCAN 管这叫“密度可达”：若点 $q$ 在核心点 $p$ 的邻域内，称 $q$ 由 $p$“直接密度可达”；沿着一串核心点依次传递，就成了“密度可达”。

这条传递链可以很长，这正是 DBSCAN 能聚出任意形状的秘密：规则是局部的，连通却是全局的。两个边界点各自人气不足，但都能从同一个核心点出发被“密度可达”，于是它们之间是“密度相连”的，也会被收进同一个簇。最终，一个簇就是从某个核心点出发、把所有密度可达与密度相连的点收拢起来的最大集合。

派对圈子的形成正是这样：达人给身边人介绍，身边的人再给他们的身边人介绍……圈子像涟漪一样沿着人链蔓延，沙发上的长条队伍就是这么连起来的。人群围成的形状再奇怪，只要人链不断，就是一个圈。

K-Means对比

假如让 K-Means 来给这场派对分组，它会怎么做？先随手画 $k$ 个圈，把宾客按“离哪个圈心近”分配，然后不断挪动圈心直到安稳。问题在于：派对上的圈子是沿着吧台弯弯曲曲的，K-Means 画一个圆根本罩不住整条人链。

它的目标函数只关心“点到所属中心的距离平方和”，完全不看密度。因此无论数据长什么样，K-Means 分出来的簇总是近似球形的。环形的朋友群、半月形的沙发组，在它眼里都会被拦腰砍成两半。更麻烦的是噪声：Bob 站在远角落，K-Means 也会把他硬塞进某个圈子——因为它的规则是“每个人必须有归属”。而且它要求你预先告诉它 $k$ 是多少，可派对上到底有几拨人，我们事先并不知道。

相当于 K-Means 拿着圆规画圈，DBSCAN 拿着“人气探测器”顺着人链走。真实数据里没有完美的圆形部落，所以面对带噪声、形状自由的数据，DBSCAN 常常更贴近现实。

任意形状聚类

什么形状都能聚，是 DBSCAN 最惊艳的地方。环形甜甜圈、弯月形、S 形人群——只要密度均匀、人链不断，都能被完整地串成一个簇。环形数据在 K-Means 眼里会被劈成两半，在 DBSCAN 眼里却是一个货真价实的整圈。

原理就藏在簇的定义里：一个簇是所有“密度相连”点的极大集合。两个点哪怕相隔很远，只要存在一个共同的核心点作为“中转站”，让它们都能沿密度链到达，它们就算一家人。环上的每个点都能通过身边邻居绕一整圈，于是“环形”不再被分割。

环形的朋友群、沿街排开的小吃摊队形，DBSCAN 都能照单全收。但要注意：全局只有一个 $\epsilon$，如果派对里“密集夜店区”和“稀疏露台区”同时存在，一个半径很难同时顾全两边的密度尺度——这正是它最大的软肋，也是 HDBSCAN 等改进算法的出发点。

参数调优实战

像布置派对前先量场地，DBSCAN 调参也要按流程走，而不是瞎猜。第一步是特征标准化。$\epsilon$ 是绝对距离，如果特征单位不同（厘米混着千米），“社交半径”会完全失真，必须先让所有特征处于同一尺度。

第二步，画 k-距离图选 $\epsilon$：令 $k=$ MinPts，对每个点算出第 $k$ 近邻居距离并排序，取曲线肘部附近的距离作为 $\epsilon$ 初值。第三步，跑一遍 DBSCAN，用轮廓系数评估聚类质量，再小范围微调两个参数。调参时还可以结合可视化：把聚类结果画出来，盯着“该连的没连、不该连的连了”的地方对症下药。

就像调派对的灯光和音乐：先量场地（标准化），再定社交半径（k-距离图），最后看看各圈气氛（轮廓系数）。参数没有万能值，但有了流程和评估指标，你总能找到顺手的组合。

AI 应用场景

Python 演示

import math  class DBSCAN:    def __init__(self, eps=0.12, min_pts=4):        self.eps = eps        self.min_pts = min_pts     def fit(self, X):        n = len(X)        labels = [-1] * n        neighbors = []        for i in range(n):            nb = []            for j in range(n):                if i != j and self._dist(X[i], X[j]) <= self.eps:                    nb.append(j)            neighbors.append(nb)         cluster_id = 0        for i in range(n):            if labels[i] != -1 or len(neighbors[i]) < self.min_pts:                continue            labels[i] = cluster_id            queue = [i]            while queue:                p = queue.pop(0)                if len(neighbors[p]) < self.min_pts:                    continue                for q in neighbors[p]:                    if labels[q] == -1:                        labels[q] = cluster_id                        queue.append(q)            cluster_id += 1        return labels     def _dist(self, a, b):        return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))  def make_data():    pts = []    for i in range(40):        a = i / 40 * 2 * math.pi        pts.append([0.38 + 0.2 * math.cos(a), 0.5 + 0.2 * math.sin(a)])    for i in range(24):        pts.append([0.76 + (i % 6) * 0.05, 0.5 + (i // 6) * 0.06])    for pos in [(0.05, 0.05), (0.95, 0.95), (0.05, 0.93),                (0.95, 0.06), (0.5, 0.02), (0.03, 0.5)]:        pts.append(list(pos))    return pts  def main():    X = make_data()    model = DBSCAN(eps=0.12, min_pts=4)    labels = model.fit(X)    sizes = {}    for lab in labels:        sizes[lab] = sizes.get(lab, 0) + 1    noise = sizes.pop(-1, 0)    print("cluster count:", len(sizes))    for lab, s in sorted(sizes.items()):        print("cluster", lab, "size:", s)    print("noise size:", noise)    print("ring cluster found as one:", len(set(labels[:40])) == 1)  if __name__ == "__main__":    main()

1. if i != j and self._dist(X[i], X[j]) <= self.eps:两两计算距离，把半径 eps 内的邻居记入 nb——相当于“数清每个人社交圈里有谁”。
2. neighbors.append(nb)预计算所有点的邻居表，后续 BFS 扩圈时不用重复算距离。
3. if labels[i] != -1 or len(neighbors[i]) < self.min_pts: continue已入簇或邻居数不够 MinPts 的点不配当“社交达人”，直接跳过。
4. labels[i] = cluster_id给达人的核心点盖章，一个新圈子正式成立。
5. if len(neighbors[p]) < self.min_pts: continue边界点已入圈但不再介绍朋友，防止圈子无边界蔓延。
6. if labels[q] == -1: labels[q] = cluster_id把达人的邻居拉进圈子，并加入待办队列等待继续扩圈。
7. print("ring cluster found as one:", len(set(labels[:40])) == 1)检查环形上 40 个点是否被连成同一个簇，验证任意形状聚类能力。

常见误区

面试题