首页 > 编程语言 >决策树之——C4.5算法及示例

决策树之——C4.5算法及示例

时间:2024-09-04 15:37:07浏览次数:12  
标签:阈值 示例 增益 构建 子集 C4.5 节点 决策树

0 前言

1 C4.5算法流程

  1. 准备数据集:
    输入数据集包含多个样本,每个样本具有多个特征(属性)和一个目标类别标签。

  2. 设置阈值:
    初始化信息增益的阈值ε,用于决定何时停止树的生长。在决策树的构建过程中,对于每个节点,计算所有特征的信息增益。如果某个特征的信息增益大于或等于阈值ε,则使用该特征进行节点划分;否则,停止划分,并将该节点标记为叶节点。通过设定较高的阈值,可以限制决策树的生长,减少节点的数量,从而避免过拟合。本文并未设置阈值,感兴趣的读者可以自行实验

  3. 选择最优属性:
    从候选属性中选择信息增益率最高的属性作为当前节点的分裂属性。

  4. 分裂数据集:
    根据选定的最优属性的不同取值,将数据集分割成若干个子集。

  5. 递归构建子树:
    对每个子集,重复步骤3~4,直到满足以下任一条件为止:①子集中的所有样本都属于同一类别。②没有更多属性可以用于进一步划分(或剩余属性的信息增益率均低于阈值ε)。

2 例题

  1. 准备数据集:
    见前言西瓜数据集。假设数据集为D。

  2. 设置阈值:
    本文不考虑。

  3. 构建根节点、分割数据集:结果如下图(2-1)所示。
    image
    计算出除编号、好瓜外的其他特征的信息增益比gr(?,?),发现gr(好瓜,纹理)的信息增益比为最大,将特征纹理作为根节点,将数据集D分割成3个子集,子集①:纹理为模糊,子集②:纹理为清晰,子集③:纹理为稍糊。当纹理为模糊时全是坏瓜,故需要设置'否'叶节点,其他情况有好瓜也有坏瓜,故应该继续构建分支。
    若读者规定决策树构建必须有阈值ε,假设阈值ε=0.4000,可以看出已经计算的所有特征的信息增益均小于阈值,根据阈值构建算法,此时D1、D2均应该变成叶节点(叶节点的类别应设置为该分支的子数据集中占比最多的类),读者是否会考虑该树太"简陋"了?所以阈值的设定很大程度上关系到决策树的准确性。

  4. 递归构建图2-1的D1:结果如下图(2-2)所示。
    image
    计算除编号、好瓜、纹理外的其他特征的信息增益比gr(?,?),发现有多个特征信息增益比同等大,默认选择第一个信息增益比最大的特征构建节点,同时分割数据集D1为若干个子集,根据子集数据去设置叶节点或继续构建分支。

  5. 递归构建图2-2的D3:结果如下图(2-3)所示。
    image
    计算出特征色泽、敲声、脐部、触感的信息增益比,选择第一个最大信息增益比的特征色泽构建节点,并分割数据集D3为若干子集,并判断子集需要设置叶节点还是继续构建分支。构建决策树中途会出现某分支没有特定特征的样本,请阅读上图中的文字说明。

  6. 递归构建图2-3的D4:结果如下图(2-4)所示。
    image
    同样计算信息增益比,选择信息增益比最大的特征构建节点,同时分割数据集并构建分支。从上图可以看到已经没有样本继续构建,所以下一步应该构建D2。

  7. 递归构建图2-4的D2:结果如下图(2-5)所示。
    image
    依次按照前文步算法骤,直到构建完成。

3 决策树的改进方法:剪枝

  1. 预剪枝:
    在构建决策树的过程中,通过设定一些规则(如节点最小样本数、最大深度等)来提前停止树的生长,防止过拟合。

  2. 后剪枝:
    在决策树完全生长后,通过剪去一些子树来降低模型的复杂度,提高模型的泛化能力。常用的后剪枝方法包括代价复杂度剪枝(CCP)等。

4 结语

如有错误请指正,禁止商用。

标签:阈值,示例,增益,构建,子集,C4.5,节点,决策树
From: https://www.cnblogs.com/hello-nullptr/p/18396369

相关文章

  • Node.js发票查验接口示例、识别查验接口参数返回
    财务、审计等经常与发票打交道的人员常常会遇到虚假发票、错票、重复报销等一系列问题。对于会计审计、代理记账、电子商务等发票查验量多的企业来说,成千上万张发票如果仅依赖于人工来进行核验,速度慢效率低,准确率也没保障,因此,如何让发票查验工作变得便捷高效,提升发票查验的效......
  • Node.js实名认证接口示例-身份证、银行卡、手机号实名认证
    随着互联网的高速发展,人们可以发表言论的渠道越来越多。网络平台不断汲取各地、各人、各时发表的各种信息。人们喜欢将信息发布到微博、知乎、天涯、豆瓣等等网络平台,逐步的,网络信息进入大爆炸时代。这些大量涌现的信息中难免掺杂着一些不良信息,比如:虚假信息、污言秽语、违法......
  • Node.js发票查验接口示例、识别查验接口参数返回
     财务、审计等经常与发票打交道的人员常常会遇到虚假发票、错票、重复报销等一系列问题。对于会计审计、代理记账、电子商务等发票查验量多的企业来说,成千上万张发票如果仅依赖于人工来进行核验,速度慢效率低,准确率也没保障,因此,如何让发票查验工作变得便捷高效,提升发票查验的......
  • Node.js实名认证接口示例-身份证、银行卡、手机号实名认证
    随着互联网的高速发展,人们可以发表言论的渠道越来越多。网络平台不断汲取各地、各人、各时发表的各种信息。人们喜欢将信息发布到微博、知乎、天涯、豆瓣等等网络平台,逐步的,网络信息进入大爆炸时代。这些大量涌现的信息中难免掺杂着一些不良信息,比如:虚假信息、污言秽语、违......
  • API接口的请求方式及其示例代码​
    API的请求方式主要包括以下几种,这些方式分别对应了HTTP协议中的不同方法,用于实现不同的数据交互需求:GET请求:用途:用于从服务器获取数据。特点:将请求的参数包含在URL中,并以键值对的形式进行传输。由于参数暴露在URL中,因此它适用于获取公开的数据,如天气信息、新闻等。GET请求一般是幂......
  • 决策树之——ID3算法及示例
    0前言本文主要介绍决策树ID3算法,并举出构建示例帮助理解。读者需要具备的知识:信息熵、条件熵、信息增益。本文使用数据集为:游玩数据集1.1节、西瓜数据集1.2节。1ID3算法简述ID3(IterativeDichotomiser3)算法是一种经典的决策树学习算法,由RossQuinlan于1986年提出。该......
  • 字典操作示例
    字典用{}标识,它是一个无序的“键(key):值(value)”对集合。在同一个字典中,键必须是唯一的,但值不必唯一,值可以是任何数据类型,但键必须是不可变的,如字符串,数字,元组首先需要先定义一个字典dict1={'Alice':'123','Beth':'456','Cecil':'abc'}输出123print(dict1['Alice'])增......
  • 列表操作示例
    首先先定义一个列表,列表是写在[]里,用逗号隔开的,元素是可以改变的列表的截取语法结构是:变量[头下标:尾下标]L=['abc',12,3.45,'python',2.789]输出完整列表print(L)输出列表的第一个元素print(L[0])将列表的第一个元素修改为‘a’L[0]='a'将列表的第2个元素到第3个元素......
  • PHP 代码示例 拷贝文件夹目录下的所有子目录及文件到另一个文件夹目录
    PHP 拷贝文件夹目录下的所有子目录及文件到另一个文件夹目录:调用示例:$srcFolder="C:/www/upload/src";$dstFolder="C:/www/upload/dst";$this->recurseCopy($srcFolder,$dstFolder);functionrecurseCopy($src,$dst){$dir=o......
  • flask多线程下数据库操作(简单示例)
    前言背景:开了两个线程操作数据库插入但是获取不到db的信息,自己摸索的方法不一定是最佳的,有更好的可以评论或私信,感谢大佬话不多说,直接上代码 #模型里面的多线程新增操作@staticmethoddefadd_users_by_thread(username,password,session):user=U......