K-means 和 EM 比較

k-means 其實是 EM 算法的特例, 分别舉 "人的氣質類型" 和 理論角度 來總結

回顧

前幾篇對 k-means 有過了解和寫了一版僞代碼, 因為思想比較非常樸素, 就是初始化幾個中心點, 然後通過計算距離的方式, "物以類聚", 不斷疊代中心點, 最後收斂, (中心點不變化) 就搞定了, 代碼也容易實作, 算法也基本不涉及數學, 感覺就是通用的全民入門算法. 跟 KNN 這種hello world 級别是一個等級, 簡單易懂, 實用性高, 易實作.

而相對 EM 算法則有些難明白一些, 它涉及幾個核心概念: 隐變量, 參數估計, 先驗分布, 貝葉斯. 它所要解決的問題, 其實就是,當無法直接觀測到總體參數時, 但有知道它是由其他隐含因子影響着的, 再此之下, 如何進行參數估計, 其實也就是咱當年學統計學中, 用樣本來估計總體, 方法無非是,極大似然法, 全機率與貝葉斯, 高斯分布 這些基礎知識而已.

為了說明EM算法, 顯示以扔硬币 的小案例來直覺認識 EM 算法的 E, M 步驟分别是做了什麼事情, 從比較直覺來看, 然後有引入高斯混合模型 來深刻推導了一波EM算法, 同時證明了EM算法的收斂性. 推導的難點在于, **如何去定義 **

E, M步驟, 然後技巧上是用了Jensen不等式, 并引入了 concave函數的特性(全局最優解), 過程其實就用到了高斯分布, 化簡用的是全機率 與貝葉斯的關系, 也就是全機率, 聯合分布, 條件機率..這些基礎知識, 嗯. 總體來說還是不難的, 可能寫代碼實作有點小複雜, 後面試着整一整, 這裡主要重點整透理論, 代碼會copy 就差不多行了.

K-means 與 EM

其實, 不難發現, 高斯混合模型(Mixture of Gaussian) EM 算法與 K-means 是相似的. K-means 從 EM 視角來看,

• Expectation : 每一個點指派(機率為1)一個 cluster
• Maximization:更新每一個 cluster 的中心

由此可得到:K-means 算法其實是EM算法的一種特殊情況.

K-means 選擇将一個資料點歸為一個 cluster (機率100%, hard decision); 而 EM 算法選擇将一個資料點看作是多個cluster (或分布) 的混合物(soft decision).

case: 人的氣質類型

(補一下性格的本質: 是習慣, 習慣決定性格, 性格決定命運, 是有科學性滴)

記得以前學心理學的時候, 談到氣質類型的章節, 一種經典的體液分法(5世紀前), 認為人體有四種液體, 不同的體液比例混合形成了四種典型氣質類型:

• 多血質: 活潑, 敏感, 好動, 反應快, 喜歡交往...., 典型人物: 王熙鳳, 姚明, 科比, 詹姆斯
• 膽汁質: 直率, 熱情, 沖動, 情緒化... 典型人物: 張飛, 魯智深, 奧尼爾, 恩比德
• 粘液質: 安靜, 穩重, 反應慢, 沉默寡言, 善于忍耐, 典型人物: 魯肅, 司馬懿, 鄧肯, 卡哇伊
• 抑郁質: 孤僻, 行動遲緩, 體驗深刻, 多愁善感, 善于察覺細節... 典型人物: 林黛玉, 羅斯

需求: 如何通過一個的性格(行為習慣) 來判斷小陳同學的氣質類型

• K-means: 小陳同學比較孤僻, 沉默寡言, 總沉浸在自己的世界... 但偶爾也活潑好動..嗯, 就判定為抑郁型
• EM: 綜合來看, 小陳同學有 30%是多血的, 50%是粘液的, 抑郁, 膽汁各10%, 嗯...大機率, 偏向粘液質一點.

從偏理論來看

E-步驟

K-means 的 \(r_{nk}\)

def \(r_{nk}\)

IF \(k = arg \ min_j \ ||x_n - u_k||^2\)

return 1

ELSE:

return 0

就是逐個計算每個樣本到各中心距離, 離哪個近,就歸為該類, 複雜度是 O(kn)

就相當于咱之前推導高斯混合裡面的 \(w_j^{(i)}\)

EM 的判别則為:

\(p^{(i)} (k|n) = \frac {p_k^{(i)} g(x_n; m_k^{(i)} \sigma_k^{(i)})}{\sum \limits _{m=1}^K p_k^{(i)} g(x_n; m_k^{(i)} \sigma_k^{(i)})}\)

就是一個全機率下的貝葉斯嘛.

def $P(k|n) $ :

IF \(k = arg \ max _s \ p(s| x_n, m_k, \sigma_k)\)

return 1

ELSE:

return 0

M-步驟

K-means 就是在周遊完一輪後, 進行中心點的更新

\(\mu_k = \frac {\sum \limits _{n} r_{nk} x_n}{\sum \limits _{n} r_{nk}}\)

就是将目前該類别下的所有點, 加起來, 再求平均, 得到中心

EM 也是做一樣的事情呀

\(m_k^{(i+1)} = \frac {\sum \limits _{n=1}^N p^{(i)}(k|n)x_n} {\sum \limits _{n=1}^N p^{(i)}(k|n)}\)

就到這裡吧, 這篇主要是回憶和小結一波 k-means 和 EM算法, 感覺EM算法整明白了對自信心提升還是蠻大的, 因為它涉及機率分布, 參數估計, 最大似然, 貝葉斯等, 這些都是機率論的核心知識點呀, 是需要一定功力的哦.