（计算机科学与技术专业论文）分类器性能评价研究.pdf

学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同 意学校向国家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：试畸彭予 导师签名： k 未蟛 签字日期：w 【o 年莎月6 日签字同期：m p 年月，81 7 t 中图分类号：t p 3 0 1 6 u d c ： 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 分类器性能评价研究 r e s e a r c ho nc l a s s i f i e rp e r f o r m a n c ee v a l u a t i o n 作者姓名：武婷婷 导师姓名：王志海 学号：0 8 1 2 0 5 5 3 职称：教授 学位类别：工学学位级别：硕士 学科专业：计算机科学与技术研究方向：数据挖掘 北京交通大学 2 0 1 0 年6 月 il【、l、心 一17x - 致谢 本论文的工作是在我的导师王志海教授的悉心指导下完成的，王志海教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响在此衷心感谢两年来 王志海老师对我的关心和指导 付斌博士对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心 的感谢 在实验室工作及撰写论文期间，张尚超，刘雪莲等同学对我论文中的分类器 性能评价研究工作给予了热情帮助，在此向他们表达我的感激之情 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业 最后，衷心地感谢在百忙之中审阅论文的各位老师和专家，恳请各位老师多 多批评指正，并提出宝贵的意见 r j ，多 【 - t 中文摘要 中文摘要 数据挖掘是研究从大量数据中用非平凡的方法发现有用知识的理论与方 法分类作为数据挖掘的一个重要课题，在统计学、机器学习、神经网络和专家 系统中得到了广泛的研究分类器性能评价作为分类过程的一个重要环节，对于 选择适当的分类器进行分类有非常重要的指导作用 本文首先介绍了数据挖掘及分类的相关概念及基本技术，随后对分类器性能 评价的通用标准以及评价方式作出详尽的总结归纳，然后对w e k a 环境下的分类器 性能评价的实现，以及评价的各项指标的数学意义作出分析最后，本文就分类 器性能评价标准中的误差一项，结合限制性贝叶斯分类器的特质，提出一种基于 限制性贝叶斯分类器的误差分解方法这种方法在0 1 损失函数的偏差方差分解方 法基础上，将限制性贝叶斯的预测概率引入到其误差分解过程中这种方法下， 分类器的误差被分解为偏差和方差两部分，偏差反映的是学习算法的平均预测与 真实值之间的偏离程度，方差反映的是学习算法在不同数据集上的预测波动 为了说明该算法的作用，本文对三种限制性贝叶斯分类算法在9 个u c i 数据 集进行了实验，实验结果表明t a n 分类器的性能最优在本文的误差分解方法下， 可清楚看到三种限制性贝叶斯分类器的误差结构，以及t a n 最优的重要原因 关键词：分类，分类器，贝叶斯网络，偏差，方差 分类号：t p 3 0 1 6 宰本文得到国家自然科学基金项目资助( 6 0 6 7 3 0 8 9 ) ， ， abst ract a bs t r a c t d a t am i n i n gi st h et h e o r ya n dm e t h o do nr e s e a r c h i n gh o wt om i n ek n o w l e d g ef r o m d a t ai nv e r yl a r g ed a t a b a s e si nn o n t r i v i a lm e t h o d s c l a s s i f i c a t i o n ，a sa ni m p o r t a n tt h e m e i nd a t am i n i n g ，h a sb e e nr e s e a r c h e de a r l i e ri ns t a t i s t i c s ，m a c h i n el e a r n i n g ，n e u r a l n e t w o r k , e x p e r ts y s t e m s ，e t c a sa ni m p o r t a n tp a r to ft h ec l a s s i f i c a t i o np r o c e s s ， c l a s s i f i e rp e r f o r m a n c ee v a l u a t i o np l a y sav e r yi m p o r t a n tr o l ei ng u i d i n gt h ea p p r o p r i a t e c l a s s i f i e rs e l e c t i n g i nt h i sp a p e r , w ef i r s t l yi n t r o d u c e dt h ec o n c e p t sa n db a s i ct e c h n i q u e sa b o u td a t a m i n i n ga n dc l a s s i f i c a t i o n t h e n ，w ed e t a i l e d l ys u m m a r i z e dt h ec o m m o ns t a n d a r d sa n d m e t h o d sf o re v a l u a t i n gt h ec l a s s i f i e r s t h e n ，w ed e t a i l e d l ya n a l y z e dt h ei m p l e m e n t a t i o n o ft h ec l a s s i f i e rp e r f o r m a n c ee v a l u a t i n ga sw e l la st h em a t h e m a t i cs e n s eo fp r i m a r y m e a s u r e so fe v a l u a t i o nu n d e rt h ew e k ap l a t f o r m f i n a l l y , w ep r o p o s e dam e t h o do f e r r od e c o m p o s i t i o nw h i c hb a s e do nt h er e s t r i c t i v eb a y e sc l a s s i f i e r s t h i sm e t h o di s b a s e do nt h et h em e t h o do fb i a sa n dv a r i a n c ed e c o m p o s i t i o nf o r0 - ll o s sf u n c t i o n w e i n d u c e dt h e p r o b a b i l i t yo fr e s t r i c t e db a y e s i a nc l a s s i f i e r f o r e c a s ti n t ot h ee r r o r d e c o m p o s i t i o np r o c e s s i nt h i sa p p r o a c h ，t h ec l a s s i f i c a t i o ne r r o ri sd e c o m p o s e di n t ot w o p a r t sc a l l e db i a sa n dv a r i a n c e t h eb i a sr e f l e c t st h ed e v i a t i o nb e t w e e nt h ea v e r a g e f o r e c a s to fl e a r n i n ga l g o r i t h ma n dt h er e a lv a l u e s ，w h i l et h ev a r i a n c er e f l e c t st h e f l u c t u a t i o no fl e a r n i n ga l g o r i t h mp r e d i c tp e r f o r m a n c eo nd i f f e r e n td a t as e t s i no r d e rt oi l l u s t r a t et h er o l eo ft h ea l g o r i t h m ，a ne x p e r i m e n tw a sc o n d u c t i e do n t h r e ek i n d so fr e s t r i c t e db a y e s i a nc l a s s i f i c a t i o na l g o r i t h mw h i l eo nn i n eu c id a t as e t s t h ee x p e r i m e n t a lr e s u l t si n d i c a t e dt h a tt a nc l a s s i f i e ri st h eo p t i m a lc l a s s i f i e r a n dt h e c o m p o s i t i o no ft h et h r e er e t r i c t e db a y e s i a nc l a s s i f i e ri sc l e a r l yo b s e r v e da n dt h e r e s e a s o nw h yt a nc l a s s i f i e ri st h e o p t i m a lc l a s s i f i e rb yt h i s e r r od e c o m p o s i t i o n m e t h o d k e y w o r d s ：c l a s s i f y , c l a s s i f i e r , p e r f o r m a n c ee v a l u a t i o n ，r e s t r i c t e db a y e s i a n c l a s s i f i e r , b i a s ，v a r i a n c e c l a s s n 0 ：t p 3 0 1 6 l ，l 】“ 目录 目录 中文摘要一v a b s t r a c t v i i l 引言1 1 1论文背景1 1 1 1 数据挖掘1 1 1 2 数据挖掘中的分类技术3 1 2本文主要工作4 2 分类器及其评价7 2 1分类与分类器7 2 2分类器性能评价9 2 2 1 分类器性能评价的作用1 0 2 2 2 分类器性能评价的问题1 0 2 3分类器性能度量标准1 0 2 3 1 分类器的准确率1 1 2 3 2r o c 曲线及a u c 。1 2 2 3 3 反馈率一精确率曲线1 3 2 3 4 成本敏感评价1 4 2 3 5m d l 原理与信息损失函数1 5 2 4分类器性能评价方式1 6 2 4 1 留置法1 6 2 4 2 随机子抽样1 7 2 4 3k 折交叉验证17 2 4 4 留一法18 2 4 5 引导法18 2 4 6 置信度试验18 2 4 7t 检验2 0 3w e k a 环境下的分类器评价分析2 3 3 1w e k a 简介。2 3 3 2w e k a 分类器评价的静态结构。2 4 3 2 1e v a l u a t i o n 包的分解2 4 3 2 2 分类器评价主类e v a l u a t i o n 2 5 北京交通人学硕十学位论文 3 3 e v a l u a t i o n 运行方式2 6 3 3 1 在训练集上进行交叉验证2 7 3 3 2 独立的训练集合与测试集合2 7 3 3 3 对给定的分类器进行评价2 8 3 4 e v a l u a t i o n 的运行参数2 8 3 4 1 与建立分类器相关的参数2 9 3 4 2 与运行方式相关的参数3 0 3 4 3 分类器在测试集之上的评价指标“3 l 3 5w e k a 分类器评价指标的数学意义与程序3 5 3 5 1 k a p p a 统计量3 5 3 5 2 相关系数3 6 3 5 3 数值预测评价指标3 7 3 5 4k & b 信息量4 0 3 5 5 类复杂度统计量一4 3 3 5 6 各类的信息检索统计4 5 4 基于限制性贝叶斯分类器的误差分解4 9 4 1误差的偏差一方差分解4 9 4 2 基于0 1 损失函数的偏差一方差分解5 0 4 2 1 标记定义5 0 4 2 20 1 损失函数偏差加方差5 1 4 3限制性贝叶斯分类器5 3 4 3 1 朴素贝叶斯分类器一5 4 4 3 2t a n 算法分类器5 6 4 3 3 s u p e r p a r e n t 算法分类器5 8 4 4一种基于限制性贝叶斯分类器的误差分解方法6 0 4 5实验方法6 l 4 6实验及结果分析6 1 5 总结6 5 参考文献6 7 作者简历7 1 独创性声明一7 3 学位论文数据集7 5 引言 1 引言 1 1 论文背景 由于数据的不断产生和数据收集、储存技术的进步，数据集的规模越来越大， 为了有效地在海量数据中提取出有用的信息，人们提出并发展了数据挖掘技术数 据挖掘( d a t am i n i n g ，d m ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含在其中的、人们事先不知道的、但潜在有用的信息和知识的 过程，并运用这些信息帮助、影响决策数据挖掘能够自动分析数据和进行归纳 性的推论，从中挖掘出潜在的规律或模式目前业界的数据挖掘软件主要有s a s e n t e r p r i s em i n e r5 3 ，s p s sc l e m e n t i n e l 2 ，r a p i d m i n e r4 2 ，v i s c o v e r ys o m i n e r 5 0 ， s a p n e t w e a r7 0d a t am i n i n gw o r k b e n c h ，o r a c l ellgd a t am i n i n g ，m i c r o s o f ts q l s e r v e r2 0 0 5a n a l y s i ss e r v i c e s 等 1 1 1 数据挖掘 数据挖掘( d a t am i n i n g ) ，又称数据库中的知识发现( k n o w l e d g ed - c o v e r yi n d a t a b a s e ) ，在最近几年罩已被数据库界所广泛研究 图1 1 描述了数据挖掘的基本过程和主要步骤，包括： 一 ( 1 ) 数据清理与集成：消除噪声和不一致数据，并将多种数据源组合在一起 ( 2 ) 数据选择：界定数据对象，选择目标数据集 ( 3 ) 数据变换预处理：数据变换或统一成适合挖掘的形式，如通过汇总或聚集 操作 ( 4 ) 数据挖掘：利用选取的挖掘算法对数据进行挖掘，提取数据模式 ( 5 ) 模式评估与知识标识：根据某种兴趣度度量，识别标识知识的真正有趣的 模式一般数据挖掘的搜索过程要反复多次，因为分析人员评价输出结果后，可 能会有新的问题或对某一方面的数据做更精细的查询可使用可视化和知识标识 技术，向用户提供挖掘的知识 数据挖掘的可以解决的问题有以下几个方面： ( 1 ) 预测建模( p r e d i c t i v em o d e l i n g ) 涉及以说明变量函数的方式为目标变量建立 模型有两类预测建模任务：分类( c l a s m i e a t i o n ) 用于预测离散的目标变量，回归 ( r e g r e s s i o n ) 用于预测连续的目标变量分类技术常见的有决策树分类法、基于规则 北京交通人学硕十学位论文 的分类法、神经网络、支持向量机和朴素贝叶斯分类法等 = = i l 数据源 l i 上一 知识 图1 1 数据挖掘的基本过程和主要步骤 f i g u r e1 1t h eb a s i cp r o c e s sa n dm a i ns t e p so fd a mm i n i n g ( 2 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 用来发现描述数据中相关联特征的模式所 发现的联系可用关联规贝j j ( a s o c i a t i o nr u l e ) 或频繁项集的形式表示关联分析的研究 主要集中在概念问题、实现问题和应用问题三个方面其中概念问题主要研究建 立描述关联分析的理论基础的框架，扩展形式机制，以处理新的模式类型，以及 扩展形式机制用于关联分析的算法主要有a p r i o f i 算法和f 1 p 增长算法 ( 3 ) 聚类分析( c l u s t e ra n a l y s i s ) 旨在发现紧密相关的观测值族群，使得与属于不 同簇的观测值相比，属于同一簇的观测值相互之间尽可能相似聚类与分类的区 别是聚类不依赖于预先定义好的类，不需要训练集常用的聚类分析算法有k 均 值和d b s c a n 算法 ( 4 ) 异常检澳i j ( a n o m a l yd e t e c t i o n ) 通过研究历史数据识别其特征显著不同于其 他数据的观测值异常检测的应用包括检测欺诈、网络攻击等 2 引言 1 1 2 数据挖掘中的分类技术 数据库蕴藏大量信息，可以用来作出明智的决策分类和预测是两种数据分 析形式，可以用于提取描述重要数据类或预测未来的数据趋势的模型这种分析 有助于我们更好地全面理解数据银行贷款员需要分析数据，搞清楚哪些贷款申 请者是“安全的”，银行的“风险 是什么；医学研究者希望分析乳腺癌数据，预 测病人应当接受三中具体治疗方案的那一种，以上两例中的这些数据分析任务都 是分类( c l a s s i f i c a t i o n ) ，都需要构造一个模型或分类器( c l a s s i f i e r ) 来预测类属标 号，如贷款应用数据的“安全”或“风险”，医疗数据的“疗法a ”，“疗法b ”或 “疗法c ”这些类属性可以用离散值表示，其中值之间的顺序没有意义 数据分类是一个两步过程如图1 2 第一步，建立描述预先定义的数据类或概念集的分类器这是训练阶段，其 中分类算法通过分析或从训练集“学习”来构造分类器由于提供了每个训练元 i j 练数据 旦鱼j 丝i i 2 9 箜! 旦旦丝金! 旦旦丝型垒兰苎! ! 丝 一 t s a n d y 3 0 n e 一：y o u n g 。1 0 w ，1 1 1 s k y b i lil e e y o u n g 1 0 w r i s k y c a r o li d ef o x ；m i d d l ej a g e d h i g h s a f e r i c kf i e l d m i d d l ea g e dl o w l r i s k y“ 1 一 一“一“_ ” _ “_ - _ f - n “”1 4 “。“ s u s a nl a k es e n i o rl o w | s a f e 一一一t 。”一 + 一”“”“” c l a i r ep h i d sl s e n i o rm e d i u m；s a f e 璺s 堡i 主b 。羹叵畦照l 金曼g 金照h i g bi 墨a f 曼 ； 分类规则 分类算法 i fa g e = y o u n gt h e nl o a n _ d e c i s i o n = r i s k y i fi n c o m e = hig ht h e nl o a c hd e c i s i o n = s a f e i fa g e = m i d d l e a g e da n di n c o m e2l o w t h e nl o a n _ d e c i s i o n = r is k y a 1 图1 1 数据分类过程：a ) 学 - - j ：用分类算法分析训练数据b ) 分类：测试数据用 于评估分类规则的准确率 f i g u r e1 1t h ep r o c e s so fd a t ac l a s s i f i c a t i o n a 1l e a r n i n g ：a n a l y z et h ed a t aw i m c l a s s i f i c a t i o na l g o r i t h m b ) c l a s s i f y ：t h et e s t i n gd a t aa l eu s e dt oe v a l u a t et h ea c c u r a c y 北京交通人学硕十学位论文 b ) 图1 2 ( 续) 数据分类过程：a ) 学习：用分类算法分析训练数据b ) 分类：测试 数据用于评估分类规则的准确率 f i g u r e1 2 ( c o n t d ) t h ep r o c e s so fd a t ac l a s s i f i c a t i o n a ) l e a r n i n g ：a n a l y z et h ed a t a w i mc l a s s i f i c a t i o na l g o r i t h m b ) c l a s s i f y ：t h et e s t i n gd a t aa r eu s e dt oe v a l u a t et h e 组的类标号，这一步也称作监督学习( s u p e r v i s e dl e a r n i n g ) 第二步，使用模型进行分类首先评估分类器的预测准确率如果用训练集 来测量分类器的准确率，则评估可能是乐观的，因为分类器趋向于过度拟合，因 此，需要使用测试集来进行测试如果对分类器的评估结果是可接受的，那么就 使用该分类器对未知类标的数据进行分类 1 2 本文主要工作 分类作为数据挖掘技术的核心技术之一，对分类技术进行研究有着不可估量 的现实意义，而分类器评估作为分类过程的一个重要坏节，对于选择合适的分类 器进行分类起着非常重要的指导作用人们希望尽量得到性能最佳的分类模型， 这使得对分类器性能的评价至关重要只有通过优秀的评价标准才能选择出性能 更好的分类器 在上述背景下，本文完成的工作主要有以下几个方面： 第1 章给出了课题的出发点以及研究的问题及范围，叙述了数据挖掘产生的 4 引言 背景以及数据挖掘相应的分析方法，分析了分类技术的研究现状，介绍了本文所 完成的工作 第2 章是全文的理论基础，分别介绍了分类与分类器性能度量的理论和相关 知识，包括分类的概念和分类器的构造方法以及分类器的评估的重要性重点分 析了现有的一些公认的分类器性能度量标准，以及相应的评价方式，并且对它们 特点和适用情况做了简单的比较 第3 章分析了w e k a 平台的大致结构，介绍了w e k a 中分类器评价部分的相关 情况然后，对w e k a 环境下的分类器评价方法作了深入的分析，包括w e k a 分 类器评价的静态结构，以及动态运行方式和运行参数随后，对w e k a 下各项评价 指标分别作出详尽的分析 第4 章是本文的理论运用部分，首先给出了误差的偏差方差分解的定义，以 及0 1 偏差方差分解的定义及推理过程接下来分析并实现了三种限制性贝叶斯分 类器算法结合限制性贝叶斯分类器的特点，在已有的误差分解方法基础上提出 一种基于限制性贝叶斯分类器的误差分解算法在w e k a 环境下实现该算法，并且 在上述三种分类器上进行试验，从误差分解的角度，观察并分析三种算法的分类 性能 第5 章，对本课题研究做了分析和总结，分析了本文中存在的不足之处，并 给出了本课题将来的研究内容和方向 5 分类器及其评价 2 分类器及其评价 2 1 分类与分类器 分类【1 , 2 】数据挖掘三大核心技术( 关联规则、分类、聚类) 之一，其实质是产生 一个目标函数 该函数将输入数据集的属性集x 映射到已经定义的类标签y 上该 目标函数通常也被称为分类模型或分类器当前，分类在很多领域都得到了应用 和推广分类和预测是两个概念，两种方法都是数据挖掘中对数据进行分析的方 法，但分类不能等同于预测分类是预测分类标号( 或离散值) ，而预测建立连续 值函数模型可以说分类是针对离散数据的情况，而预测则是针对连续数据 分类的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每 一个类找到一种准确的描述或者模型描述常常用谓词表示由此生成的类描述 用来对未来的测试数据进行分类尽管这些未来的测试数据的类标签是未知的， 但我们仍可以由此预测这些新数据所属的类但对新数据所属的类仅仅是预测， 而不是肯定也可以由此对数据中的每一个类有更好的理解也就是说：我们获 得了对这个类的知识 用于分类的描述或者模型叫做分类器，其构造和使用如图2 1 所示迄今为止， 已经发展了很多种分类器例如，决策树、朴素贝叶斯、神经网络、支持向量机 等这些分类器分别采用不同的学习算法建立模型，该模型应尽量拟合输入数据 集的属性集与类别之间的关系分类器的构造需要输入数据，或称训练集( t r a i n i n g s e t ) ，是一条条的数据库记录( r e c o r d ) 组成每一条记录包含若干条属性 ( a t t r i b u t e ) ，组成一个特征向量，记录也称为实例或者样本训练集的每条实例 还有一个特定的类标签( c l a s sl a b e l ) 与之对应该类标签是系统的输入，通常是 以往的一些经验数据一个具体样本的形式用样本向量( 1 ，i ，v 2 ，；c ) 来表示其 中表示字段值，c 表示类别训练集是分类器的基础 7 北京交通人学硕十学位论文 分类第阶段 训 图2 1 分类器构造和使用 f i g u r e2 1c o n s t r u c t i o na n du s i n go fc l a s s i f i e r 解决分类问题的过程分为两个阶段： 第一阶段，采用学习算法，建立模型阶段【l 】( 见图2 2 ) 建立模型是为了描述 预定的数据类集或概念集的分类器通常这一步骤也被称作为训练( t r a i n i n g ) 或 者是学习( l e a m i n g ) 分类算法通过分析由属性描述的训练例、训练样本或者是 实例来构造模型其中每一条训练例属于其中一个预定义的类，由一个称作类标 签属性( c l a s sl a b e la t t r i b u t e ) 的属性确定训练数据集就是用来建立分类模型所 使用的训练数据的集合训练数据集中的单条训练数据称作训练样本，并随机地 由样本群选取由于提供了每个训练样本的类标号，因此，该步也被称作有监督 的学习，即模型的学习在被告知每个训练样本属于哪个类的“指导”下进行它 不同于另外一种无监督的学习，也称作聚类，此时每个样本的类标签是未知的， 要学习的类的个数或者集合也可能事先不知道，也就是没有类标签作为学习的“指 导 一般的，学习模型用决策树、分类规则或其他数学公式的形式来表示，学习 模型使用的形式不用，学习出来的分类模型性能也有差别，所给例子采用的是分 类规则的形式建立模型 模型和分类器的概念并不完全一样，分类器的产生依赖于两个条件，一个是 模型，另一个是训练数据集，两者缺一不可如果只存在模型，而没有数据来训 练它，只能称之为分类器算法，当有了训练数据进行训练学习之后才产生能够 用于对新数据进行分类的分类器同时，仅仅有训练数据集，但是没有模型，也 不可能产生分类器，没有模型计算机无法从训练集中产生分类规则对测试实例或 者是新数据进行分类，也就是说，分类器建立在模型之上另外，虽然不同模型 决定了产生的分类器的分类性能，但是对于同一种模型，分类器还和训练集有关， 训练集中训练数目的多少以及属性个数的多少，同样决定了分类器的分类性能， 对于某些模型，如果训练实例数目过少，分类器性能可能很差，而有些模型对于 训练实例属性个数较多时，产生的分类器性能同样较差因此，分类器是模型和 练 分类器及其评价 训练数据集的产物，受模型和训练数据的影响 第二阶段【n ，将已经学习得到的分类模型用于测试集，对测试集中未知类别的 实例进行分类，图2 2 问号处所指最终会取得训练集中类别的某个值首先评价 分类模型，评估结果出来后，如果认为模型的准确率和计算复杂度可以接受，就 可以用它对类标签未知的测试例进行分类，这些测试例也称为未知的或先前未知 的数据很显然，由于分类模型倾向于过度拟合数据，因此通过训练集产生的分 类模型未必是最佳的，这就导致对测试集的分类可能产生错误而人们希望尽量 得到性能最佳的分类模型，这使得对分类器性能的评价至关重要只有通过优秀 的评价标准才能选择出性能更好的分类器 训练集 i ；一序号j 属性1 ；属性2 ：属件3 一属性4 一i 类别 1 s l 删：h o t hf 2 s u r l y h o t htn o - j 一_ ，一9 v e r c 喊j h o t 蔓一一f j y j 4 r a i n y m i l dhf y e s 5 r a c y c o o lnf y e s 6 r a c y ：c o o l ntn o ：7 j ，；o v e r c 撤，c o o l+ n t0y e s 。 。8；s t a m y ! l m dh fn o 9 ：s i g l n y ， c o o lnf y 鹤 m 毋i 一仃羽二n 一：f ， s t u l r l y m i k tn：t ， o v e r c a s t ：n u k lht 口 一一 一。“一“ o v 盯c a s th o tnf 0 m 时：m 1 3 d ht f 测试集 图2 2 分类基本步骤示例 f i g u r e2 2e x a m p l eo fb a s i cs t e p so fc l a s s i f i c a t i o n 2 2 分类器性能评价 评估是数据挖掘能否取得真正进展的关键一环【3 】采取什么样的分类器来解决 某一具体问题，需要对该分类器作出评价，或是在不同分类器之间进行系统的比 9 t 专一 1 二寸 3 一l l o l 一 一 二一 北京交通人学硕十学位论文 较评估评估并不像看上去那样简单 2 2 1 分类器性能评价的作用 我们知道，分类器性能评价是整个分类过程中不可或缺的一环对分类器性 能进行恰当的评价是决定是否采用该学习方法的关键所在分类器性能评价的这 一重要作用不仅用于对单个分类器进行评价以便决定是否采纳该学习方法下分类 器对未知类标数据的预测结果，还可以用于指导分类器的生成例如，多样性性 能评价指标应用于分类器的组合中，可以有效地选取基分类器，并组合生成性能 更优的分类器还有一些情况下，分类器评价用于调整分类器构建过程中的参数， 例如建立决策树过程中的参数优化 2 2 2 分类器性能评价的问题 我们虽然可以观察用不同推论方法在某个训练集上的不同结果，但在训练集 上表现好的绝不意味着在独立的测试集上会有好的表现我们需要的评估方法要 能够预知推论方法在实践中性能表现好与否 为了预测一个分类器在新数据上的性能表现，需要一组没有参与分类器建立 的数据集，并在此数据集上评估分类器的误差率等这组独立的数据集叫测试集 ( t e s ts e t ) 尽管可以直接使用原训练集进行评价，但就评价本身而言没有意义这 是由于分类器j 下是通过学习这些相同的训练数据而来的，因此该分类器在此训练 数据集上的任何性能评估结果都是乐观的，而且是绝对乐观的所以，除非是要 进行数据推理而非预测，我们通常对训练数据集的分类误差率不感兴趣 如果数据源充足，对分类器的评价并不是问题可以取一个较大的样本用来 训练，取另一个不同且独立的大样本数据用于预测训练样本大能够加强所建分 类器的性能，测试样本大能够加大对所建分类器误差估计的准确性问题在于当 数据源不充足时，现实中常常会发生这样的情况，那么，如何利用有限的数据集 就成为研究的重点 2 3 分类器性能度量标准 在比较不同的分类器时，常常需要参照的关键性能指标有 1 】【2 】【4 】： 分类准确率 指模型正确地预测新的或先前未见过的数据的类标号的能力影响分类准确 1 0 分类器及其评价 率的因素有：训练数据集记录的数目、属性的数目、属性中的信息、测试数据集 记录的分布情况等 计算复杂度 计算机复杂度决定着算法执行的速度和占用的资源，它依赖于具体的实现细 节和软硬件环境由于在数据挖掘中的操作对象是海量的数据库，因而空间和时 间的复杂度将是非常重要的问题 速度 这涉及产生和使用模型的时间花费 可解释性 分类结果只有可解释性好，容易理解，才能更好地用于决策支持结果的可 解释性越好，算法的受欢迎程度越高 可伸缩性 一个模型是可伸缩的，是指在给定内存和磁盘空间等可用的系统资源的前提 下，算法的运行时间应当随数据库大小线性增加这涉及学习模型提供的理解和 洞察的层次 一稳定性 一个模型是稳定的，是指它没有随着它所针对数据的变化而过于剧烈变化 强壮性( 鲁棒性) 是指在数据集中含有噪声和空缺值的情况下，分类器正确分类数据的能力 - 成本 这涉及预测错误代价所产生的计算花费 可以认为，模型的适当性( a d e q u a c y ) 是以上指标的一种综合衡量，而侧重 点往往是因具体领域和具体用户而异例如：对于数据量特别大甚至不能存放在 内存的数据集，分类算法的可伸缩性变得尤其重要，s l i q 、s p r i n t 和r a i n t 判定 树归纳框架就是为了改善算法的可伸缩性而设计的 事实上，对于一个特定问题，如何从众多的分类器选择一个合适的，目前还 没有统一的标准，必须依赖于问题、数据和目标的特征同时，这些分类器的理 论理解还不能对实践结果做出合理的解释，很多时候必须通过对其性能的试验性 比较来指导我们的选择 2 3 1 分类器的准确率 分类准确率1 1 是指分类器正确地预测新的或先前未见过的数据( 即没有类标号 信息的元组) 的类标号的能力类似地，准确率可以用一个或多个独立于训练集 北京交通人学硕十学位论文 的检验集估计估计技术，如交叉验证和引导方法在2 4 3 以及2 4 5 小节中介绍由 于所计算的准确率仅是分类器或预测器对新的数据元组预测准确程度的估计，因 此可以计算置信限度以帮助度量这种估计 目前，分类器性能评价标准很岁5 ，6 1 但长期以来，由于训练集和测试集中的 实例都仅提供了类标签，因此预测的准确率( a c c u r a c y ) 或错误率( 即1 准确率) 就 自然地成了分类器预测性能的主要评估标准 分类准确率可以如下定义： 且 p 一善f ( g ( ) ，只) ( 2 1 ) = 堡! 、“， i d i 其中，尸表示分类准确率，d 是由有限个以( x i , y i ) 表示的样本组成的集合，x i 是数 据样本中除y ；以外的属性序列，y ，是指数据样本的类标号属性，g 表示分类器，输 出结果为预测的类标号，f ( a ，6 ) 是一个比较函数，输入为a 和b ，如果a = b ，输 出1 ；否则，输出0 2 3 2r o c 曲线及a u c “接受者操作特性( r e c e i v e ro p e r a t i n gc h a r a c t e r i s t i c ) ”的缩写r o c ，是一种用 于信号探测的术语，用来体现噪声信道击中率和错误报警之间的平衡最早在第 二次世界大战中应用于雷达信号观察能力的评价，后来使用在晶体管的相关研究， 六十年代中期用于实验心理学和心理物理学研究l u s t e d 在1 9 8 8 年首次提出了 r o c 分析可用于医疗决策评价，自从八十年代起该方法广泛用于医疗诊断性能的 评价s w e t s 7 】等人将r o c 分析法延续为对诊断系统的可视化和行为分析，扩展了 r o c 分析法的应用领域p r o v o s t 和f a w c e t t 8 1 带来的r o c 曲线分析方法引起机器 学习与数据挖掘领域的注意 理论上，与准确率评估方法相比，r o c 曲线分析【9 1 方法有以下优点： ( 1 ) 充分利用了预测得到的概率值 ( 2 ) 给出不同类的不同分布情况差别，即当是不平衡数据时，不同的数据分布， 将得到不同的分类结果，而准确率评估则默认所有的数据集都是平衡数据集 ( 3 ) 考虑了不同种类错误分类代价的不同，而准确率评估默认所有的错误代价 都是相同的，这在现实生活中是不切实际的 ( 4 ) 二类分类的r o c 曲线通过斜率反映了正例和反例之间的重要关系，同时 也反映出类的分布和代价之间的关系 ( 5 ) 可以使分类器的评估结果用曲线的形式更直观地展示在二维空问中分类 1 2 j， 分类器及其评价 器分为离散分类器( d i s c r e t ec l a s s i f i e r ) 和概率分类器( p r o b a b i l i s t i cc l a s s i f i e r ) ，前 者如决策树，后者如贝叶斯分类器和神经元网络离散分类器只预测类别，在r o c 空间中只产生一个单独的点，而概率分类器则对每个实例产生一个概率值，该值 表示实例属于正例的可能性大小r o c 分析正是利用这些概率值产生代表不同分 类器性能的r o c 曲线 a u c j 作为全局数字评估标准可以很好地完成这个任务a u c 也同样能够比 较不是相互交叉的两条r o c 曲线这个面积代表了从测试集中随机选择一个j 下例 比随机选择一个负例的概率要高很显然，如果r o c 曲线f 的a u c 值大于r o c 曲线t 的a u c 值，则f 对应分类器的平均性能优于t 但是a u c 评估方法只适 在二类分类问题，如何进行多类分类器评估是个难点 计算a u c 的方法很多【1 1 1 ，在有参数、