|
剪枝的开始点不是
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。
（编辑：泰州站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
