（计算机应用技术专业论文）一种富文本分类方法的研究与实现.pdf

一种富文本分类方法的研究与实现 中文摘要 一种富文本分类方法的研究与实现 中文摘要 本文介绍了一种可应用于富文本的分类方法。分类目标文本是符合 o p e n d o c u m e n t 规范的o p e n o f f i c e o r g 文档。 本文通过分析常用的平文本分类方法在直接应用到富文本文档时表 现较差的原因，提出了富文本分类建模时应该考虑的因素，并将其归纳 为七个方面。本文从面向分类的角度深入地分析了o p e n o f f i c e o r g 文档， 描述了从文档中抽取与分类最相关的内容和格式、结构以及文档描述信 息的方法，构建了标签组件法、结构组件法和综合法三种不同的文本分 类模型，最后用朴素贝叶斯方法实现了o p e n o f f c i c e o r g 文档的三种分类 器。 本文在复旦语料库完成了封闭测试，在随机下载的文档集上完成了 开放测试，然后对实验结果进行了详细地分析。实验结果表明本文所提 出的三种方法可以较好地解决o p e n o f f i c e o r g 文档的自动分类问题。 关键词：文本分类；富文本分类；o p e n d o c u m e n t ；分类建模；特征选择 作者：朱斐 指导老师：昌强 r e s e a r c ha n di m p l e m e n t a t i o no far i c hf o r m a tt e x t c l a s s i f i c a t i o nm e t h o d a b s t r a c t t h i st h e s i si n t r o d u c e sa l la p p r o a c ht h a ti sa p p l i c a b l et or i c hf o r m a tt e x t ， a i m i n g a t c l a s s i f y i n go p e n o f f i c e o r g d o c u m e n t sw h i c hf o l l o w o p e n d o c u m e n t s t a n d a r d c o m m o np l a i nt e x tc l a s s i f i c a t i o nm e t h o d sb e h a v ep o o rw h e ns i m p l y a p p l i e do nr i c hf o r m a tt e x t s t h et h e s i s ，b ya n a l y z i n gt h er e a s o n s ，p r o p o s e s t h ef a c t o r st h a ts h o u l d b e t a k e ni na c c o u n ti n s t a g eo fr i c hf o r m a tt e x t c l a s s i f i c a t i o nm o d e l i n g a n dt h e ng r o u p st h e mi n t os e v e na s p e c t s t h et h e s i s a n a l y s e s a n d p a r s e so p e n o f f i c e o r gd o c u m e n t f r o mt e x tc l a s s i f i c a t i o n v i e w p o i n t ，d e p i c t st h em e t h o d so fe x t r a c t i n gc o n t e n t ，f o r m a t t i n g ，s t r u c t u r ea n d d e s c r i p t i v ei n f o r m a t i o n ，w h i c h a r em o s tr e l a t e dt oc l a s s i f i c a t i o n ，f r o m o p e n o f f i c e o r gd o c u m e n t s ，a n dt h e nc o n s t r u c t st h r e ed i f f e r e n tc l a s s i f i c a t i o n m o d e l sf o ro p e n o f f i c e o r gd o c u m e n t s ，r e s p e c t i v e l yc a l l e dl a b e lc o m p o n e n t s c l a s s i f i e r , s t r u c t u r ec o m p o n e n t sc l a s s i f i e ra n dc o m p r e h e n s i v ec l a s s i f i e r t h e t h e s i si m p l e m e n t st h e s et h r e ec l a s s i f i e r st h r o u g hn a f v eb a y e s t h et h e s i sa c c o m p l i s h e sc l o s e dt e s t i n go nf u d a nc o r p u sa n do p e nt e s t i n g o nc o r p u sr a n d o m l yd o w n l o a d e df r o mi n t e m e t ，a n dt h e ns t a t e sc o r r e s p o n d i n g a n a l y s e si nd e t a i l t h er e s u l ti n d i c a t e st h a tt h r e ec l a s s i f i e r sd e s c r i b i n gi nt h e t h e s i sc a na u t o m a t i c l yc l a s s i f yo p e n o f f i c e o r gd o c u m e n t sa n dw o r kq u i t e w e l l k e y w o r d s ：t e x tc l a s s i f i c a t i o n ；r i c hf o r m a tt e x tc l a s s i f i c a t i o n ；o p e n d o c u m e n t ； c l a s s i f i c a t i o nm o d e l i n g ；f e a t u r es e l e c t i o n w r i t t e nb yz h uf e i s u p e r i v i s e db yl vq i a n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所取得的成果。 除文中已经注明引用的内容外，本论文不含其他个人或集体已经发表或撰写过的研究成果 也不含为获得苏州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要 贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律责任。 研究生签名：2 轾_ 日期：2 蚵 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、中国社科院文献 信息情报中心有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密 论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公 布( 包括刊登) 授权苏州大学学位办办理。 y - 删毕冯 迎? ! 西 一种富文本分类方法的研究与实现第一章绪论 1 1 研究背景现状 第一章绪论 随着国际互联网和企业内部网的飞速发展，各种数字文档和数据迅 速增长和广泛应用。如何快速有效地获取、管理和使用这些数据，已经 成为信息系统学科迫切需要解决的重要问题。作为解决这些问题的基本 工具之一，自动文本分类技术得到了空前的发展，引起了人们普遍的关 注 1 】 孙。 文本分类可以上述至2 0 世纪6 0 年代，但是仅到了2 0 世纪9 0 年代 才成为信息系统的子领域。文本分类可以应用到很多领域，从基于控制 词表的文本检索，到文档过滤、自动元数据( m e t a d a t a ) 的生成、词义消 歧、w e b 资源层次目录的生成、文档组织和选择等【2 】。 传统上的文本分类由人工完成。许多门户网站，如y a h o o ! 、新浪都 聘请大量的专业人员进行文本分类，以提供网站或网页分类目录的服务 3 1 。但是，由于信息量巨大以及人工分类效率低下等原因，使得每天新涌 现的数字资料无法得到及时地处理。如何利用自动化技术，快速有效地 协助人工分类，来处理大量迅速增长的分类需求，是现今信息服务与知 识管理的重要课题。 伴随着计算机技术的不断发展，文本的表现形式越来越丰富。出于 功能实现以及商业目的，很多企业、组织或联盟制定了各种适用于特定 系统或特定程序的文档格式。这些文档格式常常与应用系统或应用程序 关联，导致了文档的不统一、不规范、封闭性和互不兼容，很大程度上 第一章绪论 一种富文本分类方法的研究与实现 缩小了用户选择应用系统和应用程序的范围，给用户造成大量的困扰。 为了解决这个问题，结构化信息标准组织o a s i s ( o r g a n i z a t i o nf o rt h e a d v a n c e m e n to fs t r u c t u r e di n f o r m a t i o ns t a n d a r d s ) 定义了开放办公软件文 档格式规范o p e n d o c u m e n t 【4 1 ( o p e nd o c u m e n tf o r m a tf o ro f f i c e a p p l i c a t i o n s ) 。o p e n o f f i c e o r g 是一组跨平台的办公套件，其文档遵循 o p e n d o c u m e n t 规范并且兼容大多数办公文档，如m so f f i c e 系列文档、 s t a r o f f i c e 系列文档、p d f 文档等。0 p e n d o c u m e n t 和o p e n o f f i c e o r g 受到了 s u n 、i b m 、g o o g l e 、永中等许多公司的支持，得到了较广泛的应用。 近年来，文本分类的研究在信息检索和机器学习领域得到了很多关 注，研究人员提出了多种效果较好的方法，如s v m 、k n n 、朴素贝叶 斯分类算法【1 】( 2 1 等。常见的文本分类以平文本分类为主，关注的重点局限 于文本的内容，较少考虑文本的其他属性嘲。然而在现实环境中，计算机 处理的大量文档多数是富文本文档。由于富文本文档远比平文本复杂， 包含了丰富的格式、结构、文档描述信息，也包含了很多噪音，使得富 文本更难于分类。有些研究人员将常用的平文本分类方法直接应用在富 文本文档上，但是分类效果较差，根本无法满足实际需求5 】【6 1 。因此，研 制和开发相应的富文本分类技术显得十分迫切。 1 2 研究内容和意义 本文所在的课题组“中文协同办公系统z o f f i c e ”是苏州大学2 1 1 重 点建设子项目，目标是开发一个中文协同办公系统。该项目核心子项 z o f f i c e ( c o r ev 1 0 ) 已经完成，并于2 0 0 5 年1 2 月通过江苏省科技厅鉴 ：0j一 一种富文本分类方法的研究与实现 第一章绪论 定。 z o f f i c e ( c o r ev 1 0 ) 中所使用的文档遵循o p e n d o c u m e n t 规范，支 持o p e n o f f i c e o 玛的文档格式。本文所做的工作就是实现o p e n o f f i c e o r g 文档的自动分类，从而为z o f f i c e 提供自动文档分类的特色功能。 本文通过分析常用的平文本分类方法不合适直接应用到富文本文档 原因，讨论了富文本分类建模时应该考虑的因素，完成了富文本的标签 组件法分类器和结构组件法分类器的建模。本文根据o p e n o f f i c e o r g 文档 的特点，以现有的平文本分类方法为基础，分别从o p e n o f f i c e o r g 文档中 抽取与分类最相关的内容、格式、结构以及文档描述信息，依照富文本 分类模型，构建了o p e n o f f i c e o r g 文档的标签组件法分类器、结构组件法 分类器。在分析了实验数据之后，本文按照结合两种分类方法的思路， 提出了o p e n o f f i c e o r g 文档的综合法分类器，即组合标签组件法分类器和 结构组件法分类器并通过参数协调控制进行分类预测。本文用朴素贝叶 斯方法分别实现了上述三种方法的分类器，完成了o p e n o f f c i c e o r g 文档 的自动分类。 1 3 本文的组织 本文共分六章。第一章介绍了文本分类和富文本的背景及其研究现 状，然后叙述了研究内容和研究意义。 第二章给出了文本分类的定义和实现文本分类系统的基本框架，简 要地介绍了文本分类的类型和应用。在比较了各种文档索引方法后，确 定了采用词语一文本作为文本表示的方法。本章还详细地论述了文本权 第一章绪论 一种富文本分类方法的研究与实现 重、特征降维和文本分类的各种常用方法及其各自的优缺点。 第三章首先提出了平文本分类直接应用于富文本时存在的问题，讨 论了富文本分类时应该考虑的七个因素，完成了富文本分类器的建模， 从文本分类的角度详细地分析了o p e n o f f i c e o r g 文档的存储方式、文档组 成、文档结构，设计了三种可用于o p e n o f f i c e o r g 文档的分类方法。 第四章提出了改进的2 , 2 - d f 特征选择方法，详细地叙述了 o p e n o f f i c e o r g 文档分类的处理流程以及三种可应用于o p e n o f f i c e o r g 文 档的分类器的实现方法。 第五章首先叙述了度量文本分类有效性的五种标准；接着给出了复 旦语料库上的封闭测试结果和随机语料库上的开放测试结果，用五种标 准对三种分类方法进行评价，并且进行了详细地分析。 第六章总结了本文的工作，作出了展望。 一种宫文本分类方法的研究与实现 第二章平文本的分类 2 1文本分类的定义 第二章平文本的分类 文本分类( t e x tc a t e g o r i z a t i o n 或t e x tc l a s s i f i c a t i o n ：t c ) 是指在给 定分类体系的情况下，根据文本的属性自动确定其所属类别的过程【1 】【2 1 。 即，对于给定的包含| d j 个文本的集合d = 吐，吐，啪| 和包含j c 个不相关 类别的集合c = h c ：，乍l ，文本分类是将布尔值 护崛f a l s e 赋给每个 e d c ( 1 - i - l c ，1 j 俐) 对的任务。如果嘭属于类别c f ，那么将 t r u e 赋给 ，否则将f a l s e 赋给 。文本分类可以更正式地表示 为：通过分类函数o ：d x c 斗 t r u e ，f a l s e 找到描述文本如何分类的未知目标 函数面：d x c - - , t r u 邑f a l s e 的个近似表示，使得$ 尽可能地和巾相似2 1 。 在本文中，文本是指媒体新闻、科技报告、电子邮件、技术专利、 网页、书籍等，或者是其中的一部分；文档是指文本在计算机内的存储 表示；文件指是在计算机内存储的程序或文档。 2 2文本分类的系统框架 从总体来看，文本分类系统可以分为训练、测试和分类三个部分。 其中训练的目的是训练可用于分类的分类器，主要包括两个过程： 1 建立特征集，基本流程是：预处理训练样例专文档索引一特征降 维呻特征集建立。 2 训练分类器，基本流程是：预处理训练样例j 根据特征集取得文 本的特征表示一训练分类器。 第二章平文本的分类 一种富文本分类方法的研究与实现 分类则是分类器依据训练结果对未知文本进行分类并给出类别标识 的过程，基本流程是预处理未知文本专根据特征集取得文本的特征表示 _ 分类器分类专给出分类结果。 测试的前半部分与分类相同，只是在得到测试例的分类结果之后会 将分类结果送到评测器得出分类器的评测结果。文本分类系统的框架如 图2 1 所示。 世例( ；图 ( 滁例自预萄冲习序司 处 r 1：i 厶一厶一 詈 的 ! ； ! i 特征表示l i 特征 悖疰器l | ! i 1 分类结果； ；卜器i ； 尉试部分 图2 1 文本分类系统的框架 一般而言，文本分类中的预处理包括去除非文本内容的标签、去停 一种富文本分类方法的研究与实现 第二章平文本的分类 止词、执行词于提取等操作，其中停止词是指无意义的、对分类没有影 响的字和词，如代词、介词、连词等。 2 3文本分类的两种类型 根据不同的分类要求，文本所属类别个数可能不同。文本分类有两 种类型：单标号( 单类别) 分类和多标号( 多类别) 分类( 扪。单标号分类 也称之为非覆盖分类，每个文本属于并且只属于一个类别；而多标号分 类则不然，个文本可以属于0 到i c l 个类别。 二分分类是单标号分类的一个特例，其中的每个文本属于类别c ，或者 其补集c r 。二分分类问题的算法可以用于多标号问题：只要将c = c l ，钓 下的多标号问题转化为l c l 个不相干的二分分类问题即可，但反之则不然。 这是由于在多标号问题中，分类器可能将一个文本归到多个类别，也可 能根本无法归到任何类别。由此可以看出，二分问题要比多标号问题更 具一般性。 除非特别说明，本文处理和讨论的是二分分类问题，这是因为： 1 二分分类问题很重要并且有很多实际的应用。 2 解决了二分分类问题也意味着解决了多标号分类问题。 3 大多数二分分类问题和用于二分分类的技术是已有单标号分类问 题的特例，并且能比单标号情况更易于说明。 由此，可以把c = 乍i ) 中的分类器看成是i c l 个对于给定类别 c i ( i = 1 ，l c f ) 不相干的分类问题。这样，用于类别c i 的分类函数 $ ，：d - - e t r u e ，f a l s e ) 是未知目标函数$ ，：d _ t r u e ，f a l s e ) 的近似值。 第二章平文本的分类 一种富文本分类方法的研究与实现 2 4文本分类的应用 文本分类技术有广泛的应用，如布尔信息查询系统的自动索引、词 义消歧、文档组织和归档以及文本过滤等。 2 4 1 布尔信息查询系统的自动索引 在布尔信息查询系统的自动索引中，每篇文档被赋予一个或多个描 述其内容的关键词或关键短语，这些短语属于一个称之为控制词典的有 限集合。如果控制词典中的条目被看成是类别，那么文本索引就看成是 文本分类的实例，并且可以使用自动文本分类技术。 2 4 2 词义消歧 词义消歧通常是指根据多义词所处的上下文环境确定出该词此时具 体含义的行为【7 】 8 1 。例如，“建筑材料”中的“材料”是指物质、设备， 而“人事材料”中的“材料”是指文件、档案。词义消歧对包括自然语 言处理和信息检索在内的很多应用来说都很重要。如果将多义词出现的 上下文看成是文本，将词义看成是类别的话，那么词义消歧也可以被看 成是分类问题。 自然语言处理的其他一些问题，如上下文感知的拼写纠正、介词短 语搭配、词性标注，都可以根据文本分类技术得到解决。 2 4 3 文档组织 许多文档组织和归档的问题可以利用文本分类技术。例如，新闻报 纸编辑部门在广告刊登之前要进行必要的分类，如分成招聘、汽车销售、 r 一种富文本分类方法的研究与实现第二章平文本的分类 房产等几大类。类似的应用还包括( 1 ) 将稿件分到相应的类别中以方便 查找；( 2 ) 将新闻文章自动填充到合适的栏目中；( 3 ) 将会议文献自动 分类到合适的主题中。 2 4 4 文本过滤 文本过滤是指根据用户的需要，对由信息生产者向信息消费者以异 构方式输入的文本进行分类、筛选的活动。在报社中，“自动过滤系统” 可以过滤掉编辑不感兴趣的文档。这种“自动过滤系统”可以看成是单 标号的文本分类系统。类似的，邮件过滤系统也可以用来屏蔽“垃圾” 邮件，并且可以将非“垃圾”邮件进一步按照用户关心的主题类别分类。 一个“好”的搜索引擎可以将根据用户的具体需求，将互联网上所有与 用户需求相关的网页提供给用户，屏蔽其他无关的网页。这种搜索引擎 实质上也利用了文本分类技术。 2 5文本的索引 在现阶段，文本一般不能直接由分类器或者构建分类器的算法解释。 因此需要将文本映射到内容的索引。目前常用术语文本( t e r m - t e x t ) 矩 阵的方法完成上述映射，得到的效果较好。 2 5 1 文本的表示 人在阅读文章后，根据自身的理解能力和已掌握的知识可以得出对 文章内容的模糊认识；计算机不具有人类这样的智能；，不能轻易地“读 懂”文章。因此文本自动分类的一个基本问题是如何将文本有效地表示 第二章平文本的分类 一种富文本分类方法的研究与实现 为计算机可以“理解”的形式，然后此基础上进行分类。 在文本分类中，文本集常常通过术语文本的矩阵表示。矩阵中的每 一项记录了术语是否在文本中出现以及出现的情况。由于并非所有术语 都出现在每篇文本中，因此术语文本矩阵往往是高维稀疏矩阵。 文本分类的各种方法对术语的理解有所不同，选择不同的对象作为 术语，如字、词语、句子、旬群、概念、义项掣9 】【l o 】 1 1 】 1 2 】 1 3 】 14 1 5 。目前 很多分类方法选择词语作为术语，取得了较好的分类效果。一些研究人 员尝试选择使用更复杂的对象作为术语，如词组、概念、句子等，但结 果并不理想。其原因在于：( 1 ) 尽管更复杂的对象具有更高的语义品质， 但是相对于只用词语的索引而言，其统计品质较差；( 2 ) 目前，自然语 言处理的水平还没有达到很高的层次，知识体系还在不断建设和完善， 因此很可能会由于知识体系的不合理以及处理方法不当而产生负面影 响。考虑到这些实际问题，本文选择词语作为术语。 在英文文本中，单词之间可以用空格作为分隔符；而中文文本没有 明确的分隔符，需要预先对文本切分处理。在本文中，如果没有特殊的 说明，术语指的是英文中的单词、词组以及中文切分后得到的字、词语。 在文本分类中，术语用来表示文本，也称之为文本的特征。 2 5 2 文本的权重 文本分类中，文本通常由特征的权重向量嘭= ( w i 一，) 构成，其中 ，是在文本集中出现的所有特征的集合；( o 1 ) 表示特征气对文本 d ；语义的贡献度，称为权重 1 】 2 】。各种分类方法对特征权重的理解和计算 一种富文本分类方法的研究与实现第二章平文本的分类 方法均有所不同，但大多数都是基于以下两个经典的信息论假设【1 【2 】： 1 一个特征在一篇文本中出现的次数越多，则该特征与文本主题的 相关程度就越高。 2 一个特征出现在整个集合中所有文本的次数越多，则该特征区别 文本类别的能力越弱。 常用的特征权重计算方法有t f x i d f 权重法、t f c 权重法、j t c 权重法等。 为了方便叙述，定义如下符号： 是特征f 。在文本嘭中的权重a 厶是特征气在文本t 中的频次。 体是特征气出现在整个文档集合中的总次数。 n 是集合中文本的数量。 m 是集合中去掉停止词并且完成词干处理后的特征总数。 2 5 2 1t f x i d f 权重法 t f x i d f 1 1 权重法是一种比较著名的计算特征权重的方法。这种方法用 文档的总数量除以文档中特征气出现的频次，计算方法如式2 1 所示。 = 厶t 。s ( 鲁 c 式2 - 1 ， 2 5 2 2t f c 权重法 由于t f x i d f 权重法没有考虑到文档长度，因此文档长度相同或者相近 时，t f x i d f 权重法不会受到太大的影响，但是如果文档长度相差很大时， t f x i d f 权重法会出现明显的不合理。t f c 1 1 权重法使用了长度归一化因子， 第二章平文本的分类 一种富文本分类方法的研究与实现 计算方法如式2 - 2 所示。 2 5 2 3l t c 权重法 ( 式2 - 2 ) 为了减轻较大的频次差别产生的影响，l t c 1 3 权重法使用特征频次的对 数取代特征频次，同时加上l ，以避免特征频次为0 时产生错误，计算方 法如式2 3 所示。 2 6降维 ( 式2 3 ) 特征的维数对应着不同词语的数量。一个中等规模文本分类问题的 特征空间通常高达几万维，十几万维，甚至是数十万维。如果直接在这 样一个高维特征空间上进行训练和分类，很可能带来两个问题：一是由 于计算特征时的处理花费极高，标准的文本分类技术无法处理这样庞大 的特征集，使得在低维空间上具有良好性能的分类算法在计算上变得不 可行；二是训练样本个数一定的前提下，过多的特征很可能导致“过学 习”或“过训练”。特征空间的高维度是文本分类研究中存在的一个难题， 也是亟需解决的问题。 为了提高分类器的训练和分类可行性以及效率，同时也为了避免“过 jj。l。jjlj一 一种富文本分类方法的研究与实现第二章平文本的分类 学习”和“过训练”，在训练分类器之前，往往需要将特征维数压缩到与 训练样本个数相适应的规模。这种对原始特征集的简约处理称为特征降 维。 特征降维有两个基本的途径：特征选择和特征抽取。特征选择是指 依据某个准则从众多原始特征中选择部分最能反映类别特征的相关特 征。特征抽取是指依据某一原则构造原始特征空间到新的低维特征空间 的一种变换，从而将分散在众多原始特征中的分类信息或鉴别信息集中 到少量的新特征上来。 2 6 1 特征选择 特征选择从原始的特征集丁中选择集合r ，使得刖吲并且当集合 丁用于文档索引时，产生最高的有效性。实验f 1 6 1 表明，特征选择使分类 有效性方面有适度的增长，但在不同的分类器上有不同的表现。 人们已经研究了多种特征选取方法，如：文档频次法、信息增益法、 互信息法、z 2 统计法、术语强度法等。实验1 叼【1 7 】 1 8 】【1 9 】 2 叫结果表明：信息 增益法和z 2 统计法的效果最佳；文档频次法次之，但具有实现简单、算 法复杂度低的优点；术语强度法再次之；互信息法最差。图2 2 和图2 3 显示了这五种方法的平均表现。 第二章平文本的分类一种富文本分类方法的研究与实现 图2 2五种特征选取法在k n n 上的表现 - k 飞 o 错= ： 图2 3五种特征选取法在l l s f 上的表现 2 6 1 1 文档频次法( d o c u m e n tf r e q u e n c y ) 特征的文档频次是指包含特征的文档数量。文档频次法计算训练集 中的每个特征的文档频次。文档频次法认为文档频次小于某个闽值的特 征对分类预测而言不具有代表性，故而要去掉。文档频次法保留频次大 于该闽值的特征。 2 6 1 2 信息增益法( i n f o r m a t i o ng a i n ) 信息增益法是一种常用的特征选择方法，它表示了特征在训练集上 的分布情况。信息增益法通过统计特征在各个类别中的出现和未出现次 数来计算。对于c l ，一，c i c j 个可能的类别，特征气的i g 值的计算方法如式 1 4 一种富文本分类方法的研究与实现第二章平文本的分类 2 4 所不。 ，g ( ) ：一2 p ( q ) l o g p 托) + p ( f i ) 2 p ( q l ) l 。g e ( c , i f 。) + p ( i ) ! p ( q i - ) l o g p ( q i - ) ( 式2 _ 4 ) 其中，p ( q ) 是从文档集合中属于类别c i 的文档的概率，p ( ) 是包含特征 t k 的文档的概率，p ( qi 气) 是属于类别q 并且包含特z 厂_ t 。的文档的概率， p ( qi ) 是属于类别c i 并且不包含特征的文档的概率。 信息增益法计算训练集中每个特征的i g 值，并去除i g 值低于预定 义阈值的特征。 2 6 1 3z 2 统计法 z 2 统计法衡量特征和类别q 之间的依赖程度，计算方法如式2 5 所示。 z 2t k ，c i ) = 瓦群鬈 拭2 其中，a 是属于类别c i 同时包含特征气的文档数，b 是不属于类别c ，同时 包含特征的文档数，c 属于类别c ，但不包含特征气的文档数，d 不属于 类别c 同时不包含特t k 的文档数，n 是全部的文档数。 有两种z 2 统计法：平均值z 2 统计法和最大值z 2 统计法，计算方法分 别如式2 - 6 、式2 7 所示。 z 2 ( 气) = 呈p ( c ) z 2t k ，c i ) ( 式2 - 6 ) z 。( ) = m a x 銎z 2 ( t ，q ) ( 式2 - 7 ) 2 6 2 特征抽取 特征抽取从原始的特征集合丁中生成一个“合成”的集合丁，使得 第二章平文本的分类一种富文本分类方法的研究与实现 刖i t i 并且当集合f 7 用于文档索引时，产生最高的有效性。 由于原始的特征可能不是文档内容表示的最佳元，特征抽取的方法 通过创建一个没有歧义、同义等问题的“人工合成”特征解决该问题。 特征抽取的方法包含了从原有特征中抽取新特征以及将原有的表示转化 为新的基于新合成元的表示。 2 7常用的文本分类方法 文本分类是自动确定文本所属类别的问题。常见的文本分类方法有 r o c c h i o 算法、k n n 、支持向量机、朴素贝叶斯方法等。 为了方便叙述，定义如下符号：d = d i ，啪 是要分类的文档向量， c l ，乍i 是文档可归类的类别，f 是类别q 的训练文档数。 2 7 1r o c c h i o 算法 r o c c h i o 分类器最早根据信息检索中用于计算“查询”( q u e r y ) 与文 档之间的关联程度的r o c c h i o 公式改造而来的。r o c c h i o 分类器非常简单 和直观，在文本分类领域得到了广泛的应用。 r o c c h i o 分类器按照式2 - 8 所给出的方法计算每个类别c f 的 i = ( ，一砷) 嘲。 够；未，南寸；蠹，南 式2 - 8 其中t k 在文档d j 中的权重，p d 墨是训练集中的正例，e q 是训练集 中的负例，和y 是正例和负例的控制参数。 r o c c h i o 分类器很易于实现并且比较有效，但在扩展的时候会将相关 一种富文本分类方法的研究与实现 第二章平文本的分类 文档向量直接与原查询合并，引起特征过多，计算量过大，同时某些相 关文档中偶然出现的与查询无关的词也将引入新的查询。 2 7 2k 近邻算法( k - n e a r e s tn e i g h b o r ：k - n n ) 近邻算法通过查询已知类别的例子情况，来判断新例子与已知例子 是否属于同一类。近邻算法存在很多种变种，其一般的思路是：首先存 储全部( 或选择部分) 训练例子，通过相似性函数计算测试例子与所存 储的训练例子的距离来决定类别的归属。 k n n 属于近邻算法，它通过选择与测试例子最近的k 个训练例子 来实现，测试例子的类别通常是k 个例子中出现最多的类别。k n n 的 决策规则2 1 如式2 - 9 所示。 y ( d ，c j ) = s i m ( d ，t ) y ( 哆，q ) 一岛 ( 式2 - 9 ) d j e k n n 其e p ，y ( t ，q ) o ，1 ) ：如果文档d j 属于类别q ，则y ( t ，c ，) - - 1 ；否则 y ( t ，c 1 ) = o 。s i m ( d ，d j ) 为测试文档d 到训练文档办之间的距离。岛是一个 给定的阈值。 k n n 分类算法易于实现，但是也存在着问题 2 l 】 2 2 】： 1 k n n 分类算法在应该存储多少训练例子上存在明显的难点。如果 存储全部的例子，分类器的分类速度可能太慢且不实用；如果存 储的例子过少，可能会训练不充分，直接影响分类效果。较为理 想的情况是存储可以概况重要信息的典型例子，然而如何确定这 些例子是一个难题。 2 k n n 分类器的分类效果与k 值的选取有很大关系。目前没有很 好的方法确定k 值，一般采用先设定一个初始值，然后根据实验 测试的结果调整。 2 7 3 支持向量机( s u p p o r t v e c t o rm a c h i n e ：s v m ) s v m 来自于统计学理论，采用结构风险最小化原则，其基本思想是， 对于一个给定的具有有限数量训练样本的学习任务，如何在准确性和机 器容量之间折衷，以得到最佳的推广性能2 ”。 设给定的训练集( _ ，y z ) ，( 而，y ：) ，( 葺，y 1 ) x r ”，y 1 , - 1 ) 可被一个超平 面( w x ) + 6 = o 线性分割。如果训练集中的矢量能被超平面无错误地分割， 且距该超平面最近的矢量之间的距离最大，则称该超平面为最佳超平面。 s v m 算法示意如图2 4 所示，其中距离超平面最近的点为支持矢量 ( s u p p o r tv e c t o r ) ，对决策面起作用的点称为支持向量。 。二二髟l 图2 - 4s v m 算法示意图 s v m 通过使用式2 - 1 0 将一个向量d 分成1 或者是1 。 s = w ，( d ) + 6 = 羔。a j y j k ( d ，d j ) + b ( 式2 - 1 0 ) 其中y = ! ：1 ，5 篡m 括。， d n ；。是训练向量， ” 二，是对应的类别乃e - 1 ，1 ) ， k ( d ，t ) 用于表示核，6 是预设定的阈值。 s v m 表现出了较好的性能，但也存在一些的不足和缺点 2 2 】 2 3 】： 1 训练s v m 需要求解二次规划问题，计算复杂度高，内存需求量大。 一种富文本分类方法的研究与实现 第二章平文本的分类 2 由于训练样本个数较多时会得到大量的支持向量，使得分类器计 算量过高，导致s v m 很难在大规模的应用中实现。 3 s v m 仅能应用于二分问题，应用范围受到很大地限制。 2 7 4 朴素贝叶斯方法( n a i v eb a y e sc l a s s i f i e r ：n b ) 贝叶斯方法在机器学习领域中被广泛地研究和应用。m i c h i e 研究发 现，贝叶斯方法在多数情况下与其他学习算法性能相当，在某些情况下 还优于其他算法 2 4 1 。 贝叶斯分类器将文档看成独立词语( w o r d ) 的集合。尽管这个假设 通常是不正确的，但是贝叶斯分类器在文本分类中表现出了较好的效果， 并且这种假设大大降低了分类器的计算复杂度，从而提高了贝叶斯分类 器的实用性。 贝叶斯分类器通过词语向量属于类别c i 的概率，得出文本属于类别c f 的概率，计算方法如式2 - 1 l 所示。 j p ( c f = 掣铲 c 越 其中，尸( 哆) 是随机取得的向量嘭作为其表示的概率；尸( c ，) 是随机获取的 文档属于c i 的概率。 由于向量办的数量较大，使得p ( 嘭ic i ) 值估计成为一个难题。为了弱 化这个问题，两个同等的文档向量在被认为是随机变量时，在统计上相 互独立。加入独立性的假设后，p ( t c i ) 的计算方法如式2 - 1 2 所示。 p ( 刮q ) = 兀p ( t lc 。) ( 式2 1 2 ) 5 吩 在式2 - 1 2 中，p ( t lc 。) 的值往往很小，导致p ( 嘭l q ) = 丌p ( t lc , ) - + o ， 第二章平文本的分类 一种富文本分类方法的研究与实现 在实现时常常会由于计算机中浮点数的表示、精度等原因造成误差，导 致预测错误。为了解决这个问题，在式2 - 1 2 两边取对数，做一下变形， 得到式2 - 1 3 。 蛾( 咆) 乩s p ( f = l o g ( p ( t c i ) ) l e d i p ( 嘭i c , ) ：z l o g ( p ( t c , ) ) t f i d i 使用这个假设的概率分类器称之为朴素贝叶斯分类器。在实现朴素 贝叶斯分类器时，采纳m 估计，即有统一的先验概率并且m 等于词语表 的大小，于是尸( 旧) 的估计可以近似地用公式2 - 1 4 计算。 帆) a 揣 ( 式2 - 1 4 ) 其中，i vj 是训练集中的不同词语的总数，f ( t lc 。) 是词语f 在类别c f 中出现 的频次，( t 。fc f ) 是类别为c i 的文档所包含的词语总数。 朴素贝叶斯分类器具有以下特点： 1 观察到的每个训练样例都可以降低或升高某假设的估计概率，这 提供了一种比其他算法更合理的学习途径。而其他算法会在某个 假设与任一样例不一致时完全去掉该假设。 2 先验知识可以与观察数据一起决定假设的最终概率。在贝叶斯学 习中，先验知识的形成可以是每个候选假设的先验概率或者是每 个可能假设在可观察数据上的概率分布。 3 可允许假设做出不确定的预测。 4 新的实例分类可由多个假设一起做出预测，用它们的概率加权。 - 一种富文本分类方法的研究与实现 第二章平文本的分类 2 8本章小结 本章给出了文本分类的定义和实现文本分类系统的基本框架，简要 地介绍了文本分类的类型和应用。在比较了各种文档索引方法后，确定 了采用词语一文本作为文本表示的方法。本章还详细地叙述了文本权重、 特征降维和文本分类的各种常用方法并讨论了各自的优缺点。 第三章宙文本分类研究 一种富文本分类方法的研究与实现 第三章富文本分类研究 3 1富文本和平文本 富文本是一种用标准化的方法来对不同的文本属性、格式以及结构 等信息进行编码的文本；平文本指的是只包含文本内容而不包含描述信 息的文本州。m sw o r d 的d o c 文档、o p e n o f f i c e o r g 的o d t 文档属于富文 本文档，而t x t 文档是典型的平文本文档。 富文本通常比平文本有更丰富的构成、组织和表示。富文本允许有 结构信息，允许有风格、样式等格式信息，允许加入元数据( m e t a d a t a ) 等文本信息，并且通常是由文本、图形、图像等异构信息源所构成。 3 2平文本分类面临的问题 近年来，文本分类的研究在信息检索和机器学习领域得到了很多关 注，研究人员提出了多种效果较好的方法。随着文本表现形式越来越丰 富，现在计算机处理的大量文档多数是富文本文档，文本分类的研究对 象正逐渐转变为富文本。然而传统的文本分类仍然以平文本分类为主， 目前富文本分类的研究主要是网页分类，针对其他富文本类型文档的分 类研究比较少。 平文本分类关注的重点局限于文本的内容，较多地考虑文本本身信 息，很少考虑富文本所特有的上下文语境信息、结构信息、格式信息、 元数据信息以及其他描述信息。如果将平文本分类方法直接应用在富文 本上，将导致很大的偏差，失去主要的主题和重要的焦点。同时，用平 一种富文本分类方法的研究与实现第三章富文本分类研究 文本分类方法处理富文本时，许多有助于分类的描述信息在经过了分类 预处理之后会丢失。实验表明5 】 6 1 ，平文本分类方法直接在富文本文档上 执行的效果较差。由此可见，平文本分类方法不能满足富文本分类的要 求，需要重新设计一种分类方法。 3 3富文本分类时应考虑的因素 3 3 1 富文本的格式 富文本可以包含丰富的文字格式和段落格式。富文本的文本可以具 有不同的字体、字形、字号、颜色、下划线、着重号以及其他效果，也 可以具有对齐方式、缩进方式、段前段后间距、行间距等段落格式。这 些都是平文本所不具备的，所以常用的平文本分类方法中没有考虑这些 因素。而富文本则不然，文档中颜色、字形和字体等格式的变化对文档 内容的把握有显著的突出作用 2 5 1 ，因此在设计富文本分类方法时，应该 把文本的格式考虑在内。 文本的文字格式对文本分类的作用各有不同。本文选取了其中的字 形、颜色、下划线、着重号、字号等组成了文字格式集合。在进行文本 分类时，取得文字的格式并按照格式集合的设定加以处理。文本的段落 格式用于文本结构的处理。 3 3 2 富文本的结构 3 3 2 1 富文本的物理结构和逻辑结构 文本的结构能有助于更好地理解文本的主题思想，了解文本所表达 第三章富文本分类研究 一种富文本分类方法的研究与实现 的内容及采用的方式。文本结构分析包括了文本的标题( t i t l e ) 、段落 ( p a r a g r a p h ) 、句子( s e n t e n c e ) 、词语( w o r d ) 以及文本区域( s e c t i o n ) 等层次( h i e r a r c h y ) 的识别与划分，文本标题与区域、段落、句子之间关 系的分析等方面【2 6 1 。 文本的物理结构包括标题、段落、句子和词语。文本的逻辑结构则 更侧重于表示文本所包含的思想内容和表达的逻辑方式，包括了主题、 区域、段落和正文。逻辑结构中的区域是一个或多个段落的组合，是作 者对内容在结构上有意识的安排；逻辑结构的段落是侧重于文本包含的 中心思想，而非仅仅指段落的位置和边界等信息。文本的逻辑结构直观 地表现为