当前位置: 首页 > news >正文

【机器学习】机器学习的基本分类-监督学习-决策树-C4.5 算法

C4.5 是由 Ross Quinlan 提出的决策树算法,是对 ID3 算法的改进版本。它在 ID3 的基础上,解决了以下问题:

  1. 处理连续型数据:支持连续型特征,能够通过划分点将连续特征离散化。
  2. 处理缺失值:能够在特征值缺失的情况下继续构建决策树。
  3. 偏好多值特征的问题:采用信息增益比(Gain Ratio)替代信息增益,减少对多值特征的偏好。
  4. 生成剪枝后的树:通过后剪枝技术,降低过拟合风险。

1. 核心改进

(1) 信息增益比

C4.5 使用**信息增益比(Gain Ratio)**代替 ID3 的信息增益来选择最优特征。

  • 信息增益 IG(D, A):

IG(D, A) = H(D) - H(D|A)

  • 分裂信息 SI(A):

SI(A) = -\sum_{v \in \text{Values}(A)} \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|}

其中:

  • |D_v|/|D|:特征 AAA 的第 vvv 个取值的样本比例。

  • 信息增益比 GR(D, A):

GR(D, A) = \frac{IG(D, A)}{SI(A)}

分裂信息 SI(A) 是一种归一化因子,用于惩罚取值较多的特征,降低它们被优先选择的可能性。


(2) 连续型特征处理
  • 对连续特征,C4.5 会尝试在特征值的每个分割点(例如两个样本值之间的中点)进行划分。
  • 对每个划分点计算信息增益比,选择最佳划分点。

假设某连续特征 A 的值为 \{v_1, v_2, \dots, v_n\},排序后尝试以下划分点:

划分点 = \frac{v_i + v_{i+1}}{2}, \quad i = 1, 2, \dots, n-1


(3) 处理缺失值

对于缺失值,C4.5 使用以下策略:

  1. 在计算信息增益比时,只考虑特征值非缺失的样本。
  2. 当需要划分含有缺失值的样本时,将这些样本按概率分配到各个子节点。

(4) 剪枝
  • C4.5 采用**后剪枝(Post-Pruning)**技术,通过校验数据集评估剪枝后的树是否提高性能。
  • 剪枝的目标是降低过拟合风险,增强模型泛化能力。

2. C4.5 算法流程

  1. 输入:训练数据集 D、特征集 A。
  2. 递归构造树
    1. 计算当前数据集 D 的信息熵 H(D)。
    2. 对每个特征 A ∈ A:
      • 若 A 为离散特征,计算信息增益比。
      • 若 A 为连续特征,尝试每个划分点,计算信息增益比。
    3. 选择信息增益比最大的特征 A^*,作为当前节点的分裂特征。
    4. 根据 A^* 的取值(或划分点)划分数据集 D。
    5. 对每个子数据集递归构造子树。
  3. 剪枝
    • 基于校验集对生成的决策树进行剪枝,移除不显著的分支。
  4. 输出:剪枝后的决策树。

3. 示例

数据示例

假设有以下训练数据集:

天气温度湿度风力是否运动
晴天30
晴天32
阴天28
雨天24正常
雨天20正常

目标:构造决策树判断是否运动。

步骤
  1. 计算根节点的熵

    H(D) = -\frac{3}{5} \log_2 \frac{3}{5} - \frac{2}{5} \log_2 \frac{2}{5} \approx 0.971
  2. 对每个特征计算信息增益比

    • 天气(离散特征)

      • 计算天气的条件熵 H(D|\text{Weather})
      • 计算信息增益比 GR(D, \text{Weather})
    • 温度(连续特征)

      • 尝试划分点:272727、303030、333333。
      • 对每个划分点计算信息增益比,选择最佳划分点。
    • 湿度、风力

      • 按相同方法计算。
  3. 选择信息增益比最大的特征作为分裂特征,生成子节点。

  4. 对子节点递归分裂,直至满足停止条件(如样本类别纯度高或无特征可分)。

  5. 后剪枝

    • 对生成的树在校验集上进行性能评估,剪去对性能贡献较小的分支。

4. 算法特点

优点
  1. 支持离散和连续特征,适用范围更广。
  2. 减少对多值特征的偏好,提高选择的公平性。
  3. 能处理缺失值,增强算法的鲁棒性。
  4. 剪枝减少过拟合,提高泛化能力。
缺点
  1. 计算复杂度高,特别是连续特征的划分点尝试增加了计算量。
  2. 不支持大规模数据时的并行化。
  3. 剪枝过程可能需要额外的校验集。

5. 代码实现

以下是一个简单的 Python 实现,用于计算信息增益比并构造 C4.5 决策树:

import numpy as np# 计算熵
def entropy(labels):total = len(labels)counts = {}for label in labels:counts[label] = counts.get(label, 0) + 1return -sum((count / total) * np.log2(count / total) for count in counts.values())# 计算信息增益比
def information_gain_ratio(data, labels, feature_index):total_entropy = entropy(labels)feature_values = [row[feature_index] for row in data]unique_values = set(feature_values)split_info = 0conditional_entropy = 0for value in unique_values:subset = [labels[i] for i in range(len(data)) if data[i][feature_index] == value]proportion = len(subset) / len(data)conditional_entropy += proportion * entropy(subset)split_info -= proportion * np.log2(proportion)info_gain = total_entropy - conditional_entropyreturn info_gain / split_info if split_info != 0 else 0# 示例数据
data = [["晴天", 30, "高", "弱"],["晴天", 32, "高", "强"],["阴天", 28, "高", "弱"],["雨天", 24, "正常", "弱"],["雨天", 20, "正常", "强"]
]
labels = ["否", "否", "是", "是", "否"]# 特征索引(天气、温度、湿度、风力)
for i in range(4):print(f"Feature {i}, Gain Ratio: {information_gain_ratio(data, labels, i):.4f}")

输出结果 

Feature 0, Gain Ratio: 0.3751
Feature 1, Gain Ratio: 0.4182
Feature 2, Gain Ratio: 0.0206
Feature 3, Gain Ratio: 0.4325

6. 总结

C4.5 是 ID3 的改进版本,针对实际问题的需求(连续特征、缺失值、多值特征偏好等)做了多项优化。尽管计算复杂度高,但其广泛用于分类问题,成为现代决策树算法的基础之一(如 CART)。

相关文章:

【机器学习】机器学习的基本分类-监督学习-决策树-C4.5 算法

C4.5 是由 Ross Quinlan 提出的决策树算法,是对 ID3 算法的改进版本。它在 ID3 的基础上,解决了以下问题: 处理连续型数据:支持连续型特征,能够通过划分点将连续特征离散化。处理缺失值:能够在特征值缺失的…...

代码随想录第36天

01背包问题 二维 def hanshu():wupin, bagweight [int(x) for x in input().split()]weight [int(x) for x in input().split()]value [int(x) for x in input().split()]dp [[0]*(bagweight1) for i in range(wupin)] #dp[i][j]代表从物品【0,i-1】让任意取&#xff0c…...

折叠屏手机拐点:三星领跌,华为小米逆势增长

科技新知 原创作者丨依蔓 编辑丨蕨影 折叠屏手机不香了?显示器出货量罕见下滑,并预计 2025 年仍将持续下降。 近日,市场调查机构 DSCC报告称, 2019 年至 2023 年,折叠屏市场曾保持每年至少 40% 的高速增长。然而&…...

微服务的负载均衡可以通过哪些组件实现

微服务的负载均衡可以通过多种组件来实现,以下是一些常见的负载均衡组件及其特点: Nginx: Nginx是一款轻量级的HTTP和反向代理服务器,也是一个高性能的负载均衡器。它支持多种负载均衡算法,如轮询、加权轮询、IP哈希等…...

uni-app写的微信小程序如何实现账号密码登录后获取token,并且每天的第一次登录后都会直接获取参数而不是耀重新登录(2)

接uni-app写的微信小程序如何实现账号密码登录后获取token,并且每天的第一次登录后都会直接获取参数而不是耀重新登录(1), 在main.js中 import App from ./App// #ifndef VUE3 import Vue from vue import ./uni.promisify.adap…...

算法妙妙屋-------1.递归的深邃回响:全排列的奇妙组合

全排列的简要总结 全排列(Permutation)是数学中一个经典的问题,指的是从一组元素中,将所有元素按任意顺序排列形成的所有可能序列。 特点 输入条件: 给定一组互异的元素(通常为数组或字符串)。…...

flink-connector-mysql-cdc:02 mysql-cdc高级扩展

flink-connector-mysql-cdc:01 mysql-cdc基础配置代码演示02 mysql-cdc高级扩展03 mysql-cdc常见问题汇总04 mysql-cdc-kafka生产级代码分享05 flink-kafka-doris生产级代码分享06 flink-kafka-hudi生产级代码分享 flink-cdc版本:3.2.0flink版本&#xf…...

四、自然语言处理_02RNN基础知识笔记

1、RNN的定义 RNN(Recurrent Neural Network,循环神经网络)是一种专门用于处理序列数据的神经网络架构,它与传统的前馈神经网络(Feedforward Neural Network)不同,主要区别在于它能够处理输入数…...

《船舶物资与市场》是什么级别的期刊?是正规期刊吗?能评职称吗?

问题解答 问:《船舶物资与市场》是不是核心期刊? 答:不是,是知网收录的正规学术期刊。 问:《船舶物资与市场》级别? 答:国家级。主管单位:中国船舶集团有限公司 主办单…...

【工具变量】上市公司企业所在地城市等级直辖市、副省级城市、省会城市 计划单列市(2005-2022年)

一、包含指标: 股票代码 股票代码 股票简称 年份 所属城市 直辖市:企业所在地是否属于直辖市。1是,0否。 副省级城市:企业所在地是否属于副省级城市。1是,0否。 省会城市&a…...

websocket通信

“WebSocket 允许客户端和服务器在连接建立后随时互相发送数据,而无需每次交互都重新建立连接。”我想请问,第一次前端往后端发送数据时,传递的数据应该满足接口的参数内容,在第一次建立连接后之后的数据传递还是要满足接口的参数…...

数据结构——单调队列

这篇博客我们来讨论一下单调队列的问题,其实和之前学的单调栈都是一种上通过改变操作来解决问题的一种数据结构 我们先来回忆一下单调栈的内容,这样方便将其和单调队列做区分 单调栈:(单调性从栈底到栈顶) 1.单调栈是一种栈数据…...

qt环境 C11thread子线程关闭定时器问题

环境情况:使用的是thread c11线程和qt的定时器 报错: QObject::~QObject: Timers cannot be stopped from another thread 主要原因: 1.开启了一个事件循环线程处理消息类型,但是有一种消息类型需要关闭资源,这就导…...

深入浅出:虚拟化技术及其在现代 IT 中的应用

文章目录 虚拟化的定义与基本原理虚拟机监控程序(Hypervisor) 虚拟化的历史与发展虚拟化的实现方式虚拟化的优势1. 提高资源利用率2. 降低成本3. 提升灵活性和可扩展性4. 加快应用部署和迁移5. 提高安全性和隔离性 不同类型虚拟化技术服务器虚拟化实际应…...

Golang内存模型总结1(mspan、mcache、mcentral、mheap)

1.内存模型 1.1 操作系统存储模型 从上到下分别是寄存器、高速缓存、内存、磁盘,其中越往上速度越快,空间越小,价格越高。 关键词是多级模型和动态切换 1.2 虚拟内存与物理内存 虚拟内存是一种内存管理技术,允许计算机使用比…...

优先算法 —— 滑动窗口系列 - 无重复字符的最长子串

目录 前言 1. 无重复字符的最长子串 2. 题目解析 3. 算法原理 解法1:暴力枚举 哈希表(判断字符是否有重复出现) 解法2:滑动窗口 4. 代码 前言 当我们发现暴力解法两个指针都不回退,都是向同一个方向移动的时候我…...

Python 浏览器自动化新利器:DrissionPage,让网页操作更简单!

Python 浏览器自动化新利器:DrissionPage,让网页操作更简单! 文章目录 Python 浏览器自动化新利器:DrissionPage,让网页操作更简单!🚀 引言🌟 DrissionPage简介🛠️ 三大…...

[Python] 进阶之路:模块、包和异常处理

在掌握了Python的类与对象后,下一步是深入理解模块化开发和异常处理。模块与包帮助我们组织代码,增强代码的可维护性和重用性,而异常处理则是编写健壮代码的重要技能。本文将系统讲解Python中模块、包和异常处理的核心概念与实用技巧。 一、模…...

SpringBoot 整合 Avro 与 Kafka 详解

SpringBoot 整合 Avro 与 Kafka 详解 在大数据处理和实时数据流场景中,Apache Kafka 和 Apache Avro 是两个非常重要的工具。Kafka 作为一个分布式流处理平台,能够高效地处理大量数据,而 Avro 则是一个用于序列化数据的紧凑、快速的二进制数…...

windows C#-使用 Override 和 New 关键字(上)

在 C# 中,派生类中的方法可具有与基类中的方法相同的名称。 可使用 new 和 override 关键字指定方法的交互方式。 override 修饰符用于扩展基类 virtual 方法,而 new 修饰符用于隐藏可访问的基类方法 。 在控制台应用程序中,声明以下两个类…...

FaRM译文

No compromises: distributed transactions with consistency, availability, and performance Aleksandar Dragojevic, Dushyanth Narayanan, Edmund B. Nightingale, Matthew Renzelmann, Alex Shamis, Anirudh Badam, Miguel Castro Microsoft Research 摘要 具有强一致…...

大数据新视界 -- Hive 元数据管理:核心元数据的深度解析(上)(27 / 30)

💖💖💖亲爱的朋友们,热烈欢迎你们来到 青云交的博客!能与你们在此邂逅,我满心欢喜,深感无比荣幸。在这个瞬息万变的时代,我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...

大数据项目-Django基于聚类算法实现的房屋售房数据分析及可视化系统

《[含文档PPT源码等]精品Django基于聚类算法实现的房屋售房数据分析及可视化系统》该项目含有源码、文档、PPT、配套开发软件、软件安装教程课程答疑等! 数据库管理工具:phpstudy/Navicat或者phpstudy/sqlyog 后台管理系统涉及技术: 后台使…...

当大的div中有六个小的div,上面三个下面三个,当外层div高变大的时候我希望里面的小的div的高也变大

问: 当大的div中有六个小的div,上面三个下面三个,当外层div高变大的时候我希望里面的小的div的高也变大 回答: 这时候我们就不能写死六个小的div的高度,否则上下的小的div的间距就会变大,因为他们的高度…...

使用 Postman 上传二进制类型的图片到后端接口写法

我们有的时候会有需求,就是通过 postman 传递二进制图片到后端接口,如下图: 那我们的 Java 接口需要怎么写呢? Spring Boot 接收这些数据的方式需要使用 RequestBody 注解来处理原始的二进制数据(byte[])。…...

字符串函数和内存函数

字符串函数 1、strlcpy 【字符串拷贝】 (将原字符串中的字符拷贝到目标字符数组中,包括终止符号\0,并在这里停止;为了避免越界,目标字符串数组应该足够大去接收)👆 (返回值是 dest…...

uC/OSII学习笔记(一)任务的增删改查

使用天玛智控的控制器,基础工程文件已移植ucosii。 正常的任务创建流程为: 1.OSInit(); 2.OSTaskCreate(); 3.OSStart(); 但是天玛对其有做修改,任务创建直接调用OSTaskCreate()函数即可,不用在…...

如何搭建JMeter分布式集群环境来进行性能测试

在性能测试中,当面对海量用户请求的压力测试时,单机模式的JMeter往往力不从心。如何通过分布式集群环境,充分发挥JMeter的性能测试能力?这正是许多测试工程师在面临高并发、海量数据时最关注的问题。那么,如何轻松搭建…...

蓝桥杯准备训练(lesson2 ,c++)

3.1 字符型 char //character的缩写在键盘上可以敲出各种字符,如: a , q , , # 等,这些符号都被称为字符,字符是⽤单引号括 起来的,如: ‘a’ , ‘b’ &…...

【踩坑】Collectors.toMap 抛出 NullPointerException 异常

1. 场景重现 public class Test01 {public static void main(String[] args) {List<Person> list Arrays.asList(new Person("anna", 17, 0), new Person("bob", 18, 1), new Person("jack", 20, null));Map<String, Integer> nam…...

泷羽sec专题课笔记-- Linux作业--开机自启动方法以及破解

本笔记为 泷羽sec 《红队全栈课程》学习笔记&#xff0c;课程请可自行前往B站学习&#xff0c;课程/笔记主要涉及网络安全相关知识、系统以及工具的介绍等&#xff0c;请使用该课程、本笔记以及课程和笔记中提及工具的读者&#xff0c;遵守网络安全相关法律法规&#xff0c;切勿…...

OpenCV

MFC&#xff08;C&#xff09;的使用 1、官网下载 https://opencv.org/ 选 Library - Release - 选择你需要的版本 2、安装 3、配置环境变量 将 OpenCV 的bin目录 C:\Program Files\OpenCV481\opencv\build\bin添加到系统的PATH环境变量中。这使得在运行程序时能够找到 Open…...

Wwise 使用MIDI文件、采样音频

第一种&#xff1a;当采样音频只有一个文件的时候 1.拖入MIDI文件到Interactive Music Hierarchy层级 2.拖入采样音频到Actor-Mixer Hierarchy层级 3.勾选MIDI显示出面板&#xff0c;设置Root Note与采样音频音高相同&#xff0c;这里是C#5 4.播放测试&#xff0c;成功&…...

OpenStack-Glance组件

Glance Glance使用磁盘格式和容器格式基础配置镜像转换 Glance 是 OpenStack 的镜像服务&#xff0c;负责存储、发现和管理虚拟机镜像。它允许用户创建和共享镜像&#xff0c;用于启动虚拟机实例。 Glance 的主要功能 &#xff08;1&#xff09;虚拟机镜像的管理 支持镜像的上…...

写译热点单词 | 50篇文章整理 | 手敲自用

目录 文化类 政治类 经济类 教育类 科技类 健康类 安全类 体育类 第二版 删去了部分不太常用的 文化类 1. 阴历: lunar calendar 2. 阳历: solar calendar 3. 春节: the Spring Festival 4. 除夕: Chinese New Year’s Eve 5. 清明节: Tomb Sweeping Day 6. 重阳…...

【UE5 C++】判断两点连线是否穿过球体

目录 前言 方法一 原理 代码 测试 结果 方法二 原理 一、检查连线与球体的相交情况 二、检查距离与球体半径的关系 三、检查连线与球体的相交 代码 前言 通过数学原理判断空间中任意两点的连线是否穿过球体&#xff0c;再通过射线检测检验算法的正确性。 方法一 …...

A1228 php+Mysql旅游供需平台的设计与实现 导游接单 旅游订单 旅游分享网站 thinkphp框架 源码 配置 文档 全套资料

旅游供需平台 1.项目描述2. 开发背景与意义3.项目功能4.界面展示5.源码获取 1.项目描述 随着社会经济的快速发展&#xff0c;生活水平的提高&#xff0c;人们对旅游的需求日益增强&#xff0c;因此&#xff0c;为给用户提供一个便利的查看导游信息&#xff0c;进行导游招募的平…...

【linux】服务器Ubuntu20.04安装cuda11.8教程

【linux】服务器Ubuntu20.04安装cuda11.8教程 文章目录 【linux】服务器Ubuntu20.04安装cuda11.8教程到官网找到对应版本下载链接终端操作cudnn安装到官网下载下载后解压进入解压后的目录&#xff1a;将头文件复制到 /usr/local/cuda/include/ 目录&#xff1a;将库文件复制到 …...

SpringMVC其他扩展

一、全局异常处理机制: 1.异常处理两种方式: 开发过程中是不可避免地会出现各种异常情况的&#xff0c;例如网络连接异常、数据格式异常、空指针异常等等。异常的出现可能导致程序的运行出现问题&#xff0c;甚至直接导致程序崩溃。因此&#xff0c;在开发过程中&#xff0c;…...

用“*”构成一个倒三角形:JAVA

输入&#xff1a;5 输出&#xff1a; ******* ***** *** * 代码&#xff1a; import java.util.Scanner; //倒三角 public class FF6 {public static void main(String[] args) {Scanner scannernew Scanner(System.in);while (scanner.hasNextInt()){int nscanner…...

洛谷P2670扫雷游戏(Java)

三.P2670 [NOIP2015 普及组] 扫雷游戏 题目背景 NOIP2015 普及组 T2 题目描述 扫雷游戏是一款十分经典的单机小游戏。在 n 行 m列的雷区中有一些格子含有地雷&#xff08;称之为地雷格&#xff09;&#xff0c;其他格子不含地雷&#xff08;称之为非地雷格&#xff09;。玩…...

Windows 11 环境下 条码阅读器输入到记事本的内容不完整

使用Windows11时&#xff0c;为什么记事本应用程序中的扫描数据被截断或不完整?为什么sdo 特殊字符的显示与Windows 10 记事本应用程序不同? 很多人认为和中文输入法有关&#xff0c;其实主要问题出在这个windows11下的记事本程序上&#xff0c;大家知道这个就可以了&#x…...

C# 动态类型 Dynamic

文章目录 前言1. 什么是 Dynamic&#xff1f;2. 声明 Dynamic 变量3. Dynamic 的运行时类型检查4. 动态类型与反射的对比5. 使用 Dynamic 进行动态方法调用6. Dynamic 与 原生类型的兼容性7. 动态与 LINQ 的结合8. 结合 DLR 特性9. 动态类型的性能考虑10. 何时使用 Dynamic&…...

设计模式10:观察者模式(订阅-发布)

系列总链接&#xff1a;《大话设计模式》学习记录_net 大话设计-CSDN博客 参考&#xff1a;简说设计模式——工厂方法模式 - JAdam - 博客园 参考&#xff1a;简单工厂模式(Simple Factory Pattern) - 回忆酿的甜 - 博客园 一&#xff1a;概述 观察者模式&#xff0…...

2020 年 12 月青少年软编等考 C 语言四级真题解析

目录 T1. 开餐馆思路分析T2. 邮票收集思路分析T3. 带通配符的字符串匹配思路分析T4. 删除数字思路分析T1. 开餐馆 北大信息学院的同学小明毕业之后打算创业开餐馆。现在共有 n n n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n n n 个地点排列在同一条直线…...

高级java每日一道面试题-2024年12月03日-JVM篇-什么是Stop The World? 什么是OopMap? 什么是安全点?

如果有遗漏,评论区告诉我进行补充 面试官: 什么是Stop The World? 什么是OopMap? 什么是安全点? 我回答: 在Java虚拟机&#xff08;JVM&#xff09;中&#xff0c;Stop The World、OopMap 和 安全点 是与垃圾回收&#xff08;GC&#xff09;和性能优化密切相关的概念。理…...

探索 Apache Commons Collections 4:Java 集合框架的强大扩展

在 Java 开发中&#xff0c;集合框架是处理数据的核心工具。然而&#xff0c;标准 Java 集合框架虽然功能强大&#xff0c;但在某些场景下仍显得不够灵活。Apache Commons Collections 4&#xff08;以下简称 commons-collections4&#xff09;作为一个强大的工具库&#xff0c…...

NIO(New IO)和BIO(Blocking IO)的区别

Java中的NIO&#xff08;New IO&#xff09;和BIO&#xff08;Blocking IO&#xff09;的区别及NIO的核心组件 Java中的NIO&#xff08;New IO&#xff09;和BIO&#xff08;Blocking IO&#xff09;是两种不同的网络通信模型&#xff0c;各自具有独特的特性和适用场景。下面将…...

【串口助手开发】visual studio 使用C#开发串口助手,生成在其他电脑上可执行文件,可运行的程序

1、改成Release&#xff0c;生成解决方案 串口助手调试成功后&#xff0c;将Debug改为Release&#xff0c;点击生成解决方案 2、运行exe文件 生成解决方案后&#xff0c;在bin文件夹下&#xff0c; Release文件夹下&#xff0c;生成相关文件 复制一整个Release文件夹&#xf…...

Linux 编译 convert_geotiff 时遇到的几个问题

步骤1&#xff1a;安装libgeotiff-dev 在ubuntu上&#xff0c;安装命令为&#xff1a; sudo apt-get install libgeotiff-dev在macos上&#xff0c;安装命令为&#xff1a; brew install libgeotiff在Linux上安装命令为&#xff1a; sudo yum install libgeotiff-devel注意…...