AI 摘要

決策樹（Decision Tree）演算法理論

決策樹是一種監督 式學習（supervised learning）方法，透過資料驅動的方式，學習一組具階層結構（hierarchical structure）的條件判斷規則，以近似輸入特徵與目標變數之間的映射關係。其屬於非參數模型（non-parametric model），模型結構由資料與學習過程共同決定，而非事先固定。

方法背景

經典決策樹演算法皆基於遞迴式特徵分割的核心思想。

ID3 以資訊增益作為分割準則，僅適用於分類問題

C4.5 在此基礎上擴充以處理連續特徵與缺失值，並引入增益率以修正資訊增益的偏好

CART 則提供統一框架，同時支援分類與回歸，並限制樹結構為二元形式

模型性質

決策樹採用自頂向下、貪婪式策略建構，每一步僅根據當前節點的局部最優分割進行決策，因此不保證全域最優解。此一特性構成其理論上的核心限制。

模型複雜度與泛化行為（Model Complexity and Generalization）

模型複雜度由樹的深度與節點數共同決定。樹結構越深，表達能力越強，但對資料擾動亦更為敏感，容易產生過擬合。實務上常透過限制樹結構或剪枝，作為一種結構性正則化手段。

學術定位

單一決策樹具備高度可解釋性，但模型穩定性較低。在研究與實務中，其主要價值多體現在作為集成方法（如隨機森林與梯度提升）的基礎模組，而非單獨追求最佳預測效能。

問題設定

給定一組訓練資料

$$\mathcal{D}=\{(x_i, y_i)\}_{i=1}^{n},$$

其中 $x_i \in \mathbb{R}^d$ 表示第 $i$ 個樣本的特徵向量，$y_i$ 為對應的目標變數，可為離散類別或連續數值。

決策樹的學習目標並非直接估計全域解析映射，而是透過一系列條件分割，將特徵空間劃分為多個子區域，使得每一區域內的目標分佈相對集中，並以簡單的局部模型進行預測。

分割點選擇

決策樹節點的分割點選擇是一個離散優化問題（discrete optimization problem）。演算法在每個節點僅考慮一組有限且可枚舉的候選分割（finite and enumerable candidate splits），透過窮舉搜尋（exhaustive search）評估其效果，並採用貪婪策略（greedy strategy）追求當前節點的不純度最大下降，不保證全域最優。

對於第 $j$ 個連續特徵（continuous feature） $x_j$，其候選分割點集合定義為排序後相鄰樣本值的中點：

$$\mathcal{T}_j = \left\{ \frac{x_j^{(i)} + x_j^{(i+1)}}{2} : i=1,\dots,n-1 \right\}$$

其中 $x_j^{(i)}$ 為特徵 $x_j$ 排序後的第 $i$ 個值。最優分割（optimal split） $(j^*, t^*)$ 由最大化不純度減少量（impurity reduction） $\Delta I$ 決定：

$$(j^*, t^*) = \underset{j \in \{1,\dots,d\},\ t \in \mathcal{T}_j}{\arg\max} \ \Delta I(S, j, t)$$

此構造確保候選點位於不同樣本之間，使分割後的子節點（child nodes）非空，並透過窮舉搜索找到當前節點的局部最優切分（locally optimal split）。

不純度基準 (Impurity Criteria)

$I(S)$ 表示節點 $S$ 的不純度函數，不純度用來衡量節點內目標變數分佈的不確定性，當資訊純度到達 0 的時候表是已經沒有資訊可以分類。常見的不純度函數包括資訊熵（Entropy）以及基尼不純度（Gini Impurity）。

決策樹分類（Decision Tree Classification）

在某一節點 $S$ 中，設類別標籤集合為 $\{1,2,\dots,K\}$。
令 $S_k$ 表示節點 $S$ 中屬於第 $k$ 類的樣本子集，則類別 $k$ 在節點 $S$ 中的經驗機率（empirical probability）定義為

$$p_k=\frac{|S_k|}{|S|}$$

經驗機率（empirical probability）是由有限樣本中出現的相對頻率所定義的機率估計，用來近似未知的真實機率分佈。

資訊熵（Entropy）

資訊熵源自資訊理論， $H(S)$ 衡量節點 $S$ 中類別分佈的不確定性（uncertainty）。設有 $K$ 個類別，$p_k$ 為節點中類別 $k$ 的經驗機率

$$H(S) = -\sum_{k=1}^{K} p_k \log_b p_k$$

基尼不純度（Gini Impurity）

基尼不純度 $G(S)$ 衡量從節點中隨機抽取兩個樣本，其類別不一致的機率（probability），源自統計學

$$G(S) = 1 - \sum_{k=1}^{K} p_k^2$$

決策樹回歸（ Decision Tree Regression）

在回歸問題中，葉節點以常數作為預測，其最佳估計為

$$\hat{y}_S=\frac{1}{|S|}\sum_{i\in S}y_i$$

節點誤差通常以均方誤差（Mean Squared Error, MSE）表示：

$$\text{MSE}(S)=\frac{1}{|S|}\sum_{i\in S}(y_i-\hat{y}_S)^2$$

資訊增益（Information Gain）

資訊增益（Information Gain）用於量化分割節點所獲得的純度提升。給定節點 $S$ 及其目標變數不純度 $I(S)$，若將 $S$ 分割為子節點 ${S_v}_{v=1}^V$，則資訊增益定義為：

$$IG(S) = I(S) - \sum_{v=1}^{V} \frac{|S_v|}{|S|} I(S_v)$$

範例

參考資料

[1] GeeksforGeeks, “Iterative Dichotomiser 3 (ID3) Algorithm From Scratch,” GeeksforGeeks, Jan. 02, 2024. https://www.geeksforgeeks.org/machine-learning/iterative-dichotomiser-3-id3-algorithm-from-scratch/

[2] GeeksforGeeks, “CART (Classification And Regression Tree) in Machine Learning,” GeeksforGeeks, Sep. 23, 2022. https://www.geeksforgeeks.org/machine-learning/cart-classification-and-regression-tree-in-machine-learning/

[3] GeeksforGeeks, “Decision Tree Algorithms,” GeeksforGeeks, Nov. 11, 2023. https://www.geeksforgeeks.org/machine-learning/decision-tree-algorithms/