CART決策樹-One Step By One Step

背景

雖然近期Deep Learning已經是機器學習領域的核心及焦點，但是其由於神經網絡本身的屬性，我們並不能清晰地知道其決策的原因。也是因為這個原因，決策樹算法仍然保持了其熱度。

接下來我將借用以下鏈接的例子，進行CART（Classifier and Regression Tree）進行逐步講解。CART使用Gini Index 建立決策節點。接下來將結合例子逐步講解。

鏈接：https://sefiks.com/2018/08/27/a-step-by-step-cart-decision-tree-example/

數據

本次使用的數據是，根據Outlook（天氣）、Temp.（溫度）、Humidity（溼度）、Wind（風度）等四個維度來決定是否去打高爾夫球的決策。同時，我們有14組這樣的數據（or實例）

思考

結合以上數據，我們大概能腦補出，CART大概是怎麼回事。如下圖，假如 對於是否打高爾夫球的決定，我們需要4個因素的輸入。比如，先看天氣怎麼樣、再看溫度怎麼樣.... 這樣最後的話我們在考慮了四個因素之後，我們就能從14個數據例子中 找到最終的決策 Yes or No.

所以決策樹做的事情就是，根據列示的4個特徵Outlook、Temp.、Humidity、Wind來判斷是否去打高爾夫球。

這樣看起來很簡單，實際上決策樹的構建也真的就是那麼簡單。CART決策樹的構建其實就一個核心問題：為什麼第一個“節點”是 Outlook（天氣） 而不是Temp.（溫度）呢？既然有一個排序那麼就有一個規則。

Gini Index

上一部分提出一個問題，CART決策樹的構建的一個核心問題是，其節點的順序問題。那麼對於CART決策樹來說，其原則上是 希望其節點分裂後的子節點更集中於某一分類，或者“更純”。簡單來說，就是希望分裂後，對於是否去打高爾夫球（Yes or No）的分類更清晰。

其實這個原則也很好理解，舉個例子，我們如果有一個節點，可以將最終的分類Yes or No完全分開。那麼我們肯定是優先做該節點的分裂。因為該節點分裂後，子節點的分類就更純了。

通俗一點解釋，為什麼優先看某個特徵呢、為什麼是純度呢？ 舉個例子，就拿買衣服來說，假如我們優先看的是價格、再看尺寸。所以，我們在進入某個門店的時候，會先問價格。但是為什麼呢？ 因為我們覺得價格是“權重影響力”最大的因素，當價格合適的時候，才會想往後看。那麼，對於一個“非常有影響力的因素”來說，其貴、和不貴 對於其最終的決策影響非常大。 但是我們也可能會發現，“有沒有口袋”也是衣服的特徵之一，但是因為這個特徵不重要，那麼在基於這個特徵分裂之後，我們發現“有口袋”的樣本里面，選擇買和不買的差不多數量；“無口袋”的樣本里面也同樣的情況。這也就是大家買衣服的時候，先看價格的原因，因為其對最終結果影響力大，所以其分裂後的“純度”也相應的最高。

而“純度”我們需要引入Gini Index，其是每個分類概率的平方。對於這個公式的理解，我們將在案例實際計算過程中解釋。

Gini = 1 – Σ (Pi)2 for i=1 to number of classes

Outlook天氣

天氣是一個特徵，其可以是Sunny、overcast或者rainy。根據例子中的14個數據，我們總結如下：

Gini(Outlook=Sunny) = 1 – (2/5)2 – (3/5)2 = 1 – 0.16 – 0.36 = 0.48

Gini(Outlook=Overcast) = 1 – (4/4)2 – (0/4)2 = 0

Gini(Outlook=Rain) = 1 – (3/5)2 – (2/5)2 = 1 – 0.36 – 0.16 = 0.48

然後，我們根據不同天氣的加權平均計算出最終的Gini Index

Gini(Outlook) = (5/14) x 0.48 + (4/14) x 0 + (5/14) x 0.48 = 0.171 + 0 + 0.171 = 0.342

公式解釋：根據上面的計算，我們可以看出Gini其計算的意義。 比如 Outlook為 Overcast時，有4個例子，4個都選擇的是Yes 去打高爾夫。其Gini算出來的是0. 從而我們可以看出，當Gini越小時，該節點的分類越純。當然，我們目前是在計算Outlook、Temp.、Wind、Humidity等四個特徵的Gini Index.

Temperature溫度

同樣的，溫度特徵有三個子節點：Cool、Hot、Mild

Gini(Temp=Hot) = 1 – (2/4)2 – (2/4)2 = 0.5

Gini(Temp=Cool) = 1 – (3/4)2 – (1/4)2 = 1 – 0.5625 – 0.0625 = 0.375

Gini(Temp=Mild) = 1 – (4/6)2 – (2/6)2 = 1 – 0.444 – 0.111 = 0.445

我們可以計算對於溫度特徵的 加權平均 Gini Index

Gini(Temp) = (4/14) x 0.5 + (4/14) x 0.375 + (6/14) x 0.445 = 0.142 + 0.107 + 0.190 = 0.439

Humidity

溼度特徵只有兩個選項：High、Normal

Gini(Humidity=High) = 1 – (3/7)2 – (4/7)2 = 1 – 0.183 – 0.326 = 0.489

Gini(Humidity=Normal) = 1 – (6/7)2 – (1/7)2 = 1 – 0.734 – 0.02 = 0.244

溼度的加權平均Gini Index 如下：

Gini(Humidity) = (7/14) x 0.489 + (7/14) x 0.244 = 0.367

Wind

風度特徵，有兩個Weak、Strong.

Gini(Wind=Weak) = 1 – (6/8)2 – (2/8)2 = 1 – 0.5625 – 0.062 = 0.375

Gini(Wind=Strong) = 1 – (3/6)2 – (3/6)2 = 1 – 0.25 – 0.25 = 0.5

Gini(Wind) = (8/14) x 0.375 + (6/14) x 0.5 = 0.428

Time To Decide

在我們計算了每個特徵的Gini Index之後，我們將選擇Gini Index最低的選項：

如果將其轉化為樹狀的話，那麼將如下圖：

從上面案例中可以看到 outlook的Overcast子項中，都選擇的Yes.

之後

同樣的，如果我們使用同樣的原則，對於Sunny之後的節點進行選擇時，我們對於數據樣本1、2、8、9、11 進行同樣過程的Gini Index計算。計算過程這裡就省略了，從而選擇humidity作為下一節點。 同樣，大家看下圖的時候會發現，通過Humidity節點的分裂，Humidity High的時候，選擇是No；Humidity Low的時候，選擇是Yes.

最終的最終，在我們完整計算過所有節點之後，完整的決策樹如下圖。

總結

首先，就這個例子而言，我們是面對14個Sample，每個sample有4個特徵和其對應的最終分類；

而，我們希望決策樹能做到的是，從這14個樣本中學到一些東西，從而對於新的數據Sample能有指導作用，比如當我們拿到一組新的特徵時，我們能判斷Yes or No；

就，決策樹而言，如其名，就是將每個特徵作為一個節點。將每個節點作為一個“分流”的判斷點；

而，最重要的問題就是每個節點，我們選擇哪個特徵？wind還是outlook呢？ 原則上，我們的選擇是分裂後，使得子節點的純度更高的分裂方式；

而，CART決策樹，計算“純度”的方法就是使用Gini Index

整體來看，CART決策樹的邏輯其實非常清晰。其使用Gini Index也能保證最少的分裂 和 最少的Tree深度。