決策樹 (Decision Tree) 是一種有監督學習方法，通過特徵和標籤構造一棵決策樹，學習特徵之間的規則，以解決分類和迴歸問題。
使用決策樹進行決策的過程就是從根節點開始，測試待分類項中相應的特徵屬性，並按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。
決策樹由以下 3 種元素構成：
- 根節點：包含樣本全集
- 內部節點：對應特徵屬性測試
- 葉節點：決策結果 (標籤)
決策樹如何辨別好瓜和壞瓜？
(此圖摘自周志華西瓜書，本人白板手繪版)
以上面的西瓜為例，我們要如何辨別一個瓜是好瓜。特點是：紋理清晰，根蒂稍蜷，觸感青綠，恰好，你構建了一棵決策樹，立馬判斷這是好瓜還是壞瓜？
判斷步驟如下：
- 根據紋理清晰，已知是清晰，那麼向左邊走，看第一步
- 接著，由紋理清晰到達第 2 層，由決策樹圖，我們可以看到，根蒂是稍蜷
- 接著到第 3 層，色澤的特徵的青綠，由此，我們可以得出結論，這是一個好瓜。
根據上面的示例，我們可以很直觀的得到一個實例的類別判斷，只要告訴各個特徵的具體值，決策樹的判定過程就相當於從樹中從根節點到某一個葉子節點的遍歷。每一步如何遍歷是由數據各個特徵的具體特徵屬性決定。
那麼，基於上面的一棵樹，我們又有如下疑問，為什麼根節點是紋理，而不是根蒂或者別的特徵呢？
決策樹又是基於什麼標準來選擇特徵的？如果構建決策樹？
決策樹學習的 3 個步驟
基於上面的問題，為了構建一棵優質的決策樹，決策樹主要有3個步驟。
特徵選擇，決策樹生成，決策樹剪枝
特徵選擇
特徵選擇也即選擇最優劃分屬性，從當前數據的特徵中選擇一個特徵作為當前節點的劃分標準。我們希望在不斷劃分的過程中，決策樹的分支節點所包含的樣本儘可能屬於同一類，即節點的 “純度” 越來越高。而選擇最優劃分特徵的標準不同，也導致了決策樹算法的不同。
- 信息熵 (information entropy)
- 信息增益 (information gain)
- 信息增益率 (information gain ratio)
- 基尼指數 (Gini index)
決策樹基於樹結構進行決策，可做分類，也可進行迴歸，有 ID3，C4.5，Cart 迴歸樹。通常是遞歸選擇最優特徵，並根據這個特徵對訓練數據進行分割，使得對各個子數據集有最好的決策過程，決策樹希望往最快達到純度更高子集合方向發展。
決策樹生成
生成算法 劃分標準 ID3 信息增益 C4.5 信息增益率 CART 基尼指數
ID3
ID3 以信息增益最大的特徵作為節點進行劃分，遞歸構建決策樹，直到所有特徵被劃分。
信息增益表示得知特徵 X 的信息而使得類 Y 的信息的不確定性減少程度。表示劃分前和劃分後的熵的差值，差值越大，增益越大。而劃分前的熵是確定的，劃分後的調減熵越小，則最終的信息增益越大。
決策時總是希望往最快達純度更高子集合方向發展，而純度越高怎麼解釋？純度高，特徵之間的差異越大，越利於特徵選擇。
具體方法
- 從根節點開始，對節點計算所有可能的特徵的信息增益，選擇信息增益值最大的特徵作為節點的劃分特徵；
- 由該特徵的不同取值建立子節點；
- 再對子節點遞歸地調用以上方法，構建決策樹；
- 到所有特徵的信息增益都很小或者沒有特徵可以選擇為止，得到最終的決策樹
信息增益偏向於取值較多的特徵
信息增益在面對類別較少的離散數據時效果較好，但是面對取值較多的特徵時效果會很不如人意。
關於信息增益對取值較多特徵的偏向性，我認為原因是：當特徵的取值較多時，根據此特徵劃分得到的子集純度有更大的可能性會更高(對比與取值較少的特徵)，因此劃分之後的熵更低，由於劃分前的熵是一定的，因此信息增益更大，因此信息增益比較偏向取值較多的特徵。
舉個較為極端的例子可能更好理解：如果特徵 A 的取值能將每一個樣本都分到一個節點當中去的時候(如編號等特徵)，條件熵部分會為 0，這意味著該情況下的信息增益達到了最大值，故 ID3 算法一定會選擇特徵 A。但是，顯然的，我們知道這個特徵 A 顯然不是最佳選擇。
那麼為什麼信息增益率就能改善這種情況呢？先來看一下信息增益率的計算公式：
H_A(D) 又叫特徵 A 的內部信息，H_A(D) 其實像是一個衡量以特徵 A 的不同取值將數據集 D 分類後的不確定性的度量。如果特徵 A 的取值越多，那麼不確定性通常會更大，那麼 H_A(D) 的值也會越大，而 1 / H_A(D) 會越小，相當於是在信息增益的基礎上乘上一個懲罰係數，即：
ID3 的特點
- 選擇信息增益大的特徵建立決策樹，信息增益會偏向那些取值較多的特徵(這也是C4.5採用信息增益率的原因)
- 只有樹的生成過程，容易過擬合
- 只能處理離散數據
- 不能處理缺失值
C4.5
對 ID3 進行改進，選用信息增益率進行特徵選擇，遞歸構建決策樹。
C4.5 特點
- 對 ID3 進行改進，選用信息增益率進行特徵選擇
- 能處理連續，離散類型
- 能處理缺失值
- 構造決策樹進行剪枝
Cart
CART (classification and regression tree) 分類迴歸樹算法，既可用於分類也可用於迴歸，在這一部分我們先主要將其分類樹的生成。
CART 分類樹
區別於 ID3 和 C4.5，CART 假設決策樹是二叉樹，內部節點特徵的取值為 “是” 和 “否”，左分支為取值為“是”的分支，右分支為取值為”否“的分支。
這樣的決策樹等價於遞歸地二分每個特徵，將輸入空間(即特徵空間)劃分為有限個單元。
CART 的分類樹用基尼指數來選擇最優特徵的最優劃分點，具體過程如下
- 從根節點開始，對節點計算現有特徵的基尼指數，對每一個特徵，例如 A，再對其每個可能的取值如 a，根據樣本點對 A=a 的結果的”是“與”否“劃分為兩個部分，利用
- 在所有可能的特徵 A 及該特徵所有可能的取值 a 中，選擇基尼指數最小的特徵及其對應的取值作為最優特徵和最優切分點，然後根據最優特徵和最優切分點，將數據集二分，生成兩個子節點。
- 對兩個子節點遞歸地調用上述步驟，直至節點中的樣本個數小於閾值，或者樣本集的基尼指數小於閾值，或者沒有更多特徵後停止。
- 生成 CART 分類樹。
CART 迴歸樹
迴歸樹是可以用於迴歸的決策樹模型，一個迴歸樹對應著輸入空間（即特徵空間）的一個劃分以及在劃分單元上的輸出值。
與分類樹不同的是，迴歸樹對輸入空間的劃分採用一種啟發式的方法，會遍歷所有輸入變量，找到最優的切分變量 j 和最優的切分點 s，即選擇第 j 個特徵 xj 和它的取值 s 將輸入空間劃分為兩部分，然後重複這個操作。
而如何找到最優的 j 和 s 是通過比較不同的劃分的誤差來得到的。一個輸入空間的劃分的誤差是用真實值和劃分區域的預測值的最小二乘來衡量的，即
其中 f(xi) 是每個劃分單元的預測值，這個預測值是該單元內每個樣本點的值的均值。
那麼，j 和 s 的求解可以用以下式進行
R1(j,s) 和 R2(j,s) 是被劃分後的兩個區域。
生成方法
- 選擇最優的切分變量 j 和 最優切分點 s，求解遍歷所有特徵，對固定的特徵掃描所有取值，找到使得上式達到最小值的 (j, s)
- 用選定的 (j, s) 劃分區域，並確定該區域的預測值
- 繼續對兩個子區域繼續上面的步驟，直至滿足停止條件
- 生成迴歸樹
決策樹剪枝
剪枝是為了避免決策樹模型過擬合，因為決策樹算法在學習過程中為了儘可能的正確分類訓練樣本，不停的對節點進行劃分，因此這會導致整棵樹分支過多，也就導致了過擬合。
決策樹的剪枝有兩種：預剪枝和後剪枝
預剪枝 (pre-pruning)
預剪枝就是在構造決策樹的過程中，先對每個結點在劃分前進行估計，若果當前結點的劃分不能帶來決策樹模型泛化性能的提升，則不對當前結點進行劃分並且將當前結點標記為葉結點。
後剪枝 (post-pruning)
後剪枝就是先把整顆決策樹構造完畢，然後自底向上的對非葉結點進行考察，若將該結點對應的子樹換為葉結點能夠帶來泛化性能的提升，則把該子樹替換為葉結點。
