简介
EM算法即期望最大化算法，是一种迭代法，它同时估计出每个样本所属的簇类别以及每个簇的概率分布的参数。如果要聚类的样本数据服从它所属的簇的概率分布，则可以通过估计每个簇的概率分布以及每个样本所属的簇来完成聚类。估计每个簇概率分布的参数需要知道样本属于这个簇，而确定每个样本属于哪个簇又需要知道每个簇的概率分布的参数，这个存在循环依赖。EM算法在每次迭代时交替地解决上面的两个问题，直至收敛到局部最优解。
EM算法的原理简述
首先，EM算法解决的是在概率模型中含有无法观测的隐含变量情况下的参数估计问题。假设有m个观察样本，模型的参数为θ，最大化对数似然函数可以写成如下形式：
当概率模型中含有无法被观测的隐含变量时，参数的最大似然估计变为
由于z(i)是未知的，无法直接通过最大似然估计求解参数，这时就需要利用EM算法来求解。假设z(i)对应的分布为Q(z(i))， 并满足ΣQ(z(i))。利用Jensen不等式，可以得到：
要使上式中的等号成立，需要满足：
不等式右侧函数记为r(x|θ)。当等式成立时，我们相当于为待优化的函数找到了一个逼近的下界，然后通过最大化这个下界可以使得待优化函数向更好的方向改进。
图1是一个θ为一维的例子，其中棕色的曲线代表我们待优化的函数，记为f(θ)，优化过程即为找到使得f(θ)取值最大的θ。在当前θ的取值下（即图中绿色的位置），可以计算，此时不等式右侧的函数（记为r(x|θ)）给出了优化函数的一个下界，如图中蓝色曲线所示，其中在θ处两条曲线的取值时相等的。接下来找到使得r(x|θ)最大化的参数θ′，即图中红色的位置，此时f(θ′)的取值比f(θ)（绿色的位置处）有所提升。可以证明，f(θ′)≥r(x|θ)=f(θ)，因此函数是单调的，而且P(x(i),z(i)|θ)∈(0,1)从而函数是有界的。根据函数单调有界必收敛的性质，EM算法的收敛性得证。但是EM算法只保证收敛到局部最优解。当函数为非凸时，以图1为例，如果初始化在左边的区域时，则无法找到右侧的高点。
由上面的推导，EM算法框架可以总结如下，由以下两个步骤交替进行直到收敛。
E步骤：计算隐变量的期望
M步骤：最大化
下图为流程示意图
K均值算法收敛的证明
首先，需要知道的是K均值聚类的迭代算法实际上是一种最大期望算法（Expectation-Maximization algorithm，EM算法），剩下的事情就是说明K均值算法与EM算法的关系了。K均值算法等价于用EM算法求解以下含隐变量的最大似然问题：
其中z∈{1,2,...,k}是模型的隐变量。直观地理解，就是当样本x离第k个簇的中心点μk距离最近时，概率正比于exp(-||x-μz||2)，否则为0。
(1).在E步骤，计算:
这等同于在K均值算法中对于每一个点x(i)找到当前最近的簇z(i)。
(2).在M步骤，找到最优的参数θ={μ1,μ2,...,μk}，使得似然函数最大：
因此，这一步骤等同于找到最优的中心点{μ1,μ2,...,μk}，使得损失函数:
达到最小，此时每个样本x(i)对应的簇z(i)已确定，因此每个簇k对应的最优中心点μk可以由该簇中所有点的平均计算得到，这与K均值算法中根据当前簇的分配更新聚类中心的步骤是等同的。
