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 更新 推导二均值切割所用的平方误差更新。
• 密度连通与均值漂移 区分核心点连通与不受限制的单连接链。
• 课程书目 集中列出推荐书籍。