第10章－基于树的方法(2)-树的剪枝

10.8 通过剪枝得到最优规模的树

之前我们讨论的都是如何生成树，接下来我们要讲解的是如何进行剪枝。

我们令一个树 T 的误分类误差的期望为 R?(T) .
回想一下，我们是用再代入误差估计，估计的 R?(T) ，即

R(T)=∑t∈T′R(t)=∑t∈T′p(t)r(t)

再来想一下，10.3中所讲的，r(t)是叶节点t的误分类概率，等于
1-‘基于训练集得到的叶节点t的频率最大的类别点对应的概率’,即

r(t)=1?maxp(j|t)=1?p(k(t)|t)

对于整个树，对叶节点的误分类比例进行加权累计求和，就得到了总的误分类概率。

并且，在10.3中，我们提到过，再代入误差是有趋于更小的，即树倾向生成更大的规模。我们证明了，父节点的误分类概率一定大于等于子节点误分类概率加权求和。

R(t)≥R(tL)+R(tR)

以上说明，如果我们用再代入误差最小化为策略时，我们总是倾向于选择更大的树，且无法解决减轻过拟合的影响。
(例子 略)

10.8.1 剪枝的预备知识

首先，我们先要生成最大的树，用 Tmax 来表示。
其次，设置停止生成树的阈值并不是那么重要。因为，只要树足够大，何时停止生成树影响不大。最后，树也都会在剪枝过程中被修减。下面列出几种决定何时停止生成树的方法：

1. 一直生成树，直到所有的叶节点都是”纯的”(只属于一类)
2. 一直生成树，直到所有的叶节点之和都不超过给定的阈值
3. 只要树足够大，原始树的大小就会变得不那么重要
   以上，重点就是要确保剪枝之前树要生成的足够大。

最后，我们需要预先进行一些定义：

1. Descendant: 如果一个节点 t′ 可以从一个节点 t 沿着一个连续路径向下派生出来，我们就说，t’是t的派生节点(Descendant)
2. Ancestor: 在1中的情况中，反过来说，t 是 t’的Ancestor节点
3. A branch Tt : 在一个树T 中，以一个节点t(t∈T)为根节点衍生出来的所有子(叶)节点，包括t点本身，构成了 Tt
4. 从树T 中剪枝去掉 Tt ，意味着从T中去掉t节点以及t节点派生出来的所有节点，可用 T?Tt 表示。
5. 如果T′ 是树T 已经剪枝成功后的状态，那么T’ 被称为T的剪枝后的子树，且 T′<T

即使对于适中规模的树来说，子树的数量都是非常巨大的。因此，我们无法穷尽遍历所有子树找到最优的情况。而且，我们通常也没有独立的测试集为有偏的选择提供服务。

我们需要更聪明的办法，这个办法需要满足以下两点：

• 某种程度上看，子树要是最优的
• 且，最优子树的搜索，计算量要保证简单易行
-

10.8.2 最小代价-复杂度的剪枝

如之前讨论的，再代入误差 R(T) 并不是一个很好选择子树的度量方式，因为它会倾向选择更大的树。我们需要加入对复杂度的惩罚，惩罚项要倾向于更小的树，以此来平衡再代入误差 R(T)。

代价-复杂度的定义：
对于任一子树 T<Tmax ,定义树的复杂度为 |T?| ,表示树的叶节点(终节点)的个数。定义实数 α≥0，被称作复杂度参数 ，则定义代价-复杂度 Rα(T) 为

Rα(T)=R(T)+α|T?|

叶节点越多，复杂度也就越大，因为我们把空间划分成子区域的方式会有更多，所以，会有更大的可能性更适合训练集的数据。除了复杂度，树的规模也是非常重要的。而这些问题都转化为用复杂度参数 α 来进行调整了。

最后，我们就说用上述的代价复杂度公式进行树的剪枝的。当 α=0 时，复杂度相当于被去掉，退化成再代入误差。所以，公式会选择生成最大规模的树。当 α 接近无穷大时，树的规模将为1，只有单一根节点。

通常，如果预先给定α 后，就能够找到子树T(α)，使得代价复杂度 Rα(T) 最小。

Rα(T(α))=min(Rα(T)),T≤Tmax

那么，对于任意一个 α，最小化子树总是可解的。因为只有有限多个子树。

两个问题：

1. 存在一个唯一的子树 T<Tmax ，满足 Rα(T) 最小么?
2. 在最小化子树的序列中，T1,T2,?每个子树能否通过对上一个子树剪枝得到，即，这些子树是嵌套的么?

如果最优的子树都是嵌套的，那么计算量将会大幅下降。我们先找到 T1 ，然后找 T2 时，不需要再从头开始，而是直接从 T1 开始(因为T2是T1的子树，是嵌套的)。随着 α 的增加，我们将对越来越小的树进行剪枝。

定义：对于参数α，最优最小树 Tα :

1. Rα(T(α))=min(Rα(T)),T≤Tmax
2. 如果 Rα(T)=Rα(T(α)) ，那么 T(α)≤T ，即，如果对于同样的 α,存在其他的树的代价复杂度同样也达到最小，那么其他树的规模一定是小于等于 T(α) .

根据上述定义，如果T(α)存在，那么一定是唯一的。之前我们也讨论过最小子树总是存在的，因为只有有限个子树。更近一步，我们可以证明最小子树总是存在的。这点是很重要的，因为一个树比另一个树小，说明它是是嵌套在大一点的树中的。

（编辑：衡阳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!