EM算法与K均值算法的关系

---

K均值可以看成是高斯混合模型的特例。

---

对K均值算法与EM算法进行比较后，可以发现它们之间有很大的相似性。K均值算法将数据点硬（hard）分配到聚类中，每个数据点唯一地与一个聚类相关联，而EM算法基于后验概率进行软（soft）分配。事实上，可以从EM算法推导出K均值算法。

考虑一个高斯混合模型，其中混合分量的协方差矩阵由${\sigma }^{2}I$给出，其中${\sigma }^2$是所有分量共享的方差参数，$I$是单位矩阵，因此

$$N(\mathbf{x}|{\mathbf{\mu }}_k,{\Sigma }_k)=\frac{1}{(2\pi {\sigma }^2{)}^{d/2}}\exp \left\{-\frac{1}{2{\sigma }^2}\Vert \mathbf{x}-{\mathbf{\mu }}_k{\Vert }^2\right\}\text{\hspace{1em}(31)}$$

考虑将要应用于这种形式的包含K个分量的高斯混合模型的EM算法，其中将${\sigma }^2$当作固定常数而不是重新估计的参数处理。根据式（12），特定数据点${\mathbf{x}}_i$的后验概率或责任由下式给出：

$${\gamma }_{ik}=\frac{{\pi }_k\exp \left\{-\Vert {\mathbf{x}}_i-{\mathbf{\mu }}_k{\Vert }^2/2{\sigma }^2\right\}}{{\sum }_j{\pi }_j\exp \left\{-\Vert {\mathbf{x}}_i-{\mathbf{\mu }}_j{\Vert }^2/2{\sigma }^2\right\}}\text{\hspace{1em}(32)}$$

考虑极限${\sigma }^2\to 0$，式（32）右侧的分母中包含了以j索引的多个趋于零的项。假设使得$\Vert {\mathbf{x}}_i-{\mathbf{\mu }}_j{\Vert }^2$最小的特定项（例如$j=l$的项）将会最慢地趋于零并支配该平方和。因此，数据点${\mathbf{x}}_i$的责任${\gamma }_{ik}$除了第$l$项外都会趋于零，第l项的责任${\gamma }_{ik}$将趋于1。注意，这独立于${\pi }_k$的值，只要没有任何${\pi }_k$为零即可。因此，在这个极限下，获得了数据点到聚类的硬分配，就像在K均值算法中一样，所以${\gamma }_{ik}\to r_{ik}$，其中$r_{ik}$由式（2）定义。每个数据点因此被分配到与其最近的均值所代表的聚类。

然后EM算法中${\mathbf{\mu }}_k$的重估方程由式（16）给出，并简化为K均值算法的结果[式（4）]。注意，混合系数的重估方程[式（21）]仅是将${\pi }_k$的值重置为分配给聚类k的数据点的比例，这些参数在算法中已不再起作用。

最后，在极限${\sigma }^2\to 0$下，用来给出完整数据对数似然函数期望的式（30），就可以变为

$$E_Z[\ln p(X,Z|\mathbf{\mu },\Sigma ,\pi )]\to -\frac{1}{2}\sum _{n=1}^N\sum _{k=1}^K{r}_{ik}\Vert {\mathbf{x}}_i-{\mathbf{\mu }}_k{\Vert }^2+\text{const}\text{\hspace{1em}(33)}$$

因此，看到在这个极限下，完整数据对数似然函数的最大化期望等价于最小化K均值算法的误差度量J，J由式（34）给出。注意，K均值算法不估计聚类的协方差，只估计聚类的均值。

$$J=\frac{1}{n}\sum _{i=1}^n\sum _{k=1}^K{r}_i(k)\Vert {\mathbf{x}}_i-{\mathbf{\mu }}_k{\Vert }^2\text{\hspace{1em}(34)}$$

---

算法 K-Means

---

1. 初始化$K$，$\tau >0$和 { μ k ( 0 ) } k = 1 K \{\boldsymbol{{\bm {\bm \mu}}}_k^{(0)}\}_{k=1}^K {μk(0)​}k=1K​

2. repeat

3. E 步：更新簇分配
   $$r_i^{(t+1)}(k)=\{\begin{array}{ll}1,& \text{若 }k=\arg {\min }_{j=1,\cdots ,K}\Vert {\mathbf{x}}_i-{\mathbf{\mu }}_j^{(t)}{\Vert }^2\\ 0,& \text{否则}\end{array},i=1,\cdots ,n$$

4. M 步：更新簇中心
   $${\mathbf{\mu }}_k^{(t+1)}=\frac{\sum _{i=1}^n{r}_i^{(t+1)}(k){\mathbf{x}}_i}{\sum _{i=1}^n{r}_i^{(t+1)}(k)},\text{对于 }k=1,\cdots ,K\text{\hspace{1em}(4)}$$

5. 计算得分：
   $$J^{(t+1)}=\frac{1}{n}\sum _{i=1}^n\sum _{k=1}^K{r}_i^{(t+1)}(k)\Vert {\mathbf{x}}_i-{\mathbf{\mu }}_k^{(t+1)}{\Vert }^2$$

6. until$|J^{(t+1)}-J^{(t)}|<\tau$

---

算法 使用EM和高斯混合模型聚类

---

1. 初始化$K$，$\tau >0$， { π k ( 0 ) , μ k ( 0 ) , Σ k ( 0 ) } k = 1 K \{\pi_k^{(0)}, {\bm {\bm \mu}}_k^{(0)}, {\bm \varSigma}_k^{(0)}\}_{k=1}^K {πk(0)​,μk(0)​,Σk(0)​}k=1K​

2. repeat

3. E步：更新簇成员
   $${\gamma }_k^{(t)}({\mathbf{x}}_i)=\frac{{\pi }_k^{(t)}N({\mathbf{x}}_i\mid {\mathbf{\mu }}_k^{(t)},{\Sigma }_k^{(t)})}{\sum _{k=1}^K{\pi }_k^{(t)}N({\mathbf{x}}_i\mid {\mathbf{\mu }}_k^{(t)},{\Sigma }_k^{(t)})}$$

4. M步：重新估计模型参数
   $${\mathbf{\mu }}_k^{(t+1)}=\frac{\sum _{i=1}^n{\gamma }_k^{(t)}({\mathbf{x}}_i){\mathbf{x}}_i}{\sum _{i=1}^n{\gamma }_k^{(t)}({\mathbf{x}}_i)}\text{\hspace{1em}(16)}$$$${\Sigma }_k^{(t+1)}=\frac{\sum _{i=1}^n{\gamma }_k^{(t)}({\mathbf{x}}_i)({\mathbf{x}}_i-{\hat{\mathbf{\mu }}}_k^{(t+1)})({\mathbf{x}}_i-{\hat{\mathbf{\mu }}}_k^{(t+1)}{)}^{\top }}{\sum _{i=1}^n{\gamma }_k^{(t)}({\mathbf{x}}_i)}$$$${\pi }_k^{(t+1)}=\frac{1}{n}\sum _{i=1}^n{\gamma }_k^{(t)}({\mathbf{x}}_i)\text{\hspace{1em}(21)}$$

5. 计算对数似然：
   L ( { π k ( t + 1 ) , μ k ( t + 1 ) , Σ k ( t + 1 ) } k = 1 K ) = ∑ i = 1 n ln ⁡ ( ∑ k = 1 K π k ( t + 1 ) N ( x i ∣ μ k ( t + 1 ) , Σ k ( t + 1 ) ) ) L(\{\pi_k^{(t+1)}, {\bm {\bm \mu}}_k^{(t+1)}, {\bm \varSigma}_k^{(t+1)}\}_{k=1}^K) = \sum\limits_{i=1}^n \ln \left( \sum\limits_{k=1}^K \pi_k^{(t+1)} {N}({\bm x}_i \mid {\bm {\bm \mu}}_k^{(t+1)}, {\bm \varSigma}_k^{(t+1)}) \right) L({πk(t+1)​,μk(t+1)​,Σk(t+1)​}k=1K​)=i=1∑n​ln(k=1∑K​πk(t+1)​N(xi​∣μk(t+1)​,Σk(t+1)​))

6. until ∣ L ( { π k ( t + 1 ) , μ k ( t + 1 ) , Σ k ( t + 1 ) } k = 1 K ) − L ( { π k ( t ) , μ k ( t ) , Σ k ( t ) } k = 1 K ) ∣ < τ |L(\{\pi_k^{(t+1)}, {\bm {\bm \mu}}_k^{(t+1)}, {\bm \varSigma}_k^{(t+1)}\}_{k=1}^K) - L(\{\pi_k^{(t)}, {\bm {\bm \mu}}_k^{(t)}, {\bm \varSigma}_k^{(t)}\}_{k=1}^K)| < \tau ∣L({πk(t+1)​,μk(t+1)​,Σk(t+1)​}k=1K​)−L({πk(t)​,μk(t)​,Σk(t)​}k=1K​)∣<τ

---