王明東，李有斌，馮民富

(1.四川大學(xué) 數(shù)學(xué)學(xué)院，成都 610064；2.西南油氣田礦區(qū)服務(wù)事業(yè)部，成都 610081)

李有斌(1965- )，男(漢族)，四川南充人，統(tǒng)計(jì)師，學(xué)士，研究方向：統(tǒng)計(jì)學(xué)。

一種基于支持向量機(jī)V-SVM的變形算法

王明東1，李有斌2，馮民富1

(1.四川大學(xué) 數(shù)學(xué)學(xué)院，成都 610064；2.西南油氣田礦區(qū)服務(wù)事業(yè)部，成都 610081)

基于傳統(tǒng)的V-SVM算法，結(jié)合C-SVM二階范數(shù)軟間隔形式，構(gòu)造出一種變形算法，避免了求解其對(duì)偶問題過程中解向量大小的限制，論證其解的存在以及唯一性，對(duì)于線性不可分問題，采用核函數(shù)技術(shù)，達(dá)到求解的目的，通過編程，得到數(shù)值結(jié)果，表明這是一種有效可行的算法。

V-SVM；變形；解；核函數(shù)；數(shù)值試驗(yàn)

支持向量機(jī)(Support Vector Machine,SVM)是在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上，基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化[1]理論發(fā)展起來并借助最優(yōu)化方法來解決機(jī)器學(xué)習(xí)問題的新工具。它最初于20世紀(jì)90年代由Vapnik提出，在特征空間中構(gòu)建最優(yōu)分割超平面，使得學(xué)習(xí)器能夠得到全局最優(yōu)化，并且使整個(gè)樣本空間的期望風(fēng)險(xiǎn)以某個(gè)概率滿足一定上界。近年來在其理論研究和算法實(shí)現(xiàn)方面都取得了突破性進(jìn)展，成為克服“維數(shù)災(zāi)難”和“過學(xué)習(xí)”等問題的有效方法。支持向量機(jī)是針對(duì)線性可分的情況進(jìn)行分析的，對(duì)于非線性問題，支持向量機(jī)的關(guān)鍵在于核函數(shù)[1-3]理論，把低維空間向量映射到高維數(shù)空間，達(dá)到劃分的目的，并且滿足Mercer條件[1-2]的核函數(shù)的運(yùn)算只需在原低維空間中實(shí)現(xiàn)。

近年來，由于支持向量機(jī)方法在理論上的突出優(yōu)勢，使其具有較好的泛化能力，因此在很多領(lǐng)域得到應(yīng)用并獲得了大量的研究成果。但是，統(tǒng)計(jì)學(xué)習(xí)理論和SVM方法尚處于發(fā)展階段，支持向量機(jī)仍有許多局限性與不足，許多理論在算法上尚未實(shí)現(xiàn)，并且算法與核函數(shù)以及參數(shù)的選擇都影響著分類器的性能，不同的數(shù)據(jù)類型，對(duì)于不同的算法、核函數(shù)的選擇、參數(shù)的選擇有不同的依賴性，即采用不同的算法、核函數(shù)、參數(shù)，同樣的數(shù)據(jù)可能產(chǎn)生非常大的分類差異。目前沒有一套完整成熟的解決辦法，在其優(yōu)化過程中，沒有成型的理論支持，一般都靠經(jīng)驗(yàn)選擇。本文基于傳統(tǒng)的V-SVM[2-3]基本算法，從參數(shù)ε入手，參考C-SVM[2-3]及其變形算法，對(duì)V-SVM算法作出改進(jìn)，通過理論論證及數(shù)值試驗(yàn)驗(yàn)證了此算法的可行性，增加了實(shí)際問題中算法的多樣性選擇。

1 引理

定理1 (Kuhn-Tucker定理) 給定一個(gè)定義在凸域Ω?Rn上的最優(yōu)化問題[6]：

minf(ω)ω∈Ω，s.tgi(ω)≤0，i=1,2，…，k，hi(ω)=0，i=1,2，…，m。

其中f∈C1是凸的，并且gi，hi是仿射函數(shù)。一般的，點(diǎn)ω*是最優(yōu)點(diǎn)的充要條件是存在α*，β*滿足：

定理2(Wolfe對(duì)偶定理)考慮連續(xù)可微的凸最優(yōu)化問題：

minf(x)

s.tci(x)≤0，i=1,2，…，p，…

其中：f和每一個(gè)ci都是連續(xù)可微的凸函數(shù)，則：

1) 若上述原始問題有解，則它的Wolfe對(duì)偶問題[2]也有解。

2) 若上述原始問題和Wolfe對(duì)偶問題分別有可行解，則這2個(gè)可行解分別為原始問題和對(duì)偶問題的最優(yōu)充要條件是它們相應(yīng)的原始問題和對(duì)偶問題的目標(biāo)函數(shù)值相等。

2 V-線性支持向量機(jī)的變形算法

下面討論V-線性支持向量機(jī)的原始最優(yōu)化問題的變形算法:設(shè)樣本數(shù)據(jù)集(xi，yi)，i=1,2，…，n，xi∈Rd，yi∈{+1，-1}，V-線性支持向量機(jī)的原始最優(yōu)化問題的變形算法：

(1)

s.tyi((ω·xi)+b)≥ρ-εi

(2)

εi≥0，i=1,2，…，l

(3)

ρ≥0,其中，ε=(ε1，ε2，…，εl)T

(4)

首先，原始問題(1)～(4)關(guān)于(ω,b)的解存在，并且關(guān)于ω的解是唯一的。

證明：定義n+1+l+1維向量z=(ωT,b,ε1,…,εl,ρ)T，一方面記原始問題(1)～(4)的目標(biāo)函數(shù)為F(z)，由于原始問題是凸二次規(guī)劃，其可行域非空，則問題必有解，并且由凸函數(shù)的極小定理[2]，知它的解集為凸集，任一解都是全局解。另一方面，若原始問題至少有2個(gè)解，設(shè)為z′，z″。令zt=(1-t)z′+tz″(t∈[0,1])，可以看出，zt也是最優(yōu)解，并且滿足關(guān)系F(z′)=F(z″)=F(zt)，兩邊同時(shí)對(duì)t求2次導(dǎo)數(shù)，得到ω′=ω″。

其次，容易證明該問題等價(jià)于問題:

(5)

s.tyi((ω·xi)+b)≥ρ-εi，i=1,2，…，l

(6)

ρ≥0

(7)

為此，只需證明問題(5)～(7)關(guān)于εi的解均非負(fù)。設(shè)(ω*，b*，ε*，ρ*)是問題(5)～(7)的解，若存在某個(gè)ε*lt;0，那么令ε*=0，則解(ω*，b*，ε*，ρ*)仍然滿足條件(6)，但是目標(biāo)函數(shù)值卻減小了，與(ω*，b*，ε*，ρ*)是解矛盾。因此，問題(5)～(7)關(guān)于的解均滿足ε*≥0。

然后，問題(5)～(7)的對(duì)偶問題是：

(8)

(9)

(10)

αi≥0，i=1,2，…，l，α=(α1，α2，…，αl)T

(11)

這里，δij是Kroneckerδ，當(dāng)i=j時(shí)定義為1，其余都為0。

證明 ：根據(jù)Kuhn-Tucker定理，考慮Lagrange函數(shù)：

(12)

將上述極值條件(13)～(16)帶入Lagrange函數(shù)得：

最后考慮解的問題：

αi≥0，i=1,2，…，l

如果α*是對(duì)偶問題(8)～(11)的最優(yōu)解，那么根據(jù)凸約束問題解的充要條件定理以及Kuhn-Tucker定理，知存在乘子b*,s*,ρ*,ε*滿足:

Hα*+by*-ρ*e-s*+ε*=0,s*,ρ*,ε*≥0

(17)

b*(yTα*)=0,s*Tα*=0,ρ*(eTα*-υ)=0

(18)

由(17)式，可以得到：Hα*+by*≥ρ*e-ε*，ρ*,ε*≥0

(19)

由此可知，(ω*,b*,ε*,ρ*)滿足原始問題約束條件(6)，是可行解，并且由KKT條件(18)以及條件(15)得：

所以對(duì)偶問題和原始問題的目標(biāo)函數(shù)值相等，由強(qiáng)對(duì)偶定理[2]，知(ω*,b*,ε*,ρ*)是原始問題的最優(yōu)解。

表1 數(shù)值試驗(yàn)結(jié)果統(tǒng)計(jì)

(20)

(21)

式(20)、(21)相加除以2得：

綜上所述：

圖1 數(shù)據(jù)1的平面圖以及分類線

圖2 數(shù)據(jù)2的平面圖以及分類線

3 非線性分類問題

對(duì)于非線性分類問題，SVM的解決思路是利用核函數(shù)，將線性不可分的樣本數(shù)據(jù)在高維空間變換為可分的問題，然后進(jìn)行分類，并且滿足Mercer條件的核函數(shù)在高維空間的點(diǎn)積運(yùn)算只需在原低維空間中就可實(shí)現(xiàn)，因此引入核函數(shù)K(x，x' )=(φ(x)·φ(x' ))。那么原始問題的對(duì)偶形式為：

類似于前面的線性形式，得到：

4 數(shù)值試驗(yàn)結(jié)果與分析

通過Matlab[4]編程，用函數(shù)隨機(jī)產(chǎn)生線性與非線性的兩類數(shù)據(jù)，每組樣本分別包含100個(gè)訓(xùn)練數(shù)據(jù)與50個(gè)檢驗(yàn)數(shù)據(jù)，而傳統(tǒng)的V-SVM算法則由Libsvm[3,5]軟件運(yùn)行得出結(jié)果。表1為試驗(yàn)結(jié)果統(tǒng)計(jì)，核函數(shù)類型中，多項(xiàng)式函數(shù)為K(x,x' )=((x,x' )+1)2，徑向基函數(shù)為exp(-|x-x' |2/2)，圖1與圖2分別為變行算法數(shù)據(jù)1，2的平面圖與分類線。

如表1所示，變形算法對(duì)于線性訓(xùn)練數(shù)據(jù)構(gòu)造的分類模型可以達(dá)到非常高的準(zhǔn)確率，對(duì)于非線性數(shù)據(jù)也有較高的準(zhǔn)確率，與傳統(tǒng)V-SVM算法相比，有些數(shù)據(jù)有更高的分類準(zhǔn)確率，是一種有效可行的算法。

[1] 克里斯特安尼.支持向量機(jī)導(dǎo)論[M].李國正,王猛,曾華軍,譯.北京:電子工業(yè)出版社,2004:70-98.

[2] 鄧乃揚(yáng),田英杰.數(shù)據(jù)挖掘中的新方法:支持向量機(jī)[M].北京:科學(xué)出版社,2004:1-208.

[3] 白鵬,張喜斌,張斌,等.支持向量機(jī)理論及工程應(yīng)用實(shí)例[M].西安:西安電子科技大學(xué)出版社,2008:1-37.

[4] GERALD R.數(shù)值計(jì)算方法和Matlab實(shí)現(xiàn)與應(yīng)用[M].武衛(wèi)國,萬群,張輝,譯.北京:機(jī)械工業(yè)出版社,2004.

[5] CHANG C C，LIN C J.LIBSVM:a library for support vector machines[EB/OL].(2001-12-13)[2013-01-10].http://www.csie.ntu.edu.tw/～cjlin/libsvm.

[6] 王日爽.泛函分析與最優(yōu)化理論[M].北京:北京航空航天大學(xué)出版社,2003.

[7] 白鵬,謝文俊,劉君華.混合氣體紅外光譜支持向量機(jī)分析的新方法[J].光譜學(xué)與光譜分析,2007(7):1323-1327.

ADeformationalAlgorithmBasedonTraditionalV-SVM

WANGMingdong1，LIYoubin2，F(xiàn)ENGMinfu1

(1.Department of Mathematics, Sichuan University,Chengdu 610064,China;2. Mining Service Department of Southwest Oil and Gas Field,Chengdu 610081,China)

The basic V-SVM and C-SVM algorithm are commonly used in SVM(Support Vector Machine) .There are some relationship among the number of support vectors with the parameter V in the V-SVM algorithm.In practical applications, it has no obvious effect.By solving the dual problem, each component of dual problem's solution vector is less than the inverse of total number of sample data,but each component whether is zero or not directly affects the number of support vectors, When the number of sample data are great,it is easy to produce very large errors.Based on traditional V-SVM algorithm, combined with C-SVM two order norm soft margin method, this paper proposes a new V-SVM deformational algorithm, avoids the limit of its dual problem solution,demonstrates the existence of its solution and uniqueness.Kernel function technical is used to solve the nonlinear form.By programming, the numerical results are obtained,which shows that the algorithm is effective and feasible.

V-SVM; deformation; solution; kernel function; numerical experimentation

2013-03-20

國家自然科學(xué)基金“非定常N-S方程的穩(wěn)定化有限元方法”(11271273)

王明東(1986- )，男(漢族)，四川成都人，在讀碩士研究生，研究方向：應(yīng)用軟件。

O245

A

2095-5383(2013)02-0022-04