决策树与随机森林

• 决策树
• • 中心思想
  • 划分选择
  • • 信息增益
    • 增益率
    • 基尼指数
  • 剪枝处理
  • • 预剪枝
    • 后剪枝
• 随机森林

决策树

中心思想

决策树采用“分而治之”的思想，一般包含一个根结点、若干个内部结点和若干个叶结点。

叶结点：决策结果。

根结点与内部结点：属性测试。

划分选择

信息增益

• 信息增益准则对可取值数目较多的属性有所偏好。

• 假定当前样本集合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。

参考文献：《西瓜书》第四章、第八章