机器学习-决策树算法

前言

本篇介绍决策树与随机森林的内容,先完成了决策树的部分。

在这里插入图片描述

决策树

决策树(Decision Tree)是一种有监督学习的方法,可以同时解决分类和回归问题,它能够从一系列有特征和标签的数据中总结出决策规则,并用树状图的结构来呈现这些规则,以解决问题。

决策树算法容易理解,适用各种数据,在解决各种问题时都有良好表现,尤其是以树模型为核心的各种集成算法,在各个行业领域都有广泛的应用。

举例分析

我们来简单了解一下决策树是如何工作的。决策树算法的本质是一种树结构,我们只需要问一系列问题就可以对数据进行分类了。比如说,来看看下面的一组数据集,这是一些列已知物种以及所属类别的数据:

在这里插入图片描述

我们现在的目标是,将动物们分为哺乳类和非哺乳类。那根据已经收集到的数据,决策树算法为我们算出了下面的这棵决策树:

在这里插入图片描述

这时,假如我们现在发现了一种新物种,它是冷血动物,体表带鳞片,并且不是胎生,我们就可以通过这棵决策树来判断它的所属类别。

可以看出,在这个决策过程中,我们一直在对记录的特征进行提问。最初的问题所在的地方叫做根结点,在得到结论前的每一个问题都是中间结点,而得到的每一个结论(动物的类别)都叫做叶子结点

定义

通过上述例子,我们可以总结,决策树算法的本质就是树形结构,我们可以通过一些精心设计的问题,就可以对数据进行分类(训练),一个决策树建立好之后,就可以基于该树的相关分支得到不同分类的预测结果。

在这里插入图片描述

  • 树的根节点和中间节点对应的是某一种类型特征,那么这些节点(特征)自上而下的重要性应该是由大到小进行排列的。而所谓重要性并没有一定的标准,都是根据问题而决定的。

原理

决策树算法的核心是要解决两个问题:

1.如何从数据表中找出最佳节点或最佳分枝?

2.如何让决策树停止生长,防止过拟合?

  • 决策树是基于训练集数据构建出来的,如果树长的越大分支越细致,则对训练数据的描述越清楚,但是不一定会很好的作用到测试数据中。

构建决策树

那如何根据已有的数据集来建立有效的决策树?原则上讲,任意一个数据集上的所有特征都可以被拿来分枝,特征上的任意节点又可以自由组合,所以一个数据集上可以发展出非常非常多棵决策树,其数量可达指数级。但是在这些树中,总有那么一棵树比其他的树分类效力都好,那样的树叫做”全局最优树“。

  • 全局最优:经过某种组合形成的决策树,整体来说分类效果为最好的模型
  • 局部最优:每一次分枝的时候都向着更好的分类效果分枝,但无法确认如此生成的树在全局上是否是最优的

要在这么多棵决策树中去一次性找到分类效果最佳的那一棵是不可能的,如果通过排列组合来进行筛选,计算量过于大而且低效,因此我们不会这样做。相对的,机器学习研究者们开发了一些有效的算法,能够在合理的时间内构造出具有一定准确率的次最优决策树,接下来要介绍的知识了。

不纯度

决策树需要找出最佳节点和最佳的分枝方法,对分类树来说,衡量这个“最佳”的指标叫做“不纯度”。通常来说,不纯度越低,决策树对训练集的拟合越好。不纯度基于节点来计算,树中的每个节点都会有一个不纯度,并且子节点的不纯度一定是低于父节点的。

我们一般采用熵和基尼系数来衡量不纯度。

熵(Entropy) 是对于随机变量不确定性的度量。熵值越小,对于数据分类的越干净,当然有利于后续的预测等其他工作的进行。对于决策树的某个结点而言,它在对样本数据进行分类后,我们希望分类后的结果能使得整个样本集在各自的类别中尽可能有序,也就是希望某个特征在被用于分类后,能最大程度地降低样本数据的熵。

计算公式如下:
H ( X ) = − ∑ P ( x ) l o g 2 P ( x ) H(X) = - ∑ P(x) log2 P(x) H(X)=P(x)log2P(x)
其中,X 是一个离散随机变量,P(X) 是 X 取某个值的概率。

在这里插入图片描述

根据我们总是要选取最优的特征,以及熵的定义,在构建决策树时我们可采用一种很简单的思路来进行熵减:每当要选出一个内部结点时,考虑样本中的所有尚未被使用的特征,并基于该特征计算出来的熵对样本数据进行划分。

条件熵

条件熵就是含有条件概率时的熵,它描述的是在已知随机变量X的条件下随机变量Y的不确定性。假设有两个随机变量X和Y,Y的条件熵H(Y|X)定义为X给定的条件下Y的平均熵,可以通过以下公式计算:
H ( Y ∣ X ) = ∑ P ( x ) H ( Y ∣ X = x ) H(Y|X) = ∑ P(x) H(Y|X=x) H(YX)=P(x)H(YX=x)

其中,P(x)是随机变量X取某个值的概率,H(Y|X=x)是在X取某个值的条件下Y的熵。

条件熵H(Y|X)可以理解为在已知随机变量X的值的情况下,随机变量Y的不确定性。

如果Y的值完全由X的值决定,那么条件熵H(Y|X)就为0,表示在已知X的值的情况下,Y的值没有不确定性。如果Y的值与X的值无关,那么条件熵H(Y|X)就等于Y的原始熵H(Y),表示在已知X的值的情况下,Y的不确定性没有任何减少。

信息增益

是决策树算法中用来选择分割属性的一种度量方式。它表示的是通过某个特征而得到的“信息”的增加量,或者说,不确定性的减少量。具体来说,信息增益是数据集的原始熵与给定某个属性后的条件熵之差。如果一个属性能够使得信息增益最大,那么就选择这个属性进行分割。

让我们通过一个简单的例子来理解信息增益:

假设我们有一个数据集,包含了天气(晴、阴、雨)、温度(高、中、低)和是否打篮球(是、否)三个属性,其中前两个为特征。我们想要构建一个决策树模型,来预测在不同的天气和温度条件下,是否会打篮球。

  • 首先,我们计算数据集的原始熵。假设数据集中有10个样本,其中5个样本是“打篮球”,5个样本是“不打篮球”,那么原始熵为1(因为两类样本的数量相等,所以此时熵最大,为1)。

  • 然后,我们计算给定“天气”属性后的条件熵。假设在“晴”天气下,有3个样本是“打篮球”,2个样本是“不打篮球”;在“阴”天气下,有1个样本是“打篮球”,2个样本是“不打篮球”;在“雨”天气下,有1个样本是“打篮球”,1个样本是“不打篮球”。那么,给定“天气”属性后的条件熵为0.97。因此,天气属性的信息增益为原始熵与条件熵之差,即信息增益为:1 - 0.97 = 0.03。

  • 同样,我们可以计算出温度属性的信息增益。假设温度属性的信息增益为0.01。

  • 由于天气属性的信息增益大于温度属性的信息增益,因此我们选择天气属性进行分割。

这就是信息增益的基本概念和计算方法。在实际应用中,我们通常会计算所有属性的信息增益,然后选择信息增益最大的属性进行分割。

上述过程也就是ID3算法的过程。

基尼系数

基尼系数(Gini Index)也叫基尼不纯度(Gini Impurity)是一种用来度量数据集的不纯度的指标。基尼系数的值越小,数据集的纯度越高。

基尼系数的计算公式如下:
G i n i ( D ) = 1 − ∑ ( P i ) 2 Gini(D) = 1 - ∑ (P_i)^2 Gini(D)=1(Pi)2
其中,D是数据集,Pi 是第 i 类样本在数据集D中出现的概率。

基尼系数的值域为[0, 1]。当数据集D中的所有样本都属于同一类时,基尼系数为0,表示数据集D的纯度最高;当数据集D中的样本均匀分布在各个类别中时,基尼系数为1-1/k,其中k是类别的数量,此时数据集D的纯度最低。


算法

ID3算法

ID3(Iterative Dichotomiser 3)由Ross Quinlan在1986年提出。这种算法使用信息增益作为属性选择的度量标准,选择信息增益最大的属性进行分割。ID3算法可以处理多值属性,但不能直接处理数值属性和缺失值,也没有剪枝操作,因此容易产生过拟合。

  • 计算信息增益:首先,计算数据集D的熵H(D),然后对每一个特征A,计算A对D的信息增益G(D,A)。信息增益定义为数据集D的熵与给定属性A值后的条件熵之差,即G(D,A)=H(D)-H(D|A)。
  • 选择信息增益最大的属性:在所有特征中,选择信息增益最大的特征A。
  • 分割数据集:根据特征A的每一个可能值ai,将D分割为若干个非空子集Di,每个子集Di包含D中所有在特征A上取值为ai的样本,然后对每个子集Di递归地应用上述过程。
  • 生成决策树:将特征A作为测试条件,生成一个分支节点,对应于A的每一个可能值,从该节点引出一个分支,下接对应的子集Di的决策子树。

需要注意的是,ID3算法没有剪枝操作,因此生成的决策树可能会过于复杂,容易产生过拟合。此外,ID3算法不能直接处理数值属性和缺失值,这在实际应用中可能会带来一些问题。

C4.5算法

C4.5算法由Ross Quinlan在1993年提出,是ID3算法的改进版。C4.5算法引入了信息增益率作为属性选择的度量标准,以解决ID3算法对取值数目较多的属性有所偏好的问题。此外,C4.5算法还可以处理数值属性和缺失值,通过引入置信度因子进行剪枝,以防止过拟合。

  • 计算信息增益率:首先,计算数据集D的熵H(D),然后对每一个特征A,计算A对D的信息增益G(D,A)和信息增益率GR(D,A)。信息增益率定义为信息增益与属性A的熵之比,即:

G R ( D , A ) = G ( D , A ) / H A ( D ) GR(D,A)=G(D,A)/H_A(D) GR(D,A)=G(D,A)/HA(D)

  • 选择信息增益率最大的属性:在所有属性中,选择信息增益率最大的特征A。
  • 分割数据集:根据特征A的每一个可能值ai,将D分割为若干个非空子集Di,每个子集Di包含D中所有在特征A上取值为ai的样本,然后对每个子集Di递归地应用上述过程。
  • 生成决策树:将特征A作为测试条件,生成一个分支节点,对应于A的每一个可能值,从该节点引出一个分支,下接对应的子集Di的决策子树。
  • 剪枝:C4.5算法引入了置信度因子进行剪枝,以防止过拟合。具体来说,C4.5算法会计算每个节点的错误率,然后比较剪枝前后的错误率,如果剪枝后的错误率没有显著增加,那么就进行剪枝。

需要注意的是,C4.5算法可以处理数值属性和缺失值。对于数值属性,C4.5算法会找出一个最佳的分割点,将属性的值分为两个区间;对于缺失值,C4.5算法会根据数据的分布,将缺失值分配到各个子节点。

CART算法

CART(Classification and Regression Tree)算法是既可以用于分类也可以用于回归的决策树学习算法,由Breiman等人在1984年提出。CART算法使用基尼指数作为属性选择的度量标准,选择基尼指数最小的属性进行分割。CART算法生成的决策树是二叉树,可以处理数值属性和缺失值,通过设定复杂度参数进行剪枝,以防止过拟合。

  • 计算基尼指数:首先,计算数据集D的基尼指数G(D),然后对每一个特征A,计算A对D的基尼指数G(D,A)。
  • 选择基尼指数最小的属性:在所有特征中,选择基尼指数最小的特征A。
  • 分割数据集:根据特征A的每一个可能值ai,将D分割为两个子集Di和Dj,Di包含D中所有在属性Ag上取值小于等于ai的样本,Dj包含D中所有在特征A上取值大于ai的样本,然后对每个子集Di和Dj递归地应用上述过程。
  • 生成决策树:将属性Ag和分割点ai作为测试条件,生成一个二叉节点,左分支下接对应的子集Di的决策子树,右分支下接对应的子集Dj的决策子树。
  • 剪枝:CART算法通过设定复杂度参数进行剪枝,以防止过拟合。具体来说,CART算法会计算每个节点的复杂度代价,然后比较剪枝前后的复杂度代价,如果剪枝后的复杂度代价没有显著增加,那么就进行剪枝。

CART算法可以处理数值属性和缺失值*。对于数值属性,CART算法会找出一个最佳的分割点,将属性的值分为两个区间;对于缺失值,CART算法会根据数据的分布,将缺失值分配到各个子节点。


运用实现

决策数的调用包含在skleran.tree中:

在这里插入图片描述

重要参数

criterion

这个参数用来决定不纯度的计算方法的。

sklearn提供了两种选择:

输入”entropy“,使用信息熵(Entropy)

输入”gini“,使用基尼系数(Gini Impurity)

random_state & splitter

random_state随机模式参数,默认None,在高维度时随机性会表现更明显,低维度的数据(比如鸢尾花数据集),随机性几乎不会显现。输入任意整数,会一直长出同一棵树,让模型稳定下来。

splitter 也是用来控制决策树中的随机选项的,有两种输入值

输入”best",决策树在分枝时虽然随机,但是还是会优先选择更重要的特征进行分枝。

输入“random",决策树在分枝时会更加随机,树会因为含有更多的不必要信息而更深更大。这也是防止过拟合的一种方式。当然,我们经常会使用剪枝参数来防止过拟合。

剪枝参数

剪枝策略对决策树的影响巨大,正确的剪枝策略是优化决策树算法的核心。

sklearn为我们提供了不同的剪枝策略:

max_depth

限制树的最大深度,超过设定深度的树枝全部剪掉,这是用得最广泛的剪枝参数,在高维度低样本量时非常有效。决策树多生长一层,对样本量的需求会增加一倍,所以限制树深度能够有效地限制过拟合。在集成算法中也非常实用。实际使用时,一般从=3开始尝试,看看拟合的效果再决定是否增加设定深度。

min_samples_leaf

限定一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样本,否则分枝就不会发生 。一般搭配max_depth使用,可以让模型变得更加平滑。这个参数的数量设置得太小会引起过拟合,设置得太大就会阻止模型学习数据。一般来说,建议从=5开始使用。如果叶节点中含有的样本量变化很大,建议输入浮点数作为样本量的百分比来使用。

max_features限制分枝时考虑的特征个数,超过限制个数的特征都会被舍弃。

max_features是用来限制高维度数据的过拟合的剪枝参数,但其方法比较暴力,是直接限制可以使用的特征数量而强行使决策树停下的参数,在不知道决策树中的各个特征的重要性的情况下,强行设定这个参数可能会导致模型学习不足。

min_samples_split

min_impurity_decrease限制信息增益的大小,信息增益小于设定数值的分枝不会发生。

重要的属性和接口

决策树来说,最重要的属性是feature_importances_,能够查看各个特征对模型的重要性。

除了这两个接口之外,决策树最常用的接口还有apply和predict。apply中输入测试集返回每个测试样本所在的叶子节点的索引,predict输入测试集返回每个测试样本的标签。

可视化

想要做好决策树的最后一步就是将树给画出来,但是因为侧重点不同,暂时就先不介绍。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

WPF中MVVM架构学习笔记

MVVM架构是一种基于数据驱动的软件开发架构,它将数据模型(Model)、视图(View)和视图模型(ViewModel)三者进行分离,使得开发者可以更加专注于各自领域的开发。其中,Model负…

系统架构师考试(十)

SaaS为在线客服 PaaS为二次开发,比如低代码平台 IaaS 硬件开发 B 是基础设施作为服务 软件架构的概念 架构风格 数据流风格 网络报文是在计算机网络中通过网络传输的数据单元,它是网络通信的基本单位。网络报文包含了发送方和接收方之间传输的数据&…

蛮力法0/1背包问题实验

实验项目1 蛮力法 实验题目 使用蛮力法解决0/1背包问题。 ​ 问题描述:给定n个重量(weight)为{w1, w2, … ,wn}、价值(key)为{v1, v2, … ,vn}的物品和一个**容量为C(contain)**的背包,求这些物品中的一个最有价值的子集,且要能够装到背包中…

第十三期Big Demo Day亮点项目:CCarbon重塑碳交易生态,助力全球绿色发展

第十三期Big Demo Day活动即将于2024年5月28日在香港数码港的CyberArena隆重举行。我们荣幸地宣布,利用区块链技术优化全球碳交易CCarbon项目将亮相,参与精彩的项目路演。本次活动由ZeeprLabs、BiKing Exchange、Gather冠名赞助,Central Rese…

【教学类-56-03】数感训练——数字03(寻找自己的学号数字,1号-31号,出现15-20次)

背景需求: 在实际操作中,孩子们把数字当做了自己的学好,这个提示老师可以给每位孩子做一份“学号数感训练 【教学类-56-02】数感训练——数字02(控制指定数字出现的数量)-CSDN博客文章浏览阅读341次,点赞…

【Linux学习】深入探索进程等待与进程退出码和退出信号

文章目录 退出码return退出 进程的等待进程等待的方法 退出码 main函数的返回值:进程的退出码。 一般为0表示成功,非0表示失败。 每一个非0退出码都表示一个失败的原因; echo $?命令 作用:查看进程退出码。&#xf…

学AI绘图【300集SD新课】--Stable Diffusion教程

学AI绘图需要以下步骤: 明确目标和需求:首先明确设计图的目的,是用于展示算法流程、模型结构还是其他目的。选择合适的工具:根据需求选择合适的绘图工具,如Visio、PowerPoint、Adobe Illustrator等。绘制草图&#xf…

jmeter之HTTP请求和查看结果树

一、HTTP请求作用: 可以发送post或get请求等请求可以向服务器发送参数或消息体数据可以进行文件上传 HTTP请求:是线程组内的取样器最常用的的一个原件 二、查看界面 添加一个HTTP请求:选择线程组–添加–取样器–HTTP请求 默认界面 名称和…

Steam游戏被攻击怎么办,如何针对性的做好防护措施

在现代网络环境中,在线游戏经常成为各种网络攻击的目标,尤其是DDoS攻击。这类攻击不仅会导致游戏服务器瘫痪,还会影响玩家的游戏体验,损害游戏开发商的声誉和经济利益。为了应对这些威胁,使用专门的防护措施是必要的。…

Scrapy框架简单介绍及Scrapy项目编写详细步骤

引言 Scrapy是一个用Python编写的开源、功能强大的网络爬虫框架,专为网页抓取和数据提取设计。它允许开发者高效地从网站上抓取所需的数据,并通过一系列可扩展和可配置的组件来处理这些数据。Scrapy框架的核心组成部分包括: Scrapy Engine&…

rclone迁移对象存储之间的数据

1 概述 rclone是一款文件复制工具,既可以用于在linux主机之间复制文件,也可以在对象存储之间复制文件。 rclone的官网为: https://rclone.orgrlcone关于对象存储的官方文档为: https://rclone.org/s32 安装 2.1 yum安装 yum …

centos7.9用docker运行一个nginx容器

首先你的linux 系统里面已经安装好了docker,docker的安装教程看这个 1,下载nginx镜像 有很多文章会把镜像下载说成是拉取镜像, 我觉得就是下载的意思啊,搞不懂为什么要说拉取? docker pull nginx 下载最新版 Nginx …

深度学习之基于Unet的新冠肺炎等级分割分类系统

欢迎大家点赞、收藏、关注、评论啦 ,由于篇幅有限,只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 一、项目背景与意义 近年来,新冠肺炎(COVID-19)疫情给全球公共卫生安全带来了极…

操作系统基本原理

一、基本概念 二、进程管理 三、存储管理 四、文件管理 五、设备管理 六、微内核操作系统 操作系统的概念(定义) 操作系统(Operating System,OS)是指控制和管理整个计算机系统的硬件和软件资源,并合理地组织调度计算机的工作和资源的分,以…

光耦合器的特性和应用概述

光耦合器又称光电耦合器,是现代电子学中必不可少的元件,确保隔离电路之间安全有效的信号传输。本文探讨了光耦合器的特性及其多样化应用,强调了它们在各种电子系统中的关键作用。 什么是光耦合器? 光耦合器是一种设计用于利用光传…

第十六节:带你梳理Vue2: 生命周期与钩子函数

前沿: 通过前面几节的学习,我们已经对vue有了初步的了解,大致了解了vue可以帮我们干什么, 那么接下来我们就来看看vue的生命周期和它常用的钩子函数, 1. 理解生命周期的含义 生命周期:就是一个组件从实例化创建并添加到DOM树开…

【全开源】招聘求职小程序系统源码(ThinkPHP+原生微信小程序)

基于ThinkPHP和原生微信小程序开发的招聘平台系统,包含微信小程序求职者端、微信小程序企业招聘端、PC企业招聘端、PC管理平台端 构建高效人才交流平台 一、引言:招聘求职市场的数字化趋势 在数字化时代,招聘求职市场也迎来了巨大的变革。…

Edge浏览器:重新定义现代网页浏览

引言 - Edge的起源与重生 Edge浏览器,作为Microsoft Windows标志性的互联网窗口,源起于1995年的Internet Explorer。在网络发展的浪潮中,IE曾是无可争议的霸主,但随着技术革新与用户需求的演变,它面临的竞争日益激烈。…

Linux学习笔记:线程

Linux中的线程 什么是线程线程的使用原生线程库创建线程线程的id线程退出等待线程join分离线程取消一个线程线程的局部存储在c程序中使用线程使用c自己封装一个简易的线程库 线程互斥(多线程)导致共享数据出错的原因互斥锁关键函数pthread_mutex_t :创建一个锁pthread_mutex_in…

租赁系统|北京租赁系统|租赁软件开发流程

在数字化时代的浪潮下,小程序成为了各行各业争相探索的新领域。租赁行业亦不例外,租赁小程序的开发不仅提升了用户体验,更为商家带来了更多商业机会。本文将详细解析租赁小程序的开发流程,为有志于进军小程序领域的租赁行业从业者…