CART 算法

分类与回归树(classification and regression tree, CART)模型由Breiman等人在1984年提出,是应用广泛的决策树学习算法。CART同样由特征选择、树的生成及剪枝组成,既可以用于分类也可以用于回归。以下将用于分类与回归的树统称为决策树。

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

CART算法由以下两部分组成: 1) 决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大。 2) 决策树剪枝:用验证数据集对已生成的树进行剪枝并选择则最优子树,这时用损失函数最小作为剪枝标准。

CART树生成

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

回归树生成

假设\(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) \tag{1}\]

当输入空间划分确定时,可以用平法误差\(\sum_{x \in R_m} (y_i - f(x_i))^2\) 来表示回归回归树于训练数据的预测误差,用平方误差最小的准则求解每个单元上的最优输出值,易知,单元\(R_m\)上的\(c_m\)的最优值\[\hat{c}_m = ave (y_i | x_i \in R_m)\]

问题是怎样对输入空间进行划分。这里主要采用启发式的方法,选择第\(j\)个变量\(x^{(j)}\)和它的取值\(s\),作为切分变量和切分点(spliting point),并定义两个区域:\[R_1(j,s) = \{x|x^{(j)}<=s\} 和 R_2(j,s) = \{x|x^{(j)}>s\} \tag{2}\] 然后寻找最优切分变量\(j\)和最优切分点\(s\),具体地,求解 \[\min_{j,s}[\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{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)) \quad 和 \quad \hat{c}_2 = ave (y_i | x_i \in R_1(j,s))\]遍历所有输入变量,找到最优的切分变量\(j\),构成一个对(j,s),依此将输入空间划分为两个区域。接着,对每个区域重复上述划分过程,知道满足停止条件为止。这样就生成一棵回归树,这样的回归树通常称为最小二乘回归树(least squares regression tree),现将算法叙述如下:

算法1 (最小二乘回归树生成算法)

  • 输入: 训练集\(D\)
  • 输出: 回归树\(f(x)\)
  • 在训练数据集所在的输入空间中, 递归地将每个区域划分为两个子区域并决定每个子区域上的输出值,构成二叉决策树:
    1. 选择最优切分变量\(j\)与切分点\(s\)求解\[\min_{j,s}[\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 ] \tag{3}\]遍历变量\(j\),对固定的切分变量\(j\)扫描切分点\(s\),选择使式3达到最小值的对\((j,s)\).
    1. 用选定的\((j,s)\)划分区域并决定相应的输出值:\[R_1(j,s) = \{x|x^{(j)}<=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 \quad, \quad x \in R_m \quad, \quad m=1,2\]
    1. 继续对两个子区域调用步骤1),2)直至满足停止条件。
    1. 将输入空间划分为\(M\)个区域\(R_1, R_2, ..., R_M\), 生成决策树:\[f(x)=\sum_{m=1}^M \hat {c}_m I(x \in R_m)\]
分类树生成

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

定义 1(基尼指数): 分类问题中,假设有\(K\)个类,样本点属于第k类的概率为\(p_k\), 则概率分布的基尼指数定义为\[Gini(p) = \sum_{k=1} ^K p_k (1-p_k) = 1 - \sum_{k=1} ^K p_k^2\]对于二类分类问题,若样本属于第1个类的概率是\(p\),则概率分布的基尼指数为\[Gini(p) = 2 p (1-p)\]

对于给定的样本集合\(D\),其基尼指数为\[Gini(D) = 1 - \sum_{k=1}^K(\frac {|C_k|} {|D|})^2 \tag {4}\]这里\(C_k\)\(D\)中第\(k\)类样本子集,\(K\)是类的个数。

如果样本集合\(D\)根据特征\(A\)是否取某一个可能值\(a\)被分割成\(D_1\)\(D_2\)两部分,即\[D_1=\{(x,y) \in D | A(x) = a\}, \quad D_2 = D - D_1\]则在特征\(A\)的条件下,集合\(D\)的基尼指数定义为\[Gini(D,A)=\frac {|D_1|} {|D|} Gini(D_1) + \frac {|D_2|} {|D|} Gini (D_2) \tag{5}\] 基尼指数\(Gini(D)\)表示集合\(D\)的不确定性,基尼指数\(Gini(D,A)\)表示经\(A=a\)分割后集合\(D\)的不确定性,基尼指数越大,样本集合的不确定性也就越大,这一点与熵相似。

算法2 (CART生成算法)

  • 输入: 训练数据集\(D\),停止计算的条件;
  • 输出: CART决策树
  • 根据训练数据集,从根节点开始,递归地对每个结点进行一下操作,构建二叉决策树:
  • 1 设树的训练数据集为\(D\),计算现有特征对该数据集的基尼指数。此时对每个特征\(A\),对其可能的每个取值\(a\)根据样本点对\(A=a\)测试为“是”或“否”将\(D\)切割为\(D_1\)\(D_2\)两个部分,利用式5计算\(A=a\)时的基尼指数。
  • 2 在所有可能的特征\(A\)以及它们所有可能的切分点\(a\)中, 选择则基尼指数最小的特征及其切分点作为最优特征与最优切分点。依最优特征与最优切分点,从现结点生成两个子结点。将训练数据集依特征分配到两个子结点当中去。
  • 3 对两个子结点递归调用1,2,直到满足停止条件
  • 4 生成CART 树

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

CART 剪枝

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

剪枝, 形成一个子树序列

在剪枝过程中,计算子树的损失函数 \[C_{\alpha} (T) = C(T) + \alpha |T|\] 其中, \(T\)为任意子树, \(C(T)\)为对训练数据的预测误差(如基尼指数), \(|T|\)为子树的叶结点个数, \(\alpha >= 0 为参数\)\(C_{\alpha}(T)\)为参数是\(\alpha\)时的子树\(T\)的整体损失,参数\(\alpha\)权衡训练数据的拟合程度与模型的复杂度。 对固定的\(\alpha\),一定存在是损失函数\(C_{\alpha} (T)\)最小的子树, 将其表示为\(T_{\alpha}\), \(T_{\alpha}\)在损失函数\(C_{\alpha} (T)\)最小的意义下是最优的。容易验证这样的最优子树是唯一的。当\(\alpha\)大的时候,最优子树\(T_{\alpha}\)偏小;当\(\alpha\)小的时候,最优子树\(T_{\alpha}\)偏大;极端情况,当\(\alpha = 0\)时,整体树是最优的。当\(\alpha \rightarrow \infty\)时,根节点组成的单结点树是最优的。

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

具体地, 从整棵树\(T_0\)开始剪枝,对\(T_0\)的任意内部结点\(t\),以\(t\)为单结点树的损失函数是\[C_{\alpha}(T) + \alpha\]\(t\)为根结点的子树\(T_t\)的损失函数是\[C_{\alpha}(T_t)=C(T_t)+\alpha|T_t|\]

\(\alpha=0\)时及\(\alpha\)充分小的时候,有不等式\[C_{\alpha}(T_t) < C_{\alpha}(t) \tag{6}\]\(\alpha\)增大时,在某一\(\alpha\)\[C_{\alpha}(T_t) = C_{\alpha}(t)\]\(\alpha\)再增大时,不等式6反向,只要 \(\alpha = \frac {C(t) - C(T_t)} {|T_t| - 1}\)\(T_t\)\(t\)有相同的损失函数值,而\(t\)的结点少比\(T_t\)更可取, 对\(T_t\)进行剪枝。

为此,对\(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, \alpha2)\)的最优子树。

如此剪枝下去, 知道得到根结点,在这个过程中不断的增大\(\alpha\)的值,产生新的区间。

在剪枝得到的子树序列\(T_0, T_1, T_2, ..., T_n\) 中通过交叉验证选取最优子树 \(T\)

具体地,利用独立的验证数据集, 测试子树序列\(T_0, T_1, T_2, ..., T_n\)中各棵子树的平均误差或基尼指数, 平方误差或基尼指数最小的决策树被认为是最优的决策树。 在子树序列中, 每颗子树\(T_0, T_1, T_2, ..., T_n\)都对应于一个参数\(\alpha_0, \alpha_1, \alpha_2, ..., \alpha_n\)。所以当最优子树\(T_k\)确定时,对应的\(\alpha_k\)也确定了,即得到最优决策树\(T_{\alpha}\)

算法3 (CART剪枝算法)

  • 输入: CART算法生成的决策树\(T_0\)
  • 输出: 最优决策树\(T_{\alpha}\)
  • 1 设\(k=0, \quad T=T_0\)
  • 2 设\(\alpha = +\infty\)
  • 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_t\)的叶结点个数。
  • 4 对\(g(t) = \alpha\)的内部结点\(t\)进行剪枝,并对叶结点\(t\)以多数表决法决定其类,得到数\(T\)
  • 5 设\(k=k+1, \quad \alpha = \alpha, T_k = T\)
  • 6 如果\(T_k\)不是由根结点及两个叶结点构成的树,则回到步骤3, 否则令\(T_k=T_n\)
  • 7 采用较差验证法在子树序列\(T_0, T_1, T_2, ..., T_n\)中选取最优子树\(T_{\alpha}\)