ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (11): 2558-2566.doi: 10.7544/issn1000-1239.2017.20160715

• 人工智能 • 上一篇    下一篇

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

吕亚丽1,2,武佳杰2,梁吉业1,钱宇华1   

  1. 1(计算智能与中文信息处理教育部重点实验室(山西大学) 太原 030006); 2(山西财经大学信息管理学院 太原 030006) (sxlvyali@163.com)
  • 出版日期: 2017-11-01
  • 基金资助: 
    国家自然科学基金重点项目(61432011);军民共用重大研究计划联合基金重点项目(U1435212);国家自然科学基金优秀青年科学基金项目(61322211);国家自然科学基金项目(61672332);中国博士后科学基金项目(2016M591409);山西省自然科学基金项目(2013011016-4,2014011022-2)

Random Search Learning Algorithm of BN Based on Super-Structure

Lü Yali1,2, Wu Jiajie2, Liang Jiye1, Qian Yuhua1   

  1. 1(Key Laboratory of Computational Intelligence and Chinese Information Processing (Shanxi University), Ministry of Education, Taiyuan 030006); 2(School of Information Management, Shanxi University of Finance & Economics, Taiyuan 030006)
  • Online: 2017-11-01

摘要: 近年来,贝叶斯网络(Bayesian network, BN)在不确定性知识表示与概率推理方面发挥着越来越重要的作用.其中,BN结构学习是BN推理中的重要问题.然而,在当前BN结构的2阶段混合学习算法中,大多存在一些问题:第1阶段无向超结构学习中存在容易丢失弱关系的边的问题;第2阶段的爬山搜索算法存在易陷入局部最优的问题.针对这2个问题,首先采用Opt01ss算法学习超结构,尽可能地避免出现丢边现象;然后给出基于超结构的搜索算子,分析初始网络的随机选择规则和对初始网络随机优化策略,重点提出基于超结构的随机搜索的SSRandom结构学习算法,该算法一定程度上可以很好地跳出局部最优极值;最后在标准Survey, Asia,Sachs网络上,通过灵敏性、特效性、欧几里德距离和整体准确率4个评价指标,并与已有3种混合学习算法的实验对比分析,验证了该学习算法的良好性能.

关键词: 贝叶斯网络, 结构学习, 随机搜索, 超结构, 混合算法

Abstract: Recently, Bayesian network(BN) plays a vital role in knowledge representation and probabilistic inference. BN structure learning is crucial to research on BN inference. However, there are some disadvantages in the most two-stage hybrid learning method of BN structure: it is easy to lose edges with weak relationship in the first stage, when we learn the super-structure; hill climbing search method is easily plunged into local optimum in the second stage. To avoid the two disadvantages, the super-structure of BN is firstly learned by Opt01ss algorithm, which makes the result miss few edges as much as possible. Secondly, based on super-structure, three search operators are given to analyze the random selection rule of the initial network and address the random optimization strategy for the initial network. Further, SSRandom learning algorithm of BN structure is proposed. The algorithm is a good way to jump out of local optimum extremum to a certain extent. Finally, the learning performance of the proposed SSRandom algorithm is verified by the experiments on the standard Survey, Asia and Sachs networks, by comparing with other three hybrid algorithms according to four evaluation indexs, such as the sensitivity, specificity, Euclidean distance and the percentage of overall accuracy.

Key words: Bayesian network (BN), structure learning, random search, super-structure, hybrid algorithm

中图分类号: