《機器學習與Python實踐》課件-05決策樹

本章目錄01

決策樹原理02ID3算法03C4.5算法04

CART算法1.決策樹原理01

決策樹原理02ID3算法03C4.5算法04

CART算法長相能帥不帥家庭背景好能不好人品好上進心能不能有無不能不好1.決策樹原理決策樹：從訓練數(shù)據(jù)中學習得出一個樹狀結構的模型。決策樹屬于判別模型。決策樹是一種樹狀結構，通過做出一系列決策（選擇）來對數(shù)據(jù)進行劃分，這類似于針對一系列問題進行選擇。決策樹的決策過程就是從根節(jié)點開始，測試待分類項中對應的特征屬性，并按照其值選擇輸出分支，直到葉子節(jié)點，將葉子節(jié)點的存放的類別作為決策結果。根節(jié)點

(rootnode)葉節(jié)點(leafnode)1.決策樹原理根節(jié)點(rootnode)非葉子節(jié)點

(non-leafnode)(代表測試條件，對數(shù)據(jù)屬性的測試)分支

(branches)

(代表測試結果)葉節(jié)點(leafnode)(代表分類后所獲得的分類標記)決策樹算法是一種歸納分類算法，它通過對訓練集的學習，挖掘出有用的規(guī)則，用于對新數(shù)據(jù)進行預測。決策樹算法屬于監(jiān)督學習方法。決策樹歸納的基本算法是貪心算法，自頂向下來構建決策樹。貪心算法：在每一步選擇中都采取在當前狀態(tài)下最好/優(yōu)的選擇。在決策樹的生成過程中，分割方法即屬性選擇的度量是關鍵。1.決策樹原理優(yōu)點：推理過程容易理解，計算簡單，可解釋性強。比較適合處理有缺失屬性的樣本?？勺詣雍雎阅繕俗兞繘]有貢獻的屬性變量，也為判斷屬性變量的重要性，減少變量的數(shù)目提供參考。缺點：容易造成過擬合，需要采用剪枝操作。忽略了數(shù)據(jù)之間的相關性。對于各類別樣本數(shù)量不一致的數(shù)據(jù)，信息增益會偏向于那些更多數(shù)值的特征。決策樹的特點算法支持模型樹結構特征選擇連續(xù)值處理缺失值處理剪枝特征屬性多次使用ID3分類多叉樹信息增益不支持不支持不支持不支持C4.5分類多叉樹信息增益率支持支持支持不支持CART分類回歸二叉樹基尼指數(shù)均方差支持支持支持支持1.決策樹原理決策樹的三種基本類型建立決策樹的關鍵，即在當前狀態(tài)下選擇哪個屬性作為分類依據(jù)。根據(jù)不同的目標函數(shù)，建立決策樹主要有一下三種算法：ID3(IterativeDichotomiser)、C4.5、CART(ClassificationAndRegressionTree)。

信息熵

信息熵

右邊數(shù)據(jù)中：

數(shù)量是否信息熵15960.971年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否按年齡劃分信息熵

年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否

年齡數(shù)量是否信息熵青年5230.9710中年5320.9710老年5410.7219

年齡有工作有房子信用

條件熵

條件熵

年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否

信息增益

信息增益

年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否2.ID3算法01

決策樹原理02ID3算法03C4.5算法04

CART算法2.ID3算法ID3算法最早是由羅斯昆（J.RossQuinlan）于1975年提出的一種決策樹構建算法，算法的核心是“信息熵”，期望信息越小，信息熵越大，樣本純度越低。。ID3算法是以信息論為基礎，以信息增益為衡量標準，從而實現(xiàn)對數(shù)據(jù)的歸納分類。ID3算法計算每個屬性的信息增益，并選取具有最高增益的屬性作為給定的測試屬性。ID3算法2.ID3算法ID3算法其大致步驟為：初始化特征集合和數(shù)據(jù)集合；計算數(shù)據(jù)集合信息熵和所有特征的條件熵，選擇信息增益最大的特征作為當前決策節(jié)點；更新數(shù)據(jù)集合和特征集合（刪除上一步使用的特征，并按照特征值來劃分不同分支的數(shù)據(jù)集合）；重復2，3兩步，若子集值包含單一特征，則為分支葉子節(jié)點。ID3算法缺點ID3沒有剪枝策略，容易過擬合；信息增益準則對可取值數(shù)目較多的特征有所偏好，類似“編號”的特征其信息增益接近于1；只能用于處理離散分布的特征；沒有考慮缺失值。3.C4.5算法01

決策樹原理02ID3算法03C4.5算法04

CART算法3.C4.5算法C4.5算法C4.5算法是Ross對ID3算法的改進。用信息增益率來選擇屬性。ID3選擇屬性用的是子樹的信息增益，而C4.5用的是信息增益率。在決策樹構造過程中進行剪枝。對非離散數(shù)據(jù)也能處理。能夠對不完整數(shù)據(jù)進行處理。

備注：信息增益信息增益率信息增益率

年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否

C4.5的剪枝過擬合的原因：為了盡可能正確分類訓練樣本，節(jié)點的劃分過程會不斷重復直到不能再分，這樣就可能對訓練樣本學習的“太好”了，把訓練樣本的一些特點當做所有數(shù)據(jù)都具有的一般性質，從而導致過擬合。剪枝的基本策略有“預剪枝”（prepruning）和“后剪枝”（post-pruning）通過剪枝處理去掉一些分支來降低過擬合的風險。C4.5的剪枝預剪枝（prepruning）預剪枝不僅可以降低過擬合的風險而且還可以減少訓練時間，但另一方面它是基于“貪心”策略，會帶來欠擬合風險。編號色澤根蒂敲聲紋理臍部觸感好瓜1青綠蜷縮濁響清晰凹陷硬滑是2烏黑蜷縮沉悶清晰凹陷硬滑是3烏黑蜷縮濁響清晰凹陷硬滑是6青綠稍蜷濁響清晰稍凹軟粘是7烏黑稍蜷濁響稍糊稍凹軟粘是10青綠硬挺清脆清晰平坦軟粘否14淺白稍蜷沉悶稍糊凹陷硬滑否15烏黑稍蜷濁響清晰稍凹軟粘否16淺白蜷縮濁響模糊平坦硬滑否17青綠蜷縮沉悶稍糊稍凹硬滑否編號色澤根蒂敲聲紋理臍部觸感好瓜4青綠蜷縮沉悶清晰凹陷硬滑是5淺白蜷縮濁響清晰凹陷硬滑是8烏黑稍蜷濁響清晰稍凹硬滑是9烏黑稍蜷沉悶稍糊稍凹硬滑否11淺白硬挺清脆模糊平坦硬滑否12淺白蜷縮濁響模糊平坦軟粘否13青綠稍蜷濁響稍糊凹陷硬滑否訓練集驗證集C4.5的剪枝預剪枝基于表生成未剪枝的決策樹平坦紋理色澤好瓜壞瓜根蒂色澤臍部壞瓜壞瓜壞瓜壞瓜好瓜好瓜好瓜好瓜好瓜烏黑凹陷硬挺稍糊清晰蜷曲稍蜷模糊青綠稍凹淺白青綠烏黑淺白①⑥⑤④③②剪枝策略在節(jié)點劃分前來確定是否繼續(xù)增長，及早停止增長主要方法有：節(jié)點內數(shù)據(jù)樣本低于某一閾值；所有節(jié)點特征都已分裂；節(jié)點劃分前準確率比劃分后準確率高。C4.5的剪枝預剪枝平坦壞瓜臍部凹陷稍凹①④③②好瓜好瓜驗證集精度臍部=?劃分前:42.9%劃分后:71.4%預剪枝決策:劃分驗證集精度根蒂=?劃分前:71.4%劃分后:71.4%預剪枝決策:禁止劃分驗證集精度色澤=?劃分前:71.4%劃分后:57.1%預剪枝決策:禁止劃分{1,2,3,14}{6,7,15,17}{10,16}剪枝策略在節(jié)點劃分前來確定是否繼續(xù)增長，及早停止增長主要方法有：節(jié)點內數(shù)據(jù)樣本低于某一閾值；所有節(jié)點特征都已分裂；節(jié)點劃分前準確率比劃分后準確率高。預剪枝的決策樹C4.5的剪枝后剪枝編號色澤根蒂敲聲紋理臍部觸感好瓜1青綠蜷縮濁響清晰凹陷硬滑是2烏黑蜷縮沉悶清晰凹陷硬滑是3烏黑蜷縮濁響清晰凹陷硬滑是6青綠稍蜷濁響清晰稍凹軟粘是7烏黑稍蜷濁響稍糊稍凹軟粘是10青綠硬挺清脆清晰平坦軟粘否14淺白稍蜷沉悶稍糊凹陷硬滑否15烏黑稍蜷濁響清晰稍凹軟粘否16淺白蜷縮濁響模糊平坦硬滑否17青綠蜷縮沉悶稍糊稍凹硬滑否編號色澤根蒂敲聲紋理臍部觸感好瓜4青綠蜷縮沉悶清晰凹陷硬滑是5淺白蜷縮濁響清晰凹陷硬滑是8烏黑稍蜷濁響清晰稍凹硬滑是9烏黑稍蜷沉悶稍糊稍凹硬滑否11淺白硬挺清脆模糊平坦硬滑否12淺白蜷縮濁響模糊平坦軟粘否13青綠稍蜷濁響稍糊凹陷硬滑否訓練集驗證集在已經(jīng)生成的決策樹上進行剪枝，從而得到簡化版的剪枝決策樹。后剪枝決策樹通常比預剪枝決策樹保留了更多的分支。一般情況下，后剪枝的欠擬合風險更小，泛化性能往往優(yōu)于預剪枝決策樹。C4.5的剪枝后剪枝基于表生成未剪枝的決策樹平坦紋理色澤好瓜壞瓜根蒂色澤臍部壞瓜壞瓜壞瓜壞瓜好瓜好瓜好瓜好瓜好瓜烏黑凹陷硬挺稍糊清晰蜷曲稍蜷模糊青綠稍凹淺白青綠烏黑淺白①⑥⑤④③②{6,7,15}{7,15}{1,2,3,14}剪枝方法在已經(jīng)生成的決策樹上進行剪枝，從而得到簡化版的剪枝決策樹。C4.5采用的悲觀剪枝方法，用遞歸的方式從低往上針對每一個非葉子節(jié)點，評估用一個最佳葉子節(jié)點去代替這課子樹是否有益。如果剪枝后與剪枝前相比其錯誤率是保持或者下降，則這棵子樹就可以被替換掉。C4.5通過訓練數(shù)據(jù)集上的錯誤分類數(shù)量來估算未知樣本上的錯誤率。后剪枝決策樹的欠擬合風險很小，泛化性能往往優(yōu)于預剪枝決策樹。C4.5的剪枝后剪枝后剪枝的決策樹剪枝方法在已經(jīng)生成的決策樹上進行剪枝，從而得到簡化版的剪枝決策樹。C4.5采用的悲觀剪枝方法，用遞歸的方式從低往上針對每一個非葉子節(jié)點，評估用一個最佳葉子節(jié)點去代替這課子樹是否有益。如果剪枝后與剪枝前相比其錯誤率是保持或者下降，則這棵子樹就可以被替換掉。C4.5通過訓練數(shù)據(jù)集上的錯誤分類數(shù)量來估算未知樣本上的錯誤率。后剪枝決策樹的欠擬合風險很小，泛化性能往往優(yōu)于預剪枝決策樹。平坦色澤好瓜壞瓜根蒂臍部壞瓜壞瓜好瓜好瓜好瓜凹陷硬挺蜷曲稍蜷稍凹淺白青綠烏黑①⑥⑤④③②{1,2,3,14}{7,15}原分支“色澤”的驗證集精度剪枝前:57.1%剪枝后:71.4%后剪枝決策:剪枝原分支“紋理”的驗證集精度剪枝前:42.9%剪枝后:57.1%后剪枝決策:剪枝C4.5的缺點缺點剪枝策略可以再優(yōu)化；C4.5用的是多叉樹，用二叉樹效率更高；C4.5只能用于分類；C4.5使用的熵模型擁有大量耗時的對數(shù)運算，連續(xù)值還有排序運算；C4.5在構造樹的過程中，對數(shù)值屬性值需要按照其大小進行排序，從中選擇一個分割點，所以只適合于能夠駐留于內存的數(shù)據(jù)集，當訓練集大得無法在內存容納時，程序無法運行。4.CART算法01

決策樹原理02ID3算法03C4.5算法04

CART算法4.CART算法CARTClassificationandRegressionTree(CART)是決策樹的一種。用基尼指數(shù)來選擇屬性（分類），或用均方差來選擇屬性（回歸）。顧名思義，CART算法既可以用于創(chuàng)建分類樹，也可以用于創(chuàng)建回歸樹，兩者在構建的過程中稍有差異。如果目標變量是離散的，稱為分類樹。如果目標變量是連續(xù)的，稱為回歸樹。CART算法-分類連續(xù)特征處理…………

…………第1次劃分

第2次劃分

CART算法-分類離散特征處理……………………第1次劃分

第2次劃分

CART的特征會多次參與節(jié)點的建立，而在ID3或C4.5的一顆子樹中，離散特征只會參與一次節(jié)點的建立。房子是否工作是有無3,7,8,9,10,110,1,2,4,5,6,12,13,144,12,130,1,5,6,14

CART算法-分類基尼指數(shù)

年齡有工作有房子信用類別0青年否否一般否1青年否否好否2青年是否好是3青年是是一般是4青年否否一般否5中年否否一般否6中年否否好否7中年是是好是8中年否是非常好是9中年否是非常好是10老年否是非常好是11老年否是好是12老年是否好是13老年是否非常好是14老年否否一般否分類時用基尼指數(shù)來選擇屬性粗垂直線表示根節(jié)點的決策邊界（深度0）：花瓣長度=2.45厘米。由于左側區(qū)域是純凈的（僅Iris-Setosa），因此無法進一步拆分。然而，右側區(qū)域是不純的，因此深度為1的右側節(jié)點將其分割成花瓣寬度=1.75厘米（由虛線表示）。由于max_depth設置為2，因此決策樹會在那里停止。但是，如果將max_depth設置為3，那么兩個深度為2的節(jié)點將各自添加另一個決策邊界（由點虛線表示）。150個鳶尾花樣本進行分類，特征為花萼的長度和寬度決策樹原理CART算法-回歸

CART算法-回歸預測方式對于決策樹建立后做預測的方式，上面講到了CART分類樹采用葉子節(jié)點里概率最大的類別作為當前節(jié)點的預測類別。而回歸樹輸出不是類別，它采用的是用最終葉子的均值或者中位數(shù)來預測輸出結果。CART剪枝CART算法采用一種“基于代價復雜度的剪枝”方法進行后剪枝，這種方法會生成一系列樹，每個樹都是通過將前面的樹的某個或某些子樹替換成一個葉節(jié)點而得到的，這一系列樹中的最后一棵樹僅含一個用來預測類別的葉節(jié)點。然后用一種成本復雜度的度量準則來判斷哪棵子樹應該被一個預測類別值的葉節(jié)點所代替。這種方法需要使用一個單獨的測試數(shù)據(jù)集來評估所有的樹，根據(jù)它們在測試數(shù)據(jù)集熵的分類性能選出最佳的樹。CART算法CART剪枝具體流程:(1)計算每一個結點的條件熵(2)遞歸的從葉子節(jié)點開始往上遍歷,減掉葉子節(jié)點,然后判斷損失函數(shù)的值是否減少,如果減少,則將父節(jié)點作為新的葉子節(jié)點(3)重復(2),直到完全不能剪枝.平坦紋理色澤好瓜壞瓜根蒂色澤臍部壞瓜壞瓜壞瓜壞瓜好瓜好瓜好瓜好瓜好瓜烏黑凹陷硬挺稍糊清晰蜷曲稍蜷模糊青綠稍凹淺白青綠烏黑淺白①⑥⑤④③②決策樹差異總結劃分標準的差異：ID3使用信息增益偏向特征值多的特征，C4.5使用信息增益率克服信息增益的缺點，偏向于特征值小的特征，CART使用基尼指數(shù)克服C4.5需要求log的巨大計算量，偏向于特征值較多的特征。使用場景的差異：ID3和C4.5都只能用于分類問題，CART可以用于分類和回歸問題；ID3和C4.5是多叉樹，速度較慢，CART是二叉樹，計算速度很快；樣本數(shù)據(jù)的差異：ID3只能處理離散數(shù)據(jù)且缺失值敏感，C4.5和CART可以處理連續(xù)性數(shù)據(jù)且有多種方式處理缺失值；從樣本量考慮的話，小樣本建議C