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

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（ m问题是找一组基uj ，使得均方误差 = E|2= E|x - |2 最小。这时的yi 就是从x导出的特征，而 y = umT x就表示特征变换（由n维m维）。 nmjjjuy1xxx 根据误差公式和基是标准正交的条件， = ET = E（ ）（ ）

5、= 如果把yj2 写成yj2 =（yj）（yj）=（ujTx）(xTuj) 则 Eyj2=ujT ExxTuj =ujTRuj ， 其中R是自相关矩阵 nmiTiiuy1nmjjjuy1nmjjyE12(*) = = 要找一组基，使最小，同时要满足： ujT uj = 1，j = m+1, , n.把约束ujT uj = 1用拉格朗日乘子（法）写入误差中，有 = + +nmjjTjRuu1nmjjTjRuu1nmjjTjjuu1)1 (（*）式的误差化为： =2(Ruj uj)=0, , j = m+1，,n 上式说明uj必须是R的特征向量。 （Re =e） 这样，= = = = =为了使最小

6、，特征向量 um+1，un 必须是对应最小特征值的，而近似x时所用的m个特征向量是对应m个最大特征值的。 ju nmjjTjRuu1nmjjjTjuu1nmjj1j使取极值的必要条件是：nmjjTjRuu1nmjjTjjuu1)1 (+ + 上面推导出的特征还有其它意义上的最优性质。一个分布的熵定义为 H = -Ep(y)粗略地说，当分布很平、延伸很广时，熵最大。如果x是零均值的高斯分布，那么可以证明所选择的特征向量具有最大熵。这些特征向量沿最大方差方向，这样的方向是最随机的，最不确定的，这些方向应保留下来作为特征。对最不确定的事，若有信息（测量），最有用。 例 三维观测向量的特征提取 有一三

7、维观测向量，其相关矩阵为 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.2222表示模式的特征和用于分类的特征的不同（1） 均值大小的影响若均值较大，均值就会起大作用，特征在均值方向。当两类问题的均值相差较大时，可以分类；但若均值差不多，则不会有好的效果。m R=+mmT（2）也可以使用协方差矩阵，以均值为参考点，相对于均值。 （3）最好的表示特

8、征不一定是最好的分类特征。（3）有时可将坐标系移到一个类的均值处，这时相关矩阵的最大特征值的特征向量将沿两个均值的方向排列。 *7.3 多类问题的特征提取 下面介绍的方法是Fukunaga和Koontz在1970年提出的。出发点是要同时考虑所有的类。 1. 两类时的情况令R1和R2分别是两类观测向量的相关矩阵。即 Ri = EixxT ，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的特征向量和特征值。12n 一般地说，S并不

9、把R1和R2对角化，但通过S的线性变换，它把观测向量x变为： x = STx 变换后的相关矩阵为Ri = STRiS由（*）式有 R1 + R2 = I （*）STQS = ST R1S + ST R2S = I 现在考虑在变换后新坐标系下的特征。 首先，注意到R1和R2的特征向量是相同的。假设e是R1的一个特征向量，相应的特征值是，由（*）式：R2 e = (IR1)e = e-e =(1-)e e也是R2的特征向量，相应的特征值是(1) R1 + R2 = I 由于相关矩阵的R1 、R2是半正定的，它们的特征值是非负的， 01这样，R1的大特征值正好是R2的小特征值，R1的小特征值正好是R

10、2的大特征值，这个关系如下图： R1 1 e1 11 R2重 2 e2 12要 性 n-1 e n-1 1n-1减 n en 1n小 重要性减小 对类1是最好的表示方向，对类2是最坏的，反之亦然。如何来选特征呢？有两种可能的方法。1每类各选m/2个最大特征值所对应的特征向量，当m是奇数时，再选一个不管哪类的最大特征值所对应的特征向量。2从两类的特征值中，不管哪一类，选最大的m个特征值所对应的特征向量。一般地说，这两种方法谁好谁坏和具体问题有关。 一旦特征向量选好后，则特征变换由下式确定： ej1T y = Tx = ej2T STx， ： ej1T 其中S是满足STQS = I的矩阵。* 2.

11、 C类时的情况现在考虑将模式分为C类时的特征提取问题。模式原来是用n维测量空间的向量x来表示的。每类的相关矩阵为Ri = EixxT假定各个相关矩阵的最大特征值max1，这并不失一般性，可以通过调整线性空间的比例来实现。又由于相关矩阵是半正定的，各Ri的特征值在01之间。 和前面一样，令uj，j = 1，2，n是观测空间的标准正交基。另x是任一观测向量,x x是它的截尾表示形式，x = y1u1 + y2u2 + + ymum对于第i类，我们选择一组u uj，它能使第i类的均方误差最小，i i = Ei|x-x|2 = （*）dxxpxxi)|(|2 而同时使其它类的均方误差最大。 k k =

12、 Ek|x-x|2 = (k = 1，2，c，ki) (*)单独使i i最小，而不管上式的条件已在前面讨论过。若同时也满足（*）式的条件，将使得所选择的基能最优的表示第i类，但不能最优的表示其它类。由于一般不能同时使i i最小，而k k最大，下面引入另外一个相关的准则。dxxpxxk)|(|2 和7.2节一样，可以表示 k k = ，k=1，2，c由于R Ri i是半正定的，且max1， k k的大小为下式限定： 0 k kn-m， k =1，2，,c这样，使（*）式最大等价于使下式最小（ki）(nm)k k = = nmjjkTjuRu1nmjjkTjjTjuRuuu1nmjjkTjuRIu

13、1)(k k = Ek|x-x|2 =dxxpxxk)|(|2(k = 1，2，c，ki) (*)最大 k k（ki，k=1，2，,c）和最小 i i的准则可以写成下面的组合形式，并用类数标准化。C Ci i= = )(11cikkkimnc 把 i i = 和（nm） k k的表达式代入，有 C Ci i = =式中，G Gi i= = (*)上式的准则在形式上和7.2节讨论的一样。为了选取m个特征向量u ui i来表示x x,以使Ci最小，这时的特征向量应是Gi 的最大的m个特征值所对应的特征向量。nmjjkTjuRu1nmjjiTjuGu1)(11cikkkiRIRc 下面的分析说明确实

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

15、 = = I线性变换S的推导和上节一样。当使用变换后的相关矩阵时，Gi简化为 Gi= 1/c 2 Ri +(C2)I当C = 2时，Gi= Ri，和前面的结果相同。ckkTSRS1ckkR17.4 图像特征抽取的奇异值分解法 一一幅图像可以表示为按一定顺序排列的像素的一个阵列（矩阵）。假定阵列有N行N列，这时观测向量就由N2个像素的灰度值组成。由于观测向量的维数很大，我们希望用（抽取）图像的特征来表示图像。 图像特征抽取的方法有许多种。例如从二维频率谱中抽取特征。这一节我们讨论由一组基图像的加权和表示图像的方法，这种方法和前面讨论过的利用特征值的特征抽取的方法很相似。 假定图像是用一个NN的矩

16、阵B表示的，B的元素表示像素的灰度值。考虑两个NN的标准正交矩阵U和V，矩阵B可以变换为另一矩阵A，A = UTBV由于U和V是标准正交的，所以信息并无损失。B可以通过下式（*） B = UAVT = 式中aij 是A的元素，Ui、Vj 是U和V的列向量。NiNjTjiijvua11 由于每一UiVjT都是一个NN矩阵，所以上式可以看作B图像在一组基图像下的展开，而aij是展开时的系数。特征抽取的思路是找一组基（图像），从而可以用少数n个系数aij来表示原图像。这时的图像B是上式的截尾形式。而aij即它的特征。Hadamard、Harr和Fourier变换都可以实现这一目的。 下面要介绍的奇异

17、值分解是另外一种方法。它使得矩阵A的元素只有对角线的元素非零。在这种基图像下，原图像只要用N个（或更少）的系数就可以表示了。 考虑下面的矩阵的积 BBT=UAVT .VATUT=UAATUT容易证明，BBT是对称的和半正定的。因此它有N个非零的实特征值和N个线性独立的特征向量。A = UTBVB = UAVT 如果U的列向量取BBT的特征向量，则AAT是由BBT的特征值所形成的对角矩阵。为了下面分析的方便，将AAT表示为（* *） 1 12 2 AAT = = 2 22 2 N N2 2同样，可以形成矩阵BTB = VATUT .UAVT = VATAVT 如果V矩阵的列向量是BTB的列向量，

18、则ATA必定有对角线形式 1 12 2 ATA = = 2 22 2 （* * *） N N2 2 （*）和（*）能同时满足的条件是i = =i 。此时A是一对角矩阵，其对角线元素是1 ，2 ，n 这时B化为B = = 其中ui和vi分别是BBT和BTB的特征向量。而i则由下式确定 i = = uiTBvi i = 1，2，,N i 称为B的奇异值。NiTiiivu1 上式可以用来计算图像B（或类似数据）的N个特征来表示B。另外，也可以选m(n)个最大的奇异值而放弃其余的奇异值。当矩阵B不是方阵时，仍然可以进行奇异值分解。但奇异值的数目只能等于B的较小的维数。当我们要把两类或更多的类进行分类时

19、，所抽取的特征应该是最有效地保留了类的分离性。类的分离性准则和坐标系无关，而且和（信号）类的表示准则是完全不同的。* 7.5 用于分类的特征的提取 类的分离性准则不仅和类的分布有关，而且和所用的分类器有关。例如，对线性分类器最好的特征集，对其它类型的分类器就不一定是最好的特征集。为了避免这种额外的复杂性，我们假定要找的最优的特征集是以贝叶斯分类器为基准的。这样，类的可分性就等价于贝叶斯分类器的错误率。因此，从理论上说，贝叶斯错误率是特征的有效性的最好度量。 用贝叶斯错误率作为准则的一个主要缺点是较难得到它的数学表达式（除了少数特殊情况外）。在第三章我们曾经分析过，即使对正态分布，除了等协方差的

20、情况外，贝叶斯错误率的计算也要用到数值积分。 下面将给出的几个准则都有很好的数学表达形式，它们是从物理概念中得到的。应当提醒的是，当提出一种准则时，这种准则的性能的分析都要和贝叶斯错误率联系起来。一、分类特征提取时的一些问题1模式“表示”和模式“分类”的不同模式分类特征的提取和模式表示特征的提取在许多方面是不同的，特别是所用的准则和所用的变换。例如，在描述人类时，两眼、嘴、两只手、两条腿但是在区别东方人和欧洲人时，这些特征毫无用途。因此，用于分类的特征的有效性准则是用类的重叠和分离来度量的，而不是均方误差的拟合。B 变换 当特征抽取是用于模式的表示时，所用的变换一般是标准正交变换，因为标准正交变换保留了分布的形状。而类的重叠和可分性在任何非奇异变换不是不变的，包括线性和非线性的变换。然而，任何奇异的变换都把X映射到较低维的Y，这时将损失一些分类的信息。因此，用于分类的特征抽取可以看作是在所有的可能的奇异变换中寻找最好的子空间