4.1 基本流程
決策樹（decision tree）是一類常見的機(jī)器學(xué)習(xí)方法，它是基于樹結(jié)構(gòu)來進(jìn)行決策的神得，這是人類在面臨決策問題時(shí)一種很自然的處理機(jī)制市咽。
其中，每個(gè)測(cè)試的結(jié)果或是導(dǎo)出最終結(jié)論烁焙，或是導(dǎo)出進(jìn)一步的判定問題航邢，其考慮范圍是在上次決策結(jié)果的限定范圍之內(nèi)。
在圖中考阱，色澤（屬性測(cè)試）表示的是根結(jié)點(diǎn)翠忠；根蒂和敲聲（屬性測(cè)試）表示的是內(nèi)部結(jié)點(diǎn)鞠苟，好瓜（決策結(jié)果）表示的是葉結(jié)點(diǎn)乞榨。
決策樹學(xué)習(xí)的目的：為了產(chǎn)生一棵泛化能力強(qiáng)，即處理未見示例能力強(qiáng)的決策樹当娱。
決策樹的基本流程遵循：“分而治之”（divide-and-conquer）策略吃既。
在決策樹基本算法中，有三種情形導(dǎo)致遞歸返回：
1跨细、當(dāng)前結(jié)點(diǎn)包含的樣本全屬于同一類別鹦倚，無需劃分?
2、當(dāng)前屬性集為空冀惭，或是所有樣本在所有屬性上取值相同震叙，無法劃分?
3、當(dāng)前結(jié)點(diǎn)包含的樣本集合為空散休，不能劃分媒楼。
注意：
在第2種情形下，把當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)戚丸，但類別設(shè)定為該結(jié)點(diǎn)所含樣本最多的類別划址。
在第3種情形下，把當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)，但類別設(shè)定為其父結(jié)點(diǎn)所含樣本最多的類別夺颤。
它們的不同點(diǎn)是 ：第2種是利用當(dāng)前結(jié)點(diǎn)的后驗(yàn)分布痢缎，第3種則是把父結(jié)點(diǎn)的樣本分布作為當(dāng)前結(jié)點(diǎn)的先驗(yàn)分布。
4.2 劃分選擇
決策樹學(xué)習(xí)的關(guān)鍵是：如何選擇最優(yōu)劃分屬性世澜，即使得結(jié)點(diǎn)的“純度”越來越高独旷。
4.2.1 信息增益
“信息熵”（information entropy）是度量樣本集合純度常用的指標(biāo)。例如：比如有10個(gè)西瓜寥裂，其中敲聲為清脆势告，混響，沒響聲的各有3抚恒，3咱台，4個(gè)，那么p1=3/10俭驮，p2=3/10回溺，p3=4/10。
樣本集D的信息熵Ent(D)的值越小混萝，D的純度越高遗遵。
注：
若p=0，則plog2p=0
Ent（D）的最小值為0逸嘀，最大值為log2|y|车要。
假設(shè)離散屬性a有很多個(gè)可能的取值，它會(huì)劃分出很多個(gè)分支節(jié)點(diǎn)崭倘，那么衡量這個(gè)屬性a能給我們帶來的更多信息翼岁，我們可以用“信息增益”（information gain）的概念去表示。
一般而言司光，信息增益越大琅坡，則意味著使用屬性a來劃分所獲得的“純度提升”越大。
為了更好的理解以上內(nèi)容残家，可以運(yùn)用一些實(shí)際例子來理解：
1榆俺、輸入一個(gè)數(shù)據(jù)集D（表4.1）
2、生成一個(gè)節(jié)點(diǎn)node
3坞淮、如果數(shù)據(jù)集中的樣本全部屬于同一類茴晋，比如西瓜樣本全部是“好瓜”，那么node就是葉子節(jié)點(diǎn)（好瓜）回窘。
4诺擅、如果樣本中的數(shù)據(jù)集不屬于同一類，比如西瓜中既有好瓜也有壞瓜毫玖，那就選擇一個(gè)屬性掀虎，把西瓜根據(jù)選好的屬性分類凌盯。
那么，我們應(yīng)該選擇西瓜中的哪個(gè)屬性進(jìn)行分類呢烹玉？
假設(shè)我們現(xiàn)在只有兩種屬性選擇驰怎，一種是“色澤”、另一種是“紋理”二打。
選擇“色澤”县忌，我們可以把西瓜分成三類——“淺白”全是壞瓜；“墨綠”全是好瓜继效；“青綠”90%是好瓜症杏，10%是壞瓜。
選擇“紋理”瑞信，我們可以把西瓜分為三類——“清晰”一半是好瓜厉颤，一半是壞瓜；“稍糊”40%是好瓜凡简、60%是壞瓜逼友；“模糊”30%是壞瓜，70%是好瓜秤涩。
我們會(huì)發(fā)現(xiàn)帜乞，“色澤”可以一下把很多好瓜和壞瓜區(qū)分開來，也就是說我們知道了一個(gè)西瓜的色澤后有很大幾率正確判斷它是好瓜還是壞瓜筐眷。而“紋理”卻對(duì)我們的判斷有“色澤”的幫助來得大黎烈。
因此，我們選擇“能給我們帶來更多信息”的屬性匀谣，或者說能夠“減少混淆程度”的屬性照棋。也就是我們要根據(jù)判斷一個(gè)屬性“信息增益”的大小，來進(jìn)行分類振定。（最優(yōu)化分屬性）
以屬性"色澤"為例必怜，它有 3 個(gè)可能的取值: {青綠，烏黑后频，淺白}.若使用該屬性對(duì) D 進(jìn)行劃分，則可得到 3 個(gè)子集暖途，分別記為: D1 (色 澤=青綠)卑惜， D2 (色澤2 烏黑)谢澈， D3 (色澤=淺白).
于是撕瞧，根據(jù)式(4.2)可計(jì)算出屬性"色澤"的信息增益為：
類似的折柠，我們可以得出：
顯然铁瞒，在所有計(jì)算結(jié)果中最岗，“紋理”屬性的信息增益最大娶牌，所以寒瓦，選擇這一屬性作為劃分屬性于颖。
按照“紋理”屬性，把西瓜分為清晰消请、模糊栏笆、稍糊三類：
5、把第4步得到的幾個(gè)數(shù)據(jù)子集作為輸入數(shù)據(jù)臊泰，分別再執(zhí)行上面的計(jì)算步驟蛉加，取得各屬性的信息增益，再選中其中數(shù)值最大的作為劃分屬性缸逃，以此循環(huán)针饥，直到不再執(zhí)行第4步為止（也就是葉子節(jié)點(diǎn)全部構(gòu)建完成，算法結(jié)束）需频。
4.2.2 增益率
實(shí)際上丁眼，信息增益準(zhǔn)則對(duì)可取值數(shù)目較多的屬性有所偏好，為了減少這種偏好可能帶來的不利影響昭殉，我們可以用“增益率”來選擇最優(yōu)劃分屬性户盯。
信息增益對(duì)于選項(xiàng)多的屬性有所偏好。如果我們把訓(xùn)練樣本中的“編號(hào)”也作為候選劃分屬性饲化，那么因?yàn)椤熬幪?hào)”能帶來最多的“信息增益”莽鸭，最大程度的降低混淆程度，所以編號(hào)這個(gè)屬性肯定會(huì)被選中為最優(yōu)劃分屬性吃靠。然而硫眨，這樣的決策樹顯然不具備泛化能力，無法對(duì)新樣本進(jìn)行有效的預(yù)測(cè)巢块，所以我們不會(huì)選擇編號(hào)作為屬性礁阁。
為此，我們可以考慮用增益率代替信息增益：
屬性a的可能取值數(shù)目越多族奢，IV（a）的值通常會(huì)越大姥闭。這樣，就可以有效的按一定的比例適當(dāng)降低因?yàn)榭扇≈禂?shù)目多而產(chǎn)生的偏好誤差越走。
注意：增益率準(zhǔn)則對(duì)可取值數(shù)目較少的屬性會(huì)有所偏好棚品，因此，我們應(yīng)該先從候選劃分屬性中找出信息增益高于平均水平的屬性廊敌，再?gòu)闹羞x擇增益率最高的铜跑。
4.2.3 基尼指數(shù)
Gini（D）反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個(gè)樣本，其類別標(biāo)記不一致的概率骡澈。（也就是抽取的兩個(gè)西瓜中锅纺，其中一個(gè)是好瓜，另一個(gè)是壞瓜的概率）
Gini（D）越小肋殴，數(shù)據(jù)集D的純度越高囤锉。
若基尼系數(shù)越低坦弟，越意味著樣本集中好瓜比壞瓜的樣本多，也就是說官地，好瓜和壞瓜混淆程度越低酿傍。
選擇那個(gè)使得劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性。
4.3 剪枝處理
剪枝是決策樹算法對(duì)付“過擬合”的主要手段区丑，通過主動(dòng)去掉一些分支來降低過擬合的風(fēng)險(xiǎn)拧粪。根據(jù)泛化性能是否提升來判斷和評(píng)估要不要留下這個(gè)分支。
那么沧侥，如何判斷決策樹的泛化性能是否提升呢可霎？可以采用“留出法”，即預(yù)留一部分?jǐn)?shù)據(jù)用作“驗(yàn)證集”來進(jìn)行性能評(píng)估宴杀。
首先癣朗，我們先將西瓜數(shù)據(jù)集隨機(jī)的劃分為“訓(xùn)練集”和“驗(yàn)證集”兩部分。
我們將采用“信息增益”準(zhǔn)則來進(jìn)行劃分屬性選擇旺罢，則從表4.2的訓(xùn)練集將會(huì)生成一顆如圖4.5所示的決策樹旷余。
我們將把剪枝處理分為“預(yù)剪枝”和“后剪枝”。
預(yù)剪枝過程就是在生成決策樹時(shí)扁达，用一些新的樣本（驗(yàn)證集）測(cè)試剛剛訓(xùn)練好的節(jié)點(diǎn)正卧，如果這個(gè)節(jié)點(diǎn)的存在并不能讓決策樹的泛化性能提高，則停止劃分并將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)（好瓜）跪解。（把這個(gè)剛訓(xùn)練出來的節(jié)點(diǎn)舍棄）
基于信息增益準(zhǔn)則炉旷，我們先選取“臍部”來對(duì)訓(xùn)練集進(jìn)行劃分，它被劃分為三個(gè)分支叉讥。
然而窘行，是否應(yīng)該進(jìn)行這個(gè)劃分呢？我們將要進(jìn)行劃分前后的泛化性進(jìn)行估計(jì)图仓。
首先罐盔，在結(jié)點(diǎn)1中，“臍部”是否應(yīng)該進(jìn)行劃分救崔？若其為葉結(jié)點(diǎn)惶看，則選擇訓(xùn)練樣例最多的類別去表示，則為“好瓜”（當(dāng)樣例最多的類不唯一時(shí)帚豪，可任選其中一類）碳竟。
我們?cè)儆抿?yàn)證集對(duì)其進(jìn)行測(cè)試。其中狸臣，有三個(gè)樣例被分類正確，四個(gè)樣例被分類錯(cuò)誤昌执，其驗(yàn)證集精度為42.9%烛亦。
在劃分后诈泼，?分別有 {1， 2煤禽， 3铐达， 14}（凹陷）、 {6檬果， 7瓮孙， 15， 17}（稍凹）选脊、 {10杭抠， 16}（平坦）的訓(xùn)練樣例，因此這 3 個(gè)結(jié)點(diǎn)分別被標(biāo)記為葉結(jié)點(diǎn)"好瓜"恳啥、 "好瓜"偏灿、 "壞瓜"（選擇訓(xùn)練樣例最多的類別去表示）。此時(shí)钝的，驗(yàn)證集中有5個(gè)樣例被分類正確翁垂，其驗(yàn)證集精度為71.4%>42.9%，于是硝桩，用“臍部”進(jìn)行劃分得以確定沿猜。
根據(jù)上述的步驟，以此類推碗脊，若計(jì)算出驗(yàn)證集精度劃分前>=劃分后啼肩，則禁止劃分，僅表示為好瓜/壞瓜望薄。
后剪枝過程是用一些新的樣本來測(cè)試這課剛剛訓(xùn)練出來的決策樹疟游，從下往上開始測(cè)試，如果某個(gè)節(jié)點(diǎn)被換成葉節(jié)點(diǎn)后整一棵決策樹的泛化性能提高了痕支，那么就直接替換為葉結(jié)點(diǎn)颁虐。
后剪枝會(huì)先對(duì)圖4.5中的結(jié)點(diǎn)6進(jìn)行考察，若將其分支剪除卧须，則相當(dāng)于把結(jié)點(diǎn)6替換成葉結(jié)點(diǎn)另绩，替換后的葉結(jié)點(diǎn)包含編號(hào)為{7，15}的訓(xùn)練樣本花嘶，所以葉結(jié)點(diǎn)6被標(biāo)記為“好瓜”笋籽，此時(shí)決策樹的驗(yàn)證集精度提高到57.1%，于是后剪枝策略決定剪枝椭员。
以此類推车海，考察結(jié)點(diǎn)5、2隘击、3侍芝、1研铆，最終，生成的決策樹如圖7所示州叠，其驗(yàn)證集精度為71.4%棵红。
對(duì)比圖4.7與圖4.6，可發(fā)現(xiàn)咧栗，后剪枝決策樹通常比預(yù)剪枝決策樹保留了更多的分支逆甜。且在一般情況下，后剪枝決策樹的欠擬合風(fēng)險(xiǎn)很小致板，泛化性能往往優(yōu)于預(yù)剪枝決策樹交煞。
4.4 連續(xù)與缺失值
4.4.1 連續(xù)值處理
1.為什么要使用連續(xù)值處理？
由于連續(xù)屬性的可取值數(shù)目不再有限可岂，因此错敢，不能直接根據(jù)連續(xù)屬性的可取值來對(duì)結(jié)點(diǎn)進(jìn)行劃分。
最簡(jiǎn)單的策略是采用二分法（bi-partition）
2.原理與假設(shè)缕粹？
假設(shè)樣本集D和連續(xù)屬性a稚茅，a在D上有n個(gè)不同的取值，從小到大排序?yàn)閧a1,a2...}平斩。對(duì)于屬性a亚享，考察包含n-1個(gè)元素的候選劃分點(diǎn)集合：
其中，Gain（D绘面，a）是樣本集D基于劃分點(diǎn)t（將D分為在屬性a中取值大于或不大于t的劃分點(diǎn)）二分后的信息增益欺税。我們可從中選擇出使Gain（D，a）最大化的劃分點(diǎn)揭璃。
根據(jù)表4.3晚凿，對(duì)屬性“密度”和“含糖率”，由小到大依次排列瘦馍，根據(jù)公式（4.7）歼秽，我們可以得到16個(gè)候選值：
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}.
再由公式（4.8）可計(jì)算出“密度”的信息增益為0.262（得出結(jié)果中的最大值）情组，因此燥筷，對(duì)應(yīng)的劃分點(diǎn)為0.381。
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}.
再由公式（4.8）可計(jì)算出“含糖率”的信息增益為0.349（得出結(jié)果中的最大值）院崇，因此肆氓，對(duì)應(yīng)的劃分點(diǎn)為0.126。
表4.3的數(shù)據(jù)上述屬性的信息增益為：
于是底瓣，“紋理”（信息增益值最大）被選作根結(jié)點(diǎn)劃分屬性谢揪。
注意：若當(dāng)前結(jié)點(diǎn)劃分屬性為連續(xù)屬性，該屬性還可作為其后代結(jié)點(diǎn)的劃分屬性.
例如：在父結(jié)點(diǎn)上使用了“密度<=0.381”，不會(huì)禁止在子結(jié)點(diǎn)上使用“密度<=0.294”键耕。
4.4.2 缺失值處理
1.為什么要進(jìn)行缺失值處理寺滚？
因?yàn)樵诂F(xiàn)實(shí)任務(wù)中常常會(huì)遇到不完整樣本柑营，如果簡(jiǎn)單地放棄不完整版本屈雄，僅使用無缺失值樣本進(jìn)行學(xué)習(xí)，這會(huì)對(duì)數(shù)據(jù)信息的極大浪費(fèi)官套。
2.怎樣處理缺失數(shù)據(jù)酒奶？
我們需要解決兩個(gè)問題：1）如何在屬性值缺失的情況下進(jìn)行劃分屬性選擇？ 2）給定劃分屬性奶赔，若樣本在該屬性上的值缺失惋嚎，如何對(duì)樣本進(jìn)行劃分？
首先站刑，我們先讓~D表示D中在屬性a上沒有缺失值樣本的子集另伍。
對(duì)于問題1），我們僅可根據(jù)~D來判斷屬性a的優(yōu)劣绞旅。假定屬性 α 有 V 個(gè) 可取值 {α1摆尝，α2 …， αV}因悲， 令 ~DV 表示 ~D 中在屬性 α 上取值為aV的樣本子集堕汞， ~Dk表示~D中屬于第 k 類 (k = 1,2, .. . , lyl)的樣本子集，則顯然有：
假定我們?yōu)槊總€(gè)樣本x賦予一個(gè)權(quán)重Wx晃琳，并定義：
（4.9）表示對(duì)于屬性a讯检，無缺失的樣本比例。
（4.10）表示無缺失樣本中卫旱，第k類所占比例人灼。
（411）表示無缺失樣本在屬性a上取值為aV的樣本的比例。
一般來講顾翼，樣本具有多個(gè)屬性投放。不同屬性的缺失值情況不同。直觀上來看：假如100個(gè)樣本中暴构，屬性a的缺失值高達(dá)99份跪呈，屬性b的缺失值只有1份，屬性c的缺失值有50份取逾。那在存在前面缺失的情況下耗绿，哪個(gè)屬性最可靠？
可想而知最可靠的是屬性b砾隅，其次是c误阻，再其次是a。由此可以考慮給不同屬性增加一個(gè)系數(shù)
p=無缺失值總數(shù)/樣本集合總數(shù)，例如此處舉例Pa=1/100究反，Pb=99/100寻定，Pc=50/100.
基于以上定義，我們可以將信息增益的計(jì)算式推廣為：
對(duì)于問題2）：
若樣本x在劃分屬性a上的取值已知精耐，則將x劃入與其對(duì)應(yīng)的分支結(jié)點(diǎn)狼速，并保持樣本權(quán)重Wx不變。若樣本x在劃分屬性a上的取值未知卦停，則將樣本x劃入所有子結(jié)點(diǎn)向胡，且樣本權(quán)值在與屬性值aV對(duì)應(yīng)的子結(jié)點(diǎn)中重新調(diào)整為~rV·Wx。
簡(jiǎn)單來說惊完，就是一開始的時(shí)候僵芹，選擇的第一個(gè)結(jié)點(diǎn)node，在樣本集中小槐，只取無缺失值的樣例拇派。（如：在表4.4中，以屬性“色澤”為例凿跳，可取的樣例有14個(gè)）
而在最后件豌，我們?cè)谒阈畔⒃鲆鏁r(shí)，應(yīng)該把結(jié)果乘上相應(yīng)的比例（14/17）拄显，從而能得出所有屬性在D上的信息增益苟径。
4.5 多變量決策樹
1.什么叫多變量決策樹？
若我們把每個(gè)屬性視為坐標(biāo)空間中的一個(gè)坐標(biāo)軸躬审，則 d 個(gè)屬性描述的樣本就對(duì)應(yīng)了 d 維空間中的一個(gè)數(shù)據(jù)點(diǎn)棘街，對(duì)樣本分類則意味著在這個(gè)坐標(biāo)空間中尋找不同類樣本之間的分類邊界。
特點(diǎn)：軸平衡（axis-parallel）承边，即它的分類邊界由若干個(gè)與坐標(biāo)軸平行的分段組成遭殉。
若使用斜的劃分邊界，則決策樹模型將大為簡(jiǎn)化博助。
對(duì)西瓜數(shù)據(jù)3.0a险污，我們可學(xué)得圖4.13這樣的多變量樹，其分類邊界如圖4.14所示富岳。
