決策樹的過擬合問題
決策樹是一種分類器仲闽，通過ID3腋腮，C4.5和CART等算法可以通過訓(xùn)練數(shù)據(jù)構(gòu)建一個(gè)決策樹窍侧。但是停撞，算法生成的決策樹非常詳細(xì)并且龐大瓷蛙，每個(gè)屬性都被詳細(xì)地加以考慮悼瓮，決策樹的樹葉節(jié)點(diǎn)所覆蓋的訓(xùn)練樣本都是“純”的。因此用這個(gè)決策樹來對(duì)訓(xùn)練樣本進(jìn)行分類的話艰猬，你會(huì)發(fā)現(xiàn)對(duì)于訓(xùn)練樣本而言横堡，這個(gè)樹表現(xiàn)完好，誤差率極低且能夠正確得對(duì)訓(xùn)練樣本集中的樣本進(jìn)行分類冠桃。訓(xùn)練樣本中的錯(cuò)誤數(shù)據(jù)也會(huì)被決策樹學(xué)習(xí)命贴，成為決策樹的部分，但是對(duì)于測(cè)試數(shù)據(jù)的表現(xiàn)就沒有想象的那么好食听，或者極差胸蛛，這就是所謂的過擬合(Overfitting)問題。
決策樹的剪枝
決策樹的剪枝有兩種思路：預(yù)剪枝（Pre-Pruning）和后剪枝（Post-Pruning）
預(yù)剪枝（Pre-Pruning）
在構(gòu)造決策樹的同時(shí)進(jìn)行剪枝樱报。所有決策樹的構(gòu)建方法葬项，都是在無法進(jìn)一步降低熵的情況下才會(huì)停止創(chuàng)建分支的過程，為了避免過擬合迹蛤，可以設(shè)定一個(gè)閾值玷室，熵減小的數(shù)量小于這個(gè)閾值，即使還可以繼續(xù)降低熵笤受，也停止繼續(xù)創(chuàng)建分支。但是這種方法實(shí)際中的效果并不好敌蜂。
后剪枝（Post-Pruning）
決策樹構(gòu)造完成后進(jìn)行剪枝箩兽。剪枝的過程是對(duì)擁有同樣父節(jié)點(diǎn)的一組節(jié)點(diǎn)進(jìn)行檢查，判斷如果將其合并章喉，熵的增加量是否小于某一閾值汗贫。如果確實(shí)小，則這一組節(jié)點(diǎn)可以合并一個(gè)節(jié)點(diǎn)秸脱，其中包含了所有可能的結(jié)果落包。后剪枝是目前最普遍的做法。
后剪枝的剪枝過程是刪除一些子樹摊唇，然后用其葉子節(jié)點(diǎn)代替咐蝇，這個(gè)葉子節(jié)點(diǎn)所標(biāo)識(shí)的類別通過大多數(shù)原則(majority class criterion)確定。所謂大多數(shù)原則巷查，是指剪枝過程中, 將一些子樹刪除而用葉節(jié)點(diǎn)代替,這個(gè)葉節(jié)點(diǎn)所標(biāo)識(shí)的類別用這棵子樹中大多數(shù)訓(xùn)練樣本所屬的類別來標(biāo)識(shí),所標(biāo)識(shí)的類 稱為majority class 有序，（majority class 在很多英文文獻(xiàn)中也多次出現(xiàn)）。
后剪枝算法
后剪枝算法有很多種岛请，這里簡(jiǎn)要總結(jié)如下：
Reduced-Error Pruning (REP,錯(cuò)誤率降低剪枝）
這個(gè)思路很直接旭寿，完全的決策樹不是過度擬合么，我再搞一個(gè)測(cè)試數(shù)據(jù)集來糾正它崇败。對(duì)于完全決策樹中的每一個(gè)非葉子節(jié)點(diǎn)的子樹盅称，我們嘗試著把它替換成一個(gè)葉子節(jié)點(diǎn)，該葉子節(jié)點(diǎn)的類別我們用子樹所覆蓋訓(xùn)練樣本中存在最多的那個(gè)類來代替，這樣就產(chǎn)生了一個(gè)簡(jiǎn)化決策樹缩膝，然后比較這兩個(gè)決策樹在測(cè)試數(shù)據(jù)集中的表現(xiàn)混狠，如果簡(jiǎn)化決策樹在測(cè)試數(shù)據(jù)集中的錯(cuò)誤比較少，那么該子樹就可以替換成葉子節(jié)點(diǎn)逞盆。該算法以bottom-up的方式遍歷所有的子樹檀蹋，直至沒有任何子樹可以替換使得測(cè)試數(shù)據(jù)集的表現(xiàn)得以改進(jìn)時(shí)，算法就可以終止云芦。
Pessimistic Error Pruning (PEP俯逾，悲觀剪枝）
PEP剪枝算法是在C4.5決策樹算法中提出的， 把一顆子樹（具有多個(gè)葉子節(jié)點(diǎn)）用一個(gè)葉子節(jié)點(diǎn)來替代（我研究了很多文章貌似就是用子樹的根來代替）的話舅逸，比起REP剪枝法桌肴，它不需要一個(gè)單獨(dú)的測(cè)試數(shù)據(jù)集。
PEP算法首先確定這個(gè)葉子的經(jīng)驗(yàn)錯(cuò)誤率（empirical）為（E+0.5）/N琉历，0.5為一個(gè)調(diào)整系數(shù)坠七。對(duì)于一顆擁有L個(gè)葉子的子樹，則子樹的錯(cuò)誤數(shù)和實(shí)例數(shù)都是就應(yīng)該是葉子的錯(cuò)誤數(shù)和實(shí)例數(shù)求和的結(jié)果旗笔，則子樹的錯(cuò)誤率為e彪置，這個(gè)e后面會(huì)用到
子樹的錯(cuò)誤率
然后用一個(gè)葉子節(jié)點(diǎn)替代子樹，該新葉子節(jié)點(diǎn)的類別為原來子樹節(jié)點(diǎn)的最優(yōu)葉子節(jié)點(diǎn)所決定（這句話是從一片論文看到的蝇恶，但是論文沒有講什么是最優(yōu)拳魁，通過參考其他文章，貌似都是把子樹的根節(jié)點(diǎn)作為葉子撮弧，也很形象潘懊，就是剪掉所有根以下的部分），J為這個(gè)替代的葉子節(jié)點(diǎn)的錯(cuò)判個(gè)數(shù)贿衍，但是也要加上0.5授舟，即KJ+0.5。最終是否應(yīng)該替換的標(biāo)準(zhǔn)為：
被替換子樹的錯(cuò)誤數(shù)-標(biāo)準(zhǔn)差 > 新葉子錯(cuò)誤數(shù)
出現(xiàn)標(biāo)準(zhǔn)差贸辈，是因?yàn)槲覀兊淖訕涞腻e(cuò)誤個(gè)數(shù)是一個(gè)隨機(jī)變量释树，經(jīng)過驗(yàn)證可以近似看成是二項(xiàng)分布，就可以根據(jù)二項(xiàng)分布的標(biāo)準(zhǔn)差公式算出標(biāo)準(zhǔn)差裙椭，就可以確定是否應(yīng)該剪掉這個(gè)樹枝了躏哩。子樹中有N的實(shí)例，就是進(jìn)行N次試驗(yàn)揉燃，每次實(shí)驗(yàn)的錯(cuò)誤的概率為e扫尺，符合B（N，e）的二項(xiàng)分布炊汤，根據(jù)公式正驻，均值為Ne弊攘，方差為Ne（1-e），標(biāo)準(zhǔn)差為方差開平方姑曙。
（二項(xiàng)分布的知識(shí)在文章最后）
網(wǎng)上找到這個(gè)案例襟交，來自西北工業(yè)大學(xué)的一份PPT，我個(gè)人覺得PPT最后的結(jié)論有誤
PEP案例
這個(gè)案例目的是看看T4為根的整個(gè)這顆子樹是不是可以被剪掉伤靠。
樹中每個(gè)節(jié)點(diǎn)有兩個(gè)數(shù)字捣域，左邊的代表正確，右邊代表錯(cuò)誤宴合。比如T4這個(gè)節(jié)點(diǎn)焕梅，說明覆蓋了訓(xùn)練集的16條數(shù)據(jù)，其中9條分類正確卦洽，7條分類錯(cuò)誤贞言。
我們先來計(jì)算替換標(biāo)準(zhǔn)不等式中，關(guān)于子樹的部分：
子樹有3個(gè)葉子節(jié)點(diǎn)阀蒂，分別為T7该窗、T8、T9蚤霞，因此L=3
子樹中一共有16條數(shù)據(jù)（根據(jù)剛才算法說明把三個(gè)葉子相加）酗失，所以N=16
子樹一共有7條錯(cuò)誤判斷，所以E=7
那么根據(jù)e的公式e=（7+0.5×3）/ 16 = 8.5 /16 = 0.53
根據(jù)二項(xiàng)分布的標(biāo)準(zhǔn)差公式昧绣，標(biāo)準(zhǔn)差為（16×0.53×（1-0.53））^0.5 = 2.00
子樹的錯(cuò)誤數(shù)為“所有葉子實(shí)際錯(cuò)誤數(shù)+0.5調(diào)整值” = 7 + 0.5×3 = 8.5
把子樹剪枝后级零，只剩下T4，T4的錯(cuò)誤數(shù)為7+0.5=7.5
這樣滞乙， 8.5-2 < 7.5， 因此不滿足剪枝標(biāo)準(zhǔn)鉴嗤，不能用T4替換整個(gè)子樹斩启。
Cost-Complexity Pruning(CCP，代價(jià)復(fù)雜度剪枝)
CART決策樹算法中用的就是CCP剪枝方法醉锅。
Minimum Error Pruning(MEP)
Critical Value Pruning(CVP)
Optimal Pruning(OPP)
Cost-Sensitive Decision Tree Pruning(CSDTP)
