基于贝叶斯网络的微阵列数据的研究

1、基于贝叶斯网络的微阵列数据的研究 中山大学硕士学位论文基于贝叶斯网络的微阵列数据研究姓名:张燕申请学位级别:硕士专业:信息计算科学指导教师:戴道清20100528摘要论文题目: 基于贝叶斯网络的微阵列数据研究专 业:信息计算科学硕士生: 张燕指导教师: 戴道清摘要随着人类基因组序列草图的完成,有关功能基因组的研究在生命科学领域中占据越来越重要的地位。阐明基因选择性表达所依赖的调控信息及其相互作用的分子机制,成为揭示生命现象本质的核心问题,是功能组研究的重要内容。随着基因组学研究的深入展开,基因的表达调控研究已经从单个基因、线性的调控拓展到立体层面上多基因、基因簇乃至整个基因组的调控网络。如何有

2、效地利用现已有的基因组学数据,充分整合多学科的思路,建立新的试验系统和技术体系,阐明基因组表达的调控网络,分析基因之间的相互制约关系,已经成为功能基因组学领域内国际竞争的焦点。贝叶斯网络方法将概率理论知识与图论结合,其有图形化表示、因果关系清晰以及不确定性推理等优点,本文将贝叶斯网络引入到微阵列数据中并进行分析,从概率角度描述了各基因间的依赖关系,从而阐明了整个基因组之间的调控网络。本文首先阐述了贝叶斯网络的基本概念、发展历史和分类情况及其特点,以及贝叶斯网络构造的一些基本方法,详细阐述了贝叶斯网络的结构学习和参数学习的原理,然后分几种情况将结构学习与参数学习相结合来建立表示基因之间相互影响的

3、贝叶斯网络模型。在实例分析中,本文详细描述了微阵列数据的贝叶斯网络模型构建的整个流程。本文将基因表达谱数据进行了三值离散化后构建贝叶斯网络,并分析了具有较多子结点的几个基因在网络中的作用与影响。本文主要进行了以下几个方面的研究:在完整数据集中,使用贝叶斯网络结构学习中的算法进行结构学习研究,由于需要事先确定各结点间的的排序问题,此时采用决策树算法完成排序问题,从而提高了学习效率。并在网络学习过程中讨论了设置最大父结点的个数中山大学硕士学位论文问题。通过结构学习最终获得了可反映基因之间调控关系的贝叶斯网络模型,在此基础上,使用极大似然方法进行参数估计,从而掌握基因间的后验概率。最后求出贝叶斯等价

4、类,找到在原来的网络中可以反转的有向弧,从而可以在通过实验等手段获得先验知识后进行网络结构的相应调整,这样做不影响网络的结构,更具有实用性。在有先验知识即已知网络结构的基础上,通过对数据随机分别设置/,/,/的缺失值,使用期望最大化算法进行参数学习,获得期望最大化算法对含缺失值数据的处理能力。 .在无先验知识又含有缺失数据的的基础上,使用结构期望最大化算法进行了完整的学习得到了网络结构和相应的参数结构,并获得了结构期望最大化算法的处理能力。贝叶斯网络有着很好的理论知识和清楚的知识表达形式,是不确定性研究的一种重要方法,在数据挖掘中有着重要作用。将其引入微阵列实验数据的分析中,能较好的构建网络模

5、型,分析各基因间的相互作用与影响,可广泛应用于生物学和肿瘤学的研究,观察疾病所引起的基因表达变化,并找出作用重要的变量基因。关键词:基因,贝叶斯网络,后验概率,结构学习,参数学习: : ,.,. , ,., ,. , , ., , 中山大学硕士学位论文 . , . .:, ., .,. , , . ,., . ,/,/,/. , , . , . ,.:, , ,学位论文原创性声明本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得的成果。除文中已经注明引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体,均己在文中

6、以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名:靠笾日期:劢/口年朔;日学位论文使用授权声明本人完全了解中山大学有关保留、使用学位论文的规定,即:学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版,有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅,有权将学位论文的内容编入有关数据库进行检索,可以采用复印、缩印或其他方法保存学位论文。导师签名:学位论文作者签名:奈蒸啦吃日期:犰年莎月;日魄谢弼日第一章引言 .弗一早 百.研究背景和意义随着生命科学日益深入研究,生物信息学所涉及的研究范畴也在不断的扩充。由人类基因组计

7、划牵头而兴起的基因组学研究产生了海量的生物序列数据。这种科学数据的急速和海量积累,在人类的科学研究历史中是空前的。如何更加合理有效地学习管理以及应用这些巨大的生物序列数据,从而从中挖掘出有用的生物信息是人类在探索生命奥秘的征途上面临的巨大问题。为了解决这个问题,一门名为生物信息学的新兴的交叉学科应运而生。生物信息学是的直接翻译。它的研究对象是分子生物学数据库,通过使用数学技术、计算机技术和相应的软件对海量的原始序列数据进行收集、存储、分析、注释、加工、处理、解释和传播并从中发现新的规律而获取生物学新知识。生物信息学以基因组序列信息分析作为源头,其工作内容是设法破译序列中隐藏的遗传语言规律。生物

8、信息学是由基因组学研究孕育的/新学科,而互联网、数据库、应用软件构成了生物信息学的三大技术支撑和重要组成部分。基因芯片,又称巷片 或微阵列 ,其制备主要是以玻璃片或硅片为载体,采用原位合成或离片合成的方法将寡核苷酸片段或作为探针按顺序排列在载体上【】。为了提高检测的灵敏度,样本要进行一定程度的扩增,同时用荧光标记、生物素标记或同位素标记等方法来标记样本【】。芯片经杂交反应后,再利用激光共聚焦显微镜或落射荧光显微镜等设备检测标记信号】,并记录为特殊格式的数据文件。利用计算机,通过对数据文件中的杂交点的荧光强度信号的定量分析和信息挖掘就可以得到有关样本的重要生物学信息。基因芯片是随着“人类基因组计

9、划”的发展而发展起来的一项新技术,可广泛应用于基因序列分析、基因突变预测和多态性分析,以及疾病的基因诊断等许多领域。采用微阵列技术,人们可以同时观察成千上万个基因在某一生命现象中的表达情况,通过对基因表达谱进行某种统计分析,即可得到基因功能的有关信息。.国内外研究现状年,美国田纳西州盖特林堡首次在“生物学中的信息理论研讨会上探讨了生物学和信息理论研究的结合问题,产生了生物信息学概念的萌芽。年中山大学硕士学位论文通过他发明的序列快速测定法确定了第一个完整生物的页序。随着随后几年的序列数据的日益增长,如何有效地存储加工分析利用日益增多的序列数据成了迫切需要解决的问题。世纪年代,一系列数据库的诞生和

10、互联网的推广应用使得存储大规模序列数据的物质条件基本成熟,对于大规模数据的服务和利用也取得了实际经验。随着人类基因组计划的顺利进行,基因组研究的重心已经转移到了功能基因组学,而基因表达芯片为此提供了最好的技术平台,利用基因芯片进行的表达水平检测可自动、快速、高效地检测成千上万个基因的表达情况。通过检测基因芯片的表达水平,可以进行肿瘤诊断、类型预测、基因调控网络等研究。肿瘤诊断这是目前芯片研究中应用最广、取得进展最快的一个领域。传统的肿瘤病理分类是建立在形态学的基础上,这种分类法现在仍被广泛使用,但存在很大的缺陷。预测分类目前采用的基于形态学的肿瘤分类方法,其所得的各类亚型中可能仍包含一种以上的

11、未知疾病类型。基因功能发现通过全面检测细胞在一定条件下基因的表达并对基因进行聚类分析,根据功能类别对归入其内的目标基因以功能线索的提示,或绘制基因在不同组织或条件下表达的特征图谱,并根据与其图谱一致类似的已知基因的功能,推测目标基因的功能。基因调控网络基因表达谱芯片可同时检测成千上万个基因的表达,从而使得人们有可能对细胞或组织乃至机体在某一特定时间所有基因的表达进行检测,这为重构细胞在某个时空阶段的调控网络创造了条件。研究药物作用通过用药前后不同时间结点的细胞或组织内基因表达水平的检测,可揭示药物作用通路上的基因及其调控网络,解析药物的作用机制。随着微阵列技术的发展和微阵列实验数据的不断积累,

12、研究者们转向通过对基因间相互关系的研究,重构基因调控网络,进一步找到是哪些基因的共同或相互作用导致了这一个基因的表达异常,从而探索疾病发生、发展的根源和机制。迄今为止,研究基因网络的模型很多,也有不同的分类方法:离散网络模型如和连续网络模型如 ,确第一章引言定型网络模型和随机网络模型,定量网络模型和定性网络模型等【】。布尔网络模型布尔网络模型最早由于年引进。在这种模型中,基因被定量为两种状态,“开”和“关。状态“开表示一个基因转录表达,形成基因产物,而状态“关”则代表一个基因为转录。基因之间的相互作用关系可由逻辑规则即布尔表达式来表示。线性组合模型和加权矩阵模型这两种模型在网络模型比较分析中被

13、归为一类,同属于所谓的“粗网模型。它们的共同特征是一个基因表达值被表示为其他基因表达值的函数权和。其中的权是基因之间相互关系的定量化:正权表示基因激发,负权表示基因抑制,权表示两基因没有关系。这类模型中,所有中间产物的影响都被归结为基因之间的线性相互关系。互信息关联模型互信息关联模型用熵和互信息描述基因和基因的关联。此外还有微分方程模型、神经网络模型和图解高斯模型、贝叶斯网络等。目前国外许多学者和研究结构都对贝叶斯网络进行了深入的研究主要集中在以下几个方面:基于贝叶斯网络的推理;基于贝叶斯网络的学习;基于贝叶斯网络的应用:数据挖掘中贝叶斯网络的建造。.研究内容及创新点.研究目的本文以不确定知识

14、的处理方法和贝叶斯网络理论知识为背景,介绍构建贝叶斯网络及其推理的结构学习、参数学习问题,并且应用实际数据构建相关的贝叶斯网络模型并说明其意义。本文的创新之处是将贝叶斯网络应用到基因领域,寻找基因间的相互关系。并探讨了在无任何先验知识的情况下,对完整数据集进行结构学习和参数学习在已知网络拓扑结构,对含有缺失值的数据集进行参数学习无任何先验知识时,对含有缺失值的数据进行结构学习和参数学习的情况,从而将贝叶斯网络完整的应用到基因数据中。中山大学硕士学位论文.基本思路第一章简单介绍了本文的研究背景和意义,目前国内外的研究现状以及论文的研究内容及创新点。第二章简单介绍了贝叶斯网络的知识。介绍了贝叶斯网

15、络的定义、发展史、类型、特点,以及贝叶斯网络的推理机制。第三章对贝叶斯网络进行概述,介绍贝叶斯网络的定义、结构学习算法、参数学习算法。第四章简单介绍决策树方法,并将贝叶斯网络结构学习算法用决策树方法进行优化。第五章引入数据,并对贝叶斯网络模型进行构建和推理第六章结语.资料来源、分析工具本文所分析的资料来源于数据本课题研究使用了内存和硬盘的双核计算机,数据的预处理、贝叶斯网络的结构学习、参数学习以及贝叶斯网络的推理在.环境下大型矩阵处理软件中实现。第二章贝叶斯网络的基本知识.贝叶斯网络概述.贝叶斯网络的起源和发展贝叶斯理论起源于 发表的论文“关于几率性问题求解的评论【】。世纪年代,以勋为代表提出

16、了将经验贝叶斯方法和经典方法相结合,这引起统计界的广泛关注】。年英国历史最悠久的统计学杂志又一次全文刊登的论文。世纪年代,等提出了贝叶斯网络,并且将贝叶斯网络应用到人工智能方面进行概率推理,在此基础上并将贝叶斯网络成功应用于专家系统等领域,使得贝叶斯网络成为不确定专家知识和推理的重要方法之一,这是十多年来在这些领域的一个研究热点【】。世纪年代,贝叶斯方法成为数据挖掘和机器学习、用户智能交互、信息重获、医疗诊断等的一个重要研究方向。贝叶斯网络的发展经历了以下几个阶段】:世纪年代之前,建立了贝叶斯网络的基础理论知识体系和对不确定性推理的研究;世纪年代,研究了如何根据数据以及专家知识建立贝叶斯网络的

17、问题,并研究出许多经典的贝叶斯网络学习算法;世纪,人们将许多领域的实际问题引入到贝叶斯网络中.目前,贝叶斯网络已经被广泛地用于解决许多领域的大量实际问题中,并且取得了较好的效果。概括而言,贝叶斯网络主要被运用于以下几个方面:故障诊断】:可以根据发生的故障特性,找出发生故障的原因,可根据经常发生的故障或者系统现有的状态,进行实时监控和故障预防。:专家系统【:可提供专家水平的推理,模拟人的智能,从而解决专业领域内的实际问题,例如贝叶斯网络在医学方面的应用。:规划可根据因果概率推理预测各类事件发生的可能性,对于给定的目标,得到相应的一个项目的规划。:分类】与聚类】:使用贝叶斯网络进行分类和聚类分析,

18、这在数据挖掘和模式识别中具有重要应用。近年来国内出现了许多关于使用贝叶斯网络来解决实际问题的研究。曹冬明等利用贝叶斯网络技术进行故障定位【】:李伟生等将贝叶斯网络用于规划识中山大学硕士学位论文另;邓勇等将贝叶斯网络用于模型诊断】.李明等将贝叶斯网络用于模型诊断串行译码【 】;戴芹等利用贝叶斯网络对遥感数据进行分类【.孙亚男等利用贝叶斯网络进行冠心病中医临床诊断】;李仪等利用贝叶斯分类器对移动机器人进行避障等【】。.贝叶斯网络的定义及举例.贝叶斯网络的定义又称为贝叶斯置信厍,概率网络贝叶斯网络知识 等。贝叶斯网络是一种基于概率推理的有向无环图的模型,我们可以将具体问题中的复杂变量关系在一个网络结

19、构中表示,并通过网络模型反映问题领域中变量之间的依赖关系,适用于不确定性知识的表达和推理问题研究。定义.贝叶斯网络:一个贝叶斯网络是表示变量之间概率依赖关系的有向无环图,由代表变量的结点以及连接这些结点的有向边组成,而且每个结点都标注了定量的概率信息。这里表示为有向无环图,每个结点榍于猿示变量,每条边属于臁示变量之间的概率依赖关系,同时对每个结点都对应着一个条件概率分布裹凹刁,该条件概率表指明了该变量与父结点之间概率依赖的数量关系。用数学符号表示如下:,其中互助,汤?,磊即随机变量集合,磊乃磊,乃即有向边的集合,磊历,历?,五一,磊是条件概率分布集,即条件概率表。贝叶斯网络的拓扑结构即结点与有

20、向边之间的集合用一种简单明了的方式描述了在域中成立的条件独立关系,且它提供了一种把联合概率分布分解为局部分布的方法【】:即它的图形结构编码了变量之间的概率依赖关系,具有清晰的第二章贝叶斯网络的基本知识语义特征,这种独立性的语义指明了如何组合这些局部分布来计算变量间联合分布的方法。变量用来代表感兴趣或者有意义的状态或属性,可以是任何问题的抽象,有实际意义和应用价值。有向边用来表示变量间的因果关系,箭头表示因果关系影响的方向性由父结点指向子结点,结点之间如果无连接边则表示该结点所对应的变量之间是条件独立的,这是一种定性描述。条件概率表列出了每个结点相对于其父结点的条件概率,这是一种定量描述。网络的

21、定量部分给出了变量间不确定性的数值度量。记,?,磊是网络中的结点,结点历在集合露,誓,?,取值,吼是由历的所有父结点组成的集合并在面,?,事中取值。条件概率表的元素可记为,七历砖毗。则贝叶斯网络的联合概率分布可以用下面的式子来表示:乒,七,在贝叶斯网络中,结点是条件独立于给定父结点集时的其他任意非子结点的,正是由于这种条件独立性的假设,从而大大简化了贝叶斯网络中的计算复杂度,使得贝叶斯网络推理更加方便,操作上更加简洁和可行。.贝叶斯网络举例图参:贝叶斯网络模型举例】这是一个经典的贝叶斯网络。它描述了洒水、多云、下雨以及草湿的因果关中山大学硕士学位论文系,这显示了洒水、多云、下雨以及草湿之间存在

22、一定的依赖关系,然而这种依赖关系究竟是如何发生的,其强度如何则需通过条件概率表来说明。上例中的五个变量都有对应的一张条件概率表,反映了其父结点对该变量的影响,对于根结点来说,它没有父结点,那么该条件概率表表明的是它的先验概率值。根据有向无环图的一系列的条件独立性假设,我们引入独立关系:联合概率分布具有可分解的特性,可以被分解成为更小的因式,这大大减少了确定联合分布的参数的数目,大大降低了计算复杂度。对于图.中的贝叶斯网络的联合概率分布,我们通过变量的条件独立关系和链规则可以得到:,尸冗 只,冗.贝叶斯网络的类型根据贝叶斯网络的结点类型可以将贝叶斯网络分为如下几类:.离散型贝叶斯网络如果构成贝叶

23、斯网络的结点变量是离散的变量并且取有限个值,那么这种贝叶斯网络就称为离散型贝叶斯网络。.连续型贝叶斯网络如果构成贝叶斯网络的结点变量是连续的变量,那么这种贝叶斯网络就称为连续型贝叶斯网络。.混合型贝叶斯网络如果构成贝叶斯网络的结点变量既有连续型变量又有离散型变量,那么这种贝叶斯网络就称为混合型贝叶斯网络。.贝叶斯网络的特点随着理论学习研究的不断深入和应用水平的不断提高,贝叶斯网络通过图形化的方法来表示和运用概率知识,它克服了基于规则的系统所具有的许多概念以及计算上的困难,这已经得到了学术界的普遍认可和重视。主要有以下几个特点:坚实的理论基础【】第二章贝叶斯网络的基本知识灵活的学习机制和强大的知

24、识表达以及推理能力通过在线学习并结合专家知识,使得结构和参数都能得到相应的修正与更新。通过学习贝叶斯网络我们可以发现潜在有用的模式或者关系,以实现对数据实例的分类、聚类和预测。贝叶斯网络可以有效的表达和分析处理不确定性问题,实现了运用网络结构来进行定性表达与运用概率参数进行定量描述的有机结合。应用模型的多样性贝叶斯网络模型本身具有强大的推理机制和解释功能,网络结构中的每个结点都可以作为输入和输出,这种结构上的优势使得贝叶斯网络模型的应用模式灵活多变,具有其他模型所没有的多方位推理和分析功能。.贝叶斯网络的推理机制推理?血是贝叶斯网络研究的又一个重要方面,应用贝叶斯网络的主要目的之一是当给定某些

25、可观测结点的值后,来估计未知结点的值。通过使用建立的贝叶斯网络模型解决实际问题的过程称为贝叶斯网络推理。贝叶斯网络模型可以综合样本数据信息和专家先验知识的特点,反复不断地调整网络结构和概率参数,使得推断和决策结果更加科学和准确】。贝叶斯网络的推理过程十分类似于人类大脑思维和学习的过程,具有知识发现的功能和性质。贝叶斯网络推理的本质就是概率计算,即根据先验知识和观测数据来计算目标变量的后验概率。在理论上,根据指定变量的联合概率分布可以推断出贝叶斯网络中人们感兴趣的所有结点的概率值,但是在实际应用中,计算量非常的大,往往很多情况下难以处理。尽管如此,近似推理在一定的程度上是能够满足精度方面的要求的

26、,而且可以提高推理的效率。同时利用贝叶斯网络中变量表达的条件独立性特点,可以有效地降低计算复杂度。贝叶斯网络推理中的推理方式可以分为以下几种:因果推理如果已知原因证据,可利用贝叶斯网络的推理计算,求得在该原因下的情况下结果发生的概率。诊断推理其目的是在已知结果时,找出产生该结果的原因。如果已知发生了某些结果,可根据贝叶斯网络的推理计算,求得使得该结果产生的原因和发生的概率。支持推理即提供解释一直发生的现象。其目的是对原因之间的相互影响中山大学硕士学位论文进行分析。贝叶斯网络的基本推断工作是利用结点表达的条件独立性,快速计算待求概率值的过程。在通常的情况下,采用近似推理方法不仅可以得到比较满意的

27、推理结果,而且降低了计算复杂性。通常,主要的推理算法有四类:多数传播算法、团树传播算法、图约简算法、组合优化算法。.本章小结本章简单介绍了贝叶斯网络的知识。介绍了贝叶斯网络的定义、发展史、类型、特点,以及贝叶斯网络的推理机制。第三章贝叶斯网络的构建学习过程.构建贝叶斯网络的基本步骤.概述构建贝叶斯网络的过程即为在给定数据集的情况下,找出一个能够最真实的反映该数据集中各变量之间依赖关系的有向无环图的过程。也就是在给定数据集,局,?,澌的情况下,找出一个与匹配程度最高的贝叶斯网络,。通常情况下,构建贝叶斯网络先验贝叶斯结构分为三个步骤:确定影响该领域的变量和变量域确定该问题领域的定性描述,即确定网

28、络结构,通常称为结构学习锄缸;确定该问题领域的定量描述,即确定局部概率分布,通常称为参数学习。贝叶斯网络的构建流程如图所示:匦巨扫 :,孓目一酽图:贝叶斯网络构建流程.变量和变量域确定影响该领域的变量和变量域,即确定需要分析的变量及其它们的可能值。它主要是在领域专家的指导下来选择重要的因子,有时也需要一定的策略从专家提供的变量中选择恰当合适的变量。然而实际情况下,变量往往比较复杂、数量庞大,如果不经过预处理的手段而是直接将所有变量纳入贝叶斯网络的构建中,将】中山大学硕士学位论文使得网络的构建过于复杂。所以需要对待分析变量进行预处理,之后挑选变量并确定相应的变量域。对于连续变量,需要确定其边界;

29、而当现有的推理算法只能应用离散变量时,则需要对连续变量做相应处理,例如离散化的处理。对于离散变量而言,则需要确定变量的离散状态,以及每种状态的符号与意义。.结构学习结构学习是贝叶斯网络构建的核心部分,结构学习的目标是寻找对先验知识和训练样本拟合的最好的网络拓扑结构,即从数据集中学习最优结构。确定结构学习的方法:弧的存在性可根据变量之间的条件独立性来确定,弧的方向可根据变量之间条件相对预测能力或条件相对互信息来确定。:用户可根据已有知识如根据变量之间的因果关系来建立网络结构。:以上两种方法结合。.参数学习参数学习即为构建好网络中的每一结点建立条件概率表,参数学习的目标是根据参数的先验分布和数据样

30、本集来计算参数的后验分布。确定参数学习的方法:可根据先验知识以确定局部条件概率。:可根据实验数据以确定局部条件概率。:可结合专家知识和实验数据确定局部条件概率等。.三者关系通常,以上三个方面是按顺序进行的,然而实际上一个贝叶斯网络的构建学习往往是由上述三个过程迭代、反复地交互过程。构造贝叶斯网络的方法主要如下:完整学习。即由领域的专家知识确定贝叶斯网络中的变量结点或影响因子,且通过专家知识来确定贝叶斯网络中的结构,并指出它的各变量结点的参数值。这种方法完全是在专家的指导下进行,由于人们获取知识的漫长性有限性,导】第三章贝叶斯网络的构建学习过程致构建的网络可能与实践中积累下来的数据有很大偏差。部

31、分学习。即首先主观确定贝叶斯网络中的变量结点,然后通过训练数据进行贝叶斯网络中结构和参数的学习。现实中,由于这种方法有很强的适应性,完全是一种数据驱动的方法,使得在人工智能、数据挖掘和机器学习不断发展的今天,部分学习方法应用越来越广泛。以上两种方法的结合。由领域的专家知识确定贝叶斯网络中的变量结点,并通过专家的知识来确定贝叶斯网络结构,最后通过机器学习的办法从数据中学习网络的参数。.举例以图参为例,在该问题中包含了价变量:多云、有雨、洒水、草湿。其中每个变量都有有两个不同的取值:代表是和代表否。如果己知彬取值状态为,那么求取值为的概率,则可列如下式:,.彬旦;群,根据贝叶斯网络中变量结点的条件

32、独立性,计算推理公式将得到简化,上式可简写为:,旦墨?芝三夏否五夏夏庀万;曩玎舀豇夏瓦丽,所得结果可由条件概率表中的对应值代入计算可得。同理,我们可以推断计算出在其他任意条件下,一个结点变量处于指定某种状态的概率值。.结构学习.学习算法综述世纪年代,相继出现了许多充分结合数据主动学习构建贝叶斯网络结构的算法。年,提出了在不给出结点顺序时,完全利用独立性检验使用算法来学习网络结构,但是这是一个问题。中山大学硕士学位论文年,和提出了基于评分函数和贪婪爬山法搜索策略的】算法。是已知一定的先验信息后进行结构学习的一个有实际意义的经典算法,在整个贝叶斯网络研究发展中占有重要地位,该算法在已知结点变量的顺

33、序这一先验信息的情况下,利用评分函数来估计模型和数据之间的拟合程度,然后通过不断地向网络中增加能够提高评价指标的边这样的贪婪搜索算法来找出最佳的网络结构。同年,提出了建立近似完全贝叶斯网络模型方法的算法。年,、和提出了基于的改进篚算法,在进行贝叶斯网络结构学习中将最小描述长度改为评分函数。年,和提出了使用贪婪爬山法进行结构学习,随后又提出了采用评分函数】,并利用先验知识实现约束贝叶斯网络结构复杂度的学习算法.年,提出了使用基于相等网络类上的搜索算法进行贝叶斯网络结构学习。年,提出了将贝叶斯网络看作为一个带有概率分布表的表示不确定知识的图形模型的思想。年和和年和以及次年和,都分别扩大了贝叶斯网络

34、结构学习的研究范围,将不完整数据纳入其中。年,提出了新的算法,分析了如何在分布式同构数据下进行结构学习。年,提出了使用实验数据与观测数据相结合的方法来学习贝叶斯网络结构。年,和分别提出了利用主动学习的思想对网络结构进行学习。同年,提出了通过观测底层数据模型的变化来进行因果结构发现的学习方法。基于其它的依赖分析方法建立了一种更有效的贝叶斯网络年,结构学习算法。年,和提出了混合型的贝叶斯网络结构学习算法,将条件独立性检验、演化计算和评分函数结合,结果表明该算法具有更有效的性能。.结构学习方法首先定义一个随机变量,给先验概率分布赋值为,然后计算后验概率分第三章贝叶斯网络的构建学习过程布。根据贝叶斯公

35、式错可,其中是一个常数,与结构无关是边界似然,由公式可得计算贝叶斯网络结构的后验概率分布只需要为每个可能的结构计算边界似然。贝叶斯网络的结构学习分为两种情况:完备数据集和不完备数据集的情况。.完备数据下的结构学习目前,完备数据下的贝叶斯网络结构学习方法主要分为基于评分的方法和基于依赖分析的方法。一:基于评分的方法基于评分函数的结构学习方法有算法、爬山法等。这些算法主要由两部分构成:评分函数和搜索算法。其基本思路是首先随机初始化一个网络,由给定的评分函数为当前网络打分,然后对该网络进行局部的扰动,重新对扰动后的网络评分,并保留得分高的网络,如此循环进行下去,直到局部扰动后的网络评分小于给定阈值为

36、止。理论原则上这种方法是可以得到一个与当前数据拟合的最好的网络结构的,然而实际中如果要对一个具有个结点的网络进行学习,则需要对个网络结构进行打分并计算,这显然是一个难题。使用这类算法时可以通过如下方法使得打分搜索算法变得可行:如限定结点的个数、假定变量结点有序或者根据专家知识采用某些启发式的搜索规则等。常用的评分函数有贝叶斯评分准贝, 和最小描述长度准则,评分等。常用的搜索方法有全局搜索法和启发式搜索法包括爬山算法、紧急搜索、模拟退火即遗传算法等。:评分函数:贝叶斯评分准则贝叶斯评分准则能够充分利用有关拓扑结构的先验知识,给定训练样本集时,通过贝叶斯公式,拓扑结构的后验概率计算如下:一 中山大

37、学硕士学位论文其中为网络结构的先验概率,对这些先验分布作一般假设,表达式中 是与网络拓扑结构无关的常数,为一个边缘似然分布,可看作是对当前数据的概率的平均,而这个平均是针对所有可能的参数组合的某一个特定网络结构所对应的数据的概率而作的】。如果当前的数据集样本的数量足够大我们就可以得到正确的网络结构,所以是渐进一致的。:最小描述长度最小描述长度是由提出的,其源于通用编码的思想】。如果我们想在某种介质上存储样本,同时想节省存储空间,显然希望存储它的压缩版本。总描述长度可定义为的压缩版本总长度以及压缩模型的描述长度之和,而最优模型自然是总描述长度最短的模型。将用于贝叶斯网络,是综合考虑了网络结构与数

38、据的相似性以及网络的复杂度的结果,使得网络的描述长度和样本的编码长度之和最小,这说明了网络结构的学习过程必须要在网络结构表示样本的准确性与网络结构的复杂性两者之间找到平衡点。先考虑的计算过程。以距离和互信息为基础。假设随机变量的概率密度函数是,而是的一种近似,则和之间的距离命为距离,定义为:奴灿莓础器易知,距离表示概率密度函数和间的接近程度,距离越小表示越近似于,距离为。当且仅当等于.在信息论中,用相互信息表示发送或者收到某些信息后会给某些变量所带来的信息。而在贝叶斯网络中,对于有依赖关系的两个变量结点,当我们得到一个变量的信息后,就可以得到其它相应变量的一些信息,这些信息量是可以通过相互信息

39、来衡量的,因此判定两个变量之间是否存在依赖关系,我们可以通过相互信息计算,并且可以测量依赖程度的大小。基于距离和互信息理论,是从变量域中的所有网络拓扑结构中寻找最佳逼近真实概率分布,屹?,的形式。澳度有两个部分:网络模型的复】第三章贝叶斯网络的构建学习过程杂度;数据的似然函数值。钡度可以表示为:?其中,定义为:掣.岛为网络模型的维数,为样本样,礼为中结鼠一%魄点数,为每个结点不同状态的数目。似然函数使用父结点与子结点间的互信息描述.:评分评分函数以贝叶斯统计学为基础,定义为该结构相当于给定数据集的后验概率分布,即寻找后验概率分布最大的结构。评分函数本质上是的一种特殊形式,它假定各结点参数的先验

40、分布服从分布,那么我们可以得到评分公式:吼 心七 %詹%七,上一、/蓐?,片以别驯以鳓娶旦赢娶 吆老名 七式中是贝叶斯网络结构的先验概率分布,吆屉可由公式计算得到,是中每一个参数吼的先验值,弛表示实验样本数据集中变量墨取第个值,咒的父结点构成的集吼取第个值时的实例数目。:常用的搜索方法定义完了评分函数,贝叶斯网络的结构学习接下来要讨论的是搜索问题,即通过搜索算法找出具有最佳评分的网络结构,其实这是一个.问题。我们通常采用爬山搜索法、模拟退火搜索法等算法进行修正,包括反转、添加以及删除弧。通常假定网络中不含有环,且结点变量是有顺序的。其中最基本的搜索算法有启发式局部搜索算法例如贪心算法,其思想是

41、:从给定的初始结构开始,通过反转、添加以及删除的操作使得局部最大化,并逐步扩展到整体即整个网络。最经典的算法有算法和算法。年,提出的算法是一个非常经典的网络结构学习算法,它主要用于网络结构未知、数据集完整情况下的结构学习过程。该算法在已知网络中各结】中山大学硕士学位论文点变量的次序后,提出了结点模块化思路,也就是各结点的父结点相互独立。搜索算法在假定结点变量有序、所有搜索结构的先验概率相等的条件下,采用爬山启发式的搜索算法对网络结构进行搜索,即依次按照结点顺序为每一个结点寻找它的父结点集,并且通过不断地为每个结点增加父结点的方式来增加局部网络结构的评分,直到为每一个结点变量找到评分最高的父结点

42、集后停止搜索,在整个搜索过程中始终要求满足初始假定的结点顺序。基于评分的方法试图寻找精确性、稀疏性等多因素之间的平衡点,然而由于搜索方法的先天性弱点,该方法不见得一定会找到最好的结构。但是当训练样本数据集足够打且计算次数足够多时,该方法也能得到“正确”的贝叶斯网络结构。二:基于依赖分析的方法如果发现了系统中变量之间的某些依赖关系或者调控关系,则我们可以根据这些依赖关系来建立贝叶斯网络,所以我们可以将贝叶斯网络看作是编码了变量之间的独立性关系的图结构,而进行的学习就是通过数据样本集来验证条件独立性,五,是否成立的过程。如果成立,则我们说在网络中结点咒和玛被有向分隔,也就是结点托与之间不存在边,两

43、者独立,反之则称网络中变量五和玛是依赖的,也就是结点五与间存在边。经常使用的独立性检验方法有卡方检验和基于互信息的检验方法。基于卡方检验使用似然比卡方检验来验证条件独立性五,引是否成立,卡方统计量计算如下:一./若,成立,则置与玛之间存在边,有墨,玛,由此进一步可得统计量计算如下:一、”。”一”?妯川器知,墨,假设变量五,玛,分别有%。,%,。种取值,则服从自由度为%;一?%一亿的卡方分布,基于似然比卡方检验可以得到是否接受五与玛关于是条件独立的原假设,其中显著性水平通常取值为.,.,.等.第三章贝叶斯网络的构建学习过程基于互信息的检验最大互信息准则,越功与相似,以距离和互信息为基础,从所有网

44、络拓扑结构中,努力寻找最接近真实概率分布,?,的网络。与的区别是考虑了网络结构和参数的相似性,而对网络的复杂度没有约束。假定进行网络学习的变量域为,屹,?,炉,?,为训练样本在上的联合概率密度分布,上的实际联合概率密度函数为矽,屹,?,.贝叶斯网络中结点%的父结点组成的集合为舯魄,目标是建立合适的网络结构,尽量使样本的联合概率分布,耽,?,接近于真实的分布。现在使用,屹,?,?,度量两者之间的差异,也即寻找使距离最小的网络结构。,屹,?,叠,圪,?,?,?,沈?,一,圪,乞?, 一,?,?,?,可以看到,圪,?,?,的大小取决于,蚝的大小,舯%越大则,?,?,越小,所以在变量域上所有网络结构中

45、中使,屹最大的结构为即为,屹,?,的最佳逼近,此称为。总之,是与网络的维数成正比的,可以利用最大互信息原则使搜索中止于完全图。三:混合结构学习方法混合结构学习方法将以上两种方法结合,使用依赖分析检验降低搜索空间复杂度,然后使用评分搜索方法进行学习,找到最佳网络,常用的算法:稀疏候选算法及 等。.不完整数据下的结构学习对于含有缺失值的样本数据而言,贝叶斯网络结构学习比较困难,通常研究主要集中在基于评分的方法上。开始,等人提出选择贝叶斯网络结构的方法首先基于梯度的优化. 或算法进行极大后验概率】中山大学硕士学位论文估计,然后使用词分或拉普拉斯近似 等大样本的近似方法为近似结构打分。只是由于搜索空间

46、大、存在近似打分的误差等缺陷,该算法学习效率不高,计算结果也不够可靠】。年和提出了对结构学习使用算法的思想】,该算法首先以一个随机结构作为开始点,然后进行为网络选择参数和计算网络的记分的过程,接着增加边以构造新的网络结构并使用算法来计算新的网络参数的后验期望和后验值,同时计算新的网络结构的记分,如果该新记分高于原记分,则更新网络结构接受新的网络状态。年提出了经典算法,】,算法将结构搜索算法和标准算法相结合,要求在执行过程中始终有一个候选的网络结构,并且在每次循环的过程中都要计算期望统计因子,而这些期望统计因子是评价网络结构所需要的,从而可以发现何种评分标准下更好的网络结构。算法不是一个渐进的近

47、似值,而是试图在循环内直接优化真正的贝叶斯记分。当确定了评价贝叶斯网络拓扑结构与训练数据样本集的接近程度之后,结构学习就变成了一个优化问题。从理论上证明了有向图模型拓扑结构除树结构外的搜索都是问题,因此对于贝叶斯网络的结构学习问题,我们通常采用启发式搜索方法来寻求最佳的拓扑结构。.参数学习关于贝叶斯网络的参数学习,人们已经有了大量的研究成果。贝叶斯网络参数学习的目标是:在给定网络拓扑结构和训练样本数据集的情况下,结合先验知识,最终确定贝叶斯网络模型中各结点处的条件概率密度函数,记为:,。贝叶斯网络的参数学习可以通过专家领域知识、学习训练样本数据集来确定,而由于专家领域知识具有不完整性和不精确性

48、,从而影响了网络参数的准确程度。本节所讲即在已经确定网络拓扑结构的基础上,重点分析在样本数据完整和不完整的情况下的贝叶斯网络参数学习方法。.完整数据的参数学习当训练样本数据集完整时,通常情况下采用最大似然估计和贝叶斯方第三章贝叶斯网络的构建学习过程法来学习贝叶斯网络参数。采用这两种方法进行参数学习时,首先需要对贝叶斯网络和训练样本数据集作如下假定】:.离散型贝叶斯网络:即变量域中的所有变量结点属性都是离散的;.全局、局部独立性:即在给定贝叶斯网络拓扑结构和变量集的情况下,训练样本数据集中样本出现的概率有全局和局部独立性,也就是说参数向量之间是相互独立的。.多项式分布:耳练样本数据集中每个样本都

49、独立地来源于相同的多项式分布。.数据集完整:即训练样本数据集中每个样本都不存在缺失值的情况。给定,数据的条件概率称为的条件似然度,且记引为口的似然函数。为方便实验进行,我们通常对似然函数取对数就得到对数似然函数,.最大似然估计是依据样本与参数的似然程度来判断样本与模型的拟合程度。对数似然函数为: %最大似然参数每监,其中%惫.最大似然估计的基本原理是:选择参数的值,贝叶斯网络最合适的参数是使得似然函数值最大的参数痧。通常进行最大似然参数估计学习的一种标准步骤是:首先写出数据的似然表达式,它是待估计参数的一个函数其次对每个参数的对数似然进行求导最后找到满足导数为的对应参数值随着观测值数量越来越多

50、,的参数收敛于最佳的可能值,且寻找使样本数据集发生的可能性最大的参数以最大可能的接近真实的概率值,而且实例】中山大学硕士学位论文越多,表明接近程度越好。只是的缺陷是当样本数据集不大时,方法计算速度相对较慢,并缺乏处理先验知识的能力,而且得到的结果不是很可靠。.贝叶斯方法贝叶斯方法以贝叶斯学习理论为基础,其与传统的参数估计方法最大的区别在于这二者对不确定性的理解方面,后者是将概率视为频率的无限逼近,而前者则视不确定性是人们对事物的一种认知程度,而该认知程度是由原来的主观知识和观察到的现象共同作用的结果。通常使用贝叶斯方法对未知参数向量估计学习的一般步骤是:将未知参数看成是随机向量,这是贝叶斯方法

51、与传统的统计方法的最重要区别可以根据对参数口的认识,来确定先验分布尸口.这一步其实是贝叶斯方法容易引起争议的一步,因此经常受到经典统计界的攻击根据公式表示计算出后验概率密度函数,并作出对未知参数的推断从上式可以看出,贝叶斯方法在对未知参数向量的估计中综合考虑了它的先验信息和样本信息,而如最大似然方法的传统的参数估计方法只是简单从样本数据获得信息。贝叶斯估计首先假定了一个固定的未知参数,并考虑当给定拓扑结构时,参数的的所有可能取值,然后利用先验知识,努力找到给定训练样本数据集,和拓扑结构时所具有的最大后验概率的参数取值。由贝叶斯公式,我们可以得出:掣骅其中,为在给定拓扑结构郇寸参数,的先验概率分布,是与具体参数取值无关的常数。在有关贝叶斯网络的学习研究中,最常使用的先验分布是先,而先验分布有一组验分布。假定多项式的参数为:口,?,知,超参