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

Improved K2 Algorithm Based on Two-step Search Strategy

作　　者：徐苗 王慧玲 梁义 綦小龙 高阳[2] XU Miao;WANG Huiling;LIANG Yi;QI Xiaolong;GAO Yang(School of Cybersecurity&Information Technology,Yili Normal University,Yining,Xinjiang 835000,China;State Key Laboratory for Novel Software Technology,Department of Computer Science and Technology,Nanjing University,Nanjing 210023,China)

机构地区：[1]伊犁师范大学网络安全与信息技术学院,新疆伊宁835000 [2]南京大学计算机科学与技术系计算机软件国家重点实验室,南京210023

出　　处：《计算机科学》2023年第9期303-310,共8页Computer Science

基　　金：新疆维吾尔自治区自然科学基金(2021D01C467);伊犁师范大学博士科研启动项目(2020YSBS007);学实高层次人才岗位(YSXSQN22007)。

摘　　要：贝叶斯网络由于其强大的不确定性推理能力和因果可表示性越来越受到研究者的关注。从数据中学习一个贝叶斯网络结构被称为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.

关 键 词：K2算法 PC算法 v-结构 邻居集 结构学习 

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