题目重点：严格使用输入initial centers，定义空簇和平局，区分最终质心与最后一次assignment。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练欧氏平方距离，给定k个初始中心及迭代次数；距离平局取小cluster编号，空簇保留旧中心。
- 返回最后更新的中心以及重新按它们预测的labels，0次迭代仅按initial预测；框架要求可能不同需核对。
解题路线
- Lloyd交替：按当前中心把每点分到最近簇，再对每簇求均值更新中心。不要替换给定initial为随机或前k点，那会改变要求的输出。
- 固定簇C时目标Σ||x−μ||²，对μ梯度2|C|μ−2Σx=0，μ=mean；也可拆Σ||x−mean||²+|C|·||μ−mean||²，第二项非负证明全局最优。
- assignment选择最近中心不增目标，非空簇mean更新也不增目标；因此交替下降到局部解，不保证全局最优。初始化不同可得不同聚类。
- 空簇没有均值，保留旧中心是本训练政策；重置到最远点也是选项但会改变轨迹。重复中心和距离平局必须固定规则避免输出不确定。
- 最后一次更新中心后，旧labels可能不是新中心最近预测，故若要求“模型预测类”需重新assign。若题目框架直接要迭代中的labels则按框架，不能偷换两者。
- 距离用平方即可比较无需sqrt，特征尺度影响结果，预处理应由业务定义；异常值与高维欧氏距离问题不能靠更大k自动解决。
- 验证固定输入中心轨迹、空簇、重复点和平局，独立一维精确有理数均值对照；只是检查最终loss较低不足以证明满足指定迭代合同。
手动走一遍
点[0,2,10]，中心[0,10]，首分组[0,2]/[10]，新中心[1,10]。若空簇则保持对应initial位置。k=1均值是12/3=4，不是中位数2，因为目标为平方距离。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from math import isfinite
def kmeans(data, initial, iterations):
if not data or not initial or type(iterations) is not int or iterations < 0:
raise ValueError('nonempty data/centers and nonnegative iterations required')
d = len(data[0])
if not d or any(len(row) != d or any(not isfinite(v) for v in row) for row in data + initial):
raise ValueError('finite fixed-dimensional vectors required')
centers = [list(row) for row in initial]
k = len(centers)
def assign():
return [min(range(k), key=lambda c: (sum((a-b)**2 for a,b in zip(row,centers[c])),c)) for row in data]
for _ in range(iterations):
labels = assign()
totals = [[0.0] * d for _ in range(k)]
counts = [0] * k
for row, c in zip(data, labels):
counts[c] += 1
for j, value in enumerate(row):
totals[c][j] += value
for c in range(k):
if counts[c]:
centers[c] = [v / counts[c] for v in totals[c]]
return centers, assign()
复杂度
N点D维K簇T次迭代O((T+1)NKD)，加1为最终预测；中心/累计O(KD)、labels O(N)，输入另计。
易错点与追问
容易失分的边界
- 忽略给定初始中心。
- 空簇除0。
- 最终labels与更新中心不一致却没说明。
- mean和median混淆距离目标。
继续深挖
- kmeans++为何改善初始化？
- 加权样本均值怎样改？
- L1距离为什么倾向中位数？
