[學習筆記] 機器學習: 非監督式學習 (Machine Learning: Unsupervised Learning)

Supervised Learning:


給定一組 labeled training set, 每個 training example 標示了 positive 或是 negative.

Training set: {\( (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), ..., (x^{(m)}, y^{(m)}) \)}

目標是找出 decision boundary 區分 positive label examples 與 negative label examples.
Unsupervised Learning:


給定一組 labeled training set, 但每個 training example 沒有標示 labels.

Training set: {\( x^{(1)}, x^{(2)}, ..., x^{(m)} \)}

目標是找出資料之中的結構.



以上圖為例, 其中一種結構是把資料分為不同的群 (cluster), 能夠自動把資料分類為不同的群的演算法稱為分群演算法 (clustering algorithm).

Clustering algorithm 的應用: 自動分類客戶群 (market segmentation), social network 分析, data center 自動找出電腦分群架構最佳配置, 天文資料分析.

K-means algorithm 簡介


K-means algorithm 是最被廣為使用的 clustering algorithm.



假設我們的 training set 如上圖所示, 我們想要把它分為 2 個 cluster.



首先, 如上圖, 隨機選取 2 個點, 稱為 cluster centroids.



接著, 進行 cluster assignment, 對於每一個 training example, 根據它距離哪一個 cluster centroid 較近, label 為其中之一.

以上圖為例, 距離紅色 cluster centroid 較近的 training examples, label 為紅色; 距離藍色 cluster centroid 較近的 training examples, label 為藍色.



然後, 進行 move centroids. 把 centroid 移到同一群的 training examples 的中心點.

以上圖為例, 把紅色 cluster centroid 移到所有紅色 training examples 的中心點 (座標的平均值); 把藍色 cluster centroid 移到所有藍色 training examples 的中心點 (座標的平均值).

如此, 反覆進行 cluster assignment 及 move centroids, 直到 cluster assignment 不再導致 training example 被 assign 不同的 label.

K-means Algorithm


Input:
Training set Training set: {\( x^{(1)}, x^{(2)}, ..., x^{(m)} \)}
\( x^{(i)} \in \mathbb{R}^{n} \) (drop \(x_0 = 1\) convention, thus \( x^{(i)} \notin \mathbb{R}^{n+1} \) )
K: number of clusters
Randomly initialize \(K\) cluster centroids \(\mu_1, \mu_2, ..., \mu_K \in \mathbb{R}^{n} \)

Repeat {
// cluster assignment step

for \(i\) = 1 to \(m\)
\(c^{(i)}\) := index (from 1 to \(K\)) of cluster centroid closest to \(x^{(i)}\)

(或表示為 \(c^{(i)} := min_k ||x^{(i)} - \mu_k||^2\))
// move centroid step

for \(k\) = 1 to \(K\)
\(\mu_k\) := average (mean) of points assigned to cluster \(k\)
}

K-means for non-separated clusters




即使 training examples 沒有明顯的 boundary, K-means 也可以用來做有用的 clustering.

以上圖為例, 我們有顧客的身高及體重的資料, 想要設計一款衣服, 有 S, M, L, 3 種不同的尺寸, 透過 K-means, 便可以決定 S, M, L 各個尺寸要為顧客中的哪些人來設計 (market segmentation).

K-means optimization objective


\( c^{(i)} \): index of cluster (\(1, 2, ..., K\)) to which example \(x^{(i)}\) is currently assigned

\( \mu_k \): cluster centroid \(k\) (\( \mu_k \in \mathbb{R}^n \))

\( \mu_{c^{(i)}} \): cluster centroid of cluster to which example \(x^{(i)}\) has been assigned

Optimization objective:
\( J(c^{(1)}, c^{(2)}, ..., c^{(m)}, \mu_1, \mu_2, ..., \mu_K) = \frac{1}{m}\sum_{i=1}^{m}||x^{(i)}-\mu_{c^{(i)}}||^2 \)

Find parameters \( c^{(1)}, c^{(2)}, ..., c^{(m)}, \mu_1, \mu_2, ..., \mu_K \) which minimizes cost function J (sometimes called distortion cost function or the distortion of the K-means algorithm).
K-means Algorithm
Cluster assignment step: minimize J with respect to variables \( c^{(1)}, c^{(2)}, ..., c^{(m)} \) while holding \( \mu_1, \mu_2, ..., \mu_K \) fixed.

Move centroid step: minimize J with respect to variables \( \mu_1, \mu_2, ..., \mu_K \) while holding \( c^{(1)}, c^{(2)}, ..., c^{(m)} \) fixed.
K-means Algorithm 每一次的 iteration 都會使得 cost function J 越來越低.

Random initialization


Should have \( K \lt m \)

Randomly pick \(K\) training examples.

Set \( \mu_1, \mu_2, ..., \mu_K \) to these \(K\) examples.

隨著 initial 設定的 cluster centroid 不同, 可能會導致得到不同的 clustering 結果, 也可能導致得到 local optima 而非 global optima 的結果.



若 training examples 如上圖, 下圖是 global optima (of cost function J).



下圖則是 local optima.



設法找到 global optima 的方法是以各種不同的 randomly initialized cluster centroids 來 run K-means algorithm (通常跑 50 - 1000 組 random initialization), 從中選擇最佳的 local optimal solution.

for i = 1 to 100 {
Randomly initialize K-means.

Run K-means, get \(c^{(1)}, c^{(2)}, ..., c^{(m)}, \mu_1, \mu_2, ..., \mu_K\).

Compute cost function (distortion) \(J(c^{(1)}, c^{(2)}, ..., c^{(m)}, \mu_1, \mu_2, ..., \mu_K)\)
}

Pick clustering which gave the lowest cost \(J(c^{(1)}, c^{(2)}, ..., c^{(m)}, \mu_1, \mu_2, ..., \mu_K)\)

如果 K 在 2 - 10 之間, 這個方法有助於找到不錯的 local optimal solution. 但如果 K 較大, 採用這個方法與否則不見得會有顯著的差別.

選擇 cluster 數的考量


對於 unsupervised learning, 因為 training examples 並沒有預先標 labels, 因此對於 cluster 數多少才是最佳解, 並沒有標準答案, 主要得靠手動測試及觀察.



以上圖為例, 把 data set 分為 2 個 cluster 或 4 個 cluster, 似乎都是合理的.

Elbow method:



觀察 cost function J 隨著 K (number of clusters) 增加而遞減的變化, 當變化趨緩前的 K, 視為最佳解.

以上圖為例, 當 K 在 5 之後, cost function 的遞減大幅趨緩, 因此 4 視為最佳解.



但 Elbow method 不一定有效, 因為經常遇到的情況如上圖所示, 不見得容易觀察到遞減明顯趨緩的那個點.

如果 cost function 並沒有隨著 K 增加而遞減, 需要在異常的 cluster 數的情況多跑幾次 random initialization.
舉例來說, 如果 K=5 時的 cost function 比 K=3 時的高, 應該多跑幾次 K=5 的 random initialization, 直到 K=5 時的 cost function 比 K=3 時的低.
決定合適的 cluster 數的一個務實的方法, 是回過頭來思考跑 K-means 把資料分群是為了什麼目的, 然後根據衡量符合該目的的程度的指標, 來選擇合適的 cluster 數.

延伸閱讀


[Coursera] Machine Learning: Unsupervised Learning, by Andrew Ng, Stanford University