资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

机器学习中的决策树算法：原理、实现与剪枝

创作时间:

作者:

@小白创作中心

机器学习中的决策树算法：原理、实现与剪枝

引用

来源

https://www.cnblogs.com/Codewar/p/18625008

今天继续给大家介绍决策树算法，决策树本身是一种非常简单直观的机器学习算法，用于做分类或回归任务。它就像我们平常做决定时的过程，通过逐步排除可能的选项，最终得出结论。

一个典型的决策树的决策过程如下图：

从上图可以看到一个树的结构包括：

根节点（Root Node）：代表决策过程要问的第一个问题。
内部节点（Internal Nodes）：代表依据特征决策的后续过程，每一个节点根据结果有不同的分支。
分支（Branches）：代表决策的结果，通常会指向下一个节点。
叶节点（Leaf Nodes）：代表最终决策结果，叶节点不会出现分支。

可以看出来决策树至少有两个优点：

直观易懂：决策树的结构就像一棵树，每个节点代表一个属性测试，每条边代表一个测试结果，叶子节点代表最终的分类结果。这种结构非常符合人类的思维方式，让我们很容易理解模型是如何做出决策的。
可解释性强：通过观察决策树，我们可以清晰地看到哪些特征对分类结果影响最大，从而帮助我们更好地理解数据。

理解决策树

决策树有一连串的节点，所有的特征属性其实都可以用来划分支，这个时候至少有两个问题需要弄明白：选择哪些特征作为节点？如何对相应特征进行划分？

选择哪个特征作为节点的时候有一个原则就是先用对模型贡献最大的特征来划分节点，贡献的评估标准有很多：

熵值Entropy：这个熵值是度量数据的不纯度的amount of uncertainty or impurity，我们记住熵值越大数据越不纯就好。那么按照熵值的标准我们希望通过节点后形成的分支数据越纯越好，对应的就是熵值越小越好。
信息增益Information Gain：这个是数据划分前的熵值和通过节点划分后的平均熵值的差，刚刚说了熵值越小越好，那么这个差值应该是越大越好，也就是信息增益越大越好。
基尼纯度Gini Impurity：Gini Index是衡量随机选择一个元素被错误分类的概率。

可以用以上三个标准决定使用哪个特征以及特征使用的先后顺序，具体标准总结如图：

不同的模型贡献评估标准又形成了不同的算法比如，ID3算法就是用信息增益作为贡献标准：选择信息增益最大的属性作为划分属性。C4.5算法用信息增益率，CART算法用基尼指数：CART算法采用基尼指数作为划分属性的选择标准。

那么决策树的整个划分过程又是怎么样的呢？

我们依然来看个例子：想象一下，我们想根据天气情况决定是否去打篮球。我们可以用决策树来表示这个决策过程，步骤如下：

收集数据：首先，我们收集了一些历史天气数据以及是否打篮球的，包括：天气、温度、风力、是否下雨等特征。
选择根节点：假设我们是用ID3算法：

信息增益最大化原则（ID3算法）：我们选择能提供最多信息、最能区分不同决策的属性作为根节点。
在这个例子中，我们计算每个属性（天气、温度、风力、是否下雨）的信息增益，假设计算结果是“是否下雨”的信息增益最大。
所以，我们将“是否下雨”作为根节点。

划分数据集

根据根节点的取值，将数据集分成两个子集：下雨和不下雨。

继续划分子集

对于每个子集，我们再次计算每个属性的信息增益，选择信息增益最大的属性作为划分属性。
假设对于“不下雨”这个子集，“温度”的信息增益最大。
那么，我们将“不下雨”这个子集根据“温度”划分成“温度高”和“温度不高”两个子集。
对于“下雨”这个子集，由于样本太少或其他原因，我们可能直接将其作为叶子节点，即“不下篮球”。

就这么一个思考过程决策树就出来了，决策树也就相应出来了：

所以一个常规的树的生成总结起来就是下面四步：

计算每个属性的信息增益、信息增益率或基尼指数。
选择增益最大的属性作为划分属性。
根据该属性的不同取值，将数据集划分成若干个子集。
对每个子集递归地重复上述过程，直到满足停止条件。

决策树的剪枝

大家也可以想想按照上面决策树的生成流程我一直划分一直划分下去，总是可以非常精确的，这就会产生过拟合问题，为了防止过拟合，通常需要对决策树进行剪枝。剪枝的方法主要分为预剪枝和后剪枝。

预剪枝：在树生成过程中提前停止分支生长。比如我们可以设置最大深度、设置节点包含的最小样本数、设置信息增益阈值。
后剪枝：先生成一棵完整的树，然后自底向上地剪掉一些分支。比如错误率降低剪枝 (Reduced-Error Pruning, REP) *代价复杂度剪枝 (Cost-Complexity Pruning, CCP)都属于后剪枝。

决策树实操

我们依然用iris数据集进行演示，上篇讲朴素贝叶斯的文章也是用的这个数据集，大家可以对比着看下结果。以Species作为因变量，其余变量作为自变量构建决策树代码如下：

训练好的模型在验证集中的表现如下：

针对连续特征的回归树

刚刚讲的决策树都是针对分类结局的，决策树也可以用于连续结局，叫做回归树。

比如我现在有数据集，结局是年薪（连续变量），两个预测变量，一个是工作年限，一个是工作经验HmRun，通过数据可以形成一个如下图所示的决策树：

那么对于一个工作年限为8年，工作经验为10的个体来说，模型预测其年薪结果就为577.6

上面过程也有两个问题，一个是特征分割的条件标准，另一个问题是叶节点的值是如何来的。

选择最佳划分特征和划分点：对于每个特征，遍历所有可能的划分点，计算划分后的子节点的均方误差（或其他指标），选择使均方误差最小的特征和划分点作为特征以及对应特征的划分点，回归树的叶节点输出的是该节点包含的所有训练样本目标值的平均值或中位数。

When the dependent variable is continuous, its value can be predicted using regression trees. These predict using the average values of ȳ within each subset

看一个回归树的例子，我现在有数据如下：

我想用数据集中的特征来预测medv: 房价中位数，做一个回归树，代码如下：

运行代码后输出结果如下：

这个是没有剪枝前的模型，我们看下模型的效果：

运行后可以得到模型的mse是16.24467，我们对模型进行剪枝过后再看变成下图：

相应的模型的mse也变成了10.3362。说明剪枝确实提高了拟合效果。

通过上面的叙述相信大家对剪枝带来的直观效果有印象了，继续带大家捋捋这个剪枝到底怎么减的。

Pruning剪枝实操

如果回归决策树的分支过多，容易造成过拟合。剪枝主要分为两种方法：预剪枝和后剪枝。

预剪枝（Pre-Pruning）：

预剪枝是在树的构建过程中进行的。它通过提前停止树的生长来达到剪枝的目的。具体方法包括：

限制树的深度（max_depth）：设置树的最大深度，当树达到指定深度时就停止生长。例如，设置max_depth=3意味着树最多有3层。
限制节点包含的最小样本数（min_samples_split）：规定一个节点如果要分裂，至少需要包含多少个样本。如果一个节点包含的样本数少于这个阈值，则该节点不再分裂。
限制叶节点包含的最小样本数（min_samples_leaf）：规定一个叶节点至少需要包含多少个样本。如果一个节点分裂后，某个子节点包含的样本数少于这个阈值，则该分裂不进行。
限制叶节点的最小权重总和（min_weight_fraction_leaf）：与min_samples_leaf类似，但使用样本权重的总和而不是样本数。
设定分裂的阈值（如信息增益、基尼指数的阈值）：当分裂带来的增益小于设定的阈值时，停止分裂。

举例说明预剪枝：假设我们设置min_samples_split=10。这意味着只有当一个节点包含至少10个样本时，它才会被考虑分裂。如果一个节点只包含8个样本，即使它可以被分裂成更“纯”的子节点，也不会进行分裂，从而避免了树的过度生长。

后剪枝（Post-Pruning）：

后剪枝是先让树完整地生长，然后再自底向上地对树进行修剪。它通过删除一些子树或将子树替换为叶节点来简化树的结构。常用的后剪枝方法包括：

降低错误剪枝（Reduced Error Pruning）：将数据集分成训练集和验证集。首先使用训练集构建完整的树，然后从底向上遍历每个非叶节点，尝试将其子树替换为叶节点。如果替换后在验证集上的错误率降低或保持不变，则进行替换；否则，不进行替换。
代价复杂度剪枝（Cost-Complexity Pruning）：为树的每个非叶节点定义一个代价复杂度因子（α），它衡量了剪枝带来的误差减少量与剪掉的叶节点数量之间的权衡。通过调整α的值，可以得到一系列不同复杂度的树。然后使用交叉验证等方法选择最佳的α值，并根据该值对树进行剪枝。

举例说明后剪枝：假设我们构建了一棵完整的树，其中一个非叶节点A有两个子节点B和C。我们尝试将节点A的子树（包括B和C）替换为一个叶节点，该叶节点的值为B和C包含的所有样本目标值的平均值。如果替换后在验证集上的均方误差降低了，则进行替换；否则，保留原来的子树。

故决策树剪枝的主要思想是防止模型在训练集中出现过拟合现象，使模型在测试集中的表现更好。预剪枝的逻辑我们其实很清楚了，现在我们以代价复杂度剪枝为例子看看后剪枝到底是如何操作的：

首先我们得有一个代价函数，如下图：

代价函数通常由两部分组成：