特征的选择与提取课件.ppt

1、第六章 特征的选择与提取 P1766.1 基本概念6.2 类别可分离性判据6.3 按距离度量的特征提取方法6.4 按概率距离判据的特征提取方法6.5 基于熵函数的可分性判据6.6 基于K-L变换的特征提取6.7 特征提取方法小结6.8 特征选择1第1页，共92页。本章学习目的l1了解特征空间选择在设计模式识别系统、解决模式识别具体问题中是至关重要的。l2了解描述量选择，特征组合优化的两种基本方法，一是对原特征空间进行删选原特征空间进行删选，另一种是通过变换改造原特征空间变换改造原特征空间。l3掌握典型的线性变换典型的线性变换对原特征空间优化的基本方法，进一步深入理解模式识别处理问题的基本方法确

2、定准则函数确定准则函数，并通过计算进行优化。l4了解并掌握特征选择方法使用的一些基本问题。2第2页，共92页。本章难点l1透彻理解什么叫特征空间的优化特征空间的优化，为什么要对特征空间进行优化。l2对特征空间进行优化，要用到一些数学工具，如向量点积向量点积、线性线性变换变换、正交变换正交变换、解决条件极值问题的拉格朗日乘子方法解决条件极值问题的拉格朗日乘子方法等。l3讨论利用K-L变换对特征空间进行降维，其中部分推导中用了正交变换正交变换，条件极值问题条件极值问题等数学工具，又涉及矩阵的特征值与特征矩阵的特征值与特征向量向量问题。另一方面要体会使用K-LK-L变换的好处变换的好处，如果对傅里叶

3、变换、及对信号进行时域分析与在频域分析等概念已有一定理解，可有助于对使用K-L变换方法的理解。3第3页，共92页。6.1 基本概念l分类器设计方法的研究固然重要，但如何确定合适的特征空间确定合适的特征空间是设计模式识别系统另一个十分重要、甚至更为关键的问题。l如果所选用的特征空间选用的特征空间能使同类物体分布具有紧致性紧致性，即各类样本分布在该特征空间中彼此分割开的区域内，这就为分类器设计成功提供良好的基础。l反之，如果不同类别的样本在该特征空间中混杂在一起，再好的设计方法也无法提高分类器的准确性。l本章内容属于如何构造一个特征空间如何构造一个特征空间，即对要识别的事物用什么方法进行描述描述、

4、分析分析。4第4页，共92页。(1)物理量的获取与转换l物理量的获取与转换，指用什么样的传感器获取电信号。如摄取景物则要用摄像机；文字与数字识别，首先要用扫描仪等设备，手写体文字所用传感器与印刷体文字可能不同。这些都属于物理量的获取，并且已转换成电信号，为计算机分析打下了基础l对从传感器中得到的信号，可以称之为原始信息原始信息，因为它要经过加工、处理才能得到对模式分类更加有用的信号。5第5页，共92页。(2)描述事物方法的选择与设计l在得到了原始信息之后，要对它进一步加工，以获取对分类最有效的信息。这部分信息必须对原始信息进行加工，而设计所要信息的形式是十分关而设计所要信息的形式是十分关键的键

5、的。l例如对阿拉伯数字的识别可以提出各种不同的想法，有的提出分析从框架的左边框到数字之间的距离变化反映了不同数字的不同形状，这可以用来作为数字分类的依据。l又有的方案则是强调分析不同截面的信号，如在框架的若干部位沿不同方向截取截面分析从背景到字，以及从字到背景转换的情况,如AB截面切割字符三次，CD截面切割字符一次等。6第6页，共92页。(3)特征空间的优化 l这个层次的工作发生在已有了特征的描述方法之后，也就是已有了一个初始的特征空间，如何对它进行改造与优化的问题。l一般说来要对初始的特征空间进行优化是为了降维降维。即初始的特征空间维数较高。能否改成一个维数较低的空间较低的空间，称为优化称为

6、优化，优化后的特征空间应该更有利于后续的分类计算。l所谓优化是要求既降低特征的维数，又能提高分类器的性能优化是要求既降低特征的维数，又能提高分类器的性能。l两种基本方法:特征选择特征选择(删掉部分特征)特征的组合优化特征的组合优化(一种映射)，也就是说新的每一个特征是原有特征的一个函数。7第7页，共92页。数学表达为了说得更明确，假设已有D维特征向量空间Y=y1,y2,yD,则所谓特征选择特征选择是指从原有的D维特征空间，删去一些特征描述量，从而得到精简后的特征空间。在这个特征空间中，样本由d维的特征向量描述：X=x1,x2,xd ，dD。由于X只是Y的一个子集，因此每个分量xi必然能在原特征

7、集中找到其对应的描述量xiyj。而特征提取特征提取则是找到一个映射关系：A:YX 使新样本特征描述维数比原维数降低。其中每个分量xi是原特征向量各分量的函数，即 xi=xi(y1,y2,yD)因此这两种降维的基本方法是不同的两种降维的基本方法是不同的。在实际应用中可将两者结合起来使用，比如先进行优化组合，然后再进一步选择其中一部分，或反过来。8第8页，共92页。思考题9第9页，共92页。思考题l1什么叫特征空间？如果我们用颜色、尺寸、重量来衡量水果的构造,其特征空间是几维空间？l2如果用颜色、尺寸与重量组成的特征空间来区分苹果与梨，你认为这三种度量中的哪种最有效？为什么？能否想像这两种水果在这

8、个三维空间的分布？如果用这个特征空间来区分红苹果与樱桃，你想像一下这两类水果在特征空间如何分布？能否对这两种情况设计更经济有效的特征空间？10第10页，共92页。思考题l3如果两类物体在一个二维特征空间如图分布,能否用删除其中任一维来优化特征空间？有没有什么方法能得到一个对分类很有利的一维特征空间？11第11页，共92页。思考题l4上题的答案可用下图Y1与Y2组成的空间表示？你认为哪个分量可以删掉？l5你有没有办法将原在X1、X2空间表示的数改成用Y1、Y2空间表示？12第12页，共92页。l特征选择与特征提取的任务任务：求出一组对分类最有效的特征，所谓有效有效是指在特征维数减少到同等水平时，

9、其分类性能最佳其分类性能最佳。l因此需要有定量分析比较方法，判断所得到的特征维数及所使用特征是否对分类最有利，这种用以定量检验分类用以定量检验分类性能的准则称为类别可分离性判据性能的准则称为类别可分离性判据。6.2 类别可分离性判据13第13页，共92页。6.2 类别可分离性判据（续）l对特征空间进行优化是一种计算过程对特征空间进行优化是一种计算过程，其基本方法仍然是模式识别的典型方法，即找到一种准则(或称判据)，采用优化方法，使这种准则达到一个极值。l判据，最理想的情况是与计算错误率有关的判据最理想的情况是与计算错误率有关的判据，贝叶斯公式就直接反映错误率，但在实际中运用有困难，因此又提出一

10、些其它实用性强的判据实用性强的判据。这些判据多多少少与错误率有关。大体分两类：基于距离的可分性判据基于距离的可分性判据，是一种以计算样本在特征空间离散程度为基础的准则；基于概率密度分布的判据基于概率密度分布的判据。14第14页，共92页。l6.3.1基于距离的可分性判据l6.3.2 按欧氏距离度量的特征提取方法6.3 按距离度量的特征提取方法15第15页，共92页。6.3.1基于距离的可分性判据l基于距离的可分性判据的实质是实质是Fisher准则的延伸准则的延伸，即综合考虑不同类样本的类内聚程度类内聚程度与类间的离散程度类间的离散程度这两个因素。l基于距离度量是人们常用来进行分类的重要依据，因

11、为一般情况下同类物体在特征空间呈聚类状态，即从总体上说同类物体内各样本同类物体内各样本由于具有共性由于具有共性，类内样本间距离应比跨类样本间距离小类内样本间距离应比跨类样本间距离小。lFisher准则正是以使类间距离尽可能大类间距离尽可能大同时又保持类内距离较小类内距离较小这一种原理为基础的。l特征选择与特征提取中也使用类似的原理，被称为基于距离的可基于距离的可分性判据分性判据。16第16页，共92页。6.3.1基于距离的可分性判据（续1）l为了度量类内、类间的距离，也可用另一种描述方法，即描述样本离散程度的方法。在讨论Fisher准则时曾用过两个描述离散度的矩阵。l一个是类间离散矩阵Sb：l

12、另一个是类内离散度矩阵SW：SWS1+S2及（6-1）（6-2）17第17页，共92页。6.3.1基于距离的可分性判据（续2）l以上式子是针对两类别情况的，如果推广至c类别情况，同时考虑各类的先验概率Pi不等，则可将上列各式表示成：ll其中 为所有样本的总均值向量，Pi表示各类别的先验概率，Ei表示i类的期望符号。m（6-3）（6-4）18第18页，共92页。6.3.1基于距离的可分性判据（续3）l利用(6-3)与(6-4)式可以将基于距离的可分性判据基于距离的可分性判据表示成以下形式：l1 计算特征向量间平均距离特征向量间平均距离的判据 l其中“tr”表示矩阵的迹。(6-5)式实际上是从计算

13、特征向量间总特征向量间总平均距离的公式平均距离的公式推导得到的，该式可写成该式可写成：l其中Pi、Pj分别表示各类的先验概率，ni、nj分别是第i与j类的样本个数，用来表示第i类第k个样本与j类第l个样本之间的距离度量。在欧氏距离情况下有：（6-6）（6-5）（6-7）19第19页，共92页。6.3.1基于距离的可分性判据（续4）im利用均值向量 与总均值向量 ，有代入(6-6)式可得：(6-10)中右边括弧里的前一项涉及类内各特征向量之间的平方距离类内各特征向量之间的平方距离，后一项则是类间距离项类间距离项。后一项可写成：m（6-8）（6-9）（6-10）20第20页，共92页。6.3.1基

14、于距离的可分性判据（续5）cicjjiTjijiciiTiimmmmPPmmmmP11121)()()()(（6-11）显然利用(6-10)与(6-11)就可得到(6-5)。需指出需指出的是由(6-6)推导的各式是利用有限样本数据有限样本数据，因此得到的都是母体各量的估计值，而(6-5)式用的是母体的离散度矩阵。2 考虑类内类间欧氏距离的其它判据考虑类内类间欧氏距离的其它判据 上面的判据Jd(X)是计算特征向量的总平均距离，以下一些判据则基于使类间离散度尽量大，类内离散度尽量小的考虑而提出：P18621第21页，共92页。6.3.1基于距离的可分性判据（续6）其中 表示是矩阵对应的行列式|)(

15、5wbwSSSXJ（6-12）（6-13）（6-14)(6-15)22第22页，共92页。6.3.2 按欧氏距离度量的特征提取方法 P185 基于距离可分性判据的特征优化过程特征优化过程是通过一个线性变换实现的通过一个线性变换实现的。设在原特征空间一个样本向量表示成Y(D维)，在优化特征空间中，样本向量表示成X(d维)。X与Y之间的关系是：其中W是一个Dd维矩阵，现在的问题是要利用判据找出一种线性变换，利用这种变换，实现这种判据的极值化。例如使上一节定义的判据J2(x)达到极值。(6-16)23第23页，共92页。6.3.2 按欧氏距离度量的特征提取方法(续1）如果对特征空间实行一个DD矩阵的

16、非奇异线性变换，J2，J3与J4,J5 都保持不变。例如若对原特征空间实行一DD线性变换A，则离散度矩阵 ，而映射变换后的J2(X)有：，为原空间（即y)离散度矩阵。，为映射后（即x）离散度矩阵bS*wS*bSwSp18724第24页，共92页。6.3.2 按欧氏距离度量的特征提取方法(续2）l下面讨论的特征提取变换，只考虑是降维的，即用Dd矩阵(dD)进行变换。其目的是在维数d的条件下，使相应的判据为最大。l在使用J2判据的情况下，可以将J判据表示成变换变换W的函数，有(6-17)利用特征值方法可求出使J2(W)最大的W解。如果W是一个DD的线性变换，则J2是不变的，而此时(6-17)可进一

17、步表示成(6-18)用WD代替(6-17)中的W，以强调是DD变换 25第25页，共92页。6.3.2 按欧氏距离度量的特征提取方法(续3）l如果 是 的各特征值对应的特征向量所组成的矩阵，则由(6-18)式可得 l其中i表示 的各特征值。(6-19)式表明D维特征空间中，J2判据的值是 矩阵的全部特征值之和全部特征值之和。l那么由对应于d个最大的特征值的特征向量所组成的矩阵最大的特征值的特征向量所组成的矩阵W(Dd)，就能使所得到的d维特征满足J2判据最大的要求。l虽然J2，J3，J4乃至J5所采用的计算方法各不相同，但都得到一个同样的结论，如果矩阵 的特征值 按大小顺序列为：则选择前d个特

18、征值所对应的特征向量组成变换矩阵W（W=u1,u2,ud,都可使这些判据达到最大值，即 (6-19)D,21diiWJ12)(26第26页，共92页。6.3.2 按欧氏距离度量的特征提取方法(续4）l例6.1给定先验概率相等的两类，其均值向量分别为 ，协方差矩阵是：求用J2判据的最优特征提取。解：根据前面的分析，应先求 ，再求此矩阵的特征矩阵。今有混合均值 类间离散度矩阵：T0,1,0)(2121TiTiibS)()(212121412127第27页，共92页。6.3.2 按欧氏距离度量的特征提取方法(续5）类内离散度矩则接着，需求 的特征值矩阵。由于这是一个两类别分类问题，总均值向量值是两个

19、均值向量1和2的线性求和，则 中只有一个是独立的，因此 的秩是1，换句话说 只有一个非零特征值，W是D1矩阵，是一个向量W，求该向量需解方程：28第28页，共92页。6.3.2 按欧氏距离度量的特征提取方法(续6）或wwSTw121211)(41wT)(4121是标量，所以TwSw8,5,1 41)(211这就是所要求的解 因此利用W向量对原始的两维样本进行线性变换，得到新的一维分布，特征空间从两维降到一维，并满足J2判据。该特征空间实质上就是对应于Fisher准则求得的线性分类器法向向量，如果讨论的是多类别问题，则优化后的维数至多为类别减1。29第29页，共92页。6.4 按概率距离判据的特

20、征提取方法l这一节讨论如何依据不同类别分布概率密度函数来优化空间不同类别分布概率密度函数来优化空间，首先我们要回顾一下类分布概率密度函数在本课中表示为P(x|i),显然不同类别在特征空间X中的分布要尽可能不一样，则分类就比较容易，同俗的讲，不同类别在特征空间的不同区域聚集，则分类就容易，它们重迭的程度越低，越有利于分类，因此这一类可分性判据就是用各种方式来度量它们之间重迭的程度，一种是用P(x|1)到P(x|2)之间的乘积来计算其重迭程度，像Bhattacharya距离等，另一种用两者间的比值，成为散度。这一节只要了解这些最基本概念即可。6.4.1 基于概率分布的可分性判据6.4.2 按概率距

21、离判据提取特征30第30页，共92页。6.4.1 基于概率分布的可分性判据 P180l上一节讨论的是样本在特征空间的分布距离作为特征提取的依据。该种原理直观，计算简便。但是这种原理没有考虑概率分布，因此当不同类样本中有部分在特征空间中交迭分布时，简单地按距离划分，无法表明与错误概率之间的联系。下面讨论一些基于概率分布的可分性判据。l先研究两类情况：完全可分（图a),完全不可分（图b)(a)(b)=p(x|w2)31第31页，共92页。6.4.1 基于概率分布的可分性判据(续1）l如果我们不考虑各类的先验概率，或假设两类样本的先验概率相等，那末从两类条件概率分布可以看出：l如果两类条件概率分布互

22、不交迭，即对p(X|2)0处都有p(X|1)0，如图(a)所示，则这两类就完全可分；l另一种极端情况是对所有X都有p(X|1)p(X|2)，如图(b)所示，则两类就完全不可分。l可采用p(X|1)及p(X|2)这两个分布密度函数之间的距离分布密度函数之间的距离Jp来度量概概率分布交迭的程度。率分布交迭的程度。任何函数 ，如果满足下列条件：1.Jp是非负，即Jp0 2.当两类完全不交迭时Jp达到其最大值 3.当两类分布密度相同时，Jp0 都可用来作为类分离性的概率距离度量32第32页，共92页。6.4.1 基于概率分布的可分性判据(续2）l一些常用的概率距离度量一些常用的概率距离度量l（一)Bh

23、attacharyya距离和Chernoff界限 Bhattacharyya距离的定义用下式表示 显然，当p(X|1)p(X|2)对所有X值成立时JB0，而当两者完全不交迭时JB为无穷大。Chernoff界限的定义与其相似，为 其中S取0，1区间的一个参数。不难看出s=0.5时JC=JB。Bhattacharyya距离与错误率的上界有直接关系，不仅可用来对特征空间进行降特征空间进行降维优化维优化，而且也用来对分类器的错误率作出估计对分类器的错误率作出估计。dxxpxpJssC)|()|(ln21133第33页，共92页。6.4.1 基于概率分布的可分性判据(续3）m(二)散度另一种常用的基于概

24、率距离度量的判据是利用似然比或对数似然比。对两类问题，其对数似然比为：对i类及j 类的平均可分性信息分别定义为：因此，可定义散度JD为区分i和j 的总的平均信息：m散度和Bhattacharyya距离都满足类别可分离性判据条件34第34页，共92页。6.4.1 基于概率分布的可分性判据(续4）lJB和JD都比较复杂，当概率分布具有某种参数形式，尤其是正态分布时，这些判据可以进一步简化。假定 二类都是d维正态分布，分别表示为：即 对数似然比 35第35页，共92页。6.4.1 基于概率分布的可分性判据(续5）l利用矩阵迹的性质ATB=tr(BAT)，其中A、B表示向量，上式可改写成：将其代入Ii

25、j的计算公式，并化简得：由JD的定义 得：36第36页，共92页。6.4.1 基于概率分布的可分性判据(续6）l如果两类协方差矩阵相等，即 ，则 上式右部称为Mahalanobis距离的平方。从该式中可以看出在协方差矩阵相等条件下的散度与6.3.1中定义的Jd很相似，它们都是对样本在特征空间分散程度的描述，只是Jd是用欧氏距离度量，而JD是在协方差矩阵相等的条件下用Mahalanobis距离度量。l在正态分布时Bhattacharyya距离JB可表示成：37第37页，共92页。6.4.1 基于概率分布的可分性判据(续7）l当 时，而 JB与散度JD的表达式只差一个常系数。38第38页，共92页

26、。6.4.2 按概率距离判据提取特征 P189l这一节只是在正态分布条件下的一种特殊情况进行分析。l在讨论如何按概率距离判据概率距离判据进行特征提取时，与前面讨论欧氏距欧氏距离为基础的判据离为基础的判据的基本方法是一样的。l设原始特征为Y，而经变换后的特征为X，两者之间有映射关系：l利用这种关系，可以将有关判据的表达式表示成映射关系W的函数，例如JD(W)，然后求表达式对W各分量的偏导数，并令其为零，得到所需的方程式组，并用相应方法求解。l下面我们仅讨论两类别问题以及在协方差矩阵相等的条件下，用JD方法提取特征的算法。39第39页，共92页。6.4.2 按概率距离判据提取特征（续）l正态分布下

27、散度：l如写成矩阵的迹的形式，则有 其中 ，将 代入上式可得：l显然JD在降维后的最大值对应的变换应是 矩阵的特征向量矩阵，令 的特征值矩阵为，则有111111212()()()()TTTTTDJtr WWWWtr WMW40第40页，共92页。6.4.2 按概率距离判据提取特征（续）l对于两类别问题，的秩为1，故有其中为其特征值，此处W表示一个D1向量。将式代入有：其中是一标量，因而l利用该式，可使原D维特空间变换成一维的特征空间。与任何其它一维空间相比，散度JD达到极值(最佳)。l当12时计算会复杂得多，可能会遇到非线性方程，需要使用数值求解方法。41第41页，共92页。6.5 基于熵函数

28、的可分性判据 P183l我们知道一个样本不同类的后验概率不同类的后验概率是贝叶斯决策的依据贝叶斯决策的依据，因此在特征空间的任何一点，如果它对不同类别的经验概率差别很大，则为分类提供了很明确的信息，而Shannon信息论信息论定义的熵熵可用来对可分类性可分类性作出评价，称之为基于熵函数的可分性判据基于熵函数的可分性判据。l对某些特征，如果各类后验概率都相等，即(c为类别数)，则样本的类属就无法确定，或者只能任意指定样本所属类别。此时也就是错误率最大的情况。l如果考虑另一极端，假设有一组特征使得 ijXPXPji,0)|(,1)|(且42第42页，共92页。6.5 基于熵函数的可分性判据（续）l

29、那末此时的X肯定可划分为i，而错误率为零。l由此可看出，后验概率越集中，错误概率就越小后验概率越集中，错误概率就越小，反之后验概率分布越平缓，即接近均匀分布，则分类错误概率就越大。l为了衡量后验概率分布的集中程度衡量后验概率分布的集中程度，可以借助于信息论中熵熵的概念，制订定量指标定量指标。例如Shannon熵:l另一常用的平方熵43第43页，共92页。6.5 基于熵函数的可分性判据（续2）lShannon熵和平方熵都有熵函数的以下共性：、熵为正且对称，即函数式内,项的次序可以变换不影响熵的值2、若 、对任意的概率分布，以及则l显然，为了对所提取的特征进行评价，我们要计算空间每一点的熵函数。在

30、熵函数取值较大的那一部分空间，不同类的样本必然在较大的程度上互相重叠。因此熵函数的期望值可以表征类别的分离程度熵函数的期望值可以表征类别的分离程度，它可用来作为提取特征的分类性能的评价指标。44第44页，共92页。相对熵的概念及应用举例 P195 l相对熵相对熵：用来判别某个概率分布密度p(xi)偏离给定标准分布w(xi)的程度，表示成：求和在该特征所有可能的取值范围内进行。l相对熵越小，这两类概率分布的差别越大，当两类概率分布完全相同时，相对熵达最大值（等于零）。因此可以利用相对熵概念设计判别熵判别熵W(p,q)来表征两类分布p(xi)和q(xi)的差别大小。l而在多类的情况下则可用：来表示

31、各分布之间的分离程度。i,j 表示类别号 0)(/)(log)(),(iiixwxpxpwpV0),(),(),(pqVqpVqpW(6-44)(6-45)(6-46)45第45页，共92页。相对熵的概念及应用举例(续1）l为了计算方便，也可采用以下函数 来代替W(p,q)，而不影响选取d个最优特征的结果。其中pi与qi表示两类同一特征分布两类同一特征分布的函数，显然当两类特征向量各分量的分布都相等时，U(p,q)等于零。l在不对概率分布作估计的的情况下，可以用经过归一化处理的样本特征值来代替上面式中的概率分布：且 l 表示为第l类i特征值的“概率”，k是第一类样本集中的样本号，N1是第一类的

32、样本总数，i是特征号。由于 所以这样做是合理的。iiiqpqpU0)(),(2112)1(1)1()(1NkkiixNpDikix12)1(1)(Diip11)1(ip(6-47)(6-48)(6-49)46第46页，共92页。相对熵的概念及应用举例(续2）l下面我们讨论两类别问题中如何利用 进行特进行特征提取征提取。l首先定义这两类样本的协方差矩阵 与 ，协方差矩阵 的第 i行第 j 列元素为 其中n表示类别号，Nn为第n类样本数，表示第n 类第k个样本的第i个坐标值（特征）。l 利用这两个协方差矩阵，定义一个矩阵A，有 A=G(1)-G(2)iiiqpqpU0)(),(2 )(nkiX(6

33、-50)(6-51)47第47页，共92页。相对熵的概念及应用举例(续3）l利用(6-48)到(6-51)这一系列定义，(6-47)定义的判据函数U(p,q)在此可写为 与矩阵A的关系是：(6-52)其中Aii表示矩阵A的主对角线元素。l 因此特征提取的问题，就转换为：如何对特征空间进行某种变换，如何对特征空间进行某种变换，使得到的样本分布在新坐标系统中有最小的不确定性的问题使得到的样本分布在新坐标系统中有最小的不确定性的问题。换句话换句话说就是使两者分布存在尽可能大的差异问题说就是使两者分布存在尽可能大的差异问题。此问题可利用矩阵的特征值矩阵与特征向量矩阵来实现。l令矩阵A的特征值为k，相应

34、的特征向量为 uk,k=1,2,D 48第48页，共92页。相对熵的概念及应用举例(续4）l将A矩阵在由uk组成的坐标系统中的对应矩阵表示成A0，则在新的坐标系统中差别函数新的坐标系统中差别函数为：其中A0ii表示A0矩阵的主对角线元素。由于A0矩阵是A的特征值矩阵，是一个对角矩阵，因此有l 表示矩阵 中第 i 行第 i 列的元素。l剩下的问题就是证明(6-52)中的U值确实不小于(6-54)的U0值(6-53)(6-54)iiA)(20)(20A49第49页，共92页。相对熵的概念及应用举例(续5）l将(6-52)式右端表示成：其中利用A矩阵是对称矩阵的特点，即Aki=Aik，故求和式中只需

35、用ik的项。l由于A矩阵是样本在原矩阵是样本在原X坐标系中定义的坐标系中定义的，而A0则是在则是在uk 坐标坐标系中定义的系中定义的，这两个坐标系之间存在一种旋转关系T，旋转矩阵表示由 坐标系uk到X坐标系的转换，T=(Tik),i,k=1,2,D (6-56)T是正交归一矩阵，因此有:DikiDiiiikiiDiDikiikiiiiAAAAAAU1122211222)()(2)()(2)()(6-55)(6-57)50第50页，共92页。相对熵的概念及应用举例(续6）l而(6-58)故有l 因此如将矩阵A的特征值排列成:则取前则取前d个特征值所对应的特征向量个特征值所对应的特征向量u1,u2

36、,ud 构成坐标系统，构成坐标系统，可使判别熵在这个坐标系统中最小。可使判别熵在这个坐标系统中最小。51第51页，共92页。6.6 基于基于K-L变换的特征提取变换的特征提取 P212l正交变换概念正交变换概念变换是一种工具，它的用途归根结底是用来描述事物，特别是描变换是一种工具，它的用途归根结底是用来描述事物，特别是描述信号用的述信号用的。例如我们看到一个复杂的时序信号，我们希望能够对它进行描述，特别是希望用一些经济有效的方式进行描述。描述事物的基本方法之一是将复杂的事物化成简单事物的组合,或对其进行分解，分析其组成的成分。l变换的实质是一套度量用的工具变换的实质是一套度量用的工具，例如用大

37、尺子度量大的东西，用小尺子度量小的东西，在信号处理中用高频，低频或常量来衡量一个信号中的各种不同成分。l对某一套完整的工具就称为某种变换对某一套完整的工具就称为某种变换，如傅里叶变换就是用一套随时间正弦、余弦信号作为度量工具。52第52页，共92页。l例如，图A中的信号只有一个单一频率的简谐信号，而图B中信号就不是一个简谐信号所描述的，它起码可以分解成图C中的两个成分，一是基波，另一是三次谐波。l将变换中的每一成分，用一个向量ui表示，则正交变换正交变换可表示成：ABC jijiuujTi0153第53页，共92页。6.6.1 Karhunen-Loeve6.6.1 Karhunen-Loev

38、e变换变换lKarhunen-Loeve变换(以后称K-L变换)就是以样本特征向量在特征空间分布为原始数据，通过变换，找到维数较少的组合特征，达到降维的目的。l由于样本的描述都是离散的向量，因此我们只讨论K-L变换的离散情况。l K-L变换是一种正交变换变换是一种正交变换，即将一个向量X，在某一种坐标系统中的描述，转换成用另一种基向量基向量组成的坐标系表示。这组基这组基向量是正交的向量是正交的，其中每个坐标基向量用uj表示，j=1,，因此，一个向量X可表示成1jjjucX(6-59)54第54页，共92页。6.6.1 Karhunen-Loeve6.6.1 Karhunen-Loeve变换变换

39、(续续1)1)l对一向量或一向量空间进行正交变换，可采用多种不同的正交坐标采用多种不同的正交坐标系系，关键在于使用正交变换要达到的目的，不同的要求使用不同的正交变换。这里要讨论的是，如果我们将由(6-59)表示的无限多维基向量坐标系统无限多维基向量坐标系统改成有限维坐标系近似有限维坐标系近似，即l 表示X的近似值或估计量，我们希望在同样维数条件下，使向量X的估计量误差最小。确切地说是使所引起的均方误差:l为最小。K-L变换可以实现这个目的。djjjucX1(6-60)X(6-61)55第55页，共92页。6.6.1 Karhunen-Loeve变换变换(续续2)l如果将 代入(6-61)可得到

40、l由于uj,j1,，是正交归一坐标系，有:l所以有l系数cj可以利用正交坐标系的特性得到。如令某一基向量uj与向量X作点积，则有：TTjjiij ijij d 1i d 1i d 1 j d 1Ec uc uEc c u u (6-62)jijiuujTi01(6-63)12djjcE(6-64)(6-65)56第56页，共92页。6.6.1 Karhunen-Loeve变换变换(续续3)l根据(6-63)有：l代入（6-64)得l如令 ，则有 l用拉格朗日乘子法，可以求出在满足正交变换的条件下，使 达最小，即用函数：Tjjcu X(6-66)11djjTTjjTdjTjuXXEuuXXuE（

41、6-67）TXXE1djjTjuu57第57页，共92页。6.6.1 Karhunen-Loeve变换变换(续续4)l并令其对uj求导数，得：l可见向量 应是 矩阵的特征值 的特征向量，而此时截断误差为：,1,0)(djuIjj(6-68)1djjl如将 按其大小顺序排列，即 l则取前d项特征值对应的特征向量组成的坐标系，可使向 量的均方误差为最小。l满足上述条件的变换就是满足上述条件的变换就是K-LK-L变换。变换。58第58页，共92页。uK-L变换：当取矩阵 的d个最大本征值对应的本征向量来展开x x时，其截断均方误差最小。这d个本征向量组成的正交坐标系称作x x所在的D维空间的d维K-

42、LK-L变换坐标系变换坐标系，x x在K-L坐标系上的展开系数向量CC称作x x的K-L变换59第59页，共92页。6.6.2 K-L变换的性质 P215l(1)样本的样本的K-LK-L变换系数变换系数c cii与与c cj j是无关的是无关的。这可从样本集中任两个系数的乘积的期望值看出：l(2)K-L变换后的协方差矩阵为对角矩阵。(6-69)如我们令在K-L变换后的D维坐标系统中样本向量为X，则 X=c1,c2,T 而 60第60页，共92页。l将(6-69)代入得 为一对角矩阵，或写成UTU，其中U为由(u1,.uD)组成的向量矩阵。这表明经过K-L变换后，原向量各分量之间存在的相关性已被

43、消除。下图表示了一个二维空间中椭圆分布的样本集，在用K-L变换后新的坐标系中各分量的相关性消除。而在原坐标中x1,x2两个分量之间存在很明显的相关性。下图还反映了样本的u1分量比较分散，因而对分类可能起较大作用，而u2则对分类无太大作用，可以去掉。61第61页，共92页。lK-LK-L变换的一些典型应用变换的一些典型应用上面我们从数学的角度分析了K-L变换的性质。归结起来，它消除了各分量之它消除了各分量之间的相关性间的相关性，因而用它来描述事物时，可以减少描述量的冗余性，做到用最经济有效的方法描述事物。下面结合一些应用实例来说明如何运用K-L变换的这一性质。u1u262第62页，共92页。1降

44、维与压缩 以人脸图象为例来看，K-L变换的降维效果是十分明显的。对一幅人脸图象，如果它由M行与N列象素组成，则原始的特征空间维数就应为MN。而如果在K-L变换以及只用到30个基，那么维数就降至30，由此可见降维的效果是极其明显的。另一方面降维与数据压缩又是紧密联系在一起的。譬如原训练样本集的数量为V，而现采用30个基，每个基实质上是一幅图象，再加上每幅图象的描述参数，数据量是大大降低，尤其是图象数很大时，压缩量是十分明显的。63第63页，共92页。l2构造参数模型使用K-L变换不仅仅起到降维与压缩数据的作用，更重要的是每个描述量都有明确的意义，因而改变某一个参数就可让图象按所需要的方向变化。在

45、没有使用K-L变换的原数据集中对图象的描述量是每个象素的灰度值，而弧立地改变某个象素的灰度值是没有意义的。而在使用K-L变换后，每个描述量都有其各自的作用。因此通过改变这些参数的值就可实现对模型的有效描述，这在图象生成图象生成中是很有用的。因此利用K-L变换构造出可控制的，连续可调的参数模型在人脸识别与人脸图象重构方面的应用是十分有效的。64第64页，共92页。l3人脸识别利用K-L变换进行人脸图象识别是一个著名的方法。其原理十分简单，首先搜集要识别的人的人脸图象，建立人脸图象库，然后利用K-L变换确定相应的人脸基图象，再反过来用这些基图象对人脸图象库中的所有人脸图象进行K-L变换，从而得到每

46、幅图象的参数向量(试问用哪个公式试问用哪个公式？)并将每幅图的参数向量存起来。在识别时，先对一张所输入的脸图象进行必要的规范化，再进行K-L变换分析，得到其参数向量。将这个参数向量与库中每幅图的参数向量进行比较，找到最相似的参数向量，也就等于找到最相似的人脸，从而认为所输入的人脸图象就是库内该人的一张人脸,完成了识别过程。(试问：这种识别方法属于哪一种方法这种识别方法属于哪一种方法？)65第65页，共92页。l4人脸图象合成 用K-L变换构造参数模型的另一种典型用途是人脸图象合成。从下面的例子中可以看出，有目的的控制各个分量的比例，也就是通过调整参数向量。可以将一幅不带表情图象改变成带各种表情

47、的图象，称为人脸表情图象合成。下图为生成各种表情图象的示例。66第66页，共92页。l图中从上到下分别对应K-L变换后第一至第四个主分量，这四个主分量代表了人在不同表情下面部图像的主要变化。使用这四个分量，就可以描述面部表情的大部分变化，与变换以前的描述方法对比，原来要用几万个分量(图像中的各个象素)来描述这种情感图像的变化。67第67页，共92页。l从左到右是对每个分量赋以不同的值，而得到的合成图像，其中中间一列是取均值时的对应结果，最左一列是取到 (均值减三倍标准方差)时的合成图像，同样的，按照图像上边一行标出的意义，可以合成其它几列表情图像。68第68页，共92页。uPCA(Princi

48、ple Component Analysis)方法：进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。uK-L(Karhunen-Loeve)变换：最优正交线性变换，相应的特征提取方法被称为PCA方法69第69页，共92页。6.6.3 使用K-L变换进行特征提取 P218l 上面讨论K-L变换时得出K-L坐标系是由 的特征值对应的特征向量产生，因而 被称为K-L坐标系的产生矩阵。l 实际上使用不同的向量作为产生矩阵，会得到不同的K-L坐标系，从而满足不同的分类要求。l例如可用样本数据的协方差矩阵 作为产生矩阵产生矩阵。这跟 产生的K-L

49、坐标系是一样的。l另一种按分类均值i 及各类先验概率 Pi 考虑。如各类别协方差矩阵为 ,则可以用类内离散矩阵Sw作为产生矩阵，。如果只以某一样本集的协方差矩阵 作为产生矩阵其效果相当于只按类内离散程度进行特征选取。l 下面讨论一些不同的使用K-L变换的方法。()()TE xx70第70页，共92页。6.6.3.1 利用类均值向量提取特征l在讨论欧氏距离度量进行特征提取时，曾提到一些判据是从使类内尽类内尽可能密集可能密集，类间尽可能分开类间尽可能分开的设计思想出发的，可见类内离散程度与类间离散程度要结合起来考虑。l如何在K-L变换方法中体现对这两者的兼顾,可用不同的做法。一种做法是先按类内离散

50、度矩阵类内离散度矩阵Sw提供的信息提供的信息(作为产生矩阵)产生相应的K-L坐标系统，从而把包含在原向量中各分量的把包含在原向量中各分量的相关性消除相关性消除，得到在新坐标系中各分量离散的程度。然后对均值向量在这些坐标中分离的程度作出判断，为此可设判据为：(6-72)71第71页，共92页。6.6.3.1 利用类均值向量提取特征（续1）l上述判据表征变换后的特征 的分类性能，Xj表示在新坐标轴uj上的分量，lSb是类间离散度矩阵，i,分别是类均值与总体均值,P(i)是 i 类的先验概率。实际上(6-72)也可写作l可见J(Xj)是类间离散度与类内离散度类间离散度与类内离散度在uj这坐标的分量之