5-特征提取与选择

第五章特征的选择与提取§1类别可分离性判据§2特征提取§3特征选择特征提取与选择的基本任务是研究如何从众多特征中求出那些对分类识别最有效的特征，从而实现特征空间维数的压缩,即获取一组“少而精”且分类错误概率小的分类待征.可以把特征分为三类1物理的；2结构的；3数学的。分类器x1x2x3..xd对象选择.提取模式的特征的有效性直接影响分类器的设计和性能.由信息获取部分获得的原始数据量一般是相当大的.为了有效地实现分类识别，要对原始数据进行选择或变换，得到最能反应分类本质的待征，构成特征向量.这就是特征抽取与选择的过程.传感器y1y2y3..ym学习.训练在一个较完善的模式识别系统中，明显或隐含的要有特征提取与选择技术环节，其通常处于对象特征数据采集和分类识别两个环节之间.基本概念特征选择：从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的，这个过程叫特征选择。特征提取：将一组高维特征，通过变换的方法得到一组新的低维特征，这个过程叫特征提取。特征形成：根据被识别的对象产生出一组基本特征（也可称为原始特征），它可以是计算出来的，也可以是用仪表或传感器测量出来的。特征提取：模式空间特征空间高维低维特征选择：特征集特征子集变换挑选特征提取器特征选择器说明：有时特征提取和选择并不是截然分开的。例如，可以先将原始特征空间映射到维数较低的空间，在这个空间中再进行选择以进一步降低维数；也可以先经过选择去掉那些明显没有分类信息的特征，再进行映射以降低维数。即在模式识别中，特征提取与特征选择作为两个过程，它们的先后次序并不是固定不变的。在处理实际问题时，可以根据具体情况决定先进行哪一个过程。本章讨论特征的选择与提取方法.特征提取特征选择§1类别可分离性判据1.准则函数-判据2.基于类间距离的可分性判据3.基于概率分布的可分性判据4.基于熵函数的可分性判据1.准则函数特征选择与提取的任务是求出一组对分类最有效的特征，因此我们需要一个定量的准则（或称判据）来衡量特征对分类的有效性。由于直接用错误概率作为标准来分析特征的有效性比较困难我们希望找出另外一些更实用的准则来衡量备类间的可分性，并希望可分性准则满足下列几条要求1)与错误概率（或它的上下界）有单调关系2)当特征独立时有可加性3)度量特性（非负性，互反性）4)单调性，即加入新的特征时，判据不减小2.类内类间距离各类样本可以分开是因为它们位于特征空间的不同区域，显然这些区域之间距离越大，类别可分性就越大。基本思想：考虑最简单的两类情况，ω1和ω2，ω1中任一点与ω2中的每一点都有一个距离，把所有这些距离相加求平均，可用这个均值来代表这两类之间的距离,多类情况是基于它的推导。如何表示两个类区之间的距离?我们定义各类特征向量之间的平均距离为：()(),ijijijklcdnnppxxij其中:为类别数,为两个向量间的欧氏距离，为对应类中样本数，是相应类别的先验概率分别为类和类中的特征向量()()()()()()(,)()()ijijTijklklkldxxxxxx()111,inciikiikiixpmn1()()11()()1()()icTbiiiinciiTwikikiikiSpSpxxn代入化简可得()()dbwJXtrSS说明1)基于类内类间距离的可分离性判据是一种常用的判据，它实际上是各类向量之间的平均距离。2)具体而言，即J（x）表示各类特征向量之间的平均距离，我们通常认为J（x）越大，可分离性越好。3)这种判据优点是计算简单；缺点是当类间距离较小，类内距离较大时，判据仍有可能取得较大的值，而此时的可分离性并不大。3.基于概率分布的可分性判据上面介绍的距离准则是直接从各类样本间的距离算出的,没有考虑各类的概率分布,不能确切表明各类交叠的情况，因此与错误概率没有直接联系,下面提出一些基于概率分布的可分性判据.两个分布密度函数之间的距离任何函数J，如果满足下述条件，都可用来作为类分离性的概率距离度量。1)J具有非负性2)当两类完全不交叠时，J取最大值3)当两类分布密度相同时，J应为0如图所示，图1表示两类为完全可分的情况，而图2则表示两类完全不可分的。P（x∣ω1）=P（x∣ω2）图2图1P（x∣ω1）P（x∣ω2）=0(1)Bhattacharyya距离12ln[(|1)(|2)]BJpxpxdx1ln(|1)(|2)ssCJpxpxdx注：s是在[0，1]区间取值的一个参数，当s=0.5时，上述二者相等(2)Chernoff距离定义散度等于各类平均可分信息之和：(|1)[(|1)(|2)]ln(|2)DijjiJIIpxpxpxdxpx(3)散度(/1)()ln(/2)ijpxlxpx对数似然比可以提供ω1类对ω2类的可分性信息(|1)[()](|1)ln(|2)ijijpxIElxpxdxpxω1类对ω2类的平均可分性信息为4.基于熵函数的可分性判据最佳分类器由后验概率确定，所以可由特征的后验概率分布来衡量它对分类的有效性。两种特殊情形下最佳分类器的错误率:1)各类后验概率是相等(/)1/,1,2,...,ipxcic(/)11/(1)/pexccc错误率(/)0pex错误率2)(/)1,(/)0,,1,2,...,jipxpxijic可见后验概率越集中,错误概率就越小.后验概率分布越平缓(接近均匀分布)，则分类错误概率就越大.设ω为可能取值为ωi,(i=1,2,…,c)的一个随机变量,它的取值依赖于分布密度为p(x)的随机向量x(特征向量)，即给定x后ω的概率为p(ω/x).为了衡量后验概率分布的集中程度，需要规定一个定量准则.我们可以借助于信息论中关于熵的概念.我们想知道的是：给定某一x后，我们从观察得到的结果中得到了多少信息?或者说ω的不确定性减少了多少?从特征提取的角度看，显然用具有最小不确定性的那些特征进行分类是有利的。在信息论中用“熵”作为不确定性的度量.ωiωjωiωj重叠程度越大熵函数值越大1)广义熵1211[(/),(/),...,(/)][(/)1/]21ccciiJpxpxpxpxcα为大于1的正数2)Shannon熵1121111[(/),(/),...,(/)][(/)1/]lim21(/)ln(/)ccciiciiiJpxpxpxpxcpxpx3)平方熵21221[(/),(/),...,(/)]2[(/)1]ccciiJpxpxpxpx为了对所提取的特征进行评价，我们要计算空间每一点的熵函数.在熵函数取值较大的那一部分空间，不同类的样本必然在较大的程度上互相重叠.可以表征类别的分离程度，它可用来作为所提取特征的分类性能的准则函数.12{[(/),(/),...,(/)]}ccJEJpxpxpx因此熵函数的期望值§2特征提取1按欧氏距离度量的特征提取方法2基于判别熵最小化的特征提取3两维显示4基于主成分变换的特征提取方法y1y2ymo特征提取x1x2x3xdodmX空间d维原始特征集Y空间m维新特征集变换12(,,...,)1,2,...,kkdygxxxkm确定变换的依据:类别可分性判据目标:在新的特征空间中,各类之间容易区分.①s阶Minkowski度量11(,)[]dssMklkjljjdxxxx多维空间中两个向量之间有多种距离度量，下面是一些最重要的例子：1按欧氏距离度量的特征提取方法②欧氏距离在Minkowski度量中，令s=2，得到常用的欧氏距离：2121(,)[()]dEklkjljjdxxxx③Chebychev距离:棋盘距离(,)maxTklkjljjdxxxx④Mahalanobis距离:(,)()()TQklklkldxxxxQxx式中Q是给定的正定标尺矩阵所有上面x的下标的意义如下：当只有一个下标时，此下标表示样本号；有两个下标时，第一个为样本号，第二个表示该样本的特征序号。以上的各种距离度量在实际应用中，在计算的复杂性方面，在是否便于进行解析分析以及用它进行特征提取的效果方面都各不相同。由于欧氏距离在很多情况下便于分析和计算.前面已经推导出了基于欧氏距离的一种度量函数，1()()wbJxtrSS其中Sb为类间离散度矩阵,Sw为类内离散度矩阵.同样的，我们还可以提出下面各种判据：12345(),ln[](),()bwbwwbbwwSJtrSSJSSStrSJJtrSS以J2为例,特征提取的步骤如下①作线性映射：TYWX其中X为d维原始特征向量；Y为m维压缩后的特征向量1212[,,,][,,,]TmTdYyyyXxxxWm为d矩阵②令**,TTbbwwSWSWSWSW其中Sw，Sb为原空间（即X的）离散度矩阵，S*w，S*b为映射后（即Y的）离散度矩阵③J2的表达式为：*1*21()[][()()]wbTTwbJWtrSStrWSWWSW④求变换矩阵W,使J2（W）最大将上式对W的各分量求偏导数并令其为零,可以确定一个W，从而得到使判据达最大的变换W⑤新特征集为其中X为原始特征集(d维),Y为新特征集(m维)TYWX注:W的计算（适用于J2—J5判据）：11212,,,,wbddSS设矩阵的特征值为按大小顺序排列为：则选前m个特征值对应的特征向量作为W，即：W=[u1，u2，……，um]此时21()miiJW2基于判别熵最小化的特征提取上节中讨论了用熵作为不确定性的一种度量的表达式，这里我们引入判别熵W（p，q）来表征两类分布p（xi）和q（xj）差别大小，令：iiiqpqpUqpW2)(),(),(对于特征提取来说，我们应该求得一组特征，它使上述判别熵最小。计算步骤如下①A=G1-G2,G1，G2分别是第一类样本集和第二类样本集的协方差矩阵Y为所要求的一组特征，它使得判别熵最小③新特征集为TYWX②将矩阵A的特征值进行排序222212dd选取前m个特征值对应的特征向量构成变换矩阵W=[U1，U2，……，Um]3两维显示人的经验和直观对分类有很大作用，如果能将各样本在特征空间的分布情况显示出来，我们可以直接观察哪些样本聚集在一起，因而可能属于一类。但人只能观察三维以下的空间，最好能把原来的高维特征空间映射到二维平面上显示出来，这一映射要尽可能的保持原来样本的分布情况，或者尽量使各样本间相互距离关系保持不变，上述所讨论的各种变换方法有利于我们解决这样一种两维显示的任务①线性映射两维显示只不过是前面所涉及的各种映射(线性)的一种特殊情况,即m=2②非线性映射对一些比较复杂的样本,线性映射常不能满足上面所提的保持分布不变的要求,可以用非线性映射替代y=f(x),f为某一非线性函数设映射前两点间距离为D，映射后该两点间距离为D*。希望映射后D*尽可能等于D。令e=D–D*为任意两点映射前后距离之差，我们要选择映射函数f使e的函数值达最小由于非线性映射比较复杂，一般情况下是用迭代算法。即选一个x的初值，再逐步调整（每次调整的方向应使误差减小），直到满足一个停止准则（例如，误差小于给定值，迭代次数超过预定次数，或显示结果已满足观察者要求为止4基于主成分变换的特征提取方法在实际问题中,研究多变量问题是经常遇到的,然而在多数情况下,不同指标之间是有一定相关性.由于指标较多,再加上指标之间有一定的相关性,势必增加了分析问题的复杂性.主成分分析就是设法将原来指标重新组合成一组新的相互无关的几个综合指标来代替原来指标,同时根据实际需要从中可取几个较少的综合指标尽可能多地反映原来指标的信息.这种将多个指标化为少数相互无关的综合指标的统计方法叫做主成分分析.这也是数学上处理降维的一种方法.如下例所示:某人要做一件上衣要测量很多尺寸,如身长、袖长等十几项指标,但某服装厂要生