（管理科学与工程专业论文）基于脉冲核的支持向量机研究与应用.pdf

人连理工大学硕士学位论文 摘要 数据挖掘作为信息管理领域的一个重要研究课题，其技术已经f “泛地应用到很多行 业中。作为新生代的数据挖掘技术支持向量机( 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 年代提出的。由于依据结构风险最小化原则，s v m 较好地解决了小样 本、非线性、商维学习问题，成为了当前数据挖掘领域和机器学习界的研究热点。虽然 目前已经形成了一套完整的理论框架，但是s v m 在处理一些实际问题时，其性能仍显 不足，围绕核心算法展开的理论和应用的深入研究仍在继续。通过改进训练算法、提出 全新算法、核函数构造和参数选择等途径的研究，以进一步提高s v m 的推广性能和学 习速度。 本文在介绍了s v m 的相关基础知识之后，以构造满足m e r c e r 条件的核函数为核心， 对s v m 的性能做了一些研究和探讨，主要工作包括： 1 针对目前可供s v m 选择的m e r c e r 核较少的情况，借助于f o u r i e r 变换知识，提 出了一种基于f o u r i e r 变换的核函数构造方法。经过理论证明，运用该方法构造的核函 数同样满足m e r c e r 条件，可以作为核应用于s v m 的学习过程。同时依据该方法，给出 了一个构造实例。以脉冲函数为基础，构造了脉冲核并对其参数性质作了简要探讨。通 过u c i 标准数据集的实验，表明在保证推广能力基本不变的前提下，基于脉冲核的s v m 训练得到的支持向量数普遍少于基于r b f 核的s v m 的训练结果。 2 虽然依据脉冲核的s v m 训练得到支持向景集容量较小，这在一定程度上提高了 预测阶段的效率，但是针对规模较大的问题，s v m 仍存在学习速度下降的缺点，因此 本文提出了一种基于卫向量的简化s v m 算法模型，在保证预测精确性的前提下，进一 步对s v m 算法进行了改进，使得改进后的s v m 更适合求解大规模问题。 3 由于近年消费信贷的升温，信贷机构需要对借款者的信用进行尽可能准确地评 估，针对一些已有评估方法的不足，考虑到s v m 预测技术对数据样本的分南特征没有 限制，同时理论上又有较好的推广能力，本文最后将基于脉冲核的改进s v m 模型应用 于个人信用评估中，对个人信用评估的过程进行了简要探讨，为发展个人信用评估技术 提供了一种新途径，同时也为信贷机构的信贷发放提供了决策依据。 关键词：支持向量机；f o u r i e r 变换；脉冲核；卫向量；个人信用评估 基于脉冲核的支持向域机研究与麻用 s t u d ya n da p p l i c a t i o no fs u p p o r t v e c t o rm a c h i n eb a s e do np u l s ek e r n e l a b s t r a c t d a mm i n i n ga sa j li m p o n a ma r e ao fi n f o r m a t i o nm a n a g e m e n tf i e l d ，t h et e c h n o l o g yh a s b e e nw i d e l ya p p l i e dt om a n yi n d u s t r i e s s u p p o r tv e c t o rm a c h i n e ( s v m ) w h i c hi san e wd a t a m i n i n gt e e l - m i q u e i sp r e s e n t e di nt h e1 9 9 0 sa sf o rs t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e ， s v mh a sab e t t e rs o l u t i o nt os m a l ls a m p l e ，n o n l i n e a r ，h i g h - d i m e n s i o n a ll e a r n i n gp r o b l e m s a sah o ts t u d ya r e a ，a l t h o u g hs v mh a sf o r m e dat h e o r e t i c a lf r a m e w o r k ，i t sp e r f o r m a n c e n e e d st ob ei m p r o v e dj na d d r e s s i n gs o m ep r a c t i c a lp r o b l e m s s ot h ed e e pr e s e a r c ho ni t s t h e o r ya n da p p l i c a t i o ns t i l l c o n t i n u e s i no r d e rt oi m p r o v i n gs v m sg e n e r a l i z a t i o na n d l e a r n i n gs p e e d ，m a n yw a y ss u c h a s i m p r o v i n ga l g o r i t l m l ，p r o v i d i n gn e wa l g o r i t h m ， c o n s t r u c t i n gn e wk e m e la n dc h o o s i n gs u i t a b l ep a r a m e t e r sa r en o wl s e a r c h i n g a f t e ri n t r o d u e i n gs o m eb a s i cs v m k n o w l e d g ei nt h i st h e s i s m o r ed e e pr e s e a r c ht ot h e p e r f o r m a n c eo f s v mi sd o n et h em a i ni o bi sf l sf o l l o w ： 1 u n d e rt h es i t u a t i o nt h a tt h em e r c e rk e r n e l su s e di ns v ma r eaf e w f ln e wr i l e t h o di s p r o v i d e dt oc o n s t r u c t i o nm o r ek e r n e l su s e df o u r i e rt r a n s f o r mt h e o r y w ec a np r o o ft h a tn e w k e r n e lw h i c hi sc o n s t r u c t e db yt h i sm e t h o da l s om e e tm e r e e rc o n d i t i o n t h e nan e w p u l s e k e r n e li sc o n s t r u c t e da n di t sp r o p e r t yi sa n a l y z e d e x p e r i m e n tt ou c id a t as e t ss h o w sr e s u l t t h a tt h en u m b e ro f s u p p o r tv e c t o r sg o tf r o ms v mh a s e do nt h en e wm e r o e rk e r n e l j si e s st h a n g o tf r o ms v mb a s e do nr b fk e r n e l ，b u tt h eg e n e r a l i z a i o ni sa l m o s tu n c h a n g e d 2 l e s sn u m b e ro fs u p p o r tv e c t o r sg o tf r o ms v mt r a i n i n gb a s e do nt h ep u l s em e r e e r k e r n e l ，t h i sc a ni m p r o v ec l a s s i f ys p e e d b u ti ft h et r a i n i n gs e ti sl a r g e r , t h el e a r n i n gs p e e do f s v m 、v i l lb es l o w e r i no r d e rt oo v e r c o m i n gt h i sd r a w b a c k as i m p l es v mm o d e lb a s e do n g u a r dv e c t o ri sp r o v i d e d w i t lu n c h a n g e df o r e c a s ta c c u r a c y t h i sm o d e li sm o r es u i t a b l et o s o l v i n gl a r g es e a l ep r o b l e m 3 a sc o o s u l n e rc r e d i tw a r m i n gi nr e c e n ty e a r s c r e d i ti n s t i t u t i o n sn e e dt oc o n d u c ta b o r r o w e r sc r e d i ta s s e s s m e n ta s a c c u r a t e l ya sp o s s i b l e s o m ee x i s t i n gm e t h o d sc a od ot h i s ， b u td a t ad i s t r i b u t i o ni sr e s t r i c t e d d i m r e n tw i t ht h i s s v mc a ns o l v ep r o b l e mw i t h o u ta n y r e q u e s tt od a t ad i s t r i b u t i o n s of o r n a e rm o d i f i e ds v mm o d e li su s e dt ot h ep e r s o n a lc r e d i t e v a l u a t i o n + i tp r o v i d e san e ww a yt od e v e l o pe v a l u a t i o nt e e h n i q u ea n da l s oi t p r o v i d e s r e f e r e n c et oe r e d i ti n s t i t u t i o n sw h e nt h e ya r ed e c i s i o nm a k i n g 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 ；f o u r i e rt r a n s f o r m ；p u l s ek e r n e l ；g u a r dv e c t o r ； p e r s o n a lc r e d i te v a i n a t i o n 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 人连理 ，人学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 导师签名 垄兰彭 望笙 型年立月堕臼 大连理l 大学硕七学位论文 1 绪论 1 1 研究背景和意义 计算机技术和信息网络的迅猛发展宣告了信息时代的到来，这个时代的重要特征就 是人们有了更多的机会和便捷的手段接触到大量数据。超量数据时刻充斥着网络和生 活。它们将在生产和生活中发挥巨大作用，因此人们投入了大量资源去收集和存储数据。 而实际情况中由于数据量太大，很难对其进行高效管理，或者由于数据结构太复杂，很 难对其进行有效分析，所以这些海量数据只有一小部分在发挥作用，大量潜在的高价值 信息仍没有被挖掘出来，这就出现了“数据爆炸，信息匮乏”的现象。 对大型、复杂、信息丰富的数据集的理解实际上是政府、企业、科研领域的共同需 要。在政府机构中，很多政策、法律、法规的制订都要有数据信息作为依据；在商务领 域，公司和顾客的数据都被认为是一种战略资产；在科研领域，研究者们既从数据中寻 找规律又在用数据检验规律。这就要求对数据有深刻地理解，传统的数据库技术和数据 分析方法已难以满足他们的要求。如何从海量数据中快速挖掘出有用知识，己成为信息 时代一个十分紧迫而富有挑战的研究课题。数据挖掘( d a t am i n i n g ) 技术就是在这样的背 景下应运而生的。 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取和发现隐 含在其中的人们事先不知道的，但又是潜在有用的信息和知识的过程。它是涉及机器学 习、统计学、模式识别、人工智能、数据库管理及数据可视化等学科的边缘学科。从统 计观点看，它是通过计算机对大量复杂数据集的自动探索性分析。数据挖掘面对的是初 步加工后的数据，更专注于知识发现。在实践中，数据挖掘有两个基本目标预测和 描述。预测涉及到使用数据集中的些变量预测其他所要关心的变量的未知值；描述关 注的则是找出描述可由人类解释的数据模式。因此，可以把数据挖掘活动分成两类：预 测性数据挖掘和描述性数据挖掘。预测性数据挖掘是得出一种模型，以可执行码表示， 它可以用于执行分类、预测以及评估等任务；描述性数据挖掘是利用大型数据集中的未 知模式和关系获得对所分析系统的理解。 数据挖掘作为信息管理领域中的一项重要技术，被认为具有广阔的发展前景。由于 海量数据的出现，对数据挖掘的应用形成极大的需求，使这一技术迅速得到了发展和完 善。仅在美国就有数百家公司开发出了数据挖掘的相关产品，如s p s s 、s a s 、a c c r u e 等。数据挖掘技术已在电信业、金融业、生物医学、零售业等多个行业中取得了广泛地 应用。人们可以运用该技术发现新消费者的购买倾向、设计投资战略和在会计系统中探 基于脉冲核的支持向量机研究与廊 h 测未经认可的开支，增加销售业务等。总之，数据挖掘技术以广泛应用于客户关系管理、 市场趋势预测等管理领域，为管理者进行决策提供了高价值的信息依据1 2 j 。 基于数掘的机器学习方法是数据挖掘技术中的重要方面，它研究从样本数据出发寻 找规律，利用这些规律对未来数据或无法观测的数据进行预测。现有机器学习方法共同 的理论基础之一是统计学。传统统计学研究的是样本数目趋于无穷大时的渐近理论，但 在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法在实际表现中 却可能不尽人意。v a p n i k 等人从2 0 世纪6 0 年代开始致力于统计学习理论( s t a t i s t i c a l l e a r n i n gt h e o r y ，s l t ) 方面的研究 3 i ，随着其理论的不断发展和成熟，也由于神经网络 等学习方法在理论上缺乏实质性的进展，统计学习理论开始受到越来越广泛的重视。 支持向量机( s u p p o r t v e c t o r m a c h i n e ，s v m ) 作为数据挖掘的一项新挣未，是2 0 世纪 9 0 年代中期在统计学习理论基础上发展起来的一种新型机器学习方法。它集成了最大间 隔超平面、m e r c e r 核、凸二次规划、稀疏解和松弛变量等多项技术，在处理高维、非线 性问题时具有独特的优势。神经元网络等现有的机器学习方法都是依据经验风险最小化 原则( e m p i r i c a lr i s km i n i m i z a t i o n ，e r m ) 提出的，并且网络结构的确定必须依靠经验， 当样本数目较小时，会出现“过学习”和“推广能力下降”的情况和容易陷入局部极小 点等缺点。s v m 依据结构风险最小化原则( s t r u c t u r a lr i s km i n i m i z a t i o n ，s r m ) ，能有效 解决上述问题。因此，它成为继神经网络研究之后机器学习界新的研究热点。美国科学 杂志评论：s v m 以及核学习方法被认为是“机器学习领域非常流行的方法和成功的例 予，并是一个十分令人瞩目的发展方向”。s v m 从提出和被广泛重视到现在只有几年 的时间，其基础理论已基本成熟，并己构建成s v m 的整个理论框架，但是还有很多尚 未解决或尚未充分解决的问题，在应用方面的研究也才刚刚开始，所以s v m 是一个值 得深入研究的领域。 1 2 研究现状 2 0 世纪7 0 年代，前苏联学者v a p n i k 开始致力于统计学习理论研究 3 1 。 1 9 8 1 年， 他与c h e r v o n e n k i s 联合提出了s v m 的重要基础理论_ v c 维理论【4 】。1 9 8 2 年，v a p n i k 进一步提出了具有划时代意义的结构风险最小化原理，它被称为s v m 算法的基石1 5 】。 时隔十年，又相继产生了最大化间隔分类器【6 】和非线性最大间隔的分类问题 w 。1 9 9 5 年， v a p n i k 完整地提出了s v m 理论框架【8 】，标志着对该技术的研究已发展成为机器学习中 一个独立的子领域，同时也成为数据挖掘的一种新方法。 大连理工大学硕士学位论文 由于s v m 算法的潜在应用价值，很多学者在理论上对其进行了深入研究。9 0 年代 之后取得了诌多突破性进展，许多改进的和新型的s v m 算法以及关于s v m 中核方 法研究都相继产生。 ( 1 ) 改进的训练算法 ， ， v a p n i k 于1 9 9 8 年提出了对标准c - s v m 中的目标函数进行改进，将当改为等， z 1i = 1 ， 使得在求解其对偶问题时，将c 变为核函数的一个参数例。同时在文献。1 中讨论了等 酉 的情况，当k = l 时，即为c - s v m 算法。 由于考虑到c - s v m 算法中的参数c 只是作为惩罚参数，表示最少错分样本和最大 分类间隔的折衷，缺乏直观意义，所以在实际应用中很难选取合适的值。s c h o l k o p f 和 s m o l a 提出了v s v m 算法，即用参数v 取代c 。v 用于控制支持向量的数目和误差， 具有实际意义，它表示间隔错误样本的个数所占总样本个数份额的上界，又是支持向量 个数所占总样本个数份额的下界。在训练过程中，易于选择。 为了保证决策函数的唯一性，m a n g a s a d a n 等学者提出了在目标函数中增加一项 1 i b 2 ，这种改进使得在求解对偶问题时少了不等式约束，口= 0 ，而只有关于边界的约束 2 0 口c ，由此得到的算法简称为b s v m 算法 l 引。该算法的优点是适合迭代求解，同 时应用矩阵分解技术，每次只需更新l a g r a n g e 乘子的一个分量，不需将所有样本载入内 存，从而提高了收敛速度。 由于v s v m 的复杂性，不适合于求解大规模问题，因此f r i e s s 提出了在v s v m 算 1 法中融入b s v m 算法的优点，即在原目标函数中加入一项6 2 ，由此得到了b v - s v m 2 算法【1 3 】，实验结果表明该算法具有较好的性能。 s u y k e n s 等学者于1 9 9 9 年提出了最小平方s v m ( l e a s t s q u a r es v m ) i l 4 1 ，在目标 函数中使用平方误差，同时将不等式约束改为等式约束，从而将二次规划问题转变成线 性方程组求解，降低了计算的复杂性。 l e ey t 和m a n g a s a r i s a n 提出的s s v m ( s m o o t hs v m ) 1 1 5 。该算法通过对目标函数的 变型，在算法执行中，每次循环仅优化1 个点即可，可以处理上千万个样本的大规模问 题。此外还有s s k e e r t h i 的n p a ( n e a r e s tp o i n ta l g o r i t h m ) 算法【l “、c h e wh o n g g u n n 的 w s v m t l7 1 、r o o b a e r t 的d s v m t l 8 1 算法等。 基于脉冲核的支持向量机训f 氕l j 戍h f 2 1 针对大规模问题的求解 支持向量的求解过程最终转化为一个二次规划问题，它的复杂度与训练样本数的平 方有关。- ! 1 i j l l 练样本增多时，二次寻优过程要进行大量的矩阵运算，这不仅需要占用大 量的内存窄问，同时使训练速度大大降低。所以如伺训练大规模数据集成为s v m 实际 应用的瓶颈。由于s v m 算法在求解二次规划过程中，具备解的稀疏性和最优化问题的 凸性等优点，这为有效处理大规模问题的s v m 提供了可能。处理这类问题的一个共同 特点就是将原始的大规模问题分解为若干个小规模的子问题，按照某种迭代策略，反复 求解子问题，进而构造出原问题的近似解，并使该近似解逐渐收敛到原始问题的最优解。 b e m h a r d 提出的块处理算法( c h u n k i n ga l g o r i t h m ) 1 1 9 1 。它的思想是将样本集分成工 作样本集和测试样本集，每次对工作样本集利用二次规划求得最优解，剔除其中的非支 持向量，并用训练结果对剩余样本进行检验，将不符合训练结果( 一般是指违反k k t 条 件) 的样本与本次结果的支持向量合并，成为一个新的工作样本集，然后重新训练。如 此重复下去，直至获得最优结果。块算法的一个前提是：支持向量的数目比较少。然而 如果支持向量的数目本身就比较多，那么随着训练迭代次数的增加，工作样本数也越来 越大，就会导致算法无法实施。 o s u n a 针对s v m 训练速度慢以及时间空问复杂度大的问题，提出了固定样本工作 集算法【2 ，并将之应用于人脸检测中，取得了显著效果。其主要思想是将训练样本分为 工作集b 和非工作集，占中的样本个数为g 个，口远小于总样本个数。每次只针对工 作集b 中的玎个样本训练，而固定中的训练样本。该算法的要点有三个方面： 应用k k t 条件推出本问题的约束条件，这也是终止条件。 工作集中训练样本的选择算法，应保证分解算法快速收敛，且计算费用最少。 改变分解算法收敛的理论证明。 此后c h a n g 指出o s u n a 的证明不严密 2 1 1 ，且详尽地分析了分解算法的收敛过程及速 度。该算法的关键在于选择一种最优的工作集选择算法，o s u n a 的工作集选择算法也并 不是最优的，但是o s u n a 的这一工作是开创性的，并为以后的研究奠定了基础。 p l a t t 于1 9 9 9 年提出了s m o ( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ) 算法【2 2 1 ，该算法是固 定样本工作集算法的一种极端情况，其工作样本数目定为2 。需要两个样本，是因为等 式线性约束的存在使得同时至少有两个l a g r a n g e 乘子发生变化。由于只有两个变量，而 且应用等式约束可以将其中一个用另一个表示出来，所以在迭代过程中，每一步子问题 的最优解都可以直接用解析的方法求出来，这样，算法就避开了复杂的数值求解优化问 题的过程：此外，算法还设计了一个两层嵌套循环，分别选择进入工作样本集的样本， 大连理t ：x 学硕士学位论文 这种启发式策略大大加快了算法的收敛速度。实验结果证明s m o 在速度方面表现出了 良好的性能。 对这方面研究取得的成果还有张学工的c s v m f 2 3 1 、j o a c h i m s 丌发出的软件包 s v m t i 曲【2 4 1 以及c h i h w e i h s u 和c h i h j e n l i n 综合s s k e e r t h i 中的修改过的s m o 和 s v m l i g h 中的工作集选择算法，从而实现了软件包l i b s v m 2 5 i 。这两种s v m 工具已在科 学研究中发挥着重要作用。 ( 3 ) 针对多类问题的求解 针对多类问题，s v m 的算法有以下几种： v a p n i k 给出的算法1 9 1 是，对于类问题构造出n 个两类分类器，第i 个分类器用第 j 类中的训练样本作为正的训练样本，而将其它的样本作为负的训练样本。这个算法称 为一类对余类( 1 - a g i n s t r e s t ) 。最后的输出是两类分类器输出为最大的那一类( 此时，两 类分类器的判别函数不用取符号函数s g n ) 。其缺点是它的推广误差无界。另外一个算法 是由k n e r r 2 6 1 提出的，该算法在类训练样本中构造所有可能的两类分类器，每类仅仅 在类中的两类训练样本上训练，结果共构造k = n f 一1 ) 2 个分类器，我们称该算法 为成对分类( 1 a g i n s t 1 ) 。组合这些两类分类器很自然地用到了投票法，得票最多 ( m a x w i n s ) 的类为新点所属的类。该算法的缺点是： 如果单个两类分类器不规范化，则整个类分类器将趋向于过学习。 推广误差无界。 分类器的数目随类数急剧增加，导致在决策时速度很慢。 p l a t t 针对多类问题，提出了- s e e 新的学习架构一一决策导向循环图( d e c i s i o n d i r e c t e da c y c l i cg r a p h 。d d a g ) f 27 1 ，它将多个两类分类器组合成多类分类器，对于类 问题，d d a g 含有n ( n - 1 ) 2 个分类器，每个分类器对应两类。其优点是推广误差只取决 于类数和节点上的类问间隔，而与输入空间的维数无关，根据d d a g 提出算法 d d a g s v m ，d d a g 的每个节点和个成对分类器相关，其速度明显比一类对余类或成 对分类快。 w e s t o n 等人将s v m 算法的原始问题改为如下形式【2 8 】【删，使得它能同时计算出多类 分类决策函数， m l n f e a r s t 吖 等坩豢 m功。 凑魄轮 基于脉冲核的支持向量机研究1 赢用 其中m m y ，y ， 1 ，m 是模式x ，对应的多类分类指标，从精确性来说，该 方法得到的结果可以与应用广泛的一类对余类方法相比。但是这个最优化问题要同时处 理所有的支持向量，而其它方法中，独立的两类分类问题处理的支持向量数目就小得多， 所花费的训练时间就相应减少。 ( 4 1 支持向量机中核问题的研究 针对某一特定问题选择s v m 中核函数以及参数c 和v 等对于最后得到的决策函数 是至关重要的。这种问题统称为模型选择问题。尽管模型选择方面的研究成果不多，但 它作为s v m 的重要研究内容已日益受到研究者的重视。许多实验结果表明核函数的具 体形式对分类效果的影响不大，但是核函数的形式以及其参数的确定决定了分类器类型 和复杂程度，它显然应该作为控制分类器性能的手段。有关核函数选择的理论依据仍旧 很少，对核函数的研究主要是“留一法( l e a v e0 1 1 eo u t ，l o o ) ”，j o a c h i m s 和v a p n i k 通 过最小化几种不同的l o o 误差界 3 0 1 3 1 】，给出了选择合适的核函数及相应参数的方法。 a y a t 等认为核函数在零点附近应该较快的下降，在无穷远点有适当的下降而不应为0 。 由此构造了一个新的核函数k m o d l 32 1 ，实验表明k m o d 的推广能力高于径向基函数。 c h a p e l l e 针对不同模型参数得到的验证误差，拟合出一条关于模型参数与验证误差的曲 线，给出了根据拟合曲线的梯度修正模型参数的方法p ”。 由于统计学习理论为s v m 建立了一套较好的有限样本下机器学习的理论框架和通 用方法，既有严格的理论基础，又能较好地解决小样本、非线性、高维数和局部极小点 等实际问题，因此成为2 0 世纪9 0 年代末机器学习和数据挖掘界的研究热点之一。概括 起来，s v m 将向“更小”、“更快”、“更广”的方向发展：“更小”指构造s v m 所 需的内存更小，也就是利用有限的内存，处理尽可能多的样本；“更快”就是研究各种 s v m 新的快速训练算法；“更广”就是通过对已有算法的修改和改进，使s v m 的应用 范围更加广泛。 目前在对s v m 研究过程中，仍需要解决的一些难点包括如下方面： 核函数构造与参数选择缺乏理论指导。不同的核函数对分类器性能的影响也不 同，如何根据待解决问题的先验知识和实际样本数据，选择或构造合适的核函数、确定 核函数的参数等问题，都缺乏相应的理论指导。 训练大规模数据集的问题。如何解决训练速度与训练样本规模间的矛盾，测试 速度与支持向量集间的矛盾，找到对大规模样本集有效的训练算法和分类算法仍是尚待 解决的问题。 多类分类问题的有效算法与s v m 优化设计问题。尽管训练多类s v m 问题的算 法已被提出，但用于多类分类问题时的有效算法、多类s v m 的优化设计仍是一个需要 大连理上大学硕士学位论文 进一步研究的问题。 有效的增量学习算法问题。具有增量学习能力是许多在线训练、实时应用的关 键。需要找到有效的增量学习算法，同时满足在线学习和期望风险控制的要求。 1 。3 本文主要工作 本文主要工作包括： f 1 1 针对目前可供s v m 选择的m e r c e r 核较少的情况，借助于f o u r i e r 变换知识，提 出了一种基于f o u r i e r 变换的构造核函数方法。经过理论证明，运用该方法构造的核函 数同样满足m e r c e r 条件，可以作为核应用于s v m 的学习过程。同时依据该方法，给出 了一个构造实例，并对新构造的脉冲核的参数性质作了简要探讨。通过u c i 标准数据集 的试验，表明在保证推广能力基本不变的前提下，基于脉冲核的s v m 训练得到的支持 向量数普遍少于基于r b f 核s v m 的训练结果。 虽然依据脉冲核的s v m 训练得到支持向量集容量较小，这在一定程度上提高 了预测阶段的效率，但是针对规模较大的问题，s v m 仍然存在学习速度下降的缺点， 因此本文提出了一种基于卫向量的简化s v m 算法模型，在保证预测精确性的前提下， 进一步对s v m 进行了改进，使得改进后的s v m 更适合求解大规模问题。 f 3 1 由于近年消费信贷的升温，信贷机构需要对借款者的信用度进行尽可能准确地 评估，针对一些已有评估方法对数据分布有限制的缺点，考虑到s v m 预测技术对数据 样本的分布特征没有限制，同时理论上又有较好的推广能力，本文最后将改进s v m 模 型应用到个人信用评估中，对个人信用评估的过程进行了简要探讨，为发展个人信用评 估提供了一种新途径，同时也为信贷机构的信贷发放提高了决策依据。 基于脉冲核的支持向量机驯宄2j 川i j 2 支持向量机基础 2 1 统计学习理论 统计学习理论( 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 ) 【8 】是7 0 年代末提出、并在9 0 年代逐 渐完善的一种针对小样本的机器学习理论，主要研究给定数据样本上的函数估计问题。 统计学习理论第一次强调了所谓小样本统计学的问题，这是相对于以前的样本统计学而 言( 主要考虑样本数目趋于无穷大时的统计性质) 。研究表明，对很多函数的估计问题， 通过考虑样本数量，可以得到比基于传统统计技术方法更好的解。统计学习理论是s v m 产生的重要理论基础，本节将介绍相关理论。 2 1 1 机器学习问题表示 根据给定的训练样本，机器学习的目的就是求出对某系统输入输出之间依赖关系的 估计，使它能够对未知输出尽可能准确地预测。这种学习问题可以归结为一般的多维函 数逼近问题。 设输出变量y 与输入变量z 存在一定的未知依赖关系，现有门个独立同分布观测样 本 g 。，弘) ，g ：，y ：l ，g 。，y 。) ( 2 1 ) 我们希望建立一个模型，使它根据样本( 2 1 ) ，获得具有推广能力的逼近函数。样 本学习模型主要由三部分组成： 生成器( g e n e r a t o r ) ：按某一存在但未知的概率分布p ( x ) ，生成随机向量聋。 监督器( s u p e r v i s o r ) ：按某一存在但未知的概率分布j d d f z ) ( 一般的情形监督器 常使用函数形式，y = ，g ) ) ，使输入向量x 回到输出向量y 。 学习机器( l e a r n i n gm a c h i n e ) ：其逼近能力的大小由函数集厂k 埘决定，即 ，( x ，w ) 为学习机器有可能实现的逼近函数。 在此模型下，学习问题可看作在一组函数厂( x ，w ) 中求一个最优的函数，g ，w ) 对依 赖关系进行估计，使期望风险 矗( 曲= k ，厂g ，w 归仁力 ( 2 2 ) 最小。其中杪g ，w ) 称作预测函数集，w 为函数的广义参数， ，g ，w ) 可以表示任何函 数集；l ( y ，g ，w ) ) 是厂0 ，w ) 对y 进行预测而造成的损失。不同类型的学习问题有不同 形式的损失函数。 大连理工大学硕士学位论文 机器学习问题有三种基本类型，即模式识别、函数逼近和概率密度估计。 在模式识别问题中，输出变量y 表示类别符号。两类情况下，) ，= 0 ，1 或 1 ，- 1 ，损 失函数又被称为指示函数，如下定义： 如地叫呈弼酬 眨。， 在函数逼近问题中，y 是连续变量，损失函数定义为： 工【y ，b ，) ) 一( y 一，仁，w ) ) 2 ( 2 4 ) 在概率密度估计问题中，学习目的是根据训练样本确定x 的概率密度。记估计的密 度函数为p ( 工，w ) ，则损失函数定义为： 工( p 0 ，w ) ) t i n p ( x ，w ) ( 2 5 ) 2 1 2 经验风险最小化 由上节介绍可知，学习问题的目标在于使期望风险r ( w ) 取得最小。但是由于我们可 以利用的信息只有样本数据( 2 1 ) ，因此( 2 2 ) 式无法计算。传统的学习方法采用经验风 险最小化( e r m ) 准则，即用经验风险作为( 2 2 ) 式的估计。经验风险表示为： r 一( w ) 。砉善工( ) ，t ，k ，w ) ) ( 2 6 ) 对损失函数( 2 3 ) ，经验风险就是训练样本错误率；对( 2 4 ) 式的损失函数，经验风 险就是平方训练误差；而采用( 2 5 ) 式，e r m 准则就等价于最大似然方法。 最小化经验风险在多年的机器学习方法研究中占据了主要地位。但e r m 准则代替 期望风险最小化没有经过充分的理论论证，只是直观上合理的想当然做法。e r m 准则 不成功的一个例子是神经网络的“过学习”问题。训练误差小，并不总能导致好的预测 效果。某些情况下，训练误差过小反而会导致推广能力的下降，即真实风险的增加。因 此，有限样本情况下，经验风险最小并不一定意味着期望风险最小。学习机器的复杂性 不但应与所研究的系统有关，而且要和有限数目的样本相适应。 2 1 3v c 维和推广性的界 统计学习理论是研究小样本统计估计和预测的理论，在其中定义了一系列有关函数 集学习性能的指标，其中最重要的两个概念就是v c 维( v a p n i k c h c r v o n c n k i sd i m c n s i o n ) 和推广性的界。 基于脉冲核的支持向量机 究与廓用 ( 1 ) v c 维 v c 维的直观定义是，对一个指示函数集，如果存在 个样本能够被函数集中的函 数按所有可能的2 种形式分开，则称函数集能够把 个样本打散：函数集的v c 维就是 它能打散的最大样本数目h 。若对任意数目的样本部有函数能将它们打散，则函数集的 v c 维是无穷大。 例如，假定模式空间是二维平面r 2 ，所要考察的函数集是由带方向的直线组成。直 线的方向由其法线方向表示，法线的箭头所指的一面标记为1 ，另一面标记为0 。这样， 该直线就可以看作一个学习机器( 分类器) 。图2 】表明，平面中的直线可以将三个任意 给定的点按照所有可能的方式( 2 3 种) 划分。 00 再一 ! ! o o 冰 图2 1 平面上三点被一条直线以任意方式划分 f i g 2 1c l a s s i f i c a t i o nr e s u l to ft h r e ep o i n t si nt h ep l a n eb yab e e l i n ei na n yw a y s 如果在此基础上增加一点，使二维平面上变成四点，如图2 2 所示，那么这四个点 就无法用直线按类划分。 睁 因此平面中的一条直线最多可以将三点完全分开，按照v c 维的定义，二维平面中 直线( 分类器) 的v c 维是3 。 0 大连理工大学硕士学位论文 一般的，对于门维空间r “中的m 个点，如果从中任意去除一点，剩余的所有点仍都 能保持线性独立关系，则这v n 个点能被一个超平面完全划分。由于r “上最多只有h 个点 是线性独立的，因此r “中超平面的v c 维是n + 1 。 r ”中超平面可表示为： q 0 ，a ) + q 巩= o ，( _ m ，o o ) ( 2 7 ) j = l 其中，“= l u l 一， 表示r “空间中的一组正交基，口= k ， 表示该超平面的广义 参数。因此，r “中超平面共有”+ 1 个独立参数，恰好等于其v c 维数。 对于非线性学习机器而言，v c 维与独立参数的个数之间并没有明确的对应关系。 非但如此，在非线性情况下，学习机器的v c 维通常是无法计算的。但是在实际中应用 统