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

剪枝的开始点不是 Tmax (所有叶节点都是纯的),而是 T1=T(0) , T1 是 Tmax 的最小子树(最小损失复杂度)，且满足：

R(T1)=R(T(0))=R(Tmax)

得到 T1 的步骤如下：

首先，先来看最大树 Tmax ，然后从同一个父节点划分出两个叶节点 tL,tR ，如果这两个叶节点的再代入误差和与父节点的再代入误差相等，那么需要把这两个节点剪掉。即，当 R(t)=R(tL)+R(tR) 时，剪去左右子节点。

这个过程是递归实现的。当我们把一对子节点剪掉时，树的规模缩小了一点。然后，根据这个更小规模的树，同样进行递归，直到不满足等式为止。这样生成得到的树，就是从 T1 得到的。

我们来看一个例子－－－如何得到 Tmax

(图中，可以剪枝掉 t8,t9 ，所以从 T1 得到的剪枝应该树不包含这两个子节点的。满足： R(T1)=R(T(0))=R(Tmax) ，且小于等于 Tmax .)

我们定义 Tt 是以t为根节点的派生出来的树。对于 Tt ，我们定义这个树的再代入误差， R(Tt) ，为：
R(Tt)=∑t′∈T′tR(t′)
其中， T′t 为树的所有叶节点的集合。

可以证明，如果节点t 不是树 T1 叶节点，是中间节点，那么节点t的再代入误差一定大于该节点下的树的再代入误差，即 R(t)>R(Tt) 。如果我们把节点t 下的树剪掉，那么总体的再代入误差一定是增加的。

Weakest-Link Cutting

weakest link cutting 方法不仅能找到下一个最优子树对应的复杂度参数 α 的值，还能确定这个最优子树。

对于任意的t∈T1,定义 Rα(t)=R(t)+α*1
对于任意的以t节点衍生出的分支 Tt,定义 Rα(Tt)=R(Tt)+α|T?t|

则当α=0时, R0(Tt)<T0(t) ,当α保持足够小时，不等式都会成立。
当逐渐增大α时，因为Rα(Tt)的增速会更快，当α达到一个特定值，我们将会有等式 Rα(Tt)=Rα(t) .

如上图，当 α 继续增加，则不等式将出现反转，得到 Rα(Tt)>Rα(t)。
对于一些节点t 可能比其它节点更容易达到等式（所满足的条件）。以最小 α 值达到等式所满足条件的节点－被称为 weakest link. 可能会出现若干点同时满足等式得到 weakest link 节点的情况.

解不等式 Rα(Tt)<Rα(t) ,得到

α<R(t)?R(Tt)T??t?1

不等式右边是再代入误差的差值与复杂度差值的比值，因为分子分母均为正，所以值是正数。

定义函数 g1(t),t∈T1

定义分支 T1 中的最弱链节点 tˉ1 为 g1(t) 的最小值.

然后令 α2=g1(tˉ1)
为了根据 α2 得到最优子树，可以简单的移除掉 tˉ1 分支.如果有若干节点都达到了使 g1(t) 最小,我们就把这些节点衍生出的子树都剪掉。

α2 是 α1=0 之后的第一个值，使得最优树比 T1 规模要小. 对于所有满足 α1≤α<α2 的α，最优树都是 T1 .

令 T2=T1?Ttˉ1

重复之前的步骤，从 T2 而不是 T1 作为搜索最优树的开始,找到T2中的最弱链节点，剪掉对应的分支得到下一个最优子树。(递归思想)

所需计算

计算的时候，我们需要在每个节点存储一些值：

• R(t) －节点 t 的再代入误差. 只需计算一次.
• R(Tt)－节点 t 衍生的分支对应的再代入误差. 剪枝后需要重新计算
• |Tt| －节点 t 衍生分支下的叶节点数量. 剪枝后需要重新计算

(上述三个值要如何计算－略)

αk 的法则

法则认为，对于递增序列 {αk},αk<αk+1,k≥1,where α1=0

对于任意 k≥1,αk≤α<αk+1，最优树都满足 T(α)=T(αk)=Tk,与 αk 下得到的最优子树一致。这就说明，最优子树Tk在αk≤α<αk+1时，对于连续的 α 来说，最优子树都是Tk。

（编辑：PHP编程网 - 黄冈站长网）

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