《模式识别原理与应用》课件第10章.ppt

1、第10章多分类器融合第第10章多分类器融合章多分类器融合10.1多分类器融合的基本原理多分类器融合的基本原理10.2多数投票法和多数投票法和BKS方法方法10.3基于基于Bayes理论的多分类器融合理论的多分类器融合10.4基于证据理论的多分类器融合基于证据理论的多分类器融合10.5基于神经网络的多分类器融合基于神经网络的多分类器融合10.6基于模糊积分的多分类器融合基于模糊积分的多分类器融合10.7基于决策模板的多分类器融合基于决策模板的多分类器融合习题习题第10章多分类器融合10.1.1多分类器融合的必要性多分类器融合的必要性模式识别最终的目标是得到尽可能好的识别性能。为了实现这一目标,传

2、统的做法是设计不同的分类方案,再根据实验结果,选择一个最好的分类器作为最终的解决方法。过去十多年中,对分类器研究的焦点从单个分类器的研究转移到多分类器系统的研究。10.1 多分类器融合的基本原理多分类器融合的基本原理第10章多分类器融合多分类器融合的必要性包括以下两个方面:(1)在模式识别中,分类的方法有很多,这些算法是基于不同的理论框架提出来的。分类器包括Bayes分类器、KNN分类器、各种距离分类器、模糊分类器、神经网络分类器、句法分类器等。每种分类器各有优点,对于特定的应用问题,都能够取得一定的成功,但是,没有一种方法适应所有的应用需求,或达到期望的效果。人们从大量的实验和应用中发现,不

3、同的分类器对于分类模式具有互补的信息,可以利用这种互补信息来提高识别性能,例如,更高的识别率和更低的错误率。因此,需要集成不同分类器的结果,以获得较好的分类效果。第10章多分类器融合(2)对于某些复杂的识别问题,输入的特征变量较多。这些特征变量具有不同类型、不同表现形式或不同量级。对于不同类型的特征变量,需要根据不同的理论和方法来设计分类器。对于不同表现形式和不同物理含义的特征变量,进行归一化处理非常困难,难以用一个分类器来处理。此外,当输入特征向量的维数较大时,分类器的结构将非常复杂,这增加了计算复杂度,由于有限的学习样本,分类器的性能也较差。因此,利用信息融合的思想,可将设计一个性能优良的

4、高维输入分类器问题转化成多个性能较优的低维输入分类器的设计问题,运用多分类器融合技术,为高维特征空间的划分和高可靠性分类器的设计提供一个新的思路。第10章多分类器融合10.1.2多分类器融合的体系结构多分类器融合的体系结构多分类器融合常见的结构有三种:并行结构、串行结构、串并行结构。如图10-1所示,在并行结构中,各分类器是独立进行设计的,它们之间没有关联。第10章多分类器融合图10-1 多分类器集成的并行结构第10章多分类器融合如图10-2所示,在串行结构中,前一级分类器为后一级分类器提供信息,它们之间有一定的关联。图 10-2多分类器集成的串行结构第10章多分类器融合如图10-3所示,串并

5、行结构是串行结构中某一级的分类器由多个并行结构的分类器组成,从而结合并行结构和串行结构的优点。第10章多分类器融合图 10-3多分类器集成的串并行结构第10章多分类器融合正如图10-4中的灰线和椭圆所示,各多分类器融合系统的不同之处体现在如下几个方面:(1)使用的分类器数量L。(2)单个分类器的类型。一些组合策略使用相同类型的分类器进行融合,如神经网络、线性分类器、最近邻分类器,而其他一些组合策略使用不同的分类器集合。(3)单个分类器使用的特征子集(在图10-4中用灰色椭圆表示)。第10章多分类器融合(4)分类器决策的组合方法。例如多数投票法、贝叶斯法、BKS方法、简单组合方法(如平均、相乘、

6、最小、最大)、模糊积分法、线性组合法、神经网络法、D-S证据理论法等。(5)不同分类器使用的训练集。(6)两级结构的训练类型。主要有训练多个独立的分类器,直接进行融合;先训练多个独立的分类器,再训练一个融合器;同时训练整个两级架构。通常根据分类准确度来选择单个分类器(准确度越高越好)。当整个结构作为一个整体来训练时,单个分类器的参数将随融合策略的不同而发生变化。第10章多分类器融合图 10-4多分类器融合系统 第10章多分类器融合10.1.3多分类器融合的分类多分类器融合的分类1.分类器输出信息的分类器输出信息的3个级别个级别给定模式空间S,由M个互不相交的模式类集合1,2,M组成,即S=12

7、M,ij=(ij;i,j=1,2,M),模式识别就是把给定的模式x划分到1,2,M中的一个。设e为一分类器,令=1,2,M。对于输入样本(模式)xS,e(x)=j表示分类器e把x划分到类j中。其中,jM+1,j为模式类集合j的类别号(标签)。这里引入拒识,e(x)=M+1表示分类器e拒识x,即不能判断x的类别。第10章多分类器融合一般地,分类器能够提供的信息可分为三个级别:(1)抽象级:分类器e只输出唯一的标签j,或一个子集。(2)排序级:分类器e把(或子集)中的标签按照某种规则排列成一个序列,排在首位的是第一选择。(3)度量级:分类器e给每一个标签分配一个度量值,用以表示输入样本x属于相应类

8、的程度。J J 第10章多分类器融合在上述三个级别中,度量级包含的信息最多,抽象级信息最少。根据属于某个标签的度量值,按照某种排序规则,我们可以把中标签排成一个序列(递增或递减)。通过选择排在首位的标签,或直接在度量级选择具有最大值或最小值的标签,分配给输入样本x,从而为x指定唯一的标签。换句话说,从度量级到抽象级是一个信息减少的过程或抽象的过程。第10章多分类器融合许多分类器能够提供度量级信息,例如,Bayes分类器提供后验概率P(j|x),j=1,2,M;距离分类器提供输入样本x与每类的原型样本之间的距离;模糊分类器中的隶属度,等等。度量级的处理是许多分类器的中间步骤。但是,有些分类器只能

9、提供抽象级输出,例如,句法分类器。第10章多分类器融合2.分类器融合的类型分类器融合的类型根据各分类器提供的信息的级别,多分类器融合可以分为以下三种类型:(1)决策层融合,即单个分类器输出为某个确定的类别号。假设R个分类器e1,e2,eR对同一输入样本(模式)x进行分类,事件ek(x)=jk表示分类器ek把x划分到类jk中,其中,jkM+1,ek(x)=M+1表示分类器ek拒识x,k=1,2,R。决策层融合就是利用这些事件构造一个集成的分类器e对x进行分类,输出一个确定的类别号,即e(x)=j,jM+1。第10章多分类器融合(2)排序层融合,即单个分类器输出为样本属于各类的可能性的一个排序列表

10、。对于输入x,每个分类器ek(x)产生一个子集Lk,且Lk中标签排成一个序列。排序层融合就是利用事件ek(x)=Lk,k=1,2,R,构造一个集成的分类器e,对x进行分类,输出一个确定的类别号,即e(x)=j,jM+1。第10章多分类器融合(3)度量层融合,即单个分类器输出为样本属于相应类的程度。对于输入x,每个分类器ek(x)产生一个度量向量Me(k)=(mk(1),mk(2),mk(M)T,其中,mk(i)表示x属于相应类i的程度。度量层融合就是利用事件ek(x)=Me(k),k=1,2,R,构造一个集成的分类器e,对x进行分类,输出一个确定的类别号,即e(x)=j,jM+1。这三类方法覆

11、盖了不同的应用范围,所利用的分类器输出信息量依次增多,相应地,也可能得到更好的结果。第10章多分类器融合在决策层融合中,各个分类器在理论与方法上可以相差很大,例如,有些分类器是基于统计的方法,而另一些方法是基于句法的方法。事实上,不是每种分类器都可以输出排序列表或隶属程度,但是,任何分类器至少可以输出抽象级信息,从而决策层融合可以适用于所有的模式识别领域。所以,决策层的融合成为应用最广泛,也是研究较早和较充分的一类融合方法。具有代表性的几种决策层融合方法包括多数投票法、BKS方法、Bayes规则和证据理论方法等。第10章多分类器融合在度量层融合中,融合操作只能在相同量级的度量信息上进行,从而要

12、求所有的分类器输出度量级信息。此外,不同种类的度量向量应该能够被转换成一种相同的度量向量。具有代表性的几种度量层融合方法包括Bayes方法、证据理论方法、模糊积分方法和神经网络方法等。第10章多分类器融合排序层融合位于决策层融合与度量层融合之间,它要求所有的分类器输出排序级信息。在排序层融合中,分类器不能是纯句法分类器,它只能输出抽象级信息。任何输出度量级信息的分类器都可以参与排序层融合,因为从度量向量Me(k)可以产生一个排序列表。第10章多分类器融合10.2多数投票法和多数投票法和BKS方法方法多数投票法和BKS方法是简单、有效的多分类器集成方法,本节简要讨论这两种方法。10.2.1多数投

13、票法多数投票法假设R个分类器e1,e2,eR对同一输入样本(模式)x进行分类。定义示性函数:第10章多分类器融合1,if()and()0,elsekkjejjTxx(10-1)则最保守的投票规则为 1,if,min()0()1,elseRkjkjjTeM xx(10-2)第10章多分类器融合也就是说,集成的分类器e把x划分到类j,当且仅当所有R个分类器同时把x划分到类j中,否则拒识x。多数投票准则为 11,if()max()2()1,elseRRkjikikkjTTReMxxx(10-3)第10章多分类器融合更一般的形式为 11,if()max()()1,elseRRkjikikkjTTReM

14、xxx(10-4)其中,01。若取=1,则式(10-4)变成式(10-2);若取=0.5+,为很小的正数,则式(10-4)变成式(10-3)。因此,式(10-2)与式(10-3)是式(10-4)的特例。第10章多分类器融合事实上,式(10-4)仅考虑了得票最多的类别号,并且所得票数要足够多。但是,可能出现得票最多的类别号有多个,或者得票第一多与第二多的票数相差很小。这时,式(10-4)的决策可能不可靠。进一步修正式(10-4),得到新的多数投票准则:11 11,if()max(),()()max()1,elseRRkjikikkRRkjijkikkjTTeTTRMxxxxx(其他)(10-5)

15、第10章多分类器融合基于投票准则的多分类器集成是决策层融合的一般形式,也就是说,决策层融合是基于投票准则的,或者是投票准则的变形或改进。多数投票法存在如下问题:(1)所有的分类器都是平等的,都作为一票,没有考虑不同分类器的性能差异。(2)投票准则是抽象级信息的集成,单一分类器的输出信息采用硬分类,即要么认为输入模式属于某一类,要么拒识。但是,大部分分类器的输出信息是度量级的,从而在集成的过程中,抛弃了很多有用的信息。(3)对于每个分类器,都需要确定一些门限值,这些值的确定还没有理论指导。第10章多分类器融合10.2.2BKS方法方法BKS方法又称为性能知识空间法,穷举各个分类器对训练样本集合的

16、识别结果的各种组合,然后统计各种决策组合对应的样本,找出其中占主导地位的类别,作为多分类器融合的输出。一个性能知识空间(BKS)是一个R维空间,其中,每一维代表一个分类器的判决结果。每一个分类器有M+1种可能的决策1,2,M+1,各个分类器的决策联合形成BKS的一个单元,称之为局部单元。一个二维的BKS空间如表10-1所示。第10章多分类器融合表表10-1二维二维BKS空间空间 1jM+1(1,1)(1,j)(1,M+1)i(i,1)(i,j)M+1(M+1,1)(M+1,j)(M+1,M+1)(1)|(2)ee第10章多分类器融合 利用R个分类器对所有的训练样本进行分类,统计各分类决策组合对

17、应的样本,并归入相应的局部单元中。引入记号:BKS的一个单元BKS(e(1),e(R):第一个分类器给出了决策e(1),第二个分类器给出了决策e(2),第R个分类器给出了决策e(R)等;N(e(1),e(R)(m):在BKS(e(1),e(R)中属于类别m的训练样本总数;第10章多分类器融合T(e(1),e(R):在BKS(e(1),e(R)中的训练样本总数,即(1),()(1),()1()Mee Ree RmTNm(10-6)(e(1),e(R):在BKS(e(1),e(R)中占主导地位的类别,即(e(1),e(k)=j,满足(1),()(1),()1()max()ee Ree Rm MNj

18、Nm(10-7)第10章多分类器融合对于输入样本x,各分类器决策为e(1),e(R),则多分类器融合为(1),()(1),()(1),()(1),()(1),()(),if0()1,ee kee Ree Ree Ree RNTTeMx,else(10-8)这里是一个门限值(01),用于控制最终决策的可靠性。第10章多分类器融合10.3基于基于Bayes理论的多分类器融合理论的多分类器融合本节讨论基于Bayes理论的多分类器融合,包括合成规则和合成方法。10.3.1基于基于Bayes理论的多分类器合成规则理论的多分类器合成规则假设有R个分类器,对于给定的模式x,每个分类器把模式x表示为相应的特征

19、(或度量)向量。不妨用xi表示第i个分类器ei输出的特征向量。类别k的先验概率为P(k),在模式x属于类别k为真的条件下,特征向量xi的概率密度函数为p(xi|k)(i=1,2,R;k=1,2,M)。第10章多分类器融合根据最大后验概率准则,给定特征向量xi(i=1,2,R),模式x应该划分到具有最大后验概率的类别j中,即如果1212(|,)max(|,)jRkRkPPx xxx xx(10-9)则jx(10-10)式（10-9）和（10-10）表明，为了利用所有可能的信息进行决策，必须根据所有的特征向量计算各种假设的后验概率。由Bayes公式，式（10-9）中的后验概率可以写成第10章多分类

20、器融合12121212121(,|)()(,|)()(|,)(,)(,|)()RkkRkkkRMRRiiipPpPPppPx xxx xxx xxx xxx xx12121212121(,|)()(,|)()(|,)(,)(,|)()RkkRkkkRMRRiiipPpPPppPx xxx xxx xxx xxx xx(10-11)第10章多分类器融合其中:p(x1,x2,xR)为x1,x2,xR的联合(无条件)概率密度;p(x1,x2,xR|k)为在模式 x属于类别k为真的条件下特征向量x1,x2,xR的联合概率密度。一般地,联合概率密度p(x1,x2,xR|k)较难得到。下面将利用每个分类器

21、的信息来简化式(10-11),并得到实用的融合策略。第10章多分类器融合1.积规则积规则假设在模式x属于类别k(k=1,2,M)为真的条件下,特征向量x1,x2,xR是相互独立的,即121(,|)(|)RRkikippx xxx(10-12)把式（10-12）代入式（10-11），可得11211()(|)(|,)()(|)RkikikRRmjijjiPpPPpxx xxx(10-13)第10章多分类器融合把式(10-13)代入式(10-9),则得到判决规则:如果 11()(|)max()(|)RRjijkikkiiPpPpxx(10-14)则jx(10-15)考虑到(|)()(|)()kiii

22、kkPppPxxx(10-16)第10章多分类器融合把式（10-16）代入式（10-14），利用各分类器的后验概率，得到判决规则：如果 1111(|)()max(|)()RRRRjijkikkiiPPPPxx(10-17)则jx(10-18)第10章多分类器融合式(10-17)和式(10-18)给出的判决规则称为积规则。积规则组合各分类器的后验概率,量化了假设的似然度。2.和规则和规则在式(10-17)中,进一步把后验概率P(j|xi)表示为(|)()(1)kikkiPPx(10-19)其中，ki0,则称A为证据的焦元(Focus Element),所有焦元的集合称为核。定义定义10.32上的

23、信任函数Bel(Belief Function)与似真函数Pl(Plausibility Function)定义为()()BABel Am BA(10-59)()()1()BAPl Am BBel AA (10-60)第10章多分类器融合(10-63)其中,为A的补集。信任函数Bel(A)表示证据全部给予命题A的支持程度,似真函数Pl(A)表示证据不反对(不怀疑)命题A的程度。信任函数Bel满足如下条件:ABel()=0(10-61)(10-62)Bel()=0111,()(1)()IniIni IIBel AABelA第10章多分类器融合其中:n为任意正整数;A1,An为的任意n个子集;|I

24、|表示集合I中的元素的个数。特别地,n=2,此时 21AA()()1Bel ABel AA (10-64)Bel(A)与Pl(A)满足:()()Bel APl A(10-65)区间Bel(A),Pl(A)构成证据不确定区间,表示命题的不确定程度,如图10-5所示。第10章多分类器融合图10-5 信息的不确定性表示第10章多分类器融合定义定义10.4共性函数(Commonality Function)定义为()()ABQ Am BA(10-66)Q(A)是所有以命题A为前提的命题的基本概率赋值函数之和。Q(A)可以理解为,在证据出现后,命题A作为前提(原因)的支持程度。基本概率赋值函数、信任函数

25、、似真函数与共性函数可以相互推导出来,它们包含的信息量是一样的。除了式(10-60)外,还有如下结果:第10章多分类器融合()(1)()A BBAm ABel BA (10-67)()(1)()BBABel AQ BA (10-68)()(1)()BBAQ ABel BA (10-69)第10章多分类器融合3.Dempster合成公式合成公式证据理论提供了一个有用的合成公式,它是反映证据的联合作用的一个规则,使人们能够合成多个证据源提供的证据。给定同一辨识框架上几个基于不同证据的信任函数Bel1,Bel2,Beln,如果这些证据相互独立,且不完全冲突,那么,可以利用Dempster合成公式计算

26、出一个新的信任函数Bel=Bel1Bel2Beln,作为在这些证据的联合作用下产生的信任函数。第10章多分类器融合设有n个相互独立的证据,其对应的基本概率赋值函数分别为m1,m2,mn,它们合成后得到新的基本概率赋值函数为12nmmmm，Dempster合成公式为：m()=0(10-70)1211221()()()(),1iiiniininAAAAmAm AmAmAAAk (10-71)1211221()()()(),1iiiniininAAAAmAm AmAmAAAk 第10章多分类器融合其中iniiAAAinniiAmAmAmk21)()()(2211(10-72)k为证据之间的冲突概率,

27、反映了证据冲突的程度。系数1/(1-k)称为归一化因子,它的作用就是避免在合成时将非0的概率赋给空集。利用基本概率赋值函数m,可以计算相应的信任函数Bel、似真函数Pl与共性函数Q。此外,共性函数Q满足:第10章多分类器融合11()()1niiQAQ AkA (10-73)Dempster合成公式满足交换律和结合律,即 1221mmmm(10-74)123123mmmmmm(10-75)第10章多分类器融合10.4.2度量层的多分类器融合度量层的多分类器融合假设有R个信息源或分类器,对同一对象(模式)x进行观测,第i个信息源的观测为xi(i=1,2,R)。模式分类的目的就是,把给定的模式x划分

28、到M个互不相交的模式类集合1,2,M中的一个。第10章多分类器融合1.证据模型的构造证据模型的构造每个信息源可以看成一个证据,相应的辨识框架为=1,2,M。假设观测xi对应一组信任度量其中,0表示xi支持j的信任程度。J(0)ij越大,xi支持j的信任越多。J(0)ij可以是各种形式的度量,例如,与距离有关的函数、概率论中的概率或模糊集合论中的隶属度等。(0)(0)(0)12,iiiiMEJJJ(0)0ijJ第10章多分类器融合对于证据xi,所有可能的焦元可以选择为i1,i2,ij,j=1,2,M,相应的基本概率分配函数定义为(1)121(,)iji jiiiijiJJmJ(10-76)其中:

29、i=1,2,R;j=1,2,M。第10章多分类器融合2.判别决策的确定判别决策的确定采用证据理论合成公式合成基本概率分配函数mi(i=1,2,R),得到一个综合的基本概率分配函数m,进而可以计算出相应的信任函数、似真函数和共性函数。给定一个辨识框架,有很多规则可以用来决策,例如,最大化基本概率分配函数、信任函数、似真函数或共性函数。第10章多分类器融合下面假设采用Dempster合成公式进行合成,并以最大化共性函数进行决策。对应于基本概率分配函数m与mi,单个元素的集合j(j=1,2,M)的共性函数分别为()()jjAQm A(10-77)()()jijiAQm A(i=1,2,R)(10-7

30、8)第10章多分类器融合由式(10-73)可知,它们满足:11()()1RjijiQQk(10-79)其中121122()()()iiiRiiRiRAAAkm AmAmA(10-80)k为证据之间的冲突概率。假设j在i中排在第h位,即j=ih,那么,对于基本概率分配函数mi,包含j的所有可能的焦元及其基本概率分配函数值为 第10章多分类器融合(1)111,ihi hiiihhiJJJ(1)(2)111,i hi hiiihhiJJJ 111,iiiiMMMiJJ第10章多分类器融合因此 1()()jihijiAiJQm AJ(10-81)由ijh可得，(0)ihijJJ，从而(0)1()iji

31、jiJQJ(10-82)第10章多分类器融合所以(0)(0)111111()1RRRjijijiiiiQJWJkJ(10-83)其中,常数 11111RiiWkJ与j无关。此时,采用最大化 共性函数进行决策等价于选择l使得(0)(0)111maxRRilijj MiiJJ，即第10章多分类器融合(0)11argmaxargmax()jRijljj MilJQ(10-84)进一步,若J(0)ij为概率测度,则式(10-84)等价于最大后验概率准则;若J(0)ij为模糊隶属度,则式(10-84)等价于某种最大模糊隶属度决策。第10章多分类器融合10.4.3决策层的多分类器融合决策层的多分类器融合

32、1.证据模型证据模型假设R个分类器e1,e2,eR对同一输入样本(模式)x进行分类,得到R个证据ek(x)=jk,k=1,2,R,相应的辨识框架为=1,2,M。其中,ek(x)=jk表示分类器ek把x划分到类jk中;jkM+1;ek(x)=M+1表示ek拒识x。第10章多分类器融合用(k)r和(k)s分别表示ek的正确识别率和误识率。由于引入了拒识,一般地,(k)r+(k)s1。因为ek存在误识,所以,证据ek(x)=jk存在不确定性。当ek(x)=jk,jk时,xjk为真的信任程度为(k)r,xjk不为真的信任程度为(k)s;当ek(x)=M+1时,ek不能提供任何单个类别jk的信息,从而可

33、以看成完全支持。因此,对于证据ek(x)=jk,我们定义2上的基本概率分配函数mk如下:第10章多分类器融合(1)若ek(x)=M+1,则mk只有一个焦元,mk()=1。(2)若jk,则mk可能有3个焦元:jk,jkC=jk和,并且,mk(jk)=(k)r,mk(jkC)=(k)s,mk()=1(k)r(k)s。决策层的多分类器融合就是,根据这R个证据,把给定的模式x划分到1,2,M中的一个,或者拒识x。第10章多分类器融合类似地,采用证据理论合成公式合成基本概率分配函数mi(i=1,2,R),得到一个综合的基本概率分配函数m,进而可以计算出相应的信任函数、似真函数和共性函数。给定一个辨识框架

34、,决策规则可以采用最大化基本概率分配函数、信任函数、似真函数或共性函数。下面假设采用Dempster合成公式进行合成,并以最大化信任函数进行决策。第10章多分类器融合2.快速合成算法快速合成算法 首先去掉一些不必要的证据。若ek(x)=M+1,相应地,mk()=1,这些证据对合成的结果没有影响。去掉这些证据,假设剩下R(R)个证据ek(x)=jk,k=1,2,R,jk。不失一般性,进一步排除如下三种特殊情形:(1)R=0。说明所有的R个分类器都拒识x,那么最终的决策也是拒识x。(2)若存在某个分类器ek的正确识别率(k)r=1,即ek能够绝对正确地识别任何输入模式,那么,其他的分类器就没有必要

35、存在了。第10章多分类器融合(3)若存在某个分类器ek的误识率(k)s=1,即ek总是做出错误的决策,分类器ek不能提供有用的信息,那么,去掉该证据。因此,下面只考虑R个证据ek(x)=jk,jk,k=1,2,R,分类器ek的正确识别率和误识率分别为(k)r和(k)s,0(k)r1,0(k)s1。采用Dempster合成公式进行合成上述R个证据,需要验证它们的冲突概率不为1。为此,只需要验证存在一个组合X1X2XR,使得,m1(X1)m2(X2)mR(XR)0。第10章多分类器融合对于k=1,2,R,由0mk(jk)=(k)r1可知,mk(jkC)=(k)s0与mk()=1(k)r(k)s0至

36、少有一个成立。取X1=j1,对k=2,R,若jk=j1,则取Xk=jk,否则,Xk取jkC与中的一个,使得mk(Xk)0。这样,X1X2XR,且m1(X1)m2(X2)mR(XR)0。第10章多分类器融合直接采用Dempster合成公式进行合成,其计算复杂度随M呈指数递增,特别是分类器数目较大时,巨大的计算量将阻碍多分类器融合技术的使用。考虑到每个证据结构的特殊性,mk最多可能有3个焦元:jk、jkC和,结合Dempster合成公式满足交换率和结合率,下面给出一种Dempster合成公式的快速方法,其计算复杂度为O(M)。快速方法由两步组成:第一步把具有相同识别结果的分类器分成一组,并进行合成

37、,得到一个新的证据;第二步把各组合成得到的证据进行合成,得到最终的合成结果。第10章多分类器融合可以通过迭代的方式来合成这些证据对应的基本概率分配函数mk1,mk2,mkp,得到一个合成的基本概率分配函数mEk,即12123()kppEkkkkkkkmmmmmmmm(10-85)122kkmmm或，332kmmm，1kpEppkmmmm(10-86)第10章多分类器融合例如：1212211()()()()kkkkCCkjkjkjkjkmmmm1212()()()()1 1kkkkrssr(10-87)第10章多分类器融合112212()()()()222()()()(1)(1)kkkkkkrs

38、rsmk mmk (10-88)1222112211222()()()()()22()()()()()()(1)(1)kkkkjkjkjkkjkkkkkkrsrrsmk mmmk mmkk(10-89)1222112211222()()()()()22()()()()()()(1)(1)kkkkCCCCjkjkjkkjkkkkkksrsrsmk mmmk mmkk(10-90)第10章多分类器融合2()0mA，2,kkCjjA(10-91)值得注意的是,m2和mk1,mk2,mkp 一样具有相同的焦元:kj、kCj和,因此,可以类似地计算 31,kpEmmm31,kpEmmm对于r=3,p1,

39、p,迭代公式如下:。1111()()()()krkkrkrCCrjkjrjkjkmmmm(10-92)第10章多分类器融合(10-93)1()()()rrrrkmk mm 11()()()()()()kkrkrrkrjrrjkjkrkjrmk mmmk mm(10-94)11()()()()()()kkrkrrkCCCCrjrrjkjkrkjrmk mmmk mm(10-95)()0rm A，2,kkCjjA(10-96)第10章多分类器融合下一步就是合成R1个基本概率分配函数mEk,k=1,2,R1,得到最终合成的基本概率分配函数m,即 121REEEmmmm(10-97)进而利用m计算Be

40、l(k)和Bel(kC),k=1,2,M。当R1=M时,112,1,2,RjjjM ，112,Rjjj恰好是1,2,M的一个置换。当R1M时,构造MR1个简单证据,相应的基本概率分配函数为：()kEkejx第10章多分类器融合()1kEm，()0kkEjm，1()0kCEjm11,kRM()其中，11121RRMjjjjj12,Mjjj 即12,Mjjj是1,2,M的一个置换。此时,第10章多分类器融合12121111RRRMEEEEEEEEmmmmmmmmm计算信任函数的快速算法:023103102()(),if1()()(),if1&(),else1()kkkkkkkkkkkkEjECEj

41、EjjEjEjmmKKKRMmmbelK KRMkMmKKm(10-98)(其他)第10章多分类器融合0123101211012()(),if1()()()(),if&1()(),1()kkkkkkkkkkkkkkkkkCEjEjEjCEjEjCjEjEjEjmmKKKKRMmmmbelKKKRMk RmmKKKm else(10-99)(其他)第10章多分类器融合111()1()kkkkREjkEjmKm1211()kkREjkKm131()kkRCEjkKm(10-100)第10章多分类器融合123101211(1),if1(1),ifK KKRMKK KRM(10-101)其中,k=1,

42、2,M。上述算法的复杂度为O(M)。3.判别决策判别决策最后,利用信任函数进行决策。式(10-98)与式(10-99)中,12,Mjjj是1,2,M的一个置换,因此,利用式第10章多分类器融合(10-98)式(10-101)可以得到Bel(k)和Bel(kC),k=1,2,M。采用最大化信任函数进行决策,决策规则为 1,if()max()()1,elsejkk MjbelbeleM x(10-102)进一步,为了平衡误识率和拒识率,引入阈值,01,式(10-102)修正为 第10章多分类器融合1,if()max()()1,elsejkk MjbelbeleM x(10-103)式(10-102

43、)或式(10-103)没有考虑Bel(kC),k=1,2,M。其实,它们也包含对最终决策有用的信息。下面三个决策规则考虑了这些信息:1,if()max()|,()()1,elseCjkkk Mjbelbelk beleM x(10-104)第10章多分类器融合121,if()max()|,(),()()1,elseCjkkkk Mjbelbelk belbeleM x(10-105)1,ifmax()1,elsejkk MjddeM x(10-106)其中:01,1，,A BX，AB ，有第10章多分类器融合()()()()()g ABg Ag Bg A g B(10-110)当=0时,g-模

44、糊测度是一个概率测度。假设X=x1,x2,xn为一有限集合,令=2X,表示X的所有子集组成的集合。映射:xigi=g(xi),i=1,2,n,称为模糊密度函数。对于集合A=xi1,xi2,xim,其g模糊测度由下式给出:第10章多分类器融合1211111()11jjkmimmmmiiiiiiijjkjxAg Agg gg ggg 1211111()11jjkmimmmmiiiiiiijjkjxAg Agg gg ggg (10-111)其中,0。第10章多分类器融合由g(X)=1可得满足 11(1)niig(10-112)对于给定的gini=1,0gi1,0)。定义定义10.7(X,)为一可测

45、空间,函数h:X0,1为可测函数,函数h在集合上的关于模糊测度g的Sugeno模糊积分定义为AX第10章多分类器融合0,1()()sup min min(),()supmin(,()Ax EEXh xgh x g AEg AF 0,1()()sup min min(),()supmin(,()Ax EEXh xgh x g AEg AF(10-113)其中,F=xX|h(x)。第10章多分类器融合假设X=x1,x2,xn为一有限集合,=2X,h(xi)按降序排列,即h(x1)h(x2)h(xn),则函数h在集合X上的关于模糊测度g的Sugeno模糊积分可以由下式计算得到 1()()maxmin

46、(),()niiXih xgh xg A(10-114)其中,Ai=x1,x2,xi。第10章多分类器融合当测度具有可加性时,Sugeno模糊积分与Lebesgue积分不一致,于是Murofushi和Sugeno又提出了所谓的Choquet模糊积分。定义定义10.8h在X集上关于测度g的Choquet模糊积分定义为11()()()()()niiiXih xgg Ah xh x(10-115)其中:Ai=x1,x2,xi;h(x1)h(x2)h(xn);h(xn+1)=0。第10章多分类器融合10.6.3模糊积分在信息融合中的应用模糊积分在信息融合中的应用设x为一个待分类模式,S=1,2,M为类

47、别的集合,X=x1,x2,xn为n个信息源(分类器)的集合。1.模糊密度函数的确定模糊密度函数的确定模糊密度函数gi=g(xi)(i=1,2,n)表示信源信息的重要程度或分类器xi的分类能力。gi可以由专家设定或通过训练集估计给出,例如,分类器xi的识别率。下面给出一种gi的取值方法。第10章多分类器融合假设分类器xi的识别率为pi,wi0,1为主观权值,其中,pi越大,wi越大。gi可以由下式计算给出:1niiijjgw pp(i=1,2,n)(10-116)2.模糊积分的计算模糊积分的计算定义置信度函数h(k):X0,1,h(k)(xi)表示分类器xi提供输入模式x属于类k的置信度,即分类

48、器xi认为输入模式x属于类k的隶属程度,k=1,2,M,i=1,2,n。h(k)在X集上关于测度g的Sugeno模糊积分或Choquet 模糊积分为 第10章多分类器融合()()()1()()maxmin(),()nkkkiiXiChxghxg A(k=1,2,M)(10-117)或()()()()11()()()()nkkkkiiiXiChgg Ahxhx(k=1,2,M)(10-118)第10章多分类器融合其中，()()()12()()()kkknhxhxhx()1()0knhx12,iiAx xxg(Ai)是根据模糊密度gini=1计算得到的g-模糊测度,可以由如下的迭代公式得到:第10

49、章多分类器融合111()()g Agxg(10-119)11()()()iiiiig Agg Agg A(i=2,3,n)(10-120)一方面,h(k)(xi)表示分类器xi提供输入模式x属于类k的置信度,现假定用中分类器来评价输入模式x,那么,最安全(保守)的决策中,模式x属于类k的置信度可以表示为 EX第10章多分类器融合()()()min()ikkixEWEhx(10-121)另一方面,gi=g(xi)表示分类器xi的重要程度或分类能力,那么g(E)表示分类器子集合E的重要程度或分类能力。此时,()min min(),()ikixEhxg E表示输入模式x属于类k的可能性()min()

50、ikixEhx与分类器子集合E的分类能力g(E)的一致性程度。第10章多分类器融合因此,Sugeno模糊积分()()()()sup min min(),()kkXx EEXhxghx g E(10-122)就是输入模式x属于类k的可能性与分类器子集合的分类能力的最大一致性程度,从而,()()()kXhxg 可以用来表示模式 x属于类k的融合置信度。3.决策规则决策规则选择C(k)(k=1,2,M)中最大值C(k0),此时,k0为输出类别。第10章多分类器融合10.7基于决策模板的多分类器融合基于决策模板的多分类器融合基于决策模板的多分类器融合也称为决策模板法,是一种简单、直接、稳健的融合方法。