CCP剪枝

2019-05-11  本文已影响0人  7NIC7

    在一棵树生长完成后,往往需要剪枝,这是因为一颗完整的决策树往往容易过拟合。
    CCP即为基于复杂度的剪枝(cost complexity pruning).

一 概念

    在介绍CCP剪枝的原理之前,我们先来介绍一下什么是剪枝以及剪枝所用的评价指标。
1.什么是剪枝?如图,显示了对节点t进行剪枝的过程。

prun.png

2.如何计算整棵决策树的误判率?
    整棵树的误判率被定义为各个叶子节点误判率的加权平均,权重是该叶子节点的样本数的占比。
R(T) = \sum_{t \in \tilde{T}} p(t) r(t)
其中,\tilde{T}代表叶子节点,p(t)是节点t处的样本比例,r(t)是节点t处的误判率。r(t)=1- \max_j p(c_j|t)

二 CCP原理

    CCP的基本形式是找到一个子树使得下式最小:
\min_T R_\alpha(T) = \min_T (R(T) + \alpha |\tilde{T}|)
\alpha是一个复杂度参数,当\alpha较小时,倾向于选择一个较大的树,增大\alpha的值,会减小树的大小。|\tilde{T}|代表所有叶子节点的个数。
    在正式介绍CCP之前,大家可以先想一下以下两个问题并带着这两个问题进行接下来的阅读。

    先来回答问题1,我们可以对最终选取的子树T(\alpha)做如下定义:
T(\alpha) = \arg \min_{T } R_\alpha(T),若另一个子树T使得R_\alpha(T) = R_\alpha(T(\alpha)),则必然有T(\alpha) \leq T
按照这样的定义选出的子树T(\alpha)是存在且唯一的。这个定义的意思就是如果有两个子树得到的误判率R是相同的,则选取较小的子树作为最终的决策树。

    问题2的答案就在下面的内容中,为了使得后产生的子树包含在之前的子树内,我们采取序贯剪枝的策略。

2.1 子树的产生

    在对CCP有了大概的认识之后,需要找到一系列子树。为什么要产生这些子树呢?
    为了回答这个问题,再回到上面那张剪枝图中,虚线下方的所有节点称为T_t

prun2.png

    下面列出剪枝前后的决策树误判率的相对值,为什么称作相对值呢?因为除了被裁剪的部分,其他节点的误判率和节点个数并不会发生改变,因此我们在这里只关注剪枝的部分。

    当R_{after} > R_{before},即剪枝后误差增大时不会进行剪枝操作,解出\alpha < \frac{R(t) - R(T_t)}{|\tilde{T}| - 1 },且不等号右边的值大于零。
    原则上\alpha是可以取任意连续值,但是可以想象,随着\alpha的缓慢增大,并不一定需要剪枝,只有当\alpha增大到某个值时,我们发现剪枝减小的叶子节点个数已经可以弥补误判率的增高时,才会去剪枝。也就是在真实情况下,\alpha其实是一个离散的序列,下面介绍的弱连接可以帮助我们找到这些需要进行剪枝操作的\alpha序列。

2.2 Weakest-link弱连接

    \min_t g(t) = \frac{ R(t) - R(T_t)}{|\tilde{T}| - 1 }就是弱连接的定义,就是在树中找到一个节点t使得g(t)最小,也就是达到了剪枝的临界点,可以将节点t以下的节点剪除,继而在这个新的树中再重新寻找弱连接,这样下一次剪枝是在上一次剪枝的基础之上即为序贯剪枝。对完整的决策树T,根据弱连接找\alpha序列,下面是具体过程,

从而得到一系列的子树{T_1,T_2,...},以及\alpha序列{\alpha_1, \alpha_2,...}。\alpha_i的不同取值对应着不同的子树T_i,当\alpha_k < \alpha < \alpha_{k+1}时,最小化R_\alpha(T)的子树是T_k

\alpha 的选取

    主流做法就是交叉验证。下面给出找出最优\alpha的伪代码。


for \alpha do
    for i in 1,2,...k do
        D 分为D^{(i)}D^i,D^{(i)}=D - D^i
        用D^{(i)}产生T_{max}
        根据CCP产生一系列的子树,找到\alpha对应的子树T_{\alpha}
        计算D^iT_\alpha上的误判率,记为R_i
    R_\alpha = 1/k \sum R_i
arg\min_\alpha E_\alpha


上一篇 下一篇

猜你喜欢

热点阅读