基于支持向量机的增量式算法

第42卷第12期2008年12月

浙 江 大 学 学 报(工学版)

Journal o f Zhejiang U niv ersity (Engineer ing Science)

Vol.42No.12Dec.2008

收稿日期:2007 07 12.

浙江大学学报(工学版)网址:w w w.journals.z https://www.sodocs.net/doc/1118271484.html,/eng

基金项目:宁波市自然科学基金资助项目(2008A610026);浙江大学宁波理工学院青年基金资助项目(1141147G601).作者简介:黄启春(1972-),男,福建宁德人,讲师,从事计算机科学与技术的研究.E mail:qichunhuang@https://www.sodocs.net/doc/1118271484.html,

通讯联系人:何钦铭,男,教授.E mail:h qm @https://www.sodocs.net/doc/1118271484.html,

DOI:10.3785/j.issn.1008 973X.2008.12.015

基于支持向量机的增量式算法

黄启春1,刘仰光2,何钦铭1,2

(1.浙江大学计算机科学与技术学院,浙江杭州310027; 2.浙江大学宁波理工学院,浙江宁波315100)摘 要:为了扩展支持向量机在大规模数据集和成批出现数据领域的应用,提出了一种基于支持向量机的增量式学习算法.利用标准的支持向量机算法训练得到初始的目标概念,通过增量式步骤不断更新初始的目标概念.更新模型是求解一个与标准支持向量机具有类似的数学形式的凸二次规划问题.证明了在可分情况下,如果新增加的样本不是位于边界区,那么增量式过程既不会改变分类平面也不会改变分类平面的表达.与现有的增量式支持向量机算法相比,该算法无需额外计算就可实现增量式的逆过程并且训练时间与增量式步骤数成反比.实验结果表明,该算法满足稳定性、能够不断改进性能以及性能回复三个准则.关键词:机器学习;模式分类;支持向量机;增量式算法;

中图分类号:T P181 文献标识码:A 文章编号:1008 973X(2008)12 2121 06

Incremental learning algorithm based on support vector machine

H U ANG Qi chun 1

,LIU Yang guang 2

,HE Q in ming

1,2

(1.College of Comp uter S cience and T echnology ,Zhej iang Univer sity ,H angz hou 310027,China;

2.N ingbo I nstitute T echnology ,Zhej iang Univer sity ,N ing bo 315100,China)

Abstract:An increm ental learning alg orithm based o n suppor t vecto r machine w as pro posed to pro cess large scale data o r data gener ated in batches.Initial goal concept lear ned by standard support vector m a chine algo rithm was updated by an updating model.T he model so lved a co nvex quadr atic pr ogram ming similar to standard support vecto r machine algo rithm.The algorithm proves that not only classification hy perplane but also the repr esentation of classification hyperplane areno t changed dur ing incr em ental learning pro cedure if the new samples areno t in the boundary in separable case.Decreasing learning procedur e is easy to implem ent w itho ut ex tra computation and learning time is inversely proportional to increm ental learning step co mpared w ith ex isting incremental learning support vector alg orithms.Results show that the alg orithm satisfies the three criteria of stability ,improv em ent and recoverability.

Key words:m achine learning;pattern classification;suppo rt vector machine;incremental learning algorithm

基于统计学习理论的支持向量机[1 2]作为一种新的机器学习算法,已经成功地应用到许多领域,主要的原因是其近似实现了结构风险最小化原则,具有解的稀疏表达性以及运用核技巧等优点.实际上,支持向量机训练过程是求解一个凸二次规划问题,

当数据量比较小时,用传统的求解二次规划的方法即可求解.但当数据量增大时,求解该二次规划问题所需要的内存随数据量增长成平方关系增长,故很难用传统的方法对其求解.因此,研究新的求解凸二

次规划的方法成了支持向量机的关键,目前已经提

出了2种不同的方法来克服这个缺点:分解的方法[3]和增量式方法[4 10].

与分解方法相比较,增量式学习方法的好处是不但可以处理训练集太大以至无法载入内存的情况,而且还可以处理时间序列数据或成批出现的各种科学研究数据的情况.目前,已经提出的大部分增量式算法的出发点是解决训练集太大,难于用传统的算法解二次规划问题.它们的主要思想是基于支持向量能够充分表达训练数据的思想,把大的训练集合划分为多个互不相交的训练集合,首先在其中某个子训练集合上训练支持向量机得到相应的支持向量,然后把支持向量与下一个训练合并重新训练,不断重复此过程直到最后一个子训练集.它们的主要缺点是除了增量式的最后一步,其他各步增量式过程只是选择样本,而没有利用前面步骤中得到的决策平面的信息.

本文提出一种新的增量式算法,其主要思想是借鉴人的学习过程.与已知的增量式支持向量机相比,该算法具有如下特点:

1)该算法的更新模型与标准的支持向量机具有类似的数学形式,任何用来求解标准支持向量机的算法都可以用来求解该算法的更新模型;

2)该增量式算法的逆过程易于实现,即如果在增量式过程中,发现泛化性能下降无需额外的计算就可以返回上一步.

3)实验的结果表明该方法与批处理方式训练支持向量机得到的结果相当,并且同其他增量式支持向量机相比较,该算法在大部数据集合上的性能良好.

1 相关工作

1.1 支持向量机

只考虑两类分类问题,假设其包含l个样本的训练集为(x i,y i),i=1,2, ,l,输入向量x i R n,输出编码为y i=1或-1,支持向量机构造类别间的分类间隔最大的超平面称为最优分类超平面.较大的分类间隔意味着分类器具有较好的泛化能力[1 2].假设支持向量机构造的分类超平面为w!x+b=0.决策函数为f(x)=sg n(w!x+b),在线性不可分数据上,求最大分类间隔的最优超平面问题转化为如下的二次规划问题[1 2]:

min?w?22+C#

l

i=1

i,

s.t. y i(w!x i+b)?1- i,

i?0,i=1, ,l,

x i R n,y i{+1,-1},i=1, ,l.

(1)

式中:C为非负实数,为了求解该问题通常把它转化

为其对偶问题为

m ax#

l

i=1

i-1

2

#

i,j

i j y i y j(x i!

x j),

s.t. #l i=1y i i=0,

0% i%C,i=1,2, ,l.

(2)

式中: 为Lagr ange乘子.由上述问题得到 的最

优解,则SVM的分类函数为

f(x)=sgn(w!x+b)=sg n(#x

i

SV

i y i(x!x i)+b).

(3)

SV为支持向量集合,即相应的Lagrange乘子为零

的点组成的集合.如果分类问题是非线性的,则核函

数的作用是将输入空间映射到高维的核函数特征空

间,将非线性问题转化为高维空间中的线性分类问

题.根据泛函理论,特征空间中的对偶问题和决策函

数中的内积可以由输入空间中的核函数来代替,即

式(3)中的内积x i!x j用核函数k(x i,x j)代替,用

同样的方法可处理分类决策函数中的内积.这样就

得到非线性可分问题的支持向量机.但求解上面的

对偶问题,内存开销与训练数据成平方增长.当数据

量较大时难于用传统的求解方法求解.因此,必须考

虑其他的求解方法.

1.2 增量式支持向量机

为了在大训练数据集上实现支持向量机算法,

通常采用分解方法和增量式方法.本文主要考虑增

量式学习方法.增量式支持向量机训练算法可粗略

地分为:增量式精确训练算法和近似训练算法[6 10].

Cauwenberghs等人[7]提出的精确增量式算法的好处

是当对l训练数据增加一个点的时候,可以得到l+1

训练数据的精确解.并且该增量式过程是可逆的.

增量式近似训练算法的基本思想是:标准支持

向量机算法产生的支持向量集是原数据的压缩表

示,因此该类算法首先把训练数据集合分解为能够

装入内存的多个训练子集,用其中的某个训练集训

练支持向量机得到支持向量集.然后,在增量式步骤

中,利用支持向量数据和新数据更新当前的模型.在

更新当前概念的时候,存在4种不同选择更新模型

数据的方法[6]:

1)误差驱动方法,在增量式训练中保存被误分

的数据,设在t时刻的模型为SVM t,那么用该模型

对新数据进行分类,保存被误分的数据,当误分数据

的数量达到一定数量时,结合SVM t的支持向量和

被误分的数据用支持向量机算法更新当前的模型,

2122浙 江 大 学 学 报(工学版) 第42卷

得到新的模型SVM t+1.

2)固定划分的方法.训练数据被划分为固定大小的训练子集.在增量式步骤中,每批数据装入内存时与当前模型的支持向量数据一起依支持向量机算法更新当前的模型.

3)边界判别法.当新的数据点载入内存时判断条件y i f t(x i)%1是否成立.如果该条件成立保留该点,否则遗弃该点.当收集的数据点超过给定的数量时,结合SVM t的支持向量集一起更新当前的模型.

4)方法3)与方法1)相结合的方法.

但是,以上的增量式近似学习过程存在两个缺点:增量式的每步隐含着重复训练整个过程,除了最后一步,其他各步仅仅是起了选择训练数据的作用.另外,增量式的逆过程难于实行,在增量式学习过程中,如果更新了当前的模型,就无法准确得到原来的模型,除非重新学习.而在实际应用中,当采用增量式学习方法时,如果发现更新后的模型的泛化性能下降,寻找一种无需额外的开销就可以得到原来的模型无疑是很有好处的,即增量式过程是可逆的.

本文提出的增量式算法属于一种基于支持向量机的增量式近似学习方法,但它具有与标准的支持向量机具有类似的数学形式,任何用来求解标准支持向量机的算法都可以用来求解该算法的更新模型;并且该增量式算法的逆过程易于实现,即如果在增量式过程中,发现泛化性能下降无需额外的计算就可以返回上一步.同时从实验的结果看,该算法具有良好的性能.

2 新的增量式学习算法

根据式(3)决策超平面完全由参数w、b决定,假设利用初始训练集TS0得到超平面的参数为w0、b0,支持向量集为SV0.在第k步增量式学习后超平面的参数为w k、b k,支持向量机集为SV k.第k步的新数据集为D k{x k i,y k i)}l i=1.

增量式学习过程可描述为已知w k-1,b k-1,用SV k-1及新的数据集{(x k i,y k i)}l i=1选择适当的算法更新当前的模型.首先考虑线性可分的情况,并提出求解下面的二次规划问题来更新当前模型:

m in g(w k)=1

2

?w k-w k-1?22.(4)

约束条件为

y k i(w k!x k i+b k)?1; x k i D k.(5)式中:w k-1为前一次优化问题的解,当k=1时候,w0为标准支持向量机的解.显然当w k-1=0时,其与标准支持向量机具有相同的形式.

为了解该优化问题,将其转化为对偶形式,引入拉格朗日函数:

L=1

2

(w k-w k-1,w k-w k-1)-

#m k

i=1

k i(y k i(w k!x k i+b k)-1).(6)

其中: k i,i=1, ,m k为非负的拉格朗日系数.

根据最优解的条件可以得到

L w k=w k-w k-1-#

m

k

i=1

k i y k i x k i=0!w k=

w k-1+#

m

k

i=1

k i y k i x k i,(7)

L

b k-

#m k

i=1

k i y k i=0!#

m

k

i=1

k i y k i=0.(8)把式(7)代入式(6)并结合式(8)得到对偶问题:

m ax L=-1

2

#m k

i=1

#m k

j=1

k i k j y k i y k j x k i!x k j+

#

m k

i=1

k i-#

m k

i=1

k i y k i(x k i!w k-1).

(9)

约束条件为式(8)及

k i?0,i=1, ,m k.(10)通过解其对偶问题权向量w k由式(7)给出,偏移量b k是由训练过程隐含决定的,根据优化问题的KKT条件 k i(y k i(w k!x k i+b k)-1)=0,i=1, ,l,可以选择任何 k i&0来计算b k.从上面的推导可知,本文提出的更新模型同样可以利用核函数技巧.因此,利用核函数代替决策函数中的内积,并结合式

(7)得到如下的决策函数的形式:

f k(x)=sgn(w k!x+b k)=

sgn{(w k-1!x+#x

i

SV

k

i y i x i!x)+b k}=

sgn{f k-1(x)+#x

i

S V

k

i y i x i!x+b k-b k-1}.

(11)

从决策函数f k(x)的表达中可知返回增量式的上一步是很容易实现的,无须额外的计算.

下面的定理指出用上面提出的更新算法更新初始的概念,在线性可分情况下,新数据点如果不属于边界区,那么更新模型不但不会改变决策超平面,而且不会改变决策超平面的支持向量表达.而用标准的支持向量算法作为更新模型虽然不会改变决策超平面,但可能改变它的支持向量表达.

定理1 如果在k步增量式学习过程中的核函数及其参数与k-1步相同且数据集D k满足可分

2123

第12期黄启春,等:基于支持向量机的增量式算法

条件

y k i

(w

k -1

! (x k i

)+b

k -1

)?1; x k i

D k .(12)

其中 (!)为核函数k (!,!)相应的核映射,满足k(x i ,x j )= (x i )! (x j ),那么 k

i =0,i =1, ,m k .

证明:为简单记,只对k (x i ,x j )=?x i ,x j (给出证明.由式可得L =-1

2

#m

k

i=1#

m

k

j=1 k i k j y k i y k j x k i !x k j

+

#

m

k

i=1

k

i -#m

k

i=1

k i

y

k i

(x k i

!w

k-1

+b

k-1

)+

#m

k

i=1

k i

y

k i b

k-1.(13)

考虑式(8)得到L =-1

2

#m

k i=1#

m

k

j=1 k i k j y k i y k j x k i !x k j

+

#

m

k

i=1

k

i -#

m k

i=1

k

i y k

i (x k

i !w

k-1

+b

k-1

).

(14)

根据定理条件及式(14)可得L =-1

2

#m

k i =1#

m

k

j =1 k i k j y k i y k j x k i !x k j

+

#

m

k

i=1

k

i -

#

m

k

i=1

k

i y k

i (x k

i !w k-1

+b

k-1

)%

-

12

#m k

i =1#

m k

j =1

k i k j y k

i y k

j x k

i !x k

j +

#

m k

i =1

k

i -

#

m k

i=1

k

i %0.

(15)

显然当 k

i =0,i =1, ,m k 是对偶问题(9)的一个可行解.再根据式(14)及正定核函数的定义,它也是唯一的最优解.

对于线性不可分情况,采取标准支持向量机相

同的技术,引入松弛变量 k

i ?0,i =1, ,m k ,相应的

规划形式为

min g(w k )=12?w k -w k -1?22

+C #m

k

i =1

k i ;

(16)

约束条件为

y k

i

(w k

!x k i

+b k

)?1; x k i

D k ,

i ?0,i =1, ,m k .

(17)

同样可以把它转化为相应的对偶形式.其对偶形式与可分情况基本相同,除了约束条件(10)变为

0% k

i %C;i =1, ,m k .(18)

通过以上分析可知道只要对标准支持向量机的实现方式稍加修改就可实现增量式更新模型的求解.

基于支持向量机的增量式学习过程如下:

1)学习初始的概念.利用初始数据集T S 0训练支持向量机,得到决策函数的参数(w 0

,b 0

).

2)更新当前的概念.当有新数据可利用时候,利用它解规划问题(4)或(15)的对偶问题,学习得到新的概念.

在第2)步中同样可以利用前面提到的各种不

同的方法选择更新模型的数据.在随后的实验中使用固定划分的方法.为了叙述方便,称其更新模型为QSVM.

3 实验及评价

为了评价提出的算法性能进行了两个实验:一

个是比较了本文提出的增量式训练方式与批处理训练方式支持向量机的性能;另一个是比较了本文的增量式算法(New ISVM )与文献[8]的增量式算法(ISVM )的性能.比较的依据是独立测试集合上的分类精度.在实验中使用了来自U CI 基准数据集:

Banana,Diabetes,Flare So lar,H ear t,Br east Cancer,Germ an,其中有些数据本不是两类分类问题,但已经处理为两类分类问题,并且所有的数据都处理为均值为0,标准差为1.数据集合的基本信息见表1,实验中选择的核函数为径向基函数,其参数宽度为!.实验中用到了Gunn

[11]

实现的M ATLAB

支持向量机工具箱,更新模型的实现也是通过对该

工具箱的修改而成.所有的实验均在Intel P4PC

(1.4GH z CPU ,256MB 内存)Window s2000系统上进行.

表1 数据集及实验参数

T ab.1 Data set and ex per iment par ameters 数据集合名称

训练样本数测试样本数属性个数C !Banana Br east Cancer Diabetes

F lar e So lar

G erman

H eart

400200468666700170

490077300400300100

29892013

316.20015.19010.00010.2303.162

3.16215020355

120

3.1 增量式实验过程

在不同的实验中,为了比较的方便,选择相同的核函数及其参数.第一个实验是比较本文提出的增量式训练方式与批处理训练方式支持向量机的性能差别;第二个实验有2个目的:)本文提出的方法是否满足增量式算法必须具备的准则,?与其他增量式支持向量机方法的性能比较.为了分析这两种情况,设计了如下实验:首先将数据集分割为互不相交的训练集TR 和TE 测试集,然后将训练集进一步分割为10个部分DS i ,i =1, ,10.每一部分包含各不相同的10%训练集.实现了下面两种不同的增量式学习方式[8].

2124

浙 江 大 学 学 报(工学版) 第42卷

文献[8]的增量式训练过程(ISVM ):

1)设训练子集TS=DS 1;

2)用TS 训练SVM ,保存选择的支持向量集SV 1;

3)用过程2)训练的SVM 对T E 分类并记录相应的预测精度;

4)对1%i

(1)设T S=SV i +DS i +1;

(2)用T S 训练SVM,保存选择的支持向量集SV i +1;

(3)用过程2)训练的SVM 对T E 分类并记录相应的预测精度.

新的增量式训练过程(New ISVM):

1)训练子集T S=DS 1

2)用TS 训练SVM ,保存选择的支持向量集SV 1

3)用上一步训练的SVM 对TE 分类并记录相应的预测精度

4)对1%i

(1)设T S=DS i +1;

(2)用T S 训练QSV M,保存选择的支持向量集SV i +1及Lag rang e 乘子值和偏移量b k +1;

(3)用上一步训练的SVM 对T E 分类并记录相应的预测精度.

对各个数据集不同的训练集合和测试集重复增量式学习过程10次,得到每步增量式的平均预测精度.3.2 实验结果及评价

本文提出的方法经过10步增量式学习后在测试集合上的平均预测精度p 与批处理训练的结果如图1所示

.

图1 批处理和增量式支持向量机性能

F ig.1 Per for mance o f SV M w ith batch tr aining and in

cr emental lear ning

由图1可以看出,新的增量式算法与支持向量机算法性能相当,没有哪种方法具有绝对的优势,但批处理训练的支持向量机算法难以处理大数据集问题,而用本文提出的方法能够处理大数据集问题.

一种有效的增量式算法[6]

必需满足以下3个

准则

.

图2 两种增量式算法的性能

Fig.2 Performance of two incremental learning algorithms

(1)稳定性(Stability ):在每一步增量式学习后,测试集合上的预测精度变化不会太大;

(2)性能的改进(Im pro vement):随着增量式学习的进行,机器的预测精度应该有所提高;

(3)回复性能(Recoverability):学习算法应该具有性能回复的能力,即当在某一步学习步骤后性能下降了,算法应该具有回复的能力,随着学习步骤的增加性能回复或超过先前的性能.两种不同的增量式训练方法的实验结果如图2所示.

从图2中可以看出,在第n 步增量式训练后,在测试集合上的预测精度p 变化都不是很大,满足了增量式算法稳定性的要求;并且从图中可以看出预测精度随增量式步骤的增加总体上是不断改进的,

2125

第12期

黄启春,等:基于支持向量机的增量式算法

从图中可以知道本文提出的增量式算法具有性能回复能力.因此,本文提出的增量式训练过程是满足增量式算法要求的.

实验结果表明,本文提出的增量式算法与文献[8]提出的方法具有相同的性质,并且在大部分数据集上的性能与文献[8]提出的方法相同.实验结果还发现,随着增量式步骤的增加性能改变越来越小,最后增加训练步骤几乎不会改变分类的性能.这说明本算法可以用来估计表达问题所需要的样本数.

4 结 语

本文提出一种新的基于支持向量机的增量式训练算法.其主要过程是使用标准的支持向量算法得到初始的概念,然后利用文中提出的概念更新方法,即解一个类似标准支持向量机算法的凸二次规划问题.通过与批处理训练方法的性能的比较,表明该算法具有良好的性能.与文献[8]的增量式算法具有相同的性质并且性能相当.本算法的另一个特别点是更新模型具有与标准支持向量机类似的数学形式,能够得到解的稀疏表示;无需额外的计算就可以返回上一步;还能用于估计表达问题所需的样本数量.对不可分数据而言,如果增量式步骤不断增加,虽然性能变化不大,但支持向量数会不断增加,这样会降低预测的效率.因此,对增量式停止的条件以及求解最小支持向量表达问题还有待进一步研究.

参考文献(References):

[1]V A PN IK V.The nature of statistical learning Theory

[M].New Yo rk:Spring er V er lag,1995.

[2]V A PN IK V.Statistical learning theory[M].N ew

Y or k:W iley,1998.

[3]H SU C W,L IN C J.A simple deco mpo sitio n metho d

fo r suppor t v ecto r machines[J].Machine Learning,

2002(46),291 314.

[4]XIA O R,WA N G J,Z HA N G F.A n appro ach to incre

mental SV M learning algo rit hm[C],12th IEEE Inter national Conference on Tools with Artif icial Intelligence (IC TAI2000).V anco uv er,BC,Canada:IEEE Com puter Society,2000:268 273.

[5]M IT RA P,M U RT HY C A,SAN K A R K P.Data con

densation in larg e databases by incr emental learning w ith suppo rt vector machines[C],International Conference on Pattern Recognition(IC PR?00).Barcelona,Spain: IEEE Comput er Scociety,2000:2708 2711.

[6]SYED N A S,LIU H,SU N G K.Fr om incr emental

lear ning to mo del independent instance select ion-a suppor t vecto r machine approach[R].Singapor e:N a tional U niversit y of Sing apo re,1999.

[7]CA U W EN BER GH S G,POG GIO T.Incr emental and

decremental suppor t vector machine lear ning[C]//Neu ral Information Processing Systems2000,Denver,CO, U SA:M IT,2000:409 415.

[8]SY ED N A S,L IU H,SU N G K.Incremental learning

wit h support vector machines[C],Proceedings of the Workshop on Support Vector Machines at the Internation al Joint Conference on Artificial Intelligence(IJCAI 99).

Sto ckho lm,Sw eden:[s.n.],1999.

[9]DOM EN ICON I C,GN U N OP U LO S D.Incr emental

suppo rt vector machine construction.Nick[C],Pro ceedings of the2001IEEE International Conference on Data Mining.San Jose,Califor nia,U SA:I EEE Com puter Societ y,2001:589 592.

[10]RA L AI VO L A L,DAL CH E BU C F.Incr emental sup

po rt vector machine learning:a local a ppro ach[J].

Lecture Notes in Computer Science,Springer2001 (2130):322 330.

[11]GU N N S R.Suppo rt v ecto r machines for classification

and r egr ession[R].Southampt on:U niver sity o f Southampto n,1997.

2126浙 江 大 学 学 报(工学版) 第42卷