一种基于两步搜索策略的K2改进算法

贝叶斯网络由于其强大的不确定性推理能力和因果可表示性越来越受到研究者的关注。从数据中学习一个贝叶斯网络结构被称为NP-hard问题。其中，针对K2算法强依赖于变量拓扑序的问题，提出了一种组合变量邻居集和v-结构信息的K2改进学习方法TSK2(Two-Step Search Strategy of K2)。该方法有效减小了序空间搜索规模，同时避免了过早陷入局部最优。具体而言，该方法在约束算法定向规则的启示下，借助识别的v-结构和邻居集信息可靠调整汇点的邻居在序中的位置；其次，在贝网基本组成结构的启发下，借助变量邻居集信息，通过执行顺连、分连、汇连3个基本结构的搜索，准确修正父节点与子节点的序位置，获得最优序列。实验结果表明，在Asia和Alarm网络数据集上，与对比方法相比，所提算法的准确率得到显著提升，可以获得更准确的网络结构。