假设每段已记录信号都已转为特征向量。我们想把位置接近的向量分组,事前却没有正确的群组标签。质心式方法用一个中心代表每组,再按观测值到各中心的距离分配成员。这听来简单,但仍须说清楚采用什么距离、中心代表什么,以及正在改善哪个准则。
对于 k-means,准则是每个观测值到所属中心的欧氏距离(Euclidean distance)平方总和。通常的迭代交替处理两个各自容易的问题:固定中心时选标签,再固定标签时选中心。合起来不会使准则增加,却不会自动在全局解决联合优化问题。
写清数据与目标函数
定义 1.1.1
(分配、中心与平方误差目标)
固定观测值 ,其中 ,并选择 个中心 。分配标签 把第 个观测值交给一组。定义
群组 包含分配到 的索引。这些分配标签由算法计算,并非事前提供的正确类别标签。中心不一定是某个观测值。
平方是模型的一部分,不是可以随意改动的写法。最小化距离平方才会得到均值中心;改用另一种损失,可能就需要不同更新。因此,单凭“中心”一词不能决定算法。
一次迭代采用以下规则:
- 固定中心,把每个观测值分配到最近的中心;距离相等时,选中心索引较小者。
- 对于每个非空群组,用成员的算术平均值替换中心。
- 本例对于空群组保留原中心,再重复分配与更新,直到符合所选停止条件。
空群组规则是一项明确策略:空群组的均值没有定义,如果默默把它当作零,就会在特征空间加入无关的位置。保留原中心并非唯一策略,但使程序有完整规定。
为什么算术平均值是正确更新
命题 1.1.2
(关于中心的平方误差)
设 ,,并设 。则对每个 都有
因此 是 的唯一最小化点。
证明
(围绕均值展开)
写 并展开长度平方。交叉项是 ,由于 ,交叉项消失,剩下的就是所述恒等式。第一项与 无关;第二项非负,而因 ,它恰好在 时为零。所以对这个固定的非空群组,均值是唯一的最小化中心。
证明透视
恒等式在哪里用到群组,又在哪里失效
唯一不算常规的一步,是在 与 之间插入 。这样选择,是因为它使交叉项变成与 的内积,而按 的定义它等于零;换成任何其他中间点,交叉项仍会依赖 。
非空这个条件用了两次:一是让 有定义,二是使系数 为正,唯一性正是由此而来。恒等式也准确计算了中心放错的代价:额外损失 随群组大小及位移平方增加。
这个相消依赖平方欧氏损失。对未平方的距离没有这种恒等式,最小化点也不一定是均值:在一维中, 的绝对偏差和在 时是 ,在均值 时却是 。空群组没有 ,也没有正系数,所以需要独立策略。
固定中心时,分配规则也有直接理由。每个观测值对 贡献一项,并不依赖其他观测值的标签选择;选最小距离平方便使该项最小。保持这些分配不变,再用均值更新,便使每个非空群组的贡献最小。
概念视角代数
完全不用中心的目标函数
对大小为 的群组 ,均值恒等式给出 。因此每个群组贡献的,是其无序成对距离平方之和再除以群组大小,k-means 就是寻找成员彼此接近的群组。以 验证:无序成对的平方和为 ,而群组内误差正是 。
精确追踪两轮交替步骤
例题 1.1.3
(中心更新后,观测值可以转到另一组)
使用一维观测值 ,初始两中心为 与 。表中的群组列出观测值,而不是索引。直线上两个不同中心的中点,是最近中心区域的分界。起初分界是 ,所以只有观测值 0 属于第一组。
| 阶段 | 中心 | 第一组 | 第二组 | 目标值 |
|---|---|---|---|---|
| 第一次分配 | ||||
| 第一次均值更新 | ||||
| 第二次分配 | ||||
| 第二次均值更新 |
第一行的非零误差平方是 。第二组均值为 ,把固定成员下的误差降至 。
更新把分界移至 。2 与 3 现在较接近第一中心,因此下一次分配改变了群组,得到 。新均值为 与 ,最后群内误差是
新分界为 ,位于 3 与 10 之间,因此再作分配,两组都不变;再更新均值也不改变任何值。例子已到达不动点。表格把分配与更新分开,是因为它们改变不同变量;记录目标值时,不应把旧标签与未交代的新中心混在一起。
例题 1.1.4
(距离平局,由较小索引规则决定)
取观测值 ,初始中心为 与 。观测值 1 到两个中心的距离平方都是 ,所以按既定规则归入第一组。
| 阶段 | 中心 | 第一组 | 第二组 | 目标值 |
|---|---|---|---|---|
| 第一次分配 | ||||
| 均值更新 |
第一组的均值是 ;只有一个成员的群组,其均值就是该成员,所以第二中心仍在 。分界现在是 ;观测值 1 与第一中心相距 ,与第二中心相距 ,因此没有标签改变,状态是 的不动点。
若平局改为另一方向解决,群组会是 与 ,;更新后中心为 ,,分界为 ,同样没有改变。两次运行停在不同的不动点,目标值却相同。因此,平局规则是可重现运行规格的一部分。
例题 1.1.5
(平面上的两个群组)
取 ,初始中心为 与 。四个观测值到中心 的距离平方分别是 、、 与 。所以第一个观测值留在第一中心,其余三个归第二中心,得 。
| 阶段 | 中心 | 第一组 | 第二组 | 目标值 |
|---|---|---|---|---|
| 第一次分配 | ||||
| 第一次均值更新 | 相同 | 相同 | ||
| 第二次分配 | ||||
| 第二次均值更新 | 相同 | 相同 |
第二组均值是 。在成员不变下,它的误差减少 ,由 降至 。在新中心下,四个观测值到最近中心的距离平方是 ,所以 转组,。新均值是 与 ,每个观测值与其中心的距离平方都是 ,所以 。再分配时所有标签不变,因此这是不动点。第一轮中只有一个成员的群组误差为零,其中心也没有移动。
下降性证明了什么,又没有证明什么
定理 1.1.6
(Lloyd 一轮不会使目标值增加)
设 为一个分配, 为一组中心。一轮先把每个观测值分配给 中的最近中心(平局时可用任何规则),得到 ;再把每个非空群组的中心换成其均值,空群组则保留原中心,得到 。则
所以一轮之中 不增加,且 。
另设 起初是 各群组的均值、算术为精确、没有距离平局,而且没有空群组。则分配在有限轮后不再改变。
证明
(两个半步,然后严格下降)
第一式由最近中心分配对每点分别成立:每个观测值对 贡献一项,新的一项是可选之中最小的。第二式由均值恒等式对每组分别成立;空群组贡献为零,保留原中心也不会使其贡献增加。
至于有限步终止,假设分配有所改变。至少一个观测值移到严格更近的中心,所以第一式严格成立。每次更新后,均值由分配决定,因此以 记 的各群均值,则数值 只依赖 ,并在分配改变时严格下降。于是同一个分配不会重现。带标号的分配只有 种,所以分配最终不再改变,随后均值也保持不变。
证明透视
每个不等式用了什么,论证又留下什么未决
第一式只用到 是独立各项之和,每个观测值一项,所以固定中心而改变标签时可逐项处理。第二式在标签固定下,对每个非空群组使用均值恒等式。两个半步改变不同的变量,因此一步不会抵消另一步。
严格性是较微妙的假设。若有距离平局,观测值可能以相同距离改变标签,只能得到 ,上面的有限性论证便不适用;不增加的结论则仍然成立。精确算术也必须假设,因为舍入可能破坏均值恒等式所给出的等式。
论证以计数收尾:附于有限个分配的严格递减数值序列必须停止。结论是迭代会停止,并没有说最后的数值与其他聚类相比如何。
这项保证针对的是迭代过程中 的数值,而不是极限的好坏。
反例模式
稳定聚类的目标值仍可能较差
改用另一组数据:,中心为 与 。中点是 ,最近中心分配得到 与 。它们的均值恰好仍是原中心,所以这是没有距离平局的不动点。
其目标值是
但另一种分组 与 ,均值为 与 ,其目标值为
因为 ,原不动点不是全局最佳。要反驳“每个不动点都是全局最佳”,不必证明 87 本身就是全局最小。初始中心因此可以影响结果;分配不变是一个停止条件,不是全局最优性的证明。
逐步演示重现上面的精确案例与稳定但较差的聚类。空簇情形延伸下面练习 2 的第一轮:没有分配点的簇没有平均值,而此案例按明确约定保留其原有中心。
常见错误
(较小的目标值不能用来选择群组数目)
增大时, 的最小可达值不会增加,因为多出来的中心总可以放在不起作用的位置。若跨不同 比较 并取最小者,选中的必然是最大的 。对观测值 ,取 使每个观测值各有自己的中心,,但数据的结构完全没有被学到。目标值只可比较 相同的不同运行,例如上面 与 的两个聚类;选择 需要另一个准则。
特征单位会改变正在优化的几何
反例模式
单位换算可以反转最近中心的选择
取观测值 与固定中心 、。到 的距离平方为 9 及 16,所以最近中心是 。
现在把每个观测值及中心的第二特征都乘以 10,第一特征不变。相同记录的坐标变为 、、,距离平方是 900 及 16,因此改选 。
新坐标中的无权重欧氏距离,相当于改变旧特征的相对权重。如果第 坐标缩放 倍,其贡献变为 。预处理因此是聚类模型的一部分。比较不同单位的特征时,缩放可能适用,但应表达哪些差异对任务重要,而非描述成目标函数完全不变。
不用舍入重现计算
以下一维 Python 例子用有理数精确重现表格。实现以中心索引 0、1 对应第一组及第二组。assign 按索引打破距离平局,update 则在群组为空时保留原中心。
from fractions import Fraction as F
def assign(points, centers):
return [
min(range(len(centers)), key=lambda j: ((x - centers[j]) ** 2, j))
for x in points
]
def update(points, labels, old_centers):
result = []
for j, old in enumerate(old_centers):
group = [x for x, label in zip(points, labels) if label == j]
result.append(sum(group) / len(group) if group else old)
return result
def objective(points, labels, centers):
return sum((x - centers[label]) ** 2 for x, label in zip(points, labels))
points = list(map(F, [0, 2, 3, 10, 11]))
centers = [F(0), F(3)]
for _ in range(2):
labels = assign(points, centers)
print("assignment", objective(points, labels, centers))
centers = update(points, labels, centers)
print("update", objective(points, labels, centers))
assert assign(points, centers) == labels
四个打印的目标值为 114、65、91/2、31/6。两轮只对这份特定数据及初始中心足够,固定轮数不是一般停止规则。最后断言检查再分配一次是否维持不变。研究另一个例子时,应同时追踪分配、中心及目标值,指出每个量在哪个半步改变。
练习
快速检查
(1. 量化中心偏离的成本)
固定群组的值为 。求均值与最小误差平方和,再用均值恒等式求中心为 5 时的误差,不要分别重算三个距离平方。
解答 · 解答 1
均值是 4,最小误差为 。中心移到 5,增加 ,所以新误差为 。比较期间,群组成员固定不变。
快速检查
(2. 分清平局策略与均值公式)
观测值为 ,初始中心为 ,采用所述较小索引优先规则。第一次标签与下一组中心是什么?为什么第二中心不是空组的均值?
解答 · 解答 2
两个观测值都选中心索引 0。该组均值是 1;索引 1 的组为空,保留原中心 0,所以下一组中心为 。保留 0 是明确策略,并没有把空组均值定义为 0。
快速检查
(3. 用合适证据检查全局最佳的声称)
某实现报告分配不变,而且目标值没有增加。这能确立全局最优性吗?在上述反例中,什么证据已足以反驳该不动点是全局最佳?又有哪个更强的声称尚未证明?
解答 · 解答 3
不能。目标值为 127 的不动点满足这两项观测。提出一个目标值为 87 的合法分组,已足以证明 127 不是全局最小,但不能单凭这点确立 87 是最佳可能值;后者还须排除所有更好的聚类。
快速检查
(4. 预测特征缩放的影响)
如果把所有观测值及中心的某一特征乘以 100,该特征对欧氏距离平方的贡献会乘多少倍?如果每个特征都乘相同正数,会保留最近中心的选择吗?这为什么与只缩放一个特征不同?
解答 · 解答 4
该特征的贡献乘以 。每个特征都乘相同正数、中心也同样缩放时,每个距离平方都乘同一正数常数,因此最近中心比较及平局都不变。只缩放一个特征,则改变它相对其他特征的权重,可以反转比较,正如二维例子所示。