模式识别特征的选择和提取.ppt

《模式识别特征的选择和提取.ppt》由会员分享，可在线阅读，更多相关《模式识别特征的选择和提取.ppt（62页珍藏版）》请在三一文库上搜索。

1、第七章 特征的选择和提取,7.1 引言,以前讨论分类器设计时，都假定模式的特征向量已经提取出来了（有多少特征确定了）。 特征的多少（维数）、”好坏” 对分类器的设计和性能有很大的影响。 好的特征容易把类分开，或表示时误差较小。,1. 特征的维数和特征的“好坏”,特征选择和提取的任务是如何从许多特征中找出那些最有效的特征，把高维特征空间压缩到低维特征空间。 特征的种类有物理的、结构的、数学的。物理的、结构的特征，人的感觉器官容易感受，数学的特征，如均值、相关系数、协方差矩阵的特征值和特征向量等。 物理和结构特征和所处理的具体问题有关，在解决实际问题时可以依据具体问题而定。 这一节研究一般的特征提

2、取和选择的方法。,2. 几个术语的含义,在一些书籍和文献中，在不完全相同的意义上使用“特征提取”和“特征选择”的术语。例如“特征提取”，有的专指特征的形成过程，有的指特征的形成、经选择或变换后得到有效特征的过程。 为了方便以后的讨论，我们把特征提取、特征选择的含义明确一下。,模式特征的产生过程一般包括以下步骤： 1原始特征的形成：用仪表或传感器测量出来的一些特征量，或通过计算得到的一些特征（对波形和图象），称为原始特征、原始测量或一次特征。,2特征提取：原始特征的数量可能很大，需要通过变换（映射）把高维特征空间降到低维空间，这时的特征叫二次特征，它们一般是原始特征的某种组合。 通过变换A： X

3、 Y， 测量空间 特征空间 需要尽可能多地保留对分类和表示有利的信息。 好处 ：减少计算量; 在样本少时，便于估计密度函数；提高分类器设计的性能。,3特征选择：从得到的一组特征中，挑选最有效的特征以进一步减少特征空间的维数，得到它的一个有效子集。,特征的提取和选择是人类的一项基本智能活动，从相关和不相关信息中找出主要因素。 例如在细胞识别中，用变换的方法较少的特征，用选择的方法专家意见，或用数学方法进行筛选，从n个m个。 但“提取”和“选择”不是截然分开的。 具体指什么要从上下文去理解。 特征选择时，前m个最好的不一定组合后也是最好的。,特征提取可以看作是在减少维数的同时，又能代表、表示原观测

4、向量。 模式识别的任务是判别、分类。维数减少、一般错误率要增加，要限制在一定范围内。,7.2 基于特征向量分析的特征提取方法,这一节讨论基于相关矩阵或协方差矩阵的特征向量的特征抽取方法。这一方法和统计上的主因子分析以及随机过程中的K-L（Karhunen-Loeve）变换（展开）有密切关系。,1. 模式最优表示特征的提取,假定有一n维向量x，希望能用m（ n）个向量的线性组合来近似x，这m个向量来自一组标准正交基uj，j = 1，2，n。 即把x近似表示为前m个基的组合： = y1u1 + y2u2 + + ymum 式中 yj = ujT x,写成矩阵形式， = Um y ( n m，m 1

5、 ) n 1 y = UmT x ( m n，n 1 ) m 1 其中: y1 y = Um = u1 u2 um ym ,由于uj，j = 1，2，n是标准正交基，用 表示x时的误差（残差）为 = x - = 其中，yj = ujT x , j m 问题是找一组基uj ，使得均方误差 = E|2= E|x - |2 最小。 这时的yi 就是从x导出的特征，而 y = umT x就表示特征变换（由n维m维）。,根据误差公式和基是标准正交的条件， = ET = E（ ）（ ） = 如果把yj2 写成 yj2 =（yj）（yj）=（ujTx）(xTuj) 则 Eyj2=ujT ExxTuj =uj

6、TRuj ， 其中R是自相关矩阵,(*),= 要找一组基，使最小，同时要满足： ujT uj = 1，j = m+1, , n. 把约束ujT uj = 1用拉格朗日乘子（法）写入误差中，有 = +,（*）式的误差化为：,=2(Ruj uj)=0, j = m+1，,n 上式说明uj必须是R的特征向量。 （Re =e） 这样，= = = 为了使最小，特征向量 um+1，un 必须是对应最小特征值的，而近似x时所用的m个特征向量是对应m个最大特征值的。,使取极值的必要条件是：,+,上面推导出的特征还有其它意义上的最优性质。 一个分布的熵定义为 H = -Ep(y) 粗略地说，当分布很平、延伸很广

7、时，熵最大。如果x是零均值的高斯分布，那么可以证明所选择的特征向量具有最大熵。 这些特征向量沿最大方差方向，这样的方向是最随机的，最不确定的，这些方向应保留下来作为特征。对最不确定的事，若有信息（测量），最有用。,例 三维观测向量的特征提取 有一三维观测向量，其相关矩阵为 3 -1 0 R = -1 3 0 0 0 3 它的特征值和特征向量为 1 = 4， 2 = 3， 3 = 2,1/ 0 1/ e1 = -1/ e2 = 0 e3 = 1/ 0 1 0 要选一个特征，应选e1方向，均方误差是2 +3 = 5， 要选两个特征，应选e1 、e2方向，均方误差是3 = 2.,表示模式的特征和用于

8、分类的特征的不同 （1） 均值大小的影响 若均值较大，均值就会起大作用，特征在均值方向。 当两类问题的均值相差较大时，可以分类；但若均值差不多，则不会有好的效果。,m, R=+mmT,（2）也可以使用协方差矩阵，以均值为参考点，相对于均值。 （3）最好的表示特征不一定是最好的分类特征。 （3）有时可将坐标系移到一个类的均值处，这时相关矩阵的最大特征值的特征向量将沿两个均值的方向排列。,*7.3 多类问题的特征提取,下面介绍的方法是Fukunaga和Koontz在1970年提出的。 出发点是要同时考虑所有的类。,1. 两类时的情况,令R1和R2分别是两类观测向量的相关矩阵。即 Ri = Eixx

9、T ，i = 1，2 另 Q = R1 + R2 令S是一线性变换，使得 STQS = ST R1S + ST R2S = I (*) (R1 + R2 = I),其中 1/ S = v1 v2 vn 1/ 1/ vi和ui分别为Q的特征向量和特征值。,一般地说，S并不把R1和R2对角化，但通过S的线性变换，它把观测向量x变为： x = STx 变换后的相关矩阵为 Ri = STRiS 由（*）式有 R1 + R2 = I （*）,STQS = ST R1S + ST R2S = I,现在考虑在变换后新坐标系下的特征。 首先，注意到R1和R2的特征向量是相同的。 假设e是R1的一个特征向量，相

10、应的特征值是， 由（*）式： R2 e = (IR1)e = e-e =(1-)e e也是R2的特征向量，相应的特征值是(1),R1 + R2 = I,由于相关矩阵的R1 、R2是半正定的，它们的特征值是非负的， 01 这样，R1的大特征值正好是R2的小特征值， R1的小特征值正好是R2的大特征值，,这个关系如下图： R1 1 e1 11 R2 重 2 e2 12 要 性 n-1 e n-1 1n-1 减 n en 1n 小 重要性减小,对类1是最好的表示方向，对类2是最坏的，反之亦然。 如何来选特征呢？有两种可能的方法。 1每类各选m/2个最大特征值所对应的特征向量，当m是奇数时，再选一个不

11、管哪类的最大特征值所对应的特征向量。 2从两类的特征值中，不管哪一类，选最大的m个特征值所对应的特征向量。 一般地说，这两种方法谁好谁坏和具体问题有关。,一旦特征向量选好后，则特征变换由下式确定： ej1T y = Tx = ej2T STx， ： ej1T 其中S是满足STQS = I的矩阵。,* 2. C类时的情况,现在考虑将模式分为C类时的特征提取问题。 模式原来是用n维测量空间的向量x来表示的。每类的相关矩阵为Ri = EixxT 假定各个相关矩阵的最大特征值max1，这并不失一般性，可以通过调整线性空间的比例来实现。 又由于相关矩阵是半正定的，各Ri的特征值在01之间。,和前面一样，

12、令uj，j = 1，2，n是观测空间的标准正交基。另x是任一观测向量,x是它的截尾表示形式， x = y1u1 + y2u2 + + ymum 对于第i类，我们选择一组uj，它能使第i类的均方误差最小， i = Ei|x-x|2 = （*）,而同时使其它类的均方误差最大。 k = Ek|x-x|2 = (k = 1，2，c，ki) (*) 单独使i最小，而不管上式的条件已在前面讨论过。 若同时也满足（*）式的条件，将使得所选择的基能最优的表示第i类，但不能最优的表示其它类。 由于一般不能同时使i最小，而k最大，下面引入另外一个相关的准则。,和7.2节一样，可以表示 k = ，k=1，2，c 由

13、于Ri是半正定的，且max1， k的大小为下式限定： 0 kn-m， k =1，2，,c 这样，使（*）式最大等价于使下式最小（ki） (nm)k = =,k = Ek|x-x|2 =,(k = 1，2，c，ki) (*),最大k（ki，k=1，2，,c）和最小i的准则可以写成下面的组合形式，并用类数标准化。 Ci=,把i = 和（nm）k的表达式代入，有 Ci = 式中，Gi= (*) 上式的准则在形式上和7.2节讨论的一样。 为了选取m个特征向量ui来表示x,以使Ci最小，这时的特征向量应是Gi 的最大的m个特征值所对应的特征向量。,下面的分析说明确实是这样。假定e是Gi的标准特征向量，那

14、么相应特征值可以表示为 = eTGie = 由于max1和相关矩阵的半正定性质，上式括号中每一个二次项的特征值在01之间， 01。 而且接近于1时要求eTRie1,而eTRke(ki)却0，,这样，Gi的相应于特征值接近1的特征向量对应着i类最重要的特征。 当e = 2 时，（*）式变为 G1 + G2 = I 这和两类时的情况相似，G1 和 G2 的特征向量相同，其特征值间的关系和变换后的矩阵R1 、R2时的一样。,当C2时，情况就复杂了。 上述的方法还可以进一步简化。 可以把相关矩阵进行变换，使它满足 = = I 线性变换S的推导和上节一样。当使用变换后的相关矩阵时， Gi简化为 Gi=

15、1/c 2 Ri +(C2)I 当C = 2时，Gi= Ri，和前面的结果相同。,7.4 图像特征抽取的奇异值分解法,一幅图像可以表示为按一定顺序排列的像素的一个阵列（矩阵）。 假定阵列有N行N列，这时观测向量就由N2个像素的灰度值组成。由于观测向量的维数很大，我们希望用（抽取）图像的特征来表示图像。,图像特征抽取的方法有许多种。例如从二维频率谱中抽取特征。 这一节我们讨论由一组基图像的加权和表示图像的方法，这种方法和前面讨论过的利用特征值的特征抽取的方法很相似。,假定图像是用一个NN的矩阵B表示的，B的元素表示像素的灰度值。考虑两个NN的标准正交矩阵U和V，矩阵B可以变换为另一矩阵A， A

16、= UTBV 由于U和V是标准正交的，所以信息并无损失。B可以通过下式（*） B = UAVT = 式中aij 是A的元素，Ui、Vj 是U和V的列向量。,由于每一UiVjT都是一个NN矩阵，所以上式可以看作B图像在一组基图像下的展开，而aij是展开时的系数。 特征抽取的思路是找一组基（图像），从而可以用少数n个系数aij来表示原图像。这时的图像B是上式的截尾形式。而aij即它的特征。Hadamard、Harr和Fourier变换都可以实现这一目的。,下面要介绍的奇异值分解是另外一种方法。它使得矩阵A的元素只有对角线的元素非零。在这种基图像下，原图像只要用N个（或更少）的系数就可以表示了。,考

17、虑下面的矩阵的积 BBT=UAVT .VATUT=UAATUT 容易证明，BBT是对称的和半正定的。因此它有N个非零的实特征值和N个线性独立的特征向量。,A = UTBV,B = UAVT,如果U的列向量取BBT的特征向量，则AAT是由BBT的特征值所形成的对角矩阵。为了下面分析的方便，将AAT表示为（*） 12 AAT = 22 N2 同样，可以形成矩阵 BTB = VATUT .UAVT = VATAVT,如果V矩阵的列向量是BTB的列向量，则ATA必定有对角线形式 12 ATA = 22 （*） N2,（*）和（*）能同时满足的条件是i =i 。此时A是一对角矩阵，其对角线元素是1 ，2

18、 ，n 这时B化为 B = 其中ui和vi分别是BBT和BTB的特征向量。而i则由下式确定 i = uiTBvi i = 1，2，,N i称为B的奇异值。,上式可以用来计算图像B（或类似数据）的N个特征来表示B。另外，也可以选m(n)个最大的奇异值而放弃其余的奇异值。 当矩阵B不是方阵时，仍然可以进行奇异值分解。但奇异值的数目只能等于B的较小的维数。,当我们要把两类或更多的类进行分类时，所抽取的特征应该是最有效地保留了类的分离性。类的分离性准则和坐标系无关，而且和（信号）类的表示准则是完全不同的。,* 7.5 用于分类的特征的提取,类的分离性准则不仅和类的分布有关，而且和所用的分类器有关。例如

19、，对线性分类器最好的特征集，对其它类型的分类器就不一定是最好的特征集。 为了避免这种额外的复杂性，我们假定要找的最优的特征集是以贝叶斯分类器为基准的。 这样，类的可分性就等价于贝叶斯分类器的错误率。因此，从理论上说，贝叶斯错误率是特征的有效性的最好度量。,用贝叶斯错误率作为准则的一个主要缺点是较难得到它的数学表达式（除了少数特殊情况外）。在第三章我们曾经分析过，即使对正态分布，除了等协方差的情况外，贝叶斯错误率的计算也要用到数值积分。,下面将给出的几个准则都有很好的数学表达形式，它们是从物理概念中得到的。应当提醒的是，当提出一种准则时，这种准则的性能的分析都要和贝叶斯错误率联系起来。,一、分类

20、特征提取时的一些问题,1模式“表示”和模式“分类”的不同 模式分类特征的提取和模式表示特征的提取在许多方面是不同的，特别是所用的准则和所用的变换。,例如，在描述人类时，两眼、嘴、两只手、两条腿但是在区别东方人和欧洲人时，这些特征毫无用途。 因此，用于分类的特征的有效性准则是用类的重叠和分离来度量的，而不是均方误差的拟合。,B 变换,当特征抽取是用于模式的表示时，所用的变换一般是标准正交变换，因为标准正交变换保留了分布的形状。 而类的重叠和可分性在任何非奇异变换不是不变的，包括线性和非线性的变换。然而，任何奇异的变换都把X映射到较低维的Y，这时将损失一些分类的信息。,因此，用于分类的特征抽取可以

21、看作是在所有的可能的奇异变换中寻找最好的子空间，它尽可能地在最少的维数中保留了类的可分性。,C 分类的理想特征,如果能知道对于分类来说，哪些特征是最好的，这是我们最希望的。尽管有可能这些特征得不到。 由于贝叶斯分类器利用c个后验概率q1(x) =prw1|x,qc(x), 而 ， 这样，c类的分类问题就最少需要c-1个特征。而在这c-1维特征空间的错误率和原X空间的错误率是相同的。,这样，若利用变换yi = qi(x)，i=1,c-1, 从原n维空间变换到c-1维空间，则分类信息无任何损失。 称 qi(x)，, qc-1(x) 为理想的分类特征集。 *下图是在原X空间的三类的分布,虽然贝叶斯错

22、误率是评价特征集的最好准则，后验概率是理想的特征，但在实际问题中，后验概率函数难于得到，估计时又有很大的偏差和方差，贝叶斯错误率也难求。因此我们需要较简单而且容易实现的特征抽取算法。,两种方法 ： 基于散度矩阵的，利用类间可分性度量，但和贝叶斯错误率无直接关系； 基于贝叶斯错误率上界的，如基于Bhattacharyya 距离的，但只适用于两类。,7.5 特征选择问题,前面所抽取的特征是原来所有变量的函数。但是，在实际工作中，我们需要评价每个变量以及它们组合的有效性，是一个特征子集的选择问题。 从n个特征中选择m个，基于某种类可分性的准则，共有 种，组合数目很大， 如 = 2704156种。 因此，需要一些算法去避免穷尽搜索。,各种搜索方法,最优的搜索方法 动态规划，分枝限界 次优的搜索方法 顺序前向选择，顺序后向选择，浮动选择 启发式搜索 遗传算法，Tabu搜索，模拟退火，,