算法一篇入门

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

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


本文讲解ID3决策树的模型和思想,是决策树模型相关知识的补充。

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




     本文背景     


常见的决策树算法包括ID3、C4.5和CART三种
CART和【ID3,C4.5】是两条不同的分支,
ID3算法和C4.5算法提出比较早,但目前主流是使用CART算法
 在软件算法包里,一般都只看到CART算法了
 尽管ID3和C4.5已经是一条在实际使用中逐渐遗弃的算法分支,
但它们仍有独特的闪光的地方
 
本文讲解ID3,C4.5的思路,但不再对它们落地代码,
也不建议大家花太多时间在上面




    01. ID3 模型结构    


本节讲解ID3决策树模型是什么,

并通过与CART决策树的差异对比来进一步掌握ID3决策树


   ID3决策树模型   


ID3决策树模型如下:
 

ID3决策树模型也是一棵树,输入变量必须全是枚举型
每个节点选择一个变量,按该变量所有可能取值分叉
 
 ID3决策树需要确定的内容
(1)节点选择哪个变量分叉                               
(2)节点是否能成为叶子节点                            
(3)如果是叶子节点,该叶子节点的属于哪一类 



    ID3与CART树结构的差异    


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

 (2)分叉类型
CART是二叉树,每次只作二分叉,
而ID3分叉是选举的变量,有多少个枚举值,就分多少个叉

 (3)层数上限
CART如果在第一层选择了身高变量分叉,
那第二层,仍然可以选择身高来分叉
而ID3如果在第一层选择了身高,
那第二层只能选择身高以外的变量来分叉,
所以,ID3的层数<=变量个数
 
  (4) 变量分叉点
CART在确定变量后,还需要确定分割值来作为分叉点,
而ID3不需要,它直接按变量枚举个数分叉

总结:相比CART, ID3更原始,简单,粗爆




    02. 分叉评估函数    



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



    评估函数    


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


  : 分叉子节点个数                                                   
    : 所有子节点的总样本数(也即父节点的样本数)    
 : 第 i 个子节点上样本个数                                         
 :第 i 个子节点上第k类样本的个数                             
 :父节点上第 k 类样本的个数                                     

信息增益的意义是,分叉后比分叉前信息量(不确定性)的减少量。



    评估函数的推导    


(1)节点分类质量
度量单个节点上的分类质量可以用经验熵公式:


 :节点上样本个数                   
  : 节点上样本的类别个数            
  :节点上属于 k 类的样本个数    
----------------------------------------------------------------
说明:熵的背景意义是不确定性。
所以,H越大,代表该节点越不能确定它是哪一类。越大,质量越差。
(2)分叉质量
分叉质量 (信息增益)= 分叉前质量 - 分叉后质量                                      

分叉前质量:分叉前是一个单节点,直接用单节点的经验熵即可                   


分叉后质量:用各个分叉子节点的经验熵加权和(也称为条件经验熵)即可


  : 子节点个数                              
    : 所有子节点的总样本数             
: 第 i 个子节点上样本个数           
 :第 i 个子节点上第k类样本的个数
两者相减(分叉前质量 - 分叉后质量)即可得到分叉带来的质量提升---信息增益。





    03. ID3算法流程    



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



   ID3的算法思想与算法主流程    


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

    ID3算法主流程    
(1)  计算各个变量的信息增益,确定本次由哪个变量分支           
(2)  对变量分支后,确定哪些节点是叶子节点,                        
哪些需要再分,需要再分的就继续由剩余变量分支. 
(3)  如果所有节点都不需分支,或所有变量已分完,则停止算法.  



    细节补充说明    


1.成为叶子节点的条件
(1)  该节点按最优秀的变量去分,收益仍然极小,    
则该节点不再分,作为叶子节点。             
(2)  无变量可分。                                                  
(3)  叶子上的样本全属于同一类。                          
 
2.如何确定叶节点类别
节点中所属类别最多的类









 End 






联系老饼