冲突证据合成规则的研究

中北大学 2008 届本科毕业论文第 1 页 共 47 页1 引言1.1 课题的目的与意义随着科学技术的飞速发展，无论在军事上，还是在非军事领域，数据融合技术已经成为全球的研究热点之一，因为使用信息融合技术合成后的信息比单一的信息进行判决和决策更可靠、更准确 1,2,3。从军事应用的角度，数据融合被定义为：把来自多个传感器和信息源的数据和信息加以校准、状态估计、身份识别，以及对战场态势和威胁的综合评估 4，如：目标检测、识别、跟踪以及态势评估与决策分析等；从非军事应用的角度来说，数据融合是对多个传感器和信息源所提供的关于某一环境特征的不完整信息加以综合，以形成相对完整、一致的感知描述，从而实现更加准确的识别和判断功能 5 ，如：机器人导航、故障诊断、数字图象处理、字体识别、决策分析等。D-S 证据理论源于六十年代 Dempster1在多值映射方面的工作，在其原始的表达形式中，把证据的信任函数与概率的上下值相联系，从而提供了一个构造不确定推理模型的一般框架。到七十年代中期，Shafer 2对 Dempster 的理论进行了扩充，在此基础上形成了处理不确定信息的证据理论。其建立了命题和集合之间的一一对应，把命题的不确定性问题转化为集合的不确定性问题，满足比概率论弱的情况，实际是对概率论的扩展 3。其通过引入信任函数，很好地表示了“不确定性” 、 “未知不明”等认知方面的重要概念，成为一种很有前途的证据推理方法。在许多应用领域中 4,5,6，如目标识别、军事指挥、医学诊断、故障诊断和投资决策等，人们越来越多地考虑信息的融合问题，即如何利用来自多个信息源的信息，多个专家的意见、多方面的因素来完成问题的求解。利用信息融合技术进行判决或决策的好处是显而易见的，因为合成后的信息会比单一信息更可靠、更准确、更及时。然而问题在于我们所能获得的信息常常是不确定的，造成这种不确定性的原因，既有客观因素又有人为因素。信息具有的随机性、模糊性会造成其不确定性，同时，信息可能是错误的、不相关的、不完备的、不可靠的、近似的也会造成其不确定性，这些都是导致信息具有不确定性的客观因素；另外，人为因素也会造成信息的不确定性，如人的感情因素、认知心理上的差异等等。因中北大学 2008 届本科毕业论文第 2 页 共 47 页此，信息融合技术不可避免地要解决如何处理不确定性信息的问题。D-S 证据理论作为一种不确定性的推理方法，为不确定信息的表达和合成提供了自然而强有力的方法，因而在不确定推理和信息融合中获得了广泛的应用 7,8,9。但是在证据理论的实际应用中，常常会面临各种不确定的冲突信息，而当参与合成的证据间具有较大的不一致性或冲突时，D-S 证据合成方法就不能使用或得出与事实相悖的结果。然而在许多证据推理的数据融合系统（如军事指挥系统、机器人系统等）中是不允许这种情况出现的，否则会造成系统的错误决策。这一局限性成为制约D-S 证据理论进一步推广的主要问题，所以基于冲突证据的合成方法的研究和改进是一个亟待解决的问题。虽然有许多学者对冲突证据的合成方法进行了研究，但文献报道的相关研究只是各个侧面的研究，还没有形成系统化的冲突证据合成的理论体系 10。本课题的目的是通过对 D-S 证据理论以及冲突证据合成方法的研究，形成既能有效合成冲突的证据，又保持原证据理论优越性系统化的冲突证据合成规则，且具有良好的适用性。进一步为 D-S 证据理论的研究提供新的内容和方法，提高使用冲突证据进行推理决策系统的工作能力，所以本课题的研究具有重要的理论价值和学术意义。1.2 国内外研究现状为了解决冲突证据的合成问题，不少学者对其进行了研究，并提出了许多解决方法。第一种方法是对 D-S 合成规则的改进，从根本上来说主要存在两类方法：一类是在证据完全可靠为前提的条件下，Smets 提出的可传递置信模型 11。他认为导致冲突证据合成结果不合理的主要原因是由于在未知环境中不可能得到一个有穷且完备的识别框架 ，因此必然存在着一些人们无法判断其真假的未知命题，而冲突部分正是由这些未知命题造成的。将冲突部分分配给空集，即可能的新命题，这就是 Smets 提出的解决高冲突证据的可传递置信模型方法。该改进方法保持了原方法的优点，但是在实际中证据完全可靠的条件不易满足。一类是在证据不完全可靠为前提的条件下，Yager 12提出了取消正则化过程，其基本思想是：既然人们并不真正知道冲突部分的情况，那么就让它分配在 中，而不象原来那样分配在 中的子集上。此方法虽然能合成高冲突的证据，但是该中北大学 2008 届本科毕业论文第 3 页 共 47 页方法过于保守，认为冲突的证据无法提供任何有用的信息，对证据的扰动过于敏感，大大增加了推理的不确定性，且在证据多于两个时，无法获得合理的结果，且具有一票否决的缺点。平均法 13将合成规则化为简单的平均运算，它没有区分冲突信息和无冲突信息，而且丧失了 D-S 证据理论的许多性能。Matsnvama T 对平均法扩展形成了加权证据合成法 14，该方法同样有归一化的缺陷。Toshiyuki15将 Yager 规则和 D-S 合成规则结合起来，引入了一个系数 ，当k时为 Yager 规则；当 时为 D-S 合成规则。但是这个系数的物理意义不明0k0k确，且需要优化，证据的合成顺序不同，结果也不同。Dubois 和 Prade16提出了将冲突的信任分配值分配给冲突焦元的并集，在焦元一致时采用合取算子，冲突时采用折取算子，此方法比 Yager 方法更精确，适用于高冲突的情况，但其不满足结合率，需要确定证据合成顺序。Levre17定义了一个与涉及冲突焦元的基本信任分配值成正比的加权因子，将冲突成比例地分配给涉及冲突的各个焦元，且该方法满足结合率，有利于决策，但在高冲突时，所承担的风险是巨大的。张山鹰等 18去掉了 D-S 合成规则中的归一化操作，提出了代数分派冲突法和加权分配冲突法，但是都存在不足之处。前者需要确定冲突分配函数，这在实际情况中是一个相当复杂的问题；后者则需要用先验知识来确定权系数，丧失了 D-S 证据理论的优点，且与证据合成顺序有关。黎湘等 19提出了一种修正的合成规则，虽然取得了较好的合成效果，但不足的是 值需要多次实验优化来确定。Selzeer 等 20采用了最大组合的基本信任分配值的决策规则，然而利用这种决策方法，有时不能得到甚至根本无法得到令人信服的结论。张淑清等 21引入了向下聚焦系数来修正 D-S 合成规则，即当冲突剧烈时，将冲突的信任分配值分配给冲突焦元的并集。许红波等 22提出了一种推广的合成规则，此规则不仅能使高冲突的证据得到合理的合成结果,甚至在冲突强度 的情况下一样可以合成，具有较好的抗干1K中北大学 2008 届本科毕业论文第 4 页 共 47 页扰能力,鲁棒性较强,但是推广的合成规则失去了 D-S 合成规则的交换性,其结果与合成顺序有关。第二种方法是 Murphy23提出的修改模型而不变 D-S 合成规则的方法，其具体步骤是：首先将证据的基本信任分配值进行平均，之后再用 D-S 合成规则进行信息融合。与其它方法相比，该规则可以处理冲突证据，且收敛速度较快。但是Murphy 的平均方法只是将多组证据进行简单的平均，没考虑到各个证据之间的相关性，这是该方法的不足之处。之后在 Murphy 的基础上，国内外的不少学者对证据间的相关性进行了研究，并提出了证据间距离来衡量证据间的相似程度。从根本上来说，主要有以下三种类型的证据间距离：Jousselme 等人提出的证据间距离 24；陈一雷等人提出的证据间距离 25；陈天璐和阙沛文提出的证据相似度和可信度的算法 26。邓勇等 27根据 Jousselme 等人提出的证据间距离提出了一种有效处理冲突证据的合成方法，此方法虽然可以处理由于证据不可靠而造成的冲突证据，但对于知识不完善而导致的冲突问题还有待于解决。张兵等 28提出了一种基于证据可信度加权平均的合成规则，此方法保留了 D-S 合成规则所有完备的数学性质，但是运算量大，计算比较复杂。1.3 主要研究内容冲突证据的合成推理在许多领域都具有重要的作用，但到目前为止还没有形成系统化的理论体系。本课题对合成规则的交换律、结合律、同一性、极化性、单调性、鲁棒性等“基本性质”和证据理论中的冲突悖论进行了研究；建立了新的冲突证据合成规则，并利用该合成规则对几种典型的冲突悖论进行了验证，且验证结果表明改进后的合成规具有良好的适用性。其研究的主要内容有以下几个方面：研究 D-S 证据理论的基础知识及其基本性质。包括相关概念的数学定义和物理意义，合成规则的交换律、结合律、极化性等基本性质。其中交换律指的是合成规则的结果与证据的顺序无关；结合律指的是可以先合成一些证据后再和其它证据合成；极化性是指在 元素识别框架下 个相同证据合成后，单元素焦元总ln中北大学 2008 届本科毕业论文第 5 页 共 47 页的信任分配值增加， 元素焦元的信任分配值减小，且越大越明显，这些均是合成l规则的基本数学性质。分析合成规则的鲁棒性以及与原有理论的兼容性，形成系统的理论体系。对 D-S 证据理论中的冲突悖论进行了阐述，为冲突证据合成规则的改进奠定基础。研究冲突证据的合成规则。研究的证据合成规则既不能失去原来 D-S 证据理论的优势和性质，又能避免冲突问题，有效地合成冲突证据。获得的优势至少要大于失去的，否则，就不能保证其广泛地适用性。合成规则要根据冲突产生的原因、冲突的强弱以及合成规则应具备的性质等几方面综合考虑确定，并不断用实例修正完善。通过实例来验证各种冲突证据合成规则的实用性，为进一步完善冲突证据合成理论奠定基础。1.4 本章小结本章主要介绍了本课题研究的目的、意义，国内外现状和研究的主要内容。中北大学 2008 届本科毕业论文第 6 页 共 47 页2 D-S 证据理论基础2.1 D-S 证据理论的概述不确定性作为信息的一个基本特性，对其进行表示和推理一直是知识表示和推理方面的重要问题。研究人员已经提出了多种不确定性表示模型和推理方法，例如，以 MYCIN 系统为代表的确定因子法、以 Bayesian 网为代表的概率推理方法、模糊逻辑、以及本文所要讨论的 D-S 证据理论等。这些理论和方法都有各自的优点和不足。近年来，信息融合受到人们越来越多的研究，由于信息本身具有不确定性、不精确性和不完备性，在信息融合时必须把这些因素考虑进去。一般来讲，信息融合都是基于置信度量理论(如 Rough 集理论、证据理论、概率论、模糊理论等)来处理信息的不确定性、不精确性和不完备性并给出不同信息源的合成规则。D-S证据理论这种不确定性推理方法，正受到越来越多的关注。证据理论由 Dempster 首先提出。 Dempster 试图用一个概率范围而不是单个的概率值去模拟不确定性，后来他的学生 Shafer 在 1976 年出版了证据的数学理论一书，此后证据理论则由此书拓展发展起来，又称为 D-S 证据理论。与概率推理等理论相比，D-S 证据理论在不确定性的度量上更灵活，推理机制更简洁，尤其对于未知的处理更接近于人的自然思维习惯。该理论的核心超越了概率统计推断的理论框架，可以适应于专家系统、人工智能、模式识别和系统决策等领域的实际问题，而且此理论很快发展成了智能学习和多源信息融合的重要组成部分。由于这些优点，D-S 证据理论在专家系统以及不确定性决策等领域得到了广泛的应用。就推理机制而言，在 D-S 证据理论中对于信任更新是通过 D-S 合成规则来实现的。相对于 Bayesian 后验公式来说，D-S 合成规则形式较简单，同时适合机器实现。遗憾的是 D-S 合成规则的标准化过程会导致推理结果出现悖论，尤其是证据之间存在高冲突时，合成结果常常有悖常理。自从 Zadeh 发现这个问题以来，冲突证据合成一直是 D-S 证据理论所关注的重要问题之一。中北大学 2008 届本科毕业论文第 7 页 共 47 页例 2.1：设甲某有两枚硬币，一个是正常的正反面硬币，另一个是两面都是正面的错币。他投掷硬币 20 次，每次都出现的是正面，问下一次投掷出现正面的概率是多少？可按照古典概率来计算，则，如果甲某持正常硬币；()0.5P正 面，如果甲某持错误硬币。1正 面我们缺少的正是甲某持哪个硬币的“证据” 。首先考虑用 Bayes 方法来解决。假设某甲持错误硬币的先验概率是 ，则次a投掷出现正面后持错误硬币的后验概率为： 2( 1naPn错 误 硬 币 次 出 现 正 面显然随着 的增大，这个后验概率很快趋于 1。但是，这个先验概率如何得到？n是否有其他方法无需给出先验概率，而凭直觉能获得这个硬币是“错币”的证据？以前处理类似问题只能利用概率论中事件概率的框架，而现在某些感兴趣的因素却不能用概率的方法来处理。事实上，有关证据问题在哲学文献里已经作过很深的研究，而证据在本质上就是基于观测对不同的假设赋予权值的一种方法。根据有关证据的定义，可简单地给出如下解释 12：（1）处理任意数量的假设；（2）能够把证据的权值解释为一种函数，而这个函数把假设的先验概率空间，映射到基于观测的假设后验概率空间。2.2 D-S 理论的基本概念2.2.1 识别框架D-S 证据理论一般用集合来表示命题。定义 2.1 假设现有一个需要判决的问题，对于该问题我们所能认识到的所有可能答案的完备集合用 来表示，且 中的所有元素都是两两互斥的；在任一时刻，问题的答案只能取 中的某一元素，且答案可以是数值变量，也可以是非数值变量，则称此互不相容事件的完备集合 为识别框架，可表示为：中北大学 2008 届本科毕业论文第 8 页 共 47 页（2.1）12,jn， ，其中， 称为识别框架 的一个事件或元素。由识别框架 的所有子集组成j 的一个集合称为 的幂集，记作 ，可表示为：（2.2）1212132,n ， ，这里 表示空集。识别框架 的任一子集都与一个问题答案的命题相对应。这个命题一般描述为：“问题的答案在中” 。例如，判断掷股子所出现的点数，那么 ，=1,2345,6而 则表示“掷出的点数为 1”，则 表示“掷出的点数为奇数” ，11,35则表示“掷出的点数不为 6”，即“掷出的点数为 1,2,3,4,5 中的某一,2345个” 。由此可见，幂集 中的每一个元素 都代表一个问题答案的命题。2A2.2.2 基本信任分配函数在定义了识别框架 的概念后，我们就可以来建立证据处理的数学模型了。如何来表示人们关于一个命题的信任即相信一个命题为真的程度呢？不同的学者有不同的看法。逻辑主义以及频率主义者认为 29：一个命题为真的程度是由证据完全决定的片面强调了证据的作用，忽视了人的判断作用。主观主义者认为：一个命题为真的程度完全由人决定，是人主观想象的结果片面强调了人的认识作用，忽视了证据的作用。Shafer 认为：在一批给定的证据与一个给定的命题之间没有什么一定的客观联系能够确定一个精确的支持度；一个实在的人对于一个命题的心理描述也不是总能够用一个相当精确的实数来表示，而且也并不是总能确定这样一个数。但是，对于一个命题他可以做出一种判决，在他综合考虑了一个给定的证据组中的有时含混、有时混乱的感觉与理解之后，能够说出一个数字来表示据他本人判段出的该证据支持一个给定的命题的程度，即他本人希望赋予该命题的置信度。Shafer对于人根据证据为一个命题赋予一个置信度的理解可以用图 2.1 来表示：中北大学 2008 届本科毕业论文第 9 页 共 47 页图 2.1 证据、命题与人之间的关系图在证据、命题与人之间所划的实线表示人可以对证据加以分析从而得到判断者本人希望赋予命题的信任值；在证据与命题之间所划的虚线表示一种人假想出来的证据对命题的支持关系，是人经过证据分析后所赋予的证据对命题的支持关系，支持程度 ，所以支持度与信任值是人根据证据判断出的对命题看法的SBel两个方面。这种基于证据分析，确定相信一个命题为真的程度的方法称为证据处理。按照 Shafer 的观点，证据处理的数学模型为：首先确定识别框架 。只有确定了识别框架 ，我们才能把对命题的研究转化为对集合的研究。根据证据建立一个信任程度的初始分配，即证据处理人员对证据加以分析，确定出证据对每一个命题本身的支持程度。通过分析前因后果，计算出我们对于所有命题的信任程度。从直观上看，如果一批证据对一个命题提供支持，则它也应该对该命题的推论提供同样的支持。所以，一个命题的信任度应该等于证据对它的所有前提本身提供的支持度之和。对于证据建立的信任程度的初始分配我们用基本信任分配函数来表示，其定义如下：定义 2.2 基本信任分配函数 是一个从集合 到0,1的映射， 表示识别m2A框架 的任一子集，记作 ，且满足：A（2.3）()01A其中， 称为事件 的基本信任分配值，它表示证据对 的信任程度。空()mA A集的基本信任分配值为