模式识别-第10讲-特征的选择与提取2幻灯片.ppt

1、模式识别,授课教师 薛耀红 ,第10讲 特征的选择与提取(2),本节课主要内容,1 类别可分离性判据 2 特征提取 3 特征选择,3 特征选择,1 最优搜索算法 2 次优搜索法 3 可分性判据的递推计算 4.特征选择的几种新方法,特征选择的任务是从一组数量为D的特征中选择出 数量为d（Dd）的一组最优特征来.,利用穷举法总可以找出最优的特征集,但计算量太 大.从D个特征中选取d个,共 种组合。,如: 若D=20, d=10, 则从D个特征中选取d个特征的组合数q=184756, 对每一种组合需要计算判据值J(x),最优特征的选择，要解决两个问题:,选择的标准，这可以用类可分离性判据. 确定一个

2、较好的算法，以便找出最优的特征集.,本节主要讨论第二个问题，简单介绍几种优化算法.,1. 最优搜索算法,到目前为止唯一能获得最优结果的搜索方法是“分支定界”算法，它是一种“自上而下”的方法，但具有回溯功能，可使所有可能的特征组合都被考虑到。,由于合理的组织搜索过程，使得有可能避免计算某些特征组合而不影响结果为最优。,整个搜索过程可用树来表示,树的根结点表示原始特征集, 其他结点表示从其父结点所代表的特征子集中去掉某一特征后所得到的特征子集, 结点上的标号是去掉的特征的编号.,分支定界法的搜索树示意图(D=6，d=2),X,根结点:原始特征集,结点标号:去掉的特征,每一结点表示去掉若干特征后得到

3、的子集.,从左到右同一级结点对应的特征子集的类可分性判据值递增.,说明,分支定界法之所以有效, 这主要是利用了可分离性判据的单调性，即对有包含关系的特征组 Ak，k =1，2，I，即有：,可分性判据满足：,2. 次优搜索法,最优搜索法在有些情况下计算量太大而难以实现，这时不得不放弃最优解而采取计算量较小的次优搜索方法。下面我们介绍一些不同的算法，面对实际问题时可灵活选择。,（1）单独最优特征组合,最简单的方法是计算各特征单独使用时的判据值并加以排队，取前d个作为选择结果。但我们需要注意的是，即使各特征是统计独立的，这一结果也不一定就是最优结果。,只有当可分性判据J可写为如下两种形式时，这种方法

4、才能选出一组最优的特征来：,（2）顺序前进法（SFS）,这是最简单的“自下而上”的搜索方法。每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得判据J值为最大，直到特征数增加到d为止,（3）顺序后退法（SBS）,它与顺序前进法的思路刚好相反。这是一种“自上而下”的方法，从全体特征开始每次剔除一个，所剔除的特征应使仍然保留的特征组的判据J值最大，直到特征数减少到d为止。,和顺序前进法比较，该方法用两个特点：一是在计算过程中可以估计每去掉一个特征所造成可分性的降低；二是由于它的计算是在高维空间中进行的，所以计算量比较大。,比方说，在第k步可先用SFS法一个个加入特征到 k+l 个

5、，然后再用SBS法一个个剔去 r 个特征，我们把这样一种算法叫增 l 减 r 法（lr 法）,（4）增 l 减 r 法（lr 法）,这种方法是基于前两种算法的特点提出的.为了避免前面方法的一旦被选入(或剔除)就不能再剔除(或选入)的缺点可在选择过程中加入局部回溯过程。,3. 可分性判据的递推计算,所有上述搜索算法都有一个共同点，即第 k 步特征组是在第 k1 步特征组上加入或剔除某些特征来构成的，因此我们可以分析一下，是否有可能从 k1 步的判据值 J(k-1) 推算出 J(k),而不必完全重新计算.,事实上，对于有些情况，对于这些判据递推关系是存在的，即求J(k)时可在 J(k-1)的基础上

6、把新加入（或剔除）特征的影响加进去即可，不必从头算起，这样就大大简化了计算工作.,我们注意到在进行特征选择时需要以可分性判据来度量特征选择的好坏.特征选择是一个组合优化问题,因此可以使用解决优化问题的方法来解决特征选择问题.,优化问题是很多研究人员关注的一个热点问题，近年来出现了一些有特色的解决方法,如:,1) 模拟退火算法,2) 遗传算法,3) Tabu搜索算法,4. 特征选择的几种新方法,来源于统计力学。材料粒子从高温开始，非常缓慢地降温(退火)，粒子就可在每个温度下达到热平衡。假设材料在状态i的能量为 E(i)，那么材料在温度 T时从状态i进入状态j遵循如下规律,1) 模拟退火算法,如果

7、 E(j) E(i)，接受该状态被转换。 如果 E(j)E(i)，则状态转换以如下概率被接受：,1) 模拟退火算法,模拟退火优化法：f : xR+， 其中xS，表示优化问题的一个可行解。 N(x)S 表示x的一个邻域集合。,首先给定初始温度T0和初始解 x(0)，以概率P生成下一个新解x,1) 模拟退火算法,对于温度Ti和该优化问题的解x(k)，可以生成新解x 经过多次转换，降低温度得到 T i+1 Ti。在Ti+1下重复上述过程，最终的解是对该问题寻优的结果。,1) 模拟退火算法: 步骤,Step1: 令i=0, k=0, 给出初始温度T0和初始特征组合x(0)。 Step2: 在x(k)的

8、邻域N(x(k)中选择一个状态x，即新特征组合。计算其可分性判据J(x)，并按概率P接受x(k+1)=x。 Step3: 如果在Ti下还未达到平衡，则转到Step2。 Step4: 如果Ti已经足够低，则结束，当时的特征组合即为算法的结果。否则继续。 Step5: 根据温度下降方法计算新的温度Ti+1。转到Step2。,该算法受进化论启迪，根据“物竞天择，适者生存”这一规则演变.,2) 遗传算法,基因链码：使用遗传算法时要把问题的每个解编码成一个基因链码。比如要从D个特征中挑选d个,就用一个D位的0或1组成的字符串表示一种特征组合。1表示该特征被选中，每个基因链码代表一个解，称作一个“个体”，

9、其中的每一位看作一个“基因” 群体：若干个体的集合，也就是一些解的集合,交叉：选择群体中的两个个体，以这两个个体为双亲作基因链码的交叉，从而产生两个新的个体，作为后代。,2) 遗传算法,变异：对某个体，随机选取其中一位，将其翻转,适应度：对每个解，以给定的优化准则来评价其性能的优劣，作为其适应度，即函数fi的值，个体xi越好，fi 越大。新一代群体对环境的平均适应度比父代高,Step1: 令进化代数t=0。 Step2: 给出初始化群体P(t)，令xg为任一个体。 Step3: 对P(t)中每个个体估值，并将群体中最优解x 与xg比较，如果x的性能优于xg，则xg=x Step4: 如果终止条

10、件满足，则算法结束，xg为算法的 结果。否则继续。 Step5: 从P(t)中选择个体并进行交叉和变异操作，得 到新一代群体P(t+1)。令t=t+1,转到Step3。,2) 遗传算法：步骤,关于遗传算法的说明： 由步骤3保证了最终解是所搜索过的最优解 常用的终止条件是群体的世代数超过一个给定值，或连续数个世代都没有得到更优解 群体的大小和演化代数是值得重视的参数。在一定范围内，这两个参数大些能得到更好的解 对交叉的亲本选择可采用如下规则：个体的性能越好，被选中的可能性也越大,3) Tabu搜索算法,自学,本节课结束 谢谢大家！,经过有限次转换，在温度Ti下的平衡态xi的分布为,1) 模拟退火

11、算法,当温度T降为0时，xi的分布为,模式识别,授课教师 薛耀红 ,第9讲 特征的选择与提取(1),本节课主要内容,1 类别可分离性判据 2 特征提取 3 特征选择,特征提取与选择的基本任务是研究如何从众多特征中求出那些对分类识别最有效的特征，从而实现特征空间维数的压缩,即获取一组“少而精”且分类错误概率小的分类待征.,可以把特征分为三类 1 物理的；2 结构的：易于为人的直觉感知，但有时 难于定量描述，因而不易用于机器判别 3 数学的：易于用机器定量描述和判别，如基于统计 的特征,x1 x2 x3 . . xd,对 象,模式的特征的有效性直接影响分类器的设计和性能.由信息获取部分获得的原始数

12、据量一般是相当大的.为了有效地实现分类识别，要对原始数据进行选择或变换，得到最能反应分类本质的待征，构成特征向量.这就是特征抽取与选择的过程.,传感器,y1 y2 y3 . . ym,学习.训练,选择.提取,分类器,特征选择： 从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的，这个过程叫特征选择。,特征提取： 在原始特征的维数很高的情况下，通过映射（或变换）的方法用低维空间来表示样本，这个过程叫特征提取，映射后的特征称作二次特征。,特征形成： 根据被识别的对象产生出一组基本特征（也可称为原始特征），它可以是计算出来的，也可以是用仪表或传感器测量出来的,称作原始特征。,有时特征提取

13、和选择并不是截然分开的。例如，可以先将原始特征空间映射到维数较低的空间，在这个空间中再进行选择以进一步降低维数；也可以先经过选择去掉那些明显没有分类信息的特征，再进行映射以降低维数。,本讲讨论特征的选择与提取方法.,细胞自动识别： 原始测量：（正常与异常）细胞的数字图像 原始特征（特征的形成，找到一组代表细胞性质的特征）：细胞面积，胞核面积，形状系数，光密度，核内纹理，核浆比 压缩特征：原始特征的维数仍很高，需压缩以便于分类（2种方式） 1. 特征提取：用映射（或称变换）的方法把原始特征变换为较少的新特征 2. 特征选择：从原始特征中去挑选出一些最有代表性的特征,特征的选择与提取举例1,特征的

14、选择与提取举例2,特征提取和选择：对单个鱼的信息进行特征选择，从而通过测量某些特征来减少信息量 长度 亮度 宽度 鱼翅的数量和形状 嘴的位置，等等 分类决策：把特征送入决策分类器,特征的选择与提取举例,特征的选择与提取举例,特征的选择与提取举例,特征的选择与提取举例,1 类别可分离性判据,1.准则函数-判据 2.基于类间距离的可分性判据 3.基于概率分布的可分性判据 4.基于熵函数的可分性判据,1.准则函数,特征选择与提取的任务:求出一组对分类最有效的特征。 类别可分离性判据：衡量不同特征及其组合对分类是否有效的定量准则 理想准则：某组特征使分类器错误概率最小 常用类别可分离性判据：基于距离、

15、概率分布、熵函数,类别可分离性判据,我们可以依据某种准则进行特征提取和选择，为此，应当首先构造这样的准则类别可分离性判据。这些判据应能反映各类在特征空间中的分布情况，应能刻画各特征分量在分类识别中的重要性或贡献。 1 类别可分离性判据满足的要求 （1）与错误概率（或其的上下界）有单调关系； （2）当特征独立时有可加性,（3）具有“距离”的某些特性，即 （4）对特征数目是单调不减，即加入新的特征后，判据值不减。 这里指出，所构造的可分离性判据并不一定同时具有上述的四个性质，但这并不影响它在实际使用中的性质。 下面对几种常用的判据进行讨论。,2. 类内类间距离,各类样本可以分开是因为它们位于特征空

16、间的不同区 域，显然这些区域之间距离越大，类别可分性就越大。,如何表示两个类之间的距离?,2. 类内类间距离,点到点的距离,点到点集 的均方欧式距离,类内均值向量,样本总均值向量,各类均值向量,Pi 先验概率,2. 类内类间距离,类内均方欧式距离,类内离差矩阵,类内离差矩阵 SWi 的迹等于类内均方欧式距离,两类之间的均方距离,C 类特征向量之间的平均距离为：,2. 类内类间距离,(8-5),类内平均距离,类间距离,(8-6),(8-1),2. 类内类间距离,基于距离的准则概念直观，计算方便，但与错误率没有直接联系,样本类间离散度矩阵,样本类内离散度矩阵,类间可分离性判据,1) 基于类内类间距

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

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

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

20、大熵函数值越大,4.基于熵函数的可分性判据,2) Shannon熵,4.基于熵函数的可分性判据,3) 平方熵,为了对所提取的特征进行评价，我们要计算空间每一点的熵函数. 在熵函数取值较大的那一部分空间，不同类的样本必然在较大的程度上互相重叠.,4.基于熵函数的可分性判据,2 特征提取,1 按欧氏距离度量的特征提取方法 2 基于判别熵最小化的特征提取 3 两维显示,确定变换的依据:类别可分性判据,目标: 在新的特征空间中, 各类之间容易区分.,2 特征提取,根据前面提到的类别可分离性判据。我们可以依据这些判据进行特征的提取。 设原特征向量 ，对 作线性变换，产生 d 维向量 ， ，即 矩阵 称为

21、特征提取矩阵或变换矩阵， 称为二次特征。, s阶Minkowski度量,多维空间中两个向量之间有多种距离度量,1. 按欧氏距离度量的特征提取方法, Chebychev距离: 棋盘距离,在实际应用中，在计算的复杂性方面，在是否便于进行解析分析以及用它进行特征提取的效果方面都各不相同。由于欧氏距离在很多情况下便于分析和计算.,同样的，我们还可以提出下面各种判据：,以J2为例, 特征提取的步骤如下, 作线性映射：,其中Y为D维原始特征向量；X为d维压缩后的特征向量, 令,其中Sw，Sb为原空间（即Y的）离散度矩阵，S*w，S*b 为映射后（即X的）离散度矩阵。, J2的表达式为：, 求变换矩阵W,

22、使 J2（W）最大,将上式对W的各分量求偏导数并令其为零,可以确定一个W，从而得到使判据达最大的变换W,注: W的计算（适用于J2J5判据）：,则选前d 个特征值对应的特征向量作为W，即： W=u1, u2, , ud ,此时,2. 基于判别熵最小化的特征提取,上节中讨论了用熵作为不确定性的一种度量的表达式，这里我们引入判别熵 W(p, q) 来表征两类分布 p(xi) 和 q(xj) 差别大小, 令：,对于特征提取来说，我们应该求得一组特征，它使上述判别熵最小。,计算步骤如下:, A=G1-G2, G1，G2分别是第一类样本集和第二类样本集的协方差矩阵,3. 两维显示,人的经验和直观对分类有

23、很大作用，如果能将各样本在特征空间的分布情况显示出来，我们可以直接观察哪些样本聚集在一起，因而可能属于一类。 最好能把原来的高维特征空间映射到二维平面上显示出来，这一映射要尽可能的保持原来样本的分布情况，或者尽量使各样本间相互距离关系保持不变. 上述所讨论的各种变换方法有利于我们解决这样一种两维显示的任务.,设映射前两点间距离为D，映射后该两点间距离为D* . 希望映射后D*尽可能等于D. 令 e =DD*为任意两点映射前后距离之差，我们要选择映射函数 f使e的函数值达最小.,由于非线性映射比较复杂，一般情况下是用迭代算法。即选一个x的初值，再逐步调整（每次调整的方向应使误差减小），直到满足一

24、个停止准则（例如，误差小于给定值，迭代次数超过预定次数，或显示结果已满足观察者要求为止).,本节课结束 谢谢大家！,1 设有两类三维样本，都服从正态分布，且样本均值和协方差矩阵分别为：,1). 计算其类可分性散度判据JD的值,2 设样本均值为（1，2），样本的协方差矩阵和相关矩阵分别为：,计算分别用和R计算得到的主成分，并说明其差异。,4. 基于主成分变换的特征提取方法,在实际问题中, 研究多变量问题是经常遇到的，然而在多数情况下, 不同指标之间是有一定相关性。由于指标较多, 再加上指标之间有一定的相关性，势必增加了分析问题的复杂性. 主成分分析就是设法将原来指标重新组合成一组新的相互无关的几

25、个综合指标来代替原来指标, 同时根据实际需要从中可取几个较少的综合指标尽可能多地反映原来指标的信息。 这种将多个指标化为少数相互无关的综合指标的统计方法叫做主成分分析（Principal Component Analysis).,某人要做一件上衣要测量很多尺寸,如身长、袖长等十几项指标,但某服装厂要生产一批新型服装绝不可能把尺寸的型号分得过多,而是从多种指标中综合成几个少数的综合指标,作为分类的型号,如下图:,4 基于主成分变换的特征提取方法,4 基于主成分变换的特征提取方法,主成分分析的基本方法是通过构造原变量的适当的线性组合, 以产生一系列互不相关的新信息, 从中选出少数几个新变量并使它们

26、含有尽可能多的原变量带有的信息, 从而使得用这几个新变量代替原变量分析问题和解决问题成为可能. 当研究的问题确定之后,变量中所含“信息”的大小通常用该变量的方差或样本方差来度量.,如图, 设二维样本集呈现扁椭圆分布.,x1,x2,u,将二维样本Xi向长轴方向投影,可得到一维样本Yi,设u为长轴方向的单位向量,则有,Xi,Yi,一般如何求“最好”的方向 u,？,4 基于主成分变换的特征提取方法,（1）数学模型,设 X1,X2,Xp 为某实际问题所涉及的p个随机变量.记 X=(X1, X2, , Xp )T, 其协方差矩阵为,设li=(l1i, l2i, , lpi)T (i=1,2,p)为p个常

27、数向量, 考虑如下线性组合:,我们希望用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 的第二主成分.,一般,在约束条件 及

28、 (k=1,2,i-1)之下,求li 使Var(Yi)达到最大,由此 li 所确定的随机变量 Yi=liTX 称为 X1,X2,Xp 的第i个主成分.,并且有:,定理1 设是X=(X1,X2,Xp)T的协方差矩阵, 的特征值及其相应的正交单位特征向量分别为 及 e1,e2,ep, 则X的第i个主成分为,下面进一步讨论 X1, X2, , Xp 的方差与各主成分的方差之间的关系,以确定各主成分所包含的信息占总信息的份额. 易证下面结果:,定理2 设Yi = eiTX (i=1,2,p) 为X的p各主成分, 则:,当 时， 达到最大值,定义 第k个主成分Yk的贡献率为: 前m个主成分Y1,Y2,Y

29、m的累计贡献率为:,在实际应用中, 通常选取mp,使前m个累计贡献率达到一定的比例(80%90%). 这样用前m 个主成分代替原来的变量X1,X2,Xp而不至于损失太多的信息, 从而到达减少变量个数的目的.,在实际问题中,一般(或)是未知的, 需要通过样本来估计.设,其中,（2）主成分的计算方法,分别以S和R作为和的估计,按前面所述的方法求得的主成分称为样本主成分.具体有如下结论:,其中x=(x1,x2,xp)T为X的任一观测值.当依次代入X的n个观测值 xk=(x1k,x2k,xpk)T 时,便得到第i个样本主成分yi 的n个观测值yik (k=1,2,n).,设 S=(sij)pp 是样本

30、协方差矩阵,其特征值为 , 相应的正交单位化特征向量为 ,则第i个样本主成分为:,这时,第i个样本主成分的贡献率为: 前m个样本主成分的累计贡献率为:,为了消除量纲的影响,我们可以对样本进行标准化,即令,则标准化数据的样本协方差矩阵即为原数据的样本相关矩阵R.,由R出发所求得的样本主成分称为标准化样本主成分.,只要求出R的特征值及相应的正交单位化特征向量,类似上述结果可求得标准化样本主成分.这时标准化样本的样本总方差为p.,3） 主成分解释,从代数观点看主成分就是p个变量X1,X2,Xp的一些特殊的线性组合.,在几何上这些线性组合正是把X1,X2,Xp构成的坐标系旋转产生新坐标系,新坐标系轴使

31、之通过样本变差最大的方向(或说具有最大的样本方差).,以最简单的二元正态变量来说明主成分的几何意义.,设有n个样本,每个样本有p个变量记为X1,X2,Xp,它们的综合变量记为Y1,Y2,Yp.当 p=2 时,原变量是X1, X2,设X=(X1,X2)N2(, ),它们有下图的相关关系:,对于二元正态分布变量, n个点的散布大致为一个椭圆,若在椭圆长轴方向取坐标轴Y1, 在短轴方向取Y2, 这相当于在平面上作一个坐标变换, 即:,可以看到Y1、Y2是原变量X1和X2的线性组合, 用矩阵表示为,显然UT=U-1且是正交矩阵.,如果上图的椭圆是相当扁平的,可以只考虑长轴Y1方向上的波动, 忽略Y2方向的波动. 这样, 二维可以降为一维.,一般情况, p个变量组成p维空间,n个样本就是p维空间的n个点, 对p元正态分布变量来说, 找主成分的问题就是找p维空间中椭圆体的主轴问题.,（4）举例,例一,设模式 X=(X1, X2, X3)T 的协方差矩阵为,求X的各主成分.,解: 易求得的特征值及其相应的正交化特征向量 分别为,因此X的主成分为,取第一主成分,则贡献率为,若取前两个主成分,则累计贡献率为,因此,可用前两个主成分代替原来三个变量.,%Example