特征提取与选择

1、第五章 特征的选择与提取,1 类别可分离性判据 2 特征提取 3 特征选择,特征提取与选择的基本任务是研究如何从众多特征中求出那些对分类识别最有效的特征，从而实现特征空间维数的压缩,即获取一组“少而精”且分类错误概率小的分类待征.,可以把特征分为三类 1 物理的；2 结构的；3 数学的。,分类器,x1 x2 x3 . . xd,对 象,选择.提取,模式的特征的有效性直接影响分类器的设计和性能.由信息获取部分获得的原始数据量一般是相当大的.为了有效地实现分类识别，要对原始数据进行选择或变换，得到最能反应分类本质的待征，构成特征向量.这就是特征抽取与选择的过程.,传感器,y1 y2 y3 . .

2、ym,学习.训练,在一个较完善的模式识别系统中，明显或隐含的要有特征提取与选择技术环节，其通常处于对象特征数据采集和分类识别两个环节之间.,基本概念,特征选择： 从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的，这个过程叫特征选择。,特征提取： 将一组高维特征，通过变换的方法得到一组新的低维特征，这个过程叫特征提取。,特征形成： 根据被识别的对象产生出一组基本特征（也可称为原始特征），它可以是计算出来的，也可以是用仪表或传感器测量出来的。,特征提取：,模式空间,特征空间,特征选择：,特征集,特征子集,说明： 有时特征提取和选择并不是截然分开的。例如，可以先将原始特征空间映射到维数

3、较低的空间，在这个空间中再进行选择以进一步降低维数；也可以先经过选择去掉那些明显没有分类信息的特征，再进行映射以降低维数。,即在模式识别中，特征提取与特征选择作为两个过程，它们的先后次序并不是固定不变的。在处理实际问题时，可以根据具体情况决定先进行哪一个过程。,本章讨论特征的选择与提取方法.,1类别可分离性判据,1.准则函数-判据 2.基于类间距离的可分性判据 3.基于概率分布的可分性判据 4.基于熵函数的可分性判据,1.准则函数,特征选择与提取的任务是求出一组对分类最有效的特征，因此我们需要一个定量的准则（或称判据）来衡量特征对分类的有效性。,由于直接用错误概率作为标准来分析特征的有效性比较

4、困难我们希望找出另外一些更实用的准则来衡量备类间的可分性，并希望可分性准则满足下列几条要求,1) 与错误概率（或它的上下界）有单调关系 2) 当特征独立时有可加性 3) 度量特性（非负性，互反性） 4) 单调性，即加入新的特征时，判据不减小,2.类内类间距离,各类样本可以分开是因为它们位于特征空间的不同区 域，显然这些区域之间距离越大，类别可分性就越大。,基本思想： 考虑最简单的两类情况，1和2，1中任一点与2中的每一点都有一个距离，把所有这些距离相加求平均，可用这个均值来代表这两类之间的距离,多类情况是基于它的推导。,如何表示两个类区之间的距离?,我们定义各类特征向量之间的平均距离为：,代入

5、化简可得,说明,基于类内类间距离的可分离性判据是一种常用的判据，它 实际上是各类向量之间的平均距离。 2) 具体而言，即J（x）表示各类特征向量之间的平均距离，我们通常认为J（x）越大，可分离性越好。 3) 这种判据优点是计算简单；缺点是当类间距离较小，类内距离较大时，判据仍有可能取得较大的值，而此时的可分离性并不大。,3.基于概率分布的可分性判据,上面介绍的距离准则是直接从各类样本间的距离算出的,没有考虑各类的概率分布,不能确切表明各类交叠的情况，因此与错误概率没有直接联系,下面提出一些基于概率分布的可分性判据.,两个分布密度函数之间的距离,任何函数J，如果满足下述条件，都可用来作为类分 离

6、性的概率距离度量。,1) J具有非负性 2 ) 当两类完全不交叠时，J取最大值 3 ) 当两类分布密度相同时，J应为0,如图所示，图1表示两类为完全可分的情况，而图2则表示两类完全不可分的。,(1) Bhattacharyya距离,注： s是在0，1区间取值的一个参数，当s=0.5时，上述二者相等,(2) Chernoff距离,定义散度等于各类平均可分信息之和：,(3) 散度,1类对2类的平均可分性信息为,4.基于熵函数的可分性判据,最佳分类器由后验概率确定，所以可由特征的后验概率分布来衡量它对分类的有效性。,两种特殊情形下最佳分类器的错误率:,错误率,可见后验概率越集中,错误概率就越小.后验

7、概率分布越平缓(接近均匀分布)，则分类错误概率就越大.,设为可能取值为i, ( i=1,2,c )的一个随机变量,它的取值 依赖于分布密度为p(x)的随机向量x(特征向量)，即给定x后的概率为p( / x).,为了衡量后验概率分布的集中程度，需要规定一个定量准则.我们可以借助于信息论中关于熵的概念.,我们想知道的是：给定某一x后，我们从观察得到的结果中得到了多少信息?或者说的不确定性减少了多少?,从特征提取的角度看，显然用具有最小不确定性的那些特征进行分类是有利的。在信息论中用“熵”作为不确定性的度量.,重叠程度越大熵函数值越大,2) Shannon熵,3) 平方熵,为了对所提取的特征进行评价

8、，我们要计算空间每一点的熵函数.在熵函数取值较大的那一部分空间，不同类的样本必然在较大的程度上互相重叠.,2 特征提取,1 按欧氏距离度量的特征提取方法 2 基于判别熵最小化的特征提取 3 两维显示 4 基于主成分变换的特征提取方法,特征提取,d m,确定变换的依据:类别可分性判据,目标: 在新的特征空间中,各类之间容易区分., s阶Minkowski度量,多维空间中两个向量之间有多种距离度量，下面是一些最重要的例子：,1 按欧氏距离度量的特征提取方法, Chebychev距离: 棋盘距离,所有上面x的下标的意义如下：当只有一个下标时，此下标表示样本号；有两个下标时，第一个为样本号，第二个表示

9、该样本的特征序号。,以上的各种距离度量在实际应用中，在计算的复杂性方面，在是否便于进行解析分析以及用它进行特征提取的效果方面都各不相同。由于欧氏距离在很多情况下便于分析和计算.,同样的，我们还可以提出下面各种判据：,以J2为例, 特征提取的步骤如下, 作线性映射：,其中X为d维原始特征向量；Y为m维压缩后的特征向量, 令,其中Sw，Sb为原空间（即X的）离散度矩阵，S*w， S*b为映射后（即Y的）离散度矩阵, J2的表达式为：, 求变换矩阵W, 使 J2（W）最大,将上式对W的各分量求偏导数并令其为零,可以确定一个W，从而得到使判据达最大的变换W,注: W的计算（适用于J2J5判据）：,则选

10、前m个特征值对应的特征向量作为W，即： W=u1，u2，um,此时,2 基于判别熵最小化的特征提取,上节中讨论了用熵作为不确定性的一种度量的表达式，这里我们引入判别熵W（p，q）来表征两类分布p（xi）和q（xj）差别大小，令：,对于特征提取来说，我们应该求得一组特征，它使上述判别熵最小。,计算步骤如下, A=G1-G2, G1，G2分别是第一类样本集和第二类样本集的协方差矩阵,3 两维显示,人的经验和直观对分类有很大作用，如果能将各样本在特征空间的分布情况显示出来，我们可以直接观察哪些样本聚集在一起，因而可能属于一类。但人只能观察三维以下的空间，最好能把原来的高维特征空间映射到二维平面上显示

11、出来，这一映射要尽可能的保持原来样本的分布情况，或者尽量使各样本间相互距离关系保持不变，上述所讨论的各种变换方法有利于我们解决这样一种两维显示的任务,设映射前两点间距离为D，映射后该两点间距离为D*。希望映射后D*尽可能等于D。令e=DD*为任意两点映射前后距离之差，我们要选择映射函数f使e的函数值达最小,由于非线性映射比较复杂，一般情况下是用迭代算法。即选一个x的初值，再逐步调整（每次调整的方向应使误差减小），直到满足一个停止准则（例如，误差小于给定值，迭代次数超过预定次数，或显示结果已满足观察者要求为止,4 基于主成分变换的特征提取方法,在实际问题中,研究多变量问题是经常遇到的,然而在多数

12、情况下,不同指标之间是有一定相关性.由于指标较多,再加上指标之间有一定的相关性,势必增加了分析问题的复杂性.主成分分析就是设法将原来指标重新组合成一组新的相互无关的几个综合指标来代替原来指标,同时根据实际需要从中可取几个较少的综合指标尽可能多地反映原来指标的信息.这种将多个指标化为少数相互无关的综合指标的统计方法叫做主成分分析.,这也是数学上处理降维的一种方法.如下例所示:,某人要做一件上衣要测量很多尺寸,如身长、袖长等十几项指标,但某服装厂要生产一批新型服装绝不可能把尺寸的型号分得过多,而是从多种指标中综合成几个少数的综合指标,作为分类的型号,如下图:,主成分分析的基本方法是通过构造原变量的

13、适当的线性组合,以产生一系列互不相关的新信息,从中选出少数几个新变量并使它们含有尽可能多的原变量带有的信息,从而使得用这几个新变量代替原变量分析问题和解决问题成为可能.当研究的问题确定之后,变量中所含“信息”的大小通常用该变量的方差或样本方差来度量.,如图, 设二维样本集呈现扁椭圆分布.,x1,x2,u,将二维样本Xi向长轴方向投影,可得到一维样本Yi,设u为长轴方向的单位向量,则有,Xi,Yi,一般如何求“最好”的方向 u,？,1）数学模型,设X1,X2,Xp为某实际问题所涉及的p个随机变量.记X=(X1,X2,Xp)T,其协方差矩阵为,设li=(l1i,l2i,lpi)T(i=1,2,p)

14、为p个常数向量,考虑如下线性组合:,易知有:,我们希望用Y1代替原来p个变量,这就要求Y1尽可能的反映原p个变量的信息,即Var(Y1)越大.为此,我们对li做如下限制,否则Var(Y1)无界,即:,因此,我们希望在约束条件l1Tl1=1之下,求l1使达到最大,由此l1所确定的随机变量Y1=l1TX称为X1,X2,Xp的第一主成分.,如果第一主成分Y1还不足以反映原变量的信息,考虑采用Y2.但要求Y1与Y2不相关,即,于是,在约束条件 及 之下,求l2 使Var(Y2)达到最大,由此l2所确定的随机变量Y2=l2TX称为X1,X2,Xp的第二主成分.,一般,在约束条件 及 (k=1,2,i-1

15、)之下,求li 使Var(Yi)达到最大,由此li所确定的随机变量Yi=liTX称为X1,X2,Xp的第i个主成分.,利用微积分知识的知识,可得如下结论.,并且有:,定理1 设是X=(X1,X2,Xp)T的协方差矩阵, 的特征值及其相应的正交单位特征向量分别为 及e1,e2,ep,则X的第i个主成分为,由此定理可知,求X的各主成分,等价于求的各个特征值及其相应的正交单位化特征向量,按特征值由大到小所对应的特征向量为组合系数的X1,X2,Xp的线性组合分别为X的第一、第二、甚至第p个主成分,而各主成分的方差等于相应的特征值.,下面进一步讨论X1,X2,Xp的方差与各主成分的方差之间的关系,以确定

16、各主成分所包含的信息占中总信息的份额.易证下面结果:,定理2设Yi=eiTX(i=1,2,p)为X的p各主成分,则:,由定理2,我们特给出如下定义:,定义 第k个主成分Yk的贡献率为: 前m个主成分Y1,Y2,Ym的累计贡献率为:,在实际应用中,通常选取md）的一组最优特征来.,利用穷举法总可以找出最优的特征集,但计算量太大.从D个特征中选取d个,共CdD种组合。若不限定特征选择个数，则共2D种组合 典型的组合优化问题,如: 若D=20, d=10, 则从D个特征中选取d个特征的组合数q=184756, 对每一种组合需要计算判据值J(x),最优特征的选择，要解决两个问题:,选择的标准，这可以用

17、类可分离性判据. 确定一个较好的算法，以便找出最优的特征集.,本节主要讨论第二个问题，简单介绍几种优化算法.,特征选择的方法大体可分两大类： Filter方法：根据独立于分类器的指标J来评价所选择的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。不考虑所使用的学习算法。 Wrapper方法：将特征选择和分类器结合在一起，在学习过程中表现优异的的特征子集会被选中,1. 最优搜索算法,到目前为止唯一能获得最优结果的搜索方法是“分支定界”算法，它是一种“自上而下”的方法，但具有回溯功能，可使所有可能的特征组合都被考虑到。,由于合理的组织搜索过程，使得有可能避免计算某

18、些特征组合而不影响结果为最优。,整个搜索过程可用树来表示,树的根结点表示原始特征集, 其他结点表示从其父结点所代表的特征子集中去掉某一特征后所得到的特征子集, 结点上的标号是去掉的特征的编号.,分支定界法的搜索树示意图(D=6，d=2),X,根结点:原始特征集,结点标号:去掉的特征,每一结点表示去掉若干特征后得到的子集.,从左到右同一级结点对应的特征子集的类可分性判据值递增.,说明,分支定界法之所以有效,这主要是利用了可分离性判据的单调性，即对有包含关系的特征组Ak，k=1，2，I，即有：,可分性判据满足：,2 . 次优搜索法,最优搜索法在有些情况下计算量太大而难以实现，这时不得不放弃最优解而

19、采取计算量较小的次优搜索方法。下面我们介绍一些不同的算法，面对实际问题时可灵活选择。,（1）单独最优特征组合,最简单的方法是计算各特征单独使用时的判据值并加以排队，取前d 个作为选择结果。但我们需要注意的是，即使各特征是统计独立的，这一结果也不一定就是最优结果。,只有当可分性判据J可写为如下两种形式时，这种方法才能选出一组最优的特征来：,（2）顺序前进法（SFS）,这是最简单的“自下而上”的搜索方法。每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得判据J值为最大，直到特征数增加到d 为止,（3）顺序后退法（SBS）,它与顺序前进法的思路刚好相反。这是一种“自上而下”的方法

20、，从全体特征开始每次剔除一个，所剔除的特征应使仍然保留的特征组的判据J值最大，直到特征数减少到d 为止,和顺序前进法比较，该方法用两个特点：一是在计算过程中可以估计每去掉一个特征所造成可分性的降低；二是由于它的计算是在高维空间中进行的，所以计算量比较大,比方说，在第k步可先用SFS法一个个加入特征到 k+l 个，然后再用SBS法一个个剔去 r 个特征，我们把这样一种算法叫增 l 减 r 法（lr 法）,（4）增 l 减 r 法（lr 法）,这种方法是基于前两种算法的特点提出的.为了避免前面方法的一旦被选入(或剔除)就不能再剔除(或选入)的缺点可在选择过程中加入局部回溯过程。,3. 可分性判据的

21、递推计算,所有上述搜索算法都有一个共同点，即第 k 步特征组是在第 k1 步特征组上加入或剔除某些特征来构成的，因此我们可以分析一下，是否有可能从 k1 步的判据值J（ k1）推算出J（ k ），而不必完全重新计算,事实上，对于这些判据递推关系是存在的，即求J（k）时可在J（k1）的基础上把新加入（或剔除）特征的影响加进去即可，不必从头算起，这样就大大简化了计算工作,我们注意到在进行特征选择时需要以可分性判据来度量特征选择的好坏.特征选择是一个组合优化问题,因此可以使用解决优化问题的方法来解决特征选择问题.,优化问题是很多研究人员关注的一个热点问题，近年来出现了一些有特色的解决方法,如:,1)

22、 模拟退火算法,2) 遗传算法,3) Tabu搜索算法,来源于统计力学。材料粒子从高温开始，非常缓慢地降温(退火)，粒子就可在每个温度下达到热平衡。假设材料在状态i的能量为E(i)，那么材料在温度T时从状态i进入状态j遵循如下规律,1) 模拟退火算法,如果E(j) E(i)，接受该状态被转换。 如果E(j)E(i)，则状态转换以如下概率被接受：,在某一温度下，进行了充分转换后，材料达到热平衡，这时材料处于状态i的概率满足,1) 模拟退火算法,所有状态在高温下具有相同概率,当温度降至很低时，材料会以很大概率进入最小能量状态,1) 模拟退火算法,模拟退火优化法：f: xR+， 其中xS，表示优化问

23、题的一个可行解。 N(x)S表示x的一个邻域集合。,首先给定初始温度T0和初始解x(0)，以概率P生成下一个新解x,1) 模拟退火算法,对于温度Ti和该优化问题的解x(k)，可以生成新解x 经过多次转换，降低温度得到T i+1Ti。在T i+1下重复上述过程，最终的解是对该问题寻优的结果,经过有限次转换，在温度Ti下的平衡态xi的分布为,1) 模拟退火算法,当温度T降为0时，xi的分布为,1) 模拟退火算法: 步骤,Step1: 令i=0, k=0, 给出初始温度T0和初始特征组合x(0)。 Step2: 在x(k)的邻域N(x(k)中选择一个状态x，即新特征组合。计算其可分性判据J(x)，并按概率P接受x(k+1)=x。 Step3: 如果在Ti下还未达到平衡，则转到Step2。 Step4: 如果Ti已经足够低，则结束，当时的特征组合即为算法的结果。否则继续。 Step5: 根据温度下降方法计算新的温度Ti+1。转到Step2。,该算法受进化论启迪，根据“物竞天择，适者生存”这一