（计算机应用技术专业论文）支持向量机文本分类算法的研究及其应用.pdf

大连理工大学硕士学位论文 摘要 随着信息技术和信息网络的飞速发展，从大量数据中挖掘出有用知识的数据挖掘已 成为具有重要意义的研究领域。支持向量机( s u p p o r tv e c t o rm a c h i n e ) 是近年来在统计学习 理论的基础上发展起来的一种新的模式识别方法，在解决小样本、非线性及高维模式识别 问题中表现出许多特有的优势。 虽然统计学习理论( s l t ) 有比较坚实的理论基础和严格的理论分析，但是其从理论 到应用还有很多尚未得到充分研究和解决的问题。例如，目前该领域的相关研究大多是 试图设计某种分类器，使其对未来所有可能样本的预期性能最优，而在很多实际问题中， 没有可能也没有必要用这样一个分类器对所有可能的样本进行识别，而往往只需要对一 些特定的样本进行识别。于是可以考虑设计这样一种更为经济的分类器，用它来建立一 种直接从有标签样本出发对特定的无标签样本进行识别和分类的方法和原则。相对于传 统的归纳推理方式，这种推理方式被称为直推式学习( t r a n s d u c t i v ei n f e r e n c e ) 。直推式学 习试图根据已知样本对特定的未知样本建立一套进行识别的方法和准则。渐进直推式支 持向量机学习算法( p r o g r e s s i v et r a n s d u c t i v es u p p o r tv e c t o rm a c h i n e ，p t s v m ) 可以较好地 适应各种不同的训练样本分布，实现了较一般意义上的直推式学习。本文针对p t s v m 中 的区域成对儿标注法学习过程不自然且易出错和标签重置法纠错能力不强的缺陷，提出 了一种改进的基于c a c h e 的渐进直推式支持向量机学习算法。该算法用值域成对儿标注 法和c a c h e 纠错法分别取代了p t s v m 中的区域成对儿标注法和标签重置法，不仅大大 减少了错误标记的次数，提高了算法的速度和准确度，而且消除了p t s v m 算法的死循 环现象。通过u c i 的w i s c o n s i nb r e a s tc a n c e r 和c w h 0 3 a 的s v m g u i d e 3 两个数据集的实 验，表明该算法是有效的。 将本文改进的基于c a c h e 的渐进直推式支持向量机学习算法应用于大连市公安局警 务综合应用平台的全文检索系统，显著提高了信息检索的准确性，提高了工作效率。同 时由于本文给出的系统的设计和实现方案具有通用性，对不同领域的检索系统的实现具 有一定的指导意义。 关键词：统计学习理论；支持向量机；直推式学习；c a c h e ；值域成对儿标注 支持向量机文本分类算法的研究及其应用 r e s e a r c ha n da p p l i c a t i o no f t e x tc l a s s i f i c a t i o na l g o r i t h mb a s e do ns v m a b s t r a c t a st h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n di n f o r m a t i o nn e t w o r k , d a t a m i n i n gf r o mal a r g en u m b e ro fu s e f u lk n o w l e d g eh a sb e c o m ea ni m p o r t a n t r e s e a r c ha r e a s v m i san e w l e a r n i n gm e t h o dd e v e l o p e d i nr e c e n ty e a r sb a s e do nt h ef o u n d a t i o n so fs t a t i s t i c a l l e a r n i n gt h e o r y i ri sg a i n i n gp o p u l a r i t yd u e t om a n ya t t r a c t i v ef e a t u r e sa n dp r o m i s i n ge m p i r i c a l p e r f o r m a n c ei nt h ef i e l d so fn o n l i n e a ra n dh i g hd i m e n s i o n a lp a _ t t e mr e c o g n i t i o n a l t h o u g hs t a t i s t i c a ll e a r n i n gt h e o r y ( s l t ) h a sm o r es o l i dt h e o r e t i c a lf o u n d a t i o na n d r i g o r o u st h e o r e t i c a la n a l y s i s ，t h e r ea r es t i l lm a n yp r o b l e m st ob ef u l l ys t u d i e da n d s o l v e df r o m t h e o r yt oa p p l i c a t i o n f o re x a m p l e ，c u r r e n tr e s e a r c hi nt h ef i e l d i st r y i n gt od e s i g ns o m ek i n do f c l a s s i f i e r w h i c hi se x p e c t e dt oh a v es u p e r i o ro p t i m a lp e r f o r m a n c ef o ra l lp o s s i b l es a m p l e s b i u t i nm a n yp r a c t i c a lp r o b l e m s ，i ti sn o tp o s s i b l e ，a n dn on e e da sw e l l ，t ou s es u c hc l a s s i f i e rt o i d e n t i f ya l ls a m p l e s ，b u to f t e no n l ys o m es p e c i f i co n e s 删sr e q u i r e sd e s i g n i n ga m o r e e c o n o m i c a lc l a s s i f i e r ，w h i c hh a st h ea b i l i t yt oi d e n t i f ya n dc l a s s i f ys p e c i f i cu n l a b e l e ds a m p l e s s t a r t i n gf r o ml a b e l e do n e s c o m p a r e dw i t ht r a d i t i o n a lm e t h o d so f i n d u c t i v ei n f e r e n c e ，i ti ss o c a l l e dt r a n s d u c t i v ei n f e r e n c e t s v m ( t r a n s d u c t i v es u p p o r tv e c t o rm a c h i n e ) t a k e si n t oa c c o u n t ap a r t i c u l a rt e s ts e ta n dt r i e st om i n i m i z em i s c l a s s i f i c a t i o n so f j u s tt h o s ep a r t i c u l a re x a m p l e s p t s v m ( p r o g r e s s i v et r a n s d u c t i v es u p p o r tv e c t o rm a c h i n e ) c a na u t o m a t i c a l l ya d a p t t od i f f e r e n t d a t ad i s t r i b u t i o n sa n dr e a l i z eat r a n s d u c t i v el e a r n i n go fs u p p o r tv e c t o r si nam o r eg e n e r a ls e n s e h o w e v e r ，t h ep r o c e s so fp a i r w i s el a b e l i n go fp t s v mi nt h em a r g i nb a n di su n n a t u r a la n d p r o d u c t se r r o r sm o r ee a s i l y a l t h o u g hd y n a m i c a la d j u s t i n go f f e r ss o m es o r to fe r r o rr e c o v e r y f u n c t i o n , i t sa b i l i t yi sl i m i t e d i na l l u s i o nt ot h es h o r t c o m i n g so fp t s v ml e a r n i n ga l g o r i t h m ， i c p t s v m ( a ni m p r o v e dc a c h e b a s e dp t s v m ) l e a r n i n ga l g o r i t h mi sp r e s e n t e d t h ea l g o r i t h m u s e sp a i r w i s el a b e l i n gi nt h er a n g ea n de r r o r - c o r r e c t i n go nc a c h et or e p l a c ep a i r w i s el a b e l i n gi n t h em a r g i nb a n da n dd y n a m i c a la d j u s t i n g t h e ni tn o to n l yg r e a t l yr e d u c e st h en u m b e ro f m i s 1 a b e l i n ga n di m p r o v e st h es p e e da n da c c u r a c y ，b u ta l s oe l i m i n a t ed e a dc y c l eo fp t s v m l e a r n i n ga l g o r i t h m t h r o u g he x p e r i m e n t i n go nt h ew i s c o n s i nb r e a s tc a n c e rd a t a s e to fu c i a n d t h es v m g u i d e 3d a t a s e to fc w h 0 3 a , w eh a v es h o wt h a tt h i sa l g o r i t h mi sv a l i d i nt h i sp a p e r ，t h ei m p r o v e dc a c h e b a s e dp t s v ml e a r n i n ga l g o r i t h mi su s e di nt h e f u l l t e x tr e t r i e v a ls y s t e mo ft h eg e n e r a la p p l i c a t i o np l a t f o r mo fd a l i a np o l i c e i ts i g n i f i c a n t l y i m p r o v e st h ea c c u r a c yo fi n f o r m a t i o nr e t r i e v a la n dt h ew o r ke f f i e i e n c y a tt h es a n l et i m e 。也e i i 大连理工大学硕士学位论文 s y s t e md e s i g na n di m p l e m e n t a t i o ni nt h i sp a p e ri sg e n e r a l ，a n ds oi th a sac e r t a i ng u i d i n g s i g n i f i c a n c et oi m p l e m e n t a t i o no fr e t r i e v a ls y s t e mi nd i f f e r e n tf i e l d s k e yw o r d s ：s t a t i s t i c a ll e a r n i n gt h e o r y ；s u p p o r tv e c t o rm a c h i n e ； t r a n s d u c t i v ei n f e r e n c e ；c a c h e ；p a i r w i s el a b e l i n gi nt h er a n g e 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 乏1 毛叼芬当事乏、菱互三乏砷伯气玲暮壳印 作者签名：塞! 堕日期：鲨2 年垦月2 _ 日 人连理i ：人学硕十学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 一量! 墨塑耋塑! 皇至坌：耋堑墨竺叠垒坠兰垫塑 日期：竺2 年堡月z _ 日 日期：4 年止月筚日 大连理工大学硕士学位论文 1 绪论 1 1论文的研究背景、意义和现状 机器学习研究从观测数据出发寻找规律，利用这些规律对未来数据或无法观测的数 据进行预测。其重要理论基础之一是统计学。统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ， 简称s e t ) 专门研究实际应用中有限样本情况的机器学习规律，并发展了支持向量机 ( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 这一新型通用的机器学习方法，由于它基于结构风 险最小化原理，而不是传统统计学的经验风险最小化，表现出了很多优于已有方法的性 能，迅速引起各领域的注意和研究兴趣，取得了大量的应用研究成果，推动了各领域的 发展【l 】。其实现方法大致有以下三种： ( 1 ) 经典统计预测方法 现有机器学习方法共同的重要理论基础之一是统计学。在这类方法中，模型中参数 的相关形式是已知的，训练样本来估计参数需要已知样本的分布形式，因此具有很大的 局限性。另外，传统的统计学研究的是样本数目趋于无穷大的渐进理论，但在实际问题 中，样本数量却是有限的，因此一些很优秀的学习方法在实际应用中可能表现不尽人意。 ( 2 ) 经验非线性方法 这一类方法利用己知样本建立非线性模型，克服了传统参数估计方法的困难，但往 往缺少统一的数学理论。 ( 3 ) 统计学习理论 和传统统计学相比，统计学习理论是一种专门研究小样本情况下机器学习规律的理 论。该理论针对小样本统计问题建立一套新的理论体系，不仅考虑了对渐进性能的要求， 并且追求在有限信息的条件下得到最优结果。v a p n i k 等人从2 0 世纪6 0 年代开始致力于 这方面的研究。到2 0 世纪9 0 年代中期，随着其理论的不断发展和成熟，也由于神经网 络等学习方法在理论上缺乏实质性的进展，统计学习理论开始受到越来越多的重视。 在统计学习理论的基础上发展了一种新的机器学习方法一支持向量机。该方法根 据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折中，以期获得最好的推广 能力。而且，只要定义不同的核函数，就可以实现其他现有的学习算法。因此，支持向 量机已经在众多领域取得了成功的应用。 目前，对支持向量机的研究已经成为国际学术的一个热点，在我国也开始大量的研 究学者致力于这方面的研究。尽管统计学习理论和支持向机的发展已经逐渐成熟，但仍 然有很多方面不够完善，比如：许多理论还只是理论上的意义；某些支持向量机的理论 支持向量机文本分类算法的研究及其应用 解释并非完美；核函数的选择大多依靠经验和样本的特性而没有理论依据；由于本身具 有较高的时间复杂度和空间复杂度而不适于处理大规模的样本；将二分类方法应用到多 类分类方法中等等，这些问题需要进一步的研究。 通过对现有研究成果和相关文献的归纳，可以得到如下结论，即目前对支持向量机 理论与应用的研究热点主要集中在以下几个方面【2 j ： ( 1 ) 现有支持向量机训练算法的改进与完善。 训练算法主要有三类：二次规划算法【3 】，分解算法，增量算法。另外，针对特定的 问题，很多研究者在这三类算法的基础上提出了很多改进算法，这些算法在特定问题的 解决中表现出了很好的效果。 s v m 可以归结为一个二次规划问题，二次规划是一种常见的优化问题，有一套比 较成熟的理论。从数学角度分析，s v m 是一个求条件极值问题，在二次规划中，条件 极值问题的通常解法有罚函数法和单纯形法1 4 j 。 分解算法的基本思想就是循环迭代：将原q p 问题分解成为一系列小的q p 子问题， 按照某种迭代策略，通过反复求解子问题，最终使结果收敛到原问题的最优解。根据子 问题的划分和迭代策略的不同，又可以大致分为三类：c o r t e s 和v a p n i k 提出的c h u n k i n g 算澍5 1 ，j o a c h i m s 提出的s v m l i 出旧和p l a t t 提出的s m o 7 l ( r 芋贯n 4 、化算法) 。 目前针对s m o 算法都提出了各种不同的改进方法，最近提出的一种的新的支持向 量机算法一挛生支持向量机【8 1 ，它通过建立两个支持向量的判断函数来进行分类，不仅 有了很快的分类速度，同时分类精度也得到提高；另外在s v m 分解方法的框架下提出 了一种快速s v m 训练算法。对大规模手写数字数据库的实验表明，所提出的算法较改 进的s m o 快约9 倍。结合主成分分析，对得到的数据训练l o 个一对多分类器所需的总 时间小于1 小时。同时，该快速s v m 算法在提高s v m 训练速度的同时并不牺牲泛化 性能。对m i n i s t 的错分率为0 6 。该方法为大规模数据集的训练提供了一个新的途径 【9 】 o ( 2 ) 针对大规模数据集的有效学习算法的研究 该类算法分析了增量学习过程中支持向量和非支持向量的转化情况。在此基础上提 出一种误分点回溯s v m 增量算法，该算法先找出新增样本中被误分的样本，然后在原 样本集寻找距误分点最近的样本作为训练集的一部分，重新构建分类器，这样能有效保 留样本的分类信息。实验结果表明：该算法比传统的支持向量机增量算法有更高的分类 精度。文献【胁1 4 】所提出各种不同的针对大规模数据集的有效学习算法，在训练精度影响 较少的情况下大大提高了分类速度。 大连理工大学硕士学位论文 ( 3 ) 多类支持向量机分类 通过组合多个二值分类器来实现对多类分类器的构造，常见的构造方法是“一对 一 、“一对多”两种。此外，近年来的改进算法有：纠错编码支持向量机1 1 5 1 ( e c o c s v m ) 、 有向无环图支持向量机【1 6 ( d a g s v m ) 等。层次支持向量机m s v m ) t 1 7 - 2 3 、同时也包括 s v m 与其他模式识别方法融合的多类s v m 2 4 2 5 】。 一对一算法的优点是：由于每个s v m 只考虑两类样本，故单个s v m 容易训练， 且其决策边界较一对多简单；另外，虽然它的复杂度以类数按平方增长，但就分类速度 来说，其并不比传统的一对多方法慢、而且其分类精度也较一对多高。 其缺点是：如果单个两类分类器不规范，则整个n 类分类器将趋向于过学习；并且 推广误差无界；其分类器的数目也会随类数急剧增加，然后导致在决策时速度很慢；另 外还存在误分、拒分区域。 一对多s v m 简单、有效训练时间较短。可用于大规模数据。但其缺点在于：当类 别数较大时，某一类的训练样本将大大少于其他类训练样本的总和，这种训练样本间的 不均衡将对精度产生影响；而且还存在误分、拒分区域；另外其泛化能力较“一对一 差。 e c o c ( e r r o rc o r r e c t i n go u t p u tc o d e s ) 是b o s e 和r a y c h a u d h u r i l 在19 6 0 年提出的 一种分布式输出码，1 9 9 5 年d i e t t e r i c h 和b a k i r i 提出用e c o c 解决多类模式识别问题。 e c o cs v m 的训练速度较一对多有明显改进，且当类别数比较大时仅需要少量的分类 器。然而如何根据具体问题确定码本、选择排列顺序以达到最优的分类性能依然有待研 究，且其分类效果受错误码的相关性影响很大，另外对类别超过1 0 的大类问题效果不 佳。 d a g s v m 是由p l a t t 提出的决策导向的循环图d r a g 导出的。是针对一对一s v m 存在误分、拒分现象提出的。d a g s v m s 简单易行，只需使用n 1 个决策函数即可得 出结果，较“一对一”方法提高了测试速度，而且不存在误分、拒分区域；另外，由于 其特殊的结构，故有一定的容错性。分类精度较一般的二叉树方法高。 层次支持向量机( - - 叉树支持向量机) 算法的改进是最近支持向量机学习算法的一个 热点。它的基本思想是首先将所有类别分成两个子类，再将子类划分个次级子类，如此 循环下去，直到得到一个单独的类别为止，这样就得到一个倒立的二叉分类树，其中两 个子类间的分类函数采用s v m 。而如何保证分类精度和提高分类速度是研究者们研究 的目标。 在多分类支持向量机结合其他模式识别方法也是一种目前的一种改进方法，有人提 出了一种基于f s v m 的雷达多目标识别方法，该法在最优超平面这一概念的基础上，根 支持向量机文本分类算法的研究及其应用 据该区域样本点的决策函数定义样本类别的模糊隶属度，并在此基础上，提出新的模糊 多类支撑矢量机，修正了决策函数，此法能够减少目标的错分和拒分数量，在识别率上 有了很大的提高【川，在此基础上提出了一种模糊多类支持向量机模型1 2 引。 ( 4 ) 支持向量机的应用 ， s v m 方法在理论上具有突出的优势，贝尔实验室率先对美国邮政手写数字库识别 研究方面应用了s v m 方法，取得了较大的成功。在随后的近几年内，有关s v m 的应 用研究得到了很多领域的学者的重视，在人脸检n t 2 6 1 、故障诊断 2 7 】、图像处理【2 8 。1 1 、及 其他应用研究 3 2 】等方面取得了大量的研究成果，从最初的简单模式输入的直接的s v m 方法研究，进入到多种方法取长补短的联合应用研究，对s v m 方法也有了很多改进。 由于s v m 的优越性，其应用研究目前开展已经相当广泛。陈光英等 3 3 j 设计并实现 了一种基于s v m 分类机的网络入侵检测系统它收集并计算除服务器端口之外t c p i p 的 流量特征，使用s v m 算法进行分类，从而识别出该连接的服务类型，通过与该连接服 务器端口所表明服务类型的比较，检测出异常的t c p 连接。实验结果表明，系统能够 有效地检测出异常t c p 连接。文献【3 4 】就采用了s v m 分类算法来进行经济上的风险分析， 以便做出合理的决策f 3 5 。 1 2 论文研究内容和全文组织结构 1 2 1 论文研究内容 自1 9 7 0 年以来，v a p n i k 等人一直致力于统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 的研究，他们针对传统模式识别存在的困难，提出了一种新的学习算法，即支持向量机 ( s u p p o r t v e c t o rm a c h i n e ，s v m ) 。由于s l t 和s v m 建立了一套较好的有限样本下机器学 习的理论框架和通用方法，既有严格的理论基础，又能较好地解决小样本、高维数和局部 极小点等实际问题，因此为智能模式识别与分类提供了一种新的有潜力的途径i l 3 6 | 。 虽然s l t 有比较坚实的理论基础和严格的理论分析，但是其从理论到应用还有很多 尚未得到充分研究和解决的问题【3 。川。例如，目前该领域的相关研究大多是试图设计某种 分类器，使其对未来所有可能样本的预期性能最优，而在很多实际问题中，没有可能也没有 必要用这样一个分类器对所有可能的样本进行识别，而往往只需要对一些特定的样本进 行识别。于是可以考虑设计这样一种更为经济的分类器，用它来建立一种直接从有标签样 本出发对特定的无标签样本进行识别和分类的方法和原则。相对于传统的归纳推理方式， 这种推理方式在文献【l 】中被称为直推式学 - - j ( t r a n s d u c t i v ei n f e r e n c e ) 。统计学习领域的直 推式学习是一个较新的研究领域，目前已经有了一些初步的研究成果1 3 m 引。 大连理工大学硕士学位论文 本文是对渐进直推式支持向量机学习算法( p r o g r e s s i v et r a n s d u c f i v es u p p o r tv e c t o r m a c h i n e ，p t s v m ) 的进一步研究，试图寻找一个比已有的方法学习过程更自然、不易出 错，消除死循环，并且纠错能力更强的p t s v m ，并将其应用在文本分类中。研究的主 要内容如下： ( 1 ) 介绍了自动文本分类技术的相关知识，然后对支持向量机在文本分类中的应用进 行了阐述和分析。 ( 2 ) 详细论述了统计学习领域的直推式学习的概念和核心思想，并将其与传统的归纳 推理方式作对比，分析了直推式学习的优缺点。 ( 3 ) 详细论述了直推式支持向量机学习算法概念和核心思想，并分析了其的优缺点。 ( 4 ) 详细论述了渐进直推式支持向量机学习算法的概念、核心思想和优缺点。 ( 5 ) 针对渐进直推式支持向量机的学习算法的缺陷，提出了一种改进的基于c a c h e 的 渐进直推式支持向量机学习算法i c p t s v m ，详细叙述了改进思想并给出了算法具体的 实现步骤。 ( 6 ) 通过u c i 的w i s c o n s i nb r e a s tc a n c e r 和c w h 0 3 a 的s v m g u i d e 3 两个数据集的实验， 给出了i c p t s v m 算法的实验结果并作了详细的分析。 ( 7 ) 将本文的算法应用在大连市公安局警务综合应用平台的全文检索系统中。 1 2 2 论文组织结构 论文各章节的安排如下： 第一章介绍了论文的研究背景、意义和现状，并给出了本文的主要研究内容和全 文组织结构。 第二章首先介绍了统计学习理论，然后介绍了支持向量机的基本原理和数学模型， 为新的支持向量机算法的研究做了理论准备。 第三章介绍了自动文本分类技术的相关知识，然后对支持向量机在文本分类中的 应用进行了阐述和分析。接下来对介绍了直推式学习、直推式支持向量机以及渐进直推 式支持向量机的概念和核心思想，并分别分析了它们的优缺点，通过针对渐进直推式支 持向量机的学习过程不自然、易出错、分类精度不高、算法性能不稳定以及存在死循环 等缺陷，提出了能弥补上述缺陷的一种改进的基于c a c h e 的渐进直推式支持向量机学习 算法( i c p t s v m ) ，并给出了算法的具体实现步骤，并通过实验验证算法的有效性。 第四章将i c p t s v m 算法应用在大连市公安局网络综合应用平台的全文检索系统， 并给出了项目的相关信息和具体实现。 支持向量机文本分类算法的研究及其应用 2 统计学习理论与支持向量机 支持向量机f 4 3 。4 6 1 是一种建立在统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，。s l t ) 基础 上的新的分类技术。它是基于结构风险最小化原则，根据有限样本信息在模型的复杂度 和学习能力之间寻求最佳的折衷，由于其出色的泛化性能，目前已广泛应用于模式识别 和回归分析等领域。 2 1 统计学习理论 传统的统计学研究的是样本数目趋于无穷大时的渐进理论，但实际问题中，样本的 数目往往是有限的。v a p n i k 从6 0 年代开始致力于有限样本统计理论的研究，称之为统 计学习理论，到9 0 年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习 方法在理论上缺乏实质性进展，该理论开始受到广泛的重视。统计学习理论指出经验风 险最小并不能保证期望风险最小；提出了结构风险最小化原理；给出了核心概念v c 维， 指出为了最小化期望风险必须同时最小化经验风险和v c 维；支持向量机就是基于这个 理论的一种模式识别的方法，支持向量机是统计学习理论最新的内容，也是最实用的部 分。 2 1 1 经验风险最小化 机器学习的目的就是根据给定的训练样本求出系统输入和输出之间的依赖关系。学 习问题可以一般地表示为：变量y 与x 之间存在未知依赖关系，即遵循某一未知的联合 概率分布f ( x ，少) 。机器学习问题就是根据，个独立同分布观测样本( 而，j ，。) ，( x ：，y ：) ， ( x ，y ，) ，在一组函数杪( x ，w ) ) 中，求一个最优的函数f ( x ，w o ) 对依赖关系进行估计，使 式( 2 1 ) 中期望风险r ( 们最小。 天( 川= l l ( y ，f ( x ，w ) ) a f ( x ，y ) ( 2 1 ) 其中，扩( x ，叻 称为预测函数集，w 为函数的广义参数。z ( y ，f ( x ，w ) ) 为用f ( x ，w ) 对 y 进行预测而造成的损失。 联合概率分布f ( x ，) ，) 通常未知，唯一能够获得的信息被包含在训练样本中，所以传 统的学习方法通常用经验风险r 一( w ) 最小化来代替期望风险最小化，这就是所谓的经 验风险最小化原则( e m p i r i c a lr i s km i n i m i z a t i o n ，e r m ) 。其中，经验风险r 一( w ) 定义如 下： 大连理工大学硕士学位论文 尺唧( w ) = i 1 三，m ，w ) ) ( 2 2 ) 实际上，经验风险只有在训练样本趋于无穷时才依概率收敛于期望风险，如图2 1 所示。 概率 样本数 图2 1 期望风险与经验风险的概率分布 f i g 2 1t h ep r o b a b i l i t yd i s t r i b u t i o no fe x p e c t a t i o nr i s ka n de m p i r i c a lr i s k 2 1 2 模型复杂度和推广能力 以神经网络为例，在早期的神经网络研究中，人们总是把注意力集中在如何使经验 风险最小，但很快发现，一味追求训练误差最小( 即经验风险最小) 并不总能达到好的 预测效果。实际情况是，只要学习机器足够复杂，训练时间足够长，则训练误差可以任 意减小。最极端的情况是，学习机器记住了所有的训练样本，则训练误差为零，但实际 上这种学习机器不具有推广能力。也就是说训练误差过小反而可能会导致推广能力下 降。关于机器复杂度与机器性能的关系，有如下一些结论： ( 1 ) 经验风险( 或者说训练误差) 对学习机器的性能有一定的影响，但不起决定作用。 执行经验风险最小化原则( 即最小化训练误差) ，并不总能提高学习机器的推广能力； ( 2 ) 复杂度高的学习机器，往往具有较低的经验风险。因此，经验风险最小化原则的 结果，将使学习机器变得越来越复杂； ( 3 ) 学习机器的复杂度对其性能有较大影响，推广性能好的学习机器应该具有与实际 面对的问题相对应的复杂度。 因此，如何根据实际问题，在学习机器的经验风险和模型复杂度之间取得合理的折 衷，从而使学习机器具有更高的推广能力，是一个非常重要的问题。 支持向量机文本分类算法的研究及其应用 2 1 3v c 维 定义2 1 ( n ( f ，z 。) ) ：设尸是一个假设集，即由在xc r ”上取值为一1 或1 的若干 函数组成的集合。记乙= 扛，x ：，x 。) 为x 中的m 个点组成的集合。考虑当厂取遍f 中 的所有可能的假设时产生的m 维i f i - j i ( f ( x 。) ，f ( x ：) ，f ( x 。) ) 。定义n ( f ，z m ) 为上述m 维向量中不同的向量的个数。 定义2 2 ( z 。被，打散) ：设f 是一个假设集，z 所= 伽。，x ：，x 。) 为x 中的m 个点 组成的集合。称z 。被f 打散，或f 打散z 。，如果n ( f ，z 。) = 2 ”。 定义2 3 ( v c 维) ：设假设集f 是一个由x 上取值为一1 或1 的函数组成的集合。定 义f 的v c 维为m a x mn ( f ，m ) = 2 ” 。 v c 维反映了函数集的学习能力。一般而言，v c 维越大，学习机器越复杂，学习内 容量就越大。目前没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数 集知道其v c 维。例如，在，z 维实数空间中，线性实函数的v c 维是厅+ 1 ，而 f ( x ，口) = s i n ( a x ) 的v c 维为无穷大。如何用理论和试验的方法计算其v c 维是当前统计 学习理论中一个待研究的问题。 2 1 4 结构风险最小化原理 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关 系，即泛化的界限。统计学 - - j 理论指出：经验风险r ( w ) 和实际风险r ( 川之间至少以 l 一叼的概率满足如下关系： r ( 叫r 唧( w ) + 地型竽幽 ( 2 3 ) yl 其中，是样本数，h 是函数集的v c 维。 这一结论表明，统计学习的实际风险由两部分组成：一个是经验风险，另外一个是 置信界限。置信界限反映了真实风险和经验风险差值的上确界，反映了结构复杂所带来 的风险，它和学习机器的v c 维h 及训练样本数，有关。在有限的训练样本下，学习机 器的复杂性越高，v c 维h 越高，则置信界限越大，就会导致真实风险和经验风险之间 可能的差别越大( 这里，如果v c 维无穷大时，该界限就不再成立) 。这样，学习机器 能力过强( v c 维很大) ，虽然能取得小的经验风险，但置信范围会很大；v c 维太小又会 导致大的经验风险。一个好的归纳原则必须在二者之间做出权衡。结构风险最小化原则 ( s t r u c t u r a lr i s km i n i m i z a t i o n , s r m ) 就是基于以上结论提出的一项新策略，和e r m 最小 大连理工大学硕士学位论文 化训练错误率( 即经验风险) 不同的是，s r m 不但要使经验风险最小化，还要使v c 维尽量小，即缩小置信范围，以此来使期望风险最小。 2 2 支持向量机基本原理 支持向量机是由v a p n i k 在统计学习理论基础上提出的一种新的分类算法，它基于 结构风险最小化原理，与传统机器学习方法相比，支持向量机具有小样本学习能力强、 模型泛化性能好等特性。 支持向量机的基本原理如下： 假设存在训练样本 ( x ，y ) ，f = 1 , 2 ，可以被某个超平面w x + b = 0 没有错误 地分开，其中，t r ”，y i 一1 ，1 ，z 为样本个数，r ”为n 维实数空间。则与两类样 本点距离最大的分类超平面称为最优超平面，如图2 2 所示，日即为最优超平面。其中 距最优超平面最近的异类向量( 鼠、- 2 上的点) 被称为支持向量( s u p p o r tv e c t o r ，s v ) 。 最优超平面将由离它最近的少数样本点( 即支持向量) 决定，而与其他样本无关。最优 超平面会获得最佳的泛化能力。 图2 2 最优超平面的概念 f i g 2 2t h ec o n c e p to fo p t i m a lh y p e r p l a n e 用如下形式描述与样本间隔为的分类超平面：w x + b 其中，= 1 y = 1 ， 若w x + b y = - 1 ，若w x + b - a v a p n i k 给出了一个关于一间隔分类超平面v c 维上界的定理：如果向量x 在一个 半径为r 的超球范围内，那么一间隔分类超平面集合的v c 维h 满足下面的界： 支持向量机文本分类算法的研究及其应用 厅? 嘲十一 ( 2 4 ) 这样，支持向量机首先保证了一个小的经验风险( 在训练样本可分时就是零) ，并 通过选择边缘最大的超平面的方式控制了函数集的v c 维。也就是说，使分类间隔最大 实际上就是对推广能力的控制，这就是支持向量机的核心思想之一。 2 3 支持向量机数学模型 首先将分类问题限制在简单的二类划分问题，支持向量机解决分类问题实际上就是 在样本空间中寻找最优超平面的问题。 2 3 1 线性可分支持向量机 将支持向量机最优化问题中的分类超平面归一化：令= 1 ，而w 和b 按比例缩放。 离超平面最近的样本( 支持向量) 满足： 若y = 1 ，贝0w x + b = 1 若y = 一1 ，贝0w x + b = 1 支持向量到超平面的距离为l l l 叫 。问题就转换成一个有约束的非线性规划问题： 咖吉 s t y f ( w 五+ 6 ) l ，f = 1 , 2 ，z ( 2 5 ) 称最优化问题( 2 5 ) 为原始优化问题。由于目标函数和约束条件都是凸的，根据最优 化理论，这个问题存在唯一全局最小解。其l a g r a n g e 函数为： 三= ow l l 2 + a ， 1 - y ，( w t + 6 ) 】 ( 2 6 ) 其中，a ，0 是约束y f ( w x f + b ) 1 的l a g r a n g e 乘子。 根据k k t 条件( k a r u s h k u h n t u c k e r ) 有： 考= w 一善i 口戊z ，= 。w = 喜口戊x ， c 2 7 ， 嚣= 喜哪，= 0 ( 2 8 ) 根据w o l f 对偶理论，将( 2 7 ) 、( 2 8 ) 两式代回式( 2 6 ) 中，经运算得到最优化问题( 2 5 ) 的w o l f 对偶问题： 大连理工大学硕士学位论文 掣地) 2 酗一圭弘叩 ，乃 旺口，y ，= 0 ， 口。0 ，i = 1 , 2 ，z ( 2 9 ) 求解最优化问题( 2 9 ) ，可确定最优超平面。若a 为最优化问题( 2 9 ) 的最优解，这 里a ，大部分是0 ，不是0 的口，。所对应的向量t ，即为支持向量，则w = a ；- y ，x ，为训 练样本向量的线性组合。而选用一个支持向量t 可以迸一步确定6 = y ，一w 薯。 最后，得到决策函数： ， 厂( x ) = s g n ( w x + b ) = s 盟( a ：i y ，x ，x + b ) 1 = 1 ( 2 1 0 ) 其中，s g n ( ) 为符号函数： 10t 0 ，称x ，为支持向量；如果口? = c ，称x ，为 边界支持向量；如果0 a ? 0 ，称薯为支持向量；如果口? = c ，称薯为 边界支持向量；如果0 a ：l c ，称x i 称为界内支持向量。从而得到决策函数： ， 厂( x ) = s g n ( z y ，a x ( x j ，x ) + 6 ) ( 2 2 5 ) ，- 1 支持向量机可以看作是一个3 层前向神经网络，其网络结构如图2 4 所示。 。 图2 4s v m 网络结构 f i g 2 4n e t w o r ks t r u c t u r eo fs v m k ( x 其中，x = ( x 1 ，x 2 ，x ”) 为输入变量，f ( x ) 为网络输出，其隐节点的个数即为支持 向量的个数。 支持向量机实现的就是包含一个隐层的多层感知器，隐层节点数是由算法自动确定 的，而且算法不存在困扰神经网络方法的局部极小点问题。 支持向量机文本分类算法的研究及其应用 3 基于支持向量机的文本分类技术 本章首先介绍了自动文本分类技术的相关知识，然后对支持向量机在文本分类中的 应用进行了阐述和分析。最后本人通过对渐进直推式支持向量机学习