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

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

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

具體的，在分類問(wèn)題中，假設(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

如果是二類分類問(wèn)題，計(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á)式為：