Learning Objectives
- 從月牙形資料說明 k-means 的假設與限制
- 讀懂階層式分群的合併表與樹狀圖，並比較四種連結方式
- 區分 DBSCAN 的核心點、邊界點與噪音點，並用 numpy 算出來
- 說明 eps 太小與太大各會怎樣，以及輪廓係數不一定能判斷形狀特殊的群
k-means 做不到的事
上一課的 k-means 很好用，但它有幾個內建的假設：
- 要先決定 k；
- 每一群大致是圓的、大小相近：指派時每一點找最近的群心，所以兩個群心之間的邊界一定是直線；
- 每一點都要歸到某一群：明顯的離群值也會被算進去，還會把群心拉過去。
資料不符合這些假設時會怎樣？用 make_moons 產生兩個彎月形（這是 scikit-learn 內建的模擬資料），人眼一看就知道是兩群。
逐步看：k-means 切不開月牙
make_moons 會同時回傳每一點真正屬於哪個月牙，這裡只用來事後檢查，分群時沒有用到。
階層式分群：由下而上一路合併
階層式分群（hierarchical clustering）不用先決定 k。最常用的是由下而上的凝聚式做法：
- 一開始每一點自成一群；
- 找出距離最近的兩群，合併成一群；
- 重複第 2 步，直到全部合成一群。
整個合併過程可以畫成一棵樹狀圖（dendrogram）：葉子是資料，兩條線接起來的高度是合併時的距離。 要分成幾群，事後在某個高度橫切一刀就好，切到幾條線就是幾群。
「兩群之間的距離」有好幾種定義，這個選擇叫連結方式（linkage）：
| 連結方式 | 兩群的距離 | 特性 |
|---|---|---|
ward |
合併後群內變異增加多少 | 傾向大小相近的圓形群，和 k-means 相似；scikit-learn 的預設值，只能配歐氏距離 |
complete |
兩群之間最遠的兩點 | 群比較緊湊 |
average |
兩群之間所有點對的平均距離 | 介於中間 |
single |
兩群之間最近的兩點 | 能順著長條形狀連下去，但容易被一串點連成一大群 |
逐步看：合併表與樹狀圖
八個點，看得出三團：編號 0～2、3～5、6～7。linkage 回傳的表每一列是一次合併。
逐步看：四種連結方式切月牙
同一份月牙資料，換四種連結方式。三欄分別是：連結方式、和真正月牙一致的比例、輪廓係數。上一個範例 k-means 的數字是 0.743 與 0.488。
輪廓係數也有偏好
上面的結果值得停下來想：完全切對的分法，輪廓係數反而最低。
輪廓係數比的是平均距離。一個彎月形很長，同一群裡兩端的點離得很遠，a 就大；而兩個月牙有些地方靠得很近，b 就小。
所以它偏好圓形、分得很開的群，形狀特殊時不能單靠它判斷。這裡能知道誰對，是因為我們有 y 可以事後檢查；真實的分群問題沒有 y，所以要畫出來看、看群的內容，不要只看一個數字。
single 也不是萬用的：兩個月牙之間只要有幾個點連起來，它就會把兩群合成一群。接下來的 DBSCAN 用另一種想法處理這個問題。
DBSCAN：看密度，不看距離中心多遠
DBSCAN（Ester、Kriegel、Sander 與 Xu 在 1996 年提出）的想法是：群就是密度高的區域，中間被稀疏的地方隔開。它有兩個參數：
eps：多近才算鄰居（半徑）；min_samples：半徑內至少要有幾個點，才算密度夠高。scikit-learn 的計算方式包含這一點自己。
依照這兩個參數，每一點是下面三種之一：
| 種類 | 條件 | 結果 |
|---|---|---|
| 核心點 | 半徑 eps 內至少有 min_samples 個點 |
互相可及的核心點連成一群 |
| 邊界點 | 自己不是核心點，但在某個核心點的半徑內 | 加入那個核心點的群 |
| 噪音點 | 以上皆非 | 不屬於任何群，標籤是 −1 |
和 k-means 比起來，它不用指定 k、群可以是任意形狀、允許有點不屬於任何群。
逐步看：哪些點是核心點
十一個點。先用 numpy 算出每一點的鄰居數，再和 scikit-learn 的 DBSCAN 對照。注意第 9 點與第 10 點。
逐步看：eps 怎麼影響結果
月牙資料加上 12 個隨機散布的離群點，共 312 個點。min_samples 用預設的 5，看 eps 從小到大時群數與噪音點怎麼變。
該用哪一種
eps 的範圍其實很窄：上面的資料，0.1 太小、0.4 太大。而且它是距離，一樣受尺度影響，通常要先標準化。
| k-means | 階層式 | DBSCAN | |
|---|---|---|---|
| 要先決定 | k | 連結方式；k 可事後再切 | eps、min_samples |
| 群的形狀 | 大致是圓的 | 看連結方式 | 任意形狀 |
| 離群值 | 也要歸到某一群 | 也要歸到某一群 | 標成噪音點 |
| 不適合的情況 | 形狀特殊、大小差很多 | 資料很多時（合併過程要算所有點對的距離） | 各群密度差很多（一個 eps 顧不到全部） |
| 新資料 | predict 找最近的群心 |
沒有 predict |
沒有 predict |
沒有哪一種永遠最好。資料不大時可以都試試看，畫出來比較；維度太高畫不出來時，下一課的 PCA 可以幫忙。
實作：判斷每一點是哪一種
完成 find_points(X, eps, min_samples)：回傳一個串列，每一點是 "核心"、"邊界" 或 "噪音"。
- 核心：半徑
eps內（含自己）至少min_samples個點； - 邊界：不是核心，但半徑內有核心點；
- 噪音：以上皆非。
小測驗：階層式分群與 DBSCAN
下面程式會印出什麼？（eps=1.5，鄰居數包含自己）
import numpy as np
X = np.array([[0.0], [1.0], [2.0], [9.0]])
dist = np.abs(X - X.T)
print((dist <= 1.5).sum(axis=1).tolist())
DBSCAN 回傳的標籤裡，−1 代表什麼？
資料是兩個細長的彎月形，哪一種分法最可能切開它們？
把 eps 從適當的值一路調大，通常會怎樣？
一種分法的輪廓係數 0.33，另一種 0.49，而資料是形狀特殊的彎月形。最恰當的解讀是？
階層式分群做完之後，想從 3 群改成 4 群，要怎麼做？
重點整理
- k-means 假設群大致是圓的、每一點都要歸群；不符合時（例如月牙）就切不開。
- 階層式分群由下而上合併，樹狀圖上橫切一刀就得到群；連結方式影響很大：
ward偏好圓形的群，single能順著形狀連下去。 - DBSCAN 看密度：核心點連成群，邊界點跟著核心點，噪音點標成 −1；不用指定 k，但要調
eps與min_samples，而且受尺度影響。 - 輪廓係數偏好圓形的群：完全切對月牙的分法分數反而最低。沒有標籤時要畫出來、看內容，不要只靠一個數字。
- 下一課的 PCA 處理另一個問題：特徵太多、畫不出來時，怎麼把資料投影到少數幾個方向。