【正文】 性 序數(shù)屬性也可以產(chǎn)生二元或多路劃分，只要不違背序數(shù)屬性值的有序性，就可以對(duì)屬性值進(jìn)行分組。 )( vA?)( vA? ),2,1(1 kivAv ii ???? ?年收入80k （ a） （ b） 年收入 是 否 10k {10k,25k} 10k {25k,50k} {50k,80k} 連續(xù)屬性的測(cè)試條件 有很多度量可以用來確定劃分記錄的最佳方法，這些度量用劃分前和劃分后的記錄的類分布定義。在兩類問題中，任意結(jié)點(diǎn)的類分布都可以記作 其中 。不純的程度越低，類分布就越傾斜。不純性度量的例子包括： ????? 102 )|(log)|()(citiptiptEntr opy ????? 102)]|([1)( citiptGini )]|([max1)(_C tipterrorionlassificati??熵： 基尼指數(shù)： 分類誤差： 其中 c是類的個(gè)數(shù)，并且在計(jì)算熵時(shí)， 00log 2 ?O結(jié)點(diǎn) N1 計(jì)數(shù) 類 =0 0 類 =1 6 結(jié)點(diǎn) N3 計(jì)數(shù) 類 =0 3 類 =1 3 結(jié)點(diǎn) N2 計(jì)數(shù) 類 =0 1 類 =1 5 0)6/6()6/0(1 22 ????Gini 0)6/6(log)6/6()6/0(log)6/0( 22 ????E ntropy 0]6/6,6/0max [1 ???Error )6/5()6/1(1 22 ????Gini )6/5(log)6/5()6/1(log)6/1(22 ????E ntropy ]6/5,6/1max[1 ???Erro r )6/3()6/3(1 22 ????Gini 1)6/3(log)6/3()6/3(log)6/3(22 ????E ntropy ]6/3,6/3max [1 ???Error二元分類問題不純性度量之間的比較 不同的不純性度量是一致的，但是作為測(cè)試條件的屬性選擇仍然因不純性度量的選擇而異。增益 是一種可以用來確定劃分效果的標(biāo)準(zhǔn)： ?????? kj jj vINvNparentI 1 )()()()(?I其中， 是給定結(jié)點(diǎn)的不純性度量， N是父結(jié)點(diǎn)上的記錄總數(shù)， k是屬性值的個(gè)數(shù)， 是與子女結(jié)點(diǎn) 相關(guān)聯(lián)的記錄個(gè)數(shù)。 B 是 否 結(jié)點(diǎn) N1 結(jié)點(diǎn) N2 A 是 否 結(jié)點(diǎn) N1 結(jié)點(diǎn) N2 父結(jié)點(diǎn) C0 6 C1 6 Gini= N1 N2 C0 4 2 C1 3 3 Gini= N1 N2 C0 1 5 C1 4 2 Gini= 二元屬性的劃分 標(biāo)稱屬性的劃分 車型 {運(yùn)動(dòng)，豪華 } {家用 } C0 9 1 C1 7 3 Gini 車型 {運(yùn)動(dòng) } {家用，豪華 } C0 8 2 C1 0 10 Gini 車型 {家用 } {運(yùn)動(dòng) } {豪華 } C0 1 8 1 C1 3 0 7 Gini （ a）二元?jiǎng)澐? (b)多路劃分 標(biāo)稱屬性可以產(chǎn)生二元?jiǎng)澐只蛘叨嗦穭澐? 連續(xù)屬性的劃分 v選擇 N個(gè)記錄中所有屬性值作為劃分點(diǎn) , A v 和 A ? v v的 Gini指標(biāo)，并從中選擇具有最小值的候選劃分點(diǎn) O(n2) 類 No No No Y e s Y e s Y e s No No No No 年收入 排序后的值 60 70 75 85 90 95 100 120 125 220 劃分點(diǎn) 55 65 72 80 87 92 97 110 122 172 230 = = = = = = = = = = = Y e s 0 3 0 3 0 3 0 3 1 2 2 1 3 0 3 0 3 0 3 0 3 0 No 0 7 1 6 2 5 3 4 3 4 3 4 3 4 4 3 5 2 6 1 7 0 G i ni 0 . 4 2 0 0 . 4 0 0 0 . 3 7 5 0 . 3 4 3 0 . 4 1 7 0 . 4 0 0 0 . 3 0 0 0 . 3 4 3 0 . 3 7 5 0 . 4 0 0 0 . 4 2 0 類 No No No Y e s Y e s Y e s No No No No 年收入 排序后的值 60 70 75 85 90 95 100 120 125 220 劃分點(diǎn) 55 65 72 80 87 92 97 110 122 172 230 = = = = = = = = = = = Y e s 0 3 0 3 0 3 0 3 1 2 2 1 3 0 3 0 3 0 3 0 3 0 No 0 7 1 6 2 5 3 4 3 4 3 4 3 4 4 3 5 2 6 1 7 0 G i ni 0 . 4 2 0 0 . 4 0 0 0 . 3 7 5 0 . 3 4 3 0 . 4 1 7 0 . 4 0 0 0 . 3 0 0 0 . 3 4 3 0 . 3 7 5 0 . 4 0 0 0 . 4 2 0 降低計(jì)算復(fù)雜性的方法 : Gini值 O（ NlogN） 增益率 熵和 Gini指標(biāo)等不純性度量趨向有利于具有大量不同值的屬性。 測(cè)試條件“顧客 ID”相比前兩個(gè)產(chǎn)生更純的劃分，但是它卻不是一個(gè)有預(yù)測(cè)性的屬性，因?yàn)榕c每個(gè)劃分相關(guān)聯(lián)的記錄太少，以致不能作出可靠的預(yù)測(cè)。 第二種策略：修改評(píng)估劃分的標(biāo)準(zhǔn)，把屬性測(cè)試條件產(chǎn)生的輸出數(shù)也考慮進(jìn)去。 例如：決策樹算法 （ gain ratio）的劃分標(biāo)準(zhǔn)來評(píng)估劃分。 找到最佳的決策樹是 NP完全問題。 決策樹相對(duì)容易解釋，特別是小型的決策樹。 決策樹算法對(duì)于噪聲的干擾具有相當(dāng)好的魯棒性。 由于大多數(shù)決策樹算法都采用自頂向下的遞歸劃分方法，因此沿著樹向下，記錄會(huì)越來越少。 目前為止，本章介紹的測(cè)試條件每次都只涉及一個(gè)屬性。上圖中的數(shù)據(jù)集可以很容易地用斜決策樹表示，該決策樹只有一個(gè)結(jié)點(diǎn)，其測(cè)試條件為： 1?? yx缺點(diǎn)：盡管這種技術(shù)有更強(qiáng)的表達(dá)能力，并且能夠產(chǎn)生更緊湊的決策樹，但是為給定的結(jié)點(diǎn)找出最佳測(cè)試條件的計(jì)算可能是相當(dāng)復(fù)雜的。新屬性提供了更好的類區(qū)分能力，并在決策樹歸納之前就增廣到數(shù)據(jù)集中。然而構(gòu)造歸納會(huì)產(chǎn)生冗余的屬性，因?yàn)樾聞?chuàng)建的屬性是已有屬性的組合。 分類模型誤差 訓(xùn)練誤差 泛化誤差 一個(gè)好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。數(shù)據(jù)集中，總共有 1200個(gè)數(shù)據(jù)點(diǎn)是屬于類“ o”，1800個(gè)數(shù)據(jù)點(diǎn)屬于類“ +”，其中 30%的點(diǎn)用于訓(xùn)練，剩下的 70%用于檢驗(yàn)。 具有兩個(gè)類的數(shù)據(jù)集的例子 當(dāng)決策樹很小時(shí)，訓(xùn)練誤差和檢驗(yàn)誤差都很大，這種情況稱作模型擬合不足（ mo