基于超结构与随机搜索的BN结构学习算法

发布时间：2018-06-18 22:59

本文选题：贝叶斯网络 + 混合结构学习　；参考：《山西财经大学》2017年硕士论文

【摘要】：近年来,贝叶斯网络(Bayesian network,BN)在不确定性知识表示与概率推理方面发挥着越来越重要的作用。作为一种重要的图模型方法,该模型已被广泛应用于生物信息学、金融预测分析、编码学、数据挖掘与机器学习等领域。其中,BN结构学习是BN推理研究中的重要问题,也是该模型推向应用的前提基础。然而,当前较为流行的两阶段混合结构学习算法中,大多存在两个问题:第一阶段无向超结构学习中存在容易丢失弱关系的边的问题;第二阶段的爬山随机搜索时存在易陷入局部极值的问题。针对这些问题,本文基于超结构和随机搜索策略,研究了两种BN结构的混合学习算法。具体研究内容和创新之处包括:第一,提出了基于超结构和随机搜索的SSRS算法。首先采用Opt01ss算法学习超结构,尽可能地避免出现丢边现象。然后,给出基于超结构的两种随机搜索操作,分析初始网络的随机产生规则和对初始网络的随机优化策略,重点提出SSRS结构学习算法,该算法在一定程度上可以很好地跳出局部最优极值。第二,提出了扩展的SSRS算法,即E-SSRS算法。在E-SSRS算法中,首先在初始网络的选择阶段,增加了通过评分选择对每条边添加方向之步骤,使得选取的初始网络更靠近最优网络。然后,在优化阶段,对删边策略进行了扩展,使用了基于马尔科夫毯的策略对网络进行修剪,进一步提出E-SSRS算法。通过扩展,使该算法减少了搜索次数,进一步提高算法效率。第三,设计并实现了SSRS算法和E-SSRS算法。分别在标准Survey,Asia和Sachs,Child网络上,通过几种评价指标,并与已有六种混合学习算法实验结果的对比分析,验证了本文所提出的两种混合结构学习算法的良好性能。
[Abstract]:In recent years, Bayesian Network (BN) plays an increasingly important role in uncertain knowledge representation and probabilistic reasoning. As an important graph model method, the model has been widely used in the fields of bioinformatics, financial prediction and analysis, coding, data mining and machine learning. The learning of BN structure is an important problem in the research of BN reasoning, and it is also the prerequisite for the application of the model. However, most of the popular two-stage hybrid structure learning algorithms have two problems: the first stage undirected superstructure learning has the problem of losing the edge of weak relation easily in the first stage undirected superstructure learning; In the second stage of the mountain climbing random search, the problem of local extremum is easy to fall into. In order to solve these problems, the hybrid learning algorithms of two BN structures are studied based on hyperstructure and random search strategy. The main contents and innovations are as follows: first, a new SSRS algorithm based on hyperstructure and random search is proposed. First, we use Opt01ss algorithm to learn the superstructure to avoid the phenomenon of edge loss as far as possible. Then, two kinds of random search operations based on superstructure are given, the random generation rules of initial network and the random optimization strategy of initial network are analyzed, and the SSRS structure learning algorithm is put forward. To some extent, the algorithm can get rid of the local optimal extremum. Secondly, an extended SSRS algorithm, E-SSRS algorithm, is proposed. In the E-SSRS algorithm, in the selection stage of the initial network, the step of adding direction to each edge is added to make the selected initial network closer to the optimal network. Then, in the optimization phase, the edge deletion strategy is extended and the network is pruned based on Markov blanket, and an E-SSRS algorithm is proposed. By extending the algorithm, the search times are reduced and the efficiency of the algorithm is further improved. Thirdly, SSRS algorithm and E-SSRS algorithm are designed and implemented. In the standard survey Asia and Sachschild networks, the performance of the two hybrid learning algorithms proposed in this paper is verified by comparing the experimental results with the experimental results of six hybrid learning algorithms.
【学位授予单位】：山西财经大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】