決策樹與随機森林

• 決策樹
• • 中心思想
  • 劃分選擇
  • • 資訊增益
    • 增益率
    • 基尼指數
  • 剪枝處理
  • • 預剪枝
    • 後剪枝
• 随機森林

決策樹

中心思想

決策樹采用“分而治之”的思想，一般包含一個根結點、若幹個内部結點和若幹個葉結點。

葉結點：決策結果。

根結點與内部結點：屬性測試。

劃分選擇

資訊增益

• 資訊增益準則對可取值數目較多的屬性有所偏好。

• 假定目前樣本集合D中第k類樣本所占的比例為 p k p_k pk​ ，例如 p k p_k pk​指色澤為青綠的瓜中是好瓜的比例。

  則D的資訊熵為：

  E n t ( D ) = − ∑ k = 1 ∣ γ ∣ p k log ⁡ 2 p k Ent(D) = -\sum_{k=1}^{|\gamma|} {p_k}{{\log _2}{p_k}} Ent(D)=−k=1∑∣γ∣​pk​log2​pk​

1. E n t ( D ) Ent(D) Ent(D)的值越小，則 D D D的純度越高。 E n t ( D ) Ent(D) Ent(D)的最小值為0，最大值為 log ⁡ 2 ∣ γ ∣ \log_2|\gamma| log2​∣γ∣。

• 對于離散屬性 a a a而言，有 V V V個可能的取值，若使用 a a a對樣本集 D D D進行劃分，則會産生 V V V個分支結點。其中第 v v v個分支結點包含了 D D D中所有在 a a a屬性上取值為 a v a^v av的樣本。記為 D v D^v Dv 。

  屬性a對樣本集D進行劃分所得到的 “資訊增益”：

  G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 ∣ V ∣ ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a) = Ent(D) -\sum_{v=1}^{|V|}{ \dfrac {|D^v|}{|D|}Ent(D^v)} Gain(D,a)=Ent(D)−v=1∑∣V∣​∣D∣∣Dv∣​Ent(Dv)

  其中： ∣ D v ∣ |D^v| ∣Dv∣：第v個分支結點包含了D中樣本的數量

  ∣ D ∣ |D| ∣D∣：樣本集D中樣本的數量

1. 一般而言，資訊增益越大，意味着使用屬性a來進行劃分所獲得的“純度提升”越大。
2. 一般使用資訊增益進行決策樹的劃分屬性選擇，即選擇屬性 a ∗ = a r g m a x a ∈ A G a i n ( D , a ) a _* = argmax _{a \in A}Gain(D,a) a∗​=argmaxa∈A​Gain(D,a)，例如 I D 3 ID3 ID3決策樹學習算法。

增益率

增益率準則對可取值數目較少的屬性有所偏好。

C 4.5 C4.5 C4.5： 先從候選劃分屬性中找出資訊增益高于平均水準的屬性，再從中選擇增益率最高的。

增益率：

G a i n _ r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) {Gain\_ratio(D,a)} = \dfrac {Gain(D,a)}{IV(a)} Gain_ratio(D,a)=IV(a)Gain(D,a)​

其中

I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ log ⁡ 2 ∣ D v ∣ ∣ D ∣ IV(a) = -\sum_{v=1}^V {\dfrac {|D^v|}{|D|}\log_2\dfrac {|D^v|}{|D|}} IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​

基尼指數

資料集的純度可使用基尼指數來選擇劃分屬性。

G i n i ( D ) = ∑ k = 1 ∣ γ ∣ ∑ k ′ ≠ k p k p k ′ Gini(D) = \sum_{k=1}^{|\gamma|} \sum_{{k'}\neq k}p^kp^{k'} Gini(D)=k=1∑∣γ∣​k′̸​=k∑​pkpk′

= 1 − ∑ k = 1 ∣ γ ∣ p k 2 =1- \sum_{k=1}^{|\gamma|}p_k^2 =1−k=1∑∣γ∣​pk2​

1. G i n i ( D ) Gini(D) Gini(D)越小，資料集 D D D的純度越高。

屬性為 a a a的基尼指數：

G i n i _ i n d e x = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ G i n i ( D v ) Gini\_index = \sum_{v=1}^V \dfrac{|D^v|}{|D|} Gini(D^v) Gini_index=v=1∑V​∣D∣∣Dv∣​Gini(Dv)

1. 從候選屬性集 A A A中，選擇使得劃分後基尼指數最小的屬性作為最優劃分屬性。

剪枝處理

剪枝處理是決策樹算法應對“過拟合”問題的主要手段。

預剪枝

在結點劃分前先進行估計，若通過目前最優屬性對目前結點的劃分不能帶來泛化性能的提升，則停止劃分并将目前結點标記為葉結點。

後剪枝

先從訓練集中生成一顆完整的樹，然後自底向上對非葉結點進行考察，若将該結點對應的子樹替換為葉結點能帶來決策樹泛化性能的提升，則将子樹替換為葉結點。

随機森林

随機森林（Random Forest）是在bagging上的一個擴充變體。

随機森林以決策樹為基學習器建構bagging內建：

• 對于集決策樹的每一個結點，先從結點的屬性集合中随機選取一個包含k個屬性的子集。
• 然後再從此子集中選取一個最優屬性用于劃分。
• 一般取 k = log ⁡ 2 d k=\log_2d k=log2​d。 d d d指代所有的屬性數。
• 随機森林中基學習器的多樣性不僅來自樣本擾動，還來自屬性擾動。
• 随機森林的訓練效率常優于bagging。

參考文獻：《西瓜書》第四章、第八章