4.2 中心目标与 Lloyd 更新

动机

把每个观测值分配给最近中心，还没有完整指定聚类方法。我们仍须决定如何汇总各点的分配距离：距离平方的总和给出 k-means，普通距离的总和给出中位数目标，最大距离则给出 k 中心问题。在中心固定、采用同一欧氏距离时，这些目标都会选择最近中心，但最合适的中心位置一般不同。

当某簇有一个远离其他点的观测值，差异便很明显。它的距离平方会在 k-means 损失中占很大比重，把均值拉向自己；普通距离总和的最小化代表点则可能不同。若再要求代表点必须是实际观测值，就加上另一项数学限制。因此，中心更新应由已定义的目标推导，不能只因某个点被称为“质心”就采用它。

Lloyd 算法交替更新分配和中心。固定其中一部分后，另一部分都容易求解。分析其下降性，应从这两个小型优化问题开始，而不能推断联合问题也同样容易。平局和空簇是迭代中可能出现的状态；要证明有限终止，也必须先指定它们的处理规则。

定义

定义

分配损失与最近中心损失

设观测值为 $x_1,\ldots,x_n\in\mathbb R^d$，中心列表为 $C=(c_1,\ldots,c_k)$，标签为 $z_i\in\{1,\ldots,k\}$。定义

$$J(z,C)=\sum_{i=1}^n\|x_i-c_{z_i}\|_2^2,\qquad F(C)=\sum_{i=1}^n\min_{1\le j\le k}\|x_i-c_j\|_2^2 =\min_z J(z,C).$$

标签指定一个硬聚类。某些标签可以没有观测值，列表中的中心也可以重合。

固定中心后，每个观测值独立选择一个最近中心，便使 $J$ 最小。多个中心并列最近时，选择其中任何一个对损失的贡献都相同。固定分配后，记 $I_j=\{i:z_i=j\}$；若 $I_j$ 非空，其均值为 $\mu_j=|I_j|^{-1}\sum_{i\in I_j}x_i$。

k-median 使用 $\sum_i\min_j\|x_i-c_j\|_2$，而不是距离平方。在一维，固定簇的最优中心是中位数；在多维普通欧氏距离下，所需的是几何中位数。若改用曼哈顿距离，各坐标可以分开处理，逐坐标中位数才会使相应目标最小。中心样本（medoid）另要求中心是允许的观测点，并在这些候选点中使距离总和最小。

在实数线上，把候选中位数稍向右移，会增加它到左侧观测值的距离，同时减少它到右侧观测值的距离。最小值由两侧的数量平衡决定。观测值个数为偶数时，两个中间顺序统计量之间的每一点都可以最优。多维欧氏距离中的平方根把坐标耦合起来；若几何中位数候选点不与任何观测值重合，其梯度条件为 $\sum_i(c-x_i)/\|c-x_i\|_2=0$。逐坐标中位数的依据则是曼哈顿距离的可分性，两者不能混用。

定理与命题

命题

均值使欧氏距离平方总和最小

对有 $m$ 个观测值的非空簇，设其均值为 $\mu$。对任何 $c\in\mathbb R^d$，

$$\sum_{i=1}^m\|x_i-c\|_2^2 =\sum_{i=1}^m\|x_i-\mu\|_2^2+m\|c-\mu\|_2^2.$$

因此唯一最优中心是 $\mu$。空簇对任何中心的损失贡献都是零，但没有可计算的均值。

命题

一次 Lloyd 迭代使损失不增加

从最近中心标签开始，先固定这些标签，把每个非空簇的中心换成其均值，空簇中心则保持原位；再把观测值分配给最近中心。两步都不会增加 $J$，结果的最近中心损失 $F$ 也不大于先前的值。

命题

指定平局规则后的有限终止

采用精确运算及上述均值和空簇规则。重新分配时，若旧标签仍是最近中心之一，就保留旧标签；否则选择最近中心中编号最小的一个。当标签不再改变便停止。标签只会改变有限多次，最终中心与标签构成 Lloyd 不动点。

证明思路

把 $x_i-c=(x_i-\mu)+(\mu-c)$ 代入平方范数并展开。由于 $\sum_i(x_i-\mu)=0$，所有交叉项相加为零，便得到均值分解式。当 $c\ne\mu$ 时，右边第二项严格为正，故最优中心唯一。这个计算使用欧氏内积，不能把距离任意更换后仍沿用结论。

均值是以相等非负权重组合各观测值，所以位于它们的凸包内，但不一定是某个观测点。分解式中的乘数 $m$ 也有意义：同样偏离均值一段距离，大簇的额外损失比小簇大。完整目标给每个观测值相同权重，并非给每簇相同权重。因此，要由多个簇均值还原整体样本均值，应按各簇大小加权。各簇大小相等时可用相等权重；大小不同时，相等权重一般没有这项恒等关系。

均值步骤使各非空簇对 $J$ 的贡献最小。接着固定这些中心，分配步骤使各观测值的贡献最小。空簇保持原中心，其零贡献不影响不等式。起始标签是最近中心标签，因此一轮开始时 $J(z,C)=F(C)$。这两步证明损失不增加，但仅有数值不增加，还不足以证明有限终止。

要得到更强的结论，令 $W(z)$ 为按分配 $z$ 把各非空中心设为均值后的损失；空中心不影响这个值。若重新分配改变了某个标签，按指定规则，旧标签必定已不是最近中心，因此该观测值的距离平方严格减少。设新分配为 $z'$，均值更新后的中心为 $C'$，便有

$$W(z')\le J(z',C')<J(z,C')=W(z).$$

带编号的分配至多有 $k^n$ 个，所以 $W$ 只有有限多个可能值。每次改变标签都使它严格下降，任何分配便不能重现。最后标签固定，此时非空中心已是相应均值，空中心一直保留，再迭代一次也不会改变状态。这证明不动点的存在，并没有把它等同于 $F$ 的全局最小值。

这个版本允许使用一列 $k$ 个中心，并不要求所有 $k$ 簇始终非空。重合中心或不合适的初始位置都可能令某个标签未被使用。若要求恰好 $k$ 个非空簇，就是另加优化约束；只为填满空簇而强行移动观测值，可能增加固定分配的损失，并不包含在上述下降证明内。保留空中心，已是本版本完整而明确的操作规则。

完整算例

例题

例 1：分开跟踪均值更新与重新分配

取线上的观测值 $0,2,3,9,10$，初始中心为 $(0,3)$。最近中心分配把 $0$ 放入第一簇，其余四点放入第二簇，初始损失为 $86$。

第一次均值更新得到 $(0,6)$。沿用旧标签的损失为 $50$。重新分配时，$2$ 转到第一簇；$3$ 到两个中心的距离同为 $3$，因此保留旧标签。最近中心损失变为 $38$。

下一次均值为 $(1,22/3)$，旧分配损失为 $92/3$。重新分配把 $3$ 移入第一簇，损失降至 $143/9$。最终均值和损失为

$$C=(5/3,19/2),\qquad F(C)=\left(25/9+1/9+16/9\right)+\left(1/4+1/4\right) =31/6.$$

此时最近中心标签不再改变：$0,2,3$ 属同一簇，$9,10$ 属另一簇。区分保留标签时的 $J$ 和重新分配后的 $F$，便能理解为何 $50$ 与 $38$ 对应同一组中心，却有不同损失。

例题

例 2：较大 k 的局部运行可以有较差损失

取 $X=\{0,1,8,9,20,21\}$。三个中心 $(0,1,29/2)$ 产生两个单点簇，以及最后一簇 $\{8,9,20,21\}$。各中心都是所属簇的均值，而每点都严格更接近其所属中心，所以这是 Lloyd 不动点。损失为

$$F(0,1,29/2)=\frac{169+121+121+169}{4}=145.$$

比较两个中心 $(9/2,41/2)$，它们产生簇 $\{0,1,8,9\}$ 和 $\{20,21\}$，损失为 $65+1/2=131/2$。这个已收敛的三中心结果，竟比一个可行的两中心结果差。若三中心改由 $(1/2,17/2,41/2)$ 开始，则得到三对相邻点，损失只有 $3/2$。

算例同时说明初始化和重新启动的作用。重复运行并保留最低损失，可改善目前找到的最佳结果；某次运行到达不动点，并不是全局最优的证明。比较不同 $k$ 的独立局部运行时，损失也不必单调。

例题

例 3：均值、中位数与中心样本解决不同问题

一簇包含 $0,2,9$ 时，距离平方总和由均值 $11/3$ 最小化，最小值为 $134/3$；中心 $2$ 的平方损失则是 $53$。改用普通绝对距离总和，中位数 $2$ 的损失是 $9$，均值的损失却是 $32/3$。若限制中心必须是观测点，中心样本也是 $2$，距离总和同为 $9$。

在平面上，考虑 $(0,0)$、$(2,0)$、$(0,2)$。逐坐标中位数为 $(0,0)$，欧氏距离总和是 $4$。可行点 $(1/2,1/2)$ 的总和为

$$\frac1{\sqrt2}+\sqrt{10}<4.$$

因此，逐坐标中位数不是这组数据的欧氏几何中位数。逐坐标最小化解决的是曼哈顿距离问题，其中各坐标的绝对差分开相加。

可复现的 Lloyd 计算

以下程序实现例 1。输出的是重新分配后的 $F$，并非沿用上一轮标签的损失。空中心保持原位；距离完全相同时保留旧标签。

import numpy as np

X = np.array([0.0, 2.0, 3.0, 9.0, 10.0])[:, None]
C = np.array([[0.0], [3.0]])
rows = np.arange(len(X))
def distances2():
    return np.sum((X[:, None, :] - C[None, :, :]) ** 2, axis=2)
D = distances2()
labels = np.argmin(D, axis=1)
print(f"initial cost={D[rows, labels].sum():.6f}")
round_number = 0
while True:
    round_number += 1
    for j in range(len(C)):
        members = X[labels == j]
        if len(members):
            C[j] = members.mean(axis=0)
    D = distances2()
    nearest = np.argmin(D, axis=1)
    new_labels = np.where(D[rows, labels] <= D[rows, nearest], labels, nearest)
    cost = float(D[rows, new_labels].sum())
    centre_text = ", ".join(f"{centre[0]:.6f}" for centre in C)
    print(f"{round_number}: centres=({centre_text}), cost={cost:.6f}")
    if np.array_equal(new_labels, labels):
        break
    labels = new_labels
print("labels:", labels.tolist())

initial cost=86.000000
1: centres=(0.000000, 6.000000), cost=38.000000
2: centres=(1.000000, 7.333333), cost=15.888889
3: centres=(1.666667, 9.500000), cost=5.166667
labels: [0, 0, 0, 1, 1]

初始化与肘部曲线

初始化决定交替更新从哪一个吸引区域开始。最远优先每次选取目前距离已选中心最远的观测值，使中心分散。k-means++ 则先均匀随机选一个观测值，再按到已选中心的最近距离平方作比例抽样。距离平方总和为正时，概率为

$$p_i=\frac{D_i^2}{\sum_{r=1}^nD_r^2},\qquad D_i=\min_{c\in C}\|x_i-c\|_2.$$

若所有 $D_i$ 都是零，每个输入点都已由某个选定中心代表。否则，抽样更偏向目前代表不足的点，但并非必定选取最远的一点。完成初始化后，才进行 Lloyd 更新。

设 $F_k^*$ 为使用至多 $k$ 个中心的全局最小损失。加上一个中心不会增加任何观测值的最近距离，所以 $F_{k+1}^*\le F_k^*$。每个观测值各有一个中心时，损失为零。肘部图观察额外中心带来的改善在哪里明显减弱；可行集合的论证针对全局最优值，例 2 已说明任意局部运行的损失不必遵守同一排序。肘部是平衡简洁程度与拟合的建模工具，并非每组数据必能唯一恢复簇数的定理。

常见错误

常见错误

改了更新方式，却沿用原来的目标

算术均值最小化欧氏距离平方总和。一维绝对距离目标使用中位数，多维欧氏普通距离目标使用几何中位数。中心样本则须在允许的观测代表点中最小化距离总和，不能只挑一个看似接近算术均值的观测值。

平局时损失可以不变，因此“损失不增加”和“分配数有限”合起来仍未排除等损失状态的循环。保留旧标签的规则令每次真正改变标签都严格改善损失。同样，保留空中心是明确且合法的操作，因为它对固定分配损失的贡献为零；空集合的均值则没有定义。

小结

选择更新前，先指定距离、如何汇总分配成本，以及中心允许的位置。Lloyd 的均值与最近中心步骤使欧氏平方目标下降；配合明确的平局和空簇规则，标签最终稳定，但不动点仍可能有很大损失。初始化、重新启动和肘部比较，都应按这项区分解读。

固定 $k$ 重复运行时，保留实际取得的最小目标值。增加运行次数不会使这个已保留的值变大，因为先前候选仍可选取；这说明的是目前最佳结果，而不是每次随机初始化的质量。簇的编号也没有内在意义：把标签和相应中心一同重新排列，损失不变。比较两次运行时，应比较目标值和各点的分组，避免把编号不同误当成质量不同。

练习

思考检查

练习 1：一簇包含 $1$、$2$、$6$。求均值、最小平方损失，以及选择中心 $2$ 所增加的损失。

使用距离平方分解式，无须重新微分。

思考检查

练习 2：线上的观测值为 $0$、$2$、$9$、$11$。求使绝对距离总和最小的所有中心。哪些观测点是中心样本？

两个中间观测值之间的每一点都是中位数。

思考检查

练习 3：观测值为 $0$、$4$、$5$，现有中心为 $(0,4,100)$。按最近中心分配及上述均值和空簇规则，求更新后的中心与损失。

第三簇是空簇，其中心保持原位。

思考检查

练习 4：两个观测值都等于 $0$，两个中心也都等于 $0$。任意更改平局标签，如何在损失保持零时改变状态？上述平局规则会怎样做？

区分固定的目标值与固定的带标签状态。

解答

解答 · 练习 1 解答

均值是 $3$，最小平方损失为 $4+1+9=14$。中心 $2$ 的损失为 $1+0+16=17$，额外损失是 $3(2-3)^2=3$，与两值之差一致。

解答 · 练习 2 解答

$[2,9]$ 内所有实数中心都使绝对距离总和最小，值为 $18$。限制中心为观测点后，$2$ 和 $9$ 都是中心样本，并达到同一数值。

解答 · 练习 3 解答

各簇为 $\{0\}$、$\{4,5\}$ 和空集合，更新后中心为 $(0,9/2,100)$。重新分配后各簇不变，损失为 $(4-9/2)^2+(5-9/2)^2=1/2$。

解答 · 练习 4 解答

可以反复把标签 $(1,2)$ 和 $(2,1)$ 互换；各簇均值仍为零，所有距离也为零。这改变带标签状态，却没有改善目标。平局时保留旧标签会阻止这些互换，因此状态停止改变。

相关笔记

Voronoi 区域与 k 中心问题推导最近站点几何及最大距离目标。模型验证与岭回归解释比较已拟合模型的另一项工作。课程阅读书目集中列出相关延伸阅读。