分类回归树(CART)模型是由L.布赖曼等人于1984年提出的一种应用广泛的决策树方法，基于树的方法把特征空间划分为一系列的矩形区域，在每一个区域中拟合一个简单的预测模型（如常数模型）。分类回归树(CART)模型由特征选择、树的生成及其剪枝组成，既可以用于分类也可以用于回归。CART是在给定输入特征变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征取值为“是”或“否”，树每个节点的左分支表示取值为“是”，右分支表示取值为“否”。该算法等价于递归地二分每个特征，将特征空间划分为一系列矩形区域，并在每个区域拟合一个预测模型。例如，左边的图表示利用两个特征变量和将特征空间分成了5个矩形区域，右边的图表示对应的树模型（见图）。比如，首先生成的树在点进行分叉，如果小于等于，那就考虑左边的分支；接下来，考虑树在点进行分叉，如果大于，那就考虑右边的分支，从而落入区域。

分类回归树示例图

递归构建二叉决策树，对回归树用平方误差最小的准则，对分类树用基尼指数（Gini Index）最小化准则，进行特征选择，生成二叉树。

假设和分别为输入和输出变量，且为连续变量，将已输入空间划分为个单元，为空间划分的示性函数，并且在每个单元上有一个固定的输出值，建立回归树模型为：

用平方误差最小的准则求解每个单元上的最优输出值，即输出单元上样本响应变量的均值：

在选择如何对输入空间进行划分时，选取第个变量和它的取值，作为切分变量和切分点，以此先将输入空间划分为两个区域，分别记为，。对于给定变量，求解以下最优化问题可以得到最优切分点：

重复上述划分过程直至满足条件生成一棵回归树，这样的回归树通常称为最小二乘回归树（least squares regression tree）。

假设有个类，样本点属于第类的概率为，则概率分布的基尼系数定义为

对于给定样本集合，其基尼系数为：

式中为样本中属于第类的数量，为样本总量。

如果样本集合根据特征是否取值分成两部分和，在特征的条件下，集合的基尼系数定义为：

基尼系数表示集合的不确定性，基尼系数表示经分割后集合的不确定性。基尼系数数值越大，表明样本集合的不确定性越大。

CART分类决策树的生成通过递归地对每个节点进行如下操作得到。首先，对每个特征和其可能的每个取值（假设特征是离散的，如果是连续的就考虑利用二分法切分特征），计算在该特征条件下的样本集合的基尼系数。然后，在所有特征和所有可能的切分点中选择基尼指数最小的特征及其对应的切分点，并利用该对应的特征及其切分点生成两个子节点，将训练样本依该特征切分点分配到两个子节点中去。最后，对两个子节点递归地调用前面两步，直至满足停止条件，生成分类决策树。

CART剪枝算法从“完全生长”的决策树的底端剪去一些子树，使决策树变小（模型变简单），从而避免过拟合，提高模型预测能力。CART剪枝算法由两步组成：首先，从生成算法产生的决策树底端开始不断剪枝，直到的根节点，形成一个子树序列。然后，通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。