基于DC规划方法的稀疏临近支持向量机

doi:10.15960/j.cnki.issn.1007-6093.2020.03.009

运筹学学报 ›› 2020, Vol. 24 ›› Issue (3): 115-126.doi: 10.15960/j.cnki.issn.1007-6093.2020.03.009

基于DC规划方法的稀疏临近支持向量机

杨琳希, 李国权^*

重庆师范大学数学科学学院, 重庆 401331

收稿日期:2019-12-13 发布日期:2020-09-05
通讯作者: 李国权 E-mail:ligq@cqnu.edu.cn
基金资助:
国家自然科学基金（No.11871128），重庆市自然科学基金（Nos.cstc2019jcyj-msxmX0282，cstc2019jcyj-msxmX0368），重庆市教委科技项目（No.KJQN201900531）

Sparse proximal support vector machines via DC programming

YANG Linxi, LI Guoquan^*

School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China

Received:2019-12-13 Published:2020-09-05

摘要/Abstract

摘要： 为了提高临近支持向量机（PSVM）的数值表现，在PSVM的模型中引入了$\ell_0$-范数正则项，提出了稀疏临近支持向量机模型（SPSVM），从而提高分类器的特征选择能力。然而带有$\ell_0$-范数正则项的问题往往是NP-难问题，为了克服这一问题，采用非凸连续函数近似$\ell_0$-范数，并通过适当的DC分解将问题转化成DC规划问题进行求解，同时还讨论了算法的收敛性。数值实验结果表明不论是在仿真数据还是在实际数据中，所提出的方法是比较有效稳定的。

关键词: 临近支持向量机, 稀疏优化, DC规划, 特征选择

Abstract: To improve the performance of proximal support vector machine, a new sparse proximal support vector machine is proposed in this paper where $\ell_0$-norm regularization is used to improve the feature selection ability of the new model. However, problem with $\ell_0$-norm regularization usually is NP-hard. To overcome this difficulty, a continuous nonconvex function is used to approximate $\ell_0$-norm. With proper DC decomposition, we transform the problem into a DC programming problem which can be solved efficiently by DC algorithm. Meanwhile, we also discuss the convergence properties of our algorithm. The experimental results on both simulated and real datasets demonstrate the efficiency of the proposed algorithms.

Key words: proximal support vector machine, sparse optimization, difference of convex functions programming, feature selection

中图分类号:

O224
TP181

杨琳希, 李国权. 基于DC规划方法的稀疏临近支持向量机[J]. 运筹学学报, 2020, 24(3): 115-126.

YANG Linxi, LI Guoquan. Sparse proximal support vector machines via DC programming[J]. Operations Research Transactions, 2020, 24(3): 115-126.

参考文献

[1] Burges C J. A tutorial on support vector machines for pattern recognition[J]. Data Mining and Knowledge Discovery, 1998, 2:1-43.
[2] 唐静静, 田英杰. 基于间隔迁移的多视角支持向量机[J]. 运筹学学报, 2018, 22(3):1-14.
[3] 邵元海, 杨凯丽, 刘明增, 等. 从支持向量机到非平行支持向量机[J]. 运筹学学报, 2018, 22(2):55-65.
[4] Mangasarian O L, Wild E W. Multisurface proximal support vector machine classification via generalized eigenvalues[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28:69-74.
[5] Shao Y H, Deng N Y, Chen W J, et al. Improved generalized eigenvalue proximal support vector machine[J]. IEEE Signal Processing Letters, 2013, 20:213-216.
[6] Guarracino M R, Cifarelli C, Seref O, et al. A classification method based on generalized eigenvalue problems[J]. Optimization Methods and Software, 2007, 22:73-81.
[7] Zhang L, Zhou W. On the sparseness of $\ell_1$-norm of support vector machine[J]. Neural Networks, 2010, 23:373-385.
[8] Neumann J, Schnorr C, Steidl G. Combined SVM-based feature selection and classification[J]. Machine Learning, 2005, 61:129-150
[9] Weston J, Elisseeff A, Scholkopf B. Use of the zero-norm with linear models and methods[J]. Journal of Machine Learning Research, 2003, 3:1439-1461.
[10] Shao Y H, Li C N, Liu M Z, Wang Z, Deng N Y. Sparse $\ell_q$-norm least squares support vector machine with feature selection[J]. Pattern Recognition, 2018, 78:167-181.
[11] Le Thi H A, H Minh Le, Phan D N. Feature selection in machine learning:an exact penalty approach using a Difference of Convex function algorithm[J]. Machine Learning, 2015, 101:163-186.
[12] Gotoh J, Takeda A, Tono K. DC formulations and algorithms for sparse optimization problems[J]. Mathematical Programming, Ser. B, 2018, 169:141-176.
[13] Pappu V, Panagopoulos O P, Xanthopoulos P, et al. Sparse Proximal Support Vector Machines for feature selection in high dimensional datasets[J]. Expert Systems With Applications, 2015, 42:9183-9191.
[14] Le Thi H A, Phan D N. DC programming and DCA for sparse optimal scoring problem[J]. Neurocomputing, 2016, 186:178-181.
[15] Phan D N, Le Thi H A. Convex analysis approach to D.C. programming:theory, algorithms and applications[J]. Acta Mathematical Vietnamic, 1997, 22:289-355.
[14] Bazaraa M S, Sherali H D, Shetty C M. Nonlinear Programming Theory and Algorithms (Third Edition)[M]. New Jersey:John Wiley and Sons, 2006.
[16] Fan R E, Chang K W, Hsieh C J, et al. LIBLINEAR:A library for large linear classification[J]. Journal of Machine Learning Research, 2008, 9:1871-1874.
[17] Golub T R, Slonim D K, Tamayo P, et al. Molecular classification of cancer:class discovery and class prediction by gene expression monitoring[J]. Science, 1999, 286:531-537.
[18] Alon U, Barkai N, Notterman D A, et al. Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays[J]. Proceedings of the National Academy of Sciences, 1999, 96:6745-6750.
[19] Schlimmer J. Mushroom Records Drawn from the Audubon Society Field Guide to North American Mushrooms[M]. New York:GH Lincoff (Pres), 1981.
[20] Mesejo P, Pizarro D, Abergel A, et al. Computer-Aided Classification of Gastrointestinal Lesions in Regular Colonoscopy[J]. IEEE Transactions on Medical Imaging, 2016, 35:2051-2063.
[21] Sigillito V G, Wing S P, Hutton L V, et al. Classification of radar returns from the ionosphere using neural networks[J]. Johns Hopkins APL Technical Digest, 1989, 10:262-266.
[22] Street W N, Mangasarian O L, Wolberg W H. An inductive learning approach to prognostic prediction[C]//International Conference on Machine Learning, 1995, 522-530.
[23] Street W N, Wolberg W H, Mangasarian O L. Nuclear feature extraction for breast tumor diagnosis[C]//Proceedings of SPIE-The International Society for Optical Engineering, 1993, 861-870.

基于DC规划方法的稀疏临近支持向量机

Sparse proximal support vector machines via DC programming

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	赵晨, 罗自炎, 修乃华. 稀疏优化理论与算法若干新进展[J]. 运筹学学报, 2020, 24(4): 1-24.
[2]	文再文,印卧涛,刘歆,张寅. 压缩感知和稀疏优化简介[J]. 运筹学学报, 2012, 16(3): 49-64.