分類回歸樹 CART 是決策樹家族中的基礎(chǔ)算法，它非常直覺（intuitive），但看網(wǎng)上的文章，很少能把它講的通俗易懂（也許是我理解能力不夠），幸運(yùn)的是，我在 Youtube 上看到了這個(gè)視頻，可以讓你在沒有任何機(jī)器學(xué)習(xí)基礎(chǔ)的情況下掌握 CART 的原理，下面我嘗試著把它寫出來，以加深印象.

決策樹的結(jié)構(gòu)

下圖是一個(gè)簡單的決策樹示例：

假設(shè)上面這個(gè)決策樹是一個(gè)用來判斷病人是否患有心臟病的系統(tǒng)，當(dāng)病人前來就醫(yī)時(shí)，系統(tǒng)首先會(huì)問他：血液循環(huán)是否正常？此時(shí)如果病人回答是，系統(tǒng)會(huì)走左邊的分支，并繼續(xù)問：血管是否不堵塞？如果此時(shí)病人回答是，系統(tǒng)便會(huì)判斷該病人沒有患心臟病，反之則會(huì)判斷他患有心臟病。同理，如果病人的第一個(gè)問題的回答是否，則決策樹會(huì)走到右邊的分支，接下來會(huì)繼續(xù)后面的提問，直到來到樹的根部，以輸出結(jié)果。

可見，決策樹是一個(gè)二叉樹結(jié)構(gòu)的模型，它可以被用來解決分類問題或回歸問題，該樹的非葉子節(jié)點(diǎn)本質(zhì)上是一些條件表達(dá)式，用來決定樹根到葉子的路徑，而葉子節(jié)點(diǎn)便是該模型的預(yù)測結(jié)果。

本文主要介紹如何構(gòu)建一棵分類樹：

如何構(gòu)建一棵分類樹

在構(gòu)造這棵“判斷心臟病的決策樹”之前，我們有一堆病人的診斷數(shù)據(jù)，如下

剛開始，我們可以使用「胸口疼痛」或者「血液循環(huán)正?！够蛘摺秆芏氯惯@三個(gè)特征中的一個(gè)來作為樹根，但這樣做會(huì)存在一個(gè)問題：任何上述特征都無法將是否患有心臟病分類得完全正確，如下：

既然沒有絕對(duì)最優(yōu)的答案，我們一般會(huì)選擇一個(gè)相對(duì)最優(yōu)的答案，即在這 3 個(gè)特征中選擇一個(gè)相對(duì)最好的特征作為樹根，如何衡量它們的分類好壞呢？我們可以使用不純度（impurity）這個(gè)指標(biāo)來度量，例如下圖中，P1（藍(lán)色概率分布）相對(duì)于 P2（橙色概率分布） 來說就是不純的。對(duì)于一個(gè)節(jié)點(diǎn)的分類結(jié)果來說（上圖黃色節(jié)點(diǎn)），當(dāng)然希望它的分布越純越好。

計(jì)算一個(gè)分布的不純度有很多方法，這里使用的是基尼不純度（Gini Impurity）——該值越高，越不純，反之越純。計(jì)算基尼不純度的公式很簡單：

這里 表示離散概率分布中的概率值，我們來算一下上圖中 P1 和 P2 的基尼不純度

可見 P1 的基尼不純度更高。

有了以上基礎(chǔ)，接下來我們就可以依次計(jì)算不同特征分類的基尼不純度，從中選一個(gè)值最低的特征來作為樹根，以「胸口疼痛」特征為例，其左邊和右邊的分類結(jié)果的基尼不純度為：

那么，「胸口疼痛」這個(gè)節(jié)點(diǎn)整體的不純度則為左右兩個(gè)不純度的加權(quán)平均，如下：

同理，我們也可以計(jì)算出「血液循環(huán)正?！购汀秆芏氯沟幕岵患兌确謩e為 0.360 和 0.381。相比之下，「血液循環(huán)正?！沟闹底钚?，該特征便是我們的樹根。

在選出了樹根后，原來的一份數(shù)據(jù)被樹根分成了兩份，后續(xù)要做的事情相信很多同學(xué)已經(jīng)猜到了：對(duì)于新產(chǎn)生的兩份數(shù)據(jù)，每份數(shù)據(jù)再使用同樣的方法，使用剩下的特征來產(chǎn)生非葉子節(jié)點(diǎn)，如此遞歸下去，直到滿足下面兩個(gè)條件中的任意一條：

1. 每條路徑上所有特征都使用過
2. 使用新特征沒有使分類結(jié)果更好（此時(shí)不產(chǎn)生新的節(jié)點(diǎn)）

上述第 1 個(gè)條件很容易理解，我們一起來看下第 2 個(gè)條件，假設(shè)在建樹的過程中，其中一條路徑如下：

現(xiàn)在我們需要決定黃色的這部分?jǐn)?shù)據(jù)是否還需要被「胸口疼痛」這個(gè)特征分類，假設(shè)用「胸口疼痛」來分類該數(shù)據(jù)的結(jié)果如下：

接下來我們就要對(duì)分類前后做效果對(duì)比，依然計(jì)算它們的基尼不純度，在分類前，基尼不純度為：

而使用「胸口疼痛」分類之后，基尼不純度為（省去計(jì)算細(xì)節(jié)）：

顯然繼續(xù)分類只會(huì)使結(jié)果更糟，所以該分支的建立提前結(jié)束了，且分支上只有「血液循環(huán)正?！购汀秆芏氯惯@兩個(gè)特征來進(jìn)行分類。

值得一提的是，在建樹過程中，即便候選節(jié)點(diǎn)的基尼不純度更低，但如果該指標(biāo)的降低不能超過一定的閾值，也不建議繼續(xù)加節(jié)點(diǎn)，這種做法可以在一定程度上緩解過擬合的問題。例如：假設(shè)該閾值設(shè)定為0.05，即便 G(胸口疼痛) 為 0.16，也不繼續(xù)將「胸口疼痛」作為該分支上的一個(gè)節(jié)點(diǎn)用來分類，因?yàn)榇藭r(shí)基尼不純度只降低了 0.04，低于閾值 0.05。

如何處理離散型數(shù)據(jù)

上面例子中的數(shù)據(jù)是只有 0 或者 1 的布爾類型的數(shù)據(jù)，如果遇到其他類型的數(shù)據(jù)該怎么處理呢？先來看一下離散型數(shù)據(jù)，這種類型的數(shù)據(jù)需要考慮 2 種情況：

1. 有順序的離散型數(shù)據(jù)，例如電商網(wǎng)站把商品的評(píng)論分為：好評(píng)、中評(píng)和差評(píng)
2. 順序無關(guān)的離散型數(shù)據(jù)，例如商品可能的顏色有：紅色、黃色和藍(lán)色

有順序的離散型數(shù)據(jù)

假如我們有以下數(shù)據(jù)，它根據(jù)用戶對(duì)商品的評(píng)價(jià)來判斷用戶是否喜歡該商品，其中，對(duì)商品的評(píng)價(jià)被編碼為 1（差評(píng)）、2（中評(píng)） 和 3（好評(píng)）：

以上問題實(shí)際上等價(jià)于選擇一個(gè)評(píng)價(jià)值，它能夠更好的把人們的喜好分開，這個(gè)值可以是 1 或者 2，即當(dāng)商品評(píng)價(jià)“小于等于1”或者“小于等于2”時(shí)，判斷用戶不喜歡它，否則為喜歡它，這里沒有“小于等于3”這個(gè)選項(xiàng)，因?yàn)樵撨x項(xiàng)會(huì)包含所有的數(shù)據(jù)，沒有分類價(jià)值；于是，根據(jù)上述兩個(gè)選項(xiàng)，我們可以對(duì)數(shù)據(jù)做如下 2 種分類：

接下來分別計(jì)算它們的基尼不純度，其中左邊的結(jié)果 G(1) = 0.486，而右邊 G(2) = 0.476；于是，當(dāng)使用「商品評(píng)價(jià)」這個(gè)特征來做分類時(shí)，該特征的切分點(diǎn)（cutoff）為“小于等于2”。

順序無關(guān)的離散型數(shù)據(jù)

我們再來看一個(gè)根據(jù)商品的顏色來判斷用戶是否喜歡該商品的例子，有如下數(shù)據(jù)：

對(duì)于以上數(shù)據(jù)，其作為節(jié)點(diǎn)的判斷條件有以下 6 種可能：

1. 紅色表示喜歡
2. 黃色表示喜歡
3. 藍(lán)色表示喜歡
4. 紅色或黃色表示喜歡
5. 紅色或藍(lán)色表示喜歡
6. 黃色或藍(lán)色表示喜歡

類似的，我們對(duì)每一種可能的分類結(jié)果計(jì)算其基尼不純度，然后再選擇最低的那個(gè)值對(duì)應(yīng)的條件。

如何處理連續(xù)型數(shù)據(jù)

最后我們再來看看特征是連續(xù)型數(shù)據(jù)的情況，例如我們通過人的身高來判斷是否患有心臟病，數(shù)據(jù)如下：

處理這類數(shù)據(jù)的思路和上面幾種做法一致，也就是尋找一個(gè)使基尼不純度最低的 cutoff。具體步驟是，先對(duì)身高進(jìn)行排序，然后求相鄰兩個(gè)數(shù)據(jù)之間的平均值，以每個(gè)平均值作為分界點(diǎn)，對(duì)目標(biāo)數(shù)據(jù)進(jìn)行分類，并計(jì)算它們的基尼不純度，如下：

所以，在使用「身高」來建樹時(shí)，其切分點(diǎn)為 205，即”小于205”被判斷為未患心臟病，而”不小于205“的會(huì)被診斷為患病。

總結(jié)

本文主要介紹了 CART 中的分類樹的構(gòu)建算法原理，及遇到了不同類型的數(shù)據(jù)時(shí)，該算法會(huì)如何處理，當(dāng)然這并不是分類樹的全部，因?yàn)闆Q策樹容易導(dǎo)致過擬合的原因，在建樹之后，往往會(huì)伴隨著”剪枝“的操作，這些內(nèi)容以及回歸樹部分會(huì)放在后面再做介紹。

參考：StatQuest: Decision Trees

關(guān)注作者：