《機器學習-Python實戰(zhàn)（微課版）》課件 第五章 決策樹算法

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

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

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

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

脊椎動物訓練樣本集以“飲食習性”作為分支屬性的分裂情況?！帮嬍沉曅浴睘椤叭馐硠游铩钡姆种е杏?個正例、5個反例，其熵值為：ID3算法

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

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

C4.5算法

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

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

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

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