第4章分類基本概念、決策樹與模型評估課件

第4章分類基本概念、決策樹與模型評估2022/11/23第4章分類基本概念、決策樹與模型評估第4章分類基本概念、決策樹與模型評估2022/11/22第41分類任務(wù)：確定對象屬于哪個預(yù)定義的目標類例子：1、根據(jù)電子郵件的標題和內(nèi)容檢查出垃圾郵件。2、根據(jù)星系的形狀對它們分類。螺旋狀的星系橢圓狀的星系一、預(yù)備知識第4章分類基本概念、決策樹與模型評估分類任務(wù)：確定對象屬于哪個預(yù)定義的目標類例子：螺旋狀的星系橢2分類任務(wù)的輸入數(shù)據(jù)是記錄的集合。每條記錄也稱實例或者樣例，用元組（x,y）表示，其中x是屬性的集合，而y是一個特殊的屬性，指出樣例的類標號（也成為分類屬性或目標屬性）。分類？回歸？第4章分類基本概念、決策樹與模型評估分類任務(wù)的輸入數(shù)據(jù)是記錄的集合。每條記錄也稱實例或者樣例，用3分類（classification）通過學(xué)習(xí)得到一個目標函數(shù)（targetfunction），也成為分類模型（classificationmodel），把每個屬性集x映射到一個預(yù)先定義的類標號y。目的：1、描述性建模分類模型可以作為解釋性的工具，用于區(qū)分不同類中的對象。2、預(yù)測性建模分類模型還可以用于預(yù)測未知記錄的類標號。名字體溫表皮覆蓋胎生水生動物飛行動物有腿冬眠類標號毒蜥冷血鱗片否否否是是？第4章分類基本概念、決策樹與模型評估分類（classification）通過學(xué)習(xí)4輸入屬性集（x）分類模型輸出類標號（y）分類器的任務(wù)：根據(jù)輸入屬性集x確定類標號y分類技術(shù)非常適合預(yù)測或描述二元或標稱類型的數(shù)據(jù)集，對序數(shù)分類不太有效，因為分類技術(shù)不考慮隱含在目標類中的序關(guān)系。第4章分類基本概念、決策樹與模型評估輸入屬性集（x）輸出類標號（y）分類器的任務(wù)：根據(jù)輸入屬性集5分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。分類技術(shù)決策樹分類法基于規(guī)則的分類法神經(jīng)網(wǎng)絡(luò)支持向量機這些技術(shù)都使用一種學(xué)習(xí)算法確定分類模型，修改這個模型能夠很好地擬合輸入數(shù)據(jù)中類標號和屬性集之間的聯(lián)系。學(xué)習(xí)算法得到的模型不僅要很好地擬合輸入數(shù)據(jù)，還要能夠正確地預(yù)測未知樣本的類標號。訓(xùn)練算法的目標：建立具有很好的泛化能力的模型。二、解決分類問題的一般方法樸素貝葉斯分類法第4章分類基本概念、決策樹與模型評估分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。分類技術(shù)6訓(xùn)練集：由類標號已知的記錄構(gòu)成檢驗集：由類標號未知的記錄構(gòu)成第4章分類基本概念、決策樹與模型評估訓(xùn)練集：由類標號已知的記錄構(gòu)成第4章分類基本概念、決策樹與模7預(yù)測的類類=1類=0實際的類類=1類=0二類問題的混淆矩陣表中每個表項表示實際類標號為但是被預(yù)測為類的記錄數(shù)。被分類模型正確預(yù)測的樣本總數(shù)是，而被錯誤預(yù)測的樣本總數(shù)是。雖然混淆矩陣提供衡量分類模型的信息，但是用一個數(shù)匯總這些信息更便于比較不同模型的性能。為實現(xiàn)這一目的，可以使用性能度量（performancemetric），如準確率（accuracy），其定義如下：第4章分類基本概念、決策樹與模型評估預(yù)測的類類=1類=0實際的類類=1類=0二類問題的混淆矩陣表8同樣，分類模型的性能也可以用錯誤率（errorrate）來表示，其定義如下：目標：尋求最高的準確率或者最低的錯誤率第4章分類基本概念、決策樹與模型評估同樣，分類模型的性能也可以用錯誤率（errorrate）來91、什么是決策樹？類似于流程圖的樹結(jié)構(gòu)每個內(nèi)部節(jié)點表示在一個屬性上的測試每個分枝代表一個測試輸出每個葉節(jié)點代表類或類分布三、決策樹（decisiontree）歸納3、決策樹的使用：對未知樣本進行分類通過將樣本的屬性值與決策樹相比較2、決策樹的生成由兩個階段組成決策樹構(gòu)建開始時，所有的訓(xùn)練樣本都在根節(jié)點遞歸通過選定的屬性，來劃分樣本（必須是離散值）樹剪枝許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點，樹剪枝試圖檢測和剪去這種分枝第4章分類基本概念、決策樹與模型評估1、什么是決策樹？三、決策樹（decisiontree）歸10根結(jié)點（rootnode）：它沒有入邊，但是有零條或多條出邊。內(nèi)部結(jié)點（internalnode）：恰好有一條入邊和兩條或多條出邊。葉節(jié)點（leafnode）或終結(jié)點（terminalnode）：恰好有一條入邊，但沒有出邊。葉結(jié)點根結(jié)點內(nèi)部結(jié)點體溫胎生非哺乳動物哺乳動物非哺乳動物恒溫否冷血是第4章分類基本概念、決策樹與模型評估根結(jié)點（rootnode）：它沒有入邊，但是有零條或多條出11一旦構(gòu)造了決策樹，對檢驗記錄進行分類就很容易。從樹的根結(jié)點開始，將測試條件用于檢驗記錄，根據(jù)測試結(jié)果選擇適當(dāng)?shù)姆种АＱ刂摲种Щ蛘叩竭_另一個內(nèi)部結(jié)點，使用新的測試條件，或者到達一個葉結(jié)點。到達葉結(jié)點之后，葉結(jié)點的類標號就被賦值給該檢驗記錄。名字體溫胎生……類標號火烈鳥恒溫否……？體溫胎生非哺乳動物哺乳動物非哺乳動物恒溫否冷血是第4章分類基本概念、決策樹與模型評估一旦構(gòu)造了決策樹，對檢驗記錄進行分類就很容易12如何建立決策樹對于給定的屬性集，可以構(gòu)造的決策樹的數(shù)目達指數(shù)級。盡管某些決策樹比其他決策樹更準確，但是由于搜索空間是指數(shù)規(guī)模的，找出最佳決策樹在計算上是不可行的。盡管如此，人們還是開發(fā)了一些有效的算法，能夠在合理的時間內(nèi)構(gòu)造出具有一定準確率的次最優(yōu)決策樹。這些算法通常都采用貪心策略。有許多決策樹算法:Hunt算法信息增益——Informationgain（ID3）增益比率——Gainration（C4.5）基尼指數(shù)——Giniindex

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

Class=第4章分類基本概念、決策樹與模型評估使用僅涉及單個屬性的測試條件不能有效劃分的數(shù)據(jù)集的例子斜決策36構(gòu)造歸納（constructiveinduction）提供另一種將數(shù)據(jù)劃分成齊次非矩形區(qū)域的方法，該方法創(chuàng)建復(fù)合屬性，代表已有屬性的算術(shù)或邏輯組合。新屬性提供了更好的類區(qū)分能力，并在決策樹歸納之前就增廣到數(shù)據(jù)集中。與決策樹不同，構(gòu)造歸納不需要昂貴的花費，因為在構(gòu)造決策樹之前，它只需要一次性地確定屬性的所有相關(guān)組合，相比之下，在擴展每個內(nèi)部結(jié)點時，斜決策樹都需要動態(tài)地確定正確的屬性組合。然而構(gòu)造歸納會產(chǎn)生冗余的屬性，因為新創(chuàng)建的屬性是已有屬性的組合。11、研究表明不純性度量方法的選擇對決策樹算法的性能影響很小。第4章分類基本概念、決策樹與模型評估構(gòu)造歸納（constructiveinduction）37一個好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。四、模型的過分擬合第4章分類基本概念、決策樹與模型評估一個好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。四、模型的過38二維數(shù)據(jù)過分擬合的例子下圖所示的二維數(shù)據(jù)集中的數(shù)據(jù)點屬于兩個類，分別標記為類“o”和類“+”，類“o”的數(shù)據(jù)點由三個高斯分布混合產(chǎn)生，而類“+”的數(shù)據(jù)點用一個均勻分布產(chǎn)生。數(shù)據(jù)集中，總共有1200個數(shù)據(jù)點是屬于類“o”，1800個數(shù)據(jù)點屬于類“+”，其中30%的點用于訓(xùn)練，剩下的70%用于檢驗。對訓(xùn)練集使用以Gini指標作為不純性度量的決策樹方法。具有兩個類的數(shù)據(jù)集的例子第4章分類基本概念、決策樹與模型評估二維數(shù)據(jù)過分擬合的例子下圖所示的二維數(shù)據(jù)集中的數(shù)據(jù)點屬于兩個39當(dāng)決策樹很小時，訓(xùn)練誤差和檢驗誤差都很大，這種情況稱作模型擬合不足（modelunderfitting）。出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實結(jié)構(gòu)，因此，模型在訓(xùn)練集和檢驗集上的性能都很差。一旦樹的規(guī)模變得太大，即使訓(xùn)練誤差還在降低，但是檢驗誤差開始增大，這種現(xiàn)象稱為模型過分擬合（modeloverfitting）。訓(xùn)練誤差和檢驗誤差第4章分類基本概念、決策樹與模型評估當(dāng)決策樹很小時，訓(xùn)練誤差和檢驗誤差都很大，這種40為理解過分擬合現(xiàn)象，舉個例子：可以擴展樹的葉結(jié)點，直到它完全擬合訓(xùn)練數(shù)據(jù)。雖然這樣一顆復(fù)雜的樹的訓(xùn)練誤差為0，但是檢驗誤差可能很大，因為該樹可能包含這樣的結(jié)點，它們偶然地擬合訓(xùn)練數(shù)據(jù)中某些噪聲。這些結(jié)點降低了決策樹的性能，因為他們不能很好的泛化到檢驗樣本。（a）包含11個葉結(jié)點的決策樹（b）包含24個葉結(jié)點的決策樹過分擬合與擬合不足是兩種與模型復(fù)雜度有關(guān)的異?，F(xiàn)象。第4章分類基本概念、決策樹與模型評估為理解過分擬合現(xiàn)象，舉個例子：可以擴展樹的葉結(jié)41名稱體溫胎生4條腿冬眠類標號豪豬恒溫是是是是貓恒溫是是否是蝙蝠恒溫是否是否*鯨恒溫是否否否*蠑螈冷血否是是否科莫多巨蜥冷血否是否否蟒蛇冷血否否是否鮭魚冷血否否否否鷹恒溫否否否否虹鳉冷血是否否否哺乳動物分類的訓(xùn)練數(shù)據(jù)集樣本。（“*”為錯誤標記記錄）十個訓(xùn)練記錄中有兩個被錯誤標記：蝙蝠和鯨被錯誤標記為非哺乳動物，而不是哺乳動物。噪聲導(dǎo)致的過分擬合第4章分類基本概念、決策樹與模型評估名稱體溫胎生4條腿冬眠類標號豪豬恒溫是是是是貓恒溫是是否是蝙42名稱體溫胎生4條腿冬眠類標號人恒溫是否否是鴿子恒溫否否否否象恒溫是是否是豹紋鯊冷血是否否否海龜冷血否是否否企鵝冷血否否否否鰻冷血否否否否海豚恒溫是否否是針鼴恒溫否是是是希拉毒蜥冷血否是是否哺乳動物分類的檢驗數(shù)據(jù)集樣本。第4章分類基本概念、決策樹與模型評估名稱體溫胎生4條腿冬眠類標號人恒溫是否否是鴿子恒溫否否否否象43完全擬合訓(xùn)練數(shù)據(jù)的決策樹顯示在下圖（a）中，雖然該樹的訓(xùn)練誤差為0，但是它在檢驗數(shù)據(jù)集上的誤差高達30%。體溫恒溫冷血胎生4條腿哺乳類動物非哺乳類動物非哺乳類動物非哺乳類動物是否是否體溫恒溫冷血胎生非哺乳類動物非哺乳類動物是否哺乳類動物（a）模型M1（b）模型M2圖（b）中決策樹M2盡管訓(xùn)練誤差較高（20%），但是它具有較低的檢驗誤差。第4章分類基本概念、決策樹與模型評估完全擬合訓(xùn)練數(shù)據(jù)的決策樹顯示在下圖（a）中，雖然該樹的訓(xùn)練誤44缺乏代表性樣本導(dǎo)致的過分擬合名稱體溫胎生4條腿冬眠類標號蠑螈冷血否是是否虹鳉冷血是否否否鷹恒溫否否否否弱夜鷹恒溫否否是否鴨嘴獸恒溫否是是是體溫恒溫冷血冬眠4條腿哺乳類動物非哺乳類動物非哺乳類動物非哺乳類動物是否是否人、大象和海豚都被誤分類，因為決策樹把恒溫但不冬眠的脊柱動物劃分為非哺乳動物。決策樹做出這樣的分類決策是因為只有一個訓(xùn)練記錄（鷹）具有這些特性。第4章分類基本概念、決策樹與模型評估缺乏代表性樣本導(dǎo)致的過分擬合名稱體溫胎生4條腿冬眠類標號蠑螈45過分擬合與多重比較過程1、在決策樹增長過程中，可以進行多種測試，以確定哪個屬性能夠最好的劃分訓(xùn)練數(shù)據(jù)。2、在這種情況下，算法實際上是使用多重比較過程來決定是否需要擴展決策樹。3、當(dāng)候選屬性多，訓(xùn)練記錄數(shù)少時，這種影響就變得更加明顯。多重比較過程與模型過分擬合有什么關(guān)系？第4章分類基本概念、決策樹與模型評估過分擬合與多重比較過程1、在決策樹增長過程中，可以進行多種測461、過分擬合的主要原因一直是個爭辯的話題，但大家還是普遍同意模型的復(fù)雜度對模型的過分擬合有影響。2、如何確定正確的模型復(fù)雜度？理想的復(fù)雜度是能產(chǎn)生最低泛化誤差的模型的復(fù)雜度。3、估計泛化誤差的方法使用再代入估計。用訓(xùn)練誤差提供對泛化誤差的樂觀估計結(jié)合模型復(fù)雜度估計統(tǒng)計上界使用確定集泛化誤差估計第4章分類基本概念、決策樹與模型評估1、過分擬合的主要原因一直是個爭辯的話題，但大家還是普遍同意47泛化誤差估計1、使用再代入估計再代入估計方法假設(shè)訓(xùn)練數(shù)據(jù)集可以很好地代表整體數(shù)據(jù)，因而，可以使用訓(xùn)練誤差（又稱再代入誤差）提供泛化誤差的樂觀估計。但是訓(xùn)練誤差通常是泛化誤差的一種很差的估計?？紤]下圖中的二叉決策樹。假設(shè)兩顆決策樹都由相同的訓(xùn)練數(shù)據(jù)產(chǎn)生，并且都根據(jù)每個葉結(jié)點多數(shù)類做出劃分。注意，左邊的樹T1復(fù)雜一些，它擴展了右邊決策樹T2的某些結(jié)點。左決策樹的訓(xùn)練誤差是，而右決策樹的訓(xùn)練誤差是。根據(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第4章分類基本概念、決策樹與模型評估泛化誤差估計1、使用再代入估計再代入估計方法假設(shè)訓(xùn)練數(shù)據(jù)集可482、結(jié)合模型復(fù)雜度如之前所述，模型越是復(fù)雜，出現(xiàn)過分擬合的幾率就越高，因此，我們更喜歡采用較為簡單的模型。這種策略與應(yīng)用眾所周知的奧卡姆剃刀一致。奧卡姆剃刀：給定兩個具有相同泛化誤差的模型，較簡單的模型比較復(fù)雜的模型更可取。悲觀誤差評估：使用訓(xùn)練誤差與模型復(fù)雜度罰項（penaltyterm）的和計算泛化誤差。結(jié)果泛化誤差可以看作模型的悲觀誤差估計。設(shè)n(t)是結(jié)點t分類的訓(xùn)練記錄數(shù)，e(t)是被誤分類的記錄數(shù)。決策樹T的悲觀誤差估計可以用下式計算：其中，k是決策樹的葉結(jié)點數(shù)，e(T)是決策樹的總訓(xùn)練誤差，是訓(xùn)練記錄數(shù)，是每個結(jié)點對應(yīng)的罰項。第4章分類基本概念、決策樹與模型評估2、結(jié)合模型復(fù)雜度如之前所述，模型越是復(fù)雜，出現(xiàn)過分擬合的幾49+：3-：0+：3-：1+：1-：2+：0-：2+：2-：1+：3-：1+：0-：5+：3-：6+：3-：0+：1-：4+：5-：2決策樹T1決策樹T2考慮上圖的二叉決策樹。如果罰項等于0.5，左邊的決策樹的悲觀誤差估計為：右邊的決策樹的悲觀誤差估計為：此時，左邊的決策樹比右邊的決策樹具有更好的悲觀誤差估計。第4章分類基本概念、決策樹與模型評估+：3+：3+：1+：0+：2+：3+：0+：3+：3+：150最小描述長度原則（minimumdescriptionlength,MDL）標記的未標記的第4章分類基本概念、決策樹與模型評估最小描述長度原則（minimumdescriptionl51Cost是傳輸總代價。目標：最小化Cost值。其中Cost(Data|Model)是誤分類記錄編碼的開銷。Cost(Model)是模型編碼的開銷。另一種可能是，A決定建立一個分類模型，概括X和y點之間的關(guān)系。Cost(Model,Data)=Cost(Data|Model)+Cost(Model)3、估計統(tǒng)計上界泛化誤差也可以用訓(xùn)練誤差的統(tǒng)計修正來估計。因為泛化誤差傾向于比訓(xùn)練誤差大，所以統(tǒng)計修正通常是計算訓(xùn)練誤差的上界。4、使用確認集在該方法中，不是用訓(xùn)練集估計泛化誤差，而是把原始的訓(xùn)練數(shù)據(jù)集分為兩個較小的子集，一個子集用于訓(xùn)練，而另一個稱為確認集，用于估計泛化誤差。第4章分類基本概念、決策樹與模型評估Cost是傳輸總代價。目標：最小化Cost值。另一種可能是522/3訓(xùn)練集建立模型誤差估計1/3訓(xùn)練集該方法通常用于通過參數(shù)控制獲得具有不同復(fù)雜度模型的分類技術(shù)。通過調(diào)整學(xué)習(xí)算法中的參數(shù)，直到學(xué)習(xí)算法產(chǎn)生的模型在確認集上達到最低的錯誤率，可以估計最佳模型的復(fù)雜度。第4章分類基本概念、決策樹與模型評估2/3訓(xùn)練集建立模型誤差估計1/3訓(xùn)練集該方法通常用于通過參53處理決策樹歸納中的過分擬合先剪枝(提前終止規(guī)則)樹增長算法在產(chǎn)生完全擬合整個訓(xùn)練數(shù)據(jù)集的之前就停止決策樹的生長為了做到這一點，需要采用更具限制性的結(jié)束條件:當(dāng)結(jié)點的記錄數(shù)少于一定閾值，則停止生長當(dāng)不純性度量的增益低于某個確定的閾值時，則停止生長(e.g.,informationgain).缺點：很難為提前終止選取正確的閾值:（1）閾值太高，導(dǎo)致擬合不足（2）閾值太低，導(dǎo)致不能充分解決過分擬合的問題。后剪枝在該方法中，初始決策樹按照最大規(guī)模生長，然后進行剪枝的步驟，按照自底向上的方式修剪完全增長的決策樹。修剪有兩種做法:（1）用新的葉結(jié)點替換子樹，該葉結(jié)點的類標號由子樹下記錄中的多數(shù)類定（2）用子樹中最常用的分支代替子樹第4章分類基本概念、決策樹與模型評估處理決策樹歸納中的過分擬合先剪枝(提前終止規(guī)則)后剪枝第454五、評估分類器的性能一、保持（Holdout）方法將被標記的原始數(shù)據(jù)劃分成兩個不相交的集合，分別成為訓(xùn)練集和檢驗集。在訓(xùn)練集上歸納分類模型，在檢驗集上評估模型的性能。局限性：1、用于訓(xùn)練的被標記樣本較少。2、模型可能高度依賴于訓(xùn)練集和檢驗集的構(gòu)成。第4章分類基本概念、決策樹與模型評估五、評估分類器的性能一、保持（Holdout）方法將被標記的55二、隨機二次抽樣（randomsubsampling）隨機二次抽樣可以多次重復(fù)保持方法來改進分類器性能的估計。由于它沒有控制每個記錄用于訓(xùn)練和檢驗的次數(shù)，因此，有些用于訓(xùn)練的記錄使用的頻率可能比其他記錄高得多。三、交叉驗證（cross-validation）在該方法中，每個記錄用于訓(xùn)練的次數(shù)相同，并且恰好檢驗一次。例：假設(shè)把數(shù)據(jù)分為相同大小的兩個子集，首先，我們選擇一個子集作訓(xùn)練集，而另一個作檢驗集，然后交換兩個集合的角色，原先作訓(xùn)練集的現(xiàn)在作檢驗集，反之亦然，這種方法叫做二折交叉驗證。第4章分類基本概念、決策樹與模型評估二、隨機二次抽樣（randomsubsampling）隨機56四、自助（bootstrap）法在自助法中，訓(xùn)練記錄采用有放回抽樣使得它等幾率地被重新抽取。如果原始數(shù)據(jù)有N個記錄，可以證明，平均來說，大小為N的自助樣本大約包含原始數(shù)據(jù)的63.2%的記錄。至少一個記錄被自助樣本抽取的概率它通過組合每個自助樣本的準確率和由包含所有標記樣本的訓(xùn)練集計算的準確率計算總準確率：第4章分類基本概念、決策樹與模型評估四、自助（bootstrap）法在自助法中，訓(xùn)練記錄采用有放57六、比較分類器的方法考慮一對分類模型ModelA和modelB，假設(shè)modelA在包含30個記錄的檢驗集上的準確率達到85%，而modelB在包含5000個記錄的不同檢驗集上達到75%的準確率。modelA好于modelB?估計準確度的置信區(qū)間是N次試驗觀察到的成功次數(shù)。檢驗集的記錄個數(shù)為N，準確率期望：方差：（拋硬幣試驗）第4章分類基本概念、決策樹與模型評估六、比較分類器的方法考慮一對分類模型ModelA和mode581－α第4章分類基本概念、決策樹與模型評估1－α第4章分類基本概念、決策樹與模型評估59比較兩個模型的性能考慮一對模型M1和M2，它們在兩個獨立的檢驗集D1和D2上進行評估，令n1是D1中的記錄數(shù)，n2是D2中的記錄數(shù)。另外，假設(shè)M1在D1上的錯誤率為e1，M2在D2上的錯誤率為e2。假設(shè)n1和n2都充分大，e1和e2可以使用正態(tài)分布來近似。如果用d=e1-e2表示錯誤率的觀察差，則d服從均值為（其實際差）、方差為的正態(tài)分布。D的方差為：其中和是錯誤率的方差。在置信水平下的置信區(qū)間為：第4章分類基本概念、決策樹與模型評估比較兩個模型的性能考慮一對模型M1和M2，它們在兩個獨立的檢60例：模型M1在N1=30個檢驗記錄上的錯誤率e1=0.15。M2在N2=5000個檢驗記錄上的錯誤率e2=0.25.錯誤率的觀察差d=|0.15-0.25|=0.1。使用雙側(cè)檢驗來檢查還是。錯誤率觀察差的估計方差計算如下：或結(jié)論：區(qū)間跨越0，可以斷言在95%的置信水平下，該觀察差不是統(tǒng)計顯著的。第4章分類基本概念、決策樹與模型評估例：模型M1在N1=30個檢驗記錄上的錯誤率e1=0.15。61比較兩種分類法的性能令表示分類技術(shù)在第j次迭代產(chǎn)生的模型，每對模型和在相同的劃分j上進行檢驗。用e1j和e2j分別表示它們的錯誤率，它們在第j折上的錯誤率之差可以記作。如果k充分大，則服從于均值為、方差為的正態(tài)分布。觀察差的總方差可以用下式進行估計：其中，是平均差。用t分布計算的置信區(qū)間為：第4章分類基本概念、決策樹與模型評估比較兩種分類法的性能令表示分類技術(shù)在第j62例：假設(shè)兩個分類技術(shù)產(chǎn)生的模型的準確率估計差的均值等于0.05，標準差等于0.002。如果使用30折交叉驗證方法估計準確率，則在95%置信水平下，真實準確率為：統(tǒng)計顯著查詢t分布表第4章分類基本概念、決策樹與模型評估例：假設(shè)兩個分類技術(shù)產(chǎn)生的模型的準確率估計差的均值等于0.063演講完畢，謝謝聽講!再見，seeyouagain3rew2022/11/23第4章分類基本概念、決策樹與模型評估演講完畢，謝謝聽講!再見，seeyouagain3rew64第4章分類基本概念、決策樹與模型評估2022/11/23第4章分類基本概念、決策樹與模型評估第4章分類基本概念、決策樹與模型評估2022/11/22第465分類任務(wù)：確定對象屬于哪個預(yù)定義的目標類例子：1、根據(jù)電子郵件的標題和內(nèi)容檢查出垃圾郵件。2、根據(jù)星系的形狀對它們分類。螺旋狀的星系橢圓狀的星系一、預(yù)備知識第4章分類基本概念、決策樹與模型評估分類任務(wù)：確定對象屬于哪個預(yù)定義的目標類例子：螺旋狀的星系橢66分類任務(wù)的輸入數(shù)據(jù)是記錄的集合。每條記錄也稱實例或者樣例，用元組（x,y）表示，其中x是屬性的集合，而y是一個特殊的屬性，指出樣例的類標號（也成為分類屬性或目標屬性）。分類？回歸？第4章分類基本概念、決策樹與模型評估分類任務(wù)的輸入數(shù)據(jù)是記錄的集合。每條記錄也稱實例或者樣例，用67分類（classification）通過學(xué)習(xí)得到一個目標函數(shù)（targetfunction），也成為分類模型（classificationmodel），把每個屬性集x映射到一個預(yù)先定義的類標號y。目的：1、描述性建模分類模型可以作為解釋性的工具，用于區(qū)分不同類中的對象。2、預(yù)測性建模分類模型還可以用于預(yù)測未知記錄的類標號。名字體溫表皮覆蓋胎生水生動物飛行動物有腿冬眠類標號毒蜥冷血鱗片否否否是是？第4章分類基本概念、決策樹與模型評估分類（classification）通過學(xué)習(xí)68輸入屬性集（x）分類模型輸出類標號（y）分類器的任務(wù)：根據(jù)輸入屬性集x確定類標號y分類技術(shù)非常適合預(yù)測或描述二元或標稱類型的數(shù)據(jù)集，對序數(shù)分類不太有效，因為分類技術(shù)不考慮隱含在目標類中的序關(guān)系。第4章分類基本概念、決策樹與模型評估輸入屬性集（x）輸出類標號（y）分類器的任務(wù)：根據(jù)輸入屬性集69分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。分類技術(shù)決策樹分類法基于規(guī)則的分類法神經(jīng)網(wǎng)絡(luò)支持向量機這些技術(shù)都使用一種學(xué)習(xí)算法確定分類模型，修改這個模型能夠很好地擬合輸入數(shù)據(jù)中類標號和屬性集之間的聯(lián)系。學(xué)習(xí)算法得到的模型不僅要很好地擬合輸入數(shù)據(jù)，還要能夠正確地預(yù)測未知樣本的類標號。訓(xùn)練算法的目標：建立具有很好的泛化能力的模型。二、解決分類問題的一般方法樸素貝葉斯分類法第4章分類基本概念、決策樹與模型評估分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。分類技術(shù)70訓(xùn)練集：由類標號已知的記錄構(gòu)成檢驗集：由類標號未知的記錄構(gòu)成第4章分類基本概念、決策樹與模型評估訓(xùn)練集：由類標號已知的記錄構(gòu)成第4章分類基本概念、決策樹與模71預(yù)測的類類=1類=0實際的類類=1類=0二類問題的混淆矩陣表中每個表項表示實際類標號為但是被預(yù)測為類的記錄數(shù)。被分類模型正確預(yù)測的樣本總數(shù)是，而被錯誤預(yù)測的樣本總數(shù)是。雖然混淆矩陣提供衡量分類模型的信息，但是用一個數(shù)匯總這些信息更便于比較不同模型的性能。為實現(xiàn)這一目的，可以使用性能度量（performancemetric），如準確率（accuracy），其定義如下：第4章分類基本概念、決策樹與模型評估預(yù)測的類類=1類=0實際的類類=1類=0二類問題的混淆矩陣表72同樣，分類模型的性能也可以用錯誤率（errorrate）來表示，其定義如下：目標：尋求最高的準確率或者最低的錯誤率第4章分類基本概念、決策樹與模型評估同樣，分類模型的性能也可以用錯誤率（errorrate）來731、什么是決策樹？類似于流程圖的樹結(jié)構(gòu)每個內(nèi)部節(jié)點表示在一個屬性上的測試每個分枝代表一個測試輸出每個葉節(jié)點代表類或類分布三、決策樹（decisiontree）歸納3、決策樹的使用：對未知樣本進行分類通過將樣本的屬性值與決策樹相比較2、決策樹的生成由兩個階段組成決策樹構(gòu)建開始時，所有的訓(xùn)練樣本都在根節(jié)點遞歸通過選定的屬性，來劃分樣本（必須是離散值）樹剪枝許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點，樹剪枝試圖檢測和剪去這種分枝第4章分類基本概念、決策樹與模型評估1、什么是決策樹？三、決策樹（decisiontree）歸74根結(jié)點（rootnode）：它沒有入邊，但是有零條或多條出邊。內(nèi)部結(jié)點（internalnode）：恰好有一條入邊和兩條或多條出邊。葉節(jié)點（leafnode）或終結(jié)點（terminalnode）：恰好有一條入邊，但沒有出邊。葉結(jié)點根結(jié)點內(nèi)部結(jié)點體溫胎生非哺乳動物哺乳動物非哺乳動物恒溫否冷血是第4章分類基本概念、決策樹與模型評估根結(jié)點（rootnode）：它沒有入邊，但是有零條或多條出75一旦構(gòu)造了決策樹，對檢驗記錄進行分類就很容易。從樹的根結(jié)點開始，將測試條件用于檢驗記錄，根據(jù)測試結(jié)果選擇適當(dāng)?shù)姆种?。沿著該分支或者到達另一個內(nèi)部結(jié)點，使用新的測試條件，或者到達一個葉結(jié)點。到達葉結(jié)點之后，葉結(jié)點的類標號就被賦值給該檢驗記錄。名字體溫胎生……類標號火烈鳥恒溫否……？體溫胎生非哺乳動物哺乳動物非哺乳動物恒溫否冷血是第4章分類基本概念、決策樹與模型評估一旦構(gòu)造了決策樹，對檢驗記錄進行分類就很容易76如何建立決策樹對于給定的屬性集，可以構(gòu)造的決策樹的數(shù)目達指數(shù)級。盡管某些決策樹比其他決策樹更準確，但是由于搜索空間是指數(shù)規(guī)模的，找出最佳決策樹在計算上是不可行的。盡管如此，人們還是開發(fā)了一些有效的算法，能夠在合理的時間內(nèi)構(gòu)造出具有一定準確率的次最優(yōu)決策樹。這些算法通常都采用貪心策略。有許多決策樹算法:Hunt算法信息增益——Informationgain（ID3）增益比率——Gainration（C4.5）基尼指數(shù)——Giniindex

(SLIQ，SPRINT)第4章分類基本概念、決策樹與模型評估如何建立決策樹對于給定的屬性集，可以構(gòu)造的決77在Hunt算法中，通過將訓(xùn)練記錄相繼劃分成較純的子集，以遞歸方式建立決策樹。設(shè)是與結(jié)點t相關(guān)聯(lián)的訓(xùn)練記錄集，而是類標號，Hunt算法的遞歸定義如下。（1）如果中所有記錄都屬于同一個類，則t是葉結(jié)點，用標記。（2）如果中包含屬于多個類的記錄，則選擇一個屬性測試條件，將記錄劃分成較小的子集。對于測試條件的每個輸出，創(chuàng)建一個子女結(jié)點，并根據(jù)測試結(jié)果將中的記錄分布到子女結(jié)點中。然后，對于每個子女結(jié)點，遞歸地調(diào)用該算法。第4章分類基本概念、決策樹與模型評估在Hunt算法中，通過將訓(xùn)練記錄相繼劃分成較純的子集，以遞歸78Hunt算法Tid有房者婚姻狀況年收入拖欠貸款者1是單身125k否2否已婚100k否3否單身70k否4是已婚120k否5否離異95k是6否已婚60k否7是離異220k否8否單身85k是9否已婚75k否10否單身90k是第4章分類基本概念、決策樹與模型評估Hunt算法Tid有房者婚姻狀況年收入拖欠貸款者1是單身1279拖欠貸款者=否拖欠貸款者=否拖欠貸款者=否有房者拖欠貸款者=否有房者拖欠貸款者=否婚姻狀況年收入拖欠貸款者=是拖欠貸款者=否(b)(c)(d)(a)拖欠貸款者=否有房者拖欠貸款者=否婚姻狀況拖欠貸款者=是是是否否否是單身離異單身離異已婚已婚<80k>=80kHunt算法構(gòu)造決策樹第4章分類基本概念、決策樹與模型評估拖欠貸款者=否拖欠貸款者=否拖欠貸款者=否有房者拖欠貸款者=80如果屬性值的每種組合都在訓(xùn)練數(shù)據(jù)中出現(xiàn)，并且每種組合都具有唯一的類標號，則Hunt算法是有效的。但是對于大多數(shù)實際情況，這些假設(shè)太苛刻了，因此，需要附加的條件來處理以下的情況：（1）算法的第二步所創(chuàng)建的子女結(jié)點可能為空，即不存在與這些結(jié)點相關(guān)聯(lián)的記錄。如果沒有一個訓(xùn)練記錄包含這樣的結(jié)點相關(guān)聯(lián)的屬性值組合，這種情形就可能發(fā)生。這時，該結(jié)點成為葉結(jié)點，類標號為其父結(jié)點上訓(xùn)練記錄中的多數(shù)類。（2）在第二步，如果與相關(guān)聯(lián)的所有記錄都具有相同的屬性值（目標屬性除外），則不可能進一步劃分這些記錄。在這種情況下，該結(jié)點為葉結(jié)點，其標號為與該結(jié)點相關(guān)聯(lián)的訓(xùn)練記錄中的多數(shù)類。第4章分類基本概念、決策樹與模型評估如果屬性值的每種組合都在訓(xùn)練數(shù)據(jù)中出現(xiàn)，并且每種組合都具有唯81決策樹歸納的設(shè)計問題（1）如何分裂訓(xùn)練記錄？（2）如何停止分裂過程？樹增長過程的每個遞歸步驟都必須選擇一個屬性測試條件，將記錄劃分成較小的子集。為了實現(xiàn)這個步驟。算法必須提供為不同類型的屬性指定測試條件的方法，并且提供評估每種測試條件的客觀度量。決策樹需要有結(jié)束條件，以終止決策樹的生長過程。一個可能的策略是分裂結(jié)點，直到所有的記錄都屬于同一個類，或者所有的記錄都具有相同的屬性值。第4章分類基本概念、決策樹與模型評估決策樹歸納的設(shè)計問題（1）如何分裂訓(xùn)練記錄？（2）如何停止分82表示屬性測試條件的方法1、二元屬性二元屬性的測試條件產(chǎn)生兩個可能的輸出。體溫恒溫冷血二元屬性的測試條件第4章分類基本概念、決策樹與模型評估表示屬性測試條件的方法1、二元屬性體溫恒溫冷血二元屬性的測832、標稱屬性由于標稱屬性有多個屬性值，它的測試條件可以用兩種方法表示?；橐鰻顩r單身已婚離異婚姻狀況已婚單身，離異婚姻狀況離異單身，已婚婚姻狀況單身已婚，離異多路劃分二元劃分（通過屬性值分組）第4章分類基本概念、決策樹與模型評估2、標稱屬性婚姻狀況單身已婚離異婚姻狀況已婚單身，離異婚姻狀843、序數(shù)屬性序數(shù)屬性也可以產(chǎn)生二元或多路劃分，只要不違背序數(shù)屬性值的有序性，就可以對屬性值進行分組。襯衣尺碼小號，中號大號，加大號襯衣尺碼小號中號，加大號襯衣尺碼小號，大號中號，加大號（a）（b）（c）第4章分類基本概念、決策樹與模型評估3、序數(shù)屬性襯衣尺碼小號，中號大號，加大號襯衣尺碼小號中號，854、連續(xù)屬性對于連續(xù)屬性來說，測試條件可以是具有二元輸出的比較測試或也可以是具有形如輸出的范圍查詢。年收入>80k（a）（b）年收入是否<10k{10k,25k}<10k{25k,50k}{50k,80k}連續(xù)屬性的測試條件第4章分類基本概念、決策樹與模型評估4、連續(xù)屬性年收入>80k（a）（b）年收入是否<10k{186有很多度量可以用來確定劃分記錄的最佳方法，這些度量用劃分前和劃分后的記錄的類分布定義。選擇最佳劃分的度量設(shè)表示給定結(jié)點t中屬于類i的記錄所占的比例，有時，我們省略結(jié)點t，直接用表示該比例。在兩類問題中，任意結(jié)點的類分布都可以記作其中。性別男女車型家用運動豪華C0:6C1:4C0:4C1:6C0:1C1:3C0:8C1:0C0:1C1:7（b）（a）C0:1C1:0C0:1C1:0C0:0C1:1C0:0C1:1顧客IDv1v10v20v11（c）……第4章分類基本概念、決策樹與模型評估有很多度量可以用來確定劃分記錄的最佳方法，這些度量用劃分前和87選擇最佳劃分的度量通常是根據(jù)劃分后子女結(jié)點不純性的度量。不純的程度越低，類分布就越傾斜。例如（0,1）的結(jié)點具有零不純性，而均衡分布（0.5,0.5）的結(jié)點具有最高的不純性。不純性度量的例子包括：熵：基尼指數(shù)：分類誤差：其中c是類的個數(shù)，并且在計算熵時，第4章分類基本概念、決策樹與模型評估選擇最佳劃分的度量通常是根據(jù)劃分后子女結(jié)點不純性的度量。不純88結(jié)點N1計數(shù)類=00類=16結(jié)點N3計數(shù)類=03類=13結(jié)點N2計數(shù)類=01類=15第4章分類基本概念、決策樹與模型評估結(jié)點N1計數(shù)類=00類=16結(jié)點N3計數(shù)類=03類=13結(jié)點89二元分類問題不純性度量之間的比較不同的不純性度量是一致的，但是作為測試條件的屬性選擇仍然因不純性度量的選擇而異。第4章分類基本概念、決策樹與模型評估二元分類問題不純性度量之間的比較不同的不純性度量是一致的，但90為確定測試條件的效果，我們需要比較父結(jié)點（劃分前）的不純性程度和子女結(jié)點（劃分后）的不純性程度，它們的差越大，測試條件的效果就越好。增益是一種可以用來確定劃分效果的標準：其中，是給定結(jié)點的不純性度量，N是父結(jié)點上的記錄總數(shù)，k是屬性值的個數(shù)，是與子女結(jié)點相關(guān)聯(lián)的記錄個數(shù)。決策樹算法選擇最大化增益的測試條件。第4章分類基本概念、決策樹與模型評估為確定測試條件的效果，我們需要比較父結(jié)點（劃分前）的不純性程91B是否結(jié)點N1結(jié)點N2A是否結(jié)點N1結(jié)點N2父結(jié)點C06C16Gini=0.500N1N2C042C133Gini=0.486N1N2C015C142Gini=0.3711、二元屬性的劃分第4章分類基本概念、決策樹與模型評估B是否結(jié)點N1結(jié)點N2A是否結(jié)點N1結(jié)點N2父結(jié)點C922、標稱屬性的劃分車型{運動，豪華}{家用}C091C173Gini0.468車型{運動}{家用，豪華}C082C1010Gini0.167車型{家用}{運動}{豪華}C0181C1307Gini0.163（a）二元劃分(b)多路劃分標稱屬性可以產(chǎn)生二元劃分或者多路劃分第4章分類基本概念、決策樹與模型評估2、標稱屬性的劃分車型{運動，豪華}{家用}C091C173933、連續(xù)屬性的劃分1.使用二元劃分2.劃分點v選擇N個記錄中所有屬性值作為劃分點3.對每個劃分進行類計數(shù),A<v和Av4.計算每個候選點v的Gini指標，并從中選擇具有最小值的候選劃分點5.時間復(fù)雜度為O(n2)第4章分類基本概念、決策樹與模型評估3、連續(xù)屬性的劃分1.使用二元劃分第4章分類基本概念、決策樹94降低計算復(fù)雜性的方法:1.將記錄進行排序2.從兩個相鄰的排過序的屬性值之間選擇中間值作為劃分點3.計算每個候選點的Gini值4.時間復(fù)雜度為O（NlogN）第4章分類基本概念、決策樹與模型評估降低計算復(fù)雜性的方法:第4章分類基本概念、決策樹與模型評估954、增益率熵和Gini指標等不純性度量趨向有利于具有大量不同值的屬性。性別男女車型家用運動豪華C0:6C1:4C0:4C1:6C0:1C1:3C0:8C1:0C0:1C1:7（b）（a）測試條件“車型”要比測試條件“性別”要好，因為它產(chǎn)生了更純的派生結(jié)點。測試條件“顧客ID”相比前兩個產(chǎn)生更純的劃分，但是它卻不是一個有預(yù)測性的屬性，因為與每個劃分相關(guān)聯(lián)的記錄太少，以致不能作出可靠的預(yù)測。C0:1C1:0C0:1C1:0C0:0C1:1C0:0C1:1顧客IDv1v10v20v11（c）……第4章分類基本概念、決策樹與模型評估4、增益率熵和Gini指標等不純性度量趨向有利于具有大量不同96如何解決？第一種策略：限制測試條件只能是二元劃分。第二種策略：修改評估劃分的標準，把屬性測試條件產(chǎn)生的輸出數(shù)也考慮進去。例如：CART就是采用這樣的策略。例如：決策樹算法C4.5采用增益率（gainratio）的劃分標準來評估劃分。第4章分類基本概念、決策樹與模型評估如何解決？第一種策略：限制測試條件只能是二元劃分。第二種策略97決策樹歸納特點的總結(jié)1、決策樹歸納是一種構(gòu)建分類模型的非參數(shù)方法。2、找到最佳的決策樹是NP完全問題。3、已開發(fā)的構(gòu)建決策樹技術(shù)不需要昂貴的計算代價，即使訓(xùn)練集非常大，也可以快速建立模型。4、決策樹相對容易解釋，特別是小型的決策樹。5、決策樹是學(xué)習(xí)離散值函數(shù)的典型代表。6、決策樹算法對于噪聲的干擾具有相當(dāng)好的魯棒性。7、冗余屬性不會對決策樹的準確率造成不利的影響。8、由于大多數(shù)決策樹算法都采用自頂向下的遞歸劃分方法，因此沿著樹向下，記錄會越來越少。第4章分類基本概念、決策樹與模型評估決策樹歸納特點的總結(jié)1、決策樹歸納是一種構(gòu)建分類模型的非參數(shù)989、子樹可能在決策樹中重復(fù)多次，這使得決策樹過于復(fù)雜，并且可能更難解釋。10、目前為止，本章介紹的測試條件每次都只涉及一個屬性。二維數(shù)據(jù)集的決策樹及其邊界示例第4章分類基本概念、決策樹與模型評估9、子樹可能在決策樹中重復(fù)多次，這使得決策樹過于復(fù)雜，并且可99使用僅涉及單個屬性的測試條件不能有效劃分的數(shù)據(jù)集的例子斜決策樹（obliquedecisiontree）可以克服以上的局限，因為它允許測試條件涉及多個屬性。上圖中的數(shù)據(jù)集可以很容易地用斜決策樹表示，該決策樹只有一個結(jié)點，其測試條件為：缺點：盡管這種技術(shù)有更強的表達能力，并且能夠產(chǎn)生更緊湊的決策樹，但是為給定的結(jié)點找出最佳測試條件的計算可能是相當(dāng)復(fù)雜的。x+y<1Class=+

Class=第4章分類基本概念、決策樹與模型評估使用僅涉及單個屬性的測試條件不能有效劃分的數(shù)據(jù)集的例子斜決策100構(gòu)造歸納（constructiveinduction）提供另一種將數(shù)據(jù)劃分成齊次非矩形區(qū)域的方法，該方法創(chuàng)建復(fù)合屬性，代表已有屬性的算術(shù)或邏輯組合。新屬性提供了更好的類區(qū)分能力，并在決策樹歸納之前就增廣到數(shù)據(jù)集中。與決策樹不同，構(gòu)造歸納不需要昂貴的花費，因為在構(gòu)造決策樹之前，它只需要一次性地確定屬性的所有相關(guān)組合，相比之下，在擴展每個內(nèi)部結(jié)點時，斜決策樹都需要動態(tài)地確定正確的屬性組合。然而構(gòu)造歸納會產(chǎn)生冗余的屬性，因為新創(chuàng)建的屬性是已有屬性的組合。11、研究表明不純性度量方法的選擇對決策樹算法的性能影響很小。第4章分類基本概念、決策樹與模型評估構(gòu)造歸納（constructiveinduction）101一個好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。四、模型的過分擬合第4章分類基本概念、決策樹與模型評估一個好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。四、模型的過102二維數(shù)據(jù)過分擬合的例子下圖所示的二維數(shù)據(jù)集中的數(shù)據(jù)點屬于兩個類，分別標記為類“o”和類“+”，類“o”的數(shù)據(jù)點由三個高斯分布混合產(chǎn)生，而類“+”的數(shù)據(jù)點用一個均勻分布產(chǎn)生。數(shù)據(jù)集中，總共有1200個數(shù)據(jù)點是屬于類“o”，1800個數(shù)據(jù)點屬于類“+”，其中30%的點用于訓(xùn)練，剩下的70%用于檢驗。對訓(xùn)練集使用以Gini指標作為不純性度量的決策樹方法。具有兩個類的數(shù)據(jù)集的例子第4章分類基本概念、決策樹與模型評估二維數(shù)據(jù)過分擬合的例子下圖所示的二維數(shù)據(jù)集中的數(shù)據(jù)點屬于兩個103當(dāng)決策樹很小時，訓(xùn)練誤差和檢驗誤差都很大，這種情況稱作模型擬合不足（modelunderfitting）。出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實結(jié)構(gòu)，因此，模型在訓(xùn)練集和檢驗集上的性能都很差。一旦樹的規(guī)模變得太大，即使訓(xùn)練誤差還在降低，但是檢驗誤差開始增大，這種現(xiàn)象稱為模型過分擬合（modeloverfitting）。訓(xùn)練誤差和檢驗誤差第4章分類基本概念、決策樹與模型評估當(dāng)決策樹很小時，訓(xùn)練誤差和檢驗誤差都很大，這種104為理解過分擬合現(xiàn)象，舉個例子：可以擴展樹的葉結(jié)點，直到它完全擬合訓(xùn)練數(shù)據(jù)。雖然這樣一顆復(fù)雜的樹的訓(xùn)練誤差為0，但是檢驗誤差可能很大，因為該樹可能包含這樣的結(jié)點，它們偶然地擬合訓(xùn)練數(shù)據(jù)中某些噪聲。這些結(jié)點降低了決策樹的性能，因為他們不能很好的泛化到檢驗樣本。（a）包含11個葉結(jié)點的決策樹（b）包含24個葉結(jié)點的決策樹過分擬合與擬合不足是兩種與模型復(fù)雜度有關(guān)的異常現(xiàn)象。第4章分類基本概念、決策樹與模型評估為理解過分擬合現(xiàn)象，舉個例子：可以擴展樹的葉結(jié)105名稱體溫胎生4條腿冬眠類標號豪豬恒溫是是是是貓恒溫是是否是蝙蝠恒溫是否是否*鯨恒溫是否否否*蠑螈冷血否是是否科莫多巨蜥冷血否是否否蟒蛇冷血否否是否鮭魚冷血否否否否鷹恒溫否否否否虹鳉冷血是否否否哺乳動物分類的訓(xùn)練數(shù)據(jù)集樣本。（“*”為錯誤標記記錄）十個訓(xùn)練記錄中有兩個被錯誤標記：蝙蝠和鯨被錯誤標記為非哺乳動物，而不是哺乳動物。噪聲導(dǎo)致的過分擬合第4章分類基本概念、決策樹與模型評估名稱體溫胎生4條腿冬眠類標號豪豬恒溫是是是是貓恒溫是是否是蝙106名稱體溫胎生4條腿冬眠類標號人恒溫是否否是鴿子恒溫否否否否象恒溫是是否是豹紋鯊冷血是否否否海龜冷血否是否否企鵝冷血否否否否鰻冷血否否否否海豚恒溫是否否是針鼴恒溫否是是是希拉毒蜥冷血否是是否哺乳動物分類的檢驗數(shù)據(jù)集樣本。第4章分類基本概念、決策樹與模型評估名稱體溫胎生4條腿冬眠類標號人恒溫是否否是鴿子恒溫否否否否象107完全擬合訓(xùn)練數(shù)據(jù)的決策樹顯示在下圖（a）中，雖然該樹的訓(xùn)練誤差為0，但是它在檢驗數(shù)據(jù)集上的誤差高達30%。體溫恒溫冷血胎生4條腿哺乳類動物非哺乳類動物非哺乳類動物非哺乳類動物是否是否體溫恒溫冷血胎生非哺乳類動物非哺乳類動物是否哺乳類動物（a）模型M1（b）模型M2圖（b）中決策樹M2盡管訓(xùn)練誤差較高（20%），但是它具有較低的檢驗誤差。第4章分類基本概念、決策樹與模型評估完全擬合訓(xùn)練數(shù)據(jù)的決策樹顯示在下圖（a）中，雖然該樹的訓(xùn)練誤108缺乏代表性樣本導(dǎo)致的過分擬合名稱體溫胎生4條腿冬眠類標號蠑螈冷血否是是否虹鳉冷血是否否否鷹恒溫否否否否弱夜鷹恒溫否否是否鴨嘴獸恒溫否是是是體溫恒溫冷血冬眠4條腿哺乳類動物非哺乳類動物非哺乳類動物非哺乳類動物是否是否人、大象和海豚都被誤分類，因為決策樹把恒溫但不冬眠的脊柱動物劃分為非哺乳動物。決策樹做出這樣的分類決策是因為只有一個訓(xùn)練記錄（鷹）具有這些特性。第4章分類基本概念、決策樹與模型評估缺乏代表性樣本導(dǎo)致的過分擬合名稱體溫胎生4條腿冬眠類標號蠑螈109過分擬合與多重比較過程1、在決策樹增長過程中，可以進行多種測試，以確定哪個屬性能夠最好的劃分訓(xùn)練數(shù)據(jù)。2、在這種情況下，算法實際上是使用多重比較過程來決定是否需要擴展決策樹。3、當(dāng)候選屬性多，訓(xùn)練記錄數(shù)少時，這種影響就變得更加明顯。多重比較過程與模型過分擬合有什么關(guān)系？第4章分類基本概念、決策樹與模型評估過分擬合與多重比較過程1、在決策樹增長過程中，可以進行多種測1101、過分擬合的主要原因一直是個爭辯的話題，但大家還是普遍同意模型的復(fù)雜度對模型的過分擬合有影響。2、如何確定正確的模型復(fù)雜度？理想的復(fù)雜度是能產(chǎn)生最低泛化誤差的模型的復(fù)雜度。3、估計泛化誤差的方法使用再代入估計。用訓(xùn)練誤差提供對泛化誤差的樂觀估計結(jié)合模型復(fù)雜度估計統(tǒng)計上界使用確定集泛化誤差估計第4章分類基本概念、決策樹與模型評估1、過分擬合的主要原因一直是個爭辯的話題，但大家還是普遍同意111泛化誤差估計1、使用再代入估計再代入估計方法假設(shè)訓(xùn)練數(shù)據(jù)集可以很好地代表整體數(shù)據(jù)，因而，可以使用訓(xùn)練誤差（又稱再代入誤差）提供泛化誤差的樂觀估計。但是訓(xùn)練誤差通常是泛化誤差的一種很差的估計?？紤]下圖中的二叉決策樹。假設(shè)兩顆決策樹都由相同的訓(xùn)練數(shù)據(jù)產(chǎn)生，并且都根據(jù)每個葉結(jié)點多數(shù)類做出劃分。注意，左邊的樹T1復(fù)雜一些，它擴展了右邊決策樹T2的某些結(jié)點。左決策樹的訓(xùn)練誤差是，而右決策樹的訓(xùn)練誤差是。根據(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第4章分類基本概念、決策樹與模型評估泛化誤差估計1、使用再代入估計再代入估計方法假設(shè)訓(xùn)練數(shù)據(jù)集可1122、結(jié)合模型復(fù)雜度如之前所述，模型越是復(fù)雜，出現(xiàn)過分擬合的幾率就越高，因此，我們更喜歡采用較為簡單的模型。這種策略與應(yīng)用眾所周知的奧卡姆剃刀一致。奧卡姆剃刀：給定兩個具有相同泛化誤差的模型，較簡單的模型比較復(fù)雜的模型更可取。悲觀誤差評估：使用訓(xùn)練誤差與模型復(fù)雜度罰項（penaltyterm）的和計算泛化誤差。結(jié)果泛化誤差可以看作模型的悲觀誤差估計。設(shè)n(t)是結(jié)點t分類的訓(xùn)練記錄數(shù)，e(t)是被誤分類的記錄數(shù)。決策樹T的悲觀誤差估計可以用下式計算：其中，k是決策樹的葉結(jié)點數(shù)，e(T)是決策樹的總訓(xùn)練誤差，是訓(xùn)練記錄數(shù)，是每個結(jié)點對應(yīng)的罰項。第4章分類基本概念、決策樹與模型評估2、結(jié)合模型復(fù)雜度如之前所述，模型越是復(fù)雜，出現(xiàn)過分擬合的幾113+：3-：0+：3-：1+：1-：2+：0-：2+：2-：1+：3-：1+：0-：5+：3-：6+：3-：0+：1-：4+：5-：2決策樹T1決策樹T2考慮上圖的二叉決策樹。如果罰項等于0.5，左邊的決策樹的悲觀誤差估計為：右邊的決策樹的悲觀誤差估計為：此時，左邊的決策樹比右邊的決策樹具有更好的悲觀誤差估計。第4章分類基本概念、決策樹與模型評估+：3+：3+：1+：0+：2+：3+：0+：3+：3+：1114最小描述長度原則（minimumdescriptionlength,MDL）標記的未標記的第4章分類基本概念、決策樹與模型評估最小描述長度原則（minimumdescriptionl115Cost是傳輸總代價。目標：最小化Cost值。其中Cost(Data|Model)是誤分類記錄編碼的開銷。Cost(Model)是模型編碼的開銷。另一種可能是，A決定