混合高斯模型（Mixtures of Gaussians）和EM算法

主要内容：

1、 概率论预备知识

2、 单高斯模型

3、 混合高斯模型

4、 EM算法

5、 K-means聚类算法

一、概率论预备知识

1、 数学期望/均值、方差/标准差

• 设离散型随机变量X的分布律为

则称为X的数学期望或均值

• 设连续型随机变量X的概率密度函数（pdf）为

则其数学期望定义为：

• 随机变量X的方差：
• 随机变量X的标准差：

2、 正态分布、协方差

• 正态分布：

概率密度函数：

• 设（X,Y）为二维随机变量，若存在，则称其为随机变量X和Y的协方差，记为

3、 多维高斯(正态)分布

• 概率密度函数PDF定义如下：

其中，x是维数为n的样本向量（列向量），是期望，是协方差矩阵，表示的行列式，表示的逆矩阵。

二、单高斯模型（Single GaussianModel, SGM）

注意与一维高斯分布不同，其中x是维数为d的样本向量（列向量），u是模型期望，C是模型方差。

对于单高斯模型，由于可以明确训练样本是否属于该高斯模型（如训练人脸肤色模型时，将人脸图像肤色部分分割出来，形成训练集），故μ通常由训练样本均值代替，C由样本方差代替。为了将高斯分布用于模式分类，假设训练样本属于类别K，那么，式(1)可以改为如下形式：

式(2)表明样本属于类别K的概率大小。从而将任意测试样本输入式(2)，均可以得到一个标量，然后根据阈值t来确定该样本是否属于该类别，阈值t可以为经验值，也可以通过实验确定,通常意义下，t一般取0.7-0.75.

几何意义理解：根据单高斯分布pdf的含义，我们可以知道，符合SGM分布的二维点在平面上应该近似椭圆；相应地，三维点在空间中则近似于椭球状。

二维情况如下所示：

三、混合高斯模型（GaussianMixture Model，GMM）

        高斯混合模型是单一高斯概率率密度函数的延伸。例如：有一批观察数据，数据个数为n，在d 维空间中的分布不是椭球状，那么就不适合以一个单一的高密度函数来描述这些数据点的概率密度函数。此时我们采用一个变通方案，假设每个点均由一个单高斯分布生成，而这一批数据共由M（明确）个单高斯模型生成，具体某个数据属于哪个单高斯模型未知，且每个单高斯模型在混合模型中占的比例未知，将所有来自不同分布的数据点混在一起，该分布称为高斯混合分布。

从数学上讲，我们认为这些数据的概率分布密度函数可以通过加权函数表示：

其中

表示第j个SGM的PDF。

         高斯混合模型（GMM），顾名思义，就是数据可以看作是从数个高斯分布中生成出来的。虽然我们可以用不同的分布来随意地构造 XX Mixture Model ，但是 GMM是 最为流行。另外，Mixture Model 本身其实也是可以变得任意复杂的，通过增加 Model 的个数，我们可以任意地逼近任何连续的概率密分布。

令，GMM共有M个SGM，现在，我们就需要通过样本集X来估计GMM的所有参数，样本X的概率公式为：

通常用EM（ExpectationMaximum）算法对GMM参数进行估计。

（1）初始化

方案1：协方差矩阵设为单位矩阵，每个模型比例的先验概率；均值设为随机数。

方案 2：由k均值（k-means）聚类算法对样本进行聚类，利用各类的均值作为，并计算，取各类样本占样本总数的比例。

（2）估计步骤（E-step）

令的后验概率为

（3）最大化步骤（M-step）

更新权值：

更新均值：

更新协方差矩阵：

（4）收敛条件

不断地迭代步骤（2）和（3），重复更新上面三个值，直到

，其中为更新参数后计算的值，即前后两次迭代得到的结果变化小于一定程度则终止迭代，通常。

与k-means作比较：

           与k-means一样，给定的训练样本是，我们将隐含类别标签用表示。与k-means的硬指定不同，我们首先认为是满足一定的概率分布的，这里我们认为满足多项式分布，，其中，有k个值{1,…,k}可以选取。而且我们认为在给定后，满足多值高斯分布，即。由此可以得到联合分布。

另一篇博文对GMM的介绍也深入浅出，值得一看，内容如下：

使用期望最大化算法（Expectation-Maximization）来进行密度估计（density estimation）。

          与k-means一样，给定的训练样本是，我们将隐含类别标签用表示。与k-means的硬指定不同，我们首先认为是满足一定的概率分布的，这里我们认为满足多项式分布，，其中，有k个值{1,…,k}可以选取。而且我们认为在给定后，满足多值高斯分布，即。由此可以得到联合分布。

          整个模型简单描述为对于每个样例，我们先从k个类别中按多项式分布抽取一个，然后根据所对应的k个多值高斯分布中的一个生成样例，。整个过程称作混合高斯模型。注意的是这里的仍然是隐含随机变量。模型中还有三个变量和。最大似然估计为。对数化后如下：

这个式子的最大值是不能通过前面使用的求导数为0的方法解决的，因为求的结果不是close form。但是假设我们知道了每个样例的，那么上式可以简化为：

这时候再对和进行求导得到：

就是样本类别中的比率，是类别为j的样本特征均值，是类别为j的样例的特征的协方差矩阵。

           实际上，当知道后，最大似然估计就近似于高斯判别分析模型（Gaussian discriminant analysis model）了。所不同的是GDA中类别y是伯努利分布，而这里的z是多项式分布，还有这里的每个样例都有不同的协方差矩阵，而GDA中认为只有一个。

          之前我们是假设给定了，实际上是不知道的，那么怎么办呢？考虑之前提到的EM的思想，第一步是猜测隐含类别变量z，第二步是更新其他参数，以获得最大的最大似然估计。具体如下：

         在E步中，我们将其他参数看作常量，计算的后验概率，也就是估计隐含类别变量。估计好后，利用上面的公式重新计算其他参数，计算好后发现最大化最大似然估计时，值又不对了，需要重新计算，周而复始，直至收敛。

的具体计算公式如下：

这个式子利用了贝叶斯公式。

这里我们使用代替了前面的，由简单的0/1值变成了概率值。

          对比K-means可以发现，这里使用了“软”指定，为每个样例分配的类别是有一定的概率的，同时计算量也变大了，每个样例i都要计算属于每一个类别j的概率。与K-means相同的是，结果仍然是局部最优解。对其他参数取不同的初始值进行多次计算不失为一种好方法。

四、EM算法（ExpectationMaximum）

EM的整个推导过程，在这里不细说，详细参考：

http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html

这篇博文写得非常详细，对于理解EM算法很有帮助。

五、 K-means算法

k-means算法是输入聚类个数k，以及包含 n个数据对象的数据库，输出满足方差最小标准的k个聚类。同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。

k-means算法的基本步骤：

（1）从 n个数据对象任意选择k个对象作为初始聚类中心；

（2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；

（3）重新计算每个（有变化）聚类的均值（中心对象）；

（4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2）。

六、参考文献

http://blog.csdn.net/hevc_cjl/article/details/9733945高斯混合模型学习笔记

http://www.cnblogs.com/CBDoctor/archive/2011/11/06/2236286.html 混合高斯模型算法

http://blog.pluskid.org/?p=39 漫谈 Clustering (3): Gaussian Mixture Model

http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006924.html混合高斯模型（Mixtures of Gaussians）和EM算法

http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html （EM算法）The EM Algorithm

http://www.cppblog.com/Terrile/archive/2011/01/19/120051.html GMM的C++实现