基于渦流搜索算法的支持向量機分類模型

李學(xué)貴 許少華 李 娜 張 強

(1.東北石油大學(xué)計算機與信息技術(shù)學(xué)院，黑龍江 大慶 163318；2.山東科技大學(xué)計算機科學(xué)與工程學(xué)院，山東 青島 266590；3.大慶油田化工有限責(zé)任公司東昊分公司，黑龍江 大慶 163312；4.新疆油田公司勘探開發(fā)研究院，新疆 克拉瑪依 834000)

基于渦流搜索算法的支持向量機分類模型

李學(xué)貴1許少華2李 娜3張 強4

(1.東北石油大學(xué)計算機與信息技術(shù)學(xué)院，黑龍江 大慶 163318；2.山東科技大學(xué)計算機科學(xué)與工程學(xué)院，山東 青島 266590；3.大慶油田化工有限責(zé)任公司東昊分公司，黑龍江 大慶 163312；4.新疆油田公司勘探開發(fā)研究院，新疆 克拉瑪依 834000)

提出一種將渦流搜索算法用于支持向量機參數(shù)選取的新算法，利用該算法不必遍歷搜索空間內(nèi)所有的參數(shù)點即可找到全局最優(yōu)解。給出了具體的算法流程，并進(jìn)行了仿真。仿真實驗結(jié)果表明渦流搜索算法是選取SVM參數(shù)的有效方法。

渦流搜索算法 支持向量機 參數(shù)優(yōu)化 單解優(yōu)化算法

許多現(xiàn)實生活中的優(yōu)化問題由于本身性質(zhì)比較復(fù)雜,精確優(yōu)化方法常常不能解決這些問題[1]。因此,使用近似算法就成為解決這類問題的替代方案。元啟發(fā)式算法是一類不依賴具體問題的解決方案，更具有通用性，更適用大量不同的優(yōu)化問題。元啟發(fā)式算法能在合理的時間內(nèi)得到近似最優(yōu)解,但不能保證解的最優(yōu)性。元啟發(fā)式算法分為單解元啟發(fā)算法和群解元啟發(fā)算法兩種類型[2]。單解元啟發(fā)算法在任意時間都基于單解,包括基于啟發(fā)式局部搜索算法，例如模擬退火(SA)[3]、迭代局部搜索(ITS)[4]、向?qū)Ь植克阉?GLS)[5]、隨機搜索(RS)[6]和可變鄰域搜索[7]。群解元啟發(fā)算法首先構(gòu)建一些解，然后逐步迭代更新直至滿足終止條件，群解元啟發(fā)算法又分為兩類：進(jìn)化算法和群智能算法。進(jìn)化算法基于自然選擇機制,根據(jù)適應(yīng)度從種群中選出最佳個體，然后采用一些遺傳算子產(chǎn)生后代。進(jìn)化算法的典型代表是遺傳算法(GA)[8]和差分進(jìn)化(DE)[9]。群智能算法的靈感源自于一些動物(螞蟻、蜜蜂、魚及鳥等)的集體行為，通過間接傳播媒介進(jìn)行協(xié)作在決策空間中移動[1]。蟻群優(yōu)化算法(ACO)[10]和粒子群優(yōu)化算法(PSO)[11]是群智能算法的典型代表。

渦流搜索算法(Vortex Search，VS)是最近提出的一種新型元啟發(fā)式單解優(yōu)化算法,渦流算法靈感源自攪動液體產(chǎn)生的渦流現(xiàn)象，可以提供搜索行為的探索和開發(fā)之間良好的平衡，該方法通過使用一種自適應(yīng)步長調(diào)整方案的搜索行為模擬渦流現(xiàn)象，具有操作簡單和搜索能力強的突出優(yōu)點[12]。渦流算法的搜索能力超過了單解的模擬退火算法、模式搜索算法和群解的人工蜂群算法。支持向量機(Support Vector Machine，SVM)是基于結(jié)構(gòu)風(fēng)險最小化原則建立的一種機器學(xué)習(xí)模型，具有較為完備的統(tǒng)計理論基礎(chǔ)，對于小樣本集合的學(xué)習(xí)問題有著良好的適應(yīng)性[13,14]。支持向量機的參數(shù)決定了其學(xué)習(xí)性能和泛化能力。筆者提出一種基于渦流搜索算法的支持向量機分類預(yù)測模型，將渦流搜索算法用于支持向量機的參數(shù)優(yōu)化，可以不必遍歷搜索空間內(nèi)所有參數(shù)點便可找到全局最優(yōu)解。

1 渦流搜索算法①

渦流搜索算法通過使用一種自適應(yīng)步長調(diào)整方案的搜索行為模擬渦流現(xiàn)象。在初始階段,算法提供高效的探索行為，而當(dāng)算法收斂到局部解附近時,則開始進(jìn)一步的局部開發(fā),使當(dāng)前解向著最優(yōu)解逐步逼近。渦流搜索算法操作簡單且搜索能力強，不需要設(shè)置過多參數(shù)，只需考慮迭代次數(shù)、候選解集大小及搜索空間上下界等參數(shù)。

1.1生成初始解

首先考慮一個二維優(yōu)化問題，二維空間的渦流現(xiàn)象可以通過多個嵌套圓來模擬。渦流的最外圈最先被選為搜索空間的中心，推廣到d維空間中,初始的搜索中心μ0可用下式計算：

(1)

其中，Lupper和Llower都是d維向量，分別代表d維搜索空間的上界和下界。

1.2生成候選解

在渦流算法中,臨近解集Ct(s)通過高斯分布在d維空間中心μ向量附近隨機產(chǎn)生，t代表迭代次數(shù)，初始為0。初始候選解集Ct(s)={s1,s2,…,sk,…,sn}(k=1,2,3,…,n)通過以μ0為中心的高斯分布隨機產(chǎn)生,n代表候選解集中解的個數(shù)。高斯分布的一般形式如下：

(2)

其中，x是d×1維隨機變量,μ是d×1維樣本均值(渦流中心)向量,Σ是協(xié)方差矩陣。假如Σ對角元素相等而且非對角元素都為0，分布產(chǎn)生的形狀將是球形,因此協(xié)方差矩陣Σ可以通過下式計算：

Σ=σ2·Id×d

(3)

其中，σ2為高斯分布的方差，Id×d是d×d單位向量矩陣。高斯分布的初始均方差可以通過下式計算：

(4)

其中,初始均方差σ0也可以看作在二維優(yōu)化問題中渦流外圈的初始半徑r0。算法搜索初始階段弱化局部性是必要的，所以初始半徑r0可以選擇一個較大的值。因此，初始步驟通過設(shè)置大半徑的最外圈實現(xiàn)了搜索空間的全覆蓋。

1.3當(dāng)前解更新

在選擇階段，從C0(s)中選擇一個最好的候選解s′替換當(dāng)前解μ0，前提是候選解必須在搜索空間邊界內(nèi)才能被選擇，超出邊界范圍的解將變換進(jìn)入到邊界內(nèi)，計算公式如下：

(5)

其中，k=1,2,…,n，i=1,2,…,n，rand是一個符合均勻分布的隨機數(shù)。將最佳解作為搜索空間的新中心，縮減新的圈的半徑r1，圍繞新的中心周圍產(chǎn)生新的候選解集C1(s)，在候選解集C1(s)中評價所選的最優(yōu)解s′。若最優(yōu)解s′優(yōu)于到目前為止的最優(yōu)解,則更新最優(yōu)解。接下來將最好解作為縮減半徑后的第3個圈中心,重復(fù)上述過程直至滿足終止條件。

渦流搜索算法相對比較簡單，不同于以往的單解算法，它使用了極少的內(nèi)存量，而且使用了一個額外的步驟來在迭代時進(jìn)行搜索半徑縮減。半徑縮減過程可以看作是一種自適應(yīng)步長調(diào)整過程，搜索過程是算法成功的關(guān)鍵。

1.4搜索半徑縮減

在渦流搜索算法中,每一步迭代采用不完全伽馬函數(shù)的逆函數(shù)來縮減半徑的值，如下式：

(6)

其中，λ>0為隨機變量；α>0為形狀參數(shù),相當(dāng)于搜索的分辨率，取值范圍[0,1],隨著每次迭代搜索的分辨率也應(yīng)該被矯正，所以α在搜索過程中按下式計算：

(7)

為確保在開始階段實現(xiàn)搜索空間的全覆蓋,選擇α0=1,t為當(dāng)前迭代數(shù),Imax為最大迭代數(shù)。每步迭代渦流半徑按下式更新：

σt=σ0(1/λ)γ(λ,αt)

(8)

文獻(xiàn)[12]指出,當(dāng)λ=0.1時,搜索性能最好。這種更新方法可使搜索半徑在前半部分線性縮小，側(cè)重于全局探索,后半部分指數(shù)縮小，側(cè)重于局部開發(fā)，從而可較好地實現(xiàn)探索與開發(fā)之間的平衡。

2 渦流搜索算法支持向量機分類模型

2.1支持向量機

支持向量機是一種基于結(jié)構(gòu)風(fēng)險最小化原則建立的機器學(xué)習(xí)模型[13,14]，具有較為完備的統(tǒng)計理論基礎(chǔ)，對于小樣本集合的學(xué)習(xí)問題有著良好的適應(yīng)性。支持向量機的基本思想是：首先，在線性可分情況下，在原空間尋找兩類樣本的最優(yōu)分類超平面。在線性不可分的情況下，加入了松弛變量進(jìn)行分析，通過使用非線性映射將低維輸入空間的樣本映射到高維屬性空間使它變?yōu)榫€性情況，在該特征空間中尋找最優(yōu)分類超平面，通過使用結(jié)構(gòu)風(fēng)險最小化原理在屬性空間構(gòu)建最優(yōu)分類超平面，使分類器得到全局最優(yōu)。支持向量機分類模型如圖1所示。

圖1 支持向量機分類模型

支持向量機的學(xué)習(xí)過程可轉(zhuǎn)化為優(yōu)化問題，給定訓(xùn)練樣本集(xi,yi)，i=0,1，…，l,x∈Rn，y∈{±1}，超平面記為(w·x)+b=0。尋找最優(yōu)超平面，即：

s.t.yi[(wT·φ(xi))+b]≥1-ξi

ξi≥0,i=0,1,…,n

(9)

其中，w為超平面的法向量；C為錯分樣本的懲罰因子,C>0;ξ為松弛變量；b為閾值,b∈R。

引入Lagrange函數(shù)，將二次規(guī)劃問題轉(zhuǎn)化為相應(yīng)的對偶問題，即求：

(10)

其中，K(xi,xj)為核函數(shù)，受核函數(shù)參數(shù)的影響。

2.2支持向量機分類模型參數(shù)優(yōu)化

在式(10)中K(xi,xj)核函數(shù)受核函數(shù)參數(shù)G影響。支持向量機求解問題的關(guān)鍵為在最優(yōu)核函數(shù)下尋找最優(yōu)的懲罰因子C和核函數(shù)參數(shù)G，以使正確分類率最大。因此，以C和G為對象在不同核函數(shù)類型下，C和G在一定范圍內(nèi)取值，對于選定的C和G，把訓(xùn)練集作為原始數(shù)據(jù)集計算此組C和G下訓(xùn)練集驗證分類準(zhǔn)確率，最終取訓(xùn)練集驗證分類準(zhǔn)確率最高的那組C和G作為最佳參數(shù)，懲罰系數(shù)C與核參數(shù)G的選擇過程實際上是一個優(yōu)化搜索過程，如果采用傳統(tǒng)方法，很難獲得最優(yōu)參數(shù)，采用元啟發(fā)式算法可以不必遍歷所有參數(shù)點，也能找到全局最優(yōu)解，渦流搜索算法的特點十分適合于SVM參數(shù)優(yōu)化，針對支持向量機的參數(shù)優(yōu)化問題，筆者采用渦流搜索算法對SVM參數(shù)尋優(yōu)。

2.3渦流搜索算法的SVM參數(shù)尋優(yōu)算法

采用渦流搜索算法對SVM參數(shù)進(jìn)行優(yōu)化，需要對相關(guān)參數(shù)進(jìn)行設(shè)置并對適應(yīng)度函數(shù)進(jìn)行定義。渦流搜索算法主要設(shè)置最大迭代數(shù)、候選解集大小和搜索空間上下界。由于優(yōu)化SVM的主要目的在于獲得更高的正確分類率，因此采用訓(xùn)練集進(jìn)行交叉驗證下的正確分類率Vacc作為渦流搜索算法的適應(yīng)度函數(shù)，基于渦流搜索算法的SVM參數(shù)尋優(yōu)算法描述如下：

a. 初始化搜索中心μ0，初始化搜索半徑r0，初始化均方差σ0，最優(yōu)解的適應(yīng)度函數(shù)初始化無窮小，當(dāng)前迭代步數(shù)t=0；

b. 圍繞搜索中心μt以搜索半徑rt高斯分布生成候選解集，假如有候選解值超出邊界范圍將變換進(jìn)入到邊界內(nèi)，采用式(5)進(jìn)行變換；

c. 在候選解集C1(s)中評價一個解s′，若最優(yōu)解s′優(yōu)于到目前為止的全局最優(yōu)解,則更新最優(yōu)解，若s′的適應(yīng)函數(shù)值與目前最優(yōu)解相同并且懲罰因子C小于當(dāng)前全局最優(yōu)解的懲罰因子C，也更新最優(yōu)解；

d. 將最佳解作為搜索空間新中心，縮減新的圈半徑rt+1，接下來將最好解作為縮減半徑后的圈中心，迭代步數(shù)t=t+1；

e. 判斷是否滿足終止條件，迭代步數(shù)t是否小于最大迭代步數(shù)Imax，滿足條件則轉(zhuǎn)到步驟b重復(fù)上述過程；

f. 迭代結(jié)束，輸出迄今為止的最優(yōu)解S。

3 仿真實驗

為驗證筆者所提算法的有效性,選用了UCI數(shù)據(jù)庫中的Wine、Seeds和Iris 3個數(shù)據(jù)集進(jìn)行仿真實驗，這些數(shù)據(jù)集的詳細(xì)信息見表1。實驗中將數(shù)據(jù)集的各屬性通過線性歸一化到區(qū)間[0,1]內(nèi)，在劃分各數(shù)據(jù)的訓(xùn)練樣本和測試樣本時，取一部分作為訓(xùn)練數(shù)據(jù)，一部分作為測試數(shù)據(jù)。

表1 仿真實驗數(shù)據(jù)集

筆者將渦流搜索算法中的參數(shù)設(shè)置為：搜索鄰域解數(shù)10，最大迭代步數(shù)100，懲罰因子C的范圍[0,2],核函數(shù)參數(shù)σ取值范圍[0,2]。渦流搜索算法的適應(yīng)度變化曲線如圖2所示，算法的最佳適應(yīng)度是指每次迭代搜索的最大適應(yīng)度的解，平均適應(yīng)度是指每次迭代搜索解的所有鄰域解適應(yīng)度的平均值，全局最佳適應(yīng)度代表所有已搜索的最佳解的適應(yīng)度。

仿真實驗對于3種數(shù)據(jù)集分別采用粒子群算法和網(wǎng)格搜索算法作為參比模型，支持向量機的核函數(shù)采用徑向基(RBF)核函數(shù)，搜索SVM的最優(yōu)參數(shù),然后利用搜索到的優(yōu)化模型在測試樣本上進(jìn)行測試，不同算法的實驗結(jié)果比較見表2。

圖2 渦流搜索算法優(yōu)化迭代適應(yīng)度變化曲線表2 仿真實驗結(jié)果

數(shù)據(jù)集主要參數(shù)網(wǎng)格搜索算法粒子群算法渦流搜索算法Iris懲罰因子C0.57430.36131.0027核函數(shù)參數(shù)G4.00009.30751.9880適應(yīng)度1.000000.986841.00000正確分類率/%95.945993.243297.2973Seeds懲罰因子C3.03145.00902.8677核函數(shù)參數(shù)G2.29742.00002.5219適應(yīng)度0.9038460.9038460.903846正確分類率/%97.169897.169897.1698Wine懲罰因子C0.4061264.9142001.642200核函數(shù)參數(shù)G0.50003.44481.6761適應(yīng)度0.9746840.9887640.974684正確分類率/%96.629297.752898.8760

從表2的仿真實驗結(jié)果可以看出,采用渦流算法對SVM參數(shù)進(jìn)行尋優(yōu)所需計算量減少，而其正確分類率也優(yōu)于基于網(wǎng)格搜索和粒子群算法。

4 結(jié)束語

支持向量機的參數(shù)是影響支持向量機分類精度的重要因素，參數(shù)的選擇決定了其學(xué)習(xí)性能和泛化能力，筆者將渦流搜索算法用于支持向量機參數(shù)優(yōu)化，可以不必遍歷搜索空間內(nèi)所有參數(shù)點便可找到全局最優(yōu)解。仿真結(jié)果表明：渦流搜索算法是選取SVM參數(shù)的有效方法，經(jīng)參數(shù)優(yōu)化的支持向量機具有更高的分類精度，通過優(yōu)化參數(shù)達(dá)到提高支持向量機分類精度的目的。

[1] Talbi E G.Metaheuristics:From Design to Implementation[M].New Jersey:Wiley & Sons,2009:323～325.

[2] Boussaid I,Lepagnot J,Siarry P.A Survey on Optimization Metaheuristics[J].Information Science,2013,237(7):82～117.

[3] Kirkpatrick S,Gelatt C D, Vecchi M P.Optimization by Simulated Annealing[J].Science,1983,220(5):671～680.

[4] Lourenco H R, Martin O, Stutzle T.Iterated Local Search:Framework and Applications[J].International Series in Operations Research & Management Science, 2010, 146(5): 363～397.

[5] Alsheddy A. Empowerment Scheduling: A Multi-objective Optimization Approach Using Guided Local Search[D]. Esse:University of Essex,2011.

[6] Rastrigin L A. The Convergence of the Random Search Method in the Extremal Control of a Many Parameter System[J].Autom Rem Control，1963，24(10):1337～1342.

[7] Hansen P,Mladenovic N, Perez J A M.Variable Neighbourhood Search:Methods and Applications[J].Annals of Operations Research,2010,175(1):367～407.

[8] Holland J H.Adaptation in Natural and Artificial Systems[M]. Ann Arbor: University of Michigan Press,1975:1～211.

[9] Storn R,Price K.Differential Evolution—A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[M].Berkley:Int Computer Science Institute,1995:1～15.

[10] Dorigo M.Optimization,Learning and Natural Algorithms[D].Milano:Politecnico di Milano,1992.

[11] Kennedy J,Eberhart R C.Particle Swarm Optimization[C].Proceeding of IEEE International Conference on Neural Networks. New York:IEEE,1995:1942～1948.

[12] Berat D,Tamer O.A New Metaheuristic for Numerical Function Optimization:Vortex Search Algorithm[J].Information Sciences,2015,293(1):125～145.

[13] Vapnik V N.The Nature of Statistical Learning Theory[M].New York:Springer,1995.

[14] Vapnik V N，著,許建華,張學(xué)工,譯.統(tǒng)計學(xué)習(xí)理論[M].北京:電子工業(yè)出版社,2004.

ClassificationModelofSupportVectorMachineBasedonVortexSearchAlgorithm

LI Xue-gui1, XU Shao-hua2,LI Na3, ZHANG Qiang4

(1.SchoolofComputer&InformationTechnology,NortheastPetroleumUniversity,Daqing163318,China; 2.CollegeofComputerScienceandEngineering,ShandongUniversityofScience&Technology,Qingdao266590,China；3.DonghaoBranchCo.,DaqingOilfieldChemicalCo.,Ltd.,Daqing163312,China; 4.ResearchInstituteofExplorationandDevelopment,XinjiangOilfieldCompany,Karamay834000,China)

Applying the vortex search algorithm to SVM parameter selection was proposed, which searches for global optimal solution without going through all parameter points in the space. The concrete algorithm flow was presented and simulated to show that, the vortex search algorithm is an effective way for selecting SVM parameters.

vortex search algorithm, support vector machine,parameter optimization, single-solution optimization algorithm

TP183

A

1000-3932(2016)12-1291-05

2016-10-11(修改稿)

國家自然科學(xué)基金項目(61170132)；中國石油科技創(chuàng)新基金項目(2010D-5006-0302)