謝小嬌包教包會決策樹之決策樹剪枝

謝小嬌包教包會決策樹之決策樹剪枝

大家好，我是謝小嬌。

事情有點多，而且煩，本來想說些政治不正確的話抱怨一下的，不過想想算了，這是一個正經的公眾號！

樓樓去喵星要幸福！

接上一次講的生成決策樹，下面給出一張圖。

?橫軸表示在決策樹創建過程中樹的結點總數，縱軸表示決策樹的預測精度。

?實線顯示的是決策樹在訓練集上的精度，虛線顯示的則是在一個獨立的測試集上測量出來的精度。

?可以看出隨著樹的增長， 在訓練樣集上的精度是單調上升的， 然而在獨立的測試樣例上測出的精度先上升後下降。

產生這種現象的原因如下：

?原因1：雜訊、樣本衝突，即錯誤的樣本數據。

?原因2：特徵即屬性不能完全作為分類標準。

特殊的，還有↓

?原因3：巧合的規律性，數據量不夠大。

這個時候，就需要對生成樹進行修剪，也就是剪枝。

剪枝通常有兩種做法：預剪枝和後剪枝。

預剪枝

?預剪枝就是在完全正確分類訓練集之前，較早地停止樹的生長。 具體在什麼時候停止決策樹的生長有多種不同的方法:

(1) 一種最為簡單的方法就是在決策樹到達一定高度的情況下就停止樹的生長。

(2) 到達此結點的實例具有相同的特徵向量，而不必一定屬於同一類， 也可停止生長。

(3) 到達此結點的實例個數小於某一個閾值也可停止樹的生長。

(4) 還有一種更為普遍的做法是計算每次擴張對系統性能的增益，如果這個增益值小於某個閾值則不進行擴展。

優點&缺點

?由於預剪枝不必生成整棵決策樹，且演算法相對簡單， 效率很高， 適合解決大規模問題。但是儘管這一方法看起來很直接， 但是 怎樣精確地估計何時停止樹的增長是相當困難的。

?預剪枝有一個缺點， 即視野效果問題 。 也就是說在相同的標準下，也許當前的擴展會造成過度擬合訓練數據，但是更進一步的擴展能夠滿足要求，也有可能準確地擬合訓練數據。這將使得演算法過早地停止決策樹的構造。

後剪枝

後剪枝，在已生成過擬合決策樹上進行剪枝，可以得到簡化版的剪枝決策樹。

這裡主要介紹四種：

1、REP-錯誤率降低剪枝

2、PEP-悲觀剪枝

3、CCP-代價複雜度剪枝

4、MEP-最小錯誤剪枝

REP(Reduced Error Pruning)方法

對於決策樹T 的每棵非葉子樹S , 用葉子替代這棵子樹. 如果 S 被葉子替代後形成的新樹關於D 的誤差等於或小於S 關於 D 所產生的誤差, 則用葉子替代子樹S

優點：

?REP 是當前最簡單的事後剪枝方法之一。

?它的計算複雜性是線性的。

?和原始決策樹相比，修剪後的決策樹對未來新事例的預測偏差較小。

缺點：

?但在數據量較少的情況下很少應用. REP方法趨於過擬合( overfitting) , 這是因為訓練數據集中存在的特性在剪枝過程中都被忽略了, 當剪枝數據集比訓練數據集小得多時 , 這個問題特別值得注意.

PEP(Pessimistic Error Pruning)方法

?為了克服 R EP 方法需要獨立剪枝數據集的缺點而提出的, 它不需要分離的剪枝數據集，為了提高對未來事例的預測可靠性, PEP 方法對誤差估計增加了連續性校正(continuity correction)。

e( t) 為節點 t 處誤差; i 為覆蓋 Tt 的葉子; Nt 為子樹 T t 的葉子數; n( t) 為在節點 t 處訓練事例的數.

前置知識：

在大樣本條件下，樣本比例

近似正態分布，期望為

，方差為

，通過置信區間知識，可以得到

我個人就是這麼理解公式的。

還有，公式里1/2是修正因子，突然冒出來看得很奇怪。我找了好久找到一張圖。

我這裡給出一種理解方式：當做二項分布的連續性校正（最後分類只有對和錯兩種情況。）

實例：

舉個計算例子：e』(t4)： 4+0.5=4.5；e』(Tt4) ： (1+0.5)+(2+0.5)= 4

優點：

?PEP方法被認為是當前決策樹事後剪枝方法中精度較高的演算法之一

?PEP 方法不需要分離的剪枝數據集, 這對於事例較少的問題非常有利

?它的計算時間複雜性也只和未剪枝樹的非葉節點數目成線性關係 .

缺點：

PEP是唯一使用自頂向下剪枝策略的事後剪枝方法, 這種策略會帶來與事前剪枝方法出 現的同樣問題, 那就是樹的某個節點會在該節點的子孫根據同樣準則不需要剪裁時也會被剪裁。

TIPS：

個人認為，其實以時間複雜度和空間複雜度為代價，PEP是可以自下而上的，這並不是必然的。

MEP(Minimum Error Pruning)方法

MEP 方法的基本思路是採用自底向上的方式, 對於樹中每個非葉節點, 首先計算該節點的誤差 Er(t) . 然後, 計算該節點每個分枝的誤差Er(Tt) , 並且加權相加, 權為每個分枝擁有的訓練樣本比例. 如果 Er(t) 大於 Er(Tt) , 則保留該子樹; 否則, 剪裁它.

假設：assumes that all the classes are equally likely.

n(t) 為節點 t 中的樣本總數; n c( t )為 t 中主類的樣本數目; k 為類數目 .

（個人認為這種演算法和PEP相似，也是引入了修正因子）

優點：

?MEP方法不需要獨立的剪枝數據集, 無論是初始版本, 還是改進版本, 在剪枝過程中, 使用的信息都來自於訓練樣本集.?它的計算時間複雜性也只和未剪枝樹的非葉節點數目成線性關係 .

缺點：

類別平均分配的前提假設現實幾率不大&對K太過敏感

對此，也有改進演算法，我沒有深入研究。

CCP(Cost-Complexity Pruning)方法

?CCP 方法就是著名的CART(Classificationand Regression Trees)剪枝演算法，它包含兩個步驟:

(1) 自底向上，通過對原始決策樹中的修剪得到一系列的樹 {T0,T1,T2,...,Tt}， 其中Tia 是由Ti中的一個或多個子樹被替換所得到的，T0為未經任何修剪的原始樹，幾為只有一個結點的樹。

(2) 評價這些樹，根據真實誤差率來選擇一個最優秀的樹作為最後被剪枝的樹。

α的理解：

實際上, 當 1 棵樹 T 在節點 t 處剪枝時, 它的誤差增加直觀上認為是R(t) - R (Tt) , 其中, R ( t) 為在節點 t 的子樹被裁剪後節點t 的誤差, R(Tt) 為在節點 t 的子樹沒被裁剪時子樹Tt的誤差. 然而, 剪枝後, T的葉子數減少了L(Tt) - 1, 其中, L(Tt) 為子樹Tt的葉子數, 也就是說,T的複雜性減少了. 因此, 考慮樹的複雜性因素, 樹分枝被裁剪後誤差增加率由 下式決定:

舉個計算例子：α(t4)=(4-(1+2)/80)/2-1=0.0125

好的，現在我們有了一系列的子樹，如何選擇呢？

即根據預測精度， 如何從{To,T1,T2,...,Tt}中選擇一棵最佳的樹。

作者提供了兩種截然不同的估計真實誤差的方法。其一是基於交叉驗證， 另一種基於獨立剪枝數據集。

?獨立數據集類似REP。如果使用獨立的剪枝數據集，CCP 明顯比 REP 方法存在一個缺點，它只能從{To,Ti,T2,...}中選擇最佳決策樹，而不是從原始樹中所有可能的子樹中獲到 。

?k-cv，即k番交叉驗證，即將數據集分成k分，前k-1生成樹，最後1份選擇最優樹，重複K次，再從這K個子樹中選取最優的子樹。

缺點：

生成子樹序列 T ( α) 所需要的時間和原決策樹非葉節點的關係是二次的, 這就意味著如果非葉節點的數目隨著訓練例子記錄數目線性增加, 則CCP方法的運行時間和訓練數據記錄數的關係也是二次的 . 這就比本文中將要介紹的其它剪枝方法所需要的時間長得多, 因為其它剪枝方法的運行時間和非葉節點的關係是線性的.

對比四種方法：

①MEP比PEP不準確，且樹大。兩者都不需要額外數據集，故當數據集小的時候可以用。對比公式，如果類（Label）多，則用MEP；PEP在數據集uncertain時錯誤多，不使用。

②REP最簡單且精度高，但需要額外數據集；CCP精度和REP差不多，但樹小。

③如果數據集多（REP&CCP←複雜但樹小）

④如果數據集小（MEP←不準確樹大&PEP←不穩定）

————————————————————————————————

資料來源：

《統計學習方法》

《An Empirical Comparison of Pruning Methods

for Decision Tree Induction》

《決策樹學習及其剪枝演算法研究》

《決策樹剪枝方法的比較-魏紅寧》

和雜七雜八的網上資料

後三篇都是論文，不知道怎麼引用-。-

推薦閱讀：