论文部分内容阅读
【摘 要】本文给出一种Web页面的数据结构描述方式，比对所需信息的字符串序列，对通用型框架结构和数据域进行划分，經规则化处理后可以对web网页自动地生成模板，从而达到抽取信息的目的。
【关键词】信息抽取；通用框架；算法设计
1.引言
计算机和计算机网络的发展和普及，使得网络逐渐成为信息交流的关键平台。为了人们在海量的网络信息中更加便捷地获取所需信息，有必要对同领域信息的抽取、汇总、集成，可以建立对应领域的信息库。
Web动态网页由服务器根据请求从数据库中选取数据并嵌入到通用模板而生成，缺乏结构和语义信息的描述，其中包含的信息不易被一般应用程序直接获取。因此，如何将网页中的数据抽取出来就变得非常迫切。Web页面的信息抽取技术为实现这一目标提供了新的途径[1]。
2.Web信息抽取的过程设计
2.1信息抽取
信息抽取（Information Extraction）是从文本包含中识别出用户所需的部分信息，并将其转换为结构化、有特定组织形式的数据集合的过程。
2.2 Web 页面信息的数据结构的定义
Web网页的基本元素用三类标签来描述，分别是开始标签、结束标签以及文本内容。Web网页的数据结构是用字符串序列、标签树两种结构来描述。字符串序列是用开始标签、结束标签以及文本内容构成的一种线性数据结构；标签树用开始标签和文本内容表示网页层次结构。
2.3 Web 信息抽取过程的设计
Web 信息抽取方法关键环节为通用框架结构检测、模板抽取。图 1 是Web 信息抽取的过程图。
Web 信息抽取是将包含用户所需信息的 Web 网页中的数据自动提取到一个结构化的数据集内的信息处理过程。Web 信息抽取针对有价值的文本进行结构分析，其效率和质量较高，更注重工程性和可操作性，也更容易面向实际应用[2]。
3.实现WEB信息抽取的关键技术
3.1 抽取规则——构建通用型框架
通用型框架的建构以比对字符串序列异同的方式进行，对通用型框架结构和数据域进行划分。其中，通用型框架是指与web网页呈现的主要内容无关的部分，如导航条、头尾信息、广告信息和 flash特效等。数据域是指web网页中除了通用型框架以外的内容，将数据域的字符串序列进一步转换成标签树结构，就得到数据的样本集合。
通用型框架处理过程中检测网页间共有的且与网页实质内容无关的信息，对去除通用型框架后得到的数据域信息进行信息抽取时，准确率会有所提高。具体操作是，首先进行页面分区，将网页划分成不相交的区域的过程。然后定义区域树用树状结构对页面分区的结果进行表示。树的根结点对应于整个网页，父结点的区域由各子结点区域组成。接下来，确定结点的分区级别，得到该结点对应的区域时进行的页面分区次数。区域树的分区级别指树的深度。为区域树选定合适的分区级别将有利于检测到更佳的通用型框架结构。再定义通用型框架结构。将网页间共有的、与网页实质内容无关的头信息、尾信息、广告、浏览导向条以及 flash 等内容信息称为通用型框架结构。用双序列比对算法对网页字符串序列进行比对，将最佳的相似字符串作为通用型框架结构。算法流程如下[3，4]：
（1） 对变量max、x和y进行初始化。max 表示局部最大值，y 和x 分别表示矩阵当前行及其前一行。
（2） 计算得分矩阵。该过程由以下三步迭代完成。
（2.1）
其中p（i+1，j+1）为字符串匹配函数，当字符串匹配时取值c，否则，可取值d（d<0）；g为间隔罚分。
（2.2）当p（i+1， j+1）<0时，如果max （2.3）令x=y。
（3）计算最佳相似字符串的长度 ，其中， 为调节参数。
（4）得到通用框架。位于Pm- 与Pm范围中的最佳相似字符串就是通用框架。算法中，在找到最长的匹配字符串后，需要对参数进行调节，从而得到最佳的相似字符串作为通用型框架结构。
3.2模板抽取
Web 上的动态页面有两种来源，一类是超链接方式，另外一类需要填写 Web 页面上的表单（Form），然后提交给网站服务器后动态生成，这类页面无法直接获取，也就是深网页。根据动态 Web 页面的构成模板可以将其分为A、B两大类。A 类：整个页面内容包括很多项数据，这些数据对应于一个实体的各项属性，组成了一条完整的记录。B类：页面中包含了多条记录，每条记录又包含多个数据项，即该条记录的属性项各条记录的属性项基本相同。
模板抽取是对样本间各种匹配与不匹配的部分进行搜索和划分，经规则化处理后可以得到模板。模板抽取过程如图2所示：
本文给出的抽取算法是：输入一个样本集合，每一次比较包装器树和一个样本网页树并产生一棵新的包装器树，然后再利用该包装器树和另一个样本网页树进行比较直至所有的样本网页比较完毕后生成最终的包装器树。其流程描述如下：
（1）设定任一基准Pjz∈V集合；
（2）对P∈V-{Pjz}，从根结点开始进行深度遍历，设Rjz=Root（Pjz），Rb=Root（P）。
（2.1）Rjz和Rb为叶结点，若Rjz.Name≠Rb.Name，令Rjz。Name待提取信息；
（2.2）Rjz和Rb均不为叶结点：
（2.2.1） Rb！=NULL，且Rjz.Name≠Rb.Name，令Rb为其第一右兄弟节点，重复（2.2.1），否则转（2.2.2）；
（2.2.2）若Rjz.Name≠Rb.Name，Rjz，Rb为其第一左子结点，转（2.1），否则转（2.2.3）； （2.2.3）若Rb==NULL，令Rjz.Name为设定值；
（2.3）當Rjz 和Rb 中有且只有一个是叶结点时，
（2.3.1） 若Rb 非空，令Rb 为其第一右兄弟结点，重复（2.3.1），否则转（2.3.2）；
（2.3.2） 若Rb 为空，令Rjz. Name =，否则，转（2.1）；
（2.4）若Rjz 非空，令Rjz 为其第一右兄弟结点，重复（2.1），否则，转（3）；
（3）重新遍历Pjz ，对相同的子树进行合并。
通过对网页的通用型框架结构进行定义，在信息抽取算法中引入了通用型框架结构检测阶段，采用序列比对算法对同类网页所共有的、与网页表达的实质内容无关的信息进行检测，除掉了通用型框架结构的网页信息，对信息抽取更加有利。该算法可以对数据密集的真实网页自动地生成模板、抽取信息，既不局限于人为定制的测试网页也不依赖于网页内容的先验知识[5]。
4.实验结果与分析
4.1 评价标准
实验中，我们采用召回率和查准率作为评价的指标对信息抽取系统进行评价。从直观上说，召回率可以理解为，从网页中正确抽取出来的数据项的比例，查准率可以理解为，被抽取出来的数据项中正确的比重。
当我们评价一个信息抽取系统时，为了综合评价系统的性能，应同时考虑这两个指标。为了能够直接地同时比较召回率和查准率，设定β为权重参数，其值反应在评测时侧重召回率还是查准率，由系统预设。若需要设定表明查准率更重要，就设定 β> 1，反之，召回率更重要则设定β< 1。在信息抽取系统中，通常设定β==1，以反应召回率和查准率的重要性是等同的。
4.2 实验设计与分析
本文实验采用的网页来自于真实的站点中的动态 Web 网页，其中包含的信息纷繁复杂，包括 HTML 页面的头信息、尾信息、广告、浏览导向条、flash 等，实验中，我们预先对网页中标签缺失的情况进行修正以便建立标签树。
在数据集合上应用带序列比对的信息抽取算法，对参数θ进行调节，根据抽取结果为算法选择合理的参数值。表 1 结果显示的是θ取不同值时的召回率和查准率。
对参数θ取不同的值分别进行实验，根据实验结果为算法选择合理的参数值，为后绪模板抽取实验做好准备。图3为表1对应的曲线图。
在实验召回率与查准率对照图即图3 中，纵坐标表示召回率和查准率，横坐标表示参数θ，如图所示，当θ的取值为 1.2时抽取信息的效果最优。实验证明了本文上述抽取算法的有效性。
5.结论
web网页的信息抽取过程中采用序列比对的方式进行通用型框架结构检测，剥离网页中的冗余信息，有利于模板抽取的精确度的提高。实验中把真实网站的数据密集型网页作为样本，对抽取算法在数据量和抽取准确率等方面进行了测试和比较，结果充分证明了算法的有效性。
参考文献：
[1]张鹏程，李必信，李雯睿. 时间属性序列图： 语法和语义.软件学报，2010，Vol.21（11）： 2752-2767.
[2]刘凯鹏，方滨兴.一种基于社会性标注的网页排序算法.计算机学报，2010，Vol.33（6）： 1014-1023.
[3]陈传夫，唐琼，于媛，吴志强等.网络上科学信息的时效性测量.情报学报，2009， Vol.28（4）： 610-617.
[4]刘冬宁，汤庸.时态数据库时间轴的动态逻辑模型.软件学报， 2010， Vol.21（4）：694-701.
[5]寇月，李冬，申德荣，于戈，聂铁铮.D-EEM： 一种基于DOM 树的Deep Web 实体抽取机制. 计算机发展与研究，2010，Vol.47（5）： 858-865.
基金项目：
广西教育厅科研课题（201106LX606）。
作者简介：
杨 凤（1981-），女，湖南常德汉寿县人，硕士，讲师，主要研究方向为：数据挖掘。
【关键词】信息抽取；通用框架；算法设计
1.引言
计算机和计算机网络的发展和普及，使得网络逐渐成为信息交流的关键平台。为了人们在海量的网络信息中更加便捷地获取所需信息，有必要对同领域信息的抽取、汇总、集成，可以建立对应领域的信息库。
Web动态网页由服务器根据请求从数据库中选取数据并嵌入到通用模板而生成，缺乏结构和语义信息的描述，其中包含的信息不易被一般应用程序直接获取。因此，如何将网页中的数据抽取出来就变得非常迫切。Web页面的信息抽取技术为实现这一目标提供了新的途径[1]。
2.Web信息抽取的过程设计
2.1信息抽取
信息抽取（Information Extraction）是从文本包含中识别出用户所需的部分信息，并将其转换为结构化、有特定组织形式的数据集合的过程。
2.2 Web 页面信息的数据结构的定义
Web网页的基本元素用三类标签来描述，分别是开始标签、结束标签以及文本内容。Web网页的数据结构是用字符串序列、标签树两种结构来描述。字符串序列是用开始标签、结束标签以及文本内容构成的一种线性数据结构；标签树用开始标签和文本内容表示网页层次结构。
2.3 Web 信息抽取过程的设计
Web 信息抽取方法关键环节为通用框架结构检测、模板抽取。图 1 是Web 信息抽取的过程图。
Web 信息抽取是将包含用户所需信息的 Web 网页中的数据自动提取到一个结构化的数据集内的信息处理过程。Web 信息抽取针对有价值的文本进行结构分析，其效率和质量较高，更注重工程性和可操作性，也更容易面向实际应用[2]。
3.实现WEB信息抽取的关键技术
3.1 抽取规则——构建通用型框架
通用型框架的建构以比对字符串序列异同的方式进行，对通用型框架结构和数据域进行划分。其中，通用型框架是指与web网页呈现的主要内容无关的部分，如导航条、头尾信息、广告信息和 flash特效等。数据域是指web网页中除了通用型框架以外的内容，将数据域的字符串序列进一步转换成标签树结构，就得到数据的样本集合。
通用型框架处理过程中检测网页间共有的且与网页实质内容无关的信息，对去除通用型框架后得到的数据域信息进行信息抽取时，准确率会有所提高。具体操作是，首先进行页面分区，将网页划分成不相交的区域的过程。然后定义区域树用树状结构对页面分区的结果进行表示。树的根结点对应于整个网页，父结点的区域由各子结点区域组成。接下来，确定结点的分区级别，得到该结点对应的区域时进行的页面分区次数。区域树的分区级别指树的深度。为区域树选定合适的分区级别将有利于检测到更佳的通用型框架结构。再定义通用型框架结构。将网页间共有的、与网页实质内容无关的头信息、尾信息、广告、浏览导向条以及 flash 等内容信息称为通用型框架结构。用双序列比对算法对网页字符串序列进行比对，将最佳的相似字符串作为通用型框架结构。算法流程如下[3，4]：
（1） 对变量max、x和y进行初始化。max 表示局部最大值，y 和x 分别表示矩阵当前行及其前一行。
（2） 计算得分矩阵。该过程由以下三步迭代完成。
（2.1）
其中p（i+1，j+1）为字符串匹配函数，当字符串匹配时取值c，否则，可取值d（d<0）；g为间隔罚分。
（2.2）当p（i+1， j+1）<0时，如果max
（3）计算最佳相似字符串的长度 ，其中， 为调节参数。
（4）得到通用框架。位于Pm- 与Pm范围中的最佳相似字符串就是通用框架。算法中，在找到最长的匹配字符串后，需要对参数进行调节，从而得到最佳的相似字符串作为通用型框架结构。
3.2模板抽取
Web 上的动态页面有两种来源，一类是超链接方式，另外一类需要填写 Web 页面上的表单（Form），然后提交给网站服务器后动态生成，这类页面无法直接获取，也就是深网页。根据动态 Web 页面的构成模板可以将其分为A、B两大类。A 类：整个页面内容包括很多项数据，这些数据对应于一个实体的各项属性，组成了一条完整的记录。B类：页面中包含了多条记录，每条记录又包含多个数据项，即该条记录的属性项各条记录的属性项基本相同。
模板抽取是对样本间各种匹配与不匹配的部分进行搜索和划分，经规则化处理后可以得到模板。模板抽取过程如图2所示：
本文给出的抽取算法是：输入一个样本集合，每一次比较包装器树和一个样本网页树并产生一棵新的包装器树，然后再利用该包装器树和另一个样本网页树进行比较直至所有的样本网页比较完毕后生成最终的包装器树。其流程描述如下：
（1）设定任一基准Pjz∈V集合；
（2）对P∈V-{Pjz}，从根结点开始进行深度遍历，设Rjz=Root（Pjz），Rb=Root（P）。
（2.1）Rjz和Rb为叶结点，若Rjz.Name≠Rb.Name，令Rjz。Name待提取信息；
（2.2）Rjz和Rb均不为叶结点：
（2.2.1） Rb！=NULL，且Rjz.Name≠Rb.Name，令Rb为其第一右兄弟节点，重复（2.2.1），否则转（2.2.2）；
（2.2.2）若Rjz.Name≠Rb.Name，Rjz，Rb为其第一左子结点，转（2.1），否则转（2.2.3）； （2.2.3）若Rb==NULL，令Rjz.Name为设定值；
（2.3）當Rjz 和Rb 中有且只有一个是叶结点时，
（2.3.1） 若Rb 非空，令Rb 为其第一右兄弟结点，重复（2.3.1），否则转（2.3.2）；
（2.3.2） 若Rb 为空，令Rjz. Name =，否则，转（2.1）；
（2.4）若Rjz 非空，令Rjz 为其第一右兄弟结点，重复（2.1），否则，转（3）；
（3）重新遍历Pjz ，对相同的子树进行合并。
通过对网页的通用型框架结构进行定义，在信息抽取算法中引入了通用型框架结构检测阶段，采用序列比对算法对同类网页所共有的、与网页表达的实质内容无关的信息进行检测，除掉了通用型框架结构的网页信息，对信息抽取更加有利。该算法可以对数据密集的真实网页自动地生成模板、抽取信息，既不局限于人为定制的测试网页也不依赖于网页内容的先验知识[5]。
4.实验结果与分析
4.1 评价标准
实验中，我们采用召回率和查准率作为评价的指标对信息抽取系统进行评价。从直观上说，召回率可以理解为，从网页中正确抽取出来的数据项的比例，查准率可以理解为，被抽取出来的数据项中正确的比重。
当我们评价一个信息抽取系统时，为了综合评价系统的性能，应同时考虑这两个指标。为了能够直接地同时比较召回率和查准率，设定β为权重参数，其值反应在评测时侧重召回率还是查准率，由系统预设。若需要设定表明查准率更重要，就设定 β> 1，反之，召回率更重要则设定β< 1。在信息抽取系统中，通常设定β==1，以反应召回率和查准率的重要性是等同的。
4.2 实验设计与分析
本文实验采用的网页来自于真实的站点中的动态 Web 网页，其中包含的信息纷繁复杂，包括 HTML 页面的头信息、尾信息、广告、浏览导向条、flash 等，实验中，我们预先对网页中标签缺失的情况进行修正以便建立标签树。
在数据集合上应用带序列比对的信息抽取算法，对参数θ进行调节，根据抽取结果为算法选择合理的参数值。表 1 结果显示的是θ取不同值时的召回率和查准率。
对参数θ取不同的值分别进行实验，根据实验结果为算法选择合理的参数值，为后绪模板抽取实验做好准备。图3为表1对应的曲线图。
在实验召回率与查准率对照图即图3 中，纵坐标表示召回率和查准率，横坐标表示参数θ，如图所示，当θ的取值为 1.2时抽取信息的效果最优。实验证明了本文上述抽取算法的有效性。
5.结论
web网页的信息抽取过程中采用序列比对的方式进行通用型框架结构检测，剥离网页中的冗余信息，有利于模板抽取的精确度的提高。实验中把真实网站的数据密集型网页作为样本，对抽取算法在数据量和抽取准确率等方面进行了测试和比较，结果充分证明了算法的有效性。
参考文献：
[1]张鹏程，李必信，李雯睿. 时间属性序列图： 语法和语义.软件学报，2010，Vol.21（11）： 2752-2767.
[2]刘凯鹏，方滨兴.一种基于社会性标注的网页排序算法.计算机学报，2010，Vol.33（6）： 1014-1023.
[3]陈传夫，唐琼，于媛，吴志强等.网络上科学信息的时效性测量.情报学报，2009， Vol.28（4）： 610-617.
[4]刘冬宁，汤庸.时态数据库时间轴的动态逻辑模型.软件学报， 2010， Vol.21（4）：694-701.
[5]寇月，李冬，申德荣，于戈，聂铁铮.D-EEM： 一种基于DOM 树的Deep Web 实体抽取机制. 计算机发展与研究，2010，Vol.47（5）： 858-865.
基金项目：
广西教育厅科研课题（201106LX606）。
作者简介：
杨 凤（1981-），女，湖南常德汉寿县人，硕士，讲师，主要研究方向为：数据挖掘。