（四）決策樹 Decision Tree
基本概念
決策樹(Decision Tree）是在已知各種情況發生機率的基礎上，通過構成決策樹來求取淨現值的期望值大于等于零的機率，評價項目風險，判斷其可行性的決策分析方法，是直覺運用機率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝幹，故稱決策樹。
機器學習中，決策樹是一個預測模型；他代表的是對象屬性與對象值之間的一種映射關系。樹中每個節點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結點則對應從根節點到該葉節點所經曆的路徑所表示的對象的值。
決策樹僅有單一輸出，若欲有複數輸出，可以建立獨立的決策樹以處理不同輸出。資料挖掘中決策樹是一種經常要用到的技術，可以用于分析資料，同樣也可以用來作預測。簡而言之，決策樹(decision tree)是一種基本的分類與回歸方法。
在分類問題中，表示基于特征對執行個體進行分類的過程。它可以被認為是if-then規則的集合，也可以認為是定義在特征空間與類空間上的條件機率分布。其主要有點是模型具有可讀性，分類速度快。學習時，利用訓練資料，根據損失函數最小化的原則建立決策樹模型。預測時，對新的資料，利用決策書模型進行分類。
從資料産生決策樹的機器學習技術叫做決策樹學習。決策樹學習通常包括3個步驟：特征選擇、決策樹的生成和修剪。
決策樹算法分類
| 決策樹算法 | 算法描述 |
| ID3算法 | 其核心是在決策樹的各級節點上，使用資訊增益方法作為屬性的選擇标準，來幫助确定生成每個節點時所應采用的合适屬性 |
| C4.5算法 | C4.5決策樹生成算法是機器學習算法中的一種分類決策樹算法，其核心算法是ID3算法。 C4.5算法繼承了ID3算法的優點，并在以下幾方面對ID3算法進行了改進： （1）用資訊增益率來選擇屬性，克服了用資訊增益選擇屬性時偏向選擇取值多的屬性的不足； （2）在樹構造過程中進行剪枝； （3）能夠完成對連續屬性的離散化處理； （4）能夠對不完整資料進行處理。 C4.5算法有如下優點：産生的分類規則易于了解，準确率較高。其缺點是：在構造樹的過程中，需要對資料集進行多次的順序掃描和排序，因而導緻算法的低效。 |
| CART算法 | CART（ Classification And Regression Tree）即分類回歸樹算法，它是決策樹的一種實作。 CART算法是一種二分遞歸分割技術，把目前樣本劃分為兩個子樣本，使得生成的每個非葉子結點都有兩個分支，是以CART算法生成的決策樹是結構簡潔的二叉樹。由于CART算法構成的是一個二叉樹，它在每一步的決策時隻能為“是”或者“否”，即使一個feature有多個取值，也是把資料分為兩部分。在CART算法中主要分為兩個步驟： （1）決策樹生成：将樣本遞歸劃分進行建樹過程，生成的決策樹要盡量大； （2）決策樹剪枝：用驗證資料進行剪枝，這時損失函數最小作為剪枝的标準。 |
決策樹的優缺點
優點：計算複雜度不高，輸出結果易于了解，對中間值的缺失不敏感，可以處理不相關特征資料。
缺點：可能會産生過度比對問題。
适用資料類型：數值型和标稱型
在構造決策樹時，我們需要解決的第一個問題就是，目前資料集上哪個特征在劃分資料分類時起決定性作用。為了找到決定性的特征，劃分出最好的結果，我們必須評估每個特征。完成測試之後，原始資料集就被劃分為幾個資料子集。這些資料子集會分布在第一個決策點的所有分支上。如果某個分支下的資料屬于同一類型，則無需進一步對資料集進行分割。如果資料子集内的資料不屬于同一類型，則需要重複劃分資料子集的過程。劃分資料子集的算法和劃分原始資料集的方法相同，直到所有具有相同類型的資料均在一個資料子集内。
下面是在西瓜資料集2.0上基于資訊增益生成的決策樹。引用自 《機器學習》（周志華，清華大學出版社，P78）
分類決策樹模型是一種描述對執行個體進行分類的樹形結構。決策樹由結點（node）和有向邊（directed edge）組成。結點有兩種類型：内部節點（internal node）和葉節點（leaf node）. 内部節點表示一個特征或屬性，葉節點表示一個類。
用決策樹分類，從根節點開始，對執行個體的某一特征進行測試，根據測試結果，将執行個體配置設定到其子節點；這時，每一個子節點對應着該特征的一個取值。如此遞歸地對執行個體進行測試并配置設定，直至到達葉節點。最後将執行個體分到葉節點的類中。
決策樹與if-then規則
可以将決策樹看成一個if-then規則的集合。由決策樹的根節點到葉節點建構一條規則；内部節點的特征對應着規則的條件，而葉節點的類對應着規則的結論。
決策樹的路徑或其對應的if-then規則集合有一個重要的性質：互斥并且完備。這就是說，沒一個執行個體都被一條路徑或一條規則所覆寫，而且制備一條路徑或一條規則所覆寫。
決策樹的構造
使用決策樹做預測需要以下過程：
收集資料：可以使用任何方法。比如想建構一個相親系統，我們可以從媒婆那裡，或者通過參訪相親對象擷取資料。根據他們考慮的因素和最終的選擇結果，就可以得到一些供我們利用的資料了。
準備資料：收集完的資料，我們要進行整理，将這些所有收集的資訊按照一定規則整理出來，并排版，友善我們進行後續處理。
分析資料：可以使用任何方法，決策樹構造完成之後，我們可以檢查決策樹圖形是否符合預期。
訓練算法：這個過程也就是構造決策樹，同樣也可以說是決策樹學習，就是構造一個決策樹的資料結構。
測試算法：使用經驗樹計算錯誤率。當錯誤率達到了可接收範圍，這個決策樹就可以投放使用了。
使用算法：此步驟可以使用适用于任何監督學習算法，而使用決策樹可以更好地了解資料的内在含義。
決策樹學習的算法通常是一個遞歸地選擇最優特征，并根據該特征對訓練資料進行分割，使得各個子資料集有一個最好的分類的過程。這一過程對應着對特征空間的劃分，也對應着決策樹的建構。
1） 開始：建構根節點，将所有訓練資料都放在根節點，選擇一個最優特征，按着這一特征将訓練資料集分割成子集，使得各個子集有一個在目前條件下最好的分類。
2） 如果這些子集已經能夠被基本正确分類，那麼建構葉節點，并将這些子集分到所對應的葉節點去。
3）如果還有子集不能夠被正确的分類，那麼就對這些子集選擇新的最優特征，繼續對其進行分割，建構相應的節點，如果遞歸進行，直至所有訓練資料子集被基本正确的分類，或者沒有合适的特征為止。
4）每個子集都被分到葉節點上，即都有了明确的類，這樣就生成了一顆決策樹。
一般的，一顆決策樹包含一個根節點、若幹個内部結點和若幹個葉結點；葉結點則對應于一個屬性冊書；每個葉結點包含的樣本集合根據屬性測試的結果被劃分到子結點中；根結點包含樣本全集，從根結點到每個葉結點的路徑對飲過了一個判定測試序列。決策樹學習的目的是為了産生一顆泛化能力強的決策樹，其基本流程遵循簡單且隻管的“分而治之”（divide-and-conquer）政策，如下圖所示：
顯然，決策樹的生成是一個遞歸的過程。在決策樹基本算法中，有三種情形會導緻遞歸傳回：
- 目前結點包含的樣本全屬于同意類别，無需劃分；
- 目前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分；
- 目前結點包含的樣本集合為空，不能劃分。
在第二種情形下，我們把目前結點标記為葉結點，并且将其類别設定為該結點所含樣本最多的類别；在第三種情形下，同樣把目前結點标記為葉結點，但将其類别設定為其父結點所含樣本最多類别。注意這兩種情形的處理實質不同：情形二是在利用目前結點的後驗分布，而情形三則是把父結點的樣本分布當做目前結點的先驗分布。
決策樹與條件機率分布
決策樹的條件機率分布定義在特征空間的一個partition上。将特征空間劃分為互不相交的單元cell或區域region，并且在每個單元上定義了一個類的機率分布就構成了一個條件機率分布。
決策樹的一條路徑就對應與劃分中的一個單元。決策樹所表示的條件機率分布在由各個單元給定條件下類的條件機率分布組成。
假設X為表示特征的随機變量,X表示為類的随機變量，那麼這個條件機率分布為P（Y|X）.X取之于給定劃分下但與的集合，Y取值于類的結合。各葉節點上的條件機率一般在某一個類上機率最大。
決策樹的學習
決策樹學習是由訓練資料集估計條件機率模型。基于特征空間劃分的類的條件機率模型有無窮多個。我們選擇的條件機率模型應該不僅對訓練資料有很好的拟合，而且對未知資料有很好的預測。
決策樹學習用損失函數表示這一目标。決策樹學習的損失函數通常是正則化的極大似然函數。決策樹學習的政策是以損失函數為目标函數的最小化。
當損失函數确定以後，學習問題就變為在損失函數意義下選擇最優的決策樹的問題。因為從可能的決策樹中選取最優決策樹是NP（Non-Polynomial）完全問題，是以現實中決策樹學習算法通常采用啟發式（heuristic）方法，近似求解這一最優化問題。這樣得到的決策樹通常是次最優（sub-optimal）的。
決策樹學習的算法通常是一個遞歸地選擇最優特征，并根據該特征對訓練資料進行分割，使得各個子資料集有一個最好的分類的過程。這一過程對應着對特征空間的劃分，也對應着決策樹的建構。
決策樹學習算法包含特征選擇、決策樹的生成與決策樹的剪枝過程。由于決策樹表示一個條件機率分布，是以深淺不同的決策樹對應這不同複雜度的機率模型。決策書的生成對應于模型的局部選擇，決策樹的剪枝對應于模型的全局選擇。
決策樹學習的目标：根據給定的訓練資料集建構一個決策樹模型，使它能夠對執行個體進行正确的分類。
決策樹學習的本質：從訓練集中歸納出一組分類規則，或者說是由訓練資料集估計條件機率模型。
決策樹學習的損失函數：正則化的極大似然函數
決策樹學習的測試：最小化損失函數
特征選擇
如果利用一個特征進行分類的結果與随機分類的記過沒有很差别則稱這個特征沒有分類能力。經驗上扔掉這個特征對決策書學習的精度影響不大。通常特征選擇的準則是資訊增益或資訊增益比。
特征選擇是決定用那個特征來劃分特征空間。資訊增益（information gain）就能夠很好地表示這一直覺的準則。
資訊熵
資訊熵是衡量樣本純度的一種名額，嘉定目前樣本集合D中第k類樣本所占的比例為pk(k=1,2,...,|y|),則D的資訊熵定義為：
Ent(D)的值越小，則D的純度越高。
資訊增益
一般而言，資訊增益越大，則意味着使用屬性a來進行劃分所獲得的“純度提升”越大。其中ID3決策樹就是以資訊增益為準則來選擇劃分屬性。
資訊增益的缺點
在資料類别越多的屬性上資訊增益越大，比如在主鍵上資訊增益非常大，但明顯會導緻overfitting，是以資訊增益有一定缺陷
增益率
實際上，資訊增益準則對可取值數目較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響。C4.5決策樹算法不直接使用資訊增益，而是使用“增益率”來選擇最優劃分屬性，增益率定義為：
屬性a的可能取值數目越多（即V越大），則IV(a)的值通常會越大。需要注意的是，增益率準則對可取值數目較少的屬性有所偏好，是以C4.5算法并不是直接選擇增益率最大的候選劃分屬性，而是使用了一個啟發性：先從候選劃分屬性中找出資訊增益高于平均水準的屬性，再從中選擇增益率最高的。
基尼指數（GINI）
GINI指數：
1、是一種不等性度量；
2、通常用來度量收入不平衡，可以用來度量任何不均勻分布；
3、是介于0~1之間的數，0-完全相等，1-完全不相等；
4、總體内包含的類别越雜亂，GINI指數就越大（跟熵的概念很相似）。
CART決策樹選擇劃分屬性。資料集D的純度可以用基尼指數來度量
是以，Gini（D）越小，則資料集D的純度越高
剪枝處理
決策樹很容易發生過拟合，也就是由于對train資料集适應得太好，反而在test資料集上表現得不好。這個時候我們要麼是通過門檻值控制終止條件避免樹形結構分支過細，要麼就是通過對已經形成的決策樹進行剪枝來避免過拟合。另外一個克服過拟合的手段就是基于Bootstrap的思想建立随機森林（Random Forest）。
剪枝是決策樹學習算法對付“過拟合”的主要手段。在決策樹學習中，為了盡可能正确分類樣本，節點劃分過程不斷重複，有時會造成決策樹分支過多，這時有時候把自身特點當做所有資料都具有的一般性質而導緻過拟合，是以，可以通過主動去掉一些分支來降低過拟合的風險
基本政策有先剪枝和後剪枝，先剪枝是指在決策樹生成過程中，對每個節點在劃分前先進行估計，若目前節點的劃分不能帶來決策樹泛化性能的提升，則停止劃分目前節點标記為葉節點；後剪枝則是先從訓練集生成一顆完整的決策樹，然後自底向上地對非葉節點進行考察，若将該節點對應的字數替換為葉節點能帶來決策樹泛化性能提升，則将該子樹替換為葉節點。
簡而言之：
先剪枝 —— 在構造過程中，當某個節點滿足剪枝條件，則直接停止此分支的構造。
後剪枝 —— 先構造完成完整的決策樹，再通過某些條件周遊樹進行剪枝。
其實剪枝的準則是如何确定決策樹的規模，可以參考的剪枝思路有以下幾個：
（1）使用訓練集合(Training Set）和驗證集合(Validation Set)，來評估剪枝方法在修剪結點上的效用；
（2）使用所有的訓練集合進行訓練，但是用統計測試來估計修剪特定結點是否會改善訓練集合外的資料的評估性能，如使用Chi-Square（Quinlan，1986）測試來進一步擴充結點是否能改善整個分類資料的性能，還是僅僅改善了目前訓練集合資料上的性能；
（3）使用明确的标準來衡量訓練樣例和決策樹的複雜度，當編碼長度最小時，停止樹增長，如MDL(Minimum Description Length)準則。
影響分析
先剪枝使得很多分支沒有展開，這不僅降低了過拟合的風險，還顯著減少了決策樹的訓練時間開銷和測試時間。但是，有些分支雖目前不能提升泛化性。甚至可能導緻泛化性暫時降低，但在其基礎上進行後續劃分卻有可能導緻顯著提高，是以先剪枝的這種貪心本質，給決策樹帶來了欠拟合的風險。
對比預剪枝與後剪枝生成的決策樹，可以看出，後剪枝通常比預剪枝保留更多的分支，其欠拟合風險很小，是以後剪枝的泛化性能往往由于預剪枝決策樹。但後剪枝過程是從底往上裁剪，是以其訓練時間開銷比前剪枝要大。
參考博文：https://www.jianshu.com/p/61a93017bb02?from=singlemessage
決策樹分類邊界
另外，決策樹所形成的分類邊界有一個明顯的特點：軸平行，即它的分類邊界有若幹個與坐标軸平行的分段組成。
Graphviz工具
Graphviz是開源圖形可視化軟體。圖形可視化是一種将結構資訊表示為抽象圖和網絡圖的方法。它在網絡，生物資訊學，軟體工程，資料庫和網頁設計，機器學習以及其他技術領域的可視化界面中具有重要的應用。
Graphviz：可視化工具下載下傳位址：
https://graphviz.gitlab.io/_pages/Download/Download_windows.html
在指令行中輸入的轉化指令：
dot -Tpdf src.dot -o des.pdf
src.dot 表示的是帶路徑的.dot檔案
des.pdf 表示的是生成的.pdf檔案，最好也帶個路徑
例如：
dot -Tpdf G:\MachineLearning\tree.dot -o G:\MachineLearning\tree.pdf -- 成功将dot檔案轉化為pdf檔案
dot -Tpng G:\MachineLearning\tree.dot -o G:\MachineLearning\tree.png -- 成功将dot檔案轉化為png檔案。