计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (9): 303-310.doi: 10.11896/jsjkx.220700253

• 人工智能 • 上一篇    下一篇

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

徐苗1, 王慧玲1,2, 梁义1, 綦小龙1, 高阳2   

  1. 1 伊犁师范大学网络安全与信息技术学院 新疆 伊宁 835000
    2 南京大学计算机科学与技术系计算机软件国家重点实验室 南京 210023
  • 收稿日期:2022-07-26 修回日期:2022-11-09 出版日期:2023-09-15 发布日期:2023-09-01
  • 通讯作者: 綦小龙(qxl_0712@sina.com)
  • 作者简介:(xm_1192@163.com)
  • 基金资助:
    新疆维吾尔自治区自然科学基金(2021D01C467);伊犁师范大学博士科研启动项目(2020YSBS007);学实高层次人才岗位(YSXSQN22007)

Improved K2 Algorithm Based on Two-step Search Strategy

XU Miao1, WANG Huiling1,2, LIANG Yi1, QI Xiaolong1, GAO Yang2   

  1. 1 School of Cybersecurity & Information Technology,Yili Normal University,Yining,Xinjiang 835000,China
    2 State Key Laboratory for Novel Software Technology,Department of Computer Science and Technology,Nanjing University,Nanjing 210023,China
  • Received:2022-07-26 Revised:2022-11-09 Online:2023-09-15 Published:2023-09-01
  • About author:XU Miao,born in 1996,master.Her main research interest is probability graph model learning.
    QI Xiaolong,born in 1981,Ph.D,asso-ciate professor.His main research intere-sts include probability graph modeling and machine learning.
  • Supported by:
    Natural Science Foundation of Xinjiang Uygur Autonomous Region,China(2021D01C467),Doctoral Research Start-up Project of Yili Normal University(2020YSBS007) and Promising Scholar of Academic Integrity(YSXSQN22007).

PDF (PC)

240

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

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

Abstract: 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.

Key words: K2 algorithm, PC algorithm, v-structure, Neighbor set, Structure learning

中图分类号: 

  • TP181
[1]LOU C Y,LI X S,ATOUI M A.Bayesian network based on an adaptive threshold scheme for fault detection and classification[J].Industrial and Engineering Chemistry Research,2020,59(34):15155-15164.
[2]TAGHI-MOLLA A,RABBANI M,GAVARESHKI M,et al.Safety improvement in a gas refinery based on resilience engineering and macro-ergonomics indicators:a Bayesian network-artificial neural network approach[J].International Journal of System Assurance Engineering and Management,2020,11(3):641-654.
[3]ZHANG W J,JIANG L X,ZHANG H,et al.A two-layerBayesian model:random forest naive Bayes[J].Computer Research and Development,2021,58(9):2040-2051.
[4]MIGLIORINI F,DRIESSEN A,QUACK V,et al.Comparison between intra-articular infiltrations of placebo,steroids,hyaluronic and PRP for knee osteoarthritis:a Bayesian network meta-analysis[J].Archives of Orthopaedic and Trauma Surgery,2021,141(9):1473-1490.
[5]HU X G,LIU F,BU C Y.Research progress of cognitive tra-cking model in educational big data [J].Journal of Computer Research and Development,2020,57(12):2523-2546.
[6]CHICKERING D M.Learning Bayesian networks is NP-com-plete[J].Networks,1996,112(2):121-130.
[7]HECKERMAN B D,GEIGER D,CHICKERING D M.Learning Bayesian networks:the combination of knowledge and statistical data[J].Machine Learning,1995,20(3):197-243.
[8]SPIRTES P,GLYMOUR C.An algorithm for fast recovery ofsparse causal graphs[J].Social Science Computer Review,1991,9(1):62-72.
[9]ZHANG L W,GUO H P.Introduction to Bayesian networks[M].Beijing:Science Press,2006:66-70,186-188.
[10]LIU X Q,LIU X S.Structure learning of Bayesian networks by continuous particle swarm optimization algorithms[J].Journal of Statistical Computation and Simulation,2018,88(9):1-29.
[11]PINTO P C,NAGELE A,DEJORI M,et al.Using a local discovery ant algorithm for Bayesian network structure learning[J].IEEE Transactions on Evolutionary Computation,2009,13(4):767-779.
[12]CHEN H Y,ZHANG N.Bayesian network structure learning based on hybrid improved bird swarm algorithm[J].Journal of Air Force Engineering University(Natural Science Edition),2021,22(1):85-91,98.
[13]COOPER G F,HERSKOVITS E.A Bayesian method for the induction of probabilistic networks from data[J].Machine Lear-ning,1992,9(4):309-347.
[14]LERAY P,FRANCOIS O.BNT structure learning package:Documentation and experiments[R].Technical Report,Laboratoire PSI,2006.
[15]AN N,TENG Y,YANG J Y,et al.Bayesian network structure learning method based on causal effect[J].Computer Application Research,2018,35(12):3609-3613.
[16]WU Y H,MCCALL J,CORNE D.Two novel ant colony optimization approaches for Bayesian network structure learning[C]//Proceedings of IEEE Congress on Evolutionary Computation.Barcelona,Spain:IEEE,2010:1-7.
[17]BENMOHAMED E,LTIFI H,AYED M B.ITNO-K2PC:Animproved K2 algorithm with information-theory-centered node ordering for structure learning[J/OL].Journal of King Saud University-computer and Information Science.https://doi.org/10.1016/j.jksuci.2020.06.004.
[18]GAO F,HUANG D.A node sorting method for K2 algorithm in Bayesian network structure learning[C]//Proceedings of the 2020 IEEE International Conference on Artificial Intelligence and Computer Applications.IEEE Press,2020:106-110.
[19]ANDRIEU C,FREITAS N D,DOUCET A,et al.An introduction to MCMC for machine learning[J].Machine Learning,2003,50(1):5-43.
[20]ZHOU M Y,LIU Y A,XIAO Y.Improvement of K2 algorithm in Bayesian network structure learning[J].Journal of Nanjing University of Technology,2020,44(3):320-324.
[21]AOUAY S,JAMOUSSI S,AYED Y B.Particle swarm optimization based method for Bayesian Network structure learning[C]//Proceedings of the 5th International Conference on Mo-deling,Simulation and Applied Optimization.Hammamet,Tunisia:IEEE,2013:1-6.
[22]BEHJATI S,BEIGY H.Improved K2 algorithm for Bayesiannetwork structure learning[J].Engineering Applications of Artificial Intelligence,2020,91(5):1-12.
[23]YU K,LI J Y,LIU L.A review on algorithms for constraint-based causal discovery[EB/OL].(2016-11-12)[2021-12-06].https://arxiv.org/abs/1611.03977.
[24]TSAMARDINOS I,BROWN L E,ALIFERIS C F.The max-min hill-climbing Bayesian network structure learning algorithm[J].Machine Learning,2006,65(1):31-78.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发