（计算机软件与理论专业论文）文本分类中特征向量空间降维方法研究.pdf

摘要 万维网络信息的激增使得人们在面对海量的信息时很难进行选择，文本分类正是为了解 决万维网信息检索杂乱无章的现象，作为一种信息组织和管理的技术被提出来的。然而与人 工分类问题相比，自动文本分类面临许多问题，主要有： 1 ) 用于文本表示的向量空间的维数过大，在这种高维的向量上运用分类算法，很难有 大的区分度以区分不同的类别； 2 ) 训练文本集必须要覆盖向量空间中的所有特征词，否则通过训练得出的分类器有可 能出现偏差，然而对于一个高维的向量空间，要覆盖所有的特征词是很困难的。 为了克服上述两个主要问题，特征向量空间降维的概念被提了出来，其方法在近年来得 到广泛的关注和研究。本文在前人工作的基础上，着重对基于概念统计的降维方法进行了研 究。 本文首先对文本分类的基本概念和知识进行了归纳，分析了文本的向量空间模型的表示 效力以及它对于分类效果的影响因素；讨论了对特征向量空间进行降维的必要性和基本思 路：在对特征词局域性分析的基础上探讨了局部降维的优势；分析了已有的特征空间降维算 法，并总结了它们各自的优缺点；讨论了特征词选择和析取的原则及其主要方法。 在此基础上本文分析了词形统计的局限性并阐述了引入概念的优势；分析了概念间的层 次结构关系；基于对现有的向量空问降维技术的剖析，融合概念分析的方法，提出了一个基 于概念统计的向量空间降维方法：并根据在实验中发现的问题对算法进行了改进，使得算法 更加完善，并分析了主要算法的时间复杂度。 该方法首先对训练文本集中的每篇文本提取出原始的特征词，经过去除停用词、词义消 歧的处理后，在类的内部利用概念间的层次关系( 主要是上下位关系) 用基于概念统计的方 法对特征向量进行局部降维。得出的向量与降维前相比，低频特征词的数目大为减少，高频 特征词数目增多，且高频特征词的频度得到加强，特征词总的数目减少，向量的维数降低， 对于所属类别具有更强的关联性和较好的表示效力，特别是具有较低的冗余和噪音，很好地 达到了降维的目的。 在对所给算法进行详细说明的基础上，本文对该算法的有效性和可行性用实验进行了评 估，分析了实验数据，对实验结果中特征词的频度分布的各种情况探讨了其产生的原因，并 对将本文所给算法得出的特征向量运用于具体的文本分类时可能出现的结果进行了分析。另 外，本文还对f 围值的选取及其依据等降维处理时的取舍策略做了进一步的研究，实验结果也 证明本文的阁值选取具有合理性。 关键词：文本分类、向量空间模型、降维、概念统计、w o r d n e t a b s t r a c t t h ep r o l i f e r a t i n gw e bi n f o r m a t i o nm a k e sp e o p l eg e ti nt r o u b l ew i t hf i n d i n gw h a tt h e yw a n t a s at e c h n o l o g yf o ri n f o r m a t i o no r g a n i z a t i o na n dm a n a g e m e n t , t e x tc l a s s i f i c a t i o n ( t c ) i sb r o u g h t f o r w a r dt or e s o l v ed i s o r d e r l ya n du n s y s t e m a t i cp h e n o m e n o ni ni n f o r m 撕o nr e t r i e v e b u t c o m p a r i n gt om a n u a lt e x tc l a s s i f i c a t i o n , a u t o m a t i ct e x tc l a s s i f i c a t i o nf a c e sw i t hm a n yp r o b l e m s ， m a i n l ya r e ： i ) t h ed i m e n s i o no f v e c t o rs p a c em o d e lf o rt e x tr e p r e s e n t a t i o ni st o ol a r g et h a ti ti sd i f f l c u k t o d i s t i n g u i s hd i f f e r e n tc l a s s e sw h e nc l a s s i f i c a t i o na l g o r i t h mi su s e do nt h el a r g e d i m e n s i o nv e c t o rs p a c em o d e lf v s m ) 2 ) t r a i n i n g t e x ts e tm u s tc o v e ra l lt h ec h a r a c t e rw o r d si nv e c t o rs p a c em o d e l ，o rt h ec l a s s i f i e r b yt r a i n i n gm a yb ew a r p e d b u ti ti sa l s od i f f i c u l tc o v e ra l lt h ec h a r a c t e rw o r d sf o rs ol a r g e d i m e n s i o nv e c t o r t or e s o l v et h e s et w om a i np r o b l e m s ，t h ec o n c w d to fd i m e n s i o nr e d u c t i o n ( d r ) i s p u tf o r w a r d t h em e t h o d so fd rh a v eb e e nw i d e l ya t t e n d e da n dr e s e a r c h e di nr e c e n ty e a r s o nt h eb a s eo f a n o t h e r sw o r k ，d rm e t h o db a s e do nc o n c e p ts t a t i s t i ci sa m p l yr e s e a r c h e di nt h i sp a p e r f i r s t l y ，b a s i cc o n c e p ta n dk n o w l e d g eo nt ci ss u m m a r i z e d ，a n dt h er e p r e s e n t a t i o ne f f e c t i v e n e s s o fv s ma n di t se f f e c tf a c t o r st oc l a s s i f i c a t i o na 阳a n a l y z e d t h en e c e s s a r ya n db a s i ct h i n k i n go n d ra r ed i s c u s s e d b a s e do na n a l y z i n gl o c a lp r o p e r t yo fc h a r a c t e rw o r d s ，t h ea d v a n t a g eo fl o c a l d ri sd i s c u s s a d e x i s t e n ta l g o r i t h m so nd ra r ea n a l y z e da n dt h e i rm e r i t sa n dd e m e r i t sa r e s m n m e du p a n dt h ep r i n c i p i ea n dm a i nm e t h o d so nt e r ms e l e c t i o na n de x t r a c t i o na r ed i s c u s s e d o nt h i sb a s e , t h el o c a l i z a t i o no fm o r p h o l o g ys t a t i s t i ci sd i s c u s s e da n da d v a n t a g eo fi m p o r t i n g c o n c e p ti se x p o u n d e d h i e r a r e h yr e l a t i o na m o n gc o n c e p t si sa n a l y z e d b a s e do na n a t o m yt o e x i s t e n tt e c h n o l o g yo nd r , t o g e t h e rw i t hc o n e e p ta n a l y z em e t h o d ，ad ra l g o d t h mb a s e do n c o n c e p ts t a t i s t i ci sp u tf o r w a r d a n dt h ea l g o r i t h mi si m p r o v e db yp r o b l e m sf o u n di ne x p e r i m e n t s t h i sm a k e st h ea l g o r i t h mp e r f e c t t h ep r o c e s si s ：d i s t i l l i n go r i g i n a lc h a r a c t e rw o r d sf r o mt r a i n i n g t e x ts e t , w i p i n go f fs t o pw o r d s ，r e m o v i n gd i f f e r e n tm e a n i n g s ，a n dd o i n gd rb a s e do nc o n c e p t s t a t i s t i ci nl o c a ld o m a i nu s i n gh i e r a r c h yr e l a t i o na m o n gc o n c e p t s c o m p a r i n gt h ev e c t o rb e f o r e d i m e n s i o nr e d u c t i o n , t h er e s u l tv e c t o rh a si e s sc h a r a c t e rw o r d so f l o wf r e q u e n c y , m o r ec h a r a c t e r w o r d so fh i 【g hf r e q u e n c y , t h eh i g hf r e q u e n c yi ss t r e n g t h e n e d ，t h en u m b e ro fc h a r a c t e rw o r d si s r e d u c e d ，a n dt h ed i m e n s i o ni si o w e r e d i th a ss t r o n g e ra s s o c i a t ew i t hc l a s st h a tb e l o n g st oa n d b e t t e rr e p r e s e n t a t i o n , a n ds p e c i a l l yh a sl o w e rr e d u n d a n c ya n dn o i s et h a nb e f o r e s ot h ed r o b j e c t i sw e l la c h i e v e d o nt h eb a s eo fd e t a i l e de x p l a i nf o rt h ea l g o r i t h m ，t h ev a l i d i t ya n df e a s i b i l i t yo ft h ea t g o r i t h m a r ee v a l u a t e db ye x p e r i m e n t n 璩e x p e r i m e n tr e s u l ti sa n a l y z e d a n dt h er e a s o nf o ra l lk i n d so f c h a r a c t e rw o r d sf r e q u e n c yd i s t r i b u t i n gi sd i s c u s s e d m o r e o v e rt h ep o s s i b l er e s u l ti sf o r e c a s t e d w h e nt h ev e c t o ri su s e dt om a t e r i a lc l a s s i f i c a t i o n i na d d i t i o n ，t h ea c c e p to rr e j e c tp o l i c yd u r i n g d 凡s u c ha st h r e s h o l ds e l e c t i o na n di t sf o u n d a t i o n ，i su l t e r i o rs t u d i e d a n de x p e r i m e n tr e s u l t p r o v e st h et h r e s h o l dt h a ni ss e l e c t e di nt h i sp a p e rm e e t st h en e c e s s a r yo f p r a c t i c e ， 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 , d i m e n s i o nr e d u c t i o n ，c o n c e p t i o n s t a t i s t i c , w o r d n e t 珏 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：隘鏊羞：日期：三竺! ：! ：j 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：莅：赞导师签名 研究生签名：1 7 、篁煎一导师签名 期：礁矽， 掣 第一章弓 言 1 1 研究背景 第一章引言 当今，科技的飞速发展使得信息传播从依靠如报纸、杂志等传统的媒体更多地转移到计 算机能够直接访问的媒质上来，同时网络作为一种更方便快捷的信息传播和交流方式已被大 多数人所接受，人们越来越习惯于在互联网上搜寻和发布信息，进而也就促进了因特网的不 断普及和发展。反过来，这一进程又加速了信息量的激增，其增长的速度超过了以往任何一 个时代。 网络信息量的激增丰富了人们的视野，也改变了人们获取信息的方式，但是面对潮水般 涌来的信息，很多人都感到难以选择，因为从这些杂乱的海量信息中找到我们真正感兴趣的 信息需要花费很多的时间和精力。为了能够解决目前网上信息杂乱的现象，使人们能够以更 高效地方式获取自己所需要的信息，各种信息组织和管理的技术被提出来，如文本检索、文 本分类、主题概念识别等等。其中，文本分类是给定分类体系，然后将文本分到某个( 也可 以是某几个) 合适的类别中的过程。文本分类可以用于为文本建立索引，提高文本检索的质 量：通过它给文本加上标签，用于电子邮件、新闻等文本的过滤；抽取符号知识、新闻发布、 排序电子邮件、个人信息助理、信息检索以及自动索引等“。皿”】【l ”】。总之，文本分类已 经成为一项具有较大实用价值的关键技术，是组织和管理数据的有力手段。 文本分类分为人工文本分类和自动文本分类，本文主要讨论自动文本分类的问题。大多 数情况下，自动文本分类基本都采用了向量空间模型( v e c t o rs p a c em o d e l ) ，该向量空间模 型中的f 句量由特征词( t e r m ，从文本中直接提取出或通过某种方式变换后选取的，可以表 示文本类别特征的词) 和其权值( w e i g h t ) 组成，每篇文本被表示成上述形式的一个向量， 称为特征向量。与传统的人工分类问题相比较，自动文本分类面临许多问题，主要有： 1 用于文本表示的向量空间维数过大，在这种高维的向量上运用分类算法，各个类别 之间的区别可能不是很大( 原因详见3 1 1 ) ，不能够区分不同的类别。 2 训练文本集必须要覆盖向量空间中的所有特征词，否则通过训练得出的分类器( 用 于判断类别归属的程序模块) 有可能出现偏差，然而对于一个高维的向量空间，训 练文本集要覆盖所有的特征词是很困难的。 由此可见。一个好的文本表示方法直接关系到分类的效率与准确度，而向量空间的维数 过大是其中的突出问题。通常的做法是，在形成了文本的特征向量之后，要先对该向量进行 降维，然后再进行后继的处理。 假定原特征向量为t ，其维数是，所谓特征向量降维( d i m e n s i o n a l i t yr e d u c t i o n ，d r ) 就是将该向量通过某种方法变化为向量t ，并且要求i t i i t l ( 即i t 腰远小于i t l ) ，同时还 要使得新向量t 能够更好的表达该文本的信息。降维绝不单单是使向量的维数缩小，而是通 过剔除那些对类别区分作用不大的特征词，保留区分作用较大的特征词来更好的表示一个文 本。有效的特征向量空间降维，不仅可以提高分类算法的运行效率，而且可以大大提高分类 的精度。随着文本分类技术的广泛应用，对特征向量降维的研究也越来越为人们所重视。 1 2 研究现状 到目前为止，特征向量降维的方法主要有以下几类： 1 基于词形统计的方法。较典型的有特征词选择方法( 详见3 2 1 ) 等。由于向量空 间模型本身就是基于统计的文本表示方法，所以这类方法首先被人们想到并利用。 东南大学硕士学位论文 同时，它也是现有其它各类方法的基础，这些方法或多或少都会借鉴词形统计方面 的一些研究成果。例如：f i t t l 9 9 5 采用的方法，根据文本频度的阀值，将至多在x ( 通常为1 3 ) 篇训练文本中出现的词去掉，从而达到减少特征词数目的目的； 【c a r 2 0 0 1 采用的信息增益方法，它利用信息领域中熵的概念，以选择为分类所能 提供的信息量多的词； c a r 2 0 0 1 中采用的另一种方法是c h i 统计量的方法，它是 通过计算特征词与类别之间的相关性，来达到较好的降维效果。国内也有学者研究 此方面的问题。如 z h o u 2 0 0 1 提出了隐含语义索引方法( 详见3 2 3 ) ，采用隐含语 义索引的方法，通过矩阵的奇异值分解将词一文本矩阵投影到一个低维的空间，并 用实验验证了其有效性。 l i f 2 0 0 1 用评估函数代替t f * i d f 框架中的i d f 函数( 详 见2 1 2 ) ，从如何放宽特征独立性假设利用等级关系角度探讨了对特征筛选可能的 改善。这些方法基本上都是着重考虑词的形式，优点是不受领域知识的限制，虽然 也有的考虑了语义的因素，但主要是通过数学方法计算某种相关性来得出单词间的 语义关系。 2 基于概念知识的方法。此类方法通常是将特征词抽象为特征概念，这样在文本分类 时处理的是概念而不是词。与词相比，概念可以更确切地概括和表达词义，同时也 符合人们进行分类的潜规则。当然，这种方法也要依靠一些统计的方法作为辅助手 段，而且通常要依靠额外的资源、如语义词典等。现有的常用方法，一般是将词抽 象为概念并利用概念间的语义关系对特征空间进行降维的处理。其中，利用较多的 是同义词关系和概念间的上、下位关系，也有的考虑不同概念的相关性等特性。例 如， r o d l 9 9 7 的研究利用了同义词集，而在 s a m l 9 9 8 同时利用了同义词集和上 位词集。 3 从语言学的角度来考虑、主要是通过自然语言理解的方法。这种方法重视文本的整 体内容和内涵，强调的是对文本内容的理解。在理论上这一方法非常完美，但是在 实现过程中则还有很多困难需要克服。 z h u l 9 9 9 - - 文中利用基于多特征的相似评 估技术自动获取名词短语结构规则，能够从没有任何标注的生活语料库中自动获取 数据。 另外，其他领域的一些方法也可以借鉴到降维的方法中来。比如 c h i l 9 9 7 中主题概念 提取的方法中对概念间上下位关系的运用， a l b 2 0 0 3 】中提出的词义消歧方法也可以用于特 征向量降维的预处理阶段。 1 3 本文研究目标 为了对特征向量进行有效的降维，本文将分析特征向量表示的有效性评价指标，讨论现 有的特征向量空间降维方法及其优缺点，并在文本分析的基础上。发掘特征词间的关联关系 以提供消除歧义现象的手段，将词抽象为概念，根据概念间的关系，用基于概念统计的方法 提出对特征向量空间进行降维的具体算法并进行有关实验，以解决文本分类的基础一文本表 示中涉及的语义方面的问题( 比如一词多义、同义词等) ，同时语义化特征向量的表示，解 决文本特征向量的有效表示问题。 1 4 本文研究内容及解决阔题的思路 本文要展开的主要研究内容及其解决思路如下： 1 如何进行特征词的提取。不同格式的文本具有不同的组织结构，处于不同位置的词重要 度也有所不同。本文将通过对文本的结构进行剖析，针对文本结构和词的位置的不同， 给出不同文本的相应的分析及提取特征词的方法，并将其应用于初始特征词的提取。 2 如何利用概念统计的方法进行特征空间的降维。对于提取出来的初始特征词，要在语义 2 第一章引言 词典r d n e t f b l 1 9 9 3 1 1 n o u l 9 9 3 1 的帮助下，利用其对概念间不同关系的清晰描述来解决英 文文本中出现的歧义问题，并在得到确定语义表述的概念特征向量的基础上，利用上位 概念的归纳作用和同级的概念间的重要度的不同，对该向量进行降维处理，充分挖掘文 本蕴涵的语义，给文本分类提供高质量的特征向量表示。本文考虑的思路是：先统计文 本中出现的所有词的出现频度，去掉停用词，发现词与词之间的关联关系，利用这种关 联关系并根据词语在w o r d n e t 中的上位词序列所表达的关系寻求词义的聚类以达到词 义的消歧，最后构造文本中概念的语义层次树，通过计算概念的归纳度和重要度等指标 来完成向量空间的降维。 3 对于本文提出的方法，探讨其优缺点及相关的问题，给出测试结果及分析。 1 5 本文章节安排 本文共分为五章。 第一章为引言，简要介绍问题提出的背景、国内外研究现状，提出本文的研究目标和研 究内容，以及给出论文的章节安排。 第二章介绍文本分类的基础理论，包括向量空间模型的表示方法、文本分类涉及的两个 阶段及其算法，分析特征向量表示的有效性，为第三章的分析做好理论基础方面的准备。 第三章阐述向量空间降维的必要性及分类，介绍和分析特征空间降维的现有方法，指出 其优点和不足。 第四章在分析特征词局域性和引入概念的优势的基础上提出借助w o r d n e t 的基于概念 统计的特征空间降维的方法，并给出实验数据与分析。 第五章总结本文的主要工作，分析存在的不足并提出对今后工作的展望。 3 东南大学硕士学位论文 第二章文本分类基础 如第章所述，本文的主要目标是要对文本的特征向量实施有效的降维，而降维工作是 完成文本分类任务中的一项必要步骤。因此，要对降维方法进行深入的讨论，就必须了解与 文本分类有关的基本概念、基本方法，特别是其中的文本表示问题 而且，不了解文本分类 中使用的训练和分类算法，也就无法进行第3 章中的特征向量降维必要性分析。因此，本章 将对上述这些相关内容进行讨论。 2 1 文本表示一向量空间模型 通常情况下，文本分类所要处理的文本是采用自然语言描述的，计算机并不能够理解这 些文本的内容。如果在分类之前投有将这些文本转化为计算机能够直接处理的形式，那么将 很难对它们作自动分类的处理。计算机可以处理的内容般为统一且格式化的，所以在自动 文本分类中，首先要完成的一步就是对文本进行形式化的处理，即采用一种简化、统一的方 式来实现对文本内容的描述，以适应计算机处理的需要，通常把这个过程称为文本的表示。 文本的表示方法必须能够正确、全面地反映一篇文本的特征，基于向量空间模型的表示 方法是在文本分类领域中采用最多的一种经典表示方法，该方法的具体处理措施是：把每个 文本都表示成由特征词和其权值表示的向量，这个过程在有些文献中也称为标引( i n d e x i n g ) 。 这样，一篇文本就被形式化力n 维向量空闯中的一个点( 其中1 1 表示文本中特征词的数目) ， 其一般形式为；v c f f ( w l ，w 2 ，w 。，) ，其中表示第i 个特征词的权值。一个文 本集合继而就被表示成一个特征词一文本矩阵w = ( w 曲，表示特征词f 在文本k 中的权值， 由于各个特征词一般不会在很多文本中同时出现，所以w 是一个稀疏矩阵。 各种分类方法最重要的区别在于它们选取特征向量的方法，以及使用的训练算法和分类 算法。在本节中我们将讨论与文本表示相关的特征向量选取的方法，训练和分类算法将在下 一节中讨论。 在向量空间模型中，特征向量表示所涉及的因素主要是：特征词的粒度和特征词权值的 计算方法。所谓特征词的粒度是指选取什么形式的词作为特征词。选取不同的特征词粒度或 采用不同的权值计算方法，往往会对文本分类的效果产生相应的准确与否的影响。因此我们 要对常见的特征词粒度选取和权值计算方法分别作一些讨论。 2 1 1 特征词的粒度 通常，我们可以选择单词、短语、概念等作为特征词。英文的最小语义单位是单词，且 单词与单词之间以空格作为分隔符。所以从文本中最初提取出来的一般是单词，单词再经过 进一步的处理成为短语、概念等。下面分别讨论特征词的粒度为单词、短语、概念时的情况。 1 以单词作为特征词。这是最简单的特征词表示。向量中的每个特征词对应于文本集 中的一个单词，一般会忽略大小写区别。实际操作中并不把所有的单词都作为特征 词处理，通常会去掉“停用词”( s t o pw o r d s ) 表中的词，“停用词”表中存放有不 包含分类信息的介词、连词等词。同时为了不使同一词源的词多次出现，常常还采 用提取词干的方法去掉单词的后缀，比如“t e a c h ”、“t e a c h e r ”、“t e a c h i n g ”都被转 化为其一般形式“t e a c h ”存放于特征向量中。 2 以短语作为特征词。以单词作为特征词，忽略了语法结构，段落、句子和单词的顺 4 第二章文本分类基础 序没有被考虑在内，因而原文本中相当数量的信息没有被有效地表示出来。而单词 在不同的短语中意义往往是不同的，采用短语作为特征词正是为了保留更多的区分 类别的特征信息。从文本集中抽取短语不外乎两种方法：其一是统计方法，通过对 词的共现概率统计而实现对短语的发现，这种机器学习的方法能够适合于广泛的领 域，但是需要大量的训练样例：其二是基于规则的方法，通过标注词典以及组词规 则来识别短语，但是该方法在语法上不够灵活，而且很难解决词义的歧义性，同时 词典中不可能包含所有的自然语言词汇，也很难穷尽所有的组词规则。 3 以概念作为特征词。这种方法是通过将源文本中的单词根据某种联系进行合并，最 大化内部的相似度，最小化类间的相似度，并进而将词抽象到概念层次，以此来生 成特征词。这样产生的特征词包含较多的语义信息且因为相似的信息被合并而具有 较低的冗余。该方面所涉及的一些方法与与本文的研究有着很密切的联系，因此本 文将在第四章中详细讨论这些方法。 此外，还有一些形式也可以作为特征词，比如n 元组、某种规律性的模式等( 参见 w a n 9 2 0 0 2 】) ，但主要还是以上三种用得较为广泛。这三中中后两种是在前一种的基础上通 过某种方法组合或综合而成，d a v i dl e w i s 等一致认为在英文分类中采用优化合并后的特征 词比较合适l x a t l 9 9 9 ；由于我们也希望将语义的因素考虑进来，故本文研究的方法主要以概念 作为特征词。 2 1 2 权值的计算方法 特征词的权值表示了特征词的重要程度。对于特征词权值计算的最基本的思路是：在 篇给定文本中，一个单词出现的次数越多，就认为它与该文本的类别相关度越大，从而权值 越大；一个单词在全体文本中出现的次数越多，则它与特定文本的类别相关度就越小，权值 t g , 就越d 、。常用的权值计算方法有以下几种，其中m k 表示特征词i 在文本k 中的权值即重 要程度。 1 t f ( t e r mf r e q u e n c y ) 框架，其权值定义为： k = 巩= 黜 这里c o u n t i 表示特征词f 在文本k 币的出现次数，c o u n t ( d k l 表示文本k 中特征 词总的出现次数，即以特征词i 在文本k 中的出现频率值巩作为权值。这是最基 本的一种方法，计算也较为简单。 2 布尔框架( b o o l e a n w e i g h l i n g ) ，其权值定义为： i1 特征词i 出现在文档k 中 “ 1 0否则 即文本k 中出现了特征词f 则它的权值为1 否则为0 。这种方法不需进行计算，但 是由于特征词只要出现其权值都为1 ，所以权值之间没有区别。 3 t f * i d f 框架，其权值定义为： = 砜1 d f , 东南大学硕士学位论文 t f j k 的定义同l ，逆文本频度1 d f t ( i n v e r s ed o c u m e n t f r e q u e n c y ) 是通过文本频度 d f t ( d o c u m e n t f r e q u e n c y ) 来定义的。d f i 指整个文本集合中包含特征词i 的文本 个数，d f t 值越大，包含特征词f 的文本数越多，特征词i 代表文本k 的能力越小， 反之则代表的能力越强 逆文本频度i d f i = l o g ( n d f i ) ，n 为整个文本集中的文 本个数，故权值与皿一成正比与d f t 成反比。这种方法既考虑了特征词在单个文 本中的出现频率也考虑了特征词在所有文本中的出现频率。 4 t f c 框架，其权值定义为： z e 。x 1 d f , “。阢弼j 2 其中m 为特征词的个数。t f c 框架加入了对文本的长度因素的考虑，该权值是 t f * i d f 框架的归一化。 5 基于特征词的熵这是一种基于信息理论的方法，其权值定义为： w t k = l o g ( t f * + 1 0 ) x ( 1 + j ) 舯馒特征m 麟其计算蜮加2 击善嘿l o g ( 器) 】， 表示文本集中文本的标号) ，如果某特征词的分布是均匀的，则其熵等于一1 ，权值 为0 ，分布均匀说明该特征词在很多文本中出现，故认为其代表某一文本的能力较 弱；若该词只在一个文本中出现，则其熵为0 ，权值达到最大，为l o g ( t f 。+ 1 o ) ， 这时认为该特征词代表这一文本的能力强。 第1 、2 种方法的计算较为简单，但没有考虑单词在所有文本中的出现频率，而事实上 单词在所有文本中的出现频率也是单词包含信息多少的一个标志；第3 、4 种方法通过计算 文本频度考虑了这一因素，较之第1 、2 种方法更为全面地考虑了影响权值的因素；而第5 种基于熵的方法是以信息理论中的结论为依据，具有较强的理论基础。为了初始计算上的简 便，本文实验中使用特征词的出现频度来表示其权值，虽然没有更全面地考虑对特征词的权 值有影响的其它因素，但本文所给出的后续操作会消除其潜在的不利影响。 2 2 文本分类的相关算法 文本分类是一个典型的有导师的机器学习问题，其解决过程一般分为训练和分类两个阶 段。本节将讨论训练和分类以及其中所要用到的算法。 2 2 1 文本分类的两个阶段- n 练和分类 文本分类一般首先要利用已有文本对分类规则进行训练，以生成一个能够准确区分文本 类别的分类器，然后根据此分类器确定文本类别，因此分为训练和分类两个阶段： 1 训练阶段，其主要步骤为： ( 1 ) 定义类别集合c = c i ，c 。 ，类别之间的关系可以是层次的( 即从属的) 也可以是并列的。 ( 2 ) 给出训练文本集合s = s i ，s 。) ，每一个训练文本s j 事先都被标上所属的 类别标识c ，。 ( 3 )对于训练集中的所有文本，根据2 1 节所介绍的特征词的选取规则和权值 第二章文本分类基础 的计算方法得出其特征向量，然后依据该特征向量和该文本所属的类别， 并根据特定的训练算法构造分类规则，以形成分类器。这个过程可以说是 一个从特殊到一般的过程。 2 分类阶段，其执行过程为： ( 1 ) 对于某个待分类的文本d k ，根据训练阶段得出的特征词集分词得出其特征 向量( v d k ) ，通过分类器所采用的规则判断它属于哪一类。 ( 2 ) 给出所要求取的该文本的类别。 2 2 2 训练算法和分类算法 训练算法和分类算法是分类的核心，前者的关键是如何形成分类所要依据的规则，而后 者的关键是如何确定文本的类别，它们的好坏决定了文本分类的准确与否。目前存在多种基 于向量空间模型的训练算法和分类算法，如向量距离算法、贝叶斯算法、k 近邻算法、支持 向量机算法、神经网络算法和最大平均熵算法等 t o m 2 0 0 3 。由于前三种算法与本文的后续讨论 关系更密切，放下面主要讨论这三种算法。 1 ) 向量距离算法 在训练阶段运用该算法，首先是为每一个类别生成一个中心向量( 即表示这一类别 文本的特征向量) ，一般取该类别训练文本特征向量的算术平均；然后在分类阶段根据 特征词分词确定待分类文本的特征向量，计算该向量与每类中心向量间的相似度，这里 称为距离，最后将距离最近的类作为该文本的类别。距离s i m 的计算公式为： s i m ( 弓) 2 艿笋弋f i 忑，其中砬为新文本的特征向量，弓为第，个类的 、l 候】i 嵋i 中心向量，肘为特征向量的维数，w 为向量以的第价分量。该算法独特的地方是要确 定一个类别的中心向量，然后根据此中心向量判断新文本的类别。 该算法是基于概率统计的算法，它以词在文本中出现的比率作为它属于某个类别的 概率，并综合考虑诸特征词属于各个类别的概率来计算文本属于各类别的概率，最后将 所属概率最大者作为该文本的类别。其具体计算过程及公式如下： 计算每个特征词属于各个类别的概率，这样在训练阶段，对于每个类另们就形成 了向量( ”抽 i ) ，其中”f 表示第竹特征词属于第，类的概率，其计算方法为： 一啡篇嚣罴器* 砸l + e 恩型l n ( 而t i , d k ) 其中1 吲表示c 类中不同的特征词的个数，1 d i 表示类c 的训练文本的个数， 表示第 在分类阶段，当新文本以到达时先根据特征词分词，然后根据下文中所给公式 计算该文本靠属于类c j 的概率，它是用文本中每个特征词属于各类别的概率进行综 合计算而得： 7 东南大学硕士学位论文 pc j l d 。；扪= 其中尸( ql 各 = 鼍糕，p ( c ，i 刍 按类似方法算出，旧为类的总数， 仇破) 为4 在盔中的词频， 为特征词总数。 比较新文本属于各个类的概率，将文本分到所属概率最大的那个类别中去。 该算法对文本中的词属于类别的概率进行综合，从而确定文本属于类别的概率。 3 ) l 心科( k n e a r e s t n e i g h b o r ，k 近邻) 算法 该算法首先根据前述向量距离公式( 参见1 ) 计算出待分类文本与训练文本集中文 本的相似度，选出k 篇相似度最大( 即距离最近) 的文本，然后根据这k 篇文本所属的 类别确定待分类文本的类别。该算法的具体处理步骤如下： 在训练阶段，根据特征词集合描述训练文本的特征向量； 分类阶段根据特征词对待分类的文本进行分词，计算特征词在该文本中的权值， 确定新文本的向量表示； 按照1 ) 中的相似度，距离计算公式，在训练文本集中选出与待分类文本最相似 的k 个文本。其中，k 值的确定需要经验与实验综合考虑，目前还没有一个普遍适 用的方法。一般采用的方法是：先定一个初始值，然后根据实验测试的结果调整k 值，通常初始值定为几百到几千之间。 根据待分类文本与其k 个近邻的相似度以及这些近邻属于某个类别的归属度，依 次计算该待分类文本属于各个类别的权重，乃表示待分类文本属于身狱的归属度 权重，计算公式如下： 乃2 巾q ) 2 五蠹坼，反q ) 谢赫一征向 量，d k 表示第t 个训练文本，c j 表示射个文本类别，s i r e i 。，畋l 为相似度计算 公式，其计算公式同，中所述，而y ( 五，c ，) 为事先指定的类别属性函数，即若 d 。属于类c ，那么函数值为1 ，否则为0 。 比较文本属于各个类的权重，将其分到归属度权重最大的那个类别中。 该算法是通过训练文本集中的文本的类别来确定新文本的类别。 上述方法中，贝叶斯算法中的特征向量权值计算因只是采用概率而比较固定，其它两种 方法可以采用2 1 。2 节所述的备种权值计算方法。这两种方法都利用了相似度( 即距离) 计算 公式，所不同的是：向量距离算法是在计算出待分类文本与各个类别中心向量的距离后就直 接做出判断，而k 近邻算法是计算待分类文本与每个训练文本的距离，然后根据k 个最近邻 类别的归属情况再做判断。 叠 第二章文本分类基础 除以上介绍的算法之外，支持向量机和神经网络算法在文本分类系统中应用得也较为广 泛，支持向量机的基本思想是使用简单的线性分类器划分样本空间。对于在当前特征空间中 线性不可分的模式，则使用一个函数把样本映射到一个高维空间中，使得样本能够线性可分。 而神经网络算法采用感知算法进行分类。在这种模型中，分类知识被隐式地存储在连接的权 值上，使用迭代算法来确定权值向量。当网络输出判别正确时，权值向量保持不便，否则进 行调整，因此也称为奖惩法。 综上所述，文本分类的过程可以总结为图2 1 图2 1 文本分类过程 图2 1 形象地说明了文本分类中要经历的两个主要阶段，以及文本的表示和训练分类算 法在文本分类中所处的地位。从图中可以看出，训练阶段的作用是构造一个分类器，而分类 阶段则是利用这个分类器来完成分类。另外，文本的表示是文本分类的基础，在文本分类的 两个阶段中都要用到，而本文研究的特征空问降维方法中的一个目的，就是要寻求一种有效 的文本表示方法。 2 3 特征向量表示的有效性 评价一个特征向量表示的有效性，即看它是否能较准确地表示文本，故对一个文本集合 用某一分类算法进行分类时，通常要比较该表示方法及其它表示方法所获得的分类结果。如 果该表示方法得到的结果相对较好，则表明此种方法具有好的表示效力。特征向量的表示效 力受两方面的影响：一是特征词的粒度选取，二是权值的计算。【l e w l 9 9 2 一文中指出：特 征集合的一些性质对表示方法的效力有很大的影响。很多实验的结果也证明了这一点 1o w “”】。因此，本节主要讨论特征词集合对于特征向量表示效力有影响的一些性质。 1 表示的充分性 如果用一个特征集合表示的所有文本都是可以被区分的，也就是说不同的文本在该特征 集合上的表示都是不同的，通常就认为它是充分的。否则无论通过什么样的训练算法也不可 9 东南大学硕士学位论文 能找到一个分类规则来区分训练集中的文本。 2 与训练文本集的关系 表示一篇文本的特征集合中特征词越多，则该文本可能的类别归属就会越多，而寻找一 种准确的分类器也就会变得越困难。对于特定的训练文本集，能够得到的、具有较好表征性 质的特征词数量存在个上限，硬性超过这个上限会使得分类器的效力降低。换句话说，用 予分类的特征词越多所需要的训练文本就越多。这也从另一个侧面反映了特征向量维数过大 的负面影响。 3 对分类算法使用前提的依赖性 大部分的分类算法都使用了一定的假设，如果特征集合违反了该算法所依赖的假设，则 其表示将不能达到预期的效果。比如有些特征集合可能违反了贝叶斯分类算法中的条件独立 性假设，在利用该算法进行分类时就有可能出现性能的下降。所以特征表示方法对分类算法 使用前提的依赖性要尽量的小。 4 。冗余和噪音 有些看上去不同的特征词。实际上可能是一个文本的同一个潜在性质的不同表述，这种 特征词称为“冗余”。冗余对文本的类别归属一般没有什么作用，在某些算法下甚至会干扰 正确的分类，比如在采用k 近邻算法和距离向量算法都要用到距离公式，冗余信息会使距离 计算产生偏差。“噪声”是导致错误分类的特征词。同“噪声”紧密联系的问题是空缺值， 因为一个特征词可能并非对于所有的训练或测试文本都有取值，因而在不含有它的文本中， 其权值就表现为空缺值( 一般被赋予o ) ，而大部分的分类算法基本上都没有采用特殊的技 术来处理空缺值，这样的空缺词就可能将自身放大为噪声。大量包含冗余和噪声的特征向量 不论采用何种分类算法都可能降低分类的正确性肿“”j 。 综上所述，一个在全部文本集上都有效的特征向量