一种新的支持向量机增量学习算法

《一种新的支持向量机增量学习算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第6期厦门大学学报(自然科学版)Vol.41No.62002年11月JournalofXiamenUniversity(NaturalScience)Nov.2002文章编号:043820479(2002)0620687205一种新的支持向量机增量学习算法12曾文华,马健(1.厦门大学计算机科学系,福建厦门361005;2.杭州电子工业学院计算机分院,浙江杭州310037)摘要:提出一种新的支持向量机增量学习算法.分析了新样本加入训练集后,支持向量集的变化情况.基于分析结论提出新的学习算法

2、.算法舍弃对最终结论无用的样本,使得学习对象的知识得到了积累.实验结果表明本算法在保证分类准确度的同时,在增量学习问题上比传统的支持向量机有效.关键词:支持向量机;增量学习;学习算法中图分类号:TP181文献标识码:An增量学习技术作为一种智能知识发现技术,已l,Xi∈R,yi∈{±1}.支持向量机即为线性分类经得到了广泛的研究.它与传统的学习技术相比,优器,通过构造最优分类面,使得类别间的分类间隔最越性在于它不仅可以舍弃无用样本并减小训练集[4],大.较大的分类间隔意味着分类器具有较好的泛而且可

3、以充分利用学习的历史结果,使学习具有了化能力.延续性.很多学者基于传统的学习方法提出了新的设超平面方程为:[1,2]增量学习算法.但是由于传统学习算法不能保证wX+b=0(1)很好的泛化能力,常常陷于对问题的过学习和局部则决策函数为:最小等现象,因而基于传统学习方法的增量学习算f(x)=sgn(wX+b)(2)法通常得不到原问题较好的结果.求最大分类间隔的超平面问题可以转化为如下二次支持向量机(SupportVectorMachine—SVM)是寻优问题:一种新的机器学习技术,由Vapnik和他的

4、同事于l12[3]min2

5、w

6、+C∑ξi1995年提出.基于统计学习理论的坚实基础,SVMi=1有着很强的学习能力和较好的泛化性能.SVM学习s.t.yi(wXi+b)≥1-ξi(3)采用优化方法得到的结果是全局最优解n,不会产生Xi∈R,yi∈{±1},i=1,⋯,l传统方法中的过学习和局部最小等问题.SVM学习其对偶问题为:结果为支持向量集,通常是学习样本集的一小部分,ll支持向量集充分体现了整个样本集的属性.本文基max∑αi-∑yiyαjαijXiXji=1i,j=1于SVM寻优问题的K

7、KT条件和样本之间的关系,分s.t.0≤αi≤C(4)析了样本增加后支持向量集的变化情况,基于分析l结论提出了一种新的SVM增量学习算法.∑αiyi=0,i=1,⋯,li=1α为Lagrange乘子.由上述问题得到最优解α,则1支持向量机理论SVM的分类函数为:l1.1支持向量机f(x)=sgn∑αiyi(X·Xi)+b(5)i=1给定分类问题,其样本集为{Xi,yi},i=1,⋯,如果分类问题是非线性的,则采用一种称为核函数(KernelFunction)的方法,使输入空间映射到高维的核函数特征

8、空间,将非线性问题转化为该空间收稿日期:2002204225基金项目:工业控制技术国家重点开放实验室资助项目中的线性分类问题.根据泛函理论,特征空间中对偶(K01001)问题和得到的决策函数中的点积可以由输入空间中作者简介:曾文华(1964-),男,博士,教授.的核函数来替换.此时对偶问题为:·688·厦门大学学报(自然科学版)2002年ll1因此如果样本集的改变意味着新增样本集中含有违max∑αi-2∑yiyαjαijXiXj(6)i=1i,j=1背KKT条件的样本,并且这些样本中有些转化为支决

9、策函数为:持向量,新增样本加入时其Lagrange乘子α=0.根lf(X)=sgn∑αiyiK(Xi,X)+b(7)据式(8),如果其满足KKT条件,则yif(Xi)≥1;否i=1则,yif(Xi)<1,i=1,⋯,l.可得:其中K()为核函数.-1

10、图1所αi=0]yif(Xi)≥1(8)示.因此可以得到如下结论:0<αi

11、f(Xi)

12、≥1(11