Clustering 分群懶人包

什麼是 Clustering 分群呢?

Kinna Chen
Jan 23 · 9 min read

每一筆資料是高維度空間中的一個點,即每一個特徵為一個維度。 假設這些點存在群聚分佈的現象,則我們可以透過非監度式學習 (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 這個套件來看一些簡單的例子說明….

  1. 首先,我們用套件 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

Taiwan AI Academy

news, tech reviews and supplemental materials

Kinna Chen

Written by

Taiwan AI Academy

news, tech reviews and supplemental materials

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade