質心聚類用一個中心代表一組觀察值。階層式凝聚聚類則先讓每個觀察值各自成組,再反覆把兩組合併。它記錄一整串互相嵌套的分組,所以建好階層後,我們可以再選擇較粗或較細的劃分。
不過,「合併最近的兩組」還不是完整指示:必須先定義兩組之間的遠近。最接近的一對成員、最遠的一對成員,以及所有跨組距離的平均值,回答的是不同問題。本節會推導這三種連結準則,追蹤它們不同的合併高度,並證明單連結的精確圖論解釋。階層反映的是所選相異度模型,並不證明所得分組就是真實世界的正確標籤。
從觀察值與相異度開始
定義 10.1.1
(有限的對稱相異度)
觀察值的標號為 ,其中 。假設有限數值 滿足
不同觀察值之間的相異度可以是零。以下算法及證明不要求三角不等式。歐氏距離(Euclidean distance)是一種可用輸入,但只要給出對稱相異度矩陣,也足以進行聚類。
一個群組是觀察值標號的非空集合。每一階段的現有群組都構成劃分:它們互不相交,並覆蓋所有觀察值。初始群組都是單元素集合。每次合併以聯集取代兩個現有群組 ,所以算法永不拆開較早形成的群組。
平手情況也要有明確規則。以下實作以群組標號排序後的元組作為鍵值。先按這些鍵值排列候選群組對,再在連結值最小的群組對中選字典序最小的一對。固定標號後,這使執行結果可重現,但不表示所有平手處理方法都等價。
群組距離的三種含義
定義 10.1.2
(單連結、全連結與按觀察值配對平均的連結)
對互不相交的非空群組 ,定義
每一步都合併使所選 最小的一對群組。該連結值就是這次合併的高度。這裏的平均連結,是讓跨越兩組的每一對觀察值都有相同權重。
單連結問兩組之間是否有一條接近的連接;全連結問最不相似的跨組配對有多遠;平均連結則在均勻配對權重下衡量典型跨組距離。它們是不同準則,而不是某種尚未說清楚的「接近」概念的不同實作。
反例模式
配對距離的平均不是均值之間的距離
在一維中取群組 及 ,並用一般絕對距離。平均連結為 。兩組的均值卻同為零,所以均值之間的距離是零。
把平均連結換成質心距離,就是換了一種聚類規則。尤其以下單調性證明只適用於所列的三種連結,並不是聲稱所有以質心建立的階層都具有相同性質。
更新合併後群組的距離
假設 合併,而 是另一個現有群組。 與 之間的所有跨組配對,都來自 或 ,因此三種連結的更新如下。
引理 10.1.3
(合併後的連結更新)
設 是兩兩不相交的非空群組。則
證明
(把跨組配對分成 A 與 B 兩部分)
與 之間的跨組配對,是 與 之間的跨組配對,和 與 之間的跨組配對的不交併。並集上的最小值或最大值,就是兩部分各自最小值或最大值中較小或較大的一個,這就給出前兩條公式。至於平均,所有跨組配對的距離之和同樣可以拆開,而 恰好是 與 的 個跨組配對的 之和:
的部分同理。
例題 10.1.4
(按群組大小為平均更新加權)
在實數線上取 、 及 。舊平均距離是 和 。合併 後,得 ,與直接計算三個跨組配對 相符。若取不加權平均 ,便是把兩個舊群組等權處理,而不是把它們的觀察值等權處理。只有兩個群組大小相同,或兩個舊距離相同時,兩者才會一致。
為甚麼這些樹狀圖的合併高度不會下降
定理 10.1.5
(合併高度不會下降)
對單連結、全連結及平均連結,合併高度的序列都不會下降。
證明
(新距離不可能低於當前最小值)
假設當前最小連結值是 ,而將被合併的一對群組取得這個值。其他每一對現有群組的連結值都至少為 。沒有受影響的群組對保留原值。由更新引理,到另一個群組的新距離是兩個舊距離的最小值、最大值或正權重平均,而兩個舊距離都至少為 ,所以新距離至少為 。
因此,下一步的所有候選值都至少為 ,下一次合併的高度也至少為 。每一步重複這個論證,就得到結論。
證明透視
連結規則在單調性中的作用
這個證明完全不用數據的任何性質。它只需要一點:每個更新後的距離,都落在建立它的兩個舊距離之間,或等於其中之一。這是這三種規則的性質,並非階層聚類的一般性質。質心距離就沒有這個性質。在平面上用歐氏距離,取 、、。則 ,,所以 先在高度 合併。 的質心是原點,到 的距離是 ,因此下一次合併的高度比上一次更低。
樹狀圖把每個觀察值畫成葉節點,每次合併則畫成位於所記高度的父節點。父節點包含兩個子節點的觀察值聯集。高度切割 指完成所有高度不大於 的合併,包括高度恰為 的全部平手合併,再讀取剩下的群組。剛才證明的單調性,讓這種切割與階層一致。
要求恰好 組是另一種約定:在 次二元合併後停止。若多次合併具有同一高度,水平高度切割可能跳過某些群組數。若在一批同高度合併中途停止,就使用了指定的二元平手次序。
例題 10.1.6
(同一批觀察值可有不同的合併高度)
取觀察值 ,以及 。三種規則首先都在距離一,把 與 合併。下一步都把 與 合併,但高度取決於連結準則。
| 合併,以觀察值表示 | 單連結 | 全連結 | 平均連結 |
|---|---|---|---|
| 與 | |||
| 與 | |||
| 與 |
最後一次合併的跨組距離為 10、8 和 7。分別取最小值、最大值和平均值,就得到最後一行。在高度 切割時,單連結和平均連結的群組為 ;全連結仍有 。表格及此處切割描述的大括號內是觀察值;實作記錄的則是它們的標號。
下面的互動圖以三種連結規則重新計算例題點 0、2、3、10,可用來核對高度切割會執行哪些合併(包括同高度的平手),並與在固定次數的二元合併後停止作比較。
單連結就是距離閾值下的連通性
固定 ,以每個觀察值作為一個圖頂點。當且僅當不同的 滿足 ,才在它們之間加邊。即使兩頂點的直接相異度大於 ,一條路徑仍然可能把它們連起來。
定理 10.1.7
(單連結切割等於閾值圖的連通分量)
固定 ,設 為以觀察值為頂點的圖,當且僅當不同的 滿足 時在它們之間加邊。完成所有高度不大於 的單連結合併後,群組恰好就是 的連通分量,不論該高度的平手合併如何排序。
證明
(群組不跨越分量,分量也不會被拆開)
每個群組都包含在某一個連通分量之內。單元素組顯然成立。高度不大於 的單連結合併,連接的是兩個有一對跨組配對相異度不大於 的群組,亦即 的一條邊;兩個群組各自包含在某個分量之內,又被一條邊連接,就屬於同一個分量,它們的聯集也是。
反過來,假設所有高度不大於 的合併都已完成,但某個連通分量仍與兩個現有群組相交。由單調性定理,這些合併是整個過程的一個開頭部分,所以現有群組的每一對連結值都大於 。沿著 中連接這兩個群組的一條路徑前進,途中必有一條邊跨越兩個現有群組,令它們的單連結值不大於 ,這是矛盾。因此每個分量就是一個群組。
證明透視
為甚麼兩個方向和開頭部分都不可少
這個證明有兩半,性質不同。前一半是歸納:高度不大於 的合併只能沿著 的邊進行,所以沒有群組跨越兩個分量。後一半是經由路徑的矛盾法,把關於整個分量的陳述化為關於一對相鄰現有群組的陳述。單連結是跨組配對的最小值,只有它能由一條短邊保證連結值小;全連結則要求每一對跨組配對都短,下面的鏈例子顯示這個結論對它並不成立。單調的合併高度只用了一次,用來知道切割停止時,剩下的每一對群組連結值都大於 。平手合併的次序從不出現,因為兩半都只談高度。
這個定理同時解釋單連結的用途與限制。它能捕捉由鄰近觀察值接成的連通鏈,但不要求同一組內每一對觀察值都彼此接近。
反例模式
一條鏈的直徑可以很大
對絕對距離下的點 ,閾值一的邊連接相鄰點。因此,單連結到高度一就會把四點全部合成一組,儘管兩端的距離是三。
全連結不可能在高度一把四點全部放進同一組。在全連結切割 下,每組內任意一對的相異度都不大於 :單元素組顯然成立,而每次最大跨組距離不大於 的合併也保留這個性質。平均連結沒有這個直徑保證;三點 已在高度 合併,但直徑為三。
階層會誘導一個新的距離
定義 10.1.8
(共表型相異度與瓶頸路徑公式)
設 。對不同觀察值,以 表示它們首次同屬一個合併群組的高度。對上述三種單調階層,均有
這是強三角不等式。若容許不同觀察值的相異度為零, 是偽超度量;若輸入中所有不同觀察值對的相異度均嚴格為正,它就是超度量。
證明時,取 。在高度 的劃分中,同一個群組包含 ,也包含 ,因此必包含 。它們共同合併的時間必已在高度 或以下發生。對稱性和非負性則直接來自定義。
命題 10.1.9
(單連結的共表型距離是瓶頸路徑值)
對單連結及不同的觀察值 ,
特別地,。
證明
(連接兩個觀察值所需的最小閾值)
右邊是讓 中存在 到 路徑的最小邊閾值 。刪去路徑中重複頂點之間的一段,不會增加其最大邊長,所以只須考慮簡單路徑。這種路徑只有有限多條,而且直接邊本身也是候選,所以最小值存在。由閾值連通性定理,完成所有高度不大於 的合併後, 同屬一個群組,當且僅當它們同屬 的一個連通分量,所以最小的這種 正是它們在階層中首次合組的高度。只含直接邊的路徑也是候選,故 。對角線另按定義取 。
例題 10.1.10
(四個點的共表型距離)
對點 用單連結,合併高度為 。點 在高度 合併,所以 。點 在高度 加入 ,所以 。這與路徑公式一致:路徑 的邊長為 和 ,最大邊長是 ,小於直接距離 。最後,對 有 ,因為通往 的最短橋樑是長度為 的邊 。可見 可以嚴格小於 ,卻永不大於它。
保留合併記錄的精確實作
以下教學實作接受由整數或 Fraction 值組成的方陣,並拒絕負值、非對稱或對角線不為零的矩陣。每項記錄為 (left_labels, right_labels, height),同時說明甚麼群組合併,以及合併發生的相異度尺度。若只記錄最後包含全部觀察值的大群組,就會失去階層資訊。
from fractions import Fraction
def agglomerative(matrix, linkage="single"):
if linkage not in ("single", "complete", "average"):
raise ValueError("choose single, complete or average linkage")
n = len(matrix)
if n == 0 or any(len(row) != n for row in matrix):
raise ValueError("a nonempty square matrix is required")
values = [[Fraction(value) for value in row] for row in matrix]
if any(values[i][i] != 0 for i in range(n)):
raise ValueError("diagonal entries must be zero")
if any(values[i][j] < 0 or values[i][j] != values[j][i]
for i in range(n) for j in range(n)):
raise ValueError("dissimilarities must be nonnegative and symmetric")
active = {i: (i,) for i in range(n)}
distances = {(i, j): values[i][j]
for i in range(n) for j in range(i + 1, n)}
records = []
next_id = n
def gap(i, j):
return distances[min(i, j), max(i, j)]
while len(active) > 1:
order = sorted(active, key=active.get)
pairs = ((i, j) for p, i in enumerate(order) for j in order[p + 1:])
i, j = min(pairs, key=lambda pair:
(gap(*pair), active[pair[0]], active[pair[1]]))
left, right = active[i], active[j]
height = gap(i, j)
for c in active:
if c == i or c == j:
continue
first, second = gap(i, c), gap(j, c)
if linkage == "single":
updated = min(first, second)
elif linkage == "complete":
updated = max(first, second)
else:
updated = (len(left) * first + len(right) * second) / (len(left) + len(right))
distances[c, next_id] = updated
records.append((left, right, height))
del active[i], active[j]
active[next_id] = tuple(sorted(left + right))
next_id += 1
return records
取 points = [0, 2, 3, 10],建立 matrix = [[abs(x-y) for y in points] for x in points]。每種規則首先都記錄 ((1,), (2,), Fraction(1))。單連結、全連結和平均連結的高度序列分別為 (1,2,7)、(1,3,10) 和 (1,5/2,25/3)。只有一個觀察值的矩陣不產生合併記錄;非對角線的零值則可產生合法的零高度合併。
這個直接實作每一步都掃描所有剩餘群組對,因此有 次比較及算術操作,並儲存 個距離。精確有理數運算還有分子、分母位元長度的成本,所以這是操作次數,而不是假定數值只佔固定數目位元的執行時間聲稱。專門算法可以更快;這裏的目的是展示連結不變量,並保留例題的精確值。
結果仍然依賴輸入相異度。在計算歐氏距離前,若改變其中一個特徵的單位,就可能改變合併選擇。合併高度低,也不代表已建立因果解釋、正確分類標籤,或另一個整體聚類目標的最優解。
練習與詳解
快速檢查
(對觀察值 ,已形成群組 。求它到點 的三種連結,再求稍後群組 到點 的三種連結。)
要用到每一對跨組配對的距離,而不是組均值之間的距離。
解答 · 答案
第一批跨組距離為 2 和 3,所以單連結為 2、全連結為 3、平均連結為 。稍後的跨組距離為 10、8 和 7,所以單連結為 7、全連結為 10、平均連結為 。這些是所有跨組配對的統計量,而不只是組均值之間的距離。
快速檢查
(合併群組 與 ,另有 。分別用更新公式和直接計算求新群組到 的平均連結,並說明兩個舊連結的不加權平均會得到甚麼。)
數一數每個舊群組提供多少個觀察值。
解答 · 答案
舊連結為 及 ,且 、。更新公式給出 。直接計算,三個跨組距離是 ,平均值同樣是 。不加權的 把兩個舊群組等權處理,定義的是另一種規則。
快速檢查
(對點 使用單連結,高度一的切割得到甚麼劃分?只完成兩次二元合併就停止,結果是否相同?)
記得高度切割會執行該高度的每一次合併。
解答 · 答案
四點在閾值一的圖中同屬一個連通分量,所以高度一切割只有一組。完成三次二元合併中的兩次就停止,的確剩下兩組,但那是在同高度合併中途按指定群組數停止,並不是所定義的高度一切割。該高度的三次合併必須全部納入。
快速檢查
(為甚麼單連結能在高度一把鏈 合成一組,全連結卻不能?再給出平均連結的例子,說明在高度 形成的群組,直徑可以大於 。)
比較各種連結所限制的是甚麼。
解答 · 答案
相鄰鏈邊的長度為一,所以單連結能經中間點把兩端連起來,即使兩端的直接距離為三。全連結在每次合併限制所有跨組配對,因此在切割高度也限制所有組內配對,不能在高度一納入兩端。平均連結下, 在高度 合併,但直徑為三。
快速檢查
(對鏈 ,求兩端的單連結共表型距離。為甚麼它不會大於原來的兩端距離?若兩個不同觀察值可以具有零距離,應使用甚麼術語?)
使用瓶頸路徑公式。
解答 · 答案
沿相鄰邊前進的路徑,其最大邊長是一;不可能只用短於一的邊連接不同鏈頂點,所以答案是一。一般而言,直接邊是一條候選路徑,故 。不同觀察值若在零高度合併,可能有 ,所以最一般的術語是偽超度量。輸入中非對角線距離嚴格為正時,才得到超度量。
快速檢查
(對點 使用全連結,比較先合併平手群組對 與先合併 。各自在高度一有甚麼劃分?哪一個單連結結論不依賴這些選擇?)
先算出第一次合併後的全連結距離。
解答 · 答案
若先合併 , 也可在高度一合併,得到這兩對。若先合併 ,它到 0 和 3 的全連結距離均為二,而 ,所以高度一的劃分是 。重新標號可能使字典序平手規則選到不同的第一對;固定標號時可重現,不等於重新標號後仍然不變。對單連結,完成所有高度一合併後,劃分永遠是閾值圖的連通分量,在此例就是一組。