西瓜书读书笔记整理（五）—

第四章决策树

- 4.1 基本流程
- - 4.1.1 什么是决策树算法
  - 4.1.2 决策树学习的目的
  - 4.1.3 决策树学习基本过程
  - 4.1.4 决策树学习基本算法
  - 4.1.5 递归结束的三种情况
- 4.2 划分选择
- - 4.2.1 信息增益（information gain）—— ID3 决策树学习算法属性划分准则
  - 4.2.2 信息增益率（information gain rate）—— C4.5 决策树学习算法属性划分准则
  - 4.2.3 基尼指数（Gini index）—— CART 决策树学习算法属性划分准则
- 4.3 剪枝算法
- - 4.3.1 剪枝的目的
  - 4.3.2 预剪枝（prepuning）
  - 4.3.3 后剪枝（postpruning）
- 4.4 连续与缺失值
- - 4.4.1 连续值处理
  - 4.4.2 缺失值处理
- 4.5 多变量决策树
- 4.6 总结

4.1 基本流程

4.1.1 什么是决策树算法

决策树算法 是一种通过构建 树形结构 进行分类和回归的机器学习算法。

4.1.2 决策树学习的目的

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的 “分而治之”（divide-and-conquer）策略。

4.1.3 决策树学习基本过程

决策树学习的基本过程如下：

数据准备：首先，收集和准备用于训练的数据集，包含输入特征和对应的标签（类别或数值）。
特征选择：根据特征的不同属性（离散或连续），选择合适的特征选择方法来找到对分类或回归预测有最大信息增益、基尼系数或均方误差等的特征。这一步骤是决策树学习中最重要的一步。
数据划分：将数据集按照选定的特征划分为更小的子集。每个子集中的数据都具有相同的特征值，或者至少有类似的特征属性。
递归构建树：从根节点开始，对每个子集递归地进行特征选择和数据划分，直到满足某个终止条件。终止条件可以是：节点中的数据属于同一类别，节点中的数据样本数量小于某个阈值，或者达到了预先设定的树深度。
叶节点标记：在构建树的过程中，每个叶节点都对应着一个类别标签或回归数值，这些标签或数值由训练数据决定。
剪枝（可选）：为了避免过拟合，可以对构建完成的决策树进行剪枝，即去掉一些分支，使得树的结构更简单，同时也可以提高泛化能力。
预测：使用构建好的决策树对新的输入数据进行预测。从根节点开始，根据输入数据的特征值逐步遍历决策树的分支，直到到达叶节点，然后输出叶节点的类别标签或回归数值作为预测结果。
模型评估：使用测试数据集来评估决策树的性能，通常使用准确率、召回率、F1 分数等指标来评估分类问题的性能，均方误差等指标来评估回归问题的性能。

4.1.4 决策树学习基本算法

原书第 74 页图 4.2

在这里插入图片描述

定义一个函数 TreeGenerate(D,A) 并且这是一个递归算法，因此算法伪代码最后将会重新调用本方法，直到所有的特种特征用尽为止。

面试常常问的可能是其中某一个环节、或者是大体概述整个过程。

4.1.5 递归结束的三种情况

当前结点包含的样本全属于同一类别，无需划分；
当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
当前结点包含的样本集合为空，无法划分。

4.2 划分选择

即 如何选择最优划分属性 （选择属性问题）

4.2.1 信息增益（information gain）—— ID3 决策树学习算法属性划分准则

“信息熵” (information entropy）是度量样本集合纯度最常用的一种指标。

假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k=1,2,...,|\mathcal{Y}|)$ ，则 $D$ 的信息熵定义为

$\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_k \log _2 p_k. \tag{4.1}$

$\operatorname{Ent}(D)$ 的值越小，则 $D$ 的纯度越高。

假设离散属性 $a$ 有 $V$ 个可能的取值 ${a^1, a^2, ...,a^V\}$ ，若使用 $a$ 对样本集 $D$ 进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记作 $D^v$ 。我们可根据式 $(4.1)$ 计算出 $D^v$ 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $D^v|/|D|$ ，即样本数越多的分支结点的影响越大，于是可计算出用属性 $a$ 对样本集 $D$ 进行划分所获得的 “信息增益” (information gain)

$\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \operatorname{Ent}\left(D^v\right) \tag{4.2}$

一般而言，信息增益越大，则意味着使用属性 $a$ 进行划分所获得的 “纯度提升” 越大。因此，我们用信息增益来进行决策树的划分属性选择。著名的 ID3 决策树学习算法就是以信息增益为准则来选择划分属性。

4.2.2 信息增益率（information gain rate）—— C4.5 决策树学习算法属性划分准则

实际上，信息增益准则对可取值数目较多的属性有所偏好 ，为了减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法不直接使用信息增益，而使用 “增益率（gain rate）” 来选择最优划分属性。

$Gain_ratio ⁡ ( D , a ) = Gain ⁡ ( D , a ) IV ⁡ ( a ) (4.3) \operatorname{Gain\_ ratio}(D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)} \tag{4.3}$

其中，

$\operatorname{IV}(a)=-\sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \log _2 \frac{\left|D^v\right|}{|D|} \tag{4.4}$

称为属性 $a$ 的 “固有值” （intrinsic value）。属性 $a$ 的可能性取值数目越多（即 $V$ 越大），则 $I V (a)$ 的值通常会越大。

需注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

4.2.3 基尼指数（Gini index）—— CART 决策树学习算法属性划分准则

CART 决策树使用 “基尼系数” 来选择划分属性。

$\begin{aligned} \operatorname{Gini}(D) & =\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_k p_{k^{\prime}} \\ & =1-\sum_{k=1}^{|\mathcal{Y}|} p_k^2 . \end{aligned} \tag{4.5}$

直观来说， $G ini (D)$ 反映了从数据集 $D$ 中随机选取两个样本，其类别标记不一致的概率。因此， $G ini (D)$ 越小，则数据集 $D$ 的纯度越高。

属性 $a$ 的基尼指数定义为：

$Gini_index ⁡ ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ Gini ⁡ ( D v ) (4.6) \operatorname{Gini\_ index}(D, a)=\sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \operatorname{Gini}\left(D^v\right) \tag{4.6}$

于是，我们在候选属性集 $A$ 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 $Gini_index ⁡ ( D , a ) a_*=\underset{a \in A}\argmin \operatorname{Gini\_index}(D, a)$ 。

4.3 剪枝算法

人类的局限性导致人类在解决一个问题的同时，往往会制造新的问题。

4.3.1 剪枝的目的

剪枝（pruning）是决策树学习算法对付 “过拟合” 的主要手段。

4.3.2 预剪枝（prepuning）

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

4.3.3 后剪枝（postpruning）

后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上对非叶子结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

4.4 连续与缺失值

4.4.1 连续值处理

决策树通常通过二分法来处理连续值特征。在构建决策树的过程中，对于连续值特征，需要选择一个阈值来将其划分为两个子集。以下是处理连续值特征的一般步骤：

特征选择：从所有特征中选择一个连续值特征作为当前节点的划分依据。通常，使用特征选择方法（例如信息增益、信息增益比、基尼系数等）来选择最优的特征。
阈值选择：对于选定的连续值特征，选择一个合适的阈值来将其划分为两个子集。通常的做法是遍历所有可能的阈值，并选择使得划分后的子集使得目标函数最优的阈值。
样本划分：使用选择的阈值，将训练数据中的连续值特征划分为两个子集，一个子集包含小于等于阈值的样本，另一个子集包含大于阈值的样本。
递归构建：对于每个子集，递归地重复步骤1至步骤3，直到满足停止条件（例如达到预定深度、样本数量少于阈值等）。
叶节点标签确定：对于每个划分后的子集，决定叶节点的标签。在分类问题中，通常选择子集中最频繁出现的类别作为叶节点的标签。在回归问题中，可以选择子集中样本标签的平均值作为叶节点标签。

需要注意的是，决策树的构建过程中，连续值特征的选择和阈值的确定是至关重要的，直接影响到决策树的性能和泛化能力。因此，对于连续值特征，特征选择和阈值的选择是决策树算法中的重要环节。在实际应用中，可以使用不同的特征选择方法和阈值搜索策略，或者采用其他预处理技术（如离散化）来更好地处理连续值特征。

4.4.2 缺失值处理

决策树在处理缺失值时有几种常见的策略：

缺失值剔除：最简单的方法是直接删除带有缺失值的样本。这样做可以简化问题，但可能会导致数据的信息损失，特别是当缺失值的数量较大时。
缺失值填充：另一种常见的方法是填充缺失值，使得样本在该特征上具有有效的值。填充方法可以采用均值、中位数、众数等简单的统计量，或者使用其他预测模型来估计缺失值。
缺失值作为单独类别：对于分类问题，可以将缺失值视为一个单独的类别，让决策树根据数据的其他特征来判断样本是否属于缺失值类别。
缺失值分支：在决策树的构建过程中，如果遇到某个样本在某个特征上缺失值，可以考虑将其划分到不同的分支中。这样，在测试时，如果样本的该特征缺失，就可以根据不同分支的情况来进行预测。
缺失值处理算法：一些特定的决策树算法或扩展版本（如XGBoost）具有内置的缺失值处理能力，可以自动处理缺失值并在构建树时考虑缺失值的影响。

需要根据具体情况选择合适的缺失值处理方法。对于某些数据集，直接删除缺失值可能是合理的选择，而在其他情况下，填充缺失值或将其视为独立类别可能更为适用。重要的是在处理缺失值时要注意不引入额外的偏见或错误，并考虑缺失值对模型性能的影响。