为什么衡量合并代价?
凝聚式层次聚类从每个观测各自成组开始,逐步合并两组。单链接看跨组最近的两个观测;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,合并代价变为多少倍?合并次序必然改变吗?)
注意均值之间的距离会怎样变。
解答 · 答案
均值之差乘以三,代价因此乘以九。精确计算下严格次序和相等关系都保留,使用相同的确定性平局规则便保留合并序列;分别缩放不同坐标则可能改变次序。
快速检查
(用更新公式,由三个单元素代价求合并 与 的代价,并直接验算。)
取 、、。
解答 · 答案
单元素代价为 、、。公式给出 。直接计算: 的均值为 、大小为 ,所以代价为 。