Decission Tree 決策樹 構建與剪枝

開局一張圖

 

總體流程：

    自根至葉的遞歸過程

    在每一箇中間節點尋找一個劃分屬性

終止條件：

    當前節點包含的樣本全屬於同一類別，無需劃分

    當前屬性集爲空，或者所有樣本在所有屬性上取值相同，無法劃分

    當前節點包含的樣本集合爲空，不能劃分

 

本文以周志華老師的西瓜書中的西瓜篩選作爲案例

那麼重點就在於如何選擇每一箇中間節點的劃分屬性了。

既然要選擇，那就需要比較，通常有以下三種比較方法：

 

1. 信息增益 ID3

信息增益即對當前節點的每一個屬性計算劃分後的信息熵變化

我們首先從根節點開始算起，得到根節點的熵，下一步就可以對比每一個屬性劃分後的熵相對於根節點有多少增益。

計算公式：

其中爲每一個分類的概率，該案例中只有兩個分類，「是」，「否」。 

 

然後開始計算下一個節點屬性劃分後的信息增益，先以「色澤」爲例，對「色澤」的每一個屬性值計算信息熵，然後各個屬性值加權平均得到劃分後的信息熵：

按此思路計算當前節點所有屬性的信息增益並比較，選擇增益最大的作爲當前節點的劃分屬性

 

缺點：信息增益會傾向於選擇取值範圍大的屬性，比如把編號作爲屬性，只有一層就可以全部分類，

上面這一步如果採用編號劃分，劃分後的熵就變成0了，每一個屬性劃分後都是十分確定的，只有一個種類。

 

     2. 信息增益率 C4.5

信息增益率基於信息增益進行優化，避免偏好於屬性值較多的屬性。

主要做法就是對屬性的離散度也計算一個熵，用信息增益除以這個熵。

這樣信息增益就起到一定的抑制，但是會大大增加了計算，效率下降。

所以通常先計算信息增益，從信息增益較大的前一個或者是高於平均水平的，再計算信息增益率，選擇最高的

 

        3. 基尼指數 CART (classification and regression tree)

下面是基尼指數的計算公式，需要滿足k=1Kpk=1

基尼指數越小，數據集的純度越高。

對當前節點的每一個屬性劃分後的小份計算基尼指數，然後加權平均

選擇是劃分後基尼指數最小的屬性作爲當前節點劃分屬性。

 

過擬合

對於決策樹來說，過擬合通常就是每一個樣本都落在單獨的葉子節點，決策樹把訓練數據給背下來了

在決策樹中抑制過擬合的方法就是剪枝

 

剪枝

剪掉一些不必要的分支來降低過擬合風險，通常有預剪枝與後剪枝兩種

 

預剪枝

顧名思義，提前終止某些分支的生長。

1. 可以預設樹的高度，當決策樹的高度達到預設值之後，停止繼續構建
2. 設定葉子閾值，當葉子節點裏的實例數量小於閾值時，停止
3. 設定增益閾值，噹噹前節點最大信息增益小於閾值，則停止

優點：

速度快，計算量小

缺點：

視線短淺，比如一棵完整的決策樹有層， A->B->C->D->E. 從B->C的過程中模型幾乎沒有什麼提升，但是從C->D過程中準確度提升明顯，這種情況使用預剪枝，會使模型提前終止

欠擬合風險增加

 

後剪枝

即生成一棵完全樹，再回過頭來剪枝。

常見方法是錯誤率降低剪枝，對所有非葉子節點進行剪枝計算，如果剪枝後再驗證集上錯誤率有下降，那麼就剪掉這一節點

優點：

效果一般優於預剪枝

缺點：

數據量少時容易過度剪枝，某些在訓練集中有的特徵，驗證集中不存在，出現過擬合