弯曲簇与噪声点怎样同时识别？DBSCAN 的密度连通

上一篇的高斯混合模型用椭圆成分表达重叠与不确定性。但两条月牙、蜿蜒道路轨迹或环形材料裂纹并没有一个合适的“中心”；强迫几个高斯覆盖它们，往往会把同一条曲线切成多段，还会让离群点被某个成分勉强解释。

基于密度的含噪空间聚类（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）换了问题：**不寻找中心，而寻找局部足够密的点，再沿密度连通关系扩展簇。**本文只围绕 $\varepsilon$ 邻域、核心/边界/噪声三类点，以及基于队列的簇扩展展开。

01 为什么“离哪个中心近”不是唯一聚类方式？#

看两条弯曲带状数据：

中心式分割                     密度连通

   ●●●●●                          ●—●—●—●
 ●●     ●●       │              ●       ●
             ○○  │                         ○—○
          ○○   ○○│                      ○○   ○—○

直线边界切断形状                 局部邻域沿曲线接力

K 均值和 GMM 的成分都有全局中心与整体几何；DBSCAN 只要求相邻的局部区域足够密，因此簇可以弯曲。它还允许一些点不属于任何簇，标签为噪声，而不是把所有观测都强制收编。

02 ε 邻域精确定义了什么？#

给定距离 $d(\cdot,\cdot)$ 与半径 $\varepsilon>0$，点 $x_i$ 的闭邻域是：

注意邻域包含点自身。输入 $X\in\mathbb R^{N\times D}$，若使用欧氏距离，全部两两距离矩阵为 $[N,N]$；实际实现通常借助 KD 树、球树或分块近邻查询，避免永远显式保存稠密矩阵。

eps 不是簇内任意两点的最大距离。只要点与点之间能用短邻域链连接，同一个簇的两端可以相隔很远。

03 核心点、边界点与噪声点如何判定？#

给定 min_samples：

• 若 |N_\varepsilon(x_i)|\ge\text{min_samples}，$x_i$ 是核心点（Core Point）；
• 非核心点若落在某个核心点的 $\varepsilon$ 邻域内，是边界点（Border Point）；
• 既不是核心点也不邻接任何核心点，是噪声点（Noise Point）。

              ε 邻域
          ┌───────────┐
          │  ·  ●  · │       ● 核心点：邻域计数达标
          │ ·  ●  ●  │       · 邻居
          │    ○     │       ○ 边界点：自己不够密，但邻接核心点
          └───────────┘

                         × 噪声点：远离任何核心点

边界点不是“小一点的核心点”：它能加入簇，但不能继续把自己的稀疏邻居扩展进来。

04 “密度连通”为什么能形成弯曲簇？#

若 $q\in N_\varepsilon(p)$ 且 $p$ 是核心点，则称 $q$ 从 $p$ 直接密度可达（Directly Density-Reachable）。一串核心点可以把这种关系向外传递；两个点若都能由某个核心点经这样的链到达，就属于同一密度连通分量。

核心链： ●────●────●────●
          ╲              ╱
          ○              ○    两端边界点被吸收

每条边长度 ≤ ε；整条链长度可以远大于 ε

直接可达有方向：边界点可从核心点到达，但边界点本身不能向外扩展。最终同簇关系由核心点连通分量加其邻接边界点构成。

05 用七个一维点手算簇扩展#

取：

设置 $\varepsilon=0.11$、min_samples=3，距离等于绝对差：

从核心点 0.1 开始，邻域先纳入 0.0 与 0.2；0.2 也是核心点，继续纳入 0.3。于是前四点形成簇 0，0.0 与 0.3 最终是边界点。1.0 与 1.1 虽彼此很近，却没有达到三点密度门槛，仍是噪声；3.0 也是噪声。

最终标签可写为：

这个例子也说明 min_samples 不是“一个簇至少多少点”，而是局部核心密度阈值。

06 队列如何完成一次簇扩展？#

输入：X [N,D]，eps，min_samples
预计算或按需查询 neighbors[i]
core[i] = len(neighbors[i]) >= min_samples
labels[:] = UNVISITED
cluster_id = 0

for i in 0..N-1:
    if labels[i] 已访问: continue
    if not core[i]:
        labels[i] = NOISE
        continue

    labels[i] = cluster_id
    queue = neighbors[i]
    while queue 非空:
        j = queue.pop()
        if labels[j] == NOISE:
            labels[j] = cluster_id       # 噪声可改判为边界点
        if labels[j] 已归入某簇: continue
        labels[j] = cluster_id
        if core[j]:
            queue 加入 neighbors[j]     # 只有核心点继续扩展
    cluster_id += 1

输出：labels [N]，其中 -1 表示噪声

一个容易漏掉的细节是：先前暂记为噪声的点，之后遇到相邻核心点时必须能被改判为边界点。

07 不调用聚类器，写出最小 NumPy 实现#

下面实现用于教学与小数据核对，显式构造 $[N,N]$ 距离矩阵，空间复杂度为 $O(N^2)$：

from collections import deque
import numpy as np

def dbscan_small(X: np.ndarray, eps: float, min_samples: int):
    X = np.asarray(X, dtype=np.float64)             # [N,D]
    distances = np.linalg.norm(
        X[:, None, :] - X[None, :, :], axis=2
    )                                               # [N,N]
    neighbors = [
        np.flatnonzero(distances[i] <= eps)
        for i in range(X.shape[0])
    ]
    is_core = np.array([
        len(ids) >= min_samples for ids in neighbors
    ])                                              # [N]

    UNVISITED, NOISE = -2, -1
    labels = np.full(X.shape[0], UNVISITED, dtype=int)
    cluster_id = 0

    for seed in range(X.shape[0]):
        if labels[seed] != UNVISITED:
            continue
        if not is_core[seed]:
            labels[seed] = NOISE
            continue

        labels[seed] = cluster_id
        queue = deque(neighbors[seed].tolist())
        while queue:
            point = queue.popleft()
            if labels[point] == NOISE:
                labels[point] = cluster_id
            if labels[point] != UNVISITED:
                continue
            labels[point] = cluster_id
            if is_core[point]:
                queue.extend(neighbors[point].tolist())
        cluster_id += 1

    return labels, is_core

X = np.array([[0.0], [0.1], [0.2], [0.3], [1.0], [1.1], [3.0]])
labels, is_core = dbscan_small(X, eps=0.11, min_samples=3)

assert labels.tolist() == [0, 0, 0, 0, -1, -1, -1]
assert np.flatnonzero(is_core).tolist() == [1, 2]

队列中可能重复加入索引；labels 检查保证每个点只真正扩展一次。生产实现仍应使用经过优化的近邻索引。

08 用 scikit-learn 1.9 正确落地#

当前官方 DBSCAN API ↗ 的主要输入是 eps、min_samples、距离 metric 与近邻算法；输出包括全部标签和核心样本索引：

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X_train)           # [N,D]

db = DBSCAN(
    eps=0.35,
    min_samples=8,
    metric='euclidean',
    algorithm='auto',
    leaf_size=30,
    n_jobs=-1,
)
labels = db.fit_predict(X_scaled)                   # [N]

core_mask = np.zeros(X_scaled.shape[0], dtype=bool)
core_mask[db.core_sample_indices_] = True
n_clusters = len(set(labels)) - int(-1 in labels)
noise_ratio = np.mean(labels == -1)

assert db.components_.shape[0] == core_mask.sum()
assert db.components_.shape[1] == X_scaled.shape[1]
print(n_clusters, noise_ratio)

components_ 是核心样本的副本，形状为 [n_core_samples,D]；labels_ 包含训练样本标签，噪声为 -1。algorithm 只影响近邻搜索策略，不改变 DBSCAN 的数学定义；高维或特殊距离下可能退化为暴力搜索。

09 eps 与 min_samples 应该怎样选择？#

两者共同定义密度，不能独立机械调节：

• eps 太小：多数点成噪声，真实簇被切碎；
• eps 太大：稀疏桥把多个簇串成一个，邻域内存也会上升；
• min_samples 太小：随机小团也会成为核心；
• min_samples 太大：小而真实的簇消失。

常用诊断是第 $k$ 近邻距离图，其中 $k$ 与 min_samples 的计数约定保持一致：

import numpy as np
from sklearn.neighbors import NearestNeighbors

min_samples = 8
nn = NearestNeighbors(n_neighbors=min_samples)
nn.fit(X_scaled)
distances, indices = nn.kneighbors(X_scaled)       # [N,min_samples]
k_distance = np.sort(distances[:, -1])

# 画样本排序索引 -> k_distance，拐点只提供 eps 候选，不是自动真值

因为查询结果包含样本自身的零距离，第 min_samples 个条目正对应核心点阈值所需的最远邻居。选定候选后，应画核心/边界/噪声分布，并检查参数小范围变化时簇是否稳定。

特征尺度与距离度量比参数搜索更基础。经纬度不能直接当普通欧氏坐标；文本稀疏向量可能更适合余弦距离；混合数值与类别数据需要先定义有意义的距离。eps=0.35 只在特定缩放与度量下有意义。

10 为什么大 eps 可能突然耗尽内存？#

scikit-learn 当前实现会批量计算邻域，平均每点有 $d$ 个邻居时，存储可达 $O(Nd)$；当 eps 很大、min_samples 很小时，最坏情况达到 $O(N^2)$。这与原始论文可做到的线性内存不同。

工程上应：

1. 在样本子集上统计邻居数量分位数，再扩大数据；
2. 避免用超大 eps 把所有点连成稠密图；
3. 对重复点去重，并通过 sample_weight 保留计数；
4. 必要时用 NearestNeighbors.radius_neighbors_graph(mode='distance') 分块预计算稀疏图，再设置 metric='precomputed'；
5. 需要多尺度结构或更低内存时评估 OPTICS。

n_jobs=-1 能并行部分邻域查询，不会消除平方级邻域本身。

11 训练完成后为什么没有自然的 predict？#

DBSCAN 的簇是训练样本集合上的密度连通分量。加入一个新点可能让原本的噪声变成核心点，甚至桥接两个旧簇，因此 scikit-learn 的 DBSCAN 没有像 K 均值那样的原生 predict(X_new)。

若业务必须处理流式新样本，有三种不同语义：

• 冻结旧簇，只把新点分给附近核心样本：这是近似分类规则，不是重新运行 DBSCAN；
• 定期把新旧数据一起重新聚类，并处理簇编号匹配；
• 改用有显式外推函数的模型，或专门的增量密度方法。

不要把“离某核心点最近”伪装成原算法保证。还应为离所有核心点超过 eps 的新样本保留拒绝/噪声结果。

12 常见错误与最短调试路径#

1. 忘记缩放：先打印每列量纲与标准差，再解释距离由哪些特征主导。
2. 误以为噪声就是真异常：-1 只表示当前密度阈值下不连通；边缘小群体可能被误伤。
3. 把簇标签当有序类别：0、1、2 只是编号，不表示大小或优先级。
4. 用轮廓系数掩盖噪声处理：明确指标是否剔除 -1；同时报告覆盖率与噪声率。
5. 稀疏桥合并簇：查看连接两个主体的核心点链，而不只看最终颜色。
6. 密度差异很大：一组 eps/min_samples 无法兼顾密簇和稀簇；考虑 OPTICS/HDBSCAN 或分层建模。
7. 高维距离集中：检查最近/最远距离比与近邻稳定性，必要时先做有验证的表示学习或降维。

建议对每次运行记录：簇数、簇大小、核心点比例、噪声率、每点邻居数分位数、参数、缩放器和距离度量。对重采样数据比较簇匹配后的稳定性，比追求某个单一内部指标更可靠。

13 与相近方法的边界#

DBSCAN 找到的是特定度量和密度阈值下的连通结构，不是对“自然类别”的无假设恢复。

14 今天真正需要记住什么？#

DBSCAN 用 $\varepsilon$ 邻域和 min_samples 定义核心密度，再沿核心点邻接链扩展簇；边界点可加入但不能继续扩展，其余点记为噪声。它能表达非凸簇且无需预设簇数，但结果高度依赖尺度、距离和单一密度阈值；工程上还必须关注邻域内存与没有原生新样本预测这一边界。

15 思考题与小练习#

1. 对手算例分别把 eps 改为 0.09 和 0.81，重新列出核心点与标签。哪个设置会切碎，哪个会通过邻域链合并？
2. 构造两个核心簇共享一个非核心边界点的数据，改变输入行顺序并运行 DBSCAN；哪些标签变化只是编号置换，哪个点的簇归属真的改变？
3. 在月牙数据上比较 K 均值、GMM 与 DBSCAN。除可视化外，同时报告噪声率、核心点比例、参数扰动稳定性和查询新点时各方法能否给出原生输出。

相关工作#

• Ester et al. (1996), A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise ↗：DBSCAN 原始论文。
• Ankerst et al. (1999), OPTICS: Ordering Points To Identify the Clustering Structure ↗：把不同密度尺度组织为可达顺序。
• Campello, Moulavi & Sander (2013), Density-Based Clustering Based on Hierarchical Density Estimates ↗：层次密度聚类的重要工作。
• Schubert et al. (2017), DBSCAN Revisited, Revisited ↗：重新梳理算法、参数与复杂度实践。

16 下一篇预告#

DBSCAN 用一条密度阈值切出连通簇，但真实数据常同时存在大类、小类与嵌套子类。下一篇将进入层次聚类：怎样从样本间距离逐步合并簇，用 linkage 决定“两个簇有多近”，并从树状图选择不同粒度的结构。