DBSCAN 与层次聚类

一句话定义

DBSCAN 以密度定义簇——由密度相连的核心点扩张出的连通区域，天然识别任意形状并显式标出噪声点；层次聚类则通过不断合并（凝聚式）或分裂建立嵌套的簇树（树状图），按需在任何粒度上切取结果。

为什么重要

K-means 的球形假设在很多真实数据上不成立：地理聚集、不规则流形、带离群点的观测。DBSCAN 不需要预设簇数、能拒绝噪声，是空间数据分析与非凸聚类的默认选项；层次聚类的树状图给「分成几层」提供了全局视野，在生物分类、客户层级上很直观。三者（K-means/DBSCAN/层次）构成聚类的常规工具箱。

前置知识

K-means 聚类与 k-means++ 的聚类评估困境（为什么需要非球形方案）；距离与邻域概念。

核心概念

• ε-邻域：以 x 为心、半径 ε 内的样本集合。
• 核心点：ε-邻域内样本数 ≥ min_samples 的点。
• 直接密度可达/密度可达：从核心点出发沿「都在彼此邻域内的核心点链」可达。
• 噪声点：不属于任何簇的点（DBSCAN 显式输出标签 -1）。
• 凝聚层次聚类（AGNES）：自底向上，每轮合并最近的两个簇。
• 链接准则：single（最近点距，链式效应）/ complete（最远点距，紧凑簇）/ average / ward（合并后方差增量，常用）。

直观类比

DBSCAN 像「墨迹蔓延」：把浓墨点（核心点）滴在纸上，墨沿着彼此接触的浓点不断洇开，连成一片的就是一个簇，孤立的淡点就是噪声——形状完全由密度决定，不预设「簇是圆的」。层次聚类像公司的合并史：从个体户开始，每轮兼并「最合得来」的两家，整部合并史（树状图）都留着，董事会想分几个事业部就在对应高度横切一刀。

原理与机制

DBSCAN：对每个点查 ε-邻域；核心点通过「邻域重叠」互相连接形成簇的骨架，非核心但落在核心点邻域内的点是边界点，其余为噪声。一次建好空间索引（KD-tree/ball-tree）后复杂度约 O(n log n)。参数语义明确：eps 是「相邻」的距离尺度，min_samples 是「密度门槛」（经验取 2 × 维度或更大以滤噪声）。它不保证每个点都有归属——这是特性不是缺陷。局限：eps 全局唯一，簇密度差异大时顾此失彼（HDBSCAN 为此改进）；高维空间距离集中使邻域失去区分度。

凝聚层次聚类：初始每点一簇，反复按链接准则合并；ward 准则选择使 Δ SSE = SSE(A ∪ B) - SSE(A) - SSE(B) 最小的合并，与 K-means 的方差目标一致故常配套使用。single 链接在带桥接噪声时会「串线」形成长链簇。输出是一棵树，n_clusters 或「距离阈值」两种切法都行。

公式与推导

Ward 合并准则的增量：

推导：簇内平方和可改写为 ∑_{x ∈ C} ‖ x - μ_C ‖² = 12n_C∑_{x ≠ y ∈ C} ‖ x - y ‖²（均值代入展开可得），据此重排合并前后的平方和即得上式——合并代价与「簇大小乘积 × 质心距离」成正比，自然抑制大簇吞并远点。

图示

K-means 失败 vs DBSCAN 成功（月牙形）
 K-means（球形切割）        DBSCAN（密度连通）
 ┌──────────────┐
 │ ○○○○○ │ △△△△ │        ○○○○○●●●●●
 │○○○○○○ │△△△△△ │   →    ○○○○○●●●●●
 │───────┼──────│            （两月牙各成一簇，
 │ △△△△△ │ ●●●● │             弯外散点 → 噪声 -1）
 └──────────────┘        无需 k，形状任意

实例或案例

三种算法在同心环 + 弯月数据上的对照：

from sklearn.datasets import make_moons
from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import adjusted_rand_score
from sklearn.pipeline import make_pipeline

X, y_true = make_moons(n_samples=600, noise=0.08, random_state=0)   # 借真标签算 ARI 仅为教学
algos = {
    "K-means": make_pipeline(StandardScaler(), KMeans(n_clusters=2, n_init="auto", random_state=0)),
    "DBSCAN":  make_pipeline(StandardScaler(), DBSCAN(eps=0.25, min_samples=6)),
    "Ward层次": make_pipeline(StandardScaler(), AgglomerativeClustering(n_clusters=2, linkage="ward")),
}
for name, a in algos.items():
    labels = a.fit_predict(X)
    print(f"{name}: ARI={adjusted_rand_score(y_true, labels):.3f}, 噪声点={sum(labels == -1)}")

K-means 把月牙拦腰切开，DBSCAN 与 ward 层次聚类恢复完整月牙——簇形状先验决定了成败。

常见误区

• eps 拍脑袋：应先做 k-距离图（每个点到第 min_samples 近邻的距离排序，找肘点）再定 ε。
• 高维数据直接用 DBSCAN：维度一高所有点互相「等距」，密度失去意义，先降维（kp-021）或改算法。
• 层次聚类在全量大数据上强算：O(n²) 起步的距离矩阵扛不住数万样本，先采样或换 MiniBatchKMeans。
• 把 DBSCAN 的「噪声」当错误删除：噪声标签本身是检测离群点的免费产出。

与其他知识点的关系

K-means 聚类与 k-means++ 的球形假设是本节的对照组；主成分分析 PCA 的 PCA 常作为高维聚类前的预处理；ward 准则与 K-means 共享方差目标，二者常组成「层次粗分 → K-means 细化」流程。

自测题

1. DBSCAN 的核心点、边界点、噪声点如何区分？

- 要点：核心点 ε-邻域内 ≥ min_samples；边界点落在核心点邻域内但自身非核心；两者都不是 → 噪声。

1. single 与 complete 链接的簇形态差别？

- 要点：single 看最近点距，易链式拉出长条簇；complete 看最远点距，倾向紧凑等径簇；ward 以方差增量为准则介于其间。

1. 为什么 DBSCAN 不需要预设簇数？代价是什么？

- 要点：簇数由密度结构涌现；代价是必须调好 eps/min_samples，且全局统一密度假设在多密度数据上失效。

延伸阅读

Ester 等， A Density-Based Algorithm for Discovering Clusters…（KDD, 1996）；周志华《机器学习》第 9 章。