（计算机应用技术专业论文）贝叶斯文本分类器的研究与改进.pdf

太原理工大学硕士研究生学位论文 的改善贝叶斯的分类效果。 关键词：贝叶斯文本分类，数据稀疏，l a p l a c e 平滑方法， 统计语言模型，u n i g r a m 平滑方法 太原理工大学硕士研究生学位论文 r e s e a r c ha n di m p r o v e m e n t o nn a j f v eb a y e st e x tc l a s s i f i e r a b s t r a c t a 1 0 n g w i t ht h e d e v e l o p m e n t o fn e t w o r k i n f o m l a t i o n ， a u t o m a t i ci n f o n n a t i o nc l a s s i f i c a t i o nh a sb e e na ne s s e n t i a lt o o lt o g a i nu s e f u li n f o r m a t i o n a sac l a s s 湎c a t i o nm e t h o d ，n d eb a y e s c l a s s j 6 e rh a sb e e na p p l i e dt om a n yf i e l d s t h ea d v a n t a g eo fn a w e b a y e sm e t h o dl i e si nt h eu s a g eo fp r i o ri n f b 衄a t i o n ，w h i c hc o u l d p r o v i d eap a t t e ma n dm a n a g e m e n tm e t h o du n d e rt h ei n c e r t i t u d e l o g i c f i r s to fa 1 1 ，t l l i sp 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 e c o n t e mi n c l u d e st e x ti n f i o 肌a t i o n e x p r e s s i n g 、e x t r a c t i n ga n dt h e m e t h o do ft e x tc l a s s m c a t i o n s u b s e q u e n t i ya r t i c l ed i s c u s s e db a y e s c l a s s i f i e rm o d e la n da 】g o r i m m _ a n d t h e n ，t h i sp a p e ri n t r o d u c e dd a t as p a 】笃ec o n d i t i o no fb a y e s c l a s s i 丘e r d i s a d v a n t a g eo fl a p l a c es m o o t h i n gu s e db yt r a d i t i o n a l n a r v eb a y e sc l a s s i n e rh a sb e e np o i n t e do u t ，a n o t h e rs m o o t h i n g m e t h o di sa d v i s e dt or e p l a c el a p l a c e t h ea d v i s e dm e t h o dj u s ti s s t a t i s t i c a l l a n g u a g em o d e l ( u f l i - g r a m ) s m o o t h i n g ：j e l i n e k - m e r c e r t 太原理工大学硕士研究生学位论文 s m o o t h i n g 、d i “c h i e t s m o o t h i n g a n d a b s o l u t e d i s c o u n t i n g s m o o t h i n g m o s t l y ， w eh a v e i m p r o v e db a y e s c l a s s i f i e rw i t hn e w s m o o t h i n gm e t h o d so fs t a t i s t i c a l l a n g u a g em o d e l ，t h a ti st os a 弘w e r e p l a c e dl 印l a c es m o o t h i n g o ft r a d i t i o n a lb a y e sc l a s s i f i e rw i t ho t h e r t h i e e s m o o t h i n gm e t h o d so fu n i g r 锄m o d e l s p e c m ca l g o r i t h m a n d 丹a m e w o r kh a v eb e e ns h o w n i no r d e rt oa f f i n no u rw o r k ，w e t e s tt h r e e u n i g m ms m o o t h i n gu s e d i n b a y e sc l a s s m e r ，s e l e c t s u i t a b l ep a r a m e t e rv a l u e o u re x p e r i m e n t a lr e s u l t ss h o wm a tu s i n g al a n g u a g em o d e l ，w ea r ea b l et oo b t a j nb e t t e rp e r f 0 瑚a n c et h a n t r a d i t i o n a ln 幻v eb a y e sc l a s s i f i e r i nt h e如t u r e ，w es h o u l d i m p r o v eb a y e s c l a s s i f i e rw i t h s t a t i s t i c a l l a n g u a g em o d e l ( b i g r a mm o d e la n dt t i g r a mm o d e l ) s m o o t h i n g k e yw o r d s ：n a 如eb a y e st e x tc l a s s i 6 e r ，d a t as p a r s e ，1 a p l a c e s m o o t h i n g ，s t a t i s t i c a a n g u a g em o d e l ，u n i g r a ms m o o t h i n g i v 太原理工大学硕士研究生学位论文 第一章绪论 1 1 文本分类系统介绍 随着计算机技术和通讯技术的飞速发展，人们可以获得越来越多的数 字化信息，但同时也需要投入更多的时间对信息进行组织和整理。为了减 轻这种负担，人们开始研究使用计算机对文本进行自动分类。近年来，文 本分类成为信息处理领域的一个很重要的方向。它能够将大量的文本自动 分门别类，从而更好的帮助人们把握信息。 自动文本分类就是在给定的分类体系下，让计算机根据文本的内容确 定与它相关联的类别。自动文本分类属于人工智能技术和信息获取技术相 结合的研究领域，是基于内容的自动信息管理的核心技术。国外在自动文 本分类以及相关的信息检索、信息抽取等领域进行了较为深入的研究。八 十年代，自动文本分类以知识工程的方法为主，根据领域专家对给定文本 集合的分类经验，人工提取出一组逻辑规则，作为计算机自动文本分类的 依据。进入九十年代，基于统计的自动文本分类方法日益受到重视，它在 准确率和稳定性方面具有明显的优势。基于统计方法的自动文本分类模型 如图1 - 1 所示，系统使用训练样本进行特征选择和分类器训练。系统根据 选择的特征形式化待分类的输入样本，然后输入到分类器进行类别判定， 最终得到输入样本的类别。 太原理工大学硕士研究生学位论文 图卜l 基于统计方法的自动文本分类模型 f i g u r ei - la 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 l e mb a s e ds t a t i s t i c a lm e l b o d 用简单而准确的方法将文档表示成计算机能够处理的形式是进行文 本分类的基础。最经典文本形式化表示方法是6 0 年代末s a l t o n 等人提出 的向量空间模型( v s m ：v e c t o rs p a c em o d e l ) j 1 】，它成功地被用于著名的 s m a r t 文本检索系统。向量空间模型将文本表示成特征项和特征项权重 组成的向量，使用余弦函数进行距离度量。此外还有语义网络、框架模型 等表示方法。 在基于统计方法的自动文本分类中，不同的特征项对于文档的重要性 和区分度是不同的，通常高频特征项在多个类中出现，并且分布较为均匀， 因此区分度较小；而低频特征项由于对文档向量的贡献较小，因此重要性 较低。去除区分度较小的噪音特征项可以提高分类准确率，去除重要性较 低的低频特征项可以加快运行速度。常用的特征选择方法有文档频次、互 信息、信息增益、统计量等方法。 在分类器构造上，早期多使用基于知识工程的规则方法，卡耐基集团 基于此方法为路透社开发的c o n s t r u e 系统【2 较早地进入了实用阶段，它每 天对路透社成千上万的稿件进行自动分类。现在主要使用基于统计的方 法，如朴素贝叶斯( n a y v eb a y e s ) 、k 近邻( k - n e a r e s tn e i g h b o u r s ) 、支持向 量机( s u p p o r tv e c t o rm a c h i n e ) 等。 在系统评价上，英文文档自动分类建立了r e u t e r s 、o h s u m e d 、 n e w s g r o u p s 等标准的分类语料，其中r e u t e r s n 料库的2 1 5 7 9 版本【3 】使用最 太原理工大学硕士研究生学位论文 为广泛。t r e c 测试也提供了标准的语料库 4 1 。除了经典的训练一测试 ( t r a i n - a n d ，t e s t ) 方法，目前使用较多的是k 分交叉评价( k - f o l d c r o s s v a l i d a t i o n ) 方法，目的是充分利用初始样本进行训练。它将初始样本 集合t 分成k 份扭1 ，t 2 ，t k ，t m n _ t - t i ，t t e s f j i = 1 ，2 k ，最后将k 次测试 的平均值作为最终结果。最严格也是最精确的交叉评价方法是l o o ( l e a v e o n eo u t ) 方法，假设有m 个样本，每次使用一个样本作为测试样本，其余的 样本都作为训练样本，最后将m 次测试的平均值作为最终结果。自动文本 分类系统的两个常用评价指标是准确率( p r e c i s i o n = l l m ) j 1 召回率( r e c a l l = i n ) ，其中i 为分类正确的文本数，m 为确定了类别的文本数，n 为待分类的 总文本数。综合考虑准确率和召回率，可以得到新的评估指标f t 测试值， 也称为综合分类率，计算公式如下： f ：p r e c i s i o nx r e c a l l x2 p r e c i s i o n + r e c a l l 当m = n 时，准确率= 召回率= 综合分类率。 系统分类的准确程度( 准确率、查全率和f - 测试值) 作为评价系统 性能的标志通常十分受到学者的重视，而同样重要的系统效率( 系统映射 速度) 问题却没有得到足够的重视，m u c ( 信息理解会议) 和t r e c ( 文 本检索会议) 也都未曾把响应时间等作为系统评测的标准【5 1 。而实际上， 效率和性能对于应用系统而言是同样重要的，如果能在不削弱性能的前提 下，较大程度地提高系统的响应速度，就是极有意义的工作。 1 2 贝叶斯分类的发展 目前较为著名的文本分类方法有b a y e s 、l l s f 、s v m 、k n n 、决策树 等。贝叶斯( b a y e s ) 分类方法是一种最常用的有指导的方法，以贝叶斯 定理为理论基础，是一种在已知先验概率与条件概率的情况下的模式识别 3 太原理工大学硕士研究生学位论文 方法。 1 2 1贝叶斯理论的起源 贝叶斯学派是现代统计学中于经典频率学派并列的两大学派之一，贝 叶斯数据分析就是先验分布在经过了数据所提供的证据修订之后所形成 的经验分布。英国牧师t h o m a sb a y e s 在1 7 6 3 年提出了后来以他的名字命 名的贝叶斯理论，他对贝叶斯方法奠基性的工作是他的论文“关于几率性 问题求解的评论”。当时由于贝叶斯方法在理论和应用中还存在很多不完 善的地方，因此在很长一段时间并未被普遍接受。后来随着统计决策理论、 信息论和经验贝叶斯方法等理论和方法的创立和应用，贝叶斯方法很快显 示出他的优点，成为十分活跃的一个方向。 贝叶斯的理论可以粗略地被简述成一条原则：为了预见未来，必须要 看看过去。贝叶斯的理论表示未来某件事情发生的概率可以通过计算它过 去发生的频率来估计。贝叶斯表示从本质上说，每件事都有不确定性，有 不同的概率类型( 斯坦佛教授r o n h o w a r d ) 。例如，一名研究人员把塑料 图钉往上抛，想要看看它钉头朝上落地的概率有多大，或者有多少可能性 是侧面着地，而钉子是指向什么方向的。形状，成型过程中的误差。重量 分布和其他的因素都会影响该结果。 1 ，2 2 贝叶斯理论的研究目的和意义 贝叶斯技术的吸引力在于它的简单性。预测完全取决于收集到的数 据，获得的数据越多，结果就越好。另一个优点在于贝叶斯模型能够自我 纠正，也就是说数据变化了，结果也就跟着变化。 目前，有不少的文本分类系统采用了b a y e s 算法，例如，文献【6 和 7 】都取得了不错的效果。 搜索引擎g o o g l e 和a u t o n o m y ，一家出售信息恢复工具的公司，都使 用了贝叶斯定理为数据搜索提供近似的( 但是技术上不确切) 结果。贝叶 太原理工大学硕士研究生学位论文 斯理论的一个出名的倡导者就是微软。该公司把概率用于它的n o t i f i c a t i o n p l a t f o r m 。该技术将会被内置到微软未来的软件中，而且让计算机和蜂窝 电话能够自动地过滤信息，不需要用户帮助，自动计划会议并且和其他人 联系。 威斯康星州a r t e s y n 公司的高级技术专家将贝叶斯模块添加到 s p a m a s s a s s i n 系统中，使s p a m a s s a s s i n 的过滤功能更加优异，贝叶斯已经 成为该公司对付垃圾邮件不可或缺的技术。开发出早期源代码贝叶斯垃圾 邮件过滤器的独立程序员p a u lg r a h a r n 称，贝叶斯过滤技术的基础是一种 对文档进行分类的算法。由于垃圾邮件制造者都必须或多或少说明其信息 性质的内容，所以即使垃圾邮件制造者使用哪一种欺骗技巧，贝叶斯技术 都可以根据其内容进行智能分类。在垃圾邮件内容过滤中，经常使用简单 贝叶斯分类算法。如s t a n f o r d u n i v e r s i t y 的s a h a m i ( 1 9 9 8 ) 、希腊n a t i o n a l c e n t r ef o rs c i e n t i f i cr e s e a r c h “d e m o k r i t o s ”的a n d r o u t s o p o u l o s ( 2 0 0 0 ) 、p a u l g r a h a m ( 2 0 0 2 ) 、d a v i dm e r t z ( 2 0 0 2 ) 等。他们的实验表明，简单贝叶斯 分类算法用于垃圾邮件过滤的效果比较好。 1 ，2 3 贝叶斯理论的研究现状 贝叶斯分类器分两种：一种是朴素贝叶斯分类器，它假设一个属性对给 定类的影响独立于其他属性，即特征独立性假设。当假设成立时，与其他分 类算法相比，朴素贝叶斯分类器是最精确的。但是，文本属性之间的依赖关 系是可能存在的。另一种是贝叶斯网络分类器。可以考虑属性之间的依 赖程度，其计算复杂度比朴素贝叶斯高得多，更能反映真实文本的情况。贝 叶斯网络分类器实现十分复杂，目前还停留在理论的研究阶段。 朴素贝叶斯分类已经用在了文本分类和信息检索的很多领域，虽然它 的分类效果相当不错，但都是在特征独立的假设基础上的。近几年， p e n g f u c h u n 8 等人已经在作这方面的研究，应用统计语言的n 元模型来 太原理工大学硕士研究生学位论文 改善贝叶斯的特征独立状况。 贝叶斯分类的数据稀疏也是一个不容忽视的问题，这方面的研究一直 有人在作，到目前为止，在贝叶斯分类的应用领域依然在沿用l a p l a c e 平滑 技术处理数据稀疏问题。 1 3 本文的内容 1 3 1 研究内容 本文的研究内容主要包括以下几个方面： 1 、贝叶斯文本分类模型的讨论以及平滑技术的改进 分析了贝叶斯文本分类的两种模型一贝努力模型和多项式模型，最终采 用多项式模型。为了改进贝叶斯分类的数据稀疏问题，笔者提出了采用统 计语言模型的u n i g r a m 平滑方法来处理贝叶斯的零概率问题，并将 u n i - g r a m 模型的三种平滑方法用于贝叶斯分类算法中。提出了具体的算法 与实现框图。 2 、改进了的贝叶斯分类器的实验分析 通过实验分析决定平滑算法的参数取值。比较改进了的贝叶斯分类器 与原来采用l a p l a c e 平滑的分类器的性能，提高了分类准确率和召回率。 1 3 2 本文的组织 本文的组织如下： 第一章为绪论，简单介绍文本分类系统和贝叶斯文本分类的研究目的 和意义以及研究现状，同时介绍本文的研究内容和章节安排。 第二章介绍贝叶斯文本分类系统。概括的介绍了文本分类系统，内容 包括文本信息的描述和词频特征提取，以及文本分类的方法。详细介绍了 贝叶斯文本分类模型。主要介绍了贝叶斯文本分类的多项式模型以及 太原理 二大学硕士研究生学位论文 l a p l a c e 平滑算法。 第三章介绍了统计语言模型。其中包括n 元模型的平滑方式和 u n i g r a m 模型的平滑算法。 第四章用统计语言模型的平滑方法改进了贝叶斯分类器。分析了贝叶 斯分类器i 印l a c e 平滑技术的缺陷，提出了用u n i g r a m 的三种平滑方法来 改进分类器的零概率状况，并列出了具体的改进算法墓蠢鼙基鍪 囊荐鲥囊嶷趔裂粪孬彰而莉；蠹# 叁蓑雾型羹珥到髓篓篓惶假到淫羹藐麓 髯姑崔。 蓦拍髦丝嘉擎蕊；# 篓锈u 萋一躞雾荽辛： 荨 能存在的。另一种是贝叶斯网络分类器，可以考虑属性之阳j 的依 赖程度，其计算复杂度比朴素贝叶斯高得多，更能反映真实文本的情况。贝 太原理工大学硕士研究生学位论文 2 1 引言 第二章贝叶斯文本分类系统 文本分类就是将大量的文本归到不同的类别中去。面对越来越多的网 络信息。采用人工进行分类，不仅费时，而且费事，已远远不能满足当前 的需求。因此，自动文本分类技术成为了人们研究的焦点。文本分类的方 法有很多种，本文主要研究贝叶斯文本分类方法。 贝叶斯分类器分两种：一种是朴素贝叶斯分类器，它假设个属性对给 定类的影响独立于其他属性，即特征独立性假设。当假设成立时，与其他分 类算法相比，朴素贝叶斯分类器是最精确的。但是，文本属性之间的依赖关 系是可能存在的。另一种是贝叶斯网络分类器，可以考虑属性之阳j 的依 赖程度，其计算复杂度比朴素贝叶斯高得多，更能反映真实文本的情况。贝 叶斯网络分类器实现十分复杂，目前还停留在理论的研究阶段。本文采用第 种方法设计朴素贝叶斯分类器，解决文本分类问题。如不特别指明，下文 的贝叶斯分类均代表朴素贝叶斯分类。 本章主要讨论贝叶斯文本分类器的模型及算法，着重讨论贝叶斯用于 文本分类的算法和它的平滑技术。介绍贝叶斯分类前先介绍文本自动分类 的一些相关知识。 2 2 自动文本分类系统 太原理工大学硕士研究生学位论文 2 2 1 文本信息的描述及特征提取 本文讨论的文本采取向量空间模型表示。向量空问模型( v e c t o rs p a c e m o d e l ) 是由g s a l t o n 于1 9 8 8 年提出的。该模型在s m 削订系统中得到了成 功的应用，并且广泛应用于文本信息处理领域，是一个很成功的模型。 所谓向量空间模型( s v m ) 就是用一个向量来表示一个文本的信息，使 得文本成为特征空间中的一个点。在向量空间模型中文本集合形成一个矩 阵，也就是特征空间中点的集合。 词频矩阵就是应用向量空间模型表示文本的一种形式，其表示方法如 表2 - 1 所示： 表2 1 词频矩阵的表示方法 1 h b l e2 1t e r mf r e q u e n c va r r a v 在词频矩阵中，w o r d 是向量空间模型巾的特征项，口。是项的权重， 即第f 个词在第f 篇文本中出现的频率。 1 文本信息的描述 在囊薹集耄曼誉譬耋譬，嵯案寝竖堡等一翼堡j 霎j 鬻餮鬻譬誉塑 珥日蠢i 霈藿萄妻踅，猓斐馔攀羹颡囊雾蓉- ，- 鍪塞薯嚣美茁季荔一蔫蠢嘞 辱、钼篓髫謇菰继铺薹鎏薹。本= 舡羹綦美霪萋i 篓妻务誊鬻薹霍耋嚣愿碰融 季；羹黧蠢鬟匿，彰辇又莽霎 x 太原理i ：人学硕十研究生。学竹论文 构化信息就复杂些。 中文的文本表示通常选用字、词、短语、句予以及句群等更高层次的 单位。在实际应用中，到底选择哪种蕾位来表示文本必须由处理速度、精 度要求、存储空i 白j 等方面的具体要求来决定。选择的单位越具有代表性， 语言层次越高，它所包含的信息也就越丰富，但同时进行分析时所付出的 代价也就越火。 字特征 使用字为特征项是最简i 】1 的方法，将文本分解为字特征时非常容易实 现。按旦 ig b 2 3 1 2n 勺规定其有6 7 6 8 个汉字。这样特征集合就非常小，最火 不会超过6 7 6 8 。在这一点 ：与其它特征( 如词特征) 相比优点是非常明显的。 以字为特征项出有其明显的缺点，因为从理论上配，字不能完整地表示 个语义范畴，埘文档的表示能力应当是较差的，在实际应用中也确实发现 了这个问题。 词特征 现有的研究中大部分认为应以词为单位进行文本的表示。这是因为， 首先以词为单位比较符合自然思维习惯，便于系统利用语言学知识，其次， 以词为单位就可以借用英文全文检索系统中己有的理论及方法。与字特征 比较起来，词特征蕴合了更为丰富的语义信息，能够更为完整、准确地表 达文本信息。但是，山于使_ 蚪j 词特征首先要进行有效的分词和特征抽取， 因此运1 f j 词特征将增大信息处理的工作量和复杂度。 短语特征 在文本表示时高频词和低频词对不同类别文本的区分度都低于中频 词。因此在一些研究中使用短语来代替高频词，以降低其出现频率，以词 太原理工大学硕士研究生学位论文 汇类来代替低频词，以提高其出现频率。用短语代替词来表示文本同时还 提高了对文本的表达能力。目前，最准确的生成短语的方法是句法分析。 概念特征 通过概念标注的方法把有同义关系或近义关系的词台并为概念类，也 是文本表示的方法之一，这种描述文本的方法比单纯的词汇更能反映文本 内容。但处理起来要复杂得多。 确定了描述文本的基本单位，接下来就是如何用这些特征来描述文本 的问题了。“词频矩阵”是信息分类检索领域应用最多的描述方法，许多基 于统计方法的分类、检索模型都是建立在词频矩阵的基础上的。所谓的词 频矩阵就是用一个词频向量来表示一篇文本，再由这些向量组成矩阵。如 表2 1 所示。矩阵的每行对应一个文本，每一列对应一个特征项( 字、词、 短语等) 。每个元素是第，个文本中出现第i 个特征项的频率。 用词频矩阵描述文本可以反映出词在文本中的分布情况，使研究者可 以使用统计的方法进行分析。当然，除了词频还可以加入其他信息以更完 整地描述文本的内容，比如，可以加入特征项在文本中出现的顺序信息， 这样的表达更为清晰，但是这种顺序信息需要用一个有向图或网络图才能 得出，导致分析的复杂度和存储空间都大大的增加了。因此，在实际研究 与应用中使用最多的还是词频矩阵。 2 文本的预处理一分词技术 如果以词、短语、句子及更高层的语言单位为基础，对文档进行分类、 检索的第一步就是要分词。词是最小的、能独立活动的、有意义的语言成 分。计算机的所有语言知识都来自机器词典( 给出词的各项信息) 、句法 规则( 以词类的各种组合方式来描述词的聚合现象) 以及有关词和句子的 语义、语境、语用知识库。 太原理工大学硕士研究生学位论文 配长度不易确定，若太大则时间复杂度上升，太小则有些超过该长度的词 无法匹配，降低了分词的准确率。 逆向最大匹配法与最大匹配法的原理基本相同，只是二者的扫描方向 相反，一般来讲，最大匹配法从左向右扫描，而逆向最大匹配法从右向左 扫描。有文献指出，逆向最大匹配法的分词准确率要比最大匹配法高，但 是逆向最大匹配法需要配置逆序词典，该词典与人类的语言习惯不同，因 此修改和维护不方便。 逐词遍历匹配法将词典中的词按照由长到短的顺序逐个搜索、匹配整 个待处理的语料，直到所有的词都切分出来为止。 3 文本信息特征提取的基本方法 在自动文本分类问题中遇到的一个重要困难就是高维的特征空间。通 常，一份普通的文本经过分词后有几千甚至几万个词，既它的特征空间维 数达到几千甚至几力_ 维，大多数的学习算法无法处理这么大的维数。因此 特征抽取是文本分类中的关键问题，它具有降低向量空间维数、简化计算、 防止过分拟合等作用。由于特征子集的数量和特征数量之间是指数关系， 枚举几乎是不可能的，因此，可以假设特征之间是相互独立的，这样特征 子集的抽取就转化为特征项的抽取。 文本特征项抽取有许多方法，其中最简单的方法是通过词频( t e m l f r e q u e n c y ) 选择特征。词频就是一个词在所有文档中出现的次数。通过词 频进行特征选择就是将词频小于某一阈值的词删除，从而降低特征空间的 维数。这个方法是基于这样一个假设即出现频率小的词对分类的影响也 较小。但是在信息检索的研究中认为，有时频率小的词含有更多的信息。 因此，在特征抽取的过程中不宜用词频大幅度地删词。 文本的特征的抽取还可以通过特征评价函数来进行。即根据某个特征 评分函数计算各个特征的评分，然后按评分值排序，选取若干个评分最高 太原理1 ：大学硕十研究生学位论文 的特征。这种特征函数有信息增益( i n f o r m a t i o ng a i n ) 、交叉熵( c r o s s e n t r o p y ) 、互信宫, ( m u t u a li n f o r m a t i o n ) 等。 上述几种评价函数中都是试图通过概率找出词与类别之1 2 j 的联系，信 息增益的定义过于复杂，因此应用较多的是交叉熵和互信息。其中互信息 量的效果比交叉熵要好【9 ，这是因为互信息是对不同的类别分别抽取特征 词，而交叉熵与词汇在全部类别内的分布有关，是对全部类别来抽取特征 词。所以在这儿只介绍互信息函数，定义如下 g ( w ) - l 。g 等 ( 2 1 ) 其中p 俐是词w 出现的概率，对于每一类别柬讲，词w 的互信息越 大。说明该词与陔类的共现概率越大，因此，以互信息作为提取特征的评 价时应取互信息最大的若干个词为特征项。 222 词频空间特征提取方法 其基本思想是特征项对娄c ，的有效性与该特征项在c 。中所占的比 重成正比，与该特征项在所有类中所占的比重成反比。 1 特征提取算法 直观上看，特征项在某一类的训练样本中出现的次数越多，它就越能 代表该类，在分类过程中贡献就越大，同样，如果特征项在所有类的训练 样本中出现的次数越多，它就越不具有代表性，在类别区分上贡献就越小。 具体的特征抽取算法过程如下所列： s t e p1 ：初始情况下，该特征项集合包含所有原始特征项。 s t e p2 ：对于每个类别，计算所有特征项和该类别的互信息量 ，。e ( 等 槲川w l c 户煮登高，p 蚴为w 在c i 中出现的比重，d 为该类的训练文本数，a r m 甜为词w 在d i 中的 太原理上大学硕士研究生学位论文 k 个最相似的训练文本。这最相似的聊文本按其和待分类文本的相似度高 低对类另0 予以加权平均，从而预测待分类文本的类别。其中最重要的是参数 k 的选择，k 过小，不能充分体现待分类文本的特点；而世过大，会造成噪声增加 而导致分类效果降低。 文本向量属于类别c ，的权值暇c f d ) 由下式计算，权值越高，认为文 本向量d 属于类别c ，的概率越高： 矿( c ，d ) = ：；s ( d ，q ) p ( c ，d j ) ( 2 3 ) 其中，剐d ，d ，) 是向量之间的余弦相似度徊，仇是训练集中与d 余 弦相似度最大的髟个文本向量；而p ( g f 毋) ，当d j 属于类别c 。时为l ，否则为 o 。 通过上面的分析可知，k n n 的实质就是以特征属性权值作为特征空 间的坐标系测度，先计算测试集与训练集之间在该坐标系中的余弦距离，然 后根据测试集与训练集的距离远近来确定类别。显然，它没有考虑特征属性 关联及共现等因素对文本相似度的影响，如果加以恰当地考虑，k n n 的效 果会更好。 4 决策树( d e c i s i o n t r e e ) 分类 决策树是一种常用数据分类技术，同样适用于文本分类。决策树的建立 算法有多种，其中包括：基于信息增益的启发式算法i d 3 1 3 】；基于信息增益 率的解决连续属性分类的算法c 4 5 1 4 】；基于g i n i 系数的算法c a r t 【1 5 ； 针对大样本集的可伸缩算法s l i q 16 】；可并行化算法s p r j n t 17 】；将建树 和剪枝集成到一起的算法p b u l i c 18 。 5 支持向量机( s v m ) 方法 s v m 1 9 方法适合大样本集的分类，特别是文本分类，它将降维和分类 结台在一起。s v m 算法基于结构风险最小化原理，将原始数据集合压缩到 1 9 太原理一l _ = 火学硕士研究生学位论文 支持向量集合( 通常为前者的3 5 ) ，然后用子集学习得到新知识，同时 也给出由这些支持向量决定的规则。并且可得到学习错误的概率上界，即支 持向量的期望数目和训练集合大小的比值。 如果是线性可分样本，在给出线性分类面的时候，最好将分类面取在离 两类的样本点都较远的地方。假设线性分类面的形式为： 甙d ) = ( 0 - d 斗b = 0( 2 - 4 ) 其中( 1 ) 为分类面的权系数向量，b 为分类闽值，可用任一支持向量求得， 或者通过两类中任一对支持向量驳中值求得。将判别函数归一化，使得所有 样本都满足ig ( d ) i = 1 ，即 y l ( ( 1 ) d i ) + b - l 三o ，i = l ，2 ，以( 2 5 ) 其中，y i 是样本的类别标记，即当样本属于类c 时y i = 1 ，否则y i = - 1 ；d i 是相应的样本。满足上式切使l l 叫1 1 最小的分类面就是最优分类面。 过两类样本中离分类面最近的点且平行于最优分类面的超平面h 1 和 h 2 上的训练样本就是使上式等号成立的那些样本，它们叫做支持向量 ( s u p p o r tv e c t o r s ) 。 而支持向量机的基本思想为：首先通过非线形变换将输入空问变换到 个高维空间，然后在这个新空问中求取最优线形分类面，而这种非线形 变换是通过定义适当的内积函数实现的。 2 3 贝叶斯分类器的模型 朴素贝叶斯分类器( n b c - n a i v eb a y e sc l a s s i f i e r ) 是贝叶新分类中一 种最简单的、有效的而且在实际使用中很成功的分类器。 朴素贝叶斯分类模型采用最简单的贝叶斯网络结构。在该模型中，假 设所有的属性w = 1 ，2 ，”) 都条件独立于类变量c 即每一个属性变量都以 2 0 太原理工大学硕十研究生学位论文 类变量作为唯一的父节点。由于结构简单，有时将其与严格的贝叶斯网络 分类器相区别，仅称之为朴素贝叶斯分类器。图2 - 4 直观地描述了朴素贝叶 斯分类模型的结构特点： 图2 - 4朴素贝叶斯分类器结构示意图 f i g u r e2 - 4t h ef r a m e w o r kp e r f o r m a n c eo f n a i v eb a y e sc l a s s i f i e r 朴素贝叶斯分类模型优点是： ( 1 )算法逻辑简单，易于实现i ( 2 ) 分类过程中时阳j 空间开销小； ( 3 )算法稳定，对于不同的数据特点其分类性能差别不大，不会特 别偏好某种特定的数据集，也就是说健壮性比较好。 贝叶斯分类器的目的是对一个事件进行分类。判别它是否属于一个既 定的类别，其中的事件表示成若干特征项的组合。分别计算事件属于每个 类别的概率，最大概率所对应的类别即是事件所属的类别。 贝叶斯分类规则： p h e = p e h p 明伊旧 其中p 【切是先验概率，尸【删 是条件概率，p h e 是后验概率。对每 一个类别七计算p h e e = p e h d p 日女 俨 司。 其中的假设如下： 凰表示事件属于类n a ， 表示事件属于类n b ， 2 l 太原理i ：大学硕士研究生学位论文 以此类推。 事件e 表示成胛个特征项e ，e ：，e 。的组合，其中： e 可：表示特征项e 的值为z ， e ：7 ：表示特征项e ：的值为y ， 依此类推。 在这儿，假设各个特征项是相互独立的。根据上面的假设，估计事件 e ( e ，而，e ) 在假设凰下的概率计算可写成： 尸【e 。】= p i e l = x h 。 p e 2 = y h 女】p 【e = z h 1 1( 2 - 6 ) 最终目的是比较在哪种假设h k ( 事件e 属于类别七) 下p f h g e 的取值 最大。p 司对于每个假设均为常数，可以忽略，所以p 【嗍的取值只取决 于p e j 凰 | d 【风 。 特征项目是离散的还是连续的，p e , = x h k 会有不同的计算方式。 当特征项是离散的，用如下公式： 郴，刊川= 壁燮袢鬻器黧糕笋燮 ( 2 7 ) 对于连续的特征项，采用高斯正态分布来计算条件概率 2 0 】。其中， 表示期望，盯表示标准差： 一x g t k 喁= 舢小丽1 e 2 4 ； 2 - 8 ) 理论上讲，与其它所有分类算法相比，贝叶斯分类具有最小的出错率。 然而，实践中并非如此。这是由于对其应用的假设( 如类条件独立) 的不 切实际性，以及缺乏可用的概率数据造成的。然而，种种实验研究表明， 与判定树和神经网络分类算法相比，在某些领域。该分类算法可以与之媲 美。 太原理工大学硕士研究生学位论文 设门为训练数据库的维数，尼为类标号个数，为训练样本个数。朴素 贝叶斯所花训练时间仅为编辑一张类概率估计表一张条件属性值概率估 计表。前者是一维的，后者是二维的，空间复杂度为0 ( n 女) 。为了计算估 计值，需要对数据进行一次简单的扫描，操作的时间复杂度为d ( 胛r ) 。分 类时间中，使用在训练时形成的具有空间复杂度p ( 阿的来分类一个简单样 本的时间复杂度为d ( 订约。 2 4 贝叶斯文本分类器的模型 文本分类的任务是将待分类的文本归属到一个既定的类中。其中的文 本采用向量空间模型( v s m ) 表示，每个文本有特定的特征项组成，分别 计算每个文本属于每个类的概率，最大概率所对应的类别即是这个文本所 属的类别。 2 4 1 贝叶斯分类器的表示 朴素贝叶斯分类器( n a - f v eb a y e s ) 假设特征对于给定类的影响独立于 其它特征，即特征独立性假设。对文本分类来说，它假设各个特征w 和之间 两两独立。文本壤示成向量： c - ( dh d 2 d h d 加 一= 矿( w ，d )( 2 9 ) 其中吹w 。回表示特征词w 。在文本d 中出现的次数，洲表示特征词的个 数。 设训练样本集分为七类，记为c 叠 c c i q ) ，则每个类c j 的先验概率 为尸( c ，) ，f - l ，2 ，k ，其值为g 类的样本数除以训i 练集总样本数门。对于新 样本d ，其属于c 类的条件概率是p ( 船，) 。根据贝叶斯定理，g 类的后验概 率为j p ( o 铆： 太原理 ：火学硕士研究生学位论文 粥d)=p(d矿c,)p(c)( 2 1 。) p(对于所有类均为常数，可以忽略，则式子简化为：p(c，d)oc p(dic,)p(c，)( 2 - 1 1 ) 在特殊情况下，训练样本集中各类样本数相等此时类的先验概率相等，可以简化： p(c，d)ocp ( d c ，)( 2 - 1 2 ) 朴素贝叶斯分类器将未知样本归于类的依据，如下： p(c，d)=argmaxp(dc，)jp(c)，i，=1,2，k( 2 - 1 3 ) 文档d 由其包含的特征词表示，即d 表示成( w l ，w 。) ，m 是d 的 特征词个数俐，1忖是迥i蠹蕊型奏i霎壕薹置鍪墼弦籀；答鼍 p ( d c i i 一萎l l 鼗。w 婪：；- 一。) c j ! r 赣p ( w ：c 冀：i i i ； 螫奔r t i f 釜j i 笺塞囊蒸篓羹喜筮毖s 篓转换为： 尸( c d ) 。cp ( g ) 兀尸( w c ，) ( 2 1 5 ) 为避免式中p (1 1 c ，) 等于0 ，可以采用l a p l a c e 概率估计 2 0 。 2 4 2 贝叶斯文本分类器的模型 文本的类条件概率尸( 西仁) 可以由文本中出现的特征的类条件概率求 得。 在贝叶斯假设的基础上，文本可以看作是若干词汇的集合，我们可以 认为文本是这些词汇按照一定的方式“产生”的。根据产生方式，简单贝 叶斯分类算法有两种模型：多变量贝努里事件模型( m b m ，m u l t i v a r i a t e b e r n ou l l ie v e n tm o d e l ) 和多项式事件模型( m m ，m u l t j n o m i a le v e n t m o d e lmm，multjnomiale v e n t 太原理上人学硕士研究生学位论文 出现一次的概率为尸( w 蚴，文档中出现x 欣特征词w 的概率为p ( w e r 。，出 现依这种次序排列的词的集合的概率为兀p ( w c ，) 。 按照上面的估计，很多不同序列的特征词都会对应着同一篇文档，为 了解决这个问题，在这儿采用多项式排列： m ”孙 ! ! x ! ! 二! ! ! ! 。 一一 ”11 ( ”一 1 ) ! 21 ( h 一，z i n 2 ) ! 门! = 丽( 2 - 1 7 ) 假定共有门个词，则心= ，x ，有式子： l 兀p ( c ，) 1 ( 2 1 8 ) 为了提高分类的准确率，文章的长度也应该考虑： 肌一) _ p c 抄! 兀半( 2 1 9 ) 这在实际中很难做到，所以我们在后面构造贝n t + 斯文本分类器时用的 是式子( 2 - 1 8 ) 。 多项式模型的参数是特征词出现的概率e ( w q ) ，其中： p ( w ，c ) = 1 p ( w q - ) 的值可以从训练中估计： 吃 r ， = 、j cx ，l p 太原理工大学硕士研究生学位论文 n ，c d “n r ( w ，c ，) h 7 q 卜夏韵 ( 2 - 2 0 ) 厶r 、”，。j7 其中，c d 姗f ( w “q ) 表示特征词w 。出现在q 类文档中的次数， ，“以，( w ，q ) 表示q 类文档中出现的所有特征词的总次数。为了避免 p ( w 弓) 等于零，对其的估计采用1 印i a c e 平滑技术： n ，c d “竹f ( w ，c ，) + 占 以峨化p 2 再赢赢荔丽 之1 ) 其中，例表示特征词表中的总单词数，万可以是任意的一个非零数， 常取j = 1 。 1 9 8 8 年，m c c a l l u m 和n i g 锄对两种模型作过比较，多项式模型要优于 贝努旱模型2 5 。本文采用多项式模型。 2 4 3 贝叶斯文本分类器的缺陷 多项式模型考虑到了词频和文档的长度，但是它忽略了词的相关而认 为他们是独立的。这种情况在现实中是不可能的，但是贝叶斯的分类效果 相当不错。特征项的冗余是贝叶斯的一个重大缺陷。贝叶斯的数据稀疏( 如 果一些特征项没有在数据集中出现，不管别的特征项的条件概率有多高， 都会导致条件概率的零概率) 是一个不容忽视的问题【2 1 。 现在解决数据稀疏问题采用的是l a p l a c e 平滑技术，在一定程度上避免 了零概率状况。但是由于1 a p l a c e 的平滑技术相当简单，所以分类的准确性 受到了影响，为了提高分类的准确性，我们采用统计语言模型的平滑技术