4.1 基本流程

1.決策樹的基本結(jié)構(gòu)

1）根結(jié)點：相當于樹的根
2）內(nèi)部結(jié)點(決策結(jié)點)：相當于樹的枝干
3）葉結(jié)點 (結(jié)果結(jié)點)：相當于樹的葉子

決策樹基本結(jié)構(gòu)

2.決策樹的基本流程

決策樹的基本流程基于決策樹的結(jié)構(gòu)來進行的渣玲，遵循”分而冶之“的策略铅搓，其流程如下所示嫩舟。設我們訓練集為D饭于，有m個樣本畴栖，每個樣本的屬性有d個照皆，構(gòu)成屬性集A候醒。

決策樹流程

實際上敌土，決策樹的流程是一個遞歸的過程，而遞歸需要遞歸出口(讓遞歸結(jié)束)。決策樹的流程有三個遞歸出口

• 當前結(jié)點包含的樣本全屬于同一類別策彤，無需劃分
  (樣本為同一類別庞瘸，沒有需要劃分的屬性了)

  遞歸出口1

• 當前結(jié)點包含的樣本集合為空买鸽，不能劃分
  (沒有該屬性取值下的樣本)

  遞歸出口2

• 當前屬性集為空双仍，或是所有樣本在所有屬性上取值相同，無法劃分
  (屬性集為空或者有屬性但是全部樣本屬性值一樣無需劃分)
  (屬性用完了)

  遞歸出口3

舉例：
我們要用決策樹判斷好人還是壞人翎卓。樣本集D為100個人，100人里面有30個好人摆寄、70個壞人。屬性集A為{性別微饥，年齡段逗扒，地方}，取值分別為(男欠橘，女)矩肩、（青年、中年肃续、老年）黍檩、(北京、上海)始锚。
遞歸出口1：當前結(jié)點包含的樣本全屬于同一類別刽酱，無需劃分
假設第一次劃分是根據(jù)性別劃分，然后有50個男人50個女人瞧捌。我們發(fā)現(xiàn)棵里，男人這個子節(jié)點50個全是壞人，畢竟男人都是大豬蹄子。這50個壞男人里面衍慎，有青年有中年也有老年，有北京的也有深圳的皮钠，但無所謂了稳捆，沒必要再繼續(xù)劃分。這就是第一個終止條件

遞歸出口1

該節(jié)點已經(jīng)沒有樣本了自然不能再劃分了哲鸳。依據(jù)父節(jié)點的情況給該節(jié)點歸類臣疑。

沒有屬性了

例子來源：http://www.reibang.com/p/d153130b813f

4.2 劃分選擇

1.決策樹關(guān)鍵

從決策樹的流程可以看出驮樊，關(guān)鍵在于第8行，如何選擇最有劃分屬性，即根結(jié)點囚衔。

如何選擇最優(yōu)屬性

2.選擇根結(jié)點的依據(jù)

• 信息增益
  設y是類別猴仑，如好、壞肥哎。
  設k是樣本屬于第k類辽俗，k取1、2篡诽、3……y崖飘，如第1類是好、第2類是壞
  設p_k是樣本集合D中第k類樣本數(shù)目的占比杈女。即第k類樣本數(shù)目/m個樣本

1） 信息熵(Ent)：度量樣本集合純度的指標朱浴。數(shù)據(jù)集D的Ent為

信息熵(Ent)

設屬性集A躏筏，包括多個屬性，對離散屬性a的取值可能有V個呈枉，(a_v1,a_v2,a_v3,……,a_v)趁尼，用a來對D進行劃分，則會產(chǎn)生V個分支結(jié)點猖辫。其中D^v表示酥泞，屬性a下取值為a_v的樣本。如啃憎，有15個西瓜芝囤，有三種屬性，其中屬性a是"色澤"辛萍，取值{1青綠,2淺白,3烏黑}悯姊，其中取值青綠的有D¹=6，取值淺白的有D²=6贩毕，取值烏黑的有D³=3悯许。

每個分支結(jié)點的權(quán)重為：|D^v| / |D|，樣本數(shù)越多的分支結(jié)點影響越大辉阶。
D^v的信息熵為：Ent(D^v)先壕，即關(guān)鍵求在在D^v里瘩扼，有多少樣本是屬于第k類的占比。如垃僚，上面D¹=6集绰，其中2例是好瓜，4例是壞瓜谆棺。那么
Ent(D¹) = -((2/6) * log₂(2/6) + (4/6) * log₂(4/6))

2） 信息增益
通過上面的鋪墊后栽燕，我們可以給出用屬性a對D進行劃分所獲得的"信息增益"公式：

信息增益

數(shù)據(jù)集D

色澤的信息增益

其他屬性的信息增益

第一次劃分結(jié)果

重復操作.png

3）求信息增益及畫出決策樹的步驟
① 求數(shù)據(jù)集D的信息熵Ent(D)
② 選擇一個屬性a唠摹，找出每個取值所在的樣本數(shù)目爆捞，然后求占D的比例，即權(quán)重D^v/D勾拉。
③ 求每個取值的信息熵Ent(D^v)煮甥。
④ 重復上面步驟，求出其他屬性的信息增益藕赞。
⑤ 選擇最大信息增益成肘，然后畫出根結(jié)點的結(jié)果，然后重復上述步驟斧蜕，直到得到?jīng)Q策樹双霍。

下面這個鏈接有相關(guān)的代碼和解釋
http://www.reibang.com/p/14a9e8d1f2a3

• 增益率
  1）屬性a的"固有值"

  固有值
  屬性a的可能取值數(shù)目越多，固有值通常越大批销。
  固有值看起來很像信息熵洒闸，以下是它們的區(qū)別
  固有值與信息熵的區(qū)別

2）增益率

增益率

增益率準則：選擇增益率大的。但是增益率準則對可取值數(shù)目較少的屬性有所偏好骡技。

因此鸣个，C4.5決策樹算法羞反，結(jié)合了兩個指標，使用了啟發(fā)式：
先從候選劃分屬性中找出信息增益高于平均水平的屬性囤萤，再從中選擇增益率最高的昼窗。

• 基尼系數(shù)(CART決策樹算法使用的度量)
  1）基尼值

  基尼值，k指類別
  含義：從數(shù)據(jù)集中隨機抽取兩個樣本涛舍，其類別不同的概率澄惊。基尼值越小，數(shù)據(jù)集D純度越高富雅。

  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%。

劃分后

且可以看出莉给，測試集中分類正確的結(jié)果為5/7 = 71.4%

劃分前和劃分后毙石，測試集分類正確的精度從42.9%上升到71.4%廉沮，因此預剪枝策略讓"臍部"屬性進行劃分，即不剪掉這個分支徐矩。

對于凹陷來說

對于稍凹來說

對于凹陷結(jié)點，進一步按照色澤進行劃分后鳞骤，對比劃分前后的準確性：

劃分后拂募，精度下降庭猩，因此不讓"色澤"進行劃分窟她。

接著就是對于稍凹進行上述的操作陈症，最優(yōu)劃分屬性為"根蒂"，但是劃分后的精度沒有變化震糖，因此預剪枝測率也不讓"根蒂"進行劃分录肯，即剪掉"根蒂"結(jié)點產(chǎn)生的枝干。

預剪枝決策樹

預剪枝決策樹中很多分支沒有展開吊说，這不僅降低了過擬合的風險论咏，還顯著減少了決策樹的訓練時間開銷和測試時間。但是颁井，有些分支雖當前不能提升泛化性厅贪。甚至可能導致泛化性暫時降低，但在其基礎上進行后續(xù)劃分卻有可能導致顯著提高雅宾，因此預剪枝給決策樹帶來了欠擬合的風險养涮。

2）后剪枝：先從訓練集生成一棵完整的決策樹，然后自底向上地對非葉結(jié)點進行考察眉抬，若將該結(jié)點對應的子樹替換為葉結(jié)點(結(jié)果結(jié)點)能帶來決策樹泛化性能提升贯吓，則將該子樹換成葉結(jié)點。
完整的決策樹

完整決策樹

剪枝后：后剪枝從最底部開始剪枝悄谐，先看最底部的屬性"紋理"，將其剪掉库北，即結(jié)點6替換成結(jié)果結(jié)點(葉結(jié)點)爬舰，剪掉的結(jié)點中包括{7,15}兩個訓練樣本们陆，則剪枝后的決策樹為

剪枝后的決策樹

接著往上剪結(jié)點5，即結(jié)點5替換為葉結(jié)點屁商，包含的樣本號為{6,7,15}烟很，好瓜（2個）多于壞瓜（1個），因此選擇好瓜進行標記蜡镶，剪枝后的決策樹為：

第二次剪枝

后剪枝決策樹

對比預剪枝與后剪枝生成的決策樹屯伞，可以看出
后剪枝通常比預剪枝保留更多的分支腿箩，其欠擬合風險很小，因此后剪枝的泛化性能往往優(yōu)于預剪枝決策樹劣摇。但后剪枝過程是從底往上裁剪珠移，因此其訓練時間開銷比前剪枝要大。

4.4 連續(xù)值與缺失值

1.連續(xù)值處理

現(xiàn)實學習任務中末融，我們會遇到連續(xù)屬性钧惧，它們的取值無限，因此需要進行離散化勾习。
策略：二分法
給定數(shù)據(jù)集D浓瞪，有連續(xù)屬性a，假定a在D上出現(xiàn)了n個不同的取值巧婶，將這些連續(xù)值從小到大排序乾颁，記{a¹，a²粹舵，a³钮孵，……，aⁿ}眼滤。
再設置一個劃分點t巴席，劃分點將數(shù)據(jù)集D分為D_t⁺和D_t^-，劃分點t由連續(xù)屬性的信息增益決定诅需。
D_t^-：包含了連續(xù)屬性a取值小于t的樣本漾唉。
D_t⁺：包含了連續(xù)屬性a取值大于等于t的樣本荧库。
對相鄰的連續(xù)屬性取值aⁱ 和 aⁱ⁺¹來說，t在它們的區(qū)間之內(nèi)中取任意值產(chǎn)生的劃分結(jié)果相同赵刑，所以我們可以產(chǎn)生n-1個候選劃分點分衫。可以考慮取中點般此，則有候選劃分點集合蚪战，

取中點，產(chǎn)生候選劃分點集合

如圖所示

對每一個劃分點進行嘗試科乎，找出令信息增益最大的那個劃分點

數(shù)據(jù)集D

候選劃分點集合

最大信息增益是0.262，劃分點是0.381

Ent(D)

公式第二項

結(jié)果

含糖率的最優(yōu)劃分點

所有屬性的信息增益皆辽，紋理最大

最終的決策樹

2.缺失值處理

在現(xiàn)實中，會經(jīng)常遇見不完整的樣本空免，即樣本的某些屬性值缺失空另。

屬性值缺失

• 如何在屬性值缺失的情況下進行劃分屬性選擇?
• 給定劃分屬性循榆，若樣本在該屬性上的值缺失析恢，如何對樣本進行劃分?

設數(shù)據(jù)集D和屬性a，a有V個取值{a¹秧饮，a²映挂，……，a^V}
設D^~表示D中在屬性a上無缺失值的樣本子集盗尸。如屬性a為"色澤"袖肥，則無缺失樣本為 {2，3振劳，4椎组，6，7历恐，8寸癌，9，10弱贼，11蒸苇，12，14吮旅，15溪烤，16，17}庇勃，14個
設D^~v表示D^~中在屬性a上取值為a^v的樣本子集檬嘀。如色澤取值{青綠¹，烏黑²责嚷，淺白³}鸳兽，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賦一個權(quán)重w_x(一開始都為1)潮剪，且定義

對問題一迄汛，我們可以用D^~來判斷屬性a的優(yōu)劣
我們可以將信息增益改寫為

信息增益

一開始

對于問題一

對于問題一

其他屬性的信息增益

對于問題二中的缺失值

問題二的圖解

最終決策樹

4.5 多變量決策樹

在第一章中，我們知道了屬性空間翼闹，就是每個屬性都可以看成一個坐標軸斑鼻，這樣d個屬性就形成了d維空間，而樣本就是d維空間里面的一個點猎荠。樣本分類就是在這個d維空間中坚弱，尋找它們的分類邊界。

數(shù)據(jù)集

決策樹

分類邊界由若干個與軸平行的直線構(gòu)成

多段的分類邊界

斜線劃分邊界

線性分類器

多變量決策樹對應的分類邊界