大型复杂贝叶斯网络诊断推理的简化

大型复杂贝叶斯网络诊断推理的简化

0简化网络结构现代大型复杂系统的贝叶斯网络结构也非常复杂，因此很难判断诊断。因此在进行诊断推理前,应适当地对其网络结构进行简化。本文采用分簇优化联合树算法对贝叶斯网络结构进行简化处理及推理运算,下面介绍分簇优化联合树算法及其用于网络参数学习及诊断推理算法。1基于全要素的分簇算法用于故障诊断的贝叶斯网络的结构是非常复杂的,并且由于其结构的复杂性致使故障诊断推理也非常复杂,因此,通过贝叶斯网络结构学习,寻找一个与训练数据拟合度高且网络复杂性相对较低的网络结构成为一个非常有意义和研究价值的问题。由式可知,n个变量构成的贝叶斯网络结构的数目是指数级的,要从这些可能存在的网络结构空间中搜索出最优的网络结构也是很难的。当n=10时,需要搜索的模型个数就已经达到约为4.17*1018,可见搜索空间太大,为了缩小搜索空间,有效地找到最优解,一个较好的搜索算法就非常必要。贝叶斯网络结构的学习实际就是优化搜索的问题。基于分簇的优化搜索方法就是将问题节点划分为团簇结构。团簇结构思想最早用于物理和化学领域中对分子和原子的处理,而在近代,团簇结构在许多领域得到了广泛的应用,包括模式识别,数据分析,图像处理等。许多学者都在这方面做出了研究,旨在发现能够用于更好聚类方法的簇结构,不同的网络拓扑结构对于分簇算法都是不同的。人工智能越来越多地研究这种方法,使之成为一种较为优秀的搜索算法。基于簇的搜索方法被证实较好地用于解决TSP问题。这种方法的主要优势在于不会陷入局部最优,并且搜索时间非常短。分簇算法的基本思想是把网络结构中的节点划分为若干个簇,簇内依据某种事先约定的值进行连接,在簇与簇之间,也根据这种约定进行点与点之间的连接,这里设定一个阀值,节点间的关联程度大于这个阀值时就连接这两个节点,最终基于簇的这种搜索算法将形成一个团簇树状结构。基于簇的结构学习算法是由初始的贝叶斯网络结构经过优化搜索构造出用于诊断的树形结构。设用于该算法的阀值为θ,由当前信息得到相关节点的关联程度为θij,表示第i个节点和第j个节点的关联程度,设两个数据结构D1,D2分别存放局部网络的起始参数节点表和目标节点表,首先把网络的所有节点都放入D1表中。具体的步骤如下:步骤1:随即选取一个起始节点V1,比较与V1相关的各个节点的θ1k值,若θ1k≥0,则将V1和Vk划分到一个簇S1内,把簇S1中的节点都从D1表中移出,放入表D2中。步骤2:如果D1为空表,则转到步骤4。步骤3:在D1表中随即选取一个节点Vn,比较与Vn相关的各个节点,分两种情况:(1)若无关联节点,则将Vn单独划分到簇S2中,并将节点Vn从表D1中移出,放入表D2中,转入步骤2。(2)若有关联的节点,且关联值为θnm,若θnm≥0,则将Vn和Vm划分到一个簇S2中,把簇S2中的节点从D1表中移出,放入表D2中,转入步骤2。步骤4:在簇到S1之Sn间,观察是否簇间有相关联的节点,若相关联,且关联值θij≥θ,则将Vi与Vj相连接。该算法的最终目的是搜索出一个较为简单的网络结构,减少网络推理的复杂度,使学习后的网络结构能够使用精确推理算法来实现推理,得出一个较为准确的结果。搜索的过程如图1所示。从图1可以看出,在经过分簇搜索之后,网络结构(d)比网络结构(a)有了一定程度的简化。有效的贝叶斯网络推理算法是贝叶斯网络的重要内容,也是其应用的前提。大型复杂的故障诊断系统,所建立的贝叶斯网络模型也具有非常复杂的结构,为了降低贝叶斯网络的推理复杂度,使其更容易应用于解决实际问题,一般的推理算法都是在简化网络结构上进行研究的。下面来分析经过分簇结构优化算法后的网络推理。2分簇优化联合树算法分簇优化联合树算法实现对贝叶斯网络的诊断推理。分簇优化联合树算法是分簇优化算法与联合树算法的结合,其流程图如图2所示。分簇优化已在前文介绍,下面介绍流程图中其余步骤。2.1贝叶斯网络已扩展为联合树将贝叶斯网络B转化为联合树,分为四步:建立B的Moral图;三角化Moral图;确定所有的团(Cliques);建立联合树。(1)b-mora图像简历Moral图的过程就是找出每个节点的父节点,并将他们用无相边两两相连,同时将所有有向边改为无向边。(2)三角流域图在Moral图中添加一些无向边,使图中每个大于或等于4的环中,都存在一条边连接两个非相邻节点。这就完成了对Moral图的三角化。(3)所有群体close的确定对Moral图三角化的目的就是找到构成联合树的所有团。团是Moral图三角化后最大的全连通子图,团中每对不同的节点都有边相连。(4)联合树t利用得到的团,添加一些边和分隔节点就可构造一棵联合树T。联合树T要满足:树中任意两个团C,C′在连接它们的路径上的所有团节点必须包含变量C∩C′。2.2联合树参数的指定将贝叶斯网络转化为联合树后,就要对联合树的所有节点指定参数,即对联合树进行初始化。下面的算法实现了对满足条件的联合树参数的指定。若联合树中的团Ci由X1,X2,…,Xr,r个节点组成,每一个节点有Sr个状态,则共有个状态组合。i代表Ci的分布函数,ij代表图Ci第j个状态组合的分布函数。具体步骤是:for一个随机变量V找到包含V的家庭的团Ci;fori=1,…,n(n为团的数目)初始化Φij,使Φij=1;2.3全局传递,全局互动对联合树进行初始化后,要在联合树上进行消息传递。通过个团节点之间的消息传递,可以是联合树达到全局一致,即达到稳态。如图3所示是团节点间一次消息传递的过程。从节点Ci到Cj的一次消息传递过程包括以下几步:(1)产生消息:(2)吸收信息,更新团结点的分布函数:(3)更新分隔节点的分布函数:2.4任意随机变量v当一个联合树通过消息传递满足全局一致性后,即可计算任意随机变量V的概率分布。找到任意一个包含变量V的团节点C,通过可计算出变量V的分布。2.5合树的一致性若有新的证据加入,重复证据收集和证据扩散的过程,直到得到全局一致的联合树为止。当联合树再次满足全局一致性时,对任意的团C有:C=P(C,e),(e表示加入的证据)。要计算假设的变量V的概率分布,首先找到任意一个包含变量V团结点C,,再根据条件概率公式,求出变量V的概率分布3简化贝叶斯网络推理算法有效的贝叶斯网络推理算法是贝叶斯网络的重要内容,也是其应用的前提。大型复杂的故障诊断系统,所建立的贝叶斯网络模型也具有非常复杂的结构,为了降低贝叶斯网络