开发者学堂课程【高校精品课-北京理工大学-数据仓库与数据挖掘（上）：Overfitting and Tree Pruning】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/921/detail/15644
Overfitting and Tree Pruning
内容介绍：
一、过拟合
二、树剪枝
三、决策树分类方法优势和不足
一、过拟合
1.概念
如果构造的决策树模型比较复杂，在训练集上就可能会出现 overfitting 的现象，称之为过拟合。
比如上图所示，有两类数据对象，红色和蓝色的数据对象，如果构建的决策树模型复杂类似于绿色的一条曲线，可以非常完美的把红色点和蓝色点区分开，也就是样的模型，在训练集上的效果效果是非常好的。在其他的数据集上，比如测试集效果会比较差。这种现象就是叫做过拟合的现象。
2.过拟合例子
通过一个例子介绍过拟合的现象。首先通过人工的方式构造一个数据集。数据集包含两类，第一类是蓝色的加号，模拟高斯分布利用高斯分布产生5000个点，并在5000个点的基础上，添加400个噪音点。此外，还有一类数据是红色的圆圈。红色圆圈的数据是通过一个均匀分布，产生5400个点。
在得到训练数据之后，从训练数据中抽取10%作为训练集。而剩余90%作为测试集。
3.Which tree is better?
根据训练集，可以构建很多种决策树模型。表列出了决策树的节点和决策树的 Error rate 之间的关系。随着决策树中节点数的增加，决策树模型在训练集上的 Error rate 也就是分类的错误率会越来越低。
（1）、两个模型。比如构建的是一个具有四个节点的决策树模型。Error rate 大概是0.1左右，还可以构建一棵由50个节点构成的决策树模型，Error rate 可能大概是0.9左右。那么这样的一个比较复杂的决策树模型的 Error rate 比较小。
（2）、两个模型比较
那一个模型就比较好呢？看一下两个模型在测试集上的表现。
在下图展示的是一些结构比较简单的决策树的节点数和他的Error rate 之间的变化关系。
其中，蓝色的线代表的是在训练集上的分类错误，而红色的线代表的是在测试集上的分类错误。
现在可以看到，当节点数比较小的时候，分类模型的在测试集和训练集上的 Error rate 表现是很类似的，都是随着节点数的增加而降低。
但是，当分类数模型如果比较复杂，也就是节点数比较多的时候。分类性能就会出现一些差异，随着节点数的增加，刚开始在测试集上的 Error rate 和训练集上的 Error rate 变化是一样的，都是下降，但是当节点增加到某一个区间之后，分类器的性能在测试集上的 Error rate 会随着节点数的增加而增加。所以说过于复杂的模型，那么在测试集上的表现效果可能就会比较差。
4.复杂的模型在测试集上比较差原因
过于复杂的模型在测试集上的表现效果会比较差原因，主要就是因为模型比较复杂。很好的去拟合了一个训练集。但是训练集中，可能有一部分数据代表的是噪音或者是异常。把这一部分噪音和异常也学习到分类模型里面去了，就导致比较复杂的分类模型在测试集上的效果反而不太好，这种现象就是overfitting。与之对应的就是underfitting欠拟合，欠拟合指的是分类模型构建的太简单了，在测试集和训练集上性能都不太好，Error rate 都比较大。
二、树剪枝
在决策树中主要是通过树剪枝来。避免过拟合的问题。在决策树剪枝的方法中主要是有两种策略，一种叫做预剪枝，一种叫做后剪枝。
1.预剪枝
所谓的预剪枝就指在构建一棵决策树的过程中，设立一些合适的预值。利用这些预值去判断某些节点是不是需要停止构建。
对于预剪枝来说，实行是比较困难的，主要的原因是没有办法去选择比较合适的预值。
2.后剪枝
在决策树中使用比较多的剪枝策略是后剪枝。对于后剪枝来说，首先完成决策树的构建，然后移除决策树中的某些分支，比较移出后的决策树的分类性能和之前决策树的分类性能，如果变化不大，就认为这些分支是可以被剪掉的。
3.标记的数据
在决策树剪枝的时候，需要使用到一组有标记的数据，用来去比较剪之前和剪之后的决策树的分类性能。那么，这样的一部分有标记的数据是独立于训练集的。
三、决策树分类方法优势和不足
以上就是关于决策树的知识。对于决策树来说，这种分类方法，是有一些优势的，也有一些不足之处在。
1. 优势
所有的优势中，其中有一点是非常重要的，也就是基于决策树的分类模型，是非常易于理解的。对于一个决策树模型来说，可以用 if that 的规则去表达它的分类模型，那么这样的一种分类规则是非常符合人类认知特点的，容易被人类去理解的，它比一些复杂的数学公式要被人们易于接收。所以，对于基于决策树的分类起来说，一个最大的优点就是便于理解。那此外，基于决策树的分类器，它的性能也是比较好的。
2.缺点
对于决策树分类器来说，一个缺点就是在进行属性测试条件选择的时候，每一次我们就只能选择一个属性。大分类中，实际上有很多属性是相互组合在一起或者是相互影响，从而影响类别。
