（计算机应用技术专业论文）若干svm算法的改进与设计.pdf

摘要 传统支持向量机( s v m ) 是通过一个凸二次规划求解的，并有较好的泛化能力，已 经在生物信息学、人脸识别、指纹识别、手写体识别、数据库学习与身份验证等领域得到 了较好的应用。 以统计学理论为基础，本文重点研究了支持向量机核函数的构造、支持向量机快速训 练算法、支持向量机训练集剪辑技术等内容。 本文所做的主要工作如下： 1 设计了一个泛化能力与学习能力折中的混合核函数k d 。与传统r b f 核相比，基于 k p 下的s v m ，其支持向量个数少、分类性能好。 2 提出了一种新的支持向量分类算法一一a c n n s v m ，主要为了解决n n s v m 算 法并不能保证在训练集上找到最少需要的原型样本点集的缺陷。 3 求解两个权向量，无需求解超平面的具体形式，针对g e p s v m 可能存在奇异性 问题，提出了权向量多平面支持向量机w m p s v m 。该方法不仅可以纠正某些情况下 g e p s v m 错分问题，而且避免了g e p s v m 奇异性问题。 4 将类内散度的思想融合到p s v m 分类器设计中，提出了p p s v m 。该方法保证了 较优的分类精度和好的学习速度。然后，对p s v m 优化问题中的约束条件进行修正，提 出了f p s v m 算法。由于训练过程中避免了一些矩阵的相乘及矩阵本身计算代价，故能提 高p s v m 的学习速度。 关键词：支持向量机；泛化能力；训练算法；剪辑技术；权向量；类内散度 a b s t r a c t c o n v e n t i o n a ls u p p o r tv e c t o rm a c h i n e ( s v m ) s o l v e sc l a s s i f i c a t i o np r o b l e mb yac o n s t r a i n e d q u a d r a t i cp r o g r a m m i n gp r o b l e m , a n dh a sg o o dg e n e r a l i z a t i o na b i l i t y m o r e o v e r , i th a sb e e n u s e di ns o m ef i e l d ss u c ha sb i o i n f o r m a t i c s ，f a c er e c o g n i t i o n , h a n d w r i t i n gr e c o g n i t i o n ， f r i n g e r p r i n tr e c o g n i t i o n ，d a t a b a s el e a r n i n g ，i d e n t i f i c a t i o nv a l i d a t i o na n d s of o r t h t h i sp a p e rb a s e do ns t a t i s t i c a lt h e o r yl a y se m p h a s i so ns o m er e s e a r c h e so i lc o n s t r u c t i o no f k e r n e l s ，o nf a s tt r a i n i n gs v ma l g o r i t h m sa n do nc r o p p i n gt e c h n i q u e so ft h et r a i n i n gs e to f s v m t h i sp a p e rm a i n l yc o m p l e t e st a s k sa sf o l l o w s ： 1d e s i g nam i x t u r eo fk e r n e l ( ) t h a tc a l lb a l a n c eb e t w e e nt h eg e n e r a l i z a t i o na b i l i t ya n dt h e l e a r n i n ga b l i l i t yb a s e do ns v m c o m p a r e d 研t hc o n v e n t i o n a lr b fk e r n e l ，t h en u m b e ro f s u p p o r tv e c t o r so fs v m b a s e do nk pi ss m a l l e r , a n d 、 ，i t i lb e t t e rc l a s s i f i c a t i o np e r f o r m a n c e 2p r o p o s ean e wc l a s s i f i c a t i o na l g o r i t h mb a s e do ns u p p o r tv e c t o r - - - - - - a c n n s v mt o o v e r c o m et h ef l a wt h a tn n s v mc a nn o tg u a r a n t e ei to b t a i n st h el e a s tn e e d e da n t e t y p es a m p l e p o i n t s 3p r o p o s ean o v e la l g o r i t h mi nt h i sp a p e r ：w m p s v ma i m i n gt oo v e r c o m et h es i n g u l a r p r o b l e m sa p p e a r i n gi ng e p s v m i td o e sn o tn e e dt os o l v es p e c i f i ct w oh y p e r p l a n e sb u t g e p s v md o e s m o r e o v e r , i tc a nc o r r e c tt h em i s c l a s s i f i c a t i o np r o b l e mw i t hg e p s v ma ts o m e c a s e s ，a n da v o i ds i n g u l a rp r o b l e m sa p p e a r i n gi ng e p s v m 。 4p p s v mi sp r o p o s e do nt h eb a s i so fw i t h i n c l a s ss c a t t e r t h i sa l g o r i t h mg u a r a n t e e sg o o d c l a s s i f i c a t i o np e r f o r m a n c ea n d l e a r n i n gs p e e d ，a n dt h e na n e wp s v ma l g o r i t h mc a l l e df p s v m i sc o n s t r u c t e db yr e f o r m u l a t i n gt h eo p t i m a l i z a t i o np r o b l e mi np s v m c o m p a r e d 丽t 1 1p s v m ， p p s v mh a sb e t t e rl e a r n i n gs p e e d t h i si ss ob e c a u s ei tc a l la v o i dt h ec a l c u l a t i o no fs o m e m a t r i c e sa n dt h em u l t i p l i c a t i o no fs o m em a t r i c e sa n do t h e ro n e s k e y w o r d s ：s u p p o r tv e c t o rm a c h i n e ；g e n e r a l i z a t i o na b i l i t y ；t r a i n i n ga l g o r i t h m ；c r o p p i n g t e c h n i q u e ；w e i g h tv e c t o r ；w i t h i n c l a s ss c a t t e r 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下进行的研究工作 所取得的成果。尽我所知，除文中已经特别注明引用的内容和致谢的地方外，本 论文不包舍任何其他个人或集体已经发表或撰写过的研究成果对本文的研究做 出重要贡献的个人和集体，均已在文中以明确方式注明并表示感谢本人完全意 识到本声明的法律结果由本人承担。 黼撕( 枞触业吼呷艿月 学位论文版权使用授权书 日 本学位论文作者完全了解南京林业大学有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版( 中国科学技术 信息研究所；国家图书馆等) ，允许论文被查阅和借阅本人授权南京林业大学 可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以汇编和综合 为学校的科技成果，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论 文全部或部分内容 保密口，在j 解密后适用本授权书本学位论文属于禾保密0 ( 请在以上方框内打“ ” ) 学位论文作者( 本人签名) ： 指导教师( 本人签名) ： 必乃农 业骞 q 1 1 1 月月 么 竹下 致谢 即将毕业，终于熬过两年。回想过去，一人在实验室煎熬度过的痛苦的暑假，不禁有 点辛酸。但痛苦过后也能感觉到少许的欣慰，因为并不是空手而归。这两年我也得到了许 多人的帮助。 首先，应该感谢的是我的导师业宁副教授。业老师从我入学开始就开导我，向我指明 了研究方向。起初的我，由于对理论研究缺乏了解，极度讨厌理论、讨厌数学，在这种情 况下，业老师还是虚心教诲，变换方式地激发我的研究乐趣。他不但向我传授个人的丰富 经验，而且教我做人的道理，鼓励我申请2 0 0 8 研究生科技创新项目和2 0 0 8 南京林业大学 科技创新项目并申请成功。衷心祝福业老师全家健康幸福。 感谢数学系的陈艳男、计算机系杨绪兵老师，在我撰写论文遇到困难的时候给予的帮 助。感谢我的师弟张召、王语辉，师妹催静、胡睫在我繁忙的时候帮我处理一些事务。感 谢武波同学平时对我的照顾。我还要感谢在起愉快度过两年时间的舍友们，正是你们的 帮忙以及对我的理解，使我顺利地完成了博士入学考试，我才能克服困难和疑惑，直至本 文的顺利完成。 感谢我的家人，无论我做什么样的选择，无论我遇到什么困难，一如既往地对我的支 持和肯定。也感谢我的女朋友，在日常生活中对我的照顾，对我未来抉择的支持与理解。 在论文即将完成之际，我的心情无法平静，从我踏入研究生学习生活后，有多少可敬、 可爱的人给予了我莫大的帮助，在这里，我真诚地祝福这些帮助过我的人一辈子幸福、安 康。 第一章绪论 1 1 支持向量机及国内外研究动态 传统的统计模式识别方法只有在样本趋向无穷大时，其性能才有理论上的保证。统计 学习理论表明，学习机器的实际风险由经验风险值和置信范围值两部分组成。在进行机器 学习时，传统的统计模式识别方法强调经验风险最小化，而基于经验风险最小化准则的学 习方法只强调了训练样本的经验风险最小误差，没有最小化置信范围值，因此会产生“过 学习问题”，其推广能力较差。 针对传统统计模式识别方法推广能力的不足，v a p n i k 1 j 等人提出了支持向量机 ( s u p p o r tv e c t o rm a c h i n e ，s v m ) 方法。 s v m 是建立在结构风险最小化准则之上，以训 练误差作为优化问题的约束条件，以置信范围值最小化作为优化目标，其推广能力明显优 于一些传统的学习方法。目前，已经在生物信息学、人脸识别、指纹识别、手写体识别、 数据库学习与身份验证等领域得到了较好的应用。 传统的s v m 问题是通过一个凸二次规划求解的，它不适合求解大规模问题，主要是 因为在求解过程中需要存储一个很大的核矩阵，例如，当训练集中样本个数达至u 4 0 0 0 的时 候，它需要1 2 8 m b 的内存；另外，传统s v m 还牵涉到大量的计算，这也花费大量的训练 时间。针对s v m 训练时间代价大的问题，j p l a t t 提出了贯序最小优化算法( s e q u e n t i a l m i n i m a lo p t i m a l i z a t i o n 简称s m o ) f 3 】。该方法将选择的子工作集的样本个数设为2 ，即每 次迭代过程中只调整相应两个样本点的l a g r a n g e 乘子，它只是求解一个具有两个变量的最 优化问题。由于使用了精确的解析解形式，从而避免 o s u n a 的分解方法【2 】中非常费时的 数值求解方法，该算法特别适合于稀疏样本的求解。p l a t t 将s m o 同投影共轭梯度法 ( p c g ) 进行了比较，对于u c i 中的a d u l t 数据库，s m o 比p c g 快1 5 0 0 倍。k e e r t h i 5 j 对 s m o 3 】做了进一步的改进，使用两个阈值以减少迭代次数，得到了比s m o 更快的算法。 其后很多人都对s m o 算法进行了深入的研究，并作了一些有益的改进。在s m o 和k e e r t h i 改进的s m o 算法中【5 j ，只使用了两个乘子进行优化，往往使得一次优化后的乘子数据在下 一循环优化时被大量的改变，从而引起振荡，使得收敛时间变长。业等人提出了一种多乘 子协同优化的s v m 快速学习算法( m l s v m 4 ) 4 1 ，该方法能同时使用多个拉格朗日乘子 协同优化，更精确地确定t l a g r a n g e 乘子值，从而减少了迭代次数，提高了训练速度。在 u c i 上m l s v m 4 的速度要比s m o 快上3 - 4 2 倍以上1 4 j 。 但目前仍然没有算法能有效地解决s v m 训练时间过长的问题。鉴于此，研究学者们 提出了很多新的支持向量机算法，如s l m c ( b u i l d i n gs p a r s el a r g em a r g i nc l a s s i f i e r s ) p 引、 r s v m ( r e d u c e ds v m ) 【1 3 】、c v m ( c o r ev e c m rm a c h i n e ) 【j 引。另外，m a n g a s a r i a n 等人在2 0 01 提出了近似支持向量机分类器( p s v m ：p r o x i m a ls u p p o r tv e c m rm a c h i n e ) 。该方法通过求 解线性方程，并结合s h e r m a n m o r r i s o n w o o d b u r y ( s m w ) 【1 2 】等式对高维矩阵进行降秩， 来提高训练速度。例如，对于u c i 中选取的3 2 5 6 2 个样本的a d u l t 数据库，基于线性核下 s m o 需要大概1 6 3 6 秒，m l s v m 4 需要6 9 5 秒1 4 j ，s v m l i g h t t 3 7 】需要2 1 8 4 秒，而p s v m 仅需 要7 4 秒的时间【1 2 1 。例子中说明，p s v m 的速度远远好于其他三个算法。 随p s v m 之后， m a n g a s a r i a n 等人在t p a m l 2 0 0 6 上提出了基于广义特征值下的近似支持向量机( g e p s v m ： p s v mv i ag e n e r a l i z e de i g e n v a l u e s ) 1 2 6 j 。该方法不仅能有效地解决异或问题，而且有较 好的训练速度( 主要求解两个广义特征值问题) 。 为了提高s v m 的分类速度，学者们提出了多种剪技术。它们主要对s v m 训练集修 剪，以得到较少的支持向量数目。随后，有学者继续对现存的修剪算法不断的改进，如 m a n g a s a r i a n 等人提出的r s v m 0 s 算法，在此之后l i n t 4 0 】等人对其又做了改进。同样，在 2 0 0 2 年，李等人发表了一篇题为“一种改进的支持向量机n n s v m ”的文章l l 引。由于它 并不能保证能找到最少需要的原型样本点集，所以该算法还有很大的改进空间。在对 n n s v m 研究基础上，业等人提出了一种新的支持向量分类算法( a c n n s v m ) 【4 2 j ，只 保留了最近邻修剪后的训练样本集中样本到超平面的距离差小于给定的阈值的样本，故可 以减少s v m 的支持向量个数以及分类时间。 美国w i s c o n s i n 大学m a n g a s a r i a n 领导的小组在s v m 算法上做出了很多突破性的成就， 尤其在提高传统s v m 的训练速度上。他们先后在( ( k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g 、 ( ( j o u r n a lo f m a c h i n el e a r n i n gr e s e a r c h ) ) 和m a c h i n el e a m i n g 等一流的国际期刊上发 表了很多高质量的学术论文。针对s v m 训练时间代价大的问题，他们提出了l s v m ( l a g r a n g i a ns u p p o r tv e c t o rm a c h i n e s ) 1 3 3 】、s s v m ( as m o o t hs u p o r tv e c t o rm a c h i n e ) 【4 1 1 、 a s v m ( a c t i v es u p p o r tv e c t o rm a c h i n ec l a s s i f i c a t i o n ) m j 和p s v m 算法。这些算法主要是利用 s h e r m a n - m o r r i s o n w o o d b u r y ( s m w ) 等式的性质来提速的。s m w 等式求解的时间复杂度 是q , m ) ( m 是样本个数，”是维数) 【3 1 1 ，空间复杂度是o ( m n ) 3 1 】，而传统支持向量机的 训练时间复杂度是o ( m 3 。5 ) 1 4 】，空间复杂度是o ( m 2 ) 3 1 】。很明显，利用s m w 等式的s v m 算法的速度要远快于传统的s v m ，并且内存占用要少于传统的s v m 。但是，在非线性问 题中，l s v m l 3 3 j 、s s v m 4 1 和a s v m l 3 4 却不能利用s m w 的等式优越性质，故它们只能解 决小规模问题，并保证较好的训练速度。直至l j m a n g a s a r i a n 等人提出约减s v m ( r s v m ) 之后，s m w 等式在非线性问题中不可用的问题才得到了解决，并在最接近支持向量机 ( p s v m ) 中得到应用。与以s m w 等式为基础、通过迭代求解的a s v m 和l s v m 等算法 不同，p s v m 分类器仅需求解一个线性方程组。但是，基于r s v m 技术下的p s v m 也存在 一些不可避免的缺陷。l i n 和s c h o l k o p f 等人分别在i e e et r a n s a c t i o n so nn e u r a l n e t w o r k s ) ) 【j 刿和 m a c h i n el e a r n i n gi n t e r n a t i o n a lw o r k s h o pt h e nc o n f e r e n c e ) ) 4 0 j 发表的两 篇文章上指出，运用r s v m 所得到的分类性能是不稳定的，也许会得到较差的分类性能。 并且，p s v m 得到的拉格朗日乘子正比于松弛变量，即u = c ，故丧失了稀疏性。 2 0 0 6 年，m a n g a s a r i a n 等人在i e e et r a n s a c t i o n so np a _ t t e ma n a l y s i sa n dm a c h i n e i n t e l l i g e n c e ) ) 上发表了一篇文章：m u l t i s u r f a c ep r o x i m a ls u p p o r tv e c t o rm a c h i n ec l a s s i f i c a f i o n v i ag e n e r a l i z e de i g e n v a l u e s ( g e p s v m ) 。与传统的s v m 相比，该算法能很好地解决异或问 题，并且有更快的训练速度。但是，该算法存在如下缺陷：( 1 ) 可能存在奇异性问题，以至 于计算过程中存在精度误差：( 2 ) 在某些情况下存在严重错分问题。另外，与p s v m 相比， g e p s v m 的训练速度比p s v m 要慢，这主要由于g e p s v m 需要求解两个广义特征值问题。 2 0 0 6 年，针对g e p s v m 多类问题，杨等人在计算机研究与发展提出t m h p s v m t 4 6 】 2 算法，但是，该方法在求解非线性问题的时候，也存在奇异性问题。2 0 0 7 年，杨等人又在 计算机学报上发表了一篇文章：局部化的广义特征值最接近支持向量机( l g e p s v m ) 【4 7 1 。该算法主要是针对某些情况下g e p s v m 错分问题而提出的。该算法比较复杂且不直 观，训练时间代价远远大于g e p s v m 。 s v m 另外一个研究热点是核函数的选择问题。s v m 解决原始空间线性不可分的问题， 般是通过核函数将原始空间样本映射到高维特征空间中，使样本在高维空间中线性可 分。因此，核函数的好坏直接影响到s v m 分类器性能的优劣。核理论的m e r c e r 定理可以 追溯至u 1 9 0 9 年【4 引，再生核h i l b e r t 空间的研究在1 9 世纪4 0 年代被a r o n a z a j i n 发展m j 。而运用 m e r c e r 定理把核解释成一个h i l b e r t 空间中内积这一思想，则首先是1 9 6 4 年被a i z e r m a n ， b r a v e r m a n 和r o z o e n e r 等人在机器学习领域引进的，但是，直至u b o s e r ，g u y o n 和v a p n i k 在文 献 5 0 】中运用这个思想，人们开始理解其含义。迄今，关于核函数的研究有很多( 如文献 【2 7 【3 0 】中，可以看到相关核的构造技巧) 。这些核函数主要分为局部核函数、全局核函 数，它们要么学习能力不好，要么泛化能力不足【1 0 1 。大多数的核函数选择方法是在特定 的应用领域内针对不同的应用环境，通过实验分析来解决。核函数的选择与构造仍是一个 亟待解决的难题。为了缓解局部核函数与全局核函数不足，近年来，研究人员越来越注重 混合核函数的研究。在文献 1 0 1 2 】中指出，r b f 核函数学习能力好、泛化能力不足，而 p o l y 核泛化能力好学习能力不足。为了构造泛化能力与学习能力折中的混合核，许多研究 人员对p l o y 核函数和r b f 核函数进行非负线性组合，如文献【1 2 】 1 3 】。我们知道，如果把 核函数问题转化为具体核矩阵的问题来处理，这样，构造混合核函数就变得比较直观并且 易于处理了，但是，很少学者从核矩阵角度出发直接构造混合核。 1 2 本文工作任务 在对s v m 国内外研究状况进行分析的基础上，作者对传统的s v m 算法做了些改进 与设计，本文重点工作任务如下： 设计了基于极分解下的混合核函数 在模式分类问题中，无需知道核函数的具体形式，只要知道样本在高维空间中存在的 相似关系，即：只要知道样本之间的内积关系。因此，可以把核函数问题转化为核矩阵的 问题来处理【7 】【4 5 1 ，这样，模式分类问题就变得比较直观并且易于处理了。另外，在传统的 核函数中，r b f 核是局部函数，多项式核是全局函数，而局部性核函数学习能力强、泛 化性能较弱，全局性核函数泛化性能强、学习能力较弱，因此可以考虑把这两类核函数混合 起来【1 0 】。基于学习能力与泛化能力的两者考虑，我们利用矩阵能极分解生成一个对称半 正定矩阵的特性，对r b f 核进行极分解，并结合多项式核，构造了一个性能优越的混合 核函数。在u c i 数据库中的几个数据集上进行实验，采用基于极分解下的混合核，与r b f 核进行比较，使用该核函数的s v m ，其支持向量的个数少、分类错误低m 】。 提出了一种新的支持向量分类算法a c n n - s v m 文献1 1 4 提出的n n s v m 算法并不能保证得到原型样本点集。李等人在电子学报 上提出的k s v m 【3 2 1 ，是通过求解样本点到s v m 超平面的距离再结合k 近邻算法对s v m 进行分类的。他们对s v m 分类时错分样本的分布进行分析发现，s v m 分类器出错样本 点都在分界面附近，这就提示了s v m 分类面附近样本信息与分类性能有关。这也说明， 分类错误的样本往往在分类面附近，而离分类面较远的样本点可以通过某种准则从训练集 中删除，即：对训练集约减。鉴于此，本文将点到平面距离的思想( 可以删除远离分类面 的样本点) 融于n n s v m 算法中，对其再一次约减，可达到对n n s v m 得到的最近邻修 剪集再次约减的目的。其思想是：先对训练样本集进行最近邻修剪，用s v m 训练得到 一个s v m 模型，然后，计算最近邻修剪后的训练样本集中样本到超平面的距离，如果距 离差大于给定的阈值则将其从最近邻修剪后的训练样本集中删除，最后对再修剪后的样本 集用s v m 训练得到一个最终的s v m 模型。实验发现，该算法不仅能够得到较少的支持 向量个数，还有较快的分类速度。 设计了权向量投影多平面支持向量机( w 佃s v m ) 平面型g e p s v m 分类器，不仅能保证较好的学习速度，也能较好地求解异或( x o r ) 问题，它通过求解r a y l e i g h 商问题，而不是传统s v m 凸规划问题获得s v m 解。然而， 该方法还存在很多的缺陷：在样本维数较高和求解非线性问题时，往往存在奇异问题。针 对g e p s v m 缺陷，在本文中，通过定义新准则，提出了一个新的快速的算法：权向量投 影多平面支持向量机( w m p s v m ) 。与g e p s v m 相比，w m p s v m 有以下优势：1 ) 每个 不平行分类面是通过求解简单特征值问题获得；2 ) 避免了奇异性问题；3 ) 有与g e p s v m 相当的学习速度；4 ) 测试精度与g e p s v m 相当甚至更好；5 ) 可以缓解在某些数据分布 下精度恶化的缺陷。最后在人工数据集与u c i 数据库上得到了验证。 提出了两个基于近似支持向量机( p s v m ) 的改进算法( p p s v m 、f p s v m ) 运用s h e r m a n m o r r i s o n - w o o d b u r y ( s w m ) 等式【3 3 j 【3 4 心j ，将一个研m 矩阵求逆运算 问题转换为对一个n x ，z 矩阵求逆运算问题( n 一 一 五 一丑 而 k d = m = v d v t 然后通过两个加权系数a 和b 来构造混合核函数 k o , = a k p o t y + b k 甜 ( 2 6 ) ( 2 7 ) 并且满足m e r c e r 条件。式中的为全局的多项式核函数，口，b 做这样的确定：a 6 1 且a 1 ，f l 越大混合核k p 推广能力越强。确定仍b 这两个加权系数，我们将在下节做些分 析。 2 2 2 加权系数的确定 对于局部核函数r b f 来说，其曲线函数如图2 1 所示，在测试点附近小领域内的数 据点的核函数值受影响。因此，径向基核是一个局部性的核函数。在图2 1 中，分别 把点0 0 、0 1 、0 2 、0 3 作为测试输入，核参数g a m m a 取0 5 ，这样的测试便于求出下 面要介绍的极分解核的曲线。我们把测试输入的几个值设为输入样本为，x 2 ，玛，_ ，那我们 就可以得到r b f 对应的四维核矩阵 k = 石i l x 2 i x 3 l x 工l2 x 2 2 x 32 x l 2 x l3 x 2 3 x 3 3 x x l x 2 x 3 x ( 2 8 ) 式( 2 8 ) 中的k 中的元素薯是核函数中样本对对应的函数值，而每行上的四个值分别对 应图2 1 中t e s t 0 ，t e s t 0 1 ，t e s t 0 2 ，t e s t 0 3 曲线上的四个点。易知，对k 极分解后得到的核矩 阵也有同样的特性，即可以得到极分解核屹的曲线，如图2 2 所示。图2 2 中可以看出 不同测试点下的如曲线波动比较大，通过图2 1 和图2 2 比较，可以看出如的内推力 较r b f 核内推力要大，因此，匕核在学习能力上较r b f 核的学习能力好，但其泛化能力 弱【1 2 】【1 3 】。 图2 1 不问测试点下函数r b f 的曲线圈2 2 不同测试点下的曲线 7， 两个核函数的加权系数a ，b 对核函数的性能有很大的影响。鉴于多项式核中阶数p 越 小，外推力越强【1 2 1 ，取p = j ，点0 2 作为测试输入，g a m m a = 0 5 ，先求得口= 1 ，b = 1 这种 混合核下的曲线，如图2 3 所示。 图2 3a = l ，b = l 混合核下的曲线图2 4a = 3 ，b = 2 下k o p 曲线 从图2 3 可以看到，在a = j ，b = j 的混合核下它的推广性能并不是很好，其实，它也是 一个局部核函数。如果一条曲线能一直保持一定的上升趋势，那它便可以允许相距很远的 数据点都可以对核函数的值有影响i l 引，从而提高了推广能力。加大多项式核( 全局核函 数) 的权系数a ，显然使得多项式核曲线在y 轴向上移动，这样外推力加强，从而加大了 分类器的推广能力【1 2 儿1 3 j 。k ，核的权系数b 尽量比a 小，因为，当b 增大后，原k 核曲 线同样上移，从而内推力减弱了【1 2 j 【l 引。一般来说，在s v m 中，推广能力加强，会导致学 习能力下降，鉴于推广力与学习能力的折中考虑，不能让k d 核曲线上移的幅度过大，从 而保证了其学习精度与学习性能。 综上分析，保证k 的曲线向上移动的幅度不能过大，多项式核k p 。l y 曲线向在y 轴向 上移动的幅度大，这样，既保证了核的学习能力，同时保证了核的泛化能力。即：我们对 核的权系数a ，b 做这样的确定：a b 1 且a 1 ，a ，b 越大混合核瓦。推广能力越强。取 a = 3 ，b = 2 ，在测试输入点o 2 ，0 3 下所构造的混合核的曲线，如图2 4 。显然，从图 2 4 中的k p 曲线能够看出，疋。内推力明显比图2 1 中的k 册f 内推力要弱，但其外推力 要比k 。f 的外推力要强，基于泛化能力与学习能力的一种折中考虑，提出的核疋。既保证 了很好的泛化能力，又保证了好的学习能力。 2 3 实验结果与分析 实验都用s v m q p ( q u a d p r o g ) 算法来说明。对训练数据及测试数据进行归一化到区 间 一1 ，+ 1 上。实验中的数据都是随机抽取的。我们分别对u c i 中的几个数据集进行不同 方式的分类实验，进行和r b f 性能比较。 2 3 1 实验1 我们用c e m e n t 数据进行实验。这是个多类问题，我们用两类问题来处理它。每一 类数据都取3 0 个样本作为训练集，共2 1 0 个训练数据，把数据集的第一类作为正类，其 8 他类的样本都作为负类，而测试数据都是随机抽取的。为了更好的比较，在不同的核参数 仃下选用c e m e n t 数据对两类问题进行实验，测试次数为1 0 次，在每段伊上随机抽取 不同的测试样本：仃在0 0 1 - - - 0 1 取1 8 0 0 个，盯在0 1 1 0 取1 5 0 0 个，仃在5 o 1 5 取1 2 0 0 个。取a = 3 ，b = 2 ，取多项式参数p = 1 。s v m 测试错误率见表2 1 。图2 5 是表2 1 数据所体现的r b f 与分类精度变化趋势。 表2 1k 衄f 与在不同仃下的分类结果 c 时n 舯t 纨a 基 l | 二曼罂l二 ? b 搿、。 一 一 l ； ，! ，d 飘 ： _ 一一 j 渺一 、。 弋拦 、 - o 叫 a 嘲n m 图2 5 不同仃下的k 胼与& 分类精度图 从表2 1 中我们可以看到，随着仃以及测试样本数量的变化，基于疋。的s v m 分类 错误率很小、支持向量个数也很少。从图2 5 中更直观的可以看出，其分类正确率在任何 时候都高于k 。r p ，仃的变化时，基于r b f 的s v m 分类正确率的波动起伏不定，而 所体现的分类正确率从核参数g a m m a = 0 0 5 开始都保持很好的精度，并且随仃的增大，其 分类正确率都保持一个平稳状态，从而抑制了局部核函数r b f 所引起的预测输出波动。 且在不同的核参数g a m m a 下疋。的支持向量个数少于k 船f 。 9 2 3 2 实验2 为了进一步的说明基于极分解下的混合核k 。性能的优越性，再用与实验1 不同方法 对i r i s 数据集进行分类实验。同样把i r i s 数据集作为两类问题来处理，第三类( v i 类) 的样本都作为正类，其它类别的样本全作为负类，每类取前1 5 个样本，共4 5 个样本作为 训练样本。盯取值我们分为5 个区间：0 0 0 1 - 0 1 ，0 2 - - 0 5 ，0 6 - - 1 2 ，2 1 0 ，1 1 1 0 0 。 在进行分类实验时，在5 个区间上，仃取的个数相同。在进行5 次，1 0 次以及1 5 次分类 实验时，分别取测试样本的个数为1 5 0 ，1 0 0 ，8 0 。取口= 3 ，b = 2 ，取多项式参数尸= 1 。分 类结果如表2 2 。 耋! ：! 墨跹皇茎衄坌耋笙墨 ! ! 且匝! ! 厶 分类测试样 错分样本支持向量错分样本支持向量 次数本数 平均数平均数平均数平均数 从表2 2 中同样可以看到，三种不同的测试次数，r b f 核下的分类精度分别为 8 6 6 7 ，9 7 ，9 8 7 5 ，b 下的分类精度分别为9 7 3 3 ，9 8 ，1 0 0 。在不同的核参数g a m m a 下k 的支持向量个数少于k 胼，且分类精度没有大幅度的变动，即：如分类精度稳定 性要比k 泖高，该混合核有效地抑制局部核函数k 眦所引起的预测输出波动。 2 3 3 实验3 用a b a l o n e 数据集进行实验。该数据集共4 1 7 7 个数据，分为m 、f 、i ( i n f a n t ) - 一类， 共有8 个属性( 该数据下载地址：h t t p ：a r c h i v e i c s u c i e d u m 1 ) ，我们取1 2 0 0 个样本作为 训练集，每次测试都从1 2 0 0 个样本中随机抽取3 0 0 个样本作为训练样本；剩下的样本作 为测试集。在不同的核参数仃下选用a b a l o n e 数据对两类问题进行实验，测试次数为l o 次，在每段仃上随机抽取不同的测试样本：仃在0 0 1 - 0 1 取1 8 0 0 个，仃在0 1 - - 1 0 取2 0 0 0 个，仃在5 o 1 0 取2 6 0 0 个。不同a 值下的s v m 分类效果见表2 3 、表2 4 。 室! 曼垒三i ：垒三! ! 墨衄e 皇坠坌鲞堕墨 测试 茎耻 一茎理 样本仃正确分类样 支持向量正确分类支持向量 本平均率平均数样本平均率平均数 o o l6 8 3 9 9 93 0 06 8 4 0 0 0 1 8 0 00 0 5鹋3 2 6 42 9 16 7 7 7 8 0 1 0 2 9 0 2 7 9 0 1 2 0 0 00 5 1 o 5 o 2 6 0 0 l o 6 6 3 8 踺 6 8 2 7 1 4 6 8 3 6 0 i o 6 9 2 8 0 2 6 9 2 0 7 7 2 8 9 2 9 5 2 9 6 3 0 0 3 0 0 6 5 4 1 6 0 6 8 7 7 1 4 6 8 6 8 0 盯 6 9 3 8 4 6 6 9 3 1 5 4 2 7 3 2 8 7 2 8 7 2 3 壅! ：! 璺三! 竺：垒三兰! 茎逝皇墨理坌耋堑墨 测试样 茎压盆e 筌篮 本 仃 正确分类样支持向量正确分类样支持向量 本平均率平均数本平均率平均数 从表2 3 与表2 4 中可以看出基于k 胼下的s v m 精度并没有什么波动，其精度都是 一个平稳的状态如在这种数据库下同样可以得到较k 阱还好的分类精度，并且其分类精 度同样没有大的波动。表2 3 、表2 4 中当o - = 5 0 的时候，k 脚下的s v m 能得到最好的 分类精度( 约为6 9 3 ) ，但同g a m m a 参数下的k 所体现出来的分类精度( 约为6 9 6 ) 要高于置料，且在不同的核参数g a m m a 下如的支持向量个数都少于k 狮。 2 3 4 实验4 用h i l l - v a l l e y 数据集进行实验( 该数据下载地址：h t t p ：a r c h i v e i c s u c i e d u m 1 ) 。该数 据集为2 4 2 4 个1 0 1 维向量的集合，每个向量还带了一个类标，共两类。选取6 0 6 个样本 作为训练集，剩下的1 8 1 8 个样本作为测试集每次测试从6 0 6 个样本中随机抽取5 0 0 个 样本作为训练样本集，从1 8 1 8 个样本中随机抽取1 0 0 0 个样本作为测试样本集，测试次数 为1 0 次，分类结果如表2 5 、表2 6 。 壅! ：! ! 望：垒墨! 茎五距皇墨叩坌鲞笙墨 ! ! 出征! ! 让 盯 正确分类样支持向量正确分类支持向 本平均率平均数样本平均率量平均数 o 0 0 4 05 2 1 3 3 3 5 0 0 5 5 8 3 3 34 9 5 0 0 0 6 05 1 7 0 0 0 5 0 0 5 5 5 3 3 34 9 4 1 l o o l o o o 0 5 0 0 0 1 0 0 0 o 5 0 0 0 1 0 0 0 0 5 0 0 0 0 1 0 0 0 0 5 6 0 7 1 4 5 4 4 0 0 0 5 1 6 0 0 0 5 4 o o o o 5 1 4 5 0 0 5 2 0 4 0 0 4 9 8 4 0 0 5 0 0 5 0 0 5 0 0 4 9 9 5 0 0 5 0 0 5 0 0 5 5 1 2 8 6 5 6 2 0 0 0 5 6 5 0 5 6 9 5 0 0 5 9 3 8 3 3 6 1 5 8 5 9 3 0 本平均率平均数本平均率 平均数 从表2 5 和表2 6 中可以看出k 无论是在泛化性能还是在学习速度上都优于r b f ， 并且表2 6 中也体现了k 的泛化性能随口的增大而增强，并且下的s v m 的支持向量 也随口增大而相对减少了。 表2 7 h i l l - v a l l e y 上k 脚，与k 肋训练误差比较结果 ” 赡 虬 盯 盯 如 4 4 4 4 4 4 4 一 盯 一 表2 8 a b a l o n e j 2 k 肼，- q k 南训练误差比较结果 表2 9 m l b a l c n d _ j 亡，k 肼，与k 础训练误差比较结果 我们从表2 7 、表2 8 和表2 9 中可以看到，k 。，下的s v m 学习能力并不理想，都 远远低于e 。与r b f 。比如在m l b a l c n d 数据集上r b f 、k o v ( a = 3 ) 与k o p ( a = 7 ) 最好的训练 误差分别是0 2 ，o 和0 ，而k 枷，下s v m 的最好训练误差是4 1 7 ，比r b f 、k 。( a - 3 ) 与疋。( a = 7 ) 训练误差分别多了4 1 2 、4 1 7 和4 1 7 还进一步发现，k o p 下的s v m 训 练误差与r b f 下s v m 训练误差相仿所以，疋。在保持了较r b f 还好的泛化能力的同时 也保持了好的学习能力。 2 4 本章小结 s v m 的核函数选择一直是研究的热点，找到一个合适的核函数能提高模式识别的能 力。传统的核函数基本划分为局部核函数与全局核函数两类，它们都各有利弊，要么泛化 能力不好，要么学习能力不足。构造同时满足这两个条件的核函数是s v m 分类研究领域 的难点。从实验中我们