EM算法主要思想

會(huì)計(jì)學(xué)1EM算法主要思想內(nèi)容概述1、背景簡(jiǎn)介2、問(wèn)題描述3、EM算法原理4、結(jié)論與討論第1頁(yè)/共15頁(yè)1、背景簡(jiǎn)介EM是一種聚類算法聚類：將數(shù)據(jù)集中的數(shù)據(jù)分成若干類（簇），使類內(nèi)相似度盡可能大，類間相似度盡可能小。聚類算法：基于劃分的方法（K均值）、層次聚類、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法。第2頁(yè)/共15頁(yè)2、問(wèn)題描述EM算法是基于模型的聚類方法，假設(shè)樣本分布符合高斯混合模型，算法目的是確定各個(gè)高斯部件的參數(shù)，充分?jǐn)M合給定數(shù)據(jù)，并得到一個(gè)模糊聚類，即每個(gè)樣本以不同概率屬于每個(gè)高斯分布，概率數(shù)值將由以上各個(gè)參數(shù)計(jì)算得到。第3頁(yè)/共15頁(yè)2、問(wèn)題描述（續(xù)）高斯混合模型被定義為M個(gè)高斯密度函數(shù)的線性組合：其中為均值為，協(xié)方差為的高斯分布，是混合參數(shù)，看做第i個(gè)高斯分布的權(quán)重，表征先驗(yàn)概率。且第4頁(yè)/共15頁(yè)2、問(wèn)題描述（續(xù)）

的概率密度函數(shù)為參數(shù)估計(jì)的最常用方法是最大似然估計(jì)，通過(guò)使似然函數(shù)達(dá)到最大值得到參數(shù)的估計(jì)值。將高斯混合密度函數(shù)中所有待定的參數(shù)記為，則似然函數(shù)為：第5頁(yè)/共15頁(yè)2、問(wèn)題描述（續(xù)）為了使問(wèn)題簡(jiǎn)化，我們求的最大值。這里由于有和的對(duì)數(shù)，求導(dǎo)后形式復(fù)雜，因此不能使用一般的求偏導(dǎo)并令導(dǎo)數(shù)為零的方法。第6頁(yè)/共15頁(yè)3、EM算法原理簡(jiǎn)化的問(wèn)題：某混合高斯分布一共有k個(gè)分布，并且對(duì)于每一個(gè)觀察到的x，如果我們同時(shí)還知道它是屬于k中哪一個(gè)分布的，則求各個(gè)參數(shù)并不是件難事。比如用z來(lái)表示每一個(gè)高斯分布，那么我們的觀察集不僅僅是{x1,x2,x3…},而是{(x1,z2),(x2,z3),(x3,z1)…}而現(xiàn)實(shí)往往是：我們不知道每個(gè)x屬于哪個(gè)分布，也就是說(shuō)z是我們觀察不到的，z是隱藏變量。第7頁(yè)/共15頁(yè)3、EM算法原理（續(xù)）假定可以觀察到Z，問(wèn)題變?yōu)榍笙率阶畲笾档荶是觀察不到的，因此EM算法假設(shè)Z的分布依據(jù)上一輪的估計(jì)參數(shù)確定，求取上式期望的最大值。定義：第8頁(yè)/共15頁(yè)第9頁(yè)/共15頁(yè)對(duì)上式使用拉格朗日乘數(shù)法可得求偏導(dǎo)并令值為零分別得：第10頁(yè)/共15頁(yè)其中，可由下式求得。第11頁(yè)/共15頁(yè)EM算法的具體流程為重復(fù)執(zhí)行以下兩個(gè)步驟直到收斂:第一步稱為E步驟，是根據(jù)參數(shù)初始值或上一次迭代所得結(jié)果值來(lái)計(jì)算似然函數(shù)關(guān)于條件分布的期望：第二步稱為M步驟，是將似然函數(shù)最大化以獲得新的參數(shù)值，用更新使最大化。第12頁(yè)/共15頁(yè)4、結(jié)論與討論1）EM算法比K-means算法計(jì)算復(fù)雜，收斂也較慢，不適于大規(guī)模數(shù)據(jù)集和高維數(shù)據(jù)，但比K-means算法計(jì)算結(jié)果穩(wěn)定、準(zhǔn)確。（數(shù)學(xué)手段加快收斂）2）需要已知樣本聚類數(shù)目（？）3）對(duì)初值敏感（可以多運(yùn)行幾次解決/密度/最大最小原則/模糊/…）4）爬山技術(shù)，局部最優(yōu)解（可以多運(yùn)行幾次解決?）5）對(duì)孤立點(diǎn)敏感，有噪音時(shí)效果差