（计算机软件与理论专业论文）海洋文献分类中极小化标注问题的研究.pdf

海洋文献分类中极小化标注问题的研究事 摘要 高效率的进行海洋文献的分类对海洋科学研究具有重要意义。目前，解决此 问题较为成熟的技术是有监督的文本分类技术。但其往往存在人工标注量太大的 缺点；此外，有标注资源代价昂贵，而大量无标注资源没有加以利用。半监督机 器学习方法能根据少量有标注资源从大量无标注资源中获取有用信息，有效降低 人工标注量。因此，本文运用半监督机器学习方法进行海洋文献分类中的极小化 标注问题的研究。 本文从描述文本分类和机器学习的基本概念入手，对基于机器学习的文本分 类基础技术文本的表示、分类方法和效果评估三部分内容逐一进行了讨论和 介绍，并根据已有实验结果选择了最佳的分类方法：接着通过对半监督机器学习 问题的描述，引出了本文所采用的核心算法一协同训练( c o t r a i n i n g ) 算法； 最后，使用酣n e t 语言编程实现了基于c o t r a i n i n g 算法的海洋文献分类极小化标 注，这是本文研究的核心问题。 本文的主要工作和创新点有： ( 1 ) 本文给出了基于协同训练算法的海洋文献分类的详细流程，详细设计 了六大功能模块，包括文本预处理、特征分割、训练、预测、挑选特征和评估模 块。其中，特征分割模块是c o - t r a i n i n g 方法区别于传统的有监督分类方法的标志 性模块，是本文所实现的分类方法的重点部分。 ( 2 ) 采用给特征添加标签的方式，将特征分成两个v i e w ，从而训练两个不 同的分类模型，实现协同训练方法。又通过一系列的实验，确定了适当的协同训 练次数和缓冲区样本数，以使分类结果稳定且良好。 ( 3 ) 最后，将基于c o t r a i n i n g 的分类方法与有监督分类方法的效果做了对 比，实验结果表明，在有标注训练集仅包含2 篇文献的条件下，该方法最终的f l 值和错误率分别可达到8 5 8 8 和1 4 3 5 左右，分类性能上基本接近由1 5 0 0 多 篇有标注样本训练得到的有监督分类器( 9 0 2 0 和9 1 3 ) 。 本文得到：国家自然科学基金项目( s o 6 0 6 0 2 0 1 7 ，2 0 0 7 卜2 0 0 9 1 2 ) 和山东省优秀中青年科学家科研奖励 基金( 2 0 0 8 b s 0 1 0 0 3 ，2 0 0 8 1 2 - 2 0 1 0 1 2 ) 资助 这说明将c o t r a i n i n g 方法应用于海洋文献分类可以大大减小人工标注量，并 有着较为良好的分类性能，从而实现海洋文献分类的极小化标注。 关键词：海洋文献；文本分类；机器学习；半监督学习；协同训练 t h er e s e a r c ho fminim u ml a b eip r o ble minm a rir e lit e r a t u r ecla s sific a tio n # a b s t r a c t i ti si m p o r t a n tf o r t h er e s e a r c ho fm a r i n es u b j e c t st oc l a s s i f yt h em a r i n el i t e r a t u r e e f f i c i e n t l y a tp r e s e n t ，t e x tc a t e g o r i z a t i o nb a s e do ns u p e r v i s e dl e a r n i n gi s am a t u r e t e c h n o l o g yt os o l v et h ep r o b l e m b u ts u p e r v i s e dl e a r n i n ga l w a y sn e e d st o om u c h l a b e l i n gw o r k ；m o r e o v e r , l a b e l e dr e s o u r c ec o s tal o t ，a n dl a r g en u m b e r s o fu n l a b e l e d r e s o u r c ei sn o ti nu s e s e m i s u p e r v i s e dm a c h i n el e a r n i n gc a nm a k eu s eo fal i t t l e l a b e l e dr e s o u r c et oo b t a i nu s e f u li n f o r m a t i o nf r o mn u m b e r so fu n l a b e l e dr e s o u r c e ，s o i tc a nr e d u c et h em a n u a ll a b e l i n gw o r k t h u s ，t h i st h e s i st a k e sa d v a n t a g eo f s e m i - s u p e r v i s e dm a c h i n el e a r n i n gt os t u d yt h em i n i m u ml a b e lp r o b l e mi n m a r i n e l i t e r a t u r ec l a s s i f i c a t i o n t h i st h e s i ss t a r t sw i t hd e s c r i b i n gt h eb a s i cc o n c e p t i o n so ft e x tc a t e g o r i z a t i o na n d m a c h i n el e a r n i n g ，a n dt h e ni ti n t r o d u c e st h et h r e eb a s i ct e c h n o l o g i e so ft e x t c a t e g o r i z a t i o nb a s e do nm a c h i n el e a r n i n go n eb yo n e a n d i ts e l e c t st h em o s ts u i t a b l e c l a s s i f i c a t i o na l g o r i t h mb a s e do nt h er e s u l to fa l g o r i t h m c o m p a r i n ge x p e r i m e n t s a n d t h e n ，t h i st h e s i sd e s c r i b e st h es e m i - s u p e r v i s e dm a c h i n el e a r n i n gp r o b l e m ，s e q u e n t i a l l y i ti n t r o d u c e st h ec o r ea l g o r i t h mo ft h i st h e s i s c o t r a i n i n g f i n a l l y , t h i st h e s i s r e a l i z e st h em i n i m u ml a b e lo fm a r i n el i t e r a t u r ec l a s s i f i c a t i o nb a s e do nc o t r a i n i n g w i t hc 挣n e tp r o g r a m m i n g t h em a i nw o r ka n di n n o v a t i o no ft h i st h e s i sa r ea sf o l l o w s ： ( 1 ) t h i st h e s i sp r e s e n t st h ep a r t i c u l a rf l o wo fm a r i n el i t e r a t u r ec l a s s i f i c a t i o n b a s e do nc o - t r a i n i n g i ta l s od e s i g n ss i xf u n c t i o nm o d u l e t e x tp r e t r e a t m e n t , f e a t u r es p l i t i n g ，t r a i n ，p r e d i c t , f e a t u r es e l e c t i o na n ge v a l u a t i o n t h ef e a t u r es p l i t i n g m o d u l ei st h ed i s t i n c tm o d u l ef o rt h ec o - t r a i n i n ga l g o r i t h m ，i ti st h ek e yp a r to ft h i s t h e s i s sw o r k ”t i f f st h e s i si ss u p p o r t e db yn a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o no fc h i n a ( n o 6 0 6 0 2 0 1 7 , 2 0 0 7 1 2 0 0 9 1 2 ) a n d r e s e a r c ha w a r df o u n d a t i o no fs h a n d o n gp r o v i n c ef o rm i d d l e - a g e da n dy o u n gs d e n t i s t s ( n o 2 0 0 8 b s 0 1 0 0 3 ， 2 0 0 8 1 2 2 0 1 0 1 2 ) i i i ( 2 ) t h i st h e s i ss p l i t st h ef e a t u r e si n t ot w ov i e w sb ya d d i n ge a c hf e a t u r eat a g t h e ni tt r a i n st w od i f f e r e n tc l a s s i f i e r sf r o mt w ov i e w s a n dt h e ni tc o n f i r m st h e c o t r a i n i n gi t e r a t i o n sa n dt h ep r o p e rn u m b e ro fs a m p l e si nt h ep o o lb yas e r i e so f e x p e r i m e n t ss ot h a ti tc a nm a k et h ec l a s s i f i c a t i o ne f f e c t sw e l l ( 3 ) a tl a s t ，i tc o m p a r e st h ee f f e c t so fc o - t r a i n i n ga n ds u p e r v i s e dl e a r n i n g e x p e r i m e n t ss h o w st h a te v e ni ft h e r ea r eo n l y2l a b e l e ds a m p l e si nt h et r a i n i n gs e t ，t h e f 1v a l u ea n de r r o rr a t eo ft h ec l a s s i f i c a t i o ns y s t e mc o u l dr e a c ha b o u t8 5 8 8 a n d 1 4 3 5 t h e ya r ec l o s et ot h ep e r f o r m a n c eo fs u p e r v i s e dc l a s s i f i e r ( 9 0 2 0 a n d 9 1 3 ) w h i c hi st r a i n e db ym o r et h a n1 5 0 0l a b e l e ds a m p l e s t h e s es h o wt h a tt h ea p p l i c a t i o no fc o t r a i n i n go nm a r i n el i t e r a t u r ec l a s s i f i c a t i o n c a ns i g n i f i c a n t l yr e d u c et h em a n u a lw o r k ，a n da l s oh a sw e l lp e r f o r m a n c e t h u s ，i ti s v e r ys u i t a b l ef o rp r a c t i c a la p p l i c a t i o n s k e y w o r d s ：m a r i n el i t e r a t u r e ；t e x tc a t e g o r i z a t i o n ；m a c h i n el e a r n i n g ；s e m i - s u p e r v i s e d l e a r n i n g ；c o - t r a i n i n g i v 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 ( 蕉；垫遗查墓丝盂墓缱剔直塑笪：奎拦卫窒2 或其他教育机构的学位或证书使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名：薹痂疡签字日期：加。夕年多月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：如口夕年占月7 日 导师签字： 乏裎k 签字日期：，年耵日 海洋文献分类中极小化标注问题的研究 1 引言 1 1 课题提出 2 1 世纪是海洋的世纪。世界各国正抓紧制定海洋发展策略，以海洋科学技 术为海洋学发展的龙头，刺激、带动整个海洋事业的发展，并以此来解决人类面 临的巨大的人口、资源和环境压力，以及全球变暖、厄尔尼诺等世界性问题带来 的困扰。因此，海洋科技已进入全球科技竞争的前沿。海洋科技进步已经成为衡 量国家科技总体水平和海洋强国的重要指标。 随着海洋科学技术的迅速发展，海洋学逐渐成为一个庞大的学科群，各学科 之间的交叉性和综合性明显加强。于是，海洋文献的数量也与日俱增。举例来说， 仅国际著名的s c i e n c ec i t a t i o ni n d e xe x p a n d e d ) ) ( 简称s c i e ) 数据库数据统计结 果就表明，1 9 9 6 2 0 0 5 年，1 4 9 个国家和地区被s c i e 收录的科学论文总数为1 0 1 9 80 6 3 篇，其中海洋论文就达到1 3 83 3 6 篇【l 】o 对于海洋学科研究人员来说，对海 洋文献进行人工标注是十分繁琐而缓慢的劳动，分类效率的低下使得目前海洋文 献利用率普遍不高。据统计，海洋学科研究人员在进行科学研究过程中至少要花 4 0 6 0 的时间去筛选获取信息【1 】。 因此，如何高效率的进行对海洋文献的分类，尽可能的减少费时费力的人工 劳动，已经成为海洋学科研究工作中需要迫切解决的问题。 1 2 研究背景及现状分析 1 2 1 解决文本分类问题的基本方法 海洋文献的分类属于文本分类问题。文本分类是文本自动分类( a t c ： a u t o m a t e dt e x tc l a s s i f i c a t i o n ) 的简称，是指用计算机程序自动确定特定文档与预 先规定的类别之间的隶属关系【2 】。例如，让程序自动指定一篇文本是属于海洋类 别，还是属于法律类别，或者是文学类别等预先规定好的一个或多个类别。 解决文本分类问题的方法主要有三种。第一种是最直观的方法，即简单的匹 配。如果一个文本中某个类别词出现的次数较多，那么就认为这个文本属于该类 海洋文献分类中极小化标注问题的研究 别。这种方法较为粗糙，因为往往类别词并不一定会频繁的出现在属于这个类别 的文本中。比如说医学类别的文献可能很少出现“医学”这个词。于是，对第一 种方法进行改进和发展，便产生了第二种方法，即统计某个类别中专家认为可能 出现的所有词汇，如果某个文本中这些词出现的次数多，则认为该文本属于这个 类别。这是一种基于规则和专家系统的方法，需要由专家来制定规则，制定的过 程十分复杂并且容易出错，成本比较昂贵。第三种方法是自2 0 世纪9 0 年代起逐 渐成熟的基于统计机器学习的文本分类方法。它更注重分类器的模型自动挖掘和 生成及动态优化能力，在分类效果和灵活性上都比之前基于规则和专家系统的文 本分类模式有所突破，成为相关领域研究和应用的经典范例【3 1 。 1 2 2 利用无标注样本资源来改善学习性能的机器学习技术 机器学习的研究主旨是使用计算机模拟人类的学习活动，它是研究计算机识 别现有知识、获取新知识、不断改善性能和实现自身完善的方法【4 1 。传统的有监 督学习是最常用的学习策略，它让学习器对大量有标注的( 1 a b e l e d ) 训练样本进 行学习，从而建立分类模型用于预测无标注样本的类别【5 】。 随着数据获取和存储技术的飞速发展，搜集大量无标注的( u n l a b e l e d ) 样本 已变得相当容易，而获取大量有标注的样本则相对较为困难，因为获得这些有标 注样本可能需要耗费大量的人力物力。比如，将计算机用于辅助医学图像分析， 从医院可以获得大量的医学图像作为训练样本，但是如果要求医学专家把所有这 些图像中的病灶全部都标注出来，则往往是不现实的。实际上，在现实世界的问 题中往往存在着丰富的无标注样本，但有标注样本则比较少，特别是在一些网络 在线应用中，这一问题更加突出。例如，在进行网页推荐时，需要用户标注出他 感兴趣的网页有哪些，但很少会有用户愿意花大量的时间来提供标注，因此有标 注的网页样本的数量比较少。但是，在网络上存在着极其丰富的网页资源，它们 都可以当作无标注的资源来使用。 很明显，一方面，如果只使用少量的有标注样本，那么利用它们所训练出的 学习器通常是很难具有强泛化能力的；从另一方面来说，如果仅仅使用少量昂贵 的有标注样本而不利用大量廉价的无标注样本，则是对有标注数据资源的极大浪 费。所以，在有标注样本数量较少时，怎样利用大量的无标注样本来改善和提升 2 海洋文献分类中极小化标注问题的研究 学习性能已成为当前机器学习研究中最受关注的问题之一【5 j 。 目前，主要有三大类利用无标注样本来进行学习的主流学习技术【6 l ，即直 推学习( t r a n s d u c t i v el e a r n i n g ) 、半监督学习( s e m i s u p e r v i s e dl e a r n i n g ) 和主动学 习( a c t i v el e a r n i n g ) 。这三大类技术都是尝试利用大量的无标注样本来辅助对少 量有标注样本进行学习，但它们的基本思想却有明显的不同。在半监督学习t 7 1 t 8 l 中，学习器尝试自行利用无标注样本，即整个学习过程不需人工干预，仅基于学 习器自身对无标注样本进行利用。与半监督学习的相似，直推学习【9 j 【1 0 】也是由学 习器自行利用无标注样本，但不同的是，直推学习假定无标注样本就是测试样本， 即学习的目的就是在这些无标注样本上取得最佳泛化能力。换句话说，半监督学 习考虑的是一个“开放世界”，即在进行学习时并不知道要预测的样本是什么，而 直推学习考虑的则是一个“封闭世界”，在学习时已经知道了需要预测哪些样本。 主动学习1 1 1 1 【1 2 1 【1 3 l 假设学习器对环境有一定的控制能力，可以主动地向学习器之 外的某个“神谕”f o r a c l e ) 1 进行查询来获得训练样本的标注。因此，在主动学习中， 学习器自行挑选出一些无标注样本并通过神谕查询获得这些样本的标注，然后再 将这些有标注样本作为训练样本来进行常规的有监督学习，而其技术难点则在于 如何使用尽可能少的查询来获得强泛化能力。 对比半监督学习、直推学习和主动学习这三者可以看出，后者在利用无标注 样本的过程中需要与外界进行交互，而前两者则完全依靠学习器自身，而且，半 监督学习比直推学习更加适合预测未知样本，更加贴近现实情况的需求。 1 3 本文所做的工作 1 3 1 研究目的 通过对研究现状的分析可以发现，半监督机器学习技术的特点十分适合用来 进行海洋文献的自动分类，减少人工标注量。因此，本文的研究目的主要就是研 究如何运用半监督机器学习方法，同时结合自然语言处理( n a t u r a ll a n g u a g e p r o c e s s i n g ，简称为n l p ) 技术，充分利用大量的无标注文本资源，尽可能的减少 1 这里的“神谕”可以是人，也可以是能够为样本提供真实标注的其他过程。 3 海洋文献分类中极小化标注问题的研究 海洋文献分类中的人工标注量，提高分类效率。 1 3 2 研究内容 本文的研究内容主要有以下两个方面： ( 一) 研究基于有监督机器学习的文本分类技术。参照已有实验对比分类方法 在海洋文献分类中的效果，选取效果最好的分类方法研究海洋文献分类的极小化 标注问题。 ( 二) 研究基于半监督机器学习的文本分类技术。使用c o t r a i n i n g 1 4 】算法构建 海洋文献分类系统，以减小手工标注量。并通过实验，探索在标注量极小化时， 该分类系统所能达到的性能。 1 4 本文的章节安排 下面的各个章节将就海洋文献分类中的极小化标注问题的各个方面依次展 开讨论。 第二章首先介绍文本分类和机器学习的基本概念和基本思想；然后从文本的 表示、分类方法和效果评估三个部分详细介绍基于机器学习的文本分类基础技 术；最后，参照已有的分类方法对比实验，选择最适合本文研究工作的分类方法。 第三章主要介绍半监督机器学习方法的基本理论和其种类，选择半监督学习 中的协同训练技术进行本文的研究：然后对协同训练技术的基本概念进行了介 绍，对其理论进行了分析，对其实际的应用情况也做了相应的介绍。 第四章是本文的核心章节，详细介绍了为实现海洋文献分类极小化标注而构 建的基于c o t r a i n i n g 的海洋文献分类系统的主要工作流程、功能模块的设计以及 所使用的分类工具的相关情况；然后，为了评估标注量极小化的情况下分类系统 的分类性能，设置了相应的实验，从协同训练次数和缓冲区样本数两个方面寻找 最优的配置，最后将使用半监督分类器在极小化标注条件下的分类效果与有监督 分类器的分类效果做了对比。 第五章是全文的总结与展望。总结了本文所做工作的成果与不足，分析展望 了下一步的工作方向和内容。 4 海洋文献分类中极小化标注问题的研究 2 基于机器学习的文本分类基本概述和基础技术 目前，解决文本分类问题的方法主要有两种：基于规则和专家系统的方法和 基于统计机器学习的方法。本文所采用的是基于统计机器学习的方法。 2 1 文本分类基本概述 2 1 1 文本分类问题的数学描述 基于机器学习的文本分类是一个有监督的学习过程。它通过一个事先标注好 类别的训练文本集合，学习得到文本特征和文本类别之间的关系模型；然后利用 这种关系模型将未知类别的文本文档分类到一个或多个预定义的类别中。顺便指 出，在本文的环境中对文本( t e x t ) 、文档( d o c u m e n t ) 、文献不加区别的使用。 一般的文本分类问题的数学描述如下： 假设有一个训练文档集合d = 盔，d ：，以 和预先定义的类别集合 c 一 c 1 ，c ：，c 。) ，文本分类就是将一个二元组( d ，q ) d c 映射到一个布尔值 的任务。如果文档d ，属于类别c i ，则二元组( d j ，c i ) 映射值为t ( t r u e ) ；否则映 射值为f ( f a l s e ) 【1 5 1 。 更形式化的说，训练文档集和类别集合满足一种映射关系，即：存在某个目 标函数妒： 妒：d x c - - r ，f ) ( 式2 - 1 ) 这个函数能够将任意一个文本准确地分类。通过学习训练文档集d ，可以找 到一个近似于的模型日： h ：d x c 呻 z ，f ) ( 式2 - 2 ) 一个分类系统的建立或者说分类学习的目的就是寻找一个和妒最相近似的 h ，即：给定一个评估函数e ，学习的目的应使得矽和日满足： 5 海洋文献分类中极小化标注问题的研究 叫；| ；薹e ( 盹q ) 一日( 刊) ) c 式2 - 3 ， 根据应用的需要可以给文本分类加以不同的约束。例如可能需要这样一个分 类器，对给定的整数冗( ，l 足) ，每个文档d ，e d 需要分类到c 中的靠个不同的类 别中。万= 1 时，即一个文档只能分给一个类别，这样的分类称为单类别分类， 而如果一个文档可以分给c 中的任意多个类别，这样的分类称为多类别分类。单 类别分类的一个特例就是二值分类，即对任意一个文档d ，e d 要么属于类别c i ， 要么不属于类别c ；，( 属于类别q 的补集i ) 1 6 1 。 2 1 2 机器学习概述 ( 一) 机器学习的一般概念 如果一个计算机针对某类任务t 的用p 衡量的性能根据经验e 来自我完善， 那么我们称这个计算机程序在从经验e 中学习，针对某类任务t ，它的性能用p 来衡量【1 7 1 。 实际的机器学习问题往往比较复杂，需要定义某类问题，之后探索解决这类 问题的方法，并理解学习问题的基本结构和过程。学习系统需要选择要学习的知 识的确切类型和对于这个目标知识的表示以及一种学习机制。可以认为学习智能 体包含决定采取什么动作的执行元件和修改执行元件使其能制定更好的决策的 学习元件。一个学习元件的设计受到下列三个因素的影响：将要学习的是执行元 件的哪个组成部分；对学习这些组成部分而言，可以得到什么反馈；最终部分是 如何表示的。 ( 二) 三种典型的机器学习方式【1 8 】 1 ) 增强机器学习 增强机器学习更加关注随时间变化数据的分析与建模，使用m a r k o v 与其他 非m a r k o v 方法，比如g a m et h e o r y 。 2 ) 符号机器学习 符号机器学习把目标泛化为数据描述( 符号数据分析) 。把一般规模的数据集 合变为具有上百个属性超过十万对象的数据集合。 6 海洋文献分类中极小化标注问题的研究 3 ) 统计机器学习 从神经网络的研究转变为统计机器学习与集成机器学习。强调学习算法不应 只解决玩具世界问题，已而从非线性算法转变为以线性算法为主。此外，必须考 虑学习算法泛化能力，即是对测试数据集的错误率要足够低。统计机器学习的理 论基础是对训练数据集合的错误率小不一定导致良好的泛化能力。泛化能力的研 究主要有：( 1 ) 以样本个数趋近无穷大来描述模型的泛化能力。泛化能力需要使 用世界w 来刻画( 而不是有限观测的样本集) 。( d u d a ) ( 2 ) 从“有限样本建立 模型，以估计其对世界为真的程度( v a p n i k ) 。进而发展成为v a p n i k 的有限样本 统计理论。这个统计理论是从“有限样本建立模型，以估计其对世界为真的程 度。其关键在于将泛化误差考虑为一个依赖从问题世界随机选择样本集的随机变 量。样本集和模型与误差之间的关系，即，需要确定模型泛化误差的界。研究泛 化误差界的目的，除了估计泛化能力之外，主要为了指导算法设计。 一般地说，有限样本归纳的模型与问题世界的统计分布有误差，即，存在损 失，或称存在风险。人们希望归纳的模型对问题世界有最小风险。如何描述风险， 如何从样本集估计这个风险，这就是泛化的统计问题。这是概率统计理论中的经 典问题。可以分为两类：基于先验知识的泛化理论：这需要先验地了解问题世界 的部分统计性质。基于数据的泛化估计：( 1 ) 以大数定理为基础( 无限样本卜 与d u d a 的观点对应1 1 9 】( 2 ) 以函数的划分能力为基础( 有限样本) 与v a p n i k 的观点对应。不同于以无穷样本为基础的统计理论，这个理论主要考虑在划分样 本空间的函数下，风险的下界。v a p n i k 在1 9 7 1 年奠定了有限样本的统计理论。 实际上，现在机器学习研究的热点领域是符号机器学习和统计机器学习，本 文采用的是统计机器学习的方法。 ( 三) 统计机器学习 1 ) 概述 给定样本集合“，y 。) ，纯，只) ，其中，毛。学习问题是从函数集 厂0 ，a ) la e a 中，选择一个最优函数f ( x ，口。) ，使得它是对x 与y 的最好的估 计。， ，口) 也可以称为一类基函数。对两类问题：y 一 0 ，1 ，此时称函数集合 厂g ，口) la e a 为指示函数集合。因为本文涉及的工作是有监督两类问题机器学 7 海洋文献分类中极小化标注问题的研究 习( 分类问题，或模式识别问题) ，而不是更一般的回归问题，这样，讨论将限制 在指示函数集合的划分问题上。指示函数集合 厂o ，口) ia e a 的v c 维，是能够 被集合中的函数以所有可能的种方式分为两类的向量五，x d 的最大数目。对 一个给定的指示函数集，它的v c 维说明了其划分样本的能力( 这个函数集的复 杂程度) 。它与本如何标定其类别无关。对线性指示函数集合，它能够打碎的样 本数为样本维数加1 ，这是线性指示函数集合的v c 维。频率( 经验风险) 到概率( 期 望风险) 一致收敛的条件是v c 维有限。v a p n i k 首先发现了对任何概率测度( 与分 布无关) 的e r m 原理一致的充要条件：如果指示函数集合q ( z ，口) 的v c 维是有限 的，经验风险将快速渐进收敛于期望风险。其中e r m 原理一致是指经验风险与 期望风险收敛到最小的风险值。假设指示函数集合满足一致性条件。期望风险与 经验风险满足下述不等式：r ( o t ) sr e m p ( c t ) + 中( 七d ) ，其中，r e m p ( a ) 是经验 风险，中( 尼d ) 称为置信范围。d 是指示函数集合的v c 维。为了获得最小的r ( a ) ( 期望风险) ，须使得r e m p ( a ) ( 经验风险) 与m ( 七d ) ( 置信范围) 同时最小。这就 是结构风险最小化原理。 1 9 8 4 年，v a l i a n t 提出了一种机器学习的理论p a c 。p a c 不求学习结果精确， 不求学习一定成功，学习结果除了有小的误差或失败可能，可以基本成功。但是， 学习必须在多项式时间内完成，这称为“概率、近似正确地可学习 ，p a c ( p r o b a b l y a p p r o x i m a t e l yc o r r e c t ) 。令f 是一个待学习的概念类，d 是一个确定但未知的样 集合s 的分布。对所有的分布d s ，所有概念，e f ，以及所有0 占，6s 1 ，算法 q 输出一个假设h ，使得误差率d ( h ( s ) ，( s ) ) s 至少以概率1 6 成立。将泛化 误差虑为一个依赖随机选择样本集s 的随机变量，因为s 与假设( 模型) 空间h 对 应，因此，这是一个依赖假设空间日的随机变量。这样，可以通过样本集合上 的随机变量研究泛化误差界。根据分布d ，随机选择的任一个样本集s ，假设， 船的泛化误差界头d e r r d ( h s ) s ，日，6 ) ，以概率1 6 成立。其中k 是s 中的样 本个数。 为了给出便于指导算法设计的泛化界，1 9 9 8 年，s h a w e - t a y l o r 使用类似的方 8 海洋文献分类中极小化标注问题的研究 法给出了最大边缘的泛化界。 e ，) s ( 式2 - 4 ) 这个不等式依赖于边缘y 。它给出了有几何直观的界描述，从而为算法设计 奠定基础。 2 1 3 基于机器学习的文本分类基础技术 基于机器学习文本分类的基础技术由文本的表示( r e p r e s e n t a t i o n ) 、分类方法 及效果( e f f e c t i v e n e s s ) 评估3 部分组成【划。 一般的文本分类系统的主要流程如下图： 图2 1 文本分类系统的工作流程【捌 从文本分类系统的处理流程来看，首先，要对用于训练的文本进行预处理， 使用自然语言处理技术，把文本表示成下一步进行分类计算所需要的向量形式， 并进行特征选择，去除无用的信息，减少后续步骤的复杂度和计算负担；然后， 第二步是采用一种或几种分类方法，结合这些代表训练文本的向量进行训练，得 到分类模型；第三步，对尚未分类的新文本也进行预处理，表示成向量形式，然 后用第二步已得到的分类模型对代表未分类文本的向量进行预测，得出分类结 果。至此，文本分类的过程已经完成。而分类效果好坏的评价将采用一定的方法 和指标，这将在随后的章节中介绍。 9 海洋文献分类中极小化标注问题的研究 2 2 文本的表示 2 2 1 概述 计算机并不具有人类的智能，人在阅读文章后，根据自身的理解能力可以产 生对文章内容的模糊认识，而计算机并不能轻易地“读懂”文章，从本质上说， 它只认识o 和1 ，所以，必须将文本转换为计算机可以识别的格式。现有的文本 分类技术的前提假设是特征和文档类别密切相关。在这一假设前提下，文本可以 在被提取特征后，使用文本表示模型来表示。目前的文本分类方法和系统大都以 词或词组作为文档的文本特征。 文本表示的主要工作包括三个方面，即：( 1 ) 文本的预处理和文本表示模型 的选取( 2 ) 特征降维( 3 ) 实际计算文本在这些特征上的值，从而将文本表示成 为向量。 2 2 2 文本的预处理和文本表示模型的选取 ( 一) 文本的预处理 文本预处理是指把文本转化为原始特征空间中元素的序列。对于不同语言书 写的文本，预处理过程和复杂程度不同。比如对于英语，预处理主要是去掉停用 词，还原词形为词干，得到“干净的文本。而对于中文，由于中文词语是连续 书写，词与词之间没有像英语那样的固定的间隔符( 空格) ，采用词语作为特征 项需要先从连续的文本中分离出一个个的词语来，所以预处理阶段的主要工作是 分词。目前，在中文信息处理领域，对中文自动分词研究的已经比较多，提出了 一些分词方法，如最大匹配法、逐词遍历匹配法、最小匹配法等。自动分词系统 是中文信息处理系统的一个重要组成部分，但分词本身并不是目的，而只是后续 过程的必备手段【2 1 1 。因此，在本文中对分词本身并没有作深入的研究探讨，而 是将已有的分词算法应用到文本分类系统当中。从算法的复杂性和时间复杂度方 面考虑，本文主要选用正向最大匹配算法来进行分词，据专家统计，此方法的错 误切分率为1 1 6 9 ，因此不会对分类效果产生明显的影响【2 2 1 。下面对正向最大匹 配算法进行简要介绍。 正向最大匹配法的基本思想是：( 1 ) 取待切分语句的1 1 1 个汉字作为匹配字段， 1 0 海洋文献分类中极小化标注问题的研究 其中m 为机器可读词典中最长词条的汉字个数；( 2 ) 查找机器可读词典并进行匹 配。若能匹配，则将这个匹配字段作为一个词切分出来；若不能匹配，则将这个 匹配字段的最后一个字去掉，剩下的字符串作为新的匹配字段，进行再次匹配。 重复以上过程，直到切分出所有词为止。目前常用的最大词语为成语( 除特殊领 域的特殊词汇) ，所以在正向最大匹配算法中设定最大匹配长度为4 。在分词前， 按照标点符号，将文本分成若干短句，然后对每个短旬使用正向最大匹配算法进 行分词。下面以“海洋文献元数据分类 这句话为例，详细介绍其分词过程，其 中表2 - 1 为分词所用的词典： 设定最大匹配长度m a x l e n g t h = 4 ； 字符串s = “海洋文献元数据分类 ； 字符串s ，= “； 表2 - 1 分词词典 分类 海洋 文献 元数据 分词具体步骤如下： 1 ) 是为空；墨不为空，从s 最左边取出最长子字符串w _ - “海洋文献 ； 2 ) 查词典，“海洋文献一词条不在词典中，于是将w 最右边一个字去掉， 得到w = “海洋文； 海洋文献分类中极小化标注问题的研究 3 ) 查词典，w 不在词典中，于是将w 最右边一个字去掉，得到w = “海洋”； 4 ) 查词典，w 在词典中，将w 加入到中，s 2 - “海洋 ；并将w 从s 中 去掉，此时s = “文献元数据分类 ； 5 ) 墨不为空，于是从墨最左边取出最长子串w = “文献元数 ； 6 ) 查词典，w 不在词典中，将w 最右边一个字去掉，得到w = “文献元 ； 7 ) 查词典，w 不在词典中，将w 最右边一个字去掉，得到w = “文献； 8 ) 查词典，w 在词典中，将w 加入到是中，是= “海洋文献 ；并将w 从s 中去掉，此时墨= “元数据分类； 9 ) 是为空；s 不为空，从s 最左边取出最长子串w = “元数据分”； 1 0 ) 查词典，w 不在词典中，将w 最右边一个字去掉，得到w = “元数据”； 1 1 ) 查词典，w 在词典中，将w 加入到s 中，s ，= “海洋文献元数据”； 并将w 从墨中去掉，此时s = “分类”； 1 2 ) 是为空；墨不为空，从s 最左边取出最长子串w = “分类”； 1 3 ) 查词典，w 在词典中，将w 加入到s ，中，s ，= “海洋文献元数据分 类”；并将w 从墨中去掉，此时s = “ ； 1 4 ) s 为空，输出s ：作为分词结果，至此分词过程结束。 ( 二) 文本表示模型 文本表示模型有多种，常用的有布尔模型、向量空间模型等。目前大多数分 类系统使用向量空间模型作为文本表示模型。 向量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) 2 3 】是由s a l t o n 等人在六十 年代末到七十年代初期提出的文本表示模型，近年来应用较多且效果好。v s m 的基本思想是将一篇文档表示为特征空间中的一个向量，这个向量也称为文档向 量。文档向量中每一维对应于文档中的一个特征，它的权值为该向量维对应的特 征在文档库中的权值。 常用的权重函数是t f i d f ( t e r mf r e q u e n c yi n v e r s ed o c u m e n tf r e q u e n c y ) ! 川。 海洋文献分类中极小化标注问题的研究 文本中某个特征项的权值的计算与下列因素有关：一个是特征项在该文本中出现 的频率，特征项出现的频率越高，则权重值越大；一个是特征项的文档频率，即 包含该特征项的文本的个数，含有特征项的文本数目越多，则该特征项越普通， 它对类别的区分作用越小，给它分配的权重也就越小。最后，考虑到文本的长短 不一，要将文本长度归一化，这样同一个特征项在不同长度的文本中的权重才具 有可比性。基于以上因素考虑，特征的权重函数经常采用如下方式计算： 驴：竺盟 。船5 ， 。- 了士r 一； l 氏z 。) ， 捌 t 一，l o g 旆_ _ n 丌 其中矿( q ，d f ) 表示特征皑在文本d f 中出现的频率，d f ( q ) 表示了特征q 的 文档频率，n 表示特征总数，表示了第_ 个文档矢量的第i 个特征的权值。 布尔模型可以看作是v s m 的一种特例，根据特征是否在文档中出现，特征 的权值只能取1 或0 ，即布尔权重。布尔权重是最简单的一种加权方法，公式如 下： 口甜；f l 矿( q ，d 抄o( 式2 - 6 ) 。0 ，矿( q ，d r ) ：o l 瓦 许多时候，使用二值特征的分类效果并不比考虑特征频率的差，所以，本文 采用布尔模型来表示文档。 2 2 3 特征降维 文本预处理完成后，文本成为了词语的序列。下面一步就是对这些序列的词 语空间进行降维，即减少要用来表示文本的特征词的数量，以降低计算的代价， 同时去掉对于表征文本特征不重要甚至起反作用的词，以提高整个分类的效果。 ( 一) 特征降维的作用 分类问题的最大特点和困难之一是特征空间的高维性和文档表示向量的稀 疏性。在中文文本分类中，通常采用词条作为最小的独立语义载体，原始的特征 空间由可能出现在文章中的全部词条构成。而中文的词条总数有十多万条，这样 高维的特征空间对于几乎所有的分类算法来说都偏大。所有的文本都要按这个特 海洋文献分类中极小化标注问题的研究 征空间来计算自己在其上的值，因此特征降维在计算上对降低计算代价有很重要 的作用。把文本转换为向量不仅针对训练文本集合中的文本，新到的文本也要首 先表示成向量，因此降低向量的维数不仅可以降低训练学习器整个过程的时间， 而且，也会缩短在具体判断新到文本属于类别的时间。有效降低计算代价对于实 际的工程和商业应用十分重要，这也成为推动文本分类在搜索引擎中应用的重要 因素。除了降低计算代价方面的作用以外，好的特征降维会有效去除噪音，使得 保留的特征能够更集中的体现文本的特征，从而提高分类的效果。总之，寻求一 种有效的特征抽取方法，降低特征空间的维数，提高分类的