（计算机软件与理论专业论文）中文文本分类方法研究.pdf

山东师范大学硕士学位论文 中文文本分类方法研究 摘要 随着互联网的迅速普及和发展、在线信息浚源的因益增多，人们已经从信息资源匮乏的时 代过渡到了信息资源极为丰富的数字化时代。面对海量的在线信息资源，人们很难迅速有效的 找到真正所需要的信息。因此，如何合理地和有效地组织和管理这些信息，已经逐渐成为信息 。处理领域中一个十分重要的研究课题。传统地，我们是依靠人工的方法对网页进行分类的，即 专业人员在分析网页的内容后，将它分到一个或若干个比较合适的类别中。很明显，随着网页 信息容量的快速增长，仍然依靠入工的方式来进彳亍网页分类将会耗费大量的入力和物力，这是 非常不现实的。由于文本分类是组织和管理信息的有力手段，它可以在较大程度上解决目前网 上信息杂乱无章的现象，使得用户更容易更准确地定位所需要的信息。因此，对文本的分类是 必要的，也是必需的。这就使得对文本舞动分类的研究成为了一个日益重要的研究领域，并且 它还逐步与搜索引擎、信息过滤等技术相结合，成为解决人们霹上信息获取的重要手段。 本文首先介绍了中文文本分类的关键技术。文本预处理是影响文本分类精度的关键因素之 一。为此，在这一部分我们首先介绍了中文文本的预处理技术，其中包括中文分词技术和停用 词处理；然后介绍了文本的表示方法，即向量空间模型；最后，对各种特征选择算法进行了分 析对比。 然后，本文针对文本分类的核心部分分类算法，进行研究。我们选择近几年发展起来 的新型的通用机器学习方法一支持向量枫，来进行分类。在这部分，首先给缀了支持向量机 的基本原理，包括线性可分、非线性可分、支持向量机的实现思想和常用的核函数。此外，给 出了支持向量机的训练算法，并分析了支持向量机的多类分类问题。 本文的创新点主要体现在：提出了基于离散粒子群优化算法和决策树的s v m 多类分类方 法。传统d a g s v m 和d t - s v m 方法的优点是决策速度比“一对一 和“一对多”快，提高 了训练和分类的效率。但共同的缺点是只要类别数固定，其决策树结构就是固定的，不能根据 具体约分类问题作窭盘适应的调整。各个两分类s v m 在决策树中的位置不同，其分类性能往 往也会不同，越接近根节点的位置出现错分，其“误差积累 现象越严重。传统的d a g s v m 和d t - s v m 方法均没有考虑如何最优地安排各个两分类s v m 的位置问题，即没有考虑每个决 策节点上的决策优化阀题。因此，我们提出了基于离教粒子群优化算法和决策树的s v m 多类 分类方法。引入离散p s o 优化，以类间分类间隔最大为准则，在每个决策节点上将多类训练 山东师范大学硕士学位论文 样本划分为两类进行训练，使两个子类间的可分性尽可能强，以构造合理的树结构，最终生成 最优或近优的决策树。通过实验表明，改进的分类算法提高了文本的分类精度。 关键词：文本分类；支持向量机；粒子群算法 分类号：t p 3 1 1 山东师范大举硕士学位论文 s t u d yo fc h i n e s et e x 量c l a s s i f i c a t i o nm e t h o d - a b s t r a c t w i t ht h er a p i dp o p u l a r i t ya n dd e v e l o p m e n to fi n t e r a c t t h eo n l i n ci n f o r m a t i o nr e s o u r c e sh a s b e e ni n c r e a s e dd a yb yd a y p e o p l eh a v et r a n s i tf r o mt h ep e r i o dw h i c hh a sb e e nl a c ko fi n f o r m a t i o n r e s o u r c e st ot h ed i g i t a la g et h a tt h ei n f o r m a t i o ni se x t r e m e l yr i c h f a c i n gt h ea b u n d a n to n l i n c i n f o r m a t i o nr e s o u r c e s ，i ti sd i f f i c u l tf o rp e o p l et of i n dt h ea c t u a ln e e d e di n f o r m a t i o nq u i c k l ya n d e f f e c t i v e l y t h e r e f o r e ，h o wt oo r g a n i z ea n dm a n a g et h eo n l i n ei n f o r m a t i o nr e a s o n a b l ya n de f f e c t i v e l y h a v eb e c o m eav e r yi m p o r t a n ti s s u ei nt h ei n f o r m a t i o nd e a l i n gf i e l d 。t r a d i t i o n a l l y , w e bp a g e c l a s s i f i c a t i o nh a sr e l i e do nm a n u a lm e t h o d s o b v i o u s l y , w i t ht h er a p i dg r o w t ho ft h ew e bp a g e i n f o r m a t i o nc a p a c i t y , w e bp a g ec l a s s i f i c a t i o nw i l lc o n s u m eal o to fm a n u a la n dm a t e r i a lr e s o u r c e s 。i t i su n r e a l i s t i ct h a tw es t i l ld c a l 诵t ht h ei n f o r m a t i o nm a n u a l l y t h eo n l i n ei n f o r m a t i o ni sd i s o r d e r e d a n du n s y s t e m a t i ct oag r e a t e re x t e n t t e x tc l a s s i f i c a t i o ni sap o w e r f u lm e a n so ft h eo r g a n i z a t i o na n d m a n a g e m e n to ft h ei n f o r m a t i o n i tc a l ls e t t l et h ep h e n o m e n o n i ti se a s i e rf o rc o n s u m e r st os e a r c ht h e i n f o r m a t i o nn e e d e d s ot h ec l a s s i f i c a t i o no ft h ew e bp a g ei se s s e n t i a la n dn e c e s s a r y i tb e c o m e sa n i m p o r t a n tm e a n sf o rp e o p l et os c a l et h eo n l i n ei n f o r m a t i o nw h i c hc a nc o m b i n eg r a d u a l l yw i t hs e a r c h e n g i n et e c h n i q u ea n di n f o r m a t i o nf i l t e r i n gt e c h n i q u ea n ds oo n f i r s t l y , t h i sp a p e ri n t r o d u c e s 氆ek e yt c c h n o l o g i e so f 凭ec h i n e s et e x tc l a s s i f i c a t i o n 。巍赋 p r e - p r o c e s s i n gi st h eo n eo ft h ek e yf a c t o r st h a tc a ni n f l u e n c et h ea c c u r a c yo ft e x tc l a s s i f i c a t i o n t o t h i se n d , w ea n a l y z et h ec h i n e s et e x tp r c - p r o c e s s i n gt e c h n i q u ef i r s t l yi nt h i sp a r t ，i n c l u d i n gc h i n e s e w o r ds e g m e n t a t i o na n dt h eh a n d l i n go fs t o pw o r d s t h e n w ei n t r o d u c e st h ev e c t o rs p a c em o d e la sa t e x te x p r e s s i o nm o d e l a tl a s t 。w eg i v et h ec o m p a r i s o no ft h ef e a t u r es e l e c t i o na l g o r i t h m s s e c o n d l y , t h i sp a p e rs t u d i e st h ec l a s s i f i c a t i o na l g o r i t h mt h a ti st h ec o r eo ft h et e ：x tc l a s s i f i c a t i o n an e wt y p eo fg e n e r a lm a c h i n el e a r n i n gm e t h o d ( s u p p o r tv e c t o rm a c h i n e ) w h i c hd e v e l o p e di n r e c e n ty e a r si ss e l e c t e dt oc l a s s i f y i nt h i sp a r t ，t h eb a s i cp r i n c i p l e so fs u p p o r tv e c t o rm a c h i n ei sg i v e n f i r s t i n c l u d i n gl i n c a r l ys e p a r a t i o n n o n l i n e a rs e p a r a t i o n ，s u p p o r tv e c t o rm a c h i n ea n dk e r n e lf u n c t i o n w h i c hi sc o n s t a n t l yu s e d 。i na d d i t i o n ，t r a i n i n ga l g o f i t h mo fs u p p o r tv e c t o rm a c h i n ea n dt h ep r o b l e m o fm u l t i c l a s s i f i c a t i o no fs u p p o r tv e c t o rm a c h i n ea r ea l s om e n t i o n e d t h ec o n t r i b u t i o no f t h et h e s i si sa sf o l l o w s ： a i m p r o v e dc l a s s i f i c a t i o na l g o r i t h mi sp r o p o s e dw h i c hi sb a s e do nd i s c r e t ep a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h ma n dd e c i s i o nt r e em e t h o d t h em e r i to f t r a d i t i o n a ld a g s v ma n dd t - s v m m e t h o d si st h a tt h es p e e do fd e c i s i o n m a k i n gi sf a s t e rs i g n i f i c a n t l yt h a n o n e - t o o n e ”a n d ”o n e t o - m a n y ”。h o w c v e lac o m m o nd r a w b a c ki st h a tt h ed e c i s i o nt r e es t r u c t u r ei sf i x e da sl o n ga s t h en u m b e ro ff i x e dc a t e g o r i e s i tc a l l tm a k et h ea d a p t i v ea d j u s t m e n ti na c c o r d a n c ew i t ht h es p e c i f i c c l a s s i f i c a t i o np r o b l e m s 。t h ec l a s s i f i c a t i o np e r f o r m a n c ei so f t e nd i f f e r e n tw h e ns v mi si nd i f f e r e n t p o s i t i o n so ft h ed e c i s i o nt r e e e r r o ra c c u m u l a t i o ni sv e r ys e r i o u sw h e nt h em i s m a t c hh a p p e ni n a p p r o a c ht ot h er o o tn o d e h o w e v e r , t r a d i t i o n a ld a g s v ma n dd t - s v mm e t h o d sd on o tc o n s i d e r h o wt oa r r a n g et h el o c a t i o no fs v 蠢莲。t h e yd o n tc o n s i d e rt h ed e c i s i o no p t i m i z a t i o np r o b l e m t h e r e f o r e ，ai m p r o v e dc l a s s i f i c a t i o na l g o r i t h mi sp r o p o s e dw h i c hi sb a s e do nd i s c r e t ep a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h ma n dd e c i s i o nt 炮em e t h o di nl i g h to ft h ew e a k n e s so ft h ep r e s e n t c l a s s i f i c a t i o na l g o r i t h m w ei n t r o d u c et h ep a r t i c l es w a r mo p t i m i z a t i o ni ne a c hn o d eo fd e c i s i o nt r e e i no r d e rt og e n e r a t et h eo p t i m a ld e c i s i o nt r e e t h ee x p e r i m e n t ss h o wt h a tt h ei m p r o v e dc l a s s i f i c a t i o n i 1 1 山东师范人学硕士学位论文 a l g o r i t h mh a se n h a n c e dt h ec l a s s i f i c a t i o np e r f o r m a n c ea c c u r a c yo ft h ep r e s e n ta l g o r i t h m 。o 。o o o o o o o o o o o o o o o o o o o o o o o o 。o 。o o o o o o o o o o o o o o o o o o o o o o o 。o o o o o o o _ - _ _ - _ _ _ _ - _ _ _ _ o _ o _ _ _ _ _ _ _ _ - - _ _ _ _ _ _ _ _ _ o - _ _ o - _ - - _ _ _ o _ _ _ _ o _ _ _ _ _ _ _ _ _ - 一 k e yw o r d s ：t e x tc l a s s i f i c a t i o n ；s u p p o r tv e c t o rm a c h i n e ；p a r t i c l es w a r mo p t i m i z a t i o n c l a s s i f i c a t i o n ：t p 31 1 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其它人已经发表或撰写 过的研究成果，也不包含为获得( 注：如没有其它需要特别声明的，本栏 可空) 或其它教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：荔拓 导师签字： 学位论文版权使用授权书 本学位论文作者完全了解兰墩有关保留、使用学位论文的规定，有权保留并向国家有 关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权兰墩可以将学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：馨彦钐 导师签字： 签字日期2 。叩年箩月肜日 签字目期2 0 。绎j 月泸 山东师范大学硕士学位论文 1 1 研究背景和意义 第一章绪论 随着互联网的迅速普及和发展、在线信息资源的日益增多，人们已经从信息资源匮乏的时 代过渡到了信息资源极为丰富的数字优时代。面对海量的在线信息资源，人们很难迅速有效的 找到真正所需要的信息。因此，如何合理地和有效地组织和管理这些信息，已经逐渐成为信息 处理领域中一个十分重要的研究课题。传统地，我们是依靠人工的方法对网页进行分类的，即 专业人员在分析网页的内容后，将它分到一个或若干个比较合适的类别中。很明显，随着网页 信息容量的快速增长，仍然依靠人工的方式来进行网页分类将会耗费大量的人力和物力，这是 非常不现实的。由于文本分类是组织和管理信息的有力手段，它可以在较大程度上解决目前网 上信息杂乱无章的现象，使得用户更容易更准确地定位所需要的信息。因此，对文本的分类是 必要的，也是必需的。这就使褥对文本自动分类的研究成为了一个日益重要的研究领域，并且 它还逐步与搜索引擎、信息过滤等技术相结合，成为解决人们网上信息获取的重要手段。 1 2 国内外研究的历史与现状 按照人们解决文本分类闻题的切入点的不同，文本分类可分为基于自然语言理解的文本分 类和基于统计数学的文本分类。当然在实际应用中使用的方法大都是这两种方法的结合。文本 分类的处理对象是文本，而文本是以自然语言的形式出现的，因此，试图把文本分类建立在自 然语言理解的基础之上是很自然的事情。然而事实并非如此，由于自然语言的复杂性，想把自 然语言中的切规则用知识的形式表示出来几乎不可能，这条途径事实上是相当困难的。因此， 一方面，人们继续跟随着自然语言处理技术的发展，试图建立更为理想的基子知识库的分类系 统；另一方面，人们另辟蹊径开拓了一条新的文本分类的途径，邸把文本分类建立在统计数学 的基础之上，用统计的方法从文本的字频、词频等相关元素中提取文本的特征，再建立相应的 数学模型以实现分类。 国外对文本分类的研究始于2 0 世纪5 0 年代末，h 。p l u t m 首先将词频统计思想焉于文本分 类，在该领域进行了开创性的研究。1 9 6 0 年，m a r o n 在j o u r n a lo f a s m 上发表了有关自动分类 的第一篇论文r e l e v a n c e ，p r o b a b i l i s t i ci n d e x i n ga n di n f o r m a t i o nr e t r i e v a l ) ) ，其后许多学者在这 一领域进行了卓有成效的研究工律。 从2 0 世纪6 0 年代直到2 0 世纪8 0 年代末，这期间最有效的文本分类系统一直是由专家人 山东师范大学硕士学位论文 工构建的基于知识工程技术的分类系统。其典型应用就是卡内基集团为路透社开发的c o n s t r u e 系统【l 】，它主要是由专业人员编写了一些分类规则来指导分类，在路透社的部分语料库上它的 效果非常好，平均准确率和召回率大约都可达到9 0 ，但是在其他的应用领域采用c o n s t r u e 系 统将会消耗大量的人力和物力。这种自动分类器构造方法的缺点是知识获取瓶颈的存在。它必 须要为领域专家获取的知识和知识工程师的知识表示之间架起桥梁，二者缺一不可，如果这种 分类器被转到完全不同的领域，工作必须得重新开始。9 0 年代初期，基于机器学习的分类技术 开始取代基于知识工程的方法成为文本分类的主流技术。这种算法通过归纳文本集的特征自动 创建一个分类器，这些文本集合事先被领域专家人工地分类到类集的各个类中，分类器可作为 一个规则决定文本是否属于类。如果类集c 被更新，或者系统要应用于其他不同的领域，只需 要重新构造一个人工分类文本集合，通过机器学习，自动地构造一个分类器。显然由于这种分 类方法不再需要知识工程师和领域专家的介入，节约了大量的人力和物力，同时也加快了分类 系统的建立速度。 近年来，研究者们针对机器学习的技术进行了大胆的探讨，提出了多种分类模型和分类算 法，如基于向量空间模型的r o c c h i o 分类算法【2 1 及其一系列的改进算法、k 近邻算法( k n n ) 3 - 6 l 、 决策树( d e c i s i o nt r e e ) 【6 1 、朴素贝叶斯( n a i v eb a y e s ) 【7 1 、神经网络( n e u r a ln e t w o r k ) 【8 1 、支持向量 机( s u p p o r tv e c t o rm a c h i n e ) 9 - 1 0 1 等等。这些方法在英文以及欧洲语种文本分类上有着广泛的应 用，均取得了不错的效果。国外很多研究人员对英文文本分类领域的各个问题都有相当深入的 研究，对几种流行的方法进行了大量的对比分析。此外，还有一些研究表明采用组合分类器的 方式能够提高分类的精度。 目前，国外的分类系统己经从最初的可行性研究经历了试验性研究进入了实用化阶段。并 在邮件分类、电子会议、信息过滤等方面得到了较为广泛的应用。1 9 9 4 年，a t & t 实验室的d a v i d d l e w i s 等人对基于非确定性的分类技术做了研究。两年后，该实验室将分类的技术应用到了 电子邮件领域。1 9 9 7 年，德国d o r t m u n d 大学计算机系的t o r s t e nj o a c h i m s 等人研究了基于向量 空间模型的自动分类系统。同年，美国s t a n f o r d 大学计算机系的d a p h n ek o l e 得人提出了基于 很少语料词汇的层次自动分类方法。1 9 9 8 年，美国c a r n e g i em e l t o n 大学计算机系的y i m i n g y a n g 等人将聚类算法应用于在线自动分类。1 9 9 9 年，美国j u s t r e s e a r c h 公司的a n d r e wm c c a l u m 等 人运用信息嫡理论、b a y e s 理论等实现了多类号的自动分类。随后，美国m a s s a c h u s e t t s 大学 计算机系专门针对文本库开发了自动分类系统，美国i b m 和o r a c l e 公司为推广电子商务而研制 了基于文本内容的电子邮件自动分类系统，m i c r o s o f t 公司也为其浏览器开发了基于内容属性分 类的插件。 自从文本分类的概念在国内出现以来，该项技术在国内得到了长足的发展。然而和国外的 2 山豕帅范大掌坝士学位论文 发展状况相比，我们的水平仍相对滞磊。一方面由于国内起步较晚，另一方面则由予霞蠹的工 作主要是针对中文文本。由于汉语有许多不同于英语的特点，使得中文文本分类的难度更大。 比如，汉语的书面形式是连续书写的，词与词之间没有自然的界限，在进行文本分类之前，首 先要对文本进行分词。另外，在不同的语言的研究工作中，句法分析和语义分析所占的比倒是 不同的。在英语中，句法分析比语义分析的比例要大，丽汉语是一种分析型语畜，语义分析在 汉语研究中起着举足轻重的作用，其所占的比例比句法分析要大得多。这使得在中文文本分类 中，通过句法分析等基于语法的手段把握文本的内容变得更加困难。就发展历史而言，国内的 文本分类的发展经历了三个阶段：图外研究成果引进阶段、分类技术完善阶段以及面向汉语分类 技术的发展阶段；而就发展方向来看，则有基于外延的分类方法和基于概念的分类方法之分。 中国科学院、清华大学、上海交通大学、复旦大学、南京大学、一些大学的著名学者在该领域 做出了一些研究成果，研制_ 出一批基于词典法和基于专家系统的分类系统。由于中文与英文存 在较大的差异，不能照搬国外的研究成果，中文文本分类的研究基本上是在英文文本分类的研 究策略上，结合中文文本的特点，继而形成中文文本分类研究体系。 1 3 论文结构 本文的各章节具体安排如下： 第一章：引言。阐述课题的研究背景和意义以及国内外研究的历史与现状和章节安排。 第二章：中文文本分类的关键技术。首先分析了文本预处理技术，包括中文分谲技术和停 用词处理；其次介绍了文本表示方法，即向量空间模型；最后，对各种特征选择算法进行了分 析对比。 第三章：基于离散粒子群优化算法和决策树的s v m 多类分类方法。首先介绍了匿前常用 的分类算法；然后重点介绍支持向量机的原理和训练算法。最后根据支持向量机存在的问题， 提出了基于离散粒子群算法和决策树的s v m 多类分类方法。通过实验证明该方法提高了文本 的分类耩度。 第四章：系统设计与实验。分别对特征选择方法、核函数以及分类器做了对比实验。 第五章：论文总结。对全文的研究工作进行了总结和展望。 3 山东师范大学硕士学位论文 2 。1 文本预处理 第二章中文文本分类的关键技术 文本预处理主要是放文本中提取关键词来表示文本的处理过程。在预处理过程中，首先要 对文本进行分词处理，将连续的语句分隔为分散的有独立意义的词集，然后去除集合中的停用 词，获得文本的关键词集合。文本预处理是影响文本分类准确度的关键因素之一。 2 1 1 中文分词 在中文文本预处理过程中，一般可以选择字、词或词组作为文本的特征项。根据实验结果， 普遍认为选取词作为特征项要优予字和词组，这是因为字所代表的信息量太少，而且存在很多 多义字，字与字之闻的赛限模糊，而且用字作为特征项将导致特征向量庞大，学习分类器时容 易造成特征空间的维灾难；词组虽然携带足够的信息量，但词组在文本中出现的机率不多，用 词组作为特征项会导致特征向量稀少，损失很多重要信息。因此，为了提取中文词条，需要对 中文文本进行较隽复杂的分词，称为中文分词。分词目的是将连续的字序列按照一定的规范重 新组合成词序列的过程。目前的分词算法一般分为以下三类： ( 1 ) 机械分词 机械分词指的是依据词典，按一定的策略将汉字审与词典中的词逐一匹配，如果涎配成功， 就加以切分。按照优先匹配的词长和扫描方向的不同，有四种常见方案，即正向最大匹配、正 向最小匹配、逆向最大匹配和逆向最小匹配。 机械分词方法简单，易于实现。但是由予自然语言丰富的表达方式，汉语句法构成的复杂 性，新词汇的不断涌现，使得机械分词法面临着很多问题。如：一词多义问题、歧义切分闻题 和未登录词识别问题，仅用机械分词方法都不能够很好地解决，这些问题直接影响了分词的准 确率。 ( 2 ) 基于理解的分词 通常的分析系统，都力图在分词阶段消除所有歧义切分现象。而有些系统则在后续过程中 来处理歧义切分问题，其分词过程只是整个语言理解过程的一小部分。其基本思想就是在分词 的同时进行句法、语义分析，剩用句法信息和语义信息来处理歧义现象。它通常包括三个部分： 分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、 句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词 方法需要使用大量的语言知识和信息。壶于汉语语言知识的笼统、复杂性，难以将各种语言信 气 山东师范大学硕：b 学位论文 息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。 ( 3 ) 基于统计的分词 这种分词方法利用了一种基于统计学的n g r a m 技术，根据相邻字的共现频率自动提取特 征，使文本数据分类实现了分类的领域无关性和时间无关性。它无需任何词典支持，对输入文 本所需的先验知识少。但是，在进行n g r a m 信息提取时，会产生非常大的数据冗余，时间代 价较大，相比基于词典分词获取文本特征的方法，其实现效率比较低。实际应用的统计分词系 统都要使用一部基本的分词词典( 常用词词典) 进行串匹配分词，同时使用统计方法识别一些新 的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用 了无词典分词结合上下文识别生词、自动消除歧义的优点。 本文采用基于词典和统计相结合的分词方法。我们将正向最大匹配方法和逆向最大匹配方 法结合起来构成双向匹配法。并且将词典中的词按它们在文本中的出现频度的大小排列，高频 度的单词排在前，频度低的单词排在后，从而提高匹配的速度。 2 1 2 停用词处理 一篇文本的内容主要通过名词、动词、形容词等实词来体现，虚词以及在各种文本里经常 出现的部分高频词对分类并无意义，这些无意义的字或词即被称为停用词。通常意义上的停用 词大致有如下两类： ( 1 ) 这些词应用广泛，但就是因为它随处可见，在所有类中都频繁出现，使得它不含有不同 于其它词的特性，因此没有区分类别的能力。比如“互联网 一词几乎在每个网站上均会出现， 这样的词无法保证能够给出真正相关的分类信息，反而还会降低分类的效率： ( 2 ) 包括语气助词、副词、介词、连接词等一些虚词，通常自身并无实际意义，和类别信息 没有关联，如常见的“的”、“在”。适当地减少文本处理中虚词出现的频率，可以有效地提 高关键词密度，更突出实词的分类信息。 为了节省存储空间，提高分类效率，将停用词从文本词集中剔除掉，使其不参与分类，从 而减少分类噪音。去停用词的方法是构建停用词表依次对分词得到的文本词集中的词与停用词 表进行匹配，如果词存在于表中，表明该词为停用词，则从文本词集中删除；若不在表中，则 保留。 停用词表的来源有人工构造和基于统计的自动学习两种方式。人工构造是根据主观判断选 择词集或针对某一应用选择领域词来构成停用词表；基于统计的自动学习方法是基于词频构建 停用词表，或者从初步的分词结果中得到停用词，然后在分词过程中不断更新频率并根据切分 结果进行验证；此外还可以依据词语和句子的联合熵构建停用词表。基于统计的停用词表的构 6 山东师范大学硕士学位论文 建应焉较为广泛，方法很多，如蹶益军等人提出了用词条在语料库中各个句子内发生的概率和 包含该词条的句子在语料库中的概率计算它们的联合熵，依据联合熵选取停用词。美国德克萨 斯大学达拉斯分校的f e n gz o u 等人提出了一种基于统计与信息论模型的中文停用词抽取方法。 2 2 文本表示 文本是由大量字符构成的字符串，它属于一种非结构化的数据，无法被学习算法直接用于 训练或分类。用简单而准确的方法将文本表示成计算机所能够处理的形式是进行文本分类的基 础。最经典的文本形式化表示方法是商量空闻模型( v e c t o rs p a c em o d e l ，简称v s m ) ，它将文 本表示为特征项和特征项权重组成的向量。此钋还有布尔模型和概率模型等文本表示方法。 2 。2 向量空间模型 现在各种分类算法中文本的表示普遍采用向量空间模型旧，它是文档表示的一个统计模型， 以特征项作为文档表示的基本单位，特征项可以是字：词或短语。对给定的文本 d = d t ，m ；f 2 ，w 2 ；f 。，w n ，t k 为一特征项，愀为特征项t k 所对应的权值。为了简化计算，不考 虑特征词的出现顺序和相互关系，规定每个改互异，则每一个文档可表示为特征空间的一个向量 ( 磁，) ，其中为第f 个特征项的权重。特征项的权重计算有多种方法，如矿坍诉目前 采用比较广泛的是鳓法，特征项癌文档d 中的权值为： w ( t ，露) = 辩，蠢) 谳 ( 2 1 ) 其中，矿( # ，矗) 为特征项旌该文档蠢中出现的频率，砑为其逆文档频率，它们有多种计算方 法，常用的计算公式为： w ( t ，i ) 裟矿( ，荔) 1 。g 拦0 0 1 ) n i ( 2 2 ) 其中表示训练集中的全部文本数，n i 表示含有特征项t 的文本数。如果考虑到文本长度的 影响，可| 以将权值归化为： t f ( t ，孑) 1 0 9 ( n + o 。o i ) 川，动= 产。：垒二：一 d 排动地鲁旭哆 ( 2 _ 3 ) 7 山东师范大学硕士学位论文 2 。2 。2 文本相似度计算 在向量空间模型中，两个文本d ，和如之间的内容相关度即为文本相似度， 用s i m ( d j r ，d 2 ) 来表示。相似度计算有各种距离、向量内积、夹角余弦等多种不同的方法及变 形，常鬟酌度量公式有： ( 1 ) 欧几里德躐离，简称欧式距离，麴公式( 2 4 ) 掰示： ，r 一 s i m ( d _ l ，如) = d e ( d l ，如) = 、x 互信息法与翦二者相比，在准确度上有些差距。 期望交叉熵法的改进效果不明显。 文档频度法是最简单而成本最低的方法，其效果比相关信息增益法要好得多。 术语强度法与文档频度法效果相当。 须得指出的是上述结论并不是绝对的，由于文本的种类多种多样，文本使用的自然语种也 有较大差别因此各种方法比较雩导出的结论可能会略有差别，但是此结论对我们在本项冒的实现 中挑选特征选取算法具有很好的指导意义。 2 。5 潜在语义索引 经常使用的特征选择的评价方法( 如上节所述的方法) 有一个共圆特点就是假定词之阆是 互相独立、正交的。通过计算词项和类别之间存在的某种特定关系对词进行筛选，从而达到降 维的目的。 事实上，尤其对于中文文本丽言，文本中词条的共现情况和内在的语义结构也是重要的信 息。潜在语义索引( l a t e n ts e m a n t i ci n d e x ) 就是一韩根据词条的共现信息探查词条之间内在语义 联系的方法2 。通过对文档矩阵进行特殊的矩阵分解，将矩阵近似地映射到一个k 维潜在语义 空间上。其中，k 为选择的最大的奇异值个数，映射之后的奇异值向量能最大限度的反映出词 条和文档之间的依存关系。潜在语义空阆实际上是把同现的词条映射到同一维空间上，丽非同 1 1 山乐帅范大学倾士学位论文 现的词条映射到不同的空闻上，这样使得潜在语义空间相比原来的空闯维数要小的多，实际上 也达到了降维的目的。经过这样的映射之后，原来不包含或包含很少相同词条信息的文档之间 也可能因为词条的共现关系而有较大的相似度。我们采用数学中经典的奇异值分解方法实现潜 在语义索引，选择这一方法的好处是分解的效果较好，且具备较强的扩展性能 凋。 奇异僮分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ) 是将调条一文档矩阵分解必3 个矩阵的乘积形式， 即，s 珑黼： 4 蚶= s 嬲( 坟黼) 7 ( 2 一1 6 ) 其中，t y 0 原特征空间的维数，d 为文档数，n m i n ( t ，国，硼_ d 都是正交矩阵。s 是一个对 角矩阵，对角线的值为从大到小排列的非负实数。实际上s 的对角线上的值为彳确的特征值，第 f 个特征值表示在第i 个投影轴上的偏差。只取矩阵f ，s ，d 的前露列，得到矩阵砰。玉& 确f ，d d 。惫j f 。 得到的么降维震的矩阵： 特征空间从f 维降为雠。 b = s 七。露d 触醇r( 2 1 7 ) 在文本分类中，存在训练文本集合扩展的问题，如果没有较好的扩展性，每次扩充训练语 料集都要重新进行一次奇异值分解这显然是难以接受的。实际上，在语料库扩震或语料库过大 的情况下，可以只对其中的一部分文档作矩阵奇异值分解，而对后续的文档通过前面的计算结 果进行转换，这是由以下公式推导得出的： a = t s d7 t r a = t7 t s d7 t r a = s d 7 佗1 8 ) 对每个新的文档向量曰，g 在降维后的空间中表示为tt x kt q 。这样可以扩充更多的训练 文本向量。而在未知文本的自动分类过程中，同样需要对经过特征表示的新文本进行相同的空 间映射，使用和扩溪训练文本相同的方法生成在新空间中的商量，从露使薪文本在和训练文本 在相同的特征空间中得到表示。 1 2 山东师范大学硕士学位论文 第三章基于离散粒子群优化算法和决策树的s v m 多类分类方法 3 。1 常用的分类算法 在文本分类领域中常用的有以下几种分类算法： l 、简单向量距离法 该方法根据算术平均值对训练集中的每类生成一个代表该类的中心向量，在新文本来到时， 确定新文本的向量表示，计算待分类的文本向量与每类中心向量间的距离( 相似度) ，最后将文 本判定给与文本距离最近的类，相似度的计算采取两向量的夹角余弦，公式如下： 一 w t k x w j k 一r s 珑d f ，_ = c 。s d f ，巧2 了霉蒌震k = i l 嚣亏丽 。 。3 一。， 其中，d z 为待分类的文档，巧可为类q 的类中心向量，w 腿与眦分别为两个向量中的第尼 维，拜为向量的维数。 2 、k n n 算法 k n n ( k - 最近邻) 分类算法也是基于向量间相似度的分类方法。它的算法思想是：对于个 待分类文本z ，系统在训练集中找到髟个与之距离最近的邻居，使用这k 个邻居的类别为该文本 的候选类别。该文本与阶邻居之间的相似度按类别分别求和，减去一个预先设定的闽值，就得 到该文档的类别测度。 y ( g 一，q ) = s 锄( z 乏) y ( 砬，) 一b j d r u i d | 其中：z 为一个待分类文本的向量表示，一d i 为训练集中的一个样本文本的向量表示，0 为 _ 给定的类别；y ( d z , c j ) 。，l ( 当幺属于0 时取l ；当不属于0 时取。) ，易为预先设定的类别0 的最优阙值；葶i m ( z ，) 为待分类文本与实例之间的裰似度，壶公式( 3 。3 ) 计算得至l 。 e o s _ 罂 lz | | dl ( 3 3 ) k n n 算法没有离线学习过程，分类器的训练在新样本分类前进行，所需要的时间开销较大。 1 3 山东师范大学硕士学位论文 3 、决策树( d e c i s i o nt r e e ) 算法 决策树算法通过对训练数据的学习，总结出一般化的规则，然后再利用这些规则解决问题。 其对文档分类时，先用训练集为预先定义的每一个类构造一棵决策树，构造方法如下： ( 1 ) 以训练集作为树的根结点，它表示所有的训练文档，将它标记为“未被检测 。 ( 2 ) 找到一个标记为“未被检测”的叶结点，如果它表示的所有文档都属于这个类，或者都 不属于这个类，将这个叶结点的标记改为“已被检测”，然后直接跳到第三步；否则，挑选当前 最能区分这个结点表示的文档集中属于这个类的文档和不属于这个类的文档的特征项作为这个 结点的属性值，然后以这个结点为父结点，增添两个新的叶结点，都标记为“未被检测，父结 点表示的训练文档集中含有这个特征项的所有文档用左子结点表示，所有不含有这个特征项的 文档用右子结点表示。 ( 3 ) 重复第二步操作，直到所有的叶结点都被检测过。对每棵决策树，从它的根结点开始， 判断结点的属性值( 特征项) 是否在待分类的文档中出现，如果出现，则沿着左子树向下走；否 则沿着右子树向下，再继续判断当前结点的属性值是否在待分类的文档中出现，直到到达决策 树的某个叶结点，如果这个叶结