一种具有结构先验的贝叶斯网络结构学习算法

doi:10.16180/j.cnki.issn1007-7820.2023.11.001

摘要/Abstract

摘要：

贝叶斯网络(Bayesian Network,BN)的计算复杂度随着节点数量的增加而增加,其最优结构仍是一个NP(Non-deterministic Polynomial Time)-hard问题。为优化贝叶斯网络结构,提高复杂BN结构的计算能力,通过约束和分数的混合学习方式进行BN结构优化。基于约束的学习采用PC(Peter-Clark)算法生成初始网络结构,以提高网络的初始评分。基于分数的学习采用麻雀搜索算法寻找BN的最优结构,以增强其在BN中的评分搜索能力。将麻雀搜索算法同PC算法应用于BN优化其结构,并采用标准BN进行实验,证明了所提算法在BN结构学习中的可行性与有效性。不同复杂度的网络实验表明,相比其他算法,文中所提方法获得了更好的贝叶斯信息准则评分,且在ASIA网络上的2 000个样本的测试中,与标准分数误差仅为0.2。

关键词: 贝叶斯网络, 结构学习, BIC评分, 先验结构, 麻雀搜索算法, PC算法, 约束学习, 分数学习

Abstract:

The computational complexity of Bayesian Networks(BN) increases with the increase of the number of nodes, and the optimal structure of BN is still a NP(Non-deterministic Polynomial Time)-hard problem. To optimize the BN structure and improve the computing power of the complex BN structure, the BN structure is optimized through the hybrid learning method of constraints and scores. In the constrained learning, PC (Peter-Clark) algorithm is used to generate the initial network structure to improve the initial score of the network. Score-based learning uses the sparrow search algorithm to find the optimal structure of BN to enhance its scoring search ability in BN. The sparrow search algorithm and PC algorithm are applied to BN to optimize its structure, and the standard BN is used to conduct experiments, which proves the feasibility and effectiveness of the proposed algorithm in BN structure learning. Experiments on networks with different complexities show that the proposed method obtains better BIC scores than other algorithms, and in the test of 2 000 samples on the ASIA network, the error from the standard score is only 0.2.

Key words: Bayesian network, structure learning, BIC score, prior structure, sparrow search algorithm, PC algorithm, constraint-based learning, score-based learning

中图分类号:

TP18

仝兆景,李金香,乔征瑞. 一种具有结构先验的贝叶斯网络结构学习算法[J]. 电子科技, 2023, 36(11): 1-7.

TONG Zhaojing,LI Jinxiang,QIAO Zhengrui. A Bayesian Network Structure Learning Algorithm with Structure Priors[J]. Electronic Science and Technology, 2023, 36(11): 1-7.

图/表 12

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

图10

表2

参考文献 19

[1]	Zheng Y, Zhao F, Wang Z. Fault diagnosis system of bridge crane equipment based on fault tree and Bayesian network[J]. International Journal of Advanced Manufacturing Technology, 2019, 105(9):3605-3618. doi: 10.1007/s00170-019-03793-0
[2]	Wang X, Pan J, Ren Z, et al. Application of a novel hybrid algorithm of Bayesian network in the study of hyperlipidemia related factors:A cross-sectional study[J]. BMC Public Health, 2021, 21(1):1-14. doi: 10.1186/s12889-020-10013-y
[3]	Vagis A A. Bayesian recognition procedures on networks[J]. Journal of Automation and Information Sciences, 2010, 42(11):58-63.
[4]	Yang Z, Wan C, Yang Z, et al. Using Bayesian network based TOPSIS to aid dynamic port state control detention risk control decision[J]. Reliability Engineering & System Safety, 2021, 213(4):107784. doi: 10.1016/j.ress.2021.107784
[5]	仝兆景, 乔征瑞, 李金香, 等. 基于MPC算法优化的贝叶斯网络变压器故障诊断[J]. 电子测量技术, 2021, 44(17):41-45.
	Tong Zhaojing, Qiao Zhengrui, Li Jinxiang, et al. Transformer fault diagnosis based on MPC algorithm optimized by bayesian network[J]. Electronic Measurement Technology, 2021, 44(17):41-45.
[6]	Le A, Chen Y, Chai K K, et al. Incorporating FAIR into Bayesian network for numerical assessment of loss event frequencies of smart grid cyber threats[J]. Mobile Networks and Applications, 2019, 24(5):1713-1721. doi: 10.1007/s11036-018-1047-6
[7]	Zhu J, Mu L, Ma D, et al. Faulty line identification method based on Bayesian optimization for distribution network[J]. IEEE Access, 2021, 9(12):83175-83184. doi: 10.1109/ACCESS.2021.3087131
[8]	Liu Z, Lv K, Zheng C, et al. A fault diagnosis method for rolling element bearings based on ICEEMDAN and Bayesian network[J]. Journal of Mechanical Science and Technology, 2022, 36(5):2201-2212. doi: 10.1007/s12206-022-0404-3
[9]	仝兆景, 乔征瑞, 李金香, 等. 基于改进麻雀搜索算法优化BN的变压器故障诊断研究[J]. 电子科技, 2023, 36(4):52-58.
	Tong Zhaojing, Qiao Zhengrui, Li Jinxiang, et al. Research on transformer fault diagnosis based on improved sparrow search algorithm optimization BN[J]. Electronic Science and Technology, 2023, 36(4):52-58.
[10]	仝兆景, 李金香, 乔征瑞, 等. 基于改进贝叶斯网络的电机轴承故障诊断[J]. 电子测量技术, 2022, 45(7):48-55.
	Tong Zhaojing, Li Jinxiang, Qiao Zhengrui, et al. Motor bearing fault diagnosis based on improved Bayesian network[J]. Electronic Measurement Technology, 2022, 45(7):48-55.
[11]	张淑清, 苑世钰, 姚玉永, 等. 基于ICEEMD及AWOA优化ELM的机械故障诊断方法[J]. 仪器仪表学报, 2019, 40(11):172-180.
	Zhang Shuqing, Yuan Shiyu, Yao Yuyong, et al. Machinery fault diagnosis method based on ICEMMD and AWOA optimized ELM[J]. Chinese Journal of Scientific Instrument, 2019, 40(11):172-180.
[12]	肖晓晖. 基于改进果蝇优化算法优化 SVM 的模拟电路故障诊断[J]. 电子测量与仪器学报, 2019, 31(5):57-64.
	Xiao Xiaohui. Fault diagnosis of analog circuit based on SVM optimized by improved fruit fly optimization algorithm[J]. Journal of Electronic Measurement and Instrumentation, 2019, 33(5):57-64.
[13]	刘彬, 王海羽, 孙美婷, 等. 一种通过节点序寻优进行贝叶斯网络结构学习的算法[J]. 电子与信息学报, 2018, 40(5):1234-1241.
	Liu Bin, Wang Haiyu, Sun Meiting, et al. Learning Bayesian network structure from node ordering searching optimal[J]. Journal of Electronics & Information Technology, 2018, 40(5):1234-1241.
[14]	Tsamardinos I, Brown L E, Aliferis C F. The maxmin hill-climbing Bayesian network structure learning algorithm[J]. Machine Learning, 2006, 65(1):31-78. doi: 10.1007/s10994-006-6889-7
[15]	刘浩然, 张力悦, 范瑞星, 等. 基于改进鲸鱼优化策略的贝叶斯网络结构学习算法[J]. 电子与信息学报, 2019, 41(6):1434-1441.
	Liu Haoran, Zhang Liyue, Fan Ruixing, et al. Bayesian network structure learning based on improved whale optimization strategy[J]. Journal of Electronics & Information Technology, 2019, 41(6):1434-1441.
[16]	Sun B, Zhou Y, Wang J, et al. A new PC-PSO algorithm for Bayesian network structure learning with structure priors[J]. Expert Systems with Applications, 2021, 184(2):115237. doi: 10.1016/j.eswa.2021.115237
[17]	Strobl E V. Automated hyperparameter selection for the PC algorithm[J]. Pattern Recognition Letters, 2021, 151(2):288-293. doi: 10.1016/j.patrec.2021.09.009
[18]	赵鉴, 袁渤巽, 倪凌凡, 等. 基于改进粒子群算法在多能互补微网中的应用[J]. 电子科技, 2022, 35(10):1-8.
	Zhao Jian, Yuan Boxun, Ni Lingfan, et al. Application of improved particle swarm optimization in multi-energy complementary microgrid[J]. Electronic Science and Technology, 2022, 35(10):1-8.
[19]	Xue J, Shen B. A novel swarm intelligence optimization approach:Sparrow search algorithm[J]. Systems Science & Control Engineering An Open Access Journal, 2020, 8(1):22-34.

网络	样本容量
	500		1 000		1 500		2 000
	标准分数	测试分数	标准分数	测试分数	标准分数	测试分数	标准分数	测试分数
CANCER	-1 091.77	-1 109.28	-2 165.31	-2 169.74	-3 181.13	-3 185.49	-4 167.27	-4 169.83
ASIA	-1 169.78	-1 171.88	-2 246.94	-2 247.82	-3 330.88	-3 334.67	-4 507.07	-4 507.59
INSURANCE	-9 492.39	-9 752.76	-16 338.98	-16 379.55	-23 039.49	-23 268.42	-29 673.97	-30 231.47

标准贝叶斯网络	算法	BIC	误差	迭代次数
CANCER	标准分数	-1 091.77	0.00	0
	PSO	-1 123.79	32.02	5
	SSA	-1 119.18	27.41	5
	PC-SSA	-1 109.28	17.51	3
ASIA	标准分数	-1 169.78	0.00	0
	PSO	-1 178.05	8.27	44
	SSA	-1 173.52	3.74	26
	PC-SSA	-1 171.88	2.10	12
INSURANCE	标准分数	-9 492.39	0.00	0
	PSO	-8 890.16	602.23	93
	SSA	-9 981.13	488.74	97
	PC-SSA	-9 752.76	260.37	93