【正文】 =I(256， 0) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) =0 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 23步計(jì)算年齡的熵 年齡共分三個(gè)組： 青年、中年、老年 老年買與不買比例為 125/127 S1(買 )=125 S2（不買） =127 S=S1+S2=252 P1=125/252 P2=127/252 I(S1,S2)=I(125， 127) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) = 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 24步計(jì)算年齡的熵 年齡共分三個(gè)組： 青年、中年、老年 所占比例 青年組 384/1025= 中年組 256/1024= 老年組 384/1024= 計(jì)算年齡的平均信息期望 E（年齡） =*+ *0+ * = G（年齡信息增益） = = （ 1） 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 3步計(jì)算收入的熵 收入共分三個(gè)組： 高、中、低 E（收入） = 收入信息增益 = = (2) 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 4步計(jì)算學(xué)生的熵 學(xué)生共分二個(gè)組： 學(xué)生、非學(xué)生 E（學(xué)生） = 年齡信息增益 = = （ 3） 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 5步計(jì)算信譽(yù)的熵 信譽(yù)分二個(gè)組： 良好，優(yōu)秀 E（信譽(yù)） = 信譽(yù)信息增益 = = （ 4） 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 6步計(jì)算選擇節(jié)點(diǎn) 年齡信息增益 = = （ 1） 收入信息增益 = = （ 2） 年齡信息增益 = = （ 3） 信譽(yù)信息增益 = = （ 4） 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 青 中 否 良 不買 64 青 低 是 良 買 64 青 中 是 優(yōu) 買 年齡 青年 中年 老年 買 / 不買 買 買 / 不買 葉子 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 青 中 否 良 不買 64 青 低 是 良 買 64 青 中 是 優(yōu) 買 青年買與不買比例為 128/256 S1(買 )=128 S2（不買） = 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) = 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 青 中 否 良 不買 64 青 低 是 良 買 64 青 中 是 優(yōu) 買 如果選擇收入作為節(jié)點(diǎn) 分高、中、低 平均信息期望（加權(quán)總和）： E(收入） = * 0 + * + * 0 = Gain(收入 ) = I(128, 256) E(收入 )= – = I(0,128)=0 比例 : 128/384= I(64,128)= 比例 : 192/384= I(64,0)=0 比例 : 64/384= 注意 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 年齡 青年 中年 老年 學(xué)生 買 信譽(yù) 葉子 否 是 優(yōu) 良 買 不買 買 / 不買 買 葉子 葉子 葉子 決策樹算法 第 6章 決策樹 ID3 決策樹建立算法 1 決定分類屬性； 2 對目前的數(shù)據(jù)表，建立一個(gè)節(jié)點(diǎn) N 3 如果數(shù)據(jù)庫中的數(shù)據(jù)都屬于同一個(gè)類， N就是樹葉，在樹葉上 標(biāo)出所屬的類 4 如果數(shù)據(jù)表中沒有其他屬性可以考慮，則 N也是樹葉，按照少 數(shù)服從多數(shù)的原則在樹葉上標(biāo)出所屬類別 5 否則，根據(jù)平均信息期望值 E或 GAIN值選出一個(gè)最佳屬性作 為節(jié)點(diǎn) N的測試屬性 6 節(jié)點(diǎn)屬性選定后，對于該屬性中的每個(gè)值： 從 N生成一個(gè)分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形 成分支節(jié)點(diǎn)的數(shù)據(jù)表，在表中刪除節(jié)點(diǎn)屬性那一欄 如果分支數(shù)據(jù)表非空，則運(yùn)用以上算法從該節(jié)點(diǎn)建立子樹。分別是年齡、 收入、學(xué)生、信譽(yù)。 第 6章 決策樹 ID3 –信息量大小的度量 決策樹算法 Gain（ S， A）是屬性 A在集合 S上的信息增益 Gain（ S， A） = Entropy（ S） Entropy（ S， A） 公式 3 Gain（ S， A）越大，說明選擇測試屬性對分類提供的信息越多 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63