混合核函數支持向量機的參數優化算法研究*

許少榕

(福州職業技術學院文化創意系，福建 福州 350108)

混合核函數支持向量機的參數優化算法研究*

許少榕

(福州職業技術學院文化創意系，福建 福州 350108)

本文研究支持向量機混合核函數參數優選問題，提出將量子進化算法和粒子群算法相結合，得到一種新型混合核函數支持向量機參數優選算法.提出了兩種基于收斂因子的優化策略改進量子粒子群算法，改進了量子粒子群算法存在發散和早熟收斂，無法準確搜索全局最優解的難題，避免了算法早熟收斂問題，確保量子粒子群算法能夠在全局準確搜索到核函數最優參數，最后通過仿真實驗，證明該優化算法可有效避免早熟收斂，提高了向量機預測精度.

支持向量機；混合核函數；參數優選；量子粒子群算法

引言

自機器學習誕生之日起，人們就致力于模擬和提高計算機通過學習過往數據和經驗獲取認知規律并進行預測的學習能力，統計學的發展為解決上述基于數據的機器學習問題提供了重要的研究方法并且發揮了不可替代的作用[1].以統計學習理論為基礎旨在解決小樣本集、非線性、復雜高維數等機器學習實際問題的支持向量機(Support Vector Machine，SVM)，以其結構簡單、易推廣以及解決小樣本問題時突出優勢的特點，受到了廣大學者廣泛關注和研究，并取得了豐碩的成果.

在研究采用支持向量機算法解決實際問題時，核函數是研究的重中之重，合理選擇核函數是解決小樣本學習問題的關鍵[2].這是因為選擇恰當的核函數可以同時提高算法的學習能力和泛化能力.目前被廣泛采用的單核函數主要有線性核函數、多項式核函數、高斯核函數和徑向基核函數等，基于單核函數自身性能的局限和應用背景，其無法勝任全部的機器學習問題場合[3].因此，很多學者致力于研究將不同的單核函數結合，組成混合核函數支持向量機，應用于復雜機器學習場合和同時對學習能力及泛化能力要求較高的場合，并且取得了極大成功，產生了很多研究成果.研究成果表明混合核函數的參數選擇對于支持向量機的性能具有至關重要的作用.然而諸多文獻都只指出支持向量機采取混合核函數時優于單核函數，而沒有構建出一套完整的參數優選方法體系[4～7].

為了優化支持向量機的性能，必須采用合理的智能算法對混合核函數的參數進行優選.針對傳統粒子群算法(PSO)在樣本空間進行尋優迭代時易發生早熟收斂，不能精準搜索到全局最優值的問題，本文提出將兼容性極強且易于和其它進化計算方法結合的量子進化算法與粒子群算法相結合，構造出一種量子粒子群算法，將其應用于混合核函數的參數優化選擇，在小樣本空間進行與傳統算法對比的仿真實驗，結果表明，這種算法能夠更合理的優化核函數的參數，提高支持向量機的性能.

本文所述量子粒子群算法暴露出的算法發散和早熟收斂問題，針對此，提出兩種基于收斂因子的優化量子粒子群算法策略，克服算法的早熟收斂問題，確保量子粒子群算法能夠在核函數參數尋優選擇過程中保持收斂，精確搜索到最優解.將采用優化量子粒子群算法優選參數的核函數應用于支持向量機，進行仿真實驗，實驗結果表明，采用本文提出的核函數參數優化算法對參數進行尋優，可以有效避免傳統量子粒子群算法尋優過程中早熟收斂問題，快速精確確定最優核函數參數，采用該算法的支持向量機具有更好的性能.

1 支持向量機的混合核函數

1.1支持向量機算法原理

SVM基本原理是通過某種非線性變換函數φ(x)，將樣本空間中{(xi,yi)}(i=1,2,…m)輸入量xi∈Rn映射到某一高維特征空間Z，在Z空間中搜索支持向量，并用支持向量構造最優分類超平面[8].在高維空間構造的分類決策最優線性函數為：

f(x)=sign(ωT·φ(x)+b)

(1)

根據最小化結構風險原則，參數ω,b可通過式(2)最小化得到最初問題為:

(2)

式中C是參數可調的懲罰因子，其取值越大表示對錯誤分類懲罰越大.對式(2)的問題求解可以通過拉格朗日公式轉化成式(3)的對偶求解問題：

(3)

式中ai為非負拉格朗日因子，其中所應用的非線性變換函數稱為核函數K，可定義為：

K(x,xk)=φ(xi)T·φ(xi)

(4)

通過選擇合適的核函數，聯立式(3)和(4)，對偶問題化為

(5)

再通過對偶問題(3)的求解，可得到

(6)

于是，最終可以得到最優線性決策函數為：

(7)

1.2混合核函數

支持向量機的核心即是核函數的確定和選擇.通常把能夠滿足Mercer定理的對稱函數K(x,xi)定義為核函數.

Mercer定理：要保證任意的對稱函數K(u,v)能以正的系數ak>0展開成：

(8)

(10)

多項式核函數(Poly)：

(11)

徑向基核函數(RBF)：

(12)

反正切核函數：

(13)

在實際應用中，為了兼顧改善學習能力和泛化能力，常常選擇兩種單核函數按特定的權重構建出混合核函數如式(14)所示：

Kmix=ρKpoly+(1-ρ)KRBF

(14)

2 基于量子粒子群優化參數的支持向量機

2.1量子粒子群算法

為了優化支持向量機的性能，必須采用合理的智能算法對混合核函數的參數進行優選[10].針對傳統粒子群算法(PSO)在樣本空間進行尋優迭代時易發生早熟收斂，不能精準搜索到全局最優值的問題，本文提出將兼容性極強且易于和其它進化計算方法結合的量子進化算法融合進粒子群算法，構造出量子粒子群算法(Quantum Particle Swarms Optimization, QPSO)應用于混合核函數的參數優化選擇，該算法特點是采用量子位編碼定義粒子的當前位置，再由量子旋轉門搜索確定粒子最優位置，其算法具體操作如下：

首先利用量子位概率幅Qi進行粒子初始位置的編碼:

(15)

(16)

通過上述變換即實現了從粒子位置到問題最優解的轉換，因此每一個量子位對應優化問題的兩個解.

設粒子qi當前空間尋優求解所經歷的最優位置為余弦位置，即：

Qil=(cos(θil1),cos(θil2),…,cos(θiln))

(17)

種群全部粒子所經歷的最優位置也記為余弦位置：

Qg=(cos(θg1),cos(θg2),…,cos(θgn))

(18)

由式(17)和(18)得到粒子Qi上量子幅角變化量如下式(19)所示：

Δθij(t+1)=ωΔθij(t)+c1(Δθl)+c2(Δθg)

(19)

由此推出量子旋轉門如下式為：

(20)

同理通過基于量子旋轉門幅角更新公式最終求得采用于量子粒子算法的粒子Qi的兩個更新位置分別為：

(21)

(22)

上述基本量子粒子群算法流程如圖1所示，分析可知，在QPSO中，一個量子粒子對應于解空間中兩個解，即可同時實現解空間中兩個位置移動，因此在支持向量機核函數參數優選中采用量子粒子群算法能夠優化種群粒子尋址空間搜索效率，提高算法優化參數能力[11].

圖1 量子粒子群算法流程圖

2.2采用量子粒子群優化核函數參數的支持向量機

為了發揮最佳的機器學習能力和達到更好的預測效果，本文采用基于混合核函數的支持向量機模型進行分類預測仿真實驗，并將量子粒子群算法應用于核函數最佳參數尋優，得到基于量子粒子群的混合核函數支持向量(GAPSO-CSVM)，通過紅酒分類識別實驗來檢測采用GAPSO-CSVM的性能.為檢驗本文提出的量子粒子群算法最優核函數優點和特性，分別對采用BP算法、傳統粒子群算法和量子粒子群算法核函數的三種支持向量機進行紅酒分類問題仿真實驗，實驗的數據集中共有178個樣本，每個樣本中包含14個數據，其中輸入數據為13維，依次代表著紅酒的酒精濃度、蘋果酸含量、雜質含量百分百等，而輸出數據只有一個，既紅酒種類的標識碼.實驗首先采取5個樣本作為訓練集，然后將整個數據集的178個樣本全部作為測試集，設定種群含有20個粒子，每個粒子都為5維，其所包含的數據分別為：混合核函數權重系數ρ，RBF核函數的參數δ，PLOY函數的參數d、γ和ζ.分別采用上述三種不同算法對紅酒種類識別問題進行20次仿真實驗，實驗過程中采取每做完5次實驗就暫停1次，然后將訓練樣本重新隨機選擇，保持訓練集大小不變,最后得到采用三種參數優化算法支持向量機的分類實驗準確率[12]，結果如圖2和表1所示.

圖2 BP、SVM、QPSO-SVM算法仿真結果圖

算 法最高準確率最低準確率平均準確率迭代終止次數BP89.33%87.63%88.60%30PSO-SVM91.01%89.32%90.20%35QPSO-CSVM94.38%92.70%93.57%20

分析圖2和表1可以看出，基于QPSO參數優選算法的支持向量機的最高、最低和平均分類準確率都高于另外兩種算法，同時，由于量子算法的優點和特性，采用該算法終止迭代次數明顯減少，其具有更好的學習能力和泛化能力.說明相較于另外兩種參數優選算法，量子粒子群算法可以進一步提高了參數優化效率，得到預測精度和穩定性更高的最優核函數.分析上述實驗結果可以得知，量子粒子群參數優選算法在小樣本數訓練集具備高準確率和更少迭代次數的優點，而實際應用中可能遇到大樣本空間參數優化求解問題，針對尋址空間樣本數增加時，量子粒子群算法是否依然能夠延續優異的性能，下面依次增加訓練集樣本數，進行仿真實驗.實驗將訓練集樣本數量依次定為99，135和178.利用QPSO-CSVM算法擬合出函數模型，進行與前面完全一致的實驗，結果如圖3所示.

圖3 增加訓練集樣本數時，量子粒子群算法支持向量機的分類準確率

分析對比圖2和圖3中采用量子粒子群算法核函數的支持向量機分類準確率可知，隨著訓練集樣本數由55依次增加大95、130和177過程中，最高分類準確率與最低分類準確率差值也逐漸由0.56%升高到1.12%，即隨訓練集樣本數的加大，算法分類準確率呈下降趨勢，這表明采用QPSO算法對核函數參數進行優選時，種群粒子陷入早熟收斂問題.

3 基于收斂因子改進量子粒子群

為了消除QPSO早熟收斂，可將收斂因子應用于QPSO，通過收斂因子優化調整PSO中粒子狀態的更新，提高收斂速度和全局搜索能力[13].收斂因子表達式如下式(23)所示：

(23)

式中：κ∈[0,1]，φ=φ1+φ2，φ的取值對于算法的收斂具有至關重要的作用.通過收斂因子得到粒子速度、位置更新公式如下式(24)所示：

Vi(t+1)=χ(Vi(t)+φ1c1(Pi-Xi(t))+φ2c2(Pg-Xi(t)))
Xi(t+1)=Xi(t)+Vi(t+1)

(24)

式中，pi(t)-φ1c1(Pi-Xi(t))+φ2c2(Pg-Xi(t))為第i個粒子的局部吸引因子，粒子在全局尋優搜索過程中，會持續快速的向著局部吸引子靠近.

3.1早熟收斂的評價準則

引入收斂因子克服早熟收斂，可以提高量子粒子群算法優化核函數參數的效率，因此要進行參數優化效果評價就必須先定義相應的早熟收斂的評價準則[14]：

在QPSO算法尋優迭代過程中，當迭代次數為k次，仍沒有搜索到全局最優值，且種尋址空間內所有粒子位置和速度都滿足下式(25)：

(25)

式中，e1>0,e2>0i=1，2，…，m；j=1，2，…n.

就判定算法陷入了早熟收斂.

3.2基于收斂因子改進量子粒子群算法

3.2.1 基于全新尋址搜索模式克服早熟收斂的優化策略

利用QPSO算法進行參數尋優求解時，種群多樣性的減少是造成算法無法準確搜索到全局最優解的重要原因.因此可以采取在算法出現早熟收斂時，立即重新初始化粒子種群、Pil和Pg，對種群進行重新搜索[15].針對QPSO算法中粒子速度和位置更新都在每一維進行操作，將量子粒子的每一維的幅角都在[-2π,2π)]區間上進行獨立且均勻分布的初始化操作，以m個邊長為r的子空間組成初始化空間，

(26)

式中，j=1，2，…m，θmax=2π，θmin=0.01π.早熟收斂一旦出現，即對粒子在尋址空間搜索到的最優位置重新初始化，使種群在尋優空間重新搜索最優解，直到滿足收斂條件，判定搜索到全局最優解，迭代終止,此為改進的量子粒子群算法QPSO1.

3.2.2 基于全干擾交叉模式克服早熟收斂策略

利用量子粒子優化求解過程可以采用量子交叉門，根據每個量子粒子不同下標，對種群進行概率交叉操作，進而對整個量子粒子種群進行重新排列.設交叉概率為ρc，在迭代過程中，產生隨機數r，若r>ρc,則依照表2所示對種群粒子進行交叉操作，否則不進行交叉.

表2 量子全干擾交叉

分析表2可知，在進行交叉操作時，整個粒子種群數量和數據保持不變，僅僅是量子粒子排列順序發生變化，其變化規律可歸納為下式(27)所示：

(27)

式中i′和j′分別表示新的量子種群中，粒子新的橫、縱坐標，i和j分別表示原量子種群中，粒子的橫、縱坐標，n表示染色體種群的縱坐標最大值.具體操作為，一旦概率超過設定值時，就通過進行交叉操作得到新的量子種群.由此得到新的尋優算法定義為QPSO2.

3.2.3 兩種改進量子粒子群算法的仿真實驗

為了檢驗本文所述基于克服早熟收斂策略所產生的核函數優化算法的性能，分別利用QPSO算法和改進的QPSO1、QPSO2算法對Griewank函數進行定義域xi∈(-5.25,5.25)上的最小值點及其對應的函數值的求解仿真實驗，Griewank函數的表達式如下所示

(28)

Griewank函數在三維空間中的特征如圖4所示，該函數是一個多極值函數，在定義域xi∈(-5.25,5.25)中，具有多個極大值點和極小值點.因此在作用域對該函數求解，會有多個局部最優解，而全局最優解為一個“0”向量.基于此，該函數可作為檢驗算法性能的指標.

分別采用QPSO算法、QPSO1和QPSO2對Griewank函數在10維空間中進行50次求解，粒子種群都取20，優化迭代上限次數為2 000次，設定當f(x)≤0.01時，迭代終止，分析表3所示仿真結果可知，在50次的仿真過程中，QPSO1和QPSO2算法相較于QPSO算法可以更大概率地求解出最優解.表明QPSO1算法和QPSO2算法具有較好的避免早熟收斂的能力，同時具有更好的搜索能力.進一步分析比較算法QPSO1和QPSO2可以發現，QPSO1算法相對QPSO2算法有一定的概率可以更快的搜索到最優值，而QPSO2算法則能夠搜索到更精準全局最優解，且所用的平均時間會相對較小.

圖4 Griewank函數三維空間特征

4 基于改進QPSO優化核函數參數的支持向量機仿真實驗

將QPSO、QPSO1和QPSO2算法應用到混合核函數支持向量機，分別采用這三種算法對混合核函數參數進行尋優，利用優化參數的CSVM進行和上文相同的紅酒分類實驗，并以支持向量機最終分類準確率作為核函數參數性能評價指標.

QPSO-CSVM、QPSO1-CSVM以及QPSO2-CSVM的仿真實驗參數與前文相同，樣本數分別為55、95、130、178，采用三種不同算法共進行20次迭代，得到面對不同訓練集時的分類能力如圖5(a)、(b)、(c)、(d)所示.分析圖5所示算法分類準確率可知，首先，當增加訓練集樣本數時，三種算法的分類準確率都有所提高.而當訓練集樣本為整個數據集時，QPSO1-CSVM和QPSO2-CSVM的分類準確率甚至達到了100%.其次，分析單獨一種訓練集下三種算法的分類準確率可知，基于QPSO的CSVM算法的分類準確率最差的；QPSO2-CSVM算法的分類準確率最好的，最后，對比分析基于QPSO1和QPSO2的CSVM分類準確率結果可以發現，采用QPSO1算法的支持向量機總體具有較好的分類準確率，但分析整個20次仿真實驗數據，可發現其分類準確率并不相同.

綜上分析可知，在對混合核函數參數進行尋優的過程中，兩種基于改進的QPSO算法相較于傳統QPSO算法更容易收斂到全局最優解，提高核函數參數優選效率，優化支持向量機學習能力和泛化能力.并且基于QPSO2支持向量機，相較于基于QPSO1支持向量機性能更好，說明QPSO2參數優化算法比QPSO1算法參數尋優搜索時間更短，求解到更優核函數.

表3 QPSO、QPSO1、QPSO2仿真結果

圖5 不同訓練集，三種算法的性能對比

5 結語

本文提出一種將量子進化算法和粒子群算法相結合的量子粒子群算法，并將其應用到支持向量機參數優化中，該算法發揮QPSO(量子粒子群算法)的函數優化功能，對支持向量機核函數參數尋優求解，快速準確地搜尋并求解得到最優核函數，使支持向量機在小樣本數集具有更好的性能.

由于傳統量子粒子群算法具有算法發散和早熟收斂的缺陷，在訓練集樣本數增加時，核函數參數優選不能準確搜索到最優解，本文又提出兩種基于收斂因子改進量子粒子群算法QPSO1和QPSO2，并將兩種改進量子粒子群算法應用于的支持向量機核函數參數優選，利用基于QPSO1和QPSO2的支持向量機對紅酒酒類識別進行了仿真實驗，并與傳統QPSO支持向量機進行了對比，結果表明，兩種基于改進的QPSO算法相較于傳統QPSO算法更容易收斂到全局最優解，提高核函數參數優選效率，優化支持向量機學習能力和泛化能力.并且，基于QPSO2支持向量機相較于基于QPSO1支持向量機性能更好，說明QPSO2參數優化算法比QPSO1算法參數尋優搜索時間更短，求解到更優核函數.

[1]Rodger J A. A fuzzy nearest neighbor neural network statistical model for predicting demand for natural gas and energy cost savings in public bulidings[J].Expert Syst，2014,41(4)：1813-1829.

[2]Wang Q,Zhu H,Wu W,et al. Inshore ship detection using high-resoution synthetic aperture radar images based on maximally stable extremal region[J]. Journal of Applied Remote Sensing,2015,9(1):94-95.

[3]高艷云，龐敏.基于最小流形類內離散度的支持向量機[J].計算機應用研究，2015,32(9):2639-2642.

[4]Singh A K,Shukla V P,Tiwari S,et al. Wavelet based histogram feature descriptors for classification of partially occluded object[J]. International Journal of Intelligent Systems and Applications,2015,7(3):54-61.

[5]單黎黎，張宏軍，王杰，等.一種改進粒子群算法的混合核ε -SVM 參數優化及應用[J].計算機應用研究，2013,30(6)：1636-1639.

[6]Wang X,P ardalos P M. A survey of support vector machines with uncertainties[J].Annals of Data Science,2015,1(4):293-309.

[7]欒詠紅,劉全.Twin-SVM 和 Twin-KSVC標志物檢測與分類方法[J].計算機工程與設計, 2016,37(12): 3306-3310.

[8]Rani S,Syed D. Categorization of video using viola jones and fisher linear discriminant function[J].Biometrics and Bioinformatics ,2015,7(4):110-113.

[9]Yin S,Ouyang P,Liu L, et al. Fast traffic sign recognition with a rotation invariant binary pattern based feature[J].Sensors,2015,15(1):2161-2180.

[10]Shamshirband S,Petkovic D,Hashim R,et al. An appraisal of wind turbine wake models by adaptive neuro-fuzzy methodology[J].Int J Elect Power Energy Syst,2014,63(5):618-624.

[11]苗超維，秦品樂.基于多分類SVM和Hd的目標跟蹤算法[J].計算機工程與設計，2016,37(11):3118-3123.

[12]馬家辰，武冠群 ，馬立勇，等.基于細菌覓食算法和支持向量機的表情識別[J].計算機工程與設計, 2015,36(7): 1881-1885.

[13]蔡世清，周杰.基于支持向量機的多傳感器數據融合算法[J].計算機工程與設計, 2016,37(5): 1352-1356.

[14]丁勝鋒，孫勁光.基于混合模糊隸屬度的模糊雙支持向量機研究[J].計算機應用研究，2013,30(2):432-435.

[15]Nouaouria N，Boukadoum M． Improved global-best particle swarm optimization algorithm with mixed-attribute data classification capability[J].Applied Soft Computing，2014，21: 554-567．

ResearchonParameterOptimizationAlgorithmofHybridKernelFunctionSupportVectorMachines

XU Shao-rong

(Department of Cultural Creativity, Fuzhou Polytechnic, Fuzhou Fujian 350108, China)

This paper studies the parameter selection of hybrid kernel function of support vector machines. A new hybrid kernel function support vector machine parameter optimization algorithm is proposed by combining quantum evolutionary algorithm with particle swarm optimization. It puts forward two improved quantum particle swarm optimization algorithm based on convergence factor and avoids the problem of premature convergence to ensure that the quantum particle swarm algorithm can accurately search the global optimal kernel function parameters. Simulation test results show that the optimization algorithm can effectively avoid premature convergence and improve the prediction accuracy of vector machines.

support vector machine; hybrid kernel function; parameter optimization; quantum particle swarm algorithm

1673-2103(2017)05-0020-09

2017-04-06

許少榕(1982-)，女，福州閩侯人，碩士，實驗師.研究方向：計算機技術及實驗室管理.

TP18

A