首页 基于无约束优化的最小二乘支撑向量机

基于无约束优化的最小二乘支撑向量机

举报
开通vip

基于无约束优化的最小二乘支撑向量机 第30卷第9期 2010年 9月 计算机应用 Journal of Computer Applications Vol_30 No.9 Sep.2010 文章编号 :1001—9081(2010)09—2297—04 基于无约束优化的最小二乘支撑向量机 熊福松 ,王晓明 ,朱香卫 (1.南京铁道职业技术学院 信息工程系,江苏 苏州215137; 2.江南大学 数字媒体学院,江苏 无锡 214122) f xfsxs2003@ 163.con1 摘 要:为了解决最小二乘支撑向量机...

基于无约束优化的最小二乘支撑向量机
第30卷第9期 2010年 9月 计算机应用 Journal of Computer Applications Vol_30 No.9 Sep.2010 文章编号 :1001—9081(2010)09—2297—04 基于无约束优化的最小二乘支撑向量机 熊福松 ,王晓明 ,朱香卫 (1.南京铁道职业技术学院 信息工程系,江苏 苏州215137; 2.江南大学 数字媒体学院,江苏 无锡 214122) f xfsxs2003@ 163.con1 摘 要:为了解决最小二乘支撑向量机(LSSVM)优化问题需要耗 费大量时间的问题,提 出了利用牛顿优化法来 解决 LSSVM优化问题的方法(称为 Newton—LSSVM)。首先把 LSSVM优化问题转化为无约束化优化问题的形式,然后 再采用牛顿优化法来迭代求解。实验结果 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明,该方法在大幅度减少 LSSVM算法的训练时间开销的同时,能够获得 与采用传统优化方式求解 LSSVM优化问题一样的泛化能力。 关键词 :监督学习;最小二乘支撑向量机;优化算法 中图分类号 :TP181 文献标志码 :A Least square support vector machine based on unconstrained optimization XIONG Fu—song ,WANG Xiao-ming ,ZHU Xiang-wei (1.Department ofInformation Engineering,Na ng Institute ofRailway Technology,Suzhou Jiangsu 215137,China; 2.School of Digital Media,Jiangnan University,Wuxi Jiangsu 2141 22,China) Abstract:To solve the problem that the optimization of Least Square Support Vector Machine(LSSVM)consumes too much time, a new method called Newton—LSSVM, which used Newton optimization to solve the optimization problem of LSSVM,was proposed.The method first converted LSSVM to unconstrained optimization,and then used Newton optimization to solve the optimization problem iteratively.The experimental results show that Newton—LSSVM can reduce the training time greatly but do not decrease the generating ability of LSSVM. Key words:supervised learning;Least Square Support Vector Machine(LSSVM);optimization algorithm 0 引言 近年来 ,支撑向量机(Support Vector Machine,SVM)⋯已 经在机器学习和模式识别领域的研究中引起了广泛的关注, 成为了广大学者的研究热点之一。SVM采用了最小化结构 风险 来构造决策超平面,并且能够较好地处理线性和非线 性学习问题。由于 SVM结构简单 ,泛化能力强 ,并具有坚实 的统计学习理论基础⋯,所以在众多的研究和应用领域中都 引起了广泛的关注,并取得了显著的成果。 最小 二 乘 支 撑 向量 机 (Least Squares Support Vector Machine,LSSVM) 作为传统 SVM的一种修改版本 ,近年来 也产生了广泛的研究结果 。 。LSSVM有一个问题始终没 有解决:随着训练样本量的增加 ,LSSVM优化 问题 的求解将 会耗费大量时间。这主要是由于 LSSVM优化问题的求解方 式是通过拉格朗日(Lagrangian)法 转为其对偶优化问题 ,然 后再通过求解一个线性方程组来得到最后的解。由于求解线 性方程组的时间与样本数相关,时间复杂度为训练样本数的 三次方 ,当样本量很大时必然会耗费大量时间。 针对上述 LSSVM求解过程中的问题,本文提出了基于无 约束化的LSSVM优化问题求解算法,其求解过程采用了牛顿 优化 (Newton)法 j,称 该 方法 为 Newton—LSSVM。Newton— LSSVM首先把 LSSVM的优化问题转化为一个无约束的优化 问题,然后 分别求 出 目标 函数的梯度和海森矩 阵(Hessian Matrix)L s J,最后通过牛顿优化法来迭代求解。相对于传统的 LSSVM优化问题 的求解方式 ,Newton.LSSVM最显著的优势 是其求解过程的时间复杂度是样本维数的三次方,与训练样 本数无关 ,从而相对于传统方式大幅度减少 了训练时间的开 销,且该方法在减少时间开销的同时并不改变 LSSVM的泛化 能力。最后通过实验验证了该方法的有效性。 1 最小二乘支撑向量机 本文假定有一个由Ⅳ个样本组成的样本集 X =[X 一, X ],V R , R ,所有样本分属于两个不同的类 别 ,用 表示第 (K =1,2)类样本子集 ,其中共含有 个 样本 ,Y 表示样本 的类别标号,Vy ∈{1,一1}。LSSVM的 原始优化问题定义了如下: min÷w w+手∑e 2 (1) S.t.Y (W X +b)=1一e ;i=1,2,⋯,Ⅳ 其中 为正则参数。然后通过采用 Lagrangian 法,上面的优 化问题转化为求解如下的线性方程: [:日 ,][ [0 ] 其中,Y=[y 一,Y ], =[Ol 一,OL ],1=[1,⋯,1]都为 具有 Ⅳ个元素的列向量,J为N×N的单位矩阵,日为N×N 的矩阵,H =Yi),,IT ,。利用上面的得到的解 b 和 tl' = [ ,⋯, ],则可以得到 I_SSVM得决策函数为: )=sign(∑ y T +b ) (3) 可以看出,在求解LSSVM的过程中主要是需要求解线性 收稿日期:2009—12—15;修回日期:2010—02—06。 作者简介:熊福松(1982一),男,安徽滁州人,助教,硕士,主要研究方向:图像处理、模式识别; 王晓明(1978一),男,I~lJ JI简阳人,博士研究生 主要研究方向:人工智能、模式识别; 朱香卫(1965一),男,江苏连云港人,副教授,硕士,主要研究方向:网络安全、数字图像处理、数字水印。 maozeqiang 高亮 maozeqiang 高亮 maozeqiang 高亮 maozeqiang 高亮 maozeqiang 高亮 maozeqiang 高亮 maozeqiang 高亮 maozeqiang 高亮 maozeqiang 高亮 2298 计算机应用 第30卷 方程组(2)。由于该方程组的方程数随着样本数的增加而增 加,所以当训练样本较多时求解必然会花费较多的时间。一 般直接求解的时间复杂度为0(N3) ,即便使用了改进的方 法也与训练样本数相关,从而导致了其时间开销随着样本的 增加而迅速上升。 2 最小二乘支撑向量机的无约束优化 在这一部 分内容中,将讨论采用 牛顿优化法来 解决 LSSVM的优化问题,并称通过该方法来解 决优化问题 的 LSSVM为 Newton—LSSVM。 2.1 线性情况 首先,LSSVM的目标优化问题(1)可以改写为无约束的 优化形式: 、 1 min争w ’.,+÷∑(1一Yi(’‘, +6)) (4) 可以看出,上面的优化问题把 LSSVM的优化问题(1)置 于正则化框架下,其中两个参数之间的关系可以视为 A = 1/y。线性 LSSVM待求参数为W和b。下面将讨论 LSSVM优 化问题的求解,并设定了 =[ 】。假定: = ’., ’.,+÷∑(1一Yi(w +6)) (5) 则有: OM = A +耋(1 ( +6))( = Aw+∑( X +b—Yi) = Aw+x(XTw+be 一Y ) (6) OM : 蓦( )(1 ( ¨ 6))= ∑(w +b—Yi)=e(X W+be 一yT) (7) 其中:e=[1,⋯,1]∈R 和Y=[Y 一,y l_为行向量。从 而,根据式(6)和式(7)可得目标优化函数(5)的梯度为: V骨OM + XXT , 02M Ow = ‘ d'',db W+be 一Y )1 +妇 — ) J : Xe (8) _ _02M=eeT , 02M : (9) 从而海森矩阵可以表示为: r一02M 一 ] 口 = OW2 OZM JI=AI ] cto L 一 利用梯度式(8)和海森矩阵(10),可以得到牛顿优化法 的迭代公式为: ‘ 一 一 日 (11) 在更新过程中,如果 =1并且初始点距离最优点 w 较 远时,则所产生的点列可能不收敛于 。所以为了使得 算法收敛,可以通过一维搜索来解决这个问题。通常可以考 虑使用修正牛顿优化法,即上面的 通过一维搜索法 确 定。通过上面的牛顿优化法的迭代过程可以得到其最优解为 W 和 b ,则可以得到其决策函数为: _厂(X)=sign((W ) X+b ) (12) 至此,可以得到基 于牛顿优化法的线性 LSSVM求解过 程,具体步骤如下。 算法 1 线性 LSSVM 的牛 顿优 化法 (线 性 Newton— LSSVM)。 初始化:w。:[0,⋯,0] ,b。:0, :f 。1; b Repeat 计算 V = rw+ lr_v beT _ yT) e W 】和 (X + 一v ) 日:f A¨ 删 1; 【 eXT eP J’ step 一 H 一 : 通过一维搜索法得到 ; W = 1.,+ ’step ; Until达到最大循环次数或目标函数不再发生变化; 利用上面得 到的最优 解 W 和 b ,建立决策 函数式 (12)。 从上面的求解过程可以看出,该方法主要时间消耗在于 求解海森矩阵日的逆矩阵,但是该矩阵为(d+1)维,其中d 为数据样本的维数。一般情况下,求逆矩阵的时间复杂度为 0(d )。我们知道,一般情况下样本维数都大大小于样本数, 因而 0(d )大大低于 0(N3)。另一方面虽然牛顿优化法采用 了迭代的方式,但是实验显示,目标函数值随迭代过程下降非 常快 ,一般在几步之内就能达到指定的精度。因此,这两方面 正是导致 Newton—LSSVM算法能够大幅度减少求解优化问题 时间开销的直接原因。 2.2 非线性情况 对于非线性情况,一般情况下是首先通过定义一个非线 性映射函数 : 一 日把输入空间 映射到一个高维 Hilbert空间日(该空间也被叫做特征空间),然后再应用相应 的算法。首先,在特征空间中根据再生理论 有: W=∑/3 ( ) (13) 其中W∈H。然后根据线性 LSSVM的无约束优化问题(4), 可以得到非线性 LSSVM的无约束标优化问题为: min争∑∑/3 ( ) 妒( )+ Ⅳ ÷ (1一Yi(~./3/p(xj) (Xi)+6)) (14) 其中 ( )为样本点 X 在特征空间中所对应的样本点。利 用映射函数 妒定义核矩阵K: K . = ( ) ( ,) (15) 注意,核矩阵K具有对称半正定性。假定K =[K ,⋯, r,则优化问题(14)可以改写为: min 了1∑(1一Yi( +6)2 (16) 假定核矩阵 可逆,作变换 v: 卢,则可得卢=K Tv, 则有: min +÷ (1一 +6)) (17) 第9期 熊福松等:基于无约束优化的最小二乘支撑向量机 2299 其中 =K一寺 ,。需要注意的是 ,一般情况下核矩阵 都是 可逆的,如果不可逆,则通常可以采用K=K 77J的方式来处 理成可逆矩阵,其中,为单位矩阵,叼为一个很小的正数,如 "=10~。这样 ,非 线性 的 LSSVM 就转化 为 了一 个线性 LSSVM问题,则可以通过求解线性 LSSVM问题来解决非线 性 LSSVM的问题。最后,可以得到非线性 LSSVM的决策函 数为: _,( )=∑卢 ( ) ( )+b (18) 下面简要归纳了基于牛顿优化法的非线性 LSSVM的求 解步骤。 算法 2 非线性 LSSVM的牛顿优化法(非线性 Newton— LSSVM)。 1)根据式(15)建立核矩阵 K; 2●根据变换 = 一÷ 得到新的数据集 [ 一, ], 其中K = .K ,; J⋯ 3)对上面变换后的数据集 一, ]求解线性 LSSVM 问题 (17); 4)利用上面得到的解 和 b ,得到非线性 LSSVM的解 : K—Tv 和 b ; 5)根据上面的得到的非线性 LSSVM的解,建立其决策函 数式(18)。 3 实验结果及 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 本章将对文中提出的利用牛顿优化法来求解 LSSVM优 化问题的Newton—LSSVM算法的可行性和有效性进行实验研 究。实验 分为 两部 分。在第 一部 分实 验 中主要 比较 了 Newton—LSSVM和 LSSVM的训练时间;第二部分则选取了五 个 UCI【 数据集来测试 Newton—LSSVM和 LSSVM的泛化能力 和时间开销。实验环境 :操作系统为 Windows XP,开发平台 为 Matlab 7,内存为1.5 GB,CPU主频为2.93 GHz。 3.1 训练时间比较 在这个实验中,将对两种方法的训练时间进行 比较。实 验数据选用了 Pipeline数据L9 Pipeline数据共有 2000个 12 维样本,分为3类。本文选出了第 1和第2类的数据组成了 实验的所用数据集。实验的过程是首先从每一类数据中选出 若干个样本点共同组成训练数据集,然后分 别统计出采 用 Newton—LSSVM算法和 LSSVM算法进行训练时的训练时间。 在进行实验前,所有数据都把其每一维特征处理为均值为 0, 方差为 1。实验结果如图 1所示。注意,这里 Newton—LSSVM 训练时间很短,但并不为0。从中可以看出传统的 LSSVM算 法随着训练样本数的增加时间开销大迅速增加,然而 Newton— LSSVM 算 法 却 并 没 有 太 大 的 变 化,大 部 分 时 间 都 为 0.015625 s左右。这也验证 了前面文中所述 ,LSSVM 的传统 方法优化方法的时间复杂度为 O( ),与til练样本数相关 ; 然而本 Newton—LSSVM却为 O(d ),与样本的维数相关,而与 样本数无关。 一 个需要主要的问题是,尽管本文用来求解 LSSVM优化 问题的牛顿优化法中有迭代的过程,但是通过实验发现其迭 代的过程中目标函数的值下降非常快,一般几步就可达到指 定的精度。图2给出了 Newton—LSSVM算法存选出来的两类 数据集上训练时迭代过程中目标函数值的下降过程,从中可 以看出几乎一步迭代就使得目标函数的值下降到了一个非常 小的值。所以尽管文中算法采用了牛顿优化法中有迭代的过 程 ,但是其迭代收敛的过程非常快,这也是文中算法在时间开 销上很小的原因。 训练样本数 图 1 LSSVM和 Newton—LSSVM在不同训练样本数时的训练时问 星 皿 迭代次数 图2 Newton.LSSVM的目标函数值随迭代进行的收敛过程 3.2 UCI数据 这一部分的实验采用了五个 UCI 的数据来进行测试。 表 1给出这些数据的基本信息。在进行实验前,所有数据都 把其每一维特征处理为均值为0,方差为 1。实验采用了5重 交叉测试 精度作为泛化能力的度量标准。5重交叉测试 就是把数据样本平均划分为 5部分 ,进行 5次训练测试过程, 然后计算出这5次测试的平均测试精度。在第一次训练测试 过程中,把数据的第一部分作为测试数据集,剩下的数据集作 为训练数据集;第二次训练测试过程是把数据的第二部分数 据作为测试数据集 ,其他的数据集作为训练数据集。依照这 样的过程,直到所有五次训练测试过程做完。在本文中,就是 把这五次训练测试 的平均测试精度作为泛化性能的评估准 则。实验中对于 LSSVM的参数为正则参数 y为 0.01,从而 Newton—LSSVM的参数 A为 100。 表 1给出了5重交叉测试的平均精度和方差。从这些实 验结果可以看出,当采用本文的 Newton—LSSVM时,并不改变 其泛化能力,其得到的分类精度和 LSSVM传统的采用求解线 性方程的方式一样 ,这说明了该方法的在分类精度上的有效 性。但是在时间开销上,Newton—LSSVM大幅度低于传统的方 法。这说明了Newton—LSSVM最主要的优势在于其不会降低 LSSVM的泛化能力,但却能够大幅度减少时问开销。这一优 势正是工程应用最为需要的。 2300 计算机应用 第30卷 表 1 实验中UCI数据基本信息描述 表2 在 UCI数据上的5重交叉测试的测试结果 4 结语 本文针对最小二乘支撑向量机(LSSVM)优化问题的传 统解法是通过求解线性方程组的问题,提出了利用牛顿优化 法来解决优化问题 的 Newton—LSSVM算法。实验结果表明 了,相对于传统的LSSVM优化问题求解方式,该方法在大幅 度减少了 LSSVM算法的训练时间开销的同时,能够获得与采 用传统优化方式求解 LSSVM优化问题一样的泛化能力。但 是牛顿优化法只是一个局部最优的优化方法,研究一种全局 最优的迭代方法将是将来的工作方向之一。 参考文献: [1] VAPNIK V.Statistical learning theory【M].New York:Wiley, 1998. [2] CRISTIANINI N,TAYLOR J S.An introduction to support vector machines[M].Cambridge:Cambridge University Press,2000. [3] SCHOLKOOF B,SMOLA A.Learning with kernels[M].Cam- bridge,MA:MIT Press,2002. [4] GESTEL T V,SUYKENS J A K,BAESENS B,et a1.Benchmark— ing least squares suppoa vector machine classifiers[J].Machine Learning,2004,54(1):5—32. [5] ZHAO YONGPING,SUN JIANGUO.Recursive reduced least squares support vector regression[J】.Pattern Recognition,2009, 42(5):837—842. 【6】 JIAO LICHENG,BO LIEFENG,WANG LING.Fast sparse approx- imation for least squares support vector machine[J].IEEE Transae— tions on Neural Networks,2007,18(3):685—697. [7] YU LEAN,CHEN HUANHUAN,WANG SHOUYANG,et a1.E- volving least squares suppoa vector machines for stock market trend mining[J].IEEE Transactions on Evolutionary Computation,2009, 13(1):87—102. [8] CHAPELLE O.Training a support vector machine in the primal 【J】.Neural Computation,2007,19(5):1155—1178. [9] BLAKE E,MERZ C.UCI repository of machine learning databases 【EB/OL].[2009一O9—20].hnp://www.ics.uci.edtt/~ml— earn/MLRepository.htm1. [10]ABRIL L G,ANGULO C,VELASCO F,et a1.A note on the bias in SVMs for muhiclassification【J】.IEEE Transactions on Neural Networks,2008,19(4):723—725. (上接第2282页) PzSl & JR 只S S4 S5 最& S7 0 5 10 15 2O 25 30 35 4O 45 5O 55 6O 65 7O 75 80 85 90 9S 图4 优化调度 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 表3 不同算法结果对比 5 结语 本文对 MC供应链调度的主要方法进行了 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ,针对现 有方法的不足,引入异类多种群蚁群算法,设计了基于成本最 优的数学模型和进行模型求解的分布式供应链调度模型。通 过实验分析 ,该模型适应 MC供应链调度分布式计算的实际 要求,能快速准确地制订 MC供应链 的调度 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 。未来需要 进一步改进算法参数设置、扩大算法适用性,优化运算时间, 以应用于更大规模的供应链调度优化。 参考文献: . [1] 姚建明,周国华.大规模定制模式下供应链计划调度优化分析 [J].管理科学学报,2003,6(5):58—64. [2] 姚建明,蒲云.基于动态生产能力约束的MC模式下供应链调度 优化[J].系统工程,2005,23(2):25—30. [3】 王建华,李南,郭慧.敏捷供应链静态调度模型及其贪婪算法 【J】.计算机应用,2010,30(3):846—849. [4】 李昆鹏,马士华.ATO供应链中航空运输及并行机生产协调调 度问题[J].系统工程理论与实践,2007,27(12):7—15. [5] 王林平,贾振元,王福吉,等.多产品综合作业调度问题及其求解 [J】.系统工程理论与实践,2009,29(9):73—77. [6] 姜桦,李莉,乔非,等.蚁群算法在生产调度中的应用[J].计算机 工程,2005,31(5):76—78. [7] 胡燕海,马登哲,叶飞帆.制造系统通用作业计划与蚁群算法优 化[J].计算机集成制造系,2005,11(1):104—108. [8] 李斌,陈立平,黄正东,等.面向大规模定制的装配线优化调度研 究[J].中国机械工程,2005,16(24):32—34. [9] 孙靖,林杰.基于蚁群算法的大规模定制供应链调度优化研究 【J】.计算机应用,2006,26(11):2631—2634. f 10] ELLA BIB I,CALAMAI P,BASIR O A.Exchange strategies for multiple ant colony system[J].Information Sciences,2007,177 (5):1248—1264. [1 1]隆清琦,林杰.基于多 Agent的供应链分布式仿真系统设计与实 现[J].计算机应用,2009,29(9):2556—2558. 固 口 Ⅱ
本文档为【基于无约束优化的最小二乘支撑向量机】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_460924
暂无简介~
格式:pdf
大小:323KB
软件:PDF阅读器
页数:4
分类:高中语文
上传时间:2012-01-07
浏览量:27