决策树(decision tree)(二)——剪枝

**注:本博客为周志华《机器学习》读书笔记,虽然有一些自己的理解,但是其中仍然有大量文字摘自周老师的《机器学习》书。
决策树系列博客:

  1. 决策树(一)——构造决策树
  2. 决策树(二)——剪枝
  3. 决策树(decision tree)(三)——连续值处理
  4. 决策树(四)缺失值处理

前面在 决策树(decision tree)(一) 中介绍了几种对结点划分的方法( 信息增益、信息增益率、基尼指数 ),在这篇博客里主要介绍剪枝,即;

  1. 预剪枝(pre-pruning)
  2. 后剪枝(post-pruning)

首先剪枝(pruning)的目的是为了避免决策树模型的 过拟合 。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本,不停地对结点进行划分,因此这会导致整棵树的分支过多,也就导致了 过拟合 。决策树的剪枝策略最基本的有两种:预剪枝(pre-pruning)和后剪枝(post-pruning):

  • 预剪枝(pre-pruning) 预剪枝就是在构造决策树的过程中,先对每个结点在划分前进行估计,若果当前结点的划分不能带来决策树模型泛华性能的提升,则不对当前结点进行划分并且将当前结点标记为叶结点。
  • 后剪枝(post-pruning):后剪枝就是先把整颗决策树构造完毕,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛华性能的提升,则把该子树替换为叶结点。

一、预剪枝(pre-pruning)
关于预剪枝(pre-pruning)的基本概念,在前面已经介绍过了,下面就直接举个例子来看看预剪枝(pre-pruning)是怎样操作的。数据集为(图片来自西瓜书):

这个数据集根据信息增益可以构造出一颗未剪枝的决策树(图片来自西瓜书):

下面来看下具体的构造过程:
前面博客( 决策树(一) )讲过用信息增益怎么构造决策树,这边还是用信息增益构造决策树,先来计算出所有特征的信息增益值:

因为 色泽 脐部 的信息增益值最大,所以从这两个中随机挑选一个,这里选择 脐部 来对数据集进行划分,这会产生三个分支,如下图所示:

但是因为是预剪枝,所以要判断是否应该进行这个划分,判断的标准 就是看划分前后的泛华性能是否有提升,也就是如果划分后泛华性能有提升,则划分;否则,不划分。 下面来看看是否要用 脐部 进行划分, 划分前: 所有样本都在根节点,把该结点标记为叶结点,其类别标记为训练集中样本数量最多的类别,因此标记为 好瓜 ,然后用验证集对其性能评估,可以看出样本{4,5,8}被正确分类,其他被错误分类,因此精度为43.9%。 划分后: 划分后的的决策树为:

则验证集在这颗决策树上的精度为:5/7 = 71.4% > 42.9%。因此,用 脐部 进行划分。
接下来,决策树算法对结点 (2) 进行划分,再次使用信息增益挑选出值最大的那个特征,这里我就不算了,计算方法和上面类似,信息增益值最大的那个特征是“色泽”,则使用“色泽”划分后决策树为:

但到底该不该划分这个结点,还是要用验证集进行计算,可以看到划分后,精度为:4/7=0.571<0.714,因此,预剪枝策略将禁止划分结点 (2) 。对于结点 (3) 最优的属性为“根蒂”,划分后验证集精度仍为71.4%,因此这个划分不能提升验证集精度,所以预剪枝将禁止结点 (3) 划分。对于结点 (4) ,其所含训练样本已属于同一类,所以不再进行划分。
所以基于预剪枝策略生成的最终的决策树为:

总结: 对比未剪枝的决策树和经过预剪枝的决策树可以看出:预剪枝使得决策树的很多分支都没有“展开”,这不仅降低了过拟合的风险,还显著减少了决策树的训练时间开销和测试时间开销。但是,另一方面,因为预剪枝是基于“贪心”的,所以,虽然当前划分不能提升泛华性能,但是基于该划分的后续划分却有可能导致性能提升,因此预剪枝决策树有可能带来欠拟合的风险。

二、后剪枝(post-pruning)
后剪枝就是先构造一颗完整的决策树,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛华性能的提升,则把该子树替换为叶结点。前面已经说过了,使用前面给出的训练集会生成一颗(未剪枝)决策树:

后剪枝算法首先考察上图中的结点 (6),若将以其为根节点的子树删除,即相当于把结点 (6) 替换为叶结点,替换后的叶结点包括编号为{7,15}的训练样本,因此把该叶结点标记为“好瓜”(因为这里正负样本数量相等,所以随便标记一个类别),因此此时的决策树在验证集上的精度为57.1%(为剪枝的决策树为42.9%),所以后剪枝策略决定剪枝,剪枝后的决策树如下图所示:

接着考察结点 5,同样的操作,把以其为根节点的子树替换为叶结点,替换后的叶结点包含编号为{6,7,15}的训练样本,根据“多数原则”把该叶结点标记为“好瓜”,测试的决策树精度认仍为57.1%,所以不进行剪枝。
考察结点 2 ,和上述操作一样,不多说了,叶结点包含编号为{1,2,3,14}的训练样本,标记为“好瓜”,此时决策树在验证集上的精度为71.4%,因此,后剪枝策略决定剪枝。剪枝后的决策树为:

接着考察结点 3 ,同样的操作,剪枝后的决策树在验证集上的精度为71.4%,没有提升,因此不剪枝;对于结点 1 ,剪枝后的决策树的精度为42.9%,精度下降,因此也不剪枝。
因此,基于后剪枝策略生成的最终的决策树如上图所示,其在验证集上的精度为71.4%。

总结: 对比 预剪枝 后剪枝 ,能够发现,后剪枝决策树通常比预剪枝决策树保留了更多的分支,一般情形下,后剪枝决策树的欠拟合风险小,泛华性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的,并且要自底向上的对树中的所有非叶结点进行逐一考察,因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。

参考文献
[1]: 周志华 《机器学习》





决策树 算法和 剪枝 原理 本节我们对决策算法原理做简单的解析,帮助您理清算法思路,温故而知新。 我们知道, 决策树 算法是一种树形分类结构,要通过这棵树实现样本分类,就要根据 if -else 原理设置判别条件。因此您可以这样理解, 决策树 是由许多 if -else 分枝组合而成的树形模型。 决策树 算法原理 决策树 特征属性是 if -else 判别条件的关键所在,我们可以把这些特征属性看成一个集合,我们要选择的判别条件都来自于这个集合,通过分析与计算选择与待分类样本最合适的“判别条件”。通过前面文章的学习,我们可以知
决策树 是一种非参数监督学习算法,用于分类和回归任务。它具有分层的树结构,由根节点、分支、内部节点和叶节点组成。 从上图中可以看出, 决策树 从一个根节点开始,它没有任何传入的分支。然后从根节点传出的分支馈送到内部节点,也称为决策节点。根据可用特征,两种节点类型都进行评估以形成同质子集,这些子集由叶节点或终端节点表示。叶节点代表数据集中所有可能的结果。例如,假设您正在尝试评估是否应该去冲浪,您可以使用以下决策规则来做出选择: 这种类型的流程图结构还创建了一个易于理解的决策表示,允许组织中的不同组更好地 决策树 通过一些 剪枝 方法并测试准确性这是没有实现 剪枝 算法并且只使用交叉验证的原始版本。 有一个文档“背景”描述了数据集的背景。 添加了三个子版本: De cisio n_ Tree _Origin.h、De cisio n_ Tree _Origin.cpp De cisio n_ Tree .h、De cisio n_ Tree .cpp
决策树 (de cisio n tree )是一种基本的分类与回归方法,此处主要讨论分类的 决策树 决策树 学习的算法通常是一个递归地选择最优特征(选择方法的不同,对应着不同的算法),并根据该特征对训练数据进行分割,使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着 决策树 的构建。下面为一个实例图: 构造流程: 1) 开始:构建根节点,将所有训练数据都放在根节点,选择一个最优特征,按着这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。 2) 如果这些子集已经能够被
剪枝 的目的: 剪枝 的目的是为了避免 决策树 模型的过拟合。因为 决策树 算法在学习的过程中为了尽可能的正确的分类训练样本,不停地对结点进行划分,因此这会导致整棵树的分支过多,也就导致了过拟合。 决策树 剪枝 策略最基本的有两种: 剪枝 (pre-pruning)和后 剪枝 (post-pruning): 剪枝 (pre-pruning): 剪枝 就是在构造 决策树 的过程中,先对每个结点在划分前进行估计,若果当前结点的划分不能带来 决策树 模型泛化性能的提升,则不对当前结点进行划分并且将当前结点标记为叶结点。 后 剪枝 (post-pr
快速 决策树 分类器是一种高效的 机器学习 算法,用于处理大规模数据集的分类问题。该分类器通过构建一颗 决策树 来对数据进行分类。它的快速性来自于采用了一些优化技巧。 首先,快速 决策树 分类器使用了一种高效的特征选择方法,即基尼系数。基尼系数可以评估一个特征对数据集的划分能力,选择具有最佳划分能力的特征作为当前节点的划分依据,从而减少了计算量。 其次,快速 决策树 分类器采用了 剪枝 技术,即在构建 决策树 的过程中,对叶节点进行 剪枝 ,去掉那些没有显著提升分类准确度的叶节点。这样可以避免模型的过拟合,减少了 决策树 的复杂度。 此外,快速 决策树 分类器还使用了并行计算技术,可以将数据集划分成多个子集,同时在不同的处理器上进行计算,从而提高了分类器的处理速度。 快速 决策树 分类器的应用非常广泛。它可以用于文本分类、图像分类、数据挖掘等领域。它的优势在于对大规模数据集的处理速度较快,且具有较好的分类准确度。但是,快速 决策树 分类器也有一些限制,例如对噪声数据敏感,对缺失值的处理能力较弱。 总之,快速 决策树 分类器是一种高效的分类算法,通过特征选择、 剪枝 和并行计算等技术优化了分类效率。它在大规模数据集上表现优异,可以广泛应用于各个领域。