Dempster合成规则的等效计算方法及其实现

第３４卷　第２期　２０１５年３月　许昌学院学报　Ｊ０ＵＲＮＡＬ　ＯＦ　ＸＵＣＨＡＮＧ　ＵＮＩＶＥＲＳＩＴＹ　Ｖｏ１．３４．Ｎｏ．２　Ｍａｒ．２０ｌ５　文章编号：１６７１—９８２４ｌ２０１５）０２—００６５—０５　Ｄｅｍｐｓｔｅｒ合成规则的等效计算方法及其实现　李文艺，吕现钊，郝保明　（宿州学院机械与电子工程学院，安徽宿州２３４０００）　摘　要：给出了Ｄｅｍｐｓｔｅｒ合成规则的一种等效计算方法，该方法能够由非归一化的合成结　果直接计算出最终的合成结果，同时在整个合成的过程中避开了冲突系数的计算．针对该方法给　出了一种简单的实现途径，首先利用二进制编码数据表示辨识框架幂集中的元素；然后把Ｄｅｍｐ—　ｓｔｅｒ合成规则中集合的运算转化为二进制编码数据之间的逻辑运算；最后通过算例进行了验证，　结果表明该方法与Ｄｅｍｐｓｔｅｒ合成规则得到的结果完全相同．　关键词：证据理论；等效算法；二进制编码；冲突系数　中图分类号：ＴＰ３９１　文献标识码：Ａ　证据理论源于上世纪６０～７Ｏ年代，该理论是由Ｄｅｍｐｓｔｅｒ首先提出，后来由他的学生ＳｈａＲｅｒ进行了完　善和发展，所以证据理论又称为Ｄ—ｓ证据理论　．由于证据理论可以很好的表示客观世界中的信息，并　能够区分命题的“不确定”与“不知道”之间的关系，该理论已经是模式识别、信息融合等领域的重要方　法　Ｊ．证据理论的核心是Ｄｅｍｐｓｔｅｒ合成规则，该规则可以把不同的证据进行合成，从已有的证据生成新　的证据．在一般情况下利用Ｄｅｍｐｓｔｅｒ合成规则可以使正确信息逐步聚集，从而合成结果有利于进行最终　的判断与决策．但是在使用Ｄｅｍｐｓｔｅｒ合成规则进行多个证据融合时，计算量会随证据个数的增加而急剧　增大；在进行多个证据的融合过程中，计算信任函数与冲突系数时要进行集合之间的“交”运算，而大量集　合之间的“交”、“包含”运算会耗费较多的计算时间．以上这些因素都影响到了证据理论的应用。。　．　针对证据理论计算量大的问题，本文给出了Ｄｅｍｐｓｔｅｒ合成规则的一种等效计算方法，与经典的Ｄｅｍｐ—　ｓｔｅｒ合成方法相比本文所给出的方法计算量较小、易于计算机实现．该方法利用二进制编码表示辨识框架　幂集中的元素；由此可以把证据理论中集合之间的“交”运算转换成了二进制编码之间的“与”逻辑运算．　然后利用Ｄｅｍｐｓｔｅｒ等效合成公式计算最终的融合结果．对实验分析表明该方法的计算量有所减小，计算　结果与Ｄｅｍｐｓｔｅｒ方法完全一样．　１　证据理论　非空集合Ｏ由一些互斥且可穷举的元素组成，称Ｏ为辨识框架．集合Ｏ表示人们对某一问题所有可　能结论（或所有可能假设）的集合；从而，所需要解决的问题转化为Ｏ的子集．　通常假设辨识框架Ｏ为一有限集合，用２。表示Ｏ的幂集．若函数ｍ：２　一［０，１］满足以下三个条件：　（１）ｍ（　）＝０；（２）０≤ｍ（Ａ）≤１；（３）∑ｍ（Ａ）＝１．称／ＴＺ为Ｏ上的基本概率赋值函数，又称ｍａｓｓ函数．　不同的证据可以利用Ｄｅｍｐｓｔｅｒ合成规则进行合成运算，从而产生新的证据．假设ｍ。，ｍ：表示辨识框架Ｏ下　的２个基本概率赋值函数，Ｄｅｍｐｓｔｅｒ合成规则表示为　ｒ０　Ａ＝　ｉ　收稿日期：２０１４—０５—２７　Ａ≠　‘　基金项目：安徽省高等学校省级优秀青年人才基金重点项目（２０１３ＳＱＲＬ０８４ＺＤ）；宿州学院基金项目（２００９ｙｓｓ０８，２００９ｙｓｓ０７，ｓｚｘｙｊｙｘｍ２０１３０７）　作者简介：李文艺（１９８Ｏ一），男，河南开封人，讲师，硕士，研究方向：模式识别、信息融合．　许昌学院学报　２０１５年３月　其中ｋ＝　∑ｍ　（Ａ　）ｍ：（Ａ　）表示冲突系数，冲突系数表明证据之间的冲突程度，ｃ／，表示空集．　Ｄｅｍｐｓｔｅｒ合成规则通常表示为直和的形式，即ｍ＝ｍ　０ｍ：．为了更好的表示已有信息对０的子集的支持　程度，定义了２。上的信任函数与似真函数．信任函数表示证据对命题的支持程度，信任函数的计算方法为　Ｂｅｌ（ａ）＝∑ｍ（Ｂ）（Ｖ　Ａ　）．　似真函数表示不反对命题的程度，似真函数的计算方法为　（２）　（３）　Ｐｌ（Ａ）＝∑ｍ（曰）＝１一Ｂｅｌ（Ａ）．　公式（３）中ＹＡ　，　表示　的补集．　２　Ｄｅｍｐｓｔｅｒ合成规则的等效计算方法　假设ｍ　，ｍ：为辨识框架　下的两个基本概率赋值函数，Ａ　，Ａ：，…，Ａ　表示基本概率赋值函数ｍ，的　焦元；　，Ｂ　，…，Ｂ　表示基本概率赋值函数ｍ：的焦元．利用Ｄｅｍｐｓｔｅｒ合成规则合成之后的基本概率赋值　函数记为ｍ；Ｃ，，Ｃ　，…，Ｃ　表示合成结果的焦元．　令而（Ｃ　）表示未归一化的合成结果，即：　（Ｃ１）＝∑ｍ　（Ａ　）ｍ　（Ｂ　（４）　公式（４）中Ｃ　≠＠；　＝１，２，…，Ｎ；ｊ＝１，２，…，Ｍ；ｌ＝１，２，…，Ｋ），最终的融合结果可以按一下方法计算：　．　（５）　公式（５）中（１＝１，２，…，　）．下面证明该计算方法与经典的Ｄｅｍｐｓｔｅｒ合成规则是等价的．　证明　而（Ｃｚ）＝∑ｍ。（Ａ　）ｍｚ（日　），　・　（６）　（７）　。　因此，得：　ｍ（ｃ　）　（Ｃ１）・　（８）　由证据理论的基本要求：　ｍ（Ｃ１）＋ｍ（Ｃ２）＋…＋ｍ（ＣＫ）＝１．　丽（　＋　（ｃ：）＋．．・＋　而（Ｇ　）＝１．　（９）　（１ｏ）　（１１）　（丽（Ｃｔ）＋ｍ（ｃｚ）＋．．’＋而（ＣＫ））＝　・　所以：　而（Ｃ１）十而（Ｃ２）＋…＋而（Ｃ　）＝１一ｋ．　因此，得到：　（１２）　ｍ（Ｃ　ｚ）＝　证毕．　（ｃ１）＝　而　．　（１３）　由以上可知本文所给出的方法方法与Ｄｅｍｐｓｔｅｒ合成规则是完全等效的，而不是一种近似的计算　引．　３等效计算的实现　利用Ｄｅｍｐａｔｅｒ合成规则需要判断集合之间的关系是否满足运算条件．为了避免集合之间的运算，本　文给出了一种新的实现方法，该方法中利用二进制编码之间的“与”逻辑运算代替集合之间的“交”运算．　第３４卷第２期　李文艺，等：Ｄｅｍｐｓｔｅｒ合成规则的等效计算方法及其实现　６７　本文的基本思想为：若辨识框架１９中有Ⅳ个元素，则＠的幂集２　中最多有２　个元素，而一个Ｎ位的二　进制数最多可以表示２　种不同的组合．可以用Ⅳ位的二进制数据表示辨幂集中的２　个不同的元素．下面　通过一个实例说明本文方法的基本思想．　例：假设　＝｛ｏ，ｂ，ｃ｝，＠的幂集共有８个元素分别为　，｛ｏ｝，｛ｂ｝，｛ｃ｝，｛ｏ６｝，｛６ｃ｝，｛ａｃ｝，｛ａｂｃ｝这８　个元素分别用二进制表示为：０００，１００，０１０，００１，１１０，０１１，１０１，１１１．ｍ，，ｍ：表示辨识框架　下的两个基本　概率赋值函数．使用二进制编码之后，使用Ｄｅｍｐｓｔｅｒ合成方法进行计算，合成结果可用已下方法计算：　ｍ（１　ａ｝）　Ⅲ　，ｍ－（Ａ１）　。。２８　Ａｉ　Ｅ　２ＯＡ２Ｅ　（Ａ２），　ｍ（｛６｝）　Ⅲ　，ｍ　（Ａ１）　。。Ｅ　２０　Ａ１￡２ｐＡ２　（Ａ２），　ｍ（Ｉ　ｃ｝）　川　．ｍ，（Ａ１）　。ＡＩ　Ｅ　２。Ａ２　Ｅ　２ｅ　（Ａ２），　ｔ　ａｂ｝）　。。　Ａｌ　Ｅ　２ｅ。Ａ２Ｅ　２８　Ｉ）．　（Ａ２）’　ｔ　ｂｃ｝）　。。　１）．　（Ａ２），　＾ｌ　Ｅ　２ｅＡ２　Ｅ　２ｅ　，ｍ（　）＝‘　。。ｍ　（　ｔ）　（Ａ２），　｛ａｂｃ｝）　＾ｌ＾　．ｍ－（Ａ１）．ｍ　（Ａ２）・　。Ａ１　Ｅ　２日Ａ２Ｅ　２ｅ　其中ｋ　。．ｍｔ（Ａ－）‘ｍ２（Ａ：）・　Ａｌ　Ｅ　２８Ａ２Ｅ　２０　当辨识框架中的元素较多时，只需要增加二进制编码的位数即可．Ｄｅｍｐｓｔｅｒ合成规则转换为以下表　达式：　ｆｏ　Ａ＝　ｉ　ｌ（Ａ　。　４　其中｜ｊ｝＝　∑ｍ。（Ａ　）ｍ　（Ａ　）表示冲突系．同理在计算信任函数是把集合之间的“交’’运算转换成了“与’’　运算；在计算似真函数时，把集合之间“并”运算转化为了“或”运算．　针对上述例题，利用本文所给出的方法可按照已下方法进行计算．　（　）＝　∑　ｍ，（Ａ。）・ｍ：（Ａ：），　Ａｌ　Ｅ　２ｅ，Ａ２　Ｅ　２８　（｛ｂ｝）＝　∑　ｍ。（　。）・ｍ：（Ａ：），　Ａ１‘２。Ａ２ｅ　２ｅ　．（｛ｃ｝）＝　』∑　ｍ。（Ａ。＿　一　‘　）・ｍ：（。　。Ａ：），　　Ａｌ　Ｅ　２ｅ，＾２　Ｅ　２０　（｛ａｂ｝）＝　』∑　ｍ。（Ａ。　‘　‘　）・ｍ：（。　。Ａ　），　　６８　许昌学院学报　２０１５年３月　（｛ｂｃ｝）＝　∑　ｍ　（Ａ。）。ｍ　（Ａ：），　Ａ１∈２８Ａ２∈２８　，而（｛ａｃ｝）＝　∑　ｍ　（Ａ　）・ｍ：（Ａ：），　Ａｌ　Ｅ　２８Ａ２　Ｅ　２０　，而（｛ａｂｃｔ）＝　∑　ｍ　（Ａ　）’ｍ　（Ａ：）．　Ａ１∈２０Ａ２∈２８　，分别表示未归一化之后的融合结果．则：　ｍ（１　ａ｝）＝　而（１　ａ｝），ｍ（Ｉ　ｂ　１）＝　（｛６｝），ｍ（ｔ　ｃ｝）＝　而（｛ｃ｝），ｍ（｛。６｝）＝　而（｛。６｝），　ｍ（｛ｂｃ｝）＝　而（｛ｂｃ｝），ｍ（１　ａｃ｝）＝　（｛。ｃ｝），ｍ（｛。６ｃ｝）＝　丽（｛。６ｃ｝）．　令：Ｍ＝而（｛ａ｝）＋而（｛ｂ｝）十而（｛ｃ｝）＋而（｛ａｂ｝）十而（｛６ｃ｝）＋而（｛ａｃ｝）＋而（｛ａｂｃ｝）．　则最终的融合结果可表示为　＝扣　ｍ（ｔ　ｂ　１）＝扣…　ｍ（ｔ　ｃ｝）＝　（｛ｃ｝）’　训）：扣（１　ａｂ　１），　（｛。ｃ｝），ｍ（｛。６ｃ｝）＝　（｛。６ｃ｝）．　ｍ（｛ｂｃ｝）＝　而（ｔ　ｂｃ｝），ｍ（｛ｎｃ｝）＝　通过分析知，在Ｄｅｍｐｓｔｅｒ合成规则中原来集合的“交”运算变成了逻辑“与”运算．按照此方法式（４）可以　表示为　而（Ｃ１）＝∑ｍ　（　）ｍ：（Ｂｊ）．　ＡｉＡ　Ｌ　（１５）　用二进制编码的方法实现证据融合的步骤为　步骤１：对幂集中的每个元素进行二进制编码．　步骤２：按式（１４）计算出未归一化的融合结果．　步骤３：按式（５）计算出最终融合结果．　４　算例仿真　为了比较本方法与经典的Ｄｅｍｐｓｔｅｒ方法，下面通过一个具体的算例进行仿真实验．假设有６个不同　的传感器探测到了飞行器类型，分别用ＡＢＣ表示，Ａ＝“战斗机”，Ｂ＝“轰炸机”，Ｃ：“武装直升机”．从６　个传感器得到的基本概率分配函数分别为ｍ　，ｍ　，ｍ　，ｍ　，ｍ　，ｍ　，函数值如表１所示．　表１　基本概率分配函数值　利用本文方法与Ｄｅｍｐｓｔｅｒ合成规则得到的结果是相同的，融合结果是：　ｍ（Ａ）＝０．５７３　６，ｍ（曰）＝０．３５０　８，ｍ（Ｃ）＝０．０７０　７，ｍ（ＡＢ）＝０．００１　２，ｍ（ＢＣ）＝０．００３　７．　本文所给出的方法用二进制编码表示了原来的集合，利用了二进制之间的逻辑运算代替了原来的集　合之间的运算．另外本文所给出的方法避免了冲突系数的计算，针对本算例来说由于不用计算冲突系数，　使得本文的计算量为经典Ｄｅｍｐｓｔｅｒ合成规则的约７０％，计算量有所减少．　５　结语　给出了Ｄｅｍｐｓｔｅｒ合成规则的一种等效计算方法，该方法可以避免计算证据之间的冲突系数，而可以　第３４卷第２期　李文艺，等：Ｄｅｍｐｓｔｅｒ合成规则的等效计算方法及其实现　６９　得到与原方法相同的结果，与原方法相比本文的计算量有所减少．同时，文中对所给出的方法进行了证明．　针对文中所提出方法的实现问题，文中利用二进制的方法对辨识框架的幂集中的元素进行编码．然后利用　逻辑运算代替Ｄｅｍｐｓｔｅｒ方法中集合之间的运算．用二进制编码对辨识框架进行重新表示之后，可以更加　方便的利用计算机编程的方法实现多个证据的合成问题．仿真实验表明该方法可以较好的解决多证据的　融合问题，并能够得到与Ｄｅｍｐｓｔｅｒ方法相同的融合结果．　参考文献：　Ｄｅｍｐｓｔｅｒ　Ａ　Ｐ．Ｕｐｐｅｒ　ａｎｄ　ｌｏｗｅｒ　ｐｒｏｂａｂｉｌｉｔｉｅｓ　ｉｎｄｕｃｅｄ　ｂｙ　ａ　ｍｕｌｔｉ—ｖａｌｕｅｄ　ｍａｐｐｉｎｇ［Ｊ］．Ａｎｎｕａｌｓ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　Ｓｔａｔｉｓｔｉｃｓ　１９６７，３８（４）：３２５—３３９．　『２］　Ｓｈａｆｅｒ　Ｇ．Ａ　Ｍａｔｈｅｍａｔｉｃａｌ　Ｔｈｅｏｒｙ　ｏｆ　Ｅｖｉｄｅｎｃｅ　Ｉ　Ｍ】．Ｐｒｉｎｃｅｔｏｎ：Ｐｒｉｎｃｅｔｏｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｐｒｅｓｓ，１９７６．　［３］　王凤朝，刘兴堂，黄树采．基于模糊证据理论的多特征目标融合检测算法［Ｊ］．光学学报，２０１０，３０（３）：７１３—７１９　［４］　张燕君，龙　呈．基于证据理论的目标识别方法［Ｊ］．系统工程与电子技术，２０１３，３５（１２）：２４６７—２４７０．　［５］　王　峰．Ｄ—ｓ证据理论在指纹图像分割中的应用研究［Ｊ］．计算机工程与应用，２０１０，４６（２４）：１６９—１７２．　［６］　陈圣群，王应明．证据的分组合成法［Ｊ］．控制与决策，２０１３：２８（４）：５７４—５７８．　『７］　王　壮，胡卫东，郁文贤，等．基于截断型Ｄ—ｓ的快速证据组合方法［Ｊ］．电子与信息学报，２００２，２４（１２）：１—３　［８］　李岳峰，刘大有．证据理论中的近似计算方法［Ｊ］．吉林大学学报，１９９５，３１（１）：２８—３２．　Ａｎ　Ｅｑｕｉｖａｌｅｎｔ　Ａｌｇｏｒｉｔｈｍ　ｏｆ　ｔｈｅ　Ｄｅｍｐｓｔｅｒ　Ｃｏｍｂｉｎａｔｉｏｎ　Ｒｕｌｅ　ａｎｄ　Ｉｔｓ　Ｒｅａｌｉｚａｔｉｏｎ　ＬＩ　Ｗｅｎ—ｙｉ，ＬＶ　Ｘｉａｎ—ｚｈａｏ，ＨＡＯ　Ｂａｏ－ｍｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｍｅｃｈａｎｉｃａｌ　ａｎｄ　Ｅｌｅｃｔｒｏｎｉｃ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｕｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｕｚｈｏｕ　２３４０００，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａｎ　ｅｑｕｉｖａｌｅｎｔ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ｔｈｅ　Ｄｅｍｐｓｔｅｒ　ｃｏｍｂｉｎａｔｉｏｎ　ｒｕｌｅ　ｉｓ　ｐｒｅｓｅｎｔｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．Ｂｙ　ｔｈｉｓ　ａｌｇｏ—　ｒｉｔｈｍ，ｔｈｅ　ｆｉｎａｌ　ｒｅｓｕｌｔ　ｃａｎ　ｂｅ　ｏｂｔａｉｎｅｄ　ｆｒｏｍ　ｔｈｅ　ｕｎ—ｎｏｒｍａｌｉｚｅｄ　ｃｏｍｂｉｎａｔｉｏｎ　ｒｅｓｕｌｔｓ，ａｎｄ　ｔｈｅ　ｃａｌｃｕｌａｔｉｏｎ　ｏｆ　ｔｈｅ　ｃｏｎｆｌｉｃｔ　ｃｏｅｆｆｉｃｉｅｎｔ　ｃａｎ　ｂｅ　ａｖｏｉｄｅｄ　ａｔ　ｔｈｅ　ｓａｍｅ　ｔｉｍｅ．Ａ　ｒｅａｌｉｚａｔｉｏｎ　ａｐｐｒｏａｃｈ　ｏｆ　ｔｈｉｓ　ｍｅｔｈｏｄ　ｉｓ　ｆｕｒｔｈｅｒ　ｐｒｅｓｅｎｔｅｄ．　Ｆｉｒｓｔｌｙ，ｅａｃｈ　ｅｌｅｍｅｎｔ　ｏｆ　ｔｈｅ　ｄｉｓｃｅｒｎｍｅｎｔ　ｆｒａｍｅ　ｉｓ　ｃｏｄｅｄ　ｂｙ　ｔｈｅ　ｂｉｎａｒｙ　ｅｎｃｏｄｉｎｇ，ａｎｄ　ｔｈｅｎ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎ　ｏｆ　ｓｅｔｓ　ｉｓ　ｔｒａｎｓｆｏｒｍｅｄ　ｉｎｔｏ　ｌｏｇｉｃ　ｃｏｍｐｕｔａｔｉｏｎ　ｏｆ　ｔｈｅ　ｂｉｎａｒｙ　ｅｎｃｏｄｉｎｇ　ｉｎ　ｔｈｅ　Ｄｅｍｐｓｔｅｒ　ｃｏｍｂｉｎａｔｉｏｎ　ｒｕｌｅ．Ａｔ　ｌａｓｔ，ｅａｌｃｕｌａ—　ｔｉｏｎ　ｅｘａｍｐｌｅｓ　ａｒｅ　ｕｓｅｄ　ｔｏ　ｔｅｓｔ　ｔｈｉｓ　ｎｅｗ　ｍｅｔｈｏｄ，ａｎｄ　ｆｉｎｄｉｎｇｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｒｅｓｕｌｔｓ　ｏｂｔａｉｎｅｄ　ａｒｅ　ｔｈｅ　ｓａｍｅ　ｔｏ　ｔｈｏｓｅ　ｏｂｔａｉｎｅｄ　ｂｙ　ｔｈｅ　Ｄｅｍｐｓｔｅｒ　ｃｏｍｂｉｎａｔｉｏｎ　ｒｕｌｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｅｖｉｄｅｎｃｅ　ｔｈｅｏｒｙ；ｉｄｅｎｔｉｃａｌ　ａｌｇｏｒｉｔｈｍ；ｂｉｎａｒｙ　ｅｎｃｏｄｉｎｇ；ｃｏｎｆｌｉｃｔ　ｃｏｅｆｆｉｃｉｅｎｔ　责任编辑：赵秋宇