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

王明東，李有斌，馮民富

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

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

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

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

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

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

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

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

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

1 引理

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

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

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

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

minf(x)

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

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

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

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

2 V-線性支持向量機的變形算法

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

(1)

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

(2)

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

(3)

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

(4)

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

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

其次，容易證明該問題等價于問題:

(5)

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

(6)

ρ≥0

(7)

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

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

(8)

(9)

(10)

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

(11)

這里，δij是Kroneckerδ，當i=j時定義為1，其余都為0。

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

(12)

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

最后考慮解的問題：

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

如果α*是對偶問題(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)得：

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

表1 數(shù)值試驗結果統(tǒng)計

(20)

(21)

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

綜上所述：

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

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

3 非線性分類問題

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

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

4 數(shù)值試驗結果與分析

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

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

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

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

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

[4] GERALD R.數(shù)值計算方法和Matlab實現(xiàn)與應用[M].武衛(wèi)國,萬群,張輝,譯.北京:機械工業(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].北京:北京航空航天大學出版社,2003.

[7] 白鵬,謝文俊,劉君華.混合氣體紅外光譜支持向量機分析的新方法[J].光譜學與光譜分析,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

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

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

O245

A

2095-5383(2013)02-0022-04