2.2.2　CART分類決策樹的原理

CART算法可以生成分類決策樹和回歸決策樹。我們首先介紹CART分類決策樹的算法流程，然后給出一個決策樹生成實例。

2.2.2.1　CART分類決策樹的算法流程

1. 輸入

輸入為訓練數據集D和停止計算的條件。其中，訓練數據集D包含多條記錄，每個記錄由多個屬性構成。每個屬性的數據類型均為離散的，例如二值類型、標稱值或枚舉值類型等。停止計算的條件可以是節點中的樣本個數小于預定閾值，或樣本集的基尼指數小于預定閾值，或沒有更多特征屬性等。

2. 輸出

輸出為CART分類樹。

3. CART分類決策樹的生成流程

CART算法從根節點開始，用訓練集遞歸地建立CART分類決策樹。

1）設訓練數據集為D，計算數據集現有的所有屬性特征對該訓練集的基尼增益。對每一個屬性特征F，對其所有可能取值的每個值f，根據D中的樣本實例對F=f的測試為“是”或“否”，將數據集D分割成D₁和D₂兩個子集，利用基尼增益公式計算F=f時的基尼增益。假設有N_F個屬性特征，對于每一個屬性特征i，可能取值數量為N_i，則總共需要計算的基尼不純度次數為2+1，基尼增益或基尼指數的計算次數為。

2）在所有可能的屬性特征F以及它們所有可能的切分點f_i中，選擇基尼增益最大的特征及其對應的切分點作為最優切分點，依據該最優切分點切割，生成兩個子節點，左子節點為D₁，右子節點為D₂。

3）對兩個子節點遞歸調用步驟1~2，直至滿足停止條件。

4）生成一棵完整的二叉CART分類決策樹。

4. CART分類決策樹的優化

使用決策樹模型擬合數據時容易產生過擬合，解決辦法是對決策樹進行剪枝處理。決策樹剪枝有兩種思路：預剪枝（pre-pruning）和后剪枝（post-pruning）。

5. CART分類決策樹模型的使用

決策樹算法是一種通過對歷史樣本數據進行測算實現對新數據的分類和預測的算法。整個決策過程從根節點開始，從上到下進行，根據數據的分類在每個決策節點給出不同的結果。使用決策樹的過程和人眼比對的過程類似：先比對根節點，根據比對結果走向決策樹的不同子節點；再在子節點處進行比對，直到比對到葉子節點，即得到結果。對生成的CART分類決策樹做預測的時候，如果測試集里的某個樣本A落到了某個葉子節點，且該葉子節點里存在多個類別的訓練樣本，則概率最大的訓練樣本是樣本A的類別。

2.2.2.2　CART分類決策樹的生成實例

下面以天氣與是否打網球的數據集為例，具體介紹CART分類決策樹的生成過程。是否打網球的影響因素有天氣、溫度、濕度和風力，共有如表2.2所示的14條記錄。

表2.2　天氣與是否打網球的數據（PlayTennis數據集）

首先確定根屬性特征，計算原始樣本數據集的基尼不純度：

G=1-（9/14）2-（5/14）2≈1-0.413-0.128=0.459

我們考慮第一個屬性特征：天氣。它是一個標稱值類型，包含3個枚舉值，即晴朗、陰天和下雨。統計該屬性特征取不同值時的樣本數量，如表2.3所示。

表2.3　天氣數據

根據表2.3可以得到：

G（Outlook=Sunny）=1-（2/5）2-（3/5）2=1-0.16-0.36=0.48

G（Outlook≠Sunny）=1-（7/9）2-（2/9）2≈1-0.61-0.05=0.34

G（Outlook=Overcast）=1-（4/4）2-（0/4）2=0

G（Outlook≠Overcast）=1-（5/10）2-（5/10）2=0.5

G（Outlook=Rain）=1-（3/5）2-（2/5）2=1-0.36-0.16=0.48

G（Outlook≠Rain）=1-（6/9）2-（3/9）2≈1-0.44-0.11=0.45

這樣，原始的樣本數據集會被劃分為兩個子集合。那么，具體采用天氣的哪一個值作為分割點呢?如果采用Outlook=Sunny，則產生的基尼增益和基尼指數為

GG（Outlook=Sunny）=G-5/14×G（Outlook=Sunny）-9/14×G（Outlook≠Sunny）

=0.459-5/14×0.48-9/14×0.34≈0.459-0.171-0.219=0.069

GI（Outlook=Sunny）=0.39

如果采用Outlook=Overcast，則產生的基尼增益和基尼指數為

GG（Outlook=Overcast）=G-4/14×G（Outlook=Overcast）

-10/14×（1-G（Outlook=Overcast））

=0.459-4/14×0-10/14×0.5≈0.102

GI（Outlook=Overcast）=0.357

如果采用Outlook=Rain，則產生的基尼增益和基尼指數為

GG（Outlook=Rain）=G-5/14×G（Outlook=Rain）-9/14×（1-G（Outlook=Rain））

=0.459-5/14×0.48-9/14×0.45≈0.459-0.171-0.288=0

GI（Outlook=Rain）=0.459

那么，從基尼增益或基尼指數的角度看，選擇的分割值為Overcast，基尼增益為0.102，基尼指數為0.357。

類似地，我們考慮第二個屬性特征：溫度。它也是一個標稱值類型，有3個取值，分別為熱、溫和以及涼爽。統計該屬性特征取不同值時的樣本記錄數量，如表2.4所示。

表2.4　溫度數據

根據表2.4可以得到：

G（Temperature=Hot）=1-（2/4）2-（2/4）2=0.5

G（Temperature≠Hot）=1-（7/10）2-（3/10）2=1-0.49-0.09=0.42

G（Temperature=Cool）=1-（3/4）2-（1/4）2=1-0.5625-0.0625=0.375

G（Temperature≠Cool）=1-（6/10）2-（4/10）2=1-0.36-0.16=0.48

G（Temperature=Mild）=1-（4/6）2-（2/6）2≈1-0.444-0.111=0.445

G（Temperature≠Mild）=1-（5/8）2-（3/8）2≈1-0.391-0.111=0.445

如果Temperature=Hot，則產生的基尼增益和基尼指數為

GG（Temperature=Hot）=G-4/14×G（Temperature=Hot）-10/14×G（Temperature≠Hot）

=0.459-4/14×0.5-10/14×0.42≈0.459-0.143-0.3=0.016

GI（Temperature=Hot）=0.443

如果Temperature=Cool，則產生的基尼增益和基尼指數為

GG（Temperature=Cool）=G-4/14×G（Temperature=Cool）-10/14×G（Temperature≠Cool）

=0.459-4/14×0.375-10/14×0.48≈0.459-0.107-0.343=0.009

GI（Temperature=Cool）=0.45

如果Temperature=Mild，則產生的基尼增益和基尼指數為

GG（Temperature=Mild）=G-6/14×G（Temperature=Mild）-8/14×G（Temperature≠Mild）

=0.459-6/14×0.445-8/14×0.445≈0.459-0.445=0.014

GI（Temperature=Mild）=0.445

那么，從基尼增益或基尼指數的角度看，選擇的分割值為Hot，基尼增益為0.016，基尼指數為0.443。

類似地，我們考慮第三個屬性特征：濕度。它也是一個二值類型，有2個取值，分別為高和正常。統計該屬性特征取不同值時的樣本記錄數量，如表2.5所示。

表2.5　濕度數據

根據表2.5可以得到：

G（Humidity=High）=1-（3/7）2-（4/7）2≈1-0.184-0.327=0.489

G（Humidity=Normal）=1-（6/7）2-（1/7）2≈1-0.735-0.02=0.245

G（Humidity≠High）=G（Humidity=Normal）=0.244

G（Humidity≠Normal）=G（Humidity=High）=0.489

如果Humidity=High，則產生的基尼增益和基尼指數為

GG（Humidity=High）=G-7/14×G（Humidity=High）-7/14×G（Humidity≠High）

≈0.459-0.245-0.122=0.092

GI（Humidity=High）=0.367

如果Humidity=Normal，則產生的基尼增益和基尼指數為

GG（Humidity=Normal）=G-7/14×G（Humidity=Normal）-7/14×G（Humidity≠Normal）

≈0.459-0.122-0.245=0.092

GI（Humidity=Normal）=0.367

那么，從基尼增益或基尼指數的角度看，選擇的分割值為High或Normal，基尼增益為0.092，基尼指數為0.367。

同樣，我們考慮第四個屬性特征：風力。它也是一個二值類型，有2個取值，分別為弱和強。統計該屬性特征取不同值時的樣本記錄數量，如表2.6所示。

表2.6　風力數據

根據表2.6可以得到：

G（Wind=Weak）=1-（6/8）2-（2/8）2=1-0.5625-0.062=0.375

G（Wind=Strong）=1-（3/6）2-（3/6）2=1-0.25-0.25=0.5

G（Wind≠Weak）=G（Wind=Strong）=0.5

G（Wind≠Strong）=G（Wind=Weak）=0.375

如果Wind=Weak，則產生的基尼增益和基尼指數為

GG（Wind=Weak）=G-8/14×G（Wind=Weak）-6/14×G（Wind≠Weak）

=0.459-8/14×0.375-6/14×0.5≈0.459-0.214-0.214=0.031

GI（Wind=Weak）=0.428

如果Wind=Strong，則產生的基尼增益和基尼指數為

GG（Wind=Strong）=G-6/14×G（Wind=Strong）-8/14×G（Wind≠Strong）

=0.459-6/14×0.5-8/14×0.375≈0.459-0.214-0.214=0.031

GI（Wind=Strong）=0.428

那么，從基尼增益或基尼指數的角度看，選擇的分割值為Weak或Strong，基尼增益為0.031，基尼指數為0.428。

最后，我們根據每個屬性特征的基尼增益或基尼指數，就可以決定決策樹的根節點。從表2.7中可以看出，選擇天氣屬性時，基尼增益是最大的。因此天氣被選擇為決策樹的根節點，且分割點為Overcast。

表2.7　各個屬性特征的基尼增益、基尼指數與分割點表

這樣，原樣本數據集被分割成兩個子集：子集D₁（表2.8）為Outlook=Overcast，子集D₂（表2.9）為Outlook≠Overcast。

表2.8　子集D₁：Outlook=Overcast

表2.9　子集D₂：Outlook≠Overcast

接下來考慮子集D₁，由于該子集中所有樣本都是打網球，因此，該子集直接生成葉子節點。對于子集D₂，可以繼續上述過程，選擇合適的屬性特征及其分割點，生成后續的子節點，這里就不再介紹了。