（计算机应用技术专业论文）基于svm的中文文本分类算法研究与实现.pdf

摘要 网络信息的迅速增长，促进了文本自动分类研究的发展。在众多的分类算 法中，支持向量机由于其坚实的理论基础和良好的分类性能，受到了研究者们 的广泛关注。本文在研究支持向量机理论的基础上，对基于支持向量机的分类 算法进行了深入分析与探讨，并调整与改进了传统的基于支持向量机的中文文 本分类系统的结构，以更合理的方式实现了基于支持向量机的文本分类系统， 改进了基于二叉树的多类支持向量机文本分类算法。概括而言，本文在研究已 有支持向量机理论的基础上，主要作出了如下探讨： 传统的基于支持向量机的中文文本分类系统，主要包括训练模块和测试模 块。本文在实现分类系统时，对其结构作出了调整与改进，即将文本预处理作 为一个单独的模块，而将中文分词、特征提取、特征选择和文本向量表示等过 程集成到该模块中。并为训练文本和测试文本提供了共同的输入接口，而由预 处理系统根据不同情况输出训练文本特征向量和测试文本特征向量。这样，在 训练模块和分类模块中不必涉及到文本向量表示功能，有利于系统的开发与维 护，使得系统具有更好的性能。在分类函数的训练过程中，本文使用可行性方 向法对二次规划问题进行求解，并给出了求解后的算法描述。 将支持向量机从两类分类问题推广到多类分类问题，是一个研究热点。在 各种基于支持向量机的多类分类算法中，基于二叉树的多类支持向量机分类算 法训练和分类速度相对较快，且解决了不可分问题，是一种很好的方法。本文 系统研究和分析了基于二叉树的多类支持向量机分类算法，并在此基础上对其 作出了改进，即当测试文本集规模较大时，对其先聚类再分类。改进的目的是， 使测试文本不必总是从二叉树的根结点开始进行判断，而是有指导的代入分类 函数中计算。在测试文本集规模较大，分类函数个数较多时，可以很大程度上 增加分类效率，并加大了文本正确分类的概率。 关键词：文本分类，支持向量机，统计学习，二次规划 a b s t r a c t t h e r a p i dg r o w t ho fn e t w o r k i n f o r m a t i o np r o m o t e sa u t o m a t i ct e x tc a t e g o r i z a t i o n r e s e a r c ha n dd e v e l o p m e n t a m o n gc a t e g o r i z a t i o n a l g o r i t h m s ，t h es u p p o r tv e c t o r m a c h i n ea t t r a c t sm a n yr e s e a r c h e r s a t t e n t i o no na c c o u n to fi t ss o l i dt h e o r e t i c a l f o u n d a t i o na n dg o o dc a t e g o r i z a t i o np e r f o r m a n c e b ys t u d y i n go nb a s a lt h e o r yo f s u p p o r tv e c t o rm a c h i n e ，t h ed i s s e r t a t i o ni n - d e p t ha n a l y s e sa n dd i s c u s s e st h et e x t c a t e g o r i z a t i o nm e t h o db a s e do ns u p p o r tv e c t o rm a c h i n e ，a d j u s t sa n di m p r o v e st h e s t r u c t u r eo ft r a d i t i o n a lt e x tc a t e g o r i z a t i o ns y s t e mb a s e do ns u p p o r tv e c t o rm a c h i n e ， i m p l e m e n t st e x tc a t e g o r i z a t i o ns y s t e mb a s e do ns u p p o r tv e c t o rm a c h i n ei nam o r e r e a s o n a b l em a n n e r ，a n d i m p r o v e sb i n t r e em u l t i - c l a s st e x tc a t e g o r i z a t i o na l g o r i t h m s b a s e do ns u p p o r tv e c t o rm a c h i n e g e n e r a l l ys p e a k i n g ，o nt h eb a s i so fr e s e a r c h i n g t h e o r yo fs u p p o r tv e c t o rm a c h i n e ，t h ed i s s e r t a t i o nh a sd o n es o m ew o r ka sf o l l o w i n g ： t h et r a d i t i o n a lt e x tc a t e g o r i z a t i o ns y s t e mb a s e do ns u p p o r tv e c t o rm a c h i n em a i n i n c l u d e st r a i n i n ga n dt e s t i n gm o d u l e s w h e ni m p l e m e n t i n gc a t e g o r i z a t i o ns y s t e m ，t h e d i s s e r t a t i o n a d j u s t sa n di m p r o v e s i t ss t r u c t u r e ，m a k e st e x tp r e t r e a t m e n tb ea n i n d e p e n d e n tm o d u l e ，a n da d d sc h i n e s ew o r ds e g m e n t a t i o n ，f e a t u r ee x t r a c t i o n ，f e a t u r e s e l e c t i o na n dt e x tv e c t o rf o r m i n gi n t oi t i tp r o v i d e sac o m m o n l yt e x ti n p u ti n t e r f a c e t ot r i a n i n ga n dt e s t i n g ，b u tt h et e x tp r e t r e a t m e n ts y s t e mo u t p u t st r a i n i n go rt e s t i n gt e x t v e c t o rb yd i f f e r e n ti n s t a n c e t h u s ，t h et r a i n i n ga n dt e s t i n gm o d u l e sd on o th a v et o r e l a t et ot h et e x tf o r m i n g ，i t sc o n d u c i v ef o rt h ed e v e l o p m e n ta n dm a i n t e n a n c eo f s y s t e m ，w h i c hm a k e st h es y s t e mh a v eb e t t e rp e r f o r m a n c e i nt h ep r o c e s so ft r a i n i n g , t h ed i s s e r t a t i o ns o l v e st h eq u a d r a t i cp r o g r a m m i n gp r o b l e mb yt h em e t h o do ff e a s i b l e d i r e c t i o n s ，a n dg i v e st h ea l g o r i t h mf o rs o l v i n gd e s c r i b e d i t sah o t s p o tr e s e a r c ho ns u p p o r tv e c t o rm a c h i n et h a te x t e n d si tf r o mt w o - c l a s s i s s u e st o m u l t i c l a s s a m o n ga l l k i n d so fm o t h e d s ，b i n t r e em u l t i - c l a s st e x t c a t e g o r i z a t i o na l g o r i t h mb a s e do ns u p p o r tv e c t o rm a c h i n ei s m o r ee f f e c t i v et h e n o t h e r si nt r a i n i n ga n ds o r t i n g ，a n di tw o r k so u tt h ei m p a r t i b i l i t yp r o b l e m s oi ti sa g o o dm o t h e d t h ed i s s e r t a t i o ns y s t e m a t i c a l l y r e s e a r c h e sa n da n a l y s e sb i n t r e e m u l t i c l a s st e x tc a t e g o r i z a t i o na l g o r i t h mb a s e do ns u p p o r tv e c t o rm a c h i n e ，a n dt h e n i l i m p r o v e si to ns e v e r a la s p e c t s t h a ti s ，a s s e m b l e sf i r s t l y , a n dt h e ns o r t st h e mw h e n t h e s i z eo ft e s t i n gt e x t si st o ol a r g e t h ea i mo ft h ei m p r o v e m e n ti st om a k et h et e s t i n g t e x tb ec o m p u t e dm o r ea i m a b l e ，b u td o e sn o ta l w a y sb e g i nf r o mt h er o o tn o d eo f b i n t r e e i tc a ne n h a n c et h ee f f e c t i o no ft e x tc a t e g o r i z a t i o na n dm a k ei tb em o r e a c c u r a c yw h e nt h es i z eo ft e s t i n gt e x t si st o ol a r g ea n dt h eq u a n t i t yo ft y p ef u n c t i o ni s t o o m u c h k e yw o r d s ：t e x tc a t e g o r i z a t i o n ，s u p p o r tv e c t o rm a c h i n e ，s t a t i s t i c a ll e a r n i n g t h e o r y , q u a d r a t i cp r o g r a m m i n g i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：鱼造重日 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 武汉理l i 大学硕十学位论文 1 1 研究背景及意义 第1 章绪论 至2 0 世纪9 0 年代以来，计算机网络和数据库技术已逐步趋于成熟，为各 个领域中信息共享提供了有效的平台。丰富的信息，一方面给人们的生活带来 了前所未有的便捷，另一方面也提出了一些人们必须面对的问题：如何在大量 种类繁多的信息中有效的提取出所需的资料? 如何能让提取过程更精确、更高 效? 基于数据的机器学习( m a c h i n el e a r n i n g ) 方法，正是人们为了解决这样一 些问题而努力的成果之一，其基本思想是对已知数据进行研究分析，从中发现 规律，并利用它来对未知数据进行预测。 文本分类( t e x tc a t e g o r i z a t i o n ，简称t c ) 是机器学习理论的一个重要应用， 是获取信息的一个有效方法。从数学角度而言，它是一个映射过程，即将未知 类别的文本映射到已知的类别中。分类后，原本杂乱无章的文本被归入到确定 的类别中，使得人们查阅时有规可循。当文本数量很大时，文本分类的意义显 而易见。目前，有关文本分类的方法很多，常见的如贝叶斯网络、k 近邻法、决 策树、人工神经网络和支持向量机方法等。 支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 1 1 2 j 是一种源于统计学习理 论( s t a t i s t i c a ll e a r n i n g t h e o r y , 简称s l t ) 1 3 】的机器学习算法，它由a t b e l l 实验 室的v a p i n k 等人于2 0 世纪9 0 年代提出。传统的文本分类方法，只有当训练样 本数量无穷大时才能得到理想的分类效果，这种理想化的条件在现实中是无法 满足的。因此，其实际应用价值远远不如其理论研究价值。基于s v m 的文本分 类方法克服了这缺点，它建立在样本数量有限的基础之上，能在现有训练文 本包含的信息下得到最佳分类效果。同时，s v m 源于统计学习理论中的v c 维 理论和结构风险最小化( s t r u c t u r er i s km i n i m i z a t i o n ，简称s r m ) 原理1 4 j ，有效 地解决了其它机器学习算法中的过学习问题，即s v m 在数量有限的训练样本上， 由训练误差最小化可以确保测试误差最小化。其次，s v m 最终可以转化成为一 个非线性二次规划( q u a d r a t i cp r o g r a m m i n g ，简称q p ) 问题进行求解【5 j ，从理论 上说，得到的将是全局最优解，而非局部最优解。再次，在文本非线性可分的 武汉理l ：人学硕十学位论文 情况下，s v m 将原始输入空问中的文本向量，通过非线性变换映射到高维特征 空间中，并在特征空问中构造线性判别函数来对原输入文本进行分类。这正是 s v m 的魅力之所在，它在保证s v m 有较好的推广性能的同时，巧妙地解决了 维数灾难问题，使算法复杂度与样本特征向量维数无关。 s v m 的研究是从线性可分情况下的最优分类函数开始的，而当文本集非线 性可分时，只要使用适当的核函数将其映射到高维的特征空间中，便可迎刃而 解。由于s v m 理论的不断发展与完善，以及它在应用中表现出来的良好性能， 它已经成为机器学习理论中的研究热点之一，并在语音识别、手写体识别、人 脸检测和文本自动分类等1 6 】领域得到了很好的应用。尽管如此，在实际的应用中， 基于支持向量机的文本分类系统也有许多需要改进的地方。比如，s v m 算法的 训练过程，实际上是个非线性二次规划问题的寻优过程，为了得到理想的分 类效果，训练文本的数量往往较大，训练时间往往过长，如何提高训练效率是 一个有待改进的问题。又如，标准基于s v m 的文本分类算法，是用于解决两类 分类问题的，难以满足现实世界的需要，如何将其推广到多类分类应用中，也 需要人们作出更为深入的研究。还有关于分类噪音处理、核函数的选择等问题， 都需要作进一步的探讨。国外有关s v m 算法的研究起步较早，已取得了一定的 成就，而我国在此领域的研究工作才刚刚展开【7 l 。需要对s v m 进行深入的研究， 使其理论体系不断的发展与完善，以便建立更好的基于s v m 的分类系统，更好 的为人们服务。 1 2 国内外研究现状 对文本分类的研究，国外起步较早，2 0 世纪8 0 年代末已经取得了一些成果， 主要是基于人工构建的知识工程的文本分类系统，如路透社的c o n s t r u e 新闻自 动分类系统【8 j 等。但后来的研究与应用表明，基于知识工程的分类技术面临着严 峻的形势，比如其文法规则的规模越来越大，导致文法的维护无法进行并且处 理歧义的能力差。自2 0 世纪9 0 年代以来，随着计算机硬件性能的提升和网络 技术的发展，文本资源已相当丰富，且其数量急剧增加，使得文本分类技术越 来越受到人们的重视，促进了人们对文本分类系统的探索和研究。由于基于数 据的文本分类方法具有完整的理论体系，且在应用中表现出优良的分类性能， 所以它取代了基于知识工程的方法，在文本分类算法中占据了主导地位，成为 2 武汉理i ：入学硕卜学位论文 了如今的研究热点。 相对而言，我国在文本分类方面的研究起步较晚，并且由于中英文之间的 差异，使得基于英文文本的研究成果，在中文文本分类的应用上不尽人意。因 此，必须研究出适用于中文的文本分类理论。国内在文本表示、文本分类等方 面研究较多，如建立在n g r a m t y l 上的中文文本分类技术，摆脱了对词典和切词 处理的依赖，实现了文本分类的领域无关性和时间无关性i l 。 目前，国内外已有许多性能良好的文本分类算法，如k 近邻方法l l 、朴素 贝叶斯方法l l z j 和支持向量机方法等 1 )k 近邻算法：k 近邻算法( k n e a r e s tn e r g h b o r ，简称k n n ) 是由c o v e r 和h a r t 在1 9 6 8 年提出来的，它是一种传统的基于实例的文本分类方法，其特点 是设计简单易懂，性能良好，它的算法复杂度和文本数量成正比。其基本思想 是：首先通过某一公式计算待分类文本( 在本文中，称之为测试文本) 和训练 库中所有文本的相似程度，并对计算结果按一定规则进行排序，选取其中最相 似的k 篇文本，然后统计k 篇文本的类别数量，将测试文本归入到类别数最大 的那一类中。 在k n n 算法中，通常有两种相似度计算方法，即欧氏距离公式和余弦距离 公式， r 一 ( 1 ) 欧氏距离公式：d ( d 。，d ：) 一，( q 一岛) 2 ； ( 1 1 ) ( 2 ) 余弦距离公式：o ( d 。，d ：) = 罗丸叱 箭 ( 1 2 ) k n n 算法的不足之处是，每篇测试文本都必须与训练库中的所有文本进行相 似性计算，当训练库规模较大时，算法的计算量和存储量都十分庞大，算法效 率不高。因此，k n n 算法仅适用于训练库规模较小的情况。 2 ) 朴素贝叶斯算法：朴素贝叶斯( n a i v eb a y e s ) 分类算法假定，文本中某一 特征词对于某一类的影响独立于其它特征词，即假设文本向量特征词之间两两 独立，它以贝叶斯定理为基本理论，在已知先验概率和条件概率的情况下求得 相应的后验概率。使用n a i v eb a y e s 算法判断测试文本d 所属类别的基本过程为： 首先将文本d 表示成向量形式d = 池，d ，d 。) ，其中m 为向量的维数， 3 武汉理l ：犬学硕十学何论文 d 。= 矿( 心，d ) ，f = 1 ，2 ，m 表示特征词在文本d 中出现的频数。然后计算文本 d 属于类c i 的后验概率， p ( c f i d ) ；型粤掣 ( 1 3 ) p t a j 其中，ge c , c 为类别集合， p ( c f ) = 器为类别c i 的先验概率，p ( d l q ) 为文本d 属于类别q 的条件概率，p p ) 对所有类别均为常数，可以忽略，将p ( d ) 去掉后，得到 p ( ql d ) 一p ( d l q ) p ( c 1 ) ( 1 4 ) 最后针对所有的类别，取p ( ql d ) 为最大值的那个类即为测试类文本所属类别， 即 c ( d ) 一a r g m a x p ( c ) p ( di q ) 。 ( 1 5 ) 朴素贝叶斯算法的朴素性就体现在它对文本特征词两两独立的假设上，这 限制了该算法的适用范围。 3 ) 支持向量机分类算法：s v m 分类算法的主要思想是基于统计学习理论。 它通过机器学习过程确定一个分类函数( 也称为分类超平面) 厂o ) = s g n ( + 6 ) ( 1 6 ) 然后将测试文本代入f ( x ) 中判定文本所属类别。 s v m 算法是针对训练样本有限的情况提出的，建立在统计学习理论中的v c 维和结构风险最小化等理论之上。其重要特点是，在文本非线性可分的情况下， s v m 将原始输入空间中的文本向量，通过非线性变换映射到高维特征空间中， 并在特征空间中构造线性判别函数，实现文本分类。它通过非线性变换，将非 线性分类问题转化为线性分类问题，巧妙地解决了其它机器学习算法中的维数 灾难和过学习现象。其中，统计学习理论是针对有限样本情况提出的机器学习 方法，它主要包括学习一致性、泛化误差边界和结构风险最小化等理论。有限样 本，是统计学习理论的重要特点，也是支持向量机分类算法较其它分类算法优 良的一个关键因素。 s v m 算法由v a p n i k 在1 9 9 5 年提出，是统计学习理论的成功实现之一，标 志着它的成熟。由于s v m 良好的理论基础和在应用中的出色表现，使其成为机 器学习理论研究中的热点，主要包括s v m 算法的理论和应用研究。 目前，已经出现了不少关于s v m 算法的研究和改进方法。由于当训练文本 4 武汉理i ：大学硕十学何论文 集规模较大时，s v m 训练速度较慢，人们提出了选块算法( c h u n k i n g ) 、分解算 法( d e c o m p o s i n g ) 以及序列最小化算法( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ，简称 s m o ) 州等，它们的共同目的是将大规模问题转化成小规模的问题后逐一求解 由于在s v m 分类函数的构造过程中，只有支持向量起着决定性的作用，人们研 究了各种文本预处理方法，用于寻找在训练样本中仅占少部分的支持向量。针 对标准s v m 只能处理两类分类问题的情况，人们已经研究出o n e v s r e s t 、 o n e v s o n e 、d a g s v m 和二叉树多类分类方法和一次性求解多个分类函数【j 。 等，其中前面四种方法是将多类问题转化为多个二类分类问题，或将多个二类 分类器组合成一个多类分类器。另外，人们对非线性可分情况下s v m 的核函数 构造与选择问题也作了一些探索。 目前，s v m 的应用主要在模式识别领域，如语音识别、手写识别和文本分 类等。此外，s v m 在生物信息领域、回归分析和时间序列分析等问题上也得到 了较好的推广和应用，相对而言，s v m 在文本分类问题上的研究比较成熟。 1 3 本文的主要研究内容 本文的研究工作是建立在目前已有的理论和成果之上的，重点在于s v m 算 法的研究。同时根据课题需要，描述了必要的专门针对中文文本分类方面的关 键技术和文本聚类算法。具体而言，本文主要做了如下工作： ( 1 ) 由于s v m 是建立在统计学习理论之上的，为了深入的分析s v m 算法，必 须了解统计学习理论。本文从机器学习问题开始，系统、全面地研究了统 计学习理论，重点阐述了v c 维理论，泛化误差边界原理和结构风险最小 化原理，并对比性地描述了经验风险最小化原则，它是已往许多经典的分 类算法使用的原则。 ( 2 ) 基于s v m 的文本分类算法主要包括分类函数的训练和测试文本的分类两 个阶段，本文分别研究了基于s v m 的训练算法效率的提高和分类函数形 式的简化。 ( 3 ) 针对不同情况下的s v m 算法，详细讨论了其推导与求解过程。并全面描 述了可行性方向法，它可用于解决s v m 中涉及到的二次规划问题，并结 合可行性方向法给出了非线性可分问题的s v m 算法描述。 ( 4 ) 简要的介绍了中文文本分类技术，并基于s v m 算法，实现了中文文本分 5 武汉理f ：大学硕十学付论文 类系统。在系统的设计与实现中，本文对其结构进行了调整与改进，使得 系统的结构更加合理。 ( 5 ) 收集数据，对改进后的基于s v m 的中文文本分类系统进行了测试与验证， 并对实验结果与传统的基于s v m 的中文文本分类系统进行了比较分析。 ( 6 ) 研究了基于s v m 的多文本分类算法，重点阐述了一对多、一对一和基于 二叉树的多类s v m 分类算法。并对基于二叉树的多类s v m 分类算法作出 了深入的研究，在此基础上给出了改进方法，即当测试文本集规模较大时， 对其先聚类再分类。并分析了改进后算法的分类效率和分类精度。 ( 7 ) 由于在改进基于二叉树的多类s v m 分类算法的过程中，使用到了文本聚 类算法，本文对其作出了简要研究。 1 4 本文解决的关键问题 本文在对中文文本分类和支持向量机基本理论进行深入学习和研究的基础 上，主要解决了如下关键问题： ( 1 ) 使用可行性方向法求解s v m 训练算法中涉及到的二次规划问题。 ( 2 ) 在理论研究的基础上，设计并实现了基于s v m 的中文文本分类系统，并 从结构上对传统的系统进行了调整与改进。 ( 3 ) 对基于二叉树的多类s v m 分类算法作出了详细的描述，在此基础上对其 作出了改进，即当测试文本集规模较大时，对其先聚类再分类。 6 武汉理i ：人学硕+ 学位论文 第2 章s v m 基础理论研究 2 1 机器学习问题简述 机器学习【1 5 】是指，一个系统通过执行某种过程而改进它的性能，其目的是 通过对训练库中样本的学习，寻找系统输入与输出之间的潜在规律，从而指导 系统对测试样本作出尽可能准确的判断。机器学习的基本模型如下图所示【1 6 】， 图2 1 机器学习模型 本模型中，系统s 是研究的对象，它包含着输入x 和输出y 之间的潜在依赖 关系，它是未知的。在训练学习器l m 的过程中，输入x 与输出y 由训练样本 ( x ，y ) 提供，训练过程也就是一个由输入x 和输出y 求解学习器l m 的过程。学 习器l m 是对未知系统s 的模拟。在测试时，使用学习器l m 来预测输入x 的输 出y 。 机器学习假设输出y 和输入x 之间存在某种未知的依赖关系，即存在一个未 知的联合概率f o ，y ) ，然后根据咒个独立同分布的训练样本 ，y i ) ，i 一1 , 2 ，l ，r ”，y fe y ( 2 1 ) 在函数集 ，o ，缈) ) 中寻找一个最优的函数，o ，堆) ，使得期望风险 尺( ) = 弘( y ，厂0 ，w ) ) d f o ，) ，) ( 2 2 ) 最小，其中， ，( x ，) 】为预测函数集，0 9 为预测函数的广义参数，而l ( ) ，厂o ，) ) 为损失函数，既y = 厂伍，) 与y 之间的偏差。 最基本的三类机器学习问题是模式识别( 分类) 、函数逼近( 回归估计) 和 7 武汉理i + 人学硕十学位论文 概率密度i j 。对于模式识别问题，假设输出y 为 1 ，一1 ，损失函数定义为： 坳洲删= ；僦 3 ， 则期望风险尺( 甜) 表示学习器l m 和系统s 之间输出不同的概率，即分类错误的 概率。所以模式识别即分类问题的学习过程是指，在系统s 未知的情况下，通过 训练库寻找使得分类错误概率最小的函数的过程。 2 2 经验风险最小化原理 由( 2 2 ) 式可知，只有利用联合概率f ( x ，y ) 的信息，才能使得期望风险r ( t o ) 最小化，但在实际问题中f o ，y ) 是未知的，已知的仅有训练样本 ，y ；) 的信息， 因此尺( ) 无法直接计算和最小化。有鉴于此，人们利用大数定律的思想，使用 算术平均 1 三 ) 一二 ：( y ，厂“，) ) ( 2 4 ) 刀胃 来逼近( 2 2 ) 式中的期望风险，其中r 。( ) 为用训练数据( 既经验数据) 定义 的经验风险。使用经验风险。扫) 最小化来代替期望风险r ( t o ) 最小化，从而求 解分类函数参数，确定分类函数的方法，就是经验风险最小化( e m p i r i c a lr i s k m i n i m i z a t i o n ，简称e r m ) 原则。 已往许多经典的分类算法都是基于e r m 原则的，但使用经验风险最小代替 期望风险最小并没有可靠的理论依据。大数定理只能保证当训练库趋于无穷大 时，如， ) 在概率意义上趋近于r ( o ) ，并不能保证使( ) 最小的函数 ，o ，0 9 i ) 和使尺 ) 最小的函数f ( x ，术) 为同一函数，而且当训练样本数量有限时 e r m 原则不能保证分类函数有好的泛化性能，比如神经网络中的“过学习, , d a j 问 题。由于神经网络有很强的学习能力，甚至可以记住有限训练库中的每一个样 本，此时经验风险收敛至零，但由此而建立的分类函数无法保证对测试样本有 好的分类能力。出现过学习现象的原因一是因为训练库规模过小，二是因为学 习机器的设计不合理，可以归结为学习机器的复杂性和泛化能力之间的矛盾。 由于e r m 原则的局限性，需要找到一种在有限训练样本数量的情况下，建 立具有较高分类精度和较好的泛化能力的分类函数的理论。统计学习理论的发 展和完善使之成为了这一领域的最佳理论。 8 武汉理i 人学硕十学位论文 2 3 统计学习理论 与传统统计学相比，统计学习理论研究的是训练样本有限情况下的机器学 习问题，其主要内容包括函数集的v c 维理论，泛化误差的边界和结构风险最小 化原理及相关定理。 2 3 1 函数集的v c 维 v c 维( v a p i n kc h e r v o n e n k i sd i m e n s i o n ) 是统计学习理论中的一个重要概念， 它反映了函数集的学习能力，v c 维越大学习系统越复杂，容量越大。指示函数 集【厂0 ，) 的v c 维定义为1 1 9 ：对于一个指示函数集 厂o ，) ，若存在h 个样本 ( 五，咒) ) ，f = 1 , 2 ，h 能被 ， ，) ) 里的函数按所有可能的2 6 种形式分开，则称 厂 ，) ，能将h 个样本打散。指示函数集 厂0 ，) 的v c 维就是它能打散的最大 样本数目。如果函数集能将h 个样本打散，而不能将h + k ，k ；1 ，2 ，个样本集打 散，则其v c 维是h ；如果函数集能将任意个样本打散，则其v c 维是无穷大。 例如二维平面上的线性函数集 厂o ) ，( 其中厂o ) = a x + 6a , b e r ) 可以将平 面上的3 个点以所有可能的2 3 = 8 种形式分为两类，则其v c 维是3 ，如图2 2 所示1 2 0 1 ( 其中和表示两种不同类别) 。 图2 2 线性函数集v c 维分析示意图 l i 如今还没有关于任意函数集的v c 维的通用计算方法，需要在统计学理论的 研究中得到进一步完善。 9 ， ， 夕 ， 必 、 、 武汉理i ：人学硕十学位论文 2 3 2 泛化误差的边界 统计学习理论从函数集的v c 维出发，系统地研究了经验风险和期望风险之 间的关系，即泛化误差的边界弘。v a p n i k 在2 0 世纪7 0 年代指出，对于指示函 数集中的所有函数，其经验风险如。( ) 和期望风险尺( ) 之间至少以1 一刁满足如 下的关系： 尺( ) sr 。( ) + h o n ( 2 n h ) + 1 ) - l n ( r i 4 ) ( 2 5 ) i ， 其中，h 为函数集的v c 维，n 是训练库中的样本数量。在上式中，右边第二项 称为置信范围( c o n f i d e n ti n t e r v a l ) ，它和函数集的v c 维h 及训练库容量，l 有关， 可以将其表示为： 西( 聆) ；h ( 1 n ( 2 n h ) + 1 ) - i n ( r 4 ) ( 2 6 ) 。 vn 于是( 2 5 ) 式可表示为： 尺( ) sr 。砌( 甜) + 垂( j i l i n ) ( 2 7 ) 上式从理论上说明了函数集的实际风险由两部分组成：一是经验风险( ) ( 即 训练误差) ，二是置信范围。在训练库中样本有限的情况下，函数集的v c 维h ( 复 杂性) 越高置信范围越大，则期望风险r ( ) 和经验风险如。( ) 之间的差别越大。 它从本质上解释了出现过学习现象的原因：当出现过学习的现象时，指示函数 集v c 维较高，虽然此时经验风险也。( ) 几乎趋近于零，但期望风险r ( ) 并没 有达到最小，从而导致函数集的泛化能力很差。( 2 7 ) 式表明，在指示函数集的 训练过程中，为了取得较小的期望风险，不仅要使经验风险最小化，而且要使 指示函数集的v c 维达到最小，以缩小置信范围。指示函数集的期望风险越小， 则其泛化能力越强，即根据训练库信息对测试样本的判断越准确。 2 3 3 结构风险最小化原理 指示函数集的泛化误差边界表明，要使期望风险最小必须同时让经验风险 和置信范围取得最小值，即当经验风险最小时，设法控制函数集的v c 维。事实 上，在传统的机器学习方法中，学习模型的选择过程就是一个针对训练库调整 置信范围的过程，当学习模型适合于训练库中样本时，学习模型可以取得很好 的效果。但这种方法只能凭借经验知识，有很强的技巧性。 统计学习理论中的结构风险最小化( s t r u c t u r er i s km i n i m i z a t i o n ，简称s r m ) 1 0 武汉理l ：人7 硕十学位论文 理论指出：把函数集s = ， ，) ) 分解为一个函数子集序列， 下的结构形式： s 。cs2 c cs , c cs ；s = u s i 使各个子集按v c 维的大d , l l l 页序排列， 该子集序列具有如 ( 2 8 ) j i l lsh 2s sh is h ( 2 9 ) 其中，h i 为函数集s 的v c 维。针对每个子集，其置信范围一定，在其中寻找经 验风险最小的函数，通常情况下，经验风险的最小值随着子集的v c 维增加而减 少。对于不同的子集，选择最小经验风险与置信范围之和最小的集合，即可得 到使期望风险取得最小值的函数子集。结构风险最小化的示意图如图2 3 所示 【2 2 】 图2 3结构风险最小化原理示意图 结构风险最小化原理在指示函数集的泛化能力和其复杂性的矛盾之间选择 了一个平衡点，随着函数子集的v c 维增加，经验风险的最小值不断减少，但其 置信范围却越来越大，结构风险最小化原理充分考虑这种变化，在函数子集中 选择经验风险与置信范围之和最小的集合，使得最小化经验风险得到了实际的 最好边界，从而取得最小化的期望风险。 武汉理f ：人。硕十学位论文 2 4s v m 算法研究 2 4 1s v m 算法概述 支持向量机算法的研究起源于对数据分类问题的处理，是统计学习理论的 一种实现方法，它建立在统计学习理论的v c 维和结构风险最小化原理等基础理 论之上，是专门针对训练库样本有限的情况而设计的。传统的分类算法都要求 训练样本的数量足够多，甚至只有当训练样本的数量趋于无穷大时，算法才有 较高的精确性。但在实际应用中，训练样本数量通常是有限的。s v m 方法对于 样本数量没有过高的要求，可以在样本数量有限时得到最优解。事实上，s v m 算法的训练过程，最终可以转化为一个二次规划问题的求解过程，从理论上说 得到的将是全局最优解。标准s v m 分类算法的主要思想是：利用训练库，通过 文本向量表示和求解二次规划问题等一系列运算，得到最优分类函数( 最优分 类超平面) ，然后将测试文本转化成特征向量后代入分类函数，根据计算出来的 值确定文本类别。最优分类函数是指，分类函数不但要将两种类别的文体正确 分开( 训练错误率为o ) ，而且要使两类之间的间隔最大的分类函数。如图2 4 所示，分别用和代表两类样本，实线为分类函数，两条虚线分别为各类中过 离分类函数最近的样本点，且平行于分类函数的平面，它们之间的距离即为分 类间隔。 图2 4s v m 分类示意图 s v m 的研究是从文本线性可分的情况开始的，然而，现实中大多数类别的 文本并非相互隔离，它们之间总有交界甚至彼此掺杂。s v m 通过非线性函数， 1 2 武汉理1 ：人颂 学位论文 把低维空间中非线性可分的文本映射到高维的特征空间中，将其转化为线性可 分的问题，然后在特征空问中构造最优分类函数( 最优化分类超平面) 对文体 进行分类。在将文本特征向量从原始空i 、u j 映射到特征空间的过程中，空间维数 急巨增加，使得直接在特征空间中计算最优分类函数难度变大，甚至无法进行。 通过引入核函数( k e r n e lf u n c t i o n ) k ( 薯，x f ) = m ( t 冲( x f ) ，s v m 只需要在特征 空间中进行向量的内积运算，而不必知道非线性函数西的具体形式，从而巧妙 地避免了维灾难问题。 标准的s v m 分类算法研究的是两类分类问题，它通过寻找分类函数 厂( x ) = s g n ( + 6 ) ( 2 1 0 ) 来判定测试文体x 的类别，其中s g n 为符号函数，当厂伍) 乏0 时，x 属于某一已 知正类别，当f ( x ) 0 ，iq 苎l ( x 似 一面l 置x ( 七+ 1 ) 一石( + a d ( 并置k = k + 1 ，转( 2 ) 。 算法3 1 可行性方向算法 本文使用该算法来求解s v m 中涉及的二次规划问题。 1 8 ) ) ) ) 1 2 3 4 ( ( ( ( 武汉理i ：人学硕卜学伊论文 3 2s v m 算法的求解 3 2 1 标准s v m 算法描述与求解 标准的s v m 分类算法有线性可分、近似线性可分和非线性可分三种类型。 在不同的情况下，应该使用合适的支持向量机形式，才能使分类问题变得简单 而有效。因为三种情况下算法的步骤基本相似，在此本文仅列出使用情况最广 的非线性可分问题的s v m 算法描述f 2 9 , 3 0 】： 已知动i i 练库t r = _ 【“，y ；) i x ；e r ”，y i y ，i = 1 ，2 ，1 ) ，y 一 一1 ，1 ) ； 选择适当的核函数k ( x ，五) ，构造二次规划问题 m a x 。， ) 5 善n 西一专著荟z 口j y i y j k ( x i ，) 旺西咒= o 口? 芝0 ，i = 1 ，2 ，咒 求解二次规划问题，得到解口= ( 口：，a ：，口：) r ； 选择a + 中任一分量口；o 代入式6 = y j 一) ，；c q 。k