不预先选定粒度，样本怎样长成一棵簇树？层次聚类的 linkage 与树状图

上一篇的 DBSCAN 用一组 eps/min_samples 切出密度连通簇。但商品目录可能同时有“食品—饮料—无糖饮料”三层结构，用户分群也可能既需要 3 个大类，又需要 12 个细分群。一次只给一组扁平标签，会丢掉这些嵌套关系。

凝聚层次聚类（Agglomerative Hierarchical Clustering）先把每个样本看成一个簇，再反复合并最接近的两个簇，形成一棵树。本文只讲透三个环节：簇间距离 linkage、逐步合并，以及如何切树得到不同粒度。

01 为什么一组标签不够？#

扁平聚类只回答“现在分几组”，层次结构还记录“哪些小组先组成大组”：

样本层          局部小组             全部样本

A   B   C   D     {A,B}   {C,D}       {A,B,C,D}
│   │   │   │       \       /             │
└─1─┘   └─2─┘        \─4.5─/              根

在高度 1.5 切：{A,B}, {C}, {D}
在高度 3.0 切：{A,B}, {C,D}

text

树状图（Dendrogram）的叶子是样本，内部节点是一次合并，纵轴通常是本次合并的距离或代价。它保存了从 $N$ 个单点簇到 1 个总簇的全部嵌套过程；最终标签只是选择一条水平切线后的结果。

02 算法每一轮究竟比较什么？#

输入 $X\in\mathbb R^{N\times D}$ 。初始化时：

\mathcal C^{(0)}=\{\{x_1\},\ldots,\{x_N\}\}

第 $t$ 轮在当前簇集合中寻找：

(A^*,B^*)=\arg\min_{A\ne B} d_{\text{link}}(A,B)

再用 $A^*\cup B^*$ 替换这两个簇。真正决定几何的不是“合并”二字，而是簇间距离 $d_{\text{link}}$ ，也称联接准则（Linkage Criterion）。

X [N,D]
  │ 两两样本距离
  ▼
距离/近邻结构 ──► 当前所有簇对的 linkage
                         │ 取最小
                         ▼
              children[t] = [left,right]
              distances[t] = merge_height
                         │ 重复 N-1 次
                         ▼
              合并树 ──切割──► labels [N]

text

03 四种 linkage 如何改变“最近的两个簇”？#

设簇 $A,B$ 中点对距离为 $d(x_i,x_j)$ ：

d_{single}(A,B)=\min_{i\in A,j\in B}d(x_i,x_j)

d_{complete}(A,B)=\max_{i\in A,j\in B}d(x_i,x_j)

d_{average}(A,B)=\frac{1}{|A||B|}\sum_{i\in A}\sum_{j\in B}d(x_i,x_j)

linkage	关注什么	常见几何	典型风险
`single`	最近的一对点	可沿细长或弯曲链延伸	少量桥接点造成 chaining
`complete`	最远的一对点	偏好直径较小的紧凑簇	对极端点敏感
`average`	所有跨簇点对平均	在两者之间折中	仍依赖距离与尺度
`ward`	合并后增加的 SSE	偏好紧凑、方差小的簇	只适合欧氏几何

Ward 联接（Ward Linkage）不是简单点对距离。若 $A,B$ 的样本数为 $n_A,n_B$ ，均值为 $\mu_A,\mu_B$ ，合并导致的簇内平方和增量为：

\Delta(A,B)=\frac{n_An_B}{n_A+n_B}\|\mu_A-\mu_B\|_2^2

它选择 $\Delta$ 最小的合并，因此和 K 均值一样偏好欧氏空间中的紧凑簇。ward 不能随意换成余弦距离。

04 用四个一维点手算完整合并树#

取 $A=0,B=1,C=4,D=6$ ，使用绝对距离与 average linkage。初始最小距离是 $d(A,B)=1$ ，先合并 $\{A,B\}$ 。剩余候选：

d_{avg}(\{A,B\},\{C\})=\frac{|0-4|+|1-4|}{2}=3.5

d(C,D)=2

所以第二步合并 $\{C,D\}$ 。最后两个簇的距离为：

\frac{|0-4|+|0-6|+|1-4|+|1-6|}{4} =\frac{4+6+3+5}{4}=4.5

步骤 $t$	合并节点	新节点编号	高度	新簇大小
0	A(0), B(1)	4	1.0	2
1	C(2), D(3)	5	2.0	2
2	节点 4, 节点 5	6	4.5	4

高度
4.5          ┌───────────────┐
             │               │
2.0          │          ┌────┴────┐
1.0     ┌────┴────┐     │         │
0       A         B     C         D

             在 3.0 处切割 -> 两簇 {A,B} 与 {C,D}

text

节点编号大于等于 $N$ 时表示先前产生的内部节点；第 $t$ 个新节点编号就是 $N+t$ 。这正是 scikit-learn children_ 的编码方式。

05 不调用聚类器，写出最小 average linkage#

下面实现故意每轮枚举所有簇对，只适合小数据教学核对：

from itertools import combinations
import numpy as np

def average_linkage_small(X: np.ndarray):
    X = np.asarray(X, dtype=np.float64)             # [N,D]
    n = X.shape[0]
    pairwise = np.linalg.norm(
        X[:, None, :] - X[None, :, :], axis=2
    )                                               # [N,N]

    clusters = {i: [i] for i in range(n)}
    children, heights, sizes = [], [], []

    for step in range(n - 1):
        best = None
        for left, right in combinations(sorted(clusters), 2):
            rows = clusters[left]
            cols = clusters[right]
            distance = pairwise[np.ix_(rows, cols)].mean()
            candidate = (distance, left, right)
            if best is None or candidate < best:
                best = candidate

        distance, left, right = best
        members = clusters.pop(left) + clusters.pop(right)
        clusters[n + step] = members
        children.append([left, right])
        heights.append(distance)
        sizes.append(len(members))

    return (
        np.asarray(children, dtype=int),             # [N-1,2]
        np.asarray(heights),                         # [N-1]
        np.asarray(sizes, dtype=int),                # [N-1]
    )

X = np.array([[0.0], [1.0], [4.0], [6.0]])
children, heights, sizes = average_linkage_small(X)

assert children.tolist() == [[0, 1], [2, 3], [4, 5]]
assert np.allclose(heights, [1.0, 2.0, 4.5])
assert sizes.tolist() == [2, 2, 4]

python

真实实现会维护距离更新和优先结构；不要把这段 $O(N^3)$ 风格的教学代码用于生产数据。

06 用 scikit-learn 1.9 正确落地#

当前官方 AgglomerativeClustering API ↗ 使用 metric 而不是旧参数 affinity。若要保存完整树及合并高度：

import numpy as np
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import StandardScaler

X_scaled = StandardScaler().fit_transform(X_train)  # [N,D]

model = AgglomerativeClustering(
    n_clusters=4,
    metric='euclidean',
    linkage='average',
    compute_full_tree=True,
    compute_distances=True,
)
labels = model.fit_predict(X_scaled)                 # [N]

assert model.children_.shape == (X_scaled.shape[0] - 1, 2)
assert model.distances_.shape == (X_scaled.shape[0] - 1,)
assert model.n_leaves_ == X_scaled.shape[0]
print(np.bincount(labels))

python

也可以不用预先指定簇数，改用距离阈值切树：

cut = AgglomerativeClustering(
    n_clusters=None,
    distance_threshold=2.4,
    metric='euclidean',
    linkage='complete',
    compute_full_tree=True,
    compute_distances=True,
)
labels = cut.fit_predict(X_scaled)

python

distance_threshold 非空时，n_clusters 必须为 None，完整树必须计算。compute_distances=True 便于画树状图，但会增加计算与内存开销。

07 连通约束怎样阻止“不该发生的跨越”？#

图像像素只应与空间邻居先合并，网页也可能只允许沿链接关系合并。连接矩阵 connectivity [N,N] 指定哪些样本对有资格跨簇连接：

from sklearn.cluster import AgglomerativeClustering
from sklearn.neighbors import kneighbors_graph

graph = kneighbors_graph(
    X_scaled,
    n_neighbors=12,
    mode='connectivity',
    include_self=False,
)                                                    # 稀疏 [N,N]

model = AgglomerativeClustering(
    n_clusters=6,
    linkage='ward',
    metric='euclidean',
    connectivity=graph,
    compute_full_tree='auto',
).fit(X_scaled)

python

约束能保留局部结构并减少候选合并，但图若断裂或 n_neighbors 太小，会让结果被人为拓扑主导。记录连通分量数、节点度分布，并在相邻的邻居数上做稳定性检查。

08 怎样切树，而不是对树状图“看图说话”？#

树状图可帮助发现明显的高度跳跃，但切线仍是模型选择：

在业务可接受的簇数范围内比较多个切法；
检查重采样、时间切片和小幅参数变化后的簇匹配稳定性；
同时报告簇大小，防止产生大量单点簇；
有标签时才使用 ARI 等外部指标，不能偷看测试标签选切线；
无标签时结合轮廓系数、领域解释与下游任务，但不要把任一内部指标当真值。

合并高度的绝对值依赖特征缩放、距离和 linkage。不同设置下的“高度 2.4”不能直接比较。

09 为什么它没有自然的 `predict(X_new)`？#

层次聚类的树是训练样本集合上的全局合并结果。加入一个新点，可能改变早期最近簇对，随后整棵树都不同。因此 AgglomerativeClustering 提供 fit/fit_predict 和训练标签，没有原生 predict。

如果业务必须持续接收新样本，应明确改写语义：冻结旧簇后训练一个监督分类器进行近似外推；定期全量重聚类并匹配簇身份；或使用有原生新样本分配规则的方法。不要把“分到最近质心”说成层次聚类本身。

10 复杂度、失败场景与调试路径#

层次方法通常至少需要平方级距离或候选关系；稠密大样本时，时间和内存会先于公式成为瓶颈。最短检查路径是：

特征量纲主导：打印缩放前后各列分位数，抽查最近点是否符合语义。
single 链化：检查连接两个主体簇的少数点，改用 average/complete 或处理噪声。
complete 被异常点拉高：定位决定最大跨簇距离的样本，不要只看最终颜色。
Ward 用错距离：Ward 只能用欧氏距离；类别/文本数据应另选度量和 linkage。
切线不稳定：对样本重采样，比较树切割后的共聚类矩阵，而非直接比较可置换的编号。
大数据耗尽内存：先抽样验证，构建有意义的稀疏 connectivity，或评估 BIRCH/mini-batch 方法。
把树当因果分类学：层次只反映输入表示与准则，不证明真实世界存在对应物种式层级。

11 与相近方法的边界#

方法	输出结构	主要几何/参数	噪声与新样本
K 均值	一层扁平标签	中心、簇数、欧氏 SSE	强制分配；可按中心预测
DBSCAN	密度连通标签	`eps/min_samples`	可标噪声；无原生预测
凝聚层次	合并树与切割	linkage、距离、切线	通常强制入树；无原生预测
谱聚类	图嵌入后的标签	相似图、特征向量、簇数	非凸结构；通常是传导式方法
BIRCH	CF 压缩树	阈值、分支因子	面向大数据增量压缩

层次聚类的核心价值是保留多粒度关系，不是自动免除“选多少簇”的判断。

12 今天真正需要记住什么？#

凝聚层次聚类从单点簇出发，每轮按 linkage 合并最近簇，并用 children_ 与合并高度保存一棵树。single、complete、average 和 Ward 对“簇有多近”给出不同答案；切树得到的标签依赖尺度、距离、联接与粒度选择。可靠实践要检查树的稳定性、簇大小和计算成本，并承认它没有自然的新样本预测。

13 思考题与小练习#

对 $[0,1,4,6]$ 分别手算 single 与 complete linkage 的三次合并高度。最后一次高度为何分别是 3 与 6？
给四点例子加入异常点 100，比较 average、complete 与 Ward 的树。哪个联接最直接受到最大距离影响？
在月牙数据上比较无约束和 10 近邻 connectivity 的 Ward 聚类；画出近邻图、合并高度和两种切割，并解释差异来自哪里。

14 下一篇预告#

linkage 在原空间里决定合并顺序，但两条缠绕曲线上的“全局欧氏距离”仍可能误导。下一篇将把样本变成相似图，推导图拉普拉斯与谱嵌入：为什么在原空间难切的非凸簇，能在特征向量坐标中被简单分开。

01 为什么一组标签不够？#

02 算法每一轮究竟比较什么？#

03 四种 linkage 如何改变“最近的两个簇”？#

04 用四个一维点手算完整合并树#

05 不调用聚类器，写出最小 average linkage#

06 用 scikit-learn 1.9 正确落地#

07 连通约束怎样阻止“不该发生的跨越”？#

08 怎样切树，而不是对树状图“看图说话”？#

09 为什么它没有自然的 predict(X_new)？#

10 复杂度、失败场景与调试路径#

11 与相近方法的边界#

12 今天真正需要记住什么？#

13 思考题与小练习#

相关工作#

14 下一篇预告#

09 为什么它没有自然的 `predict(X_new)`？#