決策樹 ID3 演算法 Java 完整實現：從資訊熵計算到樹構建

案例背景：流感診斷資料集

目標：用 ID3 演算法建立決策樹，預測「患流感」。

核心數學原理

資訊熵

衡量資料集純度，熵越低越純。

資訊增益

選擇資訊增益最大的屬性作為分裂節點，分類能力最強。

手算演示（關鍵步驟）

最終選擇「體溫」為根節點（增益最大），遞迴構建子樹。

Java 核心程式碼結構

package ID3Tree;

public class Entropy {           // 資訊熵計算工具類
public class TreeNode {          // 樹節點：parent、屬性名、子節點陣列
public class Comparisons implements Comparator { // TreeSet 排序用
public class UtilID3 {           // 主邏輯：建樹、計算增益、遞迴分裂、列印
    // 關鍵方法：
    // create()           入口
    // getMaxGain()       選最大增益屬性
    // insert()           遞迴插入子節點
    // gain() / entropy() 增益/熵計算
    // pickUpAndCreateArray() 依屬性值切分資料集
}

關鍵邏輯解析

1. 旗標陣列 flag[]：標記屬性是否已用於分裂，避免重複使用
2. 遞迴終止條件：gain == 0（無增益）或資料集純度 100% → 建立葉節點，類別為目標屬性值
3. TreeSet 去重：getAttributes() 取得屬性所有可能取值，自動排序
4. 列印輸出：前序遍歷，格式 節點名 → 如果：屬性值 → 子樹

執行結果

擴展建議

• 支援連續屬性離散化（如體溫 37.2°C → 閾值分箱）
• 加入剪枝（Pre-pruning / Post-pruning）防止過擬合
• 實現 C4.5 (Gain Ratio) / CART (Gini) 演算法
• 序列化模型（JSON/PMF）供線上推理服務載入

總結

本實現完整展示 ID3 從熵計算、增益選擇、遞迴建樹到列印的全流程，程式碼結構清晰，適合教學與二次開發基礎。掌握資訊論基礎與遞迴分治思想，即可靈活擴展至其他決策樹演算法。