（计算机系统结构专业论文）基于向量空间模型的文本分类系统研究与实现.pdf

中文摘要 i n t e r n e t 己被公认为是2 0 世纪末人类科技史的里程碑，它促使人类社会步 入了以网络为中心的信息时代。随着w e b 信息量爆炸性增长，人们很难从大量的 信息中迅速有效地提取出所需信息，出现所谓的“信息迷向”的现象。为了准确 地定位所需的信息，文本分类的研究显得越来越重要了。 向量空间模型是进行大规模文本处理常用的表示模型，本文对基于向量空间 模型的文本分类的关键技术进行了研究和探讨，包括：文本的表示，向量空间模 型，特征类型的确定，特征的抽取与选择和文本分类算法等问题。 传统的向量空间模型不能区别不同位置的文本特征项表达文本内容的不同 能力。针对该问题，本文运用位置修正因子调整特征项权重，提高了向量空间模 型的性能。 本文结合已有的文本信息描述和特征抽取方法，综合考虑了频度、分散度和 集中度等三项指标，设计并实现了一种新的特征抽取算法，使得选出的特征项整 体优化。 作为对比的基准，本文编程实现了传统的基于类中心分类法的文本分类系 统，通过分析该方法存在的问题，提出并实现了二级分类模式的文本分类系统。 实验结果表明，二级分类模式的分类系统具有较高的精确度、召回率和f 1 测量 值。 本文最后指出，概念空间能够深入描述文本之间的内在联系，采用概念空间 代替词频空间来表示文本，不仅能够大大降低特征维数，提高文本分类效率，还 能有效滤除噪声，提高文本分类的正确率。 关键词：文本分类，向量空间模型，特征项权重，特征抽取，二级分类模式 概念空间 a b s t r a c t i n t e m e ti sam i l e s t o n ei nt h eh i s t o r yo fs c i e n c ea n dt e c h n o l o g ya tt h ee n do f2 0 “ c e n t l a r y , m a du r g e so u rs o c i e t yt ot h ei n f o r m a t i o nt i m e st h a tc e n t e r so nt h en e t w o r k w i t ht h ee 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 e r e q u i r e di n f o r m a t i o n f r o mm a s s i v ei n f o r m a t i o n ，w h i e hi sc a l l e d “i n f o r m a t i o n c o n f u s i o n ”，t ol o c a t et h er e q u i r e di n f o r m a t i o n ，t e x tc l a s s i f i c a t i o ng r a d u a l l ys e e m e dt o b em o r ei m p o r t a n t v e c t o rs p a c em o d e l ( v s m ) i st h ep o p u l a rm o d e l sf o rl a r g es c a l eo ft e x t p r o c e s s i n g w ed i s c u s st h ek e yt e c h n i q u e so ft e x t c l a s s i f i c a t i o nb a s e do nv s m ， i n c l u d i n gt e x tr e p r e s e n t a t i o n ，b a s i cc o n c e p to fv s m ，f e a t u r ee x t r a c t i o na n ds e l e c t i o n ， a n dt e x tc l a s s i f i c a t i o n t r a d i t i o n a lv e c t o rs p a c em o d e lc a n n o td i s c r i m i n a t et h ei m p o r t a n c ed e g r e eo ft h e d o c u m e n tt e r m sa td i f f e r e n tp o s i t i o n sa n dt h e i re x p r e s s i o na b i l i t yt ot h ed o c u m e n t c o n t e n t b ya n a l y s i n gt h ep r o b l e m sa b o v e ，t h i sp a p e rm o d i f i e st h ef o r m u l ao ft e r m w e i g h t i n g ，t h et h e o r e t i ca n a l y s i sa n dt 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 en e w a l g o r i t h mi m p r o v e st h ep e r f o r m a n c eo f v s mg r e a t l y f o rt h em e t h o d so ff e a t u r ee x t r a c t i o n ，t h i sp a p e rc o m p r e h e n s i v e l yt a k e si n d e x e s s u c ha sf r e q u e n c y , d i s t r i b u t i o na n dc o n c e n t r a t i o ni n t oa c c o u n ta n dp r o p o s e san e w a l g o r i t h mo ff e a t u r ee x t r a c t i o n 。w h i c he n a b l e st h es e l e c t e df e a t u r et e r m st or e a c ht o o p t i m i s a t i o na m o n gt h e s ei n d e x e s w ei m p l e m e n ta u t o m a t i ct e x tc l a s s i f i c a t i o ns y s t e mb a s e do nt h ec a s s c e n t e r m e t h o da n dv a l i d a t ei t sf e a s i b i l i t y o nt h eb a s i so ft h ea b o v es y s t e m ，t h i sp a p e rf u r t h e r i m p l e m e n t sat e x tc l a s s i f i c a t i o ns y s t e mw i t ht h et w o l e v e lm o d e t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt w o l e v e lc l a s s i f i c a t i o nm o d eh a sh i g h l yi m p r o v e dt h er e c a l la n d p r e c i s i o nc o m p a r e dw i t ht h ec l a s s c e n t l r em e t h o d 。 c o n c e p ts p a c ec a nd e s c r i b ei n n e rr e l a t i o n sb e t w e e nt e x t sa n dm i n ed e e pc o r p u s s t r u c t u r e t h i sp a p e ri n t r o d u c e sac o n c e p t ，c o n c e p ts p a c e ，a n db u i l d sam e t h o df o r t e x td e s c r i p t i o na n dd i m e n s i o n a lr e d u c t i o ni nt h ec o n c e p ts p a c e w i t ht h eo r t h o g o n a l a n df e a t u r ee x t r a c t i o np r o p e r t i e si nt h ec o n c e p ts p a c e ，t h i ss y s t e ms h o w sag o o d p e r f o r m a n c ei nf i l t e r i n gn o i s ea n dd e c r e a s i n gd i m e n s i o n s k e yw o r d s ：t e x tc l a s s i f i c a t i o n ，v e c t o rs p a c em o d e l ，t e r mw e i g h t i n g f e a t u r ee x t r a c t i o n ，t w o - l e v e lc l a s s i f i c a t i o nm o d e ，c o n c e p ts p a c e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨洼盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：仞知各们 签字日期：时年 f 月7 目 学位论文版权使用授权书 本学位论文作者完全了解鑫洼盘堂有关保留、使用学位论文的规定。 特授权盘鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：际绍卿 二i 导师签名：7 1 百乙膨 签字日期：w 哕年 月7 日签字日期：砌f 年，月叼日 天津大学硕士学位论文 第一章绪论 1 i 选题背景和研究意义 第一章绪论 i n t e r n e t 己被公认为是2 0 世纪末人类科技史的里程碑，它作为一个开放的、 分布式的信息空间，近年来得到了飞速发展。随着i n t e r n e t 上信息量爆炸性的 增长，人们很难从大量的信息中迅速有效地提取出所需信息，出现所谓的“信息 迷向”的现象。如果计算机能够在信息的辨识和处理方面，对用户提供适当的支 持和帮助，那将能够极大地改善目前用户面临的困境和提高信息使用效率。 基于这种需求，人们对利用计算机进行智能化信息处理进行了大量研究。根 据侧重点不同，大致包括信息检索、信息抽取、文本分类、文本摘要等研究领域， 这些研究都旨在帮助用户对i n t e r n e t 上的大量信息加以辨识、分类，按用户兴 趣加以筛选、排序，甚至提炼出要点形成摘录。这些研究成果和搜索引擎相结合， 构成智能化搜索引擎，极大地提高了用户搜寻信息的能力。另外，这些技术也应 用在电子商务、数据库、w e b 页分类管理、信息过滤、个性化人机界面、个人信 函助理等领域，有效地提高了信息服务的质量。 在以上应用领域中，文本分类是一个广为关注的课题，这项技术既有潜在的 市场应用价值，又具有相当的难度。这里说的“分类”是一个广义的概念【1 圳， 包括分类和聚类：如果分类原则是事先通过事例( 包括正例和反例) 告诉计算机 的，则计算机在事例的基础上形成分类机制的过程称为有监督的分类，简称归类 或分类；如果事先没有任何示例，全凭信息本身在某种角度上的相似性来分类， 这种分类过程就称为无监督的分类，简称聚类【4 j 。分类和聚类可以在较大程度上 方便地为用户准确定位所需的信息，解决网上信息杂乱的现象，因此对文本进行 自动分类和聚类成为信息检索过程中具有较大实用价值的关键技术。本文研究和 探讨的是第一种分类，即有监督的分类。 1 2 文本分类系统的研究现状 国外在文本分类技术以及相关的信息检索、信息抽取等领域进行了较为深入 的研究，并产生了一些可用的分类系统，例如自动分类新闻稿件的文本分类器、 自动分类w e b 页的文本分类器等，至今在以下方面取得了不错的成果： 天津大学硕士学位论文 第一章绪论 1 ) 向量空间模型的研究日益成熟 s a l t o n 等人在6 0 年代末提出的向量空间模型【5 】在文本分类、自动索引、信息 检索等许多领域得到了广泛的应用，已成为最简便高效的文本表示模型之一。通 过不同文本分类系统的运行和比较表明，向量空间模型是处理文本分类领域大规 模语料库较好的表示模型。 2 ) 对特征项的选取进行了较深入的研究 对于英法德等语种，文本可以由w o r d s 、c l u s t e r so f w o r d s 、p h r a s e s 、c l u s t e r s o f p h r a s e s 或其他特征项进行表示，a n d r e w 和l e w i s 等学者对这些特征项进行了 详细地分析【6 ，并且在r e u t e r s 2 1 5 7 8 等标准语料库上进行实验，做出了较一致的 结论：使用优化合并后的w o r d s 作为特征项在文本分类中应用效果最佳。此外 也有不少学者正在努力突破以上特征项的选择空间，定义自己的文本表示空间， 例如s a ms c o t t 定义了一套符号系鲥”，利用w o r d s 和附加的符号信息表示文本， 也取得了一定的成果。 3 ) 较完整的分类算法的研究和比较 国外对于文本分类算法的研究开展得较早，也较完整。例如，对b a y e s 、k n n 、 r o c c h i o 、s v m 、神经网络等算法都有比较详细的研究和性能比较。总体而言， 这些算法在分类性能上差别不大，以k n n 和s v m 稍好。 4 ) 比较标准的测试语料库 例如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 语料库( 2 1 ，5 7 8 篇文章1 3 5 个类别) 都曾较为广泛地使用，而且t r e c 也提供了较为标准的语料库。 5 ) 较为规范的测试方法 国外学者在标准的测试语料库上也定义了较为规范的测试方法，除了传统的 测试指标外，还有一些更为细致的测试指标，例如l e w i s 给出了一套较完整的分 析方法1 6 j ，不但可以测试系统的整体性能，而且可以较科学地分析多训练文本类 和少训练文本类的分类性能。 6 ) 开始研究未标记文本对分类系统的影响 国外学者在整理语料库的过程中发现收集及分类训练文本是极其费时、费力 的过程，因此提出在训练文本不充足的情况下如何利用未标记文本提高分类系统 的性能，并且开展了一定的研究。 7 ) 将文本分类技术应用到某些特定的信息服务中 例如将文本分类技术应用到事件跟踪系统中，为用户( 主要是新闻媒体用户) 收集与事件相关的文章，制作事件专题节目。另外将文本分类技术应用于用户个 天津大学硕士学位论文第章绪论 性化服务系统中，跟踪用户感兴趣的文章，进行类别判别，为用户提供方便的信 息服务。 国内也已开展了文本分类的研究，例如，吴军、吴立德、黄蒈掣8 】等进行了 汉语语料自动分类的研究，他们以字或词为特征项构成特征向量，以频度作为词 的权重，利用一些分类算法构造分类器，取得了一定的效果。但是总的来说，研 究相对落后，主要存在如下问题： 1 ) 缺少统一的中文语料库 至今尚无标准的用于文本分类的中文语料库，各个研究者分头收集自己的训 练文本集，并在此基础上开展研究，因此系统的性能可比性不强。同时，由于财 力人力有限，中文语料库的规模普遍不大。 2 ) 适用于中文的向量空间模型的研究还不十分成熟 国内的学者，例如吴立德和黄萱菁提出可以使用字、词、概念作为中文的特 征项构成向量空间模型，并对以此为基础的文本分类系统进行了初步的性能比 较。但是，对于概念的定义不够清晰，也没有全面的比较和测试系统。另外，在 特征项抽取算法方面也缺少系统而深入的研究。 3 ) 文本分类技术与其他信息技术尚未很好地结合 国内的文本分类系统主要应用于图书馆等专业信息处理机构，在信息服务领 域，除了与搜索引擎有所结合外，文本分类技术与其他信息技术还没有很好的结 合，还没有得到充分的应用。 1 3 本文的主要研究工作 本文主要研究并实现了基于向量空间模型的中文文本自动分类系统，对固定 的文本数据集进行了实验分析，结果表明该系统具有较高的精确度、召回率和 f 1 测量值。本文研究内容有： 1 ) 基于类中心分类法的文本分类系统的实现 论文在给出文本分类系统整体方案的基础上，实现了一个基于类中心分类法 的文本分类系统，验证了整体方案的可行性，并以类中心分类法的分类结果作为 与其它分类算法进行比较的基准。 2 ) 向量空间模型的改进 传统的向量空间模型不能区别不同位置的文本特征项表达文本内容的不同 能力。针对该问题，本文运用位置修i e n 予调整特征项权重，提高了向量空间模 型的性能。 3 ) 文本信息的描述及特征的抽取 天津大学硕士学位论文 第一章绪论 本文结合已有的文本信息描述和特征抽取方法，综合考虑了频度、分散度和 集中度等三项指标，设计并实现了一种新的特征抽取算法，使得选出的特征项整 体优化。 4 ) 基于二级分类模式的中文文本分类方法 本文对文本分类中所涉及的关键技术进行了研究和探讨，通过考察以往文本 自动分类系统的研究经验，提出一种分类准确率高的基于二缴分类模式的文本分 类方法。 5 ) 概念空间及其在文本分类中的应用 概念空间使用深层的概念，而不仅仅是表象的词，因而能够深入描述文本之 间的内在联系，有利于挖掘文本集的深层结构。采用概念空间代替词频空问来表 示文本，不仅能够大大降低特征维数，提高文本分类效率，还能有效滤除噪声， 提高文本分类的正确率。 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 年代以来，随着信息存储技术和通信技术的迅猛发展， 大量的文字信息开始以计算机可读的形式存在，而且其数量每天仍在急剧增加。 在这种情况下，基于机器学习的文本分类逐渐取代了基于知识工程的方法，成为 文本分类的主流技术。 简单地说，文本分类系统的任务是：在给定的分类体系下，根据文本的内容 或属性，将大量的文本归到一个或多个类别中 9 。10 】。从数学角度来看，文本分类 是一个映射的过程，它将未标明类别的文本映射到已有的类别中，该映射可以是 一一映射，也可以是一对多的映射，因为通常一篇文本可以同多个类别相关联。 用数学公式表示如下： ，：爿- - b其中：一= ( d l ，d 2 ，d 。)b = ( c i ，c 2 ，一，c ，) ( 2 - - 1 ) 即：a 为所有待分类的文本的集合；b 为给定分类体系下，所有类别的集合。 a 可以为无限集合，而b 必须为有限集合。 文本分类的映射规则，是文本分类系统的关键，它是系统根据训练集的样本 信息总结出的分类规律，来建立判别公式和判别规则；遇到新文本后，根据总结 出的文本分类的映射规则，确定该文本相关的类别。 天津大学硕士学位论文第二二章文本分类系统概述 2 2 文本分类系统流程及需解决的问题 图2 - 1 文本分类流程图 文本分类的流程如图2 1 所示：属性选择、分类训练和测试评估构成一个循 环，根据测试结果，调整属性选择和分类训练的参数，使得分类器具有更佳的分 类效果。从该图可以看出，文本分类需要解决如下5 个问题： 1 ) 获取训练文本集 训练文本集选择是否合适对文本分类器的性能有较大影响。训练文本集应该 能够广泛代表分类系统所要处理的各个类别中的文本。般地，训练文本集应该 是公认的经人工分类的语料库。 2 ) 属性选择 语言是一个开放的系统，作为语言的一种书面物化或者电子化的文本也是开 放的，其大小、结构以及包含的语言信息也都是开放的。目前的文本分类方法和 系统都采用词和词组作为表征文本语义的属性，因此属性的数量很大。文本分类 系统应该选择尽可能少、准确并且与文本主题密切相关的属性进行文本分类。 3 ) 建立文本表示模型 即选用怎样的形式组织属性来表征文本的问题。目前的文本表示模型主要有 布尔模型和向量空间模型。 4 ) 选择分类方法 即选择用什么方法建立属性到文本类别的映射关系，这是文本分类的核心问 题。 5 ) 确定性能评估指标 天津大学硕士学位论文 第二章文本分类系统概述 目前使用比较多的分类性能评估指标为精确度、召回率和f - 测量值，下面 就详细介绍这个问题。 2 3 文本分类结果的评价 对文本分类结果主要从三个方面评价：有效性、计算复杂度和描述的筒洁度。 有效性衡量的是一个分类器正确分类的能力：计算复杂度包括时间复杂度和空间 复杂度，如果按照分类的步骤来分，计算复杂度又可以分为训练计算复杂度和分 类计算复杂度；算法描述的简洁度很容易理解，当然越简洁越好。三个方面之中， 有效性最为重要，因为不管分类器的速度有多快、占用的空间有多少、算法有多 容易理解，如果它不能正确分类的话，这个分类器就是没有用的。因此对分类结 果的评价主要指的是有效性的评价。 评价分类结果有效性主要用3 个指标：精确度( p r e c i s i o n ) 、召回率( r e c a l l ) 和f 一测量( f - m e a s u r e ) ，这几个术语均来源于信息检索。 2 3 1 精确度和召回率 精确度( p r e c i s i o n ) p ，衡量的是所有被分类器分到类别c ，的文本中正确文 本的比率；召 率( r e c a l l ) r ，衡量的是所有实际属于类别c ，的文本被分类器分到 该类别中的比率。用公式表示如下： p ：(2-2) | j r p i pj 冠，： ! ( 2 3 ) 冠，= l 一 ( 一) 。 冲+ f n 其中，丁p 指的是被分类器正确分到类别c ，的文本数；碣指的是实际不属于类 别c ，却被分类器错误地分到类别c ，的文本数；f n 指的是实际属于类别c ，但分 类器没有将其正确分到类别c 的文本数。 2 3 2f - 测量 精确度和召回率是两个相互矛盾的衡量指标，一般情况下，精确度会随着召 回率的升高而降低。两者不可兼得。所以很多情况下需要将它们综合在一起考虑。 最常用的综合方法就是f 一测量( f - m e a s u r e ) ，定义如下： f ，c p ，r ，= ! 鬻( 2 - - 4 ) 天津大学硕士学位论文 第二章文本分类系统概述 其中口是一个调整参数，用于以不同权重综合精确度和召回率。当卢等于1 时， 表示精确度和召回率被平等地对待，此时f 一测量( f - m e a s u r e ) 又被称为五，定 义如下： 州p ，r ) = 并每 ( z _ 5 ) 2 3 3 分类方法的综合评价 上面提到的精确度、召回率及 方法都是针对单个类别的分类情况而言的， 当需要评价某个分类方法时，还需要将所有类别的结果综合起来得到平均的结 果。综合的方法有两种，宏平均( m a c r o a v e r a g i n g ) 和微平均( m i c r o a v e r a g i n g ) 。 宏平均( m a c r o a v e r a g i n g ) 在计算时，是先依据公式( 2 2 ) ( 2 3 ) 求得每一 个类别的精确度和召回率，然后将它们平均得到最终的值。宏平均对应的精确度、 召回率和的计算公式如下所示，其中i c i 为类别数： f i c lp m a c r op ：兰掣( 2 - - 6 ) 一 旧 m a c r or ：率( 2 刊= 兰告掣( 2 7 ) 一 f c l m a c 加f ：! ! 丝竺! ：旦! 丝竺：墨( 2 - - 8 ) 一 m a c r o p + m a c r o r 微平均( m i c r o a v e r a g i n g ) 在计算时，首先将所有类别中对应的”，、f 尸，和 f n ，分别相加，然后计算出微平均的精度、召回率和f 的值，计算公式如下， 其中i c i 为类别数： f i c l t p 始啪一p2 霹厨l a 丽s r j ( 2 - - 9 ) 。c 1 i c l n 舱c 阳一露2 豇甄l 忑y , i 雨可( 2 - - 1 0 ) m i 仃df ：! ! 丝竺：旦! 丝竺! ：墨 ( 2 一1 1 ) m i c r o p + m i c r o r 由上面的计算公式可以看出，宏平均对所有类别的结果平等对待，不管类别 的大小，所以任何一个类的变动都可能对宏平均造成较大的影响。相对而言，微 平均更看重大类别的分类结果。因此，两个方法所得到的结果可能会有很大的差 别，特别是当各类的结果有很大差异的时候。 天津大学硕士学位论文 第三章基于向量空间模型的文本分类算法 第三章基于向量空间模型的文本分类技术 向量空间模型是信息检索常用的表示模型之一，它在大规模文本处理( 例如 文本分类、文本检索和文本摘要等) 方面具有很强的优势。在向量空间模型中， 文本不再是字或词符号顺序连接的字符串，而成为了方便于计算机处理的向量。 语料库中所有的文本都统一在向量空间模型中，从而可以利用计算机快捷地处理 它们。 本章主要讨论基于向量空间模型的文本分类技术，包括文本的表示、向量空 间模型、特征类型的确定、平滑技术、特征的抽取与选择和文本分类算法等。 3 1 文本表示 至今，计算机还不能象人类那样阅读完文章后，根据自身的理解能力对文章 内容产生一定的认识。更何况大规模文本处理的对象是大量的真实文本，要使计 算机能够高效率、高性能的处理自然文本，就必须找到一种理想的文本表示方法。 文本表示最理想的境界就是模拟人所理解的语义，通过函数f ，使得： 人所理解的语义= f ( 文本) 一旦找到了合适的函数来表示人所理解的语义，那么由计算机处理文本的问题就 变得简单了。对于文本分类来说，其过程就可以转化为一个搜索问题，即寻找和 新文本函数值差异最小的文本类。 但是不幸的是，这种精确反映人所理解语义的函数是很难定义的，或者更极 端一点说，也许根本就是不存在的。对于形式语言而言，语义还可以通过机器状 态的改变来描述，人们也正是通过这种方法来学习和掌握机器语言的：可是对于 自然语言而言，由于涉及到人这个认知主体的思维活动，不同的认知主体往往会 有不同的理解，自然语言的形式及其意义之间是多对多的关系，很难合理地定义 一个反映语义的函数。 因此，我们只好退而求其次，寻求一种能够量化、能够形式化、最终可以计 算和操作的表示方法。一种可行的方案就是走统计的路线，研究从大规模语料库 中发现出来的统计规律，利用文本在字集合或词集合上的分布来近似表示语义， 并且做如下的假设： i 两个分布完全一致的文本被认为是语义相同的。 天津大学硕士学位论文 第三章基于向量空间模型的文本分类算法 i i 两个分布相近的文本被认为是语义相近的。 自然，仅仅采用这种分布是不能精确反映人所理解的语义的，然而这种方案 却能够很方便地计算和操作，对于信息处理等应用领域，其表达效果还是可以接 受的。 根据以上思路，我们来考察文本。众所周知，文本是字词等代表特定含义的 符号按顺序连接的字符串。文本有两个基本的特征：一是组成文本的所有字词符 号出现的频率，二是这些符号间的连接顺序，即文本可以由特征项的频率及其相 互关系来完整表达。要表示文本中特征项的顺序信息，就必然要用到有向的指针 结构，这样，整个文本就变成了一个复杂的图或网。而表示文本中特征项的频率 信息，仅仅使用一个向量就够了。信息检索和文本分类等信息处理技术要求定义 一种距离函数，以表示文本间的相似程度。数学中有很多种定义距离的方式可以 供使用，例如欧式距离、相关系数等等。 3 2 向量空间模型 向量空间模型v s m ( v e c t o rs p a c em o d e l ) 是由s a l t o n 教授最早在1 9 6 8 年提 出的，一直以来都是信息检索领域最为经典的计算模型。它使用向量表示文本， 并成功应用于著名的s m a r t 系统中。该模型现已成为最简便、最高效的文本表示 模型之一。 向量空间模型的出发点是：每篇文本和查询都包含些用特征项表达的揭示 其内容的独立属性，而每个属性都可以看成是向量空间的一个维数，则文本和查 询就可以表示为这些属性的集合，从而忽略了文本的结构中段落、句子及词语之 间的复杂关系。这样，文本和查询可以分别用空间的一个向量表示，文本与查询 之间的相似度可以用向量间的距离来衡量。相似度的计算方法有很多种，常用的 方法有内积、d i c e 系数、j a c c a r d 系数和余弦系数【12 1 。通常采用余弦系数法， 即用两个向量之间的夹角余弦来表示文本与查询问的相似度。夹角越小，说明文 本和查询间的相似度越大。 向量空间检索模型可以描述为i = ( d ，t ，q ，f ，r ) ，其中： d = d 。d 2 ，d 。) 为文本集合，n 为集合中的文本数； t = 托，t ，f 。) 为特征项集合，m 为所有的特征项数。n 1 个特征项标引的某 一文本可以表示为空间中的一个向量d ，= ( q 。，f 2 ，。) ，f - 1 , 2 ，n ，。是特征 项f ，对于文本d ，的权重，如果权重值卯，为0 ，则表示，没有在d ，中出现； a = q 1 ，q 2 ，口。 为查询集，某一查询吼可以由向量牙，= ( q 。q ，2 ，q ，) 表 示，是特征项r ，对于查询g ，的权重，如果权重值g 。为0 ，则表示f ，没有在q ，中 天津大学硕士学位论文第三章基于向量空间模型的文本分类算法 出现； f = id 。d ，t ，et 为文本一特征项的描述关系， i = 1 , 2 ，j = 1 , 2 ，m ，其中0 d i 1 ； r 为检索函数，r ( q ，) 是系统响应，由查询向量牙。与文本向量一经过相似性 计算得出，系统响应r ( q ，) = a ( q 。，d ，) ，i = 1 , 2 ，z 。 基于此模型进一步定义： 以为特征项r ，在文本吐中出现的频率； 为在整个文本集中，包含特征项，的文本数； 吼为反转文本频率，奶2 1 。g ( 万a ) ； ( 3 一1 ) 珊，为特征项r ，的权值，国，2 如f 彬2 了夏i 矿j 霞x i l o g i ( n i 亏n j 翥+ 0 丽0 1 ) ( 3 2 ) 其中为文本的总数，n ，为文本集中出现f 的文本数，分母为归一化因子； ( c 0 4 。) s c ( d ，g ) 为文本与查询之间的相似度，s c ( d ，g ) = 旦_ 【( 2 ) ( ，2 ) j l = lf = l ( 3 3 ) 其中为特征项在文本中的权重，曲。为特征项在查询中的权重。 可见，传统的向量空间模型是以文本特征项的频率矿和反转文本频率f c 矿作 为其量化基础，其乘积作为特征项的权重，再通过计算文本与查询之间的相似度 来判断文本与查询是否相关。 下面用一个简单的英文例子描述使用向量空间模型进行信息检索的整个过 程，假设有以下查询和文件集： q ：“g o l ds i l v e rt r u c k ” d l ：“s h i p m e n to fg o l dd a m a g e di naf i r e d 2 ：“d e l i v e r yo fs i l v e ra r r i v e di nas i l v e rt r u c k d 3 ：“s h i p m e n to fg o l da r r i v e di nat r u c k 在这个文件集中，共有三篇文件( n = 3 ) ，如果使用英文单词为检索单元， 根据式3 1 ，各单词对应的i d f 权值1 如下： i d f 。= 0 i d f 。i = 0 1 7 6 在本论文中，所有数字近似计算取至小数点后第三位。 - l l 天津大学硕士学位论文 第三章基于向量空间模型的文本分类算法 i d f d 。d = 0 4 7 7 i d 厶。v 。，= 0 4 7 7 i d f i i ，。= 0 4 7 7 i d f 。i d = 0 1 7 6 i d f i 。= 0 i d f o f = 0 i d f 。“，。，= 0 4 7 7 i d f “i 。= 0 1 7 6 i d f 。，。k = 0 i 7 6 再根据式3 2 ，得到以下向量： q ： d l ： d 2 ： d a ： 再根据式3 3 ，得到以下相似度： s c ( q ，d 1 ) = 0 0 3 1 s c ( q ，d 2 ) = 0 4 8 6 s c ( q ，d 3 ) = 0 0 6 2 按照各文件与查询不同的相似度对文件进行排序，并提交检索结果。本例的 检索结果为：d 2 ，d 3 ，d l ，与该查询最相关的文件是d 2 ，这是和人工检索结果相 符合的。 3 3 特征项类型的确定 中文文本信息处理和欧洲语言信息处理的一个最大的区别就在于中文被写 成连续的字串，词与词之间没有显式的界限，而欧洲语言旬子的词与词之间有空 格。所以我们必须对文本进行预处理，确定好特征项类型，即基于什么类型的特 征去分类，常见的特征项类型有字、词、概念等。 确定特征项类型应该注意以下原则：一是应当选择包含语义信息较多，对文 本的表示能力较强的语言单位作为特征项；二是文本在这些特征项上的分布应当 有比较明显的统计规律性：三是比较容易实现，时间和空间的开销都不应该太大。 在实际应用中，通常可以选择以下特征项： 1 ) 字特征项 字是汉语中最基本的语言单位，以它作为特征项对文本语义的表达能力相对 天津大学硕士学位论文 第三章基于向量空间模型的文本分类算法 较差，但是汉语中汉字的数量大大少于词语的数量，所以，选择字作为特征项可 以使特征项抽取的工作量大大降低，加快系统的效率。但是选择字作为特征项在 信息处理中达到的性能较差。 2 ) 词特征项 一般认为，词是构成汉语文本的主体，是最能反映文本语义的基本单位，选 择词作为特征项能够充分表示文本的语义，系统的性能优于选择字作为特征项的 系统。 3 ) 概念特征项 以字作为特征项表示文本，颗粒度太大：以词作为特征项表示文本，颗粒度 太细。同时，在汉语中存在大量的同义词和近义词，将它们作为不同的特征项显 而易见是不太合适的，它可能使两篇类似的但用词风格不同的文本距离相差过 大。在这样的情况下，有些学者提出了概念特征项的说法。概念通常是指代表一 类同义词或近义词的条目。概念特征项合并了同义词和近义词，使得特征项的选 择尽可能地集中，贴近语义。但是，概念的判断和处理相对复杂，自然语言中存 在同义关系( 如老鼠、耗子) 、近义关系( 如忧郁、忧愁) 、从属关系( 如房屋、 房顶) 和关联关系( 如老师、学生) 等各种关系。如何很好地划分概念特征项， 确定概念类，以及概念类的数量都是需要反复尝试和改进的问题。 现有的研究认为以词为单位来进行处理比较合理，本文也采用了以词为特征 单位的方法。在分词的过程中，我们采用了北京大学计算语言所提供的分词和词 性标注系统【”。1 ”，该系统将分词和词类标注结合起来，利用丰富的词类信息对分 词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，同时 将基于规则的标注排歧与基于语料库统计模型排歧结合起来，使规则的普遍性与 灵活性得到统一，而且对未登录词的估算达到了相当高的准确率。 另外，由于文本中有很多语法词( 例如“的”、“和”等) 以及一些虚词，感叹 词，连词等，所有这些词不能表达文本的内容，更不能描述文本类别的特征；还 有一些词汇在所有文本中出现的频率都基本相同，区分性差，也不能作为文本类 别的特征，可以考虑把它们作为停用词滤除掉。因此，文本经过分词程序分词后， 首先去除停用词，合并数字和人名等词汇，然后统计词频，最终表示为前面描述 的向量形式。 3 4 平滑技术 向量空间模型在建完索引以后，文本中的特征项是非常稀疏的。对于一篇文 本，其中大部分特征项的频率矿为0 。这种情况可以采用平滑( s m o o t h i n g ) 技 天津大学硕士学位论文第三章基于向量空间模型的文本分类算法 术来进行处理。 平滑采用最大似然估计法将那些为0 的特征项的概率增大，同时为了保证概 率的归一化，将出现频率较高的特征项的概率减小。参数平滑不只是避免零概率， 它是统计语言模型里一个很关键的问题，选择合适的平滑算法能够显著提高模型 的性能。常用的平滑方法有a d d i t i v e 平滑算法和g o o d t u r i n g 算法等。 1 ) a d d i t i v e 平滑算法 a d d i t i v e 平滑算法是最简单的平滑算法之一，可以写成如下形式： p。d卉m。(vr。ir一一t+vr一一t)=：；if!：；：i!黯 ( 3 4 ) 其中0 兰占蔓1 ，v 是特征项的大小，即不同的特征项的个数。很容易证明，该算 法满足概率两个性质：非负性和归一性，因为上式中的每一项都为正，所以满足 非负性；并且： ( 万+ c ( m r k ) ) w r 占iv= 1 + c ( w 。一女+ 1 w n 1 ) 2 ) g o o d t u r i n g 算法 g o o d t u r i n g 算法是很多平滑算法的核心。该算法根据出现了多少个r + 1 次 的特征项来计算出现r 次的特征项的概率： r + ：一+ 1 1 1 丛 行r ( 3 5 ) 其中，f 。是出现了r + 1 次的特征项的个数，n ，是出现了r 次的特征项的个数。 出现了r 次的特征项经过平滑之后得到，。 显然，经过这样处理之后，没有零概率现象了。该算法满足非负性是显然的， 下面证明它同时满足归一性。 令：= ， ，且= ，+ n ，当且仅当= n 时才满足参数的归一化。 = ，+ 怫= r ( ，+ 1 ) 挚= p + 1 ) h 。= n ，所以g o o d t u r i n g 算法也满 r = 0r = 0，r = l 足归一性。 3 5 特征抽取与选择 我们知道文本表示为向量空间模型后维数相当大，可以达到几万维，对此需 = 盟雌 坚 瓮 “五 +一i万一卜 一万 叫 天津大学硕士学位论文第三章基于向量空间模型的文本分类算法 要进行维数约减。所有几万个词汇对文本分类的意义是不同的：一些通用的、各 个类别都普遍存在的词汇对分类没有贡献：只有那些在某个特定类中出现比重 大，而在其他类中出现比重小的词汇才对文本分类有大的贡献。为了提高分类精 度，我们应去除那些表现力不强的词汇，筛选出针对每一类的特征项集合。 特征抽取一般是通过构造一个特征评分函数，把测量空间的数据投影到特征 空间，得到在特征空间的值，根据每一类中特征空间的值对每个特征项进行评估。 特征选择就是根据特征评估结果从中选出最优的即最有代表性的特征项子集作 为该类的类别特征。因此，特征提取与选择是一类文本集共性的归纳过程，是文 本分类中最关键的问题。特征提取与选择可以降低特征空间的维数，从而达到降 低计算复杂度和提高分类准确率的目的。 特征评分就是要计算特征项在某个类别中的权值，以反映其表现该类别的程 度。常用的特征评分函数有【l5 】：互信息法、期望交叉熵、信息增益和文本证据权 等等，其关键是找出体现类别的关键特征。下面介绍互信息法和期望交叉熵算法： 1 ) 互信息法 互信息是统计学和信息论中一个重要的概念，大量的研究