K-means 是 GMM 的一种特例

对一个特定 GMM 模型的讨论

考虑到在非监督学习 K-means 中，那些不存在的所谓的“标签”也可以被当成“不可见因素”的想法。
本文通过一个特定的 GMM（高斯混合模型，Gaussian Mixture Model）模型讨论了 K-means 算法在该特定模型下可以看做一个 EM 算法。因此可以认为 K-means 算法与 EM 算法在某种先验条件下存在交集。

首先给出以下两个问题的描述：

聚类问题：给定数据点 $x_{1}, x_{2}, \cdots, x_{N} \in \mathbb{R}^{m}$ ，给定分类数目 $K$ ，求出 $K$ 个类中心 $\mu_{1}, \mu_{2}, \cdots, \mu_{K}$ ，使得所有点到距离该点最近的类中心的距离的平方和 $\sum\limits_{i=1}^{N} \min\limits_{1 \le k \le K} \lVert x_{i} - \mu_{k} \rVert_{2}^{2}$ 最小。

含隐变量的最大似然问题：给定数据点 $x_{1}, x_{2}, \cdots, x_{N} \in \mathbb{R}^{m}$ ，给定分类数目 $K$ ，考虑如下生成模型，

$$p(x, z \mid \mu_{1}, \mu_{2}, \cdots, \mu_{K}) \propto \left \{ \begin{aligned} &\exp \left ( -\lVert x-\mu_{z} \rVert_{2}^{2} \right ) & \qquad \lVert x-\mu_{z} \rVert_{2} = \min_{1 \le k \le K} \lVert x-\mu_{k} \rVert_{2} \\ &0 & \qquad \lVert x-\mu_{z} \rVert_{2} > \min_{1 \le k \le K} \lVert x-\mu_{k} \rVert_{2} \end{aligned} \right.$$

模型中 $z \in \{1, 2, \cdots, K\}$ 为隐变量。

这个模型的意义是：先验的假设真的存在那么 $K$ 个中心，只不过看不到而已。而所有的数据确实也是根据这 $K$ 个中心生成的，且这个生成概率是以其最近的“隐形中心”为中心呈高斯分布，并且不认为（零概率）该数据点是由离其较远的“隐形中心”生成的。（因此这个模型的条件还是很苛刻的。）

结论：用 EM 算法解这个含隐变量的最大似然问题等价于用 K-means 算法解聚类问题。

E 步骤：

1. 计算

   $$p(z_{i} \mid x_{i}, \{\mu_{k}\}^{(t)}) \propto \left \{ \begin{aligned} &1 & \qquad \lVert x_{i}-\mu_{z_{i}}^{(t)} \rVert_{2} = \min_{1 \le k \le K} \lVert x_{i}-\mu_{k}^{(t)} \rVert_{2} \\ &0 & \qquad \lVert x_{i}-\mu_{z_{i}}^{(t)} \rVert_{2} > \min_{1 \le k \le K} \lVert x_{i}-\mu_{k}^{(t)} \rVert_{2} \end{aligned} \right.$$

   以及

   $$p(Z \mid X, \{ \mu_{k} \}^{(t)}) = \prod_{i=1}^{N} p(z_{i} \mid x_{i}, \{ \mu_{k} \}^{(t)})$$

   这里使用正比于符号是考虑离数据点最近的中心可能不止一个。

   下面为了简单只讨论只有一个中心，且中心编号为 $y_{i}$ 的情况。

2. 计算目标函数

   $$\begin{aligned} Q(\{ \mu_{k} \} \mid \{ \mu_{k} \}^{(t)}) & = E_{Z \mid X, \{ \mu_{k} \}^{(t)}} [\log p(X, Z \mid \{ \mu_{k} \})] \\ & = \sum_{i=1}^{N} E_{z_{i} \mid x_{i}, \{ \mu_{k} \}^{(t)}} [\log p(x_{i}, z_{i} \mid \{ \mu_{k} \})] \\ & = \sum_{i=1}^{N} \log p(x_{i}, z_{i}=y_{i} \mid \{ \mu_{k} \}) \\ & = \mathrm{const} - \sum_{i=1}^{N} \lVert x_{i} - \mu_{y_{i}} \rVert_{2}^{2} \end{aligned}$$

   所以最大化目标函数就等价于最小化 $Q’(\{ \mu_{k} \} \mid \{ \mu_{k} \}^{(t)}) = \sum\limits_{i=1}^{N} \lVert x_{i} - \mu_{y_{i}} \rVert_{2}^{2}$ 。

M 步骤：

找寻 $\{ \mu_{k} \}$ 使得 $Q’$ 最小。

将指标集 $\{1, 2, \cdots, K \}$ 分割为 $K$ 个，$I_{k} = \{ i \mid y_{i}=k \}$ ，则

$$Q'(\{ \mu_{k} \} \mid \{ \mu_{k} \}^{(t)}) = \sum\limits_{i=1}^{K} \sum_{i \in I_{k}} \lVert x_{i} - \mu_{k} \rVert_{2}^{2}$$

由于求和的每一项都是非负的，所以每一个内层求和 $\sum\limits_{i \in I_{k}} \lVert x_{i} - \mu_{k} \rVert_{2}^{2}$ 都达到最小时，总和最小。

这和 K-means 最小化二范数平方和是一样的。

进阶讨论

以上的讨论是为了简单起见提出了一个简化的 GMM 模型，这个模型里没有提到高斯分布的协方差矩阵的问题。实际上，K-means 在简化 GMM 时，应该是限制协方差矩阵 $\Sigma = \sigma I$ ，再让 $\sigma \to 0$ 。更多的讨论在 这篇论文 的 2.1 节可以找到。