一类特殊的决策树算法——CART，Classification And Regression Tree。

1.0 CART简介

顾名思义，CART算法既可以用于创建分类树（Classification Tree）解决分类问题，也可以用于创建回归树（Regression Tree）解决回归问题，两者在建树的过程稍有差异。根据某一个维度d和某一个阈值v进行二分，得到的决策树是二叉树。

sklearn中可以通过设置criterion参数gini和entropy来选择构建树模型的算法是CART还是ID3。CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。 ID3中使用了信息增益选择特征，增益大优先选择，这和gini是相反。

2.0 分类树CART

2.1 离散特征

CART分类树算法对离散值的处理，采用的思路：不停地二分离散特征：

在ID3或C4.5，特征A被选取建立决策树节点，如果它有3个类别{A1,A2A3}，我们会在决策树上建立一个三叉点，这样决策树是多叉树。

CART采用的是不停的二分。会考虑把特征A分成f'vff{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的一颗子树中，离散特征只会参与一次节点的建立，即三叉树就划分完毕了。

2.2 连续特征

CART分类树算法对连续值的处理思想和C4.5相同，都是将连续的特征离散化。唯一区别在选择划分点时，C4.5是信息增益比，CART是基尼系数。

具体思路：m个样本的连续特征A有m个取值，从小到大排列，取相邻两样本值的平均数作为划分点，一共取m-1个。分别计算以这m-1个点作为二元分类点时的基尼系数。选择基尼系数最小的点为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为a*，则小于a*的值为类别1，大于a*的值为类别2，这样就做到了连续特征的离散化。另外，对于连续属性先进行排序（升序），只有在决策属性（即分类发生了变化）发生改变的地方才需要切开，这可以显著减少运算量。

（注：在ID3或C4.5的一颗子树中，（离散）特征只会参与一次节点的建立；CART中，无论是离散特征还是连续特征，该属性特征仍然有可能再次参与子节点产生的选择过程。）

2.3 CART分类树的构建思路

CART分类树建立算法流程，包含有剪枝，剪枝方法采用限制节点分割的最小样本数：

从根节点开始，用训练集递归建立CART分类树。

输入:训练集D，基尼系数的阈值，样本个数阈值

输出:决策树T。

S1：对于当前节点的数据集为D，如果样本个数小于阈值或没有特征，将当前节点作为叶节点，将该叶节点里概率最大的类别作为节点标签，停止递归，返回决策子树。

S2：计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。

S3：计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数。

S4：在计算出来的基尼系数中，选择基尼系数最小的最优特征A和对应的最优特征值a，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，左节点的数据集D为D1，右节点的数据集D为D2。

S5：对左右的子节点递归的调用1-4步，生成决策树。

3.0 回归树CART

3.1 回归思路

当数据拥有众多特征并且特征之间关系十分复杂时，构建全局模型的想法就显得太难了，也略显笨拙。而且，实际生活中很多问题都是非线性的，不可能使用全局线性模型来拟合任何数据。一种可行的方法是将数据集切分成很多份易建模的数据，然后利用线性回归技术来建模。如果首次切分后仍然难以拟合线性模型就继续切分。在这种切分方式下，树结构和回归法就相当有用。

CART回归树 vs. CART分类树：

1）二者建立过程类似，区别在于样本的输出，分类树输出的是离散值，是类别标签；回归树输出的是连续值，是一个数值。

2）分类树采用基尼系数的大小度量特征各种划分的好坏，回归树采用最小化均方差和进行最优划分特征的选择，对于划分特征A，划分点s两边的数据集D1和D2，求出使D1和D2各自集合的均方差最小、且D1和D2的均方差之和最小的特征和特征值划分点。

3）CART分类树采用该叶子节点里概率最大的标签作为当前节点的预测结果。回归树则采用叶子节点的均值或者中位数来预测输出结果。（这中结果选择方式和KNN一样）。

3.2 CART的剪枝策略

CART采用的办法是后剪枝法，可概括为两步：

S1：从原始决策树生成各种剪枝效果的决策树

S2：用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的树作为最终的CART树。

具体来说，假设有节点 $T$ ，和以 $T$ 为根节点的子树 $T_t$ ，如果没有剪枝，它的损失函数是 $Loss(T_t) = E(t)+\alpha \vert n \vert$ 。其中 $\alpha$ 是正则化因子， $\vert n \vert$ 是子树的结点的个数， $E(t)$ 为子树训练数据的预测误差。如果将其剪掉，仅仅保留根节点，则损失是 $Loss(T) = E(T)+\alpha$ 。