【文章內(nèi)容簡介】 ID3 –信息量大小的度量 決策樹算法 Shannon1948年提出的信息論理論。事件 ai的信息量 I（ ai ）可 如下度量： 其中 p(ai)表示事件 ai發(fā)生的概率。 假設(shè)有 n個(gè)互不相容的事件 a1,a2,a3,….,an, 它們中有且僅有一個(gè) 發(fā)生，則其平均的信息量可如下度量： ??????ni iiniin apapaIaaaI12121 )(1log)()(),.. .,( )(1log)()( 2iii apapaI ?第 6章 決策樹 ID3 –信息量大小的度量 決策樹算法 ??????ni iiniin apapaIaaaI12121 )(1log)()(),.. .,(上式，對(duì)數(shù)底數(shù)可以為任何數(shù)，不同的取值對(duì)應(yīng)了熵的不同單位。 通常取 2，并規(guī)定當(dāng) p(ai)=0時(shí) =0 )(1log)()(2iii apapaI ?公式 1 第 6章 決策樹 決策樹算法 例：假設(shè)有一個(gè)數(shù)據(jù)集合 D，其中只有兩個(gè)類，一個(gè)是正例類，一個(gè)是負(fù)例類 計(jì)算 D中正例類和負(fù)例類在三種不同的組分下熵的變化情況。 （ 1） D中包含有 50%的正例和 50%的負(fù)例。 Entropy(D)=**=1 （ 2） D中包含有 20%的正例和 80%的負(fù)例。 Entropy(D)=**= （ 3） D中包含有 100%的正例和 0%的負(fù)例。 Entropy(D)=1*log210*log20=0 從上述的結(jié)果可以看到一個(gè)趨勢(shì)，當(dāng)數(shù)據(jù)變得越來越純凈時(shí)，熵的值變得 越來越小。事實(shí)上可以證明，當(dāng)正例（ ） ,反例（ ）時(shí)，熵取最大值。當(dāng) D 中所有數(shù)據(jù)都只屬于一個(gè)類時(shí)，熵得到最小值。 顯然，上可以作為數(shù)據(jù)純凈度或混亂度的衡量指標(biāo)。這正是決策樹學(xué)習(xí)中 需要的。 在決策樹分類中，假設(shè) S是訓(xùn)練樣本集合， |S|是訓(xùn)練樣本數(shù)，樣本 劃分為 n個(gè)不同的類 C1,C2,….Cn ，這些類的大小分別標(biāo)記為 |C1|， |C2|， …..,|Cn| 。則任意樣本 S屬于類 Ci的概率為： ||||)(SCSp ii ?第 6章 決策樹 ID3 –信息量大小的度量 決策樹算法 Entropy（ S， A） =∑（ |Sv|/|S|） * Entropy（ Sv）公式 2 ∑是屬性 A的所有可能的值 v,Sv是屬性 A有 v值的 S子集 |Sv|是 Sv 中元素的個(gè)數(shù)； |S|是 S中元素的個(gè)數(shù)。 第 6章 決策樹 ID3 –信息量大小的度量 決策樹算法 Gain（ S， A）是屬性 A在集合 S上的信息增益 Gain（ S， A） = Entropy（ S） Entropy（ S， A） 公式 3 Gain（ S， A）越大，說明選擇測(cè)試屬性對(duì)分類提供的信息越多 第 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ì)數(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) 買 第 1步計(jì)算決策屬性的熵 決策屬性“買計(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) = 決策樹算法 第 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) 買 第 2步計(jì)算條件屬性的熵 條件屬性共有 4個(gè)。分別是年齡、 收入、學(xué)生、信譽(yù)。 分別計(jì)算不同屬性的信息增益。 決策樹算法 第 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) 買 第 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) = 決策樹算法 第 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) 買 第 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 決策樹算法 第 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/1024= 中年組 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 青 低 是 良 買