面向决策的影响图结点聚集方法

发布时间：2020-04-10 05:49

【摘要】： 决策是小到个人,大到国家、社会都不可避免的事情。决策分析作为解决决策问题的基本观点,成为人们研究的热点,决策的科学性也越来越受到社会的重视。作为一种决策分析的有效工具,影响图被广泛用于决策支持、预测分析、知识发现等领域中。然而,求解影响图的算法,其计算量相对于结点数是指数级的,传统的影响图由于其精确的表示及决策机制,使其不能较好地满足问题域中变量过多的实际应用。同时,许多应用中,用户并不一定需要知道各个领域内部琐碎的联系,而只需要知道各个领域之间的联系。本文针对前述问题的实际需要,在贝叶斯网结点聚集的基础上,提出影响图结点聚集的算法,使得影响图中,属于同一个领域的多个结点,聚集成为一个新的结点,从而简化影响图的结构,并通过实验验证了该方法的有效性。本文的主要工作和创新之处总结如下: 由于影响图包含不同类型的结点,且结点之间的关系也不是单纯的概率关系,因此,根据结点类型的不同,在不破坏影响图内部结构的基础上,将影响图分解为两个部分,即概率网络部分(可以等价于一个贝叶斯网)和效用网络部分,构成两个新图,然后分别对这两个图进行聚集。对于概率网络部分,我们用贝叶斯网的结点聚集算法来实现其结点的聚集。对于效用网络部分,讨论了效用结点之间的条件效用独立关系,提出效用结点的聚集算法以及效用表参数的更新。基于影响图的图形特性,根据结点之间的父子关系,将两个聚集后的新图合并成一个新的影响图。
【图文】：

贝叶斯网

影响图的基本概念和相关结论，作为本文后续章节的背景知识。2.1 贝叶斯网简介贝叶斯网络（BN）[15]是一种图形化的模型，能够直观地表示一组变量之间的依赖关系。一个贝叶斯网络包括了一个结构模型和与之相关的一组条件概率分布函数。结构模型是一个有向无环图，其中结点表示问题域中的随机变量，有向边则表示变量之间的依赖关系，其依赖程度用条件概率进行定量表示[3,15,16,17,18,19,20,21]，图 2.1 给出了一个简单的贝叶斯网示例。马尔可夫网和贝叶斯网是分别用无向图和有向无环图来表示条件独立关系的两种图形模型。下面，我们首先介绍关于图论和概率论的基础知识，然后介绍马尔可夫网和贝叶斯网的基本概念和性质[3,15],最后介绍链图模型，作为本文研究概率网络部分聚集的基础。

影响图,矿藏,影响图,储量

机变量的不同状态的概率。每一个效用结点都有一张效用分配表（也称为效用矩阵）与之对应，它描述当前状态下采取不同行动的收益情况。一个效用结点 A 的效用矩阵就是该效用结点的父亲结点集的函数，用 U(Pa(A))表示。决策结点是决策者可控制的行为描述。下面是一个简单的影响图。例 2.3 一家采矿公司对某矿藏的开采决策及收益情况如下：自然结点 O 代表矿藏的蕴藏情况，已知储量高的概率是 0.2，用 o1表示；储量一般的概率是 0.5用 o2表示；储量低的概率是 0.3，用 o3表示。决策结点 D 代表开采决策，d1表示开采，d2表示不开采。效用结点 U 表示在某种矿藏储量情况下，选择开采或不开采所获得的收益情况，它与一张效用函数表 U(O,D)相关联。如果决定开采，收益受矿藏储量的影响很大，如果储量高，，收益是 100；储量一般，收益是 30；储量低，收益是-50。如果不开采，收益为 0。那么矿藏开采决策的影响图如图 2.4 所示。
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2010
【分类号】：N945.25

【参考文献】