第五章決策樹

05-14

決策樹是一種基於分類與回歸方法。本章主要討論用於分類的決策樹。決策樹學習通常包括3個步驟：特徵選擇、決策樹的生成和決策樹的修剪。

1、決策樹模型與學習

1、1 決策樹模型

分類決策樹模型是一種描述對實例進行分類的樹形結構，決策樹由結點(node)和有向邊(directed edge)組成。結點由兩種模式：內部節點（internal node）和葉結點(leaf node)。內部節點表示一個特徵或屬性，葉結點表示一個類。

用決策樹分類，從根節點開始，對實例的某一特徵進行測試，根據測試結果，將實例分配到其子結點；這時，每一個子結點對應著該特徵的一個取值。如此遞歸地對實例進行測試並分配，直至達到葉結點。最後將實例分配到葉節點的類中。

下圖是決策樹示意圖：

1、2 決策樹if-then規則

可以將決策樹看成一個if-then規則的集合：由決策樹的根節點到葉結點的每一條路徑構建一條規則；路徑上內部節點的特徵對應著規則的條件，而葉結點的類對應著規則的結論。決策樹的路徑或其對應的if-then規則集合具有一個重要的性質：互斥並且完備。這就是說，每一個實例都被一條路徑或一條規則所覆蓋，而且只被一條路徑或一個規則所覆蓋。

1、3 決策樹與條件概率分布

決策樹還表示給定特徵條件下類的條件概率分布。這一條件概率分布定義在特徵空間的一個劃分上。將特徵空間劃分為互不相交的單元或區域。並在每一個單元定義一個類的概率分布就構成了條件概率分布。

下圖表示了特徵空間的一個劃分：

1、4決策樹學習，假設給定訓練數據集：

D = { $(x_{1},y_{1}),......(x_{n},y_{n})$ }

其中 $x_{i} = (x_{i}^{1},x_{i}^{2},......,x_{i}^{n})^{T}$ 為輸入實例，n為特徵個數， $y_{i} in$ { $1,2,......,k$ }

為類的標記，i= 1,2,3,......N，N為樣本容量。學習的目標是根據給定的訓練數據集構建一個決策樹模型，使它能夠對實例進行正確的分類。

決策樹學慣用損失函數表示這一目標，如下所述，決策樹學習的損失函數通常是正則化的極大似然函數。決策樹的學習策略是以損失函數為目標函數的最小化。

當損失函數確定以後，學習問題就變為在損失函數意義下選擇最優決策樹的問題。決策樹學習的演算法通常是一個遞歸地選擇最優特徵，並根據該特徵對訓練數據進行分割，使得對各個子集有一個很好的分類的過程。這一過程對應著對特徵空間的劃分，也對應著決策樹的構建。

開始構建根結點，將所有訓練數據都放在根結點，選擇一個最優特徵，按照這一特徵將訓練數據集分割成子集，使得各子集有一個在當前條件下最好的分類。如果這些子集已經能夠被基本正確分類，那麼構建葉結點，並將這些子集分到所對應的葉結點中去；如果還有子集不能被基本正確分類，那麼就對這些子集選擇新的最優特徵，繼續對其進行分割，構建相應的結點，如此遞歸下去，直至所有訓練數據子集被基本正確分類。

以上方法生成的決策樹可能對訓練數據由很好的分類能力，但對未知的測試數據卻未必有很好的分類能力，即可能發生過擬合現象。所以我們需要對已生成的樹自上而下進行剪枝，將樹變得更簡單，從而使它具有更好的泛化能力。具體的就是去掉過於細分的葉結點，使其回退到父節點，甚至更高的結點，然後將父節點或者更高的結點改為新的葉結點。

2、特徵選擇

2、1 特徵選擇問題

特徵選擇在於選取對訓練數據具有分類能力的特徵。這樣可以提高決策樹學習的效率。特徵選擇的準則是信息增益和信息增益比。

2、2 信息增益

先給熵和條件熵的定義。

在資訊理論與概率論中，熵（entropy）是表示隨機變數不確定性的度量。設X是一個取有限個值得離散隨機變數。其概率分布

$P(X = x_{i})=p_{i} , i =1,2,...,n$

設隨機變數X的熵定義為：

$H(X) = -sum_{i=1}^{n}{p_{i} log p_{i}}$ (1)

由定義可知，熵只依賴與X的分布，而與X的取值無關，所以也可將X的熵記做H（p）,即:

$H(p) = -sum_{i=1}^{n}{p_{i} log p_{i}}$

設有隨機變數（X,Y），其聯合概率分布為：

$P(X = x_{i},Y=y_{i}) = p_{ij},i = 1,2,...n; j = 1,2,...m$

條件熵 $H(Y|X)$ 表示在一直隨機變數X的條件下隨機變數Y的不確定性，隨機變數X在給定條件下隨機變數Y的條件熵 $H(Y|X)$ ，定義為X在給定條件下Y的條件概率分布的熵對X的數字期望

$H(Y|X) = sum_{i =1}^{n}{p_{i}H(Y|X = x_{i})}$

信息增益：表示得知X的信息而使得類Y的信息不確定性減少的程度。

特徵A對訓練數據D的信息增益為g(D,A)，定義為集合D的經驗熵H(D)與特徵A給定條下D的經驗條件熵H（D|A）之差，即：

$g(D,A) = H(D) - H(D|A)$

一般的他倆之差為互信息，決策樹學習中的信息增益等價於訓練數據集中類與特徵的互信息。

根據信息增益準則的特徵選擇方法是：對訓練數據集D（或子集），計算每個特徵的信息增益，並比較他們的大小，選擇信息增益最大的特徵。

演算法1、（信息增益的演算法）

輸入：訓練數據集D和特徵A

輸出：特徵A對訓練數據集D的信息增益g（D,A）.

（1）計算數據集D的經驗熵H(D)

$H(D) = -sum_{k =1}^{K}{frac{|C_{k}|}{|D|}log_{2}frac{|C_{k}|}{|D|}}$

（2）計算特徵A對數據集D的經驗條件熵H（D|A）

$H(D|A) = -sum_{i= 1}^{n}{frac{|D_{i}|}{|D|}}sum_{k =1}^{K}{frac{|D_{ik}|}{|D|}log_{2}frac{|C_{ik}|}{|D_{i}|}}$

（3）計算信息增益

$g(D,A) = H(D)-H(D|A)$

2、3 信息增益比

特徵A對訓練數據集D的信息增益比gr（D,A）定義為其信息增益g（D,A）與訓練數據集D的經驗熵H（D）之比：

$g_{r}(D,A) = frac{g(D,A)}{H(D)}$

3、決策樹的生成

3、1 ID3演算法

ID3 演算法的核心是在決策樹各個節點上應用信息增益準則選擇特徵，遞歸地構建決策樹。具體方法是：從根節點開始，對結點計算所有可能是特徵的信息增益，選擇信息增益最大的特徵作為結點的特徵，由該特徵的不同取值建立子結點；在對子結點遞歸地調用以上方法，構建決策樹。ID3相當於用極大似然法進行概率模型的選擇。

演算法2（ID3演算法）

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

輸出：決策樹T

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

（2）若 $A = phi$ ，則T為單節點樹，並將D中實例數最大的類 $C_{k}$ 作為該結點的類標記，返回T；

（3）否則，按演算法1計算A中各特徵對D的信息增益，選擇信息增益最大的特徵 $A_{g}$ ;

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

（5）否則，對 $A_{g}$ 的每一個取值 $a_{i}$ ，依 $A_{g} = a_{i}$ 將分割為若干非空子集 $D_{i}$ ,將其中實例數最大的類作為標記，構建子結點，由結點及其子結點構成樹T，返回T；

（6）對結點i，以 $D_{i}$ 為訓練集，以 $A-{}$ { $A_{g}$ }為特徵集，遞歸地調用步（1）~步（5），得到子樹T，返回T。

3、2 C4.5的生成演算法

C4.5演算法與ID3演算法相似，C4.5演算法對ID3演算法進行了改進，C4.5在生成的過程中，用信息增益比選擇特徵。

演算法3 （C4.5 的生成演算法）

輸入：訓練數據集D，特徵集A，閾值 $varepsilon$

輸出：決策樹T

（1）若D中所有實例屬於同一類 $C_{k}$ ,則T為單節點樹，並將 $C_{k}$ 作為該結點的類，返回T；

（2）若 $A = phi$ ，則T為單節點樹，並將D中實例數最大的類 $C_{k}$ 作為該結點的類標記，返回T；

（3）否則，按下式計算A中各特徵對D的信息增益，選擇信息增益最大的特徵 $A_{g}$ ;

$g_{r}(D,A) = frac{g(D,A)}{H(D)}$

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

（5）否則，對 $A_{g}$ 的每一個取值 $a_{i}$ ，依 $A_{g} = a_{i}$ 將分割為若干非空子集 $D_{i}$ ,將其實例數最大的類作為標記，構建子結點，由結點及其子結點構成樹T，返回T；

（6）對結點i，以 $D_{i}$ 為訓練集，以 $A-{}$ { $A_{g}$ }為特徵集，遞歸地調用步（1）~步（5），得到子樹T，返回T。

4、決策樹的剪枝

決策樹生成的演算法遞歸地產生決策樹，直到不能繼續下去為止。所以會出現過擬合現象。

在決策樹中將已生成的樹進行簡化的過程稱為剪枝（pruning）。具體的，剪枝從已生成的樹上裁掉一些子樹或葉結點，並將其根節點或父節點作為新的葉結點，從而簡化分類樹模型。

決策樹的剪枝往往通過極小化決策樹整體的損失函數（loss function）或代價函數（cost function）來實現。設樹T的葉結點個數為|T|，t是樹T的葉結點，該葉結點有 $N_{i}$ 個樣本點，其中k類的樣本點有 $N_{tk}$ 個，k = 1,2,...,K， $H_{t}(T)$ 為葉結點t上的經驗熵， $alphageq0$ 為參數，則決策樹學習的損失函數可以定義為：

$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}}$

在損失函數中，將式（5.11）右端的第1項記作

$C(T) = sum_{t= 1}^{|T|}{N_{t}H_{t}(T)} = -sum_{t= 1}^{|T|}sum_{k}^{}{frac{N_{tk}}{N_{t}}} logfrac{N_{tk}}{N_{t}}$

這時有

$C_{alpha}(T) = C(T) +alpha |T|$

上式中，C（T）表示模型對訓練數據的預測誤差，即模型與訓練數據的一盒程度，|T|表示模型的複雜度，參數 $alphageq0$ 控制著兩者之間的影響。

剪枝，就是當 $alpha$ 確定時，選擇損失函數最小的模型，即損失函數最下的子樹，當 $alpha$ 確定時，子樹越大，往往與訓練數據的你和越好，但是模型的負責度就越高，相反，子樹越小，模型的複雜度就越低，但是往往與訓練數據的擬合不好，損失函數正好表示了對兩者的平衡。

可以看出，決策樹生成只考慮了通過提高信息增益對訓練數據進行更好的擬合，而決策樹剪枝通過優化損失函數還考慮了減小模型複雜度，決策樹生成學習局部的模型，而決策樹剪枝學習整體的模型。

演算法4（樹的剪枝演算法）

輸入：生成演算法產生的整個樹T，參數 $alpha$ ；

輸出：修剪後的子樹 $T_{alpha}$

（1）計算每個結點的經驗熵。

（2）遞歸地從樹的葉結點向上回縮。

設一組葉結點回縮到其父節點之前與之後的整體樹分別為 $T_{B}與T_{A}$ ,其對應的損失函數值分別為 $C_{a}(T_{A})與C_{a}(T_{B})$ ,如果 $C_{a}(T_{A})leq C_{a}(T_{B})$ 則進行剪枝，即將父節點變為新的葉結點。

（3）返回（2），直至不能繼續為止，得到損失函數最小的子樹 $T_{a}$

5、 CART演算法

CART在給定的輸入隨機變數X條件下輸出隨機變數Y的條件概率分布的學習演算法。CART假設決策樹是二叉樹，內部節點特徵的取值為「是」或「否」，左分值為「是」，右分支為「否」，這樣的決策樹等價於遞歸地二分每一個特徵，將輸入空間即特徵空間劃分為有限個單元，並在這些單元上確定預測的概率分布，也就是在輸入給定的條件下輸出條件概率分布：

CART演算法由以下兩個步驟組成：

（1）決策樹生成：基於訓練數據集生成決策樹，生成的決策樹要盡量大；

（2）決策樹剪枝：用驗證數據集對已生成的樹進行剪枝並選擇最優子樹，這時用損失函數最小作為剪枝的標準。

5、1 CART生成

決策樹的生成就是遞歸地構建二叉樹的過程，對回歸樹用平方誤差最小化準則，對分類樹用基尼指數（Gini index）最小化準則，進行特徵選擇，生成二叉樹。

5、1.1 回歸樹的生成

演算法5（最小二乘回歸樹生成演算法）

輸入：訓練數據集D

輸出：回歸樹f（x）

在訓練數據集所在的輸入空間中，遞歸地將每個區域劃分為兩個子區域並決定每個子區域上的輸出值，構建二叉決策樹：

（1）選擇最優切分變數j與切分點s，求解

$min_{(j,s)}[min_{c_{i}}sum_{x_{i}in R_{1}(j,s)}^{}{(y_{i}-c_{1})^{2}}+ min_{c_{2}}sum_{x_{i}in R_{1}(j,s)}^{}{(y_{i}-c_{1})^{2}}]$

遍歷變數j，對固定的切分變數j掃描切分點s，選擇使式（5.21）達到最小值的對（j,s）.

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

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

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

（3）繼續對兩個子區域調用步驟（1）（2），直至滿足停止條件。

（4）將輸入空間劃分為M個區域 $R_{1},R_{2},...,R_{M}$ ,生成決策樹：

$f(x) =sum_{m =1}^{M}{c_{m}I}(xin R_{m})$

2. 分類樹的生成

分類樹用基尼指數選擇最優特徵，同時決定該特徵的最優二值切分點。

定義5.4（基尼指數）分類問題中，假設有K個類，樣本點屬於第K類的概率為 $p_{k}$ ，則概率分布的基尼指數為：

$Gini(p) = sum_{k = 1}^{K}{p_{k}(1-p_{k})} = 1-sum_{k=1}^{K}{p_{k}^{2}}$

對於二類分類問題，若樣本點屬於第1個類的概率是p，則概率分布的基尼指數為：

$Gini(p)=2p(1-p)$

對於給定的樣本集合D，其基尼指數為：

$Gini(p) = 1-sum_{k=1}^{K}{(frac{|C_{k}|}{|D|})^{2}}$

這裡， $C_{k}$ 是D中屬於第k類的樣本子集，K是類的個數。

如果樣本集合D根據特徵A是否取某一可能值a被分割成 $D_{1}和D_{2}$ 兩部分，則在特徵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 （CART生成演算法）

輸入：訓練數據集D，停止計算的條件；

輸出：CART 決策樹。

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

（1）設結點的訓練數據集為D，計算現有特徵對該數據集的基尼指數，此時，對每一個特徵A，對其可能取的每個值a，根據樣本點對A=a的測試為「是」或「否」將D分割成 $D_{1}和D_{2}$ 兩部分，利用式子計算A=a的基尼指數。

（2）在所有可能的特徵A以及它們所有可能的切分點a中，選擇基尼指數最小的特徵及其對應的切分點作為最優特徵與最優切分點，依最優特徵與最優切分點，從現結點生成兩個子節點，將訓練數據集依特徵分配到到兩個子結點中。

（3）對兩個子結點遞歸地調用（1）（2）直至滿足停止條件。

（4）生成CART決策樹。

演算法通知計算的條件是節點中的樣本個數小於預定閾值，或樣本集的基尼指數小於預定閾值，或沒有更多特徵。

5.2 CART剪枝

CART剪枝演算法從「完全生長」的決策樹的低端剪去一些子樹，使決策樹變小（模型變簡單），從而能夠對未知數據有更準確的預測。CART剪枝演算法由兩部組成：首先從生成演算法產生的決策樹 $T_{0}$ 低端開始不斷進行剪枝，直到 $T_{0}$ 的根節點，形成一個子樹序列；然後通過交叉驗證法在獨立的驗證數據集上對子樹序列進行測試，從中選擇最優子樹。

1.剪枝，形成一個子樹序列

在剪枝過程中，計運算元樹的損失函數：

$C_{alpha}(T) = C(T) +alpha |T|$

對固定的a，一定存在使損失函數 $C_{alpha}(T)$ 最小的子樹，將其表示為 $T_{a}$ . $T_{a}$ 在損失函數 $C_{alpha}(T)$ 最小的意義下是最優的。容易驗證這樣的最優子樹是唯一的。在a大的時候，最優子樹 $T_{a}$ 偏小，在a小的時候，最優子樹 $T_{a}$ 偏大，極端情況，當a = 0時，整體樹是最優的，當 $a ightarrowinfty$ 時，根節點組成的單結點樹是最優的。