在決策樹算法原理(上)這篇里，我們講到了決策樹里ID3算法，和ID3算法的改進(jìn)版C4.5算法。對(duì)于C4.5算法，我們也提到了它的不足，比如模型是用較為復(fù)雜的熵來度量，使用了相對(duì)較為復(fù)雜的多叉樹，只能處理分類不能處理回歸等。對(duì)于這些問題， CART算法大部分做了改進(jìn)。CART算法也就是我們下面的重點(diǎn)了。由于CART算法可以做回歸，也可以做分類，我們分別加以介紹，先從CART分類樹算法開始，重點(diǎn)比較和C4.5算法的不同點(diǎn)。接著介紹CART回歸樹算法，重點(diǎn)介紹和CART分類樹的不同點(diǎn)。然后我們討論CART樹的建樹算法和剪枝算法，最后總結(jié)決策樹算法的優(yōu)缺點(diǎn)。

1. CART分類樹算法的最優(yōu)特征選擇方法

我們知道，在ID3算法中我們使用了信息增益來選擇特征，信息增益大的優(yōu)先選擇。在C4.5算法中，采用了信息增益比來選擇特征，以減少信息增益容易選擇特征值多的特征的問題。但是無論是ID3還是C4.5,都是基于信息論的熵模型的，這里面會(huì)涉及大量的對(duì)數(shù)運(yùn)算。能不能簡(jiǎn)化模型同時(shí)也不至于完全丟失熵模型的優(yōu)點(diǎn)呢？有！CART分類樹算法使用基尼系數(shù)來代替信息增益比，基尼系數(shù)代表了模型的不純度，基尼系數(shù)越小，則不純度越低，特征越好。這和信息增益(比)是相反的。

具體的，在分類問題中，假設(shè)有K個(gè)類別，第k個(gè)類別的概率為pkpk, 則基尼系數(shù)的表達(dá)式為：

Gini(p)=∑k=1Kpk(1?pk)=1?∑k=1Kp2kGini(p)=∑k=1Kpk(1?pk)=1?∑k=1Kpk2

如果是二類分類問題，計(jì)算就更加簡(jiǎn)單了，如果屬于第一個(gè)樣本輸出的概率是p，則基尼系數(shù)的表達(dá)式為：

Gini(p)=2p(1?p)Gini(p)=2p(1?p)

對(duì)于個(gè)給定的樣本D,假設(shè)有K個(gè)類別, 第k個(gè)類別的數(shù)量為CkCk,則樣本D的基尼系數(shù)表達(dá)式為：