ID决策树的构造原理

devtools/2024/9/20 1:30:46/ 标签: 决策树, 算法, 机器学习, 人工智能

前言

🏷️🏷️本章开始学习有关决策树的相关知识,决策树是一种树形模型,也是一种常用的分类和回归方法。本章我们首先介绍第一种决策树的构造原理

学习目标

  1. 了解决策树算法的基本思想
  2. 掌握 ID3 决策树的构建原理

1.决策树介绍 

1.1案例引入 

有的同学可能在大学学习过一门课程叫《数据结构》,里面有一个重要的结构就是“树”,和现实生活中的树一样,树的主要由四部分树根、树干、树枝、树叶组成,今天的决策树也是一种树结构,大家学习的时候可以想象现实生活中的树来来理解。

决策树算法是一种监督学习算法,英文是Decision tree。

决策树思想的来源非常朴素,试想每个人的大脑都有类似于if-else这样的逻辑判断,这其中的if表示的是条件,if之后的then就是一种选择或决策。程序设计中的条件分支结构就是if-then结构,最早的决策树就是利用这类结构分割数据的一种分类学习方法。

比如:你母亲要给你介绍男朋友,是这么来对话的:

女儿:多大年纪了?

母亲:26。

女儿:长的帅不帅?

母亲:挺帅的。

女儿:收入高不?

母亲:不算很高,中等情况。

女儿:是公务员不?

母亲:是,在税务局上班呢。

女儿:那好,我去见见。

于是你在脑袋里面就有了下面这张图

作为女孩的你在决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别:见和不见。 

1.2构建决策树的三个步骤

  1. 特征选择:选取有较强分类能力的特征(定性分析问题还是定量分析问题等等)
  2. 决策树生成
  3. 决策树剪枝(让决策树更加简洁高效,对于一些特征不重要,或根据权值大小,对决策树的分类进行筛选)

决策树API:

  • from sklearn.tree import DecisionTreeClassifier
  • from sklearn.tree import plot_tree

2.ID3决策树 

  1. 掌握信息熵的概念
  2. 掌握条件熵的概念
  3. 掌握ID3决策树构建过程

2.1信息熵

ID3 树是基于信息增益构建的决策树.

定义

  • 熵在信息论中代表随机变量不确定度的度量
  • 熵越大,数据的不确定性度越高
  • 熵越小,数据的不确定性越低

公式:

\large H = -\sum_{i=1}^{k}p_i\log(p_i)

公式的转换,当数据类别只有两类的情况下,公式可以做如下转换:

代码角度理解信息熵的概念

import numpy as np
import matplotlib.pyplot as pltdef entropy(p):return -p*np.log(p)-(1-p)*np.log(1-p)x = np.linspace(0.01,0.99,200)
plt.plot(x,entropy(x))
plt.show()

✒️观察上图可以得出,当我们的系统每一个类别是等概率的时候,系统的信息熵最高,当系统偏向于某一列,相当于系统有了一定程度的确定性,直到系统整体百分之百的都到某一类中,此时信息熵就达到了最低值,即为0。上述结论也可以拓展到多类别的情况。

2.2 信息增益

💡💡上文我们也讲到,决策树构建第一步即特征选择是尤为重要的,每一种特征的重要性怎样体现呢,那就是信息增益。 

2.2.1定义

特征$A$对训练数据集D的信息增益$g(D,A)$,定义为集合$D$的经验熵$H(D)$与特征A给定条件下D的经验熵$H(D|A)$之差。即\large g(D,A)=H(D)-H(D|A)

根据信息增益选择特征方法是:对训练数据集D,计算其每个特征的信息增益,并比较它们的大小,并选择信息增益最大的特征进行划分。表示由于特征$A$而使得对数据D的分类不确定性减少的程度。

2.2.2算法

 设训练数据集为D,$\mid D\mid$表示其样本个数。设有$K$个类$C_k$$k=1,2,\cdots,K$$\mid C_k\mid$为属于类$C_k$的样本个数,$\sum\limits{k=1}^{K}=\mid{D}\mid$。设特征A有$n$个不同取值${a_1, a_2, \cdots,a_n}$,根据特征A的取值将D划分为$n$个子集$D_1, D_2, \cdots,D_n$$\mid D_i\mid$$D_i$样本个数,$\sum\limits{i=1}^n\mid D_i\mid=\mid D\mid$。子集中属于类$C_k$的样本集合为$D{ik}$,即$D{ik}=D_i\bigcap C_k$$\mid D{ik}\mid$$D{ik}$的样本个数。信息增益算法如下:

  • 输入:训练数据集D和特征A;

  • 输出:特征A对训练数据集D的信息增益$g(D,A)$

(1) 计算数据集D的经验熵$H(D)$

$H(D)=-\sum\limits_{k=1}^{K}\frac{\mid C_k\mid}{\mid D\mid}\log_2\frac{\mid C_k\mid}{\mid D\mid}$

(2) 计算特征A对数据集D的经验条件熵$H(D\mid A)$

$H(D\mid A)=\sum\limits{i=1}^{n}\frac{\mid D_i\mid}{\mid D\mid}H(D_i)=-\sum\limits{i=1}^{n}\frac{\mid D_i\mid}{\mid D\mid}\sum\limits{k=1}^{K}\frac{\mid D{ik}\mid}{\mid D_i\mid}\log_2\frac{\mid D_{ik}\mid}{\mid D_i\mid}$

(3) 计算信息增益

$g(D,A)=H(D)-H(D|A)$

💡💡只看公式可能觉得很复杂,下面我们带入一个例子来更好的理解

  下面以常用的贷款申请样本数据表为样本集,通过数学计算来介绍信息增益计算过程。

Step1 计算经验熵

类别一共是两个拒绝/同意,数量分别是6和9,根据熵定义可得:

H(D)=-\frac{9}{15}\log_2\frac{9}{15}-\frac{6}{15}\log_2\frac{6}{15}=0.971

Step2 各特征的条件熵

将各特征分别记为$A_1,A_2,A_3,A_4$ ,分别代表年龄、有无工作、有无房子和信贷情况,那么

Step3 计算增益 

根据计算所得的信息增益,选取最大的$A_3$ 作为根节点的特征。它将训练集$D$ 划分为两个子集$D_1$(取值为“是”)和$D_2$(取值为“否”)。由于$D_1$只有同一类的样本点,所以成为一个叶节点,节点标记为“是”。

对于$D_2$需从特征$A_1,A_2,A_4$中选择新的特征。计算各个特征的信息增益

g(D_2,A_1)=0.918-0.668=0.251\\ g(D_2,A_2)=0.918\\ g(D_2,A_4)=0.474

选择信息增益最大的特征$A_2$作为节点的特征。由于$A_2$有两个可能取值,一个是“是”的子节点,有三个样本,且为同一类,所以是一个叶节点,类标记为“是”;另一个是“否”的子节点,包含6个样本,也属同一类,所以也是一个叶节点,类别标记为“否”。

最终构建的决策树如下:

3.ID3的算法步骤

  1. 计算每个特征的信息增益

  2. 使用信息增益最大的特征将数据集 S 拆分为子集

  3. 使用该特征(信息增益最大的特征)作为决策树的一个节点

  4. 使用剩余特征对子集重复上述(1,2,3)过程

4.小结

  1. 信息熵是一个变量(特征)包含信息多少的度量方式。信息熵的值大,则认为该变量包含的信息量就大

  2. 条件熵用于衡量以某个特征作为条件,对目标值纯度的提升程度

  3. 信息增益用于衡量那个特征更加适合优先分裂

  4. 使用信息增益构建的决策树成为 ID3 决策树


http://www.ppmy.cn/devtools/22472.html

相关文章

打印机-STM32版本 硬件部分

最终PCB EDA工程: 一、确定芯片型号 根据项目需求,梳理需要用到的功能, 电量检测:ADC 按键:IO input外部中断 LED:IO output 温度检测:ADC 电机控制:IO output 打印通讯:SPI …

Python 语音识别系列-实战学习-语音识别特征提取

Python 语音识别系列-实战学习-语音识别特征提取 前言1.预加重、分帧和加窗2.提取特征3.可视化特征4.总结 前言 语音识别特征提取是语音处理中的一个重要环节,其主要任务是将连续的时域语音信号转换为连续的特征向量,以便于后续的语音识别和语音处理任务…

Vision Pro“裸眼上车”,商汤绝影全新舱内3D交互亮相

2023年,Apple Vision Pro的横空出世让人们领略到了3D交互的魅力,商汤绝影通过深厚的技术研发实力和高效的创新迭代效率,带来两大全新座舱3D交互:3D Gaze高精视线交互和3D动态手势交互。 作为全球首创的能够通过视线定位与屏幕图标…

《Fundamentals of Power Electronics》——全桥型隔离降压转换器

以下是关于全桥型隔离降压转换器的相关知识点: 全桥变压器隔离型降压转换器如下图所示。 上图展示了一个具有二次侧绕组中心抽头的版本,该电路常用于产生低输出电压。二次侧绕组的上下两个绕组可以看作是两个单独的绕组,因此可以看成是具有变…

酷开科技生态内容价值+酷开系统的开放性和可塑性,实现品效合一

互联网浪潮之下,电视行业也迎来了新的机遇和挑战,酷开科技坚持以用户为中心,想用户所想,急用户所急,抓核心科技,为消费者提供优质、便捷的产品和服务,切实解决用户电视使用痛点,得到…

照片误删怎么办?华为手机删除的照片如何恢复?

我们在使用华为手机时,可能会因为各种原因不小心删除一些照片。如果这些照片对我们来说很重要,那么恢复它们是非常必要且急迫的。那么华为手机删除的照片如何恢复呢?本文将为您介绍3种恢复华为手机中误删照片的方法。 如何恢复华为手机中被删…

leetcode-有效括号序列-94

题目要求 思路 1.使用栈的先进后出的思路,存储前括号,如果st中有对应的后括号与之匹配就说明没问题 2.有两个特殊情况就是字符串第一个就是后括号,这个情况本身就是不匹配的,还有一种是前面的n个字符串本身是匹配的,这…

k8s Dashboard 运维维护记录

k8s Dashboard 运维维护记录 k8s Dashboard 运维维护记录 Q1:需要使用firefox浏览器访问 提示了证书错误NET::ERR_CERT_INVALID,原因是由于物理机的浏览器证书不可用 需要注意的是,若提示“连接不安全”的警告时,点击“高级”…

go引入自建包名报错 package XXX is not in std和goland设置GO111MODULE提示冲突

首先在引入自建包的时候报错 查找网上的解决方法: 1、goland取消勾选Enable Go modules integration 2、set GO111MODULEoff 但是都没解决,而且更奇怪的是,我在cmd里面查看go env就显示set GO111MODULEoff 但是在goland里面的终端输入 go…

Golang实现一个批量自动化执行树莓派指令的软件(9)辅助模块-调用Ping指令判定在线

简介 基于 Golang实现一个批量自动化执行树莓派指令的软件(8)辅助模块-远程IP端口是否开放连接(TCP) 和 Golang实现一个批量自动化执行树莓派指令的软件(7)辅助模块-本地活动网络, 这两篇, 再新增使用系统ping指令判定设备是否在线。 环境描述 运行环境:…

机器学习:基于Sklearn、XGBoost框架,使用逻辑回归、支持向量机和XGBClassifier预测帕金森病

前言 系列专栏:机器学习:高级应用与实践【项目实战100】【2024】✨︎ 在本专栏中不仅包含一些适合初学者的最新机器学习项目,每个项目都处理一组不同的问题,包括监督和无监督学习、分类、回归和聚类,而且涉及创建深度学…

flutter知识点-Focus

在Flutter中,Focus是一个重要的概念,用于管理用户输入焦点,特别是在处理文本输入、按钮点击等交互场景时。以下是一些关键概念和组件,帮助理解Flutter中的焦点管理: FocusNode: FocusNode是焦点管理的核心类&#xff0…

【氮化镓】GaN 器件的高温运行

《High Temperature Operation of E-Mode and D-Mode AlGaN/GaN MIS-HEMTs With Recessed Gates》,由HANWOOL LEE, HOJOON RYU, JUNZHE KANG, 和 WENJUAN ZHU (IEEE高级会员) 四位作者共同撰写,发表在《IEEE Journal of the Electron Devices Society》上…

机器学习:基于Sklearn、XGBoost框架,使用XGBClassifier、支持向量分类器和决策树分类器预测乳腺癌是良性还是恶性

前言 系列专栏:机器学习:高级应用与实践【项目实战100】【2024】✨︎ 在本专栏中不仅包含一些适合初学者的最新机器学习项目,每个项目都处理一组不同的问题,包括监督和无监督学习、分类、回归和聚类,而且涉及创建深度学…

工业异常检测

工业异常检测在业界和学界都一直是热门,近期其更是迎来了全新突破:与大模型相结合!让异常检测变得更快更准更简单! 比如模型AnomalyGPT,它克服了以往的局限,能够让大模型充分理解工业场景图像,判…

SpringMVC中常见注解和用法

一.建立连接 RequestMapping 来实现 URL 路由映射。RequestMapping是Spring Web MVC 应⽤程序中最常被⽤到的注解之⼀,它是⽤来注册接⼝的路由映射的,表⽰服务收到请求时,路径为 /sayHi 的请求就会调⽤ sayHi 这个⽅法的代码。 路由映射: 当…

python facebook business SDK campaign 广告复制方法

facebook广告复制调试了一天,特此记录,广告复制分为两个步骤: 第一步:使用campaign.create_copy()复制广告系列。 第二步:复制源广告广告集(ad_set)如果广告集需要修改,使用api_upd…

MCU自动测量单元:自动化数据采集的未来

随着科技的飞速发展,自动化技术在各个领域中的应用日益广泛。其中,MCU(微控制器)自动测量单元以其高效、精准的特性,成为自动化数据采集领域的佼佼者,引领着未来数据采集技术的革新。本文将深入探讨MCU自动测量单元的原理、优势以…

千帆起航、芯聚未来——鸿蒙与集成电路产教融合人育人研讨活动成功举办

4月24日,“千帆起航、芯聚未来”——鸿蒙与集成电路产教融合人育人研讨活动在上海顺利举行,本次活动由华为云计算技术有限公司、上海恒驰信息系统有限公司、上海荟诚信息系统有限公司和上海青软晶睿微电子科技有限公司联合举办,汇聚了来自教育…

BERT一个蛋白质-季军-英特尔创新大师杯冷冻电镜蛋白质结构建模大赛-paipai

关联比赛: “创新大师杯”冷冻电镜蛋白质结构建模大赛 解决方案 团队介绍 paipai队、取自 PAIN AI,核心成员如我本人IvanaXu(IvanaXu GitHub),从事于金融科技业,面向银行信用贷款的风控、运营场景。但我们团队先后打过很多比赛&#xf…