剪枝是決策樹學習算法應對過擬合的主要手段。學習過程中的節點劃分過程有時會造成決策樹分支過多,以至於把訓練集自身的一些特點當作所有數據都具有的一般性質導致過擬合。
決策樹剪枝的基本策略有「預剪枝」和「後剪枝」,二者都需要對於決策樹泛化能力是否提升進行判斷。所以採用留出法從數據集中劃分出驗證集。
下表是演示剪枝原理使用的數據集:
下圖是未剪枝的決策樹:
預剪枝是指生成過程中對每個節點劃分前先進行估計,如果當前節點劃分不能提升決策樹泛化能力,則停止劃分,當前節點標記爲葉節點
計算相關的信息增益之後,我們會選擇「臍部」這一屬性對訓練集劃分,根據上表,可以分成三個分支。我們需要進行預剪枝,所以要用驗證集進行判斷:
假設不使用「臍部」進行劃分,那麼決策樹就是一個葉節點,標記爲「好瓜」,這時候驗證集的正確率爲:
在使用」臍部「進行劃分後,圖中②、③、④節點分別包含的訓練樣本是 、 、 ,所以分支的3個節點被標記爲「好瓜」、「好瓜」、「壞瓜」。這是用驗證集進行驗證,編號爲 的樣本分類正確。這時候驗證集的正確率爲: ,所以應該使用「臍部」進行劃分。
此後的節點使用類似的方法剪枝,最終可以得到「臍部」劃分出的三個節點均不能繼續劃分。最終得到的決策樹如下圖:
對比兩個決策樹可以看出預剪枝顯著減少了時間開銷,並且降低了過擬合的風險。但是預剪枝基於貪心本質禁止分支展開,也帶來了欠擬合的風險。
後剪枝是先生成決策樹,然後自底向上的考察非葉節點,若將該節點對應的子樹替換爲葉節點能提升決策樹泛化能力,則將該子樹換爲葉節點。
未剪枝的決策樹驗證集accuracy爲42.9%,先考察把⑥節點替換爲葉節點,該節點包括 兩個樣本,因此將節點標記爲「好瓜」,此時驗證集精度提高到57.1%
類似的繼續考察其他節點(如果驗證集精度保持不變根據奧卡姆剃刀準則需要剪枝,但原書爲了畫圖方便選擇不剪枝),最終得到決策樹如下圖,驗證集精度爲71.4%
可以看出後剪枝保留了更多分支,欠擬合風險很小,且泛化性能往往優於預剪枝,但是該過程在決策樹完全生成之後,且要注意考察非葉節點,因此時間開銷要大得多。
周志華《機器學習》