模型的过分拟合

分类模型的误差大致分为两种：训练误差和泛化误差。训练误差也称为再代入误差或表现误差，是在训练记录上误分类样本比例，而泛化误差是模型在未知记录上的期望误差。

注意,当决策树很小时,训练和检验误差都很大,这种情况称作模型拟合不足( modelunderfitting)。出现拟合不足的原因是模型尚未学习到数据的真实结构,因此,模型在训练集和检验集上的性能都很差随着决策树中结点数的增加,模型的训练误差和检验误差都会随之降低。然而,一旦树的规模变得太大,即使训练误差还在继续降低,但是检验误差开始增大,这种现象称为模型过分拟合( model overfitting)。

产生原因：噪声导致的过分拟合、缺乏代表性样本导致的过分拟合

过分拟合与多重比较过程：考虑未来10个交易日股市是升还是降的任务，如果股票分析家简单地随机猜测,则对任意交易日预测正确的概率是05,然而,10次猜测至少正确预测8次的概率是:

=0.0547

这看起来不大可能!

假设我们想从50个股票分析家中选择一个投资顾问,策略是选择在未来的10个交易日做出最多正确预测的分析家。该策略的缺点是,即使所有的分析家都用随机猜测做出预测,至少有个分析家做出8次正确预测的概率是:

=0.9399

这相当高。尽管每个分析家做出8次正确预测的概率很低,但是把他们放在一起,找到一个能够做出8次正确预测的分析家的概率却很高。此外,不能保证这样的分析家以后还能通过随机猜测继续做出准确的预测。

多重比较过程与模型过分拟合有什么关系呢?许多学习算法都利用一个独立的候选集{γi}然后从中选取最大化给定标准的γmax。算法将把γmax添加到当前模型中,以提高模型的整体性能。重复这一过程,直到没有进一步的提高。例如,在决策树增长过程中,可以进行多种测试,以确定哪个属性能够最好地划分训练数据,只要观察到的改进是统计显著的,就选取导致最佳划分的属性来扩展决策树。

泛化误差估计：

1.使用再代入估计做乐观估计

再代入估计方法假设训练数据集可以很好地代表整体数据,因而,可以使用训练误差(又称再代入误差)提供对泛化误差的乐观估计。在这样的前提下,决策树归纳算法简单地选择产生最低训练误差的模型作为最终的模型。然而,训练误差通常是泛化误差的一种很差的估计。

2.结合模型复杂度

如前所述,模型越是复杂,出现过分拟合的几率就越高,因此,我们更喜欢米用较为简单的模型。这种策略与应用众所周知的奥卡姆剃刀(Ocam' s razor)或节俭原则( principle of parsimony)致。

奥卡姆剃刀是很直观的原则,因为复杂模型中的附加成分很大程度上是完全对偶然的拟合。用爱因斯坦的话来说,“所有事情都应该尽可能简单,但不是简化。”下面我们介绍两种把模型复杂度与分类模型评估结合在一起的方法。

考虑下图4-27中的二又决策树。 如果罚项等于0.5,左边的决策树的悲观误差估计为： 右边的决策树的悲观误差估计为：

这样,左边的决策树比右边的决策树具有更好的悲观误差估计。对二叉树来说,0.5的罚项意味着只要至少能够改善一个训练记录的分类,结点就应当扩展,因为扩展一个结点等价于总误差增加0.5,代价比犯一个训练错误小。

如果对于所有的结点t,Ω(t)=1,左边的决策树的悲观误差估计为e(Tl)=11/24=0.458,右边的决策树的悲观误差估计为e(Tr)=10/24=0.417。因此,右边的决策树比左边的决策树具有更好的悲观错误率。这样,除非能够减少一个以上训练记录的误分类,否则结点不应当扩展。

最小描述长度原则 另一种结合模型复杂度的方法是基于称作最小描述长度( minimum description length,MDL)原则的信息论方法。为了解释说明该原则,考虑图4=28中的例子。在该例中,A和B都是已知属性x值的给定记录集。另外,A知道每个记录的确切类标号,而B却不知道这些信息。B可以通过要求A顺序传送类标号而获得每个记录的分类。一条消息需要θ(n)比特的信息,其中n是记录总数。

图4-28最小描述长度(MDL)原则

另一种可能是,A决定建立一个分类模型,概括x和y之间的关系。在传送给B前,模型用压缩形式编码。如果模型的准确率是100%,那么传输的代价就等于模型编码的代价。否则,A还必须传输哪些记录被模型错误分类信息。传输的总代价是:

其中,等式右边的第一项是模型编码的开销,而第二项是误分类记录编码的开销。

根据MDL原则,我们寻找最小化开销函数的模型。本章习题9给出了一个如何计算决策树总描述长度的例子。

3.估计统计上界

泛化误差也可以用训练误差的统计修正来估计。因为泛化误差倾向于比训练误差大,所以统计修正通常是计算训练误差的上界,考虑到达决策树一个特定叶结点的训练记录数。例如,决策树算法C4.5中,假定每个叶结点上的错误服从二项分布。为了计算泛化误差,我们需要确定训练误差的上限,在下面的例子中解释说明。

例4.3考虑图4-27所示的二又决策树的最左分支,注意,TR中的最左叶结点被扩展为TL中的两个子女结点。在划分前,该结点的错误率是2/7=0.286。用正态分布近似二项分布,可以推导出错误率e的上界是:

(4-10)

4.使用确认集

在该方法中,不是用训练集估计泛化误差,而是把原始的训练数据集分为两个较小的子集,个子集用于训练,而另一个称作确认集,用于估计泛化误差。典型的做法是,保留23的训练集来建立模型,剩余的13用作误差估计。

该方法常常用于通过参数控制获得具有不同复杂度模型的分类技术。通过调整学习算法中的参数(如决策树中剪枝的程度),直到学习算法产生的模型在确认集上达到最低的错误率,可以估计最佳模型的复杂度。虽然该方法为评估模型在未知样本上的性能提供了较好办法,但用于训练的记录减少了。

处理决策树归纳中的过分拟合

先剪(提前终止规则)在这种方法中,树增长算法在产生完全拟合整个训练数据集的完全增长的决策树之前就停止决策树的生长。为了做到这一点,需要采用更具限制性的结束条件,例如,当观察到的不纯性度量的增益(或估计的泛化误差的改进)低于某个确定的阈值时就停止扩展叶结点。这种方法的优点在于避免产生过分拟合训练数据的过于复杂的子树,然而,很难为提前终止选取正确的國值。阈值太高将导致拟合不足的模型,而阅值太低就不能充分地解决过分拟合的问题。此外,即便使用已有的属性测试条件得不到显著的增益,接下来的划分也可能产生较好的子树。

后剪枝在该方法中,初始决策树按照最大规模生长,然后进行剪枝的步骤,按照自底向上的方式修剪完全增长的决策树。修剪有两种做法:(1)用新的叶结点替换子树,该叶结点的类标号由子树下记录中的多数类确定;或者(2)用子树中最常使用的分支代替子树。当模型不能再改进时终止剪枝步骤。与先剪枝相比,后剪枝技术倾向于产生更好的结果,因为不像先剪枝,后剪枝是根据完全增长的决策树做出的剪枝决策,先剪枝则可能过早终止决策树的生长。然而,对于后剪枝,当子树被剪掉后,生长完全决策树的额外的计算就被浪费了。

修剪有两种做法：

（1）用新的叶子节点替换子树，该叶结点的类标号由子树下记录中的多数类决定。子树替换

（2）用子树中最常使用的分支代替子树。当模型不能再改进时终止剪枝步骤。子树提升

评估分类器的性能

1、训练集和测试集方法

2、交叉验证

每个记录用于训练的次数相同，并且恰好检验一次。

3、自助法bootstrap

训练记录采用有放回抽样