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

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

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

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

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