【正文】 6號(hào)中 。 當(dāng) D中 正反例所占比例相同時(shí)，熵取最大值 。 本質(zhì)上決策樹是通過一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過程 。 改進(jìn) 1：信息增益率 分裂信息 (split information)將 信息增益規(guī)范化 ||||l o g||||)(1 DDDDDS p l i t I n f o jvjjA ????該值表示數(shù)據(jù)集 D按屬性 A分裂的 v個(gè)劃分產(chǎn)生的信息 )()()(DSpl i t I nf oAG ai nAG ai nR at i oA?選擇具有 最大信息增益率 的屬性作為 分裂屬性 改進(jìn) 1：信息增益率 年齡 收入 學(xué)生 信用 買了電腦 30 高 否 一般 否 30 高 否 好 否 3040 高 否 一般 是 40 中 否 一般 是 40 低 是 一般 是 40 低 是 好 否 3040 低 是 好 是 30 中 否 一般 否 30 低 是 一般 是 40 中 是 一般 是 30 中 是 好 是 3040 中 否 好 是 3040 高 是 一般 是 40 中 否 好 否 Info(D) = Info收入 (D) = Gain(收入 ) = 高收入的有 4個(gè) 中等收入的有 6個(gè) 低收入的有 4個(gè) SplitInfo收入 (D) = 4/14 * log4/14 6/14 * log6/14 4/14 * log4/14 = GainRatio(收入 ) = Gain(收入 ) / SplitInfo收入 (D) = / = 改進(jìn) 2：連續(xù)值屬性與分裂點(diǎn) 對(duì)于 連續(xù)值屬性 ，按屬性值大小從小到大排序，取每對(duì) 相鄰值的中點(diǎn) 作為 可能的分裂點(diǎn) split_point。 該例清楚表明，當(dāng)決策樹的葉節(jié) 點(diǎn)沒有足夠的代表性時(shí)，可能會(huì) 預(yù)測(cè)錯(cuò)誤。 從決策樹導(dǎo)出產(chǎn)生式規(guī)則 ? 大型決策樹可讀性較低 ， 可通過從決策樹導(dǎo)出產(chǎn)生式規(guī)則以提高可讀性 ? 把從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑中遇到的所有測(cè)試條件聯(lián)合起來 ， 便可建立相對(duì)應(yīng)的規(guī)則集 從決策樹導(dǎo)出產(chǎn)生式規(guī)則 ? 但這樣的規(guī)則會(huì)導(dǎo)致某些不必要的復(fù)雜性 ? 可用類似的方法對(duì)規(guī)則集進(jìn)行剪枝 ? 對(duì)于某一規(guī)則 ， 將它的單個(gè)條件暫時(shí)去除 ， 在測(cè)試集上 估計(jì)誤差率 ， 并與原規(guī)則的誤差率進(jìn)行比較 ， 若新規(guī)則的結(jié)果較好 ， 則刪除這個(gè)條件 IF 天氣 =晴 AND 濕度 = 75 THEN 玩 IF 天氣 =晴 THEN 玩 主要內(nèi)容 ? 什么是決策樹 ? ID3算法 ? 算法改進(jìn) ? CART算法 CART算法 ? 分 類 回 歸 樹 （ CART:Classification and Regression Tree） ? 其特點(diǎn)是在計(jì)算過程中充分利用二分支樹的結(jié)構(gòu) （ Bianry Treestructured） ， 即根節(jié)點(diǎn)包含所有樣本 ， 在一定的分裂規(guī)則下根節(jié)點(diǎn)被分裂為兩個(gè)子節(jié)點(diǎn) ， 這個(gè)過程又在子節(jié)點(diǎn)上重復(fù)進(jìn)行 ， 直至不可再分 ， 成為葉節(jié)點(diǎn)為止 。 一個(gè)好的樹模型有低的偏倚和低的方差 ， 模型的復(fù)雜性往往在偏倚和方差之間做一個(gè)折中 ， 因此要對(duì)樹進(jìn)行剪枝 。歸納推理從若干個(gè)事實(shí)中表 征出的特征、特性和屬性中，通過比較、總結(jié)、概括而得出一 個(gè)規(guī)律性的結(jié)論。歸納學(xué)習(xí)存在一個(gè)基本的假設(shè)： 任一假設(shè)如果能夠在足夠大的訓(xùn)練樣本集中很好的逼近目標(biāo)函數(shù)，則它也能在未見樣本中很好地逼近目標(biāo)函數(shù)。 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 1） 從特殊的訓(xùn)練樣例中歸納出一般函數(shù)是機(jī)器學(xué)習(xí)的中心問題； 從訓(xùn)練樣例中進(jìn)行學(xué)習(xí)通常被視為歸納推理。 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 2） 從這些不同的變形中選擇最佳的假設(shè)（或者說權(quán)值集合）。一般 H表示所有可能假設(shè)。 ? 概念分類學(xué)習(xí)算法：來源于 Hunt,Marin和 Stone 于 1966年研制的 CLS學(xué)習(xí)系統(tǒng) ， 用于學(xué)習(xí)單個(gè)概念 。 ? 決策樹的每一層節(jié)點(diǎn)依照某一屬性值向下分為子節(jié)點(diǎn) ， 待分類的實(shí)例在每一節(jié)點(diǎn)處與該節(jié)點(diǎn)相關(guān)的屬性值進(jìn)行比較 ，根據(jù)不同的比較結(jié)果向相應(yīng)的子節(jié)點(diǎn)擴(kuò)展 ， 這一過程在到達(dá)決策樹的葉節(jié)點(diǎn)時(shí)結(jié)束 ， 此時(shí)得到結(jié)論 。 樹是圖的一個(gè)特例 ， 圖是更一般的數(shù)學(xué)結(jié)構(gòu) ，如貝葉斯網(wǎng)絡(luò) 。 ? 分類原則的選擇 ， 即在眾多分類準(zhǔn)則中 ， 每一步選擇哪一準(zhǔn)則使最終的樹更令人滿意 。 一些樹模型作為最后模型并不合適。 然而這些能力有時(shí)有些夸大， 確實(shí)對(duì)于某一個(gè)已經(jīng)分過類的記錄來說 ， 為了產(chǎn)生這種分類 ， 很簡單只要沿著從根到葉的路徑走就可以了 ， 然而一個(gè)較復(fù)雜的決策樹可能包含成千上萬的葉 ， 這么一棵樹從整體上很難提供有關(guān)問題可以理解的信息 。 ? 決策樹 所建立的算法把最勝任的拆分字段變量放在樹的根節(jié)點(diǎn) （ 并且同一個(gè)字段在樹的其他層也可以出現(xiàn) ） 。標(biāo)準(zhǔn)的回歸模型具有線性和可加性。 ? 通用的決策樹分裂目標(biāo)是整棵樹的熵總量最小 ， 每一步分裂時(shí) ， 選擇使熵減小最大的準(zhǔn)則 ， 這種方案使最具有分類潛力的準(zhǔn)則最先被提取出來 ? 它首先對(duì)數(shù)據(jù)進(jìn)行處理 ， 利用歸納法生成可讀的規(guī)則和決策樹 ， 然后使用決策對(duì)新數(shù)據(jù)進(jìn)行分析 。 根結(jié)點(diǎn) 個(gè)子大 可能是松鼠 可能是老鼠 可能是大象 在水里 會(huì)吱吱叫 鼻子長 脖子長 個(gè)子小 不會(huì)吱吱叫 鼻子短 脖子短 可能是長頸鹿 在陸地上 可能是犀牛 可能是河馬 ? 可以看到 ， 一個(gè)決策樹的內(nèi)部結(jié)點(diǎn)包含學(xué)習(xí)的實(shí)例 ， 每層分枝代表了實(shí)例的一個(gè)屬性的可能取值 ， 葉節(jié)點(diǎn)是最終劃分成的類 。 整個(gè)決策樹就對(duì)應(yīng)著一組析取的規(guī)則 。 Schlimmer 和 Fisher 于 1986年對(duì) ID3進(jìn)行改造 ， 在每個(gè)可能的決策樹節(jié)點(diǎn)創(chuàng)建緩沖區(qū) ， 使決策樹可以遞增式生成 ， 得到 ID4算法 。由于對(duì) c僅有的信息只是它在訓(xùn)練樣例上 的值，因此歸納學(xué)習(xí)最多只能保證輸出的假設(shè)能與訓(xùn)練樣例相擬 合。 ??????a m p l e st r a i n i n g e xbV t r a i nbbVbV tr a inE)(,2^ ))()(( 學(xué)習(xí)是在假設(shè)空間上的一個(gè)搜索。 學(xué)習(xí)過程將產(chǎn)生對(duì)目標(biāo)函數(shù) f的不同逼近。 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (3) 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (4) 歸納過程就是在描述空間中進(jìn)行搜索的過程。即從特殊事實(shí)到普遍性規(guī)律的結(jié)論。 最大樹 決策樹能長到每個(gè)葉子都是純的。 Boston Housing Data Leaves = Boolean Rules（布爾規(guī)則） Leaf 1 2 3 4 5 6 7 8 RM [, ) [, ) ? ? NOX .51 [.51, .63) [.63, .67) .67 ?.67 .66 .66 ?.66 Predicted MEDV 22 19 27 27 14 33 46 16 If RM ? {values} NOX ? {values}, then MEDV=value CART算法 ? CART: Classification And Regression Trees ? 可用于分類和回歸 (數(shù)值預(yù)測(cè) ) ? 使用 GINI指標(biāo)來選擇分裂屬性 ? 使用二元切分 (將生成二叉樹 ) ? 基于代價(jià) 復(fù)雜度剪枝 Gini指標(biāo) 指標(biāo)用來度量數(shù)據(jù)劃分或者數(shù)據(jù)集的不純度 。 由 “ 完全生長 ” 的樹剪去子樹。 檢查每個(gè)可能分裂點(diǎn)，取能使得 信息增益最大的分裂點(diǎn) ，將 D分裂成 D1: A = split_point 和 D2: A split_point(一個(gè)分裂點(diǎn)，二分法，二叉樹 ) 5 6 10 8 =8 8 ，而是直接使用一對(duì)值中較小的值作為可能的分裂點(diǎn)，如本例中將使用 5, 6作為可能分裂點(diǎn) 多個(gè)分裂點(diǎn)？多分法，多叉決策樹 改進(jìn) 3：缺失值的處理 在某些情況下，可供使用的數(shù)據(jù)可能缺少某些屬性的值，例如 一種簡單的辦法是賦予它該屬性最常見的值，例如將“晴”或“雨”賦予第 6個(gè)實(shí)例的天氣屬性 一種更復(fù)雜的策略是為 A的每個(gè)可能值賦予一個(gè)概率 天氣 濕度 有雨 ？ 去玩 ？晴 70 有 玩晴 90 有 不玩晴 85 無 不玩晴 95 無 不玩晴 70 無 玩多云 78 無 玩多云 65 有 玩多云 75 無 玩雨 80 有 不玩雨 70 有 不玩雨 80 無 玩雨 80 無 玩雨 96 無 玩缺失 90 有 玩改進(jìn) 3：缺失值的處理 ? 建樹過程 （ 學(xué)習(xí)過程 ） 選定訓(xùn)練樣本實(shí)例有缺失值 ， 如何知道要將其分配到哪個(gè)分支 ？ ? 分類過程 （ 測(cè)試過程或者工作過程 ） 待分類實(shí)例有缺失值 ， 如何測(cè)試該實(shí)例屬于哪個(gè)分支 ？ 天氣 晴 多云 雨 (天氣 =缺失 ，溫度 =72，濕度 =90...) 改進(jìn) 3： 建樹過程（學(xué)習(xí)過程） Gain(A) = F ( Info(D) – InfoA(D)) 其中 F 為屬性值未缺失的實(shí)例所占比例； 計(jì)算 Info(D) 和 InfoA(D) 時(shí)忽略屬性值缺失的實(shí)例 Info(D) = 8/13 log(8/13) 5/13 log(5/13) = bits Info天氣 (D) = 5/13 (2/5log(2/5) 3/5 log(3/5)) + 3/13 (3/3log(3/3) 0/3 log(0/3)) + 5/13 (3/5log(3/5) 2/5 log(2/5)) = bits Gain(天氣 ) = 13/14 ( ) = bits 天氣 濕度 有雨 ？ 去玩 ？晴 70 有 玩晴 90 有 不玩晴 85 無 不玩晴 95 無 不玩晴 70 無 玩多云 78 無 玩多云 65 有 玩多云 75 無 玩雨 80 有 不玩雨 70 有 不玩雨 80 無 玩雨 80 無 玩雨 96 無 玩缺失 90 有 玩改進(jìn) 3： 建樹過程（學(xué)習(xí)過程） 計(jì)算 SplitInfo 時(shí)，將缺失的屬性值當(dāng)作一個(gè)正常值進(jìn)行計(jì)算， 本例中，當(dāng)作天氣有四個(gè)值，分別是晴 , 多云 , 雨 , ?，再計(jì)算其 SplitInfo SplitInfo天氣 (D) = 5/14 log(5/14) 3/14 log(3/14) 5/14 log(5/14) 1/14 log(1/14) = bits 天氣 濕度 有雨？ 去玩？晴 70 有 玩晴 90 有 不玩晴