高斯混合聚类
原型聚类
聚类方法常见的有原型聚类、密度聚类与层次聚类。原型聚类（prototype-based clustering）假设聚类结构能通过一组原型刻画，即每一个原型代表了对应的类别。高斯混合聚类，也称为高斯混合模型（Gaussian Mixture Model, GMM）是原型聚类的一种聚类方法。
高斯混合聚类
常用的k-means方法在非凸数据上效果很差，例如下方的环形数据集，两个类别的中心点都在中心，使用k-means方法无法将其区分。与采用向量来表示聚类原型的k-means、LVQ（learning vector quantization）不同，高斯混合模型采用概率模型来表示聚类原型。这种聚类方法可以得到每个样本点属于各个类的概率，而不是直接将样本点硬性划为某一类，因此也较为软聚类法。
GMM假设生成一个样本的概率为k个高斯成分生成该样本的概率的加权和，公式表示为：
\(P(x) = \sum_{i=1}^k\lambda_ip(x|u_i,\Sigma_i)\)
其中x为n维样本空间$X$中的随机向量，$p(x|u_i,\Sigma_i)$为服从均值向量$u_i$和协方差矩阵$\Sigma_i$的第i个高斯分布：
\(p(x|u_i,\Sigma_i)=\frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma_i|^{\frac{1}{2}}}exp(-\frac{1}{2}(x-u_i)^T\Sigma_i^{-1}(x-u_i))\)
$\lambda_i$为相应的混合系数，$\lambda_i>0$且$\sum_{i=1}^k\lambda_i=1$。
可以容易的发现，如果我们确定了参数$\lambda_i,u_i,\Sigma_i, i={1,2,…,k}$，就可以推出样本x在各个高斯成分（类别）的概率$p(x|u_i,\Sigma_i)$以及生成该样本的概率$P(x)$。由此，我们的后验概率，生成$x_i$的高斯成分（类别）为$c_i=j, j\in{1,2,…,k}$的概率，可由贝叶斯定理得到：
\begin{equation}
\begin{split}
p(c_i=j|x_i)=&\frac{p(c_i=j)p(x_i|u_j,\Sigma_j)}{P(x_i)}
=&\frac{ \lambda_jp(x_i|u_j,\Sigma_j)}{ \sum_{c=1}^k\lambda_cp(x_i|u_c,\Sigma_c)}
=&\gamma_{ij}
\end{split}
\end{equation}
为方便后面的叙述，我们将$x_i$由高斯成分$c_j$生成的概率记为$\gamma_{ij}$。我们简单的把后验概率$\gamma_{ij}$最大的高斯成分作为样本$x_i$所属的类别$C_i$：
\(C_i = {\arg max}_{j\in\{1,2,...,k\}}\gamma_{ij}\)
现在，我们求解出参数$\lambda_i,u_i,\Sigma_i, i={1,2,…,k}$。对于m个数据的样本集D，采用极大似然估计（最大化（对数）似然）作为优化目标：
\begin{equation}
\begin{split}
LL(D)=&\ln\left(\prod_{i=1}^mp(x_i)\right)
=&\sum_{i=1}^m\ln\left(\sum_{j=1}^k\lambda_jp(x_i|u_j,\Sigma_j)\right)
\end{split}
\end{equation}
到此，我们就基本讲完了GMM。针对目标公式求解参数，我们很容易想到梯度下降法，但由于$u_j,\Sigma_j$与当前的数据分布有关，是一个有实际意义的参数，因此我们通常采用EM算法来进行参数的求解。
EM求解GMM
将$\gamma_{ij}$看做GMM的隐变量，则需要建立参数$x_i,u_j,\Sigma_j$与隐变量之间的关系。
对于M步，假设参数能够使目标公式$LL(D)$最大化，则可以推导出：
\begin{equation}
\begin{split}
\frac{\partial LL(D)}{\partial u_j}=0 \quad &\Rightarrow \quad u_j=\frac{\sum_{i=1}^m\gamma_{ij}x_i}{\sum_{i=1}^m\gamma_{ij}}
\frac{\partial LL(D)}{\partial \Sigma_j}=0 \quad &\Rightarrow \quad \Sigma_j=\frac{\sum_{i=1}^{m}\gamma_{ij}(x_i-u_j)(x_i-u_j)^T}{\sum_{i=1}^m\gamma_{ij}}
\end{split}
\end{equation}
对于$\lambda_j$需要满足条件$\lambda_j>0, \sum_{j=1}^k\lambda_j=1$，因此需要引入拉格朗日乘子：
\(\frac{\partial LL(D)+\alpha\left( \sum_{j=1}^k\lambda_j-1\right)}{\partial \lambda_j}=0 \quad \Rightarrow \quad \lambda_j=\frac{1}{m}\sum_{i=1}^m\gamma_{ij}\)
即，各高斯成分的均值可以通过样本加权平均来估计，样本权重是每个样本属于该成分的后验概率，而每个高斯成分的混合系数可以通过样本属于该成分的平均后验概率确定。
根据上式推导，我们可以获得GMM的EM算法：
- E步：根据当前参数计算各个样本属于每个高斯成分的后验概率$\gamma_{ij}$
- M步：根据上式推导的参数$x_i,u_j,\Sigma_j$与隐变量$\gamma_{ij}$之间的关系，更新参数$x_i,u_j,\Sigma_j$
参考文献 《机器学习》周志华
