---
disqus: ierosodin
---

# Clustering

> Organization contact [name= [ierosodin]([e-mail])]
###### tags: `machine learning` `學習筆記`

==[Back to Catalog](https://hackmd.io/@ierosodin/Machine_Learning)==

前面所介紹的方法，無論是 regression 還是 classification，都是屬於 supervise learning，也就是 training data 為 complete data。
然而時常我們所蒐集的資料室 incomplete data，也就是缺少 label 的資料，此時就必須依靠 unsupervise learning 來進行分類，常見的分類有：
1. K means clustering
2. Hierarchical clustering
3. EM algorithm
4. Gaussian Mixture model(GMM)

## K-means

先隨機找尋 k 個中心，並對所有的 training data 進行分類，靠近誰就加入那個中心。分類完後，對於每一群，重新計算群中心，並利用新的群中心再次進行分類，不斷迭代下去，直到收斂為止。

這種方法有可能會卡在 local minimum，因此需要多次實驗，找到真正的最小值。

## Hierarchical clustering

分成了 divisive 與 agglomerative algorithm，前者一開始假設為一群，並不斷的分裂，直到達到指定的群數，後者則是由一點一群開始，慢慢聚集直到達到指定群數。

### agglomerative algorithm

舉幾個聚集法的例子：

1. 單一連結聚合演算法（single-linkage agglomerative algorithm）
* 找兩群最近的距離作為判斷依據，也就是找 ${D_{min}}$ 最小的來合併
* 

2. 完整連結聚合演算法（complete-linkage agglomerative algorithm）
* 找兩群最遠的距離作為判斷依據，也就是找 ${D_{max}}$ 最小的來合併
* 

3. 平均連結聚合演算法（average-linkage agglomerative algorithm）
* 找兩群所有可能距離的平均值為依據，也就是找 ${D_{avg}}$ 最小的來合併
4. 沃德法（Ward's method）
* 以兩群合併後，每一點到新的群中心的平均值為依據
* 

## EM algorithm

在推導 EM algorithm 之前，我們先來看一個處裡 complete data 過程：

### one coin toss

在前面的章節，我們有推導過，如果今天投擲一個硬幣 N 次，則 ${P_{MLE}\ =\ \frac{\sum x}{N}}$，而 ${P_{MLE}}$ 為這個硬幣投擲出正面最有可能的機率。

### two coin toss

如果今天有兩個硬幣呢？我們必須先假設三個變數：
1. ${P_0}$ 為 ${C_0}$ 硬幣出現正面的機率
2. ${P_1}$ 為 ${C_1}$ 硬幣出現正面的機率
3. ${\lambda}$ 為投擲 ${C_0}$ 硬幣的機率

假設今天我們投擲了硬幣十次，${X}$ 為該次投擲的 random variable（正面或反面），而 ${Z}$ 為該次投擲的硬幣 index（0 或 1）。
因為是 complete data，所以我們可以得到以上所有資訊，接下來就要找出在 MLE 的時候，三個變數為多少。

要 maximum 的式子為：
${P\ =\ \prod (\lambda P_0^{x_i}(1-P_0)^{1-x_i})^{1-z_i}((1-\lambda)P_1^{x_i}(1-P_O)^{1-x_i})^{z_i}}$

一樣，我們先取 ${log}$：
$\begin{split}J\ =\ &\sum (1-z_i)(log\lambda\ +\ x_ilogP_0\ +\ (1-x_i)log(1-P_0))\ +\ z_i(log(1-\lambda)\ \\
&+\ x_ilogP_1\ +\ (1-x_i)log(1-P_1))\end{split}$

首先，求 ${\lambda_{MLE}}$：
${\begin{split}\frac{\partial J}{\partial \lambda}\ &=\ \sum (1-z_i)\frac{1}{\lambda}\ +\ z_i\frac{-1}{1-\lambda}\ =\ 0 \\
&\Rightarrow\ \sum (1-z_i)\frac{1}{\lambda}\ =\ \sum z_i\frac{1}{1-\lambda} \\
&\Rightarrow\ (1-\lambda)\sum(1-z_i)\ =\ \lambda\sum z_i \\
&\Rightarrow\ \sum(1-z_i)\ =\ \lambda\sum z_i\ +\ \lambda\sum(1-x_i)\ =\ \lambda N\\
&\Rightarrow\ \lambda_{MLE}\ =\ \frac{\sum(1-z_i)}{N}\end{split}}$

${P_0}$：
${\begin{split}\frac{\partial J}{\partial P_0}\ &=\ \sum (1-z_i)(\frac{x_i}{P_0}\ +\ (1-x_i)\frac{-1}{1-P_0})\ =\ 0 \\
&\Rightarrow\ \sum (1-z_i)\frac{x_i}{P_0}\ =\ \sum (1-z_i)\frac{1-x_i}{1-P_0} \\
&\Rightarrow\ (1-P_0)\sum(1-z_i)x_i\ =\ P_0\sum (1-z_i)(1-x_i) \\
&\Rightarrow\ \sum(1-z_i)x_i\ =\ P_0\sum (1-z_i)(1-x_i)\ +\ P_0\sum(1-z_i)x_i\ =\ P_0 \sum(1-z_i)\\
&\Rightarrow\ P_{0,MLE}\ =\ \frac{\sum(1-z_i)x_i}{\sum(1-z_i)}\end{split}}$

${P_1}$：
${\begin{split}\frac{\partial J}{\partial P_1}\ &=\ \sum z_i(\frac{x_i}{P_1}\ +\ (1-x_i)\frac{-1}{1-P_1})\ =\ 0 \\
&\Rightarrow\ \sum z_i\frac{x_i}{P_1}\ =\ \sum z_i\frac{1-x_i}{1-P_1} \\
&\Rightarrow\ (1-P_1)\sum z_ix_i\ =\ P_1\sum z_i(1-x_i) \\
&\Rightarrow\ \sum z_ix_i\ =\ P_1\sum z_i(1-x_i)\ +\ P_1\sum z_ix_i\ =\ P_1 \sum z_i\\
&\Rightarrow\ P_{1,MLE}\ =\ \frac{\sum z_ix_i}{\sum z_i}\end{split}}$

亦即：
${\lambda\ =\ \frac{C_0\ 出現次數}{總投擲次數}}$
${P_0\ =\ \frac{C_0\ 出現且為正面的次數}{C_0\ 出現次數}}$
${P_1\ =\ \frac{C_1\ 出現且為正面次數}{C_1\ 出現次數}}$

### Incomplete date

那如果今天我們拿不到 ${z_i}$ 的資料呢？
取而代之，我們假設今天第 ${i}$ 次投擲投到 ${x_i}$ 時，是 ${C_0}$ 的機率為 ${w_i}$
假設今天第 ${i}$ 次投到正面，則 ${w_i}$ 代表在所有投擲結果為正面的情況下，是 ${C_0}$ 投出來的機率是多少。

> 注意，${w_i}$ 是會根據 outcome 不同而改變的，在這個例子，就會有投擲到正面的 ${w_i}$ 和投擲到反面的 ${w_i}$。
> ${w_i}$ 又被稱為 responsibility

現在就可以開始我們的 EM algorithm：

首先我們先隨意假設 ${P_0,\ P_1,\ \lambda}$

E step：
分別計算兩個 ${w_i}$，
1. 投擲到正面的 ${w_i\ =\ \frac{P_0\lambda}{P_0\lambda\ +\ P_1(1-\lambda)}}$
2. 投擲到反面的 ${w_i\ =\ \frac{(1-P_0)\lambda}{(1-P_0)\lambda\ +\ (1-P_1)(1-\lambda)}}$

M step：
找出在這組 ${w_i}$ 下，${P_0,\ P_1,\ \lambda}$ 的 weight likelihood。
${\lambda\ =\ \frac{\Sigma w_i}{N}}$
${P_0\ =\ \frac{\sum w_ix_i}{\sum w_i}}$
${P_1\ =\ \frac{\sum(1-w_i)x_i}{\sum(1-w_i)}}$

> 再次強調，每個 ${w_i}$ 要根據當次的 ${x_i}$ 為正面或反面來決定

### Why EM work

在解說為何 EM 會成功以前，我們先介紹一個工具：

#### Jensen’s inequality


上圖說明了，當今天一個函數為 convex 時，${f(\sum x_i) \leq \sum f(x_i)}$
反之，當今天一個函數為 concave 時，則 ${f(\sum x_i) \geq \sum f(x_i)}$

#### EM algorithm for incomplete data

回到我們的 EM algorithm，首先必須知道，${log}$ function 屬於 concave function，因此觀察我們的 function J：
${J\ =\ \sum P(X, z_i|\theta)}$

然而在 incomplete data 中，我們並沒有 ${z_i}$ 的資訊，因此我們假設一個未知分佈 ${q(z_i)}$，式子變成：
${log\sum q(z_i)\frac{P(X, z_i|\theta)}{q(z_i)}}$

又因為 ${log}$ function 屬於 concave function：
${\begin{split}&log\left(\Sigma q(z_i)\frac{P(X, z_i|\theta)}{q(z_i)}\right) \geq \sum q(z_i)log\left(\frac{P(X, z_i|\theta)}{q(z_i)}\right) \\
=\ &\sum q(z_i)log\left(\frac{P(z_i|X, \theta)P(X|\theta)}{q(z_i)}\right) \\
=\ &\sum q(z_i)log\left(P(X|\theta)\right)\
+\ \sum q(z_i)log\left(\frac{P(z_i|X, \theta)}{q(z_i)}\right) \\
=\ &\sum q(z_i)log\left(P(X|\theta)\right)\
-\ \sum q(z_i)log\left(\frac{q(z_i)}{P(z_i|X, \theta)}\right)\end{split}}$

可以發現，${\sum q(z_i)log\left(\frac{q(z_i)}{P(z_i|X, \theta)}\right)}$ 其實就是 ${KL(q||p)}$，而 ${q(z_i)}$ 其實就是 ${w_i}$。

因此每次我們在做 E step 的時候，其實就是在 minimum ${KL(q||p)}$（還記得 ${KL(q||p)\ =\ 0}$ 的情況為：${q}$ 與 ${p}$ 的分佈相同）。
所以在 E step，我們計算 ${w_i}$ 就是使 ${w_i}$ 與當下 ${P_0,\ P_1,\ \lambda}$ 所產生的硬幣分佈是相同的。

而在 M step 的過程，其實就是在 ${\sum P(X, z_i|\theta)\ =\ \sum q(z_i)log\left(P(X|\theta)\right)}$ 的情況下，找到 MLE 的 ${P_0,\ P_1,\ \lambda}$（或者說這三項的 weight likelihood）

又因為改分佈後，${q}$ 與 ${p}$ 的分佈又會不同，因此回到 E step 重新找 ${KL\ =\ 0}$ 的 ${w_i}$，不斷的重複。
而每次更新 ${P_0,\ P_1,\ \lambda}$ 都只會讓 lower bound 更高，因此只會更好，不會更遭，直到收斂為止。

## Gaussian Mixture model (GMM)

GMM 其實就是把 Bernoull 分佈改為 Gaussian distribution，因此對應前面的例子，我們必須要有五個參數：${\lambda,\ \mu_0,\ \mu_1,\ \sigma_0,\ \sigma_1}$

### Complete data in special case

先看一個特殊的例子，當所有的 Gaussian distribution 的 variance 都是 1 時，我們可以簡化參數到三個：${\lambda,\ \mu_0,\ \mu_1}$

則按照前面的推導：
${P(X|\theta)\ =\ \prod (\lambda \frac{1}{\sqrt{2\pi}}e^{-(x_i-\mu_0)^2})^{1-z_i}((1-\lambda) \frac{1}{\sqrt{2\pi}}e^{-(x_i-\mu_0)^2})^{z_i}}$

${J\ =\ \sum(1-z_i)(log\frac{1}{\sqrt{2\pi}}+log\lambda-(x_i-\mu_0)^2)+\sum z_i(log\frac{1}{\sqrt{2\pi}}+log(1-\lambda)-(x_i-\mu_1)^2)}$

${\begin{split}\frac{\partial J}{\partial \lambda}\ &=\ \sum (1-z_i)\frac{1}{\lambda}\ +\ z_i\frac{-1}{1-\lambda}\ =\ 0 \\
&\Rightarrow\ \sum (1-z_i)\frac{1}{\lambda}\ =\ \sum z_i\frac{1}{1-\lambda} \\
&\Rightarrow\ (1-\lambda)\sum(1-z_i)\ =\ \lambda\sum z_i \\
&\Rightarrow\ \sum(1-z_i)\ =\ \lambda\sum z_i\ +\ \lambda\sum(1-x_i)\ =\ \lambda N\\
&\Rightarrow\ \lambda_{MLE}\ =\ \frac{\sum(1-z_i)}{N}\end{split}}$

${\begin{split}\frac{\partial J}{\partial \mu_0}\ &=\ \sum (1-z_i)(x_i-\mu_0)\ =\ 0 \\
&\Rightarrow\ \sum (1-z_i)x_i\ -\ \sum (1-z_i)\mu_0\ =\ 0 \\
&\Rightarrow\ \sum (1-z_i)x_i\ =\ \sum (1-z_i)\mu_0 \\
&\Rightarrow\ \mu_{0,MLE}\ =\ \frac{\sum (1-z_i)x_i}{\sum (1-z_i)}\end{split}}$

${\begin{split}\frac{\partial J}{\partial \mu_1}\ &=\ \sum z_i(x_i-\mu_1)\ =\ 0 \\
&\Rightarrow\ \sum z_ix_i\ -\ \sum z_i\mu_1\ =\ 0 \\
&\Rightarrow\ \sum z_ix_i\ =\ \sum z_i\mu_1 \\
&\Rightarrow\ \mu_{1,MLE}\ =\ \frac{\sum z_ix_i}{\sum z_i}\end{split}}$

### Complete data in general case

推廣到五個變數：

${P(X|\theta)\ =\ \prod (\lambda \frac{1}{\sqrt{2\pi\sigma_0^2}}e^{\frac{-(x_i-\mu_0)^2}{2\sigma_0^2}})^{1-z_i}((1-\lambda) \frac{1}{\sqrt{2\pi\sigma_1^2}}e^{\frac{-(x_i-\mu_1)^2}{2\sigma_1^2}})^{z_i}}$

${J\ =\ \sum(1-z_i)(log\frac{1}{\sqrt{2\pi\sigma_0^2}}+log\lambda-\frac{(x_i-\mu_0)^2}{2\sigma_0^2})+\sum z_i(log\frac{1}{\sqrt{2\pi\sigma_1^2}}+log(1-\lambda)-\frac{(x_i-\mu_1)^2}{2\sigma_1^2})}$

${\begin{split}\frac{\partial J}{\partial \lambda}\ &=\ \sum (1-z_i)\frac{1}{\lambda}\ +\ z_i\frac{-1}{1-\lambda}\ =\ 0 \\
&\Rightarrow\ \sum (1-z_i)\frac{1}{\lambda}\ =\ \sum z_i\frac{1}{1-\lambda} \\
&\Rightarrow\ (1-\lambda)\sum(1-z_i)\ =\ \lambda\sum z_i \\
&\Rightarrow\ \sum(1-z_i)\ =\ \lambda\sum z_i\ +\ \lambda\sum(1-x_i)\ =\ \lambda N\\
&\Rightarrow\ \lambda_{MLE}\ =\ \frac{\sum(1-z_i)}{N}\end{split}}$

${\begin{split}\frac{\partial J}{\partial \mu_0}\ &=\ \sum (1-z_i)(x_i-\mu_0)\ =\ 0 \\
&\Rightarrow\ \sum (1-z_i)x_i\ -\ \sum (1-z_i)\mu_0\ =\ 0 \\
&\Rightarrow\ \sum (1-z_i)x_i\ =\ \sum (1-z_i)\mu_0 \\
&\Rightarrow\ \mu_{0,MLE}\ =\ \frac{\sum (1-z_i)x_i}{\sum (1-z_i)}\end{split}}$

${\begin{split}\frac{\partial J}{\partial \mu_1}\ &=\ \sum z_i(x_i-\mu_1)\ =\ 0 \\
&\Rightarrow\ \sum z_ix_i\ -\ \sum z_i\mu_1\ =\ 0 \\
&\Rightarrow\ \sum z_ix_i\ =\ \sum z_i\mu_1 \\
&\Rightarrow\ \mu_{1,MLE}\ =\ \frac{\sum z_ix_i}{\sum z_i}\end{split}}$

${\begin{split}\frac{\partial J}{\partial \sigma_0}\ &=\ \sum (1-z_i)(\frac{-2}{\sigma_0}+\frac{(x_i-\mu_0)^2}{\sigma_0^3})\ =\ 0 \\
&\Rightarrow\ \sum (1-z_i)\frac{(x_i-\mu_0)^2}{\sigma_0^3}\ -\ \sum (1-z_i)\frac{1}{2\sigma_0} =\ 0 \\
&\Rightarrow\ \sum (1-z_i)\frac{(x_i-\mu_0)^2}{\sigma_0^3}\ =\ \sum (1-z_i)\frac{2}{\sigma_0} \\
&\Rightarrow\ \sigma_{0,MLE}^2\ =\ \frac{\sum (1-z_i)(x_i-\mu_0)^2}{2\sum (1-z_i)}\end{split}}$

${\begin{split}\frac{\partial J}{\partial \sigma_1}\ &=\ \sum (1-z_i)(\frac{-2}{\sigma_1}+\frac{(x_i-\mu_1)^2}{\sigma_1^3})\ =\ 0 \\
&\Rightarrow\ \sum z_i\frac{(x_i-\mu_1)^2}{\sigma_1^3}\ -\ \sum z_i\frac{2}{\sigma_1} =\ 0 \\
&\Rightarrow\ \sum z_i\frac{(x_i-\mu_1)^2}{\sigma_1^3}\ =\ \sum z_i\frac{2}{\sigma_1} \\
&\Rightarrow\ \sigma_{1,MLE}^2\ =\ \frac{\sum z_i(x_i-\mu_1)^2}{2\sum z_i}\end{split}}$

### Incomplete data

其實和 EM algorithm 一樣，分成 E step 與 M step，在每次的 E step，需要計算 ${w_i}$：
${w_{i, outcome=0}\ =\ \frac{\lambda e^{\frac{-(x_i-\mu_0)^2}{2\sigma_0^2}}}{\lambda e^{\frac{-(x_i-\mu_0)^2}{2\sigma_0^2}}+(1-\lambda)e^{\frac{-(x_i-\mu_1)^2}{2\sigma_1^2}}}}$

${w_{i, outcome=1}\ =\ \frac{(1-\lambda) e^{\frac{-(x_i-\mu_1)^2}{2\sigma_1^2}}}{\lambda e^{\frac{-(x_i-\mu_0)^2}{2\sigma_0^2}}+(1-\lambda)e^{\frac{-(x_i-\mu_1)^2}{2\sigma_1^2}}}}$