模式特征的提取与选择

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