【機器學習 08】Aggregation Models — Part 2 — Decision Tree 和 Random Forest
Decision tree
Decision tree 是一種很基礎的演算法，基本邏輯是直接依照資料特性切分，建立子樹，並持續切割。
DecisionTree(Dc):if termination criteria met:
return base hypothesis gₜ(x)
else:
(1) learn branching criteria b(x)
(2) split D to C parts. Dc = {(xₙ, yₙ): b(xₙ) = c}
(3) build sub-tree Gc <- DecisionTree(Dc)
(4) return G(x) = Σ(c=1)[b(x)=c]Gc(x)
此演算法中，有四個要選擇的參數：
(1) number of branches C
(2) branching criteria b
(3) termination criteria
(4) base hypothesis
這些參數要如何設定呢？最常用的演算法為 Classification and Regression Tree (C&RT)。其設定的參數如下：
(1) 每次只切出兩個部分（C=2）
(2) branching criteria b(x)：比較 D_1, D_2 純不純（C&RT 只有兩棵樹），讓 impurity 越低越好。
Impurity function 是用以衡量資料不相似程度，通常在分類問題使用 gini index，可評估類別中錯誤答案的比例，迴歸問題則是使用 regression error。
(3) termination criteria 停下來的條件：
- 所有 yₙ 都相同：impurity = 0 → g_t(x) = yₙ
- 所有 xₙ 都相同：沒有 decision stumps。
(4) base hypothesis：當無法再繼續分支下去時，會回傳 g_t(x) = constant，這個常數是可以使這個群體內 E_in 最小的數值。
- classification: majority of yₙ，佔多數的類別
- regression: average of yₙ，平均值
Decision Tree 有一個問題是容易 overfitting，因為能夠不斷地切分樹，需要 regularization 解決。最常用的解決方法是 pruning 砍樹。
將衡量樹的複雜度的 Ω(G) = NumberOfLeaves(G) 加入 E_{in} 中，其中的 λ 可以利用 Validation Data 以選擇。
然而，要真的找到最佳解的話非常困難，因為要把所有可能的樹都考慮進去。因此有一個替代方案，是先將整棵樹都先長完，再一一合併分支。每次都摘掉一片葉子，看哪些分支合併之後可以讓 E_{in} 變小就先合併，逐步減少分支的數量。
Random Forest
Random forest 就是利用 bagging 做 decision tree。兩者其實是互補的方法，因為 decision tree 的 variance 很高，而 bagging 可以降低 variance，因此 random forest 會比 decision tree 更不容易有 overfitting 的問題。
RandomForest(D):
for t = 1, 2, ..., T:
(1) Bootstrap: request size-N' data by bootstrapping with D (randomly sample N' examples from D)
(2) Random-subspace: randomly sample d' features
(3) obtain tree g_t by DTree(D) return G = Uniform({g_t})
首先，和 bagging 一樣做 bootstrapping，產生新的 dataset。
並且為了讓隨機程度提高，做 random subspace，也就是對 feature 本身做變化。此方法是隨機將 feature 乘上一個數值 P，代表對特徵的重視程度。如果 P_i=1 代表完全取這個 feature，P_i=0 代表完全不取這個 feature。
將用的很亂的 dataset 放進去長出一棵 decision tree，再把所有 decision tree 平均就是 random forest 的結果。
Random Forest 有兩個特性：self-validation 和 built-in feature selection。
Self-Validation: Out-of-Bag examples
至於 training data 和 validation data 要如何切分呢？利用 bagging 的特性，其實不需要特別區分，只要用沒有被 bootstrap 選到的 data 當作 validation，評估 training 的好壞即可。此方法稱為 self-validation，優點是不需要做完 training 之後又做 validation。
Built-in feature selection
線性模型是用每筆 feature 的權重來評估每個 feature 的重要程度。而非線性模型可以借用 permutation test 的概念：隨機亂排其中一個 feature 的順序，將原本的表現和經過隨機亂排之後的表現相減，可以得到此 feature 的重要性。
但是這個計算時需要在做 permutation 時再重新訓練和做 validation，RF 有 OOB，不需要重新訓練，只要在 OOB 做就可以了。
想要更深入了解的話，別忘了去最上面的目錄看其他章的課程筆記！
喜歡這篇文章或是對你有幫助的話，別忘了拍手給我鼓勵哦 👏🏻
