首先应该清楚回归树与分类树的本质区别在于模型的输出值不同，如果输出值为连续值则为回归树，如果为离散值则为分类树。

一、CART回归决策树算法原理

（一）、回归树的生成

假设现在已有训练数据集

并且假设已经将输入空间划分为M个单元R1,R2,……RM,此时如果给定输入空间的一个划分，那么回归树在这个划分上的预测误差即为（用平方误差表示如下）：

那么（此处假设为基于平方误差最小的准则）此回归树模型在每个划分单元上的最优输出值即为

上面公式的含义就是Rm单元内包括的样本对应的数据集中y值的平均值

最优特征及最优切分点的选择

那么现在的问题就在于依据什么原则去找到最佳的划分，现在假设样本共有k个特征（k维），假设现在选择第j维和它此时的取值为s，作为划分数据集的特征以及特征值（切分点），将数据集划分为两部分R1，R2:

我们选择最优特征以及最优切分点的准则就是：

怎么理解上面的式子呢，就是对于任意划分特征，对应的任意划分点s两边划分成的数据集R1和R2，求出使R1和R2内各自含有的样本的输出值的平方误差最小，同时两者平方误差之和最小所对应的特征j和特征值划分点s。

（二）、最小二乘回归树生成算法

这里直接贴上李航老师的描述：

这里补充一下一般停止条件有三种：
1.节点中的样本数量小于指定值
2.节点中样本的平方误差小于指定值
3.已经没有更多的特征

二、CART分类树算法原理

（一）、分类树的生成

首先需要知道的是基尼指数这个概念，
基尼指数是用来表示不确定性的一个概念。
对于给定的样本数据集D,它的基尼指数定义为：

此时对于样本数据集D,如果根据特征A是否取其某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数表达式为：

Gini（D)表示数据集D的不确定性，Gini（D,A）表示在A=a分割后D的不确定性，基尼指数越大表明不确定性越大。

最优特征及最优切分点的选择

如何选择最优特征以及切分点呢？依据的原则就是选择的特征A以及它对应的取值a使得Gini（D，A=a)最小。
怎么理解这句话，举个小例子，现在D共有职业A,年龄B,性别C三个特征，其中A可取值为“老师”，“学生”，“其他”，B假设样本中取值就只有“20”，“30”，“40”，C可能取值为“男”，“女”
现在分别计算Gini(D,A="老师“），Gini(D,A="学生“），Gini(D,A="其他“），Gini(D,B="20“）,Gini(D,B="30“）,Gini(D,B="40“）,Gini(D,C="男“），Gini(D,C="女“），然后选出最小的，假设为Gini(D,A="学生“）最小那么这一轮的最优特征就为职业，最优划分点就为是否为学生。

（二）、分类树生成算法

这里直接贴上李航老师的描述：


这里补充一下一般停止条件有三种：
1.节点中的样本数量小于指定值
2.节点中样本的平方误差小于指定值
3.已经没有更多的特征

三、CART对于特征为连续值以及离散值的处理

首先，我们应该知道CART产生的是完全二叉树。
对于CART连续值的处理问题，其思想使将连续的特征离散化。
”具体的思路如下，比如m个样本的连续特征A有m个，从小到大排列为a1,a2,…,am,则CART算法取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点Ti表示为：对于这m-1个点，分别计算以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为at,则小于at的值为类别1，大于at的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与ID3或者C4.5处理离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。“
　 对于特征取值为离散值的处理问题，CART采用的思路是不停的二分离散特征。
回忆下ID3或者C4.5，如果某个特征A被选取建立决策树节点，如果它有A1,A2,A3三种类别，我们会在决策树上一下建立一个三叉的节点。这样导致决策树是多叉树。但是CART分类树使用的方法不同，他采用的是不停的二分，还是这个例子，CART分类树会考虑把A分成{A1}和{A2,A3}, {A2}和{A1,A3}, {A3}和{A1,A2}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3},然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的节点。同时，由于这次没有把特征A的取值完全分开，后面我们还有机会在子节点继续选择到特征A来划分A1和A3。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立。
　　对于CART分类树离散值的处理问题，采用的思路是不停的二分离散特征。
　　回忆下ID3或者C4.5，如果某个特征A被选取建立决策树节点，如果它有A1,A2,A3三种类别，我们会在决策树上一下建立一个三叉的节点。这样导致决策树是多叉树。但是CART分类树使用的方法不同，他采用的是不停的二分，还是这个例子，CART分类树会考虑把A分成{A1}和{A2,A3}, {A2}和{A1,A3}, {A3}和{A1,A2}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3},然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的节点。同时，由于这次没有把特征A的取值完全分开，后面我们还有机会在子节点继续选择到特征A来划分A1和A3。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立。"这段话是刘建平老师博客里的讲解，其实对于回归树同样适用，不同的是依据使平方误差和最小的准则去选择最优特征和最优切分点

参考

李航《统计学习方法》
刘建平老师博客