ID决策树的构造原理

news/2025/1/12 10:04:36/

前言

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

学习目标

  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/news/1443436.html

相关文章

《QT实用小工具·四十五》可以在界面上游泳的小鱼

1、概述 源码放在文章末尾 该项目实现了灵动的小鱼&#xff0c;可以在界面上跟随鼠标点击自由的游泳&#xff0c;项目demo演示如下所示&#xff1a; 项目部分代码如下所示&#xff1a; #include "magicfish.h" #include <QtMath> #include <QPainter>…

物联网鸿蒙实训解决方案

一、建设背景 在数字化浪潮汹涌的时代&#xff0c;华为鸿蒙系统以其前瞻的技术视野和创新的开发理念&#xff0c;成为了引领行业发展的风向标。 据华为开发者大会2023&#xff08;HDC. Together&#xff09;公布的数据&#xff0c;鸿蒙生态系统展现出了强劲的发展动力&#x…

9.基本定时器

基本定时器的个数&#xff0c;不同芯片的定时器数量不一定一样&#xff0c;有些芯片没有基本定时器 就比如STM32F103系列&#xff0c;只有4个定时器&#xff0c;3个通用定时器&#xff0c;1个高级定时器 基本定时器作用&#xff1a; 延时 定时器更新中断 触发DAC转换 系统…

单例模式及其应用

单例模式介绍&#xff1a; 单例模式是一种常见的设计模式&#xff0c;其目的是确保某个类只有一个实例存在&#xff0c;并提供一个全局访问点。 在实现单例模式时&#xff0c;一般需要注意以下几点&#xff1a; 私有化构造函数&#xff1a;防止外部直接实例化对象。私有静态…

vue 实现 el-table 点击图标复制文本或者双击文本复制

方法一 双击复制&#xff1a; el-table 添加 cell-dblclick"dbClickCopyText" 双击 <el-table v-loading"loading" cell-dblclick"dbClickCopyText" :data"xxxList"></el-table> // 双击复制dbClickCopyText(row, col…

1.pytorch加载收数据(B站小土堆)

数据的加载主要有两个函数&#xff1a; 1.dataset整体收集数据&#xff1a;提供一种方法去获取数据及其label&#xff0c;告诉我们一共有多少数据&#xff08;就是自开始把要的数据和标签都收进来&#xff09; 2.dataloader&#xff0c;后面传入模型时候&#xff0c;每次录入数…

linux 上 jps 列出一堆 jar,如何快速定位 jar 文件启动位置?

例如&#xff0c;在 /data下有一个 xxx.jar &#xff0c;如果是通过 "java -jar /data/xxx.jar" 方式启动&#xff0c;则 jps会列出的名字中带 xxx.jar&#xff0c;这时再 "ps -ef | grep xxx.jar" 就会列出 更详细的信息&#xff0c;例如 "java -ja…

Android 振动和触感反馈功能失效问题分析

文章目录 一、 可以先通过adb来确定是否有打印Log&#xff0c;查看中相关的按键振动事件是否有效二、 适配按键事件三、延长振动时长 在Android13的项目(MTK平台)中遇到这样一个问题&#xff0c;在设置 - 提示音和振动 - 振动和触感反馈 - 打开按触反馈&#xff0c;但是按键没有…