決策樹先剪枝和後剪枝

(一)剪枝算法的簡介： 
剪枝一般是爲了避免樹的過於複雜，過於擬合而進行的一個動作，剪枝操作是一個全局的操作。

（二）預剪枝： 
預剪枝就是在樹的構建過程（只用到訓練集），設置一個閾值（樣本個數小於預定閾值或GINI指數小於預定閾值），使得當在當前分裂節點中分裂前和分裂後的誤差超過這個閾值則分列，否則不進行分裂操作。

（三）後剪枝： 
（1）後剪枝是在用訓練集構建好一顆決策樹後，利用測試集進行的操作。 
（2）算法： 
基於已有的樹切分測試數據： 
1.如果存在任一子集是一棵樹，則在該子集遞歸剪枝過程 
2.計算不合並的誤差 
3.如果合併會降低誤差的話，就將葉節點合併 
（3）在迴歸樹一般用總方差計算誤差（即用葉子節點的值減去所有葉子節點的均值）。 
後剪枝的算法包括： 
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)

（四）前剪枝和後剪枝的比較：  （1）前閾值的設定很敏感，一點點的變動，會引起整顆樹非常大的變動，不好設定。  （2）前剪枝生成比後剪枝簡潔的樹  （3）一般用後剪得到的結果比較好