特征选择提取

特征选择与提取特征的选取是模式识别的基础、关键。特征选择的好坏将直接影响到分类器设计的好坏。故从原特征的形成，到特征提取和特征选择，每一步骤都显得尤为重要。同时特征的选取它也是模式识别的难点，如何获取如何获得在追求最优解的同时代价（计算量或时间）却最小的方法。一、原特征选择的依据在运用模式识别进行分类器设计之前，毫无疑问，首先要进行广泛采集能够反映研究对象的状态、本质及性质等特征。比如，就如大家平时的讲话当中，充斥着许多描述性情节，就需从怎样描述其对象才能让大家认知，找出一大堆的描述词来对能反映的特征进行修饰。就像两个同学在分开多年以后再次遇到，其中的一个人想向另一个人打听一个不在场的同学现况，但是可能由于心奋突然一时之间想不起他的名字，这是他就会向对方提供一堆信息，比如曾用过的绰号、相貌、体型、走路的体态及说话的方式等等。这些就是泛泛的原特征，可能描述者稍加思索就可以从中找出几个甚至一个关键特征能够让对方明白他讲的是谁。比如当听者收到“当时班里男生里面个子最高的（班里最高的比其他人高都的很明显，）”或“班里最漂亮的女生（班里其他女生都惨不忍睹）”这样的话时，他就知道说的是谁了。而其它的许多特征也在描述中起到了一定的作用，一定数量的特征也可能是对方判定。故原特征选定的好坏对于整个分类器的设计过程起到了第一个瓶颈。原特征的选定应分两种情况：一种是特征之间主次很明显。向上面例子中讲的那样设计（描述）对象的特征对于设计者来说，已经比较清楚，哪个特征是最主要特征，最能反映事物的，哪个次之，哪个再次之，排序很明显，没有犯难的。这时原特征选定就比较简单，只需根据“专家知识”就能定特征。一种是特征之间的主次不明显，哪个重要哪个不重要让人犹豫不决，这时的原特征不能依赖于“专家知识”来定特征，而应该对犹豫不决的特征都收集起来，交给下个环节运用数学方法进行海选。同样，上例当中的听者收到“当时班里男生里面个子最高的（但是那时班里个子高的有好几个，而且都差不多）”或“班里最漂亮的女生（班里其他女生都个个漂亮）”的话时却因满足条件的太多了，难以产生联想。同时在原特征选定这一环节中要注意：首先，要根据需求找原特征。同样一部电台，外形设计师只获取电台的材料质地、颜色形状，而通信工程人员则会关心其频率、噪声等性能参数，而不在乎其电台是圆的还是方的，这就是需求不一样，找特征也不一样。其次，从实际情况出发找原特征。要鉴于实际，若当前的人员设备不能支撑你来获取或处理此特征，就应该抛弃或用其它可获取和处理的特征来代替。二、特征提取特征选择与提取是为了求出一组对分类最有效的特征，这就需要一个定量的准则（判据）来衡量特征对分类的有效性。把一个高维空间变换为低维空间的映射有很多，那种映射对分类最有利，需要一个比较标准。设计分类器，首先会想到有其错误率来作为标准即可。但是，基于类分布常常未知和错误概率的计算复杂，直接用错误概率作为标准来分析特征的有效性就比较困难。人们就开始找一些实用的标准来衡量各类建的可分性，但是还未有取得满意的方法。特征提取就是把维数比较多的空间最终压缩到维数比较少的空间，为下一步的特征筛选而服务的过程，是把原特征空间众多特征进行某种组合（通常是线性组合）而减少特征，降低维数的。三、特征选择特征选择就是从一组特征里挑出一些最有效的特征以降低特征空间的维数的过程。选择有两种途径：首先是从原始特征中去挑选出一些最有代表性的特征（通常在特征提取针对特征进行的映射变换之前完成，这时的特征不单单是只是数学归一，同时还具有现实意义）；再者就是用变换的方法把原始特征变换为较少的新特征。下面针对上述内容进行阐述：由原有特征空间中选出若干个特征，组成描述样本的新特征空间，即从原有的D维空间选取一个d维子空间(d＜D)，在该子空间中进行模式识别。这时就要对前面提到过的两个问题要进行解决，一个是选择特性的标准的问题，也就是选择可分离性判据，以这些判据为准则，使所选择的d维子空间具有最大的可分离性。另一个问题是找出比较好的特征选择方法，以在允许的时间为主的代价内选择出一组最优的特征。所谓最优的特征组，就是要找到合适的特征的组合。如果从逐个特征配组进行性能比较的话，即穷举的算法，特征配组的数量可能极大，组合配置的数目按下式计算如果D＝100，d＝10，则q的数量级就是1013，即使D＝20，d＝10，q也会达到184756种。如果将所有可能的特征配组列举出来，按某选定的可分离性判据进行计算，从中择优，其计算量之大是可想而知的。那末如何解决这个问题呢?曾有人以为如果将每维特征单独计算可分离性判据，并按其大小排队，如直接选用前d个特征构成新的特征空间，也许可以得到最优的可分离性。这样做的话，就把特征选择的问题过于简单化了。因为即使所有特征都互相独立（而且通过变换，仍保持相互独立的就不多了），除了极少特殊情况外，直接用前d个最有效的特征组合成的特征组并非是最优的d维特征组。因此采用这种方法并不能保证得到最优的特征组合，而需要寻找搜索最优特征组的合适方法。由于任何非穷举的算法都不能确保所得结果是最优的，因此要得最优解，就必需采用穷举法，只是在搜索技术上采用一些技巧，使计算量有可能降低。下面对一种最优特征搜索法讨论。能得到最优解的快速算法有“分支定界”算法——“自上而下”，具有回溯功能，可使所有可能的特征组合都被考虑到。其核心问题是通过合理组合搜索过程，避免一些计算而仍能得到最优的结果。其关键是利用了判据的单调性。结合一个从D＝6特征空间选择d＝2的最优子空间的例子，说明该算法的原理以及如何利用判据的单调性减少计算量。设原D维空间有六个特征表示成{x1,x2,x3,x4,x5,x6}上图的搜索树形结构表示搜索过程，根结点为原特征空间，包含全部特征，在这里是六个特征。除了根结点外，其它结点每删除一个特征，结点上的号表示被删特征序号。叶结点本身也删除一个特征，而剩下的特征组的特征数为d，在此为2。叶结点的个数由不同的d个特征配置的个数决定。由于每个结点只删除一个结点，因而从根结点到叶结点所在的层数由D-d决定，在此为4层(不算根结点所在的第零层)。该树的结构有一特点，即每一层结点的直接后继结点数各不相同，但是却有规律性。譬如第一层中三个结点各自的直接后继结点数从左到右分别是3、2与1个，而第一层的最左结点的三个直接后继结点的后继结点数也是如此。实际上整个树结构是在搜索过程中展开的。在每个当前计算结点要执行的计算按是否处于回溯过程而不同。如处在非回溯过程，则执行以下几个计算：(1)确定直接后继结点数，以根结点为例。在该结点上共有六个特征。该结点层数为i＝0，因此到达其下属某一叶结点需经(D-d-i)层(此处为4)，因而需有相应数目的特征备删除用，并且只有r-(D-d-i)个特征可用作另外的回溯支路入口，因而一结点的直接后继点数在根结点处r＝6，故q＝3，有三个直接后继结点。(2)确定直接后继结点要删除的特征为了使每一当前计算结点尽可能早地接触到判据值较大的叶结点，在确定直接后继点待删除特征时，先计算现有ψ中删去其中一特征的相应判据值，并将相应的特征Xj按判据值由小到大的顺序分别赋予相应直接后继结点，第一层的三个结点的待删除特征分别为与，也就是说有显然如此安排含有这样一种假设，即认为删除对分类较有效的特征，会使判据值有明显减小。为了说明以上两步我们再举a点为例，此时a点的为,所以，无分支结点。在d点，,达到叶结点，剩下特征组为。至于回溯过程中要执行的任务是将第i层的ψ加上第i-1层被删除的特征，并检查其分支路数q，待发现到时，就到达回溯转折点，转入其相邻左边第i层结点。从最右端首先回溯至根结点，由根结点转至中间枝的第一级点，此时再转入非回溯阶段。“分支定界”的最优搜索算法的缺点：该算法避免了部分d个特征组合的判据计算，与穷举相比节约了时间。但是由于在搜索过程中要计算中间的判据值，因此在d很小或d很接近D时，还不如使用穷举法。另外该算法必须使用具有单调