一种基于支持向量机V-SVM的变形算法

王明东，李有斌，冯民富

(1.四川大学 数学学院，成都 610064；2.西南油气田矿区服务事业部，成都 610081)

李有斌(1965- )，男(汉族)，四川南充人，统计师，学士，研究方向：统计学。

一种基于支持向量机V-SVM的变形算法

王明东1，李有斌2，冯民富1

(1.四川大学 数学学院，成都 610064；2.西南油气田矿区服务事业部，成都 610081)

基于传统的V-SVM算法，结合C-SVM二阶范数软间隔形式，构造出一种变形算法，避免了求解其对偶问题过程中解向量大小的限制，论证其解的存在以及唯一性，对于线性不可分问题，采用核函数技术，达到求解的目的，通过编程，得到数值结果，表明这是一种有效可行的算法。

V-SVM；变形；解；核函数；数值试验

支持向量机(Support Vector Machine,SVM)是在统计学习理论的基础上，基于结构风险最小化[1]理论发展起来并借助最优化方法来解决机器学习问题的新工具。它最初于20世纪90年代由Vapnik提出，在特征空间中构建最优分割超平面，使得学习器能够得到全局最优化，并且使整个样本空间的期望风险以某个概率满足一定上界。近年来在其理论研究和算法实现方面都取得了突破性进展，成为克服“维数灾难”和“过学习”等问题的有效方法。支持向量机是针对线性可分的情况进行分析的，对于非线性问题，支持向量机的关键在于核函数[1-3]理论，把低维空间向量映射到高维数空间，达到划分的目的，并且满足Mercer条件[1-2]的核函数的运算只需在原低维空间中实现。

近年来，由于支持向量机方法在理论上的突出优势，使其具有较好的泛化能力，因此在很多领域得到应用并获得了大量的研究成果。但是，统计学习理论和SVM方法尚处于发展阶段，支持向量机仍有许多局限性与不足，许多理论在算法上尚未实现，并且算法与核函数以及参数的选择都影响着分类器的性能，不同的数据类型，对于不同的算法、核函数的选择、参数的选择有不同的依赖性，即采用不同的算法、核函数、参数，同样的数据可能产生非常大的分类差异。目前没有一套完整成熟的解决办法，在其优化过程中，没有成型的理论支持，一般都靠经验选择。本文基于传统的V-SVM[2-3]基本算法，从参数ε入手，参考C-SVM[2-3]及其变形算法，对V-SVM算法作出改进，通过理论论证及数值试验验证了此算法的可行性，增加了实际问题中算法的多样性选择。

1 引理

定理1 (Kuhn-Tucker定理) 给定一个定义在凸域Ω⊆Rn上的最优化问题[6]：

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

其中f∈C1是凸的，并且gi，hi是仿射函数。一般的，点ω*是最优点的充要条件是存在α*，β*满足：

定理2(Wolfe对偶定理)考虑连续可微的凸最优化问题：

minf(x)

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

其中：f和每一个ci都是连续可微的凸函数，则：

1) 若上述原始问题有解，则它的Wolfe对偶问题[2]也有解。

2) 若上述原始问题和Wolfe对偶问题分别有可行解，则这2个可行解分别为原始问题和对偶问题的最优充要条件是它们相应的原始问题和对偶问题的目标函数值相等。

2 V-线性支持向量机的变形算法

下面讨论V-线性支持向量机的原始最优化问题的变形算法:设样本数据集(xi，yi)，i=1,2，…，n，xi∈Rd，yi∈{+1，-1}，V-线性支持向量机的原始最优化问题的变形算法：

(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)的目标函数为F(z)，由于原始问题是凸二次规划，其可行域非空，则问题必有解，并且由凸函数的极小定理[2]，知它的解集为凸集，任一解都是全局解。另一方面，若原始问题至少有2个解，设为z′，z″。令zt=(1-t)z′+tz″(t∈[0,1])，可以看出，zt也是最优解，并且满足关系F(z′)=F(z″)=F(zt)，两边同时对t求2次导数，得到ω′=ω″。

其次，容易证明该问题等价于问题:

(5)

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

(6)

ρ≥0

(7)

为此，只需证明问题(5)～(7)关于εi的解均非负。设(ω*，b*，ε*，ρ*)是问题(5)～(7)的解，若存在某个ε*lt;0，那么令ε*=0，则解(ω*，b*，ε*，ρ*)仍然满足条件(6)，但是目标函数值却减小了，与(ω*，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。

证明 ：根据Kuhn-Tucker定理，考虑Lagrange函数：

(12)

将上述极值条件(13)～(16)带入Lagrange函数得：

最后考虑解的问题：

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

如果α*是对偶问题(8)～(11)的最优解，那么根据凸约束问题解的充要条件定理以及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)得：

所以对偶问题和原始问题的目标函数值相等，由强对偶定理[2]，知(ω*,b*,ε*,ρ*)是原始问题的最优解。

表1 数值试验结果统计

(20)

(21)

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

综上所述：

图1 数据1的平面图以及分类线

图2 数据2的平面图以及分类线

3 非线性分类问题

对于非线性分类问题，SVM的解决思路是利用核函数，将线性不可分的样本数据在高维空间变换为可分的问题，然后进行分类，并且满足Mercer条件的核函数在高维空间的点积运算只需在原低维空间中就可实现，因此引入核函数K(x，x' )=(φ(x)·φ(x' ))。那么原始问题的对偶形式为：

类似于前面的线性形式，得到：

4 数值试验结果与分析

通过Matlab[4]编程，用函数随机产生线性与非线性的两类数据，每组样本分别包含100个训练数据与50个检验数据，而传统的V-SVM算法则由Libsvm[3,5]软件运行得出结果。表1为试验结果统计，核函数类型中，多项式函数为K(x,x' )=((x,x' )+1)2，径向基函数为exp(-|x-x' |2/2)，图1与图2分别为变行算法数据1，2的平面图与分类线。

如表1所示，变形算法对于线性训练数据构造的分类模型可以达到非常高的准确率，对于非线性数据也有较高的准确率，与传统V-SVM算法相比，有些数据有更高的分类准确率，是一种有效可行的算法。

[1] 克里斯特安尼.支持向量机导论[M].李国正,王猛,曾华军,译.北京:电子工业出版社,2004:70-98.

[2] 邓乃扬,田英杰.数据挖掘中的新方法:支持向量机[M].北京:科学出版社,2004:1-208.

[3] 白鹏,张喜斌,张斌,等.支持向量机理论及工程应用实例[M].西安:西安电子科技大学出版社,2008:1-37.

[4] GERALD R.数值计算方法和Matlab实现与应用[M].武卫国,万群,张辉,译.北京:机械工业出版社,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] 王日爽.泛函分析与最优化理论[M].北京:北京航空航天大学出版社,2003.

[7] 白鹏,谢文俊,刘君华.混合气体红外光谱支持向量机分析的新方法[J].光谱学与光谱分析,2007(7):1323-1327.

ADeformationalAlgorithmBasedonTraditionalV-SVM

WANGMingdong1，LIYoubin2，FENGMinfu1

(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方程的稳定化有限元方法”(11271273)

王明东(1986- )，男(汉族)，四川成都人，在读硕士研究生，研究方向：应用软件。

O245

A

2095-5383(2013)02-0022-04