Fisher正則化的最小二乘孿生支持向量機

張 萌，陳素根

（安慶師范大學 數(shù)理學院，安徽 安慶 246133）

20世紀90年代，VAPNIK等[1]提出了支持向量機（Support vector machine,SVM）算法，其是一種借助于統(tǒng)計與優(yōu)化方法來解決機器學習問題的強有力工具[2]，被廣泛應(yīng)用于分類和回歸等各種實際問題中。然而，SVM具有較高的計算復(fù)雜度等問題，限制了它的實際應(yīng)用。為了克服SVM存在的問題，人們開展了大量研究并提出了許多SVM 改進算法[3]。2006 年，MANGASARIAN 等提出了一種多平面近端支持向量機[4]，該算法不僅有較低的計算復(fù)雜度，而且可以有效地解決異或問題。受其啟發(fā)，JAYADEVA等提出了孿生支持向量機（Twin support vector machine,TWSVM），其僅僅求解兩個規(guī)模較小的二次規(guī)劃問題，且訓(xùn)練速度大約是傳統(tǒng)SVM 的4 倍[5]。2009 年，KUMAR 等[6]在TWSVM 基礎(chǔ)上提出了最小二乘形式的孿生支持向量機（Least squares twin support vector machine,LSTSVM），并利用等式約束代替TWSVM中的不等式約束，將問題轉(zhuǎn)化為求解線性方程組，從而使得LSTSVM相對于TWSVM具有計算簡單和訓(xùn)練速度快的優(yōu)勢。2011 年，陳小波等[7]提出了投影孿生支持向量機（Projection twin support vector machine,PTSVM），該算法尋找兩個最優(yōu)的投影方向以代替兩個非平行平面。受PTSVM 啟發(fā)，2012年邵元海等[8]提出了最小二乘形式的投影孿生支持向量機（Least squares projection twin support vector machine,LSPTSVM）。從此，非平行平面支持向量機算法被廣泛研究，且取得了豐碩的研究成果[9-13]。

雖然LSTSVM具有較快的求解速度，但其在求解線性方程組過程中可能存在矩陣奇異問題。同時，訓(xùn)練過程會受每個訓(xùn)練樣本影響，這使得其泛化性能較差。2018年，吳青等[14]對LSTSVM進行改進，并提出了最小二乘形式的大間隔孿生支持向量機（Least squares large margin twin support vector machine,LSLMTSVM），該算法在LSTSVM 的優(yōu)化目標函數(shù)中引入間隔分布，提高了算法的泛化性能，但LSLMTSVM 仍存在參數(shù)選擇困難等問題。為進一步提升LSTSVM 性能，受Fisher 正則化思想[15]的啟發(fā)，本文提出了Fisher 正則化的最小二乘孿生支持向量機（Fisher regularized least squares twin support vector machine,FLSTSVM）。FLSTSVM 算法的優(yōu)點有：（1）引入雙Fisher 正則化項，增強獲取判別信息的能力，提高了算法的泛化性能；（2）基于結(jié)構(gòu)風險最小化原則，解決了求解過程中可能出現(xiàn)矩陣奇異的問題；（3）FLSTSVM具有相對較快的訓(xùn)練速度。

1 相關(guān)工作

考慮n維實數(shù)空間中的一個二分類問題，假設(shè)給定的訓(xùn)練集T={(,yj)|i=1,2,j=1,2,3,…,mi}，其中，m1+m2=m，yj∈{+1,-1 }∈Rn表示第i類、第j個輸入樣本，A∈表示m1個n維的正類樣本，B∈Rm2×n表示m2個n維的負類樣本。

1.1 TWSVM

線性TWSVM尋找兩個非平行的超平面fi(x)=+bi=0,i=1,2，使每一個超平面盡可能靠近一類樣本點并且遠離另一類樣本點，其原始優(yōu)化問題為

其中，c1＞0,c2＞0是懲罰參數(shù)，ξ1,ξ2是松弛變量，e1,e2是分量全為1的適當維數(shù)的向量。

引入拉格朗日函數(shù)，并利用KKT（Karush-Kuhn-Tucker）條件，將優(yōu)化問題（1）和（2）轉(zhuǎn)化為對偶形式：

其中，α和γ是拉格朗日乘子，求解公式（3）和（4），得到w1,b1,w2,b2。

對于任意x∈Rn,i=+1,-1，根據(jù)公式（5）進行分類：

這里 |· |表示數(shù)據(jù)點到超平面的垂直距離。對于非線性TWSVM，選擇合適的核函數(shù)將原始數(shù)據(jù)映射到高維特征空間，類似于線性TWSVM構(gòu)造非線性模型，可參見文獻[5]。

1.2 LSTSVM

LSTSVM 也是尋找兩個非平行超平面fi(x)=+bi=0,i=1,2，其是TWSVM 的一種改進算法。它基于平方損失函數(shù)，并利用等式約束代替不等式約束，線性LSTSVM的原始優(yōu)化問題為

對于優(yōu)化問題（6），將等式約束代入目標函數(shù)，關(guān)于w1和b1求偏導(dǎo)數(shù)且令其等于零，整理得

令E=[A e],F=[B e]，化簡可得

對于優(yōu)化問題（7），同理可得

求得w1,b1,w2,b2后，可得超平面fi(x)=+bi=0,i=1,2。對于任意x∈Rn,i=+1,-1，根據(jù)公式（11）進行分類：

這里 |· |表示數(shù)據(jù)點到超平面的垂直距離。對于非線性的LSTSVM算法，可見參考文獻[6]。

2 Fisher正則化的最小二乘孿生支持向量機

2.1 線性的FLSTSVM

為了提高LSTSVM的判別能力，本文引入雙Fisher正則化項對LSTSVM進行改進。Fisher正則化的最小二乘孿生支持向量機也尋找兩個非平行的超平面：

給定正類樣本對應(yīng)的矩陣A和負類樣本對應(yīng)的矩陣B，記

正類Fisher正則化項[15]定義如

負類Fisher正則化項[15]定義如

正類Fisher正則化項和負類Fisher正則化項統(tǒng)稱為雙Fisher正則化項，其中公式（15）和（16）中的第一項為相應(yīng)的類內(nèi)散度，第二項是相應(yīng)的類間散度。

于是，對于給定的訓(xùn)練樣本集，考慮如下兩個優(yōu)化問題：

其中，c1,c4＞0表示正則化參數(shù)。公式（17）式和（18）的目標函數(shù)中第一項是樣本點到相應(yīng)類的超平面距離平方和，最小化這一項可使這一類樣本點聚集在此超平面周圍。目標函數(shù)的第二項為雙Fisher正則化項，最小化這一項可使類內(nèi)散度最小化和類間散度最大化。然而，優(yōu)化問題（17）和（18）是非凸的，不易求解。因此，對優(yōu)化問題（17）和（18）的目標函數(shù)和約束條件進行改進，同時在目標函數(shù)中引入新的正則項以實現(xiàn)結(jié)構(gòu)風險最小化原則。于是，線性FLSTSVM原始優(yōu)化問題為

其中，c1,c2,c3,c4,c5,c6＞0為參數(shù)，ξ1,ξ2表示松弛變量，e1,e2是分量全為1的適當維數(shù)的向量。

對于優(yōu)化問題（20），將等式約束代入目標函數(shù)以得到無約束問題：

由公式（25）和（28）求得w1,b1,w2,b2后，可得超平面（12）。對于任意x∈Rn,i=+1,-1，根據(jù)公式（29）進行分類：

綜上分析，本文給出了線性FLSTSVM的算法步驟。

2.2 非線性FLSTSVM

將線性FLSTSVM擴展為非線性模型，對于非線性情況，首先令C=[A;B]，選擇合適的核函數(shù)K，尋找兩個非平行超曲面：

與線性情況類似，分別記

類似于線性情況，非線性FLSTSVM的原始優(yōu)化問題如

類似于線性FLSTSVM 的求解過程，將等式約束代入目標函數(shù)以轉(zhuǎn)化為無約束問題，并分別關(guān)于wi,bi(i=1,2)求導(dǎo)，經(jīng)過一系列化簡，求得

求解公式（37）和（38），可得

由公式（39）和（40）求得w1,b1,w2,b2后，可得兩個非平行超曲面，如公式（30）。于是，對于任意測試樣本x∈Rn,i=+1,-1，根據(jù)公式（41）進行分類：

非線性FLSTSVM算法的求解過程與線性FLSTSVM算法非常相似，唯一不同的是先選擇合適的核函數(shù)K，并將數(shù)據(jù)映射到高維空間。

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

為驗證本文所提FLSTSVM算法的有效性，在2個人工數(shù)據(jù)集和9個UCI數(shù)據(jù)集上開展實驗，并分別與TWSVM[5]、LSTSVM[6]、PTSVM[7]、LSPTSVM[8]和LSLMTSVM[13]對比。實驗均以MATLAB R2016a 為環(huán)境，硬件配置為Windows10操作系統(tǒng)，6 GB內(nèi)存的計算機。在實驗過程中，使用逐次超松弛技術(shù)來求解各算法中的二次規(guī)劃問題。對于非線性算法，核函數(shù)選擇RBF 核K(x,y)=，μ為核參數(shù)。最優(yōu)參數(shù)均采用10-折交叉驗證和網(wǎng)格搜索的方法進行選擇，參數(shù)都取自集合{2i|i=-8,-7,-6,…,8 }。每個實驗重復(fù)10次，并將實驗結(jié)果的平均值和方差作為最后結(jié)果。

3.1 人工數(shù)據(jù)集

在兩個人工數(shù)據(jù)集XOR和復(fù)雜XOR數(shù)據(jù)集上進行實驗，其中，XOR包含240個樣本（120個正類樣本和120 個負類樣本），而復(fù)雜XOR 包含172 個樣本（90 個正類樣本和82 個負類樣本）。圖1 給出了XOR和復(fù)雜XOR數(shù)據(jù)集的散點分布。圖2給出了本文所提線性FLSTSVM算法在兩個數(shù)據(jù)集上的分類效果。不難發(fā)現(xiàn)，線性FLSTSVM算法能夠較好地解決XOR和復(fù)雜XOR數(shù)據(jù)分類問題。同時，表1給出了各線性算法在XOR和復(fù)雜XOR數(shù)據(jù)集上的實驗結(jié)果，并用粗體表示最好的分類結(jié)果。

圖2 線性FLSTSVM算法在XOR和復(fù)雜XOR數(shù)據(jù)集上的分類效果。（a）XOR數(shù)據(jù)集；（b）復(fù)雜XOR數(shù)據(jù)集

表1 線性算法在XOR和復(fù)雜XOR數(shù)據(jù)集上的分類結(jié)果

從表1可看出，本文算法在XOR和復(fù)雜XOR數(shù)據(jù)集上均取得了最好的分類準確率，故驗證了算法的有效性。需要指出的是，與其他算法相比，雖然FLSTSVM分類準確率都是最好的，但并不能明顯提高分類準確率，這可能是因為在XOR和復(fù)雜XOR數(shù)據(jù)集上非平行平面孿生支持向量機算法都具有相對較好的性能。另外，實驗中的復(fù)雜XOR數(shù)據(jù)集規(guī)模不大，F(xiàn)LSTSVM算法增強獲取判別信息的能力沒有得到充分體現(xiàn)。

3.2 UCI數(shù)據(jù)集

為了進一步驗證算法有效性，本文在UCI 數(shù)據(jù)集上進行實驗，并分別與TWSVM、LSTSVM、PTSVM、LSPTSVM 和LSLMTSVM算法進行比較，表2和3分別給出了線性和非線性算法實驗結(jié)果?？梢钥闯?，本文所提出的FLSTSVM算法在大部分數(shù)據(jù)集上都取得了較好的分類準確率，驗證了該算法的有效性。在表2 可以發(fā)現(xiàn)，線性FLSTSVM 算法在大多數(shù)數(shù)據(jù)集上的準確率要優(yōu)于其它算法。例如，在Votes數(shù)據(jù)集上，線性FLSTSVM準確率為96.39%，而TWSVM為95.86%，LSTSVM為95.86%，PTSVM為95.73%，LSPTSVM為95.97%，LSLMTSVM為95.19%。表3結(jié)果與表2相似，驗證了非線性算法的有效性。例如，在Breast數(shù)據(jù)集上，非線性FLSTSVM的分類準確率為77.98%，比TWSVM高1.15%，比LSTSVM高0.47%，比PTSVM高1.09%，比LSPTSVM高0.87%，比LSLMTSVM高0.76%。另外，表2和3的最后一行用“W-T-L”(win-tie-loss)比較了FLSTSVM與其他算法的分類準確率?？梢钥闯?，在大部分情況下，F(xiàn)LSTSVM有較高的分類準確率。在線性情況下，F(xiàn)LSTSVM僅僅比LSMTSVM的性能稍微差一點，“W-T-L”的結(jié)果為4-0-5；在非線性情況下，F(xiàn)LSTSVM與所有算法的“W-T-L”比較結(jié)果都要好一點。

表2 各線性算法在UCI數(shù)據(jù)集上的分類結(jié)果

圖3和4分別給出了在線性和非線性情況下各算法運行一次的時間圖，可以發(fā)現(xiàn)FLSTSVM在大部分情況下都有較快的訓(xùn)練速度，僅比LSTSVM 運行時間長，比其他算法的運行時間都短，進一步驗證了本文所提算法的有效性。實際上，本文所提FLSTSVM 算法是在LSTSVM算法的基礎(chǔ)上引入了Fisher正則化項，求解過程與LSTSVM 相似，但是在具體計算過程中需要多計算一些矩陣乘法運算。相較其它算法，TWSVM 和PTSVM需要求解二次規(guī)劃問題，求解速度要慢一點；同時LSPTSVM 和LSLMTSVM雖然也是求解線性方程組問題，但都需要進行一系列矩陣乘法運算。

圖3 線性算法在UCI數(shù)據(jù)集上的運行時間

圖4 非線性算法在UCI數(shù)據(jù)集上的運行時間

4 結(jié)束語

本文基于雙Fisher正則化項提出了一種新的最小二乘孿生支持向量機分類算法，有效提升了算法獲取判別信息的能力。同時，該算法是基于結(jié)構(gòu)風險最小化原則，克服了LSTSVM求解過程中可能出現(xiàn)的矩陣奇異問題。在人工數(shù)據(jù)集和UCI 數(shù)據(jù)集上驗證了本文所提FLSTSVM 算法的有效性，結(jié)果顯示FLSTSVM 算法在大多數(shù)數(shù)據(jù)集上具有較高的分類準確率和相對較快的訓(xùn)練速度。將FLSTSVM 算法推廣到多類分類和半監(jiān)督分類可作為今后的研究。