1、模式识别主讲主讲： 蔡宣平蔡宣平 教授教授 电话电话： 7344173441（O O）,73442,73442（H H）E-mailE-mail：单位单位: : 电子科学与工程学院信息工程系电子科学与工程学院信息工程系2第七章第七章 特征提取与选择特征提取与选择n 类别可分性判据类别可分性判据n 离散离散K-LK-L变换及其在特征提取变换及其在特征提取 与选择中的应用与选择中的应用n 特征选择中的直接挑选法特征选择中的直接挑选法3第七章第七章 特征提取与选择特征提取与选择 7.1 7.1 概概 述述4 模式识别的三大核心问题模式识别的三大核心问题: :第七章第七章 特征提取与选择特征提取与选择
2、7.1概述概述特征数据采集特征数据采集分类识别分类识别特征提取与选择特征提取与选择 分类识别的正确率取决于对象的表示、训练学分类识别的正确率取决于对象的表示、训练学习和分类识别算法，我们在前面各章的介绍中详细习和分类识别算法，我们在前面各章的介绍中详细讨论了后两方面的内容。本章介绍的特征提取与选讨论了后两方面的内容。本章介绍的特征提取与选择问题则是对象表示的一个关键问题。择问题则是对象表示的一个关键问题。5 通常在得到实际对象的若干具体特征之通常在得到实际对象的若干具体特征之后，再由这些原始特征产生出对分类识别最后，再由这些原始特征产生出对分类识别最有效、数目最少的特征，这就是特征提取与有效、
3、数目最少的特征，这就是特征提取与选择的任务。从本质上讲，我们的目的是使选择的任务。从本质上讲，我们的目的是使在最小维数特征空间中异类模式点相距较远在最小维数特征空间中异类模式点相距较远（类间距离较大），而同类模式点相距较近（类间距离较大），而同类模式点相距较近（类内距离较小）。（类内距离较小）。 第七章第七章 特征提取与选择特征提取与选择7.1概述概述67.1概述概述特征提取与选择的两个基本途特征提取与选择的两个基本途径径主要方法有：主要方法有：分支定界法分支定界法、用回归建模技术确定相用回归建模技术确定相关特征关特征等方法。等方法。（1 1）直接选择法：）直接选择法：当实际用于分类识别的特征
4、数目当实际用于分类识别的特征数目d d 确定后，直接从已获得的确定后，直接从已获得的n n 个原始特征中选出个原始特征中选出d d 个特征个特征 ，使可分性判据，使可分性判据J J 的值满足下的值满足下式：式：dxxx,21J x xxJ xxxdiiid1212,max,式中式中 是是n 个原始特征中的任意个原始特征中的任意d 个特征，个特征，上式表示直接寻找上式表示直接寻找n 维特征空间中的维特征空间中的d 维子空间。维子空间。idiixxx,217（2 2）变换法）变换法，在使判据，在使判据J J 取最大的目标下，对取最大的目标下，对n n 个原始特征进行变换降维，即对原个原始特征进行变
5、换降维，即对原n n 维特征空间维特征空间进行坐标变换，然后再取子空间。进行坐标变换，然后再取子空间。7.1概述概述特征提取与选择的两个基本途特征提取与选择的两个基本途径径主要方法有：主要方法有：基于可分性判据的特征选择基于可分性判据的特征选择、基于基于误判概率的特征选择误判概率的特征选择、离散离散K-LK-L变换法变换法(DKLT)(DKLT)、基于决策界的特征选择基于决策界的特征选择等方法。等方法。87.2 7.2 类别可分性判据类别可分性判据第七章第七章 特征提取与选择特征提取与选择97.2 类别可分性判据类别可分性判据 为确立特征提取和选择的准则：引入类别可分性为确立特征提取和选择的准
6、则：引入类别可分性判据，来刻划特征对分类的贡献。为此希望所构造判据，来刻划特征对分类的贡献。为此希望所构造的可分性判据满足下列要求：的可分性判据满足下列要求：构造可分性判据构造可分性判据(1) (1) 与误判概率与误判概率( (或误分概率的上界、下界或误分概率的上界、下界) )有单调关系。有单调关系。 (2) (2) 当特征相互独立时，判据有可加性，即当特征相互独立时，判据有可加性，即 ： Jx xxJxi jdi jkdk(,)()121式中，式中，x xxd12,是对不同种类特征的测量值，是对不同种类特征的测量值，Ji j( ) 表示使用括号中特征时第表示使用括号中特征时第i 类与第类与第
7、j类可分性判据函数。类可分性判据函数。107.2 类别可分性判据类别可分性判据构造可分性判据构造可分性判据(3) (3) 判据具有判据具有“距离距离”的某些特性，即的某些特性，即 ：Ji j 0，当，当ij时；时；Ji j 0，当，当ij时；时；JJi jji(4) (4) 对特征数目是单调不减，即加入新的特征后，对特征数目是单调不减，即加入新的特征后，判据值不减。判据值不减。 Jx xxJx xxxi jdi jdd(,)(,)12121117.2 类别可分性判据类别可分性判据构造可分性判据构造可分性判据值得注意的是值得注意的是：上述的构造可分性判据的要求，即：上述的构造可分性判据的要求，即
8、“单调性单调性”、“叠加性叠加性”、“距离性距离性”、“单调不单调不减性减性”。在实际应用并不一定能同时具备，但并不。在实际应用并不一定能同时具备，但并不影响它在实际使用中的价值。影响它在实际使用中的价值。 127.2 类别可分性判据类别可分性判据7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据一般来讲，不同类的模式可以被区分是由于它们一般来讲，不同类的模式可以被区分是由于它们所属类别在特征空间中的类域是不同的区域。所属类别在特征空间中的类域是不同的区域。显然，区域重叠的部分越小或完全没有重叠，类显然，区域重叠的部分越小或完全没有重叠，类别的可分性就越好。别的可分性就越好。
9、因此可以用距离或离差测度（散度）来构造类别因此可以用距离或离差测度（散度）来构造类别的可分性判据。的可分性判据。 13( (一一) ) 点与点的距离点与点的距离 d a babababkkkn( , )() ()()/T1 2211 2( (二二) ) 点到点集的距离点到点集的距离),(1) ,()(12)(2ikNkiikaxdNaxdi用用均方欧氏距离均方欧氏距离表示表示7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据14( (三三) ) 类内及总体的均值矢量类内及总体的均值矢量 ciiimPm1)(各类模式的总体均值矢量各类模式的总体均值矢量 iNkikiixNm1)
10、()(1类的均值矢量：类的均值矢量： ci, 2 , 1 Pi为相应类的先验概率，为相应类的先验概率，当用统计量代替先验概当用统计量代替先验概率时，总体均值矢量可表示为：率时，总体均值矢量可表示为：NllciNkikiciiiciixNxNmNNmPmi111)()(1)(1117.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据15( (四四) ) 类内距离类内距离 )()(1)()()(T)()(12iikiikNkiimxmxNdi类内均方欧氏距离类内均方欧氏距离 类内均方距离也可定义为：类内均方距离也可定义为： iiNkNlilikiiicxxdNNd11)()(22)
11、,() 1(1)(7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据16( (五五) ) 类内离差矩阵类内离差矩阵 T)()()()(1)(1iikiikNkimxmxNSii)(2iSTrdi显然显然( (六六) ) 两类之间的距离两类之间的距离 ),(1),()(11)(22jlNkNlikjijixxdNNdij)()(1),()()(T)(11)(2jlikjlNkNlikjijixxxxNNdij7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据17( (七七) )各类模式之间的总的均方距各类模式之间的总的均方距离离 ijNkNljlikjicjj
12、ciixxdNNPPxd11)()(2112),(121)(当取欧氏距离时，总的均方距离为当取欧氏距离时，总的均方距离为)()(121)()()(11T)()(112jlikNkNljlikjicjjciixxxxNNPPxdij7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据18( (八八) ) 多类情况下总的类内、类间及总体离差矩阵多类情况下总的类内、类间及总体离差矩阵 iiNkiikiikiciiciiWmxmxNPSPS1T)()()()(11)(1类内离差类内离差ciiiiBmmmmPS1T)()()(类间离差类间离差总体离差总体离差 BWNlllTSSmxmxN
13、S1T)(1易导出易导出dxTr SSTr SWBT2( )7.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据197.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据JTr SSWB11JSSBW2lnJTr STr SBW3JSSSSSWBWTW4207.2.17.2.1基于几何距离的可分性判据基于几何距离的可分性判据在特征空间中，当类内模式较密聚，而不同类的在特征空间中，当类内模式较密聚，而不同类的模式相距较远时，从直觉上我们知道分类就较容模式相距较远时，从直觉上我们知道分类就较容易，由各判据的构造可知，这种情况下所算得的易，由各判据的构造可知，这种情况下
14、所算得的判据值也较大。由判据的构造我们还可以初步了判据值也较大。由判据的构造我们还可以初步了解运用这类判据的原则和方法。解运用这类判据的原则和方法。217.2 7.2 类别可分性判据类别可分性判据7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据考虑两类问题。上图是一维的两类概率分布密度。考虑两类问题。上图是一维的两类概率分布密度。 (a) (a) 表示两类是完全可分的。表示两类是完全可分的。(b)(b)是完全不可分的。是完全不可分的。 22可用两类概密函数的重叠程度来度量可分性，可用两类概密函数的重叠程度来度量可分性，构造基于类概密的可分性判据。此处的所谓重
15、叠构造基于类概密的可分性判据。此处的所谓重叠程度是指两个概密函数相似的程度。程度是指两个概密函数相似的程度。7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据237.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据( (一一) ) BhattacharyyaBhattacharyya 判据判据( (J JB B) )受相关概念与应用的启发，我们可以构造受相关概念与应用的启发，我们可以构造B- -判判据，它的计算式为据，它的计算式为 W W xdxpxpJB 2121)()(ln 式中式中W W表示特征空间。在最小误判概率准则下，
16、误判表示特征空间。在最小误判概率准则下，误判概率有概率有 BJPPeP exp)()()(21210 247.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据 P eP ePp xdxPp xdx0112212( )min( )min()()()() W WW W Pp xPp xdx1122min() (),() () W W Pp xPp xdx11221 2() () () ()/ W W PPp xp x121 212() ()() ()/ W W1 2/dx 121 2/() ()expPPJB 证明：设证明：设P e( )为误分概率，则最小误分概率为
17、：为误分概率，则最小误分概率为：257.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据（二）（二） Chernoff 判据判据 ( (JC) )WxdxpxpJssC121)()(ln1s0 )(),;( 21sJxxxsJCnC);,(21sJC267.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据JC 具有如下性质：具有如下性质： (1)(1)对一切对一切01 s，0 CJ； (2)(2)对一切对一切01 s，Jp xp xC 012()() ； (3)(3)当参数当参数s和和 1 s互调时，有对称性互调时，有对称性, ,
18、)1 ;,();,(1221sJsJCC (4)(4)当当 x的各分量的各分量nxxx,21相互独立时，相互独立时， nllCnCxsJxxxsJ121);(),;(277.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据(5)(5)当当 x的各分量的各分量nxxx,21相互独立时，有相互独立时，有 )( ),;(),;(121121nkxxxxsJxxxsJkkCkC (6)(6)最小误判概率最小误判概率 ) 10( );,(exp)()()(211210 0) (a,b0)因为，当因为，当 0 0 s s 1 1 时时 f f (s) = -a(s) = -
19、as sb b1-s1-s(ln a - ln b)(ln a - ln b)2 2 0 0 (a(a b)b)且且 f(0)=f(1) = 0f(0)=f(1) = 0，从而有从而有 f(s)f(s) 0 0。由该不等式有：。由该不等式有：证毕。证毕。WxdxpxpsJssc12121)|()|(ln),(0)1ln()|()1 ()|(ln21Wssxdxpsxsp29Jc Jc 性质（性质（2 2）证明：）证明：只考虑连续的情况：只考虑连续的情况：因为因为f(0)=f(1) = 0f(0)=f(1) = 0 ，当，当 0 0 s s 1 1 时时f (s) = a-b-asb1-s (l
20、n a - ln b)=0 a=b 从而有从而有 f(s)=0 f(s)=0 a=b a=b ，由此有：由此有：)|()|(21xpxpJC=0 30Jc Jc 性质（性质（5 5）证明：）证明：设设P(e)P(e)为最小误分概率，则：为最小误分概率，则：P eP ePp xdxPp xdxPp xPp xdx01122112221( )min( )min()()()()min() (),() ()WWW利用不等式利用不等式 ，由上式进一步可得：由上式进一步可得： min,a ba bab100 01P ePPp xp xdxPPJssssssC0121121121( )()()()()()(
21、)expW317.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据由由JB和和JC的定义知：的定义知：JB=JC(1/2)对两类都是正态分布情况对两类都是正态分布情况: p xN mC() (,)( )111p xN mC() (,)( )222Jss mms CsCmms CsCCCCss1211121121211212112()()()()ln()( )( )( )( )TJmmCCmmCCCCB182121212121121211 221 2()()ln()( )( )( )( )/T327.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度
22、函数的可分性判据Jss mms CsCmms CsCCCCss1211121121211212112()()()()ln()( )( )( )( )TJmmCCmmCCCCB182121212121121211 221 2()()ln()( )( )( )( )/T当CCC12时，)()(81)()(1 (21)2()1(1T)2()1()2()1(1T)2()1(mmCmmJmmCmmssJBC337.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据Jp xp xp xdxCs ln()()()122W实际上实际上 这就启发我们运用这就启发我们运用两个概密的比
23、或差两个概密的比或差来描述来描述两个概密两个概密重迭重迭或相似的程度。或相似的程度。 WxdxpxpJssC121)()(ln可以写成：可以写成： 34( (三三) )散度散度J JD D (Divergence) (Divergence) i i类对类对 j j类的平均可分性信息为：类的平均可分性信息为： IxEp xp xp xp xp xdxi jiijiij( )ln()()()ln()()WIxEp xp xp xp xp xdxjijjijji( )ln()()()ln()()W7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据 j j 对对 i
24、i 类的平均可分性信息为：类的平均可分性信息为：35),(),()|()|(ln)|()|()()(1nDjiDjijii jj iDxxJJxdxpxpxpxpxIxIJW7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据对于对于 i i和和 j j两类总的平均可分性信息称为散度，其两类总的平均可分性信息称为散度，其定义为两类平均可分性信息之和，即定义为两类平均可分性信息之和，即 (三三)散度散度JD (Divergence)36),(),()|()|(ln)|()|()()(1nDjiDjijii jj iDxxJJxdxpxpxpxpxIxIJW7.2.
25、27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据当两类都是正态分布时：当两类都是正态分布时： JTr CCCCImmCCmmDijjiijijij122121111() ()()( )( )( )( )T当当C Ci i=C=Cj j=C=C时时JmmCmmJDijijB()()( )( )( )( )T1837散度具有如下性质：散度具有如下性质： Jx xxJx xxxknDkDkk(,),121121() 7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据(1) JD 0；(2) 对称性对称性: JD( 1 , 2)= JD(
26、2 , 1); Jp xp xD012()()(3) Jx xxJxknDkDjjk(,)()121 (4) 当当x 各分量各分量x1,x2,xn相互独立时，相互独立时，(具有可加性具有可加性) (5) 当当x各分量各分量x1,x2,xn相互独立时，相互独立时，(对特征数目单对特征数目单调不减调不减)387.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据一般情况下，散度与误分概率一般情况下，散度与误分概率( (或其上下界或其上下界) )之间之间的直接解析关系很难得到，但实验可以证明它们之间的直接解析关系很难得到，但实验可以证明它们之间存在着单调关系。例如两类都
27、是正态分布，且有相同存在着单调关系。例如两类都是正态分布，且有相同的协方差阵时，的协方差阵时， 是是 的的单调减函数单调减函数。P e0( )JDJDP eydyJD0212122( )exp当两类先验概率相等且为具有相同协方差的正态当两类先验概率相等且为具有相同协方差的正态分布时，则最小误分概率与分布时，则最小误分概率与 的关系为：的关系为：39对于对于JC 判据的判据的最小误分概率的上界最小误分概率的上界 P ePPJssssC01211201( )()()exp(,; ) Ch, , 但但Bh比较容易计算，算得比较容易计算，算得结果通常也比较接近结果通常也比较接近Ch，所以在分类器设计分
28、析中，所以在分类器设计分析中Bh、JB也是常用的。也是常用的。42对于对于c类问题，可采用平均类问题，可采用平均B-判据、判据、C-判据、判据、D-判据：判据： cicijjiBjiBJPPJ11),()()(cicijjiCjiCJPPJ11),()()( cicijjiDjiDJPPJ11),()()(由由JB、JC、JD的定义式结构以及它们与误分概率的的定义式结构以及它们与误分概率的关系可以知道，所选取的特征矢量应使所对应的关系可以知道，所选取的特征矢量应使所对应的JB、JC 、JD尽量大，这样可分性就较好。尽量大，这样可分性就较好。7.2.27.2.2基于类的概率密度函数的可分性判据基
29、于类的概率密度函数的可分性判据43大盖小问题大盖小问题 在特征空间中，若有某两类间的在特征空间中，若有某两类间的JB、JC或或JD很大，很大，可使平均判据变大，这样就掩盖了某些类对的判据值可使平均判据变大，这样就掩盖了某些类对的判据值较小的情况存在，从而可能降低总的分类正确率，即较小的情况存在，从而可能降低总的分类正确率，即所谓的所谓的大盖小问题大盖小问题。为改善这种情况，可对每个类对。为改善这种情况，可对每个类对的判据采用变换的方法，使对小的判据较敏感。例如，的判据采用变换的方法，使对小的判据较敏感。例如，对对JD ，可采用变换，可采用变换8),(exp1),(jiDjiDJJ448),(e
30、xp1),(jiDjiDJJ这样，当这样，当 i和和 j两类模式相距很远时，两类模式相距很远时， JD( i, j)变变得很大，但得很大，但 也只能接近于也只能接近于1。但对于散度。但对于散度JD( i, j) 小的情况，小的情况， 又变得较敏感。于是，又变得较敏感。于是，总的平均总的平均(变换变换)判据为判据为 ),(jiDJ),(jiDJ),()()(11jicicijDjiDJPPJ 7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据45同样对于同样对于JB，单类与平均判据分别为：，单类与平均判据分别为：21),(exp22),(jiBjiBJJ单类：单
31、类：),()()(11jicicijBjiBJPPJ平均判据：平均判据：7.2.27.2.2基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据467.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据在信息论中，在信息论中，熵熵(Entropy)(Entropy)表示不确定性表示不确定性，熵越，熵越大不确定性越大。可以借用熵的概念来描述各类的大不确定性越大。可以借用熵的概念来描述各类的可分性。可分性。pxi()对于对于c c类问题，给定各类的后验概率类问题，给定各类的后验概率 可以写成如下形式：可以写成如下形式：ccccpppxpxpxp21212121 )()
32、()(熵的定义：熵的定义：)(log)(log)()(11xpxppppHxHiciiicii由洛必达法则知：当由洛必达法则知：当 时时pi 00logiipp477.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据例如：例如：显然这时能实现完全正确的分类识别显然这时能实现完全正确的分类识别 pxi()1pxjij(), 0487.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据497.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据熵的主要性质：熵的主要性质：(4)(4)2122112132121,)(),(),(ppppppHpp
33、ppppHpppHcc其中其中021 pp说明当类别较少时，分类识别的不确定性变小。说明当类别较少时，分类识别的不确定性变小。 从特征选择角度看，我们从特征选择角度看，我们应选择使熵最小的那些特应选择使熵最小的那些特征用于分类征用于分类即选用具有最小不确定性的特征进行分即选用具有最小不确定性的特征进行分类是有益的。类是有益的。 使熵最小的特征利于分类，取熵的期望：使熵最小的特征利于分类，取熵的期望：min)|(log)|(1xPxPEJiciixH广义熵广义熵（具有熵的性质，利于计算）定义为定义为:) 1() 12(),(11121)(ciicppppH式中0， 1。不同的值可得不同的可分性度
34、量。ciiipppH1)1(log)(当当1时，由洛必达法则可得时，由洛必达法则可得Shannon熵熵ciippH12)2(1 2)(当当 =2时，可得平方熵时，可得平方熵51JH使用使用 判据进行特征提取与选择时，我们的目标是使判据进行特征提取与选择时，我们的目标是使JH min。 同理，我们亦可用点熵在整个特征空间的概率平均同理，我们亦可用点熵在整个特征空间的概率平均)(,),(),(21)(xpxpxpJEJcxH作为可分性判据。作为可分性判据。7.2.3 7.2.3 基于后验概率的可分性判据基于后验概率的可分性判据52第七章第七章 特征提取与选择特征提取与选择7.3 7.3 基于可分性
35、判据进行变换的基于可分性判据进行变换的 特征提取与选择特征提取与选择537.3 7.3 基于可分性判据进行变换的特征提取与选择基于可分性判据进行变换的特征提取与选择变换变换xWy为特征提取矩阵或变换矩阵为特征提取矩阵或变换矩阵WWn d),(21nxxxxndyyyyd, ),(21原始特征原始特征 二次特征二次特征547.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据的变换法 设设SW和和SB分别为原始特征空间中的类内和类分别为原始特征空间中的类内和类间离差矩阵，间离差矩阵，SW*和和SB*分别为变换特征空间中的类分别为变换特征空间中的类内和类间离差矩阵，可知内和类间离差矩阵，可知
36、 SW S WWW* T SW S WBB* T根据根据 J1 1=TrS=TrSW W-1-1S SB Bmaxmax或或 J4 4=|S=|SW W+S+SB B|/|S|/|SB B|=|S|=|ST T|/|S|/|SB B| max| max求变换矩阵求变换矩阵 W W。55 在变换域中在变换域中J1为为 )()(Tr)(Tr)(T1T*1*1WSWWSWSSWJBWBW 由线性代数可知，对矩阵作相似变换其迹不变，由线性代数可知，对矩阵作相似变换其迹不变，一个方阵的迹等于它的所有特征值之和。设一个方阵的迹等于它的所有特征值之和。设We为正为正交阵，用交阵，用We对对称阵对对称阵SSW
37、B 1作相似变换使其成为对角阵作相似变换使其成为对角阵,其中其中, i ni, 2 , 1 为为SSWB 1的特征值，的特征值，We的列矢量的列矢量 Wi为为SSWB 1相应于相应于 i的特征矢量。由上式可得的特征矢量。由上式可得 ),(002121111nneBWeeBWediagWSSWWSSWniieBWeBWWSSWTrSSTrJ1111（一）对于矩阵迹形式的判据（一）对于矩阵迹形式的判据56假设假设We的列矢量的排列已作适当调整，使的列矢量的排列已作适当调整，使S SW W-1-1S SB B的的特征值特征值 1 1 2 2 n n 。由此可得，在。由此可得，在d d 给给定后，取前
38、定后，取前d d 个较大的特征值所对应的特征矢量个较大的特征值所对应的特征矢量wi( (i=1,2,=1,2, ,d d) )构造特征提取矩阵构造特征提取矩阵W，即，即: :)(21dwwwWxWydiiWJ1*1)(7.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据的变换法作变换作变换 ，这时对于给定的，这时对于给定的d d所得到的所得到的 达最大值。此方法对达最大值。此方法对J3 3 =TrS=TrSB B/TrS/TrSW W 也适用。也适用。 57（二）对于行列式形式的判据（二）对于行列式形式的判据以以J4为例，由于为例，由于SW是对称正定矩阵，设有非奇异是对称正定矩阵，设有
39、非奇异阵阵A，使，使IASAW1AVSAVTIIVVAVSAVW11但一般但一般AST A不是对角阵，设有标准正交矩阵不是对角阵，设有标准正交矩阵V，使，使这里这里 为对角阵，从而为对角阵，从而7.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据的变换法0021nTUSU令令U=AV ，因此存在非奇异矩阵因此存在非奇异矩阵U ，使，使 IUSUW58上面右式两边同时取逆，有上面右式两边同时取逆，有IUSUw111) (这里这里U及及 分别是特征矢量组成的矩阵分别是特征矢量组成的矩阵(特征矢量矩特征矢量矩阵阵)及特征值对角阵。及特征值对角阵。 7.3.1 7.3.1 基于离差阵判据的变换
40、法基于离差阵判据的变换法0021nTUSUIUSUWSS UUWT1再与左式相乘，并左乘再与左式相乘，并左乘U ，有，有: 59因为因为SSSSSISSWTWWBWB111() diagn(,) 12设设SW-1SB 的特征值矩阵的特征值矩阵)()(11IUUSSUUSSIBWBW所以所以I 则则于是于是7.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据的变换法WTSSJ 4USSUTW11TWSS1TWSS1)1 (1iniini160此处的此处的U 就是前述的就是前述的We。设。设U 的各列已作适当调的各列已作适当调整，使整，使 1 2 n ，对于给定的，对于给定的d，取前，取前
41、d个较大的个较大的特征值对应的特征矢量构造变换矩阵可使特征值对应的特征矢量构造变换矩阵可使J4 取最大值，取最大值，此时此时J Widi411()()1 (1111114iniiniTWTWTWWTUSSUSSSSSSJ7.3.1 7.3.1 基于离差阵判据的变换法基于离差阵判据的变换法从从J4的构造可知，用的构造可知，用J4作判据作判据 ，不至于选用那些，不至于选用那些只对两类有很好的可分性而对其他各类分类效果不好只对两类有很好的可分性而对其他各类分类效果不好的特征。而对于的特征。而对于J1 =TrSW-1SB，只要一个，只要一个 i很大就会很大就会发生这种情况。发生这种情况。61例例7.1
42、 给定两类模式，其先验概率给定两类模式，其先验概率P( 1)= P( 2) ，均均值矢量分别为值矢量分别为 和和 ，离差阵分别，离差阵分别为为 求基于判据求基于判据J4的最优特征提取。的最优特征提取。 ) 1, 3 , 1 (1m ) 1 , 1, 1(2mC1410140001C2210120001mmm()( , , )1220 1 0TSCCW1231013000112()SW118310130008解：解： TiTiiBmmmmmmmmS)(41)(2121212162S S vvWB1为求该特征值应解方程：为求该特征值应解方程：这就是所要求的最优特征提取矩阵。这就是所要求的最优特征提
43、取矩阵。 即即TWmmmmS)(2121141由于由于 是标量，于是有：是标量，于是有：Tmm)(2141TWmmS)16,10, 2(81)(21163第七章第七章 特征提取与选择特征提取与选择7.5 7.5 离散离散K-LK-L变换及其在变换及其在 特征提取与选择中的应用特征提取与选择中的应用647.5.1 离散离散K-L变换（变换（DKLT）DKLT的性质：的性质：1. 使变换后产生的新的分量正交或不相关使变换后产生的新的分量正交或不相关;2. 以部分新分量表示原矢量均方误差最小以部分新分量表示原矢量均方误差最小;3. 使变换矢量更趋确定、能量更趋集中。使变换矢量更趋确定、能量更趋集中。
44、有限离散有限离散K-LK-L变换（变换（DKLTDKLT）, ,又称霍特林又称霍特林(Hotelling)(Hotelling)变换或主分量分解变换或主分量分解, ,它是一种基于目标它是一种基于目标统计特性的最佳正交变换。统计特性的最佳正交变换。657.5.1 离散离散K-L变换（变换（DKLT）设设n维随机矢量维随机矢量 xx xxn ( ,)12T，其均，其均值矢量值矢量 xE x ，相关阵，相关阵 RE xxx T，协方，协方差阵差阵 CE xx xxx ()()T， x经正交变换后经正交变换后产生矢量产生矢量 yy yyn (,)12T，66设有标准正交变换矩阵设有标准正交变换矩阵T，
45、（即，（即 TT=I）),( )(2121nnyyyxtttxTyniiityyTyTx11) (xtyii),2 , 1(ni取前取前m项为项为 的估计值的估计值xxy tiiim1nm J(y2),所以选最佳变换矩阵为所以选最佳变换矩阵为)707. 0 ,707. 0(1W下面依据下面依据S SW W和和S SB B作作DKLTDKLT进行最优特征提取。进行最优特征提取。此时此时447. 02/11707. 02/125 . 0316. 05 . 0316. 0707. 000447. 0707. 0707. 0707. 0707. 02/1UB对对S SB B进行白化变换：进行白化变换：
46、1896. 1896. 16 . 3BSBSBB861896. 1896. 16 . 3BSBSBB的非零特征值只有一个，的非零特征值只有一个， 6 . 41BS对应的特征矢量为对应的特征矢量为)466. 0 ,884. 0(1)046. 0 ,512. 0(1BW总的最优变换为：总的最优变换为：作业：作业：7.1187第七章第七章 特征提取与选择特征提取与选择7.5 7.5 离散离散K-LK-L变换及其在变换及其在 特征提取与选择中的应用特征提取与选择中的应用88第七章第七章 特征提取与选择特征提取与选择7.7 7.7 特征选择中的直接挑选法特征选择中的直接挑选法特征的选择除了我们前面学习的
47、变换法外特征的选择除了我们前面学习的变换法外, , 也可以也可以在原坐标系中依据某些原则直接选择特征在原坐标系中依据某些原则直接选择特征, , 即我们即我们这节课要学的直接挑选法。这节课要学的直接挑选法。7.7.1 7.7.1 次优搜索法次优搜索法7.7.2 7.7.2 最优搜索法最优搜索法897.7.1 7.7.1 次优搜索法次优搜索法( (一一) )单独最优的特征选择单独最优的特征选择单独选优法的基本思路是：单独选优法的基本思路是：计算各特征单独使用时的判计算各特征单独使用时的判据值并以递减排序，选取前据值并以递减排序，选取前d d个分类效果最好的特征。个分类效果最好的特征。 这种方法才能
48、选出一组最优特征。这种方法才能选出一组最优特征。一般地讲，即使各特征是统计独立的，这种方法选一般地讲，即使各特征是统计独立的，这种方法选出的出的d d个特征也不一定是最优的特征组合，只有可分性个特征也不一定是最优的特征组合，只有可分性判据判据J J是可分的时候，即是可分的时候，即10( )( ) ( )( )nniiiiJ xJ xJ xJ x或 90( (二二) )增添特征法增添特征法该方法也称为顺序前进法该方法也称为顺序前进法( (SFS) )。这是最简。这是最简单的自下而上搜索方法， 每次从未选入的特征中单的自下而上搜索方法， 每次从未选入的特征中选择一个特征， 使它与已选入的特征组合在
49、一起选择一个特征， 使它与已选入的特征组合在一起时时J值最大，直到选入特征数目达到指定的维值最大，直到选入特征数目达到指定的维数数d为止。为止。7.7.1 7.7.1 次优搜索法次优搜索法91( (二二) )增添特征法增添特征法7.7.1 7.7.1 次优搜索法次优搜索法设已选入了设已选入了k个特征，它们记为个特征，它们记为Xk，把未选入的，把未选入的n-k个特征个特征xj（j=1,2,n-k)逐个与已选入的特征逐个与已选入的特征Xk组合计算组合计算J 值，若：值，若：则则x1选入，下一步的特征组合为选入，下一步的特征组合为Xk+1=Xk+x1。开。开始时，始时，k=0，X0=F F， 该过程
50、一直进行到该过程一直进行到k=d为止。为止。)()()(21knkkkxXJxXJxXJ92( (二二) )增添特征法增添特征法7.7.1 7.7.1 次优搜索法次优搜索法该方法比该方法比“单独最优的特征选择法单独最优的特征选择法”要好，但要好，但其缺点也是明显的：即某特征一旦选入，即使后边其缺点也是明显的：即某特征一旦选入，即使后边的的n-k特征中的某个从组合讲比它好，也无法把它特征中的某个从组合讲比它好，也无法把它剔除。剔除。93( (三三) )剔减特征法剔减特征法7.7.1 7.7.1 次优搜索法次优搜索法该方法也称为顺序后退法该方法也称为顺序后退法(SBS)。这是一种。这是一种自上而下
