（信号与信息处理专业论文）结合文本分类系统的aip平台的研究与实现.pdf

北京交通大学硕士学位论文 摘要 为了在残酷的市场竞争中胜出，对于一个企业来说，需要及时掌握 市场动态，随时了解竞争对手信息，准确把握行业发展趋势和国家最 新政策。据统计，目前随着互联网迅猛发展和高速普及，企业所需要的 信息9 0 可以在互联网上收集到。因此从i n t e r n e t 上获取信息是企业 很好的选择。问题是，如何把这些需要的信息提取出来? 目前基本上 是通过搜索引擎进行人工搜索。但对于需要获取大量、最新信息的企 业或团体用户来说，这种方式显然会耗费大量时间和精力，而且也难 保精确。因此，为他们提供一种新的从i n t e r n e t 上快速获取信息的方 式成为了迫切需要解决的问题。 本文设计并开发了结合文本自动分类系统的a i p 平台( a 1 1d a y i n f o r m a t i o np u r s u e ) ，即全天候信息跟踪平台。它作为关注多方面消 息的企业或团体查看i n t e r n e t 上新信息的一种解决方案，可为企业或 团体提供定制的，个性化的信息服务。论文给出了a i p 平台的设计和 具体实现方法，并演示了该平台。平台主要由以下模块组成：信息源 管理模块、链接提取模块、下载模块、查重上传模块、自动分类模块、 信息发布模块。 论文重点研究了a l p 平台的关键模块一文本自动分类模块。在网络 迅猛发展的今天，文本检索显得尤为重要。论文中给出了文本分类系 统具体的设计和实现方法，并演示了该系统。系统主要由分词模块、 特征提取模块和分类模块三部分组成。分词部分改进了中科院计算所 的i c t c l a s 分词软件。原来是只能每次处理单个的文件，改进后可以 对一个文件夹下所有的文件夹或者文件全部一次处理，大大提高了处 理效率。在搭好系统的的基础上，设计实验分析比较了多种特征提取 方法，具体包括信息增益( i g ) 、互信息( m i ) 、c h i 、领域词频( d w f ) 、 d f 和t f * i d f 方法，并总结实验结果，分析了各方法性能差异的原因， 最后将最优的t f * i d f 方法应用于系统中。 关键词：信息平台，文本检索，文本分类，分词，特征提取，r o c c h i o j ! 塞茎望盔堂竺主堂焦兰苎 a b s t r a c t f o ra l l e n t e r p r i s et o w i ni nt h em a r k e tc o m p e t i t i o n i t sn e e d e dt o a c q u i r ei n f o r m a t i o no f m a r k e tv a r i a t i o n ，r i v a la n dn e wc o l m t r yp o l i c i e sa t t i m e n o wn i n e t yp e r c e n to fi n f o r m a t i o nt h a te n t e r p r i s en e e d sc a nb eg o t f r o mi n t e r a c t s 0i t sag o o dc h o i c ef o rt b e mt oc o l l e c ti n f o r m a t i o nf r o m i n t e r n e t u s i n gs e a l c he n g i n ei so n ew a y f o ru st os e a r c hi n f o r m a t i o n ，b u ti t w i l lw a s t eal o to ft i m ea n de n e r g yo ni tf o rt h o s ee n t e r p r i s e sa n dg r o u p s i n t e r e s t e di nm a n ya s p e c t so fd a i l yn e w so i li n t e r a c t c o n s e q u e n t l y , i ti s b e c o m i n g a l lu r g e n tt a s kf o ru st od e v e l o pan e ws y s t e mf o rt h e m t os e w et h ep u r p o s eo f p r o v i n ge n t e r p r i s e sa n dg r o u p si n t e r e s t e di n m a n ya s p c o t so fd a i l yn e w so ni n t e r a c tw i t l li n f o r m a t i o nt h e yn e e d e d , t h i s s t u d yd e s i g n e da n dd e v e l o p e d a na p p l a t f o r m ( a l ld a y i n f o r m a t i o np u r s u e l c o m b i n e dw i n la l la u t o m a t i ct e x t c a t e g o r i z a t i o ns y s t e m t h ep l a t f o r m m a k e su pf o rs o m es h o r t c o m i n g so fs e a r c he n g i n e i tc a nd o w n l o a dn e w s f r o mi n t e m e ta n dd i s c a r di r r e l e v a n to n e sb ya u t o m a t i ct e x tc a t e g o r i z a t i o n w i t ht h i sp l a t f o r m ，u s e rc a nb r o w s en e w sb yt i m eo rc a t e g o r yw h i l es h a r i n g o rr e c o m m e n d i n gt h e m b ym a r k i n g t h i s s t u d y a l s of o c u s e do nt h ec o r em o d u l eo fa l pp l a t f o r m - t h e a u t o m a t i ct e x tc a t e g o r i z a t i o nm o d u l e w i t ht h er a p i d l yd e v e l o p m e n to f i n t e r n e t ，t e x tr e t r i e v a lb e c o m e sm o r ea n dm o r ei m p o r t a n t a sam e a n so f t e x tr e t r i e v a l t e x tc a t e g o r i z a t i o np l a y sa ni m p o r t a n tp a r ti ni t 强f st e x t c a t e g o r i z a t i o ns y s t e m c o n s i s t st h r e e p a r t s ：w o r ds e g m e n t a t i o n ，f e a t u r e e x t r a c t i o na n dt e x t c a t e g o r i z a t i o n t h ep e r f o r m a n c e o fs e v e r a lf e a t u r e e x t r a c t i o ni n c l u d i n gi gm i ，c m ，d w ed fa n dt f + i d fw e r ec o m p a r e do n ar o c c h i oc a t e g o r i z a t i o ns y s t e m a tt h el a s to ft h i st h e s i s ，w e g a v e t h e d e s i g n a n dd e t a i lo f i m p l e m e n t i n gm e t h o d so f a i pp l a t f o r ma n ds h o w e dt h ei n t e r f a c eo ft h i s p l a t f o r m k e y w o r d s ：i n f o r m a t i o np l a t f o r m ，t e x tr e t r i e v a l ，t e x tc a t e g o r i z a t i o n ，w o r d s e g m e n t a t i o n ，f e a t u r ee x t r a c t i o n ，r o c c h i o 独创性声明 y 7 4 1 5 7 8 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成果。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北 京交通大学或其他教学机构的学位或证书而使用过的 材料。与我一起工作的同志对本研究所做的任何贡献已 在论文中作了明确的说明并表示了谢意。 本人签名： 日期：2 堕年立月卫日 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论 文的规定，即：学校有权保留送交论文的复印件，允许 论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学计算机与信息技 术学院所有。未经许可，任何单位和个人不得拷贝。版 权所有，违者必究。 本人签名： 日期：丝年上月韭日 第一章绪论 1 1 文本分类研究的背景和意义 i i 1 文本分类的概念和研究背景 在网络迅猛发展的今天，文本检索显得尤为重要，从基于关键字 的全文检索到基于自然语言处理的知识检索，对文本检索的研究正在 一步步走向深入。文本分类作为文本检索的重要手段，在文本检索中 起着重要的作用。国际上文本信息检索的发展始于二十世纪五十年代 4 ，中文文本信息检索最早见于7 4 8 工程中的汉字情报检索 5 。8 0 年代中期后，由于计算机处理能力的大大提高和应用的普及化，中文 文本信息检索的研究开始进入黄金期，各种汉字文本索引方法、检索 方法以及实用化系统开始出现，各种全文检索商用系统的出现就是这 个阶段的成果。经过l o 多年的发展，中文文本( 基于关键字) 的全文 检索技术已经完全成熟。在检索系统性能的评价方面，美国技术和标 准研究所主办了t r e c ( t e x tr e t r i e v a lc o n f e r e n c e ) 文本检索会议，旨 在建立一套评价文本检索技术和系统的标准。它的最大特点是通过提 供大规模训练语料和统一评测方法来支持i r 技术的研发。会议对包括 中文、日文在内的多种文档库开展了i r 评测。t r e c 为文本检索的发展 起到了巨大的推动作用。 文本分类就是将给定的若干文档划分到若干个类别中。这里的文 档主要指以文本为主题的文件，如新闻、记叙文、说明文、议论文等 以自然语言为主的文章，不包括诸如声音、图像以及图画等文件。同 北京交通大学硕士学位论文 时我们也主要指文本自动分类，不讨论人工分类。 1 文本分类是文本挖掘的一种。文本挖掘可以简单定义为：从大量 的非结构化的文本文档集中提取感兴趣的、非平凡( n o n t r i v i a l ) 的 模式或知识。 2 文本挖掘的主要任务是分析文档集的内容，发现文档 集中概念、文档之间的相互关系和相互作用，为用户提供相关知识和 信息。文本挖掘对信息表示更加准确，通常使用词和短语表示文本的 概念内容。文本挖掘不仅能够区分不同的概念，还能够分析不同概念 节点之间的相互关联关系。文本挖掘的基础是文本的概念集合，概念 通常由重要词语和短语表示。文本中短语获取的基础是词法、句法及 语义分析，因此自然语言处理称为文本挖掘处理的基础。 国际上，文本挖掘是一个非常活跃的研究领域。在美国，以文本 挖掘为主体的m c u ( m e s s a g eu n d e r s t a n d i n gc o n f e r e n c e ) 会议从1 9 8 7 年连续召开，对英语语料的处理已形成一套评测规范。一些情报部门 已经在利用文本挖掘系统来搜集特定方面的情报，一些公司已在吸收 文本挖掘的技术成果，以此为基础来构造提供知识检索服务的系统。 代表性的产品：i b m 的文本智能挖掘机和a u t o n o m y 的c o n c e p ta g e n t s 。 但是，由于汉语自然语言理解的困难和以往这方面科技投入的不足， 面向中文语料的文本挖掘目前还没有像样的系统。国内在中文文本挖 掘与知识检索方面有一定研究基础的有国家智能中心、复旦大学、微 电子发展中心等。中科院计算所软件研究室的主要成果有智多星中文 文本分类器( 采用聚类粒度原理的v s m 分类方法、距离中心分类方法) ， 分类体系采用中图的分类体系。t r s 中文知识管理工具包：实用化中 文文本挖掘产品，包括的构件有：文本分类、文本摘要、文本聚类、 文本相似性检索引擎等。 绪论 i i 2 文本分类的应用 我们每个人都已深切感受到信息爆炸的冲击波，特别是近年来 i n t e r n e t 的迅猛发展，将我们置身在信息的汪洋大海中，我们不再有 信息缺乏的饥饿感，而是忧心忡忡于如何消化吸收如此庞大的海量信 息。人工分类面对海量数据往往会赶到力不从心，文本自动分类是处 理海量信息的一项关键技术。一方面它是信息管理的得力助手，另一 方面它也是我们搜索信息的重要手段。文本分类可具体应用于 1 ： 1 ) 为信息检索服务：信息检索系统必需操纵大量的数据，其文本 信息库可能是相当庞大的，同时用来表示文本内容的词汇数量又是成 千上万的。通过文本分类系统对文本集进行有序地组织，把相似的、 相关的文本组织在一起，为信息检索提供了更高效的搜索策略和更准 确的查询结果。 2 ) 邮件分类：对用户收到的电子邮件进行分类。例如：麻省理工 学院为白宫开发的邮件分类系统能准确的确定每天发送给总统的大量 的电子邮件所属的类别，如外交、税收、环保、家居等，以安排适当 的人员对信件内容进行答复。 3 ) 网络论坛和电子会议：网络论坛( 包括b b s 、n e w s g r o u p 等) 是在网络上进行信息交流的重要形式，文档分类系统能够将用户发表 的信息进行聚类和组织，以便于用户查找和阅读；电子会议是一种新 型的会议方式，所有与会者通过网络电脑系统举行会议，与会者是匿 名的，便于形成平等的气氛，以调动与会者的积极性，因此能产生大 量的意见和建议，分类系统对这些意见进行聚类和组织以确定进一步 的讨论的主题。 4 ) 文本信息过滤：利用文档分类技术，可以对网络中传输的内容 北京交通大学硕士学位论文 进行识别，滤除那些垃圾信息和非法信息。 5 ) 信息分发：在许多推送( p u s h ) 系统中，需要根据用户需求定 期发送信息，文档分类系统可以自动判别信息内容，将包含用户需求 内容的信息发送给相应的用户。 本文针对文本分类系统在信息检索领域的应用，结合实际情况提 出了一个结合了文本分类系统的可以获取信息的平台- - a i p 平台。 1 。2 a l p 平台介绍 a i p ( a l ld a yi n f o r m a t i o np u r s u e ) 平台，即全天候信息跟踪平 台，它是基于互联网的，全面且及时的，自动化、智能化企业竞争情 报系统解决方案。通过将网上信息下载和信息分类技术结合，为各行 业，各企业量身定做信息系统。 1 2 1 背景 为了在残酷的市场竞争中胜出，对于个企业来说，需要及时掌 握市场动态，随时了解竞争对手信息，准确把握行业发展趋势和国家 最新政策。要达到企业获取信息的目的，有两种途径，一种是从报纸 杂志获取，另一种是从i n t e r n e t 上获取。从报纸杂志中获取信息，显 然来源大大受限，难以及时反映最新信息，而且要耗费大量精力去翻 阅各种杂志。在目前，随着互联网迅猛发展和高速普及，网络上的信 息呈几何级数爆炸性增长，越来越多的企业所关心的竞争情报正在源 源不断的向互联网上转移。根据统计，当前企业所需要的信息9 0 可以 在互联网上收集到。因此从i n t e r n e t 上获取信息是企业很好的选择。 i n t e r n e t 上浩如烟海的信息中的确藏有我们需要的信息，现在问 题是，如何把这些需要的信息提取出来? 目前的途径有种，就是通 过搜索引擎进行人工搜索。搜索引擎的出现的确为人们打开了一扇获 取网上信息的窗户，但对于需要获取大量、最新信息的企业或团体来 说，它仍然存在一些缺点： 3 。 1 通过关键字查询，查到的不相关文章很多，很难准确定位需要的文 章。这是因为汉语一词多义，在不同场合表示不同意思，因此通过关 键词不能完全准确表达用户的真正意思。 2 找出最新信息困难。因为搜索引擎都是将它认为比较重要的排在前 面，而不是按照时间，因此不是每天更新的内容都会在最上面。 3 企业或团体内一人的搜索结果不便为内部其余人共享。当某人发现 一篇大家都值得看的文章，只能通过保存再发邮件或别的方式。在文 章多的情况下，这样工作量大，也很可能造成重复。 4 关注多个方面的信息需要多次输入不同的关键字。例如从汽车到手 机需要重新查询。如果关注的信息较多，会比较烦琐。 5 不便于对每次搜索的结果进行保存整理。 因此，人工搜索的方式显然会耗费了大量时间和精力，而且也难 保精确。针对这神情况，本文提出了结合网页自动分类系统的a i p 平 台( a l ld a yi n f o r m a t i o np u r s u e ) ，作为关注多方面消息的企业或团 体查看i n t e r n e t 上新信息的一种解决方案。它为企业或团体提供定制 的，个性化的信恳服务，提供企业所关心的竞争对手及经销商、代理 商、供货商、维修商等动态，以及国家相关的产业政策等重要信息。 1 2 2a i p 平台框架 a l p 平台由以下几个模块组成( 图卜2 1 ) ，各功能模块介绍如下 北京交通大学硕士学位论文 压困 一o = ，一 厢霸雨阿 理模块 n 甄j 丽1 、j 。_ _ 一 = ：。7 i 壁堡塑里塑堡i 图1 - 2 - 1 a i p 平台框架 1 信息源：用户指定的一些i n t e r n e t 首页网址，存储在数据库中。 首页包含有许多子链接，子链接对应的网页内容是用户需要阅读的新 闻内容，也是真正需要下载的。比如：如果你想知道有关汽车的消息， 你就要把h t l p ：a u t o s o h u c o r n ( 搜狐的汽车栏目) 等类似的网址添加到信 息源中。获取这些首页网址的方式有多种，可以凭我们对某些网站的 了解，直接添加，也可以通过搜索引擎找到介绍相关内容的网站，提 取相应的首页地址。 2 信息源管理模块：查询、添加、删除、编辑信息源。信息源是需要 维护的。当有新内容或原来内容有新来源等变更后，需要添加或删除。 3 链接提取模块：把网址首页中的链接地址，标题提取出来。分析网 页的源文件，“h r e f = ”是一个子链接的标志，其后有子链接的标题。 要提取出干净准确的链接地址和标题，还需要剔除多个表示字体，位 6 置等的控制字符。例如： 手机铃声歌星列表 。提取出链按地址：h t t d ：s a s s i n g c o m c n f o c u s l i s t h t m l ， 标题：手机铃声歌星列表。 4 查重上传模块：根据子链接地址，标题到数据库中去查询，如有相 同的，则表明数据库已经存储了此页，不需再下载，没有则需要下载。 5 下载模块：把子链接代表的网页下载到本地机器。 6 自动分类模块：根据下载下来的网页的内容用分类器进行分类。并 存储到数据库中。 7 数据库：存储分类后的网页内容及其相关信息， 8 信息发布模块：读取分类后的数据表中的信息，适当的进行人工修 改，按照客户的需求发布到i n t e r n e t 上，使客户可以通过浏览器阅读 发布后的信息。 9 u s e r ：客户通过浏览器可以选择类别查看该类别中的信息。首先阅 览该类所有网页的标题信息，选中标题后可查看网页内容。可以对标 题进行标注，推荐别人阅读此文。 与搜索引擎获取信息的方式相比，a i p 平台的好处在于： 1 集中了所有关注信息并已经分好类别，关心哪方面的内容直接查看 该类别即可。 2 用户可以通过按时间浏览，查看最新信息。 3 团体共享所有信息且通过标注可以把文章推荐给别人。 4 具有网页自动分类模块，采用的分类器经过语料库的训练，能够比 关键字更好的识别文章的语义，去除了不相关文章。 5 保留了过去的信息并对其中重要的进行了标记，需要时可以调出来 北京交通大学硕士学位论文 查看。 1 3 论文的研究的问题和主要工作 本文的重点是建立一个结合了文本分类系统的a i p 平台，并比较 各种特征提取方法在文本分类系统中的性能差异。针对所提出的问题， 本文主要做了如下的一些工作。 1 改进了中科院计算所的i c t c l a s 分词软件，使之符合文本分类 系统的需要。原来是只能每次处理单个的文件，改进后可以对 一个文件夹下所有的文件夹或者文件全部一次处理，提高了处 理效率。用改进后的分词软件处理了复旦大学的语料库( 中图 的3 8 类分类法) ，为下一步的特征提取和分类做好了准备。 2 设计并开发了一个文本分类系统。论文中给出了文本分类系统 具体的设计和实现方法，并演示了该系统。系统主要由分词模 块、特征提取模块和分类模块三部分组成。在搭好系统的的基 础上，设计实验分析比较了多种特征提取方法，具体包括信息 增益( i g ) 、互信息( m i ) 、c h i 、领域词频( d w f ) 、d f 和t f * i d f 方法，并总结实验结果，分析了各方法性能差异的原因，最后 将最优的t f * i d f 方法应用于系统中。 3 设计并开发了结合文本分类系统的h i p 平台，它能为企业或团 体提供定制的，个性化的信息服务。给出了该平台的具体设计 和实现方法，并演示了该平台。平台主要由以下模块组成：信 绪论 息源管理模块、链接提取模块、下载模块、查重上传模块、自 动分类模块、信息发布模块。数据库采用的是s q ls e r v e r 2 0 0 0 ， 编程语言为j a v a ，操作系统为w i n d o w s 2 0 0 0s e r v e r 。 1 4 论文的结构 第一章：绪论。介绍文本分类的背景和现实意义；然后阐述本文 设计开发a l p 平台的原因，提出平台的设计框架和其可以解决的问题； 最后，简述论文所做的工作和论文的结构。 第二章：基于向量空间的文本分类。介绍基于向量空间模型的文 本分类的一般步骤，包括分词，权重表示，特征提取，分类，阈值选 取。然后详细介绍了每个步骤的现有方法，各方法的性能比较以及目 前的难点。 第三章：文本分类系统。介绍本人设计开发的文本分类系统，详 细给出了设计模型和具体的实现方法；改进了中科院计算所的i c t c l a s 分词软件，使之符合文本分类系统的需要。在搭好系统的基础上，设 计实验比较了几种不同的特征提取算法i g 、m i 、c h i 、d w f 、d f 和t f * i d f 的性能；并总结实验结果，分析各方法性能差异的原因；最后，演示 了该系统。 第四章：a l p 平台。介绍了本人设计开发的结合了文本分类系统的 a l p 平台，包括其背景，功能，具体的设计和实现方法，并演示了该平 台。 第五章：总结。总结本论文的主要研究成果，提出有待研究的关 键技术问题，展望应用前景。 北京交通大学硕士学位论文 第二章基于向量空间模型的文本分类 文本分类系统采用的方法可以分为两大类：基于统计的方法和基 于知识工程的方法。由于基于知识工程的方法主要依赖语言学知识， 需要编制大量的推理规则，实现起来比较复杂。所以现在对文档分类 技术的研究主要偏重于统计学的方法。利用统计学方法实现文档分类 具有速度快、实现简单等特点，且分类准确度也较高，能够满足一般 应用的要求。文档分类技术根据有无监督又分为有监督分类和无监督 分类。有监督分类指在学习过程中指定了训练样本的所属类别，无监 督分类也叫聚类，预先没有给出所要划分的类别是什么。基于统计的 有监督的文本分类方法已有许多，具有代表性的有：贝叶斯模型、实 例映射模型、神经网络模型、决策树模型、支持向量机模型、最近邻 模型等。基于机器学习的文本分类方法都需要首先将文本抽象成特征 向量，实际上的文本分类也就是分类这些特征向量。 目前，在信息处理方向上，文本的表示主要采用向量空间模型 ( v s 4 ) 6 ，2 8 ，2 9 。向量空间模型的基本思想是以向量来表示文本： ( w i ，w 2 ，w 3 w n ) ，其中w i 为第i 个特征项的权重，描述文本时 最常用的特征是词，在不同领域中各种词的分布相差很大，所以我们 选择词作为特征来建立文本的特征向量。 文本分类体系，一般由人工构造，如政治、体育、军事，或者中 美关系、恐怖事件。分类系统可以是层次结构，如y a h o o 。分类模式有 两种，一种是两类问题，属于或不属于( b i n a r y ) ；另一种是多类问题， 多个类别( m u l t i c l a s s ) ，一个文本可以属于多类。典型的分类体系有 n e u t e r s 分类体系、中图3 8 类分类法( 见附录1 ) 。 o 基于向量空间模型的文本分类 2 1 文本分类的一般步骤 1 文本预处理 在文档分类前，首先要进行预处理。对于英文文档，需要作词干 提取；对于中文文档，需要分词。 2 特征项的提取 文本经过分词程序分词或词干提取后，首先去除停用词，合并数 字和人名等词汇，然后统计词频，最终表示成一个向量。 构成文本的词汇，数量是巨大的。所以，表示文本的向量空问的 维数也相当大，可以达到几万维。因此我要需要进行维数压缩的工作。 这样做的目的主要有两个：第一，提高程序的效率和运行速度；第二， 所有几万个词汇对文本分类的意义是不同的，通用的、各个类别都普 遍出现的词汇对分类的贡献小 为了提高分类精度，对于每一类，我 们应去除哪些表现力不强的词汇，筛选出针对该类的特征项集合。 3 选择分类算法( 缺乏算法特点分析) 最常见的基于机器学习的文本分类方法有：朴素贝叶斯( n a i v e b a y e s ) 方法、r o c c h i o 方法、k n n 近邻算法、支持向量机、决策树算 法、神经网络算法 1 2 、l l s f ( 线性最小二乘拟和) 1 4 、最大墒方 法 1 9 】 朴素贝叶斯( n a i v eb a y e s ) 方法算法的主要思想是基于贝叶斯假 设，即文档中的词汇在确定文本类别的作用上相互独立该算法的基 本思路是计算文本属于类别的概率，文本属于类别的几率等于文本中 每个词属于类别的几率的综合表达式。简单向量距离分类法的分类思 路十分简单，根据算术平均为每类文本集生成一个代表该类的中心向 量，然后在新文本来到时，确定新文本向量，计算该向量与每类中心 北京交通大学硕士学位论丈 向量间的距离( 相似度) ，最后判定文本属于与文本距离最近的类。k n n 近邻算法思路是，在给定新文本后，考虑在训练文本集中与该新文本 距离最近( 最相似) 的k 篇文本，根据这k 篇文本所属的类别判定 新文本所属的类别，支持向量机的募本思想是使用简单的线形分类器 划分样本空间。对于在当前特征空间中线形不可分的模式，则使用一 个核函数把样本映射到一个高维空间中，使得样本能够线形可分。其 鲁棒性好，避免了传统方法有时出现的灾难性失败。即使在训练样本 比较少的情况下，也能取得相当好的效果。神经网络算法采用感知算 法进行分类，在这种模型中，分类知识被隐式地存储在连接的权值上， 使用迭代算法来确定权值向量。当网络输出判别正确时，权值向量保 持不变，否则进行增加或降低的调整，因此也称为奖惩法。各算法的 性能比较如下： 2 1 s v m ，k n n l l s f n n e t ”n b 4 阈值的确定 上述算法都将新文本归于分类体系的一个类，即与该文本关联最 大的类。而事实上，分类体系中的类别不是完全互斥的，存在这样一 个既属于其中一个类别，又同时属于其他类别的文本。因此，对于这 类文本需要对每个类别确定阈值，当文本在该类的闽值之上时，就将 文本归于该类中。 下面对每个步骤进行详细介绍。 2 2 中文分词 词是最小的、能独立活动的、有意义的语言成分。切词以后在词 的层面上做转换或识别，处理豹确定性就大大提高了。如信息检索，如 果不切词( 按字检索) ，当检索德国货币单位”马克”时，就会把”马克思 基于向量空闻模型的文本分类 ”检索出来，而检索”华人”时会把”中华人民共和国”检索出来。如果进 行切词，就会大大提高检索的准确率。在更高一级的文本处理中，例如 句法分析、语句理解、自动文摘、自动分类和机器翻译等，更是少不 了词的详细信息。 7 2 2 1 现有中文分词算法 现有的分词算法可分为三大类：基于字符串匹配的分词方法、基 于理解的分词方法和基于统计的分词方法。 l 、基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的 汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找 到某个字符串，则匹配成功( 识别出一个词) 。按照扫描方向的不同， 串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹 配的情况，可以分为最大( 最长) 匹配和最小( 最短) 匹配；按照是 否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相 结合的一体化方法。常用的几种机械分词方法 8 ，9 如下： 1 ) 正向最大匹配法( 由左到右的方向) ； 2 ) 逆向最大匹配法( 由右到左的方向) ： 3 ) 最少切分( 使每一句中切出的词数最小) 。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方 法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词 的特点，正向最小匹配和逆向最小匹配一般很少使用。般说来，逆 向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结 果表明，单纯使用正向最大匹配的错误率为1 1 6 9 ，单纯使用逆向最大 北京交通大学硕士学位论文 匹配的错误率为1 2 4 5 1 0 。但这种精度还远远不能满足实际的需要。 实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过 利用各种其它的语言信息来进一步提高切分的准确率。机械分词方法 指的是主要依据分词词典信息，而不使用规则知识和统计信息，以字 符串匹配的原理进行分词的方法。 一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待 分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断 点，可将原字符串分为较小的串再来进机械分词，从而减少匹配的错 误率。另一种方法是将分词和词类标注结合起来，利用丰富的词类信 息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行 检验、调整，从而极大地提高切分的准确率。 2 、基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子盼理解，达到识剐词 的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句 法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系 统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统 可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断， 即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言 知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信 息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处 在试验阶段。 3 、基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字 同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现 的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现 t 4 基于向量空间模型的文本分类 的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字 的互现信息，计算两个汉字x 、y 的相邻共现概率。互现信息体现了汉 字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认 为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行 统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。 但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不 是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的” 等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词 系统都要使用一部基本的分词词典( 常用词词典) 进行串匹配分词， 同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来， 既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结 合上下文识别生词、自动消除歧义的优点。 7 到底哪种分词算法的准确度更高，目前并无定论。对于任何一个 成熟的分词系统来说，不可能单独依靠某一种算法来实现，都需要综 合不同的算法。据了解，海量科技的分词算法 3 6 就采用“复方分词 法”，所谓复方，相当于用中药中的复方概念，即用不同的药材综合起 来医治疾病，同样，对于中文词的识别，需要多种算法来处理不同的 问题。 2 2 2 分词中的难题 中文是一种十分复杂的语言，让计算机理解中文语言更是困难。 在中文分词过程中，有两大难题一直没有完全突破。 l 、歧义识别 北京交通大学硕士学位论文 歧义是指同样的一句话，可能有两种或者更多的切分方法。例如： 表面的，因为“表面”和“面的”都是词，那么这个短语就可以分成 “表面的”和“表面的”。这种称为交叉歧义。像这种交叉歧义十分 常见，前面举的“和服”的例子，其实就是因为交叉歧义引起的错误。 “化妆和服装”可以分成“化妆和服装”或者“化妆和服装”。由 于没有人的知识去理解，计算机很难知道到底哪个方案正确。 交叉歧义相对组合歧义来说是还算比较容易处理，组合歧义就必 需根据整个句子来判断了。例如，在句子“这个门把手坏了”中，“把 手”是个词，但在句子“请把手拿开”中，“把手”就不是一个词；在 句子“将军任命了一名中将”中，“中将”是个词，但在句子“产量三 年中将增长两倍”中，“中将”就不再是词。这些词计算机又如何去识 别? 如果交叉歧义和组合歧义计算机都能解决的话，在歧义中还有一 个难题，是真歧义。真歧义意思是给出一句话，由人去判断也不知道 哪个应该是词，哪个应该不是词。例如：“乒乓球拍卖完了”，可以切 分成“乒乓球拍卖完了”、也可切分成“乒乓球拍卖完了”，如 果没有上下文其他的句子，恐怕谁也不知道“拍卖”在这里算不算一 个词。 2 、新词识别 新词，也称为未登录词。就是那些在字典中都没有收录过，但又 确实能称为词的那些词。最典型的是人名，人可以很容易理解句子“王 军虎去广州了”中，“王军虎”是个词，因为是一个人的名字，但要是 让计算机去识别就困难了。如果把“王军虎”做为一个词收录到字典 中去，全世界有那么多名字，而且每时每刻都有新增的人名，收录这 些人名本身就是一项巨大的工程。即使这项工作可以完成，还是会存 基于向量空间模型的文本分类 在问题，例如：在句子“王军虎头虎脑的”中，“王军虎”还能不能算 词? 新词中除了人名外，还有机构名、地名、产品名、商标名、简称、 省略语等都是很难处理的问题，而且这些又是人们经常使用的词。目 前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。 2 3 特征权重的表示 建立特征向量必须要考虑的一个问题是如何计算特征向量的权 重，也就是如何选择向量权重算法的问题。算法有以下几种： 1 布尔权重 最简单的算法就是如果文本中包含某个词，那么这个词的权重就是 1 ，反之是o ： 驴锯搋三 z ， 其中，是词i 在文本k 中的权重， 是词i 在文本k 中的频率。 2 词频权重 直接采用词在文本中的频率作为其权重 口* = 厶 ( 2 - 2 ) 其中，是词i 在文本k 中的权重，五是词i 在文本k 中的频率。 3 t f 奉i d f 权重 2 2 前面的两种方法只考虑了词在文本中的频率，没有考虑其在整个训 北京交通大学硕士学位论文 练语料中的频率，这显然是不合理的：在所有文本中出现频率都很高 的词对于分类的重要性显然不及那些出现频率相对低一点但是主要分 布在一两个类别中的词。一般来说，一个词在训练语料中出现的次数 越少，那么对于分类来说，它应当越重要。这也是著名t f * i d f 特征权 重算法的主要理论根据。在该算法中，词权重与该词在文本中的频率 成正比，与其在整个训练语料中的权重成反比，表达式为： 口。：厶l 。g ( 翌) ( 2 3 ) h f 其中口。是词i 在文本k 中的权重，厶是词i 在文本k 中的频率， 是训练语料中总的文本数，h ，是训练文本中包含词i 的文本数。 4 t f c 权重 r f * i d f 权重没有考虑不同的文本长度对词权重的影响。t f c 权重算 法 2 8 与t f * i d f 权重算法的唯一不同在于前者对于文本长度进行了归 一化处理。表达式如下： 一 厶+ l 。甙翌) 2 ( 2 4 ) 其中是词i 在文本k 中权重，厶是词i 在文本k 中频率，n 是 训练语料中总的文本数，珥是训练语料中包含词i 的文本数，吖是训练 语料中总词数。 5 i t c 权重 1 8 蔚 基于向量空问模型的文本分类 i t c 权重与t f c 权重的不同在于使用词频的l o g 值代替了词频，从 而减少了词频对权重的影响。 l 。g ( + 1 + o ) - 1 。g ( 丝) 刀 周画面硐 ( 2 - 5 ) 其中是词i 在文本k 中的权重， 是词i 在文本k 中的频率， n 是训练语料中的文本数，是训练语料中包含词i 的文本数，m 是训 练语料中的总词数。 6 熵权重 3 5 熵权重是建立在信息论基础上的，是一种比较复杂的权重算法。 其表达式为： 札瓤扎妒( + 去姜降l o g ( 鲁， e ， 其中是词i 在文本k 中的权重，厶是词i 在文本k 中的频率， n 是训练语料中的文本数，甩，是训练语料中包含词i 的文本数。 7 t f * i w f 权重 在t f * i b f 算法的基础上，1 9 9 9 年r o b e r t ob a s i l i 提出t f * i w f ( i n v e r s ew o r df r e q u e n c y ) 权重算法，两者的不同主要体现在两个 方面：一、t f * i w f 算法中用词频倒数的对数值i w f 代替i d f ：二、t f * d v f 算法中采用了i w f 的平方，而不是象i d f 中采用的是一次方。r o b e r i o b a s i l i 认为i d f 的一次方给了词频太多的倚重，所以用i w f 的平方来 北京交通大学硕士学位论文 平衡权重值对于词频的倚重 1 3 ，其表达式 n ( w j ) ( ) ( 2 7 ) 其中是词i 在文本k 中的权重，厶是词i 在文本k 中的频率， n ( w j ) 词j 在训练语料中出现的次数，m 是训练语料中总词数。 8 t f * i d f * d b v 算法【2 0 】 t f * i d f 权重算法中引入d b v 和听f 后，得到如下的表达式： ( 2 - 8 ) 其中口。是词i 在文本k 中的权重，n 是需要优化的t f 根次参数 厶是词i 在文本k 中的频率，n 是训练语料中总的文本数，h ，是训练 语料中包含词i 的文本数，岛是词i 在类j 中的概率，p ；是词i 在各 类中分布概率的平均值，m 是类的数目。 j 嘉c 岛一； 萎乃 这个数学表达式体现的是数据 分布的不均衡性，所以称作：d b v ( d i s _ b a l a n c e v a r i a b l e ) 考虑了 词在不同类别之间分布的差异性。 用叫弘代替t f 的原因是，在t f * i d f 中，采用词在某个文本中的 出现频率t f 表示该词的局部特性，但是我们知道如果词a 是词b 出现 频率的两倍，通常并不认为词a 对于该文本的重要性是词b 的两倍， 基于向量空间模型的文本分类 而是比两倍要小一些。很显然，如果直接采用t f ，就赋予了词频太高 的权重。为了减少计算词权重时对词频的倚重，我们用词频( t f ) 的n 次方根代替t f ，这样如果某文本中词a 的出现频率是词b 的两倍，在 其他条件相同的情况下，词a 对于该文本的重要性只是词b 出现频率 的0 2 倍。由于无法直接确定到底应当将对词频的倚重消弱到何种程 度，所以我们采用实验的方法，依次选取n 等于l 、2 、3 、4 ，结合分 类器对测试语料进行分类，根据分类结果找到最佳的n 值。 2 4 特征提取 构成文本的词汇，数量是相当大的，因此，表示文本的向量空间 的维数也相当大，可以达到几万维，因此我们需要进行维数压缩的工 作，这样做的目的主要有两个，第一，为了提高程序的效率，提高运 行速度，第二，所有几万个词汇对文本分类的意义是不同的，一些通 用的、各类别都普遍存在的词汇对分类的贡献小，在某特定类中出现 比重大而在其他类中出现比重小的词汇对文本分类的贡献大，为了提 高分类精度，对于每一类，我们应去