模式特征的提取与选择

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,模式特征的提取与选择,模式特征的提取与选择,在一个较完善的模式识别系统中，或者明显地或者隐含地要有特征提取与选择技术环节，通常其处于对象特征数据采集和分类识别两个环节之间，特征提取与选择方法（或质量）的优劣极大地影响着分类器的设计和性能，它是模式识别的核心问题之一。,模式特征的提取与选择,1 概述,在实际问题中，常常不容易找到那些最重要的特征，或受条件限制不能对它们进行测量，这就使特征选择和提取的任务复杂化而成为构造模式识别系统最困难的任务之一。,特征提取和选择的基本任务是如何从许多特征中找出那些最易得且有效的特征,从而实现特征空间维数的压缩.,模式特征的提取与选择,1 概述,虽然特征的提取和选择在模式识别中占有重要地位,但迄今没有一般方法,大多数的方法都是面向问题的.对于不同的模式识别问题可以 有不同的特征提取和选择方法,而且即使对于同一模式识别问题往往也可能用不同方法,所以要对这些方法作一般的评价是困难的.,模式特征的提取与选择,1 概述,模式特征并非提取得越多越好.在实际工作中,往往会发现当特征的数目达到某个限度后,不但不能改善分类器的性能,反而会使它的工作恶化.其原因在于用以设计分类器的样本数目是有限的.为了使模式识别的结果满意,在增加特征的同时,必须增加供学习的样本数量.,模式特征的提取与选择,1 概述,(1)用一定数量的样本估计出来的参数设计Bayes分类器时,随着维数的增加要求样本数急剧增加,这样才能保证一定的错误率.,模式特征的提取与选择,1 概述,(2)在用线性判别函数来划分模式空间时,一般要用一组样本来决定划分区域的超平面.当增加维数时,样本数应有更多的增加才能保持原有的超平面容度.,模式特征的提取与选择,1 概述,(3)在邻近法与集群分析中,经常应用的是群内离散度矩阵S,w,为了使用行列式准则,离散度矩阵必须是非奇异的,这 就要求样本数与群数之差应远大于维数.,模式特征的提取与选择,1 概述,几个基本概念,特征形成:,根据被识别的对象产生一组基本特征,它可以是计算出来的(当识别对象是波形或数字图像时),也可以是用仪表或传感器测量出来的(当识别对象是实物或某过程时),这样产生出来的特征叫做原始测量(一次测量),原始测量的直接结果或间接结果称为原始特征.,模式特征的提取与选择,1 概述,几个基本概念,特征提取:,原始特征的数量可能很大,或者说样本是处于一个高维空间中,通过映射(或变换)的方法可以用低维空间来表示样本,这个过程叫特征提取.映射后的特征叫二次特征,它们是原始特征的某种组合.变换A:YX称为特征提取器.,模式特征的提取与选择,1 概述,几个基本概念,特征选择:,从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的,这个过程叫特征选择.,有时特征提取和选择并不是截然分开的，在具体的模式识别问题中也可以结合使用。,模式特征的提取与选择,2 类别可分性判据,把一个高维空间变换为低维空间的映射有很多，哪种映射对分类最有利，需要一个比较标准，即类别可分性判据，这些判据应能反映各类在特征空间中的分布情况，应能刻画各特征分量在分类识别中的重要性或贡献。,以分类器的错误概率做为标准有难度.,模式特征的提取与选择,2 类别可分性判据,与错误概率,(,或其界限,),有单调关系,使判据取最值时,错误概率也较小,.,当特征相互独立时,判据具有可加性,.,判据须有度量特性,(,非负性,对称性,).,自身有单调性,(,加入新特征时,判据不减小,).,类别可分性判据应满足的几个要求:,模式特征的提取与选择,2 类别可分性判据,点与点的距离,点到点集的距离,类内距离,(,类内均方欧氏距离,d,2,),类内离差矩阵,S,w,(d,2,=,TrS,w,),两类之间的距离,各类间的总均方距离,总的类内类间及总体离差矩阵,S,T,=,S,w,+S,T,基于几何距离的可分性判据,模式特征的提取与选择,2 类别可分性判据,J1=TrS,w,-1,S,B,J2=,TrS,B,/TrS,w,J3=TrS,w,-1,S,T,J4=|S,T,|/|S,W,|=|S,w,-1,S,T,|,基于几何距离的可分性判据,上述各种判据存在关联性,其中一些判据如,J1,J4,具有非奇异线性变换不变性,.,它们本质相似,但性能可能不同,.,模式特征的提取与选择,2 类别可分性判据,基本原则,Jp,非负,.,当两类概率密度函数完全不重叠时,Jp,趋于无穷大,.,当两类概率密度函数完全重合时,Jp,为零,.,相对于两个概率密度具有对称性,.,基于类概率密度函数的可分性判据,模式特征的提取与选择,2 类别可分性判据,判据举例,Bhattacharyya,判据,J,B,=-lnSp(x|w,1,)p(x|w,2,),1/2,dx,Chernoff,判据,J,C,=-lnSp(x|w,1,),s,p(x|w,2,),1-s,dx,散度,(,总的平均可分性信息,),J,D,=I,12,(x)+I,21,(x),基于类概率密度函数的可分性判据,模式特征的提取与选择,2 类别可分性判据,I,12,(x)=E,1,lnp(x|w,1,)/p(x|w,2,),基于类概率密度函数的可分性判据,I,21,(x)=E,2,lnp(x|w,2,)/p(x|w,1,),模式特征的提取与选择,2 类别可分性判据,原理：选择使后验熵最小的那些特征用于分类识别。,基于后验概率的可分性判据,J,H,=E,x,-S,p,(w,i,|x)log,p,(w,i,|x),J,H,s,=E,x,H,s,(p,1,p,2,p,c,),H,s,=(2,1-s,-1)S(p,i,s,)-1,p,i,=p(w,i,|x),模式特征的提取与选择,3 基于可分性判据进行变换的特征提取,S,w,和S,B,分别为原始特征空间中类内和类间离差矩阵,S,w,*,和S,B,*,分别为变换特征空间中类内与类间离差矩阵,基于离差矩阵的特征提取,S,w,*,=W,T,S,w,W,S,B,*,=W,T,S,B,W,模式特征的提取与选择,3 基于可分性判据进行变换的特征提取,若W为非奇异矩阵,则,J1=TrS,w,-1,S,B,是不变的.,基于离差矩阵的特征提取,因此,只需求出S,w,-1,S,B,的所有特征值,选其较大的d个,以其特征向量为列向量构造W即可使J1最大.,模式特征的提取与选择,3 基于可分性判据进行变换的特征提取,由于S,w,是对称正定矩阵,故有非奇异矩阵A,使A,T,S,w,A=I,取U=AV,其中V为标准正交矩阵,则U为非奇异矩阵,且使U,T,S,T,U为对角阵.U,T,S,w,U为单位阵.,从而可知U及U,T,S,T,U分别为S,w,-1,S,T,的特征矢量矩阵及特征值对角阵.,进而可得J4为特征值的某种和,同理只需要针对较大的特征值构造W即可.,基于离差矩阵的特征提取,模式特征的提取与选择,4 最佳鉴别矢量的提取,前面依据类内,类间及总离差矩阵构造可分性判据求最佳变换矩阵,其特点是整个最佳坐标系在形式上是一起求出的,但也可以用单个分量的类间类内距离比作为准则,逐个求出最佳坐标系的各轴矢量.,模式特征的提取与选择,4 最佳鉴别矢量的提取,Fisher鉴别矢量及鉴别平面,在设计分类器时,在适当保证分类识别正确率的条件下,为简便或为可实现性,常要求降低维数,或有时为便于显示,常首先要求模式的维数是1或2,这就要求将目标的原始n维特征矢量映射成一维标量或二维矢量.,模式特征的提取与选择,4 最佳鉴别矢量的提取,Fisher鉴别矢量及鉴别平面,要将高维模式映射成二维模式,需要两个正交矢量.这时除了Fisher鉴别矢量u,1,外,还要求出第二个矢量u,2,.因此可用u,1,T,u,2,=0作为约束条件使J,F,(u,2,)最大,即,Z=max(u,2,T,S,B,u,2,)/(u,2,T,S,w,u,2,)-ku,1,T,u,2,模式特征的提取与选择,4 最佳鉴别矢量的提取,最佳鉴别矢量集,设u1是使J,F,(u,i,)取最大的Fisher最佳鉴别矢量,且u,1,已规格化,其模长为1,则单位Fisher最佳鉴别矢量u,1,是F-Sammon最佳鉴别矢量集中的第一个矢量.该矢量集中的第i个鉴别矢量u,i,通过解一个最优化问题而求得.,模式特征的提取与选择,4 最佳鉴别矢量的提取,最佳鉴别矢量集,MaxJ,F,(u,i,),s.t.u,i,T,u,j,=0,j=1,2,i-1.,|u,i,|=1,令U=(u,1,u,2,u,r,),则变换,y=U,T,x,称为F-S变换(FST).Fisher是r=2特例.,模式特征的提取与选择,5 离散K-L变换,Karhunen-Loeve变换,取变换函数:y=g(x).为使变换后的特征还能很好的体现原有特征,作估计量,x(m)=S,m,y,i,W,i,+S,m+1,b,i,W,i,x(m)=x-x(m),e,2,(m)=E|,x(m)|,2,对于不保留的那些分量,应当用它们的平均值来代替,就能得到最佳的b,i,值.,模式特征的提取与选择,5 离散K-L变换,Karhunen-Loeve变换,为了进一步得到W,i,还需要在W,i,T,W,i,=1的条件下,找出使e,2,(m)最小的W,i,.为此使用拉格朗日乘数法即可.,每个特征在代表x方面的有效性由与它相对应的特征值所确定.尽可能保留特征值大的分量.x的协方差矩阵的特征向量使拉格朗日函数在正交归一的基向量的所有选择中最小.,模式特征的提取与选择,6 特征选择中的直接挑选法,次优搜索法,单独最优的特征选择法,计算各特征单独使用时的判据值并以递减排序,从而选取前d个分类效果最好的特征即可.,即使各特征是统计独立的,该法选出的特征也不一定是最优的特征组合.,模式特征的提取与选择,6 特征选择中的直接挑选法,次优搜索法,增添特征法(顺序前进法SFS),是一种最简单的自下而上的搜索方法,每次从未选入的特征中选择一个特征,使它与已选入的特征组合在一起时J最大,直到选入特征数目达到指定的维数为止.,一般好于单独最优选择法,主要缺点是某特征一旦选入,就无法删除.该法可推广.,模式特征的提取与选择,6 特征选择中的直接挑选法,次优搜索法,剔减特征法(顺序后退法SBS),是一种最简单的自上而下的搜索方法,从全部特征开始每次剔除一个特征,所剔除的特征应使尚保留的特征组合的J最大.,计算量大于增添特征法,可推广.,模式特征的提取与选择,6 特征选择中的直接挑选法,次优搜索法,增减法(l-r法),为克服SFS和SBS中某特征一旦选入或剔除就不能再考虑的缺点,可在选择过程中加入局部回溯,例如在第k步可先用SFS对已选入的k个特征再一个一个地加入新特征到k+l,然后用SBS一个个地剔除r个.,可推广.,模式特征的提取与选择,6 特征选择中的直接挑选法,最优搜索法,分支定界法(BAB算法)原理,