CSCI3230 L05 · Part 2/5 K-Means

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2026T1 本讲：L05，第 2 部分 / 共 5 部分 · 原件 L05-Clustering-2026T1.pdf（本地课件） p.16–33 定位：交替分配与求均值使平方误差不增。前后：上一份 Clustering basics · 下一份 Density-based clustering

把迭代完整走一遍

K 是输入，中心是待求量（p.16–18）【新】

读完距离基础，我们已经能判断两点谁近。现在的问题是：如果想把点分成 $K$ 组，能不能每组放一个代表点，让成员尽量靠近它？这就是 K-Means 的出发点。

p.16 是分节页。p.17–18 中， $M$ 表示样本总数，每个样本有 $n$ 个坐标； $K$ 是事先选定的组数。第 $k$ 簇写作 $C_k$ ，它是点的集合；中心 $\mu_k$ 是一个 $n$ 维向量，不是簇的编号，也不一定是原样本。

先不要背目标函数。把算法理解为反复做两件事：

固定中心分配成员：所有点分别比较到各中心的距离，选择最近的那个。
固定成员移动中心：每一簇按坐标求均值，作为新中心。

p.18 Re-compute the centroids using the current cluster memberships.

“固定”很重要：不能看完第一个点就把中心移动，让后面的点使用另一组中心。一次完整迭代包括对全体点的分配和随后一次中心更新。后面我们会解释为什么均值是合适的代表。

第一轮：从不理想初值开始（p.19–21）

图（p.19–21）：六个二维点，两个初始中心。元素：左边三个点为 $(1,1),(2,2),(3,1)$ ，右边为 $(6,4),(7,5),(8,4)$ ；初中心却在 $(0,0)$ 和 $(3,3)$ 。看什么：人眼看到两团，并不意味着算法初始就知道正确成员。中心必须按给定数值开始，不能偷偷换成更漂亮的位置。

p.20 的初值不是全部来自样本，所以 p.18 的“选择样本为种子”是一种初始化办法，不是中心永远只能取样本位置的限制。以下沿课件记两簇为 0、1。

先算 $(2,2)$ ：到中心 0 的距离平方是 $2^2+2^2=8$ ；到中心 1 是 $(2-3)^2+(2-3)^2=2$ 。比较平方距离即可，因为开平方不会改变非负数的大小顺序。

点	到 $(0,0)$ 的距离平方	到 $(3,3)$ 的距离平方	选哪簇
$(1,1)$	2	8	0
$(2,2)$	8	2	1
$(3,1)$	10	4	1
$(6,4)$	52	10	1
$(7,5)$	74	20	1
$(8,4)$	80	26	1

第一轮并不是左右三三分；簇 0 只有一个点，簇 1 有五个。把每点选中的平方距离相加得 64，这个数描述的是“当前成员配旧中心”的误差，暂时不要拿它当最终误差。

更新后重新分配（p.22–24）

p.22 只移动中心，先不改变刚才的成员。簇 0 只有 $(1,1)$ ，均值仍是它。簇 1 有五个点，横坐标与横坐标平均，纵坐标与纵坐标平均：

\begin{aligned} \mu_{1,x}&=(2+3+6+7+8)/5=5.2,\\ \mu_{1,y}&=(2+1+4+5+4)/5=3.2. \end{aligned}

下标 $x,y$ 指坐标分量。不要把两坐标一起加成一个平均数，那样会把二维中心误变成一个数。

接下来 p.23 开始第二次分配，所有点使用新中心 $(1,1)$ 、 $(5.2,3.2)$ 。完整比较是：

点	到 $(1,1)$ 的平方距离	到 $(5.2,3.2)$ 的平方距离	新成员
$(1,1)$	0	22.48	0
$(2,2)$	2	11.68	0
$(3,1)$	4	9.68	0
$(6,4)$	34	1.28	1
$(7,5)$	52	6.48	1
$(8,4)$	58	8.48	1

例如 $(3,1)$ 原来属于簇 1，但新表中 4 小于 9.68，所以移到簇 0。成员是根据距离重算的，不是第一次分配后永久固定。

p.24 第二次更新：左簇中心为 $(2,4/3)$ ，右簇中心为 $(7,13/3)$ 。课件显示 1.3 和 4.3，是小数近似；手算保留分数更可靠。再次分配时左右三点均不改变所属簇，便得到 p.25 的稳定结果。

停止与目标（p.25–27）

为何要重复“分配、均值”？现在才引入衡量好坏的数：

J=\sum_{k=1}^{K}\sum_{x\in C_k}\lVert x-\mu_k\rVert_2^2.

$J$ 是一个非负标量，也称簇内平方误差和（SSE）。内层和把某簇每点离中心的距离平方相加；外层和把各簇再相加。输入是全部成员分配与中心，输出是一个“总共偏离了多少”的数。

分配步骤为什么不增大它？ 中心不动时，每一点的贡献只由它选哪个中心决定。选距离最小的中心，就使该点的贡献最小。把所有点的贡献相加，总和不会增加。

均值步骤为什么不增大它？ 先看一维，固定一个非空簇中的 $m$ 个数 $x_1,\ldots,x_m$ ，待选中心为 $u$ ：

\begin{aligned} J_C(u)&=\sum_{i=1}^{m}(x_i-u)^2,\\ \frac{dJ_C}{du}&=\sum_{i=1}^{m}2(u-x_i)\\ &=2mu-2\sum_{i=1}^{m}x_i. \end{aligned}

第一步对平方用链式法则： $(x_i-u)$ 的导数是 $-1$ ，于是负号把结果改写成 $2(u-x_i)$ 。令斜率等于零，移项并除以 $2m$ ，得到 $u=(\sum_i x_i)/m$ 。二阶导数为 $2m>0$ ，说明是最低点。二维及更高维的平方距离是各坐标平方项之和，所以每个坐标分别按这套步骤取均值。

课件六点例最终左簇的三项误差为 $10/9,4/9,10/9$ ，和为 $8/3$ ；右簇同样为 $8/3$ ，故最终 $J=16/3$ 。一路的误差为：旧初值分配后 64 → 第一次均值后 37.6 → 第二次分配后 22.24 → 第二次均值后 $16/3$ 。下降对应明确阶段，不是凭图形猜的。

停止可以看成员不变、中心变化很小、误差下降很小，或达到上限。每一步不增大 $J$ ，只说明在当前交替方式下改不动了，不保证所有可能分组中最好。不同初值可落到不同结果。

p.27 的复杂度 $O(IKMN)$ 中， $I$ 为迭代轮数， $K$ 为中心数， $M$ 为样本数， $N$ 为维数。每轮每个样本比较 $K$ 个中心，每次比较要算 $N$ 个坐标，于是相乘。存储数据与中心为 $O((M+K)N)$ 。原页 “Store N points” 应按同页符号理解为存 $M$ 个 $N$ 维点。有限步稳定还需要一致的等距处理及空簇约定。

补充 · 为什么平均数恰好适合平方误差（通识讲解；演示数据不属于原题）。

固定一簇成员后，取其均值 $\mu$ ，任意候选中心记为 $c$ 。每个偏差可拆成 $(x_i-\mu)+(\mu-c)$ 。平方后求和，中间项含 $\sum_i(x_i-\mu)=0$ ，于是

\sum_i\lVert x_i-c\rVert^2 =\sum_i\lVert x_i-\mu\rVert^2+n\lVert\mu-c\rVert^2.

第一项不随候选中心改变，第二项非负，因此非空簇在 $c=\mu$ 时取得最小值。演示一维点 0、2、4，均值2的误差为4+0+4=8；中心改为3，误差为9+1+1=11，增加量正好为 $3(3-2)^2=3$ 。

证明依赖的是平方欧氏距离。若把目标改成绝对距离，最优中心一般是中位数；不能改了距离仍沿用均值更新并声称原来的单调下降证明不变。空簇的 $n=0$ 也不能套“除以成员数求均值”，要另有初始化或重置约定。

补充：已经不再变化，为什么仍可能不是最好分组

自编数轴数据0、4、5、9，设 $K=2$ ，初中心2和7。按最近中心分配，0与4归左，5与9归右；各簇均值仍为2和7，因此下一轮不再改变。SSE为 $(0-2)^2+(4-2)^2+(5-7)^2+(9-7)^2=16$ 。

但另一个合法分组是 $\{0\}$ 与 $\{4,5,9\}$ ，中心为0与6，SSE为 $0+4+1+9=14$ ，比16小；其最近中心分配也稳定。这是“停止”与“全局最优”不同的完整反例，不需要靠一幅图猜测。第一次分配后交替优化只保证每步不让当前目标上升，并没有保证跨越所有可能分区去找最小者。

当分组不变，均值更新没有变化，确实达到当前分组的最优中心；这句话的限定词是“当前分组”。随机多次初始化能增加发现更好解的机会，但有限次重启仍不是一般的全局最优证明。比较重启结果应固定同一数据、同一 $K$ 、同一目标，再看SSE；不能把不同 $K$ 的更小SSE直接当作初始化更成功。

优点与K、空簇问题（p.28–30）

p.17注明K-Means（MacQueen, 1967）是划分型算法。p.28列出的优点除了高效，还包括容易理解和实现、可扩展到大型数据、达到收敛、中心与簇容易解释或可视化，以及有时比层次聚类得到更紧的簇。最后一项是“may”，取决于数据、linkage和所用紧密性指标；收敛也不等于全局最优。

p.28 的“快”有条件： $K$ 、迭代数和维数固定时，增加样本数所需工作大致成正比。p.29 的两图把 $K=3$ 改成 4，同一团可被继续切开； $K$ 改变了我们要求算法交付什么。

补充自取：数轴点 0、2、10、12，若 $K=1$ ，中心为 6，SSE 为 $36+16+16+36=104$ ；若按两团取 $K=2$ ，中心为 1、11，SSE 为 4；若每点各成一簇，SSE 为 0。不能据此说“每点一簇最好”，因为分组失去总结结构的作用。选择 $K$ 要结合用途，而不只追求训练 SSE 小。

p.29沿用六点图， $K=3$ 时左下 $(1,1)$ 自成一组， $(2,2),(3,1)$ 一组，右侧三点一组； $K=4$ 时右侧又把 $(7,5)$ 单列， $(6,4),(8,4)$ 同组。原图呈现的是不同 $K$ 下的候选结果，没有提供这两次运行的初值与全部迭代，不能把它们说成对应 $K$ 的唯一解。

图（p.30）：初中心 $(5,5)$ 、 $(10,10)$ ，六点都更靠近前者。元素：第二个中心没有任何成员。看什么：更新均值会遇到分母 0。可以重新选种子或采用明确规则，但不能假装空簇的均值是零，也不能默默删簇而仍声称保持原 $K$ 。

离群点、弯曲簇与课堂题（p.31–33）

p.31 远点会拉动均值。补充自取：一维 0、1、2 均值是 1，加入 97 后均值成 25；平方损失让远点贡献特别大。p.32 双弯月说明另一种问题：即使没有离群点，按最近质心分组也难跟随弯曲形状。这是形状假设不合适，不能靠简单多迭代自动修好。

p.31同时对照两种处理：上图把远离右团的离群点强行包进大椭圆，右团被拉长；下图把它留在两个主要团之外。原文说明离群点可能是记录错误，也可能是数值特殊但真实的对象，所以“离群”不等于“错误”。p.32则比较同一双弯月的原分组与K=2结果：最近中心切法把弯月中间的部分切到另一色，缺陷来自几何表示而不只是初始化。

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

p.33 Suppose we have three cluster centroids $\mu_1=(1,2)^T$ , $\mu_2=(-3,0)^T$ and $\mu_3=(4,2)^T$ . Furthermore, we have a training example $x^{(i)}=(-1,2)^T$ . After a cluster assignment step, which cluster will $x^{(i)}$ be assigned?

原题选项：1 Cluster 1；2 Cluster 2；3 Cluster 3；4 I Do Not Know。

公式按讲义重排。先自己算三个平方距离，再展开。

参考答案

到中心 1： $(-1-1)^2+(2-2)^2=4$ ；到中心 2： $(-1+3)^2+(2-0)^2=8$ ；到中心 3： $(-1-4)^2+(2-2)^2=25$ 。最小为 4，分到 Cluster 1（原题第一个选项）。这里只做分配，不需要重新求三个中心。

旧作业的平局与矩阵运算可见附录 A1。第一次学建议先把上面六点完整重算，再进入历史题。

本讲核心考点

完整一轮是先全体分配，再按新成员求均值（p.18–25）。
解释两步为何使 SSE 不增，区分局部稳定与全局最优（p.26–27）。
分别诊断 K、空簇、离群点与弯曲形状问题（p.29–32）；不是同一个缺陷。

附录

A1 作业/往年题演练（非讲义内容）：题面、解答与核对

历史演练的读法：先遮住下方分配列，按正文“每点一行、每中心一列”的表格自己算；再核对每点恰出现一次。求中心时先把某簇成员抄全，分别合计横、纵坐标，再除以该簇人数。遇到平局先写约定再继续；题目没指定规则时，应保留多种合法结果，而不是用答案倒推成员。以下题面与数值来自所标旧年份，不是 2026T1 当前作业。

题面（HW02-2025T1-题目.pdf · Q3(a) · p.3；图中坐标视觉读取）

p.3 3. Consider the following data and perform the K-means and DBSCAN algorithms using the Euclidean distance between points:

(a) Use K-means algorithm to perform three-class classification task. Assume that the initial cluster centers are (7, 4), (3, 6), (7,9) respectively. Calculate the updated cluster centers after the first iteration. (10%)

本题另有 (b)–(d) DBSCAN 三问，题面与演练在下一 Part 附录。原文称 classification，此处按其指定的 K-means 理解为聚类。

来源：HW02-2025T1-题目.pdf p.3 Q3(a)，A 级。题面完整数据转写： 图中a(1,2),b(2,3),c(2,4),d(6,5),e(3,1),f(3,3),g(4,4),h(7,6),i(8,8),j(8,9),k(9,4),l(5,9),m(4,7),n(6,8),o(6,4)。K=3，初中心(7,4),(3,6),(7,9)，计算第一次迭代的新中心。

点	到三中心的平方距离	分配
a	40,20,85	2
b	26,10,61	2
c	25,5,50	2
d	2,10,17	1
e	25,25,80	1或2，平局
f	17,9,52	2
g	9,5,34	2
h	4,16,9	1
i	17,29,2	3
j	26,34,1	3
k	4,40,29	1
l	29,13,4	3
m	18,2,13	2
n	17,13,2	3
o	1,13,26	1

约定平局选编号小的中心：C1={d,e,h,k,o}，均值(31/5,20/5)=(6.2,4)；C2={a,b,c,f,g,m}，均值(16/6,23/6)；C3={i,j,l,n}，均值(27/4,34/4)=(6.75,8.5)。若e给C2，前两中心改为(7,4.75)与(19/7,24/7)，同样符合未指定平局的题面。核对三簇成员数和15；不能偷偷略过e。

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

p.5 7. Use K-means to cluster the following five 2-dimensional data points: A (2,2), B (3,2), C (1,1), D (3,1), E (1.5,0.5). If the initial centroids are (2,2) and (1,1), and Euclidean distance is used. What are the two clusters after the first iteration? (2%)

来源：ESTR-Final-Exam-2023T1.pdf p.5 Part II Q7，A 级。题面： 五点A(2,2),B(3,2),C(1,1),D(3,1),E(1.5,0.5)，K=2，初中心(2,2),(1,1)，求第一次迭代结果。平方距离分别为A(0,2)、B(1,5)、C(2,0)、D(2,4)、E(2.5,.5)。因此第一簇ABD，中心(8/3,5/3)；第二簇CE，中心(1.25,.75)。核对每点各一次，中心为成员均值。

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

p.2 4. (3%) Which of the following statement is correct about clustering methods?

A. For DBSCAN, we must set the number of output clusters beforehand.

B. Agglomerative clustering is a top-down approach.

C. K-means can guarantee convergence given a finite number of data points.

D. None of the above.

按本讲有限数据、固定平局处理及正常空簇处理的 K-means 约定选 C。A 把 K-means 的输入 K 套到 DBSCAN；DBSCAN 以半径和 MinPts 决定密集连通区域。B 把 agglomerative 与 divisive 方向颠倒。C 说的是达到稳定分配或停止条件，不意味着求到全局最优；若人为在等距点间反复改分配而不固定约定，字面上的有限步收敛需要补条件。

返回正文

来源与证据

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