题目重点：不用机器学习框架也能解释 Lloyd 迭代：初始化中心、最近中心分配、按簇均值更新、收敛与空簇处理。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练输入为 n 个同维数值点，1≤k≤n；用欧氏距离平方分配，最终返回 k 个中心及每点簇标签。
- 为可复现性取前 k 个点作初始中心，等距时选较小簇 ID；初始化质量可能不好，实际应用建议多次随机重启或 k-means++。
- 空簇保留旧中心；最多迭代 max_iter 次或标签不变时停止。不同空簇策略都会改变最终结果，不能当作原题指定。
解题路线
- 每轮对每个点计算到全部 k 个中心的距离平方，选最近簇；平方与开方的最小点相同，省去 sqrt。
- 按标签对每簇每维求和/计数，非空簇新中心是该簇均值；这是固定标签下最小化平方误差的最优中心。
- 标签不变则再次更新仍得到同样中心，可以停；若轮数上限先达到，返回最后一次分配及其中心。
- 目标函数是所有点到所属中心距离平方之和。固定中心时最近中心分配不增目标，固定标签时求均值也不增目标，所以迭代单调不增，但可能卡局部最优。
- 讨论特征标准化、离群点、不同 k 选择和空簇策略；K-Means 不适合需要任意形状或类别变量直接相减的场景。
手动走一遍
点 [0]、[1]、[9]、[10] 取初始中心 [0]、[1] 时，初始分配可能先不均衡；更新后中心朝两团移动，后续迭代调整。两个相同初始点可导致空簇，训练实现保留旧中心，避免除零；真实系统可把空簇重置到最远点。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Deterministic Lloyd k-means training contract, using plain Python."""
def kmeans(points: list[list[float]], k: int, max_iter: int = 100) -> tuple[list[list[float]], list[int]]:
if not points or not 1 <= k <= len(points) or max_iter < 1:
raise ValueError("nonempty data, 1 <= k <= n, and positive iterations required")
dimension = len(points[0])
if dimension == 0 or any(len(point) != dimension for point in points):
raise ValueError("fixed positive feature dimension required")
centroids = [list(map(float, points[i])) for i in range(k)]
labels = [-1] * len(points)
for _ in range(max_iter):
new_labels = []
for point in points:
closest = min(
range(k),
key=lambda cluster: (
sum((coordinate - center) ** 2 for coordinate, center in zip(point, centroids[cluster])),
cluster,
),
)
new_labels.append(closest)
if new_labels == labels:
break
labels = new_labels
totals = [[0.0] * dimension for _ in range(k)]
counts = [0] * k
for point, cluster in zip(points, labels):
counts[cluster] += 1
for axis, coordinate in enumerate(point):
totals[cluster][axis] += coordinate
for cluster in range(k):
if counts[cluster]:
centroids[cluster] = [value / counts[cluster] for value in totals[cluster]]
# Empty cluster keeps its old center; alternatives must be specified.
return centroids, labels
复杂度
T 次迭代、n 点、k 簇、d 维：距离分配 O(Tnkd)，求和更新 O(Tnd)，中心与标签空间 O(kd+n)。默认实现每轮 materialize 标签和求和；多次随机重启再乘重启数。
易错点与追问
容易失分的边界
- 对空簇直接除以 0。
- 把 K-Means 说成保证全局最优；初始化不同可落不同局部最优。
- 忘记等距时的确定性 tie-break，测试不稳定。
- 不同量纲特征未经处理直接用欧氏距离。
- 只会调用框架函数，讲不清每轮分配/更新及复杂度。
继续深挖
- k-means++ 如何降低糟糕初始化概率？
- 怎样判断是否收敛，中心移动阈值与标签不变有何区别？
- 百万点和高维稀疏向量下如何批量/分布式更新？
- K-Means 与 Gaussian Mixture Model 的目标和软硬分配有何不同？
