北京大学：《模式识别》课程教学资源（课件讲稿）特征的选择和提取（第二部分）.pdf_大学文库

7 7.4.1 常用的概率距离度量  散度 (Divergence)  定义区分ωi 类和ωj 类的总的平均信息（散度）： ( | ) [ ( | ) ( | )]ln ; ( | ) i D ij ji i j X j p J II p p d p         x xx x x    1 2 1 2 1 12 12 1 12 21 1 0; 2 0 ( | ) ( | ), ; 3 ( , , , ) ( ); 4 ( , , ) ( , , , ); 5 , ,. D D n D n Di i D k D kk D D J Jpp J xx x J x J xx x J xx xx J J               x xx x x    ）））当的各分量彼此独立时，）当的各分量彼此独立时，） 8 7.4.1 常用的概率距离度量  正态分布下的散度  设两类别都是 d 维正态分布，分别表示为 ωi ~N(μi ，∑i ) ，ωj ~N(μj ，∑j )，则 1 /2 1/2 1 /2 1/2 1 1 ( | ) exp[ ( ) ( )], (2 ) | | 2 1 1 ( | ) exp[ ( ) ( )]; (2 ) | | 2 T i ii i d i T j jj j d j p p             x x μ Σ x μ Σ x x μ Σ x μ Σ 11 1 1 1 ln | | ( ) ( ) ( ) ( ); 22 2 j T T ij i i i j j j i l          Σ x μ Σ x μ x μ Σ x μ Σ 对数似然比 9 7.4.1 常用的概率距离度量  正态分布下的散度  利用矩阵迹的性质 tr(BAT)=tr(ATB ) (=ATB ，如 A，B是向量) ，似然比可改写成 1 1 1 1 ln | | [ ( )( ) ] 2 2 1 [ ( )( ) ]; 2 j T ij i i i i T jjj l tr tr        Σ Σ x μ x μ Σ Σ x μ x μ 1 1 1 1 1 ln | | [ ( )] 2 2 1 [ ( )( ) ]; 2 j ij i j i i T ji ji j I tr tr         Σ ΣΣ Σ Σ Σμ μμ μ 10 7.4.1 常用的概率距离度量  正态分布下的散度  如果两类协方差矩阵相等，则 1 1 1 1 1 [ 2] 2 1 ( ) ( )( ); 2 D i j ji T i j i j i j J tr          ΣΣ ΣΣ I μμ Σ Σ μμ 1 ( )( ) ; T D ij ij M J J     μ μ Σμ μ Mahalanobis 距离的平方在协方差矩阵相等条件下散度与 Jd 很相似，都是对样本在特征空间分散程度的描述。 11 7.4.1 常用的概率距离度量  正态分布下的 Bhattacharyya 距离  如果两类协方差矩阵相等，则 1 1/2 1 () () 8 2 1 |( )/2| ln ; 2 | || | T i j B i j i j i j i j J                 Σ Σ μμ μ μ Σ Σ Σ Σ 1 8( )( ) . T B ij ij DM J J J     μ μ Σμ μ 12 7.4.2 概率距离判据下的特征提取  基本方法：类似于距离度量下的特征提取  设求映射后的判据表达式（JB, JC, JD）对 A 的各分量的偏导数并令其为零，得到所需的方程式组，然后用相应方法求解。  注意：原空间中一个矩阵 W 经映射后变为 , T y Ax  .  T W A WA 

13 7.4.2 概率距离判据下的特征提取  讨论：两类别问题，正态分布及相同的协方差阵   1 12 12 1 1 21 2 1 1 21 2 ( )( ) ( )( ) ( )( ) T D T T J tr tr                   μ μ Σμ μ Σμ μμ μ Σ M M 其中，； μμμμ             1 1 1 1 1 ( ) ( ) 2 0; 2 0 D T TT T T T D T T J tr J                    A A ΣA A MA A ΣA A Σ M A A MA A A ΣA ΣA MA A ΣA A A ΣA A MA （具有非奇异变换不变性） 14 7.4.2 概率距离判据下的特征提取  讨论：两类别问题，正态分布及相同的协方差阵  设矩阵 (ATΣA)-1ATMA 的特征值矩阵与特征向量矩阵分别是 Λ 和 U，即有    1 ; T T  A ΣA A MA U U Λ ; =  -1 -1 Σ MAU - AUΛ = 0 令，则是的特征向量矩阵； B AU B Σ M   1 21 2 1 2 1 ( )( ) . ( ) T rank         -1 -1 -1 -1 Σ M Σ MA = A Σμ μ μ μ A A A Σ μ μ 对于两类别问题，即，， 15 7.5 基于熵函数的可分性判决  熵：事件不确定性的度量  A 事件的不确定性大（熵大），则对 A 事件的观察所提供的信息量大。  思路：  把各类ωi 看作一系列事件，把后验概率P(ωi | x) 看作特征 x 上出现ωi 的概率；  如从 x 能确定ωi ，则对ωi 的观察不提供信息量，熵为0  特征 x 有利于分类；  如从 x 完全不能确定ωi ，则对ωi 的观察信息量大，熵大  特征 x 无助于分类。 16 7.5 基于熵函数的可分性判决  熵函数：   ( | ), , ( | ) ; 1 x x c P P c H  J    性质 17 7.5 基于熵函数的可分性判决  常用的熵函数：  Shannon 熵：  平方熵：  熵可分离性判据：  Je大，则不同类样本重叠性大，可分性不好；  Je小，则可分性好。 1 2 1 ( | )log ( | ); c ci i i HP P      x x 2 2 1 21 ( | ). c c i i H P            x ( ) ( ) ,  Je  H x p x dx 18 7.5.1 基于判别熵最小化的特征提取  相对熵：表示某一种分布偏离给定标准分布的程度，两种分布重合时最大（0），  判别熵：表示两类分布之间的差别 ( ) ( , ) ( )log 0; ( ) i i i p V pq p q    x x x (,) (,) (, ) ( )log ( ) ( )log ( ) ( )log ( ) ( )log ( ); i i ii ii i i W pq V pq Vqp p p qq pq qp           xx xx xx xx

19  为方便计算，判别熵可被代替  目标：  结论：使 U 最小的坐标系统（变换矩阵）是由矩阵 A = G(1)- G(2) 的前 d 个（按特征值平方大小）特征向量组成的，其中G(1)、G(2)是两类各自的协方差矩阵（估计）。 7.5.1 基于判别熵最小化的特征提取 2 ( , ) ( ) 0; i i i U pq p q     20 7.6 PCA 特征提取方法与K-L变换  PCA (Principle Component Analysis) 方法：进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。  通过变换，用较少的特征近似表示原来的对象 (m<<n)，并且使得误差尽可能的小。  K-L (Karhunen-Loeve) 变换：最优正交线性变换，相应的特征提取方法被称为 PCA 方法。 21 7.6 PCA 特征提取方法与K-L变换  正交变换  给定 n 维空间中的一组标准正交基它诱导了一个线性变换：  反之，任何一个正交变换也确定了一组正交基。 , , , , 1 2  n , 正交展开。 , 1,2, , , : ( ) ( , , , ) , 1 1 2        n i i i i T i T n y y i n L L y y y   x x x y x y   22 7.6 PCA 特征提取方法与K-L变换  误差  用 m 个分量表示带来的误差  目标：误差平方的期望最小 ( ) ; 1 1          n i m i i m i i i x m x y  y  2 2 2 1 () () , n i i m em E m E y               x  23 7.6 PCA 特征提取方法与K-L变换  求解最小均方误差正交基：  首先假定随机特征向量为零均值（期望）的，否则减掉均值即可  找 n 个正交基使得对任意一组正交基和所有的 m≤n， , , , , 1 2  n 1 2 ,,,,     n    2 2 2 2 1 1 () () ; n n T T i i im im em E em E                    x x Ex  0; 24 7.6 PCA 特征提取方法与K-L变换  求解最小均方误差正交基：  目标函数：对于一个固定的 m     2 1 1 2 min ( ) min min , . . 1, 1, 2, , ; n T T i i i m n T i i i m i em E st im m n                        xx Σ  Σ＝E(xxT)，x 的协方差矩阵

25 7.6 PCA 特征提取方法与K-L变换  求解最小均方误差正交基：  用 Lagrange 乘子法    1 1 () 1 ; n n T T i i i ii im im g                Σ   2 1 1 ( ) 0, 1, , , , 1, , ; () . T i i ii i i n n ii i im im g im n im n e m                        Σ Σ Σ   令是的特征向量，是特征根；且， 26 7.6 PCA 特征提取方法与K-L变换  协方差矩阵的所有特征根是实数，特征向量也是实的，所有 n 个特征向量构成一组标准正交基，记作分别对应特征根  选择协方差矩阵的特征向量作为正交基，可以使得均方误差最小。 1 2 ,,,, n     1 2 ,      n   , , , . 2 1 2 1 1 2                               T n T T n n             1 2 ,,, m     27 7.6 PCA 特征提取方法与K-L变换  总结  当取协方差矩阵Σ的 m 个最大特征值对应的特征向量来展开 x 时，此时的截断均方误差最小。这 m 个特征向量组成的正交坐标系称作 x 所在的 n 维空间的 m 维 Karhunen-Loeve (K-L) 变换坐标系，x 在 K-L 坐标系上的展开系数向量 y 称作 x 的 K-L 变换。  实际应用中，协方差矩阵是未知的，用样本协方差矩阵代替。 28 7.6 PCA 特征提取方法与K-L变换  特征向量常被叫做“主分量”，每个样本被它在前几个主分量上的投影近似表示  特征值标记着相应特征向量上的能量；  张成的空间称为原空间的子空间， PCA 实际上是在子空间上的投影，并且   ; 1 1 1          m i i i T m i i i n i i i x y  y  x   1 2 ,,, m     2 2 2 12 1 2 1 2 11 11 . n n mm ii ii ii ii ii ii yy yy      x x       29 7.6 PCA 特征提取方法与K-L变换  K-L 变换的性质  变换后空间中的各特征是互不相关的 K-L 坐标系把矩阵Σ对角化，即通过 K-L 变换消除原有向量 x 的各分量间的相关性，从而有可能去掉那些带有较少信息的分量以达到降低特征维数的目的。 , ; TT T i j i j i i j i ij T TT T E yy E E E                         x x y y ξ x x ξ ξ Σξ Λ 1 2 0 ; 0 d           Λ  30 7.6 PCA 特征提取方法与K-L变换  例子

7.6PCA特征提取方法与K-L变换 7.6PCA特征提取方法与KL变换口KL变换的产生矩阵口PCA的问题 ■数据集K={x}的KL变换的产生矩阵由数据的 ■由于用样本协方差矩阵代替协方差矩阵，主分量二阶统计量决定，即K-L坐标系的基向量为某种与训练数据有着很大关系，用一批训练数据得到基于数据x的二阶统计量的产生矩阵的特征向量。的主成分，可能不反映其另外一批数据的特征。 ■KL变换的产生矩阵可以有多种选择：口x的相关函数矩阵R=E[xx: 口x的协方差矩阵C=E[(x-u)(K-μ)门口样本总类内离散度矩阵： ,=会2，=E[-,-,].Go 7.6PCA特征提取方法与K-L变换 7.6PCA特征提取方法与KL变换口非监督的KL特征提取口K-L变换在人脸识别中的应用一Eigenface ■训练样本的类别未知，无法定义可分离性指标 ■简介，详细内容阅读教材ch9.9 。可用方差作衡量指标一选择或提取总体未知样本方差越大，越有利于分类人脸数据库 ■可用总体协方差矩阵作为KL产生矩阵： E-容m种m宫：口把特征值从大到小排序22≥…之。，选前m 个对应的特征向量组成特征提取器→在均方误差意义下，用m<n维对n维样本空间的最佳表示。 7.6PCA特征提取方法与K-L变换 7.6PCA特征提取方法与KL变换口KL变换在人脸识别中的应用一Eigenface 口K-L变换在人脸识别中的应用一Eigenface ,Tmk&Pentland1991年提出 ■把原图像表示成“特征脸的线性组合（即特征脸一本质上与CA.KIT变换没有区别空间中的点)； ,基本思想一任意输入图像可以表示为若干特任验”的线性组合 ■按照特征值从大到小排序，并从前向后取对应的线性组合的系数反映了该人脸的特性—被用作~人龄特证 “特征脸”，即构成对原图像的最佳的降维表示。 y=Wix:x=Wy X输入图像，y变换后的特征，W变换矩阵通过计算训练样本协方差矩阵的特征分解来得到 The oniginal face and the recovered face

7.6PCA特征提取方法与K-L变换 7.7特征选择口基于PCA的人脸识别方法口特征进择：从原始特征中挑选出一些最有代表性。读取每个人的前M幅图像，构造矩阵X: 分类性能最好的特征来进行分类： ■计算：Σ=x'X X=1-H,…,xw- ■计算：[，D]=mdX方口每个特征的状态是离散的：选或不选； ■计算：=XVD; 口从N个特征中选取k个，共C种组合；如不 ■按特征值从大到小排序，选择前几个最大的特征限定个数，则共有2种组合一典型的优化值对应的ξ作为变换矩阵W。组合问题。 ■把所有训练样本做变换y=Wx,保留系数y。 ■对新样本也作变换，看与哪个y最接近。 ■与实际比较确定是否识别正确，统计识别率。 7.7特征选择 7.7特征选择口特征选择的方法大体可分两大类：口一种Filter算法：FOCUS ■Fter方法：不考虑所使用的学习算法。通常给 ■该算法致力于寻找一个能正确区分所有类别的最出一个独立于分类器的指标J来评价所选择的特小特征集合；征子集S,然后在所有可能的特征子集中搜索出 ■例如：如区分每个人的特征包括姓名、性别、籍使得J最大的特征子集作为最优特征子集。贯、工作单位、身份证号.则该算法将选择： ■Wrapper方法：将特征选择和分类器结合在一身份证号. 起，即特征子集的好坏标准是由分类器决定的， ■搜索时会检测一个特征能否正确区分样本；如不在学习过程中表现优异的的特征子集会被选中。能，则考察两个特征.…以此类推。 2 7.7特征选择 7.7特征选择口一种Wrapper算法：OBLIVION 口许多特征选择算法力求解决搜索问题，经典搜索 ■该方法与最近邻法结合，根据特征子集的分类表算法有：现来选择特征； ■分支定界法：最优搜索，效率比盲目穷举法高； ■用顺序后退法搜索特征子集： ■单独最优特征组合法：次优搜索；从全体特征开始，每次剔除一个特征，使得所保 ■顺序前进法留的特征集合有最大的分类识别率（基于最近邻 ■顺序后退法法)。依次迭代，直至识别率开始下降为止。 ■模拟退火法合数CD- ■用leave-one-out方法估计平均识别率：用M-l个 D-10.2.C=40 ■Tabu搜索法 D-100,kC=16100 穷举假常最优样本判断余下一个的类别，N次取平均。 D-10a-10C-1.731o5 非穷华摆索—次线 ■遗传算法 D-t00,4-5aC-1.00891r29 搜索方向从底肉上X。=中 D-1000d1C=499500 D-10900.d4.C=49995e01 从镇向下=X

37 7.6 PCA 特征提取方法与K-L变换  基于 PCA 的人脸识别方法  读取每个人的前 M 幅图像，构造矩阵 X；  计算：  计算：  计算：  按特征值从大到小排序，选择前几个最大的特征值对应的ξi 作为变换矩阵 W。  把所有训练样本做变换 y=WTx，保留系数 y。  对新样本也作变换，看与哪个 y 最接近。  与实际比较确定是否识别正确，统计识别率。 ; T Σ  X X   V, D X  svd( ); 1 2 ;  ξ  XVD [ , , ]; X  x1 μ  xM  μ 38 7.7 特征选择  特征选择：从原始特征中挑选出一些最有代表性、分类性能最好的特征来进行分类；  每个特征的状态是离散的：选或不选；  从 N 个特征中选取 k 个，共种组合；如不限定个数，则共有 2N 种组合 —— 典型的优化组合问题。 k CN 39 7.7 特征选择  特征选择的方法大体可分两大类：  Filter 方法：不考虑所使用的学习算法。通常给出一个独立于分类器的指标 J 来评价所选择的特征子集 S，然后在所有可能的特征子集中搜索出使得 J 最大的特征子集作为最优特征子集。  Wrapper 方法：将特征选择和分类器结合在一起，即特征子集的好坏标准是由分类器决定的，在学习过程中表现优异的的特征子集会被选中。 40 7.7 特征选择  一种 Filter 算法：FOCUS  该算法致力于寻找一个能正确区分所有类别的最小特征集合；  例如：如区分每个人的特征包括姓名、性别、籍贯、工作单位、身份证号……则该算法将选择：身份证号。  搜索时会检测一个特征能否正确区分样本；如不能，则考察两个特征……以此类推。 41 7.7 特征选择  一种 Wrapper 算法：OBLIVION  该方法与最近邻法结合，根据特征子集的分类表现来选择特征；  用顺序后退法搜索特征子集：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的分类识别率（基于最近邻法）。依次迭代，直至识别率开始下降为止。  用 leave-one-out 方法估计平均识别率：用 N-1 个样本判断余下一个的类别，N 次取平均。 42 7.7 特征选择  许多特征选择算法力求解决搜索问题，经典搜索算法有：  分支定界法 : 最优搜索，效率比盲目穷举法高；  单独最优特征组合法：次优搜索；  顺序前进法  顺序后退法  模拟退火法  Tabu 搜索法  遗传算法

7.7特征选择 7.7特征选择口单独最优特征组合口顺序前进法 ■计算各特征单独使用时的可分性判据并加以排序，取前d个作为选择结果， ·自下而上的搜索方法； ■不一定是最优结果： ■每次从未入选的特征中选择一个特征，使得它与 ■当可分性判据对各特征具有（广义）可加性，该已入选的特征组合在一起时所得的准则值为最方法可以选出一组最优的特征；例如：大，直至特征数目增加到d为止：口各类县有正态分布： ■该方法考虑了所选特征与已入选特征之间的相关口各特征统计独立：性。 ▣可分性判据基于Mahalanobis距离； J,,,)=2J,Jo=,-,-y 7.7.1特征选择一遗传算法 7.7.1特征选择一遗传算法口该算法受进化论启迪，根据“物竞天择，适者生口术语存”规则演变； ■群体：若干个体的集合，也就是一些解的集合；口术语： ■交叉：选择群体中的两个个体，以这两个个体为 ■基因链码：使用遗传算法时要把问题的每个解编双亲作基因链码的交叉，从而产生两个新的个码成一个基因链码。体，作为后代：X100,J00 ◆ X,10001010 比如要从D个特征中挑选d个，就用一个D位 X20100010 X:01001100 的0或1组成的字符串表示一种特征组合；1表 ■变异：对某个体，随机选取其中一位，将其翻转示该特征被选中。 1000010◆1001010 每个基因链码代表一个解，称作一个“个体”，其音中的每一位看作是一个“基因”。 ■适应度：对每个解，以给定的优化准则来评价其性能的优劣，作为其适应度。 7.7.1特征选择一遗传算法 7.7.1特征选择一遗传算法遗传算法的基本框架口关于遗传算法的说明 1. 初始化进化代数0： ■由步骤3保证了最终解是所搜索过的最优解： 2. 给出初始化群体P0),并令X2为任意一个体； ■常用的终止条件是群体的世代数超过一个给定 3.对P()中每个个体估值，并将群体中最优解x 值，或连续数个世代都没有得到更优解：与x2比较，若优于g则令X= ■群体的大小和演化代数是值得重视的参数；在一 4.如果终止条件满足，则算法结束，X2为最终结定范围内，这两个参数大些能得到更好的解；果。否则，转步骤5； 5.从P()选择个体并进行交又和变异操作，得到 ■对交叉的亲本选择可采用如下规则：个体的性能新一代个体P(t什1)，令1=什1，转步骤3。越好，被选中的可能性也越大

43 7.7 特征选择  单独最优特征组合  计算各特征单独使用时的可分性判据并加以排序，取前 d 个作为选择结果。  不一定是最优结果；  当可分性判据对各特征具有（广义）可加性，该方法可以选出一组最优的特征；例如： 各类具有正态分布； 各特征统计独立； 可分性判据基于 Mahalanobis 距离； ( , , , ) ( ), ( ) ( ) ( ). 1 1 1 2 i j T D i j d k ij d ij k J x x x  J x J x  μ μ Σ μ μ     44 7.7 特征选择  顺序前进法  自下而上的搜索方法；  每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的准则值为最大，直至特征数目增加到 d 为止；  该方法考虑了所选特征与已入选特征之间的相关性。 45 7.7.1 特征选择 — 遗传算法  该算法受进化论启迪，根据“物竞天择，适者生存”规则演变；  术语：  基因链码：使用遗传算法时要把问题的每个解编码成一个基因链码。比如要从 D 个特征中挑选 d个，就用一个 D 位的 0 或 1 组成的字符串表示一种特征组合； 1 表示该特征被选中。每个基因链码代表一个解，称作一个“个体”，其中的每一位看作是一个“基因”。 46 7.7.1 特征选择 — 遗传算法  术语  群体：若干个体的集合，也就是一些解的集合；  交叉：选择群体中的两个个体，以这两个个体为双亲作基因链码的交叉，从而产生两个新的个体，作为后代；  变异：对某个体，随机选取其中一位，将其翻转  适应度：对每个解，以给定的优化准则来评价其性能的优劣，作为其适应度。 47 7.7.1 特征选择 — 遗传算法  遗传算法的基本框架 1. 初始化进化代数 t=0； 2. 给出初始化群体 P(t)，并令 xg 为任意一个体； 3. 对 P(t) 中每个个体估值，并将群体中最优解 x’ 与 xg 比较，若优于 xg，则令 xg= x’； 4. 如果终止条件满足，则算法结束，xg 为最终结果。否则，转步骤 5； 5. 从 P(t) 选择个体并进行交叉和变异操作，得到新一代个体 P(t+1) ，令 t=t+1，转步骤 3。 48 7.7.1 特征选择 — 遗传算法  关于遗传算法的说明  由步骤 3 保证了最终解是所搜索过的最优解；  常用的终止条件是群体的世代数超过一个给定值，或连续数个世代都没有得到更优解；  群体的大小和演化代数是值得重视的参数；在一定范围内，这两个参数大些能得到更好的解；  对交叉的亲本选择可采用如下规则：个体的性能越好，被选中的可能性也越大