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

張 萌，陳素根

（安慶師范大學 數理學院，安徽 安慶 246133）

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

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

1 相關工作

考慮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，使每一個超平面盡可能靠近一類樣本點并且遠離另一類樣本點，其原始優化問題為

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

引入拉格朗日函數，并利用KKT（Karush-Kuhn-Tucker）條件，將優化問題（1）和（2）轉化為對偶形式：

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

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

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

1.2 LSTSVM

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

對于優化問題（6），將等式約束代入目標函數，關于w1和b1求偏導數且令其等于零，整理得

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

對于優化問題（7），同理可得

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

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

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

2.1 線性的FLSTSVM

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

給定正類樣本對應的矩陣A和負類樣本對應的矩陣B，記

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

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

正類Fisher正則化項和負類Fisher正則化項統稱為雙Fisher正則化項，其中公式（15）和（16）中的第一項為相應的類內散度，第二項是相應的類間散度。

于是，對于給定的訓練樣本集，考慮如下兩個優化問題：

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

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

對于優化問題（20），將等式約束代入目標函數以得到無約束問題：

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

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

2.2 非線性FLSTSVM

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

與線性情況類似，分別記

類似于線性情況，非線性FLSTSVM的原始優化問題如

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

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

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

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

3 實驗結果與分析

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

3.1 人工數據集

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

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

表1 線性算法在XOR和復雜XOR數據集上的分類結果

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

3.2 UCI數據集

為了進一步驗證算法有效性，本文在UCI 數據集上進行實驗，并分別與TWSVM、LSTSVM、PTSVM、LSPTSVM 和LSLMTSVM算法進行比較，表2和3分別給出了線性和非線性算法實驗結果?？梢钥闯?，本文所提出的FLSTSVM算法在大部分數據集上都取得了較好的分類準確率，驗證了該算法的有效性。在表2 可以發現，線性FLSTSVM 算法在大多數數據集上的準確率要優于其它算法。例如，在Votes數據集上，線性FLSTSVM準確率為96.39%，而TWSVM為95.86%，LSTSVM為95.86%，PTSVM為95.73%，LSPTSVM為95.97%，LSLMTSVM為95.19%。表3結果與表2相似，驗證了非線性算法的有效性。例如，在Breast數據集上，非線性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與其他算法的分類準確率?？梢钥闯?，在大部分情況下，FLSTSVM有較高的分類準確率。在線性情況下，FLSTSVM僅僅比LSMTSVM的性能稍微差一點，“W-T-L”的結果為4-0-5；在非線性情況下，FLSTSVM與所有算法的“W-T-L”比較結果都要好一點。

表2 各線性算法在UCI數據集上的分類結果

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

圖3 線性算法在UCI數據集上的運行時間

圖4 非線性算法在UCI數據集上的運行時間

4 結束語

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