论文部分内容阅读
贝叶斯网(Bayesian Network, BN)作为一种被广泛使用于不确定性知识表示与推理的概率图模型,在数据与知识工程领域扮演着重要的角色。BN学习是利用BN进行不确定性知识表示与推理的前提与基础,而从数据中学习BN则可以有效地避免和修正因为专家知识的主观性与片面性所带来的问题。随着Web应用的普及和信息采集技术的进步,人们生产与收集的数据呈现出大规模、分布式存储、动态变化等特点,而传统的BN学习方法已无法适应海量数据这些特点的要求。在这一背景下,数据密集型计算的提出,特别是MapReduce编程模型的提出,为海量数据的管理与分析处理提供了良好的技术支撑,使得从海量数据中学习并维护BN成为可能。针对海量数据大规模与分布式存储的特点,本文基于MapReduce对传统BN学习中的打分搜索方法进行分析研究后对其中关键步骤进行扩展,提出数据密集型计算的BN并行学习方法。BN的并行学习分为2个阶段：参数学习阶段和结构学习阶段。在参数学习阶段,我们通过map和reduce过程并行对海量样本数据进行分析统计,从而获得为结构学习所需的参数。在结构学习阶段,利用参数学习阶段所得参数对各节点的候选结果并行进行评分,选取得分最优的候选结构作为对应节点的局部最优候选结构。最终各节点的局部最优结构合并得到全局最优结构,即从海量数据中学习得到BN。针对海量数据动态变化的特点,本文基于MapReduce对传统BN增量维护方法进行扩展,提出数据密集型计算的BN增量维护方法。我们通过map和reduce过程对新数据并行进行读取,获取新数据对应BN的相关概率参数,并在概率参数的基础上计算新数据与BN中各节点的不一致程度。接着,根据各节点与新数据之间不一致程度,选取需要重新学习的节点采用BN并行学习方法进行重新学习,获得局部BN结构。最后,我们将局部BN结构与初始BN进行合并,得到增量维护的BN。本文所提出方法均在Hadoop平台上进行正确性与执行效率方面的实验,实现结果表明我们的方法可以正确高效地从海量数据中学习获得BN。