EM算法讲解.ppt

《EM算法讲解.ppt》由会员分享，可在线阅读，更多相关《EM算法讲解.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、提纲1、EM vs K-means2、问题描述3、极大似然估计介绍4、隐藏变量5、EM算法框架6、举例和应用7、实验1、EM vs K-meansK-means:1.数据分为K个簇，随机选取簇中心2.计算每个点到各个簇中心距离dik3.依据dik做决策，划分点的类别4.重新调整簇中心，迭代24步直到收敛。EM:1.数据来自K各未知分布，对分布的参数随机赋值2.计算每一个点来自于各个分布的期望Eik3.根据期望调整分布模型的参数，使得似然最大化。迭代23步直到收敛。Eik 可以作为聚类时候决策的依据2、问题描述假设给定一个样本集D=x1,x2,x3.xn且知道这个样本集是由K个未知模型产生的数据

2、。我们需要通过这个样本集去分别估计这K个概率模型的参数K (K=1,2,3.)使得这K个概率模型产生数据集D的概率最大。2、问题示意图模型参数？数据类别？3、极大似然估计思想你同学与一位猎人一起外出打猎，一只野兔从前方窜过只听一声枪响，野兔应声到下，如果要你推测，这一发命中的子弹是谁打的？这时你会想，这个人一枪就能打中兔子，由于猎人命中的概率大于你的同学，所以打中兔子的应该是猎人。也就是说这时候命中的概率应该属于猎人的概率。极大似然估计的思想：对于已经发生的事情，我们认为产生这个结果所对应的概率应该是最大的。)|(1iipn)|()(1iipLn3、极大似然估计a.设总体X是离散型随机变量，其

3、概率函数为 P(X|) ，其中 是未知参数若已知样本取值为x1,x2,x3.xn则事件X1 = x1 , X2 = x2,Xn = xn 发生的概率为 ：b.直观上来说既然样本出现则概率表达式也就是似然函数表示的概率应该较大。c.所以我们只要求得使上述表达式最大的就是我们要的最接近真实值的 。通常对函数求偏导得到极大值。 Kjj11（1） KjijjixfDP1)()|x( （2） KjjjKniiXifDXPDXP11j1k)()|()|( 3、简化的原问题b.由于我们假设对象时独立地产生，因此对于n个对象数据的数据集D由联合概率a.假设K个分布集合为Z密度函数分别为f1,f2fk,而观察数

4、据X由他们产生的概率为1, 2, k.则观察数据Xi由分布集合Z产生的概率为（3）（4） KjjjiXifDP1)()|x( KjjjjxipxiP1)|()|( nikjijjxfDXP11)()|( nikjijjxPXP11j)|()|( 假设这K个分布Z的参数集合=1,2 K则由上述公式推出:Kjj11其中：3、简化的原问题 01ikZ数据数据Xi来自第来自第K个分布个分布数据数据Xi不是来自第不是来自第K个分布个分布K=1,2,3. i=1,2,3.4、隐藏变量Zik如果我们知道我们观察到的每一个数据x属于哪一个模型，求模型的参数并不难。而现实往往是：我们不知道X来自哪一个分布，我们

5、只能对每一个观测数据都引入隐藏变量此时我们的观察量不仅是X=x1,x2.xn而是:(x1,z11),(x1,z12).(x1,z1k);(x2,z21).(x2,z2k);我们的任务是使得该似然函数的表达式取得最大值得到对应的参数集合 nikjijjxPZDP11j)|(),|( 4、隐藏变量ZikKjj11其中：jkzKkNjkjkNjjkjjjxPzzzxPZDP11121)|(*)|.,()|,( 10i)|(*)|(ikZiikikikxzPzxzE 10)()|(*)(*ikZikiikikxPxPzPz )()|(*) 0(*0)|(*) 1(*1ikiikkiikxPxPZPxP

6、zP )()|(*)|(*k1kiKjjijkizxPxP kjzKkNjkjkNjjkjjjxPzzzxPZDP 11121)|(*)|.,()|,( 4、Zik的期望参数初始化参数初始化expectationMaximization结束结束收敛收敛否是kjzKkNjkjkNjjkjjjxPzzzxPZDP 11121)|(*)|.,()|,( 5、EM算法框架参数初始化：对每一个未知分布赋予初始参数初始化参数集合 =k。k=1,2,3.Expectation:参数集合i，计算每一个观察数据Xi对应分布Zk的期望E(Zik).Maximization:根据E步计算得到的期望集合E，重新计算参

7、数，得到新的集合i+1和i+1。使得似然函数取值最大。直到,收敛。 H1 H2H3H4H5H6H7H8H9H101811781731671581661751701691801.隐藏变量：性别G2.观察数据：（H,(0,1)）和（H,(1,0)3.求每个数据属于男生身高和属于女生身高的期望4.最大似然函数：观察数据的联合概率表达式)(21101121)|(*)|,()|(jkZEkjkjkNjjjjHPwzHPZHP ，随机抽取10位同学测量他们的身高得到数据H假设身高服从高斯分布。分别求男生女生身高的均值和方差。(单位：CM)6、例子根据前面提到求极大似然估计的方法对的各分量k=k,k2求偏导

8、. NjjkNjjkjH11k NjjkNjkjjkkH1122)( KkNNnNjjkkk,.,2 , 1,1 要使得 最大同时满足 根据拉格朗日乘法可以得到)(21101)|(*jkZEkjkjkHPw Kjj116、参数和 关于参数的更新：对原似然函数 求对数得到 kjzKkNjkjkxP 11)|(* )2)H(exp(*21)|(22kkkkjjHP KkNjkjjkNjkkjxPzz111)|(ln*()ln*( （ H1 H2H3H4H5H6H7H8H9H10181178173167158166175170169180 NjjkNjjkjH11k NjjkNjkjjkky1122

9、)( NNnNjjkkk 1 KjjijkiixPxPz1kk)|(*)|(*)( KjjijkiixPxPz1kk)|(*)|(*)( 6、例子E-step:求隐参数期望M-step：根据期望求使得似然函数最大化的参数,2 H1 H2H3H4H5H6H7H8H9H10181178173167158166175170169180E(Zm)0.98458 0.95927 0.81704 0.37782 0.02955 0.30336 0.89674 0.62218 0.54147 0.97863 E(Zf)0.01542 0.04073 0.18296 0.62218 0.97045 0.696

10、64 0.10326 0.37782 0.45853 0.02137 E-step:1=2=0.5,1=177 2=160,12 =22=总体方差20.65106 174.91237 29.56356 0.34894 165.70619 62.20912 M-step:6、例子 H1 H2H3H4H5H6H7H8H9H10181178173167158166175170169180E(Zm)0.90455 0.88587 0.79599 0.48758 0.03342 0.41411 0.84420 0.67607 0.62051 0.90026 E(Zf)0.09545 0.11413 0.

11、20401 0.51242 0.96658 0.58589 0.15580 0.32393 0.37949 0.09974 20.65626 174.34400 27.30195 0.34374 166.65222 44.41165 M-step:用上一步计算得到的参数6、例子6 6、例子6 6、与K-MeansK-Means的区别K-Means硬分类EM软分类6、EM的局限性EM算法的局限性：a.对初始参数敏感，“坏”的参数初始值设置可以导致EM算法陷进一些局最优点。b.EM算法的收敛速度比较慢只有在不存在直接解决的算法的情况下，才应该考虑使用EM算法。因为如果分布很多或数据集只包含很少观测数据点，则EM算法的计算开销可能很大。6、EM的应用(1)不完整数据的估计例如： a.高斯混合模型参数的估计 b.隐马尔科夫模型的参数估计(2)基于概率模型的聚类参考资料1.数据挖掘概念与技术第三版2. 统计学习方法 清华大学出版社 李航3. 互联网结束结束