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

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

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

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

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

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

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

C4.5算法

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

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

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

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