普适地理信息服务匹配：实现联结树推理算法

在介绍联结树(Junction Tree，JT)推理算法之前，有必要引入三个重要的概念定义：

定义4.2　联结树JT＝(C，S)。可见联结树是一种由贝叶斯网络转换而来的串集C和任意相邻串集之间的公共边集S组成的二元组。给定任意两个相邻串集Ci和Cj，Sij是它们的相邻公共边，它们满足：

(1)Ci与Cj之间的边集上所有串均包含Ci与Cj的交集；

(2)Sij＝Ci∩Cj

定义4.3　概率势(Baysian Probalility Potential，BPP)它是一组有关串和边的变量的联合概率分布函数。

定义4.4　贝叶斯网络二次结构(Baysian Second Structure，BSS)它是一个关于联结树和概率势的二元组，BSS＝(JT，BPP)。

基于联结树的贝叶斯网络的推理算法思想如下：由于任意贝叶斯网络推理是一个NP完全难题，因此考虑将贝叶斯网络转换成一种中间的二次结构BSS，其中利用联结树表达贝叶斯网络的结构信息，而概率势表达条件依赖关系，并以联结树的精确推理代替贝叶斯网络的直接推理。

联结树推理算法详细分为三个步骤(见图4-4)：

(1)原贝叶斯网络向联结树的转化；

(2)联结树初始化；

(3)加入证据进行推理。

(www.xing528.com)

图4-4　联结树推理算法流程

联结树的初始化是指对构建好的联结树节点赋值并且利用消息传递机制使得整个联结树结构和依赖关系稳定。接下来重点介绍贝叶斯网络向联结树的转化过程，又可以分为以下几个步骤：

(1)建立Moral图。找出每一个节点的父节点，并将它们之间的有向边转换成无向边。这样得到的图称为贝叶斯网络的Moral图，如图4-5(a)所示。

(2)三角化Moral图。对于Moral图中每一个大于3的串，添加无向边将其非相邻边相连接，三角化以后的Moral图中的串的边数均为3，如图4-5(c)所示。

(3)找到Moral图中的串，其中串是Moral图中最大的全连通子图。

(4)构建联结树，在找到的串中添加无向边构造联结树JT，如图4-5(d)所示。

图4-5　贝叶斯网络的Moral图

联结树算法是当前比较流行和最为广泛应用的贝叶斯网络推理算法，它最大的特点是充分利用了贝叶斯网络的条件独立性。但是由于它是一种精确性的推理算法，当贝叶斯网络规模较大的时候，计算复杂性会成几何级数增加。联结树算法的计算复杂性主要与联结树的深度(Depth)和宽度(Width)相关。

因此，本书结合空间上下文的特点，主要依据构建贝叶斯网络的前提3，即当两个空间上下文相差的层数越过阈值D时，忽略两个空间上下文之间的推理关系，提出一种简化的联结树推理算法——即部分联结树推理算法。