本站原创文章，转载请说明来自《老饼讲解-机器学习》ml.bbbdata.com

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

本文讲解决策树构造的具体详细过程

本文讲述的构造流程来源于matlab决策树软件包，与sklearn的大同小异，相对更为简洁

   01. CART决策树的构建目标   

在讲述构建流程之前，本节先梳理CART决策树究竟希望构建一棵什么样的树

      CART决策树的构建目标     

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

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

本节讲解CART决策树的构建主流程，个别细节放在一下节细讲

    第一步：根节点分裂    

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

✍️说明
这里遗留两个细节放在下处讲解
 👉 收益的具体评估方法   
 👉【特征，分裂值】的历遍

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

当分裂完根节点后，就产生了两个新节点
 接下来需要判断，新生节点是成为叶子还是需要继续分裂

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

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

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

不断按（二）去迭代，直到没有节点需要分裂
 如下：所有节点都成为叶子节点时，就停止生长
 

     总过程     

分裂的总过程如下：

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

本节补充上面主流程中遗留的收益评估方法与【特征，分裂值】的历遍两个细节

     节点分裂质量评估-收益函数GINI    

 Gini收益函数公式
CART决策树一般用基尼函数的取反函数作为收益函数来评估节点分裂质量

  

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

 GINI收益函数的含义
 GINI收益函数整个公式的意思是，
在左（或右）节点随机抽取两个样本
这两个样本不属于同一类的概率
 公式可以如下解读：
  
 GINI系数为什么代表概率，请看《【附件】决策树GINI系数的推导》

✍️ 补充：GINI系数为什么能作为收益函数
同一个节点，不属同一类的概率越小(即属于同一类的概率越大)，
 说明节点上的杂质越小(也叫纯度越纯)

 当一个节点的纯度达到最高，即节点上所有样本所属类别都一样时，
说明该节点说明分割得越好,这正是我们想要的结果
PASS:也可以用ID3中的熵作为收益函数，但CART中更主流的是使用GINI

   【特征，分裂值】的历遍过程    

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

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

 End