# 數據挖掘十大算法----EM算法（最大期望算法） > 來源：http://blog.csdn.net/u011067360/article/details/23702125 **概念** 在統計計算中，最大期望（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_個正態分布其中之一。 其次隨機變量_x_i_按照此選擇的分布生成。 這一過程不斷重復，生成一組數據點如圖所示。為使討論簡單化，我們考慮一個簡單情形，即單個正態分布的選擇基于統一的概率進行選擇，并且_k_個正態分布有相同的方差_σ_²，且_σ_²已知。 學習任務是輸出一個假設_h_=<_μ₁_…_μ_k_>，它描述了_k_個分布中每一個分布的均值。我們希望對這些均值找到一個極大似然假設，即一個使_P_(_D_|_h_)最大化的假設_h_。  注意到，當給定從一個正態分布中抽取的數據實例_x_₁,_x_₂, …, _x_m_時，很容易計算該分布的均值的極大似然假設。 其中我們可以證明極大似然假設是使_m_個訓練實例上的誤差平方和最小化的假設。 使用當表述一下式，可以得到： （公式一） 然而，在這里我們的問題涉及到_k_個不同正態分布的混合，而且我們不能知道哪個實例是哪個分布產生的。因此這是一個涉及隱藏變量的典型例子。 **EM算法步驟** 在上圖的例子中，可把每個實例的完整描述看作是三元組<_x_i_,_z_i_₁, _z_i_₂>，其中_x_i_是第_i_個實例的觀測值，_z_i_₁和_z_i_₂表示兩個正態分布中哪個被用于產生值_x_i_。 確切地講，_z_ij_在_x_i_由第_j_個正態分布產生時值為1，否則為0。這里_x_i_是實例的描述中已觀察到的變量，_z_i_₁和_z_i_₂是隱藏變量。如果_z_i_₁和_z_i_₂的值可知，就可以用式一來解決均值_μ_₁和_μ_₂。因為它們未知，因此我們只能用EM算法。 EM算法應用于我們的_k_均值問題，目的是搜索一個極大似然假設，方法是根據當前假設<_μ_₁…_μ_k_>不斷地再估計隱藏變量_z_ij_的期望值。然后用這些隱藏變量的期望值重新計算極大似然假設。這里首先描述這一實例化的EM算法，以后將給出EM算法的一般形式。 為了估計上圖中的兩個均值，EM算法首先將假設初始化為_h_=<_μ_₁,_μ_₂>，其中_μ_₁和_μ_₂為任意的初始值。然后重復以下的兩個步驟以重估計_h_，直到該過程收斂到一個穩定的_h_值。 步驟1：計算每個隱藏變量_z_ij_的期望值_E_[_z_ij_]，假定當前假設_h_=<_μ_₁,_μ_₂>成立。 步驟2：計算一個新的極大似然假設_h_′=<_μ_₁′,_μ_₂′>，假定由每個隱藏變量_z_ij_所取的值為第1步中得到的期望值_E_[_z_ij_]，然后將假設_h_=<_μ_₁,_μ_₂>替換為新的假設_h_′=<_μ_₁′,_μ_₂′>，然后循環。 現在考察第一步是如何實現的。步驟1要計算每個_z_ij_的期望值。此_E_[_z_ij_]正是實例_x_i_由第_j_個正態分布生成的概率：   ? 因此第一步可由將當前值<_μ_₁,_μ_₂>和已知的_x_i_代入到上式中實現。 在第二步，使用第1步中得到的_E_[_z_ij_]來導出一新的極大似然假設_h_′=<_μ_₁′,_μ_₂′>。如后面將討論到的，這時的極大似然假設為：  注意此表達式類似于公式一中的樣本均值，它用于從單個正態分布中估計_μ_。新的表達式只是對_μ_j_的加權樣本均值，每個實例的權重為其由第_j_個正態分布產生的期望值。 **上面估計_k_個正態分布均值的算法描述了EM方法的要點**：即當前的假設用于估計未知變量，而這些變量的期望值再被用于改進假設。 可以證明，在此算法第一次循環中，EM算法能使似然性_P_(_D_|_h_)增加，除非它已達到局部的最大。因此該算法收斂到對于<_μ_₁,_μ_₂>的一個局部極大可能性假設。 **? EM算法的一般表述** 上面的EM算法針對的是估計混合正態分布均值的問題。更一般地，EM算法可用于許多問題框架，其中需要估計一組描述基準概率分布的參數_θ_，只給定了由此分布產生的全部數據中能觀察到的一部分。 在上面的二均值問題中，感興趣的參數為_θ_=<_μ_₁,_μ_₂>，而全部數據為三元組<_x_i_,_z_i_₁, _z_i_₂>，而只有_x_i_可觀察到，一般地令_X_=<_x_₁, …,_x_m_>代表在同樣的實例中已經觀察到的數據，并令_Y_=_X_∪_Z_代表全體數據。注意到未觀察到的_Z_可被看作一隨機變量，它的概率分布依賴于未知參數_θ_和已知數據_X_。類似地，_Y_是一隨機變量，因為它是由隨機變量_Z_來定義的。在后續部分，將描述EM算法的一般形式。使用_h_來代表參數_θ_的假設值，而_h_′代表在EM算法的每次迭代中修改的假設。 EM算法通過搜尋使_E_[ln_P_(_Y_|_h_′)]最大的_h_′來尋找極大似然假設_h_′。此期望值是在_Y_所遵循的概率分布上計算，此分布由未知參數_θ_確定。考慮此表達式究竟意味了什么。 首先_P_(_Y_|_h_′)是給定假設_h_′下全部數據_Y_的似然性。其合理性在于我們要尋找一個_h_′使該量的某函數值最大化。 其次使該量的對數ln_P_(_Y_|_h_′)最大化也使_P_(_Y_|_h_′)最大化，如已經介紹過的那樣。 第三，引入期望值_E_[ln_P_(_Y_|_h_′)]是因為全部數據_Y_本身也是一隨機變量。 已知全部數據_Y_是觀察到的_X_和未觀察到的_Z_的合并，我們必須在未觀察到的_Z_的可能值上取平均，并以相應的概率為權值。換言之，要在隨機變量_Y_遵循的概率分布上取期望值_E_[ln_P_(_Y_|_h_′)]。該分布由完全已知的_X_值加上_Z_服從的分布來確定。 _Y_遵從的概率分布是什么？一般來說不能知道此分布，因為它是由待估計的_θ_參數確定的。然而，EM算法使用其當前的假設_h_代替實際參數_θ_，以估計_Y_的分布。現定義一函數_Q_(_h_′|_h_)，它將_E_[ln_P_(_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算法就是通過迭代地最大化完整數據的對數似然函數的期望，來最大化不完整數據的對數似然函數。