COMP5318 Week 10 Tutorial 聚类手算总结（Transformer 不考）

Posted on In , Word count in article: 683 Reading time ≈ 2 mins.
COMP5318 Week 10 总结。本周讲义 Transformer 在 2026 S2 不考（Ed #187、#212），正文已删除；只保留本周 Tutorial 10 的聚类手算：K-means 一次分配与质心更新、单链与全链层次聚类的完整距离矩阵更新与对比。

COMP5318 W10 考点速成：聚类手算练习（Transformer 不考）

用时约 10 分钟。本周讲义 Transformer 整周不考（Ed 帖 187、212），只保留 Tutorial 10 的聚类手算，是 W09 聚类的配套练习。

一、知识点（三条够用）

  1. K-means 一轮：用初始质心把所有点分配完，再逐坐标取平均更新质心；比较平方距离就够。
  2. Single link 取跨簇最小距离，complete link 取最大距离；每次合并后用原始点对距离更新矩阵。
  3. Single link 容易「链」成不平衡的大簇；complete link 偏紧凑、平衡。

二、考点

flowchart BT
  subgraph S["Single link"]
    a1["A"] --> ae["AE (1)"]
    e1["E"] --> ae
    ae --> abe["ABE (2)"]
    b1["B"] --> abe
    abe --> abce["ABCE (3)"]
    c1["C"] --> abce
    abce --> all1["全部 (4)"]
    d1["D"] --> all1
  end
  subgraph C["Complete link"]
    a2["A"] --> ae2["AE (1)"]
    e2["E"] --> ae2
    b2["B"] --> bc["BC (3)"]
    c2["C"] --> bc
    bc --> bcd["BCD (5)"]
    d2["D"] --> bcd
    ae2 --> all2["全部 (10)"]
    bcd --> all2
  end
  • ★★★ 写出每一步合并和更新后的矩阵（大题按步骤给分）。
  • ★★ 同一份矩阵 single 和 complete 的合并顺序可能完全不同。
  • ★ 检查平局。

三、题目

下面 Q2、Q4 用同一个距离矩阵：

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

Q1（T10 Ex.1） 同上矩阵但 D–E = 1，初始质心 A、B，K-means 第一轮分配？

C（7 vs 3）→ B，D（10 vs 4）→ B，E（1 vs 6）→ A。{A, E}、{B, C, D}。只有距离矩阵、没有坐标，算不了均值，所以不更新质心。

Q2（T10 Ex.2） 用 single link 做凝聚聚类，写出合并顺序和高度。

  1. {A}+{E}，高度 1；更新：到 B ，到 C ，到 D 。
  2. {A,E}+{B}，高度 2；更新：到 C ，到 D 。
  3. {A,B,E}+{C}，高度 3；到 D 。
  4. {A,B,C,E}+{D}，高度 4。

Q3（T10 Ex.3） A(1,1)、B(1,3)、C(4,2)、D(8,6)、E(10,6)，初始质心 A、D，做一轮 K-means。

平方距离到 A / D：A 0 / 74，B 4 / 58，C 10 / 32，D 74 / 0，E 106 / 4 → {A, B, C}、{D, E}。 新质心 (2, 2)， (9, 6)。

Q4（T10 Ex.4） 同一矩阵用 complete link，写出合并顺序和高度。

  1. {A}+{E}，高度 1；更新：到 B ，到 C ，到 D 。
  2. 最小是 B–C = 3 → {B}+{C}，高度 3；更新：{A,E}–{B,C} ，{B,C}–D 。
  3. {B,C}+{D}，高度 5。
  4. {A,E}+{B,C,D}，高度 。

Q5（对比） Q2 和 Q4 最后两大簇分别是什么？

Single：{A,B,C,E} 与 {D}（最后高度 4）；complete：{A,E} 与 {B,C,D}（最后高度 10）。