第6卷第1期 智能系统学报 Vol.6 No.1 2011年2月 CAAI Transactions on Intelligent Systems Feb.2011 doi:10.3969/i.issn.1673-4785.2011.01.009 利用互信息学习贝叶斯网络结构 李冰寒，高晓利，刘三阳，李战国2 (1.西安电子科技大学数学系，陕西西安710071；2.西安交通大学机械工程学院，陕西西安710049) 摘要：由数据构造贝叶斯网络结构是P-难问题，因此提出了一种基于互信息的改进算法.该算法根据互信息构造 初始框架，其次利用最大支撑树算法精简初始框架，并通过条件独立测试添加方向，最后利用贪婪算法得到最优网 络结构.数值实验表明，改进算法无论是在C的得分值，还是在结构的误差上都有一定的改善，并且在迭代次数、 运行时间上均有明显降低，能较快地确定出与数据匹配程度最高的网络结构。 关键词：贝叶斯网络；结构学习；互信息；独立测试：最大支撑树 中图分类号：TP181文献标识码：A文章编号：16734785(2011)01006805 Learning Bayesian network structures based on mutual information LI Binghan',GAO Xiaoli',LIU Sanyang',LI Zhanguo2 (1.Department of Mathematics,Xidian University,Xi'an 710071,China;2.Department of Mechanical Engineering,Xi'an Jiaotong University,Xi'an 710049,China) Abstract:Constructing Bayesian network structures from data is an NP-hard problem,and an improved algorithm was proposed based on mutual information.This algorithm built the initial skeleton using mutual information,re- fined the initial skeleton by employing the maximum spanning tree algorithm,and then oriented edges according to conditional independence tests.Finally,the optimal network structure was obtained using a greedy search.Numeri- cal experiments show that both the BIC score and structural error made some improvements from previous results, and the number of iterations and running time was greatly reduced.Therefore the structure with highest degree of data matching was shown to be relatively faster as determined by the improved algorithm. Keywords:Bayesian network;structure learning;mutual information;independence test;maximum spanning tree 贝叶斯网络是表示随机变量间依赖和独立关系中结构学习主要有2种方法：一是基于依赖性测试的 的网络模型，也称为贝叶斯网、因果概率网络或信念 方法？9]，它是在给定数据下评估变量之间的条件独 网络.它由节点集、有向边集和条件概率分布集组 立性关系，构建网络结构；二是基于得分搜索的方 成，其中节点表示随机变量，是对过程、事件、状态等 法9]，其原理是在所有节点的结构空间内按照一定 实体的某些特征的描述，有向边表示变量间的概率 的搜索策略及得分准则构建贝叶斯网络结构。 依赖关系.贝叶斯网络可对现实世界的各种状态或 利用互信息、最大支撑树算法和条件独立测试， 变量进行分析，生活中的许多实例如医疗诊断山、 本文提出了一种构建最优网络结构的改进算法.通 设备故障诊断2]、故障预测3]等都可以用贝叶斯网 过数值实验表明，与文献[15]中提到的贪婪算法相 络进行建模.并且由于图形表示的直观性和易理解 比，改进算法能较快地确定出与数据匹配最好的网 性，贝叶斯网络已逐渐成为在不确定情况下进行推 络结构 理和决策的一种很受欢迎的问题表示结构[46] 学习贝叶斯网络可分为结构学习和参数学习，其 1贝叶斯网络 定义1贝叶斯网络[16N。=(G,0),其中G= 收稿日期：2010-07-13， (V,E)是一个非循环有向图，简称为DAG(directed 基金项目：国家自然科学基金资助项目(60974082). 通信作者：李冰寒.E-mail:binghan2020@126.com. acyclic graph),0是一个条件概率分布集，0：∈0表