空间聚类进阶

上一篇文章介绍了核密度分析，用连续的密度场描述点分布。本文转向离散视角：如何把点聚成有意义的簇。K-Means 是最常用的聚类算法，但它假设簇是凸的、大小相近的，且需要预先指定簇数，这在空间数据（POI 分布、犯罪热点、轨迹点群）中常常不成立。本文介绍密度聚类家族：DBSCAN、OPTICS 与 HDBSCAN，它们不预设簇数、能发现任意形状的簇，是空间聚类的标准工具。

K-Means 在空间数据上的局限

K-Means 的目标是把 $n$ 个点分到 $K$ 个簇，最小化簇内平方距离和：

\min_{C_1, \ldots, C_K} \sum_{k=1}^{K} \sum_{x \in C_k} \| x - \mu_k \|^2

其中 $\mu_k$ 是簇 $C_k$ 的均值中心。它有两个结构性假设：

簇是凸的：K-Means 用均值代表簇，本质假设簇在欧氏空间中是（近似）凸的。空间数据中的簇常呈带状、环形、沿道路延伸的形状，凸假设不成立。
需要预设 $K$ ：空间数据往往不知道"应该有几个簇"，POI 密度差异大，全局一个 $K$ 不合理。

此外 K-Means 对噪声敏感：离群点会拉偏均值，导致簇边界失真。密度聚类正是针对这些缺陷设计的。

DBSCAN：核心的密度聚类

两个参数

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，1996）基于两个参数：邻域半径 $\varepsilon$ 与最小点数 $\text{MinPts}$ 。点 $p$ 的 $\varepsilon$ -邻域定义为：

N_{\varepsilon}(p) = \{ q \in D \mid \text{dist}(p, q) \le \varepsilon \}

三种点

基于邻域内点数，点被分为三类：

核心点（Core point）： $|N_{\varepsilon}(p)| \ge \text{MinPts}$ ，密度足够高，是簇的骨架。
边界点（Border point）： $|N_{\varepsilon}(p)| < \text{MinPts}$ ，但在某个核心点的邻域内，位于簇的边缘。
噪声点（Noise point）：既不是核心点也不在任何核心点邻域内，被标记为噪声。

密度可达与密度相连

密度直达（Directly density-reachable）： $q$ 在核心点 $p$ 的 $\varepsilon$ -邻域内，则 $q$ 从 $p$ 密度直达。

密度可达（Density-reachable）：存在点链 $p_1, \ldots, p_m$ （ $p_1 = p$ ， $p_m = q$ ），使 $p_{i+1}$ 从 $p_i$ 密度直达，则 $q$ 从 $p$ 密度可达。注意密度可达是非对称的（核心点可达边界点，反之不一定）。

密度相连（Density-connected）：存在点 $o$ ，使 $p$ 和 $q$ 都从 $o$ 密度可达。密度相连是对称的，DBSCAN 的簇定义为"互相密度相连的点的最大集合"。

算法流程

遍历所有点，找到未访问的核心点 $p$ 。
从 $p$ 出发，收集所有密度可达的点，构成一个簇。
重复直到所有点被访问。

DBSCAN 的优势是不需要预设簇数、能发现任意形状的簇、天然处理噪声。代价是 $\varepsilon$ 和 MinPts 需要调参，且对密度不均的数据失效：全局单一 $\varepsilon$ 无法同时适配高密度区与低密度区，低密度区的簇会被当成噪声，高密度区的簇会被合并。

OPTICS：对密度不均的回应

OPTICS（Ordering Points To Identify the Clustering Structure，1999）的核心洞察是：与其给出一个固定的 $\varepsilon$ 划分，不如输出一个按密度排序的点序，让用户（或下游算法）在任意密度阈值下都能提取聚类。

核心距离与可达距离

对点 $p$ ，给定 MinPts，定义核心距离为"使 $p$ 成为核心点的最小半径"：

\text{core-dist}_{\varepsilon, \text{MinPts}}(p) = \begin{cases} \text{UNDEFINED}, & |N_{\varepsilon}(p)| < \text{MinPts} \\ \text{dist}(p, p_{\text{MinPts}}), & \text{otherwise} \end{cases}

其中 $p_{\text{MinPts}}$ 是 $p$ 的第 MinPts 近邻。可达距离定义为：

\text{reach-dist}(o, p) = \max\left( \text{core-dist}(p), \text{dist}(o, p) \right)

可达距离的直觉：从 $o$ 出发到达 $p$ 的"代价"由两者的距离和 $p$ 自身的密度共同决定。

输出：可达距离图

OPTICS 维护一个优先队列，按可达距离从小到大扩展点，输出一个点序 + 每个点的可达距离。把可达距离画成图（可达距离图），密度高的区域对应"山谷"，密度低的区域对应"山峰"，簇就是山谷之间的区域。用不同的水平线切割可达距离图，就能得到不同密度阈值下的聚类，这等价于在不同 $\varepsilon$ 下运行 DBSCAN，但只需运行一次 OPTICS。

HDBSCAN：层次化 + 稳定簇提取

HDBSCAN（2017）进一步解决 OPTICS 的阈值选择问题：它把密度聚类建立在层次聚类之上，用"稳定性"自动选择最优簇。

互达距离与最小生成树

定义点之间的互达距离（Mutual reachability distance）：

d_{\text{mreach}}(p, q) = \max\left( \text{core-dist}(p), \text{core-dist}(q), \text{dist}(p, q) \right)

互达距离把"两个点的核心距离"纳入距离度量，使低密度区的点对距离被"垫高"，密度不均的影响被缓解。以互达距离为边权构建最小生成树（MST），再按距离从大到小分裂，得到树状图（dendrogram），即凝聚层次聚类的密度版本。

稳定簇的提取

树状图的每个节点代表一个簇候选，簇的"密度"定义为簇分裂前所有点的互达距离倒数。簇 $C$ 的稳定性定义为：

S(C) = \sum_{p \in C} \left( \lambda_{\max}(p) - \lambda_{\min}(C) \right)

其中 $\lambda = 1 / d_{\text{mreach}}$ （密度）， $\lambda_{\max}(p)$ 是点 $p$ 所在分支的密度， $\lambda_{\min}(C)$ 是簇 $C$ 形成的密度阈值。稳定性衡量"这个簇内部密度有多高、跨度有多大"。

提取规则：自底向上遍历树状图，当子簇稳定性之和超过父簇时保留子簇，否则合并为父簇。这自动决定了簇的数量与层级，无需任何阈值参数（只需 MinPts）。

密度聚类家族的演进

DBSCAN 用固定 $\varepsilon$ 划分密度，无法处理密度不均；OPTICS 用可达距离图表达"所有密度阈值下的聚类结构"，但仍需人工看图选阈值；HDBSCAN 把密度嵌入层次聚类，用稳定性自动选簇，把"调阈值"变成"调 MinPts"。三步演进对应"固定阈值 → 阈值谱 → 自动选择"。

三种方法的对比

方法	簇数	形状	密度不均	主要参数	输出
DBSCAN	自动	任意	不擅长	$\varepsilon$ , MinPts	硬簇 + 噪声
OPTICS	自动（需看图）	任意	擅长	MinPts	可达距离图
HDBSCAN	自动	任意	擅长	MinPts	层次簇 + 概率

实践建议：空间数据密度均匀时 DBSCAN 足够；密度差异大（城市中心 vs 郊区）用 HDBSCAN；需要解释"为什么分成这些簇"时，OPTICS 的可达距离图直观。HDBSCAN 还输出每个点属于簇的概率，这对带噪声的空间数据（如 GPS 轨迹点）很实用。

与核密度分析的联系

核密度分析（KDE）给出连续的密度估计 $\hat{f}(x) = \frac{1}{nh} \sum K\left(\frac{x - x_i}{h}\right)$ ，密度聚类的"密度"概念与它同源：DBSCAN 的 $\varepsilon$ 对应 KDE 的带宽 $h$ ，MinPts 对应密度阈值。两者互补：KDE 回答"哪里密度高"，密度聚类回答"高密度区域如何分组"。实际分析中常先用 KDE 看整体形态，再用 HDBSCAN 得到明确的簇划分。

参考

[1] Ester, M., et al. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD 1996.
[2] Ankerst, M., et al. OPTICS: Ordering Points To Identify the Clustering Structure. SIGMOD 1999.
[3] Campello, R. J. G. B., Moulavi, D., & Sander, J. Density-Based Clustering Based on Hierarchical Density Estimates. PAKDD 2013.
[4] McInnes, L., Healy, J., & Astels, S. hdbscan: Hierarchical Density Based Clustering. JOSS, 2017.
[5] Lloyd, S. Least Squares Quantization in PCM. IEEE Transactions on Information Theory, 1982.