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,?,K}\Vert {\mathbf{x}}_i?{\mathbf{\mu }}_j^{(t)}{\Vert }^2\\ 0,& \text{否則}\end{array},i=1,?,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,?,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)}{)}^{?}}{\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?)∣<τ

---