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

模式识别特征的选择和提取本讲稿第一页，共六十二页7.1引言以前讨论分类器设计时，都假定模式的特征向量已经提取出来了（有多少特征确定了）。特征的多少（维数）、”好坏”对分类器的设计和性能有很大的影响。好的特征容易把类分开，或表示时误差较小。1.特征的维数和特征的“好坏”本讲稿第二页，共六十二页特征选择和提取的任务是如何从许多特征中找出那些最有效的特征，把高维特征空间压缩到低维特征空间。特征的种类有物理的、结构的、数学的。物理的、结构的特征，人的感觉器官容易感受，数学的特征，如均值、相关系数、协方差矩阵的特征值和特征向量等。物理和结构特征和所处理的具体问题有关，在解决实际问题时可以依据具体问题而定。这一节研究一般的特征提取和选择的方法。本讲稿第三页，共六十二页2.几个术语的含义在一些书籍和文献中，在不完全相同的意义上使用“特征提取”和“特征选择”的术语。例如“特征提取”，有的专指特征的形成过程，有的指特征的形成、经选择或变换后得到有效特征的过程。为了方便以后的讨论，我们把特征提取、特征选择的含义明确一下。本讲稿第四页，共六十二页模式特征的产生过程一般包括以下步骤：1原始特征的形成：用仪表或传感器测量出来的一些特征量，或通过计算得到的一些特征（对波形和图象），称为原始特征、原始测量或一次特征。本讲稿第五页，共六十二页2特征提取：原始特征的数量可能很大，需要通过变换（映射）把高维特征空间降到低维空间，这时的特征叫二次特征，它们一般是原始特征的某种组合。通过变换A：X Y，测量空间 特征空间 需要尽可能多地保留对分类和表示有利的信息。好处：减少计算量;在样本少时，便于估计密度函数；提高分类器设计的性能。本讲稿第六页，共六十二页3特征选择：从得到的一组特征中，挑选最有效的特征以进一步减少特征空间的维数，得到它的一个有效子集。本讲稿第七页，共六十二页特征的提取和选择是人类的一项基本智能活动，从相关和不相关信息中找出主要因素。例如在细胞识别中，用变换的方法较少的特征，用选择的方法专家意见，或用数学方法进行筛选，从n个m个。但“提取”和“选择”不是截然分开的。具体指什么要从上下文去理解。特征选择时，前m个最好的不一定组合后也是最好的。本讲稿第八页，共六十二页特征提取可以看作是在减少维数的同时，又能代表、表示原观测向量。模式识别的任务是判别、分类。维数减少、一般错误率要增加，要限制在一定范围内。本讲稿第九页，共六十二页7.2基于特征向量分析的特征提取方法这一节讨论基于相关矩阵或协方差矩阵的特征向量的特征抽取方法。这一方法和统计上的主因子分析以及随机过程中的K-L（Karhunen-Loeve）变换（展开）有密切关系。本讲稿第十页，共六十二页1.模式最优表示特征的提取假定有一n维向量x，希望能用m（m问题是找一组基uj，使得均方误差=E|2=E|x-|2最小。这时的yi就是从x导出的特征，而y=umTx就表示特征变换（由n维m维）。本讲稿第十三页，共六十二页根据误差公式和基是标准正交的条件，=ET =E（）（）=如果把yj2 写成yj2=（yj）（yj）=（ujTx）(xTuj)则 Eyj2=ujTExxTuj=ujTRuj，其中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)粗略地说，当分布很平、延伸很广时，熵最大。如果x是零均值的高斯分布，那么可以证明所选择的特征向量具有最大熵。这些特征向量沿最大方差方向，这样的方向是最随机的，最不确定的，这些方向应保留下来作为特征。对最不确定的事，若有信息（测量），最有用。本讲稿第十七页，共六十二页例三维观测向量的特征提取有一三维观测向量，其相关矩阵为 3-10R=-130003它的特征值和特征向量为1=4，2=3，3=2本讲稿第十八页，共六十二页1/01/e1=-1/e2=0e3=1/010要选一个特征，应选e1方向，均方误差是2+3=5，要选两个特征，应选e1、e2方向，均方误差是3=2.本讲稿第十九页，共六十二页表示模式的特征和用于分类的特征的不同（1）均值大小的影响若均值较大，均值就会起大作用，特征在均值方向。当两类问题的均值相差较大时，可以分类；但若均值差不多，则不会有好的效果。mR=+mmT本讲稿第二十页，共六十二页（2）也可以使用协方差矩阵，以均值为参考点，相对于均值。（3）最好的表示特征不一定是最好的分类特征。（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 vn1/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的一个特征向量，相应的特征值是，由（*）式：R2 e=(IR1)e=e-e=(1-)ee也是R2的特征向量，相应的特征值是(1)R1+R2=I本讲稿第二十六页，共六十二页由于相关矩阵的R1 、R2是半正定的，它们的特征值是非负的，01这样，R1的大特征值正好是R2的小特征值，R1的小特征值正好是R2的大特征值，本讲稿第二十七页，共六十二页这个关系如下图：R11 e1 11 R2重 2 e212要 性 n-1 e n-11n-1减 n en 1n小重要性减小本讲稿第二十八页，共六十二页对类1是最好的表示方向，对类2是最坏的，反之亦然。如何来选特征呢？有两种可能的方法。1每类各选m/2个最大特征值所对应的特征向量，当m是奇数时，再选一个不管哪类的最大特征值所对应的特征向量。2从两类的特征值中，不管哪一类，选最大的m个特征值所对应的特征向量。一般地说，这两种方法谁好谁坏和具体问题有关。本讲稿第二十九页，共六十二页一旦特征向量选好后，则特征变换由下式确定：ej1Ty=Tx=ej2TSTx，：ej1T其中S是满足STQS=I的矩阵。本讲稿第三十页，共六十二页*2.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=（*）本讲稿第三十二页，共六十二页而同时使其它类的均方误差最大。k k=Ek|x-x|2=(k=1，2，c，ki)(*)单独使i i最小，而不管上式的条件已在前面讨论过。若同时也满足（*）式的条件，将使得所选择的基能最优的表示第i类，但不能最优的表示其它类。由于一般不能同时使i i最小，而k k最大，下面引入另外一个相关的准则。本讲稿第三十三页，共六十二页和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=k k=Ek|x-x|2=(k=1，2，c，ki)(*)本讲稿第三十四页，共六十二页最大 k k（ki，k=1，2，,c）和最小 i i的准则可以写成下面的组合形式，并用类数标准化。C Ci i=本讲稿第三十五页，共六十二页把 i i=和（nm）k k的表达式代入，有 C Ci i=式中，G Gi i=(*)上式的准则在形式上和7.2节讨论的一样。为了选取m个特征向量u ui i来表示x x,以使Ci最小，这时的特征向量应是Gi 的最大的m个特征值所对应的特征向量。本讲稿第三十六页，共六十二页下面的分析说明确实是这样。假定e e是Gi的标准特征向量，那么相应特征值可以表示为=e eT TGie e =由于max1和相关矩阵的半正定性质，上式括号中每一个二次项的特征值在01之间，01。而且接近于1时要求eTRie1,而eTRke(ki)却0，本讲稿第三十七页，共六十二页这样，G Gi i的相应于特征值接近1的特征向量对应着i类最重要的特征。当e=2 时，（*）式变为G1+G2=I这和两类时的情况相似，G1 和 G2 的特征向量相同，其特征值间的关系和变换后的矩阵R1、R2时的一样。本讲稿第三十八页，共六十二页当C2时，情况就复杂了。上述的方法还可以进一步简化。可以把相关矩阵进行变换，使它满足 =I线性变换S的推导和上节一样。当使用变换后的相关矩阵时，Gi简化为 Gi=1/c 2Ri+(C2)I当C=2时，Gi=Ri，和前面的结果相同。本讲稿第三十九页，共六十二页7.4 图像特征抽取的奇异值分解法 一一幅图像可以表示为按一定顺序排列的像素的一个阵列（矩阵）。假定阵列有N行N列，这时观测向量就由N2个像素的灰度值组成。由于观测向量的维数很大，我们希望用（抽取）图像的特征来表示图像。本讲稿第四十页，共六十二页图像特征抽取的方法有许多种。例如从二维频率谱中抽取特征。这一节我们讨论由一组基图像的加权和表示图像的方法，这种方法和前面讨论过的利用特征值的特征抽取的方法很相似。本讲稿第四十一页，共六十二页假定图像是用一个NN的矩阵B表示的，B的元素表示像素的灰度值。考虑两个NN的标准正交矩阵U和V，矩阵B可以变换为另一矩阵A，A=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个（或更少）的系数就可以表示了。本讲稿第四十四页，共六十二页考虑下面的矩阵的积BBT=UAVT.VATUT=UAATUT容易证明，BBT是对称的和半正定的。因此它有N个非零的实特征值和N个线性独立的特征向量。A=UTBVB=UAVT本讲稿第四十五页，共六十二页如果U的列向量取BBT的特征向量，则AAT是由BBT的特征值所形成的对角矩阵。为了下面分析的方便，将AAT表示为（*）1 12 2AAT=2 22 2 N N2 2同样，可以形成矩阵BTB=VATUT.UAVT=VATAVT本讲稿第四十六页，共六十二页如果V矩阵的列向量是BTB的列向量，则ATA必定有对角线形式 1 12 2ATA=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的奇异值。本讲稿第四十八页，共六十二页上式可以用来计算图像B（或类似数据）的N个特征来表示B。另外，也可以选m(n)个最大的奇异值而放弃其余的奇异值。当矩阵B不是方阵时，仍然可以进行奇异值分解。但奇异值的数目只能等于B的较小的维数。本讲稿第四十九页，共六十二页当我们要把两类或更多的类进行分类时，所抽取的特征应该是最有效地保留了类的分离性。类的分离性准则和坐标系无关，而且和（信号）类的表示准则是完全不同的。*7.5用于分类的特征的提取本讲稿第五十页，共六十二页类的分离性准则不仅和类的分布有关，而且和所用的分类器有关。例如，对线性分类器最好的特征集，对其它类型的分类器就不一定是最好的特征集。为了避免这种额外的复杂性，我们假定要找的最优的特征集是以贝叶斯分类器为基准的。这样，类的可分性就等价于贝叶斯分类器的错误率。因此，从理论上说，贝叶斯错误率是特征的有效性的最好度量。本讲稿第五十一页，共六十二页用贝叶斯错误率作为准则的一个主要缺点是较难得到它的数学表达式（除了少数特殊情况外）。在第三章我们曾经分析过，即使对正态分布，除了等协方差的情况外，贝叶斯错误率的计算也要用到数值积分。本讲稿第五十二页，共六十二页下面将给出的几个准则都有很好的数学表达形式，它们是从物理概念中得到的。应当提醒的是，当提出一种准则时，这种准则的性能的分析都要和贝叶斯错误率联系起来。本讲稿第五十三页，共六十二页一、分类特征提取时的一些问题1模式“表示”和模式“分类”的不同模式分类特征的提取和模式表示特征的提取在许多方面是不同的，特别是所用的准则和所用的变换。本讲稿第五十四页，共六十二页例如，在描述人类时，两眼、嘴、两只手、两条腿但是在区别东方人和欧洲人时，这些特征毫无用途。因此，用于分类的特征的有效性准则是用类的重叠和分离来度量的，而不是均方误差的拟合。本讲稿第五十五页，共六十二页B 变换 当特征抽取是用于模式的表示时，所用的变换一般是标准正交变换，因为标准正交变换保留了分布的形状。而类的重叠和可分性在任何非奇异变换不是不变的，包括线性和非线性的变换。然而，任何奇异的变换都把X映射到较低维的Y，这时将损失一些分类的信息。因此，用于分类的特征抽取可以看作是在所有的可能的奇异变换中寻找最好的子空间，它尽可能地在最少的维数中保留了类的可分性。本讲稿第五十六页，共六十二页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空间的三类的分布本讲稿第五十八页，共六十二页虽然贝叶斯错误率是评价特征集的最好准则，后验概率是理想的特征，但在实际问题中，后验概率函数难于得到，估计时又有很大的偏差和方差，贝叶斯错误率也难求。因此我们需要较简单而且容易实现的特征抽取算法。本讲稿第五十九页，共六十二页两种方法：基于散度矩阵的，利用类间可分性度量，但和贝叶斯错误率无直接关系；基于贝叶斯错误率上界的，如基于Bhattacharyya距离的，但只适用于两类。本讲稿第六十页，共六十二页7.5 特征选择问题 前面所抽取的特征是原来所有变量的函数。但是，在实际工作中，我们需要评价每个变量以及它们组合的有效性，是一个特征子集的选择问题。从n个特征中选择m个，基于某种类可分性的准则，共有 种，组合数目很大，如 =2704156种。因此，需要一些算法去避免穷尽搜索。本讲稿第六十一页，共六十二页各种搜索方法最优的搜索方法动态规划，分枝限界次优的搜索方法顺序前向选择，顺序后向选择，浮动选择启发式搜索遗传算法，Tabu搜索，模拟退火，本讲稿第六十二页，共六十二页