EM算法和K-Means算法

背景：

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

无监督学习：

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

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$ 来更新簇中心

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

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,761评论 5赞 460
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,953评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,998评论 0赞 320
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,248评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,130评论 4赞 356
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,145评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,550评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,236评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,510评论 1赞 291
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,601评论 2赞 310
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,376评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,247评论 3赞 313
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,613评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,911评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,191评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,532评论 2赞 342
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,739评论 2赞 335