決策樹培訓(xùn) 課件

DataMiningTool

－DecisionTree福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室趙紅2014年11月DataMiningTool

－Decision提要數(shù)據(jù)挖掘簡(jiǎn)介決策樹的用途決策樹的建立（ID3）C4.5示例WekaJ48源碼解析212/25/2022提要212/20/2022數(shù)據(jù)挖掘簡(jiǎn)介誰(shuí)加何種類型的油？3姓名年齡收入種族信譽(yù)電話地址加何種油張三234000亞裔良281-322-03282714Ave.MSupreme李四342800白人優(yōu)713-239-78305606HollyCrRegular王二701900西班牙優(yōu)281-242-32222000BellBlvd.Plus趙五18900非洲良281-550-0544100MainStreetSupreme劉蘭342500白人優(yōu)713-239-7430606HollyCtRegular楊俊278900亞裔優(yōu)281-355-7990233RiceBlvd.Plus張毅389500亞裔優(yōu)281-556-0544399SugarRd.Regular……數(shù)據(jù)挖掘簡(jiǎn)介誰(shuí)加何種類型的油？3姓名年齡收入種族信譽(yù)電話地址數(shù)據(jù)挖掘簡(jiǎn)介你能判定他/她買計(jì)算機(jī)的可能性大不大嗎？412/25/2022姓名年齡收入學(xué)生信譽(yù)電話地址郵編買計(jì)算機(jī)張三234000是良281-322-03282714Ave.M77388買李四342800否優(yōu)713-239-78305606HollyCr78766買王二701900否優(yōu)281-242-32222000BellBlvd.70244不買趙五18900是良281-550-0544100MainStreet70244買劉蘭342500否優(yōu)713-239-7430606HollyCt78566買楊俊278900否優(yōu)281-355-7990233RiceBlvd.70388不買張毅389500否優(yōu)281-556-0544399SugarRd.78244買……數(shù)據(jù)挖掘簡(jiǎn)介你能判定他/她買計(jì)算機(jī)的可能性大不大嗎？412/數(shù)據(jù)挖掘簡(jiǎn)介我們擁有什么:Hugeamountofdata(GTE:1TB/day)我們需要什么:Informationandknowledge我們應(yīng)該怎么辦:Datamining512/25/2022數(shù)據(jù)挖掘簡(jiǎn)介我們擁有什么:512/20/2022排名挖掘主題算法得票數(shù)發(fā)表時(shí)間作者陳述人1分類C4.5611993Quinlan,J.RHiroshiMotoda2聚類k-Means601967MacQueen,J.BJoydeepGhosh3統(tǒng)計(jì)學(xué)習(xí)SVM581995Vapnik,V.NQiangYang4關(guān)聯(lián)分析Apriori521994RakeshAgrawalChristosFaloutsos5統(tǒng)計(jì)學(xué)習(xí)EM482000McLachlan,GJoydeepGhosh6鏈接挖掘PageRank461998Brin,S.ChristosFaloutsos7集裝與推進(jìn)AdaBoost451997Freund,Y.Zhi-HuaZhou8分類kNN451996Hastie,TVipinKumar9分類Na?veBayes452001Hand,D.JQiangYang10分類CART341984L.BreimanDanSteinberg數(shù)據(jù)挖掘10大算法ICDM2006Panel(會(huì)議的專題討論)共有145人選出了數(shù)據(jù)挖掘10大算法。排名挖掘主題算法得票數(shù)發(fā)表時(shí)間作者陳述人1分類C4.5611建立分類模型的一般方法建立分類模型的一般方法決策樹的用途新顧客（測(cè)試樣例），你能幫助公司將這位客人歸類嗎？即：你能預(yù)測(cè)這位顧客是屬于“買、不買”計(jì)算機(jī)的那一類？又：你需要多少有關(guān)這位客人的信息才能回答這個(gè)問(wèn)題？812/25/2022計(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)買決策樹的用途新顧客（測(cè)試樣例），你能幫助公司將這位客人歸類嗎決策樹的用途912/25/2022誰(shuí)在買計(jì)算機(jī)？他/她會(huì)買計(jì)算機(jī)嗎？年齡？學(xué)生？信譽(yù)？買青中老否是優(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)買決策樹的用途912/20/2022誰(shuí)在買計(jì)算機(jī)？他/她會(huì)買計(jì)決策樹的用途1012/25/2022一棵很糟糕的決策樹收入？學(xué)生？青中否是高低中信譽(yù)？良優(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)買決策樹的用途1012/20/2022一棵很糟糕的決策樹收入？決策樹的用途什么是決策樹Adecisiontreeisaflow-chart-liketreestructureEachinternalnodedenotesatestonanattributeEachbranchrepresentsanoutcomeofthetestLeafnodesrepresentclassesorclassdistributions.1112/25/2022年齡？學(xué)生？信譽(yù)？買青中老否是優(yōu)良不買買買不買決策樹的用途什么是決策樹1112/20/2022年齡？學(xué)生？決策樹的建立決策樹建立的關(guān)鍵對(duì)測(cè)試樣例的信息期望(信息熵)信息期望的分析與計(jì)算平均信息期望信息期望的減少（信息增益）決策樹建立步驟（例）1212/25/2022決策樹的建立決策樹建立的關(guān)鍵1212/20/2022補(bǔ)充：信息熵例子例如：桌子甲上有10個(gè)水果。其中，有2個(gè)為蘋果，有8個(gè)為橘子。桌子乙上有10個(gè)水果。其中，有5個(gè)為蘋果，有5個(gè)為橘子。從直觀上感覺(jué):桌子甲上的水果分類比較集中于橘子。桌子乙上的水果分類，比較均勻。因此我們說(shuō)桌子甲上的水果分類比較純。桌子乙上的水果分類比較混亂。1312/25/2022補(bǔ)充：信息熵例子例如：1312/20/2022補(bǔ)充：信息熵熵——系統(tǒng)凌亂程度的度量。凌亂程度在同一個(gè)集合中，分類越集中于某一類，越不凌亂；分類越均勻分散于不同的類，則越凌亂。通俗說(shuō)法：不確定性越大，熵也就越大；把它搞清楚所需要的信息量也就越大。1412/25/2022補(bǔ)充：信息熵熵——系統(tǒng)凌亂程度的度量。1412/20/202補(bǔ)充：關(guān)于某布爾分類的熵函數(shù)S為某正反樣例的樣例集（布爾分類）S的所有成員屬于同一類，Entropy(S)=0；S的正反樣例數(shù)量相等，Entropy(S)=1；S的正反樣例數(shù)量不等，熵介于0和1之間補(bǔ)充：關(guān)于某布爾分類的熵函數(shù)S為某正反樣例的樣例集（布爾分類補(bǔ)充：更一般的熵定義更一般地，如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)的分類的熵定義為：其中，pi是S中屬于類別i的比例。如果目標(biāo)屬性具有c個(gè)可能值，那么熵最大可能為log2c。補(bǔ)充：更一般的熵定義更一般地，如果目標(biāo)屬性具有c個(gè)不同的值，補(bǔ)充：用信息增益度量期望的熵降低信息增益是定義屬性分類訓(xùn)練數(shù)據(jù)的能力的度量標(biāo)準(zhǔn)。簡(jiǎn)單地說(shuō)，一個(gè)屬性的信息增益就是由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低。更精確地講，一個(gè)屬性A相對(duì)樣例集合S的信息增益Gain(S,A)，被定義為：其中，Values(A)是屬性A所有可能值的集合，Sv是S中屬性A的值為v的子集。補(bǔ)充：用信息增益度量期望的熵降低信息增益是定義屬性分類訓(xùn)練數(shù)決策樹的建立--決策樹建立的關(guān)鍵建立一個(gè)好的決策樹的關(guān)鍵是決定樹根和子樹根的屬性1812/25/2022樹根？計(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)買決策樹的建立--決策樹建立的關(guān)鍵建立一個(gè)好的決策樹的關(guān)鍵是決策樹的建立--對(duì)測(cè)試樣例的信息期望信息期望？張三屬于哪一類？為了回答該問(wèn)題，對(duì)張三的信息期望值是多少？1912/25/2022年齡計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？128中高否良買64中低是優(yōu)買32中中否優(yōu)買32中高是良買計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60老中否良買64老低是良買64老低是優(yōu)不買132老中是良買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)買決策樹的建立--對(duì)測(cè)試樣例的信息期望信息期望？張三屬于哪一決策樹的建立--對(duì)測(cè)試樣例的信息期望所需要研究的屬性為“分類屬性”假設(shè)該屬性共分m類，每一類的個(gè)數(shù)分別為

s1,s2…,sm令s=s1+s2+…+sm決定測(cè)試樣例所屬類別的信息期望：I(s1,s2…,sm)=-pi

log2(pi)其中pi

=si/s2012/25/2022i=1m決策樹的建立--對(duì)測(cè)試樣例的信息期望所需要研究的屬性為“分類決策樹的建立--例分類屬性：買計(jì)算機(jī)？該屬性共分兩類(m=2):買/不買s1=641,s2=383

s=s1+s2=1024p1=s1/s=641/1024=0.6260

p2=s2/s=383/1024=0.3740I(s1,s2)=I(641,383)

=-(p1

log2(p1)+p2

log2(p2))

=0.95372112/25/2022決策樹的建立--例分類屬性：買計(jì)算機(jī)？2112/20/202決策樹的建立--對(duì)測(cè)試樣例的信息期望討論：“買”/“不買”計(jì)算機(jī)的人數(shù)之間的比例對(duì)于信息期望值的影響I(641,383)=0.9537I(512,512)=I(4,4)=1I(51,973)=I(973,51)=0.2856I(0,1024)=I(256,0)=0I(128,256)=0.9183I(257,127)=0.9157信息期望的數(shù)值與分類屬性中各類計(jì)數(shù)之間的比例有關(guān)信息期望的數(shù)值與計(jì)數(shù)總數(shù)無(wú)關(guān)2212/25/2022決策樹的建立--對(duì)測(cè)試樣例的信息期望討論：“買”/“不買”決策樹的建立--對(duì)測(cè)試樣例的信息期望例：分類屬性：加何種油？該屬性共分三類(m=3):Regular/Plus/Supremes1=13300,s2=7300,s3=5200

s=s1+s2+s3=25800p1=s1/s=13300/25800=0.5155

p2=s2/s=7300/25800=0.2829

p3=s3/s=5200/25800=0.2016I(s1,s2,s3)=I(13300,7300,5200)

=-(p1log2(p1)+p2log2(p2)+p3log2(p3))

=1.47392312/25/2022計(jì)數(shù)年齡收入種族信譽(yù)加何種油2000老低亞裔良Supreme1500老高白人良Regular3900中中西班牙良Plus3200中低非洲優(yōu)Supreme5200青高白人優(yōu)Regular1800青中亞裔優(yōu)Plus2400青高亞裔良Regular2200青高非洲優(yōu)Regular1600老中西班牙良Plus2000青高西班牙良Regular決策樹的建立--對(duì)測(cè)試樣例的信息期望例：分類屬性：加何種油決策樹的建立--對(duì)測(cè)試樣例的信息期望討論：三種汽油購(gòu)買人數(shù)之間的比例對(duì)于需解決的信息量的影響

I(13300,7300,5200)=1.4739

I(25800,0,0)=0

I(0,10,0)=0

I(641,383,0)=0.9537

I(900,100,24)=0.6183

I(64,64,64)=1.5850當(dāng)分類屬性的種類增加時(shí)，對(duì)測(cè)試樣例的信息期望通常也相應(yīng)增加。2412/25/2022決策樹的建立--對(duì)測(cè)試樣例的信息期望討論：三種汽油購(gòu)買人數(shù)決策樹的建立--對(duì)測(cè)試樣例的信息期望信息期望？平均信息期望？2512/25/2022年齡計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？128中高否良買64中低是優(yōu)買32中中否優(yōu)買32中高是良買計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60老中否良買64老低是良買64老低是優(yōu)不買132老中是良買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)買決策樹的建立--對(duì)測(cè)試樣例的信息期望信息期望？平均信息期望決策樹的建立--對(duì)測(cè)試樣例的信息期望信息期望的減少(又稱Gain，信息增益)=信息期望–平均信息期望信息期望基于節(jié)點(diǎn)數(shù)據(jù)表平均信息期望基于該節(jié)點(diǎn)的所有直系分支數(shù)據(jù)表2612/25/2022決策樹的建立--對(duì)測(cè)試樣例的信息期望信息期望的減少(又稱G決策樹的建立--對(duì)測(cè)試樣例的信息期望平均信息期望E，是節(jié)點(diǎn)各直系分支的信息期望值的加權(quán)總和。1.假定選擇年齡作樹根節(jié)點(diǎn)，則：

青年組:I(128,256)=0.9183

中年組:I(256,0)=0

老年組:I(257,127)=0.9157青年組比例:(128+256)/1024=0.375

中年組比例:256/1024=0.25

老年組比例:(257+127)/1024=0.375平均信息期望（加權(quán)總和）：

E(年齡）=0.375*0.9183

+0.25*0+0.375*0.9157=0.6877Gain(年齡)=I(641,383)-E(年齡)

=0.9537–0.6877=0.26602712/25/2022計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？128中高否良買64中低是優(yōu)買32中中否優(yōu)買32中高是良買計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60老中否良買64老低是良買64老低是優(yōu)不買132老中是良買63老中否優(yōu)不買1老中否優(yōu)買決策樹的建立--對(duì)測(cè)試樣例的信息期望平均信息期望E，是節(jié)點(diǎn)決策樹的建立--對(duì)測(cè)試樣例的信息期望2. 假定選擇收入作樹根節(jié)點(diǎn)，則： 高收入組:I(160,128)=0.9911

中收入組:I(289,191)=0.9697

低收入組:I(192,64)=0.8113

高收入組比例:288/1024=0.2813

中收入組比例:480/1024=0.4687

低收入組比例:256/1024=0.25平均信息期望（加權(quán)總和）：E(收入）=0.2813*0.9911+0.4687*0.9697+0.25*0.8113=0.9361Gain(收入)：I(641,383)-E(收入)=0.9537–0.9361=0.01762812/25/2022決策樹的建立--對(duì)測(cè)試樣例的信息期望2. 假定選擇收入作樹決策樹的建立--對(duì)測(cè)試樣例的信息期望3. 假定選擇學(xué)生作樹根節(jié)點(diǎn)，則： 學(xué)生組:I(420,64)=0.5635

非學(xué)生組:I(221,319)=0.9761

學(xué)生組比例:484/1024=0.4727

非學(xué)生組比例:540/1024=0.5273平均信息期望（加權(quán)總和）：

E(學(xué)生）=0.4727*0.5635 +0.5273*0.9761=0.7811Gain(學(xué)生)：=I(641,383)-E(學(xué)生)=0.9537–0.7811=0.17262912/25/2022決策樹的建立--對(duì)測(cè)試樣例的信息期望3. 假定選擇學(xué)生作樹決策樹的建立--對(duì)測(cè)試樣例的信息期望4. 假定選擇信譽(yù)作樹根節(jié)點(diǎn)，則： 良好組:I(480,192)=0.8631

優(yōu)秀組:I(161,191)=0.9948

良好組比例:672/1024=0.6563

優(yōu)秀組比例:352/1024=0.3437平均信息期望（加權(quán)總和）：

E(信譽(yù)）=0.6563*0.8631+0.3437*0.9948 =0.9048Gain(信譽(yù))：=I(641,383)-E(信譽(yù)) =0.9537–0.9048=0.04533012/25/2022決策樹的建立--對(duì)測(cè)試樣例的信息期望4. 假定選擇信譽(yù)作樹決策樹的建立--對(duì)測(cè)試樣例的信息期望決定樹根節(jié)點(diǎn)E(年齡)=0.6877，Gain(年齡)=0.2660E(收入)=0.9361，Gain(收入)=0.0176E(學(xué)生)=0.7811，Gain(學(xué)生)=0.1726E(信譽(yù))=0.9048，Gain(信譽(yù))=0.04533112/25/2022決策樹的建立--對(duì)測(cè)試樣例的信息期望決定樹根節(jié)點(diǎn)3112/決策樹的建立--決策樹建立步驟（例）3212/25/2022年齡計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64高否良不買64高否優(yōu)不買128中否良不買64低是良買64中是優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60中否良買64低是良買64低是優(yōu)不買132中是良買63中否優(yōu)不買1中否優(yōu)買青中老樹葉計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？128高否良買64低是優(yōu)買32中否優(yōu)買32高是良買決策樹的建立--決策樹建立步驟（例）3212/20/202決策樹的建立--決策樹建立步驟（例）3312/25/2022年齡計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64高否良不買64高否優(yōu)不買128中否良不買64低是良買64中是優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60中否良買64低是良買64低是優(yōu)不買132中是良買63中否優(yōu)不買1中否優(yōu)買青中老買決策樹的建立--決策樹建立步驟（例）3312/20/202決策樹的建立--青年組數(shù)據(jù)表分析（例）1.假定選擇收入作節(jié)點(diǎn)I(128,256)=0.9183E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183–0.4592=0.4591I(0,128)=0

比例:128/384=0.3333I(64,128)=0.9183

比例:192/384=0.5I(64,0)=0

比例:64/384=0.16673412/25/2022計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64高否良不買64高否優(yōu)不買128中否良不買64低是良買64中是優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64高否良不買64高否優(yōu)不買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？128中否良不買64中是優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64低是良買決策樹的建立--青年組數(shù)據(jù)表分析（例）1.假定選擇收入作節(jié)決策樹的建立--青年組數(shù)據(jù)表分析（例）2.假定選擇學(xué)生作節(jié)點(diǎn)I(128,256)=0.9183E(學(xué)生）=0.3333*0+0.6667*0=0Gain(學(xué)生)=I(128,256)-E(學(xué)生)=0.9183–0=0.9183I(128,0)=0

比例:128/384=0.3333I(0,256)=0

比例:256/384=0.6667結(jié)論:不需要考慮屬性信譽(yù)，決定選擇屬性學(xué)生3512/25/2022計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64高否良不買64高否優(yōu)不買128中否良不買64低是良買64中是優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64高否良不買64高否優(yōu)不買128中否良不買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64低是良買64中是優(yōu)買決策樹的建立--青年組數(shù)據(jù)表分析（例）2.假定選擇學(xué)生作節(jié)決策樹的建立--決策樹建立步驟（例）3612/25/2022年齡計(jì)數(shù)收入信譽(yù)歸類：買計(jì)算機(jī)？64低良買64中優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60中否良買64低是良買64低是優(yōu)不買132中是良買63中否優(yōu)不買1中否優(yōu)買青中老買學(xué)生計(jì)數(shù)收入信譽(yù)歸類：買計(jì)算機(jī)？64高良不買64高優(yōu)不買128中良不買否是樹葉決策樹的建立--決策樹建立步驟（例）3612/20/202決策樹的建立--決策樹建立步驟（例）3712/25/2022年齡計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60中否良買64低是良買64低是優(yōu)不買132中是良買63中否優(yōu)不買1中否優(yōu)買青中老買學(xué)生否是買不買決策樹的建立--決策樹建立步驟（例）3712/20/202決策樹的建立--老年組數(shù)據(jù)表分析（例）1.假定選擇收入作節(jié)點(diǎn)I(257,127)=0.9157E(收入）=0.3333*1+0.6667*0.8050=0.8700Gain(收入)=I(257,127)-E(收入)=0.9157–0.8700=0.0457I(64,64)=1

比例:128/384=0.3333I(193,63)=0.8050

比例:256/384=0.66673812/25/2022計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60中否良買64低是良買64低是優(yōu)不買132中是良買63中否優(yōu)不買1中否優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60中否良買132中是良買63中否優(yōu)不買1中否優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64低是良買64低是優(yōu)不買決策樹的建立--老年組數(shù)據(jù)表分析（例）1.假定選擇收入作節(jié)決策樹的建立--老年組數(shù)據(jù)表分析（例）2.假定選擇學(xué)生作節(jié)點(diǎn)I(257,127)=0.9157E(學(xué)生）=0.6771*0.8051+0.3229*0.9998=0.8680Gain(學(xué)生)=I(257,127)-E(學(xué)生)=0.9157–0.8680=0.0477I(196,64)=0.8051

比例:260/384=0.6771I(61,63)=0.9998

比例:124/384=0.32293912/25/2022計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60中否良買64低是良買64低是優(yōu)不買132中是良買63中否優(yōu)不買1中否優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60中否良買63中否優(yōu)不買1中否優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64低是良買64低是優(yōu)不買132中是良買決策樹的建立--老年組數(shù)據(jù)表分析（例）2.假定選擇學(xué)生作節(jié)決策樹的建立--老年組數(shù)據(jù)表分析（例）3.假定選擇信譽(yù)作節(jié)點(diǎn)I(257,127)=0.9157E(信譽(yù)）=0.6667*0+0.3333*0.0659=0.0220Gain(信譽(yù))=I(257,127)-E(信譽(yù))=0.9157–0.0220=0.8937I(256,0)=0

比例:256/384=0.6667I(1,127)=0.0659

比例:128/384=0.3333結(jié)論:決定選擇屬性信譽(yù)4012/25/2022計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60中否良買64低是良買64低是優(yōu)不買132中是良買63中否優(yōu)不買1中否優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64低是優(yōu)不買63中否優(yōu)不買1中否優(yōu)買計(jì)數(shù)收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60中否良買64低是良買132中是良買決策樹的建立--老年組數(shù)據(jù)表分析（例）3.假定選擇信譽(yù)作節(jié)決策樹的建立--決策樹建立步驟（例）4112/25/2022年齡計(jì)數(shù)收入學(xué)生歸類：買計(jì)算機(jī)？60中否買64低是買132中是買青中老買學(xué)生否是買不買信譽(yù)計(jì)數(shù)收入學(xué)生歸類：買計(jì)算機(jī)？64低是不買63中否不買1中否買優(yōu)良樹葉決策樹的建立--決策樹建立步驟（例）4112/20/202決策樹的建立--決策樹建立步驟（例）4212/25/2022年齡青中老買學(xué)生否是買不買信譽(yù)計(jì)數(shù)收入學(xué)生歸類：買計(jì)算機(jī)？64低是不買63中否不買1中否買優(yōu)良買……決策樹的建立--決策樹建立步驟（例）4212/20/202決策樹算法流程（ID3）選擇節(jié)點(diǎn)分裂屬性；建立新節(jié)點(diǎn)，劃分?jǐn)?shù)據(jù)集；判斷節(jié)點(diǎn)是否到生長(zhǎng)停止條件，如果是，終止生長(zhǎng)，如果不是，轉(zhuǎn)到第1步。樹停止生長(zhǎng)條件節(jié)點(diǎn)內(nèi)的數(shù)據(jù)已經(jīng)完全屬于同一類別。節(jié)點(diǎn)內(nèi)測(cè)數(shù)據(jù)樣本數(shù)低于某一閾值。所有屬性都已經(jīng)被分裂過(guò)。決策樹算法流程（ID3）選擇節(jié)點(diǎn)分裂屬性；從ID3到C4.5從ID3到C4.5共同之處：通過(guò)自頂向下構(gòu)造決策樹進(jìn)行學(xué)習(xí)；構(gòu)造過(guò)程的開始：哪一個(gè)屬性將在樹的根節(jié)點(diǎn)被測(cè)試？區(qū)別：選擇測(cè)試屬性時(shí)的準(zhǔn)則ID3:增益準(zhǔn)則(Gaincriterion)—衡量給定屬性區(qū)分訓(xùn)練樣例的能力。C4.5:增益率準(zhǔn)則(Gainratiocriterion)44從ID3到C4.5從ID3到C4.5共同之處：44ID3信息增益存在的問(wèn)題由劃分個(gè)數(shù)引起的偏置問(wèn)題當(dāng)某個(gè)屬性具有取值越多=>劃分越多=>分塊越小，數(shù)據(jù)純度可能越高=>進(jìn)而引起偏置問(wèn)題當(dāng)某個(gè)屬性具有多個(gè)取值時(shí)，信息增益度量會(huì)賦予該屬性的有用程度一個(gè)不適當(dāng)?shù)闹甘?。ID3信息增益存在的問(wèn)題由劃分個(gè)數(shù)引起的偏置問(wèn)題ID3信息增益存在的問(wèn)題在極端情況下，比如在是否打高爾夫球的例子中，“日期”這個(gè)屬性。對(duì)于每個(gè)實(shí)例都取得不同的值。這個(gè)屬性所形成的劃分，使得每個(gè)子集都僅有一個(gè)實(shí)例。根據(jù)信息增益的定義，“日期”這個(gè)屬性將會(huì)有信息增益度量值會(huì)最高。而實(shí)際上，這個(gè)屬性可能是無(wú)關(guān)或者無(wú)用的。46ID3信息增益存在的問(wèn)題在極端情況下，比如在是否打高爾夫球的C4.5信息增益率設(shè)樣本集S按離散屬性F的V個(gè)不同的取值劃分為S1…Sv共V個(gè)子集定義Split(S,F)：則用F對(duì)S進(jìn)行劃分的信息增益率為：C4.5信息增益率設(shè)樣本集S按離散屬性F的V個(gè)不同的取值劃分C4.5例屬性穿衣指數(shù)溫度濕度風(fēng)力天氣舒適度1較多35701不舒適2較多33787不舒適3較多34804不舒適4正常32850舒適5正常33855舒適6很多25902不舒適7很多24883不舒適8很多30501舒適9很多32606不舒適10較多26860不舒適48C4.5例屬性穿衣指數(shù)溫度濕度風(fēng)力天氣舒適度1較多35701C4.5例分類屬性：天氣舒適度？該屬性共分兩類(m=2):舒適/不舒適s1=3,s2=7

s=s1+s2=10p1=s1/s=0.3

p2=s2/s=0.7I(s1,s2)=I(3,7)

=-(p1

log2(p1)+p2

log2(p2))

=0.8814912/25/2022C4.5例分類屬性：天氣舒適度？4912/20/2022C4.5例假定選擇穿衣指數(shù)作樹根節(jié)點(diǎn)，則： 較多組:I(4,0)=0

正常組:I(2,0)=0

很多組:I(3,1)=-3/4log2(3/4)-1/4log2(1/4)=0.8113

較多組比例:4/10

正常組比例:2/10

很多組比例:4/10平均信息期望（加權(quán)總和）：E(穿衣指數(shù))=0+0+0.4*0.8113=0.3255012/25/2022C4.5例假定選擇穿衣指數(shù)作樹根節(jié)點(diǎn)，則：5012/20/2C4.5例Gain(穿衣指數(shù))I(3,7)–E(穿衣指數(shù))=0.881–0.325=0.556Split_infor(穿衣指數(shù),S)=-4/10log2(4/10)-4/10log2(4/10)-2/10log2(2/10)=1.522GainRatio(穿衣指數(shù),S)=0.556/1.522

=0.36535112/25/2022C4.5例Gain(穿衣指數(shù))5112/20/2022C4.5例－選劃分點(diǎn)242526303232333334355212/25/2022屬性穿衣指數(shù)溫度濕度風(fēng)力天氣舒適度1較多35701不舒適2較多33787不舒適3較多34804不舒適4正常32850舒適5正常33855舒適6很多25902不舒適7很多24883不舒適8很多30501舒適9很多32606不舒適10較多26860不舒適C4.5例－選劃分點(diǎn)24252630323233333435C4.5例－選劃分點(diǎn)2425263032323333343553E(溫度<=24,S)=-9/10*(3/9*log2(3/9)+6/9*log2(6/9))=0.8265Gain(溫度<=24,S)I(3,7)–E(溫度)=0.881-0.8265=0.0545Split_infor(溫度<=24,S)=-9/10*log2(9/10)-1/10*log2(1/10)=0.469GainRatio(溫度<=24,S)=0.0545/0.469

=0.116212/25/2022C4.5例－選劃分點(diǎn)24252630323233333435C4.5例－選劃分點(diǎn)242526303232333334355412/25/2022屬性穿衣指數(shù)溫度濕度風(fēng)力天氣舒適度1較多35701不舒適2較多33787不舒適3較多34804不舒適4正常32850舒適5正常33855舒適6很多25902不舒適7很多24883不舒適8很多30501舒適9很多31606不舒適10較多26860不舒適C4.5例－選劃分點(diǎn)24252630323233333435C4.5例－選劃分點(diǎn)2425263032323333343555E(溫度<=26,S)=-3/10*(3/3*log2(3/3)+0/3)-7/10*(3/7*log2(3/7)+4/7*log2(4/7))=0.6897Gain(溫度<=26,S)I(3,7)–E(溫度)=0.881-0.6897=0.1913Split_infor(溫度<=26,S)=-3/10*log2(3/10)-7/10*log2(7/10)=0.8813GainRatio(溫度<=26,S)=0.1913/0.8813

=0.217112/25/2022C4.5例－選劃分點(diǎn)24252630323233333435C4.5例－選劃分點(diǎn)GainRatio(溫度<=24,S)=0.12;GainRatio(溫度<=25,S)=0.16;GainRatio(溫度<=26,S)=0.217;GainRatio(溫度<=30,S)=0.006;GainRatio(溫度<=32,S)=0.0057;GainRatio(溫度<=33,S)=0.16;GainRatio(溫度<=34,S)=0.12;因此，溫度26為溫度的最佳劃分點(diǎn)；信息增益率為0.217.56C4.5例－選劃分點(diǎn)GainRatio(溫度<=24,SC4.5例－選屬性屬性“濕度”的信息增益率GainRatio(濕度<=50,S)=0.42.屬性“風(fēng)力”的信息增益率；GainRatio(風(fēng)力<=1,S)=0.21.GainRatio(濕度<50,S)最大，所以選擇濕度作為根節(jié)點(diǎn)，最佳劃分點(diǎn)為濕度為50%.57C4.5例－選屬性屬性“濕度”的信息增益率57C4.5比ID3的改進(jìn)1)用信息增益率來(lái)選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足；

2)能夠完成對(duì)連續(xù)屬性的離散化處理；

3)在樹構(gòu)造過(guò)程中進(jìn)行剪枝；

4)能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。C4.5算法優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。C4.5算法缺點(diǎn)：在構(gòu)造樹的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。C4.5比ID3的改進(jìn)1)用信息增益率來(lái)選擇屬性，克服了用福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室趙紅2014年9月C4.5示例

WekaJ48福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室C4.5示例

WekaJ48C4.5示例數(shù)據(jù)：weka中的weather數(shù)據(jù)（字符型、數(shù)值型）Arff文件outlook,temperature,humidity,windy,playsunny,hot,high,FALSE,nosunny,hot,high,TRUE,noovercast,hot,high,FALSE,yesrainy,mild,high,FALSE,yesrainy,cool,normal,FALSE,yesrainy,cool,normal,TRUE,noovercast,cool,normal,TRUE,yessunny,mild,high,FALSE,nosunny,cool,normal,FALSE,yesrainy,mild,normal,FALSE,yessunny,mild,normal,TRUE,yesovercast,mild,high,TRUE,yesovercast,hot,normal,FALSE,yesrainy,mild,high,TRUE,nooutlook,temperature,humidity,windy,playsunny,85,85,FALSE,nosunny,80,90,TRUE,noovercast,83,86,FALSE,yesrainy,70,96,FALSE,yesrainy,68,80,FALSE,yesrainy,65,70,TRUE,noovercast,64,65,TRUE,yessunny,72,95,FALSE,nosunny,69,70,FALSE,yesrainy,75,80,FALSE,yessunny,75,70,TRUE,yesovercast,72,90,TRUE,yesovercast,81,75,FALSE,yesrainy,71,91,TRUE,noC4.5示例數(shù)據(jù)：weka中的weather數(shù)據(jù)（字符型、數(shù)weka中的weather數(shù)據(jù)（字符型、數(shù)值型）outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnormalFALSEyesrainycoolnormalTRUEnoovercastcoolnormalTRUEyessunnymildhighFALSEnosunnycoolnormalFALSEyesrainymildnormalFALSEyessunnymildnormalTRUEyesovercastmildhighTRUEyesovercasthotnormalFALSEyesrainymildhighTRUEnooutlooktemperaturehumiditywindyplaysunny8585FALSEnosunny8090TRUEnoovercast8386FALSEyesrainy7096FALSEyesrainy6880FALSEyesrainy6570TRUEnoovercast6465TRUEyessunny7295FALSEnosunny6970FALSEyesrainy7580FALSEyessunny7570TRUEyesovercast7290TRUEyesovercast8175FALSEyesrainy7191TRUEno61weka中的weather數(shù)據(jù)（字符型、數(shù)值型）outlooC4.5示例WekaJ48C4.5示例WekaJ48WekaJ48算法源碼解析WekaJ48算法源碼解析WekaJ48算法源碼解析高級(jí)類J48WekaJ48算法源碼解析高級(jí)類J48WekaJ48算法源碼解析可剪枝的C4.5分類器WekaJ48算法源碼解析可剪枝的C4.5分類器WekaJ48算法源碼解析分類樹WekaJ48算法源碼解析分類樹WekaJ48算法源碼解析分類樹WekaJ48算法源碼解析分類樹WekaJ48算法源碼解析C4.5分裂模式WekaJ48算法源碼解析C4.5分裂模式WekaJ48算法源碼解析C4.5分裂模式WekaJ48算法源碼解析C4.5分裂模式WekaJ48算法源碼解析C4.5分裂模式WekaJ48算法源碼解析C4.5分裂模式WekaJ48算法源碼解析選擇分裂屬性WekaJ48算法源碼解析選擇分裂屬性WekaJ48算法源碼解析處理離散屬性WekaJ48算法源碼解析處理離散屬性WekaJ48算法源碼解析計(jì)算增益WekaJ48算法源碼解析計(jì)算增益WekaJ48算法源碼解析計(jì)算增益率WekaJ48算法源碼解析計(jì)算增益率WekaJ48算法源碼解析熵和條件熵WekaJ48算法源碼解析熵和條件熵WekaJ48算法源碼解析屬性熵WekaJ48算法源碼解析屬性熵WekaJ48算法源碼解析處理連續(xù)屬性WekaJ48算法源碼解析處理連續(xù)屬性WekaJ48算法源碼解析處理連續(xù)屬性WekaJ48算法源碼解析處理連續(xù)屬性WekaJ48算法源碼解析處理所有可能的分裂點(diǎn)WekaJ48算法源碼解析處理所有可能的分裂點(diǎn)WekaJ48算法源碼解析剪枝算法WekaJ48算法源碼解析剪枝算法WekaJ48算法源碼解析剪枝算法WekaJ48算法源碼解析剪枝算法WekaJ48算法源碼解析計(jì)算錯(cuò)誤率WekaJ48算法源碼解析計(jì)算錯(cuò)誤率DataMiningTool

－DecisionTree福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室趙紅2014年11月DataMiningTool

－DecisionDataMiningTool

－DecisionTree福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室趙紅2014年11月DataMiningTool

－Decision提要數(shù)據(jù)挖掘簡(jiǎn)介決策樹的用途決策樹的建立（ID3）C4.5示例WekaJ48源碼解析8512/25/2022提要212/20/2022數(shù)據(jù)挖掘簡(jiǎn)介誰(shuí)加何種類型的油？86姓名年齡收入種族信譽(yù)電話地址加何種油張三234000亞裔良281-322-03282714Ave.MSupreme李四342800白人優(yōu)713-239-78305606HollyCrRegular王二701900西班牙優(yōu)281-242-32222000BellBlvd.Plus趙五18900非洲良281-550-0544100MainStreetSupreme劉蘭342500白人優(yōu)713-239-7430606HollyCtRegular楊俊278900亞裔優(yōu)281-355-7990233RiceBlvd.Plus張毅389500亞裔優(yōu)281-556-0544399SugarRd.Regular……數(shù)據(jù)挖掘簡(jiǎn)介誰(shuí)加何種類型的油？3姓名年齡收入種族信譽(yù)電話地址數(shù)據(jù)挖掘簡(jiǎn)介你能判定他/她買計(jì)算機(jī)的可能性大不大嗎？8712/25/2022姓名年齡收入學(xué)生信譽(yù)電話地址郵編買計(jì)算機(jī)張三234000是良281-322-03282714Ave.M77388買李四342800否優(yōu)713-239-78305606HollyCr78766買王二701900否優(yōu)281-242-32222000BellBlvd.70244不買趙五18900是良281-550-0544100MainStreet70244買劉蘭342500否優(yōu)713-239-7430606HollyCt78566買楊俊278900否優(yōu)281-355-7990233RiceBlvd.70388不買張毅389500否優(yōu)281-556-0544399SugarRd.78244買……數(shù)據(jù)挖掘簡(jiǎn)介你能判定他/她買計(jì)算機(jī)的可能性大不大嗎？412/數(shù)據(jù)挖掘簡(jiǎn)介我們擁有什么:Hugeamountofdata(GTE:1TB/day)我們需要什么:Informationandknowledge我們應(yīng)該怎么辦:Datamining8812/25/2022數(shù)據(jù)挖掘簡(jiǎn)介我們擁有什么:512/20/2022排名挖掘主題算法得票數(shù)發(fā)表時(shí)間作者陳述人1分類C4.5611993Quinlan,J.RHiroshiMotoda2聚類k-Means601967MacQueen,J.BJoydeepGhosh3統(tǒng)計(jì)學(xué)習(xí)SVM581995Vapnik,V.NQiangYang4關(guān)聯(lián)分析Apriori521994RakeshAgrawalChristosFaloutsos5統(tǒng)計(jì)學(xué)習(xí)EM482000McLachlan,GJoydeepGhosh6鏈接挖掘PageRank461998Brin,S.ChristosFaloutsos7集裝與推進(jìn)AdaBoost451997Freund,Y.Zhi-HuaZhou8分類kNN451996Hastie,TVipinKumar9分類Na?veBayes452001Hand,D.JQiangYang10分類CART341984L.BreimanDanSteinberg數(shù)據(jù)挖掘10大算法ICDM2006Panel(會(huì)議的專題討論)共有145人選出了數(shù)據(jù)挖掘10大算法。排名挖掘主題算法得票數(shù)發(fā)表時(shí)間作者陳述人1分類C4.5611建立分類模型的一般方法建立分類模型的一般方法決策樹的用途新顧客（測(cè)試樣例），你能幫助公司將這位客人歸類嗎？即：你能預(yù)測(cè)這位顧客是屬于“買、不買”計(jì)算機(jī)的那一類？又：你需要多少有關(guān)這位客人的信息才能回答這個(gè)問(wèn)題？9112/25/2022計(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)買決策樹的用途新顧客（測(cè)試樣例），你能幫助公司將這位客人歸類嗎決策樹的用途9212/25/2022誰(shuí)在買計(jì)算機(jī)？他/她會(huì)買計(jì)算機(jī)嗎？年齡？學(xué)生？信譽(yù)？買青中老否是優(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)買決策樹的用途912/20/2022誰(shuí)在買計(jì)算機(jī)？他/她會(huì)買計(jì)決策樹的用途9312/25/2022一棵很糟糕的決策樹收入？學(xué)生？青中否是高低中信譽(yù)？良優(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)買決策樹的用途1012/20/2022一棵很糟糕的決策樹收入？決策樹的用途什么是決策樹Adecisiontreeisaflow-chart-liketreestructureEachinternalnodedenotesatestonanattributeEachbranchrepresentsanoutcomeofthetestLeafnodesrepresentclassesorclassdistributions.9412/25/2022年齡？學(xué)生？信譽(yù)？買青中老否是優(yōu)良不買買買不買決策樹的用途什么是決策樹1112/20/2022年齡？學(xué)生？決策樹的建立決策樹建立的關(guān)鍵對(duì)測(cè)試樣例的信息期望(信息熵)信息期望的分析與計(jì)算平均信息期望信息期望的減少（信息增益）決策樹建立步驟（例）9512/25/2022決策樹的建立決策樹建立的關(guān)鍵1212/20/2022補(bǔ)充：信息熵例子例如：桌子甲上有10個(gè)水果。其中，有2個(gè)為蘋果，有8個(gè)為橘子。桌子乙上有10個(gè)水果。其中，有5個(gè)為蘋果，有5個(gè)為橘子。從直觀上感覺(jué):桌子甲上的水果分類比較集中于橘子。桌子乙上的水果分類，比較均勻。因此我們說(shuō)桌子甲上的水果分類比較純。桌子乙上的水果分類比較混亂。9612/25/2022補(bǔ)充：信息熵例子例如：1312/20/2022補(bǔ)充：信息熵熵——系統(tǒng)凌亂程度的度量。凌亂程度在同一個(gè)集合中，分類越集中于某一類，越不凌亂；分類越均勻分散于不同的類，則越凌亂。通俗說(shuō)法：不確定性越大，熵也就越大；把它搞清楚所需要的信息量也就越大。9712/25/2022補(bǔ)充：信息熵熵——系統(tǒng)凌亂程度的度量。1412/20/202補(bǔ)充：關(guān)于某布爾分類的熵函數(shù)S為某正反樣例的樣例集（布爾分類）S的所有成員屬于同一類，Entropy(S)=0；S的正反樣例數(shù)量相等，Entropy(S)=1；S的正反樣例數(shù)量不等，熵介于0和1之間補(bǔ)充：關(guān)于某布爾分類的熵函數(shù)S為某正反樣例的樣例集（布爾分類補(bǔ)充：更一般的熵定義更一般地，如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)的分類的熵定義為：其中，pi是S中屬于類別i的比例。如果目標(biāo)屬性具有c個(gè)可能值，那么熵最大可能為log2c。補(bǔ)充：更一般的熵定義更一般地，如果目標(biāo)屬性具有c個(gè)不同的值，補(bǔ)充：用信息增益度量期望的熵降低信息增益是定義屬性分類訓(xùn)練數(shù)據(jù)的能力的度量標(biāo)準(zhǔn)。簡(jiǎn)單地說(shuō)，一個(gè)屬性的信息增益就是由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低。更精確地講，一個(gè)屬性A相對(duì)樣例集合S的信息增益Gain(S,A)，被定義為：其中，Values(A)是屬性A所有可能值的集合，Sv是S中屬性A的值為v的子集。補(bǔ)充：用信息增益度量期望的熵降低信息增益是定義屬性分類訓(xùn)練數(shù)決策樹的建立--決策樹建立的關(guān)鍵建立一個(gè)好的決策樹的關(guān)鍵是決定樹根和子樹根的屬性10112/25/2022樹根？計(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)買決策樹的建立--決策樹建立的關(guān)鍵建立一個(gè)好的決策樹的關(guān)鍵是決策樹的建立--對(duì)測(cè)試樣例的信息期望信息期望？張三屬于哪一類？為了回答該問(wèn)題，對(duì)張三的信息期望值是多少？10212/25/2022年齡計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？128中高否良買64中低是優(yōu)買32中中否優(yōu)買32中高是良買計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？60老中否良買64老低是良買64老低是優(yōu)不買132老中是良買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)買決策樹的建立--對(duì)測(cè)試樣例的信息期望信息期望？張三屬于哪一決策樹的建立--對(duì)測(cè)試樣例的信息期望所需要研究的屬性為“分類屬性”假設(shè)該屬性共分m類，每一類的個(gè)數(shù)分別為

s1,s2…,sm令s=s1+s2+…+sm決定測(cè)試樣例所屬類別的信息期望：I(s1,s2…,sm)=-pi

log2(pi)其中pi

=si/s10312/25/2022i=1m決策樹的建立--對(duì)測(cè)試樣例的信息期望所需要研究的屬性為“分類決策樹的建立--例分類屬性：買計(jì)算機(jī)？該屬性共分兩類(m=2):買/不買s1=641,s2=383

s=s1+s2=1024p1=s1/s=641/1024=0.6260

p2=s2/s=383/1024=0.3740I(s1,s2)=I(641,383)

=-(p1

log2(p1)+p2

log2(p2))

=0.953710412/25/2022決策樹的建立--例分類屬性：買計(jì)算機(jī)？2112/20/202決策樹的建立--對(duì)測(cè)試樣例的信息期望討論：“買”/“不買”計(jì)算機(jī)的人數(shù)之間的比例對(duì)于信息期望值的影響I(641,383)=0.9537I(512,512)=I(4,4)=1I(51,973)=I(973,51)=0.2856I(0,1024)=I(256,0)=0I(128,256)=0.9183I(257,127)=0.9157信息期望的數(shù)值與分類屬性中各類計(jì)數(shù)之間的比例有關(guān)信息期望的數(shù)值與計(jì)數(shù)總數(shù)無(wú)關(guān)10512/25/2022決策樹的建立--對(duì)測(cè)試樣例的信息期望討論：“買”/“不買”決策樹的建立--對(duì)測(cè)試樣例的信息期望例：分類屬性：加何種油？該屬性共分三類(m=3):Regular/Plus/Supremes1=13300,s2=7300,s3=5200

s=s1+s2+s3=25800p1=s1/s=13300/25800=0.5155

p2=s2/s=7300/25800=0.2829

p3=s3/s=5200/25800=0.2016I(s1,s2,s3)=I(13300,7300,5200)

=-(p1log2(p1)+p2log2(p2)+p3log2(p3))

=1.473910612/25/2022計(jì)數(shù)年齡收入種族信譽(yù)加何種油2000老低亞裔良Supreme150