• 构造决策树时其实是使用了「贪心」的策略，在每次划分时选择当前最优的划分方法。

  • 因而应该是无法处理异或数据。

    

A 最优划分策略

希望每次划分子节点能使得子节点所包含的样本尽可能只含同一类别，即「纯度」越来越高。

下面称各类别标签为 $1, 2, \cdots, c, \cdots, C$，对于某种划分条件或者说属性 $a$（比如「纹理」），属性 $a$ 有 $V$ 个取值，能够将当前集合划分成 $V$ 个子节点（比如「清晰」「稍糊」「模糊」）。

A1 信息增益法

i. 信息熵

• 信息熵：将信息熵（不确定性的加权和）用于衡量样本集合的纯度（当 $p_c=0$ 时，规定不确定性为 0）：

  $$ {\rm Ent}(S) = -\sum_{c =1}^C p_c \log_2 p_c $$

  • 信息熵越低，表示纯度越高。信息熵的最小值为 0（各概率显示出确定的类别），最大值为 $\log_2C$（此时各概率均等）。

ii. 信息增益

• 信息增益：对于划分条件 $a$，信息增益定义为其划分前后信息熵之差（其中划分后信息熵需要作加权和）：

  $$ {\rm Gain}(S, a) = {\rm Ent} (S) - \sum_{v=1}^V \frac {|S_v|}{|S|} {\rm Ent} (S_v) $$

  • 于是可以每次选择有最大增益的划分方法 $a^* = \argmax _{a \in A(S)} {\rm Gain}(S, a)$。

• 特点：

  • 对取值数目较多的属性有所偏好。

iii. 增益率

• 固有值：为了对取值数目较少的属性进行偏好，对各个划分条件设置一个权值 ${\rm IV}(a)$，称为固有值（intrinsic value）：

  $$ {\rm IV} (a) = -\sum_{v=1}^V \frac {|S_v|}{|S|} \log_2 \frac {|S_v|}{|S|} $$

  • 属性 $a$ 的可能取值数 $V$ 越大，${\rm IV}(a)$ 通常越大。

• 增益率：增益率即定义为：

  $$ {\rm Gain\_ratio}(S, a) = \frac {{\rm Gain}(S, a)}{{\rm IV}(S, a)} $$

  • 于是可以 $a^* = \argmax _{a \in A(S)} {\rm Gain\_ratio}(S, a)$

• 特点：

  • 对取值数目较少的属性有所偏好。

A2 基尼指数法

i. 基尼值

• 基尼值：定义基尼值来衡量纯度。基尼值指的是在 $S$ 中随机抽取两个样本，其样本标记不一致的概率：

  $$ {\rm Gini}(S) = \sum_{c=1}^C \sum_{c' \neq c} p_c p_{c'} = 1 - \sum_{c=1}^C p_c^2 $$

  

  • 基尼值越低，纯度越高。

ii. 基尼指数

• 基尼指数：基尼指数即为划分后各集合基尼值的加权和。

  $$ {\rm Gini\index}(S, a) = \sum{v=1}^V \frac {|S_v|}{|S|} {\rm Gini}(S_v) $$

  • 于是可以每次选择有最大基尼指数的划分方法 $a^* = \argmax _{a \in A(S)} {\rm Gini\_index}(S, a)$。

B 决策树剪枝

• 剪枝是应对过拟合的主要手段，是为了提高模型的泛化性能。
• 剪枝后，认为叶节点上样例数最多的类别，为此叶节点预测的类别。
• 一般方法是利用验证集进行准确率判断。

B1 预剪枝

• 预剪枝是在决策树生成过程中，对每次划分进行必要性判断。
  • 如果划分后比划分前能够提升整棵树在验证集上的预测准确率，就进行划分；否则不划分，此节点为叶节点。
• 特点：
  • 速度快；
  • 但是可能会没考虑到一些能够导致泛化性能显著提高的后续划分。

B2 后剪枝