第五讲 特征提取和特征选择

《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 1 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn 第五讲 特征提取和特征选择 一、 基本概念 1、 特征选取 图 1 特征选取的内容 在模式识别系统中，确定分类和学习过程所使用的特征是非常重要的一个环 节，获得对分类最有效的特征，同时尽最大可能减少特征维数，是特征选取的主 要任务。 特征选取可以分成原始特诊的采集和转换、有效特征的生成两个步骤。 （1） 原始特征的采集和转换 对于一个模式识别任务，见过模式采集和预处理得到的模式信息不一定能直 接用于模式分类，需要从中经过数据处理和转换得到对具体分类任务有效的特 征。例如对于模式采集到的图像信息，其原始数据为像素点的颜色值矩阵，而对 于不同的模式识别任务和模式识别算法，可以提取出不同类型的特征： 轮廓特征：图像中物体的边缘轮廓 颜色特征：图像中颜色分布和均值 纹理特征：图像各个部位的主体纹理 数学特征：各像素点相关性等其他物理意义不明显的数学特征 （2） 有效特征的生成 在获得了原始特征后，需要生成有效的特征，其主要目的是大幅度降低特征 维度，减少模式识别算法的计算量。如果不经过这一降维过程，可能出现“维数 灾难”，无法进行有效的模式识别分类。例如：在文本分类中，如果采用原始的 词频统计数据作为分类特征，则有多少个不同的词就有多少维特征，一片长文的 特征维度会超过 1000维，基本无法进行计算。 在降低特征维度的同时，还要提升所获得特征的有效性，因为尽管特征数量 越多，用于分类的信息也越充足，但特征数量与分类有效性之间并不是线性关系。 降维到同样数量时，不同的特征对分类的有效性是不同的。特征选取需要采用适 当的算法，在降低特征维度的同时，最大可能地保留对分类有效的信息。 《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 2 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn 特征选取的主要方法包括特征提取和特征选择。前者从高维特征空间映射得 到低维特征空间，新的特征和旧的特征并不相同；而后者是从高维特征中选择一 部分特征组成低维特征空间，并不改变每个特征维度本身。 2、 特征提取 特征提取是通过某种变换，将原始特征从高维空间映射到低维空间。 A：X→Y； A称为特征提取器，通常是某种正交变换。 图 2 特征提取 对于各种可能的特征提取器，需要选择最优的一种，也就是降维后分类最有 效的一种，通常设定一个准则函数 J(A)，使得取到最优特征提取时，准则函数值 取到最大值，即 J(A*)=max J(A)。 3、 特征选择 特征选择是从高维特征中挑选出一些最有效的特征，以达到降低特征空间维 数的目的。 DddiSy yyyFxxxS i dD   ;,...,2,1, },......,,{:},......,,{: 2121 原始特征集合 S中包含 D个特征，目标特征集合 F中包含 d个特征。 同样，对于各种可能的特征选择方案，需要选择最优的一种，也就是降维后 分类最有效的一种，通常设定一个准则函数 J(F)，使得取到最优特征选择时，准 则函数值取到最大值，即 J(F*)=max J(F)。 4、 准则函数的选取 （1） 准则函数的选取原则 在设定了准则函数后，求取最优的特征提取或特征选择可以看作一个泛函求 极值的问题，因此，准则函数的选取是特征提取或特征选择算法的关键。 分类正确率是最佳的准则函数，如果经过某种方案的特征提取或特征选择 后，得到的低维特征是所有可能方案中分类正确率最高的，就是最优的特征提取 《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 3 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn 或特征选择。但是分类正确率难以直接计算，因此可以用特征选取方案对类别的 可分性测度作为准则函数，通常两类之间的类别可分性测度要满足以下标准： 与分类正确率有单调递增关系 当特征独立时具有可加性，即    d k kijdij xJxxxJ 1 21 )(),,, （ 具有标量测度特性：         jiij ij ij JJ jiJ jiJ 时，当 时，当 0 0 对特征数量具单调性，即： ),,,,),,, 12121 ＋（（ ddijdij xxxxJxxxJ   常用的类别可分析测度有基于类内类间距离和概率距离两种。 （2） 类内类间距离 对于一个已知的样本集，类内类间距离的数学定义为： 是各类的先验概率。，中的样本数，为中的样本数，为 ），（ ：值，称为类内类间距离向量之间的距离的平均 离，则各类中各特征）为这两个向量间的距，（特征向量， 维类中的类及分别为，类，令设一个分类问题共有 jijjii n k n l j l i k c i ji c j jid j l i k ji j l i k PPnn xx nn PPxJ xx xx i j           1 1 )()( 1 1 )()( )()( 1 2 1 )( Dc 例： 《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 4 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn                                  2 1 2 1 22 22 2 1 3 1 12 12 3 1 2 1 21 21 3 1 3 1 11 11 1 1 2 1 2 1 2121 1 11 1 22 1 2 1 32 1 2 1 23 1 2 1 33 1 2 1 1 2 1 2340602 1 2 1 k l lk k l lk k l lk k l lk n k n l j l i k i jij jid n k n l j l i k c i ji c j jid xxPP xxPP xxPP xxPP xx nn PPxJ nnPPc xx nn PPxJ i j i j ），（＋ ），（＋ ），（＋ ），（ ），（ ），（ )()( )()( )()( )()( )()( )()( )( ,,.,., )(       对于随机性的统计分类，如果样本集是给定的，则无论其中各类样本如何划 分，类内类间距离都是相等的，也就是说，类内类间距离本身和分类错误率不相 关，不能直接用于类别可分性测度。 虽然类内类间距离本身不能用作类别可分性测度，但对其进行分解处理后， 可以得到与类别可分性相关的测度指标。                mmmm n Pmxmx n P mmmmmxmx n PxJ mPmm xmim xxxxxx i T i c i i i n k i i k T i i k i c i i n k i T ii i k T i i k i c i id c i ii n k i knii j l i k j l i k j l i k i i i i                     111 11 1 1 1 11 1 )()( )()( )( )()(T)()()()( )( : 则 总均值向量： 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示所有各类样本集的用 类样本集的均值向量表示第用 ）－（）－）＝（，（则有 的距离，度量两个特征向量之间如采用均方欧氏距离来  《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 5 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn         bwbwbwd T ii c i ib n k T i i ki i k i c i iw JJStrStrSStrxJ mmmmPS mxmx n PS i        )()( )( )()( 则 间离散度矩阵分别为令类内离散度矩阵和类 1 11 1 Jw称为类内平均距离，Jb称为是类间平均距离。从类别可分性的要求来看， 希望 Jw尽可能小， Jb尽可能大。 （3） 概率距离 类间的概率距离可用分布函数之间的距离来度量，例如对两类问题： 当两类完全可分时，若 p(x|ω1) ≠0，则 p(x|ω2)＝0；当两类完全不可分时： 对任意 x，都有 p(x|ω1) ＝ p(x|ω2)；一般情况下，两类会介于完全可分和完全 不可分之间。 依据以上度量方式，可定义类别可分析的概率距离准则： 性的概率距离度量。则可作为两类之间可分 ；为、当两类完全不可分是 取得最大值；、当两类完全可分时 ；、 满足以下条件： 若任何函数 0c b 0a ],),|(),|([)( 2121 p p p p J J J dxPPxpxpgJ     二、 使用类内类间距离进行特征提取 1、 准则函数的构造 类内类间距离可表示为：Jd=Jw+Jb＝tr（Sw＋Sb) 其中 Jw是类内平均距离，Jb是类间平均距离。 对于一个给定的样本集，Jd是固定不变的。而通过特征提取后，新获得的特 征使得样本集可以划分为不同的类，最佳的特征提取应当是使得各类之间的可分 性最好，也就是 Jb最大，Jw最小。因此，可以直接采用 Jb作为特征提取的准则 函数，称为 J1准则。 但直接使用准则难以得到可行的特征提取算法，考虑到类内离散度矩阵 Sw 和类间离散度矩阵 Sb 是对称矩阵，迹和行列式值在正交变换下具有不变性，常 《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 6 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn 构造以下几种特征提取准则函数：   w bw w b w b bw S SS J Str Str J S S JSStrJ   5，，，－ )( )( ]ln[ 432 1 2、 基于 J2准则的特征提取算法 假设有 D个原始特征： TDxxxx ],,,[ 21  通过特征提取后压缩为 d个特征： Tdyyyy ],,,[ 21  其映射关系为： xWy T 令 bS 、 wS 为原始特征空间中样本集的离散度矩阵， * bS 、 * wS 为特征提取 后新特征空间中样本集的离散度矩阵，则有： WSWSWSWS b T bw T w  ** , 对于 J2准则，进行特征提取后，准则函数值为：   ])[( 1*1*2 WSWWSWtrSStrJ bT-wTbw   求最优的特征提取，就是求最优的变换阵W，使得准则函数值在此变换下能 取得最大值。 将准则函数对 W求偏导，并令其为 0，解出的 W就是可使得准则函数 J2取 得最大值的变换阵。结论为： 将矩阵 bw SS 1 的特征值按大小排序： Dλλλ  ...21 则前 d个特征值对应的特征向量 d ,...,, 21 可构成变换阵W，即 ],...,,[ 21 dW  此时的准则函数值为：   d i iWJ 1 2 ）＝（ 基于 J2 准则的特征提取算法事实上是保留了原特征空间中方差最大的特征 维度成份。 例题： 给定先验概率相等的两类，其均值向量分别为： ,]1,1,1[]1,3,1[ 21 TT   和＝ 协方差矩阵为： 《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 7 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn                       100 021 012 100 041 014 21 ＝，＝ 试基于 J2准则求最优特征提取。 解： 进行特征提取前总均值向量为： T]0,1,0[)( 2 1 21   类间离散度矩阵为：                 121 242 121 ))(( 2 1 2 1i T iibS  类内离散度矩阵为：            100 031 013 )( 2 1 21wS                             8168 5105 121 8 1 , 800 031 013 8 1 11 bww SSS 因为 bw SS 1 的秩为 1，因此 bw SS 1 只有一个非 0特征值，W是 D×1维的矩 阵，即向量 w。 求解方程 wwSS bw 1 1  得最优特征提取变换阵为： Tw )8,5,1( 8 1  三、 特征选择算法 特征选择是从 D 个特征中挑选出最有效的 d 个特征的过程，常用的算法有 以下几种。 1、 独立算法 独立算法是指分别计算 D个特征单独使用时的准则函数值，选取最优的前 d 个特征。 除非各特征相互独立，准则函数满足可加性，否则独立算法所得到的特征组 合均不能保证是最优的特征组合。因此除特殊情况外，独立算法并不实用。 《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 8 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn 2、 穷举算法 特征选择是一个组合过程，因此如从 D 个特征 中考 中考数学全套课件中考心理辅导讲座中考语文病句辨析修改中考语文古诗文必背中考单选题精选 查所有可能的 d 个特征 组合，计算其准则函数，找到最优的一个，从而得到最佳的特征选择结果，就是 穷举法的算法。 穷举法可以保证得到所有解中的全局最优解，但问题是计算量太大，例如当 D＝100，d＝10，需要经过 64401731030945 !)!( ! !)!( !      1010100 100 ddD D Cq dD 次计算才能得到特征选择结果，这在有限资源下基本是无解的。 3、 分支定界算法 （1）算法原理 分支定界算法依赖于特征选取准则函数构造时的特性，即：准则函数值对特 征数量具有单调性， ),,,,),,, 12121 ＋（（ ddijdij xxxxJxxxJ   。 此时如果某组合包含 k+1个特征，其准则函数值已经验证比另一种 k个特征 的组合的准则函数值小，则在这 k+1个特征中继续去除特征，准则函数值只会更 小，不能达到求取准则函数最大值的目的，可以不再继续计算。 其具体原理为： 1）从原始的特征数 D开始依次减少特征数，直至到达所需的特征数 d； 2）将过程中所有可能的组合情况组合成一棵搜索树；特征数少的组合作为特 征数多的组合的子节点； 3）按特定路线遍历整个搜索树，计算所遇到的每一个节点的准则函数，寻找 最大的准则函数值，此时对应的特征组合就是最优的特征选择； 4）如遇到某个节点的准则函数值比已得到的特征数更少的节点的准则函数 值还小，则放弃其下所有节点的计算。 显然，分支定界法是一种穷举算法，它在准则函数 J对特征数量单调的情况 下能保证取得最优解。但其搜索树的所有节点如都需要计算一遍，则计算量远大 于只从 D 个特征中考查所有 d 个特征组合的穷举法；只有当计算过程中利用准 则函数 J 对特征数量的单调性跳过大量节点计算时，计算量才有可能比穷举法 少。 （3） 搜索树的构造 分支定界法的搜索树可以按照以下原则构造： 根节点为 0级，包含 D个特征； 每一级舍弃 1个特征； 下一级在上一级基础上继续舍弃特征； 整个搜索树共有 D－d级， 每个叶节点代表了一种所需的 d个特征组合； 为避免组合重复，从左至右每个子树包含的分支依次减少，对搜索树进 行简化。 《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 9 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn 例：原始特征＝｛x1,x2,x3,x4｝， D=4,d=2 图 3 原始的搜索树 图 4 简化的搜索树 （3）搜索路由 分支定界法对搜索树的遍历可以采用回溯法，也可以采用剪枝法。 剪枝法是先计算少数几个叶节点的准则函数值，然后从上到下依次处理各层 节点，把那些准则函数值小于已知叶节点准则函数值的节点的以下分支均剪除 掉，直至获得无法剪除的所有叶节点，再从中选择准则函数值最大的一个作为最 优特征选择方案。 回溯法对搜索树的遍历路由是： 1）从根节点开始，沿最右边路径下行，计算每个节点的 J值，把第一个遇到 的叶节点的 J值设为边界初值 B；沿原路径回溯，遇到第一个分叉点后沿 新路径下行，计算遇到的每个节点的 J值； 2）如遇到某节点的 J值小于 B，则放弃其下的所有分支的计算，向上回溯； 3）如遇到下一个叶节点的 J值大于 B，则更新 B为新的叶节点的 J值。 4）遍历整个搜索树，最终得到的 B值对应的叶节点，就是最优特征组合。 《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 10 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn 图 5 搜索树的回溯法遍历 例题： 有一个分类问题，原始特征空间包含 5个特征，试选择 2个最重要的特征来 降低特征空间的维数。 各特征间是相互独立的，并且都有一个独立的重要性指数，其值如下： 特征 x1 x2 x3 x4 x5 重要性 0.2 0.5 0.3 0.1 0.4 解： 因各特征是相互独立的，所以特征组合的准则函数值 J可由组合中各特征的 准则函数值 J（xn）相加得到。 得到最优特征选择为{x2,x5}，这和独立算法的结果是一致的。 x1(J=1.3) X2(J=0.8) x3 x5 x4 x4(J=1.2) x3(J=1.0) x4(J=0.9) x5(J=0.6) x5(J=0.8) x2 (J=1.0) x3(J=0.7) x4(J=0.9) x4 x5 x5(J=0.5) x4(J=1.1) x3(J=1.2) x5(J=0.7) B=0.7 B=0.8 B=0.9 开始 （J=1.5） 《模式识别》讲义 2011版：第五讲 特征提取和特征选择 第 11 页 自动化学院 模式识别与智能系统研究所 高琪 gaoqi@bit.edu.cn 4、 次优算法 特征选择的穷举法虽然能获得全局最优解，但计算量太大。如采用一些次优 的算法，虽然不能保证获取到全局最优解，但计算代价会显著降低。常用的次优 算法有以下几种。 （1）顺序前进法（SFS） 从 0个特征开始，每次从未入选的特征中选择一个特征，使得它与已入选的 特征组合所得到的准则函数值最大。 kiikk XxDixXJXJ  且 最优单步方案满足： ,)},(max{)( * 11 顺序前进法的计算量为：1+1/2((D+1)D-d(d+1))。它的缺点是不能剔除已入 选的特征。 （2）顺序后退法（SBS） 从 D 个特征开始，每次从已入选的特征中剔除一个特征，使得仍保留的特 征组合所得到的准则函数值最大。 kiikk XxDixXJXJ  且 最优单步方案满足： ,)},(max{)( * 11 顺序后退法的计算量为：D×d-d(d-1)/2。它的缺点是不能召回已剔除的特征。 （3）动态顺序前进法（l-r 法） 也称为前进－后退法，它按照单步最优的原则从未入选的特征中选择 l个特 征，再从已入选的特征中剔除 r个特征，使得仍保留的特征组合所得到的准则函 数值值最大。 当 l比 r大时， 总体上算法是前进的，应当从 0个特征开始；当 l比 r小时， 总体上算法是后退的，应当从 D个特征开始。 如果 l=d，r=0，就是穷举法；如果 l和 r能实现良好的动态调节，则其计算 量比分支定界法小，而效果相当。