開發(fā)者自述：我是如何理解決策樹的

本文作者： AI研習(xí)社

2017-06-21 11:14

導(dǎo)語：關(guān)于決策樹，你了解多少？

雷鋒網(wǎng)按：本文作者夏洪進(jìn)，原載于作者個(gè)人博客，雷鋒網(wǎng)已獲授權(quán)。

前言：

最近學(xué)習(xí)了一段時(shí)間的決策樹算法，但是感覺并沒有達(dá)到自己預(yù)期的想法，所以這幾天參考了一些決策樹方面的資料，來將自己的學(xué)習(xí)的過程的筆記記錄在這里，來加深理解和請(qǐng)教別人指出錯(cuò)誤。

決策樹的原理：

決策樹又叫做decision tree，這個(gè)是一種比較簡(jiǎn)單但是又得到廣泛應(yīng)用的分類器的一種形式。我們一般都是通過訓(xùn)練的數(shù)據(jù)來搭建起決策樹的模型。通過這個(gè)模型，我們可以高效的對(duì)于未知的數(shù)據(jù)進(jìn)行歸納分類，類似于我們的聚類算法。

應(yīng)用決策樹有如下幾個(gè)優(yōu)點(diǎn)：

1：決策樹的模型的可讀性比較好，具有很強(qiáng)的可以描述性，有利于以后高效率的人工分析
2：效率高，決策樹只需要以此構(gòu)建，就可以達(dá)到反復(fù)使用的效果，每一次的預(yù)測(cè)的最大計(jì)算次數(shù)只要不超過決策樹的深度即可。
3：決策樹來如何預(yù)測(cè)：

現(xiàn)在我們以Data Analysis中的經(jīng)典案例來進(jìn)行分析：

開發(fā)者自述：我是如何理解決策樹的

從上邊的表述中的相關(guān)信息，我們可以通過記錄以前的用戶的一些相關(guān)的特性，比如記錄這個(gè)用戶是否可以償還債務(wù)，是否擁有房產(chǎn)，是否結(jié)過婚，年收入等，來構(gòu)建我們所需要的決策樹。

上表根據(jù)歷史數(shù)據(jù)，記錄已有的用戶是否可以償還債務(wù)，以及相關(guān)的信息。通過該數(shù)據(jù)，構(gòu)建的決策樹如下：

開發(fā)者自述：我是如何理解決策樹的

現(xiàn)在假設(shè)新來了一個(gè)用戶：沒有房產(chǎn)，單身狗，年收入5萬，那么根據(jù)上面的決策樹，可以預(yù)測(cè)他無法償還債務(wù)（藍(lán)色虛線路徑）。從上面的決策樹，還可以知道看出來是否擁有房產(chǎn)可以很大的決定用戶是否可以償還債務(wù)，對(duì)借貸業(yè)務(wù)具有指導(dǎo)意義。

基本步驟

現(xiàn)在我們開始學(xué)習(xí)如何構(gòu)造決策樹

決策樹構(gòu)建的基本步驟如下：

1. 開始，把所有記錄看作一個(gè)節(jié)點(diǎn)
2. 遍歷每個(gè)變量的每一種分割方式，找到最好的分割點(diǎn)
3. 分割成兩個(gè)節(jié)點(diǎn)N1和N2
4. 對(duì)N1和N2分別繼續(xù)執(zhí)行2-3步，直到每個(gè)節(jié)點(diǎn)足夠“純”為止

決策樹的變量可以有兩種：

1）數(shù)字型（Numeric）：變量類型是整數(shù)或浮點(diǎn)數(shù)，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作為分割條件（排序后，利用已有的分割情況，可以優(yōu)化分割算法的時(shí)間復(fù)雜度）。

2）名稱型（Nominal）：類似編程語言中的枚舉類型，變量只能重有限的選項(xiàng)中選取，比如前面例子中的“婚姻情況”，只能是“單身”，“已婚”或“離婚”。使用“=”來分割。

如何評(píng)估分割點(diǎn)的好壞？如果一個(gè)分割點(diǎn)可以將當(dāng)前的所有節(jié)點(diǎn)分為兩類，使得每一類都很“純”，也就是同一類的記錄較多，那么就是一個(gè)好分割點(diǎn)。比如上面的例子，“擁有房產(chǎn)”，可以將記錄分成了兩類，“是”的節(jié)點(diǎn)全部都可以償還債務(wù)，非?！凹儭?；“否”的節(jié)點(diǎn)，可以償還貸款和無法償還貸款的人都有，不是很“純”，但是兩個(gè)節(jié)點(diǎn)加起來的純度之和與原始節(jié)點(diǎn)的純度之差最大，所以按照這種方法分割。構(gòu)建決策樹采用貪心算法，只考慮當(dāng)前純度差最大的情況作為分割點(diǎn)。

量化純度

前面講到，決策樹是根據(jù)“純度”來構(gòu)建的，如何量化純度呢？這里介紹三種純度計(jì)算方法。如果記錄被分為n類，每一類的比例P(i)=第i類的數(shù)目/總數(shù)目。還是拿上面的例子，10個(gè)數(shù)據(jù)中可以償還債務(wù)的記錄比例為P(1) = 7/10 = 0.7，無法償還的為P(2) = 3/10 = 0.3，N = 2。

Gini不純度

開發(fā)者自述：我是如何理解決策樹的

熵（Entropy）

開發(fā)者自述：我是如何理解決策樹的

錯(cuò)誤率

開發(fā)者自述：我是如何理解決策樹的

上面的三個(gè)公式均是值越大，表示越“不純”，越小表示越“純”。三種公式只需要取一種即可，實(shí)踐證明三種公司的選擇對(duì)最終分類準(zhǔn)確率的影響并不大，一般使用熵公式。

純度差，也稱為信息增益（Information Gain），公式如下：

開發(fā)者自述：我是如何理解決策樹的

其中，I代表不純度（也就是上面三個(gè)公式的任意一種），K代表分割的節(jié)點(diǎn)數(shù)，一般K = 2。vj表示子節(jié)點(diǎn)中的記錄數(shù)目。上面公式實(shí)際上就是當(dāng)前節(jié)點(diǎn)的不純度減去子節(jié)點(diǎn)不純度的加權(quán)平均數(shù)，權(quán)重由子節(jié)點(diǎn)記錄數(shù)與當(dāng)前節(jié)點(diǎn)記錄數(shù)的比例決定。

停止條件

決策樹的構(gòu)建過程是一個(gè)遞歸的過程，所以需要確定停止條件，否則過程將不會(huì)結(jié)束。一種最直觀的方式是當(dāng)每個(gè)子節(jié)點(diǎn)只有一種類型的記錄時(shí)停止，但是這樣往往會(huì)使得樹的節(jié)點(diǎn)過多，導(dǎo)致過擬合問題（Overfitting）。另一種可行的方法是當(dāng)前節(jié)點(diǎn)中的記錄數(shù)低于一個(gè)最小的閥值，那么就停止分割，將max(P(i))對(duì)應(yīng)的分類作為當(dāng)前葉節(jié)點(diǎn)的分類。

過渡擬合

采用上面算法生成的決策樹在事件中往往會(huì)導(dǎo)致過濾擬合。也就是該決策樹對(duì)訓(xùn)練數(shù)據(jù)可以得到很低的錯(cuò)誤率，但是運(yùn)用到測(cè)試數(shù)據(jù)上卻得到非常高的錯(cuò)誤率。過渡擬合的原因有以下幾點(diǎn)：

1. 噪音數(shù)據(jù)：訓(xùn)練數(shù)據(jù)中存在噪音數(shù)據(jù)，決策樹的某些節(jié)點(diǎn)有噪音數(shù)據(jù)作為分割標(biāo)準(zhǔn)，導(dǎo)致決策樹無法代表真實(shí)數(shù)據(jù)。

2. 缺少代表性數(shù)據(jù)：訓(xùn)練數(shù)據(jù)沒有包含所有具有代表性的數(shù)據(jù)，導(dǎo)致某一類數(shù)據(jù)無法很好的匹配，這一點(diǎn)可以通過觀察混淆矩陣（Confusion Matrix）分析得出。

3. 多重比較：舉個(gè)列子，股票分析師預(yù)測(cè)股票漲或跌。假設(shè)分析師都是靠隨機(jī)猜測(cè)，也就是他們正確的概率是0.5。每一個(gè)人預(yù)測(cè)10次，那么預(yù)測(cè)正確的次數(shù)在8次或8次以上的概率為

開發(fā)者自述：我是如何理解決策樹的

只有5%左右，比較低。但是如果50個(gè)分析師，每個(gè)人預(yù)測(cè)10次，選擇至少一個(gè)人得到8次或以上的人作為代表，那么概率為：

開發(fā)者自述：我是如何理解決策樹的

概率十分大，隨著分析師人數(shù)的增加，概率無限接近1。但是，選出來的分析師其實(shí)是打醬油的，他對(duì)未來的預(yù)測(cè)不能做任何保證。上面這個(gè)例子就是多重比較。這一情況和決策樹選取分割點(diǎn)類似，需要在每個(gè)變量的每一個(gè)值中選取一個(gè)作為分割的代表，所以選出一個(gè)噪音分割標(biāo)準(zhǔn)的概率是很大的。

優(yōu)化方案

1：修剪枝葉

決策樹過渡擬合往往是因?yàn)樘^“茂盛”，也就是節(jié)點(diǎn)過多，所以需要裁剪（Prune Tree）枝葉。裁剪枝葉的策略對(duì)決策樹正確率的影響很大。主要有兩種裁剪策略。

前置裁剪在構(gòu)建決策樹的過程時(shí)，提前停止。那么，會(huì)將切分節(jié)點(diǎn)的條件設(shè)置的很苛刻，導(dǎo)致決策樹很短小。結(jié)果就是決策樹無法達(dá)到最優(yōu)。實(shí)踐證明這中策略無法得到較好的結(jié)果。

后置裁剪決策樹構(gòu)建好后，然后才開始裁剪。采用兩種方法：1）用單一葉節(jié)點(diǎn)代替整個(gè)子樹，葉節(jié)點(diǎn)的分類采用子樹中最主要的分類；2）將一個(gè)字?jǐn)?shù)完全替代另外一顆子樹。后置裁剪有個(gè)問題就是計(jì)算效率，有些節(jié)點(diǎn)計(jì)算后就被裁剪了，導(dǎo)致有點(diǎn)浪費(fèi)。

2：K-Fold Cross Validation

首先計(jì)算出整體的決策樹T，葉節(jié)點(diǎn)個(gè)數(shù)記作N，設(shè)i屬于[1,N]。對(duì)每個(gè)i，使用K-Fold Validataion方法計(jì)算決策樹，并裁剪到i個(gè)節(jié)點(diǎn)，計(jì)算錯(cuò)誤率，最后求出平均錯(cuò)誤率。這樣可以用具有最小錯(cuò)誤率對(duì)應(yīng)的i作為最終決策樹的大小，對(duì)原始決策樹進(jìn)行裁剪，得到最優(yōu)決策樹。

3：Random Forest

Random Forest是用訓(xùn)練數(shù)據(jù)隨機(jī)的計(jì)算出許多決策樹，形成了一個(gè)森林。然后用這個(gè)森林對(duì)未知數(shù)據(jù)進(jìn)行預(yù)測(cè)，選取投票最多的分類。實(shí)踐證明，此算法的錯(cuò)誤率得到了經(jīng)一步的降低。這種方法背后的原理可以用“三個(gè)臭皮匠定一個(gè)諸葛亮”這句諺語來概括。一顆樹預(yù)測(cè)正確的概率可能不高，但是集體預(yù)測(cè)正確的概率卻很高。

準(zhǔn)確率估計(jì)

決策樹T構(gòu)建好后，需要估計(jì)預(yù)測(cè)準(zhǔn)確率。直觀說明，比如N條測(cè)試數(shù)據(jù)，X預(yù)測(cè)正確的記錄數(shù)，那么可以估計(jì)acc = X/N為T的準(zhǔn)確率。但是，這樣不是很科學(xué)。因?yàn)槲覀兪峭ㄟ^樣本估計(jì)的準(zhǔn)確率，很有可能存在偏差。所以，比較科學(xué)的方法是估計(jì)一個(gè)準(zhǔn)確率的區(qū)間，這里就要用到統(tǒng)計(jì)學(xué)中的置信區(qū)間。

設(shè)T的準(zhǔn)確率p是一個(gè)客觀存在的值，X的概率分布為X ~ B(N,p)，即X遵循概率為p，次數(shù)為N的二項(xiàng)分布（Binomial Distribution），期望E(X) = N*p，方差Var(X) = N*p*(1-p)。由于當(dāng)N很大時(shí)，二項(xiàng)分布可以近似有正太分布（Normal Distribution）計(jì)算，一般N會(huì)很大，所以X ~ N(np,n*p*(1-p))。可以算出，acc = X/N的期望E(acc) = E(X/N) = E(X)/N = p，方差Var(acc) =Var(X/N) = Var(X) / N2= p*(1-p) / N，所以acc ~ N(p,p*(1-p)/N)。這樣，就可以通過正太分布的置信區(qū)間的計(jì)算方式計(jì)算執(zhí)行區(qū)間了。

正太分布的置信區(qū)間求解如下：

1）將acc標(biāo)準(zhǔn)化，即

開發(fā)者自述：我是如何理解決策樹的