CART树

CART（classification and regression tree）算法是分类回归树算法，它是决策树的一种实现。决策树一般有ID3,ID4.5和CART这三种算法。CART树是一颗二分树，它通过二分递归分割，在每个节点将样本空间进行分割，它在每步决策时只有是、否两种选择。
决策树的算法主要包括树生成和剪枝两步骤。本文主要讲述的是树的生成步骤。
CART树生成的主要思想就是分裂。每个准备分裂的节点，都会从数据集中选择一个最优特征的最优值作为分裂的条件，将数据分成两部分。接下来，我们界定什么是“最优”。在分类问题上，使用Gini系数来确定，在回归问题上，使用平方误差来界定。使得模型的gini系数越小、平方误差越小的特征值，就是“优” 的特征值。

1. 树模型的输入都是1*n的vector，需要把所有feature都拍平了放进去。
2. cart树每次节点分裂的时候，遍历每个feature的每个value，将dataset分为在该feature上小于选定value的部分和大于选定value的部分，根据损失函数计算两部分的loss，分类问题计算gini系数，回归问题计算平方误差。遍历结束挑出使得损失最低的feature的value，然后将数据分成两部分，左子树输入的是选出feature的value小于best value的，右边是大于best value的部分

3. 这样递归，会碰到边界条件，例如树的深度达到了，或者是数据量缩小到一定程度。然后根据叶子节点得到的数据，对样本y值求平均得到预测值。
   模型在predict的时候，根据节点的feature和value，可以一步步走到叶子节点，得到叶子节点存放的预测值。

   
   cart tree

参考：
https://machinelearninggao.readthedocs.io/zh/stable/9.树回归/
https://zhuanlan.zhihu.com/p/128472955