质心聚类用一个中心来表示一个群组。凝聚层次聚类则从每个观测各自成组开始,反复合并两个群组。它记录的是一整串相互嵌套的分组,因此建立层次结构后,我们可以按需要选取较粗或较细的划分。
在定义群组之间何谓接近之前,“合并最接近的两个群组”并不是一条完整的指令。取两组成员之间最近的一对、最远的一对,或所有跨组距离的平均值,回答的是不同问题。我们将推导这三种连接方法,追踪它们不同的合并高度,并严格证明单连接与图论之间的关系。层次结构是对所选不相似度的建模,不能据此认定所得群组就是真实世界中正确的类别。
观测与不相似度
定义 10.1.1
(有限对称不相似度)
设观测的标签为 ,其中 。假设有限数值 满足
我们允许不同观测之间的不相似度为零。这里的算法和证明不要求三角不等式成立。欧氏距离(Euclidean distance)是一种可能的输入,对称的不相似度矩阵同样足够。
簇是一个非空的观测标签集合。在每一步,当前活跃的簇构成一个划分:它们互不相交且覆盖所有观测。初始时每个簇都是单元素集合。合并操作用并集替换两个活跃簇 ,所以算法永远不会拆开已经合并的组。
我们还必须规定如何处理并列。下面的实现以簇中标签排序后的元组作为簇的键。先按这些键排列候选簇对,再从连接距离最小的候选对中,选取字典序最小的一对。对于固定标签,这使运行结果可复现,但并不意味着所有并列处理方式都会产生相同结果。
簇间距离的三种含义
定义 10.1.2
(单连接、全连接与按观测对加权的平均连接)
对不相交的非空簇 ,定义
每一步合并使所选 最小的一对簇,其连接距离称为本次合并的高度。这里的平均连接对两个簇之间的每一对观测赋予相同权重。
单连接考察两组之间是否存在一条近距离联系;全连接考察最不相似的跨组观测对有多远;平均连接则衡量跨组观测对在均匀加权下的平均距离。它们是不同的准则,而不是某个未明确指定的“接近程度”的不同实现。
反例模式
平均观测对距离不等于均值之间的距离
在一维空间中,令 、,使用通常的绝对值距离。平均连接距离是 ;而两组的均值都是零,故均值之间的距离是零。
用质心之间的距离代替平均连接会改变聚类规则。特别地,下文的单调性证明针对上面列出的三种连接方法,并不是对任意基于质心的层次聚类所作的无条件断言。
更新合并后簇的距离
假设 已被合并, 是另一个活跃簇。 与 之间的每一对观测,要么来自 与 ,要么来自 与 ,因此三种连接距离的更新如下。
引理 10.1.3
(合并后的连接更新)
设 是两两不相交的非空簇。则
证明
(把跨组观测对分成 A 与 B 两部分)
与 之间的跨组观测对,是 与 之间的跨组观测对,和 与 之间的跨组观测对的不交并。并集上的最小值或最大值,就是两部分各自最小值或最大值中较小或较大的一个,这就给出前两个公式。至于平均,所有跨组观测对的距离之和同样可以拆开,而 恰好是 与 的 个跨组观测对的 之和:
的部分同理。
例题 10.1.4
(按簇的大小为平均更新加权)
在实数轴上取 、 与 。旧的平均距离是 和 。合并 后,得 ,与直接计算三个跨组观测对 相符。若取不加权平均 ,就是让两个旧簇等权,而不是让它们的观测等权。只有两个簇大小相同,或两个旧距离相同时,两者才会一致。
为什么这些树状图的合并高度不会下降
定理 10.1.5
(合并高度不会下降)
对单连接、全连接和平均连接,合并高度的序列都不会下降。
证明
(新距离不可能低于当前最小值)
设当前最小连接距离为 ,由将被合并的那一对簇取得。其余每一对活跃簇的连接距离都至少为 。未受影响的簇对保持原值。由更新引理,到另一个簇的新距离是两个旧距离的最小值、最大值或正权重平均,而两个旧距离都至少为 ,所以新距离至少为 。
因此下一步的所有候选值都至少为 ,下一次合并的高度也至少为 。每一步重复这个论证,就得到结论。
证明透视
连接规则在单调性中的作用
这个证明完全不用数据的任何性质。它只需要一点:每个更新后的距离,都落在构成它的两个旧距离之间,或等于其中之一。这是这三种规则的性质,并非层次聚类的一般性质。质心距离就没有这个性质。在平面上用欧氏距离,取 、、。则 ,,所以 先在高度 合并。 的质心是原点,到 的距离是 ,因此下一次合并的高度比上一次更低。
树状图以叶节点表示各观测,并以位于对应高度的父节点表示每次合并。父节点包含其两个子节点中全部观测。在高度 处截断,指执行所有高度不超过 的合并,包括高度恰好等于 的全部并列合并,然后读取剩余簇。刚证明的单调性保证这是层次结构的一致截断。
要求恰好得到 个簇是另一种约定:在 次二元合并后停止。若多次合并具有相同高度,一条水平截线可能跳过某些簇数。在同一高度的并列合并中途停止,则要依照指定的二元并列次序。
例题 10.1.6
(同一组观测产生不同的合并高度)
取观测 ,令 。三种方法的第一次合并都是 与 ,距离为 1。接下来 与 合并,但高度取决于连接方法。
| 合并(显示观测值) | 单连接 | 全连接 | 平均连接 |
|---|---|---|---|
| 与 | |||
| 与 | |||
| 与 |
最后一次合并的跨组距离是 10、8、7;分别取最小值、最大值和平均值,就得到最后一行。在截断高度 处,单连接和平均连接均得到 ;全连接则仍得到 。这里表格及截断结果的花括号内显示的是观测值,而程序记录的是观测标签。
下面的互动图以三种连接规则重新计算例题点 0、2、3、10,可用来核对高度切割会执行哪些合并(包括同高度的并列),并与在固定次数的二元合并后停止作比较。
单连接等价于距离阈值下的连通性
固定 ,画一个每个观测对应一个顶点的图。当且仅当不同的 满足 时,在它们之间连边。即使两个顶点的直接不相似度超过 ,它们仍可能通过路径连通。
定理 10.1.7
(单连接截断等于阈值图的连通分量)
固定 ,设 为以观测为顶点的图,当且仅当不同的 满足 时在它们之间连边。完成所有高度不超过 的单连接合并后,各簇恰好就是 的连通分量,不论该高度的并列合并如何排序。
证明
(簇不跨越分量,分量也不会被拆开)
每个簇都包含在某一个连通分量之内。单元素簇显然成立。高度不超过 的单连接合并,连接的是两个有一对跨组观测不相似度不超过 的簇,即 的一条边;两个簇各自包含在某个分量之内,又被一条边连接,就属于同一个分量,它们的并集也是。
反过来,假设所有高度不超过 的合并都已完成,但某个连通分量仍与两个活跃簇相交。由单调性定理,这些合并是整个过程的一个开头部分,所以现在每一对活跃簇的连接距离都大于 。沿着 中连接这两个簇的一条路径前进,途中必有一条边跨越两个活跃簇,使它们的单连接距离不超过 ,这是矛盾。因此每个分量就是一个簇。
证明透视
为什么两个方向和开头部分都不可少
这个证明有两半,性质不同。前一半是归纳:高度不超过 的合并只能沿着 的边进行,所以没有簇跨越两个分量。后一半是经由路径的反证法,把关于整个分量的陈述化为关于一对相邻活跃簇的陈述。单连接是跨组观测对的最小值,只有它能由一条短边保证连接距离小;全连接则要求每一对跨组观测都近,下面的链例子表明这个结论对它并不成立。单调的合并高度只用了一次,用来知道截断停止时,剩下的每一对簇连接距离都大于 。并列合并的次序从不出现,因为两半都只谈高度。
这个定理同时解释了单连接的用途和局限:它能捕捉由相近观测组成的连通链,却不要求同一组内任意两点都相近。
反例模式
链的直径可能很大
对于实数线上使用绝对值距离的点 ,阈值为 1 的边连接相邻点。因此单连接在高度 1 就将四点全部合并,尽管两端点的距离为 3。
全连接不可能在高度不超过 1 时将四点合成一个簇。在全连接的高度 截断处,每个簇内任意两点的不相似度都不超过 :单元素簇满足这一性质,而每次最大跨簇距离不超过 的合并也会保持这一性质。平均连接没有这种直径保证:点 在高度 已合并,但其直径为 3。
层次结构诱导的新距离
定义 10.1.8
(共表型不相似度与瓶颈路径公式)
令 。对不同观测,令 为两者首次属于同一合并簇时的高度。对于上述任意一种合并高度单调的层次结构,
这称为强三角不等式。允许不同观测的不相似度为零时, 是伪超度量;若输入中所有不同观测对的不相似度均为正,则它是超度量。
为了看出不等式成立,令 。在高度 的截断划分中, 属于同一簇, 也属于同一簇,因此 必然属于同一簇。故它们共同的合并必已在高度 或更早发生。对称性和非负性直接由定义得到。
命题 10.1.9
(单连接的共表型距离是瓶颈路径值)
对单连接及不同的观测 ,
特别地,。
证明
(连接两个观测所需的最小阈值)
右边是使 中存在 到 路径的最小边阈值 。删去路径中重复顶点之间的一段,不会增加其最大边长,所以只需考虑简单路径。这种路径只有有限多条,而且直接边本身也是候选,所以最小值存在。由阈值连通性定理,完成所有高度不超过 的合并后, 属于同一簇,当且仅当它们属于 的同一个连通分量,所以最小的这种 正是它们在层次结构中首次合并的高度。只含直接边的路径也是候选,故 。对角线另按定义取 。
例题 10.1.10
(四个点的共表型距离)
对点 用单连接,合并高度为 。点 在高度 合并,所以 。点 在高度 加入 ,所以 。这与路径公式一致:路径 的边长为 和 ,最大边长是 ,小于直接距离 。最后,对 有 ,因为通向 的最短桥梁是长度为 的边 。可见 可以严格小于 ,但永不大于它。
保留合并记录的精确实现
这个教学实现接收由整数或 Fraction 值组成的方阵,并拒绝含负数、不对称或对角线非零的矩阵。每条记录为 (left_labels, right_labels, height):它同时告诉我们哪些簇合并,以及合并发生在哪个不相似度尺度;如果只记录最终包含所有观测的簇,就会丢失层次结构。
from fractions import Fraction
def agglomerative(matrix, linkage="single"):
if linkage not in ("single", "complete", "average"):
raise ValueError("choose single, complete or average linkage")
n = len(matrix)
if n == 0 or any(len(row) != n for row in matrix):
raise ValueError("a nonempty square matrix is required")
values = [[Fraction(value) for value in row] for row in matrix]
if any(values[i][i] != 0 for i in range(n)):
raise ValueError("diagonal entries must be zero")
if any(values[i][j] < 0 or values[i][j] != values[j][i]
for i in range(n) for j in range(n)):
raise ValueError("dissimilarities must be nonnegative and symmetric")
active = {i: (i,) for i in range(n)}
distances = {(i, j): values[i][j]
for i in range(n) for j in range(i + 1, n)}
records = []
next_id = n
def gap(i, j):
return distances[min(i, j), max(i, j)]
while len(active) > 1:
order = sorted(active, key=active.get)
pairs = ((i, j) for p, i in enumerate(order) for j in order[p + 1:])
i, j = min(pairs, key=lambda pair:
(gap(*pair), active[pair[0]], active[pair[1]]))
left, right = active[i], active[j]
height = gap(i, j)
for c in active:
if c == i or c == j:
continue
first, second = gap(i, c), gap(j, c)
if linkage == "single":
updated = min(first, second)
elif linkage == "complete":
updated = max(first, second)
else:
updated = (len(left) * first + len(right) * second) / (len(left) + len(right))
distances[c, next_id] = updated
records.append((left, right, height))
del active[i], active[j]
active[next_id] = tuple(sorted(left + right))
next_id += 1
return records
取 points = [0, 2, 3, 10],构造 matrix = [[abs(x-y) for y in points] for x in points]。每种方法首先记录 ((1,), (2,), Fraction(1))。单连接、全连接和平均连接的高度序列分别是 (1,2,7)、(1,3,10)、(1,5/2,25/3)。只有一个观测的矩阵不会产生合并记录;非对角元素为零则会产生合法的零高度合并。
这个直接实现每一步都扫描剩余的所有簇对,共需 次比较和算术运算,并存储 个距离。精确有理数运算还涉及分子和分母的位数成本,因此这里统计的是运算次数,并不是假设位数固定的运行时间。存在更快的专门算法;此处的目的是展示连接距离在更新时保持的规则,并保留精确的例子。
结果仍取决于输入的不相似度。例如,在计算欧氏距离前改变某个特征的计量单位,就可能改变合并的选择。低合并高度也不能证明因果解释、类别标签正确,或其他全局聚类目标达到最优。
练习与详细解答
快速检查
(对观测 ,已形成簇 。计算它到点 的三种连接距离,以及随后簇 到点 的三种连接距离。)
要用到每一对跨组观测的距离,而不是组均值之间的距离。
解答 · 答案
第一批跨组距离为 2 和 3,所以单连接为 2、全连接为 3、平均连接为 。随后的跨组距离为 10、8 和 7,所以单连接为 7、全连接为 10、平均连接为 。这些是所有跨组观测对的统计量,而不只是组均值之间的距离。
快速检查
(合并簇 与 ,另有 。分别用更新公式和直接计算求新簇到 的平均连接,并说明两个旧连接距离的不加权平均会得到什么。)
数一数每个旧簇提供多少个观测。
解答 · 答案
旧连接距离为 与 ,且 、。更新公式给出 。直接计算,三个跨组距离是 ,平均值同样是 。不加权的 让两个旧簇等权,定义的是另一种规则。
快速检查
(对点 使用单连接,高度一的截断得到什么划分?只完成两次二元合并就停止,结果是否相同?)
记住高度截断会执行该高度的每一次合并。
解答 · 答案
四点在阈值一的图中同属一个连通分量,所以高度一截断只有一个簇。完成三次二元合并中的两次就停止,确实剩下两个簇,但那是在同高度合并中途按指定簇数停止,并不是所定义的高度一截断。该高度的三次合并必须全部执行。
快速检查
(为什么单连接能在高度一把链 合成一簇,全连接却不能?再给出平均连接的例子,说明在高度 形成的簇,直径可以大于 。)
比较各种连接所限制的是什么。
解答 · 答案
相邻链边的长度为一,所以单连接能经中间点把两端连起来,即使两端的直接距离为三。全连接在每次合并限制所有跨组观测对,因此在截断高度也限制所有簇内观测对,不能在高度一纳入两端。平均连接下, 在高度 合并,但直径为三。
快速检查
(对链 ,求两端的单连接共表型距离。为什么它不会大于原来的两端距离?若两个不同观测可以具有零距离,应使用什么术语?)
使用瓶颈路径公式。
解答 · 答案
沿相邻边前进的路径,其最大边长是一;不可能只用短于一的边连接不同链顶点,所以答案是一。一般而言,直接边是一条候选路径,故 。不同观测若在零高度合并,可能有 ,所以最一般的术语是伪超度量。输入中非对角线距离严格为正时,才得到超度量。
快速检查
(对点 使用全连接,比较先合并并列的簇对 与先合并 。各自在高度一有什么划分?哪一个单连接结论不依赖这些选择?)
先算出第一次合并后的全连接距离。
解答 · 答案
若先合并 , 也可在高度一合并,得到这两对。若先合并 ,它到 0 和 3 的全连接距离均为二,而 ,所以高度一的划分是 。重新标号可能使字典序并列规则选到不同的第一对;固定标号时可重现,不等于重新标号后仍然不变。对单连接,完成所有高度一合并后,划分永远是阈值图的连通分量,在此例就是一个簇。