第17章数据挖掘模型评价.ppt
Copyright 2003-12, SPSS Taiwan Corp.,数据挖掘原理与SPSS Clementine应用宝典 元昌安 主编 邓 松 李文敬 刘海涛 编著 电子工业出版社,Copyright 2003-12, SPSS Taiwan Corp.,2,Copyright 2003-12, SPSS Taiwan Corp.,3,17.1基于损失函数的标准 17.1.1混淆矩阵 17.1.2准确率及误差的度量 17.1.3两个评价模型成本的可视化工具 17.1.4评估分类器的准确率 17.2基于统计检验的准则 17.2.1统计模型之间的距离 17.2.2统计模型的离差 17.3基于记分函数的标准 17.4贝叶斯标准,17.5计算标准 17.5.1交叉验证标准 17.5.2自展标准 17.5.3遗传算法 17.6小结,Copyright 2003-12, SPSS Taiwan Corp.,17.1基于损失函数的标准,17.1.1混淆矩阵 混淆矩阵（confusion matrix ）用来作为分类规则特征的表示，它包括了每一类的样本个数，包括正确的和错误的分类。 主对角线给出了每一类正确分类的样本的个数，非对角线上的元素则表示未被正确分类的样本个数。,Copyright 2003-12, SPSS Taiwan Corp.,对于 m类的分类问题，误差可能有m2-m。如果仅有2类（正样本和负样本，用T和F或1和0来象征性地代表），就只有两类误差。 期望为T，但分类为F：称为假负。 期望为F，但分类为T：称为假正。 此外 期望为T，但分类为T：称为真正。 期望为F，但分类为F：称为真负。,Copyright 2003-12, SPSS Taiwan Corp.,我们可以把它们汇总在表17-1正、负样本的混淆矩阵中。,表17-1 正、负样本的混淆矩阵,Copyright 2003-12, SPSS Taiwan Corp.,当分类数m为3时，对角线给出正确的预测。如表17-23个类的混淆矩阵所示。 在本例中，总共是150个检验样本。有6类误差（m2-m=32-3=6）, 在表中它们以粗体字表示。 可以看到，这个分类器对于属于B类的46中的38个样本给出了正确的分类；8个样本给出了错误的分类，其中2个分到了A类，6个分到了C类。,表 17-2 3个类的混淆矩阵,Copyright 2003-12, SPSS Taiwan Corp.,17.1.2 准确率及误差的度量 为了度量分类器的预测精度，如果明确或隐含地假设每个被错分的数据会产生相同的成本，我们引入误差率和准确率这两个参数作为它的一个性能度量来对其进行评估。 误差率R是误差数目E和检验集中的样本数S的比值： （17-1） 分类器的准确率A是检验集中正确分类数和检验集中样本数S的比值，它的计算是： （17-2）,Copyright 2003-12, SPSS Taiwan Corp.,到目前为止，我们所假设的是每个误差同等成本，如果对于不同的错误有不同的成本的话，即使一个模型有低的准确率，它也比一个有高准确率但是成本高的模型更好。 例如，在表17-23个类的混淆矩阵中如果假定每一个正确分类的成本为1000元，关于A类分错的成本是500元，关于B类分错的成本是1000元，关于C类分错的成本是2000元，则通过矩阵计算模型成本为（123×1000）（5×500）（12×1000）（10×2000）=88500元。,Copyright 2003-12, SPSS Taiwan Corp.,因此当不同类型的误差对应不同的权值时，我们要将每个误差乘以对应的权值因子cij 如果混淆矩阵中的误差元素为eij，那么总成本函数C（替代精度计算中的误差数）可以计算为： (17-3 ),Copyright 2003-12, SPSS Taiwan Corp.,要描述模型的质量，必须有更加复杂和全局性的度量。为此我们引入5个参数：敏感性（sensitivity），特异性（specificity），精度（precision），错误正例（false positives），错误负例（false negatives）。 敏感性（sensitivity）= （17-4） 特异性（specificity）= （17-5）,Copyright 2003-12, SPSS Taiwan Corp.,以上两个参数分别评估分类器识别正样本的情况和识别负样本的情况。 精度（precision）= (17-6) 错误正例（false positives）=1- （17-7） 错误负例（false negatives）=1- （17-8）,Copyright 2003-12, SPSS Taiwan Corp.,其中，t_pos是真正的样本个数， pos是正样本数，t_neg是真负的样本个数，neg是负样本的个数， f_pos是假正的样本个数。 最终准确率为： A= × + × （17-9）,Copyright 2003-12, SPSS Taiwan Corp.,例17-1 基于表17-1 正、负样本的混淆矩阵。事件(Event)这个术语代表二值响应变量的值Y，Event (1)表示成功，Event(0)表示失败。可以把一个检验数据集中的样本数据分为可能的4类，如表17-3事件（Event）的混淆矩阵:,表 17-3 事件（Event）的混淆矩阵,Copyright 2003-12, SPSS Taiwan Corp.,该模型的敏感性（sensitivity），特异性（specificity），精度（precision），错误正例（false positives），错误负例（false negatives）5个参数分别为： 敏感性（sensitivity）= 特异性（specificity）= 精度（precision）= 错误正例（false positives）= 错误负例（false negatives）=,Copyright 2003-12, SPSS Taiwan Corp.,介绍lift图和ROC曲线，这两个图都可以用来评价模型成本。它们都是关于二值响应变量的，而二值响应变量是评价方法发展最快的领域。 17.1.3.1 lift图 lift图把验证数据集中的观测数据根据它们的分数以升序或降序排列，分数是基于训练数据集估计的响应事件(成功)的概率。把这些分数再细分成10分位点，然后对验证数据集中的每个10分位点计算和图示成功的预测概率。如果这些成功的预测概率与估计概率具有相同的顺序（升序或降序），那么模型就是有效的。,17.1.3 两个评价模型成本的可视化工具,图17-1lift图示例比较了两个分类模型的lift图,Copyright 2003-12, SPSS Taiwan Corp.,图中可看出分数以降序排列，所以曲线减少越多表明模型越好。因此模型classification tree看起来比另一个更好，特别是在第3个10分位点，它具有较好的成功率。 用每个曲线的值除以基本线，可得到性能的相对指标，称为lift，它测量一个模型的价值。 对于模型classification tree，在第3个10分位点的lift值为2.77(即2.27/1.0)，这意味着使用模型classification tree的成功率是随机选择（基本线）的3倍。,Copyright 2003-12, SPSS Taiwan Corp.,17.1.3.2 ROC曲线 ROC曲线显示了给定模型的真正率即敏感性与假正率（错误正例）之间的比较评定。也就是说，给定一个二类问题，我们可以对检验集的不同部分，显示模型可以正确识别正样本的比例与模型将负样本错误标识为正样本的比例之间的比较评定。敏感性的增加以错误正例的增加为代价。,Copyright 2003-12, SPSS Taiwan Corp.,ROC曲线的画出以错误正例为水平抽，以敏感性为垂直轴，截止点是任意特定点。在模型比较方面，理想的曲线是和垂直轴一致的曲线。所以最佳曲线是最靠左边的曲线。 图17-2 3个分类模型的ROC曲线给出了对3个分类模型的ROC曲线，它说明最佳模型是reg2。不过三个模型实际上是相似的。,图17-2： 3个分类模型的ROC曲线,Copyright 2003-12, SPSS Taiwan Corp.,通常把数据集分为训练集和检验集，在训练集上建立模型，然后在检验集上评估其质量。怎样将可用样本分为训练样本和检验样本呢？ 这里我们将讨论将较小数据集划分为训练样本集和检验样本集的不同技术，这种技术通常叫做再取样方法。 17.1.4.1 再替换方法 所有可用的数据集都既用于训练集也用于检验集。换句话说，训练集和检验集是相同的,17.1.4 评估分类器的准确率,Copyright 2003-12, SPSS Taiwan Corp.,17.1.4.2保持方法和随机子抽样 保持（holdout）方法是我们目前为止讨论准确率时默认的方法（见图17-3 用保持方法估计准确率）。在这种方法中，给定数据随机地划分到两个独立的集合:训练集和检验集。通常，三分之二的数据分配到训练集，其余三分之一分配到检验集。使用训练集导出模型，其准确率用检验集估计。 随机子抽样(random subsampling)是保持方法的一种变形，它随机地选择训练集和检验集，将保持方法重复k次。总准确率估计取每次迭代准确率的平均值。,图17-3： 用保持方法估计准确率图,Copyright 2003-12, SPSS Taiwan Corp.,17.1.4.3 交叉确认 在k折交叉确认（k-fold cross-validation）中，初始数据随机划分成k个互不相交的子集或“折”D1，D2，Dk，每个折的大小大致相等。训练和检验进行k次。在第i次迭代，划分Di用作检验集，其余的划分一起用来训练模型。即在第一次迭代子集D2，Dk 一起作为训练集，得到第一个模型，并在D1上检验；如此下去。与上面的保持和随机子抽样方法不同，这里每个样本用于训练的次数相同，并且用于检验一次。对于分类，准确率估计是k次迭代正确分类的总数除以初始数据中的样本总数。 留一（leave-one-out）是k折交叉确认的特殊情况，其中k设置为初始样本数。用k-1个样本作为训练集，每次只给检验集“留出”一个样本，由此设计一个模型。从k个样本中选k-1个样本有k中选择，所以可用不同的大小为k-1训练样本重复进行k次。由于要设计k个不同的模型并对其进行比较，这种方法计算量很大。,Copyright 2003-12, SPSS Taiwan Corp.,17.1.4.4 自助法 自助法（bootstrap method）从给定训练样本中有放回均匀抽样。即每当选中一个样本，它等可能地被再次选中并再次添加到训练集中。 有多种自助法方法。常用的一种是.632自助法，其方法如下，设给定的数据集包含d个样本，该数据集有放回地抽样d次，产生d个样本的自助样本集或训练集。原数据样本中的某些样本很可能在该样本集中出现多次。没有进入该训练集的数据样本最终形成检验集。,Copyright 2003-12, SPSS Taiwan Corp.,“数字63.2从何而来？”每个样本被选中的概率是1/d，因此未被选中的概率是（1-1/d）。经过挑选d次，一个样本在全部d次挑选都未被选中的概率是（1-1/d）d。如果d很大，该概率近为e-1=0.368。这样，36.8的样本未被选为训练集而留在检验集中，其余的63.2将形成训练集 我们可以重复抽样过程k次，每次迭代，使用当前的检验集得到从当前自助样本得到的模型的准确率估计。模型的总体准确率则用下式估计： （17-10） 其中，Acc(Mi)test_set是自助样本i得到的模型用于检验集i的准确率。Acc(Mi)train_set是自助样本i得到的模型用于原数据样本集的准确率。对于小数据集，自助法效果胜过交叉确认。,Copyright 2003-12, SPSS Taiwan Corp.,17.2基于统计检验的准则,17.2.1 统计模型之间的距离 距离函数有不同的类型，当所考虑的变量是定量变量时，距离是最典型的相似性指标。如果变量是定性的，观测数据间的距离可以通过相似性指标测量。 17.2.1.1欧氏距离 (17-11),Copyright 2003-12, SPSS Taiwan Corp.,17.2.1.2 熵距离 （17-12） 17.2.1.3 卡方距离 （17-13） 17.2.1.4 0-1距离 （17-14）,Copyright 2003-12, SPSS Taiwan Corp.,17.2.2 统计模型的离差,17.2.2.1 欧氏离差 假设f是总体的未知密度，g=p是一逼近它的密度函数族（用有I个参数的向量标记）。一个统计模型g对于一个目标模型f的离差可以用欧氏距离定义： （17-15） 如果知道真正的模型f，就能通过对不同近似模型g的选择使离差最小。这样可以得到g的离差（因为是参数近似）作为未知概率模型和最佳参数统计模型之间的离差 ： （17-16）,Copyright 2003-12, SPSS Taiwan Corp.,然而f是未知的，因此不能确定谁是最佳的参数统计模型。这样用样本估计 来代替f，而I参数是基于数据估计得到的。在 f(x)样本估计和最佳的统计模型之间的离差称为g的离差（源于估计过程） （17-17） 在参数近似产生的离差和因为估计产生的离差之间找到一个平衡，作为函数f和样本估计量之间的总离差，它由如下等式给出： （17-18） 它表示了两种离差的代数和，一个源自参数近似，另一个来自估计过程。一般极小化第一种离差则倾向于复杂的模型，这样则过分拟合数据；极小化第二种离差则倾向较简单的模型，这样当观测样本有变化时模型将更稳定。,Copyright 2003-12, SPSS Taiwan Corp.,17.2.2.2 Kullback-Leibler离差 为了定义一个一般的评估量，需要用到Kullback-Leibler离差，这是一个比欧氏离差更一般的离差，但17.2.2节中的思想仍然适用。Kullback-Leibler（KL）离差可以用于任何类型的观测数据，它源自熵距离，其定义如下： （17-19） 现在可以给出统计检验并把它用于基于总的KL离差估计量的模型比较。假设P是由向量=(1，I)决定的概率密度函数，x1,x2,xn是一系列具有独立分布的观测值，所以样本密度函数可以表示为：,Copyright 2003-12, SPSS Taiwan Corp.,（17-20） 表示参数的最大似然估计量，似然函数L在这一点计算。对得到的结果表达式取对数并乘以-1/n，得到： （17-21） 实际应用中经常考虑对数形式的似然性评分，它等于： （17-22）,Copyright 2003-12, SPSS Taiwan Corp.,17.3 基于计分函数的标准,17.2节解释了一个模型选择策略如何在模型拟合和模型简化之间取得折中。现在从另一个角度看一下这个问题，它是基于偏差和方差之间的折中。我们应用估计量均方差原理来测量选择作为目标模型f最佳逼近模型 模型的欧氏距离。 （17-23）,Copyright 2003-12, SPSS Taiwan Corp.,注意到 是基于数据的估计，所以它受样本变化性的影响。此外对于 可以定义它的期望值E( )和方差Var( )。根据均方差的性质可以得到： （17-24） 这表明与一个模型相关联的误差可分为两个部分：系统误差（偏差），它不依赖于观测数据并反映由于参数逼近产生的误差；样本误差（方差），它反映了由于估计过程产生的误差，因此应精心选择可以平衡这两部分的模型。,Copyright 2003-12, SPSS Taiwan Corp.,Akaike信息标准（AIC）, 1974年Akaike形式化了其思想： （1）参数模型使用最大似然法进行估计； （2）指定的参数族包含作为特例的未知分布f(x)。 这样Akaike通过采用Kullback-Leibler样本离差函数定义了一个评分函数给每个模型赋予一个分数。在标准形式下，AIC定义为如下等式： （17-25）,其中， 是对计算最大似然估计的似然函数取对数，q是模型中参数的个数,Copyright 2003-12, SPSS Taiwan Corp.,贝叶斯信息标准（BIC），也称为SC。它是由Schwarz(1978)制定的并用下列表达式定义： （17-26） BIC与AIC区别仅在于第二部分，现在第二部分也依赖于样本规模n。当n增长时，BIC比AIC更倾向于简单的模型。当n变大时，与n是线性关系的第一项的影响压倒了与n是对数关系的第二项占支配地位。这对应着这样的事实：对于一个很大的n来说在MES表达式中的方差项可以被忽略。虽然BIC与AIC表面相似，但AIC是用经典的渐进的论断来证明，而BIC是用贝叶斯构架证明。,Copyright 2003-12, SPSS Taiwan Corp.,17.4 贝叶斯标准,在贝叶斯推导中每一个模型给一个对应于模型后验概率的分数,一个模型成为一个在所有候选模型空间中取值的离散随机变量。这个概率可以由贝叶斯规则计算： （17-27） 贝叶斯评分方法首先要解决的问题是计算模型的似然。对于一个有参数向量指定的模型M，需要计算： （17-28）,Copyright 2003-12, SPSS Taiwan Corp.,贝叶斯方法更大的优点在于模型的评分数是概率，所以还可以用于从各种竞争模型中得到推论，而不是只基于一个选定的模型得到推论，这考虑了模型的不确定性。考虑预测某个变量Y值的问题，对于在K个可选模型中，选定模型的不确定性，贝叶斯预测是： （17-29）,Copyright 2003-12, SPSS Taiwan Corp.,17.5计算标准,17.5.1交叉验证标准 交叉验证的思想是把样本分为两个样本子集：一个是训练样本集，包括n-m个样本；一个是检验样本集，包括m个样本。第一个样本用来拟合模型，第二个样本用来估计期望离差或者估算一个距离。比如，在有定量输入的神经网络中，通常用高斯离差： （17-30）,Copyright 2003-12, SPSS Taiwan Corp.,进一步的改进方法称为k-fold交叉验证。方法将所有的数据分成k个相同大小的子集，模型进行k次拟合，每次留下一个子集用来计算预测错误率。最后的错误率是所得到错误率的算术均值。 另一个常用的方法是留一(leaving-one-out )方法，从k个样本子集中各取出一个样本，用这些样本校正预测。,Copyright 2003-12, SPSS Taiwan Corp.,17.5.2 自展标准,自展方法是基于重新产生总体的“真实的”分布并且对观测样本进行重新抽样。为了比较可选择的模型，可以从虚拟的总体(可用样本)中重新抽取(重新抽样)并可以使用先前的模型比较结果。 自展方法不仅可以评估一个模型的离差及它自身的精确性，还可以提高结果的精确性。装袋 (bagging)和提升（boosting）就是两种这样的技术。,Copyright 2003-12, SPSS Taiwan Corp.,它们将k个学习到的模型组合起来，旨在创建一个改进的复合模型。对于分类和预测 ，如图17-4 提高模型的准确率所示，他们都产生一系列分类或预测的模型M1,M2Mk，接着将k个学习的得到的模型M1,M2Mk组合起来，旨在创建一个改进的复合模型M* 。使用投票策略给定未知样本的预测。,图17-4： 提高模型的准确率,Copyright 2003-12, SPSS Taiwan Corp.,17.5.2.1 装袋 装袋(bagging)方法可以描述如下：在每次循环的过程中，从可用的训练数据集中进行有替换的抽样。给定d个样本的集合D，bagging过程如下。对于迭代i(i=1,2,，k),d个样本的训练集Di 采用有放回抽样，由原始样本集D抽样。每个训练集都是自助样本，由于使用有放回抽样，D的某些原始样本可能不在Di 中出现，而其它样本可能会出现多次。由每个训练集Di 学习，得到一个分类模型Mi 。为了对一个未知的样本x分类，每个分类器Mi 返回它的类预测，算作一票。,Copyright 2003-12, SPSS Taiwan Corp.,bagging算法如下图：,Copyright 2003-12, SPSS Taiwan Corp.,17.5.2.2 提升 在提升方法中，给每个训练样本赋予权重。迭代地学习k个分类器序列。学习得到分类器Mi之后，更新它的权重，目的在于使得其后的分类器Mi+1对Mi误分类的训练样本更关注。最终的提升分类器M* 组合每个分类器，其中每个分类器投票的权重是其准确率的函数。 Adaboost提升算法,Copyright 2003-12, SPSS Taiwan Corp.,给定数据集D,包含d个有类标记的样本，其中yi是样本Xi的类标号。 初始，Adaboost对每个训练样本赋予相等的权重1/d。执行算法的其余部分k轮产生k个分类器。 在第i轮，使用有放回抽样从D中样本抽样，形成大小为d的训练集Di，每个样本被抽中的机会由它的权重决定。从训练集Di 导出模型Mi ，计算模型误差，训练集Di 中的样本根据分类情况调整权重。如果样本不能正确的分类，它的权重增加，否则权重减小。 然后，分类器使用这些权重产生下一轮的训练样本，这样的目的是在建立分类器时，希望它更关注上一轮错误的分类，即建立一个互补的分类器系列。,Copyright 2003-12, SPSS Taiwan Corp.,Adaboost算法 我们来解释一下算法中涉及到的一些数学问题。 为了计算模型Mi 的误差率，我们求Mi 误分类的Di 中所有样本的加权和:,Copyright 2003-12, SPSS Taiwan Corp.,（17-31） 其中 是样本Xj的误分类误差：如果样本误分类，则 为1，否则为0。 不像装袋将相同的表决权赋予每个分类器，提升根据分类器的分类情况，对每个分类器的表决权赋予一个权重。分类器的错误率越低，它的准确率越高，因此它的表决权重就应当越高。为了得到这个效果，我们利用以下的公式给每个分类器赋上权重:,Copyright 2003-12, SPSS Taiwan Corp.,（17-32） 针对每个类c,对每个将样本X分类为类c的分类器的权重求和，具有和最大的类是样本X的分类结果。,Copyright 2003-12, SPSS Taiwan Corp.,17.5.3 遗传算法,进化理论把物种生存的概率与它适应环境的能力相联系。这些适应性的改变使其后代得到优化，把最好的性质从这一代传到下一代。遗传算法应用相同的思想，它们模仿这些进化机制创造一个适应性的方法解决优化问题。 遗传算法对模型评价来说很重要。这些算法使我们可以以非常灵活的方式控制模型选择的过程，这是因为它们并没有一个内在的模型假设。,Copyright 2003-12, SPSS Taiwan Corp.,17.6小结,本章我们已经系统地比较了在数据挖掘中评价模型的主要标准。这些方法可以分为:,贝叶斯标准,基于评分函数的标准、,基于统计检验的标准、,基于损失函数的标准、,计算标准,
