機器學習：決策樹（Decision Tree）

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

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

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

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

則隨機變量X的熵定義為 

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

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

當熵和條件熵中的概率由數據估計（特別是極大似然估計）得到時，所對應的熵和條件熵分別成為經驗熵和經驗條件熵

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

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

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

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

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

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

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

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

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

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

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

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

三種決策樹的剪枝過程算法相同，區別的僅是對于當前樹的評價標準不同。（信息增益，信息增益率，基尼指數）

通常情況下剪枝有兩種：

先剪枝——在構造過程中，當某個節點滿足剪枝條件，則直接停止此分支的構造。 后剪枝——先構造完成完整的決策樹，再通過某些條件遍歷樹進行剪枝。數據分析師培訓

剪枝的總體思路：

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

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

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

剪枝算法：