原始空间中孪生支持向量机的大规模优化算法研究

Twin Support Vector Machines (TWSVM), a new extension of Support Vector Machine (SVM), is one of the research hotspots in recent years. Since it is a relatively new theory in data mining, there are still some problems to be further researched and improved, such as the speed of solving large-scale problems is still not fast enough. This project mainly studies the large-scale optimization algorithms of twin support vector machines in the primal space. Its main contents are as follows:(1) Based on the fact that the objective function of twin support vector machine is the sum of differentiable convex function and non-differentiable convex function, the subgradient algorithm among nonsmooth optimization algorithms are used to solve TWSVM. This algorithm has simple structure and small computational complexity, and is suitable for solving large-scale problems; (2) Based on the fact that the non-differentiable term of the objective function of twin support vector machines is not differentiable on a hyperplane, the primal optimization problem is divided into two cases: the non-differentiable term is zero or not zero. The conjugate gradient method is used to solve the problem in above two cases flexibly. This algorithm has the advantages of small storage, good stability, fast convergence speed and quadratic termination. It is also suitable for solving large-scale problems. The aim of this project is to provide fast and effective algorithms and strong theoretical support for twin support vector machines for large-scale problems. In addition, the effectiveness of the proposed methods will be verified by experiments.

孪生支持向量机是支持向量机的一种新的拓展，是近年来的研究热点之一。但由于其是数据挖掘中相对较新的理论，还存在一些有待进一步研究和改进的问题，比如对大规模问题求解速度依然不够快。本项目主要研究原始空间中孪生支持向量机的大规模优化算法，主要内容包括:(1)利用孪生支持向量机目标函数是可微凸函数和不可微凸函数之和的特点，采用非光滑优化算法中的次梯度算法对孪生支持向量机进行求解。该算法结构简单，计算量小，适合求解大规模问题;(2)利用孪生支持向量机目标函数的不可微项仅在一个超平面上不可微的特点，将原始优化问题分成不可微项为0和不可微项不为0两种情况，灵活使用共轭梯度法对其求解。该算法所需存储量小，稳定性好，且有较快的收敛速度和二次终止性等优点，也适合求解大规模问题。本项目将对孪生支持向量机用于大规模问题提供快速有效的求解算法以及强有力的理论支持。本项目还将通过实验验证所提方法的有效性。

孪生支持向量机是在支持向量机的基础上改进的一种新的非常有效的机器学习算法，其训练速度大约时支持向量机的四倍，但还存在一些有待进一步研究和改进的问题，比如对大规模问题求解速度依然不够快等缺点。本项目主要研究原始空间中孪生支持向量机的大规模优化算法，主要内容包括两方面:(1)利用孪生支持向量机目标函数是可微凸函数和不可微凸函数之和的特点，研究次梯度算法，随机次梯度算法及小批量次梯度算法加速孪生支持向量机的求解。该算法结构简单，计算量小，可有效求解大规模问题;(2)利用孪生支持向量机目标函数的不可微项仅在一个超平面上不可微的特点，将原始优化问题分成不可微项为0和不可微项不为0两种情况，灵活使用共轭梯度法对其求解。该算法所需存储量小，稳定性好，且有较快的收敛速度，也可有效求解大规模问题。本项目对孪生支持向量机用于大规模问题提供快速有效的求解算法以及强有力的理论支持。本项目还通过实验验证所提方法的有效性。