（计算机应用技术专业论文）基于信息熵的中文文本分类算法研究.pdf

西北师筢大学硬士学位论文 摘要 随着i n t e r n e t 的快速发展，w e b 已成为全球性的、巨大的、分布和共享的 信息空间，它为人们搜索信息提供了一种新的手段。但随着i n t e r n e t 上信息量 的爆炸式增加，信息搜索时，与特定用户要求不大相关的信息大量涌现，甚至掩 盖了对用户真正有用的信息。在这繁杂的信息中，如何快速地找到用户需要的信 息以及有效地利用这些信息，文本分类起着非常重要的作用，它可以有效地组织 和管理这些信息，从而提高信息搜索的效率。 本文首先介绍了文本自动分类在国内外的研究现状；其次对文本自动分类所 涉及的关键技术，包括文本表示模型、中文分词方法、特征选择以及关键的分类 算法，分别进行了研究和探索；重点针对中文分词技术，再次提出了关键词集抽 取算法，实验表明，我们的抽取系统基本上能将命名实体切出来：接下来介绍了 基于信息熵的文本分类系统的总体框架，应用信息熵理论，提出了一种文本分类 的新方法。该方法利用熵来度量新文本对于己分类文本集合的贡献大小，并以此 熵值来判断文本归属的类，最后设计并验证了基于信息熵的文本分类模型。实验 结果表明基于信息熵的文本分类模型是一种比较稳定的算法，证明了算法的有效 性。 关键词：文本分类，特征选择，中文分词，分类算法，信息熵 西北师藏大孛硬士学位论文 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 t e m e t , w e bh a sb e e nd e v e l o p e di n t oa # o b m ， m a s s w e ，d i s t r i b u t e da n ds h a r e di n f o r m a t i o ns p a c e i tp r o v i d e san e wm e a n sf o rp e o p l e t os e a r c hi n f o r m a t i o n b u tw i t ht h ee x p l o s i v ei n e a s eo fi n f o r m a t i o no nt h e i n t e m e t ， i ta v a l a n c h e sa b u n d a n c ei r r e l e v a n ti n f o r m a t i o nw i t hu s e r sr e q u e s ta n dt h er e l e v a n t i n f o r m a t i o nf o r1 1 8 e ri sc o v e r e d u p i n t h ec o m p l i c a t e di n f o r m a t i o n ，a u t o m a t i c c l a s s i f i e rp l a y sa l li m p o r t a n tr o l ei nf i n d i n gt h en e e d e di n f o r m a t i o na n di ne f f e c t i v e l y u s i n gt h es h a r e di n f o r m a t i o n i ti m p r o v e st h ee f f i c i e n c yo fi n f o r m a t i o nr e t r i e v a lb y e f f e c t i v e l yo r g a n i z i n ga n dm a n a g i n gi n f o r m a t i o n t h i sp a p e rf i r s t l yi n t r o d u c e st h er e s e a r c hs t a t u so ft e x tc a t e g o r i z a t i o na th o m e a n da b r o a d , s e c o n d l yw es t u d ya n dd i s c u s st h ek e yt e c h n i q u eo ft e x tc a t e g o r i z a t i o n ， i n c l u d i n gt e x te x p r e s sm o d e l ，c h i n e s ew o r ds e g m e n t ，f e a t u r es e l e c t i o na n dc l a s s i f y m e t h o d s f o c u s i n go nt h ec h i n e s ew o r ds e g m e n t a t i o nt e c h n o l o g y , o n c ea g a i nw e p r o p o s ean e wk e yp m a s ee x t r a c t i o na l g o r i t h m e x p e r i m e n t ss h o wt h a to u r e x t r a c t i o n s y s t e mc 强c u to u tn a m e de n t i t yb a s i c a l l y n e x t w ei n t r o d u c et h ef r a m eo ft e x t c a t e g o r i z a t i o ns y s t e mb a s e do ne n t r o p y u s i n gi n f o r m a t i o ne n t r o p yt h e o r y , w ep r e s e n t an e wt e x tc a t e g o r i z a t i o nm e t h o d i tt a k e se n t r o p yt om e a s u r et h ec o n t r i b u t i o nt h a tt h e n e wt e x tm a k e st oc a t e g o r i z a t i o ns e t ，a n du s e st h i se n t r o p yv a l u et oj u d g ew h i c ht h e n e wt e x tw i l lb e l o n gt o f i n a l l y , w ed e s i g na n dv 喇f yt h et e x tc a t e g o r i z a t i o nm o d e l b a s e do ne n t r o p y t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep e r f o r m a n c eo ft e x t c a t e g o r i z a t i o nm o d e lb a s e do ne n t r o p yi sar e l a t i v e l ys t a b l ea l g o r i t h m ，a n dp r o v et h e e f f e c t i v e n e s so ft h ea l g o r i t h m k e yw o r d s ：t e x tc a t e g o r i z a t i o n ，f e a t u r es e l e c t i o n , c h i n e s ew o r ds e g m e n t a t i o n , c a t e g o r i z a t i o na l g o r i t h m ，i n f o r m a t i o ne n t r o p y 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包括其他人已经发表或撰写过的研究成果，也不包含为 获得西北师范大学或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 签名： 圣兹日期：力越：兰：箜 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵守此规定) 日期：碑! ：兰 西北师藏大学磺士学位论文 第一章绪论 第一章绪论 i n t e r n e t 的出现为人们搜索信息提供了一种新的手段，但随着i n t e r n e t 的 快速发展，网上的信息量爆炸式地增加，与用户要求不大相关的信息大量涌现， 甚至掩盖了对用户有用的信息。如何在信息的海洋中快速地找到需要的信息，这 就需要一个自动分类器，对网上的信息分门别类，以便于提高人类搜索和阅读信 息的速度。 1 1 文本分类的研究背景和意义 当前由于计算机硬件及数据库技术的不断进步，特别是w w w 的诞生与迅猛发 展，使得大量的、内容包罗万象的文字信息开始以计算机可读的形式存在，并且 其数量每天仍在急剧增加。一方面，这使我们获得了有效且廉价、可靠的数据存 取手段和极度丰富的数据资源；另一方面，也使得无论是商业企业、科研机构或 者政府部门，都积累了大量的文档资料，面临着海量的信息。但现实中，具体的 信息用户往往只需要其中的很少一部分，如何在浩若烟海而又纷繁复杂的文本中 掌握最有效的信息始终是信息处理的一大目标。如果仅仅通过人工的手段对庞大 的原始文档集进行组织和整理，不仅费时、费力，效果也未必很理想；相比之下， 如果能由计算机直接对文档信息进行过滤、分类，把用户真正感兴趣的部分提交 给用户，就能使用户从繁琐的文档处理工作中解放出来，更加便捷地认识和区分 不同的文档内容，使大量的繁杂的文档条例化和系统化，并能极大地提高信息的 利用率。因而，研究利用计算机进行自动文档分类成为自然语言处理和人工智能 领域中一项具有重要应用价值的课题n ，。 文本分类其实也是一种文献检索的手段，与普通的文本检索不同的是文本分 类技术预先设定了一个类别集合，对检索的文本，根据一定的判别法则，判断其 是否属于这个集合中的某个类。文本分类技术在文本检索、信息过滤、数据组织、 符号知识抽取、新闻分发、排序电子邮件、学习用户兴趣等方面都具有相当的实 际应用价值。例如，( 1 ) 随着i n t e r n e t 的快速普及，人们越来越多的通过互联网 络查找各种文献资料，诸如书刊、论文、科研资料、会议记录等等。但是使用过 互联网络的人都知道，要想在网上找到自己需要的资料不是一件容易的事，即使 借助于专门的搜索引擎( 目前大部分的搜索引擎是按关键词搜索的) ，信息检索的 精度也往往不能够令人满意，检索得到的结果经常包含大量无关的资料。例如， 西北师范大学硕士学位论文 第一章绪论 网上检索关键词为“文本分类”的文献，其检索的结果令人感到尴尬：有数百篇 文献被检索到，而事实上真正符合要求的文献只有数十篇。其原因在于检索文献 的范围太宽，只要含有关键词“文本分类”的文献均被检索出，但实际想检索的 文献是那些与“文本分类”这一主题相关的文献。显然，如果能够使用文本分类 技术对检索结果进彳亍过滤，剔除掉无关的文献，无疑将有效提高网上文献检索的 精度。( 2 ) 图书馆的文本资料管理，也需要对文本进行分类。众所周知，图书馆 的整个索引系统都是建立在分类的基础之上的。( 3 ) 此外，文本分类对于语料库 语言学的发展也将有很大的推动作用。随着语料库语言学的发展要求语料库的规 模越来越大，同时，电子出版业的迅速发展也使得获取大量的电子文本建立大规 模语料库已成为可能，但语料处理的速度却相对落后于语料收集的速度。因为收 集来的粗语料通常是杂乱无章的，在加工整理前必须进行分类处理，而目前对粗 语料的分类处理过程仍然是以手工为主，不但效率低，而且对从事分类的工作人 员水平要求较高。如果能够代之以自动分类，无疑将大大加快语料处理的速度。 1 2 文本分类技术的研究现状 1 2 1 文本分类在国外的发展 国外对于文本自动分类的研究开始较早，始于2 0 世纪5 0 年代末，h p l u h n 在这一领域进行了开创性的研究，他首先将词频统计的思想用于文本分类中。 1 9 6 0 年，m a r o n 发表了有关自动分类的第一篇论文o nr e l e v a n c ep r o b a b i l i s t i c i n d e x i n ga n di n f o r m a t i o nr e t r i a l ，其后许多学者在这一领域进行了卓有成 效的研究。国外的自动分类研究大体上可以分为三个阶段：第一阶段( 1 9 5 8 年 一1 9 6 4 年) ，主要进行自动分类的可行性研究：第二阶段( 1 9 6 5 年- 1 9 7 4 年) ，自 动分类的实验研究，第三阶段( 1 9 7 5 年一至今) ，自动分类的实用化阶段，并在 邮件分类、电子会议，信息过滤等方面取得较为广泛的应用，其中较为成功的系 统有麻省理工学院( m i t ) 为白宫开发的邮件分类系统；卡内基集团为路透社开 发的c o n s t r u e 系统。1 ，主要是由专业人员编写一些分类规则来指导分类，它的 功能是自动地对路透社每天成千上万的稿件进行分类。 1 9 9 4 年，a t & t 实验室的d a v i dd 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 等人研究了基于向量空间模型的 2 西北师范大学硕士学位论文 第一章绪论 自动分类系统。同年，美国s t a n f o r d 大学计算机系的d a p h n ek o l e r v 等人提出 了基于很少语料词汇的层次自动分类方法。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 等人将决策树等聚类算法应用于在线自动分类。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 公司也为其浏览器开发了 基于内容属性分类的插件。 国外当前流行的文本分类方法有k 近邻法( k n n ) 啪、决策树。1 、朴素贝叶斯 ( n b ) 。1 、支持向量机( s v m ) 。1 、神经网络( n n e t ) ”等方法。这些方法在英文 文本自动分类上有广泛的研究，而且很多研究表明k n n 和s v m 是英文文本分类的 最好方法。 1 2 2 文本分类在国内的发展 中文文本分类研究起步较晚，始于2 0 世纪8 0 年代初期，1 9 8 1 年侯汉清教 授对计算机在文献分类工作中的应用作了探讨，并介绍了国外在计算机管理分类 表、计算机分类检索、计算机自动分类、计算机编制分类等方面的情况。我国自 动分类的研究大体上正在经历从可行性探讨一辅助分类一自动分类系统的发展阶 段。例如，清华大学吴军研制的自动分类系统、山西大学刘正瑛等人开发的金融 自动分类系统、上海交通大学王永成等研制的基于神经网络优化算法的中文自动 分类系统、广州西风公司研制开发的西风文本自动分类系统。 自从自动文本分类的概念在国内出现以来，该技术在国内得到了长足的发 展，然而和国外的发展状况相比，发展水平相对滞后，一方面由于国内起步较晚， 另方面由于国内的工作主要是针对中文文本，由于汉语有许多不同于英语的特 点，使得中文自动文本分类的难度更大。比如，汉语的书面形式是连续书写的， 词与词之间没有自然的界限，在进行文本分类之前，首先要对文本进行分词。另 外，在不同的语言的研究工作中，句法分析和语义分析所占的比例是不同的。在 英语中，句法分析比语义分析的比例要大，而汉语是一种分析性语言，语义分析 在汉语研究中起着举足轻重的作用，其所占的比例比句法分析要大得多。这使得 在中文自动文本分类中，通过句法分析等基于语法的手段把握文本的内容变得更 加困难。国内也已开展了文本分类的研究，例如，吴军、吴立德、黄萱菁“1 等进 西北师范大学硕士学位论文第一章绪论 行了汉语语料自动分类的研究，他们以字或词为特征项构成特征向量，以频度作 为词的权重，利用一些分类算法构造分类器，取得了一定的效果。但是总的来说， 研究相对落后，主要存在如下问题： ( 1 ) 缺少统一的中文语料库 至今尚无标准的用于文本分类的中文语料库，各个研究者分头收集自己的训 练文本集，并在此基础上开展研究，因此系统的性能可比性不强。同时，由于财 力人力有限，中文语料库的规模普遍不大。 ( 2 ) 适用于中文的向量空间模型的研究还不十分成熟 国内的学者，例如吴立德和黄萱菁提出可以使用字、词、概念作为中文的特 征项构成向量空间模型，并对以此为基础的文本分类系统进行了初步的性能比 较。但是，对于概念的定义不够清晰，也没有全面的比较和测试系统。另外，在 特征项抽取算法方面也缺少系统而深入的研究。 ( 3 ) 文本分类技术与其他信息技术尚未很好地结合 国内的文本分类系统主要应用于图书馆等专业信息处理机构，在信息服务领 域，除了与搜索引擎有所结合外，文本分类技术与其他信息技术还没有很好的结 合，还没于得到充分的应用。 1 3 本文工作 利用统计学方法实现文本分类具有速度快、实现简单等特点，且分类准确度 也较高，能够满足一般应用的要求。基于统计的分类方法具有如下特点：忽略文 本的语言学结构，把文本作为特征项集合对待，使用训练样本进行特征选择和分 类器训练，根据选择的特征形式化待分类的输入文本，然后输入到分类器进行类 别判定，最终得到输入文本的类别，这种方法实现简单，分类准确度也较高。 本文介绍了文本表示、文本分词、特征提取、分类算法和分类评估标准等与 文本分类相关的技术。文本分词是文本分类的基础，并在此分词的基础上提出了 关键词集抽取的算法，实验验证了其可行性。在文本分类中，在分析文本特征以 及现有文本分类方法的基础上，应用信息熵理论，提出了一种文本分类的新方法。 该方法利用熵来度量新文本对于已分类文本集合贡献的大小，并以此熵值来判断 文本归属的类，最后设计并验证了基于熵的文本分类模型。实验结果表明基于熵 的文本分类模型的性能较改进前更加令人满意，证明了算法的有效性。 4 西北师范大学硕士学位论文第章绪论 1 4 本文课题来源和内容组织 1 4 1 本文课题来源 本文研究来源于甘肃省自然科学基金( 3 z s 0 5 1 一a 2 5 0 4 7 ) 。 i 4 2 本文内容组织 全文共分六章，各章主要内容如下： 第一章：介绍了本文的研究背景和选题意义，对文本分类系统进行了概述， 对本领域国内外的研究现状作了简要介绍，给出了本文的研究工作 和组织结构。 第二章：讨论了分类系统的总体结构，对文本分类系统的关键技术作简要介 绍，包括文本表示模型、分词方法、文本特征选择、文本分类方法、 分类效果评价等。 第三章：介绍几个信息理论基本概念，讨论如何应用信息理论度量来衡量数 据内在的规律性，并利用信息度量工具改进特征选择模型和分类模 型的设计，并对其性能进行评估。 第四章：介绍了中文文本分词方法，在分词后的基础上提出了关键词集抽取 的算法。主要是从一些频率较高的词开始，根据每个词的前后词找 出相互关联的词组或短语，最终构成一组关键词集。 第五章：基于信息熵的文本分类系统的设计和实现。通过分析文本的特征以 及常用的文本分类方法，提出了一种将信息熵运用到文本分类中的 新方法，该方法利用熵来度量新文本对于文本集合的贡献的大小， 以此来决定该文本是在文本集合内还是排除在外的依据。 第六章：对本文的工作作了总结，并指出了需要进一步研究的工作。 西北师范大学硕士学位论文第二章文本分类概述 第二章文本分类概述 这一部分对文本分类的基本概念、任务和面临的困难进行了介绍，阐述了文 本表示模型的建立方法。对文本分类中的关键技术一特征选择和文本分类算法 进行了讨论，比较了不同文本特征项对分类系统的影响，分析了分类性能评估指 标对衡量分类其性能所起的作用。 2 1 文本分类的基本概念 2 1 1 文本分类问题描述 文本分类就是在给定的分类体系下，由计算机根据待分类文本的内容自动确 定文本类别的过程。分类体系一般由人工构造，著名的分类体系如r e u t e r s 分类 体系，中图分类体系，中国大百科全书学科分类体系等。分类体系可以采用 层次关系构造，也可以采用同级关系构造。 文本分类是一个映射过程，它将未标明类别的文本映射到已有的类别中，该 映射可以是一一映射，也可以是一对多的映射，因为通常一篇文本可以同多个类 别相关联，数学公式表示如下： ，：4 一口，其中，a 为待分类的文本集合，口为分类体系中的类别集合。 ( 2 1 ) 文本分类系统的决策函数厂取决于分类器的学习方法，不同的学习方法产生 不同的决策函数。解决此类问题的一种策略是让计算机从样例中学习输入到输出 的函数对应关系，这种使用样例来合成计算机程序的过程称为学习方法，其中当 样例是由输入输出对给出时，称为监督学习；若数据不包含输出值，学习的任 务是理解数据产生的过程，则称为非监督学习。因此文本的类别和数量可以是预 先预定的，也可以是不确定的。 2 1 2 文本分类的技术路线 根据分类知识获取方法不同，文本分类主要有两种技术路线，一是基于知 识工程的分类系统，一是基于统计学习的分类系统。 知识工程是源于专家系统建造而形成的一个研究领域，目前已经形成一个跨 学科的领域，涵盖自然语言理解、逻辑与推理、形象思维研究等领域。知识工程 6 西北师范大学碛士学位论文第二章文奉分类概述 的方法主要是依赖语言学知识，需要编辑大量的推理规则，分类系统实现上较为 复杂，开发成本较高，并不适用于复杂的系统。统计学习方法的实质是利用统计 概率原理，采用计算机自动学习的方法，通过对已知样本的自动学习，建立特征 体系，并实现对未知样本的预测。统计学习方法由于其实现简单，分类性能良好， 生成结果迅速，能够满足一般应用等优点，而被大多数分类系统采用，成为了文 本分类的主流技术。本文研究的分类即是基于统计学习的技术线路。 文本分类系统建立过程如下： ( 1 ) 将训练语料库进行分词，得到文本特征全集。 ( 2 ) 通过特征选择评估函数，对文本特征全集进行特征选择，形成特征向量。 ( 3 ) 采用分类算法，学习训练语料库中的文本分类规则和信息，进行分类器 构造。 ( 4 ) 利用训练语料库中的文本对分类器进行训练，得到分类器的相关参数。 ( 5 ) 利用测试语料库对分类系统进行测试，考察分类性能评估指标，如果指 标符合精度要求，则将该分类系统投入使用，否则，重新构造分类器或 重新设计分类系统。 2 2 文本表示模型 2 2 1 文本表示方法 中文具有多种表达方式和复杂的语法，若不对文本表达进行转换，机械的计 算机是很难对其理解和处理的。文本表示是为了自动抽取出能够表达文本内容的 词汇，常用的文本表示方法有三种： ( 1 ) 句法分析法。句法分析法是通过应用句法分析程序，筛选出合乎一定 过滤规则的词条。句法分析法的标引结果大多数为有意义的名词短语。 为了保证词条语义的完整性，通常需要借助词典和语料库，否则程序的 分析结果往往是合乎句法的句子而不是词。句法分析法比较复杂，应用 实例较为少见。 ( 2 ) 词库匹配法。词库匹配法是将输入文本与词库中的词汇进行匹配，以便 将文本中被词库收录的词条按照分词匹配方法被抽取出来，抽取出来的 词条就是文本的关键词。词库匹配法虽然能够保证每个关键词在语义上 都是完整的，但是并不能保证文献中所有的关键词都能被抽取出来，也 7 西北师箍大学硕士学位论文第二章文本分类概述 不能保证抽取出来的关键词就是文献真正的关键词。 ( 3 ) 词频统计法。词频统计法是中文文本分类中最常用的文本表示方法，具 体实现包括两个步骤，一是进行分词，将文本转化为只包含能够表达文 本内容的词汇；二是词汇权重计算，以此反映词汇对表达文本内容所起 的作用。本文所涉及的文本分类系统的文本表示采用的是词频统计法。 2 2 2 向量空间模型 要正确地执行文本分类的任务，首先要将文本的有用信息输入计算机中，为 此应对文本进行科学的抽象，建立它的数学模型，用以描述和替代文本。用简单 而准确的方法将文档表示成计算机能够处理的形式是进行文本分类的基础。目 前，在信息处理方向上，具有代表性的有布尔模型( b o o l e a nm o d e l ) 、向量空间 模型”1 ( v e c t o rs p a c em o d e l ) 、概率模型( p r o b a b i l i s t i cm o d e l ) 等。在以上几 种模型中，应用效果较好的是向量空问模型，该模型是由g s a l t o n 于6 0 年代 末提出的，首先在s m a r t 系统中得到了成功的应用，现在被广泛应用于文本信息 处理领域。 在该模型中，每一对象模型化为空间中的点，两对象间的差异由多维空间中 两点间的距离表示。向量空间模型的基本思想是以向量来表示文本： ( w l ，w 2 ，) ，其中嵋为第f 个特征项的权重，一般选择字、词或词组作为特征 项。根据实验结果，普遍认为选取词作为特征项要优于字和词组，因此，要将文 本表示为向量空间中的一个向量，就首先要将文本分词，由这些词作为向量的维 数来表示文本，最初的向量表示完全是0 、1 形式，即，如本中出现了该词，那 么文本向量的维数为1 ，否则为0 。这种方法无法体现这个词在文本中的作用程 度，所以逐渐0 、1 被更精确的词频代替。词频有绝对词频和相对词频之分，绝 对词频，即使用词在文本中出现的频率表示文本；相对词频为归一化的词频，这 样以来，文档信息的表示与匹配问题就转化成为空间向量的表示与匹配问题”1 。 其计算方法主要运用t f - i d f 公式，目前存在多种t f i d f “公式，比较普遍的 t f i d f 公式如下所示： 啡2 带揣器 ( 2 - 2 ) 其中，电，d ) 是词t 在文本d 中的权重，矿( f ，d ) 是词t 在文本d 中的词频， 西北师范大学硕士学位论文第二章文本分类概述 为训练文本的总数，n ，为训练文本集中出现f 的文本数，为降低高频特征对低频 特征的过分抑制，在实验中计算权值时对t f - i d f 值要进行归一化处理，分母为 归一化因子。文本经过分词程序分词后，合并数字和人名等词汇，然后统计词频， 最终表示为上面描述的文本向量。 t j 向量空间模型的最大优点在于它将文本以向量的形式映射到实数域中，把对 文本内容的处理简化为向量空间中的向量运算，使问题的复杂性大为降低，向量 空问模型的优点在于： 1 特征项权重的算法提高了检索的性能； 2 部分匹配的策略使得过滤得到的结果文本集合更接近用户的查询需求： 3 根据结果文本对于查询串的相似度通过余弦公式对结果文本进行排序。 该模型的缺点是不考虑特征词条问的语义关系，常常导致分类的精度不够 高。 2 3 分词方法 分词是将连续的字串或序列按照一定的规范重新组合成词序列的过程。众所 周知，在英文中，单词之间以空格作为自然分界符，不需要进行分词处理。中文 的最小单位是字，而在中文信息处理的诸多重要领域如文本分类、篇章理解、文 本检索与自动标引等都需要在词的基础上进行处理。词是中文中能独立活动的、 有语义的基本语言单元，只有当由单个汉字组成的句子转化成词之后，才能进行 概念抽取，以至于自然语言理解。但是中文文本中字与字之间、词与词之间并没 有明显的切分标志，需要使用中文分词技术，让计算机自动地把中文中的词与词 之间的分界线找出来。因此，中文分词技术是中文信息处理技术的基础。 9 西北师范大学硕士学位论文第二章文本分类概述 常用的分词方法主要有0 2 1 “：基于字符串匹配的分词方法、基于统计的分词 方法、专家系统分词方法和神经网络分词方法。 2 3 1 基于字符串匹配的分词方法 这种方法又叫做机械分词方法，也叫做基于词典的分词方法，主要思想是： 事先建立一个词典，对待切分的字符串，按照己经确定的策略，与词典中的词汇 进行匹配，若在词典中找到某个字符串，则匹配成功，即识别出一个词，否则继 续下一步的匹配，直到所有汉字串都被成功地切分出来。 基于字符串匹配方法的优点是：方法简单，程序容易实现，开发周期短，实 用性强。该方法的缺点是：受词典的影响较大，处理歧义的能力较差。 2 3 2 基于统计的分词方法 从中文的形式上看，词是由稳定的字组合而成的，因此在上下文中，相邻的 汉字同时出现的次数越多，就越有可能是一个词。因此字与字相邻共现的频率能 够较好地反映是否为词的概率。当字符串的紧密程度高于某一个阈值时，便可认 为此字符串是一个词。这种方法只需对语料库中的字符串组合频率进行统计，不 需要事先建立词典，因而又叫做无词典分词方法。 基于统计的分词方法的优点是：提供了消歧的方式，处理自然语言具有很好 的一致性和健壮性。该方法的缺点是：低频词很难被切分出来，同时经常抽出一 些共现频度高、但并不是词的常用字组。 2 。3 3 专家系统分词方法 该方法从模拟人脑的功能出发，将分词过程看作是知识推理的过程。首先构 造推理网络，将分词所需的中文词法、句法、语义知识分离出来。该方法把知识 表示、知识库结构与维护作为关键技术，其中知识库按常识性知识和启发性知识 分别进行组织。对于常识性知识采用“语义网络”表示，对于启发性知识采用“产 生式规则”表示。每进行一步推理，既启动常识性知识库又启动启发性知识库， 对于非歧义字段使用一般语法知识，对歧义字段则使用与其歧义有关的语法知识 和语义知识。一个句子不管其中是否含有歧义字段，其切分过程都可归结为生成 该句子词语树的过程。这种统一的分词方法不仅使整个分词处理过程简明，也使 整个系统运行效率得到提高。 1 0 西北师范大学硬士学位论文第二章文本分类概述 专家系统的优点是知识库易于维护和管理，但对外界的信息变化不敏感，反 应缓慢，不能从经验中学习。 2 3 4 神经网络的分词方法 神经网络的分词方法，模拟人脑的运行进行分布处理。它需要建立计算模型， 将分词知识分散、隐式地存入神经网络内部，通过学习和训练改变内部的权值， 从而达到正确的分词效果。 它具有对外界变化敏感、反应迅速，且具有自学习、自组织的能力；缺点在 于需要大量的实例学习，对己有知识维护更新困难，网络模型表达复杂，训练时 间长。 2 4 文本特征选择 文本分类问题的最大特点和困难是特征空闻的高维性和文本表示向量的稀 疏性。在汉语处理中，通常采用词条作为最小的独立语义载体，原始的特征空间 由可能出现在文章中的全部词条构成。而一个中等规模的语料库就常常可以包含 数十万条不同的词，这样高维的特征空间对于几乎所有的分类算法来说都偏大。 在不降低分类器的准确性的前提下寻求一种自动高效的特征抽取方法，降低特征 空间的维数，提高分类器的效率，成为文本分类中需要面对的重要问题。 近年来在中文文本分类中经常采用的特征抽取“7 1 ”方法包括最简单的停用 词移除、互信息m i 、信息增益i g 等。特征抽取方法的选取主要依据y y a n g 的 实验结果“”。由于中文文本分类问题与英文文本分类相比具有相当大的差别，体 现在原始特征空间的维数更大，文章表示更加稀疏，词性变化更加灵活等多个方 面。因此，在英文文本分类中表现良好的特征抽取方法未必适合中文文本分类。 对中文文本分类中的特征抽取方法进行系统的比较研究显得十分重要。 特征选择”的主要方法是利用相关数学公式计算来降低原始文本向量的 维数，用含有分类信息较多的特征构成新的文本特征向量。目前国际上对文本特 征提取多数通过采用某种评估函数，计算特征属性的权重，然后对所有的特征按 照其权重大小进行排序，选取权重在一定数目或某个范围内的特征项集合作为文 本的特征子集。 近年来在中文文本分类中使用较多的特征选择方法包括词频方法( d o c u m e n t f 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 n ) ， 西北师范大学硕士学位论文第二章文本分类概述 交叉熵( e x p e c t e dc r o s se n t r o p y ) ，文本证据权( w e i g h to fe v i d e n c eo ft e x t ) 和c h i 统计方法。下面将分别介绍这几种特征选择方法。 2 4 1 词频方法 词频( d o c u m e n tf r e q u e n c y ，d f ) 是指语料库中出现某词汇的文本数目。这种 方法的原理是：低频词对分类的影响力较小，可以忽略不计，一般对分类影响较 大的是中频度词，这些词被认为是重要的词汇。该方法的具体步骤是计算训练集 中每个词的词频，并排除那些词频数小于预先规定好的阈值的词，保留对分类有 一定影响力的词。 d f 方法是最简单的降维方法，计算复杂度低，随着训练集的增加而线性增 加，适合于大规模的语料库。但是有的频率较低的词汇集中出现在某一类别中， 也可能包含重要的信息，只是简单的除去，可能会影响分类的准确率，常用作辅 助特征选择方法。 2 4 2 信息增益方法 信息增益( i n f o r m n t i o ng a i n ，i g ) 指一个词汇为整个分类所能提供的信息 量，该方法通过统计词汇在一篇文本中出现或不出现的概率来决定是否被选取为 特征向量。 词汇t 的i g 评价函数为： 佑( f ) 。p ( c ，) l o g p ( c ) + p ( t ) j 善p ( c j t ) l o g p ( c j7 f ) + p ( t ) 荟p ( c j t ) l o g p ( c j t ) ( 2 3 ) 词汇的信息增益值越大，其在某个类别上分布越集中，被选取的可能性越大。 计算总体特征提取的时间复杂度为o ( m k ) 。假设每个特征词最多在个训练文 档中出现，空间复杂度为o ( m n ) 。 2 4 3 互信息方法 互n , g ( m u t u a li n f o r m a t i o n ) 方法根据某个词汇f 和类别c ；之间的共现程度 来衡量词汇和类别之问的相关性。 词汇t 的m i 评价函数为： 西北师范大学硕士学位论文第二章文本分类概述 m o , c j ) = l o g 等】 f 和c 相互独立时，两者的互信息为0 。m i 值越大， 程度越高，被选取的可能性越大。 ( 2 - 4 ) 类别和词汇之间的相关 用互信息方法提取的时间复杂度为o ( m k ) ( k 为类别数，m 为特征词的总 数) ，与信息增益方法相同。 2 4 4 交叉熵方法 交叉熵( e x p e c t e dc r o s se n t r o p y ，c e ) 方法中词汇t 的c e 评价函数为： c e 卅菱。pc c 巾ms 【并考】 s ， 交叉熵方法的原理与信息增益方法相同，唯一的不同之处在于：信息增益方 法考虑了词汇在文本中发生和不发生的两种情况，而交叉熵方法只考虑词汇在文 本中发生一种情况。这些不出现的词汇一般是噪声的来源，因此期望交叉熵比信 息增益要优越一些。 2 4 5 文本证据权方法 文本证据权( w e i g h to fe v i d e n c eo ft e x t ，w e t ) 方法中词汇t 的w e t 评价 函数为： wet ( t ) - 即漉小s 等昔渊i 浯6 ， 文本证据权方法的值反映的是类概率与在给定某一特征之下的类概率的差 别，它只考虑词汇t 在文本中出现的情况。 2 4 6c h i 统计方法 c h i 统计方法计算词汇f 和文档类别q 之间的相关程度，并假设f 和q 之间 符合具有一阶自由度的z2 分布。词汇对于某类的z2 统计值越高，它与该类之 间的相关性越大，具有的类别信息也越多。 令4 表示属于c 类且包含f 的文档频数，b 表示不属于c 类但是包含f 的文 档频数，c 表示属于c j 类但是不包含f 的文档频数，d 是既不属于c j 类也不包 西北师范大学硕士学位论文第二章文奉分类概述 含t 的文档频数。n t 对于c ；类的c h i 值由公式来计算： 石2 ( t , c j ，- 面荫篙舞署； 丽 ， 当词汇f 和类别c ；之间完全独立的时候，z2 统计量为零。z2 统计量和互 信息的差别在于它是归一化的统计量。 对于多类问题，分别计算t 对于每个类别c ；的c h i 值，它可以用以下两种标 准计算词汇t 对于整个训练集的c h i 值： z 二。( f ) = ：1 p ( c ，) z 2 ( f ，cj ) ( 2 8 ) 石：。( t ) 一m a x ：。1z2 ( t ，c ，) ( 2 - 9 ) 其中k 为类别数。从原始特征空间中去掉低于指定阙值的词汇，保留高于该 阈值的词汇，让它们作为表示文本的特征向量。 c h i 方法的计算复杂度与i g 方法的复杂度一样。 不同的特征选择算法会得到不同的词条来形成特征空间，可能产生不同的文 本分类结果。目前尚无理论表明哪种特征选择方法适用于某种文本分类算法，而 且即使是同一种特征选择方法和文本分类算法，在用于不同语料库时也会产生不 同的分类结果。 2 5 文本分类方法 文本向量经过降维处理之后，就可以使用这些特征向量来表示文本。文本分 类方法需要一个类别已标识的文本数据集来训练分类器，然后用训练好的分类器 对未标识类别的文本进行分类。文本分类方法通过构造某种分类模型( 也称为分 类器) ，并以此判断样本所属的类别。分类器的构造方法有许多种。删，常用的 分类算法有如下几种： 2 5 1 贝叶斯方法 贝叶斯方法( b a y e sm e t h o d ，b m ) 在机器学习领域中应用很广泛。贝叶斯算法 的主要思想是基于贝叶斯假设，即文本中的词汇在确定文本类别的作用上相互独 立，它首先计算特征词属于每个类别的先验概率，在新文本到达时，根据特征词 的先验概率计算该文本属于每一个类别的后验概率，最后取后验概率最大的类别 作为分类结果。贝叶斯分类器由m a r o n 提出，将文章看作独立的单词集合，通 1 4 西北师藕大学硬士学位论文第二章文本分类概述 过训练集由贝叶斯理论得到每个单词在不同类的概率大小，构造出贝叶斯模型。 贝叶斯算法假设文本由混合模型产生，每个类别对应混合模型的一个分量。 贝叶斯定理：设x 是类标号未知的数据样本。设h 为某种假定，如数据样本 x 属于某特定的类c 。对于分类问题，我们希望能确定p ( h i z ) ( 给定观测数据样 本x ，假定h 成立的概率) 。p ( h l x ) 是后验概率，条件x 下h 的后验概率。贝叶斯 定理是： p ( _ lix ) ；巫盟磐掣 ( 2 砌) p 【工j 其中，p i ) 是条件h 下，x 的后验概率。p o ) 是样本具有某些属性值的概 率，e ( h 1 是h 的概率。 具体步骤如下： 第一步：计算特征词属于每个类别的概率向量( w ，w ：，w ) ，其中， wt - p ( v r tic ，) 一 p ( 矽。i c ，) 为词形。在类别c ，中出现的比重，i d i 为该类别的训练文档数， n ( 矽i ，d ；) 为词形i 在d ；中的词频，i y l 为总词条数， 芝：! 。：= ：( 。，d i ) 为类别c ，所有词的词频之和。 第二步：在新文本到达时，根据特征词分词，然后按下面的公式计算该文本 d ，属于类c ，的概率。 p ( cjl d , ；一o ) - 蘸器胬群等器 其中，p ( c ，l e ) 暑盏淼，i 劢为相似含义，| c i 为类别的总数， ( 矿。，d ；) 为。在d 。中的词频。 第三步：比较新文本属于所有类的概率，将文本分到概率最大的那个类别中。 k 一近邻方法( k n e a r e s tn e i g h b o r ，k - n n ) 是由c o v e r 和h a r t 于1 9 6 8 年 提出的啪3 ，直至现在仍在很多领域中应用。k 一近邻方法是一种基于统计的分类 西北师范大学硕士学位论文第二章文本分类概述 方法o ”。 该算法的基本思想是：在给定新文本后，考虑在训练文本集中与该新文本距 离最近( 最相似) 的k 篇文本，根据这k 篇文本所属的类别判定新文本所属的 类别，具体的算法步骤如下： 第一步：根据特征项集合重新描述训练文本向量； 第二步：在新文本到达后，根据特征词分词新文本，确定新文本的向量表示； 第三步：在训练文本集中选出与新文本最相似的k 个文本，计算公式为： s i m ( d f ，d ，) - ( 2 1 1 ) 其中，k 值的确定目前没有很好的方法，一般先定一个初始值，然后根据试 验测试的结果调整k 值，一般初始值定在几百到几千之间。 第四步：在新文本的k 个邻居中，依次计算每类的权重，计算公式如下： p ( x ，c ，) i j i m ( 工，d t ) y ( d ，c ，) ( 2 1 2 ) d f e k n n 其中，x 为新文本的特征向量，s i r a ( 石，d ，) 为相似度计算公式，与上步 骤的计算公式相同，而y ( d 。，c ，) 为类别属性函数，即如果d 。属于类c ，那么 函数值为l ，否则为零。 第五步：比较每类