數據挖掘十大算法----EM算法（最大期望算法）
概念
在統計計算中，最大期望（EM）算法是在概率（probabilistic）模型中尋找參數最大似然估計或者最大后驗估計的算法，其中概率模型依賴于無法觀測的隱藏變量（Latent Variable）。
最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。
可以有一些比較形象的比喻說法把這個算法講清楚。
比如說食堂的大師傅炒了一份菜，要等分成兩份給兩個人吃，顯然沒有必要拿來天平一點一點的精確的去稱分量，最簡單的辦法是先隨意的把菜分到兩個碗中，然后觀察是否一樣多，把比較多的那一份取出一點放到另一個碗中，這個過程一直迭代地執行下去，直到大家看不出兩個碗所容納的菜有什么分量上的不同為止。（來自百度百科）
EM算法就是這樣，假設我們估計知道A和B兩個參數，在開始狀態下二者都是未知的，并且知道了A的信息就可以得到B的信息，反過來知道了B也就得到了A。可以考慮首先賦予A某種初值，以此得到B的估計值，然后從B的當前值出發，重新估計A的取值，這個過程一直持續到收斂為止。
EM算法還是許多非監督聚類算法的基礎（如Cheeseman et al. 1988），而且它是用于學習部分可觀察馬爾可夫模型（Partially Observable Markov Model）的廣泛使用的Baum-Welch前向后向算法的基礎。
估計k個高斯分布的均值
介紹EM算法最方便的方法是通過一個例子。
考慮數據D是一實例集合，它由k個不同正態分布的混合所得分布所生成。該問題框架在下圖中示出，其中k=2而且實例為沿著x軸顯示的點。
每個實例使用一個兩步驟過程形成。
首先了隨機選擇k個正態分布其中之一。
其次隨機變量xi按照此選擇的分布生成。
這一過程不斷重復，生成一組數據點如圖所示。為使討論簡單化，我們考慮一個簡單情形，即單個正態分布的選擇基于統一的概率進行選擇，并且k個正態分布有相同的方差σ2，且σ2已知。
學習任務是輸出一個假設h=<μ1…μk>，它描述了k個分布中每一個分布的均值。我們希望對這些均值找到一個極大似然假設，即一個使P(D|h)最大化的假設h。
注意到，當給定從一個正態分布中抽取的數據實例x1,x2, …, xm時，很容易計算該分布的均值的極大似然假設。
其中我們可以證明極大似然假設是使m個訓練實例上的誤差平方和最小化的假設。
使用當表述一下式，可以得到：
（公式一）
然而，在這里我們的問題涉及到k個不同正態分布的混合，而且我們不能知道哪個實例是哪個分布產生的。因此這是一個涉及隱藏變量的典型例子。
EM算法步驟
在上圖的例子中，可把每個實例的完整描述看作是三元組<xi,zi1, zi2>，其中xi是第i個實例的觀測值，zi1和zi2表示兩個正態分布中哪個被用于產生值xi。
確切地講，zij在xi由第j個正態分布產生時值為1，否則為0。這里xi是實例的描述中已觀察到的變量，zi1和zi2是隱藏變量。如果zi1和zi2的值可知，就可以用式一來解決均值μ1和μ2。因為它們未知，因此我們只能用EM算法。
EM算法應用于我們的k均值問題，目的是搜索一個極大似然假設，方法是根據當前假設<μ1…μk>不斷地再估計隱藏變量zij的期望值。然后用這些隱藏變量的期望值重新計算極大似然假設。這里首先描述這一實例化的EM算法，以后將給出EM算法的一般形式。
為了估計上圖中的兩個均值，EM算法首先將假設初始化為h=<μ1,μ2>，其中μ1和μ2為任意的初始值。然后重復以下的兩個步驟以重估計h，直到該過程收斂到一個穩定的h值。
步驟1：計算每個隱藏變量zij的期望值E[zij]，假定當前假設h=<μ1,μ2>成立。
步驟2：計算一個新的極大似然假設h′=<μ1′,μ2′>，假定由每個隱藏變量zij所取的值為第1步中得到的期望值E[zij]，然后將假設h=<μ1,μ2>替換為新的假設h′=<μ1′,μ2′>，然后循環。
現在考察第一步是如何實現的。步驟1要計算每個zij的期望值。此E[zij]正是實例xi由第j個正態分布生成的概率：
因此第一步可由將當前值<μ1,μ2>和已知的xi代入到上式中實現。
在第二步，使用第1步中得到的E[zij]來導出一新的極大似然假設h′=<μ1′,μ2′>。如后面將討論到的，這時的極大似然假設為：
注意此表達式類似于公式一中的樣本均值，它用于從單個正態分布中估計μ。新的表達式只是對μj的加權樣本均值，每個實例的權重為其由第j個正態分布產生的期望值。
上面估計k個正態分布均值的算法描述了EM方法的要點：即當前的假設用于估計未知變量，而這些變量的期望值再被用于改進假設。
可以證明，在此算法第一次循環中，EM算法能使似然性P(D|h)增加，除非它已達到局部的最大。因此該算法收斂到對于<μ1,μ2>的一個局部極大可能性假設。
EM算法的一般表述
上面的EM算法針對的是估計混合正態分布均值的問題。更一般地，EM算法可用于許多問題框架，其中需要估計一組描述基準概率分布的參數θ，只給定了由此分布產生的全部數據中能觀察到的一部分。
在上面的二均值問題中，感興趣的參數為θ=<μ1,μ2>，而全部數據為三元組<xi,zi1, zi2>，而只有xi可觀察到，一般地令X=<x1, …,xm>代表在同樣的實例中已經觀察到的數據，并令Y=X∪Z代表全體數據。注意到未觀察到的Z可被看作一隨機變量，它的概率分布依賴于未知參數θ和已知數據X。類似地，Y是一隨機變量，因為它是由隨機變量Z來定義的。在后續部分，將描述EM算法的一般形式。使用h來代表參數θ的假設值，而h′代表在EM算法的每次迭代中修改的假設。
EM算法通過搜尋使E[lnP(Y|h′)]最大的h′來尋找極大似然假設h′。此期望值是在Y所遵循的概率分布上計算，此分布由未知參數θ確定。考慮此表達式究竟意味了什么。
首先P(Y|h′)是給定假設h′下全部數據Y的似然性。其合理性在于我們要尋找一個h′使該量的某函數值最大化。
其次使該量的對數lnP(Y|h′)最大化也使P(Y|h′)最大化，如已經介紹過的那樣。
第三，引入期望值E[lnP(Y|h′)]是因為全部數據Y本身也是一隨機變量。
已知全部數據Y是觀察到的X和未觀察到的Z的合并，我們必須在未觀察到的Z的可能值上取平均，并以相應的概率為權值。換言之，要在隨機變量Y遵循的概率分布上取期望值E[lnP(Y|h′)]。該分布由完全已知的X值加上Z服從的分布來確定。
Y遵從的概率分布是什么？一般來說不能知道此分布，因為它是由待估計的θ參數確定的。然而，EM算法使用其當前的假設h代替實際參數θ，以估計Y的分布。現定義一函數Q(h′|h)，它將E[lnP(Y|h′)]作為h′的一個函數給出，在θ=h和全部數據Y的觀察到的部分X的假定之下。
將Q函數寫成Q(h′|h)是為了表示其定義是在當前假設h等于θ的假定下。在EM算法的一般形式里，它重復以下兩個步驟直至收斂。
步驟1：估計（E）步驟：使用當前假設h和觀察到的數據X來估計Y上的概率分布以計算Q(h′|h)。
步驟2：最大化（M）步驟：將假設h替換為使Q函數最大化的假設h′：
當函數Q連續時，EM算法收斂到似然函數P(Y|h′)的一個不動點。若此似然函數有單個的最大值時，EM算法可以收斂到這個對h′的全局的極大似然估計。否則，它只保證收斂到一個局部最大值。因此，EM與其他最優化方法有同樣的局限性，如之前討論的梯度下降，線性搜索和變形梯度等。
總結來說，EM算法就是通過迭代地最大化完整數據的對數似然函數的期望，來最大化不完整數據的對數似然函數。來自： http://blog.csdn.net//u011067360/article/details/23702125