高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于V-结构&对数似然函数定向与禁忌爬山的贝叶斯网络结构算法

刘浩然 王念太 王毅 张力悦 苏昭玉 刘文 赵旭丹

刘浩然, 王念太, 王毅, 张力悦, 苏昭玉, 刘文, 赵旭丹. 基于V-结构&对数似然函数定向与禁忌爬山的贝叶斯网络结构算法[J]. 电子与信息学报, 2021, 43(11): 3272-3281. doi: 10.11999/JEIT210032
引用本文: 刘浩然, 王念太, 王毅, 张力悦, 苏昭玉, 刘文, 赵旭丹. 基于V-结构&对数似然函数定向与禁忌爬山的贝叶斯网络结构算法[J]. 电子与信息学报, 2021, 43(11): 3272-3281. doi: 10.11999/JEIT210032
Haoran LIU, Niantai WANG, Yi WANG, Liyue ZHANG, Zhaoyu SU, Wen LIU, Xudan ZHAO. Bayesian Network Structure Algorithm Based on V-structure & Log-Likelihood Orientation and Tabu Hill Climbing[J]. Journal of Electronics & Information Technology, 2021, 43(11): 3272-3281. doi: 10.11999/JEIT210032
Citation: Haoran LIU, Niantai WANG, Yi WANG, Liyue ZHANG, Zhaoyu SU, Wen LIU, Xudan ZHAO. Bayesian Network Structure Algorithm Based on V-structure & Log-Likelihood Orientation and Tabu Hill Climbing[J]. Journal of Electronics & Information Technology, 2021, 43(11): 3272-3281. doi: 10.11999/JEIT210032

基于V-结构&对数似然函数定向与禁忌爬山的贝叶斯网络结构算法

doi: 10.11999/JEIT210032
基金项目: 国家重点研发计划(2019YFB1707301),河北省人才工程培养资助项目(A201903005)
详细信息
    作者简介:

    刘浩然:男,1980年生,教授,博士生导师,研究方向为无线传感器网络、工业故障检测及预测

    王念太:男,1996年生,硕士生,研究方向为贝叶斯网络、工业故障检测及预测

    王毅:男,1996年生,硕士生,研究方向为贝叶斯网络、工业故障检测及预测

    张力悦:男,1994年生,博士生,研究方向为贝叶斯网络、工业故障检测及预测

    苏昭玉:女,1994年生,硕士生,研究方向为贝叶斯网络、工业故障检测及预测

    刘文:女,1966年生,学士,研究方向为机床工艺参数感知与预测

    赵旭丹:女,1981年生,硕士,研究方向为财务会计理论与方法

    通讯作者:

    刘浩然 liu.haoran@ysu.edu.cn

  • 中图分类号: TP18

Bayesian Network Structure Algorithm Based on V-structure & Log-Likelihood Orientation and Tabu Hill Climbing

Funds: The National Key R&D Program of China (2019YFB1707301), The Hebei Talent Engineering Training Support Project (A201903005)
  • 摘要: 针对爬山算法搜索空间过大和易陷入局部最优的问题,该文提出基于V-结构&对数似然函数定向与禁忌爬山的贝叶斯网络结构算法(VTH)。该算法利用定向最大支撑树约束搜索空间,在最大支撑树定向过程中,提出V-结构与对数似然函数(VLL)结合的定向策略;在评分搜索过程中,提出禁忌爬山(VTH)评分搜索策略,该策略将禁忌表清空机制与爬山搜索的局部择优准则结合,在提高全局寻优能力的同时也能保证搜索效率。该算法与其他算法在Asia, Car, Child和Alarm 4种标准网络中进行仿真实验,对比汉明距离、F1值、平衡评分函数(BSF)值、运行时间4个指标,验证了该算法的有效性。
  • 图  1  最大支撑树中3节点连接关系

    图  2  ep修改CG得到候选结构

    图  3  VTH算法流程图

    图  4  HC与THC在4种网络中寻优过程对比

    图  5  4个网络中不同算法运行时间结果

    图  6  4个网络中不同算法汉明距离结果

    表  1  4种网络中VLL策略和CRAE策略定向结果

    网络数据量VLL策略CRAE策略
    TFacc(%)TFacc(%)
    Asia10005.560.5890.583.582.5658.33
    50006.020.4792.813.622.8755.82
    100006.270.4793.073.713.0255.12
    Car10007.930.9689.255.873.0266.00
    50008.180.8290.866.002.9866.83
    100008.110.8990.126.003.0066.67
    Child100013.784.9873.4614.314.4476.30
    500013.935.0773.3314.204.8074.74
    1000013.985.0273.5714.184.8274.62
    Alarm100033.490.4498.69 23.4010.5368.96
    500034.020100.0022.8411.1867.15
    1000034.000100.0022.6911.3166.73
    下载: 导出CSV

    表  2  对比算法介绍

    算法描述
    HC算法经典爬山算法
    Tabu算法利用禁忌表提高爬山全局寻优能力的禁忌搜索算法
    MMHC算法依赖分析与爬山算法结合的经典混合算法
    CHC算法通过动态限制提高爬山效率的高效算法
    FastCHC算法对CHC算法的改进算法
    SHC算法标准节点序定向最大支撑树与简化爬山结合的有效算法
    SaiyanH算法新近提出的爬山算法和禁忌搜索结合的混合算法
    下载: 导出CSV

    表  4  Car网络中不同算法F1值和BSF值结果

    数据量对比项HCMMHCTabuSHCCHCFastCHCSaiyanHVTH
    1000F10.63830.83170.69620.76900.64560.64950.78520.8810
    BSF0.63570.75890.67420.76860.64100.64300.73800.8203
    5000F10.71330.90420.76730.81330.71610.71790.82990.9609
    BSF0.69890.83330.73450.81180.70060.70200.77850.8958
    10000F10.73460.89820.78440.84620.73460.73460.84430.9617
    BSF0.71640.82770.74850.84260.71640.71640.79110.8919
    下载: 导出CSV

    表  5  Child网络中不同算法F1值和BSF值结果

    数据量对比项HCMMHCTabuSHCCHCFastCHCSaiyanHVTH
    1000F10.70540.83670.76440.8930 0.70680.69990.84670.8554
    BSF0.61930.72500.66490.7736 0.62090.61520.73080.7386
    5000F10.76660.91670.82910.96980.76540.76360.91870.9715
    BSF0.72730.84220.77760.90140.72730.72510.85260.9061
    10000F10.80000.92670.85140.9717 0.80160.80210.90610.9366
    BSF0.76070.85690.80060.9030 0.76210.76260.84660.8775
    下载: 导出CSV

    表  3  Asia网络中不同算法F1值和BSF值结果

    数据量对比项HCMMHCTabuSHCCHCFastCHCSaiyanHVTH
    1000F10.65790.74500.68620.83690.64240.64010.63190.8788
    BSF0.49640.56960.51920.67300.48410.48230.47820.6950
    5000F10.59000.85490.64810.87390.59230.59230.76870.9118
    BSF0.45120.68120.49660.71370.45300.45300.59900.7325
    10000F10.65260.87480.67210.90460.65260.65260.79740.9335
    BSF0.50690.70520.52260.74680.50690.50690.63000.7605
    下载: 导出CSV

    表  6  Alarm网络中不同算法F1值和BSF值结果

    数据量对比项HCMMHCTabuSHCCHCFastCHCSaiyanHVTH
    1000F10.51280.77670.53690.79510.50680.50950.76160.8090
    BSF0.56800.76440.58070.74570.56420.56580.74130.7545
    5000F10.54630.86900.55890.88660.54850.54850.78910.9165
    BSF0.64130.84740.64850.84880.64250.64210.79550.8755
    10000F10.53130.82680.54840.90930.53080.53290.79720.9514
    BSF0.64020.81830.65050.88560.63990.63810.80720.9174
    下载: 导出CSV
  • [1] 李硕豪, 张军. 贝叶斯网络结构学习综述[J]. 计算机应用研究, 2015, 32(3): 641–646. doi: 10.3969/j.issn.1001-3695.2015.03.001

    LI Shuohao and ZHANG Jun. Review of Bayesian networks structure learning[J]. Application Research of Computers, 2015, 32(3): 641–646. doi: 10.3969/j.issn.1001-3695.2015.03.001
    [2] ZHAO Xuan, PENG Benhong, ELAHI E, et al. Optimization of Chinese coal-fired power plants for cleaner production using Bayesian network[J]. Journal of Cleaner Production, 2020, 273: 122837. doi: 10.1016/j.jclepro.2020.122837
    [3] MCLACHLAN S, DUBE K, HITMAN G A, et al. Bayesian networks in healthcare: Distribution by medical condition[J]. Artificial Intelligence in Medicine, 2020, 107: 101912. doi: 10.1016/j.artmed.2020.101912
    [4] CARRIGER J F and BARRON M G. A Bayesian network approach to refining ecological risk assessments: Mercury and the Florida panther (Puma concolor coryi)[J]. Ecological Modelling, 2020, 418: 108911. doi: 10.1016/j.ecolmodel.2019.108911
    [5] ANDERSON B. Using Bayesian networks to perform reject inference[J]. Expert Systems with Applications, 2019, 137: 349–356. doi: 10.1016/j.eswa.2019.07.011
    [6] SCANAGATTA M, SALMERÓN A, and STELLA F. A survey on Bayesian network structure learning from data[J]. Progress in Artificial Intelligence, 2019, 8(4): 425–439. doi: 10.1007/s13748-019-00194-y
    [7] HECKERMAN D, GEIGER D, and CHICKERING D M. Learning Bayesian networks: The combination of knowledge and statistical data[J]. Machine Learning, 1995, 20(3): 197–243. doi: 10.1007/BF00994016
    [8] 曹杰. 贝叶斯网络结构学习与应用研究[D].[博士论文], 中国科学技术大学, 2017.

    CAO Jie. Bayesian network structure learning and application[D].[Ph.D. dissertation], University of Science and Technology of China, 2017.
    [9] 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
    [10] 冀俊忠, 张鸿勋, 胡仁兵, 等. 基于禁忌搜索的贝叶斯网结构学习算法[J]. 北京工业大学学报, 2011, 37(8): 1274–1280.

    JI Junzhong, ZHANG Hongxun, HU Renbing, et al. A Tabu-search based Bayesian network structure learning algorithm[J]. Journal of Beijing University of Technology, 2011, 37(8): 1274–1280.
    [11] GÁMEZ J A, MATEO J L, and PUERTA J M. Learning Bayesian networks by hill climbing: Efficient methods based on progressive restriction of the neighborhood[J]. Data Mining and Knowledge Discovery, 2011, 22(1-2): 106–148. doi: 10.1007/s10618-010-0178-6
    [12] GÁMEZ J A, MATEO J L, and PUERTA J M. One iteration CHC algorithm for learning Bayesian networks: An effective and efficient algorithm for high dimensional problems[J]. Progress in Artificial Intelligence, 2012, 1(4): 329–346. doi: 10.1007/s13748-012-0033-7
    [13] ARIAS J, GÁMEZ J A, and PUERTA J M. Structural learning of Bayesian networks via constrained hill climbing algorithms: Adjusting trade-off between efficiency and accuracy[J]. International Journal of Intelligent Systems, 2015, 30(3): 292–325. doi: 10.1002/int.21701
    [14] 刘浩然, 吕晓贺, 李轩, 等. 基于Bayesian改进算法的回转窑故障诊断模型研究[J]. 仪器仪表学报, 2015, 36(7): 1554–1561. doi: 10.3969/j.issn.0254-3087.2015.07.014

    LIU Haoran, LÜ Xiaohe, LI Xuan, et al. A study on the fault diagnosis model of rotary kiln based on an improved algorithm of Bayesian[J]. Chinese Journal of Scientific Instrument, 2015, 36(7): 1554–1561. doi: 10.3969/j.issn.0254-3087.2015.07.014
    [15] 刘彬, 刘永记, 刘浩然, 等. 基于改进遗传爬山算法的篦冷机熟料换热二次风温故障诊断[J]. 计量学报, 2018, 39(5): 651–658. doi: 10.3969/j.issn.1000-1158.2018.05.10

    LIU Bin, LIU Yongji, LIU Haoran, et al. Fault diagnosis of secondary air temperature of grate cooler cement clinker heat transfer based on improved genetic hill climbing algorithm[J]. Acta Metrologica Sinica, 2018, 39(5): 651–658. doi: 10.3969/j.issn.1000-1158.2018.05.10
    [16] CONSTANTINOU A C. Learning Bayesian networks that enable full propagation of evidence[J]. IEEE Access, 2020, 8: 124845–124856. doi: 10.1109/ACCESS.2020.3006472
    [17] CHEN Guangjie and GE Zhiqiang. Robust Bayesian networks for low-quality data modeling and process monitoring applications[J]. Control Engineering Practice, 2020, 97: 104344. doi: 10.1016/j.conengprac.2020.104344
    [18] YANG Jing, GUO Xiaoxue, AN Ning, et al. Streaming feature-based causal structure learning algorithm with symmetrical uncertainty[J]. Information Sciences, 2018, 467: 708–724. doi: 10.1016/j.ins.2018.04.076
    [19] PRIM R C. Shortest connection networks and some generalizations[J]. The Bell System Technical Journal, 1957, 36(6): 1389–1401. doi: 10.1002/j.1538-7305.1957.tb01515.x
    [20] DAI Jingguo, REN Jia, and DU Wencai. Decomposition-based Bayesian network structure learning algorithm using local topology information[J]. Knowledge-Based Systems, 2020, 195: 105602. doi: 10.1016/j.knosys.2020.105602
    [21] BEHJATI S and BEIGY H. Improved K2 algorithm for Bayesian network structure learning[J]. Engineering Applications of Artificial Intelligence, 2020, 91: 103617. doi: 10.1016/j.engappai.2020.103617
    [22] ZHAO Jianjun and HO S S. Improving Bayesian network local structure learning via data-driven symmetry correction methods[J]. International Journal of Approximate Reasoning, 2019, 107: 101–121. doi: 10.1016/j.ijar.2019.02.004
    [23] CONSTANTINOU A C. The importance of temporal information in Bayesian network structure learning[J]. Expert Systems with Applications, 2021, 164: 113814. doi: 10.1016/j.eswa.2020.113814
    [24] JIANG Jinke, WANG Juyun, YU Hua, et al. Poison identification based on Bayesian network: A novel improvement on K2 algorithm via Markov Blanket[C]. The 4th International Conference on Advances in Swarm Intelligence, Harbin, China, 2013: 173–182.
  • 加载中
图(6) / 表(6)
计量
  • 文章访问数:  1265
  • HTML全文浏览量:  604
  • PDF下载量:  97
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-01-11
  • 修回日期:  2021-04-21
  • 网络出版日期:  2021-05-07
  • 刊出日期:  2021-11-23

目录

    /

    返回文章
    返回