基于多头绒泡菌的贝叶斯网络结构学习

doi:10.11896/j.issn.1002-137X.2019.09.030

摘要/Abstract

摘要： 贝叶斯网络是概率统计与图论相结合的一种图模型,已成功应用于多个领域中。然而,仅依赖专家的领域知识构建贝叶斯网络非常困难。因此,从数据中学习贝叶斯网络结构已经成为该研究领域的重点问题。针对贝叶斯网络结构学习搜索空间太大的问题,根据多头绒泡菌在觅食过程中展现出的保留重要觅食管道的特性,文中结合多头绒泡菌相关数学模型和条件互信息理论对原始搜索空间进行缩减,并将求解得到的无向图作为网络的基础骨架;之后利用爬山法确定骨架方向,并得到对应的拓扑排序;最后将节点顺序作为K2算法的输入以求得最终网络,并选用网络拓扑结构及评分作为评价指标在多个数据集上进行对比实验。实验结果表明,所提算法在网络重构及原始数据匹配上具有更高的准确度。

关键词: 贝叶斯网络, 多头绒泡菌, 结构学习, 条件互信息

Abstract: Bayesian network is a graph model which combines probability statistics and graph theory.It has been successfully applied in many fields.However,it is very difficult to build Bayesian network only depending on the domain knowledge of experts.Therefore,learning Bayesian network structure from data has become a key issue in this field.Bayesian network structure learning is a NP-hard problem because the search space is too large.According to the chara-cteristics of physarum polycephalum in the process of foraging to retain an important feeding pipeline,the original search space was reduced by combining the relevant mathematical model of physarum polycephalum and the theory of conditional mutual information.In this paper,the obtained undirected graph is used as the basic framework of the network,and then the mountain climbing method is used to determine the direction of the skeleton and get the correspon-ding topological ordering.Finally,the order of nodes is used as the input of K2 algorithm to get the final network.The network topology structure and score are selected as the evaluation index,and comparative experiments are carried out on multiple data sets.Experiments show that the proposed algorithm has higher accuracy in network reconfiguration and raw data matching.

Key words: Bayesian network, Independence condition mutual information, Physarum polycephalum, Structure learning

中图分类号:

TP391

林朗, 张自力. 基于多头绒泡菌的贝叶斯网络结构学习[J]. 计算机科学, 2019, 46(9): 206-210. https://doi.org/10.11896/j.issn.1002-137X.2019.09.030

LIN Lang, ZHANG Zi-li. Bayesian Structure Learning Based on Physarum Polycephalum[J]. Computer Science, 2019, 46(9): 206-210. https://doi.org/10.11896/j.issn.1002-137X.2019.09.030

参考文献

[1]THRUN S,MONTEMERLO M,DAHLKAMP H,et al.Stanley:The robot that won the DARPA Grand Challenge[J].Journal of field Robotics,2006,23(9):661-692.
[2]JURAFSKY D,MARTIN J H.Speech and language processing[M].London:Pearson,2014.
[3]CHICKERING D M,HECKERMAN D,MEEK C.Large-sample learning of Bayesian networks is NP-hard[J].Journal of Machine Learning Research,2004,5(Oct):1287-1330.
[4]KALISCH M,BÜHLMANN P.Estimating high-dimensional directed acyclic graphs with the PC-algorithm[J].Journal of Machine Learning Research,2007,8(Mar):613-636.
[5]MADSEN A L,JENSEN F,SALMERÓN A,et al.A parallel algorithm for Bayesian network structure learning from large data sets[J].Knowledge-Based Systems,2017,100(117):46-55.
[6]NIE S,DE CAMPOS C P,JI Q.Efficient learning of Bayesian networks with bounded tree-width[J].International Journal of Approximate Reasoning,2017,80(C):412-427.
[7]YUE K,FANG Q,WANG X,et al.A Parallel and Incremental Approach for Data-Intensive Learning of Bayesian Networks[J].IEEE Transactions on Cybernetics,2017,45(12):2890-2904.
[8]SUZUKI J.Learning Bayesian belief networks based on the mini-mum description length principle:an efficient algorithm using the B & B technique[C]//Proceedings of the Thirteenth International Conference on International Conference on Machine Learning.Morgan Kaufmann Publishers Inc.,1996:462-470.
[9]AKAIKE H.Information theory and an extension of the maximum likelihood principle[M]//Selected papers of hirotugu akaike.New York:Springer,1998:199-213.
[10]HECKERMAN D,GEIGER D,CHICKERING D M.LearningBayesian networks:The combination of knowledge and statistical data[J].Machine Learning,1995,20(3):197-243.
[11]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.
[12]AGHDAM R,GANJALI M,ZHANG X,et al.CN:a consensus algorithm for inferring gene regulatory networks using the SORDER algorithm and conditional mutual information test[J].Molecular BioSystems,2015,11(3):942-949.
[13]ABELLÁN J,CASTELLANO J.Improving the Naive Bayesclassifier via a quick variable selection method using maximum of entropy[J].Entropy,2017,19(6):247.
[14]TABAR V R.A Simple Node Ordering Method for the K2 Algorithm based on the Factor Analysis[C]//International Conference on Pattern Recognition Applications and Methods.2017:273-280.
[15]NAKAGAKI T,YAMADA H,TO’TH A.Maze-solving by an amoeboid organism[J].Nature,2000,407(6803):470.
[16]TERO A,KOBAYASHI R,NAKAGAKI T.A mathematicalmodel for adaptive transport network in path finding by true slime mold[J].Journal of Theoretical Biology,2007,244(4):553-564.
[17]ABRAMOVICI M,NEUBACH M,FATHI M,et al.Competing fusion for bayesian applications[C]//Proceedings of Information Processing and Management of Uncertainty.2008:379.
[18]TERO A,TAKAGI S,SAIGUSA T,et al.Rules for Biologically Inspired Adaptive Network Design[J].Science,2010,327(5964):439-442.

相关文章 15

[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]	柴慧敏, 方敏, 吕少楠. 基于态势评估技术的移动机器人局部路径规划 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
[7]	邢志伟, 朱慧, 李彪, 罗谦. 基于贝叶斯网络的航班离港时间动态估计 Dynamic Estimation of Flight Departure Time Based on Bayesian Network 计算机科学, 2019, 46(10): 329-335. https://doi.org/10.11896/jsjkx.181102039
[8]	张志东,王志海,刘海洋,孙艳歌. 一种基于树型贝叶斯网络的集成多标记分类算法 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
[9]	许建锐,李战武,徐安. 小样本贝叶斯网络结构学习的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
[10]	曹如胜,倪世宏,张鹏. 基于云遗传退火的贝叶斯网络结构学习算法 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
[11]	刘冬瑞,刘东升,张丽萍,侯敏,王春晖. 基于贝叶斯网络预测克隆代码质量 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
[12]	付永平,邱玉辉. 一种基于贝叶斯网络的个性化协同过滤推荐方法研究 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
[13]	曹如胜,倪世宏,张鹏,奚显阳. 一种基于云模型的贝叶斯网络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
[14]	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
[15]	傅顺开,苏致祯,Sein Minn,吕天依. 基于拓扑信息加速马尔科夫毯学习 Accelerating the Recovery of Markov Blanket Using Topology Information 计算机科学, 2015, 42(Z11): 42-48.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed