CART(Classfication and Regression Tree)算法是目前决策树算法最为成熟的一类算法，应用范围比较广泛。它既可用于分类，也可以用于预测。

一、回归算法原理

在预测中，CART使用最小剩余方差(Squared Residuals Minimization)来判定回归树的最优划分，这个准则期望划分之后的子树与样本点的误差方差最小。这样决策树的将数据集切成很多子模型数据，然后利用线性回归技术来建模。如果每次切分后的数据仍然难以拟合，就继续切分。在这种切分方式下创建预测树，每个叶子节点都是一个线性回归模型。这些线性回归模型反映了样本集合中蕴含的模式，也称模型树。
CART不仅支持整体预测，也支持局部模式的预测，并有能力从整体中找到模式，或根据模式组合成一个整体。整体和模式之间的相互结合，对于预测分析具有十分重要的意义。

二、算法流程

决策树主函数： 决策树的主函数是一个递归函数。主要用来按CART的规则生长出决策树的各个分支节点，并根据终止条件结束算法：
1）输入需要分类的数据集合类别标签。
2）使用最小剩余方差法判定回归树的最优划分，并创建特征的划分节点——最小剩余方差子函数。
3)在划分节点划分数据集为两部分——二分数据集子函数。
4）根据二分数据的结果创建出新的左、右节点，作为树生长的两个分支。
5）检验是否符合递归的终止条件。
6）将划分的新节点包含的数据集合类别标签作为输入，递归执行上述步骤。
使用最小剩余方差子函数 ，计算数据集各列的最优划分方差，划分列，划分值。
二分数据集： 根据给定的分隔列和分隔值将数据集一分为二，分别返回。
剪枝策略： 使用先剪枝和后剪枝策略对计算出的决策树进行剪枝。

三、最小剩余方差法

CART选择最优划分点的方法，首先求取划分数据列的均值和总方差。总方差的计算方法有两种：
1.求取均值std,计算每个数据点与std的方差，然后将n个点求和。
2.求取方差var,然后var_sum=var*n，n为数据集数据数目。
对应地，每次最佳分支特征的选取过程如下：
(1)先令最佳方差为无限大bestVar=inf;
(2)依次遍历所有特征列及每个特征列的所有样本点，在每个样本点上二分数据集；
(3)计算二分数据集后的总方差currentVar（划分后左右子数据集的总方差之和），如果currentVar< bestVar,则bestVar=currentVar
(4)返回计算的最优分支特征列、分支特征值（连续特征则为划分点的值），以及左右分支子数据集到主程序。

四、模型树

模型树具有很多优秀的性质，它包含了如下的特性：
1）一般而言，样本总体的重复性不会很高，但局部模式经常重复。类似于历史不会重复，但会重演；
2）模型给出了数据的范围，它可能是一个时间范围，也可以是一个空间范围；而且模型还给出变化的趋势，可以是曲线，也可以是直线，这依赖于使用的回归算法；
3）传统的回归方法，无论是线性回归还是非线性回归，都不如模型树包含的信息丰富，模型树具有更高的预测准确度。

五、剪枝策略

因为使用了连续的数据，CART可以生长出大量的分支树，为了避免过拟合的问题，预测树采用了剪枝的方法。剪枝方法主要包括先剪枝和后剪枝。
先剪枝： 给出一个预定义的划分阈值，当节点的划分子集某个标准低于预定义的阈值时，子集划分将终止。 选取合适的阈值比较困难，过高将导致过拟合，过低将导致欠拟合。它的优势是不必生成整棵决策树，算法简单，效率高，适合大规模问题的粗略估计
后剪枝： 后剪枝指在完全生成的决策树上，根据一定的规则标准，减掉树中不具备一般代表性的子树，使用叶子节点替代。