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$；否則可用被省略的邊替換較重邊，降低總樹重。因此整條路徑都保留在閾值一之下。

相關筆記

• 層次聚類的連結準則與樹狀圖 推導單連結連通及切樹方法。
• 學習度量與隨機投影 解釋改變度量如何改變鄰域幾何。
• 高斯混合與期望最大化 使用另一種軟成員概率意義。
• 課程書目 集中列出推薦書籍。