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

《最近邻分类器置信度估计的理论分析.pdf》由会员分享，可在线阅读，更多相关《最近邻分类器置信度估计的理论分析.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、度 设有一模式分类器 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)Z cs(x1)cs(x2),(2)则称 fs(x)为 S 的广义置信度.显然,置信度

5、 cs(x)也是广义置信度.第43 卷 第 3 期科 学 通 报1998 年 2 月研究简报322 定理 对于模式分类器 S,给定拒识率 Pr,选择不同的拒识区域时,若拒识区域为 R=x cs(x)TH(Pr),则使分类器误识率 Pe 达到最低,其中 TH(Pr)是与 Pr 有关的一个门限值.推论 fs(x)是广义置信度,对于模式分类器 S,给定拒识率 Pr,选择不同的拒识区域时,拒识区域为 R=x fs(x)v 的概率:P(c1(x)v)=P(min(d1(x),d2(x)v)=P(d1(x)v 且d2(x)v)=P(d1(x)v)P(d2(x)v)=(1-P1(x-v,x+v)m(1-P2

6、(x-v,x+v)n,其中P1(y1,y2)=Qy2y1p(t X1)dt,P2(y1,y2)=Qy2y1p(t X2)dt,当 v 很小时,第43 卷 第 3 期科 学 通 报1998 年 2 月研究简报323 P(c1(x)v)=exp(mln(1-P1(x-v,x+v)+nln(1-P2(x-v,x+v)U exp(-mP1(x-v,x+v)-nP2(x-v,x+v)U exp(-2vmp(x X1)-2vnp(x X2).所以,c1(x)的概率密度q(v)=-dP(c1(x)v)/dv=2(mp(x X1)+np(x X2)exp(-2vmp(x X1)-2vnp(x X2).E(c1

7、(x)=Q+0vq(v)dv=1/(2mp(x X1)+2np(x X2)=1/2N(P(X1)p(x X1)+P(X2)p(x X2).由于 x 处样本概率密度是:p(x)=P(X1)p(x X1)+P(X2)p(x X2),所以E(c1(x)=1/(2Np(x).(7)()E(c2(x).类似上面的分析有:E(c2(x)=12Np(x)Q(x)+1Q(x)(推导过程略).(8)()E(c3(x).类似可得:E(c3(x)=2-Q(x)ln 1+1Q(x)-1Q(x)ln(1+Q(x)(推导过程略).(9)图 1 置信度同 E(c3(x)关系曲线 现在分析一 下上面 3 个 式子的物理 意义

8、:E(c1(x)只与 x 处的样本的总概率密度有关,与两类样本在 x 处的概率密度比并无直接关系,因而它不是c(x)的一种可靠的估计.E(c2(x)与各类样本在 x 处的概率密度比直接相关,但它仍然与概率密度的绝对大小有关,所以,它对 cs(x)的估计要比第一个式子好一些,但不是最优的.而 E(c3(x)只同两类概率密度的比值有关,它刚好同 cs(x)有相同的变化趋势(如图 1 所示),符合广义置信度的要求,可以说,c3(x)是在数学期望意义上的对 cs(x)的一个最优估计.当维数增加,类别增多时,表达式将更为复杂,但上面的物理概念仍然是适用的,限于篇幅,这里就不再赘述了.3 在手写字符识别中

9、的应用 本部分将通过手写数字识别的实验结果验证本文的结论.手写数字识别的训练样本和测试样本均选自美国国家标准技术局的 NIST 数据库 5.训练集有 12 000 字,测试集有 3 000字,抽取 288 维统计特征,分类器均采用最近邻分类器,分别用 3 个置信度估计公式决定拒识区域,得到表 1 的结果.在相同的拒识率下,用 c3(x)误识率最低,用 c1(x)误识率最高,这与上面的理论分析完全一致.第43 卷 第 3 期科 学 通 报1998 年 2 月研究简报324 表 1 3 个置信度估计公式在手写数字识别应用的对比结果拒识率/%误识率/%c1(x)误识率/%c2(x)误识率/%c3(x

10、)拒识率/%误识率/%c1(x)误识率/%c2(x)误识率/%c3(x)3.634.783.393.0118.34.670.650.619.9 4.781.531.4225.64.670.240.224 结论 本文对模式分类器的置信度给出了明确的定义,提出了广义置信度的概念和基于置信度的最佳拒识区域判定定理,更重要的是,首次从理论上说明了最近邻分类器的几个常用置信度估计公式的含义,指出了其中一个估计量的数学期望是广义置信度,因此是常用的几种置信度估计中最好的一种.手写数字识别的实验结果验证了本文的论断.参 考 文 献1 Lin Xiaofan,Ding Xiaoqing,Wu Youshou.

11、Handwritten numeral recognition using MFNN based adaptive multiexpert comb-ination.In:Werner B,ed.Proceedings of ICDAR.97,Los Alamitos,CA:IEEE Computer Society,1997.471 4742 Richard D M.Neural network classifiers estimate bayesian a posteriori probabilities.Neural computation,1991,2:461 4833 Fukunag

12、a K.Introduction to Statistical Pattern Recognition.New York:Academic,19724 Cover T M,Hart P E.Nearest neighbor pattern classification.IEEE Trans Inform Theory,1967,IT-13:21 275 Garris M D.NIST Form_based Handprint Recognition System.Gaithersturg,MD:National Institute of Standards and Tech-nology,19

13、94(1997-01-23 收稿,1997-09-22 收修改稿)广义系统的概周期解梁家荣 刘永清 高存臣(华南理工大学自动化系,广州 510641)摘要 研究了广义系统的概周期解问题,得到了广义系统的概周期解存在的判据,同时,给出了应用的实例.关键词 广义系统 概周期解 有界性由于广义系统理论在许多实际问题(如电网系统、经济系统、生态系统、化工系统等)有着广泛的应用,因而受到人们的日益重视.广义系统基础理论一直是人们关心的问题(如广义系统解的基本理论1、广义系统的稳定性2,3、边值问题4、周期解理论 5,6),但对广义系统概周期解的研究尚未见到,而在现实环境中,概周期现象是较为容易看到的一种现象,因此开展对广义系统概周期解理论研究是十分必要的.本文的研究在广义系统理论中尚属首次.1 准备工作 考虑广义系统Ex=A x+f(t),(1)其中 E,A I Rn n为常量矩阵,detE=0,f(t)I Rn是 t 的概周期向量函数,假设矩阵对 E,第43 卷 第 3 期科 学 通 报1998 年 2 月研究简报325