（管理科学与工程专业论文）基于aco的贝叶斯网结构学习与应用.pdf

基于a c o 的贝叶斯网结构学习与应用 摘要 在人工智能领域，不确定性问题一直成为人们关注和研究的焦点。贝叶 斯网是自然、紧凑的联合概率分布的图形表示形式，反映了变量阃的潜在的 依赖关系，揭示了领域对象的内在结构。由于其具有很多优点，贝叶斯网己 成为解决许多不确定性问题的强有力工具，成为人工智能领域的研究热点。 贝叶斯网的关键在于建立网络，而由专家给出的贝叶斯网带有主观性和 不确定性，因此从数据中学习成为可行的和必要的建网方法。 本文主要研究完备数据集的贝叶斯网结构学习，在研究和分析现有结构 学习算法的基础上，将a c o 算法和k 2 评分标准引入到基于打分的结构学习 算法中。主要研究内容如下： ( 1 ) 基于a c o 的贝叶斯网结构学习：本文将a c o 算法作为搜索算法， k 2 评分标准作为评分函数，针对结构学习中的节点排序和建网提出了a n t o r d e r i n g 算法和a c ob 算法，并且针对a c o 算法的变化形式，对a c ob 算 法加以| 寸论。 ( 2 ) 贝叶斯网在c r m 中应用；将贝叶斯网应用到c r m 的客户分析( 数 据挖掘) 模块中，利用贝叶斯网对客户信息加以分析和萃取，从中荻得所需 的信息，以满足决策者的需求。 关键词：贝叶斯网学习，结构，k 2 评分标准，a c o ，c r m a c o - b a s e db ns t r u c t u r el e a r n i n ga n di t sa p p l i c a t i o n a b s t r a c t ina l ，u n c e r t a i n t yr e a s o n i n gh a sb e e naf o c u so fr e s e a r c h b a y e s i a nn e t w o r ki sn a t u r a l c o m p a c tg r a p h i c a lr e p r e s e n t a t i o no fj o i n tp r o b a b i l i t yd i s t r i b u t i o n ，w h i c hc a ne x p r e s sa p o t e n t i a ld e p e n d e n tr e l a t i o n s h i pa m o n gu n c e r t a i nv a r i a b l e sa n dc a ne x p l o i tt h es t r u c t u r eo f t h ed o m a i n b e c a u s eo fi t sm e r i t s ，b a y e s i a nn e t w o r kh a sb e e nap o w e r f u lt o o t os o l v e m a n yu n c e r t a i n t yp r o b l e m s ，a n db e c o m eam a i n s t r e a mw i t h i n t h ea lp r o b a b i l i s t i ca n d u n c e r t a i n t yc o m m u n i t y t h ef i r s tt a s ko fa p p l y i n gb ni sc o n s t r u c t i o n n o n e t h e l e s s ，i ti so f t e nd i f f i c u l t ， s u b j e c t i v ea n dt i m e c o n s u m i n gt oc o n s t r u c tb nf r o me x p e r tk n o w l e d g ea l o n e ，p a r t i c u l a r l y b e c a u s eo ft h en e e dt op r o v i d en u m e r i c a lp a r a m e t e r s m e t h o d sf o rc a p t u r i n ga v a i l a b l ed a t a t oc o n s t r u c tb no rr e f i n ea ne x p e r t - p r o v i d e sn e t w o r kp r o m i s et og r e a t l yi m p r o v eb o t ht h e e f f i c i e n c yo fk n o w l e d g ee n g i n e e r i n ga n dt h ea c c u r a c yo ft h em e t h o d s i nt h i sp a p e r ，w el e a r nb ns t r u c t u r ef r o mc o m p l e t ed a t a o nt h eb a s i so ft h er e s e a r c h a n da n a l y s i so ft h ec u r r e n tb ns t r u c t u r el e a r n i n ga l g o r i t h m s ，w ei n t r o d u c ea c oa l g o r i t h m a n dk 2m e t r i ci n t os c o r e - b a s e db ns t r u c t u r el e a r n i n ga l g o r i t h mt h ed e t a i l sa r eg i v e na s r 0 o w s ( 1 ) a c o b a s e db ns t r u c t u r el e a r n i n ga l g o r i t h m ：w eu s ea c oa l g o r i t h ma ss e a r c h p r o c e d u r ea n dk 2m e t r i ca ss c o r em e t r i c t h es e a r c hs p a c ei nw h i c ht h ea c oa l g o r i t h m s o p e r a t ec a nb ed e f i n e di nt w od i f f e r e n tw a y s ：o r d e r i n ga n dd a g w ep r o p o s ea n to r d e r i n g a l g o r i t h mi no r d e r i n ga n da c oba l g o r i t h mi nd a g w ed i s c u s st h ed i f f e r e n tv a r i a n t so f a c oba l g o r i t h mi nt h i sp a p e r ， ( 2 ) b na p p l i c a t i o ni nc r m ：b ni sa p p l l e dt ot h ep a r to fc u s t o m e ra n a l y z i n g ( d a t a m i n i n g ) i nc r m w eu s eb ni n t oe l i c i t i n gu s e f u li n f o r m a t i o nf r o mc u s t o m e rd a t a b a s ei n o r d e rt os a t i s f y i n st h en e e d so f t h ed e c i s i o n m a k e r k e yw o r d s ： b nl e a r n i n g ，s t r u c t u r e ，k 2m e t r i c ，a c oa l g o r i t h m ，c r m 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕 士学位论文质量要求。 答辩委员会签名： 主席： 委员： 导师：旃裂j 文 雅处 新乏聊缆脚绒炒警 九厶 雒雅 插图清单 图21 蚂蚁寻食示意图1 0 图22 蚁群算法原理 1 1 图3 1 搜索技术的分类2 8 图3 2a l a r m 网络3 7 图3 3a c 0b 算法学习所得的网络3 8 图41c r m 系统结构图4 2 图4 2 数据仓库体系结构4 3 图43k d d 过程示意图4 4 图4 4c r m 系统设计图一4 6 图4 5 客户属性与业务量关系图4 7 图4 6 贝叶斯网在客户分析中应用流程图4 8 表格清单 表1 1 贝叶斯网学习算法分类 表4 1 业务量的条件概率表4 9 独创性声明 本人声明所早交的学 ：i 7 ：论文是本人在导师指导r 进行的研究| = 作及取得的研究成果。据我所 知除了文中特别加以标志和致十的地方外，论文中不包含其他人己经发表或撰写过的研究成 果，也不包含为获得盒8 b = 些太堂 或其他教育机构的学位或证书而使用过的材料。与我一 同 ，作的同忠对本研究所做的任何贡献均已在论文中作了明确的说明芹表示谢意。 学位论文作者签字：骅 签字日期：j 酊年彳月f 乒日 学位论文版权使用授权书 本忙论文作者宄全了解金艘! = 些厶堂有关保留、使川学位论文的规定，有权保留并 向画家育荚部j 成机j ! 送交论文的复印件和磁盘，允许论文被置阅成借闵。本人授权盒照= ： g 厶堂可以将学位论文的全部喊部分论文内容编入有荚数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文， ( 保密的学位论文在解密后适用本授权书) j 伊沦望香签名：3 对 箍字日期j i 瞄年6 月，乒日 学何论- 支作者毕业厉玄向 i 忤单位： 通h 地址： 一。1。 1 j 3 导师签名： 一。蠢。h 、 签字日期：，眄年占月，乒日 屯话 邮编 致谢 值此论文完成之际，衷心感谢培育我的导师杨善林教授，向他表示崇高 的敬意和深深的谢意。杨老师高瞻远瞩的视野、博大精深的知识、严谨的学 风、敏锐的洞察力和出色的领导才能，值得我终身学习。他的积极j 下拓，勇 丁进般的科研精神，学生引以为楷模，他对学生至真至诚的关怀，学生将终 生铭畦。 感谢培育我的二导胡小建博士，从论文的选题构思到撰写及修改完成都 自始至终得到了胡老师启发、指导、支持和信任，再次向胡老师表示感谢! 感谢合肥工业大学计算机网络系统研究所为本人提供良好的研究条件， 感谢马溪骏、粱昌勇、刘心报、刘业政、何建民、余本功等老师对我的关心、 数励和帮助，感谢石文刚、郑相锋、刘洋、程承、汪林、柏吴等同学对我的 热心帮助，感谢所有关心连我的老师和同学。 衷心感谢台肥工业大学管理学院、研究生部的领导、老师对我的帮助和 关心。 感谢各位评审专家，感谢他们在百忙之中抽出时间对论文进行了仔细地评 阅。 在此向所有帮助和关心过我的人们表示衷心的感谢! 晟后，我由衷地感谢我的家人对我多年来的鼓励、支持和关爱，f 是在他 们舟勺理解与支持一f ，才使我更好地完成学业和论文，他们的支持也是我今后 工作和学习中不可缺少的动力。 作者：马壮 2 0 0 5 年5 月 第一章绪论 1 1 研究背景和意义 在现实世界中，不确定性是广泛存在的。在不确定性环境下进行推理和决 策的能力是智能行为的基础。在过去几十年中，众多研究人员对多种不确定性 知识的表示和运用方法进行了探索，尝试了不确定性的多种方法。 2 0 世纪7 0 年代，医疗专家系统m y c i n 和探矿专家系统p r o s p e c t e r 的 i 刖对人类社会产生了很大的影响。这两个专家系统都采用规则作为知识表示 方式，我们通常把基于规则的不确定性处理方法称为外延方法。尽管这种基于 规则的系统在某些领域非常成功，但是由于这些早期的规则系统不能正确地分 析信息的依赖结构。因此外延方法在处理不完备和互斥信息时显得无能为力。 随着专家系统性能的不断提高和应用领域的只益广泛，a j 研究者提出了 许多新的或改进的理论模型和经验模型。基于模型的方法称为内涵方法，内涵 方法考虑知识之间的依赖结构，并且基于模型的方法都以相应的数学模型为基 础。目前，基于模型的理论主要有：贝叶斯网、证据理论模型、模糊集理论等。 2 0 世纪8 0 年代未期，p e a l 提出的贝叶斯网l 】j 是图形表示方式和概率知识 的育机结合。它揭示领域对象的内在结构，是复杂联合概率分布的紧凑表示方 j ，其i 轻实的理论基础、知识结构的自然表述方式、灵活的推理能力、方便的 决策机制及有效的学习能力使其成为一种主要的不确定性处理方法。在现代专 家系统、珍断系统及决策支持系统中发挥着至关重要的作用，广泛应用于医疗 诊断、语言理解、语音识别、模式识别、数据挖掘、数据压缩、机器人行为规 划、臻因链分析、图像解释、和因果关系的研究等方面，其应用价值受到越来 越广泛的重视j 。 贝叶斯网的首要问题是建立网络。通常，人类专家根据其知识给出贝叶斯 网，但往往是困难的和不准确的。于是，从数据中学习是可行的和必要的建网 方法。贝叶斯网络学习是以机器学习方面的理论为基础，是贝叶斯网络推理和 应用的i i 提，因而贝叶斯网络学习的研究是贝叶斯网络研究的一个重点，也是 目日u 比较活跃的研究领域。 当j 口，随着新经济的出现，i t 行业的发展催生了一个新概念一一客户关系 管理f c u s t o m e rr e l a t i o n s h i pm a n a g e m e n t ，c r m ) 。c r m 指的是企业通过富有意 义的交流沟通，理解并影响客户行为，最终实现提高客户获得、客户保留、客 - 一心减利客户创利的目的；c r m 是一个将客户信息转化为积极的客户关系的 反复过程。如何从大量的数据中找出所需的客户信息，这就需要数据挖掘技术 对数据加以萃取。贝叶斯网应用于c r m 的数据挖掘中，可以处理不完整和带 有噪声的数据集，它用概率测度的权重来描述数据间的相关性，从而解决了数 据问的不一致性，甚至是相互独立的问题；用图形的方法描述数据间的相互关 糸，语义清楚、可理解性强，这有助于数据恻的因果关系进行预测分析，为决 策者提供所需信息，也为c r m 中数掘挖掘的研究提供了一种新的思路。 1 2 课题的国内外研究现状 1 2 1 贝叶斯网的产生与发展 贝叶斯网产生于2 0 世 2 , 7 0 年代晚期，j u d e ap e a r l 于1 9 8 8 年正式提出了贝叶 斯网络。最初，贝叶斯网是为了处理阅读理解问题。阅读理解问题是指：必须 结合上下文营造的认知氛围形成统一的解释爿能理解句子的含义。出于贝叶斯 网具有诊断推理和预言推理的能力，因而可以处理此类问题。 贝叶斯网是复杂联合概率分布的紧凑表示形式，其结果中嵌入了大量的变 量独立关系，这种简便表达和使用独立性的方式大量节省了存储空间，大大简 化了知识获取和领域建模过程，大幅度降低了计算复杂性。 贝叶斯网是概率理论和图论的有机结合，联合概率分布保证了整个系统的 一致性，图形结构提供了计算的直观性、高效性。对于应用数学和工程学中的 不确定性问题，贝叶斯网提供了一种自然、有效的工具，特别是，它在机器学 习算法的分析和设计方面发挥了重要的作用。 贝叶斯网的基本思想是模块化，即通过简单的组件建造复杂系统。概率理 论为部件的组装提供了粘合剂，确保了系统的整体一致性，并为贝叶斯网和数 据的转换提供了接口。贝叶斯网的图形结构不但为人们在相关变量集上的建模 提供了直观的接口，而且给出了设计贝叶斯网高效、通用算法的一种自然数据 结构。 贝叶斯网络的发展已形成了两个分支：传统的贝叶斯网络( 又称为静态贝 叶斯网络s t a t i c b n s ，s b n s ) 和动态贝叶斯网络( d y n a m i cb n ，d b n s ) 。静态贝叶 斯网络己在专家系统，数据挖掘，人工智能和模式认别等领域获得了成功地应 用，但它不适合用于对具有时空变化性质的问题进行表示和处理。动念贝叶斯 网络是将传统的静态贝叶斯网络扩展到对时间演化的过程进行表示，以隐含马 尔可夫模型( h i d d e nm a r k o vm o d e l s ，h m m s ) $ i 静态贝叶斯网络为基础，是表示 和处理具有随机过程性质的概率模型的一种有力的和灵活的方法。动态贝叶斯 网络己在语音识别，手写体的识别，人体姿势识别和交通工具的实时监控中获 得了成功的应用。 在贝叶斯网的研究领域，出现了大量贝叶斯网理论的成功应用，代表性系 统有m u n i n ，h u g i n ，p a t h f i n d e r ，q m r d t ，c o n v i n c e 等。第一次使用贝 叶斯网建造的专家系统是m u n i n 。1 9 9 0 年，针对一般的贝叶斯网，、c o o p e r 证 明了概率值的传播计算问题是n p 难解的 3 1 。目前，如何给出合理的贝叶斯网的 树形分解结构以及如何抽象贝叶斯网是较难的课题。现在，基于贝叶斯网的专 家系统已逐渐被人们所接受。 在模式识别中，利用最简单的贝叶斯网一朴素的贝叶斯网构造的分类 器，其分类能力与经典的c 4 5 分类器不相上下，而树形增强贝叶斯网分类器、 通用贝叶斯网分类器，其分类能力要强于经典的c 4 5 分类器1 4j 。 在数据挖掘中，既可以利用贝叶斯网的批量学习算法脱机对数据进行分析 整理，也可以利用贝叶斯网的增量学习算法进行在线学习，近年来，随着研究 的深入，利用贝叶斯网学习数据中的隐含的因果关系取得了很大的进展，为数 据挖掘提供了更有力的工具。 世界上很多著名学府及著名公司、企业都在积极开展贝叶斯网学习方法及 其相关应用的研究，如斯坦福大学、普林斯顿大学、加州大学伯克利分校、微 软公司、美国航空航天局、美国电话电报公司、美国医疗研究学会等，如美国 医疗研究学会研究出名为b u g s 的用于生物领域的系统，美国航空航天局开发了 名为a u t o c l a s s 的贝叶斯分类系统，微软公司研制了名为m s b n 的偏爱预测系统 等等。 近年来，随着贝叶斯网络方法的发展，贝叶斯网络受到广大a i 研究者的青 睐。在a i 和( ( m a c h i n el e a r n i n g ) ) 等重要杂志上有不少关于贝叶斯网络的 文章。1 9 9 8 年，a i 出版了关于贝叶斯网络的专集。在i j c a i ，a a a i ，e c a i 、 a c m ，u a i 等重要会议上，贝叶斯网络研究所占的比重逐年上升。特别值得一 提的是，1 9 9 9 年，贝叶斯网络的倡导者j u d e ap e a r l 赢得了u c a i 会议的最高“研 究成就”奖。 目前，贝叶斯网研究主要集中于三个方面：贝叶斯网的高效推理算法； 基于不完备数据的贝叶斯网学习算法；扩展贝叶斯网的表达能力 1 2 2 贝叶斯网的概念 贝叶斯网是一个二元组s = ，其中 ( 1 ) g 是一个有向无环图，网中节点与知识领域的随机变量一一对应：网中 的有向弧表示变量间的因果关系，从节点x 到节点y 有向弧的直观含 义是x 对y 有直接的因果影响； ( 2 ) j p = p ( x l n ) ) ，条件概率表示因果影响的强度，其中j r ( ，代表了节点x 的父亲节点集合。 从定性的角度，贝叶斯网中的有向弧表示直接因果关系，因此，贝叶斯网 能够表达和解释那些相关关系无法表示和处理的模式。从定量的角度，贝叶斯 网是概率信息的载体，是联合概率分布的图形表示方式。 给定贝叶斯网s ，则存在一个离散变量集合x = 爿i ，x ：，x 。 上的联合 概率分布p ，x 的变量和s 中的节点间存在一对应关系，并且p 中存在递归 展1 式：p ( x ，x j = n p ( x ，l 刀- ) ，其中玎一是x ，在s 中的父亲节点集合。 这个递归表达式意味着对任一变量x ，给定其父亲集合万，爿，独立于除 玎。外的所有先驱节点。 贝叶斯网是联合概率分布的简化表示形式，可以计算变量空间的任意概率 值。当变量数目很大时，运用联合概率分布进行计算通常是不可行的，概率数 是变量数目的指数幂形式，计算量难以承受。贝叶斯网利用独立关系解决了这 个难题。贝叶斯网中存在三种独立关系：条件独立、上下文独立及因果影响独 立。三种独立关系旨在把联合概率分布分解成更小的因式，从而达到节省存贮 空间、简化知识获取和领域建模过程、降低推理过程中计算复杂性的目的，因 此说独立关系是贝叶斯网的灵魂。 1 2 3 贝叶斯网的学习 贝叶斯网s = 由网络拓扑结构g 和局部概率分布的集合p 两部分 组成，因此贝叶斯网的学习可以被分解成两个阶段： ( 1 1网络拓扑结构即有向非循环图的学习，简称为结构学习 ( 2 )网络中每个变量的局部条件概率分布的学习，简称为参数学习。 如果网络结构已知，贝叶斯网的学习的主要任务是学习概率参数：如果结 构未知，则既要学习结构，又要学习参数。结构学习和参数学习不是完全独立 的；一方面节点的条件概率很大程度上依赖于网络结构拓扑结构，另一方面， 网络拓扑结构直接由联合概率分布函数来决定。以两个分离的子阶段进行学习 是很有好处的，这是因为带有太多链接的复杂网络结构所需要的参数量大，而 为使获耿的参数达到某种信任程度所需的数据量随着参数数目的增加而迅速 增长并且复杂结构需要太大的存贮空间及冗长繁琐的计算过程才能产生预测 和解释。为使贝叶斯网作为知识表示模型是可用的，在学习过程中致力于寻找 一种最简单的网络结构是非常重要的，它含有最少可能的参数及最少可能的依 赖关系。 我们可以将两阶段的学习方式理解成：从可能最简单的网络结构开始，试 图寻找已有数据的参数，若尝试失败，再从稍微复杂的网络结构丌始，寻找符 合数据的参数，如此下去直至成功为止。 依据数据集是否完备及数据结构是否已知，贝叶斯网学习可分为四种不同 的情形，各种情形的学习重点及方法如下： 表1 1 贝叶斯网学习算法分类 网络结构已知 网络结构未知 数据 概率参数学习：简单统计估找最优网络结构：m d l 、b d e 等 完备计，m l e 方法、贝叶斯方法评分标准，启发式搜索、模拟退 火搜索等算法 数据找最优概率参数：e m 算法、既要找最佳结构，又要找最优参 不完备基于梯度方法、蒙特卡洛数，有结构e m 算法，混合模型 法，高斯算法等等 目前，对于网络结构已知、数据完备或不完备的情况，贝叶斯网学习的主 要问题被成功解决，相应的学习方法趋于成熟和完善。然而在数据不完备且网 络结构未知的情况下，贝叶斯网学习还是一个富于挑战性的研究课题，尚缺 乏行之有效、普遍适用的解决方法。 1 2 3 1 贝叶斯网的参数学习 参数学习是贝叶斯网学习的基础。参数学习可以分为完备数据和不完备数 据两种情况考虑。现有算法包括从完备数据中学习概率参数的m l e ( 最大似 然估计) 方法和贝叶斯方法，及从不完备数据中学习概率参数的蒙特卡洛方法、 高斯近似法、梯度方法和e m ( 期望一最大) 算法。 1 2 3 2 贝叶斯网的结构学习 贝叶斯网结构学习的目标是寻找对先验知识和数据拟舍得最好的网络结 构。与参数学习相同，结构学习也分为完备数据和不完备数据两种情况考虑。 目前，具有完备数据的贝叶斯网结构学习方法比较成熟，但是从不完全数据中 学习贝叶斯网结构比较困难，现有算法仍有缺陷。 1 2 3 2 1 具有完备数据的贝叶斯网结构学习 目6 t ，具有完备数据的贝叶斯网结构学习方法比较成熟。基于约束的方法 ( c o n s t r a i n tb a s e d ) 和基于打分的方法( s c o r eb a s e d ) 是两种不同的结构学习方法。 ( 1 ) 基于约束的方法：“约束”指样本d 中暗含的条件独立关系。通过一些 有效的测试手段找出d 中的条件独立关系，致力于寻找和这些条件关系一致的 网络模型。 ( 2 ) 基于打分的方法：定义某个评分标准，评判某个具体的网络结构反映出 的独立及依赖关系和样本匹配的程度，选择适宜的搜索算法搜索分值最高的网 络模型。 这两个方法各有特点，打分方法过程简单、规范，但由于搜索空洲大，一 般要求结点有顺序并根掘打分函数的可分解性进行局部确定或随机搜索，效 率较低，且易于陷入局部最优结构。基于约束方法过程比较复杂，但在一些假 设下学习效率较高，而且能够获得全局最优结构。 基于打分的方法是比较常用的结构学习方法。基于打分的方法需要解决的 主要技术关键是评分函数和搜索算法。 目前主要有两种网络评分标准： 最小描述长度m d l ( m i n i m u md e s c r i p t i o nl e n g t h ) 年l l 等价的贝叶斯信息标 准b 1 c ( b a y e s i a ni n f o r m a t i o nc r i t e r i o n ) 。 源于贝叶斯统计思想的b d e 评分方法。 搜索算法是为了搜索某个评分函数s c o r e ( ) 分值最高的网络结构。般来 说，寻找最优的模型是n p 难度的。目前常用的搜索算法为启发式搜索，如贪 心策略、模拟退火、最优最先( b e s t f i r s t ) 搜索等算法。 1 2 3 2 2 具有不完备数据的贝叶斯网结构学习 在现实世界中，大部分数据都包含缺失数据，贝叶斯网的优点之一就是具 有在数据不完备思考下进行推理的能力；并且在引入在网络结构一即数据样 本中未明显出现的隐藏变量，可以学习到简洁结构。简洁结构不仅对于避免数 据的过适合现象，而且对于在网络结构中进行有效的推理，都是十分关键的。 具有缺失数据的贝叶斯网络结构学习比较困难，现有的研究主要是基于打 分的方法。数据的缺失导致两方面问题的出现，一方面，打分函数不再具有可分 解形式，不能进行局部搜索；另一方面，一些充分统计因子不存在，无法直接进 行结构打分。围绕这两个问题相继发展了一些解决的方法，如模型选择期望 最大算法( m s e m ，m o d e ls e l e c t i o ne m ) 、交替模型选择一期望最大算法( a m s e m a l t e r n a t i v em o d e ls e l e c t i o ne m ) 、贝叶斯结构期望最大算法( b a y e s i a n s t r u c t u r ee ma l g o r i t h m ) 等。 为使学习模型具有统计鲁棒性和易计算性，经常需要在网络结构中引入隐 臧变量，这样可以简洁网络结构，节省存储空间，降低计算复杂性。围绕这个 问题，也提出一些方法，如f c i 算法等。 1 2 4 现状分析 1 t2 4 1 贝叶斯网络的优缺点 贝叶斯网络的优点： ( i ) 贝叶斯网络易于处理不完备数据集。因为贝叶斯网络提供了种对输入变量之 间的关系进行编码的一种方法。 ( 2 ) 贝叶斯网络允许学习变量间的因果关系。有利于加深对问题领域的理解，允 许在育干扰的情况下做出预测。 ( 3 ) 贝叶斯网络和贝叶斯的其它方法相结合提供了一个有效的和主要的方法柬避 免对数据的过分拟合。 ( 4 ) 贝叶斯网络提供一种对信度进行更新的方法，根据给定的因果关系确定特殊 事件发生的概率。 自适应性贝叶斯网络的优点在于适合作为一个非参数方法来进行密度估计、 数掘分析、模式分类和建立模型。另外，贝叶斯网络语义清晰易于理解，易于获 取和采用先验知识，易于实现对最新的决策方法的整合，学习过的模型可对概率 的因果进行解释，可自动地处理噪声和数据丢失的情况。 贝叶斯网络存在的问题： 当6 口，许多研究贝叶斯网络的文献都把问题集中在如何更台理地构造贝叶斯网 络、简化一个大规模的贝叶斯网络结构、细化细节( 感兴趣的节点) 以及贝叶斯网络如 何与其它相关技术( 模糊集、多值逻辑等) 相结合等方面。但是，忽略了两个关键性的 问题，即贝叶斯网络的无坏假定和静态假定。 ( 1 ) 无环假定 在现在的贝叶斯网络模型中，建模的一个基本假定是网络图中不存在环。从图论 的角度来看，贝叶斯网络的结构模型是一个有向无环图d a g ：从直观意义讲，贝叶斯 网络不考虑结果作为原因的原因。但在现实生活中，因果常常相互影响，即具有反馈 效应，在原因影响结果后，结果作为原因又影响原有的原因。那么，这时得到的就是 一个“有环”的因果网络图。针对现有的贝叶斯网络在处理因果环的实际问题中存在 的局限性，应当进一步研究如何突破贝叶斯网络的无环假定，建立有环贝叶斯网络模 型及其算法。 ( 2 ) 静念假设 现有的贝叶斯网络存在的另一个局限性是它没有考虑原因结点影响结果结点的 滞后时间，从而只适用于静态分析。因为原因发生的时间和结果发生的时间不是同时 的，而是有一定的时削滞后的，而滞后时间的长短，将影响到贝叶斯网络的推理。所 以，有必要引入动态贝叶斯网络。动态是指将时涮因素引入到贝叶斯网络的模型的建 立中，使贝叶斯网络的推理与时i 刨相关。事实上，对有环贝叶斯网络的分析，也会引 出对动态贝叶斯网络的研究。在具有单个因果环的贝叶斯网络中，只有引入时间滞后 的概念，才可以解释因果环上的信息不一致现象。在具有多个因果环的复杂的贝叶斯 网络模型中，各个环的周期是有差异的，如果按照同样的时间进行计算，必定导致推 理结果脱离实际。在这种情况下就要考虑时间因素，建立动态贝叶斯网络，它的意 义还在于可以用于对时间敏感的问题进行预测和推理。 1 2 4 2 贝叶斯网学习 应用贝叶斯网的前提是给出贝叶斯网的网络结构和条件概率。但是，由人 类号家给出贝叶斯网往往是困难和不准确的，为了帮助人类专家获取贝叶斯网 结构和条件概率，提高贝叶斯网的自适应性，从数据中学习是一种可行且较好 的方法。目前，对于网络结构己知、数据完备或不完备的情况，贝叶斯网学习 的主要问题被成功解决，相应的学习方法趋于成熟和完善。然而在数据不完备 且网络结构未知的情况下，贝叶斯网学习还是一个富于挑战性的研究课题，尚 缺乏行之有效、普遍适用的解决方法。因此，贝叶斯网学习的研究重点为结构 学习，即搜索算法的改进和评分标准的可分解性。 1 3 本文的主要研究工作 1 3 1 研究目标、思路 本文是以处理不确定性和贝叶斯网为背景，研究如何从数据中学习贝叶斯网的问 题。目自0 ，对于网络结构已知、数据完备或不完备的情况，贝叶斯网学习的主 要问题被成功解决，相应的学习方法趋于成熟和完善。然而在数据不完备且网 络结构未知的情况下，贝叶斯网的学习还是一个富于挑战性的研究课题，尚缺 乏行之有效、普遍适用的解决方法。 本文的研究重点为贝叶斯网的结构学习。由于基于打分的方法是比较常用 7 的结构学习方法，因此本文也采用基于打分的方法。基于打分的方法需要解决 的主要技术关键是评分函数和搜索算法。 本文的贝叶斯网结构学习主要考虑在数据完备情况下进行。文中，将蚁群 优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 作为搜索算法引入到贝叶斯网的结 构学习中，另外，利用k 2 评分标准用于衡量学习所得的网络结构与数据库中 事例的匹配程度。 蚁群优化算法是最近爿提出的一种新型的模拟进化算法，由意大利学者 m d o r i g o 等人首先提出来。它可用于求解各种不同的组合优化问题，如旅行商 ( t r a v e l i n gs a l e sp r o b l e m ，t s p ) 问题、二次分配( q u a d r a t i ca s s i g np r o b l e m s ， q a p ) i h 目题、作业安排( j o b s h o p ) 调度问题等等。蚁群算法不仅能够智能搜索、 全局优化，而且具有鲁棒性、正反馈、分布式计算、易与其它算法结合等特点。 将蚁群优化算法应用于贝叶斯网学习，就是利用其良好的特性，来提高算法的 效率和效果。 k 2 评分函数具有可分解性，在结构学习的过程中可以分解成关于每个参 数的局部因式，利于计算。此外，e 白! 于评分函数的可分解性，后续的计算可以 利用先前的计算，避免了大量的计算，节省了时间。 1 3 。2 本文主要内容 全文共分为五章，具体安排如下： 第一章绪论：介绍论文的研究背景、意义和理论基础，给出本文的研究目标和 思路 第二章蚁群优化算法：本章介绍了蚁群优化算法的由来、最初的蚁群算 法的模型以及改进的算法，并且介绍了蚁群优化算法的相关应用领域及发展趋 势。 第三章 基于蚁群优化算法的贝叶斯网结构学习：先研究和分析贝叶斯网 学习的现有算法，其次将蚁群优化算法与其他启发式算法作了比较，然后针对 排序和建网问题，分别提出了a n to r d e r i n g 算法和a c ob 算法。 第四章客户关系管理中贝叶斯网应用：本章针对现有的客户关系管理系 统中的客户分析( 数据挖掘) 模块，将贝叶斯网应用于陔模块，用于获取所需 的客户信息。 第五章总结与展望 第二章蚁群优化算法 2 1 引言 组合优化问题是相对基于连续变量求解的函数优化问题来进行讨论的。所 谓组合优化是指在离散的、有限的数学结构上，寻找一个满足给定约束条件并 使其目标函数值达到最大或最小的解。从一般意义上说，许多最优化问题的研 究都属于组合优化，比如研究和应用较多的规划问题，从求解问题的诸多方法 考虑，也属于组合优化的领域。如今，求解组合优化问题遍及许多学科领域， 如计算机科学、应用数学、管理科学等其他相关学科。而且，随着求解问题的 算法研究和实现算法的技术提高，一些新的组合优化问题不断出现，求解方法 也得到快速发展。组合优化问题很早引起人们的兴趣，但是组合优化问题都是 n p 难度。对于此类问题，人们从生物进化的机理中受到启发，提出了许多用 以解决复杂优化问题的新方法，如遗传算法、进化规划、进化策略等。蚁群算 法【6 1 是最近才提出的一种新型的模拟进化算法，由意大利学者m d o r i g o 等人 首先提出柬。a c o 已经在很多的组合优化问题中获得了成功的应用，这些问题可以 大体分为两类：一类是静态组合优化问题，这类问题的参数特性不会在求解过程中发 生变化，如旅行商( t r a v e l i n gs a l e sp r o b l e m ，t s p ) 门j 问题、二次分e g ( q u a d r a t i c a s s i g n m e n tp r o b l e m s ，q a p ) j 问题、序列求序( t h es e q u e n t i a lo r d e r i n gp r o b l e m ， s o p ) 1 9 1 问题、车辆路径( v e h i c l er o u t i n gp r o b l e m ，v r p ) i 司题、工作排程( j o b s h o p s c h e d u l i n g ，j s p ) m 】问题等；另一类是动态组合优化问题，这类问题的参数特性会在 求解过程中发生变化，如网络路由问题1 等。 蚁群算法不仅能够智能搜索、全局优化，而且具有鲁棒性、j 下反馈、分布 式计算、易与其它算法结合等特点。利用正反馈原理，可以加快进化过程；分 布式计算使咳算法易于并行实现，个体之间不断进行信息交流和传递，有利于 找到较好的解，不容易陷入局部最优；该算法易与多种启发式算法结合，可改 善算法的性能：由于鲁棒性强，故在基本蚁群算法模型的基础上进行修改，便 可用于其它问题。因此，蚁群算法的问世，为求解复杂的组合优化问题提供了 一种新思路。 2 2 蚁群优化算法的原理 蚂蚁算法是一种源于大自然中生物世界的新的仿生类算法，诞生至今只有 短短的十几年时间。作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的行 为特性，通过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了 成效。由于模拟仿真中使用的是人工蚂蚁概念，因此有时办被称为蚂蚁系统 ( a n ts y s t e m ，a s ) 。 据昆虫学家的观察和研究，发现生物世界中的蚂蚁有能力在没有任何可见 提示下找出从其窝巢至食物源的最短路径，并且能随环境的变化而变化，适应 性地搜索新的路径，产生新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其 走过的路径上释放一种蚂蚁特有的分泌物一一信息素，使得一定范围内的其它 蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越 多时，其留下的信息素轨迹也越来越多，以致信息素强度增大( 当然，随时间 的推移会逐渐减弱) ，后来蚂蚁选择该路径的概率也越高，从而更增加了该路 径的信息素强度，这种选择过程被称之为蚂蚁的自催化行为。由于其原理是一 种正反馈机制，因此，也可将蚂蚁王国理解成所谓的增强型学习系统。下图能 具体地说明蚂蚁寻食的原理。 幽2 1 蚂蚁寻食不意l 芏l 设a 是巢穴，e 是食物源，h c 为一障碍物。由于障碍物存在，蚂蚁要想 由a 到达e ，或者由e 返回a ，只能由h 或c 绕过障碍物。各点之间的距离 如图所示。设每个时间单位有3 0 只蚂蚁由a 到达b ，有3 0 只蚂蚁由e 到达d 点，蚂蚁过后留下的信息素为1 。为了方便，设该物质停留时涮为1 。在初始 时刻，由于路径b h 、b c 、d h 、d c 上均无信息存在，位于b 和e 的蚂蚁可以 随机选择路径。从统计的角度可以认为它们以相同的概率选择b h 、b c 、d h 、 d c ，。经过一个时间单位后，在路径b c d 上的信息量是路径b h d 上信息量的 二倍。t = l 时刻，将有2 0 只蚂蚁由b 和d 到达c ，有l o 只蚂蚁由b 和d 到达 h 。随着时间的推移，蚂蚁将会以越来越大的概率选择路径b c d ，最终完全选 择路径b c d ，。从而找到由蚁巢到食物源的最短路径。由此可见，蚂蚁个体之 蒯的信息交换是一个f 反馈过程。 c _ r 0 【b ) h t 7 i c ) 图2 2 蚁群算法原理 2 3 基本蚁群算法的模型 蚂蚁算法( a n ts y s t e m ，a s ) ，是由d o r i g o ，m a n i e z z o 和c o l o r n i 于1 9 9 1 年提 出的，这是最初的a c o 算法。蚂蚁算法最初用于解决t s p i 司题。t s p 问题是指一个 商人欲n n 个城市去推销商品，希望选择一条路径，当商人依次经过每个城市一遍后 又回到起点时所走的路径最短。t s p 是一个典型的易于描述却难以大规模处理的n p 难 题有效地解决t s p 问题具有重要的理论意义和应用价值，它已成为验证组合优化算法 有效性的一个间接标准。 对称性的t s p 问题的数学描述为： 设有n 个城市的集合c = 乜，c ：，c 0 ，城市c ，c ，c ；从n c ，的距离记办 ( d o r + ) ，且d , j = d 一此类t s p 问题的解，就是在集合c 中找一个不重复的全排列 e ，e ：，c ，。或行程c ，呻c ：j 寸c 使其路径= 叠。；最短。 现给定个有n 个城市的t s p 问题，蚁群中蚂蚁的数量为m ，以此来建市蚁群算法 的模型。 首先，引人如下记号：f 。( f ) 为t 时刻在e c ，连线上残留的信息量； 为边弧( i ，j ) 的能见度，一n ：e v q , ) 2 ，；q 为启发信息的相对重要程度( q o ) ；。为能见度 的相埘重要程度( 9 o ) ；嘭( f ) 表示在t 时刻蚂蚁k 由城市e 转移到城市c ，的概率。 夸 其次，假定每个蚂蚁的行为应符合下列规律： ( 1 ) 根据路径上的信息素浓度，以相应的概率选取下一路径； ( 2 j 不再重复选取已走过的循环路径为下一路径，这可用数据结构( t a b ul i s t ) 来控制； ( 3 ) 当完成了一次循环后，根据整个路径长度释放相应浓度的信息素，并更新 走过路径上的信息素浓度。 如果满足以下条件： ( 1 ) 在蚂蚁开始搜索的初始时刻，各条路径上分布的信息量相等，即r ，( 0 ) = a ， ( a 为常数) ： ( 2 ) 蚂蚁在运动过程中，根据各条路径上的信息量决定转移方向； ( 3 ) t 时刻位于某一城市e 的蚂蚁k ( k = 1 ，2 ，m ) 一次只能选择所有城市中的 一个目标城市e ，n 次后回到起点，完成一次循环。 那么t 时刻位于城市c ，的蚂蚁k 选择城市c ，为目标城市的概率是： 彤( r ) 器忡咄 r 。( ，) 】。 ，7 。( f ) 】4 。“：“ 0 o t t ? e r w i s e 式中，集合a l l o w e d , = o “1 ，n 一1 ) 一t a b u 女表示蚂蚁k 下一步应选择的城市；集 合t a b u 。( k = l ，2 ，m ) 用以记录蚂蚁k 当前所走过的城市。与实际蚁群不同，人工蚁群 系统具有记忆功能，集合t a b u 。随着进化过程作动态调整。随着时间的推移，以前留 下的信息渐渐消失，经过n 个时刻，蚂蚁完成一次循环，各个路径上信息量作如下做 调整： f v ( ，+ 珂) = p 毛( f ) + 00 p 8 l k = l ru r ) 9 e n d w h i l e 1 0f o re a c he d g ea 。瓯d o 信息