（计算机应用技术专业论文）用贝叶斯网络挖掘网络日志的研究与实现.pdf

用贝叶斯网络挖掘网络同志的研究与实现 摘要 摘要 随着网络飞速发展，网络的规模越来越大。互联网络已经发展成为一个巨大的、 分布广泛的信息库，基于这个巨大信息库的应用将产生同样巨量的网络日志，这些网 络日志蕴含着极其丰富的可能被挖掘的隐含信息。对这些挖掘出的隐含信息进行分 析，可以提高网络提供的服务质量，有助于网络性能管理等。 贝叶斯网络是目前不确定知识和推理领域最有效的理论模型之一。本文将贝叶 斯网络运用于网络日志挖掘，为从网络日志中找出潜在的有用的信息，进行方法框架 的尝试研究，以有助于网络管理时做出正确的决策，提高网络服务质量。 本文描述了如何运用贝叶斯网络来挖掘一个真实的每天约有一千万条数据的大 型网络日志，以达到预测网络流量的目的。为了挖掘这么大的数据集，本文首先用一 些准则过滤和归并了数据集，并通过进一步地离散化，把原始的数据集转化为用于贝 叶斯网络学习的规整的数据集。然后针对单个小时和一天的数据分别采用基于评分 的方法加上o r s e a r c h 搜索算法和贝叶斯网络增量学习方法学习出贝叶斯网络模型， 在构造出的贝叶斯网络的基础上通过计算变量间的条件概率来预测网络流量。 大量的测试结果表明，预测网络流量的正确率从4 8 左右到8 0 左右，导致这 些差异的可能原因包括：预处理数据的离散化技术，从巨数据集学习贝叶斯网络的具 体方法，数据本身的噪声处理方法等。 本文为挖掘巨量真实的网络日志提供了有益的尝试。 关键词：贝叶斯网络；网络日志挖掘；流量预测；增量学习 作者：陈佳敏 指导教师：吕强 用贝叶斯网络挖掘网络同志的研究与实现 a b s t r a c t a b s t r a c t n e t w o r ki sb e c o m i n gt h em o s tp o p u l a re n v i r o n m e n t ，a n di th a sb e e nd e v e l o p e da sa h u g ea n de x t e n s i v ei n f o r m a t i o nd a t a b a s e u n d e rt h el a r g e s c a l ed a t a b a s e ，v a s tn e t w o r k a p p l i c a t i o n sp r o d u c eh u g en e t w o r kl o g sw h i c hmi g h th i d e a b u n d a n ti n f o r m a t i o nt ob em i n e d t of i n do u tt h e s eh i d d e ni n f o r m a t i o nc a ni m p r o v et h en e t w o r ks e r v i c eq u a l i t y i ti sg r e a t l y h e l p f u lt on e t w o r ka d m i n i s t r a t i o n b a y e s i a nn e t w o r ki so n eo ft h em o s te f f e c t i v em o d e li nt h ef i e l do fu n c e r t a i nk n o w l 。 e d g ea n dr e a s o n i n g t h i st h e s i sa p p l i e sb a y e s i a nn e t w o r k t on e t w o r kl o gm i n i n g ，f i n d i n go u t t h eu n d e r l y i n ga n du s e f u li n f o r m a t i o nf r o mn e t w o r kl o g ，i no r d e rt om a k ep r o p e rd e c i s i o n - m a k i n gi nt h ea d m i n i s t r a t i o no fn e t w o r k sa n dm a k er e l e v a n tm a n a g e m e n tt oi m p r o v e n e t - w o r ks e r v i c eq u a l i t y t h i st h e s i sd e s c r i b e sh o wt oa p p l yt h eb a y e s i a nn e t w o r kt om i n ear e a ll a r g en e t w o r k l o g ，w h i c hc o n t a i n ss e v e r a lt e n sm i l l i o nr e c o r d sp e rd a y , i no r d e rt op r e d i c tn e t w o r k t r a f f i c t om i n es u c hah u g ed a t a s e t ，t h i st h e s i sf i r s t l yf i l t e r sa n dm e r g e st h ed a t a s e tb ys o m ec r i t e r i o n t ot r a n s f o r mt h eo r i g i n a ld a t a s e ti n t ot h en o r m a t i v ed a t a s e tf o rl e a r n i n gb a y e s i a nn e t w o r k t h e nt h em e t h o d sb a s e do ns c o r em e t r i c sw i t ho r s e a r c ha l g o r i t h ma n da ni n c r e m e n t a l a p p r o a c ht ol e a r n i n gb a y e s i a nn e t w o r kf o rd a t a s e t so fd i f f e r e n ts i z e sa r ei n t r o d u c e d f i n a l l y , ac l a s s i f i c a t i o no ft h en e t w o r kt r a f f i ci sc o n d u c t e db yc o m p u t i n gt h ec o n d i t i o n a lp r o b a b i l i t y b e t w e e nt h ev a r i a b l e sb a s e do nt h ec o n s t r u c t e db a y e s i a nn e t w o r k l a r g ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea c c u r a c yo ft h ep r e d i c t i o no fn e t w o r k t r a f f i ci s f r o m4 8 t o8 0 t h er e a s o n sl e dt os u c hv a r i a n t sm i g h tb ed i s c r e t i z a t i o nt e c h n i q u e sw h e n p r e p r o c e s s i n gt h el o gs e t s ，l e a r n i n gb a y e s i a nn e t w o r ka p p r o a c h e sf r o ml a r g es c a l ed a t a s e t ， a n dn o i s ep r o c e s s i n go ft h el o gs e t s h o w e v e rt h i st h e s i sp r o v i d e sap r a c t i c a lf r a m e w o r kf o rm i n i n gn e t w o r kl o gb yb a y e s i a n n e t w o r k k e y w o r d s ：b a y e s i a nn e t w o r k ，n e t w o r kl o gm i n i n g ，p r e d i c t i o no fn e t w o r kt r a f f i c ，i n c r e - m e n t a ll e a r n i n g 1 1 1 w r i t t e nb y ：c h e nj i a m i n s u p e r v i s e db y ：l t iq i a n g 用贝叶斯网络挖掘网络日志的研究与实现插图 插图 一个贝叶斯网络结构 1 5 n a i v eb a y e s 网络结构1 6 t a n 网络结构 1 7 基于k 2 打分函数学习得出的贝叶斯网络结构。 4 5 第一天数据增量学习得到的网络结构 4 6 第二天数据增量学习得到的网络结构 4 6 第三天数据增量学习得到的网络结构 4 7 三天单个小时数据集预测准确率比较图 4 8 l 2 3 1 2 3 4 5 2 2 2 5 5 5 5 5 用贝叶斯网络挖掘网络日志的研究与实现表格 表格 2 1 b a y e s i a n 网络学习分类。8 3 1 每天日志文件的统计信息 2 6 3 2 每小时日志文件的统计信息 2 7 3 3 i p 地址转换成域名后属性取值比较1 3 1 3 4 p 地址转换成域名后属性取值比较2 3 2 3 5 地址转换成域名后属性取值比较3 3 3 3 6 属性值离散化前后取值比较1 3 4 3 7 属性值离散化前后取值比较2 3 5 3 8 属性值离散化前后取值比较3 3 6 5 1 第一天单个小时数据集的预测正确率 5 0 5 2 第二天单个小时数据集的预测正确率 5 1 5 3 第三天单个小时数据集的预测正确率 5 2 5 4 三天数据集的预测正确率 5 2 用贝叶斯网络挖掘网络同志的研究与实现算法 算法 1 o r s e a r c h 算法 4 0 2 e i l p 算法 4 3 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：煎羔蛆 日 期：垫墨：! ：! 羔 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 导师签名： 毳娆 日 用贝叶斯网络挖掘网络日志的研究与实现第一章引言 第一章引言 1 1 课题背景 随着数字网络的普及与计算机的普遍使用，数据收集的速度越来越快，对堆积如 山的数据的处理与理解已经成为计算机科学家与工程师所面临的必须解决的挑战性 的任务。适应这一迫切的任务需求，数据挖掘作为理论性与应用性结合最为紧密的一 个研究领域，迅速地发展起来。 数据挖掘从经验学习知识，以适应新的环境为目标，正在引起越来越多的研究与 应用人员的注意，是各种学科的综合运用，包括计算机科学、数学、工程学、物理学、 神经科学、认知科学等。 目前数据挖掘已经形成了各种比较成熟的学习技术和方法，例如：决策树学习算 法、决策规则表、神经网络、统计学习和概率图模型等，并且已经开发了许多成功的 应用软件。针对各种不同方法的不同特点，产生了理解这些方法的几个理论框架，比 如计算学习理论、贝叶斯学习理论、经典的统计学习理论及其最小描述长度原理等。 贝叶斯网络将先验知识与样本信息相结合、依赖关系与概率表示相结合，是数据 挖掘和不确定性知识表示的理想模型。与数据挖掘中的其他方法，如规则表示、决策 树、人工神经网络等相比，贝叶斯网络具有能够处理不完备数据、学习变量间的因果 关系、先验信息与样本知识有机结合起来等优点。贝叶斯网络坚实的理论基础、直观 的知识表达、灵活的推理能力以及方便的决策机制使其成为数据挖掘领域的新兴技 术【l 】。 利用贝叶斯网络对于事件或者属性间的带有不确定性的相互关系进行建模和推 理在医学诊断【2 】2 【3 】、故障诊断【4 】、信息提取【5 】、目标识别【6 】以及不确定推理和预 测【7 】等方面产生了很多成功的应用。贝叶斯网络在医学、生物信息学、经济、军事等 领域将有巨大的研究和应用前景。 1 2 课题内容 本论文的目的是用贝叶斯网络来挖掘一个真实的每天约有一千万条数据的大型 网络日志，以达到预测网络流量的目的。 本文首先对原始的数据集进行预处理，在对原始数据的分析研究以及大量的实 验的基础上找出了某些准则对原始的数据集进行过滤和归并，并通过对属性值的进 一步离散化，把原始的数据集转化为用于贝叶斯学习的规整的数据集。 第一章引言 用贝叶斯网络挖掘网络日志的研究与实现 在学习贝叶斯网络时，本文针对不同规模的单个小时和一整天的数据，采用了不 同的学习方法。对于单个小时的数据集，本文分别采用了基于b i c 评分和基于k 2 评 分的方法加上o r s e a r c h 搜索算法。对于一整天的数据，数据集规模非常的大，前面 的方法已经无法适用，因此把增量学习的思想应用到大规模数据集的贝叶斯网络的 学习当中。增量学习方法解决了由于数据集过大而无法全部存储在内存时贝叶斯网 络学习的困难，并且随着数据集的不断扩充，增量学习的方法对于新的训练集可以利 用以前学习所获得的结果，缩短了学习的时间。 学习得出贝叶斯网络模型之后，本文在构造出的贝叶斯网络的基础上通过计算 变量间的条件概率来预测网络流量，并且跟在其他方法构造出的贝叶斯网络基础上 的流量预测进行了比较。通过对网络流量的预测和分析，了解网络流量情况及其趋 势，从而作出相关的决策，为合理调整网络资源分配和发现网络的异常行为提供依 据。 1 3 课题意义 网络流量是衡量网络运行负荷和状态的重要参数，也是网络规划设计、保证服务 质量以及网管等的重要参考因素，对网络流量的预测是网络发展研究的重要内容。目 前常见的流量预测方法有神经网络、模糊理论以及小波分析【8 】等。 贝叶斯网络是目前不确定知识和推理领域最有效的理论模型之一，在医疗诊断、 目标识别、故障诊断、自然语言理解等许多方面都已经有了很多成功的应用。本文将 贝叶斯网络方法应用于网络日志的挖掘，进行网络流量的预测等，丰富了贝叶斯网络 的应用，提出了网络日志挖掘的新方法。 本文还针对实验数据集的不同规模采用了不同的学习方法，在大规模数据集的 贝叶斯网络的学习中引入了增量学习的方法，并用实际的数据集进行实验得到了较 满意的网络流量预测结果。 1 4 本文的组织结构 本文的主要章节安排如下： 第一章主要介绍本课题的背景、研究的内容以及研究意义。 第二章主要概述了贝叶斯网络的相关概念，讲述了当前国内外关于贝叶斯网络 学习方法的研究，以及贝叶斯网络的推理。综述了贝叶斯网络在各个领域中的应用情 况。介绍了贝叶斯分类器，并且详细描述了贝叶斯网络用于分类的实例。 第三章对原始数据集进行了描述和分析，详细介绍了预处理的方法以及过程，对 各个预处理阶段的相关数据进行了比较分析。并概述了数据挖掘的现状，综述了目前 2 用贝叶斯网络挖掘网络日志的研究与实现 第一章引言 网络日志挖掘的主要方法。 第四章详绍了贝叶斯网络的构造方法，针对不同规模的数据集分别采用了基于 打分加o r s e a r c h 搜索算法方法和增量学习方法，分别对两种学习方法进行了详细的 介绍。 第五章给出了本课题的实验结果并对实验结果进行了比较和分析。 第六章对本文的工作进行总结，并提出了需要进一步完善的地方以及进一步的 研究工作。 3 用贝叶斯网络挖掘网络日志的研究与实现 第二章相关技术概述 第二章相关技术概述 2 1 贝叶斯网络的概念 不确定知识的推理是人工智能领域一个重要的研究课题，贝叶斯网络将先验知 识与样本信息相结合、依赖关系与概率表示相结合，是目前不确定知识和推理领域最 有效的理论模型之一。贝叶斯网络又称为信念网络，是一种对概率关系的有向图解描 述，适用于不确定性和概率性事物。 贝叶斯统计和图论的发展为贝叶斯网络理论的引入提供了坚实的理论基础，而 人工智能、专家系统和机器学习在实践中的广泛应用，成为贝叶斯网络产生和发展的 催化剂。 贝叶斯网络建模主要是网络参数学习和网络结构学习。而贝叶斯网络推理实质 上是回答任何给定证据下的查询问题，包括因果推理、诊断推理以及支持推理等方 面。 2 1 1 贝叶斯网络的产生和发展 贝叶斯学派奠基性的工作是英国数学家t h o m a sb a y e s 的论文“关于几率性问题 求解的评论”【9 】。随后著名的数学家拉普拉斯( l a p l a c e e s ) 用贝叶斯的方法导出了 重要的“相继律”【1 0 】，贝叶斯的方法和理论逐渐被人们理解和重视起来。随着人工 智能的发展，尤其是机器学习、数据挖掘等兴起，为贝叶斯理论的发展和应用提供了 更为广阔的空间。 在8 0 年代早期，贝叶斯网络已经成功地应用于专家系统中对不确定知识的表 达，到9 0 年代，研究人员进一步研究可学习的贝叶斯网络，并将其用于数据挖掘和 机器学习。近年来，贝叶斯学习理论方面的文章更是层出不穷，内容涵盖了人工智 能的大部分领域，包括因果推理、不确定性知识表达、模式识别和聚类分析等，并且 出现了专门研究贝叶斯理论的组织和学术刊物i s b a ( i n t e r n a t i o n a ls o c i e t yo f b a y e s i a n a n a l y s i s ) 。在学术界，人工智能不确定性研究协会( a u a i ) 是组织人工智能不确定性 会议( u a i ) 的非营利性组织，更一般地说，该组织致力于促进不确定性知识表达、学 习和推理方面的发展研究。u a i 团体中提出的原理和应用都是在人工智能研究最前 沿的，已经举办了2 4 届的u a l 年会，成为人工智能领域的顶级学术会议。 在不确定性推理中，贝叶斯网络属于一种基于模型的内涵方法，它提供了特定领 域知识的一种模型表示以及基于这种模型的若干种学习和推理机制，用于建立模型 5 第二章相关技术概述 用贝叶斯网络挖掘网络日志的研究与实现 并回答与这些领域知识相关的询问，并在此基础上进行辅助的预测、决策以及分析 等。 2 1 2 贝叶斯网络的语义 贝叶斯网络是一个表示变量间概率依赖关系的有向无环图g ，可以用三元组 g - - 表示，图中的y 代表结点集，其中的每个结点代表一个有现实意义的 变量；边集a 也就是结点间的连接表示变量间的因果关系；p 是离散变量集合上的联 合概率分布，每一个变量都有一个条件概率表( c l y l ) ，描述该变量在给定其父结点 时的概率分布，表示了变量间因果关系的强度。贝叶斯网描述了一组变量上的联合概 率分布。 贝叶斯网络模型具有较强的适应信息变化的能力，可综合专家先验知识和实例 数据的分布特征，调整其网络结构和概率分布，识别变量之间潜在的联系以及关联强 度。 给定一个有向无环图g 和离散变量集合x = 【工l ，x 2 ，h ) 上的一个联合分布 函数p ，如果变量集合x 中的每个变量与网络中的每个结点一一对应，那么网络结构 g 就表示了概率分布p ，其表示如下： p ( x i , x 2 ，而) = 兀p ( x j l p a ( x 1 ) ) ( 2 1 ) 乞f 其中，p a ( x i ) 是x i 在g 中的直接前驱，称为父结点集合。在给定直接前驱变量的状态 的情况下，每个随机变量的状态只与直接前驱的状态相关，而与非直接的其它前驱无 关。 2 1 3 贝叶斯网络的优点 由于贝叶斯网络是联合概率分布和因果关系表示的完美结合，使得贝叶斯网络 比产生式规则、决策树、人工神经元网络和聚类等机器学习方法更具优越性。贝叶斯 网络作为一种图形化的建模工具，具有以下优点【1 1 】： 1 贝叶斯网络将有向无环图与概率理论有机结合起来，具有正式的概率理论基础， 同时也具有更加直观的知识表示形式。它一方面将人类所拥有的因果知识直接 用有向无环图自然直观地表示出来，另一方面将统计数据以条件概率的形式融 人到模型中。先验信息或领域知识在建模方面很重要，尤其是在样本数据稀疏 或者数据较难获得的时候。贝叶斯网络用弧表示变量间的依赖关系，用条件概 率表来表示依赖关系的强弱程度，将先验信息与样本知识有机结合起来，克服 6 用贝叶斯网络挖掘网络日志的研究与实现 第二章相关技术概述 框架、语义网络等模型仅能表达处理信息的弱点和神经网络等方法不直观的缺 点。 2 与一般知识表示方法不同，贝叶斯网络是对于问题域的建模，当条件或行为等 发生变化时，不用对模型进行修正。 3 贝叶斯网络没有确定的输人或输出结点，结点之间是相互影响的，任何结点观 测值的获取或者对于任何结点的干涉，都会对其它结点造成影响，并可以利用 贝叶斯网络推理来进行估计和预测。 4 贝叶斯网络能够学习变量间的因果关系。因果关系不仅可以对一些客观现象做 出解释，而且可以预测人类在客观世界的行为结果，是数据挖掘中的极为重要 的模式，原因有二：在数据分析中，因果关系有利于对领域知识的理解；在干扰 较多时，便于做出精确的预测。 5 贝叶斯网络能够处理不完备数据。例如考虑具有相关关系的多个输入变量分类 或回归问题，对标准的监督学习算法而言，变量间的相关性并不是他们处理的 关键因素，当这些变量中有某个缺值时，它们的预测结果就会出现很大的偏差。 而贝叶斯网络提供了较为直观的概率关联关系模型。 2 1 4 贝叶斯网络的学习 我们把根据用户的先验知识构造的贝叶斯网络称为先验贝叶斯网络，把将先验 贝叶斯网络和数据相结合而得到的贝叶斯网络称为后验贝叶斯网络。由先验贝叶斯 网络得到后验贝叶斯网络的过程称为贝叶斯网络学习，或者说，将先验贝叶斯网络和 数据相结合而得到后验贝叶斯网络的过程称为贝叶斯网络学习。贝叶斯网络学习是 用数据对先验知识的修正，贝叶斯网络能够持续学习，上一次学习得到的后验贝叶斯 网络变成下一次学习的先验贝叶斯网络。 学习贝叶斯网就是要寻找一种网络，能按某种测度最好地与给定实例数据集拟 合。一般而言，寻找一种网络包括寻找一种有向无环图结构g 和获得与g 中每个结 点相关的条件概率表。因此学习贝叶斯网络问题可以分为以下两方面【1 2 - 1 有向无环图即网络拓扑结构的学习，简称为结构学习； 2 网络中每个变量的局部条件概率分布的学习，简称为参数学习。 贝叶斯网络的结构学习和参数学习显然不是完全独立的：一方面结点的条件概 率很大程度上依赖于网络的拓扑结构；另一方面，网络的拓扑结构直接由联合概率分 7 第二章相关技术概述用贝叶斯网络挖掘网络日志的研究与实现 布的函数来决定。但一般情况下，我们还是把这两个方面分开来进行，因为带有太多 连接的复杂的网络结构所需观测的参数比较多，而为使获得这些参数达到某种信任 程度所需的数据量随着参数数量的增加而迅速增长，并且复杂的结构需要太大的存 储空间以及冗长繁琐的计算过程才能产生预测和解释。 因此，为使贝叶斯网络作为知识模型是可用的，在学习过程中致力于寻找一种最 简单的网络结构是非常必要的，这种简单的结构模型称之为稀疏网络，它含有最少可 能的参数及最少可能的依赖关系。 根据网络结构是否己知、数据集是否完整，可以把学习贝叶斯网络的方法分为四 类【1 3 】，各种情形学习重点及方法如下表所示； 网络结构已知网络结构未知 数据完备概率参数学习，简单统计估计，m l e找最优网络结构：m d l ，b d e 等评价标 方法，b a y e s i a n 方法 准，启发式搜索，模拟退火搜索等算法 数据不完备找最优概率参数，e m 算法，基于梯度既要找最佳结构，又要找最优参数，有 方法，蒙特卡洛法，高斯算法等结构e m 算法，混合模型 目前除了数据不完备且网络结构未知，其他三种情况的贝叶斯网络学习的主要 问题已经被成功解决，相应的学习方法趋于成熟和完善，然而在数据不完备且网络结 构未知的情况下，贝叶斯网络的学习还是一个富有挑战性的研究课题，尚缺乏行之有 效、普遍适用的解决方法。 根据本课题的研究内容，下面主要就数据完备情况下的贝叶斯网络结构学习和 参数学习的方法进行介绍。 2 1 4 1 贝叶斯网络参数学习 贝叶斯网络的参数学习，实质上是在已知贝叶斯网络结构的条件下，来学习每个 结点的条件概率表。早期的贝叶斯网络的条件概率表是由专家的知识指定的，然而这 种仅凭专家经验指定的方法，往往将导致与观测数据产生较大的偏差。当前比较流行 的方法是从数据中学习这些参数的概率分布，这种数据驱动的学习方法具有很高的 适应性。 随机数据集d = ( x i , x 2 ，f l 有m 个实例，每个实例f 中都观察到了所有n 个变量x l , x 2 ，而的取值，d 也称为样本。 定义。是不确定变量，其取值岛表示结点变量f 上的条件概率分布，o 即为网 络参数。 8 用贝叶斯网络挖掘网络日志的研究与实现 第二章 相关技术概述 对于完备数据集d 进行参数学习的目标是找到能以概率形式p ( x i o ) 概括样本d 的p 。参数学习一般要先指定一定的概率分布族，如卢分布、多项分布、正态分布、泊 松分布等，然后利用一定的策略估计这些分布的参数。 虽然参数学习的具体方法和不同的概率分布族有关，但是学习的基本思想是一 致的。由于贝叶斯网络主要处理的是离散变量，对于连续变量一般要经过一定的离散 化处理，而离散化变量又以口分布和多项分布最为常见。 对于完备数据集的学习，有两种常用的学习方法：最大似然估计m l e ( m a x i m u m l i k e l i h o o de s t i m a t i o n ) 方法和贝叶斯( b a y e s i a n ) 方法。它们都是基于下面的独立同 分布i i d ( i n d e p e n d e n ti d e n t i f yd i s t r i b u t i o n ) 假设前提的： 样本中的数据是完备的； 各实例之间是相互独立的； 各实例服从统一的概率分布。 在此假设前提下，参数之间是相互独立的。 1 最大似然性估计m l e 方法【1 4 】 m l e 是基于传统的统计分析的思想的方法，它根据样本与参数的似然程度来评 判样本与模型的拟合程度。似然性是评判具体9 好坏的一种标准。似然性函数 为： l ( o ：d ) = p ( d i o ) = 几p ( x i l o ) ( 2 2 ) 似然性越大，依据口产生的样本的可能性越大，具体的口越好。m l e 算法的思 想是找到使似然性最大的参数0 ，这是直观上最容易想到的方法。 从统计学的原理我们可以知道，m l e 具有一致性、渐进有效性和表示灵活性等 优点。 2 贝叶斯方法【1 2 】 m l e 方法没有利用先验知识，收敛的速度较慢，贝叶斯方法克服了这一缺点。 贝叶斯方法与传统的统计方法最大的差别就是两者对不确定性的看法不一样， 传统的统计方法把概率简单地看作是频率的无限趋近，而贝叶斯方法认为不确 定性是人们对事物的一种认知程度，这种认知程度是由原来的主观知识和观察 到的现象共同决定的。因此贝叶斯方法学习网络参数由两部分组成：观测前的 先验知识和观测到的数据。在贝叶斯网络参数学习中，先验知识包括参数的先 9 第二章相关技术概述用贝叶斯网络挖掘网络日志的研究与实现 验分布的选取和分布参数的选取规则。学习任务就是找到一定的算法把二者有 机结合起来。 贝叶斯方法利用贝叶斯网络表示数据取样过程中的不确定性。已知口，x 的各个 观察值之间是相互独立的，由样本d 预测p + 1 发生的概率实际上是贝叶斯网 络推理的过程。 贝叶斯方法学习概率分布，其实是更新变量的后验概率。其基本思想是估计先 验概率p ( o , i g “) ，利用d 将先验概率p ( o , i g 6 ) 更新为后验概率p ( o , i d ，g 6 ) 。 贝叶斯网络可以看作是通过条件独立关系组织在一起的概率分类( 回归) 函数 的集合。产生概率输出的分类( 回归) 模型包括线性回归、广义线性回归，概率 神经网络等。这些模型都可以用于贝叶斯网络的概率学习，最常用的是贝叶斯 方法。当今研究最广泛的模型包括无限制的多项分布【1 5 】、带有高斯噪音的线 性回归【1 6 和广义线性回归。 3 m l e 方法和贝叶斯方法的比较 当实例充分多时，m l e 方法和贝叶斯方法收敛于同一个概率值，并且都是在线 累加充分统计因子的统计方法。但大多数情况下两种方法产生的估计值不同， 原因之一是两种方法对一个好的估计方法的定义不同，只要估计方法本身具有 一致性就是正确的计算p 的方法。 2 14 2贝叶斯网络结构学习 网络结构的学习中，有向弧的多余和缺乏都将影响需要学习的概率参数，无法准 确揭示领域结构和应有的因果关系，因此，网络结构的学习要力求准确。 网络结构学习的目标是找到和样本d 匹配度最高的贝叶斯网络，目前，具有完 备数据的贝叶斯网络结构学习方法比较成熟。基于c l 测试的方法( c o n s t r a i n tb a s e d ) 和基于打分的方法( s c o r eb a s e d ) 是两种不同的结构学习方法。 基于c i 测试的方法 基于c i 测试的方法通过一些有效的测试手段找出d 中的条件独立依赖关系， 由此确定网络中的结点是否存在边的关系。c i 测试致力于寻找和这些条件独 立依赖关系最相符的网络模型。 基于打分的方法 基于打分的方法通过定义某个评分的标准，来评判某个具体的网络结构反映出 的独立及依赖关系和数据集匹配的程度，即两者的拟合程度。通常，打分值越 1 0 用贝叶斯网络挖掘网络日志的研究与实现 第二章相关技术概述 高，网络模型与数据集的拟合程度越好。选择适宜的搜索算法搜索分值最高的 网络模型。 这两种方法各有各的特点，基于打分的方法过程简单、规范，但由于搜索空间 大，一般要求结点有顺序，并且根据打分函数的可分解性进行局部确定或者随 机搜索，效率较低且易于陷人局部最优结构。基于c i 测试的方法过程比较复 杂，但在一些假设下学习效率较高，而且能够获得全局最优结构。基于打分的 方法是比较常用的结构学习方法，该方法需要解决的关键技术是评分函数和搜 索算法。 1 基于c i 测试的方法 c h e n g 提出一种基于信息论的方法【1 7 】 1 8 1 ，采用以信息论为基础渐进正确的 结构学习方法来有效地搜索可能的网络空间，这种算法的效率很高，所以很快 就能构造一个和实际的网络结构很相近的候选网络。学习过程大致有以下几 步： ( a ) 画草图 设c ：= g ) 是结点集合，初始弧集合a ：= 移 ，而l ：= ( c f ，c j ) l l ( c i ，c j ) s j 是所有紧密性度量大于阈值的结点对。每一对结点的紧密性度量利用信 息论中表示两结点相互信息的公式( 2 3 ) 来计算： 婀删。善伽丽p ( c c j ) ( 2 3 ) 当，( c f ，o ) s 且在这两个结点间不存在开放路径时，用一条弧连接结点 对，检查每个结点对，确定初始连接图的弧a ：= a r c ( c i ，c j ) l ( c i ，c j ) j 乙且在 这两个结点间不存在开放路径 ，待确定的弧集合u 表示满足紧密性度量 且在结点间存在开放路径的所有结点对，u = l a 。 ( b ) 增厚图 对于图中的每一个结点对( c f ，c j ) u ，寻找它的最小阻碍集合， b ：= m i n c u t s e t ( c i ，e ，c u r r e n t g r a p h ) 并用条件互信息公式( 2 4 ) 对这一结点 对进行c i 测试： 邶删丑) = p ( c i , c j , b ) l o g 瓦p ( 丽c i , c ：l b ) ( 2 4 ) c i c j ，c k 。 、7 如果，( c f ，c j i b ) s ，则a = au ( c i ，q ) 。 1 1 第二章相关技术概述 用贝叶斯网络挖掘网络同志的研究与实现 ( c ) 削减图 对于映射中的每一条弧a r c ( c f ，c j ) a ，如果在这两结点间除了这条弧之外 在这两结点间仍存在开放路径，暂时移去这条弧a ：= a a r c ( c i ，c i ) ，然后 寻找该结点对的最小阻碍集，并执行c i 测试，如果两结点是依赖的，保留 这条边，否则将该边移去。 经过以上几步的学习，就构造了一个基于信息论测试方式的和实际的贝叶斯网 络结构很相近的候选网络，但这个网络并不是很精确。下一步需要对这个候补 网络进行进一步的学习精简，以使学习到的贝叶斯网络精确。基于信息论的方 法其算法复杂度为o ( n 2 ) 。这和其它一些算法如启发式搜索相比更有效率。这种 算法的问题在于：对于大的条件集，条件独立性测试难于完成，除非知识数据 集中的事件数很大。 2 基于打分的方法 基于打分的方法是一种基于数据统计的方法，它试图在准确性、稀疏性等多个 因素中寻找一个平衡点，是比较常用的结构学习方法。 基于打分的结构学习方法主要由两部分组成：评分函数和相应的搜索算法。评 分函数给出一定网络结构下，联合分布的一种概率度量。假设用，来表示相应 的打分函数，用它来评价每个候选贝叶斯网络g 与数据集d 的拟合程度，贝叶 斯网络的学习实质上就转化为了根据函数，的值寻找晟好的贝叶斯网络的问 题。 ( 幻评分函数 贝叶斯网络的结点只和其父结点有直接的因果关系，与其他结点无关，因 此打分机制具有可分解特性。评分函数可以分解为： 三 f ( g ：d ) = f ( x i ，p a ( x i ) ：心，e a ( 砧) ) ( 2 5 ) 百 其中，坛，) 是数据集d 中变量x i ，p a ( x , ) 取值情况的统计值。 常用的评分标准有贝叶斯信息准则( b i 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 ) 【1 9 】、最小描述长度( 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 ) 【2 0 1 ，以及基于 贝叶斯统计思想的b d e 评分方法和l ( 2 评分方法 1 5 】等。 数据完备时，这些评分标准都具备可分解性，可以分解成关于每个参数的 局部因式，利于计算。b d e 评分标准需要先验网，但是能自然地利用先验 知识和经验。b i c 、m d l 和b d e 方法都具有一致性和渐进有效性，都将收 敛于同一个常数，并且都是分值等价的，即等价的网络结构其评分相同。 1 2 用贝叶斯网络挖掘网络日志的研究与实现 第二章 相关技术概述 ( b ) 搜索算法 搜索算法是为了搜索某个评分函数分值最高的网络结构，总的说来，寻找 最优的模型是n p 问题，需要借助于启发式搜索。完备数据时，因为评分 函数即启发信息具有可分解性，并且参数学习需要的充分统计因子易于统 计，启发搜索速度相当快。某些情况下，搜索问题还可以简化为简单的优 化问题，如树形学习等。 常用的搜索算法有k 2 算法和爬山法，也可以用贪心策略、禁忌搜索【2 1 】、 模拟退火【2 2 】以及遗传算法【2 3 1 、最优最先( b e s t - f i r s t ) 搜索等组合优化领 域中的其它启发式搜索算法。 关于搜索算法，另一个需要考虑的问题是搜索空间，前面讨论的搜索算法 都是在整个贝叶斯网络的结构空间中进行，但在一些情况下，贝叶斯网络 存在着假设等价关系，也可以在不同的网络结构等价类之间搜索。这样做 的好处是搜索空间变小，局部极值也变少，缺点是从一个网络结构变动到 另一个网络结构需要做更多的操作，花费更长的时间。迄今为止，还没有 关于等价搜索的优势和代价之间孰重孰轻的比较。 对于数据不完备的情况，如何进行贝叶斯网络学习还是难点问题，因为在 实际情况下，数据集不完整的情况还是存在的。虽然贝叶斯网络在数据集 不完整的情况下能进行有效的推理，但它需要完备的数据集进行网络的学 习。为了解决这一问题，大量学者进行了研究，由于这已经超出本课题的 研究范围，相关算法在这里不一一阐述了。 2 2 贝叶斯推理 不确定性( u n c e r t a i n t y ) 是智能问题的本质特征，智能主要反映在求解不确定问 题的能力上。往往这种不确定性表现在证据、规则和推理等方面。贝叶斯网络的推理 长期以来一直是人工智能领域中的一个重要难题。贝叶斯网络相对于其它数据挖掘 算法的优势之一表现在：贝叶斯网络的推理不区分是前向推理还是后向推理，网络中 的每个结点都可以输入信息和输出信息，具有灵活的信息推理能力。 用贝叶斯网络解决的推理问题大致可以分为诊断、预测和决策制定，而解释通常 是诊断方法和预测方法的混合。诊断是指在给出证据的条件下推测引发此现象的各 种原因的值，即推测哪种原因是最可能的；预测是指在给出假设结点的情况下，预测 可能的影响；而决策制定涉及到决策结点的影响。 此外，人们通常根据推理的对象和计算复杂程度的不同来判断是采用精确推理 还是近似推理。理论上，精确推理能够满足任何推理任务，然而随着网络规摸的扩 1 3 第二章相关技术概述 用贝叶斯网络挖掘网络日志的研究与实现 张，精确推理的时间是难以预测的，同时网络拓扑结构的一个微小变动可能使相对简 单的问题变得相当复杂，所以研究近似的推理算法成为一个相当活跃的领域，近似推 理是为了降低精确推理的复杂性而提出的。 贝叶斯推理要用到先验信息，当进行推理缺乏必要的条件或数据时，依靠经验或 者历史资料来收集、挖掘和加工先验信息，形成先验分布进行推理，以提高挖掘质 量。从数掘挖掘的过程和目的来看，对一个数据集进行挖掘，事先并不知道能从数据 集中挖掘出什么样的知识，如果用先验信息来弥补这样的不足，就是说用贝叶斯推理 来进行挖掘，那就有可能提高挖掘的质量。 贝叶斯网络的推理实际上是进行概率计算。具体而言，在给定一个贝叶斯网络的 模型的情况下，根据己知条件，利用贝叶斯概率中的条件概率的计算方法，计算出所 感兴趣的查询结点发生的概率。在贝叶斯网络推理中，具体划分以下几种推理方式： 1 因果推理 因果推理是由原因推结论，也称为由项向下的推理。目的是由原因推导出结果。 已知一定的原因( 证据) ，则用贝叶斯网络的推理计算，求出在该原因的情况下 结果发生的概率。 2 诊断推理 诊断推理是由结论推知原因，也称为由底向上的推理。目的是在己知结果时， 找出产生该结果的原因。已知发生了某些结果，根据贝叶斯网络推理计算，得 到造成该结果发生的原因和发生的概率。该推理常用在病理诊断、故障诊断中， 目的是找到疾病发生和故障发生的原因。 3 支持推理 支持推理，提供解释以支持所发生的现象。目的是对原因之间的相互影响进行 分析。 贝叶斯网络推理的目的是通过联合概率分布公式，在给定结构和己知证据的情 况下，计算某一事件发生的概率。理论上，在给定网络结构和条件概率表的前提下， 任何查询都可以通过反复应用贝叶斯公式和乘积与求和公式得到。 图2 1 给出了一个贝叶斯网络结构，假设事件a 、b 、c 、d 作为已知证据，那么事 1 4 用贝叶斯网络挖掘网络日志的研究与实现 第二章相关技术概述 图2 。h 一个贝叶斯网络结构 件e 发生的概率的计算如下所示： p ( e k 如加错 p ( e ，a ，b ，c ，西 一p ( p 7 ，a ，b ，c ，由 p ( p ) p ( 口) p ( 易) p ( c l p ) p ( 翻p ，a ，易) 一p ( e 7 ) p ( a ) p ( b ) p ( c l e 7 ) p ( d l e ，a ，b ) p ( p ) p ( c 1 p ) 尸( d l p ，a ，易) 一p ( e 7 ) p ( c l e 7 ) 尸( 卅p ，以，6 ) 网络的结构特征和相关查询的类型是选择和设计推理算法应该考虑的主要因素。 网络的结构特征主要包括网络的拓扑结构、网络的类型、网络规模的大小、网络中领 域变量的类型和分布特征。其中网络的拓扑结构是影响推理性能的关键。 贝叶斯网络的独立性断言使得推理算法具有可操作性。独立性好的贝叶斯网