数据分析入门系列教程-EM原理

EM 算法又叫做最大期望算法，英文名称为 Expectation Maximization，也是一种聚类算法。是一种迭代算法，通过寻找最大似然估计值，来确定聚类。

什么是最大似然呢，假设我们有 A 和 B 两个参数，虽然我们不知道他们的具体值，但是如果给定了 A，就可以得出 B，反之亦然。那么我们就可以先赋予 A 一个初始值，然后得出一个 B 的估计值，然后再用 B 的当前值估计 A，再比较是否有误差，再反复迭代该过程，知道数据收敛为止。

由此，我们可以得出 EM 算法的过程

EM 算法

EM 算法主要分为三步：初始化参数，观察预期，重新估计。

首先给出每个参数的初始化值，然后再观察预期结果，这两步就是期望步骤，即 Expectation。如果结果存在误差，那么就需要重新估计预期参数，就是最大化步骤，即 Maximization。

而通常情况下，我们的 EM 聚类大多是基于高斯混合模型（GMM）的，即假设数据点是符合高斯分布的。这样，我们就拥有了两个参数来描述一组数据点，均值和方差！

其聚类过程如下

1.首先选择簇的数量（和 K-Means 所做的一样），并随机初始化每个簇的高斯分布参数。

2.给定每个簇的高斯分布，计算每个数据点属于一个特定簇的概率。一个点越靠近高斯的中心，它就越可能属于该簇。

3.基于这些概率，我们计算一组新的高斯分布参数使得簇内的数据点的概率最大化。

4.重复步骤 2 和 3 直到收敛，其中分布在迭代中的变化不大。

举个栗子

假设我们从一所高中里随机抽取了500个同学的鞋码数据，现在我们要在不知道任何信息的情况下对这500个数据进行分类，哪个是来自男生，哪个是来自女生；我们可以通过高斯分布来拟合数据，假设男生女生的鞋码都是符合高斯分布的。给定一个初始的参数值（均值和方差），根据这个已知参数的高斯分布可以粗略地将每一个数据都划分到指定类（属于男生或女生），这样我们就得到了500个鞋码的初始分类情况；接着利用这些属于男生分类的鞋码数据重新估计男生鞋码的高斯分布的参数，同样的方法重新估计出女生鞋码的高斯分布的参数；接着在男生和女生的鞋码分布被重新估计之后，归属于这两个分布的概率也随之会发生变化，那么我们就继续更新，这样多次迭代，直到两类的分布参数变化很小时停止迭代更新。

下面我们再通过一个简单的例子，来深入的理解下 EM 算法。

硬币实验

假设我们有 A 和 B 两种硬币，我们分别做了5组实验，每组实验投掷10次硬币，并统计出现正面的次数：

同时，在投掷的过程中还有一个隐含数据，就是我们并不知道每次投掷的硬币是 A 还是 B，现在再次假设我们知道每次投掷的硬币种类，如下：

现在我们可以求出每种硬币出现正面的次数

P(A) = (5 4)/(10 10) = 0.45，P(B) = (7 8 9)/(10 10 10) = 0.8

但是在实际情况中，我们是不知道正面的概率的，那么下面该如何使用 EM 的思想来求出正面概率呢？

运用 EM 算法

1.初始化参数。

假设硬币 A 和 B 的正面概率分别为 P(A) = 0.5 和 P(B) = 0.9

2.计算预期。

假设实验轮次1投掷的是硬币 A，因为实验1为正面，那么此时的概率为：

C(10,5)代表的是排列组合，意思为在10组中任意取出5组的组合方式，0.5的5次方乘以0.5的5次方意味5次为正面，5次为反面的概率

再假设实验轮次1投掷的是硬币 B，那么此时正面为5的概率为：

可以看出，这种假设下，实验1投掷硬币 A 的概率更大。

3.使用新的概率迭代

接下来我们再依次计算实验2-5，可以得出此时硬币的顺序为（A，A，B，B，A）。

现在就可以再根据当前得出的硬币顺序，来计算每种硬币正面的概率。然后再使用当前新的概率计算1，2步骤，直到硬币顺序不再改变为止。

与 K-Means 的异同

与 K-Means 算法相比，其最大的不同之处就是聚类的方式，K-Means 是通过距离来判断聚类的，而 EM 是通过概率。

对于 K-Means 算法，由于是通过距离来区分样本直接的差别，且每个样本再计算的时候只能属于一个分类，所以称之为硬聚类算法。而对于 EM 算法，每个样本都有一定的概率和每个聚类相关，所以称之为软聚类。

总结

其实对于 EM 算法来说，当前只要掌握其核心步骤即可。即 E 步骤，就是通过初始化参数值来估计隐含变量，M 步骤就是通过该该估计值来推导出新值并比较，观察差异。最后再迭代 E、M 两步，直到数据不再变化为止。

练习题

请用自己的话，总结下 EM 算法的原理？