（计算机应用技术专业论文）特定领域半监督文本分类系统的设计与实现.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谤 的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名 论文使用授权声明 f ：| 期：旦2 ：! ：! ： 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名： 复旦大学硕士学位论文 摘要 摘要 这是一个科学飞速发展的时代，借助计算机等工具以及人类历史上长期的 知识积累，各个学科的信息越来越深入和系统，人们迫切需要将这些特定领域 的知识进行系统化的分析和归类从而为以后更深入的研究做好准备，于是特定 领域内的文本分类成为当前研究的一大热点。 目前，特定领域文本分类主要是在传统文本分类的基础上，利用已有的特 定领域知识库对文档进行特征选择，用特定领域内的知识来表示文档。这样就 带来一个问题，如何寻找合适的知识库来尽量准确地表示文本；对于新兴的学 科而言，在尚未形成任何系统化的知识库的时候，又如何进行分类? 因此，理 想的特定领域文本分类方法是能够不借助于任何的领域知识而能够很好的进行 分类。同时，在一般的应用中，由于对训练文档进行标注需要耗费大量的人 力，所以通常在分类任务的训练集合中所给出的正例和负例的数目都是非常有 限的，并且通常标注的正例和负例的文档数目分布也相当的不均衡，大多数情 况下训练集合中都只标注出了少量的正例文本。如何从少量的已标注训练样例 中获得足够的类别信息以辅助分类也是目前研究文本分类的一个难点。 本文综述了现有特定领域文本分类系统的现状，详细介绍了在特定领域 内，对于训练集中正负例分布不均衡，且其中包含有大量未标注数据的半监督 文本分类问题，提出了一种基于紧密度衡量的分类方法。本文讨论了特定领域 半监督文本分类系统的设计与实现细节，并实现了一个用于该类分类问题的系 统。本文的工作主要包括： 本文综述了现有特定领域文本分类的研究现状，指出了现有方法由于需要 依赖于领域相关本体而带来的局限性。 本文详细分析了半监督文本分类问题的研究现状，给出了几种传统的用于 半监督文本分类问题的算法并指出了这些算法的局限性。 提出了一种基于紧密度衡量算法来解决此类的文本分类问题，将通过实验 将该算法与其他传统的基于特定领域内文本分类的方法作了详细地比较与 分析。 设计和实现了一个用于特定领域内半监督文本分类问题的系统，并在 t r e c 0 5 的基因任务数据集上进行了实验，与t r e c 0 5 基因任务的其他 组结果相比，总体的分类效果都有不同程度的提高，显示了这种算法的优 越性和适用性。 复旦大学硕士学位论文 摘要 关键词：文本分类，特定领域，特征选择，半监督机器学习 中图分类号：t p 3 复旦大学硕士学位论文 a b s t r a c t a b s t r a c t w i t ht h ef a s td e v e l o p m e n to ft h es c i e n c et o d a y , t h ek n o w l e d g ei nal o tf i e l d sa r e g r o w nm u c hf a s t e rt h a ne v e lm s o 谢t 1 1t h ew i d e l yu s e do f c o m p u t e rt e c h n i q u e sa sa k e ya n db a s i ct o o l ，t h ee f f i c i e n c ya n dq u a l i t yo fp r o c e s s i n gt h o s eh i g hv o l u m e k n o w l e d g ei sb e c o m i n gh i g h l yi m p r o v e d t h er e q u i r e m e n t so fs y s t e m a t i c a l l y a n a l y z i n ga n dc l a s s i f i c a t i o no f t h ei n f o r m a t i o ni nas p e c i f i cd o m a i ni sm o r ea n dm o r e s t r o n g ，t h e r e f o r et h er e s e a r c ho ft h ec l a s s i f i c a t i o no fas p e c i f i cd o m a i na t t r a c t sm o r e a n dm o r ei n t e r e s t s b u tn o w a d a y sm o s tc l a s s i f i c a t i o nm e t h o d sa r eu s i n gt h ed o m a i n r e l a t e do n t o l o g yt oh e l p i n gt h ef e a t u r es e l e c t i o n f o rm o s to fn e w l yc o m i n gr e s e a r c h f i e l d s ，i ti si m p o s s i b l et of m da nu p t o d a t eo n t o l o g y a l t h o u g hi ns o m ec a s e s ，t h e r e a r es o m eo n t o l o g ye x i t s ，b u th o wt op i c ko u tap r o p e ro m o l o g ya d a p t i n gt ot h e s p e c i f i cc l a s s i f i c a t i o nt a s ki sa l s oad i f f i c u l tp r o b l e m s ot h eb e s ts o l u t i o nf o ra s p e c i f i cd o m a i nc l a s s i f i c a t i o ni s t od e v e l o pan o n - d o m a i nr e l a t e dc a t e g o r i z a t i o n a l g o r i t h mi n d e p e n d e n tt oa n yd o m a i n - r e l a t ek n o w l e d g e i nr e a lt e x tc a t e g o r i z a t i o nt a s k s ，f o rt h eh i g hc o s to fm a n u a l l yl a b e l i n gt h e t r a i n i n gs e t t h e r e r eo n l yaf e wl a b e l e dp o s i t i v es a m p l e sa n da l lt h el e f td o c u m e n t sa r e t r e a t e da su n l a b e l e do l l e s a n de v e nw o r s e ，t h es c a l eo ft h el a b e l e dd a t aa n dt h e u n l a b e l e dd a t ai sa l s oi m b a l a n e e d h o wt oe x t r a c te n o u g hc l a s s - r e l a t e di n f o r m a t i o n f r o mt h es m a l ln u m b e ro fl a b e l e dd o c u m e n t st oh e l pt h ec l a s s i f i c a t i o ni sa l s oab i g p r o b l e mt ob ef o c u so n t h i sa r t i c l ef i r s t l yd i ds o m eo v e r v i e wo nt h et r a d i t i o n a lc l a s s i f i c a t i o nm e t h o d s , a n dt h e nd i s c u s s e dt h es t a t e - o f - a r tc l a s s i f i c a t i o nm e t h o d si nt h es p e c i f i cd o m a i n a n d l a t e ran e wc l o s e n e s sb a s e dc l a s s i f i c a t i o nm e t h o df o rt h eu n b a l a n c e ds e m i s u p e r v i s e d t e x tc l a s s i f i c a t i o nt a s ki sp r o p o s e d i td i s e u s s o dt h ed e t a i l so fd e s i g n i n gas e m i s u p e r v i s e dt e x tc l a s s i f i c a t i o ns y s t e ma n da l s oi m p l e m e n t e dt h et e c h n i q u e sm e n t i o n e d a b o v ei nt h es y s t e m t h ew o r ko f t h i sa r t i c l ei sm a i n l yi nt h ef o l l o w i n gp a r t s ： 1 1ab r i e fs u r v e yo ft h ec u r r e n tr e s e a r c ha b o u tt e x tc a t e g o r i z a t i o nt a s ki s g i v e n , a n dt h es t a t e - o f - a r tc l a s s i f i c a t i o n sa l g o r i t h m si ns p e c i f i cd o m a i na r e g i v e n , t h el i m i t a t i o no f t h o s ea l g o r i t h m sa r ea l s od i s c u s s e d 2 、t h es t a t e o f - a r ts e m i s u p e r v i s e dc l a s s i f i c a t i o nm e t h o di sd i s c u s s e di nt h e a r t i c l e ，a n dt h ed i s a d v a n t a g ei sa l s oa n a l y z e d 3 ) ac l o s e n e s s b a s e da l g o r i t h mt os o l v es e m i - s u p e r v i s e dt e x tc l a s s i f i c a t i o ni n - 3 一 墨呈查堂堡主堂垡垒奎 垒! ! 塑竺 t h es p e c i f i cd o m a i ni sp r o p o s e d ，a n dt h ed e t a i l so f t h i sa l g o r i t h ma l eg i v e n 4 1a s e m i - s u p e r v i s e dt e x tc l a s s i f i c a t i o ns y s t e mi sd e s i g n e d t h ee x p e r i m e n t s o nt h et r e c 0 5g e n o m i c st a s kd a t aa l eg i v e na n dt h er e s u l t ss h o wt h a t t h ec l o s e n e s s - b a s e da i g o f i t h mc a nm g m yi m p r o v et h ee f f i c i e n c yo ft h e c l a s s i f i c a t i o nt a s kw i t h o u tu s i n ga n yd o m a i n - r e l a t e dk n o w l e d g e k e y w o r d s ：t e x tc a t e g o r i z a t i o n ，d o m a i n - s p e c i f i c ，f e a t u r es e l e c t i o n , s e m i s u p e r v i s e dl e a r n i n g 4 - 复旦大学硕士学位论文第一章绪论 1 1 研究背景与意义 第一章绪论 自从信息技术出现以来，随着技术的发展和信息量的爆炸式膨胀，各个特 定领域的科学发展都极为迅速，随之而来便是各个领域内的知识呈几何级数形 式地增长。人们迫切需要一种高效工具来组织这些特定领域内的信息资源，以 便更好的检索、过滤和管理它们。特定领域文本分类就是为属于某一特定领域 的文档分配一个或几个预先定义好的类别。虽然有许多已经很成熟的传统文本 分类技术，但在特定领域内的信息具有独特的特点，如许多在一般通用领域内 看来毫无意义的词汇或仅具有一般含义的词汇，在特定领域中却具有特殊意 义。因此特定领域文本分类任务需要特定领域知识的支持，这决定了用于一般 领域的文本分类系统很难直接应用于特定领域。因此，目前大多数的基于特定 领域的文本分类任务都依赖于领域相关的知识库对文本进行特征抽取，基于本 体库找出与类别相关的信息进行文本分类。然而，对于目前迅速发展的各个科 学领域，领域内的知识甚至整个学科的都是日新月异的，要建立一个完整的领 域相关的本体是一项耗时耗力的工程。同时即使对于已经存在有大量本体库的 领域的分类任务来说，如何选择恰当的与分类任务相关的本体也是一个比较难 的任务 2 6 】。因此，如何实现分类时不依赖于特定的与领域相关的知识实现高 效的特定领域的分类是目前研究的一个重点【2 7 】。 同时，对于一般现实情况下的文本分类任务而言，由于要将整个语料标注 出来是一项非常耗时的工作，所以造成了通常在训练集中只有少量标注出的正 例，而剩下为大量的未经任何标注的文档。因此对于这样的分类任务，由于标 注出的正例数目过少，依赖于标注出的这些正例完全不能够准确而完整的反映 出测试集的实际分布情况，这样造成普通的分类方法也不能简单的适用于这种 情况。因此，如何从少量的、而且分布极其不均衡的训练集合中找出尽可能完 整的关于类别的分布信息，提高这种半监督的文本分类任务的效果也是目前研 究的一大重点。 本文总结了近年来特定领域文本分类以及半监督文本分类的关键技术和系 统设计方法，设计和实现了一套用于特定领域内半监督文本分类问题的系统， 提出了种基于紧密度进行版监督文本分类的方法，并在t r e c 0 5 的基因任 务数据集上做了实验，和t r e c 0 5 基因任务的各个单项的结果相比，分类效 果都有不同程度的提高，显示了这种算法的优越性和适用性。 复旦大学硕士学位论文第一章绪论 1 2 特定领域的文本分类问题概述与趋势 文本分类是根据文档内容，为文档分配一个或几个预先定义好的类别，将 大量的文档归到一个或几个文档中去【6 】。它根据一个已经被标注的训练文档集 合，找到文档特征和文档类别之间的关系模型，然后利用这种学习得到的关系 模型对新的文档进行类别判断。可以更形式化地对文档分类过程进行描述。假 设有一组文档概念类c 和一组训练文档d 。文档概念类和文档库中的文档可能 满足某一概念层次关系h 。客观上，存在着一个目标概念t ，有： t ：d 斗c 这里，t 把一个文档实例映射为某一个类。对d 中的文档d ，r ( d ) 是已知 的。通过有指导地对训练文档集的学习，可以找到一个近似于t 的模型h ： 日：d _ c 对于一个新文档以，日( 反) 表示对砖的分类结果。一个分类系统的建立或 者说分类学习的目的就是寻找一个和t 最相近似的h 。即给定一个评估函数f ， 学习的目标应使t 和h 满足： m i n ( 乏二厂f ( 巧) 一h ( d ，) ) ) 自上世纪六十年代以来逐渐形成了一套常用的文本分类方法。通常在分类 之前，文档就已经被表示成由词组成的向量，向量中的每个分量代表某个词在 相应文档中的权重；在此基础上，有许多基于统计学的分类方法和机器学习技 术被用来做文本分类，如回归模型( r e g r e s s i o nm o d e l s ) 2 】，最近邻分类器( k - n e a r e s t n e i g h b o r ) 2 】，决策树( d e c i s i o nt r e e ) 3 】，贝叶斯分类器( b a y e s i a n c l a s s i f i e 0 ，支持向量机( s v m ，s u p p o r tv e c t o rm a c h i n e ) 4 】，规则学习算法 ( r u l e - b a s e dc l a s s i f i c a t i o n ) 5 】，b o o s t i n g 分类方法【1 7 】，神经网络( n e u r a l n e t w o r k s ) 1 6 1 等。 在大规模语料库中。由于用来表示文档的项的数目通常都很巨大，使得用 于表示文档的向量维度相应的非常庞大，从而导致这些向量构成的空间( v e c t o r s p a c e ) 非常稀疏，而且存在着大量相互没有任何相关的特征，这在某种程度上 大大降低了分类性能和效果。另外，在大多数情况下，训练集合只有一小部分 标注出的正例和大量未标记的文本，而未标注集合中仍存在着部分正例文档。 如果简单的把包含有正例文档的未标注集合视作是负例来训练分类器，对最后 的分类结果会有相当大的影响。然而，进行训练语料的标注不仅是相当耗时的 工作，而且也比较困难，因为不仅要保证标注结果的正确性，同时也需要使得 标注出的训练集能很好地反映语料的真实分布。因此，文本分类的主要难点是 特征选择降低特征空间维度、提取出相关特征，以提高分类效率并且降低计算 复旦大学硕士学位论文第一章绪论 复杂度以及如何找到合适的训练集合，以提高分类的准确性。 特定领域文本分类与一般文本分类之间的主要区别在于：在特定领域文本 分类任务中常常通过提取出与特定领域相关的特征项来表示相应的文档，如使 用特定领域用语、术语、专有名词等；而在普通的一般通用领域内的文本分类 任务通常把文档看作“b a go fw o r d s ，只是简单把单个词当作表示文本的特征用 以表示相应的文档，因此，在特定领域文本分类任务中，如果能够合理的幂用 领域相关的知识，在帮助提高学习、数据挖掘的效率以及分类器学习模型的质 量【9 】等方面有很好的效果。 因为特定领域的文本分类问题有着独有的特点，不能简单地用一般文本分 类方法来处理特定领域文本分类任务。对于特定领域文档所包含的特殊特征， 如特定领域用语、术语以及专有名词等，通常需要特定领域辞典的支持。如对 于生物医学领域的文档来说，基因名、蛋白质名、基因或蛋白质的别名、生物 化学领域专有名词，术语等特征都是领域相关特征。为了获得文档中的基因 名、蛋白质名，研究者们开发了许多专门用于标注基因和蛋白质名的工具。 m e s ht r e e 等生物化学领域的本体辞典被开发出来，为识别专有名词和术语等 特征提供语义支持。但随之而来的一个问题就是如果领域内有比较多的本体库 是，如何选择一个合适于特定问题的本体库，同时对于一些新兴的科学研究领 域，如果不存在比较完善的领域知识，如何才能实现高效的分类，这成为特定 领域内文本分类问题研究的一大难点。 1 3 评测平台 文本检索会议 n 匝c 】( t e x tr e t r i e v a lc o n f e r e n c e ，简称t r e c ) 是文本检索 领域最权威的国际会议之一，代表了当今世界文本检索领域的最高水平。 文本检索会议是由美国国家技术标准局( n i s n 和国防部高级研究计划局 ( a r d a ) 组织召开的一年一度的国际测评会议；旨在通过提供规范的大规模 语料( o b 级) 和对文本检索系统性能客观、公正的评测来促进技术的交流和发 展；促进政府部门、学术界及工业界间的交流与合作；加速技术的产业化，发 展对文本检索系统的评测技术。从1 9 9 2 年第一届会议开始，迄今已1 6 届，是 文本检索及评测领域最为权威的国际会议。由于该会议的重大影响力，吸引了 众多公司，高校及研究组织的参加。图1 1 及表1 1 列出了历届t r e c 参加单位 数，相关任务及部分参加单位列表。 复旦大学硕士学位论文第一章绪论 i f j ； 。r 霪 l矗圜l ll 圉 罔j毳 一l ll l二! 一l _ = l捶 图1 1 历届t r e c 设立的任务和参加的单位数 公司大学亚洲参加单位 矾飞m n s i n g a p o r eu ( k r d l ) b n n c m u k o r e a u m i c r o s o f i c a m b r i d g eu a j o u u s u nc o m e l lu p o h a n g u a p p l em a r y l a n du y o n s e iu f u j i t s u m a s s a c h u s e t t su t s i n g h u au ( t a i w a n ) n e c n e wm e x i c os t a t eu t a i w a n u x e r o xc a l i f o r n i ab e r k e l e yu h o n g k o n gc h i n e s eu i b mm o n f f e a lu m i c r o s o f tr e s e a r c ha s i a c l r i t e c hj o h n sh o p k i n su -f u d a n u n t t r u t g e r su c a s 0 r a c l ew a t e r l o ou t s i n g h u au r i c o h p e n n s y l v a n i au s h a n g h a ij i a o t o n gu l e x i c l o n ed u b l i nc i t yu t o k y o u 表1 1 ：参加过n 也c 的部分单位 从表中我们可以看到参赛单位数量逐年增多，而且参赛项目常常会根据目 前的研究和应用的现状推陈出新，引领着文本处理领域的研究方向。特别值得 一提的是，复旦大学，微软亚洲研究院，清华大学和中科院计算所等是第一批 来自中国大陆的参加单位。 t r e c 0 5 的g e n o m i e s 项目是文本检索会议最早的关于特定领域的文本检索 任务。自2 0 0 4 年开始，该项目设立了c a t e g o r i z a t i o n 子任务，即基因领域文本 鲫 0 复旦大学硕士学位论文 第一章绪论 分类任务，是目前特定领域文本分类领域最权威的评测平台。 2 0 0 5 年的t r e cg e n o m i c sc a t e g o r i z a t i o n 任务【9 】是由2 0 0 4 年文本检索会议 基因领域文本分类任务的t r i a g e 子任务【1 0 】( t r e c2 0 0 4g e n o m i c st r a c k c a t e g o r i z a t i o nt a s kt r i a g es u b t a s k ) 衍生而来，包含4 个子任务，各个子任务的 目标是在语料库中分别找出属于a l l e l e so f m u t a n tp h e n o t y p e s ( a 类) 、 e m b r y o l o g i cg e n ee x p r e s s i o n ( e 类) 、g oa n n o t a t i o n ( g 类) 、t u m o rb i o l o g y ( t 类) 这4 种类型中的一种类型的文档。 t r e cg e n o m i e s 使用的语料库是由h i g h w i r ep r e s s 提供的生物化学领域的 三个杂志2 0 0 2 年和2 0 0 3 年这两年内总共1 1 8 8 0 篇全文本文章组成的；j o u r n a l o f b i o l o g i c a lc h e m i s t r y0 8 c ) ，j o u r n a lo f c e l lb i o l o g y ( j c b ) ，以及p r o c e e d i n g s o ft h en a t i o n a la e a d e m yo fs c i e n c e ( p n a s ) 。这些全文本文档的格式为基于 h i g h w i r e 文档类型定义( d t d ) 的s g m l 格式。该任务的训练集以2 0 0 2 年全 年的文章组成的集合，而2 0 0 3 年的文章集合则被作为测试集。 1 4 本文的工作及组织结构 本文总结了近年来特定领域文本分类的关键技术，同时提出了一种基于本 体知识库的方式来进行特征提取的方法，另外对于t r e cg e n o m i e s 任务的特性 提出了一种基于紧密度衡量的用于半监督文本分类的算法。同时该算法在 t r e cg e n o m i c s 数据集上的实验表明，该算法能取得比较好的性能。 本文共五章，各章节的内容具体安排如下； 第一章是绪论，介绍了本文的研究背景与意义、特定领域文本分类的基本 状况，以及t r e cg e n o m i e s 项目c a t e g o r i z a t i o n 任务的概况。 第二章介绍了文本分类的基础知识，并介绍了常用的预处理、分类方法 等，以及特定领域文本分类的现状，对参加t r e c 评测的各种特定领域文本分 类系统作了简要介绍，同时对于在特定领域内的分类问题中的两大问题做了初 步的探讨。 第三章描述了半监督文本分类任务的主要特点以及目前的研究现状，同时 提出了一种新的基于紧密度衡量的算法，并给出了基于紧密度衡量的分类系统 的框架。 第四章描述了详细介绍了特定领域内半监督文本分类系统的各组成部分及 其原理、方法及实验结果，同时给出了t r e c 的评测标准以及该系统在 t r e c 7 0 5 基因分类任务上的结果，并分析了该算法与一般传统的特定领域的 复旦大学硕士学位论文 第一章绪论 算法相比的优势。 第五章总结了特定领域内半监督文本分类的关键技术，并对未来的研究前 景做了展望。 复旦大学硕士学位论文第二章特定领域内的文本分类 第二章特定领域内的文本分类 特定领域内的文本分类固然尤其独有的特点和解决方法，但是作为文本分 类的某一种应用，解决该类问题的出发点和背景和般的通用领域的文本分类 任务类似。我们需要找到一种合适的模型来表示文本，同时在这样的模型空间 内找到能够最好地代表文本的特征的词项，最后用适合于该类问题的分类器来 对测试文档进行自动的文本分类。因此，在本章中我们将对于在一般领域内通 用的文本分类方法做一个简要的概述，并总结出各方法的特点和适用范围。 2 1 文档的表示模型 文本分类是根据文档内容，为文档分配一个或几个预先定义好的类别。自 上世纪六十年代以来逐渐形成了一套常用的文本分类方法【l 】，其中包括许多基 于统计学的分类方法和机器学习技术，如r e g r e s s i o nm o d e l s 2 】，最近邻分类器 【2 】，决策树【3 】，b a y e s i a n 分类器【3 】3 ，支持向量机( s v m ，s u p p o r tv e c t o r m a c h i n e ) 【4 】，规则学习算法 5 】，相关反馈【6 】，b o o s t i n g 算法【1 7 】，神经网络 1 4 等。 2 1 1 布尔模型简介 布尔模型【8 】可以看作是向量模型的一种特例，根据特征是否在文档中出 现，特征的权值只能取1 或0 。许多时候，使用二值特征的分类效果结果并不 比考虑特征频率的差。布尔模型的缺点是它分类时是基于二进制的规则，不能 很好的真实的反应文本的语法特征，因此应用范围比较有限。 2 1 2 向量空间模型简介 向量空问模型是由s a l t o n 7 等人于上世纪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 ft e x t ) 系统。该系统 及其相关的技术，包括项的选择、加权策略，以及采用相关反馈进行查词优化 等技术，在文本过滤、自动索引、信息检索等许多领域得到了广泛的应用。 在向量空间模型中，文档被表示成由词组成的向量，向量中的每个分量代 表某个词在这篇文档中的权重，可以用词在文档中出现的次数来简单的表示其 复旦大学硕士学位论文 第二章特定领域内的文本分类 权重。由于词的数量通常非常庞大，因此向量空间的维数也相应的非常庞大， 然而词通常并不是在每篇文章中都出现，这使得这些向量组成的矩阵非常稀 疏。这产生了文本分类的一个主要难点，即高维的特征空间。为文档中的词赋 权重的方法一般基于以下两个源于经验的原则： 夺如果某个词在一篇文档中出现的次数越多，则这个词与文档的主题越 相关。 如果某个词在越多的文档中出现过，则这个词越难以区分文档主题。 常用的取权重的方法有以下6 种。设以表示词f 在文档k 中出现的频率 ( 词频) ，n 表示所有文档数量，m 表示所有词的数量，彤表示包含词i 的文档 数( 文档频率) ，a 。表示词i 在文档k 中的权重。 2 2 传统的特征选择方法 特征抽取是指从全部的特征项中抽取出部分具有代表性的特征项，它可以 降低特征空间的维数，从而达到降低计算复杂度、增强可解释性、提高分类准 确率的目的。对文本进行特征抽取是文本处理的重要基础，为后续的文本分 类、文本检索、文本过滤等文本处理奠定了有力的基础。 一个有价值的索引必须具有以下两个特征： 1 )必须与文档内容有关，以便在需要时进行索引项的检索( 称为完全 性功能) 2 )必须能将该文档与其他文档相区分( 称为准确性功能) 。 用来表示文档内容的特征项可以使文本中的各种原单位，有单词、短语甚 至是句子等更高层次的单位。特征项也可以是相应单词或短语的语义概念类。 因此特征项的选择只能由处理速度、精度、存储空间等方面的具体要求来决 定。 选出来的特征越具有代表性，语言层次越高，特征项所包含的信息也就越 丰富，但同时所带来的分析代价就越大，而且受分析精度( 如句法分析的正确 率) 的影响也就越大。由于词汇是文本最基本的表示项，在文本中出现的频率 较高，呈现一定的统计规律，再考虑到处理大规模正式文本所面临的困难，选 择词或者词组作为特征项是比较合适的，常常被应用于文本检索与分类等领 域。 在基于向量空间模型的文本处理中，特征抽取的方法通常是：首先对训练 文档上进行去禁用词和词干抽取处理工作，然后计算剩余单词的某种特征值， 根据指标值的高低决定是否保留相应的字或词，从而实现特征选择和抽取 复旦大学硕士学位论文 第二章特定领域内的文本分类 3 2 1 。这样做的目的主要有两个，第一，为了提高程序的效率，提高运行速 度；第二，去除那些区分能力不强的词汇，筛选出最能反映主题的特征项集 合。 存在多种筛选特征项的方法，如根据词和类别的互信息量判断，根据词熵 判断，根据k l 距离判断等。 a ) 信息增量( i n f o r m a t i o ng a i n ) 信息增量表示文档中包含某一特征值时文档类的平均信息量。它定义为某 一特征在文档中出现前后的信息熵之差。假定c 为文档类变量，c 为文档类的 集合，d 为文档，f 为特征( 以下各节同此) 。对于特征f ，其信息增量记为 i g ( o ，则有： l g ( f ) = 日( c ) 一h ( c i 力 一p ( c ) l o g ( p ( c ) ) + p ( 门p o i 力l o 甄p ( c i ，) + p ( 力p ( c i 于) l o 甙p l 于) = 驴崦c 毒籍m 加g c 看籍m 晓。 因此，在只考虑单个类的时候，有： i g ( 切毗加s ( 磊m 心触( 看潞) ( ： b ) 互信息( m u t u a li n f o r m a t i o n ) 在统计学中，互信息用于表征两个变量间的相关性。对于特征，其互信息 记为蚴，则有： 嘶肛l o g ( 意舄 ( 2 s ) 显然，当f 独立于c 时，m i ( c ，f ) 为o 。在应用时一般取平均值： m i ( 力= p ( c ) m i ( c ，力 ( 2 4 ) c ) 矿统计 同样地，f 统计也是用于表征两个变量闯的相关性，但它比互信息更强， 因为它同时考虑了特征存在与不存在时的情况。对于特征其z 2 统计值为： 托力= 盟篙蔫铲 晓s ， 当c 与厂相互独立时，f ( c ，力为0 。和互信息类似，取平均值： 复巨大学硕士学位论文 第二章特定领域内的文本分类 盔( f ) - - p ( c ) x 2 ( c ，力 f e c d ) 交叉熵( c r o s se n t r o p y ) ( 2 6 ) 交叉熵和信思增量相似，不同之处在于信思增量中刷时考虑剑待，仕在又 本中发生与不发生时的两种情况，而交叉熵只考虑特征在文本中发生一种情 况。假定c 为类变量，c 为类的集合，对于特征 其交叉熵记为c e ( f ) ，则 有： c e ( f ) = 驴批g ( 蔷黔) ( 2 7 ) c e ( 咖弛，f ) l o g ( 高潞) ( 2 8 ) e ) 证据权值( w e i g h to fe v i d e n c e ) 证据权值反映的是类概率与在给定某一特征值下的类概率的差。证据权值 用如下公式表示： w e ( f ) = 萎即坝俐o g ( 絮箬 ( 2 9 ) 这里，行是训练文档实例数目，且有 o d d s ( x 1 1 = 户( 置) = 0 p ( z ) = 1 ( 2 1 0 ) p ( 置) 0 ，( x ，) 1 同样地，在单个类的情况下，有： w e ( 叫妒洲l o g ( 絮警 ( 2 1 1 ) f ) f i s h e r 判别式 f i s h e r 判别式是一种基于统计的方法，表示某一特征在类间分布和类内分 布之比： 砒，( d ：蓦生堕2 丝：2 ： ( 2 - 1 2 ) 。古( ( x ( d ，厂) 一( c ，d ) 2 ) 这里， ( 岛力= 吉妇x ( d , t ) ， ( 2 1 3 ) 坩一埘删一肼删一抛 坩一肼删一一 复旦大学硕士学位论文 第二章特定领域内的文本分类 x ( d ，厂) = n ( d ，f ) n ( d ) ( 2 1 4 ) 上面，疗 力和胛( 四分别表示特征在文档d 中的频数和文档d 中总的特征频 数。 2 3 文本分类算法 文本分类任务是给文档分配一个或多个预先定义好的类别 6 】。近年来有 许多基于概率统计的分类方法被用于文本分类任务。文本分类可以被分为两种 情况，两类分类和多类分类。两类分类即文档被分为相关和不相关两类，多类 分类是指文档被分为多个类。对于多类分类的一般解决办法，是将多类问题拆 分成多个不相干的两类分类问题。这种方法的缺点是忽略了类与类之间的联 系。下面介绍一些在文本分类任务中常用的分类算法。 其中，设d = 缸，九 是待分类的文档向量，q ，c k 是所有可能的类 别。 2 3 1 类中心( r o c c h i o ) 分类算法 类中心分类算法【6 ，3 3 】是为每个类0 构造一个原型向量，通过计算文档d 与 各个原型向量之间的距离，将文档分到距离最近的类里面。距离的计算方法一 般是通过向量的点乘或者一些相似度计算公式得出。类0 的原型向量是训练文 档集当中所有属于类0 的文档向量的平均。这种分类方法的速度比较快。 2 3 2n a i v eb a y e s 分类算法 n a i v eb a y e s 分类方法 1 1 1 ( 以下简称n b 法) 是一种简单而又非常有效的分 类方法。n b 法的一个前提假设是：在给定的文档类语境下，文档属性是相互独 立的。假设一为一任意文档，它属于文档类c 2 他，岛，靠) 中的某一类0 。根 据n b 分类法有： 鹏= 掣， ( 2 1 5 ) p ( 珥) = p ( c j ) p ( 巧ic j ) ( 2 1 6 ) 对文档d i 进行分类，就是按公式2 1 计算所有文档类在给定凼情况下的概 复旦大学硕士学位论文第二章特定领域内的文本分类 率，概率值最大的那个类就是西所在的类，即： t d l c ，矿p ( c ，i z ) = 吧野 p ( 0l 或) ( 2 1 7 ) 由公式2 1 5 公式2 1 7 可知，对于给定分类背景和测试文档，用n b 法分 类的关键就是计算p ( c j ) 和p c d , ) 。计算p ( c j ) 和p ( zh ) 的过程就是建立分 类模型( 或者说学习) 的过程。 根据p ( ti 勺) 计算方式的不同，可以将n a i v eb a y e s 方法分为最大似然模型 ( m a x i m u ml i k e l i h o o dm o d e l ) 、多项式模型( m u l t i n o m i a lm o d e l ) 、泊松模型 ( p o i s o nm o d e l ) 等 e l m 0 3 。文献 p s 0 3 d p 将n a i v eb a y e s 方法和n g r a m 有机 地结合起来，放松了b a y e s 模型中每个文档特征相互独立的假设，取得了不错 的分类效果。 2 3 3k 近邻( k n n ，k - n e a r e s tn e i g h b o r ) 分类算法 k n n 方法 1 2 】即k - n e a r e s tn e i g h b o r 分类方法，这是一种稳定而有效的文本 分类方法。采用k n n 方法进行文档分类的过程如下：对于某一给定的测试文档 d ，在训练文档集中，通过相似度找到与之最相似的k 个训练文档。在此基础 上，给每一个文档类打分，分值为k 个训练文档中属于该类的文档与测试文档 之间的相似度之和。也就是说，如果在这k 个文档中，有多个文档同属于一个 类，则该类的分值为这些文档与溺试文档之问的相似度之和。对这k 个文档所 属类的分值统计完毕后，即按分值进行排序。还应当选定一个阂值，只有分值 超过阈值的类才予以考虑。测试文档属于超过阈值的所有类。形式化表示为： s c o r e ( d ，q ) = 乏：s i m ( d , d j 沙( 订 q ) 一屯 ( 2 1 8 ) j ：京n 其中， f 1d ，c ， y ( 嘭, c j ) 2 1 0z 芒i q 匆为阈值，s i m ( d , d ，) 为文档d 和嘭的相似度，s c o r e ( d ，c ；) 为测试文档矗属于q 类的分值。 对于某一特定类来说，q 是一个有待优化的值。一般，q 可以通过一个验 证文档集来进行调整。验证文档集是训练文档集的一部分。根据公式2 4 的结 果，可以确定测试文档的类别。很显然，对于每一个测试文档，必须求解它和 训练文档库中所有文档的相似度。因此，心州方法的时间复杂度为o ( i d i 啊) 。 其中，i u i 和一分别为训练文档总数和测试文档总数。 2 3 4 支持向量机算法( s v m ，s u p p o r t v e c t o rm a c h i n e ) 复旦大学硕士学位论文第二章特定领域内的文本分类 支持向量机( s u p p o r tv e c t o rm a c h i n e 或s v m ) 【4 】是在统计学习理论 ( s t a t i s t i c a ll e a r n i n gt h e o r y 或s l t ) 的基础上发展而来的一种机器学习方法， 它基于结构风险最小化原理，将原始数据集合压缩到支持向量集合( 通常为前 者的3 。5 ) ，学习得到分类决策函数。其基本思想是构造一个超平面作为决 策平面，使正负模式之间的空白最大。支持向量机在解决小样本、非线性及高 维模式识别问题中表现出了许多特有的优势，并能够推广应用到函数拟合等其 它机器学习问题中。s v m 已初步表现出很多优于已有方