【正文】 ?決策樹分類方法存在的問題（與模型復(fù)雜度相關(guān)） – 模型擬合不足 Underfitting ?當(dāng)模型過于簡單時，訓(xùn)練誤差和檢驗誤差都比較大 ?出現(xiàn)原因：模型尚未學(xué)習(xí)到數(shù)據(jù)的真實結(jié)構(gòu) – 模型過分擬合 Overfitting ?樹的規(guī)模變得太大，即使訓(xùn)練誤差還在繼續(xù)降低，但是檢驗誤差開始增大 ?出現(xiàn)原因：模型過分擬合了訓(xùn)練數(shù)據(jù)中的噪聲數(shù)據(jù)，或者是訓(xùn)練數(shù)據(jù)缺乏代表性的數(shù)據(jù) 擬合不足 和 過分擬合 Overfitting 訓(xùn)練誤差 檢驗誤差 Underfitting 噪聲導(dǎo)致過分擬合 決策邊界被噪聲點扭曲 缺乏代表性樣本導(dǎo)致過分擬合 處理決策樹歸納中的過分擬合 ? 先剪枝（提前終止規(guī)則） – 樹增長算法在產(chǎn)生完全擬合整個訓(xùn)練數(shù)據(jù)集的完全增長的決策樹之前就停止決策樹的生長 – 方法：選取不純度增益的閾值 – 優(yōu)點：避免產(chǎn)生過分擬合訓(xùn)練數(shù)據(jù)的過于復(fù)雜的子樹 – 缺點：閾值大小難于選取 ? 后剪枝 – 初始決策樹按照最大規(guī)模生長，然后進行剪枝，按照自底向上的方式修剪完全增長的決策樹 – 方法：用新結(jié)點代替子樹；用子樹的常用分支代替子樹 – 優(yōu)點：避免過早終止決策樹的生長 – 缺點：需要浪費額外開銷 。 – 根據(jù)課本的決策樹模型，正常用戶訪問有何特征？ 決策樹歸納的特點 ? 是一種構(gòu)建分類模型的非參數(shù)方法 ? 大多決策樹算法都采用啟發(fā)式的方法來簡化搜索 ? 決策樹容易構(gòu)建，對未知樣本的分類也快 ? 決策樹相對容易理解 ? 對于噪聲的干擾具有相當(dāng)好的魯棒性 ? 冗余屬性不會對決策樹的準(zhǔn)確率造成不利影響 ? 對于數(shù)據(jù)碎片問題，可以通過規(guī)定閾值來檢測和解決 ? 可能會產(chǎn)生子樹在決策樹中重復(fù)出現(xiàn)的情況 ? 對于非水平和垂直的決策邊界問題，可以使用斜決策樹或構(gòu)造歸納方法來解決。 – Classify()：為葉子結(jié)點確定類標(biāo)號。 ?算法輸出：構(gòu)造的決策樹 ?主要函數(shù)： – createNode()：建立一個新結(jié)點。 ? 進一步優(yōu)化 ：僅僅考慮位于具有不同類標(biāo)號的兩個相鄰記錄之間的候選劃分點（ 5 80、 97），計算其 Gini指數(shù)。 – 效率低 – 計算代價昂貴 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、 ……）。 – 如果一個屬性產(chǎn)生了大量的劃分，它的劃分信息SplitInfo將會很大，從而增益率降低。 ?問題 (a)~(g) ?熵和 Gini指數(shù)等不純度趨向有利于具有大量不同值的屬性 – 產(chǎn)生大量輸出測試條件，從而導(dǎo)致與每個劃分關(guān)聯(lián)的記錄很少。 1()( ) ( )kjjjNvI pare nt I vN?? ? ? ? 決策樹歸納算法，通常就是選擇最大化增益Δ的測試條件，作為當(dāng)前節(jié)點的屬性測試條件。 ?問題： – 整個訓(xùn)練樣本集的不純度是多少？ – 如果對數(shù)據(jù)按 車型 屬性進行多路劃分，則 ?（車型 =運動）的結(jié)點的不純度是多少？ ?（車型 =豪華）的結(jié)點的不純度是多少？ ?（車型 =家用）的結(jié)點的不純度是多少？ 二元分類問題結(jié)點不純性度量之間的比較： 利用不純性度量，選擇最佳劃分 ?方法： 分別比較父節(jié)點（劃分前）的不純程度和子女結(jié)點（劃分后）的不純程度，它們的差值越大，測試條件的效果就越好。 ?問題： – 整個訓(xùn)練樣本集的不純度是多少？ – 如果對數(shù)據(jù)按 車型 屬性進行多路劃分，則 ?（車型 =運動）的結(jié)點的不純度是多少？ ?（車型 =豪華）的結(jié)點的不純度是多少？ ?（車型 =家用）的結(jié)點的不純度是多少？ 計算不純性方法 2: 基尼指數(shù)（ gini） ? 結(jié)點 t的吉尼指數(shù) : 其中， c為結(jié)點 t中不同類標(biāo)號個數(shù) p( i | t)是給定結(jié)點 t中屬于類 i的記錄所占比例，簡記為 pi ? 結(jié)點 Gini指數(shù)的取值范圍： – 當(dāng)記錄均勻分布于各分類時，將取得最大值 (1 1/nc) – 當(dāng)所有記錄都屬于同一分類時，將取得最小值 (0) 120( ) 1 [ ( | ) ]ciG ini t p i t???? ?例：分別計算 3個結(jié)點的 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???? ?結(jié)點 N 1 計數(shù) 類 = C 0 0 類 = C 1 6 結(jié)點 N 2 計數(shù) 類 = C 0 1 類 = C 1 5 結(jié)點 N 3 計數(shù) 類 = C 0 3 類 = C 1 3 練習(xí) 2 ?已知：數(shù)據(jù)見課本表 47（ P122 題 2），采用 Gini指數(shù) 作為結(jié)點的不純度度量。log2 (2/6) – (4/6)log2 (1/6) – (5/6)log 0 – 1 選擇最佳劃分的度量 ?選擇最佳劃分的度量通常是根據(jù)劃分后 子女結(jié)點不純性的程度 ： 不純的程度越低，類分布就越傾斜，劃分就越好。哪個劃分測試條件最佳？ 為了度量不同的測試條件，常用劃分前和劃分后記錄的 類分布定