Web信息抽取技术纵览一 (3)

第四章          分装器生成系统简介

第 4.1. 节         处理结构化和半结构化网页的系统 ...

第 4.1.1. 节      ShopBot

第 4.1.2. 节      WIEN..

第 4.1.3. 节      SoftMealy.

第 4.1.4. 节      STALKER.

第 4.2. 节         处理半结构化和非结构化网页的系统 ...

第 4.2.1. 节      RAPIER.

第 4.2.2. 节      SRV.

第 4.2.3. 节      WHISK.

第 4.3. 节         小结 ...

早期从网站上抽取信息的方法基本上是基于手工操作的。程序员认真研究网站的结构后手工编写代码，开发一个分装器程序，把网页的逻辑特征抽取出来并把他们存入到数据库。 TSIMMIS[13 ， 25 ， 28 ， 29] 系统和“斯坦福 -IBM 多信息源管理系统（ 1995 ）”是比较早的帮助建造分装器程序的框架系统。 TSIMMIS 的目标是以一体化的方式获取不同信息源的信息并且保证所获取信息一致性。其重点是开发支持这种包装过程的语言和工具。

对于数据量大，结构动态变化的网站而言，需要一种更为有效的分装器建造方法。一般说来，数据库领域的人把注意力放在错综复杂的信息如何进行整合，分装器则用手工建造。另一方面， AI 领域的人则把重点放在机器学习的方法如何能用在网站结构的自动学习上。本章将重点介绍分装器的自动或半自动的生成系统。

分装器及其自动生成的复杂度和难易度将取决于网站结构的层次。第 4 .1. 节介绍的系统主要是针对结构化程度相对好的网站。这类系统多数是源自分装器生成领域的研究者。第 4.2. 节介绍了能处理结构缺少规范化的网页。这类系统较多地受到传统的 IE 领域的影响。

第4.1.节                 处理结构化和半结构化网页的系统

本节介绍 ShopBot, WIEN, SoftMealy 和 STALKER 系统。这类系统可以说是属于分装器生成系统，专门用来从网站数据库系统生成的网页。采用分隔符为主的抽取规则，无需用到句法和语义知识，局限于处理比较结构化的数据。

第4.1.1.节         ShopBot

开发者： R. B. Doorenbos, O. Etzioni, D. S. Weld (1996/1997)[17,18] 。

ShopBot 是比价代理系统，专门从网上卖家的网站上抽取信息，因此，比其他系统的局限性要大。其算法主要针对以表单形式提供查询的页面，而且返回的搜索结果是以表格形式显示的产品信息页面。从结果页面中抽取信息的技巧结合了启发式搜索、模式匹配和归纳式学习。

ShopBot 的运行分两个阶段：离线学习阶段和在线比价阶段。在学习阶段，系统分析每个购物网站，获得其符号化描述，然后在比价阶段，利用获得的符号化描述，从网站上抽取信息，找到用户指定的产品的最低价格。

在学习阶段，系统利用简单的启发式方法找到正确的检索表单，学习如何向该表单发送查询请求。学习程序还必须判定查询结果页面的格式。一般包括头部、主体和尾部等三部分。头尾两部分在所有的结果页面中都是一致的，而主体则包含了想要的产品信息。结果页面的格式是通过三个步骤判定的：

第 1 步：获取“找不到产品”的失败页面。用不存在的词（如“ xldccxx-no-product” ）作为关键字查询数据库，然后分析返回的页面。

第 2 步：找到头尾部分。用可能存在的产品名称去查询数据库，通过分析返回的页面找到头尾部分。

第 3 步：判定包含产品信息的主体格式。首先用 HTML 标记和字串对可能的产品信息摘要进行定义和表示。网页主体被切分成“逻辑行”，代表“垂直空格分隔” (vertical-space-delimited) 的文本。学习程序用逻辑行比较不同的摘要形式，找到最佳匹配。这样可以找到产品的描述格式，但是不能归纳出信息栏的名称。最关键的价格信息是用手工编码的方法获取的。

第4.1.2.节         WIEN

开发者： N. Kushmerick (1997) [33,34] 。

“分装器归纳生成环境”（ WIEN-Wrapper Induction Environment ）是辅助分装器生成的工具，为网页的自动分析而设计，受到 ShopBot 的影响。不过， Kushmerick 是第一个提出分装器归纳生成这一术语的。其方法不只局限于某一领域，适用于所有包含表格信息的结构化文本，也不只是用于 HTML 文本。

这种方法可以处理被他们称之为具有 HLRT 结构的网页：头分隔符、左右分隔符（在每个待抽取的事实的左右）和尾分隔符。系统寻找标记信息点开始和结尾的统一的分隔符，以及那些把表格信息与其他周围信息分开的分隔符。符合这一规则的页面几乎都是搜索数据库所得的结果页面。

Kushmerick 力图尽量自动化，避免用人工标记样例，因此开发了一系列自动标记样例的方法。标记算法需要输入特定领域（ domain-specific ）的启发学习规则，目标是找到待抽取属性的值。系统虽然需要输入学习规则，但却不管这些规则是如何获得的，可以手工编制。即使是这样，比起标记整个网站来，其工作量要小。

系统采用归纳学习法，从查询结果样例中生成分装器。归纳算法是：把标记好的网页作为输入，然后搜索由“ HLRT 分装器模型”定义的分装器空间（ space of wrappers ），反复尝试所有可能的分隔符，直到找到与标记网页相一致的 HLRT 分装器。系统还采用基于机器学习理论的模型来预测需要学习多少个例子，以保证所生成的分装器的出错几率控制在一特定的范围内。

由于 WIEN 只考虑与待抽取数据紧相邻的分隔符，因此不能包装那些数据不全或信息项次序不固定的网页。系统采用的是多栏（ Multi-slot ）规则，这就意味着能把相关的信息联在一起，而单栏规则只能抽取孤立数据（例如，若一篇文档包含多个姓名和地址，使用单栏规则不能辨认出哪个地址是属于某人的）。

第4.1.3.节         SoftMealy

开发者： C-H. Hsu (1998)[30,31] 。

Kushmerick 之后，有好几个别的系统研发出来，力图改进 WIEN 的分装器归纳算法。 SoftMealy 是一个通过学习分装器学习从半结构化网页中抽取信息的系统。其分装器被称为“非确定有限自动机”（ non-deterministic finite automata ）。这种表达模式和学习算法据说可以处理缺失值、一栏多值和变量改变（ permutations ）的情况。

系统从训练样例中归纳上下文规则。训练样例提供一个有顺序的事实列表以及事实间的分隔符。归纳生成分装器时，把一系列带标记元组（ labeled tuples ）作为输入。这些元组提供了分隔符的位置和事实次序变化的信息。这些信息被归纳为上下文规则作为结果输出。

归纳生成的分装器是一个“非确定有限自动机”。其状态代表待抽取的事实，状态的转换代表定义分隔符的上下文规则。状态的转换由上下文规则的匹配结果来确定。分装器通过识别事实周围的分隔符来抽取事实。

SoftMealy 的规则允许使用通配符，而且能处理信息缺失和次序变化。然而，为了能处理不同次序的事实，系统需要学习其各种可能的次序。总的说来， SoftMealy 的抽取模式比 WIEN 规定的要更有表达能力。

第4.1.4.节         STALKER

开发者： I. Muslea, S. Minton, C. Knoblock. (1998) [42,43,44] 。

STALKER 采用指导学习的算法归纳抽取规则。训练例子由用户提供。用户需选择若干样例页面并把有用的数据（即所谓“ EC 树”的叶子）标记出来。页面被标记好后，系统可生成一符号序列（ the sequence of tokens ），用来表示页面的内容，还生成代表信息点开始的符号索引。符号系列（字、 HTML 标记）和通配符被作为定位标志，用于找到页面上的数据。分装器归纳算法产生抽取规则并表示为简单的标志语法（ landmark-grammars ）。此法可处理文本，但不能处理链接信息。

网页文档用所谓的“内嵌目录”（ Embedded Catalog ）表示。那是一个树形结构，其内部节点或是同构的（ homogeneous ）信息点列表，或是异构信息点元组（ tuples ）。根节点是整篇文档，任一节点的内容代表其父节点内容的一个接续（ subsequence ）。末节点即是用户需要抽取的数据。

STALKER 采用线性覆盖算法（ sequential covering algorithm ）。首先生成线性标志自动机（ landmark automata ）。这些自动机能产生尽可能多的训练正例（ positive training examples ）。该自动机实际上是一个“非确定有限自动机”。其状态的变化只有在字符串输入为了目前状态与下一状态间的转换而被接受时才发生。然后系统试图生成新的自动机以覆盖剩余的例子，一直到所有的训练例子都被覆盖为止。这时， STALKER 返回一个被称之为 SLG （简单标记语法）的解决方法。其每个分支都对应一个学习获得的标记自动机。

STALKER 可以包装有任意层结构的信息源。每个节点的抽取与其子节点独立，因此，文档中信息点的次序是没有关系的。对于信息点缺失或次序多变的文档一样能处理。这就比只能处理固定次序的 WIEN 等系统更灵活。与同样能处理信息点缺失或次序多变文档的 SoftMealy 不同， STALKER 无需把各种可能的次序变化都学习到。

STALKER 采用的规则与 WIEN 的不同，是单栏的。不过由于 STALKER 利用 EC 树把从多栏模板中取出的单个信息点集在一起，因此没有什么缺陷。