決策樹、信息論、ID3、C45算法課件

C4.5算法講解2012.11.29C4.5算法講解2012.11.291C4.5算法ID3算法知識結(jié)構(gòu)決策樹基礎(chǔ)信息論基礎(chǔ)C4.5算法ID3算法知識結(jié)構(gòu)決策樹基礎(chǔ)信息論基礎(chǔ)2決策樹基礎(chǔ)女孩家長安排相親女孩不厭其煩女孩提出決策樹父母篩選候選男士決策樹基礎(chǔ)女孩家長3決策樹基礎(chǔ)有向無環(huán)二叉/多叉樹父節(jié)點：沒有子節(jié)點的節(jié)點內(nèi)部節(jié)點：有父節(jié)點、子節(jié)點的節(jié)點葉節(jié)點：有父節(jié)點沒有子節(jié)點的節(jié)點父節(jié)點內(nèi)部節(jié)點葉節(jié)點分割屬性+判斷規(guī)則類別標識決策樹基礎(chǔ)有向無環(huán)二叉/多叉樹父節(jié)點葉節(jié)點分割屬性+判斷4決策樹基礎(chǔ)父節(jié)點內(nèi)部節(jié)點葉節(jié)點（類別標識）（分割屬性+判斷規(guī)則）決策樹基礎(chǔ)父節(jié)點葉節(jié)點（分割屬性+判斷規(guī)則）5決策樹基礎(chǔ)訓(xùn)練集：數(shù)據(jù)的集合，用于生成樹（模型）測試集：用于測試樹（模型）的性能決策樹作用：通過訓(xùn)練集算法指導(dǎo)下生成決策樹新數(shù)據(jù)進行劃分否則是“三拍”決策訓(xùn)練集算法決策樹新數(shù)據(jù)決策決策樹基礎(chǔ)訓(xùn)練集：數(shù)據(jù)的集合，用于生成樹（模型）訓(xùn)練集算法決6決策樹基礎(chǔ)實例No.頭痛肌肉痛體溫患流感1是(1)是(1)正常(0)N(0)2是(1)是(1)高(1)Y(1)3是(1)是(1)很高(2)Y(1)4否(0)是(1)正常(0)N(0)5否(0)否(0)高(1)N(0)6否(0)是(1)很高(2)N(1)7是(1)否(0)高(1)Y(1)決策樹怎么做？誰是父節(jié)點？誰是下一層子節(jié)點？為什么是它？頭-肌肉-體溫頭-體溫-肌肉肌肉-頭-體溫肌肉-體溫-頭體溫-頭-肌肉體溫-肌肉-頭三拍決策決策樹基礎(chǔ)實例No.頭痛肌肉痛體溫患流感1是(1)是(1)7決策樹基礎(chǔ)……@）￥——JK)I*&^Fkl9*^&%*&UIDOFGJNo.天氣氣溫濕度風(fēng)類別1晴熱高無N2晴熱高有N3多云熱高無P4雨適中高無P5雨冷正常無P6雨冷正常有N7多云冷正常有PNo.天氣氣溫濕度風(fēng)類別8晴適中高無N9晴冷正常無P10雨適中正常無P11晴適中正常有P12多云適中高有P13多云熱正常無P14雨適中高有N決策樹基礎(chǔ)……@）￥——JK)I*&^Fkl9*^&%*&8怎么生成好的？哪個好？種決策樹方案決策樹基礎(chǔ)N個分割屬性的訓(xùn)練集怎么生成好的？哪個好？種決策9決策樹基礎(chǔ)好的決策樹：（MDL準則下為例）MinimumDescriptionLength訓(xùn)練集中大多數(shù)數(shù)據(jù)符合這棵樹例外的數(shù)據(jù)單獨編碼描述決策樹用的bit描述例外數(shù)據(jù)用bit哪個好？決策樹基礎(chǔ)描述決策樹用的bit描述例外數(shù)據(jù)用bit哪個好？10決策樹基礎(chǔ)（選擇掌握）如何描述決策樹體溫頭痛很高正常高YNYN否是流感決策樹深度優(yōu)先遍歷決策樹用1標注父子節(jié)點用0標注葉節(jié)點記錄分割屬性1,體溫,0,Y,1,頭疼,0,Y,0,N,0,N層次少+分枝少占用存儲空間小決策計算時間快決策樹基礎(chǔ)（選擇掌握）如何描述決策樹體溫頭痛很高正常高YNY11決策樹基礎(chǔ)C4.5算法ID3算法決策樹基礎(chǔ)信息論基礎(chǔ)選哪個？？怎么生成好的？NextOne!決策樹基礎(chǔ)C4.5算法ID3算法決策樹基礎(chǔ)信息論基礎(chǔ)選哪個？12信息論基礎(chǔ)辨析先驗概率信息量信息論基礎(chǔ)辨析13信息論基礎(chǔ)—先驗概率對事件X的某一結(jié)果進行討論：例：在沒有任何幫助的情況下，奧/羅誰贏的概率P（x1=奧）=P（x2=羅）信息論基礎(chǔ)—先驗概率對事件X的某一結(jié)果進行討論：14信息論基礎(chǔ)—信息量信息論基礎(chǔ)—信息量15信息論基礎(chǔ)辨析先驗概率信息量先驗熵信息論基礎(chǔ)辨析16信息論基礎(chǔ)先驗熵——自信息量——熵H（X）原意：熱力學(xué)中形容失序現(xiàn)象和復(fù)雜程度現(xiàn)意：一個事件X的平均信息量熵越大，不確定性就越大，正確估計其值的可能性就越小。XXX熵===XXX的信息量的加權(quán)信息論基礎(chǔ)先驗熵——自信息量——熵H（X）17信息論基礎(chǔ)先驗熵——自信息量——熵H（X）原意：熱力學(xué)中形容失序現(xiàn)象和復(fù)雜程度現(xiàn)意：通信中一個事件的平均信息量信息論基礎(chǔ)先驗熵——自信息量——熵H（X）18信息論基礎(chǔ)熵H(X)——自信息量科學(xué)發(fā)展觀指導(dǎo)下的和諧社會，失序現(xiàn)象和復(fù)雜程度遠低于萬惡的資本主義社會！事件的可能結(jié)果發(fā)生幾率越相近，則熵越大信息論基礎(chǔ)熵H(X)——自信息量19信息論基礎(chǔ)辨析先驗概率信息量先驗熵后驗概率信息論基礎(chǔ)辨析20信息論基礎(chǔ)對事件X的某一結(jié)果進行討論：例：已知民意調(diào)查結(jié)果，猜奧/羅誰贏的概率P（x1=奧|y1=奧領(lǐng)先）>P（x2=羅|y1=奧領(lǐng)先）信息論基礎(chǔ)對事件X的某一結(jié)果進行討論：21信息論基礎(chǔ)辨析先驗概率信息量先驗熵后驗概率后驗熵信息論基礎(chǔ)辨析22信息論基礎(chǔ)熵H(X)原意：熱力學(xué)中形容失序現(xiàn)象和復(fù)雜程度現(xiàn)意：一個事件X的平均信息量熵越大，不確定性就越大，正確估計其值的可能性就越小。XXX熵===XXX的信息量的加權(quán)后驗熵=后驗概率的信息量的加權(quán)信息論基礎(chǔ)熵H(X)23信息論基礎(chǔ)對事件X的全部結(jié)果在某一輔助條件下進行討論：信息論基礎(chǔ)對事件X的全部結(jié)果在某一輔助條件下進行討論：24信息論基礎(chǔ)對事件X的全部結(jié)果在某一輔助條件下進行討論：例：在民意調(diào)查的結(jié)果幫助下（y1）計算2012年誰是總統(tǒng)的不確定性H(誰當選|民調(diào)奧領(lǐng)先)=？信息論基礎(chǔ)對事件X的全部結(jié)果在某一輔助條件下進行討論：25信息論基礎(chǔ)辨析先驗概率信息量熵=自信息量后驗概率后驗墑條件熵信息論基礎(chǔ)辨析26信息論基礎(chǔ)對事件X的全部結(jié)果在全部輔助條件下進行討論：信息論基礎(chǔ)對事件X的全部結(jié)果在全部輔助條件下進行討論：27信息論基礎(chǔ)條件熵即對后驗墑的所有可能輔助條件Yj累計信息論基礎(chǔ)條件熵28信息論基礎(chǔ)辨析先驗概率信息量熵=自信息量后驗概率后驗墑條件熵信息論基礎(chǔ)辨析29信息論基礎(chǔ)辨析信息量熵=自信息量先驗概率后驗概率后驗墑條件熵互信息量信息論基礎(chǔ)辨析30信息論基礎(chǔ)對于條件墑H(X|Y)由于輔助條件Y的存在由熵——不確定程度——事件X的平均信息量所以一般情況下H(X)=<H(X|Y)I(X|Y)=H(X)-H(X|Y)信息論基礎(chǔ)對于條件墑H(X|Y)31信息論基礎(chǔ)信息論基礎(chǔ)32信息論基礎(chǔ)因此定義互信息量I(X,Y)——信息增益I(X,Y)信息增益才是接收端獲得的信息量我沒收到任何東西前，我不知道你發(fā)了是什么我收到了一些東西后，才有機會猜你到底發(fā)了什么信息論基礎(chǔ)因此定義互信息量I(X,Y)——信息增益33信息論基礎(chǔ)互信息量I(X,Y)的物理含義H(X)事件X的結(jié)果的不確定性H(X|Y)事件X在輔助條件Y下的結(jié)果的不確定性H(X)-H(X|Y)輔助條件Y對事件X的結(jié)果的不確定性的消除——信息增益ID3和C4.5算法就基于以上信息論基礎(chǔ)互信息量I(X,Y)的物理含義ID3和C4.5算法34ID3算法互信息量I(X,Y)的物理含義輔助條件Y消除了事件X多少的不確定性ID3算法IterativeDichotomiser迭代二分器（為什么？）使用互信息量作為度量標準選擇當前所有分割屬性中，互信息量最大的作為內(nèi)部節(jié)點ID3算法互信息量I(X,Y)的物理含義35ID3算法ID3算法使用互信息量作為度量標準選擇當前所有分割屬性中，互信息量最大的作為內(nèi)部節(jié)點——最能消除不確定性的分割屬性生活工作中的決策（做？不做？）總是優(yōu)先選取最具有決定性意義的輔助條件進行判定如—打不打室外羽毛球？刮風(fēng)是最具有決定意義的因素ID3算法ID3算法生活工作中的決策（做？不做？）36ID3算法ID3算法互信息量最大No.頭痛肌肉痛體溫患流感1是(1)是(1)正常(0)N(0)2是(1)是(1)高(1)Y(1)3是(1)是(1)很高(2)Y(1)4否(0)是(1)正常(0)N(0)5否(0)否(0)高(1)N(0)6否(0)是(1)很高(2)Y(1)7是(1)否(0)高(1)Y(1)決策樹怎么做？誰是父節(jié)點？誰是下一層子節(jié)點？為什么是它？頭-肌肉-體溫頭-體溫-肌肉肌肉-頭-體溫肌肉-體溫-頭體溫-頭-肌肉體溫-肌肉-頭ID3算法ID3算法No.頭痛肌肉痛體溫患流感1是(1)是37例題中各數(shù)據(jù)的屬性及其取值分別為：類別（事件X）：是、否；——x1，x2分割屬性Y1頭痛：是、否；分割屬性Y2肌肉痛：是、否；分割屬性Y3體溫：很高、高、正常選擇全部數(shù)據(jù)記錄，求先驗熵（對類別）：P(x1)=4/7，P(x2)=3/7H(X)=-∑i=1,2P(xi)log2P(xi)=0.985bit后驗熵（對Y1）：y1=是，y2=否P(y1)=4/7，P(y2)=3/7P(x1|y1)=3/4，P(x2|y1)=1/4H(X|y1)=-∑i=1,2P(xi|y1)log2P(xi|y1)=0.811同理，H(X|y2)=0.918ID3算法例題中各數(shù)據(jù)的屬性及其取值分別為：ID3算法38條件熵（對Y1）：H(X|Y1)=∑j=1,2,3

P(yj)H(X|yj)=0.857互信息（對Y1）：I(X,Y1)=H(X)-H(X|Y1)=0.128同理，有：I(X,Y2)=0.006，I(X,Y3)=0.592I(X,Y3)值最大，所以選擇“體溫”作為決策樹的根節(jié)點，將其三個取值分別作為三個分支，并劃分原數(shù)據(jù)集合為三個子集判斷子集中各記錄是否屬于同一類別，若是則在樹上作標記，否則對子集重復(fù)上述步驟ID3算法條件熵（對Y1）：ID3算法39ID3算法（選擇掌握）興趣題~~使用ID3算法構(gòu)建“天氣-外出”決策樹

No.天氣氣溫濕度風(fēng)類別1晴熱高無N2晴熱高有N3多云熱高無P4雨適中高無P5雨冷正常無P6雨冷正常有N7多云冷正常有PNo.天氣氣溫濕度風(fēng)類別8晴適中高無N9晴冷正常無P10雨適中正常無P11晴適中正常有P12多云適中高有P13多云熱正常無P14雨適中高有NID3算法（選擇掌握）興趣題~~使用ID3算法構(gòu)建“天氣40例題中各數(shù)據(jù)的屬性及其取值分別為：類別：P、N；——u1、u2天氣A1：晴、多云、雨；氣溫A2：冷、適中、熱；濕度A3

：高、正常；風(fēng)A4

：有、無選擇全部數(shù)據(jù)記錄，求先驗熵（對類別）：P(u1)=9/14，P(u2)=5/14H(U)=-∑i=1,2P(ui)log2P(ui)=0.94bit后驗熵（對A1）：v1=晴，v2=多云，v3=雨P(guān)(v1)=5/14，P(v2)=4/14，P(v3)=5/14P(u1|v1)=2/5，P(u2|v1)=3/5H(U|v1)=-∑i=1,2P(ui|v1)log2P(ui|v1)=0.97同理，H(U|v2)=0，H(U|v3)=0.97ID3算法（選擇掌握）例題中各數(shù)據(jù)的屬性及其取值分別為：ID3算法（選擇掌握）41條件熵（對A1）：H(U|V)=∑j=1,2,3

P(vj)H(U|vj)=0.69互信息（對A1）：I(A1)=H(U)-H(U|V)=0.25同理，有：I(A2)=0.03，I(A3)=0.15，I(A4)=0.05I(A1)值最大，所以選擇“天氣”作為決策樹的根節(jié)點，將其三個取值分別作為三個分支，并劃分原數(shù)據(jù)集合為三個子集判斷子集中各記錄是否屬于同一類別，若是則在樹上作標記，否則對子集重復(fù)上述步驟ID3算法（選擇掌握）條件熵（對A1）：ID3算法（選擇掌握）42ID3算法每個名字都有它的意義御手洗！@#@！#￥&&￥#……Fox電影公司=狐貍電影公司Paramount電影公司=最牛的電影公司美國總統(tǒng)Bush=美國總統(tǒng)灌木叢ID3為什么是IterativeDichotomiser迭代二分器ID3算法每個名字都有它的意義43ID3算法Iterative（迭代）當前的輸出結(jié)果會返回到程序開始作自變量。

Dichotomiser（二分器）ID3算出的決策樹的“類別”只有“是”、“否”如“流感”決策樹W=F(X,Y,Z)XYZWID3算法Iterative（迭代）W=F(X,Y,Z)XY44ID3算法:主算法從訓(xùn)練集中隨機選擇一個既含正例(Y)又含反例(N)的子集（稱為“窗口”）；用“建樹算法”對當前窗口形成一棵決策樹；對訓(xùn)練集（窗口除外）中例子用所得決策樹進行類別判定，找出錯判的例子；若存在錯判的例子，把它們插入窗口，重復(fù)步驟（2），否則結(jié)束。ID3算法:主算法45ID3算法:建樹算法自頂向下：從父節(jié)點開始，逐層向下貪心：例如“100個數(shù)，挑出5個很小的數(shù)”貪心法在每層總?cè)』バ畔⒘孔钚〉膶傩缘槐ＷC整個決策樹是最優(yōu)的如果各屬性彼此獨立則最優(yōu)如果有相關(guān)性，可能非最優(yōu)遞歸：一個程序在過程中有調(diào)用自身將大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解ID3算法:建樹算法自頂向下：46ID3算法:建樹算法對窗口的所有分割屬性，計算各自的互信息量；選擇互信息最大的特征Ak，作為內(nèi)部節(jié)點把在Ak處取值相同的屬性歸于同一子集，將當前表格的行劃分成不同的子集；判斷子集，若各子集中類別屬性相同，則在決策樹上作相應(yīng)類別標記，并返回否則將子集作為1)中的窗口，進行迭代計算。當全部子集類別屬性均為相同時，則停止建樹。此時形成二分的決策樹，即只有兩個可能結(jié)果ID3算法:建樹算法47ID3算法（選擇掌握）ID3算法用編程語言的實現(xiàn)網(wǎng)絡(luò)鏈接：/view/66ac453a376baf1ffc4fad66.html本機文件：數(shù)據(jù)挖掘中ID3算法實現(xiàn).txtID3算法（選擇掌握）ID3算法用編程語言的實現(xiàn)48ID3算法優(yōu)點算法簡單易于理解缺點偏向分割屬性中取值多的一個只能處理離散屬性ID3不包括樹剪枝，易受噪聲和波動影響不宜對變化的數(shù)據(jù)集進行學(xué)習(xí)ID3算法優(yōu)點缺點49C4.5算法ID3缺點1：偏向分割屬性中取值較多的一個原因：分割屬性取值越多，每個值對應(yīng)的子集規(guī)模越小。極限情況下，每個子集內(nèi)如只有一個單元（表格中的行），則它的信息增益必然最高（對不確定性的消除達到最大）。例如用“身份證號”區(qū)分“相親”，顯然沒有任何意義，但是確實符合ID3算法。解決方法：引入增益比例C4.5算法ID3缺點1：偏向分割屬性中取值較多的一個50C4.5算法對分割屬性Y計算熵此熵與樣本類別無關(guān)（公式中沒有X）此公式衡量了分割屬性Y的均勻性回憶（習(xí)?。┖停▕W羅）例子分布越均勻H(Y)越大，反之越小4份2、2分，4份1、1、1、1分4份1、3分，4份1、1、2分的H（Y）C4.5算法對分割屬性Y計算熵51C4.5算法（不科學(xué)的證明）4份不分H(Y)=04份1、3分H(Y)=0.414份2、2分H(Y)=14份1、1、2分H（Y）=1.54份1、1、1、1分H(Y)=2份數(shù)越多，H(Y)月大份數(shù)一樣的前提下，越平均H(Y)越大C4.5算法（不科學(xué)的證明）4份不分H(Y)=052C4.5算法增益比例G(X,Y)對類別X和分裂屬性Y計算G(X,Y)ID3用信息增量I（X|Y）選擇節(jié)點分割屬性C4.5用增益比例選擇節(jié)點分裂屬性C4.5通過引入分母H(Y)，解決了ID3的最大問題，即偏向分割屬性中取值較多的一個屬性的問題C4.5算法增益比例G(X,Y)C4.5通過引入分母H(Y)53C4.5算法考慮“相親”中的身份證例子在ID3中，分割屬性取值越多，每個值對應(yīng)的子集規(guī)模越小。信息增益極大幾率增高。所以ID3產(chǎn)生了偏向性。在C4.5中，如果分割屬性取值很大，則C4.5算法考慮“相親”中的身份證例子54C4.5算法還有缺陷：C4.5算法還有缺陷：55C4.5算法解決方法：先計算所有的信息增益I（X|Y）對于超過I(X|Y)均值，進一步考量H（Y），選取H（Y）最大的這樣保證相對大C4.5算法解決方法：56排除H(Yi)=0的可能因為H(Yi)=0時Yi分布及其不均勻則I(X|Y)=0排除H(Yi)為身份證可能此時H(Yi)很大G(X|Y)很小排除H(Yi)=0的可能排除H(Yi)為身份證可能57C4.5算法ID3缺點2：只能處理離散分割屬性原因：對于連續(xù)屬性，和缺點1類似。如果把連續(xù)值看成離散值，則會產(chǎn)生分割屬性的偏向問題。解決方法：引入“閾值”。將分割屬性化為C4.5算法ID3缺點2：只能處理離散分割屬性58C4.5算法問題：對于連續(xù)取值的分割屬性，閾值=？方法：在表格中連續(xù)值分割屬性取值對每個計算增益比例，找到最大值即可C4.5算法問題：對于連續(xù)取值的分割屬性，閾值=？59C4.5算法ID3缺點3：無法對未知分割屬性進行處理原因：某分割屬性Y的一個取值由于一些原因未被計入解決方法：平均值代替 概率法代替C4.5算法ID3缺點3：無法對未知分割屬性進行處理60C4.5算法決策樹IF-THEN規(guī)則編程IF年齡>30THEN不見IF年齡<=30AND長相=丑THEN不見IF年齡<=30AND長相=帥or中等AND收入=高THEN見IF年齡<=30AND長相=帥or中等AND收入=中等AND公務(wù)員=是THEN見IF年齡<=30AND長相=帥or中等AND收入=中等AND公務(wù)員=不是THEN不見IF年齡<=30AND長相=帥or中等AND收入=低THEN不見C4.5算法決策樹IF-THEN61C4.5算法ID3缺點3：無樹剪枝，易受噪聲和波動影響解決方法：K階交叉驗證C4.5算法ID3缺點3：無樹剪枝，易受噪聲和波動影響62C4.5算法數(shù)據(jù)集(一組表格)子集1子集2子集3子集4子集5子集6子集7子集8C4.5決策樹1用于生成樹用于驗證K=8的8階交叉驗證錯誤數(shù)1C4.5算法數(shù)據(jù)集子集1子集2子集3子集4子集5子集6子集763C4.5算法數(shù)據(jù)集(一組表格)子集2子集1子集3子集4子集5子集6子集7子集8C4.5決策樹2用于生成樹用于驗證K=8的8階交叉驗證錯誤數(shù)2C4.5算法數(shù)據(jù)集子集2子集1子集3子集4子集5子集6子集764C4.5算法數(shù)據(jù)集(一組表格)子集3子集1子集2子集4子集5子集6子集7子集8C4.5決策樹3用于生成樹用于驗證K=8的8階交叉驗證錯誤數(shù)3C4.5算法數(shù)據(jù)集子集3子集1子集2子集4子集5子集6子集765C4.5算法數(shù)據(jù)集(一組表格)子集4子集1子集2子集3子集5子集6子集7子集8C4.5決策樹4用于生成樹用于驗證K=8的8階交叉驗證錯誤數(shù)4C4.5算法數(shù)據(jù)集子集4子集1子集2子集3子集5子集6子集766C4.5算法數(shù)據(jù)集(一組表格)子集5子集1子集2子集3子集4子集6子集7子集8C4.5決策樹5用于生成樹用于驗證K=8的8階交叉驗證錯誤數(shù)5C4.5算法數(shù)據(jù)集子集5子集1子集2子集3子集4子集6子集767C4.5算法數(shù)據(jù)集(一組表格)子集6子集1子集2子集3子集4子集5子集7子集8C4.5決策樹6用于生成樹用于驗證K=8的8階交叉驗證錯誤數(shù)6C4.5算法數(shù)據(jù)集子集6子集1子集2子集3子集4子集5子集768C4.5算法數(shù)據(jù)集(一組表格)子集7子集1子集2子集3子集4子集5子集6子集8C4.5決策樹7用于生成樹用于驗證K=8的8階交叉驗證錯誤數(shù)7C4.5算法數(shù)據(jù)集子集7子集1子集2子集3子集4子集5子集669C4.5算法數(shù)據(jù)集(一組表格)子集8子集1子集2子集3子集4子集5子集6子集7C4.5決策樹8用于生成樹用于驗證K=8的8階交叉驗證錯誤數(shù)8C4.5算法數(shù)據(jù)集子集8子集1子集2子集3子集4子集5子集670C4.5算法樹1錯1樹2錯2樹3錯3樹4錯4樹5錯5樹6錯6樹7錯7樹8錯8決策樹最終版僅用于小規(guī)模數(shù)據(jù)…C4.5算法樹1錯1樹2錯2樹3錯3樹4錯4樹5錯5樹6錯671C4.5算法（選擇掌握）C4.5算法用C語言的實現(xiàn)網(wǎng)絡(luò)鏈接：/view/4c7d8f82e53a580216fcfe61.html本機文件：C4.5算法的實現(xiàn).docC4.5算法（選擇掌握）C4.5算法用C語言的實現(xiàn)72參考文獻/guoqiangma/article/details/7188639/view/298415.htm/view/96473.htm/view/8be6aa18c5da50e2524d7fb2.html/view/589872.htm/yaoyaozii/article/details/5278576參考文獻/guoqi73參考文獻參考文獻74參考文獻/view/66ac453a376baf1ffc4fad66.html參考文獻/vie75參考文獻《數(shù)據(jù)挖掘原理與算法》科學(xué)出版社邵峰晶等編著；《數(shù)據(jù)挖掘算法與應(yīng)用》北京大學(xué)出版社梁循編著《現(xiàn)代通信原理》清華大學(xué)出版社曹志剛等編著參考文獻《數(shù)據(jù)挖掘原理與算法》科學(xué)出版社邵峰晶等編著；76C4.5算法講解2012.11.29C4.5算法講解2012.11.2977C4.5算法ID3算法知識結(jié)構(gòu)決策樹基礎(chǔ)信息論基礎(chǔ)C4.5算法ID3算法知識結(jié)構(gòu)決策樹基礎(chǔ)信息論基礎(chǔ)78決策樹基礎(chǔ)女孩家長安排相親女孩不厭其煩女孩提出決策樹父母篩選候選男士決策樹基礎(chǔ)女孩家長79決策樹基礎(chǔ)有向無環(huán)二叉/多叉樹父節(jié)點：沒有子節(jié)點的節(jié)點內(nèi)部節(jié)點：有父節(jié)點、子節(jié)點的節(jié)點葉節(jié)點：有父節(jié)點沒有子節(jié)點的節(jié)點父節(jié)點內(nèi)部節(jié)點葉節(jié)點分割屬性+判斷規(guī)則類別標識決策樹基礎(chǔ)有向無環(huán)二叉/多叉樹父節(jié)點葉節(jié)點分割屬性+判斷80決策樹基礎(chǔ)父節(jié)點內(nèi)部節(jié)點葉節(jié)點（類別標識）（分割屬性+判斷規(guī)則）決策樹基礎(chǔ)父節(jié)點葉節(jié)點（分割屬性+判斷規(guī)則）81決策樹基礎(chǔ)訓(xùn)練集：數(shù)據(jù)的集合，用于生成樹（模型）測試集：用于測試樹（模型）的性能決策樹作用：通過訓(xùn)練集算法指導(dǎo)下生成決策樹新數(shù)據(jù)進行劃分否則是“三拍”決策訓(xùn)練集算法決策樹新數(shù)據(jù)決策決策樹基礎(chǔ)訓(xùn)練集：數(shù)據(jù)的集合，用于生成樹（模型）訓(xùn)練集算法決82決策樹基礎(chǔ)實例No.頭痛肌肉痛體溫患流感1是(1)是(1)正常(0)N(0)2是(1)是(1)高(1)Y(1)3是(1)是(1)很高(2)Y(1)4否(0)是(1)正常(0)N(0)5否(0)否(0)高(1)N(0)6否(0)是(1)很高(2)N(1)7是(1)否(0)高(1)Y(1)決策樹怎么做？誰是父節(jié)點？誰是下一層子節(jié)點？為什么是它？頭-肌肉-體溫頭-體溫-肌肉肌肉-頭-體溫肌肉-體溫-頭體溫-頭-肌肉體溫-肌肉-頭三拍決策決策樹基礎(chǔ)實例No.頭痛肌肉痛體溫患流感1是(1)是(1)83決策樹基礎(chǔ)……@）￥——JK)I*&^Fkl9*^&%*&UIDOFGJNo.天氣氣溫濕度風(fēng)類別1晴熱高無N2晴熱高有N3多云熱高無P4雨適中高無P5雨冷正常無P6雨冷正常有N7多云冷正常有PNo.天氣氣溫濕度風(fēng)類別8晴適中高無N9晴冷正常無P10雨適中正常無P11晴適中正常有P12多云適中高有P13多云熱正常無P14雨適中高有N決策樹基礎(chǔ)……@）￥——JK)I*&^Fkl9*^&%*&84怎么生成好的？哪個好？種決策樹方案決策樹基礎(chǔ)N個分割屬性的訓(xùn)練集怎么生成好的？哪個好？種決策85決策樹基礎(chǔ)好的決策樹：（MDL準則下為例）MinimumDescriptionLength訓(xùn)練集中大多數(shù)數(shù)據(jù)符合這棵樹例外的數(shù)據(jù)單獨編碼描述決策樹用的bit描述例外數(shù)據(jù)用bit哪個好？決策樹基礎(chǔ)描述決策樹用的bit描述例外數(shù)據(jù)用bit哪個好？86決策樹基礎(chǔ)（選擇掌握）如何描述決策樹體溫頭痛很高正常高YNYN否是流感決策樹深度優(yōu)先遍歷決策樹用1標注父子節(jié)點用0標注葉節(jié)點記錄分割屬性1,體溫,0,Y,1,頭疼,0,Y,0,N,0,N層次少+分枝少占用存儲空間小決策計算時間快決策樹基礎(chǔ)（選擇掌握）如何描述決策樹體溫頭痛很高正常高YNY87決策樹基礎(chǔ)C4.5算法ID3算法決策樹基礎(chǔ)信息論基礎(chǔ)選哪個？？怎么生成好的？NextOne!決策樹基礎(chǔ)C4.5算法ID3算法決策樹基礎(chǔ)信息論基礎(chǔ)選哪個？88信息論基礎(chǔ)辨析先驗概率信息量信息論基礎(chǔ)辨析89信息論基礎(chǔ)—先驗概率對事件X的某一結(jié)果進行討論：例：在沒有任何幫助的情況下，奧/羅誰贏的概率P（x1=奧）=P（x2=羅）信息論基礎(chǔ)—先驗概率對事件X的某一結(jié)果進行討論：90信息論基礎(chǔ)—信息量信息論基礎(chǔ)—信息量91信息論基礎(chǔ)辨析先驗概率信息量先驗熵信息論基礎(chǔ)辨析92信息論基礎(chǔ)先驗熵——自信息量——熵H（X）原意：熱力學(xué)中形容失序現(xiàn)象和復(fù)雜程度現(xiàn)意：一個事件X的平均信息量熵越大，不確定性就越大，正確估計其值的可能性就越小。XXX熵===XXX的信息量的加權(quán)信息論基礎(chǔ)先驗熵——自信息量——熵H（X）93信息論基礎(chǔ)先驗熵——自信息量——熵H（X）原意：熱力學(xué)中形容失序現(xiàn)象和復(fù)雜程度現(xiàn)意：通信中一個事件的平均信息量信息論基礎(chǔ)先驗熵——自信息量——熵H（X）94信息論基礎(chǔ)熵H(X)——自信息量科學(xué)發(fā)展觀指導(dǎo)下的和諧社會，失序現(xiàn)象和復(fù)雜程度遠低于萬惡的資本主義社會！事件的可能結(jié)果發(fā)生幾率越相近，則熵越大信息論基礎(chǔ)熵H(X)——自信息量95信息論基礎(chǔ)辨析先驗概率信息量先驗熵后驗概率信息論基礎(chǔ)辨析96信息論基礎(chǔ)對事件X的某一結(jié)果進行討論：例：已知民意調(diào)查結(jié)果，猜奧/羅誰贏的概率P（x1=奧|y1=奧領(lǐng)先）>P（x2=羅|y1=奧領(lǐng)先）信息論基礎(chǔ)對事件X的某一結(jié)果進行討論：97信息論基礎(chǔ)辨析先驗概率信息量先驗熵后驗概率后驗熵信息論基礎(chǔ)辨析98信息論基礎(chǔ)熵H(X)原意：熱力學(xué)中形容失序現(xiàn)象和復(fù)雜程度現(xiàn)意：一個事件X的平均信息量熵越大，不確定性就越大，正確估計其值的可能性就越小。XXX熵===XXX的信息量的加權(quán)后驗熵=后驗概率的信息量的加權(quán)信息論基礎(chǔ)熵H(X)99信息論基礎(chǔ)對事件X的全部結(jié)果在某一輔助條件下進行討論：信息論基礎(chǔ)對事件X的全部結(jié)果在某一輔助條件下進行討論：100信息論基礎(chǔ)對事件X的全部結(jié)果在某一輔助條件下進行討論：例：在民意調(diào)查的結(jié)果幫助下（y1）計算2012年誰是總統(tǒng)的不確定性H(誰當選|民調(diào)奧領(lǐng)先)=？信息論基礎(chǔ)對事件X的全部結(jié)果在某一輔助條件下進行討論：101信息論基礎(chǔ)辨析先驗概率信息量熵=自信息量后驗概率后驗墑條件熵信息論基礎(chǔ)辨析102信息論基礎(chǔ)對事件X的全部結(jié)果在全部輔助條件下進行討論：信息論基礎(chǔ)對事件X的全部結(jié)果在全部輔助條件下進行討論：103信息論基礎(chǔ)條件熵即對后驗墑的所有可能輔助條件Yj累計信息論基礎(chǔ)條件熵104信息論基礎(chǔ)辨析先驗概率信息量熵=自信息量后驗概率后驗墑條件熵信息論基礎(chǔ)辨析105信息論基礎(chǔ)辨析信息量熵=自信息量先驗概率后驗概率后驗墑條件熵互信息量信息論基礎(chǔ)辨析106信息論基礎(chǔ)對于條件墑H(X|Y)由于輔助條件Y的存在由熵——不確定程度——事件X的平均信息量所以一般情況下H(X)=<H(X|Y)I(X|Y)=H(X)-H(X|Y)信息論基礎(chǔ)對于條件墑H(X|Y)107信息論基礎(chǔ)信息論基礎(chǔ)108信息論基礎(chǔ)因此定義互信息量I(X,Y)——信息增益I(X,Y)信息增益才是接收端獲得的信息量我沒收到任何東西前，我不知道你發(fā)了是什么我收到了一些東西后，才有機會猜你到底發(fā)了什么信息論基礎(chǔ)因此定義互信息量I(X,Y)——信息增益109信息論基礎(chǔ)互信息量I(X,Y)的物理含義H(X)事件X的結(jié)果的不確定性H(X|Y)事件X在輔助條件Y下的結(jié)果的不確定性H(X)-H(X|Y)輔助條件Y對事件X的結(jié)果的不確定性的消除——信息增益ID3和C4.5算法就基于以上信息論基礎(chǔ)互信息量I(X,Y)的物理含義ID3和C4.5算法110ID3算法互信息量I(X,Y)的物理含義輔助條件Y消除了事件X多少的不確定性ID3算法IterativeDichotomiser迭代二分器（為什么？）使用互信息量作為度量標準選擇當前所有分割屬性中，互信息量最大的作為內(nèi)部節(jié)點ID3算法互信息量I(X,Y)的物理含義111ID3算法ID3算法使用互信息量作為度量標準選擇當前所有分割屬性中，互信息量最大的作為內(nèi)部節(jié)點——最能消除不確定性的分割屬性生活工作中的決策（做？不做？）總是優(yōu)先選取最具有決定性意義的輔助條件進行判定如—打不打室外羽毛球？刮風(fēng)是最具有決定意義的因素ID3算法ID3算法生活工作中的決策（做？不做？）112ID3算法ID3算法互信息量最大No.頭痛肌肉痛體溫患流感1是(1)是(1)正常(0)N(0)2是(1)是(1)高(1)Y(1)3是(1)是(1)很高(2)Y(1)4否(0)是(1)正常(0)N(0)5否(0)否(0)高(1)N(0)6否(0)是(1)很高(2)Y(1)7是(1)否(0)高(1)Y(1)決策樹怎么做？誰是父節(jié)點？誰是下一層子節(jié)點？為什么是它？頭-肌肉-體溫頭-體溫-肌肉肌肉-頭-體溫肌肉-體溫-頭體溫-頭-肌肉體溫-肌肉-頭ID3算法ID3算法No.頭痛肌肉痛體溫患流感1是(1)是113例題中各數(shù)據(jù)的屬性及其取值分別為：類別（事件X）：是、否；——x1，x2分割屬性Y1頭痛：是、否；分割屬性Y2肌肉痛：是、否；分割屬性Y3體溫：很高、高、正常選擇全部數(shù)據(jù)記錄，求先驗熵（對類別）：P(x1)=4/7，P(x2)=3/7H(X)=-∑i=1,2P(xi)log2P(xi)=0.985bit后驗熵（對Y1）：y1=是，y2=否P(y1)=4/7，P(y2)=3/7P(x1|y1)=3/4，P(x2|y1)=1/4H(X|y1)=-∑i=1,2P(xi|y1)log2P(xi|y1)=0.811同理，H(X|y2)=0.918ID3算法例題中各數(shù)據(jù)的屬性及其取值分別為：ID3算法114條件熵（對Y1）：H(X|Y1)=∑j=1,2,3

P(yj)H(X|yj)=0.857互信息（對Y1）：I(X,Y1)=H(X)-H(X|Y1)=0.128同理，有：I(X,Y2)=0.006，I(X,Y3)=0.592I(X,Y3)值最大，所以選擇“體溫”作為決策樹的根節(jié)點，將其三個取值分別作為三個分支，并劃分原數(shù)據(jù)集合為三個子集判斷子集中各記錄是否屬于同一類別，若是則在樹上作標記，否則對子集重復(fù)上述步驟ID3算法條件熵（對Y1）：ID3算法115ID3算法（選擇掌握）興趣題~~使用ID3算法構(gòu)建“天氣-外出”決策樹

No.天氣氣溫濕度風(fēng)類別1晴熱高無N2晴熱高有N3多云熱高無P4雨適中高無P5雨冷正常無P6雨冷正常有N7多云冷正常有PNo.天氣氣溫濕度風(fēng)類別8晴適中高無N9晴冷正常無P10雨適中正常無P11晴適中正常有P12多云適中高有P13多云熱正常無P14雨適中高有NID3算法（選擇掌握）興趣題~~使用ID3算法構(gòu)建“天氣116例題中各數(shù)據(jù)的屬性及其取值分別為：類別：P、N；——u1、u2天氣A1：晴、多云、雨；氣溫A2：冷、適中、熱；濕度A3

：高、正常；風(fēng)A4

：有、無選擇全部數(shù)據(jù)記錄，求先驗熵（對類別）：P(u1)=9/14，P(u2)=5/14H(U)=-∑i=1,2P(ui)log2P(ui)=0.94bit后驗熵（對A1）：v1=晴，v2=多云，v3=雨P(guān)(v1)=5/14，P(v2)=4/14，P(v3)=5/14P(u1|v1)=2/5，P(u2|v1)=3/5H(U|v1)=-∑i=1,2P(ui|v1)log2P(ui|v1)=0.97同理，H(U|v2)=0，H(U|v3)=0.97ID3算法（選擇掌握）例題中各數(shù)據(jù)的屬性及其取值分別為：ID3算法（選擇掌握）117條件熵（對A1）：H(U|V)=∑j=1,2,3

P(vj)H(U|vj)=0.69互信息（對A1）：I(A1)=H(U)-H(U|V)=0.25同理，有：I(A2)=0.03，I(A3)=0.15，I(A4)=0.05I(A1)值最大，所以選擇“天氣”作為決策樹的根節(jié)點，將其三個取值分別作為三個分支，并劃分原數(shù)據(jù)集合為三個子集判斷子集中各記錄是否屬于同一類別，若是則在樹上作標記，否則對子集重復(fù)上述步驟ID3算法（選擇掌握）條件熵（對A1）：ID3算法（選擇掌握）118ID3算法每個名字都有它的意義御手洗！@#@！#￥&&￥#……Fox電影公司=狐貍電影公司Paramount電影公司=最牛的電影公司美國總統(tǒng)Bush=美國總統(tǒng)灌木叢ID3為什么是IterativeDichotomiser迭代二分器ID3算法每個名字都有它的意義119ID3算法Iterative（迭代）當前的輸出結(jié)果會返回到程序開始作自變量。

Dichotomiser（二分器）ID3算出的決策樹的“類別”只有“是”、“否”如“流感”決策樹W=F(X,Y,Z)XYZWID3算法Iterative（迭代）W=F(X,Y,Z)XY120ID3算法:主算法從訓(xùn)練集中隨機選擇一個既含正例(Y)又含反例(N)的子集（稱為“窗口”）；用“建樹算法”對當前窗口形成一棵決策樹；對訓(xùn)練集（窗口除外）中例子用所得決策樹進行類別判定，找出錯判的例子；若存在錯判的例子，把它們插入窗口，重復(fù)步驟（2），否則結(jié)束。ID3算法:主算法121ID3算法:建樹算法自頂向下：從父節(jié)點開始，逐層向下貪心：例如“100個數(shù)，挑出5個很小的數(shù)”貪心法在每層總?cè)』バ畔⒘孔钚〉膶傩缘槐ＷC整個決策樹是最優(yōu)的如果各屬性彼此獨立則最優(yōu)如果有相關(guān)性，可能非最優(yōu)遞歸：一個程序在過程中有調(diào)用自身將大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解ID3算法:建樹算法自頂向下：122ID3算法:建樹算法對窗口的所有分割屬性，計算各自的互信息量；選擇互信息最大的特征Ak，作為內(nèi)部節(jié)點把在Ak處取值相同的屬性歸于同一子集，將當前表格的行劃分成不同的子集；判斷子集，若各子集中類別屬性相同，則在決策樹上作相應(yīng)類別標記，并返回否則將子集作為1)中的窗口，進行迭代計算。當全部子集類別屬性均為相同時，則停止建樹。此時形成二分的決策樹，即只有兩個可能結(jié)果ID3算法:建樹算法123ID3算法（選擇掌握）ID3算法用編程語言的實現(xiàn)網(wǎng)絡(luò)鏈接：/view/66ac453a376baf1ffc4fad66.html本機文件：數(shù)據(jù)挖掘中ID3算法實現(xiàn).txtID3算法（選擇掌握）ID3算法用編程語言的實現(xiàn)124ID3算法優(yōu)點算法簡單易于理解缺點偏向分割屬性中取值多的一個只能處理離散屬性ID3不包括樹剪枝，易受噪聲和波動影響不宜對變化的數(shù)據(jù)集進行學(xué)習(xí)ID3算法優(yōu)點缺點125C4.5算法ID3缺點1：偏向分割屬性中取值較多的一個原因：分割屬性取值越多，每個值對應(yīng)的子集規(guī)模越小。極限情況下，每個子集內(nèi)如只有一個單元（表格中的行），則它的信息增益必然最高（對不確定性的消除達到最大）。例如用“身份證號”區(qū)分“相親”，顯然沒有任何意義，但是確實符合ID3算法。解決方法：引入增益比例C4.5算法ID3缺點1：偏向分割屬性中取值較多的一個126C4.5算法對分割屬性Y計算熵此熵與樣本類別無關(guān)（公式中沒有X）此公式衡量了分割屬性Y的均勻性回憶（習(xí)薄）和（奧羅）例子分布越均勻H(Y)越大，反之越小4份2、2分，4份1、1、1、1分4份1、3分，4份1、1、2分的H（Y）C4.5算法對分割屬性Y計算熵127C4.5算法（不科學(xué)的證明）4份不分H(Y)=04份1、3分H(Y)=0.414份2、2分H(Y)=14份1、1、2分H（Y）=1.54份1、1、1、1分H(Y)=2份數(shù)越多，H(Y)月大份數(shù)一樣的前提下，越平均H(Y)越大C4.5算法（不科學(xué)的證明）4份不分H(Y)=0128C4.5算法增益比例G(X,Y)對類別X和分裂屬性Y計算G(X,Y)ID3用信息增量I（X|Y）選擇節(jié)點分割屬性C4.5用增益比例選擇節(jié)點分裂屬性C4.5通過引入分母H(Y)，解決了ID3的最大問題，即偏向分割屬性中取值較多的一個屬性的問題C4.5算法增益比例G(X,Y)C4.5通過引入分母H(Y)129C4.5算法考慮“相親”中的身份證例子在ID3中，分割屬性取值越多，每個值對應(yīng)的子集規(guī)模越小。信息增益極大幾率增高。所以ID3產(chǎn)生了偏向性。在C4.5中，如果分割屬性取值很大，則C4.5算法考慮“相親”中的身份證例子130C4.5算法還有缺陷：C4.5算法還有缺陷：131C4.5算法解決方法：先計算所有的信息增益I（X|Y）對于超過I(X|Y)均值，進一步考量H（Y），選取H（Y）最大的這樣保證相對大C4.5算法解決方法：132排除H(Yi)=0的可能因為H(Yi)=0時Yi分布及其不均勻則I(X|Y)=0排除H(Yi)為身份證可能此時H(Yi)很大G(X|Y)很小排除H(Yi)=0的可能排除H(Yi)為身份證可能133C4.5算法ID3缺點2：只能處理離散分割屬性原因：對于連續(xù)屬性，和缺點1類似。如果把連續(xù)值看成離散值，則會產(chǎn)生分割屬性的偏向問題。解決方法：引入“閾值”。將分割屬性化為C4.5算法ID3缺點2：只能處理離散分割屬性134C4.5算法問題：對于連續(xù)取值的分割屬性，閾值=？方法：在表格中連續(xù)值分割屬性取值對每個計算增益比例，找到最大值即可C4.5算法問題：對于連續(xù)取值的分割屬性，閾值=？135C4.5算法ID3缺點3：無法對未知分割屬性進行處理原因：某分割屬性Y的一個取值由于一些原因未被計入解決方法