4.5 密度连通与均值漂移

使用局部集中程度的两种方式

若每组只用一个中心代表，弯曲或狭长的群组可能难以辨认。密度方法改从局部集中程度出发。DBSCAN 先问哪些观测有足够多邻近观测，再把稠密区域接起来。均值漂移则用数据建立平滑密度，把种子移往密度较高的位置。两者使用邻域的方式不同：图上的连通不是梯度步骤，而核密度的众数也不是邻域计数。

两种方法都需要几何尺度。半径或带宽改变，“邻近”的意义也改变。最后组数虽然是输出，几何仍取决于选定的距离及特征单位。我们先考虑度量空间中的有限有索引数据，再于均值漂移部分改用欧氏特征向量。

DBSCAN 的核心、边界与噪声

定义

闭邻域与核心观测

选取 $\varepsilon>0$ 及整数 $m\ge1$。对每个观测 $i$，定义

$$N_\varepsilon(i)=\{j:d(x_i,x_j)\le\varepsilon\},\qquad \mathcal C=\{i:|N_\varepsilon(i)|\ge m\}.$$

邻域包括 $i$ 本身。$\mathcal C$ 内的索引称为核心观测。非核心观测若邻域中有核心观测，便是边界观测；若没有核心邻居，便是噪声。重复观测的索引不同，因此分开计数。

只以核心观测为顶点建图，两个不同核心观测相距至多 $\varepsilon$ 时连边。连通分量构成各群组的核心部分。然后把边界观测附到包含其核心邻居的一个分量。如果有多个可附加的分量，便按固定分量次序决定唯一标签。噪声不获分组，惯例上以标签 $-1$ 表示。

命题

核心连通不会穿过边界点

核心分量不依赖遍历次序。边界观测可以同时邻接多个核心分量，但把它附到其中一组，不会合并那些核心分量。

证明

追踪哪些观测可延伸路径

核心路径只使用核心顶点及长度至多 $\varepsilon$ 的边。这类路径是否存在，是固定图本身的性质，故连通分量不依赖搜索次序。密度扩展可经核心观测继续；非核心端点可以被纳入，但不能继续延伸。两个分量共用的边界点，因而是任一扩展的端点，而不是把两者连起的中间核心顶点。它的最终标签取决于附加规则，核心分量仍保持分开。

这个区别是算法的关键。若把“至少一端是核心”的所有边放进一张图再求连通分量，就会容许共用边界点充当桥梁。另外，孤立的非核心观测是噪声，不是额外的单点群组。若 $m=1$，所有观测都是核心，DBSCAN 就退化为一般 $\varepsilon$ 邻接图的连通分量。

例题

共用边界与孤立观测

取 $\varepsilon=1$、$m=4$，一维数据为

$$X=(-1.8,-1.6,-1.4,-0.9,0,0.9,1.4,1.6,1.8,4).$$

四个负数观测都是核心而且互相连通；四个小于二的正数观测构成另一个核心分量。$-0.9$ 及 $0.9$ 的邻域各有五个观测，包括自身；其余六个核心观测各有四个邻居。零的邻域恰为 $\{-0.9,0,0.9\}$，只有三个邻居，故零是边界观测。它可按固定次序附到任一分量，却不能把两个核心分量合并。四的邻域只有自身，所以是噪声。先处理负数分量时，最后两组大小为五和四，另有一个噪声观测。

以下代码直接实现这个构造。第一个循环只标记核心分量；第二个循环把余下观测附到标签最小的相邻核心分量，如果存在这种分量。

import numpy as np

x = np.array([-1.8, -1.6, -1.4, -0.9, 0., 0.9, 1.4, 1.6, 1.8, 4.])
near = np.abs(x[:, None] - x[None, :]) <= 1.
core = near.sum(axis=1) >= 4
labels = np.full(len(x), -1, dtype=int)
next_label = 0
for start in np.flatnonzero(core):
    if labels[start] != -1:
        continue
    labels[start] = next_label
    stack = [int(start)]
    while stack:
        i = stack.pop()
        for j in np.flatnonzero(near[i] & core):
            if labels[j] == -1:
                labels[j] = next_label
                stack.append(int(j))
    next_label += 1
for i in np.flatnonzero(~core):
    adjacent = labels[near[i] & core]
    if len(adjacent):
        labels[i] = adjacent.min()
print(near.sum(axis=1).tolist())
print(labels.tolist())

邻居数是 $4,4,4,5,3,5,4,4,4,1$，标签是 $0,0,0,0,0,1,1,1,1,-1$。实现把连通问题与边界标签惯例清楚分开；两步均不要求预先给定群组数。

参数与密度层次的变化

固定 $m$ 而增大 $\varepsilon$，可能令非核心观测成为核心，也可能连接原本分开的核心区域。新的核心区域亦可能先出现，再于更大的半径才接到旧区域。因此每次增大半径，群组总数不一定都下降。固定半径而提高 $m$，则令核心要求更难满足。同一个实际半径可能揭示一个稠密区域，却把较稀疏但仍有意义的群组标为噪声。

DBSCAN 在整份数据使用一个半径与一个计数阈值。这是采用共同密度尺度的选择，不是说所有观测密度必须相同。坐标缩放后，若距离未相应调整，邻域就会改变。因此选择度量及其单位，是定义聚类问题的一部分。

从核心距离建立密度层次

层次密度方法不立即选一个半径，而是追踪不同半径下的连通结构。固定 $1\le m\le n$，沿用计入自身的惯例，定义

$$c_m(i)=\min\{r\ge0:|N_r(i)|\ge m\},\qquad w(i,j)=\max\{c_m(i),c_m(j),d(x_i,x_j)\}\quad(i\ne j).$$

核心距离 $c_m(i)$ 是收集 $m$ 个观测所需的半径。互达边权 $w(i,j)$ 只有在两端都局部集中，而且彼此接近时才会小。这个公式定义不同顶点之间的边权；若需要距离矩阵的对角值，另设为零。

例题

稀疏端点提高边权

取 $X=(0,0.1,0.2,1.2,2.2)$、$m=3$，计入观测自身。按此顺序的核心距离为

$$(c_m(i))_{i=1}^5=(0.2,0.1,0.2,1,2).$$

零至 $0.1$ 的边权为 $0.2$；$1.2$ 至 $2.2$ 的欧氏距离虽是一，边权却是二。后一个端点要到半径二才收集到第三个观测；边权因此包含其局部稀疏程度。

先建立完全加权图，再求最小生成树 MST。在每个边权阈值下，切割 MST 都保留原图的连通分量。理由是：若一条权重至多 $t$ 的边没有选入 MST，它两端在树上路径的每条边都不会比它重；否则可用它替换较重的路径边，降低树的总权重。所以删去权重大于 $t$ 的树边后，两端仍然相连。仅用 $n-1$ 条边，便保留了整个连通层次。

HDBSCAN 以最小群组大小压缩这个层次，再选取能跨越密度层次持续存在的分支。这个大小与局部计数 $m$ 是不同概念。很小的分支可被视为观测离开原有群组，而不是形成新的实质群组。稳定性分数可在正阈值 $t>0$ 下，以 $\lambda=1/t$ 度量成员累积的持续程度；同一平面划分中，选取母组便不再同时选其后代。如此可利用不同分支的存续期间，而不用一个共同水平切割。结果仍取决于距离及两类大小选择。

固定观测下的高斯均值漂移

以下回到特征向量 $x_i\in\mathbb R^d$。整个计算保持这些观测固定。对带宽 $h>0$，定义

$$K_i(p)=\exp\!\left(-\frac{\|x_i-p\|_2^2}{2h^2}\right),\qquad F(p)=\sum_{i=1}^nK_i(p),\qquad q_i(p)=\frac{K_i(p)}{F(p)}.$$

把 $F$ 乘以高斯密度估计的归一化常数，不会改变众数或对数梯度。权重 $q_i(p)$ 为正而且总和为一。加权均值与更新为

$$\mu(p)=\sum_iq_i(p)x_i,\qquad p^{(t+1)}=\mu(p^{(t)}).$$

只有种子 $p$ 移动。若把全部观测都移动，再用它们的新位置作下一轮的参照数据，所优化的密度本身便会改变。作聚类时，可在各观测位置初始化种子，执行固定密度更新，再按抵达的极限位置或明确指定的终点邻近容差，把种子分组。

命题

高斯均值漂移的方向与上升性

对固定有限数据及 $h>0$，

$$\nabla\log F(p)=\frac{\mu(p)-p}{h^2},\qquad \log F(\mu(p))-\log F(p) \ge\frac{\|\mu(p)-p\|_2^2}{2h^2}.$$

因此每个非零均值漂移步骤都严格提高此密度值。

证明

先微分，再用加权对数不等式

逐项微分可得 $\nabla K_i(p)=K_i(p)(x_i-p)/h^2$。求和后除以 $F(p)$，即得梯度公式。对任意候选位置 $z$，把 $F(z)/F(p)$ 写成使用固定权重 $q_i(p)$ 的加权和。由对数函数的凹性，

$$\log\frac{F(z)}{F(p)} \ge-\frac1{2h^2}\sum_iq_i(p) \left(\|z-x_i\|_2^2-\|p-x_i\|_2^2\right) =\frac{\|p-\mu(p)\|_2^2-\|z-\mu(p)\|_2^2}{2h^2}.$$

等号使用加权均值的平方距离分解。令 $z=\mu(p)$，即得所需下界。

由于 $F(p)\le n$，沿迭代的密度值会增加至一个有限极限。把上升下界累加，得到步长平方的总和有限，故步长趋向零。这些结论涉及目标及步长；不动点则满足驻点方程 $\nabla F(p)=0$。它未必是全局最大值，对称性甚至可能把种子留在局部最小值。

例题

每一步都使用原数据的两次精确更新

设 $X=\{0,2\}$、$h^2=2/\log2$、$p^{(0)}=0$。初始的未归一化核权重是一和二分之一，因此

$$p^{(1)}=\frac23,\qquad p^{(2)}=\frac{2}{1+2^{1/3}}\approx0.884986668.$$

第二次计算中，零与二的权重比为 $2^{1/3}$。两个权重仍根据原来的零和二重新计算，而非使用任何其他已更新的种子。带宽决定每个观测对加权中心的贡献程度。

import numpy as np

x = np.array([0., 2.])
h2 = 2. / np.log(2.)
p = 0.
for _ in range(2):
    weights = np.exp(-(x - p) ** 2 / (2. * h2))
    p = float(weights @ x / weights.sum())
    print(f"{p:.9f}")

输出依次为 0.666666667 及 0.884986668。对一般核函数，须按该核的导数推导加权更新与密度梯度的关系。上面的高斯公式来自其特定导数及带宽惯例。

带宽、驻点与停止准则

带宽同时控制密度形状及每次更新的幅度。对称数据 $X=\{-1,1\}$ 可直接化简得

$$\mu(p)=\tanh(p/h^2),\qquad \mu'(0)=h^{-2},\qquad F''(0)=2e^{-1/(2h^2)}(h^{-4}-h^{-2}).$$

零永远是不动点。若 $h>1$，密度二阶导数为负，更新映射导数的绝对值小于一：零是局部密度最大值，附近种子会被吸引过来。若 $0<h<1$，密度二阶导数为正，更新会把附近非零种子推离零，但恰在零的种子仍留在原地。当 $h=1$，上述导数检验不足以下结论。因此改变带宽可以改变驻点几何及吸引行为，不只是调整计算速度。

每次加权均值都是固定观测的凸组合。第一次更新后，种子便位于这些观测的紧致凸包内，故序列有界。再结合步长趋零：若某子序列趋向 $p_*$，由 $\mu$ 的连续性得 $\mu(p_*)-p_*=0$。所以每个聚点都是驻点。这个论证精确说明密度上升可推出的结论，没有把同一驻点指定为每个初始化必得的答案。

数值计算中的位移容差也带有带宽尺度。精确梯度恒等式给出 $\|\nabla\log F(p)\|_2=\|\mu(p)-p\|_2/h^2$。因此不同带宽下，相同位移容差可对应不同的对数梯度大小。停止准则处理种子的密度更新；把邻近终点合并所用的容差，则是另一项分组选择。

计数尺度与重复观测

邻域计数亦有采样尺度。假设把每个有索引观测在原位置复制一次，固定半径下所有邻域计数都会加倍。若 $m$ 不变，原先的边界或噪声观测便可能成为核心。虽然没有引入新的几何位置，聚类仍可能改变。因此样本量改变与特征单位改变，是不同问题。

对完全重复的数据，观测加倍时若把所需计数也加倍，各位置的原核心条件就会保留。但这不是适用于不同位置新样本的一般规则。在图像应用中，改变像素分辨率会改变邻域计数；在跟踪应用中，抽取帧数不同，也会改变同一实际半径内收集的局部证据量。因此计数阈值须配合观测过程解读。

练习

思考检查

1. 计入观测自身

对 $X=\{0,0.4,0.8,3\}$、$\varepsilon=0.5$、$m=3$，辨认核心、边界与噪声观测。

解答 · 练习 1 解答

只有 $0.4$ 是核心，其邻域为 $\{0,0.4,0.8\}$。零与 $0.8$ 各有两个邻居，是邻接此核心点的边界观测。三是噪声。结果是一个含三个观测的群组，以及一个未分配的观测。

思考检查

2. 两分量共用的边界

在十个观测的例子中，把零分到负数组，会否令正数核心分量也成为同一组的一部分？

解答 · 练习 2 解答

不会。零是非核心观测，不能延伸密度扩展。它与 $0.9$ 邻接，不会在两个核心分量之间建立核心边。先处理正数组只会改变零的标签，不会改变两个核心分量。

思考检查

3. 并非众数的不动点

取 $X=\{-1,1\}$、$h=1/2$。在零初始化高斯均值漂移种子会怎样？该点是否 $F$ 的局部最大值？

解答 · 练习 3 解答

对称性令两个权重相同，故 $\mu(0)=0$，种子停留原地。但 $F''(0)=24e^{-2}>0$，所以零是严格局部最小值。若恰在这类对称驻点初始化，种子未必抵达众数。

思考检查

4. 生成树为何保留阈值连通

一条权重 $0.7$ 的边没有选入 MST。只删去权重大于一的树边后，它的两端会否变成不连通？

解答 · 练习 4 解答

不会。两端在 MST 上路径的每条边都至多重 $0.7$；否则可用被省略的边替换较重边，降低总树重。因此整条路径都保留在阈值一之下。

相关笔记

• 层次聚类的连接准则与树状图 推导单连接连通及切树方法。
• 学习度量与随机投影 解释改变度量如何改变邻域几何。
• 高斯混合与期望最大化 使用另一种软成员概率意义。
• 课程书目 集中列出推荐书籍。