一种通过节点序寻优进行贝叶斯网络结构学习的算法

刘彬; 王海羽; 孙美婷; 刘浩然; 刘永记; 张春兰

doi:10.11999/JEIT170675

一种通过节点序寻优进行贝叶斯网络结构学习的算法

doi: 10.11999/JEIT170675

基金项目:

国家自然科学基金(51641609)

计量
- 文章访问数: 1073
- HTML全文浏览量: 138
- PDF下载量: 124
- 被引次数: 0
出版历程
- 收稿日期: 2017-07-07
- 修回日期: 2017-11-29
- 刊出日期: 2018-05-19

Learning Bayesian Network Structure from Node Ordering Searching Optimal

Funds:

The National Natural Science Foundation of China (51641609)

摘要

摘要: 针对K2算法过度依赖节点序，遗传算法节点序寻优效率差的问题，该文提出一种直接对节点序进行评分搜索的贝叶斯结构学习算法。该算法以K2算法为基础，首先通过计算支撑树权重矩阵，构建能够定量评价节点序的适应度函数。然后通过提出混合交叉策略和孤立节点处理机制，同时利用动态学习因子和倒置变异策略，提升遗传算法节点序寻优的性能。最后将得到的节点序作为K2算法的先验知识得到最优贝叶斯网络结构。仿真结果表明，该方法解决了K2算法依赖先验知识的问题，相比于其它优化算法，评分值平均增加了13.11%。
- 贝叶斯网络结构 /
- 节点序搜索 /
- 节点序适应度函数 /
- K2算法
Abstract: The performance of the K2 algorithm depends on node ordering heavily, and the genetic algorithm can not find the node ordering effectively. For these problems, a new Bayesian structure learning algorithm, named NOK2 (Node Ordering searching for K2 algorithm), is proposed to solve the Bayesian structure learning problem by searching node ordering directly. According to the requirements of K2 algorithm based on prior knowledge and the weight matrix of spanning tree, the fitness function for quantitative evaluation of node ordering is established. The genetic algorithm is redesigned by a new method combines the dynamic learning constants, the hybrid crossover strategy, the inverted mutation strategy and the isolated node processing, so that the algorithm can find the node order of the highest fitness value, and this node sequence is taken as a prior knowledge of the K2 algorithm to obtain the optimal Bayesian network structure. Compared with other optimization algorithms, experimental results indicate that the NOK2 algorithm can significantly increase nearly 13.11% in the scoring metric values.
- Bayesian network structure /
- Node ordering search /
- Fitness function of node sequence /
- K2 algorithm

HTML全文

参考文献(26)

刘广怡, 李鸥, 宋涛, 等. 基于贝叶斯网络的无线传感网高效数据传输方法[J]. 电子与信息学报, 2016, 38(6): 1362-1367. doi: 10.11999/JEIT151027.

TIEN I and KIUREGHIAN A D. Algorithms for Bayesian network modeling and reliability assessment of infrastructure systems[J]. Reliability Engineering System Safety, 2016, 156: 134-147. doi: 10.1016/j.ress.2016.07.022.

LIU Guangyi, LI Ou, SONG Tao, et al. Energy-efficiency data transmission method in WSN based on Bayesian network[J]. Journal of Electronics Information Technology, 2016, 38(6): 1362-1367. doi: 10.11999/JEIT151027.

QIU H, WEI Z, LIU Y, et al. A Bayesian network meta- analysis of three different surgical procedures for the treatment of humeral shaft fractures[J]. Medicine, 2016, 95(51): e5464. doi: 10.1097/MD.0000000000005464.

邓歆, 孟洛明. 基于贝叶斯网络的通信网告警相关性和故障诊断模型[J]. 电子与信息学报, 2007, 29(5): 1182-1186. doi: 10.3724/SP.J.1146.2005.01290.

DENG Xin and MENG Luoming. Bayesian networks based alarm correlation and fault diagnosis in communication networks[J]. Journal of Electronics Information Technology, 2007, 29(5): 1182-1186. doi: 10.3724 /SP.J.1146.2005.01290.

CHICKERING D M. Learning Bayesian networks is NP- complete[J]. Networks, 1996, 112(2): 121-130. doi: 10.1007/ 978-1-4612-2404-4_12.

CARRIGER J F, MARTIN T M, and BARRON M G. A Bayesian network model for predicting aquatic toxicity mode of action using two dimensional theoretical molecular descriptors[J]. Aquatic Toxicology, 2016, 180: 11-24. doi: 10.1016/j.aquatox.2016.09.006.

ROH M C and LEE S W. Human gesture recognition using a simplified dynamic Bayesian network[J]. Multimedia Systems, 2015, 21(6): 557-568. doi: 10.1007/s00530-014-0414-9.

CHEN X W, ANANTHA G, and LIN X. Improving Bayesian network structure learning with mutual information based node ordering in the K2 algorithm[J]. IEEE Transactions on Knowledge Data Engineering, 2007, 20(5): 628-640. doi: 10.1109/TKDE.2007.190732.

SONG K and KIM D W. An efficient node ordering method using the conditional frequency for the K2 algorithm[J]. Pattern Recognition Letters, 2014, 40(4): 80-87. doi: 10.1016/ j.patrec.2013.12.021.

刘浩然, 孙美婷, 李雷, 等. 基于蚁群节点寻优的贝叶斯网络结构算法研究[J]. 仪器仪表报, 2017, 38(1): 143-150. doi: 10.3969/j.issn.0254-3087.2017.01.019.

LIU Haoran, SUN Meiting, LI Lei, et al. Bayesian network structure learning algorithm based on ant colony optimization search optimal node ordering[J]. Chinese Journal of Scientific Instrument, 2017, 38(1): 143-150. doi: 10.3969/j.issn.0254-3087.2017.01.019.

KRUSKAL J B. On the shortest spanning subtree of a graph and the traveling salesman problem[J]. Proceedings of the American Mathematical Society, 1956, 7(1): 48-50. doi: 10.2307/2033241.

HU R S. A hybrid PSO-GA algorithm for job shop scheduling in machine tool production[J]. International Journal of Production Research, 2015, 53(19): 1-27. doi: 10.1080/ 00207543.2014.994714.

KPPPMAN R and WANG S. Mutual information based labelling and comparing clusters[J]. Scientometrics, 2017, 111(2): 1157-1167. doi: 10.1007/s11192-017-2305-2.

COOPER G F and HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data[J] Machine Learning, 1992, 9(4): 309-347. doi: 10.1007/BF00994110.

LIN S and KERNIGHAN B W. An effective heuristic algorithm for the TSP[J]. Operations Research, 1973, 21(2): 498-516. doi: 10.1287/opre.21.2.498.

刘广怡, 李鸥, 张大龙. 一种通过结构边界进行贝叶斯网络学习的算法[J].电子与信息学报, 2015, 37(4): 894-899. doi: 10.11999/JEIT140786.

LIU Guangyi, LI Ou, and ZHANG Dalong. Learning Bayesian network from structure boundaries[J]. Journal of Electronics Information Technology, 2015, 37(4): 894-899. doi: 10.11999/JEIT140786.

SCHWARZ G. Estimating dimension of a model[J]. Annals of Statistics, 1978, 6(2): 461-464. doi: 10.1214/aos/1176344136.

BEINLICH I A, SUERMONDT H J, CHAVEZ R M, et al. The ALARM monitoring mystem: A case study with two probabilistic inference techniques for belief networks[J]. Lecture Notes in Medical Informatics, 1989, 38: 247-256. doi: 10.1007/978-3-642-93437-7_28.

MAJUMDAR J and BHUNIA A K. Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times[J]. Journal of Computational Applied Mathematics, 2011, 235(9): 3063-3078. doi: 10.1016 /j.carm.2010.12.027.

TSAMARDINOS I, BROWN L E, and ALIFERIS C F. The max-min hill-climbing Bayesian network structure learning algorithm[J]. Machine Learning, 2006, 65(1): 31-78. doi: 10.1007/s10994-006-6889-7.

LARRAAGAL P, POZA M, YURRAMENDI Y, et al. Structure learning of bayesian networks by genetic algorithms: A performance analysis of control parameters[J]. IEEE Transactions on Pattern Analysis Machine Intelligence, 1996, 18(9): 912-926. doi: 10.1109/34.537345.

NIE S, CAMPOS C P D, and JI Q. Efficient learning of Bayesian networks with bounded tree-width[J]. International Journal of Approximate Reasoning, 2016, 80: 412-427. doi: 10.1016/j.ijar.2016.07.002.

施引文献

资源附件(0)

访问统计