分類回歸樹 CART 是決策樹家族中的基礎算法，它非常直覺（intuitive），但看網(wǎng)上的文章，很少能把它講的通俗易懂（也許是我理解能力不夠），幸運的是，我在 Youtube 上看到了這個視頻，可以讓你在沒有任何機器學習基礎的情況下掌握 CART 的原理，下面我嘗試著把它寫出來，以加深印象.
決策樹的結(jié)構
下圖是一個簡單的決策樹示例：
假設上面這個決策樹是一個用來判斷病人是否患有心臟病的系統(tǒng)，當病人前來就醫(yī)時，系統(tǒng)首先會問他：血液循環(huán)是否正常？此時如果病人回答是，系統(tǒng)會走左邊的分支，并繼續(xù)問：血管是否不堵塞？如果此時病人回答是，系統(tǒng)便會判斷該病人沒有患心臟病，反之則會判斷他患有心臟病。同理，如果病人的第一個問題的回答是否，則決策樹會走到右邊的分支，接下來會繼續(xù)后面的提問，直到來到樹的根部，以輸出結(jié)果。
可見，決策樹是一個二叉樹結(jié)構的模型，它可以被用來解決分類問題或回歸問題，該樹的非葉子節(jié)點本質(zhì)上是一些條件表達式，用來決定樹根到葉子的路徑，而葉子節(jié)點便是該模型的預測結(jié)果。
本文主要介紹如何構建一棵分類樹：
如何構建一棵分類樹
在構造這棵“判斷心臟病的決策樹”之前，我們有一堆病人的診斷數(shù)據(jù)，如下
| 胸口疼痛 | 血液循環(huán)正常 | 血管堵塞 | 患有心臟病 |
|---|---|---|---|
| 否 | 否 | 否 | 否 |
| 是 | 是 | 是 | 是 |
| 是 | 是 | 否 | 否 |
| ... | ... | ... | ... |
剛開始，我們可以使用「胸口疼痛」或者「血液循環(huán)正?！够蛘摺秆芏氯惯@三個特征中的一個來作為樹根，但這樣做會存在一個問題：任何上述特征都無法將是否患有心臟病分類得完全正確，如下：
既然沒有絕對最優(yōu)的答案，我們一般會選擇一個相對最優(yōu)的答案，即在這 3 個特征中選擇一個相對最好的特征作為樹根，如何衡量它們的分類好壞呢？我們可以使用不純度（impurity）這個指標來度量，例如下圖中，P1（藍色概率分布）相對于 P2（橙色概率分布） 來說就是不純的。對于一個節(jié)點的分類結(jié)果來說（上圖黃色節(jié)點），當然希望它的分布越純越好。
計算一個分布的不純度有很多方法，這里使用的是基尼不純度（Gini Impurity）——該值越高，越不純，反之越純。計算基尼不純度的公式很簡單：
這里 表示離散概率分布中的概率值，我們來算一下上圖中 P1 和 P2 的基尼不純度
可見 P1 的基尼不純度更高。
有了以上基礎，接下來我們就可以依次計算不同特征分類的基尼不純度，從中選一個值最低的特征來作為樹根，以「胸口疼痛」特征為例，其左邊和右邊的分類結(jié)果的基尼不純度為：
那么，「胸口疼痛」這個節(jié)點整體的不純度則為左右兩個不純度的加權平均，如下：
同理，我們也可以計算出「血液循環(huán)正?！购汀秆芏氯沟幕岵患兌确謩e為 0.360 和 0.381。相比之下，「血液循環(huán)正?！沟闹底钚?，該特征便是我們的樹根。
在選出了樹根后，原來的一份數(shù)據(jù)被樹根分成了兩份，后續(xù)要做的事情相信很多同學已經(jīng)猜到了：對于新產(chǎn)生的兩份數(shù)據(jù)，每份數(shù)據(jù)再使用同樣的方法，使用剩下的特征來產(chǎn)生非葉子節(jié)點，如此遞歸下去，直到滿足下面兩個條件中的任意一條：
- 每條路徑上所有特征都使用過
- 使用新特征沒有使分類結(jié)果更好（此時不產(chǎn)生新的節(jié)點）
上述第 1 個條件很容易理解，我們一起來看下第 2 個條件，假設在建樹的過程中，其中一條路徑如下：
現(xiàn)在我們需要決定黃色的這部分數(shù)據(jù)是否還需要被「胸口疼痛」這個特征分類，假設用「胸口疼痛」來分類該數(shù)據(jù)的結(jié)果如下：
接下來我們就要對分類前后做效果對比，依然計算它們的基尼不純度，在分類前，基尼不純度為：
而使用「胸口疼痛」分類之后，基尼不純度為（省去計算細節(jié)）：
顯然繼續(xù)分類只會使結(jié)果更糟，所以該分支的建立提前結(jié)束了，且分支上只有「血液循環(huán)正?！购汀秆芏氯惯@兩個特征來進行分類。
值得一提的是，在建樹過程中，即便候選節(jié)點的基尼不純度更低，但如果該指標的降低不能超過一定的閾值，也不建議繼續(xù)加節(jié)點，這種做法可以在一定程度上緩解過擬合的問題。例如：假設該閾值設定為0.05，即便 G(胸口疼痛) 為 0.16，也不繼續(xù)將「胸口疼痛」作為該分支上的一個節(jié)點用來分類，因為此時基尼不純度只降低了 0.04，低于閾值 0.05。
如何處理離散型數(shù)據(jù)
上面例子中的數(shù)據(jù)是只有 0 或者 1 的布爾類型的數(shù)據(jù)，如果遇到其他類型的數(shù)據(jù)該怎么處理呢？先來看一下離散型數(shù)據(jù)，這種類型的數(shù)據(jù)需要考慮 2 種情況：
- 有順序的離散型數(shù)據(jù)，例如電商網(wǎng)站把商品的評論分為：好評、中評和差評
- 順序無關的離散型數(shù)據(jù)，例如商品可能的顏色有：紅色、黃色和藍色
有順序的離散型數(shù)據(jù)
假如我們有以下數(shù)據(jù)，它根據(jù)用戶對商品的評價來判斷用戶是否喜歡該商品，其中，對商品的評價被編碼為 1（差評）、2（中評） 和 3（好評）：
| 商品評價 | 是否喜歡 |
|---|---|
| 1 | 0 |
| 3 | 1 |
| 2 | 1 |
| 2 | 0 |
| 3 | 1 |
| 1 | 1 |
| 3 | 0 |
以上問題實際上等價于選擇一個評價值，它能夠更好的把人們的喜好分開，這個值可以是 1 或者 2，即當商品評價“小于等于1”或者“小于等于2”時，判斷用戶不喜歡它，否則為喜歡它，這里沒有“小于等于3”這個選項，因為該選項會包含所有的數(shù)據(jù)，沒有分類價值；于是，根據(jù)上述兩個選項，我們可以對數(shù)據(jù)做如下 2 種分類：
接下來分別計算它們的基尼不純度，其中左邊的結(jié)果 G(1) = 0.486，而右邊 G(2) = 0.476；于是，當使用「商品評價」這個特征來做分類時，該特征的切分點（cutoff）為“小于等于2”。
順序無關的離散型數(shù)據(jù)
我們再來看一個根據(jù)商品的顏色來判斷用戶是否喜歡該商品的例子，有如下數(shù)據(jù)：
| 商品顏色 | 是否喜歡 |
|---|---|
| RED | 1 |
| YELLOW | 1 |
| BLUE | 0 |
| YELLOW | 1 |
| BLUE | 1 |
| RED | 0 |
對于以上數(shù)據(jù)，其作為節(jié)點的判斷條件有以下 6 種可能：
- 紅色表示喜歡
- 黃色表示喜歡
- 藍色表示喜歡
- 紅色或黃色表示喜歡
- 紅色或藍色表示喜歡
- 黃色或藍色表示喜歡
類似的，我們對每一種可能的分類結(jié)果計算其基尼不純度，然后再選擇最低的那個值對應的條件。
如何處理連續(xù)型數(shù)據(jù)
最后我們再來看看特征是連續(xù)型數(shù)據(jù)的情況，例如我們通過人的身高來判斷是否患有心臟病，數(shù)據(jù)如下：
| 身高 | 患有心臟病 |
|---|---|
| 220 | 1 |
| 180 | 1 |
| 225 | 1 |
| 155 | 0 |
| 190 | 0 |
處理這類數(shù)據(jù)的思路和上面幾種做法一致，也就是尋找一個使基尼不純度最低的 cutoff。具體步驟是，先對身高進行排序，然后求相鄰兩個數(shù)據(jù)之間的平均值，以每個平均值作為分界點，對目標數(shù)據(jù)進行分類，并計算它們的基尼不純度，如下：
| 身高 | 相鄰平均值 | 基尼不純度 |
|---|---|---|
| 225 | ||
| 222.5 | 0.4 | |
| 220 | ||
| 205 | 0.27 | |
| 190 | ||
| 185 | 0.47 | |
| 180 | ||
| 167.5 | 0.3 | |
| 155 |
所以，在使用「身高」來建樹時，其切分點為 205，即”小于205”被判斷為未患心臟病，而”不小于205“的會被診斷為患病。
總結(jié)
本文主要介紹了 CART 中的分類樹的構建算法原理，及遇到了不同類型的數(shù)據(jù)時，該算法會如何處理，當然這并不是分類樹的全部，因為決策樹容易導致過擬合的原因，在建樹之后，往往會伴隨著”剪枝“的操作，這些內(nèi)容以及回歸樹部分會放在后面再做介紹。
關注作者：
