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

Improved K2 Algorithm Based on Two-step Search Strategy

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

Bayesian network receiving increasing attention from researchers because of its strong uncertainty reasoning ability and causal representability.Learning a Bayesian network structure from data is an NP-hard problem.Among them,for the problem that the K2 algorithm strongly depends on the topological order of variables,an improved K2 learning method TSK2 is proposed,which combines variable neighbor sets and v-structure information.The proposed method effectively reduces the search scale in the order space and avoids prematurely falling into local optimum.Specifically,inspired by the orientation rules of the constraint algorithm,the method reliably adjusts the in-order position of the neighbors of the sink with the help of the identified v-structure and neighbor set information.Secondly,inspired by the basic structure of the shell net,with the help of the variable neighbor set information,the optimal sequence is obtained by performing the search of the three basic structures of shun-connection,sub-connection,and confluence-connection to accurately correct the order positions of parent nodes and child nodes.Experimental results show that the accuracy of the proposed algorithm is significantly improved compared with the comparison methods on the Asia and Alarm network datasets.A more accurate network structure can be learned.