计算机科学 ›› 2022, Vol. 49 ›› Issue (11A): 210800172-7.doi: 10.11896/jsjkx.210800172
钟坤华1,2,3, 陈芋文1,2,3, 秦小林1,3
ZHONG Kun-hua1,2,3, CHEN Yu-wen1,2,3, QIN Xiao-lin1,3
摘要: 针对贝叶斯网络结构学习K2算法要求提供实际难以获得的准确先验节点顺序信息以及爬山算法对初始网络结构依赖性强且容易陷入局部最优的问题,提出了一种基于子网融合的贝叶斯网络结构学习算法Sub-BN-Merge。该算法首先为每个节点构造一个子网,并以Voting的方式融合生成每个节点的候选父节点集,然后基于评分函数在候选集中为每个节点搜索最优父节点集合,最后消除所得网络结构中的环路,并以此为初值进一步采用启发式搜发方法对其进行优化。在小型网络Asia、中型网络Alarm和大型网络Win95pts上进行了实验验证,同时分析了算法在数据存在缺失值情况下的性能。实验结果证明了算法的有效性,Sub-BN-Merge算法在结构汉明距和算法正确率方面优于对比算法。
中图分类号:
[1]KYRIMI E,MOSSADEGN S,TAI N,et al.An incremental explanation of inference in Bayesian networks for increasing model trustworthiness and supporting clinical decision making [J].Artificial Intelligence In Medicine,2020,103. [2]ADABOR E S,ACQUAAH-MENSAH G K.Restricted-dere-stricted dynamic Bayesian Network inference of transcriptional regulatory relationships among genes in cancer [J].Computational Biology and Chemistry,2019,79:155-164. [3]CHATRABGOUN O,HOSSEINIAN-FAR A.Approximatingnon-Gaussian Bayesian networks using minimum information vine model with applications in financial modelling [J].Journal of Computational Science,2018,24:266-276. [4]ADEDIPE T,SHAFIEE M.Bayesian Network Modelling forthe Wind Energy Industry:An Overview [J].Reliability Engineering and System Safety,2020,202. [5]COOPER G F,HERSKOVITS E.A Bayesian Method for the Induction of Probabilistic Networks from Data [J].Machine Learning,1992,9(4):309-347. [6]SCUTARI M,GRAAFLAND C E.Who learns better Bayesian network structures:Accuracy and speed of structure learning algorithms [J].International Journal of Approximate Reasoning,2019,115:235-253. [7]SPIRTER P,GLYMOUR C.Causation,Prediction,and Search(2nd edition)[M].The MIT Press,2000. [8]CHICKERING D M,HECKERMAN D.Large-Sample Learning of Bayesian Networks is NP-Hard [J].Journal of Machine Learning Research,2004,5:1287-1330. [9]TABAR V R,ESKANDARI F.Finding a set of candidate parents using dependency criterion for the K2 algorithm [J].Pattern Recognition Letters,2018,111:23-29. [10]BEHJATI S,BEIGY H.Improved K2 algorithm for Bayesiannetwork structure learning [J].Engineering Applications of Artificial Intelligence,2020,91. [11]YAN ZHI,ZHANG P.Research on Bayesian Network Structure Learning Algorithm Based on Jaya [J].Computer Engineering and Applications,2019,55(19):173-177,184. [12]LIU H R,ZHANG L Y.Bayesian Network Structure Learning Based on Improved Whale Optimization Strategy [J].Journal of Electronics & Information Technology,2019,41(6):1434-1441. [13]LIU B,FAN R X.Bayesian network structure learning algo-rithm based on hybrid binarysalp swarm-differential evolution algorithm [J].Journal on Communications,2019,40(7):151-161. [14]LI J W,LI G N.Application of CS-PSO algorithm in Bayesian Network structure learning [J].Journal of Measurement Science and Instrumentation,2020,11(1):94-102. [15]CHICKERING D M.Optimal Structure Identification WithGreedy Search [J].Journal of Machine Learning Research,2002,3:507-552. [16]ALONSO-BARBA J I,OSSA L D L.Scaling up the GreedyEquivalence Search algorithm by constraining the search space of equivalence classes [J].International Journal of Approximate Reasoning,2013,54:429-451. [17]ALONSO J I,OSSA L D L.On the use of local search heuristics to improve GES-based Bayesiannetwork learning [J].Applied Soft Computing,2018,64:366-376. [18]FRIEDMAN N,KOLLER D.A Bayesian Approach to Structure Discovery in Bayesian Networks [J].Machine Learning,2003,50:95-125. [19]LIU B,WANG H Y.Learning Bayesian Network Structure from Node Ordering Searching Optimal [J].Journal of Electronics & Information Technology,2018,40(5):1234-1241. [20]MARCO S.bnlearn-an R package for Bayesian network learning and inference [EB/OL].[2017-09-06].http://www.bnlearn.com/bnrepository,2013. [21]TEYSSIER M,KOLLER D.Ordering-Based Search:A Simpleand Effective Algorithm for Learning Bayesian Networks[J].arXiv:1207.1429. |
[1] | 李嘉睿, 凌晓波, 李晨曦, 李子木, 杨家海, 张蕾, 吴程楠. 基于贝叶斯攻击图的动态网络安全分析 Dynamic Network Security Analysis Based on Bayesian Attack Graphs 计算机科学, 2022, 49(3): 62-69. https://doi.org/10.11896/jsjkx.210800107 |
[2] | 韩丽霞, 张占营. 基于树增益朴素贝叶斯网络的服务定价策略 TAN-based Service Pricing Strategy 计算机科学, 2021, 48(6A): 203-. https://doi.org/10.11896/jsjkx.200900024 |
[3] | 李超, 覃飙. 高效计算因果网中的最大可能解释 Efficient Computation of MPE in Causal Bayesian Networks 计算机科学, 2021, 48(4): 14-19. https://doi.org/10.11896/jsjkx.200500155 |
[4] | 徐源音,柴玉梅,王黎明,刘箴. 基于OCC模型和贝叶斯网络的情绪句分类方法 Emotional Sentence Classification Method Based on OCC Model and Bayesian Network 计算机科学, 2020, 47(3): 222-230. https://doi.org/10.11896/jsjkx.190200331 |
[5] | 张成伟, 罗凤娥, 代毅. 基于数据挖掘的指定航班计划延误预测方法 Prediction Method of Flight Delay in Designated Flight Plan Based on Data Mining 计算机科学, 2020, 47(11A): 464-470. https://doi.org/10.11896/jsjkx.200600001 |
[6] | 林朗, 张自力. 基于多头绒泡菌的贝叶斯网络结构学习 Bayesian Structure Learning Based on Physarum Polycephalum 计算机科学, 2019, 46(9): 206-210. https://doi.org/10.11896/j.issn.1002-137X.2019.09.030 |
[7] | 柴慧敏, 方敏, 吕少楠. 基于态势评估技术的移动机器人局部路径规划 Local Path Planning of Mobile Robot Based on Situation Assessment Technology 计算机科学, 2019, 46(4): 210-215. https://doi.org/10.11896/j.issn.1002-137X.2019.04.033 |
[8] | 邢志伟, 朱慧, 李彪, 罗谦. 基于贝叶斯网络的航班离港时间动态估计 Dynamic Estimation of Flight Departure Time Based on Bayesian Network 计算机科学, 2019, 46(10): 329-335. https://doi.org/10.11896/jsjkx.181102039 |
[9] | 张志东,王志海,刘海洋,孙艳歌. 一种基于树型贝叶斯网络的集成多标记分类算法 Ensemble Multi-label Classification Algorithm Based on Tree-Bayesian Network 计算机科学, 2018, 45(3): 189-195. https://doi.org/10.11896/j.issn.1002-137X.2018.03.030 |
[10] | 许建锐,李战武,徐安. 小样本贝叶斯网络结构学习的KDE-CGA算法 KDE-CGA Algorithm of Structure Learning for Small Sample Data Bayesian Network 计算机科学, 2017, 44(Z11): 437-441. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.093 |
[11] | 曹如胜,倪世宏,张鹏. 基于云遗传退火的贝叶斯网络结构学习算法 Bayesian Networks Structure Learning Algorithm Based on Cloud Genetic Annealing 计算机科学, 2017, 44(9): 239-242. https://doi.org/10.11896/j.issn.1002-137X.2017.09.045 |
[12] | 刘冬瑞,刘东升,张丽萍,侯敏,王春晖. 基于贝叶斯网络预测克隆代码质量 Prediction of Code Clone Quality Based on Bayesian Network 计算机科学, 2017, 44(4): 165-168. https://doi.org/10.11896/j.issn.1002-137X.2017.04.036 |
[13] | 付永平,邱玉辉. 一种基于贝叶斯网络的个性化协同过滤推荐方法研究 Method of Personalized Collaboration Filter Recommendation Based on Bayesian Network 计算机科学, 2016, 43(9): 266-268. https://doi.org/10.11896/j.issn.1002-137X.2016.09.053 |
[14] | 曹如胜,倪世宏,张鹏,奚显阳. 一种基于云模型的贝叶斯网络EM参数学习算法 EM Parameter Learning Algorithm of Bayesian Network Based on Cloud Model 计算机科学, 2016, 43(8): 194-198. https://doi.org/10.11896/j.issn.1002-137X.2016.08.039 |
[15] | SEIN Minn,傅顺开. 贝叶斯网络结构加速学习算法 Accelerating Structure Learning of Bayesian Network 计算机科学, 2016, 43(2): 263-268. https://doi.org/10.11896/j.issn.1002-137X.2016.02.055 |
|