算法一篇入门

【模型】一篇入门之-决策树C4.5算法

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


C4.5算法也是经典的决策树算法之一,它是ID3算法的延续

本文讲解决策树C4.5算法的思想,是决策树模型相关知识的补充

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



   01. 为什么会有决策树C4.5算法   



本节先理解为什么有C4.5算法,及C4.5算法是什么



    决策树C4.5算法简介    


C4.5就是对ID3的补充,
就是对ID3打补丁,
因此,C4.5并不是一个新算法,
而是对ID3添加的一系列补丁后,
如果命名为ID3 plus会更加贴切。

 

 

     决策树ID3算法的缺陷     


由于C4.5算法是ID3算法的改进,
因此我们必须了解,ID3算法有什么缺点,才知道C4.5算法的重心在哪
 
 ID3算法的缺点如下:
  
   (1) 变量偏好多枚举值            
  
 (2) ID3容易过拟合                
   (3) ID3不支持连续变量        
   (4) 不支持数据有缺失值   
    
✍️补充:如何理解“变量偏好多枚举值”
ID3更偏好优先分叉枚举值多的变量
因为ID3用信息增益评估分叉质量,该评估函数会更偏好枚举值多的变量
例如:如果变量A有2个枚举,B有10个枚举,肯定就偏好B了,
因为B一下子把节点分叉成10个子节点,而A只分成2个子节点,
分成10个子节点的确定性肯定比2个会更强些





  02. 决策树C4.5算法   



本节讲解C4.5算法具体是什么,和它具体如何改进ID3算法



   C4.5算法-基于ID3的改进   


C4.5算法主要就是改进上面所说的ID3算法的4个缺点, 它相当于给ID3打上补丁
要掌握C4.5算法,其实就是在ID3的基础上,掌握C4.5对ID3的4个缺点的改进
下面描述C4.5是如何改进ID3的四个缺点的
变量偏好纠正   
 
 变量偏好纠正:使用信息增益比
C4.5用信息增益比替代信息增益,
即信息增益/变量的熵,对枚举值多的变量进行了一定的惩罚:

信息增益比:

 分子就是ID3中的信息增益, 分母则是全体样本中变量v的熵
 分母符号说明:
:  全体样本(划重点,是全体样本)变量v的枚举个数  
 :  全体样本个数                                                           
:全体样本变量v第k个枚举值的样本个数                     
 
   过拟合处理   
 过拟合处理:添加剪枝
C4.5在ID3的基础上,加入了剪枝,来处理过拟合的问题。
先定义整棵树的评估函数(每个叶子节点质量的加权和与叶子个数的惩罚项):
 
然后自下而上,缩回式剪枝,
 先判断叶子剪前和剪后的损失函数,如果能让损失函数变小,则剪
 
    连续变量处理   
 
C4.5对连续变量处理如下:
设有n个样本,排序,在变量相邻值中间切割(n-1个割点)
每个割点将变量割成两类,计算这n-1种切法,
哪种切法分成的两类得到的信息增益比更大,则取该切法
分叉时,则按该切法,进行二分叉
 注:连续变量分叉后,后续还可以继续 使用该变量进行分叉
因此,与ID3不同,C4.5树的层数可能多于变量数

 
 (4)缺失值的处理   
 
变量有缺失值时,有三个地方要处理,大概的思路是,
(1)选择变量时,只用非缺失样本计算熵,                                    
再乘以系数 非缺失量/总样本量。                                   
(2)分派样本到子节点时,每个子节点都包含所有缺失值样本,      
但需要加上权重,权重为该子节点的样本量(非缺失)占比 
(3)评估时若有缺失值,则走所有子节点,多条路线并存,            
最后把所有叶子节点的结果评估,                                 
哪个叶子节点更可靠,就选哪个叶子节点                       
 备注   
缺失值的处理细节极为复杂,作者只能告诉你,忽略它是最好的作法
如果你一定要纠结,可以阅读《
机器学习笔记(7)——C4.5决策树中的缺失值处理
如果还纠结,直接读C4.5作者原文《Programs for Machine Learning》










 End 







联系老饼