（计算机应用技术专业论文）面向朴素贝叶斯算法的离散化方法研究.pdf

摘要 摘要 在数据挖掘领域中，有很多算法只能处理定性属性朴素贝叶斯分类算法在 处理定量属性时作了正态分布的假设然而，这一假设与实际常常是相违背的， 从而严重制约了朴素贝叶斯算法的分类性能因此，在运用分类算法之前，通常 需要离散化离散化是数据挖掘领域的一个重要方面，它是一个从定量数据到定 性数据的转化过程，它不仅能够有效地提高分类器的分类精度及效率，也能够使 更多的数据挖掘算法应用于含有定量属性的数据集中，具有重要的现实意义及研 究价值 首先，本文对数据的分类与度量进行了分析然后，阐述了数据挖掘和分类 的相关理论，介绍了朴素贝叶斯算法及其定量属性的处理方法接着分析了离散 化的研究现状，重点指出了离散化对朴素贝叶斯算法的有效性在深入研究熵最 小离散化方法( e m d ) 和m d l 准则的基础上，分析了e m d 方法的缺陷，提出了 一种基于m d l 的多元离散化方法m u l t i e m d 该方法借鉴了e m d 方法中寻找切 点的方法，在评价切点时使用了一种多元的m d l 准则，该准则综合考虑了数据集 中所有数值型属性的作用，从而对切点的评价更可靠本文还深入研究了比例离 散化方法( p k i ) ，将e m d 方法与p k i 方法相结合，使用熵最小方法来寻找切点， 使用p k i 方法计算离散化区间数量，提出了比例熵最小离散化方法p e m d 最后， 介绍了数据挖掘平台w e k a 系统的概况及其架构，在此平台上实现了m u l t i e m d 和p e m d 方法，并通过实验比较了e m d ，m u t l i e m d ，p k i 以及p e m d 方法实 验结果与分析表明，在这4 个方法之中，m u l t i e m d 比e m d 方法具有更好的离散 化性能，p e m d 方法的离散化效果则同时超越了e m d 和p k i 方法 关键词：数据挖掘；离散化；分类；朴素贝叶斯；m d l 分类号：t p 3 0 1 6 本文得剑国家自然科学基金项目资助( 基金项目编号：6 0 6 7 3 0 8 9 ) a b s t r a c t a bs t r a c t i nt h ed o m a i no fd a t am i n i n g ，m a n ya l g o r i t h m sc a no n l yh a n d l eq u a l i t a t i v e a t t r i b u t e s n a i v eb a y e sl e a r n i n ga l g o r i t h ma s s u m e st h a tt h ev a l u e so faq u a n t i t a t i v e a t t r i b u t ea r ed i s t r i b u t e di nan o r m a ld i s t r i b u t i o nw h e np r o c e s s i n gq u a n t i t a t i v ea t t r i b u t e s h o w e v e r , t h i sa s s u m p t i o ni sa l w a y sv i o l a t e di nr e a l - w o r l dd a t a s e t s ，s ot h ep e r f o r m a n c e o fn a i v eb a y e si ss e v e r e l yr e s t r i c t e d t h e r e f o r e ，ap r e p r o c e s ss t e pc a l l e dd i s c r e t i z a t i o n i sa l w a y sr e q u i r e di nt h eu s eo fc l a s s i f i c a t i o n d i s c r e t i z a t i o ni sa ni m p o r t a n ta s p e c to f d a t am i n i n gw h i c hi sad a t at r a n s f o r m a t i o np r o c e s sf r o mq u a l i t a t i v et oq u a n t i t a t i v ed a t a d i s c r e t i z a t i o nc a nn o to n l yi m p r o v et h ea c c u r a c ya n de f f i c e n c yo ft h ec l a s s i f i c a t i o n ，b u t a l s oe n a b l em o r ed a t am i n i n ga l g o r i t h m st ob ea p p l i e dt od a t a s e t sw h i c hc o n t a i n q u a n t i t a t i v ea t t r i b u t e s s od i s c r e t i z a t i o n i sw i t hi m p o r t a n tr e a l i s t i cs i g n i f i c a n c ea n d r e s e a r c hv a l u e i nt h i sp a p e r , w ef i r s tc l a s s i f yd a t a t h e nw ee x p o u n dr e l e v a n tt h e o r i 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 ，a n dw e a l s oh a v ead e e pr e s e a r c hi nn a i v eb a y e s i a n a l g o r i t h ma n dt h em e t h o dt od e a lw i t hq u a n t i t a t i v ea t t r i b u t e si nn a i v eb a y e sc l a s s i f i e r s e c o n d l y , w ea n a l y z et h ec u r r e n tr e s e a r c hs i t u a t i o na b o u td i s c r e t i z a t i o n ，t h e nw ep o i n t o u te s p e c i a l l yt h a td i s c r e t i z a t i o ni se f f e c t i v ef o rn a i v eb a y e s w ep r o p o s ean e wm d l b a s e dd i s c r e t em e t h o dn a m e dm u l t i e m da f t e rr e s e a r c h i n ge m dm e t h o da n dm d l p r i n c i p l e m u l t i - e m di sam u l t i v a r i a n ta n ds u p e r v i s e dd i s c r e t em e t h o d m u l t i e m d a l g o r i t h mh a st h es a m ew a y o ff i n d i n go u tt h eb e s tc u tp o i n tb yf i n d i n gt h em i n i m u m c u tp o i n te n t r o p yw h i c hi su s e di ne m da l g o r i t h m ，a n di tu s e sam u l t i v a r i a n tm d l p r i n c i p l et oe v a l u a t eac u tp o i n tb yt a k i n gt h ee f f e c t o fa l ln u m e r i ca t t r i b u t e si nt h e d a t a s e ti n t oa c c o u n t ，s oi tl e a d st oam o r er e l i a b l ee v a l u a t i o n m o r e o v e r , w es t u d y a n o t h e ru n s u p e r v i s e dd i s c r e t em e t h o dc a l l e dp k ii ng r e a td e p t h t h e n ，w ec o m b i n e e m da n dp k im e t h o d sb yu s i n ge m d sm e t h o dt os e a r c hf o rt h eb e s tc u tp o i n ta n d u s i n gp k i sm e t h o d t oc a l c u l a t et h eq u a n t i t yo fd i s c r e t ei n t e r v a l s ，a n dt h i sw o r kl e a dt o p e m da l g o r i t h m f i n a l l y , t h ec o m p a r i s o na m o n gt h e s em e t h o d si sc o n d u c t e di nw e k a p l a t f o r ma n dt h ee x p e r i m e n t a lr e s u l ts h o w st h a tt h em u l t i - e m da l g o r i t h mh a sa b e t t e r p e r f o r m a n c et h a ne m da l g o r i t h m ，a n dp e m d m e t h o di sb e t t e rt h a ne m da n dp k i k e y w o r d s ：d a t am i n i n g ；d i s c r e t i z a t i o n ；c l a s s i f i c a t i o n ；n a i v eb a y e s ；m d l c l a s s n o ：t p 3 0 1 6 v 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国 家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者繇泺气乍碍聊躲立点髟 签字日期：。一譬年月弓1 7 1签字同期：z 棚g 年歹月弓f i 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导l i l 于l 导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名： 和 下) 埒签字日期： 矗一g 年月多 日 致谢 本论文的工作是在我尊敬的导师王志海教授的悉心指导下完成的，王志海教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响在此衷心感谢两 年来王志海老师对我的关心和指导 衷心感谢黄厚宽和田盛丰教授，两位教授宽广豁达的长者风范以及严谨的治 学态度始终让我深深地敬仰他们在此期间对我的关心和鼓励让我深受感动 瞿有利老师对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢 在实验室工作及撰写论文期间，季长冰、李锦善、郭维维、孙培业等同学对 我论文中的数据挖掘研究工作给予了热情帮助，在此向他们表达我的感激之情 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业 最后，衷心感谢在百忙之中审阅论文的各位老师和专家，恳请各位老师多多 批评指正，并提出宝贵的意见 引言 1 1 课题背景 1 引言 在当今这样的一个信息时代里，信息量每天以爆炸性的速度增长，有人预测 全球的数据存储量每隔2 0 个月要增长一倍在如此海量的数据背后隐含了很多潜 在有价值的信息，为了摆脱数据丰富，知识贫乏的窘境，能够从海量数据中发现 知识和学习知识，人们迫切需要一种能够从这些数据中自动抽取知识的学习方 法在计算机技术迅猛发展的推动下，数据挖掘这门新兴科学应运而生 数据挖掘是一个多学科交叉领域，涉及到数据库技术、机器学习、数理统计 学、神经网络、模式识别、知识库信息提取、高性能计算等诸多领域数据挖掘 所处理的信息都是现实世界人们在各种活动中产生出来的，数据的存在形式是多 种多样的，如有些数据是数字，有些则是字符串人们将数据统分为定性数据和 定量数据两种类型定性数据是一种泛化的数据，而定量数据是一种量化的数 据这两种数据的性质决定了它们各自需要有不同的处理方法然而，研究发现 对于含信息量更加丰富的定量数据却更加难以处理数据挖掘发展至今，很多算 法只能处理定性数据或者对定性数据的学习效果比定量数据的更好因此，人们 在应用数据挖掘算法前，首先需要一种能够将定量数据转化为定性数据而又不能 有过多的信息量丢失的方法，这就是离散化方法 离散化过程作为数据预处理过程中的一个方面，在数据挖掘和知识发现领域 中发挥着重要的作用它不仅能让更多的数据挖掘算法适用于各种数据集，而且 也能明显改善这些算法的性能目前已有很多离散化方法被研究出来，包括等宽 离散化方法【l 2 ，3 1 、等频离散化方法f l 3 ，4 ，5 1 、固定频率离散化方澍3 1 、比例离散化方 法【6 1 、熵最小离散化方法【7 ，8 1 、i d 3 离散化方法【3 一、基于聚类的离散化方澍1 们、相 交离散化方澍4 1 、迭代改进离散化方法【i l 】、1 r 离散化方法【2 ，1 2 】等等这些离散化 方法各有优劣，运用于不同的学习策略上亦各有好坏 朴素贝叶斯算法是数据挖掘中基于统计理论的一个分类算法，被广泛应用于 分类学习中朴素贝叶斯分类算法具有简单性、高效性、鲁棒性和支持可增量学 习等特性，因而它长期以来都是信息检索中的核心技术，并且它在医疗疹断、邮 件过滤和模式识别中也得到非常广泛的应用朴素贝叶斯分类方法本身能够处理 定量数据，但是它对这些定量数据作了高斯分布假设大量的实验证明对现实世 界中的数据作这种假设是危险的，因而不能得到很好的分类性能研究表明对贝 北京交通人学硕 学位论文 叶斯分类器进行离散化处理是有效的，并且也证明了如果知道数据本身真实的概 率分布，经过离散化处理后能够得到与该分布相同的概率估计【13 1 再者，由于对 定量数据进行概率估计的计算量相当大，离敞化也能够在很大程度上提高朴素贝 叶斯算法的学习效率，降低时间复杂度 1 2 本文所完成的工作 在数据挖掘领域中，分类足一种非常重要的技术朴素贝叶斯算法的简单性、 高效性和鲁棒性等特性使得它在许多领域中得到了非常广泛的应用朴素贝叶斯 分类算法在处理定量属性时作了j 下态分布假设然而，这一假设与实际常常是相 违背的，从而严重制约了朴素贝叶斯算法的分类性能使用基于核函数的概率密 度估计方法虽然可以处理这一问题，但是由于计算成本太高，不能很好地适用于 朴素贝叶斯算法因此，在运用分类算法之前，通常需要离散化 离散化过程是一个从定量数据到定性数据的数据转化过程，它一直存在于机 器学习与数据挖掘领域中，作为数据预处理中的一个重要内容离敞化不仅能使 更多的分类算法应用于定量属性，而且也能够大大提高分类精度和学习效率离 散化作为分类算法对定量属性处理的一种有效方法，其性能的好坏将直接影响到 分类算法的性能因此，对离散化的研究具有重要的现实意义 在上述背景之下，本文主要完成了以下几方面的工作： 首先，对数据的分类与度量进行了分析将数据分为定量数据与定性数据， 也从度量标度级别上将数据分成四种不同标度级别 其次，概述了数据挖掘相关理论，包括数据挖掘的概念、功能、方法以及 数据挖掘中的数据预处理 接着，概述了分类技术，重点研究了朴素贝叶斯分类器，并分析了朴素贝 叶斯算法中定量属性的处理方法，指出离散化是一种更有效的途径 第四，对离散化研究现状作了深入的分析，介绍了离散化概念、意义、评 价标准以及离散化方法分类，并理论证明了离散化对朴素贝叶斯算法的有 效性 第五，讨论了著名的数据挖掘开源平台w e k a 系统，主要介绍了w e k a 的 背景、功能、w e k a 中的数据格式、设计框架总体结构及其包结构，并着 重分析了w e k a 中数据预处理的相关内容以及离散化在w e k a 中的实现 进而，重点研究了信息论中熵的理论，数据压缩，编码理论以及m d l 准 则，在此基础之上深入剖析了熵最小离散化方法( e m d ) ，介绍了e m d 方法的思想及其m d l 准则通过对e m d 方法的研究，指出了该方法存 引言 在的缺陷，提出了- j o e 基于m d l 准则的、多元的、有监督的离散化方法： 多元熵最小离散化方法( m u l t i v a r i a n te n t r o p ym i n i m u md i s c r e t i z a t i o n ) ，简 称为m u l t i e m d 该方法中使用的m d l 准则是综合考虑训练集中所有数 值型属性的相互作用，并且离散化过程也不再是依次只在单个属性上进 行，而是同时在所有的数值型属性上进行的 m u l t i e m d 方法虽然对e m d 方法作出了很大的改进，但m u l t i e m d 方法 还存在着一些不足之处，有待进一步的研究在研究了几种面向朴素贝叶 斯的无监督离散化方法之后，本文又提出了一种基于e m d 方法和比例离 散化方法( p k i ) 的离散化方法：比例熵最小离散化方法( p r o p o r t i o n a l e n t r o p ym i n i m u md i s c r e t i z a t i o n ) ，简称为p e m d p e m d 方法结合了e m d 和p k i 方法中各自的长处，一方面使用e m d 方法来寻找切点，另一方面 使用p k i 方法来计算离散化区间数量 最后，本文通过实验将e m d ，p k i ，m u l t i e m d 以及p e m d 方法进行比 较，证明了m u l t i e m d 比e m d 方法具有更好的离散化性能，p e m d 方法 结合了e m d 和p k i 方法各自的优点，并同时超越了e m d 和p k i 方法， 表现出较佳的离散化性能 1 3 论文的组织安排 本文的主要框架和结构如下： 第l 章介绍了课题的出发点和研究的问题及范围，分析了数据挖掘面临的问 题及离散化的必要性，并介绍了本文所完成的工作 第2 章介绍了与课题相关的一些理论背景，包括数据的分析与分类，数据挖 掘的相关知识，分类理论以及离散化的研究现状 第3 章介绍了著名的数据挖掘歼源软件w e k a 系统，分析了w e k a 的架构着 重分析了w e k a 中离散化的相关内容，介绍了几种离散化方法在w e k a 下的实现 第4 章具体分析了e m d 离散化方法的相关理论及算法流程，指出e m d 方法 的缺点，并针对其缺点提出了一种改进方法：m u t l i e m d 方法 第5 章分析了p k i 离散化方法与e m d 离散化方法，结合这两种方法的优点提 出了比例熵最小离散化方法( p e m d ) 第6 章通过在w e k a 平台下进行实验，证明了m u t l i e m d 和p e m d 方法具有 良好的离散化性能 第7 章总结全文，对本课题研究做了分析和总结，并给出了本课题将来的研 究内容和方向 面向分类学习的离散化方法综述 2 面向分类学习的离散化方法综述 数据可以分为不同的类型，离散化为不同类型的数据进行转换提供了一个途 径，是数据挖掘领域中数据预处理的一个方面本章足对离散化方法的综述，并 介绍了其相关背景理论：数据、数据挖掘和分类 2 1 数据 数据来源于人们对客观世界的认识，它作为信息的一个载体，其表现形式是 多种多样的不同形式的数据所含有的信息量是各不相同的，它反映了人们对客 观世界认识程度的不同如描述一个人的身高时，可以用1 7 5 c m 、1 7 5 5 c r n 和 1 7 5 5 5 c m 等数字来描述这三个数虽然都是实数，但所包含的信息量是不一样 的随着精度越来越高说明人们对一个人身高的认识越来越清楚，因而包含的信 息量也越来越丰富而且，这三个值之间是可以比较大小的，我们称它们为定量 数据我们也可以用“高”、“中等”和“矮”来描述一个人的身高这三个值之 间本身并没有一个大小比较的概念，我们只能说它们所表示的含意即身高，是越 来越小的人们对“高”的认识是很模糊的，根据人认识的不同对“高”会有不 同的理解有的人可能会认为1 7 5 c m 以上才算是高，而有的人可以会认为1 8 0 c m 以上才算是高因此“高”是一个很泛化的数据，它是定量数据在一个区间内的 集合从“高”和“1 7 5 ”这两个数据哩所反映出来的人们对一个人身高的认识程 度是不一样的，“1 7 5 ”比“高”更能反映出一个人的身高，所以这两个数据所含 的信息量也是不一样的，“1 7 5 ”比“高”含有更丰富的信息量我们称“高”、“中 等”和“矮”为三个定性数据 按照统计学的观点，有两种方法来区分数据类型数据可以分为定量数据和 定性数据，数据也可以分为不同的度量标度级别i l 4 2 1 1 定性与定量数据 定性数据也叫做类别数据，它们可以根据某些特性被分成不同的类别有时 可以对定性数据进行有意义的排序，但是不能对定性数据进行算术运算，如加、 减、乘、除、取余等典型的定性数据有：人的血型有a 、b 、a b 、o ；人的性别 有男、女；天气有晴、阴、雨等 定量数据也是数值数据可以对定量数据进行有序排列，也可以对它们进行 北京交通人学硕- 学位论文 算术运算定量数据可以进一步划分为离散型数据和连续型数据 离散型数据不能取遍数轴上的任意值，而只能取在一些特定点上如一个班 级学生的人数，一个国家城市的个数等 连续型数据可以取遍数轴上的任意值典型的有一个人的身高取值，一个物 体的重量取值，一根棒子的长度耿值等等 2 1 2 度量标度级别 数据也可以按照分类、计算和度量方法分为四种度量标度级别：名称型 ( n o m i n a l ) 、顺序型( o r d i n a l ) 、区间型( i n t e r v a l ) 和比例型( r a t i o ) 名称型数据之间是相互排斥、没有重叠的，并且是没有大小关系的如人的 血型a 、b 、a b 、o 这四个值 顺序型数据之间是有序的，但是它们之间的差异不能由数值来度量如对学 生的价评有不通过、通过、好、非常好 区间型数据之问也是有序的，并且数据之间的差异是可以由数值来衡量的但 是，“0 ”在区间型数据中不表示“没有”，这早的“0 ”与其在算术运算中的意义 不同如i q 测试中结果为“0 不表示人没有智商 比例型数据具有区间型数据的所有性质，而且“0 ”在比例型数据中的意义与 算术运算中的意义一样表示“没有”如一个家庭的人口数 可以看出，这四种数据的度量标度级别是越来越高的名称型数据的度量标 度级别最低，比例型数据的度量标度级别最高从包含信息量的角度来说名称型 数据所含的信息量最少，比例型数据所含的信息量最多因此，将度量标度级别 高的数据转化为度量标度级别低的数据会导致信息量的丢失 将以上两种分类方法综合起来，可以看出：定性数据指的是名称型数据和顺 序型数据；定量数据指的是区间型数据和比例型数据，所以将定量数据转化为定 性数据也将会导致信息量的丢失 2 2 数据挖掘 2 2 1 数据挖掘的概念 近十几年，随着科学技术飞速的发展，经济和社会都取得了极大的进步与 此同时，在各个领域产生了大量的数据，如人类对太空的探索，银行每天的巨额 交易数据等等显然在这些海量数据背后隐含着丰富的有用信息，但是这些大规 6 面向分类学习的离散化方法综述 模的信息在给人们的生活、工作带来方便的同时也带来许多问题例如，信息过 量，难以消化；信息真假难以辩识；信息安全难以保证；信息方式不一致，难以 统一处理等等计算机技术的迅速发展使得处理数据成为可能，这就推动了数据 库技术的极大发展但是面对如潮水般不断增加的数据，人们不再满足于数据库 的查询功能，提出了更深层次的问题：能否从数据中提取信息或者知识为决策服 务这个问题就数据库技术而言已经显得无能为力了同样，传统的统计技术也 面临了极大的挑战，这就急需有新的方法来处理这些海量般的数据于是，人们 迫切需要一种能够从这些数据中自动抽取知识的学习方法在超大规模数据库的 出现、计算机技术的迅猛发展和较难的统计方法的运用等冈素激发下，数据挖掘 这门新兴科学应运而生 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数 据中提取隐含在其中的、人们事先不知道的但又是潜在有用的信息和知识的过程 【1 5 1 它是一类深层次的数据分析方法数据挖掘是揭示存在于数据罩的模式及数 据间关系的学科，它强调对大量观测到的数据库的处理它是涉及数据库管理、 人工智能、机器学习、模式识别及数据可视化等学科的边缘学科用统计的观点 看，它可以看成是通过计算机对大量复杂数据集的自动探索性分析该领域对商 业、工业及科学研究都有极大的影响，且提供了大量为促使新方法的发展而进行 的研究工作在现代社会，各行各业均实现了业务自动化，商业领域产生了大量 的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯机会的商业 运作而产生的分析这些数据不再是单纯为了研究的需要，更重要的是为商业决 策提供真正有价值的信息，进而提高管理水平、生产效率和利润等等但所有企 业面临的一个共同的问题是：企业数据量非常大，而其中真j f 对自己有价值的信 息却很少因此，从大量的数据中经过深层次分析获得有利于商业运作、提高竞 争力的信息很有必要 2 2 2 数据挖掘的功能与方法 数据挖掘通过预测未来趋势及行为做出前瞻的、基于知识的决策数据挖掘 的目标是从数据库中发现隐含的、有意义的知识它综合了各门学科技术，有很 多的功能【1 5 】，主要有关联分析、聚类分析、分类、预测、时序模式和偏差分析等 1 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 数据关联是数据库中存在的一类重要的可被发现的知识，它是由r a k e s h a p w a l 等人首先提出的若两个或多个变量的取值之间存在某种规律性，就称为关联关 联可分为简单关联、时间关联、因果关联等关联分析的目的是找出数据库中隐 7 北京交通人学硕卜学位论文 藏的关联网有时并不知道数据库中数据的关联函数，即使知道也是不确定的因 此，一般用支持度和可信度两个阈值来度量关联规则的相关性，还不断引入兴趣 度、相关性等参数，使得所挖掘的规则更符合需求 2 ) 聚类分析( c l u s t e r i n g ) 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同 类中的数据彼此相异聚类分析可以建立宏观的概念，发现数据的分布模式，以 及数据属性之间可能的相互关系 3 ) 分类( c l a s s i f i c a t i o n ) 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类 的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示分类是 利用训练数据集通过一定的算法而求得分类规则，它可被用于规则描述和预测 4 ) 预测( p r e d i c a t i o n ) 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种 类及特征进行预测预测关心的是精度和不确定性，通常用预测方差来度量 5 ) 时序模式( t i m e s e r i e sp a t t e m ) 时序模式是指通过时间序列搜索出的重复发生概率较高的模式与回归一样， 它也是用已知的数据预测未来的值，但这些数据的区别是变量所处时问不同 6 ) 偏差分析( d e v i a t i o n ) 数据库中的数据常有一些异常记录，发现数据库中存在的异常情况是非常重 要并且很有意义的异常包括很多潜在的知识，如分类中的反常实例、不满足规 则的特例、观测结果与模型预测值的偏差、量值随时间变化等等偏差检验的基 本方法就是寻找观察结果与参照之问的差别 随着研究的不断深入，人们己提出很多种用于数据挖掘的方法，主要有神经 网络、遗传算法、决策树、粗糙集、统计学习方法以及模糊集方法 1 ) 神经网络方法 由于神经网络本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和 高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关 注典型的神经网络模型主要分3 大类：以感知机、b p 反向传播模型和函数型网 络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以h o p f i e l d 的 离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网络 模型；以a r t 模型、k o h o l o n 模型为代表的，用于聚类的自组织映射方法神经网 络方法的缺点是“黑箱”性，人们难以理解网络的学习和决策过程 2 1 遗传算法 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，也是一种仿 面向分类学习的离散化方法综述 生全局优化方法遗传算法在求解过程中，通过最优解的选择和彼此组合，可以 期望解的集合将会越来越好在数据挖掘中，遗传算法能够用来形成变量问的依 赖关系假设遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它在 数据挖掘中被加以应用 3 ) 决策树方法 决策树是一种常用于预测模型的算法，它通过将大量数据有目的地分类，从 中找到一些有价值的，潜在的规则，然后利用这些规则对未知数据进行预测它 的主要优点是描述简单，分类速度快，特别适合大规模的数据处理构建决策树 的方法有很多，其中最具有代表性的是c a r t 和c 4 5 算法 4 1 粗糙集方法 粗糙集理论是一种研究不精确、不确定知识的数学工具粗糙集方法有几个 优点：不需要给出额外信息；简化输入信息的表达空问；算法简单，易于操作粗 糙集处理的对象是类似二维关系表的决策表目前成熟的关系数据库管理系统和 新发展起来的数据仓库管理系统，为基于粗糙集的数据挖掘奠定了坚实的基础但 粗糙集的数学基础是集合论，难以直接处理连续的属性而现实信息表中连续属 性是普遍存在的，因此连续属性的离散化是制约粗糙集理论实用化的难点 5 ) 统计学习方法 统计方法是从事物外在数量的表现去推断该事物可能的规律传统的统计方 法在解决机器学习问题中起着基础性的作用，主要研究渐近理论常见的方法有 回归分析、聚类分析、主元分析以及相关分析等在传统的统计学习方法基础上， 已经形成了多种新型的数据分析方法，如基于范例的推理方法，朴素贝叶斯和贝 叶斯网络等新兴的支持向量机则是建立在计算学习理论的结构风险最小化原则 之上，主要针对两类分类问题在高维空间中寻找一个超平面作为分类的分割，以 保证最小分类错误率，其重要优势在于可处理线性不可分情况贝叶斯网络是由 r h o w a r d 和j m a t h e s o n 于1 9 8 1 年提出的，它是一种概率推理方法，它能从不完 全、不精确和不确定的知识和信息中做出推理，可以处理不完整和带有噪音的数 据集，解决了数据问不一致和相互独立的问题朴素贝叶斯算法是一种最简单的 贝叶斯网络，它通过样本的属性值计算实例属于某一个类的可能性，然后将样本 归属到最有可能的类中朴素贝叶斯分类算法具有简单性、高效性、鲁棒性和支 持可增量学习等特性 6 ) 模糊集方法 模糊集方法利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模 式识别和模糊聚类分析系统的复杂性越高，模糊性越强，一般模糊集合理论是 用隶属度来刻画模糊事物的办此亦彼性的 9 北京交通人学硕十学位论文 2 2 3 数据挖掘中数据的预处理 海量数据中既有噪声数据和缺损数据，又存在数据不一致现象，这些因素都 会影响人们对数据信息的使用因此，在执行数据挖掘算法前有必要对数掘进行 预处理，通过提取高质量数据的手段来达到高质量的挖掘结果的目的，而且数据 预处理也能使数据挖掘过程更有效、更容易数据挖掘中数据预处理包括以下几 个方面： 1 ) 数据集成( d a t ai n t e g r a t i o n ) 数据集成主要是从不同的数据源中选取所需要的数据，并进行统一的存储， 而且需要消除其中的不一致性数据集成是数据仓库系统中非常重要的一个特征， 建立数据仓库的过程实际上就是数据集成该部分主要涉及到选择数据、处理冲 突数据以及不一致的数据 2 ) 数据清洗( d a t ac l e a r i n g ) 数据清洗的目的是消除数据源中的噪声数据和重复数据、处理遗漏数据和清 洗脏数据数据清洗可以提高数据的质量，从而得到更准确的挖掘效果数据清 洗还可以消除数据的不一致性 3 ) 数据变换( d a t at r a n s f o r m a t i o n ) 数据变换主要是将数据转换为适合挖掘的数据形式数据变换主要有两方面 的原凶：一是现有的数据不能满足分析需要而进行数据变换；二是应用具体数据 挖掘算法的需要因为不同的算法对数据往往也有不同的要求，所以为了使计算 结果更高效更准确需要对数据进行相应的转换数据变换主要包括离散化、平滑、 聚集、数据概化、规范化以及特征构造( 属性构造) 4 ) 数据归约( d a t ar e d u c t i o n ) 数据源中的有些属性对挖掘是没有意义的，加入这些属性会大大影响挖掘效 率，甚至可能会降低挖掘结果因此，需要对数据源进行有效的数据缩减数据 归约主要包括数据立方体聚集、维规约、数据压缩以及数值规约 2 3 分类 分类是数据挖掘中一项十分重要的任务，许多分类方法已经被机器学习、专 家系统、统计学和神经生物学方面的研究者提出，并且在商、l k 领域获得了比较广 泛的应用 1 0 面向分类学习的离散化方法综述 2 3 1 分类概述 分类学习就是通过分析训练集中的数据，为每个类别建立分类分析模型，然 后利用这个分类分析模型对其他未知类别的数据进行分类分类的目的是学会一 个分类函数或分类模型( 也常常称作分类器) ，该模型能够把数据库中的数据项映 射到给定类别集合中的某一个类别它与预测是两个不同的技术预测是构造和 使用模型评估无标签样本类，或评估给定样本可能具有的属性值或区间分类与 预测相比，两者具有相同点和不同点相同点是两者都需要先构建模型，然后用 构建的模型来估计未知值二者的区别在于分类主要是用于预测离散的类标签， 而预测则是用来估计连续值 分类问题可以描述为：数据是一张标准二维关系表，它包含条记录，每条 记录通常称作元组( t u p l e ) 、实例( i n s t a n c e ) 或样本( e x a m p l e ) 每一个实例由一 个或多个度量标准描述，这种度量标准称作属性( a t t r i b u t e ) 每个属性有一个合法 的取值范围，称作该属性的域( d o m a i n ) 根据属性的域可以将属性分为两类：名 称型属性( n o m i n a l ) 和数值型属性( n u m e r i c ) 若属性域是实数域，则称该属性 为数值型属性，若属性域是有限的，那么称该属性为名称型属性这些属性中有 一个特殊的属性为类属性( c l a s sa t t r i b u t e ) ，也称为类标签( c l a s sl a b e l ) ，它表示一 个实例所属的类一个具体实例的形式用乒( 1 ，l ，v 2 ，；c ) 来表示其中y i 表示属 性值，c 表示类别 定义1 给定一个数据集z ) = - x l ，x 2 ，而) 和一组类c 毫而，c 2 ，c k ) ，分类问 题是去确定一个映射：fd c ，使每个实例x i 被分配到一个类中一个类e j 包含 映射到该类中的所有实例，即c ：= 五) = e j , l fs ，z ) 且而d 在分类中，数据通常可以分为训练集( t r a i n i n gd a t a s e t ) 和测试集( t e s t d a t a s e t ) 训练集用于构造分类器，测试集用于评估该分类器的分类精度训练集 和测试集一般采用不同的数据，以防止产生过于乐观的估计分类的过程由以下 两个步骤组成l i 副： 第一步是建立模型，描述预定的数据类集或概念集通过分析由属性描述的 数据库元组来构造模型数据元组也称作样本、实例或对象为建立模型而被分 析的数据元组形成训练数据集训练数据集中的单个元组称作训练样本，并随机 地从样本群中选取，每个训练样本有一个特定的类标签与之对应由于提供了每 个训练样本的类标签，该步也称作有监督的学习( 即模型的学习在被告知每个训 练样本属于哪个类的“指导”下进行) 它不同于另外一种无监督的学习，也称作 聚类，此时每个训练样本的类标签是未知的，要学习的类集合或数量也可能事先 不知道通常，学习模型用分类规则、决策树、等式、不等式和规则式等形式提 北京交通人。学硕十学位论文 供这些规则可以用来为以后的数掘样本分类，也能对数据库的内容提供更好的 理解 第二步是使用模型进行分类分类正确率是评估模型的一个重要指标模型 在给定测试集上的准确率是被模型正确分类的测试样本的百分比对于每个测试 样本，将已知的类标签与通过学习模型预测的结果相比较如果模型的准确率是 根据训练数据集评估，那么评估的结果町能是乐观的，因为学习模型倾向于过度 拟合数据因此，一般使用交叉验证法来评估模型如果认为模型的准确率可以 接受，就可以用它来对类标签未知的数据元组或对象进行分类 总之，我们可以把分类归结为模型建立和使用模型进行分类两个步骤其实， 模型建立的过程就是使用训练数据进行学习的过程，使用模型分类过程就是对类 标签未知的数据进行分类的过程 分类器的构造方法有多种，主要有决策树方法、贝叶斯方法、如最近邻方法、 后向传播分类、遗传算法以及粗糙集方法等这几种方法 2 3 2分类误差 分类学习方法的泛化性能涉及它在独立的检验数据上的预测能力一般情况 下，衡量一个分类器性能好坏的最重要指标是分类正确率或者分类错误率图2 1 显示了评估学习泛化能力的重要问题，表明了学习泛化能力与偏倚( b i a s ) 和方差 ( v a r i a n c e ) 之间的关系 图2 1 检验样本和训练样本误筹变化 f i g u r e 2 1e r r o rv a r i a n c eo ft e s ta n dt r a i n i n ge x a m p l e 1 2 面向分类学习的离散化方法综述 图2 1 表明了偏倚和方差之间存在一个平甜m 】，在其他条件相等的条件下，改 变学习算法的某个部分将对分类的方差和偏倚产生相反的影响更确切地说，一 个分类器的分类错误率由一个偏倚量，一个方差量和一个不可约量之和【l4 j ： 分类误差= 不可约的误差+ 方差+ 偏倚2 ( 2 1 ) 偏倚描述了由于学习算法系统的误差所构成的误差方差描述了由于训练数 据的随机性以及学习算法行为的随机性所造成的误差，因此它描述了一个算法对 于数据变化的敏感度当一个学习算法越敏感，方差就越大不可约误差描述了 由于噪声数据所引起的误差，它通常是汇集了偏倚和方差偏倚和方差的关系可 以形象地用射击打靶来描述i i ，如图2 2 高偏倚低方差 高偏倚高方差 低偏倚高方差 低偏倚低方差 图2 2 偏倚和方筹的关系 f i g u r e 2 2t h er e l a t i o nb e t w e e nb i a sa n dv a r i a n c e 在射击中，偏倚反映了射击时偏离靶心的程度，偏倚越高 兑明偏离靶心越 远方差则反映了每次射击之间的差距，方差越大说明射击越分散一个好的分 类器应该像一个好的射击手，能够达到低偏倚和低方差 北京交通人学硕十! 学位论文 对于离散化，若离散化产生的区间越多，各个新的离散值就越能得到区分， 也就越具有表示能力，使得偏倚越低；但是区间越多势必造成每个区问的实例数 越少，使得概率估计的方差越高若离散化区问越少，各个离散值的区分能力就 越低，造成偏倚越高；但是区问越少会使得每个区问内的实例数越多，从而能进 行越可靠的概率估计，使得方差越低因此，一个好的离散化算法要求得到的区 间越多越好，每个区间内的实例数也越多越好 2 - 3 3 朴素贝叶斯分类方法概述 贝叶斯分类算法是建立在贝叶斯统计学和贝叶斯网络基础上，是一种最优分 类模型它足通过计算事件出现的概率从而对事件进行预测的一种方法贝叶斯 网络是学习数据集中各属性之间的依赖关系，从而形成一个网状的结构图由于 贝叶斯方法长期以来都是统计学习中的一个重要方法，得到了广泛的研究目前， 有许多贝叶斯分类方法被人们提出，主要有：朴素贝叶斯分类器( n a i