模式特征的提取与选择.ppt

《模式特征的提取与选择.ppt》由会员分享，可在线阅读，更多相关《模式特征的提取与选择.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模式特征的提取与选择现在学习的是第1页，共34页模式特征的提取与选择在在一一个个较完完善善的的模模式式识别系系统中中，或或者者明明显地地或或者者隐含含地地要要有有特特征征提提取取与与选择技技术环节，通通常常其其处于于对象象特特征征数数据据采采集集和和分分类识别两两个个环节之之间，特特征征提提取取与与选择方方法法（或或质量量）的的优劣劣极极大大地地影影响响着着分分类器器的的设计和和性性能能，它它是是模模式式识别的的核核心心问题之一。之一。现在学习的是第2页，共34页模式特征的提取与选择1 概述概述在在实际问题中中，常常常常不不容容易易找找到到那那些些最最重重要要的的特特征征，或或受受条条件件限限

2、制制不不能能对它它们进行行测量量，这就就使使特特征征选择和和提提取取的的任任务复复杂化化而而成成为构构造造模模式式识别系系统最最困困难的任的任务之一。之一。特特征征提提取取和和选择的的基基本本任任务是是如如何何从从许多多特特征征中中找找出出那那些些最最易易得得且且有有效效的的特特征征,从而从而实现特征空特征空间维数的数的压缩.现在学习的是第3页，共34页模式特征的提取与选择1 概述概述虽然然特特征征的的提提取取和和选择在在模模式式识别中中占占有有重重要要地地位位,但但迄迄今今没没有有一一般般方方法法,大大多多数数的的方方法法都都是是面面向向问题的的.对于于不不同同的的模模式式识别问题可可以以

3、有有不不同同的的特特征征提提取取和和选择方方法法,而而且且即即使使对于于同同一一模模式式识别问题往往往往也也可可能能用用不不同同方方法法,所所以以要要对这些些方方法法作作一一般般的的评价是困价是困难的的.现在学习的是第4页，共34页模式特征的提取与选择1 概述概述模模式式特特征征并并非非提提取取得得越越多多越越好好.在在实际工工作作中中,往往往往会会发现当当特特征征的的数数目目达达到到某某个个限限度度后后,不不但但不不能能改改善善分分类器器的的性性能能,反反而而会会使使它它的的工工作作恶化化.其其原原因因在在于于用用以以设计分分类器器的的样本本数数目目是是有有限限的的.为了了使使模模式式识别的

4、的结果果满意意,在在增增加加特特征征的的同同时,必必须增增加加供学供学习的的样本数量本数量.现在学习的是第5页，共34页模式特征的提取与选择1 概述概述(1)用用一一定定数数量量的的样本本估估计出出来来的的参参数数设计Bayes分分类器器时,随随着着维数数的的增增加加要要求求样本本数数急急剧增增加加,这样才才能能保保证一一定定的的错误率率.现在学习的是第6页，共34页模式特征的提取与选择1 概述概述(2)在在用用线性性判判别函函数数来来划划分分模模式式空空间时,一一般般要要用用一一组样本本来来决决定定划划分分区区域域的的超超平平面面.当当增增加加维数数时,样本本数数应有有更更多多的的增增加才能

5、保持原有的超平面容度加才能保持原有的超平面容度.现在学习的是第7页，共34页模式特征的提取与选择1 概述概述(3)在在邻近近法法与与集集群群分分析析中中,经常常应用用的的是是群群内内离离散散度度矩矩阵Sw,为了了使使用用行行列列式式准准则,离离散散度度矩矩阵必必须是是非非奇奇异异的的,这 就就要要求求样本本数与群数之差数与群数之差应远大于大于维数数.现在学习的是第8页，共34页模式特征的提取与选择1 概述概述几个基本概念几个基本概念特征形成特征形成:根根据据被被识别的的对象象产生生一一组基基本本特特征征,它它可可以以是是计算算出出来来的的(当当识别对象象是是波波形形或或数数字字图像像时),),

6、也也可可以以是是用用仪表表或或传感感器器测量量出出来来的的(当当识别对象象是是实物物或或某某过程程时),),这样产生生出出来来的的特特征征叫叫做做原原始始测量量(一一次次测量量),),原原始始测量量的的直直接接结果果或或间接接结果果称称为原始特征原始特征.现在学习的是第9页，共34页模式特征的提取与选择1 概述概述几个基本概念几个基本概念特征提取特征提取:原原始始特特征征的的数数量量可可能能很很大大,或或者者说样本本是是处于于一一个个高高维空空间中中,通通过映映射射(或或变换)的的方方法法可可以以用用低低维空空间来来表表示示样本本,这个个过程程叫叫特特征征提提取取.映映射射后后的的特特征征叫叫

7、二二次次特特征征,它它们是是原原始始特特征征的的某某种种组合合.变换A:YXA:YX称称为特征提取器特征提取器.现在学习的是第10页，共34页模式特征的提取与选择1 概述概述几个基本概念几个基本概念特征选择特征选择:从从一一组特特征征中中挑挑选出出一一些些最最有有效效的的特特征征以以达达到到降降低低特特征征空空间维数数的的目目的的,这个个过程程叫特征叫特征选择.有有时特特征征提提取取和和选择并并不不是是截截然然分分开开的的，在在具具体体的的模模式式识别问题中中也也可可以以结合合使使用。用。现在学习的是第11页，共34页模式特征的提取与选择2 类别可分性判据类别可分性判据把把一一个个高高维空空间

8、变换为低低维空空间的的映映射射有有很很多多，哪哪种种映映射射对分分类最最有有利利，需需要要一一个个比比较标准准，即即类别可可分分性性判判据据，这些些判判据据应能能反反映映各各类在在特特征征空空间中中的的分分布布情情况况，应能能刻刻画画各各特特征征分分量量在在分分类识别中的重要性或中的重要性或贡献。献。以分以分类器的器的错误概率做概率做为标准有准有难度度.现在学习的是第12页，共34页模式特征的提取与选择2 类别可分性判据类别可分性判据l与与错误概概率率(或或其其界界限限)有有单调关关系系,使使判判据取最据取最值时,错误概率也概率也较小小.l当特征相互独立当特征相互独立时,判据具有可加性判据具有

9、可加性.l判据判据须有度量特性有度量特性(非非负性性,对称性称性).).l自自身身有有单调性性(加加入入新新特特征征时,判判据据不不减减小小).).类别可分性判据可分性判据应满足的几个要求足的几个要求:现在学习的是第13页，共34页模式特征的提取与选择2 类别可分性判据类别可分性判据l点与点的距离点与点的距离l点到点集的距离点到点集的距离l类内距离内距离(类内均方欧氏距离内均方欧氏距离d d2 2)l类内离差矩内离差矩阵S Sw w(d(d2 2=TrS=TrSw w)l两两类之之间的距离的距离l各各类间的的总均方距离均方距离l总的的类内内类间及及总体离差矩体离差矩阵 S ST T=S=Sw

10、w+S+ST T基于几何距离的可分性判据基于几何距离的可分性判据现在学习的是第14页，共34页模式特征的提取与选择2 类别可分性判据类别可分性判据lJ1=TrSJ1=TrSw w-1-1S SB B lJ2=TrSJ2=TrSB B/TrS/TrSw w lJ3=TrSJ3=TrSw w-1-1S ST T lJ4=|SJ4=|ST T|/|S|/|SW W|=|S|=|Sw w-1-1S ST T|基于几何距离的可分性判据基于几何距离的可分性判据l上上述述各各种种判判据据存存在在关关联性性,其其中中一一些些判判据据如如J1,J4J1,J4具具有有非非奇奇异异线性性变换不不变性性.它它们本本质

11、相似相似,但性能可能不同但性能可能不同.现在学习的是第15页，共34页模式特征的提取与选择2 类别可分性判据类别可分性判据基本原基本原则lJpJp非非负.l当当两两类概概率率密密度度函函数数完完全全不不重重叠叠时,Jp,Jp趋于无于无穷大大.l当当两两类概概率率密密度度函函数数完完全全重重合合时,Jp,Jp为零零.l相相对于两个概率密度具有于两个概率密度具有对称性称性.基于基于类概率密度函数的可分性判据概率密度函数的可分性判据现在学习的是第16页，共34页模式特征的提取与选择2 类别可分性判据类别可分性判据判据判据举例例lBhattacharyyaBhattacharyya判据判据J JB B

12、=-lnSp(x|w=-lnSp(x|w1 1)p(x|w)p(x|w2 2)1/21/2dxdxlChernoffChernoff判据判据J JC C=-lnSp(x|w=-lnSp(x|w1 1)s sp(x|wp(x|w2 2)1-s1-sdxdxl散度散度(总的平均可分性信息的平均可分性信息)J JD D=I=I1212(x)+I(x)+I2121(x)(x)基于基于类概率密度函数的可分性判据概率密度函数的可分性判据现在学习的是第17页，共34页模式特征的提取与选择2 类别可分性判据类别可分性判据I I1212(x)=E(x)=E1 1lnp(x|wlnp(x|w1 1)/p(x|w)

13、/p(x|w2 2)基于基于类概率密度函数的可分性判据概率密度函数的可分性判据I I2121(x)=E(x)=E2 2lnp(x|wlnp(x|w2 2)/p(x|w)/p(x|w1 1)现在学习的是第18页，共34页模式特征的提取与选择2 类别可分性判据类别可分性判据原原理理：选择使使后后验熵最最小小的的那那些些特特征征用用于分于分类识别。基于后基于后验概率的可分性判据概率的可分性判据J JH H=E=Ex x-S-Sp p(w(wi i|x)log|x)logp p(w(wi i|x)|x)J JH Hs s=E=Ex xHHs s(p(p1 1,p,p2 2,p,pc c)H Hs s=

14、(2=(21-s1-s-1)S(p-1)S(pi is s)-1)-1p pi i=p(w=p(wi i|x)|x)现在学习的是第19页，共34页模式特征的提取与选择3 基于可分性判据进行变换的特征提取基于可分性判据进行变换的特征提取S Sw w和和S SB B分分别为原原始始特特征征空空间中中类内内和和类间离离差差矩矩阵,S,Sw w*和和S SB B*分分别为变换特特征征空空间中中类内与内与类间离差矩离差矩阵基于离差矩基于离差矩阵的特征提取的特征提取S Sw w*=W=WT TS Sw wW WS SB B*=W=WT TS SB BW W现在学习的是第20页，共34页模式特征的提取与选择

15、3 基于可分性判据进行变换的特征提取基于可分性判据进行变换的特征提取若若W W为非奇异矩非奇异矩阵,则J1=TrSJ1=TrSw w-1-1S SB B 是不是不变的的.基于离差矩基于离差矩阵的特征提取的特征提取因因此此,只只需需求求出出SSw w-1-1S SB B 的的所所有有特特征征值,选其其较大大的的d d个个,以以其其特特征征向向量量为列列向向量量构构造造W W即可使即可使J1J1最大最大.现在学习的是第21页，共34页模式特征的提取与选择3 基于可分性判据进行变换的特征提取基于可分性判据进行变换的特征提取由由于于S Sw w是是对称称正正定定矩矩阵,故故有有非非奇奇异异矩矩阵A,A

16、,使使A AT TS Sw wA=I,A=I,取取U=AV,U=AV,其其中中V V为标准准正正交交矩矩阵,则U U为非非奇奇异异矩矩阵,且且使使U UT TS ST TU U为对角角阵.U.UT TS Sw wU U为单位位阵.从从而而可可知知U U及及U UT TS ST TU U分分别为S Sw w-1-1S ST T的的特特征征矢矢量量矩矩阵及特征及特征值对角角阵.进而而可可得得J4J4为特特征征值的的某某种种和和,同同理理只只需需要要针对较大的特征大的特征值构造构造W W即可即可.基于离差矩基于离差矩阵的特征提取的特征提取现在学习的是第22页，共34页模式特征的提取与选择4 最佳鉴别

17、矢量的提取最佳鉴别矢量的提取前前面面依依据据类内内,类间及及总离离差差矩矩阵构构造造可可分分性性判判据据求求最最佳佳变换矩矩阵,其其特特点点是是整整个个最最佳佳坐坐标系系在在形形式式上上是是一一起起求求出出的的,但但也也可可以以用用单个个分分量量的的类间类内内距距离离比比作作为准准则,逐个求出最佳坐逐个求出最佳坐标系的各系的各轴矢量矢量.现在学习的是第23页，共34页模式特征的提取与选择4 最佳鉴别矢量的提取最佳鉴别矢量的提取FisherFisher鉴别矢量及矢量及鉴别平面平面在在设计分分类器器时,在在适适当当保保证分分类识别正正确确率率的的条条件件下下,为简便便或或为可可实现性性,常常要要求

18、求降降低低维数数,或或有有时为便便于于显示示,常常首首先先要要求求模模式式的的维数数是是1 1或或2,2,这就就要要求求将将目目标的的原原始始n n维特特征征矢矢量量映映射射成成一一维标量量或或二二维矢量矢量.现在学习的是第24页，共34页模式特征的提取与选择4 最佳鉴别矢量的提取最佳鉴别矢量的提取FisherFisher鉴别矢量及矢量及鉴别平面平面要要将将高高维模模式式映映射射成成二二维模模式式,需需要要两两个个正正交交矢矢量量.这时除除了了FisherFisher鉴别矢矢量量u u1 1外外,还要要求求出出第第二二个个矢矢量量u u2 2.因因此此可可用用u u1 1T Tu u2 2=0

19、=0作作为约束条件使束条件使J JF F(u(u2 2)最大最大,即即Z=max(uZ=max(u2 2T TS SB Bu u2 2)/(u)/(u2 2T TS Sw wu u2 2)-ku)-ku1 1T Tu u2 2 现在学习的是第25页，共34页模式特征的提取与选择4 最佳鉴别矢量的提取最佳鉴别矢量的提取最佳最佳鉴别矢量集矢量集设u1u1是是使使J JF F(u(ui i)取取最最大大的的FisherFisher最最佳佳鉴别矢矢量量,且且u u1 1已已规格格化化,其其模模长为1,1,则单位位FisherFisher最最佳佳鉴别矢矢量量u u1 1是是F-SammonF-Sammo

20、n最最佳佳鉴别矢矢量量集集中中的的第第一一个个矢矢量量.该矢矢量量集集中中的的第第i i个个鉴别矢矢量量u ui i通通过解解一一个个最最优化化问题而而求得求得.现在学习的是第26页，共34页模式特征的提取与选择4 最佳鉴别矢量的提取最佳鉴别矢量的提取最佳最佳鉴别矢量集矢量集 MaxJMaxJF F(u(ui i)s.t.u s.t.ui iT Tu uj j=0,j=1,2,i-1.=0,j=1,2,i-1.|u|ui i|=1|=1令令U=(uU=(u1 1,u,u2 2,u,ur r),),则变换y=Uy=UT Tx x称称为F-SF-S变换(FST).Fisher(FST).Fishe

21、r是是r=2r=2特例特例.现在学习的是第27页，共34页模式特征的提取与选择5 离散离散K-L变换变换Karhunen-LoeveKarhunen-Loeve变换取取变换函函数数:y=g(x).:y=g(x).为使使变换后后的的特特征征还能很好的体能很好的体现原有特征原有特征,作估作估计量量x(m)=Sx(m)=Sm my yi iW Wi i+S+Sm+1m+1b bi iW Wi ix(m)=x-x(m)x(m)=x-x(m)e e2 2(m)=E|(m)=E|x(m)|x(m)|2 2 对于于不不保保留留的的那那些些分分量量,应当当用用它它们的的平平均均值来代替来代替,就能得到最佳的就

22、能得到最佳的b bi i值.现在学习的是第28页，共34页模式特征的提取与选择5 离散离散K-L变换变换Karhunen-LoeveKarhunen-Loeve变换为了了进一一步步得得到到W Wi i,还需需要要在在W Wi iT TW Wi i=1=1的的条条件件下下,找找出出使使e e2 2(m)(m)最最小小的的W Wi i.为此此使使用用拉拉格朗日乘数法即可格朗日乘数法即可.每每个个特特征征在在代代表表x x方方面面的的有有效效性性由由与与它它相相对应的的特特征征值所所确确定定.尽尽可可能能保保留留特特征征值大大的的分分量量.x.x的的协方方差差矩矩阵的的特特征征向向量量使使拉拉格格朗

23、朗日日函函数数在在正正交交归一一的的基基向向量量的的所所有有选择中中最最小小.现在学习的是第29页，共34页模式特征的提取与选择6 特征选择中的直接挑选法特征选择中的直接挑选法次次优搜索法搜索法单独最独最优的特征的特征选择法法计算算各各特特征征单独独使使用用时的的判判据据值并并以以递减减排排序序,从而从而选取前取前d d个分个分类效果最好的特征即可效果最好的特征即可.即即使使各各特特征征是是统计独独立立的的,该法法选出出的的特特征征也也不一定是最不一定是最优的特征的特征组合合.现在学习的是第30页，共34页模式特征的提取与选择6 特征选择中的直接挑选法特征选择中的直接挑选法次次优搜索法搜索法增

24、添特征法增添特征法(顺序前序前进法法SFS)SFS)是是一一种种最最简单的的自自下下而而上上的的搜搜索索方方法法,每每次次从从未未选入入的的特特征征中中选择一一个个特特征征,使使它它与与已已选入入的的特特征征组合合在在一一起起时J J最最大大,直直到到选入入特特征征数数目达到指定的目达到指定的维数数为止止.一一般般好好于于单独独最最优选择法法,主主要要缺缺点点是是某某特特征征一旦一旦选入入,就无法就无法删除除.该法可推广法可推广.现在学习的是第31页，共34页模式特征的提取与选择6 特征选择中的直接挑选法特征选择中的直接挑选法次次优搜索法搜索法剔减特征法剔减特征法(顺序后退法序后退法SBS)S

25、BS)是是一一种种最最简单的的自自上上而而下下的的搜搜索索方方法法,从从全全部部特特征征开开始始每每次次剔剔除除一一个个特特征征,所所剔剔除除的的特特征征应使尚保留的特征使尚保留的特征组合的合的J J最大最大.计算量大于增添特征法算量大于增添特征法,可推广可推广.现在学习的是第32页，共34页模式特征的提取与选择6 特征选择中的直接挑选法特征选择中的直接挑选法次次优搜索法搜索法增减法增减法(l-r(l-r法法)为克克服服SFSSFS和和SBSSBS中中某某特特征征一一旦旦选入入或或剔剔除除就就不不能能再再考考虑的的缺缺点点,可可在在选择过程程中中加加入入局局部部回回溯溯,例例如如在在第第k k步步可可先先用用SFSSFS对已已选入入的的k k个个特特征征再再一一个个一一个个地地加加入入新新特特征征到到k+l,k+l,然然后用后用SBSSBS一个个地剔除一个个地剔除r r个个.可推广可推广.现在学习的是第33页，共34页模式特征的提取与选择6 特征选择中的直接挑选法特征选择中的直接挑选法最最优搜索法搜索法分支定界法分支定界法(BAB(BAB算法算法)原理原理现在学习的是第34页，共34页