CART树剪枝的操作的理解

我就是我 2022-06-03 01:22 221阅读 0赞

这里我就简单讲下CART剪枝的核心思想，纯属个人意见，如有不当，请指正。  
在《统计学习方法法》中已经提到了决策树的剪枝算法了，理所当然，我们是顺着书中提到的思路来理解下决策树剪枝的关键步骤。我们定义了  
![C\_\{\\alpha\}(T) = \\sum\_\{t =1\}^\{\\vert T\\vert\}N\_tH\_t(T) + \\alpha\\vert T\\vert][C_alpha_T_ _ _sum_t _1_vert T_vert_N_tH_t_T_ _ _alpha_vert T_vert]  
该定义表示了决策树的损失函数。whaterver它是什么，现在有了损失函数这个衡量标准，并且假设我们已经根据training set生成了一棵复杂的决策树，且参数![\\alpha][alpha]已知。算法该如何实现决策树的剪枝呢？

首先明确一个概念，原本躺在那的一堆数据集，在没有决策规则被挖掘时，我们只能知道数据集中的分类标签的情况。如银行贷款问题中，银行只知道有多少人可以贷款，有多少人不可以贷款，所以躺在那的数据集的不确定度是最高的。关于这部分的理解可以参看博文【[决策树之理解ID3算法和C4.5算法 - Demon-初来驾到 - 博客频道 - CSDN.NET][ID3_C4.5_ - Demon-_ - _ - CSDN.NET]】，由此决策树越复杂，整体数据的不确定度越低。（数据被规则所明确，即银行在得知用户有房子的情况下，能根据训练数据统计出所有用户都是可以贷款的，这样的规则被银行挖掘出来了。）那么，显而易见，规则越多，数据分类的不确定性将大大降低。

咱们来看看决策树损失函数的定义。其中第一部分 ![N\_tH\_t(T)][N_tH_t_T]就是事物的不确定性次数。我们都知道存在噪声的情况下，模型将趋于复杂。在决策树中也就是 ![\\vert T\\vert][vert T_vert]的数值越大。再来看看损失函数中的 ![\\alpha\\vert T\\vert][alpha_vert T_vert]，假设参数 ![\\alpha][alpha]已知的，那么复杂的模型，所带来的结果就是 ![\\alpha\\vert T\\vert][alpha_vert T_vert]也将增大。且决策树存在过拟合现象，那么为了使得损失函数减小，有两种办法：

1.  降低第一部分的不确定次数，但我们知道这是不可能的了，因为降低不确定次数的办法是再找寻一个特征，或者找寻特征的最优切分点。这在生成决策时就已经决定了，无法改变。  
    
2.  进行剪枝操作，这是可以的。剪枝最明显地变化就是叶结点个数变少。假设是一个三叉树，那么一次剪枝它的叶结点数减少2个。变化量为![2\\alpha][2_alpha]，有了这变化量，我们就可以用来求解最优决策子树了。

因为![\\alpha][alpha]参数给定，所以一次剪枝，损失函数的减少量也是固定的。所有子结点都是三叉树时，我们可以简单认为损失函数的减少量为2![\\alpha][alpha]。假设只有一个子结点发生剪枝，那么该子结点上的叶结点都将全部归并到该结点，由此我们计算此结点的不确定次数。倘若不确定次数增大的量超过2![\\alpha][alpha]，那么剪枝失败，算法将尝试其他子结点。因为新得的子树损失函数反而增大。这从侧面又反映了什么样的事实？该子结点的分类规则是大大降低不确定次数的，并不存在噪声，所以没必要进行剪枝。所以在剪枝过程中，找寻的就是那些噪声点，却被过度规则那些子结点，把这些合并了，万事大吉，自然而然决策树的准确率将上升。

在上述剪枝过程中，还需要注意一个有趣的问题。对应于每一个参数![\\alpha][alpha]，剪枝后的子树是唯一的嘛？个人觉得这是一个最基本的前提假设，在算法中，它提到了一点，给定参数![\\alpha][alpha]，找寻损失函数最小的子树![T\_\{\\alpha\}][T_alpha]，也就是说![<\\alpha,T\_\{\\alpha\}>][alpha_T_alpha]是一一对应的！并不存在一个![\\alpha][alpha]对应于多个子树。CART剪枝算法中将用到该基本假设。

那么问题来了，参数![\\alpha][alpha]给定的？谁来给？领域专家给？这是一种行之有效的办法，但却需要领域知识。理想化的模型都希望参数由data决定，也就是![\\alpha][alpha]也由数据决定。那么我们能想到的就是拿测试数据去测试在给定![\\alpha][alpha]下生成的子树。如果给定![\\alpha][alpha]下，测试数据的准确率达到一定阈值我们就以这个![\\alpha][alpha]为准。这就存在一个非常大的问题，![\\alpha][alpha]如何变化，才能让测试数据准确率呈现极大值？这个问题在上述算法中并不好解决！

**CART剪枝核心思想**  
刚才的思路是什么？从最宏观的角度去考虑的话，就是利用![\\alpha][alpha]生成![T\_\{\\alpha\}][T_alpha]。抽象一下，从【无限的实数】中找寻【有限个数的![T\_\{\\alpha\}][T_alpha]】，这问题当然不好解决了！思路其实已经出来了，CART剪枝算法的核心思想就是说，一个复杂的决策树，不管多复杂，都能生成有限个数的子树，我们记作![\\\{T\_0,T\_1,...,T\_n\\\}][T_0_T_1_..._T_n]，那么我们只要找寻到对应于每一个子树的![\\alpha][alpha]不就可以了嘛！没错，抽象一下，从【有限个数的![T\_\\alpha][T_alpha 1]】中找寻对应的【![\\alpha][alpha]】，万事解决。

咱们先来看看决策树损失函数的定义：  
![C\_\{\\alpha\}(T) = \\sum\_\{t =1\}^\{\\vert T\\vert\}N\_tH\_t(T) + \\alpha\\vert T\\vert][C_alpha_T_ _ _sum_t _1_vert T_vert_N_tH_t_T_ _ _alpha_vert T_vert]  
做一些数学变换得：  
![C\_\{\\alpha\}(T) = \\sum\_\{t =1\}^\{\\vert T\\vert\}N\_tH\_t(T) + \\alpha\\vert T\\vert = \\sum\_\{t=1\}^\{\\vert T \\vert\}(N\_tH\_t(T)+\\alpha)][C_alpha_T_ _ _sum_t _1_vert T_vert_N_tH_t_T_ _ _alpha_vert T_vert _ _sum_t_1_vert T _vert_N_tH_t_T_alpha]  
所以说，衡量损失函数大小的真正贡献在于每个叶结点，叶结点不确定次数的累加并加个常数![\\alpha][alpha]就是我们决策树整体的损失函数。

为了得到树T的所有子序列![\\\{T\_0,T\_1,...,T\_n\\\}][T_0_T_1_..._T_n]，我们需要从底自上，每次只进行一次剪枝操作，那么进行剪枝操作后，该子序列应该是当前参数的最优子树。且应该是根据所剪的那个结点来计算参数![\\alpha][alpha]。

为什么要这么做？接下来的思路是什么？因为我们刚才说了，是通过最优子树来求解参数![\\alpha][alpha]，**因此，我们先【假设】我们找到了当前的最优子树，且必然发生剪枝。【注意加黑的这句话！】**具体地，需要归并的子结点为t，以t为单结点损失函数就可以表示为：（该子结点t已经成为我们的叶结点咯！在接下来给出的公式中，请思考哪些是已知参数，哪些是未知参数。）  
![C\_\{\\alpha\}(t) = C(t)+\\alpha][C_alpha_t_ _ C_t_alpha]  
这公式是最初的决策树损失函数变化而来的！它是其中一个子结点【吞并】它的子树，所得到【叶结点后】的损失函数。还需要强调下，因为在最初理解这个C(t)含义时，自己也被搞混了。**该公式已经是剪枝完毕后的表达式了，也就是说原先的子结点已经变成了当前的叶结点。接下来会给剪枝前的表达式！![C(t)][C_t]**表示在该叶结点中的不确定次数。

那么【剪枝前】是什么情况呢？剪枝前是以t为根结点的子树![T\_t][T_t]的损失函数是： ![C\_\{\\alpha\}(T\_t) = C(T\_t)+\\alpha\\vert T\_t\\vert][C_alpha_T_t_ _ C_T_t_alpha_vert T_t_vert]  
也就是说，剪枝前该子结点的损失函数如上。具体的含义之前都有解释过，就不再叙述了。接下来我们要明确哪些是已知参数，因为决策树已经生成了，所以每个结点的不确定次数都是知道的，即![C\_(T)][C_T],![C\_(T\_t)][C_T_t]和![\\vert T\_t \\vert][vert T_t _vert]是已知的。未知参数是![\\alpha][alpha]如何求解？还记得加粗的假设嘛？

> **假设1：必然发生剪枝！**

从中我们便能求得![\\alpha][alpha]，为什么？我们来观察下，上述两个式子。

当![\\alpha =0][alpha _0]或者充分小，明显地，不确定次数：  
![C\_\{\\alpha\}(T\_t) < C\_\{\\alpha\}(t)][C_alpha_T_t_ _ C_alpha_t]  
决策树叶结点越多，不确定性越低，不解释。

当增大![\\alpha][alpha]时，总有那么一个点，能够使得：  
![C\_\{\\alpha\}(T\_t) = C\_\{\\alpha\}(t)][C_alpha_T_t_ _ C_alpha_t 1]

当继续增大![\\alpha][alpha]时，  
![C\_\{\\alpha\}(T\_t) > C\_\{\\alpha\}(t)][C_alpha_T_t_ _ C_alpha_t 2]  
不等式反向，所以我们只要取![\\alpha\_1 = \\frac\{C(t)-C(T\_t)\}\{\\vert T\_t\\vert-1\}][alpha_1 _ _frac_C_t_-C_T_t_vert T_t_vert-1]时，当且仅当![\\alpha \\ge \\alpha\_1][alpha _ge _alpha_1]时，剪枝必然发生。![\\alpha][alpha]必须满足上述条件，否则前提假设将失去意义。所以说，我们通过假设剪枝必然发生就能找到对应的![\\alpha][alpha]。可对于任何一个子结点t都可以嘛？别忘了第二个假设。

> **假设2：剪枝发生后，当前决策树是我们的最优子树**

最优子树？现在t变成了一个变量，因为我们并不知道到底剪枝哪个子结点后决策树是最优的。不急，再来看看，公式：

![C\_\{\\alpha\}(t) = C(t)+\\alpha][C_alpha_t_ _ C_t_alpha]  
剪枝已经发生，此时，对应于每一个子结点t会生成不同的![\\alpha][alpha]我们记作![\\alpha(t)][alpha_t]，由此得：![C\_\{\\alpha\}(t) = C(t)+\\alpha(t)][C_alpha_t_ _ C_t_alpha_t]  
剪枝的决策树什么时候最优？对于当前参数![\\alpha(t)][alpha_t]而言，能够找到这样的t，使得![\\min\_\{t\}\\\{C(t)+\\alpha(t)\\\}][min_t_C_t_alpha_t]  
然而在这里为了能够求得![\\alpha][alpha]的一个序列，貌似直接最小化了  
![\\min\_\{t\}(\\frac\{C(t)-C(T\_t)\}\{\\vert T\_t\\vert-1\})][min_t_frac_C_t_-C_T_t_vert T_t_vert-1]  
找的![\\alpha][alpha]即找到了子结点t，即完成了剪枝，即找到了最优子树![T\_1][T_1]。有了上述的步骤，为了得到决策树![T\_0][T_0]的所有子序列，直接递归下去，直到根节点即可。在这一过程中，不断地增加![\\alpha][alpha]的值，产生新的区间。

后面的思路就很简单了，根据生成的子树序列，用测试集去测试这些子树，谁的测试准确率最高，谁就获胜。具体算法可以参看《统计学习方法》，讲的很详细。

总的来说，CART剪枝算法的核心在于用【有限个子树 ![T\_\{\\alpha\}][T_alpha]】计算【无限个 ![\\alpha][alpha]】，你会发现，计算过程中 ![\\alpha][alpha]变成了一个个分段区间。在利用公式推导时，注意【必剪枝】和【当前最优子树】的两个假设，且时刻问自己【已知参数】和【未知参数】是哪些。

[C_alpha_T_ _ _sum_t _1_vert T_vert_N_tH_t_T_ _ _alpha_vert T_vert]: https://www.zhihu.com/equation?tex=C_%7B%5Calpha%7D%28T%29+%3D+%5Csum_%7Bt+%3D1%7D%5E%7B%5Cvert+T%5Cvert%7DN_tH_t%28T%29+%2B+%5Calpha%5Cvert+T%5Cvert
[alpha]: /images/20220603/014185fa6fa44365a09f64988364e216.png
[ID3_C4.5_ - Demon-_ - _ - CSDN.NET]: https://link.zhihu.com/?target=http%3A//blog.csdn.net/u014688145/article/details/53212112
[N_tH_t_T]: https://www.zhihu.com/equation?tex=N_tH_t%28T%29
[vert T_vert]: https://www.zhihu.com/equation?tex=%5Cvert+T%5Cvert
[alpha_vert T_vert]: /images/20220603/014185fa6fa44365a09f64988364e216.png%5Cvert+T%5Cvert
[2_alpha]: /images/20220603/c0bd23e51146458eb824e02d7aad3807.png
[T_alpha]: https://www.zhihu.com/equation?tex=T_%7B%5Calpha%7D
[alpha_T_alpha]: https://www.zhihu.com/equation?tex=%3C%5Calpha%2CT_%7B%5Calpha%7D%3E
[T_0_T_1_..._T_n]: https://www.zhihu.com/equation?tex=%5C%7BT_0%2CT_1%2C...%2CT_n%5C%7D
[T_alpha 1]: https://www.zhihu.com/equation?tex=T_%5Calpha
[C_alpha_T_ _ _sum_t _1_vert T_vert_N_tH_t_T_ _ _alpha_vert T_vert _ _sum_t_1_vert T _vert_N_tH_t_T_alpha]: https://www.zhihu.com/equation?tex=C_%7B%5Calpha%7D%28T%29+%3D+%5Csum_%7Bt+%3D1%7D%5E%7B%5Cvert+T%5Cvert%7DN_tH_t%28T%29+%2B+%5Calpha%5Cvert+T%5Cvert+%3D+%5Csum_%7Bt%3D1%7D%5E%7B%5Cvert+T+%5Cvert%7D%28N_tH_t%28T%29%2B%5Calpha%29
[C_alpha_t_ _ C_t_alpha]: https://www.zhihu.com/equation?tex=C_%7B%5Calpha%7D%28t%29+%3D+C%28t%29%2B%5Calpha
[C_t]: /images/20220603/0e7fbb3d4e7146efb12c3742804161a6.png
[T_t]: https://www.zhihu.com/equation?tex=T_t
[C_alpha_T_t_ _ C_T_t_alpha_vert T_t_vert]: https://www.zhihu.com/equation?tex=C_%7B%5Calpha%7D%28T_t%29+%3D+C%28T_t%29%2B%5Calpha%5Cvert+T_t%5Cvert
[C_T]: https://www.zhihu.com/equation?tex=C_%28T%29
[C_T_t]: https://www.zhihu.com/equation?tex=C_%28T_t%29
[vert T_t _vert]: https://www.zhihu.com/equation?tex=%5Cvert+T_t+%5Cvert
[alpha _0]: /images/20220603/014185fa6fa44365a09f64988364e216.png+%3D0
[C_alpha_T_t_ _ C_alpha_t]: https://www.zhihu.com/equation?tex=C_%7B%5Calpha%7D%28T_t%29+%3C+C_%7B%5Calpha%7D%28t%29
[C_alpha_T_t_ _ C_alpha_t 1]: https://www.zhihu.com/equation?tex=C_%7B%5Calpha%7D%28T_t%29+%3D+C_%7B%5Calpha%7D%28t%29
[C_alpha_T_t_ _ C_alpha_t 2]: https://www.zhihu.com/equation?tex=C_%7B%5Calpha%7D%28T_t%29+%3E+C_%7B%5Calpha%7D%28t%29
[alpha_1 _ _frac_C_t_-C_T_t_vert T_t_vert-1]: /images/20220603/014185fa6fa44365a09f64988364e216.png_1+%3D+%5Cfrac%7BC%28t%29-C%28T_t%29%7D%7B%5Cvert+T_t%5Cvert-1%7D
[alpha _ge _alpha_1]: /images/20220603/014185fa6fa44365a09f64988364e216.png+%5Cge+%5Calpha_1
[alpha_t]: /images/20220603/014185fa6fa44365a09f64988364e216.png%28t%29
[C_alpha_t_ _ C_t_alpha_t]: https://www.zhihu.com/equation?tex=C_%7B%5Calpha%7D%28t%29+%3D+C%28t%29%2B%5Calpha%28t%29
[min_t_C_t_alpha_t]: /images/20220603/dd4caae31a8c412185aed814d9b6b842.png
[min_t_frac_C_t_-C_T_t_vert T_t_vert-1]: https://www.zhihu.com/equation?tex=%5Cmin_%7Bt%7D%28%5Cfrac%7BC%28t%29-C%28T_t%29%7D%7B%5Cvert+T_t%5Cvert-1%7D%29
[T_1]: https://www.zhihu.com/equation?tex=T_1
[T_0]: https://www.zhihu.com/equation?tex=T_0