摘要：后剪枝先創(chuàng)建完整的決策樹，然后再嘗試消除多余的節(jié)點，也就是采用減枝的方法。

決策樹（decision tree）是一個樹結(jié)構(gòu)，可以是二叉樹或非二叉樹，也可以把他看作是 if-else 規(guī)則的集合，也可以認為是在特征空間上的條件概率分布。

以一個簡單的用于是否買電腦預(yù)測的決策樹為例子:

樹中的內(nèi)部節(jié)點代表一個屬性，節(jié)點引出的分支表示這個屬性的所有可能的值，葉節(jié)點表示最終的分類結(jié)果。從根節(jié)點到葉節(jié)點的每一條路徑構(gòu)建一條規(guī)則，并且這些規(guī)則具有 互斥且完備 的性質(zhì)，即每一個樣本均被且只有一條路徑所覆蓋。

決策樹的創(chuàng)建是根據(jù)給定的訓(xùn)練數(shù)據(jù)來完成的，給出下面的訓(xùn)練集（本章都是圍著這個例子進行講解）：

這是一個是否買電腦的一個數(shù)據(jù)，數(shù)據(jù)上有4個特征：年齡( age )，收入( income )，是否學(xué)生( student )，信用度( credit_rating )。

案例的決策樹中，為什么是以年齡作為第一個進行分類的特征呢？

如果一個特征對結(jié)果影響比較大，那么就可以認為這個特征的分類能力比較大。相親時候一般會先問收入，再問長相，然后問其家庭情況。也就是說在這邊收入情況影響比較大，所以作為第一個特征判斷，如果不合格那可能連后續(xù)都不用詢問了。

有什么方法可以表明特征的分類能力呢？
這時候，需要引入一個概念，熵 。

1948年，香農(nóng)提出“信息熵”的概率。一條信息的信息量大小和它的不確定性有直接的關(guān)系，要搞清楚一件不確定的事，需要了解大量信息。熵(entropy)用于表示 隨機變量不確定性的度量, 如果熵越大，表示不確定性越大。

假設(shè)變量X，它有Xi（i=1,2,3...n）種情況，pi表示第i情況的概率，那么隨機變量X的熵定義為:

$$ H(X) = -sum_{i=1}^np_ilog_2{(p_i)} $$

熵的單位是比特(bit)。

比如當隨機變量X只有0,1兩種取值，則有: H(x) = -plog(p) - (1-p)log(1-p) , 可以畫出一個二維坐標表示他們的關(guān)系:

從而可知，當 p=0.5 時，熵取值最大，隨機變量不確定性最大。

回到買電腦的例子，在是否購買電腦這個結(jié)果中，數(shù)據(jù)集D，有 9 個yes，5 個no。因此它的熵是:

$$ info(D) = H(D) = - frac{9}{14}log_2(frac{9}{14}) - frac5{14}log_2(frac5{14}) = 0.940 bits $$

條件熵(conditional entropy)

隨機變量X給定的條件下，隨機變量Y的條件熵 H(Y|X) 定義為:

$$ H(Y|X) = sum_{i=1}^np_iH(Y|X=x_i) $$

信息增益表示的是：得知 特征X 的信息而使得 分類Y 的信息的不確定性減少的程度。如果某個特征的信息增益比較大，就表示該特征對結(jié)果的影響較大，特征A對數(shù)據(jù)集D的信息增益表示為：

$$ gain(A) = H(D) - H(D|A) $$

以那個買電腦的數(shù)據(jù)集為例，我們來計算下 age 這個特征的信息增益，將數(shù)據(jù)再展示一下：

從圖中可以看出，有14條數(shù)據(jù) age 這個特征中，年輕人 youth 有5人， 中年人 middle_aged 有4人，老年人 senior 有5人。分別計算這三種情況下的信息熵，再將信息熵相加就能得到 H(D|A):

$$ egin{align*} info_{age}(D) = H(D|A) &= frac5{14} imes (-frac25log_2frac25 - frac35log_2frac35) &+frac4{14} imes (-frac44log_2frac44 - frac04log_2frac04) &+frac5{14} imes (-frac35log_2frac35 - frac25log_2frac25) &=0.694 bits end{align*} $$

因此，gain(age) 的信息增益就是:

gain(age) = info(D) - info_{age}(D) = 0.940 - 0.694 = 0.246 bits

ID3算法的核心是在決策樹的各個結(jié)點上應(yīng)用 信息增益 準則進行特征選擇。這個算法也是本章主要介紹的算法。具體做法是：

從根節(jié)點開始，對結(jié)點計算所有可能特征的信息增益，選擇信息增益最大的特征作為結(jié)點的特征，并由該特征的不同取值構(gòu)建子節(jié)點；

對子節(jié)點遞歸地調(diào)用以上方法，構(gòu)建決策樹；

直到所有特征的信息增益均很小或者沒有特征可選時為止。

根據(jù)上面的計算信息增量的方法，可以得出其他特征的信息增量：
gain(income) = 0.029, gain(student) = 0.151, gain(credit_rating)=0.048 。

age 這個特征的信息增益是最大的（0.246 bits），選擇age作為第一個根節(jié)點進行分類:

然后再每個子樹中，再根據(jù)其特征的信息增益量進行每個劃分，遞歸地形成每個劃分上的樣本判定樹。

遞歸劃分步驟僅當下列條件之一成立停止：
(a) 給定結(jié)點的所有樣本屬于同一類。
(b) 沒有剩余屬性可以用來進一步劃分樣本。在此情況下，使用多數(shù)表決。這涉及將給定的結(jié)點轉(zhuǎn)換成樹葉，并用樣本中的多數(shù)所在的類標記它。替換地，可以存放結(jié)點樣本的類分布。
(c) 分枝，當所有特征的信息增益都很小，也就是沒有再計算的必要了，就創(chuàng)建一個樹葉，也是用多數(shù)表決。

C4.5算法與ID3算法的區(qū)別主要在于它在生產(chǎn)決策樹的過程中，使用信息增益比來進行特征選擇。

分類與回歸樹（classification and regression tree,CART）與C4.5算法一樣，由ID3算法演化而來。CART假設(shè)決策樹是一個二叉樹，它通過遞歸地二分每個特征，將特征空間劃分為有限個單元，并在這些單元上確定預(yù)測的概率分布。

CART算法中，對于回歸樹，采用的是平方誤差最小化準則；對于分類樹，采用基尼指數(shù)最小化準則。

這些算法共同點：都是貪心算法，自上而下的創(chuàng)建決策樹。不同點是在于對特征的選擇度量方法不同。

如果樹長到葉子深度太大，就會造成一種情況，在訓(xùn)練集上表現(xiàn)非常好，但是因為分的太細了，在新的數(shù)據(jù)上就表現(xiàn)不好了。就是出現(xiàn)過度擬合的現(xiàn)象。為了避免這個問題，有兩種解決辦法：

先剪枝：當熵減少的數(shù)量小于某一個閾值時，就停止分支的創(chuàng)建。這是一種貪心算法。

后剪枝：先創(chuàng)建完整的決策樹，然后再嘗試消除多余的節(jié)點，也就是采用減枝的方法。

優(yōu)點：

易于理解和解釋，甚至比線性回歸更直觀；

與人類做決策思考的思維習(xí)慣契合；

模型可以通過樹的形式進行可視化展示；

可以直接處理非數(shù)值型數(shù)據(jù)，不需要進行啞變量的轉(zhuǎn)化，甚至可以直接處理含缺失值的數(shù)據(jù)；

缺點：

處理連續(xù)變量不好；

不好處理變量之間存在許多錯綜復(fù)雜的關(guān)系，如金融數(shù)據(jù)分析；

決定分類的因素取決于更多變量的復(fù)雜組合時；

可規(guī)模性一般。