（计算机应用技术专业论文）基于类别均衡的文本分类算法研究.pdf

摘要 文本自动分类是在给定的分类体系下，让计算机根据文本的内容确定与它相关 联的类别。向量空间模型( v s m ) 是进行大规模文本处理的最通用模型。 为了提高分类性能，本文研究和改进了基于向量空问模型的特征词权重计算方 法，同时提出了一种基于类别均衡的k 近邻( 心) 分类算法。词语权重计算方法 的改进是在t f i d f 算法的基础上，综合考虑了特征词在分类中的重要程度和文本 中不同位置的特征词反映文本内容的能力，并引入了特征词的信息量和位置信息概 念。弥补了以前的算法虽然考虑了特征词在文本集合中的词频和分布情况但是并 没有考虑分布的比例情况，以及忽略了特征词的不同位置对文本的重要性不同的缺 陷。 基于类别均衡的k n n 分类算法是对原始训l 练集以类为单位进行重新组合，使得 小于特定闽值的相似的小类别合并为大类别，并作为大类别的子类：同时将大于特 定阈值的大类别通过聚类算法划分为若干小类别，使这些小类别成为该大类别的子 类。以每个子类的中心作为类别的代表点，并根据文本到不同类别代表点的余弦距 离之和进行分类决策。重组后的训练集类别分布更加均衡。在分布均衡的类别上进 行训练和分类，进一步解决了文本集的多峰分布、边界重叠以及忽视小类别的问题。 关键字：文本分类，向量空间模型，特征选取，特征词权重，类别均衡 a b s t r a c t a u t o m a t i ct e x tc l a s s i f i c a t i o ni sd e f i n e da st h et a s kt oa s s i g np r e - d e f i n e dc a t e g o r y l a b e l st od o c u m e n t s v e c t o rs p a c em o d e l ( v s m ) i s t h em o d e l t h a ti su s e dw i d e l yi nt h e 1 a 唱e - s c a l et e x td i s p o s a l t oi m p r o v em ec l a s s 湎c a t i o np e r f o m l a n c e ，t j l i sp a p e rd o e sr e s e a r c ha n dm l p m v e s o nt h ec l a s s i c a la l g o r i t h mo fc a l c u l a t i n gt h et e 响w e i g h ti nv s m f u n h e r m o r e ，a c a t e g o r yh o m o g e n i z i n g - b a s e d k - n e a r e s t n e i g h b o r s( k n n )a l g o r i t h m f o rt e x t c a t e g o r i z a t i o ni sp r o p o s e d t h ei m p o r t a n c eo ft e r l n s i nt e x tc a t e g o r i z a t i o na n dt h e c a p a b i l i t y o fr e n e c t i n gt e x tc o n t e mo ft e r m sl i ei nd i f f b r e n t p o s i t i o ni n t e x ta r e c o n s i d e r e di nt h ei m p r o v e m e n to na l g o r i t h mo f c a i c u i a t i n gt h et e 咖w e i 曲t i n f o r m a t i o n e n t r o p ya n dp o s i t i o no f t e r m sa r ei n t r o d u c e di nt h i sa p p r o a c hb a s e do nt f i d ft h i s a l g o r i t h mr e m e d yt f i d f sd e f 毫c t st h a td i s t r i b u t i o np r o p o n i o na n di n f o r m a t i o no f p o s i t i o no ft e r mi sn e g l e c t e d t h et m i n i n gs e ti so r g a n i z e dn e w l yw i t hc a t e g o r ya su n i ti nt h ek n na l g o r i t l l m b a s e do nc a t e g o r yh o m o g e n i z a t i o n m e a n w h i l e ，s i m i l a rs m a l lc a t e g o r i e sl e s st h a nt h e t 1 1 r e s h o l da r ec o m b i n e di n t 0n e wb i gc a t e g o r i e sa 1 1 da s s u b c a t e g o r i e so fn e wb i g c a t e g or i e s ，b i gc a t e g o r i e sm o r et h a nt h et h r e s h o l da r es e p a r a t e di n t os o m e s m a h c a t e g o r i e sa n dt h e ma ss u b c a t e g o r i e s0 fb i gc a t e g o r i e s t h e c e n t e ro fs u b c a t e g o r i e s i sc o n s j d e r e da sd o to fc a t e g o “e s t h ed o c u m e n tj sc a t e g o r i z e db a s e do ns u mo f c o s i n ed i s t a l l c eb e t w e e ni ta n dd o to fc a t e g o r i e s d i s t r i b u t i o no fc a t e g o r i e s i s h o m o g e n i z e d i nt h e o r g a n i z e dt r a i n i n g s e t t h e p r o b l e m s o f m u l t i p e a k d i s t r i b u t i o n ，o v e r l a pb o u n d a r y a n ds m a l lc a t e g o “e sa r e n e g l e c t e d a r er e s o l v e db y c a t e g o r i z i n gi nc a t e g o r yh o m o g e n i z i n g _ b a s e dt 豫i n i n gs e t k e y w o r d s ： t e x t c a t e g o r i z a t i o n v s i f e a t u r es e l e c t i o nt e r mw e i g h t c a t e g o i 了h o m o g e n i z a t i o n 创新性声明 y 8 5 8 9 2 9 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容外，论文中不 包含他人已经发表或撰写的研究成果；也不包含为获得西安电子科技大学或其它 教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所作过的 任何贡献均已在论文中作了明确的、蜕明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 垫垒 r 朔：伊6 | j fi 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为鹾安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可咀允许采用复印、影印、缩印或其它手段保存论文。( 保密的 论文在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名： 垫 ! 垂， 导师签名： 日期：删 同期 迦g ：盆! q 一 第一章绪论 第一章绪论 1 1 研究背景和意义 随着信息存储技术和通信技术的飞速发展，大量的文字信息开始以计算机可读 形式存在。尤其是近年来随着国际互联网技术的发展，网络上的信息资源呈指数级 增长，w e b 己经成为拥有几十亿个页面的分布式信息空阳j ，而这个数字仍以每4 至6 个月翻一番的速度增加。在这样一个信息化的时代，人们的同常活动当中无时无刻 不在获取信息、分析信息，并以此来决策自我的行为。从某种程度上来浇，信息的 拥有量已经成为决定和制约人类社会发展的重要因素。如何在这些人量、异质的海 量信息资源中、快速有效地发掘蕴含具有巨大潜在价值的有用知识和信息，合理分 类及准确地定位所需信息，同时过滤大量无用的或不相关的内容，己成为知识获耿 和信息过滤的瓶颈，也是当今信息发展和信息处理领域的主流技术。 文本分类技术有助于人们完成这个目标，为信息提取与信息处理打下良好的基 础，它在文本挖掘乃至网络挖掘中均占有重要的地位。文本自动分类是指根据预先 定义的主题类别，根据一定的规则将文本集合中未知类别的文本自动确定一个类 别。涉及数据挖掘、计算语义学、信息学、人工智能等多个学科，是自然语言处理 的个重要应用领域。文本自动分类的目的是通过将大量文本进行快速、有效的自 动归类，达到信息定位和信息过滤的目标。基于人工智能技术的文本分类系统能依 据文本的语义将大量的文本自动分动分门别类，从而更好地帮助人们把握文本信 息。近年来，文本分类技术己经逐渐与搜索引擎、信息推送、信息过滤等信息处理 技术相结合，有效地提高了信息服务的质量。 1 2 研究现状 文本自动分类的研究始于2 0 世纪5 0 年代末，h p l u h n 首先将词频统计思想用于 自动分类，在该领域进行了开创性的研究。1 9 6 0 年，m a r o n 在j o u m a lo f a s m 上发表 了有关自动分类的第一篇论文o nr e l e v a n c ep r o b a b i l i s t i ci n d e x i n ga n di n f o r m a t i o n r e t r i e v a l ，其后许多学者在这一领域进行了卓有成效的研究工作。从2 0 世纪6 0 年 代到2 0 世纪8 0 年代术，这期间最有效的文本分类系统一直是由专家人工构建的基于 知识工程技术的分类系统。其典型应用就是卡内基集团为路透社丌发的 c o n s t r u e 系统，它主要是由专业人员编写了一些分类规则来指导分类，在r e u t e r s 的部分语料库上它的效果非常好，平均精确率和召回率大约都可达到9 0 ，但是在 其他的应用领域采用c 0 n s t r u e 系统将会消耗大量的人力和物力。这种自动分类 器构造方法的缺点是知识获取瓶颈的存在。它必须要为领域专家获取的知识和知识 基于类别均衡的文本分类算法研究 工程师的知识表示之间架起桥梁，二者缺一不可，如果这种分类器被转到完全不同 的领域，工作必须得重新丌始。9 0 年代初期，基于机器学习( m a c h i n e l e a m i n g ) 的分 类技术丌始取代基于知识工程的方法成为文本分类的主流技术。这种方法通过归纳 文本集的特征自动创建一个分类器，这些文本集事先被领域专家人工地分类到类集 c = c 。，c ，c 。，) 的各个类c ，中，分类器可作为个规则决定文本d ，是否属于类c ，。 如果类集c 被更新，或者系统要应用于其他不同的领域，只需要重新构造一个人工 分类文本集合，通过机器学习，自动地构造一个分类器。显然由于这种分类方法不 再需要知识工程师和领域专家的介入，节约了大量的专家人力资源，同时加快了分 类系统的建立速度。 近年来，研究者们结合机器学习方法和人工智能的技术进行了大胆的探讨提 出了多种分类模型和分类算法，如基于向量空间模型的r o c c h i o s 算法及其一系列的 改进算法旧j 、k n n ( k n e a r e s tn e i g h b o r s ) 算法【3 】、决策树( d e c i s i o nt l e e ) 算法【、 朴素9 叶斯( n “v eb a y e s ) 算法j 、神经网络( n e u r a ln e t w o r k ) 算法、支持向量 机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 算法o j 等等，这些算法在英文以及欧洲语种 文本自动分类上有广泛的研究，均取得了不错的效果。国外很多研究人员对英文文 本分类领域的各个问题都有相当深入的研究，对几种流行的算法进行了大量的对比 研究1 2 j 。很多研究表明，k 卜n 和s v m 是英文文本分类中最好的算法。还有一些研 究人员研究表明结合不同的分类器能够提高分类的精度。【1 “j 1 9 9 4 年，a t & t 实验室的d a v i dd l e 谢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 等研究了基于向量空间模型的自动分类 系统。同年，美国s t a n f j r d 大学计算机系的d a p h n ek o l e r 等提出了基于很少语料词汇 的层次自动分类算法。1 9 9 8 年，美国c a r n e g i e me l l o n 大学计算机系的y i m i n gy a l l g 等将决策树等聚类算法应用于在线自动分类。1 9 9 9 年，美国j u s tr e s e a r c h 公司的 a n d r e wm c c a i 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 r 公司也为其浏览器丌发了基于内容属性分类的插件。 1 3 问题提出 1 3 j 特征词权重计算方法 文本可以表示为一个特征词集，也称为特征项集或属性集。但作为一个有效的 文本内容的特征表示词集，必须具备以下2 个特征： 1 ) 完全性：特征词能够确实标识文本内容； 第一章绪论 2 ) 区分性：特征词将目标文本与其他文本相区分的能力。 特征词是组成文本的基本元素。在特征词确定的情况下，特征词的权重计算是 文本分类的关键。通常根据特征词在文件中是否出现、出现频率或者其他重要性度 量等综合因素，给其赋予一定的权重，可以提取一定数目的权重较大的特征词作为 文本的特征表示。特征词权重综合反映了该特征词对标识文本内容的贡献度和文本 之间的区分能力。现有的t f i d f 算法，虽然同时考虑到了词频和文本频率两个因 素，但是公式本身显得有些过于简单，缺少较好的区分度，忽略了特征词的信息量 和位置信息。因此，提高特征词权重计算方法的准确性，是文本自动分类研究中的 一个重要课题。 1 3 2 文本分类算法 文本自动分类是把未知类别的文本自动分配到已知类别中的过程。文本分类的 实现需要建立在个已经人工分好类的训练集的基础上，训练集的质量好坏对文本 分类的性能有着决定性的意义，训练集对分类器的性能有着决定性的作用。设计一 个分类系统必须首先考虑训练集的问题，如果训练集质量不高，那么无论分类算法 如何精确， 都很难达到好的分类效果。一个照好的训练集，需要具备以下几个特 征： 1 ) 类别分布均衡； 2 ) 每个类别中的文本都能够很好地代表该类别； 3 ) 类别中各文本在特征空间中的排列比较集中。 但是，由于信息资源分布的特点，有些类别的信息明显匮乏，即稀有类别，这 些类别的信息资源有限，导致训练集中稀有类别的文本数量无法和普通类别相比。 在现有的文本自动分类算法中，参与分类的各个类别在分类过程中都是平等的，并 不会因为某个类别是稀有类别就在分类时区别对待。这样，分类时貌似公平的处理 在实际应用中其实有着一定程度的不公平。如何相对公平地对待稀有类别，提高稀 有类别的分类精度成为分类过程中需要迫切解决的一个问题。 1 4 本文的工作和论文的组织 本文以向量空间模型为基础系统研究了文本分类。对于文本分类流程，本文_ t 要从理论和算法两个层次进行了比较深入的研究，主要工作如下： 1 ) 对t f i d f 算法进行了深入研究，该算法虽然考虑了词在文本集合中的词 频和分布情况，但是并没有考虑分布的比例情况，同时忽略了词的不同位置对文本 的重要性不同的情况。针对这些缺陷，本文提出了t f i d f 的改进算法，引入了词 的信息量和位置信息等概念，加强了特征词权重计算的精确性。 4基于类别均衡的文本分类算法研究 2 ) 对文本分类的常用算法做了比较系统的分析，比较深入地研究分析了k n n 分类算法、朴素贝叶斯分类算法、r e c c i o s 分类算法和s v m 分类算法，并且在此基 础上提出了一种基于类别均衡的k n n 算法。该算法解决了文本集的多峰分布、边界 重叠以及忽视小类别的问题，提高了分类的精确性和召回率。 3 ) 本文使用了来自于网络上用于文本分类常用的语料库2 0n e w s g r o u p s 数据 集和r e u t e r s 2 1 5 7 8 语料库，将其组成不同的训练集，并在此基础上对本文提出的 t f i d f 的改进算法和基于类别均衡的k n n 算法做了大量的实验对实验结果进行 了分析总结。 全文分为五个章节内容如下： 第一章是绪论，首先对本课题的背景和意义做了介绍，然后讨论了文本分类的 研究现状，提出了本课题需要研究的一些问题，最后，对本课题主要的研究内容和 论文的组织做了简要的介绍。第二章主要围绕文本分类流程，系统地分析了文本分 类的整个步骤。第三章首先介绍了向量空间模型的相关概念其次分析了特征词选 择的几种算法，最后详细分析了改进的特征词权重计算方法。第四章首先介绍了训i 练集平测试集的相关概念以及常见的文本分类算法，其次详细分析了基于类别均衡 的k n n 分类算法。第五章将列出各种实验结果和分析。 第二章文本分类相关技术 第二章文本分类相关技术 本章将主要围绕文本自动分类流程图展开介绍。自动分类的基本流程包括：文 本预处理、文本特征选取、文本表示、文本分类以及分类评测。其中，两个核心步 骤是文本特征选取和文本分类。 2 1 文本分类流程 图2 1 给出了文本自动分类的流程图： 图2 1 文本自动分类流程幽 2 2 文本预处理 文本自动分类首先要做的工作就是将通常以字符串表示的文本转换为适合于 学习算法以及分类任务的表示形式。大量分析表明，一篇文本的内容主要是通过名 6基于类别均衡的文本分类算法研究 词、动词、形容词等实词来体现的，虚词以及在各种文本里经常出现的高频词对于 分类并无意义。因此，要从文本词汇列表中过滤掉虚词及统计得出的高频禁用词， 从而获得文章的内容词表。预处理通常包括下列几种类型：【2 4 】 1 ) 去除标记。 2 ) 去除停用词( s t o p w o r d ) 。停用词是指包括介词或冠词等语义内容很少的 词，也指在文本集的每个文本中都可能出现的高频词。停用词有可能出现在很多文 本中，所以对区分文本的内容价值不大，通常在预处理阶段去处掉。分类系统的停 用词是语境依赖的，例如在计算机科学的文本集中，“c o m p u t e r ”会出现在停用词 表中，但在其他领域的文本集中，它就不是停用词。 3 ) 词性标注。词性标注是给文本中的每个词选择个最有可能的词类。自然 语言中的词存在着大量的兼类现象，举例来说，单词“c o o k ”有两个意思，一个指 某种人( 厨师，如a c o o k i s i n t h ek i t c h e n ) ，另一个指的是动作( 烹调，如h ec a n c o o k d e l i c i o u s f o o d ) 。当“c o o k ”作第一种意思时，它是一个名词，而作为第二种 意思时，它是个动词。词性标注可以排除由于词的兼类而形成的歧义。 4 ) 词还原。词还原的主要目的是把一些变形词复原为浚词原来的表示形式。 主要包括以下内容：名词复数去除。把名词的复数形式恢复为原来的形式。在。 个文本中，名词的重要性是不占而喻的，文本分类的过程中名词尤其有举足轻重的 意义。动词时态转换。把动词在各种时态的形式恢复至其原来的形式。动词第 三人称转换。把动词在第三人称下的形式恢复至其原来的形式。词根还原。词根 还原是指从文本中去掉词的前后缀，用以形成和系统内部模型里一致的特征词，这 样做的目的是将具有同样概念的词( 如、v a l k ，w a l k e d ，w a l k i n g ) 统一处理。简写 词复原。文本中存在大量简写词( 如d l r ，原为d 0 1 l a r ) ，在预处理中，必须把这些 简写词复原为该词的完整形式。简写词复原可以通过分析测试集，获得所能见到的 简写词，将其汇编成简写词表。 5 ) 词根辨认。自然语言文本中存在大量的词组，如j n f e r e s tr a t e ，g r o s sn a t j o n a l p r o d u c t ，根据词对短语的依赖性，若把一个词组中的词分丌分析则会损坏这个刊组 的意义，得不到词组原来所要表达的意思，而且，一般而言，词组的歧义比次单独 的词要大。 2 3 特征选取 2 3 1 特征提取( 降维) 文本分类的一个核心难题就是特征空间的高维性( h i 曲d i m e n s i o n a l i t y ) 。特征 空间包含两维，其中的一维是由文本集中的每个特征词构成的，通常这些特征词的 数量数以万计。由于计算量太大以及缺少足够的训练数据，标准的分类技术无法处 第二章文本分娄相关技术 理如此庞大的特征词集，因此有必要简化原始的特征词集，即降维技术。 根据降维技术在实现过程中是分别在单独类别上还是在所有类别上完成，可以 分为局部降维技术与全局降维技术。局部降维中特征词集合r 用于每一个类别的 分类，其中r 7 ；在全局降维中，特征词集合r 。用于所有类别的分类，其中 r 。 7 1 ，目前全局降维技术应用得更为普遍。 上述两种降维技术的区分中所采用的具体降维技术又可以分为两类：特征选择 和特征重构。特征选择算法主要包括文本频率( d o c u m e n tf r e q u e n c y ，d f ) 、信息 增益( i n f o 锄a t i o ng a i n ，i g ) 、互信息( m u t u a li n f o m l a t i o n ，m i ) 、丌方校验( z 2 t e s t ， c h i ) 、主分量分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ，p c a ) 和类别文本频率( c a t e g o r y f r e q u e n c y d o c u m e n tf r e q u e n c y ，c f d f ) 。特征重构主要包括特征组合和潜在语义 标引( 1 a t e n ts e m a n t i ci n d e x i n g ，l s i ) 。本文将在第三章中详细介绍这些算法。 2 t 3 2 特征权重的计算 目前最常见的权重赋值方法是运用统计的方法，即用文本主要的统计信息一词 频来计算特征权重。最初的特征词权重计算方法是o 、l 赋值法，即如果文本t 寸出现 该特征词，那么文本向量的浚维为l ，否则为0 。这种方法无法体现特征词在文本中 的作用程度，所以逐渐被更精确的词频统计所代替。词频分为绝对词频和相埘词频， 绝对词频是指使用特征词在文本中出现的频率表示文本，相对词频是指归一化的词 频，其计算方法主要运用t f i d f 算法，其中t f 是特征词在文本中的绝对频率，而 i d f 表示特征词在文本中的文本内频数，目前存在多种t f i d f 算法，例如，目日“ 使用的一种比较普遍的t f x i d f 算法： = 缈t 。文。+ o o ) 厮忑万研 其中，其中彬。为词语瓦在文本口中的权值，以为词语瓦在文本d ，中出现的 频率，v 为训练文本的总数，为训练文本集中出现瓦的文本数，k = l ，2 ，。( m 为词的个数1 ，分母为归一化因子。 另外还存在其它一些t f i d f 算法，例如： ( 1 扎g 以) x l o s ( 琢忑丽 该公式中参数的含义与上式相同。 以上公式的提出是基于这样一个考虑：对区别文本最有意义的特征词应该是那 基于类别均锸的文本分类算法研究 些在文本中出现频率足够高而在文本集合中的其它文本中出现频率足够少的词。 由于对特征词的选择起决定性的作用，有很多学者对此做了深入研究。j r o c c h i o 提出了基于正例反例的批处理计算方法1 1 1 ；b w i d r o w 提出了即时的线性计 算方法【7 】：李国臣等提出了基于对数似然比测试的词权重计算方法【3 ；张月杰等提 出了结合了词在文本中的位置的词权重计算方法，如标题、正文【1 ”。 本文提出了t f i d f 的改进算法，不仅引入了词频位置权值，而且结合了词的 信息量。本文将在第三章中对该改进算法作详细阐述。 2 4 文本的表示 计算机并不具有人类的智能，人在阅读文章后，根据自身的理解能力可以产生 对文章内容的模糊认识，而计算机并不能轻易地“读懂”文章，从根本上说，它只 认识o 和1 ，所以必须将文本转换为计算机可以识别的格式。根据“贝叶斯假设”， 假定组成文本的字或词在确定文本类别的作用上相互独立，这样，可以使用文本中 出现的字或词的集合来代替文本。不言而喻，这将丢失大量关于文章内容的信息， 但是这种假设可以使文本的表示和处理形式化，并且可以在文本分类中取得较好的 效果。文本表示模型有多种，常用的有布尔逻辑模型、概率型、向量空间模型等。 布尔逻辑模型是一种传统的、简单而普遍使用的严格匹配模型。 1 御尔逻辑模型( b 0 0 1m o d e l ) 在布尔逻辑模型中，它以文本中是否包含关键词做为判断依据，基于检验关系 运算符的逻辑表达式和关键词是否匹配。靠尔逻辑模型根据用户提交的检索条件是 否满足文本表示中的逻辑关系，将检索文本分为两个集合：匹配集与非匹配集，即 只判断检索出的文本是否与查询有关。常用的是b o o lm o d e l 的扩展p 范数模型。【4 4 l 2 向量空间模型 向量空间模型将文本表示的基本单位定义为由字、词或短语构成的特征词，所 有特征词构成特征词全集。每个文本由一个维数等于特征词集个数的向量构成，该 向量的每个分量是特征词在文本中的权重。v s m 的最大优点在于它在知识表示方 面的臣大优势。在该模型中，文本内容被形式化为多维空间中的一个点，通过向量 的形式给出。从而把对文本内容的处理简化为向量空间中的向量计算，使问题的复 杂性大为降低。 本文将在第三章中详细阐述向量空间的相关概念。 3 概率模型 概率模型可克服布尔逻辑模型和向量空间模型忽略词条关联性、视文本中词条 互为独立的缺点。概率模型是利用词条间及词条与文本间的概率相依性进行信息检 索。 第二章文本分类相关技术 设文本d 与用户查询c 都可用二值词条向量组( a ，口：，) 表示 有口= l ，否则为o 。其相关公式为： 坤力= 扣删 当词条，d 时 其中只= l ，g = 一) u r ) 。，表示训练文本集中文本总数，r 为文本 集中与用户查询有关的文本数，z 表示训练文本集中包含词条，的文本数，表示r 个相关文本中包含词条f 的文本数。 目前，文本的表示主要采用的是向量空间模型。本文将在第三章中介绍向量空 间模型的基本概念。 2 5 文本分类 分类模型是文本分类的核心。根掘采用分类算法的不同，分类模型的训练和测 试的细节也有所不同。训练是分类器根掘训练样例完成的一组学习过程，负责完成 分类模型的建立和调整。在全特征集建立起来并完成特征选取工作之后，训练文本 就可用特征词表示为文本向量，然后送往分类器完成训练。训练后的分类器方可用 于分类。未知文本在被分类之前，同样需要根据特征词集转化为“文本特征向量” 表示，然后再送往分类器进行分类，以得到分类结果。 目6 # 存在多种分类算法，例如，k n n 分类算法、r o c c h i o s 分类算法、朴素贝叶 斯分类算法、支持向量机分类算法、决策树分类算法和神经网络分类算法。本文将 在第四章中具体介绍这些分类算法。 2 6 分类的评测 分类的评测在文本自动分类中具有非常重要的作用，特征抽取和分类器训练都 需要调用评测方法。分类系统的训练过程是以评价方法作为依据进行的。 2 6 1 多重二元分类任务 多重分类普遍使用的方法是把任务分为独立的二元分类问题。对于某个类和某 个文本而言，用户决定这个文本是否属于该类。当评价分类的结果时，每一个类中 的下面4 个量是非常重要的： a ： 被正确地分入该类的文本数量。 b ： 被错误地分入该类的文本数量。 c ： 被错误地划出该类的文本数量。 d ： 被j 下确地划出该类的文本数量。 因为文本分类从根本上说是一个反映过程，所以评估文本分类系统的标志是映 0 基于类别均衡的文本分类算法研究 射的准确程度和映射的速度。映射的速度取决于映射规则的复杂程度，而评估映射 准确程度的参照物是通过专家思考后对文本的分类结果的评估，与人工分类结果越 相近，分类的准确程度就越高，这里隐含了评估文本分类系统的两个指标：精确率 ( p r e c i s i o n ) 和召回率( r e c a l l ) 。 精确率是所有判断的文本中与人工分类结果吻合的文本所占的比例。其数学公 式为：精确率( p r e c i s i o n ) =分类正确的文档数 冤莉再丽孤 a p r e c l s l o n = _ a+b 即 召回率是人工分类结果应有的文本与分类系统吻合的文本所占的比例，其数学 公式表示为：召回率( r e c a l l ) = 鱼蔷茎篙，即 r e c a l l ：! 一 可以定义下列衡量标准： f a l l o u t ：j ) _ b + d a 十b 。 a + b + c + d b + c a + b + c + d 式( 2 9 ) 除了上述的指标外，实践中广泛使用的指标还包括： 1 宏平均和微平均 有两种常规方法可以用于评价各个类的平均分类情况：宏平均和微平均。宏平 均的结果是先对每个类求值，然后平均。微平均则先将所有文本a 、b 、c 、d 一块计 算，然后求值。这两种平均方法的不同在于微平均中每个文本的权重相同，而宏平 均中每个类的权重相同。 2 损益平衡点 如果独立地看上面的评估尺度可能会引起误导，通常的分类体系表现出召回率 和精确率的此消彼长。高的召回率往往意味着低的精确率：反之，高的精确率也往 往意味着低的召回率。如果调整召回率和精确率相等，这个点被称为系统的损益平 衡点。该点在文本分类评价中被广泛使用。 3 f - 评估 另一个把召回率和精确率结合的评价标准是，评估 第二章文本分类相关技术 b ：笙掣竺娑掣 式( 2 一l o ) 。6 酽d r e c i s i o n r e c d n 1 其中，口是允许召回率和精确率取不同值的参数。 4 插值法 对某些方法而言，分类任务是通过闽值实现的。例如b a y e r s 分类算法计算一个 文本在目前类中出现的概率，必须通过设定闽值来决定到底概率多大才能分入这个 类中。通过调整闽值，可以使用不同的召回率和精确度值。不同阈值的结果通过捅 值法被结合起来。 2 6 2 多重分类和多重表示分类 分类器将每个测试文本的类列表，为了用一个置信值来衡量分类器的好坏，可 以使用一种叫插值11 点平均精确率( i n t e r p o l a t e d1 1 - p o i n t e da v e r a g ep r e c i s i o n ) 的方 法。在这个方法中，一个文本的召回率定义如下： 召回轧e c = 篙鬻篆文档应有的正确类别数 刘这个分数的1 1 个值o o ，0 1 ，1 0 中的每一个，系统决定要沿着列表向下走多 远( 也就是分子的大小) 爿能得到指定的r e c a i l 。类的数量的精度可以计算如卜： 精确轴删砌= 骂裟筹 最终得到11 个精度值，求它们的平均值就可以得到衡量恢文本的表现的一个定 量标准。对一个测试文本集合，每个文本的平均精度值就是评估整个集合的分类好 坏的标准。 本文主要采用召回率和精确率评测分类器模型的性能。 2 6 3 测试方法 1 封闭性丌放性测试 所谓封闭性测试，就是将训练集合中的文本也作为测试文本进行分类测试，即 测试文本也参与训练过程。开放性测试时，使用的测试文本没有参与训练过程，仅 作为测试文本存在。丌放性测试的结果更具有实用意义，因为在实际工作环境中， 待分类的文本基本上是以前没有接触过的。而且一般封闭性测试结果比丌放性测试 结果好，当训练语料库的规模达到相当大的程度，其封闭性测试结果与开放性测试 结果应趋吻合。在测试中，训i 练文本和测试文本的数量均应该达到某一个相当的数 量值，这样才能保证测试的客观性。己经有人通过采用了两种测试方法即封闭性测 试和开放性测试证明同样条件下封闭性测试的查全率比开放性测试的查全率平均 1 2 基于类别均衡的文本分类算法研究 高8 。 2 大类，j 、类测试 大类测试指对分属于完全不同的领域的各类文本进行测试，小类测试指对同属 于某一大类的各小类文本进行测试。实验证明大类测试的查全率能够达到9 5 ，远 远高于小类测试的7 0 的平均查全率。 在本文的工作中，选用了对小类的开放性测试方法。 2 7 本章小结 本章从分类流程入手，分别讨论了流程中的文本预处理、文本特征选取、文 本表示、文本分类以及分类评测等几个步骤。流程中两个重要步骤特征选取 和文本分类，本文将在第二、三章中做详细分析。 第三章特征项提取及权重计算 第三章特征词提取及权重计算 本章主要分析了向量空间模型、特征选取和特征权重计算的改进。其中，特征 选取方法包括：特征词提取( 降维) 和特征词权重计算。目前特征选择的方法主要 有：d f 、i g 、m i 、c h i 、p c a 和c f d f 。特征权重计算方法主要有：t f i d f 算法。 3 1 向量空间模型 向量空间模型的基本概念可以描述为1 6 】： 1 文本( d o c u m e n t ) 泛指一般的文本或是文本中的片断( 段落、句群或句子) ，一般指一篇文章l l “。 2 特征词( t e r n l ) 文本的内容特征常常用它所含有的基本语言单位( 字、词、词组或短语等) 束 表示，这些基本的语言单位被统称为文本的特征词，即文本可以用特征词集( t e r m l i s t ) 表示为d o i ，f 2 ，) ，其中“是特征词， = = 。 3 特征词权重( t e 咖w e i g h t ) 对于含有n 个特征词的文本d ( f 。，f ：，f 。) ，特征词f 。常常被赋予一定的权重 w 。，表示它们在文本d 中的重要程度，即d = d “，w ；，：，w ：；，。，w 。) 。简记为 d = d ( w l ，w ”，w ) ，这时f t 的权重为m ， 丑。，则项d ，称作 为主分量。可以证明( _ ，如，丑。) 的变化与以降序方式形成的协方差距阵r 的数据 特征值的变化相对应，而单位向量( “，“：，卅。) 也与r 的特征向量对应。为了将特 征空间的维数从 降到p ( p m i 。 必须得指出的是上述结论并不是绝对的，由于文本的种类多种多样，文本使用 的自然语种也有较大差别，因此各种方法比较得出的结论可能会略有差别。 3 2 2 特征词重构 对于预先确定的1 丁i i r i ，特征重构是将原有的特征集了加以联系和转化以构 建新特征集丁的过程，从而使得降维的效果最大化。由于多意词、同音异意词、同 义词等问题的存在，原始特征词可能不是文本内容表示的最佳维度。特征词重构的 方法是试图通过重构新特征词的方法来避免这些问题。每种特征词重构的方法包 括： 1 ) 一种从原有特征词重构新特征词的方法。 2 ) 基于新构建的维度从原先的文本表示转换为新的文本表示的方法。目前主 要有两种特征重构方法：即特征词聚类( t e r n lc l u s t e r i n g ) 和潜在语义标引( l s i ) f 2 9 1 。 1 特征词聚类 特征词聚类就是试图将在语义方面具有高关联性的特征词分组，使用该分组代 替这些特征词作为向量空间中的维度。特征词聚类是有别于特征选择的，因为前者 试图阐述特征词之间意义方面的关联性，而后者则主要着眼于不提供信息的特征 词。 l e w i s 是首次在文本分类中研究特征词聚类的学者。他采用的方法称为相互近 邻聚类算法，该算法中形成聚类的方法是根据某种计算相似度的量度计算特征词之 问的相似度而产生聚类。其结果明显不如单词标引有效，当然其中的原因可能是聚 类方法低效的原因。正如l e w i s 所言，“聚类中获得的关系大多情况下都是偶然的， 而不是期望的系统性的关系”。 l i 和j a i n 根据在训练文本中特征词之间同时出现以及同时消失的情况，观察了 它们之间的语义关联性。通过在层次聚类算法语境中使用特征词聚类技术，发现只 提高了一些边际效应，然而由于研究中所采用的文本数量太小，因而很难得出任何 明确的结论。 由于特征词聚类不受与类别标识相关联的文本的影响，因而l e 州s 与“以及j a i n 都是无指导聚类的例子。b a k e r 与m c c a l l 啪提供了有指导聚类的例子，因为他们采 第三章特征项提取及权重计算 用的分布式聚类方法是将在单个相同类别或者类别组中的这些特征词进行聚类。他 们的研究基于朴素贝叶斯分类器实现，l r i 矿i 的比值达到1 0 0 0 时也仅有2 的效率 缺失。后来由s l o n i m 与t i s t l b y 开展的研究证实了有指导的聚类方法在特征重构中的 潜在价值。 2 l s i 在l s i 模型中，文本集表示为m n 的词一文本矩阵 爿= b ， 式中，n 为文本集中的文本数；川为文本集中包含的所有不同特征词的个数；口。为 非负值，表示第f 个特征词在第，个文本中出现的权重。不同的特征词对应矩阵爿中 不同的一行；每一个文本则对应矩阵一的一列。通常口。要考虑来自两方面的贡献， 即局部权值( f ，) 和全局权值c ( f ) ，它们分别表示第f 个特征词在第个文本和整 个文本集中的重要程度，这样有 吼= 三( f ，) c | ( f ) 词一文本矩阵爿建立后，利用奇异值分解计算爿的女秩近似矩阵 4 0 m i n ，”) ) 。经奇异值分解，矩阵爿可表示为三个矩阵的乘积： 爿= u y 7 式中，u 和y 分别是爿的奇异值对应的左、右奇异向量矩阵；y7 是y 的转秩； 爿的奇异值按递减排列构成对角矩阵。取u 和y 最前面的女个列构建爿的秩 近似矩阵 式中u 。和的列向量均为正交向量。假定一的秩为r ，则有 u 7 u = y 7 y = ，式( 3 1 j ) 用4 近似表征原词一文本矩阵爿，己，。和k 中的行向量分别作为特征词向量和 文本向量，在此基础上进行文本分类和其他各种文本处理，这就是隐含浯义索引技 术。尽管l s l 也是用文本中包含的特征词来表示文本的语义，但l s i 模型并不把文本 中所有的特征词看作是文本概念的可靠表示。由于文本中特征词的多样性很大程度 上掩盖了文本的语义结构，l s i 通过奇异值分解和取七秩近似矩阵，一方面消减了 原特征词一文本矩阵中包含的“噪声”因素，从而更加凸现出特征词和文本之间的 语义关系：另一方面使得特征词、文本向量空间大大缩减，可以提高文本分类的精 确率。 基于类别均衡的文本分类算法研究 3 2 _ 3 特征词的可分离性判别 特征提取的任务是求出一组对分类最有效的特征，因此需要一个定量的准则来 衡量特征对分类的有效性。具体来说，把一个高维空间变换成为低维空间的映射很 多，哪种映射对分类最有利，需要一个比较标准。 各文本要分开是因为它们位于特征空间中的不同区域，显然这些区域距离越大 可分性就越大。对于空间中两个点之间的距离度量可用下面方法来求。 先考虑最简单的两个类别的情况，及，中任一点与，中的每点都 有个距离，把所有这些距离相加求平均，可用这个均值来代表这两类之削的距离。 下面考虑多类并推导表达式。 令z ，z j 门分别为。类及国，类中的d 维特征向量，j k ”z ) 为这两个向量 间的距离，则各类特征向量之间的平均距离为： 以) = 三喜哮j 去砉喜j 刺