1 CART，又名分类回归树

CART，分类回归树，是几乎所有复杂决策树算法的基础，有以下特点：

（1）CART是一棵二叉树；
（2）CART既能是分类树，又能是回归树，由目标任务决定；
（3）当CART是分类树时，采用GINI值作为结点分裂的依据；当CART是回归树时，采用MSE(均方误差)作为结点分裂的依据；

2 分类树和回归树的区别？

针对分类任务，就是分类树；针对回归任务，就是回归树。
分类任务：预测目标是离散值，例如预测该用户是否会逾期，逾期是一类，用1表示，不逾期是另一类，用0表示。分类树采用GINI值作为结点分裂的依据；
回归任务：预测目标是连续值，例如预测用户的身高。回归树采用MSE(均方误差)作为结点分裂的依据。

下面以回归树为例，详细写一下树的分裂和生成过程。

3 回归树算法详解

回归树的算法详解，其实就是回归树的生成过程，说的是一回事儿。

• 样本集：Samples = {$s_1,s_2,...,s_N$}，有N个样本
• 特征集：Features = {$f_1,f_2,...,f_M$}，每一个样本对应一组特征
• 目标值/真实值 集合：T ={$t_1,t_2,...,t_N$}，每一个样本对应一个目标值，对于回归任务来说，每一个目标值都是一个具有连续值属性的数值。

3.1 步骤如下

1、原始数据集$S$，此时树的深度$depth$=0。
2、针对集合$S$，遍历每一个$feature$的每一个$value$，用该$value$将原数据集$S$分裂成2个集合：左集合$S_{left}$(<=value的样本)、右集合$S_{right}$(>value的样本)，每一个集合也叫做一个结点。分别计算这2个集合的mse，找到使得$(lef{t}_{mse}+righ{t}_{mse})$最小的那个$value$，记录下此时的$feature$名称和$value$，这个就是最佳分割特征以及该特征的最佳分割值；
每一个集合/结点$mse$的计算方法如下：

1、$mean=\frac{1}{N}{\sum }_{i=1}^N{y}_i$，其中$N$为该集合内样本总数，$y_i$为该集合内每一个样本的目标值（ps：这个mean就是该结点的值，也就是落在该结点内的样本的预测值，同一个结点中的样本具有同一个预测值。）
2、$mse={\sum }_{i=1}^N(y_i-mean{)}^2$

为什么要用均方差mse来作为分裂的依据呢？

只要是能衡量预测值和真实值/目标值之间的差距的数学公式，都可以用，例如信息增益、信息增益比、基尼系数等等。但是均方差有更好的好处：一阶导数和二阶导数可求并好求。

3、找到最佳分割$feature$以及最佳分割$value$之后，用该$value$将集合S分裂成2个集合：左集合$S_{left}$、右集合$S_{right}$，每一个集合也叫做一个结点。此时树的深度depth += 1。
4、针对集合$S_{left}、S_{right}$分别重复步骤2,3，直到达到终止条件。

一）终止条件有：
1、特征已经用完了：没有可供使用的特征再进行分裂了，则树停止分裂；
2、子结点中的样本已经都是同一类：此时，样本已经全部被划分出来了，不用再进行区分，该结点停止分裂（不过一般很难达到，达到的话，该树肯定过拟合）；
3、子节点中没有样本了：此时该结点已经没有样本可供划分，该结点停止分裂；
二）很多复杂的决策树算法（例如lightgbm）中还有额外的终止条件，为了防止过拟合：
1、树达到了最大深度：depth >= max_depth，树停止分裂。
2、结点的样本数量达到了阈值：如果一个集合（结点）的样本数量 < min_samples_leaf，则树停止分裂；
其中，max_depth和min_samples_leaf都是人为制定的超参数。

5、最后生成的、不再进行分裂的集合就叫做叶子结点。落在该叶子节点内的样本的预测值，就是该叶子结点的值。同一个叶子结点中的样本具有同一个预测值。

叶子结点值的计算方法：$mean=\frac{1}{N}{\sum }_{i=1}^N{y}_i$