為甚麼建立階層?
聚類不一定要預先指定群數。由個別觀測開始,逐步合併接近的群,我們便得到一系列互相嵌套的劃分。樹狀圖記錄合併的順序及距離,讓人比較不同粗細程度;但它只概括所選距離,並不能證明自然界必然有某個群數。改變特徵尺度或距離定義,可能改變整棵樹。
定義與算法
定義 22.1.1
(凝聚與連結距離)
設 為有限非空數據集,差異度 對稱、非負,且 。不同觀測之間的差異度可以為零,這裏亦不要求三角不等式。先把每個觀測各自放進一個群。對非空且不相交的群 ,定義
前者為單連結,後者為完全連結。每一步選擇連結距離最小的一對群合併,把該值記為合併高度,然後重新計算新群與其他群的距離;直至只剩一群。遇到並列時應說明確定的處理規則;不同的並列二叉樹在同一高度可以表示同一個劃分。
未改變的群之間的距離保持不變。若 ,而 是另一群,則
把 到 的點對按起點屬於 或 分開,即得這兩式,無需計算群中心。
定義 22.1.2
(樹狀圖與水平切割)
一次運行的樹狀圖是其合併所成的二叉樹,每次合併畫在它的合併高度上。高度 的水平切割是這樣得到的劃分:執行所有高度不大於 的合併(包括高度剛好等於 的所有並列合併),其餘不執行。
命題 22.1.3
(合併高度不會下降)
對單連結與完全連結,相繼的合併高度構成非遞減數列。因此高度 的切割有明確定義:高度不大於 的合併恰是整個運行的一個起始段。
證明
(為何之後的距離都不低於上次合併高度)
設 與 在高度 合併, 是當前所有群間距離的最小值。合併前,任意兩個當前群之間的距離都至少為 。合併後,未改變的群之間的距離仍至少為 ;每個新距離是兩個舊距離的最小值或最大值,而這兩個舊距離都至少為 ,所以新距離也至少為 。因此下一步可用的距離都至少為 ,下一次合併高度不小於 。
單連結的圖論定理
定理 22.1.4
(門檻圖的連通分支)
固定 。以觀測為頂點,當且僅當 時連接 。單連結完成所有高度不大於 的合併後,其群恰好是這圖的連通分支,與並列處理次序無關。
證明
(證明兩個包含關係)
每次高度不大於 的單連結合併,都有一條門檻圖的邊連接兩個舊群。由歸納法,每個產生的群都包含於某個連通分支。反過來,當沒有這類合併剩下時,若兩個不同群之間有一條邊,其單連結距離便不大於 ,矛盾。因此圖中任何路徑的每對相鄰頂點都在同一群,整個連通分支也在同一群。兩個包含關係證得結論。
證明透視
連鎖現象從何而來
定理用的是路徑,而非所有點對都接近:即使每條邊都短,路徑兩端仍可能很遠。完全連結在每次合併時控制最大的跨群距離,回答的是另一個問題。一般而言,單憑門檻圖不能重建完全連結的劃分。
算例
例題 22.1.5
(四個點上的單連結與完全連結)
考慮數軸上的 ,距離取絕對差。唯一的第一次合併為 ,高度是 。單連結下, 到 和 的距離分別是 ,而 到 的距離為 ;故接著在高度 合併 ,最後在高度 合併 。完全連結下相應距離是 ;因此在高度 合併 ,最後在高度 合併 。在 切開,單連結得到 和 ;完全連結則得到 、 和 。同一數據的結果可以不同,因為連結規則本身也是建模選擇。
例題 22.1.6
(零差異度與高度零的切割)
取數軸上的 ,距離為絕對差;前兩個觀測是不同的觀測,但差異度為零。它們在高度 合併,所以兩種連結在 的切割都是 , 的門檻圖有相同的連通分支。無論哪種連結, 到 與 的距離都是 與 ,而 ,所以 與 在高度 合併。最後一次合併不同:單連結取 ,完全連結取 。因此在 切開,單連結得到一個群,完全連結則得到 。零是合法的合併高度,高度零的切割也不一定是全部單點群的劃分。
例題 22.1.7
(對完全連結有影響、對單連結沒有影響的並列)
取 ,距離為絕對差。 與 兩對同在距離 並列。單連結下,無論先做哪一次合併,另一個並列的對仍在距離 :例如 。因此兩次合併都在高度 ,無論次序如何, 的切割都是 ,與門檻圖定理一致。完全連結下,先合併 得 ;先合併 則 。於是 的切割是 還是 ,取決於並列規則,而 的切割兩種情況都是一個群。所以完全連結在並列高度的結果,只有明確說明並列規則才能重現。
反例模式
連成一條鏈不代表群內緊密
對數軸上的 ,門檻為 時單連結產生一群,因為邊 –、–、– 形成路徑。但該群直徑是 ,不是 。所以切割高度限制的是連通所需的邊,而不是群內所有點對的距離。相反,完全連結在非負高度切割後的每群直徑都不超過切割高度;可利用每次合併的最大跨群距離作歸納證明。
如何使用樹狀圖
樹狀圖與解讀它的數據來自同一個樣本。垂直方向的大空隙可以提示值得研究的切割位置,但本身不能建立統計顯著性,也不能保證新數據上的表現。不同變量的單位不同時,標準化可能有幫助,卻也可能抹去有意義的尺度。計算距離前須明確處理缺失值。舊樹不會自動安置新觀測;重新計算整個階層甚至可能改變先前合併。大型數據的兩兩距離矩陣需要平方級儲存空間,除非實現方式明確利用額外結構,不能假設這成本消失。
概念視角組合
把單連結看成最小生成樹
單連結的合併高度,恰好是以 為權的完全圖的最小生成樹的邊權,按由小到大排列:每次合併都加入連接兩個現有群的最便宜的邊。對 ,這棵樹的邊是 –、–、–,權為 ,正是上面求得的合併高度。
常見錯誤
(葉子由左至右的次序不含距離資訊)
交換任何一次合併的兩個子樹,得到的是同一棵樹的另一種畫法。以 的單連結為例,葉子可以按 的次序畫出;交換最後一次合併的兩個子樹後,則是 。在後一種畫法中, 緊鄰 ,但 是最大的差異度。有意義的只是兩個觀測第一次落在同一群的高度,而不是它們的葉子畫得多近。
練習
快速檢查
(數軸上有 ,距離為絕對差。求完全連結的合併高度及在 切開的群。)
先算出全部六個兩兩距離。
解答 · 答案
先在高度 合併 。 至 的完全連結距離分別為 ,而 ,故在高度 合併 。兩對之間的最大跨群距離為 ,即最後高度。在 切開得 和 。
練習 22.1.8
(對上述差異度及 ,證明完全連結在 切開所得每群直徑不大於 。)
核心證明
提示(1)
對高度不大於 的合併作歸納,並把合併後群內的點對分開處理。
解答(3)
- 1
以單點群開始歸納
單點群的直徑為 ,因為 。
- 2
控制合併時的跨群距離
若 與 在高度 合併,則對所有 、 有 。由歸納假設, 內及 內的點對距離也不大於 。
依據: 完全連結的合併高度等於最大跨群距離。
- 3
得出合併後群的結論
∎中任意兩點要麼同在 ,要麼同在 ,要麼各在一邊,每種情況下距離都不大於 。切割只包含高度不大於 的合併,所以切割中每個群的直徑都不大於 。
快速檢查
(四個觀測的非對角差異度全為 。單連結的並列處理會否改變 及 的劃分?)
與門檻圖比較。
解答 · 答案
低於 時是四個單點群;在 或以上時是同一群。並列的二叉合併次序可以不同,但門檻為 的圖是完全圖,故連通分支劃分唯一。