決策樹及其變種演算法

02-12

最近面臨找工作，因此把機器學習的演算法梳理一遍，希望對自己和大家有一定的幫助。

先從決策樹開始吧。

決策樹（Decision Tree）

1.演算法簡介

與大部分機器學習演算法類似，決策樹分為分類決策樹和回歸決策樹。決策樹由節點和有向邊組成。其中，葉節點為類別標籤（預測值），非葉節點為評估條件。分類（預測）時，用一條未知類別標籤（預測值）的輸入數據與樹形結構的節點進行匹配查詢，最終找到唯一葉節點，該葉節點的類別標籤（預測值）即該該數據對應的類別（預測值）。

2.常見的決策樹演算法：

ID3、C4.5、CART。一般用來分類，其中CART可以用來做回歸。

3.模型構建三部曲：

特徵選擇、決策樹生成、決策樹剪枝。

3.1特徵選擇：

ID3的特徵選擇是信息增益，由於信息增益會偏向於特徵值較多而與類別無關的特徵，因此C4.5在ID3的基礎上改用信息增益比來選擇特徵。CART分類演算法根據基尼指數選擇特徵，CAET回歸演算法根據平方誤差最小化原則選擇特徵。具體名詞解釋將在文章末尾給出。

其中，ID3選擇信息增益最大的特徵，C4.5選擇信息增益比最大的特徵，CART分類樹選擇基尼指數最小的特徵和值對 $(j,s)$ ,從而使得數據劃分後類別的不確定性最小。CART回歸數用平方誤差最小化原則選擇特徵和值對 $(j,s)$ ，從而使得劃分後的平方誤差最小，這樣的回歸樹通常稱為最小二乘回歸樹。

3.2決策樹生成：

ID3和C4.5分類樹：

輸入：訓練數據集D，特徵集A，閾值ε；

輸出：決策樹T

1）若 $D$ 中所有實例屬於同一類 $C$ ，則 $T$ 為單節點樹，並將類 $C$ 作為該節點的類標記，返回 $T$ ；

2）若A=?，則 $T$ 為單節點樹，並將D中實例數最大的類C作為該節點的類標記，返回T；

3）否則，計算A中各特徵對D的信息增益（信息增益比），選擇A中信息增益(信息增益比)最大的特徵 $A_{j}$ ；

4）如果 $A_{j}$ 的信息增益小於閾值ε，則 $T$ 為單節點樹，並將 $D$ 中實例數最大的類 $C$ 作為該節點的類標記，返回 $T$ ；

5）否則，以特徵 $A_{j}$ 為 $T$ 的根節點，特徵 $A_{j}$ 中各個取值s下包含的非空數據集 $D_{(j,s)}$ 為訓練數據集，ε為閾值，遞歸調用該生成演算法生成 $|S|$ 個子樹 $T_{j}$ （其中 $|S|$ 表示特徵 $j$ 的取值個數）。

6）返回T。

CART分類樹：

輸入：數據集D、停止條件

輸出：CART決策樹

根據訓練數據集，從根節點開始，遞歸地對每個節點進行以下操作，構建二叉決策樹。

1）設節點的訓練數據集 $D$ ，計算現有特徵對該數據集地基尼指數 $Gini(D)$ ，對於離散型特徵來說：對每個特徵 $A_{j}$ ，以及可能取的每個值 $s$ ，根據樣本點對 $A_{j}=s$ 的測試為「是」和「否」將 $D$ 分割成 $D_{1}$ 和 $D_{2}$ 兩部分；對於連續型特徵來說：對每個特徵 $A_{j}$ ，以及可能取的每個值 $s$ ，根據樣本點是否滿足 $A_{j}leq s$ 將 $D$ 分割成 $D_{1}$ 和 $D_{2}$ 兩部分。計算按照 $(j,s)$ 劃分後數據集的基尼指數 $Gini(D,A_{j})$ 。

2）在所有可能的特徵 $A$ 以及他們所有可能的切分點 $s$ 中，選擇基尼指數最小的特徵及其對應的切分點作為最優特徵和最優切分點，作為該子樹的根節點。根據最優特徵和最優切分點從根節點生成兩個子節點，將訓練數據集按照特徵和切分點分配到兩個子節點中。

3）對兩個子節點遞歸調用1），2），直到滿足停止條件。

4）返回生成的CART決策樹。

CART回歸樹：

1）選擇最優切分特徵和值對 $(j,s)$ ,求解 $min_{(j,s)}left[ min_{c_{1}}sum_{x_{i}in R_{1}(j,s)}^{}{(y_{i}-c_{1})^{2} }+ min_{c_{2}}sum_{x_{i}in R_{2}(j,s)}^{}{(y_{i}-c_{2})^{2} } ight]$ ，遍歷特徵和值對 $(j,s)$ ，選擇使上式達到最小值的 $(j,s)$ 。

2）用選定的 $(j,s)$ 劃分區域並決定相應的輸出值：

$R_{1}(j,s)=left{ x|x^{(j)}leq s ight}$ ， $R_{2}(j,s)=left{ x|x^{(j)}>s ight}$

$ilde{c}_{m}=frac{1}{N_{m}} sum_{x_{i}in R_{m}(j,s)}^{}{y_{i}} , xin R_{m},m=1,2$

3）重複2）和3），直到滿足停止條件。

4）將輸入空間劃分為M個區域 $R_{1},R_{2},...,R_{M}$ ，生成決策樹： $f(x)=sum_{m=1}^{M}{ ilde{c}_{m}I(xin R_{m}) }$ 。

3.3決策樹剪枝

生成決策樹時過多考慮如何提高訓練數據的正確分類（預測），從而構建了過於複雜的決策樹。往往對訓練數據分類（預測）準確，但是對位置的測試數據分類準確度下降，產生過擬合。解決過擬合的方法就是簡化決策樹。對已生成的決策樹進行簡化的過程稱為剪枝。具體的，就是在已生成的樹中剪掉部分子樹或葉節點，使得子樹或葉節點的父節點變成新的葉節點，從而簡化分類（回歸）樹模型。

決策樹剪枝往往通過極小化決策樹整體損失函數（loss function）或代價函數（cost function）來實現。

設樹 $T$ 葉節點個數為 $|T|$ ， $t$ 是T的葉節點，該葉節點有 $N_{t}$ 個樣本點，其中 $k$ 類的樣本點有 $N_{tk}$ 個， $H_{t}(T)$ 為葉節點 $t$ 的經驗熵， $alpha geq 0$ 。決策樹學習的損失函數定義為： $C_{alpha }(T)=sum_{t=1}^{|T|}{N_{t}H_{t}(T)}+alpha |T|$ 。其中，經驗熵 $H_{t}(T)=-sum_{k}^{}{frac{N_{tk}}{N_{t}}logfrac{N_{tk}}{N_{t}} }$ ， $C(T)=sum_{t=1}^{|T|}{N_{t}H_{t}(T)}=-sum_{t=1}^{|T|}{sum_{k=1}^{K}{N_{tk}logfrac{N_{tk}}{N_{t}} } }$ ，因此 $C_{alpha }(T)=C(T)+alpha |T|$ 。 $C(T)$ 表示模型對訓練數據的預測誤差，即模型的擬合程度， $|T|$ 表示模型複雜度，通過 $alpha$ 調節來防止過擬合。剪枝時的損失函數極小化等價於正則化的極大似然估計。採用交叉驗證法在子樹序列 $T_{0},T_{1},...,T_{n}$ 中選擇最優子樹 $T$ 。提示：由於每次剪枝時只關注葉節點的父節點以下的樹在剪枝前和剪枝後的損失函數，選擇最小損失函數，因此其計算可以局部進行，可以由一種動態規劃演算法實現。

4.決策樹評價：

優點：簡單、高效，是一種非線性模型。

缺點：容易過擬合，需要進行剪枝。

5.python代碼實現

可能是代碼太多了，無法保存，直接鏈接到我之前的文章吧，【點擊這裡】有ID3，C4.5和CART分類樹的實現代碼。CART回歸樹與之類似，只是在每個節點上保存該節點下樣本子集中Y的均值和選擇特徵時用最小均方差。

6.名詞解釋：

1.熵：H(X)表示隨機變數不確定性的度量。 $H(X)=-sum_{i=1}^{n}{p_{i}log(p_{i}) }$ ，其中 $P(X=x_{i})=p_{i},(i=1,2,...,n)$ ，表示x的概率分布。提示：熵越大，隨機變數的不確定性越大， $0leq H(X)leq log(n)$ 。

2.條件熵： $H(Y|X)$ 表示X給定條件下Y的條件分布的熵對X的數學期望。 $H(Y|X)=sum_{i=1}^{n}{p_{i}H(Y|X=x_{i})}$ 。

3.信息增益： $g(D,A)$ 表示得知特徵A的信息使得類D的信息不確定性減少的程度。 $g(D,A)=H(D)-H(D|A)$ ，熵與條件熵的差稱為互信息，決策樹學習中的信息增益等價於訓練數據集中類與特徵的互信息。提示：信息增益大的特徵有更強的分類能力。

4.信息增益比： $g_{R}(D,A) =frac{g(D,A)}{H_{A}{(D)} }$ ，其中 $H_{A}{(D)}$ 表示數據集D關於特徵A的概率分布的熵。

5.基尼指數： $Gini(p)=sum_{k=1}^{K}{p_{k}(1-p_{k})}=1-sum_{k=1}^{K}px_{k}^{2}$ ，如果樣本集合D根據特徵A是否取某一可能值a被分割成 $D_{1}$ 和 $D_{2}$ 兩部分，則在特徵A和特徵值a的條件下，集合D的基尼指數 $Gini(D,A)=frac{|D_{1}|}{|D|} Gini(D_{1})+frac{|D_{2}|}{|D|}Gini(D_{2})$ ，基尼指數 $Gini(D)$ 表示集合D的不確定性，基尼指數 $Gini(D,A)$ 表示經過 $A=a$ 分割後集合D的不確定性。提示：基尼指數越大，樣本不確定性越大。

6.平方誤差最小化：假設切分特徵和值對為 $(j,s)$ ，根據特徵和特徵值對將數據劃分為兩部分 $R_{1}(j,s)=left{ x|x^{(j)}leq s ight} 和R_{2}(j,s)=left{ x|x^{(j)}>s ight}$ ，分別計算兩部分樣本Y的均值 $C_{1}$ 和 $C_{2}$ ，求解 $min_{(j,s)}left[ min_{c_{1}}sum_{x_{i}in R_{1}(j,s)}^{}{(y_{i}-c_{1})^{2} }+ min_{c_{2}}sum_{x_{i}in R_{2}(j,s)}^{}{(y_{i}-c_{2})^{2} } ight]$ 。依次遍歷所有特徵和可能的取值，找到使得平方誤差最小的特徵和值對 $(j,s)$ 。

決策樹的集成學習（ensemble learing）

1.概念簡介：

集成學習是機器學習中一個熱門分支，是用多個弱分類器組合成一個強分類器的方法。一般的弱分類器包括：決策樹，神經網路，貝葉斯分類器，KNN等。已有理論證明集成學習可以提高分類器的性能，且永遠不會過擬合。由於本篇文章主要介紹決策樹，因此下面將介紹以決策樹作為弱分類器的集成學習演算法。

2.集成思想：

1）Boosting：第一次按照均勻分布從樣本集中選出樣本子集 $D_{1}$ ，訓練弱分類器 $C_{1}$ ；之後對上一次的分類器 $C_{i-1},i=(2,3,...,m)$ 錯分類的樣本賦予較大的分布權值，使其在這一輪訓練中出現的概率增加，從而得到m個弱分類器，根據分類效果給分類器賦予權值（效果好的權值較大，反之較小），最後將 $m$ 個弱分類器加權平均獲得最終分類結果。

2）Bagging：從樣本集中有放回的隨機選出樣本子集 $D_{i}$ ，使用所有特徵對這個樣本子集 $D_{i}$ 建立 $m$ 個弱分類器，投票決定數據屬於哪個類別。

3）Bagging和Boosting的區別：①採樣方式不同，Bagging均勻隨機重採樣；Boosting根據錯誤率採樣，因此Boosting分類精度優於Bagging。②Bagging各分類器是不相關的，可以並行；Boosting下一個分類器依賴於上一個分類器，只能串列。

4 中常見集成演算法

1.隨機森林(RF)--Bagging

隨機森林是對樣本進行有放回的隨機採樣，並隨機選擇m個特徵( $m<M$ )，然後進行貪婪的訓練決策樹（不剪枝），重複以上操作建立多棵決策樹形成森林，決策時採用投票的方式決定。

優點：

能夠處理高維度特徵的數據，不需要做特徵選擇。
訓練過程中，能夠提取特徵之間的相互影響。
訓練完後，能夠找出重要的特徵。
訓練過程可並行化，速度快

實現簡單，不會產生過擬合
對於不平衡的數據集，可以平衡誤差
單棵樹拿出來也能派上一丁點用場（相對提升樹來說）

缺點：

在噪音較大的分類或回歸問題上會過擬合
內部（樹與樹）之間獨立----後人無法從先人身上學到東西。

2.極端隨機樹(ET)--Bagging

極端隨機樹與隨機森林有兩點主要區別：1）ET中每棵樹採用所有訓練樣本，即每棵樹的樣本集相同。2）RF在特徵子集中選擇最優分叉特徵，而ET直接隨機選擇分叉特徵。

優缺點：基本與隨即森林類似。由於ET採用所有訓練樣本使得計算量相對RF增大，而採用隨機特徵，減少了信息增益（比）或基尼指數的計算過程，計算量又相對RF減少。

3.梯度提升決策樹(GBDT)-Gradient Boosting

梯度提升：就是採用梯度下降的方法，在每次迭代時向損失函數最小的方向移動使得損失函數減小。

梯度提升(Gradient Boosting)與提升演算法(Boosting)的區別：提升演算法為錯分樣本賦予更大的權值，而忽略正確的樣本，導致過分關注錯分樣本，使得分類決策面在錯分樣本附近震蕩。而梯度提升每次計算是為了減少上一次的殘差，建立新的模型是為了使之前模型誤差沿著梯度方向下降，關注點從樣本轉移到了分類（回歸）誤差。

GBDT與RF的區別：

梯度提升樹（GBDT）將各個樹串聯起來，每棵樹學習的目標是之前 $N-1$ 棵樹的殘差；而隨即森林（RF）每棵樹都是單獨訓練。
在GBDT中，使用較淺的樹（通常採用樹樁），計算量減少。
RF不過分追求降低偏差，因此不容易過擬合（甚至根本不會過擬合），而GBDT由於過於追求降低誤差（偏差），容易產生過擬合。
GBDT不適合分散式運算，並且訓練時間較長。
GBDT單棵樹拿出來沒有任何意義。

4.AdaBoost--Boosting

AdaBoost是Boosting的一種，特點是能夠自適應的訓練分類器。可以認為AdaBoost演算法是模型為加法模型、損失函數為指數函數、學習演算法為前向分步演算法的二分類學習方法。

訓練過程中，首先樣本權值取樣本個數的倒數 $alpha_{1}=frac{1}{n}$ ，第m棵決策樹 $G_{m}(x)$ 的權值係數 $alpha _{m}=frac{1}{2} logfrac{1-e_{m} }{e_{m} }$ ， $e_{m}$ 為 $G_{m}(x)$ 的分類誤差率。更新訓練集樣本的權值分布 $w_{m+1,i}=frac{w_{mi}}{Z_{m}} (-alpha_{m}y_{i}G_{m}(x_{i})) , i=1,2...,n$ ,其中 $Z_{m}$ 為歸一化因子 $Z_{m}=sum_{i=1}^{n}{w_{mi}}e^{-alpha_{m}y_{i}G_{m}(x_{i})}$ 最終的決策函數 $f(x)=sum_{m=1}^{M}{alpha_{m}G_{m}(x)}$ ,M為決策樹個數，最終分類器函數 $G(x)=sign(f(x))$