统计学习方法 第 05 章 决策树

本篇笔记参考课本的本章总结。

• 决策树即一系列 If-Else-If 组合，其判定条件常见为关于特征值的等式判断（有限取值特征）或大于小于判断（连续特征），可以表达任何「决策逻辑」。
• 决策树算法的关键在于【生成】、【剪枝】，其生成步骤一般会关于训练数据集生成一个「完全学习」（最大限度过拟合）树，然后再运行剪枝算法。
• 决策树生成算法的基本流程是：按照某个指标，在样本所有的特征中选择一个特征进行分组（可能做二分组，也可能做多分组），并且希望该次分组之后样本的混乱程度降低。之后在分组得到的子组中递归继续分组，直到所有的子组别中样本都属于同一类。不同的学习算法有不同的分类指标。训练样本最后会被分类到决策树的叶节点上。测试阶段，如果是分类树，则分类到叶节点之后，将该测试样本分类到该叶节点上训练样本的多数标签。如果是回归树，输出叶节点上训练样本的均值。
• 显然，If-Else-If 式的决策对于存在噪声的机器学习数据是很不稳定的。实际应用中，决策树不会单独使用，而是会使用众多决策树组成随机森林，每棵决策树使用部分样本进行学习，判别时所有决策树进行投票。随机森林的决策树个数越多，则过拟合反而越小，是一个罕见的模型越大越不容易过拟合的机器学习算法。

特征选择标准

【ID3 算法】应用于离散特征，将样本按照离散特征所有可能的取值进行分类。其分类依据为信息增益最大化：

\[\begin{align*} g(D, A) &= H(D) - H(D \mid A) \\ H(D) &= - \sum_k \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|} \\ H(D \mid A) &= \sum_i \frac{|D_i|}{|D|}H(D_i) \\ C_k &:= \operatorname{Count}_D(Y = y_k) \\ D_i &:= \operatorname{Count}_D(A = a_k) \end{align*}\]

指标「信息增益」会倾向于选择取值比较多的特征（一个极端情况，任意实数特征以概率 1 得到正确率为 1 的分类）。【C4.5 算法】与 ID3 算法几乎完全相同，只是信息增益指标被替换为了相对信息增益：

\[\begin{align*} g_R(D,A) &= \frac{g(D,A)}{H_A(D)} \\ H_A(D) &= \sum_a \frac{\operatorname{Count}_D(A=a)}{|D|} \log \frac{\operatorname{Count}_D(A=a)}{|D|} \end{align*}\]

本公式引用自维基百科。注意，此处课本内容没有表达清楚，课本公式 5.10 中的项 H(D) 看上去是个与 A 无关的常量，但该项应该与 A 相关。

另外，应用于 CART 算法的指标为【基尼系数】，特征 A 条件下集合 D 的基尼系数为：

\[\begin{align*} \operatorname{gini}(D,A) &= \frac{|D_1|}{D}\operatorname{gini}(D_1) + \frac{|D_2|}{D}\operatorname{gini}(D_2) \\ \operatorname{gini}(D) &= 1 - \sum_k\left( \frac{C_k}{D} \right)^2 \end{align*}\]

课本上给出的最小二乘指标的回归树生成算法比较简单。其核心步骤与 CART 算法类似，也是选取切分变量和切分点。切分公式很符合直觉：

\[\begin{align*} \min_{j,s}\left[ \min_{c_1}\sum_{x_i\in Left}(y_i-c_1)^2 + \min_{c_2} \sum_{x_i\in Right} (y_i - c_2)^2 \right] \end{align*}\]

剪枝算法基本原理

当按照某个特征选择标准建立决策树直到分类正确率 100% 之后，决策树显然是过拟合的。可以使用剪枝算法修剪决策树。

决策树的剪枝算法需要定义损失函数。其特点是，该损失函数是每个节点的损失相加（而不是全部样本的分类损失之类的指标）。其罚项是节点个数。因此，具有两个叶子节点的内部节点是否应该「收缩」为一个叶节点，可以局部的进行判断。熵、相对熵、基尼系数这三种指标都可以用作节点损失函数。如，使用熵指标写出决策树的损失函数：

\[\begin{align*} C_\alpha(T) &= \sum_{t=1}^{|T|}N_tH_t(T) + \alpha|T| \\ H_t(T) &= - \sum_k \frac{N_{t k}}{N_t} \log \frac{N_{t k}}{N_t} \end{align*}\]

上式中 $t$ 是节点下标，$k$ 是类别下标。使用另外两种指标的损失函数大同小异。

可以推断，$\alpha$ 取值确定时决策树也是确定的。当 $\alpha$ 取不同的值时会得到不同的决策树。CART 剪枝算法使用验证集选择超参数 $\alpha$. 思路是，$\alpha$ 从大到小便利所有取值，得到一系列决策树，然后选取验证集误差最小的决策树作为最终分类结果。

习题

5.3

证明 CART 算法中，当 $\alpha$ 确定，存在唯一最小子树 $T_\alpha$ 使损失函数 $C_\alpha(T_a)$ 最小。

对于未剪枝的满树，每一个具有双叶节点的内部节点（以下简称次叶节点）上，$g(t) = \frac{C(t) - C(T_t)}{

T_t

- 1}$ 是确定的。根据 $\alpha = \min (\alpha, g(t))$, $\alpha$ 确定后，存在个数不少于 1 的节点集合 ${t_i}$ 满足 $g(t_i) = \alpha$. 是否剪枝这些节点不会影响 $C_\alpha(T)$. 剪枝任何其他节点会导致 $C_\alpha(t)$ 增大。于是最小子树就是减去所有这些节点得到的子树。于是最小子树是唯一的。

对于数据 x = [1, 2, 3, 4], y = [0, 1, 0, 1]，建立的决策树是对称的。此时如果 $\alpha$ 的取值令某个节点剪枝，其对称节点叶一定会被剪枝，也即所有的剪枝结果也都是对称的，不会出现不对称的剪枝结果（笔者没有完全理解剪枝算法时，曾经试图构造一对互相对称的剪枝结果作为反例，然而所有的剪枝结果都是对称的）。

5.4

对于所有 $\alpha_0 ≤ \alpha < \alpha_1$ 在所有次叶节点上有 $g(t) > \alpha$ 也即 $C(t) + \alpha > C(T_t) + \alpha

T_t

$, 也即剪枝任意节点 $C(T)$ 递减，所以此时满树为最优子树，而 CART 运行结果也为满树。对于所有 $\alpha_1 ≤ \alpha < \alpha_2$，所有满足 $g(t) < \alpha_1$ 的节点被剪枝。与 $\alpha_0 < \alpha < \alpha_1$ 同理可证，剪枝这些节点能保证 $C(T)$ 递减，而剪枝任意其他节点会导致 $C(T)$ 增大。于是运行结果是最优子树。其他区间同理可证。