（管理科学与工程专业论文）基于RSSVM的中文文本分类研究.pdf

内容摘要 随着通信技术和计算机技术的飞速发展，信息处理已经成为人们获取信息和知识不可 或缺的工具。文本分类是信息处理的重要研究方向，它是指在既定的分类体系下，根据文 本的内容自动判别文本类别的过程。 粗糙集理论是一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法。 它在不影响分类精度的前提下通过信息约简，去掉冗余信息，得到显式的文本分类规则， 简化信息的表达空间维度。支持向量机是一种基于统计学习理论的方法，它遵照结构最小 化原则，在统计样本较少的情况下获得良好的统计规律和泛化能力，为解决小样本学习问 题提供一个框架，但是由于庞大的文本特征维数，支持向量机的性能也经常会受到限制。 因此本文采用了一种粗糙集和支持向量机相结合的文本分类方法，即利用粗糙集属性约简 减少属性数，然后用支持向量机进行训练，再利用训练得出的分类知识对新文本进行分类， 通过两者有机的融合增强了它们在文本分类中的实用性。 本文沿着“文本分类理论粗糙集理论支持向量机理论专基于r s - s v m 分类方法的提 出专将r s - s v m 分类方法应用到文本分类中”的思路对文本分类研究内容进行了介绍。在 仿真过程中，提出了改进的j o h n s o n 贪婪算法，通过查全率和查准率的比较，表明改进的 r s - s v m 具有较好的分类精度。针对语料库的不同类别样本集的数量差异问题，本文对语料 库进行了再分类，使得分类结果更加准确有效。结果表明，基于r s - s v m 。的方法在中文文 本分类上具有一定的优越性。 关键词：文本分类粗糙集支持向量机属性约简 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ec o m m u n i c a t i o nt e c h n o l o g ya n dc o m p u t e rt e c h n o l o g y , i n f o r m a t i o nh a sb e c o m ea l l i n d i s p e n s a b l et o o l f o rp e o p l et o a c q u i r e i n f o r m a t i o na n d k n o w l e d g e t e x tc a t e g o r i z a t i o ni st h ei m p o r t a n tr e s e a r c hf i e l do fi n f o r m a t i o np r o c e s s i n g ，i ti st h e p r o c e s so fa u t o m a t i c a l l yd e t e r m i n i n gt h ec a t e g o r i z a t i o no fs o m et e x ta c c o r d i n gt ot h ec o n t e n to f t h et e x t ，w h i c hi su n d e rt h ee s t a b l i s h e dc a t e g o r i z a t i o ns y s t e m r o u g hs e t ( r s ) t h e o r yi sat h e o r e t i c a lm e t h o dw h i c hi sa p p l i e dt os t u d yt h ee x p r e s s i o n ， l e a r n i n ga n di n d u c i n go fi n c o m p l e t ea n du n c e r t a i nd a t a u n d e rt h ep r e m i s eo fn o ti n f l u e n c i n gt h e a c c u r a c yo ft e x tc a t e g o r i z a t i o n ，i t c a nc a n c e lt h er e d u n d a n ti n f o r m a t i o n ，g e t o b v i o u s l y c a t e g o r i z a t i o nr u l e s ，a n dr e d u c et h ek n o w l e d g ee x p r e s s i o ns p a c e s u p p o r tv e c t o rm a c h i n e ( s v m ) i sap o w e r f u lm a c h i n el e a r n i n gm e t h o db a s e do ns t a t i s t i c a ll e a r n i n gt h e o r y , i to b s e r v e st h e p r i n c i p l e o fs t n i c t u r a lr i s km i n i m i z a t i o n ，a n dc a nh a v e g o o ds t a t i s t i c a lr e g u l a t i o n a n d g e n e r a l i z a t i o np e r f o r m a n c eu n d e rt h es i t u a t i o no fs m a l ls a m p l e s ，p r o v i d e saf r a m e w o r kt os o l v e t h el e a r n i n gp r o b l e m sc h a r a c t e r i z e db ys m a l ls a m p l e s ，b u ti t sp e r f o r m a n c ei so f t e nw e a k e n e d b e c a u s et h ev e c t o ro ft e x ti sv e r yh u g e s ot h i st h e s i sc o m b i n e st h er o u g hs e ta n dt h es v m ， r e f i n e st h en u m b e ro fp r o p e r t i e sb yu s i n gt h ea t t r i b u t er e d u c t i o nt h e o r yo fr s ，t h e nt e x ti st r a i n e d b ys v m ，t h en e wt e x ti sc l a s s i f i e db yu s i n gt h ec a t e g o r i z a t i o nk n o w l e d g eg e t t i n gf r o mt h e t r a i n i n gr e s u l t t h ea b i l i t yo ft h et w om e t h o d su s e di nt e x tc a t e g o r z a t i o ni si m p r o v e dg r e a t l yb y c o m b i n i n gt h e mp e r f e c t l y t h i st h e s i si sa l o n gt h et h i n k i n go f t e x tc a t e g o r i z a t i o nt e c h n i q u e - - ) r o u g hs e tt h e o r y - - ) s u p p o r tv e c t o rm a c h i n et h e o r y 专t h ec o m b i n a t i o nm e t h o do fr sa n ds v m t h ea p p l i c a t i o n o fr s s v mm e t h o di nt e x tc a t e g o r i z a t i o n t oi n t r o d u c et h ea c h i e v e m e n tc o n c l u d e di nt e x t c a t e g o r i z a t i o ns t u d y i nt h es i m u l a t i o np r o c e s s ，t h et h e s i sg i v e sa ni m p r o v e dj o h n s o ng r e e d y a l g o r i t h m t h r o u g ht h ec o m p a r i s o no fr e c a l la n dp r e c i s i o n ，t h ei m p r o v e dr s s v mh a sh i g h e r c a t e g o r i z a t i o na c c u r a c y t a r g e t e df o rt h ed i f f e r e n c e si nt h en u m b e ro fs a m p l et h a tb e l o n g st o d i f f e r e n tc o r p u s ，t h i st h e s i sp r o c e s s e st h ec o r p u sw i t har e c a t e g o r i z a t i o nt oi m p r o v et h e c a t e g o r i z a t i o nr e s u l t t h er e s u l t ss h o w e dt h a tt h em e t h o db a s e do nr s s v mh a ss i g n i f i c a n t s u p e r i o r i t yi nc h i n e s et e x tc a t e g o r i z a t i o n k e yw o r d s ：t e x tc a t e g o r i z a t i o n ，r o u g hs e t ，s v m ， a t t r i b u t er e d u c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他人己经发表或撰写过的研究成果，也不包含为获得天津财经大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者虢月循 签字魄2 p 产邢日 学位论文版权使用授权书 本学位论文作者完全了解天津财经大学有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权天津财经大学可以将学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文， ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：腑 签字目其i j ：2 p 少年厂月歹e t 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 答字日期：1 年厂肜f 日 电话： 邮编： 第1 章绪论 本章的主要内容包括：指出了本文的研究背景；介绍了本课题国内外的研究状况；简 要介绍了本文所用文本分类的算法，即粗糙集和支持向量机相结合的文本分类方法；阐述 了本文所做的主要工作。 1 1 研究背景及意义 文本分类( t e x tc l a s s i f i c a t i o n ) 最初是应信息检索( i n f o r m a t i o nr e t r i e v a l ，简称 i r ) 系统的要求出现的。面对庞大而且急剧膨胀的信息海洋，如何有效地组织和管理这些 信息，并快速、准确、全面地从中找到用户所需要的信息是当前信息科学和技术领域面临 的一大挑战。因此，对文本信息进行组织分类，从而简化用户检索时对文本的存取和操作 已经成为适应当代信息迅猛发展的迫切要求，所以，对文本分类的研究和应用开始逐渐兴 起。 文本分类主要是用获取的规则来对文本进行标引和分类，它作为知识的组织工具，最 初被应用到文献分类、图书馆分类、公文和专利的分类等领域。自动分类技术的出现为模 式识别( p a t t e nr e c o g n i t i o n ) 和机器学习( m a c h i n el e a r n i n g ) 提供了研究与应用的新领 域，使得文本分类得到了越来越广泛的应用，如大型网络检索系统、文档管理、数字图书 馆中的文本归类系统、信息过滤系统等，这些系统已广泛应用到了生活的方方面面，为人 们提供了便捷的知识组织和获取途径。因此，对文本分类的研究具有重要的实用价值。 文本自动分类技术的研究目标就是实现文本分类的自动化，现已广泛应用于信息检索 信息过滤文本数据库数字化图书馆等领域，国外关于英文的文本分类技术己经研究的比较 成熟，出现了很多文本分类的软件，而国内关于中文文本分类的研究由于起步较晚，相关 技术有待进一步提高，随着中文环境下的用户数目的爆炸式增长，中文信息越来越丰富， 使中文信息处理愈加成为需要迫切解决的问题。中文在构词成句上比英文复杂的多，理论 上技术上也还不成熟，但是中文是世界上使用人数最多的语言，而且随着信息时代的到来 和知识经济的全球化，中文信息急剧增加，中文信息的利用率越来越大，其作用已经变得 举足轻重。因此，对简单高效实用的中文文本分类进行分类和研究，提高中文文本自动分 j o a c h i m st t e x tc a t e g o r i z a t i o nw i t hs u p p o r tv e c t o rm a c h i n e s ：l e a r n i n gw i t hm a n yr e l e v a n t f e a t u r e s j m a c h i n el e a r n i n g ，1 9 9 8 ：1 3 7 1 4 2 v a nl e e u w e nj a p p r o a c h e si nm a c h i n e1 e a r n i n g m a l g o r i t h m si na m b i e n ti n t e l l i g e n c e ，2 0 0 4 ：1 5 1 - 1 6 6 l 类的效率已经成为促进我国经济发展和国际知识交流的迫切要求，具有重要的现实意义。 1 2 国内外研究状况 分类( c l a s s i f i c a t i o n ) 是数据挖掘中一项非常重要的任务，应用广泛。分类是一个从 现有的带有类别标签的数据集中寻找同一类别数据的共同特性，并以此将它们进行区分的 过程。分类的目的是学会一个分类函数或分类器，该函数能把数据源中的数据项映射到给 定类别中的某一个。分类可用于预测，其目的是从历史数据记录中自动推导出对给定数据 的推广描述，从而能对未来数据进行预测。用于分类问题的方法可以分为两类：符号主义 方法和连接主义方法。 文本自动分类始于5 0 年代末。当时美国i b m 公司的h p l u h n 首次在自动分类领域进 行了开创性的研究，他的主要思想是将词频统计用于分类。6 0 年代初，m a r o n 在j o u m a lo f a s m 上发表了有关自动分类的第一篇论文“o nr 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 d i n f o r m a t i o nr e t r i e v a l ，提出了关键词自动分类技术。不久，h b o r k o 等人提出利用因 子分析法进行文献的自动分类。随后至今，许多学者在这一领域进行了一系列卓有成效的 研究。它的发展从开始的基于知识的途径到基于机器学习的途径。8 0 年代，最有效的是基 于知识工程技术的分类系统，它是由专家人工构建的，其典型应用就是卡内基集团为路透 社开发的c o n s t r u e 系统，这种系统需要领域专家人工归纳出分类规则，再由这些规则指 导知识工程师协同工作，两者缺一不可。基于知识的分类系统需要大量的人力物力，且适 应性差。9 0 年代以后，基于机器学习的分类技术开始取代基于知识工程的方法成为主流技 术。在这些年的发展中，研究者们提出了多种分类算法，主要有朴素贝叶斯( n a i v eb a y e s ， 简称n b ) 、k 近邻( k - n e a r e s tn e i g h b o r s ，简称k n n ) 、粗糙集( r o u g hs e t ，简称r s ) 和支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 锄，并且将这些分类技术从理论研究引 入到了实用化阶段。国内的文本分类起步相对较晚，始于2 0 世纪8 0 年代，研究所使用的 方法也比较单一，对中文文本进行分类。从9 0 年代以后才开始，基本上是在英文文本分 类研究的基础上，结合中文文本的特点采取相应策略，形成针对中文文本的分类系统。国 内中文文本分类中较流行的方法主要集中在朴素贝叶斯、k 近邻、粗糙集和支持向量机等 w a n gb y ，z h a n gs m an o v e lt 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 nn a i v eb a y e sa n dk l d i v e r g e n c e c i n t e r n a t i o n a lc o n f e r e n c eo np a r a l l e la n dd i s t r i b u t e dc o m p u t i n g ，2 0 0 5 ：9 1 3 9 1 5 y a n gl i h u a ，d a iq i ，g u oy a n j u n s t u d yo nk n nt e x tc a t e g o r i z a t i o na l g o r i t h m j c o n t r o l a u t o m a t i o n 。 2 0 0 6 ：2 6 9 - 2 7 0 z h a n gj i a y o n g ，删j i a n h u i i n t e l l i g e n ti n f o r m a t i o nf i l t e r i n gs y s t e m sb a s e do nc h i n e s ew o r d s e g m e n t a t i o n j i n f o r m a t i o nt e c h n o l o g y ，2 0 0 6 ：1 7 5 1 7 8 2 技术上。 这些分类算法已应用于文本自动分类中，但仍有着不同的缺点。支持向量机虽然比其 他算法表现出良好的分类精度，但其面对高维大样本环境，训练时间会很长，甚至出现维 度灾难问题。朴素贝叶斯理论上能够达到最好的分类效果，但由于在大多数情况下，概率 参数和密度函数的形式都是无法获得的，这对b a y e s 方法的应用受到很大限制。k n n 分类 算法的优点是分类精度较高，缺点是分类速度与训练文档个数有关，且没有很好地考虑到 特征之间的相互关联与共现。粗糙集可以方便地表示文本的分类规则，在处理大量数据， 消除冗余信息等方面，该理论有着良好的效果，但它对错误描述的确定性机制简单，且在 进行约简的过程中缺乏交互验证功能，当数据中存在噪音的时候，结果表现为不确定、精 度不高。 1 3 基于r s - s v m 的文本分类算法 1 1 和1 2 节分析了文本分类技术发展现状和存在问题，针对高维中文文本大样本环 境下的耗时增大与维数灾难问题，将支持向量机分类功能与粗糙集的数据处理的降维功能 相结合，提出一种新的基于粗糙集与支持向量机( r s s ) 的分类方法。该方法利用粗糙 集理论和支持向量机之间的优势互补性来获得更好的数学模型，即在向量空间模型表示文 本的前提下，引入信息约简的粗糙集理论，首先利用粗糙集理论的属性约简对原始样本数 据进行预处理，简化样本数据空间的维数，删除冗余的特征向量，目的是降低系统的复杂 性，减少s v m 的训练时间，提高s v m 的收敛速度和分类精度。再将预处理后的数据作为样 本数据用s v m 进行训练，从而构造出具有良好推广能力的模式分类器。这种结合的算法将 在第三章中详细说明。 1 4 组织结构 本文研究了中文文本分类及其关键技术，粗糙集和支持向量基本理论，提出了基于 r s - s v m 的分类方法，并对该模型中的反馈学习模块进行了分析研究，最后基于该模型设计 并实现了基于r s s v m 的中文文本分类仿真。 本文的基本组织如下： ( 1 ) 第1 章是绪论。指出了本文的研究背景，国内外的研究状况，简要介绍了本文所 用文本分类的算法，并阐述了本文所做的主要工作。 3 ( 2 ) 第2 章是中文文本分类理论基础及相关算法。主要介绍了文本分类的基础理论， 比较分析了现今文本分类领域几个关键问题的常用解决方法。 ( 3 ) 第3 章是粗糙集和支持向量机基本理论。详细介绍了粗糙集理论和支持向量机技 术，对它们的相关算法进行了详细的描述，指出算法的不足和改进方法，并分析两者相结 合的优势，深入探讨了粗糙集的约简方法和支持向量机的分类方法。 ( 4 ) 第4 章是基于r s - s v m 中文文本分类方法中的设计与实现。首先对r s s v m 中文文 本分类进行了总体设计，详细说明了该方法的设计目标及设计思想，给出了逻辑结构；然 后对文本预处理，属性预降维，粗糙集属性约简，s v m 训练和分类部分进行了详细说明， 并根据实验结果进行分析，采用客观公正的语料库和通用的评估指标，比较三种分类方法， 表明改进的r s - s v m 分类方法实验结果较好，并提出一种改进的j o h n s o n 贪婪属性约简算 法。最后，对改进的r s - s v m 分类方法进行详细分析、语料库再分类，使其分类结果更加 准确有效。 ( 5 ) 第5 章是总结与展望。对全文的研究工作做了总结，继而探讨有待进一步解决的 问题，为未来的研究探索大致方向。 4 第2 章中文文本分类理论基础及相关算法 文本分类是指在给定分类体系下，根据文本内容自动确定文本类别的过程。2 0 世纪 9 0 年代以前，占主导地位的文本分类方法一直是基于知识工程的分类方法，即由专业人员 手工进行分类。人工分类非常费时，效率过低。9 0 年代以来，众多的统计方法和机器学习 方法应用于自动文本分类。文本分类作为数据挖掘的一个新主题，己经引起人们的极大兴 趣。文本分类技术的深入研究和在信息检索领域中的应用，进一步提高了信息检索的精度 和效率。本章主要介绍中文文本分类的基本概念，文本分类的相关技术和算法。目前英文 自动分类己经取得了丰硕的成果，提出了多种成熟的分类方法，如最近邻分类、贝叶斯分 类、支持向量机和v s m 等方法。国内中文文本分类研究主要集中在朴素贝叶斯、v s m 和s v m 等技术上。本章将有重点地讨论文本表示的分词特征选择算法，权重算法和应用较为广泛 的分类算法。 2 1 文本分类基本概念 文本分类是指按照预先定义的主题类别，为文本集合中的每个文本确定一个类别。这 样用户不但能够方便地浏览文本，而且可以通过限制搜索范围来使文本的查找更容易、快 捷。 简单地说，文本分类系统的任务是：在给定的分类体系下，根据已经掌握的每类若 干样本的数据信息，总结出分类规律性，建立判别公式和判别规则，然后，当遇到新样本 点时，只需根据总结出的判别公式和判别规则，就能判别该样本点的所属类别。 从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到分类体 系下已有的类别中。该映射可以是一一映射，也可以是一对多的映射，因为通常某些文本 不但可以同一个类别相关联，也可以同多个类别相关联，该映射用数学公式表示如下： f ：a - b 其中：a = ( d 。，d 。，d 。) ，b = ( c ，c 。，c 。)( 2 1 ) 即：a 为所有待分类的文本集合，b 为给定分类体系下所有类别集合，a 可以为无限集 合，而b 必须为有限集合。 文本分类的映射规则f 是文本分类的关键，学习方法不同，f 也有所不同。在已经确 定的映射规则基础上，学习分类器在遇到新文本时，通过计算和判断，最终确定文本的相 f s e b a s t i a n i m a e h i n el e a r n i n gi na u t o m a t e dt e x tc a t e g o r i z a t i o n a c mc o m p u i n gs u r v e y s 2 0 0 2 ，3 4 ( 1 ) ：1 - 4 7 5 关类别。 一般来说，文档分类首先需要解决的问题是预先确定好文本的类别，并且对每个文本 类别提供一批预先分好类的文本( 称为训练文本集) 。训练文本集的选择是否合适对文本分 类的性能有较大影响，它应该能够广泛地代表分类系统所要处理的客观存在的各个文本类 中的文本。一般而言，训练文本集应是公认的人工分类的语料库。 2 2 中文分词 在文本信息处理过程中，一般可以选择字、词或词组作为文本的特征项，根据实验结 果，普遍认为选取词作为特征项要优于字和词组，这是因为字所代表的信息量太少，且 存在很多多义字，字与字之间的界限模糊，而且用字作为特征项将导致特征向量庞大，学 习分类器时容易造成特征空间的维灾难；词组虽然携带足够的信息量，但词组在文本中出 现的机率不多，用词组作为特征项会导致特征向量稀少，损失很多重要信息。因此，为了 提取中文词条，需要对中文文本进行较为复杂的分词，称为中文分词( c h i n e s ew o r d s e g m e n i a t i o n ) 。分词目的是将连续的字序列按照一定的规范重新组合成词序列的过程。 比如将“组合成分子时切分成“组合成分子时 。 对于计算机来说，中文文本就是由汉字和标点符号等最基本的语言符号组成的字符串， 由字构成词，由词构成短语，进而形成句、段、节章、篇等语言结构创言。信息检索和分 类中常采用字词或短语作为特征项。然而，汉语是以字为基本的书写单位，文本中词与词 之间没有明确的分隔标记，而是连续的汉字串显而易见，自动识别词边界，将汉字串分为 正确的词串的汉语分词问题无疑是实现中文信息处理各项任务的基础与关键。中文词语分 析一般包括三个过程：预处理过程的词语粗切分、切分排歧与未登陆词识别和词性标注。 目前中文词语分析采取的主要步骤是：先采取最大匹配、最短路径、概率统计、全切分等 方法，得到一个相对最好的粗分结果，然后进行排歧未登陆词识别，最后标注词性在实际 系统中，这三个过程可能相互交叉反复融合，也可能不存在明显的先后次序。可以将现在 的分词算法分为三大类：基于字符串匹配的分词方法，基于理解的分词方法和基于统计的 分词方法。 庞剑锋，卜东泼，白硕基于向量空间模型的文本自动分类系统的研究与实现 j 计算机应用研究，2 0 0 1 ，1 9 ( 9 ) ：2 3 2 6 李荣陆文本分类及其相关技术研究 d 上海复旦大学博士论文，2 0 0 5 6 2 3 文本表示 通过不同文本分类系统的运行和比较表明，向量空间模型是文本分类领域大规模语料 库较好的表示模型。至今，国外在向量空间模型的研究方面日益成熟，但在基于向量空间 模型的特征选择算法的性能比较方面，以及文本分类算法的性能比较方面，还没有得出统 一的结论。 2 3 1 停用词的处理 通过计算机对文本进行分类，首先要把文本表示成计算机能处理的数据形式。在文本 分类中最常见的是对文本进行分词，这样文本就变为词集，而将全部词集作为文本分类的 特征。构成文本词汇的数量是相当大的，可以达几万个，因此需要对词集进行相应的压缩 以获得对分类有用的特征，特征词的选择只能由处理速度、精度、储存空间等方面的具体 要求来决定。选出的特征词越具有代表性，语言层次越高，所包含的信息就越丰富，分析 的代价也就越大，而且受分析精度的影响也越大。词集中有很多虚词在文章中仅起到结 构作用，不表示实际意义，比如介词，副词等等，另外还有一些词在整个语料中出现频率 高而在每篇文档中出现概率大致相等，对分类来说作用不大，把这些词合称为停用词。对 于这些词，应该从特征集中去掉。停用词的选取对词集的大小、分类的准确率都有影响， 解决这个问题的方法是把这些词组织成一个停用词表。 停用词表的生成过程： ( 1 ) 计算词频，人工从高频词中将认为对分类贡献不大的词选出，如：“的”、“在”、 “是”、“不”、“否则 等1 8 0 个词，作为停用词，放入停用词表。 ( 2 ) 将代词表、副词表、介词表、连词表和助词表加入，经过反复实验对比分析，最 后将代词和连词扩充进停用词表。 2 3 2 向量空间模型( v s m ) 向量空间模型( v e c t o rs p a c em o d e l ) 是由一组规范化正交词条矢量所组成的向量空 间，每一个文档映射为向量空间的一个点，向量间的距离表示文档之间的相似度。在这种 模型中，每一对象模型化为空间中的点，两对象间的差异由多维空间中的两点间的距离表 周茜，赵明生等中文文本分类中的特征选择研究 j 中文信息学报，2 0 0 4 ，1 8 ( 3 ) ：1 7 2 3 g e r a r ds a l t o n a u t o m a t i ct e x ts t r u c t u r i n ga n ds u m m a r i z i n g ： i n f o r m a t i o np r o c e s s i n g m a n a g e m e n t 。 1 9 9 7 ：1 9 3 - 2 0 7 7 示。通过这种模型可以将给定的文档以向量的形式表示在v s m 中，从而将文档之间的相似 性这一抽象的问题转化为具体空间的点与点的距离问题，通过计算出任意两个向量之间的 近似程度，从而反映所对应的文档间的相似性。 向量空间模型的基本思想是以向量来表示文本：( w 。，w 。，w n ) 。其中w ；为第i 个特 征项的权重，一般选择字、词或词组作为特征项。根据实验结果，普遍认为选取词作为特 征项要优于字和词组，因此，要将文本表示为向量空间中的一个向量，就首先要将文本分 词，由这些词作为向量的维数来表示文本，最初的向量表示完全是0 、l 形式，即：如果文 本中出现了该词，那么文本向量的该维为l ，否则为0 。这种方法无法体现这个词在文本 中的作用程度，所以逐渐o 、1 被更精确的词频代替。词频有绝对词频和相对词频之分。 绝对词频是指词在文本中出现的频率：相对词频是规范化的词频，即要求所有向量分量的 平方和为1 ，其计算方法主要运用t f i d f 公式。目前存在多种t f - i d f 公式，比较普遍的 t f i d f 公式如下所示： w ( t ，五) ：坠丝竺堕竺丝坠( 2 2 ) 善 仃“i ，】x l o g ( n n t , + 0 0 1 ) 2 t 3 t l 图1 1 文本的向量空间模型 资料来源：刘清基于s v m 的网络文本分类问题研究与应用 d 南昌大学硕士论文，2 0 0 7 ：1 2 向量空间模型有效地解决了非结构化文本数据的处理问题，提高了文本处理的速度和 效率，把对文本的操作转变为对特征向量的操作。本文采取向量空间模型对文档提取向量， 文本向量维度的计算方法用t f - i d f 公式，其中t f - i d f 公式将在2 5 3 小节详细介绍。 陈治纲，何王廉，孙越恒等基于向量空间模型的文本分类系统的研究与实现 j 中文信息学报，2 0 0 5 ，1 9 ( 1 ) ：3 6 4 0 8 2 4 特征项的选择 一篇文章在经过了分词处理之后，会产生很多词条。一个全面的训练语料库包含的文 本数量较多，分词后往往具有上万个特征项，如果将这些特征项全部根据向量空间模型来 表示文本，其特征维数将达到上万维，如此庞大的向量空间会使得每个特征项所含信息非 常平滑，有用信息反而不会突出。因此文本数据的两个难点就是特征的高维性与稀疏性。 根据j o h np i e r r e 的理论，用来表示文本的特征理论上应具有如下特点：数量上尽量少， 出现频率适中，含义尽量明确与其所属类别语义相关，此外冗余和噪音也要少。但就文本 来说，最方便采用的特征就是词或短语，它们往往具有如下一些特点：数量众多、出现频 率不等、噪音多、与其所属类别不一定相关。这就会对分类算法带来两个方面的问题：其 一，将会在训练与分类时间上带来很大的开销；其二，过多的特征往往会导致人们常说的 “维数灾难 问题。因此对文本数据进行维数压缩就变得极为重要。我们需要进行特征项 选取，把词条中最能代表某类文本信息的词条挑选出来，作为文本的特征项。实验结果表 明简化特征项不但不会使分类结果准确率降低，而且还会使结果更加准确。特征项选择一 般使用统计方法，利用各种计算公式，计算特征词所代表的信息含量，确定一个阈值，将 低于阈值的词语过滤掉，或者确定一个特征项数目n ，保留处于信息含量在前n 位的词条。 特征项的选择算法是文本自动分类中的一项关键技术和瓶颈技术，如何从原始文本特 征集合中选择最能表示文本主题内容的特征子集，是文本特征抽取算法的研究目标。常用 的方法有文档频率( d o c u m e n tf r e q u e n e y ) 、互信息( m u t u a li n f o r m a t i o n ) 、信息增益 ( i n f o r m a t i o ng a i n ) 、z 2 统计量等方法罾。下面将对这些算法进行简要介绍和比较。 2 4 1 文档频率( d e ) 文档频率是最简单的特征抽取技术，不需要依赖类信息，所以是一种无监督的特征选 择方法。文档频率就是文档集合中出现某个特征项的文档数目。在特征项选择中，计算每 个特征项在训练集合中出现的频率，根据预先设定的阈值去除那些文档频率特别低和特别 高的特征项。文档频率的计算复杂度较低，随训练集的增加而线性增加，其基本原则是： 很少出现的特征对分类价值极小，对整个分类系统的效果影响也很小，因此，将这些特征 去掉有助于降低特征空间维数，并且当这些不常出现的特征为噪音时，还会有助于提高分 j o h nmp i e r r e o nt h ea u t o m a t e dc l a s s i f i c a t i o no fw e bs i t e s l i n ko p i n ge l e c t r o n i ca r t i c l e si nc o m p u t e r a n di n f o r m a t i o ns c i e n c e v o l6 ( 2 0 0 1 ：n r 0 ，4 ，2 0 0 1 ：1 2 5 1 3 8 程泽凯，陆小艺文本分类中的特征项选取方法 j 安徽工业大学学报，2 0 0 4 ，v 0 1 2 1n o 3 9 类正确率。 d f 的优点是在计算量上比其它评估函数小得多：缺点是稀有单词可能在某一类文本中 并不稀有，也可能包含着重要的判断信息，简单地舍弃，可能影响分类器的精度。因此， 在实际运用中一般并不直接使用d f 。 2 4 2 信息增益( i g ) 信息增益在机器学习领域被广泛使用。对于词条t 和文档类别c ，用i g 考察文档类 别c 中出现和不出现词条t 的文档频数来衡量词条t 对于文档类别c 的信息增益。我们采 用如下的定义式： mmm 一一 g a i n ( t ) = t ，( c ) l o g p ( q ) + p “迈，( ci t ) l o g p ( cit ) 廿“) p ( c lt ) l o g p 心lt ) ( 2 3 ) 一1一 1 - 。一 1。 其中p ( c ；) 表示c i 类文档在语料中出现的概率，p ( t ) 表示语料中包含词条t 的文档的概 率，p ( c ；lt ) 表示文档包含词条t 时属于c ；类的条件概率，p ( t ) 表示语料中不包含词条t 的文档的概率，p ( c ；it ) 表示文档不包含词条t 时属于c t 的条件概率，m 表示类别数。i g 方法提取i g 值较高的特征，其基本思想为i g 值越高，则该特征在训练集中的类别上分布 越集中也越重要。 信息增益法的优势在于对未出现词可能对文本产生的影响做了考虑，不足之处是在进 行特征值选择时计算量大，影响了效率。 2 4 3 互信息( m i ) 互信息方法可以度量特征项和类别的共现关系，特征项对于类别的互信息越大，它 们之间的共现概率也越大。假设文档集合c 分为k 类，记为c 。，c 。，c t ，特征项w 对 于文档类别c ；的互信息m i ( w ，c ；) 的计算公式如下： m i ( w ，c i ) = l o g 篇岽 ( 2 4 ) 其中p ( w ，c 。) 为特征项w 出现在类c 。中的概率，p ( w ，c ) 为特征项w 在所有文档中的出 现概率。 y i m i n gy a n g ，j a n0 p e d e r s e n ac o m p a r a t i v es t u d yo nf e a t u r ei nt e x tc a t a g o r i z a t i o n j p r o e e e d i n g so ft h e f o u r t e e n t hi n t e r n a ti o n a lc o n f e r e n c eo nm a e h i n el e a r n i n g ( i c m 9 7 ) 1 9 9 7 ：4 1 2 4 2 0 y a n gs h e n g ，s i l lp e n g f e i b i d i r e c t i o n a la u t o m a t e db r a n c ha n db o u n da l g o r i t h m f o rf e a t u r es e l e c t i o n ，j o u r n a l o fs h a n g h a iu n i v e r s i t y ( e n g l i s he d i t i o n ) ，2 0 0 5 ，9 ( 3 ) ：2 4 4 2 4 8 孙丽华，张积东，李静梅一种改进的n k n 方法及其在文本分类中的应用 j 应用科技2 0 0 2 ，2 9 ( 2 ) ：2 5 2 7 1 0 如果特征项w 不是停用词，对于每一个文档类c ；，1 i k ，计算w 对于c ：的互信息 m i ( w ，c 。) 。 m ic w 一) = l o g 鬻( 2 5 ) 其中f r e q ( w ，c ；) 是w 在文档类别c ；中出现的次数，f r e q ( w ，c ) 是w 在整个文档集c 中出现的次数。给定给定阈值口，选择m i ( w ，c 。) 口的特征项组成特征空间。 互信息的优点是：对于低频词，其互信息比常用词互信息要高：缺点是：过于倾向低频 词，在低频词过多的情况下，将影响分类效果。例如，如果两个词语具有相同的条件概率 p ( w lc 。) ，那么出现次数少的词语会比出现次数多的词语得到更大的m i 值。 2 4 4z 2 统计( c h i ) c h i 具有和m i 方法基本相似的思想，通过计算特征项t 和类别c 间的依赖程度来完成 提取。但c h i 作了更多地考虑，其计算公式如下： c h m = 酉a 瓦c 芒畿等d 汜6 ， (+) ( b + d ) ( a + b ) x ( c +) 其中n 为训练集中包含的文本总数，a 为t 与c 同时出现的次数，b 为t 出现而c 未出 现的次数，c 为c 出现而t 未出现的次数，d 为二者都未出现的次数。c h i 有平均值和最大 值两种方法来取得特征的整体评价： c h i 。v g ( t ) = p ( c i ) c h ( t ，c i ) ( 2 7 ) c h i 。x ( t ) = m a x c h i ( t ，c i ) ) ( 2 8 ) i - - 1 c h i 方法的基本思想是与类别关系越紧密的特征重要性越高。c h i 的优点是经过归一化 处理的值和其他方法相比，词汇有所减少，分类效果好：缺点是对于低频词效果不好。 分析上述特征项的选择算法，提取效率的高低排序为：c h i d f m i i g 。i g 考虑了未出 现的词对文本的影响，所以统计花费大；d f 认为低频词无信息量，但低频词也可能带有很 大的信息量，这时直接去掉低频词会影响分类效果：m 1 过于倾向低频词，对符合兴趣的词 反应灵敏，对错误的词反应较差，所以它的分类效果相对较差。而对于c h i ，矿是一个归 赵选民，徐伟等著数理统计( 第二版) 岫，2 0 0 2 ，北京：科学出版社 1 1 一化的值，可以比其它方法大约减少5 0 的词汇，并且分类效果好。本文通过对几种评估 函数进行比较，采用z 2 统计( c h i ) 方法进行特征项选取。 2 5 特征权重算法 不同的特征项对文本的重要程度和区分度是不同的，所以在对文本分类模型进行形式 化的时候，需要对所有特征项进行赋权重处理，常用的加权函数有：布尔权重、词频权重