智能系统：利用互信息学习贝叶斯网络结构

第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表

第1期 李冰寒，等：利用互信息学习贝叶斯网络结构 69… 示在给定节点X:的父节点时X:的条件概率，节点 j=1,2,…,n; 集V的联合概率分布可由式(1)表示. 2)计算I(X:;X),i≠j,ij=1,2,…,n; P(X1=a1,X2=2,…,X.=an)= 3)对HX:,X∈V,i≠j,若I(X;X)<e,其中e ΠP(X:=a1m:=F). 为阈值(0<e<1),则令E1=E,1{X-X. (1) iI 应注意的是，阈值e的取值与G,中无向边的个 式中：π：表示节点X:在G中的父节点集 数有关.如果ε过大（接近于1），则很大可能会删除 定义2DAGG的V结构是指由3个节点构成 真实网络中实际存在的边；如果ε过小，则G,中可 的有序节点组(X,Y,Z),满足下面2个条件： 能包含较多不存在于真实网络的冗余边.在贝叶斯 1)G包含有向边X+Y和Z+Y: 树络的结构学习中，通常取￡的值为0.01，因为这 2)在G中X和Z不相邻. 样能保证真实网络中的大部分边存在于G中，而且 定义3随机变量X和Y的互信息定义如 G,中含有较少的冗余边. 下： 2.2确定G1的最大支撑树G I(X;Y)=H(X)-H(XI Y) 本阶段将图中每条边上的权定义为节点间的互 式中：H(X)和H()分别是X和Y的信息熵，H(XI 信息，然后利用Pim算法构造无向图G1=(V,E,) Y)是在给定Y下X的条件信息熵.H(X)、H(XIY) 的最大支撑树.由于第1阶段构造的初始无向图 定义如下： G=(V,E,)可能包含多于三节点的环，而这些环的 H(X)=- ∑P(X)log(P(X)), 存在将会导致当前无向图不可一致延拓；但是在等 价类空间上进行贪婪搜索的输入图应该是一个可一 H(XI)=-∑∑P(X=x,Y=)· 致延拓的本质图，故第2阶段通过构造最大支撑树 log(P(X x:I Y=y:)). 来精简初始无向图，使得精简后的无向图G2=（V, 式中：n和m分别表示X和Y的状态个数.X和Y之 E2)可一致延拓. 间的互信息是对称的，即I(X;Y)=I(Y;X), 对于无向图G1=(V,E),设它的权矩阵为W= (0),S为V的一个非空子集，5=八S,定义： 2构造贝叶斯网络的改进算法 rI(X;X),若X-X∈E; 算法的思想是从完全无向图开始，第1阶段删 =0, 其他 除互信息小于给定阈值ε节点间的边，构造初始无 [S,]={X:-X∈E1IX:∈S,XeS1. 向图G,;第2阶段利用图论中的Pim算法寻找G 构造G最大支撑树的具体步骤如下： 的最大支撑树G2,精简初始无向图G;第3阶段根 1)任取X:∈V,令S={X},Eo=0,k=0. 据条件独立测试对G2中的无向边添加方向，得到部 2)若Sk=V,结束，以S为顶点集、E为边集的 分有向图G3;第4阶段对G3中剩余的无向边任意 图即是G的最大支撑树；否则转3)· 添加方向，构造可能的非循环有向图G4;第5阶段 3)构造[Sk,S],若[S,S]=,则G1不连通， 从G4开始，利用贪婪算法]在等价类空间上进行 算法停止：否则，设w(e,)=,w(e),e4=X- 搜索，得到和数据匹配最好的贝叶斯网络结构的本 Xk,X∈Sk,令S+1=SU{Xk},E+1=EkU{ez}, 质图G·,具体算法可分为以下5个阶段 k=k+1,转1). 2.1构造初始无向图G 2.3确定最大支撑树G2中边的方向得到G 由于随机变量X和Y之间的互信息度量了在 根据条件独立测试可以确定出形如X-Z一Y和 已知Y的新观察值时对X取值的不确定性的减少， X→Y-Z的子结构中无向边的方向.具体算法如下： 反之亦然，从而随机变量间的依赖程度可通过评价 1)令G3=G2 它们之间的互信息值来衡量.如果两节点X:、X之 2)确定G3中所有的子结构X-Z-Y,其中X 间的互信息小于某个临界值，即I(X:;X)<B,则在 和Y不相邻. 真实网络中这两节点极大可能不相邻，因为反映它 3)对于每个子结构X-Z-Y,若P(XIZ)≠ 们之间依赖程度的互信息值小于阈值ε，从而它们 P(XIY,Z)且对于添加边X-Y后的三角环X-Z- 之间不存在边.具体算法如下： Y-X,令S=☑.对每个节点W∈八{X,Y,Z},计算 1)令V={X1,X2,…,Xn},E1={X-Xli≠j,i, W与其他各节点（不包含Z)的互信息并降序排列

·70 智能系统学报 第6卷 设前3个与W的互信息最大的节点集为Tm,若X∈ 点间的互信息很小，在第1阶段就已经被忽略掉了， Tw且Y∈Tm,则S=SU{W}.若S=☑，则令E3= 从而后续阶段的计算复杂度相对来说比较小. E\X-Z,Y-Z UX-Z,YZ. 4数值实验 4)确定G中所有的子结构X→Y-Z. 5)对于每个子结构X+Y-Z,若等式 下面以Alam网络为例测试改进算法的性能， P(ZIY)=P(ZIY,X)成立，则令E4=E41{Y-Z}U 其中Alam网络如图1所示，其本质图如图2所示， {Y+Z};否则，对添加无向边X-Z后的子框架X- 并将测试结果与原始贪婪算法5进行比较。 Y-Z-X,令S=☑.对每个节点W∈八{X,Y,Z}, ⑧① 计算W与其他各节点（不包含Y)的互信息并降序 ①⑤ 6 排列，设前3个与W的互信息最大的节点集为Tm, 5 若XeTm且Z∈Tm,则令S=SU{W}.若=O,则 令E3=E3U{Z→X{. 3 2.4确定非循环有向图Ga 9-⑨ 30 由于第3阶段产生的图是非循环部分有向图， -29 10 因此需要对尚未确定方向的无向边添加方向.具体 算法为：对G中尚未确定方向的无向边添加任意方 图1 Alarm网络 向使之变为非循环有向图G4, Fig.1 Alarm network 2.5优化DAGG4确定最优网络结构的本质图G 由于第4阶段得到的G4可能含有或缺少真实 网络中的边，因此需要优化非循环有向图G4·具体 ①⑤ 算法如下： ⑤①-6①0 1)利用Find-Compelled算法i8确定G4的本质 4 图G4; 2)从G4开始，在等价类空间上进行贪婪搜索， 36 28 -9 得到最优结构的本质图G· 10 3复杂度分析 图2 Alarm网络的本质图 Fig.2 Essential graph of Alarm network 设n和m分别为节点个数和样本数，在第1阶 利用Matlal随机抽取4000、6000、8000和10000 段中需要计算n(n-1)/2次互信息，而计算每个互 个样本作为实验数据，其中统计参数如下所示： 信息的复杂度为0(m),故第1阶段的复杂度为 1)Sc:最优结构的BIC得分； 0(mn2);Pim算法的复杂度为0(n2),从而第2阶 2)Cs:与真实网络结构的本质图相比，算法确 段的复杂度为0(n2);在第3阶段中确定形如 定出的真实边的个数； X-Z-Y和X→Y-Z的子结构的复杂度为O(n3), 3)Ms:与真实网络结构的本质图相比，算法未 而最多有n个这样的子结构，对每个子结构进行条 确定出的边的个数； 件独立测试的复杂度为O(m),从而第3阶段的复 4)Ws:与真实网络结构的本质图相比，算法确 杂度为0(mn)+0(n3);第4阶段的复杂度为 定出的不具有方向或具有相反方向的边的个数； O(IE);算法Find-Compelled的复杂度为O(n), 5)Ws:与真实网络结构的本质图相比，算法确 故第5阶段的复杂度为O(n2),由此可知，整个算法 定出的冗余边的个数； 的复杂度为O(mn2)+0(n3),也就是说，改进算法 6)GEs MEs +Wos +Wcs; 的复杂度在最坏情况下是节点个数的多项式函数和 7)N1:算法迭代次数. 样本个数的线性函数.由于在实际生活中算法搜索 表1给出了原始贪婪算法和本文提出的改进算 时遇到的网络结构都是相当稀疏的，即使网络节点 法在不同样本容量数据集合上的实验结果.由实验 数很大，由于网络本身很稀疏，即具有较少的有向 结果可以看出：与原始贪婪算法相比，改进算法确定 边，从而参与计算的节点很少，那些没有边相连的节 的最优结构具有相对较少的缺失边和冗余边，迭代

第1期 李冰寒，等：利用互信息学习贝叶斯网络结构 ·71 次数明显减少，从而收敛速度更快，而且最优结构具 更好的求解质量，并且算法的计算复杂度得到了明 有较高的BIC得分.由此可知，改进算法能够获得 显的改进 表1不同容量下2种算法的实验结果 Table 1 Experimental results of the two algorithms on different sample capacities 样本容量 算法 Sc/10' C西 Wos Wcs N 改进算法 -4.4715 31 12 3 4 19 1 4000 贪婪算法 -5.9053 31 12 3 4 19 12 改进算法 -6.4895 32 10 3 16 1 6000 贪婪算法 -8.8311 12 19 12 改进算法 -8.5825 32 10 3 6 1 8000 贪婪算法 -11.7370 31 12 3 19 12 改进算法 -10.7290 32 10 3 3 16 1 10000 贪婪算法 -14.7050 31 12 3 4 19 12 5结束语 background knowledge[C]//Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence.San 树是极为简单又极为重要的一类图，而最大支 Francisco,USA:Morgan Kaufmann,1995:403-410. 撑树是图论中的一类非常简单的网络最优化问题. [7]BROMBERG F,MARGARITIS D,HONAVAR V.Efficient Markov network structure discovery using independence tests 结合支撑树的性质，本文提出了一个新的构想：将网 [J].Joural of Artificial Intelligence Research,2009,35 络结构中边上的权定义为节点间的互信息，从而有 (1):449485. 效地将图论和互信息知识结合起来.改进算法与原 [8]MILAN S,JIRI V.A reconstruction algorithm for the essen- 始贪婪算法相比具有更好的求解质量，并且收敛速 tial graph[J].Intemational Journal of Approximate Reason 度有明显改进，对于提高大多数智能算法如蚁群算 ing,2009,50:385-413. 法、免疫算法的收敛速度有很大帮助，因为改进算法 [9]冀俊忠，张鸿勋，胡仁兵，等.一种基于独立性测试和蚁 可用于对这些智能算法进行局部优化，并且对在等 群优化的贝叶斯网学习算法[J].自动化学报，2009,35 价类空间上搜索最优贝叶斯网络结构具有重要的研 (3):281-288. 究意义， JI Junzhong,ZHANG Hongxun,HU Renbing,et al.A Bayesian network learning algorithm based on independence 参考文献： test and ant colony optimization[J].Acta Automatica Sini- ca,2009,35(3):281-288. [1]HANSEN JF.The clinical diagnosis of ischaemic heart dis- [10]PEDRO C P,ANDEAS N,MATHAUS D,et al.Using a ease due to coronary artery disease[J].Danish Medical local discovery ant algorithm for Bayesian network structure Bulletin,1980,27:280-286. learning[J].Transactions on Evolutionary Computation, [2]WOLBRECHT E.AMBROSIO B D.PASSCH B.et al. 2009,13(4):767-779. Monitoring and diagnosis of a multi-stage manufacturing [11 CHEN Xuewen,GOPALAKRISHNA A,LIN Xiaotong. process using Bayesian networks[J].Artificial Intelligence Improving Bayesian network structure learning with mutual for Engineering Design,Analysis Manufacturing,2000, information-based node ordering in the k2 algorithm[J]. 14(1):5367. IEEE Transactions on Knowledge and Data Engineering, [3]BEISER J A,RIGDON S E.Bayes prediction for the num- 2008,20:1-13. ber of failures of a repairable system[J].IEEE Transactions [12]LEVINE J,DUCATELLE F.Ant colony optimization and on Reliability,1997,46(2):320-326, local search for bin packing and cutting stock problems [4]PEARL J.Graphical models for probabilistic and causal rea- [J].Joumal of the Operational Research Society,2004, soning[M]//TUCKER A B.The computer science and en- 55(7):705-716. gineering handbook.Boca Raton,USA:CRC Press,1997: [13]LOBONA B,AFIF M,FAIEZ G,et al.Imporving algo- 697-714. rithms for structure leaming in Bayesian networks using a [5]SCHACHTER R D.Probabilistic inference and influence di- new implicit score J].Expert System with Applixation, agrams[J].Operations Research,1988,36(4):589-605. 2010,37:5470-5475. [6]MEEK C.Causal inference and causal explanation with [14]TSAMARDINOS I,BROWN L E,ALIFERIS C F.The

72· 智能系统学报 第6卷 max-min hill-climbing Bayesian network structure learning 高晓利，女，1983年生，硕士研究 algorithm[J].Machine Learming,2006,65(1)::31-78. 生，主要研究方向为数据挖掘、贝叶斯 [15]CHICKERING D M.Learning equivalence classes of 网络、最优化理论，发表学术论文3篇· Bayesian network structures [J]..Jourmal of Machine Learning Research,2002(2)):445-498. [16]]RICHARD E N.Learning Bayesian networks[M]..Chica- go,USA::Prentie Hall,2002::40-43. [17]PROAKIS J.Digital communications M].Columbus, 刘三阳，男，1959年生，教授、博士 USA:MeGraw-Hill,2000::6 190. 生导师、博士，国家级教学名师，曾在法 [18].CHICKERING D M.A transformational characterization ofe- 国作博士后研究，西安电子科技大学理 quivalent Bayesian network structures[C]//Proceedings of the 学院院长兼数学系主任、工业与应用数 Eleventh Conference on Uncertainty in Arificial Intelligence.. 学研究所所长.主要研究方向为应用数 San Francisco,USA:Morgan Kaufmann,1995::87-98. 作者简介： 学、最优化和运筹学.先后主持10余项 科研项目，获得多次省部级科技进步奖，国家级优秀教学成 李冰寒，女，1986年生，硕士研究 果二等奖2次，陕西省优秀教学成果特等奖、一等奖和二 生，主要研究方向为数据挖掘、贝叶斯 等奖多次.发表学术论文300余篇，其中被SCI检索50余篇 网络、最优化理论，发表学术论文5篇· ,EI检索80余篇，出版专著6部， 第9届中国智能机器人学术研讨会征文通知 由中国人工智能学会智能机器人专业委员会主办、北京大学深圳研究生院承办的第9届中国智能机器人学术研讨 会将于2011年11月11-13日在深圳举行，会议将组织赴香港和澳门的学术交流与参观活动，大会组委会热忱欢迎从事 智能控制与智能机器人研究与应用的教师、学者、科技工作者和学生参加本次大会.现将大会征文范围和有关日期通知 如下 1.征文范围（但不限于） ·机器人理论与控制技术 ·机器视觉、图像处理与模式识别技术 ·人工智能与智能控制技术 ·机器人同时定位与地图创建(SLAM) ·智能机器人体系结构及实现方法 机器人结构设计及计算机仿真技术 机器学习、算法与知识工程 ·嵌入式计算机技术 基于网络的机器人结构与控制 ·无线通信网络技术 ·机器人传感技术、智能传感器 服务机器人、特种机器人 ·多智能体系统理论与应用 足球机器人、仿生（人），机器人 多传感器集成与信息融合 ·信息获取与数据挖掘 ·移动机器人及自主导航技术 ·智能机器人的应用 2.重要日期 投稿截止日期：：2011年4月30日：录用通知日期：2011年5月31日：修改定稿日期：2011年6月15日， 3.稿件要求 论文必须未公开发表过，每篇论文的篇幅（含图、表）)一般不超过6000字.录用论文在《华中科技大学学报（自然科 学椒)》增刊，刊登.论文包括：题目、作者姓名、作者单位信息、中英文摘要、关键词、正文、参考文献、作者简介和-阳l 地址.稿件要求附后或访问《华中科技大学学报》主页：htp:/xb.hust.edu.cn上的"投稿须知“栏目. 4.投稿方式 投稿方式：稿件用word电子文档发送到：1iwei0828@mail.hust.edu.cn李炜副教授； 联系电话：027-87556242（办）、18971142368（移动）： 投稿时请在稿件末尾的作者简介中注明作者的电话，以便联系

高晓利,女,1983年生,硕士研究 生,主要研究方向为数据挖掘、贝叶斯 网络、最优化理论,发表学术论文3篇 投稿方式: 稿件用word电子文档发送到: liwei0828@mail.hust.edu.cn李炜副教授; 联系电话: 027-87556242(办) 、18971142368(移动) ; 投稿时请在稿件末尾的作者简介中注明作者的电话,以便联系. 第6卷 第9届中国智能机器人学术研讨会征文通知 1.征文范围(但不限于) 由中国人工智能学会智能机器人专业委员会主办、北京大学深圳研究生院承办的第9届中国智能机器人学术研讨 会将于2011年11月11-13日在深圳举行,会议将组织赴香港和澳门的学术交流与参观活动,大会组委会热忱欢迎从事 智能控制与智能机器人研究与应用的教师、学者、科技工作者和学生参加本次大会.现将大会征文范围和有关日期通知 如下. ·机器视觉、图像处理与模式识别技术 ·机器人同时定位与地图创建(SLAM) 机器人结构设计及计算机仿真技术 ·嵌入式计算机技术 ·无线通信网络技术 服务机器人、特种机器人 足球机器人、仿生(人) 机器人 ·信息获取与数据挖掘 ·智能机器人的应用 论文必须未公开发表过,每篇论文的篇幅(含图、表) 一般不超过6000字.录用论文在《华中科技大学学报(自然科 学版) 》(增刊) 刊登.论文包括: 题目、作者姓名、作者单位信息、中英文摘要、关键词、正文、参考文献、作者简介和E-mail 地址.稿件要求附后或访问《华中科技大学学报》主页: htp: //xb.hust.edu.cn上的"投稿须知"栏目. [17] PROAKIS J. Digital communications [ M]. Columbus, USA: McGraw-Hill,2000: 6190 作者简介: ·机器人理论与控制技术 李冰寒,女,1986年生,硕士研究 生,主要研究方向为数据挖掘、贝叶斯 网络、最优化理论,发表学术论文5篇 [16] RICHARD E N. Learning Bayesian networks[ M] .Chica￾go,USA: Prentie Hall,2002: 40-43. ·人工智能与智能控制技术 ·智能机器人体系结构及实现方法 机器学习、算法与知识工程 基于网络的机器人结构与控制 ·机器人传感技术、智能传感器 ·多智能体系统理论与应用 多传感器集成与信息融合 ·移动机器人及自主导航技术 [18] CHICKERING D M. A transformational characterization of e￾quivalent Bayesian network structures[C]//Proceedings of the Eleventh Conference on Uncertainty in Arificial Intelligence. San Francisco,USA: Morgan Kaufmann,1995: 87-98. 4.投稿方式 刘三阳,男,1959年生,教授、博士 生导师、博士,国家级教学名师,曾在法 国作博士后研究,西安电子科技大学理 智 能 系 统 学 学院院长兼数学系主任、工业与应用数 学研究所所长.主要研究方向为应用数 学、最优化和运筹学.先后主持10余项 科研项目,获得多次省部级科技进步奖,国家级优秀教学成 果二等奖2次,陕西省优秀教学成果特等奖、一等奖和二 等奖多次.发表学术论文300余篇,其中被SCI检索50余篇 ,EI检索80余篇,出版专著6部. 报 2.重要日期 max-min hill-climbing Bayesian network structure learning algorithm[J] . Machine Learming,2006,65(1) : 31-78. [15] CHICKERING D M. Learning equivalence classes of Bayesian network structures [J] . Jourmal of Machine Learning Research,2002(2) :445-498. 72· 投稿截止日期: 2011年4月30日;录用通知日期: 2011年5月31日;修改定稿日期: 2011年6月15日. 3.稿件要求