機器學習算法(三) 決策樹 (二) 決策樹的剪枝

　　決策樹生成算法遞歸的產生決策樹，知道不能繼續下去爲止，這樣產生的樹往往對訓練數據的分類很準確，但是對爲止的數據不太友好，容易產生過擬合 問題，所以引入了剪枝這個話題。
　　首先剪枝（pruning）的目的是爲了避免決策樹模型的過擬合。決策樹的剪枝策略最基本的有兩種：預剪枝（pre-pruning）和後剪枝（post-pruning）：

• 預剪枝（pre-pruning）：預剪枝就是在構造決策樹的過程中，先對每個結點在劃分前進行估計，若果當前結點的劃分不能帶來決策樹模型泛華性能的提升，則不對當前結點進行劃分並且將當前結點標記爲葉結點。
• 後剪枝（post-pruning）：後剪枝就是先把整顆決策樹構造完畢，然後自底向上的對非葉結點進行考察，若將該結點對應的子樹換爲葉結點能夠帶來泛華性能的提升，則把該子樹替換爲葉結點。

預剪枝

　　關於預剪枝（pre-pruning）的基本概念，在前面已經介紹過了，下面就直接舉個例子來看看預剪枝（pre-pruning）是怎樣操作的。數據集爲（圖片來自西瓜書）：
，
通過ID3算法可以構建一個如下的決策樹：

計算出所有特徵的信息增益值：

因爲色澤和臍部的信息增益值最大，所以從這兩個中隨機挑選一個，這裏選擇臍部來對數據集進行劃分，這會產生三個分支，如下圖所示：

但是因爲是預剪枝，所以要判斷是否應該進行這個劃分，判斷的標準就是看劃分前後的泛華性能是否有提升，也就是如果劃分後泛華性能有提升，則劃分；否則，不劃分。

在測試集中：在沒有分類的時候，首先將測試集的所有數據都認爲是好瓜，發現只有4、5、8分類正確，那麼,正確率爲 3/7 = 0.428
在訓練集中：可以看到凹陷和稍凹的都是好瓜，平坦的不是好瓜
在測試集中：在進行分類的時候發現，4 5 8 11 12分類正確，那麼正確率提升，所以可以使用這個特徵進行分類
在凹陷中判斷色澤是否起到促進作用
在測試集中： 在沒有分類的時候，首先認爲凹陷的西瓜都是好瓜，那麼4 5分類正確，那麼準確率爲 2/3 = 0.666
在訓練集中 青綠 烏黑是好瓜，而淺白是壞瓜，
在測試集中：在進行分類的時候發現，4 5 8 11 12分類正確，那麼正確率提升，所以可以使用這個特徵進行分類，只分類對1個，所以說分類沒有促進作用，不可以這樣分。 （自己理解的結果和西瓜書裏面差別比較大，期待指正）

總結： 對比未剪枝的決策樹和經過預剪枝的決策樹可以看出：預剪枝使得決策樹的很多分支都沒有「展開」，這不僅降低了過擬合的風險，還顯著減少了決策樹的訓練時間開銷和測試時間開銷。但是，另一方面，因爲預剪枝是基於「貪心」的，所以，雖然當前劃分不能提升泛華性能，但是基於該劃分的後續劃分卻有可能導致性能提升，因此預剪枝決策樹有可能帶來欠擬合的風險。

後剪枝

總結：對比預剪枝和後剪枝，能夠發現，後剪枝決策樹通常比預剪枝決策樹保留了更多的分支，一般情形下，後剪枝決策樹的欠擬合風險小，泛華性能往往也要優於預剪枝決策樹。但後剪枝過程是在構建完全決策樹之後進行的，並且要自底向上的對樹中的所有非葉結點進行逐一考察，因此其訓練時間開銷要比未剪枝決策樹和預剪枝決策樹都大得多。

參考：周志華 《機器學習》