剪枝

╰半橙微兮° 2022-05-16 11:26 269阅读 0赞

将复杂的决策树进行简化的过程称为剪枝，它的目的是去掉一些节点，包括叶节点和中间节点。

剪枝常用方法：预剪枝与后剪枝两种。

预剪枝：在构建决策树的过程中，提前终止决策树生长，从而避免过多的节点产生。该方法不实用，我们无法判断何时终止树的生长。

后剪枝：在决策树构建完成后，再去掉一些节点。

常见的后剪枝方法有四种：

1.悲观错误剪枝（PEP）

2.最小错误剪枝（MEP）

3.代价复杂度剪枝（CCP）

4.基于错误的剪枝（EBP）

CCP可以用于CART算法中，它的本质是度量每减少一个叶节点所得到的平均错误。

每一个叶节点的减少，平均错误都会下降，CCP的本质就是通过计算度量其平均错误来进行的。

CCP算法会产生一系列树的序列，\{T1,T2,T3,......Tm\},其中T0是由训练得到的决策树，而Tm只含有一个根节点，序列中的树是嵌套的，也就是序列中的T(i+1)是由Ti通过剪枝得到的，即实现用T(i+1)中一个叶节点来替代Ti中医该节点为跟的子树。（此图可能有问题，后期我再改一下）

![70][]

这种被替代的原则就是使误差的增加率*α*最小，即：

![20160112133814466][]

式中，R(n)表示Ti中节点n的预测误差，*R*(*nt*)表示T*i*中以节点*n*为根节点的子树的所有叶节点的预测误差之和，|*nt*|为该子树叶节点的数量，|*nt*|也被称为复杂度，因为叶节点越多，复杂性当然就越强。

因此*α*的含义就是用一个节点*n*来替代以*n*为根节点的所有|*nt*|个节点的误差增加的规范化程度。

在T*i*中，我们选择最小的*α*值的节点进行替代，最终得到T*i*\+1。

以此类推，每需要得到一棵决策树，都需要计算其前一棵决策树的*α*值，根据*α*值来对前一棵决策树进行剪枝，直到最终剪枝到只剩下含有一个根节点的T*m*为止。

根据决策树是分类树还是回归树，节点的预测误差的计算也分为两种情况。

### **分类树：** ###

分类误差公式：可以采用1,2,3三个公式，详情请见：[https://blog.csdn.net/LEE18254290736/article/details/81842816][https_blog.csdn.net_LEE18254290736_article_details_81842816]

熵：![20160112131832033][]

基尼指数（Gini Index）：![20160112131937162][]

分类误差：![20160112132040826][]

假如用（3）来表示节点n的预测误差（这里R（n）就是直接等于分类误差的式子），则：

![20160112133857244][]

*Nj*表示节点*n*下第*j*个分类的样本数，*N*为该节点的所有样本数，max\{ *Nj*\}表示在*m*个分类中，拥有样本数最多的那个分类的样本数量。

### **回归树：** ###

我们用以下式子表示节点n的预测误差：

（熵计算用均方误差代替，把样本的预测值用样本数处置的平均来代替）

![20160112133116130][]

得到的式子为：

![20160112134409562][]

*yi*表示第*i*个样本的响应值，*N*为该节点的样本数量。

我们把分类树与回归树的这两个式子中，分子不分称为节点的风险值。

我们用全部样本得到的决策树序列为\{T0,T1,…,T*m*\}，其所对应的*α*值为*α*0<*α*1<…<*αm*。

下一步就是如何从这个序列中最优的选择一颗决策树T*i*。而与其说找到最优的T*i*，不如说找到其所对应的*αi*。

这一步骤通常采用的方法是交叉验证（Cross-Validation，定义请见：[https://baike.baidu.com/item/%E4%BA%A4%E5%8F%89%E9%AA%8C%E8%AF%81/8543100][https_baike.baidu.com_item_E4_BA_A4_E5_8F_89_E9_AA_8C_E8_AF_81_8543100]）。

我们把*L*个样本随机划分为数量相等的*V*个子集*Lv*，*v*=1,…,*V*。

第*v*个训练样本集为：

![20160112134509345][]

*Lv*被用来做*![70 1][]*的测试样本集。

对每个训练样本集*![70 1][]*按照CCP算法得到决策树的序列![70 2][]

其对应的*α*值为*α*0(*v*)<*α*1(*v*)<…<*αm*(*v*)。

*α*值的计算仍然采用![20160112133814466][]

对**分类树**来说，第*v*个子集的节点*n*的预测误差为：

![20160112134601767][]

*Nj*(*v*)表示训练样本集*L*(*v*)中节点*n*的第*j*个分类的样本数，*N*(*v*)为*L*(*v*)中节点*n*的所有样本数，max\{ *Nj*(*v*)\}表示在*m*个分类中，*L*(*v*)中节点*n*拥有样本数最多的那个分类的样本数量。

对于**回归树**来说，第*v*个子集的节点*n*的预测误差为：

![20160112134643526][]

*yj*(*v*)表示训练样本集*L*(*v*)中节点*n*的第*i*个样本的响应值。

[70]: /images/20220516/d16d3254e37349029bee4bce55b09523.png
[20160112133814466]: /images/20220516/70261a1f426b49749609fb0f9188c19e.png
[https_blog.csdn.net_LEE18254290736_article_details_81842816]: https://blog.csdn.net/LEE18254290736/article/details/81842816
[20160112131832033]: /images/20220516/ed7fec4e580a404ca807632c50abf2ff.png
[20160112131937162]: /images/20220516/e54a5f0178b64e478b778ff77691eb77.png
[20160112132040826]: /images/20220516/c75beba0c0e041f2b3f35e12e8df15f5.png
[20160112133857244]: /images/20220516/91c1e066342746f0a5943286a9155795.png
[20160112133116130]: /images/20220516/70dcbdbb0e5242f399933a3116e09ea5.png
[20160112134409562]: /images/20220516/f06101bba07f4628bb619341dff5a344.png
[https_baike.baidu.com_item_E4_BA_A4_E5_8F_89_E9_AA_8C_E8_AF_81_8543100]: https://baike.baidu.com/item/%E4%BA%A4%E5%8F%89%E9%AA%8C%E8%AF%81/8543100
[20160112134509345]: /images/20220516/3b80a5e3df4b4250b3d2b2e93183f485.png
[70 1]: /images/20220516/0dc087e4334c41b0870c4963d1b13ffc.png
[70 2]: /images/20220516/56443128df454927a6580ad73b8f5671.png
[20160112134601767]: /images/20220516/1f522e73c65f411698b9b2f26616b464.png
[20160112134643526]: /images/20220516/5cf72a748ce641aaa0ca313c2c003e23.png