[原]【機器學習基礎】決策樹算法

在之前的兩節博文 《混合和裝袋》 和 《自適應提升》 中，我們已經有現成的一堆假設g在手中，我們還如何將這些g混合起來，得到更好的分類器。

混合方式可以分為三種情況：

1. 把g看做是同等地位，通過投票或者平均的方式將它們合起來，稱為Bagging
2. g是不平等的，有好有壞，一個可行的做法是把g當成是特征的轉換，然后丟進線性模型訓練就可以了，這稱為AdaBoost
3. 如果是不同的條件下，使用不同的g，那么我們仍然可以將g當做是特征轉換，接下來使用一個非線性模型來得到最終的模型參數，這就是該文要介紹的決策樹算法

決策樹的表示方式可以有兩種形式。

第一種是從路徑的角度（Path View），將每個從根到葉子的路徑作為一個假設g，通過不同的條件組合得到最后的G(X)。

第二種是從遞歸的角度（Recursive View），父樹是由子樹遞歸定義的tree=(root,sub-trees)。

1. 從數據中看看如何做分支（branching criteria）
2. 根據分支將數據分成幾塊
3. 根據不同的數據學習子樹
4. 得到最終的決策樹

分類回歸樹(CART,Classification And Regression Tree)算法采用一種二分遞歸分割的技術，將當前的樣本集分為兩個子樣本集，使得生成的的每個非葉子節點都有兩個分支。

CART根據不同的條件，對數據進行切分，到達葉子節點時，根據剩下的數據進行預測，輸出一個常數。

CART算法中每個節點（看做是一個決策樁decision stump）對數據進行切分，如果分出來的數據的y都很接近（回歸問題）或者都一樣（分類問題），那么我們說這樣的數據是“純的”，這樣用標量對數據進行預測可以得到比較小的誤差。

我們通過上面的公式，來計算對于每一個節點的決策樁來說，分出來的兩份數據的純度是怎樣的。該公式通過計算數據集Di（i=1 or 2）的純度并根據數據集的數量對其進行加權，其加權的意義是 如果數據集的數量比較大的話，那個純度對其比較重要，反之，就不那么重要。

CART通過分出的兩部分數據綜合起來的純度對決策樁進行選擇，選擇“最純”的分割方式作為當前的分支。

我們可以將分割出來的數據和回傳的常數的誤差作為評價純度的方法，利用數據的y和回傳的y_ba的均方誤差來評價回歸問題的純度；利用0/1誤差函數來評價分類問題的純度。

如果是分類問題，我們還可以使用一個別的方法。通過基尼不純度來度量分類問題的純度問題。

下面是CART算法完整流程：

一棵完全長成的樹的訓練誤差為0Ein(G)=0，這會有過擬合的危險，在每一個節點上的數據越來越少，導致擬合到這些節點的數據可能是過擬合的。

所以，我們需要一個正則化的機制，來控制模型復雜度，讓模型不那么容易出現過擬合現象。

CART剪枝算法從完全生長的決策樹的底端剪去一些子樹，使決策樹變簡單，從而能夠對未知數據有更準確的預測。

上圖告訴我們使用葉子的數目作為正則項（regularizer），最終得到一個正則化的決策樹。

關于剪枝的具體做法時：

• 首先得到完全長成的樹作為G(0)；
• 然后試圖摘掉一片葉子，將所有摘掉一片葉子后的樹計算Ein，將最小的那棵摘掉一片葉子的數作為G(1)；
• 如此這般，得到摘掉兩片葉子的最優樹G(2)，這樣不斷剪枝，直到根結點，形成一個子樹序列；
• 最終對這個子樹序列使用argmin Ein(G)+λΩ(G)來得到最后的輸出。

機器學習技法課程，林軒田，臺灣大學