题目重点：给出可运行 Lloyd 训练版，逐步解释分配/均值更新、相等距离、空簇和随机初始化边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输入是有限浮点坐标的同维点列表；`1≤k≤不同点数量`，初始中心取输入中前 k 个不同点；距离用欧氏距离平方。
- 相同距离选较小中心编号，空簇保留旧中心，最多迭代 max_iter 轮；题目未明确这些规则，真实实现可能要求 k-means++、随机种子或空簇重启。
解题路线
- 验证非空/维度/有限数，建立 k 个确定性初始中心；初始化方式会显著影响局部最优与重现性。
- 每轮将点分给最近中心，距离相同时稳定选较小编号；若标签与上一轮完全相同即可停止。
- 根据分配结果对每簇逐维求均值；空簇按训练契约保留原中心，不除以零。达到迭代上限后，最终标签再对最终中心计算，避免返回旧中心的标签。
- Lloyd 算法每次分配与均值更新不会提高目标平方误差（在中心精确均值且分配稳定的理想条件下），但只保证局部最优。用独立朴素参考实现核对 33,435 组短数据/迭代上限组合。
手动走一遍
点 (0,0)、(0,2)、(4,4)，k=2，初始中心前两点。按最近中心分配后，(4,4) 靠近 (0,2)，第二簇均值变为 (2,3)；下一轮重新分配，直到标签不再变化或达到上限。不同初始中心可能给出不同终态。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from __future__ import annotations
from math import isfinite
def kmeans(points: list[tuple[float, ...]], k: int,
max_iter: int = 100) -> tuple[list[tuple[float, ...]], list[int]]:
"""Deterministic Lloyd training contract; first k distinct input points seed centers.
Ties choose lower center index. Empty clusters keep their previous center.
"""
if not points or k < 1 or max_iter < 1:
raise ValueError("nonempty points, positive k and max_iter required")
dimension = len(points[0])
if dimension == 0 or any(len(p) != dimension or not all(isfinite(x) for x in p) for p in points):
raise ValueError("points must have same positive dimension and finite coordinates")
seeds = list(dict.fromkeys(points))[:k]
if len(seeds) != k:
raise ValueError("need at least k distinct points")
centers = [tuple(map(float, p)) for p in seeds]
labels = [-1] * len(points)
for _ in range(max_iter):
assigned = [min(range(k), key=lambda c: (
sum((x - y) ** 2 for x, y in zip(p, centers[c])), c)) for p in points]
if assigned == labels:
break
labels = assigned
sums = [[0.0] * dimension for _ in range(k)]
counts = [0] * k
for point, label in zip(points, labels):
counts[label] += 1
for axis, value in enumerate(point):
sums[label][axis] += value
centers = [tuple(value / counts[c] for value in sums[c]) if counts[c]
else centers[c] for c in range(k)]
# Return labels consistent with the final centers after the last allowed update.
labels = [min(range(k), key=lambda c: (
sum((x - y) ** 2 for x, y in zip(p, centers[c])), c)) for p in points]
return centers, labels
复杂度
n 点、k 簇、d 维、I 轮，时间 O(I·n·k·d)，存储中心 O(kd)、标签 O(n) 与累加 O(kd)。大数据可分批或并行计算，但批量近似的收敛语义不同。
易错点与追问
容易失分的边界
- 把 kmeans 当成保证全局最优的算法。
- 空簇时均值除零。
- 相等距离不定规则，导致测试/复现不稳定。
- 用最新中心却返回上一轮标签。
- 特征尺度差异很大时未经标准化，距离被单一维度支配。
继续深挖
- k-means++ 如何降低坏初始化概率？
- 空簇改为重置最远点时目标函数可能怎样变化？
- 怎样用 silhouette/inertia 与业务指标共同选择 k？
- 类别特征和离群点很多时 KMeans 有何局限？
