（计算机软件与理论专业论文）基于粗糙集合和朴素贝叶斯模型的分类问题研究.pdf

基于粗糙集合和朴素贝叶斯模型的分类问题研究 摘要 k d d 是在数据库和人工智能的相互融合渗透中逐渐发展起来的个有着广 阔应j j 前景的新兴研究领域，是从数据中提取人们感兴趣的、潜在的、可j _ j 的知 识，并表示成用户可理解的形式。分类是k d d 领域中重要的研究分支。 由波兰数学家p a w l a k 提出的粗糙集合理论是一种表示和处理小确定性知识 的方法，在k d d 领域中具有越来越重要的地位。朴素贝叶斯分类技术是以贝叶斯 定理、最大后验假设等理论为基础，其分类模型由于简单、易于实现而受到普遍 青睐。 本文对基于粗糙集合和朴素贝叶斯的分类问题进行r 研究，主要包括以下几 个方面的内容： 研究了不完备信息系统中粗糙集合理论的扩展，提出了一种基于属性重要度 的粗集扩展模型。 将粗糙集合理论引入朴素贝叶斯分类模型的研究中，提出了基于信息熵的近 似属性约简算法( ) “l k i r ) ，改善条件属性间的依赖关系，最大程度上满足朴素贝叶 斯分类条件独立性假设的要求。 在m m r 算法的基础上提出了基于粗糙集合理论的朴素贝叶斯分类算法 ( r s b c ) ，实验证明，该算法在分类正确率上优于朴素贝叶斯分类算法。 关键词：k d d ，粗糙集合，约简，朴素贝叶斯，分类 t h er e s e a r c ho fc l a s s i f i c a t i o n b a s e do nr o u g hs e t sa n dn a i v eb a y e s a b s t r a c t k n o w l e d g ed i s c o v e r yi nd a m b a s e s ( k d df o rs h o r t ) i san e wi m p o r t a n tr s e a r c ht o p i ci n a r t i f i c i a li n t e l l i g e n c ea n dd a t a b a s ed o m a i n i ti st h ep r o c e s so fm i n i n gt h ei n t e r e s t i n g ， p o t e n t i a l l yu s e f u l ，v a l i da n du n d e r s t a n d a b l ek n o w l e d g ei nd a t a c l a s s i f i c a t i o ni sone o f t h ei m p o r t a n tp r o b l e m si nk d d r o u g hs e tt h e o r yp r o p o s e db yp o l i s hm a t h e m a t i c i a np a w l a k ，w h i c hu s e dt o r e p r e s e n tt h eu n c e r t a i nk n o w l e d g e r o u g hs e tt h e o r yh a sb e c o m eam a i nm e t h o df o r k d dd u et oi t su n i q u ea d v a n t a g ei nk n o w l e d g ed i s c o v e r y n a i v eb a y e sc l a s s i f i e r b a s e do nb a y e s i a nl e a r n i n gt h e o r ya n dm a x i m u map o s t e r i o r ip r o b a b h yh y p o t h e s e s ， w h i c hi sw e l c o m e da si t ss i m p l i c i t y t h i sd i s s e r t a t i o nf o c u s e so l f lt h er e s e a r c ho fc l a s s i f i c a t i o nb a s e do nr o u g hs e t s a n dn a i v eb a y e s , t h ec o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ： e x t e n d e dr o u g hs e tm o d e l sa r ea n a l y e da n dan e we x t e n s i o no fr o u g hs e tb a s e d o i lt h ei m p o r t a n c eo fa t t r i b u t e si sp r e s e n t e d m a i ra l g o r i t h mb a s e do ne n t r o p yt h e o r yi sp r e s e n t e d ，w h i c ht a k e si n t oa c c o u n t t h ei n f l u e n c eo ft h ed e p e n d e n c yo fc o n d i t i o nf e a t u r ea n dd e c i s i o n m a k i n gf e a t u r e t o w a r d sr e d u c t i o n ，a n d 西v e st h em o s ta p p r o x i m a t e l yi n d e p e n d e n c yr e d u c t i o nr e s u l t s t h e r e f o r e ，an a t i v eb a y e sc l a s s i f i e rm e t h o db a s e do nr o u g hs e tw a si n t r o d u c e d o nt h eb a s i so f m a l r i th a sb e e nd e m o n s t r a t e dp e r f e c tp e r f o r m a n c eb ye x p e r i m e n t k e y w o r d s ：k d d ，r o u g hs e t ，r e d u c t ，n a i v eb a y e sc l a s s i f i e r , c l a s s i f i c a t i o n 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕士学位 论文质量要求。 主席： 答辩委员会签名： 澉呵 、安锻娥 委员：。 易h 导师： 铜巳础六 、 会犯础六 职称 敬蠖 敬擂 敦壤 到娥 刭么援 娥 危 7 丝 独创性声明 本人声明所窄交的学位论文是本人在导师指导f 进行的研究【：作及取得的研究成果。据 我所知，除了文中特别加以标志和致谢的地方外，论文中小包含其他人已经发表或撰写过的 研究成果，也4 二包含为获得盒避些厶堂 或其他教育机构的学位或证书而使用过的材 刳。戏一同一i 。作的同志对本研究所做的任何贡献均已在论文巾作r 明确的说明并表不谢 意。 学位论文作者签字：素陋光签字h 期：口 年月f 3 日 学位论文版权使用授权书 本学位论文作者完全了解垒壁王些叁堂有关保留、使用学位论文的规定- 有权保留 弗向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金 8 墨至些塞堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影 印、编印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名 签字f - j 期： 年 月日 学位论文作者毕业后去向 1 作单位： 通讯地址： 挪始瑚 签字日期：眵年妒侈一 电话： 邮编： 致谢 值此论文完成之际，首先要真诚感谢我的导师胡学钢教授! 胡老师知识广博， 治学严谨能够紧密结合理论和实践。为我选择的课题既能紧紧联系实际问题， 也不失理论深度。在做人和生活上，胡老师的诚恳、宽容和强烈的责任心同样是 我学习的榜样! 如果没有胡老师对我倾注心血的指导、对我论文精心反复的修改 和推敲，我是不町能顺利完成学业的! 我同样要十分感谢计算机学院人工智能和数据挖掘实验室的王浩教授、欧阳 一鸣副教授和实验室的吴共庆、王德兴等老师，在我遇到难题时，他们总能给予 我无私的帮助。 同时，还要感谢唐志军、刘凡等师兄弟以及人【智能和数据挖掘实验室的所 有同学，大家一起研讨问题，集思广益，对我的论文有很大启发。感谢研2 0 0 2 级1 4 班的全体同学，我为能处于这样一个优秀的团队而感到骄傲! 感谢计算机学院的王新生老师对于我学业的关心和付出的辛勤工作! 虽后，也是最重要的，我要衷心的感谢我的家人! 他们对我始终如一的深爱， 催我奋发向上，让我倍感温暖! 父母不仅养育了我，还以自己的朴实、善良、坚 强，让我学会以积极、乐观的心态面对生活，正是这样的熏陶使我得以完成学业 并且准备迎接未来的种种挑战! 家人永远是我力量的源泉! 感谢我的女友潘甜甜对我一如既往的支持! 作者：郭亚光 2 0 0 5 年4 月 第一章绪论 信息技术的应用已经渗透到人类活动的各个领域，数据库、数据仓库以及 f n t e r n e t 技术的应用普及使得我们可以获得和需要处理的数据规模越来越大【4 】。 数据的丰富带来了对强有力的数据分析工具的需求。k d d ( k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ，k d d ) 吲就足在这种背景下产生的，并迅速得到广泛关注，成为当前人 工智能领域的研究熟点。本章概述了k d d 及数据挖掘的研究和发展概况，重点介 绍了其中的分类问题。此外还给出了本文的内容组织。 1 1 k d d 1 1 1k d d 定义及研究现状 近半个世纪以来，信息技术的高速发展给人类社会带来了巨大的变化 与影响，数据成为最重要的战略资源。收集和存储数据的能力已经大大超 过了对其分析和综合处理的能力，从如此大量的数据中，获取有用的知识 变得越来越困难了，这就是被j o h nn a i s b e t t 称之为“信息丰富而知识贫 乏”( d r o w n i n gi ni n f o r m a ti o nb u ts t a r v i n gf o rk n o w l e d g e ) 的窘境【5 】。 为此，有效地分析、利用和处理大量的数据成为当前的世界共同关心的问 题。随着数据库技术、人工智能、统计和并行计算等技术的发展和融合， 数据库知识发现( k n o w l e d g ed is c o v e r yi nd a t a b a s e s ，k d d ) 一1 便酝酿 而生。 k 叻一词是在1 9 8 9 年于美国底特律市召开的第1 l 届国际人工智能联合会议上 首次提出的，这届学术会议上举行了以k d d 为主题的学术讨论，随后相继在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年举行了k d d 的专题讨论会。随着对k d d 的深入研究以及k d d 在 许多领域的，。泛成功的应用，于1 9 9 5 年，在加拿大召开了第一届知识发现和数据 挖掘国际学术会议，此后每年召开一次。第一本关于k d d 的国际学术杂志d a t a m i n i n ga n dk n o w l e d g ed is c o v e r y 也j 二1 9 9 7 年3 月创刊发行。亚太地区于1 9 9 7 年在新加坡召开了首次k d d 国际学术研讨会。以后每年都召开国际及亚太地区的 k d d 会议。目前，i j c m 、a a a i 、v l d b 等代表人工智能与数据库技术研究最高水平 的国际学术会议上，和k n o w l e d g ea n di n f o r m a t i o ns y s t e m s ，i e e ec o n c u r r e n c y 等著名杂志对k d d 的研究都占有较大的比例，k d d 已经成为当今计算机科学与技术 领域研究、应用的热点领域之一。 众多的学者根据自己的对k d d 的认识和理解，给出了很多的定义，而其中 比较公认比较完整、深刻和全面的一个定义是由f a y y a 吐p i a t e t s k y - s h a p i r o 和 s m y t h 在k d d 9 6 国际会议的会议论文f r o md a t am i n i n gt ok n o w l e d g e d i s c o v e r y ) ) 一文中将k d d 定义为： “t h en o n t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n d u l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a 即k d d 指大量数据中获取有效的、新颖的、有潜在作用的和最终可理解的 模式的非平凡过程。还有很多和这术语相近似的术语，如数据挖掘( d m ) 、数 据分析( d a t aa n a l y s i s ) 、数据融合( d a t af u s i o n ) 以及决策支持( d e c i s i o n s u p p o r t i n g ) 等。 下面对这个定义作详细的解释： 数据：数据是一系列事实的集合，可以是一个或一组数据库、数据仓库、电 子表格或其他类型的信息库，在数据上进行数据清理、集成和规约后的数据。这 是k 3 3 d 处理的最常用的数据形式。 模式：模式是指用语言来表示的一个表达式，它可用来描述数据集的特性， 根据某种兴趣度度量，并于数据挖掘模块中进行交互挖掘，以便识别和表示知识 的真正有趣的模式。 过程：过程是在k d d 中包含的步骤，如数据的预处理、模式搜索、知识表 示及知识评估、过程优化等。 非平凡：是指它已经超越了一般封闭形式的数量计算，包括对结构、模式和 参数的搜索。 有效性：通过k d d 从当前数据所发现的模式必须有一定的正确程度，否则 k ) d 就毫无作用。 新颖性：经过k d d 提取出的模式必须是新颖的，全少对系统来说应该如此。 模式是否新颖可以通过两个途径来衡量：其一是在所得到的数据方面，通过对比 当前得到的数据和以前的数据或期望得到的数据之阳j 的比较，来判断该模式的新 颖程度；其二是在其内部所包含的知识方面，通过对比，发现的模式与已有的模 式的关系来进行判断。 潜在作用：提取出的模式应该是有意义的，有潜在的应用价值。 可理解：k d d 的一个目标就是将数据库中隐含的模式以容易理解的形 式表现出来，从而帮助人们更好地理解数据库中所包含的信息。 一般将k d d 中进行知识发现的阶段称为数据挖掘( d a t am i n i n g ，d m ) ，目前关于k d d 的研究大多着眼于对数据挖掘步骤的研究。某些应用领 域对数据挖掘与k d d 不加区分地使用，某种意义上二者可看作同一个概念。 目前人们对整个处理过程并没有给出非常清楚的划分，而建立合适的处理过 程模型能将各个处理阶段有机地结合在一起，以便于人们开发及使用k d d 应用 系统。比较有代表性的模型有三种： 第种是u s a m am f a y y a d 等人给出的多处理阶段模型。 第、冲 是g e o r g eh j o h n 给出的多处理阶段模型。 第三种是b r a c h m a n & a n a n d 提出的以用户为中一0 舟勺处理模型。 为了使k d d 能更好地应用于实践，下面以第种面向多阶段处理过程 的k d d 处理过程模型为例进行简要地说明，如图1 1 所示 知担 国彀据库中知i 旦发现瞬好理过程横窒 图1ik d d 的处理过程模型 有关数据挖掘技术的研究虽然时间一i 长，但已从理论研究走向了产品开发， 其速度卜分惊人。国外许多计算机公司非常重视d m 系统的开发应用，i b m 与微软 都成立了相应的研究中心进行这方面的工作。有些公司已经开始进行相应软件的 开发，如：s a s 公司的e n t e r p r i s em i t i e r ，i b m 公司的i n t e l li g e r tm i n e f ，s g 公司的s e t m i n e r ，s p s s 公司的c l e m e n t i n e 等。另外还有一些基于w e b 的数据挖掘 产品如n e tp e r c e r p t i o n s ，a c c r u ei n s i g h t 和a c c r u eh i tl i s t ，c o m m e r c e t r e n d s 等。 随着k d d 在国际上的兴起，我国也积极地开展了相应的研究和应用。 1 9 9 3 年国家自然科学基金首次支持该领域的研究项目，目前国内许多学 术会议，如数据库学术会议、机器学习会议等，也都将k d d 列为重要的研 究方向。我校是国内较早进行知识发现的研究单位之一，八十年代末期以 来相继在国家自然科学基金资助下开展了“从关系数据库中提取领域知识 的自动化获取研究”，在国家教委博士学科点专项科研基金资助下开展了 “从大规模数据库中自动提取领域知识的算法与实现研究”，以及在国家 自然科学基金项目“基于粗糙集合理论的概念格模型研究”等。 1 1 2k d d 与相关技术的比较 k d d 融合了多学科的知识，包括机器学习，模式识别，统计学，人i ： 智能，专家系统，数据可视化和高效率计算等。k d d 与这些领域的技术密 切相关，但又有一定区别。f 面简要介纠一下k d d 与这些技术的比较。 k d d 与机器学习 知识发现和机器学习都是从数据q 提取知识的过程，但二者是有区别 的。机器学习方法是计算机科学和人j ：智能发展的产物，是采用人工智能 技术来实现机器从客观世界中学习，而k d d 是在没有明确假设的前提下去 挖掘信息、发现知识，发现所得到的知识具有潜在性，有效性和实用性三 个特征；k d d 是面向大规模数据库的，且数据来源是现实世界中存在真实 数据，存在一定的缺失和噪音数据，而机器学习一般面向的是几百到几千 条记录的数据，数据大多是经过专家挑选的，没有或较少出现噪音和缺失 数据。 机器学习方法可分为自组织学习和归纳学习两种，这些方法都在k d d 过程中被运用。基于此，有入认为k d d 是利用机器学习的方法从数据库中 提取有价值的知识的过程，同时还继承和发展了其他学科的多种方法。 k d d 与数据库技术 首先，k d d 与目前数据库管理系统d b m s 的作用是不同的。数据库茸理 系统的侧重点是把大量的数据组织起来，以方便用户进行存取和维护，并 对数据的一致性和完整性进行约束。而k d d 则侧重于对数据库中的数据进 行分析，以得到有用的结果。再次，数据库中的数据库报表工具与k d d 也 是不同的，前者按用户提取数据库中的数据，进行简单的数学运算和处理， 并以特定方式提交给用户，而后者是要发现隐藏在数据背后的特征和趋 势，给出关于数据的总体特征和发展趋势。 k d d 与传统的统计方法 尽管统计方法是数据分析的理论基础，但对k d d 来说，仅有统计方法 是不够的。统计方法是完全基于数据的，依赖于特定分布和独立性假设， 排除了领域知识的参与。此外，统计方法需要用户参与指导怎样对数据进 行分析，而k d d 过程虽然也强调与用户的交瓦性，但其很多计算过程都是 计算机处理的，人工干预较少，因此k d d 比统计方法更具客观性和全面性。 4 1 1 3k d d 的主要任务 妯d 的主要任务是发掘数据问潜在的模式，找出人们可能忽视的信息，以 便于理解和观察的形式反映给用户，并给出基于知识的决策分析意见和结论。 由于k d d 所涉及的学科领域很多，在各学科领域中，k d d 均赋有不同的任务， 但以下j l 种任务是共同的 1 1 幢】，也是最重要的。 分类( c 1 8 s s i f i c a t i or 1 ) ：分类是k d d 中心f 玎最普遍的一种技术。分 类是从+ 组已知的、已分类的数据中提取出个模型( 也称作分类器) ， 该模型能把数据库中的数据项映射到给定类别中的某一个，从而实现对数 据的分类。分类问题被广泛应用于疾病诊断，银行信贷等领域。当前研究 的分类模型主要有贝叶斯( b a y e s ) 分类，决策树( d e c i s i o nt r e e ) ，神经 网络( n e u r a ln e t w o r k ) ，粗糙集合( r o u g hs e t ) ，统计方法( s t a t i s t i e s ) ， 遗传算法( e v o l u t i u n a r ya 1 9 0 r j t h m s ) 等，其中决策树由于其准确率高 和汁算量相对小，成为应用最广泛的方法。本文主要研究基于粗糙集合理 论和朴素贝叶斯的分类，研究结果表明，基于粗糙集合理论和朴素贝叶斯 的分类与其它方法相比在分类正确率上有很人提高。 汇总( s u m m a r iz a t i o n ) ：其目的是对数据进浓缩，给出其紧凑描述。 k d d 主要关心从数据泛化的角度来讨论数据总结。数据泛化是一把数据库 中的有关数据从低层次抽象到高层次过程。 关联规则( h s s o e i a t i o nr u l e s ) ：所谓关联规则，是指数据对象之间 的相互依赖关系，而发现关联规则的任务就是从数据库中发现那些确信度 ( c o n f i d e n c o ) 和支持度( s u p p o r t ) 都大于给定值的强规则( s t r u n gr u l e ) 。 近几年关联规则挖掘的研究较多。目前，已经从单。概念层次关联规则的 发现发展到多个概念层次的关联规则的发现。在概念层次上的不断深入 使发现的关联规则能提供更具体的信息，这实际上是逐步深化发现知识的 过程。常见的关联规则发现算法有h i s ，s e t m ，a p r i o r i ，d h p 等，其中， 应用较多的是a p r i o r i 和n i p 两个算法。 序列模式( s e q u e n t i a lp a t t e r n s ) ：序列模式是指在多个数据序列中 发现共同的行为模式。序列模式发现算法的框架与发现关联规则相同，也 是一个逐步迭代的过程，在每次迭代中，包括了候选频繁情节的生成和在 事件序列中识别候选情节两个过程。迭代直到不能再产生频繁情节为止。 例如，对序列数据库d 中的某顾客，序列模式发现问题就是在该数据库中 寻找所有的频繁序列或所有的最长频繁序列。r a g r a l 称最长频繁序列 为序列模式( s e q u e l 3 t i a lp a t t e r n ) 。 聚类( c 1u s t e r in g ) ：聚类是根据客体属性集对一系列未分类客体进 行类别的识别，按照相似性分成若干类别，即“物以类聚”。聚类的目的 是使属于同类别的个体之间的距离尽可能的小而不同类别的个体间的 距离尽可能的大，即聚类应该使类内个体问的相似性最大，而类别问的相 似性最小。 1 1 4k d d 发展趋势 k d d 面i 临的主要问题和研究趋势体现在以下几个方面： 挖掘方法和用户交互问题：这反映在所挖掘的知识类型、在多粒度上 挖掘知识的能力、领域知识的使用、特定的挖掘和知识显示。 性能问题：包括数据挖掘算法的有效性、可伸缩性和并行处理以及分 布式和增量挖掘算法。 数据库类型的多样性问题：如关系的和复杂的数据类型的处理( 例如 数据对象、多媒体数据、空间数据、时间数据或事务数据等) ；由异种数 据库和全球信息系统挖掘信息。 以上问题是k d d 技术未来发展的主要需求和挑战。在近年来的数据 挖掘研究和开发中，一些已受到一定程度的关注，而另一些仍处于研究阶 段。 1 2k d d 中的分类问题 分类研究一直是k d d 领域的重要问题之一，许多问题都可以等价的 转化为分类问题f 1 引。 1 2 1 分类问题的定义 分类是一种数据分析形式，可以用于提取描述重要数据类的模型来预 测未来的数据趋势。分类的目标是通过分析训练数据集，构造个分类模 型( 即分类器) ，该模型能够把数据库中的数据纪录映射到给定的某一个 类别，从而可以应用于数据预测。一般来说，分类分为两个步骤： 第一步是建立模型，描述预定的数据类集或概念集。常见的分类器模 型有决策树，神经网络，贝叶斯等。 第二步是使用模型进行分类。模型分类的首要问题是评估模型的预测 准确率，一般的方法是保持法( h o l d ) 和k 一交叉确认( k - c f o s s ) 法。如 果模型的准确率是可接受的，则利用这个模型来分类。 通常，分类器用分类规则、判定树或数学公式的形式提供。例如，对 顾客信用信息的数据库，可以通过学习有关信誉的分类规则，以识别顺客 的信誉度优良与否。这些规则可以用来为以后的数据样本分类，也能对数 据库的内容提供更好的理解。 1 2 。2 几种主要的分类模型 分类技术是很多领域，比如统计、模式识别、人工智能、神经网络等 领域的研究课题。本节介绍了一些分类算法和知识模型。 一、决策树 决策树是分类研究最常用的模型之一，利用树中从根到叶子节点的路 径表示分类规则。决策树方法的最大优点是可理解性，比较直观，缺点是 处理复杂的数据时，受噪音数据等因素导致出现过多碎片( f r a g m e n t ) 。 决策树最早起源于概念学习系统c l s ，后来发展到i d 3 方法，在i d 3 算法 的基础上，又演化出处理连续属性的c 4 5 算法，能处理数据空缺值的c a r t 和c h a i d 等方法，目前出现的两种新算法s l i q 和s p r i n t ，能在非常大的 训练集中进行决策树归纳，并可以处理符号属性和连续性属性“。”3 。 决簧树根据数据特征属性不断的划分问题求解空问，直至满足分类条 件为止。有关决策树分类的方法将在后面章节详细阐述。 二、概念格 r w 订l e 等提出的根据二元关系建立的概念格( g a o i s 格) 是一种完 备的层次结构“。”1 ，在本质上描述了对象与属性之问的联系，表明了概念 之间泛化与例化的关系。在信息检索、数字图书馆、软件工程、知识分类、 类的设计、网络管理和k d d 等领域，概念格已经显示出一定的应用价值 f 1 6 、z 2 三、粗糙集合( r o u g hs e t s ) 粗糙集合理论认为“概念”即是对象的集合，“知识”即是将对象进行分类 的能力。不可区分关系是粗糙集合理论中最基本的概念，在此基础l 二引入了元素 的成员函数关系、概念的上近似和下近似等来刻划其知识处理方法。由不可区分 关系可以确定给定论域l 的等价类，使用粗糙集合相应的公式来计算条件属性和 决策属性的依赖性，通过数据约简可以在保持分类一致的约束下大大简化样本数 据，从而肖o 减冗余对象与属性、寻求属性的最小子集以确保产生满意的近似分类， 由此可以得出知识的相对约简和相对核以及种类的相对约简和相对核等目标数 据，然后通过对目标数据的分析，使用很少的几条逻辑规则就能描述分类规则。 7 【q 、神经网络 神经网络领域前馈式神经嗣络模型手要用于分类和预测，r u m d h a r t 聚用 s i g m o l d 型作用函数，并提出了b p 算法。b p 刚络的特点是信号由输入层单向侣 输到输出层，同一层神经元之问不传递信息，每个神经元与邻层所有神经元相连， 连接强度用杈值表示，各神经元的作用函数为s i g m o i d 函数，它i 下向传播信号， 反向传播误差。学刿开始时，权值向量任意给出，然后使用迭代算法来确定权值 向量，当网络输出判别正确时，权值向量保持不变，否则进行增加或降低的调整， 通过对训练集的的训练就町阻得出相应的分类模式。神经嘲络方法的缺点足“黑 箱”性，人们难以理解网络的学爿_ 手【】决策过程。 五、统计分析 统计分析的理论基础主要是统计学和概率论，是一种基于模型的较为 精确的数据挖掘技术，包括回归分析、因子分析和判别分析等。该方法比 较容易理解，对结果描述精确。然而，当利用大规模训练集来学习时，统 计分析的评估代价变得很敏感。随着训练集规模的增长，代价增长更快。 六、贝叶斯方法 贝叶斯( b a y e s ) 分类是数据挖掘领域中一种常用的有指导的分类方 法。贝叶期分类器分两种： 一种是朴素贝叶斯分类器( n a i v eb a y e sc l a s s i f i e r ，简称nbc ) ， 基于条件独立性假设，即假设。个属性对给定类的影响独立于其他属性。 朴素贝叶斯分类的优点是具有最小的误分类率，缺点是具有较强的限制条 件( 即条件独立性假设) ，在实际应用中很难得到满足。 另一种是贝叶斯网络分类器，贝叶斯网络基于后验概念的贝叶斯定 理，是建立在统计基础上的方法。将不确定事件通过网络连接起来，可以 对其他相关事件进行结果预测，其网络变量可以是可见的，也可隐藏在训 练样本中。”。贝叶斯网络具有分类、聚类、预测和因果关系分析的功能， 其优点是具有很强的学习、推理能力，能很好地利用先验知识，缺点是队 发生频率较低事件的预测效果不好，且学习过程容易存在组合爆炸的问 题。 1 2 3 分类模型的评价 我们一般- 从以f 凡个方面对分类模型的性能进行评价： ( 1 ) 预测准确度：预测准确度是分类器的一个重要度量，分类器是已知数据 集的描述模型，也可用于对目标数据进行预测。预测准确度可以评价一个分类器 对于预测将来数据的准确度，是用得最多的。种比较尺度，特别是对于预测型分 类任务，评价分类器的预测准确度有两种常用的方法：保持( h o l d o u t ) 和k 一次交 叉验自f ( k f o l dc r o s s v a l i d a t i o n ) ，还有其他的方法也可用于评价分类器的准 确度，如b o o t s t r a p p i n g ，l o g v e o n e o u t 等等。 ( 2 ) 计算复杂度：计算复杂度依赖r 算法的实现细节与机器的硬件环境。在 数据挖掘中，目标数据大多是大型数据库，数攒规模也越来越大。因此，时空性 能将是非常重要的一个因素。 ( 3 ) 模型描述的简洁度与可解释壮：对于描述型的分类任务，模型描述越简 洁越受欢迎，因为分类器是通过特定算法挖掘出的模式，这些模式最终是面向特 定领域用户的，所以挖掘出的模式要易于理解，便于用户进行决策。 ( 4 ) 健壮性：健壮性是衡量分类器优劣的一个方面，也是分类器抗干扰能 力的度量。现实生活中的数据总会存在噪音数据，而对存在噪音数据的数据集， 能否得出好的分类器以及给出正确的预测类别，这一点也很重要。 ( 5 ) 可伸缩性：目前大部分的分类算法是基r 数据规模很小的假定。算法 的可伸缩性意味着当给定大数据量能否有效的构造模型。 总之，分类的效果一般与应用领域背景以及数据的特点有关。目前，还没 有发现一种对于所有的数据集都最优的方法。也就是说，不存在某种方法能适用 任何应用，适合各种特点的数据。 1 3 本文的内容组织 本文由五章组成： 第一章主要简述数据库中的知识发现产生的原因以及发展前景，概述了 知识发现的相关概念，介绍了k d d 及其研究对象的发展现状和未来趋势，详细 阐述了k d d 中分类阀题的定义、方法以及分类模型评价的标准等。最后简要给 出了文章的组织结构。 第二章系统介绍了贝叶斯分类的基本理论，描述了几种常用的贝叶斯分 类模型：朴素贝叶斯分类模型、贝叶斯网络模型及增量贝叶斯分类模型。对朴 素贝叶斯分类模型进行了重点研究，分析了该模型的优缺点，并通过引入粗糙 集合理论对朴素贝叶斯分类性能作了改进。 第三章阐述了粗糙集合理论的基本思想，对粗糙集合理论中知识约简的 定义、方法作了详细介绍。此外，描述了彳；完备信息系统中r o u g h 集理论的几 种扩展模型，并给出了基于属性重要度的r o u g h 扩展模型的改进。 第四章给出了本文的核心内容，在对前面理论总结研究的基础上，将粗 糙集合和贝叶斯分类两种软计算方法相结合。提出了基于信息熵的近似属性约 简算法( 1 d a i r ) ，并在此基础上提出了基于粗糙集合和朴素贝叶斯分类的r s b c 算法。此外，对r s b c 算法和n b c 算法进行了分析比较，首先从理论上对其 进行了比较，然后选择u c i 机器学习数据库提供的典型数据库实例，通过实验 对r s b c 算法和n b c 算法进行了比较。 第五章对己有的工作进行总结，并对卜一步的f 作进行了展望。 o 第二章贝叶斯理论与贝叶斯分类模型 j ! 叶斯分类器是建立在经典的贝叶斯概率理论的基础上的基) ：统计方法 的分类模型【8 3 ”。本章t 要讨论9 j 叶斯分类的基本原理和几种常见的贝叶，斯分 类模型。 2 1 贝叶斯分类的一般原理 贝叶斯分类方法的特点是用概率表示所有形式的不确定性，学爿和推理都 用概率规则来实现。贝叶斯学派的起点是贝叶斯的两项工作：贝叶斯定理和贝 叶斯假设。下面我们分别对贝叶斯定理和贝叶斯假设进行阐述。 2 1 1 贝叶斯定理 贝叶斯定理提供了一种计算假设概率的方法，它基于假设的先验概率、给 定假设下观察到不同数据的概率以及观察到的数据本身。 在给出定理之前要引入一些记号。我们用p ( h ) 表示在没有训i 练数据前假设 h 拥有的初始概率。p ( h ) 常被称为h 的先验概率( p r i o rp r o b a b i l i t y ) ，反映 了所拥有的关于h 是一正确假设的概率的背景知识。同样的，用p ( d ) 代表将要 观察的洲练数据d 的先验概率( 在没有确定某一假设成立时d 的概率) 。p ( d h ) 代表假设h 成立的情况下数据d 的概率。在机器学习中，我们需要得到给定训 练数据d 时h 成立的概率，即h 的后验概率：p ( h id ) 。 通过以上的描述可知先验概率p ( h ) 与数据d 无关，而后验概率p ( h id ) 是 与训练数据d 相关的。p ( h ) 、p ( d ) 和p ( d ih ) 都可以由已知的数据计算得到， 贝叶斯公式给出了计算后验概率p ( h i d ) 的方法： e ( hd 】；! 望凼! 塑 ( 2 1 ) p(d) 贝叶斯分类方法正是基于上述定理的。 2 1 2 极大后验假设与极大似然假设 在许多学习任务中，需要考虑候选假设集合 并在其中寻找给定的数据d 时可能佳最大的假设h h 。任何这样具有最大可能性的假设被称为极大后验假 设( r l l a x i m u map o s t e r jo r i ，m a p ) ，记为h m ： h m 。p = a r gm a xp ( hd ) = a r gm a xp ( dh ) j d ( ) p ( d ) ( 2 2 ) e h e h = a r g i t ia xp ( dh ) p ( ) e 由于p ( d ) 是不依赖于h 的常量，所以在最后一步去掉了p ( d ) 。上式就是 一个原始的分类模型。贝叶斯分类就是根据上述m a p 假设找出新实例最可能的 分类。所有对贝叶斯分类模型的研究工作都是以此假设为前提的。 在某些情况下，可假定h 中每个假设有棉同的先验概率( 即对h 中任意的 h 。和h ，p ( h 。) = p ( h ) ) 。这时可把( 2 2 ) 式进步简化，只考虑p ( d h ) 来寻找 极大可能假设。p ( d lh ) 常被称为给定h 时数据d 的似然度( 1 i k e l i h o o d ) ，任何 使p ( d lh ) 最大的假设称为极大似然假设( m a x i m u ml i k e l i h o o d ，m l ) 记为：h 。 m ；a r g m a x p ( d | ) ( 2 3 ) h e h 在分类过程中，( 2 3 ) 式常被用来在启发式搜索时进行模型检测。 2 2 几种常见的贝叶斯分类模型 下面我们简单介绍几种贝叶斯分类模型 3 7 , 4 0 , 4 1 ，并对其特点进行分析，继 而引出下一章所做的工作。 2 2 1 朴素贝叶斯分类模型及扩展 朴素贝叶斯分类器( n a i v eb a y e sc 1 a s s i f i e r ，n b c ) 是贝叶斯分类模型中 一种最简单、有效的分类器1 4 3 ，“4 5 】。其性能可以与神经网络、决策树( 如c 4 5 ) 相比。 朴素贝叶斯分类模型描述如图2 。1 所示，设有变量集u = ( a ；，a 。，a 。，c ， 其中a 。，a ：，a 是实例的属性变量，c 是取m 个值的类变量。假设所有的属性都 条件独立于类变量c ，即每一个属性变量都以类变量作为唯一的父节点，就得 到朴素贝叶斯分类器。 朴素贝叶斯模型假定特征向量的各分量间相对于决策变量是相对独立的， 也就是说各个分量独立地作用于决策变量，尽管这一假定在一定程度上限制了 朴素贝叶斯模型的适用范围，但是在实际应用中，大大降低了贝叶斯网构建的 复杂性。朴素贝叶斯分类模型已经成功地应用到聚类、分类等数据挖掘的任务 中。目前，许多研究致力于改进特征变量间独立性的限制条件，以使它能适用 于更广的_ 、范围。本文所做的研究工作正是基于这一点进行的。 。 图2 1 朴素贝叶斯分类模型结构示意刚 2 2 1 1 朴素贝叶斯分类原理 给定一个具有k 个属性的数据集，假设这k 个属性值均为离散值，分类任务是预 测测试集中每一个例子的类别。给定一个具体的例子，其属性值从a 。到a 。，该例子属 于某一个类c ；的概率是p ( c = c f a ，= a 八 a 。= a 。) 。显然如果该例子属于的某一个类 的该概率值具有最大值，那么该例子就属于这个类。根据贝叶颠定理： j p ( ci ) ：p ( x i c , ) p ( c a ， 以) 其中p ( c ，) 被称为先验概率，由于p ( x ) 对于所有类为常数，只需要最大 p ( x 1 ) p ( q ) 即可；计算p ( c i ) 很方便，可以通过公式p ( c ) = s i s 计算，其中 s 。是类c 中的训练样本数，而s 是训练样本总数。 但是针对给定具有许多属性的数据集，计算最大后验概率p ( xj q ) 时计算的 开销可能非常大。为了降低计算的开销，可以做类条件独立的朴素假定。给定 样本的类标号，假定属性值相互条件独立，即在属性问，不存在依赖关系。这 样，p ( x1 g ) = n p ( 黾i e ) 概率p ( k l e ) 可以由训练样本估值，即p ( x k i c ) = s i ，其中是在属性 a 。上具有值x 。的类c ；的训练样本数，而5 ，是c 中的i ju i 练样本数。所以就得到了 朴素贝叶斯分类算法的分类公式： = a r g m a xp ( c 。) i - p ( x ki ) k = l 为测试集中的未知样本x 分类，对于每个类c ，计算p ( x i g ) p ( c f ) ，样本 x 被指派到其p ( x i g ) p ( g ) 最大的类c 。即是 p ( x c 】) p ( q ) p ( xc j ) p ( c ，) ，l ( j m j i 朴素贝叶斯分类模型的优点是： ( 1 ) 算法逻辑简单，易于实现： ( 2 ) 算法实施的时间空间开销小； ( 3 ) 算法性能稳定，对于不同特点的数据其分类性能差别不大，即模型的健壮性 比较好。 但是，朴素贝叶斯分类模型中的类条件独立性假设也是它的先天不足所在独立 性假设在许多实际问题中并不成立，如果在这些问题中忽视这一点，会引起分类的误 差。为了克服这一不足，我们对朴素贝叶斯分类算法作了一些改进，主要是放宽条件 独立性的限制。 2 2 1 2 对朴素贝叶斯分类模型的改进 经研究发现，朴素贝叶斯分类算法在两种情彤卜分类性能最优，就是当条 件属性完全独立或完全依赖“。但是这两种情况过于极端，在实际应用中并不 常见，因此需要针对实际应用对朴素贝叶斯分类模型作一些改进。以下是我们 对其中常见的两种情形做的处理： 一是在计算训练集中属性值出现的频率时，遇到不确定值时如何处理；二 是属性的条件独立性要求过于严格，实际中很难满足，如何放宽条件限制。我 们下面分别进行讨论。 处理数据集中的不确定值 在实际数据库中，可能会因为某种原因造成数据遗失的情况，我们采用以 下方法来处理这些遗失值，一是在用给定的实例进行计算时将它们分离出来， 二是通过数据补齐算法( 如基于粗集的数据补齐算法) ，进行遗失数据的补齐。 对不确定值的处理方法的选择要结合具体应用领域来定。当某个不确定值 具有特定含义时，我们可以选择将它们分离出来。无论是哪种处理方法所造 成的误差差别不大。本文选择基于粗集的数据补齐算法来进行处理，在第四章 给出具体的算法实现。 通过属性约简改善属性间的依赖住 通过前面的介绍，我们知道运用粗糙集合理论可以对条件属性集进行约简 处理而不改变分类质量，然后结合信息熵理论可以计算出约简后的属性依赖度， 扶而可以选择一个近似独立的约简后的属性集。这样，既可以满足朴素贝叶斯 分类的类条件独立的基本要求，又可以通过约简降低特征维数，缩减求解问题 的规模。具体方法的介绍在第四章给出。 2 2 2 提升的朴素贝叶斯分类器 改进朴素贝叶斯分类器的性能可以通过“提升”( b o o s t i n g ) 3 7 , 4 5 a 6 1 的方 法。提升方法是由f r e u n d 和s c b a p i