基于条件互信息和概率突跳机制的贝叶斯网络结构学习算法  

Bayesian Network Structure Learning Algorithm Based on Conditional Mutual Information and Probabilistic Jumping Mechanism

作　　者：魏中强[1] 徐宏喆[1] 李文[1] 桂小林[1] 

机构地区：[1]西安交通大学陕西省计算机网络重点实验室,西安710049

出　　处：《计算机科学》2015年第3期214-217,共4页Computer Science

基　　金：国家自然科学基金(61172090)资助

摘　　要：贝叶斯网络分类器的精确构造是NP难问题,使用K2算法可以有效地缩减搜索空间,提高学习效率。然而K2算法需要初始的节点次序作为输入,这在缺少先验信息的情况下很难确定;另一方面,K2算法采用贪婪的搜索策略,容易陷入局部最优解。提出了一种基于条件互信息和概率突跳机制的贝叶斯网络结构学习算法(CMI-PK2算法),该算法首先利用条件互信息生成有效的节点次序作为K2算法的输入,然后利用概率突跳机制改进K2算法的搜索过程来提高算法的全局寻优能力,学习较为理想的网络结构。在两个基准网络Asia和Alarm上进行了实验验证,结果表明CMI-PK2算法具有更高的分类精度和数据拟合程度。Precise construction of Bayesian network classifier is an NP-hard problem.K2 algorithm can reduce search space effectively and improve learning efficiency,but it requires the initial node ordering as input,which is very limited by the absence of the priori information.On the other hand,K2 algorithm uses a greedy search strategy and is easy to fall into local optimization solutions.This paper presented a new Bayesian network structure learning algorithm based on conditional mutual information and probabilistic jumping mechanism.Firstly,conditional mutual information is used to determine the initial node ordering as input of K2 algorithm.Then probabilistic jumping mechanism is introduced into K2 algorithm to improve the search process and the ability of global optimization,and learn more reasonable network structure.Experimental results over two benchmark networks Asia and Alarm show that this new improved algorithm has higher classification accuracy and better degree of data matching.

关 键 词：贝叶斯网络分类器 结构学习 条件互信息 概率突跳 K2算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]