决策树剪枝（决策树剪枝是什么意思）

本篇文章给大家谈谈决策树剪枝，以及决策树剪枝是什么意思对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、【理论篇】决策树剪枝策略
• 2、决策树剪枝
• 3、决策树的原理及算法
• 4、西瓜书 第四章 决策树
• 5、在决策树归纳中，为什么树剪枝是有用的
• 6、决策树剪枝(Decision Tree Pruning)

【理论篇】决策树剪枝策略

首先，我们来思考一个问题：决策树为什么要进行剪枝呢？试想一下，如果决策树足够庞大，无限分裂下去，直到每个叶子节点的熵值都为 0 。

这个时候，分类结果没有不确定性，100%准确。这样的决策树最终的结果就是训练集表现非常完美，测试集表现非常糟糕。因此，我们说决策树过拟合的风险很大，理论上可以完全分得开数据。

决策树的剪枝策略包括预剪枝和后剪枝。

预剪枝是指边建立决策树边进行剪枝的操作，也是我们实际决策树训练时更常用的方法，更实用。

常见的预剪枝策略有：限制深度、叶子节点个森棚枣数、叶子节点样本数、信息增益量等。下面，小鱼拿下面的决策树举例，为大家分别做个简单的解释。

限制深度

通过限制深度可以阻止决策树继续向下无限的分裂。比如，上图中，我们限制决策树深度为 3 ，则到达第三层时就全部是叶子节点而不会继续向下分裂了。

叶子节点个数

通过限制决策树最多只能包含多少个叶子节点来限制无限分裂。比如，上图中，我们和吵限制叶子节点个数最多为 4 个，则达到 4 个叶子节点之后，就要停止分裂了。

叶子节点样本数

限制每个叶子节点至少包含多少个样本个数，因为决策树理论上可以分裂到每个叶子节点只有一个样本的野蛮状态。比如，上此拆图中我们可以通过限制每个叶子节点至少包含 1095 个样本，那最右侧的叶子节点就不能继续向下分裂了，到此为止。

信息增益量

通过信息增益量预剪枝具体指某个叶子节点分裂前，其信息增益为 G1，继续分裂后，信息增益变为了 G2，如果 G1 - G2 的值非常小，那就该节点就没必要继续分裂了。

当建立完决策树之后，再来进行剪枝操作。后剪枝策略实际使用的非常少，我们了解即可。

厚剪枝的实现依赖于如下的衡量标准：

上述公式，等式左侧代表最终损失，我们希望决策树最终损失越小越好。等式右侧分别为当前结点的熵或 Gini 系数，参数 α 由用户指定， Tleaf 当前结点分裂后，产生的叶子节点个数。叶子节点越多，损失越大。

下面，小鱼以如下的决策树为例，说明后剪枝策略中的损失函数如何计算。

图中，红色节点在分列前的损失为： 0.4444 * 6 + α ；分裂后的损失需要计算左子树（蓝色）和右子树（绿色）的 gini 系数之和： 0*3 + 0.4444*3 + α*2 。

以上就是决策树剪枝策略的所有内容啦~其中，前剪枝策略是需要我们重点掌握的。

[img]

决策树剪枝

决策树剪枝的目的：防止构建的决策树出现过拟合。

理由：随着决策树的深度的增加，模型的准确度肯定会越来越好。但是对于新的未知数据，模型的表现会很差，泛化能力不够。

在数据集没有足够多的情况下，数据集本身存在噪声，同时数据的特征属性不能完雹猜早全作为分类的标准。以上三点会使决策树出现过拟合现象。

构建如下的损失函数：

其实各个参数的含义：

：树中叶子的个数

:第t个叶子中的样本数量

:第t个叶子的熵

:惩罚因子

可见，模型的复杂度越高，损失越大。

剪枝分为预剪枝和后剪枝两种方法。

在构建 完全正确分类训练集 的决策树之前，停止树的构建。

常见有3种方法来决定何时停止树的构建：

1 预设树的高度。当决策树的高度达到预设值之后，停止继续构建。

2 设定阈值。当叶子结点里的实例数量小于阈值时，停止。

3 设定阈值。计算每一次增加深度后模型的增益，增益小于阈值，则停止。

优点：速度快，计算量少。

缺点：视线短浅。 比如一颗完整的决策树有5层，A- B-C-D-E。

从B-C的过程中模型几乎没有什么提升，但是从C-D的过程中模型的准确度提升显著。这种情况使用预剪枝，会使模型提前终止。

后剪枝的整体思路是先构建完整的决策树，然后再对决策树进行剪枝操作。

错误率降低剪枝（REP,Reduce-Error Pruning）

使用一个测试集。

对于非叶子节点的子树，尝试把它替换成叶子节点。 用子树中样本数量最多的类来表示这个节点的结果。 比较替换前后，两个决策树在测试集上的表现。

从下至上，遍历所有的可能的子树，直到在测试集上没有提升时，停止。

缺点： 当数据量较少时，会兆纳过度剪枝，产生过拟合现象（只着眼于当前少量数据的特征，对于未知数据表现差）。

一些少量的，只出现在训练集中的有效的特征，会被剪掉（因为该特征不出现在测试集中）。

悲观剪枝（PEP，Pessimistic Error Pruning）

特点：从上至下，不用专门使用测试集。

对于决策树中的子树，尝试把它直接替换成一个叶子节点（具体用哪个节点来替代不太确定，有些资料表示直接用子树的根来替换）。

比较 被替换子树的错误数-标准差（由二项分布计算） 和 新叶子节点错误数

如果前者大，那么执行剪枝操作。反之保留。

这里会计算 这个叶子经验错误率E。这个E会在标准差的计算中用到。

公式为：

其中L表示的是子树的叶子个数，0.5为系数，可以调整。

优点：精确度较高。不用分源雀出数据集做测试集。速度快（O（n））

缺点：因为是自顶而下，会出现和预剪枝类似的情况，出现提前终止的情况。

代价复杂度剪枝 （CCP， Cost-Complexity Pruning)

决策树的损失函数：

将 视为变量，当 极小时，最初的决策树就是最优解，当其极大时，只能使用最简单的决策树，也就是根节点作为最优解。所以，当 固定时，可以找到一个最优的决策树结构 。

对于一颗子树而言：

剪枝前：

剪枝后：

这里剪枝后，子树就只有一个节点了。

令剪枝前后的损失相等，可以求得

如果 说明 。执行剪枝操作。

下一步就是对这个子树中每个节点都计算一次

这里g(t)表示剪枝后，整体损失函数的减少程度。

找到最小的g(t)，剪去。

选最小值剪去的原因是，当前节点直至叶子节点的误差差距很小，那说明这几层的构建是没有意义的或者说意义非常少。例如从B子树到叶子节点，整个子树有8层深。这棵8层深树与直接把B节点当整棵子树相比，误差只小了0.0001，那么就没有什么必要构建这8层子树，直接剪掉就好。

整个算法的复杂度为

以上就是决策树剪枝的基本流程，具体选用哪个还是要在实际情况中分析。

决策树的原理及算法

决策树基本上就是把我们以前的经验总结出来。我给你准备了一个打篮球的训练集。如果我们要出门打篮球，一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断，最后得到结果：去打篮球？还是不去？

上面这个图就是一棵典型的决策树。我们在做决策树的时候，会经历两个阶段：构造和剪枝。

构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点：

根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点；

内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”；

叶节点：就是树最底部的节点，也就是决策结果。

剪枝就是给决策树瘦身，防止过拟合。分为“预剪枝”（Pre-Pruning）和“后剪枝”（Post-Pruning）。

预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。

后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。

1是欠拟合，3是过拟合，都会导致分类错误。

造成过拟合的原因之一就是因为训练集中样本量较小。如果决策树选择的属性过多，构造出来的决策树一定能够“完美”地把训练集中的样本分类，但是这样就会把训练集中一些数据的特点当成所有数据的特点，但这个特点不一定是全部数据的特点，这就使得这个决策树在真实的数据分类中出现错误，也就是模型的“泛化能力”差。

p(i|t) 代表了节点 t 为分类 i 的概率，其中 log2 为取以 2 为底的对数。这里我们不是来介绍公式的，而是说存在一种度量，它能帮我们反映出来这个信息的不确定度。当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高。

ID3 算法计算的是信息增益，信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。

公式中 D 是父亲节点，Di 是子节点，Gain(D,a) 中的 a 作为 D 节点的属性选择。

因为岩埋 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率粗闷蚂的方式来选择属性。信息增益率 = 信息增益 / 属性熵，具体的计算公式这里省略。

当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5 来说，属性熵也会变大，所以整体的信息增益率并不大。

ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5 中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。

悲观剪枝是后剪枝技术中的一种，通过罩李递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。

C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢，C4.5 选择具有最高信息增益的划分所对应的阈值。

针对数据集不完整的情况，C4.5 也可以进行处理。

暂无

请你用下面的例子来模拟下决策树的流程，假设好苹果的数据如下，请用 ID3 算法来给出好苹果的决策树。

「红」的信息增益为：1「大」的信息增益为：0

因此选择「红」的作为根节点，「大」没有用，剪枝。

数据分析实战45讲.17 丨决策树（上）：要不要去打篮球？决策树来告诉你

西瓜书 第四章 决策树

这一章主要介绍了决策树是什么，如何构建决策树；前三节针对离散值来对决策树的构建进行说明，而第四小节针对连续值如何处理构建决策树进行说明。

决策树： 基于树状结构，根据样本的属性来对样本进行判断、决策。如：给一个西瓜的各种属性，色泽=“青绿”、根蒂=“缩卷”、声音=“浊响”，通过这些属性来判断这一个西瓜是否为好瓜。

决策树的 叶结点 对应 决策结果 ，而其他结点则对应一个属性的测试， 根结点 则是包括全部样本。

怎样来选择最优属性呢？按属性来划分目的就是让决策树的每一分结点的样本尽可能是同一类，即结点的 “纯度” 越来越高。

判断纯度的高低有三种常用的指标，也是三种决策树算法常使用的。

我们先来看一个新定义， 信息熵 用来度量样本集合纯度的常用指标。 假定当前样本集合D中第K类样本所占比例为 ,则D的信息熵为：

【注】 信息熵越小，D的纯度越高

假定离散属性 有V个可能取值 ，若用 属性对样本集合D进行分类则有V个分支结点，第v个分支结点包含D中所有在属性 取值为 的样本，记为 ； 表示 的 信息熵 ； 表示属性 取值为 的样本占总样本的比重。

定义都清楚后，我们就来看看什么是信息增益了。 信息增益： ，简单点说就是D的信息熵减去按 属性分类后各子集的信息熵的加权平均。

**【注】信息增益越大，说明按这个属性分类后对纯度的提高越大；信息增益是ID3决策树学习并贺算法的常用指标。

增益率是C4.5决策树算法的常用指标，它是信息增益的改进。

定义： ,被称为属性a的“固有值”。

先将各个属性的 信息增益 算出来。得到其 平均值 ，将高于平均值的那些属性选出，再选择其中 增益率 最高的属性。

基尼指数：反映从数据集D中随机抽取两个样本，其类别标记不一致的概率，也可以理解为1-随机抽取两个样本类别一致的概率。

公式：

当我们要计算一个属性a的基尼指数时：

【注】基尼指数最小的属性为最优划分属性

剪枝处理是决策树学习算法应付“过拟合”的主要手段，基本策略有 “预剪枝” 和 “后剪枝” 。

预剪枝：在生成决策树过程中，对每个结点在划分前先估计，若划分后可以提高决策树的泛化能力则划分，否则就以当前结点为叶结点。

后剪枝：先从训练集生成完整的决策树，再自底向上进行判断，将当前结点替换为叶结点能否提高泛化能力，若可以则替换。

要如何判断泛化性能是否提高，这用到前面第二章提到的性能评估，以留出法为例，预剪枝在生成结点前判断生成前后的精度，精度大则泛化能力强，来看是否生成；后剪枝则生成决策树后判断替代前后的精度，看是否替换（书本的例子简单易懂，我这里就不过多简述）。

前面三节的决策树生成都以离散值为例，这里讲一下连续值如何生成决策树。

额外提一下：第三章的线性回归则需要将离散值化通过序连续化或向量化转化为连续值。第四章决策树则需要将连续值离散化。

二分法： 假定连续属性 在样本集D上有n个不同的取值，将这些值从小到大排序，记为 ,我们可以取一个划分点t将D分为子集 ，其中 包含那些在属性a上取值小于t的样本，而 则是取值大于t的样本集合。将集合D一分为二，故称为二分法。

【注】t一备缺般选择两个相邻属性值的中心点，

在使用二分法后，对于划分的点，我们需要判断这样划分是否最优，所以就需要用到前面提到的 信息增益 ， 连续值的信息增益： .

【注】信息增益越大，则其划分越优；且连续值属性作为当前结点的划分属性后，该属性还能作为后代结点的划分属性，这是与离散值属性不同的地方。

面对样本部分属性缺失的情况下，丢弃这些样本会造成信息浪费，且样本数本来有限丢失后有可能使学习器欠拟合。

面对缺失部分属性值的样本集，我们需要解决两个问题：①如何确定划分属性②给定划分属性后，那些缺失属性值的样本怎么划分。

首先，确定划分属仿蔽辩性，我们从没有属性值缺失的样本入手来判断属性a的优劣；划分则将给样本赋予一个权重，有确定属性值的样本权重为一，缺失属性值的样本按权重划分。

给定训练集D和属性 ,令 表示D中在属性 上没有缺失值的样本子集，假定 有V个取值 ,令 表示 中在属性 上取值为 的样本子集， 表示 中属于第k类 的样本子集，给每个样本 赋予一个权重 ，并定义：

对属性a,表示缺失值样本所占比例。

对属性a,表示无缺失值样本中第k类所占的比例。

对属性a,表示无缺失值样本中在属性a上取值 的样本所占比例。

信息增益： ,其中

通过上面的信息增益来判断出将哪个属性作为划分属性最优，这样划分属性就确定下来了，第二个问题就是将缺失属性值的样本按权重分入各个分支中。 举个例子更容易懂：如以属性a为划分属性，a有三个取值1,2,3先将有确定属性值的样本放入分支，假设共有10个样本其a属性有确定属性值，属性值为1有5个，属性值为2有3个，属性值为3有2个，那么这时候某个没有确定属性值的样本则在各分支点权重为 。

将每个属性视为坐标空间的一个坐标轴，那么d个属性的样本对于d维空间的一个点。

决策树形成的分类边界有一个明显特点： 轴平行，即它的分类边界若干个与坐标轴平行的分段组成。

在决策树归纳中，为什么树剪枝是有用的

【答案】B【答案解析】决策树以决策节点为出发点，引喊枣出若搭渗姿干方案枝，每条方案枝代表一个方案。方案枝的末端有一个状态节点，从状态节点引出若干概率枝，每条概率枝代表一种自然状态的决策方法。决策树的知绝分析程序为：①绘制树形图；②计算期望值；③剪枝决策。?

决策树剪枝(Decision Tree Pruning)

决策树的剪枝是将生成的树进行简化，以避免过拟合。

在决策树完美分割学习样例之前，停止决策树的生长。这种提早停止树生长的方法，称为预剪枝方法。

在构造决策树的同时进行剪枝。所有决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个哗丛阈值，即使还可以继续降低熵，也停止继续创建分支。

预剪枝可能会过早停止，降低决策树的准确度。

(1) 作为叶结点或作为根结点配芦歼需要含的最少样本个数

(2) 决策树的层数

(3) 结点的经验熵小于某个阈值才停止

后剪枝是在决策树生长完成之后，对树进行剪枝，得到简化版的决策树。后剪枝是目前最普遍的做法。

后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，这个叶子节点所标识的类别通过大多数原则(majority class criterion)确定。所谓大多数原则，是指剪枝过程中, 将一些子树删除而用叶节点代替,这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识,所标识的类称为majority class。

对于完全决策树中的每一个非叶子节点的子树，我们尝试着把它替换成一个叶子节点，然后比较这替换前后两棵决策树在测试数据集中的表现，如果替换后的决策树在测试数据集中的错误比较少(小于等于），那么该子树就可以被替换成叶子节点。该算法以自底向上(bottom-up)的方式遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。

CCP 方法主要包含两个步骤:

(1)从原始决策树 T0 开始生成一个子树序列 T0 , T 1 , … , Tn .其中 ,T0为原始的整个决策树，Ti +1从 Ti 产生 , Tn 为根节点 。

在步骤 1 中 ,生成子树序列{T0 , T1 , …, Tn}的基本思想是从 T 0 开始, 裁剪 Ti 中关于训练数据集误差增加最小培冲的分枝来得到 Ti+1 .

(2)从第 1 步产生的子树序列中 ,根据树的真实误差估计选择最佳决策树 。如何从第 1 步产生的子树序列 T0 , T1 , T2 , …中选择出 1 棵最佳决策树是 CCP 方法第 2 步的关键 .通常采用的方法有两种, 一种是 K折交叉验证(K-fold cross-validation),另一种是基于独立剪枝数据集 .

PEP 方法是 Quinlan（决策树发明者）为了克服 REP 方法需要独立剪枝数据集的缺点而提出的 ,它不需要分离的剪枝数据集 .为了提高对未来事例的预测可靠性 , PEP 方法对误差估计增加了连续性校正(continuitycorrection).

该方法是唯一一个自顶向下(Top-down)的剪枝算法。

关于决策树剪枝和决策树剪枝是什么意思的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。