基于模拟退火的贝叶斯网络结构学习算法  

An Algorithm for Bayesian Networks Structure Learning Based on Simulated Annealing

作　　者：张少中[1] 王秀坤[1] 丁华[1] 

机构地区：[1]大连理工大学计算机科学与工程系,大连116023

出　　处：《计算机科学》2004年第10期196-199,208,共5页Computer Science

基　　金：国家科技部973专项;2001CCA00700

摘　　要：贝叶斯网络的学习可分为结构学习和参数学习。基于模拟退火的结构学习算法是一种以搜索最高记分函数为原则的智能优化方法。本文以KL距离、相互信息以及最大相互信息为基础,通过附加合适的约束函数降低学习搜索的复杂度,提出一种附加约束的最大熵优化函数作为模拟退火算法的能量优化函数,并结合贝叶斯网络结构学习的特点设计了适合模拟退火的变量表示和邻近值产生机制。通过与其他用于结构学习的模拟退火算法,以及遗传和进化算法比较分析,结果表明本文中提出的基于模拟退火的贝叶斯网络结构学习算法在时间和精度上都具有较好的效果。The automated creation of Bayesian networks can be separated into two tasks, Structure learning, which consists of creating the structure of the Bayesian networks from the collected data, and parameter learning, which consists of calculating the numerical parameters for a given structure. We present a simulated annealing algorithm for structure learning in Bayesian networks and propose a score function for optimization based on maximum mutual information entropy with odditional restriction. The entropy is based on KL distance, mutual information and maximum mutual information. We also propose a denotative form for variable and give a mechanism for generating contiguous data. Some experimentation on other simulated annealing and genetic or Evolutionary algorithms are given. The result indicates that the simulated annealing algorithm based MMI-L that we propose has more efficiency and precisely in cost and precision than others.

关 键 词：结构学习 贝叶斯网络 模拟退火算法 算法 搜索 参数学习 最大熵 约束函数 表示 距离 

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