一 ? 決策樹的一般表示

數(shù)據(jù)為m個(gè)樣本，d個(gè)屬性（特征）

遞歸構(gòu)建

葉子結(jié)點(diǎn)表示 結(jié)果分類

根結(jié)點(diǎn) 表示全部樣本

從樣本空間D中選擇一個(gè)最優(yōu)屬性a*,然后依照屬性a*將樣本空間D劃分為不同樣本子集D1,D2 等

然后對子集Di找到 一個(gè)最優(yōu)屬性，進(jìn)行下一次劃分

直到子集為空，屬性為空，或者子集中樣本取值相同（分類相同）

代碼line2，當(dāng)子集為中樣本取值相同，如取值為類別C ?遞歸結(jié)束，此取值為樣本分類C

代碼line5，當(dāng)屬性為空，樣本無法進(jìn)一步挑選最優(yōu)屬性，以分類最多的為最終分類

代碼line5，當(dāng)樣本在屬性集中取值相同，即取值均勻分布，無法找到最優(yōu)屬性，以分類最多的為最終分類

代碼line12，當(dāng)樣本子集為空，取父結(jié)點(diǎn)分類最多的類別，將父結(jié)點(diǎn)的樣本分布當(dāng)做此結(jié)點(diǎn)的先驗(yàn)分布

二 信息增益法

?

ID3決策樹算法使用信息增益作為準(zhǔn)則劃分屬性

?

?

?

Ent(D)當(dāng)前樣本集信息熵

Gain(D,a)當(dāng)前樣本集在屬性a下的信息增益

|Dv|為樣本集D中屬性a對應(yīng)第v個(gè)取值，所占的樣本個(gè)數(shù)，|D|為樣本集總個(gè)數(shù)

默認(rèn)認(rèn)為屬性a將整個(gè)樣本D劃分，即無缺省值

　算法的過程為：

　　　　1)初始化信息增益的閾值??

　　　　2）判斷樣本是否為同一類輸出DiDi，如果是則返回單節(jié)點(diǎn)樹T。標(biāo)記類別為DiDi

　　　　3) 判斷特征是否為空，如果是則返回單節(jié)點(diǎn)樹T，標(biāo)記類別為樣本中輸出類別D實(shí)例數(shù)最多的類別。

　　　　4）計(jì)算A中的各個(gè)特征（一共n個(gè)）對輸出D的信息增益，選擇信息增益最大的特征AgAg

　　　　5) 如果AgAg的信息增益小于閾值??，則返回單節(jié)點(diǎn)樹T，標(biāo)記類別為樣本中輸出類別D實(shí)例數(shù)最多的類別。

　　　　6）否則，按特征AgAg的不同取值A(chǔ)giAgi將對應(yīng)的樣本輸出D分成不同的類別DiDi。每個(gè)類別產(chǎn)生一個(gè)子節(jié)點(diǎn)。對應(yīng)特征值為AgiAgi。返回增加了節(jié)點(diǎn)的數(shù)T。

　　　　7）對于所有的子節(jié)點(diǎn)，令D=Di,A=A?{Ag}D=Di,A=A?{Ag}遞歸調(diào)用2-6步，得到子樹TiTi并返回。

ID3算法值得改進(jìn)的地方。　　

　　　　a)ID3沒有考慮連續(xù)特征，比如長度，密度都是連續(xù)值，無法在ID3運(yùn)用。這大大限制了ID3的用途。

　　　　b)ID3采用信息增益大的特征優(yōu)先建立決策樹的節(jié)點(diǎn)。很快就被人發(fā)現(xiàn)，在相同條件下，取值比較多的特征比取值少的特征信息增益大。比如一個(gè)變量有2個(gè)值，各為1/2，另一個(gè)變量為3個(gè)值，各為1/3，其實(shí)他們都是完全不確定的變量，但是取3個(gè)值的比取2個(gè)值的信息增益大。如果校正這個(gè)問題呢？

　　　　c) ID3算法對于缺失值的情況沒有做考慮

　　　　d) 沒有考慮過擬合的問題

?

三 增益率

?

信息增益對屬性值較多的屬性具有偏好，例如增加一個(gè)id編號作為屬性，1000個(gè)樣本對應(yīng)1000個(gè)id，每個(gè)ip只有唯一的一個(gè)樣本。明顯無法達(dá)到泛化目的，且毫無意義。

?

C4.5決策樹算法：先從候選屬性中找出信息增益高于平均水平的屬性，然后選擇增益率最高的

對ID3的優(yōu)化：

對于連續(xù)特征 ? C4.5的思路是將連續(xù)的特征離散化。比如m個(gè)樣本的連續(xù)特征A有m個(gè)，從小到大排列為a1,a2,...,ama1,a2,...,am,則C4.5取相鄰兩樣本值的平均數(shù)，一共取得m-1個(gè)劃分點(diǎn)，其中第i個(gè)劃分點(diǎn)Ti表示Ti表示為：Ti=ai+ai+12Ti=ai+ai+12。對于這m-1個(gè)點(diǎn)，分別計(jì)算以該點(diǎn)作為二元分類點(diǎn)時(shí)的信息增益。選擇信息增益最大的點(diǎn)作為該連續(xù)特征的二元離散分類點(diǎn)。比如取到的增益最大的點(diǎn)為atat,則小于atat的值為類別1，大于atat的值為類別2，這樣我們就做到了連續(xù)特征的離散化。要注意的是，與離散屬性不同的是，如果當(dāng)前節(jié)點(diǎn)為連續(xù)屬性，則該屬性后面還可以參與子節(jié)點(diǎn)的產(chǎn)生選擇過程。

缺失值問題 ? 主要需要解決的是兩個(gè)問題，一是在樣本某些特征缺失的情況下選擇劃分的屬性，二是選定了劃分屬性，對于在該屬性上缺失特征的樣本的處理?

對于第一個(gè)子問題，對于某一個(gè)有缺失特征值的特征A。C4.5的思路是將數(shù)據(jù)分成兩部分，對每個(gè)樣本設(shè)置一個(gè)權(quán)重（初始可以都為1），然后劃分?jǐn)?shù)據(jù)，一部分是有特征值A(chǔ)的數(shù)據(jù)D1，另一部分是沒有特征A的數(shù)據(jù)D2. 然后對于沒有缺失特征A的數(shù)據(jù)集D1來和對應(yīng)的A特征的各個(gè)特征值一起計(jì)算加權(quán)重后的信息增益比，最后乘上一個(gè)系數(shù)，這個(gè)系數(shù)是無特征A缺失的樣本加權(quán)后所占加權(quán)總樣本的比例。

對于第二個(gè)子問題，可以將缺失特征的樣本同時(shí)劃分入所有的子節(jié)點(diǎn)，不過將該樣本的權(quán)重按各個(gè)子節(jié)點(diǎn)樣本的數(shù)量比例來分配。比如缺失特征A的樣本a之前權(quán)重為1，特征A有3個(gè)特征值A(chǔ)1,A2,A3。 3個(gè)特征值對應(yīng)的無缺失A特征的樣本個(gè)數(shù)為2,3,4.則a同時(shí)劃分入A1，A2，A3。對應(yīng)權(quán)重調(diào)節(jié)為2/9,3/9, 4/9。

缺點(diǎn)：

模型是用較為復(fù)雜的熵來度量

使用了相對較為復(fù)雜的多叉樹

只能處理分類不能處理回歸等

由于決策樹算法非常容易過擬合，因此對于生成的決策樹必須要進(jìn)行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有優(yōu)化的空間。思路主要是兩種，一種是預(yù)剪枝，即在生成決策樹的時(shí)候就決定是否剪枝。另一個(gè)是后剪枝，即先生成決策樹，再通過交叉驗(yàn)證來剪枝。

C4.5生成的是多叉樹，即一個(gè)父節(jié)點(diǎn)可以有多個(gè)節(jié)點(diǎn)。很多時(shí)候，在計(jì)算機(jī)中二叉樹模型會比多叉樹運(yùn)算效率高。如果采用二叉樹，可以提高效率。

C4.5只能用于分類，如果能將決策樹用于回歸的話可以擴(kuò)大它的使用范圍。

C4.5由于使用了熵模型，里面有大量的耗時(shí)的對數(shù)運(yùn)算,如果是連續(xù)值還有大量的排序運(yùn)算。如果能夠加以模型簡化可以減少運(yùn)算強(qiáng)度但又不犧牲太多準(zhǔn)確性的話，那就更好了。

?

?

四 基尼指數(shù)

?

CART決策樹算法使用此法，只用構(gòu)建二叉樹，計(jì)算只有2次項(xiàng)

CART分類樹算法對于連續(xù)特征和離散特征處理的改進(jìn)

對于CART分類樹連續(xù)值的處理問題，其思想和C4.5是相同的，都是將連續(xù)的特征離散化。唯一的區(qū)別在于在選擇劃分點(diǎn)時(shí)的度量方式不同，C4.5使用的是信息增益比，則CART分類樹使用的是基尼系數(shù)。

將連續(xù)特征 以某個(gè)基點(diǎn)劃分重兩部分，構(gòu)建2叉樹

此特征在一次劃分后可繼續(xù)參與劃分

離散特征同樣

　　　　具體的思路如下，比如m個(gè)樣本的連續(xù)特征A有m個(gè)，從小到大排列為a1,a2,...,ama1,a2,...,am,則CART算法取相鄰兩樣本值的平均數(shù)，一共取得m-1個(gè)劃分點(diǎn)，其中第i個(gè)劃分點(diǎn)Ti表示Ti表示為：Ti=ai+ai+12Ti=ai+ai+12。對于這m-1個(gè)點(diǎn)，分別計(jì)算以該點(diǎn)作為二元分類點(diǎn)時(shí)的基尼系數(shù)。選擇基尼系數(shù)最小的點(diǎn)作為該連續(xù)特征的二元離散分類點(diǎn)。比如取到的基尼系數(shù)最小的點(diǎn)為atat,則小于atat的值為類別1，大于atat的值為類別2，這樣我們就做到了連續(xù)特征的離散化。要注意的是，與ID3或者C4.5處理離散屬性不同的是，如果當(dāng)前節(jié)點(diǎn)為連續(xù)屬性，則該屬性后面還可以參與子節(jié)點(diǎn)的產(chǎn)生選擇過程。

　　　　對于CART分類樹離散值的處理問題，采用的思路是不停的二分離散特征。

　　　　回憶下ID3或者C4.5，如果某個(gè)特征A被選取建立決策樹節(jié)點(diǎn)，如果它有A1,A2,A3三種類別，我們會在決策樹上一下建立一個(gè)三叉的節(jié)點(diǎn)。這樣導(dǎo)致決策樹是多叉樹。但是CART分類樹使用的方法不同，他采用的是不停的二分，還是這個(gè)例子，CART分類樹會考慮把A分成{A1}和{A2,A3}{A1}和{A2,A3},?{A2}和{A1,A3}{A2}和{A1,A3},?{A3}和{A1,A2}{A3}和{A1,A2}三種情況，找到基尼系數(shù)最小的組合，比如{A2}和{A1,A3}{A2}和{A1,A3},然后建立二叉樹節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)是A2對應(yīng)的樣本，另一個(gè)節(jié)點(diǎn)是{A1,A3}對應(yīng)的節(jié)點(diǎn)。同時(shí)，由于這次沒有把特征A的取值完全分開，后面我們還有機(jī)會在子節(jié)點(diǎn)繼續(xù)選擇到特征A來劃分A1和A3。這和ID3或者C4.5不同，在ID3或者C4.5的一棵子樹中，離散特征只會參與一次節(jié)點(diǎn)的建立。

算法一般步驟：

算法輸入是訓(xùn)練集D，基尼系數(shù)的閾值，樣本個(gè)數(shù)閾值。

　　　　輸出是決策樹T。

　　　　我們的算法從根節(jié)點(diǎn)開始，用訓(xùn)練集遞歸的建立CART樹。

　　　　1) 對于當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)集為D，如果樣本個(gè)數(shù)小于閾值或者沒有特征，則返回決策子樹，當(dāng)前節(jié)點(diǎn)停止遞歸。

　　　　2) 計(jì)算樣本集D的基尼系數(shù)，如果基尼系數(shù)小于閾值，則返回決策樹子樹，當(dāng)前節(jié)點(diǎn)停止遞歸。

　　　　3) 計(jì)算當(dāng)前節(jié)點(diǎn)現(xiàn)有的各個(gè)特征的各個(gè)特征值對數(shù)據(jù)集D的基尼系數(shù)，對于離散值和連續(xù)值的處理方法和基尼系數(shù)的計(jì)算見第二節(jié)。缺失值的處理方法和C4.5算法里描述的相同。

　　　　4) 在計(jì)算出來的各個(gè)特征的各個(gè)特征值對數(shù)據(jù)集D的基尼系數(shù)中，選擇基尼系數(shù)最小的特征A和對應(yīng)的特征值a。根據(jù)這個(gè)最優(yōu)特征和最優(yōu)特征值，把數(shù)據(jù)集劃分成兩部分D1和D2，同時(shí)建立當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)，做節(jié)點(diǎn)的數(shù)據(jù)集D為D1，右節(jié)點(diǎn)的數(shù)據(jù)集D為D2.

　　　　5) 對左右的子節(jié)點(diǎn)遞歸的調(diào)用1-4步，生成決策樹。

?

五 優(yōu)缺點(diǎn)：

首先我們看看決策樹算法的優(yōu)點(diǎn)：

　　　　1）簡單直觀，生成的決策樹很直觀。

　　　　2）基本不需要預(yù)處理，不需要提前歸一化，處理缺失值。

　　　　3）使用決策樹預(yù)測的代價(jià)是O(log2m)O(log2m)。 m為樣本數(shù)。

　　　　4）既可以處理離散值也可以處理連續(xù)值。很多算法只是專注于離散值或者連續(xù)值。

　　　　5）可以處理多維度輸出的分類問題。

　　　　6）相比于神經(jīng)網(wǎng)絡(luò)之類的黑盒分類模型，決策樹在邏輯上可以得到很好的解釋

　　　　7）可以交叉驗(yàn)證的剪枝來選擇模型，從而提高泛化能力。

　　　　8） 對于異常點(diǎn)的容錯(cuò)能力好，健壯性高。

　　　　我們再看看決策樹算法的缺點(diǎn):

　　　　1）決策樹算法非常容易過擬合，導(dǎo)致泛化能力不強(qiáng)。可以通過設(shè)置節(jié)點(diǎn)最少樣本數(shù)量和限制決策樹深度來改進(jìn)。

　　　　2）決策樹會因?yàn)闃颖景l(fā)生一點(diǎn)點(diǎn)的改動，就會導(dǎo)致樹結(jié)構(gòu)的劇烈改變。這個(gè)可以通過集成學(xué)習(xí)之類的方法解決。

　　　　3）尋找最優(yōu)的決策樹是一個(gè)NP難的問題，我們一般是通過啟發(fā)式方法，容易陷入局部最優(yōu)。可以通過集成學(xué)習(xí)之類的方法來改善。

　　　　4）有些比較復(fù)雜的關(guān)系，決策樹很難學(xué)習(xí)，比如異或。這個(gè)就沒有辦法了，一般這種關(guān)系可以換神經(jīng)網(wǎng)絡(luò)分類方法來解決。

　　　　5）如果某些特征的樣本比例過大，生成決策樹容易偏向于這些特征。這個(gè)可以通過調(diào)節(jié)樣本權(quán)重來改善。

?

參考：

1 《機(jī)器學(xué)習(xí)》? 周志華

2??https://www.cnblogs.com/pinard/p/6053344.html

3??http://www.cnblogs.com/pinard/p/6050306.html

總結(jié)

以上是生活随笔為你收集整理的决策树算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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