決策樹的剪枝算法

作者：柏安之   審稿：歡暢  

剪****枝過程

樹一旦生成後，便進入第二階段——修剪階段。儘管我們希望能得到 “完美”、“完全” 分類訓練樣例的決策樹，但每個葉子節點都是 “純的” 並不見得就是好事。

數據中很有可能出現噪聲點和離羣點，在建立決策樹的時候，便會出現一些反應訓練樣例中的異常的分枝，即會產生過度擬合。

Quinlan 教授很早便發現了這個問題，他曾經做過一個實驗，在某個數據集上，過度擬合的決策樹的錯誤率竟然高於一個經過簡化的決策樹的錯誤率！所以在實際應用 C4.5 算法建立決策樹時，剪枝是必須要進行的步驟，其原則是正確、準確、高效。

1

預剪枝

從策略上來講，剪枝可以分爲兩種：預剪枝（Pre-Pruning）和後剪枝（Post-Pruning）。預剪枝是在構建決策樹的時候同時進行剪枝工作，當發現分類有偏差時就及早停止（比如決定在某個節點不再分裂或劃分訓練元組的子集），一旦停止，該節點就成爲葉子節點。

預剪枝的方法有很多，如：

①提前設定決策樹的高度，當達到這個高度時，就停止構建決策樹；

②當達到某節點的實例具有相同的特徵向量，也可以停止樹的生長；

③提前設定某個閾值，當達到某個節點的樣例個數小於該閾值的時候便可以停止樹的生長，但這種方法的缺點是對數據量的要求較大，無法處理數據量較小的訓練樣例；

④同樣是設定某個閾值，每次擴展決策樹後都計算其對系統性能的增益，若小於該閾值，則讓它停止生長。

預剪枝的顯著缺點是視野效果。因爲剪枝是伴隨着構建決策樹同時進行的，構建者無法預知下一步可能會發生的事，會出現某種情況，在相同標準下，當前決策樹不滿足要求最開始的構建要求、構建者進行了剪枝，但實際上若進行進一步構建後、決策樹又滿足了要求。這種情況下，預剪枝會過早停止決策樹的生長。

C4.5 算法常選擇後剪枝的方法消除決策樹的過度擬合——

2

後剪枝

後剪枝是人們普遍關注的決策樹剪枝策略，與預剪枝恰好相反，後剪枝的執行步驟是先構造完成完整的決策樹，再通過某些條件遍歷樹進行剪枝，其主要思路是通過刪除節點的分支並用樹葉節點替換，剪去完全成長的樹的子樹，這個節點所標識的類別通過大多數原則（majority class criterion）確定（既將一些子樹刪除而用葉子節點代替，這個葉節點所表示的類別用這棵子樹中的大多數訓練樣本所屬類別來進行標識），其類別稱爲 Majority Class。

目前主要應用的後剪枝方法有四種：悲觀錯誤剪枝（Pessimistic Error Pruning，PEP），最小錯誤剪枝（Minimum Error Pruning，MEP），代價複雜度剪枝（Cost-Complexity Pruning，CCP），基於錯誤的剪枝（Error-Based Pruning，EBP）。C4.5 算法採用悲觀錯誤剪枝，所以本文將重點闡述這一方法的工作原理，對其他三種只做簡單介紹。

1

悲觀錯誤剪枝

    在講解悲觀剪枝思路的時候，將會運用統計學的相關知識，所以我們將對這部分知識進行粗略的複習，再進行悲觀錯誤剪枝的學習。

    首先，我們認爲決策樹構建期間的錯分樣本數分佈近似於二項分佈 X~b(n,p)，那麼其均值與方差可得：u=np , σ2=npq（其中 q=1-p）。若 np≥4 且 nq≥4，二項概率分佈 p(y) 逼近於正態分佈，如下圖所示：

  由上圖我們可以看到 P(Y≤2) 是在正態曲線下 Y=2.5 的左端面積。只注意到 Y=2 的左端面積是不合適的，因爲它省略了相應於 Y=2 的的一半概率的長方形。爲了修正，用連續概率分佈區近似離散概率分佈，在計算概率之前我們需要將 2 增加 0.5；值 0.5 被稱爲二項概率分佈近似的連續性修正因子，因此 P(Y≤a)≈P(Z<(a+0.5-np/(npq)1/2))。

後文提到的 Quinlan 教授引入的 “基於二項分佈的連續校正公式” 則基於此思想。

悲觀錯誤剪枝是 Quinlan 在 1987 年提出，通過比較剪枝前和剪枝後的錯分樣本率來判斷是否進行剪枝。我們需要明確的是，利用 C4.5 或其他算法構建出來的決策樹在對不同測試集進行分類的時候，其錯分樣本率並不相同。我們之所以剪枝是爲了避免過渡擬合或者決策樹太過龐大帶來的可能產生冗餘工作量，而並非爲了降低錯分樣本數。

此外，需要注意的是，PEP 的特點是不需要獨立的剪枝集，而是既採用訓練集來生成決策樹又用它來進行剪枝，而是類似於用 A 來驗證 A，因此，產生的錯分樣本率 r(t) 會偏向於訓練集——或者說對準確率的評估 “過於樂觀”——無法得到最優的剪枝樹。爲此，需要加上一個懲罰來調節從訓練集得到的錯誤率。Quinlan 選擇引入了一個基於二項分佈的連續校正公式對在訓練集中產生的錯分樣本率進行校正，連續校正後的錯分樣本率 r’(t)=[e(t)+0.5]/n(t)。爲計算簡單起見，接下來的闡述將採用錯分樣本數而非錯分樣本率。

經過連續矯正之後，對節點 t 進行剪枝產生的錯分樣本數 e’(t)=e(t)+1/2；非剪枝的錯分樣本數則變爲 e’(Tt)=∑[e(s)+0.5]，其中 s∈{ Tt 子樹的所有葉子節點}。進一步，由於誤差近似看成是二項式分佈，根據 u = np, σ2=npq，可引入子樹 Tt 的服從二項分佈的標準錯誤（標準差）即：

SE (e’(Tt)) = [e’(Tt)·(n(t) - e(Tt))/ n(t) ]1/ 2

之所以引入標準差是因爲我們目前所求的錯分樣本數（率）只是該訓練集在這個決策樹模型下的錯分樣本率，而不是決策樹的錯分率——我們所做的只是利用某一個或某幾個訓練集產生的錯分樣本率對整體進行估計，最終所能得到的是錯分樣本率在某一置信區間下的置信區間。而我們判斷是否進行剪枝，則是根據剪枝之後的新的錯分樣本數是否滿足我們對錯分樣本數範圍的要求，即新錯分樣本數與規定置信水平的置信區間的上限的大小關係。那麼首先，我們需要複習有關置信區間的內容：

設θ'在大樣本下服從 E(θ') = θ, 標準誤差爲σ'的正態分佈，那麼θ在置信度等於 (1 - α) 的置信區間是：

θ'± Z α/2 σ'

基於上述思想，我們可以獲得根據訓練集兼剪枝集估計出的錯分樣本數的置信區間上限爲

e’(Tt)+SE (e’(Tt))

    PEP 算法採用自頂向下的順序遍歷完全決策樹 Tmax，對每個內部節點 t 都注意比較其 e’(t) 與 e’(Tt)+SE (e’(Tt)) 兩者間的大小，如滿足 e’(t)≤e’(Tt)+SE (e’(Tt))，就進行剪枝——刪除以 t 爲根節點的子樹而以一個葉子節點代之。

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

2

 最小****錯誤剪枝

Niblett 與 Bratko 在 1986 年提出該剪枝算法，是利用拉普拉斯 (Laplace) 概率估計來提高 ID3 算法在噪聲域中的性能, 1991 年由 Cestnik 與 Bratko 利用 Bayesian 概率估計對 MEP 進行了改進。

MEP 希望通過剪枝得到一棵相對於獨立數據集來說具有最小期望錯誤率 (Expected Error Rate) 的決策樹。所使用的獨立數據集是用來簡化對未知樣本的錯分樣本率的估計的，並不意味真正使用了獨立的剪枝集，實際情況是無論早期版本還是改進版本均只利用了訓練集的信息。

定義樣本達到節點 t 且屬於第 i 類的期望概率：Pt=[ ni(t)+paim]/n(t)+m，其中 pai 爲由訓練集得來的屬於第 i 類的先驗概率，m 表示先驗概率對期望概率 pi(t) 的影響程度，爲簡單起見，認爲所有類別的 m 均相同。

自底向上計算每個內部節點 t 的期望錯誤率 STE(t)，成爲靜態錯誤，當 m=k，pai=1/k，STE(t)=[e(t)+k-1]/[n(t)+k]；樹 Tt 的期望錯誤率稱爲動態錯誤率 DYE(t)，是其子節點的期望錯誤加權和。MEP 自底向上順序遍歷完全決策樹並計算 STE(t) 與 DYE(t)，若滿足 STE(t)≤DYE(t) 時則剪枝。

3

基於錯誤剪枝

該算法可以被認爲是悲觀錯誤剪枝算法的改進，在剪枝過程中，EBP 無需專用的剪枝集，同樣將訓練集用於生成決策樹及修剪決策樹。在 C4.5 算法中，同樣會採用這一種剪枝方法。

從概率的角度來看，錯分樣本率 r(t) 可看成是 n(t) 次實驗中，某事件發生 e(t) 次的概率，同時可得到關於錯分樣本率的一個置信區間 [LCF,UCF] , 對該置信區間設定一個置信水平 CF, 該置信區間的上限 UCF 可通過概率分佈 P(e(t)/n(t) ≤ UCF) =CF 求得，並用該上限作爲對期望錯誤率的估計。CF 值用來控制剪枝, 值越高剪枝越少，值越低剪枝越多，在 C4.5 算法中，默認爲 0.25 , 並假設錯分樣本的概率服從二項分佈。

    EBP 算法與 PEP 算法不同的是 EBP 算法是自底向上進行剪枝，整體思想大致可分爲三步：

    首先，計算葉子節點的錯分樣本率估計的置信區間的上限；

    第二步，計算葉子節點的預測錯分樣本數；

    第三步，則是判斷是否剪枝以及如何剪枝——分別計算三種預測錯分樣本數: 

    (1) 計算以節點 t 爲根的子樹 Tt 的所有葉節點預測錯分樣本數之和, 記爲 E1;

    (2) 計算子樹 Tt 被剪枝以葉節點代替時的預測錯分樣本數, 記爲 E2;

    (3) 計算子樹 T1 的最大分支的預測錯分樣本數, 記爲 E3。

    對三個值進行比較,E2 最小時則把子樹 Tt 剪掉並代以一個葉節點；E3 最小時採用 “嫁接”(grafting) 策略，即用這個最大分枝來替代子樹 Tt; E1 最小則不進行剪枝。

4

代價複雜度剪枝

    本剪枝算法在 Breimen 等人開發的 CART 系統中得到實現，在本文中只做簡單說明。

    CCP 算法定義了代價和複雜度，以及一個可由用戶設置的衡量代價與複雜度之間的關係參數α，α=[R(t)-R(Tt)]/(|Nt|-1)。其中 R(t) 是子樹 Tt 被剪枝並待以葉子節點 t 後產生的錯誤樣本數，R(Tt) 表示沒有被剪枝時的錯誤樣本數。

    CCP 算法的主要步驟是對於完全決策樹的**每個非葉子節點計算阿爾法值****，**剪掉具有最小α值的子樹，直到剩下根節點，在這一步驟中可得到一系列的剪枝樹；之後用新的剪枝集對上一步驟中的各個剪枝樹進行評估，並找出最佳剪枝樹作爲結果。採用此算法的結果是將得到一棵錯分樣本數和數的規模相折中的決策樹。

參考文獻

[1] Han Jiawei，Micheline K. 數據挖掘：概念與技術 [M] TP274. 範明, 孟小峯 譯. 北京：機械工業出版社, 2001:70-218

[2] 毛國君，段立娟，王實. 數據挖掘原來與算法 [M]. 北京：清華大學出版社, 2005

[3] Quinlan J R. C4.5:Programs for Machine Learning[M]. NewYork:Morgan Kaufnan,1993

[4] Quinlan J R. Induction of decision tree[J]. Machine Learning 1986, 1(1):81-106

[5] 馮少榮. 決策樹算法的研究與改進 [J]. 廈門大學學報（自然科學版），2007，17（5）：16-18

[6] 李慧慧，萬武族. 決策樹分類算法 C4.5 中連續屬性過程處理的改進 [M] TP301. 1006-2475(2010)08-0008-03

[7] 黃愛輝. 決策樹 C4.5 算法的改進及應用 [J]. 科學技術與工程, 2009,9(1):34-36

[8] J.R.Quinlan. Improved Use of Continuous Attributes in C4.5[J]. Journal of Artificial Intelligence Rearch 4 (1996) 77-90

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/L-VyeKLuBG4kyC1zOSfzZg