就是要你明白機器學習系列--決策樹算法之悲觀剪枝算法(PEP)
前言
在機器學習經典算法中，決策樹算法的重要性想必大家都是知道的。不管是ID3算法還是比如C4.5算法等等，都面臨一個問題，就是通過直接生成的 完全決策樹對于訓練樣本來說是“過度擬合”的，說白了是太精確了。由于完全決策樹對訓練樣本的特征描述得“過于精確” ,無法實現對新樣本的合理分析, 所以此時它不是一棵分析新數據的最佳決策樹。解決這個問題的方法就是對決策樹進行剪枝，剪去影響預測精度的分支。常見的剪枝策略有預剪枝(pre -pruning)技術和后剪枝(post -pruning )技術兩種。預剪枝技術主要是通過建立某些規則限制決策樹的充分生長, 后剪枝技術則是待決策樹充分生長完畢后再進行剪枝。由于預剪枝技術運用較少，本系列將著重介紹后剪枝技術，本文將介紹的是悲觀剪枝技術。
一、統計學相關知識復習
1、置信區間：
設θ'在大樣本下服從E(θ') = θ, 標準誤差為σ'的正態分布，那么θ的(1 - α)100%置信區間是：
θ' +/- (Z α/2 ) σ'
2、二項式概率分布：
均值和方差分別是u = np, σ 2= npq ,其中p=每次實驗成功的概率， q=1-p。
3、二項分布的正態逼近
如果np>=4 且nq>=4 ,二項概率分布p(y)逼近于正態分布。如下圖
可以看到P(Y<=2)是在正態曲線下Y=2.5的左端面積。注意到Y=2的左端面積是不合適的，因為它省略了相應于Y=2的一半概率的長 方形。為了修正，用連續概率分布去近似離散概率分布，在計算概率之前我們需要將2增加0.5。值0.5稱為二項概率分布近似的連續性修正因子，因此
P(Y<=a) 約等于 P(Z< (a+0.5 - np/ ( npq) 1/2 ) )；
P(Y>=a) 約等于 P(Z> (a-0.5 - np/ ( npq)1/2) )
二、剪枝過程
對于后剪枝技術，在決策樹形成后，最先要做的就是剪枝。后剪枝的剪枝過程是刪除一些子樹，然后用其葉子節點代替，這個葉子節點所標識的類別通過大多數原則(majority class criterion)確定。所謂大多數原則，是指 剪枝過程中, 將 一些子樹刪除而用葉節點代替,這個葉節點所標識的類別用 這棵子樹中大多數訓練樣本所屬的類別來標識,所標識的類 稱為majority class ，（majority class 在很多英文文獻中也多次出現）。
三、悲觀剪枝--Pessimistic Error Pruning (PEP)
P EP后剪枝技術是由大師Quinlan提出的。它不需要像REP(錯誤率降低修剪)樣，需要用部分樣本作為測試數據，而是完全使用訓練數據來生成決策樹，又用這些訓練數據來完成剪枝。 決策樹生成和剪枝都使用訓 練集, 所以會產生錯分。現在我們先來介紹幾個定義。
T1為決策樹T的所有內部節點(非葉子節點)，
T2為決策樹T的所有葉子節點，
T3為T的所有節點，有T3=T1∪T2,
n(t)為t的所有樣本數,
n i (t)為t中類別i的所有樣本數，
e(t)為t中不屬于節點t所標識類別的樣本數
在剪枝時，我們使用
r(t)=e(t)/n(t)
就是當節點被剪枝后在訓練集上的錯誤率，而
, 其中s為t節點的葉子節點。
在此，我們把錯誤分布看成是二項式分布，由上面“二項分布的正態逼近”相關介紹知道，上面的式子是有偏差的，因此需要連續性修正因子來矯正數據，有
r‘(t)=[e(t) + 1/2]/n(t)
和
, 其中s為t節點的葉子節點，你不認識的那個符號為 t的所有葉子節點的數目
為了簡單，我們就只使用錯誤數目而不是錯誤率了，如下
e'(t) = [e(t) + 1/2]
接著求e'(Tt)的標準差，由于誤差近似看成是二項式分布，根據u = np, σ2=npq可以得到
當節點t滿足
則Tt就會被裁減掉。
四、總結
在學習機器學習中，由于涉及的知識比較多，面又很廣，所以大家一定要把數學，統計學，算法等相關知識學透徹，多總結歸納。而且這些知識一般比較晦 澀難懂，但看別人的博客往往由于他人對知識點的理解有誤，而導致對讀者本人的誤導，且博客是不具權威，不保證正確的，所以對機器學習這種嚴謹的學科更是需 要多參考，多閱讀特別是文獻，甚至是算法原著者的論文。同時對我理解有誤的地方，歡迎大家指出，再次表示感謝了。
五、推薦閱讀
想了解其他剪枝算法(REP, MEP, EBP)的可以參考這篇文章 http://52weis.com/articles.html?id=718_21
六、參考文獻
A Comparative Analysis of Methods for Pruning Decision Trees 1997（ISSUE）
THE EFFECTS OF PRUNING METHODS ON THE PREDICTIVE ACCURACY OF INDUCED（ISSUE）
決策樹后剪枝算法的研究 范 潔 楊岳湘（ISSUE）
決策樹剪枝方法的比較 魏紅寧 2005（ISSUE）
悲觀剪枝算法在學生成績決策樹中的應用 李萍 2014（ISSUE）