《计算机应用研究》|Application Research of Computers

基于最大信息系数的贝叶斯网络结构学习算法

Bayesian network structure learning algorithm based on maximal information coefficient

免费全文下载 (已被下载 次)  
获取PDF全文
作者 魏中强,徐宏喆,李文,桂小林
机构 西安交通大学 电子与信息工程学院,西安 710049
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2014)11-3261-05
DOI 10.3969/j.issn.1001-3695.2014.11.015
摘要 为了得到正确的节点次序,构造接近最优的贝叶斯网络结构,利用最大信息系数与条件独立性测试相结合的方法,提出了一种新的贝叶斯网络结构学习算法(MICVO)。该算法利用最大信息系数衡量变量之间的依赖关系,生成初始的无向图,引入惩罚因子δ减少图中冗余边的数量,并将这个无向图分解成多个子结构,确定图中边的方向,最后生成正确的节点次序作为K2算法的输入学习网络结构。在两个基准网络Asia和Alarm中进行实验验证,结果表明基于最大信息系数的贝叶斯网络结构学习算法可以得到接近最优的节点次序,学习到的网络结构与数据的拟合程度更好,分类准确性更高。
关键词 贝叶斯网络;结构学习;节点次序;最大信息系数;条件独立性测试
基金项目 国家自然科学基金资助项目(61172090)
本文URL http://www.arocmag.com/article/01-2014-11-015.html
英文标题 Bayesian network structure learning algorithm based on maximal information coefficient
作者英文名 WEI Zhong-qiang, XU Hong-zhe, LI Wen, GUI Xiao-lin
机构英文名 School of Electronics & Information Engineering, Xi'an Jiaotong University, Xi'an 710049, China
英文摘要 In order to obtain the correct node ordering, this paper presented a new Bayesian network structure learning algorithm (MICVO) which used the method based on maximal information coefficient combining with conditional independence test. Firstly, it generated an initial undirected graph through measuring dependency between variables using maximal information coefficient, and introduced a penalty factor δ to reduce the number of redundant edges. Then divided this undirected graph into multiple sub-structures to determine the direction of edges in the graph, and finally the initial ordering of nodes obtained was as input of K2 algorithm to construct the network structure. Experimental results over two benchmark networks Asia and Alarm prove that the Bayesian network structure learning algorithm based on maximal information coefficient can obtain bear optimal ordering of nodes, network structure with better degree of data matching, and higher classification accuracy.
英文关键词 Bayesian network(BN); structure learning; node ordering; maximal information coefficient(MIC); conditional independence test
参考文献 查看稿件参考文献
  [1] DALY R, SHEN Qiang, AITKEN S. Learning Bayesian networks:approaches and issues[J] . The Knowledge Engineering Review, 2011, 26(2):99-157.
[2] FRIEDMAN N, KOLLER D. Being Bayesian about network structure:a Bayesian approach to structure discovery in Bayesian networks[J] . Machine Learning, 2003, 50(1-2):95-125.
[3] KWISTHOUT J. Most probable explanations in Bayesian networks:complexity and tractability[J] . International Journal of Approximate Reasoning, 2011, 52(9):1452-1469.
[4] CAMPOS L M D E. Independency relationships and learning algorithms for singly connected networks[J] . Journal of Experimental & Theoretical Artificial Intelligence, 1998, 10(4):511-549.
[5] De CAMPOS C P, JI Qiang. Efficient structure learning of Bayesian networks using constraints[J] . Journal of Machine Learning Research, 2011, 12(3):663-689.
[6] De CAMPOS L M, HUETE J F. A new approach for learning belief networks using independence criteria[J] . International Journal of Approximate Reasoning, 2000, 24(1):11-37.
[7] COOPER G F, HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data[J] . Machine Learning, 1992, 9(4):309-347.
[8] TEYSSIER M, KOLLER D. Ordering-based search:a simple and effective algorithm for learning Bayesian networks[C] //Proc of the 21st Conference on Uncertainty in AI. 2005:584-590.
[9] HECKERMAN D, GEIGER D, CHICKERING D M. Learning Bayesian networks:the combination of knowledge and statistical data[J] . Machine Learning, 1995, 20(3):197-243.
[10] ZHANG Ying-hua, ZHANG Wen-sheng, XIE Yuan. Improved heuristic equivalent search algorithm based on maximal information coefficient for Bayesian network structure learning[J] . Neurocomputing, 2013, 117(6):186-195.
[11] TSAMARDINOS I, BROWN L E, ALIFERIS C F. The max-min hill-climbing Bayesian network structure learning algorithm[J] . Machine Learning, 2006, 65(1):31-78.
[12] 冀俊忠, 张鸿勋, 胡仁兵, 等. 基于独立性测试和蚁群优化的贝叶斯网结构学习算法[J] . 自动化学报, 2009, 35(3):281-288.
[13] 朱明敏, 刘三阳, 杨有龙. 基于混合方式的贝叶斯网络等价类学习算法[J] . 电子学报, 2013, 41(1):98-104.
[14] CHICKERING D M. Optimal structure identification with greedy search[J] . Journal of Machine Learning Research, 2003, 3(2002):507-554.
[15] BUNTINE W. A guide to the literature on learning probabilistic networks from data[J] . IEEE Trans on Knowledge and Data Engineering, 1996, 8(2):195-210.
[16] SCHMIDT M, NICULESCU-MIZIL A, MURPHY K. Learning graphical model structure using L1-regularization paths[C] //Proc of the 22nd AAAI Conference on Artificial Intelligence. 2007:1278-1283.
[17] LARRAAGA P, KARSHENAS H, BIELZA C, et al. A review on evolutionary algorithms in Bayesian network learning and inference tasks[J] . Information Sciences, 2013, 233:109-125.
[18] CHEN Xue-wen, ANANTHA G, LIN Xiao-tong. Improving Bayesian network structure learning with mutual information-based node ordering in the K2 algorithm[J] . IEEE Trans on Knowledge and Data Engineering, 2008, 20(5):628-640.
[19] 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.
[20] JIANG Jin-ke, WANG Ju-yun, YU Hua, et al. Poison identification based on Bayesian network:a novel improvement on K2 algorithm via Markov blanket[C] //Advances in Swarm Intelligence. Berlin:Springer, 2013:173-182.
收稿日期 2013/11/8
修回日期 2013/12/20
页码 3261-3265
中图分类号 TP301.6
文献标志码 A