（计算机应用技术专业论文）文本自动分类技术研究及实现.pdf

桂林理工大学硕士学位论文 要 随着信息技术的不断发展，特别是i n t e r n e t 应用的普及，电子文本信息急剧增加。 如何有效地组织和管理这些海量信息，并且能够快速、准确地获得用户所需要的信息是 当今信息技术领域的一大挑战。文本分类作为处理和组织大量文本数据的关键技术，可 以在较大程度上解决信息杂乱的现象，方便用户准确地定位所需的信息。文本分类技术 在生活中起着越来越重要的作用，成为信息检索领域中最前沿的研究热点之一。 文本自动分类是在给定的分类体系下，对未知类别的文本进行自动处理，根据文本 特征来判断其所属类别的过程。本文首先介绍了文本自动分类在国内外的研究现状；其 次对文本自动分类的相关技术，包括中文分词技术、特征选择、文本表示以及关键的分 类算法，并分别进行了研究和探索，特别对几种不同的特征选择方法进行了研究。遗传 算法是模拟生物在自然环境中的遗传和进化过程而形成的一种全局优化概率搜索算法， 具有简单、通用、稳健等特性。本文深入研究了遗传算法，并在降低特征向量维数方面 将其引入到特征选择中。 分类器是文本分类的另一个重要环节。朴素贝叶斯分类器由于计算高效、精确度高， 并具有坚实的理论基础而得到广泛的应用。本文使用朴素贝叶斯作为分类器，设计并实 现了一个文本分类系统，该系统包括：文本预处理模块，对文本进行分词、停用词过 滤等；特征选择模块，实现了文档频率、信息增益、互信息、卡方统计等特征选择算 法；文本表示模块，采用向量空间模型来表示文本，其中特征项权重采用t f i d f 公式 计算；分类器算法模块，实现了朴素贝叶斯分类算法；分类器评价模块，对分类器 从查全率、查准率和f l 值等方面进行评价。接着利用该系统进行了几个实验，包括基于 遗传算法的特征选择方法的分类效果测试，朴素贝叶斯算法下常用的特征选择算法对分 类效果的影响，同一语料库下朴素贝叶斯算法和支持向量机算法的比较这三个实验。并 通过这些实验测试了系统的性能，验证了算法的有效性。最后对文本分类的未来研究方 向进行展望。 关键词：文本分类，特征选择，遗传算法，朴素贝叶斯，支持向量机 桂林理工大学硕士学位论文 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 fi n f o r m a t i o nt e c h n o l o g ye s p e c i a l l yt h ep o p u l a r i z a t i o no f i n t e m e ta p p l i c a t i o n ，t h ee l e c t r o n i ct e x ti n f o r m a t i o ng r e a t l yi n c r e a s e s i ti sag r e a tc h a l l e n g ef o r i n f o r m a t i o ns c i e n c ea n dt e c h n o l o g yt oo r g a n i z ea n dp r o c e s ss ol a r g ea m o u n to fd a t a ，a n df i n d o u tt h ei n t e r e s t i n gi n f o r m a t i o nf o rt h eu s e r sq u i c k l ya n de x a c t l y a st h ek e yt e c h n o l o g yi n o r g a n i z i n ga n dp r o c e s s i n gl a r g em o u n to fd o c u m e n td a t a , t e x tc l a s s i f i c a t i o nc a ns o l v et h e p r o b l e mo fi n f o r m a t i o nd i s o r d e r t oag r e a te x t e n t ，a n di sc o n v e n i e n tf o ru s e rt of i n dt h e r e q u i r e di n f o r m a t i o nq u i c k l y t e x t c l a s s i f i c a t i o nt e c h n o l o g yb e c o m e sm o r ea n dm o r e i m p o r t a n ti n0 1 1 1 d a i l yl i f ea n di th a sb e c o m eo n eo ft h eh o tp o i n t so f t h ef o r w a r dr e s e a r c h t e x tc l a s s i f i c a t i o ni st h ep r o c e d u r eo fa u t o m a t i c a l l ya s s i g n i n gp r e d e f i n e dc a t e g o r i e st o f r e et e x td o c u m e n t sb a s e dt h ed o c u m e n t sf e a t u r e s t h i st h e s i sf i r s t l yi n t r o d u c e dt h er e s e a r c h s t a t u so ft e x tc l a s s i f i c a t i o n s e c o n d l yw es t u d i e da n dd i s c u s s e dt h er e l e v a n c et e c h n o l o g i e so f t e x tc l a s s i f i c a t i o n ，i n c l u d i n gc 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 es e l e c t i o n , t e x tr e p r e s e n t a t i o n a n dc l a s s i f i c a t i o na l g o r i t h m s f e a t u r es e l e c t i o ni so n eo ft h em o s ti m p o r t a n ts e c t i o n si nt e x t c l a s s i f i c a t i o n ，s oe m p h a s e sw a r ep u to ni t t h e g e n e t i ca l g o r i t h m s a l eo n ek i n d o f a u t o - a d a p t e dg l o b a lo p t i m i z a t i o np r o b a b i l i t ys e a r c ha l g o r i t h m sw h i c hf o r mt h r o u g hs i m u l a t i n g h e r e d i t ya n de v o l u t i o np r o c e s so ft h eb i o l o g yi nt h en a t u r a le n v i r o n m e n t i t i ss i m p l e ， a l l - p u r p o s ea n ds t e a d y t h i st h e s i ss t u d i e dt h eb a s i ci d e a so f t h eg e n e t i ca l g o r i t h ma n da p p l i e d i tt of e a t u r es e l e c t i o ni nt h ea s p e c to f r e d u c i n gt h ed i m e n s i o no f v e c t o r s c l a s s i f i e ri si m p o r t a n ti nt e x tc l a s s i f i c a t i o n n a i v eb a y e s i a nc l a s s i f i e rh a so b t a i n e d w i d e s p r e a da p p l i c a t i o no w i n gt oi t sh i g h l ye f f i c i e n ta n dh i g h l yp r e c i s ec a l c u l a t i o n ，a sw e l la s i t ss t r i c tt h e o r e t i c a lf o u n d a t i o n i ti su s e da st h ec l a s s i f i e ri n t h i st h e s i s at e x ta u t o m a t i c c l a s s i f i c a t i o ns y s t e mw a sd e s i g h e da n di m p l e m e n t e d t h es y s t e mc o n t a i n s ：t e x tp r e p r o c e s s o r , s l i c i n gt h ew o f d si nt h ed o c u m e n t ，f i l t e r i n gt h es t o p w o r d ；f e a t u r es e l e c t i o nm o d u l e ，a c h i e v i n g t h ed o c u m e n tf r e q u e n c y , i n f o r m a t i o ng a i n ，m u t u a li n f o r m a t i o na n dc h i - s q u a r es t a t i s t i c ；t e x t r e p r e s e n t a t i o nm o d u l e ，a c h i e v i n gv e c t o rs p a c em o d e l ，a n da c h i e v i n gt f i d fa l g o r i t h m f o r f e a t u r ew e i g h t ；t h ec l a s s i f i c a t i o na l g o r i t h m ，a c h i e v i n gt h en a i v eb a y e s i a nc l a s s i f i c a t i o n a l g o r i t h m ；c l a s s i f i e re v a l u a t i o nm o d u l e ，a c h i e v i n gt h ec l a s s i f i c a t i o np e r f o r m a n c e se v a l u a t i o n m e c h a n i s mf r o mt h er e c a l lr a t e ，c h e c k r a t ea n dv a l u eo ff 1 s o m ee x p e r i m e n t sh a v eb e e nd o n e b yu s i n gt h i ss y s t e m ：t h ef e a t u r es e l e c t i o nb a s e do ng e n e t i ca l g o r i t h m e f f e c t s o nt h e c l a s s i f i c a t i o n ，d i f f e r e n tf e a t u r es e l e c t i o na l g o r i t h m s e f f e c t so nt h ec l a s s i f i c a t i o nu n d e rn a i v e b a y e s i a na l g o r i t h m ，t h ec o m p a r i s o no fn a i v eb a y e s i a na l g o r i t h ma n ds u p p o r tv e c t o rm a c h i n e h 桂林理工大学硕士学位论文 a l g o r i t h m d i s c u s s e da b i l i t yo ft h es y s t e ma n dp r o v e dt h ev a l i d i t yo ft h ea l g o r i t h mb yt h e e x p e r i m e n t s t h er e s e a r c h e so nt e x tc l a s s i f i c a t i o ni nf u t u r ew e r ep r o s p e c t e da tl a s t k e y w o r d s ：t e x tc l a s s i f i c a t i o n ，f e a t u r es e l e c t i o n ，g e n e t i ca l g o r i t h m ，n a i v eb a y e s i a n , s u p p o r tv e c t o rm a c h i n e i i i 研究生学位论文独创性声明和版权使用授权书 独创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含他人已经发表或撰写 过的研究成果，也不包含为获得其它教育机构的学位或证书而使用过的材料。对论文的 完成提供过帮助的有关人员已在论文中作了明确的说明并表示谢意。 ，! 学位论文作者( 签字) ：l 垦盘垒 签字日期：趁丝圜翌鲤一 学位论文版权使用授权书 本学位论文作者完全了解( 学校) 有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的印刷本和电子版本，允许论文被查阅和借阅。本人授权( 学 校) 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息研究所将本学位论文 收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。( 保密的学 位论文在解密后适用本授权书) 学位论文作者签名：善孑 农 签字日期：加。7 年乡月c 日 导师签字：融易7 鸟 签字日期：细j 年；月罗日 桂林理工大学硕士学位论文 1 1 研究背景及意义 第1 章引言 在当今的信息社会，人们已经从信息缺乏的时代过渡到了信息极大丰富的时代，特 别是随着i n t e r n e t 的大规模普及，网络上的信息量急剧增加，各种电子文本形式的情报 源所提供的信息量正以惊人的速度递增，人们仿佛置身于信息的海洋之中。人们面对丰 富的信息资源的同时，也面对着信息灾难。一方面，人们希望获得越来越多的信息；另 一方面，在这信息的汪洋之中，人们获取所需要的内容越来越困难。如何有效地组织和 管理这些信息，并快速、准确、全面地从中找到用户所需要的信息是当前信息科学和技 术领域面临的一大挑战。文本分类可以在较大程度上解决目前网上信息杂乱的现象，方 便用户准确地定位所需的信息和分流信息。文本分类作为信息检索、信息过滤、搜索引 擎、文本数据库、数字化图书馆等领域的技术基础，有着广泛的应用前景。 传统的文本分类工作是是对信息进行手工分类，这种人工分类方法存在着许多弊端： 一是耗费大量的人力、物力和精力，二是容易出现人为的分类错误，致使分类结果的一 致性不高。由于传统的手工分类周期长、成本高、效率低，难以适应信息迅速增长的现 状，以致手工分类在信息蓬勃发展的当代力不从心，基于机器学习的文本自动分类( 简称 文本分类) 越来越受到人们的重视。文本分类是人工智能技术和信息检索技术相结合的 研究领域，是进行基于内容的自动信息管理的核心技术，已成为人们研究的热点。 文本分类是指根据一些已经分配好的作为类标签的训练文档集合，来对新文档分配 类标签，其目的就是对文本集进行合理处理和组织，使得这些文本能够按照类别区分开 来。文本分类技术的研究目标就是实现文本分类的自动化，以达到降低传统分类技术的 人工费用，提高分类效率和性能等目的。近年来，计算机软、硬件技术的发展和自然语 言处理、人工智能等领域的研究进展为文本分类提供了技术条件和理论基础。文本分类 已经成为一项具有较大实用价值的技术受到广泛的关注，并得到了空前的发展和应用， 如大型网络检索系统、文档管理、数字图书馆中的文本归类系统、信息过滤系统等，这 些系统已广泛应用到了生活的方方面面，为人f i 提供了便捷的知识组织和获取途径。因 此，对文本分类的研究具有重要的实用价值。 1 2 国内外的研究现状 文本分类在国外的研究开展时间较早，1 9 5 7 年美国i b m 公司的h p l u h n 首次在自动 分类领域进行了开创性的研究，提出了将词频统计用于自动分类。1 9 6 0 年，m a r o n 在 桂林理工大学硕士学位论文 j o u r n a lo fa c m 上发表了有关自动分类的第一篇论文，提出了关键词自动分类技术，自 动分类技术正式诞生。它的发展从开始的基于知识的途径到基于机器学习的途径口1 。8 0 年代，最有效的是基于知识工程技术的分类方法，即采用人工方式来构建分类器，需要 专业人员手工编写分类规则来指导分类。其典型应用就是卡内基集团为路透社开发的 c o n s t r u e 系统b 3 。基于知识的分类系统需要大量的人力物力，且适应性差。9 0 年代以后， 随着电子文本的大量出现，基于机器学习的文本自动分类技术开始兴起，其效果明显超 过知识工程方法“】，成为信息系统学科最重要的研究领域之一。 自动文本分类技术己经成为机器学习技术和信息检索技术的交汇点和结合点，成为 所有基于内容的自动文本管理技术的重要基础。研究者们提出了多种分类算法，如朴素 贝叶斯( n a i v eb a y e s ) 、k 近邻( k n e a r e s tn e i g h b o r s ，简称i ( n n ) 嘲嘲、支持向量机( s u p p o r t v e c t o rm a c h i n e ，简称s v m ) 口1 等，并且将这些分类技术从理论研究引入到了实用化阶段。 1 9 9 6 年，a t t 实验室的d a v i dd l e w i s 等人将分类技术涉足到电子邮件领域。1 9 9 8 年， 美国c a r n e g i em e l l o n 大学计算机系的y i m i n gy a n g 等人将决策树( d e c i s i o nt r e e ) 等 聚类算法应用于在线自动分类。研究了一些可用的分类系统，例如，自动分类新闻稿件 的文本分类器饵7 1 ；自动分类w e b 页的文本分类器阳1 ；自动跟踪用户阅读兴趣的分类分析 器n 等等。这些系统大多数都建立在向量空间模型( v s m ) 的基础上，着重解决特征项的选 择和权重、机器学习算法等问题，以提高系统的性能和效率。并且建立了o h s u m e d ，r e u t e r s 等开放的分类语料库。 自从文本分类的概念在国内出现以来，该技术在国内得到了长足的发展。国内的文 本分类起步相对较晚，1 9 8 1 年，侯汉清教授首先探讨和介绍了国外文本分类的研究情况。 随后，国内很多学者在这方面进行了比较深入的研究。1 9 8 6 年，上海交大电脑应用技术 研究所的朱兰娟、王永成等开发的中文科技文献( 计算机类) 实验性分类系统。1 9 9 5 年， 清华大学电子工程系的吴军研制的汉语语料自动分类系统，以语料相关系数作为分类依 据，以字频、词频及常用搭配为补充，采用停用词表排除非特征词，进行人工指导分类。 1 9 9 8 年，东北大学的计算机系的张月杰、姚天顺研制的新闻语料汉语文本自动分类模型， 通过计算预定义类别和文本特征项之间相关性来进行自动分类。1 9 9 9 年，邹涛、王继成 等开发的中文技术文本分类系统c t d s ( c h i n e s et e c h n i c a ld o c u m e n tc l a s s i f i c a t i o n s y s t e m ) 采用了向量空间模型和基于统计的特征词提取技术，能够根据文本的具体内容将 其分配到一个或多个类别。 此外，国内很多学者对中文文本分类算法也进行了深入的研究，黄萱箐等提出一种 基于机器学习的、独立于语种的文本分类模型n 。周水庚等在论述隐含语义索引的理论 基础，研究了隐含语义索引在中文文本处理中的应用n 引。李荣陆等使用最大熵模型对中 文文本分类进行了研究n 秘。张剑等提出一种以w o r d n e t 语言本体库为基础，建立文本的 概念向量空间模型作为文本特征向量的特征提取方法n 刖。朱靖波等将领域知识引入文本 2 桂林理工大学硕士学位论文 分类，利用领域知识作为文本特征，提出一种基于知识的文本分类方法n 鄙。目前，我国 在中文文本自动分类领域已经取得了令人瞩目的研究成果，其中一些已经被成功推广和 应用，典型的代表性系统有计算所软件室的“天罗”、百度、慧聪等公司的搜索引擎等。 总之，国内外在文本分类系统上已经进行了很多的研究，也取得了不小的成果，但 是仍然存在很多尚待解决的问题，相信通过不断地努力，会进一步推动文本分类系统的 研究，获得更令人满意的结果。 1 3 本文的研究工作 首先，本文对文本自动分类中所涉及的相关技术和算法作了深入的探讨，包括文本 分类的基本概念、分类的过程，按照文本分类系统的整个过程介绍了分词技术、文本表 示方法、分类器算法、分类器的性能评价。 接着，重点研究了文本分类的特征选择，对文本分类中常用特征选择算法的性能以 及优缺点进行了分析，包括文档频率、信息增益、互信息和卡方统计，采取一种组合特 征选择方法，即综合采用几种不同的基本特征评价函数作为度量的准则。研究目前已应 用于许多领域的具有全局优化能力的遗传算法并将其应用于特征选择中，对特征空间进 行第二次降维。 在上述理论研究的基础上，设计并实现了一个文本分类系统，为研究文本分类相关 技术提供实验平台。系统分为：预处理模块，对文本进行分词、停用词过滤等；特征选 择模块，实现了文档频率、信息增益、互信息和卡方统计等特征选择算法：文本表示模 块，采用向量空间模型将文本表示为向量形式；分类器算法模块，实现了朴素贝叶斯分 类算法；分类器评价模块，从查全率、查准率和f 1 值等方面对分类器进行评价。利用该 系统，测试基于遗传算法的特征选择方法的分类效果，验证改进的特征选择方法的有效 性。测试朴素贝叶斯算法下不同特征选择算法对分类效果的影响，而且，在同一语料库 上进行朴素贝叶斯算法和支持向量机算法的比较试验。通过这些实验分析了系统的性能， 证明了算法的有效性。 1 4 本文组织 本文共分六章，文章结构及各章主要内容组织如下： 第l 章：引言，阐述了论文研究的选题背景和意义，介绍了国内外文本分类研究历 程和现状，最后，介绍了本文主要的研究工作，给出本文的整体组织结构。 第2 章：文本分类的相关技术，介绍了文本分类的相关实现技术。阐述了文本分类 的定义、分类的过程，按照文本分类系统的整个过程介绍了分词技术、文本表示方法、 分类算法、文本分类器的性能评价，为后面章节的讨论做准备。 桂林理工大学硕士学位论文 第3 章：基于遗传算法的特征选择方法研究，研究了文本分类中常用的各种特征选 择方法与遗传算法的基本思想，并将遗传算法引入到特征选择中。 第4 章：文本自动分类系统的设计与实现，介绍一个文本自动分类系统的设计与实 现，并对系统结构和主要功能等进行了说明。该系统将作为试验平台，完成文本分类技 术的一些测试研究工作。 第5 章：实验设置与结果分析，列出所做的各种实验及结果，包括各特征选择算法 及朴素贝叶斯和支持向量机分类器的测试结果。 第6 章：总结与展望，对全文的研究工作做简要总结，对今后的研究工作进行展望。 4 桂林理工大学硕士学位论文 2 1 文本分类概述 第2 章文本分类的相关技术 文本分类c r e x tc 1 a s s i f i c a t i o n ) 是一种文本管理的任务，它是机器学习和信息检 索之间的交叉学科。文本分类就是将大量文本划分为一个或一组类别，使得各个类别代 表不同的概念主题。 2 1 1 文本分类的定义 文本自动分类的任务是n 日：在给定的分类体系下，根据文本的内容自动地确定文本 关联的类别，给文本分配一个或者多个合适的类别。从数学角度来看，文本分类是一个 映射的过程，它将未标明类别的文本映射到已有的类别中，该映射可以是一一映射，也 可以是一对多的映射，因为通常一篇文本可以同多个类别相关联，用数学公式表示为： ：a 崎b 公式( 2 1 ) 其中，彳表示未标明类别的待分类的文本集合，召表示分类体系中己确定的类别集 合，厂为a 到曰的映射。文本分类的映射规则是系统根据已经掌握的每个类别的若干样 本的数据信息；总结出分类的规律性而建立起来的判别公式或判别规则。在遇到新文本 时，系统根据总结出的判别公式或规则，确定新文本相关的类别。 2 1 2 文本分类的过程 对于一般的模式识别系统，主要由四个部分组成：数据获取，预处理，特征提取和 分类决策【l 7 1 。而对于文本分类这样特定的模式识别系统，初始的数据是所给定的电子文 档，数据获取的过程可以省略掉。预处理的目的是去除噪声，加强有用的信息，并且为 后面的特征提取做准备。为了有效实现分类识别，就要对原始数据进行变换，得到最能 反映分类本质的特征，这就是特征选择的过程。一般把特征选择后得到的分类识别赖以 进行的空间叫做特征空间，在文本分类中，特征空间大多是采用文档中的关键词来表示。 分类决策就是在特征空间中用统计的方法把被识别的对象归为某一类别，基本做法就是 在样本训练集基础上确定某个判决规则，使按这种判决规则对被识别对象进行分类所造 成的错误识别率最小或引起的损失最小。这样的文本分类过程如图2 - 1 所示。 桂林理工大学硕士学位论文 2 1 3 文本分类任务的特点 ：- ， 图2 1 文本分类过程 文本分类实际上是一个模式分类任务，所以许多模式分类的算法可以应用到文本分 类中。但文本分类同时又是模式分类和自然语言处理的一个交叉学科，是和文本的语义 紧密相关的，所以与普通的模式分类任务相比有许多独特之处【1 8 】： 1 高维特征空间 在文本特征选择的时候，有大量的候选特征。如果使用词语作为文本特征，即使使 用一个接近2 0 0 0 篇的训练文档集，一般会产生两三万的候选特征。如果使用这些特征来 构造文本向量，那么向量空间的维数非常高。 2 特征语义相关 考虑一种避免“高维灾难 的解决办法是，假设特征之间是相互独立的，即一个特 征出现与否与其他的特征并无关系。但是，一般地，文本分类中很多特征包含一些相互 依赖的关系，例如：“中共、“中央”两个词共同出现的概率较大，存在相互依赖关系。 3 特征存在多义和同义现象 文本分类中一般使用词、短语等作为表征文本语义的文本特征，但是，这些特征往 往无法清晰地表达一种含义。一个特征可能有多种含义，即多义现象，如：“教授这个 特征既可以表示一种职称的含义，也可以表示一种传授知识的含义。同时，许多相同的 含义可以用不同的特征来描述，即同义现象，例如：“计算机和“电脑 这两个特征都 表示相同的含义。 4 特征分布稀疏 用特征词来表示文档的时候，往往特征维数非常高，而文档所出现的特征词只占总 6 桂林理工大学硕士学位论文 特征词的小部分。特别是对于一篇比较短的文档来说，特征空间中，仅仅出现少量的特 征词，因此，多数特征词的出现频率都为零，导致了文档向量中大多数的特征的值都是0 ， 特征的分布非常稀疏。 5 基本线性可分 文本分类中大部分类别之间是基本线性可分的，所以一些复杂的、在其他模式分类 任务中应用很成功的方法，在文本分类中未必会取得很好的效果。 2 2 分词技术 分词就是将连续的字序列按照一定的算法划分成词序列的过程。在英文文本中，单 词之间是以空格作为自然分隔符的，而中文文本一般是无分隔符的字符串，只是字、旬 和段可以通过简单的分界符来划界，唯独词没有一个形式上的分隔符，为了对文本进行 表示，我们需要对中文文本进行分词u 町。 分词是汉语自然语言处理的第一步。目前，汉语自然语言处理的应用系统处理对象 越来越多的是大规模语料，因此分词的速度和分词算法的易实现性变得相当关键。根据 研究出发点的不同，分词技术可以归纳为三类啪1 ：基于机械匹配的分词方法、基于统计 语言模型的分词方法与基于理解的分词方法。目前研究中文分词的大多是科研院校，清 华、北大、中科院、东北大学、m m 研究院、微软亚洲研究院等都有自己的研究队伍。 他们在这方面的研究取得了一定的成果，并开发出了一些较为成熟的中文分词系统。 2 3 文本表示 文本分类系统所处理的原始数据是非结构化的杂乱无章的自然语言文本，而计算机 并不能轻易地“读懂 它们，因而若要对这些信息进行分析与处理，首要的任务就是将 它们从一个无结构的原始文本转化为结构化的计算机可识别处理的信息，即对文本进行 形式化处理，这个形式化的结果一般称之为文本表示。 文本表示所采用的模型有很多种，目前通常采用的有凹u 概率模型( p r o b a b i l i s t i c m o d e l ) 、潜在语义索引模型( l a t e n ts e m a n t i ci n d e x ) 和向量空间模型( v e c t o rs p a c e m o d e l ，v s m ) 。其中，向量空间模型是目前应用最广的文本表示模型，并且已经在英文文 本分类中取得了成功，已经投入了实际应用。 1 向量空间模型 s a l t o n 等人于6 0 年代末提出了向量空间模型v s m ( v e c t o rs p a c em o d e l ) 的概念，最 早应用于信息检索领域，例如著名的s m a r t ( s y s t e mf o rt h em a n i p u l a t i o na n dr e t r i e v a l o ft e x t ) 系统就成功的应用了向量空间模型技术，后来又在文本分类领域得到了广泛的 应用。向量空间模型是一种不考虑特征项出现顺序的词袋( b a go fw o r d s ) 文本表示模 7 桂林理工大学硕士学位论文 型，这种模型带来了计算和操作上的方便。向量空间模型的一个基本假设，一份文档所 属的类别仅与某些特定的词或词组在该衷档中出现的频数有关，而与这些词或词组在文 档中出现的位置或顺序无关。 在向量空间模型中，文本集被看作是由一组正交词条( f 。，t ：，t 。) 所张成的向量空 间，每个文本可以看成为空间中的一个点( 向量) ：矿( d ) = ( w ，w ：，w 。) 其中心为词条t 的权值，表示该词条在文本中的重要程度。即文本向量中每一维对应于文本中的一个特 征，它的权重为该向量维对应的特征在文本中的权重。在v s m 中，这样如果有m 个文本， 则可以构成一个二维的m 刀阶的矩阵a ，其中第f 行代表第f 个文本，第，列代表第个 特征项，4 ，则代表第，个特征项在第f 个文本中所具有的权值。k n n 、支持向量机( s v m ) 和n b 都是基于向量空间模型的。 众多学者的研究表明：向量空间模型是大规模语料库较好的表示模型，并且在大规 模真实文本处理方面( 例如，文本分类和文本摘要等) 具有较强的优势腰列。在文本分类、 自动索引、信息检索等领域，向量空间模型得到了广泛的应用，己逐渐成为最简便最高 效的文本表示模型之一。虽然文本的向量化丢失了原先蕴涵的大量信息，但通过实践证 明，在文本分类等文本信息处理领域中，基于向量空间模型的信息处理系统仍然能够达 到较高的性能口习。 2 文本相似度计算 在向量空间模型中，两个文本4 和幺之间的内容相关度即为文本相似度，用 s i m ( d ，d ，) 来表示。相似度计算有各种距离、向量内积、夹角余弦等多种不同的方法及变 形吼1 ，常用的度量公式有： ( 1 ) 向量内积 ( 1 i n ) 公式( 2 2 ) ( 2 ) 夹角余弦 文本的相似度可以用对应的向量之间的夹角余弦来表示，余弦计算的好处是得到的 值正好是一个介于0 到1 的数。对于文本d l 和畋，相似度可以表示为： s i m ( d l ，畋) = c o s o = 3 特征权重 h ，屹 t = l ( 1 i 刀) 公式( 2 3 ) m 露烈 = 以吐 = 畋盔 跏 桂林理工大学硕士学位论文 不同的特征项对文本的重要程度和区分度是不同的，所以在对文本分类模型进行形 式化的时候，需要对所有特征项进行赋权重处理。权值的计算方法有很多，以下，我们 介绍几种常见的有代表性的权值计算方法。首先，有如下符号约定：口洼表示特征i 在文 本七中的权重，名表示特征i 在文本七中的出现频数，表示文本集的文本总数，仇表 示词条七的文本频数。 ( 1 ) 布尔权重( b o o l e a nw e i g h t i n g ) 。布尔权重只有0 和1 ，如果特征词在文本中没 有出现，就将该特征权重赋为0 ，若特征词在文本中出现，则该特征权重赋为1 ，即： f1 = t o i i 0 0 t h e r 公式( 2 4 ) ( 2 ) 词频权重( t e r mf r e q u e n c yw e i g h t i n g ) 。在词频权重中，特征词f 在文档k 中出 现的频率就是词f 在文档七中的权重，即： ni = f i 公式( 2 5 ) 词频权重的根本思想在于：某个词在文档中出现次数越多，它代表的特征项就越重 要。但是，也有不同情况，文档中的一些高频词并不一定很重要。 ( 3 ) t f i d f 权重( t e r m sf r e q u e n c yi n v e r s ed o c u m e n tf r e q u e n c yw e i g h t i n g ) 是在 文本处理领域中使用最广泛的数值权重计算方法。该方法基于以下原因：一是特征i 在文 本，中出现次数越多，越重要；二是文本集中含有特征f 的文本，越大越不重要。t f i d f 方法基于的思想和构造的统计量都很简单，但是，在实用中却表现了很好的性能。权重 函数为： w i 七= t f kxf 妖 公式( 2 6 ) 其中吮( t e r mf r e q u e n c y ) 表示项气在文本皿中的文本内出现的频率， 坝( i n v e r s ed o c u m e n tf r e q u e n c y ) 表示项气的反文档频率，是反映在一个文档集中按 文档统计出现的频繁程度的指标。它们有多种计算方法，目前较为常用的公式为： = t f k l o g ( n 。+ ，) 公式( 2 7 ) 以七 其中以表示项气在文本皿中出现的次数，的取值需要根据实验来确定，一般取 0 0 1 。根据香农信息学理论，如果项在所有文本中出现的频率越高，那么它所包含的信 息熵就越小；如果项的出现较为集中，只在少量文本中有较高的出现频率，那么它就会 9 桂林理工大学硕士学位论文 拥有较高的信息熵。上述公式就是基于这个思想的一种实现。考虑到文本长度对权重的 影响，还应该对权重公式做归一化处理，如下式所示： = 2 4 文本分类器 剩。g ( 铷。) 公式( 2 8 ) 分类算法是分类系统的核心部分，目前，研究者已经提出了许多成熟的文本分类算 法，这些算法大都来自于模式分类，基本上可以分为三大类：一种是基于统计的文本分 类方法，如k n n 分类算法，贝叶斯算法，回归模型，支持向量机，最大熵模型等算法； 另一种是基于连接的方法，也就是神经网络，还有一种是基于规则的方法，如决策树， 关联规则等。 下面我们重点介绍本文涉及到的两个文本分类算法：朴素贝叶斯算法与支持向量机 分类算法。本文选择这两个文本分类算法的原因是：朴素贝叶斯分类算法逻辑简单，易 于实现，算法实施的时间空间开销小，算法性能稳定，对于不同特点的数据其分类性能 差别不大，即模型的健壮性比较好；支持向量机算法是准确率较高的文本分类算法。 1 朴素贝叶斯 朴素贝叶斯( n a i v eb a y e s ，n b ) 乜司乜钔分类方法是贝叶斯学习方法中最常用的方法， 它是一种简单而又非常有效的分类方法。它是利用已有类别文本信息的先验概率计算新 文本所属类别的后验概率，其基本理论依据是b a y e s 定理。 朴素贝叶斯算法假定特征对于给定类的影响独立于其它特征，即特征独立性假设， 做此假设是为了简化所需的计算，并在此意义下称为“朴素的1 。对文本分类来说， 它假设各个单词彤和彤之间两两独立，如图2 2 所示。 图2 2 朴素贝叶斯分类模型( c 表示类别，| 。表示范例的属性) 1 0 桂林理工大学硕士学位论文 设i ) l l 练样本集分为k 个类，记为c = ( q ，g ) ，则每个类c ；( i = l ，2 ，k ) 的先验概 率为尸( e ) ，其值为c ；类的样本数除以训练集总样本数n 。对于新样本d ，；g n - j ：c ；类的 条件概率是p ( 刎c ；) ，根据贝叶斯定理，c ；类的后验概率为p ( c 。i d ) ： 他= 帮 公加9 ， p ( d ) 对于所有类均为常数，可以忽略，则式( 2 9 ) 简化为 尸( eid ) 虻尸( dj g ) p ( c ：) 公式( 2 1 0 ) 为避免尸( q ) 等于0 ，采用拉普拉斯概率估计： 粥) = 黼 怵2 式中：l c l 为训练集中类的数目，ld c fl 为训练集中属于类c ；的文档数，l 眈i 为训练集 包含的总文档数。 在特殊情况下，训练样本集中各类样本数相等，此时类的先验概率相等，式( 2 1 0 ) 可以简化为： 尸( gi d ) o ：e ( d l c , ) 公式( 2 1 2 ) 朴素贝叶斯分类器将未知样本归于类的依据，如下： p ( c ， d ) = a r g m a x p ( c j d ) p ( c j ) ，j = l ，2 ，七公式( 2 1 3 ) 文档d 由其包含的特征词表示，即d - - ( w 。，w 2 ，) ，m 是d 的特征词个数| d l ，m 是 第，个特征词，由特征独立性假设，则得： p ( de ) = 尸( ( h ，心，w m ) ic i ) = _ 兀尸( 一ic , ) 公式( 2 1 4 ) l a l 式中：尸( _ ic j ) 表示分类器预测单词在类g 的文档中发生的概率。因此式( 2 1 0 ) 可转换为： e ( c , l d ) 芘p ( g ) 兀i d l 尸( 叶ic 1 ) 公式( 2 1 5 ) j 桂林理工大学硕士学位论文 为避免式( 2 1 5 ) 中尸( m le ) 等于0 ，可以采用拉普拉斯概率估计。有两种方法计 算尸( m ic , ) ，即多元贝努利型计算公式和多项式型计算公式。 1 ) 多元贝努利：不考虑单词在文档中的出现频次，仅考虑单词在文档中是否出现，0 表示未出现，1 表示出现，依式( 2 1 6 ) 计算： 尸( i g ) 亏坐幽2 + i d , i 公式( 2 1 6 ) 式中：n ( d o c ( w j ) l e ) 为e 类文本中出现特征一的文本数。 2 ) 多项式：考虑单词在文档中出现的频次，依式( 2 1 7 ) 计算： 小= 商辩川2 其中，尸( w iq ) 为词w 在q 中出现的概率，p i 为该类的训练文本数，n ( w ，西) 为词 w 在文档喀中的词频，i v i 为总词数，竺。2 ( 嵋，z ) 为该类所有词的词频和。 与非贝叶斯方法相比，贝叶斯方法的突出特点是其学习机制可以综合先验信息和后 验信息，既可避免只使用先验信息可能带来的主观偏见和缺乏样本信息时的大量盲目搜 索与计算，也可避免只使用样本信息带来的噪音的影响。只要合理地确定先验，就可以 进行有效的学习。基于贝叶斯方法的分类器由于以完善的贝叶斯理论为基础，有较强的 模型表示、学习和推理能力，使得基于贝叶斯方法的分类器的研究和应用正成为模式识 别、人工智能和数据挖掘等领域的研究热点。 朴素贝叶斯的特征独立性假定使得分类器不需要计算单词之间的联合分布概率，使 得其速度远快于那些非朴素贝叶斯方法( 达到指数复杂度) 。迄今为止，朴素贝叶斯模型 已在多种分类领域及工程实践中得到了成功的应用，用于大型数据库，它也表现出了高 准确率与高速度。在理论上讲，与其他所有的分类算法相比，贝叶斯分类具有最小的出 错率，在其类条件独立的假定成立的前提下，它是最佳的分类算法。然而在很多情况下， 其类条件独立的朴素假定并不能成立，但实践证明，即便如此，它在很多领域中仍然能 够获得较好的分类结果。本文设计了一个朴素贝叶斯文本分类系统，利用该系统测试作 者采用的基于遗传算法的特征选择方法的分类效果。 2 支持向量机 支持向量机( s v m ：s u p p o r tv e c t o rm a c h i n e ) 汹汹1 方法是由v v a p n i k 与其领导的贝 尔实验室的小组一起开发出来的，是近些年来在统计学理论的基础上发展的新的模式识 别方法，它在解决小样本、非线形及高维模式识别问题中表现出许多特有的优势。支持 1 2 桂林理工大学硕士学位