K-means 聚类
K-means 将 n 个无标签点分成 k 组，交替执行两步：每点归入最近质心，再把每个质心移到成员均值。分配不再变化时停止。目标 inertia（簇内平方和）是每点到所属质心的平方距离之和。
可以把质心想成旗子：人先选最近的旗，旗再移到人群中心，随后重新选择。标准 Lloyd 迭代在本课的确定性规则与精确算术下会停止，但最终结果同时依赖数据与起点，停止不证明全局最优。
工作原理与停止依据
输入点就是训练数据，只是没有类别答案。质心是空间位置，不必等于某个样本。
- 分配。 每点比较 k 个质心，取最近者。本例 15 点、3 质心，需要 45 次距离计算。
- 更新。 每个非空簇移到成员的均值，而非中位数或某个成员。
inertia 使用平方单位，28.80 不是某段距离。分配选择不更远的质心，所以目标不增加。固定非空簇时，均值是平方距离和唯一的最小点；质心若移动，这部分目标严格下降。空簇在本课保持原位置，不能套用“空集合有唯一均值”。
仅“不增加”不足以排除同值循环。这里同距选最低编号，分配是质心的确定函数；点到 k 组的分配方式有限。对给定分配，非空质心更新到确定的均值，空质心保留；有实际非空质心移动就严格降目标。结合确定性平手规则，算法最终到达稳定分配。浮点误差与工程停止阈值属于实际实现的额外考虑。
最近质心把平面分成 Voronoi 单元，边界是两质心连线的垂直平分线的活动部分。因此单簇区域是凸多边形式的单元，不能是一整圈环或月牙。它适合欧氏距离有意义、尺度可比、簇近似团状的数据；长条、嵌套或量纲悬殊时，要检查表示与目标是否合适。
逐步演示
默认 15 点分成三个可见团块：左上五点、左下五点、右侧竖排五点。k=3，起始质心 (0,2)、(0,0)、(0,−2) 都在中间。
- 第一轮分配。 c₀ 获得左上五点和右侧
(4,3)、(4,1)，共 7；c₁ 得(5,0)、(4,−1)，共 2；c₂ 得左下五点和(4,−3)，共 6。右团被拆开，inertia 为 265.00。 - 第一轮更新。 质心到
c₀=(−1.57,3.00)、c₁=(4.50,−0.50)、c₂=(−2.50,−3.33)，inertia 降为 151.55。此时标签未更新，(4,3)虽然更靠近新的 c₁，仍保留 c₀ 标签，正是下一轮的原因。 - 第二轮分配。
(4,3)、(4,1)、(4,−3)转到 c₁，目标降为 64.60，三个簇各 5 点。 - 第二轮更新。 质心到
(−3.80,3.40)、(4.20,0.00)、(−3.80,−3.40)，inertia 为 28.80。 - 第三轮分配检查。 15 点都不换组，
new==labels，停止。两轮更新后已经是固定点，继续相同步骤不会改善。
随后换起点重跑：仍是原数据和 k=3，质心选 (−4,−4)、(4,3)、(4,−3)。三轮后停在 133.10：左边两个团合成 10 点簇，右上 (4,3) 单独成簇，右侧其余 4 点成另一簇。两种结果都稳定，却质量不同。
左侧阶梯记录目标下降。更新拍保留旧分配对应的地图，让质心移动后出现的“不一致”可见；下一次分配再刷新几何。不要把暂时的旧颜色当成最终最近质心判定。
收敛不等于最优
从 15 点选 3 个作种子，共 455 组。此例 332 组到达 28.80，123 组停在更差位置，最差到 215.53。单次停止条件只检查是否变化，不知道它落在什么解。
可多起点运行并保留最低 inertia。K-means++ 按到最近已有种子的平方距离加权选择新种子，减少差起点的风险；它和重启都不保证全局最优。比较多次分区稳定性也有价值。库的默认初始化与重启次数依版本和配置，须显式检查；使用 n_init="auto" 时不能假定它一定做了多次重启。
k 不能仅靠最小 inertia 选择。应结合领域目标、轮廓系数或其他验证。全局最优的 inertia 随 k 增大不增加，但不同局部运行可能不遵守这个顺序。本例 k=4 的最佳值 15.33 低于 k=3 的 28.80，k=n 可为零，说明单纯最小化会偏向拆成单点。
时间与空间复杂度
| 项目 | 成本 |
|---|---|
| 每轮距离与更新 | O(nkd) |
| 标签与质心存储 | O(n)+O(kd)，不含输入 |
| 总迭代 | O(nkdi)，i 为轮数 |
| 新点预测 | O(kd) |
默认有两轮更新和第三轮停止检查。轮数最坏可随输入呈指数增长，即使在平面中也存在此类构造。求全局最佳分区的一般问题是 NP-hard；小实例仍可用精确方法，不能理解成没人求解。
这里迭代本身就是拟合，质心是学习到的参数。动画设 12 轮上限并在达到上限时报告；理论算法不靠这个上限证明停止，当前预设也未触及它。
边界情况
- 空簇。 没有成员就没有均值，本课保留质心。k=4 的 1365 组样本种子中，75 组最终留有空簇，实际非空组少于请求值。其他实现可能重置空质心，规则须另查。
- 同距。 选最低编号，确定性对停止论证重要。
- 初始就位。 从三个团的均值开始，第一次更新不动；代码初始标签未知，仍需后续分配检查确认停止，不是跳过所有步骤。
- 不同位置数少于 k。 重合质心按编号抢走平票，可能饿死其他簇。面板拒绝重复起点。
- 同心环。 环形预设的 153 组双点起始都切穿两个环。两质心的 Voronoi 分区不能把内环与外环各自当完整一簇，失败来自表达形式。
常见错误
- 用 inertia 独自选 k。它偏好更多簇，须用任务标准补充。
- 一次收敛就相信结果。坏固定点也会停止，应比较起点和结果。
- 把均值换成中位数却仍声称优化同一目标。均值最小化平方距离；坐标中位数对应 L1 绝对距离的 k-medians，几何中位数又对应欧氏距离和。目标与证明必须一起改。
- 期待簇大小相等。目标没有平衡项，第二次运行得到 10、4、1 完全合法。
- 忽略单位和尺度。距离可能主要反映数值较大的列，标准化或权重应按任务决定。
简化范围
动画展示 Lloyd 的分配、均值更新、停止判断和空簇保护。没有展示 K-means++、多次重启、Elkan 加速、mini-batch、特征预处理。二维十五点也弱化了高维距离集中的问题。本课用于理解机制、起点敏感性与形状限制，实际使用仍需检查实现配置与验证结果。