K 均值聚类

Views: --
#机器学习 #聚类 #无监督学习 #EM

前面几种方法（贝叶斯、SVM）都活在有标签的世界里：知道每个样本属于哪类，去学一个映射。但很多时候数据是”裸”的——没有标签，只有一堆点。聚类要做的，就是仅凭样本之间的相似度，把它们自动分成若干组。K 均值是这件事最经典、最简洁的解法，也是理解 EM 思想的最佳入门。

一、把「聚类」写成一个优化问题

给定 NN 个 DD 维点，想分成 KK 组。K 均值的建模思路是给每组设一个代表点（中心） μk\boldsymbol{\mu}_k，并让每个样本归属到离它最近的那个中心。

用 rnk∈{0,1}r_{nk} \in \{0, 1\} 记录归属：样本 nn 属于第 kk 组就为 1，否则为 0。这是硬分配——一个点只属于一个组，没有”百分之七十属于 A”这种说法。

聚类的好坏用一个准则函数衡量——所有点到自己中心的距离平方和：

J=∑n=1N∑k=1Krnk∥xn−μk∥2J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk}\|\mathbf{x}_n - \boldsymbol{\mu}_k\|^2

JJ 越小，说明每个组内的点越聚拢、聚类越紧凑。于是聚类问题变成了：调整分配 rnkr_{nk} 和中心 μk\boldsymbol{\mu}_k，让 JJ 最小。

二、鸡生蛋问题，与交替优化

麻烦在于 rnkr_{nk} 和 μk\boldsymbol{\mu}_k 互相纠缠：要定分配，得先知道中心在哪；要算中心，又得先知道哪些点归它。两组变量耦合，没法一步解出。

K 均值的破局办法是交替优化——固定一个、优化另一个，来回迭代：

第一步（固定中心，更新分配）：每个点归到当前最近的中心。

rnk=1  ⟺  k=arg⁡min⁡j∥xn−μj∥2r_{nk} = 1 \iff k = \arg\min_j \|\mathbf{x}_n - \boldsymbol{\mu}_j\|^2

第二步（固定分配，更新中心）：对 JJ 关于 μk\boldsymbol{\mu}_k 求导置零，解得

μk=∑nrnkxn∑nrnk\boldsymbol{\mu}_k = \frac{\sum_n r_{nk}\mathbf{x}_n}{\sum_n r_{nk}}

也就是把中心移到该组所有点的均值（重心）处。“K 均值”的名字正来自这一步。

两步交替，直到中心不再移动。每一步都只会让 JJ 减小或不变（两步各自都是在当前条件下的最优），而 JJ 有下界，所以算法保证收敛——尽管收敛到的可能是局部最优，因此初始化和多次重启在实践中很重要。

三、它其实是 EM 的「硬」版本

把这两步抽象一下，会发现一个更大的结构：第一步在”分配责任”，第二步在”更新参数”。这正是 EM 算法的 E 步和 M 步。

差别只在”分配”的软硬：

  • K 均值是硬分配：rnkr_{nk} 非 0 即 1，一个点要么全属于 A，要么全属于 B。
  • GMM（高斯混合模型）+ EM 是软分配：一个点按概率”部分属于”各个组，比如 70% 像 A、30% 像 B。

所以可以说，K 均值是高斯混合模型在「硬分配 + 各向同性等方差」假设下的特例。理解了这层关系，K 均值就不再是一个孤立的小算法，而是 EM 这一大类迭代方法的最简实例——这也是它特别值得吃透的原因。

四、K 怎么定：肘部法则

K 均值要预先指定组数 KK，但很多时候我们并不知道该分几组。一个常用的经验法是肘部法则：

KK 越大，JJ 必然越小（极端情况每个点自成一组，J=0J = 0），所以不能只看 JJ 小就好。但 JJ 随 KK 下降的速度会变：起初每加一组都大幅降低 JJ，过了某个点后收益骤减、曲线趋平。这个由陡变缓的拐点（形如手肘）对应的 KK，通常就是较合理的组数——它捕捉了”再细分也没多大意义”的临界点。

小结

  • 聚类是无标签下的分组，K 均值把它写成”最小化点到中心的距离平方和”。
  • 核心是交替优化：分配（找最近中心）↔ 更新（移到组均值），保证收敛但可能陷局部最优。
  • 两步就是 EM 的 E 步和 M 步；K 均值 = GMM 的硬分配特例。
  • 肘部法则用 JJ-KK 曲线的拐点来选组数。
  • 从生成式到判别式再到聚类，这条线走完，经典机器学习的几块基石就齐了。