作者简介:殷天石,女,1980年生,硕士研究生;孙济庆,男,1952年生,研究员,硕士研究生导师。
基于树型结构的SVM 多类组合分类器在文本分类中的应用
殷天石 孙济庆
(华东理工大学 上海 200237)
摘 要 针对最初的支持向量机只能解决两类分类问题,提出了一种基于树型结构的SV M 多类组合分类器。实验发现,不同的层次结构对这种树型结构的SV M 多类组合分类器的分类准确度会产生影响;实验结果表明多个SV M 的组合使用可以改善单个SVM 的分类准确度,但是改善的程度还有待提高。关键词 多类SVM 组合分类器 文本分类
文本自动分类就是将自然文本根据文本内容分为预先定义的若干个类别。由于文本自动分类能根据内容自动将文本分到正确的类别,帮助用户快速准确地定位所需信息,改善网络信息纷繁复杂的组织形式,文本分类技术迅速成为当今的一个研究热点。
许多机器学习方法被应用于文本分类,其中支持向量机(Support V ector M achine,简称SVM ),由于在小样本的学习问题、非线性和高维模式识别问题中的许多特有优势,收到了很好的效果。Joachims 将SVM 与简单的贝叶斯、决策树算法、k 近邻、Rocchio 算法进行比较,发现SVM 表现出比上述四种算法具有更好的性能[1]。Yiming Yang 、Xin Liu 在文献中对5种文本分类方法的重检验中发现,当训练集平均每个类中的正例数目少于10时,SV M 、KNN 、LLSF 比Nnet 、N B 显然要好[2]。
针对传统的SV M 方法只能解决两类问题比单个分类器的分类精度较差,本文提出了一个基于树型结构的SVM 多类组合分类器,在树型结构的基础上正确划分出多个类别,同时使用组合分类器来提高分类的性能。通过对经典数据集的实验验证,可以发现这种树型结构的SVM 多类组合分类器比单个分类器的分类精度有所提高,为文本分类提供了一条新的解决思路。
1 支持向量机简述
支持向量机是Vapnik1995年提出的[3],它基于统计学习理论中的结构风险最小化原则,尽量提高学习机的泛化能力。对于两类分类问题,学习机器的实际风险由两部分组成:一是经验风险即训练误差;二是置信范围,它和学习机器的复杂性和训练样本数有关。结构风险最小化原则就是不仅要使经验风险最小,还要尽量缩小置信范围,保证实际风险最小。
支持向量机从线性可分情况下的最优分类面发展而来,它的基本思想是要在一个向量空间中找到一个最优决策面。该决策面不仅能正确地将两类分开,而且还要使分类间隔尽可能大。图1
说明了支持向量机的基本原理。
图1 特征空间中的最优分类超平面
对于给定样本点:(x 1,y 1),,,(x l ,y l ),x i I R n ,y i I {-1,+1},i =1,,,l
在特征空间中可以被一个最优分类超平面(w #x )+b =0分开,要找到这个最优分类超平面,就是要求解以下二次规划方程式:
min 5(w )=
1
2
(w #w )(1)subject to y i [(w #x i )+b]E 1(2)利用拉格朗日优化方法将上述问题转化为其对偶问题,可得:
M ax W(A )=
6i
A i -1
2
w (A )#w (A )(3)subject to 6i
A i y i =
(4)
0F A F C ,i =1,,,l
计算得到最后的决策函数为:
label (x )=sgn (f (x ))=sig n (w 0#x +b 0)(5)
w 0=
6l
i=1
(a 0
i y i )x i (a 0
i E 0),i =1,,,l
对于线性不可分情况,通过选择适当的非线性变换映射到
某个高维特征空间,使得在高维空间样本线性可分。
2 多类支持向量机和组合分类器
2.1 多类支持向量机(M ulticlass SVM s) 最初的支持向量
机方法只能解决两类问题,许多学者都致力于把两类问题拓展到多类问题上。目前研究主要有两个方向:一是将多类问题转化为两类问题,通过多个两类分类器的组合,实现多类分类;二
34
#情报技术#
情报杂志2006年第2期
是直接在目标函数上进行修改,将多个分类面的参数求解合并到一个最优化问题中,通过求解该最优化问题/一次性0地实现多类分类。第二种方法虽然看似简单,但是求解的变量比较多,只适合用于小型问题中。目前应用较多的多类分类都是基于第一种研究思路实现的,其具体方法有:
a.一对多法(one-versus-rest,简称1-v-r SVM s)。训练时依次把某个类别的样本归为一类,其他剩余的所有样本归为另一类,这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。
b.一对一法(one-versus-one,简称1-v-1SVM s)。其做法是在任意两类样本之间设计一个SVM,因此k个类别的样本就需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时,每个分类器都对其类别进行判断,根据少数服从多数原则,最后得票最多的类别即为该未知样本的类别。Chih-Jen Lin的L ibsvm中的多类分类就是根据这个方法实现的。
c.层次支持向量机(H-SV Ms)。层次分类法首先将所有类别分成两个子类,再将子类进一步划分成两个次级子类,如此循环下去,直到得到一个单独的类别为止。
d.其他多类分类方法。除了以上几种方法外,还有有向无环图SVM(Directed Acyclic Graph SVMs,简称DAG-SVMs)和对类别进行二进制编码的纠错编码SVM s。
2.2组合分类器组合分类器,就是通过某种方式将多个分类器组合在一起,以对未知样本进行分类。在有监督分类中,组合分类能有效地提高分类的准确率。组合分类器一般包括两个方面:分类器的构建和多个分类结果的决策组合。
现有的分类器构建方法有:样本子集法、属性选择法、随机因素法、类别编码法等等。
常用的分类结果的组合方法一般认为有3种:第一种方法是采用投票法,如果多数分类器的预测结果认为样本属于某个类别,那么就认为该样本属于这个类别。第二种方法是加权投票法,即参与投票时,每个分类器有一个权重,表示其结果占最终决策的份量。第三种方法称为分层决策法,每一层有多种分类器,后一层利用前一层的分类结果进行再次分类。
2.3现有多类SVM的不足与改进分析现有的多类SVM 可以发现,随着样本类别的增多,1-v-1SVM s的分类器数量将会急剧增多,计算复杂度会大大增加,同时也影响了分类速度。1-v-r SVM s不像H-SVM s类别数会自上而下逐渐减少,1-v-r SVM s的分类速度也会明显慢于H-SVMs。研究发现,层次支持向量机当层次结构形态接近于正态树(从顶层开始,每个包含多个类别的节点都将类别均分成两类)时,将具有理想的训练速度,同时分类时仅需要非常少量的分类器[4]。在分类速度上明显优于前二类分类器。但是H-SVM s中,如果第一个类别没有很好地划分,原本属于第一个类别的样本由于接下来的类别无法识别,就没有机会再分成第一个类别了,同时原本属于非第一个类别的样本由于被划分为第一个类别,也就无法进行再次划分了,这样每一层上的误差会逐渐自上而下累积起来,影响这种分类方法的分类精度。因而,尽量减少每一层的分类错误率,显得至关重要。为了提高分类精度,本文对H-SVMs作了改进,采用组合分类器来提高准确率。3基于树型结构的SVM多类组合分类器
整个分类器基于一个树型结构,这个树型结构通过把一个多类问题转化为多级的两类问题来达到多类分类的目的。在每一层上分别用3种不同核函数的支持向量机进行分类,通过这三个分类器的不同组合来提高准确率。
根据组合分类理论[5],组合分类要有效地提高分类的准确度,需要满足:a.每个分类器的分类准确度均大于0.5;b.各分类器的误差偏置之间、误差漂移之间的差别较大;c.各分类器之间的错误相关性低。运用不同的核函数可以得到特征空间中不同的分类超平面,只要选择恰当的核函数或选取合适的参数,就有可能使每个核函数得到的分类错误尽可能的不相同。那么多个不同核函数的支持向量机得到的结果就有可能提高分类准确度。下面以3个类别的分类为例,示意如图2
所示。
图2树型结构的SVM多类组合分类器示意图
训练过程:对第一个类别A进行训练,把属于A类的训练样本标志为1,其余的标志为-1,这样对此类别的分类就成为一个两类问题。然后分别用3种不同核函数的SVM对已经重新标志的训练样本进行分类,得到3个不同的分类超平面,这样就完成了类别A的训练。对类别B进行训练,把已经训练过的A类别训练样本除去,然后进行与类别A相似的训练。不断重复这个过程,直到剩下最后两个类别的训练样本,重复进行相似的训练过程。最后一个类别的训练样本就不需要再训练了。这样一个k个类别的训练样本集需要进行3*(k-1)次训练。
测试过程:测试过程的类别判别顺序要根据训练顺序来确定。首先确定A类别,根据训练得出的3个不同的分类超平面,得到3个判别结果,再根据某种规则,决定是否属于A类别。把已经确定为A类别的测试样本去掉,进行接下来的一个类别的判断,这样不断重复进行,直至分到k-1个类别时,剩下的类别默认属于最后一个类别。
三个SVM分类器分别选用常用的三种核函数:
SVM1:采用线性核函数K(u,v)=u c*v
SVM2:采用多项式核函数K(u,v)=(g*u c*v+r)d SV M3:采用RBF核函数K(u,v)=ex p(-g*|u-v|2)在实验中为了多方面地测试分类器性能,我们对训练顺序进行了调整。第一种顺序是原定的类别顺序;第二种顺序是根据训练样本集中每类样本数目的多少降序排列得到的。
类别决策分别采用了最简单的投票法和加权投票法。基本的投票法就是根据少数服从多数原理,如3个分类器中有2个分类结果一样,那么类别决策为这2个分类器的分类结果。加权投票法最主要的是确定分类器的权重。我们把单个分类性能最好的分类器的权重设为2,其他的设为1。
4实验结果
实验数据来自流行的Reuters-21578数据集,该数据集选
35
情报杂志2006年第2期#情报技术#
自路透社1987年的新闻专线,是一个典型的文本分类用实验数据集。我们用的数据集是已经进行过预处理的[6],一共90个类别,训练集7000多个,测试集3000多个。我们选用其中样本数目最多的10个类别进行试验。除去属于多个类别的样本,一共得到6134个训练集样本,2389个测试集样本。大于3次出现的属性作为我们最后的属性特征,这样一共得到7968个特征。
4.1不同层次结构之间的比较实验首先使用了原始的类别顺序,然后由于在文本分类中,不同的类别样本数目差别很大,分布很不均衡,我们根据每个类别样本数目的多少进行降序排列。
表1按照原始类别顺序得到的实验数据(参数见前面)分类器准确率(%)线性核函数(c=500)89.58
多项式核函数(c=500,g=0.1,r=100,d=2)89.32
RBF核函数(c=500,g=0.01)90.79
组合简单投票89.54
组合加权投票90.41
表2按照类别样本数目降序排列得到的实验数据
分类器准确率(%)线性核函数(c=0.8)90.96
多项式核函数(c=0.8,g=0.01,r=10d=2)90.92
RBF核函数(c=50,g=0.01)90.96
组合简单投票91.34
组合加权投票91.34从以上数据可以看出,调整了顺序以后,准确率有了普遍提高,这说明不同的层次结构对分类准确度也会产生影响。此外在实验中调整顺序以后,因为类别样本数目最多的类别最先去掉,所以大大加快了以后的训练和测试速度。但是这样调整顺序并没有保证第一个训练的误差是最小的,为了减小误差,应该尽可能使第一个训练类别的误差较小,依次逐渐递减。
对比以上两个实验结果还可以进一步看出,核函数对分类
器结果会产生明显的影响。如果单个分类器的准确度已经很
高,组合的效果就并不十分明显。此外,分类器的组合决策方式也会对分类效果产生影响。当某种分类器的分类准确度占有明显的优势时,可以考虑加权投票的方式提高分类精度。
4.2与1-v-1方法的比较采用相同的数据我们与1-v -1方法进行对比,得到的实验数据如下:
表31-v-1方法得到的实验数据
核函数类型准确率(%)线性(c=2)92.01
多项式(c=50,g=0.01,r=10,d=2)91.17
RBF(c=50,g=0.01)91.92从表3我们可以看出1-v-1法的分类精度与树型组合分类器分类精度基本相似,但是对于10个类别以上的分类问题来说,我们使用的树型组合分类器明显降低了计算复杂度。
5结论
从上面的分析可以看出,组合的效果不仅与不同的层次结构相关,而且与核函数的参数调整有关。选取不同的核函数可减小各个分类器之间的错误相关性,使组合效果更加明显。同时改善组合的决策方式,也是可改进的一个重要途径。
参考文献
1T horsten Joachims.T ext Categ orization with Support Vec t or:Machi nes.Learn-ing with Many Rel evant Features.In European Conference on Mac hine L e arning (ECM L),Berlin,1998
2Y.Yang and X.Liu.A Re-Ex amination of T e x t Categori zation M etho ds.In Proc.22th ACM Int.Conf.on Researc h and Devel o pment in Inform ation Re-trie v al(SIGIR.99),Berkele y,CA,1999
3Cort e s,Vapnik.Support vector networks.M a chine L e arning,1995;20(3)
4刘志刚,李德仁,秦前清,史文中.支持向量机在多类分类问题中的推广, 2004
5蒋艳凰,杨学军.多层组合分类器研究.计算机工程与科学,2004;(6)
6htt p://www.imm.dtu.dk/rem/i ndex.php?page=dat a
7Hsu and C.-J.Lin.A Comparison o f Methods for Mul t i-class Support Vector Machi nes.IEEE Transactions on Neural Networks,13(2),2002
8Chi h-Chung Chang and Chih-Jen Lin.L IBSVM:a L i brary for Support Vector Machi nes,2001.Software availa ble at http://www.csie.nt https://www.doczj.com/doc/fe15306913.html,.t w/cjli n/lib-svm
9祁亨年.支持向量机应用研究.计算机工程,2004;(10)
10魏玲,张文修.基于支持向量机集成的分类.计算机工程,2004;(13)
11蒋艳凰,周海芳,杨学军.监督学习的发展动态.计算机科学,2003;(7)
(责编:京梅)
(上接第33页)灵活的和经济的。它必须充分考虑互操作性和可扩展性。它是认证机构(CA)、注册机构(RA)等功能模块的有机结合。
3.8加快推进信息系统安全保障的基础设施建设建设信息系统安全监控基础设施,并建立相应的检测反应机制;加快银行专用密钥管理基础设施(KM I)、公钥基础设施(PKI)的建设;加快建立银行信息系统安全的快速应急反应机构(CERT),对重大安全事件进行分级限时响应。
3.9建立银行计算机安全服务体系人民银行要通过试点,研究、组织和指导银行业逐步建立计算机安全服务机制。制订运行规范,明确责任,合理配备必要的数据备份设施、应急设施和应急资源,统一调度,形成计算机安全事件的快速反应能力,最大限度地降低计算机系统的风险。
银行网络安全问题是一个系统工程,需要决策层、管理层、技术层面、可行的安全防护措施,把安全风险降低到最小程度。各层通力配合,从安全制度建设和技术手段方面着手,加强信息安全意识的教育和培训,增强自我保护意识,采取综合的防范措施,并不断改进和完善安全管理措施,自始至终坚持安全防范意识,逐步采取全面、可行的安全防护措施,把安全风险降低到最小程度。
参考文献
1钟捷,闫静.对发展网上银行的一些思考.中国金融电脑,2005;(4)
2吴蔚平.浅议网络银行的风险与监管.价格月刊,2005;(2)
3吴庆田.美国网络银行的风险控制分析与借鉴.湖南商学院学报,2005;(2)
4戴文进.网上银行风险的防范与管理.上海金融,2005;(1)
5王云红.浅谈网络银行及风险管理.中国科技信息,2005;(7)
6W.M ougay ar.Advanced stratigies f or internet driven comm e rce.Openi ng Digital Markets Burr Ridg e,IL:M c Graw-H i ll,1998
(责编:枰钧)
36
#情报技术#情报杂志2006年第2期