基于遺傳算法的雙子支持向量機的模型選擇

曹路+秦傳波+洪燦佳

摘 要： 雙子支持向量機是在支持向量機的基礎(chǔ)上提出的一種新的機器學(xué)習(xí)方法。與傳統(tǒng)支持向量機相比，雙子支持向量機尋找的是一對不平行的超平面，計算效率是傳統(tǒng)支持向量機的4倍。然而，雙子支持向量機的參數(shù)較多，在應(yīng)用過程中存在較大局限性。在研究了懲罰參數(shù)和核參數(shù)對雙子支持向量機分類性能影響的基礎(chǔ)上，利用遺傳算法來選擇雙子支持向量機的參數(shù)，避免了盲目的模型選擇。實驗結(jié)果顯示，所提算法能有效選擇合適參數(shù)，獲得的參數(shù)能使雙子支持向量機具有較好的泛化性能，同時也更加高效。

關(guān)鍵詞： 雙子支持向量機； 遺傳算法； 核函數(shù)； 參數(shù)選擇

中圖分類號： TN98?34； TP273 文獻標(biāo)識碼： A 文章編號： 1004?373X（2017）17?0105?04

Genetic algorithm based model selection of TWSVM

CAO Lu， QIN Chuanbo， HONG Canjia

（School of Information Engineering， Wuyi University， Jiangmen 529020， China）

Abstract： Twin support vector machine （TWSVM） is a new machine learning method based on support vector machine. In comparison with traditional support vector machine， TWSVM looks for a pair of non?parallel hyperplane， and its computational efficiency is increased by 3 times. However， the parameters of TWSVM are various， and have some limitations in the application process. On the basis of the research on the influence of the penalty parameter and kernel parameter on classification performance of TWSVM， the genetic algorithm is used to select the parameters of TWSVM to avoid blind model selection. The experimental results show that the algorithm can select appropriate parameters effectively， which can make the TWSVM have high generalization performance and efficient performance.

Keywords： TWSVM； genetic algorithm； kernel function； parameter selection

0 引 言

支持向量機[1]（Support Vector Machine，SVM）是20世紀60年代由V.Vapnik等人提出的基于統(tǒng)計理論的機器學(xué)習(xí)方法，在小樣本的情況下有優(yōu)良的學(xué)習(xí)性能，已被廣泛應(yīng)用于模式識別、文本分類及回歸分析等眾多領(lǐng)域[2?3]。盡管支持向量機克服了傳統(tǒng)分類器過學(xué)習(xí)、局部極值和維數(shù)災(zāi)難等缺點，但支持向量機的訓(xùn)練時間消耗非常大，復(fù)雜度較高，無法適應(yīng)大數(shù)據(jù)環(huán)境下對分類技術(shù)的更高要求。文獻[4]提出一種新的學(xué)習(xí)方法，稱為雙子支持向量機（Twin Support Vector Machines，TWSVM），將SVM中的一對平行超平面推廣到復(fù)雜的非平行超平面的情況，因而能處理一些傳統(tǒng)SVM難以處理的數(shù)據(jù)分布，如交叉數(shù)據(jù)。由于TWSVM所求解的二次規(guī)劃問題的規(guī)模是原SVM的所以，從理論上來說計算效率是傳統(tǒng)SVM的4倍，極大地提高了分類效率[5]。

在TWSVM出現(xiàn)以后，人們一直在關(guān)注著如何進一步改進TWSVM，從而涌現(xiàn)出了很多方法。文獻[6]在經(jīng)典的TWSVM基礎(chǔ)上，提出一種有邊界的雙子支持向量機（Twin Bounded Support Vector Machines，TBSVM）。該模型參照經(jīng)典支持向量機，采用結(jié)構(gòu)風(fēng)險最小原則，在一定程度上提升了原模型的識別率。文獻[7]提出基于最小二乘的雙子支持向量機（Least Squares Twin Support Vector Machines，LSTSVM），將最小二乘的思想引入TWSVM中，修改原始雙子支持向量機二次規(guī)劃問題，用等式約束取代TWSVM中的不等式約束問題，計算效率得到了顯著提高。文獻[8]提出一種新型改進型的雙子參數(shù)邊界支持向量機（Twin Parametric?margin Support Vector Machines，TPMSVM），根據(jù)參數(shù)邊界SVM的基本思想，融入TWSVM中，產(chǎn)生兩條非平行超平面，具有良好的識別性能。

盡管TWSVM在算法改進和應(yīng)用領(lǐng)域取得了較大進展，但算法仍存在一定的局限，如TWSVM中的參數(shù)較多，參數(shù)的選擇會影響分類器最終的分類性能。文獻[9?10]分別用粒子群算法和量子粒子群算法對TWSVM的參數(shù)進行優(yōu)化，取得了較好的實驗結(jié)果。目前，大多數(shù)文獻采用的是參數(shù)空間窮盡搜索法在整個參數(shù)空間進行搜索，計算復(fù)雜度較高。由此，本文提出一種基于遺傳算法的TWSVM模型選擇方法，首先利用遺傳算法獲得最優(yōu)參數(shù)，然后將參數(shù)用于TWSVM中以提高分類精度。實驗結(jié)果顯示，獲得的參數(shù)能使雙子支持向量機具有較好的泛化性能，同時也更加高效。endprint

1 雙子支持向量機

1.1 雙子支持向量機分類算法

考慮維實數(shù)空間的二值分類問題，訓(xùn)練數(shù)據(jù)集，其中是輸入空間中的樣本，是輸出分類中的分類標(biāo)簽，。雙子支持向量機構(gòu)造了兩個不平行的超平面，使得每一個分類面靠近一類樣本而遠離其他類樣本，兩個超平面分別記為：

（1）

可以通過求解兩個優(yōu)化問題獲得兩個不平行的超平面，兩個優(yōu)化問題可描述為：

（2）

（3）

式中：為參數(shù)；和為列向量。

式（2）和式（3）的對偶問題分別為：

（4）

（5）

式中：；；和分別為拉格朗日乘數(shù)。

式（6），式（7）有求解矩陣的逆，為了解決矩陣的異常性和病態(tài)矩陣，雙子支持向量機引入因子使矩陣的逆可解。通過求解式（4），式（5），可獲得式（1）定義的兩個超平面：

（6）

一個新的樣本點類別的判定依賴于樣本點與兩個超平面之間的距離，具體可描述為：

（7）

與傳統(tǒng)支持向量機一樣，為了求解非線性情況，TWSVM通過核函數(shù)將原始特征空間中的非線性分界面映射到高維空間中以獲得更好的分類效果。

1.2 支持向量機和雙子支持向量機性能比較

圖1和圖2是二維不交叉數(shù)據(jù)和二維交叉數(shù)據(jù)在SVM和TWSVM的分類效果圖，其中，“+”表示正類樣本，“○”表示負類樣本。圖1為二維不交叉數(shù)據(jù)時的情況，其中圖1（a）為SVM的分類效果圖，分類面是能將兩類數(shù)據(jù)分開且滿足最大間隔的超平面；圖1（b）為TWSVM的分類效果圖，與傳統(tǒng)SVM不一樣，TWSVM最終獲得的是兩個不平行的分類面，其中實線為正類分類面，虛線為負類分類面。圖2為二維交叉數(shù)據(jù)的情況，其中圖2（a）為SVM的分類效果圖，可以看到，線性情形下的SVM只有一條分類面，無法將兩類樣本很好地分開；而在圖2（b）中，采用TWSVM有兩個分類面，可有效識別兩類樣本。

2 參數(shù)對TWSVM的影響

2.1 懲罰參數(shù)和對TWSVM的影響

為了研究懲罰參數(shù)對TWSVM的影響，對兩類符合多維正態(tài)分布的人工數(shù)據(jù)集進行分類，采用的兩類數(shù)據(jù)均值分別為[-5，20]，[15，2]，協(xié)方差矩陣為[10，0；0，2]，[10，0；0，1]的205×2維的隨機向量，每一類中含有15個噪聲點。如圖3所示，分別為[0.01，0.01]，[0.483 9，0.494 4]，[1，1]，[10，10]，其中圖3（b）是使用交叉驗證獲得的最優(yōu)參數(shù)，分類準確度為98.78%。懲罰參數(shù)是特征空間中置信區(qū)間和經(jīng)驗風(fēng)險的折衷，其目的是使TWSVM的泛化能力達到最佳。如圖3（a）所示，和的值越小，表示經(jīng)驗風(fēng)險的誤差越小。在這種情況下，TWSVM的復(fù)雜度較低，但容錯能力較差。如圖3（c）和圖3（d）所示，當(dāng)兩個懲罰參數(shù)的值較大時，數(shù)據(jù)擬合程度較高，易出現(xiàn)過擬合的情況，不能很好地泛化新數(shù)據(jù)。

2.2 核參數(shù)對TWSVM的影響

TWSVM是一種基于核的學(xué)習(xí)方法，核函數(shù)及核參數(shù)的選擇直接影響到TWSVM的泛化能力。常用的核函數(shù)有線性核、多項式核和高斯核，其中以高斯核函數(shù)最為普遍。高斯核可描述為：其中為高斯核參數(shù)。核函數(shù)參數(shù)和特征子空間是相互對應(yīng)的。高斯核參數(shù)不同，數(shù)據(jù)所對應(yīng)的特征子空間不同，分類效果也就不同，因此高斯核參數(shù)的選取對TWSVM性能影響很大。當(dāng)很小時，TWSVM構(gòu)造的分類面過于簡單，不能很好地擬合數(shù)據(jù)；當(dāng)很大時，特征子空間維度很高，TWSVM的模型比較復(fù)雜，沒有很好的泛化能力。因此，只有選擇合適的核函數(shù)參數(shù)，將數(shù)據(jù)投影到合適的特征子空間，TWSVM才能獲得良好的推廣能力。

3 基于遺傳算法的雙子支持向量機

用常規(guī)的遍歷方法如網(wǎng)格搜索法來尋找TWSVM的最優(yōu)參數(shù)需要大量的運算，計算復(fù)雜度高，訓(xùn)練過程十分耗時，因此采用先進的尋優(yōu)算法對TWSVM的參數(shù)進行優(yōu)化是很重要的。在各種參數(shù)優(yōu)化算法中，遺傳算法（Genetic Algorithm，GA）是一種比較高效的尋優(yōu)算法[11]。本文將遺傳算法應(yīng)用到TWSVM的參數(shù)優(yōu)化中，稱為GA?TWSVM。通過遺傳的優(yōu)化功能，快速準確地確定TWSVM的懲罰參數(shù)和高斯核函數(shù)參數(shù)，從而最終確定TWSVM的模型。具體實現(xiàn)步驟如下：

（1） 初始化雙子支持向量機參數(shù)并對其進行二進制編碼，產(chǎn)生遺傳算法的初始群體。

（2） 設(shè)定遺傳算法的參數(shù)。

（3） 將初始群體解碼后送入雙子支持向量機進行訓(xùn)練并計算個體的適應(yīng)度。

（4） 應(yīng)用最優(yōu)保存策略，在進行遺傳操作之前保存適應(yīng)度較高的個體。

（5） 進行遺傳操作，選擇算子采用賭輪選擇法，通過選擇、交叉和變異操作產(chǎn)生新群體。

（6） 重復(fù)執(zhí)行步驟（3）～步驟（5）操作，直至最大迭代次數(shù)滿足適應(yīng)度要求。

4 實 驗

為了測試基于遺傳算法的TWSVM的有效性，本文采用UCI標(biāo)準數(shù)據(jù)集進行驗證，實驗數(shù)據(jù)集的描述見表1，實驗中所采用的數(shù)據(jù)可以從http：//archive.ics.uci.edu/ml/datasets.html下載。本文實驗環(huán)境為IntelCoreTM i7?37， CPU 3.4 GHz，4 GB內(nèi)存和Matlab R2013a。實驗中將選取60%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，保證足夠的數(shù)據(jù)用于模型的學(xué)習(xí)；40%的數(shù)據(jù)作為測試數(shù)據(jù)，驗證模型的效果。本文實驗采取五折交叉確認的方法，在實驗過程中，每個數(shù)據(jù)集被隨機分為5等分，取其中1個子集為測試集，其他4個子集為訓(xùn)練集。為了避免偶然性，本文將算法分別執(zhí)行5次，最后取平均值作為最后的輸出。遺傳算法的參數(shù)設(shè)置如下：群體規(guī)模為500，最大進化代數(shù)為1 000次，交叉概率為0.8，變異概率為0.05。和的優(yōu)化區(qū)間均為[0.1，100]，高斯核參數(shù)的區(qū)間為[0.01，50]。endprint

表2列出了GA?TWSVM獲得最佳訓(xùn)練精度時的懲罰參數(shù)和的值，及高斯核參數(shù)的取值，同時，表2中還列出了利用遺傳算法獲得最優(yōu)參數(shù)后，將最優(yōu)參數(shù)用于測試數(shù)據(jù)所得到的分類準確率。

表3為SVM、基于網(wǎng)格搜索法的TWSVM和基于遺傳算法的TWSVM三種算法在分類精度和搜索時間上的比較。需要特別說明的是，本文中SVM采用二次規(guī)劃的方法進行分類。從理論上講，TWSVM的運行時間應(yīng)是SVM運行效率的4倍，在實驗中發(fā)現(xiàn)，實驗結(jié)果和理論值存在一定的差距。盡管如此，從表3中可以看到，基于網(wǎng)格搜索法的TWSVM和基于遺傳算法的TWSVM在分類精度和搜索時間上相較于SVM存在非常明顯的優(yōu)勢。同時，實驗結(jié)果也顯示，基于網(wǎng)格搜索法和遺傳算法的TWSVM在搜索精度上沒有明顯的差別，但是優(yōu)化參數(shù)的搜索速度不相同。很明顯，遺傳算法的搜索速度更快，這在實際運用中有巨大的優(yōu)勢。因此，遺傳算法相對于網(wǎng)格搜索算法在基于RBF核的TWSVM分類器的參數(shù)優(yōu)化運用中具有更好的可行性。

5 結(jié) 論

與傳統(tǒng)的支持向量機相比，雙子支持向量機是解決大規(guī)模數(shù)據(jù)集的有效方法，其分類精度和訓(xùn)練速度均優(yōu)于傳統(tǒng)的支持向量機。雙子支持向量機中參數(shù)眾多，參數(shù)的選擇對分類的精度有較大影響。本文提出一種基于遺傳算法的雙子支持向量機模型選擇，通過遺傳算法的良好尋優(yōu)性能對雙子支持向量機眾多參數(shù)進行尋優(yōu)，實驗結(jié)果顯示該方法是有效的。然而遺傳算法容易受到隨機初值的影響，利用改進的遺傳算法對雙子支持向量機的參數(shù)進行優(yōu)化是下一步的研究方向，同時，探索新的應(yīng)用領(lǐng)域，推廣基于遺傳算法的雙子支持向量機的應(yīng)用也是值得考慮的問題。

參考文獻

[1] 鄧乃揚，田英杰.支持向量機：理論、算法、與拓展[M].北京：科學(xué)出版社，2009.

[2] 瓦普尼克.統(tǒng)計學(xué)習(xí)理論[M].許建華，張學(xué)工，譯.北京：電子工業(yè)出版社，2004.

[3] 王文劍，門昌騫.支持向量機建模及應(yīng)用[M].北京：科學(xué)出版社，2014.

[4] KHEMCHANDANI R， CHANDRA S. Twin support vector machines for pattern classification [J]. IEEE transactions on pattern analysis and machine intelligence， 2007， 29（5）： 905?910.

[5] 儲茂祥，王安娜，鞏榮芬.一種改進的最小二乘孿生支持向量機分類算法[J].電子學(xué)報，2014，42（5）：998?1003.

[6] SHAO Y H， ZHANG C H， WANG X B， et al. Improvements on twin support vector machines [J]. IEEE transactions on neural networks， 2011， 22（6）： 962?968.

[7] KUMAR M A， GOPAL M. Least squares twin support vector machines for pattern classification [J]. Expert systems with applications， 2009， 36（4）： 7535?7543.

[8] PENG X. TPMSVM： a novel twin parametric?margin support vector machine for pattern recognition [J]. Pattern recognition， 2011， 44（10）： 2678?2692.

[9] DING S F， YU J Z， HUANG H J， et al. Twin support vector machines based on particle swarm optimization [J]. Journal of computers， 2013， 9（8）： 2296?2303.

[10] DING S F， WU F L， NIE R， et al. Twin support vector machines based on quantum particle swarm optimization [J]. Journal of software， 2013， 8（7）： 1743?1750.

[11] 梁旭，黃明，寧濤，等.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M].北京：電子工業(yè)出版社，2014.

[12] HUANG H J， DING S F， ZHU H， et al. Invasive weed optimization algorithm for optimizating the parameters of mixed kernel twin support vector machines [J]. Journal of computers， 2013， 8（8）： 2077?2084.endprint