為何衡量合併代價?
凝聚式層次聚類由每個觀測各自成組開始,逐步合併兩組。單連結看跨組最近的兩個觀測;Ward 方法則問:將兩組各自的平均值換成一個共同平均值,最小組內平方誤差會增加多少?它與 k-means 使用相同的平方誤差,但搜索的劃分並不相同。Ward 一旦合併便不會再次拆分。
定義 23.1.1
(組內誤差與 Ward 合併代價)
設 是固定的非空有限樣本,使用歐氏(Euclidean)距離且每個觀測權重相同。對非空指標集 ,記 、,並以 表示它的組內平方誤差。對不相交的非空組 ,Ward 合併代價為
Ward 方法每次合併目前各組中合併代價最小的一對。
相同代價需要預先規定平局規則。繪製樹狀圖時應註明實際顯示的高度:不同軟件可能對增量作不同縮放。
定理 23.1.2
(Ward 合併恆等式)
對不相交的非空組 ,
因此合併代價非負,除了平均值距離,組大小也起作用。
證明
(圍繞各組平均值分解偏差)
令 。展開 ,再對 求和。因為 ,交叉項消失,所以 ; 也有相同結論。把兩式相加,得 ,故
由 ,兩個偏移分別為 和 。代入得
重複觀測也適用;不同組的平均值相等時,合併代價可以為零。
證明透視
合併恆等式的證明依賴甚麼
兩個事實承擔了全部工作。交叉項會消失,只因每組都以自己的平均值為中心,此時 ;若圍繞其他中心分解,便會多出一個線性項。其後的偏移由加權平均值 決定: 把兩個平均值之間的線段,從 起按 的比例分開。把 除以 ,就得到「乘積除以和」的權重。這裏用到各觀測權重相同;若權重不同,每個 要換成總權重。維數 不起作用,非負性及等號成立的情形(平均值相等)在最後一步直接看出。
這個恆等式也讓我們在合併之後不必重新計算平均值。
命題 23.1.3
(合併後的代價更新)
對兩兩不相交的非空組 ,其大小為 ,
證明
(圍繞合併組自己的平均值分拆)
以 表示 的平均值, 為 的平均值。展開 與 ,交叉項合起來是 ,因為 是加權平均值。所以
其中最後一項就是上一個證明中得到的式子。兩邊乘以 。對 與 用合併恆等式,;同樣 、。代入並除以 即得結論。
因此每次合併之後,到其餘各組的代價都可由三個已儲存的數算出,不必回頭使用數據。
完整算例
例題 23.1.4
(四個一維觀測)
取 。單元素組的合併代價是距離平方的一半,最小的是 。新組大小為二、平均值為 。它與 合併的代價為 ,與 合併的代價為 ;餘下兩個單元素組的代價為 50。因此第二次合併得到 ,總組內誤差為 。此組平均值為 ,與 的合併代價為 。最後誤差是 ,也可用總平均值 直接計算。按此約定,三次合併代價依次為 。
更新公式不需任何新的平均值,就能重現第二步。取 、、,單元素代價為 、、,所以 。若 ,代價為 與 ,得 。
概念視角結構
Ward 代價就是損失的組間散佈
總散佈 與分割方式無關。對於分成各組 的分割,,即組內部分加組間部分。合併使組內部分增加 ,所以組間部分恰好減少 。因此 Ward 方法每一步損失的組間散佈最少。在四點例子中,單點分割的組間部分是 ,三個代價 的總和正好等於它。
例題 23.1.5
(二維情形與平局)
取長方形的四個頂點 、、、。單元素代價是距離平方的一半:每個豎直對為 ,每個水平對為 ,每個對角對為 。兩個豎直對同為 ,出現平局。設平局規則先合併左邊一對,其平均值為 。它與其餘單元素的代價各為 ,而右邊豎直對仍只需 ,所以第二次合併形成右邊一對,平均值為 。第三次合併代價為 。三次合併代價為 ,最後誤差為 。總平均值是 ,每個頂點的平方偏差為 ,直接計算同樣得 。第一次平局若反過來處理,這裏得到相同的層次,因為另一個豎直對隨後是唯一最便宜的合併。
例題 23.1.6
(重複觀測可免費合併)
取樣本 。兩個 的平均值之差為零,所以 ,而合併 與 的代價為 。因此第一次合併不費分毫,得 。再與 合併,代價為 ,這就是最後誤差。直接計算:總平均值為 ,平方偏差為 ,和為 。合併代價為零是恆等式的邊界情形:它只表示平均值相等,並不表示先前沒有誤差。
反例模式
最近的點未必對應最小合併代價
設目前各組為 、、。單連結最小距離是一,來自 ;Ward 合併它們的代價卻是 ,而合併 的代價是 ,故 Ward 選擇後者。此處只用這些合法的目前各組比較規則,並不聲稱它們由 Ward 的先前步驟產生。只看最近的兩個點不足以確定 Ward 的選擇。
常見錯誤
常見錯誤
(小的合併代價不保證真實群體結構)
結果依賴樣本、特徵尺度和距離。平方距離使離群值及單位較大的座標影響顯著。單位任意時標準化可能合理,但它改變目標;若聚類用於預測流程,標準化參數應只由訓練數據擬合。選擇樹的切割位置仍是建模決定,並不證明存在唯一真實組數。
常見錯誤
(在某層切開層次,不等於得到該組數的最佳劃分)
恆等式在每一階段只挑出目前各組之間最便宜的下一次合併。它沒有比較所有組數減一的劃分,因為其中大多數不能由目前兩組合併得到,所以總誤差單調上升並不能說明最優性。以觀測 為例,各對 的單元素代價是 ,因此 Ward 先合併 。把 與 合併的代價是 ,與 合併是 , 與 合併是 ,所以得到 ,誤差為 。劃分 的誤差是 ,卻永遠不會出現在這個層次中,因為 與 已經合在一起。
練習與解答
快速檢查
(對 和 ,求各自組內誤差、合併增量及合併後的總誤差。)
先求兩組的平均值。
解答 · 答案
平均值為 2 和 7,各組誤差都是 。合併增量為 ,所以總誤差為 。直接用合併後的平均值 計算四個平方偏差,也得 41。
快速檢查
(兩組平均值相等,是否意味著組內所有觀測都相同?請解釋。)
找兩組平均值相同、但觀測分散的例子。
解答 · 答案
不意味著。例如 和 的平均值均為零,合併代價為零,但各組原本都有正的誤差。Ward 衡量用一個平均值替換兩個平均值所增加的誤差,而不是原有誤差。
快速檢查
(每個座標都乘以 3,合併代價變為多少倍?合併次序必然改變嗎?)
留意平均值之間的距離會怎樣變。
解答 · 答案
平均值差乘以三,代價因此乘以九。精確計算下嚴格次序和相等關係都保留,使用相同確定性平局規則便保留合併序列;分別縮放不同座標則可能改變次序。
快速檢查
(用更新公式,由三個單元素代價求合併 與 的代價,並直接驗算。)
取 、、。
解答 · 答案
單元素代價為 、、。公式給出 。直接計算: 的平均值為 、大小為 ,所以代價為 。