機(jī)器學(xué)習(xí)課件4-決策樹

第四章:決策樹目錄決策樹簡(jiǎn)介引入幾個(gè)重要的術(shù)語構(gòu)造思路離散型決策樹的構(gòu)造連續(xù)性數(shù)值的處理決策樹剪枝預(yù)剪枝后剪枝引入決策樹是一種有監(jiān)督的分類方法,它是用已有的數(shù)據(jù)構(gòu)造出一棵樹,用這棵樹,對(duì)新的數(shù)據(jù)進(jìn)行預(yù)測(cè)。幾個(gè)重要的術(shù)語根節(jié)點(diǎn):一棵樹只有一個(gè)根節(jié)點(diǎn),在之前給出的例子的樹中,最上方的節(jié)點(diǎn)(形狀為圓角方框)就是這棵樹的根節(jié)點(diǎn),我們?cè)谟眠@棵樹進(jìn)行預(yù)測(cè)時(shí),這個(gè)根節(jié)也是整個(gè)預(yù)測(cè)的入口。子節(jié)點(diǎn):我們看到最下面的形狀為矩形框節(jié)點(diǎn)就是這棵樹的葉子節(jié)點(diǎn),在決策樹中,葉子節(jié)點(diǎn)的內(nèi)容就是我們對(duì)于輸入數(shù)據(jù)的預(yù)測(cè)結(jié)果。在這里要注意,一棵樹可以有很多葉子節(jié)點(diǎn),但是根節(jié)點(diǎn)只能有一個(gè)。內(nèi)部節(jié)點(diǎn):除了根節(jié)點(diǎn)和葉子外,其他的節(jié)點(diǎn)就是內(nèi)部節(jié)點(diǎn),內(nèi)部節(jié)點(diǎn)的內(nèi)容對(duì)應(yīng)某一屬性(在例子中即為氣味或者顏色),這個(gè)屬性的不同的值可能會(huì)通向不同的內(nèi)部節(jié)點(diǎn)或者葉子節(jié)點(diǎn)。子樹:對(duì)于某一非根節(jié)點(diǎn),該節(jié)點(diǎn)及從該節(jié)點(diǎn)下面可以到達(dá)的其他節(jié)點(diǎn),可以看作原決策樹的一部分,稱為原決策樹的子樹。構(gòu)造思路在構(gòu)造一顆決策樹時(shí),在每個(gè)非葉子節(jié)點(diǎn)都需要去選擇某一屬性（該屬性如何選??？）,這個(gè)屬性不同的取值對(duì)應(yīng)這個(gè)節(jié)點(diǎn)的不同子樹,也就是說,構(gòu)造一棵好的決策樹很重要的一點(diǎn)就在于如何去選擇這個(gè)節(jié)點(diǎn)下的屬性。子節(jié)點(diǎn)的屬性一定是與父節(jié)點(diǎn)及父節(jié)點(diǎn)以上的屬性不同的,當(dāng)子節(jié)點(diǎn)沒有屬性可以選擇時(shí),這個(gè)子節(jié)點(diǎn)一定是葉子節(jié)點(diǎn)。遞歸進(jìn)行構(gòu)造構(gòu)造思路離散型決策樹的構(gòu)造在某一節(jié)點(diǎn)選擇某一屬性的目的在于選擇該屬性后可以讓決策樹分支節(jié)點(diǎn)所包含的樣本盡可能屬于同一類別,即節(jié)點(diǎn)的“純度”越來越高。如何量化純度？上面三個(gè)公式都可以用來量化純度,并且計(jì)算得到的值越大,表示越“不純”,越小表示越“純”。離散型決策樹的構(gòu)造信息增益當(dāng)計(jì)算得到的信息增益值越大,就說明在該節(jié)點(diǎn)使用屬性來劃分所獲得的“純度”越大,這也是ID3決策樹算法使用的策略,即使用信息增益來作為屬性選擇的標(biāo)準(zhǔn)。連續(xù)性數(shù)值的處理以C4.5算法為代表的一系列算法采用取值區(qū)間二分離散的方法來處理找出訓(xùn)練樣本在該連續(xù)屬性上的最大和最小值,在最大和最小值限定的取值區(qū)間上設(shè)置多個(gè)等分?jǐn)帱c(diǎn),分別計(jì)算以這些斷點(diǎn)為分裂點(diǎn)的信息增益值,并比較,具有最大信息增益的斷點(diǎn)即為最佳分裂點(diǎn),自該分裂點(diǎn)把整個(gè)取值區(qū)間劃分為兩部分,相應(yīng)的依據(jù)記錄在該屬性上的取值,也將記錄集劃分為兩部分。決策樹剪枝過擬合問題構(gòu)造出來的決策樹雖然在訓(xùn)練集上的數(shù)據(jù)的準(zhǔn)確度特別高,但是在測(cè)試集上的數(shù)據(jù)的準(zhǔn)確度確很低。如何解決預(yù)剪枝后剪枝預(yù)剪枝驗(yàn)證集精度一般我們將數(shù)據(jù)分為兩部分,一部分是訓(xùn)練集,另一部分是驗(yàn)證集。訓(xùn)練集用來進(jìn)行決策樹的構(gòu)造,另一部分沒有在構(gòu)造決策樹用到的數(shù)據(jù)稱為驗(yàn)證集。驗(yàn)證集精度即為用驗(yàn)證集去檢驗(yàn)這棵樹,預(yù)測(cè)結(jié)果的正確率。預(yù)剪枝預(yù)剪枝的方法就是在每一次選擇劃分屬性時(shí),對(duì)劃分前后兩棵樹的驗(yàn)證集精度進(jìn)行計(jì)算,劃分前精度值高,就選擇在該節(jié)點(diǎn)不進(jìn)行屬性劃分,直接將該節(jié)點(diǎn)標(biāo)為葉子節(jié)點(diǎn),并將該葉子節(jié)點(diǎn)的值設(shè)置為樣本集D中樣本數(shù)最多的類。預(yù)剪枝使得很多節(jié)點(diǎn)沒有展開,既降低了過擬合的風(fēng)險(xiǎn),又減少了訓(xùn)練決策樹時(shí)花費(fèi)的時(shí)間,但是存在這樣一種可能性,雖然這個(gè)節(jié)點(diǎn)的展開會(huì)暫時(shí)降低泛化性能,但是這個(gè)節(jié)點(diǎn)后面其他節(jié)點(diǎn)的展開又提高了泛化性能,這又提高了預(yù)剪枝帶來的欠擬合的風(fēng)險(xiǎn)。經(jīng)實(shí)踐證明,這種策略無法得到較好的結(jié)果。后剪枝在后剪枝方法中,我們先構(gòu)造出來了一棵完整的決策樹,并對(duì)這棵樹的非葉子節(jié)點(diǎn),即進(jìn)行了屬性劃分的節(jié)點(diǎn)進(jìn)行逆序?qū)哟伪闅v,從構(gòu)造出來的這棵決策樹深度最深的非葉子節(jié)點(diǎn)開始逆序進(jìn)行層次遍歷,對(duì)每一節(jié)點(diǎn)計(jì)算出當(dāng)前這棵樹的驗(yàn)證集精度和將當(dāng)前節(jié)點(diǎn)變?yōu)槿~子節(jié)點(diǎn)的驗(yàn)證集精度,取驗(yàn)證集精度最高的