樹模型是最常見的機器學習方法之一，也是入門機器學習必須掌握的基礎。
樹模型通常分為分類樹和回歸樹。
在分類樹中，即主要針對目標變量是離散變量（一般為二元變量）的情形，樹模型的普遍使用是源於其構造方法成熟且相對簡單，易於從概念上理解。一棵樹的構建可以簡單理解為多個判斷規則的多路徑分類，根據單個樣本分到其中一類。從數據的分類規則上看，樹模型可以理解為一系列if-then-else組合；從統計學上理解，樹模型可以看成是在特徵組合空間與類別之間的條件概率分布。
回歸樹是針對目標變量是連續型的情況。
本章主要先闡述決策樹的定義，然後對如何構建一棵樹展開詳細介紹，主要針對特徵選擇，針對決策樹過擬合問題講解決樹的剪枝，最後介紹對連續變量和缺失值的處理。
樹模型在樹的構建上，分類樹主要是二分類樹，它是最常見和應用最廣泛的。首先我們從數據結構上認識樹。
樹結構樹（tree）的數據結構是由n（n≥0）個有限結點組成的一個具有層次關係的集合。把它叫作「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根在上而葉朝下的。
樹是包含n（n≥0）個結點的有窮集，樹中的每個元素稱為結點（node）；最頂層的叫作根結點或樹根（root）。
除根結點之外的其餘元素被分為m（m≥0）個互不相交的集合T1，T2，…，Tm-1，其中每一個集合Ti（1≤i≤m）本身也是一棵樹，被稱作原樹的子樹（subtree）。
樹結構的常見概念：
結點的度：某結點的度定義為該結點子結點的個數。案例中根結點A的度是3，結點E的度是2。葉子結點：度為0的結點，即案例中的J、K、L結點。樹的度：一棵樹中，最大結點的度稱為樹的度。案例樹的度為3，樹的度大於2是多叉樹。如果樹的度最大為2則為二叉樹。結點的高度：從該結點起到葉子結點的最長無重複邊的路徑的邊數。D結點高度為2。結點的層數：從根開始定義起，根為第1層，根的子結點為第2層，以此類推。結點B的層數為2，結點L的層數為4。結點的層數被稱為結點的深度。樹的層數：根結點的層數。案例樹的層數為4。樹的層數被稱為樹的深度。從樹結構的概念可以得出樹結構結點數和層級的關係大體如下：樹總結點數等於所有結點的度數加1；度為n的樹中，根結點是第1層，則第i層上最多有n(i-1)個結點。決策樹樹結構是一種常見的決策方式。在日常生活中應用很廣泛。在決策的過程中，把影響該事件的過程進行層層拆解，將最重要的因素排在前面，層層決策，最後得到結論。整個過程會依賴於人的經驗，而在機器學習的決策樹進行決策的過程中，會把之前的經驗進行量化處理，以最終目標為導向（目標函數），利用一定的規則（熵、基尼係數以及均方誤差等）篩選特徵，構建一組簡單而有效的決策規則。
機器學習中把構建的樹稱為決策樹（Decision Tree）。單棵樹是由結點和有向邊組成，結點分為根結點、分裂結點和葉子結點。
分裂結點又稱內部結點，表示模型中的特徵分裂條件，葉子結點表示最終的結論。
決策樹的結構簡單、直觀，其決策思想自上而下，分而治之。如下是一個簡單的決策樹示意圖。
從圖中可以很直觀地看出某個樣本/決策是因為哪個特徵而分裂，最後流向了哪個葉子結點。
在分裂結點的內部，包含經過計算出來的閾值。很明顯樹模型是一系列的if-then-else組合，進而構建一條直觀的路徑，並且每個樣本有且只有一種路徑，所以該決策路徑（決策規則）相互之間是互斥且完備的。
再進一步看，後面的分割是在前面的決策基礎上進行的，即後面的決策依賴於前面的決策，從這個角度看，決策樹是基於特定特徵下的條件概率分布，單個樣本的類別是依賴於前面特徵的切分，在每次進行特徵切分時，都將樣本劃分為互斥且完備的空間，決策樹的一個路徑決定了一個劃分單元，從而決定最終的類別。
決策樹的目標函數通常是正則化的極大似然函數，決策樹的學習策略是最小化目標函數
如果決策樹的目標變量是離散變量，則稱它為分類樹（Classification Tree）；如果目標變量是連續變量，則稱它為回歸樹（Regression Tree）。scikit-learn已經有現成的API接口：
分類樹sklearn.tree.DecisionTreeClassifier使用的特徵分裂指標是熵和基尼指數，對應配置參數criterion{「gini」，「entropy」}，默認值為「gini」，熵和基尼指數在3.1節進行介紹。回歸樹sklearn.tree.DecisionTreeRegressor使用特徵分裂指標是均方誤差和平均絕對誤差，對應配置參數criterion{「mse」，「friedman_mse」，「mae」}，默認值為「mse」決策樹算法構建決策樹常見算法的有3種：ID3、C4.5以及CART。這3種算法是機器學習中的經典算法，本節將針對這3種不同的算法的特徵選擇過程、決策樹的生成細節進行逐步展開。決策樹的構造核心在於如何分支，即如何選取最優的特徵和劃分點依據，需要一個統一的指標（信息量）。
熵和基尼指數構建一棵樹的基礎是挑選出最有用的特徵——特徵選擇。特徵選擇的依據是特徵的貢獻度。ID3、C4.5以及CART分類樹挑選特徵的依據是使用熵和基尼指數。
熵熵（entropy）是由資訊理論之父克勞德-香農（Claude Elwood Shannon）在1948年提出的概念。
在資訊理論中，熵用來度量隨機變量的不確定性。一個系統越有序，熵越小；系統越混亂，則熵越大，所以說熵是用來衡量一個系統的有序程度。
在機器學習中，變量的不確定越大，熵越大。假設隨機變量可能的取值為x1,x2,…xn，其概率分布如下所示：
此時隨機變量X的熵定義為：
log函數通常是以2為底或者以自然對數e為底。熵的大小與X的取值無關，只依賴X的分布。對於樣本集合D來說，隨機變量X是樣本的類別，假設樣本中有k個類別，對於樣本集合D的經驗熵為：
對於隨機變量只有兩個取值的情況下，假如分類變量中只有0和1的取值，熵可以簡化為：
在二分類問題中，熵和概率的關係會呈現一個倒U曲線，熵隨著p值先增大，後縮小，在p等於0.5時，熵達到最大值。
基尼指數基尼指數（GINI）最初是用於經濟學，用來衡量收入分配公平的程度。基尼指數越大，代表貧富差距越大，反之則差距越小。
在機器學習中的含義和經濟學中相似：基尼指數越大，樣本集合的不確定性越大。
在二分類問題中，用基尼指數衡量變量的重要程度。基尼指數也稱為基尼不純度，表示樣本集合中一個隨機選中的樣本被分錯的概率。
基尼指數越小表示被分錯的概率越小，即集合的純度越高；反之，集合越不純。
全體集合的基尼指數：在二分類問題中，基尼指數的計算非常簡單。若樣本屬於正類的概率為p，此時概率分布的基尼指數為如下：
GINI指數的求解方式相對簡單，計算耗時少，並且易於理解。
ID3算法ID3算法是20個世紀80年代Quinlan對其算法原理進行總結並提出的，是決策樹最初期的一種理論和方法。其算法核心是利用各個結點上的信息增益選擇特徵，構建決策樹。
主要實現過程是：從根結點開始，計算各特徵的信息增益，選擇信息增益最大的特徵作為分裂結點，完成一層分割之後，產生新的結點，再在新的結點上重複上述方法。
ID3的求解過程就是計算特徵上的信息增益。信息增益是計算某特徵分割前後的熵差。差值越大，說明不純度減少越多，該特徵則越有用。給定數據集D和特徵A，定義信息增益g(D，A)為：
H(D)代表未經過分割之前的信息熵，即對整個數據集進行分類的不確定性，H(D|A)稱為條件經驗熵，代表在特徵A已知的情況下，對數據集進行分類的不確定性；它們的差值即代表信息增益，表示因為特徵A而使得不確定性減少的程度。
在工程中，具體的實現方式是使用所有的特徵對樣本集進行切分，從這些特徵中選取信息增益最大的。
在構建樹的過程中，越簡單的樹越好，因此會有限選擇最有用的特徵以求更快達到更高純度的集合，這裡的「更快速」和優化算法中的梯度算法是一個原理。
ID3用到的特徵選擇方法是信息增益，計算比較簡單，但ID3的局限性在於：
整棵樹是完全生長的，沒有進行剪枝操作，因此很容易過擬合；容易選擇取值較多的特徵，當某個特徵的取值越多，該特徵的信息增益偏大C4.5算法C4.5算法是在ID3算法上的一個改進。針對ID3算法會傾向於選擇包含可能值比較多的特徵。C4.5採用信息增益率（information gain ratio）來代替信息增益。把原來的絕對增量轉換為相對增量，一定程度上避免了由於特徵取值較多而被選中。信息增益率的計算公式為：
信息增益的本質是在信息增益的計算過程中加入了一個懲罰係數，當特徵取值個數越多時，分母的值越大；反之分母的值越小。
根據經驗上取值越大，分母會越大，這樣對因為特徵個數而導致信息增益變大的特徵進行了懲罰。
C4.5相對於ID3進行了如下優化：
使用信息增益率來代替信息增益，一定程度上避免了由於特徵取值較多而被選中。C4.5也有局限性如下：
採用的悲觀剪枝是從上而下的剪枝策略，這種剪枝策略會導致和預剪枝同樣的問題，可能會造成過度剪枝；需要計算熵，裡面有大量的對數運算,如果特徵是連續值則還有大量的排序運算，計算比較耗時。CARTCART（Classification And Regression Tree）由Breiman等人在1984年提出，表示分類和回歸樹，是目前機器學習算法樹模型中應用最廣泛的一種。從名稱中可以看出，CART樹既可用於分類，也可用於回歸。在CART樹的構建過程中，內部結點分成二叉樹（前面兩種算法可能產生多叉樹）。
CART分類樹在CART的分類樹中，特徵選擇會使用基尼指數。在特徵選擇的過程中，不僅會選出最優的切分特徵，也會確定最優特徵的最佳切分點。基尼指數越小，代表不確定越小，特徵越有效。條件基尼指數：在一個總量為D的樣本集中，根據特徵A是否可以取某值m，可將D劃分為D1和D2，此時在特徵A的條件下，集合D的基尼指數為：
CART分類樹與C4.5相比，C4.5是多叉樹且需要進行大量耗時的對數運算，CART分類樹計算速度更快。
CART回歸樹CART回歸樹和分類樹的區別在於目標變量是連續的，在生成樹的過程中，選取特徵的準則也不一樣，採取均方誤差（而不是基尼係數）。對於給定的數據集D = {(
在平方誤差最小的基礎上求解每個單元的最優輸出值。在回歸樹的輸入空間進行劃分時，會對所有變量的所有值進行遍歷嘗試，以此尋找當前最優的切分變量j和最優切分點s。問題最終轉化成求解如式：
在上式中，
樹的剪枝決策樹的生成過程要使用遞歸算法。完全生長的決策樹的學習是很充分的，但是對於未知的數據預測效果一般會很差，即出現了過擬合現象。過擬合的原因是在於學習的過程中過多學習了訓練集的信息。通常可利用剪枝來降低樹的複雜度，提高樹對未知數據的泛化能力。決策樹剪枝方法可分為兩類：預剪枝和後剪枝。
預剪枝預剪枝是指在決策樹的生成過程中，在結點劃分前進行評估判斷。若當前結點已經滿足截止條件或劃分後不能帶來性能的提升，則停止劃分並將當前結點標記為葉子結點。預剪枝常見的策略如下所示：
樹的最大深度：如果某個結點的深度已經達到預先設定的樹的最大深度，那麼就停止分支, 該結點被設定為葉結點；葉子最小樣本數量：一般來說， 葉結點的樣本量越多，泛化越強，反之越容易過擬合。限制葉結點的最小樣本量有助於提升決策樹的泛化能力，如果當前結點樣本量已經低於預先設定的閾值，那麼停止分支；純度準則：分支過程若導致結點上不斷地降低Gini不純度/熵/結點內方差等，說明純度一直在改進。達到特定的純度即可停止分支。在實際的建模工作中，預剪枝的截止條件閾值在配置時需要選擇合適的參數，如果參數配置的不當，可能會產生欠擬合或過擬合。參數閾值選擇可參考本書的模型調參章節，選擇適合當前模型項目的參數閾值才能使模型的訓練預測效果和泛化能力達到較好的水準。
後剪枝後剪枝是先等訓練集生成的決策樹長成後，對樹進行剪枝得到簡化版的決策樹。後剪枝的剪枝過程是刪除一些子樹，然後用其葉子結點代替，這個葉子結點所標識的類別通過多數表決法決定。
常見的後剪枝方法的主要分為3種方法：
錯誤率降低剪枝（Reduced-Error Pruning，REP）悲觀剪枝（Pesimistic-Error Pruning，PEP）代價複雜度剪枝（Cost-Complexity Pruning，CCP）第3節介紹的3種決策樹算法中，C4.5算法基於悲觀策略剪枝，CART算法是代價複雜度策略剪枝，ID3算法沒有使用後剪枝策略。
1.錯誤率降低剪枝REP
REP方法考慮將樹上的每個結點作為修剪的候選對象，對於完全決策樹中的每一個非葉子結點的子樹，嘗試著把它替換成一個葉子結點，然後比較替換前後兩棵決策樹在測試數據集中的表現，如果替換後的決策樹在測試數據集中的錯誤比較少(小於等於），那麼該子樹就可以被替換成葉子結點。該算法以自底向上的方式遍歷所有的子樹，直至沒有任何子樹可以替換使得測試數據集的表現得以改進時，算法就可以終止。2.悲觀剪枝PEP
PEP方法是了克服 REP 方法缺點而提出的，它不需要分離的剪枝數據集。PEP是根據剪枝前後的錯誤率來判定子樹的修剪。該方法引入了統計學上連續修正的概念彌補REP中的缺陷。PEP算法實用的從上而下的剪枝策略，這種剪枝方法會導致剪枝過度。。3.代價複雜度剪枝CCP
CCP方法會生成一系列樹，每個樹都是通過將前面的樹的某個或某些子樹替換成一個葉節點而得到的，這一系列樹中的最後一棵樹僅含一個用來預測類別的葉節點。然後用一種成本複雜度的度量參數α來判斷哪棵子樹應該被一個預測類別值的葉節點所代替。這種方法需要使用一個單獨的測試數據集來評估所有的樹，根據它們在測試數據集熵的分類性能選出最佳的樹。特徵處理決策樹算法案例都是基於離散數據講解的，決策樹生成方式對於離散數據是非常容易處理的。而連續屬性的可取值數目不再有限，因此不能像前面處理離散屬性枚舉離散屬性取值來對結點進行劃分。本節主要講解決策樹對於連續值以及缺失值的處理。
連續值處理對連續值的處理其實就是離散化，常用的離散化策略是二分法。這個方法是C4.5和CART中採用的策略，只是兩者選擇劃分點的衡量標準不一樣：C4.5使用信息增益率，CART使用基尼指數或平方誤差。對於連續屬性a，我們可考察包含m−1個元素的候選劃分集合如下：
即把區間[
缺失值處理在決策樹中是如何處理屬性值有缺失值的呢？可以從如下3個方面來考慮。
（1）訓練生成決策樹，在選擇分裂屬性的時候，訓練樣本存在缺失值，如何處理？
計算分裂損失減少值時，忽略特徵缺失的樣本，最終計算的值乘以比例（實際參與計算的樣本數除以總的樣本數）。假設20個樣本，屬性是a。在計算a屬性熵時發現，第20個樣本的a屬性缺失，那麼就把第20個樣本去掉，用其餘的19個樣本組成新的樣本集，在新樣本集上按正常方法計算a屬性的信息增益。然後將結果乘0.95（新樣本佔原樣本的比例），即可得到a屬性最終的信息增益。（2）訓練生成決策樹時，給定劃分屬性，訓練樣本屬性存在缺失該何處理？
將該樣本分配到所有子結點中，權重由1變為具有屬性a的樣本被劃分成的子集樣本個數的相對比率，計算錯誤率的時候，需要考慮樣本權重。（3）決策樹模型訓練完成，需要測試集樣本測試模型效果，測試樣本有缺失值該如何處理？
把待分類的樣本的屬性a值分配一個最常出現的a的屬性值，然後進行分支預測。在決策樹中屬性a結點的分支上，遍歷屬性a結點的所有分支，探索可能所有的分類結果，然後把這些分類結果結合起來一起考慮，按照概率決定一個分類。待分類樣本在到達屬性a結點時就終止分類，然後根據此時a結點所覆蓋的葉子結點類別狀況為其分配一個發生概率最高的類。