1、模式识别 第八讲特征选择与特征提取回顾：n贝叶斯分类的原理n最小错误率贝叶斯分类n最小风险贝叶斯分类n最大似然比贝叶斯分类n正态分布情况下的贝叶斯分类1、分类器的错误率错误率是评价一个分类器的重要指标错误率受分类决策方法、训练集、测试集和偶然因素的影响分类错误是一个概率事件，错误率应由概率方式表达Pe错误率Ped(n)训练集上利用n个样本得到的错误率估计Pet(n)测试集上利用n个样本得到的错误率估计 分类器的错误率最小错误率当当这时错误率为则若使错误率最小条件：（多维积分）总错误率：第二类判错：第一类判错：211221211122min22112211221122121121),(),()(
2、).(,),()()()()()()()()()()()()()()()()()()()()()()()()()(1212xxPxxPxePxPxxPxPdxxPPdxxPPePxPPxPPdxxpPdxxpPePPePPePdxxpRxPePdxxpRxPePTTYYRRRR)()(11Pxp)()(22PxpTY1R2Rx2、二类贝叶斯分类中的错误率计算量很大）总错误率)()()()(.)()(.)()(.)()()()(.)()()(11121222321111312iMiMjjjMMMMMMMPRxPPRxPRxPRxPPRxPRxPRxPPRxPRxPRxPePijMiiRiMiii
3、idxPxPPRxPMPi11)()()()()(用平均正确分类概率：，计算相对简单。错误率：)(1)(MPeP3、多类贝叶斯分类中的错误率模式识别 第八讲特征选择与特征提取内容n基本概念n距离定义n特征提取算法n特征选择算法一 基本概念复习（1）特征：特征是从对应于一个模式类的所有信息中提取出来的，可以用来进行模式识别的部分属性。特征可以是数值型的，也可以是非数值型的。特征一定有确切的定义和表示方法。（2）特征空间：特征空间中的每一个点（每一种取值），都代表了一个模式。特征空间中的一个区域，则代表了一个模式类。特征：颜色形状特征值：颜色1.24形状0.37特征向量：x=x1,x2 =颜色,形
4、状特征空间一、基本概念1、好的分类器：n特征具有良好的可分性n特征不要重复，去掉相关性高的特征2、特征提取和特征选择的目的n降低特征维数，减少信息冗余n提高特征对类别的分辨能力n寻找对分类最重要的特征3、特征提取n通过某种变换，将原始特征从高维空间映射到低维空间。T：ER=ED T为特征提取器，通常是某种正交变换。4、特征选择n从一组特征中挑选出一些最有效的特征的过程。J(F*)=min J(F)，集合F包含d个特征，J（）是准则函数w(y)wy1y2x212一、基本概念5、模式类别可分性的测度（1）特征提取和特征选择准则n错误率是最佳的特征提取和特征选择准则函数，但难以计算。n可用的类别可分
5、性测度标准应满足以下要求：n与错误率有单调关系n当特征独立时具有可加性n具有标量测度特性n对特征具单调性dkkijdijxJxxxJ121)().，（jiijijijJJjiJjiJ时，当时，当00).).12121，（，（ddijdijxxxxJxxxJ一、基本概念二、距离（1）类内类间距离的先验概率。是各类，中的样本数，为中的样本数，为），（间距离：的平均值，称为类内类各特征向量之间的距离离，则各类中）为这两个向量间的距，（维特征向量，类中的类及分别为，令类，设一个分类问题共有jijjiinknljlikcicjnnjidjlikjijlikPPnnxxPPxJxxxxijji11)()(
6、11121)()()()()(Dc二、距离（1）类内类间距离 nikiTiiikTiikniciidciiinkikniijlikjlikjlikmmmmmxmxPxJmPmmxmimxxxxxxii1)()(1111)(1)()(T)()()()()(:则总平均向量：表示所有各类样本集的用类样本集的均值向量表示第用）（）（，（则有离，两个特征向量之间的距如采用欧氏距离来度量二、距离（1）类内类间距离 尽可能大。尽可能小，我们希望从分类器的性能来看，则散布矩阵分别为令类内散布矩阵和类间bwbwbwbwdiTiciibnikiikTiikniciiwJJJJStrStrSStrxJmmmmPSm
7、xmxPS)()()(11)()(11二、距离（2）概率距离n类间的概率距离可用分布函数之间的距离来度量)(1xp)(2xp)(1xp)(2xp完全可分：若p(x|1)0时，p(x|2)0；完全不可分：对任意x，都有 p(x|1)p(x|2)；二、距离（2）概率距离性的概率距离度量则可作为两类之间可分；为、当两类完全不可分是取得最大值；、当两类完全可分时；、满足以下条件：若任何函数 0cb0a2,1),|(),|(21JpJpJpdxPPxpxpgJp二、距离（2）概率距离 几种常见的概率距离：dxxpxpJB21)|()|(ln21Bhattacharyya(巴特查雅)距离1s0 )|()|
8、(ln121，dxxpxpJssCChernoff(切诺夫)距离二、距离（2）概率距离 XjijiXijjXjiijiijDdxxpxpxpxpdxxpxpxpdxxpxpxpxlExlEJ)|()|(ln|()|()|()|(ln|()|()|(ln)|()()(）散度似然比表达了两类之间的可分性，定义对数似然比为：)|()|(ln)(jixpxpxlij则可用两类间的平均对数似然比来作为概率距离，称为散度：三、特征提取算法1、使用类内类间距离进行特征提取类内类间距离 Jd=Jw+Jbtr（SwSb)其中Jw是类内平均距离，Jb是类间平均距离p 通常给定一个训练集后，Jd是固定的，因此，在特
9、征提取时，需要加大Jb，减小Jw，来获得满意的分类效果。因此，常使用以下准则：wbwwbwbbwSSSJStrStrJSSJSStrJ5432 )()(ln 1假设对原始特征进行了提取（变换），如变换的参数使得准则函数取得了最大值，则是最优的特征选取。三、特征提取算法1、使用类内类间距离进行特征提取以准则函数J2为例，说明如何求得最优提取变换：布矩阵；为变换后特征空间的散矩阵，为原始特征空间的散布令其变换关系为：个特征：变换后压缩为通过线性个原始特征：假设有，*,d,D2121bwbwTTdTDSSSSxWy,.,y,yyy,.,x,xxx三、特征提取算法1、使用类内类间距离进行特征提取dii
10、DDbwbT-wTbwWJSSJWSWW)Str(WSStrJ122121212 Wd,.,W0W*11）（此时，。量可构成个特征值对应的特征向则前按大小排序为：，的本征值为设矩阵得到：，取极值时的来求得其为的各分量求偏导数并令可将此式对：则准则函数在变换后为例题三、特征提取算法2、使用概率距离进行特征提取 下面只对使用Chernoff概率距离进行介绍：TTTTTTTTTTdTDMWWsWWsWsWWWsWsWWWsMWWtrssWJcxWy,.,y,yyy,.,x,xxx)(|ln|ln)1(|)1(|ln)1)1()(Chernoff ,d,D12122211212121121212121
11、式中概率距离为：则进行变换后，类都是正态分布，再假设只分两类，且两其变换关系为：个特征：变换后压缩为通过线性个原始特征：假设有三、特征提取算法2、使用概率距离进行特征提取 0)()()1()1(W0)1(0W112221111212121WWWWIWWWWWIWMWWWsWWWsWsWsMWWsWWWsTTTTTTTTT一定满足：，则最优变换阵不等于，同时假定令其为的各分量求偏导数，并将它对该方程在一般情况下无解析解，只有次优解析解。在12或12，有最优解析解。四、特征选择算法n从n个特征中挑选出m个最有效的特征，这就是特征选择的任务。n最直接的方法是根据专家的知识挑选那些对分类最有影响的特征
12、。n另一种是用数学方法进行筛选比较，找出最有分类信息的特征。四、特征选择算法1、穷举算法n从D个特征中选择最优的d个特征，可对所有可能的d个特征组合计算其准则函数，寻找其最优值，从而得到最佳特征组合。问题：若D100，d10，则计算次数为：基本不可计算。64401731030945!10)!10100(!100!)!(!ddDDCqdD四、特征选择算法2、独立算法n分别计算D个特征单独使用时的准则函数，选取最优的前d个特征作为最优特征。问题：除极特殊情况外，所得特征组合均不是最优特征组合。四、特征选择算法3、分支定界算法n利用准则函数对特征数量的单调性，在穷举算法时可跳过大量计算，是最优算法。
13、（1）算法原理：从原特征数D开始依次减少特征数，至到达所需特征数d将过程中所有可能的组合情况组合成一棵搜索树；特征数少的组合作为特征数多的组合的子节点；按特定路线遍历整个搜索树，计算所遇到的每个节点的准则函数；如遇到某个节点的准则函数值比已得到的特征数更少的节点的准则函数值还小，则放弃其下所有节点的计算；3、分支定界算法（2）搜索树的构造：根节点为0级，包含D个特征；每一级舍弃1个特征；下一级在上一级基础上继续舍弃特征；整个搜索树共有Dd级；为避免组合重复，从左至右每个子树包含的分支依次减少；例：原始特征x1,x2,x3,x4,x5 D=5,d=2开始x1x2x3x4x5x4x3x4x5x5x
14、2x3x4x4x5x5x4x5x33、分支定界算法（3）搜索路由：从根节点开始，沿最右边路径下行，计算每个节点的J值，把第一个遇到的叶节点的J值设为边界初值B;沿原路径回溯，遇到第一个分叉点后沿新路径下行，计算遇到的每个节点的J值；如遇到某节点的J值小于B，则放弃其下的所有分支的计算，向上回溯；如遇到下一个叶节点的J值大于B，则更新B为新的叶节点的J值。遍历整个搜索树，最终得到的B值对应的叶节点，就是最优特征组合。开始x1x2x3x4x5x4x3x4x5x5x2x3x4x4x5x5x4x5x3四、特征选择算法3、分支定界算法（4）特点：如准则函数J单调，一定可以得到最优解如准则函数J的单调性不
15、满足，有可能得不到最优解。计算次数可能比穷举法多，也可能比穷举法少遍历的路径可以按分支顺序，也可以按每级分支节点全计算，取最大值路径四、特征选择算法4、次优算法（1）顺序前进法（SFS)每次从未入选的特征中选择一个特征，使得它与已入选的特征组合所得到的J值最大；优点：计算量少，考虑了每一步的最优；缺点：不能剔除已入选的特征；四、特征选择算法4、次优算法（2）顺序后退法（SBS)每次从已入选的特征中剔除一个特征，使得仍保留的特征组合所得到的J值最大；优点：可评估去除特征时的可分性变化情况，缺点：计算量大，不能召回以剔除调的特征；四、特征选择算法4、次优算法（3）动态顺序前进法（l-r法)每次从未入选的特征中选择l个特征，使得它们与已入选的特征组合所得到的J值最大；再从已入选的特征中剔除r个特征，使得保留的特征组合所得到的J值最大；优点：如能动态调整l和r，计算量比分支定界法小，而效果相当；缺点：不能保证所得解为最优解；
