自從第一篇講過 K-Means Clustering 的概念後，想不到要待一年零八個月的時間，才重返實戰篇。現在重溫一下概念，然後再用 python 實踐。
Cluster Analysis 是指群組分析，通過不同的演算法，將一班人或事物分類成不同的clusters。Cluster Analysis 是 unsupervised learning 之一，即從一堆沒有標籤（label）的 data 中，自動根據相似的特徵 （features）來分類或分群組。
Clustering 種類包括 K-means clustering、K-means ++ clustering 、Hierarchical clustering 和 K-NN (k nearest neighbours) 。
實際應用例子 Use Case：
究竟 clustering 如何應用在實際情況呢？我最近閱讀了 Bing Liu 寫的 Web Data Mining 這本書，所舉的3個十分好的例子。
1. Marketing Campaign
一間公司想做 marketing campaign，最好就當然為每一位顧客都度身訂做一份 marketing materials，但成本非常高；但如果公司只做一款 one size fits all 的 materials，又沒有效；最 cost- effective 的做法是根據顧客profiles 的相似度（similarities）來分groups，再為每組設計 materials。這個 segmentation task 就是用了 clustering algorithm，能將顧客劃分（partition）入相似的組別。
2. 賣衫的尺碼
一間製衣廠想生產及銷售 T-shirts，最好當然是為每位顧客度身訂做，但太沒效率了。因此，將顧客的身形大小（sizes）做 clustering，就可為每一組生產T-shirts。因此我們在服裝店通常見到的呎碼是 Large, Medium 和 Small size，很少見到每一種身形也有的 size。（這時才驚覺馬莎的體貼）
這案例普遍的做法是，以大眾的sizes做 sample，做成 measurement database。然後再將相似的data partitions 入相類似的clusters。每一個 cluster 計算平均 sizes 再大量製造（mass production）。
3. News aggregator
一間公司要做 news aggregator，從網上搜羅世界各地的新聞（news articles），但如何將新聞歸納入不同的 categories 呢？即時用人手做分類當然最好，但這樣成本高又費時，分分鐘有手民之誤。要做 classification 嗎？ Classification 是 supervised learning 即需要有 class label 做 training data，這裡亦事先需要人手做 label。而且新聞流量大、變化大，training data 亦因時變化，所以是行不通的。因此，最好的做法仍是 clustering，根據內容的相似度來自動歸類，這時需要用到的是 Hierarchical clustering algorithms，將新聞稿件分層次歸類：大的categories（又名：topics）之下有sub-categories （又名：sub-topics）。例如「港聞」之下可細分為「政治」、「突發」、「社會」等。
首 2 個例子用的是 partitional clustering，最後一個是 hierarchical clustering。但無論哪一類 clustering，都是要找「相似度」，即量度兩個objects 有幾相似，而量度的方法就是計算兩者的距離（distance），亦是所謂「物以類聚」的道理。
K-means Clustering
K-means Algorithm 是 Partitional clustering algorithm 最典型的例子 。只要有一set data，以及指定的 k 個 clusters（ k是Cluster 的數量，由 user 自訂。如K=2，即有2個Clusters），這個 algorithm 就會根據距離（measured by Euclidean distance），反覆（iterate）劃分入 k 個 clusters 中。每個 cluster 都有一個 cluster center（又叫centroid），是該 cluster 內所有 data points 的平均距離（mean）。因此，K means Algorithm 的意思是指 K 個clusters的平均距離演算法。
這個 algorithm 的做法是，首先會隨機選擇（randomly selected） k 個 data points 做 原始中心點（seed centroids）。如 k =2個 data points，即代表有2個 clusters。然後，會計算每一個 data points 與每個 seed centroid 的距離，並 assign 在最近的 centroid 內。因此，一個 centroid 及其 data points 代表一個 cluster。當所有 data points 已assign 好後，每個 cluster 的 centroid 就會用現有的 data points 重新再計算，然後根據距離重新assign 入clusters⋯⋯直至收斂（ convergence ）情況出現為止。要判斷是否完成 iteration，可根據以下三個 stopping criterion（收歛的情況）：
- Data points 沒有再被重新 assign 到其他clusters
- Centroids 沒有改變
- Sum of Squared error (SSE) 縮小減至最低
【 SSE 是 centroid 與 data points 的 deviation，即誤差，即中心點與各 data point 的距離，距離越小即 error 越小，表示 good clustering。假如 SSE 大，表示 data points 與 centroid 距離遠，並不是 good clustering。】
消失的 clusters?
K-means algorithm 在clustering 的過程中，有可能演變成 empty cluster，即一個cluster 內的 data points 全都「埋了其他堆」，整個 cluster 都真空了。要處理這問題，可以選擇距離最遠cluster的一個 data point （即SSE 最大），將它移入empty cluster 中。假如有幾個 empty cluster，以上做法就要重複幾次。
做 good cluster
有時後，我們雖然找到很多 clusters ，但可能 cluster 太細，又或 data points 與 centroid 太遠（SSE 高），都未必是 good cluster。如何做 post-processing 呢？
- 刪除有outlier 的細 cluster
- 將鬆散的 cluster ( 即 SSE 高）split 開
- 將兩個太相近的 clusters （即 SSE 較低）合併
K-means algorithm 的弱點
1. Categorical data
由於要計算 data points 及 centroid 的 mean，因此如果是 categorical data 的話，便計算不到。不過， K means algorithm 有一個變奏，就是 k-modes 來cluster categorical data。這 algorithm 用 mode 代替 mean 做 centroids。
2. Outlier
由於這 algorithm 是計算 data points 與 centroids 的平均距離，因此對於遠離其他 data points 的 outlier 出現（鶴立雞群），會有很大的影響。Outliers 可以是記錄 data 時出錯所致，又或是很特別的因素，例如在員工的薪金 data set 中，CEO 的人工由於是一眾員工的幾倍，因此是 outlier。
如何 handle outliers?
- 最簡單是在clustering 過程中，觀察幾次iterations 後，remove 遠離 centroids 的 data points。
- 選小部份的 data points 做 sampling ，首先進行 pre-clustering，當產生clusters後，視之為一個class，再做classification（supervised learning）。得出 classifier 後，就可以用來classify 剩餘的 data points，assign 入適當的 clusters中。
- 選小部份的 data points 做 sampling，首先進行 pre-clustering，當產生clusters後，視之為 seeds 進行 semi-supervised learning。Semi-supervised learning 是從小部份已有 class labels 的 instances 和大部份 un-labeled instances 中學習。
如果挑選好的 initial seeds 做 centroids？
記住，cluster 的形成跟最初你如何挑選原始 seeds 有很大關係，下圖可見，A是原始中心點，經過 B 和 C 的兩輪 iterations 後，就 convergence了。但結果可見，屬於不同clusters的 data points ，其距離十分近。這證明是 poor initial seeds。
如果重新挑選 initial seeds，可得出下圖的 clustering 結果。明顯分劃成 2大clusters，是好的 centroid。
挑選 centroids 時，有什麼方法呢？最簡單的方法是，首先把整set data 計算一次 mean。選一個距離這個 mean 最遠的 data point 做 first initial seed，然後再選距離第一個最遠的 data point做第二個 initial seed。不過假如在 data set 中有 outliers 的話，這方法就不可行。所以要先處理 outliers 才行。
第二種方法是進行 Hierarchical Clustering，這 topic 之後才說吧。
用 Scikit-learn 實戰 K-means Clustering
1. 要從 sklearn module 內的cluster 輸入 K-means 功能：
2. 準備 data
Data 最好是以 numpy array 的格式儲存。如果是其他格式，可以自建一個或 convert 做 numpy array：
np.array( [
[x1,y1], [x2, y2], [x3, y3]
])
3. 執行 k-means algorithm
以下是 k-means algorithm 的 parameters:
init = “random”
表示 initialization （起始化）的方法，by default 是 k-means++ ，或可擇隨 “random” 機抽取 data points 做 centroids
n_clusters =2
表示設定 cluster 的數量，by default 是 8 個
max_iter = 10000
表示每run 一次 algorithm 時，最多執行的 iteration 次數，by default 是 300次
n_init = 100
表示 k-means 在不同 centroid seeds （中心點）所 run 的次數，by default 是 10次
.fit(x)
表示計算 k-means clustering 的方法
4. 顯示 clustering 的分佈結果
用 kmeans.labels_ 可顯示 data points 已被分配入 0 或 1的 cluster 之中。
5. 預測新 data points 的 cluster
假如有指定的 data points ，想預測一下新 data points 會被歸入哪個 cluster，可用 kmeans.predict method。
例如下圖想知 2 個新 data points [0, 0] 和 [4, 4] 的 cluster 位置：
6. 顯示 cluster 的中心點座標
根據數據，計算出 2 個 clusters 的中心點位置：
文科人這樣讀理科 