分類基本概念決策樹(shù)與模型評(píng)估演示文稿

分類基本概念決策樹(shù)與模型評(píng)估演示文稿第一頁(yè)，共五十九頁(yè)。優(yōu)選分類基本概念決策樹(shù)與模型評(píng)估第二頁(yè)，共五十九頁(yè)。分類任務(wù)的輸入數(shù)據(jù)是記錄的集合。每條記錄也稱實(shí)例或者樣例，用元組（x,y）表示，其中x是屬性的集合，而y是一個(gè)特殊的屬性，指出樣例的類標(biāo)號(hào)（也成為分類屬性或目標(biāo)屬性）。分類？回歸？第三頁(yè)，共五十九頁(yè)。分類（classification）

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

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

分類模型還可以用于預(yù)測(cè)未知記錄的類標(biāo)號(hào)。名字體溫表皮覆蓋胎生水生動(dòng)物飛行動(dòng)物有腿冬眠類標(biāo)號(hào)毒蜥冷血鱗片否否否是是？第四頁(yè)，共五十九頁(yè)。輸入屬性集（x）

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

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

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

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

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

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

Class=第三十六頁(yè)，共五十九頁(yè)。構(gòu)造歸納（constructiveinduction）提供另一種將數(shù)據(jù)劃分成齊次非矩形區(qū)域的方法，該方法創(chuàng)建復(fù)合屬性，代表已有屬性的算術(shù)或邏輯組合。新屬性提供了更好的類區(qū)分能力，并在決策樹(shù)歸納之前就增廣到數(shù)據(jù)集中。

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

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