（运筹学与控制论专业论文）支持向量机中fourier核的性能分析.pdf

摘要 支持向量机是二十世纪九十年代发展起来的统计学习理论的核心内容，核函数 是它的重要组成部分 实际应用中发现，f o u r i e r 核函数在支持向量机中有时也能表现出较好的性能； 其中，用f o u r i e r 核支持向量机进行分类时，参数口值的选择对支持向量机分类性能 起着重要的作用 本文讨论了f o 嘶e r 核支持向量机的性能随参数g 从o 到l 的变化规律；研究了 参数g 在两个极端情况q 一0 和g 一1 时的性质，在实际分类问题中，能为f o 嘶e r 核支持向量机参数g 的选择提供一个大概参考范围在这两种情况下，f o u r i e r 核支持 向量机的“泛化”能力会下降数值实验结果进一步论证了所得结论，并且给出了使 分类错误最小的参数g 的参考值 最后，文章采用了六组标准数据集，用来检验f o u r i e r 核支持向量机的分类能力； 对每一组标准数据进行分类，f o 耐e r 核支持向量机得到了一组最优参数( q ，g ) 以及 相应参数下的最小错分率，最后还结合g a u s s 核支持向量机的分类能力进行了对比 分析 关键词支持向量札f o 嘶e r 核函数，核函数，高斯核函数，v c 维 a bs t r a c t s u p p o r tv e c t o rm a c h i n e ( s v m ) i st l l em a i nc o n t e n to fs t a t i s t i c sl e a m i i l gt h e o 巧 d e v e l o p e d 舶m19 9 0 s t h ek e m e l c t i o ni s 血ec m c i a li n 黟e d i e n to fs v m f o u r i e rk e m e lm n c t i o ni su s e di ns u p p o hv e c t o rm a c h i n e sb e c a u s eo fi t sg o o dp r o p - e r t i e ss o m e t m l e s ，m a n ya p p l i c a t i o n sd e m o n s 锨l t em a tt h ep e r f o r m a n c eo fs v mw i t h f o u r i e rk 锄e li s 砌u e n c e dg r e a t l yb yt 1 1 es c a lp a r a m e t e rq i i lm i sp a p e r t h ea u t h o rs h o wh o wt h ep a 姗e t e r 口a 归f e c t st h e 凡n c t i o no fs v mw i t h f o u r i e rk e m e l i ti sa l s op r o v e dt h a tw h e ng _ 1 ，a l lm e 廿a i l 血gs 锄p l e sa r ec l a s s i f i e d c o n e c t l yb ys w i t hf o u r i e rk e m e l ，b u tt h es v mc a no n l yg e tac o n s t a n t 劬c t i o n w h e ng 一0 ；i nb o t hc a s e s ，s w i c hf o u r i e rk e m e lh a sl i t t i eg e n e r a l i z a t i o na b i l i 够 e x p e r i ：m e n t a lr e s u l t sv a l i d a t et h ec o n c l u s i o n l a s t ，i nt h i sp a p s i xs t a i l d a d r dd a t a sa r eu s e d c 1 a s s i f i c a t i o np r o p e n i e so fs v m w i t hf o u r i e rk e m e l i sc x a m i n e db yt h e m ，t ot h ee a c hs t a l l d a r dd a t ac l a s s i 矗e db ys v m w i t hf o u r i e rk e m e l ，也eb e s tp a r a m e t e ra n dt h el e a s te r r o rp e r c e n ta r ef o u n d t h e ya l s o a r eu s e dt 0c l a s s i 矽b ys v mw i t hg a u s sk e m e l ，h o w e v e r ，n o to n l yc a l c u l a t et h ee r r o r s p e r c e n t ，b u ta l s ob o t ho fr e s u l t sa r ec o m p a r e d k e o r d ss u p p o r tv e c t o rm a c h i i l e ， f o 嘶e rk e m e lf u n c t i o n ，k e m e lf u n c t i o n ， g a u s sk e m e lf u n c t i o n ，v cd 洫e n s i o n 学位论文独创性声明 本人所呈交的学位论文是在我导师的指导下进行的研究工作及取得的研究成 果据我所知，除文中已经引用的内容外，本论文不包含其他个人已经发表或撰写的 研究成果对本文的研究做出重要贡献的个人和集体，均已在本文中作了明确的说 明并表示谢意 作者签名：i 畚鸟 日期： 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或指定机构送交论文的电子版和纸质版有权将学位论文 用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将学位论文的 内容编入有关数据库进行检索有权将学位论文的标题和摘要出版保密的学位论 文在解密后适用本规定 学位论文作者签名：l 叁勇 导师签名： 日期：础绰日 叠垫如 期：2 碰璺巧闫 第一章引言 、，a p l l i k 等人在2 0 世纪7 0 年代建立统计学习理论的基本体系，系统研究在有限 小样本情况下的机器学习问题之后在9 0 年代，建立在统计学习理论的v c 维理论与 结构风险最小化原理基础上的支持向量机( s u p p o nv e c t o fm a c 幽e ，s v m ) 技术 1 】 能够利用有限样本提供的信息，使学习机器在模型的复杂性与学习能力之间寻找最 佳折衷，从而获得较好的推广能力 这种技术已经在手写数字识别、三维目标识别、人脸识别，文本图像分类、时 间序列预测、主成份分析等实际问题的应用中，表现出了良好的的学习能力和优于 已有学习方法的性能 2 】【3 】如今，s v i 的研究及其应用已经引起越来越多人的兴 趣和关注，成为机器学习理论和技术领域的一个新热点 核函数是支持向量机的重要组成部分，支持向量机最大特点就足引用了核函数， 对于线性可分问题，所求分类面，( z ) 只需计算样本之间的内积( 反z ，) f ，( z ) = s g n ( 9 ( z ) ) = s g n ( 玑( z 嘎) + 6 ) ( 1 1 ) i = l 而对于线性不可分样本，支持向量机通过选择一个适当的映射，把原空间上的非线性 问题转化为另一个高维特征空间上的线性问题，使得在该特征空间上所涉及有关垂 的计算及学习后的解都以圣的内积形式出现【4 ，进而引入一个核函数角( z ，可) = ( 圣( z ) ，西( 可) ) ，使得所有的计算仍在原空间中进行；此时决策函数为 l ，( z ) = s g n o ) ) = s g n ( 瓯玑( 西( z ) 西( 可) ) + 6 ) ( 1 2 ) l = l 选取q 的一个小于c 的正分量，计算得到6 = 协一轨吼( 量( 戤) 垂( 巧) ) 此时， 我们同样只需要计算新空间中样本间的内积( 圣( 玩) 圣( q ) ) ；事实上，通过讨论我们 可以知道，新空间中的样本内积( 西( z i ) 西( 。j ) ) 可以表示成原空间中对应样本的函 数后( & ，勺) ，这个函数即为核函数核函数后( z ，矽) 是一个满足一定条件的连续实值 对称函数，进一步讨论还可以知道，甚至不必明确映射的具体形式，而只要定义核函 数就可以完成分类任务 华东师范大学硕士论文支持向量机中f o u r i e r 核的性能分析 常用的核函数有多项式、s i g m o i d 核，高斯径向基核、f o u r i e r 核等；高斯核的形 式：后( z ，z ) = e x p 一监云芈) ，其中z ，z 舻是样本点，仃 o 是核半经f 。u r i e r 核函数形式有多种，其中一种一维f o u n e r 核形式： 后z ( z ，z ) = 互i r 二_ 互i 丢j 编。 q 1 ( 1 3 ) 本文主要讨论n 维f o u r i e r 核的一维形式如下： 七- ( z ，z 7 ) = 互丁r 二j ；孑三耄；。 g 1 ( 4 ) 其中z ，z 兄后l ( z ，z ) 是通过庇2 ( z ，z ) 乘上一项( 1 一q ) 所得到，这是为了证明钆 维f o 嘶e r 核性质的需要，本文第二章第二节证明了后。( z ，z ) 是一个正定核 根据一维f o u r i e r 核可以构造出扎维f o u r i e r 核，事实上，它们都是一维f o u r i e r 核的乘积：若记z = ( m ， z 】。) r ，z = ( ( z ， 1 ，【z k ) r 是样本点，则n 维f o 嘶e r 核定义为 詹( 叩7 ) = 圳z 】t ，帆) ( 1 5 ) o ，q i 犰= o ， = 1 ，2 ，z 其中，i = 1 ，2 ，f ，是每个样本对应的l a g r a n g e 乘子若a + = ( 乜：，q ? ) t 是( 2 4 ) 最优化问题解，则s v m 最后的决策函数 他) = s 印( 9 ( z ) ) = s 弘( q 酬z 嘞) + 矿) i = l f 由( 2 3 ) 的k k t 条件可知，选取q 的小于c 的正分量，计算6 = 协一玑( 翰) t = 1 通常，支持向量只占所有样本中很少一部分，它们位于分类间隔内和分类间隔上，还 包括间隔外那些被错分的点它们包括了重构分类超平面的所有信息，即使移除其 余非支持向量，仍然可以从剩余的支持向量子集中找到相同的分类超平面 2 1 2 线性不可分情形 对于线性不可分问题，s 订的核心思想就是通过一个非线性映射西，把原低维 空问上的线性不可分问题转化为一个高维特征空间上的线性可分或几乎线性可分问 题，将分类问题映射到特征空间上求解，利用与前面类似的方法，只要将公式中的z 换为由( z ) ，就可以在特征空间上得到一个分离超平面，该分离超平面对应着原空间 上的一个分离超平面由对偶优化( 2 1 ) 及决策函数( 1 2 ) 的形式知道，在特征空间上 5 华东师范大学硕士论文 支持向量机中f o u e r 核的性能分析 所涉及的有关西的计算及决策函数都以圣内积形式出现，因而可以引入一个核函 数 七( z ，可) = ( 中( z ) ，圣( 可) ) 对垂进行整体处理，从而避开了对圣的直接处理和计算，使得所有的计算仍在原空 问中进行 2 2 核函数的定义和基本性质 支持向量机的显著特点是对样本空间进行映射处理从上一节的讨论知道，只 要引入满足m e r c e r 条件的函数七( z ，秒) ( 通常称它为核函数，其中z ，可为原空间d 中 的向量) ，那么可以证明存在某个特征空间丁和从原空间d 到特征空间t 的映射圣， 使得尼( z ，y ) 就是西( z ) 和圣( 秒) 的点积 在介绍m e r c e r 条件之前首先定义积分算子死、它的特征值和特征函数，以及 积分算子的半正定性 定义2 2 1 依分算子列设输入集合为舻上的紧集x ，算子以为按下式确定 在l 2 ( x ) 上的积分算子 靠，= ( 瓦，) ( ) = 后( ，z ，( z 7 ) d z ，v ，l ：( x ) ， 其中尼( - ，) 是x x 上的连续对称函数 定义2 2 2 ( 特征值和特征函数) 考虑定义2 2 1 给出的积分算子瓦，称a 为它的特征 傀并称为相应的特征函数，如果死皿= a 定义2 2 3 ( 半正定性) 定义2 2 1 给出积分算子死是半正定的，如果对任意的， 厶z ( x ) ，有儿。x 七( z ，z w ( z ) ，( z ，) d z d z o 定义2 2 4 ( m e r c e r 核) 如果七( z ，z 。) 是定义在x x 上的连续对称函甄其中z 形 上的紧集，且由定义2 2 1 给出的积分算子是半正定的，则称函数七( z ，z ) 为拖圮 核 6 华东师范大学硕士论文支持向量机中f o u r i e r 核的性能分析 满足m e r c e r 核定义的核函数后( z ，z ) 称为m e r c e r 核，根据m e r c e r 定理，一个 半正定积分算子的任何核都可以按它的特征值九 0 和对应的特征函数t 2 ( x ) ( 1 i 霍。 | l 2 = 1 ) 进行展开，即南( z ，z ) = a 。皿。( z ) 皿。( z ) 这时奄( z ，z ) = ( 中( z ) 西( z ，) ) ，其中 圣( z ) = ( 瓜圣。( z ) ，仍。( z ) ，) t f 。 而( ) 是h i l b e r t 空间2 2 的内积 定义2 2 5 ( g 姗的矩阵) 对于给定的函数忌? x x _ 尺和z l ，动x ，称第i 行第j 列元素为惫( 翰，) 的f z 矩阵k 为函数七的关于z 1 ，购x 的g m 坍矩 阵 定理2 2 1 设x 是冗”的子集，称定义在上x x 的对称函数南( z ，z 7 ) 为一个正定 栈如果对任意的z 1 ，靓x ，七( ，) 相对于z 1 ，现的锄矩阵都是半正定 定理2 2 2 设南l 和是x x 上的核，x 舻设常数n 0 则下面的函数均是 核? 后( z ，z )= 凸七l ( z ，z ) ( 2 5 ) 尼( z ，z ) = 后l ( 。，z 7 ) 七2 ( z ，z ) ( 2 6 ) 下面证明本文第一章引言提到的式( 1 5 ) n 维f o u d e r 核七( z ，z 7 ) 是正定核 证明任意给定个有限点的集合 z - ，锄) ，七。= 夏f j 未墨意，令鲍 是七2 相对于这个集合的g r a m 矩阵： 对任意o 舻，1 一q 0 ，有 q 丁( 1 一q ) a = ( 1 一q ) q t 尬q o 所以( 1 一g ) 鲍是半正定的，因而( 1 一g ) 如是核函数由定理2 2 1 可知，( 1 一g ) 是 正定核即证明了式( 1 4 ) 一维f 0 u r i e r 核忌l ( z ，z ) 是正定核 然而，我们知道，n 维f o u r i e r 核是有限一维f o “e r 核的乘积由式( 2 6 ) 可知， 式( 1 5 ) n 维f o u r i e r 核后( z ，z ) 是正定核 口 7 第三章f o u r i e r 核函数的性质和参数 3 1f o u r i e r 核函数的性质 在实际应用中，利用支持向量机进行分类时，f o u r i e r 对某些问题具有良好的性 能和很强的学习能力，n 维f o u r i e r 核的一维形式如下： 七- ( 石，z 7 ) = 互i 工- = ：；j 毛考；，。 口 0 ，已= 0 ，v = l ，2 ，f 以及同一类样本所对应的叱相同， 当犰：1 时，a i 全a + ；当玑= 一1 时，口i 全q 一；又设：个样本点中每类样本的个数分 另0 为z + 和f 一，贝0f + + z 一= 2 首先根据汀条件的等式约束求出满足假设条件的口+ 和口一，然后验证它们 是否满足汀条件的不等式约束 1 5 】由 j q t 玑= o 爿f + q + 一f 止= o ( 3 3 ) i = 1 ( 阢( ( u 圣( 戤) ) + 6 ) 一1 + 已) ) = o = 今 6 = 协一玑后( 以，巧) ( 3 4 ) i = l 9 华东师范大学硕士论文支持向量机中f 0 u r i e r 核的性能分析 挈坍忌c z ，z ，= 孕璺垂后- cc z 】t ，k 7 】t ，= 三耋三蓁三：筹 c 3 5 ， 代入( 3 4 ) 得玑+ 6 = 玑，即 三：三二 b 6 ， 由式( 3 3 ) 和( 3 6 ) 可求得 q + = 芋，q 一= 字，6 = 竿 q + 2 广，q 一2 广，d = o 一 由于惩罚参数c 取值比较大，以保证对训练榉本的分类错误较小，所以口+ ，a 一 必满足不等式约束：a + 0 以 及已= 0 满足k k t 条件 口 定理3 1 2 当g 一0 时j 而z ，f 盯核支持向量机的学习推广能力或对新样本的正确判 别能力为零，即它把所有的样本点判为同一类 证明当q _ 0 时，f o u r i e r 核 翔坼) = 辫酚l z i 巾1 ) = ( 丢) “v 训 又由k k t 条件知，啦要满足等式：q i 玑= o 所以f 。u r i e r 核支持向量机最终所求的分类超平面是，( z ) = ( 丢) n + 6 ，由于，对某 一个给定的训练洋本集而言，它的特征个数都是确定的，即他是一个确定的数因此 厂 ) 是一个常数函数，也即把所有的样本点看作同一类 口 1o 6+ 玑 口 。曲 | | 6+zz后 玑 q 。烈 i i z g 华东师范大学硕士论文支持向量机中f o u r i e r 核的性能分析 定理3 1 1 说明了，不管训练样本个数是多少，q _ 1 时f o 嘶e r 核支持向量机几 乎能把它们正确分类定理3 1 2 表明了，g 一0 时f o u r i e r 核支持向量机对所有的样 本点看作是同一类，没有学习推广能力另外，可以看出，q 一0 和g _ 1 并不是绝对 意义上的实际l 当g 的值比训练样本点之间的距离要小得多时，就能达到口- 1 的效果；当g 的值比训练样本点之间的距离要大得多时就能达到q _ 0 的效果 3 1 2 数值实验 本节的数值实验进一步说明f o 嘶e r 核s 、r l 订随参数口的变化的规律，并验证了 上文的结论实验采用了双螺旋分布数据 1 2 ，每类2 1 个样本点，共4 2 个训练样本 点，产生8 2 个服从该螺旋分布的新样本点用于测试口取不同值时s v m 的性能，以下 训练样本也被用作测试样本，实验结果见下表1 表l取不同参数值时f o u r i e r 核s v m 的性能 f o u e r 核参数值s v 的个数 训练样本被错分数测试样本被错分数 0 9 64 2 03 3 0 94 202 0 0 84 201 5 o 6 53 40 o o 53 351 0 0 3 53 291 7 0 1 53 51 01 8 0 0 9 3 91 4 2 7 o 0 3 54 21 93 7 0 0 1 3 4 22 1 4 l 从表1 中可以看到，当g 的值接近于1 时，4 2 个训练样本点都是支持向量，且全 部被正确分类，这符合定理2 结论但8 2 个测试样本中有3 3 个被错分，即正确分类 率很低，图( o ) 表明傅里叶核s v m 出现了过学习”随着g 的值变小，支持向量( s 的个数在减少，傅里叶核s v m 在把训练样本正确分类的同时，对8 2 个测试样本的 华东师范大学硕士论文支持向量机中f 0 u r i e r 核的性能分析 分类错误率减少并趋向于零图( 6 ) 中呈现螺旋状的分类超平面表明，q = 0 6 5 时， 傅里叶核s v i 取得了比较满意的结果但是随着q 的不断减少，s 江的性能又开 始下降，出现了训练错误，且对新样本的错分数不断的增多，当口= 0 0 1 3 时，傅里叶 核s v m 得到的分类超平面是一条简单的直线，见图( d ) ，这符合定理3 结论实际上， 在g 从1 逐渐变小的过程中，傅里叶核s v m 的学习推广能力经历了由低到高又变低 的过程，分类超平面则经历了一个从复杂到简单的曲线平滑过程( 图( n ) ( d ) ) 1 2 ( n ) 口= 09 6 麟j 影，、笔篆i j 心；斓 i 镧麟阁 ( 6 ) q = o6 5 堂壅堡堇查耋堡! ：! 塞塞堡堕苎堡! 坠竺量篁丝堡堕! 堑 0 口= 0 2 华东师范大学硕士论文支持向量机中f o u r i e r 核的性能分析 3 2f o u r i e r 核参数的选择 对于给定的样本，支持向量机的性能主要受核函数和误差惩罚参数c 的影响， v a p n i k e 等人研究表明：支持向量机的性能与所选用的核函数的类型关系不是很大， 而核参数和误差惩罚因子c 是影响支持向量机性能的主要因素 3 2 1v c 维理论和结构风险最小原则 在模式识别问题中，评价一个函数的好坏，首先要给出一个标准所以需要引入 期望风险这个概念： 定义3 2 1 设p ( z ，y ) 为x y 上的概率分布jc 为给定的损失函耗再设， ) 是一 个假设佚策函刘，则，( z ) 的期望风险r ，】全l 。yc p ，y ， ) ) 妇( z ，可) 其中c 常 用0 1 损失函数? c c z ，可，c z ，= ；萎圣2 厂z 期望风险的大小可以直观地理解为：当我们用假设，( z ) 进行预测时，“平均”的 损失程度或“平均”的犯错误程度它是用来评价某假设，( z ) 优劣的一个数量指标 于是，我们的任务就是在一个函数集 ，( z ，) ，q a ) 中，求出一个最优参数a o ，使 得某一个函数，( z ，o o ) 的期望风险最小但实际上p ( z ，) 通常是未知的，因此无法 求出r 【门但是可以注意到，我们已知训练集，所以能够计算出，( z ) 在这些样本点上 的偏差，这就引出了经验风险的定义： 定义3 2 2 设给定训练集t = ( 甄，肌) ) cx v xc 舻， 】厂= ( 一1 ，1 ) ，i = l ，2 ，2 ，并给定损失函数c 则厂( z ) 的经验风险? r 。唧 门= c ( 犰，m t ) ) 统计上常用经验风险最小化归纳原则作为对兄 月的估计即在适当选定的集 合fc ，：x y ) 中选择使r m p ， 最小的假设，但是，强调经验风险最好而忽 1 5 华东师范大学硕士论文支持向量机中f o u e r 核的性能分析 视对f 的选择是不可行的假设f 是包含所有，的假设集，则 厂c z ，= _ ? 冀暑2 毛。= 1 2 2 也在f 中，且这个假设的经验风险满足见唧 门= o ，显然此时，是经验风险最小的 假设，但我们把它作为决策函数显然是不妥当因此我们要适当缩小假设集f ，而f 的大小或者说它的丰富程度即是由v a p r 此等人在建立统计学习理论中提出的v c 维 定义3 2 3 对于一个指示函数集，如果存在 个向量能够被函数集中的函数以所有 可能2 的种方式分离，则称函数集能够把j 1 1 个向量安类分离，函数集的阳维就是函 数集能按类分离的最大向量数厅如果对任意数目的向量都有函数可以把它们按类 分离，则函数集的比维是无穷大 v c 维是影响学习机器推广性能的指标，同时也是函数集复杂度的度量v c 维 反映了函数集的学习能力，v c 维越大，学习机器越复杂经验风险的大小还不足以完 全判断假设，的优劣，于是v a p l l i k 指出了期望风险与经验风险之间的关系，即推广 性的界 定理3 2 1 记五是假设集f 的阳维，若训练样本数z ， ( 1 n 凳+ 1 ) + h l 昙 砉，则对于任意概率分布p ( z ，) 和任意6 ( o ，1 】，f 中的任意假设，都可使下列不 等式至少以1 6 的概率成立? r 【，】r 。p 门+( 3 7 ) p 7 1 j 式可以简写为以下形式? 础】见唧+ 圣( 孚) ( 3 8 ) ( 3 8 ) 式右侧第二项称作置信范围，它随h 的增加而增加；右侧两项之和称为结 构风险从( 3 8 ) 式可以看出，在v c 维较大时，学习机器较复杂，即使经验风险很小， 也无法保证期望风险兄 ，】较小，即无法保证系统有较好的推广性；只有当v c 维与 16 华东师范大学硕士论文支持向量机中f o u r i e r 核的性能分析 训练集的规模的比值较小，期望风险r ，】才能够比较小因此，学习机器的推广能力 不但与经验风险有关，而且和学习机器的复杂性有关；要得到一个推广性能较好的学 习系统，需要在v c 维和训练集的规模间达成一定的均衡基于此，引入结构风险最 小化原则( s t u c n l m l 砌s km i i l i m i z a t i o n ，s 砌哪我们必须在一个给定的函数集中使风 险最小化，这要通过控制经验风险和置信范围的值来完成 有两种最小化不等式( 3 8 ) 右边的构造性方法：一种是先确定一个v c 维为某 个矿的容许函数集，在学习过程中使机器最小化经验风险；神经网络首先确定网络 结构，这相当于确定了学习机器的置信范围，然后按经验风险最小化原则训练，这就 实现了第一种方法第二种是保持经验风险固定并最小化置信范围，支持向量机实现 了第二种方法统计学习理论中的以下定理说明了支持向量机最小化了v c 维的上 界，即最小化了置信范围的上界 定理3 2 2 在d 维空间中，设所有样本分布在一个半径为r 的超球范围内，则满足条 件1 1 2 c 的规范化超平面形成的分类面函数集，( z ，u ，6 ) = s g n z ) + 6 ) 的比 维满足下面的界 l i n ( r 2c 】，d ) + 1( 3 9 ) o 由定理3 2 2 可知，使忪1 1 2 最小就是使v c 维的上界最小；而分类间隔等于高， 使间隔最大等价于使怕i | 2 最小，实际就是对置信范围的控制因此，最优分类面和广 义最优分类面就是把分类函数集s = z ) + 6 ) 按照其权值的模( 线性可分情况 下就是按照分类间隔) 分成了若干个规范子集，每个子集为 吼= z ) + 6 ) ：j j u 2 “ 对于线性可分的情况，最优分类面就是在固定经验风险为0 的前提下寻求置信范围 最小的规范化子集；而在线性不可分情况下，广义最优分类面则是在控制错分样本的 情况下使置信范围最小因此支持向量机算法得到的( 广义) 最优分类面在期望风 险的界的意义上是最优的，是结构风险最小化原则的具体体现 3 2 2 支持向量机的核参数选择与结构风险最小原则 支持向量机的决策函数是特征空间中的一个线性函数，尽管特征空间的维数可 1 7 华东师范大学硕士论文支持向量机中f o u r i e r 核的性能分析 f 能很大，但是，通过u = q i 玑西( 魏) 可得 i = 1 ，cz，=sgncut西cz，+6，=sgnccq-，q。，a。【兰 这时的决策函数八功可看作由【兰 z 1 ) z 2 ) 貌) + 6 1 三专构成的z维空间t上的线性指示函 数而且我们已知几维空间上线性指示函数集的v c 维是n + 1 ，因此，支持向量机的 决策函数的v c 维往往小于2 + 1 所以，支持向量机的v c 维和特征空间的维数并没 有必然的关系，而是与空间t 的维数存在密切的关系 由于核函数到特征空间的映射是一一对应，因此，不同的核参数就相当于决定了 映射之后的不同的空间r 通过上面的讨论知道，空间丁的维数决定了能在此空间 构造的线性分类面的最大v c 维，也就决定了线性分类面能达到的最小经验误差同 时，每一个空间t 对应唯一的推广能力最好的分类超平面，如果空间丁的维数很高， 则得到的分类面就可能比较复杂，经验风险小但置信范围大，反之经验风险大但置信 范围小由( 3 8 ) 可知，这两种情况下得到的支持向量机都不会有很好的推广能力因 此，需要选择合适的核函数和核参数，使得映射后的空间r 有合适的维数 综上所述，支持向量机的核参数决定空间丁，而空间t 的维数与支持向量机 的v c 维密切相关，所以核参数的选择与v c 维密切相关，同时也影响着支持向量 机的结构风险另外，惩罚参数c 的作用是在确定的特征空间中调节学习机器置信 范围和经验风险的比例使学习机器的推广能力最好，不同特征空间中最优的c 不同 在确定的特征空间中，c 的取值小表示对经验误差的惩罚小，学习机器的复杂度小而 经验风险值较大，称为欠学习”；反之称为过学习”每个特征空间至少存在一个合 适的c 使得支持向量机推广能力最好当c 超过一定值时，支持向量机的复杂度达 到了上文提到的空间t 上允许的最大值，此时的经验风险和推广能力几乎不再改变 另外，惩罚参数没有出现在对偶形式第一式中，而只是改变了l a g r a n g e 系数的取值 18 华东师范大学硕士论文支持向量机中f 0 u r i e r 核的性能分析 范围，所以，对于一个支持向量机，如果无限增大惩罚因子，当支持向量机中没有边界 支持向量时，c 的改变不会影响分类性能 目前普遍使用的是尼折交叉确认法具体方法是：把个样本点随机分成后个互 不相交的子集，即后一折s l ，岛，鼠；每个折的大小大致相等共进行尼次训练与测 试，即对最，i = 1 ，2 ，七进行次迭代，第i 次迭代的做法就是选择s 为测试集，其 余研，& 一l ，& + 1 ，瓯的和集为训练集，算法根据训练集求出决策函数后，即可 对测试集& 进行测试【1 1 【1 3 记其中错误分类的样本点个数为f 七，七次迭代完成后， 七 七如 即得到了z 1 - k 所有七次迭代中错误分类数f 和总样本数z 之比三i - 做为算 法错误率的一个估计，该值称为尼折交叉确认误差 在实际中，后常有两种取法：第一种是取七= f ，此时，每次迭代留下一个样本 点作为测试点，因此又称为留一法( 1 e a v e 一彻e 一0 u t ，简称l o o ) 由它计算的误差也称 为l o o 误差；l o o 误差是期望风险的一个几乎无偏估计，是对支持向量机推广能力 的估计 1 4 第二种是取七= 1 0 ，这样就得到1 0 折交叉确认误差虽然1 0 折交叉 确认与留一法相比，计算量已减少了很多，但对数据量较大的样本集而言，仍旧需要 很大的计算量因此人们致力于寻找l o o 误差的一个尽可能小的上界其中，支持 向量计数法就是l o o 误差上界的评估方法之一它是对支持向量机中支持向量的 个数进行计数根据支持向量机和l o o 的原理，只有在所有样本上训练得到的支持 向量才可能在留一法测试时产生错误如果该样本进行留一法训练时，分类面不会 改变，用该样本进行测试日寸，它仍正确地分类间隔外，不会产生错分所以，若令2 是 训练样本总数，是支持向量的总数，那么l o o 误差满足r l o o ( t ) ； 1 9 第四章f o u r i e r 核在支持向量机中的应用 上章讨论了f o 嘶e r 核参数的选择，主要是依据v c 理论，通过控制经验风险 和v c 维数使得上界达到最小值；用支持向量机对某训练佯本进行分类，在选择参数 的时，可能有这两种情况发生：第当选择了一组参数对训练样本进行分类，这时的 经验风险很低，但v c 维很大；第二选择另一组参数对训练样本进行分类时，经验风 险很古 但v c 维很小当这种问题发生时，采取哳。衷的方法处理 1 0 4 1 标准数据集简介 以下采用了u c i 数据库( h t t p ： ) l n ) l m i c s u c i e d u m l e a n l m l s l 姗m a h t m l ) 中 的p i i l l a i n d i a n s d i a b e t e s 、b a l a n c e s c a l e 、b r e a s t c a n c e r - w i s c o n s i n 、i r i s 、t i c - t a c t o e 和w a 、，e f o n i l 六个标准数据集来测试f o u d e r 核支持向量机的分类能力 1 7 p i m a i n d i a n s d i a b e t e s 数据集是关于女性糖尿病和肾脏疾病，是一个2 类问题，特 征变量个数是8 ；b a l a n c e s c a l e 数据集产生于一个用天平测量左右两边物体的重量 和距离的物理实验模型的结果，是一个3 类问题，特征变量个数是4 ；b r e a s t c a j l c e r w i s c o n s i n 数据集是有关乳腺癌的，是一个2 类问题，特征变量个数是1 0 ；i r i s 数据集 包含了3 类，每一类有5 0 个样本，每一类都代表一种鸢尾植物，有一类与其它两类是 线性可分，但是那两类之间是非线性可分；t i c t a c t o e 数据集是把这个t i c 也c t o e 游戏 可能涉及到的配置情况完全编译出来的结果所组成，是一个2 类问题，特征变量个数 是9 ；w a v e f o m 数据集是一个包含噪声的波形，是一个3 类问题，特征变量个数是2 1 表2 中数据集的命名都采用原标准数据集的头一个英文单词，其中多类问题都 选取两类作为实验对象，数据集的说明如下表2 2 0 华东师范大学硕士论文支持向量机中f o u r i e r 核的性能分析 表2 标准数据集 训练样本数测试样本数 数据集类别数 样本总数特征变量个数 ( 一+ )( 一+ ) p 蛐a 27 6 81 0 0 1 0 04 0 0 1 6 88 b a l a n c e36 2 51 0 0 1 0 0 1 8 8 1 8 84 b r e a s t26 9 9 1 0 0 1 0 03 4 4 1 3 91 0 m s 31 5 01 7 1 73 3 3 34 t i c29 5 81 0 0 1 0 05 2 6 2 3 29 w a v e f b m l35 0 0 01 0 0 1 0 0 1 5 5 7 1 5 4 72 l 4 2 实验过程说明及结果分析 实验中参数口从0 变化到1 ，步长取0 1 ，惩罚参数c 的选取是1 0 ，l 的取值范 围在l 到3 之间，步长为1 表3 的第一列足数据集，第二列是f o u r i e r 核函数对应每 一组标准数据分类的最优参数( 口，c ) ，以及相应参数下的最小错分率( e n 0 rp e r c e n t ) ； 第三列是g a u s s 核函数对应每一组标准数据分类的最优参数( 盯，c ) ，以及相应参数 下的最小错分率( e r r o rp e r c e n t ) ；使得在最小错分率的情况下，对比了两种核函数的 分类能力，并进行了分析实验结果如下表3 表3 实验结果 f o u r i e rk 锄e 1 g a u s sk e r n e l d a t as e t ( g ，c ) e r r o rp e r c e n t ( 口，c ) e r r o rp e r c e n t p m l a ( 0 8 6 ，1 0 2 ) 3 3 5 4 ( 1 0 0 一，1 0 2 ) 2 3 3 6 b a l a n c e ( 0 0 8 ，1 0 3 ) 3 1 9 ( 1 0 1 ，1 0 3 5 ) 1 9 1 5 b r e a s t ( o 9 5 ，1 0 3 ) 6 4 2 ( 1 0 2 ，1 0 4 ) 4 3 5 m s ( 0 1 5 ，1 0 2 ) 3 0 3 ( 1 0 0 ，1 0 2 ) 4 5 5 t l c ( 0 8 8 ，1 0 3 ) 1 4 2 5 ( 1 0 1 ，1 0 4 ) 2 8 7 6 w a v e f b n i l ( 0 0 5 ，1 0 2 ) 1 1 6 0 ( 1 0 2 ，1 0 5 ) 1 1 9 5 2 1 华东师范大学硕士论文 支持向量机中f o u r i e r 核的性能分析 从以上表格3 中的结果可以看出，f o u r i e r 核支持向量机对一些数据集分类效 果比较好对于p i n l a 数据集，f o 嘶e r 核支持向量机的分类效果比g a u s s 核支持向 量机差；但是，对于第四行的数据集b a l a i l c e ，f o u r i e r 核持向量机的错分率是3 1 9 ， 而g a u s s 核支持向量机的错分率是1 9 1 5 ，还有第七行数据集t i c ，f o 嘶e r 核持向量 机的错分率是1 4 2 5 ，而g a u s s 核支持向量机的错分率是2 8 7 6 ，所以，f o 血e r 核 持向量机对这两类标准数据集的分类效果明显比g a u s s 核支持向量机的分类效果要 好然而，对于数据集b r e a s t 、i r i s 和w a v e f o 衄，f o u r i e r 核持向量机与g a u s s 核支持向 量机的分类效果几乎差不多，没有明显的差别 2 2 总结与展望 文章首先是引入支持向量札对它进行了线性可分和非线性可分两种情况进行 阐述，在线性不可分的情形下，通过把低维的线性不可分空间映射到高维的线性可分 空间 在线性可分的高维空间，引入了内积这个概念，使得在高维空间的计算通过内积 的形式转化到原低维的空间进行计算，进而简化了计算量，使支持向量机能在现实 中得以应用通过内积的运算引出了核函数这个概念，其实核函数的种类很多，本文 主要讨论了f o u r i e r 核函数，研究了f o 嘶e r 核支持向量机的分类能力随f o u r i e r 核参 数q 变化而变化的规律q 的变化范围是从0 到1 ；然后，通过v c 维理论和结构风险 最小化原则，对支持向量机参数选择的重要性做了说叽并对f o 嘶e r 核参数g 和惩 罚参数c 进行选择 通过对六组标准数据集进行分类实验，对每一组标准数据，f o 埘e r 核支持向量 机得到一组最优参数( g ，c ) ，以及相应参数下的最小错分率使得在错分率最小的情 况下，f o 面e r 核支持向量机与g u a s s 核支持向量机相比，f o 谢e r 核支持向量机对b a l a n c e 和t i c 数据集的分类效果明显比g u a s s 核支持向量机要好当然，本文只是对用 了这六组标准数据集来验证f o u r i e r 核支持向量机的分类能力，肯定有它的片面性和 局部性 最后，由于f o u r i e r 核函数和g u a s s 核函数的对训练样本有局部化能力 1 8 】，但 是对b a l a n c e 和t i c 数据集，为什么f o u r i e r 核支持向量机分类效果会比g u a s s 核支持 向量机要好? 这个问题还有待于继续深入进去，考虑能否用理论来证明 2 3 参考文献 【1 邓乃扬、田英杰，数据挖掘中的新方法一支持向量机，科学出版社，2 0 0 4 年 2 】v 印n i kvn t l l en a t l 鹏o fs t a d s t i c a ll e 姗i 1 1 9t l l e o r y m 】n e wy o r k ：s p 血g 昏v e r l a g ， 1 9 9 5 ：11 5 3 】nc r i s t i a n i n i ，js h a w e y a y l o r a 且i n 昀d u c t i o nt os u p p o r tv e c t o rm a c h m e sa n do t h e r k 锄e l - b a s e dm e t h o d s c 锄b r i d g e ：c a m b r i d g eu l l i v e r s i t yp r e s s ，2 0 0 0 4 l c h m j 锄f o 咖1 l l a t i o no fs u p p o r tv e c t o rm a c h i n e s ：an o t e 舶m 加0 p t i m i z 撕o np o i i