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

1、模式识别讲义2011版：第五讲 特征捉取和特征选抒第五讲特征提取和特征选择、基本概念1、特征选取图1特征选取的内容在模式识别系统中，确定分类和学习过程所使用的特征是非常重要的一个环 节，获得对分类最有效的特征，同时尽最大可能减少特征维数，是特征选収的主 要任务。特征选取可以分成原始特诊的采集和转换、有效特征的生成两个步骤。(1) 原始特征的采集和转换对于一个模式识别任务，见过模式采集和预处理得到的模式信息不一定能直 接用于模式分类，需要从中经过数据处理和转换得到对具体分类任务有效的特 征。例如对于模式采集到的图像信息，其原始数据为像素点的颜色值矩阵，而对 于不同的模式识别任务和模式识别算法，可

2、以提取出不同类型的特征：轮廓特征：图像中物体的边缘轮廓颜色特征：图像中颜色分布和均值纹理特征：图像各个部位的主体纹理 数学特征：各像素点相关性等其他物理意义不明显的数学特征(2) 有效特征的生成在获得了原始特征后，需要生成有效的特征，其主要目的是大幅度降低特征 维度，减少模式识别算法的计算量。如果不经过这一降维过程，可能出现“维数 灾难”，无法进行有效的模式识别分类。例如：在文本分类中，如果采用原始的 词频统计数据作为分类特征，则有多少个不同的词就有多少维特征，一片长文的 特征维度会超过1000维，基本无法进行计算。在降低特征维度的同时，还要提升所获得特征的有效性，因为尽管特征数量 越多，用于

3、分类的信息也越充足，但特征数星与分类有效性之间并不是线性关系。 降维到同样数量时，不同的特征对分类的有效性是不同的。特征选取需要采用适 当的算法，在降低特征维度的同时，最大可能地保留对分类有效的信息。特征选取的主要方法包括特征提取和特征选择。前考从高维特征空间映射得 到低维待征空间，新的特征和旧的特征并不相同；而后者是从高维特征中选择一 部分特征组成低维特征空间，并不改变每个特征维度本身。2、特征提取特征提取是通过某种变换，将原始特征从高维空间映射到低维空间。A： 4匕/称为特征提取器，通常是某种正交变换。对于各种可能的特征提取器，需要选择最优的一种，也就是降维后分类最有 效的一种，通常设定一

4、个准则函数几4),使得取到最优特征提取时，准则函数值 取到最大值，即J(X*)=max J()o3>特征选择特征选择是从高维特征中挑选出一些最有效的特征，以达到降低特征空间维 数的目的。S：x“2,儿yt w S,Z = 1,2,.,;d <D原始特征集合S中包含D个特征，目标特征集合F中包含d个特征。同样，对于各种可能的特征选择方案，需要选择最优的一种，也就是降维后 分类最有效的一种，通常设定一个准则函数<7(5),使得取到最优特征选择时，准 则函数值取到最大值，即J(F*)=max<7(/904、准则函数的选取(1)准则函数的选取原则在设定了准则函数后，求取最优的特

5、征提取或特征选择可以看作一个泛函求 极值的问题，因此，准则函数的选取是特征提取或特征选择算法的关键。分类正确率是最佳的准则函数，如果经过某种方案的特征提取或特征选择 后，得到的低维特征是所有可能方案中分类正确率最高的，就是最优的特征提取或特征选择。但是分类正确率难以直接计算，因此可以用特征选取方案对类别的可分性测度作为准则函数，通常两类之间的类别可分性测度要满足以下标准：与分类正确率有单调递增关系d当特征独立时具有可加性，即人（兀,花k-1%>0,当iH丿时具有标量测度特性：爲=0,当心川寸JfJ,对特征数最具单调性，W：（.丫,兀“,兀力）V J/;（ X，兀2，,Xd，Xd+i）常用

6、的类别可分析测度有基于类内类间距离和概率距离两种。（2）类内类间距离对于一个己知的样本集，类内类间距离的数学定义为：设一个分类问题共有c类，令瑠，x严分别为®类及何类中的D维 特征向量，（球，堺）为这两个向量间的出羁，则各类中各特征 向量之间的距离的平均值，称为类内类间距离：1 cC1 叫 Y陆）二扭吃弓补工D （昭堺）厶 i=l y=l ninj *=1 /=1川为q中的样本数.4为呼P的样本数，Pi. B是各类的先验概率。例:第3页门动化学院模式识别与智能系统研究所高琪 cn模式识别讲义2011版：第五讲 特征捉取和特征选抒1601234心）巧+士 $?

7、（対），申）-E 7=1 叭"）k=l f=lc = 2,片=0.6, P? = °4 加1 = 3, /I? = 2无（小；1>£巧想Ei?（昭堺） -口 ；=1 ninj k=l Z=11 1 3 3V加号占工1?（职）- * * E M3“+;恥殆工玄理,申）_I M3- 1 k-1 M- 一 n m对于随机性的统计分类，如果样本集是给定的，则无论其中各类样本如何划 分，类内类间距离都是相等的，也就是说，类内类间距离本身和分类错误率不相 关，不能直接用于类别可分性测度。虽然类内类间跖离本身不能用作类别可分性测度，但对其进行分解处理后， 可以得到与类别可

8、分性相关的测度指标。如采用均方欧氏距离来 度量两个特征向量之间的距离, 则有5（£,却）= （£_£）円垃）_申） 用表示第F类样本集的均值向量:叫=古丈 £'k = l用加表示所有各类样本集的总均值向量：m = Vil则AlJd（x）=工B右工-"山-"叫）+ （叫-第#页门动化学院模式识别与智能系统研究所高琪 cn模式识别讲义2011版：第五讲特征捉取和持征选择令类内离散度矩阵和类间离散度矩阵分别为Sb = 丫 m ： - m X"巧一 m 广i=i则 Jdx） = rr（Sw + Sb

9、）= ”（S“）+ ”（轨）=Jw + Jb儿称为类内平均距离，厶称为是类间平均距离。从类别可分性的要求來看, 希望厶尽可能小，厶尽可能大。(3) 概率距离类间的概率距离可用分布函数之间的距离来度最，例如对两类问题：当两类完全可分时，若p(x <0 0 HO,则p(x o>J=0；当两类完全不可分时: 对任意x,都有p(x cjj) = p(x2)： 一般情况下，两类会介于完全可分和完全 不可分之间。依据以上度量方式，可定义类别可分析的概率距离准则：若任何函数儿() = Jgp(x|0),p(x|初)，片，钮dx满足以下条件：a、Jp >0；b、当两类完全可分时 <，取

10、得最大值；c、当炳类完仝不可分是 丿戸为0；则可作为两类之间可分性的概率距离度呈。二、使用类内类间距离进行特征提取1、准则函数的构造类内类间距离可表示为：Jd=Jw+Jb=tF(Sw+Sb)其中几是类内平均距离，是类间平均距离。对于一个给定的样本集，人是固定不变的。而通过特征提取后，新获得的特 征使得样本集可以划分为不同的类，最佳的特征提取应当是使得各类之间的可分 性最好，也就是几最大，儿最小。因此，可以直接采用厶作为特征提取的准则 函数，称为刀准则。但直接使用准则难以得到可行的特征提取算法，考虑到类内离散度矩阵Sw 和类间离散度矩阵Sb是对称矩阵，迹和行列式值在正交变换下具有不变性，常 第5

11、页门动化学院模式识别与智能系统研究所 高琪 cn模式识别讲义2011版：第五讲 特征捉取和特征选抒构造以下儿种特征提取准则函数:tr(Sw)Sw + SbJ5=Sw(、SbJ2 = tr(Sn lSb J3 = ln, Sw2、基于丿2准则的特征提取算法假设有D个原始特征：x = x1,x2,.9xdt通过特征提取后压缩为个特征：厂其映射关系为：y = WTx令凡、冷为原始特征空间中样本集的离散度矩阵，S；、S为特征提取 后新特征空间中样本集的离散度矩阵，则有：对于力准则，进行特征提取后，准则函数值为：力=trss；）= tr（WTSyWTSbW求最优的特征提取，就是

12、求址优的变换阵"，使得准则函数值在此变换下能 取得最大值。将准则函数对"求偏导，并令其为0,解出的"就是可使得准则函数刀取 得最大值的变换阵。结论为：将矩阵的特征值按大小排序：入2毎.上心则前d个特征值对应的特征向量耳,畑,儿可构成变换阵W.即炉二丛，如，,“訂此时的准则函数值为：丿2（ W） =£儿1=1基于J2准则的特征提取算法事实上是保留了原特征空间中方差最大的特征 维度成份。例题：给定先验概率相等的两类，其均值向最分别为：曲=1,3,-1丁 和“2 =-l,-lJr,协方差矩阵为：_4 1 0_1 1 0_5=1 4 0,£>=1

13、 2 00 0 10 0 1试基于4准则求最优特征提取。解：进行特征提取前总均值向量为：“ =|（/Z14-/Z2） = OJ,OF 类间离散度矩阵为：1 2为=5工（“一“也一 "）7 21 24-1 -2-1-21类内离散度矩阵为:3-10_，sg 12-1-13010-50088-168310130001-1 = 1_8因为S，Sb的秩为1,因此&鼻只有一个非0特征值，"是DX1维的矩 阵,即向量w。求解方程得最优特征提収变换阵为：w = 6（1,5, - 8）了O三、特征选择算法特征选择是从D个特征中挑选出最有效的d个特征的过程，常用的算法有 以下儿种。1、

14、独立算法独立算法是指分别计算D个特征单独使用时的准则函数值，选取最优的前d 个特征。除非各特征相互独立，准则函数满足可加性，否则独立算法所得到的特征组 合均不能保证是最优的特征组合。因此除特殊情况外，独立算法并不实用。第7页门动化学院模式识别与智能系统研究所高琪 cn模式识别讲义2011版：第五讲 特征捉取和特征选择2、穷举算法特征选择是一个组合过程，因此如从D个特征中考査所有可能的d个特征 组合，计算其准则函数，找到最优的一个，从而得到最佳的特征选择结果，就是 穷举法的算法。D(Z>-J)!J!穷举法可以保证得到所有解中的全丿最优解，但问题是计算星太大，例如当

15、 D=1OO, d=10,需要经过(100-10)110 =17310309456440次计算才能得到特征选择结果，这在有限资源下基本是无解的。3、分支定界算法（D算法原理分支定界算法依赖于特征选取准则函数构造时的特性，即：准则函数值对特 征数量具有单调性，xd) < Ji)(xi9x2,.9xd,xd) o此时如果某组合包含上+1个特征，其准则函数值已经验证比另一种上个特征 的组合的准则函数值小，则在这XI个特征中继续去除特征，准则函数值只会更 小，不能达到求取准则函数最大值的目的，可以不再继续计算。其具体原理为：1）从原始的特征数D开始依次减少特征数，直至到达所需的特征数d:2）将过

16、程中所有可能的组合情况组合成一棵搜索树：特征数少的组合作为特 征数多的组合的子节点；3）按特定路线遍历整个搜索树，计算所遇到的每一个节点的准则函数，寻找 最大的准则函数值，此时对应的特征组合就是最优的特征选择；4）如遇到某个节点的准则函数值比已得到的特征数更少的节点的准则函数 值还小，则放弃其下所有节点的计算。显然，分支定界法是一种穷举算法，它在准则函数丿对特征数量单调的情况 下能保证取得最优解。但其搜索树的所有节点如都需要计算一遍，则计算量远大 于只从D个特征中考査所有d个特征组合的穷举法；只有当计算过程中利用准 则函数J对特征数量的单调性跳过大量节点计算时，计算星才有可能比穷举法 少。（3

17、）搜索树的构造分支定界法的搜索树可以按照以下原则构造：根节点为0级，包含Q个特征； 每一级舍弃1个特征；下一级在上一级基础上继续舍弃特征； 整个搜索树共有D-d级，每个叶节点代表了一种所需的d个特征组合:为避免组合重复，从左至右每个子树包含的分支依次减少，对搜索树进 行简化。例：原始特征=心卫丸3兀， D=4,d=2图3原始的搜索树图4简化的搜索树（3）搜索路由分支定界法对搜索树的遍历可以采用回溯法，也可以采用剪枝法。剪枝法是先计算少数儿个叶节点的准则函数值，然后从上到下依次处理各层 节点，把那些准则函数值小于已知叶节点准则函数值的节点的以下分支均剪除 掉，直至获得无法剪除的所有叶节点，再从中

18、选择准则函数值最大的一个作为最 优特征选择方案。回溯法对搜索树的遍历路由是：1）从根节点开始，沿最右边路径下行，计算每个节点的丿值，把第一个遇到 的叶节点的丿值设为边界初值沿原路径回溯，遇到第一个分叉点后沿 新路径下行，计算遇到的每个节点的丿值；2）如遇到某节点的丿值小于则放弃其下的所有分支的计算，向上回溯；3）如遇到下一个叶节点的丿值大于E,则更新8为新的叶节点的丿值。4）遍历整个搜索树，最终得到的£值对应的叶节点，就是最优特征组合。更新B初始图5搜索树的回溯法遍历例题：有一个分类问题，原始特征空间包含5个特征，试选择2个最重要的特征來 降低特征空间的维数。各特征间是相互独立的，并且都有一个独立的重要性指数，其值如下：特征X1X2X4“5重要性0.10.4解：因各特征是相互独立的，所以特征组合的准则函数值/可由组合中各特征的 准则函数值/(X相加得到。*3 X4 xs X4(J=O. 9)xs(J=0.6)x5(J=0.8) x4 K xs(J=0.5) xs(J=O. 7)B=0.9B=0.8B=0.7得到最优特征选择为小吴5，这和独立