機器學(xué)習(xí)：決策樹（Decision Tree）

決策樹（decision tree）是一種基本的分類與回歸方法。在分類問題中，它可以認(rèn)為是if-then規(guī)則的集合，也可以認(rèn)為是定義在特征空間與類空間上的條件概率分布。在學(xué)習(xí)時，利用訓(xùn)練數(shù)據(jù)，根據(jù)損失函數(shù)最小化的原則建立決策樹模型；在預(yù)測時，對新的數(shù)據(jù)，利用決策樹模型進(jìn)行分類。

1、決策樹 
1）決策樹是一種樹形結(jié)構(gòu)，其中每個內(nèi)部節(jié)點表示在一個屬性上的測試，每個分支代表一個測試輸出，每個節(jié)點代表一種類別。 
2）決策樹學(xué)習(xí)是以實例為基礎(chǔ)的歸納學(xué)習(xí)，在本質(zhì)上是從訓(xùn)練數(shù)據(jù)集中歸納出一組分類規(guī)則，其學(xué)習(xí)的策略是以損失函數(shù)（損失函數(shù)通常是正則化的極大似然函數(shù)）為目標(biāo)函數(shù)的極小化。 
3）決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法，其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子節(jié)點處的熵值為零，此時每個葉子節(jié)點中的實例都屬于一類。

2、特征選擇 
特征選擇在于選取對訓(xùn)練數(shù)據(jù)具有分類能力的特征，以提高決策樹學(xué)習(xí)的效率。通常特征選擇的準(zhǔn)則是信息增益或信息增益比，在CART樹里使用的是Gini指數(shù)。

2.1 信息增益（information gain） 
首先來了解下熵和條件熵的定義。 
熵（entropy）是表示隨機變量不確定性的度量。設(shè)X是一個取有限個值的離散隨機變量，其概率分布為 

則隨機變量X的熵定義為 

在上式中的對數(shù)通常以2為底或以e為底（自然對數(shù)），這時熵的單位是比特（bit）或納特（nat）.

**條件熵（conditional entropy）**H（Y|X）表示在已知隨機變量X的條件下隨機變量Y的不確定性。定義為X給定條件下隨機變量Y的條件概率分布的熵對X的數(shù)學(xué)期望 

當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計（特別是極大似然估計）得到時，所對應(yīng)的熵和條件熵分別成為經(jīng)驗熵和經(jīng)驗條件熵

信息增益（information gain）表示得知特征X的信息而使得類Y的信息的不確定性減少的程度。 
定義：特征A對訓(xùn)練數(shù)據(jù)集D的信息增益g（D,A），定義集合D的經(jīng)驗熵H（D）與特征A給定條件下D的經(jīng)驗條件熵H（D|A）之差，即： 

一般地，熵與條件熵之差成為互信息（mutual information），決策樹學(xué)習(xí)中的信息增益等價于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。

根據(jù)信息增益準(zhǔn)則的特征選擇方法是：對訓(xùn)練數(shù)據(jù)集（或子集）D，計算其每個特征的信息增益，并比較它們的大小，選擇信息增益最大的特征。

2.2 信息增益比（information gain ratio） 
信息增益的大小是相對于訓(xùn)練數(shù)據(jù)集而言的，并沒有絕對意義。在訓(xùn)練數(shù)據(jù)集的經(jīng)驗熵大的時候，信息增益值會偏大。反之，信息增益值會偏小。使用信息增益比可以對這一問題進(jìn)行校正。 
定義：特征A對訓(xùn)練數(shù)據(jù)集D的信息增益比定義為信息增益g（D,A）與訓(xùn)練集D的經(jīng)驗熵H（D）之比： 

2.3 Gini指數(shù) 
定義：分類問題中，假設(shè)有K個類，樣本點屬于第k類的概率為pk，則概率分布的基尼指數(shù)定義為 

對于給定的樣本集合D，其基尼指數(shù)為 

這里Ck是D中屬于第k類的樣本子集，K是類的個數(shù)。 
基尼指數(shù)Gini（D）表示集合D的不確定性。基尼指數(shù)越大，樣本集合的不確定性也就越大，這一點與熵值類似。 
關(guān)于基尼指數(shù)的討論，鄒博老師也給除了如下圖所示的解釋： 

總結(jié)：一個屬性的信息增益（率）/gini指數(shù)越大，表明屬性對樣本的熵減少的能力更強，這個屬性使得數(shù)據(jù)由不確定性變成確定性的能力越強。

3、決策樹的生成 
3.1 ID3算法 
ID3算法的核心是在決策樹各個結(jié)點上應(yīng)用信息增益準(zhǔn)則來選擇特征，遞歸地構(gòu)建決策樹。ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇。 
算法1 （ID3算法） 
輸入：訓(xùn)練數(shù)據(jù)集D，特征集A，閾值； 
輸出：決策樹T。 
（1）若D中所有實例屬于同一類Ck,則T為單節(jié)點樹，并將類Ck作為該節(jié)點的類標(biāo)記，返回T； 
（3）否則，計算A中各特征的對D的信息增益，選擇信息增益最大的特征Ag； 
（4）如果Ag的信息增益小于閾值，則置T為單結(jié)點樹，并將D中實例數(shù)最大的類為該節(jié)點的類標(biāo)記，返回T； 
（5）否則，對Ag的每一可能值ai，依Ag=ai將D分割為若干非空子集Di，將Di中實例數(shù)最大的類作為標(biāo)記，構(gòu)建子節(jié)點，由結(jié)點及其子結(jié)點構(gòu)成樹T，返回T； 
（6）對第i個子節(jié)點，以Di為訓(xùn)練集，以A-{Ag}為特征集，遞歸地調(diào)用步（1）~步（5），得到子樹Ti，返回Ti。

3.2 C4.5的生成算法 
C4.5算法與ID3算法相似，C4.5是對ID3的改進(jìn)，C4.5在生成的過程中，用信息增益比來選擇特征，其他步驟與ID3一樣。

3.3 CART算法 
CART是在給定輸入隨機變量X條件下輸出隨機變量Y的條件概率分布的學(xué)習(xí)方法。CART假設(shè)決策樹是二叉樹，內(nèi)部節(jié)點特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹等價于遞歸地二分每個特征，將輸入控件即特征空間劃分為有限個單元，并在這些單元上確定預(yù)測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。 
算法2（CART生成算法） 
輸入：訓(xùn)練數(shù)據(jù)集D，停止計算的條件； 
輸出：CART決策樹。 
根據(jù)訓(xùn)練數(shù)據(jù)集，從根節(jié)點開始，遞歸地對每個結(jié)點進(jìn)行以下操作，構(gòu)建二叉決策樹： 
（1）設(shè)結(jié)點的訓(xùn)練數(shù)據(jù)集為D，計算現(xiàn)有特征對該數(shù)據(jù)集的基尼指數(shù)，此時，對每一個特征A，對其可能取的每個值a，根據(jù)樣本點對A=a的測試為“是”或“否”將D分割成D1和D2兩部分，利用上述所給的gini求解公式計算A=a的基尼指數(shù)。 
（2）在所有可能的特征A以及它們所有可能的切分點a中，選擇基尼指數(shù)最小的特征及其對應(yīng)的切分點作為最優(yōu)特征與最優(yōu)切分點。依最優(yōu)特征與最優(yōu)切分點，從現(xiàn)結(jié)點生成兩個子結(jié)點，將訓(xùn)練數(shù)據(jù)集依特征分配到兩個子節(jié)點中去。 
（3）對兩個子節(jié)點遞歸地調(diào)用步驟（1）、（2），直至滿足停止條件。 
（4）生成CART決策樹。 
算法停止的條件是節(jié)點中的樣本個數(shù)小于預(yù)定的閾值，或樣本集的基尼指數(shù)小于預(yù)定閾值，或者沒有更多特征。

4、決策樹的剪枝 
決策樹生成算法遞歸地產(chǎn)生決策樹，直到不能繼續(xù)為止，這樣產(chǎn)生的樹容易過擬合。過擬合的原因在于學(xué)習(xí)時過多地考慮如何提高對訓(xùn)練數(shù)據(jù)的正確分類，從而構(gòu)建出過于復(fù)雜的決策樹。解決這個問題的辦法就是簡化決策樹，即剪枝。

三種決策樹的剪枝過程算法相同，區(qū)別的僅是對于當(dāng)前樹的評價標(biāo)準(zhǔn)不同。（信息增益，信息增益率，基尼指數(shù)）

通常情況下剪枝有兩種：

先剪枝——在構(gòu)造過程中，當(dāng)某個節(jié)點滿足剪枝條件，則直接停止此分支的構(gòu)造。 后剪枝——先構(gòu)造完成完整的決策樹，再通過某些條件遍歷樹進(jìn)行剪枝。數(shù)據(jù)分析師培訓(xùn)

剪枝的總體思路：

由完全樹T0開始，剪枝部分結(jié)點得到T1，再次剪枝部分結(jié)點得到T2，……，直到僅剩樹根的樹Tk;

在驗證數(shù)據(jù)集上對這K個樹分別評價，選擇損失函數(shù)最小的樹Ta

決策樹的剪枝往往通過極小化決策樹整體的損失函數(shù)（loss function）或代價函數(shù)（cost function）來實現(xiàn)。設(shè)樹T的葉結(jié)點個數(shù)為|T|，t是樹T的葉結(jié)點，該葉節(jié)點有個樣本點，其中k類的樣本點有個，k=1,2,…,K，為葉節(jié)點t上的經(jīng)驗熵，為參數(shù)，則決策樹學(xué)習(xí)的損失函數(shù)可以定義為：
其中經(jīng)驗熵為
在上述損失函數(shù)的式中，第一項表示模型對訓(xùn)練數(shù)據(jù)的預(yù)測誤差，|T|表示模型復(fù)雜度，參數(shù)控制兩者之間的影響，較大的促使選擇較簡單的模型（樹），較小的a促使選擇較復(fù)雜的模型（樹）。a=0意味著只考慮模型與訓(xùn)練數(shù)據(jù)的擬合程度，不考慮模型的復(fù)雜度。 
剪枝，就是當(dāng)s確定時，選擇損失函數(shù)最小的模型，即損失函數(shù)最小的子樹。利用損失函數(shù)的極小化等價于正則化的極大似然估計進(jìn)行模型選擇。 
剪枝系數(shù)a的確定，如下所示： 

剪枝算法：