決策樹2023最新整理收集do

something概要簡介決策樹表示法決策樹學習的適用問題基本的決策樹學習算法決策樹學習中的假想空間搜索決策樹學習的常見問題簡介決策樹方法是應用最廣的歸納推理算法之一一種逼近離散值目標函數的方法對噪聲數據有很好的健壯性且能學習析取表達式決策樹的表示法決策樹通過把實例從根節點排列到某個葉子節點來分類實例，葉子節點即為實例所屬的分類。樹上的每一個節點說明了對實例的某個屬性的測試，并且該節點的每一個后繼分支對應于該屬性的一個可能值圖表達式決策樹學習的適用問題實例是由屬性-值對表示的目標函數具有離散的輸出值訓練數據可以包含錯誤訓練數據可以包含缺少屬性值的實例屬性選擇構造好的決策樹的關鍵在于如何選擇好的邏輯判斷或屬性。對于同樣一組例子，可以有很多決策樹能符合這組例子。人們研究出，一般情況下或具有較大概率地說，樹越小則樹的預測能力越強。要構造盡可能小的決策樹，關鍵在于選擇恰當的邏輯判斷或屬性。由于構造最小的樹是NP-難問題，因此只能采取用啟發式策略選擇好的邏輯判斷或屬性。

用熵度量樣例的均一性（純度）熵的定義舉例用信息增益度量期望熵最低舉例ID3算法(IterativeDichotomiser

3)創建樹的Root結點如果Examples都為正，那么返回label=+中的單結點Root如果Examples都為反，那么返回lable=-單結點樹Root如果Attributes為空，那么返回單節點樹Root，lable=Examples中最普遍的目標屬性值否則開始

A

Attributes中分類能力最好的屬性

Root的決策屬性

A

對于每個可能值 在Root下加一個新的分支對應測試A=vi

令Example-vi為Examples中滿足A屬性值為vi的子集 如果Examples-vi為空 在這個新分支下加一個葉子結點，節點的lable=Examples中最普遍的 目標屬性值 否則在這個新分支下加一個子樹ID3(example-vi,target- attribute,attributes-|A|結束返回RootExample2FactorsaffectingsunburnS=[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.45443Forattribute‘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.01571Gain(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?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.5NameHairHeightWeightLotionSunburnedSarahBlondeAverageLightNoYesDanaBlondeTallAverageYesNoAnnieBlondeShortAverageNoYesKatieBlondeShortLightYesNoForattribute‘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)ismaximumInthiscase,thefinaldecisiontreewillbeHairBlondeRedBrownSunburnedNotSunburnedLotionYNSunburnedNotSunburnedC4.5C4.5是對ID3的改進算法對連續值的處理對決策樹進行剪枝決策樹學習中的假設空間搜索假設空間ID3算法中的假設空間包含所有的決策樹當遍歷決策樹空間時，ID3僅維護單一的當前假設。基本的ID3算法在搜索中不進行回溯ID3算法在搜索的每一步都使用當前的所有訓練樣例決策樹學習的常見問題(1)?避免過度擬合數據基本的決策樹構造算法沒有考慮噪聲，生成的決策樹完全與訓練例子擬合。有噪聲情況下，完全擬合將導致過分擬合（overfitting），即對訓練數據的完全擬合反而不具有很好的預測性能。

28OverfittinginDecisionTreeLearning解決方法剪枝是一種克服噪聲的技術，同時它也能使樹得到簡化而變得更容易理解。把訓練集分為兩個部分—用于構建決策樹的部分和用于剪枝的部分(測試集).對于構建好的樹,對于每一個內部節點在測試集上計算兩種誤差不剪枝時的誤差把這個內部節點作為葉子的誤差如果進行剪枝誤差變小,那么就進行剪枝.理論上講，向后剪枝好于向前剪枝，但計算復雜度大。

決策樹學習的常見問題（2）合并連續值屬性屬性選擇的其他度量標準信息增益比（gainratio）、Gini-index、距離度量（distancemeasure）等。不同的度量有不同的效果，特別是對于多值屬性。決策樹的優點可以生成可以理解的規則；計算量相對來說不是很大；可以處理連續和離散字段；可以處理殘缺數據決策樹可以清晰的顯示哪些字段比較重要

不足之處對連續性的字段比較難預測當類別太多時，錯誤可能會增加的比較快一般的算法分類的時候，只是根據一個屬性來分類。不是全局最優。

隨機森林的定義隨機森林是一個樹型分類器{h(x,

k),k=1,…}的集合。其中元分類器h(x,

k)是決策樹；森林的輸出采用簡單多數投票法（針對分類）或單顆樹輸出結果的簡單平均（針對回歸）得到。隨機森林算法隨機選取訓練樣本集：使用Bagging方法形成每顆樹的訓練集隨機選取分裂屬性集：假設共有M個屬性，指定一個屬性數F≤M，在每個內部結點，從M個屬性中隨機抽取F個屬性作分裂屬性集，以這F個屬性上最好的分裂方式對結點進行分裂（在整個森林的生長過程中，F的值一般維持不變）每顆樹任其生長，不進行剪枝隨機森林算法Bagging(Breiman,1996)?在訓練的每一輪中，均從原始樣本集S中有放回地隨機抽取訓練樣本集T（T的樣本個數同S），這樣一個初始樣本在某輪訓練中可能出現多次或根本不出現（S中每個樣本未被抽取的概率為(1-1/|S|)|S|≈0.36