剪枝(pruning)是決策樹學習算法對付"過擬合"的主要手段基协。在決策樹學習中匈织，為了盡可能正確分類訓練樣本盆均，結(jié)點劃分過程將不斷重復，有時會造成決策樹分支過多肩碟，這時就可能因訓練樣本學得"太好"了强窖，以致于把訓練集自身的一些特點當做所有數(shù)據(jù)都具有的一般性質(zhì)而導致過擬合。因此削祈，可通過主動去掉一些分支來降低過擬合的風險翅溺。
決策樹葉剪枝的基本策略有"預剪枝"(prepruning)和"后剪枝"(postpruning)。預剪枝是指在決策樹生成過程中髓抑，對每個結(jié)點在劃分前先進行估計咙崎，若當前結(jié)點的劃分不能帶來決策樹泛化性能提升，則停止劃分并將當前結(jié)點標記為葉結(jié)點吨拍。
舉個例子：
上圖是西瓜數(shù)據(jù)集褪猛，只不過分為了兩部分羹饰，上半部分是訓練集伊滋，下半部分是驗證集。
重點解釋下面這張圖队秩。
首先笑旺，按照臍部對訓練集進行劃分，分成了三部分：
凹陷馍资，稍凹筒主，平坦。
對應的訓練集樣本分別為:{1,2,3,14}鸟蟹，{6,7,15,17}乌妙，{10,16}
觀察下圖，發(fā)現(xiàn)凹陷的訓練集樣本都劃分為了好瓜戏锹，但是14號很明顯是壞瓜冠胯，為什么也劃分為好瓜呢？
這是因為锦针，只要好瓜的比例大于等于50%荠察，就把該樣本集都歸類為好瓜置蜀。
那么凹陷對應的驗證集為:{4,5,13}。這幾個樣本也被分為好瓜悉盆，但是13號很明顯被分錯了盯荤。
同理，稍凹中焕盟，驗證集{8,9}也都被分為好瓜秋秤，很明顯9號被分錯了。
同理脚翘，平坦中灼卢，驗證集{11,12}都被分為壞瓜，這次不錯来农，都分對了鞋真。
所以驗證集精度為：*100% = 71.4%。
我們繼續(xù)對凹陷這一個分支進行劃分沃于。
基于信息增益準則將挑選出劃分屬性為：色澤涩咖。
如下圖所示，按照色澤繁莹，將訓練集樣本{1,2,3,14}劃分為了三部分：
青綠檩互、烏黑、淺白
對應的訓練集樣本進一步被細分為：{1}咨演，{2,3}闸昨，{14}
對應的驗證集進一步被細分為：{4,13}，{}雪标，{5}
其中青綠對應的訓練集為好瓜零院，那么驗證集也被分成了好瓜，但是很明顯13號被分錯了村刨。
烏黑對應的訓練集為好瓜告抄，那么驗證集也被分為了好瓜，但此時驗證集為空嵌牺，沒影響打洼。
淺白對應的訓練集為壞瓜，那么驗證集也被分為了壞瓜逆粹，但是很明顯5號被分錯了募疮。
所以呢，用色澤去劃分僻弹，導致驗證集中的13和5號都被分錯阿浓。
所以，綜合臍部劃分和色澤劃分蹋绽，目前有三個驗證集中的樣本被分錯芭毙，分別是：13筋蓖、5、9退敦。
所以粘咖，驗證集的精度為：*100% = 57.1%。
發(fā)現(xiàn)沒有侈百，用色澤進一步劃分瓮下，竟然導致精度下降。
所以钝域，直接把色澤劃分去掉讽坏，這就是預剪枝。
