[读书笔记]《西瓜书》第四章 决策树 补充

第四章 决策树 补充

周老师的西瓜书中对于决策树的教授已经非常详细了，但还是有一些在查阅相关资料的时候感觉总结的非常不错，因此自己将其总结在此。

关键知识点

决策树学习的目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类

决策树学习的本质：从训练集中归纳出一组分类规则，将样本集合进行拆分

决策树学习的损失函数：正则化的极大似然函数

决策树学习的测试：最小化损失函数

决策树学习的目标：在损失函数的意义下，选择最优决策树的问题

构造的过程

其实决策树的构造过程整理一下，就三个关键的环节：

• 特征选择
• 树的生成
• 剪枝处理

PS: 因为决策树的构造过程是一种递归择优的过程，因此其在本质上一定会产生过拟合，因此这也是为什么构造决策树之后要进行剪枝处理的原因

虽然决策树的构造过程是三个环节，但是其在实践落实的时候比较难的点是特征选择和剪枝处理。

参考西瓜书中知识点：

在特征选择上也就是三个最具代表性的方式：信息增益、增益率、基尼指数。

PS: 根据信息增益进行特征的选择，其本质上（说人话）是选择了该特征之后，相应的样本集是否变得更加整洁，因此取值越多的特征，即能够分出的类别越多的特征其对于样本集划分越有利。因为这个特性，所以信息增益有个弊端：对可取值数目较多的属性有所偏好

PS: 增益率本身其实是在信息增益的基础上对其加入了一个惩罚项，即引入了一个底，分裂信息（Split Information），将原有的信息增益值除以分裂信息来均衡特征的分类广度和均匀性，其本质上（说人话）是当特征取值越多的时候，使其分裂信息值越大，这样变相的在信息增益没有变动的情况下，增益率变小。因此同样，这个特性：增益率会对可取值数目较少的属性有所偏好

在剪枝处理也同样就两个方向性的概念：预剪枝与后剪枝。

BUT！！！ 虽然树的生成相对要简单一些，但是在什么时候递归进行回返呢？这个地方也有三个需要注意的知识点：

• 当叶子上的数据点都具有相同的预测类别/值时停止
• 当叶子包含少于 $k$ 个数据点时停止
• 当进一步分支不能改善同质性超过最小 $\theta$ 阈值时停止

PS: 这里虽然西瓜书也给了相应的解释（参见上一篇博文的 决策树 知识点摘要），但是在查了一些资料之后，感觉这样总结可能更合适和容易理解，上面说的两个阈值都是需要提前定义好的

经典三算法

根据在特征选择上的三个代表性的方法

ID3 算法

ID3算法是J. Ross Quinlan于1975提出的一种贪心算法，用来构造决策树。其建立在“奥卡姆剃刀”的基础上，即越是小型的决策树越优于大的决策树。此外，ID3不能处理连续分布的数据特征。

生成算法

输入：训练数据集 $D$，特征集 $A$，阈值 $\epsilon$；

输出：决策树 $\mathbf{T}$。

• 若 $D$ 中所有实例属于同一类 $C_k$，则 $\mathbf{T}$ 为单结点树，并将类作为该结点的类标记，返回 $\mathbf{T}$；
• 若 $A = \varnothing$，则 $\mathbf{T}$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $\mathbf{T}$；
• 否则，计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_{g}$；
• 如果 $A_{g}$ 的信息增益小于阈值 $\epsilon$，则置 $\mathbf{T}$ 为单结点树，并将 $D$ 中实例数最大的类作为该结点的类标记，返回 $\mathbf{T}$；
• 否则，对 $A_{g}$的每一可能值 $a_{i}$，依 $A_{g}=a_{i}$将 $D$ 分割为若干非空子集 $D_{i}$，将 $D_{i}$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $\mathbf{T}$，返回 $\mathbf{T}$。
• 对第 $i$ 个子结点，以 $D_{i}$ 为训练集，以为 $A-{A_{g}}$ 特征集，递归地调用步 (1)〜步 (5)，得到子树 $\mathbf{T}_{i}$，返回 $\mathbf{T}_{i}$。

PS: ID3 算法只有树的生成，所以该算法生成的树容易产生过拟合。

C4.5算法

C4.5 算法与 ID3 算法相似，C4.5 算法对 ID3 算法进行了改进。使得能够处理连续分布的数据。

生成算法

输入：训练数据集 $D$，特征集 $A$，阈值 $\epsilon$；

输出：决策树 $\mathbf{T}$。

• 若 $D$ 中所有实例属于同一类 $C_{k}$，则 $\mathbf{T}$ 为单结点树，并将类作为该结点的类标记，返回 $\mathbf{T}$；
• 若 $A= \varnothing$，则 $\mathbf{T}$ 为单结点树，并将 $D$ 中实例数最大的类 $C_{k}$ 作为该结点的类标记，返回 $\mathbf{T}$；
• 否则，计算 $A$ 中各特征对 $D$ 的信息增益比，选择信息增益比最大的特征 $A_{g}$；
• 如果 $A_{g}$ 的信息增益比小于阈值 $\epsilon$，则置 $\mathbf{T}$ 为单结点树，并将 $D$ 中实例数最大的类作为该结点的类标记，返回 $T$；
• 否则，对 $A_{g}$ 的每一可能值 $a_{i}$，依 $A_{g}=a_{i}$ 将 $D$ 分割为若干非空子集 $D_{i}$，将 $D_{i}$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $\mathbf{T}$，返回 $\mathbf{T}$。
• 对第 $i$ 个子结点，以 $D_{i}$ 为训练集，以为 $A-{ A_{g} }$ 特征集，递归地调用步 (1)〜步 (5)，得到子树 $\mathbf{T}_{i}$，返回 $\mathbf{T}_{i}$。

CART算法

分类与回归树 (Classification And Regression Tree, CART) 模型由 Breiman 等人在 1984 年提出，是应用广泛的决策树学习方法。CART 同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。

CART 是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。CART 假设决策树是二叉树，内部结点特征的取值为 “是” 和 “否”，左分支是取值为 “是” 的分支，右分支是取值为 “否” 的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

CART 算法由以下两步组成：

• 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
• 决策树剪枝：用验证数据集对己生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

生成算法

输入：训练数据集 $D$，停止计算的条件；

输出：CART 决策树。

根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

• 设结点的训练数据集为 $D$，计算现有特征对该数据集的基尼指数。此时，对每一个特征对其可能取的每个值 $a$，根据样本点对 $A=a$ 的测试为 “是” 或 “否” 将 $D$ 分割成 $D_{1}$ 和 $D_{2}$ 两部分，计算 $A=a$ 时的基尼指数。
• 在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依据最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
• 对两个子结点递归地调用上述操作，直至满足停止条件为止。
• 生成 CART 决策树。

Reference:

• 【机器学习】深入理解决策树算法
• 决策树模型 - （ID3算法、C4.5算法） - Python代码实现
• ID3算法的原理及实现（Python）
• 机器学习实战（三）——决策树
• DECISION TREES TUTORIAL
• Decision Trees - SCIKIT-LEARN
• Decision Trees in Machine Learning

以上内容也可以到我的 Github 去查看(附了相应实现代码哟) Machine-Learning-Notes