Classification (II): Overfitting, Model Evaluation & Imbalanced Classes

1. Classification Errors

ExamSlide 4：

Error 類型	定義
Training errors（apparent errors）	Errors committed on the training set
Test errors	Errors committed on the test set
Generalization errors	Expected error of a model over random selection of records from same distribution（真正關心嘅嘢，只能估計）

1.1 Example Data Set (Slides 5–9)

Two-class problem：

• +：5400 instances——5000 個由中心 (10, 10) 嘅 Gaussian 產生，另加 400 個 noisy instances。
• o：5400 instances，由 uniform distribution 產生。
• 10% 用作 training，90% 用作 testing。

Slides 6–9 比較 nodes 數目唔同嘅 decision trees：4 nodes 嘅 tree boundary 好簡單；50 nodes 嘅 tree 喺 training data 上畫出好多細碎 boundaries（連 noise 都 fit 埋）。Slide 9 問："Which tree is better?"

2. Underfitting & Overfitting

Slide 10：As the model becomes more and more complex, test errors can start increasing even though training error may be decreasing.

Model complexity（例如 tree nodes 數）	Training error	Test error	狀態
好低（例如 1–4 nodes）	高	高	Underfitting
適中	中低	最低	Just right
好高（例如 50+ nodes）	極低（近 0）	上升	Overfitting

2.1 Impact of Training Data Size (Slides 11–12)

Using twice the number of data instances：Increasing the size of training data reduces the difference between training and testing errors at a given size of model. 即係同一個 50-node tree，用多一倍 training data 訓練，overfitting 會減輕（因為 noise 被更多真實 data「稀釋」）。

2.2 Notes on Overfitting (Slide 13)

• Overfitting results in decision trees that are more complex than necessary。
• Training error does not provide a good estimate of how well the tree will perform on previously unseen records。
• Need ways for estimating generalization errors。

3. Model Selection

Slide 14：Model selection 喺 model building 期間進行，目的係確保 model 唔會 overly complex（避免 overfitting）。要估計 generalization error，方法有：

• Using Validation Set
• Incorporating Model Complexity
• Estimating Statistical Bounds

3.1 Using Validation Set (Slide 15)

將 training data 再分兩部分：

• Training set：用嚟 model building。
• Validation set：用嚟估計 generalization error、tune model complexity 同 hyperparameters、model selection 等。

ExamNote: validation set is not the same as test set. Drawback：Less data available for training。

from sklearn.model_selection import train_test_split
X_tmp, X_test, y_tmp, y_test = train_test_split(X, y, test_size=0.2, random_state=0)
X_tr, X_val, y_tr, y_val = train_test_split(X_tmp, y_tmp, test_size=0.25, random_state=0)
# 用 (X_tr, X_val) 揀 max_depth；最後先用 X_test 報告一次

3.2 Incorporating Model Complexity (Slide 16)

Rationale：Occam's Razor——Given two models of similar generalization errors, one should prefer the simpler model over the more complex model. 因為 complex model 有更大機會係 accidentally fitted（碰啱 fit 中 noise）。所以評估 model 時應考慮 model complexity（細節 slide 標明 skipped）。

4. Model Evaluation: 三個問題

Slide 18 Purpose：To estimate performance of classifier on previously unseen data (test set)。

1. Metrics for Performance Evaluation：How to evaluate the performance of a model?
2. Methods for Performance Evaluation：How to obtain reliable estimates?
3. Methods for Model Comparison：How to compare the relative performance among competing models?

5. Metrics: Confusion Matrix & Accuracy

Slide 19：Focus on the predictive capability of a model（而唔係速度、scalability 等）。

5.1 Limitation of Accuracy (Slides 21, 44)

Exam2-class problem：Class 0 有 9990 個，Class 1 有 10 個。如果 model 將所有嘢預測為 class 0，$\text{accuracy} = 9990/10000 =$ 99.9%——但 model 一個 class 1 都偵測唔到，所以 accuracy 係 misleading。偵測 rare class 通常先係重點（frauds、intrusions、defects）。

6. Cost Matrix & Cost of Classification

Slides 22, 52：$C(i \mid j)$：Cost of misclassifying class $j$ example as class $i$（slide 22 記法，即 $C(\text{predicted} \mid \text{actual})$）。Slide 52 表格用 $C(\text{actual}, \text{predicted})$ 排列：行 = ACTUAL，列 = PREDICTED。

ACTUAL	PREDICTED
	Yes	No
Yes	$C(\text{Yes}, \text{Yes})$	$C(\text{Yes}, \text{No})$
No	$C(\text{No}, \text{Yes})$	$C(\text{No}, \text{No})$

總 cost = $\sum$（confusion matrix 每格 count × cost matrix 對應格 cost）。

Slide 24 "Cost vs Accuracy"：教科書指出如果 cost matrix 係對稱（$C(\text{Yes} \mid \text{No}) = C(\text{No} \mid \text{Yes}) = q$，$C(\text{Yes} \mid \text{Yes}) = C(\text{No} \mid \text{No}) = p$），咁 cost 同 accuracy 成線性關係，兩者排名一致；只有 cost 唔對稱時兩者先會分歧。

7. Precision, Recall, F-measure & 其他 Measures

Slide 25 Cost-Sensitive Measures：

• Precision is biased towards $C(\text{Yes} \mid \text{Yes})$ & $C(\text{Yes} \mid \text{No})$（只涉及「預測 Yes」嗰一列：TP 同 FP）
• Recall is biased towards $C(\text{Yes} \mid \text{Yes})$ & $C(\text{No} \mid \text{Yes})$（只涉及「實際 Yes」嗰一行：TP 同 FN）
• F-measure is biased towards all except $C(\text{No} \mid \text{No})$（用 TP、FP、FN，唔理 TN）

教科書亦有 $\text{Weighted Accuracy} = \frac{w_1 a + w_4 d}{w_1 a + w_2 b + w_3 c + w_4 d}$。

7.1 Worked examples (Slides 46, 47, 49, 50)

Slide 46（imbalanced：10 Yes vs 990 No）：

Confusion matrix (a, b, c, d)	Accuracy	Precision	Recall	F
A：TP 10, FN 0, FP 10, TN 980	990/1000 = 0.99	10/20 = 0.5	10/10 = 1	2(0.5)(1)/1.5 = 0.667
B：TP 1, FN 9, FP 0, TN 990	991/1000 = 0.991	1/1 = 1	1/10 = 0.1	2(1)(0.1)/1.1 = 0.182

兩個 model accuracy 差唔多（0.99 vs 0.991），但 A 搵晒所有 Yes，B 只搵到 1 個。F-measure 清楚顯示 A 較好。

Slides 47 / 49（同樣 TPR，唔同 class 比例）：

Confusion matrix	Accuracy	Precision	Recall = TPR	FPR	F
C：TP 40, FN 10, FP 10, TN 40	0.8	0.8	0.8	10/50 = 0.2	0.8
D：TP 40, FN 10, FP 1000, TN 4000	4040/5050 = 0.8	40/1040 = 0.038	0.8	1000/5000 = 0.2	0.073

重點：TPR 同 FPR 唔受 class 比例影響（C、D 都係 0.8 / 0.2），但 Precision 對 class imbalance 好敏感（Negative 多 100 倍，FP 都多 100 倍，precision 由 0.8 跌到 0.038）。

Slide 50（三個 models，各 50 Yes、50 No）：

Confusion matrix	TPR	FPR	Precision	Accuracy
TP 10, FN 40, FP 10, TN 40	0.2	0.2	0.5	0.5
TP 25, FN 25, FP 25, TN 25	0.5	0.5	0.5	0.5
TP 40, FN 10, FP 40, TN 10	0.8	0.8	0.5	0.5

三個 model 都係 $TPR = FPR$，即喺 ROC 嘅 diagonal 上 → 同 random guessing 冇分別（只係「估 Yes」嘅比例唔同）。

from sklearn.metrics import confusion_matrix, classification_report, precision_score, recall_score, f1_score
confusion_matrix(y_true, y_pred, labels=[1, 0])   # 排成 [[TP, FN], [FP, TN]]
print(classification_report(y_true, y_pred))

8. Methods for Performance Evaluation

Slide 27：Performance of a model may depend on other factors besides the learning algorithm：Class distribution、Cost of misclassification、Size of training and test sets（slide 圖 learning curve：training size 越大 accuracy 越高同越穩定）。

from sklearn.model_selection import cross_val_score, StratifiedKFold, LeaveOneOut, RepeatedStratifiedKFold
cross_val_score(clf, X, y, cv=StratifiedKFold(n_splits=10, shuffle=True, random_state=0))
cross_val_score(clf, X, y, cv=LeaveOneOut())
cross_val_score(clf, X, y, cv=RepeatedStratifiedKFold(n_splits=5, n_repeats=10))  # 可睇 variance

9. ROC Curve (Methods for Model Comparison)

Slide 32：ROC (Receiver Operating Characteristic)：

• 1950s 為 signal detection theory 分析 noisy signals 而發展。
• 一個圖像化方法，顯示 detection rate 同 false alarm rate 之間嘅 trade-off。
• ExamROC curve plots True positive rate TPR (on the $y$-axis) against False positive rate FPR (on the $x$-axis)。
• 一個 model 嘅 performance 係 ROC 上嘅一個點；改變 classifier 嘅 threshold 會改變點嘅位置。

9.1 Continuous-valued outputs (Slides 34–36)

要畫 ROC curve，classifier 必須產生 continuous-valued output（score），用嚟將 test records 由「最可能係 positive」排到「最唔可能」。好多 classifiers 只產生 discrete output（predicted class），但可以攞到 continuous outputs：Decision trees（leaf 入面 positive 比例）、rule-based classifiers、neural networks、Bayesian classifiers（posterior probability）、k-nearest neighbors（neighbors 中 positive 比例）、SVM（距離 hyperplane $\mathbf{w}\cdot\mathbf{x}+b$）。

Slide 35：Decision tree 嘅 continuous-valued outputs（每個 leaf 嘅 class 比例）。Slide 36：一維 data 有兩個 classes，$x > t$ 就分類為 positive；喺某個 threshold $t$：$TPR = 0.5$、$FNR = 0.5$、$FPR = 0.12$、$TNR = 0.88$。$t$ 向左移 → TPR 同 FPR 一齊上升。

9.2 How to Construct an ROC Curve (Slides 38–39)

Worked example（自擬）：10 個 instances（5 個 +、5 個 −）：

Score	Class	Threshold $\ge$	TP	FP	FN	TN	TPR	FPR
0.95	+	0.95	1	0	4	5	0.2	0
0.90	+	0.90	2	0	3	5	0.4	0
0.85	−	0.85	2	1	3	4	0.4	0.2
0.80	+	0.80	3	1	2	4	0.6	0.2
0.70	−	0.70	3	2	2	3	0.6	0.4
0.60	+	0.60	4	2	1	3	0.8	0.4
0.50	−	0.50	4	3	1	2	0.8	0.6
0.40	−	0.40	4	4	1	1	0.8	0.8
0.30	+	0.30	5	4	0	1	1.0	0.8
0.20	−	0.20	5	5	0	0	1.0	1.0

加上起點 $(FPR, TPR) = (0, 0)$（$\text{threshold} > 0.95$，全部預測 −）。連線：(0,0)→(0,0.2)→(0,0.4)→(0.2,0.4)→(0.2,0.6)→(0.4,0.6)→(0.4,0.8)→(0.6,0.8)→(0.8,0.8)→(0.8,1)→(1,1)。

AUC（梯形 / 長方形面積）：FPR 0–0.2 段 $TPR = 0.4$ → 0.08；0.2–0.4 段 $TPR = 0.6$ → 0.12；0.4–0.6 段 0.8 → 0.16；0.6–0.8 段 0.8 → 0.16；0.8–1 段 1.0 → 0.2。總和 = 0.72。

9.3 Using ROC for Model Comparison (Slide 37)

• No model consistently outperform the other（兩條 ROC 交叉時）：M1 is better for small FPR，M2 is better for large FPR。揀邊個視乎應用可接受幾多 false alarms。
• Area Under the ROC curve (AUC)：Ideal: Area = 1；Random guess: Area = 0.5。

from sklearn.metrics import roc_curve, roc_auc_score
y = [1,1,0,1,0,1,0,0,1,0]; s = [.95,.90,.85,.80,.70,.60,.50,.40,.30,.20]
fpr, tpr, thr = roc_curve(y, s)
roc_auc_score(y, s)   # 0.72

10. Class Imbalance Problem

Slide 41：好多 classification problems 嘅 classes 係 skewed（一個 class 嘅 records 遠多過另一個）：

• Credit card fraud
• Intrusion detection
• Defective products in manufacturing assembly line

Evaluation measures such as accuracy is not well-suited for imbalanced class. 偵測 rare class 就好似 "finding needle in a haystack"。Slides 42–50 嘅 confusion matrix 同 alternative measures 已喺上面 §5、§7 詳述。

10.1 Handling Class Imbalanced Problem (Slide 51)

10.2 Cost-Sensitive Classification (Slides 54–56)

Example：Bayesian classifier。給定 test record $x$：計每個 class $i$ 嘅 $p(i \mid x)$；decision rule：classify as class $k$ if $k = \arg\max_i p(i \mid x)$。2-class 時：classify $x$ as + if $p(+|x) \gt p(-|x)$。

呢條 rule implicitly assumes $C(+|+) = C(-|-) = 0$ and $C(+|-) = C(-|+)$（即正確冇 cost、兩種錯誤 cost 一樣）。

General decision rule：classify test record $x$ as class $k$ if $k = \arg\min_j \sum_i p(i \mid x)\, C(i, j)$（揀 expected cost 最低嘅 class）。2-class：

Decision rule：classify $x$ as + if $\text{Cost}(+) < \text{Cost}(-)$。如果 $C(+,+) = C(-,-) = 0$：

（$C(i, j)$ = 實際 class $i$ 被預測為 $j$ 嘅 cost。）

10.3 Sampling-based Approaches (Slide 57)

方法	做法	風險
Under-sample the majority class	隨機抽走部分 majority records，令兩類數目接近	丟失有用資訊
Over-sample the rare class	重複（或合成，例如 SMOTE）rare class records	重複 records 可能導致 overfitting

from sklearn.utils import resample
minority = train[train.y == 1]; majority = train[train.y == 0]
up = resample(minority, replace=True, n_samples=len(majority), random_state=0)    # over-sample
down = resample(majority, replace=False, n_samples=len(minority), random_state=0) # under-sample
# 或 cost-sensitive：DecisionTreeClassifier(class_weight={0: 1, 1: 100})

自我測驗 Self-test

Q1. 一個 model training error 2%、test error 25%；另一個 training error 20%、test error 22%。各屬咩情況？

第一個：training error 細但 test error 大 → Overfitting（model 太複雜）。第二個：兩者都大 → 傾向 Underfitting（model 太簡單）。可以用 validation set 揀中間複雜度、增加 training data，或 pruning。

Q2. Confusion matrix：$TP = 30, FN = 20, FP = 10, TN = 940$。計 Accuracy、Precision、Recall、F、FPR、Specificity。

$\text{Total} = 1000$。$\text{Accuracy} = 970/1000 =$ 0.97；$\text{Precision} = 30/40 =$ 0.75；$\text{Recall} = 30/50 =$ 0.6；$F = 2(0.75)(0.6)/1.35 =$ 0.667（或 $2a/(2a+b+c) = 60/90$）；$FPR = 10/950 =$ 0.0105；$\text{Specificity} = 940/950 =$ 0.989。

Q3. Cost matrix $C(+,+)=0, C(+,-)=50, C(-,+)=5, C(-,-)=0$。Model A：TP 80, FN 20, FP 100, TN 800；Model B：TP 95, FN 5, FP 300, TN 600。邊個 accuracy 高？邊個 cost 低？

A：$\text{accuracy} = 880/1000 = 0.88$；$\text{cost} = 20 \times 50 + 100 \times 5 = 1000 + 500 =$ 1500。
B：$\text{accuracy} = 695/1000 = 0.695$；$\text{cost} = 5 \times 50 + 300 \times 5 = 250 + 1500 =$ 1750。
A accuracy 較高而 cost 亦較低 → A 較好。（如果 $C(+,-)$ 改做 100：$A = 2500$，$B = 2000$，就會變成 B 較平。）

Q4. 解釋 holdout、k-fold CV、leave-one-out 同 stratified CV。數據得 200 records 而 positive 只有 10 個，應用邊個？

Holdout：2/3 train、1/3 test。k-fold：分 $k$ 份，輪流用 1 份 test、$k - 1$ 份 train。LOOCV：$k = n$。Stratified：確保每份 class 比例相同。細樣本 + imbalanced → 用 stratified (repeated) k-fold CV，否則某啲 folds 可能冇 positive。

Q5. ROC 上 $(FPR, TPR) = (0, 0)$、(1, 1)、(0, 1) 同對角線各代表咩？$AUC = 0.5$ 代表咩？

(0,0)：全部預測 negative；(1,1)：全部預測 positive；(0,1)：ideal（slide 用 (TPR, FPR) 寫成 (1,0)）；對角線：random guessing。$AUC = 0.5$ = random guess；$AUC = 1$ = ideal。

Q6. Scores 同 labels：0.9(+), 0.8(−), 0.7(+), 0.6(+), 0.4(−), 0.3(−)。畫 ROC 嘅點並計 AUC。

$P = 3, N = 3$。Threshold $\ge 0.9$：TP1 FP0 → (0, 0.333)；$\ge 0.8$：(0.333, 0.333)；$\ge 0.7$：(0.333, 0.667)；$\ge 0.6$：(0.333, 1)；$\ge 0.4$：(0.667, 1)；$\ge 0.3$：(1, 1)。加 (0,0)。$AUC = 0.333 \times 0.333 + 0.667 \times 1 = 0.111 + 0.667 =$ 0.778（= 9 對中 7 對 + 較高 = 7/9）。

Q7. $p(\text{fraud} \mid x) = 0.05$。漏報 fraud 嘅 cost = 2000，誤報 cost = 50，正確冇 cost。應該預測咩？

$\text{Cost}(\text{predict fraud}) = p(\text{normal} \mid x) \times 50 = 0.95 \times 50 = 47.5$；$\text{Cost}(\text{predict normal}) = p(\text{fraud} \mid x) \times 2000 = 0.05 \times 2000 = 100$。47.5 < 100 → predict fraud。$\text{Threshold} = 50/(50 + 2000) = 0.0244 < 0.05$。

Q8. 點解 precision 會受 class imbalance 影響，但 TPR / FPR 唔會？用 slide 47 例子解釋。

TPR 只用實際 positive 嗰行（$TP/(TP+FN)$），FPR 只用實際 negative 嗰行（$FP/(FP+TN)$），各自係行內比例，唔受兩類相對數目影響。$\text{Precision} = TP/(TP+FP)$ 混合咗兩行：negative 多 100 倍時 FP 亦多 100 倍（10 → 1000），precision 由 0.8 跌到 0.038，雖然 $TPR = 0.8$、$FPR = 0.2$ 冇變。

Q9. Validation set 同 test set 有咩分別？點解唔可以用 test set 揀 hyperparameters？

Validation set 由 training data 分出，用嚟估 generalization error、tune complexity / hyperparameters、model selection；test set 只喺最後評估一次。用 test set 揀 hyperparameters 會令 test set 間接參與 training，報告嘅 performance 過度樂觀，唔再係 unseen data 嘅公正估計。

一頁總結 Cheat sheet