Classification (I): Decision Trees, KNN, Naïve Bayes & SVM

1. Classification: Definition & General Approach

Slide 3：給定一批 records（training set），每個 record 由 tuple $(x, y)$ 描述：

• $x$：attribute set（又叫 attribute、predictor、independent variable、input）
• $y$：class label（又叫 class、response、dependent variable、output）

Task：Learn a model that maps each attribute set $x$ into one of the predefined class labels $y$，即將 class label 建模成 attribute set 嘅 function。

Slide 4 Goal：previously unseen records should be assigned a class as accurately as possible. 用 test set 量度 model 嘅 accuracy：通常將 data 分成 training set（建 model）同 test set（validate model）。

Slide 6 "General Approach for Building Classification Model"：Training Set → Learning algorithm（Induction）→ Learn Model → Apply Model 到 Test Set（Deduction）。

2. Decision Trees: 結構同應用

Slide 8–9 展示 decision tree 例子。Tree 由 root node、internal nodes（每個係一個 attribute test condition，叫 splitting attributes）同 leaf nodes（class label）組成。Slide 9 "Another Example" 說明：同一份 data 可以 fit 出多過一棵 tree。

本 chapter 一直用一個 10-record 例子。Slides 8–23 用 2nd edition 嘅名稱：Home Owner、Marital Status、Annual Income、class = Defaulted Borrower；slide 58 Naïve Bayes 部分就用返舊名 Refund、Taxable Income、Evade。兩套名對應同一份數據（下表用舊名，數字同 slide 8 一樣；亦同 slide 58 文字 $P(\text{No}) = 7/10$、$P(\text{Married} \mid \text{No}) = 4/7$、$P(\text{Refund} = \text{Yes} \mid \text{Yes}) = 0$ 完全吻合）：

Refund?
├── Yes → NO
└── No  → MarSt?
          ├── Married → NO
          └── Single, Divorced → TaxInc?
                                 ├── < 80K → NO
                                 └── > 80K → YES

MarSt?
├── Married → NO
└── Single, Divorced → Home Owner?
                       ├── Yes → NO
                       └── No  → Income?  < 80K → NO ; > 80K → YES

2.1 Apply Model to Test Data (Slides 10–17)

Slides 11–16 一步步示範：由 root 開始，按 test record 嘅 attribute 值沿住分支行，直到 leaf（每張 slide 用紅色箭咀多行一步）。例：test record (Home Owner = No, Marital Status = Married, Annual Income = 80K, Defaulted Borrower = ?)：

1. Root：Home Owner = No → 行去 MarSt 節點
2. MarSt = Married → 去到 leaf NO
3. 結果：slide 16 "Assign Defaulted to "No""

3. Decision Tree Induction & Hunt's Algorithm

Slide 18：好多 induction algorithms：Hunt's Algorithm（最早期之一）、CART、ID3, C4.5、SLIQ, SPRINT。

ExamSlide 19：General Structure of Hunt's Algorithm。設 $D_t$ 為到達 node $t$ 嘅 training records：

Slides 20–23 用稅務 data 示範（圖片）：一開始成個 data 係一個 node（label = majority class "No"，7 No vs 3 Yes）→ 用 Refund split（Refund = Yes 全部 No → leaf）→ Refund = No 嗰邊再用 Marital Status split（Married 全部 No → leaf）→ Single / Divorced 嗰邊再用 Taxable Income < 80K split → 全部 nodes 變 pure。

4. Design Issues & Test Conditions

Slide 24–25：Decision tree induction 有兩大設計問題：

1. How should training records be split?
   • Method for specifying test condition：視乎 attribute types（Nominal / Ordinal / Continuous）同 number of ways to split（2-way / multi-way）。
   • Measure for evaluating the goodness of a test condition：node impurity（Gini Index、Entropy、Misclassification error）。
2. How should the splitting procedure stop?
   • Stop splitting if all the records belong to the same class or have identical attribute values。
   • Model Selection：Pre-Pruning (Early Stopping Rule)、Post-pruning（trimming the nodes）。

4.1 Test Conditions by Attribute Type (Slides 26–29)

Splitting based on continuous attributes (slide 29)：

• Discretization to form an ordinal categorical attribute：ranges 用 equal interval bucketing、equal frequency bucketing（percentiles）或 clustering 搵。Static = 開頭 discretize 一次；Dynamic = 每個 node 重做。
• Binary Decision $(A \lt v)$ or $(A \ge v)$：考慮所有可能嘅 splits 搵 best cut；計算量可以較大。

5. Choosing the Best Split: Impurity Measures

Slide 30–31：Greedy approach：nodes with purer class distribution are preferred。需要一個 measure of node impurity。例如 C0 : 5, C1 : 5（high impurity，non-homogeneous）vs C0 : 9, C1 : 1（low impurity，homogeneous）。

5.1 Worked example：計單一 node 嘅 impurity

三個 measures 嘅排序一致（越 pure 越細），只係數值唔同。Entropy 對 impurity 最敏感。

5.2 Finding the Best Split (Slides 33–34)

5.3 Worked example：用 10-record data 揀 root split（Gini）

Parent：7 No、3 Yes → $P = 1 - 0.7^2 - 0.3^2 = 1 - 0.49 - 0.09 = \mathbf{0.42}$

(a) Refund：

• Refund = Yes：3 records（No 3, Yes 0）→ $\text{Gini} = 0$
• Refund = No：7 records（No 4, Yes 3）→ $\text{Gini} = 1 - (4/7)^2 - (3/7)^2 = 1 - 25/49 = 0.490$
• $M = (3/10)(0) + (7/10)(0.490) =$ 0.343 → $\text{Gain} = 0.42 - 0.343 =$ 0.077

(b) Marital Status（multi-way）：

• Single：4 records（Tid 1, 3, 8, 10 → No 2, Yes 2）→ $\text{Gini} = 0.5$
• Married：4 records（Tid 2, 4, 6, 9 → No 4）→ $\text{Gini} = 0$
• Divorced：2 records（Tid 5 Yes, 7 No）→ $\text{Gini} = 0.5$
• $M = 0.4(0.5) + 0.4(0) + 0.2(0.5) =$ 0.300 → $\text{Gain} =$ 0.120

(c) Marital Status（binary {Married} vs {Single, Divorced}）：{S, D} 有 6 records（No 3, Yes 3）→ Gini 0.5 → $M = 0.6(0.5) + 0.4(0) =$ 0.300（同 multi-way 一樣）。

(d) Taxable Income（continuous，binary split）：先排序，再喺相鄰值中點試每個 cut：

例：$v = 97.5$：左 6 records Gini 0.5，右 4 records Gini 0 → $M = 0.6 \times 0.5 = 0.3$。

結論：Marital Status 同 Taxable Income ($\le 97.5$) 都得 $M = 0.300$（Gain 0.12），好過 Refund（$M = 0.343$）。

5.4 Worked example：Information Gain（Entropy）

Parent entropy：$H = -0.3\log_2 0.3 - 0.7\log_2 0.7 = 0.521 + 0.360 = \mathbf{0.881}$

• Refund：Refund = No (3 Yes, 4 No) $\text{entropy} = 0.985$；$M = 0.7 \times 0.985 = 0.690$；$IG = 0.881 - 0.690 = 0.192$
• Marital Status：Single (2, 2) = 1；Married = 0；Divorced (1, 1) = 1；$M = 0.4 + 0 + 0.2 = 0.6$；$IG = 0.281$
• Income $\le 97.5$：(3, 3) = 1；(0, 4) = 0；$M = 0.6$；$IG = 0.281$

同 Gini 結論一致：Refund 最差。

from sklearn.tree import DecisionTreeClassifier, export_text
clf = DecisionTreeClassifier(criterion="gini")   # 或 criterion="entropy"
clf.fit(X_train, y_train)
print(export_text(clf, feature_names=list(X_train.columns)))

6. Stopping, Strengths & Weaknesses of Decision Trees

Stopping Criteria (slide 35)：

• 所有 records 屬同一 class 就停止 expand 該 node。
• 所有 records 嘅 attribute values 相似（identical）就停止。
• Early termination（防止 overfitting，詳見 Chapter 4B）。

Handling interactions (slide 37) 同 Limitations of single attribute-based decision boundaries (slide 38)：因為每個 test 只用一個 attribute，decision boundaries 永遠平行於坐標軸（axis-parallel，好似樓梯級）。如果真正嘅 boundary 係斜線（例如 $x + y \lt 1$）或者 class 取決於兩個 attributes 嘅 interaction（例如 XOR 型），tree 就要好多層先近似到。

7. Nearest-Neighbor Classifiers (KNN)

Slide 40 Basic idea："If it walks like a duck, quacks like a duck, then it's probably a duck."

ExamSlide 41：Requires three things：

1. The set of labeled records
2. Distance metric to compute distance between records
3. The value of $k$, the number of nearest neighbors to retrieve

Slide 42：To classify an unknown record：

1. Compute distance to other training records
2. Identify $k$ nearest neighbors
3. Use class labels of nearest neighbors to determine the class label of unknown record（e.g., by taking majority vote）

Slide 43：Compute proximity，例如 Euclidean distance $d(\mathbf{x},\mathbf{y}) = \sqrt{\sum_i (x_i - y_i)^2}$。決定 class：

• Take the majority vote of class labels among the $k$-nearest neighbors
• Weight the vote according to distance：weight factor $w = 1/d^2$

7.1 Worked example（自擬）

Training：$P_1(1,1)$ A、$P_2(2,2)$ A、$P_3(3,1)$ A、$P_4(5,4)$ B、$P_5(6,5)$ B、$P_6(4,4)$ B。Test $X = (3.2, 3)$。

• $k = 1$：最近係 $P_6$ → B
• $k = 3$：$P_6$ (B)、$P_2$ (A)、$P_3$ (A) → majority A（2:1）
• $k = 3$, distance-weighted：$B = 0.609$；$A = 0.410 + 0.248 = 0.658$ → A（好接近！）
• $k = 5$：B, A, A, B, A → A（3:2）

結論：$k$ 嘅選擇可以改變答案。

7.2 Choosing k & Proximity (Slides 44–45)

Slide 45：Choice of proximity measure matters——視乎 data types 同 attribute types（例如 documents 用 cosine，binary 用 Jaccard，見 Chapter 2）。

7.3 Data Preprocessing for KNN (Slide 46)

ExamAttributes may have to be scaled to prevent distance measures from being dominated by one of the attributes。例：

• height of a person may vary from 1.5m to 1.8m
• weight of a person may vary from 90lb to 300lb
• income of a person may vary from $10K to $1M

唔 scale 嘅話，distance 幾乎完全由 income 決定。Time series 通常 standardize 成 mean 0、standard deviation 1（Z-score transformation）。

7.4 其他特性 (Slides 47–49)

• Local classifiers：只用附近嘅點決定，can produce decision boundaries of arbitrary shapes（1-NN 嘅 decision boundary 係 Voronoi diagram 形狀，slide 47 圖）。
• Missing values：proximity 計算通常需要全部 attributes；有啲方法只用兩個 instances 都有嘅 attributes subset，但咁樣每對 instances 實際用唔同嘅 proximity measure，proximities are not comparable，效果未必好。
• Irrelevant attributes add noise to the proximity measure；Redundant attributes bias the proximity measure towards certain attributes。可用 variable selection 或 dimensionality reduction 處理。

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
knn = make_pipeline(StandardScaler(),
                    KNeighborsClassifier(n_neighbors=3, weights="distance"))  # 先 scale 再 KNN
knn.fit(X_train, y_train); knn.predict(X_test)

8. Naïve Bayes Classifiers

8.1 Bayes Classifier (Slides 51–54)

A probabilistic framework for solving classification problems。

將每個 attribute 同 class label 當 random variables。給定 record with attributes $(X_1, X_2, \dots, X_d)$，目標係預測 class $Y$：搵令 $P(Y \mid X_1, \dots, X_d)$ 最大嘅 $Y$。

Slide 53 問：可唔可以直接由 data 估計 $P(\text{Evade} = \text{Yes} \mid X)$ 同 $P(\text{Evade} = \text{No} \mid X)$？（$X = (\text{Refund} = \text{No}, \text{Divorced}, \text{Income} = 120\text{K})$）——通常唔得，因為 training data 未必有完全相同 attribute 組合嘅 record。

ExamApproach (slide 54)：用 Bayes theorem 計 posterior probability：

Maximum a-posteriori (MAP)：揀令 $P(Y \mid X_1 \dots X_d)$ 最大嘅 $Y$。因為分母對所有 class 一樣，等價於揀令 $P(X_1 \dots X_d \mid Y)\,P(Y)$ 最大嘅 $Y$。問題：點估計 $P(X_1 \dots X_d \mid Y)$？

8.2 Naïve Bayes Assumption (Slide 56)

Exam假設 class 已知時 attributes 之間 conditional independence：

Example：Arm length and reading skills：細路仔手臂較短、閱讀能力有限（同成人比）→ 兩者表面上相關；但如果 age 固定，arm length 同 reading skills 冇明顯關係 → 佢哋係 conditionally independent given age。

咁就可以由 training data 估計每個 $P(X_i \mid Y_j)$。新點分類到令 $P(Y_j)\prod_i P(X_i \mid Y_j)$ 最大嘅 $Y_j$。

8.3 Estimate Probabilities from Data (Slides 58–60)

• Class prior：$P(y)$ = fraction of instances of class $y$。例：$P(\text{No}) = 7/10$，$P(\text{Yes}) = 3/10$。
• Categorical attributes：$P(X_i = c \mid y) = n_c / n$，$n_c$ = 屬於 class $y$ 而 attribute value 為 $c$ 嘅 instances 數，$n$ = 屬於 class $y$ 嘅 instances 數。例：$P(\text{Status} = \text{Married} \mid \text{No}) = 4/7$、$P(\text{Refund} = \text{Yes} \mid \text{Yes}) = 0$。
• Continuous attributes（slide 59）：
  • Discretization：將 range 分 bins，用 bin value 代替（continuous → ordinal）。
  • Probability density estimation：假設 attribute 跟 normal distribution，用 data 估 parameters（mean、standard deviation），再用 distribution 估 conditional probability。

Slide 60 例子：For (Income, Class = No)：sample mean = 110、sample variance = 2975，所以 $P(\text{Income} = 120 \mid \text{No}) = \frac{1}{\sqrt{2\pi}(54.54)} e^{-\frac{(120-110)^2}{2(2975)}} = 0.0072$。公式要 one for each $(X_i, Y_j)$ pair，即每個 attribute 同每個 class 嘅組合各有一套 $\mu_{ij}$、$\sigma_{ij}^2$。

8.4 Worked example：X = (Refund = No, Divorced, Income = 120K)

8.5 Issues with Naïve Bayes (Slides 64–66)

由 slide 58 可見 $P(\text{Refund} = \text{Yes} \mid \text{Yes}) = 0$。如果 test record 係 Refund = Yes，咁 $P(X \mid \text{Yes})$ 成個乘積都會變 0——無論其他 attributes 幾支持 Yes 都冇用。如果某 record 對兩個 class 都有一個 conditional probability = 0，就完全分類唔到。

Slide 64：$P(\text{Yes} \mid \text{Married}) = 0 \times 3/10 / P(\text{Married})$，因為 $P(\text{Married} \mid \text{Yes}) = 0$；$P(\text{No} \mid \text{Married}) = 4/7 \times 7/10 / P(\text{Married})$。

Slide 66 嘅解決方法：Need to use other estimates of conditional probabilities than simple fractions：

其中 $n$ = number of training instances belonging to class $y$；$n_c$ = number of instances with $X_i = c$ and $Y = y$；$v$ = total number of attribute values that $X_i$ can take；$p$ = initial estimate of $P(X_i = c \mid y)$ known apriori；$m$ = hyper-parameter for our confidence in $p$。例：Laplace 下 $P(\text{Refund} = \text{Yes} \mid \text{Yes}) = (0 + 1)/(3 + 2) =$ 0.2（唔再係 0）。

8.6 Characteristics of Naïve Bayes (Slide 67)

• Robust to isolated noise points（概率係由大量 records 平均估計）
• Handle missing values by ignoring the instance during probability estimate calculations
• Robust to irrelevant attributes（irrelevant attribute 嘅 $P(X_i \mid Y)$ 對所有 class 差唔多，乘落去唔改變排序）
• Redundant and correlated attributes will violate class conditional independence assumption（同一資訊被乘兩次，過度影響結果）

from sklearn.naive_bayes import GaussianNB, CategoricalNB
GaussianNB().fit(X_num, y)             # continuous attributes，假設 normal
CategoricalNB(alpha=1).fit(X_cat, y)   # categorical；alpha=1 即 Laplace smoothing

9. Support Vector Machines (SVM)

9.1 Maximum Margin Idea (Slides 69–75)

• Slide 69：Find a linear hyperplane (decision boundary) that will separate the data。
• Slides 70–72：有好多個可能嘅 hyperplanes（"One possible solution"、"Another possible solution"、"Other possible solutions"）都可以將兩類分開。
• Slide 73：Which one is better? B1 or B2? How do you define better?
• Slide 74：ExamFind hyperplane maximizes the margin → B1 is better than B2.

Margin = decision boundary 同兩邊最近 data points 之間嘅距離（兩條平行 hyperplanes $b_{11}$、$b_{12}$ 之間嘅闊度）。Margin 越大，對新 data 嘅 generalization 越好（對 noise 有更大緩衝）。

9.2 Linear SVM (Slides 76–79)

Linear model：

Decision boundary：$\mathbf{w}\cdot\mathbf{x} + b = 0$；兩條 margin hyperplanes：$\mathbf{w}\cdot\mathbf{x} + b = \pm 1$。Learning the model is equivalent to determining the values of $\mathbf{w}$ and $b$.

• Slide 78：Support vectors 係 Lagrange multipliers $\lambda_i \gt 0$ 嘅點（即剛好喺 margin 上嘅點；細節略過）。
• Slide 79：Decision boundary depends only on support vectors——如果另一個 data set 有相同 support vectors，decision boundary 唔會變（其他點移動或刪除都唔影響）。
• 搵到 $\mathbf{w}$、$b$ 之後點分類 test record $\mathbf{x}$？（Slide 79 寫嘅係 $f(\mathbf{x}_i) = 1$ if $\mathbf{w}\cdot\mathbf{x}_i + b \ge 1$、$-1$ if $\le -1$，即係 training 時嘅 margin 條件；實際分類時，落喺 margin 入面嘅點就睇 $\mathbf{w}\cdot\mathbf{x} + b$ 係正定負，即下式）
  $$f(\mathbf{x}) = \begin{cases} +1 & \text{if } \mathbf{w}\cdot\mathbf{x} + b \ge 0 \\ -1 & \text{if } \mathbf{w}\cdot\mathbf{x} + b \lt 0 \end{cases}$$

9.3 Non-linearly Separable: Slack Variables (Slides 80–81)

如果問題唔係 linearly separable？引入 slack variables $\xi_i \ge 0$，容許部分點越過 margin 甚至分錯：

If $k$ is 1 or 2, this leads to similar objective function as linear SVM but with different constraints。$C$ 控制「大 margin」同「少錯誤」之間嘅 trade-off（$C$ 大 → 少容忍錯誤）。

（上式同 slide 81 一樣：成個 $\sum \xi_i$ 先至 $k$ 次方。Slide 用藍圈突出 constraints 入面嘅 $1 - \xi_i$ 同 $-1 + \xi_i$，即係同 linear SVM 唯一唔同嘅地方。）

9.4 Characteristics of SVM (Slides 82–83)

• Learning problem 係 convex optimization problem：有 efficient algorithms 搵 global minima（其他好多方法用 greedy approaches，只搵到 locally optimal solutions，例如 decision tree）。
• High computational complexity for building the model（training 慢）。
• Robust to noise。
• Overfitting is handled by maximizing the margin of the decision boundary。
• SVM can handle irrelevant and redundant attributes better than many other techniques。
• Difficult to handle missing values。

from sklearn.svm import SVC
svm = make_pipeline(StandardScaler(), SVC(kernel="linear", C=1.0))
svm.fit(X_train, y_train)
svm[-1].coef_, svm[-1].intercept_, svm[-1].support_vectors_   # w, b, support vectors

10. Summary: 四種 Classifiers 比較

自我測驗 Self-test

一頁總結 Cheat sheet