4.1 基本流程
1.決策樹的基本結構
1）根結點：相當于樹的根
2）內部結點(決策結點)：相當于樹的枝干
3）葉結點 (結果結點)：相當于樹的葉子
2.決策樹的基本流程
決策樹的基本流程基于決策樹的結構來進行的，遵循”分而冶之“的策略，其流程如下所示。設我們訓練集為D，有m個樣本，每個樣本的屬性有d個，構成屬性集A。
實際上，決策樹的流程是一個遞歸的過程，而遞歸需要遞歸出口(讓遞歸結束)。決策樹的流程有三個遞歸出口
-
當前結點包含的樣本全屬于同一類別，無需劃分
(樣本為同一類別，沒有需要劃分的屬性了)遞歸出口1 -
當前結點包含的樣本集合為空，不能劃分
(沒有該屬性取值下的樣本)遞歸出口2 -
當前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分
(屬性集為空或者有屬性但是全部樣本屬性值一樣無需劃分)
(屬性用完了)遞歸出口3
舉例：
我們要用決策樹判斷好人還是壞人。樣本集D為100個人，100人里面有30個好人、70個壞人。屬性集A為{性別，年齡段，地方}，取值分別為(男，女)、（青年、中年、老年）、(北京、上海)。
遞歸出口1：當前結點包含的樣本全屬于同一類別，無需劃分
假設第一次劃分是根據(jù)性別劃分，然后有50個男人50個女人。我們發(fā)現(xiàn)，男人這個子節(jié)點50個全是壞人，畢竟男人都是大豬蹄子。這50個壞男人里面，有青年有中年也有老年，有北京的也有深圳的，但無所謂了，沒必要再繼續(xù)劃分。這就是第一個終止條件
遞歸出口2：當前結點包含的樣本集合為空，不能劃分
對女人，我們還要繼續(xù)考察，假設接下來我們是按照年齡段劃分的子節(jié)點，然后我們發(fā)現(xiàn)，老年這個子節(jié)點里一個樣本都沒有。這肯定是沒辦法繼續(xù)劃分了。問題是，那么我們如何歸類這個子節(jié)點呢？如果來了一個“老女人”讓我們判斷，該判斷為好人還是壞人呢？答案是利用父節(jié)點來判斷，老女人這個子節(jié)點為空，但是它的父節(jié)點是30個好人20個壞人。我們無法判斷一個老女人的好壞，但是既然一個女人有60%的可能性是好人，那么我們就也把老女人判斷為好人吧！這就叫先驗概率。
遞歸出口3：屬性用完了
例子來源：http://www.itdecent.cn/p/d153130b813f
4.2 劃分選擇
1.決策樹關鍵
從決策樹的流程可以看出，關鍵在于第8行，如何選擇最有劃分屬性，即根結點。
2.選擇根結點的依據(jù)
-
信息增益
設y是類別，如好、壞。
設k是樣本屬于第k類，k取1、2、3……y，如第1類是好、第2類是壞
設pk是樣本集合D中第k類樣本數(shù)目的占比。即第k類樣本數(shù)目/m個樣本
1） 信息熵(Ent)：度量樣本集合純度的指標。數(shù)據(jù)集D的Ent為
Ent的值越小，則D的純度越高。
設屬性集A，包括多個屬性，對離散屬性a的取值可能有V個，(av1,av2,av3,……,av)，用a來對D進行劃分，則會產生V個分支結點。其中Dv表示，屬性a下取值為av的樣本。如，有15個西瓜，有三種屬性，其中屬性a是"色澤"，取值{1青綠,2淺白,3烏黑}，其中取值青綠的有D1=6，取值淺白的有D2=6，取值烏黑的有D3=3。
每個分支結點的權重為：|Dv| / |D|，樣本數(shù)越多的分支結點影響越大。
Dv的信息熵為：Ent(Dv)，即關鍵求在在Dv里，有多少樣本是屬于第k類的占比。如，上面D1=6，其中2例是好瓜，4例是壞瓜。那么
Ent(D1) = -((2/6) * log2(2/6) + (4/6) * log2(4/6))
2） 信息增益
通過上面的鋪墊后，我們可以給出用屬性a對D進行劃分所獲得的"信息增益"公式：
信息增益越大，則意味著使用屬性a來進行劃分所獲得的"純
度提升"越大，故我們可以使用信息增益來進行決策樹的劃分選擇。
舉例：
3）求信息增益及畫出決策樹的步驟
① 求數(shù)據(jù)集D的信息熵Ent(D)
② 選擇一個屬性a，找出每個取值所在的樣本數(shù)目，然后求占D的比例，即權重Dv/D。
③ 求每個取值的信息熵Ent(Dv)。
④ 重復上面步驟，求出其他屬性的信息增益。
⑤ 選擇最大信息增益，然后畫出根結點的結果，然后重復上述步驟，直到得到決策樹。
下面這個鏈接有相關的代碼和解釋
http://www.itdecent.cn/p/14a9e8d1f2a3
-
增益率
1）屬性a的"固有值"屬性a的可能取值數(shù)目越多，固有值通常越大。 固有值看起來很像信息熵，以下是它們的區(qū)別固有值固有值與信息熵的區(qū)別
2）增益率
3）增益率準則與信息增益準則的區(qū)別
信息增益準則：選擇信息增益大的。但是信息增益準則對可取值數(shù)目較多的屬性有所偏好。易導致泛化能力差。
增益率準則：選擇增益率大的。但是增益率準則對可取值數(shù)目較少的屬性有所偏好。
因此，C4.5決策樹算法，結合了兩個指標，使用了啟發(fā)式：
先從候選劃分屬性中找出信息增益高于平均水平的屬性，再從中選擇增益率最高的。
-
基尼系數(shù)(CART決策樹算法使用的度量)
1）基尼值含義：從數(shù)據(jù)集中隨機抽取兩個樣本，其類別不同的概率。基尼值越小，數(shù)據(jù)集D純度越高。基尼值，k指類別2）基尼系數(shù)
基尼系數(shù)3）準則
在屬性集A中，選擇那個基尼系數(shù)最小的屬性作為最有劃分屬性。
4.3 剪枝處理
1. 剪枝作用
防止決策樹學習算法出現(xiàn)"過擬合"的問題。
2. 剪枝處理的基本策略
設有數(shù)據(jù)集D，劃分為訓練集和測試集。
1）預剪枝：要對劃分前后泛化性能進行評估。對比決策樹某節(jié)點生成前與生成后的泛化性能。有所提升就停止剪去該分支。
下面由例子來說明預剪枝。
基于信息增益原則，屬性"臍部"的最大，選擇"臍部"作為最優(yōu)劃分屬性，問題來了，是否應該進行劃分呢？預剪枝要通過比較劃分前后，泛化性能的大小來估計。
① 未劃分前，根據(jù)訓練集，類別標記為訓練樣例數(shù)最多的類別。這里選擇"好瓜"。
當所有節(jié)點集中在根節(jié)點，所有訓練集屬于標記類別的僅有{4,5,8}，因此分類正確的是3/7 * 100%=42.9%。
| 編號 | 好瓜 |
|---|---|
| 4 | 是 |
| 5 | 是 |
| 8 | 是 |
| 9 | 否 |
| 11 | 否 |
| 12 | 否 |
| 13 | 否 |
| 3/7 = 42.9% |
且可以看出，測試集中分類正確的結果為5/7 = 71.4%
| 編號 | 按臍部劃分分類正確的 |
|---|---|
| 4(凹陷) | 分類正確 |
| 5(凹陷) | 分類正確 |
| 8(稍凹) | 分類正確 |
| 9(稍凹) | 分類錯誤 |
| 11(平坦) | 分類正確 |
| 12(平坦) | 分類正確 |
| 13(凹陷) | 分類錯誤 |
| 5/7 = 71.4% |
劃分前和劃分后，測試集分類正確的精度從42.9%上升到71.4%，因此預剪枝策略讓"臍部"屬性進行劃分，即不剪掉這個分支。
接著繼續(xù)進一步計算凹陷、根蒂特征下，其他屬性的信息增益，按照最大信息增益準則選擇最優(yōu)屬性劃分"色澤"。
對于凹陷結點，進一步按照色澤進行劃分后，對比劃分前后的準確性：
| 編號 | 按照臍部劃分 | 對凹陷，按照色澤劃分 |
|---|---|---|
| 4(凹陷、青綠) | 分類正確 | 分類正確 |
| 5(凹陷、淺白) | 分類正確 | 分類錯誤 |
| 8(稍凹) | 分類正確 | 分類正確 |
| 9(稍凹) | 分類錯誤 | 分類錯誤 |
| 11(平坦) | 分類正確 | 分類正確 |
| 12(平坦) | 分類正確 | 分類正確 |
| 13(凹陷、青綠) | 分類錯誤 | 分類錯誤 |
| 正確率 | 5/7(劃分前) | 4/7(劃分后，精度降低) |
劃分后，精度下降，因此不讓"色澤"進行劃分。
接著就是對于稍凹進行上述的操作，最優(yōu)劃分屬性為"根蒂"，但是劃分后的精度沒有變化，因此預剪枝測率也不讓"根蒂"進行劃分，即剪掉"根蒂"結點產生的枝干。
預剪枝決策樹中很多分支沒有展開，這不僅降低了過擬合的風險，還顯著減少了決策樹的訓練時間開銷和測試時間。但是，有些分支雖當前不能提升泛化性。甚至可能導致泛化性暫時降低，但在其基礎上進行后續(xù)劃分卻有可能導致顯著提高，因此預剪枝給決策樹帶來了欠擬合的風險。
2）后剪枝：先從訓練集生成一棵完整的決策樹，然后自底向上地對非葉結點進行考察，若將該結點對應的子樹替換為葉結點(結果結點)能帶來決策樹泛化性能提升，則將該子樹換成葉結點。
完整的決策樹
剪枝后：后剪枝從最底部開始剪枝，先看最底部的屬性"紋理"，將其剪掉，即結點6替換成結果結點(葉結點)，剪掉的結點中包括{7,15}兩個訓練樣本，則剪枝后的決策樹為
接著往上剪結點5，即結點5替換為葉結點，包含的樣本號為{6,7,15}，好瓜（2個）多于壞瓜（1個），因此選擇好瓜進行標記，剪枝后的決策樹為：
然后對結點②、結點③和結點①逐個進行考察(結點④不用是因為達到了遞歸出口1的條件)，最后結點②剪掉，結點③和①保留，產生最終的后剪枝決策樹。
對比預剪枝與后剪枝生成的決策樹，可以看出
后剪枝通常比預剪枝保留更多的分支，其欠擬合風險很小，因此后剪枝的泛化性能往往優(yōu)于預剪枝決策樹。但后剪枝過程是從底往上裁剪，因此其訓練時間開銷比前剪枝要大。
4.4 連續(xù)值與缺失值
1.連續(xù)值處理
現(xiàn)實學習任務中，我們會遇到連續(xù)屬性，它們的取值無限，因此需要進行離散化。
策略：二分法
給定數(shù)據(jù)集D，有連續(xù)屬性a，假定a在D上出現(xiàn)了n個不同的取值，將這些連續(xù)值從小到大排序，記{a1，a2，a3，……，an}。
再設置一個劃分點t，劃分點將數(shù)據(jù)集D分為Dt+和Dt-，劃分點t由連續(xù)屬性的信息增益決定。
Dt-：包含了連續(xù)屬性a取值小于t的樣本。
Dt+：包含了連續(xù)屬性a取值大于等于t的樣本。
對相鄰的連續(xù)屬性取值ai 和 ai+1來說，t在它們的區(qū)間之內中取任意值產生的劃分結果相同，所以我們可以產生n-1個候選劃分點。可以考慮取中點，則有候選劃分點集合，
對于含糖率也是一樣的操作，得到
2.缺失值處理
在現(xiàn)實中，會經常遇見不完整的樣本，即樣本的某些屬性值缺失。
我們需要解決兩個問題：
- 如何在屬性值缺失的情況下進行劃分屬性選擇?
- 給定劃分屬性，若樣本在該屬性上的值缺失，如何對樣本進行劃分?
設數(shù)據(jù)集D和屬性a，a有V個取值{a1，a2，……，aV}
設D~表示D中在屬性a上無缺失值的樣本子集。如屬性a為"色澤"，則無缺失樣本為 {2，3，4，6，7，8，9，10，11，12，14，15，16，17}，14個
設D~v表示D~中在屬性a上取值為av的樣本子集。如色澤取值{青綠1，烏黑2，淺白3}，D~1 = {4，6，10，17}；D~2 = {2，3，7，8，9，15}；D~3 = {11，12，14，16}
設D~k表示D~中屬于第k類(k∈1，2，……)的樣本子集。如，西瓜有好瓜和壞瓜，k = 1(好瓜)，2(壞瓜)，
則D~1={2，3，4，6，7，8}；D~2={9，10，11，12，14，15，16，17}
假定我們?yōu)槊總€樣本x賦一個權重wx(一開始都為1)，且定義
含義：對屬性a，
ρ表示無缺失樣本占全部樣本的比值；
p~k表示無缺失樣本中第k類樣本的占比；
r~v表示無缺失樣本中，取值為v的樣本的占比。
∑p~k=1；∑r~v=1。
對問題一，我們可以用D~來判斷屬性a的優(yōu)劣
我們可以將信息增益改寫為
接著對問題二：
若x在劃分屬性a上的取值已知，則將x劃入與其取值對應的子結點，且權重依舊為wx。
若x在劃分屬性a上的取值未知，則將x同時劃入所有子結點，且權重變?yōu)?strong>原來的權重乘上與對應結點的屬性值的樣本在D~中的占比，即r~v * wx，就是讓同一個樣本以不同的概率劃入到不同的子結點中去。 從問題一到問題二的舉例
4.5 多變量決策樹
在第一章中，我們知道了屬性空間，就是每個屬性都可以看成一個坐標軸，這樣d個屬性就形成了d維空間，而樣本就是d維空間里面的一個點。樣本分類就是在這個d維空間中，尋找它們的分類邊界。
由于開銷過大，因此我們考慮使用斜的劃分邊界，如圖
多變量決策樹不再是為每個非葉結點尋找最有劃分屬性，而是建立一個合適的線性分類器。如對上圖的數(shù)據(jù)集D建立線性分類器。
