（计算机应用技术专业论文）朴素贝叶斯分类器的研究与应用.pdfVIP

摘要 朴素贝叶斯分类器是一种简单高效的分类算法，在数据挖掘和模式识别中应 用广泛，但是朴素贝叶斯假设在现实中往往不能成立，或多或少都影响了分类的 效果。很多分类方法是通过适当放松朴素贝叶斯假设，提高朴素贝叶斯分类器的 分类精度，结果通常会导致计算代价的大大提高。 本文主要工作和创新点如下： ( 1 ) 详细研究了朴素贝叶斯分类器及各种改进模型，通过探讨如何更好的学习 朴素贝叶斯分类器，提出了一种基于粗糙集的特征加权朴素贝叶斯分类器，从而 提高了朴素贝叶斯分类器的分类性能。 ( 2 ) 提出一种基于粗糙集的特征加权朴素贝叶斯算法( f w n b ) 。加权参数直接 从属性的粗糙下近似集导出，其可看作是计算每种类别的后验概率时，该属性对 此计算的影响程度。将f w n b 与朴素贝叶斯分类器( n a i v eb a y e s i a nc l a s s i f i e r , n b ) 、 贝叶斯网( b a y e sn e t w o r k s ) 和n b t r e e 分类器通过数值实验比较。为了更充分地 验证f w n b 的有效性，将其与文献2 6 中的基于r o u g hs e t 的加权朴素贝叶斯分类 器和文献3 2 中的基于粗糙集的朴素贝叶斯分类算法进行了实验对比。 数值实验与对比实验都充分表明：在大多数数据集上，f w n b 分类器可在较 小的计算代价下，获得较高的分类正确率。 ( 3 ) 将基于粗糙集的特征加权朴素贝叶斯分类器应用于个人信用的指导中去， 验证其分类效果。并与w e s t 的神经网络模型以及李旭升等人提出的扩展的树增强 朴素贝叶斯网络进行了实验对比，结果表明，f w n b 在分类正确率上显著优于其 他算法。 关键词：朴素贝叶斯分类器，特征加权，贝叶斯网，粗糙集 a b s t r a c t n a i v eb a y e s i a nc l a s s i f i e ri sas i m p l ea n de f f i c i e n tc l a s s i f i c a t i o na l g o r i t h m ，w h i c hi s w i d e l yu s e di nd a t am i n i n ga n dp a t t e r nr e c o g n i t i o n , b u tt h en a i v eb a y e s i a na s s u m p t i o n o f t e nd o e sn o th o l di nt h er e a lw o r l d ，a f f e c t i n gt h ec l a s s i f i c a t i o nr e s u l t sm o r eo rl e s s a n u m b e ro ft e c h n i q u e sh a v e e x p l o r e ds i m p l e r e l a x a t i o n so ft h en a i v eb a y e s i a n a s s u m p t i o ni no r d e rt oe n h a n c ea c c u r a c y , b u tu s u a l l yl e a dt ot h ec o m p u t a t i o n a lc o s t g r e a t l y t h em a j o rt a s k sa n di n n o v a t i o np o i n t so ft h i sp a p e ra r ea sf o l l o w s s t u d yt h en a i v eb a y e s i a nc l a s s i f i e ra n di t sv a r i o u si m p r o v e dm o d e li nd e t a i l ， e x p l o r eh o w t ob e t t e rl e a r n i n gt h en a i v eb a y e s i a nc l a s s i f i e r , p r o p o s ean a i v eb a y e s i a n c l a s s i f i e r su s i n gf e a t u r ew e i g h t i n gb a s e do i lr o u g hs e t s ，w h i c hi m p r o v e st h en a i v e b a y e s i a nc l a s s i f i c a t i o np e r f o r m a n c e p r o p o s ean a i v eb 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 mu s i n gf e a t u r ew e i g h t i n gb a s e d o nr o u g hs e t s ( f w n b ) t h ef e a t u r ew e i g h t i n gc o e f f i c i e n t sa r ed i r e c t l yi n d u c e db yr o u g h l o w e ra p p r o x i m a t i o no fa t t r i b u t e s ，a n dc a nb er e g a r d e da st h es i g n i f i c a n c eo fe a c h a t t r i b u t ew h e n e v a l u a t i n gt h ep o s t e r i o rp r o b a b i l i t yo ft h ep a r t i c u l a rc l a s sv a l u e c o m p a r e dt h ef w n ba l g o r i t h mw i t ht h en a i v en a i v eb a y e s i a nc l a s s i f i e r , b a y e s i a n n e t w o r k sa n dn b t r e e ，a n dw i t ht h ew e i g h t e dn a i v eb 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 m b a s e do nr o u t hs e ti nl i t e r a t u r e2 6 ，an a i v eb a y e s i a nc l a s s i f i e ra l g o r i t h mb a s e do nt h e r o u g hs e ti nl i t e r a t u r e3 2 ，e x p e r i m e n t a lr e s u l t ss h o wt h a ti nm o s td a t a - s e t s ，f w n b a l g o r i t h mh a sah i g h e rc l a s s i f i c a t i o na c c u r a c ya tt h ec o s to fl e s sc o m p u t a t i o n t h ef w n bc l a s s i f i e ri sd e s i g n e dt ot h eg u i d a n c eo fg e r m a n yc r e d i ti no r d e rt o v a l i d a t ei t sc l a s s i f i c a t i o na c c u r a c y c o m p a r e dw i t ht h en e u r a ln e t w o r km o d e lb yw e s t , a n dx u - s h e n gl ie ta 1 p r o p o s e da ne x t e n s i o no ft h et r e ea u g m e n t e dn a i v eb a y e s i a n n e t w o r k ，e x p e r i m e n t a lr e s u l t ss h o wt h a t ，f w n bi ss i g n i f i c a n t l yb e t t e rt h a no t h e r a l g o r i t h m si nt h ec l a s s i f i c a t i o na c c u r a c y k e yw o r d s ：n a i v eb a y e s i a nc l a s s i f i e r , f e a t u r ew e i g h t i n g ，b a y e s i a nn e t w o r k s ，r o u g h s e t s 重庆交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 砂阅为 日期：9 d 年占月 7 日 重庆交通大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权重庆交通大学可以将本学位论文的全部内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中国科 学技术信息研究所将本人学位论文收录到中国学位论文全文数据库，并进行 信息服务( 包括但不限于汇编、复制、发行、信息网络传播等) ，同时本人保留 在其他媒体发表论文的权利。 一 f 学位论文作者签名：矽l 多i 才指导教师签名： 髟p f 矽 日期：歹l9 年6 月7 日日期：沙即年6 月日 本人同意将本学位论文提交至中国学术期刊( 光盘版) 电子杂志社c n k i 系 列数据库中全文发布，并按中国优秀博硕士学位论文全文数据库出版章程规 定享受相关权益。 f 学位论文作者签名：少闭才指删币签名形仁 日期：歹。f 戽6 月7 日日期：瑚fo 年6 月7 日 第一章绪论 第一章绪论 本章主要介绍本文的研究背景：数据挖掘( d a t am i n i n g ，d m ) 的基本概念，数据 挖掘过程和功能，以及研究现状和发展趋势。并重点介绍了其中的分类问题，此 外还给出了本文的组织结构。 1 1 研究背景与意义 随着数据库技术和计算机网络的迅猛发展，使得数据库领域的新内容、新应 用、新技术层出不穷，导致信息资源高速膨胀。信息资源中包含大量的数据，如 何把大量的数据转化为有用的知识是数据挖掘领域面临的一个重要研究课题。数 据挖掘作为一门处理数据的新兴技术，与传统的数据处理方法相比，具备以下几 个特征：( 1 ) 数据挖掘是面向海量的数据；( 2 ) 数据是不完全的、有噪音的，甚至 有复杂和异构的数据结构；( 3 ) 数据挖掘是一门交叉的学科，运用了统计学、计算 机、数学等学科技术。数据挖掘技术的产生和发展是随着计算机及其相关技术的 发展起来的，其中起决定性作用的相关技术包括：数据库、数据仓库和i n t e m e t 等 信息技术的发展；计算机性能的提高和先进的体系结构的发展；统计学和人工智 能等方法在数据分析中的研究和应用。这些技术的日益成熟一定程度上为数据挖 掘技术的发展起了极大的推动作用，目前数据挖掘技术已成为数据库和信息决策 领域的研究热点之一。 近年来，随着计算性能不断提高以及海量数据库大量出现，从数据中学习高 精度的分类器一直是数据挖掘领域的研究热点。而朴素贝叶斯分类器是学习效率 和分类效果均较好的分类器之一，不仅具有坚实的数学理论基础，而且有着广泛 的实际应用价值。朴素贝叶斯方法可以应用于选股嘲、文本分类( t e x t c a t e g o r i z a t i o n ) 和超文本分类汹1 、地形评估汹1 、垃圾邮件过滤( s p a r ed e t e c t i o n ) 等。例如，m i c r o s o f t 推出的智能电子邮件过滤软件m o b i l em a n a g e r ，其不仅能够自动将收到的电子邮 件归类存档等，还可以自动记忆用户的使用习惯，并以此为根据将较重要的邮件 立刻转发到用户的手机上。 1 - 2 数据挖掘基本概念 数据挖掘( d a t am i n i n g ) ，是从大量的、不完全的、有噪音的、模糊的数据 2第一章绪论 中获取有效、新颖、潜在有用的、最终用户可理解的知识的非平凡过程。数据挖 掘的广义观点，就是从存放在数据库、数据仓库或其他信息库的大量数据中“挖 掘 有趣知识的过程。 数据挖掘的本质是知识发现，它所发现的知识是隐藏在大量数据中的关联信 息，所有的知识是有特定前提和约束条件的，是面向特定领域的，而且，这些知 识还要易于用户理解，并能用自然语言表达。 1 3 数据挖掘的过程 数据挖掘，又称数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a m b a s e ，k d d ) ， 被视为知识发现过程中的一个基本步骤。知识发现过程由以下步骤组成h ： ( 1 ) 数据清理( d a t ec l e a r i n g ) 清理与挖掘主题明显无关的数据以及清除数据噪音。 ( 2 ) 数据集成( d a t ai n t e g r a t i o n ) 其主要功能是将来自多数据源的相关数据组合在一起。 ( 3 ) 数据选择( d a t as e l e c t i o n ) 搜索所有与业务有关的内部和外部数据信息，并从中选择适用于数据挖掘应 用的数据。 ( 4 ) 数据变换( d a t at r a n s f o r m a t i o n ) 其主要功能是将数据转换为易于进行数据挖掘的存储形式。 ( 5 ) 数据挖掘( d a t am i n i n g ) 数据挖掘是知识发现过程的一个步骤，其功能是通过特定算法挖掘数据模式 或规律知识。 ( 6 ) 模式评估( p a t t e r ne v a l u a t i o n ) 根据一定的评估标准从数据挖掘结果中筛选出有意义的模式。 ( 7 ) 知识表示( k n o w l e d g ep r e s e n t a t i o n ) 利用可视化的知识表达方式，向用户展示挖掘出的模式知识。 第一章绪论 数据挖掘的一般过程如图1 1 所示。 图1 1 数据挖掘过程 f i g u r e1 1t h ep r o c e s so f d a t am i n i n g 1 4 数据挖掘的功能 数据挖掘功能主要用于指定数据挖掘任务中要找的模式类型，其任务一般可 以分为：描述和预测。描述性挖掘任务是指刻画数据库中数据的一般特性，而预 测性挖掘任务是在当前数据上进行推断，用于预测。数据的挖掘的功能主要包括 以下几个方面h 5 删： ( 1 ) 概念描述( c o n c e p td e s c r i p t i o n ) 概念描述就是将某类对象关联数据进行汇总、分析和比较，并对该类对象的 内涵进行描述，概括其相关特征。例如，关系数据库中的一张表代表一个对象集， 其中的每条记录( 元组) 可以看作是一个对象，每个对象都有唯一的标识和多个 属性值。由一个或一组属性上取值相同的对象构成一个对象类。 概念描述分为特征性表述和区别性描述。前者是描述某类对象的共同特征， 而后者是描述不同类对象之间的区别。 ( 2 ) 特征规则 特征规则挖掘是将全部数据所满足的概念特征化。特征规则挖掘能够总结用 户所指定数据集的一般特征，并且能够从与学习任务相关的一级数据中提取出特 征式，这些特征涵盖了该数据集的总体特征。例如，可以从某种疾病的病状中提 取出该疾病的特征规则等。 4 第一章绪论 ( 3 ) 分类 在数据挖掘的各种方法中，分类是一种有效的数据分析方法。分类的目标是 将数据集通过分析、训练后，构造成一个分类模型( 即分类器) 。该模型可以把数 据库中的数据记录，映射到一个给定的类别，从而应用于数据预测。分类问题已 经被广泛应用于文本分类、故障诊断h 7 1 、银行贷款信用评估1 等领域。目前得 到广泛研究的分类模型有决策树( d e c i s i o nt r e e ) 、神经网络( n e u r a ln e t w o r k ) 、贝叶 斯分类( b a y e s i a nc l a s s i f i c a t i o n ) ，粗糙集( r o u g hs e t ) 、统计方法( s t a t i s t i c s ) 等。 本文主要研究的是基于粗糙集的朴素贝叶斯分类器的改进，研究结果表明， 基于粗糙集理论的特征加权朴素贝叶斯分类器在分类正确率和效率上都有了显著 提高。 ( 4 ) 关联规则 数据关联是数据库中一类重要的可被发现的知识。若两个或多个变量的 取值之间存在着某种规律性，就称为关联。关联可分为简单关联、时序关联、 因果关联。关联分析的目的是为了找出数据库中隐藏的关联网。a g r a w a l 等于 1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题1 ，关联规 则挖掘逐渐成为数据挖掘中的一个重要课题，最近几年已经被业界广泛研究。 关联性分析广泛应用于交易数据的分析，通过分析结果来制定销售、目录设 计和其他市场决策。例如，在分析美国沃尔玛超市的销售记录时，发现下班 后购买婴儿尿布的多数男性顾客同时也会购买啤酒。借助数据挖掘技术对大 量交易数据进行挖掘分析，沃尔玛才发现数据内在这一有价值的规律。 关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中 找出所有的高频项目组( f r e q u e n ti t e m s e t s ) ，第二阶段再由这些高频项目组产 生关联规贝t j ( a s s o c i a t i o nr u l e s ) 。 ( 5 ) 聚类 如果划分的类是未知的，那使用分类对数据进行分析是不可行的。聚类分析 是在预先不知道划定类的情况下，根据信息相似度原则进行信息聚集的一种方法， 是一种基于无指导的学习，所划分的类别是未知的。聚类的目的是根据最大化类 内相似性，最小化类间相似性这一原则合理的划分数据集合，并用显式或隐式的 方法描述不同的类别。 ( 6 ) 预测分析 预测是构造并使用模型评估无标号样本类，或给定样本类所可能具有的属性 值或值区间。分类和回归是预测的两类问题，其中分类是预测离散或标称值，而 回归是用于预测连续或有序值。预测主要指根据预测模型和已知数据项，对该数 第一章绪论 据项待定属性值进行预测，其也包含了可用数据的分布趋势识别，连续性预测可 用于回归统计技术建模。 1 5 数据挖掘的研究现状和发展方向 数据挖掘的理论研究工作主要体现在以下三个方面：一是对知识发现方法的 进一步研究，如近年来注重对贝叶斯方法以及b o o s t i n g 方法的研究；二是传统的 统计学回归法在数据挖掘中的应用；三是数据挖掘技术与数据仓库的结合越来越 紧密。在实际应用方面，数据挖掘工具软件层出不穷，国内外很多计算机公司都 非常重视数据挖掘系统的开发应用。以下是两个典型的工具软件：s a s 公司的 e n t e r p r i s em i n e r 和i b m 公司的i n t e l l i g e n tm i n e r 。 e n t e r p r i s em i n e r 是s a s 公司研发的数据挖掘工具，它支持s a g 统计模块， s a g 使用它的s e m m a 方法学可提供一个能支持包括关联、聚类、决策树、神经元网 络和统计回归在内的范围广阔的模型数据挖掘工具，主要支持市场划分分析、分 类、预测模型、顾客分析、计量经济时序的统计分析范围、运作研究等许多方面 的应用。 i n t e l l i g e n tm i n e r 是i b m 公司研发的数据挖掘工具，采用了多种统计方 法和挖掘算法，主要有：单变量曲线、双变量统计、线性回归、因子分析、 主变量分析、分类、分群、关联、相似序列、序列模式和预测等。 数据挖掘的研究正在推向高潮，研究的焦点主要集中在以下几个方面h 州4 3 3 ： ( 1 ) 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也许 会像s q l 语言一样走向形式化和标准化。 ( 2 ) 挖掘中可视化方法：寻求数据挖掘过程中的可视化方法，使知识发现过程 能够被用户理解，也便于在知识发现的过程中进行人机交互。 ( 3 ) 研究网络环境下的数据挖掘技术( w e b m i n i n g ) ，特别是在因特网上建立 d m k d 服务器，并与数据库服务器配合，共同实现w e b m i n i n g 。 ( 4 ) 加强对各种非结构化数据的开采，如对文本数据、图形数据、视频图像数 据、声音数据乃至综合多媒体数据的开采；处理的数据将涵盖更多的数据类型， 如比较复杂的，或者结构较为独特的数据。为了更好的处理这些数据，通常还需 要一些新的、好的分析和建立模型的方法，并且还可能制作一些针对费时和复杂 数据的工具和软件。 ( 5 ) 挖掘方法和用户的交互问题：这反映在所挖掘的知识类型、在多粒度上 挖掘知识的能力、领域知识的使用、特定的挖掘和知识显示。 6第一章绪论 ( 6 ) 性能问题：包括数据挖掘算法的有效性、可伸缩性和并行处理以及分布式 和增量挖掘算法。 1 6 数据挖掘中的分类问题 数据分类( c l a s s i f y ) 是数据挖掘和机器学习领域的一个重要研究课题，许多数据 挖掘问题本质上都可以等价或转化为分类问题。分类的目标是构造一个分类器， 为特征集描述的实例指定最适合的类标签。 数据分类一般分为两个步骤h ： 第一步：建立分类模型，描述预定的数据类集。通过分析具有属性描述的数 据库元组来构造模型。常用的分类器模型有决策树、决策表、贝叶斯方法、神经 网络和遗传算法等。 第二步：使用建好的分类模型对新的数据集进行划分，主要考虑分类规则的 准确性、矛盾划分的取舍等。一个好的分类规则集合应该对新的数据集具有很高 的准确度、尽可能少的矛盾划分和较少的规则集。 1 6 1 常见的分类方法举例 一、决策树 决策树是常用的分类方法之一，较早的被应用于数据挖掘中的分类问题。它 是一种树型结构，其每一个内部结点表示在一个属性上的测试，并且该结点的每 个后继分支与该属性的一个可能值相对应，每个叶子结点表示类或类分布，树的 最顶层结点为根结点。分类实例的方法采用自项向下的递归式，在决策树的内部 结点可得到该实例的类别。 决策树分类方法一般情况下分两步构造分类器瞄幻：树的生成与树的剪枝。在 树的生成阶段，决策树通过反复分拆训练集而成。在每一次分拆时，都是利用某 种分拆规则选择一个属性。因所选属性值不同而将训练集分成多个子集。然后在 每个子集上重复同样的分拆过程，直至每个分拆后的训练集子集样本均属于同一 类别为止。 二、贝叶斯方法 贝叶斯理论是处理不确定性信息的重要工具。作为一种不确定性推理方法， 它基于概率和统计理论，具有坚实的数学基础，贝叶斯网络在处理不确定信息的 智能化系统中已经得到了广泛的应用，并且成功地用于医疗诊断、统计决策、专 家系统等领域。这些成功的应用，充分说明了贝叶斯技术是一种强有力的不确定 第一章绪论7 性推理方法。贝叶斯分类器分为两种：一种是朴素贝叶斯分类器，另一种贝叶斯 网分类器。 朴素贝叶斯分类器是一种有监督的学习方法，其假定个属性的值对给定类 的影响而独立于其他属性值，此限制条件较强，现实中往往不能满足，但是朴素 贝叶斯分类器取得了较大的成功，表现出高精度和高效率，具有最小的误分类率， 耗时开销小d 1 的特征。贝叶斯网分类器是一种有向无环图模型，能够表示属性集 间的因果依赖。通过提供图形化的方法来表示知识，以条件概率分布表表示属性 依赖关系的强弱，将先验信息和样本知识有机结合起来；通过贝叶斯概率对某一 事件未来可能发生的概率进行估计，克服了基于规则的系统所具有的许多概念和 计算上的困难。其优点是具有很强的学习和推理能力，能够很好地利用先验知识， 缺点是对发生频率较低的事件预测效果不好，且推理与学习过程是n p h a r d 的。 三、神经网络 神经网络方法是参考生物神经系统结构和功能而建立起来的，模拟人脑神经 元的方法。以m p 模型和h e b b 学习规则为基础，可以建立三大类神经网络模型： 前馈式网络，反馈式网络和自组织网络。利用神经网络所固有的并行结构和并行 处理、自适应性、知识的分布存储、较强的容错性、本质的非线性系统等特性， 通过网络训练，建立数据库信息的非线性模型，并从中提取出相应的规则。 目前神经网络模型很多，反向传播( e r r o rb a c kp r o p a g a t i o n , b p ) 模型是最典型的 神经网络。b p 算法可以对网络中各层的权系数进行修正，故适用于多层网络的学 习。b p 算法是目前应用最广泛的神经网络学习算法之一，在自动控制中是最有用 的学习算法。 四、遗传算法 遗传算法( g e n e t i ca l g o r i t h m ) 是模拟达尔文的遗传选择和自然淘汰的生物进化 过程的计算模型盼7 1 。它的思想源于生物遗传学和适者生存的自然规律，是具有“生 存+ 检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象， 并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交 叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数 的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。作 为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处 理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果， 并逐渐成为重要的智能算法之一。 五、粗糙集理论 粗糙集理论h 订可以用于分类，发现不准确数据或噪声数据内在的结构联系， 它用于离散值属性。粗糙集理论基于给定训练数据内部的等价类的建立，形成等 8第一章绪论 价类的所有数据样本是不加区分的。粗糙集理论是用元素的成员关系函数、概念 的上近似和下近似等来刻划知识处理的方法。由不可区分关系确定给定论域的等 价类，使用粗糙集合相应的公式计算条件属性和决策属性的依赖性，通过数据约 简在保持分类一致的约束下简化样本数据，从而削减冗余对象和属性，寻求属性 提取最小子集以确保产生满意的近似分类，由此得出知识的相对约简和相对核以 及种类的相对约简和相对核等目标数据，通过对目标数据的分析，使用较少的逻 辑规则就能描述分类规则。 1 6 2 分类器的评价标准 分类方法的研究成果很多，分类器可以从以下几个方面进行评价： ( 1 ) 预测准确度：预测准确度是评价分类器最为广泛的一种比较尺度，可用于 评价一个分类器，对非样本数据的判断准确度；常见的两种方法是保持和k 次n 交叉验证法。 ( 2 ) 计算复杂度：方法实现时对时间和空间的复杂度；计算复杂度往往依赖于 具体的实现细节和硬件环境。在数据挖掘中，时间和空间复杂度是评价分类器的 一个重要尺度。 ( 3 ) 模式描述的简洁度与可解释性：对于描述型的分类任务，模型描述越简洁， 越易解释，越受欢迎。分类器是通过特定算法挖掘出的模式，这些模式最终是面 向特定领域用户的，因此挖掘出的模式要易于理解，以便于用户决策。 ( 4 ) 健壮性：健壮性是衡量分类器优劣的一个方面，也是分类器抗干扰能力的 度量。现实生活中的数据总存在噪音数据，而对存在噪音数据的数据集，能否得 出好的分类器以及给出正确分类的能力。 ( 5 ) 可伸缩性：目前大部分的分类算法是基于数据规模很小的假设。算法的可 伸缩性意味着对于大量数据能否具有有效的构造模型的能力。 而且，分类效果一般与具体的应用领域以及数据的特点相关。并不存在一种 对于所有的数据集都最优的分类算法，即不存在一种方法能适用于任何应用，适 合各种特点的数据集。 1 7 论文的组织结构 本文的具体组织结构如下： 第一章绪论：本章主要简述数据挖掘的基本概念，过程和功能，以及研究现 状和发展趋势，详细阐述了数据挖掘中各种分类问题的定义、方法以及分类模型 第一章绪论 9 评价的标准等。最后一节简要给出了文章的组织结构。 第二章朴素贝叶斯网分类器：重点讨论贝叶斯理论与贝叶斯分类模型的数理 统计基础理论。然后，针对朴素贝叶斯假设的应用不足，讨论了对于朴素贝叶斯 分类器的各种改进模型。最后，给出本章小结。 第三章粗糙集理论与应用：首先，介绍了粗糙集的基本理论，以及研究现状 和应用。然后，在下一章将使用粗糙集基本理论来改进朴素贝叶斯分类器。 第四章基于粗糙集的特征加权算法：首先，简述了特征加权朴素贝叶斯分 类步骤，对一种新的基于粗糙集理论的特征加权朴素贝叶斯分类算法进行仔细分 析。最后，通过数值实验和对比实验验证了该算法的有效性，并给出结论。 第五章基于粗糙集的特征加权算法( f w n b ) 在德国信用数据中的应用：首先 描述了德国信用数据集，并在此基础上与w e s t 的神经网络模型口铂以及李旭升等人 提出的扩展的树增强朴素贝叶斯网络1 进行了实验比较。最后，给出实验结果及 分析。 第六章总结与展望：对本文工作总结并提出下一步的工作展望。 l o 第二章贝叶斯理论与贝叶斯分类模型 2 1引言 第二章贝叶斯理论与贝叶斯分类模型 数据分类是数据挖掘和机器学习领域的一个重要研究课题，在各种不同领域 中应用广泛。分类的目标是构造一个分类器，对特征集描述的实例指定最适合的 类标签。从数据中学习高精度的分类器近年来一直是研究的热点。各种不同的方 法都可以用来学习分类器。例如：人工神经元网络( n e u r a ln e t w o r k s ) ，决策树，支 持向量机，非参数学习算法等等汹3 。与其他精心设计的分类器相比，贝叶斯分类 算法n 2 3 可以与决策树算法和神经网络算法相媲美，是学习效率和分类效果最好的 分类器之一。 贝叶斯方法是统计学分类方法，是建立在经典的贝叶斯概率理论和图论基础 上的分类模型，本章主要介绍贝叶斯基本理论和几种常见的贝叶斯分类模型。 2 2 概率论基础 2 2 1 条件概率和乘法定理 在事件a 已经发生的条件下，事件b 发生的概率，称为事件b 在给定事件a 的条件概率( 也称为后验概率) ，条件概率表示为p ( b i a ) 。相应地，p ( a ) 称为无条 件概率( 也称为先验概率) 。 定义2 1 ：设彳，召是任意两个事件，且尸例 o ，则条件概率公式为：在事件彳 已经发生的条件下，事件曰发生的条件概率为： p ( b i4 1 ：! ! 丝：星! ( 2 1 ) 由条件概率的定义可得 定理2 1 ： 若对任意两个事件彳，b 都有尸例 0 ，尸倒 0 ，则 p ( a s ) = p ( 彳) 尸( bi 么) = p ( b ) p ( ai 功 ( 2 2 ) 称公式( 2 2 ) 为乘法公式，称此结论为乘法定理。 第二章贝叶斯理论与贝叶斯分类模型 定理2 2 ： 设彳j ，a z , ，a 一为任意n 个事件，n _ 2 且p ( a l ，a 2 ，彳 0 ，则有 e ( 4 4 4 ) = p ( 4 ) p ( a 2l4 ) p ( ai4 4 ) p ( 4 ll4 4 以一。)( 2 3 ) 2 2 2 全概率公式和贝叶斯公式 定理2 3 ：设试验e 的样本空间为s ，a 1 ，a 2 ，a m 为样本空间s 的一个划分， 且尸口护0 ( i - 1 ，2 ，o a ) ，则对任意事件b ，有 尸( b ) ：窆尸( 4 ) 尸( 召l4 ) ( 2 4 ) i = 1 上式称为全概率公式。 由条件概率的定义及全概率公式有： 尸( a j l b ) = 等= 警， p ( 占) = 尸( 爿，) p ( b i 么，) 得出p r 、一p ( a ) p ( b i a ) 尸( 彳，i 曰) = 一 尸( 4 ) p ( 召i4 ) 上式称为贝叶斯定理m 1 。 2 2 3 极大后验假设与极大似然假设 ( 2 5 ) ( 2 6 ) ( 2 7 ) 贝叶斯定理提供了一种检验假设h 概率的方法，它基于h 的先验概率，给定 假设下观察到不同数据的概率以及观察到的数据本身。用尸例表示没有训练数据 前假设h 的先验概率。尸例被称为h 的先验概率( p r i o r p r o b a b i l i t y ) ，表示关于h 是正 确假设的概率的背景知识。用尸倒表示将要观察的训练数据d 的先验概率，即在 没有确定某一假设成立时d 的概率。尸pj 缈表示假设h 成立的情况下数据d 的概 率。我们需要求出给定训练数据d 时h 成立的概率，即h 的后验概率p 仍i 功，则 由贝叶斯公式求得计算后验概率尸仍i 纠的方法： p ( hld ) ：p ( d i h ) p ( h ) 尸( z ) )( 2 8 ) 定义2 2 ：极大后验假设：在许多学习场景中，学习器考虑候选假设集合h 1 2第二章贝叶斯理论与贝叶斯分类模型 并在其中寻找生成数据d 的可能性最大的假设h h 。这样具有最大可能性的假设 被称为极大后验假设( m a ) 【i m 啪ap o s t e r i o r i ，m a p ) 枷，记作：玩御。 删肚a r g 脚m a x ( ) = a r g 脚m a x 蒯铲= a r g 枷m a x p p ( 叩( 2 9 ) e h e h i 上，j e 由于p 倒是不依赖于h 的常量，所以我们去掉p 俐，并用归一化因子a 代替， 上式就是一个基本的分类模型。贝叶斯分类就是根据m a p 假设找出的新实例最有 可能的分类。所有对贝叶斯分类模型的研究工作都隐含以此假设为前提条件。 在某些情况下，可假设日中的每个假设都有相同的先验概率( 即对日中的任 意h j 和吩，都有p 伪l j 印例，此时可进一步简化计算，只考虑p ( d i h ) 来寻找极大可 能假设。p p l 砂被称为极大似然假设( m a x i m u ml i k e l i h o o d ，m l ) ，记作， = a r g m a x p ( d i 厅) ( 2 1 0 ) e 圩 通常把数据d 称作某目标函数的训练样本，而把日称为候选目标函数空间。 2 2 4 事件的独立性 设么，b 是试验e 的两个事件，一般彳的发生对b 发生的概率是有影响的， 这时p 俾l 创p 例，只有当这种影响不存在时才会有尸伊i ：p 倒，这时有： p 口印= p 伊i 尸f 冽= p 扛砂尸f 矽( 2 1 1 ) 则称彳，b 为相互独立事件。 同理，对于n 个事件a l , a z ，以，如果当公式( 2 1 2 ) 成立， 尸口，a 2 彳= 尸似p ( a 2 ) p 似( 2 1 2 ) 则称a j ，彳另，a 一为相互独立事件。 2 3 图论基础 定义2 3 ：有向图g ：是由结点集v ，边集e 表示的二元组g = e ) 。若( x ，”e 表示从结点x 到结点y 有一条有向边，也称结点x 和结点y 是邻接的。x 被称为y 的父亲结点，y 被称为x 的孩子结点。通过父亲和孩子概念的递归定义，同时获得 祖先和后继的两个概念。没有父亲结点的结点被称为根结点。 定义2 4 - d a g ( d i r e c t e da c y c l i cg r a p h ) ：称为有向无环图，即不包含环路的有 向图。 第二章贝叶斯理论与贝叶斯分类模型 2 4 贝叶斯分类模型 分类有基于规则的分类( 查询) 和非规则分类( 有指导学习) 。贝叶斯分类 是非规则分类，它通过训练集( 已分类的例子集) 训练而归纳出分类器( 被预测 变量是离散的称为分类，连续的称为回归) ，并利用分类器对未分类的数据进行 分类。贝叶斯分类器中有代表性的分类器有朴素贝叶斯分类器、贝叶斯网络分类 器和树增强朴素贝叶斯分类模型t a n 等。 贝叶斯分类具有如下特点：( 1 ) 贝叶斯分类并不是把一个实例绝对指派给某一 类，而是通过计算得出属于某一类的概率，具有最大概率的类是该实例所属的类。 ( 2 ) 一般情况下在贝叶斯分类中的所有属性都直接或间接地发挥作用，即所有的属 性都参与分类，而不是一个或几个属性决定分类。( 3 ) 贝叶斯分类实例的属性可以 是离散的、连续的，也可以是混合的。 假设彳j ，彳2 ，a 疗是数据集的n 个特征( 属性) ，假设有m 个类， c = 心，c 2 ，c 宝，c 用夕给定一个具体的实例工其属性为 x l , x 2 ，x n ，这里x i 是属 性彳，的具体取值，该实例属于某一个类g 的后验概率是尸闭c o ，c 仞表示分类所 得的类标签。贝叶斯分类器表示为： c ( x ) = a r g m a xp ( c f ) p ( xlc f ) 瞄1 j j g e c 即预测实例x 属于在属性给定条件下后验概率最大的类别时，预测的正确率最大。 2 4 1 朴素贝叶斯分类模型 但是公式( 2 1 3 ) 的后验概率难以计算，因此朴素贝叶斯分类器引入了以下假设： 在给定类别c 的条件下，所有的属性a i 相互独立。即： e ( 4ic ，4 ) = p ( 4ic ) ，v a i ，a j ，尸( o 0( 2 1 4 ) 公式( 2 1 4 ) 被称为“朴素贝叶斯假设 。 1 4第二章贝叶斯理论与贝叶斯分类模型 用贝叶斯网表达的朴素贝叶斯分类器如图2 1 所示嗍。 图2 1 朴素贝叶斯分类器 f i g u r e2 1n a i v eb a y e s i a nc l a s s i f i e r 在朴素贝叶斯分类算法中，既可以独立的学习每个属性彳，在类别属性c 下的 条件概率p 口f i a ，也可以独立学习每个属性彳，的概率，因该值为常数，可用归一 化因子a 来代替。然后，分类器应用贝叶斯公式计算特定实例数据在给定属性值 下类别的后验概率： e ( c = cl4 = a t 以= a n ) = 口尸( c = c ) ii p ( a , ic = c ) ( 2 1 5 ) i = l 并预测该实例属于后验概率最大的类别。 2 4 1 1 朴素贝叶斯分类器的学习和分类 根据公式( 2 1 5 ) 口j 知，最优阴分灭c 2 白应该i 司h 丁满足： 北，q ) = 篱北) 亿1 6 p ( qi ) p ( c jl ) j i + ( 2 1 7 ) 类别c 的先验概率分布可以简单的从训练集数据中获得其最大似然估计，等于不 同类别属性在数据集中出现的频度，计算复杂度为o o d p 。 b ( c ) = 竺c o 等u n t ( 等 。 d 1 u l 石j 由于实例 的概率p ( ) 是一常数，在计算中仅进行归一化处 理，因此，学习的过程主要是通过训练集估计属性的后验概率p ( l 砂。根 第二章贝叶斯理论与贝叶斯分类模型 据朴素贝叶斯假设，应用贝叶斯公式展开， p ( ic ) = 1 - i p ( a tic ) ，l l 公式( 2 1 9 ) d f 右边的每一项均可以用下式估计： ( 2 1 9 ) b ( a , i 加瓣铲 ( 2 2 。) 公式( 2 2 0 ) 给出了最大似然度下的基于训练数据集的参数估计值，同样可在o ( i d p 时间内计算。 朴素贝叶斯分类模型的优势是： 1 ) 算法逻辑简单，易于实现； 2 ) 分类过程中时间、空间开销小； 3 ) 算法性能稳定，对于不同的数据特点其分类性能差别不大，即模型健壮性 比较好。 2 4 1 2 朴素贝叶斯分类模型的改进 朴素贝叶斯分类器( n a i v eb a y e s i a nc l a s s i f i e r , n b c ) 由于计算高效、精确度 高，并具有坚实的理论基础而得到广泛的应用。朴素贝叶斯分类器基于条件独立 性假设，即假设一个属性对给定类的影响独立于其他属性，当条件独立性假设成 立时，朴素贝叶斯分类算法具有最小的误分类率口3 。尽管这一假设一定程度上限制 了朴素贝叶斯分类器的适用范围，然而在实际应用中，不仅以指数级的降低了朴 素贝叶斯模型构建的复杂度，而且在许多领域在违背这种假设的条件下，朴素贝 叶斯也表现出相当的健壮性和高效性，它已经成功地应用到分类、聚类及模型选 择等数据挖掘的任务中。 但朴素贝叶斯假设在实际中往往并不成立，多少影响了朴素贝叶斯分类器的 分类效果。为了改进朴素贝叶斯分类器的性能，人们提出了许多方法和技术，每 一种都在一定程度上对某些类型的问题改进了朴素贝叶斯分类器的分类精度。这 些方法包括：树增强朴素贝叶斯( t r e ea u g m e n t e dn a i v eb a y e s ( t a n ) ) 乜1 ，模糊神经 学习阳1 ( n e u r o f u z z yl e a r n i n g ) ，惰性贝叶斯规则( l a z yb a y e s i a nr u l e s ) d a 概率调 整n 力，广义朴素贝叶斯分类器阳蚓( g e n e r a l i z e dn a i v eb a y e sc l a s s i f i e r s ) ，特征加权 ( w e i g h t e dn a i v eb a y e s ( w n b ) ) n 力列蚓，完全贝叶斯分类器( f u l lb a y e s i a n n e t w o r kc l a s s i f i e r s ( f