04第四章 特征的选择与提取4.1-4.3.ppt

1、2020/7/12,中国矿业大学 计算机科学与技术学院,(28)1,第四章 特征的选择与提取,讨论的问题是对已有的特征空间进行改造，着重于研究对样本究竟用什么样的度量方法更好。使用什么样的特征描述事物，也就是说使用什么样的特征空间是个很重要的问题。这个问题称之为描述量的选择问题，又称特征的优化问题。,学习指南,对特征空间的改造、优化、主要有两种途径。一种是删选掉一些次要的特征，问题在于如何确定特征的重要性，以及如何删选。另一种方法是使用变换的手段，在这里主要限定在线性变换的方法上，通过变换来实现降维。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)2,了解特征空间的选择在设计

2、模式识别系统，解决模式识别具体问题中是至关重要的。,学习目的,了解描述量选择，特征组合优化的两种基本方法，一是对原特征空间进行删选，另一种是通过变换改造原特征空间。,典型的运用线性变换对原特征空间优化的基本方法，进一步深入理解模式识别处理问题的基本方法确定准则函数，并通过计算进行优化。,使用特征选择方法的基本问题。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)3,本章重点,1、弄清对特征空间进行优化的含义。,2、对特征空间进行优化的两种基本方法特征选择与特征的组合优化。,3、对特征空间进行优化的一些常用判据。,4、利用线段变换进行特征空间优化的基本方法。,2020/7/12

3、,中国矿业大学 计算机科学与技术学院,(28)4,1、要透彻理解什么叫特征空间的优化，为什么要对特征空间进行优化。,2、对特征空间进行优化，要用到一些数学工具，如向量点积、线性变换、正交变换、解决条件极值问题的拉格朗日乘子方法等。,本章难点,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)5,1、什么叫特征空间？如果我们用颜色、尺寸、重量来衡量水果的构造的特特空间是几维空间？,2、如果用颜色、尺寸与重量组成的特征空间来区分苹果与梨，你认为这三种度量中的哪种最有效？为什么？能否想像这两种水果在这个三维空间的分布？如果用这个特征空间来区分红苹果与樱桃，你想像一下这两类水果在特征空间

4、如何分布？能否对这两种情况设计更经济有效的特征空间？,课前思考题,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)6,3、如果两类物体在一个二维特征空间如图分布,能否用删除其中任一维来优化特征空间？有没有什么方法能得到一个对分类很有利的一维特征空间？,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)7,4、上题的答案可用下图Y1与Y2组成的空间表示？你认为哪个分量可以删掉？,5、有没有办法将原在X1、X2空间表示的数改成用Y1、Y2空间表示？,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)8,4.1 基本概念,特征空间如何设计的问题,如何确定合

5、适的特征空间是设计模式识别系统另一个十分重要，甚至更为关键的问题。如果所选用的特征空间能使同类物体分布具有紧致性，即各类样本能分布在该特征空间中彼此分割开的区域内，这就为分类器设计成功提供良好的基础。反之，如果不同类别的样本在该特征空间中混杂在一起，再好的设计方法也无法提高分类器的准确性。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)9,对要识别的事物用什么方法进行描述、分析的问题。有以下几个不同的层次：,1、物理量的获取与转换,对从传感器中得到的信号，可以称之为原始信息。,2、描述事物方法的选择与设计,在得到了原始信息之后，要对它进一步加工，以获取对分类最有效的信息。设计

6、所要信息的形式是十分关键的。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)10,设计对事物的描述方法是充分发挥设计者智慧的过程，这个层次的工作往往因事物而易，与设计者本人的知识结构也有关。这是一个目前还无法自动进行的过程。,例：印刷体数字识别,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)11,3、特征空间的优化,已有了一个初始的特征空间，如何对它进行改造与优化的问题。一般说来要对初始的特征空间进行优化是为了降维。即初始的特征空间维数较高。能否改成一个维数较低的空间，称为优化，优化后的特征空间应该更有利于后续的分类计算。,2020/7/12,中国矿业大学

7、计算机科学与技术学院,(28)12,例：用RGB颜色空间和HSI颜色空间,上图中右边是原始图像，左边是用HSI空间描述的同一图像(但是为了显示出来，用H对应R，S对应G，I对应B，然后再以RGB的方式显示出来)。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)13,确定特征空间包括若干层次：,把物体所具有的物理性质，结构性质等转换成计算机能处理的数学描述量。,使用传感器对样本的物理及其它属性进行转换与度量可得到对样本的原始度量。然而原始度量需要进一步转换成有效的特征。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)14,对特征空间进行优化有两种基本方法,1、

8、特征选择 ：删掉部分特征,已有D维特征向量空间：,xiyj,2、特征的组合优化 ：通过一种映射，说新的每一个特征是原有特征的一个函数。,已有D维特征向量空间：,找到一个映射关系： A:YX,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)15,思考题,1、研究模式识别中事物的描述方法主要靠什么？,其中若y1= x1 ， y2= x3 ，属哪一种方法：特征选择还是组合优化。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)16,4.2 类别可分离性判据,讨论的评价方法目的在于找出对特征空间进行优化的具体算法。,对特征空间进行优化是一种计算过程：,找到一种准则(或称

9、判据)，通常用一种式子表示；计算出一种优化方法，使这种计算准则达到一个极值。,判据：与计算错误率有关的判据,实用性强的判据,(1) 基于距离的可分性判据：计算样本在特征空间离散程度,(2) 基于概率密度分布的判据,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)17,4.3 按距离度量的特征提取方法,基于距离度量是人们常用来进行分类的重要依据，因为一般情况下同类物体在特征空间呈聚类状态，即从总体上说同类物体内各样本由于具有共性，因此类内样本间距离应比跨类样本间距离小。,Fisher准则正是以使类间距离尽可能大同时又保持类内距离较小这一种原理为基础的。,同样在特征选择与特征提取中

10、也使用类似的原理，这一类被称为基于距离的可分性判据。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)18,4.3.1 基于距离的可分性判据,度量类内、类间的距离，可用描述样本的离散程度的方法。,回顾Fisher准则中的各种距离定义：,类间离散度矩阵：,类内离散度矩阵：,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)19,推广至c类别情况，同时考虑各类的先验概率Pi不等,其中m为所有样本的总均值向量，Pi表示各类别的先验概率，Ei表示i类的期望符号。,(4.3-1),(4.3-2),2020/7/12,中国矿业大学 计算机科学与技术学院,(28)20,利用(4

11、.3-1)与(4.3-2)式可以将基于距离的可分性判据表示成以下形式：,(1) 计算特征向量间平均距离的判据,(4.3-3),其中“tr”表示矩阵的迹。(4.3-3)式实际上是从计算特征向量间总平均距离的公式推导得到的，该式可写成,(4.3-4),其中Pi、Pj分别表示各类的先验概率，ni、nj分别是第i与j类的样本个数，(Xk(i), Xl(i) 用来表示第i类的第k个与j类第l个样本之间的距离度量。在欧氏距离情况下有,(4.3-5),2020/7/12,中国矿业大学 计算机科学与技术学院,(28)21,均值向量,总均值向量,代入(4.3-4)式，可得,(4.3-6),(4.3-6)中右边括

12、弧里的前一项涉及类内各特征向量之间的平方距离，后一项则是类间距离项。后一项可写成 ：,(4.3-7),2020/7/12,中国矿业大学 计算机科学与技术学院,(28)22,(2) 考虑类内类间欧氏距离的其它判据,判据Jd(X)是计算特征向量的总平均距离，以下一些判据则基于使类间离散度尽量大，类内离散度尽量小的考虑而提出：,(4.3-8),(4.3-9),(4.3-10),(4.3-11),2020/7/12,中国矿业大学 计算机科学与技术学院,(28)23,4.3.2 按欧氏距离度量的特征提取方法,基于距离可分性判据的特征优化过程是通过一个线性变换实现的。,设在原特征空间一个样本向量表示成Y(

13、D维)而在优化以及的特征空间中，样本向量表示成X(d维)而X与Y之间的关系是：,W是一个Dd维矩阵，希望变换后的特征向量能满足使某个准则函数达到极值的要求。,如果对特征空间实行一个DD矩阵的非奇异线性变换，J2，J3 都保持不变。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)24,例如若对原特征空间实行一DD线性变换A，则离散度矩阵Sb与SW变为SbASbAT及SWASWAT，而映射变换后的J2(X)有：,其目的是在维数d的条件下，使相应的判据为最大。,在使用J2判据的情况下，可以将J判据表示成变换W的函数：,(4.3-12),求使J2(W)最大的W解可利用特征值方法。前面

14、曾提到如果W是一个DD的线性变换，则J2是不变的，而此时(4.3-12)可进一步表示成：,(4.3-13),其中用WD代替(4.3-12)中的W，以强调是DD变换。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)25,如果WDT 是SW-1 Sb 的各特征值对应的特征向量所组成的矩阵，则由(4.3-13)式可得：,(4.3-14),其中i表示SW-1 Sb的各特征值。,(4.3-14)式表明D维特征空间中，J2判据的值是SW-1 Sb矩阵的全部特征值之和。那么由对应于d个最大的特征值的特征向量所组成的矩阵W(Dd)，就能使所得到的d维特征满足J2判据最大的要求。,虽然J2，J

15、3，J5乃至J4所采用的计算方法各不相同，但都得到一个同样的结论，如果矩阵的特征值按大小顺序列为：,则选择前d个特征值所对应的特征向量组成变换矩阵W，都可使这些判据达到最大值。,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)26,例：给定先验概率相等的两类，其均值向量分别为：,协方差矩阵为：,求用J2判据的最优特征提取。,解：,先求SW-1 Sb，再求此矩的特征矩阵。,混合均值：,类间离散度矩阵：,2020/7/12,中国矿业大学 计算机科学与技术学院,(28)27,类内离散度矩阵：,求矩阵SW-1 Sb的特征值。由于这是一个两类别问题，总均值向量值是两个均值向量1和2的线性求和，则(1 -)中(2 -)只有一个是独立的，因此矩阵SW-1 Sb的