決策樹（decision tree）(二)——剪枝
決策樹（decision tree）(二)——剪枝
**注：本博客爲周志華《機器學習》讀書筆記，雖然有一些本身的理解，可是其中仍然有大量文字摘自周老師的《機器學習》書。
決策樹系列博客：web
前面在決策樹（decision tree）（一）中介紹了幾種對結點劃分的方法（信息增益、信息增益率、基尼指數），在這篇博客裏主要介紹剪枝，即;算法
- 預剪枝（pre-pruning）
- 後剪枝（post-pruning）
首先剪枝（pruning）的目的是爲了不決策樹模型的過擬合。由於決策樹算法在學習的過程當中爲了儘量的正確的分類訓練樣本，不停地對結點進行劃分，所以這會致使整棵樹的分支過多，也就致使了過擬合。決策樹的剪枝策略最基本的有兩種：預剪枝（pre-pruning）和後剪枝（post-pruning）：機器學習
- 預剪枝（pre-pruning）：預剪枝就是在構造決策樹的過程當中，先對每一個結點在劃分前進行估計，若果當前結點的劃分不能帶來決策樹模型泛華性能的提高，則不對當前結點進行劃分而且將當前結點標記爲葉結點。
- 後剪枝（post-pruning）：後剪枝就是先把整顆決策樹構造完畢，而後自底向上的對非葉結點進行考察，若將該結點對應的子樹換爲葉結點可以帶來泛華性能的提高，則把該子樹替換爲葉結點。
1、預剪枝（pre-pruning）
關於預剪枝（pre-pruning）的基本概念，在前面已經介紹過了，下面就直接舉個例子來看看預剪枝（pre-pruning）是怎樣操做的。數據集爲（圖片來自西瓜書）：svg
這個數據集根據信息增益能夠構造出一顆未剪枝的決策樹（圖片來自西瓜書）：post
下面來看下具體的構造過程：
前面博客（決策樹（一））講過用信息增益怎麼構造決策樹，這邊仍是用信息增益構造決策樹，先來計算出全部特徵的信息增益值：性能
由於色澤和臍部的信息增益值最大，因此從這兩個中隨機挑選一個，這裏選擇臍部來對數據集進行劃分，這會產生三個分支，以下圖所示：學習
可是由於是預剪枝，因此要判斷是否應該進行這個劃分，判斷的標準就是看劃分先後的泛華性能是否有提高，也就是若是劃分後泛華性能有提高，則劃分；不然，不劃分。 下面來看看是否要用臍部進行劃分，劃分前：全部樣本都在根節點，把該結點標記爲葉結點，其類別標記爲訓練集中樣本數量最多的類別，所以標記爲好瓜，而後用驗證集對其性能評估，能夠看出樣本{4，5，8}被正確分類，其餘被錯誤分類，所以精度爲43.9%。劃分後： 劃分後的的決策樹爲：測試
則驗證集在這顆決策樹上的精度爲：5/7 = 71.4% > 42.9%。所以，用 臍部 進行劃分。
接下來，決策樹算法對結點 (2) 進行劃分，再次使用信息增益挑選出值最大的那個特徵，這裏我就不算了，計算方法和上面相似，信息增益值最大的那個特徵是「色澤」，則使用「色澤」劃分後決策樹爲：.net
但到底該不應劃分這個結點，仍是要用驗證集進行計算，能夠看到劃分後，精度爲：4/7=0.571<0.714，所以，預剪枝策略將禁止劃分結點 (2) 。對於結點 (3) 最優的屬性爲「根蒂」，劃分後驗證集精度仍爲71.4%，所以這個劃分不能提高驗證集精度，因此預剪枝將禁止結點 (3) 劃分。對於結點 (4) ，其所含訓練樣本已屬於同一類，因此再也不進行劃分。
因此基於預剪枝策略生成的最終的決策樹爲：3d
總結： 對比未剪枝的決策樹和通過預剪枝的決策樹能夠看出：預剪枝使得決策樹的不少分支都沒有「展開」，這不只下降了過擬合的風險，還顯著減小了決策樹的訓練時間開銷和測試時間開銷。可是，另外一方面，由於預剪枝是基於「貪心」的，因此，雖然當前劃分不能提高泛華性能，可是基於該劃分的後續劃分卻有可能致使性能提高，所以預剪枝決策樹有可能帶來欠擬合的風險。
2、後剪枝（post-pruning）
後剪枝就是先構造一顆完整的決策樹，而後自底向上的對非葉結點進行考察，若將該結點對應的子樹換爲葉結點可以帶來泛華性能的提高，則把該子樹替換爲葉結點。前面已經說過了，使用前面給出的訓練集會生成一顆（未剪枝）決策樹：
後剪枝算法首先考察上圖中的結點 (6)，若將以其爲根節點的子樹刪除，即至關於把結點 (6) 替換爲葉結點，替換後的葉結點包括編號爲{7,15}的訓練樣本，所以把該葉結點標記爲「好瓜」（由於這裏正負樣本數量相等，因此隨便標記一個類別），所以此時的決策樹在驗證集上的精度爲57.1%（爲剪枝的決策樹爲42.9%），因此後剪枝策略決定剪枝，剪枝後的決策樹以下圖所示：
接着考察結點 5，一樣的操做，把以其爲根節點的子樹替換爲葉結點，替換後的葉結點包含編號爲{6,7,15}的訓練樣本，根據「多數原則」把該葉結點標記爲「好瓜」，測試的決策樹精度認仍爲57.1%，因此不進行剪枝。
考察結點 2 ，和上述操做同樣，很少說了，葉結點包含編號爲{1,2,3,14}的訓練樣本，標記爲「好瓜」，此時決策樹在驗證集上的精度爲71.4%，所以，後剪枝策略決定剪枝。剪枝後的決策樹爲：
接着考察結點 3 ，一樣的操做，剪枝後的決策樹在驗證集上的精度爲71.4%，沒有提高，所以不剪枝；對於結點 1 ，剪枝後的決策樹的精度爲42.9%，精度降低，所以也不剪枝。
所以，基於後剪枝策略生成的最終的決策樹如上圖所示，其在驗證集上的精度爲71.4%。
總結：對比預剪枝和後剪枝，可以發現，後剪枝決策樹一般比預剪枝決策樹保留了更多的分支，通常情形下，後剪枝決策樹的欠擬合風險小，泛華性能每每也要優於預剪枝決策樹。但後剪枝過程是在構建徹底決策樹以後進行的，而且要自底向上的對樹中的全部非葉結點進行逐一考察，所以其訓練時間開銷要比未剪枝決策樹和預剪枝決策樹都大得多。
參考文獻 [1]: 周志華 《機器學習》