3.2 決策樹模型

決策樹是一種基于樹結構的機器學習模型，常用于回歸或分類等預測性任務。決策樹的基本思想是直接模擬人類進行級聯選擇或決策的過程，它按照屬性的某個優先級依次對數據的全部屬性進行判別，從而得到輸入數據所對應的預測輸出。決策樹模型的求解思路與線性模型有很大差異：決策樹模型按照屬性的優先級依次對數據的全部屬性進行判別，從而完成對樣本數據的回歸或分類預測任務；線性模型則是將樣本數據的所有特征通過賦予權重參數再相加得到一個綜合數值，重點在于得到樣本數據各屬性值的權重參數。因此，決策樹模型比線性模型更具可解釋性，更易于理解。決策樹學習是指從訓練樣本數據中自動構造出決策樹模型的機器學習技術。目前，決策樹模型及其機器學習技術已被廣泛應用于醫學、制造產業、天文學、生物學以及商業等諸多領域。本節首先介紹決策樹模型的基本結構，然后分析決策樹模型的內部結點選擇的判別標準，最后給出決策樹模型的若干訓練構造算法。

3.2.1 模型結構

決策樹模型將思維過程抽象為一系列對已知數據屬性的判別或決策過程，使用樹結構表示判別的邏輯關系和一系列的判別過程，并通過葉結點表示判別或決策結果，計算過程條理清晰，邏輯結構一目了然。例如，學生小明在周五晚上考慮他在周末的安排，需要根據諸如有無作業、有無聚會和天氣是否適宜等因素做出安排或決策，可用圖3-7所示的決策樹模型表示小明的決策過程。

如圖3-7所示，決策樹是一個外向樹模型，包含一個根結點、若干內部結點和葉結點。其中葉結點表示決策的結果，內部結點表示對樣本某一屬性的判別。這些判別直接或間接地影響著決策的最終結果。從根結點到某一葉結點的路徑稱為測試序列，例如，圖3-8所示的一條測試序列表示這個周末小明沒有作業也沒有聚會，并且天氣適宜，這種情況所對應的決策結果就是運動。決策樹使用內部結點表示對確定屬性的判別，每個結點可以看作一個if-then規則判別。例如，對于“有無作業”這一屬性，如果判別結果為“有”，則小明周末就去學習，否則就進一步判斷“有無聚會”。顯然，決策樹的測試序列可以看作是一系列if-then規則判別的組合，因此決策樹是一類基于規則的模型。如果將決策樹的每個測試序列分別看作一條規則，那么對于給定的機器學習任務和用于處理該任務的決策樹模型，每個決策結論將有且僅有一條相應的規則與之對應。

圖3- 用于周末安排的決策樹模型

圖3-8 測試序列示意圖

【例題3.4】現有12枚外觀相同的硬幣，其中有1枚是假的且比真幣重。如何使用一個無砝碼天平把假幣找出來，要求不超過三次稱重。

【解】如圖3-9所示，把硬幣等分成三份，用天平分別對其中任意兩份進行稱重，確定假幣在哪一份。之后再對假幣所在的那一份進行等分，并通過稱重確定假幣在哪一份，直至找到假幣。由圖3-9可知，從根到葉就是一種基于分組比較的求解過程，該樹有12片葉子，故最多有12種可能的解。由于樹高為3，故最多只需要3次判別就能得到結論。□

圖3-9 用于找假幣的決策樹模型

決策樹模型的構造可以通過對訓練樣本數據的學習來實現。事實上，決策樹模型的構造是一個通過遞歸方式對訓練樣本集不斷進行子集劃分的過程。例如，對于上述小明周末安排的問題，表3-4列出所有8種可能狀態。在對根結點進行判別之后，原數據集便按“有無作業”被劃分為了兩個子數據集，即表3-4中左邊4種情況和右邊4種情況。

表3-4 周末安排問題的整個數據集

不同判別策略會產生不同的屬性劃分標準，從而在決策樹模型中產生不同的內部結點和分支。因此，構造決策樹模型的關鍵在于選擇適當內部結點所對應的屬性，即通過選擇適當的內部結點的判別屬性來合理地構造分支。每個分支結點根據判別屬性將其對應的數據集劃分為相應的子數據集，使得每個子數據集中的樣本盡可能屬于同一類別。當結點上的數據都是屬于同一類別或者沒有屬性可以再用于對數據集進行劃分時，則停止劃分并獲得劃分結果。

綜上所述，可得決策樹構造的基本思路如下：首先，根據某種分類規則得到最優的劃分特征，計算最優特征子函數，并創建特征的劃分結點，按照劃分結點將數據集劃分為若干部分子數據集；然后，在子數據集上重復使用判別規則，構造出新的結點，作為樹的新分支。在每一次生成子數據集之前，都要檢驗遞歸是否符合遞歸終止條件，即數據均屬于同一類別或者再也沒有用于數據劃分的屬性。若滿足遞歸終止條件，則結束構造過程，否則將新結點所包含數據集和類別標簽作為輸入，重復遞歸執行。

決策樹構造完成后，對于給定的樣本輸入，可通過決策樹提供的一系列判別條件找到最終的葉結點所對應的類別標簽，得到判別所需的判別結果。

3.2.2 判別標準

如前所述，構造決策樹的關鍵在于合理選擇其內部結點所對應的樣本屬性，使得結點所對應樣本子集中的樣本盡可能多地屬于同一類別，即具有盡可能高的純度。如果結點的樣本子集屬于同一類型，則可將該結點置為該類別的葉結點，不用對其做進一步判別。因此，內部結點所對應樣本子集的純度越高，決策樹模型對樣本數據的分類能力也就越強。一般來說，決策樹判別標準需要滿足以下兩點：

第一，如果結點對應數據子集中的樣本基本屬于同一個類別，則不用再對結點的數據子集做進一步劃分，否則就要對該結點的數據子集做進一步劃分，生成新的判別標準；

第二，如果新判別標準能夠基本上把結點上不同類別的數據分離開，使得每個子結點都是類別比較單一的數據，那么該判別標準就是一個好規則，否則需重新選取判別標準。

由以上分析可得決策樹判別屬性的選擇標準，即對于一個給定決策樹分支結點，選擇該結點所對應子集純度最高的屬性作為判別標準最為合理。

為合理量化決策樹的判別屬性選擇標準，可以使用信息論中熵的有關知識來對樣本集合的純度進行定量表示和分析。信息熵（簡稱為熵）是信息論中定量描述隨機變量不確定度的一類度量指標，主要用于衡量數據取值的無序程度，熵值越大則表明數據取值越雜亂無序。

假設ξ為具有n個可能取值{s₁，s₂，…，s_n}的離散型隨機變量，概率分布為P（ξ=s_i）=p_i，則其信息熵定義為

顯然，如果H（ξ）值越大，則隨機變量ξ的不確定性就越大。

對于任意給定的兩個離散隨機變量ξ，η，其聯合概率分布為

P（ξ=s_i，η=t_i）=p_ij，i=1，2，…，n；j=1，2，…，m

則η關于ξ的條件熵H（η|ξ）定量表示在已知隨機變量ξ取值的條件下隨機變量η取值的不確定性，計算公式為隨機變量η基于條件概率分布的熵對隨機變量ξ的數學期望，即有

其中，p_i=P（ξ=s_i），i=1，2，…，n。

對于任意給定的訓練樣本集合D，可將集合D看成是一個關于樣本標簽取值狀態的隨機變量，由此可根據熵的本質內涵來定義一個量化指標H（D）進而度量D中樣本類型的純度，通常稱H（D）為經驗熵。H（D）值越大，則表明D中所包含樣本標簽取值越雜亂；H（D）值越小，則表明D中所包含樣本標簽取值越純凈。H（D）的具體計算公式如下

其中，n表示樣本標簽值的取值狀態數；C_k表示訓練樣本集D中所有標注值為第k個取值的訓練樣本組成的集合，|D|和|C_k|分別表示集合D和C_k的基數。

對于訓練樣本集合D上的任意屬性A，可在經驗熵H（D）的基礎上進一步定義一個量化指標H（D|A）來度量集合D中的樣本在以屬性A為標準劃分后的純度，通常稱H（D|A）為集合D關于屬性A的經驗條件熵。H（D|A）的計算公式如下

其中，m表示屬性A的取值狀態數；D_i表示集合D在以屬性A為標準劃分后所生成的子集，即為D中所有屬性A取第i個狀態的樣本組成的集合。

由經驗熵H（D|A）的定義可知，其值越小則樣本集合D的純度越高。可在經驗熵的基礎上進一步計算每個屬性作為劃分指標后對數據集合經驗熵變化的影響，即信息增益。信息增益度量的是已知隨機變量ξ的信息使得隨機變量η的信息不確定性減少的程度。

對于任意給定的訓練樣本數據集合D及其上的某個屬性A，屬性A關于集合D的信息增益G（D，A）定義為經驗熵H（D）與條件經驗熵H（D|A）之差，即有

顯然，對于屬性A關于集合D的信息增益G（D，A），如果其值越大則表示使用屬性A劃分后的樣本集合純度越高，使得決策樹模型具有更強的分類能力，故可將G（D，A）作為標準選擇合適的判別屬性，通過遞歸計算樣本屬性的信息增益以實現對決策樹的構造。

【例題3.5】表3-5所示的數據集表示豌豆種子在不同環境下能否發芽的情況。豌豆種子自身有形狀、大小和種皮顏色等特征，外部影響環境有土壤、水分和日照等特征。試通過表3-5所示數據集構造決策樹并根據最后一行測試數據預測該豌豆能否發芽。

表3-5 豌豆數據集

（續）

【解】首先，計算訓練樣本數據集的經驗熵。每個訓練樣本的標注有兩個可能的取值，分別是能發芽和不能發芽，其中是能發芽占比為5/9，不能發芽占比為4/9，故有

然后，分別計算各屬性的信息增益。若以“形狀”作為劃分屬性，則將訓練樣本集合D劃分成D（圓形）和D（皺形）這兩個子集，分別計算D（圓形）和D（皺形）的經驗熵

由此可得形狀屬性的信息增益如下

同理可得其他屬性的信息增益如下：G（D，顏色）=0.09，G（D，大小）=0.09，G（D，土壤）=0.09，G（D，水分）=0.23，G（D，日照）=0.09。

顯然，水分屬性的信息增益最大，故選擇“水分”作為第一個劃分屬性，得到圖3-10所示的初始決策樹，其中D（多）={1，3，4，8}表示水分為多的訓練樣本集，D（少）={2，5，6，7，9}表示水分為少的訓練樣本集。同理繼續對D（多）和D（少）進行劃分，可得圖3-11所示的完整決策樹。

圖3-10 初始決策樹

圖3-11 完整決策樹

使用所得決策樹對測試1中的樣本進行預測。首先，其“水分”為“多”，故進入左子樹，接著其“日照”在“12h以下”進入左子樹，最后其“大小”為“飽滿”得到它的分類為“是”，故根據該決策樹的預測結果，判斷測試1中的樣本為能夠發芽。□

使用信息增益指標作為劃分屬性選擇標準時，選擇結果通常會偏向取值狀態數目較多的屬性。為解決這個問題，最簡單的思路是對信息增益進行歸一化，信息增益率便可看作對信息增益進行歸一化后的一個度量標準。信息增益率在信息增益基礎上引入一個校正因子，消除屬性取值數目的變化對計算結果的干擾。具體地說，對于任意給定的訓練樣本數據集合D及其上的某個屬性A，屬性A關于集合D的信息增益率G_r（D，A）定義如下

其中Q（A）為校正因子，由下式計算

顯然，屬性A的取值狀態數m值越大，則Q（A）值也越大，由此可以減少信息增益的不良偏好對決策樹模型構造所帶來的影響，使得所建決策樹擁有更強的泛化能力。

對于決策樹模型，還可采用基尼指數（Gini Index）作為劃分標準來選擇最優屬性。與熵的概念類似，基尼指數可用來度量數據集的純度。對于任意給定的一個m分類問題，假設樣本點屬于第k類的概率為p_k，則關于這個概率分布p的基尼指數可以定義為

即有

相應地，對于任意給定的樣本集合D，可將其基尼指數定義為

其中，C_k是D中屬于第k類的樣本子集；m是類別數。

樣本集合D的基尼指數表示在D中隨機選中一個樣本被錯誤分類的概率。顯然，Gini（D）的值越小，數據集D中樣本的純度越高，或者說D中樣本種類的一致性越高。

若樣本集合D根據屬性A是否取某一可能值a而被分割為D₁和D₂兩部分，即

D₁={（X，y）∈D|A（X）=a}，D₂=D-D₁

則在屬性A為劃分屬性的條件下，集合D的基尼指數可以定義為

例如，可以根據表3-5給出的豌豆數據集計算某些特征的基尼指數，將“大小”作為劃分屬性把集合劃分為D（飽滿）和D（皺縮）這兩個子集，分別計算這兩個子集的基尼指數

由此可得在“大小”這一屬性條件下D的基尼指數為

同理可得：Gini（D，形狀）=0.489，Gini（D，顏色）=0.433，Gini（D，土壤）=0.433，Gini（D，水分）=0.344，Gini（D，日照）=0.433。其中水分屬性的基尼指數最小，故將水分作為第一個劃分屬性，將集合D劃分為D（多）和D（少），分別對樣本集合D（多）和D（少）遞歸調用以上步驟，最后可得如圖3-12所示的完整決策樹。

圖3-12 依據基尼指數構造的決策樹模型

3.2.3 模型構造

本節介紹基于上述判別標準的三種經典的決策樹生成算法，即基于信息增益的ID3算法、基于信息增益率的C4.5算法以及基于基尼指數的CART算法。

ID3算法以信息增益最大的屬性為分類特征，基于貪心策略自頂向下地搜索遍歷決策樹空間，通過遞歸方式構造決策樹。具體地說：從根結點開始，計算當前結點所有特征的信息增益，選擇信息增益最大的特征作為該結點的分類特征，并針對該分類特征的每個不同取值分別建立相應子結點；再分別對所有子結點遞歸地調用以上方法，構造決策樹，直到所有特征的信息增益、很小或沒有特征可以選擇為止，由此得到一個完整的決策樹模型。

【例題3.6】表3-6是一個由16個樣本組成的感冒診斷訓練數據集D。每個樣本由4個特征組成，即體溫、流鼻涕、肌肉疼、頭疼。其中體溫特征有3個可能取值：正常、較高、非常高；流鼻涕、肌肉疼、頭疼分別有兩個可能取值：是、否；樣本的標注值為是否感冒。試用ID3算法通過訓練數據集D建立一個用于判斷是否感冒的決策樹。

表3-6 感冒診斷數據表

（續）

【解】首先，計算訓練數據集D的經驗熵為

若以“體溫”作為劃分屬性，則可將數據集D劃分為D（正常）、D（較高）、D（非常高）這三個子集合，分別計算它們的經驗熵，得到：

H（D（正常））=0.971，H（D（較高））=0.65，H（D（非常高））=0.7219

由此可得“體溫”屬性的信息增益為G（D，體溫）=0.0385。同理可得其他屬性的信息增益：

G（D，流鼻涕）=0.5117，G（D，肌肉疼）=0.0038，G（D，頭疼）=0.0359

其中，G（D，流鼻涕）的值最大，故取“流鼻涕”作為第一個劃分屬性。

將集合D劃分為

D₁=D（流鼻涕=是）={1，3，4，6，7，8，10，11}

D₂=D（流鼻涕=否）={2，5，9，12，13，14，15，16}

對集合D₁計算其余三個屬性的信息增益，得到：

G（D₁，體溫）=0.1992，G（D₁，肌肉疼）=0.0924，G（D₁，頭疼）=0.1379

其中，G（D₁，體溫）的值最大，故選擇“體溫”作為對集合D₁的劃分屬性。同理，對集合D₂計算其余三個屬性的信息增益，得到：

G（D₂，體溫）=0.0157，G（D₂，肌肉疼）=0.0157，G（D₂，頭疼）=0.0032

由于G（D₂，體溫）=G（D₂，肌肉疼），故可在這兩者中任選其一作為該結點的劃分屬性。此處選擇“肌肉疼”作為集合D₂的劃分屬性。

對于已劃分的子數據集，若其不滿足算法終止條件，則遞歸調用上述步驟進一步對子集進行劃分，直至滿足算法終止條件，得到圖3-13中所示的完整決策樹。□

圖3-13 由ID3算法構造的完整決策樹

ID3算法所采用的信息增益度量傾向于選擇具有較多屬性值的屬性作為劃分屬性，有時這些屬性可能不會提供太多有價值的信息，并且ID3算法并不能處理連續值和缺失值。為此可對ID3算法進行改進，使用信息增益率代替信息增益作為決策樹判別標準，由此產生C4.5算法。C4.5算法通常泛指基本C4.5生成算法、C4.5剪枝策略，以及擁有多重特性的C4.5規則等一整套算法。對于任意給定的訓練樣本集D，在D上運行C4.5算法可以通過學習得到一個從特征空間到輸出空間的映射，進而可使用該映射去預測新實例的類別。

在使用基本的C4.5算法構造決策樹時，信息增益率最大的屬性即為當前結點的劃分屬性。隨著遞歸計算的進行，被計算的屬性的信息增益率會變得越來越小，到后期則選擇相對比較大的信息增益率的屬性作為劃分屬性。為避免過擬合現象，C4.5算法中引入了剪枝策略，剪枝就是從決策樹上裁剪掉一些子樹或者葉結點，并將其根結點或父結點作為新的葉結點，從而簡化分類樹模型。剪枝的目的是為了減少決策樹學習中出現的過擬合現象，決策樹剪枝策略有預剪枝和后剪枝兩種。

預剪枝是指在決策樹的生成過程中，對每個子集在劃分前先進行估計，若當前結點的劃分不能帶來泛化性能的提升，則停止劃分并將當前結點標記為葉結點。事實上，在決策樹的生成過程中，雖然對有些分支的當前劃分并不能提升泛化性能，甚至有可能導致泛化性能暫時下降，但有利于從整體上提升決策樹的泛化性能。因此，通常難以保證預剪枝方法不會錯誤地阻止決策樹的生長。后剪枝則先從訓練樣本集生成一棵完整決策樹，然后自底向上或自頂而下考察分支結點，若將該結點對應子樹替換為葉結點能提升模型泛化性能，則進行替換。這樣可以保證剪枝操作不會降低決策樹模型的泛化性能，因此通常采用后剪枝策略。

C4.5算法通常采用一種名為悲觀錯誤剪枝（Pessimistic-Error Pruning，PEP）的算法來實現對決策樹的剪枝優化。PEP算法是一種自頂而下的后剪枝方法，主要以剪枝前后的錯誤率為標準來判定是否進行子樹的修剪。因此，該方法不需要單獨的剪枝數據集。

PEP算法的基本思想是分別考察每個內部結點對應的子樹所覆蓋訓練樣本的誤判率與剪去該子樹后所得葉結點對應訓練樣本的誤判率，然后通過比較二者間的大小關系確定是否進行剪枝操作。當剪枝后所獲得葉結點的誤判率小于所對應的子樹誤判率時，進行剪枝顯然提升了決策樹的泛化性能。然而，由于PEP算法直接通過訓練樣本集來對子樹和葉結點進行評估，導致子樹的誤判率一定小于葉結點的誤判率，從而得到在任何情況下都不需要剪枝的錯誤結論。為避免出現這種錯誤結論，PEP算法在計算誤判率時添加了一個經驗性懲罰因子。

具體地說，假設由訓練樣本數據集生成的決策樹為T，對于T的任意一個葉結點t，與其對應的訓練樣本個數為n（t），其中被錯誤分類的樣本個數為e（t）。由于訓練數據既用于生成決策樹又用于對決策樹的剪枝，故基于此訓練數據集的誤判率r（t）=e（t）/n（t）具有一定偏差，不能直接作為是否進行剪枝的判斷標準。因此，PEP算法在計算誤判率時添加了一個經驗性懲罰因子1/2，將誤判率計算公式修正為

不失一般性，設T_t為樹T的子樹，i為覆蓋T_t的葉結點，N_i為子樹T_t的葉結點數，則子樹T_t的分類誤判率為

在定量分析中，為簡單起見，直接使用作為分子的誤判樣本數代替誤判率參與計算。對于葉結點t，有

對于子樹T_t，有

由此可得子樹T_t被葉結點t替換的條件是

其中，S_e（e′（T_t））表示標準誤差，具體計算公式如下

如果式（3-32）成立，則子樹T_t應被修剪掉，并用相應的葉結點替代；否則，不進行剪枝。對所有非葉結點自頂而下依次計算測試，判斷它們是否應被修剪掉。

例如，對于圖3-14所示的決策樹，將其中第i個結點記為t_i。令A和B分別表示訓練樣本集中的兩個不同類別。現用PEP算法對該決策樹進行剪枝。首先，計算各分支結點的誤差。例如，t₁對應的訓練數據集中包含55個A類樣本、25個B類樣本，則e（t₁）=25。表3-7中數據為決策樹中各分支結點的PEP算法參數和算法結果。由計算結果可知t₄結點的子樹應該被剪枝，由此可得如圖3-15所示的剪枝后的優化決策樹。

表3-7 參與PEP算法判別各項的取值表

圖3-14 初始決策樹

圖3-15 PEP算法剪枝后的決策樹

根據以上分析得到C4.5算法的基本步驟如下：

（1）確定閾值ε，并令Γ表示樣本屬性組成的集合；

（2）若數據集D中所有樣本屬于同一個類C_i，則置Tree為單結點樹，并將C_i作為該結點的類，返回Tree。若Γ=?，則置Tree為單結點樹，并將D中樣本數最大的類C_i作為該結點的類，返回Tree；否則，分別計算集合Γ中所有屬性對于訓練數據集D的信息增益率，選擇其中信息增益率最大的屬性A_g作為劃分屬性；

（3）如果劃分屬性A_g的信息增益率小于閾值ε，則置Tree為單結點樹，并將D中實例數最大的類C_i作為該結點的類，返回Tree；否則，對A_g的每個可能取值a_gi，依照A_g=a_gi將D分割為若干非空樣本子集D_i，將D_i中樣本數最大的類別作為標記值，由此構造子結點并由該結點及其子結點構成樹Tree，返回Tree；

（4）對結點i，以D_i為訓練集，以Γ-{A_g}為特征集，遞歸地調用步驟（2）～步驟（3），得到子樹Tree_i，返回Tree_i；

（5）對生成的決策樹使用PEP算法進行剪枝，得到所求優化決策樹模型。

【例題3.7】某公司每年端午節都會組織公司員工進行龍舟比賽，舉行龍舟比賽通常要考慮天氣因素，若天氣情況糟糕，則公司會取消比賽。現有2003～2016年端午節當天的數據（編號為1～14）及天氣情況如表3-8所示，試根據該表中的數據集使用C4.5算法構造用于幫助公司判斷是否會取消龍舟比賽的決策樹。

表3-8 天氣情況表

【解】對于表3-8所示數據集D，令A和C分別表示其特征集合和輸出空間，則有A={天氣，溫度，濕度，風速}，C={進行，取消}。首先，計算訓練樣本集D的信息增益：D中包含14個樣本，其中屬于類別“進行”的有9個，屬于類別“取消”的有5個，其信息增益為

然后，計算特征集合A中的每個特征對數據集D的經驗條件熵H（D|A），得到：

根據以上結果可算得每個屬性的信息增益值：

G（D，天氣）=H（D）-H（D|天氣）=0.940-0.694=0.246

G（D，溫度）=H（D）-H（D|溫度）=0.940-0.911=0.029

G（D，濕度）=H（D）-H（D|濕度）=0.940-0.789=0.151

G（D，風速）=H（D）-H（D|風速）=0.940-0.892=0.048

為計算信息增益率，還需計算各個屬性的校正因子Q（A）值。天氣屬性有3個取值（晴、雨、陰），其中5個樣本取晴、5個樣本取雨、4個樣本取陰，故有：

溫度屬性有3個取值（炎熱、適中、寒冷），其中4個樣本取炎熱、6個樣本取適中、4個樣本取寒冷，故有：

濕度屬性有2個取值（高、正常），其中7個樣本取正常、7個樣本取高，故有：

風速屬性有2個取值（強、弱），其中6個樣本取強、8個樣本取弱，故有：

根據以上結果算得信息增益率G_r（D，A）的值如下：

G_r（D，天氣）=0.156；G_r（D，溫度）=0.018

G_r（D，濕度）=0.151；G_r（D，風速）=0.049

由于G_r（D，天氣）的取值最大，故將天氣屬性作為所求決策樹的第一個決策結點，將樣本集合D劃分為D（陰）、D（晴）、D（雨）這三個子集合，其中D（陰）={3，7，12，13}，D（晴）={1，2，8，9，11}，D（雨）={4，5，6，10，14}。由于D（陰）中所有樣本都屬于同一類，故不再對其進行劃分，并將其標記為進行活動。通過遞歸調用算法分別對樣本集合D（晴）和D（雨）做進一步劃分，直到滿足算法結束條件。由以上過程可得到圖3-16所示的決策樹模型，其中Y表示進行活動的天數，N表示取消活動的天數。對該決策樹所有分支點計算PEP算法參數，得到表3-9所示的計算結果，由表中數據可知當前決策樹已是所求最優決策樹，不需要剪枝。□

圖3-16 C4.5生成算法構造的決策樹

表3-9 PEP算法參數和計算結果

上述ID3算法和C4.5算法構造的決策樹模型都屬于分類樹，即通過數據對象的特征來預測該對象所屬的離散類別。CART算法則既可構造用于分類的分類決策樹，也可構造用于回歸分析的回歸決策樹。與C4.5算法和ID3算法不同的是，CART算法依據特征取值對訓練樣本集進行二元劃分，使得由CART算法構造的決策樹必是一棵二叉樹。

例如，對于年齡特征的三個取值{青年，中年，老年}，相應結點通常應取3個分支，由于CART算法要求決策樹為二叉樹，使得內部結點的特征取值為“是”或“否”，故需對該年齡特征的每個取值進行人為二元劃分，得到三對不同取值形式，即有：

年齡=青年，年齡≠青年；年齡=中年，年齡≠中年；年齡=老年，年齡≠老年

使用CART算法構造分類決策樹需選擇合適的特征作為結點屬性，并選擇合適的二元劃分形式作為結點分支的判別條件。如前所述，基尼指數值越小就說明二分之后子數據集樣本種類的純度越高，即選擇該屬性和該二元劃分形式分別作為結點屬性和判別條件的效果越好。因此，CART算法主要使用基尼指數值作為劃分特征選擇的標準。

具體地說，如果需要使用屬性A將訓練樣本集劃分為兩個部分，則需要確定選擇何種二元劃分方式來構造分支。假設屬性A的可能取值為{a₁，a₂，…，a_n}并選擇其中第i個特征值a_i作為劃分標準，即該分支所對應的判別條件分別為A=a_i，A≠a_i，則將劃分得到的兩個子數據集分別記為D₁、D₂，并算出該劃分所對應的基尼指數

根據以上方法分別算出特征A的所有二元劃分所對應的基尼指數，并取其中最小基尼指數所對應的二元劃分作為候選分支結點判別條件。計算所有特征的候選分支結點判別條件，取其中基尼指數最小的判別條件作為該結點的分支判別條件，完成對該結點的分支。

CART算法主要通過最小化平方誤差的優化計算方式構造回歸決策樹。對于輸入空間中給定的某個劃分，可通過構造回歸樹將該劃分的所有劃分單元分別映像到對應輸出值上。對于給定回歸任務和訓練樣本集D={（X₁，y₁），（X₂，y₂），…，（X_n，y_n）}，若將該回歸任務的輸入空間劃分為k個單元L₁，L₂，…，L_k，則回歸決策樹f在第s個單元L_s上的整體平方誤差為

顯然，當決策回歸樹f對劃分D_s的輸出為該劃分中所有輸入樣本所對應真實標記的均值時，R_s最小。即當

時，R_s最小。記

由于CART算法要求生成一棵二叉樹，故采用遞歸二元劃分方式通過對輸入空間的劃分構造回歸樹。具體地說，對于訓練樣本集D={X₁，X₂，…，X_n}，CART算法遞歸尋找單個特征x_j作為切分變量并確定x_j的某個取值b作為切分點，將訓練子集劃分為兩個區域

L₁（x_j，b）={X|x_j≤b}；L₂（x_j，b）={X|x_j>b}

決策樹f在這兩個區域上的整體誤差平方和為

選擇不同的切分變量和切分點對上述整體誤差平方和進行優化，其值達到最小時所對應的切分變量和切分點即為回歸決策樹當前結點屬性和對應的分支判別條件。因此，回歸決策樹當前結點的屬性X_j和對應判別閾值b可通過求解如下優化問題得到

遞歸上述過程直至滿足算法終止條件，便可生成一棵完整的回歸決策樹。此類通過最小化誤差平方和而構造的回歸樹通常也稱為最小二乘回歸樹。

【例題3.8】使用表3-10所示訓練樣本集構造一棵含三個葉結點的最小二乘回歸樹f。

表3-10 訓練樣本集

【解】記編號為i的樣本為X_i，由于樣本只有一個特征x，故x為最優切分變量。考慮9個切分點{1.5，2.5，3.5，4.5，5.5，6.5，7.5，8.5，9.5}，選用誤差平方和作為目標函數F（θ），則有

其中

將上述9個切分點分別代入目標函數，例如，取θ=1.5時，有

L₁={X₁}，L₂={X₂，X₃，X₄，X₅，X₆，X₇，X₈，X₉，X₁₀}；，

選取所有不同切分點θ可得的取值如表3-11所示。

表3-11取值表

將，代入目標函數F（θ）可得到目標函數的取值如表3-12所示。

表3-12 目標函數F（θ）取值表

可見取θ=6.5時，F（θ）最小。故切分變量x的第一個切分點為θ=6.5。使用選定的切分變量和切分點劃分區域，并決定輸出值。兩個區域分別是

L₁={X₁，X₂，X₃，X₄，X₅，X₆}，L2={X₇，X₈，X₉，X₁₀}

當前情況下決策樹的輸出值為

繼續對得到的樣本子集進行劃分，對L₁繼續進行劃分，選取不同的切分點θ可得到的取值如表3-13所示。計算得F（θ）的取值如表3-14所示。

表3-13取值表

表3-14F（θ）取值表

由表3-14中數據可知，當θ=3.5時，F（θ）取值最小，故得切分點為θ=3.5。由此可得如下所求回歸決策樹：當x≤3.5時，f（X）=5.72；當3.5<x≤6.5時，f（X）=6.75；當x>6.5時，f（X）=8.91。□

CART算法主要通過代價復雜度剪枝（Cost-Complexity Pruning，CCP）方法防止所建決策樹模型產生過擬合現象。CCP剪枝方法首先通過某種策略從待剪枝決策樹T₀的底端開始不斷剪枝，一直剪到T₀的根結點，由此形成一個子樹序列{T₀，T₁，…，T_n}，然后在獨立驗證數據集上對子樹序列進行測試，從中選擇最優子樹。

為找出決策樹中適合剪枝的子樹，CCP方法采用公式R_α（T）=R（T）+α|T|度量子樹的整體泛化性能。其中，T為任意子樹；R（T）為子樹T對訓練樣本集的預測誤差（如誤差平方和）；|T|為子樹葉結點個數；α≥0為參數，用于權衡子樹T對訓練樣本集擬合程度與模型復雜度之間的制約關系；R_α（T）為參數為α時子樹T的整體泛化性能值，R_α（T）的取值越小，則所對應子樹T的泛化性能就越好。

顯然，對給定的α值，一定存在使整體泛化性能值R_α（T）最小的子樹，將其記為T_α。易知最優子樹T_α對于給定的α值是唯一的。當α較大時，T_α的規模偏小，因為此時R_α（T）對模型復雜度懲罰力度較大，傾向于生成較小子樹；反之，當α較小時，最優子樹T_α規模較大，極端地，當α=0時，整個樹為最優，當α→∞時，由根結點組成的單結點樹為最優。

對于任意給定的待剪枝原始樹T₀及其任意內部結點t，設以t為單結點樹和以t為根結點子樹T_t的泛化性能值分別為R_α（t）和R_α（T_t），則有

R_α（t）=R（t）+α，R_α（T_t）=R（T_t）+α|T_t|

顯然，多結點子樹T_t對訓練樣本集的擬合程度優于單結點子樹t，即有R（T_t）<R（t）。換言之，在α較小時，預測誤差項所占權重較大，故有：R_α（T_t）<R_α（t）。若增大α取值，則模型復雜程度對整體性能度量的影響將會逐漸增大，最終使得R_α（T_t）>R_α（t）。

不難證明，若取α（t）=[R（t）-R（T_t）]/（|T_t|-1），則多結點子樹T_t與單結點子樹t的整體性能度量取值相等。由于此時t的結點較少，因此t比T_t更可取，此時可對T_t進行剪枝。

對T₀中每一內部結點t計算α（t）值，然后在T₀中剪去α（t）值最小的T_t并將所得子樹記為T₁，同時將α（t）的最小值記為α₁。遞歸上述過程，直至得到由根結點構成的單結點子樹。在這一過程中，不斷地增加α的值，獲得一個取值遞增的參數序列α₁，α₂，…，α_n，以及剪枝后得到的子樹序列{T₀，T₁，…，T_n}。可使用獨立測試集從{T₀，T₁，…，T_n}中選取最優子樹T_α。具體地說，就是通過獨立測試集分別測試子樹序列{T₀，T₁，…，T_n}中各棵子樹的泛化性能，從中選擇性能最優的子樹作為所求剪枝結果。

【例題3.9】表3-15為拖欠貸款人員訓練樣本數據集，使用CART算法基于該表數據以構造決策樹模型，并使用表3-16中測試樣本集確定剪枝后的最優子樹。

表3-15 拖欠貸款人員訓練樣本數據集

表3-16 拖欠貸款人員測試樣本數據集

【解】先考察房產狀況特征，根據是否有房可將數據集劃分為D（有）={1，4，7}和D（無）={2，3，5，6，8，9，10}，分別計算D（有）和D（無）的基尼指數

故用房產狀況特征對D進行子集劃分時所得的基尼指數為

若按婚姻情況特征劃分，需對其構造二元劃分，此時可將婚姻情況特征分為如下三對可能取值形式，并分別計算每種取值形式所對應子集劃分的基尼指數。

“婚姻情況=已婚”和“婚姻情況≠已婚”

“婚姻情況=單身”和“婚姻情況≠單身”

“婚姻情況=離異”和“婚姻情況≠離異”

當劃分取值為“婚姻情況=已婚”和“婚姻情況≠已婚”時：

當劃分取值為“婚姻情況=單身”和“婚姻情況≠單身”時：

當劃分取值為“婚姻情況=離異”和“婚姻情況≠離異”時：

對比上述計算結果，取值分組“婚姻情況=已婚”和“婚姻情況≠已婚”所得基尼指數最小，故取Gini（D，婚姻）=0.3。

最后考慮年收入特征，由于該特征為連續性數值，故對其進行二元劃分時可用閾值將年收入特征取值范圍劃分為兩個不同區間，具體做法如下：首先，依據“年收入”特征取值對樣本進行升序排序，從小到大依次用“年收入”特征相鄰取值的均值作為劃分閾值，將訓練樣本集劃分為兩個子集。

例如，有兩個相鄰樣本的“年收入”取值分別為60和70時，取它們的均值65作為劃分閾值，即用R=65表示年收入的劃分點，將“年收入>R”和“年收入<R”的樣本分別劃分到兩個樣本子集中，并計算對應的基尼指數

同理可得表3-17所示其余劃分方式及所對應的基尼指數，由表3-17中數據可知，使用年收入特征對D進行劃分的最小基尼指數為Gini（D，R=97.5）=0.3。

表3-17 年收入特征的劃分方式與基尼指數取值表

根據以上計算可知，婚姻情況和年收入特征所對應基尼指數并列最小，均為0.3。不妨選取婚姻狀況作為第一個劃分點，將集合D劃分為D（已婚）={2，4，6，9}和D（?已婚）={1，3，5，7，8，10}，得到如圖3-17a所示的初始決策樹。

由于D（已婚）中所有人均不欠貸款，故不用再劃分。對D（?已婚）遞歸調用上述過程繼續劃分，最后得到圖3-17b所示的完整決策樹，其中Y和N分別表示兩類不同取值的樣本數目。

圖3-17 使用CART生成算法構造的完整決策樹

現對圖3-17b所示決策樹進行CCP剪枝優化。設k=0，T=T_k，α_k=+∞，從根結點t₁往下計算每個點的α（t），得到t₂和t₃的α（t）值并列最小，均為0.1，故有α₁=0.1。此時可選擇剪枝規模較小的結點，對t₃進行剪枝，得到圖3-18a所示子樹，記為T₁。

令k=k+1，T=T_k，α_k=1/10，對圖3-18a中決策樹繼續剪枝，不難得出此時α（t₂）的取值0.1為最小，故有α₂=0.1。剪掉t₂得到圖3-18b所示子樹，記為T₂。

令k=k+1，T=T_k，α_k=1/10，此時決策樹只包含一個根結點t₁，可算出α（t₁）=0.2，故有α₃=0.2。

將未經剪枝的決策樹記為T₀，則可得到T₀，T₁，T₂三棵子樹，使用表3-16中測試集分別測試三棵子樹的性能，得到子樹T₀，T₁，T₂的預測錯誤率分別為

E（T₀）=1/3，E（T₁）=1/2，E（T₂）=1/3

由于子樹T₀與T₂在測試集上的預測錯誤率并列最小，但T₂的結構較為簡單，故選擇圖3-18b所示子樹T₂作為所求決策樹模型。□

圖3-18 剪枝后的決策樹