（计算机应用技术专业论文）基于量子遗传算法的贝叶斯网络结构学习.pdf

基于量子遗传算法的贝叶斯网络结构学习 摘要 在人工智能领域，不确定性知识的推理和决策一直是一个重要的研究问题。贝叶斯网络 ( b a y e s i a nn e t w o r k ，b n ) 正是对不确定性问题模拟和推理的一种有效工具。它具有坚实的 理论基础、语义清晰的网络结构、灵活的推理能力、方便的决策机制及有效的学习机制等特 点。贝叶斯网络学习包括网络的结构学习和参数学习。网络参数学习是在网络结构确定的情 况下通过数据集进行的，难度相对小些。通过数据集的学习得到合理的网络结构是相当困难 的，而且随着网络结点个数的增加网络结构空间的规模呈指数增长。已经证明，大型贝叶斯 网络的结构学习是n p 难题。因此，研究有效的网络结构学习算法对于构造贝叶斯网络具有十 分重要的意义。 本文对贝叶斯网络结构学习进行了较深入研究，所作的主要工作如下： 首先，提出基于量子遗传算法的贝叶斯网络结构学习方法。相对于常规算法，量子遗传 算法最大的优势在于将串行运算变为并行运算。它以量子计算理论为基础，用量子比特编码 表示染色体，通过量子门操作来完成进化，具有种群规模小而不影响算法性能、染色体状态 丰富、收敛速度快和全局寻优能力强等特点。将量子遗传算法用于贝叶斯网( b n ) 的结构学习， 对贝叶斯网络结构进行量子编码得到染色体，通过量子变异操作使其作为一个完备的独立解 空间进行演化，可快速搜索到全局最优的网络结构。 其次，混沌具有遍历性、随机性和规律性，以及它对初值变化具有强烈的敏感性。通过 调节变异调整系数使生成的点在上一代最优点的附近随机摆动，避免了随机漫游现象。每代仅 保留上一代的最优个体，其它个体重新生成，在最优点附近利用混沌变量的遍历性进行局部寻 优，提高了结构学习的效率。 最后，由于量子遗传算法主要是通过量子门旋转来寻优的，其中旋转角的大小直接影响 优化的结果，所以本文提出用模糊算法控制量子门的旋转角以进一步提高贝叶斯网络结构学 习的收敛速度和结果精度。 实验结果表明，将量子遗传算法和改进的量子遗传算法用于贝叶斯网络结构学习，可得到 较好的网络结构和较高的学习效率。 关键词：贝叶斯网络；结构学习：量子遗传算法；量子比特；量子旋转门 s t r u c t u r el e a m i n go f b a y e s i a nn e t w o r k sb a s e d o n q u a n t u mg e n e t i ca l g o r i t h m a b s t r a c t u n c e r t a i n t yr e a s o n i n gh a sb e e nar e s e a r c hh o t s p o ti nt h ef i e l do f a r t i f i c i a li n t e l l i g e n c ei nr e c e n t y e a r s a sa m e t h o do f d e s c r i b i n gu n c e r t a i n t yk n o w l e d g ea n dr e a s o n i n g ，b a y e s i a nn e t w o r k s ( b n s ) a r ea p p l i e de x t e n s i v e l yi nm a n yf i e l d s b n sh a sas o l i ds t a t i s t i c sg r o u n d i n g e x p l i c i ts e m a n t i c s t r u c t u r e ，f l e x i b l er e a s o n i n ga b i l i t y , c o n v e n i e n td e c i s i o nm a k i n gm e c h a n i s m ，a n de f f i c i e n tl e a r n i n g m e c h a n i s m b a y e s i a nn e t w o r kl e a r n i n gm a i n l yi n c l u d e ss t r u c t u r el e a r n i n ga n dp a r a m e t e rl e a r n i n g t h en e t w o r kp a r a m e t e r sc a nb eg o tf r o md a t as e t s ，t h ed i f f i c u l t yo fw h i c hi sl o w e r i ti sp r o v e dt h a t t h en e t w o r ks t r u c t r el e a r n i n gi san ph a r dp r o b l e m s o ，i ti so fi m p o r t a n ts i g n i f i c a n c ef o rc o n s t r u c t b n st or e s e a r c he f f i c i e n ta l g o r i t h m so f s t r u c t u r el e a r n i n g t h et h e s i sd e e p l ys t u d i e dt h es t r u c t u r el e a m i n go fb a y e s i a nn e t w o r k ，t h em a i nc o n t e n to f w h i c hi sa sf o l l o w s ： f i r s t l y , an e wm e t h o do fb a y e s i a nn e t w o r ks t r u c t u r a ll e a r n i n gb a s e do nq u a n t u mg e n e t i c a l g o r i t h m s ( q g a ) i sp r o p o s e d q g ai s an e wo p t i m i z a t i o nm e t h o dt h a tc o m b i n e sq u a n t u m c o m p u t a t i o nw i t hg e n e t i ca l g o r i t h m s ( g a ) c o m p a r e dw i t ht h ec o n v e n t i o n a la l g o r i t h m s ，q g a h a s t e n d e dt os o l v en p h a r dp r o b l e m s i te x p l o i t st h ep a r a l l e l i s mo fq u a n t u mc o m p u t a t i o ni no r d e rt o s p e e du pg e n e t i cp r o c e d u r e s i nq g a t h ec l a s sf i t n e s se v a l u a t i o na n ds e l e c t i o np r o c e d u r e sa r e r e p l a c e db yo p e r a t i o n so fq u a n t u mg a t e s i ti so fc h a r a c t e r i s t i c so fr a p i dc o n v e r g e n c ea n dg o o d c a p a b i l i t yo fg l o b a ls e a r c h n l ec h r o m o s o m ei sf o r m e db yq u a n t u mc o d i n gt h es t r u c t u r eo fb n i t m a k e st h i sc h r o m o s o m ea sac o m p l e t ei n d e p e n d e n ts o l u t i o ns p a c et oe v o l v eb yt a k i n gq u a n t u m v a r i a n c eo p e r a t i o n s e c o n d l y , t h ec h a o sa l g o r i t h mh a se n u m e r a t i o n , r a n d o ma n ds e n s i t i v i t yf o ri n i t i a lv a l u e s e x c e p tk e e p i n gt h eb e s ti n d i v i d u a lo ft h el a s tg e n e r a t i o n ，a l lt h eo t h e ri n d i v i d u a l sa r er e p r o d u c e d s e a r c h i n ga tt h eb e s tp o i n t sn e i g h b o r h o o du s i n gc h a o sv a r i a b l e sc a ni n c r e a s et h ee f f i c i e n c yo f l e a r n i n g t h i r d l y , c h r o m o s o m eh a sb e e ne v o l v e db yu s i n gq u a n t u mr o t a t i o ng a t e t h em a g n i t u d eo ft h e a n g l ep a r a m e t e rh a sa ne f f e c to nt h es p e e da n dt h eq u a l i t yo fc o n v e r g e n c e s oaf u z z yq u a n t u m g e n e t i ca l g o r i t h mb a s e do nt h ef u z z yr u l e si sp r o p o s e d e x p e r i m e n tr e s u l t ss h o w t h a ti ti sm o r ee f f i c i e n ta n dp r e c i s et ol e a mb a y e s i a nn e t w o r k su s i n g q g a a n di m p r o v e dq g a k e y w o r d s ：b a y e s i a nn e t w o r k ( b n ) ；s t r u c t u r el e a r n i n g ；q u a n t u mg e n e t i ca l g o r i t h m ( q g a ) ；q u b i t ； q u a n t u mr o t a t i n gg a t e i i 表清单 表2 - 1t o 行o l i 门真值表1 2 表2 2f e l d k i n 门真值表1 3 表2 - 3 通用量子调整策略表1 4 表3 - 1量子调整策略表2 9 表3 2c h e s tc l i n i c 包含的变量和属性3 0 表3 - 4 样本空间为1 0 ，0 0 0 的a l a r m 网络3 3 表3 5 实验结果3 5 表4 一l 三角函数作为隶属函数时输入语言变量的赋值表4 0 表4 2e 的赋值表4 3 表4 - 3u 的赋值表4 3 表4 4 模糊控制规则表一4 4 表4 - 5 旋转角的确定方法4 6 表4 - 6 改进算法后的学习结果( c h e s tc l i n i c ) 4 8 表4 7 实验结果比较表4 9 v 图清单 图3 1c h e s t _ c l i n i c 网络的标准结构3 1 图3 2 ( a ) 结点无序图3 2 ( b ) 结点有序3 l 图3 - - 3 a l a r m 网络的标准结构( b e i n l i e he ta 1 ，1 9 8 9 ) ：3 7 个结点和4 6 条边3 2 图3 4 ( a ) 结点有序时所得结构3 3 图3 4 ( b ) 结点无序时所得结构3 4 图4 2 输入、输出的变量的隶属函数4 3 图4 3 改进的改进的量子遗传算法流程图4 7 图4 4 ( a ) 结点有序 图4 4 ( b ) 结点无序4 8 图4 5 ( a ) 结点无序4 9 图4 5 ( b ) 结点有序4 9 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 金蟹工业去堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：豸l i 2 疹弓 签字日期：2o 。1 年2 月憎臼 学位论文版权使用授权书 本学位论文作者完全了解金起至些盔堂有关保留、使用学位论文的规定，有权保留并向国家有关部 fj 或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金目b 王些盔堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：孝显鸯 签字日期：2 口。7 年j 工月j f 日 学位论文作者毕业后去向 【：作单位： 通讯地址： 一名：彳髟匕 签字b 鞭：6 7 fl f 寥 电话 邮编 致谢 两年半的研究生生活转瞬即逝，虽然时间短暂但却非常充实，令我终生受益。 首先感谢我的导师张佑生教授，感谢他对我的悉心栽培，感谢他对我耐心的指导和无私 的关怀，感谢他为我课题和论文的顺利完成付出了大量的心血。张老师渊博的学术知识和严 谨的治学态度使我受益匪浅，无论是思想上还是做人的态度上张老师都对我产生了重要的影 响，为我树立了一个值得我终生学习的目标。 感谢姚宏亮老师为我指引研究的方向，以及在实验中耐心细致的指导。感谢薛峰、程玉 胜、胡敏等老师给我提供的良好的学习环境和平时给与的指导。 特别感谢0 5 级研究生李剑飞、黄忠同学，小论文的顺利发表都是和他们反复讨论、实验， 通力合作的结果。 在课题的进行过程中我还得到了洪沛霖、张齐、裴培、李响、王臻等同学的真诚帮助， 在此表示感谢。没有他们的协助，我无法顺利的完成课题研究。 至于其他为了让我能够做出些许研究成果、取得硕士学位而做出更大贡献的人 们，绝不是三言两语就能感谢得了的，唯有牢记在心，以图将来报答。 i i l 作者：李显杰 2 0 0 7 年1 2 月 1 1 引言 第一章绪论 贝叶斯网络是近年来人工智能学科最活跃的领域之一。它采用有向图的方式直观地表达 事件之间的因果关系，并且采用贝叶斯概率理论来对事件发生的可能性进行计算。它具有稳 固的数学基础，与其他知识表示形式( 如规则库、决策树、人工神经网络) 相比，具有图形 化的模型表示形式、局部及分布式的学习机制、直观的推理，适用于表达和分析不确定性和 概率性的事物等优点，是人工智能的大部分领域，包括因果推理、不确定性知识表达、模式 识别和分类、聚类分析等应用的有效工具。 贝叶斯网络在定性知识与定量知识之间达到了一个较合理的均衡，使其对实际问题的描 述更加符合实际。 本章首先介绍了贝叶斯网络的发展状况，然后是它的相关概念、推理形式、特点以及建 模方法，接着探讨它所解决的问题以及在实际问题中的应用，最后介绍了它的已有研究成果 以及发展方向。 1 2 贝叶斯网络的产生、发展 贝叶斯网络是概率统计与图论的结合【3 2 】，是一种知识的表达和推理的模型。贝叶斯网络 所描述的是复杂因果网络，它的推理依据因果传递关系。根据事件发生的边缘概率以及事件 之间发生的条件概率，贝叶斯网络模型能够根据已知事件的集合计算出所感兴趣事件的概率。 贝叶斯网络采用符合现实数据的知识表达方法，极大地利用了原始数据和统计信息。与其他 的知识表达及推理方法相比，贝叶斯网络模型的表达及推理更加直观、明确。 微软( m i c r o s o f t ) 在其视窗( w i n d o w s ) 软件中加入了基于贝叶斯网络的故障分析，目的是使 用户能够自己排除一些计算机系统的故障，减少微软公司进行软件后续服务的费用。在其最 新发布的面向分支机构、企业部门和中型企业的软件包b a c ko f f i c es e r v e r2 0 0 0 中采用了 b a y e s i a nt r o u b l es h o o t e r s 软件技术用以对系统问题进行智能分析和修复。 目前对贝叶斯网络的研究主要集中以下的几个方面： “贝叶斯网络的建模f 6 , 7 1 贝叶斯网络结构的建立，使用统计的方法、知识挖掘的方法等。 使用遗传法算法进行贝叶斯网络结构的学习。 利用不完全的数据对贝叶斯网络进行建模。 贝叶斯网络中的计算方法，复杂贝叶斯网络的计算方法。 2 、贝叶斯网络与其他技术相结合 基于模糊集的贝叶斯网络。 基于多值逻辑的贝叶斯网络。 连续变量、不连续变量的贝叶斯网络。 3 、贝叶斯网络的应用、基于贝叶斯网络的专家系统 贝叶斯网络软件工具。 基于贝叶斯网络的推理和决策方法。 基于贝叶斯网络的故障诊断。 贝叶斯网络在经济学中的应用。 医疗专家系统，如诊断系统附r h f i n d e r 淋巴节点病、c p c s b n 内服药物。 1 3 贝叶斯网络的相关概念 贝叶斯网络的理论基础是贝叶斯概率统计、图论。在讨论贝叶斯网络之前，先介绍一下 相关知识。 1 3 1 概率论 概率论是研究随机现象数学规律的数学分支。概率论的研究对象是研究现实的随机世界， 即自然界和人类社会中的随机现象。概率论的理论基础是由柯尔莫哥洛夫( k o l m o g o r o v ) 公理 系统奠定的。在柯尔莫哥洛夫( k o l m o g o r o v ) 公理系统中，概率空间( q ，f ，p ) 是一切研究的出发 点。其中q 是某个集合，它的元素称为基本事件：f 是q 上的。域，它的元素称为事件：p 是 f 上的概率测度，数值p ( a ) 是事件a 出现可能性的度量。集合论和测度论的方法被引入到概 率论中，并用它推演出概率论的理论体系。 可以使用因果空间来描述随机世界。因果空间中的事件不仅保持随机现象的直观性和形 象性，而且获得了多种表达形式。从哲学的角度看，事件存在多种表达形式是因果律中“因” 和“果”在数学中的反映。 现实中的随机现象经过数学处理后几乎都可以用随机变量来表达。随机世界不是一个杂 乱无章的世界，而是一个条理清楚、按统计规律在不断演化的世界。 1 3 2 概率论中的两个重要的原理： 1 、随机事件只有通过它和其它事件之间的联系才能被认识。 2 、在给定的条件下，随机事件出现的可能性大小能用 o ，1 1 中唯一的实数p 表达。 概率的本质是什么? 1 8 1 4 年，拉普拉斯( p s l a p l a c e ) 首次明确地给出概率的古典定义。他把概率定义为“有利 情况”的数目除以“全部可能情况”的总数目。在一些场合，古典定义是清楚和明确的。 直观地讲，概率可以使用频率来解释。 给定实验e ，假定它由条件确定。实验e 进行后事件a 可能出现，也可能不 出现。用p ( a l ) 表示事件a 出现的频率。如果在同样的条件下重复地进行实验 ，用v 。( a ) 表示前r 1 次实验中事件a 出现的次数，那么， e ( a f f ) 。幽( 卜1 ) n t 厂，j 、 并称二丛型为事件a 在该实验序列上的频率。 n 理想的无限序列上的频率具有收敛性，其极限值称为概率。记做： 矿rj 、 p ( a l f ) = l i r a 鼍 ( 卜2 ) 频率是解释抽象世界的概率概念和现实世界建立联系的基础。 概率的主观解释： 概率论的主观解释认为概率存在于人们的主观世界内，它反映了人们对某些事物的一种 信任程度，是对事物不确定性的一种主观判断。它与个人的知识水平，心理状态诸种因素有 2 关，因此称之为主观概率。概率的主观解释使用范围广泛，使用方便，符合人们的习惯。 举例来说，天气预报：“明天的降水概率是3 0 ”。在这种情况下，人们对概率的理解和 解释往往是主观上的。 概率论不涉及事件的具体内容。孤立地讨论一个事件，事件便成为一个无法理解的对象。 事件只有通过它与其它事件的联系才能被理解，被认识。 随机现象：一类现象，在个别试验中呈现不确定性；在大量重复试验中，又具有统计规律 性，称之为随机现象。 随机实验：满足以下特性：1 、可以在相同的条件下重复地进行；2 、每次试验的可能结果不止 一个，必须能事先明确试验的所有可能结果；3 、进行一次试验之前不能确定哪一个结果会出 现。 随机事件：在随机试验中，对一次试验可能出现也可能不出现，而在大量重复试验中却 具有某种规律性的事情，称之为随机试验的随机事件。 联合概率：两个事件a ，b 同时发生的概率，称为事件a b 的联合概率。记做p ( a ，b ) 。 条件概率：设a ，b 为随机试验e 的二个事件，且p ( a ) o ，则称： 户( b 1 4 ) ：! 幽( 卜3 ) ，【a ) 为事件a 发生的条件下事件b 发生的条件概率。 全概率公式：假设试验e 的样本空间为s ，a 为e 的事件，b l ，b 2 ，b n 为s 的一个 划分，且p ( b i ) 0 ( i - 1 ，2 ，n ) ，则 p ( a ) = p ( a l b 。) p ( b l 卜p ( a i b 2 ) p ( b 2 ) + + p ( a i b n ) p 0 3 n ) ( 1 4 ) 由条件概率公式和全概率公式可以推得贝叶斯公式。 贝叶斯公式： p ( e1 4 ) ：；盟盟 ( 卜5 ) e ( al 目) p ( 哆) t - i 先验概率：根据以往的数据分析得到的概率，叫做先验概率。 后验概率：在得到数据之后再重新加以校正的概率，叫做后验概率。 相互独立的事件：设a ，b 是二事件，如果满足等式 p ( a b ) = p ( a ) p ( b ) ( 1 6 ) 则称a ，b 为相互独立的事件。 ， 在实际应用中，对于事件的独立性，往往不是根据定义来判断，而是根据实际意义来加 以判断。 1 3 3 图论中的相关概念 图( g r a p h ) ：一个图g 定义为一个偶对( v ，e ) ，记作g = ( v ，e ) ，其中： 1 ) v 是一个非空集合，它的元素称为顶点； 2 ) e 是无序集的一个子集，其元素称为边。 通路( p a t h ) ：两个顶点之间通过相邻边、顶点的序列可达，称为两个顶点之间的一条通路。 链( c h a i n ) ：顶点不重复的通路，称为链。 1 回路( l o o p ) ：起始顶点与最终顶点相重合的链，称为回路。 环( c y c l e ) ：边不重复的回路，称为环。 树( t r e e ) ：连通无环称为树。 有向 ( d i r e c tg r a p h ) ：一个有向图d 定义为一个偶对d = ( v ，u ) 。其中 1 ) v 是一个非空集合，其元素称为顶点； 2 ) u 是有序集v & v 的一个子集，其元素称为弧。 有向无环图( d i r e c t a c y c l i cg r a p h ) ：无环的有向图。 有向有环图( d i r e c t c y c l i c g r a p h ) ：有环的有向图。 1 4 贝叶斯网络 贝叶斯网络又称为信念网络，是一种图型化的模型，能够图形化地表示一组变量间的联 合概率分布函数。它是基于概率论和图论的一种不确定性知识的表达和推理的模型。直观 地讲，它表现为一个赋值的复杂因果关系网络图【3 1 。 该模型的形式化描述如下： n 元随机变量x = 毛，x 2 ，吒) 的贝叶斯网络模型是一个二元组：b = ( 忍，色) 。 e = ( x ，e ) 是一个有向无环图( d i r e c t e d a c y c l i c g r a p h , d a g ) ，其中，x = “，x 2 ，) 为 结点集合，每个结点表示取离散或连续值的变量；e 是有向边的集合，每条边表示两结点间 的直接依赖关系，依赖由条件概率参数决定。称且为贝叶斯网络结构。 b r = p ( tl p 口( 一) ，彳 是贝叶斯网络模型的一组条件概率分布。在各结点取离散值的 情况下，p a ( x , ) 是在皿中t 的所有父结点的集合，b 。表示结点在其父结点某一取值组合状 态下的条件概率分布的集合。 1 4 1 贝叶斯网络的基础知识 由贝叶斯网络模型可知：贝叶斯网络是由网络结构与条件概率表两个部分组成的。网络 结构是模型中的定性部分，用于描述变量之间概率依赖关系。它是一个有向无环图，图中的 每个结点表示问题领域中某一个随机变量，每条边表示结点间可能存在直接的概率依赖关 系，两结点之间没有边连接则表示两结点间没有直接的概率依赖关系。对于网络结构中每个 结点，若没有它的父结点，则定义一个边缘概率分布；若有它的父结点，则定义一个条件概 率分布表，表的每一行为表示该结点在其父结点某一取值状态下的条件概率分布。条件概率 分布是模型中定量的部分，用于定量描述结点对其父结点的依赖程度【3 】。 贝叶斯网络的结构特征与随机变量( 结点) 的条件独立性之间的关系满足马尔可夫条件， 即：任一结点在已知其父结点取值状态的条件下，独立于它所有非子孙结点。贝叶斯网络借 助网络结构中蕴含的变量之间的独立性或条件独立性，将联合概率分解为一系列边缘概率和 条件概率的乘积，把确定联合概率分布的问题转化为对边缘概率分布和条件概率分布的确定。 具体的说，对于n 元随机向量u = ( 墨，五，咒) ，由链式法则可以得到联合概率分布的表达 式： 4 p ( u ) = 兀p ( tx , ，恐，x t i ) l ；l = l - i p l 册 ” ( 1 7 ) 其中，p a ( x , ) 表示贝叶斯网络结构中置的所有父结点的集合( 如果没有父结点，则 彤( t ) = ) ；p ( 一l p d ( t ) 表示结点t 在其父结点某一取值状态下的条件概率分布。 贝叶斯网络的推理就是在已知结点集e 的取值状态下( 此时称e 中的结点为证据结点) ， 根据式( 1 - 7 ) 计算出网络结构中其余结点x 的概率分布，即计算后验概率分布p ( x i e ) ，作 为输出。因为p ( x i e ) 与e ( x ，e ) 成正比。即： p ( x i e ) = k p ( x ，e ) ( 1 8 ) 因此，一般只需计算p ( x ，e ) ，常数k 可由p ( x i e ) 的归一性得到。 1 4 1 1 贝叶斯网络的特点 ( 1 ) 贝叶斯网络的推理严格基于概率论 贝叶斯网络是一种不确定性知识的表达和推理模型。它的推理原理基于贝叶斯概率理论， 推理过程实际上是进行概率计算【8 】。 ( 2 ) 贝叶斯网络的知识表示分为定性知识和定量知识。 定性知识指贝叶斯网络的结构，表达了事件之间的因果关系。定性关系( 因果关系、贝叶 斯网络结构图) 主要来源于专家经验、专业文献、统计学习。但直接利用原始数据的统计信息 来确定贝叶斯网络结构是n p h a r d 问题。 定量知识包括边缘概率、条件概率，表达了原因对结果的影响程度。定量关系( 概率) 主要 来源于统计学习和专业文献。当数据不丰富的时，可以使用专家估计加上统计修正的方法进 行定量。当数据丰富时，使用e m ( e x p e c t a t i o nm a x i m i z a t i o n ) 算法进行定量。使用e m 算法， 贝叶斯网络还可用于对数据缺失的情况进行处理。 ( 3 ) 知识获取与推理的复杂度较小 贝叶斯网络具有原因独立的特点。因此，可以减少知识获取与推理的复杂程度。在知识 获取时，只需关心与节点相邻的局部网络图。在推理计算时，只要知道某节点的相关节点即 可对该节点的发生概率进行估计。 1 4 1 2 贝叶斯网络的优点 贝叶斯网络与数据挖掘中的其它知识表示的方法如规则表示、决策树、人工神经网络等 相比，贝叶斯网络在知识表示方面具有以下优点： l 、贝叶斯网络能够真正有效的处理不完全数据。例如：考虑具有相关关系的多个输入变 量的分类或回归问题，对于标准的监督学习算法而言，变量间的相关性并不是它们处理的关 键因素，因此当这些变量中有某个缺值时，它们的预测结果就会出现很大的偏差。而贝叶斯 网络则提供了较为直观的概率关联关系，当变量出现某些缺值时，仍可以通过变量间的相关 性预测出正确的结果。 s 2 、贝叶斯网络和其它技术相结合能够进行因果分析。在数据分析中，因果关系有利于对 领域知识的理解；在干扰较多时，便于做出精确的预测。 3 、贝叶斯网络能够使先验知识和数据有机的结合。任何从事过实际建模任务的人都会知 道先验信息或领域知识在建模方面的重要作用，尤其是在样本数据稀疏或数据较难获得的时 候。贝叶斯网络用弧表示变量间的依赖关系，用概率分布表示依赖关系的强弱。这样就将先 验信息和样本有机的结合起来。 4 、贝叶斯网络能够有效的避免对数据的过拟合。 1 4 2 贝叶斯网络中的推理形式 贝叶斯网络推理实际上是进行概率的计算。给定一个贝叶斯网络的模型，在己知条件集 合下，利用贝叶斯概率中的条件概率的计算方法，计算出所感兴趣的查询节点( q u e r yn o d e ) 发生的概率。 在贝叶斯网络推理当中，主要有以下三种形式。 ( 1 ) 因果推理：由原因推知结论由顶向下的推理c a u s a lo r t o p d o w ni n f e r e n c e 目的是由原因推出所导致的结果。已知一定的原因( 证据) ，使用贝叶斯网络的推理计算， 求在已知原因的情况下，结果发生的概率。 ( 2 ) 诊断推理：由结论推知原因由底向上的推理( d i a g n o s t i c o r b o t t o m u p i n f e r e n c e 目的是在己知结果时，找出产生该结果的原因。已知发生了一些结果，根据贝叶斯网络 推理计算，得到造成该结果的原因的发生概率。该推理也叫做诊断推理，常用在故障诊断当 中，目的是找到造成故障的最可能原因。 ( 3 ) 支持推理：该推理目的是对原因之间的相互影响进行分析，是贝叶斯网络推理中的一 种十分合理但又有趣的现象。举例来说，事件a 、b 是导致事件c 发生的原因，如果己知事 件a 和c 同时发生，这时考察b 发生的概率，经过计算会发现，b 发生的概率会较小，甚至 比b 的边缘概率还小。这是因为，事件a “支持”了事件c 的发生，使得在该种情况下事件 b 的发生更加的不确定。这时，可以得出p ( b ) 或i o ，或者处于| 1 和1 0 之间的中间态，即1 1 和1 0 的 不同叠加态，因此一个量子比特的状态可表示为： i = 口10 + 剜1 ( 2 5 ) 其中n 和b 可以是复数，表示相应状态的概率幅，且满足下列归一化条件： i口12+i12=1(2-6) 在上式中，l 口1 2 表示l0 的概率，i 1 2 表示i1 的概率 由此可知，对于位数相同的量子比特，n 个量子比特可同时表示2 “个状态，其中任一状态 1 1 可表示为： l ：e g i 瓯 ( 2 7 ) k s l 式中，c k 为第k 个状态的概率幅，且满足归一化条件： c l1 2 + ic 21 2 + + ic。is=l(2-8) 其中，i 是一个2 ”维h i l b e r t 空间中的一个单位矢量。它所在空间的维数是随n 呈指数型 增长，这明显区别于传统遗传算法中随n 呈线性增长的态空间。 2 4 3 量子旋转门 量子计算是通过一系列么正算子实现的，么正算子保证了求解空间的独立性和可逆性。 对量子比特最基本的么正操作就是旋转门，其作用和经典计算机一样，可以由真值表给出。 d a v i dd e u t s c h 定义了一个通用量子旋转门，由这个通用旋转门可以实现任何量子门操作。在 经典可逆计算中己经证明，最简单的通用旋转门是三位f q ( - - - 位输入三位输出) 。 t o f f o l i 门和f l e d k i n 门都可以作为实现量子计算的通用旋转门。在t o 肋l i 门中，两个输 入量子位( 控制位) 控制第三个量子位( 目标位) 的状态，两个控制位不随门操作而改变。当两个 控制位同时为1 时，目标位改变，否则保持不变。( 表2 - l 是t o f f o l i 门的真值表。) 在f l e d k i n 门的三个输入位中，一个位是控制位，其他两个位是目标位，控制位不发生变化。当控制位 为“1 ”时，两目标位的值交换，否则保持不变。( 表2 2 给出了f l e d k i n 门的真值表。) 表2 - 1t o f f o i i 门真值表 i n p u tb i t s o u t p u tb i t s abcabc 控制控制目标控制控制目标 0 0oo0o o1o o1 o lo0100 l1oll1 00 1o01 011 ol l 101l01 l11l1o 表2 - 2f o l d k l n 门真值表 l n p u tb l t so u t p u tb i t s a bcabc 目标目标控制目标目标控制 oo0o0o 0lo0lo l oo100 l10 l l0 0o1 0 01 o11lo1 l0l0l1 1l11l1 在量子遗传算法中，由于染色体处于叠加或纠缠状态，量子遗传算法的遗传操作不能采 用传统遗传算法的选择、交叉和变异等操作方式，而采用将量子旋转门分别作用于各叠加态 和纠缠态的方式；子代个体的产生不是由父代群体决定，而是由父代的最优个体及其状态的 概率幅决定。遗传操作主要是将构造的量子门作用于量子叠加态或纠缠态的基态，使其相互 干涉，相位发生改变，从而改变各基态的概率幅。因此，量子门的构造既是量子遗传操作要 解决的主要问题也是量子遗传算法的关键问题。因为它直接关系到量子遗传算法的性能好坏。 在量子遗传算法中，主要采用量子旋转门，即： u ：c 。s 口一s i n 曰 l s i n e c o s 0j 式中，0 为旋转角，它的大小和方向由量子调整策略表( 表2 3 ) 决定。 ( 2 9 ) 量子位的更新是通过量子门的更新来完成的，其过程如下： 阱瞄印- 咖s i n ( z , 8 ，t 他( 2 - - 1 0 ) s i n ( a b )l jlc o s ( 只) jl 层j 在更新的过程中，a 目的大小和符号起关键作用。a 目的幅度影响收敛速度，但是如果其 幅度太大，会导致早熟。故推荐使用o 0 0 1 到o 0 5 。 表2 - 3 通用量子调整策略表 b 。r r 、 0a ，i b l l m ( 日，f ) 掣 1 - p c 警等一d ( 日) n 】 ( 2 1 2 ) _ ， l 一1 式中：m ( h ，t + 1 ) 一表示在t + l 代种群中存在模式h 的个体数目； m ( h ，f ) 一表示在t 代种群中存在模式h 的个体数目； ， ( h )一表示在t 代种群中包含模式h 的个体平均适应度； 7一表示在t 代种群中所有个体的平均适应度； 三一表示个体的长度； p ，一表示交叉概率； 巩一表示变异概率； 公式( 2 - 1 2 ) 说明高适应值、长度短、阶数低的模式在后代中至少包含该模 式的串h 的数目，而简单的交换操作不易破坏长度短、阶数低的模式，且变异 概率很小，一般不会影响这些重要模式。 用这种方法处理相似性，遗传算法减少了问题的复杂性。在某种意义上， 这些高适应值、长度短、低阶的模式成了问题的一部分解( 又叫积木块) 。遗传 算法g a 是从父代最好的部分解中构造出越来越好的串，而不是去实验每一个 可能的组合。短的、低阶的、高适应值的模式通过遗传操作再生、交换、变异， 再再生、再交换、再变异的逐渐进化，形成潜在的适应值较高的串，这就是积 木假说。遗传算法通过积木块的并置，寻找接近最优的特征。 2 、遗传算法收敛依据 量子遗传算法是一种反复迭代的搜索方法，它通过多次进化逐渐逼近最优 解，需要确定收敛判据。目前采用的收敛判据有多种，如规定遗传迭代的代数 所确定的判据，根据解的质量确定的判据等等。如连续几次得到的最优个体的 适应值没有变化或变化很小时，则认为遗传收敛了；或者种群中最优个体的适 应值与平均适应值之差与平均适应值之比小于某一给定允许值等等。为评价遗 传算法的收敛性，定义离线性能函数： - 三一 p ( r ) = ( ，) r ( 2 - - 1 3 ) t = l 其中，。为第i 代的最大个体适应值，p ( t ) 是第t 代的离线性能值。在早期搜 索中，p ( t ) 迅速增长；在后期搜索中，p ( t ) 的增长平缓下来，并最终趋向于收 敛值。 2 5 本章小结 用量子染色体的优点主要有两个：一是量子染色体是利用量子编码得到的， 由于量子的概率幅表示，一个量子染色体上携带着多个状态的信息，在对一个 量子染色体执行观察之前，这个量子染色体处于多个确定状态的叠加状态。因 此通过量子的概率幅产生新个体，使得决策变量在某种意义上不再是固定的信 息，而变成了一种携带着不同叠加态的信息，所以比单纯的使用遗传操作能带 来更丰富的种群。二是对于一些具体问题不便于对染色体进行交叉和变异操作， 因为操作后会带来大量的无效染色体，其解决方法或者是设计特殊的进化算子， 或者是在进化后对无效染色体进行修正，两种方案均增加了程序的额外开销。 在这种情况下，对量子染色体进行进化操作不失为一种好的策略。 1 6 第三章基于量子遗传算法的贝叶斯网络结构学习 3 1 引言 贝叶斯网络结构学习是一个复杂的搜索过程，是贝叶斯网络研究中的一个 重要内容。对于结构学习中的优化和计算问题，目前有很多方法与理论，但都 是建立在近似推理与局部优化的基础上，关于处理计算复杂性、搜索空间和学 习精度之间的问题，至今还没有出现令人满意的解决办法和途径。 本章首先介绍贝叶斯网络结构学习基础知识，然后介绍量子遗传算法去学 习贝叶斯网络结构。 3 2 贝叶斯网络结构学习 贝叶斯网络学习根据学习的对象，分为完整数据学习和缺失数据学习。前 者指在给定问题领域和数据实例的条件下，学习出结构模型和参数的完整网络； 后者指给定先验的部分网络结构或参数，通过数据实例进行学习修正，得到更 准确的贝叶斯网络。根据样本数据的完备性可分为完备数据学习和不完备数据 学习。根据学习方法分为：贝时斯方法学习、m d l 方法学习等1 4 “。贝叶斯网 络学习包括结构学习和参数学习两个部分，本章主要研究贝叶斯网络的结构学 习。 3 2 1 贝叶斯网络结构 结构是指系统内部各组成要素之间相互联系和作用的关系或方式。贝叶斯 网络结构就是贝叶斯网络内部各变量之间的特征与关系描述，是对具体问题领 域的种定性表达方式。它具有系统性、关联性和稳定性等几个固有属性。 ( 1 ) 结构的系统性， 贝叶斯网络结构是由若干要素( 即结点) 以一定形式构成的一个有机系统， 它具有知识表达和推理的功能。结构中的各结点不是孤立存在着的，也不是机 械的组合或简单的相加，而是通过一定的形式相互作用和影响，每个要素在结 构中都处于一定的位置，起着特定的作用，形成一个相对有序的有机整体。节 点之间的连接边是它们相互作用的桥梁，信息的传递和推理都是通过连接边来 实现的。结构的要素与组成决定了系统的特有功能，因此结构的变化和调整也 必然导致系统功能的改变。网络结构的节点排列具有一定的规律性，它们以直 观的图共同表达变量之间内在的本质与特征。 ( 2 ) 结构的关联性 联系是指两种物质( 事件) 之间的相互影响和相互作用。宇宙中的事物都是 相互联系的，联系是客观存在的，也是绝对的。结构也不例外，结构反映事物 的本质，它是人类对物质存在方式的认知，也是抽象思维的结果。贝叶斯网络 结构将节点以特有的形态合理地组织在一起，节点之间是相互联系和相互作用 的。它们之间的关系通过连接边来表达，点之间存在连接边，则表示两者之间 存在直接关联，连接边的方向由主导变量指向被动变量，关联的强度通过结构 参数来衡量。这种关联性通常表现为依赖关系、因果关系和时序关系等。网络 结构中的条件独立性正是表达关联性的一种独特方式。 ( 3 ) 结构的稳定性 世界万物的结构都是相对稳定的。没有物质结构的相对稳定，就没有相对 稳定的物质形式。网络结构具有稳定性，也具有动态性。结构变化的外因是环 境