贝叶斯网络结构学习及MBNC实验平台的构建

摘要

随着信息技术的发展,数据挖掘技术广泛应用于实际运用中,贝叶斯网络作为一种有效的知识表示方式和概率推理模型,是处理不确定性的强有力图形决策化分析工具。现实世界中存在着海量数据,如何处理这些数据,并从中发现有用的知识具有现实意义。贝叶斯网络是一个带有概率注释的有向无环图,由网络的拓扑结构和局部概率分布两部分组成。本文先简要阐述了贝叶斯网络有三大理论问题:贝叶斯网络的表示,学习和推理。近年来,基于贝叶斯网络的数据挖掘在一些数据建模问题中取得了较好的效果。用于分类的贝叶斯网络叫做贝叶斯分类器。贝叶斯分类器是特殊形式的贝叶斯网络,变量的选取和状态数均已确定,属性结点已知,类结点未知。贝叶斯分类器家族有三类常见的分类器:朴素贝叶斯分类器NBC,树扩展朴素贝叶斯分类器TANC和贝叶斯网络分类器BNC。贝叶斯分类器的学习包括结构学习和参数学习,参数学习相对简单一些。建构贝叶斯分类器是本文要解决的问题。现在比较常用的主要有Java Bayes软件包,Hugin Expert,Power Constructor,MSBNx,Netica等。这几种软件包作者均已下载研究使用,其中Hugin Expert等是限制版本,只相当于一个应用程序,而Power Constructor,MSBNx,Netica等均不提供源代码,无法在其之上完成新算法实现。基于Java语言的Java Bayes软件包提供了源代码,WEKA系统和JBNC系统是用Java语言开发的,但用Java语言编程的工作量很大,调试程序比较困难,系统的可扩展性较差。尤其是涉及到的数理统计方面的程序,已有的源代码的可读性较差,对所定义的多维数组操作繁琐易错。生成的结构需要调用第三方软件才能显示。其他下载的贝叶斯网络学习软件包也有同样的问题。基于Matlab语言的BN Toolkit(BNT)软件包可以很好的解决上述问题。Matlab语言是专门进行数值计算的高级语言,编程量较之Java语言等明显少的多,调试程序也很方便,显示所学习得到的结构也很方便。BNT的缺点是没用图形用户界面GUI。最终用BNT提供的基本函数,用Matlab语言开发了MBNC实验平台。先在MBNC实验平台上简单实现了几种贝叶斯分类器。有NBC,基于互信息测度的TANC以及基于K2算法和GS算法的BNC。所建构的这些分类器的准确性评估好于文献数据,实验数据表明:用在数理统计上天然的优越性的Matlab语言建构的分类器性能是非常好。MBNC试验平台的可扩展性也很好,进一步进行新的研究比较方便。完全的贝叶斯网络的结构学习是一个NP难问题,很多学者提出了近似算法,取得了较好的效果。本文对贝叶斯分类器结构学习进行改进,NBC不需要学习结构,我们的工作是TANC和BNC结构学习算法的改进,新算法在MBNC实验平台上进行了验证。衡量算法优劣的标准是所构建的贝叶斯分类器的准确性评估。用从UCI上下载的标准数据集进行评估。对TANC结构学习的改进是引入了新的测度函数贝叶斯信息标准BIC测度,原有的互信息MI测度是相关性测试的标准,BIC测度用于基于打分和搜索的结构学习取得了成功。用BIC测度学习结点对之间的关系,再建构最大权重跨度树,从而学习得到TANC结构。我们实现了TANC-BIC和TANC-CBIC两种分类器,实验结果表明:新的算法与基于MI测度的TANC-MI和TANC-CMI分类器分类效果相当,在某些数据集中还更优些。对于BNC结构学习,K2算法中结点次序的确定是一个NP难问题,而GS算法的时间开销很长。本文提出了基于启发式的G2算法,即用启发式思想来学习结点的次序,再用K2算法的得出网络结构。用NB结构和四种TAN结构作为启发式信息,实现了五种分类器模型,分别是G2-NB,G2-MI,G2-CMI,G2-BIC,G2-CBIC。同样也在MBNC下编程实现了这些算法。实验结果表明:学习得到的结点次序是比较优化的,分类效果比较好。该算法较好地解决了K2算法的瓶颈问题。不需要用户确定结点次序,限制可行解的搜索空间,从而加速了问题的求解过程,所添加的弧比较简洁,网络结构更加合理。对GS算法的优化正在研究之中。MBNC实验平台可以用来进行文本分类,我们研究文本分类中的特征选择和准确性评估方法两类问题,提出了稳定性评估标准,在MBNC上初步实现文本分类功能。基于MBNC实验平台也可做其他方面的算法研究,比如,缺失数据下的参数学习(如利用“相容的贝叶斯学习及其先验无关性”理论有效解决不完整数据),研究全局最优的结构学习算法(如利用遗传算法或模拟退火算法等),研究数据集的质量(如噪音数据的识别和清洗),对分类器进行增强(如用Bagging算法、Boosting算法或投票机制)等问题。

目录

中文摘要

Abstract

前言

第一章 绪论

第一节 研究背景

第二节 研究现状

第三节 本文的主要工作

第二章 贝叶斯网络的概述

第一节 图模型及其定义

第二节 贝叶斯方法的基本观点

第三节 贝叶斯网络举例

第四节 贝叶斯网络学习的成功应用

第三章 贝叶斯网络的学习

第一节 贝叶斯网络结构学习

第二节 贝叶斯网络参数学习

第三节 贝叶斯网络推理算法

第四章 MBNC实验平台的构建

第一节 贝叶斯分类器

第二节 贝叶斯软件包简介

第三节 MBNC实验平台的结构功能

第四节 用MBNC实现贝叶斯分类器

第五节 实验结果分析

第五章 基于BIC测度的TANC结构学习算法

第一节 BIC测度介绍

第二节 基于BIC测度的TANC结构学习算法

第三节 实验结果分析

第六章 BNC结构学习:基于启发式的G2算法

第一节 学习贝叶斯网络结构的K2算法

第二节 基于启发式的G2算法

第三节 实验结果分析

第七章 进一步要做的工作

结束语

读研期间已发表和已投稿的论文

后记致谢

参考文献