em演算法與kmeans

1. EM Algorithm

EM演算法和之前學的都不太一樣，EM演算法更多的是一種思想，所以後面用幾個例子講解，同時也會重點講解GMM高斯混合模型。

極大似然估計這裡面用的比較多。假設我們想要知道我們學生身高的分布，首先先假設這些學生都是符合高斯分布 我們要做的就是要估計這兩個參數到底是多少。學生這么多，挨個挨個來肯定是不切實際的，所以自然就是抽樣了。
為了統計學生身高，我們抽樣200個人組成樣本
我們需要估計的參數 首先估計一下抽到這兩百人的概率一共是多少，抽到男生A的概率 抽到學生B的概率 所以同時抽到這兩個學生的概率就是 那麼同時抽到這200個學生的G概率
最後再取一個對數就好了：

似然函數的執行步驟：
1.得到似然函數
2.取對數整理
3.求導數，另導數為零
4.解方程得到解

首先引出凸函數的概念 那麼就是凸函數，所以它的圖像就是一個勾形的，看起來是一個凹函數，實際上是凸函數。

正常來看先是要引入一個最大似然函數： 但這樣其實是和難求的，P(x|θ)完全混在了一起，根本求不出來，所以我們要引入一個輔助變數z。

所以我們引入隱變數的原因是為了轉化成和這幾個高斯模型相關的式子，否則無從下手。化簡一下上式子： 既然z可以指定x，那麼我們只需要求解出z就好了。
注意上面凸函數所提到的一個期望性質，這里就可以使用了。因為雖然優化了上面的式子，還是不能求出來，因為z變數實在是太抽象了，找不到一個合適的公式來表示它。EM的一個方法就是用優化下界函數的方法來達到優化目標函數的目的。
既然z很抽象，那麼我們就需要一個轉變一下。對於每一個樣例x都會對應一個z，那麼假設一個分布Q(z)是滿足了z的分布的，而Q(z)滿足的條件是 Qi意味著每一個x對應的z都會對應著一個Q了，這里有點復雜，再詳細解釋一下。一個x對應一組z，z是一個向量，但是每一個z又會分別對應一個一個分布Q。以為最後得到的z不會是一個數字，而是一個概率，也就是說Q(z)得到的是這個x樣例屬於這個類別的概率是多少。而z的數量，一個是當前有多少個分布混合在一起的數量。
再梳理一下：現在的樣本是xi，那麼每一個xi將會對應著一組的z，每一個xi同時也會對應著一個分布Qi，z其實就是反應了這個樣本是來自於哪個分布的。比如這個x是A1分布做了3，A2分布做了5，那麼z可能就是={3,5}。所以Qi(z)得到的是這個x屬於這些個分布的概率，也就是說這些分布對x做了多少百分比的功，自然就是要等於1了。
還要注意的是，上面的 這個並不能得到Qi(z)就是分布對x做了多少功的結論，得到這個結論是後面下界函數與目標函數相等得到的。這里只是知道了總和等於1，因為是分布的總和嘛。
現在就到了公式的化簡：
仔細看一下這個式子 這個式子其實就是求 的期望，假設 ，那麼可以利用上面 。於是化簡：
這個時候就得到了下界函數，上面也講過了，想要相等，自然就是x要是常數，所以 既然 ，而且z也是一樣的，因為一個樣本嘛。所以上下加和（如果是離散的，那就sum一下，連續的那就積分，這里是離散的，所以就是sum一下）。於是有
於是有：

這就是整一個EM演算法的框架了，可以看到其實沒有比較具體的演算法，大致上就是一個框架。那麼問題來了，怎麼樣證明這東西是一個收斂的？？

可以直接把高斯混合模型代入EM框架裡面。
存在多個高斯分布混合生成了一堆數據X，取各個高斯分布的概率是 ，第i個高斯分布的均值是 ，方差是 ，求法φ，μ，σ。
按照套路，第一個E-step求出Q，於是有：
意思就是求出第i個樣本屬於第j個分布的概率是多少。之後就是M-step了，就是化簡了：

這里可能需要解釋一下，根據 至於條件，因為很明顯，z是隱變數，只是指明了x是屬於哪個類別，和μ，Σ沒有什麼關系，所以直接忽略那兩個參數了，所以P(z)是沒有那兩個參數的，z是代表了分布，所以每一個分布的概率肯定是包括了，所以就只有一個概率的參數。P(x|z)是本身的概率，就是已經知道分布是那個了，求屬於這個分布的概率是多少，既然已經選定了分布那麼自然就不需要再看φ了，因為φ是各個分布的概率。

現在有兩個硬幣AB，進行5次試驗每一次投10次，並不知道是哪個硬幣投的，求兩種硬幣的正面的概率。
首先E-step：
首先先初始化一下，
第一個試驗選中A的概率：
同樣求得
計算機出每一個試驗的概率然後相加求均值。
之後就是M-step了：

方差的求解就不玩了，主要就是迭代求解μ和φ的值了。
首先是生成數據，4個高斯分布，每一個高斯分布的sigma都是一樣的，不一樣的只有μ和α，也就是φ，習慣上把前面的一個參數叫做權值，所以用α來表示。

這四個模型的比例分別是1:2:3:4，使用EM來找到他們屬於的類別。

其實如果用kmeans聚類的話更加快速，但是這里還是用EM。
E-step：

就是按照公式來求解w即可，求解每一個分布對樣本點做了多少的功，之後求單個樣本點求比例。
M-step：

直接按照公式優化即可。

運行函數。看看結果：

結果其實還是相差不大。達到預期。

上面所講的其實只是一種理解方法，在李航老師的統計學習方法裡面是另一種比較厲害的解法：
1.E-step：求出Q函數。
2.M-step：利用Q函數求極大值。
其實這兩種方法是完全一樣的，Q函數就是下界函數，

EM和Kmeans演算法其實很類似，事實上步驟基本可以用EM框架來替換，但是Kmeans演算法是硬分類，說一不二，但是EM演算法不太一樣，是軟分類，百分之幾是那個，百分之幾是這個。

缺點也還是有的：初值敏感，局部最優。因為存在了隱變數，所以導致了直接對x做極大似然是不可行的，log已經在sum的外面了。所以EM演算法就轉向了下界函數，而這種方法本來就不保證找到局部最優解。

如果將樣本看作觀察值，潛在類別看作是隱藏變數，那麼聚類問題也就是參數估計問題。如果一個目標函數存在多個變數，那麼梯度下降牛頓法這些逼近方法就用不了了。但我們可以使用坐標上升方法，固定一個變數，對另外一個求導數，然後替換最後逐步逼近極值點。對應到EM演算法也是一樣，E步求隱含的z變數，Mstep求解其他參數。

2. kmeans演算法原理

kmeans演算法原理如下：

K-means演算法是一種典型的基於劃分的聚類演算法該演算法具有運算速度快，執行過程簡單的優點，在很多大數據處理領域得到了廣泛的應用。

利用相似性度量方法來衡量數據集中所有數據之間的關系,將關系比較密切的數據劃分到一個集合中。K-means演算法首先需要選擇K個初始化聚類中，計算每個數據對象到K個初始化聚類中心的距離。

2、缺點：需要人工預先確定初始K值，該值與實際的類另數可能不吻合。tK均值只能收斂到局部最優。因為求解這個代價函數是個NP問題，採用的是貪心策略，所以只能通過多次迭代收斂到局部最優，而不是全局最優。

K<均值的效果受初始值和離群點的影響大。因為k均值本質上是基於距離度量來劃分的，均值和差大的維度將對數據的聚類結帆山塌果產生決定性的影響，因此需要進行歸-化處理:此外，離群點或雜訊對均值會產生影響，導致中心偏移,因此需要進行預處理。

3. EM演算法怎麼用在聚類上

k-means -> probabilistic model mixtures -> infinite probabilistic model mixtures(DP) 或者 infinite k-means

1. EM為含隱變數的概率模型提供了一個通用的框架。

2. 而用於聚類的模型其實都是離散混合模型。有限混合或者無限混合（狄利克雷過程），離散混合模型一定是含有隱變數的。所以EM就可以用來求解了。你先選一個聚類模型。你的任務簡單，就沒得選GMM或者DPGMM。若任務復雜些，可以搞分層的，或者時序的。然後用EM求解即可，求解過程中還會用到采樣或者變分，自己看想用哪個。

   
   

4. EM演算法詳解

作為N大機器學習方法的一員，EM演算法在各種書籍、博客、網上視頻上被描述或者介紹，每次看完總感覺很多地方含糊不清，不能讓一個初學者（有一定統計概率基礎）接受。最近再B站上，看到 徐亦達老師的課程 ，EM演算法這塊講解易於理解和接受，再結合PRML一書的關於混合模型和EM章節內容，對整個EM演算法從具體的原理上面有了更深入的理解。
在下文中，更多的是通過公式推導和一些文字說明來梳理EM演算法，盡量做到大家一看就明白。

極大似然估計是概率統計中，估計模型參數的一種方法，如果對似然概念以及極大似然估計的概念不理解，可參考維基網路 https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E4%BC%BC%E7%84%B6%E4%BC%B0%E8%AE%A1

這里，我們給出一個一維高斯函數的例子。如圖1所示，一維空間裡面離散分布的樣本點其分布特點可以看成是一種高斯分布。那這些樣本的高斯分布函數參數怎麼求解呢？可以通過極大似然估計獲得。

假設我們獲取圖1中數據樣本集合為 ，其分布函數假設為一維高斯分布，即：

那所有數據的聯合概率,即似然函數為：

對等式兩邊求log，即log-likelihood：

分別對參數求導：

可以得到：

通過上述方法，就可以得到基於樣本數據和假設分布函數模型情況下，得到樣本數據的分布函數。

從圖2所示中，如果樣本數據分布式藍色點和橙色點的集合，如果依然用高斯分布去進行最大似然估計，得到的分布模型自然是不合適的。很顯然，樣本數據分布存在兩個密集區（藍色點和橙色點），如果能通過一種方法，確認樣本數據裡面的藍色點和橙色點，然後分別對藍色點集合進行一個高斯估計，對橙色點集進行另外一個高斯估計，兩個高斯混合到一起，是不是比單個高斯能更好的匹配樣本數據的分布情況。這種情況下的分布函數就是高斯混合模型。

這里我們先直接給出高斯混合模型的分布函數(多維)：

在圖2例子中，提到如果給每一個數據樣本能夠先進行分類，即確定屬於哪一個集中的簇中，就能比較容易的進行混合模型的求解。這說明了什麼呢？我們可以理解，原始樣本數據是不完全的（incomplete），引入一個K維的二值隨機變數 ，這個變數採用"1-of-K"的表示方法，即K維中，只有一維是1，其餘所有元素等於0。那麼每一個樣本數據，即有數據特徵 ，再匹配一個分配變數 ，就可以將圖2過程完整描述，即我們認為 和 聯合在一起才是完全的（complete）。

數學表示上，我們利用邊緣概率分布 和條件概率分布 定義聯合概率分布 .
的邊緣概率分布根據混合系數 進行賦值，即 ,使得邊緣概率分布是合法，那麼：

類似的，在給定 的一個特定的值，即針對某一簇的情況， 的條件概率分布是一個高斯分布，即

那麼根據貝葉斯公式得到高斯混合模型：

由於我們只能觀察樣本數據 ,無法直接獲取每個數據的分配變數 ,可理解 為潛在變數（latent）
依據極大似然函數的求解方法，我們可以對高斯混合模型寫出數據的對數似然函數：

由於對數函數內部出現求和，這種情況是沒有辦法通過求導等於0的方式獲取估計參數的解析解的。這種情況下，就需要用到EM演算法，通過迭代方式獲取估計參數。下面我們先從一般性問題上進行EM演算法的理論描述，然後再利用EM演算法推導高斯混合模型的計算方法。

EM演算法叫做期望最大化方法，首先我們給出EM演算法一般性結論或者說步驟，其具體分為兩步，即E-step和M-step。

EM演算法的步驟，通過高斯混合模型可以直觀理解記憶。 是什麼意思呢，其含義是在給定數據樣本的情況下，潛在變數的概率情況。也就是說在高斯混合模型中，給定樣本數據，我們推測樣本屬於哪一個高斯簇的概率情況。在確定分配情況後，每一個簇都用高斯進行估計，衡量估計好還是不好，用期望形式表示。這樣可以幫助理解和記憶Q的定義。那EM演算法怎麼證明其收斂性呢？

我們要保證：

這樣每次迭代可以使得似然函數隨著參數變大，一直到似然函數不再增大或滿足其他終止條件止。

那怎麼保證呢？首先，利用貝葉斯公式有：

兩邊同時取log

然後兩邊同時用 求期望，可以得：

等式左邊 和 沒有關系， 是概率密度函數，積分是1，所以等式左邊依然是 .
等式右邊第一項就是E-step裡面的Q函數，第二項我們記做H函數，則：

要保證 ，首先 ，那麼是不是保證 滿足，就一定有 ？答案是肯定的。（說明一下，這裡面的H和Q函數都是關於 的函數，每一次迭代 是已知的，他不是變數）

那下面只要證明 就可以了。

因此可以得到 ，則整個EM演算法的收斂性證畢。

註：這里用到了Jessian不等式，如果函數是convex的，則有函數的期望大於期望的函數，即 .

上述EM演算法的證明，有一些技巧性，而這些技巧性有沒有一種是在已知結論基礎上硬湊的感覺呢，尤其是用 去求期望，就是為了去構造Q函數。那有沒有更好的解釋或者更為直觀的方式來得到相同的結論呢？答案是有的。

首先，仍然用到：

我們稍微變個型，假設一個概率密度函數 :

兩邊同時用 求期望：

其中等式右邊第一項，我們記做 ，可以稱為ELOB，EvidenceLowerBound，第二項是 和 的KL散度。

如圖4所示，當我固定參數 時候，ELOB就是關於 的泛函（只聽過沒學過，可理解為函數的函數），那ELOB的上界是什麼呢？那首先要理解KL散度，KL散度是衡量兩個概率分布之間的差異性，如果兩個分布沒有差異，則KL散度等於0，如果有差異則大於0，所以KL散度的最小值就是0，那ELOB的上界就是此刻的似然函數。

在EM演算法中，當前迭代時，參數 ，則對於E-step，我們需要使得ELOB最大，即KL散度為0，如圖5所示，其中 為 。此時，

對於M-Step，我們是需要得到新的估計參數，這個時候，固定 ,重新獲得ELOB的最大值，這個時候的ELOB是什麼樣的呢？

右邊第二項沒有參數 ，所以固定 最大化ELOB，就等於最大化第一項，而第一項是什麼呢？就是 函數。

如圖6所示，我們最大化 函數，也就是最大化此次迭代的ELOB。在新的參數下， ，此刻 不變，所以和新的 在沒有達到局部（或者全局）極大值的情況下，是兩個不同的概率分布，即二者KL散度是大於0的，那此刻的似然函數等於此刻的KL散度加上此刻的ELOB，自然是有 。

從ELOB和KL散度的層面可以更好的理解EM演算法的迭代過程。

PRML一書中，有圖7所示的示意圖，能比較形象的說明，EM演算法的迭代過程。

圖7中，紅色曲線表示(不完整數據)對數似然函數，它的最大值是我們想要得到的。我們首先選擇某個初始的參數值 ,然後在第一個E步驟中,我們計算潛在變數上的後驗概率分布,得到了 的一個更小的下界，它的值等於在 處的對數似然函數值，用藍色曲線表示。注意，下界與對數似然函數在 處以切線的方式連接，因此兩條曲線的梯度相同。這個界是一個凹函數，對於指數族分布的混合分布來說，有唯一的最大值。在M步驟中,下界被最大化，得到了新的值 ,這個值給出了比 處更大的對數似然函數值。接下來的E步驟構建了一個新的下界,它在 處與對數似然函數切線連接,用綠色曲線表示。以這樣的方式不停迭代，直到滿足條件。

了解了EM演算法，我們來詳細推導高斯混合模型的E步和M步的內容。這一部分內容來自徐亦達老師的課件。由於公式太多了，我就放一些截圖，供大家一起學習和參考。

徐亦達老師的課件在： https://github.com/roboticcam/machine-learning-notes/blob/master/em.pdf

後續關於EM演算法的應用會舉例以下幾方面內容
(1)Kmeans和高斯混合模型
(2)EM演算法應用之貝葉斯線性回歸
(3)EM演算法應用之PLSA
(4)EM演算法應用之缺失數據參數估計問題

5. Kmeans聚類演算法簡介

由於具有出色的速度和良好的可擴展性，Kmeans聚類演算法算得上是最著名的聚類方法。Kmeans演算法是一個重復移動類中心點的過程，把類的中心點，也稱重心(centroids)，移動到其包含成員的平均位置，然後重新劃分其內部成員。k是演算法計算出的超參數，表示類的數量；Kmeans可以自動分配樣本到不同的類，但是不能決定究竟要分幾個類。k必須是一個比訓練集樣本數小的正整數。有時，類的數量是由問題內容指定的。例如，一個鞋廠有三種新款式，它想知道每種新款式都有哪些潛在客戶，於是它調研客戶，然後從數據里找出三類。也有一些問題沒有指定聚類的數量，最優的聚類數量是不確定的。後面我將會詳細介紹一些方法來估計最優聚類數量。

Kmeans的參數是類的重心位置和其內部觀測值的位置。與廣義線性模型和決策樹類似，Kmeans參數的最優解也是以成本函數最小化為目標。Kmeans成本函數公式如下：

μiμi是第kk個類的重心位置。成本函數是各個類畸變程度(distortions)之和。每個類的畸變程度等於該類重心與其內部成員位置距離的平方和。若類內部的成員彼此間越緊湊則類的畸變程度越小，反之，若類內部的成員彼此間越分散則類的畸變程度越大。求解成本函數最小化的參數就是一個重復配置每個類包含的觀測值，並不斷移動類重心的過程。首先，類的重心是隨機確定的位置。實際上，重心位置等於隨機選擇的觀測值的位置。每次迭代的時候，Kmeans會把觀測值分配到離它們最近的類，然後把重心移動到該類全部成員位置的平均值那裡。

2.1 根據問題內容確定

這種方法就不多講了，文章開篇就舉了一個例子。

2.2 肘部法則

如果問題中沒有指定kk的值，可以通過肘部法則這一技術來估計聚類數量。肘部法則會把不同kk值的成本函數值畫出來。隨著kk值的增大，平均畸變程度會減小；每個類包含的樣本數會減少，於是樣本離其重心會更近。但是，隨著kk值繼續增大，平均畸變程度的改善效果會不斷減低。kk值增大過程中，畸變程度的改善效果下降幅度最大的位置對應的kk值就是肘部。為了讓讀者看的更加明白，下面讓我們通過一張圖用肘部法則來確定最佳的kk值。下圖數據明顯可分成兩類：

從圖中可以看出，k值從1到2時，平均畸變程度變化最大。超過2以後，平均畸變程度變化顯著降低。因此最佳的k是2。

2.3 與層次聚類結合

經常會產生較好的聚類結果的一個有趣策略是，首先採用層次凝聚演算法決定結果粗的數目，並找到一個初始聚類，然後用迭代重定位來改進該聚類。

2.4 穩定性方法

穩定性方法對一個數據集進行2次重采樣產生2個數據子集，再用相同的聚類演算法對2個數據子集進行聚類，產生2個具有kk個聚類的聚類結果，計算2個聚類結果的相似度的分布情況。2個聚類結果具有高的相似度說明kk個聚類反映了穩定的聚類結構，其相似度可以用來估計聚類個數。採用次方法試探多個kk，找到合適的k值。

2.5 系統演化方法

系統演化方法將一個數據集視為偽熱力學系統，當數據集被劃分為kk個聚類時稱系統處於狀態kk。系統由初始狀態k=1k=1出發，經過分裂過程和合並過程，系統將演化到它的穩定平衡狀態 kiki ，其所對應的聚類結構決定了最優類數 kiki 。系統演化方法能提供關於所有聚類之間的相對邊界距離或可分程度，它適用於明顯分離的聚類結構和輕微重疊的聚類結構。

2.6 使用canopy演算法進行初始劃分

基於Canopy Method的聚類演算法將聚類過程分為兩個階段

(1) 聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在一個子集中，這個子集被叫做Canopy，通過一系列計算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬於任何Canopy的情況，可以把這一階段看做數據預處理；

(2) 在各個Canopy內使用傳統的聚類方法(如Kmeans)，不屬於同一Canopy的對象之間不進行相似性計算。

從這個方法起碼可以看出兩點好處：首先，Canopy不要太大且Canopy之間重疊的不要太多的話會大大減少後續需要計算相似性的對象的個數；其次，類似於Kmeans這樣的聚類方法是需要人為指出K的值的，通過(1)得到的Canopy個數完全可以作為這個k值，一定程度上減少了選擇k的盲目性。

其他方法如貝葉斯信息准則方法(BIC)可參看文獻[4]。

選擇適當的初始質心是基本kmeans演算法的關鍵步驟。常見的方法是隨機的選取初始中心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用技術是：多次運行，每次使用一組不同的隨機初始質心，然後選取具有最小SSE(誤差的平方和)的簇集。這種策略簡單，但是效果可能不好，這取決於數據集和尋找的簇的個數。

第二種有效的方法是，取一個樣本，並使用層次聚類技術對它聚類。從層次聚類中提取kk個簇，並用這些簇的質心作為初始質心。該方法通常很有效，但僅對下列情況有效：(1)樣本相對較小，例如數百到數千(層次聚類開銷較大)；(2) kk相對於樣本大小較小。

第三種選擇初始質心的方法，隨機地選擇第一個點，或取所有點的質心作為第一個點。然後，對於每個後繼初始質心，選擇離已經選取過的初始質心最遠的點。使用這種方法，確保了選擇的初始質心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用於點樣本。由於離群點很少(多了就不是離群點了)，它們多半不會在隨機樣本中出現。計算量也大幅減少。

第四種方法就是上面提到的canopy演算法。

常用的距離度量方法包括：歐幾里得距離和餘弦相似度。兩者都是評定個體間差異的大小的。

歐氏距離是最常見的距離度量，而餘弦相似度則是最常見的相似度度量，很多的距離度量和相似度度量都是基於這兩者的變形和衍生，所以下面重點比較下兩者在衡量個體差異時實現方式和應用環境上的區別。

藉助三維坐標系來看下歐氏距離和餘弦相似度的區別：

從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標(即個體特徵維度的數值)直接相關；而餘弦相似度衡量的是空間向量的夾角，更加的是體現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標軸原點，那麼這個時候餘弦相似cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦相似度的不同之處。

根據歐氏距離和餘弦相似度各自的計算方式和衡量特徵，分別適用於不同的數據分析模型：歐氏距離能夠體現個體數值特徵的絕對差異，所以更多的用於需要從維度的數值大小中體現差異的分析，如使用用戶行為指標分析用戶價值的相似度或差異；而餘弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用於使用用戶對內容評分來區分用戶興趣的相似度和差異，同時修正了用戶間可能存在的度量標准不統一的問題(因為餘弦相似度對絕對數值不敏感)。

因為歐幾里得距離度量會受指標不同單位刻度的影響，所以一般需要先進行標准化，同時距離越大，個體間差異越大；空間向量餘弦夾角的相似度度量不會受指標刻度的影響，餘弦值落於區間[-1,1]，值越大，差異越小。但是針對具體應用，什麼情況下使用歐氏距離，什麼情況下使用餘弦相似度？

從幾何意義上來說，n維向量空間的一條線段作為底邊和原點組成的三角形，其頂角大小是不確定的。也就是說對於兩條空間向量，即使兩點距離一定，他們的夾角餘弦值也可以隨意變化。感性的認識，當兩用戶評分趨勢一致時，但是評分值差距很大，餘弦相似度傾向給出更優解。舉個極端的例子，兩用戶只對兩件商品評分，向量分別為(3,3)和(5,5)，這兩位用戶的認知其實是一樣的，但是歐式距離給出的解顯然沒有餘弦值合理。

我們把機器學習定義為對系統的設計和學習，通過對經驗數據的學習，將任務效果的不斷改善作為一個度量標准。Kmeans是一種非監督學習，沒有標簽和其他信息來比較聚類結果。但是，我們還是有一些指標可以評估演算法的性能。我們已經介紹過類的畸變程度的度量方法。本節為將介紹另一種聚類演算法效果評估方法稱為輪廓系數(Silhouette Coefficient)。輪廓系數是類的密集與分散程度的評價指標。它會隨著類的規模增大而增大。彼此相距很遠，本身很密集的類，其輪廓系數較大，彼此集中，本身很大的類，其輪廓系數較小。輪廓系數是通過所有樣本計算出來的，計算每個樣本分數的均值，計算公式如下：

aa是每一個類中樣本彼此距離的均值，bb是一個類中樣本與其最近的那個類的所有樣本的距離的均值。

輸入：聚類個數k，數據集XmxnXmxn。

輸出：滿足方差最小標準的k個聚類。

(1) 選擇k個初始中心點，例如c[0]=X[0] , … , c[k-1]=X[k-1]；

(2) 對於X[0]….X[n]，分別與c[0]…c[k-1]比較，假定與c[i]差值最少，就標記為i；

(3) 對於所有標記為i點，重新計算c[i]={ 所有標記為i的樣本的每個特徵的均值}；

(4) 重復(2)(3)，直到所有c[i]值的變化小於給定閾值或者達到最大迭代次數。

Kmeans的時間復雜度：O(tkmn)，空間復雜度：O((m+k)n)。其中，t為迭代次數，k為簇的數目，m為樣本數，n為特徵數。

7.1 優點

(1). 演算法原理簡單。需要調節的超參數就是一個k。

(2). 由具有出色的速度和良好的可擴展性。

7.2 缺點

(1). 在 Kmeans 演算法中 kk 需要事先確定，這個 kk 值的選定有時候是比較難確定。

(2). 在 Kmeans 演算法中，首先需要初始k個聚類中心，然後以此來確定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果。多設置一些不同的初值，對比最後的運算結果，一直到結果趨於穩定結束。

(3). 該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，因此當數據量非常大時，演算法的時間開銷是非常大的。

(4). 對離群點很敏感。

(5). 從數據表示角度來說，在 Kmeans 中,我們用單個點來對 cluster 進行建模，這實際上是一種最簡化的數據建模形式。這種用點來對 cluster 進行建模實際上就已經假設了各 cluster的數據是呈圓形(或者高維球形)或者方形等分布的。不能發現非凸形狀的簇。但在實際生活中，很少能有這種情況。所以在 GMM 中，使用了一種更加一般的數據表示，也就是高斯分布。

(6). 從數據先驗的角度來說，在 Kmeans 中,我們假設各個 cluster 的先驗概率是一樣的,但是各個 cluster 的數據量可能是不均勻的。舉個例子,cluster A 中包含了10000個樣本,cluster B 中只包含了100個。那麼對於一個新的樣本,在不考慮其與A cluster、 B cluster 相似度的情況,其屬於 cluster A 的概率肯定是要大於 cluster B的。

(7). 在 Kmeans 中，通常採用歐氏距離來衡量樣本與各個 cluster 的相似度。這種距離實際上假設了數據的各個維度對於相似度的衡量作用是一樣的。但在 GMM 中，相似度的衡量使用的是後驗概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通過引入協方差矩陣,我們就可以對各維度數據的不同重要性進行建模。

(8). 在 Kmeans 中，各個樣本點只屬於與其相似度最高的那個 cluster ，這實際上是一種 hard clustering 。

針對Kmeans演算法的缺點，很多前輩提出了一些改進的演算法。例如 K-modes 演算法，實現對離散數據的快速聚類，保留了Kmeans演算法的效率同時將Kmeans的應用范圍擴大到離散數據。還有K-Prototype演算法，可以對離散與數值屬性兩種混合的數據進行聚類，在K-prototype中定義了一個對數值與離散屬性都計算的相異性度量標准。當然還有其它的一些演算法，這里我 就不一一列舉了。

Kmeans 與 GMM 更像是一種 top-down 的思想，它們首先要解決的問題是，確定 cluster 數量，也就是 k 的取值。在確定了 k 後,再來進行數據的聚類。而 hierarchical clustering 則是一種 bottom-up 的形式，先有數據，然後通過不斷選取最相似的數據進行聚類。

6. 如何正確選擇聚類演算法

作者 | Josh Thompson

來源 | 數據派THU

Choosing the Right Clustering Algorithm for your Dataset - KDnuggets

聚類演算法十分容易上手，但是選擇恰當的聚類演算法並不是一件容易的事。

數據聚類是搭建一個正確數據模型的重要步驟。數據分析應當根據數據的共同點整理信息。然而主要問題是，什麼通用性參數可以給出最佳結果，以及什麼才能稱為「最佳」。

本文適用於菜鳥數據科學家或想提升聚類演算法能力的專家。下文包括最廣泛使用的聚類演算法及其概況。根據每種方法的特殊性，本文針對其應用提出了建議。

四種基本演算法以及如何選擇

聚類模型可以分為四種常見的演算法類別。盡管零零散散的聚類演算法不少於100種，但是其中大部分的流行程度以及應用領域相對有限。

基於整個數據集對象間距離計算的聚類方法，稱為基於連通性的聚類（connectivity-based）或層次聚類。根據演算法的「方向」，它可以組合或反過來分解信息——聚集和分解的名稱正是源於這種方向的區別。最流行和合理的類型是聚集型，你可以從輸入所有數據開始，然後將這些數據點組合成越來越大的簇，直到達到極限。

層次聚類的一個典型案例是植物的分類。數據集的「樹」從具體物種開始，以一些植物王國結束，每個植物王國都由更小的簇組成（門、類、階等）。

層次聚類演算法將返回樹狀圖數據，該樹狀圖展示了信息的結構，而不是集群上的具體分類。這樣的特點既有好處，也有一些問題：演算法會變得很復雜，且不適用於幾乎沒有層次的數據集。這種演算法的性能也較差：由於存在大量的迭代，因此整個處理過程浪費了很多不必要的時間。最重要的是，這種分層演算法並不能得到精確的結構。

同時，從預設的類別一直分解到所有的數據點，類別的個數不會對最終結果產生實質性影響，也不會影響預設的距離度量，該距離度量粗略測量和近似估計得到的。

根據我的經驗，由於簡單易操作，基於質心的聚類（Centroid-based）是最常出現的模型。 該模型旨在將數據集的每個對象劃分為特定的類別。 簇數（k）是隨機選擇的，這可能是該方法的最大問題。 由於與k最近鄰居（kNN）相似，該k均值演算法在機器學習中特別受歡迎。

計算過程包括多個步驟。首先，輸入數據集的目標類別數。聚類的中心應當盡可能分散，這有助於提高結果的准確性。

其次，該演算法找到數據集的每個對象與每個聚類中心之間的距離。最小坐標距離（若使用圖形表示）確定了將對象移動到哪個群集。

之後，將根據類別中所有點的坐標平均值重新計算聚類的中心。重復演算法的上一步，但是計算中要使用簇的新中心點。除非達到某些條件，否則此類迭代將繼續。例如，當簇的中心距上次迭代沒有移動或移動不明顯時，聚類將結束。

盡管數學和代碼都很簡單，但k均值仍有一些缺點，因此我們無法在所有情景中使用它。缺點包括：

因為優先順序設置在集群的中心，而不是邊界，所以每個集群的邊界容易被疏忽。 無法創建數據集結構，其對象可以按等量的方式分類到多個群集中。 需要猜測最佳類別數（k），或者需要進行初步計算以指定此量規。

相比之下，期望最大化演算法可以避免那些復雜情況，同時提供更高的准確性。簡而言之，它計算每個數據集點與我們指定的所有聚類的關聯概率。用於該聚類模型的主要工具是高斯混合模型（GMM）–假設數據集的點服從高斯分布。

k-means演算法可以算是EM原理的簡化版本。它們都需要手動輸入簇數，這是此類方法要面對的主要問題。除此之外，計算原理（對於GMM或k均值）很簡單：簇的近似范圍是在每次新迭代中逐漸更新的。

與基於質心的模型不同，EM演算法允許對兩個或多個聚類的點進行分類-它僅展示每個事件的可能性，你可以使用該事件進行進一步的分析。更重要的是，每個聚類的邊界組成了不同度量的橢球體。這與k均值聚類不同，k均值聚類方法用圓形表示。但是，該演算法對於不服從高斯分布的數據集根本不起作用。這也是該方法的主要缺點：它更適用於理論問題，而不是實際的測量或觀察。

最後，基於數據密度的聚類成為數據科學家心中的最愛。

這個名字已經包括了模型的要點——將數據集劃分為聚類，計數器會輸入ε參數，即「鄰居」距離。因此，如果目標點位於半徑為ε的圓（球）內，則它屬於該集群。

具有雜訊的基於密度的聚類方法（DBSCAN）將逐步檢查每個對象，將其狀態更改為「已查看」，將其劃分到具體的類別或雜訊中，直到最終處理整個數據集。用DBSCAN確定的簇可以具有任意形狀，因此非常精確。此外，該演算法無需人為地設定簇數 —— 演算法可以自動決定。

盡管如此，DBSCAN也有一些缺點。如果數據集由可變密度簇組成，則該方法的結果較差；如果對象的位置太近，並且無法輕易估算出ε參數，那麼這也不是一個很好的選擇。

總而言之，我們並不能說選擇了錯誤的演算法，只能說其中有些演算法會更適合特定的數據集結構。為了採用最佳的（看起來更恰當的）演算法，你需要全面了解它們的優缺點。

例如，如果某些演算法不符合數據集規范，則可以從一開始就將其排除在外。為避免繁瑣的工作，你可以花一些時間來記住這些信息，而無需反復試驗並從自己的錯誤中學習。

我們希望本文能幫助你在初始階段選擇最好的演算法。繼續這了不起的工作吧！

7. EM演算法及其應用GMM/pLSA/LDA

從樣本觀察數據（顯性特徵x）中，找出樣本的模型參數（ ）。 最常用的方法就是極大化模型分布的對數似然函數。

是樣本特徵和label的聯合分布， ，為了使得估計的結果泛化能力更好，我們將 分解為 ， 就是隱變數。

這類問題有：

以上問題，主要是通過引入隱變數，把樣本表述為隱變數的分布，從而簡化每個樣本點表述。對於此問題通用的數學描述為：

給定一個樣本集 ，我們假設觀察到的 還對應著隱含變數的概率分布 ，記 。則該模型 的對數似然函數為：

而 根據具體的問題來定義。

目標是求得參數 ，使得對數似然函數最大：

這時候，交叉熵為：

優化目標為：

它的梯度是

都是概率分布，即大於0且滿足：

直接梯度下降是行不通的，這就需要藉助EM演算法。

對於最大似然函數的參數求解：

是隱變數，觀測不到，為了求解上式，假設我們知道 的概率分布 ：

根據 Jensen 不等式 [1]，對於任意分布 都有：

且上面的不等式在 為常數時取等號。

（備註：關鍵的點就是Jensen不等式在x為常數時取等號（x的所有值重疊，等於1個值）。這里正好對應隱變數的分布的確定，即E步求解的隱變數的分布）

於是我們就得到了 的一個下界函數。我們要想套用上面的演算法，還要讓這個不等式在 處取等號，這就這要求在 時 為常數，即 。由於 是一個概率分布，必須滿足 ，所以這樣的 只能是 。那我們就把 代入上式，得到：

最大化這個下界函數：

其中倒數第二步是因為 這一項與 無關，所以就直接扔掉了。這樣就得到了本文第二節 EM 演算法中的形式——它就是這么來的。

以上就是 EM 了。至於獨立同分布的情況推導也類似。

[1]
Jensen 不等式：

對於凸函數 ，其函數的期望大於等於期望的函數

若 是嚴格凸的，則上式取等號當前僅當 為常數。

在這里 函數是嚴格 凹 的，所以要把上面的不等號方向

假設某個數據分布是由K個高斯分布加權疊加而來：

目標是，求出這K個高斯分布及其權重。

換一種說法，也就是，用K個高斯分布的加權和來擬合數據分布

相比於K-means，只是把原本樣本一定屬於某一類改成了一個樣本屬於某類的概率。K-means的結果是把每個數據點assign到其中某一個cluster,而GMM則是給出每個數據點被assign到每一個cluster的概率，又稱作soft assignment。

pLSA 模型有兩個 基本的設定：

即：

而我們感興趣的正是其中的 和 ，即文章的主題分布，和主題的詞分布。記 ， 表示我們希望估計的模型參數（模型中共有 個參數）。

根據最大log似然估計法，我們要求的就是

這里由於 這一項與 無關，在 中可以被直接扔掉。 [1]

因此

這里出現了 套 的形式，導致很難直接拿它做最大似然。但假如能觀察到 ，問題就很簡單了。於是我們想到根據 EM 演算法 ，可以用下式迭代逼近 ：

其中

在 E-step 中，我們需要求出 中除 外的其它未知量，也就是說對於每組 我們都需要求出 。 根據貝葉斯定理貝葉斯定理，我們知道：

而 和 就是上輪迭代求出的 。這樣就完成了 E-step。

接下來 M-step 就是要求 了。利用基本的微積分工具 [2]，可以分別對每對 和 求出：

以上就是 pLSA 演算法了。

EM求解方法：

E-step:

M-step:

在pLSA中用極大似然估計的思想去推斷參數（文檔的主題分布和主題的詞分布），而LDA把這兩參數視為概率分布，其先驗信息為dirichlet分布。因此，在數據量不大的時候，LDA能緩解過擬合問題，而在數據量很大的時候，pLSA是比較好的選擇。

LDA中，估計Φ、Θ這兩未知參數可以用變分(Variational inference)-EM演算法，也可以用gibbs采樣，前者的思想是最大後驗估計MAP，後者的思想是貝葉斯估計。

https://spaces.ac.cn/archives/4277

EM演算法原理總結

Probabilistic latent semantic analysis (pLSA)

A Note on EM Algorithm and PLSA --- Xinyan Lu

李航-統計機器學習第一版

高斯混合模型

github
推薦我的開源項目 exFM c++ deepFM