4.4 層次聚類的連結準則與樹狀圖

從一個劃分走向整個層次

一個劃分只提供一種分組。分析資料時，我們往往希望同時觀察不同解析度：先分成兩個大組，再研究每個大組內的細分。層次聚類用一棵樹記錄這些嵌套的決定。葉節點代表個別觀測，內部節點代表由子節點組成的群組。切割樹便可取得某個層次的劃分，而不用為每個指定組數重新擬合一套模型。

核心選擇是怎樣量度兩組之間的分隔。最近一對觀測、最遠一對觀測，以及所有跨組觀測對的平均距離，回答的是不同問題。它們也不等同於兩個平均向量的距離。只有同時指定點距離、群組連結準則及並列處理規則，層次聚類才成為明確的數學程序。

設有限資料為 $x_1,\ldots,x_n$，其中 $n\ge2$。一個群組是非空的觀測索引集合。即使兩個觀測的特徵向量相同，仍保留不同索引。在每個階段，當前各組構成一個劃分：組與組互不相交，而所有索引都恰好出現一次。

四種連結準則

定義

單連結、全連結與平均連結

對互不相交的非空群組 $A,B$ 及點距離 $d$，定義

$$L_{\mathrm{single}}(A,B)=\min_{i\in A,j\in B}d(x_i,x_j),\qquad L_{\mathrm{complete}}(A,B)=\max_{i\in A,j\in B}d(x_i,x_j),$$$$L_{\mathrm{average}}(A,B)=\frac1{|A||B|} \sum_{i\in A}\sum_{j\in B}d(x_i,x_j).$$

單連結問兩組之間是否存在鄰近的接點；全連結問所有跨組觀測對是否都接近；平均連結則量度全部跨組距離的平均值，每一對觀測所佔的權重相同。

這三種準則可用於已給定的對稱相異度矩陣，算法定義本身不要求歐氏座標。若要作進一步的幾何推論，才須核對度量性質。在一般歐氏距離下，一串短間隔可以令單連結把端點相距很遠的資料連成一組。全連結較不容易出現這種情況，因為任何很遠的跨組觀測對都會把連結值增大。

Ward 連結量度的是平方誤差增量。以下特徵向量位於 $\mathbb R^d$，範數採歐氏範數。記

$$\mu_A=\frac1{|A|}\sum_{i\in A}x_i,\qquad W(A)=\sum_{i\in A}\|x_i-\mu_A\|_2^2.$$

命題

Ward 合併代價

對互不相交的非空 $A,B$，

$$\Delta(A,B)=W(A\cup B)-W(A)-W(B) =\frac{|A||B|}{|A|+|B|}\|\mu_A-\mu_B\|_2^2.$$

Ward 方法在當前群組中選取令 $\Delta(A,B)$ 最小的一對。

證明

分開組內變異與平均值位移

設 $a=|A|$、$b=|B|$、$\mu=(a\mu_A+b\mu_B)/(a+b)$。展開 $x_i-\mu=(x_i-\mu_A)+(\mu_A-\mu)$ 並對 $A$ 求和。由於 $\sum_{i\in A}(x_i-\mu_A)=0$，交叉項消失。對 $B$ 亦然，因此

$$W(A\cup B)=W(A)+W(B)+a\|\mu_A-\mu\|_2^2 +b\|\mu_B-\mu\|_2^2.$$

又因 $\mu_A-\mu=\frac b{a+b}(\mu_A-\mu_B)$ 及 $\mu_B-\mu=-\frac a{a+b}(\mu_A-\mu_B)$，餘下兩項的和就是 $ab\|\mu_A-\mu_B\|_2^2/(a+b)$。

組的大小因子不可省略。即使兩對群組有相同的平均值距離，成員數不同也可能令合併代價不同。本節把 $\Delta$ 本身作為 Ward 樹的高度。若使用 $\sqrt{2\Delta}$ 等慣例，合併次序相同，但高度數值不同；解讀圖上的高度是否等於誤差時，必須先確定慣例。

例題

同一對群組的四個答案

在實數線上取 $A=\{0,2\}$、$B=\{5,9\}$。四個跨組距離是 $5,9,3,7$，所以

$$L_{\mathrm{single}}=3,\qquad L_{\mathrm{complete}}=9,\qquad L_{\mathrm{average}}=6,\qquad \Delta=36.$$

最後一項中，兩組大小都是二，平均值是 $1$ 和 $7$。亦可直接核算 $W(A)=2$、$W(B)=8$、$W(A\cup B)=46$，增量為 $46-2-8=36$。平均跨組距離是六，Ward 代價卻是三十六：兩者的意義及單位均不同。

凝聚程序與精確切割

凝聚法先建立 $n$ 個單點群組。計算每對當前群組的連結值，選最小的一對合併，再以其聯集取代原來兩組。重複直至只剩一組。每次合併令組數減一，因此總共有 $n-1$ 次合併。

為使結果可重現，完全並列時使用候選組對中已排序索引列表的字典序。若最小連結值相同，另一個並列規則可能產生另一棵同樣合法的樹。這個規則是程序的一部分，不表示計算出現數值故障。

完成 $n-k$ 次合併後，必定恰有 $k$ 組。因此只要 $1\le k\le n$，按合併次數切割一定可行。水平高度切割則是另一項操作：把閾值以下的所有合併都執行。多次合併若高度相同，組數可能一次跳過幾個整數，所以未必每個 $k$ 都能以某個水平高度實現。

例題

連結準則改變嵌套結構

按次序取有索引的點 $0,3,4,6,8$，使用上述並列規則。兩種準則的完整合併記錄如下：

合併	單連結	高度	全連結	高度
1	$\{3\},\{4\}$	$1$	$\{3\},\{4\}$	$1$
2	$\{3,4\},\{6\}$	$2$	$\{6\},\{8\}$	$2$
3	$\{3,4,6\},\{8\}$	$2$	$\{0\},\{3,4\}$	$4$
4	$\{0\},\{3,4,6,8\}$	$3$	$\{0,3,4\},\{6,8\}$	$8$

切成兩組時，單連結給出 $\{0\}$ 與 $\{3,4,6,8\}$；全連結則給出 $\{0,3,4\}$ 與 $\{6,8\}$。差別直接來自準則：單連結可沿着長度二的間隔逐步延伸，但全連結必須同時考慮三與八之間的距離。

合併後如何更新連結值

每次合併後重新列出所有觀測對，會掩蓋可用的遞推結構。對另一當前群組 $C$，設 $a=|A|$、$b=|B|$，則

$$L_{\mathrm{single}}(A\cup B,C) =\min\{L_{\mathrm{single}}(A,C),L_{\mathrm{single}}(B,C)\},$$ $$L_{\mathrm{complete}}(A\cup B,C) =\max\{L_{\mathrm{complete}}(A,C),L_{\mathrm{complete}}(B,C)\},$$ $$L_{\mathrm{average}}(A\cup B,C) =\frac a{a+b}L_{\mathrm{average}}(A,C) +\frac b{a+b}L_{\mathrm{average}}(B,C).$$

平均連結公式只需把雙重求和分成來自 $A$ 與 $B$ 的觀測對。若把兩個舊連結值不加權平均，就會讓大小不同的群組佔相同總權重，因而定義出另一種方法。最小值及最大值公式則來自兩個跨組觀測對集合的聯集。

這些更新式也說明三種準則的合併高度不會下降。當某對在當前最小值 $h$ 被合併時，其餘各對的值均至少為 $h$。新值是舊值的最小值、最大值或加權平均，故也至少為 $h$。逐次應用即可得到整個高度序列單調不減。

命題

單連結切割等於圖的連通分量

固定閾值 $t\ge0$，以觀測索引為頂點，當 $d(x_i,x_j)\le t$ 時連邊。把單連結層次中高度至多 $t$ 的合併全部完成後，所得群組恰好是這張圖的連通分量。

證明

跨組短邊恰好對應可執行的合併

若一條長度至多 $t$ 的邊連接兩個當前群組，其單連結值就至多為 $t$，所以算法不可能在仍分開這兩組時完成閾值切割。因此圖中同一路徑上的頂點最終會在同一組。反過來，每次高度至多 $t$ 的合併，必有一條長度至多 $t$ 的跨組邊作連接。從單點組出發，這類合併不會超出原圖的一個連通分量。兩個方向合起來即得結論。

即使一條連接路徑上的邊都很短，連通分量的直徑仍可能很大。圖的表述精確呈現了鏈狀效應，也解釋為何刪除一條橋邊便可把很大的單連結群組拆開，儘管大部分成對距離幾乎沒有改變。

可執行的小型合併記錄

以下直接實作全連結，分開保存索引與座標，並用 tuple 次序處理完全並列。每次從定義計算準則，方便核對小型手算過程。

import numpy as np

x = np.array([0., 3., 4., 6., 8.])
clusters = [(i,) for i in range(len(x))]
while len(clusters) > 1:
    candidates = []
    for i in range(len(clusters)):
        for j in range(i + 1, len(clusters)):
            a, b = clusters[i], clusters[j]
            height = np.abs(x[list(a), None] - x[list(b)]).max()
            candidates.append((float(height), a, b, i, j))
    height, a, b, i, j = min(candidates)
    print(a, b, height)
    clusters = [c for k, c in enumerate(clusters) if k not in (i, j)]
    clusters.append(tuple(sorted(a + b)))
    clusters.sort()

輸出的高度是 $1,2,4,8$。tuple 是從零起算的觀測索引，故第一個合併 $(1,),(2,)$ 指座標三和四。連結記錄必須保留這項區別，才不會在特徵向量重複時丟失觀測身分。

分裂式層次

自上而下的方法先把全部資料視為一組，再逐次切開一個當前群組。一個具體程序是選成員最多的組，大小並列時用索引列表決定，然後以二均值法切成兩組。二均值法的初始化及並列處理也須指定。切割完成後，後續操作只在子組內進行，不會讓觀測跨過先前建立的邊界。

例題

切開最大的群組

從 $0,1,8,9,20$ 開始，以零和二十初始化二均值法，穩定後得到 $\{0,1,8,9\}$ 與 $\{20\}$，平均值分別為 $4.5$ 和 $20$。第一組較大；再以零和九初始化切割它，得到 $\{0,1\}$ 與 $\{8,9\}$。最後三組的組內平方誤差為 $1/2+1/2+0=1$，而第二次切割前是 $65$。後一次切割只細分其母組，沒有重新考慮包含二十的單點組。

分裂式與凝聚式方法作出不同的不可逆決定。因此一連串二均值切割並不是 Ward 合併次序的倒轉。兩者都提供嵌套劃分，但搜尋過程及局部選擇不同。樹記錄的是這些決定，不能據此推論每個切割都令全局聚類目標最小。

解讀合併高度

高度的意義取決於連結準則。對全連結，如果某群組由高度不超過一個閾值的合併形成，則其直徑也不超過該閾值。可用歸納法證明：單點組直徑為零；兩組合併時，每個跨組距離都不超過全連結值，而子組內的距離已滿足界限。因此這個閾值控制合併後每一對觀測，而不只是最後接上的位置。

對單連結，閾值控制的是連接路徑所需的最大邊長；長鏈的兩端可以相距很遠。對平均連結，高度是當前跨組觀測對的平均距離。前面零和二一組、五和九一組的例子，平均連結是六，合併後直徑卻是九。平均值的界限不能直接變成每一對距離的共同上界。

Ward 高度有另一種累積意義。每次合併，總組內平方誤差恰好增加記錄的代價。單點組的誤差為零，因此把某個合併次數切割之前的全部 Ward 代價相加，就得到該劃分的總平方誤差，可直接用來核對合併記錄。這項關係使用本節未開平方的高度；把高度逐一開平方再相加，不能還原總誤差。

選擇切割因此須先有實質問題。全連結閾值可表達組內相異度的最大容許值，Ward 切割則可按總重建誤差比較。相鄰高度出現大跳躍，表示下一次合併在所選準則下接起較分離的群組。這個解讀依賴特徵幾何與連結準則，並不是用來證明自然群組數唯一的通用檢定。

圖像分組中的特徵幾何

考慮一個圖像例子，把每個像素視為有索引的觀測。設 $I_i$ 為灰階強度，$(r_i,c_i)$ 為行列位置。可取特徵向量 $x_i=(I_i,\alpha r_i,\alpha c_i)$，其中 $\alpha\ge0$ 指定空間的相對尺度。於是

$$\|x_i-x_j\|_2^2=(I_i-I_j)^2 +\alpha^2\big((r_i-r_j)^2+(c_i-c_j)^2\big).$$

空間權重為零時，即使兩個像素在圖中相距很遠，強度接近仍可令它們分在同組。正權重則加入空間分隔的代價，其大小必須相對於強度單位解讀：若把所有強度乘以常數而不相應調整空間權重，兩者的平衡便改變。Ward 連結量度的是這個特徵空間中的平方誤差增量。

若要求分割區域在空間上連通，便須對允許合併的組對加入明確鄰接限制。單是把像素座標加入特徵，並未強制這個限制。這也呈現一般建模中的區別：特徵映射定義相似程度，允許的合併則決定算法能建立哪些劃分。比較不同切割時，兩項選擇都應保持固定。

練習

思考檢查

1. 更新平均連結

已知 $|A|=2$、$|B|=1$、$L_{\mathrm{average}}(A,C)=6$、$L_{\mathrm{average}}(B,C)=3$，求 $A\cup B$ 到 $C$ 的連結值。

解答 · 練習 1 解答

權重為 $2/3$ 和 $1/3$，故答案是 $\frac23(6)+\frac13(3)=5$。不加權平均得到的 $4.5$，讓較小群組 $B$ 佔了過大的總影響。

思考檢查

2. Ward 高度與歐氏距離

對位於零和四的兩個單點組，分別計算歐氏距離及本節高度慣例下的 Ward 合併代價。

解答 · 練習 2 解答

距離為四，而 $\Delta=(1\cdot1/2)(0-4)^2=8$。合併後平均值為二，平方誤差也是 $4+4=8$。

思考檢查

3. 高度並列時的切割

對點 $0,1,2,3$ 使用單連結。為何按合併次數可切成兩組，但水平高度閾值卻辦不到？

解答 · 練習 3 解答

三次合併的高度都是一。完成兩次合併後恰剩兩組，其成員由指定並列次序決定。閾值小於一時留下四個單點組；閾值至少為一時，整條相連的鏈合成一組。兩類水平閾值都無法給出兩組。

思考檢查

4. 分裂式細分可改變甚麼

一次分裂得到 $A$ 與 $B$，後來把 $A$ 分成 $A_1,A_2$。這一步能否把 $B$ 中一個觀測移進 $A_1$？

解答 · 練習 4 解答

不能。層次細分要求 $A_1\cup A_2=A$ 且子組不相交；從 $B$ 移入觀測會違反嵌套性。若按新中心重新分配全部觀測，則是另一種非層次更新。

相關筆記

• 中心目標與 Lloyd 更新 推導二均值切割所用的平方誤差更新。
• 密度連通與均值漂移 區分核心點連通與不受限制的單連結鏈。
• 課程書目 集中列出推薦書籍。