热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

决策树C4.5算法的理解

在上一篇博文中,我们一起学习了决策树中的ID3算法,知道了如何选择决策树分裂的属性。但是我们细心一想,在ID3算法中仍然有几方面的不足&#

在上一篇博文中,我们一起学习了决策树中的ID3算法,知道了如何选择决策树分裂的属性。但是我们细心一想,在ID3算法中仍然有几方面的不足:
1. 在ID3算法当中,选择分裂的属性的时候,依据是信息增益,其实信息增益用作分裂的依据并不如信息增益率(information gain ratio)。
2. ID3算法不能对连续的数据进行处理,只能将连续的数据离散化处理。
3. ID3算法并没有做剪枝处理,导致决策树可能会过于复杂导致过拟合。
所以在这里,我们提出一种基于ID3算法的优化算法—C4.5算法,为了说清楚这个C4.5,我们还是沿用上一篇博文中的股票数据。


今日股票涨跌上证指数涨跌幅明日股票涨跌
+2983+1.2-
-2962-6.6+
+3008+7.0-
-2966-3.2-
+3018+5.7+
-2995-2.2+
+2899+1.7-
-3065-0.6+
+2888+0.2-
-3112-9.3+

首先我们来看看信息增益率的公式吧:


Info_Ratio=Info_GainInstrinsicInfoInfo_Ratio=Info_GainInstrinsicInfo


其中Info_Gain就是我们上一篇博文中给出的公式:



Info_Gain=EntropyiIpiEntropyiInfo_Gain=Entropy−∑i∈Ipi⋅Entropyi


在信息增益的公式中,分母InstrinsicInfo表示分裂子节点数据量的信息增益,也就是分裂节点的熵计算公式如下:



InstrinsicInfo=i=1mniNlog2(niN)InstrinsicInfo=−∑i=1mniN⋅log2(niN)


在这个公式中ni表示子节点的数据量,N表示父节点的数据量。同理,信息增益率越大,表示分裂的效果越好。为了计算说明,我们就不像上一篇博文那样每一种属性都计算一遍了,我们就拿今日股票涨跌来做例子吧。


今日股票涨跌对明日股票的影响

在上一篇博文中我计算了信息增益Info_Gain=0.278,接着我们来计算子节点数据量的信息增益InstrinsicInfo:



InstrinsicInfo=i=1mniNlog2(niN)=(12log212)×2=1InstrinsicInfo=−∑i=1mniN⋅log2(niN)=−(12log212)×2=1


所以以今日股票涨跌作为分裂属性的信息增益率 = Info_Gain/InstrinsicInfo=0.278。

讲到这里,有的朋友就会说,如果我用上证指数这种连续型属性作为分类属性,数据应该怎么处理?这里就涉及到了对连续性属性的处理。我们首先对上证指数进行一个从低到高的排序:


今日股票涨跌上证指数涨跌幅明日股票涨跌
+2888+0.2-
+2899+1.7-
-2962-6.6+
-2966-3.2-
+2983+1.2-
-2995-2.2+
+3008+7.0-
+3018+5.7+
-3065-0.6+
-3112-9.3+

其实在上一篇博文中我以上证指数3000点为界限来作为切割线,也就是在2995和3008之间划分一条切割线来分裂,这种做法其实是不科学的。其实这10组数据就会有9条可能的分割线来为决策树做分裂,我们最科学的方法是计算每一种分裂方法的信息增益率,然后取最大的一条分割线。如图所示:
分割线1
不好意思,画的时候手有点抖,凑合看一下。这样划分的话,其实计算量很大的,我们想个办法来优化一下,如图所示:分割线2
我们来看图中第一行和第二行中明日股票的涨跌都是跌,可以把这看做一类,不必在这两组数据之间做分割,如果强行把这两组在一类的数据分割,那么效果肯定不如把他们归为一类。所以同理,我们可以得到图中的分割线,这样本来有9条分割线降低到了5条,这样可以降低了计算的复杂度。

说完了上面的这些,我们再来说一下剪枝,剪枝其实就是在完全生长的决策树基础上,对分类不理想的子树做修剪,从而降低决策树的复杂度,防止决策树的过拟合,让决策树达到一个理想的状态。决策树的剪枝可以分成两类,一类是先剪枝一类是后剪枝,先剪枝的意思是提前结束决策树的生长,后剪枝的意思是在决策树构造完毕之后再进行剪枝操作。在C4.5算法中采用的是悲观剪枝法(PEP),就是说如果决策树的精度在剪枝之后没有降低的话,那么就进行剪枝操作。这里有朋友就要提出问题了,什么样叫决策树的精度没有降低?我们用数学的角度来看看,这里有判决是否进行剪枝操作的数学公式:


EleafEsubtree+S(Esubtree)Eleaf⩽Esubtree+S(Esubtree)


在这个公式中Eleaf表示子节点的误差,Esubtree表示子树的误差。可以把子树的误差精度理解成满足二项分布,所以根据二项分布特性:



Esubtree=i=1m(ei+0.5),S(Esubtree)=np(1p),p=EsubtreeNEsubtree=∑i=1m(ei+0.5),S(Esubtree)=np(1−p),p=EsubtreeN


其中N是子树的数据量。在上述公式中,0.5表示的是修正因子,因为对父节点的分裂总会得到比父节点分类结果更好的效果,所以子节点的误差会大于父节点的误差,为了让父节点的误差不小于子节点的误差,所以要加上一个修正因子。我们来举一个例子:


决策树例子

我们可以计算得到:



Esubtree=i=1m(ei+0.5)=(2+0.5)+(1+0.5)+(1+0.5)=5.5Esubtree=∑i=1m(ei+0.5)=(2+0.5)+(1+0.5)+(1+0.5)=5.5




S(Esubtree)=np(1p)=5.5(15.515)=1.866S(Esubtree)=np(1−p)=5.5(1−5.515)=1.866




Eleaf=e+0.5=6+0.5=6.5Eleaf=e+0.5=6+0.5=6.5


所以满足公式:



Eleaf<Esubtree&#43;S(Esubtree)Eleaf


所以对于上述决策树来说&#xff0c;应该进行剪枝操作。这就是我们的C4.5决策树&#xff0c;希望对您有所帮助&#xff0c;本人能力有限&#xff0c;如有纰漏请轻喷&#xff0c;不吝指教。如有转载&#xff0c;请标明出处&#xff0c;谢谢。


推荐阅读
  • 在机器学习领域,深入探讨了概率论与数理统计的基础知识,特别是这些理论在数据挖掘中的应用。文章重点分析了偏差(Bias)与方差(Variance)之间的平衡问题,强调了方差反映了不同训练模型之间的差异,例如在K折交叉验证中,不同模型之间的性能差异显著。此外,还讨论了如何通过优化模型选择和参数调整来有效控制这一平衡,以提高模型的泛化能力。 ... [详细]
  • 本文详细介绍了在 CentOS 7 系统中配置 fstab 文件以实现开机自动挂载 NFS 共享目录的方法,并解决了常见的配置失败问题。 ... [详细]
  • 本文介绍了几种常用的图像相似度对比方法,包括直方图方法、图像模板匹配、PSNR峰值信噪比、SSIM结构相似性和感知哈希算法。每种方法都有其优缺点,适用于不同的应用场景。 ... [详细]
  • com.sun.javadoc.PackageDoc.exceptions()方法的使用及代码示例 ... [详细]
  • Ihavetwomethodsofgeneratingmdistinctrandomnumbersintherange[0..n-1]我有两种方法在范围[0.n-1]中生 ... [详细]
  • 本文详细介绍了 PHP 中对象的生命周期、内存管理和魔术方法的使用,包括对象的自动销毁、析构函数的作用以及各种魔术方法的具体应用场景。 ... [详细]
  • 本文讨论了在进行 MySQL 数据迁移过程中遇到的所有 .frm 文件报错的问题,并提供了详细的解决方案和建议。 ... [详细]
  • 本文将详细介绍如何在Mac上安装Jupyter Notebook,并提供一些常见的问题解决方法。通过这些步骤,您将能够顺利地在Mac上运行Jupyter Notebook。 ... [详细]
  • 题目《BZOJ2654: Tree》的时间限制为30秒,内存限制为512MB。该问题通过结合二分查找和Kruskal算法,提供了一种高效的优化解决方案。具体而言,利用二分查找缩小解的范围,再通过Kruskal算法构建最小生成树,从而在复杂度上实现了显著的优化。此方法不仅提高了算法的效率,还确保了在大规模数据集上的稳定性能。 ... [详细]
  • 在C#编程中,数值结果的格式化展示是提高代码可读性和用户体验的重要手段。本文探讨了多种格式化方法和技巧,如使用格式说明符、自定义格式字符串等,以实现对数值结果的精确控制。通过实例演示,展示了如何灵活运用这些技术来满足不同的展示需求。 ... [详细]
  • 在对WordPress Duplicator插件0.4.4版本的安全评估中,发现其存在跨站脚本(XSS)攻击漏洞。此漏洞可能被利用进行恶意操作,建议用户及时更新至最新版本以确保系统安全。测试方法仅限于安全研究和教学目的,使用时需自行承担风险。漏洞编号:HTB23162。 ... [详细]
  • 如何使用 `org.apache.poi.openxml4j.opc.PackagePart` 类中的 `loadRelationships()` 方法及其代码示例详解 ... [详细]
  • 本文详细解析了使用C++实现的键盘输入记录程序的源代码,该程序在Windows应用程序开发中具有很高的实用价值。键盘记录功能不仅在远程控制软件中广泛应用,还为开发者提供了强大的调试和监控工具。通过具体实例,本文深入探讨了C++键盘记录程序的设计与实现,适合需要相关技术的开发者参考。 ... [详细]
  • 本文介绍了如何利用Shell脚本高效地部署MHA(MySQL High Availability)高可用集群。通过详细的脚本编写和配置示例,展示了自动化部署过程中的关键步骤和注意事项。该方法不仅简化了集群的部署流程,还提高了系统的稳定性和可用性。 ... [详细]
  • 在配置Nginx的SSL证书后,虽然HTTPS访问能够正常工作,但HTTP请求却会遇到400错误。本文详细解析了这一问题,并提供了Nginx配置的具体示例。此外,还深入探讨了DNS服务器证书、SSL证书的申请与安装流程,以及域名注册、查询方法和CDN加速技术的应用,帮助读者全面了解相关技术细节。 ... [详细]
author-avatar
mobiledu2502858037
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有