基于双重约束的最优BN结构学习算法OA北大核心CSTPCD

针对现有基于动态规划的贝叶斯网络结构学习算法复杂度高、无法在合理时间内学习大规模网络的问题,提出基于双重约束的最优贝叶斯网络(Bayesian Network,BN)结构学习算法.首先,利用最大信息系数和马尔科夫毯限制条件独立性(Conditional Independence,CI)测试的候选节点集合和约束集,得到邻居节点集合;其次,利用邻居节点集合约束父节点图的搜索过程,得到候选父节点集合,从候选父节点集合中取出每个节点的最优父集构造初始有向图;再次,利用Tarjan算法计算初始有向图中的强连通分量,得到节点块序;最后,利用节点块序约束节点序图的搜索过程,获得最优的BN结构.实验表明,相比于现有的5种基于动态规划的结构学习算法,本文提出的算法在精度稍微降低的前提下,极大幅度提高了算法的学习效率,如Sachs网络,本文提出的算法相对DPCMB(Dynamic Programming Constrained with Markov Blanket)算法降低了40.3%的时耗,算法精度下降了12.1%.