搜索
第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)1§4.6基于Karhunen-Loeve变换的特征提取•K-L变换又称主分量分析，是一种正交变换，K-L变换常用来作为数据压缩，这里我们用它作降维，学习这一节主要要掌握以下几个问题：1．什么是正交变换2．K-L变换是一种最佳的正交变换，要弄清是什么意义的最佳，也就是说它最佳的定义。3．K-L变换的性质。4．K-L变换的重要应用。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)2§4.6.1Karhunen-Loeve变换正交变换概念•变换是一种工具，是用来描述事物，特别是描述信号用的。•描述事物的基本方法之一是将复杂的事物化成简单事物的组合,或对其进行分解，分析其组成的成分。•变换的实质是一套度量用的工具。•对某一套完整的工具就称为某种变换，如傅里叶变换就是用一套随时间正弦、余弦信号作为度量工具，这些正弦，余弦信号的频率是各不相同的，才能度量出信号中相应的不同频率成分。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)3图4.6-1一个正弦信号图4.6-2(a)另一种信号图4.6-2(b)信号的基波与谐波第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)4•对事物可以有不同的描述方法。对复杂事物进行经济有效的描述，我们希望将其分解成相互独立的成分，•用变换对信号进行分析，所使用的数学工具是点积。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)5•对正交变换的定义归为：如果将这种变换中的每一成分，用一个向量ui表示，i是其下标，原理上可以到∞，则正交变换可表示成：第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)6•以样本特征向量在特征空间分布为原始数据，通过实行Karhunen-Loeve变换，找到维数较少的组合特征，达到降维的目的。由于样本的描述都是离散的向量，因此我们只讨论Karhunen-Loeve变换(以后称K-L变换)的离散情况。•K-L变换的最佳：特征空间的降维，原特征空间是D维的，现希望降至d维dD。要找的正交变换能使一组样本集的截均方误差的期望值为最小。•K-L变换是一种正交变换，即将一个向量X，在某一种坐标系统中的描述，转换成用另一种基向量组成的坐标系表示。这组基向量是正交的，其中每个坐标基向量用ui表示，j=1,…,∞，因此，一个向量X可表示成：(4.6-1)第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)7•对一向量或一向量空间进行正交变换，可采用多种不同的正交坐标系，关键在于使用正交变换要达到的目的，不同的要求使用不同的正交变换。•如果将由(4.6-1)表示的无限多维基向量坐标系统改成有限维坐标系近似，即(4.6-2)表示X的近似值或估计量，我们希望在同样维数条件下，使向量X的估计量误差最小。确切地说是使所引起的均方误差：(4.6-3)第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)8•要找满足(4.6-3)式为最小是一个求极值的问题，求最佳的是正交变换的基ui，i=1,…∞。•同时还要满足变换是正交归一这个条件，因此这是一个求条件极值的问题。•至于对某一个数据X的相应cj值，可以通过X与每一个基uj的点积来计算。由于不同的基之间是相互正交的，这个点积值就是cj的值，即cj=ujTx•如果要求一组系数cj，并将其表示成一个向量形式C=(c1,c2,……)T，则可得：(4.6-4)第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)9•则U就是一个变换矩阵，其中每一行是某一个正交基向量的转置。由X计算C称为对X的分解。反过来，如果希望用C重构信号X，则它是各个成分之和。•如果我们将对应于每个基ui的成分表示成xi，则重构的信号又可表示成一个向量形式。(4.6-5)•显然，与原向量X是有差别的，是原向量的一个近似，要使与X的差异越小，则要用更多维数的正交基。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)10•如果将代入(4.6-3)可得到•由于uj,j＝1,…，∞是正交归一坐标系，有(4.6-6)所以有(4.6-7)•系数cj可以利用正交坐标系的特性得到。如令某一基向量uj与向量X作点积，则有(4.6-8)利用(4.6-6)有(4.6-9)第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)11•(4.6-9)代入(4.6-7)得(4.6-10)•如令则有•欲使该均方误差ε为最小，就变成在确保正交变换的条件下，使ε达最小的问题，这可用拉格朗日乘子法求解。为此设一函数：并令其对uj求导数，得(4.6-11)第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)12•可见向量ujj=d+1,…,∞应是ψ矩阵的特征值λj的特征向量，而此时截断误差为如将λj按其大小顺序排列，即则取前d项特征值对应的特征向量组成的坐标系，可使向量的均方误差为最小。•满足上述条件的变换就是K-L变换。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)13§4.6.2K-L变换的性质(1)样本的K-L变换系数ci与cj是无关的(4.6-12)(2)K-L变换后的协方差矩阵为对角矩阵。令在K-L变换后的D维坐标系统中样本向量为X'，则第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)14•∧为一对角矩阵。•表明经过K-L变换后，原向量各分量之间存在的相关性已被消除。图4.2表示在用K-L变换后新的坐标系中各分量的相关性消除。还反映了样本的w1分量比较分散，因而对分类可能起较大作用。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)15K-L变换的一些典型应用•K-L变换的性质：它消除了各分量之间的相关性，因而用它来描述事物时，可以减少描述量的冗余性，做到用最经济有效的方法描述事物。1．降维与压缩以人脸图象这个例子看，K-L变换的降维效果是十分明显的。对一幅人脸图象，如果它由M行与N到象素组成，则原始的特征空间维数就应为M×N。而如果在K-L变换以及只用到30个基，那么维数就降至30，由此可见降维的效果是极其明显的。另一方面降维与数据压缩又是紧密联系在一起的。譬如原训练样本集的数量为V，而现采用30个基，每个基实质上是一幅图象，再加上每幅图象的描述参数(式(4.6-9)中的C)，数据量是大大降低，尤其是图象数很大时，压缩量是十分明显的。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)162．构造参数模型使用K-L变换不仅仅起到降维与压缩数据的作用，更重要的是每个描述量都有明确的意义，因而改变某一个参数就可让图象按所需要的方向变化。在没有使用K-L变换的原数据集中对图象的描述量是每个象素的灰度值，而弧立地改变某个象素的灰度值是没有意义的。而在使用K-L变换后，每个描述量都有其各自的作用。因此通过改变这些参数的值就可实现对模型的有效描述，这在图象生成中是很有用的。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)173．人脸识别利用K-L变换进行人脸图象识别是一个著名的方法。其原理十分简单，首先搜集要识别的人的人脸图象，建立人脸图象库，然后利用K-L变换确定相应的人脸基图象，再反过来用这些基图象对人脸图象库中的有人脸图象进行K-L变换，从而得到每幅图象的参数向量并将每幅图的参数向量存起来。在识别时，先对一张所输入的脸图象进行必要的规范化，再进行K-L变换分析，得到其参数向量。将这个参数向量与库中每幅图的参数向量进行比较，找到最相似的参数向量，也就等于找到最相似的人脸，从而认为所输入的人脸图象就是库内该人的一张人脸,完成了识别过程。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)184．人脸图象合成用K-L变换构造参数模型的另一种典型用途是人脸图象合成。从下面的例子中可以看出，有目的的控制各个分量的比例，也就是通过调整参数向量。可以将一幅不带表情图象改变成带各种表情的图象，称为人脸表情图象合成。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)19第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)20图中从上到下分别对应K-L变换后第一至第四个主分量，这四个主分量代表了人在不同表情下面部图像的主要变化。使用这四个分量，就可以描述面部表情的大部分变化，与变换以前的描述方法对比，原来要用几万个分量(图像中的各个象素)来描述这种情感图像的变化。从左到右是对每个分量赋以不同的值，而得到的合成图像，其中中间一列是取均值时的对应结果，最左一列是取到均值减三倍标准方差时的合成图像，同样的，按照图像上边一行标出的意义，可以合成其它几列表情图像。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)21§4.6.3使用K-L变换进行特征提取•K-L坐标系是由E[XXT]的特征值对应的特征向量产生，因而E[XXT]被称为K-L坐标系的产生矩阵。(1)用样本数据的协方差矩阵作为产生矩阵(2)按分类均值及各类先验概率考虑各类别协方差矩阵类内离散矩阵SW作为产生矩阵(3)如果只以某一样本集的协方差矩阵作为产生矩阵，则效果是对该类样本集有信息压缩的最优性质。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)22例:设有两类问题，其先验概率相等，即:样本均值向量分别为：协方差矩阵分别为：为了把维数从2压缩为1，求SW的特征向量其特征值矩阵和特征向量分别是：第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)23因此作为一维特征空间的坐标轴。，第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)24§4.7特征提取方法小结•基于各种原理与判据的特征提取方法(1)一类基于对样本在特征空间分布的距离度量。其基本思想是通过原有特征向量线性组合而成新的特征向量，做到既降维，又能尽可能体现类间分离，类内聚集的原则。在欧氏距离度量的条件下所提出的几种判据都是从这一点出发的，如描述类内离散度与类间离散度的矩阵是两个主要描述样本分布的数据。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)25(2)利用K-L变换进行特征提取的方法也是出于同样的原理。是在原特征空间进行的一种特殊的正交变换，在其产生矩阵确定的范围内消除了特征各分量间的相关性，并从中选择有关的特征子空间。这一类方法由于直接从样本之间在特征空间中的距离度量出发，具有直观与计算简便等优点。但由于没有从概率分布考虑，与计算错误率没有直接的关系，当不同类别的样本存在交迭区时，所采用的特征提取结果无法保证有较小的错误率。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)26(3)从概率分布的差异出发，制订出反映概率分布差异的判据，以此确定特征如何提取。这类判据由于与错误率之间可能存在单调或上界关系等，因此从错误率角度考虑有一定的合理性。但是使用这种方法需要有概率分布的知识，并且只是在概率分布具有简单形式时，计算才比较简便。熵概念的运用是描述概率分布另一种有用的形式，使用时也可仿造本章中所举例子，将一些量折算成概率形式，利用熵原理构造的判据，进行特征提取。第四章特征的选择和提取2020/3/3中国矿业大学计算机科学与技术学院(31)27判别函数的极值往往演变为找有关距阵的特征值与特征向量，由相应的特征向量组成坐标系统的基向量。•特征提取各个方法中的共同特点计算有关矩阵的特征值矩阵与特征向量，选择前d个大特征值，以它们相应的特征向量构成坐标系统，这是大部特征提