【正文】 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 23步計算年齡的熵 年齡共分三個組： 青年、中年、老年 老年買與不買比例為 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) = 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(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步計算年齡的熵 年齡共分三個組： 青年、中年、老年 所占比例 青年組 384/1025= 中年組 256/1024= 老年組 384/1024= 計算年齡的平均信息期望 E（年齡） =*+ *0+ * = G（年齡信息增益） = = （ 1） 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(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步計算收入的熵 收入共分三個組： 高、中、低 E（收入） = 收入信息增益 = = (2) 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(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步計算學(xué)生的熵 學(xué)生共分二個組： 學(xué)生、非學(xué)生 E（學(xué)生） = 年齡信息增益 = = （ 3） 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(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步計算信譽(yù)的熵 信譽(yù)分二個組： 良好，優(yōu)秀 E（信譽(yù)） = 信譽(yù)信息增益 = = （ 4） 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(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步計算選擇節(jié)點 年齡信息增益 = = （ 1） 收入信息增益 = = （ 2） 年齡信息增益 = = （ 3） 信譽(yù)信息增益 = = （ 4） 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 青 中 否 良 不買 64 青 低 是 良 買 64 青 中 是 優(yōu) 買 年齡 青年 中年 老年 買 / 不買 買 買 / 不買 葉子 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(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) = 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 青 中 否 良 不買 64 青 低 是 良 買 64 青 中 是 優(yōu) 買 如果選擇收入作為節(jié)點 分高、中、低 平均信息期望（加權(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= 注意 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(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) 良 買 不買 買 / 不買 買 葉子 葉子 葉子 決策樹分類規(guī)則提取 ? 決策樹所表示的分類知識可以被抽取出來并可用IFTHEN 分類規(guī)則形式加以表示。分別是年齡、 收入、學(xué)生、信譽(yù)。 信息增益的計算 設(shè) S是有 s個訓(xùn)練樣本數(shù)據(jù)的集合，類標(biāo)號屬性具有 m個不同值，定義 m個不同類 Ci（i=1,2,…,m ）， si是類 Ci中的樣本數(shù)，則對一個給定的訓(xùn)練樣本分類所需要的 期望信息為 ： ? ? ? ?????miiim ppsssI1221 l o g, ?其中 pi是任意樣本屬于 Ci的概率，可用 si/s來估計 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(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) 買 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計算機(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) 買 決策屬性“買計算機(jī)？”。 ?信息增益 是指劃分前后進(jìn)行正確預(yù)測所需的 信息量之差 。 ? 用信息增益這種 信息論 的理論方法，使得對一個對象分類所需要的期望測試數(shù)目達(dá)到最小，并確保找到一棵簡單的樹。 對輸入的記錄 ， 從根結(jié)點依次測試記錄的屬性值 ， 直到到達(dá)某個葉結(jié)點 ， 從而找到該記錄所在的類 。 這個過程實際上是一個從數(shù)據(jù)中獲取知識 ， 進(jìn)行機(jī)器學(xué)習(xí)的過程 。 ? 為了適應(yīng)處理大規(guī)模數(shù)據(jù)集的需要，后來又提出了若干改進(jìn)的算法，其中 SLIQ (supervised learning in quest)和 SPRINT (scalable parallelizable induction of decision trees)是比較有代表性的兩個算法。 收入 40000 高負(fù)債 工作時間 5年 是 否 是 否 “年收入大于￥ 40000”并且“高負(fù)債”的用戶被認(rèn)為是“高風(fēng)險”； “年收入小于￥ 40000”但“工作時間大于 5年”的申請，是“低風(fēng)險”； N Y Y N N Y 決策樹 buys_puter的決策樹示意 Age? Credit_rating? student? yes no yes yes no =30? 40 30~40 yes no fair excellent 決策樹 ? 決策樹（ decision tree） ? 1986年 Quinlan提出了著名的 ID3算法。樹的最頂層節(jié)點是根節(jié)點。它從一組無次序、無規(guī)則的元組中推理出決策樹表示形式的分