spark 決策樹剪枝 spss決策樹剪枝詳情 - spark 決策樹剪枝,決策樹,子樹,結點,誤分類,Spark,大數據 mob64ca1413c518 博客

決策樹——剪枝

本篇是決策樹系列的第二篇，介紹一下決策樹的剪枝過程。過擬合是決策樹構建過程中常見的問題，信息失衡、噪聲等問題都會導致過擬合，剪枝則是提高決策樹模型泛化能力的重要手段，下面對常用的剪枝方法作一些介紹。

1. 預剪枝

決策樹系列第一篇《分類：決策樹——樹的生長》中提到過，樹的生長是一種“完全”式的生長，終止條件也僅有“所有的樣本屬於同一類，或者所有的樣本具有相同的屬性值”這兩條，但有時可以再增加一些終止條件，提前結束樹的生長，這個過程相當於在一棵“完全”生長的樹上剪去一些枝幹，這就是預剪枝過程。例如，可以增加這樣一條生長終止條件：當結點劃分後度量參數（信息增益、增益率或者基尼指數）變化小於設定閾值時，則將該結點當作葉子結點，不予劃分。

預剪枝過程簡單，計算量也較小，但是它有兩個缺點，一個是前面提到的終止生長時設定的閾值，該值通常難以確定，另一個則是會出現“欠擬合”現象，在當前結點上的劃分效果不理想時，但其子女結點上的劃分效果可能會比較理想，預剪枝過程容易發生這種情況。

一般預剪枝方法在實際中不會用到。

2. 後剪枝

後剪枝是在決策樹生長停止之後進行的剪枝，按照剪枝的方向，分為從上至下(top-bottom)和從下至上(bottom-top)。後剪枝方法有多種，除了剪枝方向的區別外，主要的區別在在於剪枝的條件，現依據剪枝條件的不同，介紹一下常用的幾種後剪枝方法。

1.1 REP(Reduced Error Pruning)方法

REP方法是Quinlan教授提出的，採用從下至上(bottom-top)的剪枝方式。使用該方法時，需要將樣本劃分為訓練集和驗證集，然後從樹底到樹頂，將每個內部結點生成的子樹用該結點代替，實現剪枝，用驗證集來判斷剪枝前後的誤差，若剪枝後誤差增大，則取消剪枝，反之則剪枝。

從剪枝的過程來看，REP方法是比較簡單的，每個子樹只需要訪問一次，所以它的計算過程是線性的。該方法的缺點一個是需要將樣本集劃分為訓練集與驗證集，這在樣本量不足夠大時比較影響模型構建；另外一個是當驗證集/訓練集中包含的信息在訓練集/驗證集中未出現時，剪枝反而降低了模型泛化能力。

樣本量不大時一般不使用REP剪枝方法。

1.2 PEP(Pessimistic Error Pruning)方法

PEP方法是Quinlan教授為了彌補REP方法需要單獨的驗證集的缺點而提出的剪枝方法，模型的構建、剪枝過程使用同一個樣本集，該方法使用採用從上至下(top-bottom)的方式。由於剪枝時採用的同一樣本集，因此更趨向於不剪枝，畢竟更多的子樹能做更準確的分類，為此PEP方法中為每一個葉子結點引入了懲罰項

$\Omega$

，一般取

$\Omega =1/2$

。對於一棵二叉樹來説，

$\Omega =1/2$

意味着只要能夠改善一個訓練記錄的分類，就應該劃分結點；對於一棵m叉樹來説，

$\Omega =1/2$

意味着必須改善

$\left | m/2 \right |$

個訓練記錄的分類時才應該劃分結點，其中

$\left | m/2 \right |$

表示大於

spark 決策樹剪枝 spss決策樹剪枝_子樹_07

的最小整數。因此，在引入懲罰項後，更多的子樹就不一定能做到更準確的分類了。未引入懲罰項前，葉子結點

$t_{i}$

的誤分類率

$r(t_{i})$

定義為

$r(t_{i})=e(t_{i})/n(t_{i})$

(1)

$e(t_{i})$

為該結點上的誤分類數，

$n(t_{i})$

為該結點所包含的樣本數。引入懲罰項後，其誤差率定義為

$r(t_{i})=(e(t_{i})+1/2)/n(t_{i})$

(2) 假設一棵子樹的葉子結點數為k，則該子樹的誤分類數

spark 決策樹剪枝 spss決策樹剪枝_決策樹_14

與誤分類率

spark 決策樹剪枝 spss決策樹剪枝_spark 決策樹剪枝_15

分別為

$e(T_{i})=\sum_{i=1}^{k}e(t_{i})+k/2$

(3)

$r(T_{i})= \frac{\sum_{i=1}^{k}e(t_{i})+k/2}{\sum_{i=1}^{k}n(t_{i})}$

(4) 將該子樹剪掉、用葉子結點代替後，其誤分類數

spark 決策樹剪枝 spss決策樹剪枝_子樹_18

為

spark 決策樹剪枝 spss決策樹剪枝_結點_19

(5)

spark 決策樹剪枝 spss決策樹剪枝_決策樹_20

為未引入懲罰項前的誤分類數。對於指定的子樹，樹上的樣本數是確定的，因此可以用誤分類數代替誤分類率，按照REP方法中的剪枝策略，當滿足

$e'(T)\leqslant e(T_{i})$

(6)

時即將子樹剪掉。

引入了懲罰項後，剪枝條件還是比較嚴格的，拿二叉樹來説，很容易做到改善一個訓練樣本的分類結果，從而取消剪枝。為此，Quinlan教授重新定義了剪枝的條件。在一顆子樹上，一個樣本的分類結果只有“正確”和“錯誤”兩種，這實際上是一個伯努利過程，錯誤分類的概率為

spark 決策樹剪枝 spss決策樹剪枝_子樹_22

，當子樹上包含

spark 決策樹剪枝 spss決策樹剪枝_子樹_23

個樣本時，那麼這

spark 決策樹剪枝 spss決策樹剪枝_spark 決策樹剪枝_24

個樣本的分類結果就服從概率為

spark 決策樹剪枝 spss決策樹剪枝_子樹_25

的二項分佈，期望為

spark 決策樹剪枝 spss決策樹剪枝_子樹_26

，方差為

spark 決策樹剪枝 spss決策樹剪枝_誤分類_27

。對於一棵包含

spark 決策樹剪枝 spss決策樹剪枝_誤分類_28

個樣本的子樹，其誤分類率

$r(T_{i})$

是可以統計出來的(即已知的，見式(4))，即

$p=r(T_{i})=\frac{e(T_{i})}{n}$

則該子樹上被正確分類的樣本的標準差為

$SE[e(T_{i})]=\sqrt{\frac{e(T_{i})(n-e(T_{i}))}{n}}$

(7) 儘管當前子樹的誤分類數為

$e(T_{i})$

，但是參考其誤分類數的標準差來看，對於一些待分類的樣本，該子樹的誤分類數可能會達到

$e(T_{i})+SE[e(T_{i})]$

為此，Quinlan教授將子樹的剪枝條件放寬為

$e'(T)\leqslant e(T_{i})+SE[e(T_{i})]$

(8)

PEP方法是後剪枝方法中唯一採用從上至下(top-bottom)剪枝的方法，因而其有着與預剪枝方法一樣的優點，就是效率高，是後剪枝方法中精度較高的方法之一，並且不需要驗證數據集。

1.3 CCP(cost-complexity Pruning)方法

CCP方法是Breiman等人提出的，是CART算法中採用的剪枝方法，剪枝時採用從下至上(bottom-top)的方式。

首先，定義子樹的損失函數

$C_{\alpha }(T)=C(T)+\alpha |T|$

(9) 式(9)中，

spark 決策樹剪枝 spss決策樹剪枝_子樹_36

表示任意的子樹，

spark 決策樹剪枝 spss決策樹剪枝_結點_37

表示子樹對訓練數據的預測誤差（如基尼指數、誤分類率等，由於CART算法使用基尼指數作度量，因此這裏一般使用基尼指數），

spark 決策樹剪枝 spss決策樹剪枝_決策樹_38

表示子樹的葉子結點數，

$\alpha$

為子樹的參數(

$\alpha \geqslant 0$

)，

$C_{\alpha }(T)$

為指定參數

$\alpha$

下子樹

spark 決策樹剪枝 spss決策樹剪枝_決策樹_43

的整體損失。先來定義最優子樹：最優子樹是指在訓練樣本上損失函數最小的子樹。從式(9)中對子樹的損失函數定義可以看到，當

$\alpha$

較大時子樹葉子結點的個數（子樹的複雜度）對損失函數的影響較大，最優子樹偏小；當

$\alpha$

較小時子樹的預測誤差對損失函數影響較大，最優子樹偏大。極端情況下，當

$\alpha =0$

時整體樹是最優的，當

$\alpha \rightarrow \infty$

時根節點構成的單結點樹是最優的。可以證明，對於一個給定的

$\alpha$

值，最優子樹是唯一的，由於

$\alpha$

的取值範圍為

$[0,+\infty ]$

，因此在

$\alpha$

增大的過程中可以得到一系列的最優子樹。對於一個決策樹，由於內部結點個數是一定的，因此

$\alpha$

可能在一個區間範圍內對應的最優子樹都是同一棵子樹。接下來，考慮一下如何尋找給定

$\alpha$

值下的最優子樹。顯然，通過遞增

$\alpha$

值，然後遍歷樹上所有結點計算損失函數、得到最優子樹的方式是不現實的，

$\alpha$

值的連續變化導致這個計算複雜度難以估計，因此我們可以換一個思路來尋找最優子樹。試想一下，既然我們的目的就是為了剪枝，那何不採用遍歷樹上所有內部結點(非葉子結點)、逐個剪枝，比較得到的子樹的損失函數的方式來確定最優子樹呢？這個計算複雜度只與內部結點個數相關。具體的過程以樹的任一內部結點

spark 決策樹剪枝 spss決策樹剪枝_spark 決策樹剪枝_56

來説明，以結點

spark 決策樹剪枝 spss決策樹剪枝_誤分類_57

為根節點生成的子樹，其損失函數為

$C_{a}(T_{t})=C(T_{t})+\alpha \left | T_{t} \right |$

(10) 以結點

spark 決策樹剪枝 spss決策樹剪枝_spark 決策樹剪枝_59

替換子樹、得到單結點樹的損失函數為

$C_{\alpha }(t)=C(t)+\alpha$

(11) 當

$\alpha$

=0及充分小時，有如下關係

$C_{a}(T_{t})<C_{a}(t)$

(12) 隨着

$\alpha$

逐漸增大，到某個值時存在如下關係

$C_{a}(T_{t})=C_{a}(t)$

(13)

$\alpha$

再繼續增大時，不等式(12)將反向。當等式(13)成立時

$\alpha =\frac{C(t)-C(T_{t})}{|T_{t}|-1}$

(14) 此時將該子樹剪去(這裏剪去的意思是用單一結點代替其生成的子樹，後面不再説明)後損失函數不變，但是整體樹的結點更少，因此應該執行剪枝。對結點

spark 決策樹剪枝 spss決策樹剪枝_誤分類_67

來説，當公式(14)成立時，剪枝前後損失函數不變的只是它本身，但整體樹的損失函數由於

$\alpha$

的取值而發生變化，很顯然

$\alpha$

越小，餘下的樹的損失函數越小，也越優(可以參照公式(9)理解)。有人可能會想，那我剪去葉子結點更多的子樹可以嗎？答案是不可以，因為這會改變餘下的樹的預測誤差，由公式(12)可知反而會增大損失函數。從下至上，對樹的每一個內部結點按照公式(14)計算出

$\alpha$

值，選擇其中最小

$\alpha$

值對應的結點，將以該結點生成的子樹剪枝，完成本輪剪枝過程。説完了單輪的剪枝過程，現在我們以整體樹

$T_{0}$

為初始樹説明CPP方法中完整的剪枝過程。樹

$T_{0}$

經過第一輪剪枝後得到樹

$T_{1}$

，第一輪剪枝結點對應的

$\alpha$

值為

$\alpha_{1}$

（按照公式(14)計算出），那樹

$T_{1}$

是不是一個全局的最優子樹呢？不見得，就算不用驗證集進行驗證我們也可以這樣説，因為樹

$T_{1}$

只是

$\alpha$

取

$\alpha_{1}$

時的最優子樹，由前面所講內容及公式(12)可知，實際上樹

$T_{1}$

也是

$\alpha$

在

$[0,\alpha _{1}]$

上的最優子樹。如果只在樹

$T_{0}$

上變化

$\alpha$

值，不管

$\alpha$

取多少，根據公式(12)、(13)、(14)所説明的內容，最優的子樹仍然是樹

$T_{1}$

。因此，我們可以以樹

$T_{1}$

為初始樹，繼續下一輪剪枝，此時初始樹的結構變了，這樣可以得到最優子樹

$T_{2}$

及對應的

$\alpha_{2}$

（顯然

$\alpha _{2}>\alpha _{1}$

），然後以樹

$T_{2}$

為初始樹繼續這個過程，知道整體樹

$T_{0}$

的根節點，最終我們會得到一系列最優子樹

$T_{0},T_{1},...,T_{n}$

，這些最優子樹是訓練集上的最優子樹。在驗證集上使用交叉驗證法驗證

$T_{0},T_{1},...,T_{n}$

，其中表現最好的子樹將作為的剪枝結果。

1.4 EBP(Error-Base-Pruning)方法

EBP剪枝方法是C4.5算法中默認使用的剪枝方法，它採用的是一種從下至上的剪枝方式。

本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。

mob64ca1413c518 博客

mob64ca1413c518 博客

博客 / 詳情