【正文】 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 24步計(jì)算年齡的熵 年齡共分三個(gè)組： 青年、中年、老年 所占比例 青年組 384/1024= 中年組 256/1024= 老年組 384/1024= 計(jì)算年齡的平均信息期望 E（年齡） =*+ *0+ * = G（年齡信息增益） = = （ 1） 決策樹(shù)算法 第 6章 決策樹(shù) 計(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) 決策樹(shù)算法 第 6章 決策樹(shù) 計(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） 決策樹(shù)算法 第 6章 決策樹(shù) 計(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） 決策樹(shù)算法 第 6章 決策樹(shù) 計(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） 學(xué)生信息增益 = = （ 3） 信譽(yù)信息增益 = = （ 4） 決策樹(shù)算法 第 6章 決策樹(shù) 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 青 中 否 良 不買 64 青 低 是 良 買 64 青 中 是 優(yōu) 買 年齡 青年 中年 老年 買 / 不買 買 買 / 不買 葉子 決策樹(shù)算法 第 6章 決策樹(shù) 計(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) = 決策樹(shù)算法 第 6章 決策樹(shù) 計(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= 注意 決策樹(shù)算法 第 6章 決策樹(shù) 計(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) 良 買 不買 買 / 不買 買 葉子 葉子 葉子 決策樹(shù)算法 第 6章 決策樹(shù) ID3 決策樹(shù)建立算法 1 決定分類屬性； 2 對(duì)目前的數(shù)據(jù)表，建立一個(gè)節(jié)點(diǎn) N 3 如果數(shù)據(jù)庫(kù)中的數(shù)據(jù)都屬于同一個(gè)類， N就是樹(shù)葉，在樹(shù)葉上 標(biāo)出所屬的類 4 如果數(shù)據(jù)表中沒(méi)有其他屬性可以考慮，則 N也是樹(shù)葉，按照少 數(shù)服從多數(shù)的原則在樹(shù)葉上標(biāo)出所屬類別 5 否則，根據(jù)平均信息期望值 E或 GAIN值選出一個(gè)最佳屬性作 為節(jié)點(diǎn) N的測(cè)試屬性 6 節(jié)點(diǎn)屬性選定后，對(duì)于該屬性中的每個(gè)值： 從 N生成一個(gè)分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形 成分支節(jié)點(diǎn)的數(shù)據(jù)表，在表中刪除節(jié)點(diǎn)屬性那一欄 如果分支數(shù)據(jù)表非空，則運(yùn)用以上算法從該節(jié)點(diǎn)建立子樹(shù)。 電信運(yùn)營(yíng)商的客戶流失有三方面的含義：一是指客戶從一個(gè) 電信運(yùn)營(yíng)商轉(zhuǎn)網(wǎng)到其他電信運(yùn)營(yíng)商，這是流失分析的重點(diǎn)。 連續(xù)型屬性概化為區(qū)間值：表中年齡、費(fèi)用變化率和在網(wǎng)時(shí)間為 連續(xù)型數(shù)據(jù)，由于建立決策樹(shù)時(shí)，用離散型數(shù)據(jù)進(jìn)行處理速度最 快，因此對(duì)連續(xù)型數(shù)據(jù)進(jìn)行離散化處理，根據(jù)專家經(jīng)驗(yàn)和實(shí)際計(jì) 算信息增益，在“在網(wǎng)時(shí)長(zhǎng)”屬性中，通過(guò)檢測(cè)每個(gè)劃分，得到在 閾值為 5年時(shí)信息增益最大，從而確定最好的劃分是在 5年處，則 這個(gè)屬性的范圍就變?yōu)椋?=5,5： H1,H2｝。 一個(gè)好的分類模型必須具有低的訓(xùn)練誤差和泛化誤差。 Occan法則（又稱 Occan剃刀 Occan Razor） :具有相同 泛化誤差的兩個(gè)模型，較簡(jiǎn)單的模型比復(fù)雜的模型更可取。驗(yàn)證樣本用于測(cè)試 訓(xùn)練后的性能。 第 6章 決策樹(shù) 決策樹(shù)算法 ID3算法實(shí)際應(yīng)用 在電信行業(yè)應(yīng)用實(shí)例（ 3） 屬性刪除：將有大量不同取值且無(wú)概化操作符的屬性或者可用其 它屬性來(lái)代替它的較高層概念的那些屬性刪除。 參考 Top 10 algorithms in data mining Knowledge Information System 2023 14:1–37 第 6章 決策樹(shù) 決策樹(shù)算法 ID3算法小結(jié) ID3算法是一種經(jīng)典的決策樹(shù)學(xué)習(xí)算法，由 Quinlan于 1979年 提出。 第 6章 決策樹(shù) ID3 –信息量大小的度量 決策樹(shù)算法 Gain（ S， A）是屬性 A在集合 S上的信息增益 Gain（ S， A） = Entropy（ S） Entropy（ S， A） 公式 3 Gain（ S， A）越大，說(shuō)明選擇測(cè)試屬性對(duì)分類提供的信息越多 第 6章 決策樹(shù) 計(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) 買 決策樹(shù)算法 第 6章 決策樹(shù) 計(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ī)？”。 選擇 (a)時(shí)，如果我們選擇按照多數(shù)服從少數(shù)的方法，則會(huì)產(chǎn)生 5個(gè)錯(cuò)誤的分類。沒(méi)有規(guī)定采用何種測(cè)試屬性。 是整個(gè)決策樹(shù)的開(kāi)始。其分類精度為 .43/ 上例的數(shù)據(jù)來(lái)自 UCI Machine Learning Repository中的 German Credit Dataset 可以免費(fèi)獲取。 學(xué)習(xí)過(guò)程將產(chǎn)生對(duì)目標(biāo)函數(shù) f的不同逼近。即從特殊事實(shí)到普遍性規(guī)律的結(jié)論。最終結(jié)果 綜合了兩個(gè)分類器的結(jié)果得到。 第 6章 決策樹(shù)