EM算法和K-Means算法

在实际工作中，会遇到这样的问题，给机器输入大量的特征数据，并希望机器希望学习找到某种共同的特征或者结构，亦或是数据之间存在的某种关联，例如，视频网站根据用户的观看行为进行分组，从而建立不同的推荐策略，或是找到视频是否流畅与用户是否退订之间的关系等。属于无监督学习算法。

包括两大类，一：数据聚类，此类方案往往是通过数次迭代找到数据的最优分割。二：特征变量的关联规则，此类方法利用各种相关性分析找到变量之间的关系。

Kmeans的 核心 是将给定的数据集划分成K个簇，并给出每个数据对应的中心点。算法具体步骤如下：

1：数据预处理，如归一化、离散点处理等

2：随机选取K个簇中心，记为 。

3：定义代价函数： 。

4：令 为迭代步数，重复下面过程直到 收敛

4.1 对于每一个样本将其分到距离最近的簇

4.2 对于每一个类簇k，重新计算类簇的中心

K均值在迭代时，交替方向法求解，假设当前 没有达到最小值，那么首先固定簇中心 ,调整样本 所属的类别 来让 函数减小，然后再固定 ,调整中心 使 减小，这两个过程交替循环， 单调递减，当 递减到最小时， 和 同时收敛。

缺点：

1：受初始值的影响

2：异常值的影响

3：当簇分布相差很大时，不适合

优点：

大数据集， 均值聚类相对是可伸缩和高效的，计算复杂度 ,其中 是数据对象的数目， 是聚类簇数， 是迭代的轮数。尽管算法经常局部最优结束，一般情况下局部最优已经满足要求

调优方向

1：数据归一化和离散点处理

2：合理选择 值

一：手肘法：选择若干个K画均方误差的折线图肉眼查看拐点 二：Gap Statistic方法的基本思路是：引入参考的测度值，其可以通过Monte Carlo采样的方法获得。 

3：采用核函数

利用kmeans假设各个数据簇的数据具有一样的先验概率，并呈现高纬球形分布，但是实际生活中是不常见的。面对非凸的数据分布时，引入核函数来优化。核心：利用非线性核函数将样本映射到高纬空间，并在新的特征空间中进行聚类。非线性映射增加了数据的线性可分的概率。

针对对初始值敏感的改进

K-means++算法：

起步

由于 K-means 算法的分类结果会受到初始点的选取而有所区别，因此有提出这种算法的改进: K-means++ 。

算法步骤

其实这个算法也只是对初始点的选择有改进而已，其他步骤都一样。初始质心选取的基本思路就是，初始的聚类中心之间的相互距离要尽可能的远。

算法描述如下：

步骤一： 随机选取一个样本作为第一个聚类中心；

步骤二：

计算每个样本与当前已有类聚中心最短距离（即与最近一个聚类中心的距离） 这个值越大，表示被选取作为聚类中心的概率较大；

最后，用轮盘法选出下一个聚类中心；

步骤三： 重复步骤二，知道选出 k 个聚类中心 。

选出初始点后，就继续使用标准的 k-means 算法了。

      ISODATA的聚类个数是可变的，因为在聚类的过程中，对类别数有一个“合并”和“分裂”的操作。合并是当聚类结果某一类中样本数太少，或两个类间的距离太近时，将这两个类别合并成一个类别；分裂是当聚类结果中某一类的类内方差太大，将该类进行分裂，分裂成两个类别。

ISODATA分类的过程和K-Means一样，用的也是迭代的思想：先随意给定初始的类别中心，然后做聚类，通过迭代，不断调整这些类别中心，直到得到最好的聚类中心为止。

注：

初始簇个数 ，最终簇大小范围

分裂和合并的标准

每个簇的样本数最小 ，小于这个值不进行分裂

每个簇样本的最大方差 ，大于这个则进行分裂

两个簇之间的最小距离围 ，小于这个则进行合并

EM算法是一种迭代算法，用于含有隐变量的概率模型的极大似然估计，或者说是极大后验概率估计。

算法步骤

输入：观测变量数据Y，隐变量Z，联合分布 ，条件分布

输出：模型参数

1：选择参数的初始值

2：E步：记 为第 次迭代参数 的估计值，在第 次迭代的E步，计算 函数 ，其中， 是再帮给定Y和 下隐变量数据Z的条件概率分布；

3：M步：求使 极大化的 ，确定第 次迭代的参数的估计值 ,

4：重复2，3步，直到收敛

EM算法推导

通过不断求解下界的极大化逼近求解对数似然函数的极大化的算法

含有隐变量的概率模型的极大似然估计

下面证明

利用Jensen不等式

令

则 即函数 增大 ，也可以使得 有尽可能的增大，选择 使得 达到极大，即 现在求 的表达式 = = = =

假设有m个观察样本，模型的参数 ，最大化对数似然函数可以写成如下的形式

当概率模型含有无法观测的隐变量时，参数的最大似然估计

因为含有不可观测的隐变量，无法通过极大似然估计求解参数，这时可以通过EM算法求解。假设 对应的分布 ，并满足 。利用Jensen不等式，可以得到，

。不等式右侧，即为 。当等式成立时，我们相当于优化的函数找到了一个逼近的下界，然后最大化这个下界

EM算法和k-means关系

1：E步骤

2：M步骤：最大化

K均值算法等价于以下隐变量求最大似然问题

相当于E步找到x当前最近的簇

在M步骤 来更新簇中心

#####引用葫芦书和李航机器学习

EM（Expectation-Maximum）算法也称期望最大化算法，它是最常见的隐变量估计方法，在机器学习中有极为广泛的用途，例如常被用来学习高斯混合模型（Gaussian mixture model，简称GMM）的参数；隐式马尔科夫算法（HMM）、LDA主题模型的变分推断等等。

EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），一轮轮迭代更新隐含数据和模型分布参数，直到收敛，即得到我们需要的模型参数。

1. EM算法推导过程

补充知识：Jensen不等式：

如果f是凸函数，函数的期望 大于等于 期望的函数。当且仅当下式中X是常量时，该式取等号。（应用于凹函数时，不等号方向相反）

2. EM算法流程

3. EM算法的其他问题

上面介绍的传统EM算法对初始值敏感，聚类结果随不同的初始值而波动较大。总的来说，EM算法收敛的优劣很大程度上取决于其初始参数。

EM算法可以保证收敛到一个稳定点，即EM算法是一定收敛的。

EM算法可以保证收敛到一个稳定点，但是却不能保证收敛到全局的极大值点，因此它是局部最优的算法，当然，如果我们的优化目标是凸的，则EM算法可以保证收敛到全局最大值，这点和梯度下降法这样的迭代算法相同。

EM算法的简单实例： https://zhuanlan.zhihu.com/p/40991784

参考：

https://zhuanlan.zhihu.com/p/40991784

https://blog.csdn.net/u011067360/article/details/24368085

 EM算法的英文全称是 Expectation Maximization Algorithm——期望极大化算法 ，它采用迭代的方式逼近带隐变量的似然函数。通过对似然函数的一个下界求偏导，得到每一步参数估计的过程。

 这个名称由于缺乏作用对象，让人一头雾水。这里的期望是什么？为什么我们要极大化这个期望，我们试图优化什么？

 这里的期望的含义其实是针对 极大似然估计 中的 似然函数 来说的，这里的期望就是似然函数的一个 下界 ，我们的目的是求这样一个期望:这个下界是根据 詹森不等式(Jensen's inequality） 放缩得到的，为什么要放缩呢？因为我们试图找出一个下界，极大化这个带参数的下界之后，可以无限近似于似然函数。你想，如果这个做法ok的话，意味着什么？意味着我们可以通过这个过程找出极大似然估计或最大后验估计的参数近似解。这也意味着我们可以搞一个迭代法来得到一个近似解。但是即便我说的天花乱坠，这个下界要是不收敛那也白搭。而下界要收敛必须满足两个条件：

 1.这个下界的取值要单调递增（因为每回迭代的结果要比上一次的取值更大）

 2.这个下界必须有上界(这个上界就是对数似然函数，且这一点可以由詹森不等式保证，这个也是EM的核心)

大白话就是 单调有界必有极限 。

我们来证明一下它确实是收敛的。

 首先，在极大似然估计中，我们的目的是根据手头上的 个样本，最大化 后，将参数 估计出来；引入对数： 此时引入辅助变量 我们的对数似然函数就变成了：

设置变分函数： 那么：

根据琴生不等式,对数函数为凸函数(因为 ：等号在 为常数时取到)：

上面的这个下界，就是用来逼近原对数似然函数的，这里我们已经证明了算法收敛的一个条件， 有界性 ；但是在继续进行下一步的时候，我们还有一个问题没搞清楚，那就是变分函数 的具体形式,实际上，我们可以通过琴生不等式等号成立的条件导出我们要的这个变分函数q。

令 为常数：

接着我们代入变分函数 的形式，定义这个下界的第一项：

定义下界的第二项：

对于第二项，我们看看随着迭代步数的增大，它是否是递增的，

我们将不同参数的 与 看作是两个分布，那么这个结果实际上是一个KL散度，它表征两个分布的相似度,其结果总是大于等于0的。

大于等于0的原因：

所以：

H为一个递增的序列，那么剩下的就是Q是否递增了，基于前面提到的这个下界是有上界的，上界就是我们的对数似然函数。在这个前提下，现在我们只要证明，Q递增是整个下界递增的充分必要条件即可。

必要性：

当整个下界递增，即：

那么：

所以 单调递增，必要性得证。

充分性：

因为：

前面已经证明：

又因为：

所以：

即，在 递增的情况下，整个下界递增。

充分性得证。

证毕。

 这个算法名称里提及的期望究竟是什么？

我们说了这么多，实际都是要做一件事，那就是：

由于前面证明过整个下界有界。且只要找到让第i次迭代的Q函数最大的 作为下一次迭代的参数，我们就可以让Q递增，让算法收敛。

我们来看看Q的形式。

这就是为什么叫期望最大算法的原因。

 我们以概率PCA，来展开EM的应用：

 当然这里的应用只涉及变分函数已知情况下的应用，并不涉及广义EM的内容，日后看完文献在来唠唠广义EM，AVE，GAN等内容。

 我们先来算一下PPCA的EM期望的形式：

在 概率PCA 中，我们有提到：

所以：

所以期望里面是这个式子：

我们的目的是要估计出 和 那么我们分别对它们求偏导:

所以：

因为：

代入偏导中

所以：

我们偏导得到的结果就是：

我们会发现我们还有两个估计量没解决，一个是一阶估计量 ,另一个是二阶估计量

在概率PCA中，我们提到过：

那么我们就有了一阶估计量：

二阶估计量可以通过简单的计算得到：

剩下的代入即可.

结果展示：

---