【文章內(nèi)容簡介】 T (scalable parallelizable induction of decision trees)是比較有代表性的兩個(gè)算法。 決策樹的步驟 ?使用決策樹進(jìn)行分類分為兩步： ?第 1步：利用訓(xùn)練集 建立 并精化一棵 決策樹 ， 建立決策樹模型 。 這個(gè)過程實(shí)際上是一個(gè)從數(shù)據(jù)中獲取知識(shí) ， 進(jìn)行機(jī)器學(xué)習(xí)的過程 。 ?第 2步：利用生成完畢的決策樹對(duì)輸入數(shù)據(jù)進(jìn)行 分類 。 對(duì)輸入的記錄 ， 從根結(jié)點(diǎn)依次測試記錄的屬性值 ， 直到到達(dá)某個(gè)葉結(jié)點(diǎn) ， 從而找到該記錄所在的類 。 決策樹 ?算法遞歸執(zhí)行的終止條件（停止分支的條件） ? 對(duì)于給定的節(jié)點(diǎn)， 所有的例子都屬于同一個(gè)類 ? 雖然對(duì)于某一個(gè)節(jié)點(diǎn)當(dāng)前的例子不屬于同一個(gè)類，但是已經(jīng) 沒有屬性 可用來選擇繼續(xù)進(jìn)行分支處理 分裂屬性選擇 ?選擇屬性的方法 ? 選擇具有 最大信息增益 的屬性作為當(dāng)前節(jié)點(diǎn)的測試屬性 ? 該屬性使得對(duì)結(jié)果劃分中的樣本分類所需的 信息量最小 ，并反映劃分的最小隨機(jī)性。 ? 用信息增益這種 信息論 的理論方法，使得對(duì)一個(gè)對(duì)象分類所需要的期望測試數(shù)目達(dá)到最小，并確保找到一棵簡單的樹。 分裂屬性選擇 ?怎樣計(jì)算信息增益（ information gain） ?信息增益被定義為 原始分割的熵 與劃分以后各分割的熵 累加得到的總熵之間的差。 ?信息增益 是指劃分前后進(jìn)行正確預(yù)測所需的 信息量之差 。 ?選擇具有 最高信息增益 的屬性作為當(dāng)前節(jié)點(diǎn)的測試屬性。 信息增益的計(jì)算 設(shè) S是有 s個(gè)訓(xùn)練樣本數(shù)據(jù)的集合，類標(biāo)號(hào)屬性具有 m個(gè)不同值，定義 m個(gè)不同類 Ci（i=1,2,…,m ）， si是類 Ci中的樣本數(shù)，則對(duì)一個(gè)給定的訓(xùn)練樣本分類所需要的 期望信息為 ： ? ? ? ?????miiim ppsssI1221 l og, ?其中 pi是任意樣本屬于 Ci的概率，可用 si/s來估計(jì) 決策樹算法 計(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) 買 決策樹算法 計(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) 買 決策屬性“買計(jì)算機(jī)？”。該屬性分 兩類：買 /不買 S1(買 )=641 S2（不買） = 383 S=S1+S2=1024 P1=641/1024= P2=383/1024= I(S1,S2)=I(641,383) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) = 第 1步計(jì)算決策屬性的熵 決策樹算法 計(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) 買 第 2步計(jì)算條件屬性的熵 條件屬性共有 4個(gè)。分別是年齡、 收入、學(xué)生、信譽(yù)。 分別計(jì)算不同屬性的信息增益。 決策樹算法 計(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) 買 第 21步計(jì)算年齡的熵 年齡共分三個(gè)組： 青年、中年、老年 青年買與不買比例為 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) = 決策樹算法 計(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) 買 第 22步計(jì)算年齡的熵 年齡共分三個(gè)組： 青年、中年、老年 中年買與不買比例為 256/0 S1(買 )=256 S2（不買） = 0 S=S1+S2=256 P1=256/256 P2=0/256 I(S1,S2)=I(256， 0) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) =0 決策樹算法 計(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) = 決策樹算法 計(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） 決策樹算法 計(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) 決策樹算法 計(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） 決策樹算法 計(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ù)信息增益 =