決策樹學習筆記(三):CART算法,決策樹總結

點擊上方「Python數據科學」，選擇「星標公眾號」

關鍵時刻，第一時間送達！

作者：xiaoyu

介紹：一個半路轉行的數據挖掘工程師

 

推薦導讀：本篇為樹模型系列第三篇，旨在從最簡單的決策樹開始學習，循序漸進，最後理解並掌握複雜模型GBDT，Xgboost，為要想要深入了解機器學習算法和參加數據挖掘競賽的朋友提供幫助。

▍前情回顧

前兩篇介紹了決策樹主要的三個步驟，以及ID3和C4.5算法：

本篇將繼續介紹決策的第三種算法：CART算法，它可以說是學習決策樹的核心了。高級集成學習很多複雜框架都是基於CART的。下面將詳細介紹CART算法的來龍去脈。

CART生成算法

CART剪枝算法

CART算法小結

決策樹算法優缺點總結

▍CART生成算法

為什麼叫CART算法呢？這還要從它的英文單詞說起。CART是 "Classification and Regression Trees" 的縮寫，意思是 "分類回歸樹"。從它的名字上就不難理解了，CART算法是既可以用於分類的，也可以用於回歸的。

很多朋友詫異於決策樹為什麼可以用於回歸，明明是if-then結構用於分類的。下面我們來分別介紹CART分類和回歸兩種情況。

分類樹生成算法

CART算法的分類樹是與ID3和C4.5有所不同。下面我們針對特徵值的類型來分別介紹CART算法是如何進行分類的，以及和C4.5有什麼異同。

如果特徵值是連續值：CART的處理思想與C4.5是相同的，即將連續特徵值離散化。唯一不同的地方是度量的標準不一樣，CART採用基尼指數，而C4.5採用信息增益比。下面舉個例子說明下：

特徵a有連續值m個，從小到大排列。m個數值就有m-1個切分點，分別使用每個切分點把連續數值離散劃分成兩類，將節點數據集按照劃分點分為D1和D2子集，然後計算每個劃分點下對應的基尼指數，對比所有基尼指數，選擇值最小的一個作為最終的特徵劃分。

基尼指數公式，以及基於特徵A劃分後的基尼指數

以上就實現了將連續特徵值離散化，但是CART與ID3，C4.5處理離散屬性不同的是：如果當前節點為連續屬性，則該屬性（剩餘的屬性值）後面還可以參與子節點的產生選擇過程。

如果特徵值是離散值：CART的處理思想與C4.5稍微所有不同。如果離散特徵值多於兩個，那麼C4.5會在節點上根據特徵值劃分出多叉樹。但是CART則不同，無論離散特徵值有幾個，在節點上都劃分成二叉樹。CART樹是如何進行分類的呢？

還是假設特徵a有m個離散值。分類標準是：每一次將其中一個特徵分為一類，其它非該特徵分為另外一類。依照這個標準遍歷所有的分類情況，計算每種分類下的基尼指數，最後選擇值最小的一個作為最終的特徵劃分。

特徵值連續和離散有各自的處理方法，不應該混淆使用。比如分類0,1,2隻代表標籤含義，如果進行加減的運算或者求平均則沒有任何意義。因此，CART分類樹會根據特徵類型選擇不同的劃分方法，並且與C4.5不同是，它永遠只有兩個分支。

李航 「統計學習方法」 中的分類樹算法流程僅僅是針對特徵是離散型的情況，並沒有提及連續值的情況。本篇根據上面我們介紹兩個特徵類型情況重新給出一個算法流程（主要就是區分兩種不同特徵類型）：

輸入：訓練數據集D，停止計算的參數條件。 
輸出：CART決策樹。

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

1：如果樣本個數小於閾值或者沒有特徵，
  則返回決策子樹，當前節點停止遞歸。
2：計算樣本集D的基尼係數，如果基尼係數小於閾值，
  則返回決策樹子樹，當前節點停止遞歸。
3：識別各個特徵類型，離散值還是連續值？
  對每種類型使用相應的處理方法並計算每個切分下的基尼係數。
  缺失值的處理方法和C4.5算法裡描述的相同。
4：在計算出來的各個特徵的各個特徵值對數據集D的基尼係數中，
  選擇基尼係數最小的特徵A和對應的特徵值a。
  根據這個最優特徵和最優特徵值，把數據集劃分成兩部分D1和D2，
  同時建立當前節點的左右節點，做節點的數據集D為D1，右節點的數據集D為D2.
5：對左右的子節點遞歸的調用1-4步，生成決策樹。

算法停止計算的條件是：如步驟1,2中所示，結點中的樣本個數小於預定閾值，
或樣本集的Gini係數小於預定閾值（樣本基本屬於同一類），或者沒有更多特徵。

回歸樹生成算法

與分類樹不同，回歸樹的預測變量是連續值，比如預測一個人的年齡，又或者預測季度的銷售額等等。另外，回歸樹在選擇特徵的度量標準和決策樹建立後預測的方式上也存在不同。

預測方式

一個回歸樹對應著輸入特徵空間的一個劃分，以及在劃分單元上的輸出值。先假設數據集已被劃分，R1,R2,...,Rm共m的子集，回歸樹要求每個劃分Rm中都對應一個固定的輸出值cm。

這個cm值其實就是每個子集中所有樣本的目標變量y的平均值，並以此cm作為該子集的預測值。所有分支節點都是如此，葉子節點也不例外。因此，可以知道回歸樹的預測方式是：將葉子節點中樣本的y均值作為回歸的預測值。而分類樹的預測方式則是：葉子節點中概率最大的類別作為當前節點的預測類別。

選擇特徵的度量標準

CART回歸樹對於特徵類型的處理與分類樹一樣，連續值與離散值分開對待，並只能生成二叉樹。但是CART回歸樹對於選擇特徵的度量標準則完全不同。

分類樹的特徵選擇標準使用基尼指數，而回歸樹則使用RSS殘差平方和。了解線性回歸的朋友知道，損失函數是以最小化離差平方和的形式給出的。回歸樹使用的度量標準也是一樣的，通過最小化殘差平方和作為判斷標準，公式如下：

注意：計算的是屬性劃分下樣本的目標變量y的殘差平方和，而非屬性值。

上面公式的含義是：計算所有的特徵以及相應所有切分點下的殘差平方和，找到一組(特徵j，切分點s)，以滿足：分別最小化左子樹和右子樹的殘差平方和，並在此基礎上再次最小化二者之和。

其實，回歸樹也有分類的思想。所謂 「物以類聚」，相同類之間的目標變量值才會更接近，方差值也就會更小。對於回歸樹的生成算法，除了以上兩點外，其它都分類樹是相同的。

▍CART剪枝算法

對於決策樹剪枝，上一篇已經介紹：決策樹學習筆記（二）：剪枝，ID3，C4.5。這部分重點介紹下CART是如何剪枝的？選擇的是哪種方式？

CART回歸樹和CART分類樹的剪枝策略除了在度量損失的時候一個使用均方差，一個使用基尼係數，算法基本完全一樣，因此將它們統一來說。CART採用的辦法是後剪枝法，即先生成決策樹，然後產生所有可能的剪枝後的CART樹，然後使用交叉驗證來檢驗各種剪枝的效果，選擇泛化能力最好的剪枝策略。

也就是說，CART樹的剪枝算法可以概括為兩步：

1）是從原始決策樹生成各種剪枝效果的決策樹序列。

2）是用交叉驗證來檢驗剪枝後的預測能力，選擇泛化預測能力最好的剪枝後的數作為最終的CART樹。

1）生成決策樹序列

CART採用CCP（代價複雜度）的後剪枝方法，定義了決策樹的損失函數和正則化項。公式如下：

CART剪枝與C4.5有所不同，C4.5剪枝算法是人為給定一個alpha，然後從葉結點逐漸向根節點回溯，然而CART多了一個遍歷alpha的步驟，從0~+無窮。

我們先明確幾個概念，然後將這幾個概念結合起來就可以理解整個生成決策樹序列的算法流程了。

現假設我選定了決策樹的任意一個節點t，並將節點t作為根節點。那麼這個時候我想知道節點t下的分支是否需要剪枝，怎麼辦呢？

很容易想到，我們可以對比一下剪枝以後的預測誤差和剪枝以前的預測誤差值的大小，如果不剪枝的誤差比剪枝的大，那麼我們就執行剪枝。用公式來抽象描述一下：

以t為單節點樹的損失函數，|t|=1（剪枝後）

以t為根節點的Tt損失函數（剪枝前）

現在我們有了以t為根節點剪枝前後的損失函數，我們只需要對比一下就知道了。由於alpha未確定，因此臨界的情況是：

我們把這時候的alpha臨界值稱為誤差增益率，用g(t)來表示，公示如下：

我們可以將g(t)簡單的理解為一種閾值，如果alpha大於或者等於g(t)，那麼就剪枝。因為在相等的情況下，不剪枝和剪枝達到同樣的效果，也就相當於這些分支沒有什麼作用。如果alpha小於g(t)，則保留，不剪枝。

考慮另外一個問題，如何選擇用哪個節點進行剪枝呢？

我們上面已經找到了對某個節點下是否該剪枝的方法了，但我們開始假設的是任意一個節點t，是一個通用的方法。對於一個生成完整的決策樹而言，是至少擁有一個節點的。如果一個決策樹有n個節點，那麼我就會有相應的n個誤差增益率g(t)。

現在alpha是未知的，我們需要從零開始遍歷，直到正無窮。顯然，如果節點下的g(t)越小，alpha就會越先達到該節點的閾值，而此時的alpha大小還不足以達到其它節點的閾值。這說明g(t)越小的節點應該越先被剪枝。

如果我們將所有g(t)排序，g1(t)，g2(t)，...，gn(t)，那麼我就會先對g1(t)對應的節點剪枝，得到一個最優子樹，和alpha區間。然後在此基礎上再對g2(t)對應的節點進行剪枝，得到第二個最優子樹，直到得到n個最優子樹的序列。

有的朋友不明白：既然是遍歷alpha，從0~+無窮，那為什麼還會得到一個alpha的區間呢？這個很好理解，因為每個alpha區間是對應一個特徵節點的，而決策樹的節點是有限的，因此我們真正的目的並不是遍歷alpha，而是通過遍歷alpha與各個g(t)比較而得到(n+1)個最優子樹序列。

交叉驗證

得到字數序列以後，我們可以使用獨立的驗證數據集，測試各子樹的平方誤差或基尼指數。平方誤差或基尼指數最小的決策樹被認為是最優的決策樹。並且，每顆子樹都對應著一個alpha，所以最優子樹確定了，alpha也就確定了。

上面已經將CART剪枝進行詳細的分析了，下面看一下CART剪枝的整個算法流程。

▍CART算法小結

上面我們對CART算法做了一個詳細的介紹，CART算法相比C4.5算法的分類方法，採用了簡化的二叉樹模型，同時特徵選擇採用了近似的基尼係數來簡化計算。當然CART樹最大的好處是還可以做回歸模型，這個C4.5沒有。下表給出了ID3，C4.5和CART的一個比較總結。希望可以幫助大家理解。

看起來CART算法高大上，那麼CART算法還有沒有什麼缺點呢？有，主要的缺點如下：

1）無論是ID3, C4.5還是CART,在做特徵選擇的時候都是選擇最優的一個特徵來做分類決策，但是大多數，分類決策不應該是由某一個特徵決定的，而是應該由一組特徵決定的。這樣決策得到的決策樹更加準確。這個決策樹叫做多變量決策樹(multi-variate decision tree)。在選擇最優特徵的時候，多變量決策樹不是選擇某一個最優特徵，而是選擇最優的一個特徵線性組合來做決策。這個算法的代表是OC1，這裡不多介紹。

2）如果樣本發生一點點的改動，就會導致樹結構的劇烈改變。這個可以通過集成學習裡面的隨機森林之類的方法解決。　　　

▍決策樹算法優缺點總結

我們前面介紹了決策樹的特徵選擇，生成，和剪枝，然後對ID3, C4.5和CART算法也分別進行了詳細的分析。下面我們來看看決策樹算法作為一個大類別的分類回歸算法的優缺點。

決策樹算法的優點

1）簡單直觀，生成的決策樹很直觀。

2）基本不需要預處理，不需要提前歸一化，處理缺失值。

3）使用決策樹預測的代價是O(log2m)O(log2m)。 m為樣本數。

4）既可以處理離散值也可以處理連續值。很多算法只是專注於離散值或者連續值。

5）可以處理多維度輸出的分類問題。

6）相比於神經網絡之類的黑盒分類模型，決策樹在邏輯上可以得到很好的解釋

7）可以交叉驗證的剪枝來選擇模型，從而提高泛化能力。

8） 對於異常點的容錯能力好，健壯性高。

決策樹算法的缺點

1）決策樹算法非常容易過擬合，導致泛化能力不強。可以通過設置節點最少樣本數量和限制決策樹深度來改進。

2）決策樹會因為樣本發生一點點的改動，就會導致樹結構的劇烈改變。這個可以通過集成學習之類的方法解決。

3）尋找最優的決策樹是一個NP難的問題，我們一般是通過啟發式方法，容易陷入局部最優。可以通過集成學習之類的方法來改善。

4）有些比較複雜的關係，決策樹很難學習，比如異或。這個就沒有辦法了，一般這種關係可以換神經網絡分類方法來解決。

5）如果某些特徵的樣本比例過大，生成決策樹容易偏向於這些特徵。這個可以通過調節樣本權重來改善。‍‍

下一篇將會介紹一個決策樹應用的實戰內容，以及如何使用sklearn進行決策樹的調參。

[1] 統計學習方法，李航，p73

[2] https://www.cnblogs.com/pinard/p/6053344.html

[3] https://blog.csdn.net/zlsjsj/article/details/81387393

推薦閱讀 

決策樹學習筆記（二）：剪枝，ID3，C4.5

教程 | 十分鐘學會函數式 Python

我們分析了633個中國城市，發現五分之二都在流失人口

決策樹學習筆記（一）：特徵選擇