4.1基本流程

決策樹是基于樹結(jié)構(gòu)來進(jìn)行決策的翅阵，例如在西瓜問題中歪玲，對新樣本的分類可看作對“當(dāng)前樣本屬于正類嗎”這個問題的“決策”過程，圖4.1是西瓜問題的一棵決策樹

決策樹學(xué)習(xí)基本算法如圖4.2所示

在決策樹基本算法中掷匠，有三種情形導(dǎo)致遞歸返回：1滥崩、當(dāng)前結(jié)點包含的樣本全屬于同一類別，無需劃分 2讹语、當(dāng)前屬性集為空，或是所有樣本在所有屬性上取值相同顽决，無法劃分 3短条、當(dāng)前結(jié)點包含的樣本集合為空，不能劃分擎值。在第2種情形下慌烧，把當(dāng)前結(jié)點標(biāo)記為葉結(jié)點逐抑，但類別設(shè)定為該結(jié)點所含樣本最多的類別鸠儿。在第3種情形下，把當(dāng)前結(jié)點標(biāo)記為葉節(jié)點厕氨，但類別設(shè)定為其父結(jié)點所含樣本最多的類別进每。它們的不同點是 ，第2種是利用當(dāng)前結(jié)點的后驗分布命斧，第3種則是把父結(jié)點的樣本分布作為當(dāng)前結(jié)點的先驗分布

一個例子搞清楚（先驗分布/后驗分布/似然估計）轉(zhuǎn)載 - 簡書

4.2劃分選擇

圖4.2中田晚，決策樹學(xué)習(xí)的關(guān)鍵是第8行：如何選擇最優(yōu)劃分屬性。一般希望決策樹的分支結(jié)點所包含的樣本盡可能屬于同一類別国葬，即結(jié)點的“純度”越來越高

4.2.1信息增益

“信息熵”是度量樣本集合純度常用的指標(biāo)贤徒，樣本集D的信息熵Ent(D)的值越小芹壕，D的純度越高。定義為

利用屬性a對樣本集D進(jìn)行劃分可以得到“信息增益”接奈，信息增益越大踢涌，使用屬性a來劃分獲得的“純度提升”越大。定義為

下面舉一個例子來了解這兩個概念：

屬性“色澤”的信息增益為

4.2.2增益率

由于信息增益準(zhǔn)則對可取值數(shù)目較多的屬性有所偏好序宦，C4.5決策樹算法使用“增益率”來選擇最優(yōu)劃分屬性睁壁，定義為

IV(a)是屬性a的固有值，屬性a的可能取值越多(即V越大)互捌，IV(a)的值越大潘明，例如，在表4.1中秕噪，IV(觸感)=0.874(V=2)钳降，IV(色澤)=1.580(V=3)，IV(編號)=4.088(V=17)

由于增益率準(zhǔn)則對可取值數(shù)目較少的屬性有所偏好腌巾，C4.5算法采用先從候選劃分屬性中找出信息增益高于平均水平的屬性牲阁，再從中選擇增益率最高的方法來選擇最優(yōu)劃分屬性

4.2.3基尼指數(shù)

基尼指數(shù)反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個樣本，其類別標(biāo)記不一致的概率壤躲。Gini(D)越小城菊，數(shù)據(jù)集D的純度越高。定義為

在候選屬性集合A中碉克，選擇使劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性凌唬，即

4.3剪枝處理

剪枝是決策樹算法處理“過擬合”的手段。剪枝的基本策略有“預(yù)剪枝”和“后剪枝”漏麦。

預(yù)剪枝是對每個結(jié)點在劃分前先進(jìn)行估計客税，若當(dāng)前結(jié)點的劃分不能使決策樹泛化性能提升，則停止劃分并將當(dāng)前結(jié)點標(biāo)記為葉節(jié)點撕贞。后剪枝是先從訓(xùn)練集生成一棵完整的決策樹更耻，然后自底向上對非葉結(jié)點考察，若將該結(jié)點的子樹替換成葉結(jié)點能使決策樹性能提升捏膨，則將該子樹替換成葉結(jié)點秧均。

決策樹的預(yù)剪枝與后剪枝 - zfan520的博客 - CSDN博客

4.4連續(xù)與缺失值

在決策樹中使用連續(xù)屬性，采用二分法對連續(xù)屬性進(jìn)行處理号涯。

假設(shè)樣本集D和連續(xù)屬性a目胡，a在D上有n個不同的取值，從小到大排序為{a1,a2...}链快。對于屬性a誉己，考察包含n-1個元素的候選劃分點集合：

Gain(D,a,t)是樣本集D基于劃分點t二分后的信息增益，選擇使Gain(D,a,t)最大化的劃分點域蜗。

下面舉一個例子：

4.4.2缺失值處理

對于某些屬性值缺失的樣本：1巨双、屬性選擇：通過樣本集D在屬性a上沒有缺失值的樣本子集來判斷屬性a的優(yōu)劣 2噪猾、樣本劃分：若樣本x在劃分屬性a上的取值已知，則將x劃入對應(yīng)的子結(jié)點筑累，反之則將x同時劃入所有子結(jié)點畏妖，調(diào)整子結(jié)點的樣本權(quán)值，相當(dāng)于讓同一個樣本以不同概率劃入不同的子結(jié)點

信息增益計算式推廣為

下面舉一個例子：

4.5多變量決策樹

d個屬性對應(yīng)d維空間的一個數(shù)據(jù)點疼阔，對樣本分類表示在坐標(biāo)空間中找到不同樣本之間的分類邊界戒劫。

分類邊界由若干個與坐標(biāo)軸平行的分段組成，例子如下：

“多變量決策樹”能實現(xiàn)斜的劃分邊界婆廊，使決策樹模型簡化迅细。在多變量決策樹的學(xué)習(xí)過程中，不是為非葉結(jié)點尋找最優(yōu)劃分屬性淘邻，而是試圖建立合適的線性分類器茵典。例子如下：