DATA-MINING(CH10)-第10章--模型选择与模型评估-《数据挖掘与知识发现》(第2版).ppt

《DATA-MINING(CH10)-第10章--模型选择与模型评估-《数据挖掘与知识发现》(第2版).ppt》由会员分享，可在线阅读，更多相关《DATA-MINING(CH10)-第10章--模型选择与模型评估-《数据挖掘与知识发现》(第2版).ppt（44页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第1010章章 模型选择与模型选择与 模型评估模型评估 数据挖掘与知识发现(第2版)1数据挖掘与知识发现(第2版)李雄飞等2003,2010模型选择与模型评估模型选择与模型评估 生成若干数据模型后，需要依据模型对数据的解释能力或生成若干数据模型后，需要依据模型对数据的解释能力或生成若干数据模型后，需要依据模型对数据的解释能力或生成若干数据模型后，需要依据模型对数据的解释能力或预测能力，确定一个最优的模型。本章介绍模型选择和模型评预测能力，确定一个最优的模型。本章介绍模型选择和模型评预测能力，确定一个最优的模型。本章介绍模型选择和模型评预测能力，确定一个最优的模型。本章介绍模型选择和模型评估方

2、法。主要讨论启发式方法，数据重用技术，以及模型选择估方法。主要讨论启发式方法，数据重用技术，以及模型选择估方法。主要讨论启发式方法，数据重用技术，以及模型选择估方法。主要讨论启发式方法，数据重用技术，以及模型选择和验证的解析方法，具体包括：和验证的解析方法，具体包括：和验证的解析方法，具体包括：和验证的解析方法，具体包括：模型的过拟合模型的过拟合模型的过拟合模型的过拟合 没有天生优越的分类器没有天生优越的分类器没有天生优越的分类器没有天生优越的分类器 模型、模型选择和模型评估模型、模型选择和模型评估模型、模型选择和模型评估模型、模型选择和模型评估 自助法自助法自助法自助法 OccamOccam

3、剃刀剃刀剃刀剃刀 最小描述长度准则最小描述长度准则最小描述长度准则最小描述长度准则 信息准则信息准则信息准则信息准则 比较分类器的方法比较分类器的方法比较分类器的方法比较分类器的方法 聚类评估聚类评估聚类评估聚类评估2数据挖掘与知识发现(第2版)李雄飞等2003,2010模型的过拟合模型的过拟合 分类模型的误差有两类：分类模型的误差有两类：分类模型的误差有两类：分类模型的误差有两类：训练误差（训练误差（训练误差（训练误差（training errortraining error）：也称为再代入误差（）：也称为再代入误差（）：也称为再代入误差（）：也称为再代入误差（resubstitution

4、errorresubstitution error），），），），是训练样本上的误分类比例。是训练样本上的误分类比例。是训练样本上的误分类比例。是训练样本上的误分类比例。泛化误差（泛化误差（泛化误差（泛化误差（generalization errorgeneralization error）：是模型在未知样本上的期望误差。）：是模型在未知样本上的期望误差。）：是模型在未知样本上的期望误差。）：是模型在未知样本上的期望误差。一个好的分类模型应该同时具有低训练误差和低泛化误差。一个好的分类模型应该同时具有低训练误差和低泛化误差。一个好的分类模型应该同时具有低训练误差和低泛化误差。一个好的分类模型应

5、该同时具有低训练误差和低泛化误差。如果分类模型如果分类模型如果分类模型如果分类模型A A拟合训练数据较好，但与另一个拟合训练数据相对较差的拟合训练数据较好，但与另一个拟合训练数据相对较差的拟合训练数据较好，但与另一个拟合训练数据相对较差的拟合训练数据较好，但与另一个拟合训练数据相对较差的分类模型分类模型分类模型分类模型B B相比，模型相比，模型相比，模型相比，模型A A具有更高的泛化误差，则称模型具有更高的泛化误差，则称模型具有更高的泛化误差，则称模型具有更高的泛化误差，则称模型A A过拟合。过拟合。过拟合。过拟合。例，以二维数据为例解释过拟合。例，以二维数据为例解释过拟合。例，以二维数据为例

6、解释过拟合。例，以二维数据为例解释过拟合。在图在图在图在图10.110.1二维数据集合中，数据点属于两类：二维数据集合中，数据点属于两类：二维数据集合中，数据点属于两类：二维数据集合中，数据点属于两类：标记为标记为标记为标记为“o”“o”的数据由三个独立的正态分布产生，的数据由三个独立的正态分布产生，的数据由三个独立的正态分布产生，的数据由三个独立的正态分布产生，12001200个。个。个。个。标记为标记为标记为标记为“+”“+”的数据由均匀分布产生。的数据由均匀分布产生。的数据由均匀分布产生。的数据由均匀分布产生。18001800个。个。个。个。随机选取随机选取随机选取随机选取30%30%用

7、于训练决策树，其余用于训练决策树，其余用于训练决策树，其余用于训练决策树，其余70%70%用于测试。为说明过拟合现用于测试。为说明过拟合现用于测试。为说明过拟合现用于测试。为说明过拟合现象，对完全生长的决策树进行不同程度的剪枝。图象，对完全生长的决策树进行不同程度的剪枝。图象，对完全生长的决策树进行不同程度的剪枝。图象，对完全生长的决策树进行不同程度的剪枝。图10.210.2显示了不同节点数显示了不同节点数显示了不同节点数显示了不同节点数的决策树的训练误差和测试误差。的决策树的训练误差和测试误差。的决策树的训练误差和测试误差。的决策树的训练误差和测试误差。3数据挖掘与知识发现(第2版)李雄飞等

8、2003,2010模型的过拟合模型的过拟合 模型拟合不足模型拟合不足模型拟合不足模型拟合不足(model underfitting):(model underfitting):训练误差和测试误差都较大。训练误差和测试误差都较大。训练误差和测试误差都较大。训练误差和测试误差都较大。决策树生长不充分决策树生长不充分 模型过拟合模型过拟合模型过拟合模型过拟合(model overfitting):(model overfitting):训练误差继续降低，测试误差增大。训练误差继续降低，测试误差增大。训练误差继续降低，测试误差增大。训练误差继续降低，测试误差增大。决策树的规模过于复杂决策树的规模过于复

9、杂4数据挖掘与知识发现(第2版)李雄飞等2003,2010李雄飞等2003,2010没有天生优越的分类器没有天生优越的分类器 考虑两类问题：考虑两类问题：考虑两类问题：考虑两类问题：设训练集设训练集设训练集设训练集D D由模式由模式由模式由模式x xi i以及与之相应的类别标签以及与之相应的类别标签以及与之相应的类别标签以及与之相应的类别标签y yi i=，i i=1=1，n n，y yi i由待学习的未知目标函数由待学习的未知目标函数由待学习的未知目标函数由待学习的未知目标函数F F(x x)给出，即给出，即给出，即给出，即y yi i =F F(x xi i)。多数情况下，多数情况下，多数

10、情况下，多数情况下，F F(x x)都含有随机成分，相同的输入被分到不同的类别中，都含有随机成分，相同的输入被分到不同的类别中，都含有随机成分，相同的输入被分到不同的类别中，都含有随机成分，相同的输入被分到不同的类别中，导致非零贝叶斯错误率。导致非零贝叶斯错误率。导致非零贝叶斯错误率。导致非零贝叶斯错误率。令令令令H H表示假设集或待学习的可能参数集合。表示假设集或待学习的可能参数集合。表示假设集或待学习的可能参数集合。表示假设集或待学习的可能参数集合。h h(x x)H H是特定的假设，如，神经网络中的量化权值、泛函模型中的参是特定的假设，如，神经网络中的量化权值、泛函模型中的参是特定的假设

11、，如，神经网络中的量化权值、泛函模型中的参是特定的假设，如，神经网络中的量化权值、泛函模型中的参数数数数 或者树中的决策集合等等。或者树中的决策集合等等。或者树中的决策集合等等。或者树中的决策集合等等。设设设设P P(h h)表示算法训练后产生假设表示算法训练后产生假设表示算法训练后产生假设表示算法训练后产生假设h h的先验概率。的先验概率。的先验概率。的先验概率。P P(h h D D)表示在数据集表示在数据集表示在数据集表示在数据集D D上训练后产生假设上训练后产生假设上训练后产生假设上训练后产生假设h h的概率。的概率。的概率。的概率。对于确定性学习算法，对于确定性学习算法，P P(h

12、h D D)在单一假设在单一假设h h外，处处为零。外，处处为零。最近邻和决策树最近邻和决策树 对于随机算法，对于随机算法，P P(h h D D)可能是一个分布。可能是一个分布。神经网络神经网络令令令令E E表示表示表示表示0-10-1损失函数或其他损失函数的误差。损失函数或其他损失函数的误差。损失函数或其他损失函数的误差。损失函数或其他损失函数的误差。6数据挖掘与知识发现(第2版)李雄飞等2003,2010没有天生优越的分类器没有天生优越的分类器 评判学习算法的泛化性能：关于所有可能目标求和的误差期望值。评判学习算法的泛化性能：关于所有可能目标求和的误差期望值。评判学习算法的泛化性能：关于

13、所有可能目标求和的误差期望值。评判学习算法的泛化性能：关于所有可能目标求和的误差期望值。显然，固定训练集显然，固定训练集显然，固定训练集显然，固定训练集D D上期望误差率，与以输入的概率上期望误差率，与以输入的概率上期望误差率，与以输入的概率上期望误差率，与以输入的概率P P(x x)为权、学习算法为权、学习算法为权、学习算法为权、学习算法P P(h h D D)与真实后验与真实后验与真实后验与真实后验P P(F F D D)“)“匹配匹配匹配匹配”的情况的加权和有关。的情况的加权和有关。的情况的加权和有关。的情况的加权和有关。如果没有关于如果没有关于如果没有关于如果没有关于P P(F F D

14、 D)的先验知识，不能检验任何特定的学习算法的先验知识，不能检验任何特定的学习算法的先验知识，不能检验任何特定的学习算法的先验知识，不能检验任何特定的学习算法P P(h h D D)，包括其泛化性能。，包括其泛化性能。，包括其泛化性能。，包括其泛化性能。当真实函数是当真实函数是当真实函数是当真实函数是F F(x x)，第，第，第，第k k个候选学习算法的概率是个候选学习算法的概率是个候选学习算法的概率是个候选学习算法的概率是P Pk k(h h(x x)D D)时，非训练时，非训练时，非训练时，非训练集的期望误差率是：集的期望误差率是：集的期望误差率是：集的期望误差率是：7数据挖掘与知识发现(

15、第2版)李雄飞等2003,2010没有天生优越的分类器没有天生优越的分类器 定理定理定理定理10.110.1：（没有免费的午餐，：（没有免费的午餐，：（没有免费的午餐，：（没有免费的午餐，No free lunchNo free lunch，NFLNFL）任给两个学习算法）任给两个学习算法）任给两个学习算法）任给两个学习算法P P1 1(h h D D)和和和和P P2 2(h h D D)，下列命题正确，且与样本分布，下列命题正确，且与样本分布，下列命题正确，且与样本分布，下列命题正确，且与样本分布P P(x x)及训练点个数及训练点个数及训练点个数及训练点个数n n无无无无关：关：关：关：

16、(1)(1)对所有目标函数对所有目标函数对所有目标函数对所有目标函数F F求平均，有求平均，有求平均，有求平均，有 1 1 E E F F,n n-2 2 E E F F,n n=0=0；(2)(2)任意固定的训练集任意固定的训练集任意固定的训练集任意固定的训练集D D，对所有，对所有，对所有，对所有F F求平均，有求平均，有求平均，有求平均，有 1 1 E E F F,D D-2 2 E E F F,D D=0=0；(3)(3)对所有先验对所有先验对所有先验对所有先验P P(F F)求平均，有求平均，有求平均，有求平均，有 1 1 E E n n-2 2 E E n n=0=0；(4)(4)

17、任意固定的训练集任意固定的训练集任意固定的训练集任意固定的训练集D D，对所有先验，对所有先验，对所有先验，对所有先验P P(F F)求平均，有求平均，有求平均，有求平均，有 1 1 E E D D-2 2 E E D D=0.=0.NFLNFL定理表明：定理表明：定理表明：定理表明：使用哪种算法完成分类任务，取决于问题本质特征，而不是数据挖掘者对哪使用哪种算法完成分类任务，取决于问题本质特征，而不是数据挖掘者对哪个算法更熟悉。个算法更熟悉。研究和试图说明某种算法具有天生的优越性是没有意义的。研究和试图说明某种算法具有天生的优越性是没有意义的。当面对一个新的分类问题时：当面对一个新的分类问题时

18、：当面对一个新的分类问题时：当面对一个新的分类问题时：(1)(1)应该关注事务的本质应该关注事务的本质应该关注事务的本质应该关注事务的本质 先验信息、数据分布、训练样本数量、代价或奖励函数等。先验信息、数据分布、训练样本数量、代价或奖励函数等。(2)(2)根据以上关于问题的根据以上关于问题的根据以上关于问题的根据以上关于问题的“信息信息信息信息”，选择适当的分类算法。，选择适当的分类算法。，选择适当的分类算法。，选择适当的分类算法。8数据挖掘与知识发现(第2版)李雄飞等2003,2010李雄飞等2003,2010没有天生优越的分类器没有天生优越的分类器 假定没有关于假定没有关于假定没有关于假定

19、没有关于F F(x x)的先验信息。所有目标函数平等。要全面地比较算法，的先验信息。所有目标函数平等。要全面地比较算法，的先验信息。所有目标函数平等。要全面地比较算法，的先验信息。所有目标函数平等。要全面地比较算法，必须对所有与训练数据一致的目标函数求平均。必须对所有与训练数据一致的目标函数求平均。必须对所有与训练数据一致的目标函数求平均。必须对所有与训练数据一致的目标函数求平均。与训练数据集与训练数据集与训练数据集与训练数据集D D中三个模式一致的不同目标函数一共有中三个模式一致的不同目标函数一共有中三个模式一致的不同目标函数一共有中三个模式一致的不同目标函数一共有2 25 5个，确实存在另

20、个，确实存在另个，确实存在另个，确实存在另一个目标函数一个目标函数一个目标函数一个目标函数GG，其关于非训练数据的输出是表中，其关于非训练数据的输出是表中，其关于非训练数据的输出是表中，其关于非训练数据的输出是表中F F(x x)的取反，也即的取反，也即的取反，也即的取反，也即GG(x x)=(1,-1,1,1,-1,1,-1,-1),)=(1,-1,1,1,-1,1,-1,-1),而而而而 1 1 E E GG,D D=0.6=0.6和和和和 2 2 E E GG,D D=0.4=0.4，也即也即也即也即F F和和和和GG使得算法使得算法使得算法使得算法1 1和算法和算法和算法和算法2 2

21、的性能相反，从而对定理的性能相反，从而对定理的性能相反，从而对定理的性能相反，从而对定理10.110.1的的的的(2)(2)中公式的中公式的中公式的中公式的贡献相抵消。贡献相抵消。贡献相抵消。贡献相抵消。任何一个二值分类学习算法任何一个二值分类学习算法任何一个二值分类学习算法任何一个二值分类学习算法 如果不在某些问题上付出相等的负的性能代价，则不可能在所关心的问题如果不在某些问题上付出相等的负的性能代价，则不可能在所关心的问题如果不在某些问题上付出相等的负的性能代价，则不可能在所关心的问题如果不在某些问题上付出相等的负的性能代价，则不可能在所关心的问题上得到等量的正的性能。上得到等量的正的性能

22、。上得到等量的正的性能。上得到等量的正的性能。如果没有限定一定要使用某种特定的算法解决问题，那么，我们所能做的如果没有限定一定要使用某种特定的算法解决问题，那么，我们所能做的如果没有限定一定要使用某种特定的算法解决问题，那么，我们所能做的如果没有限定一定要使用某种特定的算法解决问题，那么，我们所能做的就是在期望遇到的问题和不期望遇到的问题之间做一些性能折中。就是在期望遇到的问题和不期望遇到的问题之间做一些性能折中。就是在期望遇到的问题和不期望遇到的问题之间做一些性能折中。就是在期望遇到的问题和不期望遇到的问题之间做一些性能折中。学习算法必须做一些与问题相关的学习算法必须做一些与问题相关的学习算

23、法必须做一些与问题相关的学习算法必须做一些与问题相关的“假设假设假设假设”，也就是偏置（，也就是偏置（，也就是偏置（，也就是偏置（biasbias）。）。）。）。即使是非常流行而且理论坚实的算法，也会在学习算法与问题后验不即使是非常流行而且理论坚实的算法，也会在学习算法与问题后验不即使是非常流行而且理论坚实的算法，也会在学习算法与问题后验不即使是非常流行而且理论坚实的算法，也会在学习算法与问题后验不“匹匹匹匹配配配配”的情况下表现不佳。的情况下表现不佳。的情况下表现不佳。的情况下表现不佳。仅仅熟悉有限的几种分类算法，并不能解决所有分类问题。仅仅熟悉有限的几种分类算法，并不能解决所有分类问题。仅

24、仅熟悉有限的几种分类算法，并不能解决所有分类问题。仅仅熟悉有限的几种分类算法，并不能解决所有分类问题。10数据挖掘与知识发现(第2版)李雄飞等2003,2010模型、模型选择和模型评估模型、模型选择和模型评估 模型可以定义为对输入输出之间联系的一种描述。这种描述可以用不同方模型可以定义为对输入输出之间联系的一种描述。这种描述可以用不同方模型可以定义为对输入输出之间联系的一种描述。这种描述可以用不同方模型可以定义为对输入输出之间联系的一种描述。这种描述可以用不同方式形式化。式形式化。式形式化。式形式化。例如分类器、神经网络、决策树、产生式规则、数学方程等。例如分类器、神经网络、决策树、产生式规则

25、、数学方程等。模型、分类器和估计子基本上含义相同。模型、分类器和估计子基本上含义相同。模型、分类器和估计子基本上含义相同。模型、分类器和估计子基本上含义相同。分类器是用于分类目的的数据模型：给定新的输入，分类器依据训练结果分类器是用于分类目的的数据模型：给定新的输入，分类器依据训练结果分类器是用于分类目的的数据模型：给定新的输入，分类器依据训练结果分类器是用于分类目的的数据模型：给定新的输入，分类器依据训练结果将其划分到某一个类中。将其划分到某一个类中。将其划分到某一个类中。将其划分到某一个类中。估计子来自于统计学，定义为样本值的函数，是计算参数的一种方法。估计子来自于统计学，定义为样本值的函

26、数，是计算参数的一种方法。估计子来自于统计学，定义为样本值的函数，是计算参数的一种方法。估计子来自于统计学，定义为样本值的函数，是计算参数的一种方法。估计模型时所必需的独立的信息项的数目称为模型的自由度。估计模型时所必需的独立的信息项的数目称为模型的自由度。估计模型时所必需的独立的信息项的数目称为模型的自由度。估计模型时所必需的独立的信息项的数目称为模型的自由度。选择简洁模型，在若干表现良好的模型中，选择参数数目少的模型。选择简洁模型，在若干表现良好的模型中，选择参数数目少的模型。选择简洁模型，在若干表现良好的模型中，选择参数数目少的模型。选择简洁模型，在若干表现良好的模型中，选择参数数目少的

27、模型。模型误差指真实值和模型输出值之间的绝对误差或平方误差。模型误差指真实值和模型输出值之间的绝对误差或平方误差。模型误差指真实值和模型输出值之间的绝对误差或平方误差。模型误差指真实值和模型输出值之间的绝对误差或平方误差。当由数据生成一个模型时，称之为模型拟合数据。当由数据生成一个模型时，称之为模型拟合数据。当由数据生成一个模型时，称之为模型拟合数据。当由数据生成一个模型时，称之为模型拟合数据。不仅需要检验模型的拟合优度（拟合误差），而且需要检验模型的预测优不仅需要检验模型的拟合优度（拟合误差），而且需要检验模型的预测优不仅需要检验模型的拟合优度（拟合误差），而且需要检验模型的预测优不仅需要检

28、验模型的拟合优度（拟合误差），而且需要检验模型的预测优度（预测误差）。度（预测误差）。度（预测误差）。度（预测误差）。在生成的若干模型中择优的过程称为模型选择在生成的若干模型中择优的过程称为模型选择在生成的若干模型中择优的过程称为模型选择在生成的若干模型中择优的过程称为模型选择(model selection)(model selection)。11数据挖掘与知识发现(第2版)李雄飞等2003,2010李雄飞等2003,2010模型、模型选择和模型评估模型、模型选择和模型评估 偏倚与方差偏倚与方差偏倚与方差偏倚与方差 偏倚度量模型与问题偏倚度量模型与问题“匹配匹配”的准确度，高偏倚意味着更差的

29、匹配；的准确度，高偏倚意味着更差的匹配；方差度量方差度量“匹配匹配”的精确度，高方差意味着更弱匹配。的精确度，高方差意味着更弱匹配。对于给定的均方误差，偏倚和方差之间存在对于给定的均方误差，偏倚和方差之间存在对于给定的均方误差，偏倚和方差之间存在对于给定的均方误差，偏倚和方差之间存在“守恒律守恒律守恒律守恒律”的形式。假如有先的形式。假如有先的形式。假如有先的形式。假如有先验信息，可以创建出具有不同均方误差的分类器。验信息，可以创建出具有不同均方误差的分类器。验信息，可以创建出具有不同均方误差的分类器。验信息，可以创建出具有不同均方误差的分类器。评估模型的拟合优度和预测优度，必须首先计算误差。

30、评估模型的拟合优度和预测优度，必须首先计算误差。评估模型的拟合优度和预测优度，必须首先计算误差。评估模型的拟合优度和预测优度，必须首先计算误差。误差分为两部分：偏倚和方差。误差分为两部分：偏倚和方差。误差分为两部分：偏倚和方差。误差分为两部分：偏倚和方差。(1)(1)偏倚偏倚偏倚偏倚(BiasBias)是通过增加样本容量也无法降低的误差。偏倚也称系统误差，是通过增加样本容量也无法降低的误差。偏倚也称系统误差，是通过增加样本容量也无法降低的误差。偏倚也称系统误差，是通过增加样本容量也无法降低的误差。偏倚也称系统误差，包括：包括：包括：包括：测量误差：无法消除的试验误差测量误差：无法消除的试验误差

31、 样本误差：样本可能没有正确地产生于分布，从而没有正确地描述数据。样本误差：样本可能没有正确地产生于分布，从而没有正确地描述数据。通过计算某些参数的估计值的数学期望和真实值之差得出偏倚通过计算某些参数的估计值的数学期望和真实值之差得出偏倚通过计算某些参数的估计值的数学期望和真实值之差得出偏倚通过计算某些参数的估计值的数学期望和真实值之差得出偏倚：13数据挖掘与知识发现(第2版)李雄飞等2003,2010李雄飞等2003,2010模型、模型选择和模型评估模型、模型选择和模型评估 拟合优度和预测优度，也即训练误差和测试误差。拟合优度和预测优度，也即训练误差和测试误差。拟合优度和预测优度，也即训练误

32、差和测试误差。拟合优度和预测优度，也即训练误差和测试误差。过度训练通常意味着数据过拟合。过度训练通常意味着数据过拟合。过度训练通常意味着数据过拟合。过度训练通常意味着数据过拟合。当将过度训练的神经网络应用于测试数据时，其预测当将过度训练的神经网络应用于测试数据时，其预测当将过度训练的神经网络应用于测试数据时，其预测当将过度训练的神经网络应用于测试数据时，其预测/泛化误差通常较大。泛化误差通常较大。泛化误差通常较大。泛化误差通常较大。15数据挖掘与知识发现(第2版)李雄飞等2003,2010简单划分和交叉验证简单划分和交叉验证 简单划分：简单划分：简单划分：简单划分：为评估模型，将可用数据简单地

33、划分为两部分：训练数据和测试数据，为评估模型，将可用数据简单地划分为两部分：训练数据和测试数据，为评估模型，将可用数据简单地划分为两部分：训练数据和测试数据，为评估模型，将可用数据简单地划分为两部分：训练数据和测试数据，训练数据用于拟合模型，测试数据用于评估模型的预测优度。训练数据用于拟合模型，测试数据用于评估模型的预测优度。训练数据用于拟合模型，测试数据用于评估模型的预测优度。训练数据用于拟合模型，测试数据用于评估模型的预测优度。随机地通过一个经验公式，抽取约随机地通过一个经验公式，抽取约随机地通过一个经验公式，抽取约随机地通过一个经验公式，抽取约1/21/2或或或或2/32/3数据用于训练

34、。数据用于训练。数据用于训练。数据用于训练。特点：高偏倚、低方差。特点：高偏倚、低方差。特点：高偏倚、低方差。特点：高偏倚、低方差。交叉验证：交叉验证：交叉验证：交叉验证：令令令令n n表示训练数据集中数据点的数目，将全部数据分为表示训练数据集中数据点的数目，将全部数据分为表示训练数据集中数据点的数目，将全部数据分为表示训练数据集中数据点的数目，将全部数据分为k k个等规模的子个等规模的子个等规模的子个等规模的子集，使用集，使用集，使用集，使用k k-1-1个部分进行训练，余下的那一部分用于测试，并计算预测误差个部分进行训练，余下的那一部分用于测试，并计算预测误差个部分进行训练，余下的那一部分

35、用于测试，并计算预测误差个部分进行训练，余下的那一部分用于测试，并计算预测误差(预测优度预测优度预测优度预测优度)。重复这一过程。重复这一过程。重复这一过程。重复这一过程k k次，得到次，得到次，得到次，得到k k次结果的平均值。次结果的平均值。次结果的平均值。次结果的平均值。常用的是常用的是常用的是常用的是1010折交叉验证，数据集被分为折交叉验证，数据集被分为折交叉验证，数据集被分为折交叉验证，数据集被分为1010个子集，最终预测误差为个子集，最终预测误差为个子集，最终预测误差为个子集，最终预测误差为1010次预测误差的平均值。次预测误差的平均值。次预测误差的平均值。次预测误差的平均值。特

36、点特点特点特点:低偏倚和高方差。低偏倚和高方差。低偏倚和高方差。低偏倚和高方差。简单划分用于数据集规模较大的情况。简单划分用于数据集规模较大的情况。简单划分用于数据集规模较大的情况。简单划分用于数据集规模较大的情况。交叉验证用于数据集较小且难于处理的情况交叉验证用于数据集较小且难于处理的情况交叉验证用于数据集较小且难于处理的情况交叉验证用于数据集较小且难于处理的情况 。16数据挖掘与知识发现(第2版)李雄飞等2003,2010李雄飞等2003,2010Occam剃刀剃刀 在给定论域，观测现象的最简单解释（模型）是最可能正确的。在给定论域，观测现象的最简单解释（模型）是最可能正确的。在给定论域，

37、观测现象的最简单解释（模型）是最可能正确的。在给定论域，观测现象的最简单解释（模型）是最可能正确的。给定若干模型，应该选择更给定若干模型，应该选择更给定若干模型，应该选择更给定若干模型，应该选择更“紧凑紧凑紧凑紧凑”的模型。的模型。的模型。的模型。由更小数目规则构成由更小数目规则构成 规则的平均长度比其他模型中的规则平均长度更短规则的平均长度比其他模型中的规则平均长度更短 许多机器学习算法使用了许多机器学习算法使用了许多机器学习算法使用了许多机器学习算法使用了OccamOccam剃刀启发式方法。剃刀启发式方法。剃刀启发式方法。剃刀启发式方法。问题：问题：问题：问题：已经用其生成模型，但还要用其

38、进行模型选择。已经用其生成模型，但还要用其进行模型选择。在某些情况下，在某些情况下，OccamOccam剃刀可能是完全错误的。剃刀可能是完全错误的。无论是无论是无论是无论是“避免过拟合避免过拟合避免过拟合避免过拟合”技术，还是最小描述长度原理，都没有固有的优越技术，还是最小描述长度原理，都没有固有的优越技术，还是最小描述长度原理，都没有固有的优越技术，还是最小描述长度原理，都没有固有的优越性，这类技术对分类器的形式或参数施加一种性，这类技术对分类器的形式或参数施加一种性，这类技术对分类器的形式或参数施加一种性，这类技术对分类器的形式或参数施加一种“偏爱偏爱偏爱偏爱”或或或或“偏置偏置偏置偏置”

39、（biasbias）。）。）。）。这些技术仅在其恰好与问题这些技术仅在其恰好与问题这些技术仅在其恰好与问题这些技术仅在其恰好与问题“匹配匹配匹配匹配”时才是有益的。时才是有益的。时才是有益的。时才是有益的。决定因素是学习算法与问题的决定因素是学习算法与问题的决定因素是学习算法与问题的决定因素是学习算法与问题的“匹配匹配匹配匹配”，而不是，而不是，而不是，而不是“避免过拟合避免过拟合避免过拟合避免过拟合”本身。本身。本身。本身。18数据挖掘与知识发现(第2版)李雄飞等2003,2010最小描述长度准则最小描述长度准则 RissanenRissanen给出最小描述长度原理（给出最小描述长度原理（给

40、出最小描述长度原理（给出最小描述长度原理（Minimum Description Length Minimum Description Length PrinciplePrinciple，MDLMDL）。MDLMDL：如果系统能够用输入和与之相应的输出数据定义，则最差情形：如果系统能够用输入和与之相应的输出数据定义，则最差情形：如果系统能够用输入和与之相应的输出数据定义，则最差情形：如果系统能够用输入和与之相应的输出数据定义，则最差情形(最最最最长）下，可以使用全部数据描述这一系统（数据的最长长）下，可以使用全部数据描述这一系统（数据的最长长）下，可以使用全部数据描述这一系统（数据的最长长）下

41、，可以使用全部数据描述这一系统（数据的最长/最小的压缩模型最小的压缩模型最小的压缩模型最小的压缩模型)。MDLMDL原理表明，理论（模型原理表明，理论（模型原理表明，理论（模型原理表明，理论（模型/假设）的复杂度可以通过理论本身的编码位假设）的复杂度可以通过理论本身的编码位假设）的复杂度可以通过理论本身的编码位假设）的复杂度可以通过理论本身的编码位数与使用该理论表达数据的编码位数之和度量。数与使用该理论表达数据的编码位数之和度量。数与使用该理论表达数据的编码位数之和度量。数与使用该理论表达数据的编码位数之和度量。给定一组模型，选择最小化和：给定一组模型，选择最小化和：给定一组模型，选择最小化和

42、：给定一组模型，选择最小化和：L L(h h,D D)=)=L L(MM)+)+L L(D D|MM)的模型。即，的模型。即，的模型。即，的模型。即，其中其中其中其中L L(MM)为描述模型的长度（位数），为描述模型的长度（位数），为描述模型的长度（位数），为描述模型的长度（位数），L L(D D|MM)为使用模型为使用模型为使用模型为使用模型MM编码描述数据编码描述数据编码描述数据编码描述数据的长度。的长度。的长度。的长度。用贝叶斯的观点解释最小描述长度原理：用贝叶斯的观点解释最小描述长度原理：用贝叶斯的观点解释最小描述长度原理：用贝叶斯的观点解释最小描述长度原理：最优假设最优假设最优假设最

43、优假设h*h*是使得是使得是使得是使得后验概率最大的那个假设。后验概率最大的那个假设。后验概率最大的那个假设。后验概率最大的那个假设。19数据挖掘与知识发现(第2版)李雄飞等2003,2010最小描述长度准则最小描述长度准则 香农最优编码理论：香农最优编码理论：香农最优编码理论：香农最优编码理论：串串串串x x可以可以可以可以-log-log2 2P P(x x)为代价下界进行传输或表示。为代价下界进行传输或表示。为代价下界进行传输或表示。为代价下界进行传输或表示。关于过拟合问题：关于过拟合问题：关于过拟合问题：关于过拟合问题：具有较大具有较大L L(MM)值的复杂模型很容易构建，该模型具有较

44、小的值的复杂模型很容易构建，该模型具有较小的L L(D D|MM)值，值，过拟合数据。过拟合数据。具有较小具有较小L L(MM)值的简单模型也很容易构建，该模型具有较大的值的简单模型也很容易构建，该模型具有较大的L L(D D|MM)值，拟合数据不足。值，拟合数据不足。假定生成了两个解释假定生成了两个解释假定生成了两个解释假定生成了两个解释/拟合数据一样好的两个不同模型，拟合数据一样好的两个不同模型，拟合数据一样好的两个不同模型，拟合数据一样好的两个不同模型，MDLMDL原理提示应选择较简单的模型。原理提示应选择较简单的模型。原理提示应选择较简单的模型。原理提示应选择较简单的模型。相互联系：相

45、互联系：相互联系：相互联系：MDLMDL原理和贝叶斯方法之间的联系。原理和贝叶斯方法之间的联系。MDLMDL原理可以看成原理可以看成OccamOccam剃刀的形式化。剃刀的形式化。20数据挖掘与知识发现(第2版)李雄飞等2003,2010Akaike信息准则信息准则 AkaikeAkaike信息准则（信息准则（信息准则（信息准则（Akaike Information CriterionAkaike Information Criterion，AICAIC）和）和）和）和BayesianBayesian信信信信息准则（息准则（息准则（息准则（Bayesian Information Criter

46、ionBayesian Information Criterion，BICBIC）是两种统计学度量，用）是两种统计学度量，用）是两种统计学度量，用）是两种统计学度量，用于在使用不同参数个数的模型间进行模型选择，这些模型彼此相关。于在使用不同参数个数的模型间进行模型选择，这些模型彼此相关。于在使用不同参数个数的模型间进行模型选择，这些模型彼此相关。于在使用不同参数个数的模型间进行模型选择，这些模型彼此相关。要估计预测误差要估计预测误差要估计预测误差要估计预测误差E E，训练误差，训练误差，训练误差，训练误差TrETrE易于计算，但是，由于测试向量不一定与易于计算，但是，由于测试向量不一定与易于计

47、算，但是，由于测试向量不一定与易于计算，但是，由于测试向量不一定与训练向量一致，训练向量一致，训练向量一致，训练向量一致，TrETrE通常过于乐观，作为修正，需要估计乐观的误差通常过于乐观，作为修正，需要估计乐观的误差通常过于乐观，作为修正，需要估计乐观的误差通常过于乐观，作为修正，需要估计乐观的误差EopEop，并计算样本内误差（并计算样本内误差（并计算样本内误差（并计算样本内误差（in-sample errorin-sample error）如下：）如下：）如下：）如下：E E=TrETrE+EopEop AICAIC定义如下：定义如下：定义如下：定义如下：(10.14)(10.14)其中

48、其中其中其中logLlogL是极大对数似然，即是极大对数似然，即是极大对数似然，即是极大对数似然，即 (10.15)(10.15)P P(Y)(Y)是包含真实密度的密度族，是包含真实密度的密度族，是包含真实密度的密度族，是包含真实密度的密度族，是是是是 的极大似然估计，的极大似然估计，的极大似然估计，的极大似然估计，d d是模型是模型是模型是模型参数个数。参数个数。参数个数。参数个数。21数据挖掘与知识发现(第2版)李雄飞等2003,2010Akaike信息准则信息准则 如果生成了一族可以调整参数如果生成了一族可以调整参数如果生成了一族可以调整参数如果生成了一族可以调整参数 的模型，则的模型，

49、则的模型，则的模型，则AICAIC重写为重写为重写为重写为 (10.16)(10.16)方差方差方差方差varvar2 2定义为定义为定义为定义为 (10.17)(10.17)AICAIC()()是测试误差曲线的估计，选择最小化该函数的模型为是测试误差曲线的估计，选择最小化该函数的模型为是测试误差曲线的估计，选择最小化该函数的模型为是测试误差曲线的估计，选择最小化该函数的模型为最佳模型。最佳模型。最佳模型。最佳模型。22数据挖掘与知识发现(第2版)李雄飞等2003,2010李雄飞等2003,2010比较分类器的方法比较分类器的方法 考虑一对分类模型考虑一对分类模型考虑一对分类模型考虑一对分类模

50、型MMA A和和和和MMB B。假设。假设。假设。假设MMA A在包含在包含在包含在包含3030个记录的检验集上的准确率个记录的检验集上的准确率个记录的检验集上的准确率个记录的检验集上的准确率达到达到达到达到85%85%，而，而，而，而MMB B在包含在包含在包含在包含50005000个记录的不同检验集上达到个记录的不同检验集上达到个记录的不同检验集上达到个记录的不同检验集上达到75%75%的准确率。根的准确率。根的准确率。根的准确率。根据这些信息，是否可以断定据这些信息，是否可以断定据这些信息，是否可以断定据这些信息，是否可以断定MMA A比比比比MMB B更好呢？更好呢？更好呢？更好呢？(