分類基本概念決策樹與模型評估演示文稿

分類基本概念決策樹與模型評估演示文稿當(dāng)前第1頁\共有59頁\編于星期日\19點(diǎn)優(yōu)選分類基本概念決策樹與模型評估當(dāng)前第2頁\共有59頁\編于星期日\19點(diǎn)分類任務(wù)的輸入數(shù)據(jù)是記錄的集合。每條記錄也稱實(shí)例或者樣例，用元組（x,y）表示，其中x是屬性的集合，而y是一個特殊的屬性，指出樣例的類標(biāo)號（也成為分類屬性或目標(biāo)屬性）。分類？回歸？當(dāng)前第3頁\共有59頁\編于星期日\19點(diǎn)分類（classification）

通過學(xué)習(xí)得到一個目標(biāo)函數(shù)（targetfunction），也成為分類模型（classificationmodel），把每個屬性集x映射到一個預(yù)先定義的類標(biāo)號y。目的：1、描述性建模

分類模型可以作為解釋性的工具，用于區(qū)分不同類中的對象。2、預(yù)測性建模

分類模型還可以用于預(yù)測未知記錄的類標(biāo)號。名字體溫表皮覆蓋胎生水生動物飛行動物有腿冬眠類標(biāo)號毒蜥冷血鱗片否否否是是？當(dāng)前第4頁\共有59頁\編于星期日\19點(diǎn)輸入屬性集（x）

分類模型輸出類標(biāo)號（y）分類器的任務(wù)：根據(jù)輸入屬性集x確定類標(biāo)號y分類技術(shù)非常適合預(yù)測或描述二元或標(biāo)稱類型的數(shù)據(jù)集，對序數(shù)分類不太有效，因?yàn)榉诸惣夹g(shù)不考慮隱含在目標(biāo)類中的序關(guān)系。當(dāng)前第5頁\共有59頁\編于星期日\19點(diǎn)分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。分類技術(shù)決策樹分類法基于規(guī)則的分類法神經(jīng)網(wǎng)絡(luò)支持向量機(jī)這些技術(shù)都使用一種學(xué)習(xí)算法確定分類模型，修改這個模型能夠很好地?cái)M合輸入數(shù)據(jù)中類標(biāo)號和屬性集之間的聯(lián)系。學(xué)習(xí)算法得到的模型不僅要很好地?cái)M合輸入數(shù)據(jù)，還要能夠正確地預(yù)測未知樣本的類標(biāo)號。訓(xùn)練算法的目標(biāo)：建立具有很好的泛化能力的模型。二、解決分類問題的一般方法樸素貝葉斯分類法當(dāng)前第6頁\共有59頁\編于星期日\19點(diǎn)訓(xùn)練集：由類標(biāo)號已知的記錄構(gòu)成檢驗(yàn)集：由類標(biāo)號未知的記錄構(gòu)成當(dāng)前第7頁\共有59頁\編于星期日\19點(diǎn)預(yù)測的類類=1類=0實(shí)際的類類=1類=0二類問題的混淆矩陣表中每個表項(xiàng)表示實(shí)際類標(biāo)號為但是被預(yù)測為類的記錄數(shù)。被分類模型正確預(yù)測的樣本總數(shù)是，而被錯誤預(yù)測的樣本總數(shù)是。雖然混淆矩陣提供衡量分類模型的信息，但是用一個數(shù)匯總這些信息更便于比較不同模型的性能。為實(shí)現(xiàn)這一目的，可以使用性能度量（performancemetric），如準(zhǔn)確率（accuracy），其定義如下：當(dāng)前第8頁\共有59頁\編于星期日\19點(diǎn)同樣，分類模型的性能也可以用錯誤率（errorrate）來表示，其定義如下：目標(biāo)：尋求最高的準(zhǔn)確率或者最低的錯誤率當(dāng)前第9頁\共有59頁\編于星期日\19點(diǎn)1、什么是決策樹？類似于流程圖的樹結(jié)構(gòu)每個內(nèi)部節(jié)點(diǎn)表示在一個屬性上的測試每個分枝代表一個測試輸出每個葉節(jié)點(diǎn)代表類或類分布三、決策樹（decisiontree）歸納3、決策樹的使用：對未知樣本進(jìn)行分類通過將樣本的屬性值與決策樹相比較2、決策樹的生成由兩個階段組成決策樹構(gòu)建開始時(shí)，所有的訓(xùn)練樣本都在根節(jié)點(diǎn)遞歸通過選定的屬性，來劃分樣本（必須是離散值）樹剪枝許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn)，樹剪枝試圖檢測和剪去這種分枝當(dāng)前第10頁\共有59頁\編于星期日\19點(diǎn)根結(jié)點(diǎn)（rootnode）：它沒有入邊，但是有零條或多條出邊。內(nèi)部結(jié)點(diǎn)（internalnode）：恰好有一條入邊和兩條或多條出邊。葉節(jié)點(diǎn)（leafnode）或終結(jié)點(diǎn)（terminalnode）：恰好有一條入邊，但沒有出邊。葉結(jié)點(diǎn)根結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)體溫胎生非哺乳動物哺乳動物非哺乳動物恒溫否冷血是當(dāng)前第11頁\共有59頁\編于星期日\19點(diǎn)

一旦構(gòu)造了決策樹，對檢驗(yàn)記錄進(jìn)行分類就很容易。從樹的根結(jié)點(diǎn)開始，將測試條件用于檢驗(yàn)記錄，根據(jù)測試結(jié)果選擇適當(dāng)?shù)姆种?。沿著該分支或者到達(dá)另一個內(nèi)部結(jié)點(diǎn)，使用新的測試條件，或者到達(dá)一個葉結(jié)點(diǎn)。到達(dá)葉結(jié)點(diǎn)之后，葉結(jié)點(diǎn)的類標(biāo)號就被賦值給該檢驗(yàn)記錄。名字體溫胎生……類標(biāo)號火烈鳥恒溫否……？體溫胎生非哺乳動物哺乳動物非哺乳動物恒溫否冷血是當(dāng)前第12頁\共有59頁\編于星期日\19點(diǎn)如何建立決策樹

對于給定的屬性集，可以構(gòu)造的決策樹的數(shù)目達(dá)指數(shù)級。盡管某些決策樹比其他決策樹更準(zhǔn)確，但是由于搜索空間是指數(shù)規(guī)模的，找出最佳決策樹在計(jì)算上是不可行的。盡管如此，人們還是開發(fā)了一些有效的算法，能夠在合理的時(shí)間內(nèi)構(gòu)造出具有一定準(zhǔn)確率的次最優(yōu)決策樹。這些算法通常都采用貪心策略。有許多決策樹算法:Hunt算法信息增益——Informationgain

（ID3）增益比率——Gainration（C4.5）基尼指數(shù)——Giniindex

(SLIQ，SPRINT)當(dāng)前第13頁\共有59頁\編于星期日\19點(diǎn)在Hunt算法中，通過將訓(xùn)練記錄相繼劃分成較純的子集，以遞歸方式建立決策樹。設(shè)是與結(jié)點(diǎn)t相關(guān)聯(lián)的訓(xùn)練記錄集，而是類標(biāo)號，Hunt算法的遞歸定義如下。（1）如果中所有記錄都屬于同一個類，則t是葉結(jié)點(diǎn)，用標(biāo)記。（2）如果中包含屬于多個類的記錄，則選擇一個屬性測試條件，將記錄劃分成較小的子集。對于測試條件的每個輸出，創(chuàng)建一個子女結(jié)點(diǎn)，并根據(jù)測試結(jié)果將中的記錄分布到子女結(jié)點(diǎn)中。然后，對于每個子女結(jié)點(diǎn)，遞歸地調(diào)用該算法。當(dāng)前第14頁\共有59頁\編于星期日\19點(diǎn)Hunt算法Tid有房者婚姻狀況年收入拖欠貸款者1是單身125k否2否已婚100k否3否單身70k否4是已婚120k否5否離異95k是6否已婚60k否7是離異220k否8否單身85k是9否已婚75k否10否單身90k是當(dāng)前第15頁\共有59頁\編于星期日\19點(diǎn)拖欠貸款者=否拖欠貸款者=否拖欠貸款者=否有房者拖欠貸款者=否有房者拖欠貸款者=否婚姻狀況年收入拖欠貸款者=是拖欠貸款者=否(b)(c)(d)(a)拖欠貸款者=否有房者拖欠貸款者=否婚姻狀況拖欠貸款者=是是是否否否是單身離異單身離異已婚已婚<80k>=80kHunt算法構(gòu)造決策樹當(dāng)前第16頁\共有59頁\編于星期日\19點(diǎn)如果屬性值的每種組合都在訓(xùn)練數(shù)據(jù)中出現(xiàn)，并且每種組合都具有唯一的類標(biāo)號，則Hunt算法是有效的。但是對于大多數(shù)實(shí)際情況，這些假設(shè)太苛刻了，因此，需要附加的條件來處理以下的情況：（1）算法的第二步所創(chuàng)建的子女結(jié)點(diǎn)可能為空，即不存在與這些結(jié)點(diǎn)相關(guān)聯(lián)的記錄。如果沒有一個訓(xùn)練記錄包含這樣的結(jié)點(diǎn)相關(guān)聯(lián)的屬性值組合，這種情形就可能發(fā)生。這時(shí)，該結(jié)點(diǎn)成為葉結(jié)點(diǎn)，類標(biāo)號為其父結(jié)點(diǎn)上訓(xùn)練記錄中的多數(shù)類。（2）在第二步，如果與相關(guān)聯(lián)的所有記錄都具有相同的屬性值（目標(biāo)屬性除外），則不可能進(jìn)一步劃分這些記錄。在這種情況下，該結(jié)點(diǎn)為葉結(jié)點(diǎn)，其標(biāo)號為與該結(jié)點(diǎn)相關(guān)聯(lián)的訓(xùn)練記錄中的多數(shù)類。當(dāng)前第17頁\共有59頁\編于星期日\19點(diǎn)決策樹歸納的設(shè)計(jì)問題（1）如何分裂訓(xùn)練記錄？（2）如何停止分裂過程？樹增長過程的每個遞歸步驟都必須選擇一個屬性測試條件，將記錄劃分成較小的子集。為了實(shí)現(xiàn)這個步驟。算法必須提供為不同類型的屬性指定測試條件的方法，并且提供評估每種測試條件的客觀度量。決策樹需要有結(jié)束條件，以終止決策樹的生長過程。一個可能的策略是分裂結(jié)點(diǎn)，直到所有的記錄都屬于同一個類，或者所有的記錄都具有相同的屬性值。當(dāng)前第18頁\共有59頁\編于星期日\19點(diǎn)表示屬性測試條件的方法1、二元屬性

二元屬性的測試條件產(chǎn)生兩個可能的輸出。體溫恒溫冷血二元屬性的測試條件當(dāng)前第19頁\共有59頁\編于星期日\19點(diǎn)2、標(biāo)稱屬性由于標(biāo)稱屬性有多個屬性值，它的測試條件可以用兩種方法表示。婚姻狀況單身已婚離異婚姻狀況已婚單身，離異婚姻狀況離異單身，已婚婚姻狀況單身已婚，離異多路劃分二元劃分（通過屬性值分組）當(dāng)前第20頁\共有59頁\編于星期日\19點(diǎn)3、序數(shù)屬性序數(shù)屬性也可以產(chǎn)生二元或多路劃分，只要不違背序數(shù)屬性值的有序性，就可以對屬性值進(jìn)行分組。襯衣尺碼小號，中號大號，加大號襯衣尺碼小號中號，加大號襯衣尺碼小號，大號中號，加大號（a）（b）（c）當(dāng)前第21頁\共有59頁\編于星期日\19點(diǎn)4、連續(xù)屬性對于連續(xù)屬性來說，測試條件可以是具有二元輸出的比較測試或也可以是具有形如輸出的范圍查詢。年收入>80k（a）（b）年收入是否<10k{10k,25k}<10k{25k,50k}{50k,80k}連續(xù)屬性的測試條件當(dāng)前第22頁\共有59頁\編于星期日\19點(diǎn)有很多度量可以用來確定劃分記錄的最佳方法，這些度量用劃分前和劃分后的記錄的類分布定義。選擇最佳劃分的度量設(shè)表示給定結(jié)點(diǎn)t中屬于類i的記錄所占的比例，有時(shí)，我們省略結(jié)點(diǎn)t，直接用表示該比例。在兩類問題中，任意結(jié)點(diǎn)的類分布都可以記作其中。性別男女車型家用運(yùn)動豪華C0:6C1:4C0:4C1:6C0:1C1:3C0:8C1:0C0:1C1:7（b）（a）C0:1C1:0C0:1C1:0C0:0C1:1C0:0C1:1顧客IDv1v10v20v11（c）……當(dāng)前第23頁\共有59頁\編于星期日\19點(diǎn)選擇最佳劃分的度量通常是根據(jù)劃分后子女結(jié)點(diǎn)不純性的度量。不純的程度越低，類分布就越傾斜。例如（0,1）的結(jié)點(diǎn)具有零不純性，而均衡分布（0.5,0.5）的結(jié)點(diǎn)具有最高的不純性。不純性度量的例子包括：熵：基尼指數(shù)：分類誤差：其中c是類的個數(shù)，并且在計(jì)算熵時(shí)，當(dāng)前第24頁\共有59頁\編于星期日\19點(diǎn)結(jié)點(diǎn)N1計(jì)數(shù)類=00類=16結(jié)點(diǎn)N3計(jì)數(shù)類=03類=13結(jié)點(diǎn)N2計(jì)數(shù)類=01類=15當(dāng)前第25頁\共有59頁\編于星期日\19點(diǎn)二元分類問題不純性度量之間的比較不同的不純性度量是一致的，但是作為測試條件的屬性選擇仍然因不純性度量的選擇而異。當(dāng)前第26頁\共有59頁\編于星期日\19點(diǎn)為確定測試條件的效果，我們需要比較父結(jié)點(diǎn)（劃分前）的不純性程度和子女結(jié)點(diǎn)（劃分后）的不純性程度，它們的差越大，測試條件的效果就越好。增益是一種可以用來確定劃分效果的標(biāo)準(zhǔn)：其中，是給定結(jié)點(diǎn)的不純性度量，N是父結(jié)點(diǎn)上的記錄總數(shù)，k是屬性值的個數(shù)，是與子女結(jié)點(diǎn)相關(guān)聯(lián)的記錄個數(shù)。決策樹算法選擇最大化增益的測試條件。當(dāng)前第27頁\共有59頁\編于星期日\19點(diǎn)B是否結(jié)點(diǎn)N1結(jié)點(diǎn)N2A是否結(jié)點(diǎn)N1結(jié)點(diǎn)N2父結(jié)點(diǎn)C06C16Gini=0.500N1N2C042C133Gini=0.486N1N2C015C142Gini=0.3711、二元屬性的劃分當(dāng)前第28頁\共有59頁\編于星期日\19點(diǎn)2、標(biāo)稱屬性的劃分車型{運(yùn)動，豪華}{家用}C091C173Gini0.468車型{運(yùn)動}{家用，豪華}C082C1010Gini0.167車型{家用}{運(yùn)動}{豪華}C0181C1307Gini0.163（a）二元劃分(b)多路劃分標(biāo)稱屬性可以產(chǎn)生二元劃分或者多路劃分當(dāng)前第29頁\共有59頁\編于星期日\19點(diǎn)3、連續(xù)屬性的劃分1.使用二元劃分2.劃分點(diǎn)v選擇N個記錄中所有屬性值作為劃分點(diǎn)3.對每個劃分進(jìn)行類計(jì)數(shù),A<v和Av4.計(jì)算每個候選點(diǎn)v的Gini指標(biāo)，并從中選擇具有最小值的候選劃分點(diǎn)5.時(shí)間復(fù)雜度為O(n2)當(dāng)前第30頁\共有59頁\編于星期日\19點(diǎn)降低計(jì)算復(fù)雜性的方法:1.將記錄進(jìn)行排序2.從兩個相鄰的排過序的屬性值之間選擇中間值作為劃分點(diǎn)3.計(jì)算每個候選點(diǎn)的Gini值4.時(shí)間復(fù)雜度為O（NlogN）當(dāng)前第31頁\共有59頁\編于星期日\19點(diǎn)4、增益率熵和Gini指標(biāo)等不純性度量趨向有利于具有大量不同值的屬性。性別男女車型家用運(yùn)動豪華C0:6C1:4C0:4C1:6C0:1C1:3C0:8C1:0C0:1C1:7（b）（a）測試條件“車型”要比測試條件“性別”要好，因?yàn)樗a(chǎn)生了更純的派生結(jié)點(diǎn)。測試條件“顧客ID”相比前兩個產(chǎn)生更純的劃分，但是它卻不是一個有預(yù)測性的屬性，因?yàn)榕c每個劃分相關(guān)聯(lián)的記錄太少，以致不能作出可靠的預(yù)測。C0:1C1:0C0:1C1:0C0:0C1:1C0:0C1:1顧客IDv1v10v20v11（c）……當(dāng)前第32頁\共有59頁\編于星期日\19點(diǎn)如何解決？第一種策略：限制測試條件只能是二元劃分。第二種策略：修改評估劃分的標(biāo)準(zhǔn)，把屬性測試條件產(chǎn)生的輸出數(shù)也考慮進(jìn)去。例如：CART就是采用這樣的策略。例如：決策樹算法C4.5采用增益率（gainratio）的劃分標(biāo)準(zhǔn)來評估劃分。當(dāng)前第33頁\共有59頁\編于星期日\19點(diǎn)決策樹歸納特點(diǎn)的總結(jié)1、決策樹歸納是一種構(gòu)建分類模型的非參數(shù)方法。2、找到最佳的決策樹是NP完全問題。3、已開發(fā)的構(gòu)建決策樹技術(shù)不需要昂貴的計(jì)算代價(jià)，即使訓(xùn)練集非常大，也可以快速建立模型。4、決策樹相對容易解釋，特別是小型的決策樹。5、決策樹是學(xué)習(xí)離散值函數(shù)的典型代表。6、決策樹算法對于噪聲的干擾具有相當(dāng)好的魯棒性。7、冗余屬性不會對決策樹的準(zhǔn)確率造成不利的影響。8、由于大多數(shù)決策樹算法都采用自頂向下的遞歸劃分方法，因此沿著樹向下，記錄會越來越少。當(dāng)前第34頁\共有59頁\編于星期日\19點(diǎn)9、子樹可能在決策樹中重復(fù)多次，這使得決策樹過于復(fù)雜，并且可能更難解釋。10、目前為止，本章介紹的測試條件每次都只涉及一個屬性。二維數(shù)據(jù)集的決策樹及其邊界示例當(dāng)前第35頁\共有59頁\編于星期日\19點(diǎn)使用僅涉及單個屬性的測試條件不能有效劃分的數(shù)據(jù)集的例子斜決策樹（obliquedecisiontree）可以克服以上的局限，因?yàn)樗试S測試條件涉及多個屬性。上圖中的數(shù)據(jù)集可以很容易地用斜決策樹表示，該決策樹只有一個結(jié)點(diǎn)，其測試條件為：缺點(diǎn)：盡管這種技術(shù)有更強(qiáng)的表達(dá)能力，并且能夠產(chǎn)生更緊湊的決策樹，但是為給定的結(jié)點(diǎn)找出最佳測試條件的計(jì)算可能是相當(dāng)復(fù)雜的。x+y<1Class=+

Class=當(dāng)前第36頁\共有59頁\編于星期日\19點(diǎn)構(gòu)造歸納（constructiveinduction）提供另一種將數(shù)據(jù)劃分成齊次非矩形區(qū)域的方法，該方法創(chuàng)建復(fù)合屬性，代表已有屬性的算術(shù)或邏輯組合。新屬性提供了更好的類區(qū)分能力，并在決策樹歸納之前就增廣到數(shù)據(jù)集中。

與決策樹不同，構(gòu)造歸納不需要昂貴的花費(fèi)，因?yàn)樵跇?gòu)造決策樹之前，它只需要一次性地確定屬性的所有相關(guān)組合，相比之下，在擴(kuò)展每個內(nèi)部結(jié)點(diǎn)時(shí)，斜決策樹都需要動態(tài)地確定正確的屬性組合。然而構(gòu)造歸納會產(chǎn)生冗余的屬性，因?yàn)樾聞?chuàng)建的屬性是已有屬性的組合。11、研究表明不純性度量方法的選擇對決策樹算法的性能影響很小。當(dāng)前第37頁\共有59頁\編于星期日\19點(diǎn)一個好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。四、模型的過分?jǐn)M合當(dāng)前第38頁\共有59頁\編于星期日\19點(diǎn)二維數(shù)據(jù)過分?jǐn)M合的例子下圖所示的二維數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)屬于兩個類，分別標(biāo)記為類“o”和類“+”，類“o”的數(shù)據(jù)點(diǎn)由三個高斯分布混合產(chǎn)生，而類“+”的數(shù)據(jù)點(diǎn)用一個均勻分布產(chǎn)生。數(shù)據(jù)集中，總共有1200個數(shù)據(jù)點(diǎn)是屬于類“o”，1800個數(shù)據(jù)點(diǎn)屬于類“+”，其中30%的點(diǎn)用于訓(xùn)練，剩下的70%用于檢驗(yàn)。對訓(xùn)練集使用以Gini指標(biāo)作為不純性度量的決策樹方法。具有兩個類的數(shù)據(jù)集的例子當(dāng)前第39頁\共有59頁\編于星期日\19點(diǎn)當(dāng)決策樹很小時(shí)，訓(xùn)練誤差和檢驗(yàn)誤差都很大，這種情況稱作模型擬合不足（modelunderfitting）。出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實(shí)結(jié)構(gòu)，因此，模型在訓(xùn)練集和檢驗(yàn)集上的性能都很差。一旦樹的規(guī)模變得太大，即使訓(xùn)練誤差還在降低，但是檢驗(yàn)誤差開始增大，這種現(xiàn)象稱為模型過分?jǐn)M合（modeloverfitting）。訓(xùn)練誤差和檢驗(yàn)誤差當(dāng)前第40頁\共有59頁\編于星期日\19點(diǎn)

為理解過分?jǐn)M合現(xiàn)象，舉個例子：可以擴(kuò)展樹的葉結(jié)點(diǎn)，直到它完全擬合訓(xùn)練數(shù)據(jù)。雖然這樣一顆復(fù)雜的樹的訓(xùn)練誤差為0，但是檢驗(yàn)誤差可能很大，因?yàn)樵摌淇赡馨@樣的結(jié)點(diǎn)，它們偶然地?cái)M合訓(xùn)練數(shù)據(jù)中某些噪聲。這些結(jié)點(diǎn)降低了決策樹的性能，因?yàn)樗麄儾荒芎芎玫姆夯綑z驗(yàn)樣本。（a）包含11個葉結(jié)點(diǎn)的決策樹（b）包含24個葉結(jié)點(diǎn)的決策樹過分?jǐn)M合與擬合不足是兩種與模型復(fù)雜度有關(guān)的異?，F(xiàn)象。當(dāng)前第41頁\共有59頁\編于星期日\19點(diǎn)名稱體溫胎生4條腿冬眠類標(biāo)號豪豬恒溫是是是是貓恒溫是是否是蝙蝠恒溫是否是否*鯨恒溫是否否否*蠑螈冷血否是是否科莫多巨蜥冷血否是否否蟒蛇冷血否否是否鮭魚冷血否否否否鷹恒溫否否否否虹鳉冷血是否否否哺乳動物分類的訓(xùn)練數(shù)據(jù)集樣本。（“*”為錯誤標(biāo)記記錄）十個訓(xùn)練記錄中有兩個被錯誤標(biāo)記：蝙蝠和鯨被錯誤標(biāo)記為非哺乳動物，而不是哺乳動物。噪聲導(dǎo)致的過分?jǐn)M合當(dāng)前第42頁\共有59頁\編于星期日\19點(diǎn)名稱體溫胎生4條腿冬眠類標(biāo)號人恒溫是否否是鴿子恒溫否否否否象恒溫是是否是豹紋鯊冷血是否否否海龜冷血否是否否企鵝冷血否否否否鰻冷血否否否否海豚恒溫是否否是針鼴恒溫否是是是希拉毒蜥冷血否是是否哺乳動物分類的檢驗(yàn)數(shù)據(jù)集樣本。當(dāng)前第43頁\共有59頁\編于星期日\19點(diǎn)完全擬合訓(xùn)練數(shù)據(jù)的決策樹顯示在下圖（a）中，雖然該樹的訓(xùn)練誤差為0，但是它在檢驗(yàn)數(shù)據(jù)集上的誤差高達(dá)30%。體溫恒溫冷血胎生4條腿哺乳類動物非哺乳類動物非哺乳類動物非哺乳類動物是否是否體溫恒溫冷血胎生非哺乳類動物非哺乳類動物是否哺乳類動物（a）模型M1（b）模型M2圖（b）中決策樹M2盡管訓(xùn)練誤差較高（20%），但是它具有較低的檢驗(yàn)誤差。當(dāng)前第44頁\共有59頁\編于星期日\19點(diǎn)缺乏代表性樣本導(dǎo)致的過分?jǐn)M合名稱體溫胎生4條腿冬眠類標(biāo)號蠑螈冷血否是是否虹鳉冷血是否否否鷹恒溫否否否否弱夜鷹恒溫否否是否鴨嘴獸恒溫否是是是體溫恒溫冷血冬眠4條腿哺乳類動物非哺乳類動物非哺乳類動物非哺乳類動物是否是否人、大象和海豚都被誤分類，因?yàn)闆Q策樹把恒溫但不冬眠的脊柱動物劃分為非哺乳動物。決策樹做出這樣的分類決策是因?yàn)橹挥幸粋€訓(xùn)練記錄（鷹）具有這些特性。當(dāng)前第45頁\共有59頁\編于星期日\19點(diǎn)過分?jǐn)M合與多重比較過程1、在決策樹增長過程中，可以進(jìn)行多種測試，以確定哪個屬性能夠最好的劃分訓(xùn)練數(shù)據(jù)。2、在這種情況下，算法實(shí)際上是使用多重比較過程來決定是否需要擴(kuò)展決策樹。3、當(dāng)候選屬性多，訓(xùn)練記錄數(shù)少時(shí)，這種影響就變得更加明顯。多重比較過程與模型過分?jǐn)M合有什么關(guān)系？當(dāng)前第46頁\共有59頁\編于星期日\19點(diǎn)1、過分?jǐn)M合的主要原因一直是個爭辯的話題，但大家還是普遍同意模型的復(fù)雜度對模型的過分?jǐn)M合有影響。2、如何確定正確的模型復(fù)雜度？理想的復(fù)雜度是能產(chǎn)生最低泛化誤差的模型的復(fù)雜度。3、估計(jì)泛化誤差的方法使用再代入估計(jì)。用訓(xùn)練誤差提供對泛化誤差的樂觀估計(jì)結(jié)合模型復(fù)雜度估計(jì)統(tǒng)計(jì)上界使用確定集泛化誤差估計(jì)當(dāng)前第47頁\共有59頁\編于星期日\19點(diǎn)泛化誤差估計(jì)1、使用再代入估計(jì)再代入估計(jì)方法假設(shè)訓(xùn)練數(shù)據(jù)集可以很好地代表整體數(shù)據(jù)，因而，可以使用訓(xùn)練誤差（又稱再代入誤差）提供泛化誤差的樂觀估計(jì)。但是訓(xùn)練誤差通常是泛化誤差的一種很差的估計(jì)?？紤]下圖中的二叉決策樹。假設(shè)兩顆決策樹都由相同的訓(xùn)練數(shù)據(jù)產(chǎn)生，并且都根據(jù)每個葉結(jié)點(diǎn)多數(shù)類做出劃分。注意，左邊的樹T1復(fù)雜一些，它擴(kuò)展了右邊決策樹T2的某些結(jié)點(diǎn)。左決策樹的訓(xùn)練誤差是，而右決策樹的訓(xùn)練誤差是。根據(jù)再代入估計(jì)，左決策樹要優(yōu)于右決策樹。+：3-：0+：3-：1+：1-：2+：0-：2+：2-：1+：3-：1+：0-：5+：3-：6+：3-：0+：1-：4+：5-：2決策樹T1決策樹T2當(dāng)前第48頁\共有59頁\編于星期日\19點(diǎn)2、結(jié)合模型復(fù)雜度如之前所述，模型越是復(fù)雜，出現(xiàn)過分?jǐn)M合的幾率就越高，因此，我們更喜歡采用較為簡單的模型。這種策略與應(yīng)用眾所周知的奧卡姆剃刀一致。奧卡姆剃刀：給定兩個具有相同泛化誤差的模型，較簡單的模型比較復(fù)雜的模型更可取。悲觀誤差評估：使用訓(xùn)練誤差與模型復(fù)雜度罰項(xiàng)（penaltyterm）的和計(jì)算泛化誤差。結(jié)果泛化誤差可以看作模型的悲觀誤差估計(jì)。設(shè)n(t)是結(jié)點(diǎn)t分類的訓(xùn)練記錄數(shù)，e(t)是被誤分類的記錄數(shù)。決策樹T的悲觀誤差估計(jì)可以用下式計(jì)算：其中，k是決策樹的葉結(jié)點(diǎn)數(shù)，e(T)是決策樹的總訓(xùn)練誤差，是訓(xùn)練記錄數(shù)，是每個結(jié)點(diǎn)對應(yīng)的罰項(xiàng)。當(dāng)前第49頁\共有59頁\編于星期日\19點(diǎn)+：3-：0+：3-：1+：1-：2+：0-：2+：2-：1+：3-：1+：0-：5+：3-：6+：3-：0+：1-：4+：5-：2決策樹T1決策樹T2考慮上圖的二叉決策樹。如果罰項(xiàng)等于0.5，左邊的決策樹的悲觀誤差估計(jì)為：右邊的決策樹的悲觀誤差估計(jì)為：此時(shí)，左邊的決策樹比右邊的決策樹具有更好的悲觀誤差估計(jì)。當(dāng)前第50頁\共有59頁\編于星期日\19點(diǎn)最小描述長度原則（minimumdescriptionlength,MDL）標(biāo)記的未標(biāo)記的當(dāng)前第51頁\共有59頁\編于星期日\19點(diǎn)Cost是傳輸總代價(jià)。目標(biāo)：最小化Cost值。其中Cost(Data|Model)是誤分類記錄編碼的開銷。Cost(Model)是模型編碼的開銷。另一種可能是，A決定建立一個分類模型，概括X和y點(diǎn)之間的關(guān)系。Cost(Model,Data)=Cost(Data|Model)+Cost(Model)3、估計(jì)統(tǒng)計(jì)上界泛化誤差也可以用訓(xùn)練誤差的統(tǒng)計(jì)修正來估計(jì)。因?yàn)榉夯`差傾向于比訓(xùn)練誤差大，所以統(tǒng)計(jì)修正通常是計(jì)算訓(xùn)練誤差的上界。4、使用確認(rèn)集在該方法中，不是用訓(xùn)練集估計(jì)泛化誤差，而是把原始的訓(xùn)練數(shù)據(jù)集分為兩個較小的子集，一個子集用于訓(xùn)練，而另一個稱為確認(rèn)集，用于估計(jì)泛化誤差。當(dāng)前第52頁\共有59頁\編于星期日\19點(diǎn)2/3訓(xùn)練集建立模型誤差估計(jì)1/3訓(xùn)練集該方法通常用于通過參數(shù)控制獲得具有不同復(fù)雜度模型的分類技術(shù)。通過調(diào)整學(xué)習(xí)算法中的參數(shù)，直到學(xué)習(xí)算法產(chǎn)生的模型在確認(rèn)集上達(dá)到最低的錯誤率，可以估計(jì)最佳模型的復(fù)雜度。當(dāng)前第53頁\共有59頁\編于星期日\19點(diǎn)處理決策樹歸納中的過分?jǐn)M合先剪枝(提前終止規(guī)則)樹增長算法在產(chǎn)生完全擬合整個訓(xùn)練數(shù)據(jù)集的之前就停止決策樹的生長為了做到這一點(diǎn)，需要采用更具限制性的結(jié)束條件: