基于人为误差的支持向量机_AE_SVM

第10卷�第3期大连民族学院学报Vo.l10,No.3�2008年5月JournalofDalianNationalitiesUniversityMay2008�文章编号:1009-315X(2008)03-0243-03基于人为误差的支持向量机���AE-SVM*王�炜1,王淑艳1,郭小明2,刘丽琴1(1.辽宁师范大学数学学院,辽宁大连116029;2.辽宁石油化工大学理学院,辽宁抚顺113001)摘�要:传统的支持向量机是将分类问题转化成二次规划问题来解决的。针对传统的支持向量机算法及其变形算法忽略了训练集数据含有较大人为误差参与时其算法精度所存在的保障问题,提出了基于人为误差的支持向量机(artificialerror�supportvectormachine以下称AE-SVM)的基本理论,并建立了AE-SVM的理论模型。该模型是C-SVM模型的改进和推广。关键词:支持向量机(SVM);统计学习理论;AE-SVM中图分类号:O234文献标志码:ASupportVectorMachinebuiltonArtificialError���AE-SVMWANGWei1,WANGShu-yan1,GUOXiao-ming2,LIULi-qin1(1.SchoolofMathematics,LiaoningNormalUniversity,DalianLiaoning116029,China;2.SchoolofScience,LiaoningShihuaUniversity,FushunLiaoning113001,China)Abstract:Traditionalsupportvectormachinechangesthesortproblemsintoquadraticprogram�mingproblemstosolve.Inthispaper,forthetraditionalanddeformationalgorithmsofSupportVectorMachineneglectedwhenthepracticeofextractingdatawithbiggerparticipationofartifi�cialerror,wedescribedthedatafromthecentralizedtrainingwiththeparticipationoftheartifi�cialerror,emphaticallytransformedtheexperienceriskmeasurementoftheoriginalsupportvectormachinealgorithm,introducedthebasictheoryofthesupportvectormachinebasedontheartificialerror(calledAE-SVM),andestablishedtheoreticalmodelofAE-SVM,whichistheupswingandextensionofC-SVMmode.lKeywords:supportvectormachine(SVM);statisticallearningtheory;AE-SVM.��支持向量机SVM是统计学习理论的新发展,与传统统计学相比,SVM算法没有以传统的 经验 班主任工作经验交流宣传工作经验交流材料优秀班主任经验交流小学课改经验典型材料房地产总经理管理经验 风险最小化原则作为基础,而是建立在结构风险最小化原则之上,是一种新型的结构化学习方法。基于惩罚参数的支持向量机有两个相互矛盾的目标,即最大化间隔和最小化训练错误,通常引入�li=1�i作为一种经验风险的度量,描述训练集被错划的程度;引入结构参数C,描述模型对这两个矛盾目标的重视程度。C没有明确的物理意义,所以C的选择比较困难。为此支持向量机的若干变形算法被提出,比较成功的有v-SVM[1]、R-SVM[2]、W-SVM[3]、LS-SVM[4]等一系列变形的支持向量机算法。然而,这些算法均忽略了训练集中的数据若存在较大的人为误差时,如何保障模型的精度这个问题。另外,这种现象在实践中是经常发生的,并成为考验模型适应性的重要因素。例如,现有技术的不完善造成的人为误差、医学观察中的人为误差等。当训练集中有人为误差参与的时候,以上算法的效果会与实际产生较大的偏差。因此,本文主要针对近似线性可分的训练集中存在人为误差的情况,改造C-SVM的经验风险度量,建立AE-SVM的理论模型。*收稿日期:2007-12-11作者简介:王炜(1960-),女,辽宁本溪人,教授,博士,主要从事最优化理论与方法研究。244��大�连�民�族�学�院�学�报第10卷1�传统的SVM模型给定训练集T={(x1,y1),,(xl,yl)}!(X∀Y)l,xi!X=Rn,yi!Y={-1,1},i=1,,l,寻找X=Rn上的一个实值函数g(x),以便用决策函数f(x)=sgn(g(x))推断任一模式x相对应的y值。由此可见,求解分类问题实质上就是找到一个把Rn上的点分成两部分的规则。当训练集线性可分时,SVM模型为min,b12##2s.t.�yi((∃xi)+b)%1,(1)i=1,,l。当训练集近似线性可分时,任何分划超平面都有可能出现错划的情况[5]。对第i个训练点(xi,yi)引进松弛变量�i%0,有下面的SVM模型min,b12##2+C�li=1�is.t.�yi((∃xi)+b)%1-�i,(2)i=1,,l,式中,�为松弛变量,C为正则化参数。也称该支持向量机为C-SVM[1]。科研工作者经过大量试验证明了该支持向量机无论是在理论还是实践中都是比较成功的,但同时也发现了一些不足。例如,C没有直观解释,在实际应用中很难选择适当值;C-SVM算法不适合处理大规模问题;C-SVM算法不能根据每个样本点数据的重要性区别对待等。针对这些不足,研究者们分别建立了一些修正模型,如v-SVM、R-SVM、W-SVM等。除此之外,近期最受关注的一个修改模型就是LS-SVM,它是传统的SVM算法与最小二乘技术的完美结合。虽然目前SVM有很多种类的修改模型,但是它们都忽略了如果训练集中某些样本点信息含有一定的人为误差的情况,本文就从该缺陷入手,引入了AE-SVM基本理论。2�AE-SVM基本理论C-SVM算法不能根据每个样本点数据的重要性区别对待,W-SVM中用si来惩罚C��i一项,但是si的选取需要合理化。文献[6]认为,在样本集中第一个样本的重要性最低,si选取为小于1的值,最后一个样本的重要性最高,si设定为1。采用线性插值方法得到其他样本点的加权系数。文献[7]针对v-SVM提出W-SVM方法,si只有2个值s+和s-,分别表示正类和负类对应的加权系数,根据二类别中每类样本的数量来确定s+和s-的值,即s+&s-=l+&l-,l+、l-分别表示正、负类的样本数。其实,针对训练集中某些样本点信息含有一定的人为误差的情况来改进现有SVM的核心,就是选用更为合理的经验风险的度量方法。3�基于人为误差的支持向量机���AE-SVM原始模型建立��给定训练集T={(x1,y1),,(xl,yl)}!(X∀Y)l,xi!X=Rn,yi!Y={-1,1},i=1,,l。对此训练集用C-SVM算法解C-SVM模型的对偶问题,求得最优解!*=(!*1,!*2,,!*l)T。原始问题的Lagrangian函数为�LP=12##2+C�li=1�i-�li=1!i{yi(xi∃+b)-1+�i}-�li=1∀i�i,式中,!i%0,∀%0。原始问题的KKT条件是-�li=1!iyixi=0,�li=1!iyi=0,C-!i-∀i=0,yi(xi∃+b)-1+�i%0,!i%0,∀i%0,!i{yi(xi∃+b)-1+�i}=0,∀i�i=0。由最优解!*和KKT条件中的互补松弛性可求得�i,i=1,,l。下面利用上述求得的�i,i=1,,l以及预先给定的常数#(0<#<1)的信息,提取受人为误差影响严重的训练点的集合T∋。由于�i度量了第i个训练点的误差情况,那么认为(若�i比�li=1�i的某个倍数大时,其对应的训练点可能存在较大的人为误差)这一结论成立是有道理的。于是可以取T∋={(xi,yi)|�i%#�li=1�i}�T。显然上述参数#(0<#<1)的意义是很明显的。例如取#=12,则有T∋={(xi,yi)|�i%#�lj=1j∗i�i}�T,这说明只有明显大于其他值的�i对应的训练点才被认为存在较大的人为误差。由此易知,#(0<#<1)取值越大时,被认为存在较大人为误差的判别条件越苛刻。因此,用这样的集合改造C-SVM会得到较好的效果。第3期王炜,等:基于人为误差的支持向量机AE-SVM245��定义函数h(z)=1,z<#�li=1�ie-(z-#�li=1�i),z%#�li=1�i得到基于函数h(z)的改进C-SVM算法的模型为min,b12##2+C�1i=1�ih(�i)s.t.�yi((∃xi)+b)%1-�i,(1)�i%0,i=1,,l。定义1(错误率∃)当对一个近似线性可分的训练集进行分类时,分类发生错误的百分比定义为错误率,记作∃。命题1�(+)若T∋=�,则h(z)=1;(,)T∋∗�,∃AE-SVM−∃C-SVM。证明�(+)若T∋=�,即�i<#�li=1�i,则由h(z)的定义可知h(z)=1。(,)由(+)知,C-SVM是AE-SVM的特例。又由概率的知识可知[8],若A�B则P(A)−P(B),所以有1-P(A)%1-P(B),即∃AE-SVM−∃C-SVM。由于h(z)是非光滑函数,因此上述问题为非光滑优化问题。下面探讨模型光滑化的问题。令q%(z)=1,z<#�li=1�i-%az2+bz+c,#�li=1�i-%−z−#�li=1�i+%,e-(z-#�li=1�i),z>#�li=1�i+%式中,a=-e-%4%,b=-e-%2%(#�li=1�i-%),c=-e-%4%(#�li=1�i-%)(#�li=1�i-%-2)+1,参数%为任意常数。命题2�(+)函数q%(z)在实数域上是连续的光滑函数;(,)lim%.0q%(z)=h(z)。证明略。因此可用以下模型近似代替模型(1),得新的模型min(,b,�i)12##2+C�li=1�iq%(�i)s.t.yi((∃xi)+b)%1-�i,(2)�i%0,i=1,,l,式中,a=-e-%4%,b=-e-%2%(#�li=1�i-%),c=-e-%4%(#�li=1�i-%)(#�li=1�i-%-2)+1,参数%为任意常数。由上述过程可以看出,模型(2)为光滑约束优化问题,其解法转化为经典解法。4�结�语本文在肯定了C-SVM算法的优点的同时,指出了它及其修正算法的不足。从C-SVM算法及其修正算法忽略了训练集中某些样本点信息存在一定的人为误差的情况的缺陷入手,考虑当实践中提取的数据近似线性可分并有一定的人为误差参与的情况下的支持向量机,从改变经验风险度量的角度对C-SVM模型进行改造,提出了基于人为误差的支持向量机���AE-SVM的模型及基本理论,为以后新的支持向量机算法的改进提供理论基础。参考文献:[1]邓乃扬,田英杰.数据挖掘中的新方法���支持向量机[M].北京:科学技术出版社,2004.[2]马义德,邱秀清.支持向量机若干优化算法的比较研究[EB/OL].[2006-09-01],http://www.paper.edu.cn.[3]杜树新,吴铁军.模式识别中的支持向量机方法[J].浙江大学学报:工学版,2003,37(5):521-527.[4]TONYVANGESTEL,JOHANAK.Suykensbench�markingleastSquaressupportvectormachineclassifiers[J].MachineLearning,2004,54:5-32.[5]于乐源,董玉林.错误分离最小化的一个新的近似算法[J].辽宁师范大学学报:自然科学版,2007,30(1):20-22.[6]LINCF,WANGSD.Fuzzysupportvectormachines[J].IEEETransonNeuralNetworks,2002,13(2):464-471.[7]CHEWHG,BOGNERRE,LIMCC.Dualv-supportvectormachinewitherrorrateandtrainingsizebeasing[C]//Proceedingsof2001IEEEIntConfonAcoustics,Speech,andSignalProcessing.SaltLakeCity:IEEE,2001.[8]梁之舜,邓集贤.概率论及数理统计[M].北京:高等教育出版社,1988.(责任编辑�邹永红)