（计算机系统结构专业论文）基于bayes方法的文本分类器的研究与实现.pdf

重庆大学硕士学士论文 中文摘要 摘要 从大量的数据中挖掘出有用的信息是数据挖掘的任务。随着互联网的迅速发 展，w e b 已经发展成为拥有上亿页面的分布式信息空间。在信息急剧丰富的同时经 过加工的知识信息却相对匮乏，文本是互联网上主要的信息载体，因此文本挖掘 就成为数据挖掘中日益流行而重要的研究课题。文本分类技术是文本挖掘的基础 和核心。 2 0 世纪9 0 年代以后，基于机器学习的文本自动分类方法越来越成为主流，它 具有周期短，效率高，节省人力资源，分类结果一致性高等优点。但文本自动分 类研究自开展以来，准确率一直不能达到令人满意的效果。目前，i n t e r n e t 信息急 剧膨胀，文本分类有了广阔的发展空间，文本自动分类面临前所未有的机遇和挑 战，如何提高分类准确率成为研究热点。 朴素贝叶斯( n a i v eb a y e s ) 分类器是当前使用比较广泛的一种文本分类方法， 它应用统计理论进行文本分类。在朴素贝叶斯分类方法中，有一个“独立性假设”： 给定一个实例的类标签，实例中的每个属性的出现都独立于实例中其他属性的出 现，而在实际应用中这种条件并不易满足，另外由于文本的特殊性，相关的特征 项可能会产生新的语义信息，而在用传统的向量空间模型表示文本时该信息极有 可能丢失。 本文首先对文本分类系统以及贝叶斯分类模型作了分析和探讨，包括文本信息 的表示、提取，文本分类的方法以及贝叶斯方法用于文本分类的模型和算法。然 后针对上述朴素贝叶斯文本分类方法的不足之处，在训练文本时，对特征选择后 产生的特征项集用互信息方法考察它们相互之间的相关性，然后对相关程度较高 的特征进行适当的合并处理。在本文提出并实现的文本分类系统上，我们进行了 一系列的测试工作，并得到了严格的实验数据，这些实验数据都表明：这个改进 的文本分类系统可以获得更好的分类效果。 关键字：文本分类，独立性假设，相关性，互信息 重庆大学硕士学位论文 英文摘要 a b s t r a c t t h et a s ko fd a t am i n i n gi sm i n i n gu s e f u li n f o r m a t i o nf r o mam a s so fd a t a t e x t s m i n i n gi sb e c o m i n go n eo f t h ef o c u s e so f d a t am i n i n gw i t ht h er a p i dd e v e l o p m e n to f t h e i n t e m e tb e c a u s et h a tt e x ti st h em a i ni n f o r m a t i o nc a r r i e ro fw e bp a g e s t h et e x t c l a s s i f i c a t i o ni st h eb a s ea n dc e n t e ro f t e x t sm i n i n g t h ea u t o m a t i cm e t h o do ft e x tc l a s s i f i c a t i o nb a s e do nm a c h i n el e a r n i n gw a s b e c o m i n gm a i ns t r e a ma f t e r1 9 9 0 ss t a g eb ys t a g e i th a ss h o r tp e r i o d ，h i 曲e f f i c i e n c y , a n dh i 曲c o n s i s t e n c yo ft h er e s u l t s t h o u g ha u t o m a t i ct e x tc l a s s i f i c a t i o nh a ss om a n y m e r i t s ，t h ea c c u r a c yo f i t sr e s u l t si sn o ts a t i s f i e dt i l ln o w t e x tc l a s s i f i c a t i o ng e t saw i d e s t a g ei nt h ea g eo ft h ei n f o r m a t i o ni ni n t e r n e ti n c r e a s i n gr a p i d l y i ti sc o n f r o n t e dw i t h o p p o r t u n i t i e sa n dc h a l l e n g e s ，a n dt h es t u d yf o c u s e sh o w t oi m p r o v et h ea c c u r a c yo ft h e t e x tc l a s s i f i c a t i o nr e s u l t n a i v eb a y e sc l a s s i f i e ri sp r o v e dt ob eo n eo ft h em o s te f f e c t i v ec l a s s i f i e ra n db e u s e dw i d e l yi ta p p l i e ss t a t i s t i c a lt h e o r yt ot e x tc l a s s i f i c a t i o n t h e r ei sa l l ”i n d e p e n d e n c e h y p o t h e s i s ”i nb a y e s i a nc l a s s i f i e rm e t h o d ：e x a m p l e so f t h ee m e r g e n c eo fe a c ha t t r i b u t e a r ei n d e p e n d e n tf r o mt h ee x a m p l e so fo t h e ra t t r i b u t e sa p p e a r , t h ep r a c t i c a la p p l i c a t i o n o fs u c hc o n d i t i o n sa r en o te a s i l ys a t i s f i e d ，a n db e c a u s eo ft h es p e c i a lv e r s i o no ft h e r e l a t e dc h a r a c t e r sm a yh a v en f f c rm e a n i n gi nas p e c i a lt e x t ； f i r s to fa i l ，t h hp a p e rd e s c r i b e dt e x tc l a s s i f i c a t i o ns y s t e m ，t h ec o n t e n ti n c l u d e st e x t i n f o r m a t i o ne x p r e s s i n g e x t r a c t i n ga n dt h em e t h o do ft e x tc l a s s i f i c a t i o n s u b s e q u e n t l y a r t i c l ed i s c u s s e db a y e sc l a s s i f i e rm o d e la n da i g o r i t h i n s p e c i f i c a l l yf o rb r e a k i n gt h ec o n f i n e o fi n d e p e n d e n c eh y p o t h e s i so nn a i v eb a y e sc l a s s i f i c a t i o nm e t h o d ，w h i l et r a i n i n gt h et e x t ，t h e h i g h e rc h a r a c t e r st o l e v a n ti n t e n s i t yc a r r i e so u ta m a l g a m a t i o n , t h ee x p e r i m e n t a ld a t ai n d i c a t e s ，t h i s i m p r o v e dm e t h o dc a l li m p r o v et h ea l g o r i t i a r aa c c u r a c ya p p r e c i a b l y k e y w o r d ：t e x tc l a s s i f i c a t i o n , i n d e p e n d e n c eh y p o t h e s i s ，r e l a t i v i t y ，m u t u a li n f o r m a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重鏖太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：厅洌钦签字日期：夕一7 年月季日 学位论文版权使用授权书 本学位论文作者完全了解重麽太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权 重废太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“”) 学位论文作者签名：角确每乏 签字日期：力汐7 年石月争日 导师签名：势玉芳 签字日期：知7 年月牛日 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 引言 二十世纪九十年代以来，i n t e r a c t 以惊人的速度发展起来，它容纳了海量的各 种类型的原始信息，包括文本信息、声音信息、图像信息等等。信息的高速增长 迫切要求信息处理技术的不断进步，自动文本分类系统是近年来信息处理领域的 一个很重要的方向。它能够依据文本的语义将大量的文本自动分门别类，从而更 好地帮助人们把握文本信息。 自动文本分类就是在给定的分类体系下，让计算机根据文本的内容确定与它相 关联的类别。自动文本分类属于人工智能技术和信息获取技术相结合的研究领域， 是基于内容的自动信息管理的核心技术。 1 2 文本分类问题 面对越来越多的网络信息，采用人工进行分类，不仅费时，而且费事，已远远 不能满足当前的需求。因此，自动文本分类技术成为了人们研究的焦点。文本分 类的任务就是按照预先定义的主题类别，为文档集合中的每个文档确定一个类别。 这样，用户不但能够方便地浏览文档，而且可以通过限制搜索范围来使文档的查 找更为容易。系统的输入是需要进行分类处理的大量文本，而系统的输出是与文 本关联的类别。 从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到 分类体系下已有的类别中，该映射可以是一一映射，也可以是一对多的映射，因 为某些文本不但可以同一个类别相关联，也可以同多个类别相关联。该映射用数 学公式表示如下： f ：a - - - h b 其中a = ( d 1 ，d 2 ，见) b = ( c 1 ，c 2 ，c 卅) ( 1 1 ) 即：a 为所有待分类的文本的集合，b 为给定分类体系下所有类别的集合，a 可以为无限集合，而b 必须为有限集合。 文本分类的映射规则f 是文本分类系统的关键，它是系统根据已经掌握的每 类若干样本的数据信息，总结出分类的规律性而建立的判别公式和判别规则。根 据系统使用的学习方法的不同，这些判别公式和判别规则也有所不同。在己经确 定的映射规则的基础上，系统在遇到新文本时，通过计算和判断，最终确定文本 相关的类别。 在上世纪九十年代以前，自动文本分类以知识工程的方法为主，根据领域专家 对给定文本集合的分类经验，人工提取出一组逻辑规则，作为计算机自动文本分 重庆大学硕士学位论文 1 绪论 类的依据。进入九十年代，基于统计的自动文本分类方法日益受到重视，它在准 确率和稳定性方面具有明显的优势。基于统计方法的自动文本分类模型如图1 1 所 示，系统使用训练样本进行特征选择和分类器训练。系统根据选择的特征形式化 待分类的输入样本，然后输入到分类器进行类别判定，最终得到输入样本的类别。 图1 1 基于统计方法的自动文本分类模型 f i 9 1 1a u t o m a t e dt e x tc l a s s i f i c a t i o nb a s e do nt h es t a t i s t i c a lm o d e l 1 2 1 文本分类的研究目的和意义 文本分类是大规模信息处理重要的应用技术之一。随着信息存储技术和通信技 术的迅猛发展，大量的文字信息开始以计算机可读的形式存在，并且其数量每天 仍在急剧增加。这些文字信息的内容包罗万象，用户往往只需要其中的很少一部 分。如果仅仅通过人工的手段对庞大的原始文档集进行组织和整理，不仅费时、 费力，效果也未必很理想；相比之下，如果能由计算机直接对文档信息进行过滤、 分类，把用户真正感兴趣的部分提交给用户，就能使用户从繁琐的文档处理工作 中解放出来，并能极大地提高信息的利用率。 在信息时代，文本分类技术越来越紧密地与其他信息技术相结合，多方位地更 好地为人类服务。搜索引擎是重要的网络信息查找工具，但是传统的搜索引擎检 索效果往往不尽如人意，而文本分类技术可以弥补传统搜索引擎的不足，可以过 滤用户并不需要的某些文章，并且可以将检索结果分门别类，使用户能够清晰地 发现自己感兴趣的内容。文本分类技术还可以参与到主动的信息推送服务中。在 传统的获取信息的技术中用户是主动方，由用户向信息服务系统提出要求，启动 信息服务工具，从信息库中查找信息，并向用户返回信息，在这种模式中，用户 可以说是主动地“拉动”信息；而与之相反的另一种形式是“推送”信息，在这种模式 中，用户是被动的，随着信息的增长，信息服务系统可以主动地将最新的信息推 送给用户。要想有效地做到这一点，信息服务系统必须具有将新信息分门别类的 能力，然后根据用户的要求分发出去。总之，在信息服务过程中，文本分类是一 项基本而重要的功能，它能够很好地帮助用户整理、获取信息，具有很重要的研 究价值。 2 重庆大学硕士学位论文1 绪论 1 2 2 文本分类的研究现状 在早期的文本自动分类中，主要采用了信息检索技术中经典的布尔模型对文本 进行分类，表示文本和类别的特征一般较少，分类的准确率不高，无法达到处理 大规模真实文本的实用目的。后来，随着对自然语言处理及人工智能技术的研究 日渐深入，曾经一度被当作信息检索问题进行研究的文本自动分类问题己经被视 为模式识别的一个特例进行研究。在目前的研究中，较为常用的手段是采用基于 统计的方法抽取文本特征，运用信息检索中的计算模型进行特征加权，采用模式 识别中的分类算法进行类别学习。 国外对于文本自动分类的研究开展较早，目前，文本自动分类己广泛的应用 于电子邮件分类、电子会议、数字图书馆、搜索引擎、信息检索等方面。 文本自动分类主要经历了四个发展阶段： 第一阶段0 9 5 8 1 9 6 4 ) ：研究文本自动分类的可能性； 第二阶段( 1 9 6 5 1 9 7 4 ) ：进入文本自动分类的实验性阶段； 第三阶段( 1 9 7 5 1 9 9 8 ) ：文本自动分类的实用性阶段； 第四阶段( 1 9 9 0 至今) ：因特网文本自动分类研究阶段。 在此期间，国外在文本分类技术以及相关领域进行了较为深入的研究，取得了 不少令人注目的研究成果，并产生了一些可用的分类系统。例如，自动分类新闻 稿件的文本分类器 l e w i s1 9 9 4 2 1 ；自动分类w e b 页的文本分类器 c r a v e n1 9 9 8 】 3 1 。 国内对于文本自动分类的研究起步相对较晚，而目前国内对于中文文本分类的 研究尚存在着许多待解决的问题，如： 缺少标准、开放的分类测试数据集可供使用，各研究者大多使用自己建立的 数据集进行训练和测试，其结果没有可比性和可重复性，不便于交流与提高。 分词是影响中文文本分类的重要因素之一，分词的速度与准确率都制约着最 终的分类结果。尤其是互联网上不断出现新词汇，相应的信息处理中对通用性词 典的构建和词典的完备性提出了较高的要求。 特征选择是文本自动分类过程中的关键技术。需要结合特定的分类算法对其 进行更深入的研究。 1 2 3 贝叶斯方法与文本分类 文本分类是数据挖掘学科中的一种应用。数据挖掘有多种实现技术，如：数据 概念汇总归纳、决策树方法、神经网络方法、贝叶斯方法等。其中贝叶斯方法以 统计学为理论基础，其特点是使用概率去表示所有形式的不确定性，学习和推理 都用概率规则来实现，是数据挖掘中的一个重要方法。 与非贝叶斯方法相比，贝叶斯方法的突出特点是其学习机制可以综合先验信息 3 重庆大学硕士学位论文1 绪论 和后验信息，既可避免只使用先验信息可能带来的主观偏见和缺乏样本信息时的 大量盲目搜索与计算，也可避免只使用样本信息带来的噪音的影响。只要合理地 确定先验，就可以进行有效的学习。它在数据挖掘的各个领域都有着广泛的应用， 如：分类、聚类、偏差分析与预测等。目前，贝叶斯方法己经在信息检索模型建立、 信息提取、网络入侵检测等领域取得了较为成功的应用。而本文则针对贝叶斯分 类器在文本分类中的应用问题进行研究。 1 3 本文的研究内容和组织结构 1 3 1 本文的研究内容 本文的研究内容主要包括以下几个方面： 向量空间模型以及特征选择的研究 在向量空间模型的基础上，针对贝叶斯文本分类的特性，对现有的特征选取方 法进行研究讨论，选择合适的特征选择算法 朴素贝叶斯文本分类模型的讨论及其改进 在朴素贝叶斯分类方法中，有一个“独立性假设”【习：给定一个实例的类标签，实 例中的每个属性的出现都独立于实例中其他属性的出现，而在实际应用中这种条 件并不易满足，另外由于文本的特殊性，相关的特征项可能会产生新的语义信息， 而在用传统基于向量空间模型的朴素贝叶斯方法训练文本时该信息极有可能丢 失。因此在训练文本时，对特征选择后产生的特征集用一种简单可行的方法考察 它们相互之间的相关性，使基于特征独立性假设的b a y e s 方法分类效果提高，本 文采用了互信息方法对特征项进行考察，并对相关性较高的特征项进行归并处理 来达到这一目标 研究未标记文档对贝叶斯文本分类性能的影响 在现有的b a y e s 文本分类方法上进行改进，使之可以在初始训练文档集很小的 情况下在分类过程中提高自身的分类性能，用最大期望( e m ) 算法【3 9 】结合b a y e s 方法进行文本分类可以使在初始训练集很小的情况下结合未标记的文档来提高分 类性能，但是这种方法效率太低，可以考虑一个折衷的方法来实现提高分类系统性 能，同时效率也不会受到太大影响的方法，探讨自反馈与本文研究改进的贝叶斯分 类方法结合来提高分类性能的可行性。 1 3 2 本文的组织结构 本文的组织如下： 第一章为绪论，简单介绍文本分类课题的研究内容和意义及文本分类课题的研 究现状，同时介绍本文的研究内容，并罗列本文的章节安排。 第二章将概括性地介绍基于向量空间模型的文本分类系统。主要内容包括两个 4 重庆大学硕士学位论文 1 绪论 部分：向量空间模型简介和文本分类系统的算法描述。第一部分主要讨论了向量 空间模型的基本概念，并讨论了文本预处理中的分词算法，特征项选择算法及特 征项权重的计算方法。第二个部分介绍了各种文本分类算法，包括：k _ 近邻算法、 支持向量机算法、类中心向量最近距离判别算法及其他算法，给出了算法的理论 基础和算法公式。 第三章系统介绍了贝叶斯分类的基本理论，详细阐述并分析了几种常用的贝叶 斯分类模型：朴素贝叶斯分类模型、贝叶斯网络模型及t a n 贝叶斯分类模型等。 第四章是本文的核心内容。通过分析朴素贝叶斯文本分类模型和其改进模型， 研究讨论属性相关性度量，并提出一种改进贝叶斯文本分类模型，对朴素贝叶斯 分类模型的结构进行了扩展，其目的是为了突破朴素贝叶斯分类模型特征属性间 独立性假设限制，提高分类性能，并探讨反馈系统与贝叶斯文本分类模型结合的 可行性。 第五章描述了基于向量空间模型的贝叶斯文本分类系统的结构，给出了结构模 块图，并描述了系统中采用的关键算法，同时介绍了系统的实现，针对实验结果， 本文进行了一定的分析和预测。 第六章总结全文，并讨论了进一步的工作。 5 重庆大学硕士学位论文2 基于向量空间模型的文本分类算法 2 基于向量空间模型的文本分类算法 2 1 文本预处理和向量空间模型 与数据库中的结构化数据相比，文本信息具有有限的结构，或者根本没有结构。 即使具有一些结构，也是着重于格式，而非文档内容。不同类型的文档的结构也 不一致。此外，文档的内容是人类所使用的自然语言，计算机很难处理其语义。 文本信息源的这些特殊性使得现有的数据挖掘技术无法直接应用于其上。目前， 在信息处理中，文本的表示主要采用向量空间模型( v e c t o rs p a c em o d e l ，简称 v s m ) 呻】。v s m 是s a l t o n 等人于上个世纪6 0 年代首先提出的，并在著名的s m a r t ( s y s t e mf o r t h em a n i p u l a t i o na n dr e t r i e v a lo f t e x t ) 系统得到成功的应用。目前，该模 型及其相关技术，包括项的选择、加权策略，以及采用相关反馈进行优化查询等 在文本分类、自动索引、信息检索等诸多领域得到广泛的应用，并取得了较好的 效果。 2 1 1 分词 在使用向量空间模型表示文本时，是以特征项为基本单位的，特征项可以取字、 词或短语，所以，要对文本进行相应的预处理操作，提取出特征值序列。在汉语 中，词是最小的、能独立活动的，有意义的语言成分，中文信息处理系统只要涉 及句法、语义( 如检索、翻译、文摘、校对等应用) ，就需要以词为基本单位，而文 本分类算法也一般采用词作为特征项表示文本。 自动分词是针对中文的一种自然语言处理技术。中文与英文不同，句子中各个 词条间没有固定的分割，因此首先需要对中文文本进行分词。分词是指将大字符 集上的连续字串分割成能够代表语义单元的词或者n 元词条。自动分词是中文文 本自动分类的基础，自动分词过程也是原始文本特征集的确定过程。自动分词问 题是中文信息处理的首要问题与难点，它是一切工作的基础，分词不当，必将对 后续的处理工作产生严重的影响。目前的分词算法一般分为以下三类： 机械分词 机械分词指的是依据词典，按一定的策略将汉字串与词典中的词逐一匹配，如 果匹配成功，就加以切分。按照优先匹配的词长和扫描方向的不同，有四种常见 方案，即正向最大匹配、正向最小匹配、逆向最大匹配和逆向最小匹配。机械分 词方法简单，易于实现。但是由于自然语言丰富的表达方式，汉语句法构成的复 杂性，新词汇的不断涌现，使得机械分词法面临着很多问题。如：一词多义问题、 歧义切分问题和未登录词识别问题，仅用机械分词方法都不能够很好地解决，这 些问题直接影响了分词的准确率。 6 重庆大学硕士学位论文2 基于向量空间模型的文本分类算法 基于理解的分词 通常的分析系统，都力图在分词阶段消除所有歧义切分现象。而有些系统则在 后续过程中来处理歧义切分问题，其分词过程只是整个语言理解过程的一小部分。 其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来 处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。 在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来 对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用 大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信 息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。 基于统计的分词 这种分词方法利用了一种基于统计学的n g r a m 技术，根据相邻字的共现频率 自动提取特征，使文本数据分类实现了分类的领域无关性和时间无关性。它无需 任何词典支持，对输入文本所需的先验知识少。但是，在进行n g r a m 信息提取时， 会产生非常大的数据冗余，时间代价较大，相比基于词典分词获取文本特征的方 法，其实现效率比较低。实际应用的统计分词系统都要使用一部基本的分词词典( 常 用词词典) 进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和 串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典 分词结合上下文识别生词、自动消除歧义的优点。 2 1 2 向量表示 所谓向量空间模型f v s m ) 就是用一个向量来表示一个文本的信息，使得文本成 为特征空间中的一个点。在向量空间模型中文本集合形成一个矩阵，也就是特征 空间中点的集合。词频矩阵就是应用向量空间模型表示文本的一种形式，文本被 看作是一系列项t 的集合。对每个项t ，可以加上一个对应的权值w ，这样将文 档表示为加权的特征向量：d = d ( 正，；正，；瓦，呒；) ，其中d 表示文档，t 表示特征项，对应得w 表示为该特征项的权重。这样文档就由形如 的对组成。每篇文档d 都可映射成此空间上的一个特征向量。 2 1 3 特征选择 通过自动分词对文本进行处理后将得到原始文本特征集，在这些词中，有一些 高频词，如助词、虚词，连词等不包含语义，通常将其作为停用词直接删去。经 过处理后的特征集合仍然是庞大的，常常有数万维。所以，有必要进一步对文本 特征空间进行降维处理，其主要目的是提高分类效率，同时也可降低训练数据与 分类器的过度拟合。多项研究表明，使用压缩后的特征向量来表示文本，不但不 会降低分类系统的分类性能，而且还可能提高分类的精度【”。 特征选择主要用于排除与类别无关或关联性不大的特征。它常采用特征独立性 7 重庆大学硕士学位论文2 基于向量空间模型的文本分类算法 假设来简化选择过程，达到计算时间和计算质量之间的折衷。一般的做法是采用 某种评估函数对每个文本特征独立打分，按降序保留预定数目的特征项。 特征子集的选取有多种算法，多数特征子集选取算法的思想是构造一个评价函 数，对特征集中得每个特征进行独立的评估，这样每个特征都获得一个评估分， 然后对所以的特征按照其评估分大小进行排序，选取预定数目的最佳特征作为结 果的特征子集。以下介绍目前在文本分类中经常使用的特征选择算法： 文档频率( d o c u m e n tf r e q u e n c y , d f ) 文档频率通过计算训练集中包含特征项t 的文档数目进行特征选择。设p i 为训练集文本总数，d 。为一训练文本，则有： 日 d f ( t ) = p ( t ，d ，) ( 2 1 ) 若t d 。，贝p ( t ，d ，) = 1 ；若t 仨d ，贝0 p ( t ，d f ) = 0 。 其应用的理论假设是：d f 较小的特征项( 稀有特征项) 对文档分类没有帮助，或 者对整体性能的影响很小。如果它恰巧是训练集中的噪音，去掉它还能够提高系 统分类的准确度。文档频率是最简单的特征选择技术，由于其具有相对于训练语 料规模的线性计算复杂度，能够容易地被用于大规模语料统计。但其缺陷是，被 筛选掉的稀有特征项可能在某一类文本中并不稀有，而且包含着重要的判断信息。 信息增益( i n f o r m a t i o ng a i n ，i g ) 信息增益是机器学习领域中常用的衡量特征项重要程度的指标，它通过文本特 征在文本中出现与不出现的情况来推算该特征项所带有的信息量，计算公式如 下： i g ( t ) = p ( c , ) l o g p ( c , ) + p ( t ) x p ( qi t ) l o g p ( c ，i f ) + 烈f ) p ( gl t ) l o g p ( ci i ) l = li = 1 1 = 1 ( 2 2 ) 其中p ( q ) 表示类别g 出现的概率，p ( t ) 表示特征项t 出现的概率，p ( gl t ) 表 示特征项t 在属于类别c l 的文档中出现的概率，尸( q i f ) 表示特征项t 在不属于类 别的文档中出现的概率。 互信息( m u t u a li n f o r m a t i o n , m i ) 互信息( m u t u a li n f o r m a t i o n ) 在统计语言模型中被广泛采用【8 】，互信息用于表征 两个变量的相关性，常被用来作为文本特征相关的统计模型及其相关应用的标准， 文本特征t 与类别c 的互信息m l ( t ，c t ) 定义如下： m l ( t , c f ) = l o g 等 ( 2 3 ) 其直观意义是：对于每个词t 以它在每个类别中的出现占它在整个文本集中的 重庆大学硕士学位论文2 基于向量空间模型的文本分类算法 出现的比率作为它对每个类别分类依据的贡献。互信息的缺点是特征分值受l 临界 特征的概率影响较大，从公式可以看出，当特征项的p ( tg ) 值相等时，出现频率 越小的特征项，它的m 1 分值越高：因此，频率相差太大的文本特征分值不具有可 比性。 x 2 估计( x 2 - t e s t ，c h i ) c h i 方法度量特征项t 和文档类别c ，之间的相关程度，并假设t 和c f 之间符合 具有一阶自由度的工2 分布。词条对于某类的x 2 统计值越高，它与该类之间的相关 性越大，携带的类别信息也较多。 以幅，= 盟笺器器乎盟 晓4 ， g a l a v o t t il 等人提出了一个简化的工2 算法【9 】： x 2 ( f ，g ) = p ( t ，c 1 ) 尸( ，i ，c t ) - p ( t ，q ) 仃，c i ) ( 2 5 ) 文本证据权( w e i g h to f e v i d e n c ef o rt e x t ，w e t ) 文证据权的计算公式如下： w e t 以驴驯l o g 器器踹i 眨a ， 文本证据权是一种较新的评估函数，它衡量类的概率和给定特征时类的条件 概率之间的差别。如果词条和类别强相关p ( c ii f ) 大，并且相应类别出现的概率小， 说明这时词条对分类的影响大，计算出的函数值就大，可选取作为特征项。或者 如果类别出现的概率大，而词条又和类别弱相关p ( gl f ) 小，说明这时词条对分类 的影响小，计算出的函数值就小，不会被选取作为特征项。 事实上，在具体的分类问题中选择哪一个特征选择方法效果会更好，此问题并 没有定论。随着数据集和分类算法的不同，各特征选择方法的表现也会有所差异。 2 2 基于向量空间模型的文本分类方法 文本分类的方法基本上可分为两大类：第一类方法是人工的方法，早期通过构 造与专家系统中的分类或诊断系统类似的系统进行：由知识工程师在输入的文木表 示与输出的类别间定义一个或多个中间层，提供规则在各层的结论( c o n c l u s i o n ) 之 间进行映射【l o 】。 第二类方法属于归纳学( i n d u c t i v el e a r n i n g ) 的范畴，它从大规模的语料库中归 纳计算出类别概念，一般采用统计的方法进行。训练方法和分类算法是分类系统 的核心部分，目前存在多种基于向量空间模型的训练算法和分类算法。这些方法 包括贝叶斯分类( b a y e s i a nc l a s s i f i c a t i o n ) ，k - 最近距离( k - n e a r e s t - n e i g h b o r ) ，决策树 9 重庆大学硕士学位论文2 基于向量空间模型的文本分类算法 ( d e c i s i o nt r e e s ) 、因素分析( f a c t o ra n a l y s i s ) 、模糊集( f u z z ys e t s ) ，线性回退( 1 i n e a r r e g r e s s i o n ) 等。基于学习的系统比第一种系统更容易建立，在一些应用中结果更加 精确。本文研究的重点内容是贝叶斯文本分类，在第三章和第四章将对贝叶斯文 本分类方法作详细的介绍和分析，本节以下将介绍除贝叶斯方法以外的多种基于 向量空间模型的分类算法。 2 2 1 简单距离向量判别法 该方法的思路十分简单，根据算术平均为每类文本集生成一个代表该类的中心 向量，然后在新文本来到时，确定新文本向量，计算该向量与每类中心向量间的 距离( 相似度) ，最后判定文本属于文本距离最近的类。 计算新文本特征向量和每类中心向量间的相似度的公式为： s i m f = ( 2 7 ) 公式中，s i m 。表示新文本特征向量i 与第j 类中心向量的相似度，m 为特征向 量的维数，阡0 为向量i 的第k 维。比较每类中心向量与新文本的相似度，将文本 分到相似度最大的那个类别中。 2 2 2 k n n 算法 k 最近邻居算法( kn e a r e s tn e i g h b o rc l a s s i f i e r s ，k n n ) 在基本思想是，在给定新 文本后，考虑在训练文本集中与该类文本距离最近的k 篇文本，根据这k 篇文本 的所属类别判定新文本所属的类别。k 最近邻居算法是基于机械学习的分类算法。 机械学习是最简单的机器学习算法，它的实质就是记忆，即把新的知识存储起来， 供需要时使用，而不需要计算和推理。虽然机械学习在方法上看来很简单，但由 于计算机的存储容量相当大，检索速度又相当快，而且记忆精确，无丝毫误差， 所以也能产生很不错的效果。当前很多的弈棋程序都采用了这种机械记忆策略， 在与人对弈的过程中，计算机搜索棋局，选择得分最高的棋局。 k - 近邻算法的训练过程十分简单，它仅仅存储文本向量和文本对应的类别，而 不进行归纳和分析，即不从训练样本中发掘类别的含义。换句话说，它允许类中 全部样本点都具有代表类的资格。 当新文本到达时，该算法计算新文本与所有样本点之间的距离，选择k 个距 离最近的样本点，然后检查这些样本点的类别，按公式计算每个类别的比重值， 将新文本归入比重最大的一类中。 2 2 3 归纳逻辑方法 按逻辑的观点来看，文本分类的过程实际上是通过对训练文本的学习，归纳出 1 0 重庆大学硕士学位论文2 基于向量空间模型的文本分类算法 分类规则，应用到测试文本，从而将测试文本分类。学习的目的是构造一个逻辑 程序，该程序根据一些基本关系和目标关系本身( 递归定义) ，给出目标关系的定义， 这些定义便是归纳出的规则【1 l 】。 决策树实际上是一种0 阶学习，归纳逻辑( i n d u c t i v el o s i c ) 文本分类方法主要研 究的是1 阶学习方法。1 阶学习与0 阶学习的区别在于：属性之上还存在关系 ( r e l a t i o n ) ，属性只是关系的参数，规则是关系间一对多的映射，训练数据用正负元 组( ( t u p l e ) 表示。 2 2 4 支持向量机算法 支持向量机( s u p p o r tv e c t o rm a c h i n e s ) 是由vv a p n i k 与其领导的贝尔实验室的 小组【1 4 】一起开发出来的一种新的机器学习技术。s v m 的理论基础来自于v a p n i k 等提出的统计学习理论，它的基本思想是，对于一个给定的具有有限数量训练样 本的学习任务，如何在准确性和机器容量( 机器可无错误地学习任意训练集的能力) 间进行折衷，以得到最佳的推广( g e n e r a l i z a t i o n ) 性能。 支持向量机的主要思想是针对两类分类问题，在高维空间中寻找一个超平面作 为两类的分割，以保证最小的分类错误率。而目支持向量机的一个重要的优点是 可以处理线性不可分的情况。y a n g 曾经做过实验，发现s v m 处理线性不可分问 题比处理线性可分问题相差无几【”】。 s v m 方法具有两个主要优点：一、训练集可动态变化。除k n n 方法外，其余 的分类方法在训练集变化时，都要全部重新计算。这使得s v m 方法能够适应文木 波动较大的环境。二、特征选择步骤成为可选。特征选择是一个耗费计算的步骤， 其他分类方法的结果很大程度上依赖特征选择的结果，而在s v m 方法中，分类过 程与特征集的大小无关。我们知道，文木分类是一个大训练集的学习过程，其特 征集的大小对以往分类方法的计算有很大影响，这使得s v m 方法在这个领域具有 很大的优势。 2 2 5 其他文本分类方法 除了以上讨论的分类算法外，目前尚在研究的分类算法还包括i d 3 决策树算 法、神经网络算法、r o c c h i o 算法等等，下面简单介绍一下决策树和神经网络算法： d 3 决策树算法 i d 3 是q u l i a n 于1 9 8 6 年提出的一种重要的归纳学习算法。它具有以下三个 特点：使用一棵分类决策树表示学习结果；决策树的每个节点都是样本的某个属 性，采用信息熵作为节点的选择依据；采用了有效的增量学习策略。决策树相比 贝叶斯方法有一个突出的优点，即它没有贝叶斯方法中的独立假设前提，该前提 我们在第四章详细介绍。决策树将特征按属性分割成一个个子集，子集中的各特 征之间是或的关系，仅需要在这个子集当中估计成员之间的概率分布，而这是不 重庆大学硕士学位论文2 基丁二向量空间模型的文本分类算法 需要独立假设的。 神经网络算法 神经网络领域采用感知算法进行分类。r o s e n b l a t t 于1 9 5 7 年采用感知机模型 来解决机器人的感知问题，在这种模型中，分类知识被隐式地存储于连接的权值 上，使用迭代算法来确定权值向量。当网络输出判别正确时，权值向量保持不变， 否则进行增加或降低的调整，因此也称为奖惩法。 可以证明，对于线形可分的情况，感知判别算法是收敛的。对于线形不可分的 情况，一般都是不收敛的，可以采用最小均方误差准则。神经网络分类器的一个 首要问题就是确定神经网络的结构，不良结构会使得训练过程很慢或根本不收敛。 现在有些学者正致力于神经网络结构的演化研究。 2 3 文本分类的评价方法 性能评价在文本自动分类中具有非常重要的作用，特征选择和分类器训练都需 要调用评价方法，分类系统的训练过程也是以评价方法作为依据进行的。文本分 类的目标是用计算机使文本分类更准确，系统输出的结果与专家分类结果越相近， 分类的准确程度就越高，对文本分类系统评价所采用的指标主要有准确率 ( p r e c i s i o n ) 和召回率( r e c a l l ) 等。除了上述两项指标外，还采用了收益率( o a i n ) 、分 类正确率( c l a s s i f i c a t i o n ) 、准确率与召回率的几何平均数、信息估计值等来衡量分 类器的性能。一般用准确率、召回率、f 值衡量系统的性能。 准确率是所有输入系统进行分类处理的文本中与专家分类结果完全吻合的文 本所占的比率，其数学公式表示如下： 准确率( p r e c i s i o n ) = 二 脚 其中l 为分类正确的文本数，而m 为分类系统实际分类的文本数。 召回率是类别中应有文本中被分类系统分类正确的文本所占的比率，其数学公 式表示如下： 召回率( m t t ) ：一l n ， 其中l 同准确率中l 的定义相同，而n 为应有文本数。 结合这两个指标产生出一种新的评估指标，f 1 测试值，我们也称之为综合分 类率，其数学公式如下： 砌撇c ”篆等 1 2 重庆大学硕士学位论文2 基于向量空间模型的文本分类算法 文本分类系统的精确度作为评价系统得标志，其重要性不言而喻，另外一方面如 果能在保证分类的精确度的同时，下面几点也是相当重要的： 模型的简洁性和可理解性 分类器模型越简洁越容易理解就越受到欢迎。 算法复杂度 在硬件条件限制下，时间复杂度和空间复杂度是一个重要的评估标准，比 如对内存的需求，或者算法的收敛性等。 鲁棒性 它反映了数据集在出现噪音数据或属性值空缺等情况下，分类器是否仍具 有正确的分类能力。 可伸缩性 大部分算法在训练时需要驻留在内存中，这将依赖于数据集的规模。在数 值实验中采用的数据集规模一般不大，但在实际应用中算法面临的是大规模数 据集特别是海量数据，这就意味着一个好的分类算法在硬件条件限制下具有很 好的伸缩性。 重庆大学硕士学位论文3 贝叶斯理论与贝叶斯分类方法 3 贝叶斯理论与贝叶斯分类方法 3 1 引言 贝叶斯学派是现代统计学中与经典频率学派并列的两大学派之一，贝叶斯数据 分析就是先验分布在经过了数据所提供的证据修订之后所形成的经验分布。英国 牧师t h o m a s b a y e s 在1 7 6 3 年提出了后来以他的名字命名的贝叶斯理论，他对贝叶 斯方法奠基性的工作是他的论文“关于几率性问题求解的评论”。当时由于贝叶斯方 法在理论和应用中还存在很多不完善的地方，因此在很长一段时间并未被普遍接 受。后来随着统计决策理论、信息论和经验贝叶斯方法等理论和方法的创立和应 用，贝叶斯方法很快显示出他的优点，成为十分活跃的一个方向。 在数据挖掘中，构造分类模型可以使用许多不同的方法，如决策树、贝叶斯分 类法、神经网络分类法等。通过对分类算法的比较研究发现，贝叶斯分类算法可 以与决策树算法和神经网络算法相媲美。基于贝叶斯方法的分类器由于以完善的 贝叶斯理论为基础，有较强的模型表示、学习和推理能力，使得基于贝叶斯方法 的分类器的研究和应用正成为模式识别、人工智能和数据挖掘等领域的研究热点。 对于大型数据库，朴素贝叶斯分类法也己表现出高准确率与高速度。贝叶斯分类 是统计学分类方法，是建立在经典的贝叶斯概率理