|
剪枝的开始点不是
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
不等式右边是再代入误差的差值与复杂度差值的比值，因为分子分母均为正，所以值是正数。
（编辑：网站开发网_盐城站长网 ）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
