机器学习-决策树(ID3算法及详细计算推导过程)

news/2024/11/29 6:53:54/

        决策树是一种基于树结构进行决策的机器学习算法 ,以下是关于它的详细介绍:

1.基本原理

  • 决策树通过一系列的条件判断对样本进行分类或预测数值。它从根节点开始,根据不同的属性值逐步将样本划分到不同的分支,直到到达叶节点,每个叶节点代表一个类别或数值。
  • 本质是通过条件判断对样本分类,每个内部节点是一个属性上的测试,分支是测试输出,叶节点是类别或值,从根节点到叶节点的路径对应一条分类规则。

2.主要组成部分

  • 节点:包括根节点、内部节点和叶节点。根节点是决策树的起始点,内部节点表示在某个属性上的测试,叶节点则给出最终的分类结果或数值预测。
  • 分支:连接各个节点,代表根据节点测试结果的不同走向,即不同的决策路径

3.决策树举例 

        图1是一个简单的用来对鸟类进行分类的决策树。在该图中,根节点包含各种鸟类;叶节点是所能识别的各种鸟的名称;中间节点是鸟的一些属性;边是鸟的某一属性的属性值;从根节点到叶节点的每一条路径都描述了一种鸟,它包括该种鸟的一些属性及相应的属性值。

        决策树还可以表示为规则的形式。上图的决策树可表示为如下规则集:    

  • IF  鸟类会飞   AND  是家养的    THEN  可能是和平鸽    
  • IF  鸟类会飞   AND  不是家养的  THEN  可能是信天翁    
  • IF  鸟类不会飞 AND  会游泳      THEN  可能是企鹅    
  • IF  鸟类不会飞 AND  不会游泳    THEN  可能是鸵鸟    

        决策树学习过程实际上是一个构造决策树的过程。当学习完成后,就可以利用这棵决策树对未知事物进行分类。

4.重要概念

4.1信息熵

        信息熵是对信息源整体不确定性的度量。假设S为样本集,S中所有样本的类别有k种,如y1,y2,…,yk,各种类别样本在S上的概率分布分别为P(y1),P(y2),…,P(yk),则S的信息熵可定义为:

        其中,概率P(yj)(j=1,2,…,k),实际上为yj的样本在S中所站的比例;对数可以是以各种数为底的对数,在ID3算法中,我们取以2为底的对数。E(S)的值越小,S的不确定性越小,即其确定性越高。 

4.2信息增益

        信息增益(information gain)是对两个信息量之间的差的度量。其讨论涉及到样本集S中样本的结构。对S中的每一个样本,除其类别外,还有其条件属性,或简称为属性。若假设S中的样本有m个属性,其属性集为X={X1,X2,…,Xm},且每个属性均有r种不同的取值,则我们可以根据属性的不同取值将样本集S划分成r个不同的子集S1, S2, ... , Sro。此时,可得到由属性x;的不同取值对样本集S进行划分后的加权信息熵

        其中,t为条件属性x;的属性值;St为x ;= t时的样本子集;E(St)为样本子集St信息熵;IS|和|St分别为样本集S和样本子集St的大小,即样本个数。有了信息熵和加权信息熵,就可以计算信息增益。所谓信息增益就是指E(S)和E(S,x1)之间的差,即

        可见,信息增益所描述的是信息的确定性,其值越大,信息的确定性越高。后面会会给出例题,看例题就明白了。

5.ID3算法

        ID3算法的学习过程是一个以整个样本集为根节点,以信息增益最大为原则,选择条件属性进行扩展,逐步构造出决策树的过程。若假设S={s1,s2,…sn}为整个样本集,X={x1,x2,…,xm}为全体属性集,Y={y1,y2,…yk}为样本类别。则ID3算法描述如下:    

        (1) 初始化样本集S={s1,s2,…sn}和属性集X={x1,x2,…,xm},生成仅含根节点(S, X)的初始决策树。    

        (2) 如果节点样本集中的所有样本全都属于同一类别,则将该节点标记为叶节点,并标出该叶节点的类别。算法结束。 否则执行下一步。    

        (3) 如果属性集为空;或者样本集中的所有样本在属性集上都取相同值,即所有样本都具有相同的属性值,则同样将该节点标记为叶节点,并根据各个类别的样本数量,按照少数服从多数的原则,将该叶节点的类别标记为样本数最多的那个类别。算法结束。否则执行下一步。

        (4) 计算每个属性的信息增益,并选出信息增益最大的属性对当前决策树进行扩展。    

        (5) 对选定属性的每一个属性值,重复执行如下操作,直止所有属性值全部处理完为止:     ① 为每一个属性值生成一个分支;并将样本集中与该分支有关的所有样本放到一起,形成该新生分支节点的样本子集;     ② 若样本子集为空,则将此新生分支节点标记为叶节点,其节点类别为原样本集中最多的类别;     ③ 否则,若样本子集中的所有样本均属于同一类别,则将该节点标记为叶节点,并标出该叶节点的类别。  

        (6) 从属性集中删除所选定的属性,得到新的属性集。    

        (7) 转第(3)步。

5.1 ID3算法举例

  • info:信息量
  • E:信息熵(信息量的加权求和)
  • gain:信息增益

用上图来计算构建决策树

5.1.1计算总的信息量

1.在上表中先看序号,总共有9个P,5个N,则我们可以计算出总的信息量为

2.我们要在天气、气温、湿度和风中选择一个做为根节点 

(1)天气的信息增益

先看天气,天气为时,有2个P,三个N,则信息量

天气为时,有三个P,两个N,则信息量

天气为多云时,有三个P,0个N,则信息熵

天气各种情况加权求和,即天气的信息熵为:

故基于天气的信息增益为:

 

(2)气温的信息增益

 气温-热:

 气温-适中:

气温-冷:

各个气温情况加权求和:

基于气温的信息增益为: 

同理我们可以计算湿度和风的信息增益

3.天气的信息增益最大,所以我们选择天气作为根节点

 

4.天气作为根节点,则他的子树我们就用相同的方法即可计算出来 

 


http://www.ppmy.cn/news/1550837.html

相关文章

【C++】简单数据类型详解

博客主页: [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯字符型(char)1.1 ASCII 码表 💯整型(int)2.1 整型的分类2.2 有符号和无符号整型2.3 跨平台差异2.4 整型数据类型…

Android获取状态栏、导航栏的高度

Android获取状态栏的高度: 方法一:通过资源名称获取, getDimensionPixelSize,获取系统中"status_bar_height"的值,方法如下: Java: public static int getStatusBarHeight(Context…

【操作文档】mysql分区操作步骤.docx

1、建立分区表 执行 tb_intercept_notice表-重建-添加分区.sql 文件; DROP TABLE IF EXISTS tb_intercept_notice_20241101_new; CREATE TABLE tb_intercept_notice_20241101_new (id char(32) NOT NULL COMMENT id,number varchar(30) NOT NULL COMMENT 号码,cre…

遗传算法与深度学习实战——进化优化的局限性

遗传算法与深度学习实战——进化优化的局限性 0. 前言1. 数据集加载2. 模型构建相关链接 0. 前言 深度学习 (Deep learning, DL) 模型的规模不断扩大,从早期只有数百个参数的模型到最新的拥有数十亿个参数的 transformer 模型。优化或训练这些网络需要大量的计算资…

【Linux】自定义简易shell

【Linux】自定义简易shell 🥕个人主页:开敲🍉 🔥所属专栏:Linux🍊 🌼文章目录🌼 1. 实现思路 2. 实现代码 2.1 输出命令行提示符 2.2 获取用户输入信息 2.3 解析用户输入命令 2.4 …

鸿蒙开发App 如何通过抓包查看 http 网络请求?

通过借助第三方工具 Charles https://www.charlesproxy.com/ https://www.zzzmode.com/mytools/charles/https://www.zzzmode.com/mytools/charles/ Charles 激活码计算器 相关博客日志:https://zhuanlan.zhihu.com/p/281126584 MAC上的使用方法: ch…

c++类模板成员函数的特化

是的,类成员函数可以是模板函数。在C中,类模板和非模板类都可以包含模板成员函数。这种设计允许类在某些成员函数中具有泛型行为,而不需要将整个类设计为模板。 本文将详细介绍类成员函数作为模板函数的概念、声明和定义方法,以及…

算法竞赛(Python)-链表

文章目录 一 链表简介1.1链表定义1.2 双向链表1.3 循环链表 二、链表的基本操作2.1 链表的结构定义2.2 建立一个线性链表2.3 求线性链表的长度2.4 查找元素2.5 插入元素2.5.1 链表头部插入元素2.5.2 链表尾部插入元素2.5.3 链表中间插入元素 2.6 改变元素2.7 删除元素2.7.1 链表…