【機器學習】樹的剪枝策略

時間 2021-01-13

剪枝

決策樹剪枝分前剪枝(預剪枝)和後剪枝兩種形式.

決策樹爲什麼(WHY)要剪枝？原因是避免決策樹過擬合(Overfitting)樣本。前面的算法生成的決策樹非常詳細並且龐大，每個屬性都被詳細地加以考慮，決策樹的樹葉節點所覆蓋的訓練樣本都是「純」的。因此用這個決策樹來對訓練樣本進行分類的話，你會發現對於訓練樣本而言，這個樹表現完好，誤差率極低且能夠正確得對訓練樣本集中的樣本進行分類。訓練樣本中的錯誤數據也會被決策樹學習，成爲決策樹的部分，但是對於測試數據的表現就沒有想象的那麼好，或者極差，這就是所謂的過擬合(Overfitting)問題。Quinlan教授試驗，在數據集中，過擬合的決策樹的錯誤率比經過簡化的決策樹的錯誤率要高。

預剪枝

PrePrune：預剪枝，及早的停止樹增長。

通過提前停止樹的構造進行剪枝.

樹到達一定高度
節點下包含的樣本點小於一定數目
信息增益小於一定的閾值等等
節點下所有樣本都屬於同一個類別

後剪枝

後剪枝的剪枝過程是刪除一些子樹，然後用其葉子節點代替，這個葉子節點所標識的類別通過大多數原則(majority class criterion)確定。所謂大多數原則，是指剪枝過程中, 將一些子樹刪除而用葉節點代替,這個葉節點所標識的類別用這棵子樹中大多數訓練樣本所屬的類別來標識,所標識的類稱爲majority class ，（majority class 在很多英文文獻中也多次出現）。

後剪枝首先通過完全分裂構造完整的決策樹,允許過擬合,然後採取一定的策略來進行剪枝,常用的後剪枝策略包括:

降低錯誤剪枝 REP(Reduced Error Pruning)
悲觀錯誤剪枝 PEP(Pessimistic Error Pruning)
基於錯誤剪枝 EBP(Error Based Pruning)
代價-複雜度剪枝 CCP(Cost Complexity Pruning)
最小錯誤剪枝 MEP(Minimum Error Pruning)
等等

其實剪枝的準則是如何確定決策樹的規模，可以參考的剪枝思路有以下幾個：

使用訓練集合(Training Set）和驗證集合(Validation Set)，來評估剪枝方法在修剪結點上的效用
使用所有的訓練集合進行訓練，但是用統計測試來估計修剪特定結點是否會改善訓練集合外的數據的評估性能，如使用Chi-Square（Quinlan，1986）測試來進一步擴展結點是否能改善整個分類數據的性能，還是僅僅改善了當前訓練集合數據上的性能。
使用明確的標準來衡量訓練樣例和決策樹的複雜度，當編碼長度最小時，停止樹增長，如MDL(Minimum Description Length)準則。

我們先看下使用思路一來解決問題的集中後剪枝方法：

Reduced-Error Pruning(REP,錯誤率降低剪枝）

自底向頂剪枝

該剪枝方法考慮將書上的每個節點作爲修剪的候選對象，決定是否修剪這個結點有如下步驟組成：

1：刪除以此結點爲根的子樹

2：使其成爲葉子結點

3：賦予該結點關聯的訓練數據的最常見分類

4：當修剪後的樹對於驗證集合的性能不會比原來的樹差時，才真正刪除該結點

因爲訓練集合的過擬合，使得驗證集合數據能夠對其進行修正，反覆進行上面的操作，從底向上的處理結點，刪除那些能夠最大限度的提高驗證集合的精度的結點，直到進一步修剪有害爲止(有害是指修剪會減低驗證集合的精度)

REP是最簡單的後剪枝方法之一，不過在數據量比較少的情況下，REP方法趨於過擬合而較少使用。這是因爲訓練數據集合中的特性在剪枝過程中被忽略，所以在驗證數據集合比訓練數據集合小的多時，要注意這個問題。

儘管REP有這個缺點，不過REP仍然作爲一種基準來評價其它剪枝算法的性能。它對於兩階段決策樹學習方法的優點和缺點提供了了一個很好的學習思路。由於驗證集合沒有參與決策樹的創建，所以用REP剪枝後的決策樹對於測試樣例的偏差要好很多，能夠解決一定程度的過擬合問題。

Pessimistic Error Pruning (PEP，悲觀剪枝）

具體看https://www.jianshu.com/p/794d08199e5e

出現標準差，是因爲我們的子樹的錯誤個數是一個隨機變量，經過驗證可以近似看成是二項分佈，就可以根據二項分佈的標準差公式算出標準差，就可以確定是否應該剪掉這個樹枝了。子樹中有N的實例，就是進行N次試驗，每次實驗的錯誤的概率爲e，符合B（N，e）的二項分佈，根據公式，均值爲Ne，方差爲Ne（1-e），標準差爲方差開平方。

在上面這個例子中

剪枝前：Error=(7+3*0.5)/16

mean = N*e = 8.5

std = sqrt(error*(1-error)*N) = $\sqrt{Error*(1-Error)*N}$ =2

剪枝後：將T4的所有子樹剪掉之後，根據大多數原則重新計算錯分率，假設仍有7個樣本誤分。

Error_mean = (7+0.5)=7.5

判斷：

7.5 > 8.5-2

所以不剪枝

PEP優缺點

該算法被認爲是當前決策樹後剪枝算法中經度比較高的算法之一，但是仍存在有缺陷。首先，PEP算法是唯一使用Top-Down剪枝策略，這種策略會導致與預剪枝出現同樣的問題，將該結點的某子節點不需要被剪枝時被剪掉；另外PEP方法會有剪枝失敗的情況出現。

雖然PEP方法存在一些侷限性，但是在實際應用中表現出了較高的精度,。兩外PEP方法不需要分離訓練集合和驗證機和，對於數據量比較少的情況比較有利。再者其剪枝策略比其它方法相比效率更高，速度更快。因爲在剪枝過程中，樹中的每顆子樹最多需要訪問一次，在最壞的情況下，它的計算時間複雜度也只和非剪枝樹的非葉子節點數目成線性關係。

Cost-Complexity Pruning(CCP、代價複雜度)

CART用的就是CCP剪枝。

最後一句話感覺是ccp的重點，得到的最優決策樹可能並不是原決策樹的所有可能子樹，有可能出現新的決策樹。

比較

參考文章：

http://blog.sina.com.cn/s/blog_4e4dec6c0101fdz6.html

http://leijun00.github.io/2014/10/decision-tree-2/

https://www.jianshu.com/p/794d08199e5e

【機器學習】 樹的剪枝策略

剪枝

預剪枝