EM算法及其与k-means算法的关系
EM算法
EM 算法就是含有隐变量的模型参数的极大似然估计法
我们面对一个含有隐变量的概率模型，给定的训练样本是{𝑥(1),…,𝑥(𝑚)}，样本间独立，
我们想找到每个样例隐含的类别z，能使得 p(x,z)。即极大化：
极大化(1.1)式的主要的困难有两个方面：①有隐藏变量 z 存在；②包含和的对数，这使得求偏导比较困难。
既然不能直接最大化L(θ)，我们可以不断地建立L的下界（E步），然后优化下界（M 步）。EM 算法就是这么做的。
Jesen 不等式
对于每一个样例 i，让 𝑄𝑖表示该样例隐含变量 z 的某种分布，𝑄𝑖满足的条件是∑ 𝑧 =
1， 𝑄𝑖 ≥ 0。（如果 z 是连续性的，那么Q是概率密度函数，需要将求和符号换做积分符号）。
我们把𝑄𝑖引入到式(1.1)中，得：
假设θ已经给定，由式（1.2）可得L(θ)的值就取决于𝑄𝑖(𝑧(𝑖))和𝑃(𝑥𝑖,𝑧(𝑖))。我们可以通过调整这两个概率使下界不断上升， 以逼近L(θ)的真实值（M步）。
那么什么时候算是调整好了呢？当不等式变成等式时，说明我们调整后的概率能够等价于L(θ)了。按照这个思路，我们要找到等式成立的条件。在Jensen不等式中说到，当自变量X=E(X)时，即为常数的时候，等式成立，这里得到：
对此式子做进一步推导，我们知道∑ 𝑄𝑖(𝑧) 𝑧 = 1，那么也就有∑ 𝑃(𝑥𝑖,𝑧(𝑖)|𝜃) 𝑧 =constant。(将(1.3)式同时左边的分子分母同时加上Σ𝑧)。把 ∑ 𝑃(𝑥𝑖,𝑧(𝑖)|𝜃) 𝑧 =constant这一项代入到(1.3)式中，得到
所以𝑄𝑖(𝑧(𝑖))可以写成如下形式：
E 步，建立L(θ)的下界。接下来的 M 步，就是在给定𝑄𝑖(𝑧(𝑖))后，调整θ，去极大化 L(θ) 的下界（在固定𝑄𝑖(𝑧(𝑖))后，下界还可以调整的更大）。 那么一般的 EM 算法的步骤如下：
关于收敛性
假定𝜃(𝑡)和𝜃(𝑡+1)是 EM 第 t 次和 t+1 次迭代后的结果。如果我们证明了L(𝜃(𝑡)) ≤
L(𝜃(𝑡+1))，也就是说极大似然估计单调增加，那么最终我们会到达最大似然估计的最大值。
下面来证明，选定𝜃(𝑡)后，我们得到E步：
这一步保证了在给定𝜃(𝑡)时，Jensen不等式中的等式成立，也就是
注意这里t 和i的区别。t表示第t次迭代，i表示第 i个样本。然后进行 M 步，固定
𝑄𝑖 (𝑡)(𝑧(𝑖))，调整𝜃(𝑡)到𝜃(𝑡+1)，我们能得到一下式子：
k-means
假设给定训练样本是{𝑥(1),…,𝑥(𝑚)}，每个𝑥(𝑖) ∈ 𝑅𝑛,但没有了y，也就是说我们不知道每个𝑥(𝑖)对应的类别。K-means算法就是用来将这些样本聚类成k个簇。
同EM算法一样，首先我们先定义k-means的目标函数，如下：
J 函数表示每个样本点到其质心的距离平方和。 K-means 是要将J调整到最小。
假设当前 J 没有达到最小值，那么首先可以固定每个类的质心𝜇𝑗，调整每个样例的所属的类别𝑐(𝑖)来让J函数减少，同样，固定𝑐(𝑖)，调整每个类的质心𝜇𝑗也可以使 J 减小。 这两个过程就是内循环中使 J 单调递减的过程。
下面详细介绍下 K-means 与 EM 的关系，对应于 K-means 来说就是我们一开始不知道每个样例𝑥(𝑖)对应隐含变量，也就是最佳类别𝑐(𝑖)。最开始可以随便指定一个𝑐(𝑖)给它，然后为了让目标函数J最小，我们求出在给定c情况下， J最小时的𝜇𝑗（每个类的质心坐标）， 然而此时发现，可以有更好的𝑐(𝑖)（质心与样例𝑥(𝑖)距离最小的类别）指定给样例𝑥(𝑖)，那么𝑐(𝑖)得到重新调整，上述过程就开始重复了，直到没有更好的𝑐(𝑖)指定。 这样从 K-means 里我们可以看出它其实就是 EM 的体现。
k-means算法中的E步就是更新每个样本所属的类别；M步就是更新每个类别的质心坐标使J最小化
