決策樹的預剪枝與後剪枝

前言：

本次講解參考的還是周志華的《機器學習》，採用的是書中的樣例，按照我我的的理解對其進行了詳細解釋，但願你們能看得懂。機器學習

一、數據集

其中{1,2,3,6,7,10,14,15,16,17}爲測試集，{4,5,8,9,11,12,13}爲訓練集。性能

二、預剪枝

預剪枝是要對劃分先後泛化性能進行評估。對比決策樹某節點生成前與生成後的泛化性能。學習

（1）在未劃分前，根據訓練集，類別標記爲訓練樣例數最多的類別，因爲訓練集中的好瓜與壞瓜是相同多的類別，均爲5，所以任選其中一類，書中選擇了好瓜做爲標記類別。測試

當全部節點集中在根節點，全部訓練集屬於標記類別的僅有{4,5,8}，所以分類正確的是3/7*100%=42.9%spa

（2）計算訓練集的信息增益，得知臍部的信息增益最大，所以按照臍部進行劃分。又由於在訓練集中，凹陷特徵好瓜的佔比多，所以凹陷劃分爲好瓜，稍凹特徵好過佔比多，所以將其標記爲好瓜，所以按照臍部劃分的子樹結果以下：blog

劃分後，對比結果以下：ci

（3）在臍部劃分的基礎上，進一步計算凹陷、根蒂特徵下，其餘屬性的信息增益，根據計算結果可知，在凹陷的狀況下，色澤的信息增益最大，所以對於凹陷的西瓜，進一步肯定按照色澤進行劃分，劃分結果以下：table

對於凹陷數據，進一步按照色澤進行劃分後，對比劃分先後的準確性：class

對稍凹數據集，進一步計算其餘屬性的信息增益，肯定根蒂的信息增益最大，所以對稍凹，進一步按照根蒂進行劃分：基礎

對於稍凹數據，進一步按照根蒂進行劃分後，對比劃分先後的準確性：

（4）所以按照預剪枝，最終造成的決策樹以下圖，其泛化性爲71.4%。

由圖可知，預剪枝使得不少分支沒有展開，這不只下降了過擬合的風險，還顯著減小了決策樹的訓練時間開銷和測試時間。可是，有些分支雖當前不能提高泛化性。甚至可能致使泛化性暫時下降，但在其基礎上進行後續劃分卻有可能致使顯著提升，所以預剪枝的這種貪心本質，給決策樹帶來了欠擬合的風險。

三、後剪枝

後剪枝表示先從訓練集中生成一顆完整決策樹。

（1）我在今生成的決策樹上將測試集的數據在此樹上進行了標記，以下圖所示：

對比標記節點的劃分類與各數據的真實分類，計算準確率，以下表所示：

生成的決策樹，在驗證集上的準確度爲3/7*100%=42.9%

（2）後剪枝將從決策樹的底部往上進行剪枝，先看最底部的紋理，將其領銜的分支減掉，即將其換成葉子節點。因爲在訓練集上，替換後，包含的樣本號爲{7,15}，好瓜壞瓜比例相等，所以選擇好瓜進行標記，剪枝後的決策樹爲：

當減掉底部紋理劃分後，準確率提升，所以按照紋理劃分需裁剪掉。

（3）接着往上裁剪，此時應該是色澤部分，因爲在訓練集上，替換後，包含的樣本號爲{6,7,15}，好瓜（2個）多於壞瓜（1個），所以選擇好瓜進行標記，剪枝後的決策樹爲：

此時決策樹驗證集精度仍爲57.1%，所以可不進行剪枝，即對於臍部稍凹，根蒂稍蜷部分，可保留按照色澤進一步劃分。

（4）接下來，咱們看臍部凹陷分支。因爲在訓練集上，將色澤替換爲葉節點後，包含的樣本號爲{1,2,3,14}，好瓜（3個）多於壞瓜（1個），所以選擇好瓜進行標記，剪枝後的決策樹爲：

當減掉最左側色澤劃分後，準確率提升，所以按照色澤劃分需裁剪掉。

（5）整棵樹遍歷基本完成，所以該決策樹最終後剪枝的結果以下圖所示，其驗證精度爲71.4%。

四、總結

對比預剪枝與後剪枝生成的決策樹，能夠看出，後剪枝一般比預剪枝保留更多的分支，其欠擬合風險很小，所以後剪枝的泛化性能每每因爲預剪枝決策樹。但後剪枝過程是從底往上裁剪，所以其訓練時間開銷比前剪枝要大。