【人工智能 | 机器学习 | 理论篇】决策树(decision tree)

文章目录

  • 1. 基本流程
  • 2. 划分选择
    • 2.1 信息增益
    • 2.2 增益率
    • 2.3 基尼系数
  • 3. 剪枝处理
    • 3.1 预剪枝
    • 3.2 后剪枝
  • 4. 连续与缺失值
    • 4.1 连续值处理
    • 4.2 缺失值处理
  • 5. 多变量决策树


1. 基本流程

二分类任务决策树流程:
在这里插入图片描述
决策树:包含 1个根结点、若干个内部结点、若干个叶结点。叶结点对应决策结果,内部结点对应属性测试

决策树训练过程
在这里插入图片描述决策树训练时,有 3 种情况会导致递归 return

  1. 结点包含的样本同属于同一类别,无需划分
  2. 属性值完全一致,或者属性集为空(递归边界条件)
  3. 样本集合为空

对第1、2点区别:
样本同属于同一类别,指的是 D 的 y 值取值相同,此时无需划分
属性值完全一致,但是对应的 y 值可能有多个,此时也无需划分。一个原因导致多个结果,不能界定该原因具体会导致哪个结果

第1点关注的是决策树的目标输出
第2点关注的是输入特征

对于2,可以把当前结点标记为叶结点,将类别 y 设定为 取值最多 的类别(后验分布)
对于3,标记为叶结点,将类别设定为 父结点 所含样本最多的类别(先验分布)

对于3,样本划分过程有空集落入,可能由于:

  • 划分过程中,样本被错误分类到其他子节点
  • 过程的划分属性或者划分值导致某些子节点没有样本


这样处理是为了使模型处理不完美数据时也能正常工作,并给出合理的预测结果


2. 划分选择

决策树学习算法 可知,算法的关键在于第 8 行:如何选择最优属性
随着划分过程不断进行,决策树的分支包含的样本应尽可能属于同一类别,即结点的 纯度 越来越高

2.1 信息增益

信息熵(information entropy):度量样本集合纯度的指标
在这里插入图片描述

约定:若 p = 0,则 p l o g 2 p k = 0 plog_2p_k = 0 plog2pk=0

E n t ( D ) Ent(D) Ent(D) 的值越小,D 的纯度越高

信息增益(information gain)
在这里插入图片描述信息增益越大,用 a 来进行划分的 “纯度提升” 越大

a ∗ = a r g m a x a ∈ A G a i n ( D , a ) a_*= \underset{a\in A}{arg\ max}\ Gain(D, a) a=aAarg max Gain(D,a)

信息增益计算案例:在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述

2.2 增益率

信息增益准则对取值数目较多的属性有偏好。例如把上述案例的编号作为划分属性,信息增益远大于其他属性。因为每个编号分支仅对应一个样本,分支结点的纯度最大。但这没有意义
增益率:减少信息增益准则对可取值数目较多的属性的偏好带来不利影响
在这里插入图片描述增益率 对可取值较的属性有偏好
信息增益 对可取值较的属性有偏好
可以从划分属性中 找出信息增益高于平均水平的属性,再 从中选出增益率最高的

2.3 基尼系数

在这里插入图片描述


3. 剪枝处理

剪枝:对付“过拟合”。过度学习导致决策树分支过多
基本策略:预剪枝、后剪枝
预剪枝:生成决策树过程中,划分结点前先估计。若当前结点的划分不能提升决策树的泛化能力,停止划分并将结点标记为叶结点
后剪枝:生成完决策树,自底向上检察非叶结点。若将该结点对应的子树替换为叶结点能提升泛化性能,则将该子树替换为叶结点

验证方法可使用前面章节提到的 “留出法”,事先预留部分数据作为验证集


3.1 预剪枝

以下为原文:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

对于结点2,3,4,按脐部的属性凹陷、稍凹、平坦将训练集归类。对于凹陷,1、2、3是好瓜,14是坏瓜。因此把 结点2 暂时判断为 好瓜。对于稍凹,6、7是好瓜,15、17是坏瓜。此时把结点3归纳为好瓜、坏瓜 对验证集精度计算是没有影响的

如果某个结点划分的子结点,好瓜坏瓜的比例都是50%,验证集精度划不划分都是50%。个人觉得划分好点。可能划分后子结点的子结点能提升验证集精度。可能赚可能不赚,但至少不会亏

3.2 后剪枝

在这里插入图片描述在这里插入图片描述

在这里插入图片描述


4. 连续与缺失值

4.1 连续值处理

上述例子用到的都是离散属性来生成决策树。在现实学习任务中,常会遇到连续属性。连续属性的可取值数目是无限的,因此可以将 连续属性离散化

关键在于找到划分点 t。以连续值的二分类任务为例:
在这里插入图片描述
在这里插入图片描述

以下示例:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述


计算 G a i n ( D , a ) Gain(D, a) Gain(D,a),先计算根结点的熵 E n t ( D ) Ent(D) Ent(D) ,17瓜,8好9坏,得 E n t ( D ) = 0.9975 Ent(D) = 0.9975 Ent(D)=0.9975

  1. t = 0.381 t = 0.381 t=0.381 为例,17个瓜分为2类,
  2. 小于等于0.381的,4瓜,0好4坏;
  3. 大于0.381,13瓜,8好5坏;
  4. 计算 E n t ( D ) Ent(D) Ent(D) 分别为 0,0.9612366。
  5. G a i n = E n t ( D ) − Σ ∣ D ′ ∣ ∣ D ∣ E n t ( D ′ ) = 0.9975 − ( 0.9612366 ∗ 13 17 + 0 ∗ 4 17 ) = 0.262 Gain = Ent(D) - \Sigma\frac{|D'|}{|D|}Ent(D') = 0.9975 - (0.9612366 * \frac{13}{17} + 0 * \frac{4}{17}) = 0.262 Gain=Ent(D)ΣDDEnt(D)=0.9975(0.96123661713+0174)=0.262


计算其他 t,得到的 G a i n Gain Gain 均小于此。所以选择 0.381 作为划分点

4.2 缺失值处理

将缺失值直接丢弃会造成样本浪费。考虑利用有缺失值的样例进行学习
在这里插入图片描述

  • (1)如何在属性值缺失情况下进行划分属性选择?
  • (2)给定划分属性,若样本在该属性上的值缺失,如何样本划分?

对于问题(1)
在这里插入图片描述在这里插入图片描述在这里插入图片描述

这部分就是把不缺失值的数据集单独拎出来,再计算时加个权重。

划分属性选择缺失值不参与

对于问题(2)
在这里插入图片描述

在a属性上的取值是样本在a上的取值,不是样本取值y

以下示例:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

ρ \rho ρ : 整个样本集中,无缺失值样本占的比例
p k p_k pk : 无缺失值样本中,某类样本占的比例
r r r :无缺失值样本中,属性某个取值的样本占的比例


5. 多变量决策树

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述在这里插入图片描述

在这里插入图片描述

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

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

相关文章

vue.js3+element-plus+typescript add,edit,del,search

vite.config.ts server: {cors: true, // 默认启用并允许任何源host: 0.0.0.0, // 这个用于启动port: 5110, // 指定启动端口open: true, //启动后是否自动打开浏览器 proxy: {/api: {target: http://localhost:8081/, //实际请求地址,数据库的rest APIschangeOr…

Maven Wrapper深入实战

概述 官网,GitHub。 Maven Wrapper,缩写为mvnw,是一个受Gradle Wrapper和Takari Wrapper启发而产生的Maven子项目,主要有以下三个用途: 让开发者电脑上无需安装Maven,也不用配置环境变量,即可…

【案例63】SSL RC4 加密套件支持检测 (Bar Mitzvah)修复方案

漏洞详情信息 漏洞名称 SSL RC4 加密套件支持检测 (Bar Mitzvah) 漏洞等级 高 漏洞描述 远程主机支持在一个或多个密码组中使用 RC4。 RC4 密码在伪随机字节流的生成中存在缺陷,导致引入了各种各样的小偏差,降低了其随机 性。 如果反复加密明文&am…

Linux下qt程序缺少中文字库,中文显示为框框

现象 Linux下qt5.9编译程序,运行时候界面上的中文显示一个一个的框框。 如图 原因 开发板里缺少中文字库或者qt字库环境未正常配置导致的。 解决方法一: 如果系统中存在中文字库,一般是在/usr/share/下有一个fonts文件夹 配置qt中文字库路…

【雷电防护】同为科技为国科大构建雷电防护系统

中国科学院大学(University of Chinese Academy of Sciences),以下简称“国科大”,主校区位于北京市,是一所以科教融合为办学模式、研究生教育为办学主体的创新型大学,是国家“双一流”建设高校&#xff0c…

go+gin+vue入门

后端框架 1、安装go、goland 2、创建空项目 3、下载要用的包:命令行输入go get -u github.com/xxxx 4、安装mysql数据库,使用navicat创建数据库。 5、按照项目框架搭建目录、文件、代码:如router、model… 6、运行测试,go run ma…

openshift node NotReady kubelet http: TLS handshake error

文章目录 问题现象解决方法 问题现象 openshift 集群 node 节点 notready $ oc get node NAME STATUS ROLES AGE VERSION master1.ocp4.demo.com Ready control-plane,master 4d14h v1.29.76abe8a1 master2.ocp4…

什么是响应式?

表达式: 用于表达式进行插值,渲染到页面之中 语法: {{ 表达式 }} 案例 <template><h1>{{ arr[2] }}</h1><h1>{{ 9 5 }}</h1><h1>{{ "神奇" }}</h1> </template><script setup> import { ref } from vue; …

C++ | Leetcode C++题解之第375题猜数字大小II

题目&#xff1a; 题解&#xff1a; class Solution { public:int getMoneyAmount(int n) {vector<vector<int>> f(n1,vector<int>(n1));for (int i n - 1; i > 1; i--) {for (int j i 1; j < n; j) {f[i][j] j f[i][j - 1];for (int k i; k &l…

刚开始学习软件编程,如何克服编程学习中的挫折感?

编程学习之路往往充满挑战&#xff0c;即便是最优秀的程序员也会遇到挫折。克服挫折感的关键在于心态、方法和持续的学习。以下是一些通俗易懂的建议和案例&#xff0c;展示了如何在遇到编程难题时保持积极态度。 1. 接受挫折是成长的一部分 编程是一个不断学习和成长的过程。…

【Java设计模式】Bridge模式:在Java中解耦抽象与实现

文章目录 【Java设计模式】Bridge模式&#xff1a;在Java中解耦抽象与实现一、概述二、Bridge设计模式的别名三、Bridge设计模式的意图四、Bridge模式的详细解释及实际示例五、Java中Bridge模式的编程示例六、Bridge模式类图七、Java中何时使用Bridge模式八、Java中Bridge模式的…

【日记】今天实在太累了(436 字)

正文 今天的工作强度跟之前完全不是一个级别。能不能不要给我找这么多事做&#xff0c;我只想摸鱼摆烂。以后到下一个单位就说自己啥都不会好了&#xff0c;省得一天天全来找我。 忙碌程度上升了一个数量级&#xff0c;一天结束之后完全不想说话。 好想睡觉。 昨晚尝试完成年度…

【Python】Python 函数综合指南——从基础到高阶

文章目录 Python 函数综合指南1. 函数介绍1.1 什么是函数&#xff1f;1.2 定义函数示例&#xff1a;1.3 调用函数1.4 函数参数1.4.1 必需参数1.4.2 默认参数1.4.3 关键字参数1.4.4 可变长度参数 2. Python 内置函数2.1 字符串处理函数示例&#xff1a; 2.2 数学函数示例&#x…

大数据之数据湖Apache Hudi

一、Hudi框架概述 Apahe Hudi (Hadoop Upserts delete and Incrementals) 是Uber主导开发的开源数据湖框架&#xff0c;为了解决大数据生态系统中需要插入更新及增量消费原语的摄取管道和ETL管道的低效问题&#xff0c;该项目在2016年开始开发&#xff0c;并于2017年开源&#…

Memcached:单节点、集群案例;概念、工作原理

目录 案例前置知识点 Memcached 概念 部署场景 Memcached常用架构 流程 Memcached Memcached API 数据存储方式 数据过期方式 LRU Lazy Expiration Memcached缓存机制 Memcached路由算法 求余数hash算法 一致性hash算法 Memcached分布式 案例 单节点Memcach…

mysql数据库--表的操作

目录 1.创建表 2.查看表 3.修改表 对于表的重命名 更改某一列的属性 直接删除某一列 修改某一列的名称&#xff1a; 增加某一列 4.删除表 1.创建表 按照上次的那个创建表的操作&#xff0c;我们创建完成之后首先就是去把这个use一下&#xff0c;即进入到这个表里面去…

1+X 职业技能等级证书面向哪些人群介绍

日前&#xff0c;“大数据应用开发&#xff08;Python&#xff09;”职业技能等级证书已开放面向社会人员招生。 什么是1X职业技能等级证书&#xff1f; “1” 学历证书&#xff0c;代表专业&#xff0c;即学历、毕业 “X” 若干职业技能等级证书&#xff0c;是根据…

Linux远程管理—SSH协议

SSH协议是远程连接的安全性协议&#xff0c;该协议可以有效防止远程管理过程中的信息泄漏&#xff0c;是西安传输数据加密&#xff0c;能够防止DNS和IP欺骗&#xff0c;传输数据压缩&#xff0c;加快传输速度。 安全验证方法有口令验证和密钥验证两种实现手段&#xff0c;该协…

微信H5下载文件、微信浏览器无法下载文件解决方案

手机端的微信访问网页的时候&#xff0c;是禁止直接下载文件的 但是IOS端可以预览.txt/.doc/.docx/.xls/xlsx/.pdf等格式的文件&#xff0c;Android端在下载这些格式的文件时&#xff0c;可以唤起 ‘即将离开微信&#xff0c;在浏览器打开’ 提示 所以&#xff0c;根据手机微…

redis面试(二十四)Semaphore锁实现

Semaphore也是redis分布式锁支持的一种&#xff0c;同步组件 之前给大家的讲解的锁&#xff0c;基本上都是同时间只能一个客户端获取这个锁&#xff0c;然后做一些事情&#xff0c;处理完了以后释放锁 Semaphore&#xff0c;信号量&#xff0c;他作为一个锁机制&#xff0c;可以…