9.1 K均值聚类
⾸ 先， 我 们 考 虑 寻 找 多 维 空 间 中 数 据 点 的 分 组 或 聚 类 的 问 题。 假 设 我 们 有 ⼀ 个 数 据
集{x1, . . . ,xN}，它由D维欧⼏⾥得空间中的随机变量x的N次观测组成。我们的⽬标是将数据
集划分为K个类别。现阶段我们假定K的值是给定的。直观上讲，我们会认为由⼀组数据点构
成的⼀个聚类中，聚类内部点之间的距离应该⼩于数据点与聚类外部的点之间的距离。我们可
以形式化地说明这个概念。引⼊⼀组D维向量µk，其中k = 1, . . . ,K，且µk是与第k个聚类关联
的⼀个代表。正如我们将看到的那样，我们可以认为µk表⽰了聚类的中⼼。我们的⽬标是找到
数据点分别属于的聚类，以及⼀组向量{µk}，使得每个数据点和与它最近的向量µk之间的距离
的平⽅和最⼩。
现在，⽐较⽅便的做法是定义⼀些记号来描述数据点的聚类情况。对于每个数据点xn，我
们引⼊⼀组对应的⼆值指⽰变量rnk ∈ {0, 1}，其中k = 1, . . . ,K表⽰数据点xn属于K个聚类中
的哪⼀个，从⽽如果数据点xn被分配到类别k，那么rnk = 1，且对于j ̸= k，有rnj = 0。这被
称为“1-of-K”表⽰⽅式。之后我们可以定义⼀个⽬标函数，有时被称为失真度量（distortion
measure），形式为
J =
N∑
n=1
K∑
k=1
rnk∥xn − µk∥
2 (9.1)
它 表 ⽰ 每 个 数 据 点 与 它 被 分 配 的 向 量µk之 间 的 距 离 的 平 ⽅ 和。 我 们 的 ⽬ 标 是 找
到{rnk}和{µk}的值，使得J达到最⼩值。我们可以⽤⼀种迭代的⽅法完成这件事，其中每次迭
代涉及到两个连续的步骤，分别对应rnk的最优化和µk的最优化。⾸先，我们为µk选择⼀些初
始值。然后，在第⼀阶段，我们关于rnk最⼩化J，保持µk固定。在第⼆阶段，我们关于µk最⼩
化J，保持rnk固定。不断重复这个⼆阶段优化直到收敛。我们会看到，更新rnk和更新µk的两个
阶段分别对应于EM算法中的E（期望）步骤和M（最⼤化）步骤。为了强调这⼀点，我们会
在K均值算法中使⽤E步骤和M步骤的说法。
⾸先考虑确定rnk。由于公式（9.1）给出的J是rnk的⼀个线性函数，因此最优化过程可以很
容易地进⾏，得到⼀个解析解。与不同的n相关的项是独⽴的，因此我们可以对每个n分别进⾏
最优化，只要k的值使∥xn − µk∥2最⼩，我们就令rnk等于1。换句话说，我们可以简单地将数据
点的聚类设置为最近的聚类中⼼。更形式化地，这可以表达为
rnk =
{
1 如果k = arg minj ∥xn − µj∥2
0 其他情况
(9.2)
293
