九、決策樹

9.1 決策樹原理

9.1.1 決策樹概述

決策樹(Decision Tree)是在已知各種情況發(fā)生概率的基礎上，通過構成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率，評價項目風險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。決策樹是一個非常常見并且優(yōu)秀的機器學習算法，它易于理解、可解釋性強，其可作為分類算法，也可用于回歸模型。

決策樹將算法組織成一顆樹的形式。其實這就是將平時所說的if-then語句構建成了樹的形式。這個決策樹主要包括三個部分：內(nèi)部節(jié)點、葉節(jié)點和邊。內(nèi)部節(jié)點是劃分的屬性，邊代表劃分的條件，葉節(jié)點表示類別。構建決策樹就是一個遞歸地選擇內(nèi)部節(jié)點，計算劃分條件的邊，最后到達葉子節(jié)點的過程。

決策樹算法有以下7個特點：

(1) 決策樹是從訓練數(shù)據(jù)中學習得出一個樹狀結構的模型，通過做出一系列決策(選擇)來對數(shù)據(jù)進行劃分，這類似于針對一系列問題進行選擇。

(2) 決策樹屬于判別模型。

(3) 決策樹的決策過程就是從根節(jié)點開始，測試待分類項中對應的特征屬性，并按照其值選擇輸出分支，直到葉子節(jié)點，將葉子節(jié)點的存放的類別作為決策結果。

(4) 決策樹算法是一種歸納分類算法，它通過對訓練集的學習，挖掘出有用的規(guī)則，用于對新數(shù)據(jù)進行預測。

(5) 決策樹算法屬于監(jiān)督學習方法。

(6) 決策樹歸納的基本算法是貪心算法，自頂向下來構建決策樹。(貪心算法：在每一步選擇中都采取在當前狀態(tài)下最好優(yōu)的選擇。)

(7) 在決策樹的生成過程中，分割方法即屬性選擇的度量是關鍵。

9.1.2 決策樹算法思想

決策樹的算法思想如下：

輸入：訓練數(shù)據(jù)集，特征集，閾值。

其中：數(shù)據(jù)集，特征，是數(shù)據(jù)集的熵，是中特征取第個值的樣本子集，是數(shù)據(jù)集的熵，是數(shù)據(jù)集對特征的條件熵，是中屬于第類的樣本子集。是特征取值的個數(shù)，是類的個數(shù)。

輸出：決策樹。

(1) 如果中所有實例屬于同一類，則置為單結點樹，并將作為該結點的類，返回。

(2) 如果，則置為單結點樹，并將中最多的類作為該節(jié)點的類，返回。

否則，根據(jù)相應公式計算中各個特征對的信息增益、信息增益率和基尼指數(shù)，選擇最合適的特征。

(3) 如果的得分小于，則置為單結點樹，并將作為該結點的類，返回。

否則，根據(jù)特征取值，對數(shù)據(jù)進行劃分，繼續(xù)遞歸構造決策樹，返回。

建立決策樹的關鍵，即在當前狀態(tài)下選擇哪個屬性作為分類依據(jù)。

根據(jù)不同的目標函數(shù)，建立決策樹主要有一下三種算法：ID3(Iterative Dichotomiser)、C4.5、CART(Classification And Regression Tree)。

9.2 ID3算法

9.2.1 ID3算法概述

ID3(Iterative Dichotomiser)算法最早是由羅斯昆(J. Ross Quinlan)于1975年提出的一種決策樹構建算法，算法的核心是“信息熵”，期望信息越小，信息熵越大，從而樣本純度越低。ID3 算法是以信息論為基礎，以信息增益為衡量標準，從而實現(xiàn)對數(shù)據(jù)的歸納分類。

算法是參考了奧卡姆剃刀(用較少的東西，同樣可以做好事情)的原則：越是小型的決策樹越優(yōu)于大的決策樹。

ID3 算法的核心思想就是以信息增益來度量特征選擇，選擇信息增益最大的特征進行分裂。算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間(C4.5 也是貪婪搜索)。

其大致步驟為：

(1) 初始化特征集合和數(shù)據(jù)集合。

(2) 計算數(shù)據(jù)集合信息熵和所有特征的條件熵，選擇信息增益最大的特征作為當前決策節(jié)點。

(3) 更新數(shù)據(jù)集合和特征集合(刪除上一步使用的特征，并按照特征值來劃分不同分支的數(shù)據(jù)集合)。

(4) 重復 2，3 兩步，若子集值包含單一特征，則為分支葉子節(jié)點。

9.2.2 ID3劃分標準

ID3 使用的分類標準是信息增益，它表示得知特征的信息而使得樣本集合不確定性減少的程度。

信息增益越大表示使用特征來劃分所獲得的“純度提升越大”。對信息增益率進行計算，會使用到信息熵、條件熵和信息增益等概念。

1. 信息熵

信息熵是信息論中用于度量信息量的一個概念。一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越是混亂，隨機變量的不確定性就越大信息熵就越高。所以，信息熵也可以說是系統(tǒng)有序化程度的一個度量。信息熵的公式如下：

表9-1訓練數(shù)據(jù)

序號	年齡	有工作	有自己的房子	信貸情況	類別
0	青年	否	否	一般	否
1	青年	否	否	好	否
2	青年	是	否	好	是
3	青年	是	是	一般	是
4	青年	否	否	一般	否
5	中年	否	否	一般	否
6	中年	否	否	好	否
7	中年	是	是	好	是
8	中年	否	是	非常好	是
9	中年	否	是	非常好	是
10	老年	否	是	非常好	是
11	老年	否	是	好	是
12	老年	是	否	好	是
13	老年	是	否	非常好	是
14	老年	否	否	一般	否

以表9-1的數(shù)據(jù)為例，特征為：：“年齡”、：“有工作”、：“有自己的房子”、：“信貸情況”；標簽為“類別”，這里只有“是、否”兩類，因此代表類別，本訓練數(shù)據(jù)總共有15個樣本，因此，類別1有9個樣本(類別為“是”)，類別2有6個樣本(類別為“否”)，根據(jù)信息熵的公式，得到：

1. 條件熵

針對某個特征，對于數(shù)據(jù)集的條件熵為：

是特征，是特征取值。

表9-1的訓練數(shù)據(jù)按年齡特征劃分：可以得到表9-2的結果:

表9-2按年齡劃分的統(tǒng)計信息

年齡	數(shù)量	是	否
青年	5	2	3
中年	5	3	2
老年	5	4	1

根據(jù)表9-2計算得到的條件熵：

青年

中年

老年

年齡

1. 信息增益

信息增益表示得知特征的信息條件下，信息不確定性減少的程度。

信息增益 = 信息熵 - 條件熵：

老年老年

同理可以求出其它特征的信息增益，選擇信息增益最大的特征進行分裂。

9.2.3 ID3算法總結

ID3 算法的核心思想就是以信息增益來度量特征選擇，選擇信息增益最大的特征進行分裂。ID3算法有以下缺點：

(1) ID3 沒有剪枝策略，容易過擬合。

(2) 信息增益準則對可取值數(shù)目較多的特征有所偏好，類似“編號”的特征其信息增益接近于1。

(3) 只能用于處理離散分布的特征。

(4) 沒有考慮缺失值。

9.3 C4.5算法

9.3.1 C4.5算法概述

C4.5 算法是對 ID3 算法的改進，主要改進點如下：

(1) ID3選擇屬性用的是子樹的信息增益， C4.5 算法最大的特點是克服了 ID3 對特征數(shù)目的偏重這一缺點，引入信息增益率來作為分類標準。

(2) 在決策樹構造過程中進行剪枝，引入悲觀剪枝策略進行后剪枝。

(3) 對非離散數(shù)據(jù)也能處理。

(4) 能夠對不完整數(shù)據(jù)進行處理。通過將連續(xù)特征離散化，假設個樣本的連續(xù)特征有個取值，C4.5 將其排序并取相鄰兩樣本值的平均數(shù)，個取值總共個劃分點，分別計算以該劃分點作為二元分類點時的信息增益，并選擇信息增益最大的點作為該連續(xù)特征的二元離散分類點。

對于缺失值的處理可以分為兩個子問題：

(1) 在特征值缺失的情況下進行劃分特征的選擇？即，如何計算特征的信息增益率？C4.5 的做法是：對于具有缺失值特征，用沒有缺失的樣本子集所占比重來折算。

(2) 選定該劃分特征，對于缺失該特征值的樣本如何處理？即，到底把這個樣本劃分到哪個結點里？C4.5 的做法是：將樣本同時劃分到所有子節(jié)點，不過要調(diào)整樣本的權重值，其實也就是以不同概率劃分到不同節(jié)點中。

9.3.2 C4.5劃分標準

C4.5用的是信息增益率作為劃分標準，利用信息增益率可以克服信息增益的缺點，其公式為：

稱為特征的固有值，是特征的取值個數(shù)。

繼續(xù)使用表9-1的訓練數(shù)據(jù)，綜合利用信息熵和信息增益的公式，計算可得：

老年老年

則：

老年老年

這里需要注意，信息增益率對可取值較少的特征有所偏好(分母越小，整體越大)，因此 C4.5 并不是直接用增益率最大的特征進行劃分，而是使用一個啟發(fā)式方法：先從候選劃分特征中找到信息增益高于平均值的特征，再從中選擇增益率最高的。

9.3.3 C4.5剪枝處理

剪枝(Pruning)是決策樹學習算法應對過擬合的主要手段。

在決策樹學習中，為了盡可能正確分類訓練樣本，節(jié)點劃分過程將不斷地重復，有時候會造成決策樹的分支過多，這時就可能因訓練樣本學的太好了，以至于把訓練樣本自身的一些特點當作所有數(shù)據(jù)都具有的一般性質而導致過擬合。因此，需要主動去掉一些分支來降低過擬合的風險。

1. 剪枝策略

決策樹剪枝的基本策略有預剪枝(Pre-Pruning)和后剪枝(Post-Pruning)：

(1) 預剪枝是指在決策樹生成的過程中，對每個節(jié)點在劃分前先進行估計，若當前節(jié)點的劃分不能帶來決策樹泛化能力的提升，則停止劃分并將當前節(jié)點標記為葉節(jié)點。預剪枝不僅可以降低過擬合的風險而且還可以減少訓練時間，但另一方面它是基于“貪心”策略，會帶來欠擬合風險。

(2) 后剪枝則是先從訓練集生成一棵完整的決策樹，然后自底向上地對非葉節(jié)點進行考察，若將該節(jié)點對應的子樹替換為葉節(jié)點能帶來決策樹泛化性能的提升，則將該子樹替換為葉節(jié)點。

1. 剪枝案例

對于判斷性能是否得到了提升，我們可以將數(shù)據(jù)集劃分成兩部分，一部分用于訓練，另一部分用于驗證，對性能進行評估。如我們對上面的西瓜數(shù)據(jù)集隨機分成兩部分，表9-3 是訓練集，表9-4 是驗證集：

表9-3 西瓜數(shù)據(jù)訓練集

編號	色澤	根蒂	敲聲	紋理	臍部	觸感	好瓜
1	青綠	蜷縮	濁響	清晰	凹陷	硬滑	是
2	烏黑	蜷縮	沉悶	清晰	凹陷	硬滑	是
3	烏黑	蜷縮	濁響	清晰	凹陷	硬滑	是
6	青綠	稍蜷	濁響	清晰	稍凹	軟粘	是
7	烏黑	稍蜷	濁響	稍糊	稍凹	軟粘	是
10	青綠	硬挺	清脆	清晰	平坦	軟粘	否
14	淺白	稍蜷	沉悶	稍糊	凹陷	硬滑	否
15	烏黑	稍蜷	濁響	清晰	稍凹	軟粘	否
16	淺白	蜷縮	濁響	模糊	平坦	硬滑	否
17	青綠	蜷縮	沉悶	稍糊	稍凹	硬滑	否

表9-4西瓜數(shù)據(jù)驗證集

編號	色澤	根蒂	敲聲	紋理	臍部	觸感	好瓜
4	青綠	蜷縮	沉悶	清晰	凹陷	硬滑	是
5	淺白	蜷縮	濁響	清晰	凹陷	硬滑	是
8	烏黑	稍蜷	濁響	清晰	稍凹	硬滑	是
9	烏黑	稍蜷	沉悶	稍糊	稍凹	硬滑	否
11	淺白	硬挺	清脆	模糊	平坦	硬滑	否
12	淺白	蜷縮	濁響	模糊	平坦	軟粘	否
13	青綠	稍蜷	濁響	稍糊	凹陷	硬滑	否

1. 預剪枝

預剪枝在節(jié)點劃分前來確定是否繼續(xù)增長，及早停止增長的主要方法有：

(1) 節(jié)點內(nèi)數(shù)據(jù)樣本低于某一閾值；

(2) 所有節(jié)點特征都已分裂；

(3) 節(jié)點劃分前準確率比劃分后準確率高。

假設我們按照信息增益的原則來進行屬性的劃分，可以得到如下的決策樹：

圖9-2 基于表生成未剪枝的決策樹

首先，基于信息增益我們會選擇“臍部”進行劃分，產(chǎn)生 3 個分支，如上圖的①。是否進行這個劃分呢，這時候就需要對劃分前后的性能進行評估。

在劃分前所有的樣本集中在根節(jié)點。若不進行劃分，根據(jù)算法該節(jié)點被標記為葉節(jié)點，類別標記為訓練樣本數(shù)最多的類別(最多的樣本的類不唯一時，可以任選其中一類)。假設我們將這個葉節(jié)點標記為好瓜(上表訓練集中的正例與負例一樣多，選擇其中好瓜作為標簽)，用上表中的測試集對這個單點決策樹進行評估，那么編號{4,5,8}的樣本被正確分類，另外四個樣本被錯誤分類，于是驗證集的精度為$。

在使用屬性“臍部”劃分之后，上圖的②③④三個節(jié)點被標記為“好瓜”、“好瓜”、“壞瓜”。此時驗證集中編號為{4,5,8,11,12}的樣本被正確的分類，驗證集的精度為。因此，可以選擇用“臍部”對瓜進行有效的劃分。

然后決策算法要對節(jié)點②進行劃分，基于信息增益的原則選出屬性“色澤”進行劃分，可以看到青綠和烏黑的樣本被劃分為正例，淺白的樣本被劃分為負例。然而使用色澤進行劃分之后，驗證集中編號為{4,8,11,12}的樣本被正確分類，可以看到與上面的相比，驗證集編號為{5}的樣本的分類結果由正確變成了錯誤，使得樣本集的精度下降為57.1% 。因此，預剪枝策略禁止在②節(jié)點處劃分。

對節(jié)點③我們使用“根蒂”進行劃分，劃分后驗證集的精度不改變，沒有能提升驗證集的精度，因此，根據(jù)預剪枝的策略，禁止在③幾點處進行劃分。

對于節(jié)點④，所有的訓練樣本已經(jīng)屬于同一類別，因此不需要進行劃分。

因此最終生成的決策樹就是上圖，驗證集的精度為 71.4% 。這是一棵僅有一層的決策樹，亦成為決策樹樁(Decision Dtump)。

預剪枝的優(yōu)點：對比剪枝前與剪枝后可以發(fā)現(xiàn)，預剪枝是的決策樹的很多分支都沒有“展開”，這不僅降低了過擬合的風險，還顯著的降低了訓練的時間開銷和測試時間開銷。

缺點：有些分支的當前劃分雖然不能提升泛化性能、甚至是導致泛化性能的下降，但在其基礎上進行后續(xù)的劃分卻有可能導致性能顯著提高；預剪枝是基于貪心本質禁止這些分支展開，給預剪枝決策樹帶來了欠擬合的風險。

1. 后剪枝

后剪枝在已經(jīng)生成的決策樹上進行剪枝，從而得到簡化版的剪枝決策樹。

C4.5 采用的悲觀剪枝方法，用遞歸的方式從低往上針對每一個非葉子節(jié)點，評估用一個最佳葉子節(jié)點去代替這課子樹是否有益。如果剪枝后與剪枝前相比其錯誤率是保持或者下降，則這棵子樹就可以被替換掉。C4.5 通過訓練數(shù)據(jù)集上的錯誤分類數(shù)量來估算未知樣本上的錯誤率。

后剪枝決策樹的欠擬合風險很小，泛化性能往往優(yōu)于預剪枝決策樹。但同時其訓練時間會大的多。

后剪枝先從訓練一棵完整的決策樹，如上圖的未剪枝的決策樹，可以知道此時的驗證集精度為 42.9%。

后剪枝策略首先考察上圖的⑥節(jié)點。將其領銜的分支剪除，相當于把節(jié)點⑥標記為葉節(jié)點。替換后的葉節(jié)點包含編號為{7,15}的訓練樣本，于是該節(jié)點被標記為“好瓜”，此時決策樹驗證集的精度提升到了57.1%，于是節(jié)點⑥進行后剪枝。如下圖所示：

然后考察節(jié)點⑤，將其領銜的子樹替換為葉節(jié)點，替換后的節(jié)點包含{6,7,15}的訓練樣例，葉節(jié)點類別標記為好瓜，此時驗證集的精度為57.1%，因此不進行剪枝。

對節(jié)點②，將其領銜的子樹替換為葉節(jié)點，則替換后的葉節(jié)點包含編號為{1,2,3,14}的訓練樣本，葉節(jié)點被標記為“好瓜”。此時驗證集的精度為71.4%，因此，記性剪枝的操作。

對于節(jié)點③和①，若將其領銜的子樹替換為葉節(jié)點，獲得驗證集精度分別為71.4%和42.9%，均沒有提高，因此不進行剪枝。

最終得到的結果就是上圖，驗證集的精度為 71.4%。

對比預剪枝和后剪枝可以看出，后剪枝決策樹通常比預剪枝決策樹保留了更多的分支。

1. 剪枝總結

一般情況下，后剪枝的欠擬合風險更小，泛化性能往往優(yōu)于預剪枝決策樹。但后剪枝決策過程是在生產(chǎn)完全決策樹之后進行的，并且要自底向上的對樹種的所有非葉子節(jié)點進行逐一考察，因此訓練時間開銷比未剪枝決策樹和預剪枝決策樹都要打很多。

9.3.4 C4.5算法總結

C4.5算法的核心思想就是以信息增益率來度量特征選擇，選擇信息增益率最大的特征進行分裂。C4.5算法有以下缺點：

(1) C4.5剪枝策略可以再優(yōu)化。

(2) C4.5用的是多叉樹，用二叉樹效率更高。

(3) C4.5 只能用于分類。

(4) C4.5 使用的熵模型擁有大量耗時的對數(shù)運算，連續(xù)值還有排序運算。

(5) C4.5 在構造樹的過程中，對數(shù)值屬性值需要按照其大小進行排序，從中選擇一個分割點，所以只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當訓練集大得無法在內(nèi)存容納時，程序無法運行。

9.4 CART算法

9.4.1 CART算法概述

CART(Classification and Regression Tree,分類回歸樹)，CART算法既可以用于創(chuàng)建分類樹(Classification Tree)，也可以用于創(chuàng)建回歸樹(Regression Tree)。回歸樹算法上與分類樹相似，在分類和回歸時，其算法流程大致相同，但是其特征劃分、輸出預測結果等步驟是不同的。

CART分類時候用基尼指數(shù)來選擇屬性，CART回歸時候用均方差來選擇屬性。

如果目標變量是離散的，稱為分類樹。

如果目標變量是連續(xù)的，稱為回歸樹。

CART算法是一種二分遞歸分割技術，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子結點都有兩個分支，因此CART算法生成的決策樹是結構簡潔的二叉樹。由于CART算法構成的是一個二叉樹，它在每一步的決策時只能是“是”或者“否”，即使一個特征有多個取值，也是把數(shù)據(jù)分為兩部分。

9.4.2 CART分類樹

CART分類樹輸出的是樣本的類別，屬性選擇的標準度量方法是基尼指數(shù)。

當基尼指數(shù)越小的時候，說明樣本之間的差異性小，不確定程度低?；嶂笖?shù)最小為根節(jié)點，逐節(jié)分裂。

ID3中使用了信息增益選擇特征，增益大優(yōu)先選擇。C4.5中，采用信息增益率選擇特征，減少因特征值多導致信息增益大的問題。CART分類樹算法使用基尼指數(shù)來代替信息增益率，基尼指數(shù)代表了模型的不純度，基尼指數(shù)越小，不純度越低，特征越好。這和信息增益(比)相反。

對于決策樹建立后做預測的方式，CART分類樹采用葉子節(jié)點里概率最大的類別作為當前節(jié)點的預測類別。

1. 基尼指數(shù)

基尼指數(shù)也稱為基尼系數(shù)，表示在樣本集合中一個隨機選中的樣本被分錯的概率。

假設一個數(shù)據(jù)集中有個類別，第個類別的概率為，則基尼指數(shù)的表達式為：

上面的公式中，表示第個類別出現(xiàn)的概率，那么顯然就是當前數(shù)據(jù)集中，除了第個類別以外的其他所有類別出現(xiàn)的概率，所以兩者相乘就是當前數(shù)據(jù)集中，第個類別和其他所有類別都出現(xiàn)的概率，這個概率越高，數(shù)據(jù)集越不純。

設代表特征集，樣本集合的基尼指數(shù)：假設集合中有個類別，每個類別的概率是，其中表示類別的樣本類別個數(shù)，表示樣本總數(shù)，第個類別的數(shù)量為，則樣本的基尼指數(shù)表達式為：

對于樣本,如果根據(jù)特征集的某個值，把分成、到部分，則在特征集的條件下，的基尼指數(shù)表達式為：

2.離散值劃分決策樹的例子

根據(jù)表9-1的數(shù)據(jù)，應用CART算法，使用基尼指數(shù)劃分，生成決策樹：

根據(jù)公式：

青年

中年

老年

由于青年和老年相等，都為，且最小，所以青年和老年都可以選a作的最優(yōu)切分點。

求特征和的基尼指數(shù)：

是

是

由于和只有一個切分點，所以它們就是最優(yōu)切分點。

求特征的基尼指數(shù)：

非常好

好

一般

一般最小，所以一般為的最優(yōu)切分點。

在、、、幾個特征中，是最小，所以選擇特征為最優(yōu)特征，是為其最優(yōu)切分點。于是根結點生成兩個子結點，一個是葉結點。對另一個結點繼續(xù)使用以上方法在、、中選擇最優(yōu)特征及其最優(yōu)切分點，結果是是。依此計算得知，所得結點都是葉結點。

1. 離散值處理

CART分類樹算法對離散值的處理，采用的思路：不停地二分離散特征。

在ID3、C4.5，特征被選取建立決策樹節(jié)點，如果它有多個類別我們會在決策樹上建立一個多叉點，這樣決策樹是多叉樹。CART采用的是不停的二分，決策樹為二叉樹。

假設特征有個離散值。分類標準是：每一次將其中一個特征分為一類，其他非該特征分為另一類。依照這個標準遍歷所有分類情況，計算每個分類下的基尼指數(shù)，最后選擇最小的作為最終的特征劃分。

如圖9-6，第1次取為類別1，那么剩下的特征 ,,……, 為類別2，由此遍歷，第次取為類別1，那么剩下的特征為類別2。

CART的特征會多次參與節(jié)點的建立，而在ID3或C4.5的一顆子樹中，離散特征只會參與一次節(jié)點的建立。

圖9-6 CART算法對離散值的劃分 4.連續(xù)值處理

具體思路：個樣本的連續(xù)特征有個，從小到大排列，CART取相鄰兩樣本值的平均數(shù)做劃分點，一共取個，其中第個劃分點表示為：。分別計算以這個點作為二元分類點時的基尼指數(shù)。選擇基尼數(shù)最小的點為該連續(xù)特征的二元離散分類點。

比如取到的基尼指數(shù)最小的點為，則小于的值為類別1，大于的值為類別2，這樣就做到了連續(xù)特征的離散化，接著采用基尼指數(shù)的大小來度量特征的各個劃分點。

劃分例子見圖9-7。

圖9-7 CART算法對連續(xù)值的劃分

9.4.3 CART回歸樹

回歸樹：輸出的是一個數(shù)值，特征選擇采用均方差。

CART(Classification and Regression Tree,分類回歸樹)，從名字就可以看出其不僅可以用于分類，也可以應用于回歸。其回歸樹的建立算法上與分類樹部分相似，這里簡單介紹下不同之處。

在回歸模型中，我們使用常見的均方差度量方式，對于任意劃分特征，對應的任意劃分點

兩邊劃分成的數(shù)據(jù)集 和 ，求出使 和 各自集合的均方差最小，同時 和 的均方差之和最小所對應的特征和特征值劃分點。表達式為：

其中，為數(shù)據(jù)集的樣本輸出均值，為數(shù)據(jù)集的樣本輸出均值。

相比ID3，CART遍歷所有的特征和特征值，然后使用二元切分法劃分數(shù)據(jù)子集，也就是每個節(jié)點都只會分裂2個分支。接著計算數(shù)據(jù)子集的總方差來度量數(shù)據(jù)子集的混亂程度，總方差越小數(shù)據(jù)子集越純，最后選擇總方差最小的劃分方式對應的特征和特征值，而二元切分的依據(jù)就是將小于等于這個特征值和大于這個特征值的數(shù)據(jù)劃分為兩塊。這里說的總方差一般就是通過數(shù)據(jù)子集的樣本輸出值的均方差乘以數(shù)據(jù)子集的樣本個數(shù)來計算。最后的輸出結果是取各葉子節(jié)點數(shù)據(jù)的中位數(shù)或均值。

9.4.4 CART剪枝處理

CART算法采用一種“基于代價復雜度的剪枝”方法進行后剪枝，這種方法會生成一系列樹，每個樹都是通過將前面的樹的某個或某些子樹替換成一個葉節(jié)點而得到的，這一系列樹中的最后一棵樹僅含一個用來預測類別的葉節(jié)點。然后用一種成本復雜度的度量準則來判斷哪棵子樹應該被一個預測類別值的葉節(jié)點所代替。

這種方法需要使用一個單獨的測試數(shù)據(jù)集來評估所有的樹，根據(jù)它們在測試數(shù)據(jù)集熵的分類性能選出最佳的樹。

核心思想：

(1) 計算每一個結點的條件熵。

(2) 遞歸的從葉子節(jié)點開始往上遍歷，減掉葉子節(jié)點，然后判斷損失函數(shù)的值是否減少，如果減少，則將父節(jié)點作為新的葉子節(jié)點。

(3) 重復第二步，直到完全不能剪枝。

9.4.5 CART算法總結

CART算法既可以用于分類，也可以用于回歸。在分類和回歸時，其算法流程大致相同，但是其特征劃分、樹結構、使用數(shù)據(jù)和剪枝等方面是不同的。

1.特征劃分

CART算法用基尼指數(shù)來選擇屬性(分類)，或用均方差來選擇屬性(回歸)。

2.樹結構

CART算法是一種二分遞歸分割技術，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子結點都有兩個分支，因此CART算法生成的決策樹是結構簡潔的二叉樹。

3.使用數(shù)據(jù)

CART算法既可以使用連續(xù)型的數(shù)據(jù)，也可以使用離散型的數(shù)據(jù)，同時支持特征的多次使用。

4.剪枝

CART算法支持剪枝操作，采用一種“基于代價復雜度的剪枝”方法進行后剪枝。

9.5 決策樹總結

9.5.1 三種決策樹算法的差異

建立決策樹主要有一下三種算法：ID3、C4.5 和 CART，總結對比下三者之間的差異。ID3、C4.5、CART這三種算法劃分的基本標準、剪枝策略，總結如表9-5：

表9-5三種決策樹算法的差異

算法	支持模型	樹結構	特征選擇	連續(xù)值處理	缺失值處理	剪枝	特征屬性多次使用
ID3	分類	多叉樹	信息增益	不支持	不支持	不支持	不支持
C4.5	分類	多叉樹	信息增益率	支持	支持	支持	不支持
CART	分類 回歸	二叉樹	基尼指數(shù) 均方差	支持	支持	支持	支持

9.5.2 決策樹的優(yōu)缺點

1.優(yōu)點

(1) 便于理解和解釋。計算簡單，樹的結構可視化，可解釋性強。

(2) 訓練需要的數(shù)據(jù)少，不需要數(shù)據(jù)規(guī)范化。

(3) 能夠處理連續(xù)型數(shù)據(jù)和離散型數(shù)據(jù)。

(4) 可自動忽略目標變量沒有貢獻的屬性變量，也為判斷屬性變量的重要性，減少變量的數(shù)目提供參考。

(5) 比較適合處理有缺失屬性的樣本。

2.缺點

(1) 容易造成過擬合，需要采用剪枝操作。

(2) 忽略了數(shù)據(jù)之間的相關性。

(3) 對于各類別樣本數(shù)量不一致的數(shù)據(jù)，信息增益會偏向于那些更多數(shù)值的特征。

(4) 對新增加的樣本，需要重新調(diào)整樹結構。

參考文獻

[1] QUINLAN J R . Introduction of decision trees[J]. Machine Learning, 1986, 1(1):81-106.

[2] QUINLAN J R. C4. 5: programs for machine learning[M]. Boston: Morgan Kaufmann,1993.

[3] BREIMAN L, FRIEDMAN J H, OLSHEN R A, et al. Classification and regression trees[M]. New York: Chapman and Hall/CRC,1984

[4] 李航. 統(tǒng)計學習方法[M]. 北京: 清華大學出版社,2019.

[5] 周志華. 機器學習[M]. 北京: 清華大學出版社,2016.

[6] Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning[M]. New York: Springer,2001.

[7] Peter Harrington.機器學習實戰(zhàn)[M]. 北京:人民郵電出版社,2013.

[8] CHRISTOPHER M. BISHOP. Pattern Recognition and Machine Learning[M]. New York: Springer,2006.

本文節(jié)選自《機器學習入門基礎（微課版）》一書，作者：黃海廣，徐震，張笑欽。文章來源地址http://www.zghlxwxcb.cn/news/detail-821203.html