决策树剪枝算法

引言1、算法目的2、算法基本思路：3、决策树损失函数4、剪枝类型：4.1 预剪枝4.2 后剪枝4.3 两种剪枝策略对比

引言

\quad \quad在决策树、ID3、C4.5算法一文中，简单地介绍了决策树模型，以及决策树生成算法：决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即容易出现过拟合现象。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化，下面来探讨以下决策树剪枝算法。

1、算法目的

\quad \quad决策树的剪枝是为了简化决策树模型，避免过拟合。

同样层数的决策树，叶结点的个数越多就越复杂；同样的叶结点个数的决策树，层数越多越复杂。剪枝前相比于剪枝后，叶结点个数和层数只能更多或者其中一特征一样多，剪枝前必然更复杂。层数越多，叶结点越多，分的越细致，对训练数据分的也越深，越容易过拟合，导致对测试数据预测时反而效果差，泛化能力差。

2、算法基本思路：

\quad \quad剪去决策树模型中的一些子树或者叶结点，并将其上层的根结点作为新的叶结点，从而减少了叶结点甚至减少了层数，降低了决策树复杂度。

\quad \quad决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。

3、决策树损失函数

\quad \quad设树T的叶节点个数为∣T∣|T|∣T∣,t是树T的叶节点，该叶节点有NtN_tNt​个样本点，其中k类的样本点有NtkN_{tk}Ntk​个，k=1,2,...,Kk=1,2,...,Kk=1,2,...,K,Ht(T)H_t(T)Ht​(T)为叶节点t上的经验熵，α≥0\alpha\geq0α≥0为参数，则决策树学习的损失寒素可以定义为

Cα(T)=∑t=1∣T∣NtHt(T)+α∣T∣C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|Cα​(T)=t=1∑∣T∣​Nt​Ht​(T)+α∣T∣

其中，经验熵为Ht(T)=−∑kNtkNtlogNtkNtH_t(T)=-\sum_{k}\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}Ht​(T)=−k∑​Nt​Ntk​​logNt​Ntk​​

记C(T)=∑t=1∣T∣NtHt(T)=−∑t=1∣T∣∑k=1KNtklogNtkNtC(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}log\frac{N_{tk}}{N_t}C(T)=t=1∑∣T∣​Nt​Ht​(T)=−t=1∑∣T∣​k=1∑K​Ntk​logNt​Ntk​​

则 Cα(T)=C(T)+α∣T∣C_\alpha(T)=C(T)+\alpha|T|Cα​(T)=C(T)+α∣T∣C(T)C(T)C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度,|T|表示模型复杂度。α∣T∣\alpha|T|α∣T∣是为了避免过拟合，给优化目标函数增加一个正则项，正则项包含模型的复杂度信息|T|。对于决策树来说，其叶结点的数量 ∣T∣ 越多就越复杂。参数 α\alphaα 控制了两者之间的影响程度。较大的 α\alphaα促使选择较简单的模型（树），较小的 α\alphaα 促使选择较复杂的模型（树）。上式定义的损失函数Cα(T)C_\alpha(T)Cα​(T)的极小化等价于正则化的极大似然估计。

\quad \quad剪枝，就是当α\alphaα确定时，选择损失函数最小的模型，即损失函数最小的子树。当α\alphaα确定时，子树越大，往往与训练数据的拟合越好，但是模型的复杂度就越高；相反，子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好。损失函数正好表示了对两者的平衡。

4、剪枝类型：

\quad \quad决策树的剪枝基本策略有预剪枝 (Pre-Pruning) 和 后剪枝 (Post-Pruning) [Quinlan, 1933]。根据周志华老师《机器学习》一书中所描述是先对数据集划分成训练集和验证集，训练集用来决定树生成过程中每个结点划分所选择的属性；验证集在预剪枝中用于决定该结点是否有必要依据该属性进行展开，在后剪枝中用于判断该结点是否需要进行剪枝。

4.1 预剪枝

\quad \quad预剪枝是在决策树生成过程中，对树进行剪枝，提前结束树的分支生长。

加入预剪枝后的决策树生成流程图如下：

\quad \quad其中的核心思想就是，在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分；如果可以就继续递归生成节点。

4.2 后剪枝

\quad \quad后剪枝是在决策树生长完成之后，对树进行剪枝，得到简化版的决策树。

\quad \quad对于后剪枝，周志华老师《机器学习》中述说如下：

后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则将该子树替换为叶结点。

李航《统计学习方法》中述说如下：

输入：生成算法产生的整个树T，参数α\alphaα

输出：修剪后的子树TαTαTα

计算每个结点的经验熵递归地从树的叶结点向上回缩

\quad设一组叶结点回缩到父结点之前与之后的整体树分别为TBT_BTB​和TAT_ATA​，其对应的损失函数值分别是Cα(TB)Cα(T_B)Cα(TB​)与Cα(TA)Cα(T_A)Cα(TA​)，如果Cα(TA)≤Cα(TB)Cα(T_A)≤Cα(T_B)Cα(TA​)≤Cα(TB​)则进行剪枝，即将父结点变为新的叶结点。返回(2)，直至不能继续为止，得到损失函数最小的子树Tα

代码稍后更新

4.3 两种剪枝策略对比

后剪枝决策树通常比预剪枝决策树保留了更多的分支；后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树；后剪枝决策树训练时间开销比未剪枝决策树和预剪枝决策树都要大的多。

参考资料：

/yujianmin1990/article/details/49864813

/ylhlly/article/details/93213633