決策樹的過擬合問題
決策樹是一種分類器，通過ID3，C4.5和CART等算法可以通過訓練數據構建一個決策樹。但是，算法生成的決策樹非常詳細并且龐大，每個屬性都被詳細地加以考慮，決策樹的樹葉節點所覆蓋的訓練樣本都是“純”的。因此用這個決策樹來對訓練樣本進行分類的話，你會發現對于訓練樣本而言，這個樹表現完好，誤差率極低且能夠正確得對訓練樣本集中的樣本進行分類。訓練樣本中的錯誤數據也會被決策樹學習，成為決策樹的部分，但是對于測試數據的表現就沒有想象的那么好，或者極差，這就是所謂的過擬合(Overfitting)問題。
決策樹的剪枝
決策樹的剪枝有兩種思路：預剪枝（Pre-Pruning）和后剪枝（Post-Pruning）
預剪枝（Pre-Pruning）
在構造決策樹的同時進行剪枝。所有決策樹的構建方法，都是在無法進一步降低熵的情況下才會停止創建分支的過程，為了避免過擬合，可以設定一個閾值，熵減小的數量小于這個閾值，即使還可以繼續降低熵，也停止繼續創建分支。但是這種方法實際中的效果并不好。
后剪枝（Post-Pruning）
決策樹構造完成后進行剪枝。剪枝的過程是對擁有同樣父節點的一組節點進行檢查，判斷如果將其合并，熵的增加量是否小于某一閾值。如果確實小，則這一組節點可以合并一個節點，其中包含了所有可能的結果。后剪枝是目前最普遍的做法。后剪枝的剪枝過程是刪除一些子樹，然后用其葉子節點代替，這個葉子節點所標識的類別通過大多數原則(majority class criterion)確定。所謂大多數原則，是指剪枝過程中, 將一些子樹刪除而用葉節點代替,這個葉節點所標識的類別用這棵子樹中大多數訓練樣本所屬的類別來標識,所標識的類 稱為majority class ，（majority class 在很多英文文獻中也多次出現）。
后剪枝算法
后剪枝算法有很多種，這里簡要總結如下：
Reduced-Error Pruning (REP,錯誤率降低剪枝）
這個思路很直接，完全的決策樹不是過度擬合么，我再搞一個測試數據集來糾正它。對于完全決策樹中的每一個非葉子節點的子樹，我們嘗試著把它替換成一個葉子節點，該葉子節點的類別我們用子樹所覆蓋訓練樣本中存在最多的那個類來代替，這樣就產生了一個簡化決策樹，然后比較這兩個決策樹在測試數據集中的表現，如果簡化決策樹在測試數據集中的錯誤比較少，那么該子樹就可以替換成葉子節點。該算法以bottom-up的方式遍歷所有的子樹，直至沒有任何子樹可以替換使得測試數據集的表現得以改進時，算法就可以終止。
Pessimistic Error Pruning (PEP，悲觀剪枝）
PEP剪枝算法是在C4.5決策樹算法中提出的， 把一顆子樹（具有多個葉子節點）用一個葉子節點來替代（我研究了很多文章貌似就是用子樹的根來代替）的話，比起REP剪枝法，它不需要一個單獨的測試數據集。
PEP算法首先確定這個葉子的經驗錯誤率（empirical）為（E+0.5）/N，0.5為一個調整系數。對于一顆擁有L個葉子的子樹，則子樹的錯誤數和實例數都是就應該是葉子的錯誤數和實例數求和的結果，則子樹的錯誤率為e，這個e后面會用到
子樹的錯誤率
然后用一個葉子節點替代子樹，該新葉子節點的類別為原來子樹節點的最優葉子節點所決定（這句話是從一片論文看到的，但是論文沒有講什么是最優，通過參考其他文章，貌似都是把子樹的根節點作為葉子，也很形象，就是剪掉所有根以下的部分），J為這個替代的葉子節點的錯判個數，但是也要加上0.5，即KJ+0.5。最終是否應該替換的標準為：
被替換子樹的錯誤數-標準差 > 新葉子錯誤數
出現標準差，是因為我們的子樹的錯誤個數是一個隨機變量，經過驗證可以近似看成是二項分布，就可以根據二項分布的標準差公式算出標準差，就可以確定是否應該剪掉這個樹枝了。子樹中有N的實例，就是進行N次試驗，每次實驗的錯誤的概率為e，符合B（N，e）的二項分布，根據公式，均值為Ne，方差為Ne（1-e），標準差為方差開平方。（二項分布的知識在文章最后）網上找到這個案例，來自西北工業大學的一份PPT，我個人覺得PPT最后的結論有誤
PEP案例
這個案例目的是看看T4為根的整個這顆子樹是不是可以被剪掉。樹中每個節點有兩個數字，左邊的代表正確，右邊代表錯誤。比如T4這個節點，說明覆蓋了訓練集的16條數據，其中9條分類正確，7條分類錯誤。我們先來計算替換標準不等式中，關于子樹的部分：子樹有3個葉子節點，分別為T7、T8、T9，因此L=3子樹中一共有16條數據（根據剛才算法說明把三個葉子相加），所以N=16子樹一共有7條錯誤判斷，所以E=7那么根據e的公式e=（7+0.5×3）/ 16 = 8.5 /16 = 0.53根據二項分布的標準差公式，標準差為（16×0.53×（1-0.53））^0.5 = 2.00子樹的錯誤數為“所有葉子實際錯誤數+0.5調整值” = 7 + 0.5×3 = 8.5把子樹剪枝后，只剩下T4，T4的錯誤數為7+0.5=7.5這樣， 8.5-2 < 7.5， 因此不滿足剪枝標準，不能用T4替換整個子樹。
Cost-Complexity Pruning(CCP，代價復雜度剪枝)
CART決策樹算法中用的就是CCP剪枝方法。也是不需要額外的測試數據集。
Minimum Error Pruning(MEP)
Critical Value Pruning(CVP)
Optimal Pruning(OPP)
Cost-Sensitive Decision Tree Pruning(CSDTP)
。
附錄
二項分布 Binomial Distribution
考察由n次隨機試驗組成的隨機現象，它滿足以下條件：
重復進行n次隨機試驗；
n次試驗相互獨立；
每次試驗僅有兩個可能結果；
每次試驗成功的概率為p，失敗的概率為1-p。
在上述四個條件下，設X表示n次獨立重復試驗中成功出現的次數，顯然X是可以取0，1，…，n等n+1個值的離散隨機變量，且它的概率函數為：
二項分布概率公式
這個分布稱為二項分布，記為b(n,p)。
二項分布的均值：E(X)=np
二項分布的方差：Var(X)=np(1-p)。
標準差就是方差開平方
舉個例子比較好理解。扔好多次硬幣就是一個典型的二項分布，符合四項條件：
扔硬幣看正反面是隨機的，我們重復進行好多次，比如扔5次
每次扔的結果沒有前后關聯，相互獨立
每次扔要么正面，要么反面
每次正面（看作成功）概率1/2, 反面（看作失敗）概率1-1/2 = 1/2 ，即這里p=0.5
于是這個實驗就符合B（5，0.5）的二項分布。那么計算扔5次硬幣，出現2次正面的概率，就可以帶入公式來求：P（X=2）= C(5，2)×(0.5)2×(0.5)3 = 31.25%這個實驗的的期望（均值）為np=5×0.5=2.5，意思是：每扔5次，都記錄正面次數，然后扔了好多好多的“5次”，這樣平均的正面次數為2.5次這個實驗的方差為np(1-p)=5×0.5×0.5=1.25，表示與均值的誤差平方和，表示波動情況。多說一句，二項分布在n很大時，趨近于正態分布。
作者：程sir
鏈接：http://www.jianshu.com/p/794d08199e5e
來源：簡書
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。