【文章內容簡介】 是 否 結點 N1 結點 N2 A 是 否 結點 N1 結點 N2 父結點 C0 6 C1 6 Gini= N1 N2 C0 4 2 C1 3 3 Gini= N1 N2 C0 1 5 C1 4 2 Gini= 二元屬性的劃分 標稱屬性的劃分 車型 {運動，豪華 } {家用 } C0 9 1 C1 7 3 Gini 車型 {運動 } {家用，豪華 } C0 8 2 C1 0 10 Gini 車型 {家用 } {運動 } {豪華 } C0 1 8 1 C1 3 0 7 Gini （ a）二元劃分 (b)多路劃分 標稱屬性可以產生二元劃分或者多路劃分 連續(xù)屬性的劃分 v選擇 N個記錄中所有屬性值作為劃分點 , A v 和 A ? v v的 Gini指標，并從中選擇具有最小值的候選劃分點 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 劃分點 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 劃分點 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 降低計算復雜性的方法 : Gini值 O（ NlogN） 增益率 熵和 Gini指標等不純性度量趨向有利于具有大量不同值的屬性。 性別 男 女 車型 家用 運動 豪華 C0:6 C1:4 C0:4 C1:6 C0:1 C1:3 C0:8 C1:0 C0:1 C1:7 （ b） （ a） 測試條件“車型”要比測試條件“性別”要好，因為它產生了更純的派生結點。 測試條件“顧客 ID”相比前兩個產生更純的劃分，但是它卻不是一個有預測性的屬性，因為與每個劃分相關聯(lián)的記錄太少，以致不能作出可靠的預測。 C0:1 C1:0 C0:1 C1:0 C0:0 C1:1 C0:0 C1:1 顧客 ID v1 v10 v20 v11 （ c） … … 第一種策略：限制測試條件只能是二元劃分。 第二種策略：修改評估劃分的標準，把屬性測試條件產生的輸出數(shù)也考慮進去。 例如： CART就是采用這樣的策略。 例如：決策樹算法 （ gain ratio）的劃分標準來評估劃分。 InfoSpli t ratioGain in f o?? 是劃分的總數(shù)，而其中，劃分信息 k)()logP( vInfoSplit 1i 2i??? k ivP決策樹歸納特點的總結 決策樹歸納是一種構建分類模型的非參數(shù)方法。 找到最佳的決策樹是 NP完全問題。 已開發(fā)的構建決策樹技術不需要昂貴的計算代價，即使訓練集非常 大，也可以快速建立模型。 決策樹相對容易解釋，特別是小型的決策樹。 決策樹是學習離散值函數(shù)的典型代表。 決策樹算法對于噪聲的干擾具有相當好的魯棒性。 冗余屬性不會對決策樹的準確率造成不利的影響。 由于大多數(shù)決策樹算法都采用自頂向下的遞歸劃分方法，因此沿著樹向下，記錄會越來越少。 子樹可能在決策樹中重復多次，這使得決策樹過于復雜，并且可能更難解釋。 目前為止，本章介紹的測試條件每次都只涉及一個屬性。 二維數(shù)據(jù)集的決策樹及其邊界示例 PQ RS 0 10 1QS 00 1y 0 . 3 3 ? : 0 : 3 : 4 : 0y 0 . 4 7 ? : 4 : 0 : 0 : 4x 0 . 4 3 ?Y e sY e sN oN o Y e s N o0 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 100 . 10 . 20 . 30 . 40 . 50 . 60 . 70 . 80 . 91xy使用僅涉及單個屬性的測試條件不能有效劃分的數(shù)據(jù)集的例子 斜決策樹（ oblique decision tree）可以克服以上的局限，因為它允許測試條件涉及多個屬性。上圖中的數(shù)據(jù)集可以很容易地用斜決策樹表示，該決策樹只有一個結點，其測試條件為： 1?? yx缺點：盡管這種技術有更強的表達能力，并且能夠產生更緊湊的決策樹，但是為給定的結點找出最佳測試條件的計算可能是相當復雜的。 x + y 1 Class = + Class = 構造歸納（ constructive induction） 提供另一種將數(shù)據(jù)劃分成齊次非矩形區(qū)域的方法，該方法創(chuàng)建復合屬性，代表已有屬性的算術或邏輯組合。新屬性提供了更好的類區(qū)分能力，并在決策樹歸納之前就增廣到數(shù)據(jù)集中。 與決策樹不同，構造歸納不需要昂貴的花費，因為在構造決策樹之前，它只需要一次性地確定屬性的所有相關組合，相比之下，在擴展每個內部結點時，斜決策樹都需要動態(tài)地確定正確的屬性組合。然而構造歸納會產生冗余的屬性，因為新創(chuàng)建的屬性是已有屬性的組合。 1研究表明不純性度量方法的選