COMP5318 Week 09 聚类（K-means、GMM 与层次聚类）讲课总结

Posted on In , Word count in article: 1.5k Reading time ≈ 5 mins.
COMP5318 Week 09 讲课总结，整理聚类的定义（无监督、类内相似类间相异）与应用、欧氏/曼哈顿/余弦距离、质心与中心点、 五种簇间距离、聚类算法分类；K-means 三步算法与距离矩阵手算题、初始化敏感性与 K-means++、空簇与离群点、二分 K-means、 对非球形/不同大小/不同密度簇的失效；GMM 的 EM 算法与软分配；凝聚式层次聚类、单链/全链/平均链/Ward、树状图及复杂度， 以及 Lab 中 n_init、GMM 椭圆簇和 K-means 颜色压缩。

COMP5318 W09 考点速成：K-means、GMM 与层次聚类

用时约 15 分钟。考试分量很重：K-means 一轮大题（PE1 Q33）、层次聚类大题（PE2 Q33）、GMM 隶属度、链接距离。对应 PE1 Q24、Q25、Q33，PE2 Q24、Q25、Q33。更多手算练习在 W10 聚类手算。 不考：基于密度 / 网格的聚类、聚类评估（Clustering II，Ed 帖 225）。

一、知识点

1. 基本概念

  • 聚类 = 无监督；好聚类 = 高内聚（簇内距离小）+ 高分离（簇间距离大）。
  • 质心 centroid = 簇内点坐标的均值（通常不是真实点）；中心点 medoid = 最居中的真实点。
  • 三类算法：划分式（K-means）、基于模型（GMM）、层次式（凝聚 / 分裂）。

簇间距离

方法 定义 倾向
Single link 跨簇点对的最小距离 一个点一个点「链」上去，可发现非球形簇
Complete link 跨簇点对的最大距离 紧凑、大小相近
Average link 跨簇点对距离的平均 介于两者之间
Ward 合并后 SSE 的增量 与 K-means 目标一致

2. K-means

flowchart LR
  A["选 k 个初始质心"] --> B["把所有点分给最近质心"]
  B --> C["每簇逐坐标求均值 = 新质心"]
  C --> D{"质心变了吗？"}
  D -->|"变了"| B
  D -->|"不变"| E["结束"]
  1. 选 个初始质心；
  2. 用当前质心把所有点都分配完（每点去最近质心）；
  3. 每簇逐坐标取平均更新质心；质心不变就停，否则回到 2。
  • 目标：最小化簇内平方误差 ；平方欧氏距离下均值是最优代表点。
  • 比较距离时用平方欧氏即可，不必开方。复杂度 。
  • 对初始质心敏感 → 多次运行取 SSE 最小（n_init）、K-means++（下一个质心按 的概率选，倾向远离已选质心）、二分 K-means。
  • 必须事先给 ；对离群点敏感；只适合球形、大小相近、密度相近的簇（硬分配、凸簇、边界在两质心中点）。
  • 空簇：换一个质心（离现有质心最远的点，或从 SSE 最大的簇里挑）。

3. GMM

flowchart LR
  A["随机初始化 μ, σ, π"] --> E["E 步：责任度 γ = π·f / Σ π·f"]
  E --> M["M 步：用 γ 加权重估 μ, σ, π"]
  M --> C{"收敛？"}
  C -->|"否"| E
  C -->|"是"| R["每点得到软分配概率"]
  • 假设数据由 个高斯混合生成，一个高斯 = 一个簇；用 EM 估参数。
  • E 步：算每个点对每个分量的责任度（后验隶属概率）

（先验 × 密度，再归一化，和朴素贝叶斯一样。） - M 步：用 加权重估 、、。 - 和 K-means 对比：软分配 vs 硬分配；椭圆簇 vs 圆形簇；GMM 是 K-means 的推广。要「每个分量的隶属概率」就选 GMM。

4. 层次聚类

flowchart LR
  A["每点一簇 + 距离矩阵"] --> B["合并最近的两簇"]
  B --> C["更新矩阵：single 取 min / complete 取 max"]
  C --> D{"只剩一簇？"}
  D -->|"否"| B
  D -->|"是"| E["画树状图，按高度切得任意簇数"]
  • 凝聚式（自底向上，更常用）：每点一簇 → 反复合并最近的两簇 → 更新距离矩阵 → 直到一簇。分裂式（自顶向下）。
  • 结果画成树状图（dendrogram）；不需要事先指定簇数，在不同高度切即可。
  • 更新矩阵时用原始点对距离取 min / max / 平均。平局要有规则。
  • 缺点：空间 、时间 ；不是增量式；对噪声和离群点敏感（Ward 最敏感）。

二、考点

  1. ★★★ K-means 一轮：距离表 → 分配 → 质心。先全部分配完再更新。
  2. ★★★ 层次聚类合并顺序：找最小距离合并 → 按 single / complete 更新 → 再找最小。
  3. ★★★ 链接距离直接读：列出所有跨簇距离取 min / max / mean。
  4. ★★ GMM 责任度手算；GMM 给软分配。
  5. ★★ 平方欧氏下均值最优；K-means 对初始化敏感、K-means++ 怎么选初值。

三、题目

Q1（PE1 Q33，10 分大题） ，点 A(0,1)、B(2,1)、C(6,3)、D(8,3)，初始 ， 。(a) 每点到两个初始质心的平方距离和分配；(b) 更新后的两个质心。

  1. 到 / ：A 0 / 68，B 4 / 40，C 40 / 4，D 68 / 0 → 簇 1 = {A, B}，簇 2 = {C, D}。
  2. ， 。

Q2（PE2 Q33，10 分大题） 一维点 A = 0、B = 3、C = 8、D = 10。(a) 用 complete link，给出第一次合并、合并后到其余单点的距离、第二次合并；(b) 剩下两簇的 single-link 和 complete-link 距离，各由哪对点决定？

两两距离 AB 3、AC 8、AD 10、BC 5、BD 7、CD 2。 (a) 先合并 {C, D}（2）； ， ；再合并 {A, B}（3）。 (b) 跨簇距离 8、10、5、7：single = 5（B–C），complete = 10（A–D）。

Q3（PE1 Q24） 平方欧氏距离下，哪个代表点使固定簇内平方距离和最小？

簇内各点的逐坐标均值。

Q4（PE1 Q25） 两分量 GMM： ， ， ， 。分量 1 的后验隶属度？

0.462。0.12 是没归一化的分子，0.538 是分量 2。

Q5（PE2 Q24） 想得到每个分量的隶属概率，而不只是一个硬分配，哪个模型直接给出？

GMM。K-means 和树状图切割都是硬分配。

Q6（PE2 Q25） 一维簇 A = {0, 2}、B = {6, 8}，绝对距离。single-link 和 average-link？

跨簇距离 6、8、4、6 → single 4，average 24/4 = 6。

Q7（自拟） 5 个点的距离矩阵中 ， （顺序 A, B, C, D, E）。初始质心 A、B，第一轮分配？

C：7 vs 3 → B；D：10 vs 4 → B；E：1 vs 6 → A。结果 {A, E}、{B, C, D}。

Q8（自拟） K-means++ 怎么选第 2 个初始质心？

每个点被选中的概率 ∝ 它到最近已选质心距离的平方，所以倾向选远处的点。