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

• 作 者: 龚彩云
• 机 构: 云南大学
• 出 处: 云南大学
• 发表日期: 2010年期
• 关键词: 影响图 贝叶斯网 效用独立 结点聚集算法 图形特性

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