CART算法

引言
1、概述
2、CART算法

2.1 CART生成

2.1.1 回归树的生成
2.1.2 分类树的生成

2.2 CART剪枝

2.2.1 剪枝，形成一个子树序列
2.2.2 在剪枝得到的子树序列 $T_0,T_1,T_2,T_3......T_n$ 中通过交叉验证选取最优子树 $T_\alpha$
2.2.3 CART剪枝算法

3、决策树算法小结

引言

$\quad \quad$ 在决策树、ID3、C4.5算法一文中，简单地介绍了决策树模型，以及决策树生成算法ID3算法和ID3算法的改进版C4.5算法；在决策时剪枝算法一文中，简单地介绍了剪枝的算法。我们也提到了它的不足，比如模型是用较为复杂的熵来度量，使用了相对较为复杂的多叉树，只能处理分类不能处理回归等。对于这些问题， CART算法大部分做了改进。CART算法也就是我们下面的重点了。由于CART算法可以做回归，也可以做分类，我们分别加以介绍，先从CART分类树算法开始，重点比较和C4.5算法的不同点。接着介绍CART回归树算法，重点介绍和CART分类树的不同点。然后我们讨论CART树的建树算法和剪枝算法，最后总结决策树算法的优缺点。

1、概述

$\quad \quad$ CART，又名分类回归树，既可以用于分类又可以用于回归。

$\quad \quad$ 有以下特点：

（1）CART是一棵二叉树；
（2）CART既能是分类树，又能是回归树，由目标任务决定；
（3）当CART是分类树时，采用GINI值作为结点分裂的依据；当CART是回归树时，采用MSE(均方误差)作为结点分裂的依据；

2、CART算法

$\quad \quad$ CART算法由以下两步生成：
（1）决策树生成：基于训练数据集生成决策树。生成的决策树要尽量大；
（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

2.1 CART生成

$\quad \quad$ 决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准测，对分类树用基尼指数（GINI）最小化准则，进行特征选择，生成二叉树。

2.1.1 回归树的生成

划分的准则是平方误差最小化

$\quad \quad$ 假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集 $D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_n)\}$
假定已将输入空间划分为M个单元 $R_1,R_2,...,R_M$ ，并且在每个单元 $R_M$ 上有一个固定的输出值 $c_m$ ,则

回归模型：
$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$
预测误差：平方误差
$\sum_{x_i\in R_m}(y_i-f(x_i))^2$

如何选择每一个单元上的最有输出值 $c_m$ ？

$\quad \quad$ 用平方误差最小的准则求解每个单元上的最有输出值得单元 $R_M$ 上的 $c_m$ 的最优值 $\hat{c_m}$ 是 $R_M$ 上的所有输入实例 $x_i$ 对应的输出 $y_i$ 的均值，即
$\hat{c_m}=ave(y_i|x_i\in R_m)$

如何对输入空间进行划分？

采用启发式的方法，选择第j个变量 $x^{(j)}$ 和它的取值s，作为切分变量和切分点，并定义两个区域：
$R_1(j,s)=\{x|x^{(j)}\leq s\} \ 和\ R_2(j,s)=\{x|x^{(j)}> s\}$
然后寻找最优切分变量j和最优切分点。具体地，求解
$\mathop{min}\limits_{j,s}[\mathop{min}\limits_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\mathop{min}\limits_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^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)$ ，依次将输入空间划分为两个区域。接着，对每一个区域重复上述划分过程，直到满足停止条件为止。这样就生成一棵回归树。这样的回归树通常称为最小二乘回归树。算法具体流程如下：

算法5.5 （最小二乘回归树生成算法）
输入：训练数据集D
输出：回归树 $f(x)$
在训练数据集所在的输入空间中，递归地将每一个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
（1）选择最优切分变量 j 和切分点 s，具体操作是求解使
$\mathop{min}\limits_{j,s}[\mathop{min}\limits_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\mathop{min}\limits_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$ 最小的对 (j,s)
（2）用选定的对 (j,s) 划分区域，并决定相应的输出值 c：
$R_1(j,s)=\{x|x^{(j)}\leq s\} \ ，\ R_2(j,s)=\{x|x^{(j)}> s\}\\ \hat{c_m}=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i\,x\in R_m,m=1,2$
（3）继续对两个子区域调用步骤（1）（2），直至满足停止条件。
（4）将输入空间划分为M个区域 $R_1,R_2,...,R_M$ ,生成决策树：
$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$

2.1.2 分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

定义（基尼指数）：

$\quad \quad$ 分类问题中，假设有 $K$ 个类别，样本点属于第 $k$ 类别的概率为 $p_k$ , 则概率分布的基尼指数定义为：
$Gini(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}p_k^2$
$\quad \quad$ 对于二分类问题，若样本点属于第1个类的概率是p,则概率分布的基尼指数为 $Gini(p)=2p(1-p)$
$\quad \quad$ 对于给定的样本集合 $D$ ,假设有 $K$ 个类别, 第k个类别的数量为 $C_k$ ,则样本D的基尼系数表达式为：
$Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2$

$\quad \quad$ 特别的，对于样本 $D$ ,如果根据特征 $A$ 的某个值a,把 $D$ 分成 $D_1$ 和 $D_2$ 两部分，则在特征 $A$ 的条件下， $D$ 的基尼指数表达式为：

$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$

$\quad \quad$ 基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼指数 $Gini(D，A)$ 表示经 $A=a$ 分割后集合 $D$ 的不确定性。基尼指数越大，样本集合的不确定性也就越大，这一点与熵相似。

$\quad \quad$ 对于二类分类，基尼指数和熵之半以及分类误差率的曲线如下：
机器学习笔记21——决策树之CART算法原理及python实现案例
$\quad \quad$ 从上图可以看出，基尼系数和熵之半的曲线非常接近，仅仅在45度角附近误差稍大。因此，基尼系数可以做为熵模型的一个近似替代。而CART分类树算法就是使用的基尼系数来选择决策树的特征。同时，为了进一步简化，CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。这样一可以进一步简化基尼系数的计算，二可以建立一个更加优雅的二叉树模型。

$\quad \quad$ 分类树生成算法具体如下：

输入：训练数据集，停止计算的条件
输出：CART决策树即分类树
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树
（1）训练数据集为D,计算现有特征对训练数据集的基尼指数，此时对于每一个特征A,对其可能取得每一个值a，根据此值将训练样本切分为 $D_1$ 和 $D_2$ 两部分，然后根据上式计算A=a基尼指数。
（2）在所有可能的特征A以及所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优的特征及切分点，从结点生成两个子结点，将训练数据集分配到子结点中去。
（3）递归的调用（1 ），（2），直到满足停止的条件
（4）生成分类决策树

$\quad \quad$ 算法停止计算的条件是节点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。

2.2 CART剪枝

$\quad \quad$ 由于决策时算法很容易对训练集过拟合，而导致泛化能力差，为了解决这个问题，我们需要对CART树进行剪枝，即类似于线性回归的正则化，来增加决策树的泛化能力。但是，有很多的剪枝方法，我们应该这么选择呢？CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。

$\quad \quad$ CART回归树和CART分类树的剪枝策略除了在度量损失的时候一个使用均方差，一个使用基尼系数，算法基本完全一样。

$\quad \quad$ CART剪枝算法由两步组成：

首先从生成算法产生的决策树 $T_0$ 底端开始不断的剪枝，直到 $T_0$ 的根结点，形成子树序列 $\{T_0,T_1,T_2,T_3......T_n\}$ $T_0$ 就是没剪的，T1就是剪了一个叶结点的，T2就是又剪了一点的这样子哦！
然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树，具体操作如下。

2.2.1 剪枝，形成一个子树序列

$\quad \quad$ 在剪枝的过程中，对于任意的一刻子树T,其损失函数为：
$C_\alpha(T)=C(T)+\alpha|T|$

$\quad \quad$ 其中， $T$ 为任意子树，C(T)为训练数据的预测误差，分类树是用基尼系数度量，回归树是均方差度量， $|T|$ 为子树的叶节点个数， $\alpha\geq0$ 为正则化参数，权衡训练数据的拟合程度与模型的复杂度。
$\quad \quad$ 当α=0时，即没有正则化，原始的生成的CART树即为最优子树。当α=∞时，即正则化强度达到最大，此时由原始的生成的CART树的根节点组成的单节点树为最优子树。当然，这是两种极端情况。一般来说，α越大，则剪枝剪的越厉害，生成的最优子树相比原生决策树就越偏小。对于固定的α，一定存在使损失函数 $C_α(T)$ 最小的唯一子树。

剪枝的思路:
$\quad \quad$ 可以用递归的方法对树进行剪枝。将 $\alpha$ 从小增大， $0=\alpha_0<\alpha_1<...<\alpha_n<+∞$ ,产生一系列的区间 $[\alpha_i,\alpha_{i+1}),i=0,1,...,n$ ;剪枝得到的子树序列对应着区间 $\alpha\in[\alpha_i,\alpha_{i+1}),i=0,1,...,n$ 的最优子树序列 $\{T_0,T_1,...,T_n\}$ ,序列中的子树是嵌套的。

$\quad \quad$ 具体地，从整体数 $T_0$ 开始剪枝。

对 $T_0$ 的任意内部结点t,以t为单结点树的损失函数为
$C_\alpha(t)=C(t)+\alpha$
以t为根节点的子树 $T_t$ 的损失函数是
$C_\alpha(T_t)=C(T_t)+\alpha|T_t|$
当α=0或者α很小时， $C_α(T_t)<C_α(t)$ , 当α增大到一定的程度时,在某一 $\alpha$ 有
$C_α(T_t)=C_α(t)$
当α继续增大时不等式反向，也就是说，如果满足下式：

$α=\frac{C(T)−C(T_t)}{|T_t|−1}$
$T_t$ 和t有相同的损失函数，但是t节点更少，因此t比 $T_t$ 更可取，对 $T_t$ 进行剪枝。

$\quad \quad$ 为此，对 $T_0$ 中每一内部结点t，计算
$g(t)=\frac{C(T)−C(T_t)}{|T_t|−1}$
它表示剪枝后整体损失函数减少的程度。在 $T_0$ 中剪去 $g(t)$ 最小的 $T_t$ ，将得到的子树作为 $T_1$ ，同时将最小的 $g(t)$ 设为 $\alpha_1$ 。 $T_1$ 为区间 $[\alpha_1,\alpha_2)$ 的最优子树。

$\quad \quad$ 如此剪枝下去，直至得到根结点。在这一过程中，不断地增加 $\alpha$ 的值，产生新的区间。

2.2.2 在剪枝得到的子树序列 $T_0,T_1,T_2,T_3......T_n$ 中通过交叉验证选取最优子树 $T_\alpha$

$\quad \quad$ 利用平方误差准则或者是基尼指数准则，在新的验证集中分别测试子树序列，选取里面最优的子树进行输出，便是裁剪之后的子树，即得到最优决策树

2.2.3 CART剪枝算法

算法 5.7 （CART 剪枝算法）
输入：CART算法生成的决策树
输出：最优决策树 $T_\alpha$
（1）设 $k=0$ , $T=T_0$
（2）设 $\alpha=+∞$ （正无穷）
（3）自下而上的对内部结点t进行计算 $C(T_t)$ , $|T_t|$ 和 $g(t)=\frac{C(t)-C(T_{t})}{|T_{t}|-1}，\alpha=min(\alpha,g(t))$
其中， $T_t$ 表示以t为根结点的子树， $C(T_t)$ 是对训练数据的预测误差， $|T_t|$ 是 $T_t$ 的叶结点个数。
（4）自上而下地访问内部结点t，如果有 $g(t)=\alpha$ 的内部结点,则进行剪枝，并对叶结点t以多数表决法决定其类，得到树T
（5）设 $k=k+1,\alpha_k=\alpha，T_k=T$
（6 ）如果T不是由根结点单独构成的树，回到步骤4,
（7 ）采用交叉验证法在子树序列上进行验证选取最优子树 $T_\alpha$

3、决策树算法小结

机器学习笔记21——决策树之CART算法原理及python实现案例

首先我们看看决策树算法的优点：

1）简单直观，生成的决策树很直观。

2）基本不需要预处理，不需要提前归一化，处理缺失值。

3）使用决策树预测的代价是O(log2m)。 m为样本数。

4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。

5）可以处理多维度输出的分类问题。

6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释

7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。

8）对于异常点的容错能力好，健壮性高。

我们再看看决策树算法的缺点:

1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。

2）决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。

4）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。

5）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

参考资料：
1、李航《统计学习方法》
2、https://www.cnblogs.com/pinard/p/6053344.html