原理

决策树的剪枝

在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）。

决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。设树T的叶结点个数为\(\mid T \mid\)，t是树T的叶结点，该叶结点有\(N_t\)个样本点，其中k类的样本点有\(N_{tk}\)个，k=1,2,…,K，\(H_t(T)\)为叶结点t上的经验熵，\(\alpha \geq 0\)为参数，则决策树学习的损失函数可以定义为

\[C_\alpha(T)=\sum_{t=1}^{\mid T \mid} N_t H_t(T)+\alpha \mid T \mid\]

其中经验熵为

\[H_t(T)=-\sum_k \frac{N_{tk}}{N_t} log \frac{N_{tk}}{N_t}\]

在损失函数中，将

\[C(T) = \sum_{t=1}^{\mid T \mid} N_t H_t(T) = -\sum_{t=1}^{\mid T \mid} \sum_{k=1}^K N_{tk} log \frac{N_{tk}}{N_t}\]

这时有

\[C_\alpha(T)=C(T)+ \alpha \mid T \mid\]

其中，C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，\(\mid T \mid\)表示模型复杂度，参数\(\alpha \geq 0\)控制两者之间的影响。较大的\(\alpha\)促使选择较简单的模型（树），较小的\(\alpha\)促使选择较复杂的模型（树）。\(\alpha=0\)意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

剪枝，就是当\(\alpha\)确定时，选择损失函数最小的模型，即损失函数最小的子树。当\(\alpha\)确定时，子树越大，往往与训练数据的拟合越好，但是模型的复杂度就越高；相反，子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好。损失函数正好表示了对两者的平衡。

可以看出，决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

损失函数的极小化等价于正则化的极大似然估计。所以，利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。

树的剪枝算法：

输入：生成算法产生的整个树T，参数\(\alpha\);

输出：修剪后的子树\(T_\alpha\).

(1) 计算每个结点的经验熵.

(2) 递归地从树的叶结点向上回缩.

设一组叶结点回缩到父结点之前与之后的整体树分别为\(T_B\)与\(T_A\)，其对应的损失函数值分别是\(C_\alpha(T_B)\)与\(C_\alpha(T_A)\)，如果

\[C_\alpha(T_A) \leq C_\alpha(T_B)\]

则进行剪枝，即将父节点变为新的叶结点。

(3) 返回(2)，直到不能继续为止，得到损失函数最小的子树\(T_\alpha\).

注意，(2)中只需考虑两个树的损失函数的差，其计算可以在局部进行。所以，决策树的剪枝算法可以由一种动态规划的算法实现。

CART算法

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

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。

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

CART算法由以下两步组成：

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

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

CART生成

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

  1. 回归树的生成

假设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}^M c_m I(x \in R_m)\]

当输入空间的划分确定时，可以用平方误差\(\sum_{x_i \in R_m}(y_i-f(x_1))^2\)来表示回归树对训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元\(R_m\)上的\(c_m\)的最优值\(\hat{c}_m\)是\(R_m\)上的所有输入实例\(x_i\)对应的输出\(y_i\)的均值，即

\[\hat{c}_m = ave(y_i \mid x_i \in R_m)\]

问题是怎样对输入空间进行划分。这里采用启发式的方法，选择第j个变量\(x^{(j)}\)和它取的值s，作为切分变量（splitting variable）和切分点（splitting point），并定义两个区域：

\[R_1(j,s)={x \mid x^{(j)} \leq s}, R_2(j,s)={x \mid x^{(j)} > s}\]

然后寻找最优切分变量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 \mid x_i \in R_1(j,s)), \hat{c}_2 = ave(y_i \mid x_i \in R_2(j,s))\]

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

最小二乘回归树生成算法：

输入：训练数据集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]\]

遍历遍历j，对固定的切分变量j扫描切分点s，选择使上式达到最小值的对(j,s).

(2) 用选定的对(j,s)划分区域并决定相应的输出值：

\[R_1(j,s)={x \mid x^{(j)} \leq s}, R_2(j,s)={x \mid 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}^M 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) = 2p(1-p)\]

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

\[Gini(D) = 1- \sum_{k=1}^K (\frac{\mid C_K \mid}{\mid D \mid})^2\]

这里，\(C_k\)是D中属于第k类的样本子集，K是类的个数。

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

\[D_1={(x,y) \in D \mid A(x) = a}, D_2 = D - D_1\]

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

\[Gini(D,A) = \frac{\mid D_1 \mid}{\mid D \mid} Gini(D_1) + \frac{\mid D_2 \mid}{\mid D \mid}Gini(D_2)\]

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

CART生成算法：

输入：训练数据集D，停止计算的条件；

输出：CART决策树.

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

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

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

(3) 对两个子结点递归调用(1),(2)，直到满足停止条件。

(4) 生成CART决策树。

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

CART剪枝

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

  1. 剪枝，形成一个子树序列

在剪枝过程中，计算子树的损失函数：

\[C_\alpha(T)=C(T)+\alpha \mid T \mid\]

其中，T为任意子树，C(T)为对训练数据的预测误差（如基尼指数），\(\mid T \mid\)为子树的叶结点个数，\(\alpha \geq 0\)为参数，\(C_\alpha(T)\)为参数是\(\alpha\)时的子树T的整体损失。参数\(\alpha\)权衡训练数据的拟合过程与模型的复杂度。

Breiman等人证明：可以用递归的方法对树进行剪枝。将\(\alpha\)从小增大，\(0=\alpha_0 < \alpha_1 < ... < \alpha_n < +\infty\)，产生一系列的区间\([\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}\)，序列中的子树是嵌套的。

具体地，从整体树\(T_0\)开始剪枝，对\(T_0\)的任意内部结点t，以t为单结点树的损失函数是

\[C_\alpha(t)=C(t) + \alpha\]

以t为根结点的子树\(T_t\)的损失函数是

\[C_\alpha(T_t)=C(T_t)+\alpha \mid T_t \mid\]

当\(\alpha=0\)及\(\alpha\)充分小时，有不等式

\[C_\alpha(T_t) < C_\alpha(t)\]

当\(\alpha\)增大时，在某一\(\alpha\)有

\[C_\alpha(T_t) = C_\alpha(t)\]

当\(\alpha\)再增大时，上述不等式反向。只要\(\alpha = \frac{C(t)-C(T_t)}{\mid T_t \mid -1}\)，\(T_t\)与t有相同的损失函数值，而t的结点少，因此t比\(T_t\)更可取，对\(T_t\)进行剪枝。

为此，对\(T_0\)中每一内部结点t，计算

\[g(t) = \frac{C(t)-C(T_t)}{\mid T_t \mid -1}\]

它表示剪枝后整体损失函数的减少程度。在\(T_0\)中剪去g(t)最小的\(T_t\)，将得到的子树作为\(T_1\)，同时将最小的g(t)设为\(\alpha_1\)。\(T_1\)为区间\([\alpha_1, \alpha_2)\)的最优子树。

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

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

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

CART剪枝算法

输入：CART算法生成的决策树\(T_0\);

输出：最优决策树\(T_\alpha\).

(1) 设\(k=0, T=T_0\).

(2) 设\(\alpha=+\infty\).

(3) 自下而上地对内部各结点t计算\(C(T_t)\)，\(\mid T_t \mid\)以及

\[g(t) = \frac{C(t)-C(T_t)}{\mid T_t \mid -1}\] \[\alpha = min(\alpha, g(t))\]

这里，\(T_t\)表示以t为根结点的子树，\(C(T_t)\)是对训练数据的预测误差，\(\mid T_t \mid\)是\(T_t\)的叶结点个数。

(4) 对\(g(t)=\alpha\)的内部结点t进行剪枝，并对叶结点t以多数表决法决定其类，得到树T.

(5) 设\(k=k+1, \alpha_k = \alpha, T_k = T\).

(6) 如果\(T_k\)不是由根结点及两个叶结点构成的树，则回到步骤(3)；否则令\(T_k=T_n\).

(7) 采用交叉验证法在子树序列\(T_0, T_1, ..., T_n\)中选取最优子树\(T_\alpha\).

实现

参考文献

  • 统计学习 李航 第5章 决策树