4.3.1有监督学习(三) - 决策树(Decision Tree) - 剪枝(Pruning)
简介
决策树是与有监督学习中的常用方法。决策树的算法多见于分类问题中,即我们常说的分类树(Classification Tree);少数情况下,决策树也可以用于连续问题,即回归树(Regression Tree)。若构建决策树的自变量过多,会产生高维度、过拟合等问题,因此,需要在全树的基础上进行剪枝,保留最有效的自变量,删除不那么重要的自变量。这一过程,就叫剪枝。
一句话解释版本:
剪枝分为前剪枝与后剪枝,通过留出法在测试集上比对剪枝前后的效果来判定是否剪枝。
数据分析与挖掘体系位置
决策树是有监督学习中的一种模型。所以在数据分析与数据挖掘中的位置如下图所示。
剪枝的目的
对决策树进行剪枝的目的是为了防止过拟合(Overfitting)问题。
过拟合就是值学习器把样本学的太好了,把一些只属于训练集的特性也当作了一般性规律处理。在决策树中,过多的分支会使模型将一些个性化特征视为一般性特征,降低了泛化能力。因此就需要我们通过剪枝减少分支(自变量)个数。
剪枝的方法
剪枝的方法分为:预剪枝(pre-pruning)与后剪枝(post-pruning)。
预剪枝是在决策树生成的过程中剪枝。即,对每个结点在划分前估计,若当前结点的划分不能使决策树泛化性能提升,则停止划分,并将当前结点标记为叶结点。
后剪枝是在决策树生成完整后剪枝。即,先生成一个完整的决策树,然后从枝叶的最末端往树干方向逐一考察非叶结点,若将非叶结点对应的子树替换为叶结点能提升模型泛化能力,则在此剪枝,将子树替换为叶结点。
剪枝的步骤
一、留出法:划分样本
模型的泛化能力可以通过留出法验证,即将样本划分为互斥的样本训练集与样本测试集。在训练集上建立模型,在测试集上应用模型并评估预测结果的好坏。若通过剪枝,能够让决策树在测试集上的表现得到提升,就代表通过剪枝模型的泛化能力得以增强。
同样用4.3.1有监督学习(二) - 决策树(Decision Tree) - 构建树的核心指标 中的样本数据,我们总共17条数据中的10条作为训练集(Training Sample),7条作为测试集(Testing Sample)。
10条训练集数据中,分别有5条最终决策是“去玩”,5条是“不出去玩”。样本划分结果如下图所示:
二、构建树:信息增益/增益率/基尼系数
第二步,我们需要基于训练集的数据构建一棵完整的决策树。构建树的方法,可以是4.3.1有监督学习(二) - 决策树(Decision Tree) - 构建树的核心指标 中的任何一种。
这里,我们使用相对较为简单的信息增益计算出未剪枝的完整的树。
三、预剪枝
首先,我们来分析预剪枝。基于第二步计算出的信息增益,我们最先选取属性“双休日”划分训练集。预剪枝首先要评判这个划分是否需要。具体的评判标准如下:
划分之前,所有样本集中在根节点,证明我们没有做任何划分。那么,我们把所有类别标记为训练样例数最多的类别,把所有的决策都定义为:“去”。所以不论是否双休、是否加班、女友是否同意、天气如何,我们都会选择“去玩”。那么,把这种评定标准带入到测试集中,我们会发现,分对了3个,分错了4个。在测试集上的精度为:3/7 * 100% = 42.9%。
划分之后,也就是我们通过属性“双休日”对样本进行划分后,双休日为“是”的中有“去”占4/5,双休日为“否”的中有“去”占1/5,所以我们可以得到下面的划分图:
其中,双休日为“是”这条分支在测试集中全部预测正确,双休日为“否”这条分支在测试集中也全部预测正确。
所以,在划分后,精度由原先的42.9%上升为100%,那么代表这个分支是很有效的。我们肯定要保留此分支。
之后,我们要对下一级的分支重复此操作,其结果就是下图
所以,将在属性“双休日”后就对决策树进行剪枝。最终,剪枝后的树精度为100%。
但是,预剪枝存在的风险在于,由于剪枝是一层一层向下推进的,有些属性在一些属性的基础上才会有性能的提高,但是预剪枝不能考虑这些问题,有时候在开始就把整个枝都给剪掉了,这也可能会导致“欠拟合”问题。
四、后剪枝
后剪枝是从树的最末端开始往上判断。
首先,我们判断,一颗完整的树,其在测试集上的精度为多少?将测试样本带入模型后,我们发现7个测试样本中,5个预测对了,2个预测错了(BH:8与13)。所以,模型的精度为5/7 = 71.4%。
之后,后剪枝先考察最末端的分支,即“女朋友”属性,将这个分支删除后,“天气”属性为多云的结果判定为“去”(当样本两种结果几率一样时,任意选择一个)。此时,模型的精度下降为57.1%。因此后剪枝判定不剪枝。
但是,这里有个有趣的事实,因为样本量太少,在删除了“女朋友”属性后,“天气”=“多云”且“双休日”=“否”的样本只剩下两个,一个是去玩,一个是不去玩。这时,我们只能任意选其一作为叶结点的结果。如果,我们将“天气”属性为多云的结果判定为“不去”,那么,模型的精度反而会提升到85.7%,后剪枝会判定剪枝。
所以,这就反映出了样本足够大,以及样本抽取合理的重要性。
总体而言,后剪枝比前剪枝保留的分支可能更多一些,产生欠拟合的几率相对小一些,泛化能力也好于决策树。
剪枝的在Python与R中的实现
代码好长,不想放这里占地方,请去Github下载吧。
https://github.com/starsfell/decision_tree
参考资料:
【1】周志华:《机器学习》