（计算数学专业论文）最小二乘与最小二乘支撑向量机.pdf

摘要 摘要 本论文主要研究了最小二乘支撑向量机( l s s v m ) 增量型训练算法以及固定 尺度算法。最小二乘支撑向量机( l s s v m ) 是由j a 。ks u y k e n s 等人根据支撑向 量机( s v m ) 算法提出的，是s v m 的扩展版本。 标准的最小二乘支撑向量机算法主要是离线应用训练算法，对其在线训练算 法的研究相对较少，因此本文在已有成果的基础上，主要进行了如下的研究： 1 ) 深入探讨了最小二乘支撑向量机调练算法的基本理论，然后利用仿真实 验对最小二乘法、标准最小二乘支撑向量机、稀疏最小二乘支撑向量机算法性能 进行了比较。 2 ) 研究了增量型的最小二乘支撑向量机训练算法以及固定尺度训练算法。 针对常规固定尺度最小二乘支撑向量机存在的问题( 比如对于时间序列数据，可 能导致支撑向量过于集中于初期) 进行了分析，得到了有效的改进方法，大大的 提高了算法的性能。通过仿真实验验证了改进方法的有效性。 关键词：统计学习理论，最小二乘法，最小二乘支撑向量机，稀疏性，增量算法 a b s t r a c t a b s t r a c t n et h e s i ss t u d i e st h ei n c r e m e n t a la n df i x e d s i z et r a i n i n ga l g o r i t h mo fl e a s t s q u a r e ss u p p o r t v e c t o rm a c h i n e ( l s s v m ) 。l s s v m ，w h i c hw a s p u tf o r w a r da n db a s e d u p o ns u p p o r t v e ，c - t o rm a c h i n e ( s v m ) b yj a ks u y k e n se t a l ，i sa l le x t e n d e d e d i t i o n o f s v m n # s t a n d a r da l g o r i t h mo fl s s v m8 1 ea ho f f l i n eo n e s ，w h i c hc o u l d n tb eu s e d 0 1 1 l i n e t h e r ea r ef e ws t u d i e so no n l i n el s s v m t r a i n i n ga l g o r i t h m s b a s e d o l lp r e v i o u s r e s e a r c hr e s u l t s ，t h em a j o rc o n t e n t so f t h i st h e s i sa r ea sf o l l o w i n g ： f i r s t ，t h eb a s i ct h e o r e t i c a lo ft h el s s v ma l g o r i t h mh a sb e e ng o n ed e e pi n t o d i s c u s s e d t h e nl e a s ts q u a r e sm e t h o d ，l s s v ma n dp r u n i n gs p a r e sa l g o r i t h mo f l s s v mh a v eb e e nc o m p a r e db yt h es i m u l a t i o nr e s u l t s f i n a l l y , w er e s e a r c h e do nt h ei n c r e m e n t a la n dt h ef i x e d - s i z et r a i n i n ga l g o r i t h m so f l s s v m f o rt h ed e f e c ti nr e g r e s s i o np r e d i c t i n gw h i c hl s s v m , a ni m p r o v e dm a h o di s p r o p o s e d ，w h i c hh i g h l yp e r f o r m a n c eo f l s s v m s i m u l a t i o n r e s u l t ss h o wt h ev a l i d i t yo f t h ei m p r o v e da l g o r i t h m k e yw o r d s ：s t a t i s t i cl e a r n i n gt h e o r y , l e a s ts q u a r e sm e t h o d ，l e a s ts q u a r e ss u p p o r t v e c t o rm a c h i n e , s p a r s e n e s s ，i n c r e m e n t a la l g o r i t h m n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特另加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：丛鱼叠日期：瑚了年f 月2 8 h 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，- 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：猛鱼痒导师签名：丑：比 ， 。 日期：佣矿石月i - 日 f 第一章数据挖掘与机器学习理论 第一章数据挖掘与机器学习理论 在这个数据资源呈指数增长的时代里，银行、超市、通讯、股票、基金、证 券、网络等等产生的数据大规模向人们的生活进军。在这个数据的海洋里，如何 利用它们得到有用的信息和知识，为企业或者个人在决策制定、科学管理、商务优 化、生产控制、市场分析、工程设计和科学探索等方面提供先验知识，从而减少 盲目性，避免风险，减少损失，获得更大的收益，取得更大的成功，成为信息时 代迫在眉睫的研究热点问题，因此数据挖掘的研究被提了出来。数据挖掘被信息 产业界认为是数据库系统最重要的前沿之一，是信息产业最有前途的交叉学科， 在这个信息时代，她将无处不在。换句话说，只要存在数据存储的地方，数据挖掘 就有存在的土壤。 机器学习作为数据挖掘的一种常用方法，近年来也已被成功地应用于很多领 域，从检测信用卡交易欺诈的数据挖掘程序，到获取用户阅读兴趣的信息过滤系 统，再到能在高速公路上自动行驶的汽车。同时，这个学习的基础理论和算法也 有了重大进展。 1 1 数据挖掘的基本概念及理论基础 数据挖掘( d a t am i n i n g ，d m ) 是知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e , k d d ) 的核心环节，是从在大量的、不完全的、含噪声的、模糊的、随机的数据 中，提取隐含其中的、目前未知的、最终可以理解的、有效的、新颖的、潜在有 用的信息和知识的非平凡过程。简单的说，数据挖掘就是从存放在数据库、数据 仓库或其他信息库中的大量历史数据中提炼有趣知识的过程。当然，这里指的知 识并不是崭新的科学理论或数学公式，也不需要用什么定理来证明。d m 是集数据 库技术、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、 信息检索、图象与信号处理和空间数据分析等领域交叉研究的产物。 由于数据挖掘宽阔的研究领域与交叉理论体系，与之相关的理论基础研究还 没有完全成熟。坚实的和系统的理论基础对于数据挖掘非常重要，因为它给数据 挖掘技术的开发、评价和实践提供了一个统一的平台。目前而言，数据挖掘的理论 基础主要包括以下的内容【l 】： 电子科技大学硕士学位论文 数据归约( d a t ar e d u c t i o n ) ：这一理论的主要目的是在数据挖掘中有效地减 少数据的描述，使其能有效地提高数据库的查询速度。 数据压缩( d a t ac o m p r e s s i o n ) ：根据这一理论，数据挖掘应该在对给定的 数据进行压缩的基础上进行，它一般是通过按位、关联规则、决策树、簇等进行 编码实现的。而其编码实现的依据是最小描述长度理论( m i n i m u md e s c r i p t i o nl e n g t h p r i n c i p l e ) 。 模式发现( p a t t e r nd i s c o v e r y ) ：在这一理论中，数据挖掘的基础是在数据库 中发现模式，比如关联规则、分类模型、序列模式等。 概率理论( p r o b a b i l i t yt h e o r y ) ：它基于统计理论。依据这一理论，数据挖 掘的基础是发现随机变量的联合概率分布。 1 2 数据挖掘的主要研究内容 数据挖掘自从2 0 世纪8 0 年代末提出后，经过十几年的发展，已经成为一种 比较成熟的技术，当前对数据挖掘的研究主要集中在以下几个方面。 数据挖掘模型的研究。 数据挖掘技术和算法的研究。 数据挖掘应用研究【3 “。由于数据挖掘可以应用于决策支持，也可以应用于 数据库管理系统，因此，它已广泛地用于金融风险分析、信用欺诈检测、股票价 格分析与预测、d n a 检测、时间序列、客户关系管理、市场营销、质量检测、化学 制药、图象处理、空间数据挖掘等领域。 1 3 机器学习的基本概念 随着现代信息技术、通讯技术和计算机技术的高速发展，数据库应用的范围、 深度和规模不断扩大。传统的信息系统大部分是查询驱动的，数据库作为历史知识 库对于一般的查询过程是有效的，但当数据和数据库的规模急剧增长时，传统的 数据库管理系统的查询检索机制和统计分析方法已远远不能满足现实的需求，它 迫切要求能够自动、智能和快速地从数据库中挖掘出有用的信息和知识。在这种 需求的指引下，一种新的知识获取技术机器学习( m a c h i n el e a r n i n g ) 产生了，它 指的是借助计算机等通过一定的程序、方法来达到从经验中得出结论。机器学习 这门学科致力于回答类似下面的问题【2 】： 2 第一章数据挖掘与机器学习理论 存在什么样的算法从特定的训练数据学习一般的目标函数呢? 如果提供 了充足的训练数据，什么样的条件下会使特定的算法收敛到期望的函数? 哪个算 法对哪些问题和表示的性能最好? 多少训练数据是充足的? 怎样找到学习到的假设的置信度与训练数据的 数量及提供给学习器的假设空间特性之间的一般关系? 学习器拥有的先验知识是怎样引导从样例进行泛化的过程的? 当先验知 识仅仅是近似正确时，它们会有帮助吗? 关于选择有效的后续训练经验，什么样的策略最好? 这个策略的选择会如 何影响学习问题的复杂性? 怎么把学习任务简化为一个或多个函数逼近问题? 换一种方式，系统该试 图学习哪些函数? 这个过程本身能自动化吗? 学习器怎样自动地改变表示法来提高表示和学习目标函数的能力? 有关学习问题的研究历史可以分为四个阶段f 3 】： 1 ) 第一个学习机器的建立( 2 0 世纪6 0 年代) 1 9 5 8 年，生理学家f r o s e n b l a t t 提出了第一个称作感知器的学习机器模型， 用于解决最简单的分类问题。r o s e n b l a t t 通过一些简单的实验证明了这个模型的 可推广性。在此之后，研究人员提出了很多不同类型的学习机器，如b w i d r o w 构 造的m a d a l i n e 自适应学习机、k s t e i n b u c h 提出的学习矩阵等，这些学习机器都获 得较好的推广性。 2 ) 学习理论基础的创立( 2 0 世纪6 0 7 0 年代) 为了提取上述不同学习机器的共性，研究人员找到了一个通用的归纳原则： 经验风险最小化( e m p i r i c a li h s km i n i m i z a t i o n , e r m ) 原则，并在此基础上创立了模 式识别问题的e r m 理论，它包含通用的推广性的定性理论和通用的定量理论两部 分。 3 ) 神经网络( 2 0 世纪8 0 年代) 反响传播( b a c kp r o p a g a t i o n , b p ) 技术可以同时寻找多个神经元的权值，标志着 构造一般性学习机器研究的完成。学习机器的研究历史进入了一个新阶段，即人 工神经元网络( a a i f i e i a l n e u r a l n e t w o r k ，a n n ) 时代。在随后的十几年中，人们在许 多领域对神经网络进行了深入细致的研究，不但在实际应用中取得了良好效果， 而且提出了若干其他神经网络模型，如自组织型、向前型、反馈型以及随机神经 网络等等。尽管神经网络在许多应用领域都取得了重要成果，但其实现过程过多 地依赖人的主观意识和先验知识，而不是建立在严格的理论基础之上，因此，难 3 电子科技大学硕士学位论文 以对神经网络模型的性能及其使用范围进行理论分析。 4 ) 统计学习理论( s t a t i s t i c a ll e a m i n gt h e o r y , s l t ) 的建立( 2 0 世纪9 0 年代) v a p n i k 等人从六、七十年代开始致力于统计学习理论的研究。到2 0 世纪9 0 年代中期，随着其理论的不断发展和成熟，人们研究的重点转移到对神经网络的 这种替代方法上。与传统统计学相比，s l t 针对小样本统计问题建立了一套新的 理论体系，在这种体系下的统计推理规则不仅考虑了对渐进性能的要求，而且追 求在现有有限信息的条件下得到最优结果。目前，该理论的理论基础己然完善， 研究工作开始转向理论推广及算法的优化设计上，同时该理论也正被人们广泛的 应用于诸多领域。 1 4 机器学习的发展与展望 目前，随着机器学习相关理论的逐步成熟，对其在应用领域的研究已经推向 了新的高度，其在许多领域都取得了很大的成功，如用于自然语言处理、模式识 别、机器翻译以及专家系统等。 从目前的研究趋势来看，估计机器学习今后将在以下几个方面做更多的工作： 人类学习机制的研究：发展和完善现有的学习方法，并开展新的学习方法的研究； 建立实用的学习系统，特别是多种学习方法协同工作的集成化系统的研究；机器 学习有关理论及应用的研究；支撑向量机作为一类较新型的机器学习方法，由于 其坚实的理论基础，其改进型模型和应用研究都将是今后很长一段时间人们研究 的一项重要课题。 4 第二章最小二乘方法 2 1 引言 第二章最小二乘方法 1 8 0 5 年，l _ e g e n d r e 在其发表的著论计算彗星轨道的新方法的附录中最早 提出了最小二乘法，可能由于该方法尚未成熟，他没有在其有关卫星轨道计算的 讨论中涉及最b - - - 乘法。1 8 0 9 年，g a u s s 在其发表的著论天体运动理论的末 节提出了最小二乘法，并成功利用该方法验证了正态分布 7 1 。由此可见，最小二乘 法最初是作为解“观测组合”问题的一种工具出现的，随着现实中求解线性数据 拟合问题的大量出现，利用线性最小二乘问题的计算来处理拟合问题已经得到了 广泛的应用。然而，在数据拟合问题中，人们为了减少数据观测过程中带来的误 差，总会采集比待定参数个数更多的样本数据，因此数据拟合问题就相应地转化 为解一个超定线性方程组。 2 2 最小二乘原理 设( x ，y ) 是一对观测量，r x = ( 一，工“) 7 r 4 ，y r 满足下面的理论函数： y = 似m ，) ( 2 - 1 ) 其中o = 1 ，m ) 是待定参数。 为了寻找函数y = m ；w i ，) 的参数( f = l ，m ) 的最优估计值，给出托 ( 对实际问题而言有玎m ) 对观测数据( x s ，y 。) ，求解使得目标函数： ( m ，h k ) = ( m 一厂( 五；w l ，m k ) ) 2 ( 2 2 ) 1 = 1 取最小值时的参数o = l ，m ) 。求解的这类问题就是通常的最小二乘问题，该 方法的几何语言也称为最j 、- - 乘拟合。 拟合函数与观测数据对中函数在各观测点上的差值 ( w ) = 乃一，( 五；w l ，m _ ) 0 = l ，厅) ( 2 - 3 ) 称为残差。这里w = ( m ，w 2 ，) e r ”。有时，为了保证拟合的精度，常用各观 5 电子科技大学硕士学位论文 测残差的加权平方和作为目标函数，即求参数o = 1 ，m ) 使 工( m ，) = 窆 ( w r ：窆一( 咒一厂( ；，”：( 2 - 4 ) i if i 为最小。其中以 o 称为在观测点( x l ，y ，) 处的权。关于权一，可以简单地理解为该 观测点在实验观测时出现的次数。 2 3 最小二乘问题求解方法3 】 2 3 1 线性最小二乘问题求解方法 当( 2 1 ) 是线性线性函数时，我们可以将( 2 3 ) 式或( 2 4 ) 式用矩阵表示如下： 其中爿= 爿# z 写 彳 巧 r a 。i n0 a w y i l 2 或哑n i i a ( a w - y ) 1 1 2 r ”。a = 辰 ； 0 ( 2 5 ) ( 2 6 ) ( r + ) ”m w 贰“，y r “， j j | | 表示2 - 范数，这里玎 m 。它们的求解方法主要有以下几类： 2 3 1 1 法方向法 利用偏导数求极值以及内积定义，易知，最d , - - 乘问题( 2 5 ) 或( 2 6 ) 的解集和 法方向 a 7 4 w = a 7 y ( 2 7 ) 或a 2 a w = a 7 a 2 y ( 2 8 ) 的解集完全相同。 当r a n k ( a ) = 研时，a 7 a 和4 7 a 2 4 均为对称正定矩阵，此时利用c h o l e s k y 分解 ( 即有a = l l r ，或彳7 a 2 4 = 皿i ，其中上是下三角可逆矩阵) 可求得最d x - - 乘 问题的唯一解w = ( f ) - 1 f a 7 y ( 或w = ( f ) 4 f 1 a 7 a 2 y ) 。然而，当彳的条件数过大 或r a n k ( a ) m 时，不易利用法方向问题求解。 6 。：厉 第二章最4 x - 乘方法 2 3 1 2 正夏分解法( o r 分解法) 对于许多大型问题的计算，可能由于法方程组的严重病态，导致法方程组( 2 7 ) 或( 2 8 ) 中的系数矩阵爿7 爿或彳7 a 2 4 为奇异矩阵。因此，为了避免在构造法方程组 中导致矩阵病态问题，常应用h o u s e h o l d e r 变换来处理( 2 5 ) 和( 2 6 ) 。 为了便于书写，以下几类方法都只对( 2 - 5 ) 的情况进行讨论。应用h o u s e h o l d e r 变换把系数矩阵4 r ? 正交三角化分解( 即q r 分解) ，使 剑= ( 苫 p ， 其中q r 为正交矩阵，r r 罗为上三角阵，0 r 一m 的零矩阵，p r “为 置换矩阵。 q ( a w - y ，= ( 咖( 言) 肌一( 烈鬈“ 叫 其中9 = ( ； ，又q 是正交矩阵，有： i l a w - y l l 2 = q ( a w - y ) 旷= r 一硎2 = l l 艘w 叫卜忙1 1 2 ( 2 1 1 ) 要使肛w y i l 2 取极小值，只需选择_ h ，使得 r p w - c = 0 ( 2 - 1 2 ) 即可。 对( 2 1 2 ) 式求解，根据，的取值，可分为两类： 第一类：，= 研，直接由r p 的可逆性求解，得w = p 7 r - 1 c ； 第二类：， m ，由r r ：x “，对彤豫：”进行q r 分解，得 职7 = ( 苫 只j r 7 = y 7 ( 苫 日 g 一s ， 其中v r “为正交矩阵，置7 r ”为非奇异的上三角矩阵，日r ”为置换矩 阵，则( 2 1 2 ) 式，有： 掣。) 脚；。哆j 墨，焉c l = c 铮c 1 嘶。印 ( 2 - 1 4 ) 7 电子科技大学硕士学位论文 由阡w = 得( 2 - 5 ) 的最小二乘可行解： w 矿时叫置。) 弘均 其中d l r ”的任意向量。当且仅当吐= o 时，得 ，岷m = p 7 巧7 墨1 日c ( 2 - 1 6 ) 为( 2 - 5 ) e e 唯一的范数最小的最小二乘解，其中曙r ”为9 7 的前r 列组成的子矩 阵。 。 由上可见，q r 分解法可以有效避免法方向法可能导致的矩阵病态问题，是求 解线性最4 - - 乘问题的一个非常稳定的方法，其不足之处在于h o u s e h o l d e r 变换在 计算复杂度上高于g a u s s 消去法，因此，当系数矩阵不会出现病态问题时，不用 考虑该方法。 2 3 1 3 奇异值分解法 由矩阵理论知识可知，如果( 2 - 5 ) 的系数矩阵为a r 了“，j 1 r a n k ( a ) = ，( r 0 ，如果存在一个超平面厂( 功= w r x + b 沿y 轴 1 4 第三章支撑向量机( s r v ) 与最小二乘支撑向量机( l s s v m ) 依次上下平移s 所扫过的区域包含了2 中所有的训练点，即满足关系： - f - i 卣十毒i l 孵矿， “加 7 智、7 s t 咒一矿五一6 + 毒 ( 3 4 ) i6 一只+ w 7 玉占+ 螽 【 磊o i = 1 ，2 ，玎 为了求解这个约束最优化问题，引入拉格朗日函数 l ( w , b ，善，c r ) = j ( w 掌+ ) 一主( 屈螽+ 万善) 一呸( + 缶一咒+ m ，墨+ 功( 3 5 ) 一竞乏( s + 善一6 + 咒一矿五) 其中拉格朗日乘子满足g = ，莓，乏) 7 2 0 ，= ( 磊，荔，成，荭) 7 o 。分 别对w ，b ，f 求偏导或梯度并令它们为0 ，得到 w ：窆( 呸一面) 墨 窆( 一乏) ：0 c 一呸一属= 0 c 一仅e p = 0 将( 3 6 ) 代入( 3 5 ) ，并对它求关于口的极大，就得到原始优化问题的对偶问题 1 7 ( 3 6 ) 电子科技大学硕士学位论文 。m 讲a x 。一三喜喜 一呸a ) ( 巧一芴) b ) 一占杰( 啦+ 乏) + 杰只( 啦一乏) n ( 啦一面) = 0 0 量口，s c o s 互 0 为正规化参数，p = “，巳) 2 为误差向量，引入拉格朗日乘子，有： 三( 嵋6 ，岛口) ：丢矿w + 导窆白2 一窆啦( 矿玉+ 6 + 岛一m ) ( 3 - 1 3 ) 式中p - ：- - 1 , - - - , 栉) 是拉格朗曰乘子。由最优化条件，就( 3 1 3 ) 分别对w ，b ，g 和口 求偏导数，并设为0 ，有： k 动砷 静弘 * 蚱 钳 珏 塘 电子科技大学硕士学位论文 詈= 。j w = 喜q 五 雾o l = o j 打。 任。 罢：o j ： 七：1 一，弹 。 o e , 罢；o j 矿矗+ b + 气一以：o 七：1 ，栉 d 盯。 学问= s ， 其中q r ，且q f = 而7 ，f ，= 1 ，以，j 为月阶单位矩阵，1 r ”为元素全为 1 的向量，口= ( q ，) 7 ，y = ( 乃，耽，只) 7 。 最后，将( 3 1 5 ) 中求解出的口和6 代n ( 3 - 2 ) ，可以表出最小二乘回归估计函数： 厂( x ) = 矿x + 6 = 呸彳x + b ( 3 1 6 ) 约束条件中利用一个非线性映射妒( ) ：r 4 专瞅( 这里m 、h 分别表示输入样本空 空间，因此对于非线性影射妒( ) 的计算是困难的，并有可能导致“维数灾难”。类 芷( 五，_ ) = ( 妒( 五) 伊( _ ) ) 降问= ( ：) b - 乃 第三章支撑向量机( s r v ) 与最小二乘支撑向量机( l s s v m ) 其e p k , ，= 足( ，_ ) = “) 伊( _ ) ) ，f ，j = 1 ，一。对应( 3 1 4 ) 的第一个等式 w = q 矿( 墨) ，则回归估计函数为： i = l 厂( z ) = m ，伊( 工) + 6 = q k ( ，工) + 6 ( 3 - 1 8 ) 1 = 1 由于最小二乘支撑向量机把支撑向量回归机的凸二次规划问题( 3 7 ) 或( 3 8 ) 的 求解转化为了一个线性方程组( 3 1 5 ) 或( 3 1 7 ) 的求解，这极大地简化了计算复杂度， 从而有效地提高了求解速度。同时可以看出，由于使用了等式约束条件，只能保 证解的局部最小性，丧失了支撑向量回归机的勰的一个重要特性：鲁棒性；而且， 由于没有使用f 不敏感损失函数，从( 3 1 4 ) 第三个式子：吒= c ，k = l ，l ，可 以看出支撑向量的拉格朗日乘子的绝对值大小与训练点处的残差成正比，因此丧 失了支撑向量机的解的另外一个重要特性：稀疏性。 3 5l s s v m 的求解方法以及算法设计 从1 9 9 9 年j a 。kj u y k e r l $ 和j v a n d e w a i l l e 提出最小二乘支撑向量机以来，其精 简、快速的求解过程吸引了众多的研究者在此基础上进行算法改进。为了充分发 挥l s s v m 的优良性能，研究者f f 3 弓l 入了剪枝法和w 权向量表出法等来提高解的 稀疏性或鲁棒性，以此增强l s s v m 的泛化能力。 前几节的分析已经说明支撑向量回归机引入占一不敏感损失函数后，其解具有 稀疏性，这个特性对实际应用问题具有很强的适应能力，而最d x - - 乘支撑向量机 的解丧失了这一优良特性，因此阻碍了该算法的实际应用和推广。为了弥补该算 法的这个遗憾，使之在实际应用中获得推广，s u y k e n s 等人提出了剪枝法( p r u n i n g m e t h o d ) 1 蚣川求近似解。该方法的主要思想就是利用i 啦i 越小的样本点对回归估计函 数的贡献越小的事实，通过剪枝一定比例的啦( 通常是训练集数据个数的5 ) ， 训练缩减后的样本数据，如此反复，直到最小二乘支撑向量机的性能变差为止。 此算法称为稀疏近似最小二乘支撑向量机。 算法一：【1 9 】 ( 1 ) 输入n = 玎个训练样本点，以是输入样本个数，对个样本训练最小二乘 支撑向量机； ( 2 ) 对i 啦i ( i = 1 ，) 进行排序，剪枝m 个i 啦l 最小的训练样本( 一般来说， m = n 5 ) ： 2 1 电子科技大学硕士学位论文 ( 3 ) 设= 一m ，将剩余的个训练样本组成新的训练样本集； ( 4 ) 用最4 x - - 乘支撑向量机训练新的样本集： ( 5 ) 返回( 2 ) ，直到最小二乘支撑向量机的性能变差，停机。 该方法可增强最小二乘支撑向量机解的稀疏性，但由算法第( 4 ) 步可以看出， 它需要对所有样本点构成的集合以及其部分子集中的所有元素进行反复的优化， 该算法是以牺牲训练速度为代价来增强解的稀疏性，不能充分体现最小二乘支撑 向量机速度快的特点。 为了改善和克服上述算法的不足，g c c a w l e y 和n l ct a l b o t 提出了另外一 种求稀疏解的方法【2 1 捌一利用有限或少量样本点完全或不完全表出w 权向量来 求最小二乘支撑向量机的稀疏解，其基本思想：根据( 3 1 4 ) 第一个表达式以及( 3 1 8 ) 式的回归估计函数，如果能用有限或少量的x t ( i s ，s c 1 ，2 ，n - i ，且蚓 以， h 表示元素个数) 表出或近似表出w ，即w = c t l x ，( 在文献 1 5 】中采用的是近似 表出：w 一哆五) ，则可设q = o ，j s ，这样就可在子集q = ( 五，m ) i f s ) c t 上用最小二乘支撑向量机进行训练。由于蚓 栉，故此方法一定比剪枝法速度更快。 此算法称为求最小二乘支撑向量机稀疏解的改进算法，简称i s l s s v m 。 对上述方法有两点需要说明：一是这样的s 是否存在；二是如何确定s 。 实际上，对于大型数据样本集而言，一般都是大型稀疏矩阵，因此显然存在 s c 1 ，2 ，栉) ，且大多数情况有蚓撑，使得z ，属薯，这里- k e t ；又 w = 啦五，显然由线性代数知识有w = 五，这里是与和a 相关的参数， 将谢记作啦，i s 即可。 对于非线性的情况，将五换为妒( 五) ( 可能是无穷维的向量) ，如果向量集 妒“) ，伊( 吃) ，妒( ) 中妒是非线性映射，例如径向基映射，则这样的s 是很难 求或不存在的。此时解决的方法可用近似表出w z q 妒( 薯) 来代替完全表出。 下面根据g c c a w l e y 等人提出地求稀疏解的算法来对非线性问题进行一下简 单地推导，其中假设所需的s 已经求出： 原始问题的最优化函数通过上面的叙述可变为 1 一n 厂 、2 曾l ( 咖) 2 圭丕吒吩k ( ) + 詈善卜薹吩k ( ”) 。6 j ( 3 以9 ) 第三章支撑向量机( s r v ) 与最小二乘支撑向量机( l s s m m ) 同样，在上式中对口和6