• 流程
  1. 從現有特徵中選擇最好的特徵作為劃分節點
     • 貪婪搜索
  2. 產生分支
  3. 把樣本、數據劃分到節點裡面，並刪除該特徵
  4. loop 1~3
• 如何選擇最好的節點劃分
  • ID3, C4.5, CART
• 分類器分類方法
  • 通常都多數決
  • 除了 CART

1. ID3

• 選擇信息增益度最大的特徵
• 越小的樹優於越大的
• 信息增益越大表示使用特征 A 来划分所获得的“纯度提升越大”

1-1. 信息增益度

• 信息增益度 = 信息熵 - 條件熵
  • $Gain(D,A)=H(D)-H(D|A)$
    • D 代表樣本（數據）
    • A 代表特徵
  • $H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log\frac{|C_k|}{|D|}$
    • |Ck| 表示所有樣本中第 k 個類別的子集數量
  • $H(D|A) =\sum_{i=1}^m\frac{|D_i|}{|D|}H(D_i) =\sum_{a=1}^m\frac{|D_i|}{|D|}(-\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}log\frac{|D_{ik}|}{|D_i|})$
    • |Di| 表示所有樣本中特徵 A 取第 i 個值的子集數量
      • 特徵 A 的取值共有 m 個
    • |Dik| 表示所有樣本中（特徵 A 取第 i 個值）&（為第 k 個類別）的子集數量

1-2. 缺點

• 对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
• ID3 没有剪枝策略，容易过拟合；
• 只能用于处理离散分布的特征；
• 没有考虑缺失值。

2. C4.5

• 使用信息增益率解決 ID3 流水號特徵問題
• 引入悲观剪枝策略进行后剪枝降低擬和程度
• 可處理連續特徵
  • 假设 n 个样本的连续特征 A 有 m 个取值
  • 将其排序并取相邻两样本值的平均数共 m-1 个數作為划分点
• 可處理缺失值
  • 如果某特徵值A的樣本有缺失值，就用該特徵其他沒缺失的樣本子集之比重來計算
  • 如果新樣本缺少某特徵值，又需要以該特徵值分類時，就將該樣本劃分到該層所有子集之中只是以不同的權重，即不同的概率