[1]李冰寒,高晓利,刘三阳,等.利用互信息学习贝叶斯网络结构[J].智能系统学报,2011,6(1):68-72.
LI-Binghan,GAO-Xiaoli,LIU-Sanyang,et al.Learning Bayesian network structures based on mutual information[J].CAAI Transactions on Intelligent Systems,2011,6(1):68-72.
点击复制
LI-Binghan,GAO-Xiaoli,LIU-Sanyang,et al.Learning Bayesian network structures based on mutual information[J].CAAI Transactions on Intelligent Systems,2011,6(1):68-72.
利用互信息学习贝叶斯网络结构
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
6
期数:
2011年第1期
页码:
68-72
栏目:
学术论文—智能系统
出版日期:
2011-02-25
- Title:
- Learning Bayesian network structures based on mutual information
- 文章编号:
- 1673-4785(2011)01-0068-05
- Keywords:
- Bayesian network; structure learning; mutual information; independence test; maximum spanning tree
- 分类号:
- TP181
- 文献标志码:
- A
- 摘要:
- 由数据构造贝叶斯网络结构是NP难问题,因此提出了一种基于互信息的改进算法.该算法根据互信息构造初始框架,其次利用最大支撑树算法精简初始框架,并通过条件独立测试添加方向,最后利用贪婪算法得到最优网络结构.数值实验表明,改进算法无论是在BIC的得分值,还是在结构的误差上都有一定的改善,并且在迭代次数、运行时间上均有明显降低,能较快地确定出与数据匹配程度最高的网络结构.
- Abstract:
- Constructing Bayesian network structures from data is an NPhard problem, and an improved algorithm was proposed based on mutual information. This algorithm built the initial skeleton using mutual information, refined the initial skeleton by employing the maximum spanning tree algorithm, and then oriented edges according to conditional independence tests. Finally, the optimal network structure was obtained using a greedy search. Numerical experiments show that both the BIC score and structural error made some improvements from previous results, and the number of iterations and running time was greatly reduced. Therefore the structure with highest degree of data matching was shown to be relatively faster as determined by the improved algorithm.
- 参考文献/References:
-
［1］HANSEN J F. The clinical diagnosis of ischaemic heart disease due to coronary artery disease［J］. Danish Medical Bulletin, 1980, 27: 280286.
［2］WOLBRECHT E, AMBROSIO B D, PASSCH B, et al. Monitoring and diagnosis of a multistage manufacturing process using Bayesian networks［J］. Artificial Intelligence for Engineering Design, Analysis & Manufacturing, 2000, 14(1): 5367.
［3］BEISER J A, RIGDON S E. Bayes prediction for the number of failures of a repairable system［J］. IEEE Transactions on Reliability, 1997, 46(2): 320326.
［4］PEARL J. Graphical models for probabilistic and causal reasoning［M］//TUCKER A B. The computer science and engineering handbook. Boca Raton, USA: CRC Press, 1997: 697714.
［5］SCHACHTER R D. Probabilistic inference and influence diagrams［J］. Operations Research, 1988, 36(4): 589605.
［6］MEEK C. Causal inference and causal explanation with background knowledge［C］//Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. San Francisco, USA: Morgan Kaufmann, 1995: 403410.
［7］BROMBERG F, MARGARITIS D, HONAVAR V. Efficient Markov network structure discovery using independence tests［J］. Journal of Artificial Intelligence Research, 2009, 35(1): 449485.
［8］MILAN S, JIRI V. A reconstruction algorithm for the essential graph［J］. International Journal of Approximate Reasoning, 2009, 50: 385413.
［9］冀俊忠,张鸿勋,胡仁兵,等.一种基于独立性测试和蚁群优化的贝叶斯网学习算法［J］.自动化学报, 2009, 35(3): 281288.
JI Junzhong, ZHANG Hongxun, HU Renbing, et al. A Bayesian network learning algorithm based on independence test and ant colony optimization［J］. Acta Automatica Sinica, 2009, 35(3): 281288.
?［10］PEDRO C P, ANDEAS N, MATHAUS D, et al. Using a local discovery ant algorithm for Bayesian network structure learning［J］. Transactions on Evolutionary Computation, 2009, 13(4): 767779.
［11］CHEN Xuewen, GOPALAKRISHNA A, LIN Xiaotong. Improving Bayesian network structure learning with mutual informationbased node ordering in the k2 algorithm［J］. IEEE Transactions on Knowledge and Data Engineering, 2008, 20: 113.
［12］LEVINE J, DUCATELLE F. Ant colony optimization and local search for bin packing and cutting stock problems［J］. Journal of the Operational Research Society, 2004, 55(7): 705716.
［13］LOBONA B, AFIF M, FAIEZ G, et al. Imporving algorithms for structure learning in Bayesian networks using a new implicit score［J］. Expert System with Applixation, 2010, 37: 54705475.
［14］TSAMARDINOS I, BROWN L E, ALIFERIS C F. The maxmin hillclimbing Bayesian network structure learning algorithm［J］. Machine Learning, 2006, 65(1): 3178.
［15］CHICKERING D M. Learning equivalence classes of Bayesian network structures［J］. Journal of Machine Learning Research, 2002(2): 445498.
［16］RICHARD E N. Learning Bayesian networks［M］. Chicago, USA: Prentice Hall, 2002: 4043.
［17］PROAKIS J. Digital communications［M］. Columbus, USA: McGrawHill, 2000: 6190.
［18］CHICKERING D M. A transformational characterization of equivalent Bayesian network structures［C］//Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. San Francisco, USA: Morgan Kaufmann, 1995: 8798.
- 相似文献/References:
-
[1]杨有龙,刘? 蔚,吴?? 艳.贝叶斯网络的非忠实性分布[J].智能系统学报,2009,4(4):335.
YANG You-long,LIU Wei,WU Yan.Unfaithful distributions with respect to Bayesian networks[J].CAAI Transactions on Intelligent Systems,2009,4():335.
[2]郭坤,王浩,姚宏亮,等.逻辑回归分析的马尔可夫毯学习算法[J].智能系统学报,2012,7(2):153.
GUO Kun,WANG Hao,YAO Hongliang,et al.An algorithm for a Markov blanket based on ?logistic regression analysis[J].CAAI Transactions on Intelligent Systems,2012,7():153.
[3]段海滨,马冠军,赵振宇.基于模糊规则和动态蚁群贝叶斯网络的无人作战飞机态势评估[J].智能系统学报,2013,8(2):119.[doi:10.3969/j.issn.1673-4785.201211031]
DUAN Haibin,MA Guanjun,ZHAO Zhenyu.UCAV situation assessment based on fuzzy rules and dynamic ant colony-Bayesian network[J].CAAI Transactions on Intelligent Systems,2013,8():119.[doi:10.3969/j.issn.1673-4785.201211031]
[4]张兴,陈昊.差分隐私的高维数据发布研究综述[J].智能系统学报,2021,16(6):989.[doi:10.11992/tis.202104023]
ZHANG Xing,CHEN Hao.A research review of high-dimensional data publishing based on a differential privacy model[J].CAAI Transactions on Intelligent Systems,2021,16():989.[doi:10.11992/tis.202104023]
[5]张平,刘三阳,朱明敏.基于人工蜂群算法的贝叶斯网络结构学习[J].智能系统学报,2014,9(3):325.[doi:10.3969/j.issn.1673-4785.201310014]
ZHANG Ping,LIU Sanyang,ZHU Mingmin.Structure learning of Bayesian networks by use of the artificial bee colony algorithm[J].CAAI Transactions on Intelligent Systems,2014,9():325.[doi:10.3969/j.issn.1673-4785.201310014]
备注/Memo
收稿日期：2010-07-13.
基金项目：国家自然科学基金资助项目(60974082).
通信作者：李冰寒.
E-mail: binghan2020@126.com.
作者简介：
李冰寒，女，1986年生，硕士研究生，主要研究方向为数据挖掘、贝叶斯网络、最优化理论，发表学术论文5篇.
高晓利，女，1983年生，硕士研究生，主要研究方向为数据挖掘、贝叶斯网络、最优化理论，发表学术论文3篇.
刘三阳，男，1959年生，教授、博士生导师、博士,国家级教学名师,曾在法国作博士后研究，西安电子科技大学理学院院长兼数学系主任、工业与应用数学研究所所长.主要研究方向为应用数学、最优化和运筹学.先后主持10余项科研项目,获得多次省部级科技进步奖，国家级优秀教学成果二等奖2次，陕西省优秀教学成果特等奖、一等奖和二等奖多次.发表学术论文300余篇，其中被SCI检索50余篇，EI检索80余篇，出版专著6部.
更新日期/Last Update:
2011-04-13