模式识别 6

1第六章特征的选择与提取P176§6.1基本概念§6.2类别可分离性判据§6.3按距离度量的特征提取方法§6.4按概率距离判据的特征提取方法§6.5基于熵函数的可分性判据§6.6基于K-L变换的特征提取§6.7特征提取方法小结§6.8特征选择2本章学习目的z1．了解特征空间选择在设计模式识别系统、解决模式识别具体问题中是至关重要的。z2．了解描述量选择，特征组合优化的两种基本方法，一是对原特征空间进行删选，另一种是通过变换改造原特征空间。z3．掌握典型的线性变换对原特征空间优化的基本方法，进一步深入理解模式识别处理问题的基本方法——确定准则函数，并通过计算进行优化。z4．了解并掌握特征选择方法使用的一些基本问题。3§6.1基本概念z分类器设计方法的研究固然重要，但如何确定合适的特征空间是设计模式识别系统另一个十分重要、甚至更为关键的问题。z如果所选用的特征空间能使同类物体分布具有紧致性，即各类样本分布在该特征空间中彼此分割开的区域内，这就为分类器设计成功提供良好的基础。z反之，如果不同类别的样本在该特征空间中混杂在一起，再好的设计方法也无法提高分类器的准确性。z本章内容属于如何构造一个特征空间，即对要识别的事物用什么方法进行描述、分析。4(1)物理量的获取与转换z物理量的获取与转换，指用什么样的传感器获取电信号。如摄取景物则要用摄像机；文字与数字识别，首先要用扫描仪等设备，手写体文字所用传感器与印刷体文字可能不同。这些都属于物理量的获取，并且已转换成电信号，为计算机分析打下了基础z对从传感器中得到的信号，可以称之为原始信息，因为它要经过加工、处理才能得到对模式分类更加有用的信号。5(2)描述事物方法的选择与设计z在得到了原始信息之后，要对它进一步加工，以获取对分类最有效的信息。这部分信息必须对原始信息进行加工，而设计所要信息的形式是十分关键的。z例如对阿拉伯数字的识别可以提出各种不同的想法，有的提出分析从框架的左边框到数字之间的距离变化反映了不同数字的不同形状，这可以用来作为数字分类的依据。z又有的方案则是强调分析不同截面的信号，如在框架的若干部位沿不同方向截取截面分析从背景到字，以及从字到背景转换的情况,如AB截面切割字符三次，CD截面切割字符一次等。6(3)特征空间的优化z这个层次的工作发生在已有了特征的描述方法之后，也就是已有了一个初始的特征空间，如何对它进行改造与优化的问题。z一般说来要对初始的特征空间进行优化是为了降维。即初始的特征空间维数较高。能否改成一个维数较低的空间，称为优化，优化后的特征空间应该更有利于后续的分类计算。z所谓优化是要求既降低特征的维数，又能提高分类器的性能。z两种基本方法:{特征选择(删掉部分特征){特征的组合优化(一种映射)，也就是说新的每一个特征是原有特征的一个函数。7补充材料——广义线性判别函数‹二次函数的一般形式：2012()gxccxcx=++‹g(x)又可表示成：映射X→Y11022123321yacyxacyxac⎡⎤⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥====⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎣⎦ya，31()Tiiigxay===∑ay8数学表达为了说得更明确，假设已有D维特征向量空间Y={y1,y2,…,yD,}则所谓特征选择是指从原有的D维特征空间，删去一些特征描述量，从而得到精简后的特征空间。在这个特征空间中，样本由D维的特征向量描述：X={x1,x2,…,xd}，d＜D。由于X只是Y的一个子集，因此每个分量xi必然能在原特征集中找到其对应的描述量xi＝yj。而特征提取则是找到一个映射关系：A:Y→X使新样本特征描述维数比原维数降低。其中每个分量xi是原特征向量各分量的函数，即xi=xi(y1,y2,…,yD)因此这两种降维的基本方法是不同的。在实际应用中可将两者结合起来使用，比如先进行优化组合，然后再进一步选择其中一部分，或反过来。9主要方法有：分支定界法、用回归建模技术确定相关特征等方法。特征选择法：当实际用于分类识别的特征数目d确定后，直接从已获得的D个原始特征中选出d个特征，使可分性判据J的值满足下式：dxxx,,,21()()[]JxxxJxxxdiiid1212,,,max,,,=式中是D个原始特征中的任意d个特征，上式表示直接寻找D维特征空间中的d维子空间。idiixxx,,,2110特征提取变换法，在使判据J取最大的目标下，对D个原始特征进行变换降维，即对原D维特征空间进行坐标变换，然后再取子空间。主要方法有：基于可分性判据的特征提取、基于误判概率的特征提取、离散K-L变换法(DKLT)、基于决策界的特征提取等方法。11思考题12思考题z1．什么叫特征空间？如果我们用颜色、尺寸、重量来衡量水果的构造,其特征空间是几维空间？z2．如果用颜色、尺寸与重量组成的特征空间来区分苹果与梨，你认为这三种度量中的哪种最有效？为什么？能否想像这两种水果在这个三维空间的分布？如果用这个特征空间来区分红苹果与樱桃，你想像一下这两类水果在特征空间如何分布？能否对这两种情况设计更经济有效的特征空间？13思考题z3．如果两类物体在一个二维特征空间如图分布,能否用删除其中任一维来优化特征空间？有没有什么方法能得到一个对分类很有利的一维特征空间？14思考题z4．上题的答案可用下图Y1与Y2组成的空间表示？你认为哪个分量可以删掉？z5．你有没有办法将原在X1、X2空间表示的数改成用Y1、Y2空间表示？15z特征选择与特征提取的任务：求出一组对分类最有效的特征，所谓有效是指在特征维数减少到同等水平时，其分类性能最佳。z因此需要有定量分析比较方法，判断所得到的特征维数及所使用特征是否对分类最有利，这种用以定量检验分类性能的准则称为类别可分离性判据。§6.2类别可分离性判据16§6.2类别可分离性判据（续）z对特征空间进行优化是一种计算过程，其基本方法仍然是模式识别的典型方法，即找到一种准则(或称判据)，采用优化方法，使这种准则达到一个极值。z判据，最理想的情况是与计算错误率有关的判据，贝叶斯公式就直接反映错误率，但在实际中运用有困难，因此又提出一些其它实用性强的判据。这些判据多多少少与错误率有关。大体分两类：{基于距离的可分性判据，是一种以计算样本在特征空间离散程度为基础的准则；{基于概率密度分布的判据。17希望所构造的可分性判据满足下列要求：(1)与误判概率(或误分概率的上界、下界)有单调关系。(2)当特征相互独立时，判据有可加性，即：JxxxJxijdijkdk(,,,)()121==∑式中，xxxd12,,,是对不同种类特征的测量值，Jij()⋅表示使用括号中特征时第i类与第j类可分性判据函数。18(3)判据具有“距离”的某些特性，即：Jij0，当ij≠时；Jij=0，当ij=时；JJijji=(4)对特征数目是单调不减，即加入新的特征后，判据值不减。JxxxJxxxxijdijdd(,,,)(,,,,)12121≤+19值得注意的是：上述的构造可分性判据的要求，即“单调性”、“叠加性”、“距离性”、“单调不减性”。在实际应用并不一定能同时具备，但并不影响它在实际使用中的价值。20{6.3.1基于距离的可分性判据{6.3.2按欧氏距离度量的特征提取方法§6.3按距离度量的特征提取方法216.3.1基于距离的可分性判据z基于距离的可分性判据的实质是Fisher准则的延伸，即综合考虑不同类样本的类内聚程度与类间的离散程度这两个因素。z基于距离度量是人们常用来进行分类的重要依据，因为一般情况下同类物体在特征空间呈聚类状态，即从总体上说同类物体内各样本由于具有共性，类内样本间距离应比跨类样本间距离小。zFisher准则正是以使类间距离尽可能大同时又保持类内距离较小这一种原理为基础的。z特征选择与特征提取中也使用类似的原理，被称为基于距离的可分性判据。226.3.1基于距离的可分性判据（续1）z为了度量类内、类间的距离，也可用另一种描述方法，即描述样本离散程度的方法。在讨论Fisher准则时曾用过两个描述离散度的矩阵。z一个是类间离散矩阵Sb：z另一个是类内离散度矩阵SW：SW＝S1+S2及（6-1）（6-2）236.3.1基于距离的可分性判据（续2）z以上式子是针对两类别情况的，如果推广至c类别情况，同时考虑各类的先验概率Pi不等，则可将上列各式表示成：zz其中为所有样本的总均值向量，Pi表示各类别的先验概率，Ei表示i类的期望符号。m（6-3）（6-4）246.3.1基于距离的可分性判据（续3）z利用(6-3)与(6-4)式可以将基于距离的可分性判据表示成以下形式：z1计算特征向量间平均距离的判据z其中“tr”表示矩阵的迹。(6-5)式实际上是从计算特征向量间总平均距离的公式推导得到的，该式可写成：z其中Pi、Pj分别表示各类的先验概率，ni、nj分别是第i与j类的样本个数，用来表示第i类第k个样本与j类第l个样本之间的距离度量。在欧氏距离情况下有：（6-6）（6-5）（6-7）256.3.1基于距离的可分性判据（续4）im利用均值向量与总均值向量，有代入(6-6)式可得：(6-10)中右边括弧里的前一项涉及类内各特征向量之间的平方距离，后一项则是类间距离项。后一项可写成：m（6-8）（6-9）（6-10）266.3.1基于距离的可分性判据（续5）∑∑∑===−−=−−cicjjiTjijiciiTiimmmmPPmmmmP11121)()()()(（6-11）显然利用(6-10)与(6-11)就可得到(6-5)。需指出的是由(6-6)推导的各式是利用有限样本数据，因此得到的都是母体各量的估计值，而(6-5)式用的是母体的离散度矩阵。2考虑类内类间欧氏距离的其它判据上面的判据Jd(X)是计算特征向量的总平均距离，以下一些判据则基于使类间离散度尽量大，类内离散度尽量小的考虑而提出：P186276.3.1基于距离的可分性判据（续6）其中表示是矩阵对应的行列式。可以证明J2,J3,J5在任何条件下非线性变换是不变的，J4与坐标系有关。||||)(5wbwSSSXJ+=（6-12）（6-13）（6-14)(6-15)28在特征空间中，当类内模式较密聚，而不同类的模式相距较远时，从直觉上我们知道分类就较容易，由各判据的构造可知，这种情况下所算得的判据值也较大。由判据的构造我们还可以初步了解运用这类判据的原则和方法。296.3.2按欧氏距离度量的特征提取方法P185基于距离可分性判据的特征优化过程是通过一个线性变换实现的。设在原特征空间一个样本向量表示成Y(D维)，在优化特征空间中，样本向量表示成X(d维)。X与Y之间的关系是：其中W是一个D×d维矩阵，现在的问题是要利用判据找出一种线性变换，利用这种变换，实现这种判据的极值化。例如使上一节定义的判据J2(x)达到极值。(6-16)306.3.2按欧氏距离度量的特征提取方法(续1）如果对特征空间实行一个D×D矩阵的非奇异线性变换，J2，J3与J5都保持不变。例如若对原特征空间实行一D×D线性变换A，则离散度矩阵，而映射变换后的J2(X)有：，为原空间（即y)离散度矩阵。，为映射后（即x）离散度矩阵bS*wS*bSwSp187316.3.2按欧氏距离度量的特征提取方法(续2）z下面讨论的特征提取变换，只考虑是降维的，即用D×d矩阵(d＜D)进行变换。其目的是在维数d的条件下，使相应的判据为最大。z在使用J2判据的情况下，可以将J判据表示成变换W的函数，有(6-17)利用特征值方法可求出使J2(W)最大的W解。如果W是一个D×D的线性变换，则J2是不变的，而此时(6-17)可进一步表示成(6-18)用WD代替(6-17)中的W，以强调是D×D变换326.3.2按欧氏距离度量的特征提取方法(续3）z如果是的各特征值对应的特征向量所组成的矩阵，则由(6-18)式可得z其中λi表示的各特征值。(6-19)式表明D维特征空间中，J2判据的值是矩阵的全部特征值之和。z那么由对应于d个最大的特征值的特征向量所组成的矩阵W(D×d)，就能使所得到的