层次聚类

层次聚类（Hierarchical Clustering）是数学建模中"不预设类别数、自底向上把样本逐层合并成树"的聚类方法。它以树状图（dendrogram）为核心输出，一次计算即可得到从"每个样本各成一类"到"全体合并为一类"的完整谱系，切割位置可任意选择，特别适合样本量不大、需要探索层级结构的竞赛题目。本文从原理、适用场景、评价指标、可视化到可运行代码（含手写实现与 scipy/sklearn 对照），完整梳理层次聚类的竞赛实战用法。

一、算法含义

1.1 通俗理解

班级出游要分组，老师并不事先规定分几组，而是采用"抱团"策略：一开始每个人自己是一组，然后每一步都把"距离最近"的两组合并成一组，直到最后全班合成一组。把每一步"谁和谁、在多近的时候合并"都记下来，就得到一棵合并树，就像家谱或公司组织架构图。

层次聚类回答三个问题：

合并顺序：哪些样本最相似、最先合并？
层级结构：样本之间天然的分层关系是什么（大类里套小类）？
任意 K 的划分：在合并树的任意高度"横切一刀"，就得到一种划分——想分几类就切在哪。

例如： $n$ 个样本，第 1 步合并最近的两点成 $G_1$ （此时共 $n-1$ 簇），第 2 步再合并最近的两簇，……第 $n-1$ 步所有样本合成一簇。每一步合并时两簇的距离记为合并高度 $h_m$ ：高度越小，说明被合并的两簇越相似、合并得越"自然"。

1.2 两种构建方向

凝聚式（自底向上，Agglomerative，又称 AGNES）：从 $n$ 个样本各自成簇出发，每次合并最近的两簇，共 $n-1$ 次合并。形式化描述：

$(i^{*}, j^{*}) = \arg\min_{1 \le i < j \le c} d(G_i, G_j), \qquad G_{new} = G_{i^{*}} \cup G_{j^{*}}$

其中 $c$ 为当前簇数， $d(G_i, G_j)$ 为簇间距离。scipy、sklearn 提供的都是凝聚式，工程中最常用。

分裂式（自顶向下，Divisive，又称 DIANA）：从全部样本为一大簇出发，每步把一个簇分裂成两个，直到每个样本各成一簇。每次分裂都要在簇内寻找最优二分（常先用一次 K-means(k=2) 或最小割），计算量大，scipy/sklearn 均未直接提供，实际中很少使用。

二者的共同点：都产生一棵二叉树——叶子为样本，内部节点为合并/分裂操作，结果都可以画成树状图。由于凝聚式占绝对主流，本文后续默认讨论凝聚式。

1.3 簇间距离的三种链接方式

"两簇之间的距离"如何定义，直接决定合并顺序与最终聚类形状。三种经典定义（ $d(x, y)$ 为样本点间的距离，常取欧氏距离）：

单链接（Single Linkage，最近点）：

$d_{single}(A, B) = \min_{x \in A,\ y \in B} d(x, y)$

只盯着两簇之间最近的两个点。效果：只要两簇之间有一条"桥"（哪怕只是一串稀疏点），二者就被认为很近，从而沿桥逐步合并——这就是链式效应（chaining effect）。优点是能识别细长、连通的非凸结构（哑铃、螺旋、环）；缺点是极容易被噪声点"搭桥"，把本该分开的两个簇错误合并。

全链接（Complete Linkage，最远点）：

$d_{complete}(A, B) = \max_{x \in A,\ y \in B} d(x, y)$

只盯着两簇之间最远的两个点。效果：两簇必须"整体都近"才合并，倾向产生直径小、紧凑的球形簇；长条或哑铃结构会被拦腰切碎。缺点是对离群点敏感——一个极端点就能撑大簇直径，阻止本应发生的合并。

平均链接（Average Linkage，UPGMA）：

$d_{average}(A, B) = \frac{1}{|A|\,|B|} \sum_{x \in A} \sum_{y \in B} d(x, y)$

取两簇之间所有样本对距离的平均。效果：单链接与全链接的折中，对噪声和离群点更稳健，是竞赛中最稳妥的默认选择。

此外还有 Ward 链接：每次合并使簇内方差增加最小的两簇（原理见第八节），适合球形数据，但只支持欧氏距离。

1.4 距离矩阵与合并过程

层次聚类的全部输入信息是一张 $n \times n$ 的距离矩阵：

$D = \begin{pmatrix} 0 & d(x_1,x_2) & \cdots & d(x_1,x_n) \\ d(x_2,x_1) & 0 & \cdots & d(x_2,x_n) \\ \vdots & \vdots & \ddots & \vdots \\ d(x_n,x_1) & d(x_n,x_2) & \cdots & 0 \end{pmatrix}, \qquad D_{ij} = d(x_i, x_j)$

凝聚过程共 $n-1$ 步，第 $m$ 步的合并记为：

$Z_m = \left(i_m,\ j_m,\ h_m,\ s_m\right)$

其中 $i_m, j_m$ 为被合并的两簇编号， $h_m$ 为合并高度（即两簇的簇间距离）， $s_m$ 为新簇样本数。全部 $Z_m$ 拼成 $(n-1) \times 4$ 的合并记录矩阵 $Z$ ，它完整等价于整棵聚类树，树状图就由它画出（这也是 scipy 的 linkage 函数返回的格式）。

合并后如何更新新簇与其余簇的距离？不必重算所有样本对——用 Lance-Williams 公式（设 $G_k = G_i \cup G_j$ ， $G_l$ 为其余任一簇）：

$d(G_k, G_l) = \alpha_i\, d(G_i, G_l) + \alpha_j\, d(G_j, G_l) + \beta\, d(G_i, G_j) + \gamma\, \left| d(G_i, G_l) - d(G_j, G_l) \right|$

三种链接方式只是参数取值不同：

链接方式	$\alpha_i$	$\alpha_j$	$\beta$	$\gamma$	含义
单链接	$\dfrac{1}{2}$	$\dfrac{1}{2}$	0	$-\dfrac{1}{2}$	$d(G_k,G_l)=\min\{d(G_i,G_l),\, d(G_j,G_l)\}$
全链接	$\dfrac{1}{2}$	$\dfrac{1}{2}$	0	$+\dfrac{1}{2}$	$d(G_k,G_l)=\max\{d(G_i,G_l),\, d(G_j,G_l)\}$
平均链接	$\dfrac{n_i}{n_i+n_j}$	$\dfrac{n_j}{n_i+n_j}$	0	0	按样本数加权平均
Ward	$\dfrac{n_i+n_l}{n_i+n_j+n_l}$	$\dfrac{n_j+n_l}{n_i+n_j+n_l}$	$\dfrac{-n_l}{n_i+n_j+n_l}$	0	方差增量最小化

（ $n_i$ 为簇 $G_i$ 的样本数。Lance-Williams 公式把每次合并后的更新量从 $O(n^2)$ 降到 $O(c)$ ，是层次聚类得以实用的关键技巧。）

1.5 树状图（dendrogram）

树状图是层次聚类最核心的输出：横轴是样本（顺序经过重排），纵轴是合并高度 $h_m$ 。每个叶子代表一个样本，每个内部节点代表一次合并，节点所在高度就是合并时两簇的距离。

高度越低的两簇合并得越早、越相似；高度越高说明越"勉强"才合并；
在任意高度画一条水平线，与竖线相交的个数就是该切割下的簇数——这就是"横切一刀选 K"的方法；
单/全/平均/Ward 链接的合并高度随合并次序单调不减，因此树状图总是向上生长、不会交叉（个别链接如质心法可能出现"反转"，这是它的缺陷之一）。

1.6 优缺点

优点：

无需预设簇数 K：一次建树，所有可能的 K 都包含在树里，切割位置灵活选择；
输出完整层级结构：能回答"哪些类更相似、哪些差异大"，这是 K-means 给不了的；
只需距离矩阵即可运行，可使用任意距离度量（欧氏、曼哈顿、余弦、Jaccard 等），也能处理"只有相似度矩阵、没有坐标"的数据；
树状图直观，评审老师一眼可懂，论文中天然自带一张漂亮的结果图；
小样本下结果稳定、可复现（无随机初始化，不像 K-means 依赖初值）。

缺点：

计算复杂度高：需维护 $O(n^2)$ 的距离矩阵，时间复杂度 $O(n^2) \sim O(n^3)$ （scipy 的优化实现约 $O(n^2)$ ），样本量大时"矩阵爆炸"；
合并是贪心且不可逆：早期一次错误合并，后面所有层级都被污染，无法回头纠正；
对噪声与离群点敏感：单链接怕噪声搭桥，全链接怕离群点撑大直径；
不适合大样本（ $n > 10^4$ 时需谨慎）、高维数据（欧氏距离在高维失效）等场景。

二、何时使用（适用场景与条件）

2.1 适用场景

样本量小到中等（几百 ~ 几千，一般 $n \le 5000$ 最舒服）：层次聚类的 $O(n^2)$ 内存是硬约束；
需要层级结构：物种分类学（界门纲目科属种）、文本主题层级（总主题-子主题）、企业集团-子公司归属、城市群层级体系；
需要树状图可视化：向评审展示"聚类谱系"本身就是论证的一部分；
不确定分几类：先用树状图探索数据的分层结构，再决定切割位置；
只有距离/相似度矩阵（如序列比对得分、网络节点相似度），无法使用基于坐标的方法。

2.2 竞赛典型题目

分类学 / 谱系类：病毒株系演化谱系、方言区划、企业信用等级分层——先聚类再命名，树状图直接当谱系图用；
层次体系构建：指标体系梳理（把相关性强的指标合并为"一级指标"）、区域发展分层（一线/二线/三线城市）、消费者画像分层；
探索性预分析：作为 K-means 的"前奏"，用树状图估计合理的 K 值，再交给其他算法或用于论证类别数的合理性。

2.3 使用前提

样本量不宜过大（见 2.4），特征维度不宜过高；
特征必须先标准化（z-score）：距离度量对量纲敏感，否则量级大的特征会主导聚类；
链接方式与距离度量要与问题匹配：物理上连通的形态用单链接，追求紧凑球形用全链接/Ward，稳妥默认用平均链接；
当真实类别数恰好是"树状图上的一个切割位置"时，方法最自然。

2.4 不适用情形

大样本（ $n \ge 10^4$ ）：距离矩阵 $O(n^2)$ 内存爆炸，改用 K-means、DBSCAN、BIRCH；
含噪的非凸簇：单链接虽能识别连通结构，但噪声点一多就会链式误并；对带噪声的月牙、环状数据，DBSCAN 通常更稳；
需要明确簇中心：层次聚类只给划分，不给中心（需自行计算均值/中位数）；
要求全局最优划分：贪心合并不保证目标函数（如总 SSE）全局最优。

2.5 与 K-means、DBSCAN 的对比选择

维度	K-means	层次聚类	DBSCAN
是否需预设簇数	必须预设 K	不需要（树状图切割）	不需要（自动发现）
簇形状	凸的球形簇	单链接可非凸，全/Ward 偏球形	任意形状
噪声处理	差（每个点都入簇）	差（噪声会搭桥/撑直径）	好（自动标记噪声点）
输出层级结构	无	有（树状图）	无
复杂度	$O(nKt)$	$O(n^2)$ 以上	$O(n \log n)$ （索引良好时）
适合规模	大	小 ~ 中	大
竞赛用法	常规划分	谱系/层级/小样本	密度分布型数据

一句话选择：样本小、要谱系、不确定 K → 层次聚类；样本大、球形 → K-means；形状怪、有噪声 → DBSCAN。

三、算法指标

3.1 轮廓系数（Silhouette Coefficient，评价聚类质量）

对每个样本 $i$ 定义：

$a(i)$ ：样本 $i$ 与同簇其余样本的平均距离（簇内凝聚度）；
$b(i)$ ：样本 $i$ 与最近的其他簇的平均距离（簇间分离度）；
样本 $i$ 的轮廓系数：

$s(i) = \frac{b(i) - a(i)}{\max\{a(i),\, b(i)\}}, \qquad s(i) \in [-1, 1]$

总体轮廓系数为所有样本的均值：

$S = \frac{1}{n} \sum_{i=1}^{n} s(i)$

含义与解读： $S > 0.5$ 聚类结构较好； $0.2 \sim 0.5$ 一般； $< 0.2$ 结构弱；接近 0 说明簇间重叠严重；出现负值说明大量样本"站错了队"。注意：轮廓系数偏好凸、紧凑、大小均衡的簇——结构正确但细长的簇（如哑铃）会被系统性低估，这正是它在本例数据上"失灵"的原因（见 7.1 节）。

3.2 cophenetic 相关系数（树状图保真度）

树状图把 $n(n-1)/2$ 个样本对距离压缩成 $n-1$ 个合并高度，信息有损失。定义样本对 $(i, j)$ 的 cophenetic 距离 $t(i, j)$ 为二者首次并入同一簇时的合并高度（即树状图上"最近共同祖先"的高度）。树状图对原始距离结构保留得好不好，用两者的 Pearson 相关系数衡量：

$c = \frac{\displaystyle\sum_{i<j} \left(d(i,j) - \bar{d}\right)\left(t(i,j) - \bar{t}\right)}{\sqrt{\displaystyle\sum_{i<j}\left(d(i,j) - \bar{d}\right)^2 \cdot \sum_{i<j}\left(t(i,j) - \bar{t}\right)^2}}$

其中 $\bar{d}, \bar{t}$ 分别是原始距离与 cophenetic 距离在全部 $n(n-1)/2$ 个样本对上的均值。

含义与解读： $c$ 越接近 1，树状图越"忠于"原始距离结构；经验上 $c > 0.75$ 认为树状图可用。注意两点：① $c$ 衡量的是保真度而非聚类正确性——单链接的链式合并会把大距离压成低合并高度， $c$ 反而偏低（本例即如此）；② 跨链接方式比较 $c$ 时， $c$ 高不代表分类更好，只代表树更"忠实"。

3.3 各簇样本数

切割后第 $k$ 簇的样本数 $n_k$ （ $k = 1, 2, \dots, K$ ），满足 $\sum_{k=1}^{K} n_k = n$ 。

含义与解读：各簇样本数应结合业务判断——极度不均衡（如 195/3/2）常提示切得过细或数据本身存在"长尾"；单链接容易产出只含 1 个点的"独点簇"（噪声点最后才被并入）。竞赛中常在论文里给出各簇样本数表作为结果佐证，并据此给各类命名与定性。

3.4 不同链接方式的对比（提及）

链接方式	簇形状偏好	对噪声/离群点	链式效应	典型适用
单链接	细长、连通、非凸	极敏感（噪声搭桥）	有	谱系、物理连通结构
全链接	紧凑球形	敏感（离群点撑大直径）	无	希望簇直径受控
平均链接	折中	较稳健	弱	通用默认
Ward	球形、大小均衡	较稳健	无	欧氏空间常规数据

3.5 指标汇总表

指标	中文名	公式	含义	解读
$S$	轮廓系数	$S = \dfrac{1}{n}\displaystyle\sum_{i} \dfrac{b(i)-a(i)}{\max\{a(i),b(i)\}}$	簇内紧凑、簇间分离的综合度量	越接近 1 越好； $>0.5$ 结构好；偏好凸簇
$c$	cophenetic 相关系数	见 3.2 式	树状图对距离矩阵的保真度	越接近 1 越好； $>0.75$ 可用；≠ 分类正确性
$ARI$	调整兰德指数	见下方说明	聚类结果与真实标签的一致程度（扣除随机一致）	1 为完全一致，0 为随机水平；仅当有真实标签时可用
$n_k$	各簇样本数	$\sum_{k=1}^{K} n_k = n$	划分的规模结构	极不均衡时警惕切分不当
$h_m$	合并高度	$Z_m$ 第 3 列	两簇合并时的簇间距离	高度跳变处 = 合理的切割位置

ARI 的完整公式（ $n_{ij}$ 为真实类别 $i$ 与聚类结果 $j$ 的交集样本数， $a_i$ 、 $b_j$ 为边际计数， $n$ 为样本量）：

$ARI = \frac{\displaystyle\sum_{i,j} \binom{n_{ij}}{2} - \left[\sum_{i} \binom{a_i}{2} \sum_{j} \binom{b_j}{2}\right] \Big/ \binom{n}{2}}{\dfrac{1}{2}\left[\displaystyle\sum_{i} \binom{a_i}{2} + \sum_{j} \binom{b_j}{2}\right] - \left[\displaystyle\sum_{i} \binom{a_i}{2} \sum_{j} \binom{b_j}{2}\right] \Big/ \binom{n}{2}}$

四、可视化图表

4.1 图表总览

图名	用途	关键解读点
①树状图（`scipy.cluster.hierarchy.dendrogram`，含切割阈值线）	展示合并过程与层级结构；选择簇数 K	切割线（红色虚线）与竖线的交点个数 = 簇数；合并高度越高的"桥"越勉强；高度出现大幅跳变处是天然切割位
②按树状图切割的聚类结果散点图	展示最终划分在原始空间中的样子	颜色对应类别；红色 ✕ 标记与真实标签不符的点；哑铃结构是否被完整识别
③三种链接方式（单/全/平均）结果对比面板	对比不同链接方式的划分差异	单链接沿桥连通成哑铃；全链接/平均链接把哑铃切碎并先合并邻近的 C、D；对照 ARI 与轮廓系数
④距离矩阵热力图（可选）	检查距离结构与簇的块状对应	按簇重排后呈"块状结构"（块内深色 = 距离小、块间浅色 = 距离大）；块边界不清晰提示簇间重叠
⑤（附加）各链接方式指标条形图	一键对比 ARI/轮廓系数/cophenetic	不同指标可能给出不同"最优方法"——这正是竞赛论文值得讨论的点

4.2 好图与异常图的特征

好图特征：树状图有清晰的"长枝"结构（合并高度跳变明显），切割位置位于跳变区间内；散点图各类颜色区域分明、无大面积交错；热力图块状对角线结构清晰；多个指标（ARI、轮廓系数）互相印证。

异常图特征：树状图合并高度均匀递增、没有跳变 → 数据可能本无簇结构；散点图类别犬牙交错 → 距离度量或特征尺度有问题；热力图几乎无块状结构 → 聚类结果与距离结构矛盾；cophenetic 相关系数很低（如 $< 0.6$ ）→ 树状图失真，切割结论不可靠。

五、符号说明

符号	含义	示例/单位
$n$	样本量	本例 $n = 200$
$p$	特征维数	本例 $p = 2$ （二维平面点）
$x_i$	第 $i$ 个样本向量	$x_i = (x_{i1}, x_{i2})^\top$
$d(x, y)$	两点间距离（常为欧氏距离）	$\\|x-y\\|_2 = \sqrt{\sum_j (x_j - y_j)^2}$
$D$	距离矩阵（ $n \times n$ 对称阵）	$D_{ij} = d(x_i, x_j)$
$G_i$	第 $i$ 个簇（样本集合）	$G_k = G_i \cup G_j$
$d(G_i, G_j)$	簇间距离（由链接方式决定）	单/全/平均链接三种定义
$n_i$	簇 $G_i$ 的样本数	$n_i = \lvert G_i \rvert$
$Z$	合并记录矩阵（ $(n-1) \times 4$ ）	每行 [簇i, 簇j, 合并高度, 样本数]
$h_m$	第 $m$ 次合并的高度	$h_m = d(G_i, G_j)$ ，距离单位
$K$	目标簇数（由切割位置决定）	本例 $K = 3$
$a(i), b(i)$	样本 $i$ 的簇内平均距离、最近簇间平均距离	距离单位
$s(i), S$	样本 $i$ 与总体的轮廓系数	无量纲， $[-1, 1]$
$t(i, j)$	cophenetic 距离（首次同簇的合并高度）	距离单位
$c$	cophenetic 相关系数	无量纲， $[-1, 1]$ ，接近 1 好
$ARI$	调整兰德指数	无量纲，1 为完全一致
$\alpha_i, \alpha_j, \beta, \gamma$	Lance-Williams 更新系数	取值见 1.4 节表格

六、可运行程序（完整代码）

环境要求：Python 3.12，依赖 numpy、scipy、scikit-learn、matplotlib、pandas（pip install numpy scipy scikit-learn matplotlib pandas）。以下所有代码块按顺序拼接保存为 hc_demo.py，在本文档所在目录运行即可：控制台打印全部指标，并在 figures/ 子目录生成 5 张图（文件名以 hc_ 开头）。数据为程序内合成的"4 高斯簇 + 哑铃桥"（ $n = 200$ ，np.random.seed(42) 保证可复现），无外部文件依赖。

# -*- coding: utf-8 -*-
"""
============================================================
层次聚类完整示例：手写实现 + scipy / sklearn 对照
------------------------------------------------------------
数据（合成）：4 个高斯簇 + 1 条稀疏桥（其中两个高斯簇构成"哑铃"
结构，真实类别数 = 3），n = 200，np.random.seed(42) 保证可复现
输出：控制台打印全部常用指标 + figures/ 目录下 5 张图（hc_ 前缀）
依赖：numpy、scipy、scikit-learn、matplotlib、pandas
============================================================
"""

# ========== 0. 导入库与全局设置 ==========
import os
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, fcluster, dendrogram, cophenet
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_score, adjusted_rand_score

# ---- matplotlib 中文显示设置（防止图内中文乱码）----
plt.rcParams["font.sans-serif"] = ["PingFang SC", "Arial Unicode MS", "SimHei"]
plt.rcParams["axes.unicode_minus"] = False   # 让负号"-"正常显示

# ---- 图片输出目录（相对当前工作目录的 figures/ 子目录）----
FIG_DIR = "figures"
os.makedirs(FIG_DIR, exist_ok=True)

# ========== 1. 数据生成：4 个高斯簇 + 1 条桥（哑铃结构） ==========
np.random.seed(42)                          # 固定随机种子，保证每次运行结果完全一致

n_a, n_b, n_bridge = 40, 40, 15             # 哑铃：左球 A + 右球 B + 连接桥
n_c, n_d = 55, 50                           # 另两个普通高斯簇 C、D
n = n_a + n_b + n_bridge + n_c + n_d        # 总样本量 = 200

# 簇 A（哑铃左球）与簇 B（哑铃右球）：中心相距 6，标准差 0.45
XA = np.random.normal(loc=[3.0, 3.0], scale=0.45, size=(n_a, 2))
XB = np.random.normal(loc=[9.0, 3.0], scale=0.45, size=(n_b, 2))
# 桥（哑铃"柄"）：x 在 4.2~7.8 上均匀排布、y 在 3 附近小幅抖动，
# 把 A、B 连成一个"连通结构"——这正是单链接能识别、全链接会切碎的哑铃形状
X_bridge = np.column_stack([
    np.linspace(4.2, 7.8, n_bridge),
    3.0 + np.random.normal(0.0, 0.10, n_bridge),
])
# 簇 C、D：彼此较近（中心距 4.0），用来检验全链接/平均链接是否会"先把它俩合并"
XC = np.random.normal(loc=[8.0, 10.0], scale=0.55, size=(n_c, 2))
XD = np.random.normal(loc=[12.0, 10.0], scale=0.55, size=(n_d, 2))

X = np.vstack([XA, XB, X_bridge, XC, XD])
# 真实类别（结构性真值）：哑铃（A + 桥 + B）是一个连通结构，算作 1 类；C、D 各 1 类 → 共 3 类
y_true = np.array([0] * (n_a + n_b + n_bridge) + [1] * n_c + [2] * n_d)

print(f"已生成 n = {n} 个样本，真实类别数 k_true = {len(np.unique(y_true))}")
print(f"真实各类样本数：{np.bincount(y_true).tolist()}（哑铃 95 = 左球 40 + 桥 15 + 右球 40）")

# ========== 2. 手写实现：凝聚式层次聚类（Lance-Williams 更新公式） ==========
def dist_matrix(X):
    """手写欧氏距离矩阵 D：D[i, j] = ||x_i - x_j||₂，对角置 inf（自己不算）"""
    diff = X[:, None, :] - X[None, :, :]         # (n, n, 2)：两两坐标差
    D = np.sqrt((diff ** 2).sum(axis=2))         # 逐元素求欧氏距离
    np.fill_diagonal(D, np.inf)
    return D

# Lance-Williams 公式参数：新簇 k = i ∪ j 与旧簇 l 的距离为
#   d(k, l) = α_i·d(i, l) + α_j·d(j, l) + β·d(i, j) + γ·|d(i, l) − d(j, l)|
# 三种链接方式只是 α、β、γ 取值不同：
LW_PARAMS = {
    "single":   (0.5, 0.5, 0.0, -0.5),   # 单链接：新距离 = min(d(i,l), d(j,l))，链式效应
    "complete": (0.5, 0.5, 0.0, +0.5),   # 全链接：新距离 = max(d(i,l), d(j,l))，紧凑球形簇
    "average":  (0.0, 0.0, 0.0,  0.0),   # 平均链接：α 按簇内样本数加权（UPGMA），见下方分支
}

def agglomerative(X, method="single"):
    """
    手写凝聚式层次聚类（自底向上）：
      1) 每个样本自成一簇，维护簇间距离矩阵 D；
      2) 每次找出距离最近的一对簇 (i, j)，合并成新簇 k = i ∪ j；
      3) 把本次合并记入 Z（供画树状图、供 fcluster 切割）；
      4) 用 Lance-Williams 公式更新新簇 k 与其余各簇的距离（不必重算样本对距离）；
      5) 重复 n−1 次，直到全部合成一簇。
    返回 Z：形状 (n−1, 4)，每行 [簇i, 簇j, 合并高度, 新簇样本数]，与 scipy 的 linkage 格式一致。
    """
    n = X.shape[0]
    D = dist_matrix(X)                           # 欧氏距离矩阵（内部直接使用）
    max_nodes = 2 * n - 1                        # 总节点数：n 个叶子 + n−1 个内部节点
    D_full = np.full((max_nodes, max_nodes), np.inf)
    D_full[:n, :n] = D                           # 只用到活跃节点的子块
    sizes = np.ones(max_nodes)                   # 每簇样本数（叶子为 1）
    active = np.zeros(max_nodes, dtype=bool)     # 是否为"活跃簇"（尚未被合并）
    active[:n] = True
    Z = np.zeros((n - 1, 4))

    for m in range(n - 1):                       # 共需 n−1 次合并
        idx = np.where(active)[0]                # 当前所有活跃簇的编号
        sub = D_full[np.ix_(idx, idx)]           # 活跃簇之间的子距离矩阵
        ii, jj = np.unravel_index(np.argmin(sub), sub.shape)   # 找全局最近的一对
        i, j = idx[ii], idx[jj]
        d_ij = D_full[i, j]
        k = n + m                                # 新簇编号（叶子 0~n−1，新簇从 n 起）
        Z[m] = [i, j, d_ij, sizes[i] + sizes[j]] # 记录合并过程（第 3 列即合并高度 h_m）

        # ---- Lance-Williams 更新：只更新新簇 k 与其余活跃簇 l 的距离 ----
        if method == "average":                  # 平均链接（UPGMA）：α 与簇大小成比例
            ai = sizes[i] / (sizes[i] + sizes[j])
            aj = sizes[j] / (sizes[i] + sizes[j])
        else:
            ai, aj = LW_PARAMS[method][0], LW_PARAMS[method][1]
        beta, gamma = LW_PARAMS[method][2], LW_PARAMS[method][3]
        for l in idx:
            if l == i or l == j:
                continue
            D_full[k, l] = D_full[l, k] = (ai * D_full[i, l] + aj * D_full[j, l]
                                           + beta * d_ij
                                           + gamma * abs(D_full[i, l] - D_full[j, l]))
        D_full[k, k] = np.inf
        sizes[k] = sizes[i] + sizes[j]
        active[i] = active[j] = False            # 旧簇退出
        active[k] = True                         # 新簇加入
    return Z

# ========== 3. 手写实现：cophenetic 相关矩阵与相关系数 ==========
def cophenetic_matrix_hand(Z, n):
    """
    由合并记录 Z 手写 cophenetic 距离矩阵 C：
    C[i, j] = 样本 i 与 j 首次落入同一簇时的合并高度（树状图上"最近共同祖先"的高度）。
    技巧：从最后一次合并（树顶）倒序处理——倒序处理时，跨越"本次合并两个子簇"的
    样本对，其首次相遇必然就是本次合并，直接把当前高度填入即可；每个样本对只会被填一次。
    """
    C = np.full((n, n), np.inf)
    members = {i: [i] for i in range(n)}         # 每个节点的样本成员列表
    for m in range(n - 1):                       # 第一遍（正向）：自上而下建好每个节点的成员列表
        i, j = int(Z[m, 0]), int(Z[m, 1])
        members[n + m] = members[i] + members[j]
    for m in range(n - 2, -1, -1):               # 第二遍（倒序）：从树顶往树根填 cophenetic 距离
        i, j, h = int(Z[m, 0]), int(Z[m, 1]), Z[m, 2]
        for a in members[i]:                     # 跨越两个子簇的所有样本对
            for b in members[j]:
                C[a, b] = C[b, a] = h            # 首次相遇高度 = 本次合并高度
    return C

def cophenetic_corr_hand(D, Z):
    """手写 cophenetic 相关系数 c：原始距离 d 与 cophenetic 距离 t 的 Pearson 相关（上三角）"""
    n = D.shape[0]
    C = cophenetic_matrix_hand(Z, n)
    triu = np.triu_indices(n, k=1)               # 只取 i < j 的样本对（共 n(n−1)/2 对）
    d, t = D[triu], C[triu]
    dd, tt = d - d.mean(), t - t.mean()          # 中心化
    return float((dd * tt).sum() / np.sqrt((dd ** 2).sum() * (tt ** 2).sum()))

# ========== 4. 手写实现：轮廓系数（并与 sklearn 对照验证） ==========
def silhouette_hand(D, labels):
    """
    手写轮廓系数：对每个样本 i，
      a(i) = i 与同簇其余样本的平均距离（簇内凝聚度）；
      b(i) = i 到"最近的其他簇"的平均距离（簇间分离度）；
      s(i) = (b(i) − a(i)) / max(a(i), b(i)) ∈ [−1, 1]。
    总体轮廓系数 S = 所有样本 s(i) 的平均值。
    """
    n = D.shape[0]
    D0 = D.copy(); np.fill_diagonal(D0, 0.0)     # 对角置 0：自己到自己的距离不计入均值
    labs = np.unique(labels)
    k = len(labs)
    onehot = np.zeros((n, k))                    # 指示矩阵：onehot[i, r] = 1 当样本 i 属于第 r 簇
    for r, lab in enumerate(labs):
        onehot[labels == lab, r] = 1.0
    mean_dist = D0 @ onehot / onehot.sum(axis=0) # mean_dist[i, r] = 样本 i 到第 r 簇的平均距离
    a = np.zeros(n); b = np.full(n, np.inf)
    for r, lab in enumerate(labs):
        mask = labels == lab
        n_r = mask.sum()
        # 簇内均值要去掉自己：总和/(n_r − 1)（对角已置 0，总和 = mean_dist * n_r）
        a[mask] = mean_dist[mask, r] * n_r / (n_r - 1)
        others = np.delete(mean_dist[mask], r, axis=1)   # 到其余各簇的平均距离
        b[mask] = others.min(axis=1)
    s = (b - a) / np.maximum(a, b)
    return float(s.mean()), s

# ========== 5. 主流程：三种链接方式 + Ward 的全指标对比 ==========
D = dist_matrix(X)                               # 手写距离矩阵（后面所有指标都用它）
print(f"\n【距离矩阵】形状 {D.shape}，最小样本间距离 = {np.min(D):.4f}，"
      f"平均样本间距离 = {np.mean(D[np.triu_indices(n, k=1)]):.4f}")

methods = ["single", "complete", "average", "ward"]   # ward 只由 scipy 实现（手写仅三种链接）
K = len(np.unique(y_true))                       # 目标簇数 = 3（哑铃算 1 类）

rows = []
print("\n【各方法指标明细】")
for method in methods:
    # ---- 手写凝聚聚类（scipy 对照用；ward 只有 scipy 版）----
    Z_hand = agglomerative(X, method) if method != "ward" else None
    # ---- scipy 库实现：linkage + fcluster（与手写完全相同的凝聚过程）----
    Z_scipy = linkage(X, method=method)
    labs_scipy = fcluster(Z_scipy, t=K, criterion="maxclust")   # 按树状图切割成 K 类
    labs_hand = fcluster(Z_hand, t=K, criterion="maxclust") if Z_hand is not None else None
    # ---- 手写 vs scipy 对照：合并高度序列是否一致、切割后标签是否一致 ----
    if Z_hand is not None:
        heights_same = np.allclose(np.sort(Z_hand[:, 2]), np.sort(Z_scipy[:, 2]))
        ari_hs = adjusted_rand_score(labs_hand, labs_scipy)
    else:
        heights_same = ari_hs = None
    # ---- 聚类质量指标：ARI（对真实标签）、轮廓系数（手写 + sklearn 对照）、cophenetic ----
    ari_true = adjusted_rand_score(labs_scipy, y_true)
    sil_hand, _ = silhouette_hand(D, labs_scipy)
    sil_sk = silhouette_score(X, labs_scipy)
    coph_hand = cophenetic_corr_hand(D, Z_scipy)                  # 手写 cophenetic 相关系数
    coph_scipy = cophenet(Z_scipy, D[np.triu_indices(n, k=1)])[0]  # scipy 自带 cophenet 对照
    counts = np.bincount(labs_scipy)[1:].tolist()                 # 各簇样本数（标签从 1 开始）
    rows.append([method, ari_true, sil_hand, sil_sk, coph_hand, coph_scipy, counts])
    print(f"  方法 {method:8s} | ARI(对真实) = {ari_true:.4f} | 轮廓系数(手写/sklearn) = "
          f"{sil_hand:.4f} / {sil_sk:.4f} | cophenetic(手写/scipy) = {coph_hand:.4f} / "
          f"{coph_scipy:.4f} | 各簇样本数 = {counts}")
    if Z_hand is not None:
        print(f"         手写 vs scipy 对照：合并高度序列一致 = {heights_same}，"
              f"聚类结果 ARI = {ari_hs:.4f}（应为 1.000）")

# ---- 用 pandas 汇总成一张对比表 ----
df = pd.DataFrame(rows, columns=["链接方式", "ARI(对真实)", "轮廓系数(手写)", "轮廓系数(sklearn)",
                                 "cophenetic(手写)", "cophenetic(scipy)", "各簇样本数"])
print("\n【各链接方式对比汇总表】")
print(df.round(4).to_string(index=False))

# ---- sklearn AgglomerativeClustering 对照：三个库应给出完全一致的结果 ----
sk = AgglomerativeClustering(n_clusters=K, linkage="single")
labs_sklearn = sk.fit_predict(X)
ari_sklearn = adjusted_rand_score(labs_sklearn, fcluster(linkage(X, method="single"), t=K,
                                                         criterion="maxclust"))
print(f"\nsklearn AgglomerativeClustering(single) 与 scipy 的聚类结果 ARI = {ari_sklearn:.4f}"
      f"（应为 1.000）")

# ---- 手写轮廓系数与 sklearn 的最大偏差（浮点精度级） ----
max_sil_gap = max(abs(r[2] - r[3]) for r in rows)
print(f"手写轮廓系数与 sklearn 的最大绝对偏差 = {max_sil_gap:.2e}（应约为 1e-12 量级）")

# ========== 6. 绘图：第四节要求的全部图（保存到 figures/ 并显示） ==========
Z_single = linkage(X, method="single")           # 单链接：哑铃数据上的"正确答案"
labs_single = fcluster(Z_single, t=K, criterion="maxclust")
ari_single = adjusted_rand_score(labs_single, y_true)

# ---- 图① 树状图（手写合并记录 Z，scipy 仅负责绘制）----
Z_hand_single = agglomerative(X, method="single")
print("\n手写合并记录 Z（前 5 次合并）——格式 [簇i, 簇j, 合并高度, 新簇样本数]：")
for row in Z_hand_single[:5]:
    print(f"  合并: 簇 {int(row[0])} + 簇 {int(row[1])}，高度 {row[2]:.4f}，新簇样本数 {int(row[3])}")
hs = np.sort(Z_hand_single[:, 2])                # 全部合并高度（升序）
cut = (hs[n - K - 1] + hs[n - K]) / 2            # 使"一刀切"后恰好 K=3 类的切割阈值
fig, ax = plt.subplots(figsize=(10, 5))
dendrogram(Z_hand_single, ax=ax, color_threshold=cut,
           above_threshold_color="gray", no_labels=True)   # n=200 不标样本编号，避免糊成一团
ax.axhline(cut, color="red", ls="--", lw=1.5,
           label=f"切割阈值 h = {cut:.2f}（横切一刀 → {K} 类）")
ax.set_title("树状图（dendrogram）：手写凝聚聚类合并记录，单链接")
ax.set_xlabel("样本编号"); ax.set_ylabel("合并高度（簇间距离）")
ax.legend()
plt.tight_layout(); plt.savefig(os.path.join(FIG_DIR, "hc_dendrogram.png"), dpi=200); plt.show()

# ---- 图② 按树状图切割的聚类结果散点图（单链接，k=3）----
fig, ax = plt.subplots(figsize=(7, 6))
colors = ["tab:blue", "tab:orange", "tab:green"]
for c in np.unique(labs_single):
    m = labs_single == c
    ax.scatter(X[m, 0], X[m, 1], c=colors[c - 1], s=28, alpha=0.85,
               label=f"类 {c}（{m.sum()} 个样本）")
wrong = labs_single != y_true + 1                # 与真实标签不符的样本（本例应为 0 个）
ax.scatter(X[wrong, 0], X[wrong, 1], marker="x", s=120, c="red",
           linewidths=1.6, label=f"与真实标签不符（{wrong.sum()} 个）")
ax.set_title(f"按树状图切割为 {K} 类的聚类结果（单链接，ARI = {ari_single:.3f}）")
ax.set_xlabel("x1"); ax.set_ylabel("x2")
ax.legend(loc="upper left")
plt.tight_layout(); plt.savefig(os.path.join(FIG_DIR, "hc_scatter.png"), dpi=200); plt.show()

# ---- 图③ 三种链接方式（+Ward）结果对比面板 ----
fig, axes = plt.subplots(2, 2, figsize=(12, 10))
title_cn = {"single": "单链接", "complete": "全链接", "average": "平均链接", "ward": "Ward"}
for ax, method in zip(axes.ravel(), methods):
    labs = fcluster(linkage(X, method=method), t=K, criterion="maxclust")
    ari_m = adjusted_rand_score(labs, y_true)
    sil_m = silhouette_score(X, labs)
    for c in np.unique(labs):
        m = labs == c
        ax.scatter(X[m, 0], X[m, 1], c=colors[c - 1], s=22, alpha=0.85)
    ax.set_title(f"{title_cn[method]}：ARI = {ari_m:.3f}，轮廓系数 = {sil_m:.3f}")
    ax.set_xlabel("x1"); ax.set_ylabel("x2")
plt.suptitle("三种链接方式 + Ward 在哑铃数据上的聚类结果对比（均切割为 3 类）", fontsize=13)
plt.tight_layout(); plt.savefig(os.path.join(FIG_DIR, "hc_linkage_compare.png"), dpi=200); plt.show()

# ---- 图④ 距离矩阵热力图（样本按单链接聚类结果重排，观察块状结构）----
order = np.argsort(labs_single * 1e6 + X[:, 0] * 10 + X[:, 1])  # 先按簇、簇内按位置排序
D_sorted = D[np.ix_(order, order)]
fig, ax = plt.subplots(figsize=(7, 6))
im = ax.imshow(D_sorted, cmap="viridis", aspect="auto")
plt.colorbar(im, ax=ax, label="欧氏距离")
boundaries = np.cumsum(np.bincount(labs_single[order])[1:])     # 三个簇之间的边界位置
for b in boundaries[:-1]:
    ax.axhline(b - 0.5, color="red", lw=0.8)
    ax.axvline(b - 0.5, color="red", lw=0.8)
ax.set_title("距离矩阵热力图（样本按单链接聚类结果重排，呈块状结构）")
ax.set_xlabel("样本（重排后）"); ax.set_ylabel("样本（重排后）")
plt.tight_layout(); plt.savefig(os.path.join(FIG_DIR, "hc_dist_heatmap.png"), dpi=200); plt.show()

# ---- 图⑤（附加）各链接方式指标条形图：ARI + 轮廓系数 + cophenetic ----
metrics_df = df.set_index("链接方式")
fig, ax = plt.subplots(figsize=(8, 5))
xpos = np.arange(len(metrics_df)); w = 0.28
ax.bar(xpos - w, metrics_df["ARI(对真实)"], w, label="ARI（对真实标签）")
ax.bar(xpos, metrics_df["轮廓系数(sklearn)"], w, label="轮廓系数")
ax.bar(xpos + w, metrics_df["cophenetic(scipy)"], w, label="cophenetic 相关系数")
ax.set_xticks(xpos); ax.set_xticklabels([title_cn[m] for m in metrics_df.index])
ax.set_ylim(0, 1.1)
for bars in ax.containers:
    ax.bar_label(bars, fmt="%.3f", fontsize=8)
ax.set_title("不同链接方式的聚类质量指标对比（哑铃数据，k = 3）")
ax.legend()
plt.tight_layout(); plt.savefig(os.path.join(FIG_DIR, "hc_silhouette_bar.png"), dpi=200); plt.show()

print(f"\n【树状图切割】k = {K} 的切割阈值 h = {cut:.4f}"
      f"（介于排序后第 {n - K} 与第 {n - K + 1} 小的合并高度之间）")
print(f"5 张图已保存到 {FIG_DIR}/ 目录：hc_dendrogram.png、hc_scatter.png、"
      f"hc_linkage_compare.png、hc_dist_heatmap.png、hc_silhouette_bar.png")

七、结果解读与注意事项

7.1 运行输出解读（以本例合成数据为例）

以第六节代码生成的合成数据（4 个高斯簇 + 哑铃桥， $n = 200$ ，真实类别数 $K = 3$ ）为例，运行脚本后控制台输出如下：

已生成 n = 200 个样本，真实类别数 k_true = 3
真实各类样本数：[95, 55, 50]（哑铃 95 = 左球 40 + 桥 15 + 右球 40）

【距离矩阵】形状 (200, 200)，最小样本间距离 = 0.0110，平均样本间距离 = 5.7647

【各方法指标明细】
  方法 single   | ARI(对真实) = 1.0000 | 轮廓系数(手写/sklearn) = 0.6723 / 0.6723 | cophenetic(手写/scipy) = 0.8585 / 0.8585 | 各簇样本数 = [95, 50, 55]
         手写 vs scipy 对照：合并高度序列一致 = True，聚类结果 ARI = 1.0000（应为 1.000）
  方法 complete | ARI(对真实) = 0.4677 | 轮廓系数(手写/sklearn) = 0.6940 / 0.6940 | cophenetic(手写/scipy) = 0.9170 / 0.9170 | 各簇样本数 = [105, 41, 54]
         手写 vs scipy 对照：合并高度序列一致 = True，聚类结果 ARI = 1.0000（应为 1.000）
  方法 average  | ARI(对真实) = 0.4694 | 轮廓系数(手写/sklearn) = 0.6869 / 0.6869 | cophenetic(手写/scipy) = 0.9174 / 0.9174 | 各簇样本数 = [105, 40, 55]
         手写 vs scipy 对照：合并高度序列一致 = True，聚类结果 ARI = 1.0000（应为 1.000）
  方法 ward     | ARI(对真实) = 0.4694 | 轮廓系数(手写/sklearn) = 0.6869 / 0.6869 | cophenetic(手写/scipy) = 0.9102 / 0.9102 | 各簇样本数 = [105, 40, 55]

【各链接方式对比汇总表】
    链接方式  ARI(对真实)  轮廓系数(手写)  轮廓系数(sklearn)  cophenetic(手写)  cophenetic(scipy)         各簇样本数
  single    1.0000    0.6723         0.6723          0.8585             0.8585  [95, 50, 55]
complete    0.4677    0.6940         0.6940          0.9170             0.9170 [105, 41, 54]
 average    0.4694    0.6869         0.6869          0.9174             0.9174 [105, 40, 55]
    ward    0.4694    0.6869         0.6869          0.9102             0.9102 [105, 40, 55]

sklearn AgglomerativeClustering(single) 与 scipy 的聚类结果 ARI = 1.0000（应为 1.000）
手写轮廓系数与 sklearn 的最大绝对偏差 = 0.00e+00（应约为 1e-12 量级）

手写合并记录 Z（前 5 次合并）——格式 [簇i, 簇j, 合并高度, 新簇样本数]：
  合并: 簇 159 + 簇 172，高度 0.0110，新簇样本数 2
  合并: 簇 166 + 簇 186，高度 0.0119，新簇样本数 2
  合并: 簇 157 + 簇 168，高度 0.0199，新簇样本数 2
  合并: 簇 6 + 簇 18，高度 0.0256，新簇样本数 2
  合并: 簇 40 + 簇 57，高度 0.0279，新簇样本数 2

【树状图切割】k = 3 的切割阈值 h = 0.8757（介于排序后第 197 与第 198 小的合并高度之间）
5 张图已保存到 figures/ 目录：hc_dendrogram.png、hc_scatter.png、hc_linkage_compare.png、hc_dist_heatmap.png、hc_silhouette_bar.png

逐项解读：

单链接 ARI = 1.0000：单链接把哑铃（A + 桥 + B）完整识别成一个连通结构，C、D 各成一类，与真实标签完全一致。为什么能成功？看合并高度序列：哑铃内部所有合并（球内最近点、桥的逐步衔接）高度都小于 0.9，而 C 与 D 之间最近的"搭桥"距离约 0.90、哑铃与 C/D 大块合并的高度约 4.24——树状图自然先完成哑铃、再各自完成 C 和 D，切割阈值 h = 0.8757 恰好切在"C/D 尚未搭桥"的空档上。
全链接/平均链接/Ward 全部失败（ARI ≈ 0.47）：三种方法的错误方式一致——C 与 D 中心距只有 4，被先合并成一个大簇（105 个样本）；而哑铃两球 A、B 之间隔着 6 的距离，全链接/平均链接/Ward 认为它们"整体上不够近"，在 3 类切割下把哑铃拦腰拆成两半（41 与 54，或 40 与 55，视链接方式而定）。这正是 1.3 节"链式效应 vs 拦腰切碎"的教材级演示。
轮廓系数的"背叛"：单链接结构完全正确（ARI = 1.0000），轮廓系数却最低（0.6723）；全链接结构错误、轮廓系数反而最高（0.6940）。原因：轮廓系数偏好紧凑凸簇，哑铃细长（簇内平均距离大）被系统性低估。结论：评价指标要结合结构真值/业务理解，不能只看轮廓系数。
cophenetic 相关系数的"背叛"：平均链接 cophenetic 最高（0.9174），单链接最低（0.8585），但分类正确性恰好相反。原因：单链接的链式合并把"隔着 6 的两个球"压成低合并高度，树状图对距离的保真度天然偏低。结论：cophenetic 高 ≠ 分类正确，它只衡量树状图是否忠实再现距离矩阵。
手写 vs scipy：三种链接方式的合并高度序列全部一致、聚类结果 ARI 全部为 1.0000，证明手写的 Lance-Williams 实现与 scipy 的 linkage 是同一套算法。
sklearn vs scipy：AgglomerativeClustering(linkage="single") 与 scipy 切割结果 ARI = 1.0000，三个库互相印证。
手写轮廓系数与 sklearn 最大偏差 0：手写公式与 sklearn 内部实现完全一致。
各簇样本数：单链接给出 [95, 50, 55]，与真实结构一一对应；全/平均/Ward 给出 [105, 40~~41, 54~~55]（哑铃被拆 + C/D 被合并），数字本身就是诊断线索。

7.2 五张图的解读（本例）

图①（树状图）：红色虚线在 h = 0.88 处横切一刀，与 3 条竖线相交 → 3 类。底部两簇高高的"长枝"分别对应 C、D 两个大簇；哑铃由大量低高度合并（高度均小于 0.9）拼接而成，直观展示了"链式效应"——一连串低高度的小步合并，而不是一次高高度的大合并。
图②（切割结果散点图）：三种颜色完整勾勒出"哑铃 + C + D"，红色 ✕ 数量为 0，ARI = 1.000。
图③（对比面板）：单链接把哑铃连成一体（ARI = 1.000）；全链接/平均链接把哑铃从中切开、并把 C、D 合成一类（子图标题 ARI ≈ 0.47）；Ward 同样失败——链接方式绝不是"随便挑一个"。
图④（热力图）：样本按聚类结果重排后，沿对角线出现三个清晰的深色块（块内距离小），块间浅色（簇间距离大）；哑铃块细长（横跨 95 个样本），与其连通结构一致。
图⑤（指标条形图）：三根柱子三种口径——ARI 说单链接最好（1.000），轮廓系数说全链接最好（0.694），cophenetic 说平均链接最好（0.917）。单看任何一个指标都可能被误导，这正是本例最有价值的教训。

7.3 常见坑与应对

链接方式选择不当（本例就是教材级案例）：默认无脑用平均链接或 Ward，遇到连通结构数据必然出错。应对：先画散点图观察结构——连通/细长用单链接，紧凑球形用全链接/Ward，拿不准时三种都跑一遍、对比指标并解释选择理由（这本身就是竞赛论文的加分点）。
距离度量需配合标准化：特征量纲不同（如"收入（元）"与"年龄（岁）"）时，欧氏距离完全由大数值特征主导，聚类结果没有意义。应对：聚类前对每列特征做 z-score 标准化（ $\frac{x_j - \bar{x}_j}{s_j}$ ）；只有相似度矩阵时用非欧度量（余弦、Jaccard）也要统一到"距离越大越不相似"。
样本量大时矩阵爆炸： $n = 10^5$ 时距离矩阵约 40 GB（双精度）， $n = 10^6$ 约 4 TB。应对： $n > 10^4$ 改用 K-means/DBSCAN/BIRCH，或先随机抽样在小样本上做层次聚类定 K，再回大样本上跑 K-means。
树状图切割位置主观："横切一刀"的位置不同，簇数就不同。应对：不要拍脑袋切——结合①合并高度跳变（跳变区间内切）；②轮廓系数随 K 的变化曲线（取峰值）；③业务含义（每类能否解释、命名）；并在论文中写明切割依据。
无真实标签时用不了 ARI：竞赛题目通常没有真实标签，ARI 只用于仿真自检。论文中应以轮廓系数、cophenetic 相关系数、各簇业务可解释性为主论证聚类质量，ARI 仅在"算法对比实验"（如手写 vs 库实现）中作为一致性指标使用。
把 cophenetic 高当成分类正确：如 7.1 所示，平均链接 cophenetic 最高却分错了类。cophenetic 只回答"树状图是否忠实保留距离结构"，不回答"切割出来的类是否合理"。
Ward 与非欧度量的兼容性：Ward 的方差最小化推导只对欧氏距离成立；用其他距离时 scipy 会直接报错（sklearn 要求 affinity="euclidean"），此时应改用平均链接。
合并不可逆的连锁污染：早期噪声点被错误并入某簇后无法纠正。应对：聚类前做去噪/标准化，必要时用 DBSCAN 先剔除噪声点，再做层次聚类。

7.4 竞赛论文写作建议（话术模板）

建模段（本文数据实例版，数值与 7.1 节运行输出一致）：

由数据散点图可知，样本呈"两个球形团块经一条稀疏桥连接、另有两个独立团块"的哑铃形态，聚类需保持连通结构，故采用层次聚类（欧氏距离、单链接）。按树状图横切一刀（切割高度 $h = 0.876$ ）得到 3 类，各类样本数分别为 95、50、55，与仿真设定的真实类别对比，调整兰德指数 $ARI = 1.000$ ，聚类结果完全正确。

对比论证段（评审加分点）：

进一步对比单链接、全链接、平均链接三种簇间距离定义：全链接与平均链接在切割为 3 类时均将哑铃结构拦腰截断、并将邻近两团块合并为一类（ $ARI \approx 0.47$ ），说明这两种链接方式不适用于连通型结构数据。单链接的 cophenetic 相关系数虽为四种方法中最低（ $c = 0.858$ ，链式合并压缩了合并高度），但对数据结构的划分最准确。可见链接方式的选取需结合数据结构判断，而非只看单一指标。

指标段（通用模板，⟨ ⟩ 内替换为自己的数值；示例值非本例输出，仅供参考格式）：

采用层次聚类（欧氏距离、平均链接）对样本聚类，cophenetic 相关系数 ⟨0.86⟩ 表明树状图较好地保留了原始距离结构，按树状图切割为 ⟨4⟩ 类，轮廓系数 ⟨0.58⟩，聚类结构合理。各类样本数分别为 ⟨n₁, n₂, …⟩，结合业务含义，将各类分别命名为 ⟨…⟩。

八、延伸阅读

BIRCH：为大规模数据设计的层次聚类近似算法。用 CF 树（聚类特征树）增量扫描数据，把层次聚类做到近似 $O(n)$ ，内存可控，适合 $n$ 非常大又想要"层次感"的场景。sklearn 的 Birch 可直接调用，竞赛中可作为"大样本想用层次聚类"的备选方案。
DBSCAN（下一篇，第 25 篇）：基于密度的聚类，自动发现任意形状的簇并标记噪声点，恰好补上层次聚类"怕噪声、怕大样本"的两块短板。竞赛中常与层次聚类配套出现：DBSCAN 出主体划分，层次聚类出谱系结构。
谱聚类：把样本看作图的节点，用相似度构造拉普拉斯矩阵，取其特征向量再做 K-means。能切出非凸簇，但计算量约 $O(n^3)$ （近似算法可降低），适合小到中样本的高难度形状数据。
Ward 方法原理：每次合并选择使簇内离差平方和（ESS）增量最小的一对簇。两簇合并的方差增量为

$\Delta ESS(G_i, G_j) = \frac{n_i\, n_j}{n_i + n_j}\, \left\|\bar{x}_i - \bar{x}_j\right\|^2$

即"加权中心距离的平方"——中心近、规模小的两簇优先合并，因此倾向生成球形、大小均衡的簇。Ward 只适用于欧氏距离，其 Lance-Williams 参数见 1.4 节表格。 5. 推荐资源：scipy 官方文档 scipy.cluster.hierarchy（linkage、dendrogram、fcluster 的 API 与全部链接方式说明）；sklearn 用户指南 Clustering 一章（含层次聚类与各方法对比图）；《统计学习导论》（ISLR）第 12 章无监督学习；姜启源等《数学模型》聚类分析章节。

一、算法含义​

1.1 通俗理解​

1.2 两种构建方向​

1.3 簇间距离的三种链接方式​

1.4 距离矩阵与合并过程​

1.5 树状图（dendrogram）​

1.6 优缺点​

二、何时使用（适用场景与条件）​

2.1 适用场景​

2.2 竞赛典型题目​

2.3 使用前提​

2.4 不适用情形​

2.5 与 K-means、DBSCAN 的对比选择​

三、算法指标​

3.1 轮廓系数（Silhouette Coefficient，评价聚类质量）​

3.2 cophenetic 相关系数（树状图保真度）​

3.3 各簇样本数​

3.4 不同链接方式的对比（提及）​

3.5 指标汇总表​

四、可视化图表​

4.1 图表总览​

4.2 好图与异常图的特征​

五、符号说明​

六、可运行程序（完整代码）​

七、结果解读与注意事项​

7.1 运行输出解读（以本例合成数据为例）​

7.2 五张图的解读（本例）​

7.3 常见坑与应对​

7.4 竞赛论文写作建议（话术模板）​

八、延伸阅读​