（计算机应用技术专业论文）web页面分块算法mdsps及其在web信息抽取中的应用.pdf

东北大学硕士学位论文 摘要 w e b 页面分块算法l v l d s p s 及其在w e b 信息抽取中的应用 摘要 随着w e b 的快速发展，如何从w e b 网站中获得想要的信息成为亟待解决的问题， 因此w e b 信息抽取成为必要，w e b 信息抽取技术也成为当今的一个研究热点。w e b 信息抽取需要解决的问题是：如何使信息抽取免受页面结构差异和页面结构变化的影 响，并尽可能地减少人为参与。 针对上述问题，目前出现了一种全新的基于分块的w e b 信息抽取技术，即先将 w e b 页面分成若干个相互独立的语义块，再根据不同的应用，从中选取具有相应语义 特征的语义块进行信息抽取。新的抽取方式不仅有效降低了信息抽取问题的复杂度， 而且大幅度提高了信息抽取的精确度。 本文的研究重点是如何设计并实现一种准确、自动、智能、高效、简单的w e b 页 面分块算法，以及该算法在w e b 信息抽取中的应用。首先本文提出了一种基于h t m l 标签分布统计的w e b 页面分块算法m d s p s ，详细描述了m d s p s 的基本原理、实现 过程，并与现有的两种经典w e b 页面分块算法：h t m l 分块解析方法和v i p s 分块算 法进行分析比较。其次，本文提出了块层次结构获取算法，能够根据m d s p s 分块算 法的分块结果，得到w e b 页面的块层次结构。本文同时给出了块语义特征分析方法， 能够简单有效地提取块的语义特征。利用块语义特征分析方法，以块结构层次为基础， 针对不同的w e b 应用，能够从大量的语义块中快速准确选取相应的特定语义块，提高 w e b 信息抽取的准确度。最后，通过展示m d s p s 在本课题组所实现的基于分类本体 的w e b 信息集成系统n e u - w i i s 中的具体应用，详细描述w e b 页面分块在w e b 信息 抽取中的作用，由此证明v l d s p s 分块算法和基于分块的w e b 信息抽取方式具有良好 的性能，能够满足实际应用的需求。 关键词：w e b 信息抽取；分块算法 标签统计：层次结构；块语义特征分析 一 东北大学硕士学位论文 a b s t r a c t p a g es e g m e n t a t i o na l g o r i t h mb a s e do nh t m l m a r k d i s t r i b u t i o ns t a t i s t i c sa n dt h ea p p l i c a t i o no f w e bi f o r m a t i o ne x t r a c t i o n 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 fw e b ，h o wt og e tt h ei n f o r m a t i o ny o uw a n tb e c o m e st o b ear e s o l v i n gp r o b l e m s oi ti sn e c e s s a r yf o rw e bi n f o r m a t i o ne x t r a c t i o n ，w h i c hi sa l s o r e g a r d e da st h eh o ts p o to ft h er e s e a r c ha tp r e s e n t t h ep r o b l e mn e e d e dt ob er e s o l v e di s h o wt om a k et h ei n f o r m a t i o na b s t r a c t i o np r e v e n tt h ei n f i u e n c ef r o mt h ed i f f e r e n c ea n dt h e c h a n g eo f p a g e ss t r u c t u r e a n dr e d u c et h ep e r s o n sa n t i c i p a t i o na sf a ra sp o s s i b l e a i m i n ga tr e s o l v i n gt h ep r o b l e m ，an e wt e c h n o l o g yo fw e bi n f o r m a t i o ne x 仃a c f i o n b a s e do nb l o c k sa p p e a r s i ts p l i tt h ew e bp a g et oi n d e p e n d e n ts e m a n t i cb l o c k s t h e n a c c o r d i n gt od i f f e r e n ta p p l i c a t i o n , i t c h o o s e sb l o c k sw h i c hh a v er e l a t i v e l ys e m a n t i c c h a r a c t e rt oe x t r a c ti n f o r m a t i o n t h en e wm e t h o dn o to n l yr e d u c e st h ec o m p l e x i t yo ft h e p r o b l e m se f f i c i e n t l y , b u ta l s oi m p r o v e st h ep r e c i s i o n t h er e s e a r c hs t r e s so ft h et h e s i si sh o wt od e s i g na n di m p l e m e n tp a g e s ls e g m e n t a t i o n a l g o r i t h mw h i c hi se x a c t ，a u t o m a t i c ，i n t e l l i g e n t ，e f f i c i e n ta n ds i m p l e f i r s t ，t h et h e s i s p r o p o s e sp a g es e g m e n t a t i o na l g o r i t h mb a s e d o nh t m lm a r kd i s t r i b u t i o n s t a t i s t i c s ， d e s c r i b e st h ep r i n c i p l ea n dt h ep r o c e s so fi m p l e m e n t a t i o n ，a n dc o m p a r e si tw i t ht w oc l a s s i c p a g es e g m e n t a t i o na l g o r i t h m s ，w h i c ha r eh t m ls e g m e n t a t i o na n a l y s i sa l g o r i t h ma n dv i p s s e c o n d ，t h et h e s i sp r o p o s e st h ea l g o r i t h mg e t t i n gt h eb l o c k ss t r u c t u r e ，w h i c hc o u l dg e tt h e b l o c k ss t r u c t u r ea c c o r d i n gt ot h er e s u l to f m d s p s b e s i d e s ，i tp r o p o s e st h ea n a l y s i sm e t h o d o fb l o c k ss e m a n t i cc h a r a c t e r s a d o p t i n gt h em e t h o d ，i ti sa b l et os e l e c tt h es p e c i f i co n e s f r o ml o t so f s e m a n t i cb l o c k sf a s ta n da c c u r a t e l y a tl a s t , b ys h o w i n gt h ea p p l i c a t i o ni nw e b i n f o r m a t i o ni n t e g r a t i o ns y s t e mb a s e do nt h ec l a s s i f y i n go n t o l o g y , i td e s c r i b e st h ea f f e c t so f t h ep a g es e g m e n t a t i o ni nw e bi n f o r m a t i o ne x t r a c t i o ni nd e t a i l i tp r o v e sm d s p sa n dt h e w a yo fw e bi n f o r m a t i o ne x t r a c t i o nh a v eg o o dp e r f o r m a n c e s ，a n da l s ot h ed e m a n do fa c t u a l a p p l i c a t i o n s 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 ；p a g es e g m e n t a t i o na l g o r i t h m ；m a r ks t a t i s t i c s ；l e v e l s t r u c t u r e ；b l o c ks e m a n t i c sc h a r a c t e r i s t i ca n a l y s i sm e t h o d l i i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：霸主镊 日 期：上柙f ，j 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不问意。) 学位论文作者签名：渤# 镇 签字日期：6 、f 导师签名：移幺 签字日期：力哟、1 东北大学硕士学位论文 第一章前言 1 1 问题的提出 第一章前言 随着i n t e m e t 的飞速发展，w e b 已经发展成为一个全球的、巨大的、分布和共享 的信息空间，并且仍在不断快速增长中。毫无疑问，w e b 已经成为人们获取信息的主 要资源，但是要想从w e b 上获取条有用信息的难度却越来越大。这是因为随着w e b 数据的不断增长和异构数据源集成的应用，导致了大量半结构( s e i r l i s t r u c t u r e d ) 数据【i 刭 的产生，具体而言就是w e b 页面。目前绝大多数的w e b 页面是通过h t m l 语言来展 现，而h t m l 语言的一个显著特点是结构隐含、不规则或不完整，导致由h t m l 语 言编写的w e b 页面缺乏对数据本身的描述，不含清晰的语义信息，模式也不太明确， 结果使得w e b 上的数据处于杂乱无序的状态，数据集成性菲常差，应用程序无法直接 解析、获取并利用w e b 上海量的信息，给w e b 应用的建立造成了极大的困难。 如何从浩繁的w e b 数据中抽取出有用的信息成为众多研究工作希望解决的问题， 因此出现了w e b 信息抽取技术，它通过“包装”现有的w e b 信息源，将网页中的信 息以更为结构化、语义清晰的方式发布出来，为面向w e b 的信息系统利用w e b 中的 数据提供了可能【3 1 。i n t e m e t 具有的海量、异构、动态变化等特性使w e b 信息抽取不同 于传统信息抽取，面临巨大的困难。首先，面对呈几何级数增长的巨大的w e b 信息空 间，如何自动高效地处理海量w e b 信息是w e b 信息抽取的一个难点：其次，如何消 除w e b 页面间的异构性，从w e b 页面中准确识别所需的信息点成为一个较大的难点； 最后，w e b 网站的动态更新使得保持信息抽取的适应性也成为一个有待解决的问题。 传统的w e b 信息抽取直接以w e b 页面作为信息抽取的对象，这种处理方式面临 着巨大的挑战。在信息量日益增长的同时，w e b 页面提供信息的密集程度也不断的增 强，w 曲页面需要能在有限的空间中提供更多的信息，因而变得越来越复杂【”。首先 w e b 页面中往往包含着大量的“噪声”。例如：为了增强用户交互性而加入的脚本 ( s c r i p t ) ，为了便于用户浏览而加入的导航链接，以及出于商业因素所加入的广告链 接等【5 1 ，本文称之为“硬噪声”。此外，与传统的文本文档相比，w e b 文档在语义的内 聚性上难以得到保证，即一个w e b 页面中往往包含多个语义无关的部分【，由于实际 的信息抽取往往是针对某一类的应用，这时w e b 页面中所包含的与当前应用无关，又 东北大学硕士学位论文 第一章前言 不同于“硬噪声”的内容就称为“软噪声”。“软噪声”并非固定不变，是个相对的概 念，因为对w e b 信息的需求不同，导致“软噪声”的具体内容也不同，因此在某些应 用看来是噪声的东西，正是其他应用所需要的。 针对上述问题，目前出现了一种全新的基于分块的w e b 信息抽取技术，即先将 w e b 页面分成若干个相互独立的语义块，再根据不同的应用，从中选取具有相应语义 特征的语义块进行信息抽取。基于分块的w e b 信息抽取机制的思想核心在于：w e b 信 息抽取的对象不再是直接的w e b 页面，而是w e b 页面所包含的特定语义块。这种方 式不仅有效降低了信息抽取问题的复杂度，而且大幅度提高了精确度，显然这种抽取 机制更为合理。要实现基于分块的w e b 信息抽取，前提就是实现一种w e b 页面分块 算法。 1 2 研究的主要问题 基于分块的w e b 信息抽取技术作为一种全新的w e b 信息抽取技术，为w e b 信息 抽取技术的发展开辟了新的领域，而作为基于分块的w e b 信息抽取技术底层支持的 w e b 页面分块算法，现在已经成为国内外研究的热点。 为了设计并实现一种准确、自动、智能、高效、简单的w e b 页面分块算法，以及 如何在w e b 信息抽取中得以应用，需要研究如下几方面问题： ( 1 ) 确定w e b 页面文档和w e b 页面语义内容间的对应关系。首先，目前绝大多数 w e b 页面文档都是基于h t m l 的，x m l 仅占很少的一部分，因此主要针对h t m l 文 档进行分析。由于h t m l 语言本身包含大量的标签，具有灵活的使用方式，用它编写 出来的h t m l 文档形式复杂多样，是典型的半结构化数据，无法直接解析。其次， w e b 页面本身所包含的语义内容繁杂，是多语义内容的集合，包含大量的“噪声”， 并且各个不同w e b 页面问的内容组织方式也千差万别，给w e b 页面语义内容分析也 带来巨大的困难。如何发现并根据w e b 页面语义内容的分布规律，确定半结构化的 h t m l 文档和w e b 页面语义内容间的对应关系，是实现w e b 页面分块算法的研究基 础。 ( 2 ) 建立w e b 页面语义内容结构模型。根据h t m l 文档和w e b 页面语义内容间的 对应关系，建立相应的w e b 页面语义内容结构模型，要求模型能够准确体现w e b 页 面语义内容的分布规律，方便w e b 页面分块算法实现。 ( 3 ) 实现w e b 页面分块算法。根据w e b 页面语义内容结构模型，设计并实现相应 一2 东北大学硕士学位论文第一章前言 的w e b 页面分块算法。算法应该满足下列要求：能实现w e b 页面的准确分块，具 有可用性；能实现w e b 页面的自动分块，适用于机器自动化处理，具有实用性； 能够处理各种不同类型的w e b 页面，解决w e b 页面的多样性问题，具有自适应性； 能够高效地拆分w e b 页面，提高w e b 应用系统的响应速度，具有时效性；要求 分块结果具有层次结构，能够满足不同w e b 应用的需求；要求算法简单，便于编程 实现，具有简单性。 ( 4 ) 在w e b 信息抽取中应用w e b 页面分块算法。基于分块的w e b 信息抽取技术有 两个基本点：一是将w e b 页面拆分成若于个相互独立的语义块；二是根据不同的应用， 从中选取具有相应语义特征的语义块进行信息抽取。如果只是简单的将w e b 页面拆分 为一系列的基本语义块，并获取块的层次结构，仍然无法直接应用于w e b 信息抽取， 因此必须找到一种简单有效的方法，能够准确描述语义块的基本特征，才能针对不同 w e b 应用的不同需求，快速准确地选取具有相应语义特征的语义块进行信息抽取。 1 3 本文的主要工作 本文在分析了w e b 页面特征的基础上，建立了基于分块的w e b 页面语义内容结 构模型，设计并实现了基于h t m l 标签分布统计的分块算法m d s p s ( p a g e s e g m e n t a t i o na l g o r i t h mb a s e do nh t m lm a r kd i s t r i b u t i o ns t a t i s t i c s ) ，并与现有的两种 经典页面分块算法：h t m l 分块解析方法【6 1 和v i p s t ( v i s i o n b a s e dp a g es e g m e n t a t i o n a l g o r i t h m ) 分块算法进行分析比较。本文同时给出了块层次结构获取算法，能够根据 m d s p s 分块算法的分块结果，得到w e b 页面的块层次结构。本文还提出了块语义特 征分析方法，能够简单有效地提取块的语义特征。利用块语义特征分析方法，以块层 次结构为基础，针对不同的w e b 应用，能够从大量的语义块中快速准确选取相应的特 定语义块，提高w e b 信息抽取的准确度。最后，通过展示m d s p s 在本课题组所实现 的基于标准分类本体的w e b 信息集成系统n e u w i i s 中的具体应用，详细描述分块在 w e b 信息抽取中的作用，由此证明m d s p s 和基于分块的w e b 信息抽取机制具有良好 的性能，能够满足实际的需求。 一3 一 末北大学硕士学位论文第= 章研究基础 第二章研究基础 2 1w e b 信息抽取技术概述 2 。1 1 信息抽取 信息抽取i e ( i n f o r m a t i o n e x t r a c t i o n ) 直接从自然语言文本中抽取事实信息，并以 结构化的形式描述信息，供信息查询、文本深层挖掘、自动回答问题等应用，为人们 提供有力的信息获取工具。近十年来，信息抽取逐步发展成为自然语言处理领域的一 个重要分支，涉及到了深层次的语言理解、篇章分析与推理、多语言文本处理、w e b 信息描取、名实体识别等自然语言研究领域。通过系统化、大规模地定量研究和评测 推动了自然语言处理研究的发展，促进了自然语言处理研究与应用的紧密结合。近年 来，信息抽取的处理对象也扩展到了语音、图像、视频等其他媒体类型的数据。可以 说，信息抽取已成为当前自然语言处理和相关领域的研究热点。信息抽取技术对搜索 引擎、网络信息过滤和信息安全、自动问答系统、机器翻译、文本挖掘、企业智能信 息系统等许多应用领域具有至关重要的作用。 2 ：1 2w 曲信息抽取 w e b 信息抽取，就是以w e b 信息为信息源的信息抽取。w e b 信息有如下特点：信 息不由任何组织和个人控制，没有固定的数据模型；信息的组织是任意的，只要能在 w e b 上展现即可；信息的内容和表现方式是动态变化的；信息量巨大并且增长迅速8 引。 正是由于w e b 信息存在上述特点，导致w e b 信息抽取比传统的信息抽取更为复杂。 w e b 信息抽取承接了传统信息抽取技术研究的成果，其核心是将分散在i n t e r n c t 上的半结构化的h t m l 页面中隐含的信息点抽取出来，并以更为结构化、语义更为清 晰的形式表示，为用户在w e b 中查询数据、应用程序直接利用w e b 中的数据提供便 利吼 将信息从嘲页中抽取出来通常是由包装器( w r a p p e r ) 完成的，所谓包装器就是一 个能够将数据从w e b 页面中抽取出来并且将它们还原为结构化的数据的软件程序。 包装器是在分析一定数量的样本文档( 这个数量一般较少) 而生成的，一旦生成 包装器是在分析一定数量的样本文档( 这个数量一般较少) 而生成的，一旦生成 4 东北大学硕士学位论文第二章研究基础 第二章研究基础 2 1w e b 信息抽取技术概述 2 1 1 信息抽取 信息抽取i e ( i n f o r m a t i o n e x t r a c t i o n ) 直接从自然语言文本中抽取事实信息，并以 结构化的形式描述信息，供信息查询、文本深层挖掘、自动回答问题等应用，为人们 提供有力的信息获取工具。近十年来，信息抽取逐步发展成为自然语言处理领域的一 个重要分支，涉及到了深层次的语言理解、篇章分析与推理、多语言文本处理、w e b 信息抽取、名实体识别等自然语言研究领域。通过系统化、大规模地定量研究和评测 推动了自然语言处理研究的发展，促进了自然语言处理研究与应用的紧密结合。近年 来，信息抽取的处理对象也扩展到了语音、图像、视频等其他媒体类型的数据。可以 说，信息抽取已成为当前自然语言处理和相关领域的研究热点。信息抽取技术对搜索 引擎、网络信息过滤和信息安全、自动问答系统、机器翻译、文本挖掘、企业智能信 息系统等许多应用领域具有至关重要的作用。 2 1 2w e b 信息抽取 w 曲信息抽取，就是以w e b 信息为信息源的信息抽取。w e b 信息有如下特点：信 息不由任何组织和个人控制，没有固定的数据模型；信息的组织是任意的，只要能在 w e b 上展现即可：信息的内容和表现方式是动态变化的；信息量巨大并且增长迅速】。 正是由于w e b 信息存在上述特点，导致w e b 信息抽取比传统的信息抽取更为复杂。 w e b 信息抽取承接了传统信息抽取技术研究的成果，其核心是将分散在i n t e m e t 上的半结构化的h t m l 页面中隐含的信息点抽取出来，并以更为结构化、语义更为清 晰的形式表示，为用户在w e b 中查询数据、应用程序直接利用w e b 中的数据提供便 利【3 】o 将信息从网页中抽取出来通常是由包装器( w r a p p e r ) 完成的，所谓包装器就是一 个能够将数据从w e b 页面中抽取出来并且将它们还原为结构化的数据的软件程序。 包装器是在分析一定数量的样本文档( 这个数量一般较少) 而生成的，旦生成 一4 东北大学硕士学位论文 第二章研究基础 后，就可以利用这个包装器对与样本文档具有类似结构的所有文档进行自动的信息抽 取。 w e b 信息抽取研究需要解决的问题是：如何构造尽可能准确、健壮和通用的 w r a p p e r ，使其免受网站结构差异和页面结构变化的影响，并尽可能地减少人为参与。 因此w e b 数据抽取的核心就是构造用于抽取的w r a p p e r 。 2 1 3w e b 信息抽取的应用 w e b 信息抽取的个直接应用就是帮助人们在纷繁复杂的w e b 信息海洋中快速准 确地查找所需信息，加快人们获取信息的速度，从而提高生产效率。另外，半结构化 数据抽取所得到的结构化信息可以直接被其它的应用程序利用，进一步完成信息搜索 ( i n f o r m a t i o ns e a r c h ) 、数据挖掘( d a t am i n i n g ) 、机器翻译( m a c h i n et r a n s l a t i o n ) 、 文本摘要( t e x t d i g e s t ) 等后续w e b 信息处理，具有广阔的应用价值和前景。 2 1 4w e b 信息抽取技术的分类 传统的构造w r a p p e r 的方式是手工编码，既费时费力、容易出错，还需要专家完 成，手工生成的包装器如t s i m m i s t l 0 j 和w 4 f “】，于是许多半自动化或自动化的方法 被提出，半自动和自动生成的包装器如w i l l s k t ”，w i e n ”1 ，s t a l k e r t l 3 1 等。 对w e b 信息抽取方法的分类角度很多，如根据自动化程度分为手工、半自动和全 自动。根据方法的原理可分为机器学习、基于自然语言理解、o n t o l o g y 方法和h t m l 方法等。本节从方法的原理出发，介绍几种w e b 信息的抽取技术。 2 1 4 1 基于自然语言理解方式的信息抽取 自然语言处理技术通常用于自由文本的信息抽取，需要经过的处理步骤包括：句 法分析、语义标注、专有对象的识别( 如人物，公司) 和抽取规则。具体地说就是把 文本分割成多个句子，对一个句子的句子成分( p a r to f s p e e c h ，p o s ) 进行标记，然后 将分析好的句子语法结构和事先定制的语言模式( 规则) 匹配，获得句子的内容。其 实就是利用予句结构、短语和子句间的关系建立基于语法和语义的抽取规则实现信息 抽取。规则可以由人工编制，也可从人工标注的语料库中自动学习获得。这类信息抽 取主要适用于源文档中含有大量文本的情况( 特别针对于合乎文法的文本) 。 基于自然语言的信息抽取技术是将w e b 文档视为文本进行处理的( 主要适用于含 有大量文本且句子完整、适合语法分析的w e b 页面) ，其缺点也较为明显： 5 一 东北大学硕士学位论文 第二章研究基础 ( 1 ) 抽取的实现没有利用w e b 文档独特于普通文本的层次特性，抽取规则表达能力 有限，缺乏健壮性：获得有效的抽取规则需要大量的样本学习，达到全自动的程序较 难，而且速度较慢，对于操作网上海量数据来说这是一个大问题。 ( 2 ) 只支持记录型的语义模式结构，不支持复杂对象的抽取。 ( 3 ) 由于w e b 页面中的文本通常不是结构完整的句子，所以适用范围较窄。 2 1 4 2 基于包装器归纳方式( w r a p p e ri n d u c t i o n ) 的信息抽取 包装器由一系列的抽取规则以及应用这些规则的程序代码组成。通常，一个包装 器只能处理一种特定的信息源。从几个不同信息源中抽取信息，需要一系列的包装器 程序库。形式化地，每一类w e b 页面对应一个包装器。 包装器归纳法可以自动分析出待抽取信息在网面中的结构特征并实现抽取，其主 要思想是用归纳式学习方法生成抽取规则，该方法首先由n i c h o l a s k u s h m e r i c k 于1 9 9 6 年提出。 与自然语言处理方式比较，包装器较少依赖于全面的句子语法分析和分词等复杂 的自然语言处理技术，更注重于文本结构和表格格式的分析。 使用包装器的困难在于： ( 1 ) 包装器的针对性强，可扩展性( s c a l a b i l i t y ) 较差。由于一个包装器只能处理一 种特定的信息源，所以若从几个不同的信息源中抽取信息，就需要一系列的包装器集。 这样使得信息抽取的工作量巨大。 ( 2 ) 可重用性( r e u s a b i l i t y ) 差。包装器对页面结构的依赖性强，当出现一类新的 w e b 页面或旧的页面结构发生了变化后，原来的包装器就会失效，无法从数据源中获 得数据或得到错误的数据。这使得一个新的问题出现，即包装器的维护问题。 ( 3 ) 缺乏对页面的主动理解。目前的包装器主要依赖于原网页或其后台数据库的模 式，基本上是一种数据模式的还原，缺乏对数据语义的主动理解。 2 1 4 3 基于o n t o l o g y 方式的信息抽取 按照s t a n f o r da i 专家t o mg r u b e r 的定义，o n t o l o g y 是为了帮助程序和人共享知 识的概念化规范，在知识表达和共享领域，o n t o l o g y 描述了在代理之间的概念和关系 ( c o n c e p t sa n dr e l a t i o n s ) 1 4 1 。 基于o n t o l o g y 的信息抽取主要利用了对数据本身的描述信息实现抽取，对网页结 构的依赖较少。由b r i d a my o n gu n i v e r s i t y 开发的信息抽取工具就采用了这种方法。 采用该方法，事先要由领域知识专家采用人工的方式书写某一应用领域的 6 东北大学硕士学位论文 第二章研究基础 o n t o l o g y ( 包括对象的模式信息、常值、关键字的描述信息，其中常值和关键字提供 了语义项的描述信息) 。并且根据o n t o l o g y 中常值和关键字的描述信息产生抽取规则， 对每个无结构的文本块进行抽取获得各语义项的值。另外系统根据边界分隔符和启发 信息将源文档分割为多个描述菜一事物不同实例的无结构的文本块。还将抽取出的结 果放入根据o n t o l o g y 的描述信息生成的数据库中。 基于o n t o l o g y 方式的最大的优点是对网页结构的依赖较少，只要事先创建的应用 领域的o n t o l o g y 足够强大，系统可以对某一应用领域中各种网页实现信息抽取。主要 缺点是； ( 1 ) 需要由领域专家创建某一应用领域的详细清晰的o n t o l o g y ，工作量大。 ( 2 ) 由于是根据数据本身实现信息抽取，因此在减少了对网页结构依赖的同时，增 加了对网页中所含的数据结构的要求，如要求内容中包含时间、日期、d 号码等有一 定格式的内容【h 】。 ( 3 ) 从大量异构的文档中提取公共模式工作量繁重。并且不支持对超链接的处理。 2 1 4 4 基于h t m l 结构的信息抽取 该类信息抽取技术的特点是根据w e b 页面的结构定位信息。在信息抽取之前通过 解析器将w e b 文档解析成语法树，通过自动或半自动的方式产生抽取规则，将信息抽 取转化为对语法树的操作实现信息抽取。 2 1 5w e b 信息抽取存在的问题 通过对现有的w e b 信息抽取技术的分析，可以发现w e b 信息抽取面临着挑战， 这些挑战同时也是有待进一步研究和解决的问题。 ( 1 ) 抽取规则一直是信息抽取过程的一个重要环节。目前各类信息抽取技术中生成 规则的依据主要有五类：结构特征、位置特征、显示特征、语义特征和引用特征。这 些方式各有缺陷，如何将基于结构和基于文本方式有效地结合起来是信息抽取需要解 决的一个问题。 ( 2 ) 机器学习往往通过大量的样本学习来提高获取规则的自动化程度，这意味着系 统需要经过较长时间的学习才能获得较好的查准率。抽取规则的适应性较差，缺乏健 壮性是现有信息抽取技术所面临的难点。现有的技术均采用定制的语言表达抽取规则， 缺乏通用性，系统不易升级，且不易与其他基于w e b 的应用集成。如何处理效率与健 壮性之间的矛盾是一个重要问题。 7 东北大学硕士学位论文 第二章研究基础 ( 3 ) 性能较好的信息抽取技术需要用户的大量参与，自动化程度不高；而自动化程 度高的信息技术其准确率和适应性较低，实用性较差。这两者之间的矛盾也需要解决。 包装器的生成与维护问题随着信息抽取的不断应用而突显出来。由于w r a p p e r 与 h t m l 文档格式的紧密联系，使得w r a p p e r 应该有着较强的适应能力和可扩展性。如 何最大程度地利用已有的资源( 程序、数据等) ，通过最小程度地改造适应新的信息源， 增强系统的可扩展性也是一个重要问题。 2 1 6w e b 信息抽取的关键技术 2 1 6 1 抽取规则的生成 从对信息抽取技术的分析中不难看出，所有的抽取技术都在抽取规则的生成上下 尽了功夫。抽取规则对于抽取工作的自动化程序至关重要，同时又对抽取的质量有着 重大的影响，因此是信息抽取系统的一个关键组成部分。 抽取规则描述的是要抽取信息的各种特征和规律，作用是要确定需要抽取哪些信 息，用于在w e b 上识别和定位待抽取的信息。 抽取规则的生成方法主要有两类： ( 1 ) 人工获取方式。这种方式是人类专家依靠自身的知识和技术，审阅一定量的待 处理文本文档，归纳出相关信息出现的规律，然后按照信息抽取系统内部对抽取规则 格式书写的要求表述抽取规则。显然，人类专家掌握相关领域知识的水平和技能状态 对系统的性能起着相当关键的作用。另外，w e b 页面更新( 内容或格式的变化) 或者 出现新一类的w e b 页面时，都需要人工识别，更新或重新生成抽取规则，这样导致了 系统可扩展性较差。 ( 2 ) 自动学习方式。自动学习的方式也需要一定的人工成分。主要是依靠人工在训 练集合中的文档中用适当的方式标出相关信息的出现，生成系统自动学习抽取规则需 要的训练集( t r a i n i n ge x a m p l e ) 。学习模块就可以在训练数据的基础上运行了a 2 1 6 2 机器学习与归纳学习方法 在w e b 信息抽取过程中，面对的是海量的数据，如果采用人工的方式生成抽取规 则或是抽取信息并不现实。因此，机器学习被应用于这个领域，并在多年的应用中发 挥着重要的作用。 人们一直在努力使机器能够模仿人的思维进行自动学习，r s h a n k 曾说“一台计 算机若不会学习，就不能称为具有智能”，机器学习( 自动获取新的事实及新的推理算 一8 一 东北大学硕士学位论文 第二章研究基础 法) 是使计算机具有智能的根本途径。 用于w e b 信息抽取的机器学习方法有很多，如符号化学习法，归纳逻辑设计法 ( i l p ) ，包装器归纳法，统计法和语法归纳法。目前很多信息抽取系统都是结合了归 纳学习的方法，在实用过程中相当广泛，也较易实现。 归纳学习( i n d u c t i v el e a r n i n g ) 是一种基于假设的，从特殊情况推导一般规则的 学习方法，其主要思路是，如果归纳出来的规则能够解释观察到的实例，或者在新实 例出现时能做出准确的预测，那么这种归纳则是成功的。可以说，人类知识的增长主 要得益于归纳学习方法。归纳学习存在很强的可证伪性，对于认识的发展和完善具有 重要的启发意义。 2 2 h t m l 简介 目前大多数w e b 页面都是基于h t m l 的，x m l 仅占很少的一部分，为了能正确 分析w e b 页面，必须先了解h t m l 。 2 2 1h t m l 特点 h t m l 是h y p e r l i n kt e x tm a r k u pl a n g u a g e 的缩写，即超文本标记语言。 1 9 8 9 年，欧洲物理量子实验室( c e r n ) 的信息专家蒂姆伯纳斯李发明了超 文本链接语言，使用该语言能轻松地将一个文件中的文字或图形连到其它的文件中去， 这就是h t m l 的前身。1 9 9 1 年，蒂姆伯纳斯李在c e r n 定义了h t m l 语言的第 一个规范，之后成为w 3 c 组织为专门在互联网上发布信息而设计的符号化语言规范。 h t m l 语言简单，功能强大，支持不同数据格式的文件( 文本、图像、动画等) 嵌入，其主要特点有【1 6 j ： ( 1 ) 简单性：h t m l 语言易学易用； ( 2 ) 可扩展性：h t m l 语言被广泛应用，功能不断增强，标签集也在不断扩充，h t m l 采取予类元素的方式，使系统扩展方便。 ( 3 ) 平台无关性：h t m l 可以使用在广泛的平台上，这也是w w w 盛行的原因之一。 2 2 2h t m l 标签 h t m l 是一种标记语言，既然是一种语言，就必然有它自己的语法。其实，h t m l 的语法很简单，就是用一些预定义的描述性的标记符( 或称为标签) 来标识页面元素、 东北大学硕士学位论文第二章研究基础 结构、格式等，修饰用户实际要显示的文本，描述文档结构，以在w e b 上发布。 h t m l 标签具有如下特征： ( 1 ) 单标签：某些标签称为“单标签”，因为它只需单独使用就能完整地表达意思， 这类标记的语法是： 。最常用的单标签是 ，它表示换行。 ( 2 ) 双标签：大多数标签称为“双标签”，它由“始标签”和“尾标签”两部分构成， 必须成对使用。始标签前加一个斜杠( ) 即成为尾标签。其中始标签告诉w e b 浏览 器从此处开始执行该标记所表示的功能，而尾标签告诉w e b 浏览器在这里结束该功 能。这类标记的语法是： 文本内容叫标签名称 。其中“内容”部分就是 要被这对标记施加作用的部分。 ( 3 ) 标签属性：许多单标记和双标记的始标签内可以包含一些属性，其语法是： 。各属性之间无先后次序，属性也可省略( 即取默 认值) ，例如单标记 表示在文档当前位置画一条水平线，一般是从窗口中当前行 的最左端一直画到最右端。 h t m l 标签是区分文本各个组成部分的分界符，用来把h t m l 文档划分成不同的 逻辑部分( 或结构) ，如段落、标题和表格等。标签描述了文档的结构，它向浏览器提 供该文档的格式化信息，以传送文档的外观特征，浏览器则根据这些信息进行解释并 实现。可见h t m l 的核心就是这些标记，而h t m l 的标记比较繁多，而且各个版本 还有所不同。 2 2 3h t m l 文档结构 用h t m l 编写的文档称为h t m l 文档，以纯文本文件( a s c i i ) 的方式存储，其 中没有包含任何与平台或程序专用的信息。自1 9 9 0 年以来h t m l 就直被用作w o r l d w i d ew e b 的信息表示语言，它提供超文本链接，支持在文本中嵌入图像、声音、动画 等不同格式的文件。h t m l 是一种描述文档结构的语言，而不能描述实际的表现形式， 因此使用h t m l 语言描述的文档，需要通过测览器解释执行，才能显示出效果。 h t m l 文档的大致结构如图2 1 所示。从h t m l 的文档结构来看，整个文件处于 h t m l 标签对 与饥i 喇l 之间， 用以声明这是h t m l 文件，让浏 览器识别并正确处理此h t m l 文档。文档分为两大部分，由 5 5 称为 开头部分，i 扫 至 称为正文部分。基本上两者各有适用的标记，如 只可出现于开头部分，它所标示的是文件的标题，会出现于浏览器顶部。开 1 0 东北大学硕士学位论文 第二章研究基础 头部分用以存载重要资讯，而只有正文部分会被显示，所以大部分标签会运用于正文 部分，如 、 等标签。 2 2 4h t m l 文档组成 部分外，邦存在h t ? v l l 文档的正文 部分，故又称为正文文本。 超链接文本，点击后具有页面跳转功能的特殊文本，被包含在 标签对 中，能够从一个w e b 页面链接到另一个w e b 页面或是w e b 页面的特定部分，一 般用于页面链接或是页面导航。 ( 2 ) h t m l 标签，以( 为基本特征，主要用于h t m l 文档的排版。 ( 3 ) 脚本代码，包含在 h t m l 标签对中，由浏览器解释执行来 实现一些特殊功能，以j a v a s c r i p t 代码为主。 ( 4 ) 其它，主要是指样式表c s s 。c s s 是c a s c a d i n gs t y l es h e e t 的简写，译为“层叠 样式表单”。样式表c s s 在网页中占着极重要的地位，c s s 几乎可以定义所有的网页 元素，最常见的有：定义字体大小、消除超链接下划线积超链接变色等。 2 3w 曲页面分块算法 基于内容的文本检索、过滤和分类、聚类等技术取得了巨大的进展，信息检索和 w e b 挖掘的研究正朝着精