（计算机应用技术专业论文）基于网站结构的web信息抽取方法研究.pdf

北京工商大学硕士学位论文 摘要 随着i n t e r n e t 的飞速发展，w e b 已经发展成为一个全球的、巨大的、分布和共享 的信息空间，为用户提供了一个极具价值的资源。但因i n t e r a c t 所固有的开放性、动 态性与异构性，使得用户很难准确快捷地从w w w 上获取所需信息。如何快速准确地 从浩瀚的信息资源中找到所需信息成为困扰网络用户的一大难题，这就是所谓的r i c h d a t a - p o o ri n f o r m a t i o n 。针对这一问题，出现了w e b 信息抽取技术。w e b 信息抽取系统 从i n t e m e t 上抽取的信息不仅可以直接提供给用户，还可以作为构建智能查询系统和 数据挖掘系统的基础，有着广阔的应用前景。 本文在概述w e b 信息抽取以及分析现有系统的基础上，针对数据密集型网站，设 计并实现了一种新的基于网站结构的w e b 信息抽取方案。该方案主要包括四个步骤： ( 1 ) 网站结构树生成：从网站的拓扑结构入手，根据网页之间的链接关系，生成网站结 构图；然后去掉网站结构图中的回溯边，将网站结构图转化成网站结构树；( 2 ) 页面规 范化：将网站结构树的叶子结点所在的页面进行规范化，转换成格式良好的x h t m l 文档；( 3 ) 页面二次聚类：采用二次聚类算法对网站结构树的叶子结点根据文档的组织 结构进行聚类：( 4 ) 模板推导：采用匹配算法推导出每类的模板。本文所取得的主要研 究成果如下： ( 1 ) 提出了由网站结构图生成网站结构树的算法。该算法的目的是去掉网站结构图 中的回溯边，从而将网站结构图转化成网站结构树，其主要思路是：首先根据网页结 点u r l 所在目录的层次关系，去掉网站结构图中的部分回溯边；然后在宽度优先遍历 的过程中去掉已经遍历过的重复结点，生成网站结构树。实验证明了该算法的有效性。 ( 2 ) 针对聚合聚类算法时间耗费较大从而不适合数据量大的网站的特点，本文提出 二次聚类算法对此进行了改进。二次聚类算法首先将网站结构树中深度值最大的叶子 结点与其兄弟结点合并为同一类，称为“一次聚类”；然后采用聚合聚类法对一次聚类 的结果以及剩余叶子结点进行聚类，称为“二次聚类”。这样可以大大减少聚合聚类的 工作量，提高聚类的运行速度。并且实验证明，结果基本上能够达到聚类要求。 ( 3 ) 模板推导是本文研究的重点。本文引入抽象语法树( a b s t r a c ts y n t a xt r e e ，a s t ) 和u n i o n f r e e 正则表达式的概念，并且用a s t 描述的u n i o n f r e e 正则表达式来表示模 板( 即包装器) ，提出了一种新的模板推导方法。该方法采用树状结构的匹配算法，对 基于网站结构的w e b 信息抽取方法研究 表示为a s t 的当前包装器和d o m 树形式的当前样本进行匹配操作。算法不仅能够正 确推导出结构上的可选、迭代模式，而且能推导出文本模板。 本文设计实现的w e b 信息抽取方案，可以自动推导出数据密集型网站中各类网页 的通用结构模板和文本模板，从而利用该模板对同类网页的信息进行抽取，为当前 w e b 信息抽取方法的研究提供了新的思路。 关键词：信息抽取；网站结构；数据密集型网站；聚类；模板推导 北京工商大学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r a c t , w e bh a sb e a d ) m eag l o b a l ，h u g e ，d i s m b u t e d a n ds h a r e di n f o r m a t i o ns p a c e ，w h i c hp r o v i d e su s e r sam a s s i v ea n dv a l u a b l ei n f o r m a t i o n r e s o u r r ：c b u ti ti sd i f f i c u l tf o ru s e r st oo b t a i ne x a c ti n f o r m a t i o nq u i c k l yb e 4 7 , a u s co f i n t e m e t so p e n i n g ，d y n a m i ca n dh e t e r o g e n e i t y h o wt of i n dt h en e e d e di n f o r m a t i o nq u i c k l y a n da c c u r a t e l yf r o mt h eh u g pi n f o r m a t i o nr e s o u r c eh a sb e c o m ead i f f i c u l tp r o b l e mt h a t p u z z l e st h eu s e r s t h i si s c a l l e d “r i c hd a t a p o o ri n f o r m a t i o n ”f o rt h i sp u 巾e ，t h e t e c h n o l o g yo fw e bi n f o r m a t i o ne x t r a c t i o na p p e a r e d t h ei n f o r m a t i o ne x t r a c t e db yw e b i n f o r m a t i o ne x t r a c t i o ns y s t e m sn o to n l yc a r lp r o v i d ef o r t h ee n du s e r s ，b u ta l s oi st h eb a s i s t ob u i l di n t e l l i g e n tq u e r ys y s t e m so rd a t am i n i n gs y s t e m s s ow e bi n f o r m a t i o ne x t r a c t i o n h a sag o o dp r o s p e c t b a s e do nt h eo v e r v i e wo fw e bi n f o r m a t i o ne x t r a c t i o na n da n a l y z i n gt h ee x i s t i n g s y s t e m s ，t h i sp a p e rd e s i g n sa s c h e m eo fw e b s i t es t r u c t u r e - b a s e dw e bi n f o r m a t i o ne x t r a c t i o n i nd a t a - i n t e n s i v ew e b s i t e s ，w h i c hh a sf o u rs t e p sa sf o l l o w s ：( 1 ) s p a nt h ew e b s i t es t r u c t u r e t l e e a c c o r d i n gt ot h et o p o l o g yo fw e b s i t ea n dh y p e r l i n k sb e t w e e nw e bp a g e s ，t h ew e b s i l e s t r u c t u r eg r a p hi sg o t a n dt h e ns p a nt h ew e b s i t es t r u c t u r ef l e eb yr e m o v i n gt h et r a c i n g e d g e si nw e b s i t es t r u c t u r eg r a p h ( 2 ) s t a n d a r d i z ew e bp a g e s s t a n d a r d i z et h el e a f - n o d e so f t h ew e b s i t es t r u c t u r et r e e ，t h a ti s , c o n v e r tt h e mi n t ot h ew e l l - f o r m e dx h t m ld o c u m e n t s ( 3 ) c l u s t e rw e bp a g e st w i c e c l u s t e rt h el e a f - n o d e so ft h ew e b s i t es t r u c t u r et r e ea c c o r d i n gt o t h ed o c u m e n ts t r u c t u r eu s i n gt w i c e - c l u s t e r i n ga l g o r i t h i n ( 4 ) i n d u c tt h et e m p l a t e i n d u c tt h e t e m p l a t eo fe a c hc l a s su s i n gm a t c h i n ga l g o r i t h m t h em a i np r o d u c t i o n si n t h i sp a p e ra s f o l l o w s ： ( 1 ) i no r d e rt or e m o v et h et r a c i n ge d g e si nt h ew e b s i t es t r u c t u r eg r a p ha n ds p a nt h e w e b s i t es t r u c t u r et r e e ，t h i sp a p e rp r e s e n t st h es p a n n i n gt r e ea l g o d t h i no fw e b s i t es t r u c t u r e o nt h eb a s i so fg e t t i n gw e b s i t es t r u c t u r eg r a p h t h ea l g o r i t h mf i r s t l yp a r t l yr e m o v e st h e t r a c i n ge d g e si nw e b s i t es t r u c t u r e dg r a p ha c c o r d i n gt ot h eh i e r a r c h yo fu r l d i r e c t o r i e s ，a n d t h e nd e l e t e st h en o d e sw h i c hh a v eb e e n 仃a v e r s e dd u r i n gt h ec o u r s eo fb r e a d t h f i r s t t r a v e r s i n g e x p e r i m e n t ss h o wt h ea l g o r i t h m i sf a i r l ye f f e c t i v e i l l 基于网站结构的w e b 信息抽取方法研究 ( 2 ) b e c a u s et h ea g g l o m e r a t i v ec l u s t e r i n ga l g o r i t h mh a sah i g ho v e r h e a da n di ti s n t a p p r o p r i a t ef o r t h em a s s i v ew e b s i t e s ，t h i sp a p e rp r e s e n t st h et w i c e - c l u s t e r i n ga l g o r i t h m t h e a l g o r i t h mf i r s t l yd u s t e r st h ed e e p e s tl e a f - n o d e sa n dt h e i rb r o t h e r s ，w l f i c bi s c a l l e d “f i r s t c l u s t e r i n g a n dt h e ni tc l u s t e r st h e 佗吼n to ff i r a tc l u s t e r i n ga n dt h er e s tl e a f - n o d e su s i n gt h e a g g l o m e r a t i v ec l u s t e r i n ga l g o f i t h m , w h i c hi sc a l l e d “s e c o n dc l u s t e r i n g b yd o i n gt h i s ，t h e e f f i c i e n c yo fc l u s t e r i n gc a n b ei m p r o v e d ( 3 ) t h ei n d u a i o no ft e m p l a t ei st h em o s ti m p o r t a n tp a r to ft h i sp a p e r t h ec o n c e p t so f a b s t r a c ts y n t a x 廿c c ( a s na n du n i o n f r e er e g u l a re x p r e s s i o na r ei n t r o d u c e d b a s e do nt h i s , t h i sp a p e rp r e s e n t sa l la p p r o a c ho ft e m p l a t ei n d u c t i o n u s i n gt h em a t e h i n ga l g o r i t h mo f 仃e e s t r u c t u r e ，t h ea p p r o a c hm a t c h e st h ec u r r e n tw r a p p e r ( r e p r e s e n t e db ya s t ) a n dt h ec u r r e n t s a m p l e ( r e p r e s e n t e db yd o mt r e e ) i tc a ni n d u c tn o to n l yt h eo p t i o n a l0 1 i t e r a t i v ep a t t e r n s i ns t r u c t u r e , b u ta l s ot h et e x tt e m p l a t e s i nc o n c l u s i o n , t h es c h e m eo fw e bi n f o r m a t i o ne x t r a c t i o nd e s i g n e di nt h i sp a p e rc a i n d u c ta u t o m a t i c a l l ys t r u c t u r et e m p l a t e sa n dt e x tt e m p l a t e si nd a t a - i n t e n s i v ew e b s i t e s u s i n gt h et e m p l a t e sw ec a ne x t r a c ti n f o r m a t i o nf r o mt h ew e bp a g e s t h i sp r o v i d e sad e w s o l u t i o nf o rt h e 瓣n tr e s e a r c ho nw e bi n f o r m a t i o ne x t r a c t i o n k e y w o r d s ：i n f o r m a t i o ne x t r a c t i o n ；w e b s i t es t r u c t u r e ； d a t a i n t e n s i v ew e b s i t e ；c l u s t e r i n g ；t e m p l a t ei n d u c t i o n 北京工商大学学位论文原创性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下进行的研究工作所 取得的研究成果。除了文中已经注明引用的内容外，论文中不包含其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体 均已在文中以明确方式标明。本声明的法律后果完全由本人承担。 学位论文作者签名：镍蓑日期：p 年y 月堵日 北京工商大学学位论文授权使用声明 本人完全了解北京工商大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属北京工商大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以采用影印、缩印或其它复 制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 学位论文电子版同意提交后，可于口当年口一年口二年后在学校图 书馆网站上发布，供校内师生浏览。 学位论文作者签名：兰扛生导师签名 日期：k 7 年t s l t , t 日 北京工商大学硕士学位论文 1 1 研究背景 第1 章绪论 随着i n l e r n e t 的飞速发展，w e b 已经发展成为一个全球的、巨大的、分布和共享 的信息空间，越来越融入到人们的生活、工作、学习、商务活动中去。企业及个人通 过建立网站或网页及时发布自己的信息、资源、需求，同时又通过网络来才寻求帮助， 获取信息。w e b 上包含了从技术资料、商业信息到新闻报道、娱乐信息等多种类别和 形式的信息，为用户提供了一个及其价值的资源。 w e b 在给人们带来便捷、快速、廉价、丰富的信息的同时，也带来了一个问题。 由于越来越多的企业和个人通过w e b 发布信息，使得w e b 上的信息量以指数级的增 长速度增长；同时w e b 是一个具有开放性、动态性和异构性的全球分布式网络，资源 分布非常分散，且没有统一的管理和结构，因此导致信息获取非常困难。w e b 上巨大 的信息量和用户的需求之间产生了严重的不平衡和矛盾，用户为了获取自己需要的一 点点信息，可能需要花费几十分钟、几个小时、甚至更长时间来搜索、浏览网页、查 找信息，一不小心，就会淹没在信息的海洋中。如何快速准确地从浩瀚的信息资源中找 到所需信息成为困扰网络用户的一大难题，这就是所谓的砌c hd a t a - p o o r i n f o r m a t i o n 。 虽然现在出现了形形色色的搜索引擎，但是这种基于关键字的搜索，得到的却还是一 个庞大的网页链接的结果集，用户必须逐个点击这些网页链接，采用人工的方式定位 最终的信息，同时这个结果集也并不一定都是用户想要的，这和具体的搜索引擎的性 能有关，这样就浪费了大量的人力、物力和时间。即使获得了相关内容的网页，如何 将这些网页中有用的信息抽取出来加以保存，作为自己信息库中的信息，也不是一件 简单的事情。 上述问题的关键在于目前w e b 信息大多以h t m l 文档的形式发布【1 1 。这些以 h t m l 标记语言发布的w e b 信息面向显示，缺乏模式信息和语义信息。对h t m l 标 记的理解和处理工作主要由浏览器来完成，而对通过浏览器看到的w e b 信息的理解和 处理工作则由用户完成，一般的应用程序不能解析、理解、应用w e b 信息。为了增强 w e b 信息的可用性，出现了w e b 信息抽取技术。该技术将w e b 上用户感兴趣的信息 从h t m l 文档中“抽取”出来，为应用程序利用w e b 中的信息提供了可能。现有的 基于网站结构的w e b 信息抽取方法研究 w e b 的信息抽取技术不但可以直接定位到用户所需的信息，而且采用一定的方式为其 附加语义，将其转化为语义清晰、结构化的信息，为w e b 查询提供了更为精确的方法， 使w e b 信息的再利用成为可能。因此w e b 信息抽取有着明显的优势和广阔的前景， 是当前的一个研究热点。 1 2 研究目标及内容 根据对邪冒的统计，设计者在设计网站的组织结构时，为了便于组织管理，他们 往往会根据人对知识的理解而将网站内容进行分类，从而将主题相同的页面放在w e b 服务器的同一个目录下，或根据主题层次组织成树形目录，这些目录和页面的层次结 构将映射到具体页面以及目录的u r l 上。即使在同一个页面中，信息的组织也有其规 律性簇聚性，就是内容含义相同或相似的信息组织在一起，在页面上体现为占据某 一块页面。另外，对于大型的网站，例如购物网、新闻网等，发布的网页大部分是通 过相应的后台数据库生成、以 r 刑l 文档的形式来显示的，使得内容网页的组织结构 具有很大的相似性，这类网站通常称为数据密集型网站( d a t a i n t e n s i v ew e b s i t e ) 。这些 结构类似的网页所共有的组织结构称为模板( t e m p l a t e ) 。本文研究的切入点就是这种 网页结构类似的数据密集型网站。 本文的研究目标是：对于一个网页结构类似的数据密集型网站，系统可以自动推 导出该网站的各类模板，从而利用模板对属于该模板的同类网页进行信息抽取。由于 时间所限，后续的根据生成的模板对同类网页进行信息抽取，并对抽取出的数据项进 行语义标识部分不包括在本文工作中。 本文研究的主要内容包括： ( 1 ) 网站结构图的生成方法，即如何根据网站的拓扑结构，生成网站结构图。 ( 2 ) 由网站结构图生成网站结构树的算法，即如何去掉网站结构图中的回溯边，生 成该网站的网站结构树。 ( 3 ) 页面规范化，即如何将不规范的h t m l 文档转换成格式良好的x h t m l 文档。 其中包括：对h t m l 存在的主要问题的分析，x h t m l 的优势，以及页面规范化的实 现方法。 ( 4 ) 聚类算法的研究。常用的聚类算法通常时间耗费较大，不适合数据量大的网站， 因此需要结合本文所研究问题的特点，对原有的聚类算法进行改进或者提出一种新的 2 北京工商大学硕士学位论文 聚类算法。其中相似度的计算、聚类算法的选择以及如何聚类，是本文研究的一个重 点与难点。 ( 5 ) 模板推导算法。这是本文研究的重点之一。该算法所实现的主要功能为：对于 聚类后的每一类网页，能够推导出各类网页的模板，不仅包括结构上的迭代模式、可 选模式和或模式，而且包括文本模板。 1 3 本文组织结构 本文在结构上共分为8 章： 第1 章介绍本文的研究背景、研究目标、研究内容以及论文的组织结构。 第2 章对w e b 信息抽取进行概述首先介绍信息抽取及w e b 信息抽取的相关概 念，并指出信息抽取与信息检索的区别；其次介绍信息抽取的发展历史和w e b 信息抽 取的研究现状，并对现有系统进行简要分析；最后介绍w e b 信息抽取的应用。 第3 章介绍了方案的设计目标及原则，给出了方案的总体框架，并对其中的各部 分作了简要介绍。 第4 章首先介绍了编辑距离的概念以及计算方法，然后详细论述了网站结构树生 成的设计与实现，包括网站页面的获取、网站结构的存储、网站结构图的生成以及由 网站结构图生成网站结构树的算法，最后给出了实验结果。 第5 章首先介绍了h t m l ，分析了h t m l 存在的主要问题，然后介绍了具有严格 规则定义的m l ，最后给出了页面规范化的实现方法。 第6 章首先介绍分析了常用的聚类算法，然后结合本文面向的对象是数据量大的 网站的特点，提出二次聚类算法来提高聚类的运行效率，并详细介绍了其中关系到聚 类质量的相似度的计算，提出了基于d o m 树编辑距离的相似度计算方法，最后给出 了验证聚类有效性的实验结果。 第7 章首先对相关概念进行了定义，在分析本文提出的模板推导方法的基础上， 给出了模板推导的总体设计，然后对其中主要函数的设计与实现进行了详细论述，最 后给出了几个数据密集型网站模板推导的结果。 第8 章总结本文所做的工作，并提出了今后进一步的研究和工作。 基于网站结构的w e b 信息抽取方法研究 2 1 相关概念 第2 章w e b 信息抽取概述 2 1 1 信息抽取的定义 信息抽取( i n f o r m a t i o ne x t r a c t i o n ，m ) 是近十几年来发展起来的新领域，起源于文 本理解，是自然语言处理领域的一个重要分支。 信息抽取的普遍定义为：从文本信息中抽取出预先想要的信息( 知识) ，表示成一 种统一的、结构化的形式，供信息查询、文本深层挖掘、自动回答问题等应用，为人 们提供有力的信息获取工具。例如从网上书店中抽取出图书的情况：书名、作者、出 版社、出版时间等；从经济新闻报道中抽取出公司发布新产品的情况：公司名、产品 名、发布时间、产品性能等；从病人的医疗记录中抽取出症状、诊断记录、检验结果、 处方等等。 从广义上讲，信息抽取的处理对象可以是文本、图像、语音、视频等多种媒体。 但随着文本信息抽取的强势发展，特别是在美国防高级研究计划局( d a r p a ) 所资助的 消息理解会议( m u c ) 对不同文本信息抽取系统组织统一评估后，信息抽取已被用来专 指文本信息的抽取1 2 l 。 信息抽取虽然需要对文本进行一定程度的理解，但与真正的文本理解( t e x t u n d e r s t a n d i n g ) 还是不同的在信息抽取中，用户一般只关心有限的感兴趣的事实信 息，而不关心文本意义的细微差别以及作者的写作意图等深层理解问题1 3 】。因此，信 息抽取只能算是一种浅层的或者说简化的文本理解技术。 2 1 2w e b 信息抽取的定义 顾名思义，w e b 信息抽取m c bi n f o r m a t i o ne x t r a c t i o n ，简称为w e b l e ) ，顾名思义， 是将w e b 作为信息源的一类信息抽取。 目前w e b 上的数据大部分都是以超文本标记语言( h y p c m x tm a r k u pl a n g u a g e ， r r r m l ) 描述的，主要目的是为了显示，让人通过浏览器浏览，缺乏对数据本身的描述， 4 北京工商大学硕士学位论文 不含清晰的语义信息，模式也不太明确。这使得应用程序无法直接解析并利用w e b 上 海量的信息，造成资源极大的浪费。 w e b 信息抽取正是研究如何将分散在i n t e m e t 上的半结构化的h t m l 页面中的隐 含的信息点提取出来，并以更为结构化、语义更为清晰的形式表示，为用户在w e b 中 查询数据、应用程序直接利用w e b 中的数据提供便利。 2 1 3 信息抽取与信息检索的区别 与信息抽取密切相关的一项研究是信息检索( i n f o r m a t i o nr e t r i e v a l ) ，但信息抽取 与信息检索存在差异，主要表现在三个方面【4 】： ( 1 ) 功能不同。信息检索系统主要是从大量的文档集合中找到与用户需求相关的 文档列表：而信息抽取系统则旨在从文本中直接获得用户感兴趣的事实信息。 ( 2 ) 处理技术不同。信息检索系统通常利用统计及关键词匹配等技术，把文本看 成词的集合( b a g so f w o r d s ) ，不需要对文本进行深入分析理解；而信息抽取往往要借 助自然语言处理技术，通过对文本中的句子以及篇章进行分析处理后才能完成。 ( 3 ) 适用领域不同。由于采用的技术不同，信息检索系统通常是领域无关的，而 信息抽取系统则是领域相关的，只能抽取系统预先设定好的有限种类的事实信息。 另一方面，信息检索与信息抽取又是互补的。为了处理海量文本，信息抽取系统 通常以信息检索系统( 如文本过滤) 的输出作为输入；而信息抽取技术又可以用来提 高信息检索系统的性能。二者的结合能够更好地服务于用户的信息处理需求。 2 2 信息抽取的发展历史 从自然语言文本中获取结构化信息的研究最早开始于2 0 世纪6 0 年代中期，这被 看作是信息抽取技术的初始研究，它以两个长期的、研究性的自然语言处理项目为代 表 5 1 。 美国纽约大学开展的l i n g u i s t i c s t r i n g 项目开始于6 0 年代中期并一直延续到8 0 年 代。该项目的主要研究内容是建立一个大规模的英语计算语法，与之相关的应用是从 医疗领域的x 光报告和医院出院记录中抽取信息格式( i n f o r m a t i o nf o r m a t s ) ，这种信 息格式实际上就是信息抽取最终的输出结果模板( t e m p l a t e ) 。 另一个相关的长期项目是由耶鲁大学r o g e r s c h a n k 及其同事在2 0 世纪7 0 年代开 5 基于网站结构的w e b 信息抽取方法研究 展的有关故事理解的研究。由他的学生g e r a l dd ej o n g 设计实现的f r u m p 系统是根 据故事脚本理论建立的一个信息抽取系统。该系统从新闻报道中抽取信息，内容涉及 地震、工人罢工等很多领域或场景。该系统采用了期望驱动c r o p d o w n ，脚本) 与数 据驱动( b o t t o m u p ，输入文本) 相结合的处理方法。这种方法被后来的许多信息抽取 系统采用。 从2 0 世纪年代末开始，信息抽取研究蓬勃开展起来，这主要得益于消息理解 系列会议( 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 系列会议使信息抽 取发展成为自然语言处理领域一个重要分支，并一直推动这一领域的研究向前发展。 推动正发展的研究活动与项目主要有： m u c 从1 9 8 7 年开始到1 9 9 8 年，m u c 会议共举行了七届，它由美国国防高级研究计 划委员会( d e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ，d a r p a ) 发起并资助。m u c 的显著特点并不是会议本身，而在于对信息抽取系统的评测。只有参加信息抽取系统 评测的单位才被允许参加m u c 会议。在每次m u c 会议前，组织者首先向各参加者 提供样例消息文本和有关抽取任务的说明，然后各参加者开发能够处理这种消息文本 的信息抽取系统。在正式会议前，各参加者运行各自的系统处理给定的测试消息文本 集合。由各个系统的输出结果与手工标注的标准结果相对照得到最终的评测结果。最 后才是所谓的会议，由参与者交流思想和感受。它通过一系列国际化的研究系统测评， 来推动信息抽取的研究，提高信息抽取的能力 从历次m u c 会议，可以清楚地看到信息抽取技术发展的历程。 1 9 8 7 年5 月举行的首届m u c 会议基本上是探索性的，没有明确的任务定义，也 没有制定评测标准，总共有4 个系统参加，所处理的文本是海军军事情报，每个系统 的输出格式都不一样。 m u c 2 于1 9 8 9 年5 月举行，共有9 个系统参加，处理的文本类型与m u c 1 一样。 m u c - 2 开始有了明确的任务定义，规定了模板以及槽的填充规则，抽取任务被明确为 一个模板填充的过程。 m u c - 3 于1 9 9 1 年5 月举行，共有1 5 个系统参加，抽取任务是从新闻报告中抽取 拉丁美洲恐怖事件的信息，定义的抽取模板由1 8 个槽组成。从m u g 3 开始引入正式 的评测标准，其中借用了信息检索领域采用的一些概念，如召回率和准确率等。 m u c - 4 于1 9 9 2 年6 月举行，共有1 7 个系统参加，任务与m u c - 3 一样，仍然是 6 北京工商大学硕士学位论文 从新闻报告中抽取恐怖事件信息。但抽取模板变得更复杂了，总共由2 4 个槽组成。 从这次会议开始m u c 被纳入t i p s t e r 文本项目。 m u c - 5 于1 9 9 3 年8 月举行，共有1 7 个系统参加。此次会议设计了两个目标场景： 金融领域中的公司合资情况、微电子技术领域中四种芯片制造处理技术的进展情况。 除英语外，m u c - 5 还对日语信息抽取系统进行了测试。在本次会议上，组织者尝试采 用平均填充错误率( e r r , e r r o rp e rr e s p o n s ef i l l ) 作为主要评价指标。与以前相比， m u c - 5 抽取任务的复杂性更大，比如公司合资场景需要填充1 1 种子模板总共4 7 个槽， 光任务描述文档就有4 0 多页。m u c - 5 的模板和槽填充规范是m u c 系列评测中最复 杂的。 m u c - 6 于1 9 9 5 年9 月举行，训练时的目标场景是劳动争议的协商情况，测试时 的目标场景是公司管理人员的职务变动情况，共有1 6 家单位参加了这次会议。m u c - 6 的评测更为细致，强调系统的可移植性以及对文本的深层理解能力。除了原有的场景 模板( s c e n a r i ot e m p l a t e s ) 填充任务外，又引入三个新的评测任务：命名实体( n a m e e l e n t i t y ) 识别、共指( c o r e f e r e n c e ) 关系确定、模板元素( t e m p l a t eh e m e m ) 填充等。 最后一届m u c 会议m u c - 7 于1 9 9 8 年4 月举行。训练时的目标场景是飞机 失事事件，测试时的目标场景是航天器( 火箭导弹) 发射事件。除m u c - 6 已有的四 项评测任务外，m u c - 7 又增加了一项新任务一模板关系任务，它意在确定实体之 间与特定领域无关的关系。 m u c 系列会议对信息抽取这一研究方向的确立和发展起到了巨大的推动作用。 m u c 定义的信息抽取任务的各种规范以及确立的评价体系已经成为信息抽取研究事 实上的标准。 m e t m e t 是m u l t i l i n g u a le n t i t yt a s ke v a l u a t i o n 的缩写，它也是d a r p a 发起的一个测 评项目。与m u c 主要针对英语文本进行分析和信息抽取的情况不同，m e w 的主要是 对日语、汉语以及西班牙语等多语种新闻文献进行命名实体抽取。m e t - 1 和m e t - 2 测 试分别于1 9 9 6 年和1 9 9 8 年进行。 a c e 【q 目前，除强烈的应用需求外，正在推动信息抽取研究进一步发展的动力主要来自 美国国家标准技术研究所( n i s t ) 组织的自动内容抽取评测( a u t o m a t i cc o n t e n t e x t r a c t i o n ) 会议。这项评测从1 9 9 9 年7 月开始酝酿，2 0 0 0 年1 2 月正式开始启动。这 7 基于网站结构的w e b 信息抽取方法研究 项评测旨在开发自动内容抽取技术以支持对三种不同来源( 普通文本、由自动语音识 别a s r 得到的文本、由光学字符识别o c r 得到的文本) 的语言文本的自动处理，研 究的主要内容是自动抽取新闻语料中出现的实体、关系、事件等内容，即对新闻语料 中实体、关系、事件的识别与描述。 与m u c 相比，目前的a c e 评测不针对某个具体的领域或场景，采用基于漏报( 标 准答案中有而系统输出中没有) 和误报( 标准答案中没有而系统输出中有) 为基础的 一套评价体系，还对系统跨文档处理( c r o s s - d o c u m e n tp r o c e s s i n g ) 能力进行评测。这 一新的评测会议将把信息抽取技术研究引向新的高度。 2 3w e b 信息抽取的国内外研究现状 如何从w e b 网页中抽取出所需要的信息，己成为互联网信息搜索与集成、信息 抽取研究领域中一个重要的研究课题。这个新的研究课题，虽只有几年的研究历史， 却已取得了许多重要的研究成果。为了对信息抽取技术作进一步研究，以增强本文原 型的易用和实用性，有必要对现有的信息抽取技术进行分析。w e b 信息抽取技术有多 种分类方式门。根据自动化程度可以分为：人工方式的信息抽取、半自动方式的信息 抽取和全自动方式的信息抽取3 大类。根据各种w e b 信息抽取工具所采用的原理将现 有的工具分为5 类：基于自然语言处理方式的信息抽取、基于包装器归纳方式的信息 抽取、基于0 m 吣l o g y 方式的信息抽取、基于i r r m l 结构的信息抽取和基于w e b 查询的信息抽取闱。 下面结合典型的系统，在语义的附加方式、模式的定义方式、规则的表现形式、 语义项的定位方式、对象的定位方式等几方面进行分析和比较。其中结构化的数据称 为对象。 2 3 1 基于自然语言处理方式的信息抽取 这类信息抽取主要适用于源文档中包含大量文本的情况( 特别针对于合乎文法的 文本) ，在一定程度上借鉴了自然语言处理技术，利用子句结构、短语和子句之间的关 系，建立基于语法和语义的抽取规则实现信息抽取。目前采用这种原理的典型系统有 r a p i e r t g j 、s r 叫1 0 l 、w m s k l l l l 。下面结合比较典型的系统w h i s k 来详细说明这种方 式的信息抽取。 8 北京工商大学硕士学位论文 w h 塔k 该系统既适用于结构化、半结构化的文本也适用于自由文本。结构化和半结构化 的文本，一般不符合文法，所以系统主要是根据语义项的上下文实现感兴趣信息的定 位。对自由文本，系统首先根据分割符将源文档分割成多个实例( 每个实例是一个语义 相关的文本块，如，在一个房地产广告的页面中，每- - n 广告称为一个实例) 。在交互 式的环境下，系统每一次呈现给用户一组实例用户在可视化的环境下根据系统提供的 实例标记出感兴趣的信息并定义模式，系统使用语法分析器和语义类( 如人名、机构名) 分析器，分析出用户标记信息的语法成分和对应的语义类，生成基于语法标记和语义 类标记的抽取规则，实现信息抽取。 这种基于自然语言理解方式的信息抽取技术，是将w e b 文档视为文本进行处理 的，抽取的实现没有利用到w e b 文档独特于普通文本的结构信息，使得信息抽取的效 果有很大的局限性，获得有效的抽取规则需要大量的样本学习。 2 3 2 基于包装器归纳方式的信息抽取 包装器归纳方式的信息抽取根据事先由用户标记的样本实例应用机器学习方式的 归纳算法，生成基于定界符的抽取规则。其中定界符实质上是对感兴趣语义项上下文 的描述，即根据语义项的左右边界来定位语义项。该类信息抽取方式和基于自然语言 理解方式的信息抽取技术最大的不同在于仅仅使用语义项的上下文来定位信息，并没 有使用语言的语法约束。采用这种原理的典型的系统有s t a l k e r 1 1 1 2 1 1 3 1 、 s o f t m e a l y l l 4 1 、w m n l l 5 l 。下面根据具体的系统来详细分析这类信息抽取技术。 s 1 a i j ( e r 。 该系统根据用户事先标记的样本页面和用户嵌入式目录树( e m b e d d e dc a t a l o gt r e e ) 形式提供的页面的结构信息，应用逐步覆盖算法( s e q u e n t i a lc o v e r i n ga l g o r i t h m ) ，逐步 归纳生成基于定界符的精确的抽取规则，实现层次信息抽取。此法可处理文本，但不 能处理链接信息。 嵌入式分类树( e c t ) 在该系统中是一个重要的概念，它是用户根据页面结构定 义的嵌套模式，该树形结构一方面描述了页面的逻辑结构，另一方面提供了模式信息 和语义信息( 树中节点的名称) 。下面说明信息抽取过程：系统遍历e c t ，若根节点的 孩子为l i s t 节点则在源文档中应用普通抽取规则抽取出多个对象组成的信息块，然 9 基于网站结构的w e b 信息抽取方法研究 后再在获得的信息块中应用迭代规则实现单个对象的定位，若该l i s t 节点的孩子为 叶节点，则系统在上一步获得的单个对象构成的信息块中执行叶节点对应的抽取规则 获得单个语义项。 该系统中语义的附加是在用户定义嵌入式分类树阶段完成的。信息定位的实质是 使用左右边界实现感兴趣信息的识别。该系统在一定程度上是按结构抽取和按文本抽 取的结合，所以可以抽取复杂的对象。但是规则中的定界符不仅仅是由h t m l 标记组 成，而且还有某类网页经常出现的关键字组成。所以该类信息抽取不但对页面的结构 有所依赖，而且对网页的内容也有所依赖，要想获得精确的抽取规则，必须进行大量 的样本训练。 w i e n 该系统中事先由用户标记样本页面，系统根据页面逻辑结构的不同，使用不同的 启发式归纳算法生成不同的包装器。例如，产生一个h l r t ( h e a d , b o d y , t a i l ) 包装器。 该系统语义和模式信息是用户附加的。通过感兴趣信息的左右边界实现信息的定 位。方式和上面系统类似，本文不作介绍。只是该系统对复杂对象不做处理。 2 3 3 基于o n t o l o g y 方式的信息抽取 该类信息抽取介绍主要利用对数据本身的描述信息实现抽取，对网页结构的依赖 较少。由b r i g h a m y o n gu n i v e r s i t y ( b y l r ) 开发的信息抽取工具【1 6 】中采用了这种方式，另 外q u i x o t e 1 7 1 【1 卅也采用了这种方式。 b y u 在该小组开发的