统计学习方法笔记05

李航. 统计学习方法[M]. 清华大学出版社, 2012.

5.4 决策树的剪枝(pruning)

剪枝是从已生成的树上裁掉一些子树或叶节点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。

设树 $T$ 的叶结点个数为 $|T|$ ， $t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个， $H_t(T)$ 为叶结点 $t$ 上的经验熵， $\alpha\geq 0$ 为参数，则决策树学习的损失函数可以定义为：

$\begin{aligned}C_{\alpha}(T) &= \sum_{t=1}^{|T|} N_tH_t(T) + \alpha|T| \\&= \sum_{t=1}^{|T|} \left[ N_t \left( -\sum_k \dfrac{N_{tk}}{N_t} \log{\dfrac{N_{tk}}{N_t}} \right) \right] + \alpha|T| \\&= -\sum_{t=1}^{|T|}\sum_k N_{tk} \log{\dfrac{N_{tk}}{N_t}} + \alpha|T| \\&= C(T)+\alpha |T|\end{aligned}$

其中 $C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度； $|T|$ 表示模型复杂度。剪枝，就是当 $\alpha$ 确定时，选择损失函数最小的模型，即损失函数最小的子树。

决策树剪枝算法

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

输出：修剪后的子树 $T_{\alpha}$

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

(2) 递归地从树的叶结点向上回缩。如果回缩到父结点后损失函数变小，则进行剪枝，父结点变为新的叶结点；

(3) 返回(2)直到不能继续为止。

5.5 CART算法

分类与回归树(classification and regression tree, CART)同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”。

5.5.1 CART生成
- 5.5.1.1 回归树的生成（最小二乘回归树）

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

$f(x) = \sum_{m=1}^M c_m \mathbb{I}(x\in R_m)$

当输入空间划分确定时，可以用平方误差 $\sum_{x_i\in R_m}(y_i-f(x_i))^2$ 来表示回归树对于训练数据的预测误差，用平方误差最小化的准则求解每个单元上的最优输出值。易知， $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$ ，作为切分变量(splitting variable)和切分点(splitting point)，并定义两个区域

$R_1(j,s) = \{x|x^{(j)}\leq s\}$ 和 $R_2(j,s) = \{x|x^{(j)} > s\}$

然后寻找最优切分变量 $j$ 和最优切分点 $s$ 。具体地，求解

$\min_{j,s} \left[ \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\right]$

对固定输入变量 $j$ 可以找到最优切分点 $s$ 。遍历所有输入变量，找到最优的切分变量 $\hat{j}$ 及其最优切分点 $\hat{s}$ ，构成一个对 $(\hat{j},\hat{s})$ 。依此将输入空间划分为两个区域。接着对每个区域重复上述划分过程，直到满足停止条件为止。

* **5.5.1.2 分类树的生成**

定义（基尼指数）

分类问题中，假设由 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$ ，则概率分布的基尼指数定义为：

$Gini(p) = \sum_{k=1}^K p_k(1-p_k) = 1 - \sum_{k=1}^K p_k^2$

对于给定的样本集合D，其基尼指数为 $Gini(D) = 1 - \sum_{k=1}^K \left(\dfrac{|C_k|}{|D|}\right)^2$ 。

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

$D_1 = \{(x,y)\in D|A(x)=a\}$ 和 $D_2 = D - D_1$

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

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

基尼指数 $Gini(D)$ 表示集合D的不确定性，基尼指数 $Gini(D,A)$ 表示经 $A=a$ 分割后集合D的不确定性。基尼指数越大，样本集合的不确定性越大。

CART分类树生成算法

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

5.5.2 CART剪枝

CART剪枝分为两步：①首先从生成算法产生的决策树 $T_0$ 底端开始不断剪枝，直到 $T_0$ 的根结点，形成一个子树序列 $\{T_0,T_1,\dots,T_n\}$ ；②然后通过交叉验证法在独立的验证集上对子树序列进行测试，从中选出最优子树。

CART剪枝算法

输入：CART算法生成的决策树 $T_0$

输出：最优决策树 $T_{\alpha}$

(1) 设 $k=0$ ， $T=T_0$ ， $\alpha=+\infty$ 。

(2) 自下而上地对各内部结点 $t$ 计算 $C(T_t)$ 、 $|T_t|$ 以及

$g(t) = \dfrac{C(t)-C(T_t)}{|T_t|-1}$

$\alpha = \min (\alpha, g(t))$

其中， $T_t$ 表示以 $t$ 为根结点的子树， $C(T_t)$ 是对训练数据的预测误差， $|T_t|$ 是 $T_t$ 的叶结点个数。

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

(4) 设 $k=k+1$ ， $\alpha_k=\alpha$ ， $T_k=T$ 。

(5) 如果T_k不是由根结点及两个叶结点构成的树，则回到步骤(2)；否则令 $T_k=T_n$ 。

(6) 采用交叉验证法在子树序列 $T_0,T_1,\dots,T_n$ 中选择最优子树 $T_{\alpha}$ 。

Breiman等人证明：

可以用递归的方法对树进行剪枝。将 $\alpha$ 从小增大， $0=\alpha_0 < \alpha_1 <\dots<\alpha_n<+\infty$ ，产生一系列的区间 $[\alpha_i,\alpha_{i+1}), i=0,1,\dots,n$ ；剪枝得到的子树对应着区间 $\alpha\in [\alpha_i,\alpha_{i+1})$ 的最优子树序列 $\{T_0,T_1,\dots,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 |T_t|$

当 $\alpha=0$ 或充分小时，有不等式 $C_{\alpha}(T_t) < C_{\alpha}(t)$ 。当 $\alpha$ 再增大时，不等式反向。只要 $\alpha = \dfrac{C(t)-C(T_t)}{|T_t|-1}$ ， $T_t$ 与 $t$ 有相同的损失函数值，而 $t$ 的结点少因此 $t$ 比 $T_t$ 更可取，对 $T_t$ 进行剪枝。