基于全条件独立的贝叶斯网络MPD-JT构造算法  

Construction algorithm of MPD-JT for Bayesian networks based on full conditional independence

作　　者：朱明敏[1] 刘蔚[1] 杨有龙[1] 

机构地区：[1]西安电子科技大学数学系,陕西西安710071

出　　处：《系统工程与电子技术》2010年第6期1325-1328,共4页Systems Engineering and Electronics

基　　金：国家自然科学基金(60674108;60705004)资助课题

摘　　要：针对求解贝叶斯网络最大主子图存在的NP(non-deterministic polynomialtine)难问题,提出了一种基于全条件独立结构的最大主子图连接树(maximal prime sub-graph decomposition junction tree,MPD-JT)构造算法。该算法通过道义图上的全条件独立结构得到贝叶斯网络最大主子图,并利用构成这些最大主子图的节点作为簇节点构造连接树,避免了三角化过程,而且在求解过程中通过删除一些符合条件的点,大大降低了算法复杂度。给出了算法的理论证明,通过具体案例分析验证了算法的有效性。As the decomposition of Bayesian networks（BN） into their maximal prime sub-graph is a NP-hard problem,a new method for constructing the maximal prime sub-graph junction tree（MPD-JT） of BN is presented.This approach obtains the MPD of BN motivated by the full conditional independence information encoded in the moral graph of the original BN and uses these MPDs as a cluster of nodes to construct a junction tree,it also avoids the process of triangulation and reduces the time complexity by eliminating some coincident nodes.The correctness of the method is proven and the validity of the algorithm is analyzed by an example.

关 键 词：贝叶斯网络 最大主子图 连接树 全条件独立 

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