一种基于实体的自底向上Web数据抽取方法

摘要

本发明提供了一种基于实体的自底向上Web数据抽取方法，属于网络数据管理领域，具体步骤包括：选择Web数据页面、划分文本、标注实体属性、抽取属性序列重复模式抽取、化简结果模式；本发明的Web数据抽取方法，可以更广泛的抽取复杂Web页面的结构化数据，有效避免先前抽取技术对页面结构的过度依赖，适应性好，准确度高。

说明书

技术领域

本发明属于网络数据管理领域，特别涉及一种针对Web数据页面的自底向上抽取方法。

背景技术

随着网络信息量的日益扩大，结构单一的Web页面已经不能够满足数据的承载，主题多 样、结构复杂的Web页面数量在当今的互联网络中不断增长。这在拓展人们视线的同时也给 Web数据的应用带来很多问题。Web页面复杂度和噪声信息量与日俱增，甚至同主题、同数 据源的页面都存在很大的偏差，使得网页中高质量的结构化数据越来越难以被有效的分析和 整合，信息的利用率明显下降。所以，从复杂、多样的Web页面中提取信息并将其转换为结 构化数据变得日益重要。然而，如何准确而高效的从无结构化或者半结构化的HTML页面中 抽取结构化数据成为人们研究的课题，同时也是巨大的挑战。近年来，研究出的有代表性的 方法有RoadRunner、ViPER、MDR。除此之外，随着技术的发展，一些在实体领域提出的技 术也被应用到Web数据抽取上面。

RoadRunner方法需要事先选择一些Web页面作为它的训练集，然后通过比较这些HTML 文档内容上的异同来发现样本的结构特征，进而由此推导出包装器的抽取规则。RoadRunner 方法较比人工标注的方式明显提高了扩展性，并且可以处理一些嵌套的结构。但是，对于训 练集未涉及的页面该方法依然不能很好的适用。

ViPER是基于页面可视化特征的抽取方法，它主要通过模拟人眼对页面的识别过程来完 成抽取。然而，ViPER需要实现建立可视化模型，这将耗费大量的时间，而且当页面有用信 息和噪声混杂分散存在的时候，ViPER的抽取效果也不尽如人意。

MDR方法通过分析包含多记录的单个HTML页面来进行包装器抽取规则的推导，主要 基于页面的DOM树特征，分析出DOM树中节点的重复模式，识别并划分页面中包含的记 录，并以节点路径标识记录中的属性。后来，改进的MDR II方法采用树的结构信息来定位 节点，但无论是MDR还是MDR II均无法摆脱对于页面DOM树的过分依赖，当某一标识下 的属性发生改变时，它们无法保证抽取的准确性。所以，该类方法比较适用于结构简单的页 面抽取，对于复杂的页面并不适合。

近年来，一些研究在这些典型技术的基础上提出了新的方法，但大多是直接或者间接基 于页面结构来推导抽取规则的，所以，这些方法在处理结构复杂、数据分散的Web页面的时 候，查全率会明显的下降。实体抽取技术的发展，给解决这一问题带来了转机，但是目前的 方法更多只关注实体抽取而忽略了它们之间的联系，若要取得高质量的结构化数据还需要很 多工作，但无疑它为我们提供了良好的契机。

发明内容

针对已有Web数据抽取方法的不足，本发明提供了一种基于实体的自底向上的Web数据 抽取方法。

本发明采用的技术方案的具体步骤如下：

步骤1.选择Web数据页面：对于DeepWeb响应页面，需要输入查询词来获得；Web页 面可以看作是由HTML语言描述的文本字符串，使用DOM解析工具(HtmlAgilityPack)将 其解析成为标签和文本；然后，在DOM树中删除所有script节点和comment节点，对HTML 文档进行最基本的去噪并做规范化处理，得到符合XML标准的文档D；D可以表示为：(T， M，S)，其中T是DOM树中所有标签节点的集合，M是DOM树文本节点中的分隔符的集 合，S是DOM树文本节点中除了T和M之外所有的文本字符串。

步骤2.划分文本：对于给定的文档D，按照下面两个条件将S划分为有序的字符串序列：

(1)对于每一个t∈T，m∈M，都以此为分隔在S上做一次划分；

(2)对于相邻的子字符串且对应的文本节点在DOM树中深度相差一级的划分，予以合 并操作；文本S经过以上划分后得到有序序列S_list＝<s₁，s₂，...，s_n>，其中且 每一个s_i都对应文档D中的一段文本字符串，这里s_i被称为实体；

步骤3.标注实体属性：即赋予S_list中的每个实体一个实体类型的名称；每类Web主题都 包含特定的实体类型集，那么给定一个主题，也就确定下来该领域的实体类型集A；对于每 个实体类型a∈A，采用一个二级抽取模型，第一级L₁定义查全规则r_a1∈R₁，第二级L₂定义 查准规则r_a2∈R₂，其中R₁是该主题所有实体类型的查全属性集合，R₂是该主题所有实体类型 的查准属性集合；这样做能够很好的将查全率与查准率的相互依赖性拆开，保证信息的最小 丢失和最大收益；给定B代表能够匹配该实体的规则集，A代表匹配B中某条规则后 得到的属性标签；具体标注过程如下：

(1)将R₁中的每一条规则r_x1在S_list上进行匹配，规则r_x1会将所有匹配它的实体添加x 属性，若某一实体s_x匹配r_x1，则将属性x添加到s_x的属性列表中，x∈A；经过规则

集R₁匹配后的实体属性序列可以表示为：

$\{<\underset{r_{x_{1}1}}{U}{x}_1,\underset{r_{x_{2}1}}{U}{x}_2,...,\underset{r_{x_{n}1}}{U}{x}_n>|x_1,x_2,...,x_n\in A,r_{x_{1}1},r_{x_{2}1},...,r_{x_{n}1}\in R_1\}$

(2)将R₂中的每一条规则r_x2在S_list上进行匹配，规则r_x2会将所有匹配它的实体唯一标识 x属性，若某一实体s_x匹配r_x2则s_x的属性唯一确定为x，删除s_x的其它属性，x∈A。 假设s₁的属性被确定为x₁，s_n的属性被确定为x_n，那么经过规则集R₂匹配后的实体 属性序列可以表示为：

$\{<x_1,\underset{r_{x_{2}1}}{U}{x}_2,...,x_n>|x_1,x_2,...,x_n\in A,r_{x_{1}1},r_{x_{2}1},...,r_{x_{n}1}\in R_1\}$

用A_list表示上面的序列，它是一个拥有部分确定属性的实体属性序列。

步骤4.属性序列重复模式抽取：设集合I为所有实体在文本中的索引的集合即Ind＝ {Index(s_i，D)|i∈Z⁺}，Z⁺是正整数集合；定义集合AI＝{(a，ind)|a∈A_list，ind∈I}，具体过程如下：

(1)选择起始关键属性，即找到(a_k，ind_k)满足：

$(a_k,{\mathrm{ind}}_k)=\arg \left(\min \left(\frac{\mathrm{sum}\left({\mathrm{ind}}_{a_m}\right)}{\mathrm{count}\left(a_m\right)}\right)\right),m\in [1,\mathrm{SN}]$

其中，sum函数求出所有被标注包含有a_m属性的实体的索引值的和，count函数计算 出被标注为包含a_m属性实体的个数，SN为该主题的实体类型数量。

(2)在A_list中从a_k开始遍历，创建一个队列Q记录遍历过的属性序列，每当遇到包含a_k的属性a_x，则将Q中已有的属性序列作为一个重复模式P_r添加到候选模式集合P中， 并将a_x加入队列作为下一个属性序列的开始；若某一序列只包含一个元素，则将其 添加到上一序列，并移除该元素的a_k标签；若P中已经包含P_r，则将P_r的支持参数 Support(P_r)增加1；反之则将P_r支持数初始化为0，重复执行以上步骤直到整个A_list遍历完毕；模式P_r可以表示为<a₁，a₂，...，a_rn>，x_i∈A，rn为P_r中包含的实体属性数量， 则生成的候选模式集合P可以表示为{P₁，P₂，...，P_pn}，P中的每个元素都代表D中唯 一的重复模式，pn是从D中抽取出的不同重复模式数量。

(3)根据rn将P中的模式分组，保证同一组的模式都具有相同的rn，不同组的模式都具 有不同的rn；将经过分组后的P表示为G＝{g_l1，g_l2，...，g_lgn}，l_i是每组模式rn的值， gn是组的数目；对任意组gli中的所有模式做两两交运算，给定两个具有相同rn的模 式P₁＝<a₁，a₂，...，a_rn>，P₂＝<b₁，b₂，...，b_rn>，定义P₁与P₂的交运算如下：对于每对 属性a_p1∈P₁，a_p2∈P₂，做集合交运算a_p1∩a_p2；所以P₁∩P₂＝<a₁∩b₁，a₂∩b₂，...， a_rn∩b_rn>；对于没有Φ元素的交运算结果P_∩，将这两个模式用P_∩代替；对于有Φ元 素的P_∩，将这两个模式予以保留；因此，在算法结束时每组都可能包含一个或者多 个结果模式，且大多数结果模式只包含单一属性；少数复杂的模式在交运算之后仍然 包含多标签属性，对于这类结果模式，将遵循保证模式内包含最大实体类型数目的原 则拆分多标签属性；假设某一结果模式P^c＝<x₁，x₂∪x₃，x₃，x₄>，根据分裂后的信息增 益，将其输出为<x₁，x₂，x₃，x₄>；经过完整算法，G可以表示为：

$\underset{i=1}{\overset{\mathrm{gn}}{U}}\underset{j=1}{\overset{{\mathrm{cn}}_i}{U}}{P}_{{\mathrm{rn}}_{i}j}^c$

其中cn_i是组g_i中包含的结果模式数目，是长度为rn_i的组中的一个结果模式；

将G中的结果模式重新按照初始顺序构建为P。

(4)选择P中全部Support相同且在D中相邻出现的模式，对于每对符合条件的P₁，P₂， 若P₁或P₂具有包含a_k属性的多标签属性且P₁∪P₂∈P，则用P₁∪P₂代替P₁和P₂，并 将Support(P₁∪P₂)增加Support(P₁)；对于那些Support数仍为1且包含较少的实体类 型或者包含较多不确定属性标签的模式删除；最终，通过一个阈值σ控制输出P中符 合条件的结果模式集合P_c，σ是大于0的正整数。

步骤5.化简结果模式：对P_c中的每个模式建立有限自动机，按照模式的序列顺序设立 初始状态和终止状态，每遇到一个特定的属性都会转移到指定的状态；当模式序列遍历结束 时，自动机同时创建完毕，输出满足以下两个条件的序列为化简后的模式：

(a)保证每个属性值被至少访问一次；

(b)该序列是满足(a)条件的从初始状态到终止状态的最短路径；

最后，删除化简后产生重复冗余的模式。

本发明的有益效果：采用本发明的Web数据抽取方法，可以更广泛的抽取复杂Web页面 的结构化数据，有效避免先前抽取技术对页面结构的过度依赖，适应性好，准确度高。

附图说明

图1为本发明总体流程图

图2为本发明实体属性标注流程图

图3为本发明属性重复模式抽取流程图

图4为本发明所选示例页面截图

图5为本发明所选示例化简结果模式自动机示意图。

具体实施方式

下面结合附图对本发明的基于实体的自底向上Web数据抽取方法做进一步详细描述。

实施例：

步骤1、选择Web数据页面：选择流行的机票预订网站“淘宝机票” http://ipiao.taobao.com/2010/home.htm？TBG＝66409.71436.28&ad_id＝&am_id＝&cm_id＝140038 1961b2c34cffa7&pm_id＝作为数据源，航班始发地选择沈阳市，目的地选择深圳，日期选择 2011/5/11，点击搜索返回机票结果页面(见附图4)，将该页面的HTML源代码最为输入。

步骤2、划分文本：完成对结果页面D的预处理后，对D进行文本划分，得到的的文本 序列S_list为<“航班信息(沈阳-深圳)”，”共8个航班信息，共217个机票商家”，”深圳航空”，” ￥2050”，”起(不含税)”，”详情”，”航班信息”，”起抵时间”，”机型”，”机建/燃油”，”价格”，” 联系”，”选择”，”操作”，”深圳航空ZH9828”，”14:25”，”桃仙机场”，”18:25”，”宝安国际机 场”，”319”，”￥965”，”(4.2折)”，”千翼航空”，”海南航空HU7730”，”17:50”，”桃仙机 场”，”23:00”，”宝安国际机场”，”738”，”￥1288”，”(5.6折)”，”乐到网”，”深圳航空 ZH9898”，”09:30”，”桃仙机场”，”13:35”，”宝安国际机场”，”320”，”￥1363”，”(6.0折)”，” 爱特博旅运”，”深圳航空ZH9980”，”19:05”，”桃仙机场”，”23:10”，”宝安国际机场”，”320”，” ￥1363”，”(6.0折)”，”爱特博旅运”，”南方航空CZ6303”，”16:00”，”桃仙机场”，”19:50”，” 宝安国际机场”，”M90”，”￥1749”，”(7.7折)”，”千翼航空”，”南方航空CZ6309”，”18:15”，” 桃仙机场”，”22:20”，”宝安国际机场”，”319”，”￥1749”，”(7.7折)”，”千翼航空”，”南 方航空CZ6311”，”08:30”，”桃仙机场”，”13:45”，”宝安国际机场”，”320”，”￥1749”，”(7.7 折)”，”千翼航空”，”深圳航空ZH9842”，”15:55”，”桃仙机场”，”21:15”，”宝安国际机 场”，”320”，”￥4357”，”(头等舱)”，”天旺航空”>。

步骤3、标注实体属性：订票主题的抽取规则定义如下：

  第一级规则级R₁  第二级规则集R₂ 航班(F)   \C{4，8}([\w\d]{6})？   \C{2}航空\w{2}\d{4}  时间(T)   \d{1，2}[:点]\d{1，2}   ([01][0-9])|(2[0-4])[:点]([0-5][0-9])|(60)  机场(A)   \C{2，8}   \C{2，4}机场  机型(N)   [\d\w\C]{3，5}   (M90)|(波音747)|(A380)  价格(P)   ￥？\d{3，5}(元|RMB)？   ￥\d{3，4}  折扣(D)   \d\？\d折？   [1-9].\d折  舱位(S)   \C{2，3}   \C{2}舱  商家(B)   [\C\d\w]{2，8}   天旺航空|千翼航空  杂项(O)   未匹配以上  ——

为了便于理解，上表中抽取规则以简易的伪正则表达式书写，目的在于体现R₁和R₂规则抽 取意图的差别；特殊的，我们把未匹配任何属性标签的实体标注为O；

(1)S_list经过R₁处理后，得到的A_list如下：

<{O}，{O}，{F， A，N，B}，{P}，{O}，{A，B}，{F， A，N，B}，{F， A，N，B}，{A，B}，{O}，{A，B}，{A， B}，{A，B}，{A，B}，{F}，{T}，{F， A，N，B}，{T}，{F， A，B}，{N，P，B}，{P}，{D}，{F， A，N，B}，{F}， {T}，{F， A，N，B}，{T}，{F， A，B}，{N，P，B}，{P}，{D}，{A，N，B}，{F}，{T}，{F， A，N，B}，{T}，{F， A，B}，{N，P，B}，{P}，{D}，{F， A，N，B}，{F}，{T}，{F， A，N，B}，{T}，{F， A，B}，{N，P，B}，{P}， {D}，{F， A，N，B}，{F}，{T}，{F， A，N，B}，{T}，{F， A，B}，{N，B}，{P}，{D}，{F， A，N，B}，{F}， {T}，{F， A，N，B}，{T}，{F， A，B}，{N，P，B}，{P}，{D}，{F， A，N，B}，{F}，{T}，{F， A，N，B}，{T}， {F， A，B}，{N，P，B}，{P}，{D}，{F， A，N，B}，{F}，{T}，{F， A，N，B}，{T}，{F， A，B}，{N，P，B}，{P}， {A，N，S，B}，{F， A，N，B}>

(2)S_list经过R₂处理后，得到的A_list如下：

<{O}，{O}，{F， A，N，B}，{P}，{O}，{A，B}，{F， A，N，B}，{F， A，N，B}，{A，B}，{O}，{A，B}，{A， B}，{A，B}，{A，B}，{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{D}，{B}，{F}，{T}，{A}，{T}，{A}， {N，P，B}，{P}，{D}，{A，N，B}，{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{D}，{F， A，N，B}，{F}， {T}，{A}，{T}，{A}，{N，P，B}，{P}，{D}，{F， A，N，B}，{F}，{T}，{A}，{T}，{A}，{N}，{P}，{D}， {B}，{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{D}，{B}，{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}， {D}，{B}，{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{S}，{B}>

步骤4、将上面最终得到的A_list做如下操作，以获得模式结合P：

(1)对F，T，A，N，P，D，S，B计算对应实体在页面中的索引平均值，选择最小的索引平 均值ind_k，根据(a_k，ind_k)的对应关系确定a_k＝F；

(2)由此对A_list进行重复模式的抽取，以包含F的属性作为抽取的依据，抽取结果如下：

P＝{<{F， A，N，B}，{P}，{A，B}，{A，N，B}>，<{F， A，N，B}，{A，B}，{A，B}，{A，B}，{A，B}，{A， B}>，<{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{D}，{B}>，<{F}，{T}，{A}，{T}，{A}，{N，P，B}， {P}，{D}，{A，N，B}>，<{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{S}，{B}>}，它们的Support及 rn如下表所示：

  P   rn   Support   <{F， A，N，B}，{P}，{A，B}，{A，N，B}>   4   1   <{F， A，N，B}，{A，B}，{A，B}，{A，B}，{A，B}，{A，B}>   6   1   <{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{D}，{B}>   9   4   <{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{D}，{A，N，B}>   9   3   <{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{S}，{B}>   9   1

(3)根据上表，将P按照rn分组，结果如下：

G＝{{<{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{D}，{B}>，<{F}，{T}，{A}，{T}，{A}，{N，P，B}， {P}，{D}，{A，N，B}>，<{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{S}，{B}>}，{<{F， A，N，B}，{P}， {A，B}，{A，N，B}>}，{<{F， A，N，B}，{A，B}，{A，B}，{A，B}，{A，B}，{A，B}>}}

(a)g₁＝{<{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{D}，{B}>，<{F}，{T}，{A}，{T}，{A}，{N，P， B}，{P}，{D}，{A，N，B}>，<{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{S}，{B}>}。

对其组内模式进行交运算，结果如下：

g₁＝{<{F}，{T}，{A}，{T}，{A}，{N，P，B}，{P}，{D}，{B}>，<{F}，{T}，{A}，{T}，{A}，{N，P， B}，{P}，{S}，{B}>}。

在两个模式中均已存在准确的P、B属性，那么根据最大属性种类增益原则，将多标签属 性分裂后结果如下：

g₁＝{<{F}，{T}，{A}，{T}，{A}，{N}，{P}，{D}，{B}>，<{F}，{T}，{A}，{T}，{A}，{N}，{P}， {S}，{B}>}。

(b)g₂＝{<{F， A，N，B}，{P}，{A，B}，{A，N，B}>}。

由于集合中只有一个模式，所以集合交运算后g₂不变。又由于g₂中不确定属性较多，且 无法通过最大增益原则将多属性标签单一化，故g₂不做处理。

(c)g₃＝{<{F， A，N，B}，{A，B}，{A，B}，{A，B}，{A，B}，{A，B}>}，处理方式同g₂；

(4)经过(3)步骤的处理，得到模式结合P以及对应Support如下表：

  P   rn   Support   1   <{F， A，N，B}，{P}，{A，B}，{A，N，B}>   4   1   2   <{F， A，N，B}，{A，B}，{A，B}，{A，B}，{A，B}，{A，B}>   6   1   3   <{F}，{T}，{A}，{T}，{A}，{N}，{P}，{D}，{B}>   9   7   4   <{F}，{T}，{A}，{T}，{A}，{N}，{P}，{S}，{B}>   9   1

模式1和模式2包含了太多的不确定属性标签且它们的Support为1，故将P₁和P₂判断为噪 声信息，予以删除；因此，得到的结果模式如下：

(a)若σ＝1，P＝{<{F}，{T}，{A}，{T}，{A}，{N}，{P}，{D}，{B}>，<{F}，{T}，{A}，{T}，{A}， {N}，{P}，{S}，{B}>}。

(b)若1＜σ＜7，P＝{<{F}，{T}，{A}，{T}，{A}，{N}，{P}，{D}，{B}>}

两种情况下P的an值均为7。

步骤5、选择P＝{<{F}，{T}，{A}，{T}，{A}，{N}，{P}，{D}，{B}>，<{F}，{T}，{A}，{T}，{A}， {N}，{P}，{S}，{B}>}的情况，对P中的模式进行化简，建立的有限自动机如附图5所示。

最终，得到化简后的结果模式为：

P＝{<{F}，{T}，{A}，{N}，{P}，{D}，{B}>，<{F}，{T}，{A}，{N}，{P}，{S}，{B}>}

步骤6、最终得到的结构化数据见表一：

表一

该数据源的其他页均可以用模式P进行抽取，获得如上表样式的结构化数据。