基于混合方式的贝叶斯网弧定向算法  

A Hybrid Method for Orienting Edges of Bayesian Network

作　　者：贾海洋[1] 陈娟[1] 朱允刚[1] 刘大有[1] 

机构地区：[1]吉林大学计算机科学与技术学院,吉林大学符号计算与知识工程教育部重点实验室,吉林长春130012

出　　处：《电子学报》2009年第8期1842-1847,共6页Acta Electronica Sinica

基　　金：国家自然科学基金重大项目(No.60496321);国家自然科学基金(No.60373098;No.60573073;No.60603030;No.60503016);国家863高技术研究发展计划(No.2006AA10Z245);吉林省科技发展计划重大项目(No.20020303);吉林省科技发展计划(No.20030523);欧盟项目TH/Asia Link/010(No.111084)

摘　　要：贝叶斯网是不确定知识表示及推理的主要方法之一,BNs结构中的因果关系在知识建模中起到十分关键的作用,因此确定BNs中弧的方向是一重要问题.目前已有的方法存在以下问题:(1)算法计算复杂性高;(2)将统计不可分的弧定向,可能与领域知识不符.本文提出一种结合条件独立测试和打分搜索的BNs弧定向方法.该方法仅执行零阶和一阶条件独立测试,执行次数为多项式级;打分搜索可分解为局部子图的搜索,提高了算法的效率.算法输出结果为最大链图,该图仅对统计可分的弧进行定向,对统计不可分的弧保留无向的特性.这种结果更准确的表现了数据中蕴含的因果关系,便于结合领域知识进行建模.Bayesian network is one of the most important methods for representing and inferring with uncertainty knowledge, causal relation between variables is a key property for modeling the knowledge, so it is an important problem to orient the edges. There are some problems in the exist methods： （ 1 ） the computational complexity of the algorithms is high; （2） orienting the statistical indistinguishable edges may inconsistent with the domain knowledge. This paper presents an algorithm which combining the con- straint approach and score search approach to orient the edges. The time of zero order and first order conditional independent test is polynomial; The search space can be decomposed to sub graph, which improving the efficiency of the algorithm. The output of the algorithm is largest chain graph, which just orienting the statistical distinguishable edges, keep the indistinguishable edges undirected. This graph present the causal relation more accuracy, and more convenient for combining domain knowledge.

关 键 词：贝叶斯网 弧定向 马尔科夫等价类 链图 

分 类 号：TP11[自动化与计算机技术—控制理论与控制工程]