（应用数学专业论文）基于连续型数据的朴素贝叶斯分类器的改进研究.pdf

中山大学硕士学位论文 基于连续型数据的朴素贝叶斯分类器的改进研究 专业：应用数学 硕士生：刘彩通 指导教n - 张磊副教授 摘要 样本分类是数据挖掘一项非常重要的任务，在众多分类方法和理论中，贝叶 斯分类方法具有坚实的统计理论基础，其简单形式是朴素贝叶斯方法( n b c 模 型) ，由于具有简单快速的计算过程及泛化能力强等优点，n b c 模型得到了广泛 应用。本文着重研究基于连续型数据的朴素贝叶斯分类器，探讨基于属性加权及 增量学习的改进方法。 在属性加权改进方法上，本文引进f i s h e r 判别分析理论定义各属性的分类权 重，提出了f i s h e r 加权朴素贝叶斯分类器( f w n b c 模型) ，通过实验分析表明 f w n b c 模型在一定程度上提高了朴素贝叶斯分类器的准确率。 在增量学习方法上，由于朴素贝叶斯对数据作高斯分布假设，本文首先应用 有限混合模型思想分析分类器的参数求解过程实质上是高斯混合模型的参数估 计过程。接着讨论e m 算法在高斯混合模型参数估计问题上的应用，提出增加未 标注训练样本的结合e m 算法的朴素贝叶斯分类器( e m n b c 模型) 。实验表明当 数据对朴素贝叶斯有较好的类可分性时，e m n b c 模型可以明显地提高参数估计 精确性和分类准确率。 当数据的类可分性较差时，本文将传统n b c 模型与e m n b c 模型通过线性 组合设计组合e m n b c 模型与加权组合e m n b c 模型，并用实验表明组合模型 有相对稳定的表现，准确率较传统n b c 模型有一定提升，加权后的组合e m n b c 模型能使准确率有进一步提升。 关键词：朴素贝叶斯，f i s h e r 加权方法，有限混合模型，e m 算法，参数估计 中山大学硕士学位论文 ar e s e a r c ho nt h ei m p r o v e m e n to fn a i v eb a y e s c l a s s i f i e rb a s e d0 1 1c o n t i n u o u sd a t a m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：l i uc a i t o n g s u p e r v i s o r ：z h a n gl e ia s s o c i a t ep r o f e s s o r a bs t r a c t c l a s s i f i c a t i o ni sav e r yi m p o r t a n tm i s s i o no fd a t am i n i n g i nm a n yc l a s s i f i c a t i o n m e t h o d sa n dt h e o r i e s ，b a y e sm e t h o dh a sah a r da c a d e m i cb a s e ，a n dn a i v eb a y e s c l a s s i f i e r ( n b c ) i si t ss i m p l ef o r m b e c a u s eo fi t sq u i c kc o m p u t a t i o na n dh i g l l g e n e r a l i z a t i o na b i l i t y , n b ch a sb e e nw i d e l yu s e d t i l i sp a p e rm a i n l ym a k e s r e s e a r c h o nn a i v eb a y e sc l a s s i f i e rb a s e do nc o n t i n u o u sd a t a , a n dd i s c u s s e st h ei m p r o v e d m e t h o db yw e i g h t e da t t r i b u t ea n di n c r e m e n tl e a r n i n g i nt h ed i r e c t i o no fw e i g h t e da t t r i b u t e ，t h i sp a p e ri n t r o d u c e saw e i g h t i n gm e t h o d b a s e do nf i s h e rd i s c r i m i n a t et h e o r y , a n dd e s i g n st h ef i s h e rw e i g h t e dn a i v eb a y e s c l a s s i f i e r ( f w n b c ) t h er e s u l to fe x p e r i m e n ti n d i c a t e st h a tf w n b c c a l li m p r o v e t h ea c c u r a c yo f n b ct oac e r t a i nd e g r e e i nt h ed i r e c t i o no fi n c r e m e n tm e t h o a , b e c a u s en b ce m p l o y sg a u s sa s s u m p t i o n i n t os a m p l e s ，t h i sp a p e rf t r s f l ya n a l y s e st h a tt h es u b s t a n c eo ft h en b ci st h ep a r a m e t e r e s t i m a t i n gc o u r s eo ft h eg a u s sm i x t u r ed i s t r i b u t i o nm o d e l ，a n dt h e ni n t r o d u c e se m a l g o r i t h mi n t ot h ee s t i m a t i n gp r o g r e s s f i n a l l yi td e s i g n san e wc l a s s i f i e r ( e m n b c ) b r i n g i n gi nu n l a b e l e ds a m p l e sa n da p p l y i n ge ma l g o r i t h m t oo p t i m i z et h ep a r a m e t e r e s t i m a t i n gc o u r s e e x p e r i m e n tr e s u l t si n d i c a t et h a tw h e nt h ed a t ah a sg o o dc l a s s s e p a r a b i l i t yt on b c ，e m n b cc a l lc a l t yo u tr e m a r k a b l yb e t t e rp e r f o r m a n c et h a n t r a d i t i o n a ln b cb o t hi np a r a m e t e re s t i m a t i o na n dt h ea c c u r a c yo ft h ec l a s s i f i c a t i o n w h e nt h ec l a s ss e p a r a b i l i t yi sn o tg o o d ，t oi m p r o v et h ep e r f o r m a n c eo fe m n b c ， i tc o m b i n e st r a d i t i o n a ln b ca n de m n b ct od e s i g nac o m b i n e dm o d e l 1 1 l er e s u l t so f e x p e r i m e n ti n d i c a t et h 【a tc o m b i n e de m n b cc a ng a i nas t a b l e rp e r f o r m a n c ea n d h i g h e ra c c u r a c yt h a nb o t ht r a d i t i o n a ln b c a n de m n b c ，f u r t h e r m o r et h ew e i g h t i n g c o m b i n e de m n b cc a np e r f o r mf u r t h e ri m p r o v e m e n t k e yw o r d s ：n a i v eb a y e sc l a s s i f i e r , f i s h e rw e i g h t i n gm e t h o d ，l i m i t e dm i x t u r e m o d e l ，e ma l g o r i t h m ，p a r a m e t e re s t i m a t i n g 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：吝d 弼通 日期：矽fo 年r 月7e t 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：袁丑霖5 通 日期：矽o 年t - 月叩e l 导师签名： 日期：7 , 4 日 中山大学硕士学位论文 第一章绪论 1 1 论文的研究背景和意义 随着社会的信息化发展，各行业所积累的数据量的迅速增长，在海量的数据 背后隐含着很多有潜在价值的信息，如何将数字符号背后隐藏的信息提取出来引 起了学术界的广泛关注，也成为近几年来学术界的研究热点，应运而生的就是数 据挖掘技术。样本分类是数据挖掘一项非常重要的任务，在现实生活和经济活动 中有着广泛应用，比如在通信行业，通过对客户的信息进行分析，按客户特征对 客户群进行分类；又如在医疗行业中，可以根据病人的各项检查指标判断他是否 患有某种疾病。分类技术作为数据挖掘领域的重要研究课题，具有极为重要的实 用价值和研究意义。常见的构造分类器的方法有贝叶斯方法【1 1 、决策树方法【2 】、 支持向量机方法( s u p p o r t v e c t o rm a c h i n e ，s v m ) 1 3 1 4 、神经网络方法【5 1 、基于关 联规则的方法c b a 6 1 ，c m a r 7 ，c p a r t 8 1 等等。 分类数据挖掘中的数据类型分为离散型和连续型，离散型数据是一种泛化数 据，连续型数据是一种量化数据，较离散型数据含更丰富的信息量，在各个领域 都有广泛应用，除上述常见分类器外，专门处理连续变量的分类器有速度较快的 最小距离分类器，基于f i s h e r 准则的线性分类器 9 1 、基于主成分投影的主成分分 类器【l o l 。 在众多分类器中，贝叶斯分类器能够处理离散型和连续型的数据，同时有着 坚实的理论基础、稳定的分类性能、综合先验知识的增量学习特性和丰富的概率 表达能力，这些特点使其成为众多方法中引人注目的焦点之一，成为分类挖掘技 术中尤为重要的方法。但学习最优的贝叶斯分类器和学习贝叶斯网络一样是一个 n p 难问题【l l 】，同时在高维问题上训练贝叶斯网络也比较困难，于是作为其简单 形式的朴素贝叶斯分类器得到广大学者的重视。本文将着重研究基于连续型数据 的朴素贝叶斯分类器的设计及改进方法。 中山大学硕士学位论文 1 2 朴素贝叶斯方法的研究现状 朴素贝叶斯分类方法是形式最简单的贝叶斯分类方法，为了简化贝叶斯分类 的学习过程，它对数据作一个简单而不现实的假定：在给定类标记时属性值之间 相互条件独立，然后利用贝叶斯理论建立基于概率分布函数的分类规则对样本归 类。朴素贝叶斯方法由于计算高效、精确度高、对缺失数据敏感度低，并有坚实 的理论基础而得到了广泛应用【1 2 】。针对朴素贝叶斯分类器的一些局限性，学者 们也提出了许多改进朴素贝叶斯的方法【1 3 1 。 针对类条件独立假设难以满足的局限，贝叶斯网络方法【1 4 】从结构扩展方向 上改进朴素贝叶斯方法的结构，用有向边来表达属性之间的依赖关系，使之可以 代表属性间的依赖关系。在局部学习上，s n n b 算法【1 5 1 、l w n b 算法【1 6 1 ，i c l n b 算法【1 7 】提出在一个局部数据集上建立朴素贝叶斯分类器，虽然类条件独立假设 在整个训练集上不成立，但在某些局部数据集上，属性间的依赖性会比在整个训 练集上弱，局部学习的基本思想就是在一个局部数据集上建立朴素贝叶斯分类 器。在属性选择上，为减少属性间的独立性假定影响，s b c 算法【1 引、c f s 算法 提出了选择贝叶斯分类方法，是一种基于向前选择特征集的方法的选择贝叶斯分 类器，以消除属性依赖对分类性能的影响。 由于经典朴素贝叶斯认为属性的分类重要性是一样的，这样有可能掩盖了一 些对分类贡献比较大的属性的作用。在属性加权方法上，文献【2 0 】提出根据各属 性对分类的重要性赋予它们不同的权重，提出基于信息增益率的加权方法、基于 爬山算法的加权方法、以及基于m a r k o vc h a i nm o n t ec a r l o 的加权方法改进朴素 贝叶斯分类的分类精度。 处理连续型数据时，有学者提出用离散化的方法【2 1 】对处理进行预处理，如 等宽离散化方法 2 2 1 、比例离散化方法1 2 3 1 、基于聚类的离散化方法【2 4 1 、基于熵的 离散化方法【2 5 1 等等。离散化方法能将连续型数据泛化成离散型数据，使数据结 构得到简化，但由于存在离散区间段数目不好确定，无法利用一些先验信息等， 将损失一定原始数据信息，影响分类精度。除属性离散化方法外，一般有两种方 法进行直接处理【2 6 】【2 刀，经典的方法是对数据作高斯分布假设，建立参数模型， 利用高斯分布的密度函数求各样本的类隶属概率。另一种方法是基于核密度的非 参数方法【2 8 j ，它对数据集中的点在一个邻域上用核函数估计，再将这些点的估 2 中山大学硕士学位论文 计作加权求和，分类精度较经典朴素贝叶斯有所提高，但计算效率较慢。 数据的潜在概率分布需要大量的训练样本才能反映出来，在训练样本不足的 情况下，参数估计方法中的概率分布的参数估计值与真实参数值的误差将会比较 大，导致较低分类精度。于是有学者提出用增量学习的方法改进分类精度，如文 献 2 9 1 提出一种基于类支持度的增量贝叶斯学习模型，定义类支持度帮助分类器 选择较优的增量样本，然后添加进训练样本训练分类器。 1 3 本文的主要工作 本文将主要研究朴素贝叶斯分类器( n b c 模型) 在连续型数据分类问题中的 应用和改进。由于将连续型数据离散化将损失原来的信息，尤其在小量样本的情 况下，离散化方法难以进行，因此本文将采用效率较快的参数方法处理连续型数 据，即对数据作高斯分布假设。在以上背景下，本文完成的主要研究工作如下： ( 1 ) 应用混合模型思想分析朴素贝叶斯分类器的工作原理和设计过程，阐述 分类器的训练过程实质上是高斯混合模型的参数估计过程。 ( 2 ) 经典朴素贝叶斯方法认为所有属性对样本的分类的贡献程度是一样的， 但事实上属性与类别之间存在不同的关联程度，朴素贝叶斯算法直接忽略这种关 联性，有可能增加分类误判。因此本文引进f i s h e r 判别分析理论构造f i s h e r 加权 朴素贝叶斯分类模型( f w n b c 模型) ，在一定程度上提高分类准确率。 ( 3 ) 当训练样本不足而又有大量未标注样本时，传统朴素n b c 模型的参数估 计会有较大偏差而得不到较好的准确率，于是本文用增量学习方法，添加未标注 类标的样本引进e m 算法进行模型参数估计的优化，提出结合e m 算法的朴素贝 叶斯分类器( e m n b c 模型) ，在数据的类可分性比较好的情况下较明显地提高分 类器的准确率。 当数据的类可分性较差时，本文提出将n b c 与e m n b c 组合起来设计组合 模型，使e m n b c 模型的分类效果得到改善。最后通过实验验证了组合e m n b c 模型是一个比较稳定的分类器，且准确率较传统n b c 模型高的分类器，加权后 的e m n b c 模型可使准确率得到进一步提高。 3 中山大学硕士学位论文 1 4 本文的主要内容和结构 第一章，主要介绍本论文的研究背景和意义，朴素贝叶斯分类器的简介及研 究现状，还有本文的主要研究工作和章节安排。 第二章，首先介绍贝叶斯理论、朴素贝叶斯分类器的基本原理和设计过程。 对于连续型数据，应用有限混合模型思想分析其设计过程，阐述其训练过程实质 上是混合分布模型的参数估计过程，再提出基于f i s h e r 权重的属性加权方法进行 改进，最后用实验论证加权方法的可行性和有效性。 第三章，详细讨论混合分布模型参数的最大似然估计问题，介绍e m 算法的 原理和步骤，接着阐述e m 算法在高斯混合模型参数估计的应用，最后通过实验 论证e m 算法在参数估计过程中确实是一种有效的方法。 第四章，将未标注类标的样本添加进训练过程，提出结合e m 算法的朴素贝 叶斯分类器( e m n b c 模型) 及组合e m n b c 模型。 第五章，实验分析与结果评价，评价在不同大小的增量训练样本下，各分类 器在参数估计及分类准确率上的表现。 4 中山大学硕士学位论文 第二章朴素贝叶斯分类器及f w n b c 模型的设计 贝叶斯方法提供了基于概率的推理手段，它假设待考查的变量遵循某种概率 分布，且可根据这些概率及已观察到的数据进行推理，从而作出最优的决策，贝 叶斯分类器则是建立在经典的概率理论的基础上的统计分类模型。本章详细阐述 贝叶斯方法的理论基础、贝叶斯分类模型的特点、基于参数方法朴素贝叶斯分类 器的基本原理，以及应用有限混合模型思想讨论朴素贝叶斯器的设计，接着在属 性加权方法上，提出基于f i s h e r 权重的加权朴素贝叶斯分类器( f i s h e rw e i g h t e d n a i v eb a y e sc l a s s i f i e r , f w n b c ) ，最后用实验论证加权方法的可行性和有效性。 2 1 贝叶斯理论概述 贝叶斯理理论的基础f 3 0 1 是有关概率的三个基本公式，由此得到贝叶斯定理。 条件概率：设彳，b 为两随机事件且尸( 4 ) 0 ，事件b 在给定事件彳发生时 的条件概率定义为： 尸( bi 舻篱( 2 - 1 ) 乘法定律：直观上，p ( bi 彳) 是当已知事件么发生时，事件b 发生的概率； p ( b ) 则是在不知道事件么是否发生时，事件b 发生的概率。由( 2 - 1 ) 式可得： 尸( 彳召) = p ( 4 ) p ( b i4 )( 2 2 ) 这称为概率的乘法定律，其含意非常直观：事件彳和b 同时发生的概率，等于彳 发生的概率乘以已知么发生时召发生的概率。 全概率公式：设试验e 的样本空间为s ，彳为e 的事件，b i ，曰：，色为s 的 一个划分，且尸( e ) o ，o = 1 , 2 ，刀) ，则： 一 p ( 彳) = p ( 忍) p ( 么i 忍) ( 2 - 3 ) 贝叶斯定理：由条件概率定义和全概率公式可得贝叶斯公式： 5 中山大学硕士学位论文 尸( ei 彳) ：善型塑上( 2 - 4 ) p ( b , ) p ( ab i )， 当贝叶斯理论用于求解最佳的决策( 或称假设) 时，将用到下面的两个判据。 极大后验假设：在许多学习场合中，决策模型考虑在候选假设集合日中寻 找给定的数据d 时，出现可能性最大的假设h h 。这样具有最大可能性的假设 被称为“极大后验假设 ( m a x i m u m a p o s t e r i r i ，m a p ) ，记作：。 = a r g m m a x p h d = a r g 删m a x 掣铲= a r g 删m a x p d ( 2 - 5 ) h e hh e h r工，heh ( 2 5 ) 式是分类模型的一个原始理论依据，贝叶斯分类器的原理就是依据上述 m a p 假设来找出样本最有可能归属的类别。 极大似然假设：所有对贝叶斯分类模型的研究都是以此假设为前提条件。在 某些情况下，可假定日中的每个假设h 都有相同的先验概率( 即对日中的任意的 吃和乃，7 占p ( h t ) = j p ( ) ) 。这时可以把( 2 5 ) 式进一步简化，只考虑p ( dj 厅) 来寻 找极大可能假设。p ( dh ) 常被称为给定h 时的数据d 的似然度，而使得p ( dh ) 最大的假设称为极大似然假设( 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 ( dh )( 2 6 ) 在给定数据d 后求解最优决策( 假设) 的问题中，我们把数据d 称作某目标函数的 训练样本，而把日称为候选目标函数空间。 在基于贝叶斯理论建模的简化过程中，需要用到独立性条件，下面给出其定 义。 事件的独立性：设彳，b 是试验e 的两个事件，一般么的发生对b 发生的概率 是有影响的，这时p ( a b ) p ( a ) p ( b ) 。称彳，b 为相互独立事件，如果 p ( a b ) = 尸( 彳) 尸( b ) ( 2 - 7 ) 类似地，称九个事件4 ，a 2 ，以为相互独立事件，如果如下条件成立： p ( a l a 2 4 ) = p ( a 1 ) 尸( 彳2 ) p ( a 。)( 2 - 8 ) 6 中山大学硕士学位论文 2 2 贝叶斯分类器 分类问题是对样本类别进行预测的判别分析问题，用于预测类别的模型常称 为分类器。分类有规则分类与非规则分类这两种。贝叶斯分类属于非规则分类， 它通过训练集( 已标注类标的样本集) 的i j l l 练得到分类器( 或称决策函数) ，然后利 用构建好的分类器对未标注类标的样本( 测试集) 进行分类。贝叶斯分类有如下特 占【3 l 】 ( 1 ) 贝叶斯分类不把一个样本绝对地指派给某个类别，而是计算该样本隶属 于各个类的概率，将具有最大概率的类标定为该样本所归属的类。 ( 2 ) 一般情况下贝叶斯分类中所有的属性都起潜在作用，即并不是依据一个 或者几个属性来求解分类决策函数，而是让所有属性都参与分类，经典的贝叶斯 分类器认为各属性对分类的作用是一样的，但其中可能存在某些属性对分类的影 响较大，因此可以根据不同属性的分类贡献程度对分类器进行改进。 ( 3 ) 综合先验知识的增量学习特性，使训练过程可以增量地进行【3 2 j ，降低了 算法的复杂程度，提高算法效率。 ( 4 ) 对缺失数据的敏感度低，当数据缺失率较高时，与其他分类器相比，贝 叶斯分类器可以得到较高的准确率【3 3 1 。 贝叶斯分类器中比较有代表性的有贝叶斯网络分类器、朴素贝叶斯分类器。 贝叶斯网络分类器是当前各种分类方法中最为有效和流行的一种，因为其考虑了 变量之间的相关性，较为符合实际情况，但其参数求解问题仍未彻底解决。朴素 贝叶斯分类器( n a j c v eb a y e sc l a s s i f i e r ，n b c ) i 由于具有简单有效和易于实现的特性 更受到人们的普遍青睐【3 4 】，即使所需的类条件独立假设不被满足，在某些场合 其分类性能仍可与决策树、k 近邻等经典分类器相当。 2 2 1 贝叶斯网络分类器 贝叶斯网络亦称信念网络( b e l i e f n e t w o r l ( ) 【1 4 l ，于是1 9 8 5 年由j u d e a p e a r l 首 先提出，表述联合条件概率分布，并且允许在变量的子集间定义类条件独立性， 提供一种因果关系的图形模型，可以对其进行学习，即求解参数。训练后的贝叶 7 中山大学硕士学位论文 斯信念网络可以用于分类，贝叶斯网络是一个带有概率注释的有向无环图，如图 2 1 。 图中的每一个节点均表示一个随机变量，两节点中若存在着一条弧，则表示 这两节点相对应的随机变量是概率依赖的，反之说明这两个随机变量是条件独立 的。如果一条弧由节点a 。到节点a 2 ，则4 是4 ：的双亲或直接前驱，而彳：是4 的 后代。 图2 1 贝叶斯网络分类模型示意图 给定其双亲，每个变量有条件地独立于图中它的非后代。对于每个变量彳， 信念网络有一个“条件概率表 ( c o n d i t i o n a lp r o b a b i l i t yt a b l e ，c p d ，用以说明条 件分布节点彳在其父节点取各种可能值时的条件概率e ( ap a r e n t s ( a ) ) ，其中 p a r e n t s ( a ) 是a 的双亲。若节点彳无父节点，则彳的c p t 为其先验概率分布。 设x = ( 而，x ：，勤) 是由属性a = ( 4 ，彳：，以) 描述的样本，注意到给定变量 的双亲时，每个变量都有条件地独立于网络图中它的非后代，于是联合概率分布 可以用下式表示： d e ( x i ，而，勤) = 兀p ( 以ip a r e n t s ( a i ) ) ( 2 9 ) 8 中山大学硕士学位论文 网络中的节点可以选作“输出 节点，代表类标号属性。可以有多个输出节 点。分类过程不是返回单个类标号，而是可以返回概率分布，给出样本属于每个 类的概率。 贝叶斯网络分类器的分类过程主要分为两个阶段，第一个阶段是学习网络的 结构和c p t 的学习；第二阶段是贝叶斯网络分类器的推理，即计算类节点的条 件概率，对样本进行分类。这两个阶段的时间复杂性均取决于特征值间的依赖程 度，这是一个n p 完全问题，因而在实际应用中，往往需要对贝叶斯网进行简化， 于是作为其最简单形式的朴素贝叶斯分类器得到广大学者的重视。 朴素贝叶斯模型假设特征向量的各个分量之间相对于类变量是相互独立的， 也就是在各个类中分量之间相互独立地作用于决策变量，尽管这个假设在一定程 度上限制着朴素贝叶斯模型的适用范围，但在实际应用中，大大降低了贝叶斯网 的构建复杂性。针对这一缺点，人们可以通过属性选择，属性加权等方法对分类 器进行改进，使得朴素贝叶斯分类器在实际应用中表现出很好的性能。 2 2 2 朴素贝叶斯分类器 朴素贝叶斯分类法假定在各类中属性变量是条件独立的，即给定样本的类标 号，假定属性的值可以有条件地相互独立，这一假定大大简化了计算复杂性。 设有变量集u = a l ，彳2 ，a d ，c ，其中a 1 ，彳2 ，a d 是数据集的d 个属性变 量，c 是取m 个值的类变量。假设所有的属性变量都条件独立于类变量c ，即每 一个属性变量都以类变量c 作为唯一父节点，就得到朴素贝叶斯分类器( n a i v e b a y e sc l a s s i f i e r , n b c ) t 。 朴素贝叶斯分类模型描述如图2 2 所示。 9 中山大学硕士学位论文 图2 - 2 朴素贝叶斯分类模型示意图 由此可见，朴素贝叶斯是贝叶斯网的最简单形式，且当数据服从假定的概率 分布以及类条件独立假定成立时，朴素贝叶斯分类器的分类错误率是最小的【3 5 】。 虽然所需的类条件独立性假设在现实中常常不能被满足，但朴素贝叶斯分类器在 某些领域内的分类性能仍然可与决策树、k 近邻等经典算法相当。经过研究，发 现当以分类误差来考虑分类器最优性时，它不一定与假设的概率分布的拟合程度 相关( 例如独立性假设的适当性) ，只要真实的分布和估计的分布在概率最大的类 上相合，得到的分类器就是最优的【3 6 】【3 7 1 。下面介绍朴素贝叶斯分类器的基本原 理和归类过程。 基本原理：假定有小个类c l ，c 2 ，c 。，每个样本有d 个属性4 ，彳：，以。 用d 维特征向量x = ( x 1x 2 ，勤) 表示样本x 在d 个属性4 ，彳：，以上的取值。 给定一个未标注的样本y = ( y ly ：，y d ) ，按极大后验假设，贝叶斯分类器 将判决y 属于具有最大后验概率p ( cjy ) 的类：e ( y ) = a r g m a x p ( c jiy ) ，p ( y ) 为y 所属类别。根据贝叶斯定理得： 尸( qi少)=p(y矿i c j ) p ( c j ) ( 2 1 。) p ( y ) = p ( ylc j ) p ( c j ) ( 2 - 1 1 ) 由于p ( y ) 对于所有类为常数，故只需要计算尸( 少lc j ) p ( c j ) 即可，由此可知 1 0 中山大学硕士学位论文 贝叶斯分类方法就是计算待判样本y 对于各类的判别函数p ( yiq ) 尸( c ) 的值， 然后将少判归给具有最大尸( y i c j ) p ( c j ) 值的类别。 归类过程：类q 的先验概率p ( q ) 可用p ( c j ) = 力疗估计，其中甩为类q 的训练样本数，刀为总训练样本数。若给定多属性数据集，计算p ( yiq ) 的开销 可能非常大，因此作类条件独立的“朴素 假设( 这也是朴素贝叶斯分类器命名 的由来) ，从而有： d e ( y l g ) = 兀p ( y kr g ) ( 2 - 1 2 ) k = l 当a 。是连续型属性，则通常假设该属性变量服从高斯分布f 3 8 l 。这主要有两 方面原因：一是高斯分布在数学上比较简便，另一个是物理上的合理性f 3 5 1 。在 类q 中，设各4 相互独立，且4 n o t 业，仃五) ，概率密度函数为： 地= 面1e 卅警， 仁聊 兰x 2 ，壹( x g ，一鲰) ： 舯2 一磊= 生f 广一阴训瓣棚始舫黼计 参数和2 的值。 从而分类判别函数为： 梳，= 蒜d 器1 军( y , - z j 女) 2 q - 1 4 )尸( c 舢) ：等竺竺? 生百( 2 丢p ( q ) 珥赢唧 - 笋 朴素贝叶斯分类器的主要优点是：( 1 ) 算法逻辑简单，易于实现；( 2 ) 计算复 杂度较低，由训练过程分析可知，n b c 的算法复杂度为o ( m ) ；( 3 ) 算法稳定， 对于不同的数据特点其分类性能差别不大；( 4 ) 对缺失数据集敏感度低。 朴素贝叶斯分类器的主要缺点是：( 1 ) 类条件独立性很难满足，因此是一种 中山大学硕士学位论文 近似模型；( 2 ) 对各个属性的分类重要性判断一样；( 3 ) 当i , l l l 练样本个数较少时， 数据的潜在分布难以表现出来。 在连续型数据的分类问题中，朴素贝叶斯分类器假定在同一类中各个属性变 量相互独立，不同类的样本属于相互独立的不同总体。在建立分类器前先假设样 本数据服从高斯分布，然后利用训练样本估计各类总体分布的参数，即高斯分布 的均值和方差，从而得出分类判别函数( 式( 2 1 4 ) ) 。因此设计基于参数模型的朴 素贝叶斯分类器，相当于对数据建立高斯混合分布模型，其训练过程实质上是高 斯混合模型参数的估计问题，为了加深理解朴素贝叶斯分类器的工作原理，以及 为后文对贝叶斯分类器在小标注样本的算法改进作准备，下面用混合模型思想详 细分析朴素贝叶斯的分类原理及设计过程。 2 3 有限混合模型及其在朴素贝叶斯模型中的应用 对于样本数据的描述，建立统计学模型是一种比较好的方法。通过模型可以 更清晰地推理隐含在数据中的潜在规律，朴素贝叶斯分类器假设数据由一个潜在 的概率分布函数产生，于是在构造分类器时可以用有限混合模型来描述与建模数 据。 2 3 1 基于概率密度的有限混合模型 有限混合模型是以概率统计为理论基础的分析数据的工具，它不但灵活而且 功能强大，已经在统计学和模式识别中得到了广泛的应用【3 9 1 。它的一个普遍的 应用就是用有限混合分布模型进行密度估计和分类。实际中，用单一密度函数去 拟合数据分布往往精度不高，而有限混合分布模型通过多个密度函数的加权组合 可以更为灵活地适用于对数据分布进行拟合。有限混合模型的定义描述如下： 设x l ，x 2 ，x 臃为m 个d 维随机变量，x f 之间相互独立，p f o i8 ，) 是对应 的概率密度函数，j f = 1 , 2 ，m ，其中，x r j 是x ，的取值，p ，是参数。若将 x 。，x ：，x 肘的样本按一定比例混合后，再从中对一个样本x 进行观察，则称 随机变量x 服从混合分布，它的概率密度为： 1 2 中山大学硕士学位论文 p ( xp ) = a j p ( xlo ) 卅 其中a 是混合比例，满足仅o ，a j = 1 ，0 = l ，a 2 ，a 研，0 l ，日2 ，0 ，) 。 = l ( 2 1 5 ) 这样建立的模型( 2 1 5 ) 称为概率混合模型，简称为混合模型。p 是模型的参 数，x 。，x ：，x 历是混合模型的m 个分支。 有限混合模型【4 0 】是分析复杂现象的一个灵活的建模工具，它提供了基于简 单的结构来模拟复杂密度的一个有效方法，给出了模拟同质性和异质性的自然框 架和半参数结构。在实践中，如果观测现象是由若干随机变量的一个( 或几个) 所 引起，则可考虑构建有限混合模型研究这一复杂的现象。实践表明，有限混合模 型是一个灵活而强有力的概率分析工具，其有效性已经在许多领域得到了普遍认 可，主要表现在以下几个方面： ( 1 ) 它采用简单的结构模拟复杂结构的方法。 ( 2 ) 它提供一个模拟同质性和异质性的数据分析方法。当模型分支数为1 时， 混合分布总体将是单一的分布，因而数据是同质的；当模型分支数大于1 时，混 合分布总体将由多个分支总体构成，它反映了混合数据的异质性，而每一个分支 总体即各样本类。 ( 3 ) 混合模型在密度参数估计框架上提供了一个非常可靠的建模环境，使其 具备模型上的解析优势。 怎样估计混合模型的密度参数是一般的混合模型研究的主要议题。自从 d e m p s t e r 等人于1 9 7 7 年提出了计算不完全数据的极大似然估计的e m 算法，并 给出了混合模型的不完全数据的描述方法，极大似然方法成为混合模型参数估计 的主流方法。 2 3 2 基于有限混合模型的朴素贝叶斯分类器的设计 对数据建立混合分布模型之后，全部样本组成的数据集就是一个混合分布的 样本，其m 个类总体就是混合模型的m 个分支，朴素贝叶斯分类器的训练过程 实质上是混合模型的参数估计过程，而分类过程就是基于求出的参数得到后验概 中山大学硕士学位论文 率，下面给出训练过程和分类过程的详细推导。 训练过程：估计混合模型的混合比例a 和各类分支的参数值 0 = ( 9 7 ，p ；9 e9 口：) ，歹= 1 ，2 ，m 。 s t e p l ：估计混合比例，常用方法是用频率作为近似值，即： 旷等，j = 1 ，2 ，脚( 2 - 1 6 ) s t e p 2 ：估计各分支的参数p _ ，= ( p ? ，硝，础) ，歹= 1 ，2 ，m ： 本文讨论对于连续型数据的分类问题，为估计类条件密度，假设属性a 。服 从正态分布，o , 为正态分布( j l l 肚，仃弦2 ) ，参数p z = ( j l f 业，仃肛) ，日k 可用第类的训 练样本的极大似然估计求出，= 1 , 2 ，m ，k = 1 , 2 ，d ，即： x 妒 j l l 庸= 型一，歹= 1 , 2 ，m ( 2 1 7 ) n 。 一 ( x 2 一纵) 2 仃磊= _ ，歹= 1 , 2 ，m( 2 1 8 ) m 蚂阳，d 电i d l 瓦1 k = ie x p _ 笋， i = l 二，u 陆o o 肛 蚂= 纛d1 嘉( y 荤k - p j k ) 2 p 刎 善a ，珥赢唧卜笋， 1 4 中山大学硕士学位论文 e ( y ) = a r g m a x e ( c jly ) ( 2 2 1 ) l 旬铆 由此可见，朴素贝叶斯分类器的训练过程的实质是对高斯混合分布的参数估 计过程，当训练样本量较大时，利用训练样本的信息，可以较为准确地估计各个 分支的混合比例和密度参数，然后用这些参数信息建立判别准则将未知类标的样 本归类。 朴素贝叶斯对连续数据作高斯分布假设，尽管现实中数据常常不满足这一分 布假设，但朴素贝叶斯对数据的分类准确率仍可与一些复杂的算法相当。由于其 分类函数只与参数和仃三有关，从几何意义上分析，j l l 弦为类c j 的中心，仃业为 类c i 的半径，即使数据不满足高斯分布，朴素贝叶斯分类器依然可以通过各类 中心与半径将各类区分开来。 2 4 本文提出的f i s h e r 加权朴素贝叶斯分类模型( f w n b c 模型) n b c 模型认为所有条件属性对决策属性的分类重要性是一致的( 即权重均为 1 ) ，但事实并非如此，样本属性与类别之间存在不同的关联程度，朴素贝叶斯算 法直接忽略这种关联，有可能增加分类误判。针对这一情况，学者们提出了各种 方法，将特征加权算法与朴素贝叶斯分类器结合，对不同的属性根据其对分类的 重要性赋予不同的权值，属性的权值越大，该属性对分类的影响就越大，使n b c 扩展为加权n b c ( w n b c ) ，以提高分类器的性能。这些加权方法是给每个条件属 性赋予一个权值1 ，。使n b c 得以扩展，其加权后的判别函数为： p ( x ) = a r g m a x p ( c j ) 兀p lq ) 唯 ( 2 2 2 ) l , ：j o n k = 1 在离散型数据分类问题中，很多学者提出从属性上对朴素贝叶斯进行改进， w e b b 等提出了a p n b c ( a d j u s t e dp r o b a b i l i t yn a i v eb a y e sc l a s s i f i e r ) 等方法【4 1 1 ，该 方法的加权参数作用于类别节点上，用分类器计算出样本隶属于各类别的概率 后，再通过二次加权方法调整后验概率，然后完全分类。m a r kh a l l 根据决策树 的技术来对属性进行加权【4 2 】。z h a n gh a r r y 给出了确定权值唯的信息增益率方法、 爬山算法和m a r k o vc h a i nm o n t ec a r l o 方法【2 0 1 。 中山大学硕士学位论文 基于以上加权方法的启发，本文提出一种适用于连续型数据的基于f i s h e r 准则函数的属性加权方法，对朴素贝叶斯在属性权重选择上进行改进。 由于每个属性对分类的贡献不一致，我们希望通过判断单一属性对各类的可 分离性贡献程度来确立各个属性的权重，而f i s h e r 判别准则函数删正是度量数 据可分离性判据的一种常用方法，于是考虑通过f i s h e r 判别准则函数j f ( k ) ，来 建立各个属性的分类权重心。 设d = ( z 1z ：，z 。) 为样本集，样本属性为连续变量：4 ，a 2 ，a d ，d 中样 本的类标集为c = c l ，c 2 ，q ，( z f 力，z y ，z 。( j 。) 为第，类样本集， = 1 ，2 ，m ，单独地将属性4 与类标变量结合考虑，对于属性4 ，求在各个类 q 中，第七个分量的均值，即q 的第七个分量的中心： 纵：壹z ( 2 - 2 3 ) 纵2 i 备碳 总均值： 舻去产( 2 - 2 4 ) n p k2 7 。z 彘 咒，一l 类间离差值： 类内离差值： s b ( k ) = 疗( 砖- p t ) 2 ( 2 - 2 5 ) = l s w ( k ) ：m n i ( z 一) z ( 2 - 2 6 ) 属性4 的f i s h e r 判别准则函数j f ( k ) ： j f ( k ) ：= s b ( k ) s w ( 七1 ( 2 - 2 7 ) 在f i s h e r 判别理论中，类间离差值s b ( k ) 用以刻画不同类之间的距离，类内 离差值s w ( k ) 用以刻画同一类之间样本的距离，由j f ( k ) 的定义式可知，腰( 后) 值 1 6 中山大学硕士学位论文 越大，表示单独立在4 中不同类的样本分得越开，同一类的样本越集中，因此 基于属性a 。的类可分性越强，即越有助于分类。 考虑当属性的j f 值高于平均水平时，应使权重高于1 提高其对分类的影响， 当属性的历值低于平均水平时，应使权重低于1 降低其对分类的影响。于是将 确立权重的方法定义如下： 定义2 - 1 ：f i s h e r 权重唯： 吨2 j f 广( k ) 一d - 邮2 3 风耶蚂脚毋d 瓦1 攀x p 警 ， 、口毋d 面1 唧 一掣，唯 以钏加菇妻亭 a ，兀百 e x p 一半老芝 ，l l七= l v 二7 u 正。l ，庸 2 5f w n b c 模型的实验分析 为了验证f i s h e r 加权朴素贝叶斯方法对连续数据分类问题的可行性和有效 性，本节选用u c i 机器学习斟删【4 5 1 中的数据集b r e a s t 、i r i s 、s e g m e n t 、p a r k i m o n s 、 p i m a 、w i m 、h a b e r