EM算法和K-Means算法

作者: cassie_xs | 来源:发表于2019-10-07 22:00 被阅读0次

背景：

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

无监督学习：

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

K-means 算法步骤

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

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

2：随机选取K个簇中心，记为 $\mu _{1}^0, \mu _{2}^0, ,...\mu _{K}^0,$ 。

3：定义代价函数： $J(c,\mu )=\min_{\mu} \min_{c}\sum_{i=1}^M\vert \vert x_{i} -\mu _{c_{i}} \vert \vert ^2$ 。

4：令 $t=0,1,2...$ 为迭代步数，重复下面过程直到 $J$ 收敛

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

$c_{i}^t \leftarrow argmin_{\mu}\vert \vert x_{i} -\mu _{k}^t \vert \vert$

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

$\mu _{k}^{t+1}\leftarrow argmin_{\mu}\sum_{i:\mu _{c_{i}}=k}\vert \vert x_{i} -\mu _{} \vert \vert ^2$

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

K-means缺点以及如何调优

缺点：

1：受初始值的影响

2：异常值的影响

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

优点：

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

调优方向

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

2：合理选择 $K$ 值

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

3：采用核函数

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

针对K-Means算法的缺点进行改进

针对对初始值敏感的改进

K-means++算法：

起步

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

算法步骤

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

算法描述如下：

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

步骤二：

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

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

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

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

针对K值不容易确定引入了ISODATA算法

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

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

注：

初始簇个数 $K_{0}$ ，最终簇大小范围 $K_{0} /2=<K<=2*K_{0}$

分裂和合并的标准

每个簇的样本数最小 $N_{min}$ ，小于这个值不进行分裂

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

两个簇之间的最小距离围 $D_{min}$ ，小于这个则进行合并

EM算法

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

算法步骤

输入：观测变量数据Y，隐变量Z，联合分布 $P(Y,Z|\theta )$ ，条件分布 $P(Z|Y,\theta )$

输出：模型参数 $\theta$

1：选择参数的初始值 $\theta^{0}$

2：E步：记 $\theta ^i$ 为第 $i$ 次迭代参数 $\theta$ 的估计值，在第 $i+1$ 次迭代的E步，计算 $Q$ 函数 $Q(\theta ,\theta ^i )=E_{z} [logP(Y,Z|\theta)|Y ,\theta ^i )]=\sum_{z}logP(Y,Z|\theta)P(Z|Y,\theta^i)$ ，其中， $P(Z|Y,\theta^i)$ 是再帮给定Y和 $\theta^i$ 下隐变量数据Z的条件概率分布；

3：M步：求使 $Q(\theta ,\theta ^i )$ 极大化的 $\theta$ ，确定第 $i+1$ 次迭代的参数的估计值 $\theta ^{i+1}$ , $\theta ^{i+1}=arg\max_{a}Q(\theta ,\theta ^i)$

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

EM算法推导

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

含有隐变量的概率模型的极大似然估计 $L(\theta )=logP(Y|\theta )=log\sum_{z} P(Y,Z|\theta )=log\sum_{z} P(Y|Z,\theta )P(Z,\theta )$

下面证明 $L(\theta )>L(\theta ^i)$

$L(\theta )-L(\theta ^i)=log\sum_{z} P(Y|Z,\theta )P(Z,\theta )-logP(Y|\theta ^i )$

利用Jensen不等式

$L(\theta )-L(\theta ^i)=log\sum_{z} P(Y|Z,\theta )P(Z,\theta )-logP(Y|\theta ^i )$

$>=\sum_{z} logP(Z|Y,\theta^i )\frac{P(Z,\theta )P(Y|Z,\theta )}{P(Z|Y,\theta^i )} -logP(Y|\theta ^i )=\sum_{z} logP(Z|Y,\theta^i )\frac{P(Z,\theta )P(Y|Z,\theta )}{P(Z|Y,\theta^i )P(Y|\theta ^i )}$

令 $B(\theta ,\theta^i)=L(\theta ^i )+\sum_{z} logP(Z|Y,\theta^i )\frac{P(Z,\theta )P(Y|Z,\theta )}{P(Z|Y,\theta^i )P(Y|\theta ^i )}$

则 $L(\theta )>=B(\theta ,\theta^i)$ 即函数 $B(\theta ,\theta^i)$ 增大 $\theta$ ，也可以使得 $L(\theta )$ 有尽可能的增大，选择 $\theta^{i+1}$ 使得 $B(\theta ,\theta^i)$ 达到极大，即 $\theta^{i+1}=arg\max_{a} {B(\theta ,\theta^i)}$ 现在求 $\theta^{i+1}$ 的表达式 $\theta^{i+1}=arg\max_{\theta }( L(\theta ^i )+\sum_{z} logP(Z|Y,\theta^i )\frac{P(Z,\theta )P(Y|Z,\theta )}{P(Z|Y,\theta^i )P(Y|\theta ^i )})$ = $arg\max_{\theta }(\sum_{z} logP(Z|Y,\theta^i )\frac{P(Z,\theta )P(Y|Z,\theta )}{P(Z|Y,\theta^i )P(Y|\theta ^i )})$ = $arg\max_{\theta }(\sum_{z}P(Z|Y,\theta^i ) logP(Z|\theta )P(Y|Z,\theta ))$ = $arg\max_{\theta }(\sum_{z} P(Z|Y,\theta^i )logP(Y,Z|,\theta ))$ = $arg\max_{\theta }Q(\theta ,\theta^i)$

K-means和EM算法的关系****

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

$\theta =argmax\sum_{i=1}^mlogP(y^i,\theta)$

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

$\theta =argmax\sum_{i=1}^m\sum_{z^i} logP(y^i,z^i|\theta)$

因为含有不可观测的隐变量，无法通过极大似然估计求解参数，这时可以通过EM算法求解。假设 $z^i$ 对应的分布 $Q_{i} (z^i)$ ，并满足 $\sum_{z^i} Q_{i} (z^i)=1$ 。利用Jensen不等式，可以得到，

$\sum_{i=1}^m\sum_{z^i} logP(y^i,z^i|\theta)=\sum_{i=1}^m log\sum_{z^i}Q_{i}(z^i)\frac{P(y^i,z^i|\theta)}{Q_{i}(z^i)} >=\sum_{i=1}^m \sum_{z^i}Q_{i}(z^i)log\frac{P(y^i,z^i|\theta)}{Q_{i}(z^i)}$

$Q_{i}(z^i)=\frac{P(y^i,z^i|\theta)}{\sum_{z^i}P(y^i,z^i|\theta)} =P(z^i|y^i,\theta)$ 。不等式右侧，即为 $r(x\vert \theta )$ 。当等式成立时，我们相当于优化的函数找到了一个逼近的下界，然后最大化这个下界

EM算法和k-means关系

1：E步骤 $Q_{i}(z^i)=\frac{P(y^i,z^i|\theta)}{\sum_{z^i}P(y^i,z^i|\theta)} =P(z^i|y^i,\theta)$

2：M步骤：最大化 $\argmax_{\theta } \sum_{i=1}^m \sum_{z^i}Q_{i}(z^i)log\frac{P(y^i,z^i|\theta)}{Q_{i}(z^i)}$

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

$P(y,z|\mu_{1},\mu_{2},...\mu_{k})=exp(-||y-\mu_{z}||^2)【 if 】||y-\mu_{z}||^2=min ||y-\mu_{k}||^2 else【 0】$

$Q_{i}(z^i)==P(z^i|y^i,\theta) 「1」 if ||x-\mu_{z}||^2=min ||x-\mu_{k}||^2 【 else「 0」$

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

在M步骤 $\theta =\argmax_{\theta } \sum_{i=1}^m \sum_{z^i}Q_{i}(z^i)log\frac{P(y^i,z^i|\theta)}{Q_{i}(z^i)} =const -\sum_{i=1}^m \vert \vert x^i-\mu_{z^i} \vert \vert ^2$ 来更新簇中心

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

EM算法和K-Means算法

背景：

无监督学习：

K-means 算法步骤

K-means缺点以及如何调优

针对K-Means算法的缺点进行改进

针对K值不容易确定引入了ISODATA算法

EM算法

K-means和EM算法的关系****

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

K-Means