【白话机器学习】算法理论+实战之EM聚类
1. 寫在前面
如果想從事數據挖掘或者機器學習的工作，掌握常用的機器學習算法是非常有必要的，常見的機器學習算法：
監督學習算法：邏輯回歸，線性回歸，決策樹，樸素貝葉斯，K近鄰，支持向量機，集成算法Adaboost等
無監督算法：聚類，降維，關聯規則, PageRank等
已發布：
【白話機器學習】算法理論+實戰之K近鄰算法
【白話機器學習】算法理論+實戰之決策樹
【白話機器學習】算法理論+實戰之樸素貝葉斯
【白話機器學習】算法理論+實戰之支持向量機（SVM）
【白話機器學習】算法理論+實戰之AdaBoost算法
【白話機器學習】算法理論+實戰之K-Means聚類算法
【白話機器學習】算法理論+實戰之PCA降維
為了詳細的理解這些原理，曾經看過西瓜書，統計學習方法，機器學習實戰等書，也聽過一些機器學習的課程，但總感覺話語里比較深奧，讀起來沒有耐心，并且理論到處有，而實戰最重要， 所以在這里想用最淺顯易懂的語言寫一個白話機器學習算法理論+實戰系列。
個人認為，理解算法背后的idea和使用，要比看懂它的數學推導更加重要。idea會讓你有一個直觀的感受，從而明白算法的合理性，數學推導只是將這種合理性用更加嚴謹的語言表達出來而已，打個比方，一個梨很甜，用數學的語言可以表述為糖分含量90%，但只有親自咬一口，你才能真正感覺到這個梨有多甜，也才能真正理解數學上的90%的糖分究竟是怎么樣的。如果這些機器學習算法是個梨，本文的首要目的就是先帶領大家咬一口。另外還有下面幾個目的：
檢驗自己對算法的理解程度，對算法理論做一個小總結
能開心的學習這些算法的核心思想， 找到學習這些算法的興趣，為深入的學習這些算法打一個基礎。
每一節課的理論都會放一個實戰案例，能夠真正的做到學以致用，既可以鍛煉編程能力，又可以加深算法理論的把握程度。
也想把之前所有的筆記和參考放在一塊，方便以后查看時的方便。
學習算法的過程，獲得的不應該只有算法理論，還應該有樂趣和解決實際問題的能力！
今天是白話機器學習算法理論+實戰的第九篇之EM聚類。聽到這個名字，就知道這是一個無監督學習算法了，如果使用基于最大似然估計的模型，模型中存在隱變量的時候，就要用到EM算法去做估計。所以這個算法就是含有隱變量的概率模型參數的極大似然估計法，可能我說的這些話你還聽不太懂，什么隱變量，什么極大似然亂七八糟的？沒事，通過今天的學習，就能夠快速的掌握EM算法的工作原理，還能理解極大似然，還能最后通過調用工具實現EM算法并完成一個王者榮耀英雄人物的聚類（玩游戲的時候，是不是會遇到對手搶了你擅長的英雄的情況啊， 那你該如何選一個和這個英雄整體實力差不多的呢？）。哈哈 ，是不是迫不及待了啊？?我們開始吧。
大綱如下：
從一個生活場景引出EM算法的核心思想（分菜均勻，你該如何劃分？）
白話EM算法的工作原理，并舉例子說明（拋硬幣都玩過吧）
看看EM聚類（和KMeans有何不同？）
EM算法實戰 - 對王者榮耀的英雄角色進行聚類（實行聚類之后，我們就可以找到可以互相替換的英雄，也就不怕你的對手選擇了你擅長的英雄了）
OK, let's go!
2. EM算法，還是先從分菜開始吧！
提起EM算法（英文叫做Expectation Maximization，最大期望算法），你可能是第一次聽說過， 但是你知道嗎？?你在生活中可能不止一次用過這個思想了吧， 正所謂我之前常說的算法來源于生活。啥？不信？?那我們看看下面這個場景：
★假設，你炒了一份菜，我想要你把它平均分到兩個碟子里，該怎么分？
你一聽平均分？總不能拿個稱來稱一稱，計算出一半的分量進行平分吧，如果你真這樣做，那不得不承認你是個天才，不用學機器學習了。?反正我感覺大部分人的方法是這樣做的：
先分一部分到碟子 A 中，然后再把剩余的分到碟子 B 中，再來觀察碟子 A 和 B 里的菜是否一樣多，哪個多就勻一些到少的那個碟子里，然后再觀察碟子 A 和 B 里的是否一樣多……
整個過程一直重復下去，直到份量不發生變化為止。
你是采用的哪種方法呢？?如果是后者，那么恭喜你，你已經初步認識了EM算法，并且和它打交道不止一次了。下面的知識對你來說已經灑灑水了。輕松愉快的往下走吧。
在這個例子中你能看到三個主要的步驟：初始化參數，觀察預期和重新估計。首先是先給每個碟子初始化一些菜量，然后再觀察預期，這兩個步驟實際上就是期望步驟（Expectation）簡稱E步。如果結果存在偏差就需要重新估計參數，這個就是最大化步驟（Maximization）簡稱M步。這兩個步驟加起來也就是 EM 算法的過程。哈哈，是不是豁然開朗了啊，趁著這個時候，看看EM算法的具體工作原理吧。
3. EM算法的工作原理
說到 EM 算法，我們需要先來看一個概念“最大似然”，英文是 Maximum Likelihood，Likelihood 代表可能性，所以最大似然也就是最大可能性的意思。
什么是最大似然呢？
★舉個例子，有一男一女兩個同學，現在要對他倆進行身高的比較，誰會更高呢？根據我們的經驗，相同年齡下男性的平均身高比女性的高一些，所以男同學高的可能性會很大。這里運用的就是最大似然的概念。
”那還有一個問題：最大似然估計是什么呢？
★它指的就是一件事情已經發生了，然后反推更有可能是什么因素造成的。還是用一男一女比較身高為例，假設有一個人比另一個人高，反推他可能是男性。最大似然估計是一種通過已知結果，估計參數的方法。
”上面說的這些是啥？EM 算法到底是什么？它和最大似然估計又有什么關系呢？（你這三連問，我有點不知所措）
其實，EM 算法是一種求解最大似然估計的方法，通過觀測樣本，來找出樣本的模型參數。
★再回過來看下開頭我給你舉的分菜的這個例子，實際上最終我們想要的是碟子 A 和碟子 B 中菜的份量，你可以把它們理解為想要求得的模型參數。然后我們通過 EM 算法中的 E 步來進行觀察，然后通過 M 步來進行調整 A 和 B 的參數，最后讓碟子 A 和碟子 B 的參數不再發生變化為止。
”然后，你恍然大悟，哦，原理EM算法就這么簡單啊，哈哈，不要太高估自己了， 實際我們遇到的問題，比分菜復雜的多。不行，那再看看我給你舉的下面這個例子：
拋硬幣大家都玩過吧，假設我們有 A 和 B 兩枚硬幣，我們做了 5 組實驗，每組實驗投擲 10 次，每次只能只有A或者B一枚硬幣。那么我們統計出現每組實驗正面的次數，實驗結果如下：我想問你，你知道，A硬幣和B硬幣各自正面朝上的概率嗎？
怎么樣？蒙了吧， 你說這咋求，每一組實驗，我都不知道用的是A或者B拋的。我怎么算？?那么好，我假設把這個表再給你完善一下：這你能告訴我答案了吧？你說：這還不簡單， 我們不就可以直接求了，令A正面朝上的概率是θA, B正面朝上的概率是θB，然后：哈哈， 漂亮！你知道嗎？一開始我提到這樣一句話：
★如果使用基于最大似然估計的模型，模型中存在隱變量的時候，就要用到EM算法去做估計
”這里的第二列，就是隱含的數據，而A和B就是隱變量。實際中我們是不知道這一列的，就是開始給你的只有實驗組數和正面的次數， 那么你該怎么辦呢？
也就是說，我們如果不知道每一組扔的是A還是B，那么我們就無法去估計θA和θB, 而如果想知道每一組扔的是A還是B，我們就必須先知道A和B正面朝上的概率θA和θB，然后利用極大似然的思想，根據每一組實驗正面朝上的次數去估計出這一輪究竟用的A還是B。?有點繞哈！?你會發現這是一個雞生蛋蛋生雞的問題，無法求解！
那么說了半天，應該怎么辦呢？?這里就采用了EM算法的思想。
★我先隨機初始化一個θA和θB， 有了這兩個參數，我們就能按照極大似然估計出每一組用的是A還是B，然后基于每一組用的是A還是B，我們又能按照極大似然反過來計算出θA和θB，然后又能去估計新的用的是A還是B，然后又能計算新的θA和θB，這樣一輪輪的下去， ?當計算出的新的θA和θB與我們前一輪θA和θB一樣的時候，說明這個θA和θB有可能就是真實的值了。這個就是EM初級版。
”好了，根據我上面說的，我們看看怎么實行吧。這里有兩個問題需要解答一下：
★新估計出的θA和θB一定會更接近真實的θA和θB？答案是：沒錯，一定會更接近真實的θA和θB，數學可以證明，但這超出了本文的主題，請參閱其他書籍或文章。（這就類似你均勻分菜，總會有分好的那一個點吧）
迭代一定會收斂到真實的θA和θB嗎？答案是：不一定，取決于θA和θB的初始化值，一般是會的。
其實，上面介紹的這個只是一個初始的版本，為什么這么說呢？因為我們上面第一次計算概率的時候，我們算出：這時候我們直接取得第一次用硬幣A(下面幾組實驗同理)。
你沒有發現，這樣做決定太硬，太絕對了嗎？?雖然B出現正面次數為5的概率比A的小，但是也不是0啊，就是也有可能出現啊。這時候我們應該考慮進這種可能的情況，那么這時候，第一輪實驗用的A的概率就是: 0.246 / (0.246 + 0.015) = 0.9425；用B的概率就是1-0.9425 = 0.0575。
相比于前面的方法，我們按照最大似然概率，直接將第1輪估計為用的硬幣A，此時的我們更加謹慎，我們只說，有0.9425的概率是硬幣A，有0.0575的概率是硬幣B，不再是非此即彼。這樣我們在估計θA和θB時，就可以用上每一輪實驗的數據，而不是某幾輪實驗的數據，顯然這樣會更好一些。
這一步，我們實際上估計的是用A或者B的一個概率分布，這步就稱作E步。
這樣，每一輪實驗，我們會求出這樣一個表來，分別有A和B的概率：然后，我們在結合著統計結果，按照最大似然概率的法則重新估計新的θA和θB：
★以硬幣A為例， 第一輪的正面次數為5相當于 5次正面，5次反面
0.9425 * 5 = 4.7125(這是正面）
0.9425 * 5 = 4.7125（這是反面）
那么對于硬幣A來說， 可以把五輪的表格畫成下面的形式：這樣， 新的thetaA = 4.22 / (4.22+7.98)=0.35 ?這樣，改變了硬幣A和B的估計方法之后，會發現，新估計的thetaA會更加接近真實的值，因為我們使用了每一輪的數據，而不是某幾輪的數據。
PS：上面這個表我只是為了說明意思，截取過來的一個圖，真實數據并不是這樣的數據，看第一輪也能看出來，真實數據是我上面計算的那個，按照那個計算方法，計算出每一輪的硬幣A的時候正面和反面的數據，硬幣B的正面和方面的數據，然后求新的θA和θB會更加準確一些。
這步中，我們根據E步求出了硬幣A和B在每一輪實驗中的一個概率分布，依據最大似然法則結合所有的數據去估計新的θ1和θ2， 被稱作M步。
這個就是進階版的EM算法。
說到這，EM算法的工作原理可算是介紹完了， 你明白了嗎？
簡單的總結下上面的步驟：
★你能看出 EM 算法中的 E 步驟就是通過舊的參數來計算隱藏變量。然后在 M 步驟中，通過得到的隱藏變量的結果來重新估計參數。直到參數不再發生變化，得到我們想要的結果。
”下面，我們看看EM算法聚類的原理，前面介紹過KMeans聚類，同是聚類，有什么區別？
4. EM聚類的工作原理
EM算法一般用于聚類，也就是無監督模型里面，因為無監督學習沒有標簽（即y值)，EM算法可以先給無監督學習估計一個隱狀態（即標簽），有了標簽，算法模型就可以轉換成有監督學習，這時就可以用極大似然估計法求解出模型最優參數。其中估計隱狀態流程應為EM算法的E步，后面用極大似然估計為M步。
相比于 K-Means 算法，EM 聚類更加靈活，比如下面這兩種情況，K-Means 會得到下面的聚類結果。因為 K-Means 是通過距離來區分樣本之間的差別的，且每個樣本在計算的時候只能屬于一個分類，稱之為是硬聚類算法。而 EM 聚類在求解的過程中，實際上每個樣本都有一定的概率和每個聚類相關，叫做軟聚類算法。
★你可以把 EM 算法理解成為是一個框架，在這個框架中可以采用不同的模型來用 EM 進行求解。常用的 EM 聚類有 GMM 高斯混合模型和 HMM 隱馬爾科夫模型。GMM（高斯混合模型）聚類就是 EM 聚類的一種。比如上面這兩個圖，可以采用 GMM 來進行聚類。
”和 K-Means 一樣，我們事先知道聚類的個數，但是不知道每個樣本分別屬于哪一類。通常，我們可以假設樣本是符合高斯分布的（也就是正態分布）。每個高斯分布都屬于這個模型的組成部分（component），要分成 K 類就相當于是 K 個組成部分。這樣我們可以先初始化每個組成部分的高斯分布的參數，然后再看來每個樣本是屬于哪個組成部分。這也就是 E 步驟。
再通過得到的這些隱含變量結果，反過來求每個組成部分高斯分布的參數，即 M 步驟。反復 EM 步驟，直到每個組成部分的高斯分布參數不變為止。
這樣也就相當于將樣本按照 GMM 模型進行了 EM 聚類。所以說很多KMeans解決不了的問題，EM聚類是可以解決的。在 EM 框架中，我們將潛在類別當做隱藏變量，樣本看做觀察值，把聚類問題轉化為參數估計問題，最終把樣本進行聚類。
最后再多啰嗦一句，EM 算法相當于一個框架，你可以采用不同的模型來進行聚類，比如 GMM（高斯混合模型），或者 HMM（隱馬爾科夫模型）來進行聚類。
GMM 是通過概率密度來進行聚類，聚成的類符合高斯分布（正態分布）。
而 HMM 用到了馬爾可夫過程，在這個過程中，我們通過狀態轉移矩陣來計算狀態轉移的概率。HMM 在自然語言處理和語音識別領域中有廣泛的應用。
好了，也說了EM算法聚類的原理了，下面讓我們實戰吧！
5. EM算法實戰 - 王者榮耀英雄的聚類
上面是EM算法的原理，懂了原理之后，趁熱打鐵，做一個實際的小項目，看看EM算法的威力吧！
5.1 如何使用EM工具包
在 Python 中有第三方的 EM 算法工具包。由于 EM 算法是一個聚類框架，所以你需要明確你要用的具體算法，比如是采用 GMM 高斯混合模型，還是 HMM 隱馬爾科夫模型。
我們主要是用GMM，所以需要引入工具包
from sklearn.mixture import GaussianMixture那么如何創建GMM聚類呢？
★gmm = GaussianMixture(n_components=1, covariance_type='full', max_iter=100)來創建， 參數如下：
n_components：即高斯混合模型的個數，也就是我們要聚類的個數，默認值為 1。如果你不指定 n_components，最終的聚類結果都會為同一個值。
covariance_type：代表協方差類型。一個高斯混合模型的分布是由均值向量和協方差矩陣決定的，所以協方差的類型也代表了不同的高斯混合模型的特征。協方差類型有 4 種取值：
covariance_type=full，代表完全協方差，也就是元素都不為 0；
covariance_type=tied，代表相同的完全協方差；
covariance_type=diag，代表對角協方差，也就是對角不為 0，其余為 0；
covariance_type=spherical，代表球面協方差，非對角為 0，對角完全相同，呈現球面的特性。
max_iter：代表最大迭代次數，EM 算法是由 E 步和 M 步迭代求得最終的模型參數，這里可以指定最大迭代次數，默認值為 100。
創建完GMM聚類器之后，可以傳入數據讓它進行迭代擬合。
我們使用 fit 函數，傳入樣本特征矩陣，模型會自動生成聚類器，然后使用 prediction=gmm.predict(data) 來對數據進行聚類，傳入你想進行聚類的數據，可以得到聚類結果 prediction。
你能看出來擬合訓練和預測可以傳入相同的特征矩陣，這是因為聚類是無監督學習，你不需要事先指定聚類的結果，也無法基于先驗的結果經驗來進行學習。只要在訓練過程中傳入特征值矩陣，機器就會按照特征值矩陣生成聚類器，然后就可以使用這個聚類器進行聚類了。
5.2如何用 EM 算法對王者榮耀數據進行聚類
首先我們知道聚類的原理是“人以群分，物以類聚”。通過聚類算法把特征值相近的數據歸為一類，不同類之間的差異較大，這樣就可以對原始數據進行降維。通過分成幾個組（簇），來研究每個組之間的特性。或者我們也可以把組（簇）的數量適當提升，這樣就可以找到可以互相替換的英雄，比如你的對手選擇了你擅長的英雄之后，你可以選擇另一個英雄作為備選。
5.2.1 數據集的介紹
看看數據的樣子：數據集在這里下載這里我們收集了 69 名英雄的 20 個特征屬性，這些屬性分別是最大生命、生命成長、初始生命、最大法力、法力成長、初始法力、最高物攻、物攻成長、初始物攻、最大物防、物防成長、初始物防、最大每 5 秒回血、每 5 秒回血成長、初始每 5 秒回血、最大每 5 秒回藍、每 5 秒回藍成長、初始每 5 秒回藍、最大攻速和攻擊范圍等。
5.2.2執行流程
在這里插入圖片描述首先加載數據源
在準備階段，我們需要對數據進行探索，包括采用數據可視化技術，讓我們對英雄屬性以及這些屬性之間的關系理解更加深刻，然后對數據質量進行評估，是否進行數據清洗，最后進行特征選擇方便后續的聚類算法
聚類階段：選擇適合的聚類模型，這里我們采用 GMM 高斯混合模型進行聚類，并輸出聚類結果，對結果進行分析。
5.2.3 實戰操作
首先導入包
加載數據
數據可視化的探索 我們將 20 個英雄屬性之間的關系用熱力圖呈現了出來，中間的數字代表兩個屬性之間的關系系數，最大值為 1，代表完全正相關，關系系數越大代表相關性越大。從圖中你能看出來“最大生命”“生命成長”和“初始生命”這三個屬性的相關性大，我們只需要保留一個屬性即可。同理我們也可以對其他相關性大的屬性進行篩選，保留一個。你在代碼中可以看到，我用 features_remain 數組保留了特征選擇的屬性，這樣就將原本的 20 個屬性降維到了 13 個屬性。
結果如下：
特征工程
數據規范化 我們能看到“最大攻速”這個屬性值是百分數，不適合做矩陣運算，因此我們需要將百分數轉化為小數。我們也看到“攻擊范圍”這個字段的取值為遠程或者近戰，也不適合矩陣運算，我們將取值做個映射，用 1 代表遠程，0 代表近戰。然后采用 Z-Score 規范化，對特征矩陣進行規范化。
建模并產生結果，寫入文件
我們采用了 GMM 高斯混合模型，并將結果輸出到 CSV 文件中。這里我將輸出的結果截取了一段（設置聚類個數為 30）：第一列代表的是分組（簇），我們能看到張飛、程咬金分到了一組，牛魔、白起是一組，老夫子自己是一組，達摩、典韋是一組。聚類的特點是相同類別之間的屬性值相近，不同類別的屬性值差異大。因此如果你擅長用典韋這個英雄，不防試試達摩這個英雄。同樣你也可以在張飛和程咬金中進行切換。這樣就算你的英雄被別人選中了，你依然可以有備選的英雄可以使用。
聚類和分類不一樣，聚類是無監督的學習方式，也就是我們沒有實際的結果可以進行比對，所以聚類的結果評估不像分類準確率一樣直觀，那么有沒有聚類結果的評估方式呢？這里我們可以采用 Calinski-Harabaz 指標，代碼如下：
from sklearn.metrics import calinski_harabaz_score print(calinski_harabaz_score(data, prediction))指標分數越高，代表聚類效果越好，也就是相同類中的差異性小，不同類之間的差異性大。當然具體聚類的結果含義，我們需要人工來分析，也就是當這些數據被分成不同的類別之后，具體每個類表代表的含義。
另外聚類算法也可以作為其他數據挖掘算法的預處理階段，這樣我們就可以將數據進行降維了。
6. 總結
到這終于寫完了， 我的天啊，每次寫都是這么多，這可以慢慢的干貨啊，雖然多，但真的可以學到東西。?趕緊來總結一下，今天首先從分菜的例子出發，感受了一下EM算法。
然后，我們從拋硬幣的例子，知道了初級EM和升級版EM。然后解釋了EM的工作原理，EM 算法中的 E 步驟就是通過舊的參數來計算隱藏變量。然后在 M 步驟中，通過得到的隱藏變量的結果來重新估計參數。直到參數不再發生變化，得到我們想要的結果。
接下來，就是對比了EM和KMeans的區別，知道了EM可以解決Kmeans不能解決的一些問題，并且EM是個框架，具體實現包括高斯混合模型和隱馬爾可夫模型，后期會具體講隱馬爾可夫。
最后，調用sklearn的EM算法工具完成了一個王者榮耀英雄的聚類任務， 知道了一個衡量聚類結果的函數。
希望通過今天的學習可以對EM算法在感性上有一個了解，至于理性方面， 可以看看西瓜書或者統計學習方法進行深一步的學習了。
參考：
http://note.youdao.com/noteshare?id=2949a4c56e27b97df5fa282dc75060e7&sub=B08633D2250849F2B33A5947351E8389
https://www.cnblogs.com/coshaho/p/9573367.html
https://blog.csdn.net/taka_is_beauty/article/details/88095032
往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習在線手冊深度學習在線手冊AI基礎下載（pdf更新到25集）本站qq群1003271085，加入微信群請回復“加群”獲取一折本站知識星球優惠券，請回復“知識星球”喜歡文章，點個在看
總結
以上是生活随笔為你收集整理的【白话机器学习】算法理论+实战之EM聚类的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【科普】国内外高质量数据科学竞赛平台有哪
- 下一篇： 【数据挖掘】视频版权检测优胜解决方案