决策树(部分)

目录

信息熵

总结:

特征选择

信息增益:ID3算法

增益率:C4.5

基尼指数

剪枝处理

预剪枝

后剪枝


信息熵

         信息熵 (entropy)是 用于度量样本集合“ 纯度 ” 最常用的一种指标,其中 “ 熵 ” 是事物的不确定性,假定当前样本集合D根据某属性共分为 |y| 个集合,每个集合中,k 类样本所占的比例为p_{k},则 D 的信息熵定义为:
Ent(D)=-\sum_{k=1}^{|y|}{p_{k}}{log_{2}}{p_{k}}
        这个信息熵值越小,则 D 的纯度越高
        西瓜书信息熵计算的例子:

        对于这个数据集根节点,样本有 2 种类型,分别为“是好瓜”与“否好瓜”,则 |y| 为2,p1=8/17(是好瓜),p2=9/17(否好瓜),可得总体信息熵
Ent(D)=-\sum_{k=1}^{|2|}{p_{k}}{log_{2}}{p_{k}}=-(\frac{8}{17}{log_{2}}\frac{8}{17}+\frac{9}{17}{log_{2}}\frac{9}{17})
        对于色泽这个属性,样本有 3 种类型:
  • 青绿样本 D1:1,4,6,10,13,17。共6个,3是3否,信息熵

Ent(D_{1})=-(\frac{3}{6}{log_{2}}\frac{3}{6}+\frac{3}{6}{log_{2}}\frac{3}{6})=1

  • 乌黑样本 D2:2,3,7,8,9,15。共6个,4是2否,信息熵

Ent(D_{2})=-(\frac{4}{6}{log_{2}}\frac{4}{6}+\frac{2}{6}{log_{2}}\frac{2}{6})=0.918

  • 浅白样本 D3:5,11,12,14,16。共5个,1是4,信息熵

Ent(D_{3})=-(\frac{1}{5}{log_{2}}\frac{1}{5}+\frac{4}{5}{log_{2}}\frac{4}{5})=0.772

        色泽这个属性总体的信息熵为三种类型样本的加权平均,因为样本量越多的类型越重要,信息熵越大,即:

 \frac{6}{17}Ent(D_{1})+\frac{6}{17}Ent(D_{2})+\frac{5}{17}Ent(D_{3})=\frac{6}{17}*1+\frac{6}{17}*0.918+\frac{5}{17}*0.722

总结:

        信息熵与概率是一个事物的一体两面,概率指“事件多大可能发生”,表示事件发生的“确定性”,而信息熵指“事件有几种可能性”表示时间发生的“不确定性”。反映的是事情复杂、混乱的程度。统计意义上来说这是一种加权平均,表示整体的选择个数。信息熵还可以用来进行信息编码,可用于计算信息编码的平均长度

        由于日常所得的数据中既有有效数据又含噪音,选择特征的方法包括信息增益(Information Gain)、基尼指数(Gini Index)和增益率(Gain Ratio)等。

特征选择

信息增益:ID3算法

        在了解信息熵的意思后,我们就可以通过得知信息前后不确定性的变化(信息熵的差额)对信息进行量化,从而看出信息对问题判断是否有效,多有效

        由此将这个信息熵的差额称作信息增益,假设划分前的信息熵为Ent(D),,则信息增益定义为:

Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Ent(D^{v})

         前者是划分前的信息熵,后者是划分后的信息熵,信息增益越大,使用该属性划分的效果越好

        综上,将纹理作为决策树的第一个分叉。在分叉后,将子集作为样本,每个类别作为根节点,计算其他属性的信息增益,继续分叉

增益率:C4.5

        信息增益一般偏向于选择属性取值较多的特征,为减少这种偏好可能带来的不利影响使用增益率,其公式:

Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}=\frac{Gain(D,a)}{-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}log_{2}\frac{|D^{v}|}{|D|}}

        a 是指某属性有几种类别的特征,取值数量越多,V 越大,IV(a) 越大,选择模型时,先从候选划分属性中找出信息增益高于平均水平的, 再从中选取增益率最高的

        补充:关于属性分裂信息度量

        在属性分列后,需要考虑接下来在哪个叶子节点进行分列

        用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息,这些信息称为属性的内在信息(instrisic information),反应节点的不确定性。举个例子,假设上面色泽分裂出的三个颜色,浅白的全是坏瓜,说明这个类别类别是”纯“的,我们用其他“不纯”的节点进行其他属性的分裂

        C4.5的算法流程:

  1. while(当前节点"不纯"):

  2. 计算当前节点的类别熵(以类别取值计算,每个类别当做根节点计算)

  3. 计算当前阶段的属性熵(按照每个属性取值的类别计算,某类别中其他属性的熵)

  4. 计算信息增益

  5. 计算各个属性的分裂信息度量

  6. 计算各个属性的信息增益率

  7. end while

  8. 当前阶段设置为叶⼦节点

基尼指数

        该方法反映了 D 中抽取两个样例,其类别不一致的概率

        基尼值

Gini(D)=\sum_{k=1}^{|y|}\sum_{k'\neq k}p_{k}p_{k'}=1-\sum_{k=1}^{|y|}p_{k}^{2}

        基尼系数

Gini\_index(D,a)=\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Gini(D^{v})

        由于划分选择的各种准则虽然对决策树的尺寸有较大影响,但对泛化性能的影响非常小,所以关于基尼系数可以在该文中的应 P 查看具体例子,图片源:
源自:决策树算法概述及原理详解-CSDN博客

        只需要知道,在候选属性集合中,选取那个使划分后基尼指数最小的属性即可,基尼指数越小,纯度越高(纯度指分完之后正反例是否掺杂)

剪枝处理

        核心目的:解决过拟合问题

预剪枝

        自上而下,若分叉不能提高精度,则不分

        对于数据的训练集,1~8是好瓜,9~17是坏瓜,按信息增益率的方法生成决策树:

        对于脐部和色泽的分支,对应属性的西瓜编号如下:

  • 脐部分叉之前3好瓜4坏瓜,测试集精度3/7,分叉后,测试集{9,13}样本预测错误,其余正确,精度5/7提高了,所以这个叉应该分。

        每个属性取值的标记依靠训练集中好坏瓜的比例来定,好瓜多就标记为好瓜,如果某一取值好坏瓜的比例为1:1,默认为是好瓜

  • 色泽分叉前,4、5号预测准确,精度2/3,分叉后只有4号样本预测正确,精度1/3,下降。因此色泽这个枝不应该分,剪去
  • 同理,对于根蒂这个属性,分叉前后都是一对一错(8是好瓜,9非好瓜),精度并未提升,因此也不分叉

        最终预剪枝得到的决策树如下:

后剪枝

        与预剪枝类似,只是后剪枝是自下而上的,能不剪就不剪

        考虑最底下的纹理是否分叉,在未剪枝的情况下,3个错4个对,正确率3/7,减去后,测试集中的8号被预测正确了,此时正确率提高为4/7,因此应该这个枝剪去

        对于其他节点一样进行判断,最终得到这样的结果 :

        连续值与缺失值的处理待补充,缺失值不同于常规方法的是在决策树中,用缺失前后数据量的比值对信息增益进行缩小,即可计算

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/467441.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

webpack 执行流程 — 实现 myWebpack

前言 实现 myWebpack 主要是为了更好的理解,webpack 中的工作流程,一切都是最简单的实现,不包含细节内容和边界处理,涉及到 ast 抽象语法树和编译代码部分,最好可以打印出来观察一下,方便后续的理解。 re…

【python】Flask

文章目录 1、Flask 介绍2、Flask 实现网页版美颜效果3、参考 1、Flask 介绍 Flask 是一个用 Python 编写的轻量级 Web 应用框架。它设计简单且易于扩展,非常适合小型项目到大型应用的开发。 以下是一些 Flask 库中常用的函数和组件: 一、Flask 应用对…

AI大模型如何重塑软件开发流程?

《AI大模型对软件开发流程的重塑:变革、优势、挑战与展望》 一、传统软件开发流程与模式(一)传统软件开发流程(二)传统软件开发模式面临的问题(一)AI在软件开发中的应用场景(二&…

OceanBase 应用实践:如何处理数据空洞,降低存储空间

问题描述 某保险行业客户的核心系统,从Oracle 迁移到OceanBase之后,发现数据存储空间出现膨胀问题,数据空间 datasize9857715.48M,实际存储占用空间17790702.00M。根据 required_mb - data_mb 值判断,数据空洞较为严重…

Zookeeper运维秘籍:四字命令基础、详解及业务应用全解析

文章目录 一、四字命令基础二、四字命令详解三、四字命令的开启与配置四、结合业务解读四字命令confconsenvi命令Stat命令MNTR命令ruok命令dump命令wchswchp ZooKeeper,作为一款分布式协调服务,提供了丰富的四字命令(也称为四字短语&#xff…

MATLAB大数计算工具箱及其用法

1. MATLAB大数工具箱Variable Precision Integer Arithmetic介绍 Variable Precision Integer Arithmetic是John DErrico 开发的大数运算工具箱,可以用完全任意大小的整数进行算术运算。支持vpi定义的数组和向量。 2.MATLAB代码 完整代码见: https://download.cs…

【野生动物识别系统】Python+深度学习+人工智能+卷积神经网络算法+TensorFlow+ResNet+图像识别

一、介绍 动物识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对18种动物数据集进行训练,最后得到一个识别精度较高的模型。并基于Django框架,开发网页端操作平台&…

数据库_SQLite3

下载 1、更新软件源: sudo apt-get update 2、下载SQLite3: sudo apt-get install sqlite3 3、验证: sqlite3启动数据库,出现以下界面代表运行正常。输入 .exit 可以退出数据库 4、安装sqlite3的库 sudo apt-get install l…

PyTorch核心概念:从梯度、计算图到连续性的全面解析(三)

文章目录 Contiguous vs Non-Contiguous TensorTensor and ViewStrides非连续数据结构:Transpose( )在 PyTorch 中检查Contiguous and Non-Contiguous将不连续张量(或视图)转换为连续张量view() 和 reshape() 之间的区别总结 参考文献 Contig…

如何解决导入aioredis报错TypeError: duplicate base class TimeoutError的问题(轻松解决,亲测有效)

下面是根据你的要求撰写的文章: 文章目录 📖 介绍 📖🏡 演示环境 🏡📒 aioredis导包报错 📒📝 解决方案📝 小贴士⚓️ 相关链接 ⚓️📖 介绍 📖 最近在使用Python异步redis模块aioredis的时候遇到了一个错误,导包报错提示 TypeError: duplicate base cla…

基于Springboot+Android的智慧社区互助平台 (含源码数据库)

1.开发环境 开发系统:Windows10/11 架构模式:MVC/前后端分离 JDK版本: Java JDK1.8 开发工具:IDEA 数据库版本: mysql5.7或8.0 数据库可视化工具: navicat 服务器: SpringBoot自带 apache tomcat 主要技术: Java,Springboot,mybatis,mysql,vue 2.视频演示地址 3.功能 这个系…

讨论一个mysql事务问题

最近在阅读一篇关于隔离级别的文章,文章中提到了一种场景,我们下面来分析一下。 文章目录 1、实验环境2、两个实验的语句执行顺序3、关于start transaction和start transaction with consistent snapshot4、实验结果解释4.1、实验14.2、实验24.3、调整实…

Kubernetes-编排工具篇-01-Kustomize与Helm对比

Kustomize与Helm对比 0、前言 K8s 是一个开源容器编排平台,可自动执行容器化应用程序的部署、扩展和管理。近年来,K8s 已成为采用云原生架构和容器化技术的组织的标准。 但是由于K8s的复杂性,所以很多公司以及开源组织都在开发相关的工具来…

确定图像的熵和各向异性 Halcon entropy_gray 解析

1、图像的熵 1.1 介绍 图像熵(image entropy)是图像“繁忙”程度的估计值,它表示为图像灰度级集合的比特平均数,单位比特/像素,也描述了图像信源的平均信息量。熵指的是体系的混乱程度,对于图像而言&#…

数字IC后端设计实现之Innovus自动修复Min Step DRC Violation方案

在实际IC后端项目中我们经常会遇到min step的DRC Violation,如下图所示。 在咱们IC后端训练营项目中也会遇到这类DRC Violation。这类DRC Violation的本质是出现Metal的Notch,即metal有凹槽。 如果是pg net的 Min Step问题,我们可以使用下面的…

进程相关内容

进程内容 进程类型守护进程进程的概念查看进程信息父子进程创建子进程进程结束 – exit/_exit进程回收 –wait waitpid 进程类型 交互进程 (Interactive Process) 交互进程是由用户通过终端或图形界面直接启动的进程,例如我们在命令行输入的命令。它通常需要等待用…

石墨舟氮气柜:半导体制造中的关键保护设备

石墨舟是由高纯度石墨材料制成的,主要用于承载硅片或其他基板材料通过高温处理过程,是制造半导体器件和太阳能电池片的关键设备之一。 石墨舟在空气中容易与氧气发生反应,尤其是在高温处理后,表面可能更为敏感;石墨舟具…

rabbitMq双节点高可用集群安装(亲测可用)

查询系统版本 cat /etc/redhat-release CentOS Linux release 7.7.1908 (Core) rabbitmq v3.9.13 (centos7支持比较大的版本了,后面版本貌似都是centos8以上) erlang erlang-23.3.4.11-1.el7.x86_64 (需要和rabbitmq版本匹配&…

简单介绍一下mvvm mvc mvp以及区别、历史

MVC(Model - View - Controller) 因MVC架构的灵活性,架构图形式很多,仅供参考 历史: MVC 是最早出现的软件架构模式之一,其历史可以追溯到 20 世纪 70 年代,最初被用于 Smalltalk - 80 环境。…

Nordic SoftDevice蓝牙主机操作流程

Nordic SoftDevice蓝牙主机操作流程 之前学习nordic的nus client 主机例程时做了些笔记,现在有空重新整理了一下发出来。 NRF_SDH_BLE_OBSERVER 宏介绍 这个宏可以设置多个BLE事件的回调函数,并按设置的优先级依次执行。这么一来,就可以将…