决策树模型(3)决策树的生成与剪枝

这篇具有很好参考价值的文章主要介绍了决策树模型(3)决策树的生成与剪枝。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

决策树的生成

有了信息增益和信息增益比,我就可以以此衡量特征的相对好坏,进而可以用于决策树的生成。相对应的基于信息增益计算的方法所生成的决策树的算法我们叫做ID3算法,而基于信息增益的算法我们叫做C4.5,二者唯一的区别就在于一个使用信息增益衡量特征好坏而另外一个使用信息增益比,因此本文重点讲述ID3算法。

ID3算法

  1. 特殊情况判断
    • 如果数据集中所有的样本均属于同一类\(C_k\),那么直接将\(C_k\)作为该结点的类别标记,并返回决策树\(T\)
    • 如果此时特征集合\(A=\varnothing\)为空,那么将\(D\)中相同类别数最多样本的类别作为该结点的类别标记并返回\(T\)
  2. 若没有出现上述特殊情况,则计算\(A\)中各特征的信息增益\(g(D, A_i)\),并选择信息增益最大的特征\(A_g\)
  3. \(A_g\)的信息增益小于阈值\(\epsilon\),那么同样的,将\(D\)中相同类别数最多的样本的类别作为该结点的类别标记并返回\(T\)
  4. 否则使用\(A_g=a_i\)再次将训练集分割为若干非空子集\(D_i\),其中\(a_i\)是特征\(A_g\)的每个可能取值,然后对每一个\(D_i\)以其实例数最大的类作为标记构建子节点。
  5. 对第\(i\)个子结点以\(D_i\)为训练集,特征集合\(A=A - {A_g}\)为特征集,递归调用\((1)-(5)\)

下面是更形象化的图示:
决策树模型(3)决策树的生成与剪枝

决策树的剪枝

为了减少决策树的复杂度,并降低过拟合,对决策树进行剪枝是十分有必要的。

代价复杂度剪枝

设决策树\(T\)的叶子结点个数为\(|T|\),叶子结点表示为\(t\)\(N_t\)表示\(t\)上的所有样本点,\(N_{tk}\)表示第\(k\)类的样本点,\(H_t(T)\)表示叶子节点\(t\)上的经验熵(损失)。

\[H_t(T) = -\sum_{k=1}^K\frac{N_{tk}}{|N_{t}|}\mathrm{log}\frac{N_{tk}}{|N_{t}|} \]

那么决策树的损失函数可以定义为

\[C_\alpha(T)=\sum_{t=1}^{|T|}\frac{|N_t|}{|N|}H_t(T)+\alpha |T| \]

前一项表示模型对训练数据的预测误差。

算法

对每个叶子节点的父节点进行剪枝,设剪枝前树的损失为\(T_\alpha(T_A)\),为剪枝的为\(T_\alpha(T_B)\),若满足

\[T_\alpha(T_A) <= T_\alpha(T_B) \]

则表明需要进行剪枝,此过程持续进行,直到无法再继续剪枝。文章来源地址https://www.toymoban.com/news/detail-844001.html

到了这里,关于决策树模型(3)决策树的生成与剪枝的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数学建模--决策树的预测模型的Python实现

    目录 1.算法流程简介 2.算法核心代码 3.算法效果展示

    2024年02月08日
    浏览(52)
  • 机器学习(三)决策树对连续值数据的预剪枝及后剪枝(Python代码)

    参考: https://blog.csdn.net/ylhlly/article/details/93213633 https://zhuanlan.zhihu.com/p/267368825 为什么要进行剪枝? 当我们的数据集 样本量很大 、 每个特征的取值很多 时,生成决策树的 代价 就会 很大 。不仅如此,虽然一个完整的决策树对训练数据的预测非常准,但这会造成 对训练数据

    2023年04月22日
    浏览(39)
  • sklearn中决策树模块的剪枝参数ccp_alpha如何可视化调整

    决策树作为树模型中最经典的算法,根据训练数据生长并分裂叶子结点,容易过拟合。所以一般来说会考虑生长停止后进行剪枝,把一些不必要的叶子结点去掉(让其父结点作为叶子结点),这样或许对其泛化能力有积极作用。 在scikit-learn的决策树模块里,默认是不剪枝的,

    2024年02月21日
    浏览(44)
  • python机器学习(六)决策树(上) 构造树、信息熵的分类和度量、信息增益、CART算法、剪枝

    模拟相亲的过程,通过相亲决策图,男的去相亲,会先选择性别为女的,然后依次根据年龄、长相、收入、职业等信息对相亲的另一方有所了解。 通过决策图可以发现,生活中面临各种各样的选择,基于我们的经验和自身需求进行一些筛选,把判断背后的逻辑整理成结构图,

    2024年02月14日
    浏览(49)
  • 回归决策树的介绍

    一、回归决策树的介绍 1.什么是回归决策树 回归决策树(Regression Decision Tree)是一种决策树算法,用于解决回归问题。 与传统的分类决策树不同,回归决策树的目标是预测连续数值型的输出,而不是离散的类别标签 。 2.原理概述 数据集准备: 首先,需要准备训练数据集,

    2024年02月17日
    浏览(36)
  • 决策树的分类

    决策树是一种树形结构 树中每个内部节点表示一个特征上的判断,每个分支代表一个判断结果的输出,每个叶子节点代表一种分类结果 决策树的建立过程 1.特征选择:选取有较强分类能力的特征。 2.决策树生成:根据选择的特征生成决策树。 3. 决策树也易过拟合,采用剪枝

    2024年01月18日
    浏览(60)
  • 决策树的优缺点

    决策树优点 1. 易于理解和解释,因为树木可以画出来被看见 2. 需要很少的数据准备。其他很多算法通常都需要数据规范化,需要创建虚拟变量并删除空值等。但请注意, sklearn中的决策树模块不支持对缺失值的处理。 3. 使用树的成本(比如说,在预测数据的时候)是用于训

    2024年02月06日
    浏览(64)
  • 决策树的原理及其实现

    目录 一、决策树简介 二、决策树的基本流程 三. 划分选择,寻找最优划分属性 (一)、信息增益 (二)、信息增益率 (三) 、基尼指数 四、剪枝处理 五、决策树实现 (一)基于sklearn的代码实现  (二)基于Python实现  实例:基于CART算法,实现预测贷款用户是否具有偿还贷款的

    2024年04月22日
    浏览(24)
  • 决策树的多类别分类

    决策树是一种常用的机器学习算法,它通过构建一棵树来对数据进行分类和预测。在这篇文章中,我们将深入探讨决策树在多类别分类任务中的应用,以及其核心概念、算法原理和实现细节。 决策树算法的主要优点包括易于理解、可视化、无需特征预处理等。然而,决策树也

    2024年03月22日
    浏览(56)
  • 机器学习 -决策树的案例

    我们对决策树的基本概念和算法其实已经有过了解,那我们如何利用决策树解决问题呢? 数据准备 我们准备了一些数据如下: 这些数据分别是天气,是否闷热,风速和是否出门郊游。 现在要解决的问题是“基于当前的天气和其他条件,我们是否应该进行户外活动? 构建决

    2024年02月01日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包