基于频繁项挖掘的贝叶斯网络结构学习算法BNSL-FIM

doi:10.11772/j.issn.1001-9081.2021060898

《计算机应用》唯一官方网站 ›› 2021, Vol. 41 ›› Issue (12): 3475-3479.DOI: 10.11772/j.issn.1001-9081.2021060898

• 第十八届中国机器学习会议(CCML 2021) • 上一篇

基于频繁项挖掘的贝叶斯网络结构学习算法BNSL-FIM

李昡熠¹^,², 周鋆¹^,²()

^1.国防科技大学系统工程学院，长沙 410073
^2.国防科技大学信息系统工程重点实验室，长沙 410073

收稿日期:2021-05-12 修回日期:2021-06-08 接受日期:2021-06-23 发布日期:2021-08-20 出版日期:2021-12-10
通讯作者: 周鋆
作者简介:李昡熠（1993—），女，江西婺源人，硕士研究生，主要研究方向：机器学习、贝叶斯网络；
基金资助:
国家自然科学基金资助项目(61703416);长沙市杰出创新青年培养计划项目(KQ2009009)

BNSL-FIM： Bayesian network structure learning algorithm based on frequent item mining

Xuanyi LI¹^,², Yun ZHOU¹^,²()

^1.College of Systems Engineering，National University of Defense Technology，Changsha Hunan 410003，China
^2.Science and Technology on Information Systems Engineering Laboratory，National University of Defense Technology，Changsha Hunan 410073，China

Received:2021-05-12 Revised:2021-06-08 Accepted:2021-06-23 Online:2021-08-20 Published:2021-12-10
Contact: Yun ZHOU
About author:LI Xuanyi， born in 1993， M. S. candidate. Her research interests include machine learning， Bayesian network.
Supported by:
the National Natural Science Foundation of China(61703416);the Training Program for Excellent Young Innovators of Changsha(KQ2009009)

摘要/Abstract

摘要：

贝叶斯网络能够表示不确定知识并进行推理计算表达，但由于实际样本数据存在噪声和大小限制以及网络空间搜索的复杂性，贝叶斯网络结构学习始终会存在一定的误差。为了提高贝叶斯网络结构学习的准确度，提出了以最大频繁项集和关联规则分析结果为先验知识的贝叶斯网络结构学习算法BNSL-FIM 。首先从数据中挖掘出最大频繁项集并对该项集进行结构学习，之后使用关联规则分析结果对其进行校正，从而确定基于频繁项挖掘和关联规则分析的先验知识。然后提出一种融合先验知识的BDeu评分算法进行贝叶斯网络结构学习。最后在6个公开标准的数据集上开展了实验，并对比引入先验/不引入先验的结构与原始网络结构的汉明距离，结果表明所提算法与未引入先验的BDeu评分算法相比显著提高了贝叶斯网络结构学习的准确度。

关键词: 贝叶斯网络, 结构学习, 关联规则分析, Apriori算法, BDeu评分

Abstract:

Bayesian networks can represent uncertain knowledge and perform inferential computational expressions， but due to the noise and size limitations of actual sample data and the complexity of network space search， Bayesian network structure learning will always have certain errors. To improve the accuracy of Bayesian network structure learning， a Bayesian network structure learning algorithm with the results of maximum frequent itemset and association rule analysis as the prior knowledge was proposed， namely BNSL-FIM （Bayesian Network Structure Learning algorithm based on Frequent Item Mining）. Firstly， the maximum frequent itemset was mined from data and the structure learning was performed on the itemset， then the association rule analysis results were used to correct it， thereby determining the prior knowledge based on frequent item mining and association rule analysis. Secondly， a Bayesian Dirichlet equivalent uniform （BDeu） scoring algorithm was proposed combining with prior knowledge for Bayesian network structure learning. Finally， experiments were carried out on 6 public standard datasets to compare the Hamming distance between the structure with/without prior and the original network structure. The results show that the proposed algorithm can effectively improve the structure learning accuracy of Bayesian network compared to the original BDue scoring algorithm.

Key words: Bayesian network, structure learning, association rule analysis, Apriori algorithm, Bayesian Dirichlet equivalent uniform (BDeu) score

中图分类号:

TP391

李昡熠, 周鋆. 基于频繁项挖掘的贝叶斯网络结构学习算法BNSL-FIM[J]. 计算机应用, 2021, 41(12): 3475-3479.

Xuanyi LI, Yun ZHOU. BNSL-FIM： Bayesian network structure learning algorithm based on frequent item mining[J]. Journal of Computer Applications, 2021, 41(12): 3475-3479.

图/表 8

参考文献 19

1	CHICKERING D M. Learning Bayesian networks is NP-complete［J］. FISHER D， LENZ H J. Learning from Data： Artificial Intelligence and Statistics V， LNS 112. New York： Springer， 1996： 121-130. 10.1007/978-1-4612-2404-4_12
2	AMIRKHANI H， RAHMATI M， LUCAS P J F， et al. Exploiting experts’ knowledge for structure learning of Bayesian networks［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2017， 39（11）：2154-2170. 10.1109/tpami.2016.2636828
3	SPIRTES P， GLYMOUR C， SCHEINES R. Causation， Prediction， and Search［M］. 2nd ed. Cambridge： MIT Press， 2001：116-120. 10.7551/mitpress/1754.001.0001
4	SCUTARI M， GRAAFLAND C E， GUTIÉRREZ， J M. Who learns better Bayesian network structures： accuracy and speed of structure learning algorithms［J］. International Journal of Approximate Reasoning， 2019， 115： 235-253. 10.1016/j.ijar.2019.10.003
5	ZHOU Y， FENTON N， ZHU C. An empirical study of Bayesian network parameter learning with monotonic influence constraints［J］. Decision Support Systems， 2016， 87：69-79. 10.1016/j.dss.2016.05.001
6	EGGELING R， VIINIKKA J， VUOKSENMAA A， et al. On structure priors for learning Bayesian networks［C］// Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics. New York： JMLR.org， 2019：1687-1695.
7	WANG Z D， GAO X G， YANG Y， et al. Learning Bayesian networks based on order graph with ancestral constraints［J］. Knowledge-Based Systems， 2020， 211： No.106515. 10.1016/j.knosys.2020.106515
8	WITTEN I H， FRANK E， HALL M A. Data Mining： Practical Machine Learning Tools and Techniques［M］. 3rd ed. Burlington， MA： Morgan Kaufmann Publishers， 2011：85-145. 10.1016/b978-0-12-374856-0.00004-3
9	肖海慧，俞奎，王浩. 融合关联规则与知识的贝叶斯网络学习算法［J］. 微电子学与计算机， 2008， 25（12）：70-72， 75. 10.3724/SP.J.1001.2008.01707
	XIAO H H， YU K， WANG H. The method of learning Bayesian networks combining association rules with knowledge［J］. Microelectronics and Computer， 2008， 25（12）：70-72， 75. 10.3724/SP.J.1001.2008.01707
10	KHARYA S， SONI S， SWARNKAR T. Weighted Bayesian association rule mining algorithm to construct Bayesian belief network［C］// Proceedings of the 2019 International Conference on Applied Machine Learning. Piscataway： IEEE， 2019：27-33. 10.1109/icaml48257.2019.00013
11	ANGELOPOULOS N， CUSSENS J. Bayesian learning of Bayesian networks with informative priors［J］. Annals of Mathematics and Artificial Intelligence， 2008， 54（1/2/3）：53-98. 10.1007/s10472-009-9133-x
12	HECKERMAN D， GEIGER D， CHICKERING D M. Learning Bayesian networks： the combination of knowledge and statistical data［J］. Machine Learning1995， 20（3）： 197-243. 10.1007/bf00994016
13	COOPER G F， HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data［J］. Machine Learning， 1992， 9（4）： 309-347. 10.1007/bf00994110
14	SUZUKI J. A construction of Bayesian networks from databases based on an MDL principle［C］// Proceedings of the 9th Conference on Uncertainty in Artificial Intelligence. Burlington， MA： Morgan Kaufmann Publishers， 1993： 266-273. 10.1016/b978-1-4832-1451-1.50037-8
15	SCANAGATTA M， DE CAMPOS C P， ZAFFALON M. Min-BDeu and max-BDeu scores for learning Bayesian networks［C］// Proceedings of the 2014 European Workshop on Probabilistic Graphical Models， LNCS8754. Cham： Springer， 2014： 426-441.
16	ZHENG X， ARAGAM B， RAVIKUMAR P， et al. DAGs with NO TEARS： continuous optimization for structure learning［C］// Proceedings of the 32nd International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2018： 9492-9503. 10.1145/3232116.3232145
17	SCUTARI M. bnlearn - an R package for Bayesian network learning and inference ［DS/OL］［2021-03-20］. . 10.18637/jss.v077.i02
18	LI X Y. BNSL-FIM［CP/OL］［2021-03-20］. .
19	KOLLER D， FRIEDMAN N. Probabilistic Graphical Models： Principles and Techniques［M］. Cambridge： MIT Press， 2009： 794-804.

节点名称	节点数	边数	节点名称	节点数	边数
Asia	8	8	Insurance	27	52
Sachs	11	17	Hailfinder	56	66
Alarm	37	46	Hepar2	70	123

节点名称	节点数	边数	节点名称	节点数	边数
Asia	8	8	Insurance	27	52
Sachs	11	17	Hailfinder	56	66
Alarm	37	46	Hepar2	70	123

关联规则	置信度	关联规则	置信度
（Either， XraY）	0.951 5	（Lung， Tub）	0.989 0
（Tub， Asia）	0.987 6	（Either， Tub）	1.000 0
（Asia， Tub）	0.989 2	（XraY， Lung）	0.997 0
（XraY， Asia）	0.987 2	（XraY， Either）	0.996 8
（Lung， Aisa）	0.986 6	（Lung， Either）	0.989 0
（Either， Asia）	0.987 3	（Either， Lung）	1.000 0
（XraY， Tub）	0.999 7

关联规则	置信度	关联规则	置信度
（Either， XraY）	0.951 5	（Lung， Tub）	0.989 0
（Tub， Asia）	0.987 6	（Either， Tub）	1.000 0
（Asia， Tub）	0.989 2	（XraY， Lung）	0.997 0
（XraY， Asia）	0.987 2	（XraY， Either）	0.996 8
（Lung， Aisa）	0.986 6	（Lung， Either）	0.989 0
（Either， Asia）	0.987 3	（Either， Lung）	1.000 0
（XraY， Tub）	0.999 7

样本大小	Asia		Sachs		Alarm		Insurance		Hailfinder		Hepar2
样本大小	BNSL-FIM	BDeu	BNSL-FIM	BDeu	BNSL-FIM	BDeu	BNSL-FIM	BDeu	BNSL-FIM	BDeu	BNSL-FIM	BDeu
100	11.1	10.8	12.1	12.4	83.0	83.9	56.2	57.3	77.9	78.9	298.2	299.4
300	12.3	12.6	7.3	7.7	70.9	71.7	46.5	47.4	59.5	63.2	226.2	226.6
500	11.3	11.8	5.8	5.9	57.5	57.6	41.1	41.4	57.4	61.5	206.4	207.4
800	8.4	10.2	6.7	7.0	55.8	56.5	48.1	48.7	56.7	61.3	183.8	183.6
1 000	7.3	9.5	6.6	7.0	51.8	52.8	44.5	46.4	57.4	61.2	168.2	167.4
3 000	5.4	10.0	6.8	7.2	47.8	47.8	35.6	35.6	62.4	66.7	130.2	130.2
5 000	4.3	9.1	5.5	5.7	43.2	43.2	39.1	40.5	56.6	63.4	101.6	101.8

基于频繁项挖掘的贝叶斯网络结构学习算法BNSL-FIM

BNSL-FIM： Bayesian network structure learning algorithm based on frequent item mining

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 19

相关文章 15

编辑推荐

Metrics

序号	汉明距离		序号	汉明距离
序号	BNSL-FIM	BDeu	序号	BNSL-FIM	BDeu
1	5	9	6	4	7
2	4	8	7	5	10
3	4	12	8	5	10
4	4	8	9	3	9
5	4	8	10	5	10

[1]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[2]	孙建强, 许少华. 基于可微神经计算机和贝叶斯网络的知识推理方法[J]. 计算机应用, 2021, 41(2): 337-342.
[3]	张榜, 朱金鑫, 徐正蓺, 刘盼, 魏建明. 基于贝叶斯网络的楼层定位算法[J]. 计算机应用, 2019, 39(8): 2468-2474.
[4]	杨洁, 李松斌, 邓浩江. 基于贝叶斯网络的压缩语音信息隐藏检测[J]. 计算机应用, 2018, 38(7): 1967-1973.
[5]	卢玲, 杨武, 刘旭, 李言. 基于实体情感演化置信网的观点检测方法[J]. 计算机应用, 2017, 37(5): 1402-1406.
[6]	邢志伟, 唐云霄, 罗谦. 基于贝叶斯网络的航班保障服务时间动态估计[J]. 计算机应用, 2017, 37(1): 299-304.
[7]	徐开勇, 龚雪容, 成茂才. 基于改进Apriori算法的审计日志关联规则挖掘[J]. 计算机应用, 2016, 36(7): 1847-1851.
[8]	杨燕霞, 冯林. 基于Hadoop平台的并行DHP数据分析方法[J]. 计算机应用, 2016, 36(12): 3280-3284.
[9]	张丽萍, 张瑞霞, 王欢, 闫盛. 基于贝叶斯网络的克隆代码有害性预测[J]. 计算机应用, 2016, 36(1): 260-265.
[10]	毛莺池, 接青, 陈豪. 河网中具有时空关系的异常事件在线检测[J]. 计算机应用, 2015, 35(11): 3106-3111.
[11]	杜元伟, 石方园, 杨娜. 基于证据理论/层次分析法的贝叶斯网络建模方法[J]. 计算机应用, 2015, 35(1): 140-146.
[12]	张春生庄丽艳. 基于Apriori的相容数据集间关联规则演绎方法[J]. 计算机应用, 2013, 33(10): 2796-2800.
[13]	赵学武刘广亮程新党冀俊忠. 基于拓扑序列和量子遗传算法的贝叶斯网结构学习[J]. 计算机应用, 2013, 33(06): 1595-1603.
[14]	曾安平. 多类关联规则生成算法[J]. 计算机应用, 2012, 32(08): 2198-2201.
[15]	史建国高晓光. 离散动态贝叶斯网络推理的编程计算算法[J]. 计算机应用, 2012, 32(07): 1943-1946.