什么是直方图算法
什么是直方图算法?
直方图算法是一种优化决策树分裂点搜索效率的算法,被广泛应用于像 LightGBM 和 XGBoost 这样的梯度提升决策树框架中。其核心思想是通过将连续特征的取值范围离散化为有限的区间(称为 bins),在这些区间上计算统计量以确定最佳分裂点。
直方图算法的核心流程
-
特征值离散化(分桶化):
- 连续特征被分为固定数量的区间(bins),每个区间表示一段范围内的值。
- 例如,将一个特征值的范围 [ 0 , 100 ] [0, 100] [0,100] 划分为 10 个区间,每个区间的大小是 10,那么特征值 x = 15 x=15 x=15 将被映射到区间 [ 10 , 20 ] [10, 20] [10,20] 对应的 bin。
-
构建直方图:
- 在每轮训练中,遍历样本数据,为每个 bin 累计对应的梯度和统计量(如样本权重、样本数量等)。
- 例如:
- Bin 1:梯度和 G 1 G_1 G1,样本数量 N 1 N_1 N1
- Bin 2:梯度和 G 2 G_2 G2,样本数量 N 2 N_2 N2
- …
-
计算分裂增益:
- 遍历直方图中的每个分裂点,基于直方图统计量(如梯度和、样本权重)计算分裂增益。
- 常用公式(以均方误差为例):
Gain = G left 2 H left + G right 2 H right − G total 2 H total \text{Gain} = \frac{G_\text{left}^2}{H_\text{left}} + \frac{G_\text{right}^2}{H_\text{right}} - \frac{G_\text{total}^2}{H_\text{total}} Gain=HleftGleft2+HrightGright2−HtotalGtotal2
其中:- G left G_\text{left} Gleft、 G right G_\text{right} Gright:左、右子节点的梯度和;
- H left H_\text{left} Hleft、 H right H_\text{right} Hright:左、右子节点的二阶导数和(Hessian)。
-
选择最佳分裂点:
- 根据分裂增益选择直方图中使增益最大的分裂点。
为什么使用直方图算法?
直方图算法的目标是加速分裂点搜索过程,特别是在大规模数据和高维特征场景下。以下是使用直方图算法的原因:
-
时间复杂度降低:
- 传统分裂点搜索:对每个特征值进行排序,并在排序后的值之间计算增益,时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)。
- 直方图算法:通过分桶,每个特征的分裂点搜索复杂度仅为 O ( k ) O(k) O(k),其中 k k k 是 bin 的数量,通常远小于样本数 n n n。
-
内存效率提高:
- 连续特征被映射为离散的整数(bin 索引),内存占用显著降低。
- 离散化后的统计量只需在固定数量的 bin 上累加,而不是存储每个样本的原始值。
-
支持稀疏特征:
- 对于稀疏特征(如文本特征的TF-IDF矩阵),直方图算法可以高效处理零值分布。
-
易于并行化:
- 直方图算法天然适合并行化。多个特征的直方图可以独立构建,特征的分裂点选择也可以并行化完成。
直方图算法的特点
-
快速性:
- 特征值离散化后,分裂点搜索在离散的 bin 空间进行,计算复杂度大幅降低。
-
精度折衷:
- 离散化会导致信息损失(如分裂点的精度降低),但通常通过增加 bin 的数量可以减轻这一问题。
- 默认 bin 数量通常为 256,兼顾了效率与性能。
-
增量更新机制:
- 在树的增量构建过程中,直方图可以高效地从父节点继承统计量,并根据样本分配情况快速更新,避免重复计算。
直方图算法的改进(以LightGBM为例)
-
单树共享直方图:
- 在同一棵树的构建过程中,叶子节点之间共享直方图,减少重复构建带来的额外开销。
-
区间剪枝:
- 在特征分裂时,LightGBM会通过前序剪枝技术限制分裂搜索的区间,进一步提高效率。
-
稀疏直方图优化:
- 对于稀疏数据,LightGBM只对非零值部分的 bin 进行统计,加速计算。
直方图算法的数学直观
假设某特征的连续取值范围为 [ 0 , 100 ] [0, 100] [0,100],包含 1,000,000 个样本。传统算法需要对这 1,000,000 个样本排序,计算分裂点。而直方图算法将其划分为 256 个 bins,每个 bin 的范围是 [ i × 0.39 , ( i + 1 ) × 0.39 ] [i \times 0.39, (i+1) \times 0.39] [i×0.39,(i+1)×0.39](0.39 是 100 / 256 100/256 100/256)。
-
传统方法:
- 遍历每个样本点可能的分裂点,计算增益。
- 时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)。
-
直方图方法:
- 每个样本点被映射到对应的 bin 索引。
- 在 256 个 bins 中搜索最佳分裂点,时间复杂度为 O ( k ) O(k) O(k)。
最终,直方图算法实现了计算时间与内存使用的显著优化,同时保持了模型性能。
相关文章:
什么是直方图算法
什么是直方图算法? 直方图算法是一种优化决策树分裂点搜索效率的算法,被广泛应用于像 LightGBM 和 XGBoost 这样的梯度提升决策树框架中。其核心思想是通过将连续特征的取值范围离散化为有限的区间(称为 bins),在这些…...
pg_dump -Fc 导出的自定义格式数据库文件 相关操作
实例 将 test.dmp 文件转换为普通SQL内容, 并打印到屏幕 pg_restore -U postgres -Fc -f - test.dump将 test.dmp 文件转换为普通SQL内容, 并输出到 test.sql 文件中 pg_restore -U postgres -Fc -f test.sql -v test.dump备份得到自定义格式的数据库文件(dmp) pg_dump -U…...
Oh My Posh安装
nullSet up your terminalhttps://ohmyposh.dev/docs/installation/windows Git ee oh-my-posh: Windows上的oh-my-zsh,源地址 https://github.com/JanDeDobbeleer/oh-my-posh.git (gitee.com)https://gitee.com/efluent/oh-my-posh...
Node.js——fs模块-文件夹操作
1、借助Node.js的能力,我们可以对文件夹进行创建、读取、删除等操作 2、方法 方法 说明 mkdir/mkdirSync 创建文件夹 readdir/readdirSync 读取文件夹 rmdir/rmdirSync 删除文件夹 3、语法 其余的方法语法类似 本文的分享到此结束,欢迎大家评论区…...
15分钟学 Go 实战项目三 : 实时聊天室(学习WebSocket并发处理)
实时聊天室:学习WebSocket并发处理 目标概述 在本项目中,我们将创建一个实时聊天室,使用Go语言和WebSocket来处理并发消息交流。这将帮助你深入理解WebSocket协议的工作原理以及如何在Go中实现并发处理。 1. 项目需求 功能需求 用户可以…...
架构评估的方法
三种评估方法※ 第一是基于问卷(检查表)的方式,通过问卷调查对系统比较熟悉的相关人员,这种方式主观性很强。 专家问卷评估、用户问卷评估、内部团队问卷评估 第二是基于度量的方式,对系统指标完全量化,基于量化指标评价系统,这种方式需要评估者对系统非常熟悉。 软件质…...
羲和数据集收集器1.0
为了提升问答对的提取能力并完善GUI,我们从以下几个方面进行改进: 增强文本清理和解析能力:确保能够更准确地识别问答对。 支持更多文件格式:除了现有的 .txt, .docx, 和 .pdf,可以考虑支持其他常见格式如 .xlsx 等。 优化GUI设计:提供更友好的用户界面,包括进度条、日…...
ENSP OSPF和BGP引入
路由协议分为:内部网关协议和外部网关协议。内部网关协议用于自治系统内部的路由,包括:RIP和OSPF。外部网关协议用于自治系统之间的路由,包括BGP。内部网关协议和外部网关协议配合来共同完成网络的路由。 BGP:边界网关路由协议(b…...
软件工程 软考
开发大型软件系统适用螺旋模型或者RUP模型 螺旋模型强调了风险分析,特别适用于庞大而复杂的、高风险的管理信息系统的开发。喷泉模型是一种以用户需求为动力,以对象为为驱动的模型,主要用于描述面向对象的软件开发过程。该模型的各个阶段没有…...
证书学习(六)TSA 时间戳服务器原理 + 7 个免费时间戳服务器地址
目录 一、简介1.1 什么是时间戳服务器1.2 名词扩展1.3 用时间戳标记顺序1.4 7 个免费TSA时间戳服务器地址(亲测可用)1.5 RFC 3161 标准二、时间戳原理2.1 时间戳服务工作流程2.2 验证工作流程2.3 举个例子2.4 时间戳原理总结三、代码实现3.1 curl 命令请求时间戳3.2 java 代码…...
NVR设备ONVIF接入平台EasyCVR私有化部署视频平台如何安装欧拉OpenEuler 20.3 MySQL
在当今数字化时代,安防视频监控系统已成为保障公共安全和个人财产安全的重要工具。NVR设备ONVIF接入平台EasyCVR作为一款功能强大的智能视频监控管理平台,它不仅提供了视频远程监控、录像、存储与回放等基础功能,还涵盖了视频转码、视频快照、…...
c中柔性数组
c99中,结构中最后一个元素允许是未知大小的数组,这就叫柔性数组成员。 柔性数组的特点 1.结构中柔性数组前必须至少有一个其他成员 2.sizeof返回的这种结构大小不包括柔性数组的内存 3.包含柔性数组成员的结构用malloc函数进行动态分配,并…...
图像信号处理器(ISP,Image Signal Processor)详解
简介:个人学习分享,如有错误,欢迎批评指正。 图像信号处理器(ISP,Image Signal Processor) 是专门用于处理图像信号的硬件或处理单元,广泛应用于图像传感器(如 CMOS 或 CCD 传感器&a…...
越权访问漏洞
V2Board Admin.php 越权访问漏洞 ## 漏洞描述 V2board面板 Admin.php 存在越权访问漏洞,由于部分鉴权代码于v1.6.1版本进行了修改,鉴权方式变为从Redis中获取缓存判定是否存在可以调用… V2Board Admin.php 越权访问漏洞 漏洞描述 V2board面板 Admin.ph…...
【Ant.designpro】上传图片
文章目录 一、前端二、后端 一、前端 fieldProps:可以监听并且获取到组件输入的内容 action{“/api/upload_image”} 直接调用后端接口 <ProFormUploadButtonlabel{"上传手续图片"}name{"imgs"}action{"/api/upload_image"}max{5} fieldPro…...
为何选择Spring AI Alibaba开发智能客服平台?
0 前言 本文来看如何使用Spring AI Alibaba构建Agent应用。 1 需求 智能客服平台,可帮助用户完成机票预定、问题解答、机票改签、取消等动作,具体要求: 基于 AI 大模型与用户对话,理解用户自然语言表达的需求支持多轮连续对话…...
HiveSQL 中判断字段是否包含某个值的方法
HiveSQL 中判断字段是否包含某个值的方法 在 HiveSQL 中,有时我们需要判断一个字段是否包含某个特定的值。下面将介绍几种常用的方法来实现这个功能。 一、创建示例表并插入数据 首先,我们创建一个名为employee的表,并插入一些示例数据&am…...
Nginx简易配置将内网网站ssh转发到外网
声明:本内容仅供交流学习使用,部署网站上线还需要根据有关规定申请域名以及备案。 背景 在内网的服务器有一个运行的网页,现使用ssh反向代理,将它转发到外网的服务器。 但是外网的访问ip会被ssh反向代理拦截 所以使用Nginx进行…...
【go从零单排】error错误处理及封装
🌈Don’t worry , just coding! 内耗与overthinking只会削弱你的精力,虚度你的光阴,每天迈出一小步,回头时发现已经走了很远。 📗概念 在 Go 语言中,error 是一个内置的接口类型,用于表示错误情…...
全平台设置jetbrains mono字体
相信大家都用过IDEA,推荐使用开发字体:jetbrains mono 本地下载的位置(记一下)后续需要打开安装 本地下载的:E:\download\font\jetbrainsmono\JetBrainsMono-2.304\fonts\ttf 官网上下载:https://www.jetbr…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
机器学习的数学基础:线性模型
线性模型 线性模型的基本形式为: f ( x ) ω T x b f\left(\boldsymbol{x}\right)\boldsymbol{\omega}^\text{T}\boldsymbol{x}b f(x)ωTxb 回归问题 利用最小二乘法,得到 ω \boldsymbol{\omega} ω和 b b b的参数估计$ \boldsymbol{\hat{\omega}}…...
在Zenodo下载文件 用到googlecolab googledrive
方法:Figshare/Zenodo上的数据/文件下载不下来?尝试利用Google Colab :https://zhuanlan.zhihu.com/p/1898503078782674027 参考: 通过Colab&谷歌云下载Figshare数据,超级实用!!࿰…...
Selenium 查找页面元素的方式
Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素,以下是主要的定位方式: 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...
