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

复旦大学硕士学位论文摘要 摘要 随着信息技术的迅速发展，各种学科的信息也在随之迅速膨胀，人们迫切需 要这些特定领域的信息检索与管理工具，特定领域文本分类成为当前研究热点。 目前，特定领域文本分类主要是在传统文本分类的基础上，利用已有的特定领域 知识库扩展文档特征。如何提取领域相关特征是其主要难点之一。 本文综述了现有特定领域文本分类系统，详细介绍了特定领域文本分类系统 的设计思想与实现细节，设计并实现了一套特定领域文本分类系统，针对如何提 取领域相关特征的问题，提出了一种基于领域相关术语提取的特征选择方法，改 进了术语提取方法，并且分析了各系统组成部分。本文的工作主要包括： 本文综述了现有特定领域文本分类系统，提出了特定领域文本分类系统的体 系结构。 本文提出了一种基于领域相关术语提取的特征选择方法，该方法具有以下优 点：( 1 ) 提取出来的特征与领域密切相关，提高了分类效果；( 2 ) 大大降低 了特征空间维数，提高了系统运行性能；( 3 ) 由于该方法使用基于语料库对 比的术语提取方法，不依赖任何特定领域知识库，从而使系统具有很强的通 用性，能轻松应用于各个领域。 本文根据词语搭配分布，改进了传统的基于语料库对比的术语提取方法，使 术语提取方法兼顾了对语言结构的分析。 本文详细分析了预处理、特征选择、二级分类器等系统组成部分对分类效果 及系统性能的影响。 本文设计并实现了一套具有很强通用性的特定领域文本分类系统，该系统参 加了t r e c2 0 0 5g e n o m i c s 项目c a t e g o r i z a t i o n 任务的评测，在四个子任务中 取得了两个第一的好成绩。 关键词：文本分类，特定领域，特征选择，降维 复旦大学硕士学位论文 摘要 a b s t r a c t w h i l et h er a p i dg r o w t ho ft h ei n f o r m a t i o nt e c h n o l o g y , m o r ea n dm o r e i n f o r m a t i o no fe v e r yk i n do fs u b j e c t si sa v a i l a b l e ，p e o p l ea r ec r y i n gf o ri n f o r m a t i o n r e t r i e v a lt o o l st om a n a g et h e s ed o m a i n s p e c i f i cr e s o u r c e s ，a n dt h e s em a d et h e d o m a i n s p e c i f i c t e x tc a t e g o r i z a t i o nt ob eo n eo ft h em o s ta c t i v er e s e a r c ha r e a s p r e s e n t l y , t h ed o m a i n - s p e c i f i ct e x tc a t e g o r i z a t i o ns y s t e m sa r em o s t l yb u i l tb a s e do n t h ec o n v e n t i o n a lt e x tc a t e g o r i z a t i o ns y s t e m ，w i t he x p a n d e df e a t u r es p a c eb yt h eh e l p o fd o m a i n s p e c i f i ck n o w l e d g ed a t a b a s e s o n eo fi t sm a j o rp r o b l e m si sh o wt oe x t r a c t d o m a i n s p e c i f i cf e a t u r e s i nt h i st h e s i s ，t h es u r v e yo fc u r r e n td o m a i n s p e c i f i ct e x tc a t e g o r i z a t i o ns y s t e m s a n dt h ed e t a i l so ft h et e x tc a t e g o r i z a t i o ns y s t e ma r ep r e s e n t e d f o rt h ep r o b l e mo f e x t r a c t i n gd o m a i n - s p e c i f i cf e a t u r e s ，a f e a t u r es e l e c t i o nm e t h o db a s e do n d o m a i n - s p e c i f i ct e r me x t r a c t i o nt o g e t h e rw i t ha ni m p r o v e dv i s i o no fd o m a i n s p e c i f i c t e r me x t r a c t i o nm e t h o da r ep r o p o s e d t h ea n a l y s i so fe a c hp a r t so ft h es y s t e mi s p r e s e n ti nd e t a i l t h ew o r ko ft h i st h e s i sm a i n l yi n c l u d e s ： t h es u r v e yo fc u r r e n td o m a i n - s p e c i f i ct e x tc a t e g o r i z a t i o ns y s t e m si sp r e s e n t e d a n dt h ea r c h i t e c t u r eo fd o m a i n s p e c i f i ct e x tc a t e g o r i z a t i o ns y s t e mi sp r o p o s e d af e a t u r es e l e c t i o nm e t h o db a s e do nd o m a i n s p e c i f i ct e r me x t r a c t i o ni sp r o p o s e d t h i sm e t h o dh a v et h e s ev i r t u e s ：f 1 ) t h es e l e c t e df e a t u r e sa r ec o r r e l a t e dw i t ht h e d o m a i n ，w h i c hc a ni m p r o v et h ee f f e c to fc a t e g o r i z a t i o n ，( 2 ) t h ed i m e n s i o ni s r e d u c e dg r e a t l y , w h i c hc a ni m p r o v et h es y s t e mp e r f o r m a n c e ，( 3 ) a st h em e t h o do f d o m a i n - s p e c i f i ct e r me x t r a c t i o ni sb a s e do nc o r p u sc o m p a r i s o n ，w h i c hd o e s n t r e l yo na n yd o m a i n s p e c i f i ck n o w l e d g ed a t a b a s e ，t h es y s t e mc a nb ee a s i l ya p p l i e d t oa n yd o m a i n t h ec o n v e n t i o n a lm e t h o do fd o m a i n s p e c i f i ct e r me x t r a c t i o ni si m p r o v e db a s e d o nt h ed i s t r i b u t i o no ft e r m s c o m b i n a t i o n t h ea n a l y s i so fe a c h p a r t s i m p a c t t ot h es y s t e mp e r f o r m a n c ea n dt h e c l a s s i f i c a t i o ne f f e c ti sp r e s e n ti nd e t a i l ，s u c ha st h ep r e p r o c e s s i n g ，f e a t u r e s e l e c t i o n ，a n dt w o - s t a g ec l a s s i f i e r t h es y s t e mw ed e v e l o p e df o rd o m a i n s p e c i f i ct e x tc l a s s i f i c a t i o nh a sg o t t e nt h e h i 曲e s ts c o r ea m o n gr u n sf r o m1 7g r o u p si nt h ee v a l u a t i o no ft r e c2 0 0 5 g e n o m i c st r a c kc a t e g o r i z a t i o nt a s k 4 复旦大学硕士学位论文 摘要 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 ， d i m e n s i o nr e d u c t i o n 5 复旦大学硕士学位论文 第一章绪论 1 1 研究背景与意义 第一章绪论 随着信息技术的发展和信息量的迅速膨胀，各个特定领域的信息量也在随之 增长，如法律、医学、计算机科学、生物学、经济学等领域。人们迫切需要一种 高效工具来组织这些特定领域信息资源，以便更好的检索、过滤和管理它们。特 定领域文本分类是特定领域信息管理的核心组成部分，是为属于某一特定领域的 文档分配一个或几个预先定义好的类别。虽然有许多已经很成熟的传统文本分类 技术，但是特定领域信息所具有独特特点，比如有许多在一般人看来毫无意义的 词汇或仅具有一般含义的词汇，在特定领域中却具有特殊意义。因此特定领域文 本分类任务需要特定领域知识的支持，这决定了用于一般领域的文本分类系统很 难直接应用于特定领域。然而，若聘请具备特定领域专业知识的工作人员手工的 分类，将会非常耗时和昂贵，严重限制这项工作的效率。因此，特定领域自动文 本分类技术成为了研究热点。 作为特定领域信息管理的核心组成部分，特定领域文本分类系统具有非常广 泛的应用领域，如法律、医学、计算机科学、生物学、经济学等领域的文本过滤、 分类、检索等。著名期刊 b y t e 曾有文章预测：这类信息检索与数据挖掘软件 将成为继文字处理软件、表处理软件之后未来最重要的五种软件之一；有着十分 广阔的应用领域和市场价值。 本文总结了近年来特定领域文本分类的关键技术和系统设计方法，设计和实 现了一套特定领域文本分类系统，提出了一种基于特定领域术语提取的特征选择 方法。 1 2 文本分类概述 文本分类是根据文档内容，为文档分配一个或几个预先定义好的类别，将大 量的文档归到一个或几个文档中去 1 。自上世纪六十年代以来逐渐形成了一套 常用的文本分类方法。在做分类之前，文档通常被表示成由词组成的向量，向量 中的每个分量代表某个词在这篇文档中的权重；在此基础上，有许多基于统计学 的分类方法和机器学习技术被用来做文本分类，如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 ，支持向量机( s v m ，s u p p o r t 墨呈奎堂堡主堂垡迨奎 笙二童! 鱼 v e c t o rm a c h i n e ) 4 ，规则学习算法 5 ，相关反馈 6 ，v o t e d 分类器 7 ，神 经网络 8 等。 在大规模语料库中，由于词的数量非常巨大，使得用于表示文档的向量维度 相应的非常庞大，从而导致这些向量组成的向量空间非常稀疏，而且存在着大量 不相关特征。这大大降低了分类性能和效果。因此，文本分类的主要难点是特征 选择，即如何从文档中去除不具信息的词，降低特征空间维度、提取出相关特征， 以提高分类效率并且降低计算复杂度。 近年来研究者们常用的一些特征选择方法 2 ：文档频率阈值，i n f o r m a t i o n g a i n ，c h i s q u a r e ，m u t u a li n f o r m a t i o n ，t e r ms t r e n g t h 。 1 3 特定领域文本分类的新趋势 在特定领域文本分类任务中，领域知识能够帮助提高学习、数据挖掘的效率 以及分类器学习模型的质量 9 。因此，在特定领域文本分类任务中，对领域知 识的运用是非常重要的。特定领域文本分类与一般文本分类之间的主要区别在 于： 特定领域文本分类任务的语料库由特定领域文档构成，而一般文本分类任务 的语料库由一般领域或多个领域文档构成。 在特定领域文本分类任务中需要提取与特定领域相关的文档特征，如特定领 域用语、术语、专有名词等；一般文本分类任务通常把文档看作“b a go fw o r d s ”， 只需要简单的用单个词作为特征即可。 这些区别决定了不能简单地用一般文本分类方法来处理特定领域文本分类 任务。对于特定领域文档所包含的特殊特征，如特定领域用语、术语、专有名词 等，通常需要特定领域辞典的支持。如对于生物医学领域的文档来说，基因名、 蛋白质名、基因或蛋白质的别名、生物化学领域专有名词、术语等特征都是领域 相关特征。为了获得文档中的基因名、蛋白质名，研究者们开发了许多专门用于 标注基因和蛋白质名的工具。m e s h f r e e 等生物化学领域的本体辞典被开发出来， 为识别专有名词和术语等特征提供语义支持。 1 4t r e 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 ) 是文本检索领域 复巨大学硕士学位论文 第一章绪论 最权威的国际会议之一，代表了当今世界文本检索领域的最高水平。文本检索会 议是由美国国家技术标准局和国防部高级研究计划局组织召开的一年一度的国 际测评会议；旨在通过提供规范的大规模语料( g b 级) 和对文本检索系统性能客 观、公正的评测来促进技术的交流和发展；促进政府部门、学术界及工业界间的 交流与合作：加速技术的产业化，发展对文本检索系统的评测技术。从1 9 9 2 年 第一届会议开始，迄今已1 4 届，是文本检索及评测领域最为权威的国际会议。 由于该会议的重大影响力，吸引了众多公司，高校及研究组织的参加。 复旦大学，微软亚洲研究院，清华大学和中科院计算所等是第一批来自中国 大陆的参加单位。 1 5t r e c2 0 0 5g e n o m i c s 项目c a t e g o r i z a t i o n 任务 g e n o m i c s 项目是文本检索会议最早的特定领域文本检索任务。自2 0 0 4 年开 始，该项目设立了c a t e g o r i z a t i o n 子任务，既基因领域文本分类任务，是目前 特定领域文本分类领域最权威的评测平台。 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 任务 1 0 是由2 0 0 4 年文本检索 会议基因领域文本分类任务的t r i a g e 子任务 1 1 ( 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 fm 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 种类型中的一种类型的文档。使用的语料库是由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 lo fb i o l o g i c a lc h e m i s t r y ( j b c ) ，j o u r n a lo fc e l l b i o l o g y ( j c b ) ，以及p r o c e e d i n g so ft h en a t i o n a la c 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 年的文章作为测试集。 2 0 0 4 年刚设立该项目时有1 4 家单位参加评测，2 0 0 5 年则有1 7 家单位参加 评测。其中不乏i b m 研究院、马里兰大学、u i u c 、清华大学等著名企业和高校。 笔者代表复旦大学参加了t r e c2 0 0 5g e n o m i c s 项目c a t e g o r i z a t i o n 任务，取得 了e 类第一、g 类第一、t 类第三、a 类第五的好成绩 1 2 。 复旦大学硕士学位论文 第一章绪论 1 6 本文的工作及组织结构 本文总结了近年来特定领域文本分类的关键技术和系统设计方法，设计和实 现了一套特定领域文本分类系统，提出了一种基于特定领域术语提取的特征选择 方法。并以该系统参加了t r e c2 0 0 5g e n o m i c s 项目c a t e g o r i z a t i o n 任务，获得 4 个子任务中的2 个第一。 本文共五章，各章节的内容具体安排如下： 第一章是绪论，介绍了本文的研究背景与意义、特定领域文本分类的基本状 况，以及t r e c2 0 0 5g e n o m i c s 项目c a t e g o r i z a t i o n 任务。 第二章介绍了文本分类的基础知识，并介绍了常用的预处理、特征选择、分 类方法等，以及特定领域文本分类的现状，对参加t r e c 评测的各种特定领域文 本分类系统作了简要介绍。 第三章描述了特定领域文本分类系统的设计及细节，在总结了特定领域文本 分类基本框架的基础上，设计了不依赖于特定领域知识、具有通用性的特定领域 文本分类系统框架，并详细介绍了系统各组成部分的原理、方法及实验结果。 第四章介绍了该系统的实现，以及其在t r e c2 0 0 5g e n o m i c s 项目 c a t e g o r i z a t i o n 任务中的评测结果。 第五章总结了特定领域文本分类的关键技术，并对未来的研究前景做了展 望。 复旦大学硕士学位论文 第二章相关工作 第二章文本分类 2 1 文本分类概述 文本分类是根据文档内容，为文档分配一个或几个预先定义好的类别。自上 世纪六十年代以来逐渐形成了一套常用的文本分类方法，其中包括许多基于统计 学的分类方法和机器学习技术，如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 ，支持向量机( 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 ，v o t e d 分类器 7 ，神经网络 8 等。 2 2 预处理 文本分类的第一步是转换文档格式，将由字符串组成的文档转化为适合分类 器和机器学习算法的表示形式，这一步通常被称为预处理。预处理通常包括以下 一些步骤： 夺去除h t m l 或其他标签 夺去除禁用词 夺取词干 禁用词是在文档中频繁出现的并不表示任何信息的词，如代名词、前置词、 连接词等。取词干是指去除后缀，把词还变成一般形式，把具有相同意义的词归 为一个词，例如t a l k 、t a l k e r 、t a l k e d 、t a l k i n g 等词都归于t a l k 。p o r t e r s t e m m e r 1 3 是最常用的取词干工具。 2 3 文档表示 向量空间模型 1 4 ( v s m ，v e c t o rs p a c em o d e l ) 是最普遍的文档表示形式。 在向量空间模型中，文档被表示成由词组成的向量，向量中的每个分量代表某个 词在这篇文档中的权重，可以用词在文档中出现的次数来简单的表示其权重。由 于词的数量通常非常庞大，因此向量空间的维数也相应的非常庞大，然而词通常 并不是在每篇文章中都出现，这使得这些向量组成的矩阵非常稀疏。这产生了文 本分类的一个主要难点，即高维的特征空间。为文档中的词赋权重的方法一般基 于以下两个源于经验的原则： 复旦大学硕士学位论文第二章相关工作 夺如果某个词在一篇文档中出现的次数越多，则这个词与文档的主题越相 关。 夺如果某个词在越多的文档中出现过，则这个词越难以区分文档主题。 常用的取权重的方法有以下6 种。设如表示词j 在文档膏中出现的频率( 词 频) ，n 表示所有文档数量，m 表示所有词的数量，娥表示包含词j 的文档数( 文 档频率) ，n 。表示词j 在文档丘中的权重。 2 3 1 布尔权重法 布尔权重法是最简单的取权重方法，如公式2 1 所示，如果某个词在文档中 出现，其权重则为1 ，否则为0 。 f 1 。i 0 | k 0 其他 2 3 2 词频权重法 ( 2 1 ) 词频权重法如公式2 2 所示，是简单的用词在文档中出现的频率作为权重。 a m = 以( 2 2 ) 2 3 3t f * id f 权重法 t f * i d f 权重法( 公式2 3 ) 是一种常用的权重方法 1 4 ，这种权重法在词频权 重法的基础上引入了对文档频率的考虑，文档频率越大的词的权重应该越低。 驴纠。g 。， 复旦大学硕士学位论文 第二章相关t 作 2 3 4t f c 权重法 t f c 权重法 1 5 是在t f * i d f 权重法的基础上用文档长度做正规化，如公式 2 4 所示。 以跛= 2 3 5i t c 权重法 ( 2 4 ) l t c 权熏法 1 6 与t f c 权重法的区别在于使用词频的对数取代词频，以减少 词频差异过大的影响，其详细形式如公式2 5 所示。 口瞻= 2 3 6 熵权重法 ( 2 5 ) 的权重。这是这些权重方法中最繁琐也是效果最好的方法。如公式2 6 所示，公 式中的z 表示词i 的熵，如果词在每篇文章中都出现，z 的值则为一1 ；如果词 仅出现在一篇文章中，z 的值则为0 。 以请= l o g 心氏+ 1 ) 【1 + z ) z - 南躺崦劁 组e ， 复旦大学硕士学位论文第二章相关工作 2 。4 降维与特征选择 基于概率统计学的文本分类的关键问题之一就是特征空间的维数太高。在文 档集当中找到的每个词都对应着特种空间的一个维度，文档集当中通常有几十万 甚至几百万个词。标准的分类技术无法处理如此巨大的特征集，因此需要减小特 征空间，这在模式识别中被称为降维。大部分降维方法可以归结为两类：特征选 择和r e p a r a m e t e r i s a t i o n 。这里主要介绍特征选择方法。 特征选择是从文档中去除不具信息的词，以提高分类效率并且降低计算复杂 度。y a n g 2 介绍了一些常用的特征选择方法：文档频率阈值，i n f o r m a t i o ng a i n ， c h i s q u a r e ，m u t u a li n f o r m a t i o n ，t e r ms t r e n g t h 。g a n g 的实验发现，结合 k - n e a r e s tn e i g h b o u r 分类器的情况下前三种方法最为有效。 2 4 1 文档频率阈值 词的文档频率是指包含这个词的文档数目。在训练文档集当中计算每个词的 文档频率，去除文档频率低于一定阈值的词，这些词通常被认为不代表任何信息， 对分类毫无用处。去除这些词不会影响对全局性能。 2 4 2i n f o r m a t i o nb a i n i n f o r m a t i o ng a i n 方法根据词是否出在文档中出现来计算这个词用来分类 的信息量的多少。设c ，c 。表示所有可能的类别。一个词的i n f o r m a t i o ng a i n 可以表示为： i g ( 小一耄p m o g p p ( w ) 耋p ( c ，1 w ) l 。g p ( c ，1w ) j 。1j j ，n 、 + p ( _ 废尸( c 厢) 1 0 9 p ( c ) 忆 这里的p 【c ，j 可以表示为文档集当中属于类。的文档的比例，p ) 可以表示 为包含词的文档在文档集当中的比例，p ( c ，1 wj 可以表示为类。中包含词胪的 文档的比例，p 【c fl w j 表示类。中彳i 包含词的文档的比例。 为训练文档集当中的每个词计算一个i n f o r m a t i o ng a i n 值，去除那些值低 复旦大学硕士学位论文 第二章相关工作 于一定阂值的词。 2 4 3c h i s q u a r e c h i s q u a r e 方法计算词矿和类。之间的依赖程度，如公式2 8 所示。 z 2w , c j ) = 百无冈n 而可( a d 耳- i c b 两) 2 硐 z s ) 这里的a 是。类当中包含词矿的文档数，b 是包含词舻但不属于。类的文档， c 是。类中不包含词矿的文档数，d 是不属于。类也不包含词矽的文档数，n 是 所有文档数。 通过以下两种基于c h i s q u a r e 的度量方法，去除那些c h i s q u a r e 值低于一 定阈值的词。 z 2 ( w ) = 童p b k 2 ( w 一) c z 。) 2 ；( w ) = m ，a x z 2w , c j ) 2 5 文本分类方法 ( 2 1 0 ) 文本分类任务是给文档分配一个或多个预先定义好的类别。近年来有许多基 于概率统计的分类方法被用于文本分类任务。文本分类可以被分为两种情况，两 类分类和多类分类。两类分类即文档被分为相关和不相关两类，多类分类是指文 档被分为多个类。对于多类分类的一般解决办法，是将多类问题拆分成多个不相 干的两类分类问题。这种方法的缺点是忽略了类与类之间的联系。下面介绍一些 在文本分类任务中常用的分类算法。设d ；他，d 。 是待分类的文档向量， c 。，c 。是所有可能的类别。 1 4 复旦大学硕士学位论文 第二章相关工作 2 5 1 类中心( r o c c h i o ) 分类算法 类中心分类算法是为每个类。构造一个原型向量，通过计算文档d 与各个原 型向量之间的距离，将文档分到距离最近的类里面。距离的计算方法一般是通过 向量的点乘或者一些相似度计算公式得出。类。的原型向量是训练文档集当中所 有属于类。的文档向量的平均。这种分类方法运行起来是非常快的。 2 5 2n a i v eb a y e s 分类算法 n a i v eb a y e s 分类算法 1 8 假设文章中词与词之间相互独立，根据训练数据 计算测试样本属于各个类的概率，如公式2 1 1 和公式2 1 2 所示。 班篙掣 e ( dj 的值不会夏化，凼此司以忽略掉。 p ( c ，i d ) = p ( c ，) 兀p i c j ) 尸0i c ，) ：单 m + 荟 p n j ( 2 1 1 ) ( 2 1 2 ) 公式中的彤是训练集当中属于类q 的文档数，是训练集当中词昕在类。 中出现的次数。 2 5 3k 近邻( k n n ，k - n e a r e s tn e i g h b o u r ) 分类算法 k n n 算法 1 9 计算测试文档与训练文档向量之间的距离或相似度，用k 个最 近或最相似的文档所属的类别标记测试文档。k n n 算法不需要训练时间，主要的 计算时间是用来计算文档之间的距离。 复旦大学硕士学位论文第二章相关工作 2 5 4 决策树算法 决策树算法通过训练集构造一棵决策树，并用这个决策树来判断测试文档向 量是否属于某个类，如c a r t 算法 2 0 。 2 5 5 支持向量机算法( s ，s u p p r o tv e c t o rm a t hin e ) 支持向量机算法 4 结合了降维和分类，将一个向量分为1 或一1 两类，其原 理如公式2 1 3 所示。 s = w 7 妒( d ) + 6 = 刚r k ( d ，以) + 6 y = 旒 昭1 3 d 表示训练集文档向量，n 表示可能的类别，即属于或不属于某个类别。 k ( d ，d j ) 表示核函数。 2 5 5 1 训练s v m 可分的情况 首先，考虑这种情况：数据是线性可分的。这意味着存在一个向量矿和一个 常数b ，使得对于训练集当中的所有文档以都满足公式2 1 4 ： w r p ，) + 6 1f ，y i = 1 w 7 0 f ) s 一1f ，y ；：一1 2 1 4 s v m 构造一个超平面w 7 妒忙) + 6 使得两个类的分界面之间的距离最大化。使 得超平面最优化的w 可以通过最小化l l w l l 2 来获得。最优酽可以写成一个庐国) 的线 性组合( 公式2 1 5 ) 酗y 以) 可以通过最大化小1 - 1 。a r q a ( a o 口耐 y ：o ) 求得吒，这里 复旦大学硕士学位论文第二章相关1 ：作 】，：( ) ，y 。) ，q 是一个对称矩阵，岛；y l y k ( d ；，d ，) ：y ，y p ，尸驴白，) 。 2 5 5 2 训练s 不可分的情况 在不可分的情况下，使得超平面最优化的w 可以通过最小化割w | 1 2 + c 薹岛 来获得，其中鼻满足以下约束条件( 公式2 1 6 ) ： w 7 庐0 。) + 6 1 一曼fy ，= 1 w 7 驴p f ) + 6s 一1 + 岳f ，y f ：一1 2 1 6 可以通过最大化1 _ 1 z a r q a ( 0 a sc 1 蒯y = o ) 求得。 当数据集非常庞大的时候，上面所述的优化问题是非常具有挑战性的，因为 内存需求随着数据集大小的平方增长。计算和存储的复杂度可以通过将训练集分 割成许多小块来降低，并使用单个向量来代表这些小块训练集。 2 5 6 投票分类算法 许多研究者已经对结合多类分类技术来构造一个单独的分类器做了深入研 究，这种过程通常被称做投票。投票算法使用一个分类器和训练集作为输入，在 训练集的多个不同的形式上对训练分类器多次训练。生成的分类器于是被结合起 来生成一个最终分类器，用来对测试集做分类。 投票算法可以被分为两种类型：b a g g i n g 算法和b o o s t i n g 算法。这两种类 型的主要区别在于他们生成的不同种类的训l 练集。 2 5 6 1 b a g g in g 算法 b a g g i n g 算法 2 1 使用的作为输入的分类器算法，( - ) 以及一个训练集t ，返 回一组分类器，( ) = ，1 ( k ，厶( ) ) ，这里，) 是一个从训练集的样本子集t r 学习 而来的分类器。样本子集是通过在训练集上叠代n 次的随机选择得来的，n 是训 练集的大小。这将会创建一个和原来一样大小的训练集合，但某些样本会被不止 一次的表示，然而其他的可能没有被表示过。 复旦大学硕士学位论文第二章相关工作 为了给一个新样本d 分类，每个分类器，( ) 对d 做一次分类( 公式2 1 7 ) ， 得到分类后的标记集合，l ( d i ，2 0 k ，厶0 ) 。投票分类器的结果是这些单个分类 器分出的数目最多的类别。 ，+ p ) = a 唱m a x y r ：f r 再三 2 5 6 2b o o s tin g 算法 ( 2 1 7 ) b o o s t i n g 算法 2 2 包含一系列的方法。和b a g g i n g 相同的地方是，这些方 法通过随机替代原训练集当中的样本，为分类器厂，( ) 选择一个大小为n 的训练 集。然而不同的是，选择样本的概率对于训练集当中的所有样本来说并不相同。 这取决于这个样本被前k - 1 个分类器分错的频率。这样b o o s t i n g 算法试图产生 新的分类器集合，对于当前分类性能不好的分类器，能更好的e 确的将样本分类。 不同形式的b o o s t i n g 算法产生了选择样本的不同概率。在a d a b o o s t 算法 2 2 中，设为训练集t ，选择样本d ，的概率为p 。，。首先，所有的概率都是相同的，比 如，对于所有样本d 。，p = i n 。为了决定p ，对于分类器f + ，( ) 的值，a d a b o o s t 算法首先计算使用分类器，( ) 错误分类样本的概率和e ，( 公式2 1 8 ) ： 弋弋 e r2 ，丢p f ， ( 2 1 8 ) 其次，a d a b o o s t 将正确分类的样本赋予较低的权重，将被错误分类的样本 赋予更高的权重。所有被，( ) 正确分类的样本的概率被乘上e ，所有被错误 分类的样本的概率被乘已e “。这里a ，；l o g f 三导1 。 最后，这些对概率值做正规化处理，使得他们的和为1 。 在这过程被循环r 次之后，将得到r 个分类器，1 ( h ，r ( ) 和r 个值 口，口。要给一个新样本d 分类，每个分类器，r ( ) 被用来给d 分类，得到分类 结果，1 0 l ，2 0 x ，0 ) ，不同于b a g g i n g 算法的是，并不给每个分类结果赋予 相同的权重，而是使用口，值来给结果赋权重。这意味着d 的最后的分类结果是 按照公式2 1 9 得来的： 厂+ ( 啦a r g m a k 。：积 复旦大学硕士学位论文 第二章相关工作 a d a b o o s t 算法的一个主要缺点是它不能很好的解决多类分类问题。而且， 不能处理一个文档可能属于多个类别的情况。a d a b o o s t m l t 算法 2 3 对此做了改 进。设文档d 。和类别c k 在第r 个循环中的权重为p 。首先，所有权重都相等， 比如对于所有样本d ；和所有类别c 。，p m = 1 n 。对于每一轮，a d a b o o s t m l 算 法计算k 个分类器，0 ，七) 的分类结果。，0 。，七) 表示类别c t 是否被作为样本d t 的分类结果。并根据公式2 2 0 调整权重： p 地f ，+ 1 1 = p 浙e x p ( - y 成，r 【d l ，七) ) ( 2 2 0 ) 这里，如果类别c 。属于样本d ，可能的正确类别，则y l k = l ；否则y ik = 一1 。在 权重调整之后对他们再做正规化处理，使得萃；p 肼+ 1 ) 2 1 。 在这过程循环r 次之后，将得到r k 个分类器，0 ，七) 。要给一个新样本d 分类，每个分类器对d 做分类，最后的分类结果由公式2 2 1 得出： ，+ 2 善f 2 6 特定领域文本分类 ( 2 2 1 ) 特定领域文本分类是为属于某一特定领域的文档分配一个或几个预先定义 好的类别，本质是文本分类在特定领域中的应用。特定领域文本分类系统能够极 大地提高特定领域研究者们的生产率和工作效率。然而这样的系统却还没有在日 常工作中得到应用。缺少系统的严谨的评测平台是阻碍其发展的一个主要因素 2 4 。文本检索领域的权威评测会议文本检索会议( t r e c ，t e x tr e t r i e v a l c o n f e r e n c e ) 于2 0 0 4 年开始在其面向特定领域的g e n o m i c s 项目中设立了文本分 类任务t r e c2 0 0 4g e n o m i c s 项目c a t e g o r i z a t i o n 任务t r i a g e 予任务，以 及t r e c2 0 0 5g e n o m i c s 项目c a t e g o r i z a t i o n 任务，是一种面向生物学领域的特 定领域文本分类任务，是目前特定领域文本分类领域最权威的评测平台。 同一般文本分类一样，必须把文档表示成分类器能够接受的形式，这中间要 经历预处理、特征选择等过程。他们的别在于： 1 、 处理的文档。特定领域文本分类所处理的文档是属于特定领域的， 而一般文本分类所处理的文档属于一般领域或多个领域。特定领域 文档中包含大量专有名词、术语等其他领域文档所不包含的词语， 特定领域的语言结构也可能和一般领域有所区别。 2 、 特征选择。特定领域文本分类必须选择与特定领域相关的特征。由 复旦大学硕士学位论文第二章相关工作 于特定领域文档和一般领域文档之间的区别，适用于一般领域的特 征选择方法可能不能提取出适合特定领域的特征。如专有名词、术 语、独特的语言结构等特征都需要特殊的处理，而其，这些特征在 特定领域文档中的分布与一般领域文档特征的分布不尽相同，因此， 常用于一般领域的基于概率统计的特征选择方法不一定能找出与特 定领域文档相关的特征。 特定领域文本分类与一般文本分类的共同点这决定了特定领域文本分类系 统采用一般文本分类的框架，他们之间的区别决定了特定领域文本分类需要特殊 的特征选择方法，为分类器提供与特定领域相关的文档特征。 以t r e cg e n o m i c s 项目c a t e g o r i z a t i o n 任务为例，其使用的语料库是由 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 lo fb i o l o g i c a lc h e m i s t r y ( j b c ) ， j o u r n a lo fc e l lb i o l o g y ( j c b ) ，以及p r o c e e d i n g so ft h en a t i o n a la c a d e m y o fs c i e n c e ( p n a s ) 。这些全文本文档的格式为基于h i g h i r e 文档类型定义( d t d ) 的s g 札格式。以2 0 0 2 年的文章作为训练集，2 0 0 3 年的文章作为测试集。 t r e c 2 0 0 4g e n o m i c s 项目c a t e g o r i z a t i o n 任务t r i a g e 子任务的目的是要 找出能用于g o 标注的文档，是一个二类分类任务。t r e c2 0 0 5g e n o m i c s 项目 c a t e g o r i z a t i o n 任务则由t r e c2 0 0 4g e n o m i c s 项目c a t e g o r i z a t i o n 任务t r i a g e 子任务衍生而来，包含4 个子任务，各个子任务的目标是在语料库中分别找出 属于a l l e l e so fm 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 种类型中的一种 类型的文档。可以把这4 个子任务看作4 个二类分类任务。 从任务的目的和要求来看，这些任务和一般文本分类任务一样，输入的是 文本文档，输出的是文档类别；并且有训练语料供分类器学习。所不同的是， 这些文档都是属于生物医学领域的学术文章，这些文章与一般领域文档有很多 不同之处，如生物医学领域术语、专有名词、基因名、蛋白质名等等，甚至包 括一些独特的语言结构，这些特征的分布与一般领域文档的特征分布不尽相同。 2 6 1 主要的特定领域文本分类系统类型 作为目前特定领域文本分类领域最权威的评测平台，参加t r e cg e n o m i c s 项 目c a t e g o r i z a t i o n 任务评测的文本分