决策树的优化-剪枝

为什么决策树需要剪枝？我们可以类比于神经网络的“过拟合”问题来进行思考。在神经网络之中，会出现过拟合问题，即出思安对特定的样本识别率升高，对其余样本的识别率降低。在决策树中也会出现类似的问题，会出现枝条过多的现象，是问题复杂化，准确率却得不到上升。

决策树的剪枝分为2种，一种是预剪枝，第二种是后剪枝。

预剪枝：在创建进行到某一个节点处，我们先计算当前节点的准确率，然后在按照该节点的属性进行分类，在计算分类后的准确率，比较和，如果较大则该节点不需要进一步的分枝，否则如果较大则该节点需要进行分枝操作。

后剪枝：首先我们要有一颗完整的决策树，然后从该决策树的叶子节点的父节点开始，分别计算该父节点不分枝的准确率和分枝后的准确率，继续和预剪枝的一样的操作，决定是否进行剪枝操作，然后向上寻找，逐个判断。

例子：

我们拿脐部作为节点进行说明，脐部的好瓜有{4,5,8}共3个，坏瓜有{9,11,12,13}共4个，准确率为3/7，大概为42.9%。

分枝后我们有凹陷，稍凹，平坦三个属性。我们认为凹陷与稍凹是好的，平坦是坏的。凹陷有{4,5,13}共3个，其中2个判断正确。稍凹有{8,9}共2个，1个判断正确。平坦有{11,12}共2个，2个判断正确。故最终准确率为5/7，大概为71.4%，大于42.9%，故该节点进行分枝操作。