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

摘要

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

主权项

1.一种基于实体的自底向上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）对于每一个tT，mM，都以此为分隔在S上做一次划分；（2）对于相邻的子字符串且对应的文本节点在DOM树中深度相差一级的划分，予以合并操作；文本S经过以上划分后得到有序序列S_list = <s₁，s₂，…，s_n>，其中s_iS，且s₁s₂…s_nS；每一个s_i都对应文档D中的一段文本字符串，这里s_i被称为实体；步骤3. 标注实体属性：即赋予S_list中的每个实体一个实体类型的名称；每类Web主题都包含特定的实体类型集，那么给定一个主题，也就确定下来实体类型集A；对于每个实体类型aA，采用一个二级抽取模型，第一级L₁定义查全规则r_a1R₁，第二级L₂定义查准规则r_a2R₂，其中R₁是该主题所有实体类型的查全属性集合，R₂是该主题所有实体类型的查准属性集合；这样做能够很好的将查全率与查准率的相互依赖性拆开，保证信息的最小丢失和最大收益；给定， B代表能够匹配该实体的规则集，A代表匹配B中某条规则后得到的属性标签；具体标注过程如下：将R₁中的每一条规则r_x1在S_list上进行匹配，规则r_x1会将所有匹配它的实体添加x属性，若某一实体s_x匹配r_x1，则将属性x添加到s_x的属性列表中，xA；经过规则集R₁匹配后的实体属性序列可以表示为：将R₂中的每一条规则r_x2在S_list上进行匹配，规则r_x2会将所有匹配它的实体唯一标识x属性，若某一实体s_x匹配r_x2，则s_x的属性唯一确定为x，删除s_x的其它属性，xA；假设s₁的属性被确定为x₁，s_n的属性被确定为x_n，那么经过规则集R₂匹配后的实体属性序列可以表示为：用A_list表示上面的序列，它是一个拥有部分确定属性的实体属性序列；步骤4. 抽取属性序列重复模式：设集合I为所有实体在文本中的索引的集合即Ind = {Index(s_i, D)|iZ⁺}，Z⁺是正整数集合；定义集合AI = {(a, ind)|aA_list, indI}，具体过程如下：选择起始关键属性，即找到(a_k, ind_k)满足：其中，sum函数求出所有被标注包含有a_m属性的实体的索引值的和，count函数计算出被标注为包含a_m属性实体的个数，SN为该主题的实体类型数量；在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_iA，rn为P_r中包含的实体属性数量，则生成的候选模式集合P可以表示为{P₁, P₂, …, P_pn}，P中的每个元素都代表D中唯一的重复模式，pn是从D中抽取出的不同重复模式数量；根据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_p1P₁，a_p2P₂，做集合交运算a_p1a_p2；所以P₁P₂ = <a₁b₁, a₂b₂, …, a_rnb_rn>；对于没有元素的交运算结果，将这两个模式用代替；对于有元素的，将这两个模式予以保留；因此，在算法结束时每组都可能包含一个或者多个结果模式，且大多数结果模式只包含单一属性；少数复杂的模式在交运算之后仍然包含多标签属性，对于这类结果模式，将遵循保证模式内包含最大实体类型数目的原则拆分多标签属性；假设某一结果模式P^c = <x₁, x₂x₃, x₃, x₄>，根据分裂后的信息增益，将其输出为<x₁, x₂, x₃, x₄>；经过完整算法，G可以表示为：其中cn_i是组g_i中包含的结果模式数目，是长度为rn_i的组中的一个结果模式；将G中的结果模式重新按照初始顺序构建为P；选择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)条件的从初始状态到终止状态的最短路径；最后，删除化简后产生重复冗余的模式。