CART樹的剪枝

CART樹剪枝

預剪枝

• 控制樹的深度
• 設定基尼係數(殘差)的閾值，即若當前劃分特徵的基尼係數(殘差)小於閾值時不再對當前的特徵進行劃分
• 設定樣本量的閾值，樣本量小於閾值不再劃分

後剪枝

總體思路：

1. 由完全樹T0開始，剪枝部分結點，得到T1，再次剪枝部分結點得到T2。。。知道僅剩樹根的樹Tk;
2. 通過交叉驗證，對以上k個樹分別評價，選擇損失函數最小的數Tα

具體過程：

• 損失函數 

  原來的損失函數，子樹的整體損失等於，對於每個葉子節點t，葉子結點t的樣本個數再乘以葉子結點t的熵，的加和。   

   在此基礎上，加上正則項，損失函數可轉化爲： 

lTleafl爲子樹的葉子結點的個數，Cα(T)是參數是α時的子樹T的整體損失。參數α權衡訓練數據的     擬合程度與模型的複雜度。設定了α就相當於給樹剪枝了，保證了不會隨着葉結點的增多，讓模型複雜。

在真實計算過程中，當α = 0時，相當於不加正則項，也就是相當於未剪枝，也就是表示未剪枝的決策樹損失最小；當α = 正無窮時，充分剪枝，造成單根結點的決策樹損失最小。

• 剪枝係數

假定當前對以r爲根的子樹剪枝，可以計算剪枝前和剪枝後的損失函數，令兩者相等，可以恰巧求出一個α，讓剪枝前剪枝後損失相似，此時的α即爲剪枝係數。

表示了剪枝後整體損失函數減少的程度。 

• 剪枝過程

1. 對整體樹T0，計算內部各個結點的剪枝係數
2. 查找剪枝係數最小的結點進行剪枝，得到一棵新的決策樹
3. 然後對新的決策樹再次計算各個結點的剪枝係數，再剪枝，重複以上步驟，知道只剩一個結點。
4. 通過以上步驟生成了T0,T1,…Tk決策樹
5. 對這些決策樹依次進行交叉驗證，選取最優子樹Tα