機(jī)器學(xué)習(xí)算法與實(shí)踐 課件 第7章 決策樹

第七章決策樹決策樹（DecisionTree）是一種基本的分類與回歸方法，是最早的機(jī)器學(xué)習(xí)算法之一。1979年，J.RossQuinlan提出了ID3算法原型，并于1983年和1986年對(duì)ID3算法進(jìn)行了總結(jié)和簡(jiǎn)化，正式確立了決策樹理論。此間的1984年，LeoBreiman,JeromeFriedman,RichardOlshen與CharlesStone共同提出了分類與回歸樹（ClassificationandRegressionTrees），即CART算法。1993年，Quinlan在ID3算法的基礎(chǔ)上又提出了著名的C4.5算法。相對(duì)于其他算法，決策樹算法的基本原理更加符合人的思維方式，可以產(chǎn)生可視化的分類或回歸規(guī)則，生成的模型也具有可解釋性，因此其應(yīng)用十分廣泛。本章主要介紹上述3種決策樹算法的原理、流程及實(shí)現(xiàn)。17.1決策樹概述決策樹是一種呈樹形結(jié)構(gòu)的層次模型，可以是二又樹也可以是多叉樹。在分類問(wèn)題中，樹的每個(gè)非葉節(jié)點(diǎn)表示對(duì)一個(gè)特征的判斷，每個(gè)分支代表該特征在某個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類別。使用決策樹進(jìn)行決策的過(guò)程就是從根節(jié)點(diǎn)開始，逐個(gè)判斷待分類項(xiàng)中相應(yīng)的特征，并按照其值選擇輸出分支，直到到達(dá)葉節(jié)點(diǎn)，將葉節(jié)點(diǎn)存放的類別作為決策的結(jié)果。每一個(gè)樣本只會(huì)被一條路徑覆蓋（樣本的特征與路徑上的特征一致或樣本滿足規(guī)則的條件）。27.1決策樹概述如果想知道在不同天氣情況下人們是否會(huì)去室外打球，就可以建立圖7-1中的決策樹。圖中的菱形框表示對(duì)一個(gè)特征的判斷，菱形框下方線段上的文字表示每個(gè)判斷的所有可能的取值。圖中最上方的矩形框?yàn)椤案?jié)點(diǎn)”，中間矩形框?yàn)椤爸虚g節(jié)點(diǎn)”，最下方矩形框?yàn)椤叭~節(jié)點(diǎn)”。圖7-1決策樹算法原理舉例3稱箭頭的起點(diǎn)是終點(diǎn)的“父節(jié)點(diǎn)”，終點(diǎn)是起點(diǎn)的“子節(jié)點(diǎn)”。當(dāng)子節(jié)點(diǎn)只有兩個(gè)時(shí)，通常把他們稱為“左子節(jié)點(diǎn)”和“右子節(jié)點(diǎn)”。7.1決策樹概述決策樹構(gòu)造過(guò)程：1）從根節(jié)點(diǎn)開始，將數(shù)據(jù)集依照某個(gè)特征的取值劃分為互不相交的幾個(gè)子集；2）如果某個(gè)子集中的樣本都屬于同一個(gè)類別或某一個(gè)類別所占的百分比大于設(shè)定的閾值，則將其設(shè)置為葉節(jié)點(diǎn)，并將多數(shù)樣本的類別作為該葉節(jié)點(diǎn)的類別。否則將該子集設(shè)置為中間節(jié)點(diǎn)，并依照某個(gè)特征的取值繼續(xù)劃分；3）重復(fù)步驟2）直至所有分支的末尾一行均為葉節(jié)點(diǎn)。

47.1決策樹概述構(gòu)造決策樹的關(guān)鍵是如何進(jìn)行最優(yōu)特征劃分，即確定非葉節(jié)點(diǎn)對(duì)應(yīng)的特征及其判斷閾值。最優(yōu)特征劃分的方法有很多，每種決策樹之所以不同，一般都是因?yàn)樽顑?yōu)特征選擇的標(biāo)準(zhǔn)上有所差異，不同的標(biāo)準(zhǔn)導(dǎo)致生成不同類型的決策樹。本章介紹其中三個(gè)相對(duì)而言比較基本且使用廣泛的算法：ID3、C4.5和CART。三種算法是以遞進(jìn)的關(guān)系產(chǎn)生的。1）ID3算法是最基礎(chǔ)的決策樹算法，可以解決離散型數(shù)據(jù)的分類問(wèn)題。2）C4.5算法在ID3算法的基礎(chǔ)上進(jìn)一步發(fā)展，可以解決混合型數(shù)據(jù)的分類問(wèn)題。3）CART算法則更進(jìn)一步，在分類問(wèn)題的基礎(chǔ)上，還可以解決回歸問(wèn)題。雖說(shuō)上述算法的功能越來(lái)越強(qiáng)大，但其核心思想都是一致的，即算法通過(guò)不斷劃分?jǐn)?shù)據(jù)集來(lái)生成決策樹，其中每一步都選擇最優(yōu)的劃分特征。5一般而言，隨著劃分過(guò)程不斷進(jìn)行，希望決策樹的每個(gè)分枝中所包含的樣本盡可能屬于同一類別，即節(jié)點(diǎn)的“純度”越來(lái)越高。因此，對(duì)于一個(gè)包含多個(gè)特征的數(shù)據(jù)集，應(yīng)盡量選擇對(duì)劃分后子集的純度提升最多的特征。信息熵可以用來(lái)度量一個(gè)系統(tǒng)的有（無(wú)）序程度。如果將其應(yīng)用在數(shù)據(jù)集上，那么一個(gè)集合中包含樣本的類別越多，則說(shuō)明數(shù)據(jù)越“混亂”，信息墑越大；否則說(shuō)明數(shù)據(jù)越“純凈”，信息墑越小。而我們要做的就是保證每一次劃分都讓劃分后的信息墑降低的最多，也就是信息墑的增益最大。ID3決策樹算法就是以信息增益作為決策樹分支的劃分依據(jù)，每次選擇信息增益最大的特征進(jìn)行劃分。ID3算法只能處理離散數(shù)據(jù)，即可以處理像性別特征、布爾值特征等離散型特征，但沒法處理特征值在某個(gè)區(qū)間內(nèi)可以任意取值的特征，如身高特征、年齡特征等。7.2

ID3算法6

7.2.1信息熵和信息增益7

7.2.1信息熵和信息增益8

7.2.1信息熵和信息增益9

7.2.2

ID3算法流程10（8）對(duì)每個(gè)子集從步驟（1）開始繼續(xù)執(zhí)行。其中步驟（6）的“停止條件”（也可稱為“預(yù)剪枝”）有多種定義方法，較為常用的是如下兩種：1）若選擇作為劃分特征時(shí)的信息增益小于某個(gè)閾值，則停止；2）事先把數(shù)據(jù)集分為訓(xùn)練集與測(cè)試集，若由訓(xùn)練集得到的節(jié)點(diǎn)并不能降低測(cè)試集上的錯(cuò)誤率，則停止。這兩種停止條件通用于C4.5算法和CART算法。同時(shí)，決策樹會(huì)在許多地方應(yīng)用到遞歸的思想，上述算法中的步驟（7）正是經(jīng)典的遞歸。7.2.2

ID3算法流程11例7-1：表7-1給出了一個(gè)哺乳動(dòng)物數(shù)據(jù)集包含14個(gè)樣本，樣本有“飲食習(xí)性”、“胎生動(dòng)物”、“水生動(dòng)物”、“會(huì)飛”四個(gè)特征，“哺乳動(dòng)物”為樣本的類別標(biāo)記，有“是”與“否”兩種取值。

7.2

ID3算法表7-1

哺乳動(dòng)物分類數(shù)據(jù)集12

7.2

ID3算法13

7.2

ID3算法14

7.3

C4.5算法ID3算法存在一個(gè)問(wèn)題，就是偏向于多值特征。例如，如果一個(gè)特征是樣本的唯一標(biāo)識(shí)，則ID3會(huì)選擇它作為最優(yōu)劃分特征。這樣雖然使得劃分充分純凈，但這種劃分對(duì)分類幾乎毫無(wú)用處，而且小數(shù)目子集在分類效果上是不如大數(shù)目子集好的（如過(guò)擬合、抗噪差等問(wèn)題）。所以，為了解決這個(gè)問(wèn)題，可以對(duì)會(huì)產(chǎn)生大量“小數(shù)目”子集的劃分進(jìn)行懲罰，即劃分后產(chǎn)生的子集越小，它的信息熵要懲罰性的增大。這樣雖然ID3算法中會(huì)因?yàn)楹芏鄤澐趾蟮男?shù)量子集而產(chǎn)生較低的信息熵，但做懲罰值處理后，熵值就會(huì)平衡性的增大。這就是C4.5算法的改進(jìn)方向，它不再使用信息增益而是改用信息增益率來(lái)對(duì)最優(yōu)劃分特征進(jìn)行選擇，克服了使用信息增益選擇特征時(shí)偏向于多值特征的不足。此外，C4.5算法還可以處理連續(xù)型特征。15

7.3.1信息增益率

16

7.3.1信息增益率由此看出，劃分的子集越多、子集中樣本數(shù)量越少，懲罰值越大，相除后的信息增益率也就越小，依此做到了一定的平衡。由于“懲罰”了產(chǎn)生小樣本數(shù)量子集的劃分，其由于樣本數(shù)量少帶來(lái)信息增益抗噪性差的問(wèn)題也得到一定程度的解決，這就是C4.5算法的最大好處。另外C4.5和ID3算法還有一個(gè)特點(diǎn)，這兩個(gè)算法的根本都要計(jì)算信息增益，而信息增益的一個(gè)大前提就是要先進(jìn)行劃分，然后才能計(jì)算。所以，每計(jì)算一次增益也就代表進(jìn)行了一次劃分，而劃分特征接下來(lái)就不能再用了，所以ID3和C4.5算法在分類時(shí)會(huì)不斷消耗特征。17

7.3.2連續(xù)型特征處理

18

7.3.2連續(xù)型特征處理

19

7.3.2連續(xù)型特征處理

20

7.3.3C4.5算法流程

21

7.3.3C4.5算法流程

22

7.4分類與回歸樹分類與回歸樹（ClassificationAndRegressionTree，CART）算法是目前決策樹算法中最為成熟的一類算法，它既可用于分類，也可用于回歸。其一大特色就是假設(shè)最終生成的決策樹為二叉樹，即它在處理離散型和連續(xù)型特征時(shí)都會(huì)通過(guò)二分標(biāo)準(zhǔn)來(lái)劃分?jǐn)?shù)據(jù)。在處理分類問(wèn)題時(shí)，CART算法一般會(huì)使用基尼系數(shù)作為劃分優(yōu)劣的度量，算法的其他流程與C4.5算法類似。在處理回歸問(wèn)題時(shí)，CART算法使用平方誤差最小化準(zhǔn)則（SquaredResidualsMinimization）。將數(shù)據(jù)集劃分后，利用線性回歸建模，如果每次劃分后的子集仍然難以擬合則繼續(xù)劃分。這樣創(chuàng)建出來(lái)的決策樹，每個(gè)葉節(jié)點(diǎn)都是一個(gè)線性回歸模型。這些線性回歸模型反映了數(shù)據(jù)集中蘊(yùn)含的模式，也稱為模型樹。因此，CART不僅支持整體預(yù)測(cè)，也支持局部模式的預(yù)測(cè)，并有能力從整體中找到模式或根據(jù)模式組合成一個(gè)整體。整體與模式之間的相互結(jié)合，對(duì)于預(yù)測(cè)分析非常有價(jià)值。237.4.1基尼系數(shù)

247.4.1基尼系數(shù)

257.4.2回歸樹

267.4.2回歸樹

277.4.2回歸樹

287.5剪枝策略從直觀上來(lái)說(shuō)，只要決策樹足夠深，劃分標(biāo)準(zhǔn)足夠細(xì)，它在訓(xùn)練集上的表現(xiàn)就能接近完美：但同時(shí)也容易想象，由于它可能把訓(xùn)練集的一些“特性”當(dāng)作所有數(shù)據(jù)的“特性”來(lái)看待，它在未知的測(cè)試數(shù)據(jù)上的表現(xiàn)可能就會(huì)比較一般，亦即會(huì)出現(xiàn)過(guò)擬合的問(wèn)題。模型出現(xiàn)過(guò)擬合問(wèn)題一般是因?yàn)槟Ｐ吞^(guò)復(fù)雜，所以決策樹解決過(guò)擬合的方法是采取適當(dāng)?shù)摹凹糁Α薄?97.5剪枝策略剪枝通常分為兩類：“預(yù)剪枝”和“后剪枝”，其中“預(yù)剪枝”的概念在前文中已有使用，彼時(shí)采取的說(shuō)法是“停止條件”，如樹的深度超出閾值、當(dāng)前節(jié)點(diǎn)的樣本數(shù)量小于閾值、信息增益小于閾值等等。但是選取適當(dāng)?shù)拈撝当容^困難，過(guò)高會(huì)導(dǎo)致過(guò)擬合，而過(guò)低會(huì)導(dǎo)致欠擬合，因此需要人工反復(fù)地訓(xùn)練樣本才能得到很好的效果。預(yù)剪枝也有優(yōu)勢(shì)，由于它不必生成整棵決策樹，且算法簡(jiǎn)單、效率高，適合大規(guī)模問(wèn)題的粗略估計(jì)。而“后剪枝”是指在完全生成的決策樹上，剪掉樹中不具備一般代表性的子樹，使用葉節(jié)點(diǎn)取而代之，進(jìn)而形成一棵規(guī)模較小的新樹。換句話說(shuō)，后剪枝是從全局出發(fā)，通過(guò)某種標(biāo)準(zhǔn)對(duì)一些節(jié)點(diǎn)進(jìn)行局部剪枝，這樣就能減少?zèng)Q策樹中節(jié)點(diǎn)的數(shù)目，從而有效地降低模型復(fù)雜度。307.5剪枝策略問(wèn)題的關(guān)鍵在于如何定出局部剪枝的標(biāo)準(zhǔn)。通常來(lái)說(shuō)有兩種做法：1）應(yīng)用交叉驗(yàn)證的思想，若局部剪枝能夠使得模型在測(cè)試集上的錯(cuò)誤率降低，則進(jìn)行局部剪枝（預(yù)剪枝中也可應(yīng)用類似的思想）；2）應(yīng)用正則化的思想，綜合考慮不確定性和模型復(fù)雜度來(lái)定出一個(gè)新的損失函數(shù)（此前的損失函數(shù)只考慮了誤差），用該損失函數(shù)作為一個(gè)節(jié)點(diǎn)是否進(jìn)行局部剪枝的標(biāo)準(zhǔn)。第二種做法又涉及另一個(gè)關(guān)鍵問(wèn)題：如何定量分析決策樹中一個(gè)節(jié)點(diǎn)的復(fù)雜度？一個(gè)直觀且合理的方法是：直接使用該節(jié)點(diǎn)下屬葉節(jié)點(diǎn)的個(gè)數(shù)作為復(fù)雜度，這種方法稱為代價(jià)復(fù)雜度剪枝法（CostComplexityPruning）。317.5剪枝策略

327.5剪枝策略

33圖7-1決策樹算法原理舉例

7.5.1單一因子策略

34

7.5.1單一因子策略

357.5.2最優(yōu)因子策略

367.5.2最優(yōu)因子策略

377.5.2最優(yōu)因子策略

38

7.6

本章小結(jié)本章主要介紹了決策樹算法中的ID3算法、C4.5算法以及CAR