决策树——ID3算法-程序员宅基地

前言

我们在使用数据挖掘的时候，完成数据的“清洗”等一系列繁琐的步骤，就可以对数据进一步地进行“挖掘”——对数据进行分类的建立、预测、聚类分析等等的操作。在分类和预测的过程中，有一系列的算法得以脱颖而出——“回归分析”、“决策树”、“人工神经网络”等等

那么今天我就来介绍一下”决策树“——ID3算法

一、ID3算法

ID3作为一种经典的决策树算法，是基于信息熵来选择最佳的测试属性，其选择了当前样本集中具有最大信息增益值的属性作为测试属性。
样本集的划分则依据了测试属性的取值进行，测试属性有多少种取值就能划分出多少的子样本集；同时决策树上与该样本集相应的节点长出新的叶子节点。
ID3算法根据信息论理论，采用划分后样本集的不确定性作为衡量划分样本子集的好坏程度，用“信息增益值”度量不确定性——信息增益值越大，不确定性就更小，这就促使我们找到一个好的非叶子节点来进行划分。

二、ID3算法的基本原理以及实例分析

1.我们假设一个这样的数据样本集S，其中数据样本集S包含了s个数据样本，假设类别属性具有m个不同的值（判断指标）：C_i(i=1,2,3,…,m)

S_i是C_i中的样本数，对于一个样本集
总的信息熵为：
I(S1,S2,...,Sm)=
其中，P_i表示任意样本属于C_i的概率，也可以用s_i/s 进行估计。
我们假设一个属性A具有k个不同的值 {a₁,a₂,…,a_k}, 利用属性A将数据样本S划分为k个子集{S₁，S₂，…， S_k}，其中S_j包含了集合S中属性A取a_j值的样本。若是选择了属性A为测试属性，则这些子集就是从集合S的节点生长出来的新的叶子节点。
设S_ij是子集S_j中类别为C_i的样本数，则根据属性A划分样本的信息熵值为：

最后，我们利用属性A划分样本集S后得到的信息熵增益为：
在这里插入图片描述

2.实例分析

我们假设有这么一个案例，小学校门口总是会出现一些零食小贩，判断某一天这些零食小贩的收入是否良好可以依据很多因素，如：天气、学生是否放假、保安是否打压、是否进行活动促销等等多个属性来衡量。
对于天气属性，我们将是否下雨作为一个天气好坏的叛别，则天气具有“好”与“不好”两种属性值；
学生是否放假也有两种属性值“是”与“否”；
保安是否打压也分为“好”与“不好”；
活动促销的两种属性值为“是”与“否”
而对于小贩的收入，我们假设取全年的平均收入为平均值，高于平均值为“高”，否则为“低”。
由此，我们得到了这样的一个表格：

在这里插入图片描述
计算过程：
首先，我们先计算总的信息熵，其中共有10条记录，收入为“高”有5条，收入为“低”也有5条
步骤1 总信息熵:

在这里插入图片描述
下面计算各个属性的信息熵:
步骤2 天气属性：
天气好的情况下，收入为“高”的记录为4条，收入为“低”的记录为1条，可以表示为(4,1)；天气不好的情况下，收入为“高”的记录为1条，收入为“低”的记录为4条,可以表示为(1,4).
则天气属性的信息熵的计算过程如下：
在这里插入图片描述

步骤3 学生放假属性：
学生放假时，收入为“高”有0条，收入为“低”有4条。记为（0,4）；
学生不放假时，收入为“高”有5条，收入为“低”有1条。记为（5,1）；

学生放假属性的计算过程为：
在这里插入图片描述

在这里插入图片描述
步骤4 促销属性：
当小贩进行促销时，收入为“高”有3条，收入为“低”有2条。记为（3,2）；
当小贩不进行促销时，收入为“高”有2条，收入为“低”有3条。记为（2,3）；
促销属性的计算过程为：

在这里插入图片描述

步骤5 计算信息增益值

由步骤4可以知道“学生放假”的信息增益值最大，所以以“学生放假“为节点进行划分，划分为两个分支分别为“是”、“否”（指学生是否放假），然后再循环进行步骤1 ~步骤5的过程（排除已经进行划分的节点步骤），对剩下的2个节点分支进行划分，再进行信息增益的计算。

直至无法形成新的节点，从而生成一棵“决策树”。

ID3算法参考了《python数据分析与挖掘实战》中关于ID3算法的解释，感兴趣的可以前往观看。

总结

ID3算法是经典的决策树算法，但是随着时间的发展，出现的C4.5算法弥补了许多ID3算法在使用信息增益率来选择节点属性的不足之处。
感谢各位的观看，望斧正。

本文链接：https://blog.csdn.net/weixin_46245411/article/details/114703474

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

攻防世界_难度8_happy_puzzle_攻防世界困难模式攻略图文-程序员宅基地

文章浏览阅读645次。这个肯定是末尾的IDAT了，因为IDAT必须要满了才会开始一下个IDAT，这个明显就是末尾的IDAT了。，对应下面的create_head()代码。，对应下面的create_tail()代码。不要考虑爆破，我已经试了一下，太多情况了。题目来源：UNCTF。_攻防世界困难模式攻略图文

达梦数据库的导出（备份）、导入_达梦数据库导入导出-程序员宅基地

文章浏览阅读2.9k次，点赞3次，收藏10次。偶尔会用到，记录、分享。1. 数据库导出1.1 切换到dmdba用户su - dmdba1.2 进入达梦数据库安装路径的bin目录，执行导库操作　　导出语句：./dexp cwy_init/[email protected]:5236 file=cwy_init.dmp log=cwy_init_exp.log　注释：　　 cwy_init/init_123..._达梦数据库导入导出

js引入kindeditor富文本编辑器的使用_kindeditor.js-程序员宅基地

文章浏览阅读1.9k次。1. 在官网上下载KindEditor文件，可以删掉不需要要到的jsp，asp，asp.net和php文件夹。接着把文件夹放到项目文件目录下。2. 修改html文件，在页面引入js文件：<script type="text/javascript" src="./kindeditor/kindeditor-all.js"></script><script type="text/javascript" src="./kindeditor/lang/zh-CN.js"_kindeditor.js

STM32学习过程记录11——基于STM32G431CBU6硬件SPI+DMA的高效WS2812B控制方法-程序员宅基地

文章浏览阅读2.3k次，点赞6次，收藏14次。SPI的详情简介不必赘述。假设我们通过SPI发送0xAA，我们的数据线就会变为10101010，通过修改不同的内容，即可修改SPI中0和1的持续时间。比如0xF0即为前半周期为高电平，后半周期为低电平的状态。在SPI的通信模式中，CPHA配置会影响该实验，下图展示了不同采样位置的SPI时序图[1]。CPOL = 0，CPHA = 1：CLK空闲状态 = 低电平，数据在下降沿采样，并在上升沿移出CPOL = 0，CPHA = 0：CLK空闲状态 = 低电平，数据在上升沿采样，并在下降沿移出。_stm32g431cbu6

计算机网络-数据链路层_接收方收到链路层数据后,使用crc检验后,余数为0,说明链路层的传输时可靠传输-程序员宅基地

文章浏览阅读1.2k次，点赞2次，收藏8次。数据链路层习题自测问题1.数据链路(即逻辑链路)与链路(即物理链路)有何区别?“电路接通了”与”数据链路接通了”的区别何在?2.数据链路层中的链路控制包括哪些功能?试讨论数据链路层做成可靠的链路层有哪些优点和缺点。3.网络适配器的作用是什么?网络适配器工作在哪一层?4.数据链路层的三个基本问题(帧定界、透明传输和差错检测)为什么都必须加以解决？5.如果在数据链路层不进行帧定界，会发生什么问题？6.PPP协议的主要特点是什么？为什么PPP不使用帧的编号？PPP适用于什么情况？为什么PPP协议不_接收方收到链路层数据后,使用crc检验后,余数为0,说明链路层的传输时可靠传输

软件测试工程师移民加拿大_无证移民，未受过软件工程师的教育（第1部分）-程序员宅基地

文章浏览阅读587次。软件测试工程师移民加拿大无证移民，未受过软件工程师的教育(第1部分) (Undocumented Immigrant With No Education to Software Engineer(Part 1))Before I start, I want you to please bear with me on the way I write, I have very little gen...

随便推点

Thinkpad X250 secure boot failed 启动失败问题解决_安装完系统提示secureboot failure-程序员宅基地

文章浏览阅读304次。Thinkpad X250笔记本电脑，装的是FreeBSD，进入BIOS修改虚拟化配置（其后可能是误设置了安全开机），保存退出后系统无法启动，显示：secure boot failed ，把自己惊出一身冷汗，因为这台笔记本刚好还没开始做备份.....根据错误提示，到bios里面去找相关配置，在Security里面找到了Secure Boot选项，发现果然被设置为Enabled，将其修改为Disabled ，再开机，终于正常启动了。_安装完系统提示secureboot failure

C++如何做字符串分割（5种方法）_c++ 字符串分割-程序员宅基地

文章浏览阅读10w+次，点赞93次，收藏352次。1、用strtok函数进行字符串分割原型： char *strtok(char *str, const char *delim);功能：分解字符串为一组字符串。参数说明：str为要分解的字符串，delim为分隔符字符串。返回值：从str开头开始的一个个被分割的串。当没有被分割的串时则返回NULL。其它：strtok函数线程不安全，可以使用strtok_r替代。示例：//借助strtok实现split#include <string.h>#include <stdio.h&_c++ 字符串分割

2013第四届蓝桥杯 C/C++本科A组真题答案解析_2013年第四届c a组蓝桥杯省赛真题解答-程序员宅基地

文章浏览阅读2.3k次。1 .高斯日记大数学家高斯有个好习惯：无论如何都要记日记。他的日记有个与众不同的地方，他从不注明年月日，而是用一个整数代替，比如：4210后来人们知道，那个整数就是日期，它表示那一天是高斯出生后的第几天。这或许也是个好习惯，它时时刻刻提醒着主人：日子又过去一天，还有多少时光可以用于浪费呢？高斯出生于：1777年4月30日。在高斯发现的一个重要定理的日记_2013年第四届c a组蓝桥杯省赛真题解答

基于供需算法优化的核极限学习机(KELM)分类算法-程序员宅基地

文章浏览阅读851次，点赞17次，收藏22次。摘要：本文利用供需算法对核极限学习机(KELM)进行优化，并用于分类。

metasploitable2渗透测试_metasploitable2怎么进入-程序员宅基地

文章浏览阅读1.1k次。一、系统弱密码登录1、在kali上执行命令行telnet 192.168.26.1292、Login和password都输入msfadmin3、登录成功，进入系统4、测试如下：二、MySQL弱密码登录：1、在kali上执行mysql –h 192.168.26.129 –u root2、登录成功，进入MySQL系统3、测试效果：三、PostgreSQL弱密码登录1、在Kali上执行psql -h 192.168.26.129 –U post..._metasploitable2怎么进入

Python学习之路：从入门到精通的指南_python人工智能开发从入门到精通pdf-程序员宅基地

文章浏览阅读257次。本文将为初学者提供Python学习的详细指南，从Python的历史、基础语法和数据类型到面向对象编程、模块和库的使用。通过本文，您将能够掌握Python编程的核心概念，为今后的编程学习和实践打下坚实基础。_python人工智能开发从入门到精通pdf