统计学习方法笔记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$ 进行剪枝。

为此，对 $T_0$ 中每一内部结点 $t$ ，计算

$g(t) =\dfrac{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$ 的值，产生新的区间。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,470评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,393评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,577评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,176评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,189评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,155评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,041评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,903评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,319评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,539评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,703评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,417评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,013评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,664评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,818评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,711评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,601评论 2赞 353

统计学习方法笔记05

5.4 决策树的剪枝(pruning)

5.5 CART算法

推荐阅读更多精彩内容