机器学习-模型与算法

【模型】一篇入门之-决策树ID3算法

作者 : 老饼 发表日期 : 2022-09-25 19:19:25 更新日期 : 2025-06-02 23:57:39
本站原创文章,转载请说明来自《老饼讲解-机器学习》www.bbbdata.com



ID3决策树是罗斯.昆兰(J. Ross Quinlan)于1975年提出的一种基于信息增益函数的决策树模型

本文讲解ID3决策树的模型结构、模型思想原理,以及ID3决策树的算法流程

通过本文,可以快速了解ID3决策树模型是什么,以及ID3决策树的相关公式的具体意义






     前言     


ID3算法是相对较早的算法,现在已经一般都不使用了,而是使用CART决策树
但ID3作为一个经典算法,仍然有独特的、闪光的地方
本文讲解ID3算法是什么,包括它的思想、模型结构以及相关公式
 由于一般的软件已经不实现ID3,实际中也很少使用
因此本文不提供代码实现,事实上也不建议大家花太多时间在ID3决策树上面

 备注:本文需建立在CART决策树的认识上再进行阅读,阅读时注意ID3与CART的区别





    01. ID3决策树-模型结构    





本节讲解ID3决策树模型是什么,并与CART决策树进行对比





   ID3决策树模型   


ID3是最早的决策树模型算法,由罗斯.昆兰(J. Ross Quinlan)于1979年提出
ID3决策树模型简单而朴素,它模仿人类的决策方式,用于解决模式识别(分类)问题
 ID3决策树模型如下:
 
ID3决策树的模型结构
ID3决策树模型与CART决策树一样,都是一棵树,但它的输入变量必须全是枚举型
它在每个节点都选择一个变量,然后按变量的所有取值可能进行分枝
 如图所示,一棵ID3决策树由3部分构成:
1. 节点选择哪个变量分枝                               
2. 节点是否能成为叶子节点                            
3. 如果是叶子节点,该叶子节点的属于哪一类 






    ID3与CART树的比较   


下面不妨通过ID3决策树与CART决策树的比较,来进一步加深对ID3决策树的理解
ID3与CART决策树的模型结构差异如下:

1. 变量类型 
 CART的输入是连续变量,ID3的输入变量是枚举变量

2. 分叉类型
CART决策树是一棵二叉树,即每次只作二分叉
而ID3是全分叉,它对节点变量的枚举值全分叉,变量有多少个枚举值就分多少个叉
 所以CART需要指定分裂阈值,而ID3并不需要,因为它是全分裂

3. 层数上限
CART如果在第一层选择了身高变量分叉,那第二层,仍然可以选择身高来分叉
而ID3如果在第一层选择了身高,那第二层只能选择身高以外的变量来分叉,即变量不可重复
 因此,CART可能会有很多层,因为它的变量可重复利用,而ID3的层数必定<=变量个数
 
 4. 变量分叉点
CART在确定节点所选择的变量后,还需要确定变量的分割阈值,根据阈值来分叉
而ID3不需要,它直接按变量枚举个数进行全分叉,因此它不需要阈值

 一句话总结:相比CART, ID3更原始、简单、粗爆,它就是枚举变量全分叉







    02. ID3决策树-分叉评估函数    





本节介绍ID3决策树分叉时使用的评估函数





    ID3的分叉评估函数    


ID3每次分叉时,需要确定选择哪一个变量,因此需要一个函数来评估分叉质量
在ID3算法中,使用信息增益作为分叉质量评估函数
 信息增益(Gain)函数如下:

 其中,
  :分叉子节点个数                                               
  :所有子节点的总样本数(也即父节点的样本数)
  :第 i 个子节点上样本个数                                  
 :第 i 个子节点上第k类样本的个数                       
  :父节点上第 k 类样本的个数                               
信息增益的意义是,分叉后比分叉前信息量(不确定性)的减少量





    信息增益函数的推导    


ID3的信息增益(Gain)函数的意义就是,分叉后比分叉前信息量(不确定性)的减少量
 信息增益函数的详细推导如下:
1. 节点分类质量

度量单个节点上的分类质量可以用经验熵公式:
 
 其中
 
  :节点上样本个数                    
  :节点上样本的类别个数        
 :节点上属于 k 类的样本个数 
 说明:熵的背景意义是不确定性
所以,H越大,代表该节点越不能确定它是哪一类,越大质量就越差
2. 分叉质量
分叉质量 (信息增益)= 分叉前质量 - 分叉后质量                                      
分叉前质量:分叉前是一个单节点,直接用单节点的经验熵即可                   
 
分叉后质量:用各个分叉子节点的经验熵加权和(也称为条件经验熵)即可
 
 其中,
  :子节点个数                                
   :所有子节点的总样本数               
 :第 i 个子节点上样本个数           
  :第 i 个子节点上第k类样本的个数 
两者相减(分叉前质量 - 分叉后质量)就得到了分叉带来的质量提升--信息增益







    03. ID3决策树-算法流程    




本节讲解ID3的整体算法流程




   ID3决策树-算法流程    


算法基本是用贪婪算法,即从根节点,逐个逐个节点向下分裂,
每次只要确定分裂哪个变量,分裂之后节点是否还要继续分裂即可

  ID3算法主流程
   
ID3算法主流程如下:
ID3决策树-算法流程图 
1. 计算各个变量的信息增益,确定本次由哪个变量分支           
2. 对变量分支后,确定哪些节点是叶子节点                              
哪些需要再分,需要再分的就继续由剩余变量分支       
3. 如果所有节点都不需分支,或所有变量已分完,则停止算法      
其中,成为叶子节点的条件如下:
(1) 该节点按最优秀的变量去分,收益仍然极小    
则该节点不再分,作为叶子节点             
(2) 无变量可分                                                  
(3) 叶子上的样本全属于同一类                          
      叶子节点的类别如下确定:
叶子节点的样本中,哪个类别的样本最多,则节点就是哪个类别






好了,以上就是ID3决策树的算法流程与相关公式了~









 End 






图标 评论
添加评论