K均值（K-Means） & 高斯混合模型（GMM）——K均值是高斯混合模型的特例

K-means和GMM（高斯混合模型）两种聚类算法的特点

K-means

• non-probabilistic
• 根据距离判断
• 硬分类
• 球形簇

GMM

• probabilistic
• 根据后验概率判断
• 软分类
• 每一个类是一个高斯分布
• 椭圆形簇

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

算法 K-Means

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

2. repeat

3. E 步：更新簇分配
   $${\alpha }_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{\alpha }_i^{(t+1)}(k){\mathbf{x}}_i}{{\sum }_{i=1}^n{\alpha }_i^{(t+1)}(k)},\text{对于 }k=1,\cdots ,K$$

5. 计算得分：
   $$J^{(t+1)}=\frac{1}{n}\sum _{i=1}^n\sum _{k=1}^K{\alpha }_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 \{\alpha_k^{(0)}, \mu_k^{(0)}, \Sigma_k^{(0)}\}_{k=1}^K {αk(0)​,μk(0)​,Σk(0)​}k=1K​

2. repeat

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

4. M步：重新估计模型参数
   $${\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)}$$$${\Sigma }_k^{(t+1)}=\frac{{\sum }_{i=1}^n{\gamma }_k^{(t)}({\mathbf{x}}_i)({\mathbf{x}}_i-{\hat{\mu }}_k^{(t+1)})({\mathbf{x}}_i-{\hat{\mu }}_k^{(t+1)}{)}^{\top }}{{\sum }_{i=1}^n{\gamma }_k^{(t)}({\mathbf{x}}_i)}$$$${\alpha }_k^{(t+1)}=\frac{1}{n}\sum _{i=1}^n{\gamma }_k^{(t)}({\mathbf{x}}_i)$$

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(\{\alpha_k^{(t+1)}, \mu_k^{(t+1)}, \Sigma_k^{(t+1)}\}_{k=1}^K) = \sum_{i=1}^n \ln \left( \sum_{k=1}^K \alpha_k^{(t+1)} \mathcal{N}({\bm x}_i \mid \mu_k^{(t+1)}, \Sigma_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(\{\alpha_k^{(t+1)}, \mu_k^{(t+1)}, \Sigma_k^{(t+1)}\}_{k=1}^K) - L(\{\alpha_k^{(t)}, \mu_k^{(t)}, \Sigma_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​)∣<τ