決策樹根據李峰等人的PPT改編課件主要依據李航編寫的《統計學習方法》編制，清華大學出版社另一本參考書：《數據挖掘與數學建模》國防工業出版社第1頁，共66頁。決策樹1.1決策樹模型與學習1.2特征選擇1.3決策樹的生成1.4決策樹的剪枝1.5CART算法第2頁，共66頁。1.1決策樹模型與學習1.1.1決策樹模型1.1.2決策樹與if-then規則1.1.3決策樹與條件概率分布1.1.4決策樹學習第3頁，共66頁。1.1.1決策樹模型什么是決策樹？定義1.1（決策樹）分類決策樹模型是一種描述對實例進行分類的樹形結構。決策樹由結點和有向邊組成。結點有兩種類型：內部結點和葉節點。內部結點表示一個特征或屬性，葉節點表示一個類。第4頁，共66頁。決策樹學習算法的特點決策樹學習算法的最大優點是，它可以自學習。在學習的過程中，不需要使用者了解過多背景知識，只需要對訓練實例進行較好的標注，就能夠進行學習。顯然，它屬于有監督學習。從一類無序、無規則的事物(概念)中推理出決策樹表示的分類規則。第5頁，共66頁。決策樹學習的主要算法

建立決策樹的關鍵，即在當前狀態下選擇哪個屬性作為分類依據。根據不同的目標函數，建立決策樹主要有一下三種算法。ID3

（J.RossQuinlan-1975）核心：信息熵C4.5—ID3的改進，核心：信息增益比CART（Breiman-1984），核心：基尼指數第6頁，共66頁。例1.找對象決策樹分類的思想類似于找對象。現想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：

女兒：多大年紀了？(年齡)

母親：26。

女兒：長的帥不帥？(長相)

母親：挺帥的。

女兒：收入高不？(收入情況)

母親：不算很高，中等情況。

女兒：是公務員不？(是否公務員)

母親：是，在稅務局上班呢。

女兒：那好，我去見見。第7頁，共66頁。1.1.2決策樹與if-then規則由決策樹的根結點到葉結點的每一條路徑構建一條規則；路徑上內部結點的特征對應著規則的條件，而葉結點的類對應著規則的結論。If-then規則集合的一重要性質：互斥并且完備第8頁，共66頁。1.1.3決策樹與條件概率分布將特征空間劃分為互不相交的單元或區域，并在每個單元定義一個類的概率分布就構成了一個條件概率分布。各葉結點(單元)上的條件概率往往偏向某一個類，即屬于某一類的概率較大，決策樹分類時將該結點的實例強行分到條件概率大的那一類去。

第9頁，共66頁。1.1.4決策樹學習

第10頁，共66頁。1.1.4決策樹學習目標：我們需要的是一個與訓練數據矛盾較小的決策樹，同時具有很好的泛化能力。決策樹學習的損失函數：（通常是）正則化的極大似然函數。但是基于損失函數找到全局最優決策樹是NP-完全問題。現實中決策樹學習通常采用啟發式方法，即局部最優。具體做法：每次選擇feature時，都挑選擇當前條件下最優的那個feature作為劃分規則，即局部最優的feature。第11頁，共66頁。1.2特征選擇

特征選擇問題特征選擇在于選取對訓練數據具有分類能力的特征。如何判斷一個特征對于當前數據集的分類效果？

也即確定選擇特征的準則。第12頁，共66頁。ID年齡有工作有自己的房子信貸情況類別1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否例1.2右表是一個由15個樣本組成的貸款申請訓練數據。數據包括貸款申請人的四個特征。表的最后一列是類別，是否同意貸款，取2個值：是、否。希望通過所給的訓練數據學習一個貸款申請的決策樹，用以對未來的貸款申請進行分類。特征選擇是決定用哪個特征來劃分特征空間。第13頁，共66頁。1.2.2信息增益

第14頁，共66頁。熵-就分類而言，所有成員都屬于一類，熵為零；不同類別

數目相等，則熵等于1，類別數目不等，則熵介于0,1之間。

第15頁，共66頁。條件熵

第16頁，共66頁。信息增益

第17頁，共66頁。信息增益的具體公式

第18頁，共66頁。信息增益算法

第19頁，共66頁。例1.3對表1.1所給的訓練數據集D,

根據信息增益準則選擇最優特征。ID年齡有工作有自己的房子信貸情況類別1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否

第20頁，共66頁。1.2.3信息增益比

第21頁，共66頁。1.3決策樹的生成

1.3.1ID3算法

第22頁，共66頁。例1.4對表1.1的訓練數據集，利用ID3算法建立決策樹ID年齡有工作信貸情況類別1青年否一般否2青年否好否3青年是好是5青年否一般否6中年否一般否7中年否好否13老年是好是14老年是非常好是15老年否一般否有自己的房子(A3)ID年齡有工作信貸情況類別4青年是一般是8中年是好是9中年否非常好是10中年否非常好是11老年否非常好是12老年都好是是否表1表2第23頁，共66頁。

第24頁，共66頁。有自己的房子是否是是否有工作ID年齡信貸情況類別3青年好是13老年好是14老年非常好是表3ID年齡信貸情況類別1青年一般否2青年好否5青年一般否6中年一般否7中年好否15老年一般否表4

這里生成的決策樹只用到兩個特征（兩個內節點），ID3算法容易存在過擬合問題。第25頁，共66頁。補充：如何解決決策樹的過擬合問題概念原因解決什么是過度擬合數據過度擬合數據是怎么產生的怎么去解決這個問題第26頁，共66頁。補充：如何解決決策樹的過擬合問題——概念

過度擬合（overfitting）：如果決策樹對訓練樣本的特征描述得“過于精確”，無法實現對新樣本的合理分析，所以此時它不是一棵分析新數據的最佳決策樹。一棵完全決策樹能非常準確地反映訓練集中數據的特征，但因失去了一般代表性而無法用于對新數據的分類或預測，這種現象一般稱為“過擬合”。

定義：給定一個假設H，如果在假設空間上存在另一個假設H'，使得在訓練集上H的錯誤率差比H'小，而在測試集上H的錯誤率卻比H'要大，那么稱假設H過度擬合訓練數據。第27頁，共66頁。二.產生過度擬合數據問題的原因有哪些？原因1：樣本問題（1）樣本里的噪音數據干擾過大，大到模型過分記住了噪音特征，反而忽略了真實的輸入輸出間的關系；（什么是噪音數據？）（2）樣本抽取錯誤，包括（但不限于）樣本數量太少，抽樣方法錯誤，抽樣時沒有足夠正確考慮業務場景或業務特點，等等導致抽出的樣本數據不能有效足夠代表業務邏輯或業務場景；（3）建模時使用了樣本中太多無關的輸入變量。原因2：構建決策樹的方法問題在決策樹模型搭建中，我們使用的算法對于決策樹的生長沒有合理的限制和修剪的話，決策樹的自由生長有可能每片葉子里只包含單純的事件數據或非事件數據，可以想象，這種決策樹當然可以完美匹配（擬合）訓練數據，但是一旦應用到新的業務真實數據時，效果是一塌糊涂。第28頁，共66頁。三.如何解決過度擬合數據問題？針對原因1的解決方法：合理、有效地抽樣，用相對能夠反映業務邏輯的訓練

集去產生決策樹；針對原因2的主要解決方法：剪枝：提前停止樹的增長或者對已經生成的樹按照一

定的規則進行后剪枝。第29頁，共66頁。1.3.2C4.5的生成算法C4.5算法與ID3算法相似，C4.5算法對ID3算法進行了改進.C4.5在生成的過程中，用信息增益比來選擇特征。第30頁，共66頁。1.4決策樹的剪枝

第31頁，共66頁。算法1.4樹的剪枝算法

第32頁，共66頁。關于剪枝的補充——先剪枝剪枝是一個簡化過擬合決策樹的過程。有兩種常用的剪枝方法：

先剪枝（prepruning）：通過提前停止樹的構建而對樹“剪枝”，一旦停止，節點就成為樹葉。該樹葉可以持有子集元組中最頻繁的類；有多種不同的方式可以讓決策樹停止生長，下面介紹幾種停止決策樹生長的方法：

1.定義一個高度，當決策樹達到該高度時就可以停止決策樹的生長，這是一種最為簡單的方法；

2.達到某個結點的實例具有相同的特征向量，即使這些實例不屬于同一類，也可以停止決策樹的生長。這種方法對于處理數據中的數據沖突問題非常有效；第33頁，共66頁。補充：關于剪枝——先剪枝3.定義一個閾值，當達到某個結點的實例個數小于該閾值時就可以停止決策樹的生長；4.定義一個閾值，通過計算每次擴張對系統性能的增益，并比較增益值與該閾值的大小來決定是否停止決策樹的生長。

先剪枝方法不但相對簡單，效率很高，而且不需要生成整個決策樹，適合于解決大規模問題。該方法看起來很直接，但要精確地估計決策樹生長的停止時間并不容易，即選取一個恰當的閾值是非常困難的。高閾值可能導致過分簡化的樹，而低閾值可能使得樹的簡化太少。第34頁，共66頁。解決決策樹過擬合的另一種方法——隨機森林根據總投票人數，250可能有所調整定義一個閾值，當達到某個結點的實例個數小于該閾值時就可以停止決策樹的生長；女兒：長的帥不帥？(長相)

母親：挺帥的。對于樣本的誤差率e，我們可以根據經驗把它估計成各種各樣的分布模型，比如是二項式分布，比如是正態分布。補充：如何解決決策樹的過擬合問題CART假設決策樹是二叉樹，內部結點特征的取值為“是”和“否。2特征選擇

特征選擇問題1所給的訓練數據集D,

根據信息增益準則選擇最優特征。C4.現想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：決策樹由結點和有向邊組成。那么一棵樹錯誤分類一個樣本值為1，正確分類一個樣本值為0，該樹錯誤分類的概率（誤判率）為e（e為分布的固有屬性,可以通過關于剪枝的補充——后剪枝

后剪枝（postpruning）：它首先構造完整的決策樹，允許樹過度擬合訓練數據，然后對那些置信度不夠的結點子樹用葉子結點來代替，該葉子的類標號用該結點子樹中最頻繁的類標記。相比于先剪枝，這種方法更常用，正是因為在先剪枝方法中精確地估計何時停止樹增長很困難。第35頁，共66頁。補充：關于剪枝的準則無論是通過及早停止還是后修剪來得到正確規模的樹，一個關鍵的問題是使用什么樣的準則來確定最終正確樹的規模：1.使用訓練集合(TrainingSet）和驗證集合(ValidationSet)，來評估剪枝方法在修剪結點上的效用。2.使用所有的訓練集合進行訓練，但是用統計測試來估計修剪特定結點是否會改善訓練集合外的數據的評估性能。測試來進一步擴展結點是否能改善整個分類數據的性能，還是僅僅改善了當前訓練集合數據上的性能。3.使用明確的標準來衡量訓練樣例和決策樹的復雜度，當編碼長度最小時，停止樹增長，如MDL(MinimumDescriptionLength)準則。第36頁，共66頁。補充：關于剪枝的準則Reduced-ErrorPruning(REP,錯誤率降低剪枝）

REP方法是一種比較簡單的后剪枝的方法，在該方法中，可用的數據被分成兩個樣例集合：一個訓練集用來形成學習到的決策樹，一個分離的驗證集用來評估這個決策樹在后續數據上的精度，確切地說是用來評估修剪這個決策樹的影響。這個方法的動機是：即使學習器可能會被訓練集中的隨機錯誤和巧合規律所誤導，但驗證集合不大可能表現出同樣的隨機波動。所以驗證集可以用來對過度擬合訓練集中的虛假特征提供防護檢驗。第37頁，共66頁。REP——錯誤率降低剪枝

該剪枝方法考慮將樹上的每個節點作為修剪的候選對象，決定是否修剪這個結點由如下步驟組成：1：刪除以此結點為根的子樹2：使其成為葉子結點3：賦予該結點關聯的訓練數據的最常見分類4：當修剪后的樹對于驗證集合的性能不會比原來的樹差時，才真正刪除該結點訓練集合可能過擬合，使用驗證集合數據能夠對其進行修正，反復進行上面的操作，從底向上的處理結點，刪除那些能夠最大限度的提高驗證集合的精度的結點，直到進一步修剪有害為止(有害是指修剪會減低驗證集合的精度)。第38頁，共66頁。Pesimistic-ErrorPruning(PEP,悲觀錯誤剪枝）悲觀錯誤剪枝法是根據剪枝前后的錯誤率來判定子樹的修剪。該方法引入了統計學上連續修正的概念彌補REP中的缺陷，在評價子樹的訓練錯誤公式中添加了一個常數，假定每個葉子結點都自動對實例的某個部分進行錯誤的分類。把一棵子樹（具有多個葉子節點）的分類用一個葉子節點來替代的話，在訓練集上的誤判率肯定是上升的，但是在新數據上不一定。于是我們需要把子樹的誤判計算加上一個經驗性的懲罰因子。第39頁，共66頁。PEP——悲觀錯誤剪枝對于一個葉子節點，它覆蓋了N個樣本，其中有E個錯誤，那么該葉子節點的錯誤率為（E+0.5）/N。這個0.5就是懲罰因子，那么一棵子樹，它有L個葉子節點，那么該子樹的誤判率估計為這樣的話，我們可以看到一棵子樹雖然具有多個子節點，但由于加上了懲罰因子，所以子樹的誤判率計算未必占到便宜。剪枝后內部節點變成了葉子節點，其誤判個數J也需要加上一個懲罰因子，變成J+0.5。那么子樹是否可以被剪枝就取決于剪枝后的錯誤J+0.5在第40頁，共66頁。PEP續的標準誤差內。對于樣本的誤差率e，我們可以根據經驗把它估計成各種各樣的分布模型，比如是二項式分布，比如是正態分布。那么一棵樹錯誤分類一個樣本值為1，正確分類一個樣本值為0，該樹錯誤分類的概率（誤判率）為e（e為分布的固有屬性,可以通過統計出來），那么樹的誤判次數就是伯努利分布，我們可以估計出該樹的誤判次數均值和標準差：第41頁，共66頁。PEP續把子樹替換成葉子節點后，該葉子的誤判次數也是一個伯努利分布，其概率誤判率e為(E+0.5)/N，因此葉子節點的誤判次數均值為使用訓練數據，子樹總是比替換為一個葉節點后產生的誤差小，但是使用校正后有誤差計算方法卻并非如此，當子樹的誤判個數大過對應葉節點的誤判個數一個標準差之后，就決定剪枝：這個條件就是剪枝的標準。當然并不一定非要大一個標準差，可以給定任意的置信區間，我們設定一定的顯著性因子，就可以估算出誤判次數的上下界。第42頁，共66頁。PEP——小例題T4這棵子樹的誤差率：子樹誤判次數的標準誤差：子樹替換為一個葉節點后，其誤判個數為：7+0.5=7.5因為8.5+1.996>7.5，所以決定將子樹T4替換這一個葉子節點。第43頁，共66頁。Cost-ComplexityPruning（CCP，代價復雜度剪枝)該算法為子樹Tt定義了代價（cost）和復雜度（complexity），以及一個可由用戶設置的衡量代價與復雜度之間關系的參數α，其中，代價指在剪枝過程中因子樹Tt被葉節點替代而增加的錯分樣本，復雜度表示剪枝后子樹Tt減少的葉結點數，α則表示剪枝后樹的復雜度降低程度與代價間的關系，定義為其中，|N1|：子樹Tt中的葉節點數；R（t）：結點t的錯誤代價，計算公式為R（t）=r（t）*p（t），r（t）為結點t的錯分樣本率，p（t）為落入結點t的樣本占所有樣本的比例；R（Tt）：子樹Tt錯誤代價，計算公式為R（Tt）=∑R(i)，i為子樹Tt的葉節點。第44頁，共66頁。例子我們以非葉結點T4為例，假設已有的數據有60條，那么R(t)=r(t)*p(t)=(7/16)*(16/60)=7/60R（Tt）=∑R(i)=(2/5)*(5/60)+(0/2)*(2/60)+(3/9)*(9/60)=5/60α=（R(t)-R（Tt）)/(|N1|-1)=1/60第45頁，共66頁。CCP續CCP剪枝算法分為兩個步驟：1.對于完全決策樹T的每個非葉結點計算α值，循環剪掉具有最小α值的子樹，直到剩下根節點。在該步可得到一系列的剪枝樹｛T0，T1，T2......Tm｝,其中T0為原有的完全決策樹，Tm為根結點，Ti+1為對Ti進行剪枝的結果；2.從子樹序列中，根據真實的誤差估計選擇最佳決策樹。第46頁，共66頁。CCP續通常使用1-SE（1standarderrorofminimumerror）規則從步驟1產生的一系列剪枝樹中選擇一棵最佳的剪枝決策樹。方法為，假定一個含有N＇個樣本的剪枝集，分別用在步驟1中產生的剪枝樹Ti對該剪枝集進行分類，記Ti所有葉結點上長生的錯分樣本數為Ei，令E＇=min｛Ei｝，定義E＇的標準錯誤為：，所得的最佳剪枝樹Tbest是滿足條件Ei≤E＇+SE（E＇）且包含的接點數最少的那棵剪枝樹Ti。第47頁，共66頁。幾種后剪枝方法的比較REPPEPCCP剪枝方式自底向上自頂向下自底向上是否需要獨立剪枝集需要不需要不需要誤差估計剪枝集上的誤差估計使用連續校正標準誤差計算復雜度O(n)O(n)O(n2)第48頁，共66頁。1.5CART（分類與回歸樹）算法CART同樣由特征選擇、樹的生成及剪枝組成，既可以用于分類也可以用于回歸。CART假設決策樹是二叉樹，內部結點特征的取值為“是”和“否。這樣的決策樹等價于遞歸地二分每個特征。步驟：（1）決策樹生成：基于訓練數據集生成決策樹，生成的決策樹要盡量大；（2）決策樹剪枝：用驗證數據集對已生成的樹進行剪枝并選擇最優子樹，這時用損失函數最小作為剪枝的標準。第49頁，共66頁。1.5.1CART生成決策樹的生成就是遞歸地構建二叉決策樹的過程。對回歸樹用平方誤差最小化準則，對分類樹用基尼指數(Giniindex)最小化準則，進行特征選擇，生成二叉樹。最開始我們可以按：表面覆蓋為毛發與非毛發表面覆蓋為鱗片與非鱗片恒溫與非恒溫來產生當前結點的左右兩個孩子。我們將Gini指數來作為準則判別哪種劃分比較好。第50頁，共66頁。GINI指數

第51頁，共66頁。1.5.2CART剪枝

第52頁，共66頁。記原始數據為D，長度為N(即圖中有N個離散點)解決決策樹過擬合的另一種方法——隨機森林*當然可以使用決策樹作為基本分類器本質仍然是分類問題：對于某個電影，有N個決策樹，每個決策樹對該電影有1個分類(1、2、3、4、5類)，求這個電影應該屬于哪一類(可以是小數：分類問題變成了回歸問題)*在所有屬性上，對這n個樣本建立分類器(ID3、C4.T4這棵子樹的誤差率：但是基于損失函數找到全局最優決策樹是NP-完全問題。有多種不同的方式可以讓決策樹停止生長，下面介紹幾種停止決策樹生長的方法：*從所有屬性中隨機選擇k個屬性，選擇最佳分割屬性R：該電影的用戶投票的平均得分(Rating)把一棵子樹（具有多個葉子節點）的分類用一個葉子節點來替代的話，在訓練集上的誤判率肯定是上升的，但是在新數據上不一定。這些分類器組成的“總分類器”，仍然叫做隨機森林。*將數據放在這m個分類器上，最后根據這m個分類器不同類別

數目相等，則熵等于1，類別數目不等，則熵介于0,1之間。r（t）為結點t的錯分樣本率，p（t）為落入結點t的樣本占所有樣本的比例；使用訓練數據，子樹總是比替換為一個葉節點后產生的誤差小，但是使用校正后有誤差計算方法卻并非如此，當子樹的誤判個數大過對應葉節點的誤判個數一個標準差之后，就決定剪枝：實驗結果第53頁，共66頁。UCI\method\precisioniriswineBreast-cancer感知機100%--KNN88%73.33%-樸素貝葉斯97.8%95.62%95.614%決策樹100%96.4286%98.5507%第54頁，共66頁。解決決策樹過擬合的另一種方法——隨機森林BootstrapingBootstraping的名稱來自成語“pullupbyyourownbootstraps”，意思是依靠你自己的資源，稱為自助法，它是一種有放回的抽樣方法。注：Bootstrap本義是指高靴子口后面的懸掛物、小環、帶子，是穿靴子時用手向上拉的工具。“pullupbyyourownbootstraps”即“通過拉靴子讓自己上升”，意思是“不可能發生的事情”。后來意思發生了轉變，隱喻“不需要外界幫助，僅依靠自身力量讓自己變得更好”第55頁，共66頁。解決決策樹過擬合的另一種方法——隨機森林組合模型——Bagging的策略（三個臭皮匠頂個諸葛亮的意思）

*

bootstrapaggregation

*

從樣本集中重采樣(有重復的)選出n個樣本*在所有屬性上，對這n個樣本建立分類器(ID3、C4.5、

CART、SVM、Logistic回歸等)*重復以上兩步m次，即獲得了m個分類器*將數據放在這m個分類器上，最后根據這m個分類器

的投票結果，決定數據屬于哪一類第56頁，共66頁。解決決策樹過擬合的另一種方法——隨機森林第57頁，共66頁。解決決策樹過擬合的另一種方法——隨機森林隨機森林應用非常廣泛，根據目標變量的取值類型大致可分為兩類一種是分類：當目標變量取值為離散型時（屬性變量、種類變量、有序變量、多級變量等），采用該法可進行分類；

當目標變量為連續型，則可做回歸，對應的預測結果是目標變量的分布。優點：可以產生高準確度的分類器第58頁，共66頁。解決決策樹過擬合的另一種方法——隨機森林隨機森林在bagging基礎上做了修改。*從樣本集中用Bootstra