決策樹剪枝(cart剪枝)的原理介紹

決策樹是一種分類器，經過ID3，C4.5和CART等算法能夠經過訓練數據構建一個決策樹。可是，算法生成的決策樹很是詳細而且龐大，每一個屬性都被詳細地加以考慮，決策樹的樹葉節點所覆蓋的訓練樣本都是「純」的。所以用這個決策樹來對訓練樣本進行分類的話，你會發現對於訓練樣本而言，這個樹表現無缺，偏差率極低且可以正確得對訓練樣本集中的樣本進行分類。訓練樣本中的錯誤數據也會被決策樹學習，成爲決策樹的部分，可是對於測試數據的表現就沒有想象的那麼好，或者極差，這就是所謂的過擬合(Overfitting)問題。

決策樹剪枝主要能夠分爲兩種： 預剪枝和後剪枝

預剪枝（Pre-Pruning）

在構造決策樹的同時進行剪枝。全部決策樹的構建方法，都是在沒法進一步下降熵的狀況下才會中止建立分支的過程，爲了不過擬合，能夠設定一個閾值，熵減少的數量小於這個閾值，即便還能夠繼續下降熵，也中止繼續建立分支。可是這種方法實際中的效果並很差，由於在實際中，面對不一樣問題，很難說有一個明確的閾值能夠保證樹模型足夠好，固然在xgboost和lightGBM裏面有一些參數例如min_child_weight也算是設置了分裂節點的權重值，像xgboost之類已經把過擬合寫進損失函數中了，所以不須要有剪枝的過程。函數

後剪枝（Post-Pruning）

後剪枝的剪枝過程是刪除一些子樹，而後用其葉子節點代替，在剪枝過程當中, 將一些子樹刪除而用葉節點代替,這個葉節點所標識的類別用這棵子樹中大多數訓練樣本所屬的類別來標識。
學習

決策樹構造完成後進行剪枝。剪枝的過程是對擁有一樣父節點的一組節點進行檢查，判斷若是將其合併，熵的增長量是否小於某一閾值。若是確實小，則這一組節點能夠合併一個節點，其中包含了全部可能的結果。後剪枝是目前最廣泛的作法。測試

剪枝做爲決策樹後期處理的重要步驟，是必不可少的。沒有剪枝，就是一個徹底生長的決策樹，是過擬合的，須要去掉一些沒必要要的節點以使得決策樹模型更具備泛化能力。
spa

2.CART剪枝

實際上這個g(t)表示剪枝的閾值，即對於某一結點a，當整體損失函數中的參數alpha = g(t)時，剪和不剪整體損失函數是同樣的（這能夠在書中（5.27）和（5.28）聯立獲得）。
這時若是alpha稍稍增大，那麼不剪的總體損失函數就大於剪去的。即alpha大於g(t)該剪，剪了會使總體損失函數減少；alpha小於g(t)不應剪，剪了會使總體損失函數增大。
（請注意上文中的整體損失函數，對象能夠是以a爲根的子樹，也能夠是整個CART樹，對a剪枝先後兩者的整體損失函數增減是相同的。）對於同一棵樹的結點，alpha都是同樣的，
當alpha從0開始緩慢增大，總會有某棵子樹該剪，其餘子樹不應剪的狀況，即alpha超過了某個結點的g(t)，但尚未超過其餘結點的g(t)。這樣隨着alpha不斷增大，不斷地剪枝，就
獲得了n+1棵子樹，接下來只要用獨立數據集測試這n+1棵子樹，試試哪棵子樹的偏差最小就知道那棵是最好的方案了。
對象

By the way，書上第二版的最後貌似迭代過程是錯的，應該是回到步驟2, 由於，每次都須要逐步增長g(t)，這樣遍歷全部的g(t)以後就必定會剪成一顆只有一個根節點的樹，這個你們能夠好好理解。

這裏有張圖，說明爲何要選擇小的g(t)值，看看應該就能懂blog

爲何要選擇最小的g(t)呢？以圖中兩個點爲例，結點1和結點2，g(t)2大於g(t)1, 假設在全部結點中g(t)1最小，g(t)2最大，兩種選擇方法：當選擇最大值g(t)2，即結點2進行剪枝，
但此時結點1的不修剪的偏差大於修剪以後的偏差，即若是不修剪的話，偏差變大，依次類推，對其它全部的結點的g(t)都是如此，從而形成總體的累計偏差更大。反之，若是
選擇最小值g(t)1，即結點1進行剪枝，則其他結點不剪的偏差要小於剪後的偏差，不修剪爲好，且總體的偏差最小。從而以最小g(t)剪枝得到的子樹是該alpha值下的最優子樹！
it

這下該明白了吧，反正我是明白了。。。有不懂能夠留言學習方法

最後附上cart剪枝的正確流程圖：遍歷