（应用数学专业论文）支持向量机中核函数的选取方法的研究.pdf

摘要 内容摘要：支持向量机在解决线性不可分样本的分类问题时引入核函 数技术，从而把非线性问题转化为线性问题来解决，降低了算法的 复杂度虽然目前关于核函数的研究在理论和应用两方面均取得了一 定的成果，但还未深入到足以指导核函数的选取 本文的主要研究工作有： 1 研究了混合核函数的性质，与单一的普通核函数相比，分析了 混合核函数的优势 2 为了确定由哪些类型的普通核函数来构造混合核函数，。本文 重点分析了五种常用核函数的性质特点，得到j 5 c b f 核函数、多项式 核函数和傅立叶核函数各自都有突出的优点且彼此间有很强的互补 性，由此我们以这三种核函数来构造适用于更广泛问题的混合核函 数 3 对于核参数的确定，本文另辟蹊径，采用董玉林提出的平衡约 束优化( m p e c ) 模型来优化选取核参数 4 综合利用本文的研究成果，建立若干选取规则，分别解决了核 函数的类型及核参数选取的问题，提出了不同于传统意义的核函数 的选取方法- - - - r s m ( r e a s o n a b l es e l e c t i o nm e t h o d ) 方法 5 进行实验研究，并把实验结果与传统方法相比较，实验结果表 明，本文给出的r s m 方法确定的核函数更具有合理性，能够得到性 能更加优越的s v m 关键词：支持向量机：核函数；混合核函数；平衡约束规划( m p e c ) a b s t r a c t c o n t e n t ：k e r n e lf u n c t i o ns e l e c t i o ni st h ek e yp a r ta n dt h eh a r di s s u e o fs u p p o r tv e c t o rm a c h i n e b yt h ek e r n e lt r i c k ，t h en o n l i n e a rd a t a c a nb em a p p e di n t oah i g h e rd i m e n s i o n a ll i n e a rs p a c ei n c l u d i n gt h e n o n l i n e a rd a t a ，a sar e s u l t ，t h en o n , n e a rl e a r n i n gp r o b l e mc a nb e s o l v e da sal i n e a rl e a r n i n gp r o b l e m r e c e n t l y , r e s e a r c h e so nk e r n e l f u n c t i o nh a v ea c h i e v e dg r e a tp r o g r e s s ，h o w e v e r ，t h es e l e c t i o no fk e r n e l f u n c t i o nr e i n a i n st ob eah a r dn u tt oc r a c k t h em a i nr e s u l t so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 w ea n a l y z es o m ei m p o r t a n tp r o p e r t i e so fm i x t u r e so fk e r n e l s i ns o m ea p p l i c a t i o n s ，m i x t u r e so fk e r n e l sh a v eb e t t e re f f e c t st h a na s i n g l eo r d i n a r yk e r n e l 2 w ea n a l y z es o m ep r o p e r t i e so ff i v et y p e so fo r d i n a r yk e r n e l s i no r d e rt od e t e r m i n ew h i c ht y p eo fo r d i n a r yk e r n e lc a nb eu s e dt o c o n s t r u c tm i x t u r e so fk e r n e l s i nt h i sp a p e r ，m i x t u r e so fk e r n e l sa r e c o n s t r u c t e db yr b fk e r n e l ，g a u s sk e r n e la n df o u r i e rk e r n e lb e c a u s e o ft h e i rg o o dp r o p e r t i e s 3 t h i sp a p e rg i v eam p e cm o d e lt os e l e c tt h ep a r a m e t e r sw h i c h h a sb e e np r o p o s e db yd o n gy u - l i n ，t h ep r o b l e mo fh o wt os e l e c t p a r a m e t e r sa r er e s o l v e d 4 i nt h i sp a p e r ，w ec a l lg i v es o m er e g u l a t i o n sa c c o r d i n gt ow h i c h t os e l e c tak e r n e l b a s e do nt h e s er e g u l a t i o n s ，w ep r o p o s ean e wk e r n e l 支持向量机中核函数的选取方法的研究 s e l e c t i o nm e t h o d - - - - r e a s o n a b l es e l e c t i o nm e t h o dw h i c hi sd i f f e r e n t f r o mt r a d i t i o n a lm e t h o ( i s 5 a nf a c ed e t e c t i o ne x p e r i m e n th a sb e e nm a d ea n dt h er e s u l t s h o w st h a to u rn e wm e t h o di sv e r ye f f i c i e n t ，w ec a l lo b t a i ns v m w i t h m o r es u p e r i o rp e r f o r m a n c eb yt h i sm e t h o d k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e ；k e r n e lf u n c t i o n ；m i x t u r e s o fk e r n e l ；m a t h e m a t i c a lp r o g r a m m i n gw i t he q u i l i b r i u mc o n s t r a i n t s ( m p e c ) n 1 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果论文中除特别 加以标注和致谢的地方外，不包含其他人和其他机构已经撰写或发表过的研究成果，其他同 志的研究成果对本人的启示和所提供的帮助，均已在论文中做出了明确的声明并表示谢意 学位论文作者签名智爪6 i j 日期：w 占f 汐 学位论文版权使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有权 保留并向国家有关部门或机构送交复印件和磁盘，允许论文被查阅和借阅本人授权辽宁师 范大学，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或其他复制手段保存、汇编学位论文保密的论文在解密后使用本授权书 学位论文作者签名：备小叼 指导教师签名：i 珥 e l 期：伽量乒 支持向量机中核函数的选取方法的研究 支持向量机中核函数的选取方法的研究 1引言 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是2 0 世纪9 0 年代v a p n i k 基于统 计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y , s l t ) 1 1 提出的一种新的机器学习方 法，由于其出色的学习性能，近年来成为机器学习理论和技术领域的一个研究 热点目前为止，s v m 已广泛应用于分类、回归、密度估计等领域在手写字符 识别、人脸检测、文本自动分类、时间序列预测、基因分类、函数回归、函数 逼近、文本过滤及数据挖掘、非线性系统控制等问题中，都有s v m 成功的应 用 s v m 建立在统计学习理论的v c 维理论和结构风险最小化原理基础之上， 其理论最初来自于对数据分类问题的处理数据分类问题主要由两部分组成：线 性可分的分类问题和线性不可分的分类问题当分类问题线性不可分时，通过引 入核函数技术有效地解决了该问题核函数的基本思想是：在进行分类时，对于 线性不可分的样本首先通过一个非线性映射将原空间的样本映射到一个高维的 特征空间，在高维特征空间中训练样本的像是线性可分或近似线性可分的，因 此在高维特征空间中进行线性分类，从而实现了相对于原空间的非线性可分样 本的分类 在s y m 创立之初，人们更多的是关心基于核函数的算法的设计后来认识 到，提高s v m 性能的关键之一，是设计适合给定问题的核函数，不同的核函 数会导致s v m 的性能有很大的不同，这就要求对核函数本身有深入的了解核 函数的定义和使用，并非源自机器学习问题本身但是核函数作为一种方法的提 出，与统计学习理论和以此为基础的s v m 的研究和发展密不可分 1 1统计学习理论简介 统计学习理论是一种专门研究小样本情况下机器学习规律的理论，是传统 统计学的重要发展和补充传统的统计学主要研究的是渐进理论，即当样本趋于 无穷多时的统计性质在实际问题中，样本数目往往是有限的，因此许多理论上 优秀的算法在实际应用中的效果不理想，会出现“过学习 与“欠学习”等问 题 1 支持向量机中核函数的选取方法的研究 v a p n i k 等人在2 0 世纪6 0 年代开始研究有限样本情况下的机器学习问题， 到9 0 年代，逐渐形成了较完善的理论体系一一统计学习理论该理论针对小样本 统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了 对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果 1 1 1v c 维 统计学习理论的一个重要概念是v c 维( v cd i m e n s i o n ) 概念，它是描述函数 集或学习机器的复杂性或者说是学习能力的一个重要指标，在此概念基础上发 展出了一系列关于统计学习的一致性、收敛速度、泛化性能等的重要结论模式 识别方法中v c 维的直观定义是：对一个指示函数集，如果存在h 个样本能够 被函数集里的函数按照所有可能的2 种形式分开，则称函数集能够把九个样 本打散函数集的v c 维就是它能打散的最大样本数目h 若对任意数目的样本都 有函数能将它们打散，则函数集的v c 维是无穷大有界实函数的v c 维可以通过 一定的阈值将它转化成指示函数集来定义 由定义可见，如果存在h 个样本的样本集能够被函数集打散，且任意 + 1 个样本的样本集不能被此函数集打散，则函数集的v c 维就是h ；如果对于任 意的样本数，总能找到一个样本集能够被这个函数集打散，则函数集的v c 维就 是无穷大 v c 维反映了函数集的学习能力，v c 维越大则学习机越复杂，目前还没有 通用的关于函数集v c 维计算的理论只对一些特殊的函数集知道其v c 维，比如 在佗维实数空间线性分类器和线性实函数的v c 维是n + 1 对于一些比较复杂 的学习机( 如神经网络) ，其v c 维除了与函数集选择有关外，还受学习算法的影 响，因此其确定将更加困难对于给定的学习函数集，如何用理论或实验的方法 来计算它的v c 维仍是当前统计学习理论中有待研究的一个问题 1 1 2 结构风险最小化 统计学习理论系统地研究了对于各种类型的函数集、经验风险见唧【，】和 期望风险冗【月之间的关系v 如n i k 从理论上证明了经验风险尼唧【卅与期望风 险冗 ，】之间存在一定的关系，即对任给的0 叼 0 ，则z 相对应的y 值为1 ，否则，z 相对应的y 值为一1 由此可见，求解分类问题，实质上就是找到一个把留上的 点分成两部分的规则 1 2 1 线性支持向量机 s v m 是从线性可分情况下最优分类超平面发展而来的，基本思想可用两类 线性可分情况说明s v m 学习的结果是寻找最优的超平面，不但能将两类样本 点正确地分开，而且使分类间隔最大分类间隔是指过两类中离分类超平面最近 的样本点且平行于分类超平面的两个超平面间的距离 当训练点完全线性可分时，s v m 算法通过求解下面的问题得到最大间隔分 类超平面 r a u ，i 6 n 互11 1 u 1 1 2 ( 1 1 ) s t y i ( ( 6 9 戤) + b ) 1 ，i = 1 ，l 对于上述优化问题，其解可以通过l a g r a n g e 对偶问题得到 ll m 。i n 互1 ；荟。o t i a j y i y j ( x i ) 一暑 s t lq 瓠：0 ， ( 1 2 ) 啦0 ，i = 1 ，z 其中，q = ( q 1 ，q f ) t r ，o t i 是对应于不等式约束犰( p 龟) + b ) 1 的l a g r a n g e 乘子如果解q + 的分量q ： 0 ，则称对应的输入样本点戤为支持向 量 对于近似线性可分问题，即两类样本点可能有少量的融合、交叉，线性分 划造成的错分点可能较少，对这类问题仍可考虑使用线性分划，但需要对上述 方法加以改进引入松弛变量& ，i = 1 ，l ，使最大间隔分类问题归结为下述 凸二次规划问题 m ：篁i n 篙x 案i 三b 一1 3 ， s 亡 玑( ( u ) + ) 一矗 、“。7 已之0 ，i = 1 ，f 其中，c 0 是惩罚参数，用来综合间隔与错分之间的权重问题( 1 3 ) 可以通过 4 支持向量机中核函数的选取方法的研究 求解如下l a g r a n g e 对偶问题得到 ff m i n 互1 a i a j y i y j ( 甄巧) 一o t i q 。i d “= l、。j = l s t a i y i = 0 ， i = 1 0 o ，靠= 唧( 一甲2 ) i 仃 o ) ， 碍= 丽1 - 忙q s 韧丽i o q 1 ， 焉z = p 1 碍+ p 2 巧+ p 3 碍j p i 0 ， = 1 ，江1 ，2 ，3 g 其中，以称为权参数，代表着这三类- - 核1p i 函数在混合核函数中占的比重 d ，仃，口称为核参数 规则1 ：取核函数k ( z ，z 7 ) 焉霉 2 2 2选取规则2 在选取核参数之前，我们需要对多项式核函数的阶数d 及傅立叶核函数的 阶数佗做出限定二者的阶数不易过大，正如上文所述，阶数太大，二者各自 的展开项越多，不仅增加了学习模型的复杂性，易出现“过拟合现象，而且 使s v m 的推广性能降低因此，规定d ( 或n ) 的取值不超过3 规则2 ：d m i n 3 ，d i m i l 练集) ) ，n r a i n 3 ，d i m i l l 练集】) 2 2 3 选取规则3 确定了混合核函数后，核参数的选择也同样重要正如上文所分析，核参数 选取的好坏直接影响着s v m 的性能正确的核参数选择可以使s v m 恰当表征数 据的内在结构，以达到最小化结构风险的目的由于已选择的混合核函数： 酢一脚1 ( ( ) + 1 ) d + 以唧( 学卜而杀幂可丽 中的参数比较复杂，所以按照每一部分又可单独作为一个核函数的特点，把参 数选取分成两个步骤完成，即：首先，选取单一核的参数( d ，仃，q ) ；其次，选取权 参数( p 1 ，p 2 ，p a ) 下面针对( d ，盯，g ) 的选取给出规则3 ，针对( p 1 ，p 2 ，朋) 的选取给出 规则4 令p 1 = 1 ，比= 船= 0 ，相当于仅选用单一的多项式核函数，此时用下面 所给出的方法之一来选取最优的核参数d 1 3 支持向量机中核函数的选取方法的研究 方法一：已经被人们所熟悉的选取核参数的方法，主要有：预先给定参 数值；交叉验证法；网络搜索法；改进的方法，如遗传算法等 方法二：本文采用董玉林提出的平衡约束规划( m p e c ) 模型来优化选取核 参数其思想是首先给出非线性s v m 核参数优化选取的具有非光滑目标函数的 平衡约束规划( m p e c ) 模型；其次，为了方便求解该模型，给出了它的光滑化 近似模型，并且证明了原模型和光滑化模型之间的解存在一定的关系；最后给 出了光滑化模型的最优性条件及求解算法，由此即可求得最优的核参数的值 同理，令p 2 = 1 ，p l = p s = 0 ，对单一的r b f 核函数，采用同样的方法选 取最优的核参数盯： 令p s = 1 ，p 1 = , 0 2 = 0 ，对单一的傅立叶核函数，也采用相同的方法选取 最优的核参数g 据上述分析，我们得到 规贝i j 3 ：( d ，以g ) 满足：d 最优核参数d ip l = 1 ，化军船= ，o ) ，盯 最优 核参数仃i , 0 2 = 0 ，p l = p 3 = o ) ，q 最优核参数q ip 3 = l ，p l = , 0 2 = o ) 2 2 4选取规则4 将规则3 中已确定好的( d ，口，g ) 代入混合核函数后，接下来要考虑哪一类型 的核函数在混合中占主导地位，从而使得s v m 具有最优的非线性处理能力，这 取决于权参数臃( i = 1 ，2 ，3 ) 的选择当( d ，盯，口) 确定后，权参数实质上相当于混 合核函数中的核参数，可采用效仿规则3 中的方法进行选择( 即选择方法一或方 法二中的某种方法) 规贝j j 4 ( p 1 ，化，p 3 ) 满足： ( p 1 ，化，p 3 ) 最优权参数( p l ，p 2 ，p s ) i ( d ，盯，口) 按照规则3 给出) 以上4 点选取规则，仅仅为解决核函数的选取问题提供一种思路不同于传 统意义上核函数的选取方法，采用本文给出的方法来确定的核函数更具有合理 性，我们称该选取方法为r s m ( r e a s o n a b l es e l e c t i o nm e t h o d ) 方法 1 4 支持向量机中核函数的选取方法的研究 2 3 实验结果 0 ：基。“0 童蘩苫鬻1 霉耋霉；鬻 稿帮耐勰嘲滞鹂謦q 焉式如爿览刳德硝 l l i 雾菹，。魁一荔磕旌，；淑2 磊瓠，童斑。量缓。美茹熬j 实验中所使用的部分归一化后的人脸图像 为了验证本文给出的尼s m 方法选取核函数的合理性，我们利用r s m 方法 选取的核函数来解决人脸图像的识别问题，并分别与多项式核函数、r b f 核 函数进行比较，验证混合核函数的性能实验采用o r l 人脸库，此库包含4 0 人， 每人有1 0 幅不同表情的正面图像，另外脸部的光照、大小也各有差异实验中， 从o r l 库中随机选择2 0 0 个样本作为训练样本集，余下的2 0 0 个样本作为测试样 本集，进行训练和识别首先将图像的灰度值归一到【0 ，1 】区间，人脸尺寸归一 为3 2x3 2 然后，用r s m 方法选取核函数来进行人脸识别实验具体过程如下： 由选取规则1 ，我们选择混合核函数 聊，砷( x x t ) + 1 ) d + 以e x p ( 一烩笋i ) ， v 其中，k ( z ，) 刀； 由选取规则2 ，可知核参数d 的取值范围是d 3 ； 由选取规女i i 3 ，令p l = 1 ，比= 0 时，采用m p e c 模型来优化选取核参数 d ，得到最优值d = 2 ；令p 1 = 0 ，晚= 1 时，同样采用m p e c 模型来优化选取 核参数盯，得到最优值盯= 0 7 此时混合核函数具体化为 m 他州+ 助唧( 学) 由选取规则4 ，对权参数p 1 ，p z 也采用同样的方法进行选取，并得到最优 值p 1 = 0 9 ，p 2 = 0 1 由此，我们得到混合核函数为k ( z ，一) = o 9 ( o ) + 1 ) 2 + o 1 唧( 一炼笋) ， 比较结果如下表所示 1 5 支持向量机中核函数的选取方法的研究 t a b l e1 ：实验结果 核函数种类核参数识别正确率 多项式核函数 d = 2 9 4 3 r b f 核函数仃= 0 7 9 5 1 混合核函数 p l = 0 9 ，p 2 = 0 1 ，d = 2 ，o r = 0 7 9 6 2 支持向量机中核函数的选取方法的研究 3 结论与展望 目前，对核函数选取问题的研究已经逐步形成热潮以往的研究，多是选 取一些给定的核函数，研究用这些已给定的核函数的分类能力，或是仅对核 函数的性质加以讨论本文另辟蹊径，从常用核函数的特性入手，分析各自 对s v m 性能的影响和彼此的内在关系，在此基础上，提出了不同于传统方法的 核函数的选取方法一一r s m 方法 今后，仍然要考虑如何在更一般的意义下，比如根据实际问题中数据分布 的特点等背景下研究选取最优核函数的某些规律，是值得我们进一步研究的课 题对于核函数选取的研究，将是一个不断深入和不断创新的过程 1 7 参考文献 【1 】1v a p n i kv n t h en a t u r eo fs t a t i s t i c a ll e a r n i n gt h e o r y m n e wy o r k ：s p r i n g e r v e r l a g ，1 9 9 5 【2 】刘华富支持向量机m e r c e r 核的若干性质【j 】北京联合大学学报，2 0 0 5 ，1 9 ( 1 ) ：4 5 4 6 【3 】3b u r g e sjc g e o m e t r ya n di n v a r i a n c ei nk e r n e lb a s e dm e t h o d s a a d v a n c e si nk e r - n e lm e t h o d s - s u p p o r tv e c t o rl e a r n i n g m c a m b r i d g e ：m i tp r e s s ，1 9 9 9 8 9 - 1 1 6 【4 】吴涛，贺汉根，贺明科基于插值的核函数构造【j 】计算机学报，2 0 0 3 ，2 6 ( 8 ) ：9 9 0 - 9 9 6 【5 1 5s a m a r i ，s w u i m p r o v i n gs u p p o r tv e c t o rm a c h i n ec l a s s i f i e r sb ym o d i f y i n gk e r n e l f u n c t i o n s ( j n e u r a ln e t w o r k s ，1 9 9 9 ，1 2 ：7 8 3 7 8 9 【6 】齐志泉，田英杰，徐志浩支持向量机中的核参数选择问题【j 】控制工程，2 0 0 5 ，1 2 ( 4 ) ：3 7 9 - 3 8 1 【7 1 吴涛核函数的性质方法及其在检测中的应用博士学位论文，国防科学技术大学，2 0 0 3 f 8 】林茂六，陈春雨基于傅立叶核和径向基核的支持向量机性能之比较f j 】重庆邮电学院 学报，2 0 0 5 ，1 7 ( 6 ) ：1 4 【9 】s m i t sgf ，j o r d a nem i m p r o v e ds v mr e g r e s s i o nu s i n gm i x t u r e so fk e r - n e l s a p r o c e e d i n g so ft h e2 0 0 2i n t e r n a t i o n a lj o i n tc o n f e r e n c eo nn e u r a ln e t w o r k s c h a w a i i ：i e e e ，2 0 0 2 2 7 8 5 - 2 7 9 0 【1 0 】邓乃扬，田英杰数据挖掘中的新方法一支持向量机【m 】北京：科学出版社，2 0 0 4 1 1 8 - 1 1 9 【11 】d o n gy u - l i n ，x i az u n - q u a n ，w a n gm i n g z h e n g a nm p e cm o d e lf o rs e l e c t i n g o p t i m a lp a r a m e t e ri ns u p p o r tv e c t o rm a c h i n e s a t h ef i r s