从K-means到GMM

K-means 到 GMM：从距离最小化到概率模型与 EM 推导

目标：从 K-means 的几何距离出发，一步步推导到 高斯混合模型 GMM 与其 EM 算法，用详细数学公式串起：
距离 → 指数形式似然 → 高斯分布 → 混合模型 → 隐变量 → 联合分布与边缘化 → E 步后验 → M 步闭式解 → EM 单调性 → K-means 作为极限情形。

---

1. K-means：基于距离的硬聚类

1.1 模型设定

数据集：

$$X = \{x_1,\dots,x_N\},\quad x_n\in\mathbb{R}^D.$$

簇中心（“原型”）：

$$\{\mu_k\}_{k=1}^K,\quad \mu_k\in\mathbb{R}^D.$$

硬分配变量（隐含的 cluster assignment）：

$$r_{nk}\in\{0,1\},\quad \sum_{k=1}^K r_{nk} = 1,\quad \forall n.$$

1.2 K-means 的目标函数

K-means 最小化簇内平方距离和：

$$J_{\text{kmeans}}(\{\mu_k\},\{r_{nk}\}) = \sum_{n=1}^N \sum_{k=1}^K r_{nk}\|x_n - \mu_k\|^2.$$

算法交替迭代：

• Assignment 步（类似 E 步）：给定中心 ，为每个样本选最近簇：

  $$r_{nk} = \begin{cases} 1, & k = \displaystyle\arg\min_j \|x_n - \mu_j\|^2,\\[4pt] 0, & \text{otherwise}. \end{cases}$$

• Update 步（类似 M 步）：给定分配 ，更新中心为簇内样本均值：

  $$\mu_k = \frac{\sum_{n=1}^N r_{nk} x_n}{\sum_{n=1}^N r_{nk}}.$$

K-means 此时仅是一个几何优化问题，尚无明确的概率结构。

---

2. 从“距离”到“概率”：指数形式与高斯分布

我们希望将“距离近 → 概率大”形式化为一个概率模型。

2.1 能量视角：距离作为“能量”

直觉假设：

点 越靠近中心 ，则“属于这一簇”的可能性越大。

构造一个未归一化的似然/密度：

$$\tilde{p}(x|\mu) = \exp\big(-\lambda \|x - \mu\|^2\big),\quad \lambda>0.$$

• 非负；
• 距离大 ⇒ 指数衰减；
• 但尚未满足“积分为 1”。

2.2 归一化：1 维情形

先看 1 维：

$$\tilde{p}(x|\mu) = \exp\big(-\lambda (x-\mu)^2\big).$$

归一化常数：

$$Z = \int_{-\infty}^{\infty} \exp\big(-\lambda (x-\mu)^2\big)\,dx.$$

平移变量 ：

$$Z = \int_{-\infty}^{\infty} \exp(-\lambda y^2)\,dy.$$

利用高斯积分（经典结果）：

$$\int_{-\infty}^{\infty} e^{-\lambda y^2} dy = \sqrt{\frac{\pi}{\lambda}}.$$

因此：

$$Z = \sqrt{\frac{\pi}{\lambda}}, \quad p(x|\mu) = \frac{1}{Z} e^{-\lambda (x-\mu)^2} = \sqrt{\frac{\lambda}{\pi}}\, e^{-\lambda (x-\mu)^2}.$$

令 ，得到标准 1 维高斯：

$$p(x|\mu,\sigma^2) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right).$$

2.3 D 维情形

在 维空间中：

$$\tilde{p}(x|\mu) = \exp(-\lambda\|x-\mu\|^2),\quad x,\mu\in\mathbb{R}^D.$$

归一化常数：

$$Z = \int_{\mathbb{R}^D} \exp(-\lambda\|x-\mu\|^2) dx.$$

同样平移 ：

$$Z = \int_{\mathbb{R}^D} \exp(-\lambda\|y\|^2) dy = \left(\int_{-\infty}^{\infty} e^{-\lambda y^2} dy\right)^D = \left(\sqrt{\frac{\pi}{\lambda}}\right)^D = \left(\frac{\pi}{\lambda}\right)^{\frac{D}{2}}.$$

于是：

$$p(x|\mu) = \frac{1}{Z}\exp(-\lambda\|x-\mu\|^2) = \left(\frac{\lambda}{\pi}\right)^{\frac{D}{2}} \exp(-\lambda\|x-\mu\|^2).$$

令 ，得：

$$p(x|\mu,\sigma^2 I) = \frac{1}{(2\pi\sigma^2)^{D/2}} \exp\left(-\frac{1}{2\sigma^2}\|x-\mu\|^2\right),$$

即 协方差为 的各向同性多元高斯分布。

结论：
“距离平方的指数形式 + 归一化” ⇒ 高斯分布。

---

3. 从单高斯到高斯混合模型（GMM）

实际数据常呈多峰结构 ⇒ 用多个高斯叠加。

3.1 GMM 定义

设有 个高斯成分，每个成分参数为：

• 权重：，满足
• 均值：
• 协方差矩阵：，对称正定

则 GMM 的边缘分布为：

$$p(x|\theta) = \sum_{k=1}^K \pi_k \, \mathcal{N}(x|\mu_k,\Sigma_k),$$

其中

$$\mathcal{N}(x|\mu_k,\Sigma_k) = \frac{1}{(2\pi)^{D/2}|\Sigma_k|^{1/2}} \exp\Big(-\frac{1}{2}(x-\mu_k)^\top\Sigma_k^{-1}(x-\mu_k)\Big),$$

且

$$\theta = \{\pi_k,\mu_k,\Sigma_k\}_{k=1}^K.$$

3.2 生成过程（引出隐变量）

为刻画“样本来自哪个高斯成分”这一过程，引入隐变量 ：

$$z_n = (z_{n1},\dots,z_{nK})^\top,\quad z_{nk}\in\{0,1\},\quad \sum_{k=1}^K z_{nk}=1.$$

1. 首先选簇（离散选择）：

   $$p(z_{nk}=1) = \pi_k,$$

   紧凑写法（one-hot）：

   $$p(z_n) = \prod_{k=1}^K \pi_k^{z_{nk}}.$$

   说明：只有一个 $ k^ z_{nk^}=1 $，故：

   $$\prod_{k} \pi_k^{z_{nk}} = \pi_{k^*}^1 \prod_{j\ne k^*}\pi_j^{0} = \pi_{k^*}.$$

2. 选定成分后，从对应高斯采样：

   $$p(x_n|z_{nk}=1) = \mathcal{N}(x_n|\mu_k,\Sigma_k),$$

   紧凑写法：

   $$p(x_n|z_n) = \prod_{k=1}^K \mathcal{N}(x_n|\mu_k,\Sigma_k)^{z_{nk}}.$$

3.3 联合分布

由链式法则：

$$p(x_n,z_n) = p(z_n)\,p(x_n|z_n) = \prod_{k=1}^K \left[ \pi_k \mathcal{N}(x_n|\mu_k,\Sigma_k) \right]^{z_{nk}}.$$

3.4 边缘分布 ：对隐变量求和

因为 只能是 K 种 one-hot 取值 ，因此：

$$\begin{aligned} p(x_n) &= \sum_{z_n} p(x_n,z_n) \\ &= \sum_{k=1}^K p(x_n,z_n=e_k) \\ &= \sum_{k=1}^K \pi_k \mathcal{N}(x_n|\mu_k,\Sigma_k), \end{aligned}$$

即回到混合模型形式。

3.5 后验分布（责任度）

利用 Bayes 公式：

$$\gamma_{nk} \triangleq p(z_{nk}=1|x_n) = \frac{p(z_{nk}=1)p(x_n|z_{nk}=1)} {\sum_{j=1}^K p(z_{nj}=1)p(x_n|z_{nj}=1)}.$$

代入 GMM 参数：

$$\gamma_{nk} = \frac{\pi_k\mathcal{N}(x_n|\mu_k,\Sigma_k)} {\sum_{j=1}^K \pi_j\mathcal{N}(x_n|\mu_j,\Sigma_j)}.$$

即 责任度（responsibility），表示“成分 k 对样本 的解释程度”，实现软聚类。

---

4. GMM 的最大似然与 EM 算法

4.1 对数似然与隐变量

观测数据对数似然：

$$\log p(X|\theta) = \sum_{n=1}^N \log p(x_n|\theta) = \sum_{n=1}^N \log\left( \sum_{k=1}^K \pi_k\mathcal{N}(x_n|\mu_k,\Sigma_k)\right).$$

问题：log 内部带有求和 ，难以直接对 求导最大化。

引入隐变量 ，定义完全数据对数似然：

$$\log p(X,Z|\theta) = \sum_{n=1}^N\sum_{k=1}^K z_{nk}\big[ \log\pi_k + \log\mathcal{N}(x_n|\mu_k,\Sigma_k) \big].$$

EM 思想：用 $\mathbb{E}[z{nk}] z{nk} $。

4.2 Q 函数定义

在第 次迭代，已知参数 ，定义：

$$Q(\theta,\theta^{(t)}) = \mathbb{E}_{Z|X,\theta^{(t)}}[\log p(X,Z|\theta)].$$

因为

$$\mathbb{E}_{Z|X,\theta^{(t)}}[z_{nk}] = \gamma_{nk}^{(t)},$$

得到：

$$Q(\theta,\theta^{(t)}) = \sum_{n=1}^N \sum_{k=1}^K \gamma_{nk}^{(t)} \Big( \log\pi_k + \log\mathcal{N}(x_n|\mu_k,\Sigma_k) \Big).$$

4.3 E 步：计算责任度

给定当前参数 ：

$$\gamma_{nk}^{(t)} = p(z_{nk}=1|x_n,\theta^{(t)}) = \frac{\pi_k^{(t)} \mathcal{N}(x_n|\mu_k^{(t)},\Sigma_k^{(t)})} {\sum_{j=1}^K \pi_j^{(t)} \mathcal{N}(x_n|\mu_j^{(t)},\Sigma_j^{(t)})}.$$

4.4 M 步：最大化 Q 得到闭式更新

记

$$N_k = \sum_{n=1}^N \gamma_{nk}^{(t)}.$$

4.4.1 更新混合系数

取与 有关部分：

$$Q_\pi = \sum_{n,k} \gamma_{nk}\log\pi_k.$$

约束：

$$\sum_k \pi_k = 1.$$

构造拉格朗日函数：

$$\mathcal{L}(\pi,\lambda) = \sum_{k=1}^K \big(\sum_{n=1}^N \gamma_{nk}\big)\log\pi_k + \lambda\left(\sum_{k=1}^K \pi_k -1\right).$$

对 求导：

$$\frac{\partial\mathcal{L}}{\partial \pi_k} = \frac{\sum_n\gamma_{nk}}{\pi_k} + \lambda = 0 \quad\Rightarrow\quad \pi_k = -\frac{\sum_n\gamma_{nk}}{\lambda}.$$

套用约束：

$$\sum_k \pi_k = 1 \Rightarrow -\frac{1}{\lambda}\sum_{k}\sum_n\gamma_{nk} = 1.$$

又因为对每个 n, $\sum_k\gamma_{nk}=1$，所以：

$$\sum_k\sum_n\gamma_{nk} = N \Rightarrow -\frac{N}{\lambda} = 1 \Rightarrow \lambda = -N.$$

于是：

$$\pi_k^{(t+1)} = \frac{\sum_n\gamma_{nk}}{N} = \frac{N_k}{N}.$$

4.4.2 更新均值

只取与 有关的 Q 部分：

$$Q_{\mu,\Sigma} = \sum_{n,k} \gamma_{nk} \log\mathcal{N}(x_n|\mu_k,\Sigma_k).$$

展开高斯 log：

$$\log\mathcal{N}(x_n|\mu_k,\Sigma_k) = C - \frac{1}{2}(x_n-\mu_k)^\top\Sigma_k^{-1}(x_n-\mu_k),$$

其中 与 无关。

因此

$$Q_{\mu_k} = -\frac{1}{2}\sum_n \gamma_{nk} (x_n-\mu_k)^\top\Sigma_k^{-1}(x_n-\mu_k).$$

对 求导：

$$\frac{\partial}{\partial\mu_k} (x_n-\mu_k)^\top\Sigma_k^{-1}(x_n-\mu_k) = -2\Sigma_k^{-1}(x_n-\mu_k)$$

故

$$\frac{\partial Q_{\mu_k}}{\partial\mu_k} = -\frac{1}{2} \sum_n \gamma_{nk}\big(-2\Sigma_k^{-1}(x_n-\mu_k)\big) = \sum_n \gamma_{nk} \Sigma_k^{-1}(x_n-\mu_k).$$

令导数为 0：

$$\sum_n \gamma_{nk} \Sigma_k^{-1}(x_n-\mu_k) = 0 \Rightarrow \sum_n \gamma_{nk} (x_n-\mu_k) = 0.$$

展开：

$$\sum_n \gamma_{nk} x_n = \mu_k \sum_n \gamma_{nk} = \mu_k N_k,$$

所以：

$$\mu_k^{(t+1)} = \frac{1}{N_k}\sum_{n=1}^N\gamma_{nk}x_n.$$

4.4.3 更新协方差

再次从：

$$Q_{\Sigma_k} = \sum_n \gamma_{nk}\Big( -\frac{1}{2}\log|\Sigma_k| -\frac{1}{2}(x_n-\mu_k)^\top\Sigma_k^{-1}(x_n-\mu_k) \Big)$$

对 求导。

引用矩阵求导（对称矩阵）公式：

得到：

$$\frac{\partial Q_{\Sigma_k}}{\partial\Sigma_k} = -\frac{1}{2}\sum_n\gamma_{nk}\left[ \Sigma_k^{-1} - \Sigma_k^{-1}(x_n-\mu_k)(x_n-\mu_k)^\top\Sigma_k^{-1} \right].$$

令导数为 0：

$$\sum_n\gamma_{nk}\left[ \Sigma_k^{-1}(x_n-\mu_k)(x_n-\mu_k)^\top\Sigma_k^{-1} -\Sigma_k^{-1} \right]=0.$$

左、右乘 ：

$$\sum_n\gamma_{nk}\left[ (x_n-\mu_k)(x_n-\mu_k)^\top - \Sigma_k \right]=0.$$

→

$$\sum_n\gamma_{nk}(x_n-\mu_k)(x_n-\mu_k)^\top = \sum_n\gamma_{nk}\Sigma_k = N_k \Sigma_k.$$

因此：

$$\Sigma_k^{(t+1)} = \frac{1}{N_k}\sum_{n=1}^N \gamma_{nk} (x_n-\mu_k^{(t+1)})(x_n-\mu_k^{(t+1)})^\top.$$

---

5. EM 单调性：为何每一步都不降低对数似然？

5.1 构造变分下界（ELBO）

对任意分布 ，有：

$$\log p(X|\theta) = \log \sum_Z p(X,Z|\theta) = \log \sum_Z q(Z)\frac{p(X,Z|\theta)}{q(Z)}.$$

用 Jensen 不等式：

$$\log p(X|\theta) \ge \sum_Z q(Z)\log\frac{p(X,Z|\theta)}{q(Z)} \triangleq \mathcal{F}(q,\theta).$$

定义：

$$\mathcal{F}(q,\theta) = \mathbb{E}_q[\log p(X,Z|\theta)] + H(q),$$

其中 为熵。

5.2 KL 分解：log-likelihood 与下界的关系

可以证明：

$$\log p(X|\theta) = \mathcal{F}(q,\theta) + \mathrm{KL}\big(q(Z)\,\|\,p(Z|X,\theta)\big),$$

其中 KL 散度总是非负。

推导：

$$\begin{aligned} \mathcal{F}(q,\theta) &= \sum_Z q(Z)\log\frac{p(X,Z|\theta)}{q(Z)} \\ &= \sum_Z q(Z)\log\frac{p(Z|X,\theta)p(X|\theta)}{q(Z)} \\ &= \log p(X|\theta) + \sum_Z q(Z)\log\frac{p(Z|X,\theta)}{q(Z)} \\ &= \log p(X|\theta) - \mathrm{KL}\big(q(Z)\,\|\,p(Z|X,\theta)\big). \end{aligned}$$

移项即得。

5.3 E 步：固定 ，最优的

当 固定， 是常数。

我们希望最大化
等价于最小化 KL：

$$\mathrm{KL}(q(Z)\,\|\,p(Z|X,\theta^{(t)})).$$

最小值为 0，当且仅当：

$$q^{(t)}(Z) = p(Z|X,\theta^{(t)}).$$

此时：

$$\mathcal{F}(q^{(t)},\theta^{(t)}) = \log p(X|\theta^{(t)}).$$

即：E 步把下界“拉到”当前 log-likelihood 上方，与之相切。

5.4 M 步：固定 ，更新

在 M 步，根据定义：

$$\theta^{(t+1)} = \arg\max_\theta \mathcal{F}(q^{(t)},\theta),$$

因此：

$$\mathcal{F}(q^{(t)},\theta^{(t+1)}) \ge \mathcal{F}(q^{(t)},\theta^{(t)}) = \log p(X|\theta^{(t)}).$$

另一方面，对于新参数 ，依然有分解：

$$\log p(X|\theta^{(t+1)}) = \mathcal{F}(q^{(t)},\theta^{(t+1)}) + \mathrm{KL}\big(q^{(t)}\,\|\,p(Z|X,\theta^{(t+1)})\big) \ge \mathcal{F}(q^{(t)},\theta^{(t+1)}).$$

综合两式：

$$\log p(X|\theta^{(t+1)}) \ge \mathcal{F}(q^{(t)},\theta^{(t+1)}) \ge \mathcal{F}(q^{(t)},\theta^{(t)}) = \log p(X|\theta^{(t)}).$$

因此：

$$\boxed{ \log p(X|\theta^{(t+1)}) \ge \log p(X|\theta^{(t)}), }$$

即 EM 每一步迭代都不会降低对数似然。

5.5 Q 函数与 的关系

在 E 步选定 后：

$$\mathcal{F}(q^{(t)},\theta) = \mathbb{E}_{Z|X,\theta^{(t)}}[\log p(X,Z|\theta)] + H(q^{(t)}),$$

其中 与 无关。

因此，在 M 步最大化 等价于最大化：

$$Q(\theta,\theta^{(t)}) = \mathbb{E}_{Z|X,\theta^{(t)}}[\log p(X,Z|\theta)],$$

也就是前面 M 步推导中使用的 Q 函数。

---

6. K-means 作为 GMM-EM 的极限情况

设 GMM 进行如下约束简化：

1. 所有成分协方差相同且为球形： $$\Sigma_k = \sigma^2 I,\quad \forall k.$$
2. 权重均匀： $$\pi_k = \frac{1}{K},\quad \forall k.$$

则责任度：

$$\gamma_{nk} = \frac{\exp\left(-\frac{1}{2\sigma^2}\|x_n-\mu_k\|^2\right)} {\sum_{j=1}^K \exp\left(-\frac{1}{2\sigma^2}\|x_n-\mu_j\|^2\right)}$$

是“距离平方的 softmax”。

当 时：

• 距离最小的簇对应的指数项远大于其它；
• softmax 退化为 argmin 的 one-hot 分配。

即：

$$\gamma_{nk} \to r_{nk} = \begin{cases} 1, & k = \arg\min_j \|x_n - \mu_j\|^2,\\ 0, & \text{otherwise}. \end{cases}$$

此时：

• E 步 ⇒ 最近中心的硬分配（K-means Assignment）；
• M 步： $$\mu_k = \frac{\sum_n \gamma_{nk}x_n}{\sum_n \gamma_{nk}} \to \frac{\sum_n r_{nk}x_n}{\sum_n r_{nk}},$$ 即 K-means 更新。

因此：

K-means = GMM-EM 在“协方差趋于 0、权重均匀”的极限下的 Hard EM 特例。

---

7. 总结

1. K-means：最小化簇内平方距离；

   • 几何模型，无概率结构；
   • 硬分配（0/1）。

2. 从距离到高斯：

   • 指数能量模型 ；
   • 归一化 ⇒ 高斯分布。

3. GMM：多个高斯的加权和；

   • 引入 one-hot 隐变量 构造联合 ；
   • 边缘化 ⇒ 混合形式 ；
   • 后验 ⇒ 软责任度。

4. EM 算法：

   • E 步：计算 $\gamma_{nk}=p(z_{nk}=1|x_n,\theta^{(t)})$
   • M 步：最大化 Q，得闭式更新 。

5. EM 单调性：

   • 构造变分下界 ，利用 $$\log p(X|\theta) = \mathcal{F}(q,\theta) + \mathrm{KL}(q\|p(Z|X,\theta))$$
   • E 步使 KL=0，下界等于当前 log-likelihood；
   • M 步提升下界 ⇒ log-likelihood 不下降。

6. K-means 与 GMM 的关系：

   • GMM 是 K-means 的概率推广；
   • K-means 是 GMM-EM 在球协方差相同且 的极限 Hard EM。