文章目錄

• CART算法
• CART回歸樹生成
• CART分類樹的生成
• • 連續(xù)值處理：
  • 離散值處理：
• CART 剪枝

CART算法

分類與回歸樹(CART)是應用廣泛的算法，同樣由特征選擇、樹的生成及剪枝組成，可以用于解決分類和回歸問題。

ID3算法、C4.5算法分別使用了信息增益、信息增益比來選擇特征，他們都使用了包含大量的對數(shù)運算的熵模型來計算樣本純度。而CART算法使用基尼系數(shù)來代替信息增益(比)，基尼系數(shù)代表了模型的不純度，基尼系數(shù)越小，則不純度越低，特征越好。這和信息增益(比)是相反的。

CART決策樹的生成過程是遞歸構建二叉樹的過程。對于分類樹，使用基尼指數(shù)最小化準則；對回歸樹，使用平方誤差最小化準則。

CART回歸樹生成

構建回歸樹有兩個問題：

(1) 如何得到預測結果？

(2) 如何對輸入空間進行劃分？

一顆回歸樹是輸入空間的一個劃分，以及在劃分單元的輸出值。假設輸入空間已經劃分為M個：$R_1,R_2,...,R_M$，并且在每個單元$R_m$有一個固定的輸出值$c_m$，于是回歸樹模型可表示為：
$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$
可以用平方誤差${\sum }_{x_i\in R_m}(y_i?f(x_i){)}^2$來表示回歸樹的預測誤差，用平方誤差最小的準則求解每個單元的最優(yōu)輸出值。

對于第一個問題，單元$R_m$上的$c_m$的最優(yōu)值${\hat{c}}_m$是$R_m$上所有輸入實例$x_i$對應的輸出$y_i$的均值，即：
$${\hat{c}}_m=ave(y_i|x_i\in R_m)$$
那么如何對輸入空間進行劃分？可以采用啟發(fā)式的方法，選擇樣本x的第j個特征$x^{(j)}$和它的均值s作為切分變量和切分點。定義兩個區(qū)域：
$$\begin{gathered} R_1(j,s)=\{x|x^{(j)}?s\} \\ {R}_2(j,s)=\{x|x^{(j)}>s\} \end{gathered}$$
然后尋找最優(yōu)切分變量 j 和最優(yōu)切分點 s，具體地就是遍歷所有特征的所有切分點，求解：
$$\underset{j,s}{\min }[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i?c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i?c_2{)}^2]$$
其中，$c_1$為R1數(shù)據(jù)集的樣本輸出均值，$c_2$為R2數(shù)據(jù)集的樣本輸出均值：
$${\hat{c}}_1=ave(y_i|x_i\in R_1(j,s)),{\hat{c}}_2=ave(y_i|x_i\in R_2(j,s))$$
遍歷所有輸入變量，找到最優(yōu)的切分變量 j，構成一個對(j,s)。依次將輸入空間劃分為兩個區(qū)域。對每個區(qū)域重復上述劃分過程，直到滿足停止條件位置，這樣的回歸樹通常稱為最小二乘回歸樹，算法敘述如下：

輸入：訓練數(shù)據(jù)集$D$

輸出：回歸樹$f(x)$

步驟：

遍歷變量$j$，對固定的切分變 量$j$ 掃描切分點$s$，得到滿足下面關系的$(j,s)$
$$\underset{j,s}{\min }?\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i?c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i?c_2{)}^2?$$

用選定的$(j,s)$, 劃分區(qū)域并決定相應的輸出值
$$\begin{gathered} R_1(j,s)=\{x|x^{(j)}\le s\},R_2(j,s)=\{x|x^{(j)}>s\} \\ {\hat{c}}_m=\frac{1}{N}\sum _{x_i\in R_m(j,s)}{y}_j,x\in R_m,m=1,2 \end{gathered}$$

對兩個子區(qū)域調用(1)(2)步驟， 直至滿足停止條件

將輸入空間劃分為$M$個區(qū)域$R_1,R_2,\dots ,R_M$，生成決策樹：
$$f(x)=\sum _{m=1}^M{\hat{c}}_{m}I(x\in R_m)$$

CART分類樹的生成

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

假設有K個類，樣本點屬于k類的概率為$p_k$，則概率分布的基尼指數(shù)定義為：
$$Gini(p)=\sum _{k=1}^K{p}_k(1?p_k)=1?\sum _{k=1}^K{p_k}^2$$
對于二分類問題：
$$Gini(p)=2p(1?p)$$
對于給定樣本集合D，其基尼指數(shù)為：
$$Gini(D)=1?\sum _{k=1}^K(\frac{|C_k|}{|D|}{)}^2$$
如果D按照特征A是否取某個值a，分割為子集$D_1,D_2$兩個部分，即$D_1=\{(x,y)\in D|A(x)=a\},D_2=D?D_1$，則在特征A的條件下，集合D的基尼指數(shù)為：
$$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$
Gini值越大，樣本集合的不確定性也越大（與熵類似），因此每次選擇Gini小的特征來劃分。

連續(xù)值處理：

CART分類樹對連續(xù)值的處理思路和C4.5是相同的，都是將連續(xù)的特征離散化。

具體來說，假設有m個樣本，都包含連續(xù)特征A，特征A的取值從小到大排序后用：$a_1,a_2,...,a_m$表示，則CART算法取相鄰兩樣本值的平均數(shù)，一共取得m-1個劃分點，其中第i個劃分點$T_i$表示為：$T_i=\frac{a_i+a_{i+1}}{2}$。對于這m-1個點，分別計算以該點作為二元分類點時的基尼系數(shù)。選擇基尼系數(shù)最小的點作為該連續(xù)特征的二元離散分類點。比如取到的基尼系數(shù)最小的點為$a_t$，則小于$a_t$的值為類別1，大于$a_t$的值為類別2，這樣我們就做到了連續(xù)特征的離散化。要注意的是，與ID3或者C4.5處理離散屬性不同的是，如果當前節(jié)點為連續(xù)屬性，則該屬性后面還可以參與子節(jié)點的產生選擇過程。

離散值處理：

如果某個特征A被選取建立決策樹節(jié)點，如果它有A1,A2,A3三種類別，我們會在決策樹上一下建立一個三叉的節(jié)點。這樣導致決策樹是多叉樹。但是CART分類樹使用的方法不同，他采用的是不停的二分，還是這個例子，CART分類樹會考慮把A分成{A1}和{A2,A3}，{A2}和{A1,A3} {A3}和{A1,A2}三種情況，找到基尼系數(shù)最小的組合，比如{A2}和{A1,A3}，然后建立二叉樹節(jié)點，一個節(jié)點是A2對應的樣本，另一個節(jié)點是{A1,A3}對應的節(jié)點。同時，由于這次沒有把特征A的取值完全分開，后面我們還有機會在子節(jié)點繼續(xù)選擇到特征A來劃分A1和A3。這和ID3或者C4.5不同，在ID3或者C4.5的一棵子樹中，離散特征只會參與一次節(jié)點的建立。

結合上面的知識，總結得到算法流程如下：

輸入：訓練數(shù)據(jù)集D，基尼系數(shù)的閾值，樣本個數(shù)閾值。

輸出：決策樹T。

根據(jù)訓練數(shù)據(jù)集，從根結點開始，遞歸地對每個結點進行以下操作，構建二叉決策樹:

設結點的訓練數(shù)據(jù)集為D，計算現(xiàn)有特征對該數(shù)據(jù)集的基尼指數(shù)。此時，對每一個特征A,對其可能取的每個值a,根據(jù)樣本點對A=a的測試為“是"或“否”，將D分割成$D_1$和$D_2$兩部分，計算$A=a$時的基尼指數(shù)。

在所有可能的特征A以及它們所有可能的切分點a中，選擇基尼指數(shù)最小的特征及其對應的切分點作為最優(yōu)特征與最優(yōu)切分點。依最優(yōu)特征與最優(yōu)切分點，從現(xiàn)結點生成兩個子結點，將訓練數(shù)據(jù)集依特征分配到兩個子結點中去。

對兩個子結點遞歸地調用(1),，(2)，直至滿足停止條件。

生成CART決策樹。

算法停止計算的條件是結點中的樣本個數(shù)小于預定閾值，或樣本集的基尼指數(shù)小于預定閾值(樣本基本屬于同-類)，或者沒有更多特征。

對于生成的決策樹做預測的時候，假如測試集里的樣本A落到了某個葉子節(jié)點，而節(jié)點里有多個訓練樣本，則對于A的類別預測采用的是這個葉子節(jié)點里概率最大的類別。

舉個同樣的例子：

分別用$A_1,A_2,A_3,A_4$表示年齡、有工作、有房子、貸款情況4個特征，則有：
$$\begin{array}{rl}& Gini(D,A_1=1)=\frac{5}{15}(2\times \frac{2}{5}\times (1?\frac{2}{5}))+\frac{10}{15}(2\times \frac{7}{10}\times (1?\frac{7}{10}))=0.44\\ & Gini(D,A_1=2)=0.48\\ & Gini(D,A_1=3)=0.44\end{array}$$
由于$Gini(D,A_1=1)$和$Gini(D,A_1=3)$最小且相等，所以$A_1,A_3$都可以作為最優(yōu)切分點。同理可以得到$A_2,A_3$的基尼指數(shù)：
$$\begin{gathered} Gini(D,A_2=1)=0.32 \\ Gini(D,A_3=1)=0.27 \end{gathered}$$
由于$A_2,A_3$只有一個切分點，所以基尼指數(shù)最小的即為對應特征的最優(yōu)切分點。

$A_4$的基尼指數(shù)：
$$\begin{gathered} Gini(D,A_4=1)=0.36 \\ Gini(D,A_4=2)=0.47 \\ Gini(D,A_4=3)=0.32 \end{gathered}$$
$Gini(D,A_4=3)$最小，所以$A_4=3$為$A_4$的最優(yōu)切分點。

$A_1,A_2,A_3,A_4$的特征中，$Gini(D,A_3=1)=0.27$最小，所以選擇$A_3$為最優(yōu)特征，$A_3=1$為最優(yōu)切分點，于是生成了兩個子節(jié)點。左子節(jié)點是葉節(jié)點，右子節(jié)點則需要繼續(xù)在$A_1,A_2,A_4$中選擇最優(yōu)切分點，如此往復，知道所以節(jié)點都是葉節(jié)點。

CART 剪枝

CART回歸樹和CART分類樹的剪枝策略除了在度量損失的時候一個使用均方差，一個使用基尼系數(shù)，算法基本完全一樣，這里我們一起來講。

CART剪枝算法分為兩步：

首先從CART生成算法產生的原始決策樹$T_0$的底端開始，不斷剪枝，直到$T_0$的根節(jié)點，從而獲得一個子樹序列{$T_0,T_1,...,T_n$}；

通過交叉驗證子樹序列中的每個子樹進行測試，從中選擇最優(yōu)子樹作為最終的剪枝結果；

先看第一步，要明白如何構建{$T_0,T_1,...,T_n$}。$T_0$好理解，就是未經剪枝的決策樹，$T_1$怎么來的？

$T_1$是$T_0$的子樹，意味著子樹$T_1$的損失函數(shù)至少要≤剪枝前$T_0$的損失函數(shù)(剪枝前后損失函數(shù)不變，但剪枝后復雜度降低，亦可以剪枝)。CART樹T剪枝時，子樹T的損失函數(shù)如下：
$$C_{\alpha }(T)=C(T)+\alpha |T|$$
其中，$C(T)$為訓練數(shù)據(jù)的預測誤差，對回歸而言可以是平方誤差和，對分類而言可以是$sum(每個葉子節(jié)點的gini值\times 葉子節(jié)點樣本數(shù)目）$。

當α=0時，損失函數(shù)等于預測誤差，相當于不進行剪枝，對應的最優(yōu)子樹即決策樹本身；α越大，則懲罰越大，會得到更加簡單的樹，即剪枝幅度更大；

由于樹的葉子個數(shù)是離散值，所以給定α后，必定存在某個子樹$T_{\alpha }$使得損失函數(shù)$C_{\alpha }(T)$取得最小值。于是只要確定序列{${\alpha }_0,{\alpha }_1,...,{\alpha }_n$}就能確定對應的最佳子樹序列{$T_0,T_1,...,T_n$}。因此，目標為找到合適的α序列的構造。

我們將α序構造為遞增的序列，則子樹序列T是滿樹到根節(jié)點樹的遞減樹序列。首先令${\alpha }_0=0$，決策樹本身為$T_0$，在$T_0$上進行第一次剪枝（構造${\alpha }_1$），由于剪枝后的損失函數(shù)要≤剪枝前，因此，如果想在內部節(jié)點t處剪枝(即只保留節(jié)點t，左右子樹刪除)，只需要將問題聚焦于節(jié)點t以及t節(jié)點對應的子樹$T_t$上。

若在節(jié)點t處需要剪枝，則剪枝后的t變?yōu)榱巳~節(jié)點，對應的損失函數(shù)為：
$$C_{\alpha }(t)=C(t)+\alpha \times 1\text{\hspace{1em}(1)}$$
若不進行剪枝，則t及其子樹$T_t$的損失函數(shù)為：
$$C_{\alpha }(T_t)=C(T_t)+\alpha |T_t|\text{\hspace{1em}(2)}$$
由于剪枝是為了降低損失函數(shù)或者簡化樹模型，于是有：
$$C_{\alpha }(T_t)\le C_{\alpha }(t)$$
將式子(1)、(2)代入得到：
$$C(t)+\alpha \le C(T_t)+\alpha |T_t|\text{\hspace{1em}(2)}$$
解得：
$$\alpha \ge \frac{C(t)?C(T_t)}{|T_t|?1}$$
即當$\alpha \in [0,\frac{C(t)?C(T_t)}{|T_t|?1})$時，不滿足剪枝條件，若要滿足剪枝條件，至少有${\alpha }_{min}=\frac{C(t)?C(T_t)}{|T_t|?1}$，此時雖然損失函數(shù)沒有減少，但是可以簡化決策樹，達到了剪枝的條件。我們記：
$$g(t)={\alpha }_{min}=\frac{C(t)?C(T_t)}{|T_t|?1}$$
對于一顆要剪枝的樹，自下而上地對內部每個內部節(jié)點 t 計算$g(t)$，然后減去$g(t)$取值最小的$T_t$，將得到的子樹作為$T_1$。為什么取最小的$g(t)$，是因為要保證$\alpha$序列是遞增的，每次取最小的${\alpha }_{min}$可以保證不遺漏任何可以剪枝的情況。每次得到${\alpha }_{min}$的同時，$T_t$也隨之得到了，于是可以同時得到序列{${\alpha }_0,{\alpha }_1,...,{\alpha }_n$}和{$T_0,T_1,...,T_n$}。

接下來進行第二步，在獲得了可以剪枝的最優(yōu)子樹序列{$T_0,T_1,...,T_n$}之后，再將每棵樹進行交叉驗證，交叉驗證結果最好的那顆子樹便是最終的剪枝結果。

CART剪枝算法流程如下：

輸入: CART算法生成的決策樹$T_0$

輸出: 最優(yōu)決策樹$T_{\alpha }$

(1) 設$k=0,T=T_0$

(2) 設$\alpha =+\infty$。.

(3) 自下而上地對各內部結點 t 計算$C(T_t),|T_t|$以及
$$\begin{gathered} g(t)=\frac{C(t)?C(T_t)}{|T_t|?1} \\ \alpha =min(\alpha ,g(t)) \end{gathered}$$

這里，$T_t$表示以t為根結點的子樹，$C(T_t)$是對訓練數(shù)據(jù)的預測誤差，$|T_t|$ 是$T_t$的葉結點個數(shù)。

(4) 對$g(t)=\alpha$的內部結點t進行剪枝，并對葉結點t以多數(shù)表決法決定其類，得到樹T。

(5) 設$k=k+1,{\alpha }_k=\alpha ,T_k=T$

(6) 如果$T_k$不是由根結點及兩個葉結點構成的樹，則回到步驟(2); 否則令$T_k=T_n$。

(7) 采用交叉驗證法在子樹序列{$T_0,T_1,...,T_n$}中選取最優(yōu)子樹$T_{\alpha }$

參考文章：

《統(tǒng)計學習方法 第二版》

決策樹算法原理(上)

決策樹算法原理(下)

cart樹怎么進行剪枝？[椒鹽砒霜葉小沐]

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的分类与回归树(CART)相关知识的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。