EM算法主要思想

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

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