DanielLaah

《统计学习方法》笔记 (七) - 决策树(下)


本篇博客为《统计学习方法》笔记系列第7篇, 是接着第6篇的内容, 对应《统计学习方法》中第五章第5节. 主要介绍CART.
说明: 目前来讲, 本系列博客内容基本完全摘抄自李航博士的《统计学习方法》, 所以阅读本系列博客极有可能造成您的不适, 如发生, 请尽快关闭浏览器. 写此系列博客目的一是学习的时候加深印象二是为了方便自己随时复习. 后面如果在其他书籍或课程中学习了相关的知识, 可能会对文章内容进行适量增删. 谢谢你!
PPT下载


五. CART算法

5.1 CART生成

CART算法的决策树生成和前面的生成树算法本质的区别就在于特征选择的标准. 前面提到过, ID3使用的是信息增益, C4.5使用的是信息增益率. 这里的CART有两种情况, 当生成回归树的时候, 使用平方误差最小化准则; 当生成分类树的时候使用的是基尼指数(Gini index)最小化准则. 并且, 这里生成的是二叉树.

5.1.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}^Mc_mI(x\in R_m)$$
当输入空间的划分确定时, 可以用平方误差$\sum_{x_i\in R_m}(y_i-f(x_i))^2$来表示回归树对于训练数据的预测误差, 用平方误差最小的准则求解每个单元上的最优输出值. 易知, 单元$R_m$上的$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$, 作为切分变量和切分点, 并定义两个区域:
$$R_1(j,s)=\{x|x^{(j)}\le s\} \quad \text{和}\quad R_2(j,s)=\{x|x^{(j)}\gt 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{c}_1=ave(y_i|x_i\in R_1(j,s))\quad \text{和}\quad \hat{c}_2=ave(y_i|x_i\in R_2(j,s))$$
遍历所有输入变量, 找到最优的切分变量$j$, 构成一个对$(j,s)$. 依此将输入空间划分为两个区域. 接着, 对每个区域重复上述划分过程, 直到满足停止条件为止. 这样就生成一棵回归树. 这样的回归树通常称为最小二乘回归树(least squares regression tree) , 现将算法叙述如下:
输入:训练数据集$D$;
输出:回归树$f(x)$.
在训练数据集所在的输入空间中, 递归地将每个区域划分为两个子区域并决定每个子区域上的输出值, 构建二叉决策树:
(1) 选择最优切分变量$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$, 对固定的切分变量$j$扫描切分点$s$, 选择使上式达到最小值的对(j,s) .
(2) 用选定的对(j,s) 划分区域并决定相应的输出值:
$$R_1(j,s)=\{x|x^{(j)}\le s\} \quad ,\quad R_2(j,s)=\{x|x^{(j)}\gt 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个区域R1,R2,…Rm, 生成决策树:
$$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$$

5.1.2 分类树的生成

分类问题中, 假设有$K$个类, 样本点属于第$k$类的概率为$p_k$, 则概率分布的基尼指数定义为:
$$\text{Gini}(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$$
对于二类分类问题, 若样本点属于第1个类的概率是$p$, 则概率分布的基尼指数为:
$$\text{Gini}(p)=2p(1-p)$$
对于给定的样本集合$D$, 其基尼指数为:
$$\text{Gini}(D)=1-\sum_{k=1}^K\left(\frac{|C_k|}{|D|}\right)^2$$
这里, $C_k$是$D$中属于第$k$类的样本子集, $K$是类的个数.
如果样本集合$D$根据特征$A$是否取某一可能值$a$被分割成$D1$和$D2$两部分, 即:
$$D_1=\{(x,y)\in D|A(x)=a\}, D_2=D-D_1$$
则在特征A的条件下, 集合D的基尼指数定义为:
$$\text{Gini}(D,A)=\frac{|D_1|}{|D|}\text{Gini}(D_1)+\frac{|D_2|}{|D|}\text{Gini}(D_2)\tag{5.25}$$
基尼指数$\text{Gini}(D)$表示集合$D$的不确定性, 基尼指数$\text{Gini}(D,A)$表示经$A=a$分割后集合$D$的不确定性. 基尼指数值越大, 样本集合的不确定性也就越大, 这一点与熵相似.
下图显示二类分类问题中基尼指数$\text{Gini}(p)$, 熵(单位比特) 之半$\frac{1}{2}H(p)$和分类误差率的关系. 横坐标表示概率$p$, 纵坐标表示损失. 可以看出基尼指数和熵之半的曲线很接近, 都可以近似地代表分类误差率.

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

5.2 CART剪枝

CART剪枝算法从”完全生长”的决策树的底端剪去一些子树, 使决策树变小(模型变简单) , 从而能够对未知数据有更准确的预测. CART剪枝算法由两步组成:首先从生成算法产生的决策树$T_0$底端开始不断剪枝, 直到$T_0$的根结点, 形成一个子树序列$\{T_0, T_1,…,T_n\}$, 然后通过交叉验证法在独立的验证数据集上对子树序列进行测试, 从中选择最优子树.
1.剪枝, 形成一个子树序列
在剪枝过程中, 计算子树的损失函数:
$$C_\alpha(T)=C(T)+\alpha|T|$$
其中, $T$为任意子树, $C(T)$为对训练数据的预测误差(如基尼指数) , $|T|$为子树的叶结点个数, $\alpha\le 0$为参数, $C_\alpha(T)$为参数是a时的子树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_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|T_t|$$
当$\alpha=0$及$\alpha$充分小时, 有不等式
$$C_\alpha(T_t)\le C_\alpha(t)$$
当$\alpha$增大时, 在某一$\alpha$有
$$C_\alpha(T_t)=C_\alpha(t)$$
当$\alpha$再增大时, 不等式反向. 只要$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$, $T_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,\alpha_2)$的最优子树.
如此剪枝下去, 直至得到根结点. 在这一过程中, 不断地增加$\alpha$的值, 产生新的区间.
2.在剪枝得到的子树序列$T_0,T_1,…,T_n$中通过交叉验证选取最优子树$T_a$
具体地, 利用独立的验证数据集, 测试子树序列$T_0,T_1,…,T_n$中各棵子树的平方误差或基尼指数. 平方误差或基尼指数最小的决策树被认为是最优的决策树. 在子树序列中, 每棵子树$T_0,T_1,…,T_n$都对应于一个参数$\alpha_0,\alpha_1,…,\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)$, $|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$的叶结点个数.
(4) 自上而下地访问内部结点$t$, 如果有$g(t)=\alpha$, 进行剪枝, 并对叶结点$t$以多数表决法决定其类, 得到树$T$.
(5) 设$k=k+1, \alpha_k=\alpha, T_k=T$.
(6) 如果$T$不是由根结点单独构成的树, 则回到步骤(4) .
(7) 采用交叉验证法在子树序列$T_0,T_1,…,T_n$中选取最优子树$T_\alpha$.