最近邻分类器置信度估计的理论分析.pdf

《最近邻分类器置信度估计的理论分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第43卷第3期科学通报1998年2月研究简报最近邻分类器置信度估计的理论分析林晓帆丁晓青吴佑寿(清华大学电子工程系,北京100084)摘要分类器的置信度是模式识别中的一个重要参量,它在决定拒识门限和多分类器集成中起着关键作用.最近邻分类器是最经典、最常见的非参数统计模式识别方法.但是,如何确定它的分类结果的置信度?最近距离与置信度有何联系?在以往的文献中没有对这个问题做明确理论分析.对几个常见经验公式进行了理论分析,并论证了其中一种置信度度量的数学期望符合本文提出的广义置信度的要求;同时,在手写字符识别的实际应用中,这种置信度度量在用于拒识判决时,确实表现出了比其他度量更好的性能.关

2、键词最近邻分类器置信度最优拒识手写字符识别对于任何一个模式分类器,除了希望它有尽可能高的识别率外,还希望能比较准确地估计它的分类结果的准确性,即置信度.置信度的主要用途有:(1)为拒识提供依据.在很多应用场合下,我们不仅希望识别率尽可能高,还希望误识率低,在一定的分类器下,这只能通过拒识部分样本实现.这样就需要决定拒识哪一部分样本,如果拒识的样本总是识别置信度最低的样本,系统的误识率就会在拒识率一定的情况下获得最大幅度的下降.(2)为多方案集成提供根据.现在,多方案集成是模式识别的一个重要趋势.人们已不再满足于简单的表决,而[1]希望能充分利用单个分类器的各种信息.其中,每个分类器的

3、置信度是一种重要信息.其意义是明显的:当多个分类器的结果不同时,应当选择置信度比较大的分类器的结果,至少应给予较大的权重.鉴于置信度的重要地位,基本上各种应用系统都以某种方式给出置信度的估计.对于基于前向神经网络的分类器,文献[2]中证明了在使用均方误差或交叉熵做代价函数时,神经网输出的期望值是各个类别的后验概率,这就为用神经网的输出估计置信度提供了强有力的理论根据.而对于早在60年代就已提出、并在几十年的模式识别实践中得到广泛应用的最近邻[3]分类器,尽管人们在实践中采用了各种置信度估计的经验公式,未见有对这些估计的理论阐述.本文将从理论上分析各种经验公式的内涵,并指出其中一种估计

4、量在物理概念上是优于其他估计量的.1分类器的置信度和广义置信度设有一模式分类器S,x为从输入模式提取的特征向量,S对x的判决为es(x)(为M个类别之一),x的真实类别为X(x),则定义es(x)正确的概率:cs(x)=P(es(x)=X(x))(1)为S在特征向量空间内点x处的置信度.需要指出的是,置信度与我们常说的识别正确率之间是局部与整体的关系,即:置信度反映的是S在某点的判决可信度,而识别正确率是置信度在x定义域上的平均值.同时,若存在函数fs(x)与cs(x)对特征空间内任意两点x1,x2总满足:fs(x1)>fs(x2)Zcs(x1)>cs(x2),(2)则称fs(x)为

5、S的广义置信度.显然,置信度cs(x)也是广义置信度.322第43卷第3期科学通报1998年2月研究简报定理对于模式分类器S,给定拒识率Pr,选择不同的拒识区域时,若拒识区域为R={xcs(x)

6、计在下面推导中设特征维数为1,类别为2,且训练样本总数N足够大.22文献[4]中证明当训练样本充分大时,条件错误率P(ex)=1-P(X1x)-P(X2x),S在x处的置信度是:2222cs(x)=1-P(ex)=P(X1x)+P(X2x)=(1+Q(x))/(1+Q(x)),(3)其中X1,X2是两个可能的类别,P(X1)和P(X2)是两类的先验概率,P(X1x)和P(X2x)是两个类别在x处的后验概率,p(xX1)和p(xX2)是两类的概率密度函数Q(x)=[P(X1)p(xX1)]/[P(X2)p(xX2)].(3)式完全由各类样本在x处的概率密度比决定,由于P(X1)和P(X

7、2)是已知的,如果能得到后验概率P(X1x)和P(X2x),我们就能直接算出cs(x).问题是,我们只有N个训练样本,可以获得的观测量是x距这些样本的距离.人们常用下面一些公式来估计cs(x):c1(x)=-min(d1(x),d2(x)),(4)c2(x)=d1(x)-d2(x),(5)c3(x)=1-min(d1(x),d2(x))/max(d1(x),d2(x)),(6)其中d1(x)是x与第一类样本的最近距离,d2(x)是x与第二类样本的最近距离.