计本1501、数据挖掘祝盼1502em算法

EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步，另一个为极大步（M步，所以算法被称为EM算法（ExpectationizationAlgorithm。EM算法受到缺失思想影响，最初是为了解决数据缺失情况下的参数估计问题其算法基础和收敛有效性等问题在Dempster，Laird和Rubin三人于1977年所做的文章umlikelihoodfrom pletedataviatheEMalgorithm中给出了详细的阐述。其基本思想是：首先根据己经给出的观测反复迭代，直至最后收敛，迭代结束EMtentVariable)。最大期望经常用在机器学习和计算机视觉的数据聚类(DataClust

ME总体来说，EMEMθ。记已知的样本集为：似然函数（linkehoodfunction：联合概率密度函数称为相对于θ如果是参数空间中能使似然函数最大的θ值则应该“最可能”的参数值，那么就是θ设是定义在实数域上的函数，如果对于任意的实数，都的Hesse矩阵是半正定的，即那么是凸函数。特别地，如果或 ，那么称为严格凸函数0，fJensen不等式表述如下：如果f是凸函数，X是随量，那么[X])X，E[x]xx例如，图2中，实线f是凸函数，X是随量，有0.5的概率是a，有0.5的概b。XabE[f(X)]≥f(E[X])成立。、JensenX，Jensen，关于函数的凹凸性百科中是这样解释的—“中国数学界关于函数凹凸性定义和国外很多定义是反的。国内中的凹凸，是指曲线，而不是指函数，图像的凹凸，

相反”就不会把概念E[f(X)]≥f(E[X])E[f(X)]≤f(E[X])就可以。随量的期设离散型随量X的概率分布为 其中（X若连续型 Y=（X若X是连续型随量，概率密度函数 ，EM我们可以不断地建立的下界（E），然后优化下界（M）。这句话比较抽象，

i，让z。（如果z是连续性的，那 是概率密度函数，需要将可以由前面阐述的内容得到下面的到（2）到（3）利用了Jensen不等式，考虑 是凹函数（二阶导数小0），就是的期望（回想期 中 规则设Y是随量X的函 （g是连续函数），那X是离散型随量，它的分布律为，k=1,2,...。 绝对收敛，有X是连续型随量，它的概率密度 ， 绝对收敛对应于上述问题，Y ，X是， g是 根据凹函数时的Jensen不等式：可以得到（3）好的？假 已经给定，那 了。我们可以通过调整两个概率使下界不断上升，以近 随量变成常数值，这里得到：c为常数，不依赖于。对此式子做进一步推导，我们知 ，那 个概率比值都是c），那么有下式：

的计算就是后验概率，解决了如何选择的问题。这一步就是E步，建 的下界。接下来的M步，就 后，调整，去极大化 整的更大。那么一般的EM算法的步骤如下：循环重复直到收 （E）i，（M）那么究竟怎么确保EM收敛？假定和 后，我们得到E步这一步保证了在给定时，Jensen然后进行M步，固定，并将 使等式成立，等式成立只有是在固定，并按E步得到 第（5）步利用了M步的定义，M步就是将调整到 再次解释一下（4）、（5）、（6）。首先（4）Q（4）Q，能保证等式一定成立。（4）到（5）M，（5）到（6）E保证等式成立条件。也就是说E步会将下界拉到与 一样的高度，而此时发现下界仍然可以上升，因此经过M步后，下界又被拉升，

从前面的推导中我们知道，EMJ，EQ，MQ产生，其中，和未知，。但是不知体的是第产生，即可以使用和表示。这是一个典型的涉及到隐藏变量的例子，隐藏变量为和。可EME步：，即求数据是由第个分布产生的概率denominator=0forjinxrange(k):denominator=denominator+mt.exp(-1/(2*sigma**2)*(X[0,i]-from importfromnumpyimportimportmathassigma=miu_1=miu_2=N=X=zeros((1,foriinX[0,i]=random.randn()*sigma+X[0,i]=random.randn()*sigma+#miu的初始值k=miu=random.random((1,#miu=mat([40.0,Expectations=zeros((N,foriin

j])**forjinnumerator=mt.exp(-1/(2*sigma**2)*(X[0,i]-miu[0,j])Expectations[i,j]=numerator/#oldMiu=miuoldMiu=zeros((1,forjinxrange(k):oldMiu[0,j]=miu[0,j]numerator=0denominator=foriinnumerator=numerator+Expectations[i,j]*X[0,i]denominator=denominator+Expectatio