模式识别讲义-特征提取和特征选择课件

模式识别 第八讲特征选择与特征提取模式识别 第八讲特征选择与特征提取回顾：n贝叶斯分类的原理n最小错误率贝叶斯分类n最小风险贝叶斯分类n最大似然比贝叶斯分类n正态分布情况下的贝叶斯分类回顾：贝叶斯分类的原理1、分类器的错误率错误率是评价一个分类器的重要指标错误率受分类决策方法、训练集、测试集和偶然因素的影响分类错误是一个概率事件，错误率应由概率方式表达Pe错误率Ped(n)训练集上利用n个样本得到的错误率估计Pet(n)测试集上利用n个样本得到的错误率估计 分类器的错误率1、分类器的错误率 分类器的错误率2、二类贝叶斯分类中的错误率2、二类贝叶斯分类中的错误率3、多类贝叶斯分类中的错误率3、多类贝叶斯分类中的错误率模式识别 第八讲特征选择与特征提取模式识别 第八讲特征选择与特征提取内容n基本概念n距离定义n特征提取算法n特征选择算法内容基本概念一 基本概念复习（1）特征：n特征是从对应于一个模式类的所有信息中提取出来的，可以用来进行模式识别的部分属性。n特征可以是数值型的，也可以是非数值型的。n特征一定有确切的定义和表示方法。（2）特征空间：n特征空间中的每一个点（每一种取值），都代表了一个模式。n特征空间中的一个区域，则代表了一个模式类。一 基本概念复习特征：颜色形状特征值：颜色1.24形状0.37特征向量：x=x1,x2 =颜色,形状特征空间特征：特征值：特征向量：特征空间一、基本概念1、好的分类器：n特征具有良好的可分性n特征不要重复，去掉相关性高的特征2、特征提取和特征选择的目的n降低特征维数，减少信息冗余n提高特征对类别的分辨能力n寻找对分类最重要的特征一、基本概念1、好的分类器：3、特征提取n通过某种变换，将原始特征从高维空间映射到低维空间。T：ER=ED T为特征提取器，通常是某种正交变换。4、特征选择n从一组特征中挑选出一些最有效的特征的过程。J(F*)=min J(F)，集合F包含d个特征，J（）是准则函数w(y)wy1y2x212一、基本概念3、特征提取w(y)wy1y2x212一、基本概念5、模式类别可分性的测度（1）特征提取和特征选择准则n错误率是最佳的特征提取和特征选择准则函数，但难以计算。n可用的类别可分性测度标准应满足以下要求：n与错误率有单调关系n当特征独立时具有可加性n具有标量测度特性n对特征具单调性一、基本概念5、模式类别可分性的测度一、基本概念二、距离（1）类内类间距离二、距离（1）类内类间距离二、距离（1）类内类间距离二、距离（1）类内类间距离二、距离（1）类内类间距离二、距离（1）类内类间距离二、距离（2）概率距离n类间的概率距离可用分布函数之间的距离来度量完全可分：若p(x|1)0时，p(x|2)0；完全不可分：对任意x，都有 p(x|1)p(x|2)；二、距离（2）概率距离完全可分：若p(x|1)0时，二、距离（2）概率距离二、距离（2）概率距离二、距离（2）概率距离 几种常见的概率距离：Bhattacharyya(巴特查雅)距离Chernoff(切诺夫)距离二、距离（2）概率距离Bhattacharyya(巴特查雅)二、距离（2）概率距离 散度似然比表达了两类之间的可分性，定义对数似然比为：则可用两类间的平均对数似然比来作为概率距离，称为散度：二、距离（2）概率距离 散度则可用两类间的平均对三、特征提取算法1、使用类内类间距离进行特征提取类内类间距离 Jd=Jw+Jbtr（SwSb)其中Jw是类内平均距离，Jb是类间平均距离n 通常给定一个训练集后，Jd是固定的，因此，在特征提取时，需要加大Jb，减小Jw，来获得满意的分类效果。因此，常使用以下准则：假设对原始特征进行了提取（变换），如变换的参数使得准则函数取得了最大值，则是最优的特征选取。三、特征提取算法1、使用类内类间距离进行特征提取类内类间距离三、特征提取算法1、使用类内类间距离进行特征提取以准则函数J2为例，说明如何求得最优提取变换：三、特征提取算法1、使用类内类间距离进行特征提取三、特征提取算法1、使用类内类间距离进行特征提取三、特征提取算法1、使用类内类间距离进行特征提取例题例题模式识别讲义-特征提取和特征选择课件三、特征提取算法2、使用概率距离进行特征提取 下面只对使用Chernoff概率距离进行介绍：三、特征提取算法2、使用概率距离进行特征提取三、特征提取算法2、使用概率距离进行特征提取 该方程在一般情况下无解析解，只有次优解析解。在12或12，有最优解析解。三、特征提取算法2、使用概率距离进行特征提取 该方程在四、特征选择算法n从n个特征中挑选出m个最有效的特征，这就是特征选择的任务。n最直接的方法是根据专家的知识挑选那些对分类最有影响的特征。n另一种是用数学方法进行筛选比较，找出最有分类信息的特征。四、特征选择算法从n个特征中挑选出m个最有效的特征，这就是特四、特征选择算法1、穷举算法n从D个特征中选择最优的d个特征，可对所有可能的d个特征组合计算其准则函数，寻找其最优值，从而得到最佳特征组合。问题：若D100，d10，则计算次数为：基本不可计算。四、特征选择算法1、穷举算法四、特征选择算法2、独立算法n分别计算D个特征单独使用时的准则函数，选取最优的前d个特征作为最优特征。问题：除极特殊情况外，所得特征组合均不是最优特征组合。四、特征选择算法2、独立算法四、特征选择算法3、分支定界算法n利用准则函数对特征数量的单调性，在穷举算法时可跳过大量计算，是最优算法。（1）算法原理：从原特征数D开始依次减少特征数，至到达所需特征数d将过程中所有可能的组合情况组合成一棵搜索树；特征数少的组合作为特征数多的组合的子节点；按特定路线遍历整个搜索树，计算所遇到的每个节点的准则函数；如遇到某个节点的准则函数值比已得到的特征数更少的节点的准则函数值还小，则放弃其下所有节点的计算；四、特征选择算法3、分支定界算法（1）算法原理：3、分支定界算法（2）搜索树的构造：根节点为0级，包含D个特征；每一级舍弃1个特征；下一级在上一级基础上继续舍弃特征；整个搜索树共有Dd级；为避免组合重复，从左至右每个子树包含的分支依次减少；例：原始特征x1,x2,x3,x4,x5 D=5,d=2开始x1x2x3x4x5x4x3x4x5x5x2x3x4x4x5x5x4x5x33、分支定界算法（2）搜索树的构造：例：原始特征x1,x3、分支定界算法（3）搜索路由：从根节点开始，沿最右边路径下行，计算每个节点的J值，把第一个遇到的叶节点的J值设为边界初值B;沿原路径回溯，遇到第一个分叉点后沿新路径下行，计算遇到的每个节点的J值；如遇到某节点的J值小于B，则放弃其下的所有分支的计算，向上回溯；如遇到下一个叶节点的J值大于B，则更新B为新的叶节点的J值。遍历整个搜索树，最终得到的B值对应的叶节点，就是最优特征组合。开始x1x2x3x4x5x4x3x4x5x5x2x3x4x4x5x5x4x5x33、分支定界算法（3）搜索路由：开始x1x2x3x4x5x4四、特征选择算法3、分支定界算法（4）特点：如准则函数J单调，一定可以得到最优解如准则函数J的单调性不满足，有可能得不到最优解。计算次数可能比穷举法多，也可能比穷举法少遍历的路径可以按分支顺序，也可以按每级分支节点全计算，取最大值路径四、特征选择算法3、分支定界算法（4）特点：四、特征选择算法4、次优算法（1）顺序前进法（SFS)每次从未入选的特征中选择一个特征，使得它与已入选的特征组合所得到的J值最大；优点：计算量少，考虑了每一步的最优；缺点：不能剔除已入选的特征；四、特征选择算法4、次优算法（1）顺序前进法（SFS)四、特征选择算法4、次优算法（2）顺序后退法（SBS)每次从已入选的特征中剔除一个特征，使得仍保留的特征组合所得到的J值最大；优点：可评估去除特征时的可分性变化情况，缺点：计算量大，不能召回以剔除调的特征；四、特征选择算法4、次优算法（2）顺序后退法（SBS)四、特征选择算法4、次优算法（3）动态顺序前进法（l-r法)每次从未入选的特征中选择l个特征，使得它们与已入选的特征组合所得到的J值最大；再从已入选的特征中剔除r个特征，使得保留的特征组合所得到的J值最大；优点：如能动态调整l和r，计算量比分支定界法小，而效果相当；缺点：不能保证所得解为最优解；四、特征选择算法4、次优算法（3）动态顺序前进法（l-r法)