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

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

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

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

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