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