決策樹
martin
- 決策樹
- 基本概念
- ID3
- C45
- CART
- 剪枝處理
- 前剪枝
- 後剪枝
基本概念
一般的，一顆決策樹包含一個根節點、若幹個内部節點和若幹個葉節點，是以決策樹相當于多叉樹。葉節點對應于決策結果，其他每個結點則對應與一個屬性測試，每個節點包含的樣本集合根據屬性測試的結果被分到子節點中。決策樹學習的目的是為了産生一棵泛化能力強，即處理未見示例能力的決策樹，基本思想遵循“分而治之”的政策。
決策樹的生成是一個遞歸過程。在決策樹算法中有三種情形會導緻遞歸傳回：
- 目前節點包含的樣本全部屬于同一個類别，無需劃分。
- 目前屬性集為空，或是所有樣本在所有屬性集上取值相同，無法劃分。此時，把目前節點标記為葉節點，并将其類别設定為該節點所含樣本最多的類别。
- 目前節點包含的樣本集合為空，不能劃分。此時，同樣把目前節點标記為葉節點，但将其類别設定為其父節點所含樣本最多的類别。
注意：2和3不同，2是後驗機率，3是把父節點的樣本分布作為目前節點的先驗機率。
下面給出一個決策樹的例子：
決策樹相當于對特征空間進行劃分，如下：
也就是說，決策樹的每條路徑對應于特征空間的每個區域。對于決策樹主要有以下幾種：ID3，C4.5主要應用于分類任務；CART樹，主要應用于預測任務，下面将逐個介紹。
ID3
對于之前給出的決策樹的節點劃分在ID3中有特定的方法，ID3中節點劃分所衡量的名額是：資訊增益。
資訊熵：E(D)=−∑k=1ypklog2pk
特征a的資訊增益：Gain(D,a)=E(D)−∑v=1v|Dv||D|E(Dv)
一般而言，資訊增益越大，則意味着使用屬性 α 來進行劃分所獲得的的“純度提升”越大。是以，我們可用資訊增益來進行決策樹的劃分屬性選擇。
給一個資料集，我們在這個資料集上來進行ID3決策樹的生成：
| 編号 | 色澤 | 根蒂 | 敲聲 | 紋理 | 臍部 | 觸感 | 好瓜 |
|---|---|---|---|---|---|---|---|
| 1 | 青綠 | 蜷縮 | 濁響 | 清晰 | 凹陷 | 硬滑 | 是 |
| 2 | 烏黑 | 蜷縮 | 沉悶 | 清晰 | 凹陷 | 硬滑 | 是 |
| 3 | 烏黑 | 蜷縮 | 濁響 | 清晰 | 凹陷 | 硬滑 | 是 |
| 4 | 青綠 | 蜷縮 | 沉悶 | 清晰 | 凹陷 | 硬滑 | 是 |
| 5 | 淺白 | 蜷縮 | 濁響 | 清晰 | 凹陷 | 硬滑 | 是 |
| 6 | 青綠 | 稍蜷 | 濁響 | 清晰 | 稍凹 | 軟粘 | 是 |
| 7 | 烏黑 | 稍蜷 | 濁響 | 稍糊 | 稍凹 | 軟粘 | 是 |
| 8 | 烏黑 | 稍蜷 | 濁響 | 清晰 | 稍凹 | 硬滑 | 是 |
| 9 | 烏黑 | 稍蜷 | 沉悶 | 稍糊 | 稍凹 | 硬滑 | 否 |
| 10 | 青綠 | 硬挺 | 清脆 | 清晰 | 平坦 | 軟粘 | 否 |
| 11 | 淺白 | 硬挺 | 清脆 | 模糊 | 平坦 | 硬滑 | 否 |
| 12 | 淺白 | 蜷縮 | 濁響 | 模糊 | 平坦 | 軟粘 | 否 |
| 13 | 青綠 | 稍蜷 | 濁響 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 14 | 淺白 | 稍蜷 | 沉悶 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 15 | 烏黑 | 稍蜷 | 濁響 | 清晰 | 稍凹 | 軟粘 | 否 |
| 16 | 淺白 | 蜷縮 | 濁響 | 模糊 | 平坦 | 硬滑 | 否 |
| 17 | 青綠 | 蜷縮 | 沉悶 | 稍糊 | 稍凹 | 硬滑 | 否 |
然後，我們要計算出目前屬性集合 {色澤，根蒂，敲聲，紋理，臍部，觸感} 中每個屬性的資訊增益。
先計算根節點的資訊熵：
E(D)=−∑k=12pklog2pk=−(817log2817+917log2917)=0.998
計算屬性“ 色澤 ”的資訊增益，它有3個可能取的值： {青綠，烏黑，淺白} ，分别記為：
D1(色澤=青綠) ，包含編号為 {1,4,6,10,13,17} 6個樣例，于是 p1=36,p2=36 ，
D2(色澤=烏黑) ，包含編号為 {2,3,7,8,9,15} 6個樣例，于是 p1=46,p2=26 ，
D3(色澤=淺白) ，包含編号為 {5,11,12,14,16} 5個樣例，于是 p1=15,p2=45 ，
有了上面的資訊就可以求該特征的每個屬性的資訊熵了：
E(D1)=−36log2(36)−36log2(36)=1.000
E(D2)=−46log2(46)−26log2(26)=0.918
E(D3)=−15log2(15)−45log2(45)=0.722
于是，可以計算出屬性色澤的資訊增益：
Gain(D,色澤)=E(D)−∑v=13|Dv||D|E(Dv)=0.998−(617×1.000+617×0.918+517×0.722)=0.109
類似的，我們可以計算出其他屬性的資訊增益：
Gain(D,根蒂)=0.143
Gain(D,敲聲)=0.141
Gain(D,紋理)=0.381
Gain(D,臍部)=0.289
Gain(D,觸感)=0.006
顯然，屬性紋理的資訊增益最大，于是它被選為劃分屬性，給出基于紋理對根節點進行劃分的結果：
然後，決策樹學習算法将對每個分之節點做進一步劃分。以上圖第一個分支節點(紋理=清晰)為例，該節點包含的樣例集合 D1 中有編号為 {1,2,3,4,5,6,8,10,15} 的9各樣例，可用屬性集合為 {色澤，根蒂，敲聲，臍部，觸感} ，少了一個紋理屬性。基于 D1 計算出各個屬性的資訊增益：
先計算第一個分支節點的資訊熵：
E(D1)=−∑k=12pklog2pk=−(79log279+29log229)=0.764
計算屬性“ 色澤 ”的資訊增益，它有3個可能取的值： {青綠，烏黑，淺白} ，分别記為：
D1(色澤=青綠) ，包含編号為 {1,4,6,10} 4個樣例，于是 p1=34,p2=14 ，
D2(色澤=烏黑) ，包含編号為 {2,3,8,15} 4個樣例，于是 p1=34,p2=14 ，
D3(色澤=淺白) ，包含編号為 {5} 1個樣例，于是 p1=11,p2=01=0 ，
有了上面的資訊就可以求該特征的每個屬性的資訊熵了：
E(D1)=−34log2(34)−14log2(14)=0.811
E(D2)=−34log2(34)−14log2(14)=0.811
E(D3)=−11log2(11)−0×log2(0)=0
于是，可以計算出屬性色澤的資訊增益：
Gain(D1,色澤)=E(D1)−∑v=13|Dv||D|E(Dv)=0.764−(49×0.811+49×0.811+0)=0.043
類似的，我們可以計算出其他屬性的資訊增益：
Gain(D1,根蒂)=0.458
Gain(D,敲聲)=0.331
Gain(D,臍部)=0.458
Gain(D,觸感)=0.458
根蒂，臍部，觸感3個屬性均取得了最大的資訊熵增益，可任選其中之一作為劃分屬性，于是在第一個分支上劃分後的決策樹如下圖：
重複上述操作即可得如下圖的最終決策樹結果：
C4.5
實際上，ID3的資訊增益劃分法對可取數值較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響，C4.5算法不采用資訊增益，取而代之的是資訊增益率來選擇最優劃分特征屬性。資訊增益率定義為：
Gainraio(D,a)=Gain(D,a)IV(a)
其中，
IV(a)=−∑v=1v|Dv||D|log2|Dv||D|
IV(a)稱為屬性 a 的“固有值”。屬性a的可能值數目越多(即V越大)，則IV(a)的值通常會越大。例如，對于上表的西瓜資料集，有：
IV(觸感)=−1217log21217−517log2517=0.874(v=2)
IV(色澤)=−617log2617−617log2617−517log2517=1.580(v=3)
IV(編号)==4.088(v=17)
與ID3決策樹一樣，同是選擇最大的值作為最優劃分。
CART
CART決策樹是一棵二叉樹，内部節點特征取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。CART決策樹使用“基尼系數”來選擇劃分屬性。基尼系數的定義如下：
Gini(D)=∑k=1ypk(1−pk)=1−∑k=1kp2k
那麼對于屬性 a 其基尼系數即為：
Gini(D,a)=∑v=1v|Dv||D|Gini(Dv)
直覺來說，Gini(D)反映了從資料集 D 中随機抽取兩個樣本，其類别标記不一緻的機率。是以，Gini(D)越小，則資料集D的純度越高。于是，對于屬性集合 A 中，選擇那個使得劃分後基尼系數最小的屬性作為最優劃分屬性。
| 編号 | 年齡 | 工作 | 房子 | 信貸 | 類别 |
|---|---|---|---|---|---|
| 1 | 青年 | 否 | 否 | 一般 | 否 |
| 2 | 青年 | 否 | 否 | 好 | 否 |
| 3 | 青年 | 是 | 否 | 好 | 是 |
| 4 | 青年 | 是 | 是 | 一般 | 是 |
| 5 | 青年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 一般 | 否 |
| 7 | 中年 | 否 | 否 | 好 | 否 |
| 8 | 中年 | 是 | 是 | 好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 中年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 非常好 | 是 |
| 12 | 老年 | 否 | 是 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 好 | 是 |
| 14 | 老年 | 是 | 否 | 非常好 | 是 |
| 15 | 老年 | 否 | 否 | 一般 | 否 |
求特征A1(年齡)的基尼系數：
Gini(D,青年)=515[1−(252+352)]+1015[1−(7102+3102)]=0.44
Gini(D,中年)=515[1−(352+252)]+1015[1−(6102+4102)]=0.48
Gini(D,老年)=515[1−(452+152)]+1015[1−(5102+5102)]=0.44
由于Gini(D,青年)和Gini(D,老年)相等且最小，是以都可以作為年齡的最優切分點。
接着求工作，房子的基尼系數：
Gini(D,有工作)=515[1−(552)]+1015[1−(4102+6102)]=0.32
Gini(D,沒工作)=1015[1−(4102+6102)]+515[1−(552)]=0.32
Gini(D,有房子)=615[1−(662)]+915[1−(392+692)]=0.27
Gini(D,沒房子)=915[1−(392+692)]+615[1−(662)]=0.27
是以對工作和房子分别取0.32和0.27。接着求信貸的基尼系數：
Gini(D,一般)=0.36
Gini(D,好)=0.47
Gini(D,非常好)=0.32
Gini(D,非常好)最小，是以信貸非常好作為最優切分點。
最後，在年齡(Gini(D,青年)=0.44)，工作(Gini(D,有工作)=0.32)，房子(Gini(D,有房子)=0.27)，信貸(Gini(D,非常好)=0.32)中，房子的基尼系數最小，是以選擇房子作為最有特征，有房子作為其最優切分點。于是根節點生出兩個子節點，一個是葉節點，對另一個節點繼續使用以上方法在年齡，工作，信貸中選擇 最優特征 及 最優劃分點
剪枝處理
剪枝是決策樹學習算法對付“過拟合”的主要手段。決策樹剪枝的基本政策有“前剪枝”和“後剪枝”。前剪枝是指在決策樹生成過程中，對每個節點在劃分前先進行預估，若目前節點的劃分不能夠帶來決策樹泛化性能的提升，則停止劃分并将目前節點标記為葉節點。後剪枝則是先從訓練集生成一棵完整的決策樹，然後自底向上的對非葉子節點進行考察，若将該節點對應的子樹替換為葉節點能帶來決策樹泛化性能的提升，則将該子樹替換為葉節點。在進行泛化能力考察時，采用的方法是從原資料集中留出“驗證集”的方式進行驗證。
給出一個資料集，已經分割為“訓練集”和“驗證集”：
訓練集：
| 編号 | 色澤 | 根蒂 | 敲聲 | 紋理 | 臍部 | 觸感 | 好瓜 |
|---|---|---|---|---|---|---|---|
| 1 | 青綠 | 蜷縮 | 濁響 | 清晰 | 凹陷 | 硬滑 | 是 |
| 2 | 烏黑 | 蜷縮 | 沉悶 | 清晰 | 凹陷 | 硬滑 | 是 |
| 3 | 烏黑 | 蜷縮 | 濁響 | 清晰 | 凹陷 | 硬滑 | 是 |
| 6 | 青綠 | 稍蜷 | 濁響 | 清晰 | 稍凹 | 軟粘 | 是 |
| 7 | 烏黑 | 稍蜷 | 濁響 | 稍糊 | 稍凹 | 軟粘 | 是 |
| 10 | 青綠 | 硬挺 | 清脆 | 清晰 | 平坦 | 軟粘 | 否 |
| 14 | 淺白 | 稍蜷 | 沉悶 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 15 | 烏黑 | 稍蜷 | 濁響 | 清晰 | 稍凹 | 軟粘 | 否 |
| 16 | 淺白 | 蜷縮 | 濁響 | 模糊 | 平坦 | 硬滑 | 否 |
| 17 | 青綠 | 蜷縮 | 沉悶 | 稍糊 | 稍凹 | 硬滑 | 否 |
驗證集：
| 編号 | 色澤 | 根蒂 | 敲聲 | 紋理 | 臍部 | 觸感 | 好瓜 |
|---|---|---|---|---|---|---|---|
| 4 | 青綠 | 蜷縮 | 沉悶 | 清晰 | 凹陷 | 硬滑 | 是 |
| 5 | 淺白 | 蜷縮 | 濁響 | 清晰 | 凹陷 | 硬滑 | 是 |
| 8 | 烏黑 | 稍蜷 | 濁響 | 清晰 | 稍凹 | 硬滑 | 是 |
| 9 | 烏黑 | 稍蜷 | 沉悶 | 稍糊 | 稍凹 | 硬滑 | 否 |
| 11 | 淺白 | 硬挺 | 清脆 | 模糊 | 平坦 | 硬滑 | 否 |
| 12 | 淺白 | 蜷縮 | 濁響 | 模糊 | 平坦 | 軟粘 | 否 |
| 13 | 青綠 | 稍蜷 | 濁響 | 稍糊 | 凹陷 | 硬滑 | 否 |
前剪枝
基于上述給出的不完整的訓練集根據資訊增益所生成的未剪枝的決策樹如下：
在進行劃分時，對于要剪枝的節點需注意的是： 其标記為訓練樣本中最多的類别 。
第一步：
對根節點進行剪枝預估，對于根節點來說，所有訓練集入選，則根據訓練集中類别最多的進行标記，因為訓練集中好瓜壞瓜的數量相同，可以任選一個，于是将1節點标記為好瓜。對根節點剪枝後為如圖所示：
其意思為，不管你新來的資料的任何屬性，隻要來一個西瓜我就認為是好瓜，那麼這樣剪枝在驗證集上隻有對 {4,5,8} 分類正确，對其餘的四個分類錯誤，故其精度為： 37×100%=42.9% 。
在用屬性“臍部”劃分後2，3，4節點分别包含訓練集中資料為 {1,2,3,14} ， {6,7,15,17} ， {10,16} ，故根據标記最多的來标記這些節點的準則，2,3,4分别被标記為“好瓜”，“好瓜”，“壞瓜”。此時，該模型為如下所示：
上面的圖是在對“臍部”進行劃分後的決策樹，其在驗證集上分别對 {4,5,8,11,12} 分類正确，于是它的精度為： 57×100%=71.4%>42.9% ，于是确定“臍部”的劃分。
第二步：
對節點2進行剪枝預估。如果對2節點的“色澤”進行剪枝，則剪枝完後的決策樹如圖：
其在驗證集上的精度為： 57×100%=71.4% ，如果不對2節點進行剪枝決策樹如圖：
那麼未剪枝的決策樹在驗證集上對 {4,8,11,12} 分類正确，精度為 47×100%=57.1%<71.4% ，是以未剪枝使得決策樹泛化能力下降，是以進行剪枝處理。
第三步：
對節點3進行剪枝預估。如果對3節點的“根蒂”進行剪枝，則剪枝完後的決策樹如圖：
其在驗證集上的精度為： 57×100%=71.4% ，如果不對3節點進行剪枝決策樹如圖：
對于5節點，其包含訓練集資料 {6,7,14} ，故将其标記為好瓜。那麼此未剪枝處理的決策樹在驗證集對 {4,5,8,11,12} 分類正确，是以精度為 57×100%=71.4% ，是以劃分沒有提高泛化能力，故剪枝。
第四步：
對節點4進行剪枝預估。因為4節點已經為一個葉子節點了，是以不再進行剪枝。
于是最終決策樹模型為：
可以看出，前剪枝是的決策樹的很多分支沒有展開，這不僅降低了過拟合的風險，還顯著減少了決策樹的訓練時間開銷和測試時間的開銷。但另一方面，在有些分支上雖然暫時不能提高泛化能力，但是在該節點的後續節點上面卻能提高泛化能力，而沒有得以展開，是以帶來了欠拟合的風險。
後剪枝
後剪枝先從訓練集生成一棵完整的決策樹，如圖，該樹在驗證集上的精度為 42.9% 。
後剪枝考慮的政策是對已經生成的決策樹自底向上對節點進行考量。
第一步:
首先考慮6節點，将其替換為葉節點，是以該節點包含的訓練集資料為 {7,15} ，是以任選其中之一标記，于是将該節點标記為“好瓜”。此時，生成的局決策樹為下圖：
那麼該樹在驗證集上的精度為 57.1%>42.9% ，是以決定剪枝。
第二步：
考慮5節點，如果對其進行剪枝，其節點包含訓練集資料 {6,7,15} ，故将其标記為“好瓜”，如圖:
此決策樹在驗證集上的精度為 57.1%=57.1% ，是以決定不剪枝。
第三步：
對節點2進行預估。在該節點的訓練資料集為 {1,2,3,14} ，故将其标記為“好瓜”，如圖：
此時在驗證集上精度提高到 71.4% ，故決定剪枝處理。
第四步：
對節點3,1節點進行預估。均未能在驗證集上提高精度。是以對3,1節點不進行剪枝處理。第三步生成的決策樹即為最終的決策樹。
[1]《機器學習》周志華
[2]《統計學習方法》李航