[科普中国]-分类与回归树

介绍

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

CART算法由以下两步组成：

1）树的生成：基于训练数据集生成决策树，生成的决策树要尽量大；

2）树的剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。

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

回归树的生成假设X与Y分别是输入和输出向量，并且Y是连续变量，给定训练数据集

考虑如何生成回归树。

一个回归树对应着输入空间（即特征空间）的一个划分以及在划分的但单元上的输出值。假设已将输入空间划分为M个单元 ，并且在每个单元 上有一个固定的输出值 ，于是回归树模型可表示为

当输入空间的划分确定时，可以用平方误差 来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元 上的 的最优值 是 上所有输入实例 对于的输出 的均值，即

问题是怎样对输入空间进行划分，这里采用启发式的方法，选择第 个变量 和它取的值 ，作为切分变量和切分点，并定义两个区域：

然后寻找最优切分变量 和最优切分点 。具体的，求解

对固定输入变量 可以找到最优切分点

遍历所有输入变量，找到最优切分变量 ，构成一个对 ，依次将输入空间划分为两个区域。接着，每个对每个区域重复上述划分过程，直到满足停止条件为止。这样就生成一棵回归树，这样的回归树通常被称为最小二乘树。1

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

基尼指数在分类过程中，假设有K个类，样本点属于第k个类的概率为 ，则概率分布的基尼指数定义为：

对于二类分类问题，若样本点属于第1个类的概率是p，则概率分布的基尼指数为：

对于给定的样本集合D ，其基尼指数为：

其中， 是D中属于第k类的样本子集，K是类的个数。

如果样本集合D根据特征A是否取某一可能值a 被分割成 和 两部分，即：

则在特征A的条件下，集合D的基尼指数定义为：

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

生成算法输入：训练数据集D,停止计算的条件

输出：CART决策树

根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

（1）设结点的训练数据集为D，计算现有特征对该数据集的基尼系数。此时，对每个特征A，对其可能取得每一个值a，根据样本点A=a的测试为“是"或”否“将D分成 和 两部分，计算A=a时的基尼指数

（2）在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点，依据最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去

（3）对两个子结点递归地调用 （1），（2），直至满足停止条件

（4）生成CART决策树

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

CART剪枝CART剪枝算法从”完全生长“的决策树的底端剪去一些子树，使决策树变小（模型变简单），从而能够对未知的数据有更准确的预测。CART剪枝算法由两步组成：首先从生成算法产生决策树 底端开始不断剪枝，直到 的根结点，形成一个子序列 ;然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。1

通过CART生成的树，记为T0，然后从T0的底端开始剪枝，直到根节点。在剪枝的过程中，计算损失函数：

， 为训练数据的预测误差， 为模型的复杂度。

对于一个固定的 ，在T0中一定存在一颗树 使得损失函数 最小。也就是每一个固定的 ，都存在一颗相应的使得损失函数最小的树。这样不同的 会产生不同的最优树，而我们不知道在这些最优树中，到底哪颗最好，于是我们需要将 在其取值空间内划分为一系列区域，在每个区域都取一个 然后得到相应的最优树，最终选择损失函数最小的最优树。

现在对 取一系列的值，分别为：

产生一系列的区间 。在每个区间内取一个值 ，对每个 ，我们可以得到一颗最优树 。于是我们得到一个最优树列表{T0,T1,…,Tn}。

那么对于一个固定的 ，如何找到最优的子树？

现在假如节点t就是一棵树，一颗单节点的树，则其损失函数为：

对于一个以节点t为根节点的树，其损失函数为：

当 =0时，即没有剪枝时， 。

然而，随着 的增大， 和 的大小关系会出现变化。

当Ca(t)= Ca(Tt)时，即：

据上分析，在 中的每个内部节点，计算 的值，它表示剪枝后整体损失函数减少的程度。在T0中剪去 最小的子树Tt，将得到的新的树记为 ，同时将此 记为 。即 为区间上的最优树。

与损失函数之间的关系分析：当 =0时，此时未进行任何剪枝，因为产生过拟合，所以损失函数会较大，而随着的增大，产生的过拟合会慢慢消退，因而，损失函数会慢慢减小，当增大到某一值时，损失函数会出现一个临界值，因而超过此临界值继续增大的话损失函数就会因而模型越来越简单而开始增大。所以我们需要找到一个使损失函数最小的临界点。

如何找到使损失函数最小的呢？

依次遍历生成树的每一个内部节点，分别计算剪掉该内部节点和不剪掉该内部节点时的整体损失函数，当这两种情况的损失函数相等时，我们可以得到一个，此表示当前需要剪枝的最小。这样每个内部节点都能计算出一个。此示整体损失函数减少的程度。

那么选择哪个来对生成树进行剪枝呢？

我们选择上面计算出的最小的来进行剪枝。假如我们选择的不是最小的进行剪枝的话，则至少存在两处可以剪枝的内部节点，这样剪枝后的损失函数必然会比只剪枝一处的损失要大（这句话表述的可能不准确），为了使得损失函数最小，因而选最小的来进行剪枝。

在选出之后，我们就需要计算该对应的使损失函数最小的子树。即从树的根节点出发，逐层遍历每个内部节点，计算每个内部节点处是否需要剪枝。剪枝完之后的树便是我们所需要的树。