cart樹怎麼進行剪枝？

01-16

能否詳細介紹一下cart剪枝演算法流程？
推薦經典的剪枝論文？
謝謝。

這裡我就簡單講下CART剪枝的核心思想，純屬個人意見，如有不當，請指正。

在《統計學習方法法》中已經提到了決策樹的剪枝演算法了，理所當然，我們是順著書中提到的思路來理解下決策樹剪枝的關鍵步驟。我們定義了

$C_{alpha}(T) = sum_{t =1}^{vert Tvert}N_tH_t(T) + alphavert Tvert$

該定義表示了決策樹的損失函數。whaterver它是什麼，現在有了損失函數這個衡量標準，並且假設我們已經根據training set生成了一棵複雜的決策樹，且參數 $alpha$ 已知。演算法該如何實現決策樹的剪枝呢？

首先明確一個概念，原本躺在那的一堆數據集，在沒有決策規則被挖掘時，我們只能知道數據集中的分類標籤的情況。如銀行貸款問題中，銀行只知道有多少人可以貸款，有多少人不可以貸款，所以躺在那的數據集的不確定度是最高的。關於這部分的理解可以參看博文【決策樹之理解ID3演算法和C4.5演算法 - Demon-初來駕到 - 博客頻道 - CSDN.NET】，由此決策樹越複雜，整體數據的不確定度越低。（數據被規則所明確，即銀行在得知用戶有房子的情況下，能根據訓練數據統計出所有用戶都是可以貸款的，這樣的規則被銀行挖掘出來了。）那麼，顯而易見，規則越多，數據分類的不確定性將大大降低。

咱們來看看決策樹損失函數的定義。其中第一部分 $N_tH_t(T)$ 就是事物的不確定性次數。我們都知道存在雜訊的情況下，模型將趨於複雜。在決策樹中也就是 $vert Tvert$ 的數值越大。再來看看損失函數中的 $alphavert Tvert$ ，假設參數 $alpha$ 已知的，那麼複雜的模型，所帶來的結果就是 $alphavert Tvert$ 也將增大。且決策樹存在過擬合現象，那麼為了使得損失函數減小，有兩種辦法：

降低第一部分的不確定次數，但我們知道這是不可能的了，因為降低不確定次數的辦法是再找尋一個特徵，或者找尋特徵的最優切分點。這在生成決策時就已經決定了，無法改變。
進行剪枝操作，這是可以的。剪枝最明顯地變化就是葉結點個數變少。假設是一個三叉樹，那麼一次剪枝它的葉結點數減少2個。變化量為 $2alpha$ ，有了這變化量，我們就可以用來求解最優決策子樹了。

因為 $alpha$ 參數給定，所以一次剪枝，損失函數的減少量也是固定的。所有子結點都是三叉樹時，我們可以簡單認為損失函數的減少量為2 $alpha$ 。假設只有一個子結點發生剪枝，那麼該子結點上的葉結點都將全部歸併到該結點，由此我們計算此結點的不確定次數。倘若不確定次數增大的量超過2 $alpha$ ，那麼剪枝失敗，演算法將嘗試其他子結點。因為新得的子樹損失函數反而增大。這從側面又反映了什麼樣的事實？該子結點的分類規則是大大降低不確定次數的，並不存在雜訊，所以沒必要進行剪枝。所以在剪枝過程中，找尋的就是那些雜訊點，卻被過度規則那些子結點，把這些合併了，萬事大吉，自然而然決策樹的準確率將上升。

在上述剪枝過程中，還需要注意一個有趣的問題。對應於每一個參數 $alpha$ ，剪枝後的子樹是唯一的嘛？個人覺得這是一個最基本的前提假設，在演算法中，它提到了一點，給定參數 $alpha$ ，找尋損失函數最小的子樹 $T_{alpha}$ ，也就是說 $<alpha,T_{alpha}>$ 是一一對應的！並不存在一個 $alpha$ 對應於多個子樹。CART剪枝演算法中將用到該基本假設。

那麼問題來了，參數 $alpha$ 給定的？誰來給？領域專家給？這是一種行之有效的辦法，但卻需要領域知識。理想化的模型都希望參數由data決定，也就是 $alpha$ 也由數據決定。那麼我們能想到的就是拿測試數據去測試在給定 $alpha$ 下生成的子樹。如果給定 $alpha$ 下，測試數據的準確率達到一定閾值我們就以這個 $alpha$ 為準。這就存在一個非常大的問題， $alpha$ 如何變化，才能讓測試數據準確率呈現極大值？這個問題在上述演算法中並不好解決！

CART剪枝核心思想

剛才的思路是什麼？從最宏觀的角度去考慮的話，就是利用 $alpha$ 生成 $T_{alpha}$ 。抽象一下，從【無限的實數】中找尋【有限個數的 $T_{alpha}$ 】，這問題當然不好解決了！思路其實已經出來了，CART剪枝演算法的核心思想就是說，一個複雜的決策樹，不管多複雜，都能生成有限個數的子樹，我們記作 ${T_0,T_1,...,T_n}$ ，那麼我們只要找尋到對應於每一個子樹的 $alpha$ 不就可以了嘛！沒錯，抽象一下，從【有限個數的 $T_alpha$ 】中找尋對應的【 $alpha$ 】，萬事解決。

咱們先來看看決策樹損失函數的定義：

$C_{alpha}(T) = sum_{t =1}^{vert Tvert}N_tH_t(T) + alphavert Tvert$

做一些數學變換得：

$C_{alpha}(T) = sum_{t =1}^{vert Tvert}N_tH_t(T) + alphavert Tvert = sum_{t=1}^{vert T vert}(N_tH_t(T)+alpha)$

所以說，衡量損失函數大小的真正貢獻在於每個葉結點，葉結點不確定次數的累加並加個常數 $alpha$ 就是我們決策樹整體的損失函數。

為了得到樹T的所有子序列 ${T_0,T_1,...,T_n}$ ，我們需要從底自上，每次只進行一次剪枝操作，那麼進行剪枝操作後，該子序列應該是當前參數的最優子樹。且應該是根據所剪的那個結點來計算參數 $alpha$ 。

為什麼要這麼做？接下來的思路是什麼？因為我們剛才說了，是通過最優子樹來求解參數 $alpha$ ，因此，我們先【假設】我們找到了當前的最優子樹，且必然發生剪枝。【注意加黑的這句話！】具體地，需要歸併的子結點為t，以t為單結點損失函數就可以表示為：（該子結點t已經成為我們的葉結點咯！在接下來給出的公式中，請思考哪些是已知參數，哪些是未知參數。）

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

這公式是最初的決策樹損失函數變化而來的！它是其中一個子結點【吞併】它的子樹，所得到【葉結點後】的損失函數。還需要強調下，因為在最初理解這個C(t)含義時，自己也被搞混了。該公式已經是剪枝完畢後的表達式了，也就是說原先的子結點已經變成了當前的葉結點。接下來會給剪枝前的表達式！ $C(t)$ 表示在該葉結點中的不確定次數。

那麼【剪枝前】是什麼情況呢？剪枝前是以t為根結點的子樹 $T_t$ 的損失函數是： $C_{alpha}(T_t) = C(T_t)+alphavert T_tvert$

也就是說，剪枝前該子結點的損失函數如上。具體的含義之前都有解釋過，就不再敘述了。接下來我們要明確哪些是已知參數，因為決策樹已經生成了，所以每個結點的不確定次數都是知道的，即 $C_(T)$ , $C_(T_t)$ 和 $vert T_t vert$ 是已知的。未知參數是 $alpha$ 如何求解？還記得加粗的假設嘛？

假設1：必然發生剪枝！

從中我們便能求得 $alpha$ ，為什麼？我們來觀察下，上述兩個式子。

當 $alpha =0$ 或者充分小，明顯地，不確定次數：

$C_{alpha}(T_t) < C_{alpha}(t)$

決策樹葉結點越多，不確定性越低，不解釋。

當增大 $alpha$ 時，總有那麼一個點，能夠使得：

$C_{alpha}(T_t) = C_{alpha}(t)$

當繼續增大 $alpha$ 時，

$C_{alpha}(T_t) > C_{alpha}(t)$

不等式反向，所以我們只要取 $alpha_1 = frac{C(t)-C(T_t)}{vert T_tvert-1}$ 時，當且僅當 $alpha ge alpha_1$ 時，剪枝必然發生。 $alpha$ 必須滿足上述條件，否則前提假設將失去意義。所以說，我們通過假設剪枝必然發生就能找到對應的 $alpha$ 。可對於任何一個子結點t都可以嘛？別忘了第二個假設。

假設2：剪枝發生後，當前決策樹是我們的最優子樹

最優子樹？現在t變成了一個變數，因為我們並不知道到底剪枝哪個子結點後決策樹是最優的。不急，再來看看，公式：

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

剪枝已經發生，此時，對應於每一個子結點t會生成不同的 $alpha$ 我們記作 $alpha(t)$ ，由此得：
$C_{alpha}(t) = C(t)+alpha(t)$

剪枝的決策樹什麼時候最優？對於當前參數 $alpha(t)$ 而言，能夠找到這樣的t，使得
$min_{t}{C(t)+alpha(t)}$

然而在這裡為了能夠求得 $alpha$ 的一個序列，貌似直接最小化了

$min_{t}(frac{C(t)-C(T_t)}{vert T_tvert-1})$

找的 $alpha$ 即找到了子結點t，即完成了剪枝，即找到了最優子樹 $T_1$ 。有了上述的步驟，為了得到決策樹 $T_0$ 的所有子序列，直接遞歸下去，直到根節點即可。在這一過程中，不斷地增加 $alpha$ 的值，產生新的區間。

後面的思路就很簡單了，根據生成的子樹序列，用測試集去測試這些子樹，誰的測試準確率最高，誰就獲勝。具體演算法可以參看《統計學習方法》，講的很詳細。

總的來說，CART剪枝演算法的核心在於用【有限個子樹 $T_{alpha}$ 】計算【無限個 $alpha$ 】，你會發現，計算過程中 $alpha$ 變成了一個個分段區間。在利用公式推導時，注意【必剪枝】和【當前最優子樹】的兩個假設，且時刻問自己【已知參數】和【未知參數】是哪些。

李航老師的《統計學習方法》第五章中有CART剪枝，主要思路是：

對於原始的CART樹A0，先剪去一棵子樹，生成子樹A1，然後再從A1剪去一棵子樹生成A2，直到最後剪到只剩一個根結點的子樹An。於是得到了A0-AN一共n+1棵子樹。然後再用n+1棵子樹預測獨立的驗證數據集，誰的誤差最小就選誰。

面臨一個問題：一棵樹，應該剪哪個結點？

這部分始終困擾我的是（5.31）式，即：

書里對g(t)的解釋是：

它表示剪枝後整體損失函數減少的程度。

這麼說應該剪掉以g(t)最大結點為根的子樹，因為g(t)最大，那麼剪枝後整體損失函數減少程度也最大。但書中的演算法卻說優先剪去g(t)最小的子樹，困惑了我好久。

實際上這個g(t)表示剪枝的閾值，即對於某一結點a，當總體損失函數中的參數alpha = g(t)時，剪和不剪總體損失函數是一樣的（這可以在書中（5.27）和（5.28）聯立得到）。這時如果alpha稍稍增大，那麼不剪的整體損失函數就大於剪去的。即alpha大於g(t)該剪，剪了會使整體損失函數減小；alpha小於g(t)不該剪，剪了會使整體損失函數增大。

（請注意上文中的總體損失函數，對象可以是以a為根的子樹，也可以是整個CART樹，對a剪枝前後二者的總體損失函數增減是相同的。）

對於同一棵樹的結點，alpha都是一樣的，當alpha從0開始緩慢增大，總會有某棵子樹該剪，其他子樹不該剪的情況，即alpha超過了某個結點的g(t)，但還沒有超過其他結點的g(t)。這樣隨著alpha不斷增大，不斷地剪枝，就得到了n+1棵子樹，接下來只要用獨立數據集測試這n+1棵子樹，試試哪棵子樹的誤差最小就知道那棵是最好的方案了。

如有錯誤請一定指正。

CART的剪枝和ID3/C4.5的剪枝對比進行理解：二者關鍵的區別就在於 $alpha$ 上面。

你可以仔細看李航的《統計學習方法》里兩種類型剪枝的步驟裡面，ID3/C4.5的剪枝 $alpha$ 是作為參數輸入的，也就是說這裡的 $alpha$ 是由人來確定的；CART則不是。

在ID3/C4.5中，是在人給定的 $alpha$ 作為前提條件下，從葉結點開始往根結點方向回溯，如果在回溯的過程中，下級的結點相比上級的結點損失函數反而增加了，說明下級沒有存在的必要，於是就被剪掉了。

而在CART中多了一個遍歷 $alpha$ 的步驟，按理說 $alpha$ 的取值是從0到正無窮的，是遍歷不完的。但是決策樹是有限的，因為數據中的特徵是有限的，就算再多也是有限個數的。而實際上，每一個子樹對應的不是一個 $alpha$ 值，而是一個 $alpha$ 的區間。其實現在回過頭來看，我們其實並不是想要遍歷某個參數 $alpha$ ，我們想要遍歷的從來都是決策樹個各個方案而已。

具體來講：

對於一個生長完全的決策樹 $T_0$ ,其中的每一個結點 $t$ ，結點 $t$ 的下面有若干子結點 $T_t$ ，現在做剪枝就是要考慮一下 $T_t$ 有沒有存在的必要。

剪枝後的損失函數為： $C_alpha(t)=C(t)+alpha$

剪枝前的損失函數為： $C_alpha(T_t)=C(T_t)+alpha|T|$

隨著 $alpha$ 逐漸增大，損失函數對模型複雜度（公式後邊的 $alpha|T|$ ）的懲罰就越來越大，總有一個 $alpha$ 會使剪枝前後的損失函數相等，即從這個時候開始，就有必要剪枝了。而這個臨界點的 $alpha=frac{C(t)-C(T_t)}{|T_t|-1}$ ，這一個東西叫做誤差增益。看看它的分子就會明白了：分子是由剪枝前後模型的擬合程度的差值構成的，也就是說， $alpha$ 的大小和剪枝前後模型的擬合能力的變化決定的，由於剪枝的關係，模型在樣本內的擬合能力通常是減弱的，所以才叫做"誤差"增益值。

所以，對於那個完全長成的樹 $T_0$ 中的每一個結點 $t$ ，我們都要算一算它的誤差增益是多少，當然擬合能力減少最小的那個剪枝方案 $T_1$ 就是我們最需要的。

然後我們繼續增加 $alpha$ ，繼續計算誤差增益，繼續找那個最優的子樹，最終會找出一個子樹序列來： ${T_0,T_1,T_2,...,T_n}$ ，最後交叉驗證一下就好啦。

?預剪枝（PrePrune）判斷停止樹生長的方法可以歸納為以下幾種：

①達到最大數深度(Maximum Tree Depth)；

②最優劃分(Split)標增益小於某一個閾值也可停止樹的生長；

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

④計算每次生長對系統性能的增益，如果這個增益值小於某個閾值則不進行生長。如果在最好情況下的生長增益都小於閾值，即使有些葉子結點的實例不屬於同一類，也停止樹的增長。

?後剪枝（PostPrune）主要有以下幾種方法：

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

拿T6葉節點來說：剪掉T6驗證集準確度91%

不剪去T6驗證集準確度90%

剪枝後準確率更高（錯誤率降低），所以剪枝！

②悲觀剪枝 Pessimistic Error Pruning(PEP）

悲觀剪枝是自上而下的對訓練集建立的樹。

$e^{$

成立時， $T_{t}$ 被剪枝。

上式中：

$e^{$

$S_{e}(e^{$

e(t)為結點t出的誤差；i為覆蓋 $T_{t}$ 的葉子結點； $N_{t}$ 為 $T_{t}$ 的葉子樹； $n_{t}$ 為 $T_{t}$ 的數據數據量；

樹中每個節點有兩個數字，左邊的代表正確，右邊代表錯誤

以T4節點為例，帶入公式：

$e^{$

$S_{e}(e^{$

最終： $7.5leq 8.5+2$ 成立，所以進行剪枝！

③代價複雜度剪枝Cost-Complexity Pruning(CCP)

設初始k=0， $T=T_{0} ,alpha$ 為正無窮

自上而下的計算

$g(t) =frac{R(t)-R(T_{t}) }{left| N_{T_{t} } ight| -1}$

$alpha =min(alpha ,g(t))$

$left| N_{T_{t} } ight|$ 表示子樹包含的葉子節點個數

$R(t)$ 訓練數據的預測誤差（如基尼指數）=節點t上的數據占所有數據的比例*節點t的誤差率

$R(T_{t})$ 是子樹 $T_{t}$ 的預測誤差=子樹 $T_{t}$ 上所有葉子節點的預測誤差之和；

若已知所有的數據總共有60條，則節點T4的節點誤差代價為：

$R(t)=frac{7}{16}*frac{16}{60}$

$R(T_{t})=Sigma R(i)=frac{2}{5}*frac{5}{60}+frac{0}{2}*frac{2}{60}+frac{3}{9}*frac{9}{60} =frac{5}{60}$

$g(t)=frac{1}{60}$

$alpha =min(+infty ,frac{1}{60} )$

T6的節點誤差代價為:

$R(t)=frac{3}{7}*frac{7}{60}$

$R(T_{t})=Sigma R(i)=frac{2}{5}*frac{5}{60}+frac{0}{2}*frac{2}{60} =frac{5}{60}$

$g(t)=(frac{3}{60}-frac{2}{60})/(2-1) =frac{1}{60}$

$g(t)=alpha$

對T6剪枝！得到新的樹T。具體演算法過程參考統計學習方法P73

如有錯誤還請指正~

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

參考資料：

《統計學習方法》李航

《機器學習》周志華

數據挖掘十大經典演算法--CART: 分類與回歸樹

最近學習《統計學習方法》，正好看到了這個話題，簡單說下個人的看法，非專業或理論角度，僅描述通俗的見解，幫助大家理解CART剪枝的思想，同時歡迎大牛拍磚！

書中前半段內容不難，但如何通過每次給定的alpha值，剪掉最小的g(t)，即可獲得該alpha值下的最優子樹？看起來比較費勁。為什麼要選取最小的，而不是最大的g(t)或者別的值。

為了說明這個問題，手繪了一個簡單的示意圖如下：

對於每個給定的alpha值，樹中的每個結點作為子結點和葉結點時，樹的預測誤差（分類的不確定性）是不同的，簡單的，也就是說該結點修剪之前和剪掉之後，對應的樹和子樹對訓練數據的預測誤差不同，代價函數的損失大小不同。如上圖所示：假設alpha變化時，樹中的兩個結點對應的預測誤差的變化(修剪前後）分別如黑色和紅色線所示，顯然，當alpha較小時，結點不修剪的誤差要小於修剪之後的誤差，此時不剪為好，但當alpha增大時，修剪前後的誤差先減小後增大，對應每個結點都有一個臨界值g(t)。

為什麼要選擇最小的g(t)呢？以圖中兩個點為例，結點1和結點2，g(t)2大於g(t)1, 假設在所有結點中g(t)1最小，g(t)2最大，兩種選擇方法：當選擇最大值g(t)2，即結點2進行剪枝，但此時結點1的不修剪的誤差大於修剪之後的誤差，即如果不修剪的話，誤差變大，依次類推，對其它所有的結點的g(t)都是如此，從而造成整體的累計誤差更大。反之，如果選擇最小值g(t)1，即結點1進行剪枝，則其餘結點不剪的誤差要小於剪後的誤差，不修剪為好，且整體的誤差最小。從而以最小g(t)剪枝獲得的子樹是該alpha值下的最優子樹！

疑問：，CART剪枝演算法是遞歸演算法，即從下往上開始剪枝，直到根結點，從而每次剪枝時由alpha產生的g(t)，下層要小於上層，上層不存在更小的g(t)，這點在理論上應該成立，不然剪枝會發生混亂，判斷下層結點時，結果上層結點g(t)更小。希望大牛們能夠解答下。

記得李航的書里CART剪枝講的很詳細