一种新的模糊支持向量机多分类算法_刘太安
- 格式：pdf
- 大小：124.24 KB
- 文档页数：2
收稿日期:2007-07-02;修回日期:2007-09-20 基金项目:山东省自然科学基金资助项目(2007ZRB019FK)作者简介:刘太安(1963-),男,山东泰安人,副教授,主要研究方向为数据挖掘、软件工程(l ta999@163.co m );梁永全(1966-),男,山东聊城人,教授,博导,博士,主要研究方向为数据挖掘、智能计算;薛欣(1970-),女,山东新泰人,副教授,博士,主要研究方向为数据挖掘、支持向量机.一种新的模糊支持向量机多分类算法*刘太安1,梁永全2,薛 欣3(1.山东科技大学信息工程系,山东泰安271019;2.山东科技大学信息科学与工程学院,山东青岛266510;3.泰山学院数学与系统科学系,山东泰安271021)摘 要:在模糊多分类问题中,由于训练样本在训练过程中所起的作用不同,对所有数据包括异常数据赋予一个隶属度。
针对模糊支持向量机(fuzzy support vector m ach i nes ,FSV M )的第一种形式,引入类中心的概念,结合一对多1-a -a(one -agai ns-t all)组合分类方法,提出了一种基于一对多组合的模糊支持向量机多分类算法,并与1-a -1(o ne -agai ns-t one)组合和1-a -a 组合的分类算法比较。
数值实验表明,该算法是有效的,有较高的分类准确率,有更好的泛化能力。
关键词:支持向量机;模糊支持向量机;一对多组合;隶属函数;多分类算法中图分类号:TP391 文献标志码:A 文章编号:1001-3695(2008)07-2041-02N e w mu lti classifi cation al gorit hm based on f uzzy support vector m ach i nesL I U T a-i an 1,L IANG Y ong -quan 2,XUE X i n 3(1.Dept .o f Infor m ation &Eng i neeri ng,Shandong Universit y of S cience&Technol ogy,Ta i .an Shandong 271019,China;2.C oll ege of Infor -m ation Science&Eng i neeri ng,Shand ong Un i v e rsit y of S cience&T ec hnology,Q i ngdao Shand ong 266510,China;3.De p t .of M a t he m atics&Syste m S cie n c e ,Ta is han Un i versit y,Tai .an Shandong 271021,Ch i na )Abstract :In t he f uzzy mu lticl assifi cation proble m,gave a degree of membershi p to all the data incl udi ng abnor mal data as thetrai ning sa m ples played d ifferent affecti ons i n t he trai ning procession .Facing to the first f or m of f uzz y support vectorm ach i nes ,used the concept of the cl ass center .Consi dered w it h the one -agai ns-t all associati on assorti ngm ethod ,put out a new f uzz y sup -port vector m ach i nes m ulticl ass ificati on m odel based on one -agai ns-t all associati on ,and co m pared w it h one -agai ns-t one and one -agai ns-t all associati on assorti ngm et hod .The numerical test has m i proved that the algorith m i s effective ,and it has h i gher accurate rate of classifi cation ,al so better ab ility of generalizati on .Key words :support vectorm ach i nes(S VM );f uzzy support vector m ach i nes(FSVM );one -agai ns-t al;l m e m bersh i p f unc -ti on ;mu lticlassificati on algorith m0 引言模糊支持向量机(FSVM )是一种改进的支持向量机SVM 。
FS VM 有两种表现形式:a)2002年由台湾学者L in Chun -fu 等人提出的,根据训练样本在训练过程中所起的作用不同,对所有数据包括异常数据赋予一个隶属度,加大对容易错分样本的惩罚,以改进S VM 性能的模糊支持向量机[1];b )2001和2002年由日本学者T akuga 与Shigeo 提出的,针对两类问题推广到多分类问题时,决策过程中存在不可分区域,构造隶属函数,以减少不可分区域的模糊支持向量机[2,3]。
目前对FSVM 的理论以及应用的研究是S VM 领域研究的一个热点,对解决模糊分类问题有重要的理论意义和应用价值。
1 模糊支持向量机FSVM在机器学习的训练过程中,每个训练数据对支持向量机所起的作用是不同的。
边缘数据是最容易错分的且成为支持向量的机会多一些,而中间的数据成为支持向量的可能性要小一些,甚至根本不可能成为支持向量。
文献[1,4]根据训练样本在训练过程中的不同作用,对所有数据包括异常数据赋予一个隶属度。
对于最简单的两分类问题,首先对数据进行预处理:事先选择一个适当的隶属函数,对所有样本进行模糊化,得到每一个样本x i 隶属度s i ,于是训练集合便成为模糊训练集:(x 1,y 1,s 1),(x 2,y 2,s 2),,,(x n ,y n ,s n )其中:x i I R m ;y i I {+1,-1};0[s i [1。
对于上述新的训练集,为了得到最优分类超平面,需要解决以下优化问题:m i n 1/2X T @X +C 6ni =1s i N i(1)s .t .y i [X @<(x i )+b]\1-N i(2)其中:C 为常量;<将x i 从R m 映射到高维空间,将隶属度s i 引入决策函数的生成过程,求解式(1)(2)的优化问题,可由以下Lagrange 函数的鞍点给出:L (X ,b ,N ,A ,B )=1/2X T @X +C 6ni =1s i N i -6n i =1A i [y i (X @<(x i )+b)-1+N i ]-6ni =1B i N i(3)其中:A =(A 1,A 2,,,A n );B =(B 1,B 2,,,B n )为L ag range 乘子,将式(3)分别对X 、b 、N 求导并置为0,则有第25卷第7期2008年7月计算机应用研究Application R esearc h of C o m putersV o.l 25N o .7Ju.l 20089L (X ,b,N ,A ,B )/9X =X -6ni =1A i y i <(x i )=09L (X ,b ,N ,A ,B )/9b =-6ni =1A i y i =09L (X ,b ,N ,A ,B )/9N =s iC -A i -B i =0(4)将式(4)代入(3)可将式(1)(2)转换为m i n Q (A )=1/26ni =16nj =1A i A j y i y j K (x i ,x j )-6ni =1A i(5)s .t .6ni =1A i y i =0;0[A i [s i C(6)通过解决优化问题式(5)(6),构造出最优分类超平面,得到决策函数。
对于多分类问题,目前使用较多的方法有1-a -a 方法[5]、1-a -1方法[6]和DDAG 方法[7,8]。
S .A be 等人提出的解决多分类问题的FSVM 是在这些方法的基础上,构造隶属函数以减少不可分区域,达到解决问题的目的。
基于同样的思想方法,将其推广到F S VM 的第一种形式,便得到了笔者提出的基于一对多组合的模糊支持向量机多分类算法。
2 基于一对多组合的模糊支持向量机多分类算法在该算法中,对于一个k 分类问题,有如下的训练样本:(x 1,y 1,s 1),(x 2,y 2,s 2),,,(x n ,y n ,s n )(7)其中:x i I R m;y i I {1,2,,,k };0[s i [1。
首先引入类中心的概念[9]。
定义1 对于R m上的一类点{x 1,x 2,,,x n },记x c 为类中心点,r 为类半径。
其中:x c =1/n 6ni =1x ir =m ax x i+x c -x i +(8)结合一对多组合思想进行分类,即训练k 个两类分类器,且每次训练过程都是引入模糊性的,即事先为每个样本x i 生成一个模糊隶属度s i 。
例如现在要将第l 类和剩余样本分开,由以上定义易得第l 类的中心点,记为x +,类半径记为r +;剩余样本看做一类,其中心点记为x _,类半径记为r _。
给定一个充分小的D ,模糊隶属度s i 可定义为s i =1-+x +-x i +/(r ++D ) y i =l 1-+x --x i +/(r -+D ) y i X l(9)这里D 的引入是为了避免s i =0。
接下来进行模糊支持向量机的训练过程,每次可得一个两类分类器。
当所有训练结束时,得到k 个两类分类器:f i (x)=X i @x +b i =6nj =1a j y j K (x j ,x)+b ;i =1,2,,,k(10)对于新给的测试样本x 被分入:class (x)=arg m ax {f 1(x ),f 2(x ),,,f k (x )}(11)通过下面的数值实验,验证了该算法的有效性。
