簡介

CART與C4.5類似，是決策樹算法的一種。此外，常見的決策樹算法還有ID3，這三者的不同之處在于特征的劃分：

• ID3：特征劃分基于信息增益
• C4.5：特征劃分基于信息增益比
• CART：特征劃分基于基尼指數(shù)

基本思想

CART假設(shè)決策樹是二叉樹，內(nèi)部結(jié)點特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價于遞歸地二分每個特征，將輸入空間即特征空間劃分為有限個單元，并在這些單元上確定預(yù)測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。

CART算法由以下兩步組成：

• 決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大;
• 決策樹剪枝：用驗證數(shù)據(jù)集對已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹，這時損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。

CART決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。CART決策樹既可以用于分類也可以用于回歸。本文我們僅討論用于分類的CART。對分類樹而言，CART用Gini系數(shù)最小化準(zhǔn)則來進(jìn)行特征選擇，生成二叉樹。 CART生成算法如下：

• 輸入：訓(xùn)練數(shù)據(jù)集D，停止計算的條件：
• 輸出：CART決策樹。

根據(jù)訓(xùn)練數(shù)據(jù)集，從根結(jié)點開始，遞歸地對每個結(jié)點進(jìn)行以下操作，構(gòu)建二叉決策樹：

設(shè)結(jié)點的訓(xùn)練數(shù)據(jù)集為D，計算現(xiàn)有特征對該數(shù)據(jù)集的Gini系數(shù)。此時，對每一個特征A，對其可能取的每個值a，根據(jù)樣本點對A=a的測試為“是”或 “否”將D分割成D1和D2兩部分，計算A=a時的Gini系數(shù)。

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

對兩個子結(jié)點遞歸地調(diào)用步驟l~2，直至滿足停止條件。

生成CART決策樹。

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

代碼

代碼已在github上實現(xiàn)(調(diào)用sklearn)，這里也貼出來

測試數(shù)據(jù)集為MNIST數(shù)據(jù)集，獲取地址為train.csv

運行結(jié)果