葉黎明，陳素根

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

0 引言

支持向量機(jī)（Support Vector Machine，SVM）是一種經(jīng)典的機(jī)器學(xué)習(xí)的算法［1］，它最初是由Vapink 等人提出的一種用于解決分類問(wèn)題的算法，由于SVM具有較強(qiáng)的理論基礎(chǔ)和較好的泛化能力而被廣泛應(yīng)用［1］. 在解決二分類問(wèn)題上，SVM依據(jù)的是在特征空間中尋找間隔最大化的分類超平面. 2006年，廣義特征值近端支持向量機(jī)（Proximal Support Vector Machines Via Generalized Eigenvalues，GEPSVM）［3］的出現(xiàn)，使得支持向量機(jī)的研究進(jìn)入新篇章. 受GEPSVM算法的啟發(fā)，Jayadeva等人于2007年提出孿生支持向量機(jī)（Twin Support Vector Machine，TWSVM）［4］. 實(shí)際上，TWSVM求解兩個(gè)規(guī)模較小的凸二次規(guī)劃問(wèn)題代替SVM中一個(gè)規(guī)模較大的凸二次規(guī)劃問(wèn)題，提升訓(xùn)練性能，理論上使訓(xùn)練速度變成SVM的4倍. 從此，諸多學(xué)者對(duì)TWSVM 及相關(guān)算法開(kāi)展深入研究，取得豐碩的成果［5-6］，PTSVM 就是具有代表性的研究成果之一［7］. 該算法的思想是找出2個(gè)最優(yōu)的投影方向，使得本類樣本投影之后盡可能聚集在該類的投影中心周圍，同時(shí)另一類樣本投影之后盡可能遠(yuǎn)離該投影中心. 隨后，許多學(xué)者在PTSVM的基礎(chǔ)上提出各種改進(jìn)算法［8-10］，豐富PTSVM的研究.

盡管對(duì)于PTSVM的研究還在持續(xù)不斷地進(jìn)行著，它的性能也在不斷地加強(qiáng)，但在參數(shù)選擇上仍存在不足之處，且參數(shù)的好壞對(duì)于PTSVM 性能有較大影響. 為提升算法的性能，智能算法逐漸被引入到TWSVM算法中，丁世飛等人將粒子群算法（PSO）［11］和量子粒子群算法（Quantum Particle Swarm Optimization，QPSO）［12］與TWSVM結(jié)合，分別提出基于粒子群算法孿生支持向量機(jī)［13］和量子粒子群算法孿生支持向量機(jī)［14］. 之后，受上述文獻(xiàn)啟發(fā)，李景燦等人提出基于人工魚群算法（Artificial Fish Swarms Algorithm，AFSA）的孿生支持向量機(jī)［15］. 另一方面，PSO是一種基于全局式搜索的群智能優(yōu)化算法，該算法不但設(shè)計(jì)原理簡(jiǎn)單、計(jì)算量比較小、編程容易實(shí)現(xiàn)，而且由于PSO能夠在多維空間中可以有效地對(duì)懲罰參數(shù)進(jìn)行分析優(yōu)化，并具有收斂快、求解質(zhì)量高的特點(diǎn). 因此，粒子群算法被廣泛應(yīng)用于各種研究問(wèn)題［16-18］的參數(shù)優(yōu)化中，并取得不錯(cuò)的實(shí)際應(yīng)用效果. 基于上述分析，本文嘗試將粒子群算法與PTSVM相結(jié)合，提出基于粒子群算法的投影孿生支持向量機(jī)，解決PTSVM懲罰參數(shù)和核參數(shù)選擇問(wèn)題，提升算法性能，并在UCI數(shù)據(jù)集上驗(yàn)證算法的有效性.

1 相關(guān)理論

1.1 投影孿生支持向量機(jī)

假設(shè)2類樣本集合分別表示為：

其中，m1和m2分別為正類(+1) 和負(fù)類( -1) 樣本數(shù)，并且令m=m1+m2，m為樣本總數(shù)量，再假定n為樣本維度. PTSVM是尋找兩個(gè)最優(yōu)的投影方向w1和w2，并最小化同類的投影樣本的類內(nèi)方差，并使另一類的投影樣本盡可能分散. PTSVM算法的具體問(wèn)題如下：

其中：C1和C2是非負(fù)懲罰參數(shù)，ξk和ηk是非負(fù)松弛變量.

為簡(jiǎn)化上述表達(dá)，給出以下定義.

在求解式（1）和式（2）中，引入拉格朗日函數(shù)，結(jié)合KKT（Karush-Kuhn-Tucker）條件，再結(jié)合式（3）和式（4），將優(yōu)化問(wèn)題轉(zhuǎn)化為對(duì)偶形式：

其中：α和γ是拉格朗日乘子，，A和B為正負(fù)類樣本集合. 求解式（5）和式（6），得到w1和w2. 對(duì)于未知樣本x∈Rn，其決策函數(shù)為：

對(duì)于非線性PTSVM，將原空間映射到高維特征空間，則式（3）和式（4）中S1，S2改為：

其中：K 為特定的核函數(shù)，CT=[AT,BT]. 類似于線性PTSVM的方式，得到：

于是，得到相應(yīng)的決策平面為：

其中：X1=A,X2=B.

1.2 粒子群算法

PSO算法可以簡(jiǎn)單描述為：假設(shè)有N 個(gè)微粒在種群中，種群中粒子i 在d 維的搜索空間中第t 代的位置可以用一個(gè)d 維向量表示，粒子i 的速度和位置通過(guò)式（13）和式（14）快速迭代更新.

其中t 為粒子更新迭代次數(shù). 在d 維空間中第t 代粒子i 所經(jīng)歷的“最好”位置記作“最好”的粒子位置記作，c1和c2為加速系數(shù)，w 為慣性系數(shù)，c1、c2、w 都是固定值.r1和r2是2個(gè)在區(qū)間[0,1]范圍內(nèi)隨機(jī)變化的數(shù). 粒子經(jīng)過(guò)不停更新迭代學(xué)習(xí)，最后達(dá)到d 維空間中解的全局最優(yōu)位置，最終輸出的gb 就是算法找到的全局最優(yōu)解. 圖1是粒子群算法的流程圖，該圖直觀地?cái)⑹隽Ｗ尤核惴ǖ倪\(yùn)行步驟.

圖1 粒子群算法流程圖

圖2 PSO-PTSVM算法流程圖

2 基于粒子群算法的投影孿生支持向量機(jī)

投影孿生支持向量機(jī)需要尋找2個(gè)最優(yōu)投影方向w1和w2，在線性PTSVM中，需要對(duì)2個(gè)懲罰參數(shù)進(jìn)行優(yōu)化確定，在非線性PTSVM中，除懲罰參數(shù)外，還有核參數(shù)需要確定. 網(wǎng)格搜索是常用的參數(shù)選擇方法，但該方法會(huì)花費(fèi)很多時(shí)間，而且這種窮舉搜索過(guò)多依賴于調(diào)參設(shè)置，極大地影響分類結(jié)果的準(zhǔn)確性.而PSO算法的全局參數(shù)優(yōu)化能力將克服網(wǎng)格搜索方法的缺點(diǎn)，受其啟發(fā)，本文提出一種新的算法：基于粒子群算法的投影孿生支持向量機(jī)（PSO-PTSVM）. 將PSO算法引入到PTSVM中，通過(guò)PSO算法對(duì)PTSVM的多個(gè)參數(shù)進(jìn)行尋優(yōu)，這樣不僅能提高PTSVM的分類精度，同時(shí)又能大幅度降低PTSVM的運(yùn)行總時(shí)間.下面給出PSO-PTSVM的具體步驟：

Step1 將粒子群規(guī)模N 和最大的迭代次數(shù)K 設(shè)置為固定的數(shù)值，將PTSVM中所需優(yōu)化的參數(shù)當(dāng)作粒子群中需要初始化的個(gè)體，并計(jì)算出初始化后所需優(yōu)化的粒子速度和方向. 將初始化后的粒子代入到投影孿生支持向量機(jī)中，對(duì)訓(xùn)練集進(jìn)行分類，計(jì)算出分類精度，然后將分類精度設(shè)置成適應(yīng)度值.

Step2 根據(jù)式（13）和式（14），不斷在全局中更新粒子的速度和方向，同時(shí)計(jì)算粒子新的適應(yīng)度值，將產(chǎn)生的更好適應(yīng)度值替換原來(lái)的適應(yīng)度值，如果更新后某個(gè)粒子的最優(yōu)適應(yīng)度值比當(dāng)前全局的最好適應(yīng)度值更優(yōu)，那就更新全局最優(yōu)值.

Step3 假如迭代次數(shù)已經(jīng)達(dá)到Step1中設(shè)置的固定數(shù)值，那么就終止迭代. 否則，重復(fù)執(zhí)行Step2.

Step4 最終得到最優(yōu)適應(yīng)度值，將其對(duì)應(yīng)的數(shù)值作為投影孿生支持向量機(jī)的參數(shù)值，得到最優(yōu)的分類精度，這就構(gòu)成PSO-PTSVM模型.

圖2給出PSO-PTSVM 算法的流程圖.

3 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證PSO-PTSVM 的性能，選取8個(gè)UCI 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，表1給出數(shù)據(jù)集的特征. 具體實(shí)驗(yàn)環(huán)境是MATLAB R2018a，硬件配置為Window10操作系統(tǒng)，16 GB內(nèi)存，AMD和3.40 GHz主頻CPU的計(jì)算機(jī).實(shí)驗(yàn)中，選取TWSVM，PTSVM和AFSA-PTSVM作為對(duì)比實(shí)驗(yàn)，與PSO-PTSVM進(jìn)行比較. 非線性實(shí)驗(yàn)中，選取Gauss徑向基核函數(shù)K( x,y )=e-μ‖x-y‖2，其中μ 為核參數(shù).

表1 實(shí)驗(yàn)數(shù)據(jù)集的特征

實(shí)驗(yàn)階段，在TWSVM、PTSVM、AFSA-PTSVM 和PSO-PTSVM 中，對(duì)每個(gè)數(shù)據(jù)集都采用10-折交叉驗(yàn)證方法，實(shí)驗(yàn)結(jié)果給出平均分類精度和運(yùn)行總時(shí)間. 在TWSVM 和PTSVM 中，C1,C2和μ 的網(wǎng)格搜索范圍均設(shè)置為{2i|i=-8,-7,-6,…,6,7,8} ，AFSA-PTSVM 中，最大嘗試次數(shù)try_number、視野Visual、步長(zhǎng)Step、擁擠度因子δ、最大迭代次數(shù)K 、種群規(guī)模N 分別設(shè)置為5、0.5、0.1、0.618、50、10. 基于實(shí)驗(yàn)公平性考慮，PSO中K 和N 的設(shè)置和AFSA一樣，2個(gè)學(xué)習(xí)因子η1=η2=2，慣性權(quán)重ω=0.8. 圖3和圖4分別給出線性和非線性PSO-PTSVM在Australian數(shù)據(jù)集上的收斂曲線，其中橫坐標(biāo)和縱坐標(biāo)分別表示迭代次數(shù)和分類精度. 從圖3和圖4可以看出，該算法收斂速度快，大概只需15次迭代就收斂.

表2 和表3給出線性情況下比較結(jié)果，表2是4種算法的分類精度和方差，表3是4種算法在不同數(shù)據(jù)集上運(yùn)行的總時(shí)間. 表4給出非線性情況下4種算法的分類精度和方差的比較結(jié)果，表5給出非線性情況下4種算法在不同數(shù)據(jù)集上運(yùn)行的總時(shí)間. 為體現(xiàn)算法的優(yōu)越性，將最高分類精度和最短的運(yùn)行總時(shí)間用加粗?jǐn)?shù)字標(biāo)出.

圖3 Australian數(shù)據(jù)集線性結(jié)果

圖4 Australian數(shù)據(jù)集非線性結(jié)果

觀察表2～表5的結(jié)果可以發(fā)現(xiàn)，在線性分類情形下，PSO-PTSVM都獲得較好的分類結(jié)果，其分類精度都高于其他3個(gè)算法；非線性分類情形下，PSO-PTSVM 在大多數(shù)數(shù)據(jù)集上取得較好的分類精度，僅在Liver、Ionosphere 和Wpbc 3 個(gè)數(shù)據(jù)集上比AFSA-PTSVM 略差一點(diǎn)，但仍然比TWSVM 和PTSVM 效果好.從表3和表5可以看出，在線性和非線性情形下本文提出的PSO-PTSVM運(yùn)行總時(shí)間更短. 為便于觀察實(shí)驗(yàn)結(jié)果，圖5和圖6給出分類精度，易知本文提出的PSO-PTSVM比TWSVM、PTSVM以及AFSA-PTSVM 3種算法具有更好的分類性能.

圖5 線性情形下分類精度

圖6 非線性情形下分類精度

表2 線性模式下4種算法的實(shí)驗(yàn)比較

表3 線性模式下4種算法運(yùn)行時(shí)間比較

表4 非線性模式下4種算法的實(shí)驗(yàn)比較

表5 非線性模式下4種算法運(yùn)行時(shí)間

4 結(jié)論

本文針對(duì)投影孿生支持向量機(jī)（PTSVM）算法運(yùn)行時(shí)間過(guò)長(zhǎng)和最優(yōu)參數(shù)選擇困難的問(wèn)題，提出基于粒子群算法的投影孿生支持向量機(jī)（PSO-PTSVM）. 利用粒子群算法快速高效的搜索能力，對(duì)PTSVM算法中的多個(gè)參數(shù)進(jìn)行優(yōu)化，避免參數(shù)選擇的盲目性. 在UCI 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，與TWSVM、PTSVM 和AFSA-PTSVM算法對(duì)比，PSO-PTSVM運(yùn)行總時(shí)間短且具有更好的分類性能. 但不足之處在于，粒子群算法容易陷入局部最優(yōu)，如何將新型智能算法用于解決投影孿生支持向量機(jī)的參數(shù)選擇問(wèn)題，并構(gòu)建高效的全局最優(yōu)算法，依然值得進(jìn)一步研究.