jjzjj

一文搞懂决策树！ #51CTO博主之星评选#

51Ann 2023-03-28 原文
分类决策树模型是一种描述对实例进行分类的树形结构。 决策树由结点和有向边组成。^[《统计学习方法》李航]

结点有两种类型：

  • 内部结点（internal node）：表示一个特征或属性
  • 叶结点（leaf node）：叶结点表示一个类
顾名思义，决策树说白了就是使用树结构进行决策。让我们借助:watermelon:书^[《机器学习》周志华]里的一张图来看一下子。

怎么判断一个西瓜是不是好瓜呢？

先看他的色泽是不是已经青绿色了，如果是，继续往下看；再看他gen蒂是否蜷缩，如果是就继续往下看；再敲一敲（签订契约，不是）听声音，如果是浊响，那他就是一个好瓜:watermelon:。

画决策树谁都会画，比如给你一串数据：

Refund Marital Status Income Cheat
Yes Single 125K No
No Married 100K No
No Single 70K No
Yes Married 120K No
No Divorced 95K Yes
No Married 60K No
Yes Divorced 220K No
No Single 85K Yes
No Married 75K No
No Single 90K Yes
你搞个决策树出来：

你可以看到上边两个决策树都能对给出的数据进行正确分类，那哪棵树更好呢？

学过算法的我们应该知道在查找过程中，不同结构的二叉树会对查找效率造成影响，同理，决策树结构不同也会影响判断的质量。

决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个都没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。

决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。

由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。 决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

接下来我们从三个步骤分别进行详细介绍如何搞一颗好用的决策树。

1 特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。

同一组数据建立决策树，究竟选择哪个特征更好些？这就要求确定选择特征的准则。 直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。

如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。这样的特征一般来说丢弃也对整体结果没有太大的影响。

特征选择的准则是信息增益或信息增益比。

2 决策树生成

生成决策树的主要是两个算法，ID3和C4.5，前者是用信息增益生成决策树，后者是用信息增益比生成决策树。

2.1 预备知识

在知道怎么算信息增益之前我们先看一下需要的一些基础知识。

学过高中化学的应该都知道熵这个概念，熵的本质是一个系统“内在的混乱程度”。它在控制论、概率论、数论、天体物理、生命科学等领域都有重要应用，在不同的学科中也有引申出的更为具体的定义。

在信息论与概率统计中，熵是表示随机变量不确定性的度量。其实说白了就是越乱熵越高，不确定性越大熵越搞。

设 $X$ 是 一个取有限个值的离散随机变量, 其概率分布为 $$ P\left(X=x_{i}\right)=p_{i}= \frac{n_i}{n_{total}}, \quad i=1,2, \cdots, n $$ 则随机变量 $X$ 的熵定义为 $$ H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i} $$

从这个定义中我们看出，$X$的熵和$X$的取值没什么关系，只和X的分布有关。

设有随机变量 $(X, Y)$, 其联合概率分布为 $$ P\left(X=x_{i}, Y=y_{j}\right)=p_{i j}, \quad i=1,2, \cdots, n ; \quad j=1,2, \cdots, m $$ 条件熵 $H(Y \mid X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。随机变量 $X$ 给定的条件下随机变量 $Y$ 的条件熵 $H(Y \mid X)$, 定义为 $X$ 给 定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望 $$ H(Y \mid X)=\sum_{i=1}^{n} p_{i} H\left(Y \mid X=x_{i}\right) $$ 这里, $p_{i}=P\left(X=x_{i}\right), i=1,2, \cdots, n$ 。

熵 $H(Y)$ 与条件熵 $H(Y \mid X)$ 之差称为互信息 。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

==信息增益表示== 得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。

对于一个数据集$D = {(x_i,y_i),i = 1,2,...,k}$

balabala…… ?正常的一个教程，到这里就会摆出一个数据集，然后开始各种符号写公式，不同的书他用的符号还不一样，就比如我看到西瓜书、统计分析方法跟我们老师上课讲的用的就是三套不同的符号，但是他们讲的都是一样的东西。所以在这里我就先不列那些乱七八糟的公式，直接举个例子来看一看。当然了公式也不能不讲，那我们根据数据讲完之后再讲一下计算公式。

我们还是要用到西瓜书里的数据集。

比如:watermelon:数据集：

现在我们以色泽为例对其进行计算：

2.2 计算信息增益

因为我们是要对比不同特征的分类效果，所以信息增益是对每一个特征进行计算的。

因为我们是要确定一个瓜是不是好瓜，所以我们要首先对是否是好瓜进行计算，对于y只有两个分类：是或者否。

$n_是 = 8 \quad n_否 = 9 \quad n_{total} = 17$

获得类别$y$的先验概率：

$p_是 = \frac{8}{17}\quad p_否 = \frac{9}{17}$

计算的熵：

$E(D) = -(p_{是} \log p_{是}+ p_{否} \log p_{否}) = 0.998$

色泽一共被分为三类：乌黑、青绿、浅白。

$n_{乌黑} = 6 \quad n_{青绿} = 6 \quad n_{浅白} = 5$

$p_{乌黑} = \frac{6}{17} \quad p_{青绿} = \frac{6}{17} \quad p_{浅白} = \frac{5}{17}$

因为这一步是要计算条件概率，就是说在这三个条件下的分类情况：

$n_{乌黑_是} = 4 \quad n_{乌黑_否} = 2$

$n_{青绿_是} = 3 \quad n_{青绿_否} = 3$

$n_{浅白_是} = 1 \quad n_{浅白_否} = 4$

$p_{乌黑_是} = \frac{4}{6} \quad p_{乌黑_否} = \frac{2}{6}$

$p_{青绿_是} = \frac{3}{6} \quad p_{青绿_否} = \frac{3}{6}$

$p_{浅白_是} = \frac{1}{5} \quad p_{浅白_否} = \frac{4}{5}$

然后我们计算色泽的条件熵：

$E_{乌黑} = -(p_{乌黑_是} \log p_{乌黑_是}+p_{乌黑_否} \log p_{乌黑_否}) = 0.918$

$E_{青绿} = -(p_{青绿_是} \log p_{青绿_是}+p_{青绿_否} \log p_{青绿_否}) = 1.000$

$E_{浅白} = -(p_{浅白_是} \log p_{浅白_是}+p_{浅白_否} \log p_{浅白_否}) = 0.722$

$E_{色泽} = p_{乌黑}E_{乌黑} + p_{青绿}E_{青绿} + p_{浅白}E_{浅白} = 0.889$

最后得到信息增益：

$Gain_{色泽} = E(D)-E_{色泽} = 0.998-0.889 = 0.109$

2.3 信息增益比

计算信息增益比顾名思义就是由信息增益得到的一个概率值。

其实就是用信息增益除以一个有关于某个特征值的熵，还是用色泽来说：

$H_{色泽} = -(p_{乌黑} \log p_{乌黑}+p_{青绿} \log p_{青绿}+p_{浅白} \log p_{浅白}) = 1.580$

$GainRatio_{色泽} = \frac{Gain_{色泽}}{H_{色泽}} = 0.069$

2.4 公式总结

$D = {(x_i,y_i),i = 1,2,...,k}$

对于这个数据集我已经将这些符号对应什么都标注出来了。

其分类特征为$x$，决策结果为$y$。

分类特征$x$共有$s$个：$x = {x^1,x^2,...,x^s}$

某一特征有$n$中分类：$x^i = {f_1,f_2,...,f_n}$

决策的结果有$m$类：$y={l_1,l_2,...,l_m}$

  • 首先要求整个数据集决策的熵：
    • $y$各分类的先验概率： $p_{i} = |l_i| \div k, \quad i=1,2,...,m$
    • 熵： $E(D) = -\sum_{i=0}^m p_i\log_2 p_i$
  • 求F特征的条件熵：
    • $F$特征被分为$n$类，要求出单独的先验概率： $p_i = |f_i| \div k, \quad i=1,2,...,n$
    • 求$F$特征在$y$各个分类下的概率： $p_{ij} = f_{ij} \div |f_i|, \quad i=1,2,...,n,\quad j=1,2,...,m$
    • 求各个分类的熵： $E(F){i} = -\sum{j=0}^m p_{ij}\log_2 p_{ij} , \quad i=1,2,...,n$
    • 求$F$特征的条件熵： $E(F) = -\sum_{i=0}^n p_iE(F)_i$
  • 最后求得某特征$F$的信息增益： $Gain(F,D) = E(D)-E(F)$
  • 某一特征$F$的信息增益比： $H(F) = -\sum_{j=0}^n p_{i}\log_2 p_{i}$ $GainRatio = Gain(F,D) \div H(F)$

2.5 决策树分类算法

决策树分类算法有很多种，比如：

  • ID3 [Quinlan,1986]
  • C4.5 [Quinlan,1993]
  • CART [Breiman el all, 1984]
ID3算法是通过选择具有最高信息增益的属性作为数据集的划分，从而可创建决策树中的一个结点，根据该属性的不同取值可形成该结点的不同分枝。再对各分枝中的数据子集进行递归划分，直至形成叶结点或者某分枝上的所有数据不属于同一类别，但又没有剩余的属性可以进一步划分为止。

优点：

  • ID3算法通常只需要测试一部分属性就可完成对训练数据集的分类。
  • 从ID3算法构建的决策树中，很容易获得相应的决策规则。
缺点：

  • D3算法在选择根节点和内部结点的属性时，使用信息增益作为评价标准。信息增益更倾向于选择取值种类较多的属性进行划分，而不一定是最优属性进行划分。
  • ID3算法只能对属性值为离散型的数据集进行划分（构建决策树），不能处理属性值为连续型的数据集。
C4.5算法使用信息增益比来确定分枝属性，能够克服ID3算法使用信息增益时偏向于取值类型较多属性的不足。

C4.5算法既可以处理离散型描述属性，也可以处理连续型描述属性。

  • 当处理离散型属性时，C4.5算法与ID3算法相同；
  • 当处理连续型属性时，C4.5算法需要先将连续型属性转换成离散型属性。
至于CART算法，这个内容好长，日后我单独开一篇文章填坑。

决策树修剪

决策树会出现的问题： 由于数据中的噪声和孤立点，许多分枝反映的是训练数据中的异常，造成对新样本的判断不准确。

两种剪枝策略：

  • 先剪枝：通过提前停止树的构造——如果在一个结点划分样本将导致低于预定义阈值的分裂（e.g. 使用信息增益度量）； 但是，选择一个合适的阈值通常是很困难的。
  • 后剪枝：由“完全生长”的树剪去分枝——对于树中的每个非叶结点，计算该结点上的子树被剪枝可能出现的期望错误率。 使用一个独立的测试集来评估每棵树的准确率， 就能得到具有最小期望错误率的决策树。
一文之星浅白tdstrong决策树信息增益数据集机器学习深度学习人工智能yyds干货盘点

有关一文搞懂决策树！ #51CTO博主之星评选#的更多相关文章

  1. C51单片机——实现用独立按键控制LED亮灭（调用函数篇） - 2

    说在前面这部分我本来是合为一篇来写的，因为目的是一样的，都是通过独立按键来控制LED闪灭本质上是起到开关的作用，即调用函数和中断函数。但是写一篇太累了，我还是决定分为两篇写，这篇是调用函数篇。在本篇中你主要看到这些东西！！！1.调用函数的方法（主要讲语法和格式）2.独立按键如何控制LED亮灭3.程序中的一些细节（软件消抖等）1.调用函数的方法思路还是比较清晰地，就是通过按下按键来控制LED闪灭，即每按下一次，LED取反一次。重要的是，把按键与LED联系在一起。我打算用K1来作为开关，看了一下开发板原理图，K1连接的是单片机的P31口，当按下K1时，P31是与GND相连的，也就是说，当我按下去时

  2. 一文解决关于VLAN所有的疑惑 - 2

    一文解决关于VLAN所有的疑惑VLAN基本概念为什么需要VLAN？怎么在交换机上划分VLAN，VLAN的工作原理有了子网，已经隔离了广播，还需要VLAN干啥？只进行子网划分，不进行VLAN划分VLAN划分与子网划分附加VLAN信息的方法VLAN划分交换机的端口类型（Access和Trunk）一、访问链接二、汇聚链接汇聚链接VLAN间通信为什么要进行VLAN间通信？路由器实现VLAN间通信路由器和交换机的连接方式通信细节三层交换机实现VLAN间通信加速VLAN间通信三层交换机与路由器三层交换机路由器路由器和交换机配合构建LAN的实例使用VLAN设计局域网的特点VLAN增加网络的灵活性不使用VLA

  3. 一文让你彻底掌握操作符（超详细教程） - 2

    ✅作者简介：大家好，我是小杨📃个人主页：「小杨」的csdn博客🔥系列专栏：小杨带你玩转C语言【初阶】🐳希望大家多多支持🥰一起进步呀！大家好呀！我是小杨。小杨花几天的时间将C语言中的操作符这部分知识做了一个大总结，在方便自己复习的同时也能够帮助到大家。通篇字数在一万字左右，可以算作是非常详细了，一文就可以带领大家彻底掌握操作符这部分内容，文章很长建议先收藏再看，防止下次想看就找不到啦。文章目录✍1，算术操作符✍2，移位操作符    🔍2.1,左移操作符    🔍2.2,右移操作符       ✨2.2.1,算术移位       ✨2.2.2,逻辑移位✍3，位操作符    🔍3.1,按位与&   

  4. 51单片机——74HC595的应用（SPI实践） - 2

    目录SPI总线SPI总线概述 SPI总线分类SPI优点及缺点SPI接口硬件原理SPI四种工作模式 74HC595应用74HC595芯片概述74HC595封装及管脚功能74HC595工作原理 ​编辑 74HC595串行转并行点亮LED灯 程序实现  Proteus运行结构示意图SPI总线SPI总线概述 SPI（SerialPeripheralinterface）：串行外围设备接口 用途：用来在微控制器与外围设备芯片之间实现数据交换 特点：高速、全双工、同步 SPI总线分类四线制全双工SPI（同时收发）MISO    主机输入/从机输出MOSI    主机输出/从机输入SCLK   串行时钟CS或

  5. 基于51单片机、DS1302时钟模块的电子闹钟设计 - 2

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录一、设计原理1.DS1302介绍2.闹钟音乐播放原理二、程序设计1.DS1302.h2.ds1302.c3.music.h4.main.c三、电路图四、运行结果1.proteus仿真2.开发板实验五、总结六、附件提示：以下是本篇文章正文内容，下面案例可供参考一、设计原理1.DS1302介绍DS1302是美国DALLAS公司推出的一种高性能、低功耗、带RAM的实时时钟电路，它可以对年、月、日、周、时、分、秒进行计时，具有闰年补偿功能，工作电压为2.0V～5.5V。该芯片采用普通32.768kHz晶振，DS1302工作时功耗很

  6. 一、51单片机 使用Proteus掌握LCD1602显示屏的使用（仿真及代码） - 2

    1、单片机控制液晶显示模块1602LCD的显示。液晶显示器（LiquidCrystalDisplay，LCD）具有省电、体积小、抗干扰能力强等优点，LCD显示器分为字段型、字符型和点阵图形型。（1）字段型。以长条状组成字符显示，主要用于数字显示，也可用于显示西文字母或某些字符，广泛用于电子表、计算器、数字仪表中。（2）字符型。专门用于显示字母、数字、符号等。一个字符由5、7或5、10的点阵组成，在单片机系统中已广泛使用（3）点阵图形型。广泛用于图形显示，如笔记本电脑、彩色电视和游戏机等。它是在平板上排列的多行列的矩阵式的晶格点，点大小与多少决定了显示的清晰度。引脚包括8条数据线、3条控制线和3

  7. 一文掌握软件项目成本预算、估算的方法和成本控制的秘籍 - 2

    每个企业都希望在完成项目后获得盈利，但不少企业到了年终后才发现项目做了不少，公司却并没能达到预期，甚至还出现了亏损。那么钱究竟去了哪里？很多公司都搞不清楚原因，出现糊涂账较多的状况，这将会造成严重的后果，尤其在疫情影响下，大环境很恶劣，如果是大公司的事业部门出现亏损，就可能会导致事业部门解散；如果是小公司出现亏损，就很容易导致公司倒闭；怎样做才能确保我们所完成的项目都能获利？从财务角度看，要确保盈利必须做到合理估算成本，只有这样才能在对外签订合约时做出合理报价，在对内在开始项目前做出充分评估投入代价，同时在实施过程中还要控制成本得当，最后项目结束时才会有可能获得盈利。那么我们怎样才能准确的判断

  8. 51单片机（郭天祥版）——键盘检测原理及应用实现 - 2

    实验中我们使用的是52单片机目录前言一、单片机是什么？二、实验步骤1.独立键盘检测1.2代码如下(示例)：1.3图片1.4视频2.矩阵键盘检测2.2代码如下（示例）：2.3图片2.4视频总结：以上就是今天要讲的内容，本文仅仅简单介绍了单片机键盘检测的应用实现，而单片机键盘检测相关理论可以参考教材进行学习前言文章内主要概念引自郭天祥老师《新概念51单片机C语言版》一书主要展示郭天祥老师书中第四章键盘检测原理及应用实现。分为仿真、实体两部分。一、单片机是什么？单片机就是在一块硅片上集成了微处理器、存储器及各种输入/输出接口的芯片，这样一块芯片就具有了计算机的属性，因而被成为单片微型计算机，简称单片

  9. 一文详解COINDAO是什么？ - 2

    COINDAO旨在重建社区信任和安全。基于皖北基因的强烈共识，COINDAO自发产生了一个共创、共建、共治、共享的协作组织。它专注于DAO投资管理协议，为新的优质项目创造增长技术和资金。COINDAO的使命就是为真正的优质项目打造一个去中心化、公开透明的平台，让各个赛道上的优质项目能够以更低的成本快速募集资金并向公众开放.打破头部垄断。让真正的爱好者直接获得早期参与优质项目的资格，不再遥不可及，构建生态应用的可信体系，打造人人参与共建、人人共享的去中心化DAO好处。生态系统，我们称之为COINDAO生态系统。COINDAO国内各大财经网站宣发如下：COINDAO国外各大财经网站宣发： COIN

  10. 一文吃透前端低代码的 “神仙生活” - 2

    今天来说说前端低代码有多幸福？低代码是啥？顾名思义少写代码……这种情况下带来的幸福有：代码写得少，bug也就越少（所谓“少做少错”），因此开发环节的两大支柱性工作“赶需求”和“修bug”就都少了；要测的代码少了，那么测试用例也可以少写了。所以，总结低代码带来的幸福感有这三大点：开发效率提高开发成本减少维护性更高针对上述三点，我们展开说说。01、开发效率提高对于低代码的理解，个人认为可以通过配置化的低成本交互方式（主流是拖拽）加上少量的胶水代码，去满足一类应用的需求。这就说明，基于低代码，开发人员无需代码或说只需少量代码就可以开发出各类应用管理系统，如：OA协同办公、KM知识管理、CRM客户关系

随机推荐