決策樹統(tǒng)計學(xué)習(xí)方法概述課件

1、決策樹根據(jù)李峰等人的PPT改編課件主要依據(jù)李航編寫的統(tǒng)計學(xué)習(xí)方法編制，清華大學(xué)出版社另一本參考書：數(shù)據(jù)挖掘與數(shù)學(xué)建模國防工業(yè)出版社 2010決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁) 決策樹 1.1 決策樹模型與學(xué)習(xí) 1.2 特征選擇 1.3 決策樹的生成 1.4 決策樹的剪枝 1.5 CART算法決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.1 決策樹模型與學(xué)習(xí) 1.1.1 決策樹模型 1.1.2 決策樹與if-then規(guī)則 1.1.3 決策樹與條件概率分布 1.1.4 決策樹學(xué)習(xí)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹

2、統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.1.1 決策樹模型什么是決策樹？定義1.1（決策樹） 分類決策樹模型是一種描述對實例進行分類的樹形結(jié)構(gòu)。決策樹由結(jié)點和有向邊組成。結(jié)點有兩種類型：內(nèi)部結(jié)點和葉節(jié)點。內(nèi)部結(jié)點表示一個特征或?qū)傩?，葉節(jié)點表示一個類。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹學(xué)習(xí)算法的特點 決策樹學(xué)習(xí)算法的最大優(yōu)點是，它可以自學(xué)習(xí)。在學(xué)習(xí)的過程中，不需要使用者了解過多背景知識，只需要對訓(xùn)練實例進行較好的標(biāo)注，就能夠進行學(xué)習(xí)。顯然，它屬于有監(jiān)督學(xué)習(xí)。從一類無序、無規(guī)則的事物(概念)中推理出決策樹表示的分類規(guī)則。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66

3、頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹學(xué)習(xí)的主要算法 建立決策樹的關(guān)鍵，即在當(dāng)前狀態(tài)下選擇哪個屬性作為分類依據(jù)。根據(jù)不同的目標(biāo)函數(shù)，建立決策樹主要有一下三種算法。ID3 （J. Ross Quinlan-1975）核心：信息熵C4.5ID3的改進，核心：信息增益比CART（Breiman-1984），核心：基尼指數(shù)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)例1. 找對象 決策樹分類的思想類似于找對象?，F(xiàn)想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話： 女兒：多大年紀(jì)了？ (年齡) 母親：26。 女兒：長的帥不帥？ (長相) 母親：挺帥的

4、。 女兒：收入高不？ (收入情況) 母親：不算很高，中等情況。 女兒：是公務(wù)員不？ (是否公務(wù)員) 母親：是，在稅務(wù)局上班呢。 女兒：那好，我去見見。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.1.2 決策樹與if-then規(guī)則由決策樹的根結(jié)點到葉結(jié)點的每一條路徑構(gòu)建一條規(guī)則；路徑上內(nèi)部結(jié)點的特征對應(yīng)著規(guī)則的條件，而葉結(jié)點的類對應(yīng)著規(guī)則的結(jié)論。If-then規(guī)則集合的一重要性質(zhì)：互斥并且完備決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.1.3 決策樹與條件概率分布 將特征空間劃分為互不相交的單元或區(qū)域，并在每個單元定義一個類

5、的概率分布就構(gòu)成了一個條件概率分布。 各葉結(jié)點(單元)上的條件概率往往偏向某一個類，即屬于某一類的概率較大，決策樹分類時將該結(jié)點的實例強行分到條件概率大的那一類去。 決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.1.4 決策樹學(xué)習(xí)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.1.4 決策樹學(xué)習(xí)目標(biāo)：我們需要的是一個與訓(xùn)練數(shù)據(jù)矛盾較小的決策樹，同時具有很好的泛化能力。決策樹學(xué)習(xí)的損失函數(shù)：（通常是）正則化的極大似然函數(shù)。但是基于損失函數(shù)找到全局最優(yōu)決策樹是NP-完全問題?，F(xiàn)實中決策樹學(xué)習(xí)通常采用啟發(fā)式方法，即局部最優(yōu)。具體做法：

6、每次選擇feature時，都挑選擇當(dāng)前條件下最優(yōu)的那個feature作為劃分規(guī)則，即局部最優(yōu)的feature。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.2 特征選擇1.2.1 特征選擇問題特征選擇在于選取對訓(xùn)練數(shù)據(jù)具有分類能力的特征。如何判斷一個特征對于當(dāng)前數(shù)據(jù)集的分類效果？ 也即確定選擇特征的準(zhǔn)則。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)ID年齡有工作有自己的房子信貸情況類別1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年

7、否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否例1.2 右表是一個由15個樣本組成的貸款申請訓(xùn)練數(shù)據(jù)。數(shù)據(jù)包括貸款申請人的四個特征。表的最后一列是類別，是否同意貸款，取2個值：是、否。希望通過所給的訓(xùn)練數(shù)據(jù)學(xué)習(xí)一個貸款申請的決策樹，用以對未來的貸款申請進行分類。特征選擇是決定用哪個特征來劃分特征空間。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.2.2 信息增益決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)熵-就分類而言，所有成員都屬于一類，熵為零；不同類別 數(shù)目相等，則熵等

8、于1，類別數(shù)目不等，則熵介于0,1之間。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)條件熵決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)信息增益決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)信息增益的具體公式?jīng)Q策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)信息增益算法決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)例1.3 對表1.1所給的訓(xùn)練數(shù)據(jù)集D,根據(jù)信息增益準(zhǔn)則選擇最優(yōu)特征。ID年齡有工作有自己的房子信貸情況類別1青年否否一般否2青年否否好

9、否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.2.3 信息增益比決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.3 決策樹的生成1.3.1 ID3算法決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)例1.4 對表1.1的訓(xùn)練數(shù)據(jù)集，利用ID3算法建立決策樹ID年齡有工作信貸情況類別1青

10、年否一般否2青年否好否3青年是好是5青年否一般否6中年否一般否7中年否好否13老年是好是14老年是非常好是15老年否一般否有自己的房子(A3)ID年齡有工作信貸情況類別4青年是一般是8中年是好是9中年否非常好是10中年否非常好是11老年否非常好是12老年都好是是否表1表2決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)有自己的房子是否是是否有工作ID年齡信貸情況類別3青年好是13老年好是14老年非常好是表3ID年齡信貸情況類別1青年一般否2青年好否5青年一般否6中年一般否7中年好否15老年一

11、般否表4 這里生成的決策樹只用到兩個特征（兩個內(nèi)節(jié)點），ID3算法容易存在過擬合問題。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)補充：如何解決決策樹的過擬合問題概念原因解決什么是過度擬合數(shù)據(jù)過度擬合數(shù)據(jù)是怎么產(chǎn)生的怎么去解決這個問題決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)補充：如何解決決策樹的過擬合問題概念 過度擬合（overfitting）：如果決策樹對訓(xùn)練樣本的特征描述得“過于精確”，無法實現(xiàn)對新樣本的合理分析，所以此時它不是一棵分析新數(shù)據(jù)的最佳決策樹。一棵完全決策樹能非常準(zhǔn)確地反映訓(xùn)練集中數(shù)據(jù)的特征，但因失去了一般代表

12、性而無法用于對新數(shù)據(jù)的分類或預(yù)測，這種現(xiàn)象一般稱為“過擬合”。 定義：給定一個假設(shè)H，如果在假設(shè)空間上存在另一個假設(shè)H，使得在訓(xùn)練集上H的錯誤率差比H小，而在測試集上H的錯誤率卻比H要大，那么稱假設(shè)H過度擬合訓(xùn)練數(shù)據(jù)。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)二.產(chǎn)生過度擬合數(shù)據(jù)問題的原因有哪些？原因1：樣本問題 （1）樣本里的噪音數(shù)據(jù)干擾過大，大到模型過分記住了噪音特征，反而忽略了真實的輸入輸出間的關(guān)系；（什么是噪音數(shù)據(jù)？） （2）樣本抽取錯誤，包括（但不限于）樣本數(shù)量太少，抽樣方法錯誤，抽樣時沒有足夠正確考慮業(yè)務(wù)場景或業(yè)務(wù)特點，等等導(dǎo)致抽出的樣本數(shù)據(jù)不能有

13、效足夠代表業(yè)務(wù)邏輯或業(yè)務(wù)場景； （3）建模時使用了樣本中太多無關(guān)的輸入變量。原因2：構(gòu)建決策樹的方法問題 在決策樹模型搭建中，我們使用的算法對于決策樹的生長沒有合理的限制和修剪的話，決策樹的自由生長有可能每片葉子里只包含單純的事件數(shù)據(jù)或非事件數(shù)據(jù)，可以想象，這種決策樹當(dāng)然可以完美匹配（擬合）訓(xùn)練數(shù)據(jù)，但是一旦應(yīng)用到新的業(yè)務(wù)真實數(shù)據(jù)時，效果是一塌糊涂。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)三.如何解決過度擬合數(shù)據(jù)問題？針對原因1的解決方法： 合理、有效地抽樣，用相對能夠反映業(yè)務(wù)邏輯的訓(xùn)練 集去產(chǎn)生決策樹；針對原因2的主要解決方法： 剪枝：提前停止樹的增長或者

14、對已經(jīng)生成的樹按照一 定的規(guī)則進行后剪枝。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.3.2 C4.5的生成算法 C4.5算法與ID3算法相似，C4.5算法對ID3算法進行了改進.C4.5在生成的過程中，用信息增益比來選擇特征。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.4 決策樹的剪枝決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)算法1.4 樹的剪枝算法決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)關(guān)于剪枝的補充先剪枝剪枝是一個簡化過擬合決策樹的過程。有兩種常用

15、的剪枝方法： 先剪枝（prepruning）：通過提前停止樹的構(gòu)建而對樹“剪枝”，一旦停止，節(jié)點就成為樹葉。該樹葉可以持有子集元組中最頻繁的類； 有多種不同的方式可以讓決策樹停止生長，下面介紹幾種停止決策樹生長的方法： 1.定義一個高度，當(dāng)決策樹達到該高度時就可以停止決策樹的生長，這是一種最為簡單的方法； 2.達到某個結(jié)點的實例具有相同的特征向量，即使這些實例不屬于同一類，也可以停止決策樹的生長。這種方法對于處理數(shù)據(jù)中的數(shù)據(jù)沖突問題非常有效；決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)補充：關(guān)于剪枝先剪枝 3.定義一個閾值，當(dāng)達到某個結(jié)點的實例個數(shù)小于該閾值時就

16、可以停止決策樹的生長； 4.定義一個閾值，通過計算每次擴張對系統(tǒng)性能的增益，并比較增益值與該閾值的大小來決定是否停止決策樹的生長。 先剪枝方法不但相對簡單，效率很高，而且不需要生成整個決策樹，適合于解決大規(guī)模問題。該方法看起來很直接，但要精確地估計決策樹生長的停止時間并不容易，即選取一個恰當(dāng)?shù)拈撝凳欠浅＠щy的。高閾值可能導(dǎo)致過分簡化的樹，而低閾值可能使得樹的簡化太少。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)關(guān)于剪枝的補充后剪枝 后剪枝（postpruning）：它首先構(gòu)造完整的決策樹，允許樹過度擬合訓(xùn)練數(shù)據(jù)，然后對那些置信度不夠的結(jié)點子樹用葉子結(jié)點來代替，該

17、葉子的類標(biāo)號用該結(jié)點子樹中最頻繁的類標(biāo)記。相比于先剪枝，這種方法更常用，正是因為在先剪枝方法中精確地估計何時停止樹增長很困難。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)補充：關(guān)于剪枝的準(zhǔn)則無論是通過及早停止還是后修剪來得到正確規(guī)模的樹，一個關(guān)鍵的問題是使用什么樣的準(zhǔn)則來確定最終正確樹的規(guī)模： 1.使用訓(xùn)練集合(Training Set）和驗證集合(Validation Set)，來評估剪枝方法在修剪結(jié)點上的效用。 2.使用所有的訓(xùn)練集合進行訓(xùn)練，但是用統(tǒng)計測試來估計修剪特定結(jié)點是否會改善訓(xùn)練集合外的數(shù)據(jù)的評估性能。測試來進一步擴展結(jié)點是否能改善整個分類數(shù)據(jù)的性

18、能，還是僅僅改善了當(dāng)前訓(xùn)練集合數(shù)據(jù)上的性能。 3.使用明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的復(fù)雜度，當(dāng)編碼長度最小時，停止樹增長，如MDL(Minimum Description Length)準(zhǔn)則。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)補充：關(guān)于剪枝的準(zhǔn)則Reduced-Error Pruning(REP,錯誤率降低剪枝） REP方法是一種比較簡單的后剪枝的方法，在該方法中，可用的數(shù)據(jù)被分成兩個樣例集合：一個訓(xùn)練集用來形成學(xué)習(xí)到的決策樹，一個分離的驗證集用來評估這個決策樹在后續(xù)數(shù)據(jù)上的精度，確切地說是用來評估修剪這個決策樹的影響。 這個方法的動機是：即使學(xué)習(xí)

19、器可能會被訓(xùn)練集中的隨機錯誤和巧合規(guī)律所誤導(dǎo)，但驗證集合不大可能表現(xiàn)出同樣的隨機波動。所以驗證集可以用來對過度擬合訓(xùn)練集中的虛假特征提供防護檢驗。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)REP錯誤率降低剪枝 該剪枝方法考慮將樹上的每個節(jié)點作為修剪的候選對象，決定是否修剪這個結(jié)點由如下步驟組成： 1：刪除以此結(jié)點為根的子樹 2：使其成為葉子結(jié)點 3：賦予該結(jié)點關(guān)聯(lián)的訓(xùn)練數(shù)據(jù)的最常見分類 4：當(dāng)修剪后的樹對于驗證集合的性能不會比原來的樹差時，才真正刪除該結(jié)點 訓(xùn)練集合可能過擬合，使用驗證集合數(shù)據(jù)能夠?qū)ζ溥M行修正，反復(fù)進行上面的操作，從底向上的處理結(jié)點，刪除那些能

20、夠最大限度的提高驗證集合的精度的結(jié)點，直到進一步修剪有害為止(有害是指修剪會減低驗證集合的精度)。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)Pesimistic-Error Pruning(PEP,悲觀錯誤剪枝） 悲觀錯誤剪枝法是根據(jù)剪枝前后的錯誤率來判定子樹的修剪。該方法引入了統(tǒng)計學(xué)上連續(xù)修正的概念彌補REP中的缺陷，在評價子樹的訓(xùn)練錯誤公式中添加了一個常數(shù)，假定每個葉子結(jié)點都自動對實例的某個部分進行錯誤的分類。 把一棵子樹（具有多個葉子節(jié)點）的分類用一個葉子節(jié)點來替代的話，在訓(xùn)練集上的誤判率肯定是上升的，但是在新數(shù)據(jù)上不一定。于是我們需要把子樹的誤判計算加

21、上一個經(jīng)驗性的懲罰因子。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)PEP悲觀錯誤剪枝 對于一個葉子節(jié)點，它覆蓋了N個樣本，其中有E個錯誤，那么該葉子節(jié)點的錯誤率為（E+0.5）/N。這個0.5就是懲罰因子，那么一棵子樹，它有L個葉子節(jié)點，那么該子樹的誤判率估計為這樣的話，我們可以看到一棵子樹雖然具有多個子節(jié)點，但由于加上了懲罰因子，所以子樹的誤判率計算未必占到便宜。剪枝后內(nèi)部節(jié)點變成了葉子節(jié)點，其誤判個數(shù)J也需要加上一個懲罰因子，變成J+0.5。那么子樹是否可以被剪枝就取決于剪枝后的錯誤J+0.5在決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(

22、PPT66頁)PEP續(xù)的標(biāo)準(zhǔn)誤差內(nèi)。對于樣本的誤差率e，我們可以根據(jù)經(jīng)驗把它估計成各種各樣的分布模型，比如是二項式分布，比如是正態(tài)分布。 那么一棵樹錯誤分類一個樣本值為1，正確分類一個樣本值為0，該樹錯誤分類的概率（誤判率）為e（e為分布的固有屬性,可以通過統(tǒng)計出來），那么樹的誤判次數(shù)就是伯努利分布，我們可以估計出該樹的誤判次數(shù)均值和標(biāo)準(zhǔn)差：決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)PEP續(xù) 把子樹替換成葉子節(jié)點后，該葉子的誤判次數(shù)也是一個伯努利分布，其概率誤判率e為(E+0.5)/N，因此葉子節(jié)點的誤判次數(shù)均值為 使用訓(xùn)練數(shù)據(jù)，子樹總是比替換為一個葉節(jié)點后產(chǎn)

23、生的誤差小，但是使用校正后有誤差計算方法卻并非如此，當(dāng)子樹的誤判個數(shù)大過對應(yīng)葉節(jié)點的誤判個數(shù)一個標(biāo)準(zhǔn)差之后，就決定剪枝： 這個條件就是剪枝的標(biāo)準(zhǔn)。當(dāng)然并不一定非要大一個標(biāo)準(zhǔn)差，可以給定任意的置信區(qū)間，我們設(shè)定一定的顯著性因子，就可以估算出誤判次數(shù)的上下界。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)PEP小例題T4這棵子樹的誤差率：子樹誤判次數(shù)的標(biāo)準(zhǔn)誤差：子樹替換為一個葉節(jié)點后，其誤判個數(shù)為：7+0.5=7.5因為8.5+1.9967.5，所以決定將子樹T4替換這一個葉子節(jié)點。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)Cost-

24、Complexity Pruning（CCP，代價復(fù)雜度剪枝) 該算法為子樹Tt定義了代價（cost）和復(fù)雜度（complexity），以及一個可由用戶設(shè)置的衡量代價與復(fù)雜度之間關(guān)系的參數(shù)，其中，代價指在剪枝過程中因子樹Tt被葉節(jié)點替代而增加的錯分樣本，復(fù)雜度表示剪枝后子樹Tt減少的葉結(jié)點數(shù)，則表示剪枝后樹的復(fù)雜度降低程度與代價間的關(guān)系，定義為其中，|N1|：子樹Tt中的葉節(jié)點數(shù)；R（t）：結(jié)點t的錯誤代價，計算公式為R（t）=r（t）*p（t），r（t）為結(jié)點t的錯分樣本率，p（t）為落入結(jié)點t的樣本占所有樣本 的比例；R（Tt）：子樹Tt錯誤代價，計算公式為R（Tt）=R(i)，i為子樹T

25、t的葉節(jié)點。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)例子我們以非葉結(jié)點T4為例，假設(shè)已有的數(shù)據(jù)有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決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)CCP續(xù)CCP剪枝算法分為兩個步驟： 1.對于完全決策樹T的每個非葉結(jié)點計算值，循環(huán)剪掉具有最小值的子樹，直到剩下根節(jié)點。在該步可得到一系列的剪枝樹T

26、0，T1，T2.Tm,其中T0為原有的完全決策樹，Tm為根結(jié)點，Ti+1為對Ti進行剪枝的結(jié)果； 2.從子樹序列中，根據(jù)真實的誤差估計選擇最佳決策樹。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)CCP續(xù) 通常使用1-SE（1 standard error of minimum error）規(guī)則從步驟1產(chǎn)生的一系列剪枝樹中選擇一棵最佳的剪枝決策樹。方法為，假定一個含有N個樣本的剪枝集，分別用在步驟1中產(chǎn)生的剪枝樹Ti對該剪枝集進行分類，記Ti所有葉結(jié)點上長生的錯分樣本數(shù)為Ei，令E=minEi，定義E的標(biāo)準(zhǔn)錯誤為：，所得的最佳剪枝樹Tbest是滿足條件EiE+SE

27、（E）且包含的接點數(shù)最少的那棵剪枝樹Ti。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)幾種后剪枝方法的比較REPPEPCCP剪枝方式自底向上自頂向下自底向上是否需要獨立剪枝集需要不需要不需要誤差估計剪枝集上的誤差估計使用連續(xù)校正標(biāo)準(zhǔn)誤差計算復(fù)雜度O(n)O(n)O(n2)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.5 CART（分類與回歸樹）算法CART同樣由特征選擇、樹的生成及剪枝組成，既可以用于分類也可以用于回歸。CART假設(shè)決策樹是二叉樹，內(nèi)部結(jié)點特征的取值為“是”和“否。這樣的決策樹等價于遞歸地二分每個特征。步驟：（1

28、）決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大；（2）決策樹剪枝：用驗證數(shù)據(jù)集對已生成的樹進行剪枝并選擇最優(yōu)子樹，這時用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.5.1 CART生成決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過程。對回歸樹用平方誤差最小化準(zhǔn)則，對分類樹用基尼指數(shù)(Gini index)最小化準(zhǔn)則，進行特征選擇，生成二叉樹。最開始我們可以按：表面覆蓋為毛發(fā)與非毛發(fā)表面覆蓋為鱗片與非鱗片恒溫與非恒溫來產(chǎn)生當(dāng)前結(jié)點的左右兩個孩子。我們將Gini指數(shù)來作為準(zhǔn)則判別哪種劃分比較好。決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT6

29、6頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)GINI指數(shù)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)1.5.2 CART剪枝決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)實驗結(jié)果決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)UCImethodprecisioniriswineBreast-cancer感知機100%-KNN88%73.33%-樸素貝葉斯97.8%95.62%95.614%決策樹100%96.4286%98.5507%決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66

30、頁)解決決策樹過擬合的另一種方法隨機森林BootstrapingBootstraping的名稱來自成語“pull up by your own bootstraps”，意思是依靠你自己的資源，稱為自助法，它是一種有放回的抽樣方法。注：Bootstrap本義是指高靴子口后面的懸掛物、小環(huán)、帶子，是穿靴子時用手向上拉的工具?！皃ull up by your own bootstraps”即“通過拉靴子讓自己上升”，意思是“不可能發(fā)生的事情”。后來意思發(fā)生了轉(zhuǎn)變，隱喻“不需要外界幫助，僅依靠自身力量讓自己變得更好”決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)解決決策樹

31、過擬合的另一種方法隨機森林組合模型Bagging的策略（三個臭皮匠頂個諸葛亮的意思） * bootstrap aggregation * 從樣本集中重采樣(有重復(fù)的)選出n個樣本 * 在所有屬性上，對這n個樣本建立分類器(ID3、C4.5、 CART、SVM、Logistic回歸等) *重復(fù)以上兩步m次，即獲得了m個分類器 *將數(shù)據(jù)放在這m個分類器上，最后根據(jù)這m個分類器 的投票結(jié)果，決定數(shù)據(jù)屬于哪一類決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)解決決策樹過擬合的另一種方法隨機森林決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)解決決

32、策樹過擬合的另一種方法隨機森林隨機森林應(yīng)用非常廣泛，根據(jù)目標(biāo)變量的取值類型大致可分為兩類 一種是分類：當(dāng)目標(biāo)變量取值為離散型時（屬性變量、種類變量、有序變量、多級變量等），采用該法可進行分類； 當(dāng)目標(biāo)變量為連續(xù)型，則可做回歸，對應(yīng)的預(yù)測結(jié)果是目標(biāo)變量的分布。 優(yōu)點：可以產(chǎn)生高準(zhǔn)確度的分類器決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)決策樹統(tǒng)計學(xué)習(xí)方法概述(PPT66頁)解決決策樹過擬合的另一種方法隨機森林隨機森林在bagging基礎(chǔ)上做了修改。* 從樣本集中用Bootstrap采樣選出n個樣本；* 從所有屬性中隨機選擇k個屬性，選擇最佳分割屬性 作為節(jié)點建立CART決策樹；* 重復(fù)以上兩步m次，即建立了m棵CART決策樹* 這m個CART形成隨機森林，通過投票表決結(jié)果，決