1. 章節(jié)主要內(nèi)容

決策樹是機器學習的一類常見算法，其核心思想是通過構(gòu)建一個樹狀模型來對新樣本進行預(yù)測。樹的葉結(jié)點是預(yù)測結(jié)果，而所有非葉結(jié)點皆是一個個決策過程。

要相對深入的了解決策樹機器學習算法，我們將按照以下的分標題順序由淺入深的進行介紹。

1）決策樹算法的基本流程

一般的，一顆決策樹包含一個根結(jié)點、若干內(nèi)部結(jié)點和若干個葉結(jié)點；葉結(jié)點對應(yīng)于決策結(jié)果，其它每個內(nèi)部結(jié)點（包括根結(jié)點）則對應(yīng)一個屬性測試。決策樹根據(jù)內(nèi)部結(jié)點的屬性測試結(jié)果將該結(jié)點所包含的樣本集按照屬性測試的結(jié)果被劃分到不同的子結(jié)點中。

這是一種簡單且直觀的“分而治之”（divide-and-conquer）策略，決策樹學習的目的是為了產(chǎn)生一顆泛化能力強的決策樹。

套用俗語，決策樹分類的思想類似于找對象?，F(xiàn)想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：

女兒：多大年紀了？

母親：26。

女兒：長的帥不帥？

母親：挺帥的。

女兒：收入高不？

母親：不算很高，中等情況。

女兒：是公務(wù)員不？

母親：是，在稅務(wù)局上班呢。

女兒：那好，我去見見。

這個女孩的決策過程就是典型的分類樹決策。相當于通過年齡、長相、收入和是否公務(wù)員對將男人分為兩個類別：見和不見。假設(shè)這個女孩對男人的要求是：30歲以下、長相中等以上并且是高收入者或中等以上收入的公務(wù)員，那么這個可以用下圖表示女孩的決策邏輯：

上邊的訓練過程就是我所理解的決策樹構(gòu)建過程，其實它就是一個將數(shù)據(jù)按屬性分堆的過程。雖然名字叫的挺高大上的，但是背后的邏輯卻十分簡單。

既然決策樹那么簡單，我想有人應(yīng)該會疑問“為什么還有那么多的人在一直研究和使用決策樹”了。其實，這也不難理解吧，既然決策樹的背后邏輯十分簡單（其實大多數(shù)算法的思想都很簡單，大家不要被復(fù)雜的公式嚇到），那么它較難的地方就不在于這個背后邏輯了，它難的一定是在別的地方。

也許細心的人已經(jīng)發(fā)現(xiàn)了我所舉的例子中有些問題是沒有解答的，比如我們是根據(jù)什么策略來決定屬性測試的順序的（年齡 > 長相 > 收入 > 公務(wù)員）；這些選定屬性的取值是如何決定的（什么叫帥、什么叫丑，標準是什么）；這個構(gòu)建的決策樹是否足夠泛化，能涵蓋新樣本數(shù)據(jù)的可能情況等

這些問題才是決策樹tricky的地方所在，不過沒關(guān)系，大家不要著急，這些內(nèi)容我們將在下邊一一進行解答。

2）屬性的劃分選擇

隨著劃分過程不斷進行，我們希望決策樹的分支結(jié)點所包含的樣本盡可能屬于同一類別，即結(jié)點的“純度”（purity）越來越高。

要使得結(jié)點純度越來越高，我們得要選擇合適的指標來對純度進行評估，并且我們也得要在這些指標上對屬性的劃分進行選擇。目前決策樹主流使用的屬性劃分指標為以下三個：

［1］信息增益

“信息熵”（information entropy）是度量樣本集合純度最常用的一種指標。其代表的是不同的類別在數(shù)據(jù)在總數(shù)據(jù)集中的熵的和，當樣本集合越“純”時，信息熵越小（信息熵的取值范圍為0～log2(k)）。

既然信息熵代表的是樣本集合的純度，那么我們一個合理的屬性劃分邏輯可以是這樣的：當用一個屬性對樣本進行劃分后，分開的不同樣本集合的信息墑之和純度最高，那么這個屬性就是目前最好的劃分選擇。

原始信息熵與新的劃分后的信息墑之差就是這次屬性劃分的“信息增益”（information gain），所以我們的屬性劃分選擇就是在每個結(jié)點找到最高信息增益的屬性。

［2］增益率（gain ratio）

信息增益是個優(yōu)秀的屬性劃分指標，可實際上，信息增益準則對可取值數(shù)目較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響，選擇增益率來選擇最優(yōu)劃分屬性。

增益率是讓信息增益除以選擇的劃分屬性的“固有值”（intrinsic value）。一般來說屬性a的可能取值數(shù)目越多，則固有值越大，所以信息增益除以固有值后，抵消了信息增益對取值數(shù)目多的屬性的偏好。

需注意的是，信息增益除以固有值后獲得的增益率反而是偏愛取值數(shù)目較少的屬性的，所以一個合理利用增益率來對屬性劃分的方法是：先從候選劃分屬性中選出信息增益高于平均水平的屬性，再從中選擇增益率最高的。

［3］基尼指數(shù)

基尼值的公式如下：

Gini(D) = 1 - pk的平方

從上式可以看出，基尼值反映了從數(shù)據(jù)集D中隨機抽取兩個樣本，其類別標記不一致的概率。因此，基尼值越小，則數(shù)據(jù)集D的純度越高。

那么同信息增益的選擇策略一樣：當用一個屬性對樣本進行劃分后，原始基尼值與新劃分后的不同樣本集合的基尼值之和的差值就是“基尼指數(shù)”（Gini index），所以我們的屬性劃分選擇就是在每個結(jié)點找到劃分后最高基尼指數(shù)的屬性。

3）剪枝處理

剪枝（pruning）是決策樹學習算法對付“過擬合”的主要手段。為了盡可能正確分類訓練樣本，會不斷的進行結(jié)點劃分，有時會造成決策樹分支過多，這時就可能因為訓練過程學得太好了，將訓練集自身的一些特點當作普遍化特征進行學習而會導致過擬合。

因此，可通過主動去掉一些分支來降低過擬合的風險。目前決策樹剪枝的基本策略有以下兩種：

［1］預(yù)剪枝

在決策樹生成過程中，對每個結(jié)點在劃分前后進行估計，若當前結(jié)點的劃分不能帶來決策樹泛化性能提升，則停止劃分并將當前結(jié)點標記為葉結(jié)點。

［2］后剪枝

在訓練出一顆完整的決策樹之后，自底向上的對非葉結(jié)點進行考察，若將該結(jié)點對應(yīng)的子樹替換成葉結(jié)點能提升泛化性能，則將該子樹替換為葉結(jié)點。

［3］剪枝過程

使用第二章中提到的性能評估方法來比較泛化性能的改變；

從樣本預(yù)留出一部分數(shù)據(jù)用作“驗證集”以進行性能評估。

4）連續(xù)與缺失值

在前邊提到的決策樹處理邏輯中的屬性使用的都是離散值，那么當遇到屬性是連續(xù)或缺失時，我們應(yīng)該知道該如何處理。

［1］連續(xù)值處理

遇到連續(xù)值屬性的一個合適的處理邏輯是：將連續(xù)值轉(zhuǎn)換為離散值不就得了。我們需要做的是將訓練樣本中該屬性的所有取值進行排序，并對這排好序的取值隊列進行分區(qū)劃分，每一個分區(qū)即為該屬性的一個離散點取值。

不失一般性，我們就取二分法（即分為兩個分區(qū)，可以根據(jù)需要分為N個）來進行描述。以身高劃分為例，訓練集中身高數(shù)據(jù)取值（cm）排序如下：

｛160，163，168，170，171，174，177，179，180，183｝

因為是二分法，我們只需要找到一個劃分點即可。每個劃分點可放在兩個取值之間，也可放在一個取值之上，這里我們?nèi)蓚€取值之間的中位數(shù)。那么上邊例子中可選的劃分點為：

｛161.5，165.5，169，170.5，172.5，175.5，178，179.5，181.5｝

根據(jù)不同的劃分，我們可以分別計算一下信息增益的大小，然后選出一個最好的劃分來。

需注意的是，和離散值不同，連續(xù)值的劃分是可以在子結(jié)點上繼續(xù)劃分的。即你將身高劃分為“小于175”和“大于等于175”兩部分，對于“小于175”的子結(jié)點，你仍然可以繼續(xù)劃分為“小于160”和“大于160”兩部分。

［2］缺失值處理

屬性缺失時，我們需要處理兩個問題：

第一，如何在屬性值缺失的情況下進行屬性劃分選擇

不將缺失值的樣本代入選擇判斷的公式計算（信息增益、增益率、基尼指數(shù)）之中，只在計算完后乘以一個有值的樣本比例即可。

比如訓練集有10個樣本，在屬性 a 上，有兩個樣本缺失值，那么計算該屬性劃分的信息增益時，我們可以忽略這兩個缺失值的樣本來計算信息增益，然后在計算結(jié)果上乘以8/10即可。

第二，若一個樣本在劃分屬性上的值為空，它應(yīng)該被分在哪個子結(jié)點中

若樣本 x 在劃分屬性 a 上取值未知，則將 x 劃入所有子結(jié)點，但是對劃入不同子結(jié)點中的 x 賦予不同的權(quán)值（不同子結(jié)點上的不同權(quán)值一般體現(xiàn)為該子結(jié)點所包含的數(shù)據(jù)占父結(jié)點數(shù)據(jù)集合的比例）。

5）多變量決策樹

在學習任務(wù)的真實分類邊界比較復(fù)雜時，必須使用很多段劃分才能獲得較好的近似，此時的決策樹會相當復(fù)雜，由于要進行大量的屬性測試，預(yù)測時間開銷會很大。

若能使用斜的劃分邊界，則決策樹模型將大為簡化，這就是多變量決策樹（multivariate decision tree）。在此類決策樹中，非葉結(jié)點不再是僅對某個屬性，而是對屬性的線性組合進行測試；換言之，每個非葉結(jié)點時一個形如線性回歸的線性分類器了。下圖是一個在連續(xù)屬性密度和含糖率上的選瓜多變量決策樹樣例：

2. 基礎(chǔ)知識

1）信息熵

2）信息增益

3）增益率

4）基尼指數(shù)

3. 總結(jié)

1）決策樹采用的是一種簡單且直觀的“分而治之”（divide-and-conquer）策略

2）決策樹根據(jù)數(shù)據(jù)集的總體純度來衡量不同屬性劃分的優(yōu)劣

3）當屬性選擇過于頻繁會導致模型過擬合，這時候就需要使用剪枝算法來進行處理

4）剪枝算法的判斷標準是剪枝前后模型的性能指標是否提高

5）當遇到連續(xù)值的屬性時，可以通過將其拆解成兩塊的方式將數(shù)據(jù)轉(zhuǎn)換為連續(xù)值

6）當遇到缺失值屬性時，可以通過在屬性選擇算法中加入缺失值數(shù)據(jù)的影響來適應(yīng)

7）在處理真實分類邊界比較復(fù)雜的學習任務(wù)時，我們可以使用屬性的線性組合來對數(shù)據(jù)進行劃分