基于直推式支持向量机的图像分类算法

1、收稿日期:2006-12-15;修订日期:2007-02-26基金项目:国家自然科学基金资助项目(K06A30060;北京交通大学“十五”科技基金资助项目(2004S M013作者简介:沈新宇(1982-,男,江苏无锡人,硕士研究生,主要研究方向:基于内容的图像检索;许宏丽(1963-,女,辽宁沈阳人,主要研究方向:多媒体数据库、基于内容的多媒体信息检索;官腾飞(1982-,男,硕士研究生,主要研究方向:机器学习.文章编号:1001-9081(200706-1463-02基于直推式支持向量机的图像分类算法沈新宇,许宏丽,官腾飞(北京交通大学计算机与信息技术学院,北京100044(xinyu_s

2、hen 摘要:直推式支持向量机(TS VM 是在利用有标签样本的同时,考虑无标签样本对分类器的影响,并且结合支持向量机算法,实现一种高效的分类算法。它在包含少量有标签样本的训练集和大量无标签样本的测试集上,具有良好的效果。但是它有算法时间复杂度比较高,需要预先设置正负例比例等不足。通过对原有算法的改进,新算法在时间复杂度上明显下降,同时算法效果没有明显的影响。关键词:支持向量机;直推式学习;图像分类中图分类号:TP391.41文献标识码:AI mage cl a ssi f i ca ti on ba sed on tran sducti ve support vector mach i n

3、esSHEN Xin 2yu,XU Hong 2li,G UAN Teng 2fei(Co m puter Infor m ation and Technology Institute,B eijing J iaotong U niversity,B eijing 100044,China Abstract:Transductive Support Vect orMachines (TS VM take advantage of the test sets as well as the train sets and inherit most p r operties of inductive

4、S VM s .They are more efficient than inductive S VM s,es pecially f or very s mall training sets and large test sets .But they still have disadvantages,such as high ti m e comp lexity and the require ment of "nu m +".The i m p r oved algorith m substantially reduces the ti m e comp lexity

5、with little influence on the perfor mance .Key words:Support Vect orMachine (S VM ;transductive learning;i m age classificati on0引言直推式学习1中,训练集中只有少数的有标签样本,而无标签样本是相对大量的;在这样的混合样本的学习过程中,分类器同时考虑了有标签样本和无标签样本分布信息。在传统的支持向量机学习方法中,学习算法的目标是使学习所得的分类器在训练集上有最小的错误率,用训练集的分布来近似预计测试集的分布。但在实际情况中,学习的目标是使训练得到的分类器,在测试集上有

6、尽可能小的实际误差,这就是直推式支持向量机(Transductive Support Vect orMachine,TS VM 所要解决的问题2。由于TS VM 存在时间复杂度较高,需要预先设置正负例比例等问题,研究者对其作出了多种改进。本文提出一种改进算法,在决策超平面附近选择一定数量的符合条件的样本点,并且根据所处位置赋予样本相应的标签,然后进行反复训练。由于S VM 的特性,S VM 分类器的构造只与支持向量有关,这样在决策超平面附近添加有标签样本点,可以使得分类器的构造逐渐向优化的方向移动,得到更好效果的分类效果。1TS VM 算法介绍直推式学习可以形式化定义如下:一组已经给定标签的样

7、本点集:(x 1,y 1,(x n ,y n ,x i R m,y i -1,+1(1和另一组具有相同分布的无标签样本点集:x 31,x 32,x 33,x 3k(2这样,TS VM 就可以被描述为这样的一个优化问题:M ini m ize:V (y 31,y 3k ,w ,b,1,3k =12w w +C ni =0i +C3kj =03jSubject to:n i =1y i w x i +b 1-i k j =1y 3j w x 3j +b 1-3jn i =1i >0k j =13j>0k j =1y 3j -1,+1(3其中C 和C 3是用户制定用以调节的参数,C 是有

8、标签样本的影响因子,C 3是无标签样本的影响因子;y 3j 是对于k 个无标签样本x 3j 的未知标签;i 和3j 分别是训练集样本和无标签样本在训练中错分的惩罚因子。Vapnik,Joachi m s 等人在TS VM 方面做了重要的工作,其中Joachi m s 的S VM light 软件3实现了TS VM 算法,并且已经被应用于文本分类、图像识别、生物技术等领域。Joachi m s 的TS VM 算法输入是训练集(x 1,y 1,(x n,y n 和测试集x 31,x 32,x 33,x 3k ;参数C,C 3分别是有标签样本和无标签样本的影响因子,num +是测试集中判为正例第27

9、卷第6期2007年6月计算机应用Computer App licati onsVol .27No .6June 2007的数量;输出是测试集中样本的标签y31,y3k。这个过程可以看作是一个从推导式S VM(C3_=C3+=0到完全的直推式S VM(C3_=C3+=C3的缓慢提升;在逐渐增大C3的过程中,无标签样本的影响逐渐增大,这样兼顾了有标签样本和无标签样本在分类中的贡献4。在直推式支持向量机的学习中,给予有标签样本较大影响值的同时,给予无标签样本初始较小影响值,并且逐步增大无标签样本的影响,这样训练得到的分类器在训练集和测试集上得到较小的分类误差;这相对于传统的支持向量机载训练集上误差最

10、小化,TS VM的分类器效果更好,更符合实际应用的需求。但是在时间复杂度上,TS VM与I S VM相比要高很多。这也是TS VM很重要的不足之处,当样本数量增加的时候,这就成为了主要问题。2本实验的算法介绍本实验的算法针对经典TS VM算法的不足,着重在时间复杂度上进行了算法改进。经典TS VM算法在时间复杂度高,主要是因为在初次分类后,将所有无标签样本添加标签,然后逐步调整C3,进行重新学习;在本实验的改进算法中,同样采取多遍训练,逐步改善的方法,但是在每一遍的训练过程中,不是对所有有标签样本和无标签样本的判定标签进行公式(3的优化,只选择支持向量附近的无标签样本点,这些样本点对于分类器的

11、训练影响较大。根据各无标签样本点的判别函数值,有下式定义: |f(x3i-1|<,when f(x3i>0(4 |f(x3i+1|<,when f(x3i<0(5其中f(x是判决函数f(x=w x+b,是样本点距离分类超平面距离的参数。根据支持向量机理论,支持向量面到分类判决面的距离是1/w,对应的判决函数值f(x=±1,因此在公式(4和(5中的的取值区间为0,1。在选择样本点进行加标签时,选择离分类超平面距离之内的所有无标签样本点,将这些样本按照分类判决进行加标签。这样可以逐渐调整分类超平面,也可以加快算法的收敛速度。无标签样本的选择如图1所示。算法的结束条

12、件设置为添加样本点以后,分类超平面没有偏移。这样既可以达到逐渐修改分类判决面的目的,又不会因为加入了对分类器没有影响的样本点而浪费训练时间。结合以上改进,本实验M y-TS VM算法总结如下所示:(,b,-=sv m_qp(x1,y1(xn,y n,C,0 C3=C;while(true(,b,3=sv m_qp(x1,y1 (xn,yn,(x31,y31(x3k,y3k,C,C3;if(S V not changebreak;while(ly3l×S gn(xl+b<0/Loop2 y3l=-y3l;/if pass the hyperp lane,s w itch the

13、label(,b,3=sv m_qp(x1,y1 (xn,y n,(x31,y31(x3k,y3k,C,C3;for every unlabeled examp lesif(|f(x3i-1|<&&f(x3i>0y3i=1;if(|f(x3j+1|<&&f(x3j<0y3j=-1;return (y31,y3k;图1无标签样本的选择3实验结果和分析基于内容的图像检索是采用图像内容进行图像信息查询的检索,通常根据图像所包含的色彩、纹理、形状以及对象的空间关系等低层次图像特征来分析图像信息,使用图像的多维特征矢量进行相似查询5。本实验主要使用

14、基于RG B颜色空间的192维彩色直方图特征进行分类。本实验将改进的TS VM算法应用在基于颜色直方图的图像语义分类上。实验选择了CORAL图片集中六个语义类图片,分别是花朵、飞机、日落、赛车、玛雅金字塔、桥,并进行5 -fl od交叉确认实验,以减少实验的偶然性。实验中的S VM 和TS VM算法采用S VM light软件实现。实验使用AMD A thl on 2800+,512M内存。将本算法和TS VM算法及其改进算法PTS VM算法6,还有支持向量机算法进行比较实验,所得结果如表1所示。表15-f old CV p recisi on/recall f or six classes

15、fr om CORAL(=0.3fl ower Prec Recp lanePrec RecsunsetPrec ReccarPrec RecmayaPrec RecbridgePrec RecTS VM60.3691.6063.0293.2065.5290.8058.478858.769054.7482.4 PTS VM56.8092.8083.2381.667.1787.2057.8580.857.9691.655.5888.4 S VM48.8596.8091.3855.686.2973.2058.6686.847.9099.654.9276.8 My-TS VM49.8296.8099

16、.0545.694.1169.259.8082.842.3710054.7672从上述实验数据可以看出,本实验的改进算法在部分图片集上总体性能相近或超过原有经典TS VM算法,和改进算法PTS VM;在部分图片集上,查准率(p recisi on能有所上升;部分图片集上,查全率(recall有所上升。但是在分类器的训练速度上,本实验的改进算法有了明显的提高,如表2所示。在本实验算法中,每次将多个无标签样本进行加标签,而且算法结束条件为分类决策面没有偏移(等价于重新训练后(下转第1467页4641计算机应用2007年法和本文提出算法分别对图像进行消噪。本文采用峰值信噪(PS NR 比和均方差(M

17、SE 来衡量去噪的效果,其定义为:PSN R =10lgQ 2MNMm =1Nn =1f (m ,n -f (m ,n 2(dB (11=mnf (m ,n -f (m ,n 2MN(12其中Q 表示图像量化的级数,f (m ,n 是原始图像,f (m ,n 表示处理后复原的图像,M ,N 为图像矩阵的行、列总数。图像的去噪效果如图2所示 。图2去噪效果表1图像去噪效果比较MSEPS NR (dB wiener 143.696226.5903分层小波阈值消噪图像192.580225.3187本文算法消噪图像107.288027.8593由于添加噪声的随机性,对每种方法分别做5次运算结果,取其平

18、均的PS NR 和MSE 。处理结果如表1所示。通常情况下,峰值信噪比(PS NR 越高,表明去噪效果越好,而均方差(MSE 越低,表明去噪效果越好。从消噪后图像和表1中的数据可以看出,本文算法处理后的图像有较高的PS NR 及较小的MSE,并且与其他两种消噪方法相比,在有效去除噪声的同时,图像产生较小模糊,图像细节保存较好,效果最好。实验证明本文算法具有良好的去噪效果,采用此方法较之空间域滤波法和传统的小波去噪方法获得的去噪图像有更好的光滑性和相似性。图像细节和边缘的模糊,去除图像的大部分噪声,并有效保持了图像的细节和边缘信息,有利于医生的诊断工作。参考文献:1王芸,刘时进,王正强.基于小波

19、变换的核磁共振图像去噪方法J .现代电子技术,2005,3(14:63-64.2DONOHO DL ,JOHNST ONEL I M .I deal Spatial Adap tati on viaW avelet ShrinkageJ .B i ometrika,1994,81(3:425-45.3CCHANG SG,Y U B ,VETTERL I M.Adap tive W avelet Threshol 2ding f or I m age Denoising and Comp ressi on J .I EEE Trans I m agePr ocessing,2000,9(9:15

20、32-1546.4CA I TT,SI L VER MAN BW.I ncor porating infor mati on on neighbor 2ing coefficients int o wavelet esti m ati on J .Sankhya:The I ndian Journal of Statistics,2001,63:127-148.5(美崔锦泰.小波分析导论M .程正兴,译.西安:西安交通大学出版社,1997.24-28.6KE I M H,TRCKER D,MALLAT S,et al .On denoising and bestsignal rep resen

21、tati on J .I EEE Transacti on I nfor mati on Theory,1999,5(7:2225-2238.7DONOHO DL.W avelet Shrinkage and W.V.D.A Ten 2M inute TourJ .Pr ogress in analysis and App licati on,1993:109-128.8DONOHO DL.Denoising by Soft -thresholdingJ .I EEE Trans onI T,1995,41(3:613-627.9侯建华,熊承义,田金文,等.基于邻域阈值分类的小波域图像去噪算法

22、J .光电工程,2006,33(8:192-195.(上接第1464页没有新的无标签样本进入宽度为2的样本选择区间,这样相对于TS VM 算法和PTS VM 算法显著减少重复训练分类器的遍数;在最坏情况下,TS VM 的重复训练次数为2k 次,M y -TS VM 的重复次数为k 次。并且相对于TS VM 算法每遍训练对于所有样本进行如公式(3的优化,My -TS VM 算法只对于已经添加标签的样本进行优化,这样优化子问题涉及的样本个数也显著的少,每遍训练的优化问题时间复杂度显著的下降。两个层次的改进都有利于算法的时间复杂度下降。表25-fold CV train ti m e f or si

23、x classes fr om CORAL (=0.3Runti m e (m s Fl ower Plane Sunset Car Maya B ridge TS VM 91275668065706875146145890113056PTS VM 376525944149250940183125My -PTS VM759768790584731703基于上述的分析,以及实验结果,本算法在时间复杂度上的确有显著的下降,同时训练的结果没有很明显的下降。训练速度的提高在很多对时间有较高要求的领域具有很重要的作用。但是本实验的算法还有一些不足和改进,比如C 3的取值等方面。4结语本文首先介绍TS VM 算法,在此基础上提出了自己的改进算法,针对TS VM 的不足之处进行了改进,实验结果显示,改进算法达到了改进的目的,总体