機器學習-決策樹

機器學習—決策樹

（一）決策樹的基本流程

（二）決策樹中節點的劃分

（三）多變量決策樹

四、決策樹

　　正如西瓜書前言所述，從本章至第十章，主要介紹一些經典而常用的機器學習算法。這些方法大部分為分類方法，也穿插了少量回歸算法(例如6.5節的支援向量回歸)；大部分為監督學習方法，少量為無監督學習方法(第九章的聚類和第十章的降維)。

1.1 決策樹的基本概念

　　決策樹(Decision Tree）是在已知各種情況發生機率的基礎上，通過構成決策樹來求取淨現值的期望值大于等于零的機率，評價項目風險，判斷其可行性的決策分析方法，是直覺運用機率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝幹，故稱決策樹。在機器學習中，決策樹是一類常見的機器學習方法，也是一個預測模型，他代表的是對象屬性與對象值之間的一種映射關系。Entropy = 系統的淩亂程度，使用算法ID3, C4.5和C5.0生成樹算法使用熵。這一度量是基于資訊學理論中熵的概念。

　　決策樹是一種樹形結構，其中樹的最高層即為根節點，每個内部節點表示一個屬性上的測試，每個分支代表一個測試輸出（結果），而決策樹的每一個葉節點代表一種類别。決策樹是基于樹結構來進行決策的，這恰是人類在面臨決策問題時一種很自然的處理機制。

例如，我們針對西瓜問題中“是否為好瓜的判定作出決策，通常會進行一系列的判斷或“子決策”：

我們先看，“色澤”這一屬性，也即“該西瓜是什麼顔色？”

=>　若“色澤”=“青綠色”

2. 則再看“根蒂”的屬性，“西瓜的根蒂是什麼形态？”

=>　若“根蒂”=“蜷縮”

3. 則判斷“敲聲”的屬性，“西瓜敲起來是什麼聲音？”

=>　若“敲聲”=“濁響”

4. 最後，結合以上判斷，最終決策為，這是一個好瓜

以上，決策過程如下圖所示：

在上圖的決策樹中，決策過程的每一次判定都是對某一屬性的“測試”，決策最終結論則對應最終的判定結果。一般地，一棵決策樹包含：唯一的根節點、若幹個内部節點和若幹個葉子節點。進而有：

葉節點對應于決策結果，其餘，其餘每個節點則對應于一個屬性測試；

每個非葉子節點，表示一個特征屬性測試。

每個分支，表示這個特征在某個值域上的輸出、

每個葉子節點，存放一個類别。

每個節點包含的樣本集合，通過屬性測試被劃分到子節點中，根節點包含樣本全集。

決策樹學習的目的：為了産生一棵泛化能力強，即處理未見示例能力強的決策樹。

1.2 決策樹的構造及基本流程

　　類似于樹的資料結構，決策樹學習的算法通常是一個遞歸地選擇最優特征，并根據該特征對訓練資料進行分割，使得各個子資料集有一個最好的分類的過程。這一過程對應着對特征空間的劃分，也對應着決策樹的建構。

終止條件: 在決策樹基本算法中，有以下三種情形會導緻遞歸傳回：

情形(1) 葉節點（目前節點）包含的樣本全屬于同一類别，無需劃分（這時直接将該節點标記為葉節點，并設為相應的類别）。

情形(2) 目前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分（這時将該節點标記為葉節點，并将其類别設為該節點所含樣本最多的類别）。

情形(3) 目前節點包含的樣本集合為空，不能劃分（這時将該節點标記為葉節點，并将其類别設為父節點中所含樣本最多的類别）。

說明：在情形(2)下，我們把目前節點标記為葉節點，并将其類别設定為該節點所含樣本最多的類别；

在情形(3)下，同樣把目前節點标記為葉節點，但将其類别設定為其父節點所含樣本最多的類别。

注意這兩種情形的處理實質不同：情形(2)是在利用目前節點的後驗分布，而情形(3)則是把父節點的樣本分布作為目前節點的後驗分布。

決策樹的基本流程遵循簡單而直覺的“分而治之”(divide-and-conquer)政策。

輸入：訓練集 D = ${(x_1,y_1), (x_2,y_2),\cdots,(x_m, y_m)}$;

　　　屬性集 A = ${a_1,a_2,\cdots,a_d}$.

過程：函數 TreeGenerate(D,A)

1: 生成節點node:

2: if D中樣本全屬于同一類别C then

3: 　　将node标記為C類葉節點;

　　　return; # 終止條件1（最好的情形）

4: end if

5: if A = ∅ OR D中樣本在A上取值相同then

6: 　　将node标記為葉節點，其類别标記為D中樣本數最多的類;　

　　　return; # 終止條件2（屬性用完或分不開的情形，使用後驗分布）

7: end if

8: 從A中選擇最優劃分屬性$a_{*}$;

9: for $a_{*}$的每一個值$a_{*}^{v}$ do

10: 　　為node生成一個分支；令$D_{v}$表示D在D中在$a_{*}$上取值為$a_{*}^{v}$ 的樣本子集；

11: 　　if $D_{v}$ 為空 then

12: 　　　　将分支節點标記為葉節點，其類别标記為D中樣本最多的類;

　　　　return; # 終止條件3（分支為空，使用先驗分布）

13: 　　else

14: 　　　　以TreeGenerate($D_{v}$, A \ { $a_{*}$ })為分支節點

　　　　 (若 $a_{*}$為連續屬性，則不用去除，尋找下一個最優劃分點可繼續作為子節點的劃分屬性)

15: 　　end if

16: end for

輸出：以node為根節點的一棵決策樹

從上述僞代碼算法可以看出，決策樹學習的關鍵在于算法的這一行：從A中選擇最優劃分屬性$a_{*}$;

由此可以看出：決策樹學習的關鍵在于如何選擇劃分屬性，不同的劃分屬性得出不同的分支結構，進而影響整顆決策樹的性能。

所謂決策過程，就是不斷根據某屬性進行劃分的過程(注意：每次決策時考慮範圍是在上次決策結果的限定範圍之内的)，即“If...Else, If...Else”的決定過程。

　　但是資料集是不可能無限劃分的，那麼劃分到什麼時候就停止劃分呢？這就是下面三個"return"代表的遞歸傳回。

下面分别做一個解釋：

首先，應該明白決策樹的基本流程是根據某種原則(從A中選擇最優劃分屬性$a_{*}$)每次選擇一個屬性按屬性的取值(例如西瓜的“觸感”包括硬滑和軟粘)進行劃分(将所有“觸感”為硬滑的西瓜分到一起，将所有“觸感”為軟粘的西瓜分到一起；根據該屬性劃分後，産生的各子集内部樣本在該屬性上的取值分别相同)，依次再對各劃分子集進行遞歸劃分。

然而這裡有幾種特殊情況需要考慮：

(1) 劃分期望得到的結果是各子集隻包含同一類别的樣本，例如好瓜(或壞瓜)，若遞歸劃分過程中某子集已經隻含有某一類别的樣本(例如隻含好瓜)，那麼此時劃分的目的已經達到了，無需再進行劃分，這即為遞歸傳回的情形(1)；

(2)遞歸劃分時每次選擇一個屬性，并且劃分依據屬性不能重複使用，例如本次根據“觸感”對目前樣本子集$D$進行劃分時，那麼後面對該子集$D$劃分成的子集(以及子集的子集$\cdots \cdots$)再次進行遞歸劃分時不能再使用“觸感”(TreeGenerate($D_{v}$, A \ { $a_{*}$ })中的$D_{v}$, A \ { $a_{*}$ }表示從候選依據屬性中将目前使用的依據屬性去除，這是因為根據某屬性劃分之後，産生的各個子集在該屬性上的取值相同)；但樣本的屬性是有限的，是以劃分次數不超過屬性個數；若所有屬性均已被作為劃分依據，此時子集中仍含有多類樣本(例如仍然同時含有好瓜和壞瓜)，但是因已無屬性可作為劃分依據(即子集中樣本在各屬性上取值均相同，但卻無法達到子集隻包含同一類别的樣本)，此時隻能少數服從多數，以此子集中樣本數最多的類作為标記，此即為遞歸傳回的情形(2)的A= ∅ ;

(3)疊代過程中，每遞歸一次，候選的屬性個數就減少一個；假設現在還剩一個屬性可用(比如“觸感”)，而且子集中仍含有多類樣本(例如仍然同時含有好瓜和壞瓜)，由于隻剩一個屬性可用，我們也隻能在這個屬性上劃分，但是子集所有樣本在該屬性上的取值都相同(例如“觸感”都是硬滑)，就陷入了一個尴尬的境地，無法再繼續劃分了(無法繼續劃分的原因是因為屬性取值都相同，其實剩餘多個屬性也類似的，劃分就是根據屬性的不同取值将目前樣本集合分為多個子集，若目前樣本集合在任何候選屬性上的取值相同，則無法劃分)，此時也隻能服從少數服從多數，以此子集中樣本最多的類為标記，此即為遞歸傳回的情形(2)中的“D中樣本在Ａ上取值相同”；

(4)根據某屬性進行劃分時，若該屬性多個屬性值中的某個屬性值不包含任何樣本(這可能是訓練集的樣本不夠充分造成的)，例如對目前子集D以“紋理”屬性來劃分，“紋理”共有三個值：清晰、稍糊、模糊，但發現目前子集D中并無樣本“紋理”屬性取值為稍糊(即子集D中樣本或為清晰、或為稍糊)，此時對于取值為清晰的子集和取值為稍糊的子集繼續遞歸，而對于取值為模糊的分支，因為無樣本落入，将其标記為葉節點，其類别标記為D中樣本最多的類(即把父節點的樣本分布作為目前節點的先驗分布)；

注意，此分支必須保留，因為測試時，可能會有樣本落入該分支。此即遞歸傳回的情形(3)

如此用文字叙述還比較抽象，下面使用在表4.1西瓜資料集2.0上基于資訊增益生成的圖4.4決策樹來具體說明：

(1) 根據“紋理”屬性劃分偶，發現“紋理”為模糊的3個樣本全部是壞瓜，即遞歸傳回的情形(1):目前節點包含的樣本全屬于同一類别，無需劃分；

同理，接下來對“紋理”為清晰的樣本，再次根據“根蒂”屬性劃分後，發現“根蒂”為蜷縮的樣本全部是好瓜，“根蒂”為硬挺的樣本全部是壞瓜，即遞歸傳回的情形(1)；此時隻有“根蒂”為稍蜷的樣本同時含有好瓜和壞瓜，是以需要繼續進行劃分：

(2) 接下來對“根蒂”為稍蜷的樣本，再次根據“色澤”屬性進行劃分後，發現“色澤”為青綠的樣本全部是好瓜，即遞歸傳回的情形(1)；發現沒有“色澤”為淺白的樣本，即遞歸傳回情形(3)：目前節點包含的樣本集合為空，不能互粉；是以同樣把目前節點标記為葉節點，将其類别設定為其父節點所含樣本最多的類别，即好瓜(如下表所示，其父節點包含三個樣本，其中兩個為好瓜，一個不是好瓜)：

(3) 注意：決策樹的流程中沒有出現遞歸傳回情形(2)，這是因為表4.1的西瓜資料集2.0樣本數太少。假設表4.1的資料集隻包含“紋理”和“根蒂”兩個屬性，則根據“紋理”劃分之後，再對“紋理”為清晰的樣本根據“根蒂”劃分，發現兩個屬性都已使用，但“根蒂”為稍蜷的樣本子集中仍同時包含好瓜和壞瓜，即遞歸傳回的情形(2)的A = ∅.

此時将“根蒂”為稍蜷的節點标記為葉節點，并将其類别設定為該節點所含樣本最多的類别，即“好瓜”(好瓜包含三個樣本，其中兩個為好瓜，一個不是好瓜)。

(4) 對于遞歸傳回情形(2)的“D中樣本在A上取值相同”，如下表所示(非表4.1資料，純為解釋該遞歸傳回情形而編造的):

此時已根據“紋理”和“根蒂”兩個屬性進行劃分，樣本子集中仍同時包含好瓜和壞瓜，仍有“臍部”和“觸感”兩個屬性可以使用，但目前子集中的樣本在剩餘的“臍部”和“觸感”兩個屬性上的取值均相等(均為凹陷和硬滑)，是以無法進行劃分，是以将該節點标記為葉節點，并将其類别設定為該節點所含樣本最多的類别，即“好瓜”(節點包含五個樣本，其中三個為好瓜，兩個不是好瓜)。

總結：(a) 劃分期望得到的結果是各子集隻包含同一類别的樣本

(b) 使用的屬性在後續各子集繼續劃分時不能再使用，因為各子集内的樣本在該屬性上取值相同，因為各子集内的樣本在該屬性上取值相同(僅針對離散屬性，若是連續屬性，則可以重複使用，如表4.3中的“密度”和“含糖率”)；

(c) 對于遞歸傳回情形(1)，雖有可用屬性但樣本類别卻已相同，可以了解為這些屬性對目前劃分不起作用；

(d) 對于遞歸傳回情形(2)，目前子集樣本在所有屬性上取值相同，但樣本類别卻不同，可以了解為樣本集含的标記含有噪聲(特征相同的樣本，被标記的類别卻不相同，可能是标記資料時弄錯了)，或應增加新特征(即目前的幾種特征屬性不足以描述樣本)；

(e) 決策樹并不一定是二叉樹，分支個數等于屬性取值個數。

2.1 三種度量節點“純度”的名額：

什麼樣的劃分屬性是最優的？

我們希望決策樹的分支結構所包含的樣本盡可能屬于同一類别，也即屬性劃分的目标是讓各個劃分出來的子節點盡可能地“純”，節點的“純度”越來越高，可以高效地從根節點到達葉節點，進而得到決策結果。

如何評價度量節點“純度”？

三種度量節點“純度”的名額：

資訊增益 => ID3算法

增益率 => C4.5算法

基尼指數 => CART算法

2.1.1、資訊增益

在資訊論與機率統計中，熵（entropy）是表示随機變量不确定性的度量。

設X是一個取有限個值的離散随機變量，其機率分布為：

\[P(X=x_i) = p_i, i=1,2,\cdots,n

則随機變量X的熵定義為：

\[H(X) = H(p) = -\sum \limits_{i=1}^{n}p_ilog_2p_i,log以2為底，熵H(x)的機關為比特(bit) \\

H(X) = H(p) = -\sum \limits_{i=1}^{n}p_ilog_ep_i = -\sum \limits_{i=1}^{n}p_ilnp_i,log以e為底，熵H(x)的機關為納特(nat)\\

由定義可知，熵越大，随機變量的不确定性就越大。

“資訊熵”(information entropy)是度量樣本集合純度最常用的一種名額。假定目前樣本集合D中第k類樣本所占的比例為$p_k(k = 1,2,\cdots,|K|)$,則D的資訊熵定義為：

\[Ent(D) = -\sum \limits_{k=1}^{|K|} p_klog_2p_k　\quad \quad (4.1)

當樣本集合D中隻含某一類樣本時資訊熵Ent(D)最小:(若p = 0，則$plog_2p = 0$)-

\[Ent(D) = - \sum \limits_{k=1}^{|y|} p_k log_2 p_k = -1 \cdot log_21 - 0\cdot log_2 0 - \cdots 0 \cdot log_2 0 = 0

若D中隻包含一類樣本，則Ent(D)=0，此時純度最高。

由定義關系式可知，資訊熵Ent(D)的值越小，則D的純度越高($p_k$與Ent(D)成反比。

假定離散屬性A有K個可能的取值$\left\{a_1, a_2,\dots,a_K\right\}$,若使用A來對樣本集D進行劃分，則會産生K個分支結點，其中第k個分支節點包含了樣本集D中所有在屬性A上上取值為$a_k$的樣本，記為$D^{k}$。

我們根據$Ent(D) = -\sum \limits_{k=1}^{|y|} p_klog_2p_k$計算出$D^{k}$的資訊熵，再考慮到不同的分支節點所包含的樣本數不同，給分支節點賦予權重$\frac{|D^{k}|}{|D|}$，即樣本數越多的分支節點的影響越多，于是可計算出用屬性A對樣本集D進行劃分所獲得的“資訊增益”（information gain）

\[Gain(D,A) = Ent(D) - \sum \limits_{k=1}^{K}\frac {|D^{k}|}{|D|}Ent(D^{k}) \quad \quad (4.2)

我們希望經過依據某屬性劃分後，劃分所得各子集的純度越高越好，即各子集的資訊熵$Ent(D^k)$越小越好(若是各子集樣本的類别相同，則所有子集的$Ent(D^k)=0$)，也就是說，資訊增益$Gain(D,A)$越大越好。

又由于劃分所得各子集包含的樣本個數有多有少，故以其所占比例$\frac{|D^k|}{|D|}$為權重進行權重。

設訓練資料集為$D$,$|D|$表示其樣本容量（即樣本個數）。

設有K個類$C_k$，$k = 1,2,\cdots,|C_k|$為屬于類$C_k$的樣本個數，$\sum \limits_{k=1}^{K} |C_k| = |D|$。

設特征A有n個不同的取值${a_1,a_2,\cdots,a_n}$，

根據特征A的取值将D劃分為n個子集$D_1,D_2,\cdots,D_n$,

$|D_i|$為$D_i$的樣本個數，$\sum \limits_{i=1}^{n} |D_i| = |D|$。

記子集$D_i$中屬于類$C_k$的樣本的集合為$D_{ik}$，即$D_{ik} = D_i ∩ C_k$,$|D_ik|$為$D_ik$為$D_ik$的樣本個數。

當熵和條件熵中的機率由資料估計（特别是極大似然估計）得到時，所對應的熵與條件熵分别稱為經驗熵（empirical entropy）和經驗條件熵（empirical conditional entropy）。

此時，若機率為1或0，則令1log1=0或0log0=0。

資訊增益（information gain）表示得知特征X的資訊而使得類Y的資訊的不确定性減少的程度。

[算法1]資訊增益的算法

輸入：訓練資料集(目前樣本集合)D和特征(離散屬性)A

輸出：特征A對訓練資料D的資訊增益$g(D,A)$.

(1) 計算資料集D的經驗熵$H(D)$(經驗熵為《統計學習方法》的表述，等同于西瓜書的資訊熵)：

\[H(D) = -\sum \limits_{k=1}^{K} \frac{|C_k|}{D} log_2 \frac{C_k}{D} \\

= Ent(D) = -\sum \limits_{k=1}^{|K|}p_klog_2p_k \\

其中 p_k = \frac {|C_k|}{D}

(2) 計算特征A對資料D的經驗條件熵$H(D|A)$：

\[H(D|A) = \sum \limits_{i=1}^{n} \frac{|D_i|}{D}H(D_i) = -\sum \limits_{i=1}^{n} \frac{|D_i|}{D} \left[ \sum \limits_{k=1}^{K} \frac{D_{ik}}{D_i}log_2 \frac{|D_{ik}|}{|D_i|}\right] \\

= - \sum \limits_{k=1}^{K}\frac{|D^k|}{|D|} Ent(D^{k}) \\

= \sum \limits_{k=1}^{k}\frac{|D^k|}{|D|} \left[(-\sum \limits_{k=1}^{K}p_klog_2p_k)\right] \\

= -\sum \limits_{k=1}^{k}\frac{|D^k|}{|D|}(\sum \limits_{k=1}^{K}p_klog_2p_k)

(3) 計算資訊增益：

\[Gain(D,A) = g(D,A) = H(D) - H(D|A) \\

= Ent(D) - \sum \limits_{k=1}^{K}\frac {|D^{k}|}{|D|}Ent(D^{k}) \\

= -\sum \limits_{k=1}^{K} \frac{|C_k|}{D} log_2 \frac{C_k}{D} - \left[ -\sum \limits_{i=1}^{n} \frac{|D_i|}{D} \left[ \sum \limits_{k=1}^{K} \frac{D_{ik}}{D_i}log_2 \frac{|D_{ik}|}{|D_i|}\right]\right] \\

= \sum \limits_{i=1}^{n} \frac{|D_i|}{D}\sum \limits_{k=1}^{K} \frac{D_{ik}}{D_i}log_2 \frac{|D_{ik}|}{|D_i|} - \sum \limits_{k=1}^{K} \frac{|C_k|}{D} log_2 \frac{C_k}{D} \\

= \sum \limits_{k=1}^{k}\frac{|D^k|}{|D|}(\sum \limits_{k=1}^{K}p_klog_2p_k) - \sum \limits_{k=1}^{|K|}p_klog_2p_k

一般來說，資訊增益越大，則意味着使用屬性A來進行劃分所獲得的“純度提升”越大。

以下表中的西瓜資料集2.0為例，該資料集包含17個訓練樣例，用以學習一棵能預測沒剖開的是不是好瓜的決策樹。

若按照是否為“好瓜”進行分類決策，則此時$|K|$ =2。在決策樹學習開始時，根節點包含資料集$D$中的所有樣例，其中正例（“好瓜”）占$p_1$= $\frac {8}{17}$，反例（“壞瓜”）=$\frac{9}{17}$。

于是，根據公式$Ent(D) = -\sum \limits_{k=1}^{|K|}p_klog_2p_k$有:

\[Ent(D) = -\sum \limits_{k=1}^{K=2}p_klog_2p_k \\

= -(\frac{8}{17}log_2\frac{8}{17} + \frac{9}{17}log_2\frac{9}{17}) = 0.998

然後，我們要計算出目前屬性集合{色澤，根蒂，敲聲，紋理，臍部，觸感}中每個屬性的資訊增益。

以屬性“色澤”為例，它有三個可能的取值：{青綠，烏黑，淺白}。

若使用該屬性對資料集$D$進行劃分，則可得到三個子集，分别記為:{$D^{1}$(色澤=青綠)，$D^{2}$(色澤=烏黑)，$D^{3}$(色澤=淺白)}。

子集$D^{1}$包含編号為{1,4,6,10,13,17}的6個樣例，其中正例（“好瓜”）占$p_1=\frac{3}{6}$，反例（“壞瓜”）占$p_2=\frac{3}{6}$;

子集$D^{2}$包含編号為{2,3,7,8,9,15}的6個樣例，其中正例（“好瓜”）占$p_1=\frac{4}{6}$，反例（“壞瓜”）占$p_2=\frac{2}{6}$;

子集$D^{3}$包含編号為{5,11,12,14,16}的6個樣例，其中正例（“好瓜”）占$p_1=\frac{1}{5}$，反例（“壞瓜”）占$p_2=\frac{4}{5}$;

根據公式$Ent(D) = -\sum \limits_{k=1}^{|K|}p_klog_2p_k$，可計算出用“色澤”劃分之後所獲得的3個分支節點的資訊熵為：

\[Ent(D^{1}) = -(\frac{3}{6}log_2\frac{3}{6} + \frac{3}{6}log_2\frac{3}{6}) = 1.000 ,\\

Ent(D^{2}) = -(\frac{4}{6}log_2\frac{4}{6} + \frac{2}{6}log_2\frac{2}{6}) = 0.918 ,\\

Ent(D^{3}) = -(\frac{1}{5}log_2\frac{1}{5} + \frac{4}{5}log_2\frac{4}{5}) = 0.722

于是，根據$Ent(D) - \sum \limits_{k=1}^{K}\frac {|D^{k}|}{|D|}Ent(D^{k})$，可計算出屬性“色澤”的資訊增益為：

\[Gain(D,色澤) = Ent(D) - \sum \limits_{k=1}^{K=3}\frac{|D^{k}|}{|D|}Ent(D^{k}) \\

= 0.998 - (\frac{6}{17}*1.000 + \frac{6}{17}*0.918 + \frac{5}{17}*0.722) = 0.109

類似的，以屬性“根蒂”為例，它有三個可能的取值：{蜷縮，稍蜷，硬挺}。

若使用該屬性對資料集$D$進行劃分，則可得到三個子集，分别記為:{$D^{1}$(根蒂=蜷縮)，$D^{2}$(根蒂=稍蜷)，$D^{3}$(根蒂=硬挺)}。

子集$D^{1}$包含編号為{1,2,3,4,5,12,16,17}的6個樣例，其中正例（“好瓜”）占$p_1=\frac{5}{8}$，反例（“壞瓜”）占$p_2=\frac{3}{8}$;

子集$D^{2}$包含編号為{6,7,8,9,13,14,15}的7個樣例，其中正例（“好瓜”）占$p_1=\frac{3}{7}$，反例（“壞瓜”）占$p_2=\frac{4}{7}$;

子集$D^{3}$包含編号為{10,11}的6個樣例，其中正例（“好瓜”）占$p_1=\frac{0}{2}$，反例（“壞瓜”）占$p_2=\frac{2}{2}$;

根據公式$Ent(D) = -\sum \limits_{k=1}^{|K|}p_klog_2p_k$，可計算出用“根蒂”劃分之後所獲得的3個分支節點的資訊熵為：

\[Ent(D^{1}) = -(\frac{5}{8}log_2\frac{5}{8} + \frac{3}{8}log_2\frac{3}{8}) = 0.954 ,\\

Ent(D^{2}) = -(\frac{3}{7}log_2\frac{3}{7} + \frac{4}{7}log_2\frac{4}{7}) = 0.985 ,\\

Ent(D^{3}) = -(\frac{0}{2}log_2\frac{0}{2} + \frac{2}{2}log_2\frac{2}{2}) = 0.00

于是，根據$Ent(D) - \sum \limits_{k=1}^{K}\frac {|D^{k}|}{|D|}Ent(D^{k})$，可計算出屬性“根蒂”的資訊增益為：

\[Gain(D,根蒂) = Ent(D) - \sum \limits_{k=1}^{K=3}\frac{|D^{k}|}{|D|}Ent(D^{k}) \\

= 0.998 - (\frac{8}{17}*0.954 + \frac{7}{17}*0.985 + \frac{2}{17}*0.00) = 0.143

同樣的，我們可以計算出其他屬性的資訊增益：

\[Gain(D,敲聲) = 0.141；Gain(D,紋理) = 0.381；\\

Gain(D,臍部) = 0.289; Gain(D,觸感) = 0.006; \\

我們選擇資訊增益最大的屬性（“紋理”），作為劃分屬性，也即為最優特征。

下圖為基于“紋理”對根節點進行劃分的結果，各分支節點所包含的樣例子集顯示在節點中。

然後，決策樹學習算法将對每個分支節點做進一步劃分。

以上圖第一個分支節點（“紋理”=“清晰”）為例,該節點包含的樣例集合$D^{1}$中有編号為{1,2,3,4,5,6,8,10,15}的9個樣例，可用屬性集合為{色澤,根蒂,敲聲,臍部,觸感}

基于$D_{1}$計算出各屬性的資訊增益:

\[Gain(D^{1},色澤) = 0.043; \quad Gain(D^{1},根蒂) = 0.458; \\

Gain(D^{1},敲聲) = 0.331; \quad Gain(D^{1},臍部) = 0.458; \\

Gain(D^{1},色澤) = 0.458;

以上，“根蒂”，“臍部”，“觸感”三個屬性均取得了最大的資訊增益，可任選其之一作為劃分依據。類似的，對每個分支節點進行上述操作，最終得到決策樹如下圖所示。

例題[1] 根據資訊增益準則選擇最優特征

對下表所給出的訓練資料集D，根據資訊增益準則選擇最優特征。（來源-統計學習方法）

下表資料包括貸款申請人的4個特征（屬性）:

第一個特征是年齡，有三個可能值{青年，中年，老年}；

第二個特征是有工作，有兩個可能值{是，否}；

第三個特征是有自己的房子，有兩個可能值{是，否}；

第四個特征是信貸情況，有三個可能值{非常好，好，一般}。

表的最後一列是類别，是否同意貸款，取兩個值{是，否}。

解：

首先計算經驗熵H(D):以“類别”作為決策結果，則$|K|=2$.

根據$H(D) = -\sum \limits_{k=1}^{K} \frac{|C_k|}{D} log_2 \frac{C_k}{D}$有：

\[H(D) = -\left[\frac{9}{15}log_2\frac{9}{15} + \frac{6}{15}log_2\frac{6}{15}\right] \\

= -\frac{9}{15}log_2\frac{9}{15} - \frac{6}{15}log_2\frac{6}{15} = 0.971

然後分别計算各特征對資料集D的資訊增益。分别記為:{$A_1$(年齡),$A_2$(有工作),$A_3$(有自己的房子),$A_4$(信貸情況)}，則：

(1) 對于$A_{1}$(年齡)，若使用該屬性對資料集$D$進行劃分，則可得到三個子集，分别記為:{$D^{1}$(年齡=青年)，$D^{2}$(年齡=中年)，$D^{3}$(年齡=老年)}。

子集$D^{1}$包含編号為{1,2,3,4,5}的5個樣例，其中正例（“是”）占$p_1=\frac{2}{5}$，反例（“否”）占$p_2=\frac{3}{5}$;

子集$D^{2}$包含編号為{6,7,8,9,10}的5個樣例，其中正例（“是”）占$p_1=\frac{3}{5}$，反例（“否”）占$p_2=\frac{2}{5}$;

子集$D^{3}$包含編号為{11,12,13,14,15}的5個樣例，其中正例（“是”）占$p_1=\frac{4}{5}$，反例（“否”）占$p_2=\frac{1}{5}$;

根據公式$H(D) = -\sum \limits_{k=1}^{K} \frac{|C_k|}{D} log_2 \frac{C_k}{D}$，可計算出用“年齡”劃分之後所獲得的3個分支節點的資訊熵為：

\[H(D^{1}) = -(\frac{2}{5}log_2\frac{2}{5} + \frac{3}{5}log_2\frac{3}{5}) = 0.971 ,\\H(D^{2}) = -(\frac{3}{5}log_2\frac{3}{5} + \frac{2}{5}log_2\frac{2}{5}) = 0.971 ,\\H(D^{3}) = -(\frac{4}{5}log_2\frac{4}{5} + \frac{1}{5}log_2\frac{1}{5}) = 0.722

\[g(D,A_1) = H(D) - \left[ \frac{5}{15}H(D^{1}) + \frac{5}{15}H(D^{2}) + \frac{5}{15}H(D^{3})\right] \\

= 0.971 -\left[ \frac{5}{15}(-\frac{2}{5}log_2\frac{2}{5} - \frac{3}{5}log_2\frac{3}{5}) + \frac{5}{15}(-\frac{3}{5}log_2\frac{3}{5} - \frac{2}{5}log_2\frac{2}{5}) + \frac{5}{15}(-\frac{4}{5}log_2\frac{4}{5} - \frac{1}{5}log_2\frac{1}{5})\right] \\

= 0.971 - \left[\frac{2}{3}×0.971+\frac{1}{3}×0.722\right] \\

= 0.971 -0.888 = 0.083

類似地，

(2)對于$A_{2}$(有工作):若使用該屬性對資料集$D$進行劃分，則可得到兩個子集，分别記為:{$D^{1}$(有工作=是)，$D^{2}$(有工作=否)}

子集$D^{1}$包含編号為{3,4,8,13,14}的5個樣例，其中正例（“是”）占$p_1=\frac{5}{5}$，反例（“否”）占$p_2=\frac{0}{5}$;

子集$D^{2}$包含編号為{1,2,5,6,7,9,10,11,12,15}的10個樣例，其中正例（“是”）占$p_1=\frac{4}{10}$，反例（“否”）占$p_2=\frac{6}{10}$;

\[g(D,A_2) = H(D) - \left[ \frac{5}{15}H(D^{1}) + \frac{10}{15}H(D^{2}) \right] \\

= 0.971 - \left[ \frac{5}{15}×0 + \frac{10}{15}\left(-\frac{4}{10}log_2\frac{4}{10} - \frac{6}{10}log_2\frac{6}{10}\right)\right] = 0.324

(3)對于$A_{3}$(有自己的房子):若使用該屬性對資料集$D$進行劃分，則可得到兩個子集，分别記為:{$D^{1}$(有自己的房子=是)，$D^{2}$(有自己的房子=否)}

子集$D^{1}$包含編号為{4,8,9,10,11,12}的6個樣例，其中正例（“是”）占$p_1=\frac{6}{6}$，反例（“否”）占$p_2=\frac{0}{6}$;

子集$D^{2}$包含編号為{1,2,3,5,6,7,13,14,15}的9個樣例，其中正例（“是”）占$p_1=\frac{3}{9}$，反例（“否”）占$p_2=\frac{6}{9}$;

\[g(D,A_3) = H(D) - \left[ \frac{6}{15}H(D^{1}) + \frac{9}{15}H(D^{2}) \right] \\

= 0.971 - \left[ \frac{6}{15}×0 + \frac{9}{15}\left(-\frac{3}{9}log_2\frac{3}{9} - \frac{6}{9}log_2\frac{6}{9}\right)\right] = 0.420

(4)對于$A_{4}$(信貸情況):若使用該屬性對資料集$D$進行劃分，則可得到三個子集，分别記為:{$D^{1}$(信貸情況=一般)，$D^{2}$(信貸情況=好)，$D^{3}$(信貸情況=非常好)}

子集$D^{1}$包含編号為{1,4,5,6,15}的5個樣例，其中正例（“是”）占$p_1=\frac{1}{5}$，反例（“否”）占$p_2=\frac{4}{5}$;

子集$D^{2}$包含編号為{2,3,7,8,12,13}的6個樣例，其中正例（“是”）占$p_1=\frac{4}{6}$，反例（“否”）占$p_2=\frac{2}{6}$;

子集$D^{3}$包含編号為{9,10,11,14}的4個樣例，其中正例（“是”）占$p_1=\frac{4}{4}$，反例（“否”）占$p_2=\frac{0}{4}$;

\[g(D,A_4) = H(D) - \left[ \frac{5}{15}H(D^{1}) + \frac{6}{15}H(D^{2}+ \frac{4}{15}H(D^{3}) \right] \\

= 0.971 - \left[ \frac{5}{15}(-\frac{1}{5}log_2\frac{1}{5}-\frac{4}{5}log_2\frac{4}{5}) + \frac{6}{15}\left(-\frac{4}{6}log_2\frac{4}{6} - \frac{2}{6}log_2\frac{2}{6}\right) + \frac{4}{15}×0 \right] \\

= 0.971 - 0.608 = 0.363

最後，比較各特征值的資訊增益值{($A_1$=0.083)，($A_2$=0.324)，($A_3$=0.420)，($A_4$=0.363)}。

由于特征值$A_3$（有自己的房子）的資訊增益值最大，是以選擇特征值$A_3$作為最優特征。

2.1.2、增益率

實際上，以資訊增益作為劃分訓練資料集的特征，資訊增益準則對可取值數目較多的屬性有所偏好，存在偏向于選擇取值較多的特征的問題。使用增益率（資訊增益比）（information gain ratio）可以對這一問題進行校正。

增益率（資訊增益比）的定義：

特征（屬性）A對訓練資料集（目前樣本集合）D的增益率（資訊增益比）$g_{R}(D,A)$定義為其資訊增益$g(D,A)$與訓練資料集D關于特征A的值的熵$H_{A}(D)$之比，也即

\[\begin{align}

& 西瓜書表述: Gain-ratio(D,A) = \frac{Gain(D,A)}{IV(A)} \\

& 統計學習方法表述：g_{A}(D,A) = \frac{g(D,A)}{H_{A}(D)} 　\quad \quad (4.3)

\end{align}

其中，

&西瓜書表述：IV(A) = - \sum \limits_{v=1}^{V} \frac{|D_{v}|}{D} log_2 \frac{D_v}{D} \\

&統計學習方法表述：

H_{A}(D) = =- \sum \limits_{i=1}^{n} \frac{|D_{i}|}{D} log_2 \frac{D_i}{D} \quad \quad (4.4)

稱為屬性A的“固有值”(intrinsic value)，n為特征取值的個數。

特征（屬性）A的可能取值數目越多（也即V越大）,則$IV(A)$的值通常會越大。

例如，對西瓜資料集2.0，有IV(觸感)=0.874(V=2)，IV(色澤)=1.580(V=3)，IV(編号)=4.088（V=17）。

為了解上式(4.4)“固有值”的概念，可以将式(4.4)與(4.1)進行比較。

式(4.1)可重寫為：

$Ent(D) = -\sum \limits_{k=1}^{|\mathcal{Y}|}p_k log_2 p_k = - \sum \limits_{k=1}^{|\mathcal{Y}|} \frac{|\mathcal{D}^k|}{|\mathcal{D}|}log_2 \frac{|\mathcal{D}|}{|\mathcal{D}|}$.

其中$p_k = \frac{|D^k|}{|D|}$，為第k類樣本所占的比例。

與式(4.4)的表達式作對比：

$IV(A) = -\sum \limits_{v=1}^{V} \frac{\mathcal{D}^v}{|\mathcal{D}|}log_2 \frac{\mathcal{D}^v}{\mathcal{D}}$

其中$p_v = \frac{|D^v|}{|D|}$，為屬性A等于第v個屬性值的樣本所占的比例。

即式(4.1)是按樣本集合D的類别标記計算的資訊熵，而式(4.4)是按屬性A的取值計算的資訊熵(相當于将屬性A作為類别)。

這裡考慮一種特殊情況：若屬性A的取值與類别标記一一對應，則$Ent(D) = IV(A)$，式(4.2)中第二項等于零，此時式(4.3)的增益率等于1。

需注意的是，增益率準則對可取值數目較少的屬性有所偏好，是以，C4.5算法的思想是：并不直接選擇增益率最大的屬性作為劃分候選屬性，而是使用了一個啟發式:先從候選劃分屬性中找出資訊增益高于平均水準的屬性，再從中選擇增益率最高的。

2.1.3、基尼值＆基尼指數

[注]在西瓜書中對于$Gini(D)$稱為基尼值，對于$Gini(D,A)$稱為基尼指數。實際上，在《統計學習方法》藍皮書中沒有嚴格區分，$Gini(D)$僅為$Gini()$

基尼值的定義:在分類問題中，假設有Ｋ個類，樣本點屬于第k類的機率為$p_k$，

采用與資訊熵$Ent(D) = - \sum \limits_{k=1}^{K}p_klog_2p_k$相同的符号，則資料集Ｄ機率分布(D的純度)可用基尼值表示。定義為

\[Gini(p) = \sum \limits_{k=1}^{K} \sum \limits_{k^{'}≠k}p_kp_{k^{'}} \\

= \sum \limits_{k=1}^{K}p_k(1-p_k) = 1 - \sum \limits_{k=1}^{K}p_k^2 \quad \quad (4.5)

(4.5)的推導：

假設資料集D中樣例标記種類共有三類，每類樣本所占比例分别為$p_1,p_2,p_3$。現從資料集D中随機抽取兩個樣本，如下表所示

$p_1$ $p_2$ $p_3$

$p_1p_1$ $p_1p_2$ $p_1p_3$

$p_2p_1$ $p_2p_2$ $p_2p_3$

$p_3p_1$ $p_3p_2$ $p_3p_3$

兩個樣本标記正好一緻的機率為(即對角線元素之和)：

$p_1p_1 + p_2p_2 + p_3p_3 = \sum \limits_{k=1}^{|\mathcal{Y}|=3}p_k^2$

兩個樣本标記不一緻的機率為(即“基尼值”)：

$Gini(D) = p_1p_2 + p_1p_3 + p_2p_1 + p_2p_3 + p_3p_1 + p_3p_2 = \sum \limits_{k=1}^{|\mathcal{Y}|=3}\sum \limits_{k' \neq k}p_k p_{k'}$

很容易證明(提取公因式即可，注意$p_1+p_2+p_3 = 1$)

$(p_1p_1 + p_2p_2 + p_3p_3) +(p_1p_2 + p_1p_3 + p_2p_1 + p_2p_3 + p_3p_1 + p_3p_2) \\ =(p_1p_1 + p_1p_2 + p_1p_3) + (p_2p_1 + p_2p_2 + p_2p_3) + (p_3p_1 + p_3p_2 + p_3p_3) \\= p_1(p_1 + p_2 + p_3) + p_2(p_1 + p_2 + p_3) + p_3(p_1+p_2+p_3) \\ =p_1 + p_2 + p_3 = 1$

即得式(4.5):

$Gini(D) = \sum \limits_{k=1}^{|\mathcal{Y}|}\sum \limits_{k'\neq k} p_kp_{k'} = 1 - \sum \limits_{k=1}^{|\mathcal{Y}|}p_k^2$.

從一個資料集Ｄ中任取兩個樣本，類别标記一緻的機率越大表示其純度越高(即大部分樣本屬于同一類)；

類别标記不一緻的機率(即基尼值)越大表示純度越差；是以選擇使各劃分子集的基尼值盡可能小的屬性作為劃分屬性，基尼指數即各子集基尼值的權重平均。

\(p_2\)	\(p_3\)
\(p_1p_1\)	\(p_1p_2\)	\(p_1p_3\)
\(p_2p_1\)	\(p_2p_2\)	\(p_2p_3\)
\(p_3p_1\)	\(p_3p_2\)	\(p_3p_3\)

對于二分類問題，若樣本點屬于一個類的機率為$p$，則機率分布的基尼值為

\[Gini(p) = 2p(1-p)

對于給定的樣本集合D，其基尼值為：

\[Gini(Ｄ) = 1 - \sum \limits_{k=1}^{K} \left(\frac{C_k}{|D|} \right)

其中,$C_k$是Ｄ中屬于第ｋ類的樣本子集，Ｋ是類的個數。

直覺來說，Gini(D)反映了從資料集D中随機抽取兩個樣本，其類别标記不一緻的機率。是以，Gini(D)越小，則資料集D的純度越高。

基尼指數的定義

如果樣本集合Ｄ根據特征Ａ是否取某一可能值a被分割成$D_1$和$D_2$兩部分，即

\[D_1 = \left\{(x,y)∈D｜A(x) = a\right\}, \quad D_2 = D_1

采用與資訊增益$Gain(D,A) = Ent(D) - \sum \limits_{k=1}^{K} \frac{|D^{k}|}{|D|}Ent(D^{k})$相同的符号表示，

則在特征Ａ的條件下，集合Ｄ的基尼指數定義為

\[Gini\_index(D,A) = Gini(D,A) = \sum \limits_{k=1}^{K} \frac{|D^{k}|}{|D|}Gini(D^{k})\\

= \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2) \\

基尼指數Gini(D)表示集合D的不确定性，基尼指數Gini(D,A)表示經A＝a分割後集合D的不确定性。

基尼指數的值越大，樣本集合的不确定性也就越大，這一點與熵相似。

于是，我們在候選屬性集合A中，選擇那個使得劃分後基尼指數最小的屬性作為最優劃分屬性，

即$A_{*} = \underset{a∈A}{\arg \min}$Gini_index(D,A).

下圖顯示二分類問題中基尼指數$Gini(p)$、熵（機關比特）的一半$\frac{H(p)}{2}$和分類誤差率的關系。

其中，橫坐标表示機率$p$，縱坐标表示損失。可以看出基尼指數和$\frac{H(p)}{2}$的曲線很接近，都可以近似地代表分類誤差率。

2.2 決策樹的生成算法

三種主要的決策樹算法：ID3, C4.5,CART

2.2.1、ID3決策樹學習算法

ID3的構造準則是資訊增益。

ID3算法的基本思想是，以資訊熵為度量，用于決策樹節點的屬性選擇，每次優先選取資訊量最多的屬性，亦即能使熵值變為最小的屬性，以構造一棵熵值下降最快的決策樹，到葉子節點處的熵值為0。此時，每個葉子節點對應的執行個體集中的執行個體屬于同一類。

[算法2]ID3算法

輸入：訓練資料集D，特征集A門檻值ε;

輸出：決策樹T。

（1）若D中所有執行個體屬于同一類$C_{k}$,則T為單節點樹，并将類$C_k$作為該節點的類标記，傳回T;

（2）若A=∅,則T為單節點樹，并将D中執行個體數最大的類$C_{k}$作為該節點的類标記，傳回T

（3）否則，按照資訊增益準則算法計算特征集A中各特征對資料集D的資訊增益，選擇資訊增益最大的特征值$A_{g}$;

（4）如果A_g的資訊增益小于門檻值ε,則置T為單節點樹，并将資料集D中執行個體數最大的類$C_{k}$作為該節點的類标記，傳回T;

（5）否則，對$A_g$的每一個可能值$a_{i}$，依據$A_g$=$a_i$将D分割為若幹個非空子集$D_i$，将$D_i$中執行個體數最大的類作為标記，建構子節點，由節點及其子節點構成樹T，傳回T;

（6）對第i個子節點，以$D_{i}$為訓練集，以$A-{A_{g}}$為特征集，遞歸地調用步驟(1)-步驟(5)，得到子樹$T_{i}$，傳回$T_i$

例題[2] 利用ID3算法建立決策樹

對下表的訓練資料集，利用ID3算法建立決策樹（來源-統計學習方法）

根據[例1]的結果，由于特征$A_3$(有自己的房子)的資訊增益值最大，是以選擇特征$A_3$作為根節點的特征。

它将訓練資料集D劃分為兩個子集$D_1$（有自己的的房子=是）,$D_2$（有自己的房子=否）。由于$D_1$隻有一類的樣本點，是以将它作為葉節點，節點的類标記為“是”。

對$D_2$則需從特征$A_1$(年齡),$A_2$(有工作)和$A_4$(信貸情況)中選擇新的特征。計算各個特征的資訊增益：

\[g(D_2,A_1) = H(D_2) - H(D_2|A_1) = 0.918 - 0.667 = 0.251 \\

g(D_2,A_2) = H(D_2) - H(D_2|A_2) = 0.918 - 0 = 0.918 \\

g(D_2,A_4) = H(D_2) - H(D_2|A_4) = 0.918 - 0.444 = 0.474

選擇資訊增益最大的特征$A_2$(有工作)作為節點的特征。由于$A_{2}$有兩個可能取值，從這一節點引出兩個子節點：

一個對應“是”（有工作）的子節點，包含3個樣本，它們屬于同一類，是以這是一個葉節點，類标記為“是”；

另一個是對應“否”（無工作）的子節點，包含6個樣本，它們也屬于同一類，這也是一個葉節點，類标記為“否”。

由圖可見，該決策樹隻用了兩個特征（有兩個内部節點）。

ID3算法隻有樹的生成，是以該算法生成的樹容易産生過拟合。

2.2.2、C4.5決策樹學習算法

C4,5算法與ID3算法相似，C4.5算法在ID3算法的基礎上進行了改進。C4.5在生成過程中，使用增益率（資訊增益比）來選擇特征（劃分屬性）。

[算法3]C4.5的生成算法

（1）如果資料集D中所有執行個體屬于同一類$C_{k}$，則置T為單節點=樹，并将$C_{k}$作為該節點的類，傳回T；

（2）如果A=∅，則置T為單節點樹，并将D中執行個體樹最大的類$C_{k}$作為該節點的類，傳回T；

（3）否則,按照$g_R(D,A) = \frac{g(D,A)}{H_{A}(D)}$計算A中各特征對D的資訊增益比，選擇資訊增益比最大的特征$A_{g}$；

（4）如果$A_{g}$的資訊增益比小于門檻值ε，則置T為單節點樹，并将D中執行個體數最大的類$C_{k}$作為該節點的類，傳回T；

（5）否則，對$A_{g}$的每一可能值$a_{i}$,依$A_{g} = a_{i}$将D分割為子集若幹非空$D_{i}$，将$D_{i}$中執行個體數最大的類作為标記，建構子節點，由節點及其子節點構成樹T，傳回T；

（6）對節點$i$，以$D_{i}$為訓練集，以A-{$A_{g}$}為特征集，遞歸地調用步驟(1)～步驟(5)，得到子樹$T_{i}$，傳回$T_{i}$。

連續與缺失值

連續值處理

現實學習任務中常會遇到連續屬性，有必要讨論如何在決策樹學習中使用連續屬性。

由于連續屬性的可取值數目不再有限，是以，不能直接根據連續屬性的可取值來對節點進行劃分。此時，就要用到連續屬性離散化技術。其中最簡單的政策是采用二分法（bi-partition）對連續屬性進行處理，這正是C4.5決策樹算法中采用的機制。

　　給定樣本集Ｄ和連續屬性A，假定Ａ在Ｄ上出現了n個不同的取值，将這些值從小到大排序，記為{$a^{1},a^{2},\cdots,a^{n}$}。基于劃分點$t$可将Ｄ分為子集$D_t^{-}$和$D_t^{+}$，其中$D_t^{-}$包含那些在屬性A上取值不大于t的樣本，而$D_t^{+}$則包含那些在屬性Ａ上取值大于t的樣本。

　　顯然，對相鄰的屬性取值$a^{i}$和$a^{i+1}$來說，$t$在區間[$a^i,a^{a+1}$)中取任意值所産生的劃分結果相同。是以，對于連續屬性Ａ，我們可考察包含n-1個元素的候選劃分點集合。

\[T_a = \left\{\frac{a^{i} + a^{a+1}}{2} \quad | 1 ≤ i ≤ n-1\right\}　\quad \quad (4.7)

即把區間[$a^{i}$, $a^{i+1}$)的中位點$\frac{a^{i}+a^{i+1}}{2}$作為候選劃分點。然後，我們就可像離散屬性值一樣來考察這些劃分點，選取最優的劃分點進行樣本集合的劃分。例如可對資訊增益公式$Gain(D,A) = Ent(D) - \sum \limits_{v=1}^{V} \frac{|D^{v}|}{|D|}Ent(D^{v})$進行改造

\[Gain(D,A) = \max \limits_{t∈T_a} Gain(D,A,t) \\

= \max \limits_{t∈T_a} Ent(D) - \sum \limits_{\lambda∈{(-,+})} \frac{|D_t^{\lambda}|}{|D|}Ent(D_t^{\lambda}) \quad \quad (4.8)

基于$Gain(D,A,t)$是樣本集合Ｄ基于劃分點t二分後的資訊增益。于是，我們就可選擇使$Gain(D,A,t)$最大化的劃分點。

　　對屬性“密度”，在決策樹學習開始時，根節點包含的17個訓練樣本在該屬性上取值均不同。根據$T_a = \left\{\frac{a^{i}+a^{i+1}}{2} \quad | 1 ≤ i ≤ n-1\right\}$,該屬性的候選劃分點集合包含16個候選值：$T_{密度}=${0.244,0.294,0.351,0.381,0.420,0.459,0.518,0.574,0.600,0.621,0.636,0.648,0.661,0.681,0.708,0.746}

由$Gain(D,A) = \max \limits_{t∈T_a} Gain(D,A,t) = \max \limits_{t∈T_a} Ent(D) - \sum \limits_{\lambda∈{(-,+})} \frac{|D_t^{\lambda}|}{|D|}Ent(D_t^{\lambda})$可計算出屬性“密度”的資訊增益為0.262，對應于0.381。

　　對屬性“含糖率”，其候選劃分點集合也包含16個候選值：

$T_{含糖率}＝${0.049,0.074,0.095,0.101.0,126,0.155,0.179,0.204,0.213,0.226,0.250,0.265,0.292,0.344,0.373,0.418}.類似的，根據上式可計算出屬性“含糖率”的資訊增益為0.349，對應于劃分點0.126。

　　再由于資訊增益準則，可知表上資料各屬性的資訊增益為：

\[Gain(D,色澤) = 0.109; \quad Gain(D,根蒂) = 0.143; \\

Gain(D,敲聲) = 0.141; \quad Gain(D,紋理) = 0.381; \\

Gain(D,臍部) = 0.289; \quad Gain(D,觸感) = 0.006; \\

Gain(D,密度) = 0.262; \quad Gain(D,含糖率) = 0.349.

　　于是，“紋理”被選作根節點劃分屬性，此後節點劃分過程遞歸進行，最終生成如下所示的決策樹

　　需注意的是，與離散屬性不同，若目前節點劃分屬性為連續屬性，該屬性還有可作為其後代節點的劃分屬性。

缺失值處理

　　現實任務中常會遇到不完整樣本，即樣本的某些屬性值缺失。例如由于診測成本、隐私保護等因素，患者的醫療資料在某些屬性上的取值（如HIV測試結果）未知；尤其是在屬性數目較多的情況下，往往會有大量樣本出現缺失值。如果簡單地放棄不完整樣本，僅使用無缺失值的樣本來進行學習，顯然是對資料資訊極大的浪費。

例如，下表是西瓜資料集2.0出現缺失值的版本，如果放棄不完整樣本，則僅有編号{4,7,14,16}的4個樣本能被使用。顯然，有必要考慮利用有缺失屬性值的訓練樣例來進行學習。

我們需解決兩個問題：

(1)如何在屬性值缺少的情況下進行劃分屬性選擇?

(2)給定劃分屬性，若樣本在該屬性上的值缺失，如何對樣本進行劃分？

給定訓練集Ｄ和屬性Ａ,令$\tilde{D}$表示D在屬性Ａ上沒有缺失值的樣本子集。

　　對于問題(1)，顯然我們僅可根據$\tilde{D}$來判斷屬性Ａ的優劣。假定屬性Ａ有Ｖ個可取值{$a^1,a^2,\cdots,a^V$}，令$\tilde{D^v}$表示$\tilde{D}$中在屬性a上取值為$a^v$的樣本子集，$\tilde{D_k}$表示$\tilde{D}$中屬于第k類(k=1,2,...,|y|)的樣本子集，則顯然有$\tilde{D}= U_{k=1}^{|y|}\tilde{D_k}$,$\tilde{D} = U_{v=1}^{V}\tilde{D^{v}}$。假定我們為每個樣本x賦予一個權重$w_x$，并定義

\[p = \frac{\sum_{x∈\tilde{D}}w_x}{\sum_{x∈D}w_x} \\

\tilde{p_k} = \frac{\sum_{x∈\tilde{D_k}}w_x}{\sum_{x∈\tilde{D}}w_x} (1≤k≤|y|)，\\

\tilde{r_v} = \frac{\sum_{x∈\tilde{D^v}}w_x}{\sum_{x∈\tilde{D}}w_x} (1≤v≤V).

　　直覺地看，對于屬性A,$p$表示無缺失值樣本所占的比例，$\tilde{p_k}$表示無缺失樣本中第ｋ類所占的比例，$\tilde{r_v}$則表示無缺失值樣本中在屬性a上取值$a^{v}$的樣本所占的比例。顯然，$\sum_{k=1}^{|y|}\tilde{p_k}=1$,$\sum_{v=1}^{V}\tilde{r_v}=1$.　　

　　基于上述定義，我們可将資訊增益的計算式推廣為

\[Gain(D,A) = p×Gain(\tilde{D},A) \\

= p×\left(Ent(\tilde{D})- \sum_{v=1}^{V}\tilde{r_v}Ent(\tilde{D^v})　\right)

其中由式$Ent(D) = -\sum\limits_{k=1}^{|y|}p_klog_2p_k$.有

\[Ent(\tilde{D})= -\sum \limits_{k=1}^{|y|}\tilde{p_k}log_2\tilde{p_k}

　　對于問題(2)，若樣本ｘ在劃分屬性Ａ上的取值已知，則将ｘ劃入與其取值對應的子節點，且樣本權值在子節點中保持為$w_x$。若樣本ｘ在劃分屬性A上的取值未知，則将ｘ同時劃入所有子節點，且樣本權植在與屬性值$a^v$對應的子節點中調整為$\tilde{r_v}*w_x$；

　　直覺地看，這就是讓同一個樣本以不同的機率劃入到不同的子節點中去。

接下來，我們以上面缺失資料的表為例來生成一棵決策樹。

在學習開始時，根節點包含樣本集Ｄ中全部17個樣例，各樣例的權值均為1。以屬性“色澤”為例，該屬性上無缺失值的樣例子集$\tilde{D}$包含編号為{2,3,4,6,7,8,9,10,11,12,14,15,16,17}的14個樣例。顯然，$\tilde{D}$的資訊熵為

\[Ent(\tilde{D}) = -\sum \limits_{k=1}^2\tilde{p_k}log_2\tilde{p_k} \\

= -(\frac{6}{14}log_2\frac{6}{14}+\frac{8}{14}log_2\frac{8}{14}) = 0.985.

令$\tilde{D^1},\tilde{D^2}$與$\tilde{D^3}$分别表示在屬性“色澤”上取值為“青綠”，“烏黑”以及“淺白”的樣本子集，有

\[Ent(\tilde{D^1}) = -(\frac{2}{4}log_2\frac{2}{4} + \frac{2}{4}log_2\frac{2}{4}) = 1.000 \\Ent(\tilde{D^2}) = -(\frac{4}{6}log_2\frac{4}{6} + \frac{2}{6}log_2\frac{2}{6}) = 0.918\\Ent(\tilde{D^3}) = -(\frac{0}{4}log_2\frac{0}{4} + \frac{2}{6}log_2\frac{2}{6}) = 0.000.

是以，樣本子集$\tilde{D}$上屬性“色澤”的資訊增益為

\[Gain(\tilde{D},色澤) = Ent(\tilde{D} - \sum \limits_{v=1}^{3}\tilde{r_v}Ent(

\tilde{D^v})) \\

= 0.985 - (\frac{4}{14}×1.000+\frac{6}{14}×0.918+\frac{4}{14}×0.000)\\

= 0.306

于是，樣本集Ｄ上屬性“色澤”的資訊增益為

\[Gain(D,色澤) = p×Gain(\tilde{D},色澤) = \frac{14}{17}×0.306 = 0.252

類似地，可計算出所有屬性在Ｄ上的資訊增益:

\[Gain(D,色澤) = 0.252; \quad Gain(D,根蒂) = 0.171; \\

Gain(D,敲聲) = 0.145; \quad Gain(D,紋理) = 0.424; \\

Gain(D,臍部) = 0.289; \quad Gain(D,觸感) = 0.006.

　　“紋理”在所有屬性中取得了最大的資訊增益，被用于對根節點進行劃分。劃分結果是使編号為{1,2,3,4,5,6,15}的樣本進入“紋理＝清晰”分支，編号為{7,9,13,14,17}的樣本進入“紋理＝稍糊”分支，而編号為{11,12,16}的樣本進入“紋理＝模糊”分支，且樣本在各子節點中的權重保持為1。

　　需注意的是，編号為{8}的樣本在屬性“紋理”上出現了缺失值，是以它将同時将進入三個分支中，但權重在三個子節點中分别調整為$\frac{7}{15}、\frac{5}{15}、\frac{3}{15}$。編号為{10}的樣本有類似劃分結果。

　　上述節點劃分過程遞歸執行，最終生成的決策樹如下圖所示。　　

2.2.3、CART決策樹學習算法

CART決策樹[分類與回歸樹(classification and regression tree，CART)] [Breiman et al.,1984]由Breiman等人在1984年提出，是應用廣泛的決策樹學習方法。使用“基尼指數”（Gini index）來選擇劃分屬性（特征）。

CART同樣由特征選擇、樹的生成及剪枝組成，既可以用于分類也可以用于回歸。

CART是在給定輸入随機變量X條件下輸出随機變量Y的條件機率分布的學習方法。CART假設決策樹是二叉樹，内部節點特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價于遞歸地二分每個特征，将輸入空間（即特征空間）劃分為有限個單元，并在這些單元上确定預測的機率分布，也就是在輸入給定的條件下輸出的條件機率分布。

CART算法由以下兩步組成：

(1) 決策樹生成：基于訓練資料集生成決策樹，生成的決策樹要盡量大；

(2) 決策樹剪枝：用驗證資料集對已生成的樹進行剪枝并選擇最優子樹，此時改用損失函數最小作為減枝的标準。

2.2.3.1 CART決策樹生成

2.2.3.1.1 回歸樹的生成

對回歸樹用平均誤差最小化準則。

假設X和Y分别為輸入變量和輸出變量，并且輸出變量Y是連續變量，給定訓練資料集

\[D = {(x_1,y_1), (x_2,y_2),\cdots, (x_{N},y_{N})}

下面考慮如何生成回歸樹：

　　一棵回歸樹對應着輸入空間(即特征空間)的一個劃分以及在劃分的單元上的輸出值。假設已将輸入空間劃分為M個單元$R_1,R_2,\cdots,R_M$,并且在每個單元$R_m$上有一個固定的輸出值$c_m$，于是回歸樹模型可表示為

\[f(x) = \sum \limits_{m=1}^{M}c_mI \quad (X ∈ R_m)

接下來需要對輸出空間Ｘ進行空間劃分，這裡采用啟發式的方法：

選擇第j個變量$x^{(j)}$作為切分變量（splitting variable）,選擇變量$x^{(j)}$的取值$s$作為切分點（splitting point），進而可以得到兩個區域：

\[Ｒ_{1}(j,s) = \left\{x|x^{j} ≤s \right\} \\

Ｒ_{2}(j,s) = \left\{x|x^{j} ≥ s\right\}

然後在空間區域中尋找最優切分變量$j$和最優切分點$s$。

　　具體求解如下：

　　當輸入空間Ｘ的劃分确定時，則可以平方誤差$\sum \limits_{x_{i} ∈ R_{m}}(y_i - f(x_i))^{2}$來表示回歸樹對于訓練資料的預測誤差，用平方誤差最小的準則來求解每個單元上的最優輸出值。

\[\underset{j,s}min \left[ \underset{c_1} min　\sum \limits_{x_i∈R_1(j,s)}(y_i-c_1)^2 + \underset{c_2} min \sum \limits_{x_i∈R_2(j,s)}(y_i - c_2)^2 \right]

　　周遊變量$j$，對固定的切分變量$j$掃描切分點$s$，選擇使上式達最小值的對象$(j,s)$.　　

　　易知，單元$R_m$上的$c_m$的最優值$\hat c_m$是$R_m$上的所有輸入執行個體$x_i$對應的輸出$y_i$的均值，即

\[\hat c_m = ave(y_i|x_i ∈ R_m)

　　對固定輸入變量$j$可以找到最優切分點$s$。

\[\hat c_1 = ave(y_i|x_i ∈ R_1(j,s)) \\

\hat c_2 = ave(y_i|x_i ∈ R_2(j,s))

　　周遊所有輸入變量，找到最優的切分變量$j$，構成一個對$(j,s)$。依次将輸入空間Ｘ劃分為兩個區域。

接着，對每個區域重複上述劃分過程，直到滿足停止條件為止。這樣就生成一棵“最小二乘回顧樹”（least squares regression tree）。　　

[算法4]（最小二乘回歸樹生成算法）

輸入：訓練資料集；

輸出：回歸樹$f(x)$。

在訓練資料集合所在的輸入空間Ｘ中，遞歸地将每個區域劃分為兩個子區域并決定每個子區域熵的輸出值，建構二叉決策樹；

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

周遊變量$j$，對固定的切分變量$j$掃描切分點$s$，選擇使上式達最小值的對象$(j,s)$.

（2）用標明的對$(j,s)$劃分區域并決定相應的輸出值：

\[Ｒ_1(j,s) = \left\{x|x^{(j)} \leq s\right\},Ｒ_2(j,s) = \left\{x|x^{(j)} > s\right\} \\

\hat c_m = \frac{1}{N_m} \sum \limits_{x_i∈R_m(j,s)}y_i, \quad x∈R_m, m＝1,2

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

（4）将輸入空間劃分為Ｍ個區域$R_1,R_2,\cdots,R_M$,生成決策樹：

\[f(x) = \sum \limits_{m=1}^{M} \hat c_mI \quad (x∈R_m)

2.2.3.1.2 分類樹的生成

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

[算法5]（CRAT生成算法）

輸入：訓練資料集D,停止計算的條件

輸出：CART決策樹

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

（1）設節點的訓練資料集為D，計算現有特征對該資料集的基尼指數。此時，對每一個特征A，對其可能取得的每個值a，根據樣本點對A = a的測試為“是”或“否”，将D分割為$D_{1}$和$D_2$兩部分，利用基尼指數的定義式$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$計算A=a時的基尼指數。

（2）在所有可能的特征A以及它們所有可能的切分點a中，選擇基尼指數最小的特征及其對應的切分點作為最優特征和最優切分點。依最優特征與最優切分點，從現節點生成兩個子節點，将訓練資料集依特征配置設定到兩個子節點中去。

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

（4）生成CART決策樹。

算法停止計算的條件是，節點中的樣本個數小于預定門檻值，或樣本集的基尼指數小于預定門檻值（樣本基本屬于同一類），或者沒有更多特征。

例題[3]應用CART算法生成決策樹。

根據下表所給訓練資料集，應用CART算法生成決策樹。

解　首先計算各特征的基尼指數，選擇最優特征以及其最優切分點。j将A分别記為:{$A_1$(年齡),$A_2$(有工作),$A_3$(有自己的房子),$A_4$(信貸情況)}, 其中$A_1${($A_1=1$,青年)，($A_1=2$,中年)，($A_3=1$,老年)}；$A_2${($A_2=1$,是)，($A_2=2$,否)}；$A_3${($A_3=1$,非常好)，($A_3=2$,好)(，$A_3=3$,一般)}；

求特征$A_1$的基尼指數：

\[Gini(D,A_1 = 1) = \frac{5}{15}(2×\frac{2}{5}×(1-\frac{2}{5})) + \frac{10}{15}(2×\frac{7}{10}×(1-\frac{7}{10})) = 0.44 \\

Gini(D,A_1 = 2) = 0.48 \\

Gini(D,A_1 = 3) = 0.44

由于$Gini(D,A_1 = 1)$和$Gini(D,A_1 = 3)$相等，且最小，是以$A_1 = 1$和$A_1 = 3$都可以選作$A_1$的最優切分點。

求特征$A_2$和$A_3$的基尼指數：

\[Gini(D,A_2 = 1) = 0.32 \\

Gini(D,A_3 = 1) = 0.27

由于$A_2$和$A_3$隻有一個切分點，是以它們就是最優切分點。

求特征$A_4$的基尼指數：

\[Gini(D, A_4 = 1) = 0.36 \\

Gini(D, A_4 = 2) = 0.47 \\

Gini(D, A_4 = 3) = 0.32

$Gini(D, A_4=3)$最小，是以$A_4=3$為$A_4$的最優切分點。

在$A_1$,$A_2$,$A_3$,$A_4$幾個特征中，$Gini(D, A_3 = 1)$ = 0.27最小，是以選擇特征$A_3$為最優特征,$A_3=1$為其最優切分點。于是根節點生成兩個子節點，一個是葉節點，對另外一個節點繼續使用以上方法在$A_1,A_2,A_4$中選擇最優特征及其最優切分點，結果是$A_2=1$。依次計算得知，所得節點都是葉節點。

以下，為生成的決策樹，與按照ID3算法所生成的決策樹完全一緻。

2.2.3.2 CART決策樹剪枝

CART剪枝算法的作用：從“完全生長”的決策樹的低端剪去一些子樹，使決策樹變小(模型變簡單)，進而能夠使得對未知資料有更準确的預測。

CART剪枝算法的步驟：

(1) 首先，從生成算法産生的決策樹$T_{0}$底端開始不斷剪枝，直到$T_{0}$的根節點，形成一個子樹序列${T_0,T_1,\cdots,T_n}$

(2) 然後，通過交叉驗證法在獨立的驗證資料集熵對子樹序列進行測試，從中選擇最優子樹。

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

在剪枝過程中，計算子樹的損失函數:

\[C_\alpha(T)　＝　C(T) + \alpha|T|

其中，Ｔ為任意子樹，Ｃ(Ｔ)為對訓練資料的預測誤差（如基尼指數）,$|T|$為子樹的葉節點個數，$\alpha≥0$為參數，$C_{\alpha}(T)$為參數是$\alpha$時的子樹Ｔ的整體損失。參數$\alpha$權衡訓練資料的拟合程度與模型的複雜度。

對固定的$\alpha$為，一定存在使損失函數$C_{\alpha}(T)$最小的子樹，将其表示為$T_{\alpha}$。$T_{\alpha}$在損失函數$C_{\alpha}(T)$最小的意義下是最優的。容易驗證，這樣的最優子樹是唯一的。

\[\left\{\begin{matrix}

當\alpha大的時候，最優子樹T_{\alpha}偏小； \\

當\alpha小的時候，最優子樹T_{\alpha}偏大。 \\

極端情況，當\alpha＝０時，整體樹是最優的。 \\

當\alpha → ∞時，根節點組成的單節點樹是最優的。

\end{matrix}\right.

[Breiman等人]證明：可以用遞歸的方法對樹進行剪枝。

　　将$\alpha$從小增大，$0 = \alpha_0 < \alpha_1 < \cdots< +∞$,産生一系列的區間[$\alpha_i$, $\alpha_{i+1}$),$i=0,1,\cdots,n$:剪枝後得到的子樹序列對應着區間$\alpha∈[\alpha_{i},\alpha_{i+1})$，$i=0,1,\cdots,n$的最優子樹序列${T_0,T_1,\cdots,T_n}$，序列中的子樹是嵌套的。

具體地，從整體樹$T_0$開始剪枝。

對$T_0$的任意内部節點t，以t為單節點樹的損失函數是：

\[C_{\alpha}(t) = C(t) + \alpha

以$t$為根節點的子樹$T_t$的損失函數是

\[Ｃ_{\alpha}(T_t) = C(T_t) + \alpha|T_t|

當$\alpha=0$及$\alpha$充分小時，有不等式

\[C_{\alpha}(T_{\alpha}) < C_{\alpha}(t)

當$\alpha$增大時，在某一$\alpha$有

\[C_{\alpha}(T_t) = C_{\alpha}(t)

當$\alpha$再增大時，不等式$C_{\alpha}(T_{\alpha}) < C_{\alpha}(t)$反向為$C_{\alpha}(T_{\alpha}) > C_{\alpha}(t)$.

隻要$\alpha = \frac{C(t)-C(T_t)}{|T_t|-1}$,$T_t$與$t$有相同的損失函數值，而$t$的節點稍，是以$t$比$T_t$更可取，對$T_t$進行剪枝。

為此，對$T_0$中每一内部節點$t$，計算

\[g(t) = \frac{C(t) - C(T_t)}{|T_t|-1}

g(t)表示，剪枝後整體損失函數減少的程度。在$T_0$中剪去g(t)最小的$T_t$，将得到的子樹作為$T_1$,同時将最小的$g(t)$設為$\alpha_1$。$T_1$為區間$[\alpha_1, \alpha_2)$的最優子樹。

如此剪枝下去，直至得到根節點。在這一過程中，不斷地增加$\alpha$的值，産生新的區間。

2.在剪枝得到的子樹序列$T_0,T_1,\cdots,T_n$中通過交叉驗證選取最優子樹$T_{\alpha}$。

具體地，利用獨立的驗證資料集，測試子樹序列$T_0,T_1,\cdots,T_n$中各個子樹的平方誤差或基尼指數。平方誤差或基尼指數最小的決策樹被認為是最優的決策樹。在子樹序列中，每棵子樹$T_1,T_2,\cdots,T_n$都對應一個參數$\alpha_1,\alpha_2,\cdots,\alpha_n$。是以，當最優子樹$T_{k}$确定時，對應的$\alpha_k$也就确定了，也即得到了最優決策樹$T_{\alpha}$.

[算法]（CART剪枝算法）

輸入：CART算法生成的決策樹Ｔ

輸出：最優決策樹$T_{\alpha}$.

（1）設$k = 0,T = T_0$.

（2）設$\alpha = ∞$.

（3）自下而上地對各内部節點$t$計算$C(T_t)$，$|T_{t}|$以及

\[g(t) = \frac{C(t) - C(T_{t})}{|T_t| - 1} \\

\alpha = min(\alpha, g(t))

其中，$T_t$表示以ｔ為根節點的子樹，$C(T_t)$是對訓練資料的預測誤差，$|T_t|$是$T_{t}$的葉節點個數。

（4）對$g(t) = \alpha$的内部節點t進行剪枝，并對葉節點t以多數表決法決定其類，得到樹T

（5）設$k = k+1,\alpha_k = \alpha,T_k = T$.

（6）如果$T_k$不是由根節點及兩個葉節點構成的樹，則回到步驟(2)；否則令$T_k = T_n$。

（7）采用交叉驗證法在子樹序列$T_0,T_1,\cdots,T_n$中選擇最優子樹$T_{\alpha}$.

2.3 決策樹的剪枝算法

2.3.1 決策樹剪枝的基本概念

　　決策樹生成算法遞歸地産生決策樹，直到不同繼續下去為止。這樣産生的樹往往對訓練資料的分類很準确，但對未知的測試資料的分類卻沒有那麼準确，也即出現“過拟合”現象。過拟合的原因在于學習時過多的考慮如何提高對訓練資料的正确分類，以至于把訓練集自身的一些特點當作所有資料都具有的一般性質，進而建構出在于複雜的決策樹。解決這個問題的辦法是考慮決策樹的複雜度，對已生成的決策樹進行簡化。

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

　　這裡介紹一種簡單的決策樹學習的剪枝算法。

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

\[C_{\alpha}(T) = \sum \limits_{t=1}^{|T|}N_tH_t(T) + \alpha|T|

其中，經驗熵為

\[H_t(T) = -\sum \limits_{k}\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}

在損失函數中，将$C_{\alpha}(T) = \sum \limits_{t=1}^{|T|}N_tH_t(T) + \alpha|T|$中的$\sum \limits_{t=1}^{|T|}N_tH_t(T)$記作

\[C(T) = \sum \limits_{t=1}^{|T|}N_tH_t(T) = -\sum \limits_{t=1}^{|T|}\sum \limits_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}

這時有

\[C_{\alpha}(T) = C(T) + \alpha|T|

其中，$C(T)$(表示模型對訓練資料的預測誤差，也即為模型與訓練資料的拟合程度)，$|T|$表示模型複雜度，

\[\alpha ≥ 0控制兩者之間的影響。

\left\{\begin{matrix}

\alpha=0,意味着隻考慮模型與訓練資料的拟合程度，不考慮模型的複雜度。\\

較大的\alpha,促使選擇較簡單的模型（樹）\\

較小的\alpha,促使選擇較複雜的模型（樹）

　　所謂剪枝，就是當$\alpha$确定時，選擇損失函數最小的模型，即損失函數最小的子樹。當$\alpha$值确定時，子樹越大，往往與訓練資料的拟合越好，但是模型的複雜度就越高；相反，子樹越小，模型的複雜度就越低，但是往往與訓練資料的拟合不好。損失函數正好表示了對兩者的平衡。

　　從上面可以看出，決策樹生成值考慮了通過提高資訊增益（或資訊增益比）對訓練資料進行更好的拟合。而決策樹剪枝通過優化損失函數還考慮了減少模型複雜度。決策樹生成學習局部的模型，而決策樹剪枝葉學習整體的模型。

　　$C_{\alpha}(T) = \sum \limits_{t=1}^{|T|}N_tH_t(T) + \alpha|T|$或$C_{\alpha}(T) = C(T) + \alpha|T|$定義的損失函數的極小化，等價于正則化的極大似然估計。是以，利用損失函數最小原則進行剪枝，就是用正則化的極大似然估計進行模型原則的。

下圖為決策樹剪枝過程的示意圖。

[算法6]（樹的剪枝算法）

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

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

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

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

　　設一組葉節點回縮到其父節點之前與之後的整體樹分别為$T_{B}$與$T_{A}$，其對應的損失函數值分别是$C_{\alpha}(T_A)$與$C_{\alpha}(T_B)$，如果$C_{\alpha}(T_{A})≤ C_{\alpha}(T_B)$,則進行剪枝，也即為将父節點變為新的葉節點。

（3）傳回(2)，直至不能繼續為止，得到損失函數最小的子樹$T_{\alpha}$。

[注意]對于$C_{\alpha}(T_{A})≤ C_{\alpha}(T_B)$隻需考慮兩個樹的損失函數的差，其計算可以在局部進行。是以，決策樹的剪枝算法可以由一種動态規劃的算法實作。

2.3.2 決策樹剪枝的基本政策

　　決策樹剪枝的基本政策有：“預剪枝”（pre-pruning）和“後剪枝”（post-pruning）[Quilan,1993]。

“預剪枝”是指在決策樹生成過程中，對每個節點在劃分前進行估計，若目前節點的劃分不能帶來決策樹泛化性能提升，則停止劃分并将目前節點标記為葉節點；

“後剪枝”則是先從訓練集生成一棵完整的決策樹，帶來決策樹泛化性能提升，則将該子樹替換為葉節點。

　　如何判斷決策樹泛化性能是否提升呢？可以使用性能評估方法。

假定采用留出法，即預留一部分資料用作“驗證集”以進行性能評估。

例如，對西瓜資料集2.0，我們将其随機劃分為兩部分，如下表所示。

編号為{1,2,3,6,7,10,14,15,16,17}的樣例組成訓練集，

編号為{4,5,8,9,11,12,13}的樣例組成驗證集。

假定我們采用資訊增益準則來進行劃分屬性選擇，則從西瓜資料集2.0将會生成一棵如下圖所示的決策樹

(1)預剪枝

基于資訊增益準則，我們對于上圖決策樹，會選取屬性“臍部”來對訓練集進行劃分，并産生三個分支。

如下圖所示

然而，是否應該進行這個劃分呢？預剪枝要對劃分前後的泛化性能進行估計。

　　在劃分之前，所有的樣例集中在根節點。若不進行劃分，則情況為{屬性集Ａ=∅ OR 訓練集D中樣本在Ａ上取值相同},則{将該生成節點node标記為葉節點，其類别标記為Ｄ中樣本數最多的類}。假設我們将這個節點标記為“好瓜”。并且，用西瓜資料集2.0劃分的驗證集對這個單節點決策樹進行評估，則編号為{4,5,8}的樣例被分類正确，另外4個樣例分類錯誤，于是，驗證集精度為$\frac{3}{7}×100 = 42.9%$.

　　在用屬性“臍部”劃分之後，上圖決策樹中的節點②包含了{1,2,3,14}的訓練樣例,該節點被标記為“好瓜”

節點③包含了{6,7,15,17}的訓練樣例,該節點被标記為“好瓜”

節點④包含了{10,16}的訓練樣例，該節點被标記為“壞瓜”

此時，驗證集中編号為{4,5,8,11,12}的樣例被分類正确，驗證集精度為$\frac{5}{7}×100%$=71.4% > 42.9%.于是，用“臍部”進行劃分得以确定。

　　然後，決策樹算法應該對節點②進行劃分，基于資訊增益準則将挑選出劃分屬性“色澤”。然後，在使用“色澤”劃分後，編号為{5}的驗證集樣本分類結果會由正确轉向錯誤，使得驗證集精度下降為57.1%。于是，預先剪枝政策将禁止節點②被劃分。

　　對于節點③,最優劃分屬性為“根蒂”，劃分後驗證精度仍為71.4%，這個劃分不能提升驗證集精度，于是，預剪枝政策禁止節點③被劃分

　　對于節點④，其所含訓練樣例已屬于同一類，不再進行劃分。

于是，基于預剪枝政策所生成的決策樹，其驗證集合精度為71.4%。這是一棵僅有一層劃分的決策樹，亦稱“決策樹樁”（decision stump）。

對比以上，可以看出，預剪枝使得決策樹的很多分支都沒有“展開”，這不僅降低了過拟合的風險，還顯著減少了決策樹的訓練時間開銷，但另一方面，有些分支的目前劃分雖不能提升泛化性能、甚至可能導緻泛化性能暫時下降，但在其基礎上進行的後續劃分卻有可能導緻性能顯著提高；預剪枝基于“貪心”本質，禁止這些分支展開，給預剪枝決策樹帶來了欠拟合的風險。

(2)後剪枝

後剪枝先從訓練集生成一棵完整決策樹

後剪枝首先考察上圖節點⑥。若能将其領銜的分支剪除，則相當于是把⑥替換為葉節點。于是，該葉節點的類别标記為“好瓜”，此時決策樹驗證集精度提高至57.1%,于是，後剪枝政策決定剪枝。

然後考察節點⑤，若将其領銜的子樹替換為葉節點，則替換後的葉節點包含編号為{6,7,15}的訓練樣例，葉節點類别标記為“好瓜”，此時決策樹驗證集精度仍為57.1%,于是可以不進行剪枝。

對節點③和①，若将其領銜的子樹替換為葉節點，則所得決策樹的驗證集精度分别為71.4%與42.9%，均未得到提高，于是将它們保留。

最終，基于後剪枝政策從西瓜資料2.0所生成的決策樹，如下圖所示，其驗證集精度為71.4%.

對比可以看出，後剪枝決策樹通常比預剪枝決策樹保留了更多的分支。一般情形下，後剪枝決策樹的欠拟合風險很小，泛化性能往往優于預剪枝決策樹。但後剪枝過程是在生成完全決策樹隻有進行的，并且要自底向上地對樹中的所有非葉節點進行逐一考察，是以其訓練時間開銷比未剪枝決策樹和預剪枝決策樹都要大得多。

若我們把每個屬性視為坐标空間中的一個坐标軸，則d個屬性描述的樣本就對應了d維空間中的一個資料點，對樣本分類則意味着在這個坐标空間中尋找不同類樣本之間的分類邊界。決策樹所形成的分類邊界有一個明顯的特點：軸平行（axis-parallel）,也即它的分類邊界由若幹個與坐标軸平行的分段組成。

以下表的西瓜資料3.0$\alpha$為例，

将它作為訓練集合可得到下圖所示的決策樹

這棵樹所對應的分類邊界如下圖所示

由上圖可以看出，顯然，分類邊界的每一段都是與坐标軸平行的。這樣的分類邊界使得學習結果有較好的可解釋性，因為每一段劃分都直接對應了某個屬性取值。但在學習任務的真實分類邊界比較複雜時，必須使用很多段才能獲得較好的近似。

對上圖的解釋：

對應着生成的決策樹，來看一看上圖的邊界是怎麼畫出來的：

在下圖中，黑色正斜杠( / )陰影部分表示已确定标記為壞瓜的樣例，紅色反斜杠( \ )陰影部分表示已确定标記好瓜的樣例，空白部分表示需要進一步劃分的樣例。

第一次劃分條件是“含糖率$\leq$0.126?”，滿足此條件的樣例直接标記為壞瓜(如圖(a)黑色陰影部分所示)，而不滿足此條件的樣例還需要進一步劃分(如圖(a)空白部分所示);

在第一次劃分的基礎上對圖(a)空白部分繼續進行劃分，第二次劃分的條件是“密度$\leq$0.381?”，滿足此條件的樣例直接被标記為壞瓜(如圖(b)黑色陰影部分所示)，而不滿足此條件的樣例還需要進一步劃分(如圖(b)空白部分所示)；

在第二次劃分的基礎上對圖(b)空白部分繼續進行劃分，第三次劃分條件是"含糖率$\leq$0.205?"，不滿足此條件的樣例直接标記為好瓜(如圖(c)新增紅色陰影部分所示)，而且，而滿足此條件的樣例還需進一步劃分(如圖(c)空白部分所示)；

第三次劃分的基礎上對圖(c)空白部分繼續進行劃分，第四次劃分的條件是“密度$\leq$0.560?”，滿足此條件的樣例直接标記為好瓜(如圖(d)新增紅色陰影部分所示)，而不滿足此條件的樣例直接标記為壞瓜(如圖(d)新增黑色陰影部分所示)。

經過四次劃分已無空白部分，表示決策樹生成完畢。

從圖(d)中可以清晰地看出好瓜與壞瓜的分類邊界。

複雜分類邊界的分段近似如下圖所示

顯然，此時的決策樹分類複雜，由于要進行大量的屬性測試，預測時間開銷會很大。

　　若能使用斜的劃分邊界。如上圖紅色線段所示，則決策樹模型将大為簡化。“多變量決策樹”（multivariate decision tree）就是能實作這樣的“斜劃分”甚至更複雜劃分的決策樹。以實作斜劃分的多變量決策樹為例，在此類決策樹中，非葉節點不再是僅對某個屬性，而是對屬性的線性組合進行測試；換言之，每個非葉節點是一個形如$\sum_{i=1}^{d}w_ia_i = t$的線性分類器，其中$w_i$是屬性$a_i$的權重，$w_i$和$t$可在該節點所含的樣本集和屬性集上學得。于是，與傳統的“單變量決策樹”（univariate decision tree）不同，在多變量決策樹的學習過程中，不是為每個非葉節點尋找一個最優劃分屬性，而是試圖建立一個合适的線性分類器。

　　例如對西瓜資料集3.0$\alpha$，我們可學得下圖所示的多變量決策樹

其分類邊界如下圖所示

上圖共有兩條分類邊界

左邊一條為一次函數“－0.800×密度-0.044×含糖率 = -0.313”;

右邊一條為一次函數"-0.365×密度-0.366×含糖率= -0.158";

為更友善了解，可将含糖率替換為$y$，将密度替換為$x$。

關于判斷直線的哪一側大于零，哪一側小于令，簡單來說，法向量方向即為大于零的區域。

例如直線“0.800×密度-0.044×含糖率+0.313=0”，法向量為(-0.800, -0.044)，指向第三象限，為“-0.800×密度-0.044×含糖率+0.313>0”，是以上圖左邊左邊直線的左側為“壞瓜”，這是因為當“0.800×密度-0.044×含糖率+0.313$\leq$0”不成立時(即大于零)為壞瓜。

另外需要注意的是，這裡所要劃分的區域僅是第一象限，因為兩個屬性“含糖率”和“密度”的取值範圍均為正值。

參考材料

[1]周志華《機器學習》

[2]李航《統計學習方法》

Talk is cheap. Show me the code