EM(Expectation-maximization algorithm)翻译为期望最大化算法，是数据挖掘的十大算法之一，主要解决的是当含有隐含变量时，如何利用最大似然法求解未知参数。现实中会遇到多个数据混杂在一起，这个多个类别数据虽然是一个概率分布，但数学期望或方差不同，每次取得一个数据时也不知道这个数据是哪个类别下，每个数据属于哪个类别的信息是一个隐含变量，遇到这种情况时我们不能直接用最大似然法。EM算法中文名称中就已经说明了算法过程，即先求出数学期望的函数，然后求其最大值，逐步求出未知参数。EM算法网上典型的例子是抛硬币计算正反概率问题，本篇也将用这个例子，同时利用数学推导和程序代码来说明EM算法的工作机制及原理。
一、EM算法解决抛硬币问题
1.1 了解EM算法过程
在扔硬币时根据大数定律，只要次数足够多，硬币的正反的概率应该各为50%,或者换个说法，如果是真币那么正反的概率应该都是50%。现在发现两个假币A和B,两种假币的朝正面的概率未知（肯定不是50%），测试人员也没做标记，每次测试时从两枚假币中任意选一个扔10次，记录假币正反的情况，这10次扔的过程为一组数据，共得到5组数据，现需要通过这些数据得到A和B朝正面的概率。这个问题显然是为了说明EM算法设计出来的，世上肯定没有这么笨的测试员。我们也可以换一个没有'设计'的味道而非常自然的例子：两类按正态分布的数据混合在一起，其方差一样、数学期望不一样，现在需要求两类数据的数学期望。显然在用最大似然法求解参数时，对于每个拿到手的数据在这个场景下都有两种可能性，这个可能性也可以理解为一个分布，即这组混合数据中这两类数据各占百分之多少，这个'各占百分之多少'显然又是一个未知量，是需要先求解出来的一个隐含变量。
回到抛硬币的问题上来，这个问题其实是一个二项分布问题，如果存在隐变量有两个以上那就是一个多项分布问题，多项分布的EM算法过程与二项分布一样，EM算法解决这类问题方法分两步：
E步骤：要求未知参数θA,θB，先随机初始化一组未知参数θA,θB，利用这组参数求出每一组数据的分布,在这个问题中就是求出每组数据是假币A或假币B的概率。
M步骤：求出每组分布后，综合这5组数据求出一套新的参数θA,θB，与初始数据比较，如果发现误差在设定范围内则停止，否则拿新的参数继续E步骤。
EM算法解决这个二项分布问题可以用下图来表示:
上图a代表每次知道扔的是假币A或者是B，这种场景下没有隐含变量，可以用传统最大似然法求出A和B的'朝正’概率，这个得到的概率可以验证我们接下来EM算法得到概率是否准确。图b代表每次并不知道扔的是哪个假币，此时用的EM算法。
算法首先初始化一个概率，假设A的正面概率为0.6,B的正面概率是0.5，这两个概率事件是独立不相关的，所以其和并不等于1，接下来选择其中一个假币扔10次、每10次为一组；拿第一组为例，扔出的结果是[H,T,T,T,H,H,T,H,T,H],正面5次反面5次，假设是A货币，则由θA=0.6并结合二项概率分布知，出现这组情况的概率是0.65*(1-0.6)5=0.0007962624；而如果是B,同样可以计算得到出现这样的概率是0.55*(1-0.5)5=0.0009765625，利用归一化处理得到：
P(A)=0.0007962624/(0.0007962624＋0.0009765625)≈0.45
P(B)=0.0009765625/(0.0007962624＋0.0009765625)≈0.55
即在先设定θA=0.6，θB=0.5后出现[H,T,T,T,H,H,T,H,T,H]的情况时，是A币的概率是0.45，是B的概率是0.55；根据这个分布还可以得到分别为A或B时的正反面期望次数:
A币正面的期望次数：5*0.45=2.2次
B币正面的期望次数：5*0.55=2.8次
5次为反的情况可以这样计算:
A币反面的期望次数：5*0.45=2.2次
B币反面的期望次数：5*0.55=2.8次
每组数据是A币或是B币是一个互斥事件，概率之和是1，这里需要和θA、θB区别一下。这样就得到第一组数据分布情况，按此方法顺序计算其他四组数据分布，以上的过程是EM算法的E步骤。
在得到每组数据分布之和后，分别用A、B正面'期望次数'除以正反面总的期望次数，得到新的θA、θB, 判断一下新的一组参数与原参数的误差是否在可接受范围内，如果相差较大，则利用新的这组参数代替原参数重复之前操作；如果误差比较小则结束计算，从而得到最终解。这个过程是EM中的M步骤，E和M步骤一前一后像一套组合拳，在EM算法中这两个步骤也称为一次迭代过程。
1.2 推导EM算法过程
