为什么建立层次?
聚类不一定要预先指定群数。由单个观测开始,逐步合并接近的群,我们便得到一系列互相嵌套的划分。树状图记录合并的顺序及距离,让人比较不同粗细程度;但它只概括所选距离,并不能证明自然界必然有某个群数。改变特征尺度或距离定义,可能改变整棵树。
定义与算法
定义 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
得出合并后群的结论
∎中任意两点要么同在 ,要么同在 ,要么各在一边,每种情况下距离都不大于 。切割只包含高度不大于 的合并,所以切割中每个群的直径都不大于 。
快速检查
(四个观测的非对角相异度全为 。单连接的并列处理会否改变 及 的划分?)
与阈值图比较。
解答 · 答案
低于 时是四个单点群;在 或以上时是同一群。并列的二叉合并次序可以不同,但阈值为 的图是完全图,故连通分支划分唯一。