? 既然上次講到了隨機(jī)森林，而隨機(jī)森林是由多棵決策樹(shù)構(gòu)成的，現(xiàn)在就回頭仔細(xì)看看決策樹(shù)。

? 博客園中已經(jīng)有介紹決策樹(shù)的非常好的 博文 。其中詳細(xì)介紹了ID3，C4.5決策樹(shù)的構(gòu)造，這篇博文主要關(guān)注在樹(shù)的每個(gè)節(jié)點(diǎn)如何確定 最佳分裂屬性 和 剪枝 。

? 1.確定最佳分裂屬性

? 一般介紹決策樹(shù)都是以ID3(Quinlan 1986)為例。ID3算法使用的是信息增益，信息增益的具體細(xì)節(jié)我不再贅述。在決策樹(shù)的節(jié)點(diǎn)N上，ID3算法選取在該節(jié)點(diǎn)對(duì)應(yīng)的訓(xùn)練樣例集合D上用輸入屬性進(jìn)行分類后信息增益最大的輸入屬性。信息增益的定義為： 。其中S為節(jié)點(diǎn)N上的訓(xùn)練樣例集合，A為某個(gè)輸入屬性。對(duì)于所有在節(jié)點(diǎn)N上可用的輸入屬性，我們選取信息增益值最大的屬性進(jìn)行分裂。因?yàn)樯鲜街械谝豁?xiàng)對(duì)于所有輸入屬性都是一樣的，所以第二項(xiàng)越小，信息增益值越大。

? 其實(shí)，除了信息增益（亦即熵值）之外，還有許多其他方法用來(lái)確定最佳分裂屬性。他們都統(tǒng)稱為不純性度量（impurity measure）。使用某個(gè)屬性對(duì)訓(xùn)練樣例集進(jìn)行劃分，如果劃分后每個(gè)分支內(nèi)的所有樣例都屬于同一類，則稱該劃分是純的，如果每個(gè)劃分里的樣例屬于很多不同的類，則稱該劃分是不純的。

? 我們用不純性度量來(lái)衡量用某個(gè)屬性劃分訓(xùn)練樣例的純潔度，度量值越高表示劃分越不純（因?yàn)檫@是不純性度量，不是純性度量），我們?cè)诿總€(gè)節(jié)點(diǎn)上進(jìn)行分裂時(shí)盡量選取不純度低的輸入屬性。上述的熵值可以用作不純性度量，熵值越小，信息增益越大，不純度越小，這種劃分越好。除了熵值之外，還可以采用以下幾種不純度度量方法（僅表示一個(gè)劃分內(nèi)的不純度度量，對(duì)于整體劃分的不純度度量可用各劃分的不純度度量值的加權(quán)和即可）：

? (1) Gini指數(shù)： ，其中fi為該劃分中屬于i分類的訓(xùn)練樣例的比率，Gini系數(shù)是Breiman于1984年提出來(lái)的，主要用在CART(Classfication and Regression Tree)中。

? (2)誤分類誤差：1-max(f1,f2,...,fm)。

? 2.剪枝

? 在創(chuàng)建決策樹(shù)的過(guò)程中，停止分裂的條件是 (1) 該節(jié)點(diǎn)處所有的樣例都屬于同一類別 或者 (2) 沒(méi)有可以用的輸入屬性。

? 但是按照這樣的停止條件訓(xùn)練出來(lái)的決策樹(shù)往往會(huì)過(guò)度擬合(overfit)訓(xùn)練數(shù)據(jù)，亦即該模型對(duì)于訓(xùn)練數(shù)據(jù)有非常高的分類準(zhǔn)確率，但是對(duì)于新的數(shù)據(jù)，分類的準(zhǔn)確率較差。有兩種方法可以用來(lái)避免過(guò)度擬合：

? (1) 及早停止樹(shù)增長(zhǎng)，亦即先剪枝(prepruning)。

? 比如，如果決策樹(shù)中一個(gè)節(jié)點(diǎn)的訓(xùn)練樣例的數(shù)目小于整個(gè)訓(xùn)練集的某個(gè)百分比(如5%)，則該節(jié)點(diǎn)不進(jìn)行分裂，而是對(duì)該節(jié)點(diǎn)訓(xùn)練樣例進(jìn)行"多數(shù)表決"。因?yàn)榛谳^少實(shí)例的決策樹(shù)會(huì)導(dǎo)致較大方差，從而導(dǎo)致較大泛化誤差(Generalization Error)。

? (2)后剪枝(postpruning)。

? 后剪枝的方法很多，這里只介紹訓(xùn)練和驗(yàn)證集法的一個(gè)變種：

? 首先讓決策樹(shù)完全增長(zhǎng)，然后我們找出過(guò)分?jǐn)M合的子樹(shù)并剪裁掉。具體的做法是：我們從之前的訓(xùn)練數(shù)據(jù)中取出一部分作為驗(yàn)證集，其余的還是作訓(xùn)練集。用訓(xùn)練集訓(xùn)練處一個(gè)完全增長(zhǎng)的決策樹(shù)，然后對(duì)于決策樹(shù)中的每個(gè)子樹(shù)，我們都用包含該子樹(shù)的所有訓(xùn)練樣例的葉節(jié)點(diǎn)來(lái)代替，該葉節(jié)點(diǎn)的分類為"多數(shù)表決"的結(jié)果。我們用驗(yàn)證集來(lái)測(cè)試替換前后分類性能的變化。如果替換后分類準(zhǔn)確性有所上升，則我們有理由認(rèn)為之前的那個(gè)子樹(shù)過(guò)于復(fù)雜，對(duì)于訓(xùn)練集中的訓(xùn)練樣例過(guò)度擬合，所以將之替換為葉節(jié)點(diǎn)。否則不予替換。

? 通常的做法是將可用訓(xùn)練樣例的三分之二作為訓(xùn)練集，剩余的三分之一作為驗(yàn)證集。

? 兩種剪枝方法比較，先剪枝比較快，可以再構(gòu)建決策樹(shù)的同時(shí)進(jìn)行。而后剪枝比較慢，要在構(gòu)造完決策樹(shù)之后對(duì)于每一個(gè)子樹(shù)進(jìn)行替換和驗(yàn)證，但是其準(zhǔn)確性比先剪枝要高。

?

參考文獻(xiàn)：

[1] ?算法雜貨鋪——分類算法之決策樹(shù)(Decision tree)

[2] 機(jī)器學(xué)習(xí) Tom M. Mitchell

[3] 機(jī)器學(xué)習(xí)導(dǎo)論 Ethern Alpaydin

機(jī)器學(xué)習(xí)-決策樹(shù)