Python机器学习 使用sklearn构建决策树复习

熵值的计算公式如上图。

预剪枝：是在决策树的生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分即结束树的构建并将当前节点标记为叶结点；

后剪枝：是先从训练集生成一棵完整的决策树，然后自底向上地对叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化为性能提升，则将该子树替换为叶结点。泛化性能的提升可以使用交叉验证数据来检查修剪的效果，通过使用交叉验证数据，测试扩展节点是否会带来改进。如果显示会带来改进，那么我们可以继续扩展该节点。但是，如果精度降低，则不应该扩展，节点应该转换为叶节点。

1. 预剪枝

下表为西瓜数据集

以信息增益准则来进行属性选择，从上表数据可以得到一棵决策树，如下图1所示：

这是未剪枝的决策树，以属性“脐部”来对训练集进行划分时，产生3个分支凹陷、稍凹，平坦，然而是否应该进行这个划分呢？预剪枝要对划分前后的泛化性能进行评估。

划分前，所有样例集中在根结点，若不进行划分，该结点被标记为叶结点，其类别标记为训练样例数最多的类别，若将该结点标记为“好瓜”。用上表中的验证集对这个单结点决策树进行评估，样例（4,5,8）被正确分类，另外的4个样例（9,11,12,13）分类错误，可得验证集上的精度为42.9%

若用属性“脐部”划分之后，三个结点分别包含训练样例（1,2,3,14）、（6,7,15,17）、（10,16）

三个结点分别被标记为叶结点“好瓜”、“好瓜”、“坏瓜”，此时验证集中的样例（4,5,8,9,13）被分类正确，验证精度，于是应该用“脐部”进行划分。

然后，决策树算法应该对蓝色结点进行划分，基于信息增益准则以“色泽”作为划分属性。使用色泽划分后，编号为9的验证集样本分类结果由正确转为错误，验证集下降为57.1%，故预剪枝测量将禁止蓝色结点2的被划分。

对于结点3，最优划分属性为“根蒂”，划分后验证集精度仍为71.4%。这个划分不能提升验证集精度，故预剪枝测量将禁止结点3的被划分。

对于结点4， 其所含训练样例已属于同一类，不再进行划分。

预剪枝使得很多决策树的很多分支没有展开，降低了过拟合的风险，同时显著减少了决策树的训练时间开销和预测时间开销。但是，另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但是在其基础上进行的后续划分却有可能带来性能显著提升。预剪枝 是一种“贪心”策略，这给预剪枝带来了欠拟合的风险。

2. 后剪枝

后剪枝先生成一颗完整的决策树，由图1可知，该决策树的验证精度为42.9%。现在自底向上地对叶结点进行考察，先看结点6，若将该分支剪去，则6变为叶结点，替换后叶结点包含编号（7,15）训练样本，该叶结点被标记为好瓜，此时决策树的验证精度提高至57.1%，于是后剪枝决定剪枝，剪枝后如下图2所示：

然后考察5，将其变为叶结点后包含编号为（6,7,15）的样例，叶结点标记为“好瓜”，此时决策树精度仍为57.1%。可以不进行剪枝。

对于结点2，将其子树换为叶结点，该叶结点包含编号为（1,2,3,14）的样例，标记为“好瓜”，此时决策树的验证集精度提高至71.4%，做剪枝处理。

对于结点3和1，将其对应子树替换为叶结点，所得决策树的验证集精度分别为71.4%和42.9%，均未得到提高，被保留。最终，基于后剪枝策略生成的决策树如图2所示，其验证精度为71.4%。

3. 两种策略的比较

后剪枝策略通常比预剪枝保留了更多的分支。一般情况下，后剪枝决策树的欠你和风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程在生成完全决策树之后才能进行，并且要自底向上对树中的所有非叶子结点逐一计算，因此训练时间开销比未剪枝决策树和预剪枝决策树的开销大得多。