Web数据抽取（精选7篇）
Web数据抽取 篇1
随着互联网的出现,Web文档的信息抽取逐渐成为亟待解决的问题。一个Web文档就是一个网页,网页与纯文本的结构差别很大,主要表现为网页中存在大量的标记,这些标记将网页要显示的文本内容分隔开来。大量的标记为网页信息抽取提供了更多可利用的信息,从而可以开发各种不同于传统信息抽取的方法对网页进行信息抽取。
常见的动态网页是由相应数据库中结构化的数据值嵌入模版生成的。EXALG系统也是将动态网页中的模版推导出来,然后利用推导得到的模版来进行同类Web文档上数据抽取工作。该系统初看起来是一个很成功的模版推导系统,但经验证发现该系统还存在着一定的不足。本文正是在EXALG的基础上,提出了改进的抽取算法,即EXALG+算法。
1 数据类型定义
一个页面的模板和内容是由数据类型(Data Types)和数据值,也即数据实例(Instance)所构建而成的。数据格式是多种属性通过一种固定的序列进行排列而成。其中每种属性都可能是诸如字串,可选项或分离项等其它数据形式,由此,可以对数据类型作出递归定义。其中,分离项和可选项是数据抽取技术中通用的定义。
1.1 基本定义
定义1.1:基本数据类型由符号β表示。它描述了一个标记串,是一个页面文本的基本单元。在本文中,标记定义为一个单词(Word)或一个HTML的固有标签。
该数据类型的实例为各种标记(Token)所组成的字串,有dom(β)={s|s从属于string}。特别地,定义一个特殊的字串,记做Φ,表示为空字串的数据类型,也可以称之为NULL数据类型。
定义1.2:若T1,T2,…,Tn是数据类型,则序列集合
类型
定义1.3:如果T为数据类型,则集合{T}也是一个类型。称集合{T}是由类型T通过集合构造器构造而成的类型,有dom({T})={e1e2,…,ei|e从属于dom(T)}。
类型{T}的实例为元素{e1,e2,…,em}的集合,其中,ei(1≤i≤m)均为类型T的一个实例。
由此,本文中将类型的实例称作“值”,将符号“<>”和“{}”称作类型构造器符号,将元组构造器和集合构造器统称为类型构造器,并通过记号“<>”和“{}”来区分。
1.2 分离项和可选项
一般来说,一个模板的建立主要由两种构造器以及构造器所使用的基本类型组成。这两种构造器一般分别为元组构造器和集合构造器。另外,在网页页面中同时还普遍存在着两种其它形式的类型构造器,分别为可选项和分离项两种类型构造器。
例如,在浏览Chinapub网站的时候看到的图书信息,这些书中有的是国内作者编著的书籍,有的是翻译过来的书籍。后一种书籍中会有“译者”这个选项,则其中“译者”就可以看作是可选项;而相应的国内作者所著的书籍中,有时候也会有中文版和外文版。如果在这本书籍的介绍页面当中仅可能出现一种版式,就是分离项的形式。
定义1.4:如果T为数据类型,则可选项(T)?也是一种数据类型,称为可选项类型。有dom((T)?)=dom(T)∪{Φ}={ei|ei∈dom(T)∪Φ}。并称数据类型(T)?是由类型T通过可选项构造器构造而成。
定义1.5:如果T1,T2都是数据类型,则(T1|T2)也是一种数据类型,有dom((T1|T2))=dom(T1)∪dom(T2)={axi|ali∈dom(T1),or a2i∈dom(T2)},称为分离项类型。其中(T1|T2)是由类型T1,T2通过分离项构造器构造而成。
每一种数据类型都可以用数据类型树来抽象表示,而且该树具有一定的层次结构,称这种用来表示数据类型的树为抽象模式树(Abstract Schema Tree,AST)。
1.2 页面生成模型
本节给出由动态页面产生模板的页面生成模型。如图1所示,一个值X,通过使用一个模板T而被编码到一个实际页面中。用λ(T,X)表示编码页面结果。
定义1.6:一个模式S的模板,即将S中的每一个的类型构造器τ映射到一个有序的标记串集合T(τ)中,同时有如下特性。
1)若τ是一个n维元组构造器,则T(τ)是一个标记串的序列,形如
2)若τ是一个集合构造器,则T(τ)是一个标记串。
为区分不同的模板,把模板T记做TS,用于表示该模板是为模式S作作的定义。也就是说,在编码函数λ(T,X)给定的时候,将模式S的实例X嵌入到模板T上,而此时,可以使用编码函数,对该实例X可以按下列方式嵌入。
第一,如果X是基本类型β,则λ(T,X)就作为x自身输出到页面上。
第二,如果X为n维元组的形式,形如
第三,如果X是形如{e1,e2,…,em}τs的一个集合,则λ(T,X)为一个有序标记串输出到页面上,形如λ(T,e1)Sλ(T,e2)S…λ(T,em)。其中T(τs)=S。
第四,如果X是形如(X)?的可选项,λ(T,X)输出的实例为X或空字串Φ。
第五,如果X为形如X=(X1|X2)的分离项,则函数λ(T,X)为λ(T,X1)和λ(T,X2)二者其中的一个输出到页面上。
1.3 数据抽取
本文中的数据抽取是针对Web文档进行的,是一种根据网页的相似性结构自动找到网页中的数据并归纳出抽取规则的完全自动化的抽取方法。网页中的许多标记和文字的出现常常是频繁的,所以可以根据这些标记形成等价类,推导出生成网页的结构模板,并利用这个模板抽取需要的数据。
1.3.1 数据抽取定义
定义1.7:给定一个具有n个页面的集合P,其中Pi=λ(T,xi)(1
一般来说,从一个大的互联网站点给定的一个实际页面集合,在页面编码中,人工选择正确的模板和数据值时一般不会有任何疑问。而要达到的目标恰恰是解决实际网页的抽取问题,也即能够生成被“人”认为是正确的模板和数据值。
如上所述,为了将页面模板推导出来,可以将页面中的所有标记加以识别区分,判断标记是模板标记值还是数据值。将所有属于模板的标记区分出来后,再利用这些标记完成模板的建立和其后的数据抽取。因此,为了将数据标记和模板标记区分开来,可以利用页面中的标记的不变/变动特性来达到区分的效果。同一类网页所使用的模板是固定不变的,而变化部分则是嵌入到这些模板标记中的数据值,因此,通过分析网页中的标记是否具有变动性质就可以完成区分工作。但是,实际工作依然很困难。
第一,模板标记中的标记值和数据集合中的标记值可能相同,也就是会出现同样的标记扮演不同角色的情况。
第二,在页面中出现的可选项和分离项使得不变/变动的性质难以区分,从而使得模板推导更加复杂。
分离项可能具有多种表示方式,比如,“姓名”或“地址”就可能会出现由于语言习惯或地域的不同而使用不同的表示方式。同样的,日期的表示格式等也属于此类问题,而且表示方法更多:可以表示成“日期/月份/年份”或是“月份/日期/年份”等。
因此,在实际的模板推导中由于这些问题将会导致最终的推导结果出现很多不同可能的模板。此时与这些模板相对应的抽取出来的数据也就不尽相同。也就是所谓的存在冲突模式(Ambiguity Schema)。目前,已经证明了想要推导出一个无冲突的模式属于一个NP完全问题。因此,抽取问题的关键,在于如何找到一个更好的或者说最佳的模板用于数据抽取。
1.3.2 数据抽取原理
EXALG是由Arvind与Hector二人于SIGMOD2003提出的数据抽取系统。该方法使用了类似RoadRunner的模型,希望将生成Web文档的模板推导出来,然后再根据得到的模板,来抽取采用同样结构的Web文档中的相关数据值。
这两种方法的归纳方式不同。EXALG不是逐个比较两个网页中的标记,而是提出了出现向量(Occurrence Vector)和等价类(E-quivalence Class)的概念。通过统计最大最频繁的等价类和角色区分来推导模板。EXALG对于给出页面集合,可以发现页面中所隐含的模板,并通过模板将数据抽取出来。
根据Arvind二人提供的数据和他们发布的EXALG系统的实际使用情况,可以发现EXALG对于原来已有的其它方法来说有了很大的进步;而本文给出的抽取方法,对于抽取的数据在正确性和完整性方面做得更加完善。
本文的抽取方法,是受EXALG的启发得到,所以称之为EXALG+方法。它可分为两个阶段。在第一个阶段用于发现与生成输入页面的未知模板中相同的类型构造器相联系的标记的集合。在第二个阶段则使用上面生成的集合推导出模板。然后,推导得到的模板被用来抽取页面的编码值。以上两个阶段的工作完全由机器完成,是无需人工参与的过程。
第一个阶段,利用出现频繁程度作为向量,用来表示一个标记串在所有网页中的出现频率,并且利用原作者提出的等价类概念,即具有相同出现向量的标记串,聚集到同一个有序的标记串集合中。由于等价类中的所有标记串在相同模板的作用下,会产生同样的出现频率,因此,利用这种特点将所有合法的等价类寻找出来,然后将这些等价类中的标记串转换成最后的模板。
可以将HTML文档看作一棵DOM树。首先,将页面中所有相同的字串根据其DOM树路径位置的不同来区分其扮演的角色,将其称为特定标记串。然后,将所有扮演相同角色的特定标记串按其出现次数组成出现向量,然后将所有具有相同出现向量的特定标记串聚合在一起,形成一个等价类。在这一步骤中,可能会出现一些不合法的等价类,利用第三步将这些不合法的等价类去除。这些不合格等价类在被过滤掉的同时释放该类所包含的所有特定标记串,并将特定标记串中一些与页面意义不一致的个体过滤掉。这一步利用了当特定标记串出现在不同等价类的区间位置不同而具有不同的意义这一特性,可以把这些具有相同值的特定标记串进一步地区分开来,并反复形成新的等价类,过滤掉不合法的等价类,得到一个最频繁出现的等价类集合。到此为第一个阶段阶段,称为等价类生成阶段。本文的主要改进工作都是在这个阶段完成的。对应于这部分的模块称之为等价类生成模块(Equivalence Class Generation Module:ECGM)。随后,将这些等价类作为输出传送到第二个阶段的模板分析模块(Template Analysis Module),由这个模块产生最后的输出。其流程如图2所示。
第二个阶段,即模板建立和值抽取模块。该模块的输入是一个由第一个阶段生成的频繁等价类集合和一个使用标记串描述的页面集合,其输出是一个模板和一个对应页面值的集合。该模块由两个子模块组成,模板生成子模块和值抽取子模块。对于数据抽取技术,一旦获得了正确的模板之后,值抽取是一个非常直观的过程,在此不作赘述。
这些频繁等价类集合中,存在一个最重要的等价类,<1,1,…,1>,将其称为基本等价类。该等价类的特殊性在于,该集合中所有的标记串出现各个页面仅一次,比如常见HTML文档中的
等标记串组合均属此列。另外,一般来说等标记串通常是一个页面的开始标记串和结束标记串,因此,该基本等价类的页面的范围往往是最广泛的,模板构建模块即由此等价类开始构建模板。然后利用先深搜索方式,对于每个等价类的非空区间位置,判断是否为数据嵌入位置,或者该区间是否嵌入了另外一个等价类。如果该位置为数据嵌入位置,则跳转到该等价类的下一个非空的区间位置;如果该位置为一个等价类的嵌入位置,则进入嵌入等价类的非空区间再次进行判断,直到将所有的等价类的非空区间遍历完全,即可构造出一个完整的页面模板。
1.4 小结
文章给出了数据抽取过程中需要的基本定义,描述了数据抽取所基于的页面生成模型。同时给出了EXALG+这种数据抽取方法的基本流程,并给出了这种方法的抽取流程图。
参考文献
[1]Xi W P,Li X,Jiang K,et al.Information Extraction Technology for Web Forums[J].Computer Engineering,2005,31(4):34-37.
[2]Chinchor N,Marsh E.MUC-7Information Extraction Task Definition(version5.1)[C].Proceedings of the Seventh Message Understanding Conference,1998:210-221.
[3]宋静静,李振坤.基于Wrapper技术的Web数据处理系统研究[J].计算机应用研究,2004(12):298-300.
[4]李效动,股毓清.基于DOM的Web信息提取[J].计算机学报,2002,25(5):526-533.
[5]张绍华,徐林昊,杨文柱.基于样本实例的Web信息抽取[J].河北大学学报:自然科学版,2001(4):431-437.
基于DOM的Web数据抽取研究 篇2
随着Internet的快速发展, Web上的数据信息急剧增加, 成为了世界上规模最大的公共数据资源。目前虽然搜索引擎为用户查找信息提供了简便的方法, 但它只是提高了Web文档的检索效率, 只能根据用户提交的关键词返回一组网址, 用户必须逐一浏览网址对应的Web页, 采用人工的方式定位最终信息, 现有的搜索引擎本身不能直接定位到所需的数据, 更谈不上为数据增加语义。XML技术出现之后, 因为其定义严格, 语法明确, 结构良好, 已经迅速成为互联网信息表示的事实标准, 通过把HTML文档转换成XHTML, 借助于DOM分析技术, 可以方便从中提取有用信息。
1 WEB数据抽取
Web信息抽取是一种从Web文档中抽取出有用信息的技术, 可以大大的缩短了对资料的整理时间, 为信息检索提供方便, 有利于现实文档的存档管理。我们可以利用行业信息模型和领域特征做主题搜索, 在收集信息时去除领域无关的信息, 在信息检索时实现更优秀的查询扩展, 从而提高搜索结果的查全率和查准率, 有效解决通用搜索系统给出的检索结果往往过于繁杂, 用户甄别信息价值的时间长问题。主题搜索利用逐渐成熟的文本分类技术, 去除用户不关心数据, 具有更多的针对性, 减少搜索、浏览时间中的比重, 使其满足人们对信息的精准化需求, 提高工作效率。
2 信息抽取方法发展情况
2.1 手工方法:
通过观察网页及其源代码, 由编程人员找出一些模式, 再根据这些模式编写程序抽取目标数据。然而这种方式无法抽取站点数量巨大的形式。手工方法由于设计难度大, 只能针对少量网页抽取, 目前基本不再使用。
2.2 包装器归纳:
即有监督学习方法, 是半自动的。从手工标注的网页或数据记录集中利用机器学习方法序列覆盖学习一组抽取规则。随后这些归则即被用于从具有类似格式的网页中抽取目标数据项。由于需要手工标注的工作, 不适合对大量站点抽取, 并且维护开销大。
2.3 自动抽取:
即无监督学习方法, 给定一张或数张网页, 这种方法自动从中寻找模式或语法, 以便进行数据抽取。自动化抽取的主要优点是它能处理大量站点的情况, 并且维护开销小, 主要缺点是因为系统不知道用户对什么感兴趣, 它可能抽取了大量不需要的数据。
3 DOM树的解析、扩展和Xpath使用
文件对象模型 (Document Object Model, 简称DOM) , 是W3C组织推荐的处理可扩展置标语言的标准编程接口。DOM可以先将XML文档解析成结点对象以元素、属性、实体和注释等节点形式存放信息的树形分级结构, 然后以节点树的形式在内存中, 由于树形数据结构应用较为广泛, 有很多成熟的算法可以用来遍历、搜索、编辑XML文档树, 同时借助于JDOM、DOM4J、SAX等技术类库可以更加方便的访问分档中的数据。
XPath是一种用于查询XML文档中的信息的语言, 是定位XML文档节点的声明式语言, 是W3CXSLT标准的主要组成部分。Xpath规范定义了允许到XML文档各个部分的路径说明的表达式语法和支持这些表达式的核心库基本函数。主要用于识别、选择和匹配XML文档中的各个组成部分, 包括元素、属性和文本内容等。XPath可以使用路径表达式方便地定位XML节点, 所以很适合于数据抽取。
4 Web信息抽取的概念及实现流程
Web信息抽取就是从Web页面中抽取目标信息的问题, 从网页中所包含的无结构或半结构的信息中识别用户感兴趣的数据, 并将其转化为结构和语义更为清晰的格式 (XML、关系数据、面向对象的数据等) 。基于XML技术抽取的流程为:首先, 从网络中获取HTML文档;然后, 经Tidy等工具处理后转换为符合XML格式的XHTML文档, 再使用XSL保存的数据抽取规则, 经XSLT处理抽取出XML, 中对原始的HTML文件加工清洗, 经过使用工具Tity对网页语法检查及纠错, 将HTML文档转换为结构完整的XHTML;第三, 使用HTMLParser等工具解析XML文档生成DOM树模式;最后, 利用Xpath和正则表达式信息抽取规则提取有价值的信息存储到数据库中以便使用。
5 DOM子树最大匹配求方法
设有两棵树T1=RA:
- …
- 就是需要集中抽取的数据区域。
6 结束语
Web数据抽取技术目前还处在不断发展之中, 是Web数据挖掘研究领域中的难题和热点。本文论述了基于DOM技术查找网页中的数据区域方法, 维护开销小, 具有很强的实用价值。值得注意的是还存在着改进的地方, 比如抽取了一部分用户不感兴趣的数据, 这可以尝试使用领域分词过滤掉不需要的信息加以完善。
摘要：文章阐述了利用XML中的DOM树将Web数据结构分析, 转化为结构化的XML数据, 使用Xpath实现数据匹配查找数据, 通过正则表达式实现数据抽取。同时, 对目前数据抽取技术做一些简单探讨研究。
关键词：数据抽取,XML数据,DOM树
参考文献
[1]蔚晓娟.基于DOM的XML解析与应用[J].计算机技术与发展, 2007.17 (4) .
[2]李雪竹.一种基于XML的Web数据抽取的实现[J].科学技术与工程, 2008 (9) .
Web数据抽取 篇3
伴随着互联网及应用普及,智能电视以及互联网电视得到了飞速的发展。相较于传统的电视,互联网电视可以使用户拥有更好的个性化服务;相对于电脑、手机等手持终端设备,互联网电视可以给用户更好的视听享受。然而网上信息量以指数级增长,将海量的数据抽取并集成可以极大的提高用户的使用效率。
Web页面通常按照一定的模板及规律展现出来。基于脚本生成网页结构的相似性可以使信息抽取系统使用简单的规则从网页中抽取信息,这些规则称为包装器(Wrapper)[1,2,3]。目前,从Web页面抽取信息的方法主要是基于规则,这些规则一般集成到包装器中。现有的Web包装器从数据定位方法上可以分为三大类[4,5,6,7],第一类是将HTML页面看成纯粹的文本流,第二类是直接采用某种高级的脚本语言,第三类是将HTML文档转换成一棵DOM树。目前绝大多数的包装器描述语言如W4F[8]、WDL[9]等,将HTML文档转换为一棵DOM树的方法[10]。W4F等语言采用绝对下标表达式来表示DOM树中的一个节点。WDL语言在W4F绝对下标表达式的基础上提出了相对下标的数据定位方法。文献[4]提出了交叉定位法,结合了相对坐标与绝对坐标的方法,提高了抽取的精确度。然而,视频网站较一般的新闻网站,结构更加清晰,信息的抽取对定位要求更加精确,在抽取过程中往往不需要构造整个页面的DOM树,只需将页面进行分块,只对需要进行抽取的模块进行定位、抽取。Web数据具有动态性和异构性的特点,一个轻微的变化都将引起包装器的中断或数据错误的采集,导致包装器中的抽取规则失效而无法正常抽取数据。而且,无论是W4F还是WDL都需要将HTML页面解析成一棵完整的DOM树,这需要耗费相对较大的计算资源;而交叉定位法耗时较高,随着网页结构的变化,误判率较高。
因此,为了提高数据抽取的精率、召回率和效率,本文提出了一种改进的基于内部特征、自底向上归纳总结的数据交叉定位方法,该方法建立了基于元素文本特征和基于元素属性特征的坐标系,将两种坐标系中的坐标值进行交叉验证获取待抽取的元数据信息。
2 交叉定位法的分析
HTML文档由结构化的数据和非结构化的数据混合构成,可以将HTML文档转化成一棵DOM树,将有用的信息存储在DOM树的节点当中。交叉定位法是将HTML转化成DOM树后,根据定义的不同坐标系、原点、坐标,将DOM树映射在各个坐标系中。交叉定位法采用了绝对坐标系、绝对特征坐标系、相对坐标系、相对特征坐标系相结合的方法。如果存在某个坐标P,抽取错误,那么可以利用该点在其他坐标系中的坐标修正坐标P。然而,交叉定位法采用坐标系较多,花费时间较长;且页面变化频率较高,绝对坐标系、绝对特征坐标系定位效果较差,易造成交叉定位法误判;当Web页面微调,只是某些属性的顺序发生变化,包装器虽能够正常运行,但当交叉定位时,用坐标系定位出错的坐标系数目大于正确的数目时,会导致抽取正确数据的坐标系置信度下降,从而导致误判。
为说明方便,采用图1所示HTML页面源代码进行辅助说明。将HTML页面转化为DOM树,如图2所示。在绝对坐标系和相对坐标系中,路径表达式只以标签名称作为路径的唯一标识符,例如,主演信息的绝对路径为[PATH XPATH=“/html/body/div[0]/span[1]/a[List]”],相对路径为[PATH START-PATH=“<div id=‘content’>”XPATH=“span[1]/a[List]”]。在绝对特征坐标系以及相对特征坐标系中,路径表达式结合稳定的特征作为路径的标识符,例如,主演信息的绝对特征路径为[PATH XPATH=“/html/body/div[0]/span[1]/[span=‘主演’]”],相对特征路径为[PATH START-PATH=“<div id=‘content’>”XPATH=“span[1]/[span=‘主演’]”]。在HTML页面中有些信息的顺序有时会发生微小调整,如图3所示,只是主演与导演的顺序发生了改变,这种调整能使包装器依然正常的运行,但是绝对坐标系和相对坐标系的定位发生了错误,经过多坐标交叉定位时,由于定位错误的坐标系数目等于定位正确的坐标系数目,会造成误判,抽取的数据发生严重的错误。
3 基于相对特征坐标系的交叉定位包装器的生成算法
3.1 最小包装器生成算法
本文采用自底向上的逻辑归纳思想。设D(D1,D2,…,Dn)表示HTML页面集合,x表示包装器的路径表达式XPATH。最小包装器路径唯一,定义x最小包装器满足条件:Min(XPATH)=x0,且没有其他的XPATH表达式,x满足:x=x0,并且Precision(x0)=Precisionn(x),Recall(x0)=Recall(x)。生成最小包装器的目的是为了满足各抽取元素路径最短的情况下同时使查全率和查准率尽可能为1。
假设x是一个XPATH路径表达式的包装器,如其查全率和查准率都为1,但并不满足最小包装器的条件,那么x并不是最小包装器,我们需要找到最小包装器。最小包装器可以在抽取数据的过程中减少由于页面变动而引起的抽取数据错误和中断,并且可以减少抽取的时间。基于元素文本特征的包装器生成算法如下所述:
该算法输入是一系列有标签的Web页面集合,输出是基于元素文本特征坐标系的原点以及使用XPATH路径表达式表示的包装器集合ResultSet,即各抽取节点的坐标。
算法第1行为初始化,基于文本特征坐标系的坐标原点START-PATH为第一个可定位到待抽取元素的文本,Point为中间指针,初始化为第一个可定位到待抽取元素的文本,ResultSet为NULL;第2行为判断START-PATH是否为Web页面的最开始标签,若为html节点,则遍历到顶点了,结束遍历;第3行计算根据当前路径精确度和召回率是否为1,若是则遍历到最小包装器,否则执行7行-8行;第11行返回XPATH路径表达式表示的包装器集合ResultSet,以及获得到START-PATH。将START-PATH作为坐标系原点,ResultSet作为最小包装器。
本算法按照最坏情况计算时间复杂度。本算法主要耗时在计算坐标系的坐标原点上。步骤1的时间复杂度为时间常量,即为0(1)。假设HTML转化为DOM树,DOM树的深度为n,则步骤2在最坏的情况下的时间复杂度为O(n)。在每次循环过程中,步骤3-步骤9的时间复杂度为0(1),因此该算法的时间复杂度为0(1)+0(n),即为O(n)。因此,采用本算法每种坐标系的时间复杂度为O(n),假设采用的坐标系种数为k,则采用改进的交叉定位法的时间复杂度为kO(n),算法复杂度呈线性增长。
其他几种方法在构造DOM树的过程中,考虑在最差情况下的时间复杂度,绝对路径方法的时间复杂度为O(n);相对路径方法的时间复杂度为O(n);绝对特征路径方法的时间复杂度为O(n);相对特征路径方法的时间复杂度为O(n);交叉定位方法的时间复杂度分别为40(n)。本文提出的算法在时间复杂度上并未明显增长。
3.2 基于内部特征的相对特征坐标系的构造方法
本文参考待抽取信息块的内部特征,采用基于内部特征的相对特征坐标系构造交叉定位的包装器。在视频网站中,包含一些稳定的元素文本,而元素中包含一些稳定的属性特征,因此,本文构造的基于内部特征的相对特征坐标系主要依据HTML的2个方面的内部特征:①元素文本特征;②元素属性特征。由两个方面的内部特征分别构造了基于元素文本特征的坐标系和基于元素属性特征的坐标系。
3.2.1 基于元素文本特征的坐标系
在抽取视频网站中视频的元数据信息时,直接定位不到有用的信息,需要借助定位得到待抽取信息节点的父节点、子节点或兄弟节点,从而定位得到有用信息的节点。一个HTML信息块由元素构成,而元素由子元素、文本或两者结合的混合式内容构成。分析多家视频网站,可以得出视频的元数据信息定位方式主要分为3种方式:
基于元素文本特征的坐标系,利用第一个可以定位到的待抽取元数据的文本(父节点元素的文本、子节点元素的文本、兄弟结点元素的文本)作为坐标原点,根据此坐标原点寻找其他待抽取元素的路径即坐标,如果可以定位得到其他元素的坐标,则此元素可以作为原点;否则,将此元素的父节点作为坐标原点,寻找其他元素的坐标,如此向上递归直至找到一个节点作为坐标原点,以此坐标原点可以定位得到所有元素的坐标,即将该元素作为坐标原点,每个待抽取的元素的路径作为坐标。
3.2.2 基于元素属性特征的坐标系
元素的标签中往往包含一些属性,有些属性名称或是属性值是唯一的,可以识别唯一的元素。
根据分析,可以看到,能够唯一识别元素的属性特征分为以下三种:
(1)标签中具有属性名称为“id”的属性。例如,<PATH START-STR=<div id=“content”>/>。
(2)同一抽取页面中待抽取模块中的属性具有唯一的名称。例如,<PATH START-STR=<div id=“content”>XPATH=span[propertyName=“style”]/>,可以用于定位到第一个属性名称为style的标签。
(3)同一抽取页面里待抽取模块中的属性名称不唯一,但属性值唯一;且同一类待抽取页面,不同的页面中同一元素的属性名称相同,属性值也相同。例如,在图1源码的span标签中,有一个稳定特征property=“v:genre”,那么<PATH START-STR=<div id=“content”>XPATH=span[@property=“v:genre”]/>,可以用于定位到这个第一个property属性值为v:genre的span标签。
选取的属性可以最大程度上的区分同一抽取模块中的不同的元素,同时也尽可能的识别不同网页中待抽取模块中相同的元素。利用基于元素文本特征坐标系生成的坐标原点的元素所在的子树作为划分的待抽取的模块,在待抽取模块中进行训练上述三种属性特征。利用基于元素文本特征坐标系生成的坐标原点作为基于元素属性特征坐标系的原点,利用上述三种特征的属性定位到待抽取的元素的路径作为坐标值。
3.3 基于相对特征坐标系包装器的生成算法
根据元素文本特征构造的坐标系,在进行抽取视频元数据的过程中,由于页面结构的变化,使某些待抽取信息的子节点、父节点、兄弟节点元素的缺失,或文本的改变导致定位不到待抽取信息等原因引起的抽取错误。因此,结合基于元素属性特征的坐标系,共同定位待抽取的信息。
基于相对特征坐标系包装器的生成流程图如图4所示。将待抽取的HTML页面分为两个部分:训练集与测试集。
将训练集部分的页面分别训练生成两种坐标系:①根据3.1节提出的最小包装生成器的算法,定位基本元素文本特征坐标系的坐标原点;根据坐标原点以及各元素的路径计算各元素坐标;生成基于元素文本特征的坐标系;②根据坐标原点确定待抽取模块所在DOM树中的子树;在子树中训练3.2.2节提出的元素属性;计算各元素在基于属性坐标系中的坐标;生成基于元素属性特征的坐标系。
利用测试集,测试根据训练集生成的包装器。分别采用两种坐标系对视频元数据进行抽取;在抽取过程中,若基于元素文本特征的坐标系抽取成功,则采用该坐标系抽取的信息,否则采用基于元素属性特征的坐标系抽取的元数据信息。
4 实验结果及分析
本文选取了8家视频网站进行数据抽取,如表1所示。从各家网站中分别选取50个页面作为训练集训练包装器;通过3个月观察,各个网站结构发生部分调整,其中,土豆、优酷、爱奇艺等网站有过一次较大的变化,分别选取其中部分网页作为测试集进行抽取实验,选取各个网站的网页数目如表2所示,选取待抽取的元数据信息包括:视频名称、集数、导演、演员、类型、地区、上映时间、剧情描述。
本实验环境:LINUX redhat5.3,JAVA语言,JDK＿1.6。本文主要从抽取精度、召回率和效率上进行实验。
计算抽取效率的过程时,只计算定位、抽取的时长,不包含存储、过滤的时间。见以下公式。
其中,a表示为抽取正确并判断正确的元素数;b表示抽取正确但判断错误的元素数;c表示抽取错误但误断为正确结果的元素数;d表示抽取错误并能够判断抽取结果为错误的元素数,如表3所示。
根据表4、表5结合实际抽取结果分析得出:①采用四种单独的坐标系,抽取的精度比较低;②采用四种单独的坐标系,不需要采用投票的方式判定结果,所以没有将抽取正确的结果误断为错误的结果,召回率为1;③交叉定位法在精度上有了很大的改进,但是以大大降低召回率为代价;④改进的交叉定位法在以降低较小的召回率为前提下很大程度上提高了抽取的召回率。
根据表6可以看出:①采用单种方法使用的时间较小,但也不排除某些页面在抽取过程中失败引起的时间较少的原因;②交叉定位方法是综合上述4种方法,用时较长;③改进的交叉定位方法相较于交叉定位方法在时间上大大缩短。实验结果如表4-表6所示,交叉定位法和改进交叉定位法如上述3个表中的最后两行结果所示。
5 结束语
Web信息抽取是当今互联网及应用和服务的普及过程中的一项重要技术。由于Web数据动态性和异构性的特点,网页结构也经常发生改变,一个轻微的变化都将引起包装器的中断或数据错误的采集,导致包装器中的抽取规则失效而无法正常抽取数据。本文分析了当前的数据定位常用的方法,分析了其优点与不足。本文对交叉定位方法进行了改进,通过实验表明,此方法抽取数据受网站微调影响较小,可以大大提高了抽取的准确性,并且可以极大的缩短抽取数据的时间。
摘要：针对包装器在抽取Web网站的过程中抽取精度差、耗时长以及鲁棒性差等问题,提出了一种改进的基于内部特征、自底向上归纳总结的数据交叉定位方法,该方法建立了基于元素文本特征和基于元素属性特征的坐标系,将两种坐标系中的坐标值进行交叉验证获取待抽取的元数据信息。实验结果表明:该方法抽取数据相较于绝对路径方法、相对路径方法、绝对特征路径方法、相对特征路径方法以及交叉定位方法,在召回率略降2.2%的情况下,精确度提高了31.1%,并且相较于交叉定位法,抽取数据的时间提高了17.9秒。
关键词：Web信息抽取,交叉定位,包装器,内部特征,DOM树
参考文献
[1]Nilesh Dalvi,Ravi Kumar,Mohamed Soliman.Aulomatic Wrappers for Large Scale Web Extraction[J].In VLDB,2011,4(4):219-230
[2]Parameswaran A,Dalvi N,Garcia-Molina H,et al.Optimal schemes for robust web extraction[J].Proceedings of the VLDB Conference.VLDB Endowment,2011,4(11):980-991
[3]N.Kushmerick,D.Weld and R.Doorenbos.Wrapper induction for information extraction[C]//Proceedings of the 15th international conference on Artificial Intelligence.1997.729-735
[4]ChenTian,HuangMin.Data Cross-Locating in Web Information Extraction[J].Journal of South China University of Technology(Natural Science Edition).2008,36(5):43-47,52
[5]Chang Chiahui,Lui Shaochen.IEPAD:information extraction based on pattern discovery[C]//Proceedings of the Tenth International Conference on World Wide Web.Hong Kong:ACM,2001.681-688
[6]Chang Chiahui,Lui Shaochen,Wu Yenchin.Applying pattern mining to Web information extraction[C]//Proceedings of the 5th Pacific Asia Conference on Knowledge Discovery and Data Mining.Hong Kong:Springer,2001.4-16
[7]Kistlera T,Marais H.WebL:a programming language for the Web[J].Computer Networks and IS-DNS Systems,1998,30(l):259-270
[8]Sahuget A,Azayant F.Building light-weight wrappers for legacy Web data sources using W4F[C]//Proceedings of the 25th International Conference on Very Large Data Bases.Edinburgh:Morgan Kaufmann,1999.738,741
[9]Sun Jianling,Cat Junjie,Dong Jinxiang.WDI:a general XML-based Web wrapper description anguage[J].Journal of Zhejiang University:Engineering Science,2003,37(1):24-31
浅谈web信息抽取 篇4
(一) 什么是web信息抽取
Web信息抽取是指从Web页面所包含的无结构、半结构或者结构化的信息中识别用户感兴趣的数据, 并将其转化为结构和语义更为清晰的格式的Web页面信息抽取的过程[1]。
(二) Web信息抽取技术涉及的内容
因特网提供了一个巨大的信息源。这种信息源往往是半结构化的, 并且中间夹杂着结构化和自由文本。网上的信息还是动态的, 包含超链接, 都以不同的形式出现。
1. Web信息抽取的内容一般可以分为几个方面:
命名实体的抽取、与模板有关的内容信息抽取、各个实体之间关系的抽取和预置事件的信息抽取。
信息抽取的方法主要可以分为以下两类:一类是基于层次结构的信息抽取归纳方法, 另一类是基于概念模型的多记录信息抽取方法。
Web信息抽取工作主要包装器 (Wrapper) 来完成[1]。包装器是一种软件过程, 这个过程使用已经定义好的信息抽取规则, 将网络中Web页面的信息数据抽取出来, 转换为用特定的格式描述的信息。一个包装器一般针对某一种数据源中的一类页面。包装器运用规则执行程序对实际要抽取的数据源进行抽取。
2. 抽取过程一般包括以下几个步骤[2]:
(1) 将Web网页进行预处理。预处理的目的是将半结构化HTML页面去掉无用的信息以及对不规则的HTML标识进行修正, 为下一步标记信息做准备。
(2) 用一组信息模式描述所需要抽取的信息。通常可以针对某一领域的信息特征预定义好一系列的信息模式, 存放在模式库中供用户选用。
(3) 对文本进行合理的词法、句法及语义分析, 通常包括识别特定的名词短语和动词短语。
(4) 使用模式匹配方法识别指定的信息模式的各个部分。
(5) 进行上下文分析和推理, 确定信息的最终形式。
(6) 将结果输出成结构化的描述型式以便由网络集成系统进行查询分析。
(三) Web信息抽取方法的分类
把所有网页都归入半结构化文本是不恰当的。若能通过识别分隔符或信息点顺序等固定的格式信息正确抽取出来, 那么该网页是结构化的。半结构化的网页则可能包含缺失的属性, 或一个属性有多个值, 或一个属性有多个变体等例外的情况。若需要用语言学知识才能正确抽取属性, 则该网页是非结构化的。
网页的结构化程度总是取决于用户想要抽取的属性是什么。通常机器产生的网页是非常结构化的, 手工编写的则结构化程度差些, 当然有很多例外。
按照Web信息抽取对象的结构化程度, 大体上可以分为三种类型:结构化文本;自由文本;半结构化文本。
1. 根据Web信息抽取对象划分, 可以分为三种类型:
(1) 从自由格式的文本中抽取出所需要的信息内容。自由文本的抽取技术可分为三类:基于自然语言处理 (NPL) 的方式;基于规则的方式;基于统计学习的方式。
(2) 从半结构化的文本中, 抽取出所需要的信息内容。
(3) 从结构化的文本中抽取出所需要的信息内容。
2. 根据自动化程度可以分为
人工方式的信息抽取、半自动方式的信息抽取和全自动方式的信息抽取三大类。
3. 根据现有Web信息抽取系统和模型实现原理的不同, 分为以下几类:
(1) 基于归纳学习的信息抽取[2]。通过对若干个待抽取实例网页进行结构特征学习, 归纳出抽取规则, 然后使用抽取规则自动分析待抽取信息在网页中的结构特征并实现信息抽取。采用这种原理的典型的系统有STALKER, SOHTMEALY, WIEN。
(2) 基于HMM (Hidden Markov Model) 的信息抽取[3,4]。是最近几年应用最广泛的抽取知识表达模型。它是一种随机的有限状态自动机, 由于HMM有成熟的学习算法和坚实的统计基础, 所以在信息抽取中是一种成功的模型。
(3) 基于特征模式匹配的信息抽取[2]。通过大量学习实例, 归纳学习出待抽取信息的语法结构模式, 并根据这些模式从待抽取网页中抽取出相匹配的信息, 适用于复杂结构信息的抽取。
(4) 基于网页结构特征分析的信息抽取[2]。将Web文档转换成反映HTML文件层次结构的解析树, 通过自动或半自动的方式产生抽取规则。采用该类技术的典型系统有LIXTO等。
(5) 基于Ontology的Web信息抽取。本体的构建是这类抽取的基础与核心, 如何构造出良好的面向应用领域的Ontology对提高信息抽取的精确度有直接的影响。该方法主要是利用对数据本身的描述信息实现抽取, 对网页结构依赖较少。由Brigham Yong University信息抽取小组开发的信息抽取工具中采用了这种方式, 另外QUIXOTE也采用了这种方式。
(6) 基于自然语言处理 (Natural Language Processing, NLP) 。这类信息抽取主要适用于源文档中包含大量文本的情况 (特别针对于合乎文法的文本) , 在一定程度上借鉴了自然语言处理技术, 利用子句结构、短语和子句间的关系建立基于语法和语义的抽取规则实现信息抽取。目前采用这种原理的典型的系统有RAPIER, SRV, WNISK。
(7) 基于Web查询的信息抽取。将Web信息抽取转化为使用标准的Web查询语言对Web文档的查询, 具有通用性。采用该类技术的典型的系统有:Web-OQL以及自主开发的原型系统PQAgent。
(四) 国内外Web信息抽取技术的研究和应用
上世纪80年代以来, 国内外许多大学、公司和研究机构对信息抽取技术展开了有计划的、长期系统的研究与应用工作, 取得了一些成果并有许多相关的应用。也使信息抽取研究蓬勃开展起来, 这主要有两个因素对其发展有重要的影响:一是在线和离线文本数量的几何级增加, 另一个是“消息理解研讨会” (MUC, Message Understanding Conference) 从1987年开始到1998年共举行了七届会议对该领域的关注和推动。MUC由美国国防高级研究计划委员会 (DARPA, the Defense Advanced Research Projects Agency) 资助, 其显著特点并不是会议本身, 而在于对信息抽取系统的评测。近些年来, 信息抽取技术的研究与应用更为活跃。
在研究方面, 主要侧重于以下几方面:利用机器学习技术增强系统的可移植能力、探索深层理解技术、篇章分析技术、多语言文本处理能力、WEB信息抽取 (Wrapper) 以及对时间信息的处理等等。
在应用方面, 信息抽取应用的领域更加广泛, 除自成系统以外, 还往往与其他文档处理技术结合建立功能强大的信息服务系统。
至今, 已经有不少以信息抽取技术产品为主的公司出现, 比较著名的有Cymfony公司、Bhasha公司、Linguamatics公司、Revsolutions公司等。
目前, 除了强烈的应用需求外, 正在推动信息抽取研究进一步发展的动力主要来自美国国家标准技术研究所 (NIST) 组织的自动内容抽取 (ACE, Automatic Content Extraction) 评测会议。这项评测从1999年7月开始酝酿, 2000年12月正式开始启动, 从2000年到2007年已经举办过好几次评测。这项评测旨在开发自动内容抽取技术以支持对三种不同来源 (普通文本、由自动语音识别ASR得到的文本、由光学字符识别OCR得到的文本) 的语言文本的自动处理, 研究的主要内容是自动抽取新闻语料中出现的实体、关系、事件等内容, 即对新闻语料中实体、关系、事件的识别与描述。与MUC相比, 目前的ACE评测不针对某个具体的领域或场景, 采用基于漏报 (标准答案中有而系统输出中没有) 和误报 (标准答案中没有而系统输出中有) 为基础的一套评价体系, 还对系统跨文档处理 (Cross-document processing) 能力进行评测。这一新的评测会议将把信息抽取技术研究引向新的高度。
国内对中文信息提取系统的研究起步较晚, 还集中在命名实体识别方面, 遵照MUC规范的完整的中文信息提取系统目前还处于探索阶段。Intel中国研究中心在ACL-2000上演示了他们开发的一个抽取中文命名实体以及实体间关系的系统。在MUC-6和MUC-7上, 增加了中文系统的评测项目, 国立台湾大学 (National Taiwan University) 和新加坡肯特岗数字实验室参加了MUC-7中文命名实体识别任务的评测, 测试了中文命名实体 (人名、地名、时间、事件等名词性短语) 的识别, 取得了与英文命名实体识别系统相近的性能。当然这只是对中文信息提取作了比较初步的工作, 并不能真正进行中文信息提取。另外, 北京大学计算语言所对中文信息提取也作了比较早的和比较系统的探讨, 承担了两个有关中文信息提取项目的工作, 即自然科学基金项目“中文信息提取技术研究”和IBM——北大创新研究院项目“中文信息提取系统的设计与开发”。其目标是研究中文信息提取中的一些基础性和关键性的问题, 为开发实用的信息提取技术提供理论指导, 并具体探讨信息提取系统设计的各个环节。
(五) 研究的热点和趋势
从目前的研究和应用情况看, 信息抽取系统的性能和可移植性仍然是制约web信息抽取技术广泛应用的两个主要瓶颈。信息抽取的准确率, 对不同语言和不同类别的文本的适应性还有待提高, 在自然语言处理中的核心问题仍未完全解决, 而且与国外相比, 我们在信息抽取系统的研究上仍存在很大的差距。
因此, 以下问题将是今后Web信息抽取技术研究的热点问题:
1. 如何提高Web信息抽取系统抽取范围的全面性。
2. 如何简化学习过程, 提高自动化程度。
3. 如何提高系统对新网页的适应性, 增强系统对Web信息抽取的适应性。
4. 如何加强对已有抽取规则的归纳, 提高系统的抽取效率和准确性。
5. Web上的信息和网页结构处于不断的更新和变化中, 因此应如何感知Web信息和结构的更新变化。
6. 目前的Web信息抽取工具一般都是通过学习之后可以
对结构相似的一类网页进行抽取, 因此应如何判断结构相似, 如何提高系统的性能、可移植性的设计以及适应多语种的能力。
7. 在中文Web信息抽取系统的研究方面, 应如何借鉴国外
比较成熟的系统构建技术, 并结合汉语的特殊性, 充分利用一些基础的汉语研究成果来构建高效、精确的中文Web信息抽取系统。
(六) 结束语
Web信息抽取是目前最活跃的研究领域之一, 特别是经过最近十几年的发展, Web信息抽取作为一种能帮助人们在海量信息中迅速找到所需信息的技术越来越受到重视。尽管目前该领域研究已经取得了一定的进展, 但仍然存在一些问题有待解决。相信随着领域专家对Web信息抽取领域的研究的逐渐深入, 难题逐渐被解决, 越来越多的好技术应用到该领域, Web信息抽取技术必将得到更大的发展和更广泛的应用。
参考文献
[1]刘迁, 焦慧, 贾惠波.信息抽取技术的发展现状及构建方法的研究[J].计算机应用研究, 2007, 24 (7) :6-9.
[2]柳佳刚, 刘高嵩, 贺令亚, 陈山.基于Web的信息抽取技术现状与发展[J].福建电脑, 2007 (7) :48-49.
[3]Ping Zhong;Jinlin Chen;Cook T.;“Web Information Extraction Using Generalized Hidden Markov Model”, Hot Topics in Web Systems and Technologies, 2006.HOTWEB'06.1st IEEE Workshop on13-14Nov.2006Page (s) :1-8
WEB信息的抽取与集成研究 篇5
1 WEB信息抽取系统设计与实现
1.1 系统分析
1)映射关系:为了实现数据的正确抽取,需要在两者之间建立映射关系。映射关系的建立有两种方式:一种就是通过最大重复模式发现,来自动获取匹配模式,实现到目的模式的一一映射;另外一种就是通过样本学习,由用户标记自己感兴趣的内容,然后将其映射到目的数据结构上去,通过采用人工参与的方式实现数据关系映射。
2)抽取规则:(1)建立了映射关系,只是建立了具体的数据和目的结构之间的映射关系,我们要将这种映射关系应用到其他和此数据具有类似结构的数据上去,就要根据这些映射关系,发现抽取模式,进而形成抽取规则。抽取规则的表示直接和网页描述方式有关;(2)基于XPath的方式———Web网页描述基于DOM树的表示方式。这种方式是基于在Web网页描述时,采用了DOM树的表示方式,这样,当用户在浏览网页,进行样本学习时,一旦选中了所需抽取的数据,就可以利用XPath技术很快的得到这个所需抽取数据在DOM树中的位置,实现数据的定位。
3)信息抽取过程逻辑描述:由于我们决定将Web信息抽取过程的逻辑定义和Web信息抽取具体实施分开,两者之间通过文件的方式通讯,那么,我们就必须将在Web信息抽取过程的逻辑定义过程中所产成的信息很好的保存下来,这些信息包含:数据源描述(服务器地址、用户名、密码、URL列表),目的表结构(表名、表类型、字段名、字段类型),抽取规则。
1.2 系统设计及框架结构
该WEB信息抽取系统的框架包含五个模块:网页定义模块、源网页获取和解析模块、目的数据模式定义模块、规则获取模块、规则修正模块、数据抽取实施模块。
1.3 系统实现
根据上面的系统设计,笔者做了一个演示程序,其具体实现过程如下:
1)网页路径定义:首先,在定义网页位置信息时,我们采用如下结构保存以下信息:
(1)网络信息:针对现在有些用户上网需要代理,所以我们要有一个结构来保存代理服务器的信息,包括代理服务器的地址(IP)、用户名、用户密码等。
(2)页面信息:对于静态网页,它的URL相对比较简单,就是一个固定的唯一的字符串。而动态网页页面的情况比较特殊,它往往是带参数的字符串,同时访问方式也分为Get和Post两种(参见前面的Http介绍)。所以,一张页面的访问信息要包括以上信息,数据结构定义如下:
2)源网页获取和解析:其次,用户给定样本网页的URL,根据用户输入的URL来获得源网页。同时,由于HTML文档没有严格规范的代码规定,这会导致对文档进行语法分析、分离显示格式和数据内容时就不够严谨。为此,在对源网页进行扫描解析前,我们首先利用W3C组织推荐的HTML Tidy工具对其进行规范化,并进一步生成格式良好的XHTML。这样,我们就可以利用XML技术对这张网页进行扫描解析,生成一个能表征这张网页结构的DOM树,并维护这棵DOM树。这棵树只有一个根节点,每一个叶节点都表示HTML网页中出现的各种类型的数据。以后任何对源网页的操作都会反应到对这个DOM树的操作之上。
3)建立映射关系:在定义完了目的数据模型之后,就是在源数据结构和目的数据结构之间建立映射,其实就是样本学习的过程。如上图,用户首先选中感兴趣的信息元:德生收音机R202T,然后指定其对应的目的数据结构中的表字段(receriver-type),建立映射关系,用三元组来表示。
4)数据抽取实施模块:用户利用我们提供的可视化的工具定义完源网页访问信息、目的数据的模式结构、指定从HTML网页到目的数据模式之间的映射关系、获得抽取规则之后,我们采用XML作为中间数据交换模型,将这些信息(即Web信息抽取过程逻辑描述)保存为XML文档的形式,交由数据抽取实施模块解析执行,最终实现Web信息的抽取与保存。
2 结束语
本文设计了一个工具来实现对Web信息抽取。在这个工具中,我们将Web信息抽取过程的逻辑描述和Web信息抽取过程的执行相分离,并用图形化的方式来帮助用户定义Web信息抽取过程,包括定义Web访问信息、抽取模式、结果数据保存模式等信息。
参考文献
[1]陈少飞,郝亚南,李天柱,等.Web信息抽取技术研究进展[J].河北大学学报:自然科学版,2003,23(1):106-112.
[2]张成洪,肖军建,张诚.Web内容抽取及其数据管理方法[J].复旦学报:自然科学版,2001,40(2):177-183.
基于聚类的Web链接抽取 篇6
随着互联网的不断发展, 人们越来越多地在互联网上发布和获取信息。Web已经成为信息制造、发布、加工和处理的主要平台。与传统的基于文档内容的互联网应用技术相比, 互联网又包含了传统数据环境所没有的另一种丰富信息, 即互联网的超链接拓扑结构。网页间的超链接一方面引导网页浏览的过程, 另一方面也反映了网页创建者认为所链接的网页包含了有价值的信息。因此, 基于链接分析的应用得到了广泛的研究, PageRank及其改进算法是最早并且最成功地将链接分析技术应用到商业搜索引擎中的算法。
在真实的互联网环境中存在大量重复的链接、镜向的站点以及商业广告链接, 从而使高价值网页的计算发生偏差, 产生主题漂移的现象。而与主题相关链接的抽取的研究较少, Bharat等提出将传统的文本分析技术结合应用到链接分析中。文献[2]根据实际观察提取规则并且用于模型统计的方法, 去除链接噪音数据。该方法在某一个网站上可以很好地应用。但当遇到新的网站或网站的模版改变时, 要重新设计规则或重新输入训练网页集。我们在文献[7]中对文本链接抽取进行了初步的研究。因此深入研究并区分这种链接对链接分析技术更为有效的应用具有十分重要的意义。
通过分析链接本身的特点, 本文提出一种基于聚类的链接抽取方法。由于所采用的特征主要是链接的自身信息:如链接文本的内容、字体大小, 字形权值, 位置1等, 该方法的实现与网页的模版无关。该方法可以实现抽取相关的链接, 排除无关的链接, 改善基于链接分析算法的效果、减少主题漂移。
1 链接特点分析
对网页链接的抽取, 是对每个页面的链接进行预处理, 区分每个链接是否与主题相关, 目的是抽取与主题相关的链接, 作为基于链接分析算法的输入, 改善该算法的效果, 减少主题漂移的产生。图1是一个新浪网页部分内容, 信息块1包含的内容是导航条, 信息块2包含的内容是正文, 信息块3包含的内容是与主题相关链接, 信息块4网站新闻导航, 信息块5包含的内容是广告链接。其部分相应的链接见图2。
从图1、图2可以发现, 其一, 网页中的相关链接与奥运会开幕式天气有关, 如果采用PageRank和HITS算法来进行主题抽取, 显然, 开幕式天气是相关的主题。其二, 由于广告链接和新闻导航出现的频率颇高, 所以所链接的广告页面作为hub页所链接的authority页面同时也会被抽取出来, 我们还会得到这样的主题词, 如:彩铃等。这明显不是我们想要获得的主题。所以对链接进行必要的预处理是非常必要的。
通过对数百个网页中的相关链接以及无关的链接的分析, 我们发现链接的以下特点:
(1) 每个链接在标记之间, 有若干个与主题相关链接, 简称为相关链接;有若干个与主题无关的链接, 简称为无关连接。
(2) 相关链接锚文字 (Anchor text) 与主题相关, 出现次数较多, 无关链接的锚文字与主题不相关, 每个关键词几乎只出现一次。
(3) 无关链接通常由网站模版生成, 通常是相同内容分布在网站的大部分页面内。
(4) 相关链接一般在主题文章的后面, 处在网页的中下部分。而无关链接大部分在相关链接的后面, 页面的末端, 或页面的右边。
(6) 除了文字链接, 还有图像链接, 见图3, 一般图像都有以下属性:Height、Width等, 有的图像标签中可能含有“Alt”标记文本。
链接抽取方法所采用的特征是链接本身的信息, 每个链接有相应的链接向量A (a1, a2….am) 表示, m是向量维数, 也就是链接选取的特征数, 包括页面关键词组、图像特征、字形等外形特征等。
该方法不需要生成抽取模板, 而是通过分析网页链接本身的特征, 产生关键词组。关键词组具体的抽取过程如下:
(3) 位置信息
(1) 无关链接在页面的最后位置;
(2) 无关链接在页面的靠右位置。
根据以上信息, 我们得到了能区分一个链接的链接文本内容特征, 外形特征、位置特征等。从链接文本内容抽取关键字作为文本特征, 外形特征采用链接文本的字体信息、位置特征采用链接所在的位置等。表1给出了一些特征类型的样例。
定义1:设有向量簇C1和C2, C1和C2的簇间聚类度量为:
, 是两个向量p和q之间的距离。
3 基于聚类的WEB链接抽取方法
我们的策略自底向上, 首先将每个对象作为一个簇, 然后合并这些原子簇为越来越大的簇, 直到所有的对象都在一个簇中, 或者某个条件被满足。具体算法如下:
输入:页面中的链接向量。
输出:主题相关链接簇。
(1) 将数据空间每个数据点初始化为初始类;
(2) 合并最近的两个类 (见定义1) ;
(3) 返回第2步, 直至聚集为一个类或满足结束条件;
(4) 将平均信息熵最小的簇返回。
4 试验结果和分析
我们是用准确率来评价试验结果。定义试验结果的准确率如下:
我们从网页中随机选出200个页面的链接作为训练集, 另外选出100个页面的链接作为测试集。用本文的方法与使用完全的文本信息抽取 (算法1) 进行对比试验, 测试结果见表2。
从试验数据可以看出, 本文的方法准确率比原有的算法有明显的提高, 这是由于算法1的链接抽取全部是基于文本分析, 所有特征全部采用关键字, 而本文算法的关键字特征只占有一部分, 还有一部分结构信息, 使算法更加可靠。
5 结论
本文研究了一种基于聚类的自动的W e b链接的抽取方法, 主要使用链接本身的信息, 如:链接文本、文本字体信息、位置信息、标志信息等。我们的工作非常有效, 能抽取与主题相关的链接, 减少无关链接对基于链接分析算法的干扰, 并且使用不受网站模版的变化的影响。下一步的工作是将自动的Web链接的抽取方法应用到基于链接分析的应用算法中, 如PageRank等。
参考文献
[1]Paolo Boldi, Massimo Santini, Sebastiano Vigna.PageRank as a Function of the Damping Factor[C].WWW2005.May10-14.2005.Chiba.Japan.
[2]邓健爽, 郑启伦, 彭宏等.基于Web挖掘的网页清洗技术.计算机工程与应用.2006.
[3]王晓宇, 周傲英.万维网的链接结构分析及其应用综述[J].软件学报.2003.
[4]Bharat K, Henzinger M.Improved algorithms for topic distillation in a hyperlinked environment[C].In:Voorhees E, et al., eds.Proceedings of the21st ACM-SIGIR International Conference on Research and Develop-ment in Information Retrieval.Melbourne:ACM Press.1998.
[5]Yuan Wang David J.DeWitt.Computing PageRank in a Distrib-uted Internet Search System[C].Proceedings of the30th VLDB Conference.Toronto.Canada.2004.
[6]Saeko Nomura, Satoshi Oyama, Tetsuo Hayamizu.Analysis and Improvement of HITS Algorithm for DetectingWeb Communities[C].Proceedings of the2002Symposium on Applications and the Internet.
[7]朱红灿, 邹凯.基于机器学习的WEB链接的抽取.情报理论与实践.2007.
Web数据抽取 篇7
随着网络的推广与普及, 网页已经成为人们获取、交换和发布信息的重要途径。CNNIC (中国互联网络信息中心) 在2010年1月15日公布的《第25次中国互联网络发展状况统计报告》显示, 截至2009年12月, 我国网民规模已达3.84亿, 互联网普及率进一步提升, 达到28.9%, 网络新闻和搜索引擎的使用率分别占80.1%和73.3%。然而发展的同时也带来了一些新的问题:网页噪声[1]几乎占据了主题型网页内容的一半、许多由查询数据库自动生成的网页不能被搜索引擎检索从而成为了所谓的hidden web[2]、互联网的开放性和动态性使得网络信息难于组织、搜索引擎仅能提供搜索结果列表, 用户依然难以在海量信息中找到所需内容等。人们迫切需要一种自动化的工具对网络信息进行有效的处理和整合, 从而将被淹没在网络信息海洋中的有价值的信息抽取出来, Web信息抽取技术就是在这样的需求背景下应运而生的。
2、相关工作
Web信息抽取的定义多种多样, 根据Proteus工程的创建者纽约大学计算机科学系的Ralph Grishman[3]描述信息抽取的概念为:“信息抽取涉及到为从文本中选择出的信息创建一个结构化的表示形式”, 因此Web信息抽取可以理解成“从网页文本中抽取指定的一类信息并将其形成结构化的数据填入一个数据库中供用户查询使用的过程”。与Web信息抽取有密切关系以及最容易混淆的一个技术就是Web信息检索 (Web Information Retrieval) , 事实上二者具有本质上的区别:信息检索是根据用户的查询请求返回一个指向相关资源的列表, 用户需要自己根据这个列表查看其指向的资源才能够找到自己所需的信息;而Web信息抽取则是对网络上的信息资源进行加工和提取, 直接抽出用户感兴趣的一部分内容返回给用户。
常见的文本信息可以分为三种:自由文本、结构化文本和半结构化文本。陈治昂[4]、刘亚东[5]、赵欣欣[6]、杨桢[7]等人均认为Web信息为半结构化。尽管当前大多数网页都遵循W3C的DOM[8]树状结构, 但是在网页中确实充斥着大量的看似杂乱无章的文本、链接、图片, 并且大部分网页信息会以各种不同的形式来呈现, 然而并不能以此为依据来说明所有网页都是半结构化的。Hsu对网页类型做了颇为准确的定义:若能通过识别分隔符或信息点顺序等固定的格式信息即可把“属性-值”正确抽取出来, 那么, 该网页是结构化的。半结构化的网页则可能包含缺失的属性, 或一个属性有多个值, 或一个属性有多个变体等例外的情况。若需要用语言学知识才能正确抽取属性, 则该网页是非结构化的。
web信息抽取技术已经成为当前应用和研究领域的一个重要课题。李效东等以文档对象模型为基础, 把所要提取的信息在该层次结构中的路径作为信息抽取的坐标, 设计了一种归纳学习算法来半自动地生成提取规则。张志刚[9]等提出了一种以启发式规则为基础的网页净化方法, 利用信息检索技术以及web页面特征提取网页主题和相关内容, 达到净化网页的作用;欧建文[10]等以网页链接关系中的锚点, 采用机器自动学习方式生成对应模板的提取规则, 依据模板的提取规则对网页主题信息进行提取。韩忠明[11]等分析了中文新闻网页与博客网页的正文特征, 用实验表明了利用HTML标签与文本的密度比可以进行文本的识别与抽取。杨少华[12]等针对电子商务网站的商品描述网页研究如何从这类由模板生成的网页中检测出其背后的模板, 并深入分析模板产生网页的结构特征, 从而将嵌入的数据自动地抽取出来。刘亚东等介绍了一种基于智能的网页信息抽取系统EIES, 在提取过程中不需人工干预, 实现了信息抽取的智能化。张彦超[13]等将网页解析成文档对象模型, 根据用户需求建立抽取规则自动生成模板, 并依据模板的抽取规则对网页信息进行抽取。Lochovsky[14]提出DSE (Data-rich Section Extraction) 算法, 通过自顶向下深度优先遍历两棵同模板的网页树, 去除相同的子树并把剩余部分作为网页的主题内容。Road Runner[15]系统中的算法根据比较样本网页的HTML代码之间的匹配与不匹配部分来确定一个公用的包装器, 能够基本实现自动化信息抽取。
3、问题分析
现有的web信息抽取方法大致有三种:基于文档对象模型的方法、基于视觉特征的方法和基于自然语言处理的方法。由于网页是由HTML标签和文本信息混合组成的, 文本中含有大量的标签, 因此完整的句子通常被HTML标签所分隔。网页的这种结构特性为中文分词造成了很大的困难, 所以基于自然语言处理的方法在普通文本信息的抽取中具有的优势无法完全延续到web信息抽取领域中。Deng Cai[16]等最早提出了基于网页视觉特征的信息抽取方法, 但视觉特征非常复杂, 不同的标签可能会呈现同样的效果, 而且许多网站的布局并不规范, 这些因素都不利于基于视觉模式的发展。基于文档对象模型的方式克服了数据源的限制, 而HTML语言本身具有树结构的特点更加有利于这种方式的处理, 在实际应用中通常会结合统计学的理论, 因此成为目前发展最为迅速且抽取效果较好的一类方法。DSE算法和Road Runner中的算法是基于文档对象模型的方法中效果较好的两种, 但是DSE算法将两个同源页面的相同部分完全去掉的做法显然会增加丢失页面正文的可能性;而算法仅仅把HTML代码当作普通的字符串来处理, 忽视了其本身具有的结构特征。这两种算法均直接对结构复杂的页面进行处理, 没有考虑到首先去掉网页噪声等无用信息, 影响了处理效率, 并且, 针对每个网页都需要进行同样的重复的处理, 没有总结出一个适用于大部分页面的模板以免去多次重复处理的繁琐工作。
本文通过对DSE算法和算法的探究, 改进了上述这两种算法的不足, 并在将二者结合的基础上提出了一种新的web信息抽取方法。
4、算法流程设计
4.1 处理对象的选取
DSE算法只适用于两个同网站中结构相似的页面, 但原始算法中并没有指出如何去判定这样的两个网页, 也并未给出基于什么样的阈值来确定研究对象。本算法中引入了生物学中的FDR (False Discovery Rate, Benjamini, 1995) 算法。FDR算法是用来处理有n个输出的问题, 从中选取r个, 其中有s个是正确, v个错误, 那么错误的比率fdr=v/r, 试验中如果需要fdr小于某个阈值, 也就相当于在统计学中控制fdr不能超过这个阈值。根据Benjamini的证明, 对n个输出的p值从小到大排列, p (1) , p (2) ...p (n) , 如果想控制fdr不超过阈值q, 只需要找到最大的整数i, 使得p (i) <= (i*q) /m.然后, 挑选对应p (1) , p (2) , ..., p (i) 的输出, 就能满足阈值的需求。
由于两个url串的相似比值在0~1之间, 因此也可以看作是相似的概率, 也可以通过上述的算法来确定相似的程度, 把组成url的字母当作是n个输出, 已知阈值是0.05 (生物学实验中常用的阈值) , 那么就能根据上述公式来确定两个url的相似程度。
4.2 噪声的去除
DSE算法和Road Runner算法中并没有涉及到对页面进行预处理的过程, 直接对整个页面进行处理必然会占用大量的空间并且浪费处理时间。本文参考了现有处理方法的经验, 首先对网页中的一些明显的“噪声”进行处理, 针对过滤后的页面内容再进行运算处理。
本算法中采用的噪声去除方法是直接取出包含噪声的标签。统计数据表明, 网页中包含噪声的标签主要集中在以下几种:、、、
但是, 由于增加了对内容节点的比较, 所以从整体上看会比原始的DSE算法耗费更多的处理时间。
本文从上述四个方面改进了原始的DSE算法, 解决了原始算法没有对抽取对象进行预处理、处理相似度很高的页面时发生信息丢失、多次进行重复对比处理的问题, 下面概括介绍本算法的处理流程。 (图2)
本文以“中国木业网”的“供应”和“求购”信息页面为例, 在同等的硬件条件下对本算法和原始的DSE算法的处理效率进行了比较, 重点比较了准确率、召回率以及运行时间三项:
摘要：随着我国信息化进程的推进, 人们开始认识到互联网作为信息来源的重要性, 如何更有效地从网络的海量信息中抽取所需要的内容并进行合理的组织和利用已经成为亟待解决的问题。本文通过对DSE算法和RoadRunner系统中的算法的探讨和改进, 提出了一种新的自动生成模板的信息抽取方法, 并且在确定同模板网页url的阈值时引入了生物信息学中的FDR方法, 为阈值的确定提出了理论根据。实验结果表明, 经过改进的抽取方法对抽取结果的准确率有着明显的改善作用。