第五章 特征选择与特征提取

第五章 特征选择与特征提取 5.1 问题的提出 前面主要介绍的是各种分类器的设计 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，实际上我们已经完全可以解决模式识别的问题了。然而在实际应用中，在分类器设计之前，往往需要对抽取出的特征进行一下处理，争取尽量减小特征的维数。在实践中我们发现，特征的维数越大，分类器设计的难度也越大，一维特征的识别问题最容易解决，我们只要找到一个阈值 ，大于 的为一类，小于 的为一类。同时特征维数越大，要求的训练样本数量越多，例如在一维的情况下，10个训练样本就可以比较好的代表一个类别了，而在10维空间中，10个训练样本则是远远不够的。这一章中我们就来介绍一下减小特征维数的方法。 一般来说模式识别系统的输入是传感器对实物或过程进行测量所得到的一些数据，其中有一些数据直接可以作为特征，有一些数据经过处理之后可以作为特征，这样的一组特征一般称为原始特征。在原始特征中并不一定每个特征都是有用的，比如在识别苹果和橙子的系统中，我们可以抽取出的特征很多，（体积，重量，颜色，高度，宽度，最宽处高度），同样还有可能抽取出其它更多的特征。在这些特征中对分类有用的是（颜色，高度，最宽处高度），其它特征对识别意义不大，应该去除掉。这样的过程称为是特征选择，也可以称为是特征压缩。 特征选择可以描述成这样一个过程，原始特征为 维特征 ，从中选择出 个特征构成新的特征矢量 ， 。 同时，特征矢量的每一个分量并不一定是独立的，它们之间可能具有一定的相关性，比如说高度和最宽处的高度，高度值越大，最宽处的高度值也越大，它们之间具有相关性，我们可以通过一定的变换消除掉这种相关性，比如取一个比值：最宽处的高度/高度。这样的过程称为特征提取。 特征提取可以描述为这样一个过程，对特征矢量 施行变换： ， ， ，产生出降维的特征矢量 。 在一个实际系统的设计过程中，特征的选择和提取过程一般都需要进行，首先进行特征选择，去除掉无关特征，这些特征实践上根本就不需要抽取出来，这部分传感器根本不需要安装，这样也可以减小系统的的成本。然后进行特征提取，降低特征的维数。然后利用降维之后的样本特征来设计分类器。 5.2 模式类别的可分性判据 在讨论特征选择和特征压缩之前，我们先要确定一个选择和提取的原则。对一个原始特征来说，特征选择的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 很多，从 维特征种选择出 个特征共有 中选法，其中哪一种方案最佳，则需要有一个原则来进行指导。同样，特征的压缩实际上是要找到 个 元 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 ， 元函数的数量是不可数的，这也要有一个原则来指导找出 个最佳的 元函数。 我们进行特征选择和特征提取的最终目的还是要进行识别，因此应该是以对识别最有利原则，这样的原则我们称为是类别的可分性判据。用这样的可分性判据可以度量当前特征维数下类别样本的可分性。可分性越大，对识别越有利，可分性越小，对识别越不利。 人们对的特征的可分性判据研究很多，然而到目前为止还没有取得一个完全满意的结果，没有哪一个判据能够完全度量出类别的可分性。下面介绍几种常用的判据，我们需要根据实际问题，从中选择出一种。 一般来说，我们希望可分性判据满足以下几个条件： 1. 与识别的错误率由直接的联系，当判据取最大值时，识别的错误率最小； 2. 当特征独立时有可加性，即： 是第 类和第 类的可分性判据， 越大，两类的可分程度越大， 为 维特征； 3. 应具有某种距离的特点： ，当 时； ，当 时； ； 4. 单调性，加入新的特征后，判据不减小： 。 但是遗憾的是现在所经常使用的各种判据很难满足上述全部条件，只能满足一个或几个条件。 一、基于几何距离的可分性判据 在介绍这一类判据之前，先来看一下各种几何距离的定义。 1. 点与点的距离 这是我们前面已经介绍过的一种距离，可以有多种形式，如欧氏距离、街市距离、马氏距离等，特征矢量 和 之间的距离可以表示为： （欧氏距离） 2. 点与类别之间的距离 这也是我们前面定义过的一种距离度量，常用的有：平均样本法、平均距离法、最近距离法， -近邻法等。特征矢量 与 类别之间距离的平方可以表示为： （平均距离法） 其中 为 类中的样本， 为 类别中的样本数。 3. 类内距离 设 了由样本集 ，样本的均值矢量为 ，则由样本集定义的类内均方距离为： 当取欧氏距离时有： 4. 类别之间的距离 在第二章中对类别之间的距离也做过定义，包括最短距离法，最长距离法，类平均距离法等。 类与 类之间的距离可以表示为： （平均距离法） 当取欧氏距离时，可定义两类之间的均方距离： 有了距离度量之后，我们就可以在此基础上定义可分性测度了。一般来讲，当各个类别的类内距离越小时可分性越强，而类间距离越大时，可分性越强。因此可以有以各类样本之间的平均距离作为判据： 所反映的主要还是类别之间的分离程度，对类内的聚集程度反映不够。通常我们采用跟一般的矩阵形式来构造可分性判据。 1. 类内散度矩阵 设有 个类别， ， 类样本集 ， 类的散度矩阵定义为： 总的类内散度矩阵为： 2. 类间散度矩阵 第 个类别和第 个类别之间的散度矩阵定义为： 总的类间散度矩阵可以定义为： 令： 为总体均值， ，则有： 3. 总体散度矩阵 总体散度矩阵可以定义为： 其中 为总的样本数， 。可以证明： 。 可以看出三个散度矩阵均为实对称矩阵。 上面我们所定义的判据： = 。 表示取一个矩阵的迹，也就是主对角线元素之和， 维方阵 的迹为： 同样我们可以利用三个散度矩阵定义出一系列的可分性判据： 其中 表示方阵 的行列式的值，比较常用的判据是 。 基于几何距离的可分性判据计算起来比较简单，只要我们已知各个类别的训练样本集，就可以计算出三个散度矩阵，同时也就可以计算出各种可分性判据。 二、基于概率分布的可分性判据 基于几何距离的可分性判据计算起来比较简单，然而它没有考虑各类别的概率分布，因此与识别错误率之间的联系却不是很紧密。下面介绍一种直接基于概率分布的可分性判据。 先以最简单的一维特征、两类问题为例，下图表示了两种极端情况： 第一种情况是两类完全可分：对所有 的点，有 ； 第二种情况是两类完全不可分：对所有的 有 。 下面我们可以定义两个类条件概率密度函数之间的距离 作为交叠程度的度量， 应该满足如下条件： 1. 非负性， ； 2. 当两类完全重叠时 取最大值，即若对所有 有 时， ，则 ； 3. 当两类密度函数完全相同时， 应为零，即若 ，则 。 按照这样的要求，可以定义出多种可分性判据，这里我们只介绍其中一种—散度。 现在考虑 和 两类之间的可分性，取其对数似然比： 则 类对 类的平均可分性信息可以定义为： 同样 类对 类的平均可分性信息： 散度 定义为区分 类和 类的总平均信息： 从 的定义可以看出，当两类分不完全性同 时， ；当两类完全可分时， 。 基于概率的可分性判据优点是直接与识别的错误率相联系，缺点是需要已知各个类别类概率密度函数，只有当我们预先已知各类别的概率分布时，才可以利用训练样本集合估计出概率密度函数，但是对很多实际问题来说各类别的概率分布情况我们是无法预先知道的。 5.3 特征选择 所谓特征选择，就是从一组数量为 的特征中选择出一组数量为 的最优特征，（ ）这里有两个问题要解决，1、选择一种可分性判据作为最优特征选择的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ；2、找到一个好的算法，来选择出这组最优特征。下面我们就来介绍几种特征选择的算法。 一个最简单的思路是：我们假设 个特征之间相互独立，并且使用的可分性判据满足可加性： ，这时候我们只要把 个特征每个单独使用时的可分性判据 计算出来，然后从大到小排序： ，选择出前 个特征就是一组最优的特征。然而问题往往没有这么简单，这种特征独立性假设多数情况下并不成立，并且可分性判据也不一定满足可加性。 另外一个简单的思路是(穷举法)：对从 中选择出 个特征的所有组合情况都计算其可分性判据，然后选择出其中的最大者作为解决方案。当 的数值比较小时，这种方法一定是可行的，然而当 比较大时，这个组合数会非常大，比如 ， 时，组合数的数量级是 ，当 ， 时，组合数为184756。将所有的组合都计算一遍显然是不现实的。因此我们需要有一个搜索算法来进行特征选择。 一、最优搜索算法—分支定界算法 到目前为止唯一能够找到最优解的算法是“分支定界”算法。它所利用的是可分性判据中的单调性质： ，我们前面定义的各种判据都满足这个性质。 1. 分支定界的思想 分支定界算法实际上是对一个特征选择的搜索树进行搜索，下面先以 ， 的情况来说明一下搜索树。 在搜索树中根节点 代表全部特征的集合 ，每向下一级节点代表从集合中删除一个特征，节点边上的数字表示在这一级中删除的特征，比如A节点表示删除 特征，代表 ，因为最后要保留2个特征，因此树的级数为 。每一个叶节点代表一种组合，比如C节点代表 。 由于可分性判据具有单调性，因此在搜索树中的节点具有这样的性质：每个节点代表的特征集合的可分性判据要大于其后继节点代表的特征集合的可分性判据，比如： 根据这样的性质，我们就可以有如下的搜索算法。 2. 分支定界算法（不严格） 1) 搜索从右向左进行，首先设置一个界值 ，初始化为 ； 2) 如果当前节点没有分支，则向下搜索，直到叶节点为止，计算叶节点代表的特征集合的可分性判据，如果大于界值 ，则将 替换为这个判据值，并 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 这个特征集合，作为当前的最优选择；向上回溯，直到有节点有未搜索过的分支为止，按照从右向左的顺序搜索其子节点； 3) 如果当前节点有分支，则计算当前节点代表的特征集合的可分性判据，如果小于界值 ，则中止该节点向下的搜索，因为其子节点的可分性判据已经不可能大于 了。否则按照从右向左的顺序搜索其子节点。 分支定界算法的计算时间是不确定的，同最优解分支所在位置有关，如果最优解分支在最右端，并且去掉 或 的可分性判据均小于最优解，则搜索时间最短，只需计算3组可分性判据；如果每个分支的可分性判据都大于其左端分支的可分性判据，则搜索时间最长，需计算可分性判据的次数可能 次。 二、次优搜索算法 1. 顺序前进法（Sequential Forward Selection, SFS） 每次从未入选的特征中选择一个特征，使得它与已入选的特征组合到一起所得到的可分性判据最大，直到特征数增加到 为止。用 表示在第 步时的特征集合，搜索算法如下： 1) 开始时， ，从 个特征中选择一个 最大的特征，加入已选特征集， ； 2) 在第 步， 中包含已经选择的 个特征，对未入选的 个特征计算， ，其中 ，并且按照由大到小排序，将可分性判据最大的特征 加入 ， ； 3) 直到所选的特征数等于 为止。 2. 顺序后退法 (Sequential Backward Selection, SBS) 同顺序前进法的过程刚好相反，最开始时取 ，每次从中剔除一个特征，使得剩余的特征可分性判据最大。 3. 增l减r法（ 法） 前两种方法可以进一步改进，比如每次不是加入1个特征，而是加入 个特征；或者每次不是剔除一个特征，而是剔除 个特征。这样的效果要比每次加1或减1的效果好，但是计算量要增大。 另外一种改进方法是将SFS和SBS结合，先使用SFS算法逐个选入 个最佳特征，然后使用SBS算法逐个剔除 个最差特征， ，再使用SFS算法增加 个特征，再使用SBS剔除 个特征，…，直到选出 个特征为止。 5.4 特征提取 特征抽取的方法很多，下面我们以其中的一种—基于离散K-L变换(DKLT)的特征抽取，其它方法与此类似。 设原始特征为 为矢量 ，均值矢量 ，相关矩阵 ，协方差矩阵 。 我们可以对 作如下的标准正交变换，将其变为矢量 : 的每个分量： ，其中 为一个 的标准正交矩阵， 为其第 个列矢量， 。也就是说 的每个分量是 每一个分量的线性组合。 同样 可以表示为： 我们要进行特征提取，也就是要用 的 项来代替 ，这种代替必然带来误差，下面我们来对这个误差进行估计： 令： ， ，引入的均方误差为： 这又变成一个优化问题，我们希望寻找到一个标准正交矩阵 ，使得 最小，因此可以去这样的准则函数： 第一项保证均方误差最小，第二项保证 为标准正交矩阵， 为一待定常数。 ， 即： ，很明显 为相关矩阵 的特征值， 为对应于 的特征矢量，由于 是一个实对称矩阵，所以 相互正交， 为一个正交矩阵。均方无差： 根据矩阵论，有这样的结论：一个 的正定实对称矩阵有 个特征值和特征矢量，这些特征矢量之间是正交的。相关矩阵 就是一个实对称矩阵，当训练样本足够多时，也可以满足正定性，根据上式我们知道，当要从 维特征中提取出 维特征时，我们只需要统计出特征相关矩阵 ，然后计算其特征值和特征矢量，选择对应特征值最大的前 个特征矢量作成一个 特征变换矩阵 ，就可以完成特征提取。步骤如下： 1、 利用训练样本集合估计出相关矩阵 ； 2、 计算 的特征值，并由大到小排序： ，以及相应的特征矢量： ； 3、 选择前 个特征矢量作成一个变换矩阵 ； 4、 在训练和识别时，每一个输入的 维特征矢量 可以转换为 维的新特征矢量： 。 这种方法是利用相关矩阵 进行变换，同样也可以利用协方差矩阵 进行变换，还可以利用样本的散度矩阵 ， ， 或者 进行变换。过程都是一样的，需要计算特征值和特征向量，选择最大的 个特征值对应的特征矢量作出变换矩阵。 例5.1 PAGE 52 _1113077605.unknown _1113140469.unknown _1113302137.unknown _1113478101.unknown _1113479473.unknown _1113479896.unknown _1113480425.unknown _1113480562.unknown _1113480614.unknown _1113480680.unknown _1113480740.unknown _1113480642.unknown _1113480604.unknown _1113480455.unknown _1113480537.unknown _1113480426.unknown _1113480131.unknown _1113480250.unknown _1113480316.unknown _1113480424.unknown _1113480202.unknown _1113480046.unknown _1113480069.unknown _1113479918.unknown _1113479742.unknown _1113479813.unknown _1113479895.unknown _1113479759.unknown _1113479587.unknown _1113479660.unknown _1113479578.unknown _1113479199.unknown _1113479275.unknown _1113479374.unknown _1113479375.unknown _1113479302.unknown _1113479241.unknown _1113479255.unknown _1113479224.unknown _1113479035.unknown _1113479118.unknown _1113479140.unknown _1113479047.unknown _1113478736.unknown _1113478944.unknown _1113478945.unknown _1113478745.unknown _1113478536.unknown _1113477136.unknown _1113477528.unknown _1113477918.unknown _1113477944.unknown _1113478100.unknown _1113477923.unknown _1113477624.unknown _1113477869.unknown _1113477602.unknown _1113477375.unknown _1113477456.unknown _1113477457.unknown _1113477455.unknown _1113477306.unknown _1113477315.unknown _1113477189.unknown _1113302769.unknown _1113476460.unknown _1113476574.unknown _1113477094.unknown _1113476507.unknown _1113476363.unknown _1113476402.unknown _1113302923.unknown _1113302629.unknown _1113302709.unknown _1113302739.unknown _1113302682.unknown _1113302425.unknown _1113302618.unknown _1113302239.unknown _1113302424.unknown _1113299498.unknown _1113301871.unknown _1113302038.unknown _1113302085.unknown _1113302107.unknown _1113302076.unknown _1113301916.unknown _1113302037.unknown _1113301889.unknown _1113301762.unknown _1113301830.unknown _1113301855.unknown _1113301774.unknown _1113301624.unknown _1113301687.unknown _1113301709.unknown _1113301669.unknown _1113299509.unknown _1113156696.unknown _1113157092.unknown _1113157511.unknown _1113157750.unknown _1113157994.unknown _1113157457.unknown _1113156952.unknown _1113157086.unknown _1113156936.unknown _1113156417.vsd _1113156538.unknown _1113156648.unknown _1113156518.unknown _1113156327.unknown _1113156363.unknown _1113140470.unknown _1113133390.unknown _1113137552.unknown _1113137999.unknown _1113139877.unknown _1113139947.unknown _1113139952.unknown _1113139935.unknown _1113139828.unknown _1113139864.unknown _1113138143.unknown _1113137790.unknown _1113137961.unknown _1113137976.unknown _1113137806.unknown _1113137682.unknown _1113137722.unknown _1113137647.unknown _1113133762.unknown _1113133998.unknown _1113137213.unknown _1113137240.unknown _1113134088.unknown _1113133941.unknown _1113133985.unknown _1113133878.unknown _1113133576.unknown _1113133736.unknown _1113133755.unknown _1113133653.unknown _1113133522.unknown _1113133568.unknown _1113133429.unknown _1113112939.unknown _1113133020.unknown _1113133123.unknown _1113133243.unknown _1113133384.unknown _1113133239.unknown _1113133089.unknown _1113133112.unknown _1113133088.unknown _1113132863.unknown _1113132929.unknown _1113132997.unknown _1113132897.unknown _1113132792.unknown _1113132801.unknown _1113113016.unknown _1113078174.unknown _1113078381.unknown _1113112917.unknown _1113112918.unknown _1113078382.unknown _1113078265.unknown _1113078294.unknown _1113078380.unknown _1113078215.unknown _1113077869.unknown _1113078021.unknown _1113078057.unknown _1113077925.unknown _1113078015.unknown _1113077746.unknown _1113077800.unknown _1113077639.unknown _1113069236.unknown _1113075861.unknown _1113076594.unknown _1113077348.unknown _1113077450.unknown _1113077585.unknown _1113077383.unknown _1113076684.unknown _1113077294.unknown _1113076604.unknown _1113076202.unknown _1113076356.unknown _1113076466.unknown _1113076237.unknown _1113076141.unknown _1113076156.unknown _1113076109.unknown _1113070631.unknown _1113072870.unknown _1113073848.unknown _1113075679.unknown _1113073818.unknown _1113072783.unknown _1113072821.unknown _1113070802.unknown _1113071363.unknown _1113070672.unknown _1113069847.unknown _1113070050.unknown _1113070339.unknown _1113070514.unknown _1113070521.unknown _1113070346.unknown _1113070314.unknown _1113070037.unknown _1113069708.unknown _1113069709.unknown _1113069336.unknown _1113026570.unknown _1113068947.unknown _1113069113.unknown _1113069166.unknown _1113069192.unknown _1113069154.unknown _1113069040.unknown _1113069041.unknown _1113069039.unknown _1113026680.unknown _1113068928.unknown _1113068938.unknown _1113068852.unknown _1113026612.unknown _1113026673.unknown _1113026575.unknown _1113025185.unknown _1113025568.unknown _1113026415.unknown _1113026433.unknown _1113025634.unknown _1113026382.unknown _1113025540.unknown _1113025557.unknown _1113025492.unknown _1113025057.unknown _1113025143.unknown _1113025176.unknown _1113025094.unknown _1113023383.unknown _1113023399.unknown _1113023375.unknown _1111328349.unknown