高维数据局部贝叶斯网络结构学习

doi:10.12305/j.issn.1001-506X.2024.08.15

摘要/Abstract

摘要：

针对高维数据下贝叶斯网络结构学习精度和效率低的问题, 提出一种基于归一化互信息和近似马尔可夫毯的特征选择(feature selection based on normalized mutual information and approximate Markov blanket, FSNMB)算法来获取目标节点的马尔可夫毯(Markov blanket, MB), 进一步结合MB和Meek规则实现基于特征选择的局部贝叶斯网络结构(construct local Bayesian network based on feature selection, FSCLBN)算法, 提高局部贝叶斯网络结构学习的精度和效率。实验证明, 在高维数据中, FSCLBN算法与现存的局部贝叶斯网络结构学习算法相比更具优势。

关键词: 贝叶斯网络, 特征选择, 互信息, 马尔可夫毯

Abstract:

To address the issue of low learning accuracy and efficiency of Bayesian network structure learning under high-dimensional data, a feature selection based on normalized mutual information and approximate Markov blanket (FSNMB) algorithm is proposed to obtain the Markov blanket (MB) of the target node. The MB and Meek's rule are further combined to implement the algorithm of construct local Bayesian network based on feature selection (FSCLBN), which improves the accuracy and efficiency of local Bayesian network structure learning. Experiment results show that in high-dimensional data, the FSCLBN algorithm has more advantages than the existing local Bayesian network structure learning algorithms.

Key words: Bayesian network, feature selection, mutual information, Markov blanket (MB)

中图分类号:

TP181

王阳阳, 高晓光, 茹鑫鑫. 高维数据局部贝叶斯网络结构学习[J]. 系统工程与电子技术, 2024, 46(8): 2676-2685.

Yangyang WANG, Xiaoguang GAO, Xinxin RU. Local Bayesian network structure learning for high-dimensional data[J]. Systems Engineering and Electronics, 2024, 46(8): 2676-2685.

图/表 12

图1

图2

表1

表2

表3

表4

表5

表6

表7

表8

表9

表10

参考文献 31

1	CHEN S H , POLLINO C A . Good practice in Bayesian network modelling[J]. Environmental Modelling & Software, 2012, 37, 134- 145.
2	SCANAGATTA M , SALMERON A , STELLA F . A survey on Bayesian network structure learning from data[J]. Progress in Artificial Intelligence, 2019, 8, 425- 439. doi: 10.1007/s13748-019-00194-y
3	ZHANG Y , WENG W G . Bayesian network model for buried gas pipeline failure analysis caused by corrosion and external interference[J]. Reliability Engineering & System Safety, 2020, 203, 107089.
4	WANG Y Y , GAO X G , RU X X , et al. Using feature selection and Bayesian network identify cancer subtypes based on proteomic data[J]. Journal of Proteomics, 2023, 280, 104895. doi: 10.1016/j.jprot.2023.104895
5	茹鑫鑫, 高晓光, 王阳阳. 基于模糊约束的贝叶斯网络参数学习[J]. 系统工程与电子技术, 2023, 45 (2): 444- 452. doi: 10.12305/j.issn.1001-506X.2023.02.15
	RU X X , GAO X G , WANG Y Y . Bayesian network parameter learning based on fuzzy constraints[J]. Systems Engineering and Electronics, 2023, 45 (2): 444- 452. doi: 10.12305/j.issn.1001-506X.2023.02.15
6	WANG X C , REN H J , GUO X X . A novel discrete firefly algorithm for Bayesian network structure learning[J]. Knowledge-Based Systems, 2022, 242, 108426. doi: 10.1016/j.knosys.2022.108426
7	CHICKERING M , HECKERMAN D , MEEK C . Large-sample learning of Bayesian networks is NP-hard[J]. Journal of Machine Learning Research, 2004, 5, 1287- 1330.
8	谭翔元, 高晓光, 贺楚超. 基于马尔可夫毯约束的最优贝叶斯网络结构学习算法[J]. 电子学报, 2019, 47 (9): 1898- 1904. doi: 10.3969/j.issn.0372-2112.2019.09.012
	TAN X Y , GAO X G , HE C C . Learning optimal bayesian network structure constrained with Markov blanket[J]. Acta Electronica Sinica, 2019, 47 (9): 1898- 1904. doi: 10.3969/j.issn.0372-2112.2019.09.012
9	BUI A T , JUN C H . Learning Bayesian network structure using Markov blanket decomposition[J]. Pattern Recognition Letters, 2012, 33 (16): 2134- 2140. doi: 10.1016/j.patrec.2012.06.013
10	KOLLER D , SAHAMI M . Toward optimal feature selection[J]. Internationa Conference on Machine Learning, 1996, 28 (96): 284- 292.
11	MARGARITIS D , THRUN S . Bayesian network induction via local neighborhoods[J]. Advances in Neural Information Processing Systems, 1999, 12, 505- 511.
12	TSAMARDINOS I, ALIFERIS C F, STATNIKOV A R, et al. Algorithms for large scale Markov blanket discovery[C]//Proc. of the 16th International FAIRS Conference, 2003: 376-380.
13	TSAMARDINOS I , BROWN L E , ALIFERIS C F . The max-min hill-climbing Bayesian network structure learning algorithm[J]. Machine Learning, 2006, 65, 31- 78. doi: 10.1007/s10994-006-6889-7
14	ALIFERIS C F, TSAMARDINOS I, STATNIKOV A. HITON: a novel Markov blanket algorithm for optimal variable selection[C]//Proc. of the AMIA Annual Symposium, 2003.
15	GAO T , JI Q . Efficient Markov blanket discovery and its application[J]. IEEE Trans. on Cybernetics, 2016, 47 (5): 1169- 1179.
16	BOMMERT A , SUN X D , BISCHL B , et al. Benchmark for filter methods for feature selection in high-dimensional classification data[J]. Computational Statistics & Data Analysis, 2020, 143, 106839.
17	JIA W K , SUN M L , LIAN J , et al. Feature dimensionality reduction: a review[J]. Complex & Intelligent Systems, 2022, 8 (3): 2663- 2693.
18	YU K , LIU L , LI J Y . A unified view of causal and non-causal feature selection[J]. ACM Transaction on Knowledge Discovery from Data, 2021, 15 (4): 1- 46.
19	SUN L Q , YANG Y L , NING T . A novel feature selection using Markov blanket representative set and particle swarm optimization algorithm[J]. Computational and Applied Mathematics, 2023, 42, 81. doi: 10.1007/s40314-023-02221-0
20	施启军, 潘峰, 龙福海, 等. 特征选择方法研究综述[J]. 微电子学与计算机, 2022, 39 (3): 1- 8.
	SHI Q J , PAN F , LONG F H , et al. A review of feature selection methods[J]. Microelectronics & Computer, 2022, 39 (3): 1- 8.
21	YU L , LIU H . Efficient feature selection via analysis of relevance and redundancy[J]. The Journal of Machine Learning Research, 2004, 5, 1205- 1224.
22	ESTEVEZ P A , TESMER M , PEREZ C A , et al. Normalized mutual information feature selection[J]. IEEE Trans. on Neural Networks, 2009, 20 (2): 189- 201. doi: 10.1109/TNN.2008.2005601
23	KERBER R. Chimerge: discretization of numeric attributes[C]//Proc. of the 10th National Conference on Artificial Intelligence, 1992: 123-128.
24	HARTEMINK A J. Principled computational methods for the validation discovery of genetic regulatory networks[D]. Cambridge: Massachusetts Institute of Technology, 2001.
25	RESHEF D N , RESHEF Y A , FINUCANE H K , et al. Detecting novel associations in large data sets[J]. Science, 2011, 334 (6062): 1518- 1524. doi: 10.1126/science.1205438
26	LI J D , CHENG K W , WANG S H , et al. Feature selection: a data perspective[J]. ACM Computing Surveys, 2017, 50 (6): 1- 45.
27	GAO T, FADNIS K, CAMPBELL M. Local-to-global Bayesian network structure learning[C]//Proc. of the 34th International Conference on Machine Learning, 2017: 1193-1202.
28	YIN J X, ZHOU Y, WANG C Z, et al. Partial orientation and local structural learning of causal networks for prediction[C]//Proc. of the Workshop on the Causation and Prediction Challenge, 2008: 93-105.
29	GAO T, JI Q. Local causal discovery of direct causes and effects[C]//Proc. of the 29th Annual Conference on Neural Information Processing Systems, 2015: 2512-2520.
30	WANG C Z , ZHOU Y , ZHAO Q , et al. Discovering and orienting the edges connected to a target variable in a DAG via a sequential local learning approach[J]. Computational Statistics & Data Analysis, 2014, 77, 252- 266.
31	MARKELLE K, RACHEL L, KOLBY N. The UCI Machine Learning Repository[EB/OL]. [2023-08-06]. https:archive.ics.uci.edu.

标准网络	节点数量	边数量	最大入度	最大出度
Alarm	37	46	4	5
Hepar2	70	123	6	17
Win95pts	76	112	5	10
Pathfinder	109	195	5	106
Andes	223	338	6	12

节点序号	所属网络	PC和配偶节点数量
35	Alarm	1, 4, 3
19	Hepar2	2, 17, 7
31	Win95pts	0, 10, 19
1	Pathfinder	0, 106, 30
163	Andes	2, 6, 9

数据集	样本数量	特征数量	分类数量
Wine	178	14	3
Breast	569	30	2
Ionosphere	351	34	2
Splice	3 175	60	3
Semeion	1 593	256	10

数据集	算法	F得分	准确率	召回率	运行耗时/s
Alarm	FSNMB	0.57±0.07	0.44±0.08	0.79±0.06	0.01±0.01
	IAMB	0.22±0.00^*	1.00±0.00	0.13±0.00	0.00±0.00
	HITON-MB	0.53±0.07	0.36±0.07	0.98±0.05	0.13±0.11
	MMMB	0.40±0.02^*	0.25±0.02	0.98±0.05	2.48±0.44
	STMB	0.36±0.00^*	0.22±0.00	1.00±0.00	0.57±0.35
Hepar2	FSNMB	0.43±0.10	0.34±0.08	0.61±0.16	0.01±0.01
	IAMB	0.07±0.02^*	0.90±0.30	0.04±0.01	0.00±0.00
	HITON-MB	0.38±0.13^*	0.46±0.15	0.33±0.12	0.01±0.01
	MMMB	0.52±0.05	0.42±0.04	0.67±0.07	0.72±0.15
	STMB	0.53±0.00^*	0.36±0.00	1.00±0.00	0.94±0.40
Win95pts	FSNMB	0.33±0.01	0.75±0.02	0.21±0.01	0.01±0.00
	IAMB	0.00±0.01^*	0.02±0.14	0.00±0.00	0.00±0.00
	HITON-MB	0.12±0.01^*	0.67±0.05	0.07±0.02	0.01±0.00
	MMMB	0.12±0.01^*	0.51±0.07	0.07±0.00	0.01±0.00
	STMB	0.32±0.01	0.28±0.01	0.37±0.02	0.01±0.00
Pathfinder	FSNMB	0.66±0.04	1.00±0.00	0.50±0.05	4.03±1.38
	IAMB	0.00±0.00^*	0.00±0.00	0.00±0.00	0.00±0.00
	HITON-MB	0.00±0.00^*	0.00±0.00	0.00±0.00	0.00±0.00
	MMMB	1.00±0.00^*	0.99±0.00	1.00±0.00	67.57±0.30
	STMB	-	-	-	-
Andes	FSNMB	0.34±0.07	0.30±0.06	0.41±0.11	0.04±0.02
	IAMB	0.14±0.05^*	0.65±0.24	0.08±0.03	0.01±0.00
	HITON-MB	0.26±0.08^*	0.49±0.14	0.18±0.06	0.01±0.00
	MMMB	0.23±0.07^*	0.44±0.13	0.16±0.05	0.02±0.00
	STMB	0.27±0.08	0.19±0.06	0.46±0.17	0.01±0.01

数据集	算法	F得分	准确率	召回率	运行耗时/s
Alarm	FSNMB	0.95±0.06	0.96±0.06	0.94±0.09	0.00±0.00
	IAMB	0.55±0.00^*	1.00±0.00	0.38±0.00	0.00±0.00
	HITON-MB	0.94±0.06	0.95±0.06	0.93±0.09	0.01±0.00
	MMMB	0.94±0.06	0.95±0.06	0.93±0.09	0.01±0.00
	STMB	0.58±0.08^*	0.41±0.08	0.99±0.04	0.01±0.00
Hepar2	FSNMB	0.47±0.08	0.93±0.09	0.32±0.07	0.01±0.00
	IAMB	0.27±0.03^*	0.90±0.11	0.16±0.02	0.01±0.00
	HITON-MB	0.33±0.07^*	0.96±0.09	0.20±0.05	0.01±0.00
	MMMB	0.32±0.07^*	0.96±0.09	0.20±0.05	0.01±0.00
	STMB	0.47±0.11	0.61±0.11	0.40±0.12	0.02±0.01
Win95pts	FSNMB	0.47±0.00	1.00±0.02	0.31±0.00	0.01±0.00
	IAMB	0.24±0.01^*	0.80±0.01	0.14±0.00	0.01±0.00
	HITON-MB	0.32±0.01^*	0.75±0.00	0.21±0.02	0.02±0.01
	MMMB	0.33±0.03^*	0.86±0.02	0.21±0.04	0.01±0.01
	STMB	0.45±0.05	0.55±0.05	0.38±0.04	0.02±0.01
Pathfinder	FSNMB	0.70±0.02	1.00±0.00	0.53±0.02	3.95±0.63
	IAMB	0.00±0.00^*	0.00±0.00	0.00±0.00	0.00±0.00
	HITON-MB	0.00±0.00^*	0.00±0.00	0.00±0.00	0.00±0.00
	MMMB	1.00±0.00^*	0.99±0.00	1.00±0.00	370.90±84.60
	STMB	-	-	-	-
Andes	FSNMB	0.75±0.05	0.94±0.07	0.63±0.06	0.03±0.01
	IAMB	0.45±0.03^*	0.98±0.06	0.29±0.02	0.02±0.00
	HITON-MB	0.74±0.05	0.92±0.06	0.62±0.07	0.04±0.01
	MMMB	0.75±0.07	0.90±0.08	0.65±0.09	0.04±0.01
	STMB	0.37±0.04^*	0.24±0.03	0.77±0.08	0.10±0.03