[ML] 機器學習技法：第九講 Decision Tree

ML：基礎技法學習
Package：scikit-learn
課程：機器學習技法
簡介：第九講 Decision Tree

提要

  • 優點
    • 可輕易被解釋
    • 簡單實現
    • 有效率
  • 缺點
    • 理論支持薄弱
    • 參數無理論保證，難以設計
    • 無特定代表性的演算法，只有流不流行

基本算式

$$ G(\mathbf{x})=\sum_{c=1}^{C}[b(\mathbf{x})=c]\cdot G_c(\mathbf{x}) $$ \(G(\mathbf{x})\)：表示整顆樹
\(b(\mathbf{x})\)：表示分支的條件
\(G_c(\mathbf{x})\)：表示 c 條件下分支的子樹
$$ G(\mathbf{x})=\sum_{t=1}^{T}q_t(\mathbf{x})\cdot g_t(\mathbf{x}) $$ \(T\)：表示 leaf 的個數，如圖中共有六個 leaf
\(q_t(\mathbf{x})\)：表示滿足條件的 path，如紫色的部分
\(g_t(\mathbf{x})\)：表示到達 leaf 上最終執行的演算法
或者可以換個方向來看
一顆樹是由不同的分支子樹所組成的
$$ G(\mathbf{x})=\sum_{c=1}^{C}[b(\mathbf{x})=c]\cdot G_c(\mathbf{x}) $$ 用 \(G(\mathbf{x})\) 表示整顆樹，依不同的分支條件 \([b(\mathbf{x})=c]\)，決定其分支的子樹 \(G_c(\mathbf{x})\)

基本演算法

  • function \(DecisionTree(D=\{(\mathbf{x}_n,y_n)\}_{n=1}^N\)
    • if (符合中止條件)
      • 回傳 \(g_t(\mathbf{x})\)
    • else
      1. 學習  \(b(\mathbf{x})\)
      2. 將 \(D\) 分割成 C 個部分 \(D_c=\{(\mathbf{x}_n,y_n):b(\mathbf{x}_n)=c\}\)
      3. 遞迴 \(G_c(x)= DecisionTree(D_c)\)
      4. 回傳 \(G(\mathbf{x})=\sum_{c=1}^{C}[b(\mathbf{x})=c]\cdot G_c(\mathbf{x})\)

Classification and Regression Tree (C&RT)

來自於 CARTTM of California Statistical Software
  • function \(DecisionTree(D=\{(\mathbf{x}_n,y_n)\}_{n=1}^N\)
    • if (無法再切割) => 故為 fully-grown tree
      • 回傳 \(g_t(\mathbf{x})=E_{in}-optimal\ constant\)
    • else
      1. 學習 \(b(\mathbf{x})\)
        $$ b(\mathbf{x})\underset{decision\ stumps\ h(\mathbf{x})}{=argmin}\sum_{c=1}^{2}|D_c\ with\ h|\cdot impurity(D_c\ with\ h) $$
        • classification 使用 Gini index
          $$impurity(D)=1-\sum_{k=1}^{K}\left (\frac{\sum_{n=1}^{N}[y_n=k]}{N}  \right )^2$$
        • regression
          $$impurity(D)=\frac{1}{N}\sum_{n=1}^{N}(y_n-\bar{y})^2$$
          \(\bar{y}\) 為 \(\{y_n\}\) 的平均
      2. 將 \(D\) 分割成 2 個部分 \(D_c=\{(\mathbf{x}_n,y_n):b(\mathbf{x}_n)=c\}\)
      3. 遞迴 \(G_c(x)= DecisionTree(D_c)\)
      4. 回傳 \(G(\mathbf{x})=\sum_{c=1}^{\color{Orange}{2}}[b(\mathbf{x})=c]\cdot G_c(\mathbf{x})\)
基於基本的 decisionTree 的演算法
首先決定樹的種類，為二元樹，所以 \(C=2\)
決定 leaf 上回傳的 \(g_t(\mathbf{x})\) 是一個最佳化的常數
  • classification => 回傳 \(\{y_n\}\) 最多數的類別
  • regression => 回傳 \(\{y_n\}\) 的平均值
\(C=2\) 如何切兩半呢？可利用 decision stump，這裡比較不同的是，值為 {1,2}，而不是 {0,1}
那麼怎樣才是好的切割？因 \(g_t(\mathbf{x})\) 的決定方式，希望此時的 \(D_c\) 越純越好，這樣 \(E_{in}\) 才會低
$$ b(\mathbf{x})\underset{decision\ stumps\ h(\mathbf{x})}{=argmin}\sum_{c=1}^{2}impurity(D_c\ with\ h) $$ 但 impurity function 該用什麼才能表示純度呢？
首先可考慮 \(E_{in}\) 的大小，越小越純
  • regression
    • 常用的 square error，\(\bar{y}\) 為 \(\{y_n\}\) 的平均
      $$impurity(D)=\frac{1}{N}\sum_{n=1}^{N}(y_n-\bar{y})^2$$
  • classification
    • 分類錯誤 \(impurity(D)=\frac{1}{N}\sum_{n=1}^{N}[y_n\neq y^*]\)，\(y^*\) 為多數的 \(\{y_n\}\)
    • 或者換個方式寫 \(impurity(D)=1-\underset{1\le k\le K}{max}\frac{\sum_{n=1}^{N}[y_n=k]}{N}\)，\(k=y^*\)
    • 但以上兩者的缺點就是只考慮單一項，未考慮整體的分佈是否有集中在某項上
      故通常使用 Gini index \(impurity(D)=1-\sum_{k=1}^{K}\left (\frac{\sum_{n=1}^{N}[y_n=k]}{N}  \right )^2\)
但資料切割後，大小不一樣，理論上越大的希望越純，越小的則較不重要
故加上一加權值 \(|D_c\ with\ h|\) 為資料的大小，也許可使用百分比
$$ b(\mathbf{x})\underset{decision\ stumps\ h(\mathbf{x})}{=argmin}\sum_{c=1}^{2}|D_c\ with\ h|\cdot impurity(D_c\ with\ h) $$ 那麼何時可以終止呢？切到無法再切為止
所以滿足以下其中之一，即可中止
  • 當 \(y_n\) 都一樣時，表示 impurity = 0 => \(g_t(\mathbf{x})=y_n\)
  • \(\mathbf{x_n}\) 都一樣時，無法再執行 decision stumps

關於 Decision Tree

  • Regularization by Pruning
    • 當 \(\mathbf{x_n}\) 都不一樣時，fully-grown tree 雖然可以 \(E_{in}(G)=0\)
      但這也表示很容易 overfit，因為越接近 leaf 的資料 \(D_c\) 越少，訓練出來的越有問題
    • regularized decision tree，通常也叫做 pruned decision tree
      利用此式子，\(\Omega (G)\) 為 leaf 的個數
      \(\underset{all\ possible\ G}{argmin}E_{in}(G)+\lambda \Omega (G) \)
    • 實際上無法考慮所有的 \(G\)，故實務上只針對訓練出來的 \(G\) 做處理
      • \(G^{(0)}\) = fully-grown tree
      • \(G^{(i)}\) = \(\underset{G}{argmin}\ E_{in}(G)\)
        \(G^{(i−1)}\) 移除一個 leaf 的所有選擇中，最好 \(E_{in}(G)\) 的 \(G\)
      • 移除 leaf 的意義即是跟隔壁資料做合併，重新計算 \(g_t(\mathbf{x})\)
      • 將全部的 \(G^{(i)}\) 代入 regularizer decision tree，使用 Validation 得到合適的 \(\lambda\)
        或者直接用此得到合適的 \(G\)
  • Branching on Categorical Features
    • numerical feature，像是血壓
      \(b(\mathbf{x})=[x_i \le \theta ]+1\)，\(\theta \in \mathbb{R}\)
    • 若換到 Categorical Features 也可輕易應用，像是症狀
      \(b(\mathbf{x})=[x_i \in S ]+1\)，\(S \subset {1,2,\cdots ,K}\)
    • decision subset，某幾類走左邊，其餘走右邊，由 \(S\) 決定
  • Missing Features by Surrogate Branch
    • 可適用缺少資料的時候
    • 訓練時，同時記錄替代的 feature，令其分類跟原本的最佳解差不多
      替代的 \(\ branch\ b_1(\mathbf{x}), b_2(\mathbf{x}),\cdots \approx best\ branch\ b(\mathbf{x})\)

C&RT 特點

  • 與 AdaBoost 比較
    • 只針對特定區域做切割，並非是整區切割
    • 較有效率，t=90 已完成，但 AdaBoost 仍在微調
  • 特點
    • 容易解釋
    • multiclass 實現簡單
    • categorical features 應用簡單
    • missing features 處理簡單
    • non-linear training (and testing) 有效率
  • 與之對應
    • C4.5 演算法，在關鍵點的處理不同而已

比較

  • blending
    • 適用已知 \(g_t\)，\(g_t\) 來自不同的 \(H\)，只是單純合併
  • learning 
    • 適用未知 \(g_t\)，\(g_t\) 來自同樣的 \(H\)，邊學邊決定

程式碼

Overfitting 需注意
import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

# 建立訓練資料
rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
# 每五個加入 noise
y[::5] += 3 * (0.5 - rng.rand(16))

# 訓練模型
estimators = [("max_depth=max", DecisionTreeRegressor(), "slategray"),
              ("max_depth=5", DecisionTreeRegressor(max_depth=5), "yellowgreen"),
              ("max_depth=2", DecisionTreeRegressor(max_depth=2), "cornflowerblue"),]
size = len(estimators)
# 預測資料
X_test = np.arange(0.0, 5.0, 0.01)[:, None]

# 畫圖
plt.figure()

for i, (label, clf, c) in enumerate(estimators):
    # 訓練
    clf.fit(X, y)
    # 預測
    yp = clf.predict(X_test)
    # 畫預測的線
    plt.plot(X_test, yp, label=label, linewidth=size-i, c=c)

# 畫出原始資料
plt.scatter(X, y, c="darkorange", label="data")
# 標示 x, y
plt.xlabel("data")
plt.ylabel("target")
# 設定 title
plt.title("Decision Tree Regression")
plt.legend()
plt.show()

參考

1.10. Decision Trees
sklearn.tree.DecisionTreeClassifier
sklearn.tree.DecisionTreeRegressor

留言

張貼留言