数据挖掘导论__第4章_分类：基本概念、决策树与模型评估课件.ppt

模型过分拟合和拟合不足 当决策树很小时，训练和检验误差都很大，这种情况称为模型拟合不足。出现拟合不足的原因是模型尚未学习到数据的真实结构。 随着决策树中结点数的增加，模型的训练误差和检验误差都会随之下降。 当树的规模变得太大时，即使训练误差还在继续降低，但是检验误差开始增大，导致模型过分拟合 模型模型过分拟合和拟合不足 过分拟合 导致过分拟合的原因 导致过分拟合的原因 噪声导致的过分拟合 例子：哺乳动物的分类问题 十个训练记录中有两个被错误标记：蝙蝠和鲸 如果完全拟合训练数据，决策树1的训练误差为0，但它在检验数据上的误差达30%.人和海豚，针鼹误分为非哺乳动物 相反，一个更简单的决策树2，具有较低的检验误差（10%），尽管它的训练误差较高，为20% 决策树1过分拟合了训练数据。因为属性测试条件4条腿具有欺骗性，它拟合了误标记的训练纪录，导致了对检验集中记录的误分类 噪声导致的过分拟合（例子） 噪声导致决策边界的改变 缺乏代表性样本导致的过分拟合 根据少量训练记录做出分类决策的模型也容易受过分拟合的影响。 由于训练数据缺乏具有代表性的样本，在没有多少训练记录的情况下，学习算法仍然细化模型就会产生过分拟合。 例子：五个训练记录，所有的记录都是正确标记的，对应的决策树尽管训练误差为0，但检验误差高达30% 人、大象和海豚被误分类，因为决策树把恒温但不冬眠的动物分为非哺乳动物。决策树做出这样的分类决策是因为只有一个训练记录（鹰）具有这些特征。 这个例子清楚的表明，当决策树的叶结点没有足够的代表性样本时，很可能做出错误的预测。 过分拟合与多重比较 模型的过分拟合可能出现在使用多重比较过程的算法中 多重比较的例子：考虑未来十个交易日股市是升还是降 一个人十次猜测至少正确预测八次的概率是：0.0547 假设从50个股票分析家中选择一个投资顾问，策略是选择在未来的十个交易日做出最多正确预测的分析家。 该策略的缺点是，即使所有的分析家都用随机猜测做出预测，至少有一个分析家做出八次正确预测的概率是：1-（1-0.0547）50=0.9399，这一结果相当高。 多重比较过程与模型过分拟合有什么关系？ 在决策树增长过程中，可以进行多种测试，以确定哪个属性能够最好的划分训练数据。 在这种情况下，算法实际上是使用多重比较过程来决定是否需要扩展决策树。 当候选属性多，训练记录数少时，这种影响就变得更加明显。 泛化误差估计 过分拟合的主要原因一直是个争辩的话题，但大家还是普遍同意模型的复杂度对模型的过分拟合有影响。 如何确定正确的模型复杂度？理想的复杂度是能产生最低泛化误差的模型的复杂度。 估计泛化误差的方法 使用再代入估计。用训练误差提供对泛化误差的乐观估计 结合模型复杂度 估计统计上界 使用确认集 结合模型复杂度 奥卡姆剃刀 （Occams Razor ）：给定两个具有相同泛化误差的模型，较简单的模型比复杂的模型更可取 因为复杂模型中的附加成分很大程度上是偶然的拟合。因此，分类模型评估应把模型复杂度考虑进去 方法：悲观误差估计、最小描述长度原则（MDL） 悲观误差评估 悲观误差估计公式： Q(ti)为每个结点ti的罚分，e(T)为训练样本集的错分样本数，Nt为训练样本总数，k为叶结点数。 例子1：如果罚分等于0.5，训练样本集中样本数为24个，我们构建了7个叶结点的决策树，训练样本集的错分样本数为4 根据公式我们得e’(T)=(4+7*0.5)/24=0.3125 例子2：如果罚分等于0.5，训练样本集中样本数为24个，我们构建了4个叶结点的决策树，训练样本集的错分样本数为6 根据公式我们得e’(T)=(6+4*0.5)/24=0.3333 当罚分等于1时，例1，2为0.458，0.417 0.5的罚分项表示只要至少能够改进一个训练记录的分类，结点就应当扩充，因为扩展一个结点等价于总误差增加0.5，代价比犯一个训练错误小 最小描述长度 (MDL) Cost(Model,Data) = Cost(Data|Model) + Cost(Model) Cost 是传输总代价. 最小化cost值. Cost(Data|Model) 是误分类记录编码的开销. Cost(Model) 是模型编码的开销 . 使用确认集 该方法中，不是用训练集估计泛化误差，而是把原始的训练数据集分为两个较小的子集，一个子集用于训练，而另一个称为确认集，用于估计泛化误差。 该方法为评估模型在未知样本上的性能提供了较好办法。 处理决策树中的过分拟合 先剪枝 (Early Stopping Rule) 树增长算法在产生完全拟合整个训练数据集的之前就停止决策树的生长 为了做到这一点，需要采用更具限制性的结束条件: 当结点的记录数少于一定阈值，则停止生长 当不纯