（计算机应用技术专业论文）针对贝叶斯分类器的数据质量的定量分析研究.pdf

i l ：京交遥大学硕士学位论文 摘要 摘要 分类是数据挖掘中非常重要的一类技术，其中的贝叶颠分类器是应用概率 统计学知识进行分类的算法一般来讲，同一个分类器针对不同的数据集，其 分类精度会有着相当大的差异这种差异部分地是由予数据集本身的质量所引 起数据质量的不闷度量方式对不同分类算法所表现出的分类性赞的差晃可篷 是非常不同的由予贝叶斯分类器原理清晰，易于分析以及高效性，故本文以贝 叶斯分类器为基础，通过设计实例选择算法来研究数据集的质量特征与评价方 法 本文在充分而深入地对相关理论，包括分类技术，数据质量，遗传算法进行 了说明和分柝之艨，介绍了w e k a 这一数据挖撅实验平台，重点分析了w e k a 下的 数据过滤器的结构和使用，以及每个予类的功能和实现原理，并对如何实现一 个过滤器进行了说明然后，采用最优保存简单遗传算法作为搜索方法。数据 质量戆定量佬指标作隽适应性函数，来设计并实现进行实例选择静算法，并提 出了称为随机采样分类测试的针对实例的数据质量指标同时使用u c i 数据集 在w e k a - 鼍z 台上实现进行了实验。其中详细地介绍了实验的过程，并展示了不同 参数设置下韵结巢，最后对结果进行比较和分析上述研究表明，该抽样方法不 仅可以在至少不降低分类器精度的前提下，大幅度的降低计算代价，而且对部 分数据集还可以有效地提高分类器的分类精度这就从实验上验证了数据集酶 质量可以以这种定量化的标准来衡量，并且这种标准可以用于数据挖掘中的数 据采集和预处理工作，作为其启发性函数进行指导，对于降低数据集规模和提 离分类糖度具有重要的实酥意义1 关键词：贝咔蓊分类器；数据质量；实锣l | 选择；数据挖掘 分类号：t p 3 0 1 6 1 本文得到国家自然科学基金项目资助( 基金项目编号：6 0 6 7 3 0 8 9 ) a b s l l 艮c t a b s t r a c t c l a s s i f i c a t i o ni so n eo f i m p o r t a n tt e c h n o l o g i e si nt h ed o m a i no fd a t am i n i n g a n d b a y e s i a nc l a s s i f i e r , w h i c hi sas u c c e s s f u li m p l e m e n to fc l a s s i f i c a t i o n ，i saa l g o r i t h m w h i c hu s ek n o w l e d g eo fs t a d c st oc l a s s i f yt h ei n s t a n c e g e n e r a l l y , t h es a l l l ec l a s s i f i e r w i l lh a v ed i f f e r e n 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 t h ed i f f e r e n c e sc o m ef r o ms o m e i n n e rc a u s eo fd a t as e t ，w h i c hc a l l e dq u a l i t yo fd a t a b a y e s i a nc l a s s i f i e ri sc h o s e na st h e b a s eo ft h ed a t aq u a l i t yw er e s e a r c h e d ，f o ri t sp r i n c i p l ei sc l e a ra n dt h eh i g hp e r f o r m a n c e o n t i m e a f t e rw i d e l yi n t r o d u c t i o na n da n a l y s i so f r e l e v a n tt h e o r i e s ，i n c l u d i n gc l a s s i f i c a t i o n ， q u a l i t yo fd a t a ，g e n e t i ca l g o r i t h m ，t h i sp a p e ri n t r o d u c et h ew e k a ，ad me x p e r i m e n t p l a t f o r m ，p a r s e dt h es t r u c t u r ea n dt h eu s a g eo fd a t af i l t e ro fw e k a ，s h o wf u n c t i o na n d p r i n c i p l eo fi t si m p l e m e n to fe v e r yc h i l d r e nc l a s so fi n s t a n c ef i l t e r , a n dd e s c r i b eh o w t o i m p l e m e n tad a t af i l t e r t h e n ，w ep u tf o r w a r da ni n s t a n c es e l e c t i o na l g o r i t h m ，w h i c h u s eg aa ss e a r c ha l g o r i t h ma n dr s c ta sh e u r i s t i cf u n c t i o n r s c t , w h i c hs t a n df o r r a n d o ms a m p l ec l a s s i f yt e s li st h eq u a n t i t yc r i t e r i o nw ep u tf o r w a r di nt h i sp a p e r w e i m p l e m e n tt h i sa l g o r i t h mi nw e k a ，a n du s eu c id a t as e tt od os o m ee x p e r i m e n t t h e p r o c e s so ft h ee x p e r i m e n ta n dt h er e s u l tu n d e rd i f f e r e n tp a r a m e t e r si sg i v e nd e t a i l e d t h e nw ec o m p a r ea n da n a l y z et h er e s u l t i ts h o w st h a t ，t h i sr e s a m p l em e t h o dc a n g r e a t l yd e c r e a s et h ec o s to fc o m p u t a t i o nu n d e rt h ec o n d i t i o nw h i c h a tl e a s tt h ea c c u r a c y i sn o tl o w e rt h a nt h eo r i g i n a l ，a n di tc a l li n c r e a s et h ea c c u r a c yf o rs o m ed a t as e t i ti s p r o v e dt h a tt h eq u a l i t yo fd a t as e tc a l lb em e a s u r eq u a n t i t yw i t ht h i sc r i t e r i o n ，w h i c h c a nb eu s e da sh e u r i s t i cf u n c t i o ni nd a t as a m p l ea n d p r e p r o c e s so fd m a n dt h i sh a sa m a r k a b l em e a n i n gi nr e d u c t i o no fd a t aa n dt h eo p t i m i z a t i o no ft h ec l a s s i f i e r k e y w o r d s ：b a y e s i a nc l a s s i f i e r ；d a t aq u a l i t y ；i n s t a n c e ss e l e c t i o n ；d a t am i n i n g c l a s s n o ：t p 3 0 1 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。 特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：鸯罐水 签字日期：3 州徭钼多日 导师签名： 乓蛎。 签字日期：删年莎月3 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成 果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研 究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 学位论文作者签名：牵名。止 签字日期：凇，拜月多日 致谢 本论文的工作是在我的导师王志海副教授的悉心指导下完成的，王志海 副教授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷 心感谢两年来王志海老师对我的关心和指导。 王志海副教授悉心指导我们完成了实验室的科研工作，在学习上和生活 上都给予了我很大的关心和帮助，在此向王志海老师表示衷心的谢意。 王志海副教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表 示衷心的感谢 在实验室工作及撰写论文期问，郭维维同学对我论文中的遗传算法研究 工作给予了热情帮助，李锦善，谢作将同学对我论文中的贝叶斯分类器的相关 性理论方面给予了很大的协助，孙培业同学对我的论文的字章架构提供了宝贵 的意见，在此向他们表达我的感激之情 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业 北京交通大学硕士学位论文第1 章引言 1 1 课题背景 第1 章引言 数据采集和存储技术的进步导致了庞大的数据库日益增多，这已经发生在 人类的大部分领域但是，数据不等于信息，更不等于知识，大量的数据堆积，直 接导致了从海量数据中寻找信息的困难大大增加那么，能否从这些数据中提 取出对数据库拥有者有价值的信息呢? 人们对于这个问题的研究以及努力成为 了一门学科，称为”数据挖掘”这里我们采用如下的数据挖掘定义： 数据挖掘就是对观测到的数据集( 一般来讲是很庞大的) 进行分析，目的是 发现未知的关系和以数据拥有者可以理解并对其有价值的新颖方式来总结数 据 数据挖掘的任务从其目标上进行分类1 9 l ，可以分为：探索性数据分析( e x p l o r a t o r yd a t aa n a l y s i s ，e d a ) ，描述建模( d e s c r i p t i v em o d e l i n g ) 预测建模( p r e d i c t i v em o d e l i n g ) ：分类和回归，寻找模式和规则，根据内容检索 分类是数据挖掘中非常重要的一种技术，分类就是在已有的数据集上，学 习一个分类函数或者构造一个分类模型( 分类器) 不同的方法构造的分类器结 构上也是不同的，主要有决策树方法，贝叶斯分类模型方法，七一近邻等几个方法 其中贝叶斯分类模型方法就是使用传统的概率理论，以贝叶斯定理为基础，建 立分类模型的一种学习方式 此外，数据挖掘一般来讲不会独立的存在，他经常处在更广阔的数据库知识 发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 也就足k d d 的背景之下k d d 过程包括 几个阶段：选择目标数据，预处理数据，转化数据( 如果需要) ，进行数据挖掘以提 取模式和关系实际上，数据的质量，也就是选择目标数据以及数据预处理的能 力以及准确度，将会极大的影响数据挖掘算法的性能以及提取出的模式和关系 的可信程度，即所谓的g i g o 一垃圾进，垃圾出( g a r b a g ei n ，g a r b a g eo u t ) 那么，如果对数据进行预处理，包括清洗或过滤，使其包含的信息或知识更 加易于学习或者更加的精练都是很有必要的所谓“数据浓缩”就是将用户难 以理解的由大量数据所构成的数据库，在一定条件下，蒸发那些无意义的数据， 使其变换为相对自然简洁的表示，以便使用户( 或计算机) 对这个数据库内容的 理解更容易【2 4 1 而数据约简中对于数据实例的选择，又可以被称为数据重采样 或着样本选择，重点在于选择更具信息的样本来提高学习的效率和精度对于 分类技术来讲，数据集的相关性的研究已经展开了很多，比如属性选择的研究 北京交通大学硕士学位论文第1 章引言 问题已经开展的比较广泛这些研究从不同的角度，比如互信息度，信息论角度 等等，也进行了很多的探索而针对分类器的数据集的相关性的另外一个方面， 即数据实例的质量问题，也有一定的研究比如a d a b o o s t i n g 等，通过改变数据集 中数据实例的权值，进而改变数据集的概率分布来提高分类器精度对数据实 例的选择，或者称之为抽样，可以极大的降低要学习数据集的规模，提高学习效 率，增高学习的精度针对贝叶斯分类器这种需要多次对数据的概率分布进行 计算或者估计的数学模型来讲，降低数据规模会对算法的性能有着显著的提升 同时由于贝叶斯分类器足建立在严谨的数学基础之上，其分类过程及训练集的 数学特征分析都可以得到充分的理论支持，可以进行更加有效的分析和研究 故本文以贝叶斯分类器为基础，通过设计实例选择算法来研究数据集的质量特 征与评价方法 1 2 本文所完成的工作 数据挖掘领域中，如何对数据进行预处理是非常重要以及复杂的问题如 何判断一个样本足合格的，或者说有质量的都是一个非常现实的问题 我们知道，所有的数据都是真实世界中某种客观存在在不同的层面和维度 的投影所得由于投影的角度以及内容不同，我们会得到多个对于同一个客观 存在进行描述的数据集，或者说对真实世界中的客观存在建立的不同数学模型 这些不同的数学模型，会存在一些比另外一些更好的逼近真实模型针对这个 问题，也就是针对贝叶斯分类器的数据质量，就是如何确定一个数据集可以构 建出一个良好的概率模型，进而可以选择所有不同数据集中，或者说一个数据 集的不同子集中，哪一个最适宜用来构建分类器本文就是以此作为出发点，进 行了如下的工作 首先，本文简要介绍了各种分类技术，然后针对贝叶斯分类器，对其原理以 及分类的过程进行了介绍分析并实现一些限制性贝叶斯分类器算法，如朴素 贝叶斯分类器，t a n 分类器，s p 分类器等，了解其具体实现以及性能之后对于 涉及到的数据质量问题进行了详细的阐述 其次，对目前现有的一些属性评价方法进行原理和实现上的说明包括c f s ， 信息增益( i n f o r g a i n ) ，和r e l i e f 等方法这些方法将用于随后设计的数据实例 选择算法，并且与本文提出的随机采样分类测试方法进行比较同时通过对于 这些属性间相关程度的评估算法的了解，也为进一步的提出评价实例问的数据 质量提供了参考 第三，由于本文只是针对数据集的一个方面提出某种验证方案，因此需要采 用同一个数据集的不同子集来测定数据间的质量不同因此本文通过设计使用 遗传算法做为搜索方法，数据质量的定量分析指标作为评价函数的实例选择算 2 北京交通大学硕士学位论文第1 章引言 法来验证数据质量在数据预处理中的指导作用所以本文还深入分析了遗传算 法的基本原理以及其数学上的证明，并针对本文所针对的对象，说明其中需要 进行修改的若干部分运算，以进行最优子集的寻找 第四，本文通过对w e k a 系统中的实例选择过滤器的组成结构和运行机制进 行深入分析和研究，来说明如何选择一个数据集的子集，或者说是如何对数据 集中的数据实例进行过滤通过这一部分的工作，使得对于具体应用中如何实 现一个实例选择工具有了一个基本的了解，这样就为实验验证实例集合之间数 据质量的差异奠定了基础 本文最主要的工作在于通过设计应用随机抽样分类测试的遗传实例选择 算法，来验证通过这种数据质量的定量化的指导作用可以进行实例的选择。获 得一个相较于其他数据实例更为优秀的一些数据实例而本文最为重要的工作。 是提出了一种称为抽样分类测试的数据质量评价方式，以定量的方式来测量数 据集针对特定贝叶斯算法的数据质量并最终通过实验验证了这一算法，即通 过使用遗传分类测试作为评价函数，以遗传算法作为搜索方式的实例选择算法， 可以选择出一个比原始数据集质量更高的数据子集 1 3 论文的组织安排 本文的组织和安排如下： 第1 章给出了课题的出发点，以及研究的问题以及其范围，叙述了数据挖掘 这门学科产生及发展的背景，和其使用的主要的一些方法，重点介绍了分类算 法的研究现状，并对本文的工作以及论文组织进行说明 第2 章作为论文的理论综述部分，首先介绍了分类器的相关知识，之后重点 介绍了贝叶斯分类器的相关理论知识并介绍了一些经典的限制性贝叶斯分类 器的算法并进行了实现然后对数据质量问题进行了理论上的综述，包括一般 意义上的数据质量问题，针对属性选择的数据质量问题，以及针对样本选择的 质量问题 第3 章介绍了使用遗传算法来进行样本选择的方法首先对遗传算法以及 其重要概念进行了说明，其后又深入分析了遗传算法的数学含义以及其收敛性 能并就遗传算法应用于数据实例选择中而产生的一些特殊的问题，做出解决 第4 章介绍了w e k a 这一开源数据挖掘平台，重点分析其中实例过滤器的组 成结构和运行机制，也就是w e k a f i l t e r 包下的针对i n s t a n c e 的包里面的内容，对 其实现和参数进行说明并阐述了如何在算法的实现中利用已有的这个平台和 借鉴其中的一些类，来实现特定的数据实例过滤器 第5 章详细说明了应用随机抽样分类测试作为适应性函数进行数据选择实 3 北京交通大学硕士学位论文第l 章引言 验的过程，并展示了实验的结果之后对实验的结果进行对比，做出分析和说明 第6 章总结全文，对本课题研究做了分析和总结，指出本课题存在的一些尚 未被解决的问题，给出了将来的研究内容和方向 4 北京交通大学硕士学位论文第2 章分类器理论和数据质量理论概述 第2 章分类器理论和数据质量理论概述 本章将针对分类技术进行详细的说明，并重点介绍贝叶斯分类器的原理及 实现之后还会对数据质量的相关理论进行概述，包括一般性的数据质量问题， 针对属性选择的数据相关度问题，以及针对实例选择的数据质量问题 2 1 分类理论 分类是数据挖掘一项十分重要的任务，许多分类方法已经被机器学习、专 家系统、统计学和神经生物学方面的研究者提出，并且在商业领域获得了比较 广泛的应用对于分类技术，研究人员提出了各种的理论来构建分类器，包括贝 叶斯分类器，决策树理论，k 。近邻分类器，支持向量机( s v m ) 等各种技术 2 1 1 分类技术概述 分类和预测是两个概念，两种方法都是数据挖掘中对数据进行分析的方法， 但分类不能等同于预测分类是预测分类标号( 或离散值) ，而预测建立连续值函 数模型可以说分类是针对离散数据的情况，而预测则是针对连续数据 分类的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每 一个类找到一种准确的描述或者模型描述常常用谓词表示由此生成的类描 述用来对未来的测试数据进行分类尽管这些未来的测试数据的类标签足未知 的，但我们仍可以由此预测这些新数据所属的类但对新数据所属的类仅仅是 预测，而不是肯定也可以由此对数据中的每一个类有更好的理解也就是说： 我们获得了对这个类的知识 分类的一般流程如下： 获取训练集，这个工作一个算法最基本的输入是一定要满足的对于分类 算法来讲，获取训练集的工作看上去也许并不是那么重要，但是实际上，数据挖 掘中大部分的工作可能都集中在数据的收集工作中数据库和e t l 工具只能是 提取出最为原始的数据，我们还需要根据特定的目的来对数据进行格式转换， 清洗，抽样，进行各式各样的预处理( p r e p r o c e s s ) ，目前在分类领域研究的比较多 的有属性选择，数据清洗等工作而且由于分类算法一般处理的都是海量的数 据，因此如何来存储或者说，如何来读取这些数据集，也是一个非常重要的课题 一个合适的数据组织和存储方式，可以极大的提高算法实现和运行的效率 5 第2 章分类器理论和数据质量理论概述 使用训练集构建分类器，建立模型是为了描述预定的数据类集或概念集 的分类器，通常这一步骤也被称作为训练( t r a i n i n g ) 或者是学习( l e a r n i n g ) 分 类算法通过分析由属性描述的训练例，训练样本或者是实例来构造模型其中 每一条训练实例属于其中一个预定义的类，由一个称作类标签属性( c l a s sl a b e l a t t r i b u t e ) 的属性确定训练数据集就是用来建立分类模型所使用的训练数据的 集合训练数据集中的单条训练数据称作训练样本，并随机地由样本群选取由 于提供了每个训练样本的类标号，所以该步也称作有监督的学习，即模型的学 习在被告知每个训练样本属于哪个类的”指导”下进行它不同于另外一种无监 督的学习，也称作聚类，此时每个样本的类标签是未知的，要学习的类的个数或 者集合也可能事先不知道，也就是没有类标签作为学习的”指导”一般的，学习 模型用决策树，分类规则或其他数学公式的形式来表示，学习模型使用的形式 不同，学习出来的分类模型性能也有差别 使用分类器，首先需要对分类器进行评估，评估一般有如下三个方面 预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测型 分类任务，目前公认的方法是n 重交叉验证法，刀一般取1 0 计算复杂度：计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘 中，由于操作对象是巨量的数据库，因此空问和时间的复杂度问题将是非 常重要的一个环节但是这个问题也与数据采集的周期有关，一个很短的 数据采集周期必然需要一个效率很高的算法来支持 模型描述的简沽度：也称分类模型的可解释性，对于描述型的分类任务，模 型描述越简洁越受欢迎，例如，采用规则表示的分类器构造法就更有用， 而s v m 和神经网络方法产生的结果就难以理解 其中，一般来讲比较关心的预测准确度评估模型的正确率或错误率有很 多种方法，保持( h o l d o u t ) 方法是一种使用类标签样本测试集的简单方法 2 2 1 这些 样本随机选取，并独立于训练样本模型在给定测试集上的准确率是被模型正确 分类的测试样本的百分比，错误率则是被模型错误分类的测试样本的百分比 对于每个测试样本，将已知的类标签与该样本的学习模型预测的结果相比较 如果模型的准确率或错误率是根据训练数据集评估，那么评估的结果可能 是乐观的，因为分类模型倾向于过度拟合数据也就是说，分类模型可能并入训 练数据中某些特别的异常，这些异常不出现在总体样本群中因此，评估分类模 型效果时，使用测试集效果会更好 但是，分类的效果一般是和数据集的特点有关，有些数据集噪声过大，有些 数据集含有较多缺损值，而有些数据集数据的分布十分地稀疏。还有些数据集 数据字段或属性间相关性强对于数据集上的属性来说，有些数据是离散的，有 6 北京交通大学硕士学位论文第2 章分类器理论和数据质量理论概述 些数据是连续的或者是混合式的总之，各种各样的数据集之间有各自的特点， 目前普遍认为不存在某种方法能适合于各种特点的数据集 2 1 2 贝叶斯分类理论 贝叶斯分类是统计学分类方法贝叶斯分类器可以预测类成员关系的可能 性，如给定样本属于一个特定类的概率目前，贝叶斯分类方法已经在文本分类， 字母识别，经济预测等领域获得了成功的应用贝叶斯方法正在以其独特的不 确定性知识表达形式，丰富的概率表达能力，综合先验知识的增量学习等特性 成为众多数据挖掘方法中最引入注目的焦点之一 贝叶斯分类器的核心是贝叶斯定理贝叶斯定理建立起了先验概率和后验 概率的联系先验概率是指根据历史资料或主观判断确定的各事件发生的概率， 由于没有经过事实证实，属于检验前的概率，所以称为先验概率先验概率分为 两类：一是客观先验概率，指利用历史资料计算得到的概率；二是主观先验概率， 指在没有历史资料或者历史资料不全的情况下，仅仅凭借主观经验判断得到的 概率 后验概率是指利用贝叶斯定理，结合调查等方式获取了新的附加信息，对先 验概率进行修正后得到的更符合实际的概率贝叶斯定理中的贝叶斯公式也称 后验公式，有几种不同的形式通常采用事件形式或随机变量形式表示其定理 形式为式2 1 所示，其中a 为非类标属性，c 为类标属性 尸( c 陋) = _ p ( a 丽l c ) p 广( c ) ( 2 1 ) 而贝叶斯分类器就以这个公式为基础，采用不同的形式和方法来构建贝叶 斯网络，对其网络结构进行估值n a i v e b a y c s 分类器就是最简单的一种贝叶斯分 类器 2 1 3 决策树分类理论 决策树分类器是以样本为基础的归纳学习分类方法将决策树转换成分类 规则比较容易其表现形式是一个树结构，其中每一个内部节点表示在一个属 性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或者是类分 布树的最顶层节点是根节点 为了对未知的样本进行分类，样本的属性值在决策树上测试，路经由根到存 放该测试样本的叶节点决策树容易将决策结果转换成分类规则基于决策树 的分类方法在训练过程中不需要用户了解很多背景知识，只要训练样本能够用 属性值的方式表达，就可以使用决策树来训练并分类 7 北京交遥大学硕士学位论文第2 章分类器理论窝数据凄量理论概述 决策树的基本算法是贪心算法，采用自顶向下的递归方式构造决策树 h u n t 等人于1 9 6 6 年提出的概念学习系统c l s 是最早的决策树算法，以后的许多 决策树算法都是对c l s 的改进或者由c l s 衍生而来q u i n l a n 于1 9 7 9 年提出了著 名的i d 3 算法| 1 7 1 。以嬲为蓝本的t 2 4 。5 算法是一个能处理连续属性的算法珏9 1 。其他 决策树方法还有i d 4 和i d 5 等 2 1 4 扣最近邻分类理论 最近邻分类基予类比学习，训练样本用n 维数值属性描述每个样本代表n 维 空闻的一个点这样，所有的训练样本都存放在n 维模式空闻中绘定一个未知样 本，扣最近邻分器搜索模式空间，找出最接近未知样本的k 个训练样本这七个训 练样本是未知样本的吏个近邻。点之阀的瞧近牲耀欧几墨德距离定义，其中两个 点x = ( 魏，娩，而) 和y = ( ) ，l ，y 2 ，弘) 的欧几里德距离是： 吠五力=弦。2 ) 未知样本被分配到k 个最近邻中最公共的类。当k = l 时，未知样本被指定到 模式空间中与之最临近的训练样本的类 最近邻分类是基于要求的或懒惰式的学习方法，即它存放所有的训练样本， 并且直到新的样本需要分类时才建立分类这与决策树，贝时斯分类等急切学 习法形成了鲜明的对比急切学习法在接受待分类的新样本之前构造出一个一 般模型当与给定的无标签的样本毯：较的可畿的邻近耆数量很大时，懒惰式学 习算法可能导致很高的计算歼销因此有时儆需要有效的索引技术懒惰式学 翔算法在训练阶段比急切式方法要快，但在分类时慢 2 1 5 支持向量机( s v m ) 理论 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 1 2 9 1 ，是最近兴起的一类薪型分类 技术统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y 或s l t ) 是一种专门研究小样本 情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论 体系，在这种体系下的统计推理规受l j 不仅考虑了对渐近性能的要求，而且追求 在现有有限信息的条件下得到最优结果vv a p n i k 等人从六七十年代开始致力 予此方螽研究，到九十年代中麓，随着其理论的不断发震和成熟，也壹于神经褥 络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的 重视 统计学习理论的一个核心概念就是v c 维w ed i m e n s i o n ) 概念，它是描述函 数集或学习机器的复杂性或者说是学习能力( c a p a c i t yo f t h em a c h i n e ) 的一个重 8 北京交通大学硕士学位论文第2 章分类器理论和数据质量理论概述 要指标，在此概念基础上发展出了一系列关于统计学习的一致性( c o n s i s t e n c y ) ， 收敛速度，推广性能( g e n e r a l i z a t i o np e r f o r m a n c e ) 等的重要结论 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学 习问题提供了一个统一的框架它能将很多现有方法纳入其中，有望帮助解决 许多原来难以解决的问题，比如神经网络结构选择问题，局部极小点问题等 同时，在这一理论基础上发展了一种新的通用学习方法一支持向量机，已 初步表现出很多优于已有方法的性能一些学者认为，s l t 和s v m 正在成为继神 经网络研究之后新的研究热点，并将推动机器学习理论和技术有重大的发展 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理 基础上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的学习精 度，a c c u r a c y ) 和学习能力( 即无错误地识别任意样本的能力) 之问寻求最佳折衷， 以期获得最好的推广能力( g e n e r a l i z a t i na b i l i t y ) 支持向量机方法的几个主要 优点有： 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不 仅仅是样本数趋于无穷大时的最优值 算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将是全局 最优点，解决了在神经网络方法中无法避免的局部极值问题 算法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r es p a c e ) ， 在高维空问中构造线性判别函数来实现原空问中的非线性判别函数，特 殊性质能保证机器有较好的推广能力，同时它巧妙地解决了维数问题，其 算法复杂度与样本维数无关 在s v m 方法中，只要定义不同的内积函数( 核函数) ，就可以实现多项式逼近， 贝叶斯分类器，径向基函数( r a d i a lb a s i cf u n c t i o n 或r b f ) 方法，多层感知器网络 等许多现有学习算法 统计学习理论从七十年代末诞生，到九十年代之前都处在初级研究和理论 准备阶段，近几年才逐渐得到重视，其本身也趋向完善，并产生了支持向量机这 一将这种理论付诸实现的有效的机器学习方法 目前，s v m 算法在模式识别，回归估计，概率密度函数估计等方面都有应用 例如，在模式识别方面，对于手写数字识别，语音识别，人脸图像识别，文章分类 等问题，s v m 算法在精度上已经超过传统的学习算法或与之不相上下 2 2 限制性贝叶斯分类器 贝叶斯分类器建立在贝叶斯统计学和贝叶斯网络方法基础上，是一种最优 9 北京交通大学硕士学位论文第2 章分类器理论和数据质量理论概述 分类器模型，它通过学习训练数据的概率分布，构造属性之间的条件依赖关系， 形成属性变量的网络结构图然而，学习无任何限制条件的贝叶斯网络是非常 耗时的，其时间复杂度为属性变量的指数级，并且空间复杂度也非常高并且已 有研究证明，学习一个最优化的贝叶斯网络是一个n p 难问题【4 】 限制性贝叶斯分类器是在贝叶斯分类器的基础上加上相应的限制条件，譬 如，n a i v e 贝叶斯分类器就是在贝叶斯网络上限制各个属性只能依赖于类属性。 而且各个属性在依赖于类属性的条件下是独立的，所以它的构造过程非常简单， 不需要结构的搜索过程，而且，在一部分特定的实际应用中表现出了相当高的 精度，因此获得了非常广泛的应用由此开始，限制性贝叶斯分类器就成了非常 热门的研究领域，众多的学习算法也相继被研究出来 n a i v e 贝叶斯分类器虽然在特定的应用中效果出众，然而由于其很强的条件 独立性假设，使得在绝大多数实际数据集中该假设难以被满足，因此分类性能 不尽如人意，因此，有学者提出适当的放宽n a i v e 贝叶斯分类器的很强的条件独 立性假设，这就产生了相应的半n a i v e 贝叶斯( s e m i n a i v e ) 分类器算法 在本部分，我们对限制贝叶斯分类器做了相应的研究工作，包括对n a i v e 贝 叶斯分类器，t a n 分类器，s p 分类器的理论基础进行分析，对其结构进行描述， 给出其算法流程，并且在实验平台上实现了这几种分类器 2 2 1 n a i v e b a y e s 分类器 n a i v e 贝叶斯分类器最早在1 9 7 3 年就被d u d a 和h a r t 两人提出，但是由于不现 实的条件独立性假设，当时并不被人们所看好，而仅仅作为复杂分类算法研究 的比较对象直到8 0 年代末，有研究人员惊奇发现n a i v e 贝叶斯分类器具有人们 当时没有预料到的优越性能，研究人员将n a i v e 贝叶斯分类器与决策树，k 最近 邻，神经网络和基于规则的学习算法等方法进行比较，发现在某些领域表现出 了非常好的性能，这也推动了朴素贝叶斯分类器的实际应用 n a i v e 贝叶斯分类器是一颗只有一层结构的树，树的根节点足类节点，也 就是类属性，其他所有的属性节点依赖于根，也就是依赖于类节点，其结构如 图2 1 所示 令随机变量c 表示一个实例的类标属性，随机变量向量a 表示其他所有的非 类标属性，令c 表示特定的一个类标签，而a 表示其他属性上的取值向量，给定一 个待分类的测试实例，那么使用n a i v e 分类器分类的规则就是： p ( c = c m = 口) = p ( a = a 币l c = 乏c ) p 广( c 一= c ) ( 2 3 ) 选择所有类标标签的分布概率中最大的那个类标标签作为待分类的测 1 0 北京交通大学硕士学位论文第2 章分类器理论和数据质量理论概述 图2 1 ：朴素贝叶斯分类器 f i g u r e2 1 ：n a i v eb a y e s i a nc l a s s i f i e r 试实例的类标值。这里的a = 日代表了一个事件，该事件为a l = a laa 2 = a 2a aa 一= a 。，并且我们做了独立性假设，认为这些概率在类条件下是独立 的，因此上式可以化为： p ( c = c 陋= 口) = ! 垒鱼【_ 三堕! 叁l 三竺 茜刍 全专手二二! 丛三二型 ( 2 4 ) p ( c = c l a = 口) = i 丢e ( c = c ) ilp ( a i = a d c = 0 ( 2 5 ) ，”2 缈 ；：i l 这个公式无论对于是训练集还是对于测试实例都是非常容易计算的，而且， 分母中的联合概率可以不用计算，这仅仅足相当于一个规范化因子，因为所有的 预测类标签都有相同的值，和具体某一个类的取值是无关的可以看出，朴素贝 叶斯分类器因为其很强的条件独立性假设，将整个分类器训练过程和对测试例 的分类过程简单化，整个过程不需要像贝叶斯网络那样搜索过程，它的结构是 固定的，而且计算过程也仅仅是几个概率值的相乘同时，存储空间的使用也很 少，只需要存储训练集上实例的条数，类的个数，在各个类标签上相应的实例个 数，各个类标签上各自属性值上的实例条数等几个频率数即可分类过程也就 是将类条件概率相乘即可，过程十分简单 n a i v ei 贝叶斯分类器对于缺损值的处理很简单，这也是朴素贝叶斯分类器在 实际数据集上应用非常广泛的一个重要原因n a i v e 贝叶斯分类器对于缺损值 的处理是忽略，因为它在训练的过程中存储的是各个类的先验概率和各个类上 各个属性上的相应取值的条件概率，根据上面的公式，忽略了一个有缺损值的 属性也就相当于少了一个联合概率的分数项，但这并不是问题，因为这个分数 项不是在一个类标签上忽略的，对于所有的类标签都会如此 北京交通大学硕士学位论文第2 章分类器理论和数据质量理论概述 n a i v e 贝叶斯分类器因为其简单而且高效的特点，在实际中大量应用，而 且n a j c v e 贝叶斯是健壮的，能够直接处理带有缺损值的数据，然而，n a i v e 贝叶斯 分类器特别强的条件独立性假设，实际的绝大多数数据集是难以满足这个特性 的，因此在部分数据集上分类效果并不好于是有研究者要部分的保留n a j c v e 贝 叶斯分类器简单高效的特定，另外适当的放宽条件独立性假设的限制，提出了一 种半n a i v e 贝叶斯分类器( s e m i n a i v e ) 的相应算法，并且其中的一些已经得到实 际应用 2 2 2t a n 分类器 1 9 9 6 年f r i e d m a n 等人提出了一种改进的朴素贝叶斯分类器，称之为树扩张 型朴素贝叶斯( t r e ea u g m e n t e dn a i v eb a y e s ) 分类器【8 j ，它适当的放宽了n 飙贝 叶斯很强的条件独立性假设，提高了分类性能t a n 分类器的结构如图2 2 表示： 图2 2 ：t a n 分类器 f i g u r e2 2 ：t a nc l a s s i f i e r 从图上可以看出，t a n 分类器各个属性依赖的除了依赖于类属性之外，还 依赖其他至多一个非类属性节点，而且，所有的非类属性构成一颗生成树，其根 节点只依赖于类属性节点，其他非根节点都依赖一个非类属性如果属性个数 有n 个，那么边的个数有n 1 条由于每一个属性都是依赖于类属性节点的，实际 上，整个结构也就这颗树另外再加上类属性构成的，除开根节点之外各个属性 节点依赖了其它一个属性节点，这放松了朴素贝叶斯分类器中的很强的条件独 立性假设：各个属性节点仅仅依赖于类属性节点，而且在类属性节点下各个属 性之间是独立的，放宽到各个属性节点依赖于除类属性之外的其他一个属性节 点，各个属性节点在满足这个条件的基础上，是相互独立的 此时，分类时的情况就需要被修改，此时的分类公式就成为： 即= c l a = a ，= 志只曲跗一陆鲥刚力g 6 ， 1 2 。、拶 缈 、。气 。，矜。 北京交通大学硕士学位论文第2 章分类器理论和数据质量理论概述 其中，a ，是被所有其他非类标属性依赖的属性公式和n a i v e 贝叶斯中不同 的就是依赖的条件中多了一个属性，而不仅仅是原来的类属性正是这个多出 来的依赖属性，使得n a y v e 贝叶斯的条件独立性假设被放宽 这样，就产生了一个问题，如何确定属性之间的依赖关系? c h o w 和l i u ， 在1 9 6 8 年提出的互信息( m u t u a li n f o m a t i o n ) 的概念。也许可以表示这个关系 f r i e d m a n 等人正是采用了互信息度来确定属性的依赖关系互信息度的定义如 下： ，；玛) = p d ( 麓，劫i 。p d p ( d 墨( x ) p d i , x ( j 历) ( 2 7 ) x i ：x l o 由于分类器需要在条件下工作，因此f r i e d m a n 等人扩展了互信息度的概念， 提出了条件互信息度，表示两个属性在依赖与类标属性的条件下的相互联系程 度 髓；w ) _ 。善p d ( x i , x j , c ) i 昭丽e o 厩( x i , x 丽l c ) ( 2 8 ) 通过计算互信息度，建立互信息度矩阵，可以在属性问建立一个无向全连通 图，其边的权值就是条件互信息度构建t a n 分类器模型结果，关键就是如何构 建依赖的树结构因此，问题就已经成为，如果在一个拥有权值的无向全连通图 中寻找一颗最大生成树，这个问题在数据结构方面已经得到了非常圆满的解决 当生成一颗最大生成树后，随机选择一个节点作为根节点，建立依赖关系有些 研究者也提出，选择不同的节点作为根节点可能会导致不同的性能，但是具体 的选择标准未知 t a n 分类器构造好之后就能用于分类，由于它削弱了很强的条件独立性假 设，使得属性节点不仅仅只依赖于类属性节点，还能依赖于其他的一个属性节 点，因此更能符合实际的数据集的情况，从而提高了分类器的分类效果，目前， t a n 分类器是公认的对朴素贝叶斯改进最好的分类器 2 2 3s p 分类器 s p 英文的全称为s u p e r p a r e n l 该方法是为了降低爬山法的时间复杂度而提 出的，而且其分类精度和爬山法相近由于爬山法是从整个属性生成的完全无向 图上找能提高分类性能的边，每找一条都需要用交叉验证法评价分类器性能，从 而使得时间复杂度为d ( 3 ) ，s p 算法，在取得性能相同的前提下，降低了分类器的 训练时间复杂度该算法也是i 扫k e o g h 和p a z z a n i 等人提出【1 5 1 s p 算法比起爬山法是一种更有效的启发式搜索算法，分类精度和爬山法差 1 3 就京交逶大学颈圭学健论文第2 章分类豢理论和数据质量理论概述 不多，但是搜索代价减小了爬山法是每一次都尝试着加进一条最佳的边，该边 的加入能够使