【正文】 ND 濕度 = 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)為止 。 2. 計(jì)算剪去節(jié)點(diǎn)前后的損失函數(shù)，如果剪去節(jié)點(diǎn)之后損失函數(shù)變小了，則說明該節(jié)點(diǎn)是可以剪去的，并將其剪去；如果發(fā)現(xiàn)損失函數(shù)并沒有減少，說明該節(jié)點(diǎn)不可剪去，則將樹還原成未剪去之前的狀態(tài)。 例如通過剪枝使 在測試集上 誤差率降低。 由 “ 完全生長 ” 的樹剪去子樹。 該例清楚表明，當(dāng)決策樹的葉節(jié) 點(diǎn)沒有足夠的代表性時(shí)，可能會(huì) 預(yù)測錯(cuò)誤。人和大象都不是 哺乳動(dòng)物。 ? 實(shí)際應(yīng)用中 ， 當(dāng)訓(xùn)練樣本中 有噪聲 或 訓(xùn)練樣例的數(shù)量太少以至于不能產(chǎn)生目標(biāo)函數(shù)的有代表性的采樣 時(shí) ， 該策略可能會(huì)遇到困難 ? 在以上情況發(fā)生時(shí) ， 這個(gè)簡單的算法產(chǎn)生的樹會(huì) 過度擬合訓(xùn)練樣例 (過度擬合 : Over fitting) ? 過度擬合產(chǎn)生的原因：訓(xùn)練樣本中 有噪聲 ， 訓(xùn)練樣例太小等 改進(jìn) 4：欠擬合、合適擬合、過擬合 欠擬合 合適擬合 過擬合 改進(jìn) 4：過度擬合 ? 訓(xùn)練樣本中噪聲導(dǎo)致的過度擬合 錯(cuò)誤的類別值 /類標(biāo)簽 ， 屬性值等 ? 訓(xùn)練樣本中缺乏代表性樣本所導(dǎo)致的過度擬合 根據(jù)少量訓(xùn)練記錄作出的分類決策模型容易受過度擬合的影響 。 檢查每個(gè)可能分裂點(diǎn)，取能使得 信息增益最大的分裂點(diǎn) ，將 D分裂成 D1: A = split_point 和 D2: A split_point(一個(gè)分裂點(diǎn)，二分法，二叉樹 ) 5 6 10 8 =8 8 ，而是直接使用一對值中較小的值作為可能的分裂點(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è)分支 ？ ? 分類過程 （ 測試過程或者工作過程 ） 待分類實(shí)例有缺失值 ， 如何測試該實(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 有 不玩晴 85 無 不玩晴 95 無 不玩晴 70 無 玩缺失 90 有 玩多云 78 無 玩多云 65 有 玩多云 75 無 玩雨 80 有 不玩雨 70 有 不玩雨 80 無 玩雨 80 無 玩雨 96 無 玩晴 多云 雨 缺失 GainRatio(天氣 ) = Gain(天氣 ) / SplitInfo天氣 (D) = / 改進(jìn) 3： 建樹過程（學(xué)習(xí)過程） 分裂時(shí)，將屬性值缺失的實(shí)例分配給所有分支，但是帶一個(gè)權(quán)重 濕度 有風(fēng) 玩？ 權(quán)重 70 90 85 95 70 90 有 有 無 無 無 有 玩 不玩 不玩 不玩 玩 玩 1 1 1 1 1 5/13 濕度 有風(fēng) 玩？ 權(quán)重 90 78 65 75 有 無 有 無 玩 玩 玩 玩 3/13 1 1 1 T1: (天氣 =晴 ) T1: (天氣 =多云 ) 濕度 有風(fēng) 玩？ 權(quán)重 80 70 80 80 96 90 有 有 無 無 無 有 不玩 不玩 玩 玩 玩 玩 1 1 1 1 1 5/13 T1: (天氣 =雨 ) 本例 14個(gè)實(shí)例中共 13個(gè)實(shí)例天氣屬性值未缺失： 其中 5個(gè)實(shí)例的天氣屬性為“晴”， 3個(gè)實(shí)例的天氣屬性為“多云”， 5個(gè)實(shí)例的天氣屬性為“雨” 本例 14個(gè)實(shí)例中共 1個(gè)實(shí)例天氣屬性值缺失，因此估算出天氣屬性值缺失的第 6個(gè)實(shí)例： 天氣是晴的概率是 5/13，天氣是多云的概率是 3/13，天氣是雨的概率是 5/13 改進(jìn) 3： 建樹過程（學(xué)習(xí)過程） 濕度 有風(fēng) 玩？ 權(quán)重 70 90 85 95 70 90 有 有 無 無 無 有 玩 不玩 不玩 不玩 玩 玩 1 1 1 1 1 5/13= T1: (天氣 =晴 ) 濕度 =75 2玩， 0不玩 濕度 75 5/13玩， 3不玩 濕度 玩 () 不玩 () =75 75 葉節(jié)點(diǎn)以 (N/E) 的形式定義， 其中 N 為到達(dá)該葉節(jié)點(diǎn)的實(shí)例數(shù)， E 為其中屬于其它分類的實(shí)例數(shù)。 改進(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) 對于 連續(xù)值屬性 ，按屬性值大小從小到大排序，取每對 相鄰值的中點(diǎn) 作為 可能的分裂點(diǎn) split_point。對 PID的分裂將產(chǎn)生大量劃分（與樣本個(gè)數(shù)一樣多），每個(gè)分類只包含一個(gè)樣本，且每個(gè)劃分都是純的。 如果 A 是 離散值 ，可依屬性 A 將 D 劃分為 v 個(gè)子集 { D1, D2, ..., Dj , ..., Dv } 其中， Dj為 D中的樣本子集，它們在 A上具有屬性值 aj 這些劃分將對應(yīng)于從該節(jié)點(diǎn) A出來的分支。 決策樹的基本原理 分類決策樹 C l a s s i f i c a t i o n T r e eX 1 3 8 . 5X 1 0 5 1 . 5X 1 0 . 59 ( 9 9 % )1 ( 7 8 % )X 1 0 4 0 . 57 ( 9 6 % )X 1 . 5X 1 . 51 ( 9 5 % )X 1 0 1 7 . 5 X 1 0 7 1 . 51 ( 8 0 % )1 ( 5 6 % )7 ( 9 1 % ) 7 ( 7 3 % )X 1 0 6 19 ( 8 7 % )1 ( 6 4 % )y e s noA decision tree is so called because the predictive model can be represented in a treelike structure. the target is categorical, the model is a called a classification tree. 分類樹采用的標(biāo)準(zhǔn)： ◆ 分類錯(cuò)誤率 : ◆ Gini 指數(shù) : ◆ 信息熵 : ?1 mkp?1? ?(1 )K m k m kkpp???1? ?lo gK mk mkkpp???主要內(nèi)容