基于QR分解的稀疏LSSVM算法

周水生, 周艷玲, 姚 丹, 王保軍

(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 西安 710126)

最小二乘支持向量機(LSSVM)用等式約束代替不等式約束, 將標準支持向量機(SVM)求解凸二次規(guī)劃問題轉(zhuǎn)化為線性方程組的求解問題, 加快了求解速度, 在保證最小二乘誤差最小的情況下最大化分類間隔[1-2]. Suykens等[3]提出了利用對偶問題求解LSSVM的模型(D-LSSVM); 由于其解缺乏稀疏性, 文獻[4-5]提出了修剪法, 如去除Lagrange乘子相對較小的支持向量或去掉靠近分類超平面的支持向量, 以增強解的稀疏性, 但這類方法需要先求解一系列非線性方程組, 算法復(fù)雜度較高; 文獻[6-7]提出了基于對偶模型的選基法, 即選擇一組樣本子集來得到低秩近似核矩陣進行求解, 如通過尋找特征空間的一組近似線性無關(guān)向量, 直接構(gòu)造分類判別函數(shù)的稀疏表示或快速稀疏近似算法FSA-LSSVM和PFSA-LSSVM. 實驗結(jié)果表明, 當設(shè)定支持向量的數(shù)目較少時, 這些稀疏算法使最小二乘支持向量機性能損失較大. 周水生[8]基于表示定理提出了在原空間求解最小二乘支持向量機的模型(P-LSSVM), 在核矩陣不滿秩的情況下該模型可得到稀疏解, 克服了D-LSSVM的不足. 周水生[8]提出PCP-LSSVM稀疏迭代算法求解P-LSSVM的稀疏解, 該算法基于選主元的Cholesky分解方法逐步得到大規(guī)模核矩陣K的低秩近似矩陣, 整個過程只需計算核矩陣的對角元素及部分精選的列, 可解決大規(guī)模訓(xùn)練問題. 但PCP-LSSVM算法僅依賴于線性無關(guān)性選取樣本作為支持向量, 因此選取的支持向量代表性不強.

已知基于正交三角(QR)分解的數(shù)值穩(wěn)定性能保證所選樣本之間保持較大的差異性, 該性質(zhì)可能會使所選訓(xùn)練樣本對應(yīng)的支持向量更具有代表性. 基于這種思想, 本文對基于QR分解選取樣本的方法進行研究. 為了保持P-LSSVM的優(yōu)點, 同時克服PCP-LSSVM算法僅基于線性無關(guān)性選取支持向量可能導(dǎo)致的不足, 提出一種基于QR分解的QRP-LSSVM稀疏迭代算法尋找P-LSSVM的稀疏解. 實驗結(jié)果表明, QRP-LSSVM算法可以找到分布均勻、 代表性強的支持向量, 從而得到更稀疏的解, 甚至在稀疏水平不超過0.05%的情況下也能達到較高的準確率, 算法穩(wěn)定性較好, 可有效解決大規(guī)模訓(xùn)練問題.

1 稀疏最小二乘支持向量機

(1)

其中輸入樣本集為{xi,yi},i=1,2,…,m,xi∈n, 樣本xi相應(yīng)的標簽為yi∈{+1,-1}. 采用最小二乘支持向量機模型在樣本集上進行訓(xùn)練學(xué)習(xí), 可得到分類函數(shù)f(x)將樣本盡可能分開. 在特征空間H中解決非線性分類問題時, 選用半正定核函數(shù)K:n×n→避免計算特征映射的內(nèi)積, 滿足K(x,z)=〈φ(x),φ(z)〉H, 其中, 特征映射φ:d→H將d維空間的樣本xi映射到高維甚至無窮維特征空間中. 樣本和標簽之間的關(guān)系由決策函數(shù)sgn(f(x))確定, 分類超平面為常數(shù).

(2)

P-LSSVM在核矩陣不滿秩的情況下, 存在包含r≤rank(K)個非零元素的稀疏解. 直接求解線性方程組(2)顯然計算復(fù)雜度較大, 周水生[8]提出基于Cholesky分解的PCP-LSSVM稀疏算法進行求解, 降低了計算復(fù)雜度同時提高了測試準確度, 可有效解決非線性大數(shù)據(jù)訓(xùn)練問題. 但PCP-LSSVM算法選取的支持向量可能不具有代表性, 從而可能導(dǎo)致結(jié)果穩(wěn)定性較差. 已知基于QR分解的數(shù)值穩(wěn)定性能保證所選樣本之間保持較大的差異性, 為了保持PCP-LSSVM的優(yōu)點同時克服基于線性無關(guān)性選取支持向量可能導(dǎo)致的不足, 本文對基于QR分解的QRP-LSSVM稀疏算法進行求解.

2 算法設(shè)計

2.1 基于QR分解的P-LSSVM稀疏解形式

將K的Nystr?m近似代入式(2)得到等價的線性方程組為

(3)

對于已有的基本集B, 稀疏解僅依賴于列滿秩的矩陣KMB. 此外, 對KMB進行QR分解得到KMB=QR, 其中:Q∈m×r;R∈r×r. 推導(dǎo)出K的低秩近似矩陣分解式將其代入式(3)中可得在基本集B上的稀疏解為

(4)

其中偏置b為

(5)

目前有許多尋找基本集B的方法, 隨機選擇樣本點加入基本集B, 不能保證得到K的最優(yōu)低秩近似矩陣. 基于Cholesky分解的PCP-LSSVM算法是根據(jù)線性無關(guān)性選取樣本點確定基本集B的, 但并未明確所選樣本間線性無關(guān)的程度, 易漏選一些影響力較大的樣本點, 因此該算法選定的基本集不一定具有代表性. 本文給出QRP-LSSVM稀疏迭代算法解決此問題.

2.2 核矩陣的低秩近似及誤差分析

(6)

整理并簡化后的低秩近似核矩陣誤差上界為

(7)

利用求逆公式

(8)

可以將式(7)整理簡化為

(9)

(10)

2.3 算法描述

算法1QRP-LSSVM算法.

輸入： 訓(xùn)練數(shù)據(jù)集M={1,2,…,m}, 核函數(shù)K(x,z), 最大稀疏上限r(nóng)max;

輸出： 基本集B和相應(yīng)的Q,R;

1) 初始化B0∶=?,N0∶=M, Δε0=1,i∶=0;

2) WhileN0:≠? andi

4) 令Bi+1←Bi∪{t},Ni+1←Ni{t};

5) Ifi=0;

7) else

9) End if

10) 更新i←i+1;

11) End while

12) ReturnB←Bi,Q←Qi,R←Ri.

QRP-LSSVM算法迭代地實現(xiàn)基本集的選擇及低秩近似核矩陣的分解, 在保證較小近似核矩陣誤差的同時, 使基于QR分解的數(shù)值穩(wěn)定性選取的樣本之間保持較大的差異性, 最終得到盡可能均勻分布的代表性較強的支持向量, 降低了內(nèi)存占用的同時在計算復(fù)雜度不大于O(mr2)的情況下得到P-LSSVM模型的稀疏解, 可有效解決大規(guī)模訓(xùn)練問題.

3 實驗結(jié)果與分析

首先將稀疏LSSVM算法PCP-LSSVM和QRP-LSSVM運用在人工生成數(shù)據(jù)和Banana數(shù)據(jù)(http://www.pudn.com/.htm)上進行實驗對比, 以表明QRP-LSSVM迭代選點特征及優(yōu)勢； 然后在4種大規(guī)模非線性數(shù)據(jù)集上進行對比實驗, 從測試準確率和稀疏度水平兩方面分析對比PCP-LSSVM和QRP-LSSVM兩種算法的分類效果. 本文采用徑向基核函數(shù)[2]K(x,z)=exp{-γ‖x-z‖2}解決非線性分類問題. 為了使算法達到較好的泛化能力, 通過簡單的交叉驗證選擇各訓(xùn)練數(shù)據(jù)集上分布參數(shù)γ和正則化參數(shù)λ的最優(yōu)組合.

3.1 人工生成數(shù)據(jù)實驗

在[0,1]×[0,1]橫縱坐標軸上各自等間距選取100個點, 得到平面上均勻分布的10 000個樣本點, 將[0,0.5]×[0,0.5]和[0.5,1]×[0.5,1]方形區(qū)域內(nèi)的所有樣本點標志為正類, 將[0,0.5]×[0.5,1]和[0.5,1]×[0,0.5]方形區(qū)域內(nèi)的所有樣本點標志為負類, 在10 000個樣本點中隨機選取6 000個樣本點作為訓(xùn)練樣本集, 剩余的樣本點全部作為測試樣本集. 最終生成包含6 000個訓(xùn)練樣本和4 000個測試樣本的人工生成數(shù)據(jù). 實驗中設(shè)定基本集的樣本數(shù)為5, QRP-LSSVM算法和PCP-LSSVM算法在人工生成數(shù)據(jù)上的分類效果如圖1所示.

圖1 QRP-LSSVM和PCP-LSSVM算法在人工生成數(shù)據(jù)上的分類效果Fig.1 Classification effects of QRP-LSSVM and PCP-LSSVM algorithm on artificial data

由圖1可見, QRP-LSSVM算法基于QR數(shù)值穩(wěn)定性選取樣本點所得到的支持向量分布均勻且具有代表性, 穩(wěn)定性較好. QRP-LSSVM迭代選取的5個支持向量都是類中心點, 且通過多次運行程序發(fā)現(xiàn)每次實驗的分類結(jié)果基本相同, 差異性較小, 分類效果理想; 而PCP-LSSVM算法選取的支持向量分布的規(guī)則性較弱, 通過多次運行程序發(fā)現(xiàn)每次實驗的分類結(jié)果差異性較大, 且選取了其中最好的一個運行結(jié)果進行對比實驗, 充分說明PCP-LSSVM算法選取的樣本點不具有代表性, 且實驗結(jié)果的穩(wěn)定性較差.

圖2 QRP-LSSVM和PCP-LSSVM算法分類結(jié)果的ROC曲線Fig.2 ROC curves of classification results of QRP-LSSVM and PCP-LSSVM algorithms

下面使用ROC(receiver operating characteristic)曲線法客觀反映QRP-LSSVM和PCP-LSSVM算法的性能. 對人工生成數(shù)據(jù)進行分類實驗, 分別采用QRP-LSSVM和PCP-LSSVM算法進行訓(xùn)練, 并分別采用訓(xùn)練所得的決策函數(shù)預(yù)測得到測試樣本對應(yīng)的函數(shù)值. 設(shè)定閾值的取值在預(yù)測函數(shù)值對應(yīng)的最大、 最小值范圍內(nèi), 對每個閾值, 將測試結(jié)果大于閾值的測試樣本劃歸為正類, 小于閾值則劃分為負類, 分別計算特異度和敏感度作為橫、 縱坐標值, 繪制對應(yīng)的ROC曲線. 圖2為QRP-LSSVM和PCP-LSSVM算法分類結(jié)果的ROC曲線. 已知ROC曲線的開始上升部分越陡, 算法性能則越好. 兩條曲線都達到靈敏度臨界值1時線下面積值越大, 表明算法準確度越高. 由圖2可見: QRP-LSSVM算法對應(yīng)的曲線上升較快, 曲線對應(yīng)的敏感度先到臨界值1； 而PCP-LSSVM算法對應(yīng)的曲線上升較緩慢, 且在特異度較大的情況下到達臨界值, 表明QRP-LSSVM算法性能更好、 穩(wěn)定性更高. 通過對比兩個算法所得的敏感度都到達臨界點1后兩條曲線的線下面積大小可知, QRP-LSSVM算法的準確度更高.

3.2 Banana數(shù)據(jù)實驗

選用一個標準小數(shù)據(jù)集對比QRP-LSSVM 算法和PCP-LSSVM算法的選點特征和分類效果, 驗證QRP-LSSVM 算法的有效性. 在LIBSVM包中選取Banana數(shù)據(jù), 所選Banana數(shù)據(jù)庫是包含1 000個訓(xùn)練集樣本和1 000個測試樣本的二分類數(shù)據(jù). 圖3(A)～(C)分別為基本集大小為10(1%),15(1.5%),20(2%)時QRP-LSSVM算法在Banana數(shù)據(jù)上進行分類的實驗結(jié)果, 圖3(D)～(F)分別為PCP-LSSVM算法在基本集大小為10(1%),15(1.5%),20(2%)時的分類結(jié)果.

圖3 基本集大小分別為10,15,20時兩種算法的分類效果對比Fig.3 Comparisons of classification effects of two algorithms with basic set size of 10,15,20 respectively

對比圖3(A)和(D)可見: QRP-LSSVM算法訓(xùn)練過程中僅選用10個樣本即可得到較好的分類結(jié)果, 在圖3(A)中表現(xiàn)為紅色正類數(shù)據(jù)和藍色負類數(shù)據(jù)很好地分開, 兩類數(shù)據(jù)所呈現(xiàn)的香蕉狀非常清晰, 其中5個標五角星符的紅色數(shù)據(jù)和5個標菱形符的藍色數(shù)據(jù)即為QRP-LSSVM算法迭代選擇的10個支持向量, 其均勻分布在所屬類區(qū)域中； PCP-LSSVM算法選用的10個樣本并不能將正負類樣本進行很好地分類, 分類結(jié)果不呈香蕉形, 且邊界模糊, 表明分類準確度較低. 類似地, 對比圖3(C)和(F)可見, 兩者分類結(jié)果較接近, 都能呈現(xiàn)出相對清晰的香蕉形, 但QRP-LSSVM算法準確度更高且所選的支持向量均勻分布. 再由圖3(A)～(C)可見, QRP-LSSVM算法隨著稀疏度的增大分類結(jié)果越來越好, 分類結(jié)果的穩(wěn)定性較強, 表現(xiàn)為3個圖中分類結(jié)果的香蕉形狀規(guī)則性較強, 差異性不大. 相比圖3(D)～(F)可知, PCP-LSSVM算法隨著稀疏度的增大分類結(jié)果差異性較大, 穩(wěn)定性較差, 表現(xiàn)為3個圖中分類結(jié)果的香蕉形狀變化較大, 差異性較明顯, 規(guī)則性不明顯. 由圖3可見: QRP-LSSVM迭代選取的支持向量分布較均勻, 代表性較強, 在稀疏度非常低時分類效果較好, 隨著稀疏度的增大分類結(jié)果越來越好, 且穩(wěn)定性較強; 而PCP-LSSVM算法所選的支持向量不一定具有代表性, 且隨著稀疏度的增大分類結(jié)果差異性較大, 穩(wěn)定性較差.

3.3 大規(guī)模數(shù)據(jù)集實驗

選擇表1所列的4種大規(guī)模數(shù)據(jù)集作為實驗對象. 圖4比較分析了QRP-LSSVM和PCP-LSSVM算法在4種大數(shù)據(jù)集上的測試準確率隨稀疏度增長的變化情況, 其中圖4(A)～(D)分別為在Shuttle,Vechile,Cod-rna和Adult數(shù)據(jù)集上進行實驗的結(jié)果, 圖中每個點都是20次隨機實驗的平均值.

表1 4種大規(guī)模數(shù)據(jù)集的特征

圖4 兩種算法測試準確率隨稀疏水平的變化情況Fig.4 Test accuracies of two algorithms vary with sparsity levels

由圖4可見: QRP-LSSVM算法在所選的大數(shù)據(jù)集上均表現(xiàn)很好； 隨著稀疏度的增加, PCP-LSSVM算法相比QRP-LSSVM算法的測試準確率波動性較大, 且對于相同的稀疏度, QRP-LSSVM算法明顯高于PCP-LSSVM算法的測試準確率; 在稀疏水平較小時, QRP-LSSVM算法的優(yōu)勢更突出; 在稀疏水平很低的情況下, QRP-LSSVM算法明顯高于PCP-LSSVM算法的測試準確率, 且稀疏水平越小, 二者的差異性越大, 尤其是QRP-LSSVM算法在稀疏水平小于0.05%時即能達到較高的測試準確率. 表2列出了QRP-LSSVM算法和PCP-LSSVM算法在4種大規(guī)模數(shù)據(jù)集上分別進行實驗后測試準確率和測試時間的結(jié)果.

表2 兩種稀疏LSSVM算法在4種大規(guī)模數(shù)據(jù)集上的實驗結(jié)果對比

由表2可見, 當設(shè)定QRP-LSSVM算法的稀疏水平是PCP-LSSVM算法稀疏水平的50%時, QRP-LSSVM算法比PCP-LSSVM算法的測試準確率高, 且訓(xùn)練時間基本相當. 當設(shè)定相同的稀疏水平時, QRP-LSSVM算法明顯高于PCP-LSSVM算法的測試準確率, 雖然訓(xùn)練時間會略高于PCP-LSSVM算法的訓(xùn)練時間, 但仍有可比性.

實驗結(jié)果表明, QRP-LSSVM算法得到更稀疏解的同時可達到較高的測試準確率, 雖然在相同稀疏水平的情況下訓(xùn)練時間會稍長, 但測試準確率得到了極大提高, 對大規(guī)模數(shù)據(jù)訓(xùn)練問題有效.

綜上所述, 本文提出了一種基于QR分解的QRP-LSSVM算法來尋找P-LSSVM的稀疏解, 該算法基于QR分解的數(shù)值穩(wěn)定性迭代地選擇差異性較大的樣本, 得到代表性強的基本集B及核矩陣的Nystr?m近似, 最小化低秩近似核矩陣誤差的同時降低了內(nèi)存占用, 在計算復(fù)雜度不大于O(mr2)的情況下可得到更稀疏的解. 實驗分析表明, QRP-LSSVM算法可得到均勻分布、 代表性強的支持向量, 算法穩(wěn)定性較好. 該算法在稀疏水平不超過0.05%時能達到較高的準確率, 可有效解決大規(guī)模訓(xùn)練問題.

[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]. 吉林大學(xué)學(xué)報(理學(xué)版), 2015, 53(4): 720-724. (CHENG Ze’en. Identification of Android Malicious Behaviors Based onkNearest 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] 甘良志, 孫宗海, 孫優(yōu)賢. 稀疏最小二乘支持向量機 [J]. 浙江大學(xué)學(xué)報(工學(xué)版), 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, Sch?lkopf B. Sparse Greedy Matrix Approximation for Machine Learning [C]//Proceedings of the 17th International Conference on Machine Learning. San Francisco: Morgan Kaufmann, 2000: 911-918.

[10] Drineas P, Mahoney M W. On the Nystr?m 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] Sch?lkopf B, Smola A J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond [M]. Cambridge: MIT Press, 2003.