论文部分内容阅读
贝叶斯网(Bayesian Network, BN)是联合概率分布的一种图形化表示,由于具有结构清晰,语义明确等特点,因此成为处理不确定性知识表示和推理的一种重要理论模型。贝叶斯网在机器学习、医疗诊断、金融分析等领域有着广泛的应用,并已经取得了较大的成功。但仅由专家构建贝叶斯网通常十分困难,有时甚至是不可能的。因此,从数据中快速、准确地学习贝叶斯网络结构具有重要的理论意义和应用价值。本文在研究国内外现有算法的基础上,针对其中的一些贝叶斯网结构学习算法的不足,以K2网络结构评分为测度,提出了几种改进方法。主要工作包括三个部分:首先,针对目前学习算法参数较多,结构复杂的不足,将禁忌搜索(Tabu Search)应用到贝叶斯网结构学习当中,提出了一种基于禁忌搜索的贝叶斯网结构学习算法。新算法首先利用加边、减边、逆向边三个算子产生当前解的邻域,然后将禁忌表和蔑视准则结合使用来引导和限制搜索过程,两步骤迭代进行,最后达到全局最优解或近似最优解。与其他算法相比,新算法结构简单、参数少,易于实现和应用,同时求解质量也有一定的提高。其次,针对蚁群优化学习贝叶斯网结构算法ACO-B的不足,提出了基于独立性测试和蚁群优化的结构学习的改进算法I-ACO-B。新算法首先利用0阶独立性测试来限制侯选结构的搜索空间,避免了蚁群的一些不必要的搜索,然后融合解的全局评分增益和节点间局部的互信息,给出了启发能力更强的启发函数来引导随机搜索,实验结果表明,新算法能更有效地处理大规模数据,且大幅度提升了学习速度。最后,针对数据不完备情况下贝叶斯网算法学习精度不高的问题,将EM(Expectation Maximization)算法与I-ACO-B算法相结合,提出了能够直接从不完备数据中学习贝叶斯网结构的新算法EACO-B。首先随机初始化未观察到的数据,得到完整的数据集,并利用蚁群算法学习得到初始网络结构;然后进行迭代学习,在每次迭代中根据当前最好的贝叶斯网结构,利用EM估计和随机的采样插入对数据进行完备化,在完备数据下,利用改进的蚁群优化过程使结构不断进化,直到获得全局最优的解。实验结果表明,新方法能够有效地从不完备数据中学习贝叶斯网结构,且与新近的一些方法相比,具有更高的学习精度。