決策樹（decision tree）是一類常見的機器學習方法，顧名思義，決策樹是基于樹結(jié)構(gòu)來進行決策的，這恰是人類在面臨決策問題時一種很自然的處理機制。例如，我們想買西瓜的時候，如何判斷一個好瓜是一項很實用的技能。我們可能會從顏色，根蒂或者敲聲來進行判斷，通常會通過一個優(yōu)先級順序來進行子決策，如圖

西瓜問題的一顆決策樹

一般的，一顆決策樹包含一個根結(jié)點、若干個內(nèi)部結(jié)點和若干個葉節(jié)點；葉節(jié)點對應于決策結(jié)果，其他每個結(jié)點則對應于一個屬性測試；每個結(jié)點包含的樣本集合根據(jù)屬性測試的結(jié)果被劃分到子結(jié)點中；根結(jié)點包含樣本全集。決策樹的學習目的是為了產(chǎn)生一顆泛化能力強，即處理未見示例能力強的決策樹。該算法遵循“分而治之”的策略。如圖

決策樹基本學習算法

顯然，決策樹的生成是一個遞歸過程。在決策樹基本算法中，有三種情形會導致遞歸返回：（1）當前結(jié)點包含的樣本全屬于同一類別，無需劃分；（2）當前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分；（3）當前結(jié)點包含的樣本集合為空，不能劃分。

在第（2）種的情形下，我們把當前結(jié)點標記為葉結(jié)點，并將其類別設(shè)定為該結(jié)點所含樣本最多的類別；在第（3）種情形下，同樣把當前結(jié)點標記為葉結(jié)點，但將其類別設(shè)定為其父結(jié)點所含樣本最多的類別。注意這兩種情形的處理實質(zhì)不同：情形（2）是在利用當前結(jié)點的后驗分布，情形（3）則是把父結(jié)點的樣本分布作為當前結(jié)點的先驗分布。

劃分結(jié)點

決策樹學習最為關(guān)鍵的是確定如何選擇最優(yōu)劃分屬性。一般而言，決策樹的分支結(jié)點所包含的樣本盡可能屬于同一類別，即結(jié)點的純度越來越高。

1、信息增益

“信息熵”（information entropy）是度量樣本集合純度最常用的一種指標。

接下來需要計算信息增益，一般而言，信息增益越大，則意味著使用屬性a來進行劃分所獲得的“純度提升”越大。決策樹基本算法的第八行就是通過選擇最大信息增益來進行劃分屬性的。計算方法如下：

信息增益計算方法

對于西瓜問題，它的屬性有色澤、根蒂、敲聲、臍部、觸感，那首先選擇哪個屬性作為第一個節(jié)點分類呢？這就需要計算他們的信息增益，選擇信息最高的那個，然后再往下重復這一過程。

2、增益率

信息增益最高的并不意味著它是最理想的劃分屬性，例如，有12個西瓜，我給這12個西瓜分別排上1到12的序號，這時，如果我是通過序號來計算信息增益的，可以得到最大的信息增益。這很容易解釋：序號將產(chǎn)生12個分支，每個分支結(jié)點僅包含一個樣本，這些分支結(jié)點的純度已達最大。然而這樣的決策樹是不具備泛化能力的，無法對新樣本進行有效預測。

實際上，信息增益準則對可取值數(shù)目較多的屬性有所偏好，為了減少這種偏好帶來的不利影響，著名C4.5決策樹算法不直接使用信息增益，二是使用“增益率”來選擇最優(yōu)劃分屬性。增益率定義為：

IV(a)成為屬性a的固有值，屬性a可能取值數(shù)目越大，則IV(a)越大。但世上沒有完美的事情，增益率對可取值數(shù)目較少的屬性有所偏好，因此，C4.5算法并不是直接選擇增益率最大的候選劃分屬性，而是使用了一個啟發(fā)式：先從候選劃分屬性中找出信息增益高于平均水平的屬性，再從中選擇增益率最高的。

3、基尼指數(shù)

CART決策樹使用“基尼指數(shù)”來選擇劃分屬性。CART是Classfication and Regression Tree的簡稱，這是一種著名的決策樹學習算法，分類和回歸任務都可用。數(shù)據(jù)集D的純度可用基尼值來度量：

基尼值計算方法

其中p_k是指當前樣本集合中第k類樣本所占的比例為p_k(k=1,2,.....,|y|).直觀來說，Gini(D)反映了從數(shù)據(jù)集D中隨機抽取兩個樣本，其類別標記不一致的概率。因此，Gini(D)越小，則數(shù)據(jù)集的純度越高。

屬性a的基尼指數(shù)定義為：

于是，在候選屬性集合時，選擇那個使得劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性。

剪枝處理

減枝是決策樹學習算法中對付“過擬合”的主要手段。在決策樹學習過程中，有時會造成決策樹分支過多，這時有可能發(fā)生因訓練樣本學的太好了，以致于把訓練集自身的一些特點當作所有數(shù)據(jù)都具有的一般性質(zhì)而導致過擬合。這時可以通過主動去掉一些分支來降低過擬合風險。

決策樹的剪枝策略有“預剪枝”和“后剪枝”。預剪枝是指在決策樹的生成過程中，對每個結(jié)點在劃分前先進行估計，若當前結(jié)點的劃分不能帶來決策樹泛化性能的提升，則將該子樹替換為葉結(jié)點。后剪枝則是先從訓練集生成一顆完整的決策樹，然后自底向上地對非葉結(jié)點進行考察，若將該結(jié)點對應的子樹替換為葉結(jié)點能帶來決策樹泛化能力的提升，則將該子樹替換為葉結(jié)點。

一般情形下，后剪枝決策樹的欠擬合風險很小，泛化性能往往優(yōu)于預剪枝決策樹。但后剪枝過程是在生成完全決策樹之后進行的，并且要自底向上地對樹中的所有非葉子結(jié)點進行逐一考察，因此其訓練時間開銷比未剪枝決策樹和預剪枝決策樹都要大得多。

連續(xù)和缺失值

1、連續(xù)值處理

前面我們主要討論了基于離散屬性來生成決策樹。現(xiàn)實學習任務中常會遇到連續(xù)屬性，有必要討論如何在決策樹學習中使用連續(xù)屬性。

因為連續(xù)屬性的可取數(shù)目不再有限，因此，連續(xù)屬性離散化技術(shù)派上用場。最簡單的策略是采用二分法對連續(xù)屬性進行處理。

缺失值處理

現(xiàn)實任務中常會遇到不完整的樣本，即樣本的某些屬性值缺失。如果簡單地放棄不完整樣本，僅使用無缺失值的樣本進行學習，顯然是對數(shù)據(jù)信息的極大浪費。有必要使用有缺失值的數(shù)據(jù)來進行模型訓練。

這時我們需要解決的問題有兩個：（1）如何在屬性值缺失的情況下進行劃分屬性選擇？

（2）給定劃分屬性，若樣本在該屬性上的值缺失，如何對樣本進行劃分？