01|前言：

本篇接著上一篇決策樹詳解，CART是英文“classification and regression tree”的縮寫，翻譯過來是分類與回歸樹，與前面說到的ID3、C4.5一致，都是決策樹生成的一種算法，同樣也由特征選擇、樹的生成以及剪枝組成，既可以用于分類也可以用于回歸。CART算法由決策樹的生成以及決策樹剪枝兩部分組成。

02|CART的生成：

決策樹的生成就是遞歸地構建二叉決策樹的過程。對回歸樹用平方差最小化準則，對分類樹用基尼指數最小化準則，進行特征選擇，生成二叉樹。

分類樹與回歸樹的一個區別是：如果目標變量是離散型變量則用分類樹，如果目標變量是連續型變量則用回歸樹。

2.1回歸樹的生成

回歸樹是用于目標變量是連續型變量的情況下，假設X與Y分別為輸入和輸出變量，并且Y是連續型變量，給定數據即D={(x1,y1),(x2,y2),...(xn,yn)}，根據訓練數據集D生成決策樹。

前面說過，回歸樹的生成準則是平方差(總離差平方和：實際觀察值與一般水平即均值的離差總和)最小化準則，即預測誤差最小化，所以我們的目的就是找到一個分界點，以這個點作為分界線將訓練集D分成兩部分D1和D2，并且使數據集D1和D2中各自的平方差最小。然后然后再分別再D1和D2中找類似的分界點，繼續循環，直到滿足終止條件。

在具體找分解值的時候采用遍歷所有變量的方法，依次計算平方差，選擇平方差最小時對應的分解值。

2.2分類樹的生成

分類樹用基尼指數選擇最優特征(與信息增益類似)，同時決定該特征的最優二值切分點。

2.2.1基尼指數

分類問題中，假設有K個類，樣本點屬于第k類的概率為pk，則概率分布的基尼指數定義為：

對于二分類問題，若樣本點屬于第一類的概率為p，則概率分布的基尼指數為：Gini(p)=2p(1-p)。

對于樣本給定的集合D，其基尼指數為：Gini(D)=1-∑(|Ck|/|D|)*2，這里Ck是D中屬于第k類的樣本子集，K是類的個數。

條件基尼指數：

上面公式表示在特征A的條件下，集合D的基尼指數，其中D1和D2表示樣本集合D根據特征A是否取某一個可能值a被分割成的兩部分。

基尼指數Gini(D)表示集合D的不確定性，基尼指數Gini(D,A)表示經A=a分割后集合D的不確定性。基尼指數數值越大，樣本集合的不確定性越大。

2.2.2算法步驟

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

輸出：CART決策樹

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

設結點的訓練數據集為D，計算現有特征對該數據集的基尼指數，此時，對每一個特征A，對其可能取的每一個值a,根據樣本點A=a的測試為“是”或“否”將D分割成D1和D2兩部分，然后計算Gini(D,A)。

在所有可能的特征A以及他們所有可能的切分點a中，選擇基尼指數最小的特征及其對應的切分點作為最優特征與最佳切分點。依最優特征與最優切分點，從現結點生成兩個子節點，將訓練數據集依特征分配到兩個子節點中去。

對兩個子節點遞歸調用.1，.2，直至滿足停止條件。

生成CART決策樹。

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

03|CART剪枝：

我們再前面那一章節提過剪枝是為了避免數據發生過擬合現象，而避免這種情況發生的方法就是使損失函數最小化。

先看看損失函數的公式：

在α已知得情況下，要使上面得Cα(T)最小，就需要使|T|最小，即子樹得葉節點數量最小；或者使訓練誤差最小，要使訓練誤差最小，就需要再引入新的特征，這樣更會增加樹得復雜度。所以我們主要通過降低|T|來降低損失函數，而這主要是通過剪去一些不必要得枝得到得。

但是在具體剪得過程中，我們需要有一個評判標準用來判斷哪些枝可以剪，哪些使不可以剪得。而這個評判標準就是剪枝前后該樹得損失函數是否減少，如果減小，就對該枝進行剪枝。

具體地，從整數T0開始剪枝，對T0的任意內部節點t，以t為單結點樹(即該樹沒有葉節點)的損失函數是：Cα(t)=C(t)+α

以t為根節點的子樹Tt的損失函數是：Cα(Tt)=C(Tt)+α|Tt|

當α=0或者充分小，有不等式：?

當α繼續增大時，在某一α處會有：

當α再繼續增大時，在某一α處會有：

當下式成立時:

在這個時候，Tt與t有相同的損失函數值，而t的結點少，因此t比Tt更可取，對Tt進行剪枝。

為此，可以對T0中的每一內部節點t，計算g(t)=(C(t)-C(Tt))/(|Tt|-1)，該式表示剪枝后整體損失函數減少的程度。在T0中剪去g(t)最小的Tt,將得到的子樹作為T1，同時將最小的g(t)設為α1.T1為區間最小[α1,α2)的最優子數。如此剪枝下去，直至得到根節點，在這一過程中不斷增加α的值，產生新的區間。

在剪枝得到的子樹序列T0，T1，...，Tn中獨立驗證數據集，測試子樹序列的T0，T1，...，Tn中各顆子樹的平方誤差或基尼指數。平方誤差或基尼指數最小的決策樹被認為是最優的決策樹。

3.1算法步驟：

輸入：CART算法生成的決策樹T0

輸出：最優決策樹Tα

設k=0,T=T0

設α=+∞

自上而下地對各內部節點t計算C(Tt)，|Tt|以及g(t)，這里，Tt表示以t為根節點的子樹，C(Tt)是對訓練數據的預測誤差。|Tt|是Tt的葉結點個數。

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

設k=k+1，αk=α,Tk=T。

如果Tk不是由根節點及兩個葉節點構成的樹，則回到步驟(3)；否則令Tk=Tn。

采用交叉驗證法在子樹序列T0，T1，...，Tn中選取最優子樹Tα。

你還可以看：

機器學習開篇

決策樹詳解

總結

以上是生活随笔為你收集整理的机器学习第五篇：详解决策树-CART算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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