第五章決策樹算法本章主要講述機(jī)器學(xué)習(xí)中決策樹算法概念。通過本節(jié)學(xué)習(xí)可以：熟悉決策樹算法的基礎(chǔ)知識(shí)。學(xué)習(xí)如何給決策樹剪枝等相關(guān)知識(shí)。學(xué)習(xí)ID3,C4.5及CART樹等相關(guān)知識(shí)。了解剪枝的原理。學(xué)習(xí)目標(biāo)決策樹分類算法原理以信息論為基礎(chǔ)的分類原理決策樹分類算法框架衡量標(biāo)準(zhǔn)：信息熵決策樹算法的簡(jiǎn)化決策樹算法的優(yōu)、缺點(diǎn)與應(yīng)用決策樹分類算法決策樹剪枝當(dāng)信息被擁有它的實(shí)體傳遞給接收它的實(shí)體時(shí)，僅當(dāng)接收實(shí)體不知道信息的先驗(yàn)知識(shí)時(shí)信息才得到傳遞。如果接收實(shí)體事先知道了消息的內(nèi)容，這條消息所傳遞的信息量就是0。只有當(dāng)接收實(shí)體對(duì)消息的先驗(yàn)知識(shí)掌握少于100%時(shí)，消息才真正傳遞信息。信息論

信息論信息熵解決的是對(duì)信息的度量問題。信息量和事件發(fā)生的概率有關(guān)，當(dāng)事件發(fā)生的概率越低，傳遞的信息量越大。信息量應(yīng)當(dāng)是非負(fù)的，必然發(fā)生的信息量為0。兩個(gè)事件的信息量可以相加，并且兩個(gè)獨(dú)立事件的聯(lián)合信息量應(yīng)該是他們各自信息量的和。信息量決策樹分類算法原理以信息論為基礎(chǔ)的分類原理決策樹分類算法框架衡量標(biāo)準(zhǔn)：信息熵決策樹算法的簡(jiǎn)化決策樹算法的優(yōu)、缺點(diǎn)與應(yīng)用決策樹分類算法決策樹剪枝分類算法是利用訓(xùn)練樣本集獲得分類函數(shù)即分類模型(分類器)，從而實(shí)現(xiàn)將數(shù)據(jù)集中的樣本劃分到各個(gè)類中。分類模型通過學(xué)習(xí)訓(xùn)練樣本中屬性集與類別之間的潛在關(guān)系，并以此為依據(jù)對(duì)新樣本屬于哪一類進(jìn)行預(yù)測(cè)。決策樹算法決策樹簡(jiǎn)單來說就是帶有判決規(guī)則（if-then）的一種樹，可以依據(jù)樹中的判決規(guī)則來預(yù)測(cè)未知樣本的類別和值。用一個(gè)網(wǎng)上通俗易懂的例子（相親）來說明：女兒：年紀(jì)多大了？母親：26女兒：長(zhǎng)相如何？母親：挺帥的女兒：收入如何？母親：不算很高，中等情況女兒：是公務(wù)員不？母親：是，在稅務(wù)局上班女兒：那好，我去見見決策樹案例決策樹是一個(gè)屬性結(jié)構(gòu)的預(yù)測(cè)模型，代表對(duì)象屬性和對(duì)象值之間的一種映射關(guān)系。它由節(jié)點(diǎn)（node）和有向邊（directededge）組成，其節(jié)點(diǎn)有兩種類型：內(nèi)節(jié)點(diǎn)（internalnode）和葉節(jié)點(diǎn)（leafnode），內(nèi)部節(jié)點(diǎn)表示一個(gè)特征或?qū)傩裕~節(jié)點(diǎn)表示一個(gè)類。如上圖所示的相親例子，藍(lán)色的橢圓內(nèi)節(jié)點(diǎn)表示的是對(duì)象的屬性，橘黃色的矩形葉節(jié)點(diǎn)表示分類結(jié)果（是否相親），有向邊上的值則表示對(duì)象每個(gè)屬性或特征中可能取的值。決策樹定義決策樹通過把數(shù)據(jù)樣本分配到某個(gè)葉子結(jié)點(diǎn)來確定數(shù)據(jù)集中樣本所屬的分類。決策樹由決策結(jié)點(diǎn)、分支和葉子結(jié)點(diǎn)組成。決策結(jié)點(diǎn)表示在樣本的一個(gè)屬性上進(jìn)行的劃分。分支表示對(duì)于決策結(jié)點(diǎn)進(jìn)行劃分的輸出。葉結(jié)點(diǎn)代表經(jīng)過分支到達(dá)的類。從決策樹根結(jié)點(diǎn)出發(fā)，自頂向下移動(dòng)，在每個(gè)決策結(jié)點(diǎn)都會(huì)進(jìn)行次劃分，通過劃分的結(jié)果將樣本進(jìn)行分類，導(dǎo)致不同的分支，最后到達(dá)個(gè)葉子結(jié)點(diǎn)，這個(gè)過程就是利用決策樹進(jìn)行分類的過程。決策樹決策樹分類算法原理以信息論為基礎(chǔ)的分類原理決策樹分類算法框架衡量標(biāo)準(zhǔn)：信息熵決策樹算法的簡(jiǎn)化決策樹算法的優(yōu)、缺點(diǎn)與應(yīng)用決策樹分類算法決策樹剪枝信息和抽象該如何來度量？1948年香農(nóng)提出“信息熵(entropy)”的概念。一條信息的信息量大小和他的不確定性有直接的關(guān)系，要搞清楚一件非常非常不確定的事情，或者是我們一無所知的事情需要了解大量信息，信息量的度量就等于不確定性的多少。例如：猜世界杯冠軍，假如是一無所知，需要猜多少次？每個(gè)隊(duì)奪冠的幾率不是相等的。比特(bit)來衡量信息的多少，變量的不確定性越大，熵也就越大。決策樹須知概念-信息熵信息熵解決的是對(duì)信息的度量問題。信息量和事件發(fā)生的概率有關(guān)，當(dāng)事件發(fā)生的概率越低，傳遞的信息量越大。信息量應(yīng)當(dāng)是非負(fù)的，必然發(fā)生的信息量為0。兩個(gè)事件的信息量可以相加，并且兩個(gè)獨(dú)立事件的聯(lián)合信息量應(yīng)該是他們各自信息量的和。信息熵決策樹分類算法原理以信息論為基礎(chǔ)的分類原理決策樹分類算法框架衡量標(biāo)準(zhǔn)：信息熵決策樹算法的簡(jiǎn)化決策樹算法的優(yōu)、缺點(diǎn)與應(yīng)用決策樹分類算法決策樹剪枝決策樹算法的思想是，先從一個(gè)特征入手，就如同我們上面的游戲中一樣，既然無法直接分類，那就先根據(jù)一個(gè)特征進(jìn)行分類，雖然分類結(jié)果達(dá)不到理想效果，但是通過這次分類，我們的問題規(guī)模變小了，同時(shí)分類后的子集相比原來的樣本集更加易于分類了。然后針對(duì)上一次分類后的樣本子集，重復(fù)這個(gè)過程。在理想的情況下，經(jīng)過多層的決策分類，我們將得到完全純凈的子集，也就是每一個(gè)子集中的樣本都屬于同一個(gè)分類。決策樹算法的簡(jiǎn)化決策樹學(xué)習(xí)算法包含特征選擇、決策樹生成與決策樹的剪枝。決策樹表示的是一個(gè)條件概率分布，所以深淺不同的決策樹對(duì)應(yīng)著不同復(fù)雜程度的概率模型。決策樹的生成對(duì)應(yīng)著模型的局部選擇（局部最優(yōu)），決策樹的剪枝對(duì)應(yīng)著全局選擇（全局最優(yōu)）。決策樹常用的算法有ID3，C4.5，CART。決策樹優(yōu)點(diǎn)：它構(gòu)成一個(gè)簡(jiǎn)單的決策過程，使決策者可以按順序有步驟地進(jìn)行。決策樹法有直觀的圖形，便于決策者進(jìn)行科學(xué)的分析、周密的思考。將決策樹圖形畫出后，便于集體討論和共同分析，有利于進(jìn)行集體決策。決策樹法對(duì)比較復(fù)雜問題進(jìn)行決策，特別是對(duì)多級(jí)決策問題尤感方便，甚至在決策過程中，通過畫決策樹逐級(jí)思考可以走一步看一步，三思后行。缺點(diǎn)：在分析的過程中有些參數(shù)沒有包括在樹中，顯得不全面。如果分級(jí)太多或出現(xiàn)的分枝太多，畫起來就不方便。決策樹優(yōu)缺點(diǎn)決策樹分類算法原理以信息論為基礎(chǔ)的分類原理決策樹分類算法框架衡量標(biāo)準(zhǔn)：信息熵決策樹算法的簡(jiǎn)化決策樹算法的優(yōu)、缺點(diǎn)與應(yīng)用決策樹分類算法決策樹剪枝決策樹學(xué)習(xí)算法包含特征選擇、決策樹生成與決策樹的剪枝。決策樹表示的是一個(gè)條件概率分布，所以深淺不同的決策樹對(duì)應(yīng)著不同復(fù)雜程度的概率模型。決策樹的生成對(duì)應(yīng)著模型的局部選擇（局部最優(yōu)），決策樹的剪枝對(duì)應(yīng)著全局選擇（全局最優(yōu)）。決策樹常用的算法有ID3，C4.5，CART。決策樹ID3算法是在每個(gè)結(jié)點(diǎn)處選取能獲得最高信息增益的分支屬性進(jìn)行分裂。在每個(gè)決策結(jié)點(diǎn)處劃分分支、選取分支屬性的目的是將整個(gè)決策樹的樣本純度提升衡量樣本集合純度的指標(biāo)則是熵：舉例：如果有一個(gè)大小為10的布爾值樣本集S_b，其中有6個(gè)真值、4個(gè)假值，那么該布爾型樣本分類的熵為：ID3

計(jì)算分支屬性對(duì)于樣本集分類好壞程度的度量——信息增益。由于分裂后樣本集的純度提高，則樣本集的熵降低，熵降低的值即為該分裂方法的信息增益。ID3算法

脊椎動(dòng)物分類訓(xùn)練樣本集：ID3算法動(dòng)物飲食習(xí)性胎生動(dòng)物水生動(dòng)物會(huì)飛哺乳動(dòng)物人類雜食動(dòng)物是否否是野豬雜食動(dòng)物是否否是獅子肉食動(dòng)物是否否是蒼鷹肉食動(dòng)物否否是否鱷魚肉食動(dòng)物否是否否巨蜥肉食動(dòng)物否否否否蝙蝠雜食動(dòng)物是否是是野牛草食動(dòng)物是否否是麻雀雜食動(dòng)物否否是否鯊魚肉食動(dòng)物否是否否海豚肉食動(dòng)物是是否是鴨嘴獸肉食動(dòng)物否否否是袋鼠草食動(dòng)物是否否是蟒蛇肉食動(dòng)物否否否否此樣本集有“飲食習(xí)性”、“胎生動(dòng)物”、“水生動(dòng)物”、“會(huì)飛”四個(gè)屬性可作為分支屬性，而“哺乳動(dòng)物”作為樣本的分類屬性，有“是”與“否”兩種分類，也即正例與負(fù)例。共有14個(gè)樣本，其中8個(gè)正例，6個(gè)反例，設(shè)此樣本集為S，則分裂前的熵值為：ID3算法

脊椎動(dòng)物訓(xùn)練樣本集以“飲食習(xí)性”作為分支屬性的分裂情況?！帮嬍沉?xí)性”為“肉食動(dòng)物”的分支中有3個(gè)正例、5個(gè)反例，其熵值為：ID3算法

同理，計(jì)算出“飲食習(xí)性”分類為“草食動(dòng)物”的分支與分類為“雜食動(dòng)物”的分支中的熵值分別為：設(shè)“飲食習(xí)性”屬性為Y，由此可以計(jì)算得出,作為分支屬性進(jìn)行分裂之后的信息增益為：ID3算法

同理，可以算出針對(duì)其他屬性作為分支屬性時(shí)的信息增益。計(jì)算可得，以“胎生動(dòng)物”“水生動(dòng)物”“會(huì)飛”作為分支屬性時(shí)的信息增益分別為0.6893、0.0454、0.0454。由此可知“胎生動(dòng)物”作為分支屬性時(shí)能獲得最大的信息增益，即具有最強(qiáng)的區(qū)分樣本的能力，所以在此處選擇使用“胎生動(dòng)物”作為分支屬性對(duì)根結(jié)點(diǎn)進(jìn)行劃分。ID3算法由根結(jié)點(diǎn)通過計(jì)算信息增益選取合適的屬性進(jìn)行分裂，若新生成的結(jié)點(diǎn)的分類屬性不唯一，則對(duì)新生成的結(jié)點(diǎn)繼續(xù)進(jìn)行分裂，不斷重復(fù)此步驟，直至所有樣本屬于同一類，或者達(dá)到要求的分類條件為止。常用的分類條件包括結(jié)點(diǎn)樣本數(shù)最少于來設(shè)定的值、決策樹達(dá)到預(yù)先設(shè)定的最大深度等。在決策樹的構(gòu)建過程中，會(huì)出現(xiàn)使用了所有的屬性進(jìn)行分支之后，類別不同的樣本仍存在同一個(gè)葉子結(jié)點(diǎn)中。當(dāng)達(dá)到了限制條件而被強(qiáng)制停止構(gòu)建時(shí)，也會(huì)出現(xiàn)結(jié)點(diǎn)中子樣本集存在多種分類的情況。對(duì)于這種情況，一般取此結(jié)點(diǎn)中子樣本集占數(shù)的分類作為結(jié)點(diǎn)的分類。分支多的屬性并不一定是最優(yōu)的，就如同將100個(gè)樣本分到99個(gè)分支中并沒有什么意義，這種分支屬性因?yàn)榉种嗫赡芟啾戎聼o法提供太多的可用信息，例如個(gè)人信息中的“省份”屬性。ID3算法

C4.5算法

CART算法采用的是一種二分循環(huán)分割的方法，每次都把當(dāng)前樣本集劃分為兩個(gè)子樣本集，使生成的決策樹的結(jié)點(diǎn)均有兩個(gè)分支，顯然，這樣就構(gòu)造了一個(gè)二叉樹。如果分支屬性有多于兩個(gè)取值，在分裂時(shí)會(huì)對(duì)屬性值進(jìn)行組合，選擇最佳的兩個(gè)組合分支。假設(shè)某屬性存在q個(gè)可能取值，那么以該屬性作為分支屬性，生成兩個(gè)分支的分裂方法共有

種。CART算法在分支處理中分支屬性的度量指標(biāo)是Gini指標(biāo)。在前面例子中，假設(shè)選擇“會(huì)飛”作為分支屬性，其Gini指標(biāo)為：CART樹算法

決策樹分類算法原理以信息論為基礎(chǔ)的分類原理決策樹分類算法框架衡量標(biāo)準(zhǔn)：信息熵決策樹算法的簡(jiǎn)化決策樹算法的優(yōu)、缺點(diǎn)與應(yīng)用決策樹分類算法決策樹剪枝訓(xùn)練誤差代表分類方法對(duì)于現(xiàn)有訓(xùn)練樣本集的擬合程度。泛化誤差代表此方法的泛化能力，即對(duì)于新的樣本數(shù)據(jù)的分類能力如何。模型的訓(xùn)練誤差比較高，則稱此分類模型欠擬合。模型的訓(xùn)練誤差低但是泛化誤差比較高，則稱此分類模型過擬合。對(duì)于欠擬合問題，可以通過增加分類屬性的數(shù)量、選取合適的分類屬性等方法，提高模型對(duì)于訓(xùn)練樣本的擬合程度。過擬合對(duì)口罩銷售定價(jià)進(jìn)行分類樣本集測(cè)試集過擬合產(chǎn)品名功能是否為純色銷售價(jià)位加厚口罩防塵否低保暖口罩保暖否高護(hù)耳口罩保暖是高活性炭口罩防霧霾是中三層防塵口罩防塵否低藝人同款口罩防塵是高呼吸閥口罩防霧霾是中產(chǎn)品名功能是否為純色銷售價(jià)位兒童口罩防塵是低情侶口罩保暖否高一次性口罩防塵否低無紡布口罩防塵是低顆粒物防護(hù)口罩防霧霾否中三層決策樹，訓(xùn)練誤差為0，測(cè)試誤差高達(dá)2/5。兩層決策樹，訓(xùn)練集擬合程度相比較低，但測(cè)試集表現(xiàn)更好。過擬合問題過擬合現(xiàn)象會(huì)導(dǎo)致隨著決策樹的繼續(xù)增長(zhǎng)，盡管訓(xùn)練誤差仍在下降，但是泛化誤差停止下降，甚至還會(huì)提升。決策樹誤差曲線：過擬合問題決策樹的剪枝有兩種思路：預(yù)剪枝（Pre-Pruning）和后剪枝（Post-Pruning）。決策樹剪枝后剪枝算法有很多種，這里簡(jiǎn)要總結(jié)如下：Reduced-ErrorPruning(REP,錯(cuò)誤率降低剪枝）PessimisticErrorPruning(PEP，悲觀剪枝）Cost-ComplexityPruning(CCP，代價(jià)復(fù)雜度剪枝)后剪枝錯(cuò)誤率降低剪枝（REP）是后剪枝策略中最簡(jiǎn)單的算法之一，該算法從葉子結(jié)點(diǎn)向上，依次將決策樹的所有子樹用其樣本中最多的類替換，使用一個(gè)測(cè)試集進(jìn)行測(cè)試，記錄下對(duì)于決策樹的每棵子樹剪枝前后的誤差數(shù)之差，選取誤差數(shù)減少最少的子樹進(jìn)行剪枝，將其用子樣本集中最多的類替換。按此步驟自底向上，遍歷決策樹的所有子樹，當(dāng)發(fā)現(xiàn)沒有可替換的子樹時(shí)，即每棵子樹剪枝后的誤差數(shù)都會(huì)增多，則剪枝結(jié)束。REP剪枝方法簡(jiǎn)單、快速，在數(shù)據(jù)集較大時(shí)效果不錯(cuò)，但由于需要比對(duì)模型子樹替換前后的預(yù)測(cè)錯(cuò)誤率，因此需要從數(shù)據(jù)集中劃分出單獨(dú)的測(cè)試集，故而當(dāng)數(shù)據(jù)集較小時(shí)，REP剪枝策略的效果會(huì)有所下降。錯(cuò)誤率降低剪枝悲觀剪枝（PEP）與REP相比，PEP不再需要構(gòu)建一個(gè)單獨(dú)的測(cè)試集。其假設(shè)某葉子結(jié)點(diǎn)t中有N(t)個(gè)樣本，其中有e(t)個(gè)被錯(cuò)誤分類的樣本，則此葉子結(jié)點(diǎn)誤分類率定義：其中0.5為修正因子。對(duì)于一棵有著N個(gè)葉子結(jié)點(diǎn)的子樹T，其誤分類率計(jì)算公式如下：由于修正因子的存在，有時(shí)即便子樹的誤差數(shù)要小于剪枝后的誤差，仍有可能進(jìn)行剪枝操作，因?yàn)檎`分類率的計(jì)算公式中考慮到了葉子結(jié)點(diǎn)樹大?。∟）的影響。悲觀剪枝

代價(jià)復(fù)雜度剪枝策略(CCP)定義了代價(jià)與復(fù)雜度的概念，代價(jià)是指在剪枝過程中因?yàn)樽訕浔惶鎿Q而增加的錯(cuò)分樣本，復(fù)雜度表示剪枝后減少的葉結(jié)點(diǎn)數(shù)。CCP算法使用α作為衡量代價(jià)與復(fù)雜度之間關(guān)系的值，其計(jì)算公式如下：CCP的具體方法為，計(jì)算決策樹T的每個(gè)非葉子結(jié)點(diǎn)的α值，每次計(jì)算之后剪掉具有最