（计算机科学与技术专业论文）基于遗传算法的web信息抽取技术.pdf

中文摘要 摘要 随着w e b 信息的迅速扩张，w e b 成为当今信息获取和发布的事实标准。为此 人们对信息抽取( i e ) 系统进行大量研究，以帮助用户在浩瀚如烟的w e b 上准确 有效地提取自己真正需要的信息。如今已出现大量的信息抽取系统，如w 4 f 、 r o a d r u n n e r 、w h i s k 、r a p i e r 、w i e n 等。它们在使用技术、自动化程度、适用 领域等方面都存在一定的差异性。 i e 系统中最重要的是抽取规则，它用来定位和识别待抽取的信息。w h i s k 系 统是一个半自动的i e 系统，对结构化、半结构化的w e b 文本它都能使用生成的抽 取规则进行信息抽取。但是它在规则学习过程中规则不能保证以最优的方式进行 扩展，且生成规则集的效率较低。针对以上问题，本文提出了利用遗传算法改进 w h i s k 的监督式学习算法，并采用移除法生成规则集。算法主要实现以下功能： 一、例子的预处理，包括例子去噪和例子标注；二、项的定义和转化；三、用遗 传算法扩展规则；四、用移除法生成规则集。 我们还实现了一个用于在线挖掘网站的w e b 信息抽取系统，应用检索规则探 查不同网站，使用抽取规则抽取浅层知识，再进行统计分析发现变化趋势。系统 主要提供以下功能：1 、根据检索规则自动下载并解析网页；2 、在用户的参与下， 提供图形用户界面定义单槽抽取规则或通过学习算法生成多槽抽取规则；3 、实现 批量任务的自动抽取并存储数据；4 、对抽取的历史数据，提供直观的图形显示统 计结果。 通过对多种类型的真实在线的网页进行实验分析，表明i e 系统有较好的通用 性；通过与w h i s k 系统的实验结果进行比较分析，表明利用遗传算法的规则学习 算法在效率和准确率上都有一定的提高。 关键词：w e b 信息抽取；抽取规则；遗传算法：归纳学习算法；w h i s k 系统 英文摘要 a b s t r a c t w i t ht h er a p i de x p a n s i o no fw e bi n f o r m a t i o n ，t o d a y sw e bh a sb e e nt h ed ef a c t o s t a n d a r df o rp u b l i s h i n ga n do b t a i n i n gi n f o r m a t i o n t h e r ei sam o u n to fw o r ko n i n f o r m a t i o ne x t r a c t i o n ( i e ) s y s t e m st oa i dp e o p l et oq u i c k l yg e tw h a tt h e yr e a l l yn e e d f r o mt h eh u g ew e b al o to fi es y s t e m sh a v eb e e ne m e r g e di nr e c e n ty e a r s ；g o o d e x a m p l e sa r ew 4 f ，r o a d r u n n e r ，w h i s k ，r a p i e r ，w i e na n ds oo n t h e s es y s t e m s d i f f e ri nt h et e c h n i q u et h e yu s e ，t h ed e g r e eo fa u t o m a t i o n ，a n dt h ea p p l i c a t i o nd o m a i n e x t r a c t i o nr u l e sa r et h em o s ti m p o r t a n tp a r to fi es y s t e m s ；t h e ya r ei ng e n e r a lu s e d t od e f i n eh o wt ol o c a t ea n di d e n t i f yt h ed a t au n d e re x t r a c t i o n w h i s ks y s t e mi sa s e m i a u t o m a t i ci es y s t e mf e a t u r e ds u p e r v i s e de x t r a c t i o nr u l el e a r n i n g i tw o r k sw e l li n e x t r a c t i n gi n f o r m a t i o nf o rs t r u c t u r e do rs e m i s t r u c t u r e dw e bt e x t s ，b u tt h e r ei sn o g u a r a n t e et h a tt h er u l el e a r n i n ga l g o r i t h mc a ne x t e n dr u l e si na l lo p t i m a lw a y a l s oi t t a k e st i m et og e n e r a t et h er u l es e t t os o l v et h e s ep r o b l e m s ，w ep r o p o s et ou s et h e g e n e t i ca l g o r i t h mt oi m p r o v et h ew h i s ka l g o r i t h mb yah e u r i s t i cr u l ee x p a n s i o n ，a n d t ou s ear e m o v i n gm e t h o dt og e n e r a t et h er u l es e t o u ra l g o r i t h mm a i n l yi m p l e m e n t s f u n c t i o n ss u c ha s ：1 p r e - p r o c e s s i n gt r a i n i n g e x a m p l e s ，i e r e m o v i n gn o i s ef r o m e x a m p l e sa n dl a b e l i n ge x a m p l e s ；2 d e f i n i t i o no ft e r m sa n dt h e i rt r a n s f o r m a t i o n ；3 e x t e n d i n gr u l e sw i t hg e n e t i ca l g o r i t h m ；4 g e n e r a t i n gr u l es e tw i t har e m o v i n gm e t h o d a l s ow ei m p l e m e n ta ni es y s t e mf o rm i n i n go n l i n ew e bs i t e s ；i te x p l o r e sv a r i o u s w e bs i t e sg u i d e db yr e t r i e v a lr u l e s ，e x t r a c t ss h a d o wk n o w l e d g eb yd e f i n e de x t r a c t i o n r u l e s ，a n dd o e ss t a t i s t i c a la n a l y s i st od i s c o v e rc h a n g et r e n d so fw e bd a t a o u rs y s t e m m a i n l yp r o v i d e sf u n c t i o n sl i k e ：1 p e r i o d i c a l l yd o w n l o a d i n ga n dp a r s i n gw e bp a g e s ；2 d e f i n i t i o no fo n e - s l o tr u l e st h r o u g hu s e ri n t e r a c t i o nw i t hag r a p h i c a lu s e ri n t e r f a c e ，a n d g e n e r a t i o no fm u l t i s l o tr u l e sb yal e a r n i n ga l g o r i t h m ；3 d a t ae x t r a c t i o na n ds t o r ei na b a t c hm o d e ；4 s t a t i s t i c a la n a l y s i sa n dg r a p h i c a lr e p r e s e n t a t i o nh i s t o r i c a le x t r a c t e dd a t a t h r o u g he x p e r i m e n ta n a l y s i so fr e a lo n l i n ew e bp a g e s ，w ec o n c l u d et h a tt h ei e s y s t e mc a na d a p tt ov a r i o u sw e b s i t ew e l l i nc o m p a r i s o nt ow h i s ks y s t e m ，t h e e x p e r i m e n t a lr e s u l t sr e v e a lt h a tt h eg e n e t i ca l g o r i t h mb a s e dr u l el e a r n i n go u t p e r f o r m s t h ew h i s k a l g o r i t h mi nb o t he f f i c i e n c ya n da c c u r a c y k e yw o r d s ：w e bi n f o r m a t i o ne x t r a c t i o n ；e x t r a c t i o nr u l e ；g e n e t i ca l g o r i t h m ； i n d u c t i o nl e a r n i n ga l g o r i t h m ；w h i s ks y s t e m 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文 = = 基王塑佳篡洼的型业值：垦抽塑夔苤： 。除论文 中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文 中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公 开发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：盔弊 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密岔在上年解密后适用本授权书。 ， 不保密酉( 请在以上方框内打“) 论文作者签名：智锭岛导师签名：叩鹈 日期：加0 7 年7 月弓日 基于遗传算法的w e b 信息抽取技术 第1 章绪论 1 1 课题研究背景 自从上个世纪九十年代，随着i n t e m e t 的快速发展，网络已成为现代社会生活 各个领域的不可缺少的部分。海量的信息呈现在网络上，网络已经成为发布信息 和获取信息的重要渠道和场所，网页成为信息的载体。面对浩瀚如烟的网络信息， 使用关键字搜索的搜索引擎( 如g o o g l e 、b a i d u 等) 不能满足用户的真正需求，它 呈现给用户的是一系列包含关键字的信息摘要，而不是为用户直接提供他们真正 想要的w e b 数据，用户仍然需要进一步通过文档超链接查找获取真正需要的信息。 事实上，大量的w e b 数据，据统计约8 0 的内容，是存储在网站背后的数据库系 统中，但是由于安全考虑我们却无法获取网站后台的数据库。 目前w e b 的数据信息都是夹杂在h t m l 标签间呈现给我们，这样便于使用浏 览器浏览和显示，且相同主题的数据通常分布在不同的网站上，并且网页对数据 本身没有描述，也没有清晰的语义信息和明确的模式，不能像使用数据库中的数 据一样使用这些数据。传统的手工获得网络数据的方法是“查找网页一打开网页 一查找关键数据一存储数据一分析数据 ，这样需要大量的人力物力，也会引入人 为的不必要的错误。 这些背景表明，如何高效、准确的从w e b 上的获取用户感兴趣的结构化的数 据成为一个重要的研究课题。 1 2 课题研究目的与意义 w e b 信息抽取技术就在这种迫切需求的背景下产生并发展开来，它是智能信 息检索研究的一个重要的子领域。信息抽取( i e ：i n f o r m a t i o ne x t r a c t i o n ) 是从一 段文本中抽取指定的一类信息( 事件、事实) 并将其形成结构化的数据填入一个 数据库中，可进一步用于信息查询、文本深层挖掘、自动回答问题等n 1 。w e b 信息 抽取也是信息检索、数据挖掘、竞争情报、自动回答等研究领域的一个重要课题幢1 。 w e b 信息爆炸式的增长蕴含着宝贵的知识和丰富的资源，为用户提供了一个极有 价值的信息源。 第1 章绪论 现有的w e b 信息抽取技术已经广泛应用在不同领域，如：网上比较购物系统， 系统通过抽取不同网站中不同品牌的同类商品的信息( 如性能、价格等) ，为用户 提供清晰的商品比较分析；股票分析系统将分散在不同w e b 页面的动态变化的股市 信息抽取出来，用于股市行情公告；天气分析系统通过抽取并存储每天的天气情 况，为天气预报和分析提供依据。除此外，w e b 信息抽取还广泛应用于企业情报获 取、个性化信息服务、网站恢复重建等等。 w e b 数据结构差异较大，网页存在超链接、图片等信息，数据动态变化较快， 网页的标签不完整。传统的i e 工具采用基于句法和语义结合的抽取规则( 模式) ， 而这对于w e b 上的半结构化数据则不适用，这使得从w e b 抽取信息和传统的信息 抽取技术存在很大的差异性，更具有一定的复杂性和挑战性。 目前已经出现了大量的i e 系统和工具，总体上看，它们在自动化程度、对复杂 对象的支持、页面内容要求、用户界面、x m l 输出、健壮性和适应性等方面都表 现各异。系统一般都适用于特定领域，且适应性和健壮性都有待提高，因此，建 立一个高效、适用性强的w e b 抽取系统具有重要的实践作用和意义。 1 3 论文内容与组织结构 为了能从海量信息的w e b 中准确的获得用户感兴趣的信息，本课题重点是针 对w e b 上的数据特点，设计实现了一个半自动化的w e b 信息抽取系统，重点利用 遗传算法改进w h i s k 系统1 中的规则学习算法生成抽取规则集，对w e b 上的结构 化和半结构化的数据进行实验，并统计分析抽取数据。本文的主要内容分为以下 几个方面： 网页的获取和解析，即从网上通过网络爬虫获取网页并通过解析器解析网页。 网页信息块的预处理，主要是指对信息块去噪和训练例子标注。 抽取规则的生成，包括单槽和多槽抽取规则的定义和生成，重点是利用遗传算 法学习生成抽取规则的算法。 实验结果的比较，主要针对改进算法在效率、召回率、准确率上同原算法进行 对比分析。 趋势分析，主要针对系统一段时间的不同主题的抽取数据以图形化的方式统计 基于遗传算法的w e b 信息抽取技术 和分析抽取数据。 本文共分六章，除本章外其它各章的安排及内容概括如下： 第2 章为“w e b 信息抽取概述”，本章简单介绍了信息抽取的发展历程，并 详细比较分析现有的w e b 信息抽取工具。 第3 章为“遗传算法的简介”，本章简单介绍遗传算法的基本流程和基本算子。 第4 章为“基于遗传算法的规则学习算法”，这是本文的重点之一，详细的介 绍遗传算法在规则学习算法中的应用。 第5 章为“系统设计实现”，本章主要介绍w e b 信息抽取系统的实现框架和模 块组成，并详细阐述其中的关键技术。 第6 章为“实验分析”，本章主要介绍w e b 信息抽取系统的对三类网页的测试 结果，对学习算法的实验结果对比分析，并对已抽取的数据进行趋势分析。 第7 章为“结论”，本章总结本文的主要工作和w e b 信息抽取系统的优缺点， 并针对存在问题提出了下一步的研究工作。 基于遗传算法的w e b 信息抽取技术 第2 章w e b 信息抽取概述 2 1 信息抽取的起源与发展 信息抽取技术的初始研究最早追溯到2 0 世纪6 0 年代中期，以两个长期的、研 究性的自然语言处理项目为代表，即美国纽约大学开展的l i n g u i s t i cs t r i n g 项目和 耶鲁大学r o g e rs c h a n k 及有关事故理解的研究n 3 。这两个项目都是从自然语言文本 中抽取得到结构化的信息，其中纽约大学的项目用到抽取信息格式，也就是现在 信息抽取中的规则或模板；而耶鲁大学的项目采用了期望驱动和数据驱动结合的 方法。 从1 9 8 7 年到1 9 9 8 年，消息理解会议( m u c ，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 ) 共举行了七次，它们的召开使信息抽取成为自然语言处理领域的一个重要分支， 推动了信息抽取的蓬勃发展。m u c 的一个重要的成就是制定了信息抽取系统的评 测标准。它采用评测驱动的会议模式，即每个参加会议的单位根据预定的知识领 域开发一个信息抽取系统，然后用该系统处理相同的文档库，把系统抽取结果与 手工标注的标准结果相对照得到最终的评测结果碡3 。 近几年来，随着信息抽取技术的广泛研究，它涉及到了深层次的语言理解、 篇章分析与推理、多语言文本处理、w e b 信息抽取、名实体识别等自然语言研究 领域。信息抽取技术的研究对网络信息过滤和信息安全、搜索引擎、信息检索、 机器翻译、文本挖掘、企业智能信息系统等许多应用领域具有重要的推动作用。 同时，w e b 信息抽取作为信息抽取的一个子研究领域得到了广泛的研究和发展。 2 2 信息抽取系统的评测标准 消息理解系列会议的召开推动了信息抽取的发展。m u c 会议的显著特点并不 是会议本身，而在于对信息抽取系统的评测n3 。在m u c 中，衡量信息抽取系统的 性能主要根据两个评价指标：召回率( r e c a l l ) 和准确率( p r e c i s i o n ) 。表2 1 是抽取 结果的统计表。 第2 章w e b 信息抽取概述 表2 1 抽取结果统计表 t a b 2 1s t a t i s t i c sf o rt h ee x t r a c t e dr e s u l t s 说明数= 蕈( 个) 抽取出的相关信息点的个数 a 抽取出的不相关信息点的个数 b 未抽取出的相关信息点的个数c r = _ 冬水1 0 0 ，召回率( r ) 是指系统正确抽取的结果占所有可能正确结果 么+ c 的比例，值越大，抽取出的正确数据越多。 p = _ _ 冬木1 0 0 ，准确率( p ) 是指系统正确抽取的结果占所有抽取结果的比 么+ 召 例，值越大，抽取出数据的准确性越高。 f = 篱，理想情况下，召回率( p ) 和准确率( r ) 的值都越高越好， 但是两者通常不能兼得，所以引入f 一指标。f 一指标是召回率和准确率两个指 标的综合性指标。其中矽是表示召回率和准确率的相对重要性的比例因子， 越小，召回率的重要性就越强，反之，罗越大，准确率的重要性就越强。通常 p 设定为1 ，此时召回率和准确率的值同等重要。 d a w ng ，g r e g g 等提出了适应性的信息抽取系统具备的要求嘲：准确性、弹性、 自我修复性、通用性、可扩展性、开放性。这就要求要从多方面因素考虑抽取系 统的性能，不断完善和改进。 c h i a h u ic h a n g 等人用三维空间评测主要的w e b 信息抽取系统心1 ：1 、抽取任务 的领域；2 、使用的技术；3 、自动化程度。第一维度标准解释了为什么i e 系统未 能处理一些特殊结构的网站；第二维度标准基于使用的技术来分类i e 系统；第三 维度标准评测i e 系统的自动化程度。这三个标准为各种i e 系统提供定性的评估。 2 3w e b 信息抽取的原理 基于遗传算法的w e b 信息抽取技术 图2 1w e b 信息抽取系统的一般模型 f i g 2 1t h eg e n e r a lm o d e lo fw e bi n f o r m a t i o ne x t r a c t i o ns y s t e m w 曲信息抽取的主要工作由包装器完成，其一般模型如图2 1 。包装器是数据 源中数据由一种模式转化为另一种模式的软件构件，在w e b 环境下的包装器能从 网页中抽取相关内容并用结构化形式表示，它通常由一些抽取规则( 模式) 和应 用这些规则的执行抽取数据的计算机程序组成。 w 曲信息抽取一般模型主要分为两个模块，首先是由包装器的生成规则过程 根据样本网页生成本领域的抽取规则集，并将其加入抽取规则库，然后通过包装 器的抽取数据过程抽取同源网页中数据，并以结构化形式输出数据。 包装器的生成方法是w e b 信息抽取系统的重点，传统的方法采用手工编写规 则和相应的代码来生成包装器，这样不但需要高水平的专家而且编写费时费力， 因此后来的w e b 信息抽取系统一般采用机器学习的方法构建包装器，自动化程度 各不相同。 根据包装器学习的自动化程度，w e b 信息抽取系统较流行的两种方法是基于 监督学习的包装器归纳方法和基于非监督学习的全自动抽取方法呻1 。包装器归纳法 广泛采用的一种用机器学习方法自动生成分装器的方法，其主要思想是从一系列 标记网页中归纳学习生成抽取规则，再去抽取同源网页中的数据，如王小朋等人 第2 章w e b 信息抽取概述 提出的基于解释学习的包装器生成n0 。但两者都存在各自固有的优缺点，具体见 表2 2 。 表2 2 监督和非监督学习算法的优缺点比较 t a b 2 2c o m p a r i s o no ft h ea d v a n t a g e sa n dd i s a d v a n t a g e so fs u p e r v i s e da n dn o n s u p e r v i s e d l e a r n i n ga l g o r i t h m 方法类型优点缺点 基r 监督学习的包装手上标注，明确感兴趣的手上标注代价较高，包装器需要维护。 器归纳学习方法抽取内容和数据意义。 基于非监督学习的全抽取存储过程完全自动抽取结果可能含许多无关数据，无语义， 自动抽取方法化，维护代价小。多网站抽取数据需要集成操作。 2 4w e b 信息抽取工具分类 现有很多i e 系统，采用的方法也各不同，根据l a e n d e r 的分类n 引：有的采用 包装器语言，如m i n e r v a 和w e b o q l 1 ；有的依赖h t m l 文档结构，如w 4 f n 1 1 1 和r o a d r u n n e r n 羽；有的采用自然语言处理( n l p ) 技术，如w h i s k 1 和r a p i e r n3 1 ； 有的采用包装器归纳学习，如w i e n n 钔和s o f t m e a l y n 5 m 1 ；有的使用数据模型，如 d e b y e n 17 1 ；有的运用领域本体，如b y u n 一刚。 网络是一个巨大的信息源，w e b 信息为了便于显示往往夹杂在h t m l 标签内， 因此，w e b 上的文本可以分为三种类型：结构化的文本、半结构化的文本、自由 文本n 引。根据处理w e b 文本类型的不同，可以把现有的信息抽取系统分为：处理 结构化文本的i e 系统、处理结构半结构化文本的i e 系统、处理半结构化自由文 本的i e 系统、处理自由文本的i e 系统。本文按此分类标准对现有i e 系统进行详 细的介绍分析比较。 2 4 1 处理结构文本的i e 系统 w e b 上的结构化文本一般是从网站后台数据库中读取的文本或者是根据事先 定义的严格的格式生成的文本，这样的信息比较容易抽取且抽取的准确率较高。 代表性的系统有w 4 f 1 、x w r a p 2 0 1 、r o a d r u n n e r n 2 1 、m d r 2 2 1 。 基于遗传算法的w e b 信息抽取技术 w 4 f w 4 f 的抽取规则利用h t m l 的结构特点，它用h e l ( h t m l e x t r a c t i o nl a n g u a g e ) 定义抽取规则，提供图形用户界面。它只能自动的定义单个 抽取规则，而对于想得到感兴趣的多个数据项时，只能由用户人工地写抽取规则， 是半自动化的信息抽取工具。 图2 2w 4 f 信息抽取过程 f i g 2 2i n f o r m a t i o ne x t r a c t i o no fw 4 f 图2 2 显示w 4 f 的抽取过程。具体过程如下：首先，通过检索代理根据一个 或多个检索规则从w e b 上检索并下载w e b 文档；然后，根据w e b 文档的d o m 模 型通过h t m l 解析器构建h t m l 语法树；接着，用户根据语法树手工编写抽取规 则，用来在语法树上定位数据，利用提取引擎抽取数据，抽取出的数据用w 4 f 的 内部格式n s l 存储；最后，根据映射引擎把抽取出的数据映射成x m l 格式，以 备进一步使用。 x w r a p 是利用了h t m l 结构的半自动化的信息抽取系统。系统首先通 过交互式的方式，检索并规范化网页( 清除掉不规范的h t m l 标签) ；然后再将网 页解析成h t m l 语法树；接着系统根据用户在样本页中指定的抽取区域和类型， 以及在样本页中指定语义项和与之对应的实例，自动学习抽取规则实现信息抽取， 第2 章w e b 信息抽取概述 最后利用启发信息获得数据间的层次结构关系，生成x m l 文档。 系统在学习阶段需要用户的参与较多，并且该系统只适合对含有明显区域结构 的网页进行信息抽取，模式的表达能力也非常有限。 r o a d r u n n e r 是第一个全自动的信息抽取系统。系统分为两个过程：模式 发现过程和数据抽取过程。模式发现过程：系统对两个样本页面中的内嵌类型( 主 要是标签) 进行比较，分析并解决标签不匹配的情况，并获得一个利用正则表达 式表示的该类页面的通用结构模式，此结构模式被称为w r a p p e r 。数据抽取过程： 利用w r a p p e r 的内容和其它样本网页进行比较归纳，总结出所有具有相似内嵌类 型的网页的通用的结构模式，系统根据结构模式中h t m l 标记间的关系，以嵌套 的形式组织抽取出的数据。 图2 。3r o a d r u n n e r 例子n 2 1 f i g 2 3e x a m p l eo fr o a d r u n n e r 图2 3 是用r o a d r u n n e r 信息抽取工具进行信息抽取的一个例子。图中用了两 个样本网页( 一个称为w r a p p e r ，另个称为s a m p l e ) 进行比较，当s a m p l e 中出 现的字符串与w r a p p e r 中指定的字符串不匹配时，就调用r o a d r u n n e r 自己定义的 不匹配算法进行归纳，产生左下角的w r a p p e r 。系统抽取出结构模式确定的所有数 据，但是包含很多用户不感兴趣的数据，而且抽取出的数据没有语义信息。另外， 基于遗传算法的w e b 信息抽取技术 该系统的实现需要大量的样本训练，网页规模对系统影响较大，对于大规模的网 页，运行效率较低。 m d r ( m i n i n gd a t ar e c o r d si nw e bp a g e s ) 也是一个全自动的从网页中 抽取结构化数据记录，无需人工参与。m d r 使用标签树( 如图2 4 右侧的树) 来 描述模板或规则，其具体流程如下：首先，为待抽取信息的网页建立对应的h t m l 标签树：其次，用标签树和h t m l 标签字符串匹配算法挖掘出页面中数据区域，数 据区域中包含许多结构相似的数据记录；最后，从每个数据区域中识别出数据记 录，这些数据记录在标签树中表现为拥有同一个父节点。m d r 仅实现了从页面中 自动的抽取结构化的数据记录，而不是页面中的结构化的数据。 图2 4h t m l 文件以及它对应d o m 树和标签树 f i g 2 4ah t m lf i l ea n di t sc o r r e s p o n d i n gd o m t r e ea n dt a gt r e e 后来又出现许多改进m d r 的自动化工具，如d e p t a 2 3 1 和n e t t 2 4 1 ，它们都是 从产品列表或表格中抽取信息，但是它们都对待抽取网页中信息的结构化程度要 求比较严格。 第2 章w e b 信息抽取概述 上述的四种信息抽取系统虽然都利用h t m l 的结构特点实现信息抽取，但是 它们的自动化程度、规则表示、抽取槽的类型、是否基于h t m l 结构等方面表现各 异，它们还存在很多重要的不同。表2 3 总结比较上述系统的主要特点。 表2 3 处理结构化文本的工具比较 t a b 2 3c o m p a r i s o no ft o o l sd e a l i n gw i t hs t r u c t u r e dt e x t 自动化程支持支持非“ 工具 主要技术规则类型学习算法 度多槽h t m l 文档 w 4 f h t m i 标签正则表达式否手工 否 否 w r a pd o m 树 自由上下文否手工否否 m d r h t m l 标签树标签树局部树全自动 否否 r o a d r u n n e rh t m l 标签正则表达式字符算法全自动是限制 2 4 2 处理结构半结构化文本的i e 系统 半结构化的文本是指夹杂在h t m l 标签内的非结构化的文本，由于结构化的数 据抽取较容易，有些系统把它和没有严格格式的半结构化文本同时处理。代表性 的系统有w i e n t l4 1 、s o f i m e a l y f l 5 , 1 6 1 、s t a l k e r 2 2 , 2 5 , 2 6 1 ，i a s a 【2 8 1 ，( 1 p ) 2 【2 9 】。 w i e n 分装器归纳生成环境( w r a p p e ri n d u c t i o ne n v i r o n m e n t ) ，它是第一 个提出包装器归纳生成的系统。它的抽取规则定义为h l r t 结构，即包括头分隔 符、左右分隔符、尾分隔符，其中头尾分隔符是用来定位信息点的开始和结束， 左右分隔符是指待抽取槽的左右，符合这个规则的页面几乎都是搜索数据库所得 的表格布局显示的页面。实现过程如下：首先，用户输入标记好分隔符的整个网 页，然后，搜索由“h l r t 分装器模型 定义的分装器空间，反复尝试所有可能的 分隔符，直到找到与标记网页相一致的h l r t 分装器。 w i n e 还实现自动标记样例的方法，标记算法输入是特定领域的人工编制的启 发式规则，输出是待抽取内容。这样能避免人工标记整个网页集的繁重的工作量。 系统为了控制出错率，还采用了机器学习的理论预测需要学习例子的个数。w n e 只考虑与待抽取数据紧相邻的分隔符，因此系统不能抽取数据项缺失或数据项次 基于遗传算法的w e b 信息抽取技术 序不固定的网页：w i n e 以整个网页作为输入条件，因此网页规模对系统影响较大。 s o r m e a l 广也采用包装器学习的方法，使用非确定有限状态机归纳学习 自动生成提取w e b 信息的包装器。其中，状态机的状态代表待抽取的事实，边代 表定义分隔符的抽取规则，状态转换由上下文规则的匹配结果确定，因此能处理 结构变化的数据项，每个待抽取数据项对应一个特定的转移路径。系统的抽取规 则用一类识别事实周围的分隔符的集合表示。 系统主要由两个状态机构成，一个是体转化器和元组转化器。前者用于从网页 中提取某类数据区域，输入分隔符集合，输出是字符集；后者用于从数据区域中 提取属性序列，输入一系列带标记的元组，这些元组提供了分隔符的位置和事实 次序变化的信息，通过归纳分装器输出抽取规则。s o f t m e a l y 处理能力比w i n e 强， 能够处理信息项的缺失和次序简单的变化。 s t a l k e r 是一个通过学习算法归纳抽取规则的包装器系统。它采用了 基于类型树( 图2 6 左侧) 的内嵌目录结构树( 如图2 6 右侧) 。每个抽取项对应 内嵌目录树中的一个节点，包装器将使用规则从该节点的父节点中抽取出该项内 容。对每项待抽取的内容，需要两条规则：开始规则，用于检测并标识抽取项的 开始位置；结束规则，用于检测并标识抽取项的结束位置。分装器归纳算法产生 抽取规则并表示为简单的标志语法。 1 1 r e s t a u r a n tn a m e ： g o o dn o o d l e s 8 0 0 9 9 6 5 0 2 3 1 5 7 0 0l a k es t ， o a kp a r k 。p h o n e ：( 7 0 8 ) 7 9 8 - 0 0 0 8 图2 5 一段餐馆的h t m l 代码l j f i g 2 5p 矾o fh t m lc o d ef o rr g s t a u r a n t s 第2 章w e b 信息抽取概述 元组：餐厅 字符串：名称所集：地垃 i 元组：地址 一一孑矿卜 字符串：字符串：字符串：宇符串； 街道城市 地区码 电话号码 名称囊：( 地址) i 地址 一一7 吣 街道醢市地区码电话号码 图2 6 图2 5 对应的类型树和内嵌目录树1 f i g 。2 。6x y p et r e ea n de m b e d d e dc a t a l o gt r e eo ff i g 。2 5 s t a l k e r 采用线性覆盖学习算法，即在训练过程中覆盖尽可能多的正例，而 忽略所有反例。s t a l k e r 适用于抽取多层嵌套架构的数据记录，采用分级抽取的 思想，将复杂的抽取问题变成一系列简单的抽取子任务，不同级别的抽取相互独 立，每次抽取是单个信息项。因此，文档中信息项的次序是没有关系的。对于信 息项缺失或次序多变的文档一样能处理。 w i e n 、s o f l m e a l y 、s t a l k e r 这三个工具都采用包装器归纳的方式，用户需 要标注部分例子指导包装器的生成，因此它们都是半自动化的。表2 4 从以下方面 进行对比分析，其中“丢失多”是指信息项丢失或增加，“不固定”是指信息项顺 序不固定，“嵌套”是指数据的嵌套对象格式。 表2 4w i n e 、s o f t m e a l y 、s t a l k e r 的比较 t a b 2 4c o m p a r i s o no fw i n e ，s o f t m e a l y , s t a l k e r 支持非h t m l支持抽取目标变化 工具抽取规则类型支持多槽 文档丢失多不固定嵌套 w i n e正则表达式是是否否限制 s o f t m e a l y 正则表达式 否 是是限制是 s t a l k e r正则表达式否是是是是 2 4 3 处理半结构化自由文本i e 系统 信息抽取最初的处理对象是自由文本( 如新闻报告、医药研究报告) ，它通常 基于遗传算法的w e b 信息抽取技术 使用自然语言处理技术，抽取规则建立在词或词类间句法关系的基础上；而半结 构化的文本是介于自由文本和结构化文本之间的文本( 如电报报文) ，它缺少语法， 没有完整的句子，抽取规则需要依赖字符和h t m l 标签，语法和语义作用有限。有 些i e 系统能够处理的文本要复杂一些，能够抽取事先标注的的简单的自由文本和 半结构化文本，如r a p i e r 12 1 、s r v 3 0 , 3 1 , 3 2 、w h i s k 3 1 。 r a p i e r 一一健壮的信息抽取规则自动生成系统( r o b u s ta u t o m a t e d p r o d u c t i o no fi n f o r m a t i o ne x t r a c t i o nr u l e s ) ，是以半结构化文本为处理对象，采用 学习算法生成抽取规则。其抽取规则使用限制的语法和语义信息作为模式，每个 模式分为三部分：前填充子，匹配待抽取项之前的文本模式；填充子，匹配抽取 项的模式；后填充子，匹配紧接着待抽取项的文本模式；模式的每个部分都是由 模式项和模式列表顺序组成。一个模式项准确地匹配满足限制的一个单词，一个 模式列表是满足限制因素的最大长度为n 的词的集合。r a p i e r 采用三种限制因 素，即特殊单词、单词词性以及它的语义，这些限制是一个或多个单词或语义类 的析取列表。 系统输入待抽取信息的填充模板集作为训练内容，从中学习得到模式匹配规 则，抽取文本中符合填充模板中的空槽。它的学习算法是一个由一个特殊到一般、 从底向上的搜索算法，算法从训练例子集中找出与目标槽匹配的最具体的规则开 始。首先，随机从具体的规则库中抽取一系列成对的规则；然后，通过横向搜索 找到这对规则的最好的概括，采用最少概括的概括方法，增加限制条件，不断重 复直到不再有进展为止。系统以目标词组为中心设定抽取目标，因此系统只能进 行单槽抽取。 s r v 带确认功能的次序规则( s e q u e n c er u l e s w i t hv a l i d a t i o n ) 是一种自 上而下、关系型的信息抽取算法。系统输入一系列已标记出待抽取区域的样例网 页以及一系列基于字符串的特征，输出一系列的抽取规则。 s r v 用分类问题解决信息抽取问题。实例中所有可能的短语( 取最长者) 都 是实例，文档中的候选实例交到分类器。系统为每个短语赋予一个测量值，作用 是反映该短语作为目标格填充子的信度。s r v 利用了简单特征和关系特征，简单 第2 章w e b 信息抽取概述 特征包括字词的长度、类型、拼写、词性等；关系特征是指字词的相邻度。s r v 的规则具有较强的表达能力，且事先无需先进行句法分析。 w h i s k 采用了监督式的学习算法，它能够从多种格式文本中产生抽取 规则。处理结构化或半结构化文本时，w h i s k 无须事先经过句法分析，但处理自 由文本时，要先对文本作句法和语义标注。w h i s k 可以产生单槽和多槽的抽取规 则，即可以实现单槽抽取也可以实现多槽抽取。但是w h i s k 操作对象不是整个 h t m l 文档，而是象句子或类似长度的文本。 w h i s k 抽取模式是用正则表达式表示，主要包括两部分内容：描述有关信息 及上下文的语义信息及待抽取信息的准确边界。系统采用监督式学习算法，而且 需要输入一系列手工标注的训练实例，输出是一系列归纳学习生成的规则。w h i s k 属于机器学习算法中的覆盖学习法，首先，找到一个最宽泛的能覆盖规则种子的 规则，对每个槽依次进行生成规则，若规则不能满足错误率，则一次增加一项扩 展规则，直到满足错误率的要求。 r a p i e r 、s r v 、w h i s k 这三个系统都支持非h t m l 的文档，都能处理自由文 本，都采用了学习算法，都需要标注样例，都能够处理一些属性缺失或多属性值 的情况。表2 5 从以下方面统计比较了它们的差异，其中抽取层次分为四类：域级 别、记录级别、网页级别、站点级别，r a p i e r 和s r v 为了抽取单槽记录，相当 于域的级别。 表2 5r a p i e r 、s r v 、w h i s k 的比较 t a b 2 5c o m p a r i s i o no fr a p i e r ，s r v ，w h i s k 工具规则类型抽取层次支持多槽学习算法 r a p i e r 逻辑规则域级别 否 自底向上的i l p s r v 逻辑规则域级别否自底向上的i l p w h i s k 正则表达式记录级别是自顶向下的覆盖学习 2 4 4 处理自由文本的ie 系统 这类文本的信息抽取工作最为困难，一般需要使用自然语言处理技术