一種通過節(jié)點序?qū)?yōu)進行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學習的算法
doi: 10.11999/JEIT170675
基金項目:
國家自然科學基金(51641609)
Learning Bayesian Network Structure from Node Ordering Searching Optimal
Funds:
The National Natural Science Foundation of China (51641609)
-
摘要: 針對K2算法過度依賴節(jié)點序,遺傳算法節(jié)點序?qū)?yōu)效率差的問題,該文提出一種直接對節(jié)點序進行評分搜索的貝葉斯結(jié)構(gòu)學習算法。該算法以K2算法為基礎(chǔ),首先通過計算支撐樹權(quán)重矩陣,構(gòu)建能夠定量評價節(jié)點序的適應(yīng)度函數(shù)。然后通過提出混合交叉策略和孤立節(jié)點處理機制,同時利用動態(tài)學習因子和倒置變異策略,提升遺傳算法節(jié)點序?qū)?yōu)的性能。最后將得到的節(jié)點序作為K2算法的先驗知識得到最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。仿真結(jié)果表明,該方法解決了K2算法依賴先驗知識的問題,相比于其它優(yōu)化算法,評分值平均增加了13.11%。
-
關(guān)鍵詞:
- 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu) /
- 節(jié)點序搜索 /
- 節(jié)點序適應(yīng)度函數(shù) /
- 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. -
劉廣怡, 李鷗, 宋濤, 等. 基于貝葉斯網(wǎng)絡(luò)的無線傳感網(wǎng)高效數(shù)據(jù)傳輸方法[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. 鄧歆, 孟洛明. 基于貝葉斯網(wǎng)絡(luò)的通信網(wǎng)告警相關(guān)性和故障診斷模型[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. 劉浩然, 孫美婷, 李雷, 等. 基于蟻群節(jié)點尋優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)算法研究[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. 劉廣怡, 李鷗, 張大龍. 一種通過結(jié)構(gòu)邊界進行貝葉斯網(wǎng)絡(luò)學習的算法[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. -
計量
- 文章訪問數(shù): 1196
- HTML全文瀏覽量: 161
- PDF下載量: 124
- 被引次數(shù): 0