CSCI3230 L05 · Part 4/5 Agglomerative hierarchical clustering

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2026T1 本讲：L05，第 4 部分 / 共 5 部分 · 原件 L05-Clustering-2026T1.pdf（本地课件） p.54–77 定位：每次合并最近两簇，关键在如何更新簇间距离。前后：上一份 Density-based clustering · 下一份 Summary

从距离矩阵长出一棵树

自底向上与自顶向下（p.54–56）【新】

如果既不想先猜一个 $K$ ，也不想只得到一个固定尺度的分组，可以保留“哪些点先聚在一起、哪些小组后来才相遇”的全过程。这就是层次聚类的直觉。前置只需会读距离表、比较大小和求均值；无需先学树算法。

p.54 是分节页，p.55 对比两方向：**凝聚式（agglomerative）**先让每点自成一簇，再合并；**分裂式（divisive）**先把全部点放一簇，再拆分。本讲 p.56 选前者。

p.56 Starting with each item in its own cluster

有 5 点时先有 5 簇；每合并两簇，数量少 1，经过 4 次就剩一簇。但输出不是只要最后“全在一起”这句话，而是一棵记录每次合并的树状图（dendrogram）。从不同位置切这棵树，可以读出不同粒度的分组。

生物树与距离矩阵（p.57–59）

p.57 的生物树展示层次结构可以表达亲疏关系；它不是说任何距离聚类都能证明生物祖先。p.58 改用五个抽象样本，输入是两两距离。这里的 1、2、3、4、5 是样本名字，不是它们的一维坐标。

p.57左图的叶子依次标A–E，A与B先共享一个分叉，C与D共享另一个分叉，再由这两支共享更早的分叉，E在更早处分出；Branch point指分叉结点，Branch指连接的分支，右端是现生物种、左端指向祖先。右图用生命树形象展示生物信息学应用。图在这一页不提供物种间数值距离或祖先时间，不能把纸面枝长自行换成某个年代。

表（p.58）：原下三角矩阵按对称性补全，数字不变。

样本	1	2	3	4	5
1	0	2	6	10	9
2	2	0	5	9	8
3	6	5	0	4	5
4	10	9	4	0	3
5	9	8	5	3	0

第 2 行第 3 列是 5，表示样本 2 到样本 3 的距离。对角线的 0 是到自己的距离，选合并时忽略；上三角与下三角只是同一信息的两份。

现在出现 p.59 的问题：两个点的距离已知，两个簇的距离是什么？若簇 A 有两点、簇 B 也有两点，跨簇有四对点，选最小、最大还是平均？这个选择就叫 linkage（链接准则）。

最短、最长和平均（p.60–62）

p.59–63的原图是 $C_1=\{A,B\}$ 、 $C_2=\{C,D\}$ ，四条跨簇联系为AC、AD、BC、BD。图中最近是AC，最远是BD，因此single取 $d(A,C)$ ，complete取 $d(B,D)$ ；average取 $[d(A,C)+d(A,D)+d(B,C)+d(B,D)]/4$ ；centroid取 $d((A+B)/2,(C+D)/2)$ ，最后一式把A–D视为坐标向量。原图只给相对位置，没有给距离数值，所以下面的数字例另标补充。

先用一组补充自取的一维簇看差异： $A=\{0,2\}$ ， $B=\{5,9\}$ 。跨簇点对距离为 5、9、3、7，共四项。

Single linkage 取最近点对，距离 3：只要有一对靠近，就允许两簇较早合并。
Complete linkage 取最远点对，距离 9：要把最远的成员也考虑进去，要求更严格。
Average linkage 取全部四项平均， $(5+9+3+7)/4=6$ ：既不只看一条近边，也不只看最远边。

数学上，令 $C_1,C_2$ 是两个非空簇， $\lvert C_1\rvert$ 是第一个簇有几个点，则

d_{\mathrm{avg}}(C_1,C_2)=\frac{\sum_{x\in C_1}\sum_{y\in C_2}d(x,y)}{\lvert C_1\rvert\lvert C_2\rvert}.

两个求和符号表示“第一个簇每个点都配第二个簇每个点”；分母是点对总数。输入是两组点，输出仍是一个距离数。不是先平均坐标再求距离。

合并后为什么要按人数加权？ 若 A 有 2 点、B 有 1 点，A 到 C 的平均距离是 4，B 到 C 是 10（补充自取），来自 A 的跨簇点对有来自 B 的两倍。因此合并后是 $(2\times4+1\times10)/3=6$ ，不是 7。

一般地，把所有跨簇距离之和分成“来自 A”和“来自 B”两批，得到

\begin{aligned} d_{\mathrm{avg}}(A\cup B,C) &=\frac{\lvert A\rvert\lvert C\rvert d_{\mathrm{avg}}(A,C)+\lvert B\rvert\lvert C\rvert d_{\mathrm{avg}}(B,C)}{(\lvert A\rvert+\lvert B\rvert)\lvert C\rvert}\\ &=\frac{\lvert A\rvert d_{\mathrm{avg}}(A,C)+\lvert B\rvert d_{\mathrm{avg}}(B,C)}{\lvert A\rvert+\lvert B\rvert}. \end{aligned}

第一行还原“总距离 ÷ 总点对数”，第二行约掉共同的 $\lvert C\rvert$ 。这样记就不必死背权重位置。

质心与第一次合并（p.63–65）

Centroid linkage先各自平均坐标得到中心，再计算两个中心的距离。它与 average 不同：补充自取 $A=\{0,4\}$ 、 $B=\{2\}$ ，两个中心都为 2，质心距离为 0；但两对原点距离为 2、2，平均点对距离为 2。

回到课件五点矩阵。p.64 重列数据，p.65 找到最小非对角数是 2，对应样本 1、2，于是合成簇 {1,2}，记录合并距离 2。这一步各簇还是单点，所以常见 linkage 都给同一第一次选择；后续就未必相同。

更新矩阵与第二次合并（p.66–68）

课件这条完整演示选 single linkage。合并 1、2 后，旧的两行两列移除，新簇到 3 的距离取 $\min(6,5)=5$ ；到 4 取 $\min(10,9)=9$ ；到 5 取 $\min(9,8)=8$ 。每个 min 的两项都来自原矩阵。

当前簇	{1,2}	{3}	{4}	{5}
{1,2}	0	5	9	8
{3}	5	0	4	5
{4}	9	4	0	3
{5}	8	5	3	0

p.66 后两行印出的原距离下标有笔误：到 4 应取 $d_{1,4},d_{2,4}$ ；到 5 应取 $d_{1,5},d_{2,5}$ 。数值 9、8 与原矩阵一致，不能照错下标重新取出另一组数。

此时全表最小非对角数是 3，对应 {4}、{5}，所以 p.67 第二次合并 {4,5}，不是让刚形成的 {1,2} 每次都优先参加。p.68 更新后只剩三簇：

当前簇	{1,2}	{3}	{4,5}
{1,2}	0	5	8
{3}	5	0	4
{4,5}	8	4	0

其中 $d(\{1,2\},\{4,5\})=\min(10,9,9,8)=8$ ，四项对应四个跨簇点对； $d(\{3\},\{4,5\})=\min(4,5)=4$ 。没有参与合并的簇之间距离保持不变。

最后两步与树状图（p.69–71）

三簇表的最小距离是 4，于是合并 {3} 与 {4,5} 得到 {3,4,5}。剩下两簇的距离是 $\min(5,8)=5$ ，最后在距离 5 合并全部。

合并次序	合并前两簇	距离	合并后剩几簇
1	{1} 与 {2}	2	4
2	{4} 与 {5}	3	3
3	{3} 与 {4,5}	4	2
4	{1,2} 与 {3,4,5}	5	1

课件 p.65–71 的树横放，距离刻度在横轴；其他书常把距离画成纵轴高度。读图应先找标有 Distance 的轴，不能背“总看竖直高度”。下面自画文本树保留相同合并关系：

全部，在距离 5 合并
├─ {1,2}，在距离 2 合并
│  ├─ 1
│  └─ 2
└─ {3,4,5}，在距离 4 合并
   ├─ 3
   └─ {4,5}，在距离 3 合并
      ├─ 4
      └─ 5

若只接受距离不超过 3.5 的合并，就保留 {1,2}、{3}、{4,5} 三簇；阈值 4.5 则得到 {1,2} 与 {3,4,5} 两簇。课件横放树应沿等距离线竖切；纵放树才是水平切。两点在纸面位置接近不等于距离小，必须看它们第一次共享的合并结点。

补充 · 平均连接不是把两个旧平均直接再平均（通识讲解；演示数据不属于原题）。

average linkage 对所有跨簇点对平均。若 A 有1点，B有3点，准备合并A和B，与另一簇C的距离应为 $(1d(A,C)+3d(B,C))/4$ ；这里 C 的成员数同时出现在两个点对总数中，约掉后得到按 A、B 大小加权。

演示旧距离分别为2和6，正确新距离是 $(2+18)/4=5$ ，直接算 $(2+6)/2=4$ 则让只有1点的 A 和有3点的 B 获得相同权重，改变了“所有点对同权”的定义。有些其他连接约定确实给两个子簇相同权重，但那是另一种规则，不能只因名称里都有平均就混用。

因此更新距离矩阵时，除了保存距离，还要保存簇大小。树状图记录合并历史；一旦这一步算错，后续最近簇的选择就可能改变，最后的图形再漂亮也无法补救定义不一致。

改变linkage就改变结构（p.72–74）

图（p.72）：同样八点，左图 single 通过最近点对逐步连起来，右图 complete 因最远点约束得到不同外层合并。p.73 同一肿瘤数据画出 average、farthest、nearest 三棵不同形状的树。看什么：树不是数据的唯一“自然答案”，linkage 把我们对“组间接近”的含义写进结果。

把p.72的具体差别写成集合：两图最内层都是{1,2}、{3,4}、{5,6}、{7,8}。single图接下来横向组合成{1,2,5,6}与{3,4,7,8}；complete图则纵向组合成{1,2,3,4}与{5,6,7,8}，最后都合成全部八点。p.73的鼠肿瘤数据（原页署Hastie等）在average、farthest、nearest下产生三棵树，nearest呈明显的逐点链入现象；没有同一阈值、标签和评价结果时，不能仅凭树更均匀就判定哪种科学结论更正确。

p.74 的基因表达图每行对应一个基因、横向表示不同条件或时间，颜色表示表达变化。把变化相似的行聚在一起，可以提出可能相关功能的线索；共同变化不是因果证明。这也提醒我们，距离之前仍有特征与尺度的选择。

p.74将这种应用具体称为microarray（微阵列）测量不同条件下的基因活性；图上横轴标time，右侧以A–E括出若干表达变化相近的组，出处写Eisen等、PNAS 1998。颜色块与左侧树须一起理解：树把表达轨迹相近的行排在一起，颜色显示它们随时间的变化。本页没有提供颜色的完整数值标尺，不能从亮度读出精确表达倍数。

补充：质心连接的合并高度可能向下走

自编三个二维点 $A=(-1,0),B=(1,0),C=(0,1.8)$ 。AB距离为2，AC与BC均为 $\sqrt{1+3.24}=\sqrt{4.24}\approx2.0591$ ，所以先合并AB，合并高度为2。新簇质心为 $(0,0)$ ，到C的质心距离为1.8，下一次合并高度反而比2低。

这个现象叫合并高度倒置，说明“树上越往后合并，距离一定越大”不是所有linkage共有的性质。原因是新质心是新位置，原有点对都较远，不代表它们的平均位置也较远。若使用single或complete，本例第二次分别取跨簇最小或最大距离，均为约2.0591，不会得到1.8。

因此读树状图时要同时读连接定义。对标准单、全、平均连接，通常可以按单调合并高度理解水平切割；质心连接出现倒置时，简单“某高度以上都更远”的解释需要额外小心。这个补充并不改动课件的原矩阵例，而是解释为什么不能把其中一种树形直觉推广到全部准则。

优点与课堂题（p.75–76）

优点是一次输出多个尺度，不必一开始给 K；给定矩阵、linkage 和确定的平局规则，过程可以重算。若最小值有并列，则必须交代挑选方式，否则“相同输入结果唯一”不完整。

题面（L05-Clustering-2026T1.pdf，p.76）：

p.76 Suppose Cluster 1 contain $\{(-1,0)^T,(1,0)^T\}$ . Cluster 2 contain $\{(2,0)^T,(5,0)^T\}$ . If we apply the single-linkage clustering, what is the distance between the two clusters.

原题选项：A 为 0，B 为 1，C 为 2，D 为 3。

公式按原件重排。先列全四对，再选所要求的统计量。

参考答案

四对欧氏距离为 3、6、1、4，single 取最小值 1（原选项 B）。若改问 complete 才取 6；average 为 $14/4=3.5$ 。不要看见“cluster”就先求均值，只有 centroid linkage 才先平均坐标。

不可撤销与复杂度表（p.77）

普通凝聚过程把两个簇合并后，不会再拆开改分。早期一条近边造成的不合适合并会进入后续树。这与 K-Means 每轮允许样本重新换组不同。

表（p.77）：课件给出的复杂度摘要；这些数值有实现条件，不是任意三重循环代码的保证。

方法	课件准则	课件时间复杂度	课件备注
Single	最近点对	$O(n^2)$	链式效应
Complete	最远点对	$O(n^2\log n)$	对噪声敏感
Average	全部跨簇点对平均	$O(n^2\log n)$	称适合多数应用；不是普遍定理
Centroid	质心间距离	$O(n^2\log n)$	可能出现合并距离倒置

$n$ 是样本数。单存完整距离矩阵就有 $n^2$ 个位置，这已经比只存几个中心昂贵。若实现每一步重新扫描整个矩阵，还会带来额外成本，不能直接套表中优化实现的界。

补充小检查： 合并簇 A（3 点）与 B（1 点），它们到 C 的 average 距离分别为 2 和 10，新距离是 6 吗？

参考答案

不是。A 贡献的跨簇点对是 B 的三倍，所以为 $(3\times2+1\times10)/4=4$ 。6 是对两个旧平均数等权，遗失了簇大小。先还原“距离总和”，再除“点对总数”即可自检。

历史矩阵题可见附录 A1，重点练每次更新而不是只画最后的树。

本讲核心考点

把点间距离和簇间 linkage 分开，解释 average 与 centroid 的差别（p.58–63）。
每合并一次都更新矩阵，并记录距离与簇数（p.64–71）。
读树先找距离轴；图的横竖方向不改变合并关系（p.65–71）。
平局、不可撤销和复杂度都需要明确约定（p.75–77）。

附录

A1 作业/往年题演练（非讲义内容）：三道完整计算题

历史题先做一张事件表：第几次、合并谁、距离多少、剩几簇。完成事件表再画树，避免为了画得好看而改变合并次序。Average 题在每个新簇名字旁写成员数；Single 题保留“最小距离来自哪对原点”的记录。下面的等距情况要实际检查它们是否共享簇：不共享的两次合并可能只交换执行顺序，共享簇的平局则可能改变后续结构。

题面（HW02-2025T1-题目.pdf · Q4 · p.4）

p.4 4. Use the distance matrix in the following table to perform the hierarchical clustering with the group average distance. Show your results by listing all intermediate updated table and drawing the final dendrogram. The dendrogram should clearly show the order in which the points are merged. (20%)

表（题面，p.4）：原题下三角矩阵

	A	B	C	D	E
A	0
B	8	0
C	6	7	0
D	2	3	9	0
E	1	6	5	4	0

HW02-2025T1-题目.pdf p.4 Q4，A 级。题面： 五对象A–E的下三角距离为AB8,AC6,AD2,AE1,BC7,BD3,BE6,CD9,CE5,DE4。使用group average凝聚聚类，给中间距离矩阵与树状图。

第一次AE距离1。剩{AE},B,C,D，上三角依次：AE-B=(8+6)/2=7，AE-C=(6+5)/2=5.5，AE-D=(2+4)/2=3；B-C=7,B-D=3,C-D=9。存在距离3平局，以下约定先合并AE与D。

第二次形成AED，高度3。剩AED,B,C，距离AED-B=(8+6+3)/3=17/3；AED-C=(6+5+9)/3=20/3；B-C=7。第三次AED与B，高度17/3。剩AEDB与C，距离(6+5+9+7)/4=27/4，最后高度27/4合并。树为((((A,E)@1,D)@3,B)@(17/3),C)@(27/4)。

若第二步先BD，则AE到BD为(8+2+6+4)/4=5；AE到C5.5；BD到C8。第三步AE与BD高度5，最后同为27/4。两棵树都由题目未指定的平局引起，需交代约定。核对每次平均分母为跨簇点对数量。

题面（ESTR-Final-Exam-2023T1.pdf · Part III Q2 · p.7；扫描件，视觉读取）

p.7 2. (8%) This question is about clustering. Given five data points with the following matrix of Euclidean Distance, use agglomerative hierarchical clustering to cluster them.

a) If use Single Linkage, write down the clustering results in a dendrogram, and also give the updated matrix of distance for each step. (3%)

b) Besides Single Linkage, are there other methods to compute the distance between clusters? State the names of the linkage and explain their definitions. (3%)

c) Besides Euclidean distance (L2-norm), there are other similarity measurements such as Manhattan Distance (L1-norm) and Minkowski Distance (p-norm). Write down the mathematical formula of p-norm, and explain why it is a general description of L1-norm and L2-norm. (2%)

表（题面，p.7）：距离矩阵

	1	2	3	4	5
1	0.0
2	2.0	0.0
3	6.0	5.0	0.0
4	10.0	9.0	4.0	0.0
5	9.0	8.0	5.0	3.0	0.0

(a) 使用本讲 p.60 的最小跨簇距离。先合并 1、2，高度 2；新距离 $d(12,3)=\min(6,5)=5$ 、 $d(12,4)=\min(10,9)=9$ 、 $d(12,5)=\min(9,8)=8$ 。完整更新矩阵为

	12	3	4	5
12	0	5	9	8
3	5	0	4	5
4	9	4	0	3
5	8	5	3	0

接着 4、5 以高度 3 合并； $d(12,45)=\min(10,9,9,8)=8$ ， $d(3,45)=\min(4,5)=4$ 。

	12	3	45
12	0	5	8
3	5	0	4
45	8	4	0

第三步合并 3 与 45，高度 4； $d(12,345)=\min(6,10,9,5,9,8)=5$ 。

	12	345
12	0	5
345	5	0

最后高度 5 合并，矩阵只剩一个 0。示意图（原题 p.7 的计算结果，我画的，非原图）：

全部 @5
├─ {1,2} @2
│  ├─ 1
│  └─ 2
└─ {3,4,5} @4
   ├─ 3
   └─ {4,5} @3
      ├─ 4
      └─ 5

(b) Complete 取跨簇最远点对，Average 平均全部跨簇点对，Centroid 比较两簇成员均值的距离。检查区别：Average 的分母是两簇大小乘积，Centroid 只在求完中心后计算一次距离。

d_p(a,b)=\left(\sum_{j=1}^n\lvert a_j-b_j\rvert^p\right)^{1/p},\quad p\ge1.

代 $p=1$ 得绝对差之和，即 L1；代 $p=2$ 得平方和开根号，即 L2，分别对应本讲 p.8–9。这里逐步重新计算，避免只借正文的同矩阵结论跳过该题。

题面（Final-Exam-CSCI3230-Record-2025T1-官方节选.pdf 及 ESTR 同题 · Part II Q5 · PDF p.3；扫描件，视觉读取）

p.3 5. (6%) The following is the distance matrix for 5 data points (A, B, C, D, E). The matrix defines the minimum distance (single-linkage) between any two clusters.

Use the agglomerative hierarchical clustering algorithm (single-linkage), write down the complete merge process step by step. (4%) Draw the dendrogram that corresponds to the complete merge process. The dendrogram should clearly show the merge order and the merge distances on the vertical axis. (2%)

表（题面，p.3）：原题下三角矩阵

	A	B	C	D	E
A	0
B	3	0
C	9	7	0
D	6	4	5	0
E	10	8	4	6	0

2025两份官方节选 PDF p.3（卷面p.6）Part II Q5，A 级。题面： A–E下三角为AB3,AC9,AD6,AE10,BC7,BD4,BE8,CD5,CE4,DE6，使用single linkage画树并标合并距离。

先AB，高度3。剩AB,C,D,E：AB-C7，AB-D4，AB-E8，C-D5，C-E4，D-E6。两对距离4并列；可先ABD，高度4，剩ABD,C,E：ABD-C5,ABD-E6,C-E4；再CE，高度4；最后ABD与CE距离min(9,10,7,8,5,6)=5。树为(((A,B)@3,D)@4,(C,E)@4)@5。两次高度4交换顺序不改变这棵层次结构。核对最后距离5来自D-C。

返回正文

来源与证据

原件：L05-Clustering-2026T1.pdf（本地课件）；对应页区间见文件头及各节标题。本页正文按 PDF 实际页号阅读；L05 当前文件共 80 页。
数字演示凡非课件原例均明确标为“补充自取”；这些例子用于理解，不是教师布置的作业。
附录中的历史题面保留其文件名、年份和题号，与当前作业区分；它们不能证明本学期考试范围。正文的学习检查是通识练习，不作出题预测。