西瓜书读书笔记整理（五）—— 第四章 决策树

4.1 基本流程

4.1.1 什么是决策树算法

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

4.1.2 决策树学习的目的

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

4.1.3 决策树学习基本过程

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

1. 数据准备：首先，收集和准备用于训练的数据集，包含输入特征和对应的标签（类别或数值）。

2. 特征选择：根据特征的不同属性（离散或连续），选择合适的特征选择方法来找到对分类或回归预测有最大信息增益、基尼系数或均方误差等的特征。这一步骤是决策树学习中最重要的一步。

3. 数据划分：将数据集按照选定的特征划分为更小的子集。每个子集中的数据都具有相同的特征值，或者至少有类似的特征属性。

4. 递归构建树：从根节点开始，对每个子集递归地进行特征选择和数据划分，直到满足某个终止条件。终止条件可以是：节点中的数据属于同一类别，节点中的数据样本数量小于某个阈值，或者达到了预先设定的树深度。

5. 叶节点标记：在构建树的过程中，每个叶节点都对应着一个类别标签或回归数值，这些标签或数值由训练数据决定。

6. 剪枝（可选）：为了避免过拟合，可以对构建完成的决策树进行剪枝，即去掉一些分支，使得树的结构更简单，同时也可以提高泛化能力。

7. 预测：使用构建好的决策树对新的输入数据进行预测。从根节点开始，根据输入数据的特征值逐步遍历决策树的分支，直到到达叶节点，然后输出叶节点的类别标签或回归数值作为预测结果。

8. 模型评估：使用测试数据集来评估决策树的性能，通常使用准确率、召回率、F1 分数等指标来评估分类问题的性能，均方误差等指标来评估回归问题的性能。

4.1.4 决策树学习基本算法

原书第 74 页图 4.2

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

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

4.1.5 递归结束的三种情况

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

4.2 划分选择

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

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

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

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

$$\mathrm{Ent}(D)=-\sum _{k=1}^{|\mathcal{Y}|}{p}_k{\log }_2{p}_k.\text{\hspace{1em}(4.1)}$$

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

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

$$\mathrm{Gain}(D,a)=\mathrm{Ent}(D)-\sum _{v=1}^V\frac{\left|D^v\right|}{|D|}\mathrm{Ent}\left(D^v\right)\text{\hspace{1em}(4.2)}$$

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

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

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

$$Gain\_ratio(D,a)=\frac{\mathrm{Gain}(D,a)}{\mathrm{IV}(a)}\text{\hspace{1em}(4.3)}$$

其中，

$$\mathrm{IV}(a)=-\sum _{v=1}^V\frac{\left|D^v\right|}{|D|}{\log }_2\frac{\left|D^v\right|}{|D|}\text{\hspace{1em}(4.4)}$$

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

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

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

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

$$\begin{array}{rl}\mathrm{Gini}(D)& =\sum _{k=1}^{|\mathcal{Y}|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}\\ & =1-\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2.\end{array}\text{\hspace{1em}(4.5)}$$

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

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

$$Gini\_index(D,a)=\sum _{v=1}^V\frac{\left|D^v\right|}{|D|}\mathrm{Gini}\left(D^v\right)\text{\hspace{1em}(4.6)}$$

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

4.3 剪枝算法

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

4.3.1 剪枝的目的

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

4.3.2 预剪枝（prepuning）

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

4.3.3 后剪枝（postpruning）

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

4.4 连续与缺失值

4.4.1 连续值处理

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

1. 特征选择：从所有特征中选择一个连续值特征作为当前节点的划分依据。通常，使用特征选择方法（例如信息增益、信息增益比、基尼系数等）来选择最优的特征。

2. 阈值选择：对于选定的连续值特征，选择一个合适的阈值来将其划分为两个子集。通常的做法是遍历所有可能的阈值，并选择使得划分后的子集使得目标函数最优的阈值。

3. 样本划分：使用选择的阈值，将训练数据中的连续值特征划分为两个子集，一个子集包含小于等于阈值的样本，另一个子集包含大于阈值的样本。

4. 递归构建：对于每个子集，递归地重复步骤1至步骤3，直到满足停止条件（例如达到预定深度、样本数量少于阈值等）。

5. 叶节点标签确定：对于每个划分后的子集，决定叶节点的标签。在分类问题中，通常选择子集中最频繁出现的类别作为叶节点的标签。在回归问题中，可以选择子集中样本标签的平均值作为叶节点标签。

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

4.4.2 缺失值处理

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

1. 缺失值剔除：最简单的方法是直接删除带有缺失值的样本。这样做可以简化问题，但可能会导致数据的信息损失，特别是当缺失值的数量较大时。

2. 缺失值填充：另一种常见的方法是填充缺失值，使得样本在该特征上具有有效的值。填充方法可以采用均值、中位数、众数等简单的统计量，或者使用其他预测模型来估计缺失值。

3. 缺失值作为单独类别：对于分类问题，可以将缺失值视为一个单独的类别，让决策树根据数据的其他特征来判断样本是否属于缺失值类别。

4. 缺失值分支：在决策树的构建过程中，如果遇到某个样本在某个特征上缺失值，可以考虑将其划分到不同的分支中。这样，在测试时，如果样本的该特征缺失，就可以根据不同分支的情况来进行预测。

5. 缺失值处理算法：一些特定的决策树算法或扩展版本（如XGBoost）具有内置的缺失值处理能力，可以自动处理缺失值并在构建树时考虑缺失值的影响。

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

4.5 多变量决策树

多变量决策树（Multivariate Decision Trees）是对传统决策树算法的一种扩展，旨在处理多个特征之间的相互作用和关联。传统的决策树算法（如ID3、C4.5、CART）每次只考虑一个特征来进行划分，因此可能无法充分捕捉多个特征之间的复杂关系。

多变量决策树通过同时考虑多个特征来进行划分，以更好地建模多个特征之间的交互作用。在构建每个节点的决策条件时，它会考虑多个特征的联合情况，而不仅仅是单个特征的划分。这样可以更好地处理特征之间的相关性和非线性关系，提高模型的表现和泛化能力。

多变量决策树的构建过程相对复杂，需要考虑更多的特征组合和划分方式。通常，多变量决策树的构建过程可以通过以下几种方法来实现：

1. 多变量划分准则：传统决策树使用单变量划分准则（如信息增益、基尼系数）来选择最优划分特征。而多变量决策树可以使用多变量划分准则来选择多个特征的组合作为划分依据。

2. 贪心算法：多变量决策树的构建可以采用贪心算法，每次选择能够最大程度提升整体模型性能的多变量划分。

3. 剪枝策略：在多变量决策树的构建过程中，为了防止过拟合，可以采用剪枝策略来简化模型。

4. 集成学习：多变量决策树也可以与集成学习方法（如随机森林、梯度提升树）相结合，进一步提高模型的性能。

需要注意的是，多变量决策树的构建和优化相对复杂，可能需要更多的计算资源和时间。在实际应用中，根据数据集的大小和复杂性，需要权衡不同决策树算法的优势和劣势，选择合适的方法来构建和训练多变量决策树模型。

4.6 总结

决策树算法是一种非常经典、可解释性强的算法，值得好好学习，并把这个作为其他更加复杂、更加高效的算法的学习基础。

Smileyan
2023.08.06 21:54