分类与回归树模型同样由特征选择，树的生成和剪枝组成既可用于分类也可以用于回归。
算法的组成
CART算法由一下两个部分组成：
（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽可能的大；
（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
回归问题
CART生成
决策树的生成就是递归的构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。
假设X与Y分别为输入和输出变量，并且Y是连续的。给定训练数据集D。
一个回归树对应着输入空间（即特征空间）的一个划分已经在划分的单元上的输出值。假设已经输入空间划分为M个单元$R_1,R_2,…,R_M$,并且在每个单元R_n上有一个固定的输出值c_n,于是回归树模型可以表示为
当输入孔家你得划分确定是，可以用平方误差$\sum_{x_i \in R_m}(y_i-f(x_i))^2$来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。我们可以知道，某个单元上的最优的值c_m 是R_m上所有输入实例x对应的输出y的均值，意思就是 如果好多样本都在一个叶子结点中，那么这个叶子结点最好的输出值（就是让损失函数最小）就是这些样样本对应y的均值。
现在问题来了，我们应该对输入空间怎么划分。这里采用启发式的方法，选择第j个变量$x^{(j)}$和他的取值s，作为切分变量和切分点，并定义两个区域。
A区域就是考察所有样本的第j个变量，如果小于等于s，则把这些样本划分到A区域，其余都是大于s的，所以就划分到B区域。
那现在问题就变成，如何找到最优的切分变量j和最优切分点s.具体的我们来求解：
用我自己的话解释就是，我遍历每一个特征，对特征进行尝试切分：
如果是离散变量，那么我们就遍历这个变量中的每个可选址值，假设是k，把所有样本分成2类（是k的属于一类，不是k的属于另外一类，因为必须是二叉树），然后计算损失函数，看看这个可选值是否可以最好切分点。计算损失函数的话，那么我们可以知道我们把所有样本分成了2个叶子结点，我们计算每个叶子结点中样本y的平均值当做这个叶子结点的输出，然后再用上面的公式计算，然后记住这个值，然后计算所有的可选值，并把他们都记住。
如果是连续变量，那么我们也可以遍历这个变量的所有取值，每种取值都可以把样本分成2类，小于等于这个取值的和大于这个取值的，然后按照上面的方法遍历计算，保存每次计算的值，最后对比所有 计算的值，找到最小的那个值，就把那个特征当做要切分的特征，那个点当做切分点。
用书面语说就是：遍历所有的输入变量，找到最优的切分变量j，构成一个对(j,s)。依此将输入空间划分为2个区域。接着对每个区域重复上述划分的过程，知道满足停止条件为止。这样就生成了一颗回归树。这样的回归树通常称为最小二乘回归树
分类问题
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
分类问题中，假设有K个类，样本点属于第k个类的概率为$pk$,则概率分布的基尼指数定义为
$$Gini(p)=\sum{k=1}^Kpk(1-p_k)=1-\sum{k=1}^Kpk^2Gini(p)=2p(1-p)Gini(D)=1-\sum{k=1}^K(\frac{|C_k|}{|D|})^2D_1={(x,y)\in D|A(x)=a},D_2=D-D_1Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D2)$$
基尼指数Gini（D）表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性，基尼指数值越大，样本集合的不确定性也就越大，这和熵类似。
CART生成算法
输入：训练数据集D和停止计算的条件
输出：CART决策树
根据D，从根节点开始，递归的对每个结点进行以下操作，构建二叉决策树：
（1）设结点的训练数据集是D，计算现有的葛铮对该数据集的基尼指数。此时对每个特征A，对其可能去的每个值a,根据样本点对A=a测试为‘是’或者‘否’将D分割为$D_1和D_2$，利用公式计算A=a是的基尼指数。
（2）在所有可能的特征A以及他们所有可能的切分点a钟，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依照最优特征与最优切分点，生成2个子结点，将训练数据集依特征分配到两个子结点中去。
（3）对两个子结点递归的调用（1）（2），直至满足停止条件。
（4）生成CART决策树。
算法停止计算的条件是结点中的样本个数小于预定的阈值，或者样本集的基尼指数小于预定的阈值（这说明样本基本属于同一类），或者没有更多的特征可以进行划分。
这篇文章里有一个回归树做回归问题的例子，可以看一下。
回归树例子
