分層決策樹(shù)完

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

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

給定閾值k1，對(duì)各分支中統(tǒng)計(jì)的每個(gè)類個(gè)數(shù)進(jìn)行如下操作若此分支中的某個(gè)類的數(shù)據(jù)個(gè)數(shù)在這個(gè)類所含全部數(shù)據(jù)的概率小于給定閾值k1，則此分支中對(duì)應(yīng)類的例子個(gè)數(shù)可忽略。(k1值隨數(shù)據(jù)庫(kù)不同而進(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)前測(cè)試屬性分割結(jié)果否則給定閾值k2，如果兩個(gè)類的重疊程度都大于給定閾值k2，則這些大于閉值的類組合在一起。考慮剩余的類，分別把剩余的類放入交疊程度大于k2的類組合中，否則，把剩余的類組合在一起，最終轉(zhuǎn)化為正、反兩類。(k2值隨數(shù)據(jù)庫(kù)不同而進(jìn)行調(diào)整，通常取值大于0.8)Car數(shù)據(jù)集(對(duì)于屬性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