4.決策樹

4.1基本流程

決策樹（decisiontree）基于樹結(jié)構(gòu)進(jìn)行決策，符合人的思維機(jī)制，是一類常見的機(jī)器學(xué)習(xí)方法。一般的，一棵決策樹包含一個(gè)根結(jié)點(diǎn)、若干個(gè)內(nèi)部結(jié)點(diǎn)和若干個(gè)葉結(jié)點(diǎn)。葉結(jié)點(diǎn)就對(duì)應(yīng)于決策結(jié)果；內(nèi)部結(jié)點(diǎn)則對(duì)應(yīng)屬性值分類，每個(gè)內(nèi)部結(jié)點(diǎn)包含的樣本集合根據(jù)屬性測(cè)試的結(jié)果（值）劃分到子結(jié)點(diǎn)中；根結(jié)點(diǎn)包含樣本全集，從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的路徑對(duì)應(yīng)一個(gè)判定測(cè)試序列。決策樹學(xué)習(xí)的目的是為了產(chǎn)生一棵泛化能力強(qiáng)，可判定未見示例分類結(jié)果的決策樹，其基本流程遵循簡(jiǎn)單而直觀的分而治之策略。

決策樹學(xué)習(xí)的基本算法描述如下：

輸入：訓(xùn)練集D={(x₁,y₁),(x₂,y₂),…(x_m,y_m)}

????? 屬性集A={a₁,a₂,…,a_d}

過程：函數(shù)TreeGenerate(D,A)

????? 1）生成結(jié)點(diǎn)node；

????? 2）if D中的樣本全屬于同一類別C then

?????????? 將node標(biāo)記為C類葉節(jié)點(diǎn)； return

???????? end if

????? 3）if A=? or D中樣本在A上取值相同 then

?????????? 將node標(biāo)記為葉結(jié)點(diǎn)，其類別標(biāo)記為D中樣本數(shù)最多的類；return

???????? end if

????? 4）從A中選擇最優(yōu)劃分屬性a_*；

????? 5）for a_*中的每一個(gè)值 a_* ^v do

???????????? 為node生成一個(gè)分支；令Dv表示D中在a_*上取值為a_* ^v 的樣本子集；

???????????? if Dv為空then

?????????????? 將分支結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)，其類別標(biāo)記為D中樣本數(shù)最多的類；return

???????????? else

?????????????? 以TreeGenerate(Dv,A-{ a_*})為分支結(jié)點(diǎn)

???????????? end if

????????? end for

??? 輸出：以node為根結(jié)點(diǎn)的一棵決策樹。

決策樹生成是一個(gè)遞歸過程，有三種情形會(huì)導(dǎo)致遞歸終止：1）當(dāng)前結(jié)點(diǎn)包含的樣本全屬于同一類別，無需劃分；2）當(dāng)前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分；3）當(dāng)前結(jié)點(diǎn)包含的樣本集為空，不能劃分。

第2種情形下，把當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)，并將其類別設(shè)定為該結(jié)點(diǎn)所含樣本最多的類別；在第3種情形下，也是把當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)，不過將其類別設(shè)定為父結(jié)點(diǎn)所含樣本最多的類別。二者的區(qū)別在于，第2中情形利用當(dāng)前結(jié)點(diǎn)的后驗(yàn)分布；而第3種情形則把父結(jié)點(diǎn)的樣本分布作為當(dāng)前結(jié)點(diǎn)的先驗(yàn)分布。

4.2劃分選擇

前文的決策樹生成算法中第4步從A中選擇最優(yōu)劃分屬性a*是重點(diǎn)，要如何選擇才能做到最優(yōu)呢？隨著劃分過程的深入，希望決策樹的分支結(jié)點(diǎn)所包含的樣本盡可能屬于同一類別，即結(jié)點(diǎn)的純度（purity）越來越高。用結(jié)點(diǎn)的純度來衡量屬性劃分的最優(yōu)選擇，用信息熵（informationentropy）這一指標(biāo)來度量樣本集合純度。

一般來說，信息增益越大，使用屬性a進(jìn)行劃分所獲得的純度提升越大，如此，用信息增益大小作為決策樹劃分屬性的選擇。在決策樹生成算法上，選擇屬性a*=arg max Gain(D,a)作為劃分依據(jù)。

配合文中的西瓜集例子可以很好理解這個(gè)信息增益計(jì)算。考慮一種特殊情況，就是屬性a的值v恰好有m個(gè)值（和D樣本集數(shù)量一樣），就是說每個(gè)樣本在屬性a上都有不同的值，共有m個(gè)值，這個(gè)分支將產(chǎn)生m個(gè)，每個(gè)分支結(jié)點(diǎn)只包含一個(gè)樣本，其純度是最大，選擇a作為屬性劃分依據(jù)顯然是理所當(dāng)然。但是這樣的劃分所生成的決策樹，不具備泛化能力，無法對(duì)新樣本進(jìn)行有效預(yù)測(cè)。從這個(gè)特殊的屬性例子上來說，信息增益準(zhǔn)則對(duì)屬性取值數(shù)目較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響，不直接使用信息增益，而使用增益率來選擇最優(yōu)劃分屬性。

在候選屬性集合a中，選擇劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性，即

a*=arg minGain_index(D,a)。

從劃分選擇的指標(biāo)選擇上看，算法在考量特殊情況下，為避免各種偏好帶來的不利影響，需優(yōu)化，優(yōu)化過程就需要數(shù)學(xué)定義。

4.3剪枝處理

為解決決策樹學(xué)習(xí)算法帶來的過擬合，需剪枝（pruning）。在決策樹學(xué)習(xí)中，為了盡可能正確分類訓(xùn)練樣本，結(jié)點(diǎn)劃分過程將不斷重復(fù)，有時(shí)會(huì)造成決策樹分支過多，這時(shí)就可能因?yàn)橛?xùn)練樣本學(xué)得太好了，以至于把訓(xùn)練集自身的一些特點(diǎn)當(dāng)作所有數(shù)據(jù)集都具有的一般性質(zhì)而導(dǎo)致過擬合，如此，可通過主動(dòng)去掉一些分支來降低過擬合的風(fēng)險(xiǎn)?；仡櫹?#xff0c;過擬合就是把訓(xùn)練集的特點(diǎn)（個(gè)性）當(dāng)作所有數(shù)據(jù)集的特點(diǎn)（共性）。

決策樹剪枝的基本策略有預(yù)剪枝（pre-pruning）和后剪枝（post-pruning）。預(yù)剪枝是指在決策樹生成過程中，對(duì)每個(gè)結(jié)點(diǎn)在劃分前進(jìn)行估計(jì)，若當(dāng)前結(jié)點(diǎn)的劃分不能帶來決策樹泛化性能提升，則停止劃分并將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)；后剪枝則是先從訓(xùn)練集生成一棵完整的決策樹，然后自底向上地對(duì)非葉結(jié)點(diǎn)進(jìn)行考察，若將該結(jié)點(diǎn)對(duì)應(yīng)的子樹替換為葉結(jié)點(diǎn)能帶來決策樹泛化性能提升，則將該子樹替換為葉結(jié)點(diǎn)。預(yù)剪枝就是在生成過程中就判斷泛化性能來剪枝，后剪枝則是在生成樹后來判斷泛化性能來剪枝。

要看泛化性能是否提升，重心就落在了泛化性能的評(píng)估上。泛化性能評(píng)估上，采用留出法，即預(yù)留一部分?jǐn)?shù)據(jù)作為驗(yàn)證集以進(jìn)行性能評(píng)估。

1）預(yù)剪枝

預(yù)剪枝的基本過程是：1）劃分訓(xùn)練集和驗(yàn)證集；2）基于信息增益準(zhǔn)則，應(yīng)用訓(xùn)練集選擇最優(yōu)劃分屬性來生成分支；3）對(duì)分支的劃分前后用驗(yàn)證集分別計(jì)算精度；4）如果有提升，則劃分，無提升則禁止劃分。

通過預(yù)剪枝剪去決策樹不少分支，避免過擬合，減少?zèng)Q策樹訓(xùn)練時(shí)間開銷和測(cè)試時(shí)間開銷。但是，被剪去的分支，雖然當(dāng)前分支不能提升泛化性能，但有可能其后續(xù)劃分可以顯著提高。預(yù)剪枝這種基于貪心策略的算法，給預(yù)剪枝決策樹帶來了欠擬合的風(fēng)險(xiǎn)?；仡櫱窋M合概念，就是數(shù)據(jù)集的特點(diǎn)（共性）沒有從訓(xùn)練集的特點(diǎn)（個(gè)性）中訓(xùn)練出來。

2）后剪枝

后剪枝先從訓(xùn)練集上生成一棵完整的決策樹，然后用驗(yàn)證集對(duì)內(nèi)部結(jié)點(diǎn)計(jì)算精度來剪枝。后剪枝決策樹通常比預(yù)剪枝決策樹保留更多分支。一般情形下，后剪枝決策樹的欠擬合風(fēng)險(xiǎn)很小，泛化性能往往優(yōu)于預(yù)剪枝決策樹。但后剪枝過程是在生成完全決策樹之后進(jìn)行的，并且要自底向上地對(duì)樹中的所有非葉結(jié)點(diǎn)進(jìn)行逐一考察，因此其訓(xùn)練時(shí)間開銷比未剪枝決策樹和預(yù)剪枝決策樹要大得多。

4.4連續(xù)與缺失值

1）連續(xù)值

對(duì)于基于離散屬性生成的決策樹，信息增益準(zhǔn)則作為劃分屬性的最優(yōu)選擇，對(duì)于可取值數(shù)目可分支；但如果屬性值是連續(xù)性的，屬性可取值數(shù)目不再有限，分支怎么劃分呢？這個(gè)時(shí)候，連續(xù)屬性離散化技術(shù)可以用上，最簡(jiǎn)單策略就是采用二分法（bi-partition）對(duì)連續(xù)屬性進(jìn)行處理。

2）缺失值

現(xiàn)實(shí)任務(wù)中常會(huì)遇到不完整樣本，即樣本的某些屬性值缺失，尤其在屬性數(shù)目較多的情況下，往往會(huì)有大量樣本出現(xiàn)缺失值。如果簡(jiǎn)單放棄不完整樣本，僅使用無缺失值的樣本進(jìn)行學(xué)習(xí)，顯然對(duì)數(shù)據(jù)信息是極大的浪費(fèi)，因此需要考慮利用有缺失屬性值的訓(xùn)練樣例來進(jìn)行學(xué)習(xí)。

存在缺失值情況生成決策樹，需要解決兩個(gè)問題：1）如何在屬性值缺失的情況下進(jìn)行劃分屬性選擇？2）給定劃分屬性，若樣本在該屬性上的值缺失，如何對(duì)樣本進(jìn)行劃分？

?

4.5多變量決策樹

若把每個(gè)屬性視為坐標(biāo)空間中的一個(gè)坐標(biāo)軸，則d個(gè)屬性描述的樣本對(duì)應(yīng)了d維空間中的一個(gè)數(shù)據(jù)點(diǎn)，對(duì)樣本分類則意味著在這個(gè)坐標(biāo)空間中尋找不同類樣本之間的分類邊界。決策樹所形成的分類邊界有一個(gè)明顯的特點(diǎn)：軸平行（axis-parallel），即它的分類邊界由若干個(gè)與坐標(biāo)軸平行的分段組成。

分類邊界的每一段都是與坐標(biāo)軸平行的，這樣的分類邊界使得學(xué)習(xí)結(jié)果有較好的可解釋性，因?yàn)槊恳欢蝿澐侄贾苯訉?duì)應(yīng)了某個(gè)屬性取值。但在學(xué)習(xí)任務(wù)的真實(shí)分類邊界比較復(fù)雜時(shí)，必須使用很多段劃分才能獲得較好的近似，此時(shí)決策樹會(huì)相當(dāng)復(fù)雜，由于要進(jìn)行大量的屬性測(cè)試，預(yù)測(cè)時(shí)間開銷會(huì)很大。若使用斜的劃分邊界，則決策樹模型將大為簡(jiǎn)化。

與傳統(tǒng)的單變量決策樹（univariate decision tree）不同，在多變量決策樹的學(xué)習(xí)過程中，不是為每個(gè)非葉結(jié)點(diǎn)尋找一個(gè)最優(yōu)劃分屬性，而是試圖建立一個(gè)合適的線性分類器。

文中的圖示比較清晰的展示上文描述。本來很難理解多變量決策樹在本章中的意義，后來想到最優(yōu)劃分屬性選擇上的貪心策略時(shí)，才意識(shí)到，泛化性能好的學(xué)習(xí)算法應(yīng)該是分類邊界定義很好的。從這點(diǎn)來看，多變量決策樹，就是在最優(yōu)劃分屬性選擇之上的進(jìn)一步優(yōu)化，通過對(duì)非葉結(jié)點(diǎn)的屬性線性組合找到更好的邊界。抽象之于數(shù)學(xué)，如之。

總結(jié)

以上是生活随笔為你收集整理的机器学习笔记(四)决策树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。