模式识别第七章特征提取与选择.ppt

模式识别第七章特征提取与选择1现在学习的是第1页，共49页第七章第七章 特征提取与选择特征提取与选择 7.1 7.1 概概 述述2现在学习的是第2页，共49页 模式识别的三大核心问题模式识别的三大核心问题:第七章第七章 特征提取与选择特征提取与选择7.1概述概述特征数据采集特征数据采集分类识别分类识别特征提取与选择特征提取与选择 分类识别的正确率取决于对象的表示、训练学习分类识别的正确率取决于对象的表示、训练学习和分类识别算法，我们在前面各章的介绍中详细讨论和分类识别算法，我们在前面各章的介绍中详细讨论了后两方面的内容。本章介绍的特征提取与选择问题了后两方面的内容。本章介绍的特征提取与选择问题则是对象表示的一个关键问题。则是对象表示的一个关键问题。3现在学习的是第3页，共49页 通常在得到实际对象的若干具体特征之后，通常在得到实际对象的若干具体特征之后，再由这些原始特征产生出对分类识别最有效、再由这些原始特征产生出对分类识别最有效、数目最少的特征，这就是特征提取与选择的任数目最少的特征，这就是特征提取与选择的任务。从本质上讲，我们的目的是使在最小维数务。从本质上讲，我们的目的是使在最小维数特征空间中异类模式点相距较远（类间距离较特征空间中异类模式点相距较远（类间距离较大），而同类模式点相距较近（类内距离较大），而同类模式点相距较近（类内距离较小）。小）。第七章第七章 特征提取与选择特征提取与选择7.1概述概述4现在学习的是第4页，共49页7.1概述概述特征提取与选择的两个基本途径特征提取与选择的两个基本途径主要方法有：主要方法有：分支定界法分支定界法、用回归建模技术确定相关特征用回归建模技术确定相关特征等等方法。方法。（1 1）直接选择法：）直接选择法：当实际用于分类识别的特征数目当实际用于分类识别的特征数目d d 确定后，确定后，直接从已获得的直接从已获得的n n 个原始特征中选出个原始特征中选出d d 个特征个特征 ，使可分性判据，使可分性判据J J 的值满足下式：的值满足下式：dxxx,21J x xxJ xxxdiiid1212,max,式中式中 是是n 个原始特征中的任意个原始特征中的任意d 个特征个特征，上式表示直接寻找，上式表示直接寻找n 维特征空间中的维特征空间中的d 维子空间。维子空间。idiixxx,215现在学习的是第5页，共49页（2 2）变换法）变换法，在使判据，在使判据J J 取最大的目标下，对取最大的目标下，对n n 个原始个原始特征进行变换降维，即对原特征进行变换降维，即对原n n 维特征空间进行坐标变维特征空间进行坐标变换，然后再取子空间。换，然后再取子空间。7.1概述概述特征提取与选择的两个基本途径特征提取与选择的两个基本途径主要方法有：主要方法有：基于可分性判据的特征选择基于可分性判据的特征选择、基于误判基于误判概率的特征选择概率的特征选择、离散离散K-LK-L变换法变换法(DKLT)(DKLT)、基于决策界基于决策界的特征选择的特征选择等方法。等方法。6现在学习的是第6页，共49页7.2 7.2 类别可分性判据类别可分性判据第七章第七章 特征提取与选择特征提取与选择7现在学习的是第7页，共49页7.2 类别可分性判据类别可分性判据 为确立特征提取和选择的准则：引入类别可分性判据为确立特征提取和选择的准则：引入类别可分性判据，来刻划特征对分类的贡献。为此希望所构造的可分性，来刻划特征对分类的贡献。为此希望所构造的可分性判据满足下列要求：判据满足下列要求：构造可分性判据构造可分性判据(1)(1)与误判概率与误判概率(或误分概率的上界、下界或误分概率的上界、下界)有单调关系。有单调关系。(2)(2)当特征相互独立时，判据有可加性，即当特征相互独立时，判据有可加性，即 ：Jx xxJxi jdi jkdk(,)()121式中，式中，x xxd12,是对不同种类特征的测量值，是对不同种类特征的测量值，Ji j()表示使用括号中特征时第表示使用括号中特征时第i 类与第类与第j类可分性判据函数。类可分性判据函数。8现在学习的是第8页，共49页7.2 类别可分性判据类别可分性判据构造可分性判据构造可分性判据(3)(3)判据具有判据具有“距离距离”的某些特性，即的某些特性，即 ：Ji j 0，当，当ij时；时；Ji j 0，当，当ij时；时；JJi jji(4)(4)对特征数目是单调不减，即加入新的特征后，判据对特征数目是单调不减，即加入新的特征后，判据值不减。值不减。Jx xxJx xxxi jdi jdd(,)(,)121219现在学习的是第9页，共49页7.2 类别可分性判据类别可分性判据构造可分性判据构造可分性判据值得注意的是值得注意的是：上述的构造可分性判据的要求，即：上述的构造可分性判据的要求，即“单调单调性性”、“叠加性叠加性”、“距离性距离性”、“单调不减性单调不减性”。在。在实际应用并不一定能同时具备，但并不影响它在实际使实际应用并不一定能同时具备，但并不影响它在实际使用中的价值。用中的价值。10现在学习的是第10页，共49页7.2 类别可分性判据类别可分性判据7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据一般来讲，不同类的模式可以被区分是由于它们所属类一般来讲，不同类的模式可以被区分是由于它们所属类别在特征空间中的类域是不同的区域。别在特征空间中的类域是不同的区域。显然，区域重叠的部分越小或完全没有重叠，类别的显然，区域重叠的部分越小或完全没有重叠，类别的可分性就越好。可分性就越好。因此可以用距离或离差测度（散度）来构造类别的可因此可以用距离或离差测度（散度）来构造类别的可分性判据。分性判据。11现在学习的是第11页，共49页(一一)点与点的距离点与点的距离 d a babababkkkn(,)()()()/T1 2211 2(二二)点到点集的距离点到点集的距离),(1),()(12)(2ikNkiikaxdNaxdi用用均方欧氏距离均方欧氏距离表示表示7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据12现在学习的是第12页，共49页(三三)类内及总体的均值矢量类内及总体的均值矢量 ciiimPm1)(各类模式的总体均值矢量各类模式的总体均值矢量 iNkikiixNm1)()(1类的均值矢量：类的均值矢量：ci,2,1 Pi为相应类的先验概率，为相应类的先验概率，当用统计量代替先验概率当用统计量代替先验概率时，总体均值矢量可表示为：时，总体均值矢量可表示为：NllciNkikiciiiciixNxNmNNmPmi111)()(1)(1117.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据13现在学习的是第13页，共49页(四四)类内距离类内距离 )()(1)()()(T)()(12iikiikNkiimxmxNdi类内均方欧氏距离类内均方欧氏距离 类内均方距离也可定义为：类内均方距离也可定义为：iiNkNlilikiiicxxdNNd11)()(22),()1(1)(7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据14现在学习的是第14页，共49页(五五)类内离差矩阵类内离差矩阵 T)()()()(1)(1iikiikNkimxmxNSii)(2iSTrdi显然显然(六六)两类之间的距离两类之间的距离 ),(1),()(11)(22jlNkNlikjijixxdNNdij)()(1),()()(T)(11)(2jlikjlNkNlikjijixxxxNNdij7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据15现在学习的是第15页，共49页(七七)各类模式之间的总的均方距离各类模式之间的总的均方距离 ijNkNljlikjicjjciixxdNNPPxd11)()(2112),(121)(当取欧氏距离时，总的均方距离为当取欧氏距离时，总的均方距离为)()(121)()()(11T)()(112jlikNkNljlikjicjjciixxxxNNPPxdij7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据16现在学习的是第16页，共49页(八八)多类情况下总的类内、类间及总体离差矩阵多类情况下总的类内、类间及总体离差矩阵 iiNkiikiikiciiciiWmxmxNPSPS1T)()()()(11)(1类内离差类内离差ciiiiBmmmmPS1T)()()(类间离差类间离差总体离差总体离差 BWNlllTSSmxmxNS1T)(1易导出易导出dxTr SSTr SWBT2()7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据17现在学习的是第17页，共49页7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据JTr SSWB11JSSBW2lnJTr STr SBW3JSSSSSWBWTW418现在学习的是第18页，共49页7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据在特征空间中，当类内模式较密聚，而不同类的模在特征空间中，当类内模式较密聚，而不同类的模式相距较远时，从直觉上我们知道分类就较容易，式相距较远时，从直觉上我们知道分类就较容易，由各判据的构造可知，这种情况下所算得的判据值由各判据的构造可知，这种情况下所算得的判据值也较大。由判据的构造我们还可以初步了解运用这也较大。由判据的构造我们还可以初步了解运用这类判据的原则和方法。类判据的原则和方法。19现在学习的是第19页，共49页7.2 7.2 类别可分性判据类别可分性判据7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据考虑两类问题。上图是一维的两类概率分布密度。考虑两类问题。上图是一维的两类概率分布密度。(a)(a)表示两类是完全可分的。表示两类是完全可分的。(b)(b)是完全不可分的。是完全不可分的。20现在学习的是第20页，共49页可用两类概密函数的重叠程度来度量可分性，构造可用两类概密函数的重叠程度来度量可分性，构造基于类概密的可分性判据。此处的所谓重叠程度是指两基于类概密的可分性判据。此处的所谓重叠程度是指两个概密函数相似的程度。个概密函数相似的程度。7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据21现在学习的是第21页，共49页7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据(一一)BhattacharyyaBhattacharyya 判据判据(J JB B)受相关概念与应用的启发，我们可以构造受相关概念与应用的启发，我们可以构造B-判判据，它的计算式为据，它的计算式为 W W xdxpxpJB 2121)()(ln 式中式中W W表示特征空间。在最小误判概率准则下，误判表示特征空间。在最小误判概率准则下，误判概率有概率有 BJPPeP exp)()()(21210 22现在学习的是第22页，共49页7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据（二）（二）Chernoff判据判据(JC)WxdxpxpJssC121)()(ln1s0，1。不同的值可得不同的可分性度量。ciiipppH1)1(log)(当当1时，由洛必达法则可得时，由洛必达法则可得Shannon熵熵ciippH12)2(1 2)(当当=2时，可得平方熵时，可得平方熵现在学习的是第33页，共49页JH使用使用 判据进行特征提取与选择时，我们的目标是使判据进行特征提取与选择时，我们的目标是使JH min。同理，我们亦可用点熵在整个特征空间的概率平均同理，我们亦可用点熵在整个特征空间的概率平均)(,),(),(21)(xpxpxpJEJcxH作为可分性判据。作为可分性判据。7.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据34现在学习的是第34页，共49页第七章第七章 特征提取与选择特征提取与选择7.5 7.5 离散离散K-LK-L变换及其在变换及其在 特征提取与选择中的应用特征提取与选择中的应用35现在学习的是第35页，共49页7.5.1 离散离散K-L变换（变换（DKLT）DKLT的性质：的性质：使变换后产生的新的分量正交或不相关使变换后产生的新的分量正交或不相关;以部分新分量表示原矢量均方误差最小以部分新分量表示原矢量均方误差最小;1.使变换矢量更趋确定、能量更趋集中。使变换矢量更趋确定、能量更趋集中。有限离散有限离散K-LK-L变换（变换（DKLTDKLT）,又称霍特林又称霍特林(Hotelling)(Hotelling)变换或主分量分解变换或主分量分解,它是一种基于目标统计特它是一种基于目标统计特性的最佳正交变换。性的最佳正交变换。36现在学习的是第36页，共49页7.5.1 离散离散K-L变换（变换（DKLT）设设n维随机矢量维随机矢量 xx xxn (,)12T，其均，其均值矢量值矢量 xE x，相关阵，相关阵 RE xxx T，协方，协方差阵差阵 CE xxxxx ()()T，x经正交变换后经正交变换后产生矢量产生矢量 yy yyn (,)12T，37现在学习的是第37页，共49页设有标准正交变换矩阵设有标准正交变换矩阵T，（即，（即 TT=I）),()(2121nnyyyxtttxTyniiityyTyTx11)(xtyii),2,1(ni取前取前m项为项为 的估计值的估计值xxy tiiim1nm 1（称为（称为 的的K-LK-L展开式）展开式）x其均方误差为其均方误差为)()()(T2xxxxEmnmiiinmiiyyEyE11238现在学习的是第38页，共49页nmiiinmiiyyEyE112nmiixinmiiitRttxxEt11)()(2mxtyii 在在TT=I的约束条件下的约束条件下,要使均方误差要使均方误差min)()()(12nmiixitRtxxxxEmnmiiiinmiixitttRtJ11)1(为此作准则函数为此作准则函数nmi,.,10itJ0)(iixtIR由由 可得可得iiixttRnmi,.,1即即39现在学习的是第39页，共49页iiixttRnmi,.,1xRit i是是 的特征值，而的特征值，而 是相应的特征矢量。是相应的特征矢量。由由表明表明:nmiinmiiiinmiixitttRtm1112)(利用上式有利用上式有:7.5.1 离散离散K-L变换（变换（DKLT）在上述的估计式中，如果不是简单地舍弃后在上述的估计式中，如果不是简单地舍弃后(n-m)项，而是用预选的常数项，而是用预选的常数bi代替代替yi,i=m+1,n，此时的估，此时的估计式为计式为:xy tb tiiimiii mn1140现在学习的是第40页，共49页7.5.1 离散离散K-L变换（变换（DKLT）xy tb tiiimiii mn11的均方误差为的均方误差为:nmiiibyExxxxEm122)()()()(（1）最佳的）最佳的bi可通过可通过 求得求得 20bibEybiii()20 xtxEtyEbiiiinmiixinmiiinmiiinmiiitCttxxxxEtxtxtEbyEm1112122)()()()(41现在学习的是第41页，共49页7.5.1 离散离散K-L变换（变换（DKLT）42现在学习的是第42页，共49页7.5.1 离散离散K-L变换（变换（DKLT）因为因为TxxxxCR为非负定阵，故有为非负定阵，故有)()(xixiCRni,2,1上述的讨论可归纳为上述的讨论可归纳为:当我们用简单的当我们用简单的“截断截断”方式产生估计式时方式产生估计式时,使均方误使均方误差最小的正交变换矩阵是随机矢量差最小的正交变换矩阵是随机矢量x x的相关阵的相关阵R Rx x的特征矢量的特征矢量矩阵矩阵;当估计式除了选用当估计式除了选用m m个分量个分量y yi i(i=1,2,(i=1,2,m),m)之外之外,还用余还用余下的各下的各y yi i的均值的均值b bi i代替相应的分量时代替相应的分量时,使均方误差最小的正使均方误差最小的正交变换矩阵是交变换矩阵是x x的协方差阵。的协方差阵。这表明对于相同的这表明对于相同的m m，第一种估计式比，第一种估计式比第二种估计式的均方差大。第二种估计式的均方差大。43现在学习的是第43页，共49页DKLTDKLT的性质的性质(1)(1)变换后各特征分量正交或不相关变换后各特征分量正交或不相关 的自相关阵和协方差阵为变换后的矢量的各分量是正交的,或不相关的(因为C=R-E(x)E(x)，当E(x)=0时，不相关即是正交)；i=E(yi2),或i=Eyi-E(yi)2(方差)ynxyTRTxTxTEyyER21T)(nxyTCTyyyyEC21)(44现在学习的是第44页，共49页 妈妈新开了个淘宝店，欢迎前来捧场妈妈新开了个淘宝店，欢迎前来捧场 妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，但生妈妈的淘宝点开了快半年了，主要卖的是毛绒玩具、坐垫、抱枕之类的，但生意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没有人气，所意一直不是很好，感觉妈妈还是很用心的，花了不少功夫，但是就是没有人气，所以我也来出自己的一份力，帮忙宣传一下。以我也来出自己的一份力，帮忙宣传一下。并且妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。并且妈妈总是去五亭龙挑最好的玩具整理、发货，质量绝对有保证。另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。另外我家就在扬州五亭龙玩具城旁边，货源丰富，质量可靠，价格便宜。欢迎大家来逛逛欢迎大家来逛逛【扬州五亭龙玩具总动员扬州五亭龙玩具总动员】个人小广告：个人小广告：45现在学习的是第45页，共49页1x2x1y2y1t2t46现在学习的是第46页，共49页(2)(2)最佳逼近性最佳逼近性(3)(3)使能量向某些分量相对集中，增强随机矢使能量向某些分量相对集中，增强随机矢量总体的确定性量总体的确定性min)(12nmiimnmmixtyii;,2,1 DKLTDKLT的性质的性质47现在学习的是第47页，共49页例例:已知两类样本已知两类样本 试用试用K-LK-L变换做一维特征提取。变换做一维特征提取。)5,6(,)6,5(,)5,4(,)4,5(,)5,5(:1)5,4(,)4,5(,)5,6(,)6,5(,)5,5(:20515151)2(51)1(iiiixxm解：解：（1 1）4.0 ,4.50 025)4.25(|2122IR1121 ,1121 21,21tt,jt tRjjj（3 3）求求R R的特征值、特征矢量的特征值、特征矢量2/110/5)()(21PP4.2525254.25 5121 5121)(51)2()2(51)1()1()()(21iiiiiiiiiixxxxxxEPxxER（2 2）48现在学习的是第48页，共49页（4）选选 1 1对应的对应的 作为变换矩阵作为变换矩阵1t11211tT得211,211,29,29,210:129,29,211,211,210:21x2x1t2t55550yxTy21055)1,1(21)1(1)1(1xTy211)1(5)1(5xTy由由 得变换后的一维模式特征为得变换后的一维模式特征为49现在学习的是第49页，共49页