（计算机应用技术专业论文）选择性贝叶斯分类算法研究.pdf

j 壁塞窑垣盔堂擅堂僮论塞虫塞撞蔓 中文摘要 摘要：分类是模式识别、机器学习以及数据挖掘中一项基本丽又重要的任务。在 众多的分类方法中，贝叶斯分类方法嚣建立在贝时袈统计学和贝时斯网络基础上， 能够有效地处理不完整数据，并且具有模型可解释、精度高等优点，而被认为是 最优分类模型之一。尤其是朴素贝时斯分类器，虽然结构简单，但在很多情况下 却具有相当高的分类精度，可以达到甚至超过其它成熟算法如c 4 5 的分类精度， 而且对噪声数据具有很强的抗干扰能力。 囱从车 、素贝叶斯分类器提出以后，就被应用到了众多领域中，其有效性已经 为实践所证明。但是，随着应用领域的扩大，该种分类器的不足也更加明显。朴 素贝叶斯分类器要以一个很强的条件独立性假设为前提，即假设在各个类中，每 个属性变量( 也称作特征) 的概率分布独立予其它属性变量的概率分布。然而，实际 中的数据一般难以满足这一假设前提。如果不满足这一前提条件，分类器的分类 效果往往会明显下降。弥孙这一不足的一种有效的方法是利用属性选择去除数据 集中的冗余属性，使选择出的属性尽可能地满足条件独立性假设。然后，在选择 出的属性子集上构建炎叶斯分类器，即选择性贝时斯分类器。蟊前已有不少学者 对选择性贝叶斯分类器进行过研究，并给出了一些有效的算法，但这些算法大都 是用于完整数据和低维数据。虽然实际中不完整数据大量存在，并且这些数据大 都包含着严重影响分类效果和效率的冗余属性和无关属性，然而，由于处理不完 整数据的复杂性，目前用于不完整数据的选择性分类算法却很少见。因此，充分 利用贝叶妖分类方法能够有效地处理不完整数据的优势，来构造用于不完整数据 的选择性贝时斯分类算法是一项重要的研究课题，这正是本文主要研究内容之一； 另外，随着现代信息技术的不断发展，大量的高维数据不断涌现，而朴素贝 叶斯简单高效，适于处理高维数据，同时又对属性选择很敏感，因此对用于高维 数据的选择性贝叶斯分类算法的研究具有重要的意义，也是本文的另一项主要研 究内容。 本文的主要贡献如下： ( 1 ) 通过分析以往在分类过程中对不完整数据的处理方法，给寤了一种基于分 布的不完整数据分类算法d b c i ( d i s t r i b u t i o n b a s e db a y e s i a nc l a s s f l i e r sf o r i n c o m p l e t ed a t a ) 。该算法在训练过程中将缺失值的频数合理地分配到其它观测值的 频数中。因此，不完整数据集中所包含的信息可以得到充分利用。该算法与分类 效果和效率都很突出的不完整数据分类器r b c ( r o b u s tb a y e sc l a s s i f i e r s ) 相比，其分 类效果与后者相当，面算法的效率明显高于后者。 ( 2 ) 虽然不完整数据集中也通常包含着大量影响分类效果和效率的冗余属性 j i 塞銮遭鑫堂熊堂篷途塞空塞煎錾 或无关属性，但是，目翦用于不完整数据的选择性分类器却极为少见。针对这 问题，基于包装法( w r a p p e r s ) 给出了两个有效的选择性不完整数据分类器。首先， 通过分析以往的不完整数据分类算法，构造了选择性不完整数据分类器 s r b c ( s e l e g t i v er o b u s tb a y e sc l a s s i f i e r s ) 。与高效的胎c 以及d b c i 相比，s r b c 不仅能获得显著更高的分类准确率，同时还能大幅度地降低冗余属性和无关属性 的数目。然后，利用提出的照加高效的d b c l 分类器构造了选择性分类器 s d b c ( s e l e c t i v ed i s t r i b u t i o n - b a s e db a y e s i a nc l a s s i f i e r sf o ri n c o m p l e t ed a t a ) 。与s r b c 相比，s d b c 的分类准确率和效率都有明显提高。 ( 3 ) 为进一步提高上述s r b c 和s d b c 的效率，基于混合法构造了三个更加高 效的选择性不完整数据分类器。首先，利用一个简化的增益率计算式和s r b c 构 造了分类器s r b c b g ( s e l e c t i v er o b u s tb a y e sc l a s s i f i e l 8b a s e do ng a i nr a t i o ) 。与此 同时，剩用用于不完整数据的卡方统计量和s r b c 构造了分类器c b s r b c ( c h i s q u a r e b a s e ds e l e c t i v er o b u s tb a y e sc l a s s i f i e r s ) 。与s r b c 和s d b c 相比， s r b c b g 和c b s r b c 具有更高的分类效率和更好的分类效果。然后，为了构造对 大型不完整数据集具有更好的扩展性的选择性贝叶斯分类器，又利用推广的r e l i e f 算法和s d b c 构造了比c b s r b c 和s r b c b g 更嵩效鲍分类器r b s d ( r e l i e f - f a l g o r i t h m - b a s e ds e l e c t i v ed b c i ) 。 ( 4 ) 针对最为常见的高维数据文本数据，给出了两个用于贝叶斯分类器的 多类别文本数据属性评价璐数，以构造基于过滤法的选择性贝叶斯分类器。在文 本数据集上的分类结果显示，利用这两个属性评价函数构造的选择性贝叶疑分类 器具有更好的分类效果。 关键词：贝时斯分类；属性选择；不完整数据；蒿维数据；文本分类 分类号：t p l 8 a bs t r a c t a b s 。l 。l t a c 。i ： c l a s s i f i c a t i o ni s 觚e l e m e n t a r ya n di m p o r t a n tt a s ki n p a t t e mr e c o g n i t i o n ，m a c h i n e l e a r n i n ga n dd a t am i n i n g a so n eo ft h eb e s tc l a s s i f i c a t i o n m e t h o d s ，b a y ，e s i a n c l a s s i f i e r s ，b e i n gf o u n d e do nb a y e s i a ns t a t i s t i c sa n db a y e s i a nn e t w o r k s ，h a v es t r o n g a b i l i t yo fp r o c e s s i n gi n c o m p l e t ed a t a ，m e a n i n g f u lm o d e la n d h i g hp r e c i s i o n e s p e e l a l l y t h en a i v eb a y e s i a nc l a s s i f i e rq m ) ，a st h ef o r e m o s ta n ds i m p l e s to n e h a sv e r yh i g h c l a s s i f i c a t i o na c c u r a c ym a t c h i n go re v e ne x c e e d i n gt h a to f o t h e rm a t u r ec i n s s i f i e r s s u c h 弱c 4 5i nm a n y s i t u a t i o n s f u r t h e r m o r e ，n bh a ss t r o n ga b i l i t yt oc o u n t e r a c tn o i s ed a t a n - bh a sb e e na p p l i e dt om a n ya r e a ss i n c ei tw a s p r o p o s e da n di t se f f e c t i v e n e s sh a s b e e nv e r i f i e di np r a c t i c e w i t ht h ei n c r e a s eo fi t sa p p l i c a t i o n ，h o w e v e r , i t sd i s a d v a n t a g e b e c o m e sm o r ea n dm o r ec l e a r as t r o n gc o n d i t i o n a li n d e p e n d e n c ea s s u m p t i o nf 曲n bi s m a d el i k e t h i s ：i ne a c hc l a s st h ep r o b a b i l i t yd i s t r i b u t i o no fa l l a t t r i b u t e ( i e f e a t u r e ) i s i n d e p e n d e n to ft h a to fo t h e ra t t r i b u t e s d a t a s e t si nr e a l i t y , h o w e v e r , n s u a l l yd on o t s a t i s f yt h i s a s s u m p t i o n ，w h i c ho f t e nr e d u c et h ec l a s s i f i c a t i o ne f f e c to fn bd b v i o u s i v o n em e t h o dt or e s o l v et h i s p r o b l e mi s t od e l e t er e d u n d a n ta t t r i b u t e sb va 删b u t e s e l e c t i o na n dc o n s t r u c tn bo n r e m a i n i n ga t t r i b u t e s ( i c c o n s t r u c ts e l e o t i v en a e b a y e s i a nc l a s s i f i e r ) s o m ee f f e c t i v ea l g o r i t h m sa b o u ts e l e c t i v eb a y e s i a nc l a s s i f i e r sh a v e b e e np r o p o s e d m o s to ft h e m ，h o w e v e r , a r ea p p l i e dt o c o m p l e t ea n dl o w d i m e n s i o n a l d a t 鹤e t s i nr e a l i t yt h e r ea r em a n yi n c o m p l e t ed a t a s e t s ，a n dm o s to ft h e mc o n t a i n r e d u n d a n to ri r r e l e v a n ta t t r i b u t e st h a tc a ns e r i o u s l yi n f e c tt l l ec l 嬲s 讧i c a t i o ne f i e c ta n d e f f i c i e n c y d u et ot h ec o m p l e x i t yo fp r o c e s s i n gi n c o m p l e t ed a t a ，h o w e v e r , t h e r ea r es t i l l v e r yf e ws e l e c t i v ec l a s s i f i e r sf o ri n c o m p l e t e d a t a s e t s s o ，c o n s t r u c t i n g s e l e c t i v e b a y e s i a nc l a s s i f i e r sf o ri n c o m p l e t ed a t a , w h i c hc a l lu t i l i z et h ea d v a n t a g eo fb a y e s i a n c l a s s i f i e r sf o rp r o c e s s i n gi n c o m p l e t ed a t a ，i s 舶i m p o r t a n tt a s k , a n di so n eo ft h em a i l l r e s e a r c hc o n t e n to ft h i sd i s s e r t a t i o n ， i n a d d i t i o n ，w i t h t h e d e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , m o r ea n dm o r e h i g h _ d i m e n s i o n a ld a t ac o m e sf o r t h a sn bi ss i m p l ea n de f f i c i e n t , s oi ti s v e r ys u i t a b l e f o rp r o c e s s i n gh i g h d i m e n s i o n a ld a t a b u ti t i s a l s os e n s i t i v et oa t t r i b u t e8 e l e c t i o n h e n c e ，t h es t u d ro fs e l e c t i v eb a y e s i a nc l a s s i f i e r sa p p l i e dt oh i g h d i m e n s i o n a ld a t a s e t s i si m p o r t a n t ，a n di sa n o t h e rr e s e a r t hc o n t e n to ft h i sd i s s e r t a t i o n t h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r ed e s c r i b e d a sf o i l o w s v j t 塞銮遣态堂莲坌堂焦i 佥塞蠡垒苎至基堡薹。 ( 1 ) w i t ht h ea n a l y s i so fm a i nm e t h o d so fp r o c e s s i n gi n c o m p l e t ed a t af o rc l a s s i f i c a t i o n ， t h ed i s t r i b u t i o n - b a s e db a y e s i a nc l a s s i f i e rf o ri n c o m p l e t ed a t a ( d b c i ) i sp r o p o s e d i n t h et r a i n i n gp r o c e s so fd b c it h ef r e q u e n c i e so fm i s s i n gv a l u e sa r ed i s t r i b u t e d r e a s o n a b l yt ot h a to fo t h e ro b s e r v e dv a l u e s s o ，i n f o r m a t i o nc o n t a i n e di ni n c o m p l e t e d a t a s e t sc a nb es u f f i c i e n t l yu t i l i z e d n o to n l yt h ec l a s s i f i c a t i o na c c u r a c yb fd b c ii s s i m i l a rw i t ht h a to ft h ev e r ye f f e c t i v ec l a s s i f i e rf o ri n c o m p l e t ed a t an a m e dr b c ( r o b u s t b a y e sc l a s s i f i e r ) ，b u ta l s oi t se f f i c i e n c yi sh i g h e rt h a nt h a to f t h e l a t e r ( 2 ) t h o u g hi n c o m p l e t ed a t a s e t so f t e nc o n t a i nm a n yr e d u n d a n to ri r r e l e v a n ta t t r i b u t e s 呶a tc a ns e r i o u s l yi n f e c tc l a s s i f i c a t i o ne f f i c i e n c ya n de f f e c t , b u tt h e r ea r es t i l lv e r yf e w s e l e c t i v ec l a s s i f i e r sf o ri n c o m p l e t ed a t a a n ds o ，t w os e l e c t i v eb a y e s i a nc l a s s i f i e r sf o r i n c o m p l e t ed a t ab a s e do nw r a p p e r sa r ep r e s e n t e d a tf as t , t h r o u g ht h ea n a l y s i so f c l a s s i f i e r sf o ri n c o m p l e t ed a t aw ec o n s t r u c tt h es e l e c t i v er o b u s tb a y e s i a nc l a s s i f i e r ( s r b c ) c o m p a r e dw i t hr b c a n dd b c i ，s r b cc a l lg e tm u c hh i g h e ra c c u r a c ya n dc a n s h a r p l yd e l e t er e d u n d a n to ri r r e l e v a n ta t t r i b u t e s t h e n ，w i t hm o r ee f f e c t i v ed b c i ，w e p r e s e n tt h es e l e c t i v ed i s t r i b u t i o n b a s e db a y e s i a n c l a s s i f i e r sf o r i n c o m p l e t e d a t a ( s d b c ) c o m p a r e dw i 娃ls r b c ，s d b ci sm o r ee f f i c i e n ta n de f f e c t i v e ( 3 ) i no r d e rt of u r t h e ri m p r o v et h ee f f i c i e n c yo fs r b ca n ds d b c ，w ep r e s e n tt h r e e s e l e c t i v ec l a s s i f i e r sb a s e do nh y b r i dm e t h o d s a tf a s t , w i t hs r b ca n das i m p l i f i e dg a i n r a t i of o r m u l a , w ep r e s e n tt h es e l e c t i v er o b u s tb a y e sc l a s s i f i e r sb a s e do ng a i nr a t i o ( s r b c b g ) 。a l s ow i t hs r b ca n dc h i s q u a r es t a t i s t i c sf o ri n c o m p l e t ed a t aw ec o n s t r u c t t h ec h i s q u a r e b a s e ds e l e c t i v er o b u s tb a y e sc l a s s i f i e r s ( c b s r b c ) c o m p a r e d 、讥m s r b ca n ds d b c ，b o t hc b s r b ca n ds r b c b gh a v em u c hh i g h e re f f i c i e n c ya n d a c c u r a c y i no r d e rt oe o n s h u c tm o r es c a l a b l es e l e c t i v ec l a s s i f i e r sf o rl a r g ei n c o m p l e t e d a t a s e t s ，w i t ht h ee x p e n d e dr e l i e fa l g o r i t h ma n ds d b cw eg i v et h er e l i e f - f a l g o r i t h m b a s e ds e l e c t i v ed b c i ( r b s d ) t h a ti sm o r ee f f i c i e n tt h a ns r b c b ga n dc b s r b c ( 4 ) f o rt h em o s ta b u n d a n th i g h d i m e n s i o n a ld a 协- t 礤玉哦w ep r e s e n tt w o a t t r i b u t ee v a l u a t i o nf u n c t i o n sa p p l i e dt om u l t i - c l a s st e x td a t af o rt h ec o n s t r u c t i o no f s e l e c t i v eb a y e s i a nc l a s s i f i e r sw i t hf i l t e r sm e t h o d t h ec l a s s i f i c a t i o nr e s u l t so nt e x t d a t a s e t ss h o wt h a tt h es e l e c t i v eb a y e s i a nc l a s s i f i e r su s i n gt h e s et w oe v a l u a t i o nf u n c t i o n p e r f o r mm u c h b e t t e rt h a nw i t ho t h e rf u n c t i o n s 。 x e y 购r 黔s ： b a y e s i a nc l a s s i f i c a t i o n ； a t t r i b u t es e l e c t i o n ； i n c o m p l e t ed a t a ； h i g h d i m e n s i o n a ld a t a ；t e x tc l a s s i f i c a t i o n c l a s s n o ：t p l8 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：蓐糸祥 签字日期：少口汐年万月日 导师签 签字日期 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者繇降辫 签字日期：如驴年乡月日 1 0 5 致谢 值此论文完成之际，首先谨向我尊敬的导师黄厚宽教授表示衷心的感谢! 感 谢导师几年来的辛勤培养，感谢导师为我们取得的每一点进步所付出的大量心血。 导师以他渊博的学识、深邃的思想给予我不倦的教诲和悉心的指导，使我的博士 论文得以顺利地完成。导师严谨的治学态度、勤勉的工作精神、务实的生活作风 和睿智的学者风范给我留下了深刻的印象；他对科学的热情和对自己信念的执著 将对我今后的学习、工作和生活产生潜移默化的长远影响，令我终身受益。导师 不仅为我创造了良好的学习和科研环境，同时，在日常生活中给予了我无微不至 的关怀和照顾，从师四年的学习经历使我受益颇多，我将终生难忘。我会永远记 住黄老师为我所获得的每一次成功而露出的欣慰笑容。 在本文的研究与撰写过程中，得到了田盛丰教授、于剑教授热心的指导和无 私的帮助，在此表示深深的谢意。同时还要感谢田凤占副教授、王志海副教授、 林友芳副教授、瞿友利副教授给予的大力帮助，他们热情和深刻而富有洞察力的 见解使我获益良多。 在博士学习期间，还得到许多同学的帮助，与各位同学的讨论和交流使我受 益匪浅，使我得到了很多有价值的启示和建议，他们是：付树军、贺志、邵超、 穆成坡、尹传环、董兴业、杨莉萍、董红斌、邓大勇、裴振奎、牟少敏、薛小平、 邱桃荣、陈萍、赵翔、师智斌、陈晓青、李向军、袁岗、范亚琼、张莹、赵静、 汪廷华、郓佳丽、贺利坚、童向荣、朱岩、周丽萍、张小平、刘峰、冯奇等。他 们的真诚合作与帮助使我度过了四年愉快而充实的学习生活，在此一并向他们表 示诚挚的谢意! 另外，在编程过程中得到了许多同学的帮助，他们是：林永民、 刘玉玲、李广群、乔珠峰、付友、杨笛等，在此表示深深的谢意。 特别要感谢我的父母、妻子和岳父母及其他的亲人，正是他们真诚无私的奉 献和持之以恒的支持与鼓励，才使得我能够没有后顾之忧地专注于学业，没有他 们全身心的支持和巨大的付出，我将难以完成本论文。本论文凝聚了他们的大量 心血，再次对他们表示深深的谢意。 最后，谨以本文献给所有关心、帮助和支持我的老师、亲人和朋友们! 北京交通大学博士学位论文 第一章绪论 随着信息技术的迅猛发展和计算机及互联网的普及，各行各业产生和收集数 据的能力迅速提高。如何有效地组织、利用这些数据，从中提取有用的信息和知 识已成为当前信息社会面临的重大问题。机器学习( m a c h i n el e a r n i n g ) 与数据挖掘 ( d a t am i n i n g ) j e 是研究和解决这一重大问题的理论和技术i l 捌，这些理论与技术在 当今世界科技和经济领域中日益获得广泛的应用。 作为机器学习、数据挖掘等领域中最重要的研究问题之一，分类是一项非常 基本和重要的任务，并有着极其广泛的应用。分类是利用预定的已分类数据集构 造出一个分类函数或分类模型( 也称作分类器) ，并利用该模型把未分类数据映射到 某一给定类别中的过程。分类器的构造方法很多，主要包括规则归纳、决策树、 贝叶斯、神经网络、粗糙集、以及支持向量机( s v m ) 等方法。其中贝叶斯分类 方法建立在贝叶斯统计学口l 和贝叶斯网络t 暑】基础上，能够有效地处理不完整数据， 并且具有模型可解释、精度高等优点，而被认为是最优分类模型之一f 9 】。尤其是最 早的朴素贝叶斯分类器【10 】虽然结构简单，但在很多情况下却具有相当高的分类精 度，可以达到甚至超过其它成熟算法如c 4 5 【l lj 的分类精度，而且对噪声数据具有 很强的抗干扰能力。因此，对贝叶斯分类算法的深入研究，无论对其理论的发展， 还是在实际中的应用，都具有很重要的意义。 1 1 贝叶斯网络的发展及现状 作为贝叶斯分类算法基础的贝叶斯网络，其发展的根源应归结于英国学者 r e v e r e n dt h o m a sb a y e s 的论文“a ne s s a yt o w a r ds o l v i n gap r o b l e mi nt h ed o c t r i n eo f c h a n c e s ”r 7 1 该文给出了著名的贝叶斯公式和一种归纳推理方法。由于当时贝叶斯方 法在理论和应用方面还很不完善，因而在1 9 世纪并未被普遍接受和重视。直到2 0 世纪3 0 年代形成了以h j e f f r e y s 等为代表的贝叶斯学派，5 0 6 0 年代，r o b b m s 等 学者将经验贝叶斯方法和经典方法相结合，发展成很有影响的贝叶斯统计学派。 随着人工智能的发展，为了表示专家系统中不确定性知识并进行不确定性推理， 由r h o w a r d 和j m a t h e s o n 于1 9 8 1 年提出了贝叶斯网络。之后，j p e a r l 【8 】系统地 论述了贝叶斯网络的理论和方法，阐明贝叶斯网络是一个带有概率注释的有向无 环图，能够表示随机变量之间的因果关系和概率关系，可以直接进行概率推理， 第一章绪论 做出最优决策。工p e 剥的这一文献是关于贝叶斯网络的经典论著。从此，许多关 于贝叶斯网络的专著和论文相继出现 1 2 - 1 8 j ，贝叶斯网络的理论和方法不断发展和 完善。下面从贝叶斯网络的两个主要方面：贝叶斯网络学习和贝时斯网络推理， 对其研究现状加以概述。 l 。1 。1 贝叶斯网络的学习 在早期的贝叶斯网络学习中，常常是根据领域专家的知识确定贝叶斯网络的 结构，指定网络的分布参数。但是，当问题领域的随机变量较多时，利用领域专 家的知识来确定嬲络结构和分布参数不仅非常困难，焉旦也不够准确。与此同时， 随着信息技术的进步和计算机存储数据能力的提高，大量隐含着网络结构信息和 分布参数信息的领域数据越来越容易获取。因此，人们开始研究从问题领域的数 据中学习贝叶斯网络模型，利用获取的数据对款领域知识中得到的网络模型( 即 先验模型) 进行修正，得到后验模型。利用领域数据，由先验信息和样本数据褥 到后验信息的过程称为贝叶斯网络学习。 贝叶斯网络学习分为参数学习和结构学习。下面分别对它们进行介绍。 ( 1 ) 哭叶斯豳络的参数学习 根据获取的领域数据是否完整( 即有无缺失数据) ，贝叶斯网络的参数学习可 分为完整数据集上的参数学习和不完整数据集上的参数学习两种情况。 给定贝叶斯网络结构，从完整数据中学习网络参数时，无论网络结点上的概 率分布是离散型分布还是连续的高斯分布，参数学习将会很容易进行。这时，由 于存在封闭解，可以采用最大似然估计技术进行参数学 - i t l 吼2 0 1 ，这是参数学习最 简单的情形。 对于从不完整数据中学习网络参数的问题，由于存在缺值变量或隐藏交量( 其 值从来在数据中爨现的变量) ，般不能简单地采用最大似然估计技术，丽往往需 要借助近似求解方法，例如，梯度下降法【2 1 - 2 3 1 、e m 算法1 2 4 】及g i b b s 抽样技术【2 5 l 等来学习贝叶斯网络的参数。尽管这些技术可以从不完整数据中学到网络参数， 但计算开销往往很大。 跪) 贝时斯网络的结构学习 贝叶斯网络的结构学习也分为完整数据集和不完整数据集两种情况。目前， 在完整数据集上的贝叶斯网络结构学习算法主要有两类：类是基于启发式的搜 索方法。蓠先构造一个结构模型，然后用打分函数对该模整进行评估，搜索和评 估过程一童进行到新的结构模型的分值不是明显地比煎一个模型的分值更好为 北京交通大学博士学位论文 止。用于该类算法的打分函数有许多种，常见的有贝叶斯打分函数1 1 3 , 2 6 】，熵2 w ， 最小描述长度等【2 8 1 。 另一类结构学习算法基于相关性分析。在贝叶斯网络中，如果两个随机变量 是相关的，则从一个变量的取值信息中，可以获取另一变量取值的信息。获取信 息量的多少可以利用互信息来衡量，它表示了变量间的相关程度。因此，通过计 算变量间的互信息可以确定变量间是否相关( 当互信息小于某一阈值时，就认为 变量相互独立) ，从而可导出网络的结构。这类算法一般需要指数次的条件独立 性( c i ：c o n d i t i o n a li n d e p e n d e n c y ) 测试。j i ec h e n g 的算法采用启发式的方法，只 需o ( n 2 ) 次c i 测试【l4 1 ，其中n 为数据集中的属性变量总数。 这两类算法各有不足之处，第一类算法的时间复杂度较高【2 9 1 ，并且由于使用 启发式搜索而可能得不到最优解；第二类算法通常能得到近似的最优解，但如果 训练数据不足，c 1 测试的结果极可能是不可靠的。 在不完整数据集上的网络结构学习是目前网络学习中最困难的一个问题，对 于存在隐藏变量的情况，研究人员提出了一些解决方法。c o n n o l l y 利用聚类技术来 发现隐藏变量【3 们，但只局限于树状的网络结构。f r i e d m a n 提出了s e m 算法【3 1 1 可以 用于学习带隐藏变量的贝叶斯网络结构。由于s e m 算法要事先知道网络中隐藏变 量的个数，而人们事先很难知道网络结构中是否包含以及包含几个隐藏变量，因 此，该算法在实际中不便于应用。r a m o n i 弓i 入了b c 方法( b o u n da n dc o l l a p s e ) 进行 网络模型学习【3 2 ，3 3 1 ，而b c 方法不能保证总能得到有效的学习结果。王双成等3 4 1 通 过随机填补缺失数据得到完整的数据集，并利用完整数据集学习贝叶斯网络结构。 然后，利用g i b b s 抽样修正缺失数据，利用新得到的完整数据集调整贝叶斯网络结 构。通过上述两个步骤的多次迭代使网络结构得到改进。田风占等【3 5 】将遗传算法 引入到不完整数据条件下的贝叶斯网络结构学习中，一定程度上避免了确定性搜 索算法容易陷入局部极值的问题。上述各种学习方法得到的大都是近似的网络结 构，算法的复杂度一般都很高。到目前为止，从不完整数据中学习网络结构仍然 是一个尚未完善解决的问题。 1 1 2 贝叶斯网络推理 贝叶斯网络是随机变量间概率关系的图形表示，贝叶斯网络推理的根本任务 就是给定证据变量集合后，计算查询变量集的概率分布。贝叶斯网络早期最主要 的应用就是不确定知识的表示及不确定性推理。推理形式包括因果推理、诊断( 证 据推断) 、原因之间的推断及上述三种推理的混合。贝叶斯推理比较典型的应用有 故障诊断3 6 1 、医疗诊断 3 7 , 3 8 1 、金融市场分析【3 9 】等。 第一章绪论 贝叶斯网络的推理可以分为精确推理和近似推理。精确推理主要包括基于连 接树蒯4 m 4 3 1 和基于消除的方法l 枷。精确推理的时间复杂度般很高，c o o p e r 早已 证吲霹朝，对任意贝叶斯网络的精确推理是一个n p 问题。因此，许多研究人员开始 研究贝时辫网络的近似推理。当前，主要有三种近似推理方法：结构近似、基于 搜索的方法以及随机抽样，而随机抽样又包括逻辑抽样、重要性抽样和g i b b s 抽样 等方法1 4 6 , 4 7 。文献 4 8 ，4 9 对贝叶斯网络的推理进行了较为详细的阐述。尽管理 论上贝叶斯网络的近似推理被谥萌是n p 问题。1 ，但在许多实际闯题中却是非常有 效的。 1 2 贝叶斯分类算法的发展及现状 贝叶斯网络最初主要是用于因果推断，最早用于分类任务的贝叶斯网络模型 是朴素贝叶斯1 1 0 1 ，由于不现实的属性独立性假设，朴素贝叶斯分类方法起初并没 有引起研究人员的重视，只是作为其它分类算法的参照对象。8 0 年代末开始，研 究人员惊奇地发现朴素贝叶分类器不仅简单高效，而且在很多场合下其分类效果 可以达到甚至超过决策树、k 一近邻、神经网络及基于规则等复杂的分类算法1 5 1 - 5 4 1 。 d o m i n g o s 等人深入研究了朴素贝叶斯能产生较好分类效果的原因f 5 卯，发现只要类 后验概率估计值的顺序与其正的类后验概率值的顺序致，就能得到正确的分类 结果，而与后验概率的具体估计值无关。 但是，如果属性独立性假设改变了真正的类后验概率值的排列顺序，朴素贝 叶斯的分类精度将会明显降低，而这种情况在实际中并不少见。为此，许多研究 人员提出了一些方法和技术用于减轻属性独立性假设的负面影响，以改进朴素贝 时斯分类器的性能。 一种改进的方式是放松条件独立性假设，在朴素贝时簸分类器的基础上增加 属性间可能存在的依赖关系。基于这思路，k o n o n e n k o 提出了半朴素贝叶斯分类 器碡引，把属性变量分成多个组，相关的属性变量分在一个组，不同组中的属性变 量被认为是条件独立的。s a h a m i 提出了珏依赖关系贝叶斯分类器7 1 ，该分类器允 许每个属性变量最多有除类结点之外的k 个父结点。与此同时，f r i e d m a n 等人提 出了树扩展的朴素贝叶斯分类器( t a n ：t r e e a u g m e n t e dn a i v eb a y e s ) t 5 刳，在t a n 中，类变量没有父结点，每一个属性变量以类变量和最多另一个属性变量为父结 点，所有属性变量之闻构成的整个网络结构是树形结构。在该文中f r i e d m a n 还对 更一般的多网模型、贝时颠网络扩展的柃素贝叶额( b a n ：b a y e s i a nn e t w o r k 4 北京交通大学博士学位论文 a u g m e n t e d n a v eb a y e s ) 及普通贝叶斯网络分类器( g b n ：g e n e r a l b a y e s i a nn e t w o r k c l a s s i f i e r s ) 进行了研究，结果发现这几种更一般的模型的分类效果在某些数据集上 优于t a n ，面在另外一些数据集上却不如t a n 。之后，1 i ec h e n g 等人对b a n 和 g b n 利用条件独立测试溺络学习方法进行了改进粥，使分类效果有所提高。与此 同时，k e o g h 等人提出了超父贝叶斯分类器( s p b n ：s u p e r - p a r e n tb a y e s i a n n e t w o r k s ) 6 0 1 , 该模型假设有一个属性变量作为其它属性变量的共同父结点( 称为超 父) 。近来，石洪波等人提出了限定性的双层贝叶颠分类模型f 6 1 1 ，将属性集分为两 个子集，把其中一个子集中的属性作为另一个子集中的属性的父结点，得到的分 类效果好于t a n 。 还有相当一部分文献，在对网络结构进行扩展的同时，还将得到的多个扩展 结构进行组合，得到功能更强的分类器。t h i e s s o n 等人给出的有向无环图组合 ( m d a g ：m i x t u r e so f d i r e c t e da o y c l i cg r a p h ) 6 2 l ，w e b b 等入提出的平均王依赖结计 ( a o d e ：a v e r a g eo n ed e p e n d e n c ee s t i m a t i o n ) 1 6 3 1 及最近李建国、张长水等人提出的 广义附加贝叶斯网络分类器( g a b n ：g e n e r a l i z e da d d i t i v eb a y e s i a nn e t w o r k c l a s s i f i e r s ) 1 6 4 1 都属于这一类型。 基于上述思路提出的算法一般都是在分类精度和算法复杂度之阉进行折衷考 虑，在带有某种结构限制的网络模型中搜索条件依赖关系。除了复杂度方面的考 虑之外，这种做法的一个重要原因是基于复杂网络的贝叶斯分类器的分类效果未 必更好，有时反而明显不如朴素贝叶斯分类器的分类效果。网络结构越复杂，对 数据的过拟合现象就越可能发生。并且如果选择了不可靠的依赖关系集，贝时斯 网络分类器的分类性能将严重受损f 5 引。在样本数目一定的情况下，数据昀维数越 高，贝叶斯网络分类器的结构越复杂，对网络中各个参数的估计就会越不可靠， 其分类性能就越有可能不如朴素贝叶斯分类器。 另一种提高朴素贝叶斯分类器性能的方式是通过属性( 也称特征) 选择选出部 分属性参与分类模型的学习，在选出的具有较好的属性独立关系的属性子集上构 建贝叶斯分类器，即选择性贝叶斯分类器。基于这一思路，l a n g l e y 和s a g e 利用 后来称为包装法( w r a p p e r s ) 捧弼的属性选择方法提出了选择性朴素贝叶斯分类器 f s s 【6 6 1 。p a z z a n i 也基于包装法给出了两个选择性分类算法f