分类与回归树(Classfification And Regression Tree, CART) 模型也是一种决策树模型， 它既可用于分类，也可用于回归。
其学习算法分为如下两步：
第一步：决策树生成。用训练数据生成决策树，生成树尽可能地大。
第二步：决策树剪枝。基于损失函数最小化的标准，用验证数据对生成的决策树剪枝。
分类与回归树模型采用不同的最优化策略。CART回归生成树用平方误差最小化策略，CART分类生成树采用基尼指数最小化策略。
给定训练数据集$ D = {(x_1,y_1),(x_2,y_2),...,(x_N,y_N)},y_i \in R$。设已经将输入空间划分为$M$个单元$R_1,R_2,...R_M$，且在单元$R_m$上输出的值为$c_m,m=1,2,...,M$。则回归树的模型为：
$f(x)=\sum\limits_{m=1}^Mc_mI(x \in R_m)$，其中$I( \cdot )$为示性函数
如果给定输入空间的一个划分，回归树在训练数据集上的误差（平方误差）为：$\sum\limits_{x_i \in R_m}((y_i - f(x_i)))^2$
基于平方误差最小的准则，可以求解出每个单元的最优输出值$\hat{c_m}$，而$\hat{c_m}=ave(y_i | x_i \in R_m)$。它就是$R_m$上所有输入样本对应的输出$y_i$的平均值。
现在需要找到最佳的划分，使得该划分对应的回归树的平方误差在所有的划分中最小。设$x_i = (x_i^{(1)},x_i^{(2)},...,x_i^{(k)})$，即输入为k维。选择第j维$x_i^{(j)}$，它的取值s作为切分变量和切分点。
定义两个区域：
$R_1(j,s) = {x | x^{(j)} \leq s }$
$R_2(j,s) = {x | x^{(j)} > s }$
然后寻求最优切分变量j和最优切分点s，即求解：
$\underset{j,s}{min}[\underset{c_1}{min} \sum\limits_{x_j \in R_1(j,s)} (y_i - c_1)^2 + \underset{c_2}{min} \sum\limits_{x_j \in R_2(j,s)} (y_i - c_1)^2]$
对于给定的维度j可以找到最优切分点s。同时：
$\hat{c_1}=ave(y_i|x_i \in R_1(J,S))$
$\hat{c_2}=ave(y_i|x_i \in R_2(J,S))$
问题是如何求解j？首先遍历所有的维度，找到最优切分维度j，然后对该维度找到最优切分点s构成一个$(j,s)$对，并将输入空间划分为两个区域。然后再子区域中重复划分过程，直到满足停止条件为止。这样的回归树被称为最小二乘回归树。
通常的停止条件为下列条件之一：
$\clubsuit$ 节点中样本个数小于预设值
$\clubsuit$ 样本集的平方误差小于预定值
$\clubsuit$ 没有更多特征
假设有K个分类，样本点属于第k类的概率为$p_k = P(Y = c_k)$。定义概率的基尼指数为：
$$Gini(p)=\sum\limits_{k=1}^Kp_k(1-p_k)=1-\sum\limits_{k=1}^Kp_k^2$$
对于给定的样本集合D，设属于类$c_k$的样本子集为$C_k$，则基尼指数为：
$$Gini(D) = 1 - \sum\limits_{k=1}^K(\frac{|D|}{|C_k|})^2$$
给定特征A，根据其是否取某一个可能值a，样本集D被分为两个子集：$D_1$和$D_2$，其中：
$$D_1 = {(x,y) \in D | x^{(A)} = a }$$
$$D_2 = {(x,y) \in D | x^{(A)} \ne a } = D - D_1$$
定义$Gini(D,A)$：
$$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1,A)+\frac{|D_2|}{|D|}Gini(D_2,A)$$
它表示在特征A的条件下，集合D的基尼指数。对于样本集合D，$Gini(D)$越小说明样本越属于同一类。