CASIA OpenIR  > 毕业生  > 博士学位论文
最小包含球算法及其在支持向量机中应用的研究
其他题名Study on Minimum Enclosing Ball Algorithm and its Applications in Support Vector Machine
王永庆
2008-12-31
学位类型工学博士
中文摘要支持向量机(SVM)问题和最小包含球(MEB)问题,虽然二者的研究背景和问题的原始描述不同,但它们都是可以通过引入拉各朗日乘子,由对偶理论转换为约束条件更简单的凸二次规划问题。由于该问题的最优解具有全局性,因此在二次规划问题中对它的研究有重要的意义。本文在凸二次规划问题的框架下对上述两个问题进行了探讨和研究。 SVM的几何解释理论曾指出:在两个给定的点集间寻找最大间隔平面等价于在包含两类点集的的两个最小凸壳中寻找一对最近点。从那以后,很多学者探讨研究了不同范数意义下的分隔超平面,并声称:优化问题在L1<下标!>范数意义下获得的分隔超平面比在传统L2<下标!>范数意义下获得的分隔超平面的训练时间更短,对外点的稳健性更好。本文借鉴了相关的研究工作,在不同的范数下探讨了MEB和SVM的对偶形式,并给出了二者在L1<下标!>、Linfty<下标!>范数下的对偶等价。 此外,本文还就MEB已有算法进行了有益地改进,提出了两种启发式的迭代算法,并从理论分析和实验结果上对比了所提算法与已有 算法的性能优劣。 在本文中,主要的工作和贡献有: 1)给出了SVM问题与MEB问题在L1<下标!>、Linfty<下标!>范数下的对偶等价,并指出:二类软间隔L1--MEB和二类硬间隔MEB在L1<下标!>(Linfty<下标!>)范数下的间隔平面优化问题的对偶问题分别是二类软间隔L1--SVM和二类硬间隔SVM在L1<下标!>(Linfty<下标!>)范数下的间隔平面优化问题的对偶问题的特例,为后续的研究提供了理论基础。 2)利用线性规划方法在L1<下标!>、Linfty<下标!>范数下对MEB问题进行求解,获得了比在L2<下标!>范数下训练时间更短、稳健性更好的训练过程,使得在不同范数下讨论MEB问题具有了一定的现实意义。 3)提出了一种基于优化软件包的改进的MEB算法,在根据与当前球心距离最远的原则向当前核心集增加核心向量的同时,再根据有理论上保证算法收敛的去点原则来缩减当前核心集,从而使得当前核心集规模最小,为后继的迭代减少计算复杂度。我们通过理论分析和实验证得到结论:在基本不改变支持向量、不降低分类正确率的前提下,该方法可以获得更少的核心向量,从而降低计算过程中的空间复杂度和时间复杂度,因此更加适合大规模数据的增量学习和数据约简。 4)提出了一种不基于优化软件包的更简单的MEB算法,通过放宽对核函数的要求,获得了一种半径在逐渐扩张的更简单的MEB算法,并使得该方法在核方法中的潜在应用范围更广;同时,我们还给出了该算法的收敛性证明,也从理论上对其空间、时间复杂度进行了分析;最后,通过实验,我们得出了与其他算法相比,本文提出的更简单的MEB算法更加适合解决较大规模的数据集。 总的说来,本文在SVM问题与MEB问题的联系以及MEB算法的改进方面作了有益的探索和研究。
英文摘要Due to the global optimum, studying the convex quadratic programming problem is of great significance to the quadratic programming problem. In this thesis, we discuss and study SVM and MEB within the framework of convex quadratic programming. From the geometric interpretation theory of SVM on, many researchers explored the margin hyperplane in the sense of different norms, they claimed that: the margin hyperplane attained in the sense of L1<下标!> norm in optimization problem compared to the one attained in the sense of conventional L2<下标!> norm, is of less training time and more robust to outliers. In this dissertation, the main work and contribution including: 1) We present the dual equivalence of MEB and SVM in the sense of L1<下标!> and Linfty<下标!> norms, and point out that: the dual problems of margin hyperplane optimization problem in two-class soft margin L1--MEB and two-class hard margin MEB in the sense of L1<下标!>(Linfty<下标!>) norm is the special case of the dual problems of margin hyperplane optimization problem in two-class soft margin L1--SVM and two-class hard margin SVM in the sense of L1<下标!>(Linfty<下标!>) norm, respectively, which provides theoretical fundamentals for subsequent study. 2) We solve the MEB problem in the sense of L1<下标!> and Linfty<下标!> norms by using linear programming, and attain a training process with less training time and more robustness, and hence discussing MEB in the sense of different norms is of some practical sense. 3) We propose an optimization toolbox--based improved MEB algorithm, which adds the furthest point away from the current center as the core vector to the current core-set. At the same time, we reduce the current core sets by a theoretical guaranteed dropping principle, by which we can guarantee the minimal volume of current core-set, and hence lessen the computational complexities for the subsequent iterations. We also provide theoretical analysis about the space and time complexities of the proposed algorithm, and then we compared it with other MEB algorithms through experiments. 4) We propose a non--optimization toolbox--based improved MEB algorithm by relaxing the requirement on kernel function, which achieved an simpler MEB algorithm where the radius is expanded incrementally. Hence, the proposed algorithm can solve more extensive kernel methods. We also provide theoretical proof on convergence and analysis about the space and time complexities of the proposed algorithm, and then we come to the conclusion that the proposed algorithm is more suitable to handle larger data sets with comparative accuracies by comparing with other MEB algorithms through experiments. In a word, in this thesis, we have made profitably exploration and research both on the connection between the SVM and MEB problem and the improvement of MEB algorithms.
关键词支持向量机 最小包含球 凸二次规划 近似算法 对偶理论 Support Vector Machine Minimum Enclosing Ball Convex Quadratic Programming Approximate Algorithm Duality Theory
语种中文
文献类型学位论文
条目标识符http://ir.ia.ac.cn/handle/173211/6137
专题毕业生_博士学位论文
推荐引用方式
GB/T 7714
王永庆. 最小包含球算法及其在支持向量机中应用的研究[D]. 中国科学院自动化研究所. 中国科学院研究生院,2008.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
CASIA_20051801462801(3645KB) 暂不开放CC BY-NC-SA
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[王永庆]的文章
百度学术
百度学术中相似的文章
[王永庆]的文章
必应学术
必应学术中相似的文章
[王永庆]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。