搜索
模式识别徐蔚然北京邮电大学信息工程学院简单回顾本章讨论的问题对已有的特征空间进行改造,着重于研究对样本究竟用什么样的度量方法更好譬如用三种度量来描述苹果与梨那么是否运用这三种度量是最有效的呢？颜色：这一个指标对区分红苹果与梨很有效区分黄苹果与梨就会困难得多即，这个指标就不很有效了简单回顾降维主要有两种途径对特征空间的改造、优化、主要的目的是降维，即把维数高的特征空间改成维数低的特征空间，降维主要有两种途径特征的选择:一种是删选掉一些次要的特征问题在于如何确定特征的重要性，以及如何删选特征的提取:另一种方法是使用变换的手段，在这里主要限定在线性变换的方法上，通过变换来实现降维简单回顾特征选择和特征提取两者区别特征选择:删掉部分特征特征提取:通过一种映射，也就是说新的每一个特征是原有特征的一个函数简单回顾类别可分离性判据特征选择与特征提取的任务是求出一组对分类最有效的特征所谓有效是指在特征维数减少到同等水平时，其分类性能最佳因此需要有定量分析比较的方法,判断所得到的特征维数及所使用特征是否对分类最有利这种用以定量检验分类性能的准则称为类别可分离性判据简单回顾类别可分离性判据的种类基于距离度量的可分性判据基于概率分布的可分性判据等特征提取按欧氏距离度量的特征提取方法按概率距离判据提取特征8.4特征选择特征选择即对原有特征进行删选优化概念上十分简单一般人常想，只要逐个分析每个特征，判断它对分类的价值，然后根据其优值删去或保留，这是一个为人们常采用方法但是这种方法并不能保证特征空间的最优组合优化搜索算法特征选择的含意由原有D维特征所组成的特征空间中选出若干个特征，组成描述样本的新特征空间即从原有的D维空间选取一个d维子空间(d＜D)，在该子空间中进行模式识别搜索算法有两个问题要解决一个是选择特性的标准也就是选择前面讨论过的可分离性判据以这些判据为准则，使所选择的d维子空间具有最大的可分离性另一个问题是要找出较好的特征选择方法以在允许的时间内选择出一组最优的特征。所谓最优的特征组，就是要找到合适的特征的组合搜索算法计算量问题如果从逐个特征配组进行性能比较的话，即穷举的算法，特征配组的数量极大如果D＝100，d＝10，则q的数量级就是1013，即使D＝20，d＝10，则q也可达184756种。如果将所有可能的特征配组列举出来，按某选定的可分离性判据进行计算，从中择优，其计算量非常大搜索算法如何解决这个问题呢?如果将每维特征单独计算可分离性判据，并按其大小排队，如然后直接选用前d个特征构成新的特征空间能得到最优的可分离性？不能即使所有特征都互相独立，除了一些特殊情况外，一般用前d个最有效的特征组合成的特征组并非是最优的d维特征组因此采用这种方法并不能保证得到最优的特征组合搜索算法要得最优解，就必需采用穷举法任何非穷举的算法都不能确保所得结果是最优的，因此要得最优解，就必需采用穷举法搜索技术上采用一些技巧，使计算量有可能降低最优特征搜索法，次优解的算法搜索算法“自上而下”与“自下而上”两类算法“自上而下”:从D维特征开始，逐步将其中某些特征删除，直到剩下所要求的d维特征为止。筛选剩下的特征组在每一步上都是最优的“自下而上”:从零维特征空间开始，逐个地从D维持征中选择特征，直至达到预定的维数指标为止。在每一步都生成最优的特征空间8.4.1最优搜索算法用最少的计算量得到最优的特征组合“分支定界”算法能得到最优解的唯一快速算法属于“自上而下”算法，但是具有回溯功能，可使所有可能的特征组合都被考虑到。其核心问题是通过合理组合搜索过程，可以避免一些计算而仍能得到最优的结果。其关键是利用了判据的单调性最优搜索算法判据的单调性如果特征存在包含关系:则有:称该判据具有单调性讨论过的J1-J5,以及基于概率距离的判据JD,JC,JB都满足上述关系最优搜索算法下面我们结合一个从D＝6的六维特征空间选择d＝2的二维最优子空间的例子，说明该算法的原理以及如何利用判据的单调性减少计算量。设原D维空间有六个特征表示成{x1,x2,x3,x4,x5,x6}可用下面的搜索树形结构图表示搜索过程最优搜索算法最优搜索算法搜索树形结构图根结点为原特征空间，包含全部特征，在这里是六个特征除了根结点外，其它结点每删除一个特征，结点上的号表示被删特征序号叶结点本身也删除一个特征，而剩下的特征组的特征数为d，在此为2。该树的结构特点:即每一层结点的直接后继结点数各不相同，但是却有规律性。譬如第一层中三个结点各自的直接后继结点数从左到右分别是3、2与1个，而第一层的最左结点的三个直接后继结点的后继结点数也是如此最优搜索算法最优搜索算法在每个当前计算结点要执行的计算按是否处于回溯过程而不同。如处在非回溯过程，则执行以下几个计算:(1)确定直接后继结点数一结点的直接后继点数:在根结点处r＝6，故q＝3，有三个直接后继结点(2)确定直接后继结点要删除的特征删去其中一特征的相应判据值，判据最小最优搜索算法回溯过程要执行的任务是将第i层的ψ加上第i-1层被删除的特征，并检查其分支路数q待发现到qi-11,就到达回溯转折点，转入其相邻左边第i层结点。最优搜索算法优点该算法避免了部分d个特征组合的判据计算，与穷举相比节约了时间。缺点但是由于在搜索过程中要计算中间的判据值，因此在d很小或d很接近D时，还不如使用穷举法另外该算法必须使用具有单调性的判据有时在理论上具有单调性的判据，在实际运用样本计算时，可能不再具备单调性因此存在不能保证结果为最优的可能性8.4.2次优搜索法上述分支定界算法虽然比盲目穷举法节省计算量，但计算量仍可能很大而无法实现，因此人们还是常用次优搜索法单独最优特征组合单独最优特征组合将各特征按单独使用计算其判据值，然后取其前d个判据值最大的特征作为最优特征组合。这种做法的问题在于即使各特征是独立统计的，也不一定得到最优结果。但如果可分性判据可写成如下形式可以选出最优特征来顺序前进法(SFS)顺序前进法最简单的自下而上搜索方法首先计算每个特征单独进行分类的判据值，并选择其中判据值最大的特性，作为入选特征。然后每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的J值为最大，直到特征数增至d个为止。顺序前进法(SFS)优点顺序前进法与前一小节的单独特征最优化组合相比，由于考虑了特征之间的相关性，在选择特征时计算与比较了组合特征的判据值，要比前者好些。缺点一旦某一特征被选入，即使由于后加入的特征使它变为多余，也无法再把它剔除。该法可推广至每次入选r个特征，而不是一个，称为广义顺序前进法(GSFS)顺序后退法(SBS)顺序后退法(SBS)与面一个方法相反，是自上而下的方法从现有的特征组中每次减去一个不同的特征并计算其判据，找出这些判据值中之最大值，如此重复下去直到特征数达到予定数值d为止与SFS相比，此法计算判据值是在高维特征空间进行的，因此计算量比较大此法也可推广至每次剔除r个，称为广义顺序后退法(GSBS)增l减r法(l-r法)前面两种方法的缺点即一旦特征入选(或剔除)，过程不可逆转为了克服这种缺点，可采用将这两种方法结合起来的方法，即增l减r法原理:对特征组在增加l个特征后，转入一个局部回溯过程，又用顺序后退法，剔除掉r个特征这种方法既可能是“自上而下”方法，也可能是“自下而上”的，这取决于l与r的数据大小当l＜r时，入选特征数逐渐增加，属“自下而上”型反之属“自上而下”型。增l减r法(l-r法)此法也可推广至用GSFS及GSBS代替SFS及SBS并可在实现增加l特征时采用分几步实现增l特征用Zl步减r则用Zr步，该种方法一般称为(Zl,Zr)法这种做法是为了既考虑入选(或剔除)特征之间的相关性，又不至因此引起计算量过大。合理地设置Zl和Zr可以同时对两者，即计算复杂性及特征选择的合理性兼顾考虑增l减r法(l-r法)