CART剪枝

今天药忘吃喽~ 2021-09-30 06:50 276阅读 0赞

### 1. CART剪枝介绍 ###

> CART 剪枝算法从完全生长的决策树的底端剪去一些子树，使决策树变小（模型简单），从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成：首先从生成算法产生的决策树\\(T\_0\\)底端开始不断剪枝，直到\\(T\_0\\)的根节点，形成一个子序列\\(\{T\_0,T\_1,T\_3,.....T\_n\}\\),然后通过交叉验证在独立的验证集上对子树序列进行测试，从中选择最优子树。

### 2. 剪枝的两个过程 ###

#### 2.1 剪枝，形成一个子树序列 ####

> 在剪枝过程中，计算子树的损失函数\\\[C\_\{\\alpha\}(T) = C(T) + \\alpha|T|\\\]  
> 其中，T为任意子树，\\(C(T)\\)为对训练数据的预测误差（如基尼系数），\\(|T|\\)为子树叶节点个数，\\(\\alpha >= 0\\),\\(C\_\{\\alpha\}(T)\\)为参数是\\(\\alpha\\)时的子树\\(T\\)的整体损失，参数\\(\\alpha\\)权衡训练数据的拟合程度与模型的复杂度。  
> 对于每一个给定的\\(\\alpha\\)，都有唯一的最优子树\\(T\_\{\\alpha\}\\)使得\\(C\_\{\\alpha\}(T)\\)最小。  
> 下面是通过\\(\\alpha\\)的变化来解释树的复杂度
> 
> > 当\\(\\alpha\\)比较大的时候，最优子树\\(T\_\{\\alpha\}\\)偏小  
> > 当\\(\\alpha\\)比较小时，最优子树\\(T\_\{\\alpha\}\\)偏大  
> > 当\\(\\alpha = 0\\)时，最优子树为未剪枝的\\(T\_0\\)  
> > 当 \\(\\alpha\\rightarrow+\\infty\\),最优子树为根结点树

> 具体的,从整体树\\(T\_0\\)开始剪枝，对\\(T\_0\\)的的任意内部结点\\(t\\),以\\(t\\)为单结点树的损失函数为\\\[C\_\{\\alpha\}(t) = C(t) + \\alpha\\\]  
> 以\\(t\\)为根结点的子树\\(T\_t\\)的损失函数是\\\[C\_\{\\alpha\}(T\_t) = C(T\_t) + \\alpha|T\_t|\\\]  
> 当\\(\\alpha=0\\)或充分小时，有不等式\\\[C\_\{\\alpha\}(T\_t) < C\_\{\\alpha\}(t)\\\]  
> 当\\(\\alpha\\)增大时，必在某一点有\\\[C\_\{\\alpha\}(T\_t) = C\_\{\\alpha\}(t)\\\]  
> 此时可以计算得到\\\[\\alpha = \\frac\{C(t) - C\_\{\\alpha\}(T\_t)\}\{|T\_t| - 1\}\\\]  
> 当\\(\\alpha\\)继续增大时，不等式反向，只要\\(\\alpha = \\frac\{C(t) - C\_\{\\alpha\}(T\_t)\}\{|T\_t| - 1\}\\)，\\(T\_t\\)与\\(t\\)有相同的损失函数值，而\\(t\\)的结点少，因此\\(t\\)比\\(T\_t\\)更可取，对\\(T\_t\\)进行剪枝。  
> 通过上述方法，我们可以计算出\\(\{(\\alpha\_0,T\_0),(\\alpha\_1,T\_1),....(\\alpha\_n,T\_n)\}\\)

#### 2.2 在剪枝得到的子树序列\\(\{T\_0,T\_1,T\_2,...T\_n\}\\)中通过交叉验证选取最优子树\\(T\_\{\\alpha\}\\) ####

> 具体地，利用独立的验证数据集，测试子树序列\\(T\_0,T\_1,....T\_n\\)中各棵子树的平方误差或基尼指数。依据平方误差或基尼指数最小来选择其中最优的决策树，其相应的\\(\\alpha\\)也就确定了，得到最优决策树\\(T\_\{\\alpha\}\\)

转载于:https://www.cnblogs.com/lpworkstudyspace1992/p/8030186.html