數(shù)學(xué)建模決策樹PPT資料

數(shù)學(xué)(shùxué)建模決策樹第一頁，共36頁。概要(gàiyào)簡(jiǎn)介決策樹表示法決策樹學(xué)習(xí)的適用問題根本的決策樹學(xué)習(xí)算法決策樹學(xué)習(xí)中的假想空間(kōngjiān)搜索決策樹學(xué)習(xí)的常見問題第二頁，共36頁。簡(jiǎn)介(jiǎnjiè)決策樹方法是應(yīng)用最廣的歸納推理(ɡuīnàtuīlǐ)算法之一一種逼近離散值目標(biāo)函數(shù)的方法對(duì)噪聲數(shù)據(jù)有很好的健壯性且能學(xué)習(xí)析取表達(dá)式第三頁，共36頁。決策樹的表示法決策樹通過把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來分類實(shí)例，葉子節(jié)點(diǎn)即為實(shí)例所屬的分類。樹上的每一個(gè)(yīɡè)節(jié)點(diǎn)說明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試，并且該節(jié)點(diǎn)的每一個(gè)(yīɡè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)(yīɡè)可能值第四頁，共36頁。圖第五頁，共36頁。表達(dá)式第六頁，共36頁。決策樹學(xué)習(xí)的適用(shìyòng)問題實(shí)例是由屬性-值對(duì)表示的目標(biāo)函數(shù)(hánshù)具有離散的輸出值訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例第七頁，共36頁。屬性(shǔxìng)選擇構(gòu)造好的決策樹的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩?shǔxìng)。對(duì)于同樣一組例子，可以有很多決策樹能符合這組例子。人們研究出，一般情況下或具有較大概率地說，樹越小那么樹的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹，關(guān)鍵在于選擇恰當(dāng)?shù)倪壿嬇袛嗷驅(qū)傩?shǔxìng)。由于構(gòu)造最小的樹是NP-難問題，因此只能采取用啟發(fā)式策略選擇好的邏輯判斷或?qū)傩?shǔxìng)。第八頁，共36頁。用熵度量(dùliàng)樣例的均一性〔純度〕熵的定義(dìngyì)舉例第九頁，共36頁。第十頁，共36頁。用信息(xìnxī)增益度量期望熵最低第十一頁，共36頁。舉例(jǔlì)第十二頁，共36頁。第十三頁，共36頁。第十四頁，共36頁。第十五頁，共36頁。第十六頁，共36頁。ID3算法(suànfǎ)(IterativeDichotomiser3)創(chuàng)立樹的Root結(jié)點(diǎn)如果Examples都為正，那么返回label=+中的單結(jié)點(diǎn)Root如果Examples都為反，那么返回lable=-單結(jié)點(diǎn)樹Root如果Attributes為空，那么返回單節(jié)點(diǎn)樹Root，lable=Examples中最普遍的目標(biāo)屬性值否那么開始 AAttributes中分類能力最好的屬性 Root的決策屬性A 對(duì)于每個(gè)可能值 在Root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=vi 令Example-vi為Examples中滿足A屬性值為vi的子集 如果Examples-vi為空 在這個(gè)(zhège)新分支下加一個(gè)葉子結(jié)點(diǎn)，節(jié)點(diǎn)的lable=Examples中最普遍的 目標(biāo)屬性值 否那么在這個(gè)(zhège)新分支下加一個(gè)子樹ID3(example-vi,target- attribute,attributes-|A|結(jié)束返回Root第十七頁，共36頁。Example2Factorsaffectingsunburn第十八頁，共36頁。S=[3+,5-]Entropy(S)=-(3/8)log2(3/8)–(5/8)log2(5/8) =0.95443FindIGforall4attributes:Hair,Height,Weight,LotionForattribute‘Hair’:Values(Hair):[Blonde,Brown,Red]S=[3+,5-]SBlonde=[2+,2-] E(SBlonde)=1SBrown=[0+,3-] E(SBrown)=0SRed=[1+,0-] E(SRed)=0Gain(S,Hair)=0.95443–[(4/8)*1+(3/8)*0+(1/8)*0] =0.45443第十九頁，共36頁。Forattribute‘Height’:Values(Height):[Average,Tall,Short]SAverage=[2+,1-] E(SAverage)=0.91829STall=[0+,2-] E(STall)=0SShort=[1+,2-] E(SShort)=0.91829Gain(S,Height)=0.95443–[(3/8)*0.91829+(2/8)*0+(3/8)*0.91829] =0.26571Forattribute‘Weight’:Values(Weight):[Light,Average,Heavy]SLight=[1+,1-] E(SLight)=1SAverage=[1+,2-] E(SAverage)=0.91829SHeavy=[1+,2-] E(SHeavy)=0.91829Gain(S,Weight)=0.95443–[(2/8)*1+(3/8)*0.91829+(3/8)*0.91829] =0.01571Forattribute‘Lotion’:Values(Lotion):[Yes,No]SYes=[0+,3-] E(SYes)=0SNo=[3+,2-] E(SNo)=0.97095Gain(S,Lotion)=0.95443–[(3/8)*0+(5/8)*0.97095] =0.01571第二十頁，共36頁。Gain(S,Hair)=0.45443Gain(S,Height)=0.26571Gain(S,Weight)=0.01571Gain(S,Lotion)=0.3475Gain(S,Hair)ismaximum,soitisconsideredastherootnodeNameHairHeightWeightLotionSunburnedSarahBlondeAverageLightNoYesDanaBlondeTallAverageYesNoAlexBrownShortAverageYesNoAnnieBlondeShortAverageNoYesEmilyRedAverageHeavyNoYesPeteBrownTallHeavyNoNoJohnBrownAverageHeavyNoNoKatieBlondeShortLightYesNoHairBlondeRedBrown[Sarah,Dana,Annie,Katie][Emily][Alex,Pete,John]SunburnedNotSunburned?第二十一頁，共36頁。Repeatingagain:S=[Sarah,Dana,Annie,Katie]S:[2+,2-]Entropy(S)=1FindIGforremaining3attributesHeight,Weight,LotionForattribute‘Height’:Values(Height):[Average,Tall,Short]S=[2+,2-]SAverage=[1+,0-] E(SAverage)=0STall=[0+,1-] E(STall)=0SShort=[1+,1-] E(SShort)=1Gain(S,Height)=1–[(1/4)*0+(1/4)*0+(2/4)*1] =0.5NameHairHeightWeightLotionSunburnedSarahBlondeAverageLightNoYesDanaBlondeTallAverageYesNoAnnieBlondeShortAverageNoYesKatieBlondeShortLightYesNo第二十二頁，共36頁。Forattribute‘Weight’:Values(Weight):[Average,Light]S=[2+,2-]SAverage=[1+,1-] E(SAverage)=1SLight=[1+,1-] E(SLight)=1Gain(S,Weight)=1–[(2/4)*1+(2/4)*1] =0Forattribute‘Lotion’:Values(Lotion):[Yes,No]S=[2+,2-]SYes=[0+,2-] E(SYes)=0SNo=[2+,0-] E(SNo)=0Gain(S,Lotion)=1–[(2/4)*0+(2/4)*0] =1Therefore,Gain(S,Lotion)ismaximum第二十三頁，共36頁。Inthiscase,thefinaldecisiontreewillbeHairBlondeRedBrownSunburnedNotSunburnedLotionYNSunburnedNotSunburned第二十四頁，共36頁。C4.5C4.5是對(duì)ID3的改進(jìn)算法(suànfǎ)對(duì)連續(xù)值的處理對(duì)決策樹進(jìn)行剪枝第二十五頁，共36頁。決策樹學(xué)習(xí)中的假設(shè)(jiǎshè)空間搜索假設(shè)空間ID3算法中的假設(shè)空間包含所有的決策樹當(dāng)遍歷決策樹空間時(shí)，ID3僅維護(hù)單一的當(dāng)前假設(shè)。根本的ID3算法在搜索(sōusuǒ)中不進(jìn)行回溯ID3算法在搜索(sōusuǒ)的每一步都使用當(dāng)前的所有訓(xùn)練樣例第二十六頁，共36頁。決策樹學(xué)習(xí)(xuéxí)的常見問題(1)?防止過度擬合數(shù)據(jù)根本的決策樹構(gòu)造算法沒有考慮噪聲，生成的決策樹完全與訓(xùn)練例子擬合。有噪聲情況下，完全擬合將導(dǎo)致過分(guò〃fèn)擬合〔overfitting〕，即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測(cè)性能。第二十七頁，共36頁。28OverfittinginDecisionTreeLearning第二十八頁，共36頁。解決(jiějué)方法剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹得到簡(jiǎn)化而變得更容易理解(lǐjiě)。把訓(xùn)練集分為兩個(gè)局部—用于構(gòu)建決策樹的局部和用于剪枝的局部(測(cè)試集).對(duì)于構(gòu)建好的樹,對(duì)于每一個(gè)內(nèi)部節(jié)點(diǎn)在測(cè)試集上計(jì)算兩種誤差不剪枝時(shí)的誤差把這個(gè)內(nèi)部節(jié)點(diǎn)作為葉子的誤差如果進(jìn)行剪枝誤差變小,那么就進(jìn)行剪枝.理論上講，向后剪枝好于向前剪枝，但計(jì)算復(fù)雜度大。

第二十九頁，共36頁。決策樹學(xué)習(xí)(xuéxí)的常見問題〔2〕合并連續(xù)值屬性(shǔxìng)屬性(shǔxìng)選擇的其他度量標(biāo)準(zhǔn)信息增益比〔gainratio〕、Gini-index、距離度量〔distancemeasure〕等。不同的度量有不同的效果，特別是對(duì)于多值屬性(shǔxìng)。第三十頁，共36頁。決策樹的優(yōu)點(diǎn)(yōudiǎn)可以生成可以理解的規(guī)那么；計(jì)算量相對(duì)來說不是很大；可以處理連續(xù)和離散字段；可以處理殘缺數(shù)據(jù)決策樹可以清晰的顯示哪些字段比較(bǐjiào)重要

第三十一頁，共36頁。缺乏(quēfá)之處對(duì)連續(xù)性的字段比較難預(yù)測(cè)(yùcè)當(dāng)類別太多時(shí)，錯(cuò)誤可能會(huì)增加的比較快一般的算法分類的時(shí)候，只是根據(jù)一個(gè)屬性來分類。不是全局最優(yōu)。

第三十二頁，共36頁。隨機(jī)森林(sēnlín)的定義隨機(jī)森林是一個(gè)樹型分類器{h(x,k),k=1,…}的集合。其中元分類器h(x,k)是決策樹；森林的輸出采用簡(jiǎn)單多數(shù)投票法〔針對(duì)分類〕或單顆樹輸出結(jié)果(jiēguǒ)的簡(jiǎn)單平均〔針對(duì)回歸〕得到。第三十三頁，共36頁。隨機(jī)森林(sēnlín)算法隨機(jī)選取訓(xùn)練樣本集：使用Bagging方法形成(xíngchéng)每顆樹的訓(xùn)練集隨機(jī)選取分裂屬性集：假設(shè)共有M個(gè)屬性，指定一個(gè)屬性數(shù)F≤M，在每個(gè)內(nèi)部結(jié)點(diǎn)，從M個(gè)屬性中隨機(jī)抽取F個(gè)屬性作分裂屬性集，以這F個(gè)屬性上最好的分裂方式對(duì)結(jié)點(diǎn)進(jìn)行分裂〔在整個(gè)森林的生長過程中，F(xiàn)的值一般維持不變〕每顆樹任其生長，不進(jìn)行剪枝第三十四頁，共36頁。Bagging(Breiman,1996)?第二十九頁，共36頁。隨機(jī)選取訓(xùn)練樣本集：使用Bagging方法形成(xíngchéng)每顆樹的訓(xùn)練集Forattribute‘Lotion’:用信息(xìnxī)增益度量期望熵最低95443–[(3/8)*0.