基于拓扑排序的贝叶斯网络结构学习方法

Bayesian Network Structure Learning Based on Topology Sorting

贝叶斯网络是一种运用于知识推理的信息模型,为解决网络结构学习过程中K2算法易受节点顺序影响问题,提出了一种基于拓扑排序的贝叶斯结构学习方法。算法首先采用最大权重生成树算法确定节点间连接关系建立生成树;其次通过带环监测的深度优先搜索算法为节点进行拓扑排序;最后将深度优先搜索的排序提供给K2算法选取评分最高的网络结构作为结构学习结果。算法与采用广度优先搜索算法进行节点排序的结构学习结果比较表明,在大中型网络上的正确率和学习效率有良好效果。

Bayesian network is a kind of information model applied to knowledge reasoning. To solve the problem that K2 algorithm is easily affected by the order of nodes in learning network structure,a Bayesian learning method based on topological ordering is proposed. Firstly,the algorithm uses the maximum weighted spanning tree algorithm to determine the connection between nodes and builds a spanning tree. Secondly,it uses the Depth-first Search algorithm with loop detection to sort the nodes. Finally,the Depth-first Search order is provided to the K2 algorithm to select the highest rated network structure as a result of structure learning. The comparison between the algorithm and the structure learning results using the Breadth-first Search algorithm for node ordering shows there is a good effect of the correctness and learning efficiency in large and medium-sized networks.