ID3 決策樹演算法完整解析：從資訊熵到分類規則推導

背景知識：決策樹分類原理

決策樹透過訓練資料建立樹狀模型進行分類預測。樹由決策節點（測試屬性）、分支（測試結果）、葉節點（分類結果）組成。根節點位於最上層，自上而下遍歷對應分類決策過程。

ID3 演算法核心：資訊論基礎

ID3 由 Quinlan 提出，以資訊增益為屬性選擇標準。關鍵定義：

• 資訊量：n 等概率訊息，單一訊息資訊量 = log₂(n)
• 熵 Entropy：機率分布 P=(p₁...pₙ) 的資訊量 I(P) = -Σ pᵢ log₂(pᵢ)
• 類別資訊 Info(T)：資料集 T 依類別 C₁...Cₖ 分布的熵
• 條件資訊 Info(X,T)：依非類別屬性 X 分割後的加權平均熵 Σ (|Tᵢ|/|T|) Info(Tᵢ)
• 資訊增益 Gain(X,T)：Info(T) - Info(X,T)，增益越大代表屬性 X 越能區分類別

實例演示：預測高中生物理及格與否

步驟 1：資料離散化

原始分數轉為二元值：≥60 → 1（及格），<60 → 0（不及格）。

步驟 2：訓練集統計（161 筆）

步驟 3：計算各屬性資訊增益

• Info(T)（物理）= I(32,129) = 0.7195
• Info(國文, T) = 0.6136 → Gain = 0.1059
• Gain(數學) = 0.2136、Gain(英文) = 0.095、Gain(化學) = 0.1701

數學增益最高，選為根節點。

步驟 4：遞迴建樹

• 數學不及格（104 人）→ 物理不及格 100 人（準確率 96.2%）→ 停止分割，葉節點：物理不及格
• 數學及格（57 人）→ 物理及格 26、不及格 31 → 需進一步分割
• 選化學為分割節點：

數學及格
├─ 化學及格 (32人) → 物理及格 26、不及格 6 → 準確率 81.3% → 葉節點：物理及格
└─ 化學不及格 (25人) → 物理不及格 22、及格 3 → 準確率 88% → 葉節點：物理不及格

步驟 5：驗證集測試與規則萃取

1. 規則 1：數學不及格 → 物理不及格（準確率 96.2%，覆蓋率 64.6%）
2. 規則 2：數學及格 ∧ 化學不及格 → 物理不及格（準確率 88%，覆蓋率 16%）
3. 規則 3：數學及格 ∧ 化學及格 → 物理及格（準確率 81.3%，覆蓋率 20%）

教學啟示

數學基礎直接影響物理學習效果；化學程度對物理亦有輔助。教學策略應重視數理基礎整合，對「數學好但物理普通」學生加強化學輔導。