一种增强贝叶斯网络结构学习的自动变量序调整算法

doi:10.13232/j.cnki.jnju.2021.02.010

南京大学学报(自然科学版) ›› 2021, Vol. 57 ›› Issue (2): 255–261.doi: 10.13232/j.cnki.jnju.2021.02.010

一种增强贝叶斯网络结构学习的自动变量序调整算法

许国强¹, 余长州², 王林¹, 周春蕾¹, 高阳²()

^1.江苏方天电力技术有限公司，南京，211102
^2.南京大学计算机科学与技术系，南京，210023

收稿日期:2020-10-09 出版日期:2021-03-30 发布日期:2021-03-23
通讯作者: 高阳 E-mail:gaoy@nju.edu.cn
作者简介:E⁃mail：gaoy@nju.edu.cn
基金资助:
江苏方天电力技术有限公司科技项目(KJ201919)

An automatic variable order adjustment algorithm to enhance the structure learning of Bayesian networks

Guoqiang Xu¹, Changzhou Yu², Lin Wang¹, Chunlei Zhou¹, Yang Gao²()

^1.Jiangsu Frontier Electric Technology Co. Ltd. ，Nanjing，211102, China
^2.Department of Computer Science and Technology，Nanjing University，Nanjing，210023, China

Received:2020-10-09 Online:2021-03-30 Published:2021-03-23
Contact: Yang Gao E-mail:gaoy@nju.edu.cn

摘要/Abstract

摘要：

现有的混合结构学习算法受制于变量的邻居集，导致混合结构学习算法在约束学习阶段，若变量的邻居集没有包含真实结构的节点，该节点将再也不会被考虑.为改进这一问题，通过探索贝叶斯网络结构与节点影响度间存在的可能性关系，设计基于节点影响度的变量序调整方法并将调整后的变量序应用于网络结构学习.调整后的变量序在减少搜索空间的同时，也改善了传统约束空间过于依赖变量邻居集的问题，进而提升网络结构的学习质量.实验结果表明，该算法能有效地提升现有混合结构学习算法的精度，同时也验证了从节点影响度的角度去探索贝叶斯网络结构图的可行性.

关键词: 贝叶斯网络结构, 节点影响度, 混合结构学习算法, 变量序, 约束空间

Abstract:

The existing hybrid structure learning algorithm is subject to the neighbor set of variables，which results in the hybrid structure learning algorithm in the constraint learning stage. If the neighbor set of variables does not contain nodes of real structure，the nodes will not be considered. To improve this problem，this paper explores the Bayesian network structure and the possibility of relation between node effect degree，designs a variable order adjustment method based on node effect degree，and applies the adjusted variable order to network structure learning. The adjusted variable order not only reduces the search space，but also improves the problem that the traditional constraint space relies too much on the neighbor set of variables，thus improving the learning quality of the network structure. Experimental results show that the proposed algorithm can effectively improve the accuracy of existing hybrid structure learning algorithms，and also verify the feasibility of exploring Bayesian network structure diagram from the point of node effect degree.

Key words: Bayesian network structure, node effect degree, hybrid structure learning algorithm, variable ordering, constraint space

中图分类号:

TP181

许国强, 余长州, 王林, 周春蕾, 高阳. 一种增强贝叶斯网络结构学习的自动变量序调整算法[J]. 南京大学学报(自然科学版), 2021, 57(2): 255–261.

Guoqiang Xu, Changzhou Yu, Lin Wang, Chunlei Zhou, Yang Gao. An automatic variable order adjustment algorithm to enhance the structure learning of Bayesian networks[J]. Journal of Nanjing University(Natural Sciences), 2021, 57(2): 255–261.

图/表 5

图1

图2

表1

本文算法的主要步骤及结果"

$ρ$	$ρ n e w$	依附点(有序)	说明
$1,2, 4,5, 6,7, 8,3, 9,10$	1,2,6,7,8,10	2,6,7,8,10
$1,2, 4,5, 6,7, 8,3, 9,10$	1,2,6,7,5,8,10,9	1,5,7,8,9
$1,2, 4,5, 6,7, 8,3, 9,10$	1,2,6,7,5,8,4,10,9,3	5,7,8,3	$ρ n e w$ 长度为10退出

表1

表2

表3

参考文献 22

1	周志华. 机器学习. 北京：清华大学出版社，2016，425.
2	Scutari M，Graafland C E，Gutiérrez J M. Who learns better Bayesian network structures：constraint?based，score?based or hybrid algorithms?2018，arXiv:1805.11908v1.
3	Tsamardinos l，Brown L E，Aliferis C F，et al. The Max?Min Hill?Climbing Bayesian network structure learning algorithm. Machine Learning，2006，65(1)：31-78.
4	Han W J，Sang H Y，Ma X，et al. Sensing statistical primary network patterns via Bayesian network structure learning. IEEE Transactions on Vehicular Technology，2017，66(4)：3143-3157.
5	Yang J，An N，Alterovitz G. A partial correlation statistic structure learning algorithm under linear structural equation models. IEEE Transactions on Knowledge and Data Engineering，2016，28(10)：2552-2565.
6	李硕豪，张军. 贝叶斯网络结构学习综述. 计算机应用研究，2015，32(3)：641-646.
	Li S H，Zhang J. Review of Bayesian networks structure learning. Application Research of Computers，2015，32(3)：641-646.
7	王越，谭暑秋，刘亚辉. 基于互信息的贝叶斯网络结构学习算法. 计算机工程，2011，37(7)：62-64.
	Wang Y，Tan S Q，Liu Y H. Bayesian network structural learning algorithm based on mutual information. Computer Engineering，2011，37(7)：62-64.
8	曹杰. 贝叶斯网络结构学习与应用研究. 博士学位论文. 合肥：中国科学技术大学，2017.
	Cao J. Bayesian network structure learning and application. Ph.D. Dissertation. Hefei：University of Science and Technology of China，2017.
9	范敏，黄席樾，石为人等. 一种改进的贝叶斯网络结构学习算法. 系统仿真学报，2008，20(17)：4613-4617.
	Fan M，Huang X Y，Shi W R，et al. Improved Bayesian networks structure learning algorithm. Journal of System Simulation，2008，20(17)：4613-4617.
10	朱明敏. 贝叶斯网络结构学习与推理研究. 博士学位论文. 西安：西安电子科技大学，2013.
	Zhu M M. Research on structural learning and inference in Bayesian networks. Ph.D. Dissertation. Xi'an：Xidian University，2013.
11	胡学钢，胡春玲. 一种基于依赖分析的贝叶斯网络结构学习算法. 模式识别与人工智能，2006，19(4)：445-449.
	Hu X G，Hu C L. A dependency analysis based algorithm for learning Bayesian networks. Pattern Recognition and Artificial Intelligence，2006，19(4)：445-449.
12	金焱，胡云安，张瑾等. 互信息与爬山法相结合的贝叶斯网络结构学习. 计算机应用与软件，2012，29(9)：122-125.
	Jin Y，Hu Y A，Zhang J，et al. Bayesian network structure learning combining mutual information with hill climbing algorithm. Computer Applications and Software，2012，29(9)：122-125.
13	刘明辉，王磊，党林阁等. 非确定先验信息的贝叶斯网结构学习方法. 计算机工程，2010，36(5)：165-167.
	Liu M H，Wang L，Dang L G，et al. Structure learning method of Bayesian network with uncertain prior information. Computer Engineering，2010，36(5)：165-167.
14	Spirtes P，Glymour C，Scheines R. Causation，prediction and search. The 2nd Edsition. Cambridge：The MIT Press，2000，568.
15	Spirtes P，Glymour C. An algorithm for fast recovery of sparse causal graphs. Social Science Computer Review，1991，9(1)：62-72.
16	Cheng J，Greiner R，Kelly J，et al. Learning Bayesian networks from data：an information?theory based approach. Artificial Intelligence，2002，137(1-2)：43-90.
17	张盈侠. 基于约束的贝叶斯网络结构学习算法研究. 博士学位论文. 西安. 电子科技大学，2014. (Zhang Y X. Research on constraint?based algorithms for Bayesian network structure learning. Ph.D. Dissertation. Xi'an：Xidian University，2014.)
18	De Campos L M，Castellano J G. Bayesian network learning algorithms using structural restrictions. International Journal of Approximate Reasoning，2007，45(2)：233-254.
19	Cooper G F，Herskovits E. A Bayesian method for the induction of probabilistic networks from data. Machine Learning，1992，9(4)：309-347.
20	Mahjoub M A，Bouzaiene A，Ghanmy N. Tutorial and selected approaches on parameter learning in Bayesian network with incomplete data∥Wang J，Yen G G，Polycarpou M M. Advances in neural networks. Springer Berlin Heidelberg，2012：478-488.
21	綦小龙，高阳，王皓等. 一种可度量的贝叶斯网络结构学习方法. 计算机研究与发展，2018，55(8)：1717-1725.
	Qi X L，Gao Y，Wang H，et al. A measurable Bayesian network structure learning method. Journal of Computer Research and Development，2018，55(8)：1717-1725.
22	Marco S. Bnlearn：a R package for Bayesian network learning and inference. http:∥www.bnlearn.com/bnrepository,2017-09-06.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Dataset	Sample size	#vars	#edges
Child	5000	20	25
Child3	5000	60	79
Child5	5000	100	126
Child10	5000	200	257
hailfinder	5000	56	66
sachs	5000	11	17

Dataset	Edge Type	MMHC	MMPC? autoVOA?K2	BNS^vo? autoVOA?K2
Child	Missing	1.00	0.00	0.00
	Additional	1.00	0.00	0.00
	Reverse	1.00	0.00	0.00
Child3	Missing	4.00	1.00	1.00
	Additional	3.00	0.63	1.00
	Reverse	7.33	1.00	1.00
Child5	Missing	6.20	1.80	1.00
	Additional	6.00	1.60	1.00
	Reverse	7.50	1.25	1.00
Child10	Missing	3.65	1.76	1.00
	Additional	3.28	1.67	1.00
	Reverse	4.75	1.58	1.00
hailfinder	Missing	1.00	1.04	1.00
	Additional	0.87	1.12	1.00
	Reverse	0.00	1.80	1.00
sachs	Missing	2.00	1.40	1.00
	Additional	4.4	1.80	1.00
	Reverse	0.8	1.00	1.00

[1]	周小亮, 吴东洋, 曹磊, 王玉鹏, 业宁. 基于修剪树的优化聚类中心算法[J]. 南京大学学报(自然科学版), 2021, 57(2): 167-176.
[2]	汪敏,赵飞,闵帆. 储层预测的代价敏感主动学习算法[J]. 南京大学学报(自然科学版), 2020, 56(4): 561-569.
[3]	朱荀,刘国强,丁华平,沈庆宏. 一种通过支持向量机对交通拥堵情况进行分类的方法[J]. 南京大学学报(自然科学版), 2020, 56(2): 278-283.
[4]	王卫星,刘兆伟,石敬华. 基于时间敏感滑动窗口的CP⁃nets结构学习[J]. 南京大学学报(自然科学版), 2020, 56(2): 175-185.
[5]	信统昌,刘兆伟. 基于贝叶斯⁃遗传算法的多值无环CP⁃nets学习[J]. 南京大学学报(自然科学版), 2020, 56(1): 74-84.
[6]	郑文萍,刘韶倩,穆俊芳. 一种基于相对熵的随机游走相似性度量模型[J]. 南京大学学报(自然科学版), 2019, 55(6): 984-999.
[7]	黄华娟,韦修喜. 基于自适应调节极大熵的孪生支持向量回归机[J]. 南京大学学报(自然科学版), 2019, 55(6): 1030-1039.
[8]	刘　素, 刘惊雷. 基于特征选择的CP－nets结构学习[J]. 南京大学学报(自然科学版), 2019, 55(1): 14-28.
[9]	贾海宁, 王士同. 面向重尾噪声的模糊规则模型[J]. 南京大学学报(自然科学版), 2019, 55(1): 61-72.
[10]	曲昭伟, 杨凯翔, 王晓茹, 李百威. 基于语义行为和社交关联的好友推荐模型[J]. 南京大学学报(自然科学版), 2018, 54(6): 1124-1131.

一种增强贝叶斯网络结构学习的自动变量序调整算法

An automatic variable order adjustment algorithm to enhance the structure learning of Bayesian networks

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 22

相关文章 10

Metrics

本文评价

推荐阅读 0