（计算机应用技术专业论文）词间语义关系的研究及其在文本分类中的应用.pdf

中文摘要 自动文本分类是信息检索领域的基本任务之一。随着互联网上的信息量呈爆 炸性增长，人们很难从大量的文本信息中迅速有效地提取出所需信息。为了解决 信息迷向的现象，对文本分类的研究显得越来越重要。 本文设计并实现了基于模块化的可扩展自动文本分类系统。对分类过程中的 各重要环节进行了细致全面的研究和分析。在此基础上我们提出了将自然语言处 理领域中的词语语义关系挖掘模型与文本分类系统相结合的方法，目的在于解决 目前向量空间模型中词语相互独立这一基本假设的不合理性。同时期望通过利用 文本中词语问的深层内涵，在较小的向量空间内表示更加丰富的文档信息，并以 此提高文本分类的测试效果。 语义关系挖掘模型利用语言学的句法分析和信息学的统计思想，通过对文本 语料的深层挖掘，得到词条间网状语义关系词典。该词典资源丰富了文本的向量 信息，使得向量表示更加高效简洁。我们把该模型与强大的s v m 分类器模型结 合在一起，显著提升了分类系统的结果。 在实验中我们将该模型与标准的词袋模型在2 0 n g 和r e u t e r s 测试语料上进 行比较。结果表明语义关系扩展可以明显改进文本分类的准确率和召回率。而且 还可以在保证分类结果的同时，有效地降低计算的空间和时间复杂度，使得对超 大规模文本语料的分析成为可能。最后，作者提出了语义关系挖掘模型在信息检 索领域中未来的研究方向。 关键词；文本分类语义关系向量空间模型依存模型句法分析 a b s t r a c t t e x tc a t e g o r i z a t i o n1 so n eo ft h eb a s i ct a s k si ni n f o r m a t i o nr e t r i e v a l w i t ht h e e x p l o s i v eg r o w t ho fw e bi n f o r m a t i o n , p e o p l eh a v ed i f f i c u l t yi nf i n d i n gt h er e q u i r e d i n f o r m a t i o nf r o mm a s s i v ei n f o r m a t i o n i no r d e rt os o l v et h es oc a l l e d i n f o r m a t i 0 1 1 c o n f u s i o n p r o b l e m , r e s e a r c ho nt e x tc a t e g o r i z a t i o ng r e d u a n ys e e m e dt ob e1 1 1 0 1 0 i m p o r t a n t t h i sp a p e rd e s i g na n di m p l c m a n tam o d u l e - b a s e ds c a l a b l ea u t o m a t e dt e x t c a t e g o r i z a t i o nf i 恤n e w o r k w ea l s od i dac o m p r e h e n s i v es u r v e yo ne a c hi m p o r t a n t s t e pi nt h ef r a m e w o r k b a s e do nt h i sf i a m e w o 咄w eb r i n gu pam e t h o dt h a t i n t e g r a t i n gt h et e r ms e m a n t i cr e l a t i o n s h i pi n t oc l a s s i ct e x tc a t e g o r i z a t i o nt a s k t h i s m e t h o d ns o l v et h ei n h e r e n ti r r a t i o n a l i t yi nt h ea s s u m p t i o no fv e c t o rs p a c em o d e l t h a tt e r m sa r et r e a t e di n d e p e n d e n t l y m e a n w h i l ew es h o wt h a tt h ed c e pa s s o c i a t i o n b e t w e e nt e r m sc a nb eu s e dt oi m p r o v et h er e s u l to f o u rc u r r e n te x p e r i m e n t t e r ms e m a n t i cr e l a t i o n s h i pc 强b eo b t a i n e db yu s i n gs e n t e n c ep a r s i n gi nn a t u r a l l a n g u a g ep r o c e s s i n ga n ds t a t i s t i c a lm e t h o di ni n f o r m a t i o nt h e o r y w ep r e s a n t e dt h e d e e pt c n nr e l a t i o n s h i pi nt h ef o r mo ft h e s a u r u sw h i c hc a nm a k et h ed o c u m e n tv c c r y f m o r ei n f o r m a t i v ea n de f f e c t i v e w h e nc o m b i n e dw i t ht h ec l a s s i f i c a t i o np o w e ro f s v m ，t h i sm e t h o dy i e l d sh i g hp e r f o r m a n c e i nt e x tc a t e g o r i z a t i o n 。 w ec o m p a r et h i s t e c h n i q u ew i t hs v m - b a s e dc a t e g o t i z a t i o na n do t h e rt e r m r e l a t i o n s h i pm o d e lo n2 0 n ga n dr e u t e r s 2 1 5 7 8d a t a s e tu s i n gt h es i m p l em i n d e d b a g - o f - w o r d s ( b o w ) r e p r e s e n t a t i o n t h ec o m p a r i s o ns h o w st h a t o u rm e t h o d o u t p e r f o r m so t h e r sm o d e li nm o s tc a s 懿 f i n a l l y , w eb r i n go u ts o m ef u t u r er e s e a r c ho nu s i n gt e r ms e m a n t i cr e l a t i o n s h i pi n i n f o r m a t i r e t r i e v a la r e a k e y w o r d s ：t e x tc a t e g o r i z a t i o n , t e r ms e m a n t i cr e l a t i o n s h i p ，v e c t o rs p a c em o d e l ， d e p e n d e n c ym o d e l ，p a r s i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫鲞盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名书也磐签字吼砷易年二月矽日 学位论文版权使用授权书 本学位论文作者完全了解鑫鲞盘堂有关保留、使用学位论文的规定。 特授权鑫鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：书眈努 签字日期：翮年2 ，月句日 导师签名： ) 呵璃 签字日期：力诌年2 月矽日 天津大学硕士学位论文第一章绪论 1 1 选题背景 第一章绪论 随着i n t e r n e t 的飞速发展以及企业内部网的日益普及，网上的可用信息不 断增加。在这些海量、异构的w e b 信息资源中，蕴含着具有巨大潜在价值的知识。 人们迫切的需要能够有效地查找、过滤和管理这些资源的工具。这些工具包括搜 索引擎( 通过基于关键字的查询来搜索网页) 、分类结构树( 像y a h o o 2 3 、 l o o k s m a r t 2 4 那样把网页放入一个分级集合中) 等。t h e n 和d u m a i s 在2 0 0 0 年 的一个研究表明用户更喜欢通过分类结构树来浏览网页 2 5 。但是这些分类是由 大量的编辑手工完成的。然而随着网上资源的迅猛发展，手工维护这样的分类结 构日趋困难，甚至成为一件不现实的事情。如果计算机能够在信息的辨识和处理 方面，对用户提供适当的支持和帮助，那将能够极大地改善目前用户面临的困境 和提高信息使用效率。自动网页分类技术对于解决这些问题提供了一种有效的方 法，因此成为近几年研究的热点。 文本分类是将一篇自由文档根据其内容信息标记上一个或多个预先定义的 类别标签的过程 1 2 。这样，用户不但能够方便的浏览文档，而且可以通过限 制搜索范围来使文档的查找更为容易。作为一个被广为关注的课题，这项技术既 有潜在的市场应用价值，又具有相当的技术难度。它是信息管理和自然语言处理 任务的重要组成部分：包括对电子邮件和文件实时地层次分类；主题识别研究以 支持题材相关的处理操作；结构化的搜索和浏览；搜索与特定的长期个人兴趣相 关的文档等。 虽然文本分类技术从2 0 世纪6 0 年代开始已经得到了深入的研究和长足的发 展，但由于分词、词性标注和句法分析等自然语言处理领域的核心任务研究相对 滞后，导致针对文本分类的研究绝大多数探索都限制在对于分类器的创新与改进 方面。而对文本信息本身的深入挖掘和处理则没有突破性的进展。 1 2 文本分类研究现状 自动文本分类的概念提出于2 0 世纪6 0 年代，到现在已经经历了很长的研究 天津大学硕士学位论文第一章绪论 阶段。直到2 0 世纪8 0 年代文本分类任务主要依靠知识工程理论，根据专家知识 库通过建立一系列规则实现自动化的目的。进入9 0 年代后，随着网络上的多元 化信息不断增加，一种基于机器学习的统计方法逐渐超越了原有体系并成为文本 分类的主导技术 3 4 3 。该方法是一种通用的归纳过程，通过对预先分类好的一 组训练文档集合的学习，自动地生成分类器对未知文档进行处理。这个过程是与 知识领域无关的，可以省去大量的人力劳动，使分类过程更加高效。 1 2 1 国际研究概况 国际上在文本分类技术以及相关的信息检索、信息抽取等领域起步较早，进 行了较为深入的研究，并开发了一系列可用的分类系统，例如分别针对新闻稿件、 网页和电子邮件的自动文本分类器等。至今已在信息处理的很多领域取得突破性 进展，并为文本分类效果的不断提升奠定了基础： 1 ) 文档信息表示模型 s a l t o n 等人在6 0 年代末提出的向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 4 3 在文本分类、自动索引、信息检索等许多领域得到了广泛的应用，已成为最 简便高效的文本表示模型之一，并且被很多商业搜索引擎采用。 随着自然语言处理研究的不断深入，概率语言模型( p r o b a b i l i s t i cl a n g u a g e m o d e l ，p l m ) 也被逐渐应用到索引技术、信息检索领域 5 6 。这种概率形式的 模型在文本检索应用中显示出了很有潜力的结果 7 8 。 2 ) 特征选择方法 在使用向量空间模型表示文本信息时，为了降低向量维度和计算时间复杂 度，通常采用特征选择的方法对文本中的词条进行筛选，从而过滤掉充当句法成 分的无意义词条，以及信息区分能力弱的词条。国际上已经提出多种行之有效的 基于信息学和统计学的方法，并进行了深入的调研和比较，总结出每种方案的适 用范围和效果 9 1 0 。这些方法包括：文档频率( d o c u m e n tf r e q u e n c y ，d f ) 、 信息增益( i n f o r m a t i o ng a i n ，i g ) 、互信息( m u t u a li n f o r m a t i o n ，m i ) 、z 2 统 计分布( z 2 一s t a t i s t i c s ，c h i ) 、期望交叉熵( e x p e c t e dc r o s se n t r o p y ) 以及词 条强度( t e r ms t r e n g t h ，t s ) 等。 天津大学硕士学位论文 第一章绪论 3 ) 文本分类方法 随着网络上越来越多的文字信息的出现，如果没有高效的索引和文档信息摘 要功能作为基础，很难实现有效的检索目的。同时网络上大量可用的文字信息也 为基于统计和机器学习技术的分类器提供了丰富的资源。近些年，很多理论技术 被应用到该领域，包括：朴素贝叶斯( n a i v eb a y e s ，n b ) 1 4 、支持向量机( s u p p o r t v e c t o rm a c h i n e ，s ) 1 5 2 9 、k - 近邻( kn e a r e s tn e i g h b o r ，k n n ) 1 6 1 7 、 神经网络模型( n e u r a ln e t w o r k ，n n ) 1 8 3 1 9 2 0 、决策树模型( d e c i s i o nt r e e ， d t ) 1 3 、最大熵模型( m a x i m u me n t r o p y ，m e ) 3 5 以及线性最小平方拟合( l i n e a r l e a s ts q u a r e sf i t ，l l s f ) 2 1 。y a n g 对这些文本分类的方法进行了全面的显 著性测试，得出了各种方法的性能比较结果以及适用范围 2 2 。 4 ) 测试语料库及评测方法 国际上对于英文文本分类语料，制定了一些规则完善、标准统一的语料集， 包括：2 0 n e w s g r o u p s 语料库( 约2 0 ，0 0 0 多篇文章2 0 个类别) ，w e b k b 语料库( 4 。1 9 9 篇文章7 个类别) ，r e u t e r s 系列语料库( 2 1 ，5 7 8 篇文章1 3 5 个类别) 都曾较为 广泛地使用，而且t r e c 也提供了较为标准的语料库。特别是r e u t e r s - 2 1 5 7 8 已 经成为目前分类系统的评测基准。 在系统性能评测方面，除了标准的指标。l e w i s 给出了一套较完整的分析方 法 2 6 ，不但可以测试系统的整体性能，而且可以较科学地分析训练文本充足的 类别和训练文本不足的类别的分类性能差异。 5 ) 语义概念的研究 近些年，随着自然语言处理在词性标注、词义消歧和句法分析等方面都得到 了快速的发展。人们开始把对语言更高层次的理解和挖掘应用到信息检索相关的 诸多领域。出现了以计算理论为基础的基于矩阵分析的潜在语义分析方法 ( l a t e n ts e m a n t i ca n a l y s i s ，l s a ) 1 1 3 ，还有基于统计的分析方法。通过挖 掘大量文本语料中词条的共现关系，提取出分布语义词典，并将该词典资源用于 文本分类的语义概念模型 2 7 2 8 。另外基于词聚类 5 0 的方法目前也已经得到 许多研究者的认可。这些方法使人们对于文本信息处理不再停留在单词的出现频 率上，而是将单词出现时所处的上下文信息充分地利用。 天津大学硕士学位论文第一章绪论 6 ) 前景与应用 除了在自然语言处理方面的深入研究，国外研究人员在机器学习方面也力求 新的突破：由于训练语料需要人工的标注，时间和人力成本较高，所以很难大批 量的提供给学习模块。因此人们开始研究半监督( s e m i s u p e r v i s e d ) 模式下的 机器学习方法 3 0 3 1 ，有机地将文本分类和聚类结合起来。 文本分类已经是一项较成熟的技术，目前已被用于搜索引擎和网络服务的个 性化处理等领域。 1 2 2 国内研究概况 国内对于中文文本分类的研究虽然起步较晚，但是发展迅猛。特别是随着中 文信息处理的关键技术中文分词技术的准确率不断提升，使得大规模的中文 文本处理成为可能。但由于至今尚无标准的用于文本分类的中文语料库，各个研 究者收集自己的训练文本集，并在此基础上开展研究，因此系统的性能可比性不 强 3 2 3 3 。同时，由于财力人力有限，中文语料库的规模普遍不大。 另一方面，由于汉语言在词义、句法和语法等概念上与英文相比存在较大差 异，这就要求我们在分析和处理文本时，要充分考虑词义消歧和词间语义概念对 分类系统的影响 3 4 。而后者正是作者未来在中文分类领域的研究方向。 1 3 本文的研究课题 本文提出了一种基于句法分析的依存模型，该模型通过对大规模的语料进行 深度语义挖掘，获得词条间的网状语义关系。本实验的创新之处就在于将该语义 关系与文本分类问题的有效结合。实验表明依存模型可以显著改进分类效果，并 可以降低文档向量表示的维度空间。本文所涉及的研究方向包括： 1 ) 设计并实现了基于向量空间模型的自动文本分类系统 本文设计了一个可扩展的自动文本分类系统，该系统采用基于k n n 和s v m 的 分类器模型，自主实现除中文分词1 以及s 。以外的分类过程的全部模块，包括： 文本预处理模块、特征选择模块，k n n 分类器模块以及评测模块等。在此基础上 ：分词模块采用天津市海量科技发展有限公司提供的海量智能分词研究版。w w w h y l a n d a c o m 。支持向量机模块采用t h o r s w nj c h i m 提供的s v m - “曲tv 3 5 0 版本。h t t p ：s v m h g h t j o a c h i m s o r g 天津大学硕士学位论文第一章绪论 为进一步的研究搭建了实验平台。 2 ) 文本特征向量选择方法的性能比较 由于本文的研究重心为词条间语义关系，因此在系统中我们实现了多种词条 特征选择的方法，并得出实验对比结果。最后利用效果最好的一种特征选择方案 作为系统语义级扩展的基础。 3 ) 对目前流行的基于语义的词条关系挖掘方法进行全面的调研 本文所涉及的方法包括： 基于计算理论的潜在语义分析模型，该模型以矩阵分析为工具挖掘词条 所处的上下文信息模式，将提取出的隐含模式应用到原文本向量。 基于统计理论的分析模型，包括：词条共现模型，解决数据聚类问题的 信息瓶颈分布聚类框架，以及以句法成分分析为基础的统计依存模型等。 4 ) 提出了基于统计依存模型( d e p e n d e n c ym o d e l ) 的词间语义关系扩展和 文本分类系统相结合的模型，并在目前流行的语料库上进行了性能评测。 1 4 本文的组织结构 第一章为绪论，介绍文本分类课题的研究背景、研究价值以及文本分类课题 的研究现状，然后列出本文的核心研究工作。 第二章介绍自动文本分类方法，包括问题描述、任务、解决方案以及分类结 果的评价方法等，并在此基础上描述本课题涉及的文本分类系统的体系结构。 第三章详细介绍有关词条间语义关系模型的各种挖掘方法。包括基于计算理 论和统计理论的两大类方法。 第四章我们将介绍如何通过统计依存模型，得到词条语义关系，并将其应用 到文本分类系统中。随后我们给出实验结果分析。 第五章将总结本文的研究工作，规划语义关系和文本分类未来的研究方向。 天津大学硕士学位论文第二章自动文本分类系统 第二章自动文本分类系统 2 1 文本分类系统的问题描述 自动文本分类是数值分类学和信息处理技术相结合的研究方向。在最初的分 类学中，人们往往通过经验和专业知识对事物进行定性分析，很少使用数学工具。 随着信息的不断增长，信息之间的关系也日益复杂，从而导致分类程度越来越细， 分类规模也越来越大，这时仅仅依靠定性分析已经无法满足要求，于是人们在分 类过程中引入数学工具，使用统计、人工智能等各种方法处理信息，从而推动了 数值分类学( n u m e r i c a lt a x o n o m y ) 的形成，以及信息处理技术前进的步伐。 直到8 0 年代末，在文本分类方面占主导地位的一直是基于知识工程的分类 方法，即由专业人员手工编写分类规则进行分类，其中最著名的系统是为路透社 开发的c o n s t r u e 系统。9 0 年代以来，随着信息存储技术和通信技术的迅猛发展， 大量的文字信息开始以计算机可读的形式存在，而且其数量每天仍在急剧增加。 在这种情况下，基于机器学习的文本分类逐渐取代了基于知识工程的方法，成为 文本分类的主流技术。 文本分类系统任务是：在给定的分类体系下，根据文本的内容或属性，将大 量的自由文本标记上一个或多个类别标签的过程 1 2 3 。从数学角度来看，文本 分类是一个映射的过程，它将未标明类别的文本映射到已有的类别中，该映射可 以是一一映射，也可以是一对多的映射，因为通常一篇文本可以同多个类别相关 联。用数学公式表示如下： f ：一哼b 其中：4 = d l ，d 2 ，见，b = 翰，c 2 ，q ) ( 2 - 1 ) 即：a 为所有待分类的文本的集合；b 为给定分类体系下，所有类别的集合。 a 可以为无限集合，而b 必须为有限集合。 文本分类的映射规则，是文本分类系统的关键，它是系统根据训练集的样本 信息总结出的分类模式，作为判别公式或者规则。待遇到新文本时，根据总结出 的文本分类的映射规则，确定该文本所属的相关类别。 天津大学硕士学位论文第二章自动文本分类系统 2 2 文本分类系统流程 文本分类系统的流程如图2 - 1 所示：由文本预处理、特征选择、分类器训练 和测试评估四个主要模块构成一个循环体系。反馈机制根据系统在测试文本集上 的测试结果，启发性地调整特征选择方法和分类器训练的参数，使得分类器显示 更佳的分类效果。 图2 - 1 文本分类系统流程图 从该图可以看出，文本分类需要解决如下5 个问题： 1 ) 选取训练和测试文本集 2 ) 文本预处理过程 3 ) 特征选择方法 4 ) 分类器模型 5 ) 系统性能评测 2 2 1 文本集合的选取 选择适当的训练文本集对文本分类器的性能有较大影响。如果训练和测试文 本集的分布存在很大差异，就很难保证良好的分类结果，特别是对于训练样本很 少的情况 3 6 。因此训练文本集应该能够广泛代表分类系统所要处理的各个类别 中的文本。一般来说，训练文本集是公认的经人工分类和处理的语料库。而且各 个类别所包含的训练文本书应保持在数量上基本一致。这样训练得到的分类器不 天津大学硕士学位论文第二章自动文本分类系统 会对某些文档类产生估计偏差。 2 2 2 文本信息预处理 预处理模块是分类的基础部分。首先对中文文本进行分词处理，然后根据停 用词表过滤掉无用词，最后统计得到其它词条词频信息。该词频信息也将作为下 一步特征选择的输入参数。 词频统计过程与文档索引表示过程同时进行。在本文我们使用最常用的一种 文本表示方法一向量空间模型 4 3 7 。在该模型中文本被表示成为由词条构 成的向量形式。通常将一个文本集合表示成为“词条一文档”矩阵a 。矩阵中的 每一个元素表示某一词条在一篇文档中的出现情况。如： a=(ad(2-2) 表示词条i 在文档k 中的权值。由于所有的词条并不是均匀的出现在每个文档 中，因此矩阵a 往往是一个稀疏矩阵。矩阵的行数对应于词典中的词条数，而 矩阵的列数则对应于训练文本集。词条数有可能会非常大，所以特征空间庞大的 维度也是文本分类问题的一个特点和难题。下一部分将讨论几种降维方法。 决定词条i 在文档k 中的权值有很多方法，但它们都是基于两个文本分析 的经验原则： 词条在一篇文档中出现的频率越高，该词条与这篇文档的主题相关度越 强，称为权值计算的局部因素。 词条在整个文档集合中普遍出现的次数越高，该词条的文档区分能力越 弱，称为权值计算的全局因素。 基于这两条基本原则，本文给出权值计算的三种具体方案：首先我们定义肘 为在进行停用词处理后全部词条的总个数，是训练文档集合中所有文本的总个 数，五为词条i 在文本k 中出现的频率，n t 为词条i 在整个训练文档集合中的出 现频率。 1 ) t f i d f 权值 该方法是信息检索领域中最经典的一种词条权值计算方法 3 7 】。词条的权值 正比于它在文本中的出现频率- 1 甲，而反比例于它在整个文档集合中的出现 天津大学硕士学位论文第二章自动文本分类系统 频率d f 。i d f 算法的核心思想是，在大多数文档中都出现的特征项不如只 在小部分文档中出现的特征项重要。i d f 算法能够弱化一些在大多数文档中都出 现的高频特征项的重要程度，同时增强一些在小部分文档中出现的低频特征项的 重要度。 甜b g c 2 ) t f c 权值 由于t f i d f 方法没有考虑到不同文档的向量空间长度有可能不同，因此需 要对方法1 ) 中的结果进行规一化处理【3 8 】。 2 ( 2 - 4 ) 3 ) l t c 权值 该方法对2 ) 傲了进一步改进，对词频信息丘做了对数处理，从而降低了词 频差异大对分类效果的影响 3 9 1 。 2 ( 2 - 5 ) 这也是本文实现的文本分类系统中采纳的三种特征词的权值计算方法。 2 2 3 特征选择方法 目前的文本分类系统都采用词和词组作为表征文本信息的特征，文本特征的 提取一般通过对文本的多遍扫描实现，但是所得到的特征向量的维数往往很高， 这样就会增加信息处理的时间。因此在基本不影响分类结果的前提下，需进行特 征子集的选取，即特征选择。文本分类系统应该尽可能精简特征的数量，并选择 与文本主题密切相关的特征作为分类的依据。其方法一般是构造个评价函数， 对特征集中的特征进行评价，然后从中选取评价较高的一组特征作为特征子集。 天津大学硕士学位论文 第二章自动文本分类系统 常用的特征选择方法有基于阈值的统计方法，如文档频率方法( d f ) 、信息增益方 法( i g ) 、互信息方法( m i ) 、z 2 统计方法 9 】，期望交叉熵、文本证据权、优势率 4 1 】， 基于词频覆盖度的特征选择方法等，以及由原始的低级特征( 比如词) 经过某种变 换构建正交空间中的新特征的方法，如主分量分析的方法 4 2 】等。 对于特征词t ，各种特征选择标准的含义如下： 1 ) 文档频率( d o c u m e n tf r e q u e n c y ) 它表示包含特征词t 的文档的个数总和。我们统计每个特征词在训练文档集 合中的文档频率，并将那些文档频率小于预先定义的阈值的特征从特征空间中过 滤掉。这种方法的基本假设是稀有词汇或者对于类别预测不含有用信息，或者在 全局范围内不足以产生影响。这两种情况下，删除稀有词汇可以有效地降低特征 空间的维度。而且如果删除的稀有词汇是噪音，还可以改善分类系统的性能。 文档频率是特征选择最简单的一种技术。由于它的处理时间属于线性复杂 度，因此可以很容易扩展到大规模文本处理。文档频数的不足之处是某些低频词 可能在某一类文档中并不稀有，而且包含重要的分类信息。因此我们不能不加判 断的删除稀有词汇。 2 ) 信息增益( i n f o r m a t i o ng a i n ) 信息增益作为有效的评选特征的标准，在机器学习领域得到广泛的应用。它 描述了一个词在一篇文档中出现与否对于类别预测的信息比特数的贡献。令 c f ) ：。表示目标空间的类别集合，则词条f 的信息增益表示为： 佑( f ) = 一0 ( q ) l o g p ( c ，) + p ( f ) p ( qi t ) l o g p ，( c li t ) “1 。1(2-6) + e ( - ) 只( c i f ) l o g p , ( e , i _ ) j - 1 定义包含给定特征t ，类别的条件概率估计和熵值计算。它从所有类别的平 均角度出发衡量一个特征词的好坏。与文档频率类似，我们统计每个特征词在训 练文档集合中的信息增益，并将那些信息增益小于预先定义的阈值的特征词从特 征空间中过滤掉。 3 ) 互信息( m u t u a li n f o r m a t i o n ) 互信息通常用于词汇关联的统计语言模型。它表征了两个统计量间相互关联 天津大学硕士学位论文第二章自动文本分类系统 的程度，关联程度越高，互信息越大，反之亦然。列联表( c o n t i n g e n c yt a b l e ) 可以辅助我们进行分析理解。所谓列联表是一种用来显示两个变量数据资料中被 观察到的频率的统计表，其中横列表示一个变量，纵行表示另一个变量。如果我 们考虑由词条f 和类别c 构成的列联表，用a 表示t 和c 同时出现的次数，b 表 示t 出现c 不出现，c 表示c 出现t 不出现，n 表示所有的文档数。则t 与c 之间 的互信息标准定义为： 刖礼g 焉 c ， 它可以近似用下面的公式进行估计： ，o ，c ) l o g 两西a x 币n 丽 2 8 ) 很显然，如果t 与c 相互独立，则，o ，c ) 的值为零。为了在全局的特征空间 中对特征词进行选择，可以将上面的定义拆分成与类别相关的两种模式： ( f ) = p v ( f ，c f ) 扣1 ( 2 - 9 ) 。( f ) = m，q ) 互信息方法的缺点是它的取值很容易受到特征词条边缘概率强烈的影响。我 们可以将2 7 式改写成如下形式： ，( f ，c ) = l o g p ( f i o - l o g p ，( t ) ( 2 1 0 ) 从2 1 0 式可以看出对于条件概率相同的特征词，稀少的词条会比普通词汇 得到更高的分数。因此这很难在词频差异大的特征词之间进行比较。 4 ) z 2 统计( c h i ) 该方法表述了特征t 和类别c 之间的缺乏相互独立程度。如果用列联表表示 特征t 和类别c ，a 表示t 和c 同时出现的频率，b 表示f 出现c 不出现的次数， c 表示c 出现t 不出现的次数，d 表示t 和c 都不出现的频率，n 表示文档数量。 则特征词的好坏被定义为： z 2 ( f ，c ) = 面石硒y 雨, , ( a 丽d - 酉c m 丽2 而 2 - 1 1 ) 天津大学硕士学位论文 第二章自动文本分类系统 如果t 和c 相互独立则该统计值为零。首先我们计算每个特征词在训练文档 集合中针对每个类别得到的统计值，然后可以使用如下任意一种表示方法： z 2 。( f ) = p ( q ) z 2 ( f ，c f ) “1(2-12) z 2 。( f ) = t 毒品 z ：o ，q ) ) c h i 与m i 的不同之处在于z 2 统计得到的是归一化的值，因此它可以在同一 个类别中进行比较。但对于低频特征词其值交得不可信 4 3 1 。 6 ) 期望交叉熵( e x p e c t e dc r o s se n t r o p y ) 熵是信息学中的重要概念。在信息论中，信息被定义为对事物不确定性的消 除和减少。如果要衡量信息量的多少，就需要确定信息输入前后事物不确定性的 大小，熵( e n t r o p y ) 可以用来度量不确定性或复杂性的大小。期望交叉熵的形 式为： 喇姜讹ir ) l o g 锗 ( 2 - 1 3 ) t lr 、。， 其中e ( q i f ) 表示文本中出现特征项f 时，文本属于c f 的概率。如果特征项和类别 强相关，也就是只心i f ) 大，且相应的类别出现概率又小的话，则说明该特征项 对分类的影响很大，其对应的期望交叉熵值就大。期望交叉熵反映了文本类别的 概率分布和在出现了某个特征项的条件下文本类别的概率分布之间的距离，特征 项的期望交叉熵越大，对文本类别分布的影响也越大。 其他方法由于没有在本实验系统内实现，因此不再赘述。 特征选择对于粘着法构词的语言( a g g l u t i n a t i v el a n g u a g e s ，比如中文和 日文) 变得十分微妙。因为对于这类语言来说，单词识别任务本身并不是一件唾 手可得的技术。在文本经过分词模块或词性标注模块处理后得到的未知词中，既 包含有重要的关键词( 如人名，机构名等) ，同时也包含无意义词。如何有效地 选择这些未知词，成为中文分类系统的关键问题之一。 2 2 4 分类器模型 分类器的设计和实现是文本分类系统的核心。目前比较成熟的技术基本都属 天津大学硕士学位论文第二章自动文本分类系统 于统计学习理论的范畴。在机器学习领域，分类和回归都可用于预测。预测的目 的是从利用历史数据纪录中自动推导出对给定数据的推广模式描述，从而能对未 来数据进行预测。和回归方法不同的是，分类的输出是离散的类别值，而回归的 输出则是连续数值。不同的模型也决定了训练后得到的映射规则，的差异性。本 文将不讨论回归方法。 一般而言，机器学习是研究如何使用计算机来模拟人类学习活动的一门学 科。较为严格的提法是：机器学习是一门研究机器获取新知识和新技能，并识别 现有知识的学问。如何让机器学习尽可能地贴近人类的学习，让机器尽可能地掌 握人类的智能，是机器学习领域需要解决的最终问题。从5 0 年代起，机器学习 的发展过程大体上可以分为4 个时期： 5 0 年代中叶到6 0 年代中叶。在这个时期，所研究的是“没有知识”的学习， 即“无知”学习；其研究目标是各类自组织系统和自适应系统；主要的研究方法 是不断修改系统的控制参数以改进系统的执行能力，不涉及与具体任务有关的知 识；形成了机器学习的两种重要方法，即判别函数法和进化学习。所取得的学习 结果都很有限，远不能满足人们对机器学习系统的期望。 6 0 年代中叶到7 0 年代中叶。研究目标是模拟人类的概念学习过程，并采用 逻辑结构或图结构作为机器内部描述。机器能够采用符号来描述概念( 符号概念 获取) ，并提出关于学习概念的各种假设。这种学习系统取得较大的成功，但只 能学习单一概念。 7 0 年代中叶到8 0 年代中叶。在这个时期，人们从学习单个概念扩展到学习 多个概念，搜索不同的学习策略和各种学习方法。机器的学习过程一般都建立在 大规模的知识库上，实现知识强化学习。尤其今人鼓舞的是，本阶段已开始把学 习系统与各种应用结合起来，并取得了很大的成功，促进了机器学习的发展。1 9 8 0 年，在美国的c m u 大学召开了第一届机器学习国际研讨会，标志着机器学习研究 已经在全世界兴起。 8 0 年代中叶至今。机器学习的研究已在全世界范围内出现新的高潮。机器学 习与人工智能各种基础问题的统一性观点正在形成，各种学习方法应用范围不断 扩大。 在文本分类的机器学习过程中，关键的问题是如何让计算机将新文本正确地 天津大学硕士学位论文第二章自动文本分类系统 归入相应的类别中。目前存在多种基于向量空间模型的文本分类算法，下面详细 介绍几种常见的分类方法。 首先我们给出一些通用的符号定义：d _ 吐，如 表示待分类的文档向量， c = b ，) 表示可能的全部类别，并假定训练所使用的文档集包含n 篇文档 d l ，d 。) 所对应的类别为饥，y , v ，m 表示类别属于q 的文档数。 1 ) r o c c h i o 算法( 也称为类中心分类法) 该方法在信息检索领域是处理文档过滤和路由的经典方法。它会为每个类别 建立一个中心向量。该中心向量是在文档集合中，根据算术平均值为每个文档类 生成的一个代表该类的向量。当新文本来到时，通过计算文本向量与类中心向量 之间的距离判定分类结果。向量间距离可以使用点积或j a c c a r d 相似度计算。 2 ) 朴素贝叶斯( n a i v eb a y e s ) 概率分类器在机器学习中很常用。贝叶斯方法 4 4 1 的基本思想是利用单词和 类之间的联合概率来估计给定文档属于某一类别的概率。它的朴素之处在于它的 词条独立性假设，即不同词条在给定类别下的条件概率分布是互相独立的。该假 设使得朴素贝叶斯分类器不需要计算单词之间的联合分布概率，使得其速度远快 于哪些非朴素贝叶斯( 达到指数复杂度) 。根据贝叶斯公式可以推断： p ( c jj d ) = p ( e i j ) p 五( d 广 c j ) ( 2 1 4 ) 在2 1 4 式中，分母值对于不同的类别是恒定的所以可以忽略不计。再加上词 条独立性假设，则上式可改写成： 吖 p ( e jd ) = p ( c j ) 兀p ( 4i 勺) ( 2 1 5 ) i = l 对p ( c ，) 的估计反o ) 可以通过训练文档集合中属于类别q 的文档比例计算： 氟c 吲= 等( 2 - 1 6 ) 对于p ( 4i q ) 的估计反面i 勺) 可以通过下面的式子得到： 嘲俨遗巍 ( 2 - 1 7 ) 天津大学硕士学位论文第二章自动文本分类系统 其中n f 表示词条i 在属于类别勺的文档中出现的频率。 虽然朴素贝叶斯的词条独立假设并不合理，但是该分类器的效果在很多语料 库上取得了很好的成绩。 3 ) k 最邻近方法( k - n e a r e s tn e i g h b o r ) k n n 是最著名的模式识别统计学方法之一，已经有四十多年的历史。它在 很早就被用于文本分类研究【4 5 】，它也是在r e u t e r s 语料( 包括2 1 4 5 0 版本和a p t e 给出的集合) 上取得最好结果的文本分类算法之一。 k n n 算法相当简单：给定一个待分类的测试文档，系统在训练集合中查找 与测试文档最相似的k 个文档( 称为邻居) ，并根据这些邻居的类别所属情况来给 该测试文档的候选类别评分。可以把邻居文档和测试文档的相似度作为邻居文档 所在类的类权重。如果这k 个邻居中的部分文档属于同一个类，则该类别中的每 个邻居的类权重之和作为该类别和测试文档的相似度。最后通过对候选类评分的 排序，并给出一个预先设置的阈值，就可以判定测试文档的类别。相似度计算可 以使用欧式距离或者向量间的余弦值得到。 p ( d ，c j ) = s i m ( d ，d f ) y ( d f ，c j ) - b j ( 2 1 8 ) 其中岛为类别勺的预定义阈值，y ( d ，q ) 为类别属性函数： 鹏咿化2 q ( 2 - 1 9 ) 各个分类的阈值b 则是通过训练集合的交叉检验( c r o s s - v a l i d a t i o n ，取训练 集合的一部分训练，其他部分作为测试) 获得，这些阈值使得在交叉检验中得到 最好的f 测度。 k n n 是一个基于实例的懒惰学习方法，它不需要离线的训练阶段。主要的 耗时在于被测文档与训练文档集之间相似度的实时计算，从而得到最近的k 个邻 居。 4 ) 支持向量机( s u p p o r tv e c t o rm a c h i n e ) 支持向量机( s v m ) 由v a p u i k 在1 9 9 5 年提出【1 5 】，用于解决二分类模式识 别问题。它基于结构风险最小化原则( 该原则的错误上界已经得到了证明【1 5 】) 。 已经在很多二值分类问题上表现出很好的泛化能力( g e n e r a l i z t i o n ) 。也正是由于 天津大学硕士学位论文 第二章自动文本分类系统 这个原因，为了在文本分类问题中使用s v m ，就需要将文本分类问题分解成为 一系列二值分类的问题集合 从机器学习的术语角度理解，$ v m 是一个非顺序( 训练样本实例之间没有 固定的顺序要求，比如词袋模式( b a g - o f - w o r d ) 等) 、监督的( 每一个训练样本 都包含输入信息和输出信息) 、非估计模式( 学习得到的模式是一个潜在的判定 函数，而不是概率分布) 的机器学习方法。 ( x 1 ，y 1 ) ，( x 2 ，y 2 ) ，( x 。，y 。) + 1 ) 图2 - 2s v m 模型是一个非顺序、监督式、非估计式的机器学习方法 结构化风险最小化的思想就是找到一个假设h ，它可以保证最低的真实误差 ( l o w e s t t r u ee r r o r ) 。 的这个最低真实误差可以理解为它在未知的随机选择的 测试样本上的判断错误的概率。我们可以在 的真实误差与矗在训练样本集合上 的误差和日( 包含h 的假设空间) 的复杂度( 用v c 维来描述) 之间用一个上限 将它们联系起来。支持向量机可以找到这样的一个假设空间h ，可以最小化真实 误差而又有效的控制h 的v c 维度。 支持向量机在向量空间中找到一个决策面( d e c i s i o ns u r f a c e ) ，这个面能“最 好”地分割两个类别中的数据样本。为了定义“最好”分割，我们引入两个类别 之间的分类问隔( m