大规模稀疏支持向量机算法研究

发布时间：2018-01-19 01:15

本文关键词： 大规模稀疏学习支持向量机最优化损失函数数据挖掘分类问题　出处：《北京交通大学》2017年博士论文　论文类型：学位论文

【摘要】：稀疏学习是一种有效处理冗余问题的方法。目前,稀疏优化方法已广泛应用于信号压缩感知、图像处理等实际问题中,其理论和算法都在快速发展中。由于大规模数据挖掘问题往往具有冗余和稀疏的特点,因此稀疏优化是处理大规模数据挖掘问题的上佳之选。而支持向量机作为通用的机器学习方法,具有坚实的统计学习理论基础,实际应用效果好,使用方便,模型参数较少,在图像、视频、声音、文本等不同领域得到了广泛的应用。国内外关于大规模稀疏支持向量机的理论研究和方法并不成熟,缺乏理论基础和模型算法,尚处于初始阶段。比如:1)稀疏模型的有效性检验指标,即如何度量模型的稀疏程度以及稀疏效果的好坏问题等;2)大规模问题的稀疏模型缺乏统一的理论基础;3)大规模问题的稀疏优化模型求解问题;4)拓展研究比较少,对其拓展有较大空间。我们拟从最优化的角度对上述多方面进行系统研究。本文共分七章,组织结构如下:第一章为引言部分,介绍本文的研究背景、研究意义、研究对象和主要工作概述。第二章详细介绍与本文研究内容密切相关的算法,包括标准的支持向量机(SVM)、最小二乘支持向量机(LSSVM)、基于Ramp损失函数的支持向量机(RSVM)、双子支持向量机(TWSVM)、非平行支持向量机(NPSVM),并比较分析了他们的优缺点。由于NPSVM具有更好的推广能力,后面的研究内容则重点围绕NPSVM展开,一方面从理论上探索其统计学习理论基础,另一方面从方法上构建更稀疏的、能处理大规模问题的NPSVM模型和算法。第三章针对分类问题,提出一个具有稀疏性和鲁棒性的非平行超平面分类机—基于Ramp损失函数的非平行超平面SVM(RNPSVM)。RNPSVM在训练阶段可以处理含有噪音和异常点的数据,并含有较少的支持向量,从而增加了模型的稀疏程度,具有更好的推广能力。针对该模型中非凸优化问题的求解,我们引入了有效的CCCP策略。进一步,对该模型的稀疏性、复杂度、初始化等进行了理论分析,大量的数值实验也验证了该模型的有效性。第四章从U-SVM的角度构建了NPSVM的结构风险最小化原则,给出了其相应的统计学习理论解释。之后从提升计算效率的角度出发,分别给出了基于线性规划形式的NPSVM和基于线性规划形式的RNPSVM,为NPSVM方法处理更大规模的问题提供了可选择的模型。第五章首先讨论了 LSTWS VM和LSS VM的关系,证明LSS VM是LSTWS VM的退化情况。进一步,基于LSSVM,提出了一个新的稀疏和鲁棒的最小二乘支持向量机RLSSVM。在原有稀疏模型ε-LSSVM基础上,构建并引入了一个新的基于ε-不敏感损失函数的Ramp损失函数,新模型可以有效地对噪音抗干扰,并且具有更好的稀疏性。引入了CCCP策略来求解该模型中非凸优化问题,不同数据集上的数值实验证明了RLSSVM的有效性。第六章基于前面的NPS VM和RNPS VM,提出针对大规模线性分类问题的交替方向乘子法(ADMM),ADMM是目前处理大规模问题的有效优化算法。通过将NPSVM和RNPS VM中的优化问题构造为ADMM可以求解的形式,实现了ADMM在这两个算法上的应用。大量的实验证明了算法的有效性。最后一章总结了本文的主要工作以及取得的成果,并提出了进一步的研究方向。
[Abstract]:Sparse learning is an effective method for treatment of redundant problems. At present, the sparse optimization method has been widely used in signal compressed sensing, image processing and other practical problems, the theory and algorithm are in rapid development. Because of the characteristics of large-scale data mining problems is often redundant and sparse, and sparse optimization is the best choice to deal with large-scale the problem of data mining. And the support vector machine as a general machine learning method, has a solid statistical learning theory, the practical application effect is good, easy to use, model parameter, in the image, video, sound, text and other different fields. It has been widely applied at home and abroad on the theory and method of large scale sparse support vector machine is not mature, lack of theoretical basis and model algorithm, is still in the initial stage. For example: 1) test validity index sparse model, namely how to measure model The sparse degree and sparse effect quality problems; 2) sparse model of large-scale problems the lack of theoretical basis; 3) sparse optimization model for solving large-scale problems; 4) expand the research is relatively small, there is a large space for its development. We have to carry out systematic research on these aspects from the optimization point in this paper. The organizational structure is divided into seven chapters, as follows: the first chapter is the introduction part, introduces the research background, research significance, research object and main works are summarized. The second chapter introduces the research content closely related algorithms, including the standard support vector machine (SVM), least squares support vector machine (LSSVM), support vector Ramp based on loss function (RSVM), twin support vector machine (TWSVM), non parallel support vector machine (NPSVM), and compare their advantages and disadvantages are analyzed. Because NPSVM has better generalization ability, behind The research content mainly around the NPSVM, on the one hand to explore the theoretical basis of learning from the statistical theory, on the other hand, the construction method from more sparse, NPSVM model and algorithm can handle large-scale problems. The third chapter according to the classification problem, this paper proposes a sparse and robust non parallel hyperplanes classifier Ramp loss function based on non parallel hyperplanes SVM (RNPSVM) to deal with noise and outliers in the data can be in the training phase.RNPSVM, support vector and contains less, thus increasing the degree of sparsity model, has better generalization ability. For solving non convex optimization problem in the model, we introduce effective the strategy of CCCP. Further, the sparsity and complexity of the model, initialization is analyzed, a large number of numerical experiments have verified the validity of the model. In the fourth chapter, from the perspective of U-SVM. The structural risk minimization principle NPSVM, explain the statistical learning theory. From the efficiency point of view, are given based on NPSVM linear programming form and linear programming based on the form of RNPSVM, the choice of model for the NPSVM method to handle larger scale problems. The fifth chapter discussed the relationship between LSTWS VM and LSS VM, LSS VM LSTWS that is a degenerate case of VM. Further, based on LSSVM, proposes a new sparse least squares and robust support vector machine RLSSVM. in the original model based on sparse epsilon -LSSVM, constructed and introduced a Ramp loss function insensitive loss function based on the new model can effectively resist interference to noise, and has better sparsity. Using CCCP method to solve the model of non convex optimization problem on the set of different numerical data The experiment proves the validity of the RLSSVM. The sixth chapter is based on the front of the NPS VM and RNPS VM, is proposed to solve the classification problem of large-scale linear alternating direction method of multipliers (ADMM, ADMM) is an effective optimization algorithm currently dealing with large-scale problems. Through the optimization of NPSVM and RNPS in VM structure for ADMM can be solved in the form of and realizes the application of ADMM in these two algorithms. Experiments prove the effectiveness of the algorithm. The last chapter summarizes the main work and achievements, and puts forward the direction of further research.

【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】