決策樹與隨機森林

02-28

分類決策樹模型是一種描述對實例進行分類的樹形結構。決策樹由結點（node）和有向邊（directed edge）組成。結點有兩種類型：內結點（internal node）和葉結點（leaf node）。內部結點表示一個特徵或者屬性，葉結點表示一個類。

決策樹學習

假設給定訓練數據集：

其中， $x_i$ 為輸入實例（特徵向量）， $y_i$ 為類標記， $N$ 為樣本容量。學習的目標是根據給定的訓練數據集構建一個決策樹模型，使它能夠對實例進行正確的分類。

決策樹學慣用損失函數表示這一目標。決策樹學習的損失函數通常是正則化的極大似然函數。決策樹學習的策略是以損失函數為目標函數的最小化。

決策樹學習演算法包含特徵選擇，決策樹生成和決策樹剪枝三個部分。決策樹的生成只考慮局部最優，而決策樹的剪枝考慮全局最優。

信息增益

首先介紹熵這個概念。在資訊理論與概率統計中，熵（entropy）是表示隨機變數不確定性的度量。設X是一個取有限個值的離散隨機變數，其概率分布為：

$P(X=x_i)=p_i,i=1,2,?,n$

則隨機變數X的熵定義為： $H(X)=-sum_{i=1}^{bN}{p_ilog(p_i)}$

熵只依賴於X分布，而與X的取值無關，所以也可以將X的熵記作H(p)。熵越大，隨機變數的不確定性就越大。

設有隨機變數 $(X,Y)$ ，其聯合概率分布為： $P(X=x_i,Y=y_j)=p_{ij}$

條件熵 $H(Y|X)$ 表示在隨機變數X給定的條件下隨機變數Y的條件熵(conditional entropy)，定義為X給定條件下Y的條件概率分布的熵對X的數學期望：

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

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

信息增益（information gain）表示已知特徵X的信息而使得類Y的信息的不確定性減少的程度。

特徵A對訓練數據集D的信息增益 $g(D,A)$ ，定義為集合D的經驗熵 $H(D)$ 與特徵 $A$ 給定條件下 $D$ 的經驗條件熵 $H(D|A)$ 之差，即： $g(D,A)=H(D)?H(D|A)$

白話一點說這三個概念的聯繫：

熵：表示隨機變數的不確定性。
條件熵：在一個條件下，隨機變數的不確定性。（知道的條件越多，事件不確定性越小）
信息增益：熵 - 條件熵。在一個條件下，信息不確定性減少的程度。
綜上，如果信息增益大的話那麼這個特徵對於分類來說很關鍵。

特徵選擇

特徵選擇在於選取對訓練數據具有分類能力的特徵。這樣可以提高決策樹學習的效率。如果利用一個特徵進行分類的結果與隨機分類的結果沒有很大差別，則稱這個特徵是沒有分類能力的。

決策樹學習應用信息增益準則選擇特徵。信息增益大的特徵具有更強的分類能力。

對訓練數據集（或子集）D,計算其每個特徵的信息增益，並比較他們的大小，選擇信息增益最大的特徵。

信息增益比

以信息增益作為劃分訓練數據集的特徵，存在偏向於選擇取值較多的特徵的問題。使用信息增益比可以對這一問題進行校正。這是特徵選擇的另一準則。

特徵A對訓練數據集D的信息增益比 $g_R(D,A)$ 定義為其信息增益 $g(D,A)$ 與訓練數據集D關於特徵A的值的熵 $H_A(D)$ 之比，即 : $g_R(D,A)=frac{g(D,A)}{H_A(D)}\ H_A(D)=sum_{i=1}^{n}{frac{|D_i|}{|D|}log_2frac{|D_i|}{|D|}}\ n是特徵A取值的個數$

ID3演算法

演算法是在決策樹各個結點上應用信息增益準則選擇特徵，遞歸地構建決策樹。具體方法是：

從根結點開始，對結點計算所有可能的特徵的信息增益，選擇信息增益最大的特徵作為結點的特徵，由該特徵的不同取值建立子結點
再對子結點遞歸地調用以上方法，構建決策樹
直到所有特徵的信息增益均很小或沒有特徵可以選擇為止
最後得到一個決策樹。

ID3相當於用極大似然法進行概率模型的選擇。

C4.5演算法

ID3演算法存在偏向於選取取值較多的特徵的問題，所以改進演算法使用信息增益比來進行特徵選擇，也即C4.5演算法。

剪枝

決策樹生成演算法遞歸地產生決策樹，直到不能繼續下去為止。這樣產生的樹容易出現過擬合現象。過擬合的原因在於學習時過多地考慮如何提高對訓練數據的正確分類，從而構建出過於複雜的決策樹，這樣對訓練數據擬合很好，卻對未知的測試數據分類不準確。

在決策樹學習中講已生成的樹進行簡化的過程稱為剪枝（pruning）。

決策樹的剪枝往往通過極小化決策樹整體的損失函數來實現。

設樹 $T$ 的葉結點個數為 $|T|$ ， $t$ 是樹 $T$ 的葉結點，該葉結點有 $N_t$ 個樣本點，其中 $k$ 類的樣本點有 $N_{tk}$ 個, $H_t(T)$ 為葉節點 $t$ 上的經驗熵，α≥0為參數，則決策樹學習的損失函數可以定義為：

其中第一項表示模型對訓練數據的預測誤差，即模型與訓練數據的擬合程度， $|T|$ 表示模型複雜度，參數α≥0控制兩者之間的影響。較大的α促使選擇較簡單的模型（樹），較小的α促使選擇較複雜的模型（樹）。α=0意味著只考慮模型與訓練數據的擬合程度，不考慮模型的複雜度。

決策樹生成學習局部的模型，而決策樹剪枝學習整體的模型。

樹的剪枝演算法：

輸入：生成演算法產生的整個樹T，參數α；

輸出：修剪後的子樹 $Tα$

計算每個結點的經驗熵
遞歸地從樹的葉結點向上回縮，設一組葉結點回縮到其父結點之前與之後的整體樹分別為 $T_B$ 與 $T_A$ ，其對應的損失函數值分別是 $Cα(T_B)$ 與 $Cα(T_A)$ ，如果 $Cα(T_A)leq Cα(T_B)$ ，則進行剪枝，即將父結點變為新的葉結點
返回上一步，直至不能繼續為止，得到損失函數最小的子樹 $Tα$

CART演算法（分類與回歸樹）

CART假設決策樹是二叉樹，內部結點特徵的取值為「是」和「否」，左分支是取值為「是」的分支，右分支是取值為「否」的分支。這樣的決策樹等價於遞歸地二分每個特徵，將輸入空間即特徵空間劃分為有限個單元，並在這些單元上確定預測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。

特徵選擇按照基尼指數。

隨機森林【暫】

既然都看到這兒了，少年點個贊可好？感謝！

done 2017年11月30日20:42:43