老饼讲解-机器学习 机器学习 神经网络 深度学习
逻辑回归与决策树

【原理】CART分类树构建原理

作者 : 老饼 发表日期 : 2022-06-26 14:03:07 更新日期 : 2023-11-10 22:55:36
本站原创文章,转载请说明来自《老饼讲解-机器学习》www.bbbdata.com


本文剖析matlab的CART决策树函数fitctree构建决策树的原理。

通过本文的学习,掌握和了解CART决策树的实现逻辑,

在《CART分类树-代码自实现》中,我们按本文提供的逻辑,重现fictree函数的效果



   01. CART决策树的构建目标   



本节先梳理究竟我们希望CART决策树构建成什么样



    CART决策树的构建目标    


CART目标是构建一棵二叉树,尽量把历史样本按类别分到不同的叶子节点
最理想时,所有叶子的类别都只有一个最不理想时,所有叶子的类别都平均
 示例如下:
 





   02. CART决策树的构建主流程   



本节讲解CART决策树构建过程的主流程

通过本节了解一个CART决策树是怎么构建出来的



    第一步:根节点分裂    


最开始时,所有样本都在根节点,
然后寻找一个特征和阈值,把样本一分为二,将样本分到左右节点

那怎么确定分裂时使用哪组【特征,分裂值】呢?
其实是靠历遍,历遍所有的【特征,分裂值】,然后评估收益,
哪组分裂后的收益最大,就用哪组【特征,分裂值】
收益的评估后面再详细说明




   第二步:新生节点的判断:成为叶子或继续分裂   


当分裂完根节点后,就产生了两个新节点,
接下来需要判断,新生节点是成为叶子还是需要继续分裂
1.继续分裂
如果需要继续分裂,就继续寻找一个【特征,分裂值】,
将节点继续一分为二,这称为树的生长
示例如下:
 
2. 成为叶子
 
如果成为叶子,将节点标为叶子,不再分裂,
并将节点上样本最多的类别作为叶子类别
 如果需要输出类别概率,就把该类别的占比一起记录下来
 示例如下:
 

  
节点成为叶子的判别一般有以下几种条件:  
 👉1. 节点上的样本都属于同一个类别            
 👉2. 节点上的样本太少 例如,少于10个      
 👉3. 节点层数过深  例如,节点层数>=10   




  第三步: 不断迭代直到终止  


不断按(二)去迭代,直到没有节点需要分裂
 



     CART决策树构建过程总结     


 CART决策树构建的总过程如下:






   03. 【特征-分割值】的选择过程与收益函数GINI   



本节补充上面主流程遗留的【特征,分割值】的选择细节,以及历遍过程的具体细节



     节点分裂质量     


【特征,分割值】的选择一般是历遍计算所有特征、所有可分割点带来的收益,
然后选择收益最大者作为分割点
节点分裂质量:收益函数GINI   
CART树一般用基尼函数的取反函数作为收益函数。
Gini收益函数公式如下
 

其中,                                                            
 :  划到左节点的样本个数                              
 :  划到右节点的样本个数                              
   :   本次划分的总样本个数,即  
 :  左节点上属于 ​ 类的个数                    
 :  右节点上属于  类的个数                   
✍️GINI收益函数的含义:
GINI收益函数整个公式的意思是,
在左(或右)节点随机抽取两个样本,
这两个样本不属于同一类的概率。
公式可以如下解读:
  
GINI系数为什么代表概率,请看附件《GINI系数的含义与推导》。
 GINI系数为什么能作为收益函数:
 
同一个节点,不属同一类的概率越小(即属于同一类的概率越大),
 说明节点上的杂质越小(也叫纯度越纯)
 
 当一个节点的纯度达到最高,即节点上所有样本所属类别都一样时,
说明该节点说明分割得越好,这正是我们想要的结果




     历遍过程细节说明     


历遍的过程是先对所有特征历遍,再找出每个特征的所有分割可能,
分别评估所有分割可能的收益,最后选择收益最大者,作为节点的【特征-分割值】
  




以上,就是matlab自带的fitctree函数构建一棵CART分类决策树的流程了。






 End 







联系老饼