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

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

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

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

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

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

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

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人人都是极客

Peter教你谈情说AI | 09决策树(下)—既能回归又能分类的模型

我们提取七个特征,用来判断一个形象,是人是猫。这七个特征包括:有否蝴蝶结;是否穿衣服;是否高过5个苹果;是否有胡子;是否圆脸;是否有猫耳朵;是否两脚走路。

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

Jacobi方法求矩阵特征值的算例及代码

Jacobi方法用于求实对称阵的全部特征值、特征向量。对于实对称阵 A,必有正交阵 Q ,使 QT A Q = Λ 其中Λ是对角阵,其主对角线元素λii是A的特...

2294
来自专栏小小挖掘机

DQN三大改进(三)-Dueling Network

论文地址:https://arxiv.org/pdf/1511.06581.pdf 代码地址:https://github.com/princewen/tens...

1K6
来自专栏杂七杂八

numpy中的乘法(*,dot)

numpy中数据表示有数组和矩阵两种数据类型,他们的乘法计算也是多种形式,下面我们主要来说一下numpy中的乘法计算 numpy.ndarray 运算符 ...

2636
来自专栏人工智能LeadAI

机器学习实战 | 第四章:模型验证和选择

模型选择和评估主要是在sklearn.model_selection这个模块里面.这里只会列出概述和常见函数的用法,更加详细的可以到sklearn.model_...

3075

用Python的长短期记忆神经网络进行时间序列预测

长短期记忆递归神经网络具有学习长的观察序列的潜力。

1.8K8
来自专栏Brian

深入浅出Logistic Regression之二分类

---- 概述 在深度学习笔记-神经网络基础文章里面介绍过Logistic Regression模型进行二分类和推导。比如:我们现在有一张彩色图片让计算机自己识...

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

广义雅可比方法

标准雅可比方法只能求解标准特征值问题。对于广义特征值问题需要采用广义雅可比方法求解。 前面已提到标准Jacobi方法的理论依据是对于实对称阵 A,必有正交阵 ...

2805
来自专栏文武兼修ing——机器学习与IC设计

关于蘑菇数据集的探索分析数据集描述读取数据集直观分析——颜色鲜艳的蘑菇都有毒?相关性分析——判断各指标与毒性相关性模型训练——使用决策树模型

数据集描述 来源于kaggle的蘑菇数据集,包括毒性,大小,表面,颜色等,所有数据均为字符串类型,分析毒性与其他属性的关系 读取数据集 dataset = pd...

3546
来自专栏李蔚蓬的专栏

第14周Python机器学习周记

(2)新增一个键值(maybe),计算香农熵,观察其变化(熵越高,则混合的数据也越多);

733

扫码关注云+社区