《统计学习方法》第五章：决策树

模型

决策树

决策树是一种分类与回归的方法，它是由结点和有向边组成的树形结构。决策树的内部结点表示一个特征或属性，叶结点表示一个类。

决策树学习的目标就是根据给定的训练集生成一个决策树模型，利用该模型对实例正确分类。也就是说决策树的生成在本质上是从训练集中归纳出一组分类规则，决策树中结点之间的路径正是对应了这种分类规则。

分类与回归树

分类与回归树（CART）模型是一种应用广泛的决策树模型，CART 假定决策树为二叉树，左分支为“是”路径，右分支为“否”路径。CART 模型将每个特征不断二分，划分为有限个单元，最后就能在这些单元上进行预测。

策略

决策树可以看作为一系列 if-then 规则的集合，那么如何选择规则的判断条件就十分重要了。选择判断条件就是在选择训练数据的特征，可以想象，如果利用一个特征作为分类条件得到的结果与随机分类的结果没有很大差别，那么这个特征是没有分类能力的。为了生成精确的决策树模型，我们需要设立用于衡量所选特征分类能力的准则。

常用选择特征的准则包括信息增益、信息增益比、平方误差和基尼指数。

信息增益

设一个离散随机分布为

那么随机变量 \(X\) 的熵就定义为

若 \(p_i=0\)，规定 \(0\log 0=0\)，其中的对数也可取 2 为底或取自然对数。熵是衡量随机变量不确定（混乱）程度的度量，熵值越大，则随机变量越不确定，也就是说各事件发生的概率值越接近，概率分布也更分散。

条件熵用于表示在某条件下随机变量的不确定性，条件熵具有条件期望的形式，定义为

在实际操作中会使用频率估计概率，这时候熵就称为经验熵，条件熵称为经验条件熵。

特征 \(A\) 对训练集 \(D\) 的信息增益就定义为训练集的经验熵与给定特征下的经验条件熵之差：

可以直观地理解为，若特征 \(A\) 具有分类能力，在选定的特征 \(A\) 下，数据集表现出更大的确定性或有序性，熵值相应减小，那么熵值变化的大小就可以用来衡量数据集在应用该特征后确定性的增加程度，也就是该特征分类能力的强弱。因此，信息增益大的特征具有更强的分类能力。

对于训练集 \(D\)，用 \(|D|\) 表示集合中元素个数，即样本个数。设有 \(K\) 个类 \(C_k\)，类 \(C_k\) 中有 \(|C_k|\) 个样本。依据特征 \(A\) 可将 \(D\) 划分为 \(n\) 个子集 \(D_i\)，\(D_i\) 中属于类 \(C_k\) 的样本的集合记作 \(D_{ik}\)。那么就按以下方法计算信息增益。

算法 5.1

输入：训练集 \(D\) 和特征 \(A\)
输出：特征 \(A\) 对训练集 \(D\) 的信息增益

1. 计算数据集 \(D\) 的经验熵
   $$H(D)=-\sum_{k=1}^Kp_k\log_2p_k=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}$$
2. 计算特征 \(A\) 对数据集的经验条件熵
   $$H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|}$$
3. 计算信息增益
   $$g(D,A)=H(D)-H(D|A)$$

信息增益比

若参考信息增益比的大小选择特征，选择结果会偏向取值较多的特征。可以这么理解，特征取值越多，即划分条件越多，例如按年龄将人群分为青年、中年、老年（特征取值为 3）相较于按出生地将人群划分为是否当地居民（特征取值为 2），得到的划分结果会更「有序」。但这并不意味着年龄这一特征具有更好的分类能力，分类结果可能与被调查人的出生地有着更为密切的关系。

当特征取值过多时，这个特征就像是精心制作的筛子，过筛后的结果总是「显得」更加有序，因此需要使用信息增益比校正这一问题。信息增益比定义为

其中 \(n\) 为特征 \(A\) 的取值个数。

平方误差

平方误差 \(\sum(y_i-f(x_i))^2\) 是十分常用的误差函数，平方误差常用于回归树的构建。

回归树将输入空间分割为若干单元，并在每个单元 \(R_m\) 上有一个固定的输出 \(c_m\)，可以表示为

在每个单元上的最优输出 \(\hat{c}_m\) 自然是该单元中所有实例对应的输出 \(y_i\) 的均值：

目的是找到最优的切分特征 \(j\) 与最优切分点 \(s\)，那么对于切分后得到的某一块区域 \(R_m\) 内，\(c_m\) 偏离于实例 \(y_i\) 的值都应该尽可能小：

实际上，这就是利用最小二乘法确定单元中的 \(\hat{c}_m\) 并使其平方误差最小，这样回归树又称为最小二乘回归树。

因为回归树是二叉的，每次划分得到两个区域，对于整体而言。最优的划分条件 \(j\) 与 \(s\) 应使得到两个区域 \(c_m\) 的平方误差之和尽可能小，完整求解问题表述为

基尼指数

基尼指数也是特征分类能力的度量，常用于分类树。样本点属于第 \(k\) 类的概率为 \(p_k\)，基尼指数定义为

从基尼指数的定义可以看出，若样本点越分散，基尼指数越大。从下图可以看出，基尼指数与分类误差率、熵有着相似的变化关系，因此基尼指数同样可以用于衡量特征的分类能力。

特征 \(A\) 将样本 \(D\) 划分为两个部分，那么在特征 \(A\) 条件下的基尼指数就表示为

算法

决策树的生成

算法 5.2（ID3 算法）

输入：训练集 \(D\)，特征集 \(A\) 与阈值 \(\varepsilon\)
输出：决策树 \(T\)

1. 若 \(D\) 中所有实例属于同一类（分类完成），将该类作为结节的类标记，返回 \(T\)；
2. 若 \(A=\varnothing\)（无特征可分），将 \(D\) 中实例数量最多的类作为该结点类标记，返回 \(T\)；
3. 否则，计算各特征的信息增益，选择信息增益最大的特征 \(A_g\);
4. 若 \(g(D,A_g)<\varepsilon\)（信息增益小于阈值），将 \(D\) 中实例数量最多的类作为该结点类标记，返回 \(T\)；
5. 否则，使用 \(A_g\) 的可能值 \(a_i\) 将训练集分割为若干 \(D_i\)，将 \(D_i\) 中实例数量最多的类作为类标记构建子结点，返回 \(T\);
6. 对于第 \(i\) 个结点，以 \(D_i\) 为训练集，以 \(A-\{A_g\}\) 为特征集，递归 1~5 步，返回子树 \(T_i\)。

算法 5.4（C4.5 算法）

使用信息增益比代替 ID3 算法中的信息增益，就是 C4.5 算法。

算法 5.4（最小二乘回归树生成算法）

输入：训练数据集 \(D\)
输出： 回归树 \(f(x)\)

1. 选择最优切分变量 \(j\) 与切分点 \(s\)，遍历 \(j\) 与 \(s\)，得到使下式最小的对 \((j,s)\)
   $$\min_{j,s}\left[\min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min_{c_1}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2\right]$$
2. 用对 \((j,s)\) 划分区域并确定 \(\hat{c}_m\)
   $$\begin{gather} R_1(j,s)=\{x|x^{(j)}\leq s\},\quad R_2(j,s)=\{x|x^{(j)}>s\}\\ \hat{c}_m=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i,\quad x\in R_m,\ m=1,2 \end{gather}$$
3. 对子区域继续调用步骤（1）~（2），直至停止；
4. 使用划分的区域生成决策树。

算法 5.6（CART 生成算法）

输入：训练数据集 \(D\)
输出：CART 决策树

1. 计算所有特征对于数据集 \(D\) 的基尼指数，对于所有可能特征 \(A\) 的所有可能取值 \(a\)，使用是否满足 \(A=a\) 作为判断条件将数据集划分为两个部分；
2. 选择基尼指数最小的特征与切分点，生成两个子结点；
3. 对于子结点继续调用 1~2 步，直至停止；
4. 生成 CART 决策树。

References

• 李航, 2019. 统计学习方法（第2版）. 清华大学出版社.