基于QR分解的稀疏LSSVM算法
|
摘要
传统最小二乘支持向量机(LSSVM)一般通过随机选择部分样本得到核矩阵的低秩近似提高解的稀疏性,为了使该近似分解用尽可能小的低秩矩阵更好地近似原核矩阵,提出一种基于正交三角(QR)分解的QRP-LSSVM稀疏算法.采用QR分解保持正交的特性挑选差异更大的样本,迭代地精选核矩阵的部分列得到核矩阵的Nystr9m型低秩近似,并利用分解结果快速求得最小二乘支持向量机的稀疏解.实验分析表明,该算法在不牺牲分类性能的前提下可得到更稀疏的解,甚至在稀疏水平不超过0.05%的情况下准确率也较高,可有效解决大规模训练问题.
The traditional least squares support vector machine(LSSVM)obtained the low rank of kernel matrix by randomly choosing apart of samples to improve the sparsity of solution.In order to make the approximate decomposition of low rank matrix as small as possible to approximate the original kernel matrix,we proposed QRP-LSSVM sparse algorithm based on QR factorization.Using the orthogonal feature of QR factorization to choose some samples with a big diversity,we iteratively selected some columns of the kernel matrix to get Nystr9 m type low rank approximation of kernel matrix,and used decomposition results to get the sparse solution of LSSVM quickly.The experimental analyses show that the proposed algorithm can get more sparse solutions without sacrificing the classification performance,and even get higher accuracy with the sparsity level less than 0.05%,and it can solve large-scale training problems effectively.
The traditional least squares support vector machine(LSSVM)obtained the low rank of kernel matrix by randomly choosing apart of samples to improve the sparsity of solution.In order to make the approximate decomposition of low rank matrix as small as possible to approximate the original kernel matrix,we proposed QRP-LSSVM sparse algorithm based on QR factorization.Using the orthogonal feature of QR factorization to choose some samples with a big diversity,we iteratively selected some columns of the kernel matrix to get Nystr9 m type low rank approximation of kernel matrix,and used decomposition results to get the sparse solution of LSSVM quickly.The experimental analyses show that the proposed algorithm can get more sparse solutions without sacrificing the classification performance,and even get higher accuracy with the sparsity level less than 0.05%,and it can solve large-scale training problems effectively.
引文
[1]Ferreira L V,Kaszkurewicz E,Bhaya A.Solving Systems of Linear Equations via Gradient Systems with Discontinuous Right Hand Sides:Application to LS-SVM[J].IEEE Transactions on Neural Networks,2005,16(2):501-505.
[2]承泽恩.基于k近邻和最小二乘支持向量机的Android恶意行为识别[J].吉林大学学报(理学版),2015,53(4):720-724.(CHENG Ze’en.Identification of Android Malicious Behaviors Based on k Nearest Neighbor Algorithm and Least Squares Support Vector Machin[J].Journal of Jilin University(Science Edition),2015,53(4):720-724.)
[3]Suykens J A K,Vandewalle J.Least Squares Support Vector Machine Classifiers[J].Neural Processing Letters,1999,9(3):293-300.
[4]Suykens J A K,Lukas L,Vandewalle J.Sparse Approximation Using Least Squares Support Vector Machines[C]//Proceedings of IEEE International Symposium on Circuits and Systems.Piscataway,NJ:IEEE,2000:757-760.
[5]Suykens J A K,Brabanter J D,Lukas L,et al.Weighted Least Squares Support Vector Machines:Robustness and Sparse Approximation[J].Neural Computation,2002,48(1/2/3/4):85-105.
[6]甘良志,孙宗海,孙优贤.稀疏最小二乘支持向量机[J].浙江大学学报(工学版),2007,41(2):245-248.(GAN Liangzhi,SUN Zonghai,SUN Youxian.Sparse Least Squares Support Vector Machines[J].Journal of Zhejiang University(Engineering Science),2007,41(2):245-248.)
[7]JIAO Licheng,BO Liefeng,WANG Ling.Fast Sparse Approximation for Least Squares Support Vector Machine[J].IEEE Transactions on Neural Networks,2007,18(3):685-697.
[8]ZHOU Shuisheng.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.
[9]Smola A J,Sch9lkopf B.Sparse Greedy Matrix Approximation for Machine Learning[C]//Proceedings of the17th International Conference on Machine Learning.San Francisco:Morgan Kaufmann,2000:911-918.
[10]Drineas P,Mahoney M W.On the Nystr9m Method for Approximating a Gram Matrix for Improved Kernel-Based Learning[J].Journal of Machine Learning Research,2005,6:2153-2175.
[11]Higham N J.Analysis of the Cholesky Decomposition of a Semi-definite Matrix[C]//Reliable Numerical Computation.Oxford,UK:Oxford University Press,1990:161-185.
[12]Smola A J,Bartlett P.Sparse Greedy Gaussian Process Regression[C]//Proceedings of the 13th International Conference on Neural Information Processing Systems.Cambridge:MIT Press,2000:598-604.
[13]Keerthi S S,Chapelle O,Decoste D.Building Support Vector Machines with Reduced Classifier Complexity[J].Journal of Machine Learning Research,2006,7:1493-1515.
[14]Scholkopf B,Smola A J.Learning with Kernels:Support Vector Machines,Regularization,Optimization,and Beyond[M].Cambridge:MIT Press,2003.
[2]承泽恩.基于k近邻和最小二乘支持向量机的Android恶意行为识别[J].吉林大学学报(理学版),2015,53(4):720-724.(CHENG Ze’en.Identification of Android Malicious Behaviors Based on k Nearest Neighbor Algorithm and Least Squares Support Vector Machin[J].Journal of Jilin University(Science Edition),2015,53(4):720-724.)
[3]Suykens J A K,Vandewalle J.Least Squares Support Vector Machine Classifiers[J].Neural Processing Letters,1999,9(3):293-300.
[4]Suykens J A K,Lukas L,Vandewalle J.Sparse Approximation Using Least Squares Support Vector Machines[C]//Proceedings of IEEE International Symposium on Circuits and Systems.Piscataway,NJ:IEEE,2000:757-760.
[5]Suykens J A K,Brabanter J D,Lukas L,et al.Weighted Least Squares Support Vector Machines:Robustness and Sparse Approximation[J].Neural Computation,2002,48(1/2/3/4):85-105.
[6]甘良志,孙宗海,孙优贤.稀疏最小二乘支持向量机[J].浙江大学学报(工学版),2007,41(2):245-248.(GAN Liangzhi,SUN Zonghai,SUN Youxian.Sparse Least Squares Support Vector Machines[J].Journal of Zhejiang University(Engineering Science),2007,41(2):245-248.)
[7]JIAO Licheng,BO Liefeng,WANG Ling.Fast Sparse Approximation for Least Squares Support Vector Machine[J].IEEE Transactions on Neural Networks,2007,18(3):685-697.
[8]ZHOU Shuisheng.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.
[9]Smola A J,Sch9lkopf B.Sparse Greedy Matrix Approximation for Machine Learning[C]//Proceedings of the17th International Conference on Machine Learning.San Francisco:Morgan Kaufmann,2000:911-918.
[10]Drineas P,Mahoney M W.On the Nystr9m Method for Approximating a Gram Matrix for Improved Kernel-Based Learning[J].Journal of Machine Learning Research,2005,6:2153-2175.
[11]Higham N J.Analysis of the Cholesky Decomposition of a Semi-definite Matrix[C]//Reliable Numerical Computation.Oxford,UK:Oxford University Press,1990:161-185.
[12]Smola A J,Bartlett P.Sparse Greedy Gaussian Process Regression[C]//Proceedings of the 13th International Conference on Neural Information Processing Systems.Cambridge:MIT Press,2000:598-604.
[13]Keerthi S S,Chapelle O,Decoste D.Building Support Vector Machines with Reduced Classifier Complexity[J].Journal of Machine Learning Research,2006,7:1493-1515.
[14]Scholkopf B,Smola A J.Learning with Kernels:Support Vector Machines,Regularization,Optimization,and Beyond[M].Cambridge:MIT Press,2003.