k-means 只做两件事：把每个点归给最近的中心，再把中心挪到名下所有点的平均位置。 两步反复， 直到中心不动。Demo 里惯性从 1955.70 掉到 199.78 就停了； k 从 1 加到 3，惯性 2109 掉到 200， 再加就只掉几十——那个拐点就是 k。 而一次坏初值能让惯性停在 1153.54，是正确解的 5.8 倍。
前面四个算法做的是「换坐标」，这一节开始做「分堆」。 分堆听起来简单，但它是无监督学习里最实用的一类——客户分群、图像压缩、异常检测都靠它。 k-means 是最古老也最快的版本，代价是它对「堆长什么样」有一套很强的假设。 下一节的混合高斯就是为了拆掉这些假设而出现的。
一、两步循环，就这么简单
k-means 的输入只有两样：数据 X 和簇的个数 k。输出是每个点的簇编号，以及 k 个中心。过程是这样的—— 第一步（分配）：把每个点归给离它最近的那个中心。 第二步（更新）：每个簇的中心挪到「属于这个簇的所有点的平均位置」。 然后重复，直到中心不再移动（或者移动小于一个阈值）。 它优化的目标函数叫惯性：每个点到它所属中心的距离平方和。 这两步各自都在让惯性变小——分配那一步是「固定中心，选最近的」，更新那一步是「固定分配， 均值就是平方误差最小的位置」。 所以惯性单调不增，算法一定会停。 停的原因是「再也找不到能让惯性更小的改动」， 而不一定是「找到了全局最优」。这两者的区别下面会说。 Demo 里惯性是这样掉的：1955.70 → 1095.73 → 377.93 → 199.88 → 199.78，第五轮之后就不动了。 前四轮干完了所有活，后面全是原地踏步。
二、k 该取几个：肘部法与它的局限
k 不是算出来的，是给的。这是 k-means 最尴尬的地方——它不会告诉你该分几堆。 那怎么办？ 最常见的办法叫肘部法：把 k 从 1 试到 10，每个 k 都跑一遍，画出惯性曲线。 惯性随 k 单调下降（簇越多，每个点离中心越近），但下降速度会在某个 k 之后突然变慢。 那个拐点就是「再多分也没多少收益」的位置。 Demo 的数：k = 1 时 2109.34，k = 2 时 1119.74，k = 3 时 199.78，k = 4 时 173.53。 从 2 到 3 掉了 920，从 3 到 4 只掉 26。 拐点清清楚楚在 3。 但肘部法有个致命局限：真实数据的曲线经常没有拐点，就是一个平滑的弧。 这时候你会盯着图看半天， 然后随便选一个。所以工程上还会配轮廓系数、Gap 统计量这些指标，但它们也都有各自的偏好。 最实在的判断标准其实不是数学，是用途。 做客户分群，分 5 群能落成 5 个运营策略就取 5； 分 12 群做不出 12 套动作，那就是分多了。k 是业务问题，不是数学问题。
三、初值：它能停在错误的地方
这是 k-means 最容易踩的坑。
Demo 里专门做了对照：把三个初始中心全塞进中间那团，跑完之后惯性是 1153.54，纯度 0.66；
随机 10 次取最好，惯性 199.78，纯度 1.0000。惯性差了 5.8 倍。
为什么会这样？
三个中心挤在同一团里，它们在那里抢同一批点，而另外两团没有任何中心去认领，
只能被硬塞进最近的簇。每一步都在让惯性变小，所以它心安理得地停在了这个糟糕的解上。
惯性下降只保证「比上一轮好」，不保证「比别的初值好」。
标准解法是多次随机初值，取惯性最小的那次。
scikit-learn 里这个参数叫 n_init，老版本默认 10，新版本改成了 'auto'。
跑十次 k-means 的成本远低于一次分错群的代价。
更进一步的办法是 k-means++：不再纯随机挑初值，而是让第一个中心随机，
后续每个中心都「离已有中心越远，越容易被选中」。
这把「初值全挤在一起」的概率压得很低，是现代实现的默认做法。
四、它假设了三件不一定成立的事
第一，簇是凸的、差不多圆的。 k-means 用欧氏距离划分， 划分出来的边界一定是直线（高维里是超平面）拼成的，所以每一块都是凸多边形。 遇到弯月形、长条形、同心圆，它一定切错。 第二，各簇大小差不多。 一个 1000 点的大团和一个 20 点的小团放一起， k-means 会为了照顾大团把小团并掉——因为惯性是所有点加起来算的，大团的误差权重大得多。 第三，各簇的「散度」差不多。 这个假设比前两个隐蔽。 一个又细又长的簇和一个又圆又小的簇，即使用同样的中心数， k-means 也倾向把细长的那个劈成两半—— 因为劈开它能降更多惯性。 下一节的混合高斯正是冲这一点来的。 这三条合起来就是一句话： k-means 假设「所有簇长得一样圆、一样大、一样散」，而且只承认直线边界。 数据不符合时它不报错， 只是默默给你一个错的答案。
五、动手 Demo：分堆、挪中心，反复到不动
三团点，每团 120 个，中心在 (0,0)、(4,0)、(2,3.6)，标准差 0.55。 数据本身很干净，这样才好单独观察算法行为——后面几段要看的不是「能不能分开」，而是「怎么分、 什么时候分错」。 代码就是两步循环，加上一个「跑十次取最好」的外壳。 另外单独做了一次「坏初值」实验：把三个中心全放进同一团里。
import numpy as np
for it in range(1, 9):
# 第一步：每个点归给最近的中心
D = ((X[:, None, :] - C[None, :, :]) * (X[:, None, :] - C[None, :, :])).sum(axis=2)
lab = np.argmin(D, axis=1)
# 第二步：把中心挪到它名下所有点的平均位置
C = np.array([X[lab == c].mean(axis=0) for c in range(3)])
print(it, ((X - C[lab]) * (X - C[lab])).sum()) # 惯性只会往下走
# 初值敏感：随机多次，取惯性最小的那次
best = None
for _ in range(10):
inertia, C1, lab1, _ = kmeans(X, 3, rg)
if best is None or inertia < best[0]:
best = (inertia, C1, lab1)
实跑输出：
--------------------------------------------------------------------
k-means：反复「分堆—挪中心」直到不动
--------------------------------------------------------------------
造三团点，每团 120 个。**k-means 只认一件事：每个点到它所属中心的距离平方和要小。**
它不知道「团」是什么，只知道要找一个让总距离最小的分法。
【一】惯性的下降：每次迭代都在往下走
迭代 惯性（簇内平方和）
--------------------------
1 1955.6983
2 1095.7273
3 377.9282
4 199.8821
5 199.7819
6 199.7819
7 199.7819
8 199.7819
第一轮掉得最狠，因为初值中心是随便挑的三个点；后面每一轮只微调，最后几乎不动了。
**惯性单调不增**是 k-means 的硬性质——分配和挪中心这两步，每一步都不会让总距离变大。
【二】k 该取几个：肘部法
k 惯性 纯度
------------------------------
1 2109.336 0.3333
2 1119.741 0.6667
3 199.782 1.0000
4 173.531 0.9972
5 154.590 1.0000
6 132.039 1.0000
k 从 1 加到 3，惯性掉得飞快（2109 到 200）；从 3 再加，只掉几十。**那个「拐点」就是 k。**
注意纯度那一列：k=3 就到 1.0000，再加大 k 也不会更高，k=4 甚至还略掉了——
**多出来的簇只是把一个真团切碎，不会让结果更准。**
而且真实场景里你手上没有 y，纯度根本算不出来，能用的只有惯性拐点。
【三】初值决定成败：一次坏初值能毁掉整个结果
初值 惯性 纯度
------------------------------------------------
三个中心全塞进中间那团 1153.541 0.6639
随机 10 次取最好 199.782 1.0000
三个中心全落在同一团里，它们三个在那里抢同一批点，**另外两团只能被硬塞进最近的簇**。
惯性 1154，是正确解（200）的 5.8 倍；纯度 0.66，比瞎猜（0.33）好一点，离 1.0000 差得远。
**k-means 停下来的时候，它并不知道自己停错了地方。**
所以实际用的时候必须「随机多次、
取惯性最小的那个」——这就是 k-means++ 和改进版里 n_init 参数的来历。
【四】它默认了三件不一定成立的事
**第一，簇是「凸的、差不多圆」的。**
k-means 用欧氏距离划分，划分出来的区域一定是直线切出来的多边形，
遇到弯月形或者长条形就会切错——下一节的混合高斯就是补这一点的。
**第二，各簇大小差不多。**
一个 1000 点的大团和一个 20 点的小团放在一起，k-means 会为了照顾大团把小团并掉。
**第三，k 得你自己给。**
它不会告诉你该分几堆，肘部法也只是个经验办法，数据一乱那个拐点根本看不出来。
惯性表要看「第几轮不动」。1955.70 → 1095.73 → 377.93 → 199.88 → 199.78，第五轮之后一模一样。 四轮干完所有活，这是 k-means 快的原因之一。 k 表两列要一起看。惯性一直降（k 越大簇越多，当然更贴合），但纯度在 k = 3 就到 1.0000， k = 4 反而掉到 0.9972。「惯性更低」不等于「分得更对」。 坏初值那两行最能说明问题。1153.54 对 199.78，差 5.8 倍；纯度 0.66 对 1.0000。 同样一份数据、同样的算法，只因初值不同，结果天差地别。 注意「纯度」这个指标本身有偏。它按簇内多数类加权算，簇越多越容易刷高（每个簇只装一类就行）。 所以它只能横向比同一个 k，不能拿来比不同 k。这也是无监督评价的通病：没有真值，指标都是代理。
30 秒实验
- 把三团的中心改成 (0,0)、(0.5,0)、(0,0.5)（三团挤在一起），k-means 还能分开吗？
- 把其中一团改成横向拉长的椭圆（x 标准差 3、y 标准差 0.3），k-means 会怎么切？
- 把
restarts从 10 改成 1，重复跑五次，惯性每次一样吗？
常见误区
- 只跑一次就信结果。k-means 会卡在局部最优，单次结果可能差好几倍。 必须多初值，取惯性最小的。
- 用惯性选 k。惯性随 k 单调下降，k 等于样本数时惯性是 0，照这个逻辑该分成 n 堆。 要看拐点，不要看绝对值。
- 拿 k-means 处理非球形簇。同心圆、弯月、长条，它一定切错，而且不报错。 先画个散点图，或者改用密度聚类、谱聚类。
自测三问（点开对答案）
1. 为什么 k-means 的惯性一定单调不增？ —— 因为它两步各自都在做「给定另一项时的最优选择」：分配时给每个点选最近的中心， 更新时把中心放到平方误差最小的位置（均值）。每一步都不会让惯性变大。 2. k-means 的两步分别在优化什么？ —— 分配步：固定中心，让每个点归给最近的中心，最小化距离平方和。 更新步：固定归属，让中心挪到名下点的均值，这也是平方误差最小的位置。 3. 为什么坏初值会让结果差好几倍？ —— 多个中心挤在同一团里会互相抢点，而别的团没有中心认领。 算法每一步都在降惯性，所以它停在一个「局部最优」上，自己并不知道错了。k-means 给每个点一个硬编号，还假设簇都是圆的。 3.6 节的混合高斯把这两件事都改了：给概率，而且让每个簇有自己的形状。
- ☐ （本节完，下一节 3.6 算法 15：混合高斯分布）