模型算法基础——决策树剪枝算法(一)

在决策树生成以后,常常出现过拟合的问题。这是因为如果决策树过于复杂,训练样本的每个属性(变量)都被详细的加以考虑,决策树的每个叶节点所覆盖的样本都是或接近“纯”的。这种情况下,决策树往往对训练样本拟合的很好,但是拟合验证样本时效果却大打折扣。

举一个栗子可以加深对过拟合的理解:在上学的时候,有一些同学准备考试的方法是“背题”,仅仅靠背解题过程却无法掌握其中规律性的的东西,如果题目都押中了这类同学就可以考得很好,但是对于大多数情况他们却以失败告终;还有一些同学,他们擅长在题目中寻找规律,即使题目千变万化他们也能得到高分。模型也是一样,我们更希望它能够体现规律性的东西,而不是训练样本中的细节。

这时,对决策树进行剪枝就成为了一个必不可少的步骤。其实对决策树而言,相对于树的生成过程,剪枝的过程更为重要。今天介绍一种后剪枝算法——误差降低剪枝(Reduced Error Pruning/REP)

误差降低剪枝是最简单粗暴的剪枝方法。首先用训练样本生成决策树后,自下而上对于每个节点决定是否修剪该节点。先假设我们要删除该节点下的子树使其成为叶子节点并赋予训练样本最常见的分类,再用验证样本比较修剪前后的错分率,当修剪后的错分率不比修剪前的高时便真正删除该节点下的子树。

举个栗子,假设有个训练样本产生的决策树长这样(目标变量可分类为1或):

其中T4节点中13和7表示该节点覆盖的样本中目标变量为1和的个数。再假设用这个决策树拟合验证样本后的结果长这样:

自下而上,按照T5、T6、T4的顺序来决定每个节点是否需要被修剪:

在判断T4是否修剪前,T7、T8节点已被删除,T5成为新的叶子节点。可以看到最终T4节点下的全部子树都被删除。

误差降低剪枝使用了和训练样本独立的验证样本,由于验证样本没有参与决策树的生成过程,因此一定程度上可以解决过拟合问题,但也可能会产生过剪枝的问题。

本文来自企鹅号 - 全球大搜罗媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据科学学习手札

(数据科学学习手札23)决策树分类原理详解&Python与R实现

  作为机器学习中可解释性非常好的一种算法,决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的...

3767
来自专栏mantou大数据

[机器学习实战]K-近邻算法

1. K-近邻算法概述(k-Nearest Neighbor,KNN) K-近邻算法采用测量不同的特征值之间的距离方法进行分类。该方法的思路是:如果一个样本在特...

3284
来自专栏李智的专栏

Deep learning基于theano的keras学习笔记(1)-Sequential模型

《统计学习方法》中指出,机器学习的三个要素是模型,策略和优算法,这当然也适用于深度学习,而我个人觉得keras训练也是基于这三个要素的,先建立深度模型,然后选用...

801
来自专栏决胜机器学习

机器学习(十七) ——SVM进一步认识

机器学习(十七)——SVM进一步认识 (原创内容,转载请注明来源,谢谢) 注:这两天边看ng的svm视频,边看机器学习实战的书的svm代码,两边都看的云里雾里...

3058
来自专栏有趣的Python和你

机器学习实战之Logistic回归

953
来自专栏数据结构与算法

09:矩阵乘法

09:矩阵乘法 总时间限制: 1000ms 内存限制: 65536kB描述 计算两个矩阵的乘法。n*m阶的矩阵A乘以m*k阶的矩阵B得到的矩阵C 是n*k阶的...

3815
来自专栏MyBlog

#数值分析读书笔记(4)求非线性方程的数值求解

是否同号, 然后即可知根落在左侧还是右侧, 用这个中点来代替掉原来的端点, 然后得到一个新的区间, 如此反复迭代下去之后, 我们会发现区间收敛到接近一个数

882
来自专栏数值分析与有限元编程

可视化 | MATLAB划分均匀矩形网格

之前发过一个划分均匀三角形网格的例子。下面结合一个悬臂梁说说如何在规则区域划分均匀矩形网格。 ? 将一个矩形平面区域划分成相同大小的矩形。X方向等分nex,Y方...

3969
来自专栏jeremy的技术点滴

机器学习课程_笔记07

3377
来自专栏编程

图像处理基础

作者简介 本文来自鲍骞月的投稿,主要讲解图像处理基础,欢迎大家积极留言,提出你的疑问或者建议,与投稿小伙伴交流。 GitHub地址:https://github...

1886

扫码关注云+社区