Cart（Classification And Regression Tree）决策树作为决策树算法分支的一条，是一类非线性的模型，从CART决策树的全称不难看出这是一类可用于分类与回归的决策树。
CART算法主要由以下两步组成：
- 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
- 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
CART决策树生成
与多叉决策树ID3，C4.5不同，CART决策树是一棵递归建树的二叉树，，对回归树用平方误差最小化准则，对分类树用基尼系数最小化准则，进行特征选择，生成二叉树。
CART回归决策树生成
输入：训练集D
输出：回归决策树f(x)
记X为输入数据，Y为输出值，且Y为连续变量，给定训练数据集：
D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}D={(x1,y1),(x2,y2),⋯,(xN,yN)}
选择第j个变量xj及其取值s作为切分变量和切分点，并定义两个区域： R 1 ( j , s ) = { x ∣ x j ≤ s } , R 2 ( j , s ) = { x ∣ x j > s } R_{1}(j, s)=\left\{x | x_{j} \leq s\right\}, \quad R_{2}(j, s)=\left\{x | x_{j}>s\right\}R1(j,s)={x∣xj≤s},R2(j,s)={x∣xj>s}
切分点的选取基于最小平方误差准则： j , s = arg min j , s [ min c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] j, s=\arg \min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]j,s=argminj,s[minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2] 其中c1,c2分别为R1,R2区间内的输出平均值，即：
c m = 1 N ∑ x i ∈ R m ( j , s ) y i , m = 1 , 2 c_{m}=\frac{1}{N} \sum_{x_{i} \in R_{m}(j, s)} y_{i}, \quad m=1,2cm=N1∑xi∈Rm(j,s)yi,m=1,2对切分好的区域继续进行切分，依然切分为两部分，并基于最小平方误差计算切分点。
重复3操作直至无法继续切分，最后将空间划分为M个区域R1,R2,⋯,RM ，在每个区域上的输出为cm,m=1,2,⋯,M，CART回归树可表示为：
f ( x ) = ∑ m = 1 M c ^ m I ( x ∈ R m ) f(x)=\sum_{m=1}^{M} \hat{c}_{m} I\left(x \in R_{m}\right)f(x)=∑m=1Mc^mI(x∈Rm)
总结：此方法的复杂度较高，尤其在每次寻找切分点时，需要遍历当前所有特征的所有可能取值，假如总共有F个特征，每个特征有N个取值，生成的决策树有S个内部节点，则该算法的时间复杂度为：O ( F ⋆ N ⋆ S ) \mathbf{O}\left(\mathbf{F}^{\star} \mathbf{N}^{\star} \mathbf{S}\right)O(F⋆N⋆S)。
CART分类决策树生成
输入：训练数据集D，特征A，阈值ε
输出：分类决策树
- 设训练集为D，共有k个不同类别对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割成D1和D2两部分，并计算Gini(D,A)：
D 1 = { ( x , y ) ∣ A ( x ) = a } , D 2 = D − D 1 D_{1}=\{(x, y) | A(x)=a\}, \quad D_{2}=D-D_{1}D1={(x,y)∣A(x)=a},D2=D−D1
Gini ( D , A ) = ∣ D 1 ∣ ∣ D ∣ Gini ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ Gini ( D 2 ) \operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right)Gini(D,A)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)
其中Gini ( D ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 \operatorname{Gini}(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}Gini(D)=1−∑k=1K(∣D∣∣Ck∣)2为基尼指数，|Ck|表示属于第k类的样本个数，|D|表示数据集样本总数，基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也越大，这一点与熵类似。 - 与回归树相类似，选取使得基尼指数Gini(D,A)最小的特征及其对应的切分点（如A=a）作为最优特征与最优切分点。依此从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
- 对2中分配好的节点继续进行1，2操作，直至满足停止条件（算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值，或者没有更多特征）。
- 生成分类决策树
总结：CART分类决策树复杂度计算与回归决策树类似
CART决策树剪枝
剪枝目的：决策树是一类很容易过拟合的非线性机器学习模型，合理的剪枝可以有效的降低其过拟合程度
大致思路：对于原始的CART树T0，先剪去一棵子树，生成子树T1，然后再从A1剪去一棵子树生成T2，直到最后剪到只剩一个根结点的子树Tn，于是得到了T0-TN一共n+1棵子树。
然后再用n+1棵子树预测独立的验证数据集，谁的误差最小就选谁
输入：CART决策树T0
输出：最优决策树Tα
记决策树字子数序列为T0,T1,…,Tn
设k=0,T=T0
设α=+∞
自下而上地对各内部结点t计算C(Tt),|Tt|，以及
g ( t ) = C ( t ) − C ( T t ) ∣ T t ∣ − 1 g(t)=\frac{C(t)-C\left(T_{t}\right)}{\left|T_{t}\right|-1}g(t)=∣Tt∣−1C(t)−C(Tt)
α = min ( α , g ( t ) ) \alpha=\min (\alpha, g(t))α=min(α,g(t))
其中，Tt表示以t为根结点的子树，C(Tt)是对训练数据的预测误差，|Tt|是Tt的叶结点个数。g(t) 为裁剪阈值，每次与之前所存的最小的g(t)对比自下而上地访问内部结点t，如果有g(t)=α，则进行剪枝，并对叶结点t以多数表决法决定其类别，得到树T
设k=k+1,αk=α,Tk=T
如果T不是由根结点单独构成的树，则回到步骤4.
采用交叉验证法在子树序列T0,T1,⋯,Tn中选取最优子树Tα