【正文】 ，可依屬性 A 將 D 劃分為 v 個子集 { D1, D2, ..., Dj , ..., Dv } 其中， Dj為 D中的樣本子集，它們在 A上具有屬性值 aj 這些劃分將對應(yīng)于從該節(jié)點 A出來的分支。 數(shù)據(jù)集的信息熵 假設(shè)按屬性 A 劃分 D 中的樣本，且屬性 A 根據(jù)訓(xùn)練數(shù)據(jù)的觀測具有 v 個不同取值 { a1, a2, ..., aj , ..., av }。 （ 1） D中包含有 50%的正例和 50%的負(fù)例。 每個葉結(jié)點 (橢圓框 )代表一個類 : buys_puters=yes 或者 buys_puters=no ? 在這個例子中 ， 特征向量為： (age, student, credit_rating, buys_puters) ? 被決策數(shù)據(jù)的格式為 : (age, student, credit_rating) ? 輸入新的被決策的記錄 ， 可以預(yù)測該記錄隸屬于哪個類 。決策樹分類 王成（副教授） 計算機(jī)科學(xué)與技術(shù)學(xué)院 主要內(nèi)容 ? 什么是決策樹 ? ID3算法 ? 算法改進(jìn) ? CART算法 Decision Tree Modeling 決策樹是一種簡單且應(yīng)用廣泛的 預(yù)測 方法 決策樹 圖 常見的決策樹形式 每個內(nèi)部結(jié)點 (方形框 )代表對某個屬性的一次檢測 。 信息熵 (Entropy) 對于任意一個隨機(jī)變量 X(比如奪冠球隊 )，它的熵定義為 ????XxxPxPXH )(l o g)()(變量的不確定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大 數(shù)據(jù)集的信息熵 設(shè)數(shù)據(jù)集 D中有 m個不同的類 C1, C2, C3, ..., Cm 設(shè) Ci,D是數(shù)據(jù)集 D中 Ci類的樣本的集合 , |D|和 |Ci,D|分別是 D和 Ci,D中的樣本個數(shù) 21( ) lo gmiiiInfo D p p??? ?其中 pi是 數(shù)據(jù)集 D中任意樣本屬于類 Ci的概率，用 估計 |||| ,DC Di數(shù)據(jù)集 D的信息熵 : 例 : 計算對下列數(shù)據(jù)集分類所需的信息熵 年齡 收入 學(xué)生 信用 買了電腦 30 高 否 一般 否 30 高 否 好 否 3040 高 否 一般 是 40 中等 否 一般 是 40 低 是 一般 是 40 低 是 好 否 3040 低 是 好 是 30 中 否 一般 否 30 低 是 一般 是 40 中 是 一般 是 30 中 是 好 是 3040 中 否 好 是 3040 高 是 一般 是 40 中 否 好 否 22()5 5 9 9l o g l o g1 4 1 4 1 4 1 40 . 9 4 0In fo D? ? ??|D|=14 |C1,D|=5 |C2,D|=9 使用熵衡量數(shù)據(jù)純度 假設(shè)有一個數(shù)據(jù)集合 D，其中只有兩個類，一個是正例類，一個是負(fù)例類 計算 D中正例類和負(fù)例類在三種不同的組分下熵的變化情況。這正是決策樹學(xué)習(xí)中 需要的。ve Bayes CART 改進(jìn) 1：信息增益的問題 假設(shè)按屬性 A 劃分 D 中的樣本，且屬性 A 根據(jù)訓(xùn)練數(shù)據(jù)的觀測具有 v 個不同取值{ a1, a2, ..., aj , ..., av }。 例如， 不玩 () 表示 到達(dá)“不玩”節(jié)點，其中 不屬于“不玩” 改進(jìn) 3： 分類過程 濕度 玩 () 不玩 () =75 75 天氣 晴 (天氣 =晴，溫度 =90， 濕度 =缺失 ...) 對于任一實例， 濕度 =75 的可能性是 ( + )， 濕度 75 的可能性是 ( + ) 當(dāng)濕度 =75 時， 分類為玩的可能性 = 100% 分類為不玩的可能性 = 0 當(dāng)濕度 75 時， 分類為玩的可能性 = 分類為不玩的可能性 = 3/=88% 最終分類的概率分布為： 玩 = 100% + 12% = 44% 不玩 = 88% = 56% 改進(jìn) 4：學(xué)習(xí)過程中的過度擬合 ? 上述的 決策樹算法 增長樹的每一個分支的 深度 ， 直到恰好能對訓(xùn)練樣例比較 完美地分類 。 改進(jìn) 4：預(yù)剪枝 { , }?age youthsenior??student ?cre it fair?yes yes no 剪枝處理 { }?ine medium?yes no 4 5 3 1 1 no 否 否 否 否 是 是 是 是 最直接的方法： 事先限定樹的最大生長高度 如果設(shè)為 3，則如圖剪枝 改進(jìn) 4：后剪枝 訓(xùn)練過程 中允許對數(shù)據(jù)的過度擬合，然后再利用 測試集 對樹進(jìn)行修剪 樹葉用被替換的子樹最頻繁的類標(biāo)號 { , }?age youthsenior??student ?cre it fair?yes yes no { }?ine medium?yes no 4 1 3 1 1 no ?credit fair?2 {}ine highyes/no 2 NO 是 是 是 是 是 是 否 否 否 否 否 否 改進(jìn) 4：后剪枝 在測試集上 定義損失函數(shù) C，我們的目標(biāo)是通過剪枝使得 在測試集上 C的值下降。 21( ) 1miiG in i D p??? ?其中， 是 中樣本屬于 類的概率，并用 估計。最大的分類 可以達(dá)到 100%的準(zhǔn)確，最大的回歸樹殘差為 0。 歸納對于認(rèn)識的發(fā)展和完善具有重要的意義。歸納可分為自 頂向下，自底向上和雙向搜索三種方式。 F的每一個逼近都 叫做一個假設(shè)。概念學(xué)習(xí)也可以看作是一 個搜索問題的過程。若沒有更多的信息，只能假定對于未見實例最好的假設(shè)就是 訓(xùn)練數(shù)據(jù)最佳擬合的假設(shè)。 1988年 ， Utgoff 在 ID4基礎(chǔ)上提出了 ID5學(xué)習(xí)算法 ， 進(jìn)一步提高了效率 。 ? 決策樹學(xué)習(xí)算法的最大優(yōu)點是 ， 它可以自學(xué)習(xí) 。如果判定是二元的 ， 那么構(gòu)造的將是一棵二叉樹 ， 在樹中每回答一個問題就降到樹的下一層 ， 這類樹一般稱為 CART（ Classification And Regression Tree） 。 本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進(jìn)行分類的過程 。他們需要更多的數(shù)據(jù)準(zhǔn)備階段：如缺失值的處理、啞變量編碼。 在用于預(yù)測時 ， 重要的變量會漂浮到樹的頂端 ， 這種方式產(chǎn)生的一個有用的結(jié)果是使得我們很容易就能發(fā)現(xiàn)哪些解釋變量最勝任預(yù)測工作 。 ? 決策樹方法之所以經(jīng)常被選用是因為它能理順一些可以理解的規(guī)則 。 ? 設(shè)計分類原則 ， 即數(shù)據(jù)的哪些屬性可以被用來分類 ， 以及如何將該屬性量化 。 節(jié)點用于存貯信息或知識 ， 分枝用于連接各個節(jié)點 。 決策樹的基本原理 ? 決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法 。 ? 從一類無序 、 無規(guī)則的事物 （ 概念 ） 中推理出決策樹表示的分類規(guī)則 。這些計數(shù)存儲在混同矩陣（ Confusion Matrix）的表格中，二元 分類問題混淆矩陣如下： 實際 的類 類 1 f11 類 0 f01 f10 f00 類 1 類 0 預(yù)測的類 準(zhǔn)確率 =正確的預(yù)測數(shù) /預(yù)測總數(shù) =（ f11+f00） /(f11+f01+f10+f00) 差錯率 =錯誤的預(yù)測數(shù) /預(yù)測總數(shù) =（ f10+f01） /(f11+f01+f10+f00) 歸納學(xué)習(xí)假設(shè) 機(jī)器學(xué)習(xí)的任務(wù)是在整個實例集合 X上確定與目標(biāo)概念 c相同 的假設(shè) 。在表示中 通常需要修改參數(shù)（如 a, b）。 自頂向下法對可能的一般性描述集進(jìn)行搜索，試圖找到一些 滿足一定要求的最優(yōu)的描述。 銳角三角形內(nèi)角和等于 180度； 鈍角三角形內(nèi)角和等于 180度； 三角形內(nèi)角和 直角三角形內(nèi)角和等于 180度； 等于 180度 已知三角形 ABC， A角等于 76度， B角等于 89度，則其 C角等于 15度 歸納學(xué)習(xí)由于依賴于檢驗數(shù)據(jù)，因此又稱為檢驗學(xué)習(xí)。 歸納是從特殊到一般的過程。 同樣 ， 太小的決策樹僅含有很少的分支 ， 會導(dǎo)致欠擬合 。 3. 重復(fù)上述過程，直到所有的非葉節(jié)點 (除了根節(jié)點 )都被嘗試了。決策樹作出這樣的判 斷是因為只有一個訓(xùn)練樣例具有 這些特點（鷹，恒溫，不冬眠） 被劃分為非哺乳動物。 2()1 1 1 ( l o g )1 4 1 10P I DI n f o D???對屬性 PID劃分得到的 信息增益最大 ，顯然，這種 劃分對分類沒有用處 。 jDD InfoA(D)越小， 表示劃分的純度越高 信息增益 ( ) ( ) ( )AGainA InfoD Info D??選擇具有最高信息增益 Gain(A) 的屬性 A作為分裂屬性 按照能做 “ 最佳分類 ” 的屬性 A劃分， 使完成樣本分類需要的信息量最小 max ()G a in Am in ()AIn fo D確定第一次分裂的屬性：按 年齡 劃分 年齡 收入 學(xué)生 信用 買了電腦 30 高 否 一般 否 30 高 否 好 否 3040 高 否 一般 是 40 中等 否 一般 是 40 低 是 一般 是 40 低 是 好 否 3040 低 是 好 是 30 中 否 一般 否 30 低 是 一般 是 40 中 是 一般 是 30 中 是 好 是 3040 中 否 好 是 3040 高 是 一般 是 40 中 否 好 否 年齡 30的有 5個 , 其中 3個為“否” 年齡 3040的有 4個 , 其中 0個為“否” 年齡 40的有 5個 , 其中 2個為“否” 6 )53log5352log52(145)40log4044log44(144)52log5253log53(145?????????? Info年齡 (D) Gain(年齡 ) = Info(D) Info年齡 (D) = = 確定第一次分裂的屬性：按收入劃分 年齡 收入 學(xué)生 信用 買了電腦 30 高 否