【正文】 Ch eat No No No Yes Yes Yes No No No NoTa xab l e In c om e60 70 75 85 90 95 100 120 125 22055 65 72 80 87 92 97 110 122 172 230= = = = = = = = = = = Yes 0 3 0 3 0 3 0 3 1 2 2 1 3 0 3 0 3 0 3 0 3 0No 0 7 1 6 2 5 3 4 3 4 3 4 3 4 4 3 5 2 6 1 7 0G in i 候選劃分點 排序后的值 決策樹歸納的設計問題 2： 如何停止分裂過程？ ?停止方法： – 方法 1：當所有記錄都屬于同一分類時，停止劃分 – 方法 2：當所有記錄都有相似（相同）屬性值時，停止劃分 – 方法 3：提前終止 決策樹歸納算法 ?算法輸入：訓練記錄集 E和屬性集 F。log2 (5/6) = P(C0) = 2/6 P(C1) = 4/6 Entropy = – (2/6) – 通常，將給定的數(shù)據(jù)集分為 訓練集（ training set ）和 檢驗集（ test set ） 。log 0 – 1 – 效率低 – 計算代價昂貴 TaxableIne 80K?Yes NoTi d 有房者 婚姻 狀況 收入 拖欠 貸款者 1 Yes Single 125K No 2 No Marr i ed 100K No 3 No Single 70K No 4 Yes Marr i ed 120K No 5 No Divor ce d 95K Yes 6 No Marr i ed 60K No 7 Yes Divor ce d 220K No 8 No Single 85K Yes 9 No Marr i ed 75K No 10 No Single 90K Yes 10 改進方法： ? 根據(jù)劃分屬性，先對記錄進行 排序 ? 從兩個相鄰的排過序的屬性值中 選擇中間值作為候選劃分點(5 6 7 80、 …… ）。 – Classify()：為葉子結點確定類標號。 ?問題： – 整個訓練樣本集的不純度是多少？ – 如果對數(shù)據(jù)按 車型 屬性進行多路劃分，則 ?（車型 =運動）的結點的不純度是多少？ ?（車型 =豪華）的結點的不純度是多少？ ?（車型 =家用）的結點的不純度是多少？ 計算不純性方法 2: 基尼指數(shù)（ gini） ? 結點 t的吉尼指數(shù) : 其中， c為結點 t中不同類標號個數(shù) p( i | t)是給定結點 t中屬于類 i的記錄所占比例，簡記為 pi ? 結點 Gini指數(shù)的取值范圍： – 當記錄均勻分布于各分類時，將取得最大值 (1 1/nc) – 當所有記錄都屬于同一分類時，將取得最小值 (0) 120( ) 1 [ ( | ) ]ciG ini t p i t???? ?例：分別計算 3個結點的 Gini指數(shù) P(C0) = 0/6 = 0 P(C1) = 6/6 = 1 Gini = 1 – P(C0)2 – P(C1)2 = 1 – 0 – 1 = 0 P(C0) = 1/6 P(C1) = 5/6 Gini = 1 – (1/6)2 – (5/6)2 = P(C0) = 2/6 P(C1) = 4/6 Gini = 1 – (2/6)2 – (4/6)2 = 120( ) 1 [ ( | ) ]ciG ini t p i t???? ?結點 N 1 計數(shù) 類 = C 0 0 類 = C 1 6 結點 N 2 計數(shù) 類 = C 0 1 類 = C 1 5 結點 N 3 計數(shù) 類 = C 0 3 類 = C 1 3 練習 2 ?已知：數(shù)據(jù)見課本表 47（ P122 題 2），采用Gini指數(shù) 作為結點的不純度度量。ve Bayes and Bayesian Belief Networks ? 支持向量機 Support Vector Machines 決策樹定義 ?決策樹是由結點和有向邊組成的層次結構。 在二元分類問題中，任意結點的類分布可以記作 (p0， p1)，其中p1 =1 p0 。 – 極端情況如：以顧客 ID進行劃分，比其他劃分方法能得到更“純”的派生結點 改進方法 ? 信息增益（熵差） : ni = 孩子節(jié)點 i的記錄數(shù) n = 節(jié)點 p的記錄數(shù) ?用于 ID3和 ???????? ??ki isp lit iEntropynnpEntropyGAIN 1 )()(? 增益率 : 將父節(jié)點 p劃分為 k部分 n表示 p的記錄數(shù) ni 表示第 i部分（ p的第 i個節(jié)點）的記錄數(shù) – 調整信息增益，引入劃分信息 SplitInfo，把屬性測試條件產(chǎn)生的輸出數(shù)也考慮進去。 ? 不純度度量方法的選擇對決策樹性能影響很小 ?分類模型的誤差： – 訓練誤差：在訓練記錄上誤分樣本的比例 – 泛化誤差（檢驗誤差）：模型在未知記錄上的期望誤差 ?一個好的分類模型，必須具有低的訓練誤差和泛化誤差。 ?用 增益 Δ來作為確定劃分效果的標準 其中： I(.)是結點不純性度量 ,N是父節(jié)點上的記錄總數(shù)， k是父節(jié)點的分支數(shù)， N(vj)是子女結點 vj的記錄個數(shù)。 假設 t表示結點， Dt 表示與結點 t相關聯(lián)的訓練記錄集， y={y1,y2,…,yc} 是類標號 ? Hunt算法的遞歸定義 : – 如果 Dt 中所有記錄都屬于 同一個類 yt, 則 t就是葉子節(jié)點，并用 yt標號 – 如果 Dt 是一個 空集 ，那么 t就是葉子節(jié)點，其標號為其父結點上訓練記錄中的多數(shù)類 Tid Re f und Marital Stat u s Taxable In e Che a t 1 Yes Single 125K No 2 No Marr i ed 100K