# 数据挖掘十大算法----EM算法(最大期望算法)
> 来源:http://blog.csdn.net/u011067360/article/details/23702125
**概念**
在统计计算中,最大期望(EM)算法是在概率(probabilistic)模型中寻找参数最大似然估计或者最大后验估计的算法,其中概率模型依赖于无法观测的隐藏变量(Latent Variable)。
最大期望经常用在机器学习和计算机视觉的数据聚类(Data Clustering)领域。
可以有一些比较形象的比喻说法把这个算法讲清楚。
比如说食堂的大师傅炒了一份菜,要等分成两份给两个人吃,显然没有必要拿来天平一点一点的精确的去称分量,最简单的办法是先随意的把菜分到两个碗中,然后观察是否一样多,把比较多的那一份取出一点放到另一个碗中,这个过程一直迭代地执行下去,直到大家看不出两个碗所容纳的菜有什么分量上的不同为止。(来自百度百科)
EM算法就是这样,假设我们估计知道A和B两个参数,在开始状态下二者都是未知的,并且知道了A的信息就可以得到B的信息,反过来知道了B也就得到了A。可以考虑首先赋予A某种初值,以此得到B的估计值,然后从B的当前值出发,重新估计A的取值,这个过程一直持续到收敛为止。
EM算法还是许多非监督聚类算法的基础(如Cheeseman et al. 1988),而且它是用于学习部分可观察马尔可夫模型(Partially Observable Markov Model)的广泛使用的Baum-Welch前向后向算法的基础。
### 估计_k_个高斯分布的均值
介绍EM算法最方便的方法是通过一个例子。
考虑数据_D_是一实例集合,它由_k_个不同正态分布的混合所得分布所生成。该问题框架在下图中示出,其中_k_=2而且实例为沿着_x_轴显示的点。
每个实例使用一个两步骤过程形成。
首先了随机选择_k_个正态分布其中之一。
其次随机变量_x<sub>i</sub>_按照此选择的分布生成。
这一过程不断重复,生成一组数据点如图所示。为使讨论简单化,我们考虑一个简单情形,即单个正态分布的选择基于统一的概率进行选择,并且_k_个正态分布有相同的方差_σ_<sup>2</sup>,且_σ_<sup>2</sup>已知。
学习任务是输出一个假设_h_=<_μ<sub>1</sub>_…_μ<sub>k</sub>_>,它描述了_k_个分布中每一个分布的均值。我们希望对这些均值找到一个极大似然假设,即一个使_P_(_D_|_h_)最大化的假设_h_。
![](https://box.kancloud.cn/2016-02-11_56bc53035bf6e.png)
注意到,当给定从一个正态分布中抽取的数据实例_x_<sub>1</sub>,_x_<sub>2</sub>, …, _x<sub>m</sub>_时,很容易计算该分布的均值的极大似然假设。
其中我们可以证明极大似然假设是使_m_个训练实例上的误差平方和最小化的假设。
使用当表述一下式,可以得到:
![](https://box.kancloud.cn/2016-02-11_56bc53037906f.png)(公式一)
然而,在这里我们的问题涉及到_k_个不同正态分布的混合,而且我们不能知道哪个实例是哪个分布产生的。因此这是一个涉及隐藏变量的典型例子。
**EM算法步骤**
在上图的例子中,可把每个实例的完整描述看作是三元组<_x<sub>i</sub>_,_z<sub>i</sub>_<sub>1</sub>, _z<sub>i</sub>_<sub>2</sub>>,其中_x<sub>i</sub>_是第_i_个实例的观测值,_z<sub>i</sub>_<sub>1</sub>和_z<sub>i</sub>_<sub>2</sub>表示两个正态分布中哪个被用于产生值_x<sub>i</sub>_。
确切地讲,_z<sub>ij</sub>_在_x<sub>i</sub>_由第_j_个正态分布产生时值为1,否则为0。这里_x<sub>i</sub>_是实例的描述中已观察到的变量,_z<sub>i</sub>_<sub>1</sub>和_z<sub>i</sub>_<sub>2</sub>是隐藏变量。如果_z<sub>i</sub>_<sub>1</sub>和_z<sub>i</sub>_<sub>2</sub>的值可知,就可以用式一来解决均值_μ_<sub>1</sub>和_μ_<sub>2</sub>。因为它们未知,因此我们只能用EM算法。
EM算法应用于我们的_k_均值问题,目的是搜索一个极大似然假设,方法是根据当前假设<_μ_<sub>1</sub>…_μ<sub>k</sub>_>不断地再估计隐藏变量_z<sub>ij</sub>_的期望值。然后用这些隐藏变量的期望值重新计算极大似然假设。这里首先描述这一实例化的EM算法,以后将给出EM算法的一般形式。
为了估计上图中的两个均值,EM算法首先将假设初始化为_h_=<_μ_<sub>1</sub>,_μ_<sub>2</sub>>,其中_μ_<sub>1</sub>和_μ_<sub>2</sub>为任意的初始值。然后重复以下的两个步骤以重估计_h_,直到该过程收敛到一个稳定的_h_值。
步骤1:计算每个隐藏变量_z<sub>ij</sub>_的期望值_E_[_z<sub>ij</sub>_],假定当前假设_h_=<_μ_<sub>1</sub>,_μ_<sub>2</sub>>成立。
步骤2:计算一个新的极大似然假设_h_´=<_μ_<sub>1</sub>´,_μ_<sub>2</sub>´>,假定由每个隐藏变量_z<sub>ij</sub>_所取的值为第1步中得到的期望值_E_[_z<sub>ij</sub>_],然后将假设_h_=<_μ_<sub>1</sub>,_μ_<sub>2</sub>>替换为新的假设_h_´=<_μ_<sub>1</sub>´,_μ_<sub>2</sub>´>,然后循环。
现在考察第一步是如何实现的。步骤1要计算每个_z<sub>ij</sub>_的期望值。此_E_[_z<sub>ij</sub>_]正是实例_x<sub>i</sub>_由第_j_个正态分布生成的概率:
![](https://box.kancloud.cn/2016-02-11_56bc530386d61.png)
![](https://box.kancloud.cn/2016-02-11_56bc5303929d7.png)
因此第一步可由将当前值<_μ_<sub>1</sub>,_μ_<sub>2</sub>>和已知的_x<sub>i</sub>_代入到上式中实现。
在第二步,使用第1步中得到的_E_[_z<sub>ij</sub>_]来导出一新的极大似然假设_h_´=<_μ_<sub>1</sub>´,_μ_<sub>2</sub>´>。如后面将讨论到的,这时的极大似然假设为:
![](https://box.kancloud.cn/2016-02-11_56bc5303a1a95.png)
注意此表达式类似于公式一中的样本均值,它用于从单个正态分布中估计_μ_。新的表达式只是对_μ<sub>j</sub>_的加权样本均值,每个实例的权重为其由第_j_个正态分布产生的期望值。
**上面估计_k_个正态分布均值的算法描述了EM方法的要点**:即当前的假设用于估计未知变量,而这些变量的期望值再被用于改进假设。
可以证明,在此算法第一次循环中,EM算法能使似然性_P_(_D_|_h_)增加,除非它已达到局部的最大。因此该算法收敛到对于<_μ_<sub>1</sub>,_μ_<sub>2</sub>>的一个局部极大可能性假设。
** EM算法的一般表述**
上面的EM算法针对的是估计混合正态分布均值的问题。更一般地,EM算法可用于许多问题框架,其中需要估计一组描述基准概率分布的参数_θ_,只给定了由此分布产生的全部数据中能观察到的一部分。
在上面的二均值问题中,感兴趣的参数为_θ_=<_μ_<sub>1</sub>,_μ_<sub>2</sub>>,而全部数据为三元组<_x<sub>i</sub>_,_z<sub>i</sub>_<sub>1</sub>, _z<sub>i</sub>_<sub>2</sub>>,而只有_x<sub>i</sub>_可观察到,一般地令_X_=<_x_<sub>1</sub>, …,_x<sub>m</sub>_>代表在同样的实例中已经观察到的数据,并令_Y_=_X_∪_Z_代表全体数据。注意到未观察到的_Z_可被看作一随机变量,它的概率分布依赖于未知参数_θ_和已知数据_X_。类似地,_Y_是一随机变量,因为它是由随机变量_Z_来定义的。在后续部分,将描述EM算法的一般形式。使用_h_来代表参数_θ_的假设值,而_h_´代表在EM算法的每次迭代中修改的假设。
EM算法通过搜寻使_E_[ln_P_(_Y_|_h_´)]最大的_h_´来寻找极大似然假设_h_´。此期望值是在_Y_所遵循的概率分布上计算,此分布由未知参数_θ_确定。考虑此表达式究竟意味了什么。
首先_P_(_Y_|_h_´)是给定假设_h_´下全部数据_Y_的似然性。其合理性在于我们要寻找一个_h_´使该量的某函数值最大化。
其次使该量的对数ln_P_(_Y_|_h_´)最大化也使_P_(_Y_|_h_´)最大化,如已经介绍过的那样。
第三,引入期望值_E_[ln_P_(_Y_|_h_´)]是因为全部数据_Y_本身也是一随机变量。
已知全部数据_Y_是观察到的_X_和未观察到的_Z_的合并,我们必须在未观察到的_Z_的可能值上取平均,并以相应的概率为权值。换言之,要在随机变量_Y_遵循的概率分布上取期望值_E_[ln_P_(_Y_|_h_´)]。该分布由完全已知的_X_值加上_Z_服从的分布来确定。
_Y_遵从的概率分布是什么?一般来说不能知道此分布,因为它是由待估计的_θ_参数确定的。然而,EM算法使用其当前的假设_h_代替实际参数_θ_,以估计_Y_的分布。现定义一函数_Q_(_h_´|_h_),它将_E_[ln_P_(_Y_|_h_´)]作为_h_´的一个函数给出,在_θ_=_h_和全部数据_Y_的观察到的部分_X_的假定之下。
![](https://box.kancloud.cn/2016-02-11_56bc5303b0269.png)
将_Q_函数写成_Q_(_h_´|_h_)是为了表示其定义是在当前假设_h_等于_θ_的假定下。在EM算法的一般形式里,它重复以下两个步骤直至收敛。
步骤1:估计(E)步骤:使用当前假设_h_和观察到的数据_X_来估计_Y_上的概率分布以计算_Q_(_h_´|_h_)。
![](https://box.kancloud.cn/2016-02-11_56bc5303bd797.png)
步骤2:最大化(M)步骤:将假设_h_替换为使_Q_函数最大化的假设_h_´:
![](https://box.kancloud.cn/2016-02-11_56bc5303cb21d.png)
当函数_Q_连续时,EM算法收敛到似然函数_P_(_Y_|_h_´)的一个不动点。若此似然函数有单个的最大值时,EM算法可以收敛到这个对_h_´的全局的极大似然估计。否则,它只保证收敛到一个局部最大值。因此,EM与其他最优化方法有同样的局限性,如之前讨论的梯度下降,线性搜索和变形梯度等。
总结来说,EM算法就是通过迭代地最大化完整数据的对数似然函数的期望,来最大化不完整数据的对数似然函数。