第1期 李冰寒，等：利用互信息学习贝叶斯网络结构 ·71 次数明显减少，从而收敛速度更快，而且最优结构具 更好的求解质量，并且算法的计算复杂度得到了明 有较高的BIC得分.由此可知，改进算法能够获得 显的改进 表1不同容量下2种算法的实验结果 Table 1 Experimental results of the two algorithms on different sample capacities 样本容量 算法 Sc/10' C西 Wos Wcs N 改进算法 -4.4715 31 12 3 4 19 1 4000 贪婪算法 -5.9053 31 12 3 4 19 12 改进算法 -6.4895 32 10 3 16 1 6000 贪婪算法 -8.8311 12 19 12 改进算法 -8.5825 32 10 3 6 1 8000 贪婪算法 -11.7370 31 12 3 19 12 改进算法 -10.7290 32 10 3 3 16 1 10000 贪婪算法 -14.7050 31 12 3 4 19 12 5结束语 background knowledge[C]//Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence.San 树是极为简单又极为重要的一类图，而最大支 Francisco,USA:Morgan Kaufmann,1995:403-410. 撑树是图论中的一类非常简单的网络最优化问题. [7]BROMBERG F,MARGARITIS D,HONAVAR V.Efficient Markov network structure discovery using independence tests 结合支撑树的性质，本文提出了一个新的构想：将网 [J].Joural of Artificial Intelligence Research,2009,35 络结构中边上的权定义为节点间的互信息，从而有 (1):449485. 效地将图论和互信息知识结合起来.改进算法与原 [8]MILAN S,JIRI V.A reconstruction algorithm for the essen- 始贪婪算法相比具有更好的求解质量，并且收敛速 tial graph[J].Intemational Journal of Approximate Reason 度有明显改进，对于提高大多数智能算法如蚁群算 ing,2009,50:385-413. 法、免疫算法的收敛速度有很大帮助，因为改进算法 [9]冀俊忠，张鸿勋，胡仁兵，等.一种基于独立性测试和蚁 可用于对这些智能算法进行局部优化，并且对在等 群优化的贝叶斯网学习算法[J].自动化学报，2009,35 价类空间上搜索最优贝叶斯网络结构具有重要的研 (3):281-288. 究意义， JI Junzhong,ZHANG Hongxun,HU Renbing,et al.A Bayesian network learning algorithm based on independence 参考文献： test and ant colony optimization[J].Acta Automatica Sini- ca,2009,35(3):281-288. [1]HANSEN JF.The clinical diagnosis of ischaemic heart dis- [10]PEDRO C P,ANDEAS N,MATHAUS D,et al.Using a ease due to coronary artery disease[J].Danish Medical local discovery ant algorithm for Bayesian network structure Bulletin,1980,27:280-286. learning[J].Transactions on Evolutionary Computation, [2]WOLBRECHT E.AMBROSIO B D.PASSCH B.et al. 2009,13(4):767-779. Monitoring and diagnosis of a multi-stage manufacturing [11 CHEN Xuewen,GOPALAKRISHNA A,LIN Xiaotong. process using Bayesian networks[J].Artificial Intelligence Improving Bayesian network structure learning with mutual for Engineering Design,Analysis Manufacturing,2000, information-based node ordering in the k2 algorithm[J]. 14(1):5367. IEEE Transactions on Knowledge and Data Engineering, [3]BEISER J A,RIGDON S E.Bayes prediction for the num- 2008,20:1-13. ber of failures of a repairable system[J].IEEE Transactions [12]LEVINE J,DUCATELLE F.Ant colony optimization and on Reliability,1997,46(2):320-326, local search for bin packing and cutting stock problems [4]PEARL J.Graphical models for probabilistic and causal rea- [J].Joumal of the Operational Research Society,2004, soning[M]//TUCKER A B.The computer science and en- 55(7):705-716. gineering handbook.Boca Raton,USA:CRC Press,1997: [13]LOBONA B,AFIF M,FAIEZ G,et al.Imporving algo- 697-714. rithms for structure leaming in Bayesian networks using a [5]SCHACHTER R D.Probabilistic inference and influence di- new implicit score J].Expert System with Applixation, agrams[J].Operations Research,1988,36(4):589-605. 2010,37:5470-5475. [6]MEEK C.Causal inference and causal explanation with [14]TSAMARDINOS I,BROWN L E,ALIFERIS C F.The