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

定义函数 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。

在剪枝的初始步骤中，算法倾向于快速的剪去包含许多叶节点的大分支。然后，剪枝速度会随着树的变小而越来越慢，算法倾向于剪掉更少的点。

10.8.3 最优的剪枝后的子树

有两种方法来选择最优的剪枝后的子树：

（编辑：网站开发网_盐城站长网 ）

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