Clustering 分群懶人包
什麼是 Clustering 分群呢?
每一筆資料是高維度空間中的一個點，即每一個特徵為一個維度。 假設這些點存在群聚分佈的現象，則我們可以透過非監度式學習 (unsupervised) 的方法，找出對應的群聚分割分佈，如下圖所示…
那有什麼方法能分群呢?
統計上的分群有…
• K-means
• EM(Expectation-Maximization Algorithm)
• GMM(Gaussian Mixture Model)
• Bayesian-GMM (Bayesian Gaussian Mixture Model)
讓我們依序看下去….
• K-means
Key Points :
假設在 N 筆資料中，可將資料分為 K 群。透過反覆的閱讀資料點，更新對應的群中心，可視作質心點 µ₁, …, μ_K ，使得找到最代表每個群的對應質心
，換句話說，每個資料點會被分配到與他最相近的群裡。
Algorithm:
接下來，是專業一點點的說法….
先介紹會用到的符號
(1)我們有 N 筆維度皆為 d 的資料點，分別標記為 X = {x₁, x₂, …, x_N}。
(2)假定存在 K 群分佈，亦即給定 K 個 prototype vectors，記為 μ₁, …, μ_K。
(3)計算第 n 筆資料和第 k 個中心的距離 (∥xₙ − µₖ∥₂)²
(4)定義 rₙₖ 表示對每個資料點 xₙ 與第 k 群的 indicator variable
(5)最後定義 objective function J 記為
記住後就開始訓練吧!
step 1:
Choose K prototype vectors as initial values for μₖ , randomly.
step 2:
For t = 1, …
(1) For each data point xₙ, determine rₙₖ
where 1≤ k≤ K.
(2) Update µₖ
Repeat step 2 until µₖ converges.
• EM(Expectation-Maximization Algorithm)
EM-Algorithm 有許多的統計專有名詞和證明，對此就不推坑了，就以演算法流程做一個簡約的概念敘述。
跟上述的 K-means 極類似的概念，就是去找到一組收斂的參數 θ，在統計學 裡面，最能代表的，就是找到能夠表示出分佈的機率密度函數 f 以及對應的參 數「均值 µ」以及「變異數 σ」，接著用已知的樣本作為每次更新概似函數 (MLE, maximal likelihood function)
的下界 (LB, lower bound)
之參數，z 代表的是隱藏的訊息。
Key Points :
如果您是一個對統計相當無感的人，建議您可以遐想成「質心→ µ」、「半徑→ σ」 的收斂狀況，而且距離質心越近的分佈會越密集，一個住市中心和郊區的概念， 當然這個想法不完全的正確，但是可以當作一個概念的比擬。
Algorithm :
給定有 N 筆維度為 d 的資料，給每個樣本分別標記為 {x₁, x₂, …, x_N}， 每個樣本之間彼此獨立，稱為 i.i.d. (independent and identical distribution)。
假定存在 K 群，zᵏ為第 k 群的隨機變數 (又稱，censored data)，初始化參數…就是說當 t = 0 時的初始值 θ⁰
where q(zᵏ) = αₖ for k = 1,…,K.
E-step :
假設已知參數 θᵗ，則計算
用已更新整體權重 wₖᵗ
M-step :
經由 MLE 的計算，估計 q(θᵗ; θᵗ⁺¹) 的參數 θᵗ⁺¹，並且更新 θᵗ⁺¹
Until θ converges…
Comment:
EM 只是一個統計上的演算法流程，比較常見的應用有 GMM(Gaussian Mixture Model) 和 HMM(Hidden Markov Model)。
• GMM(Gaussian Mixture Model)
簡單來說，GMM 就是 EM-Algorithm 在每個機率密度函數為 Gaussian Distribution 假設下的例子。 深入淺出地說明 GMM 的重點，就是在於當 data distribution 可能出現雙峰(或多峰)的分佈情形，這個由兩個高斯分佈所相加成的過程我們稱之為高斯混合模型 (Gaussian Mixture Model)。
• Bayesian-GMM (Bayesian Gaussian Mixture Model)
這邊我們不做複雜的推導，只用一句不嚴謹的話表示
Bayesian Gaussian Mixture = Gaussian distribution + Dirichlet process
當我們不知道要分幾群比較好時，往往都會設定過多的群數 K ，用底下那張圖做說明，如果將 K 設定為 5，但實際上只需要 3群就能分得很好了，使用 GMM 會讓效果變得很不實際，所以再確立是 Gaussian distribution 加上 Dirichlet process 拯救這樣的現象。
遇到問題時，要怎麼著手?
Take the example….
底下我們就用 python 之 sklearn 這個套件來看一些簡單的例子說明….
- 首先，我們用套件 sklearn 裡的函數 make_classification、make_blobs、make_blablablabla…，取得一些隨機分佈，當作我們實作的資料。製作資料時，可以自由的選擇想要的特徵個數(n_feature)、預設資料要有幾個類別(n_classes)、每群預設有幾個類別(n_clusters_per_class)。
畫出來看看，到底隨機抽到什麼東西咧…
2. 上面演算法看得霧煞煞，不會照著步驟寫 code 該怎麼辦呢？
想太多了啦!!! sklearn 有一堆套件，只需要兩個指令就行啦!!!底下用兩個 不同的函數做示範。
(1) 如果是 sklearn.cluster 裡的函數，只需要 fit 和 label 兩道指令。
(2) 如果是 sklearn.mixture 裡的函數，只需要 fit 和 predict。
剩下的就給大家自己練習啦!!!
這麼多哪個比較好? 有沒有 SOP?
拿到資料，畫完分佈圖，一點頭緒都沒，那 K-means 先套下去準沒錯。
如果畫完發現 K-Means 發現，群聚現象明顯，或是本身是統計數據資料，分群分得不好， 不妨先假定這些群是 Gaussian Distribution，畫看看 GMM 就對啦！
但大家一定有個疑問 “”K””要怎麼設呢？這個嘛…沒有一定的答案，一般來說 K 是訓練出來的，太小或太小都會失焦，只有萬中選一的 K 會讓 objective function J 到最小值。
當你的數量龐大，有一百萬筆該怎麼辦，無法一直計算分群時，隨機抽樣一小部分的數據，用暴力法的方式看一下 K 與 objective function J 的關係圖，通常應該很快就能找到適合的 K ，一般來說，K 都不會太大，除非你的資料分布本身分布過於複雜，果真如此，痾….辛苦了！
一個小撇步告訴你，如果你可以放心大膽的假設你的數據分布是 Gaussian Distribution (不是別亂用)，但不知道要分幾群洽當，可以將 K 設稍微大一點點，接著用 Bayesian-GMM 吧！
不過注意一下!!!有時候資料看起來應該很好分群的，可是演算法試過千千百百種就是沒有好的分群，這時不妨停下腳步看看你的 initial value 起始值可能選到一個不理想的的點，這在機器學裡是非常常見的，起始點的選擇也是有千千百百種的(QAQ)。
在此，要提醒各位，上述分群的演算法不是萬能，測距的方式皆為一個資料點與中心點的直線距離，如果資料本身是個””抽象分布””或是””不規則形””，例如以下的範例，會深刻感受到上述方法不適用於此。
嚇到吃手手….三十六計看到先放棄….??放棄太早了！
辦法是人想的，接下來會有一些分法，專門處理不規則的群聚形狀或是抽象…..
Reference:
(1) 機器學習: EM 演算法(Expectation-Maximization Algorithm, EM)、高斯混合模型(Gaussian Mixture Model, GMM)和GMM-EM詳細推導
(2) Gaussian Mixture Model Selection
(3) Comparing different clustering algorithms on toy datasets
