決策樹 ID3 算法原理與 Python 實現詳解

決策樹 ID3 算法：從信息熵到樹構建

ID3 (Iterative Dichotomiser 3) 是決策樹經典算法，核心思想是用信息增益作為屬性選擇標準，採用貪心策略遞歸構建樹，使每個非葉節點獲得最大類別信息，將整體熵值降至最低。

核心概念：信息熵與信息增益

信息熵 Entropy

衡量數據集純度。設目標屬性 C 有 m 種取值，比例分別為 P1...Pm，則：

Entropy(S) = - Σ (Pi * log2(Pi))

例：Weather 數據集 14 筆，Play=Yes 9 筆，No 5 筆。
Entropy = -(9/14*log2(9/14) + 5/14*log2(5/14)) ≈ 0.940

信息增益 Information Gain

屬性 A 將數據集 S 分割為 k 個子集 Si，增益為：

Gain(S, A) = Entropy(S) - Σ (|Si|/|S| * Entropy(Si))

例：以 Wind 劃分 (Weak 8 筆，Strong 6 筆)。
Entropy(Weak)=0.811, Entropy(Strong)=1.0
Entropy_after = (8/14)*0.811 + (6/14)*1.0 ≈ 0.892
Gain = 0.940 - 0.892 = 0.048

樹的遞歸構建流程

1. 計算所有候選屬性對目標屬性的信息增益。
2. 選擇增益最大的屬性作為當前決策節點。
3. 按該屬性值劃分數據集，對每個子集遞歸構建子樹（注意：遞歸時使用當前子集而非原始數據集）。
4. 終止條件：所有樣本同類、屬性用盡、增益為 0。

Weather 例：Outlook 增益 0.246 最大 → 根節點。Sunny 分支下再算 Temperature/Humidity/Wind，Humidity 增益最大 → 子節點，最終得到完整決策樹。

ID3 優缺點總結

優點

• 貪心策略保證每步局部最優，構建速度快，模型可解釋性強。
• 自動進行特徵選擇，適合離散型特徵。

缺點

• 僅支援離散屬性，連續值需離散化預處理。
• 缺失值處理困難，需填補或剔除。
• 偏好取值多的屬性：信息增益天然傾向分支多的屬性（如 ID 編號），可能導致過擬合。改進算法 C4.5 引入信息增益率修正此缺陷。