【正文】 馬 ? 構(gòu)造一棵決策樹要解決四個(gè)問題： ? 收集待分類的數(shù)據(jù) ， 這些數(shù)據(jù)的所有屬性應(yīng)該是完全標(biāo)注的 。 根結(jié)點(diǎn) 個(gè)子大 可能是松鼠 可能是老鼠 可能是大象 在水里 會(huì)吱吱叫 鼻子長 脖子長 個(gè)子小 不會(huì)吱吱叫 鼻子短 脖子短 可能是長頸鹿 在陸地上 可能是犀牛 可能是河馬 ? 可以看到 ， 一個(gè)決策樹的內(nèi)部結(jié)點(diǎn)包含學(xué)習(xí)的實(shí)例 ， 每層分枝代表了實(shí)例的一個(gè)屬性的可能取值 ， 葉節(jié)點(diǎn)是最終劃分成的類 。 決策樹的基本原理 ? 樹是由節(jié)點(diǎn)和分枝組成的層次數(shù)據(jù)結(jié)構(gòu) 。 整個(gè)決策樹就對(duì)應(yīng)著一組析取的規(guī)則 。 ? 其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹 ， 到葉子節(jié)點(diǎn)處的熵值為零 ， 此時(shí)每個(gè)葉節(jié)點(diǎn)中的實(shí)例都屬于同一類 。 Schlimmer 和 Fisher 于 1986年對(duì) ID3進(jìn)行改造 ， 在每個(gè)可能的決策樹節(jié)點(diǎn)創(chuàng)建緩沖區(qū) ， 使決策樹可以遞增式生成 ， 得到 ID4算法 。 })1,0{:( ?xhh決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 4） ? 決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí) 。由于對(duì) c僅有的信息只是它在訓(xùn)練樣例上 的值，因此歸納學(xué)習(xí)最多只能保證輸出的假設(shè)能與訓(xùn)練樣例相擬 合。 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 3） 分類模型的性能根據(jù)模型正確和錯(cuò)誤預(yù)測也可以根據(jù)的檢驗(yàn)記錄計(jì)數(shù) 進(jìn)行評(píng)估。 ??????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è)搜索。通過 調(diào)整假設(shè)的表示，學(xué)習(xí)過程將產(chǎn)生出假設(shè)的不同變形。 學(xué)習(xí)過程將產(chǎn)生對(duì)目標(biāo)函數(shù) f的不同逼近。直 到最終的一般化描述。 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (3) 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (4) 歸納過程就是在描述空間中進(jìn)行搜索的過程。這種一般性 描述能夠解釋給定的輸入數(shù)據(jù)，并可以用來預(yù)測新的數(shù)據(jù)。即從特殊事實(shí)到普遍性規(guī)律的結(jié)論。 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (1) 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法。 最大樹 決策樹能長到每個(gè)葉子都是純的。 因此建立的樹模型不能很好的推廣到總體中的其他樣本數(shù)據(jù) 。 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ù)測 ) ? 使用 GINI指標(biāo)來選擇分裂屬性 ? 使用二元切分 (將生成二叉樹 ) ? 基于代價(jià) 復(fù)雜度剪枝 Gini指標(biāo) 指標(biāo)用來度量數(shù)據(jù)劃分或者數(shù)據(jù)集的不純度 。 2. 計(jì)算剪去節(jié)點(diǎn)前后的損失函數(shù)，如果剪去節(jié)點(diǎn)之后損失函數(shù)變小了，則說明該節(jié)點(diǎn)是可以剪去的，并將其剪去；如果發(fā)現(xiàn)損失函數(shù)并沒有減少，說明該節(jié)點(diǎn)不可剪去，則將樹還原成未剪去之前的狀態(tài)。 由 “ 完全生長 ” 的樹剪去子樹。人和大象都不是 哺乳動(dòng)物。 檢查每個(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è)分支 ？ ? 分類過程 （ 測試過程或者工作過程 ） 待分類實(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ù)。對(duì) PID的分裂將產(chǎn)生大量劃分（與樣本個(gè)數(shù)一樣多），每個(gè)分類只包含一個(gè)樣本，且每個(gè)劃分都是純的。 決策樹的基本原理 分類決策樹 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)容 ? 什么是決策樹 ? ID3算法 ? 算法改進(jìn) ? CART算法