分类与回归树(Classification And Regression Tree,CART)采用二叉树,小于等于决策节点特征值的分到左分支,其他分到右分支。此过程迭代地二分每个特征,将输入空间划分成有限个单元,并在这些单元上确定预测的概率分布。采用二叉树的主要原因是担心组合爆炸,如果是多叉树会有非常多的特征组合,导致训练特别慢。

  CART 算法一般分两个步骤:

  1. 决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大。
    1. 分类树生成
    2. 回归树生成
  2. 决策树剪枝:用验证数据集对已生成的决策树进行剪枝并选择最优子树,这时用损失函数最小作为剪枝的标准。

1. CART 生成

  CART 的生成就是迭代地构建二叉树的过程,如果待预测结果是离散型数据,CART 生成分类决策树,如果待遇测数据是连续型数据,CART 生成回归决策树。对分类树用基尼系数最小化准则,对回归树用平方误差最小化准则,进行特征选择,生成二叉树。

1.1 分类树的生成

  与 ID3 和 C4.5 不同的是,CART 划分的结果是二叉树。在生成分类树时对每一个属性 $a$ 的每一种取值 $a^v$ 判断“当前属性值是否小于等于 $a^v$”,如此将样本集 $D$ 分成 $D_1$ 和 $D_2$ 两个部分。遍历属性 $a$ 的所有取值 $a^v$,找到能够使得基尼系数最小化的属性值。

  对于样本集 $D$,计算所有属性 $a \in A$ 的最优二分方案,选择其中基尼系数最小的,作为样本集 $D$ 在此处划分的属性和阈值:

  然后对划分的两个子结点迭代地进行上述两个遍历计算,直到满足停止条件。

  分类结果可以用概率表示,就计算对应分类叶子节点中该类别样本数占该叶子节点样本数目的比例即可。

  为了方便对比,写下分类树的损失函数:

  $k$ 表示特征,$t_k$ 表示特征的一个阈值(大于、等于或小于 $t_k$),$m$ 为样本个数,$G$ 是啥?。

1.2 回归树的生成

  回归树的预测结果(区分属性值为连续型时的操作)是连续型数据,有两个问题需要搞清楚:

  1. 划分点怎么找?(即不纯度如何计算?)
  2. 因为划分后为二叉树,原本可能有很多取值的结果要怎么输出?

  介绍前首先假设 $X$ 和 $Y$ 分别为输入和输出变量,$Y$ 为连续变量,给定数据集:

  其中 $x _ { i } = \left( x _ { i } ^ { ( 1 ) } , x _ { i } ^ { ( 2 ) } , \ldots , x _ { i } ^ { ( n ) } \right)$ 为输入实例(特征向量),$i=1,2,\dots,N$,$n$ 为特征个数,$N$ 为样本总量。

  如果选择特征向量的第 $j$ 个特征变量 $x^{(j)}$ 和其某一个属性值 $s$ 作为切分变量 (Splitting variable) 和切分点 (Splitting point),由其划分的两个区域为:

  如何去衡量这样的划分好不好?类似分类树在划分子树时采用基尼系数作为衡量标准,回归树采用平方误差作为不纯度衡量来划分子树。我们划分的目标是让划分之后的每个子区域的样本输出值跟真实值之间的差距最小,为此我们分两步进行,首先对一个特定属性 $j$,先找到能够使当前划分指标最优的 $s$,然后再遍历所有的属性 $j$,如此找到最优的划分组合 $j$ 和 $s$。

  先考虑特定属性 $j$ 找到合适的划分属性值 $s$:

  其中 $c_1$ 和 $c_2$ 分别是需要计算的左右子树输出值。由于 $s$ 的不同取值会同时影响到 $c_1$ 和 $c_2$,函数 $L$ 不是连续的,没有办法通过一般的优化方式求解。当然也不需要用优化算法,因为这里是通过遍历的方式找到最优的选择,不需要找到优化方向。

  以属性值 $s$ 来划分子树后,左右两个子树的样本就确定了,那么对于找到最小的 $L$,其实就是分别求两个平方误差的最小值,进而得到对应的 $c_1$,$c_2$。

  当输入空间的划分确定时,利用平方误差最小化原则来求解每个单元上的最优输出值。通过求二阶导能知道单调性,可证明单元 $R_m$ 上的 $c_m$ 的最优值是 $R_m$ 上所有输入实例 $x_i$ 对应的输出的 $y_i$ 的均值:

具体证明可以展开查看!

  给定一个随机的数列 $\{ x _ { 1 } , x _ { 2 } , \dots , x _ { n } \}$,假设该空间中最优的输出值为 $a$,则根据最小平方误差准则,我们能得到有关 $a$ 的函数如下:

  我们考察其单调性:

  二阶导为正数,所以该函数为严格凸函数,那么令 $F ^ { \prime } ( a ) = 0$,得到 $a = \frac { 1 } { n } \sum _ { i = 1 } ^ { n } x _ { i }$,即最小值点为:


  那么两个子区域的最优输出值分别为:

  这里是针对特定属性 $j$ 找划分特征值 $s$ 的计算,接着遍历所有的属性 $j$,找每个属性对应的最优划分属性值 $s$,从所有组合中找到最优的划分组合。

  根据子区域的最优输出值计算,对应求解最优划分变量的方式可以变为:

  如此我们得到了当前划分的一个最优划分对 $(j,s)$,据此将输入空间划分为两个区域,接着循环执行这个划分流程,直到满足停止条件,将输入空间划分成了 $M$ 个区域,生成回归树。

  回归的损失函数采用的是 MSE 作为衡量标准,不像分类树用 GINI 不纯度:

2. CART 剪枝——代价复杂性剪枝法

  CART 剪枝算法是想从“完全生长”的决策树的底端减去一些子树,使决策树变小 (模型变简单)。这里介绍 CART 应用最广泛的代价复杂性剪枝法 (Cost Complexity Pruning, CCP)。

  CCP 主要包含两个步骤:

  1. 从原始决策树 $T_0$ 开始自底向上生成一个子树序列 ${T_0, T_1, \dots, T_n }$,其中,$T_{i+1}$ 从 $T_{i}$ 产生,$T_n$ 为根节点。
  2. 从第 $1$ 步产生的子树序列中,根据树的真实误差估计选择最佳决策树。

2.1 生成子树序列

  完整的树我们以 $T_0$ 表示,以此为基础,从决策树底端开始,考察一个内部结点,减去一个子树形成 $T_1$;接着在 $T_1$ 的基础上继续减去一个子树形成 $T_2$,循环往复直到剪枝只剩下根节点 $T_n$。接着利用独立的验证数据集对 ${T_0, T_1, \dots, T_n }$ 这 $n+1$ 个子树进行测试,从中选择最优的子树。

  那么接下来的问题是,如何选择一个子树(内部结点)进行剪枝?

  CART 剪枝时定义了计算子树的损失函数:

  其中 $T$ 表示任意的子树,$C ( T )$ 为对训练数据的预测误差 (比如基尼系数等指标),$\mid\mathcal {T} \mid $ 表示子树的叶节点个数。$\alpha$ 衡量和调节训练数据的拟合程度与模型复杂度的参数,$C _ { \alpha } ( T )$ 表示参数为 $\alpha$ 的子树 $T$ 的整体损失。

  接下来从整体树 $T_0$ 开始剪枝,对于 $T_0$ 的任意内部结点 $t$,现在要衡量 $T_t$ 子树有没有存在的必要,以 $t$ 为单节点树的损失函数 (即剪枝后子树变成一个叶节点,其对应的损失函数) 是:

  以 $t$ 为根节点的待剪枝的子树的损失函数为:

  当 $\alpha=0$ 及 $\alpha$ 充分小时,有如下不等式成立,此时还不需要剪枝:

  当 $\alpha$ 慢慢增大时,损失函数对模型复杂度 (即公式中的 $\alpha \vert T _ { t }\vert $) 的惩罚也越来越大,在某一个 $\alpha$ 上会使得剪枝前后的损失函数相等

  那么,从这个时候开始,就有必要进行剪枝了 (类别有多数表决产生),此时我们得到一个被称作误差增益的式子:

  观察其分子,可以看做是在节点 $t$ 处剪枝后增加的误差,而剪枝后子树 $T_t$ 叶节点的数目减少了 $\vert T _ { t }\vert - 1$ 个,故 $\alpha$ 的这个计算式被称为误差增益

  有了误差增益这个衡量标准,我们自底向上对 $T_0$ 中每一个内部结点,计算剪枝的阈值 $g(t)$:

  找到 $T_0$ 中能使得 $g(t)$ 最小的一个内部结点 $t$ 进行剪枝得到 $T_1$,在 $T_1$ 中重复这个找内部结点并剪枝的过程,一直到只剩下根节点,从而得到了子树序列 $\{T_0, T_1, \dots, T_n \}$。

2.2 寻找最优子树  

  得到子树序列 $\{T_0, T_1, \dots, T_n \}$ 后,接下来就是要找到其中最优的子树作为预测的模型,一般有两种策略:

  1. 采用 K-fold Cross Validation 来选择具有最优拟合效果的子树;
  2. 基于独立的剪枝数据集进行选择。

3. CART 预测

  训练好的 CART 结果对应着输入空间(即特征空间)的一个划分以及在划分的单元上的输出值。假设已知将输入空间分成了 $M$ 个单元 $R_1, R_2, \dots, R_M$,并且每个单元 $R_m$ 上有一个固定的输出值 $c_m$,则 CART 决策函数可以表示为:

  其中 $I$ 为指示函数:

  每个子区域的 $c_m$ 值:

  1. 分类树:看子区域的样本中大多数的类别是什么就取其值
  2. 回归树:子区域所有样本输出值的平均值

4. 不稳定性

  虽然决策树有容易理解和解释、易用、拟合能力强大的特点,但是其对数据扰动非常敏感,分两个部分,一是对数据旋转敏感,而是对数据增减变化也较敏感。

  如下图,左图用一层的决策树就可以很好的划分数据集,右图表示将左图数据旋转 50° 后,需要更多层的决策树来拟合。可以看出左右图拟合效果都还不错,在复杂度上有较大区别。我们可以用 PCA 对数据进行降维,可以在一定程度上减轻这样的数据旋转问题。可能因为 PCA 选择的特征都是互相正交的,没有旋转的现象。

  第二个是对数据增减变化较敏感。例如在 iris 数据集中,我们把最宽、的 Iris-Versicolor 删去,可以看到变化前后的决策树完全变样了。这个问题可以用随机森林来避免!

4. CART 总结

  决策树很容易发生过拟合,可以改善的方法有:

  1. 通过阈值控制终止条件,避免树形结构分支过细。
  2. 通过对已经形成的决策树进行剪枝来避免过拟合。
  3. 基于Bootstrap的思想建立随机森林。

CART 优点

  1. 支持回归和分类任务
  2. 支持连续值处理,缺失值处理和剪枝操作;
  3. 非常灵活,可以允许有部分错分成本,还可指定先验概率分布,可使用自动的成本复杂性剪枝来得到归纳性更强的树。

CART 缺点

  1. 如果样本发生一点点的改动,就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。
  2. 在构造树的过程中,需要对数据集进行多次顺序扫描和排序,致使算法相对较低效。

  训练的时间复杂度为 $O(n\times m\log_2(m))$,预测时间复杂度是 $O(\log_2(m))$,其中 $m$ 是样本个数,$n$ 为特征个数。

4.1 思考

1. 如果一个样本有一百万个样本,那么我们大概用多深的数来进行拟合?

  一颗 well-balanced 的树,如果完全不设限制任其生长,最后所有的样本都会归属到一个只有一个样本的叶节点上,过拟合的十分厉害。那么可以算下如果样本个数为 $m$,该数的深度为 $\log_2(m)$。所以一百万样本的树深度最多为 $\log_2(10^6)\approx 20$,实际数肯定比这个小,因为实际有限制,不会这么 well balanced。

References

  1. 决策树之CART(分类回归树)详解
  2. cart树怎么进行剪枝? - zzhang27的回答 - 知乎
  3. 機器學習經典算法優缺點總結
  4. Why are implementations of decision tree algorithms usually binary and what are the advantages of the different impurity metrics?