Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (9): 303-310.doi: 10.11896/jsjkx.220700253

• Artificial Intelligence • Previous Articles     Next Articles

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)

244

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

CLC Number: 

  • 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.
[1] ZHONG Kun-hua, CHEN Yu-wen, QIN Xiao-lin. Sub-BN-Merge Based Bayesian Network Structure Learning Algorithm [J]. Computer Science, 2022, 49(11A): 210800172-7.
[2] CHEN Jun-fen,ZHANG Ming,ZHAO Jia-cheng. Clustering Algorithm by Fast Search and Find of Density Peaks for Complex High-dimensional Data [J]. Computer Science, 2020, 47(3): 79-86.
[3] LIN Lang, ZHANG Zi-li. Bayesian Structure Learning Based on Physarum Polycephalum [J]. Computer Science, 2019, 46(9): 206-210.
[4] XU Jian-rui, LI Zhan-wu and XU An. KDE-CGA Algorithm of Structure Learning for Small Sample Data Bayesian Network [J]. Computer Science, 2017, 44(Z11): 437-441.
[5] CAO Ru-sheng, NI Shi-hong and ZHANG Peng. Bayesian Networks Structure Learning Algorithm Based on Cloud Genetic Annealing [J]. Computer Science, 2017, 44(9): 239-242.
[6] SEIN Minn and FU Shun-kai. Accelerating Structure Learning of Bayesian Network [J]. Computer Science, 2016, 43(2): 263-268.
[7] FU Shun-kai, SU Zhi-zhen, Sein Minn and LV Tian-yi. Accelerating the Recovery of Markov Blanket Using Topology Information [J]. Computer Science, 2015, 42(Z11): 42-48.
[8] WEI Zhong-qiang, XU Hong-zhe, LI Wen and GUI Xiao-lin. Bayesian Network Structure Learning Algorithm Based on Conditional Mutual Information and Probabilistic Jumping Mechanism [J]. Computer Science, 2015, 42(3): 214-217.
[9] LI Peng-fei,LI Zhi-hua,YIN Xi,SUN Ya and ZHANG Hua-wei. Energy-level Based Clustering Network Topology Control Algorithm [J]. Computer Science, 2014, 41(3): 96-99.
[10] . Application of Bayesian Networl} to Predicting Students' Achievement [J]. Computer Science, 2012, 39(Z11): 280-282.
[11] . Bayesian Network Classifier Based on L1 Regularization [J]. Computer Science, 2012, 39(1): 185-189.
[12] HU Chun-ling ,HU Xue-gang （School of Computer and Information, Hefei University of Technology, Hefei 230009, China）. [J]. Computer Science, 2009, 36(2): 199-202.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.