分層決策樹完

基于層次分解思想的決策樹2015.04.09分層思想的提出ID3算法典型的基于自頂向下的貪婪算法在每個(gè)節(jié)點(diǎn)找到局部最優(yōu)的屬性進(jìn)行擴(kuò)展，需要更多的附加節(jié)點(diǎn)針對多分類問題，ID3算法不容易處理分層思想的提出分層思想解決多類問題的手段是把一個(gè)多類問題轉(zhuǎn)為兩類問題。這種方法首先通過選擇相關(guān)程度最大的屬性一值對(它盡可能把多個(gè)類清晰分割為正、反兩大類)把訓(xùn)練集中的多個(gè)類轉(zhuǎn)換成正(Y)和反(N)兩類，用ID3方法產(chǎn)生第一級決策樹。把經(jīng)過第一層劃分后得到的正、反兩大類數(shù)據(jù)集分別在細(xì)分為子的正、反兩類來產(chǎn)生第二級決策樹。對第二級決策樹得到的每個(gè)子正、反類在重復(fù)上述操作，直到把原訓(xùn)練集中所有類分清；最后將各層決策樹轉(zhuǎn)化為一組規(guī)則。實(shí)例基于分層思想生成決策樹基于層次分解思想的決策樹生成過程從所給例子中選出訓(xùn)練集。對每個(gè)屬性考察它是否能把多個(gè)類分割為正、反兩大類:若某些屬性能分割，計(jì)算由此屬性把原數(shù)據(jù)集轉(zhuǎn)化為正、反兩大類后根節(jié)點(diǎn)的嫡值，選取分割類后根屬性所獲得熵最小的屬性分割標(biāo)準(zhǔn)作為當(dāng)前層的最終分割結(jié)果，把多類轉(zhuǎn)化為正、反兩類。若所有屬性都不能分割，則使用經(jīng)典ID3方法直接產(chǎn)生決策樹。用ID3方法產(chǎn)生當(dāng)前層決策樹。分別對所得到的正、反兩類遞歸調(diào)用該過程。把每層產(chǎn)生的決策樹轉(zhuǎn)化為相應(yīng)的一組規(guī)則。原理的區(qū)別算法Step1:

統(tǒng)計(jì)當(dāng)前屬性下的每個(gè)分支所含的類,每個(gè)類包含的例子個(gè)數(shù)Step2:

給定閾值k1，對各分支中統(tǒng)計(jì)的每個(gè)類個(gè)數(shù)進(jìn)行如下操作若此分支中的某個(gè)類的數(shù)據(jù)個(gè)數(shù)在這個(gè)類所含全部數(shù)據(jù)的概率小于給定閾值k1，則此分支中對應(yīng)類的例子個(gè)數(shù)可忽略。(k1值隨數(shù)據(jù)庫不同而進(jìn)行調(diào)整，通常取值小于0.1)Step3:

計(jì)算每個(gè)類與其他類在每個(gè)分支中重疊個(gè)數(shù)之和占此類中總個(gè)數(shù)的比例。統(tǒng)計(jì)出各個(gè)類之間的重疊程度。Step4:

判斷每個(gè)類與其他類重疊程度如果某個(gè)或某幾個(gè)類與其他類的重疊程度接近0，則這個(gè)或者這幾個(gè)類為正類，其他類為反類，得到當(dāng)前測試屬性分割結(jié)果否則給定閾值k2，如果兩個(gè)類的重疊程度都大于給定閾值k2，則這些大于閉值的類組合在一起。考慮剩余的類，分別把剩余的類放入交疊程度大于k2的類組合中，否則，把剩余的類組合在一起，最終轉(zhuǎn)化為正、反兩類。(k2值隨數(shù)據(jù)庫不同而進(jìn)行調(diào)整，通常取值大于0.8)Car數(shù)據(jù)集(對于屬性A6)類unaccaccvgoodgooda1576000a2357180039a32772046530交疊程度的計(jì)算unacc與acc的交疊程度355/(355+277+576)+277/(355+277+576)=0.523unacc與vgood的交疊程度277/(355+277+576)=0.229unacc與good的交疊程度355/(355+277+576)+277/(355+277+576)=0.523acc與unacc的交疊程度180/(180+204)+204/(180+204)=1acc與vgood的交疊程度204/(180+204)=0.531交疊程度矩陣類unaccaccvgoodgoodunacc10.5230.2290.523acc110.5311vgood1111good