決策樹(decision tree) 是一種基本的分類與回歸方法.本章主要讨論 用于分類的決策樹。決策樹模型呈樹形結構，在分類問題中，表示基于特征對執行個體進行分類的過程。它可以認為 是 i f − t h e n 是if-then 是if−then規則的集合，也可以認為是定義在特征空間與類空間上的條件機率分布。其主要優點是模型具有可讀性，分類速度快。學習時，利用訓練資料，根據損失函數最小化的原則建立決策樹模型。預測時，對新的資料，利用決策樹模型進行分類。決策樹學習通常包括3個步驟：特征選擇、決策樹的生成和決策樹的修剪。這些決策樹學習的思想主要來源于由Quinlan在1986年提出的 ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART算法。本章首先介紹決策樹的基本概念，然後通過ID3和C4.5介紹特征的選擇、決策樹的生成以及決策樹的修剪，最後介紹CART算法.
一.決策樹模型與學習
1.1 決策樹模型
定義5.1 (決策樹) 分類決策樹模型 是一種描述對執行個體進行分類的樹形結構。決策樹由 結點(node) 和有向邊(directed edge) 組成.結點有兩種類型：内部結點(intermnal node)和葉結點(leaf node)。 内部結點表示一個特征或屬性，葉結點表示一個類.
用決策樹分類，從根結點開始，對執行個體的某一特征進行測試，根據測試結果，将執行個體配置設定到其子結點；這時，每一個子結點對應着該特征的一個取值。如此遞歸地對執行個體進行測試并配置設定，直至達到葉結點。最後将執行個體分到葉結點的類中。
圖5.1是一個決策樹的示意圖。圖中圓和方框分别表示内部結點和葉結點.
1.2 決策樹與 if-then 規則
可以将決策樹看成一個 i f − t h e n if-then if−then規則的集合。将決策樹轉換成 i f − t h e n if-then if−then規則的過程是這樣的：由決策樹的根結點到葉結點的每一條路徑建構一 條規則；路徑上内部結點的特征對應着規則的條件，而葉結點的類對應着規則的結論。決策樹的路徑或其對應的 i f − t h e n if-then if−then規則集合具有一個重要的性質：互斥并且完備。這就是說，每一個執行個體都被一條路徑或一條規則所覆寫，而且隻被一條路徑或一條規則所覆寫。這裡所謂覆寫是指執行個體的特征與路徑上的特征一緻或執行個體滿足規則的條件。
1.3 決策樹與條件機率分布
決策樹還表示給定特征條件下類的 條件機率分布。這一條件機率分布定義在特征空間的一個劃分(partition) 上.。将特征空間劃分為互不相交的單元(cel)或區域(region)，并在每個單元定義一個類的機率分布就構成了一個條件機率分布，決策樹的一條路徑對應于劃分中的一個單元，決策樹所表示的條件機率分布由各個單元給定條件下類的條件機率分布組成。假設X為表示特征的随機變量, Y為表示類的随機變量，那麼這個條件機率分布可以表示為 P ( Y ∣ X )，X取值于給定劃分下單元的集合， Y取值于類的集合，各葉結點(單元)上的條件機率往往偏向某一個類，即屬于某一類的機率較大。 決策樹分類時将該結點的執行個體強行分到條件機率大的那一類去.
圖 5.2 (a) 示意地表示了特征空間的一個劃分。圖中的大正方形表示特征空間。這個大正方形被若幹個小矩形分割，每個小矩形表示一個單元特征空間劃分上的單元構成了一個集合， x取值為單元的集合，為簡單起見，假設隻有兩類：正類和負類，即 Y取值為 + 1和 -1 。小矩形中的數字表示單元的類，圖 5.2 (b) 示意地表示特征空間劃分确定時，特征(單元)給定條件下類的條件機率分布。圖 5.2 (b) 中條件機率分布對應于圖 5.2 (a) 的劃分.當某個單元 c 的條件機率滿足 P(Y=+1|X =c)> 0.5 時，則認為這個單元屬于正類，即落在這個單元的執行個體都被視為正例.圖 5.2 © 為對應于圖5.2 (b)中條件機率分布的決策樹.
1.4 決策樹的學習
決策樹學習，假設給定訓練資料集
其中，
為輸入執行個體(特征向量，n 為特征個數， yi∈{1,2,⋯,K} 為類标記， i = 1 , 2 , ⋯ , N， N為樣本容量。學習的目标是根據給定的訓練資料集建構一個決策樹模型，使它能夠對執行個體進行正确的分類。
決策樹學習的政策是以損失函數為目标函數，然後求取其最小化的過程，如下所述,決策樹學習的損失函數通常是正則化的極大似然函數。
當損失函數确定以後，學習問題就變為在損失函數意義下選擇最優決策樹的問題.因為從所有可能的決策樹中選取最優決策樹是 NP完全問題，是以現實中決策樹學習算法通常采用啟發式方法，近似求解這一最優化問題.這樣得到的決策樹是次最優( sub-optimal)的.
決策樹學習的算法通常是一個遞歸地選擇最優特征，并根據該特征對訓練資料進行分割，使得對各個子資料集有一個最好的分類的過程。這一過程對應着對特征空間的劃分，也對應着決策樹的建構。開始，建構根結點，将所有訓練資料都放在根結點，選擇一個最優特征，按照這一特征将訓練資料集分割成子集，使得各個子集有一個在目前條件下最好的分類。如果這些子集已經能夠被基本正确分類，那麼建構葉結點，并将這些子集分到所對應的葉結點中去：如果還有子集不能被基本正确分類,那麼就對這些子集選擇新的最優特征，繼續對其進行分割，建構相應的結點。如此遞歸地進行下去,直至所有訓練資料子集被基本正确分類,或者沒有合适的特征為止。 最後每個子集都被分到葉結點上，即都有了明确的類.這就生成了一棵決策樹.
二.特征選擇
特征選擇在于選取對訓練資料具有分類能力的特征。這樣可以提高決策樹學習的效率，如果利用一個特征進行分類的結果與随機分類的結果沒有很大差别，則稱這個特征是沒有分類能力的。經驗上扔掉這樣的特征對決策樹學習的精度影響不大。通常特征選擇的準則是 資訊增益或資訊增益比。
例表5.1 是一個由 15 個樣本組成的貸款申請訓練資料。資料包括貸款申請人的 4 個特征(屬性)：第 1 個特征是年齡，有 3 個可能值：青年，中年，老年；第 2 個特征是有工作，有 2 個可能值：是，否；第 3 個特征是有自己的房子，有 2 個可能值：是，否；第 4 個特征是信貸情況，有 3 個可能值：非常好，好，一般。表的最後一列是類别，是否同意貸款，取2個值：是，否。
希望通過所給的訓練資料學習一個貸款申請的決策樹，用以對未來的貸款申請進行分類，即當新的客戶提出貸款申請時，根據申請人的特征利用決策樹決定是否準許貸款申請。
圖5.3 表示從表5.1 資料學習到的兩個可能的決策樹，分别由兩個不同特征的根結點構成。圖5.3 (a)所示的根結點的特征是年齡，有3個取值，對應于不同的取值有不同的子結點。圖5.3 (b)所示的根結點的特征是有工作，有2個取值，對應于不同的取值有不同的子結點。兩個決策樹都可以從此延續下去，問題是：究竟選擇哪個特征更好些? 這就要求确定 選擇特征的準則。直覺上，如果一個特征具有更好的分類能力，或者說，按照這一特征将訓練資料集分割成子集，使得各個子集在目前條件下有最好的分類，那麼就更應該選擇這個特征。資訊增益(information gain) 就能夠很好地表示這一直覺的準則.
2.1 資訊增益
為了便于說明，先給出 熵與條件熵的定義.在資訊論與機率統計中，熵(entropy) 是表示随機變量不确定性的度量。熵值越大，則随機變量的不确定性越高，設 x x x 是一個取有限個值的離散随機變量，其機率分布為
則随機變量 X的熵定義為
在上式中，若 p i = 0, 則定義 0log0=0。通常，上式中的對數以 2 為底或以 e 為底(自然對數)，這是熵的機關分别稱作比特（bit） 或納特（nat）。由定義可知，熵隻依賴X的分布，而與X的取值無關，是以也可将X的熵記作H(p)，即
熵越大，随機變量的不确定性就越大。從定義可驗證
當随機變量隻取兩個值，例如1，0時，即X的分布為
熵為
這時，熵 H(p) 随機率 p 變化的曲線如圖5.4所示(機關為比特).
當 p = 0 或 p = 1 時 H ( p ) = 0 ，随機變量完全沒有不确定性。當 p=0.5時，H(p)=1,熵取值最大，随機變量不确定性最大.
設有随機變量 ( X , Y )，其聯合機率分布為
條件熵 H(Y∣X)表示在已知随機變量 X的條件下随機變量 Y的不确定性。随機變量 X給定的條件下随機變量 Y的條件(conditional entropy) H(Y∣X)，定義為 X給定條件下 Y的條件機率分布的熵對 X 的數學期望
這裡，
當熵和條件熵中的機率由資料估計(特别是極大似然估計)得到時，所對應的熵與條件熵分别稱為 經驗(empiricalentropy)熵和經驗條件熵(empiricalconditional entropy)。此時，如果有0機率，令 0log0=0。資訊增益(informationgain)表示得知特征X的資訊而使得類Y的資訊的不确定性減少的程度.
定義5.2（資訊增益）
特征 A對訓練資料集 D 的資訊增益 g(D,A)，定義為集合 D的經驗熵 H(D)與特征 A給定條件下D的經驗條件熵H(D∣A)之差，即
一般地, 熵 H(Y)與條件熵 H(Y∣x)之差稱為 互資訊(mutual information)。決策樹學習中的資訊增益等價于訓練資料集中類與特征的互資訊.
決策樹學習應用資訊增益準則選擇特征。給定訓練資料集D和特征A,經驗熵 H(D)表示對資料集 D進行分類的不确定性。而經驗條件熵H(D∣A)表示在特征A給定的條件下對資料集D進行分類的不确定性。那麼它們的差,即 資訊增益，就表示由于特征A而使得對資料集D的分類的不确定性減少的程度。顯然，對于資料集D而言，資訊增益依賴于特征，不同的特征往往具有不同的資訊增益。資訊增益大的特征具有更強的分類能力.
根據資訊增益準則的特征選擇方法是：對訓練資料集(或子集) D,計算其每個特征的資訊增益，并比較它們的大小，選擇資訊增益最大的特征。
設訓練資料集為 D，∣D∣ 表示其樣本容量，即樣本個數。設有 K 個類 Ck, k=1,2,⋯,K, ∣Ck∣ 為屬于類Ck 的樣本個數，
設特征 A 有 n個不同的取值 { a 1 , a 2 , ⋯ , a n },根據特征 A 的取值将 D 劃分為 n 個子集 D1,D2,⋯,Dn，∣Di∣ 為 Di 樣本個數，
記子集 Di 中屬于類 Ck的樣本的集合為 Dik，即，|Dk |為Dk的樣本個數.于是資訊增益的算法如下:
算法 5.1（資訊增益算法）
輸入：訓練資料集 D和特征A;
輸出：特征 A對訓練資料集 D的資訊增益 g(D,A)
2.2 例題：利用資訊增益求解問題
例5.2 對表 5.1 所給的訓練資料集 D，根據資訊增益準則選擇最優特征
（4）
最後，比較各特征的資訊增益值.由于特征 A3 (有自己的房子)的資訊增益值最大，是以選擇特征 A3 作為最優特征.
2.3 資訊增益比
資訊增益值的大小是相對于訓練資料集而言的，并沒有絕對意義。在分類問題困難時，也就是說在訓練資料集的經驗熵大的時候，資訊增益值會偏。反之，資訊增益值會偏小。使用 資訊增益比(infornation gain ratio) 可以對這一問題進行校正，這是特征選擇的另一準則.
定義5.3（資訊增益比） 特征A 對訓練資料集 D 的資訊增益比 gR(D,A) 定義為其資訊增益 g(D,A) 與訓練資料集 D 的經驗熵 H(D) 之比:
三.決策樹的生成
本節将介紹決策樹學習的生成算法。首先介紹 ID3 的生成算法，然後再介紹C4.5中的生成算法，這些都是決策樹學習的經典算法.
3.1 ID3算法
ID3算法的核心是在決策樹各個結點上應用資訊增益準則選擇特征，遞歸地建構決策樹。具體方法是：從根結點(root node)開始，對結點計算所有可能的特征的資訊增益，選擇資訊增益最大的特征作為結點的特征，由該特征的不同取值建立子結點：再對子結點遞歸地調用以上方法，建構決策樹；直到所有特征的資訊增益均很小或沒有特征可以選擇為止.最後得到一個決策樹. ID3 相當于用極大似然法進行機率模型的選擇.
算法 5.2（ID3算法）
3.2 例題：利用ID3算法建立決策樹
例 5.3 對 表5.1 的訓練資料集， 利用ID3算法建立決策樹
3.3 C4.5算法
四.決策樹的剪枝
決策樹生成算法遞歸地産生決策樹，直到不能繼續下去為止。這樣産生的樹往往對訓練資料的分類很準确，但對未知的測試資料的分類卻沒有那麼準确，即出現 過拟合現象。過拟合的原因在于學習時過多地考慮如何提高對訓練資料的正确分類，進而 建構出過于複雜的決策樹。解決這個問題的辦法是考慮決策樹的複雜度，對已生成的決策樹進行 簡化。
在決策樹學習中 将已生成的樹進行簡化的過程稱為剪枝(pruning)。具體地，剪枝從已生成的樹上裁掉一些子樹或葉結點, 并将其根結點或父結點作為新的葉結點，進而簡化分類樹模型.
本節介紹一種簡單的決策樹學習的剪枝算法。
決策樹的剪枝往往通過 極小化決策樹整體的損失函數(loss function)或代價函數(cost function) 來實作。設樹 T的葉結點個數為 ∣T∣, t 是樹 T 的葉結點，該葉子節點上有Nt 個樣本點，其中 k 類的樣本點有 Ntk 個， k=1,2,⋯,K，Ht(T) 為葉節點 t 上的經驗熵， α≥0為參數，則決策樹學習的損失函數可以定義為
其中經驗熵為
在損失函數中，将式 (5.11) 右端的第 1 項記作
這時有
式 (5.14) 中， C(T) 表示模型對 訓練資料的預測誤差，即模型與訓練資料的拟合程度， ∣T∣表示 模型複雜度，參數a≥0 控制兩者之間的影響。較大的 a 促使選擇較簡單的模型（樹）， 較小的 a 促使選擇較複雜的模型(樹)。 a=0 意味着隻考慮模型與訓練資料的拟合程度，不考慮模型的複雜度.
剪枝，就是當 a 确定時，選擇損失函數最小的模型，即損失函數最小的子樹。當 a 值确定時，子樹越大，往往與訓練資料的拟合越好，但是模型的複雜度就越高；相反，子樹越小，模型的複雜度就越低，但是往往與訓練資料的拟合不好。損失函數正好表示了對兩者的平衡.
可以看出，決策樹生成隻考慮了通過提高資訊增益(或資訊增益比)對訓練資料進行更好的拟合。而決策樹剪枝通過優化損失函數還考慮了減小模型複雜度。決策樹生成學習局部的模型，而決策樹剪枝學習整體的模型。式 (5.11) 或式 (5.14) 定義的損失函數的極小化等價于 正則化的極大似然估計。是以，利用損失函數最小原則進行剪枝就是用正則化的極大似然估計進行模型選擇.
圖5.6 是決策樹剪枝過程的示意圖，下面介紹剪枝算法。
4.1 剪枝算法
五.CART樹
分類與回歸樹(lassification and regression tree, CART)模型由Breiman等人在1984 年提出，是應用廣泛的決策樹學習方法.。CART同樣由特征選擇、樹的生成及剪枝組成，既可以用于分類也可以用于回歸。以下将用于分類與回歸的樹統稱為決策樹.
CART是在給定輸入随機變量 X 條件下輸出随機變量 Y 的 條件機率分布 的學習方法。CART假設決策樹是二叉樹，内部結點特征的取值為 “是”和“否”**，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價于遞歸地二分每個特征，将輸入空間即特征空間劃分為有限個單元，并在這些單元上确定預測的機率分布，也就是在輸入給定的條件下輸出的條件機率分布.
決策樹的生成就是遞歸地建構二叉決策樹的過程。對回歸樹用平方誤差最小化準則，對分類樹用基尼指數(Gini index)最小化準則，進行特征選擇生成二叉樹.
5.1 CART回歸樹生成
假設 X 與 Y 分别為輸入和輸出變量，并且 Y 是連續變量，給定訓練資料集
考慮如何生成回歸樹。一個回歸樹對應着輸入空間(即特征空間)的一個劃分以及在劃分的單元上的輸出值。假設已将輸入空間劃分為 M 個單元 R1,R2,⋯,RM 并且在每個單元Rm上有一個固定的輸出值 cm，于是回歸樹模型可表示為
當輸入空間的劃分确定時,可以用平方誤差
來表示回歸樹對于訓練資料的預測誤差，用平方誤差最小的準則求解每個單元上的最優輸出值。易知，單元 Rm 上的 cm的最優值 cm^ 是 Rm 上的所有輸入執行個體xi 對應的輸出 yi 的均值，即
問題是怎樣對輸入空間進行劃分，這裡采用 啟發式的方法，選擇第 j 個變量x(j)和它取的值 s，作為 切分變量(spliting variable) 和 切分點(spliting point),并定義兩個區域：
然後 尋找最優切分變量 j 和最優切分點 s。具體地，求解
對固定輸入變量 j 可以找到最優切分點 s
周遊所有輸入變量，找到最優的切分變量 j，構成一個對 (j,s)。依此将輸入空間劃分為兩個區域.接着，對每個區域重複上述劃分過程，直到滿足停止條件為止。這樣就生成一棵回歸樹.。這樣的回歸樹通常稱為最小二乘回歸樹(least squaresregression tree)，現将算法叙述如下:
5.2 CART分類樹生成
分類樹用 基尼指數選擇最優特征，同時決定該特征的最優二值切分點。
定義5.4 (基尼指數)
分類問題中， 假設有 K個類，樣本點屬于第 k 類的機率為 Pk，則機率分布的基尼指數定義為
對于二類分類問題，若樣本點屬于第1個類的機率是 p，則機率分布的基尼指數為
對于給定的樣本集合D,其基尼指數為
這裡， Ck 是 D 中屬于第 k 類的樣本子集，K 是類的個數
如果樣本集合 D 根據特征 A 是否取某一可能值a 被分割成D1和 D2兩部分，即
則在特征 A 的條件下，集合D 的基尼指數定義為
基尼指數 Gini(D) 表示集合D的不确定性，基尼指數 Gini(D,A)表示經 A=a 分割後集合 D 的不确定性。基尼指數值越大，樣本集合的不确定性也就越大，這一點與熵相似。
圖5.7顯示二類分類問題中基尼指數 Gini(p)、熵（機關比特）之半
和分類誤差率的關系，橫坐标表示機率p，縱坐标表示損失。可以看出 基尼指數和熵之半的曲線很接近，都可以近似地代表分類誤差率.
5.3 例題：應用CART算法生成決策樹
例：根據 表5.1 所給訓練資料集，應用CART算法生成決策樹.