對CART決策樹剪枝程序的理解

前言：CART決策樹生成的程序比較好理解，但是剪枝的程序看了好幾遍才看明白，故寫出下文，供同樣困惑的朋友參考，下文不涉及復雜嚴密的數學推導，以輔助理解為主，

一. 損失函式的定義方法

CART的損失函式用的是下式：

\[C_\alpha(T)=C(T)+\alpha |T| \tag{1} \]

損失函式表征的是模型預測錯誤的程度，所以它越小越好，

上式中$C_\alpha (T)$ 是關于 $T$ 和 $\alpha$ 的函式，$T$ 表示一個決策樹，$C(T)$ 是對訓練資料的預測誤差（分類用基尼指數表示，回歸用均方誤差表示），$|T|$ 表示樹 $T$ 的葉節點個數，$\alpha $ 是一個常數，用來平衡模型對資料的擬合程度（由$C(T)$項決定）和模型的復雜度（$\alpha|T|$項決定，復雜度也就是樹的分支多不多），

如果 $\alpha$ 非常小，那么損失函式 $C_\alpha(T)$ 的值大小由 $C(T)$ 決定，為了使損失函式的值小，$C(T)$ 也就會趨于小，也就是多分枝，充分延展樹（因為我們生成樹時，選擇屬性的標準就是使基尼指數或者均方誤差減小的最多，所以充分分枝意味著更小的 $C(T)$）；

反之，如果 $\alpha$ 充分大，那么損失函式 $C_\alpha(T)$ 的值大小由 $\alpha |T|$ 決定，為了使損失函式的值小， $|T|$ 也就會趨于小，而最小的樹就是只有一個節點，所以此時剪枝成一個單節點樹，$|T|=1$ ，

總而言之，$\alpha$ 越大，在損失函式的影響下，模型趨向于少分枝，$\alpha$越小，模型越趨向于多分枝，

二. 剪枝的程序

假設通過CART生成一個完整的樹$T_0$，如下：

剪枝的整體思路是：

每次樹所有的內結點（不是葉結點的結點，如上示樹的N4,N2,N3,N7,N1），得出最適合剪枝的結點并對其剪枝，得到一個子樹 $T_i$ ，然后再分析 $T_i$ 的所有內結點，找出 $T_i$ 最適合剪枝的結點并對其剪枝，得到子樹 $T_{i+1}$；

$\cdots$
重復至最終得到的子樹只剩下三個結點（一個根結點連著兩個葉結點），如果這個程序中，我們得到了 k+1 個子樹（注意，每次剪完枝得到的子樹都要存盤起來），不妨記作 {$T_0,T_1,\cdots,T_k$}；
最后使用交叉驗證，看看哪個樹的性能最好，我們就選擇哪個樹，

核心步驟是第一步，以下給出具體解釋和方法：

第一部分我們分析過：$\alpha$ 越大，越趨向于多分枝；$\alpha$ 越小，越趨向于少分枝，所以，必定存在一個$\alpha$，使得分不分枝都可以（分枝與不分枝的損失函式值相同），我們記這個$\alpha$ 為 $\alpha_0$，所以，我們只需要依次將樹的內結點和它的子節點組成的子樹拿出來（比如上示樹中標示出來的以 $N3$ 為根節點和以 $N4$ 為根節點的子樹），計算它的 $\alpha_0$ ，對于全部的內結點，我們得到一組 $\alpha_0$ 值，然后選擇其中最小的 $\alpha_0$ 對應內結點，并對其剪枝，

這句話需要稍微轉個彎才能理解，為什么要選擇 $\alpha_0$ 最小的結點剪枝呢？假設我們選擇了一個大于 $min(\alpha_0)$ 的值 $\alpha'$ 作為閾值，那么對于剪枝閾值α0 小于 α′ 的結點，他們都處于 “趨向于不分枝“ 的狀態，也就是需要剪枝，這樣就會有多個結點需要剪枝，但是我們不能確保這些需要被剪枝的結點都是不相關的（剪掉一個后對另一個結點沒有影響），所以我們需要控制每次只剪一個結點的枝，選擇最小的$\alpha_0$對應的結點剪枝，就是為了控制每次只剪掉一個結點的枝，因為在損失函式是$C_\alpha(T)=C(T)+\alpha_0 |T|$的情況下，其他結點都處于 ”趨向于多分枝的狀態“ ，

Breiman對此有嚴密的數學證明，感興趣可以看看，

接下來就是確認每個內結點的$\alpha_0$，注意，確認每個內結點的$\alpha_0$需要將該結點作為根節點的子樹單獨拿出來研究，以 $N4$ 結點為例，首先我們把它作為根節點的子樹拿出來：

不剪枝，它的損失函式是：

\[C_\alpha(T_{N4})=C(T_{N4})+\alpha |T_{N4}|\\ T_{N4}表示以N4為根節點的子樹，|T_{N4}|表示T_{N4}的葉結點數，這里等于2，但是為了得到通式，這里寫為|T_{N4}| \tag{2} \]

剪枝后，它只剩下 N4 一個結點，光桿司令，這時候損失函式是：

\[C_\alpha(N4)=C(N4)+\alpha ,N4表示只有N4這個節點的樹 \tag{3} \]

找“剪不剪枝都可以的$\alpha$” ，也就是找 $C_\alpha(T_{N4})=C_\alpha(N4)$ 的 $\alpha$ ，故有

\[C(T_{N4})+\alpha |T_{N4}|=C(N4)+\alpha \\ 得到：\alpha=\frac{C(N4)-C(T_{N4})}{|T_{N4}|-1} \tag{4} \]

可得，對于任意結點$t$，記以 $t$ 為根節點的子樹為$T_t$ ,只有 $t$ 一個結點的樹直接記為 $t$ ，則得到計算結點 $t$ “剪不剪枝都可以的$\alpha$” 的公式：

\[\alpha=\frac{C(t)-C(T_t)}{|T_t|-1} \tag{5} \]

問題得解：我們對每個內結點都用式 (5) 找出它”剪不剪枝都可以“ 的臨界$\alpha_0$，然后篩選出最小的 $\alpha_0$ 對應的內結點剪枝，

三. CART 剪枝演算法

輸入：CART演算法生成的決策樹$T^0$

輸出：最優決策樹 $T_\alpha$

設 $k=0$
設$\alpha_t = +\infin$
對樹,$T^k$各個內部節點 $t$ 計算$C(T_t)$ ，$T_t$ 以及

\[\alpha(t) = \frac{C(t)-C(T_t)}{|T_t|-1}\\ \alpha_t = min(\alpha,\alpha(t)) \]
$T_t$ 是以t結點為根節點的子樹，$t$代表結點t，也表示只有 $t$ 一個結點的樹，$C(T_t)$ 是訓練資料的預測誤差（可以用基尼指數或者均方誤差表征），$|T_t|$ 是$t$為根節點的子樹的葉結點數，
對$\alpha(t)=\alpha$的內部結點$t$ 進行剪枝，對于剪枝后的結點$t$ 采用多數表決法確認其類別，得到樹 $T^{k+1}$
$k=k+1$
重復 3-5 ，直到$T^k$是一個三結點樹（一個根節點兩個葉結點）
對于得到的子樹序列${T_0,T_1,\cdots,T_n}$，采用交叉驗證法選出最優子樹$T_\alpha$

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/517772.html

標籤：其他

上一篇：資料結構基礎—串

下一篇：一鍵上手時下最火AI作畫工具