# ML 筆記 - Ch03

###### tags: `機器學習`

## 3. 走馬看花：ML 各分類器巡覽

### 3.1 天下沒有白吃的午餐
〈天下沒有白吃的午餐〉定律（There ain't no such thing as a free lunch）
為經濟學用語，原指「任何午餐（利益）都需付出一定的 **成本**」
在 ML 中的類比是：任何 ML 模型即便再優秀，都必有其缺陷
因此最好能多比較不同 ML Algorithms 的 **執行結果** 與 **效能**
再依據要處理的問題，選擇較佳的 ML Algorithm(s)

### 3.2 選擇分類器模型/演算法

**1. 影響分類結果的要素**
| 要素種類 | 要素 |
| -------- | -------- |
| data | 輸入特徵數量、特徵種類 |
| data | 訓練樣本數 |
| model | 模型的成本（假設前提、訓練時間） |

Explanation:
* **要素(1)：輸入特徵數量、特徵種類**
輸入特徵 與 預期輸出（標籤/分類/category） 需具有高相關性
特徵數量 太少 => 可能造成預測不夠準確
特徵數量 太多 => 可能造成預測太夠準確，以致於無法泛化到（訓練資料外的）其它資料
* **要素(2)：訓練樣本數**
訓練樣本太少 => optimization method 可能無法收斂到理想的位置
* **要素(3)：模型的成本 — 假設前提**
分類模型 通常具有一些 假設前提（assumptions）
如： **Linear separability 線性可分**
假設前提
e.g., 在第 2 節的 practices: perceptron, Adaline 中
因採用特徵（X:花萼長度, Y: 花瓣長度）與 [鳶尾花資料集](https://archive.ics.uci.edu/ml/datasets/iris) 繪製成散佈圖後大致呈 **線性可分**
故在給予 二元線性分類模型 適當的 學習率（learning rate） 和 訓練次數（epochs）之下
預期、實際測試都可以得到可接受的分類結果（i.e., decision regions & losses/costs）
> 但倘若訓練資料繪製成散佈圖後，兩維度對應的大多數資料點並非呈線性
> （在分類問題中，即：預期難以對標為正、負類的 2 組資料找出一條合適的 **線性** 決策邊界）
> 則意味者這批資料在我們選定的特徵下，違反線性分類模型對線性的假設
> 那麼線性分類模型可能就不太適合應用在這類資料的分類任務
> examples:
> 
> ◦ 左圖：預期的決策邊界大致呈一個圈圈
> ◦ 右圖：預期的決策邊界大致呈一個曲線，而非直線
> 若欲對左圖或右圖做分類器，用線性二分類模型想必都不容易 fitting（擬合/配適）得夠好

**2. 訓練 ML 演算法的幾個步驟**
* (1) 置備資料集：選擇「特徵」、蒐集資料
* (2) 選擇 評估方法：選擇「效能指標」（performence metrics）
* (3) 選擇 ML 模型/演算法、最佳化方法（optimization method(s)）
* (4) 評估模型效能
* (5) 調校 ML 模型/演算法

### 3.3 再次實作 perceptron (透過 scikit-learn)
[ML_practices/practice_03_Classifiers_with_scikit_learn](https://github.com/dada00321/ML_practices/tree/master/practice_03_Classifiers_with_scikit_learn)

**實際效果**
decision regions

**觀察**
* Versicolor Iris 的其中 1 個測試樣本，錯誤分類到了 Setosa Iris 所屬的紅色區域
* Virginca Iris 的其中 4 個非測試樣本，錯誤分類到了 Versicolor Iris 所屬的藍色區域
* Setosa Iris 各樣本距離決策邊界不夠遠，容易將 Setosa 的 outlier(s) 錯誤分類為 Versicolor
* 期望的更佳決策邊界：最好能讓 Versicolor 與 Virginca 之間決策邊界的斜率更低（呈負斜率）

**參考書籍作者對 perceptron 的詮釋**
若欲處理的 dataset 難以完美地做線性分類
（樣本間至少存在少許 overlap(s) / not **linear separability**）
則：對此 dataset 用 perceptron 訓練，模型將難以收斂

### 3.4 利用 Logistic regression 對類別機率塑模
**1. Odds ratio**
又稱 OR、發生比、勝算比
*odds ratio* = *p* / (1 - *p*)
*p*: 正事件的發生機率
（正事件: 二元分類問題中，觀察者較有興趣的事件）

**2. Logit function**
* domin: (0, 1)
* range: R ≡ (-∞, ∞)
* 定義為「對數勝算比」，即：log (*odds ratio*)
log = log_e，為自然對數
* 可以把一定義域為 (0, 1) 的機率值映射到實數域

**3. Logistic function**
* domin: R ≡ (-∞, ∞)
* range: (0, 1)
* 為 logit function 的反函數
* 可以把一實數值映射到此函數的值域 (0, 1)
* 因為曲線形狀長得像 "S"，又稱 sigmoid function

**4. logistic regression 在 ML 中的應用**
因為已知
(1) 輸入特徵矩陣 X
(2) 初始權重 W
(3) 由 (1), (2) 可計算得 net input: Z
並希望設計一個 activation function
已將 Z 轉換到 **二元分類** 的輸出

而透過 logistic function 作為 activation function
可以將分佈於任意實數的 net input: Z
經由此函數，轉換為輸出分佈於 (0, 1) 的值
進而預測：**（給定特徵後）某特定樣本** 屬於 **某特定類別** 的機率

e.g.,
定義: 0 為負類，1 為正類

1. **sigmoid function**
○ 1 ＞*ϕ*(z) **≧ 0.5** if **z ≧ 0**
○ 0.5 ＞*ϕ*(z) ＞ 0 if z ＜ 0
2. **threshold function**
○ **ŷ = 1** if *ϕ*(z) **≧ 0.5**
○ ŷ = 0 if *ϕ*(z) ＜ 0.5
3. **sigmoid function + threshold function**
○ ŷ = 1 if **z ≧ 0**（預測為正類）
○ ŷ = 0 if **z ＜ 0**（預測為負類）

**5. logistic regression 的假設 [1]**
1. 觀察事件必須是「二分的」(dichotomous)
正事件（正類） 與 負事件（負類） 必須是樣本事件的 partition
2. 資料（樣本）中沒有離群值
3. predictors 之間不存在高度相關（多重共線性）
> (2) 可先對連續型的輸入特徵（predictors 的實現值）做 **z-score 標準化**
> 並將 [-3.29, 3.29] 區間外的離群值所對應的樣本予以剔除
>
> (3) 可藉由相關性矩陣（correlation matrix）評估：predictors 之間是否存在多重共線性

**6. 從 logit function 到 logistic function 的簡單推導**
Let y = *logit* (*p*) = log_e (*p* / (1 - *p*))
取 e, 得:
*e*^y = *p* / (1 - *p*)
1 + *e*^y = 1 / (1 - *p*)
取倒數, 得:
1 / (1 + *e*^y) = 1 - *p*
*p* = 1 - 1 / (1 + *e*^y) = *e*^y / (*e*^y + 1) = 1 / (1 + e^(-y))
得: logistic(x) = 1 / (1 + e^(-x))

**7. 以程式簡單驗證 logit function 與 logistic function**
**logit function**
1. 首先，定義好 logit function
並分別帶入臨界值 0 和 1
logit function 的定義域不含 0 和 1
而實測結果也因 Python 避免 overflow 而拋出例外錯誤

2. 用接近 0 的浮點數代入 logit function
回傳值為負實數（浮點數），與預期結果相同

3. 用接近 1 的浮點數代入 logit function
回傳值為正實數（浮點數），與預期結果相同
**Logistic function**
定義 ｌogistic function，並分別代入正無限大、負無限大
回傳結果分別為 1.0 和 0.0，與預期結果相同

### 3.5 比較 logistic regression 與 perceptron, adaline


| 特性＼模型 | Perceptron | Adaline | Logistic regression |
| -------- | -------- | -------- | -------- |
| net input func. 後的函數數量 | 1 | 2 | 2 |
| 有無 activation func. | 無 | 有 | 有 |
| activation func.| ✖ | identical / linear | sigmoid |
| 權重更新方式 | 直接更新 | GD/SGD/... | GD/SGD/... |

**logistic regression 的優勢**
在輸入 threshold func. 之前
sigmoid func. 的輸出為介於 0 ~ 1 的連續值，而非離散型的 0 或 1
可用來表示「某樣本給定特徵之下，預測為某類的機率」
故在天氣預報、醫學，乃至各種欲得知分類 **發生機率** 的應用上
時常以 logistic function 輔助研究

example [2]:

### 3.6 logistic regression 的 loss/cost function
**Review: Adaline 的 loss/cost function**
*J*(w) = 1/2 SSE = 1/2 Σ_i (*ϕ*(z_i) - y_i)^2

**Logistic 的 loss/cost function**
利用 M.L.E.(Maximum Likelihood Estimation)
1. 定義：
***maximize***: *L*(w) = *P*(y|x ; w) = **π_i** *P*(y_i|x_i ; w) = π_i *ϕ*(z_i)^(y_i) * (1 - *ϕ*(z_i))^(1- y_i)
2. 取自然對數：
***maximize***: *l*(w) = log_e *L*(w) = **Σ_i** [ y_i log_e (*ϕ*(z_i)) + (1- y_i) log_e (1 - *ϕ*(z_i)) ]
3. 改寫 *l*(w) 為「**最小化** 目標函數」：
***minimize*: *J*(w) = -*l*(w) = Σ_i [ - y_i log_e (*ϕ*(z_i)) - (1- y_i) log_e (1 - *ϕ*(z_i)) ]**
即 logistic regression 的 loss/cost function
> *L*(w): likelihood function 概似函數
> π_i: 各樣本 i 的連乘積

**單一訓練樣本的 loss/cost 計算**
***J*(*ϕ*(z), y ; w) = -y log_e (*ϕ*(z)) - (1- y) log_e (1 - *ϕ*(z))**
(I) 當 y = 1（正類）
　　*J*(*ϕ*(z), y ; w) = -log_e (*ϕ*(z))
(II) 當 y = 0（負類）
　　*J*(*ϕ*(z), y ; w) = -log_e (1 - *ϕ*(z))

### 3.7 實作 logistic regression (透過 scikit-learn)
[ML_practices/practice_03_Classifiers_with_scikit_learn](https://github.com/dada00321/ML_practices/tree/master/practice_03_Classifiers_with_scikit_learn)

**實際效果**
decision regions

**觀察**
* Setosa Iris 全部樣本皆分佈於 Setosa Iris 的 decision region
* 3 個 Virginca Iris 樣本（其中 1 個為測試樣本）錯誤分類到 Versicolor Iris 的 decision region
* 2 個 Versicolor Iris 樣本（皆為訓練樣本）錯誤分類到 Virginca Iris 的 decision region
* Setosa Iris 各樣本距離決策邊界足夠遠，不容易將 Setosa 的 outlier(s) 錯誤分類為 Versicolor
* 就結果而言，logistic regression 具有相較於 [perceptron](https://hackmd.io/qmk-_lAFTH6qQN305AZPcQ?view#33-%E5%86%8D%E6%AC%A1%E5%AF%A6%E4%BD%9C-perceptron-%E9%80%8F%E9%81%8E-scikit-learn) 更理想的 **線性分類能力**
* 只能求出 **線性的** decision boundaries：無法正確區分 Versicolor 與 Virginca 的 outliers

### 3.8 以正規化處理 Overfitting

**1. 何謂 Overfitting**
| | Underfitting | Overfitting |
| -------- | -------- | -------- |
| Model Complexity | Low | High |
| Disadvantage | High **bias** | High **variance** |


* 一般而言，高變異 與 Overfitting 成正比，高偏誤 與 Underfitting 成正比
* 偏誤（bias）: 系統性、非隨機性、模型中可解釋的部分。
* 變異（variance）: 包含隨機性、波動性、模型中難以解釋的部分。
* 變異 可用來衡量模型「預測能力」的「**一致性（consistency）**」
* 若一模型具有低變異，可宣稱模型對訓練資料的「**隨機性（randomness）**」反應良好

**The bias-variance tradeoff**
若模型與訓練資料 fitting 得太差（Underfitting）
因模型的偏誤太高
訓練資料、測試資料（沒看過的新資料）皆無法精準預測
反之，若模型與訓練資料 fitting 得太好（Overfitting）
模型在訓練資料上的預測能力遠勝於非訓練資料的預測能力
即：模型的泛化能力（generalization ability）會變差
> 延伸閱讀 [3]
> [機器學習-Bias-Variance Tradeoff](https://dasanlin888.pixnet.net/blog/post/469515653-%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-bias-variance-tradeoff)

**2. 正規化（Regularization）**
* 在 bias 和 variance 取平衡的方法之一
* 可以處理輸入特徵間的 **共線性（collinearity）** 問題
* 可以過濾資料中得雜訊（noise），進而避免 Overfitting

**正規化 的設計理念**
Overfitting 往往因為訓練樣本中存在的 outlier(s)
導致模型過於靈敏地捕捉這些 outlier(s)
使得：對訓練集而言 (1) low bias (2) high variance
而正規化的理念在於：「藉由提升模型 bias，以降低模型過高的 variance」
故引入「懲罰項」（可視為一種特徵），以懲罰極端樣本過高的權重更新增量

**L2 regularization**
> *λ*: 正規化參數
> L2 regularization，又稱 weight decay，可避免模型 overfitting

**成本函數中加入 L2 正規化項**
minimize: J(w) = -l(w) = Σ_i [ - y_i log_e (ϕ(z_i)) - (1- y_i) log_e (1 - ϕ(z_i)) ] + ***λ*/2 Σ_j w_j^2**

**scilit-learn 的參數 C**
3.7 小節以 scilit-learn 實作 logistic regression 分類器
其中設定參數 C = 100.0
參數 C 為 L2 正規化項: *λ* 的倒數（又稱 inverse regularization parameter）
若將參數 C 設定得越低，則 *λ* 越高，正規化強度越高

如上圖所示
將 logistic regression 的參數 C 分別設為 10^-4 ~ 10^4 並用 matplotlib 繪製
可觀察到：
1. 當參數 C 較大，L2 正規化項較低，意味著正規化強度較弱
使得兩輸入特徵 fit 出的 **權重估計係數** 趨於發散
2. 反之，將參數 C 設定得較小，正規化強度較強，
使得兩輸入特徵 fit 出的 **權重估計係數** 趨於收斂

### 3.9 SVM: 最大化分類的決策邊界
* Support Vector Machine （支援向量機）
* 可視為 perceptron 的延伸
* perceptron 的目標是 **減少 misclassification 的發生（最小化 loss）**
而 SVM 的目標是 **最大化 邊界（margin）**

**SVM 的直觀理解**


**使用閒置變數處理非線性分類**
1. **原本: 線性約束（linear constraint）**
=> 可處理 線性可分 的資料
=> 但難以處理 非線性 資料
2. **SVM + 閒置變數（slack variable, ξ）**
=> 由 Vladimir Vapnik 於 1995 提出
=> **軟邊界分類 / soft-margin classification**
=> 動機：適當「成本懲罰」下，使 線性約束 略為「鬆弛」，以配適非線性資料
=> （使 nonlinear separable 的資料收斂（converge））

解釋：
* 參數 C：可控制 **錯誤分類** 的 **成本懲罰（cost penalization）** 程度
* **成本懲罰偏高**
即：將參數 C 的數值設定地得較大
會使得 (1) bias 小，variance 大
　　　 (2) 訓練資料 loss 小，即便存在 outlier 亦可捕捉
　　　 (3) 難以處理非線性資料
　　　 (4) 正規化強度較弱
> 統計量（估計式）的評估：
> 模型具有較佳的 **無偏性（unbiasedness）**
> 模型具有較差的 **有效性（efficiency）**
> 模型較難滿足 **變異齊一性（equal variance）** 的假設（assumption）

* **成本懲罰偏低**
即：將參數 C 的數值設定地得較小
會使得 (1) bias 大，variance 小
　　　 (2) 若訓練資料存在 outlier，未必可良好捕捉
　　　 (3) 較容易處理非線性資料
　　　 (4) 正規化強度較強
> 統計量（估計式）的評估：
> 模型具有較差的 **無偏性（unbiasedness）**
> 模型具有較佳的 **有效性（efficiency）**
> 模型較容易滿足 **變異齊一性（equal variance）** 的假設（assumption）

* **藉由改變參數 C 數值，可對 bias-variance balance 做調校**

### 3.10 實作 Linear SVM (透過 scikit-learn)
[ML_practices/practice_03_Classifiers_with_scikit_learn](https://github.com/dada00321/ML_practices/tree/master/practice_03_Classifiers_with_scikit_learn)
實際效果
decision regions

### 3.11 kenerel SVM 處理非線性資料
**模擬一批分線性（XOR）資料**
[ML_practices/practice_03_Classifiers_with_scikit_learn](https://github.com/dada00321/ML_practices/tree/master/practice_03_Classifiers_with_scikit_learn)
這批資料非 linear separability
故先前的 perceptron, Adaline, logistic regression, linear SVM 皆無法有效處理
（這些 linear model 只能配適出一 linear hyperplane）

**kernel SVM**
* 想法
1. 產生 **非線性組合（nonlinear combination）**
2. 藉由 **mapping function: *ϕ*(•)** 將原特徵投影（project）到更高維的空間中
而假設資料在高維空間中為線性可分
則在高維空間（利用 linear SVM）做出分離不同類資料的 **線性超平面**
3. 將高維空間的 線性超平面 再 **投影** 回原始特徵空間，成為一 **非線性** 的 **決策邊界**

* 示意圖

* Example of mapping function

**kernel function**
kernel SVM 想法雖簡單，但會面臨一個問題：
訓練樣本轉換到高維空間需要 **建構新特徵**
而此過程相當消耗計算資源
（訓練資料本身已是高維資料，則影響更鉅）
* 解決方式：**核技巧（kernel trick）**
將計算高維（新）向量內積的必要步驟：
把原本的 x_i • x_j 替換為 ***ϕ*(x_i) • *ϕ*(x_j)**
包裝成 **kernel function**：
**Κ(x_i, x_j) = *ϕ*(x_i) • *ϕ*(x_j)**
以利節省一些計算資源
* 被廣泛使用的 kernel: **RBF kernel 與 Gaussian kernel**
(1) RBF kernel: Radial Basis Function kernel 弳向基底函數核
(2) Gaussian kernel: 高斯核

**kernel 的意義**
核（kernel）：**成對樣本** 間的 **相似度函數**，其值落在 0 ~ 1 之間（0: 完全不相似，1: 完全相似）

### 3.12 實作 Kernel SVM (透過 scikit-learn)
[ML_practices/practice_03_Classifiers_with_scikit_learn](https://github.com/dada00321/ML_practices/tree/master/practice_03_Classifiers_with_scikit_learn)
* 實際效果
decision regions
Step 1. 先模擬一批隨機資料
Step 2. 再利用 kernel SVM（C=10.0） 配適出 nonlinear decision boundary

* **參數 Gamma 對 RBF kernel SVM 的意義**
如 [3.11 小節](https://hackmd.io/qmk-_lAFTH6qQN305AZPcQ?view#311-kenerel-SVM-%E8%99%95%E7%90%86%E9%9D%9E%E7%B7%9A%E6%80%A7%E8%B3%87%E6%96%99) > **kernel function** > **RBF kernel** 所提及
-1/2σ^2 可寫為 Γ，即 Γ = -1/2σ^2，為「自由參數」（free parameter）
Γ 可被解釋為：高斯球（Gaussian sphere）的截斷參數（cut-off parameter）

增加 Γ 數值，會使得：決策邊界更加「緊 且 顛簸」（tight and bumpier）
> Γ 過大 => 訓練資料集：分類良好，未知資料：generalization error 偏高
> 優化 Γ 的過程，與模型是否 overfitting 關係密切

### 3.13 決策樹
* Decision Tree (Classifier)
* 可提供良好的 **可解釋性（interpretability）**
* 模式：
藉由學習一系列的問題
依序對原始資料做分割
依此推斷樣本所屬的類別標籤（做出決策）
* 特性
1. 決策數常用但不限於依 **名目變數** 做分類
e.g. 「週六出去玩」?
特徵的值若為實數，仍可用決策樹做分類
e.g. 「花萼寬 ≧ **2.8** cm」?
P.S. 名目變數: 名目尺度的隨機變數
2. IG (Information Gain, 資訊增益)
*rough concept:*
從 根節點(root node) 開始
決策樹模型 依照特徵值將資料分割到不同邊
使之可得到較大的 資訊增益
並反覆/迭代地持續 分割 的流程
直到得到 葉節點(leaf node) 為止
=> 葉節點 的所有樣本皆同屬於一個類別
3. 注意事項
實務上，很可能做出一個又大又深的決策樹
導致 Overfitting，需多留意
=> 藉由 **限定樹的高度** 可預防此情況
* 種類
- 1. 分類決策樹: 用於 離散型變數，如: ID3, C4.5, CART
- 2. 迴歸決策樹: 用於 連續型變數，如: C4.5, CART

**3.13.1 最大化 Information Gain**
(Ⅰ) 想法:
為了在節點上，使用 **最具意義的特徵** 作為分割依據
需先定義一 objective function (目標函數)

(Ⅱ) 決策數的 objective function:
“maximize: **Information Gain** of each split operation”
*I*: Impurity measure (不純度)
一個隨機選中的樣本在子集中被 **分錯** 的可能性
又稱 splitting criteria (分割條件)
Impurity 可為以下幾種
=> 1. Gini impurity (吉尼不純度)
=> 2. Entropy (熵)
=> 3. Classification error rate (分類錯誤率)

(Ⅲ) 特色
決策樹 **不需對輸入特徵做正規化**

> **Q: Why "tree-based algorithm" don't need to do "feature scaling"?**
> ref: [Feature Scaling](https://www.analyticsvidhya.com/blog/2020/04/feature-scaling-machine-learning-normalization-standardization/) --> Subsection: "***Tree-Based Algorithms***"
> A:
> Decision tree is only splitting a node **based on a single feature**.
> The decision tree splits a node on a feature that increases the homogeneity of the node.
> **This split on a feature is not influenced by other features.**

**3.13.2 說明**
最大化 資訊增益 IG
即: 最小化 所有子節點**不純度**的總和
(若為 2 分支: D_left & D_right，但分支節點數不限於 2)

**3.13.3 意義**
不純度: 是衡量資料不確定性(entropy)或隨機性的估計式
利用決策樹對父節點的資料做 **分割**
旨在找出幾個彼此互斥(disjoint)的子集合
使得:
1)當樣本資料屬於不同類別的機率極度不均勻，如:皆屬於同一類別
此估計式有最大的 "所有子集不純度總和"
2)當樣本資料屬於不同類別的機率服從均勻分佈，如:屬於各類別的機率均等
此估計式有最小的 "所有子集不純度總和"

當利用特徵 f 對父資料集 D_p 做分割
所得之 IG (=> IG(D_p, f)) 越大，說明:
「特徵 f 解釋能力強，能為分類模型帶來較多資訊
(特徵 f 攜帶的信息量較大，或稱特徵 f 的「特徵權重」較大)」

有可能，但不足以說明:
「分割後的 **所有子資料集的不確定性總和** 較低，較無法再為分類模型提供有用資訊」
因為: **父集:各子集 樣本數的比值**、**父集的不純度** 也會影響 IG

**3.13.4 再看 Impurity measure**
1. Entropy (熵)
**I_H(t) = -Σ_i P(i|t) log_2 P(i|t)**
P(i|t): 節點 t 上「樣本屬於類別 i」的機率
若一節點「所有樣本皆屬於同一類別」，則 entropy = I_H = 0 為最小，表示分類最完全
若一節點「樣本屬於各類別的機率均等(呈均勻分布)」，則 entropy = I_H = 1 為最大，表示分類最不完全

2. Gini impurity (吉尼不純度)
**I_G(t) = 1 - Σ_i P(i,t)^2**
可解釋為: 最小化錯誤分類機率的準則
若存在完美的混雜(節點上樣本屬於各類別的機率均等)，則有最大的 Gini impurity: 1 - Σ_[i=1 to 2](0.5)^2 = 0.5

3. Classification error rate (分類錯誤率)
**I_E(t) = 1 - max｛P(i|t)｝**

**3.13.5 Example**
假設有 2 結構相同的二元決策數
(x, y) 表示在節點上某樣本屬於類別 1 的機率為 x，屬於類別 2 的機率為 y
可由 (1) Entropy (2) Gini impurity (3) Classification error rate
計算 2 種決策樹情形各自的 Information Gain:

(可先在每個節點註記 屬於各類別的機率 及 樣本數)
**(1) Entropy**
**I_H(t) = -Σ_i P(i|t) log_2 P(i|t)**
case A:
I_H(D_p) = -(0.5 log_2(0.5) + 0.5 log_2(0.5)) = -(-1/2 * 2) = 1
I_H(D_left) = -(3/4 * log_2(3/4) + 1/4 * log_2(1/4)) ~= 0.8113
I_H(D_right) = -(1/4 * log_2(1/4) + 3/4 * log_2(3/4)) ~= 0.8113
→ **IG_H(D_p, f)** = 1 - [40/80 * 0.8113 + 40/80 * 0.8113] **~= 0.1887**

case B:
I_H(D_p) = -(0.5 log_2(0.5) + 0.5 log_2(0.5)) = -(-1/2 * 2) = 1
I_H(D_left) = -(1/3 * log_2(1/3) + 2/3 * log_2(2/3)) ~= 0.9183
I_H(D_right) = -(1 * log_2(1) + ~~0 * log_2(0)~~) ~= 0
→ **IG_H(D_p, f)** = 1 - [60/80 * 0.9183 + 20/80 * 0] **~= 0.3113**

∵ Information gain of case B (0.3113) is greater than case A's (0.1887)
∴ Choose case B

**(2) Gini impurity**
**I_G(t) = 1 - Σ_i P(i,t)^2**
case A:
I_G(D_p) = 1 - (0.5^2 + 0.5^2) = 0.5
I_G(D_left) = 1 - ((3/4)^2 + (1/4)^2) = 0.375
I_G(D_right) = 1 - ((1/4)^2 + (3/4)^2) = 0.375
→ **IG_G(D_p, f)** = 0.5 - [40/80 * 0.375 + 40/80 * 0.375] **~= 0.125**

case B:
I_G(D_p) = 1 - (0.5^2 + 0.5^2) = 0.5
I_G(D_left) = 1 - ((1/3)^2 + (2/3)^2) = 0.4444...
I_G(D_right) = 1 - (1^2 + 0^2) = 0
→ **IG_G(D_p, f)** = 0.5 - [60/80 * 0.4444... + 20/80 * 0] **~= 0.1667**

∵ Information gain of case B (0.1667) is greater than case A's (0.125)
∴ Choose case B

**(3) Classification error rate**
**I_E(t) = 1 - max｛P(i|t)｝**
case A:
I_E(D_p) = 1 - 0.5 = 0.5
I_E(D_left) = 1 - 3/4 = 1/4
I_E(D_right) = 1 - 3/4 = 1/4
→ **IG_E(D_p, f)** = 0.5 - [40/80 * 0.25 + 40/80 * 0.25] **~= 0.25**

case B:
I_E(D_p) = 1 - 0.5 = 0.5
I_E(D_left) = 1 - 2/3 = 1/3
I_E(D_right) = 1 - 1 = 0
→ **IG_E(D_p, f)** = 0.5 - [60/80 * (1/3) + 20/80 * 0] **~= 0.25**

∵ Information gain of case B (0.25) is equal to case A's (0.25)
∴ Choose both of A and B

**3.13.6 視覺化 impurity**
假設僅有 2 種類別: 類別 1 及 類別 2
x-axis 為 節點上樣本屬於類別 1 的機率
- 當此機率值趨近於 0 或趨近於 1，impurity 趨近於 0，表示不純度(不確定性)極低
- 當此機率值趨近於 0.5，impurity 趨近於估計式的最大值，表示不純度(不確定性)極高

### 3.14 實作決策樹
**3.14.1 手工搭建一個簡易決策樹**
[ML_practices/decision_tree](https://github.com/dada00321/ML_practices/blob/master/practice_03_Classifiers_with_scikit_learn/decision_tree.py)

**整體流程**
1. load_data: 載入所有訓練樣本的 (1)各維度特徵 (2)標籤 (視需要加上預處理)
2. create_tree: (**核心**) 建立決策樹 (回傳值: dict or JSON-like data)
3. list_combinations: 列出所有可能的組合 (組合: 決策樹節點訪問的路徑，具先後順序關係)
4. predict: 由 create_tree() 產生的決策樹，對特定新資料 (一組任意特徵向量) 作預測

**核心細節: create_tree()**
※ create_tree function 主要用到 recursion，藉由每次迭代計算出最佳特徵以分割當前資料
直到 所有特徵皆用罄 或 所有標籤皆相同 方傳回最終標籤 (此標籤即為某一連串節點組合的葉節點)

- Recursion 終止條件 1: All labels are same
- Recursion 終止條件 2: All features were be used

- Step 1. Define formula of impurity
impurity(不純度) 可為 **shannon entropy** (香農熵)
也可為 gini impurity 或 classification error impurity
=> 無論採用何者，需先定義出計算 impurity 的 function(s)

- Step 2. Find the "best feature" ("feature to split") within current data
每一次 recursion 的迭代，找最好 (具有最高 Information Gain) 的特徵
此步驟需計算父節點的不純度 *Ⅰ*(D_p) // 只需計算一次，重複使用
並依序對各維度特徵，計算單一維度特徵「各個可能特徵值」的多個 *Ⅰ*(D_child)
再加總得 Σ_i *Ⅰ*(D_child)_i
最後由 **父節點不純度** 與 **各子節點不純度總和** 相減得: **IG** ( Information Gain)
表示特定(單一維度)特徵值在當前節點上可提供給分類模型的資訊增益
該特徵的資訊增益越大，表示當前資料經此特徵分割後有較小的不確定性，即分割得較完全
=> 經各維度特徵求算得 IGs 的比較，具最大 IG 者即為本次迭代的 **最佳特徵** (用於後續分割資料)

- Step 3. Form up the decision tree
3a. 先由 最佳特徵 取: **特徵原始名稱**，依此建立 decision tree 的 key
並以 dict (key-value pair) 作為對應此 key 的 value

3b. 再由 最佳特徵 的 所有可能特徵值，依序 (loop) 作為上述子 dict 的 key

3c. 最後在每一次的 loop 迭代
萃取出「**特徵 = 某特定特徵值**」的資料，並對資料移除此特徵(欄)，作為「分割後資料」
再將「分割後資料」作為 輸入參數: data，呼叫自身 function 以實現 recursion

**實際效果**
**Ⅰ. 舉辦活動與否的決策樹 [手工建立的決策樹, impurity: entropy]**
說明: 根據 12 筆過往資料，包含天氣、溫度、濕度、風速 4 個已記錄特徵
每筆記錄也包含「是否舉辦會議」已記錄標籤，標籤可能值共 2 種: yes, no
根據歷史記錄，產出一決策樹，使其能列出不同循序式條件下「是否舉辦會議」的預測結果
- **dataset**

- **Create a decision tree and list all combinations**

- **Predict for a specific, new record with features: (1,1,1,0)**
> The predicted value (prediction) is "yes"
depends on one of combinations “[濕度=1] => [天氣=1] => [yes]”

**Ⅱ. 用來分類三種鳶尾花的決策樹 [Scikit-learn 決策樹, impurity: Gini]**
說明: 鳶尾花資料與先前章節相同，特徵採 2 維度: petal length (cm), petal width (cm)
標籤可能值共 3 種: Setosa, Versicolor, Virginica

- **dataset**
**特徵 (*X*, 僅部分資料)**

**標籤 (*Y*)**

- **分類結果**

- **決策樹圖**

[**小實驗: 改變決策樹的層數**]
- 將決策樹的層樹依序設定為 1 ~ 8 層並產出結果

- **decision boundaries**

- **decision tree (graph)**

- 觀察
當設定層數=1，係扣除根節點外之層數=1
從結果可觀察出：
1. 當設定 層數=1 ~ 層數=6
扣除根節點外之層數分別為 1層 ~ 6層
2. 當設定 層數=7 ~ 層數=8
扣除根節點外之層數皆保持在6層
=> 可能原因:
impurity 在 層數=6 時
剩餘的 5 個葉節點之中僅 1 個葉節點 impurity > 0
其它葉節點的 impurities 皆為 0.0
impurity = 0 的葉節點佔 80%，說明此時的分割已趨於完全
而每一輪分割會找出本輪最佳特徵，對現有資料再分割
**猜測**: 層數=6 時，**所有特徵皆已用罄**
才會使得在 層數未達上限 且 仍存在一葉節點 impurity > 0 之條件下
仍無法再對 impurity > 0 的葉節點進行分割並使該節點向下延伸

### 3.15 隨機森林: 結合多個決策樹
**前言**
2021 之前的十多年間，ensemble (整體) 方法在 ML 領域備受矚目
ensemble 分類效能高，且在 overfitting 問題的表現也具有相當的 robustness (穩固性)
例如: bagging (裝袋法)、boosting (強化法) 皆屬於常見的 ensemble 方法

**Random Forest Algorithm 隨機森林演算法**
Concept: 隨機森林 透過結合多個(苦於)高變異的 決策樹
將各決策樹的估算結果作平均，共同塑造出一個較 robust 的模型
因「平均」的流程能使此模型 **降低「一般化誤差」**
故此模型較不易發生 overfitting

**Steps of Random Forest**
1. 定義樣本數為 n 的隨機 **自助(bootstrap)** 樣本 // 取出放回 (with replacement)
2. 從 **自助(bootstrap)** 樣本導出決策樹
對每個節點:
a. 隨機選取 d 個特徵 // 取出不放回 (without replacement)
b. 使用特徵依序分割該節點
=> 依據 objective function 找出的最佳方式作分割
(e.g., Maximize: Information Gain )
3. 重複 k 次步驟 1 ~ 2 // 產生 k 個 decision trees
4. 匯總所有決策樹的預測，以 **多數決(majorority voting)** 選出類別標籤
> Ref:「多數決」方法 refers to Ch 7

**隨機森林的優點與缺點 (與決策樹相比)**
[優點] 選擇超參數較容易，**不須額外修剪(pruning)**
> Q: 為何隨機森林「不須額外修剪(pruning)」
> A: 透過 ensemble，模型具有良好的 robustness
> 個別決策樹的雜訊不會影響整體結果
> 主要需考慮的要素為 Step 3 中 k 的數值

[缺點] **可解釋性** 不如決策樹

**k 值的取捨: 決策樹越多越好嗎?**
一般而言，k 值越大(決策樹越多)，隨機森林分類器的效能越好
但其代價是: 計算成本(運行時間)會增加

**其它實務上較少見的超參數**
1. Bootstrap (自助法) 樣本數 **n**
- 藉由調整 n ，可以控制隨機森林的 bias-variance tradeoff，並可試圖取得平衡
- 一般而言，ML 套件實作多把 n 設為 num. of training dataset
> 當 n 越小，好處有二: (1) 降低 overfitting 影響 (2) 增加個別 decision tree 隨機性
> 壞處是: 可能使得 隨機森林分類器 整體效能變差 (bias 增加)
> 導致以上現象的箇中原因是: 當 n 變小， Bootstrap 樣本包含特定訓練樣本的機率較低
> 自然較不容易使 model 過度配適 training data
> 換言之，當 n 過小，亦有可能導致模型 underfitting training data

2. 每個節點隨機選取的特徵數量 **d**
- 一般而言，ML 套件實作多把 d 設為 sqrt(m)，m 是 training set 的特徵數目

### 3.16 實作隨機森林
[ML_practices/random_forest](https://github.com/dada00321/ML_practices/blob/master/practice_03_Classifiers_with_scikit_learn/sklearn_random_forest.py)
- 實際效果
鳶尾花資料集 - decision regions [impurity: **entropy**]

### 3.17 KNN (K-Nearest-Neighbors)
KNN 是一種 **惰式學習器 (lazy learner)**
它不會從訓練資料集中，學習出 **判別函數 (descriminative function)**
而是藉由直接「記憶」訓練資料集，達到分類的效果

> 1. 有母數 (parametric) 模型
> e.g., Perceptron (感知器), Logistic regression (邏輯斯迴歸)
> linear SVM (線性支援向量機)
> **藉由設立初始假設 (hypothesis)**
> 即: 給定初始 Cost Function: J(*Θ*)
> (及 input neurons, weight vector, method of weight update,
> initial learning rate, num. of epochs 等超參數)
> **並對訓練樣本的原始母體參數做估計 (estimation)**
> 即: 利用樣本資料，在每一輪訓練中更新權重向量，持續修正原始假設
> (每次的權重更新，預期得到一組使 cost 更小的新權重向量；
> 直到 cost 不減反增 / overfitting)
> **最終可學習出一個 判別函數 (descriminative function)**
> => 而其在給定訓練樣本資料前，就可依原始假設做簡易分類
> 　　
> 2. 無母數 (non-parametric) 模型
> e.g., kernel SVM (核技巧-支援向量機 | 用於解決非線性資料的分類問題),
> decision tree (決策樹), random forest (隨機森林), KNN (K-最近鄰)
> 其中 KNN 為一種「基於實例學習 (instance-based learning)」的分類器
> 所謂 lazy learner 屬於 instance-based learning 的特例
> 藉由 **記憶** 實例 (實際樣本) 的方式達到學習「分類」的能力
>
> 3. KNN 的優點:
> - 蒐集 新訓練實例 的同時，分類器也同步被更新
> - 不需先擬定 hypothesis
>
> 4. KNN 的缺點:
> - 在 worse case 下，計算複雜度 (computational complexity) 會隨 訓練樣本數 線性增加
> - Memory-based model 樣本不可被丟棄，故當 訓練樣本數 很大，需考慮儲存空間的問題
>
> 5. 避免 KNN 計算複雜度 隨 訓練樣本數 線性增加的方法
> (1) KNN 特徵數目極少
> (2) 實作高效能的資料結構
> e.g., KD-tree
> Ref: 《An Algorithm for Finding Best Matches in Logarithmic Expected Time》[4]

**Steps of KNN**
1. 選擇 K 值和一個 **距離度量 (distance metric)**
2. 找出 目標資料點 的 K 最近鄰
3. 以 **多數決(majority vote)** 方式指定類別標籤

**KNN 的平手問題**
1. 當 KNN 「多數決」產生多於 1 個結果 (投票平手)
會將目標(新)樣本的類別標籤指定為: 與 目標(新)樣本 間 distance 最短者
2. 若超過 1 個類別標籤 distance 最短且相同
會將目標(新)樣本的類別標籤指定為: 第一個找到的訓練樣本對應的類別標籤

**KNN 的 維數災難 (curse of dimensionality)**
需注意 KNN 很容易因「維數災難」造成 overfitting 現象
維數災難:「對一樣本大小固定的資料集，當特徵維數越多，特徵空間便越稀疏
換言之，在一高維度空間中，對一樣本點而言，即便最近的樣本，與該樣本點間的距離也過於遙遠
而無法利用 KNN 提供合理的估計

**避免維數災難**
Logistic regression 可透過 正規化(regulization) 避免 overfitting
但對於「無法利用正規化(regulization) 避免 overfitting 現象」的模型
如: decision tree, KNN
需透過「**特徵選擇**」或「**降維**」來避免「維數災難」
> Logistic regression 可透過 正規化(regulization) 避免 overfitting
> Ref: [3.8 以正規化處理 Overfitting](https://hackmd.io/qmk-_lAFTH6qQN305AZPcQ?view#38-%E4%BB%A5%E6%AD%A3%E8%A6%8F%E5%8C%96%E8%99%95%E7%90%86-Overfitting)

### 3.18 實作 KNN
[ML_practices/KNN](https://github.com/dada00321/ML_practices/blob/master/practice_03_Classifiers_with_scikit_learn/sklearn_KNN.py)
- 實際效果
鳶尾花資料集 - decision regions

- 注意事項
實作中，設定 metric="minkowski"，即指定以**明考斯基距離**作為 KNN 度量方式
需注意: 若選用**歐基里德距離**作為 KNN 度量方式，必須做特徵正規化
使各維度特徵能對「距離」做出同等程度的貢獻
Ref: [sklearn.neighbors.DistanceMetric](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.DistanceMetric.html)[5]

## 參考資料
[1] [Logistic Regression](https://www.statisticssolutions.com/free-resources/directory-of-statistical-analyses/what-is-logistic-regression/)

[2] [Logistic Regression for malignancy prediction in cancer](https://towardsdatascience.com/logistic-regression-for-malignancy-prediction-in-cancer-27b1a1960184)

[3] [機器學習-Bias-Variance Tradeoff](https://dasanlin888.pixnet.net/blog/post/469515653-%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-bias-variance-tradeoff)

[4] [An Algorithm for Finding Best Matches in Logarithmic Expected Time
ACM Transactions on Mathematical Software (TOMS), 3(3):209-226, 1977.](https://www.researchgate.net/publication/220493118_An_Algorithm_for_Finding_Best_Matches_in_Logarithmic_Expected_Time)

[5] [sklearn.neighbors.DistanceMetric](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.DistanceMetric.html)