__K-means算法回顧__：
03 聚類算法 - K-means聚類__K-means算法__，也稱為k-均值聚類算法，是一種非常廣泛使用的聚類算法之一。
假定輸入樣本為S=x1,x2,x3,...,xm,則算法步驟為：
1、選擇初始的k個簇中心點μ1,μ2,...,μk；
2、将樣本Xi标記為距離簇中心最近的簇: labeli;
3、疊代處理所有樣本資料，計算出各個樣本點所屬的對應簇。
4、更新簇中心點坐标：μi；
5、重複上述三個操作(2~4)，直到算法收斂。
算法收斂條件：疊代次數/簇中心變化率/MSE/MAE。
回到這個損失函數J(k，μ) ，我們的目的是将樣本分成k個類，即樣本中有k個隐藏的類别，而這k個類别是什麼我不知道。我想找到這k個分類的坐标，利用這些坐标将樣本集X進行劃分。
EM的思想是，首先我先假定幾個目标分類，但如何知道這些假定的分類是否正确？
我們使用樣本的極大似然估計進行度量，如果找到的分類坐标能夠讓 P(預測結果=真實結果 | k) ,如果能夠找到 k=y 讓__P(預測結果=真實結果)__最大，那麼說明y就是我們的最佳類别。而事實上我們知道，P(預測結果=真實結果)不僅僅依賴于分類的個數k=y，還依賴于分類點的初始值μ或等等其他因素。
我們就可以先固定k=y，然後調整μ的參數。在調整μ的過程中，我們可以獲得一個更好的k值的選擇。
最後重新指定k=ynew的作為初始值，再反複疊代計算 __P(預測結果=真實結果 | k)__的最大值，選擇更好的y值。即我調整的是每一次K-means算法的初始聚類中心點，然後來找到最優的分類結果。
上述過程有幾個難點：
第一，如何指定k=y？ 是每種分類的劃分都取相同的機率，還是不同分類結果有不同的機率？這種度量方式我們不知道。
第二，如何調正參數才能讓最終的P(預測結果=真實結果|k,....)最大？
EM算法分為兩步：
1、E - expectation 期望：估計出隐藏類别y的期望值。
2、M - Maximization 最大化：調整其他參數，使得在隐藏類别y的情況下能夠達到最大值(極大似然估計)，然後在其他參數确定的情況下，重新估計隐藏類别y的期望值。$color{red}{M步就是先算極大似然估計，然後更新期望值。}$
....
四、EM算法引入
EM算法舉例：
公司有男同僚=[A，B，C]，同時有很多漂亮的女職員=[小甲，小章，小乙]。（請勿對号入座）你迫切的懷疑這些男同僚跟這些女職員有“問題”。為了科學的驗證你的猜想，你進行了細緻的觀察。于是：
觀察資料：
1、A，小甲、小乙一起出門了；
2、B，小甲、小章一起出門了；
3、B，小章、小乙一起出門了；
4、C，小乙一起出門了；
收集到了資料，你開始了神秘的EM計算。
__初始化：__你覺得三個同僚一樣帥，一樣有錢，三個美女一樣漂亮，每個人都可能跟每個人有關系。是以，每個男同僚跟每個女職員“有問題”的機率都是1/3;
EM算法中的__E步驟__：
1、A跟小甲出去過了 1/2 * 1/3 = 1/6 次，跟小乙也出去了1/6次；
2、B跟小甲，小章也都出去了1/6次；
3、B跟小乙，小章又出去了1/6次；
4、C跟小乙出去了1/3次；
總計：
A跟小甲出去了1/6次，跟小乙也出去了1/6次 ;
B跟小甲，小乙出去了1/6次，跟小章出去了1/3次；
C跟小乙出去了1/3。
EM算法中的__M步驟__ - 你開始__更新__你的八卦：
A跟小甲，小乙有問題的機率都是1/6 / (1/6 + 1/6) = 1/2；
B跟小甲，小乙有問題的機率是1/6 / (1/6+1/6+1/6+1/6) = 1/4;
B跟小章有問題的機率是(1/6+1/6)/(1/6 * 4) = 1/2;
C跟小乙有問題的機率是1。
EM算法中的__E步驟__ - 然後你又開始根據最新的機率計算了。
1、A跟小甲出去了 1/2 * 1/2 = 1/4 次，跟小乙也出去 1/4 次；
2、B跟小甲出去了1/2 1/4 = 1/8 次， 跟小章出去了 1/2 1/2 = 1/4 次；
3、B跟小乙出去了1/2 1/4 = 1/8 次， 跟小章又出去了 1/2 1/2 = 1/4 次；
4、C跟小乙出去了1次；
EM算法中的__M步驟__ - 重新反思你的八卦：
A跟小甲，小乙有問題的機率都是1/4/ (1/4 + 1/4) = 1/2；
B跟小甲，小乙是 1/8 / (1/8 + 1/4 + 1/4 + 1/8) = 1/6 ;
B跟小章是 2/3 ;
C跟小乙的機率是1。
你繼續計算，反思，總之，最後，你得到了真相。
通過上面的計算我們可以得知，EM算法實際上是一個不停疊代計算的過程，根據我們事先估計的先驗機率A，得出一個結果B，再根據結果B，再計算得到結果A，然後反複直到這個過程收斂。
可以想象飯店的後方大廚，炒了兩盤一樣的菜，現在，菜炒好後從鍋中倒入盤，不可能一下子就配置設定均勻，是以先往兩盤中倒入，然後發現B盤菜少了，就從A中勻出一些，A少了，從B勻.....
五、EM算法概述
EM算法(Expectation Maximization Algorithm, 最大期望算法)是一種疊代類型的算法，是一種在機率模型中尋找參數最大似然估計或者最大後驗估計的算法，其中機率模型依賴于無法觀測的隐藏變量。
1、EM算法流程：
1、初始化分布參數。
2、重複下列兩個操作直到收斂：
__E步驟：__估計隐藏變量的機率分布期望函數；
__M步驟：__根據期望函數重新估計分布參數。
2、EM算法原理
給定的m個訓練樣本{x(1),x(2),...,x(m)}，樣本間獨立，找出樣本的模型參數θ，極大化模型分布的對數似然函數如下：
假定樣本資料中存在隐含資料z={z(1),z(2),...,z(k)}，此時極大化模型分布的對數似然函數如下：
期望回顧
對于離散型随機變量X，我們定義X的數學期望為：
X有i個取值x1~xi,分别乘以i個變量發生的機率pi，加和之後就得到了随機變量的期望EX；
若X是一個随機變量，g(X)是任意實函數，那麼g(X)的數學期望Eg(X)為：
同理，函數乘以函數發生的機率，最後得到了整個函數集合的期望Eg(X);
證明：令Y=g(X)，則Y仍然是一個離散型随機變量，設其可能的取值為yj，j=1,2,3……。于是：
根據期望的定義：
結論：複合函數g(x)的期望，就等同于每個xi取值出現的機率pi，乘以這個xi的在g(x)中的映射值g(xi)；
補充知識：Jensen不等式
如果函數f為凸函數，那麼存在下列公式：
拓展一下更多的點： 若θ1,...,θk≥0，θ1+....+θk=1;則
PS：如果我不是一個凸函數，是凹函數怎麼辦？
結論正好反一反即可。
2、EM算法原理(繼續)
總結了__期望__和__Jensen不等式__的知識後，我們回過頭繼續推導EM算法原理。
Q(z) - 随機變量的分布。每一個取值對應的機率密度之和等于1；
令z的分布為Q(z;θ) ，并且Q(z;θ)≥0；那麼有如下公式：
l(θ) 是我們一開始寫到的極大似然估計的__最大化__的函數。
1~4的公式推導了解後，有這樣一個問題：回到下面這個公式，即 f(E(X))和 E(f(x)) 分别怎麼求？
一般情況下，z是隐含變量，我們不知道應該取多少合适。但有可能可以通過最後得到的這個公式對z進去求解。如果最後兩步相等的話，我們就用公式的最後一步去替代l(θ)，來求這個新公式的最大值。
問題來了，什麼時候最後兩步的公式相等？
根據不等式的性質，當下面式子中log内的随機變量為常數的時候，l(θ)和右邊的式子取等号。
公式推導：
根據Jensen不等式的特性，當下列式子的值為常數的時候，l(θ)函數才能取等号。
最後結論：如果__Q(z；θ) = p(z|x;θ)__ ， l(θ)函數取得等号。
03 EM算法 - EM算法流程和直覺案例![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)