04第四章 特征的选择与提取4.6-4.8.ppt

《04第四章 特征的选择与提取4.6-4.8.ppt》由会员分享，可在线阅读，更多相关《04第四章 特征的选择与提取4.6-4.8.ppt（31页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第四章 特征的选择和提取4.6 基于Karhunen-Loeve变换的特征提取K-L变换又称主分量分析，是一种正交变换，变换又称主分量分析，是一种正交变换，K-L变换常变换常用来作为数据压缩，这里我们用它作降维，学习这一节用来作为数据压缩，这里我们用它作降维，学习这一节主要要掌握以下几个问题：主要要掌握以下几个问题：1什么是正交变换什么是正交变换 2K-L变换是一种最佳的正交变换，要弄清是什么意义的变换是一种最佳的正交变换，要弄清是什么意义的最佳，也就是说它最佳的定义。最佳，也就是说它最佳的定义。3K-L变换的性质。变换的性质。4K-L变换的重要应用。变换的重要应用。12/20/20221中国

2、矿业大学 计算机科学与技术学院第四章 特征的选择和提取4.6.1 Karhunen-Loeve变换正交变换概念正交变换概念变换是一种工具，是用来描述事物，特别是描述信号用的。变换是一种工具，是用来描述事物，特别是描述信号用的。描述事物的基本方法之一是将复杂的事物化成简单事物的描述事物的基本方法之一是将复杂的事物化成简单事物的组合组合,或对其进行分解，分析其组成的成分。或对其进行分解，分析其组成的成分。变换的实质是一套度量用的工具。变换的实质是一套度量用的工具。对某一套完整的工具就称为某种变换，如傅里叶变换就是用对某一套完整的工具就称为某种变换，如傅里叶变换就是用一套随时间正弦、余弦信号作为度量

3、工具，这些正弦，余弦一套随时间正弦、余弦信号作为度量工具，这些正弦，余弦信号的频率是各不相同的，才能度量出信号中相应的不同频信号的频率是各不相同的，才能度量出信号中相应的不同频率成分。率成分。12/20/20222中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取图图4.6-1 一个正弦信号一个正弦信号图图4.6-2(a)另一种信号另一种信号图图4.6-2(b)信号的基波与谐波信号的基波与谐波12/20/20223中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取对事物可以有不同的描述对事物可以有不同的描述方法。方法。对复杂事物进行经济有效的对复杂事物进行经济有效的描述，我们希

4、望将其分解成描述，我们希望将其分解成相互独立的成分，相互独立的成分，用变换对信号进行分析，用变换对信号进行分析，所使用的数学工具是点积。所使用的数学工具是点积。12/20/20224中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取对正交变换的定义归为：对正交变换的定义归为：如果将这种变换中的每一成分，用一个向量如果将这种变换中的每一成分，用一个向量ui表示，表示，i是是其下标，原理上可以到其下标，原理上可以到，则正交变换可表示成：，则正交变换可表示成：12/20/20225中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取以样本特征向量在特征空间分布为原始数据，通过实行以样本

5、特征向量在特征空间分布为原始数据，通过实行Karhunen-Loeve变换，找到维数较少的组合特征，达到变换，找到维数较少的组合特征，达到降维的目的。由于样本的描述都是离散的向量，因此我们降维的目的。由于样本的描述都是离散的向量，因此我们只讨论只讨论Karhunen-Loeve变换变换(以后称以后称K-L变换变换)的离散情况。的离散情况。K-L变换的最佳变换的最佳：特征空间的降维，原特征空间是特征空间的降维，原特征空间是D维的，现希望降至维的，现希望降至d维维dD。要找的正交变换能使一组样本集的截均方误差的要找的正交变换能使一组样本集的截均方误差的期望值为最小。期望值为最小。K-L变换是一种正

6、交变换，即将一个向量变换是一种正交变换，即将一个向量X，在某一种坐标在某一种坐标系统中的描述，转换成用另一种基向量组成的坐标系表示。系统中的描述，转换成用另一种基向量组成的坐标系表示。这组基向量是正交的，其中每个坐标基向量用这组基向量是正交的，其中每个坐标基向量用ui表示，表示，j=1,，因此，一个向量因此，一个向量X可表示成：可表示成：(4.6-1)12/20/20226中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取对一向量或一向量空间进行正交变换，可采用多种不同的对一向量或一向量空间进行正交变换，可采用多种不同的正交坐标系，关键在于使用正交变换要达到的目的，不同正交坐标系，关键

7、在于使用正交变换要达到的目的，不同的要求使用不同的正交变换。的要求使用不同的正交变换。如果将由如果将由(4.6-1)表示的无限多维基向量坐标系统改成有限表示的无限多维基向量坐标系统改成有限维坐标系近似，即维坐标系近似，即(4.6-2)表示表示X的近似值或估计量，我们希望在同样维数条件下，的近似值或估计量，我们希望在同样维数条件下，使向量使向量X的估计量误差最小。确切地说是使所引起的均方误差：的估计量误差最小。确切地说是使所引起的均方误差：(4.6-3)12/20/20227中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取要找满足要找满足(4.6-3)式为最小是一个求极值的问题，求最佳

8、的式为最小是一个求极值的问题，求最佳的是正交变换的基是正交变换的基ui，i=1,。同时还要满足变换是正交归一这个条件，因此这是一个求同时还要满足变换是正交归一这个条件，因此这是一个求条件极值的问题。条件极值的问题。至于对某一个数据至于对某一个数据X的相应的相应cj值，可以通过值，可以通过X与每一个基与每一个基uj的点积来计算。由于不同的基之间是相互正交的，这个点的点积来计算。由于不同的基之间是相互正交的，这个点积值就是积值就是cj的值，即的值，即cj=ujTx 如果要求一组系数如果要求一组系数cj，并将其表示成一个向量形式并将其表示成一个向量形式C=(c1,c2,)T，则可得：则可得：(4.6

9、-4)12/20/20228中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取则则U就是一个变换矩阵，其中每一行是某一个正交基向量就是一个变换矩阵，其中每一行是某一个正交基向量的转置。由的转置。由X计算计算C称为对称为对X的分解。反过来，如果希望用的分解。反过来，如果希望用C重构信号重构信号X，则它是各个成分之和。则它是各个成分之和。如果我们将对应于每个基如果我们将对应于每个基ui的成分表示成的成分表示成xi，则重构的信号则重构的信号又可表示成一个向量形式。又可表示成一个向量形式。(4.6-5)显然，与原向量显然，与原向量X是有差别的，是原向量的一个近似，要使是有差别的，是原向量的一个

10、近似，要使 与与X的差异越小，则要用更多维数的正交基。的差异越小，则要用更多维数的正交基。12/20/20229中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取如果将如果将代入代入(4.6-3)可得到可得到 由于由于uj,j1,，是正交归一坐标系，有是正交归一坐标系，有(4.6-6)所以有所以有(4.6-7)系数系数cj可以利用正交坐标系的特性得到。如令某一基向量可以利用正交坐标系的特性得到。如令某一基向量uj与向量与向量X作点积，则有作点积，则有(4.6-8)利用利用(4.6-6)有有(4.6-9)12/20/202210中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取(

11、4.6-9)代入代入(4.6-7)得得(4.6-10)如令如令则有则有欲使该均方误差欲使该均方误差为最小，就变成在确保正交变换的条为最小，就变成在确保正交变换的条件下，使件下，使达最小的问题，这可用拉格朗日乘子法求解。达最小的问题，这可用拉格朗日乘子法求解。为此设一函数：为此设一函数：并令其对并令其对uj求导数，得求导数，得(4.6-11)12/20/202211中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取可见向量可见向量uj j=d+1,应是应是矩阵的特征值矩阵的特征值j的特征向的特征向量，而此时截断误差为量，而此时截断误差为如将如将j按其大小顺序排列，即按其大小顺序排列，即则

12、取前则取前d项特征值对应的特征向量组成的坐标系，可使向量项特征值对应的特征向量组成的坐标系，可使向量的均方误差为最小。的均方误差为最小。满足上述条件的变换就是满足上述条件的变换就是K-L变换。变换。12/20/202212中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取4.6.2 K-L变换的性质(1)样本的样本的K-L变换系数变换系数ci与与cj是无关的是无关的(4.6-12)(2)K-L变换后的协方差矩阵为对角矩阵。变换后的协方差矩阵为对角矩阵。令在令在K-L变换后的变换后的D维坐标系统中样本向量为维坐标系统中样本向量为X，则则12/20/202213中国矿业大学 计算机科学与技

13、术学院第四章 特征的选择和提取 为一对角矩阵。为一对角矩阵。表明经过表明经过K-L变换后，原向量各分量之间存在的相关性变换后，原向量各分量之间存在的相关性已被消除。已被消除。图图4.2表示在用表示在用K-L变换变换后新的坐标系中各分量后新的坐标系中各分量的相关性消除。还反映的相关性消除。还反映了样本的了样本的w1分量比较分分量比较分散，因而对分类可能起散，因而对分类可能起较大作用。较大作用。12/20/202214中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取K-L变换的一些典型应用变换的一些典型应用K-L变换的性质：它消除了各分量之间的相关性，因而用它来变换的性质：它消除了各分量

14、之间的相关性，因而用它来描述事物时，可以减少描述量的冗余性，做到用最经济有效的描述事物时，可以减少描述量的冗余性，做到用最经济有效的方法描述事物。方法描述事物。1降维与压缩降维与压缩以人脸图象这个例子看，以人脸图象这个例子看，K-L变换的降维效果是十分明显的。变换的降维效果是十分明显的。对一幅人脸图象，如果它由对一幅人脸图象，如果它由M行与行与N到象素组成，则原始的特到象素组成，则原始的特征空间维数就应为征空间维数就应为MN。而如果在而如果在K-L变换以及只用到变换以及只用到30个基，个基，那么维数就降至那么维数就降至30，由此可见降维的效果是极其明显的。另一，由此可见降维的效果是极其明显的。

15、另一方面降维与数据压缩又是紧密联系在一起的。譬如原训练样本方面降维与数据压缩又是紧密联系在一起的。譬如原训练样本集的数量为集的数量为V，而现采用而现采用30个基，每个基实质上是一幅图象，个基，每个基实质上是一幅图象，再加上每幅图象的描述参数再加上每幅图象的描述参数(式式(4.6-9)中的中的C)，数据量是大大数据量是大大降低，尤其是图象数很大时，压缩量是十分明显的。降低，尤其是图象数很大时，压缩量是十分明显的。12/20/202215中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取2构造参数模型构造参数模型使用使用K-L变换不仅仅起到降维与压缩数据的作用，更重要的变换不仅仅起到降维与

16、压缩数据的作用，更重要的是每个描述量都有明确的意义，因而改变某一个参数就可是每个描述量都有明确的意义，因而改变某一个参数就可让图象按所需要的方向变化。让图象按所需要的方向变化。在没有使用在没有使用K-L变换的原数据集中对图象的描述量是每个象变换的原数据集中对图象的描述量是每个象素的灰度值，而弧立地改变某个象素的灰度值是没有意义的。素的灰度值，而弧立地改变某个象素的灰度值是没有意义的。而在使用而在使用K-L变换后，每个描述量都有其各自的作用。变换后，每个描述量都有其各自的作用。因此通过改变这些参数的值就可实现对模型的有效描述，这因此通过改变这些参数的值就可实现对模型的有效描述，这在图象生成中是很

17、有用的。在图象生成中是很有用的。12/20/202216中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取3人脸识别人脸识别利用利用K-L变换进行人脸图象识别是一个著名的方法。变换进行人脸图象识别是一个著名的方法。其原理十分简单，首先搜集要识别的人的人脸图象，建立其原理十分简单，首先搜集要识别的人的人脸图象，建立人脸图象库，然后利用人脸图象库，然后利用K-L变换确定相应的人脸基图象，再变换确定相应的人脸基图象，再反过来用这些基图象对人脸图象库中的有人脸图象进行反过来用这些基图象对人脸图象库中的有人脸图象进行K-L变换，从而得到每幅图象的参数向量并将每幅图的参数向变换，从而得到每幅图象的

18、参数向量并将每幅图的参数向量存起来。量存起来。在识别时，先对一张所输入的脸图象进行必要的规范化，在识别时，先对一张所输入的脸图象进行必要的规范化，再进行再进行K-L变换分析，得到其参数向量。将这个参数向量与变换分析，得到其参数向量。将这个参数向量与库中每幅图的参数向量进行比较，找到最相似的参数向量，库中每幅图的参数向量进行比较，找到最相似的参数向量，也就等于找到最相似的人脸，从而认为所输入的人脸图象也就等于找到最相似的人脸，从而认为所输入的人脸图象就是库内该人的一张人脸就是库内该人的一张人脸,完成了识别过程。完成了识别过程。12/20/202217中国矿业大学 计算机科学与技术学院第四章 特征

19、的选择和提取4人脸图象合成人脸图象合成用用K-L变换构造参数模型的另一种典型用途是人脸图象合成。变换构造参数模型的另一种典型用途是人脸图象合成。从下面的例子中可以看出，有目的的控制各个分量的比例，从下面的例子中可以看出，有目的的控制各个分量的比例，也就是通过调整参数向量。可以将一幅不带表情图象改变成也就是通过调整参数向量。可以将一幅不带表情图象改变成带各种表情的图象，称为人脸表情图象合成。带各种表情的图象，称为人脸表情图象合成。12/20/202218中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取12/20/202219中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取图中

20、从上到下分别对应图中从上到下分别对应K-L变换后第一至第四个主分量，这变换后第一至第四个主分量，这四个主分量代表了人在不同表情下面部图像的主要变化。使四个主分量代表了人在不同表情下面部图像的主要变化。使用这四个分量，就可以描述面部表情的大部分变化，与变换用这四个分量，就可以描述面部表情的大部分变化，与变换以前的描述方法对比，原来要用几万个分量以前的描述方法对比，原来要用几万个分量(图像中的各个象图像中的各个象素素)来描述这种情感图像的变化。来描述这种情感图像的变化。从左到右是对每个分量赋以不同的值，而得到的合成图像，从左到右是对每个分量赋以不同的值，而得到的合成图像，其中中间一列是取均值时的对

21、应结果，最左一列是取到均值其中中间一列是取均值时的对应结果，最左一列是取到均值减三倍标准方差时的合成图像，同样的，按照图像上边一行减三倍标准方差时的合成图像，同样的，按照图像上边一行标出的意义，可以合成其它几列表情图像。标出的意义，可以合成其它几列表情图像。12/20/202220中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取4.6.3 使用K-L变换进行特征提取 K-L坐标系是由坐标系是由EXXT的特征值对应的特征向量产生，的特征值对应的特征向量产生，因而因而EXXT被称为被称为K-L坐标系的产生矩阵。坐标系的产生矩阵。(1)用样本数据的协方差矩阵作为产生矩阵用样本数据的协方差矩

22、阵作为产生矩阵(2)按分类均值及各类先验概率考虑按分类均值及各类先验概率考虑 各类别协方差矩阵各类别协方差矩阵 类内离散矩阵类内离散矩阵SW作为产生矩阵作为产生矩阵(3)如果只以某一样本集的协方差矩阵作为产生矩阵，则效如果只以某一样本集的协方差矩阵作为产生矩阵，则效果是对该类样本集有信息压缩的最优性质。果是对该类样本集有信息压缩的最优性质。12/20/202221中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取例例:设有两类问题，其先验概率相等，即设有两类问题，其先验概率相等，即:样本均值向量分别为：样本均值向量分别为：协方差矩阵分别为：协方差矩阵分别为：为了把维数从为了把维数从2压

23、缩为压缩为1，求，求SW的特征向量的特征向量其特征值矩阵和特征向量分别是：其特征值矩阵和特征向量分别是：12/20/202222中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取因此因此 作为一维特征空间的坐标轴。作为一维特征空间的坐标轴。，12/20/202223中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取4.7 特征提取方法小结 基于各种原理与判据的特征提取方法基于各种原理与判据的特征提取方法(1)一类基于对样本在特征空间分布的距离度量。其基本思想是一类基于对样本在特征空间分布的距离度量。其基本思想是通过原有特征向量线性组合而成新的特征向量，做到既降维，通过原有特征向

24、量线性组合而成新的特征向量，做到既降维，又能尽可能体现类间分离，类内聚集的原则。又能尽可能体现类间分离，类内聚集的原则。在欧氏距离度量的条件下所提出的几种判据都是从这一点出在欧氏距离度量的条件下所提出的几种判据都是从这一点出发的，如发的，如描述类内离散度与类间离散度的矩阵是两个主要描述样本分描述类内离散度与类间离散度的矩阵是两个主要描述样本分布的数据。布的数据。12/20/202224中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取(2)利用利用K-L变换进行特征提取的方法也是出于同样的原理。变换进行特征提取的方法也是出于同样的原理。是在原特征空间进行的一种特殊的正交变换，在其产生矩

25、阵是在原特征空间进行的一种特殊的正交变换，在其产生矩阵确定的范围内消除了特征各分量间的相关性，并从中选择有确定的范围内消除了特征各分量间的相关性，并从中选择有关的特征子空间。关的特征子空间。这一类方法由于直接从样本之间在特征空间中的距离度量出这一类方法由于直接从样本之间在特征空间中的距离度量出发，具有直观与计算简便等优点。但由于没有从概率分布考发，具有直观与计算简便等优点。但由于没有从概率分布考虑，与计算错误率没有直接的关系，当不同类别的样本存在虑，与计算错误率没有直接的关系，当不同类别的样本存在交迭区时，所采用的特征提取结果无法保证有较小的错误率。交迭区时，所采用的特征提取结果无法保证有较小

26、的错误率。12/20/202225中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取(3)从概率分布的差异出发，制订出反映概率分布差异的从概率分布的差异出发，制订出反映概率分布差异的判据，以此确定特征如何提取。判据，以此确定特征如何提取。这类判据由于与错误率之间可能存在单调或上界关系等，因这类判据由于与错误率之间可能存在单调或上界关系等，因此从错误率角度考虑有一定的合理性。但是使用这种方法需此从错误率角度考虑有一定的合理性。但是使用这种方法需要有概率分布的知识，并且只是在概率分布具有简单形式时，要有概率分布的知识，并且只是在概率分布具有简单形式时，计算才比较简便。计算才比较简便。熵概念

27、的运用是描述概率分布另一种有用的形式，使用时也熵概念的运用是描述概率分布另一种有用的形式，使用时也可仿造本章中所举例子，将一些量折算成概率形式，利用熵可仿造本章中所举例子，将一些量折算成概率形式，利用熵原理构造的判据，进行特征提取。原理构造的判据，进行特征提取。12/20/202226中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取判别函数的极值往往演变为找有关距阵的特征值与特征向量，判别函数的极值往往演变为找有关距阵的特征值与特征向量，由相应的特征向量组成坐标系统的基向量。由相应的特征向量组成坐标系统的基向量。特征提取各个方法中的共同特点特征提取各个方法中的共同特点计算有关矩阵的特

28、征值矩阵与特征向量，选择前计算有关矩阵的特征值矩阵与特征向量，选择前d个大特征值，个大特征值，以它们相应的特征向量构成坐标系统，这是大部特征提取方以它们相应的特征向量构成坐标系统，这是大部特征提取方法的基本做法。法的基本做法。12/20/202227中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取(1)与错误概率或其上界或下界有单调关系，如能做到这一点，与错误概率或其上界或下界有单调关系，如能做到这一点，当判据达到其最大值时，一般说来其错误概率较小。当判据达到其最大值时，一般说来其错误概率较小。在特征提取方法中所使用的各种判据原理不尽相同，但在特征提取方法中所使用的各种判据原理不尽相

29、同，但一般希望判据能满足以下几点要求：一般希望判据能满足以下几点要求：基于概率分布的判据，如基于概率分布的判据，如Bhattacharyya距离和距离和Chernoff界界限符合这个条件，而基于特征空间分布欧氏距离度量的一些限符合这个条件，而基于特征空间分布欧氏距离度量的一些判据与错误概率没有直接关系。判据与错误概率没有直接关系。(2)判据在特征独立时有可加性，即判据在特征独立时有可加性，即 Jij表示第表示第i与与j类之间的可分性准则函数，类之间的可分性准则函数，Jij(xk)表示相应的表示相应的k分量的可分性准则函数。分量的可分性准则函数。12/20/202228中国矿业大学 计算机科学与

30、技术学院第四章 特征的选择和提取(3)可分性判别应满足可分性判别应满足即有可分性和对称性。即有可分性和对称性。(4)单调性，是指维数增多时，判据值不应减少。单调性，是指维数增多时，判据值不应减少。12/20/202229中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取4.8 特征选择 特征选择：对原有特征进行删选优化特征选择：对原有特征进行删选优化般人常想，只要逐个分析每个特征，判断它对分类的价值，般人常想，只要逐个分析每个特征，判断它对分类的价值，然后根据其优值删去或保留，这是一个为人们常采用方法，然后根据其优值删去或保留，这是一个为人们常采用方法，但是这种方法并不能保证特征空间的

31、最优组合优化，因此本但是这种方法并不能保证特征空间的最优组合优化，因此本节讨论了一些原理上更好的方法，由于方法本身比较繁琐，节讨论了一些原理上更好的方法，由于方法本身比较繁琐，本节不作为学习重点。本节不作为学习重点。12/20/202230中国矿业大学 计算机科学与技术学院第四章 特征的选择和提取有两个问题要解决：有两个问题要解决：(1)选择特性的标准，也就是选择前面讨论过的可分离性判选择特性的标准，也就是选择前面讨论过的可分离性判据，以这些判据为准则，使所选择的据，以这些判据为准则，使所选择的d维子空间具有最维子空间具有最大的可分离性。大的可分离性。(2)找出较好的特征选择方法，以在允许的时间内选择出一找出较好的特征选择方法，以在允许的时间内选择出一组最优的特征。所谓最优的特征组，就是要找到合适的组最优的特征。所谓最优的特征组，就是要找到合适的特征的组合。特征的组合。12/20/202231中国矿业大学 计算机科学与技术学院