（控制科学与工程专业论文）基于支持向量机的特征选择方法的研究与应用.pdf

摘要 特征选择和提取技术是当前信息领域，尤其是模式识别领域的研究热点之 一。随着人工智能、计算机技术的迅速发展和应用领域的不断拓宽，特征选择 和提取方法得到了较大的发展，这方面基于统计或机器学习的理论研究成果不 断出现，其中的一些已在实际工程应用中显示出巨大的发展潜力。 本文主要讨论基于支持向量机的特征选择方法的理论研究工作及其相关 的应用。考虑到特征选择算法应用领域的广泛性，文中选取了化工领域，生物 信息领域中的多个不同类型的应用数据集作为算法分析和测试的对象。这些对 象的特征所具有的相互关系涵盖了现实当中特征间可能存在的大部分关系，例 如不相关、线性相关和非线性相关等。文中以应用的领域为线索，以支持向量 机为特征选择算法的基本工具，对这些问题的处理方法加以阐述，并初步解释 了所选择的重要特征的物理意义。为了迸一步的考察算法的实用性，我们选择 以模糊支持向量机为代表的几种决策工具建立诊断系统j 对该特征选择算法的 性能作出了一个综合性的考察。 本文的主要内容如下： 1 ) 介绍了特征选择算法发展的各个分支方向及发展态势。对国内外当前的 研究成果进行了详尽的分析和阐述，指出了理论研究和实际应用中所存 在的困难和一些亟待解决的问题，并提出了一种可供实际应用的解决对 策。 2 ) 目前生物信息癌症诊断数据集中普遍存在高维度、小样本情况。在这些 数据集上，传统的基于统计的和基于线性分类器的特征选择方法难以奏 效，本文提出了一种基于遗传算法和非线性核支持向量机的特征选择方 法。用遗传算法来确定进行特征选择操作的非线性核支持向量机的核参 数和惩罚参数。实验中的各项参数表明，所提出的算法在性能上要优于 基于统计的和基于线性分类器的特征选择方法，且所选择的特征具有较 为明显的生物意义。 3 ) 基于遗传算法和非线性支持向量机的特征选择算法虽然能够在一定程 度上取得较为满意的效果，但是它的运算效率较低，还不能满足实际应 浙江大学博士学位论文 用的需求。为此，我们从回归特征消除的整个过程分析出发，提出了 种在基于非线性核支持向量机的回归特征消除方法中应用自适应核参 数的方法，并提出了一种快速整定核参数的策略。在癌症诊断生物信息 数据上的测试结果表明，这种方法的性能在某种程度上更加优于基于遗 传算法和非线性支持向量机的特征选择算法，而且运算速率大大加快， 具有一定应用价值。 4 ) 回归特征消除的过程是一个对特征进行逐个消除的循环过程，换言之， 该算法的运算量非常大，如果特征逐个消除，那么算法的运算时间与特 征的数量成正比，严重影响到该算法实际应用的可能性。针对这一问题， 我们根据特征对决策机器的贡献，提出了一系列统计指标用于在保证算 法性能的前提下，加速整个特征选择的过程。在t e p 标准数据集上的实 验表明，该算法达到了这个目的。 5 ) 特征选择的目的基本上可以分为两部分，一是为了选择出更多的关键性 的目标变量，从研究的角度确定出引发故障或者疾病的根源，另外一个 则是对最后的决策过程起辅助作用，消除不相关或者不重要的变量所带 来的干扰作用。我们在多类的癌症诊断生物信息数据集和t e p 数据集上 针对这两方面都作了相关的讨论，每两类之间都应用基于支持向量机的 回归特征消除方法，在确定最佳特征组之后，用基于参数自整定的模糊 支持向量机方法来进行诊断决策。实验结果表明，本研究得到了较多的 可供研究的关键变量，获得了令人满意的决策效果。 6 ) 针对现有单一分类器在很多决策领域内难以取得满意分类效果的问题， 从现有的特征选择的观点出发，提出了一种基于特征选择算法来构建双 层式组合分类器的新方法。在用蛋白质质谱芯片所采集的卵巢癌数据集 上的应用测试表明，该方法相对于单个分类器而言具有较高的精度提 升，同时避免了一般组合分类器结构过于复杂的通病。 7 ) 最后对全文进行概括总结，并指出理论和应用上有待进一步研究的问 题。 关键词：支持向量机；参数整定：遗传算法；回归特征消除；特征选择；模糊 决策；算法加速；组合分类器；化工过程故障信息发现与诊断；生物信息发现 与疾病诊断 i a b s t r a c t f e a t l l r es e l e c t i o na n de x 打a c t i o nt e c h n i q u e sa r eh o tt 叩i ci nc u r r e n ti n f o m a t i o n s c i e n c e ，e s p e c i a l l yi nf i e l do fp a t t e mr e c o g n i 6 0 n t h i sk i n do ft c c h n i q u e sp r o 伊e s s w i t l lt h es t e po fd e v e l o p m e i l ti na n m c i a li n t e l l 噜e n c ea n dc o m p u t e rt e c h n o l o g y s ”c h r o n o u s l y v a r i o u st l l e o r e t i ca c h i e v e m e n t sb a s e do ns t a t i s 石c a l o rm a c h i n e l e 删n ga p p e a r e de n d l e s s l y ， af e wo fw h i c hh a db e e n印p l i e di np r a c t i c a l e n g 至n e e 矗n ga n dp 拍n n e d w e n ， i nt h i sd i s s e n a t i o n ，t h e o f e t i cr e s e a r c ha n dr e l a t e d 印p l i c a t i o n so f f 醯h h l es e l e c d o n b a s e do ns u p p o nv e c t o rm a c h j n ea r ed i s s s e dm o s t l yc o n s i d e r i n gt h eu n i v e r s a l 时 o fa p p l j c a t i o nf i e l d s f o rf c a t l l r es e l e c t i o n a l g o r i t h m s ，w es e l e c tm a n yk i n d s o f d a t a s e t si nc h e m i c a le n g i n e e r i n ga n db i o i n f o m a t i c sa sm ea n a l y s i s 锄dt c s td b j c c t s f 研o u ra l g o r i 1 m s t h er e l a t i o no ft h ef e a n j r e si nt h e s eo b j e c t sc o m a i l l sm o s t “n d s o fr e l a t i o n sa m o n gf e a 加r e si nt m e 1 i f e ，e g u n c o r r e l a t e d ，砷d1 i n e a rc o r r e l a t e da n d n 一1 i n e a rc o r r e l a t e d ，u s i n ga p p l i c a t i o n 丘e l d sa si n d c xa n df e a t u r es e l e c t i o n a 1 9 0 r i t l l i i lb a s e do ns u p p o r tv e c t o rm a c h i l l ea sb a s i ct o o l ，t h ed i s p o s a lf o rd e 嗣i n g w i t l l 吐l e s er e l a t i o n si s e x p l a i n e d ，a n dt h ep h y s i c a lm e a n j n g so fm e s ei m p o n a n t f e a m r e sa r ca l s oi n v 0 1 v e dp f i m a r i l y i no r d e rt op m v et h e e f f b c t i v e n e ；so fo w a l g o r i t h m sc o i r l p r c h e n s i v e l y ，m z z ys u p p o r tv e c t o rm a c h i n ea n ds o m eo t l l c rd e c i s i o n m a c h i n e sa r cs e l e c t e dt oc o n s t 兀l c td i a g n o s i ss y s t e m sb a s e d 叩t h er e s u l t sa c h i e v e d a b o v e t h em a i nc o n t b u t k m so f t h ed s s e r t a t 奴ma r ea sf o l l o w s ： i e a c he m b r a n c l l l l l e n to ff 宅a t l l r es e l e c t i o na i l dt h e i re v 0 1 u t i v es t a m sa r e i n 仃o d u c e d d e t a i l e da n a l y s i sa n de x p l a n a t i o no fa c h i e v e m e n t si nm ew o r l d a r e p r e s e m e d s o m ed i ：匝c u l t i e s a n d p r o b l e m si n t h ef j e l d j l l d u d i n g t h e o r e t i ca n a l y s i sa n da p p l i c a t i o na r cp o i n t e do u t a n dac o n s m l c t i v ef u n l r c r e s e a r c hd i r e c t i o na n dd e v e l o p m e n ts t r a t c g yi nt h i sf i e l da r ea l s oi n t r o d u c e d 2 ，d a t a s e t sw i mh i 曲_ d i m e n s i o n a lb u ts m a l ln l l l l l b e ro fs a m p l e sa p p e a r e d e q u e n t l y i nb i o m e d i c a l 矗e l d s ，e g b i o c h i p sb a s e dc a n c e fd a g n o s i s 致谢 在本论文完成之际，我首先要感谢我的导师孙优贤教授。导师严谨的治学 作风、敏锐的洞察力、渊博的学识和积极的进取精神是我一生学习的榜样。多 年来，导师在学习、实践、生活等各方面都给予了我悉心的指导和无微不至的 关怀。导师强调理论联系实际、科技服务社会的谆谆教诲更令我终身难忘。 衷心感谢林庆女士在学习和生活上给予我的热诚周到的帮助。 非常感谢啥佛大学医学院王天赐副教授和周晓波研究员所提供的数据集和 在算法设计过程中提供的有益信息，因为这些，使得本文得以完成。 在本论文形成过程中，得到了现代控制工程研究所很多老师的帮助，在此 深表感谢。他们是；皮道映教授、王文海教授、戴华平副教授、王智副教授、 卢建刚副教授、章辉老师。 我要真诚地感谢同实验室的所有同学。他们和我一起进行了许多有益的讨 论，使我受益菲浅。他们是：孙宗海博士后，杨旭华、张端、黎善斌、陈积明、 孙宗海、钟伟民、夏锋、夏铮、尹征、徐军、罗艳斌、张益波、包哲静，汪辉 王成群、申兴发等博士以及童昱、徐建国、王博、马东星，黄豪佑、高嫒、郑 强等硕士。 同时要感谢刘育明、李奇安、张少杰、任世锦、周黔、付克昌、刘斌、何 宁、万征等博士对我的帮助。 感谢浙江大学控制科学与工程系的所有帮助和教过我的老师，他们是李平 教授、苏宏业教授、吴铁军教授、宋执环教授、荣冈教授，梁军教授等等。 最后，要感谢我的父母以及李志平小姐，正是他们一直以来的理解、支持 和帮助，使作者可以全身心地投入到学习和工作中。 谨以此文献给所有关心和帮助过我的亲人和朋友i 毛勇 2 0 0 6 年4 月 于求是园 第一章绪论 摘要：本章首先概述了研究特征选择的意义及这方面算法的发展状况，并从不同的角度对 特征选择算法进行了分类。接着对国内外最新的研究成果进行了总体的分析和阐述，指出 了理论研究和实际应用中所存在的困难和一些亟待解决的问题。然后从实用的角度出发， 结合机器学习的观点探讨了应用支持向量机技术来进行特征选择的研究发展对策。最后 概述了论文的立题依据、主要内容和主要贡献。 1 1 特征选择方法综述 特征选择是模式识别领域的研究热点之一。为了阐述特征选择提取与模式 识别的关系，有必要先介绍一下模式识别系统的设计组成。它大致可以分为模 式获取，预处理，特征选择提取，回归分类描述，后处理等5 个模块。它的 流程可以用图1 1 来进行表述( s aj p md ，2 0 0 2 ) 。图1 1 中多次提到“特征”的 问题，部分反映出特征的选择提取和模式的识别是息息相关的。 由分类的角度来看，模式识别就是把具体事物归到具体的某一类别的过程， 也就是先用一定数量的样本，根据它们之间的相似性进行分类器设计，而后用 所设计的分类器对待识别的样本进行分类决策。分类的过程既可以在原始数据 空间中进行，也可以对原始数据进行变换，将数据映射到晟能反映分类本质的 特征空间中进行。相比而言，后耆使得决策机器的设计变得更为容易，它通过 更为稳定的特征表示，提高了决策机器的性能，删去了多余的或者不相关的信 息，并且更加容易发现研究对象之间的固有联系。因而，特征是决定样本之间 的相似性和分类器设计的关键( g a n e s h a n a n d a ms & 心z a l l o w s k iw i j ，1 9 8 9 ) 。当 分类的目的决定之后，如何找到合适的特征是认知与识别的核心问题。但是， 由于在很多实际问题当中，常常不容易找到那些最重要的特征，或者受条件限 制不能对它们进行测量，这使得特征选择和提取的任务复杂化，从而成为构造 模式识别系统，提高决策精度的最困难的任务之一( 边肇祺& 张学工，2 0 0 0 ： t h e o d o r j d i ss & k o u t r b a sk 一2 0 0 3 ) 。 浙江大学博士学位论文 图1 1 模式识别系统设计组成基本流程图 模式识别中的另一项关键任务是进行数据分析和处理。一般来说，模式识 别系统中包含由特征和属性所描述的对象的数学模型，研究一般意义上的对象 间的相互关系很大程度上依赖于特征。在认知科学中，很多状况下，对象间的 关系是已知的，而导致这种对象间显著差别的原因是未知的。一般状态下，可 能是几个关键性的特征在引导着对象间的差别( d o u 曲e 啊e r ，2 0 0 1 ；d o u g h e n y e r “口，2 0 0 4 ；ms “d ，2 0 0 2 ) 。在实际应用的过程当中，不同的对象可能 就代表着正常状况和疾病或者故障状况，而靠这些特征就可以表述正常状态和 故障或者疾病状态之间的差别。如果能够甄别出这些导致区别的关键性特征， 那么就可以直接或者间接找到解决对象间差异性的办法，例如找到导致故障或 者疾病的关键原因( h a s t i e te f 讲，2 0 0 1 ) 。 由于上述原因特征选择在很多领域已经越来越受到人们的重视。 1 1 1 有关特征选择的一些概念 模式识别的过程需要从被识别的对象产生出一组基本的特征，它既可以是 第章绪论 具有某种含义的物理统计量，也可以使用仪器仪表所i 见量得到的测量值。这些 可以作为待识别对象的原始特征。但是原始特征的数量可能非常大，而且其中 的某些测量可能对数据分析和模式识别的过程产生副作用，因而对初始数据进 行降维操作势在必行。降维操作可以通过两种操作来实现。一种是“特征选择”， 而另外种则是“特征提取”；两者在同一模式识别系统当中也可以混合使用( 边 肇祺& 张学工，2 0 0 0 ，w c b b a r 2 0 0 2 j a i n a “靠，2 0 0 0 ；b a u d a t g a n o u a r f 2 0 0 3 ) 。 “特征选择”和“特征提取”常常同时出现在些文献当中。但是这两个术语 的意义是不完全相同的。为了避免概念上的混淆和行文的方便，我们先对这一 对名词作一些相关说明。 特征提取当样本处于高维空间的时候，通过映射( 或变换) 的方法 可以用低维空间来表示样本，这个过程叫做特征提取。映射后的特征叫二 次特征，他们是原始特征的某种组合。特征提取在广义上就是指一种变换。 若l ，是测量空间，x 是特征空间，则变换一：y 寸x 就叫做特征提取器。典 型的特征提取过程包括主元分析( p c a ) ，独立主元分析( i c a ) 等等( c a o l j “口，2 0 0 4 ，f o 邶n aj c 印s o nd ，2 0 0 4 ) 。 特征选择主要研究从一组原始特征中挑选出一些最有效的特征以达 到降低特征空间维数的目的，这个过程叫特征选择( d a s hm & l i uh ，2 0 0 3 ， d e 】1 1 1 m gm & b l l l l l m a n np | ，2 0 0 4 ) 。 用映射的方法把原始特征变换为较少的新特征，这就是特征提取。从原始 的特征中挑选出一些最有代表性的特征，这就是特征选择。从两者的定义中， 我们可以总结出两者的一些区别：1 ) 特征提取得到的结果是新的组合特征，这 些组合特征往往只具有数学意义，从物理上很难解释；而由特征选择所得到的 特征实际上就是原始的特征，往往具有很明显的物理意义。因而用特征选择不 仅可以达到提高决策精度的目的，也可以达到选择出具有重要意义的实际物理 因素的目的。2 ) 由特征提取所得到的特征往往是多个原始特征的组合。当用这 些组合特征进行模式识别的时候还需要对组合特征中所涉及到的单个的原始特 征进行测量。在很多的情况下，实际上还是需要对所有的原始特征进行测量。 而特征选择的结果则是指示出一些必须测量的重要的原始变量，而其余的冗余 的或者噪声性质的原始特征就可以忽略不计了，也就使用较少的测量变量达到 浙江大学博士学位论文 精确决策的目的。因此，特征选择算法也可称为关键特征的辨识算法( c h i a l l g l h & p e l lr j 2 0 0 4 k 1 1 2 特征选择方法的分类综述 特征选择的任务是从一组数量为d 的特征中选择出数量为d ( d d ) 的一 组最优特征。由于各个特征之间存在复杂的相互关系，在大多数情况下，如果 仅对每个单独的特征按照一定的统计或者可分性判据来进行排队，而后取排在 前面的d 个特征，这种方法所取得的结果在大多数情况下并非最优特征组，甚 至在仿真状况下还有可能取到最差的特征组( 边肇棋& 张学工，2 0 0 0 ；w e b b a r ，2 0 0 2 ) 。 从d 个特征中选择出d 个最优的特征，在这两个参数都已知的状况下，所 有可能的组合数为 q = c 暑= d l ( d d ) d f 。 如果d = 1 0 0 ，d = l o ，则q 的数量级是1 0 ”，若d = 2 0 ，d = 1 0 ，则q ；1 8 4 7 5 6 。 如果把各种可能的特征组合都算出来再用各项指标参数加以比较，这样的计算 量就已经非常之大了。而且在实际问题的研究过程当中，d 的维数往往远远高 于l o o ，例如，在利用生物芯片来进行药物设计和癌症诊断时，其产生的有效 特征的维数往往在1 0 0 0 0 左右。而实际需要选取的优化特征组的特征数量d 是 未知的( d u d o i ts “讲，2 0 0 2 ；a d 锄b l 甜口，2 0 0 1 ) 。因而，寻找可行的特征选 择算法已逐渐成为国际上研究的热点所在，它也是数据挖掘的主要理论课题之 一0 目前国际上进行该项研究的着眼点主要放在选择优化特征集合所需要的两 个主要步骤。要确定关键的变量，即优化的特征子集，首先必须确定进行搜索 所需要的策略；其次，必须确定一些评价准则，根据这些准则来评价所选择的 特征子集的好坏程度( s u nz h 酊口，2 0 0 4 ) 。因而，可以把特征选择方法从这 两个角度进行分类。 第章绪论 1 1 2 1 按搜索策略划分特征选择算法 根据算法进行特征选择所用的搜索策略可以把特征选择算法分为采用全局 最优搜索策略、随机搜索策略或启发式搜索策略的三种特征选择方法( s u nz h 盯口，2 0 0 4 ；j a i n a “，2 0 0 0 ；k u d o m s k l a n s k y j ，2 0 0 0 ) 。 ( 1 ) 采用全局最优搜索策略的特征选择算法 到目前为止，唯一应用全局最优搜索策略得到最优结果的特征方法是“分支 定界”( b r a n c ha n db o u n d ) 算法( c h e nx w ，2 0 0 3 ；f u g u n a g ak n a r e n d r ae m ， 1 9 7 5 ，h 锄a m o 佃y “口，1 9 9 0 ) 。该算法的主要思路是：定义一个评价准则函数， 该评价准则函数必须满足单调性条件，也就是，对两个特征子集一和s 2 而言， 如果s 1 是s 2 的子集，那么一所对应的评价函数值必须要小于s 2 所对应的评价 函数值。在定义了该评价函数的前提下，该算法对最终特征子集的选择过程可 以用一棵树来描述。树根是所有特征的集合，从树根往下，在树的每一级每一 支都舍弃一个特征，而后根据可分性判据值和事先定义的最佳特征子集的特征 数目，搜索满足要求的特征子集。这个过程中可使用各种树搜索算法，例如“自 上而下”搜索方法，等等。使用不同的搜索算法可以加速该方法搜索效率，提高 运行速度，相比于耗尽搜索方法大大节约了计算时间，但是从统计的角度而言， 它的运算时间数量级与耗尽搜索仍然相差不远。 这种算法能保证在事先确定优化特征子集中特征数目的情况下找到相对于 所设计的可分性判据而言的最优子集。这样的话，起码存在三个问题：1 ) 既然 该算法无法对所有的特征依据其重要性进行排序，那么如何事先确定优化特征 子集的数目就成了一个很大的问题，该问题影响到算法的求解规模，且与实际 应用紧密联系；2 ) 合乎问题要求的满足单调性的可分性判据难以设计，这里的 合乎问题要求指能够让最后选择出的特征子集符合决策的要求，取得较高的决 策正确率；3 ) 当处理高维度多类问题的时候，由于算法要运行多次，算法的运 算效率问题将非常明显。 ( 2 ) 采用随机搜索策略的特征选择算法 解特征选择这样的组合优化问题的一个非全局最优方法就是采用带有一定 智能的随机搜索策略。它在计算过程中把特征选择问题和模拟退火算法、禁忌 浙江大学博士学位论文 搜索算法、遗传算法( 王凌，2 0 0 4 ) 等、或者仅仅是一个随机重采样的b 0 0 t s 仃印 过程( t s y m b a l a 耐。，2 0 0 3 ，w u b l “d ，2 0 0 3 ) 结合起来，以概率推理和采 样过程作为算法的基础，基于对分类估计的有效性，在算法运行中对每个特征 赋以一定的权重，而后根据用户所定义的或自适应的阈值来对特征重要性进行 评价；当特征所对应的权重超出了这个阈值，它就被选中作为重要的特征来训 练分类器。这里对特征重要性的评价既可以采取特征的统计得分，也可以采用 特征对分类器的贡献率( w u b l “口，2 0 0 3 ) 。 遗传算法在这一领域的应用最为广泛( y h gj h 0 n a v a r v ，1 9 9 8 ；c h 缸g l h p e l l r - j ，2 0 0 4 ， s u n z ，h 鲥口，2 0 0 4 ； s i e d l e c h iw s k l a n s k yj ，1 9 8 9 p e n gs h “以，2 0 0 3 ) 。s i e m e c h i 等学者提出了早期的基于遗传算法和k 近邻分 类器的特征选择方法；而后杨等学者又提出了使用遗传算法结合人工神经网络 分类器进行特征选择的方法。在后者的方法中使用了基于等级排序的遗传算法 选择策略。在他们的等级选择方法中预置了一个参数p f o 5 ，1 1 ，它被设置为最 高效的特征被选择的概率；被排在第j j 位的特征的概率为p ( 1 一p ) “1 。他们使用 了几个标准的实际模式识别问题来测试算法，并得到了比较好的结果。但是， 他们在适应度函数当中用到了澳4 试集精度，这将给最终的分类器的构造带来不 可避免的偏置，也就是他们所选择出的特征可能只能有效的表征出现过的数据， 而在新出现的数据上这些特征的性能无法得到保证，c h i a n g 等学者引入了一个 关键得分的比较，使用二迸编码和标准的遗传操作数来表述特征选择问题。采 用基于训练集上分类性能的评价函数，结合几个化工过程关键变量辨识问题， 他们认为遗传算法在使用非常大的计算量的基础之上得到了比较鲁棒的结果。 从解决问题的效果上来看，这种方法可以对所有的特征按它的重要性进行排 序，甚至把分类性能引入作为特征的评价准则，得到一个较好的应用结果，但 是这一类方法同样也存在着一些问题：1 ) 大量的时间消耗，它的运行时间随着 数据集变量的增加呈指数增长，对于特征很多的数据集( 如生物芯片数据等) 很难应用；2 ) 如果在该类算法中采用的是统计得分的方式，那么仅能对所有特 征的重要性进行排序，很难确定一个优化的特征子集，而采用类似于c k a l l g 等 人的方法，那么在算法运行的过程中就必须指定优化特征子集的特征数目的上 限，算法的复杂度与该上限呈指数关系，且事先难以确定。上述两个问题在采 用o n ev s o n e 的多类分类算法当中体现尤为突出。 第一章绪论 ( 3 ) 采用启发式搜索策略的特征选择算法 采用启发式搜索策略的特征选择算法主要有以下几种： 单独最优特征组台：该方法依靠计算各特征单独使用时的判据值对特征加 以排队。取前d 个特征作为满足条件的特征组。这种方法仅当单个特征的 判据值满足加和性或者乘性条件的时候才能选择出一组最优的特征。例如： 在两类问题中，当两类都是正态分布情况，且各个特征间统计独立的时候， 用m a l l a l a i l o b i s 距离作为可分性判据，则可以达到这样的效果。但是特征 间具有这种关系仅仅是极少数情况，大多数状况下，该算法甚至可能取到 最差的特征组合( 边肇祺张学工，2 0 0 0 ) 。但是在很多情况下，该方法 可以用来去掉一些不重要的变量，例如对所有变量排序，而后去掉排在后 面的一定数目的变量。由于特征对应的判据计算较为简单，因此在很大程 度上很快地缩减特征选择的范围。是一种较好的预处理方法。 序列前向选择方法( s f s ，s e q u e t n j a lf o r 、v a r ds e l e c t i o n ) ：该方法也称为集合 增加法。它是一种自下而上的搜索方法。先把所需要的特征集合初始化为 一个空集，每一次向特征集合中增加一个特征直到到达最后的特征集。该 过程可以描述为：设所有的特征集合为q ，假设有一个已有z 个特征的特 征集x “，对每一个未入选特征；，( 即q x d 中的特征) 计算其准则函数 j ，= j ( x 日+ 白) 。选择使j ，最大的那个特征，并把它加入到集合x 4 中。实 际上，在算法的每一步，都选择了一个特征加入到当前集合，使得特征选 择准则最大。当最佳改进使特征集性能变坏或达到最大允许的特征个数的 时候，该算法认为已经选择出最佳特征子集。该算法的运算董相对较小， 但是特征之间的统计相关性没有得到充分的考虑。从这个角度出发的搜索 方式仅能适合一小撮满足特殊条件的特征集合。举个倒子，它第一步选出 的必然是使准则函数最大的一个特征，而后来每一步选出的都是对前一个 特征集合作为最佳补充的一个特征( m a ok z ，2 0 0 2 ) 。在实际的过程中， 最佳特征集合极有可能并不包括单独贡献率( 准则函数值) 最大的那个特 征，仅仅只是一些单独贡献率极为普通的特征的组合。在该算法中每一步 都可能出现这样的现象。 广义序列前向选择方法( g s b s ，g c n e m l i z c ds e q u e n t i a lf o r 啪r ds e l e c t i o n ) ：该 方法是s f s 算法的加速方法，它可以根据准则函数一次性向特征集合中增 浙江大学博士学位论文 加r 个特征。也就是在没有入选优化特征子集的剩余的特征集中，寻找一个 规模为r 的小特征集f ，使得j ( 蜀+ r ) 最大。该方法相对于s f s 在特征统 计相关性上要稍好些，但是计算量相对s f s 增大了许多，且在s f s 中出现 的问题依旧难以避免。 序列后向选择方法( s b s ，s e q u e n 石a lb a c k w a r ds e l e c t i o n ) ：该方法是一种自 上而下的方法。该方法在运行之初假定整个特征集合就是所需要的优化特 征集。而后在算法的每一步运行过程中删除一个对准则函数无贡献的特征， 直到剩余特征个数符合集合基数要求。该方法在一个较大的变量集上计算 准则函数t ，所以该算法相对于s f s 计算量要大。该方法的优势在于充分 考虑了特征之间的统计相关特性，因而在采用同样合理的准则函数的时候， 它的实际计算性能和算法的鲁棒性要大大优于s f s 算法。 广义序列后向选择方法( g s b s g e n e r a l i z c ds e q u e i l d a lb a c k w a r ds e l e c t i o n ) ： 该方法是s b s 算法的加速算法，它根据准则函数在算法的每个循环当中， 一次性删除一定个数的无用特征。它是一种可以应用于实际过程的快速特 征选择方法。他的优点在于速度较快，性能相对较好。不足之处在于有的 时候，特征消除操作进行的太快，容易丢失重要的变量，导致找不到优化 的特征组。 增，去r 选择方法：这种方法允许在特征选择的过程中进行回溯。如果， ， 则该算法是自下而上的方法。用s f s 方法将，个特征加入到当前特征集中， 然后再用s b s 方法删除r 个最差的特征。这种方法消除了嵌套问题，因为 某一步获得的特征集不一定是下一步特征集的子集。如果， o 为l a g r a n g e 系数。 通过对w 和6 求偏导数，并令相应的结果为o ，可以把这个分类问题转化 第一章绪论 为它的对偶问题，即：最大化泛函 q 恤) = q 一寺d ，a ，_ y 。y ，( x ，) ( 1 2 5 ) f = l，拉】 s t y f 口，= o ( 1 2 6 ) t = 1 o ，f = 1 ，”， ( 1 2 7 ) 口，为与第个样本相对应的l a g r a n g e 乘子。这是一个有不等式约束的二次规划 问题，因此存在唯一解。解上述问题后得到的最优分类函数是 ，( 耳) = s g n ( 工) + 6 ) = s 印 芝：z 咒( 薯功+ 6 ) ( 1 2 8 ) f = l 式中口j 是( 1 2 5 ) 、( 1 2 6 ) 、( 1 2 7 ) 的解，矿是分类阅值，可以用任一个支持 向量( 满足( 1 2 i ) 式的等号) 求得。实际上，在很多情况下，对绝大多数的 样本，它们的系数茸将为零，取不为零的西对应的那些样本就是支持向量。靠 这个方法，支持向量机内的节点个数得到了有效的控制。而对于偏置值矿，它 的求解结果往往非常小( 1 0 。7 左右) ，几乎不会对决策精度产生影响，在有的工 具包中，甚至直接将其设置为零( g u n ns r 1 9 9 8 ) 。 1 2 1 2 用于两类分类的支持向量机 在很多实际情况中，训练数据集是线性不可分的。对于这类非线性问题， 可以通过非线性变换将它转化为某个高维空问中的线性问题，在这个高维空间 中寻求最优分类面，如图1 4 所示。 由于这种变化可能比较复杂，因此在一般情况下是不容易实现的。从 ( 1 2 5 ) 和( 1 2 8 ) 可以看到，不论是对于寻优函数还是分类函数都只涉及到 训练样本之间的内积运算x ，因此实际上在高维空间中只需进行内积运算， 而这种内积运算是可以通过定义在原空间中的函数来实现的，这里可以忽略变 换的形式。 j- 、 l ， o 。曼。蛾x 一一样 尊口 f ， ， o i o 尊 j ， 、 v 6 、：夕。狡7 i 二 、_ 图1 4 数据集的非线性变换 因此，在最优分类面中采用核函数k ( 置，z ，) 实现某种非线性变换后，计算 的复杂度并没有增加，此时( 1 2 5 ) 和( 1 2 8 ) 分别写作 q ( 窿) = 呸一寺q 口，) 钞，置( t ，工，) ( 1 2 。9 ) 1 1 l ，一 ( x ) = s g n z m 足( 再，x ) 十6 。 ( 1 2 1 0 ) 上式中，常用的核函数包括以下三种： 1 ) 多项式核函数 k ( 上，薯) = ( 工五+ 1 ) 4 ( 1 ，2 1 1 ) 其中d 是多项式的阶次； 2 ) g a u s s i a n 核函数 m = c x p 一等 ， ( 1 2 1 2 ) 其中a 为核宽度参数： 3 ) s i g m o i d 函数 k ( x ，葺) = t a l l l l ( 吠x t ) + c ) ， ( 1 2 1 3 ) v 为一阶常数，c 为偏置项e 除了上诉三种核函数外，在特殊的场合还可以构造 特殊的核函数( b r a i l o v s k y v l e ta 1 ，1 9 9 9 ；c d s t i a 血jn g ，口，2 0 0 2 ) 。 在实际应用当中，即使是使用了各种变换对数据进行映射的状况下，由于 测量噪声或者人为的干扰，在很大程度上也有可能使得整个数据集中的各类数 第一章绪论 据是不可能被完全被分开的。该状况可图标为1 5 。 图1 5 样本集中的不可分状况 在文献v 矗i kv l q ( 1 9 9 9 ) 当中，提出了使用惩罚参数来控制支持向量机 对错分样本的惩罚程度，实现在错分样本的比例与算法复杂度之间的折衷，从 而通过对该参数的适当调节在某种程度上避免支持向量机训练时所产生的过拟 合现象。该过程的数学表达为：当对训练样本集用函数妒( _ ) 映射后，某些训练 样本依然不能满足如下条件 卫【( - 妒( t ) ) + 们一1 0 ( 1 2 1 4 ) 则在上述条件中增加一个松弛项毒o ，使上式转化为： 咒【( w 妒( 毛) ) + 胡一1 + 盏o ( 1 2 1 5 ) 在上式的约束条件下，求函数 ( ，f ) = 寺( w ，) 十c ( 二= ，专) ( 1 2 1 6 ) 的极小值。用偏导法将这个问题转换后，所得到的等价问题与没有加入惩罚因 子前的等价问题基本相同，仅将式( 1 2 7 ) 变为 0 c ，f = 1 ，一，”。 ( 1 2 1 7 ) 通过用二次规划方法求解该问题得到的分类面也称为广义分类面，它折衷考虑 最小错分样本和最大分类间隔。 这整个过程可以理解为：支持向量机通过某种事先选择的非线性映射将输 浙江大学博士学位论文 入向量映射到一个另一个特征空间，在这个特征空间中构造最优分类超平面 ( v 却n i kvn ，1 9 9 9 ) 。在形式上s v m 分类函数类似于一个神经网络，输出是 中间节点的线性组合，每个中间节点对应于一个支持向量，可以图标为1 6 ( 边 肇祺张学工，2 0 0 0 ) 。 k 伍1 图1 6 支持向量机结构图 实际情况下，在大部分数据集上，支持向量机进行分类时都会遇到样本线 性不可分，甚至映射后仍然不可分的状况。解决这个问题需要靠支持向量机模 型参数的选取。模型参数包括惩罚参数c 和相应的核参数。这是本文在用支持 向量机进行特征选择过程当中所需要面对的问题之一。 总结支持向量机的理论与实践方法，相比于其它一些机器学习方法，该方 法具有一些明显的优势( s c h o l k o p fb & s m o l aa j ，2 0 0 2 ；c o n e sc v a p n i k v n 。1 9 9 5 ) ： 1 ) 支持向量机方法是基于统计学习理论的结构风险最小化准则， 它不仅兼顾了传统机器学习方法所追求的经验风险最小，而且 通过寻找最大间隔分接口来控制模型的复杂度，从而有效的避 免了过拟合现象。 2 ) 它的算法是针对有限样本的情况，它所求的是现有信息下的最 3 ) 4 ) 优解，而不是有限样本可能无法反映的样本数趋于无穷大时的 最优解。 支持向量机的求解最终转化为线性条件下的凸二次优化问题， 这种优化问题的极值点即是全局最优点，相比而言，避免了神 经网络中经常出现的局部极值问题。 支持向量机与核技术结合，解决了非线性判别问题，且用稀疏 的支持向量组合方法解决了特征维数灾难问题，很大程度上保 证了分类器的推广能力。 近年来，在v l p n i k 及其研究小组的研究基础之上，很多学者也提出了许多 两类s v m 的改进算法。这些方法主要集中在快速求解支持向量机( p 1 a t tj c ， 1 9 9 9 ) ，如何使支持向量机克服扰动问题( s u y k e n sj & v a n d e w a l ej ，1 9 9 9 ，k u m a r r 鲥口，2 0 0 5 ) ，支持向量机增量算法( l a u k w & w u q h ，2 0 0 3 ) ，对s v m 的 输出进行可靠性建模( s o l l i c hp ，2 0 0 2 ；m a d e v s k a b o g d a n o v aa 甜口，2 0 0 4 ) ，以 及支持向量机的模型选择( c h a p e l l eo 群口f ，2 0 0 2 ；k e e r i t h is s ，2 0 0 2 ；s t e i n w a n i ，2 0 0 3 ) 等研究领域内。 不失一般性，本文从支持向量机基本算法的角度出发，讨论关于基于支持 向量机的特征选择算法及在此基础上的决策等一些相关问题。在上述研究进展 当中，与本文最为相关的当属支持向量机的模型选择问题。 核函数类别的选择，核函数参数的选择及惩罚参数的选择统称为支持向量 机模型选择问题。支持向量机方法当中核函数非常重要，因为样本由原始空间 映射到哥标空间的分布很大程度上由核函数决定。它的设计好坏直接影响到分 类结果。目前，在实际应用当中常用的还是前文所提到的三种核函数：高斯核 函数，多项式核函数和感知器网络核函数。文献c h i a n gl h 耐d f ( 2 0 0 4 ) ，v a p n i k v - n ( 1 9 9 9 ) ，鼬k u c h i t & a b es ( 2 0 0 5 ) 表明，一般来说这几种核函数的性能 差异不大。在这三者当中，实际应用较为广泛的是高斯核函数，这主要是因为 它具有较为明显的数学含义，用用来体现不同类样本之间的差异非常合适 ( z h a n gx & l i uy ，2 0 0 3 ) 。对于核参数的选择和惩罚参数的选择，目前大部 分文献中依然使用经验的办法人工调节，或者直接用采用这些参数的支持向量 机在验证集上的表现作为评价指标进行耗尽搜索( l e ej h & l i nc j ，2 0 0 0 ) 。 该方法效率较低，在需要对多个支持向量机进行参数选择的情况下难有作为。 2 0 浙江大学博士学位论文 而采用如( k u l k a n l ia “以，2 0 0 4 ) 当中的基于a g e n t 的遗传一科西一牛顿算法可 以较好的达到搜索合理参数的目的，但是耗费的计算资源相当大，如果在单机 上运行该方法，也需要相当长的运算时间。在该文章中，提到在选择模型参数 的过程当中，采用式( 1 2 2 ) 所提到的支持向量机的错误上界理论来调节参数， 在实验当中采用遗传算法来解决局部极小点问题，结合爬山法可以找到较为合 理的参数。而在文献( c h a p c l l e o 甜口，2 0 0 2 ) 当中，作者使用了多种理论错误 上界来寻找模型参数，包括j a a c c 0 1 a h a u s s l c r 界，o p p e t w i n m e r 界，r a d i l l s ，m a r g i n 界，s p a n 界等等，给出了这些界之间的精确性关系，并给出了一些指导性的实 验结果。该文献当中认为s p a n 界最为精确，然而该界是不连续的，作者采用了 拟合近似的方法，用连续的函数替代了该界，展现了一个较好的参数选择结果。 但是，该拟合方法所用的参数并非对任何一个数据集都适用，因而操作上较为 复杂。实际上，该优化问题的解决很大程度上依赖于合理的初值的选择，而在 理论错误界的选择上应该