數(shù)學(xué)建模決策樹PPT精品文檔

1、1決策樹2概要n簡介n決策樹表示法n決策樹學(xué)習(xí)的適用問題n基本的決策樹學(xué)習(xí)算法n決策樹學(xué)習(xí)中的假想空間搜索n決策樹學(xué)習(xí)的常見問題3簡介n決策樹方法是應(yīng)用最廣的歸納推理算法之一n一種逼近離散值目標(biāo)函數(shù)的方法n對(duì)噪聲數(shù)據(jù)有很好的健壯性且能學(xué)習(xí)析取表達(dá)式4決策樹的表示法n決策樹通過把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來分類實(shí)例，葉子節(jié)點(diǎn)即為實(shí)例所屬的分類。樹上的每一個(gè)節(jié)點(diǎn)說明了對(duì)實(shí)例的某個(gè)屬性的測試，并且該節(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值5圖6表達(dá)式7決策樹學(xué)習(xí)的適用問題n實(shí)例是由屬性-值對(duì)表示的n目標(biāo)函數(shù)具有離散的輸出值n訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤n訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例8屬性選擇n構(gòu)

2、造好的決策樹的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩?。?duì)于同樣一組例子，可以有很多決策樹能符合這組例子。人們研究出，一般情況下或具有較大概率地說，樹越小則樹的預(yù)測能力越強(qiáng)。要構(gòu)造盡可能小的決策樹，關(guān)鍵在于選擇恰當(dāng)?shù)倪壿嬇袛嗷驅(qū)傩?。由于?gòu)造最小的樹是NP-難問題，因此只能采取用啟發(fā)式策略選擇好的邏輯判斷或?qū)傩浴?9用熵度量樣例的均一性（純度）n熵的定義n舉例1011用信息增益度量期望熵最低12舉例1314151617ID3算法(Iterative Dichotomiser 3)創(chuàng)建樹的Root結(jié)點(diǎn)如果Examples都為正，那么返回label=+中的單結(jié)點(diǎn)Root如果Examples都為反，那么返回

3、lable=-單結(jié)點(diǎn)樹Root如果Attributes為空，那么返回單節(jié)點(diǎn)樹Root，lable=Examples中最普遍的目標(biāo)屬性值否則開始AAttributes中分類能力最好的屬性Root的決策屬性A對(duì)于每個(gè)可能值 在Root下加一個(gè)新的分支對(duì)應(yīng)測試A=vi令Example-vi為Examples中滿足A屬性值為vi的子集如果Examples-vi為空在這個(gè)新分支下加一個(gè)葉子結(jié)點(diǎn)，節(jié)點(diǎn)的lable=Examples中最普遍的 目標(biāo)屬性值否則在這個(gè)新分支下加一個(gè)子樹ID3(example-vi,target-attribute,attributes-|A|結(jié)束返回 Root18Example

4、 2nFactors affecting sunburnName Hair Height Weight Lotion Result Sarah Blonde Average Light No Sunburned Dana Blonde Tall Average Yes None Alex Brown Short Average Yes None Annie Blonde Short Average No Sunburned Emily Red Average Heavy No Sunburned Pete Brown Tall Heavy No None John Brown Average

5、Heavy No None Kate Blonde Short Light Yes None 19nS = 3+, 5-Entropy(S) = -(3/8)log2(3/8) (5/8)log2(5/8)= 0.95443Find IG for all 4 attributes: Hair, Height, Weight, LotionnFor attribute Hair:Values(Hair) : Blonde, Brown, RedS = 3+,5-SBlonde = 2+,2- E(SBlonde) = 1SBrown = 0+,3-E(SBrown) = 0 SRed = 1+,

6、0-E(SRed) = 0Gain(S,Hair) = 0.95443 (4/8)*1 + (3/8)*0 + (1/8)*0= 0.4544320nFor attribute Height:Values(Height) : Average, Tall, ShortSAverage = 2+,1- E(SAverage) = 0.91829STall = 0+,2-E(STall) = 0 SShort = 1+,2-E(SShort) = 0.91829Gain(S,Height) = 0.95443 (3/8)*0.91829 + (2/8)*0 + (3/8)*0.91829= 0.26

7、571nFor attribute Weight:Values(Weight) : Light, Average, HeavySLight = 1+,1- E(SLight) = 1SAverage = 1+,2- E(SAverage) = 0.91829 SHeavy = 1+,2-E(SHeavy) = 0.91829Gain(S,Weight) = 0.95443 (2/8)*1 + (3/8)*0.91829 + (3/8)*0.91829= 0.01571nFor attribute Lotion:Values(Lotion) : Yes, NoSYes = 0+,3- E(SYe

8、s) = 0SNo = 3+,2-E(SNo) = 0.97095Gain(S,Lotion) = 0.95443 (3/8)*0 + (5/8)*0.97095= 0.0157121Gain(S,Hair) = 0.45443Gain(S,Height) = 0.26571Gain(S,Weight) = 0.01571Gain(S,Lotion) = 0.3475Gain(S,Hair) is maximum, so it is considered as the root nodeNameHairHeightWeightLotionSunburnedSarahBlondeAverageL

9、ightNoYesDanaBlondeTallAverageYesNoAlexBrownShortAverageYesNoAnnieBlondeShortAverageNoYesEmilyRedAverageHeavyNoYesPeteBrownTallHeavyNoNoJohnBrownAverageHeavyNoNoKatieBlondeShortLightYesNoHairBlondeRedBrownSarah, Dana,Annie, KatieEmilyAlex, Pete, JohnSunburnedNotSunburned?22Repeating again:S = Sarah,

10、 Dana, Annie, KatieS: 2+,2-Entropy(S) = 1Find IG for remaining 3 attributes Height, Weight, LotionnFor attribute Height:Values(Height) : Average, Tall, ShortS = 2+,2-SAverage = 1+,0- E(SAverage) = 0STall = 0+,1-E(STall) = 0 SShort = 1+,1-E(SShort) = 1Gain(S,Height) = 1 (1/4)*0 + (1/4)*0 + (2/4)*1= 0

11、.5NameHairHeightWeightLotionSunburnedSarahBlondeAverageLightNoYesDanaBlondeTallAverageYesNoAnnieBlondeShortAverageNoYesKatieBlondeShortLightYesNo23nFor attribute Weight:Values(Weight) : Average, LightS = 2+,2-SAverage = 1+,1- E(SAverage) = 1SLight = 1+,1-E(SLight) = 1 Gain(S,Weight) = 1 (2/4)*1 + (2

12、/4)*1= 0nFor attribute Lotion:Values(Lotion) : Yes, NoS = 2+,2-SYes = 0+,2- E(SYes) = 0SNo = 2+,0- E(SNo) = 0 Gain(S,Lotion) = 1 (2/4)*0 + (2/4)*0= 1Therefore, Gain(S,Lotion) is maximum24nIn this case, the final decision tree will beHairBlondeRedBrownSunburnedNotSunburnedLotionYNSunburnedNotSunburne

13、d25C4.5nC4.5是對(duì)ID3的改進(jìn)算法q對(duì)連續(xù)值的處理q對(duì)決策樹進(jìn)行剪枝26決策樹學(xué)習(xí)中的假設(shè)空間搜索n假設(shè)空間nID3算法中的假設(shè)空間包含所有的決策樹n當(dāng)遍歷決策樹空間時(shí)，ID3僅維護(hù)單一的當(dāng)前假設(shè)。n基本的ID3算法在搜索中不進(jìn)行回溯nID3算法在搜索的每一步都使用當(dāng)前的所有訓(xùn)練樣例27決策樹學(xué)習(xí)的常見問題(1) n避免過度擬合數(shù)據(jù)q基本的決策樹構(gòu)造算法沒有考慮噪聲，生成的決策樹完全與訓(xùn)練例子擬合。有噪聲情況下，完全擬合將導(dǎo)致過分?jǐn)M合（overfitting），即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測性能。 28Overfitting in Decision Tree Learni

14、ng29解決方法n剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹得到簡化而變得更容易理解。q把訓(xùn)練集分為兩個(gè)部分用于構(gòu)建決策樹的部分和用于剪枝的部分(測試集).q對(duì)于構(gòu)建好的樹,對(duì)于每一個(gè)內(nèi)部節(jié)點(diǎn)在測試集上計(jì)算兩種誤差n不剪枝時(shí)的誤差n把這個(gè)內(nèi)部節(jié)點(diǎn)作為葉子的誤差q如果進(jìn)行剪枝誤差變小,那么就進(jìn)行剪枝.n理論上講，向后剪枝好于向前剪枝，但計(jì)算復(fù)雜度大。30決策樹學(xué)習(xí)的常見問題（2）n合并連續(xù)值屬性n屬性選擇的其他度量標(biāo)準(zhǔn)q信息增益比（gain ratio）、Gini-index、距離度量（distance measure）等。不同的度量有不同的效果，特別是對(duì)于多值屬性。31決策樹的優(yōu)點(diǎn)n可以生成可以

15、理解的規(guī)則；n計(jì)算量相對(duì)來說不是很大；n可以處理連續(xù)和離散字段；n可以處理殘缺數(shù)據(jù)n決策樹可以清晰的顯示哪些字段比較重要32不足之處n對(duì)連續(xù)性的字段比較難預(yù)測n當(dāng)類別太多時(shí)，錯(cuò)誤可能會(huì)增加的比較快n一般的算法分類的時(shí)候，只是根據(jù)一個(gè)屬性來分類。n不是全局最優(yōu)。33隨機(jī)森林的定義n隨機(jī)森林是一個(gè)樹型分類器h(x,k),k=1,的集合。其中元分類器h(x,k)是決策樹；森林的輸出采用簡單多數(shù)投票法（針對(duì)分類）或單顆樹輸出結(jié)果的簡單平均（針對(duì)回歸）得到。34隨機(jī)森林算法n隨機(jī)選取訓(xùn)練樣本集：使用Bagging方法形成每顆樹的訓(xùn)練集n隨機(jī)選取分裂屬性集：假設(shè)共有M個(gè)屬性，指定一個(gè)屬性數(shù)FM，在每個(gè)內(nèi)部結(jié)點(diǎn)，從M個(gè)屬性中隨機(jī)抽取F個(gè)屬性作分裂屬性集，以這F個(gè)屬性上最好的分裂方式對(duì)結(jié)點(diǎn)進(jìn)行分裂（在整個(gè)森林的生長過程中， F的值一般維持不變）n每顆樹任其生長，不進(jìn)行剪枝35隨機(jī)森林算法nBagging(Breiman,1996) q在訓(xùn)練的每一輪中，均從原始樣本集S中有放回地隨機(jī)抽取訓(xùn)練樣本集T（T的樣本個(gè)數(shù)同S），這樣一個(gè)初始樣本在某輪訓(xùn)練中可能出現(xiàn)多次或根本不出現(xiàn)（ S中每個(gè)樣本未被抽取的概率為(1-1/|S|)|S|0