Robust Least Squares Twin Support Vector Machine and Its Sparse Algorithm

doi:10.3778/j.issn.1002-8331.2203-0037

Abstract

Abstract: Least squares twin support vector machine（LSTSVM） solves two linear programming problems instead of solving complex quadratic programming problems. LSTSVM has the advantages of simple calculation and fast training speed. However, the hyperplanes obtained by LSTSVM are easily affected by outliers and the solution to LSTSVM lacks sparse. To solve this problem, a robust least squares twin support vector machine（R-LSTSVM） based on truncated least squares loss is proposed, and it verifies that the new model is robust to outliers in theory. Furthermore, in order to handle large-scale datasets, a sparse solution to the R-LSTSVM is obtained based on the representation theorem and incomplete Cholesky decomposition, and it proposes a sparse R-LSTSVM algorithm which is suitable for dealing with large-scale datasets with outliers. Numerical experiments show that compared with the existing algorithm, the classification accuracy, sparsity and convergence speed of the new algorithm are improved by 1.97%-37.7%, 26-199 times and 6.6-2 027.4 times, respectively.

Key words: robust least squares twin support vector machine, truncated least square loss function, incomplete Cholesky decomposition, representation theorem, sparse solution

摘要： 最小二乘孪生支持向量机通过求解两个线性规划问题来代替求解复杂的二次规划问题，具有计算简单和训练速度快的优势。然而，最小二乘孪生支持向量机得到的超平面易受异常点影响且解缺乏稀疏性。针对这一问题，基于截断最小二乘损失提出了一种鲁棒最小二乘孪生支持向量机模型，并从理论上验证了模型对异常点具有鲁棒性。为使模型可处理大规模数据，基于表示定理和不完全Cholesky分解得到了新模型的稀疏解，并提出了适合处理带异常点的大规模数据的稀疏鲁棒最小二乘孪生支持向量机算法。数值实验表明，新算法比已有算法分类准确率、稀疏性、收敛速度分别提高了1.97%~37.7%、26~199倍和6.6~2 027.4倍。

关键词: 鲁棒最小二乘孪生支持向量机, 截断最小二乘损失函数, 不完全Cholesky分解, 表示定理, 稀疏解

JIN Qifan, CHEN Li, XU Mingliang, JIANG Xiaoheng. Robust Least Squares Twin Support Vector Machine and Its Sparse Algorithm[J]. Computer Engineering and Applications, 2022, 58(18): 78-89.

靳启帆, 陈丽, 徐明亮, 姜晓恒. 鲁棒最小二乘孪生支持向量机及其稀疏算法[J]. 计算机工程与应用, 2022, 58(18): 78-89.

References

[1] CORTES C，VAPNIK V.Support-vector networks[J].Machine Learning，1995，20（3）：273-297.
[2] KHEMCHANDANI R，CHANDRA S.Twin support vector machines for pattern classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29（5）：905-910.
[3] ARUN KUMAR M，GOPAL M.Least squares twin support vector machines for pattern classification[J].Expert Systems with Applications，2009，36（4）：7535-7543.
[4] CHEN J，JI G R.Weighted least squares twin support vector machines for pattern classification[C]//The 2nd International Conference on Computer and Automation Engineering.Singapore：IEEE，2010：242-246.
[5] 储茂祥，王安娜，巩荣芬.一种改进的最小二乘孪生支持向量机分类算法[J].电子学报，2014，42（5）：998-1003.
CHU M X，WANG A N，GONG R F.Improvement on least squares twin support vector machine for pattern classification[J].Acta Electronice Sinica，2014，42 （5）：998-1003.
[6] 黄贤源，翟国君，隋立芬，等.LS-SVM 算法中优化训练样本对测深异常值剔除的影响[J].测绘学报，2011，40（1）：22-27.
HUANG X Y，ZHAI G J，SUI L F，et al.The influence of optimized train samples on elimination of sounding outliers in the LS-SVM arithmetic[J].Acta Geodaeticaet Cartographica Sinica，2011，40（1）：22-27.
[7] 郭战坤，金永威，梁小珍，等.基于异常值检测的港口集装箱吞吐量预测模型[J].数学的实践与认识，2019，49（17）：26-34.
GUO Z K，JIN Y W，LIANG X Z，et al.Prediction model of port container throughput based on outlier detection[J].Mathematics in Practice and Theory，2019，49（17）：26-34.
[8] SHEN X T，TSENG G C，ZHANG X G，et al.On ψ-learning[J].Journal of the American Statistical Association，2003，98（463）：724-734.
[9] WU Y C，LIU Y F.Robust truncated hinge loss support vector machines[J].Journal of the American Statistical Association，2007，102（479）：974-983.
[10] WANG K，ZHONG P.Robust non-convex least squares loss function for regression with outliers[J].Knowledge-Based Systems，2014，71：290-302.
[11] YANG X，TAN L，HE L.A robust least squares support vector machine for regression and classification with noise[J].Neurocomputing，2014，140：41-52.
[12] 安亚利，周水生，陈丽，等.鲁棒支持向量机及其稀疏算法[J].西安电子科技大学学报，2019，46（1）：64-72.
AN Y L，ZHOU S S，CHEN L，et al.Robust support vector machines and their sparse algorithms[J].Journal of Xidian University，2019，46（1）：64-72.
[13] SUYKENS J A，LUKAS L，VANDEWALLE J.Sparse approximation using least squares support vector machines[C]//The 2000 IEEE International Symposium on Circuits and Systems，2000：757-760.
[14] ZENG X Y，CHEN X W.SMO-based pruning methods for sparse least squares support vector machines[J].IEEE Transactions on Neural Networks，2005，16（6）：1541-1546.
[15] LI Y，LIN C，ZHANG W.Improved sparse least-squares support vector machine classifiers[J].Neurocomputing，2006，69（13/15）：1655-1658.
[16] 刘小茂，孔波，高俊斌，等.一种稀疏最小二乘支持向量分类机[J].模式识别与人工智能，2007，20（5）：681-687.
LIU X M，KONG B，GAO J B，et al.A sparse least support vector machine classifier[J].Intelligence Pattern Recognition and Artificial，2007，20（5）：681-687.
[17] JIAO L，BO L，WANG L.Fast sparse approximation for least squares support vector machine[J].IEEE Transactions on Neural Networks，2007，18（3）：685-697.
[18] DE BRABANTER K，DE BRABANTER J，SUYKENS J，et al.Optimized fixed-size kernel models for large data sets[J].Computational Statistics and Data Analysis，2010，54（6）：1484-1504.
[19] ZHOU S S.Sparse LSSVM in primal using Cholesky factorization for large scale problems[J].IEEE Transactions on Neural Networks and Learning Systems，2016，27（4）：783-795.
[20] SHALEV-SHWARTZ S，BEN-DAVID S.Understanding machine learning：from theory to algorithms[M].[S.l.]：Cambridge University Press，2014.
[21] SCH?LKOPF B，HERBRICH R，SMOLA A J.A generalized representer theorem[C]//International Conference on Computational Learning Theory.Berlin，Heidelberg：Springer，2001：416-426.
[22] YUILLE A，RANGARAJAN A.The concave-convex procedure[J].Neural Computation，2003，15（4）：915-936.
[23] GEMAN D，YANG C D.Nonlinear image recovery with half-quadratic regularization[J].IEEE Transactions on Image Processing，1995，4（7）：932-946.
[24] NIKOLOVA M，NG M K.Analysis of half-quadratic minimization methods for signal and image recovery[J].SIAM Journal on Scientific Computing，2005，27（3）：937-966.
[25] HE B，YUAN X.On the [O(1/n)] convergence rate of the Douglas-Rachford alternating direction method[J].SIAM Journal on Numerical Analysis，2012，50（2）：700-709.
[26] 业巧林，闫贺.基于最小二乘的孪生有界支持向量机分类算法[J].华中科技大学学报（自然科学版），2018，46（3）：30-35.
YE Q L，YAN H.Least squares based twin bounded support vector machine classification algorithm[J].Journal of Huazhong University of Science & Technology（Natural Science Edition），2018，46（3）：30-35.
[27] CHEN L，ZHOU S S.Sparse algorithm for robust LSSVM in primal space[J].Neurocomputing，2018，275：2880-2891.