決策樹是一種基本的分類與回歸方法。ID3和C4.5決策樹可以用于分類记某，CART（分類與回歸樹）既可以用于分類偎痛，也可以用于回歸旱捧。決策樹的學習通常包括3個步驟：特征選擇、決策樹的生成和決策樹的修剪踩麦。這里主要介紹分類決策樹枚赡。附上機器學習實戰(zhàn)的書中決策樹代碼。

定義

分類決策樹模型是一種描述對實例進行分類的樹形結構谓谦，決策樹由結點和有向邊組成贫橙。結點由兩種類型：內部結點和葉結點。內部結點表示一個特征或屬性反粥，葉結點表示一個類卢肃。

由決策樹的根結點到葉結點的每一條路徑構建一條規(guī)則：路徑上內部結點的特征對應著規(guī)則的條件，而葉結點的類對應著規(guī)則的結論星压。決策樹的路徑對應的規(guī)則互斥且完備践剂，每一個實例都只被一條路徑所覆蓋鬼譬。

決策樹還能表示給定特征條件 $X$ 下類 $Y$ 的條件概率分布 $P(Y|X)$ 娜膘。

決策樹的學習

決策樹學習，假設給定訓練數據集
$D= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$
其中优质， $x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T$ 為輸入實例（特征向量）竣贪， $n$ 為特征個數， $y_i\in \{1,2,\cdots,K\}$ 為類標記巩螃， $i=1,2,\cdots,N$ 演怎， $N$ 為樣本容量，學習的目的是根據給定的訓練數據集構建一個決策樹模型避乏，使它能夠對實例進行正確的分類爷耀。

決策樹學習的算法通常是一個遞歸的選擇最優(yōu)特征，并根據該特征對訓練數據進行分割拍皮，使得對各個子數據集有一個最好的分類的過程歹叮，這一過程對應著對特征空間的劃分，也對應著決策樹的構建铆帽。在構建完成后咆耿，決策樹對訓練數據有了很好的劃分，但是一般不具備很好的泛化能力爹橱，容易出現過擬合萨螺，于是可以通過剪枝算法剪去一些子樹來提高泛化能力。剪枝的結果不是唯一的，需要選擇一個最優(yōu)的決策樹最為最終的模型慰技。這一最優(yōu)化問題是NP完全問題椭盏，通常采用啟發(fā)式算法求解，得到的決策樹是次最優(yōu)的惹盼。

NP完全問題=NPC問題庸汗，這種問題存在的現象就是生成問題的一個解比驗證一個給定解花費的時間多得多。

特征選擇

特征選擇在于選取對訓練數據具有分類能力的特征手报。這樣可以提高決策樹學習的效率蚯舱。通常特征選擇的準則是信息增益或信息增益比。

信息增益

首先定義熵和條件熵

熵

熵是表示隨機變量不確定性的度量掩蛤，設 $X$ 是一個取有限個值的離散隨機變量枉昏，其概率分布為
$P(X=x_i)=p_i,\ \ i=1,2,\cdots,n$
則隨機變量的熵定義為
$H(X)=-\sum_{i=1}^np_ilogp_i\tag1$
當隨機變量越確定時，熵越小揍鸟。例如0,1分布兄裂， $P(X=1)=p$ 的熵隨概率 $p$ 的曲線：

當 $p=0.5$ 時，最不確定0還是1阳藻，此時熵最大晰奖。

條件熵

設隨機變量 $(X,Y)$ ，其聯合概率分布為
$P(X=x_i,Y=y_j)=p_{ij},\ \ i=1,2,\cdots,n;\ \ j=1,2,\cdots,m$
條件熵 $H(Y|X)$ 表示在一直隨機變量 $X$ 的條件下隨機變量 $Y$ 的不確定性腥泥。隨機變量 $X$ 給定的條件下隨機變量 $Y$ 的條件熵 $H(Y|X)$ 匾南，定義為 $X$ 給定條件下 $Y$ 的條件概率分布的熵對 $X$ 的期望
$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)$
當熵和條件熵中的概率有數據估計（特別是極大似然估計）得到時，所對應的熵與條件熵分別稱為經驗熵和經驗條件熵蛔外，此時蛆楞，如果有0概率，令 $0\log0=0$ 夹厌。

信息增益定義

特征 $A$ 對訓練數據集 $D$ 的信息增益 $g(D,A)$ 豹爹，定義為集合 $D$ 的經驗熵 $H(D)$ 與特征 $A$ 給定條件下 $D$ 的經驗條件熵 $H(D|A)$ 之差，即
$g(D,A)=H(D)-H(D|A)\tag2$
表示通過特征 $A$ 劃分矛纹，數據集 $D$ 分類不確定性減少的程度臂聋。

信息增益的算法

輸入：訓練數據集 $D$ 和特征 $A$ ；

輸出：特征 $A$ 對訓練數據集 $D$ 的信息增益 $g(D,A)$ 或南。

（1）計算數據集 $D$ 的經驗熵
$H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}$
其中 $|C_k|$ 是訓練集中屬于 $C_k$ 類的樣本個數孩等， $|D|$ 是訓練集樣本總數

（2）計算特征 $A$ 對數據集 $D$ 的經驗條件熵 $H(D|A)$
$H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|}$
其中 $D_i$ 是訓練集 $D$ 根據特征 $A$ 的第 $i$ 個取值劃分得到的子集， $\sum D_i=D$ 迎献， $D_{ik}$ 是子集 $D_i$ 中屬于 $C_k$ 類的樣本的集合

（3）計算信息增益
$g(D,A)=H(D)-H(D|A)$

信息增益比

以信息增益作為劃分訓練數據集的特征瞎访，存在偏向于選擇取值較多的特征的問題，使用信息增益比可以對這一問題進行校正吁恍。

信息增益比定義

特征 $A$ 對訓練數據集 $D$ 的信息增益比 $g_R(D,A)$ 定義為其信息增益 $g(D,A)$ 與訓練數據集 $D$ 關于特征 $A$ 的值的熵 $H_A(D)$ 之比扒秸，即
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$
其中播演， $H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}$ ， $n$ 是特征 $A$ 取值的個數伴奥。熵 $H(D)$ 是針對數據集 $D$ 的分類 $Y$ 的写烤，這里 $H_A(D)$ 是針對數據集 $D$ 的特征 $A$ 的。

決策樹的生成

ID3的生成算法

輸入：訓練數據集 $D$ 拾徙，特征集 $A$ 洲炊，閾值 $\varepsilon$ ；

輸出：決策樹 $T$ 尼啡。

（1）若 $D$ 中所有實例屬于同一類 $C_k$ 暂衡，則 $T$ 為單結點樹，并將類 $C_k$ 作為該結點的類標記崖瞭，返回 $T$ 狂巢；

（2）若 $A=\varnothing$ ，則 $T$ 為單結點樹书聚，并將 $D$ 中實例數最大的類 $C_k$ 作為該結點的類標記唧领，返回 $T$ ；

（3）否則雌续，按信息增益算法計算 $A$ 中各特征對 $D$ 的信息增益斩个，選擇信息增益最大的特征 $A_g$ ；

（4）如果 $A_g$ 的信息增益小于閾值 $\varepsilon$ 驯杜，則置 $T$ 為單結點樹受啥，并將 $D$ 中實例數最大的類 $C_k$ 作為該結點的類標記，返回 $T$ 艇肴；

（5）否則腔呜，對 $A_g$ 的每一個可能值 $a_i$ 叁温，依 $A_g=a_i$ 將 $D$ 分割為若干非空子集 $D_i$ 再悼，將 $D_i$ 中實例數最大的類作為標記，構建子結點膝但，由結點及其子結點夠成樹 $T$ 冲九，返回 $T$ ；

（6）對第 $i$ 個子結點跟束，以 $D_i$ 為訓練集莺奸，以 $A- \{A_g\}$ 為特征集忍啤，遞歸的調用步(1)-(5)跺撼，得到子樹 $T_i$ ，返回 $T_i$ 聪建。

C4.5的生成算法

輸入：訓練數據集 $D$ 略贮，特征集 $A$ 甚疟，閾值 $\varepsilon$ 仗岖；

輸出：決策樹 $T$ 。

（1）若 $D$ 中所有實例屬于同一類 $C_k$ 览妖，則 $T$ 為單結點樹轧拄，并將類 $C_k$ 作為該結點的類標記，返回 $T$ 讽膏；

（2）若 $A=\varnothing$ 檩电，則 $T$ 為單結點樹，并將 $D$ 中實例數最大的類 $C_k$ 作為該結點的類標記府树，返回 $T$ 俐末；

（3）否則，按公式(2)計算 $A$ 中各特征對 $D$ 的信息增益比奄侠，選擇信息增益比最大的特征 $A_g$ 鹅搪；

（4）如果 $A_g$ 的信息增益小于閾值 $\varepsilon$ ，則置 $T$ 為單結點樹遭铺，并將 $D$ 中實例數最大的類 $C_k$ 作為該結點的類標記丽柿，返回 $T$ ；

（5）否則魂挂，對 $A_g$ 的每一個可能值 $a_i$ 甫题，依 $A_g=a_i$ 將 $D$ 分割為若干非空子集 $D_i$ ，將 $D_i$ 中實例數最大的類作為標記涂召，構建子結點坠非，由結點及其子結點夠成樹 $T$ ，返回 $T$ 果正；

（6）對第 $i$ 個子結點炎码，以 $D_i$ 為訓練集，以 $A- \{A_g\}$ 為特征集秋泳，遞歸的調用步(1)-(5)潦闲，得到子樹 $T_i$ ，返回 $T_i$ 迫皱。

兩個算法的區(qū)別僅在于ID3使用信息增益最大為標準選擇劃分特征歉闰，而C4.5使用信息增益比最大為標準選擇劃分特征。

決策樹的剪枝

生成算法產生的決策樹對訓練數據有很好的劃分卓起，但是容易出現過擬合和敬，這時候就需要對生成的決策樹進行剪枝，提高模型的泛化能力戏阅。

剪枝通過極小化決策樹整體的損失函數或代價函數來實現昼弟。設樹 $T$ 的葉結點個數為 $|T|$ ， $t$ 是樹 $T$ 的葉結點奕筐，該葉結點有 $N_t$ 個樣本點舱痘，其中 $k$ 類的樣本點有 $N_{tk}$ 個蚕键， $k=1,2,\cdots,K$ ， $H_t(T)$ 為葉結點 $t$ 上的經驗熵衰粹， $\alpha\geq0$ 為參數锣光，則決策樹學習的損失函數可以定義為
$C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|\tag3$
其中經驗熵為
$H_t(T)=-\sum_k\frac{N_{tk}}{N_t}\log\frac{N_{tk}}{N_t}\tag4$
在損失函數，將公式(3)中右端第一項記做
$C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}\log\frac{N_{tk}}{N_t}\tag5$
這時有
$C_\alpha(T)=C(T)+\alpha|T|\tag6$
上式中 $C(T)$ 表示模型對訓練數據的預測誤差铝耻， $|T|$ 表示模型復雜度誊爹。參數 $\alpha$ 控制兩者之間的影響，較大的 $\alpha$ 促使選擇簡單的模型瓢捉，較小的 $\alpha$ 促使選擇復雜的模型频丘， $\alpha=0$ 表示不考慮模型復雜度。該損失函數的極小化等價于正則化的極大似然估計泡态。

樹的剪枝算法

輸入：生成算法產生的整個樹 $T$ 搂漠，參數 $\alpha$ ；

輸出：修剪后的子樹 $T_\alpha$ 某弦。

（1）計算每個結點的經驗熵

（2）遞歸的從樹的葉結點向上回縮桐汤。設一組葉結點回縮到父結點之前與之后的整體樹分別為 $T_B$ 與 $T_A$ ，其對應的損失函數值分別是 $C_\alpha(T_B)$ 與 $C_\alpha(T_A)$ 靶壮，如果
$C_\alpha(T_A)\leq C_\alpha(T_B)$
則進行剪枝怔毛，即將父結點變?yōu)樾碌娜~結點。

（3）返回(2)腾降，直至不能繼續(xù)位置拣度，得到損失函數最小的子樹 $T_\alpha$ 。

剪枝算法可以通過動態(tài)規(guī)劃的算法實現螃壤。

CART算法

CART是分類與回歸樹的簡寫抗果，即既可以實現分類，也可以實現回歸的樹奸晴。CART是二叉樹冤馏，內部結點有兩個分支，左邊是“是”蚁滋，右邊是“否”宿接，對特征進行遞歸的二分赘淮。

CART算法由以下兩步組成：

（1）決策樹生成：基于訓練數據集生成決策樹辕录，生成的決策樹要盡量大；

（2）決策樹剪枝：用驗證數據集對已生成的樹進行剪枝并選擇最優(yōu)子樹梢卸，這時用損失函數最小作為剪枝的標準走诞。

CART生成

回歸樹生成

假設 $X$ 和 $Y$ 分別為輸入和輸出變量，并且 $Y$ 是連續(xù)變量蛤高，給定訓練數據集
$D= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$
考慮如何生成回歸樹蚣旱。

一個回歸樹對應著輸入空間（即特征空間）的一個劃分以及在劃分的單元的輸出值碑幅。假設已將輸入空間劃分為 $M$ 個單元 $R_1,R_2,\cdots,R_M$ ，并且在每個單元 $R_m$ 有一個固定的輸出值 $c_m$ 塞绿，于是回歸樹模型可表示為
$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$
當輸入空間的劃分確定時沟涨，可以用平方誤差 $\sum_{x_i\in R_m}(y_i-f(x_i))$ 來表示回歸樹對訓練數據的預測誤差，用平方誤差最小的準則求解每個單元上的最優(yōu)輸出值异吻。易知裹赴，單元 $R_m$ 上的 $c_m$ 的最優(yōu)值 $\hat c_m$ 是 $R_m$ 上的所有輸入實例 $x_i$ 對應的輸出 $y_i$ 的均值，即
$\hat c_m=\mathrm{ave}(y_i|x_i\in R_m)$
問題是怎樣對輸入空間進行劃分诀浪。這里采用啟發(fā)式的方法棋返，選擇第 $j$ 個變量 $x^{(j)}$ 和它的取值 $s$ ，作為切分變量和切分點并定義兩個區(qū)域：
$R_1(j,s)= \{x|x^{(j)}\leq s\}\ \ 和\ \ R_1(j,s)= \{x|x^{(j)}\gt s\}$
然后尋找最優(yōu)切分變量 $j$ 和最優(yōu)切分點 $s$ 雷猪。具體的睛竣，求解
$\min_{j,s}\bigg[\min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2\bigg]$
對固定輸入變量 $j$ 可以找到最優(yōu)切分點 $s$ 。
$\hat c_1=\mathrm{ave}(y_i|x_i\in R_1(j,s))\ \ 和\ \ \hat c_2=\mathrm{ave}(y_i|x_i\in R_2(j,s))$
遍歷所有輸入變量求摇，找到最優(yōu)的切分變量 $j$ 射沟，構成一個對 $(j,s)$ ，以此將輸入空間劃分為兩個區(qū)域与境。接著躏惋，對每個區(qū)域重復上述劃分過程，直到滿足停止條件（例如結點中的樣本個數小于預定閾值）為止嚷辅。這樣就生成一顆回歸樹簿姨，這樣的回歸樹通常稱為最小二乘回歸樹。

最小二乘回歸樹生成算法

輸入：訓練數據集 $D$ 簸搞；

輸出：回歸樹 $f(x)$ 扁位。

在訓練數據集所在的輸入空間中，遞歸的將每個區(qū)域劃分為兩個子區(qū)域并決定每個子區(qū)域上的輸出值趁俊，構建二叉決策樹：

（1）選擇最優(yōu)切分變量 $j$ 與切分點 $s$ 域仇，求解
$\min_{j,s}\bigg[\min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2\bigg]\tag7$
遍歷變量 $j$ ，對固定的切分變量 $j$ 掃描切分點 $s$ 寺擂，選擇使公式(7)達到最小的值的對 $(j,s)$

（2）用選定的對 $(j,s)$ 劃分區(qū)域并決定相應的輸出值：
$R_1(j,s)= \{x|x^{(j)}\leq s\},\ \ R_2(j,s)= \{x|x^{(j)}\gt s\}$

$\hat c_m=\frac1{N_m}\sum_{x_i\in R_m(j,s)}y_i,\ \ x\in R_m,\ \ m=1,2$

（3）繼續(xù)對兩個子區(qū)域調用步驟(1)暇务，(2)，直至滿足停止條件怔软。

（4）將輸入空間劃分為 $M$ 個區(qū)域 $R_1,R_2,\cdots,R_M$ 垦细，生成決策樹：
$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$

分類樹的生成

分類樹用基尼指數選擇最優(yōu)特征，同時決定該特征的最優(yōu)二值切分點挡逼。

基尼指數的定義

分類問題中括改，假設有 $K$ 個類，樣本點屬于第 $k$ 類的概率為 $p_k$ 家坎，則概率分布的基尼指數定義為
$\mathrm{Gini}(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2\tag8$
對于給定樣本集 $D$ 嘱能，其基尼指數為
$\mathrm{Gini}(D)=1-\sum_{k=1}^K\bigg(\frac{|C_k|}{|D|}\bigg)\tag9$
這里吝梅， $C_k$ 是 $D$ 中屬于第 $k$ 類的樣本子集。

如果樣本集合 $D$ 根據特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 兩部分惹骂，則在特征 $A$ 的條件下苏携，集合 $D$ 的基尼指數定義為
$\mathrm{Gini}(D,A)=\frac{|D_1|}{|D|}\mathrm{Gini}(D_1)+\frac{|D_2|}{|D|}\mathrm{Gini}(D_2)$
基尼指數 $\mathrm{Gini}(D)$ 表示集合 $D$ 的不確定性，基尼指數越大对粪，不確定性越高兜叨，和熵有相似的性質●媒模基尼指數 $\mathrm{Gini}(D,A)$ 表示按特征 $A=a$ 劃分后的不確定性国旷。

CART生成算法

輸入：訓練數據集 $D$ ，停止計算的條件茫死；

輸出：CART決策樹跪但。

根據訓練數據集，從根結點開始峦萎，遞歸的對每個結點進行以下操作屡久，構建二叉決策樹：

（1）設結點的訓練數據集為 $D$ ，計算現有特征對該數據集的基尼指數爱榔。此時對每一個特征 $A$ 被环，對其可能取的每個值 $a$ ，根據樣本點對 $A=a$ 的測試為“是”或“否”將 $D$ 分割成 $D_1$ 和 $D_2$ 兩部分详幽，利用
$\mathrm{Gini}(D,A)=\frac{|D_1|}{|D|}\mathrm{Gini}(D_1)+\frac{|D_2|}{|D|}\mathrm{Gini}(D_2)$
計算 $A=a$ 時的基尼指數筛欢。

（2）在所有可能的特征 $A$ 以及它們所有可能的切分點 $a$ 中，選擇基尼指數最小的特征及其對應的切分作為最優(yōu)特征與最優(yōu)切分點唇聘。依最優(yōu)特征與最優(yōu)切分點版姑，從現結點生成兩個子結點，將訓練數據依特征分配到兩個子結點中去迟郎。

（3）對兩個子結點遞歸的調用(1)剥险，(2)，直至滿足停止條件宪肖。

（4）生成CART決策樹表制。

算法停止計算的條件是結點中的樣本個數小于預定閾值，或樣本集的基尼指數小于預定閾值（樣本基本屬于同一類）控乾，或者沒有更多特征么介。

CART 剪枝

在剪枝過程中，計算子樹的損失函數：
$C_\alpha(T)=C(T)+\alpha|T|$
其中阱持， $T$ 為任意子樹夭拌， $C(T)$ 為對訓練數據的預測誤差（分類樹中 $C(T)=\sum_{t=1}^{|T|}N_t\mathrm{Gini}_t(T)$ ）， $|T|$ 為子樹的葉結點個數衷咽， $\alpha\geq0$ 為參數鸽扁，較大的 $\alpha$ 促使選擇簡單的模型，較小的 $\alpha$ 促使選擇復雜的模型镶骗。

對固定的 $\alpha$ 桶现，一定存在使損失函數 $C_\alpha(T)$ 最小的子樹，于是我們把 $\alpha$ 從小增大鼎姊， $0=\alpha_0\lt\alpha_1\lt\cdots\lt\alpha_n\lt+\infty$ 使其從復雜到簡單逐步進行剪枝骡和，剪枝得到的子樹序列對應著區(qū)間 $\alpha\in[\alpha_i,\alpha_{i+1}]$ ， $i=0,1,\cdots,n$ 的最優(yōu)子樹序列 $\{T_0,T_1,\cdots,T_n\}$ 相寇，序列中的子樹是嵌套的慰于。

具體的，從整體樹 $T_0$ 開始剪枝唤衫。對 $T_0$ 的任意內部結點 $t$ 婆赠，以 $t$ 為單結點樹的損失函數是
$C_\alpha(t)=C(t)+\alpha$
以 $t$ 為根結點的子樹 $T_t$ 的損失函數是
$C_\alpha(T_t)=C(T_t)+\alpha|T_t|$
當 $\alpha=0$ 及 $\alpha$ 充分小時，有不等式
$C_\alpha(T_t)\lt C_\alpha(t)$
單結點樹損失更大一點佳励，因為 $\alpha$ 充分小時休里，復雜的樹損失更小。當 $\alpha$ 增大時赃承，在某一 $\alpha$ 有
$C_\alpha(T_t)=C_\alpha(t)$
單結點樹和子樹損失相同妙黍。當 $\alpha$ 再增大時，不等式反向瞧剖，單結點樹損失更小拭嫁。

所以只要 $\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$ ， $T_t$ 與 $t$ 有相同的損失函數值抓于，而 $t$ 的結點少噩凹，因此 $t$ 比 $T_t$ 更可取，對 $T_t$ 進行剪枝毡咏。

為此驮宴，對 $T_0$ 中每一內部結點 $t$ ，計算
$\alpha=g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$
減去 $g(t)$ 最小的 $T_t$ 呕缭，得到的子樹作為 $T_1$ 堵泽，所處的區(qū)間為 $[\alpha_1,\alpha_2]$ （整體樹的區(qū)間是 $[\alpha_0=0,\alpha_1)$ ）。

如此剪枝下去恢总，直至得到根結點迎罗。在這一過程中，不斷的增加 $\alpha$ 的值片仿，產生新的區(qū)間纹安。并且每個區(qū)間的子樹是在上個區(qū)間的子樹上剪枝得到的，因為當 $\alpha$ 更大時，對于之前 $g(t)$ 值更小的結點厢岂， $C_\alpha(T_t)\gt C_\alpha(t)$ 光督，即之前剪去的結點其子樹 $T_t$ 的損失要比單結點 $t$ 更大，所以嵌套的剪枝是合理的塔粒。

剪枝完成后结借，子樹序列 $T_0,T_1,\cdots,T_n$ 對應的 $\alpha$ 序列 $\alpha_1,\alpha_2,\cdots,\alpha_n$ 也就確定了，利用驗證數據集在子樹序列 $T_0,T_1,\cdots,T_n$ 中計算損失 $C_{\alpha_n}(T)$ 卒茬，選擇損失最小的決策樹 $T_\alpha$ 船老。