基于贝叶斯网络的数据挖掘研究.doc

分类编号： 单位代码：10065密 级： 学 号：05209029 研究生学位论文论文题目：基于贝叶斯网络的数据挖掘研究 学 生 姓 名： 徐 计 申请学位级别：工学硕士 申请专业名称：计算机应用技术 研 究 方 向： 数据挖掘 指导教师姓名： 张桂芸 专业技术职称： 副教授 提交论文日期： 独 创 性 声 明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得天津师范大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签 名：日 期： 学位论文版权使用授权书本人完全了解天津师范大学有关保留、使用学位论文的规定，即：学校有权将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的论文在解密后应遵守此规定)签 名： 导师签名： 日 期： 天津师范大学硕士学位论文基于贝叶斯网络的数据挖掘研究摘 要贝叶斯网络是贝叶斯方法与图形理论的有机结合。由于理论上的严格性和一致性，以及有效的局部计算机制和直观的图形化知识表达，贝叶斯网络已经成为人工智能领域的研究热点。本文将贝叶斯网络应用于农业科学领域，对某农场的牛奶产量进行学习与预测，完成了用贝叶斯网络方法进行数据挖掘的整个流程，并将获得的结果与多元线性回归方法得到的结果进行了比较。本文的主要工作和创新之处如下：(1) 简要介绍了数据挖掘的概念和相关技术，阐述了贝叶斯网络的基本原理和方法。(2) 在数据预处理阶段，采用了作者于2007年3月提出的Chi2变形算法。该算法在保持数据忠实性的同时，将各预测变量的取值离散化，以便于贝叶斯网络方法的应用。(3) 在网络结构搜索阶段，采用了带启发规则和随机重启机制的贪心算法。此方法充分利用了领域知识，再结合变量本身的含义制定了五条启发规则，大大减小了搜索空间。带随机重启机制的贪心算法，既保留了贪心算法的简洁特性又克服了其可能陷入局部最优的缺点，获得了可与众多智能搜索算法相媲美的结果。(4) 在贝叶斯网络推理获得离散值结果后，为了提高预测的精度，进一步考虑了如何将离散取值还原为连续值得问题，而不是简单的采用相应区间上的中位数。另外，在将两种方法的结果进行比较时，先把原始数据排序得到新的显示序列，避免了散点图的杂乱，使得贝叶斯网络结果的优越性更加显而易见。关键词：数据挖掘，贝叶斯网络，Chi2变形，贪心算法，线性回归iiiResearch on Data Mining Using Bayesian Network Abstract Bayesian Network is the combination of Bayesian theory and the graph theory. Because it is strict and consistent in theory, and also due to its effective local computation mechanism and visualized knowledge representation, Bayesian Network has attracted most attention of researchers from the AI field. In this paper, Bayesian Network was applied to deal with data from agricultural domain, more specifically, to predict the milk output of a certain farm after having studied its history data. The whole procedure of data mining using Bayesian Network is completely done, and subsequently we made a comparison between the results generated by Bayesian Network and multinomial linear regression. The main work and innovations of this paper are as follows:1. The concepts and related techniques of data mining are briefly introduced. The basic principles and methods of Bayesian Network are described with details. 2. In the data pre-processing stage, a variation of Chi2 algorithm put forward by the author in March, 2007 is employed. The algorithm discretizes the predicting variables without sacrificing the fidelity of the training data, hence makes it convenient to use Bayesian Network method.3. In the stage of structure searching, applied is the greedy algorithm with heuristic rules and random restart mechanism. This method takes full advantage of the domain knowledge and the semantics of the variables to work out five heuristic rules. In this way, the search space is dramatically reduced. The greedy algorithm with random restart mechanism remains the merit of simplicity and overcomes the shortcoming of probably being trapped in the local optimality, therefore gains as good results as most of the intelligent searching algorithms. 4. After we getting the discrete-valued result through Bayesian Network inference, the question of how to transform the discrete values into continuous ones is also considered in order to improve the prediction accuracy, instead of straightly using the median of corresponding interval.In addition, when the results generated by the two methods are brought to make a comparison in a visualized way, a new order produced by sorting the original data is adopted to avoid the chaos in the scatter figure. So, the better performance of Bayesian Network with respect to this problem is much clearer.Key words: Data Mining, Bayesian Network, A variation of Chi2, Greedy Algorithm, Linear Regression天津师范大学硕士学位论文基于贝叶斯网络的数据挖掘研究目 录摘 要IAbstractII第一章绪论11.1知识发现的相关概念11.1.1数据、信息与知识11.1.2 知识发现11.2 知识发现的步骤21.3 知识发现的功能31.3.1 数据总结31.3.2 分类31.3.3 聚类31.3.4 相关性分析41.4 知识发现的方法和技术41.4.1 统计方法41.4.2 机器学习的方法61.4.3 神经计算71.4.4 混合算法71.5论文组织7第二章贝叶斯网络92.1 贝叶斯学习理论92.2 贝叶斯网络的产生、发展和研究现状92.3 贝叶斯网络的定义102.4 贝叶斯网络中的独立关系和因果关系112.4.1 独立关系112.4.2 因果关系132.5贝叶斯网络的结构模型学习132.5.1 评分函数142.5.2 搜索策略142.6贝叶斯网络的局部概率学习152.6.1先验分布的选取152.6.2 局部概率学习的步骤162.7 贝叶斯网络推理172.8 小结18第三章算法及实验过程193.1 实验背景及领域知识193.1.1 实验背景193.1.2 关于牛奶产量的领域知识193.2 实验中的若干关键算法213.2.1数据预处理阶段的算法213.2.2 网络结构学习阶段的算法233.2.3 局部概率学习阶段的算法343.2.4 运用贝叶斯网络进行推理的算法353.3 实验程序的模块及其功能介绍363.3.1 程序模块及其关系363.3.2 实验环境介绍373.3.3 程序的实现383.4 小结40第四章结果比较与分析424.1 贝叶斯网络学习的结果424.2多元线性回归分析的结果434.2.1回归分析简介434.2.2 多元线性回归及其标准输出434.2.3 多元线性回归分析处理本例的结果444.3 两种方法的比较与分析464.4 小结47第五章结束语485.1 总结485.2 展望49参考文献50致 谢53攻读硕士学位期间发表学术论文情况54第一章 绪论1.1知识发现的相关概念1.1.1数据、信息与知识在信息科学中，数据是事物、概念或指令的一种形式化的表示形式，以便于对它们进行通信、解释或处理。信息是根据数据表示所采用的约定，赋予数据的意义。数据是信息的载体，与具体的介质和编码方式有关；同样的数据形式，可能因为约定的不同，而表达不同的信息。可以说，信息与数据的关系与哲学范畴内容和形式的关系比较相似。信息经过加工和改造之后就形成了知识。知识是人类在实践的基础上产生、又经过实践检验的、对客观实际可靠的反映。知识是人脑创新的结果，是人类智慧的结晶。知识按照它的内容特征，一般可以分为陈述性知识、过程性知识和控制性知识。陈述性知识提供概念和事实，描述状态、环境和条件等，使人们知道“是什么”。过程性知识提供有关状态的变化、问题求解过程的操作、演算和动作的描述，使人们知道“如何做”。控制性知识是用控制策略表示问题的知识，常常用来协调整个问题的求解过程。知识具有客观性、相对性、进化性、依附性、可重用性和共享性。1.1.2 知识发现知识发现是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。其中，“有效”指发现的知识对于新得数据能保持一定的可信度；“新颖”指要求发现的模式应该是新的而不是已经显然成立或者众所周知的；“潜在有用”是指发现得知识有一定的效用，比如可以用来指导将来的一些工作，提高经济效益；“最终可理解性”意为发现的模式能够被用户理解，主要体现在简洁性上；“模式”指的是数据集中蕴藏的结构或者规律；“非平凡”指知识发现的过程要具有一定的智能性和自动性，例如仅仅对所有得数据在某个字段上求和就不能算一个发现过程。知识发现将信息变为知识，从数据矿山中找到蕴藏的知识金块，将为知识创新和知识经济的发展作出贡献。知识发现的应用领域非常广泛，可以是经济、工业、农业、军事、社会、商业等。知识发现的直接作用对象也可以由很多种，比如数据库、文本、web信息、空间数据、图像和视频数据等等。由于知识发现是一门受到来自不同领域的研究者共同关注的一门学科，因此它有很多不同的术语名称。除了KDD（knowledge discovery in database, 数据库知识发现）之外，还有如下若干中提法：数据挖掘(data mining)、知识抽取(information extraction)、信息发现(information discovery)、智能数据分析(intelligent data analysis )、探索式数据分析(exploratory data analysis)、信息收获(information harvesting)、数据考古(data archeology)等等。最常用的是“知识发现”和“数据挖掘”。1.2 知识发现的步骤一个完整的知识发现的过程一般包括以下三个步骤：（一）数据准备（data preparation）数据准备又可以分为数据选取、数据预处理和数据变换三个阶段。其中，数据选取是确定知识发现任务的操作对象，即用户提供的原始数据集；数据预处理可能包括消除噪声、推导计算缺失数据、消除重复数据记录和进行数据类型的转换；数据变换主要是指消减数据维数，从初始特征中找出真正有用的特征以降低数据挖掘过程中的计算复杂度，同时又保持挖掘的准确性。数据预处理和数据变换这两个阶段可能会互相交织在一起，而没有明显的界线。（二）数据挖掘数据挖掘是整个知识发现过程中最重要的一个环节。在本环节中，首先要决定知识发现的任务是什么，比如说是分类、聚类还是关联规则发现等。确定了任务之后，就要选择挖掘算法。选择时主要从两个方面考虑，一是数据的特点，没有任何一种挖掘算法能在所有的数据集上优于其它的算法，因此针对不同特性的数据集选用不同的算法是很重要的；二是用户或者实际运行系统的需求，比如搞清楚用户是需要描述性的（descriptive）还是预测性的（predictive）知识。尽管数据挖掘算法是知识发现的核心，但要获得好的挖掘结果，必须对各种挖掘方法的要求或前提假设有充分的理解。挖掘过程中没有简单的操作指南，而是在采用已有理论框架的前提下，针对具体的数据特点和领域知识，充分发挥个人的主观能动性，多尝试多总结以获得更好的挖掘效果。（三）结果的解释和评价（interpretation and evaluation）数据挖掘的结果是描述性或解释性的知识，这些知识的计算机表示可能用户并不能理解，这就需要挖掘人员向用户提供结果的解释。数据挖掘的任务不同，对其结果的具体评价方法会有差异。如果评价结果不理想，则要对挖掘的过程进行回溯，退回到前面某一阶段，修改参数甚至修改算法重新实验。1.3 知识发现的功能1.3.1 数据总结数据总结是指对数据进行浓缩分析，给出其紧凑的特征描述。传统的数据总结方法包括计算数据库各字段上的和、均值、方差等统计值，或者用直方图、饼状图等图形方式表示。数据挖掘主要从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次的过程。数据泛化目前主要有两种技术：多维数据分析方法和面向属性的归纳方法，前者针对的是脱机的历史数据，而后者可以处理联机数据。1.3.2 分类分类是数据挖掘中一项非常重要和常见的任务，目前的实际应用最多。分类的目的是构造一个分类器，把用户提供的数据项映射到给定类别集中的某一个类。分类和回归都可以用于预测，即从历史数据中推导出给定数据的推广描述，进而对未来数据进行预测。两者的不同之处是分类的输出是离散的类别值，而回归的输出是连续数值。要构造分类器，需要有一个训练样本数据集作为输入，一个样本可以表示为（v1,v2,vn; c）,其中vi是属性值，而c是类别标签。分类的效果一般和数据集本身的特点有关，普遍认为不存在能适应各种特点数据的分类方法。1.3.3 聚类聚类是根据数据集中数据的不同特征，将数据划分为不同的类别。在聚类过程中，寻找某种算法，该算法产生的距离度量能使属于同一类别的个体之间的距离尽可能的小，而不同类别上的个体之间的距离尽可能的大。聚类的方法有统计方法、机器学习方法和面向数据库的方法等。在机器学习中，聚类称作无监督或无教师归纳。因为与分类学习相比，分类学习的训练数据有类别标志，而要聚类的数据没有类别标志。聚类中，数据的类别标志由算法来自动确定。人工智能文献中，常常称聚类为概念聚类，因为这里的距离不再是统计方法中的几何距离，而是根据概念的描述来确定的。1.3.4 相关性分析相关性分析是为了发现特征之间或者数据之间的相互依赖或者相互影响的关系。数据的相关性是一类很重要的可发现的知识。如果从一个元素A的值可以以某个概率P推导出元素B的取值，则称B依赖于A。这里的元素可以是特征，也可以是特征之间的关系。依赖关系分析的结果有时候可以直接提供给用户。然而通常情况下，当P很大时，所反映的依赖关系是特定领域中人所共知的常识，而不是什么新发现。自动查找依赖关系是一种有用的方法。常用的技术中就包含了贝叶斯网络，当然还有其他的方法，如回归分析，关联规则挖掘等。1.4 知识发现的方法和技术1.4.1 统计方法统计方法是从事物的外在数量表现去推断该事物可能的内部规律。科学的规律一般是隐藏的，首先总是从数量上通过统计分析表现出一些线索。根据这些线索，研究者提出一定的假说，再进行深入的理论研究和科学实验以对该假说进行证实或证伪。下面简要介绍与统计学有关的机器学习方法。l 传统的统计学方法统计学在解决机器学习问题中起着基础性作用。传统的统计学主要研究当样本数量趋于无穷多的是性质，主要考虑测试预想的假设是否与数据模型拟合。它依赖于显式的基本概率模型。统计方法处理过程分为三个阶段：（1）搜集数据：采样、实验设计（2）分析数据：建模、知识发现及可视化（3）进行推理：预测和分类常用的统计方法有回归分析（多元线性回归、自回归等），判别分析（如贝叶斯判别和费希尔判别），聚类分析和探索性分析等。目前国际上已经有很多统计软件，其中流行的有SAS，SPPS和Minitab等。l 模糊集模糊集是指这样一种集合,其元素均在一定程度上属于或不属于该集合。描述元素对模糊集合隶属程度的量称为隶属度,隶属度由隶属函数定义,取值区间为0,1。模糊集是表示和处理不确定数据的重要方法，它不仅能处理不完全数据、噪声或不精确数据，而且在开发数据的不确定模型方面能提供比传统方法更加灵巧和平滑的性能。l 支持向量机传统的学习方法是将对于训练集上的错误率最小化，该方法称为经验风险最小化（Empirical Risk Minimization ，ERM）。支持向量处理机则是基于源于统计训练理论的结构风险最小化（Structural Risk Minimization，SRM)原则。对于未知的测试数据，支持向量机有更好的泛化能力，它能通过降低训练数据的识别错误率之和来实现结构风险最小化这一目标。支持向量机可以用作基于一种新颖的统计学习方法的模式分类器，它通过扩大决策面和数据之间的空余量来降低总体错误率上限。目前支持向量机已经在许多模式识别领域得到成功应用，包括：人脸发现比较与识别、目标搜索与识别、手写数字和文字识别、语音识别、信息与图像恢复、性别判别与预测以及文本搜索和分类等等。l 粗糙集粗糙集理论的特点是不需要预先给定某些特征或属性的数量描述。如统计学中的概率分布、模糊集理论中的隶属度或隶属函数等,而是直接从给定问题的描述集合出发，通过不可分辨关系和不可分辨类确定给定问题的近似域。从而找出该问题中的内在规律。粗糙集理论的出发点是，根据目前已有的对给定问题的知识，将问题的论域进行划分，然后对划分后的每一个组成部分确定其对某一概念的支持程度：即肯定支持此概念、肯定不支持此概念和可能支持此概念。在粗糙集理论中，以上三种情况分别用三个近似集合来表示为正域、负域和边界。近年来，粗糙集理论和应用的研究取得了很快发展，其涉及的领域很广，包括模式识别、机器学习、决策分析和决策支持、知识获取、知识发现等。粗糙集理论同模糊集、神经网络、证据理论等其它理论一起，成为不确定性计算的一个重要分支。1.4.2 机器学习的方法常用的机器学习方法有： l 规则归纳规则反映数据项中某些属性或数据集中某些数据项之间的统计相关性，关联规则的一般形式为 ， 其可信度为C，支持度为S。l 决策树决策树学习是研究较为广泛的一种以实例为基础的归纳学习算法，它属于有监督的学习。在决策树生成阶段，对训练集中的实例采用自顶向下的方式，在内部结点进行属性值的比较并根据不同的属性值向下分支，在叶结点得到结论。通过对训练集学习而得到的决策树就是一个分类器。l 范例推理这种推理方法直接使用过去的经验或解法来求解给定的问题。范例常常是已经遇到并有解法的集体问题。当给定一个问题，就检索范例库，寻找相似的范例。如果找到相似的范例，那么它的解法就可以用来解新的问题。l 贝叶斯网络贝叶斯网络是用来表示变量之间连接概率的图形模型，它提供了一种表示因果信息的方法，长期以来一直被认为是人工智能领域中的一个重要的研究课题。贝叶斯网络综合考虑先验信息和样本数据，充分地利用专家知识和经验，可以进行定性分析和定量分析。将主观和客观有机地结合起来，避免了对数据的过度拟合，又避免了主观因素可能造成的偏见。由于这种方法的本文的研究重点，将在以后的章节作详细介绍。l 遗传算法遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。1.4.3 神经计算人工神经网络是近年来发展起来的模拟人脑生物过程的人工智能技术,它是由大量简单神经元广泛互连而形成的复杂非线性系统,具有自学习、自组织、自适应和很强的非线性映射能力，特别适合于因果关系复杂的非确定性推理、判断、识别和分类等问题。神经网络的工作机理是通过学习，改变神经元之间的连接强度。1.4.4 混合算法由于如前所述的那样，不存在某种算法或技术，在各种数据集上都能取得优良的预测、分类或解释效果，所以不少研究者都尝试了将两种或两种以上的知识发现方法结合使用。例如，将神经网络和贝叶斯网络结合形成的贝叶斯-神经网络，模糊集和粗糙集的结合等等。实验证明，在解决某些特定问题的时候，混合算法取得了比单一方法更好的性能。1.5论文组织本文的章节组织如下：第一章 介绍了知识发现的相关概念，如数据、信息和知识的定义和它们之间的联系；详细阐释了知识发现的定义。介绍了知识发现的步骤和功能，简要介绍了知识发现常用的方法和技术。第二章 介绍了贝叶斯学习理论与传统的概率推断的区别，贝叶斯网络的产生、发展和研究现状；给出了贝叶斯网络的定义，介绍了贝叶斯网络中的独立关系和因果关系以及它们对于贝叶斯网络的意义；介绍了贝叶斯网络的学习（包括结构和参数的学习），以及如何利用已经确定的贝叶斯网络进行推理。第三章 首先介绍了实验所采用的数据集的背景和领域知识，这些知识可用于后来的启发规则的制定；然后详细描述了实验过程中采用的十二个算法，还针对某些算法，给出了算例。最后介绍了实验程序的结构模块及各部分的功能。第四章 介绍了回归分析和多元线性回归分析，并将贝叶斯网络的结果和采用多元线性回归分析的结果作了比较。第五章 总结了本文所完成的主要工作，并提出下一步继续学习和研究贝叶斯网络及其它数据挖掘技术的展望。51第二章 贝叶斯网络2.1 贝叶斯学习理论概率推理既是概率学和逻辑学的研究对象，也是心理学的研究对象，但研究的角度是不同的。概率学和逻辑学研究的是客观概率推算的公式或规则；而心理学则研究人们主观概率估计的认知加工过程及其规律。贝叶斯推理的问题是条件概率推理问题，这一领域的探讨对揭示人们对概率信息的认知加工过程与规律、指导人们进行有效的学习、判断和决策都具有十分重要的理论意义和实践意义。贝叶斯学习是基于贝叶斯概率而形成的。贝叶斯概率与客观概率有重要区别，某一事件的贝叶斯概率是一个人相信该事件发生的程度（The Bayesian probability of an event x is a persons degree of belief in that event.）以抛掷硬币为例说明，正面（Head）向上的客观概率一般认为是1/2，但是它的贝叶斯概率就很可能不是1/2。比如某人先有关于这枚硬币的背景知识，知道它是从魔术商店买来的；或者是通过观察，他认为这枚硬币的质地、形状不均匀。在这些情况下，此人对抛掷该枚硬币正面朝上的贝叶斯概率都有可能不是1/2，而是其他的值，比如说是3/5。贝叶斯学派的起点是贝叶斯定理和贝叶斯假设。下面分别介绍：贝叶斯定理可用(2.1)式进行表示，它根据先验概率推导出了后验概率。 . (2.1)贝叶斯假设说的是，如果没有任何以往的知识来帮助确定 ，就可以采用均匀分布作为其分布，即参数在它的变化范围内，取到各个值的机会是相同的。贝叶斯学习的结果表示为随机变量的概率分布，它可以解释为我们对不同可能性的信任程度。2.2 贝叶斯网络的产生、发展和研究现状贝叶斯(Reverend Thomas Bayes, 1702-1761)学派奠基性的工作是贝叶斯的论文关于几率性问题求解的评论。或许是他自己感觉到他的学说还有不完善的地方，这一论文在他生前并没有发表，而是在他去世后，由他的朋友代为发表的。著名的数学家拉普拉斯(Laplace, P.S)用贝叶斯的方法导出了重要的“相继律”之后，贝叶斯的方法和理论逐渐被人理解和重视起来。1958年，英国最悠久的统计杂志Biometrika重新全文刊登了贝叶斯的论文，20世纪50年代，以罗宾斯(Robbins,H.)为代表，提出了经验贝叶斯方法和经典方法相结合，引起统计界的广泛关注。这一方法很快就显示出它的优点，成为一个很活跃的方向。在这里值得一提的是，八十年代以后，人工智能的发展，尤其是机器学习、数据挖掘的兴起，为贝叶斯理论的发展和应用提供了更为广阔的空间。贝叶斯网络是贝叶斯方法与图形理论的有机结合。1986年Pearl首次在专家系统中引进了贝叶斯网络。1988年Pearl明确指出影响图中没有决策节点和结果节点就是贝叶斯网，指出贝叶斯网络或许是概率推理中最普及的模型。1989年Andreassen使用贝叶斯网络建造了专家系统MLININ(Muscle and Nerve Inference Network)。1990年，Shafer指出贝叶斯网络目前已经成为公认的表示概率知识的系统。贝叶斯网络方法由于其理论上的严格性和一致性，以及有效的局部计算机制和直观的图形化知识表达，已经成为人工智能领域的研究热点。国际权威期刊Communications of the ACM 1995年发表了贝叶斯网络研究专辑，在Artifical Intelligence和machine leaning等重要杂志上有很多贝叶斯网络方面的文章；在UCAI, AAAI, ECAI, ACM, UAI等重要会议上贝叶斯网络研究也占到了相当大的比重。在我国，自2000年以来，CNKI收录的标题中包含“贝叶斯网络”的学术论文就有460余篇。2.3 贝叶斯网络的定义一个变量集X=x1,x2,xn 的贝叶斯网络由两部分组成:(1) 网络结构S，表达了X中各变量的条件依赖；(2) 与每个变量相关的局部概率分布P。这两个部分合在一起，定义了X的联合概率分布。用图形的形式表示出来，贝叶斯网络是一个有向无环图，其中节点与X的变量一一对应，两节点之间无弧相连表示条件独立。给定网络结构S，X的联合概率分布为.(2.2)Pai为xi的父亲节点集。用P表示局部概率（local probability）, 是乘积式中的各个项。这样做的好处有:由于在一个由多变量组成的贝叶斯网络中，变量间交互作用的关系是稀疏的，这种局部概率分布表能指数级的降低联合分布表的容量;存在许多适合于局部分布表的贝叶斯推理算法;贝叶斯网络中的定量表示与定性表示的分离有利于知识工程的建模。图2.1所示的就是一个贝叶斯网络。图2.1. 贝叶斯网络示例图贝叶斯网络不同于一般的基于知识的系统，它以强有力的数学工具处理不确定知识，以简单直观的方式解释它们。它也不同于一般的概率分析工具，它将图形表示和数值表示有机结合起来。由于贝叶斯网BN=由网络拓扑结构S和局部概率分布的集合P两部分组成，因此贝叶斯网的学习可以被分解成两个阶段：(1)网络拓扑结构即有向无环图的学习，简称结构学习；(2)网络中每个变量的局部条件概率分布的学习，简称为参数学习。2.4 贝叶斯网络中的独立关系和因果关系2.4.1 独立关系为使贝叶斯网作为知识模型可用，在学习过程中应当寻找一种最简单的网络结构。这种简单的结构模型称之为稀疏网络，它含有尽可能少的参数及依赖关系。稀疏网络的前提条件是变量间的独立关系。另外，虽然贝叶斯网作为联合概率分布的简化表示形式，可以计算变量空间的任意概率值。但当变量数目很大时，运用联合概率分布进行计算通常是不可行的，因为概率数目是变量数目的指数幂，计算量难以承受。贝叶斯网必须利用独立因果影响关系来解决这个难题。贝叶斯网中的三种独立关系分别是：条件独立、上下文独立及因果影响独立。三种独立关系旨在把联合概率分布分解成更小的因式，从而达到节省存储空间、简化知识获取和领域建模过程、降低推理过程中计算复杂性的目的。l 条件独立贝叶斯网的图形结构本身已经表达出条件独立关系，每个节点在已知其父亲节点的条件下独立于所有其余的非子孙节点。l 上下文独立为了说明上下文独立，我们先看如图2.2所示的贝叶斯网络。表2.1是图2.2中所示的贝叶斯网络的局部概率表。表中的星号表示的是“任何状态”，即不管Age 和Sex取何值，只要Fraud=yes, P(J|F,A,S)=0.05，这就是说，在Fraud=yes的“上下文”中，Jewelry的取值是独立于Age及Sex的。 表2.1. 图2.2中BN的局部概率表FraudAgeSexP(J|F,A,S)yes*0.05no30male0.000001no3050male0.0004由于这类独立性的存在，需要给出的条件概率数目大大减少，同时也就减少了计算工作量，而且使得训练出来的网络模型更具有好的性能。图2.2. 用于说明上下文独立的贝叶斯网络l 因果影响独立贝叶斯网中的有向弧是一种因果关系，表示父亲节点对儿子节点的直接影响，但是没有对儿子如何依赖父亲集作出约束，在最坏的情况下，需要给出的条件概率数目是父亲节点数目的指数幂。一些情况下，父亲节点(原因)之间相互合作，对儿了节点(结果)有一个共同的影响。但是，很多情况下，各个父亲独自对儿子起作用，父亲节点之间没有合作，我们说父亲节点对儿了节点的影响是因果独立的。定义2.1： 我们说节点X的各个父亲x1, .,xm对于X是因果影响独立的，如果对应于x1, .,xm，存在和X有相同取值范围的随机变量1, m，并且下面两个条件成立:(1)对于每个i, i仅仅在概率意义上依赖于xi，在xi条件下独立于所有其它的xj及j，(ji)，即，Independent(i，x1, .,xi-1, xi+1, .,xm, 1, i-1, i+1, m).(2)存在一个定义域是X的取值范围，且具有交换律和结合律的二元运算符*，使得X=1*2 *.*m 成立。*称作是X的基本结合运算符。我们把i称作是xi对X贡献。粗略地讲，有共同作用结果的多个原因是因果影响独立的，如果每个原因的各自贡献是独立的，所有原因对结果的影响是各自贡献的简单组合。因果影响独立大大降低每个节点所需的条件概率数目，从指数级降到线性级，当父亲节点很多时，降幅是十分巨大的。可以说，这个思想与简单贝叶斯方法是十分相似的。2.4.2 因果关系数据分析和决策都可以看成是广义的预测过程，而在预测过程中一般有两种任务：分类和因果关系的预测。有的分类器(如决策树)只能完成单一的分类任务，而贝叶斯网络在利用其表示联合概率分布来进行分类的同时，它本身的节点之间的弧就表示了变量之间可能存在的因果关系。由于学习的结果揭示了变量间的因果关系，因而相对于神经网络这一类的“黑盒”知识表示方式，贝叶斯网络的用户可理解性更强，更容易以直观的方式支持决策的制定。2.5贝叶斯网络的结构模型学习网络结构学习的目标是找到和样本数据D匹配度最好的贝叶斯网络结构，根据观察贝叶斯网络的视角不同，可以把学习贝叶斯网络结构的方法分成两类：基于评分的方法(Based on Scoring)和基于条件独立性的方法(Based on Conditional Independence)。基于评分的方法把贝叶斯网络看成是含有属性之间联合概率分布的结构，学习的目的是搜索与数据拟合最好的结构。一般的做法是给出评价网络结构的评分函数(如贝叶斯后验概率、最小描述长度和Kullback-Leiber熵等)，然后采用某种搜索策略来搜索最优的网络结构。第二种方法把贝叶斯网络看作是对变量间独立性关系进行编码了的结构。学习的目的是根据独立性关系(如卡方检验)对变量分组。由于本文采用的方法是第一种，所以只介绍第一种方法。2.5.1 评分函数定义2.2：对于给定的节点，它的各个父节点的取值的组合称为父节点的配置。 已知数据集D的条件下，贝叶斯网络的结构为S的条件概率（作为评分函数）为：p(Sh|D)=p(Sh )p(D|Sh)/p(D). (2.3)Sh 表示了“X的联合概率分布可以根据结构S来进行分解”这一假设，p(D)是一个规范化常数，不依赖于Sh，可不予考虑。p(Sh)的值可由用户指定，它表示某一贝叶斯网络的结构为S 的可能性。所以需要计算的只是p(D|Sh)。Cooper和Herskovits给出了p(D|Sh)的计算公式： . (2.4)式(2.4)中n是数据集中每条记录的变量个数，qi是第i个变量的父节点集的配置个数，N ijk和是D中第i个变量它的父节点集的配置为第 j个且该变量的取值为第k个值的记录（也叫实例）数，N ij为N ijk对k求和，ijk的含义在2.6节介绍。这是一种基于最大后验概率(Maximum A Posterior, MAP)的度量方法。2.5.2 搜索策略Chickering 等人于 1995提出要全面搜索找到评分函数值最高的网络模型是NP-hard的问题，1996年Chickering又进一步更加确切地证明了它是NP-Complete问题。这就意味着全面搜索是不可行的。因此研究人员采用了启发式搜索方法，包括贪心搜索、带重启的贪心搜索、最好优先搜索等方法，还有的采用了模拟煺火、遗传算法的智能计算方法进行搜索。结合实际，本文中的实验采用的搜索算法是带启发规则和随机重启的贪心算法。该算法利用领域知识制定一些启发规则，例如断言某些节点之间一定有弧相连，从而缩小搜索空间，然后运用随机重启机制克服贪心算法可能陷入局部最优的缺点。Chickering已经证实在同样的计算时间内，带随机重启的贪心算法能选择到比模拟煺火和最好优先方法更好的模型。带随机重启的贪心算法的基本思想是，选择一个合理的模型结构作为起点，利用评分函数得到一个初始的评分，然后进行弧的增删和反向等操作，选择一个评分增益为正数的模型替换原来的起点，迭代一直进行到在指定的次数内得不到增益为正数的模型，这样就完成了一轮搜索。然后随机选择一个合理的模型作为新的起点，进行下一轮的搜索，直到搜索轮数大于给定的值。详细的算法描述参见第三章。2.6贝叶斯网络的局部概率学习贝叶斯网络的局部概率学习，又称为贝叶斯网络的参数学习，实质上是在已知给定结构的条件下，来学习每个节点的概率分布表。早期的贝叶斯网的概率分布表是由专家的知识指定的，然而这种仅凭专家经验指定的方法，往往导致与观测数据产生较大的偏差。当前广泛采用的方法是从数据中学习这些参数，这种数据驱动的学习方法具有很高的适应性。根据数据的观测状况，可分为完备数据集和不完备数据集。完备数据集中的每个实例，都具有完整的观测数据，不完备数据集是指对某个实例的观测有部分值缺失或观测异常的情况。本文只讨论完备数据集的情形。贝叶斯方法学习网络局部概率应该由两部分组成：观测前的先验知识和观测到的数据。在贝叶斯参数学习中，先验知识包括局部概率的先验分布的选取和分布参数的选取。学习的任务就是找到一定的算法把二者有机结合起来。2.6.1先验分布的选取Raiffa和Schaifeer提出先验分布应选取共轭分布，即要求后验分布与先验分布属于同一分布类型。它的一般描述为: 定义2.3：设样本X1,X2, . ,Xn对参数的条件分布为p( x1,x2, . ,xn |)，如果先验分布密度函数()决定的后验密度(|x)与()同属于一种类型，则称()为p(x|)的共扼分布。定义2.4：设P= p(x|): 是以为参数的密度函数族，H= ()是的先验分布族，假设对任何pP和H,得到的后验分布(|x)仍然在H族中，则称H为P的共轭分布族。指数函数族包括一项分布、多项分布、正态分布、Gamma分布、Poisson分布和多变量正态分布等都是共轭分布。常用的共轭分布还有Dirichlet分布。本文采用的就是Dirichlet分布。用共轭分布作先验可以将历史上做过的各次试验进行合理综合，也可以为今后的试验结果分析提供一个了合理的前提。非共扼分布的计算实际上是相当困难的，而共轭分布计算后验只需要利用先验做乘法，其计算特别简单。可以说，共轭分布族为贝叶斯学习的实际使用铺平了道路。2.6.2 局部概率学习的步骤定义2.5：对参数而言，统计量t(x1,x2,xn)是充分的，如果不论的先验分布是什么，相应的后验分布h(| x1,x2,xn) 总是和t(x1,x2,xn)的函数，这样的 统计量称为充分统计量。一般说来，任何一个统计量都有压缩数据的功能。而充分统计量既压缩数据，又不损失相关参数的信息。 上面各式中i、j、k的意义如前所述，ri表示第i个节点的取值个数。举例说明qi的计算，例：如果以下三条假设满足：一、D是完备的数据集；二、参数独立，也就是说ij是相互独立的，式子三、数据集来自随机样本。则可以根据局部分布函数快捷地计算出后验分布P(s | D, Sh) 。步骤如下：第二步，估计先验参数ijk，其计算方法如下： 第三步，根据Dirichlet分布的性质，后验概率可如下计算：2.7 贝叶斯网络推理在完成了贝叶斯网络的模型和参数学习之后，就得到了一个完整的贝叶斯网络。利用这个贝叶斯网络，我们可以进行分类或预测。以图2.2中给出的贝叶斯网络为例，说明如何利用贝叶斯网络进行推理。首先，利用有向无环图的拓扑排序选择一个适当的变量顺序，为将来运用概率乘法公式做准备。在图2.2中，应当选择