第三课:决策树
决策树
【原理】CART决策树构建过程
作者 : 老饼 日期 : 2022-06-26 03:40:31 更新 : 2022-09-27 17:10:48
本站原创文章,转载请说明来自《老饼讲解-机器学习》ml.bbbdata.com


上面我们是借用sklearn包实现的,那软件内部是如何构造树的呢?

本文讲解决策树构造的过程。

(下面的构造流程来源于matlab决策树软件包,与sklearn的大同小异,相对更为简洁)。



   01. 构建目标   


CART目标是构建一棵二叉树,

尽量把历史样本按类别分到不同的叶子节点

最理想时,所有叶子的类别都只有一个

最不理想时,所有叶子的类别都平均







   02. 构建主流程   



    第一步:根节点分裂    


最开始时,所有样本都在根节点,
然后寻找一个特征和阈值,
把样本一分为二,将样本分到左右节点。
那怎么确定分裂时使用哪组【特征,分裂值】呢。
其实是靠历遍,历遍所有的【特征,分裂值】,
然后评估收益,
哪组分裂后的收益最大,就用哪组【特征,分裂值】
(收益的评估后面再详细说明)



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



当分裂完根节点后,就产生了两个新节点,

接下来需要判断,

新生节点是成为叶子还是需要继续分裂,


1、继续分裂


如果需要继续分裂,
就继续寻找一个【特征,分裂值】,
将节点继续一分为二,
这称为树的生长
 




2、成为叶子


如果成为叶子,将节点标为叶子,不再分裂,
并将节点上样本最多的类别作为叶子类别
(如果需要输出类别概率,就把该类别的占比一起记录下来)。
 
节点成为叶子的判别一般有以下几种条件:  
(1)节点上的样本都属于同一个类别            
(2)节点上的样本太少(例如,少于10个)      
(3)节点层数过深。(例如,节点层数>=10)

PASS:此类条件还有很多,不同软件包提供不同的条件选择。



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


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


     总过程     


分裂的总过程如下:




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



这里补充上面主流程遗留的【特征,分割值】的选择细节。


【特征,分割值】的选择一般是历遍计算所有特征、所有可分割点带来的收益,

然后选择收益最大者作为分割点。


  (一)节点分裂质量:收益函数GINI   



CART树一般用基尼函数的取反函数作为收益函数。


(1) Gini收益函数公式:


 

其中,                                                            
 :  划到左节点的样本个数                              
 :  划到右节点的样本个数                              
   :   本次划分的总样本个数,即  
 :  左节点上属于 ​ 类的个数                    
 :  右节点上属于  类的个数                   


(2) GINI收益函数的含义:


GINI收益函数整个公式的意思是,
在左(或右)节点随机抽取两个样本,
这两个样本不属于同一类的概率。
公式可以如下解读:

 

GINI系数为什么代表概率,请看附件《决策树GINI系数推导》。



(3) GINI系数为什么能作为收益函数:


同一个节点,不属同一类的概率越小(即属于同一类的概率越大),
 说明节点上的杂质越小(也叫纯度越纯)。

 
当一个节点的纯度达到最高,即节点上所有样本所属类别都一样时,
说明该节点说明分割得越好,这正是我们想要的结果。

PASS:也可以用ID3中的熵作为收益函数,但CART中更主流的是使用GINI。



  (二)历遍过程   


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


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






 End 







联系小饼