（模式识别与智能系统专业论文）基于页面浅语义化表示和条件随机域的web信息抽取研究.pdf

摘要 摘要 w e b 信息抽取( w e bi n f o r m a t i o ne x t r a c t i o n ) 是当前w e b 信息处理中的重要课题。其主要任务是对 页面中的目标数据进行分析，进而进行语义标注。具有语义标记的数据可精确地回答用户的查询，有极 广阔的应用前景。目前，w e b 信息抽取技术以知识工程、自然语言处理和统计学习为基础。其中基于统 计学习的技术是当前研究的热点。 本文将信息抽取问题分为特征获取、页面浅语义化表示和信息抽取( 语义标注) 三个部分，分别进行 研究，并通过实验分析来验证方法的有效性。 在特征提取部分引入了文本主题和页面分隔线两类特征。在比较特征权重计算、特征选择方法、分 类器和中文分词技术的基础上，构建并简化了用于获取文本主题特征的文本分类模块。在s o g o u 语料库 上两次文本分类实验的平均f l 值为8 1 2 5 。本文还将图像识别方法用于页面分隔线的提取，实验表明 该方法能较为准确地提取页面分隔线。 在页面浅语义化表示部分，首先提出了简化h t m l 布局规则和页面代码的页面结构调整算法，该算 法用h t m l 扩展子集重新描述页面，这种最简描述较好地解决了因页面模型复杂化而导致算法适应能力 下降的问题。然后研究了基于分隔线和混合距离的页面分块算法，以分离页面中内容不相关的块，获取 页面的块语义。实验表明，在分块任务中结构调整和分隔线特征分别使f l 值提高了+ 8 4 3 和+ 1 2 8 。 在信息抽取部分，将层次条件随机域( h c r f ) 模型用于标注页面数据的语义。研究了页面特征组合， 以及页面浅语义化表示和文本主题特征对信息抽取性能的影响。实验结果表明整体研究方案是有效的。 对比实验还表明采用文本主题特征和页面浅语义化表示能改善信息抽取性能，在相同样本上的f l 值分 别提高了+ 3 9 和+ 8 8 。 关键词：信息抽取，文本分类，分隔线检测，页面结构调整，布局语义，页面分块，层次条件随机域 东南大学硕士论文 a b s t r a c t w 曲i n f o r m a t i o ne x t r a c t i o nt h a ta i m st oa n a l y z et h ed a t ao nw e bp a g ea n dl a b e lt h e mt h es e m a n t i cr o l e s p l a y sa ni m p o r t a n tr o l ei nw e bi n f o r m a t i o np r o c e s s i n g t 1 l el a b e l e dd a mc o u l db ee m p l o y e dt oa c c u r a t e t y a l l s w d - q u e r i e sf r o mu s e r s w 曲i n f o r m a t i o ne x t r a c t i o ns t h ed e v e l o p m e n to ft e c h n i q u e s b a s e do n h l o w l e d g ee n g i n e e r i n g ，n a t u r a ll a n g u a g ep r o c e s s i n ga n ds t a t i s t i cl e a r n i n ge t c a m o n gt h e m , s t a t i s t i cl e a r n i n g i sc o n s i d e r e dt ob et h ek e yo fi n f o r m a t i o ne x t r a c t i o nb e c a u s eo fi t se x c e l l e n ta b i l i t yt om o d e lr e l a t i o n s h i p s a m o n g an u m b e ro f f a c t o r s t h et a s ko f i n f o r m a t i o ne x t r a c t i o ni sd i v i d e di n t ot h r e ep a r t si nt h i ss o l u t i o n ，r e s e a r c h e sa n de x p e r i m e n t s a r ee x e r t e dr e s p e c t i v e l y t o p i c so f p a g et e x t sa n dp a g es e p a r a t o r sa r ei n t r o d u c e dt os e g m e n tp a g e sa n da n n o t a t ed a t a 勰t w on o v e l f e a t u r e s i no r d e rt oe x t r a c tt o p i c sf r o mt e x t ，at e x tc l a s s i f i c a t i o ni sp r e s e n t e dw i t hc o m p a r i s o ns t u d i e so i l m e t h o d so f w o r df e a t u r e sc o n s t r u c t i o n ，w e i g h t i n ga n ds e l e c t i o n ta n dc o m p a r i s o ne x p e r i m e n t so f c l a s s i f i e ma n d c h i n e s ew o r ds e g m e n t e r s e x p e r i m e n t sc o n d u c t e do ns o g o uc o r p o $ s h o wt h a tw i t i is u c hm e t h o dt h e c l a s s i f i c a t i o na c c u r a c yr e a c h e s8 1 2 5 o nt h eo t h e rh a n d i m a g ep r o c e s s i n gm e t h o d sa r ee m p l o y e dt od e t e c t p a g es e p a r a t o r sw i t ht h ep e r f o r m a n c eo f 9 2 o n5 0 t e s tp a g e s t h ef u s ts t e po f t h es e c o n dp a r ti st or e c o d ew e bp a g e sw i t l ir o we l o m e n t c o l u m ne l e m e n ta n ds e q u e n t i a l l a y o u tr u l e w i t h o u tr e d u n d a n td o m n o d e s t l l i ss t e pw h i c hi sc a l l e dp a g es t r u c t u r er e g u l a t i o np r o d u c e sa s i m p l yp a g et r e ew i t hl a y o u ts e m a n t i c s p a g es e g m e n t a t i o nb yp a g es e p a r a t o r sf e a t u r ea n db r o a ds e n s e d i s t a n c e sd d 碱o nr e c o d e dp a g e si st h es e c o n ds t e p p a g es e g m e n t a t i o ne x p e r i m e n t sa r ec o n d u c t e do nf o u r g r o u p so fp a g e s ，a n dt h er e s u l t ss h o wt h a tt h ep r o c e s so fp a g es t r u c t u r er e g u l a t i o na n dp a g es e p a r a t o r sc a l l i m p r o v et h ef i - n l e a s u r eb y + 8 4 a n d + 1 2 8 o na v e r a g er e s p e c t i v e l y a c c o r d i n gt os o m ev a l u a b l ew o r k so nt h ea p p l i c a t i o no f c o n d i t i o n a lr a n d o mf i e l d s ，h i e r a r c h i c a lc r fi s c h o s et oa n n o t a t ea n de x t r a c td a t ao fp a g e t h ek e yt e c h n i q u ei nt h es o l u t i o n i n v e s t i g a t i o n sf o c u s e do n c o m b i n i n gp a g ef e a t u r e sa r et h ep r i m a r yt a s k e x t r a c t i o ne x p e r i m e n t sv a l i d a t et h es o l u t i o n ，a n dt h er e s u l t so f c o m p a r i s o ne x p e r i m e n t ss h o wt h a tw i t ht e x tt o p i cf e a t u r ea n dp a g es t r u c t u r er e g u l a t i o nt h ef l - m e a s o r ei s i m p r o v e db y 十3 9 a n d + 8 8 o na v e r a g er e s p e c t i v e l y k e yw o r d s ：i n f o r m a t i o ne x t r a c t i o n ，t e x tc l a s s i f i c a t i o n ，s e p a r a t o rd e t e c t i o n ，p a g es t i | r er e g u l a t i o n ， l a y o u t ，p a g es e g m e n t a t i o n ，h i e r a r c h i c a lc o n d i t i o n a lr a n d o mf i e l d s i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档， 可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保 密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的 公布( 包括刊登) 授权东南大学研究生院办理。 研究生繇垄虹新戤纽期：堕胆z 一 第一章绪论 第一章绪论 1 1 研究背景 万维网( w w ) 的迅速发展使w e b 成为重要的信息来源，逐渐渗入人们生活的每个角落。中国互联网 信息中心( c n n i c ) 的报告显示，截至2 0 0 6 年底国内网页数目达到4 4 7 亿个1 。这些网页中蕴藏了大量的 数据，但是只有很少的便于机器理解的知识。如何从海量的数据中抽取可理解的信息成为了研究人员和 企业关注的热点。w e b 信息抽取( i n f o r m a t i o ne x t r a c t i o n ) 正是产生于这种大背景之下。 w e b 信息抽取是信息抽取技术在w e b 中的应用。在w e b 信息抽取出现之前，对结构化文档和自然语 言的信息抽取研究已取得很多成果。但w e b 数据是种介于结构化文档和自然语言之间的独特的数据，原 有信息抽取技术无法满足w e b 信息抽取的要求。因此在已有信息抽取技术的基础上，需要发展新的技术 以适应w e b 环境下的数据。 w e b 信息抽取技术与w e b 信息检索( i n f o r m a t i o nr e t r i e v a l ) 有许多共同的任务和技术，同属于w e b 信息处理。w e b 信息检索技术广泛应用于搜索引擎，它以页面集合为处理对象，告知用户所查找的信息 存在于何处。但它无法将目标页面上与人们最相关的信息以结构化的形式直接展现出来 1 。w e b 信息 抽取技术弥补了信息检索技术的不足，它以单个页面为处理对象，从中抽取特定的事实信息( f a c t u a l i n f o r m a t i o n ) 2 。例如，从产品页面中抽取产品名称、价格和图片等信息；从研究机构主页中抽取研 究领域、论文成果、主要成员和联系方式等。抽取出的事实信息以结构化的形式存入数据库，用户查询 时系统自动寻找或构造与问题匹配的信息抽取模版，并根据抽取出的事实信息自动地生成答案。 目前，w e b 信息抽取主要用于特定领域，如采集购物信息、论坛信息，以及为企业获取商业信息等， 与w e b 信息检索构成良性互补。信息抽取的最终目标是将半结构化的页面数据结构化，即获取页面数据 的语义。为了达到这个目标，研究人员提出了许多方法 3 ，最初由人工编写抽取规则，到后来由工具 辅助生成抽取规则，目前研究的重点是从样本中学习抽取规则的自动抽取技术，这也是w e b 信息抽取最 有前途的方法。自动抽取技术的研究主要围绕特征的选择和提取，页面内容分离和语义标注模型展开。 1 2 w e b 信息抽取 信息抽取技术已经有了多年的研究和发展。其中1 9 8 7 年由n r a d ( n a v a lr e s e a r c ha n dd e v e l o p m e n t g r o u p ) 和n c c o s c ( n a v a lc o m m a n d ，c o n t r o la n do c e a ns u r v e ill a n c ec e n t e r ) 举办的首届删c ( m e s s a g e u n d e r s t a n d i n gc o n f e r e n c e ) 2 是其重要标志。此外2 0 0 0 年n i s t ( n a t i o n a li n s t i t u t eo fs t a n d a r da n d t e c h n o l o g y ) 发起的首届a c e ( a i i t o m a t i cc o n t e x te x t r a c t i o n ) 3 、a r d a ( a d v a n c e dr e s e a r c ha n d d e v e l o p m e n ta c t i v i t y ) 和d o c ( d o c u m e n tu n d e r s t a n d i n gc o n f e r e n c e ) 5 对信息抽取研究方向的确立和 发展起了巨大的推动作用。 w e b 信息抽取技术则是于2 0 世纪9 0 年代初期在w e b 的推动下发展起来的。与w e b 信息检索相比， w e b 信息抽取有三方面的不同 4 ：就目的而言，w e b 信息抽取从页面中抽取用户感兴趣的信息，信息检 索则是从页面库中查找和与用户查询有关的页面；就技术而言，w e b 信息抽取根据单个页面的内容结构 抽取特定的信息并结构化地保存，w e b 信息检索则依据页面内的关键词和页面间的链接对页面库进行排 1 h t t p ：- v c n n i c n e t c n h t m l d i r 2 0 0 7 0 1 2 2 4 3 9 5 h t m 2h t t p ：) n w f u l l s e a r c h e r c o m d o w n i n f o r m a t i o n e x t r a c t i o n 6 h t m l 3 h t t p ：w w w n i s t g o v s p e e c h t e s t s a c e i n d e x h t m 。h t t p ：v t c w i c - a r d a o i - g h t t p ：d u c n i s t g o v l 东南大学硕士论文 序和索引；就适用范围而言，w e b 信息检索与具体领域无关，而w e b 信息抽取需要针对具体领域设计。 现有的w e b 信息抽取技术包括基于自然语言理解 1 3 ，1 4 、文法推断 6 、树自动机 7 ，8 、统计理 论 9 3 和关系学习的技术 1 0 ，1 1 ，1 2 。基于自然语言理解的抽取技术相当于将页面退化为自然语言文档 进行处理；文法推断则将页面的半结构化特征形式化地表示为方法，并且通过归纳推理得到其语法定义； 页面形化地表示为树后，信息抽取过程看成树路径查询过程，用树自动机处理；通过统计方法还可训练 条件随机域( c o n d i t i o n a lr a n d o mf i e l d s ，c r f ) 等模型来识别目标数据；关系学习根据输入的一组已标 记相关事实信息的网页和一组待学习的特征属性进行学习，输出一组抽取规则。 文献 3 7 ，4 6 ，5 5 ，5 6 3 设计了完整的具有代表性w e b 信息抽取模型。首先根据视觉线索将页面逐层分 割为若干主题不相关的块 3 7 ，再用层次条件随机域( h c r f ) 对块及块中的数据进行语义标注 4 6 5 5 5 6 。h n d r e wg c c a l l u m 等人设计的w a l l e t 6 工具包整合了多种分类器、优化算法和特征选择 方法等信息抽取技术。w w w 7 ，i ( d 矿和s i g i r 9 等学术会议展示了w e b 信息抽取最先进的研究成果，c m u ， i i s r r ，s t a n d f o r d 和u m a s s “等研究机构代表了最高研究水平。在工业领域，微软推出的整合信息抽取 技术的l i v es e a r c h 引擎，各种以信息抽取技术为基础的垂直搜索引擎大量出现。 w e b 页由包含文本和h 删l 标签的h t m l 文档描述。h t m l 标签由w 3 c 的h t m l 规范“定义，可以表示数 据( 如标签 表示图片) 和标记数据的属性( 如代码 h e l l o 中的标签 表示文本h e l l o 显示为 斜体) 。如果一组标签明确地表明了其所修饰数据的具体意义( 称标签具有语义) ，那么用这组标签描述 的文档是容易理解的( 称文档为结构化文档) 。例如有一组标签 分别表示名称、类 型和价格，则文档 摩托罗拉 m p x 2 2 0 3 5 8 0 0 0 元 明确地告知这样的事实信息：型号为w p x 2 2 0 的摩托罗拉手机售价3 5 8 0 元。与上述标签相比，h t m l 标 签控制数据的外观，所描述数据的具体意义需要通过阅读获取；与自然语言文本相比，h t m l 具有丰富 的外观样式。h t m l 文档同时具有自然语言文档和结构化文档的部分特征，属于半结构化文档( 图卜i ) 。 图l 一1 文档的结构化程度 4 。h t t p ：m a l l e t c s u m a s s e d u i n d e x p h p m a i n - p a g e 7 h t t p ：w w w 2 0 0 7 o r g h t t p ：| | w s i g k d d o r g h t t p ：m s i g i r o r g ”h t t p ：r e s e a r c h m i c r o s o f t c o m a s i a g r o u p 向s m d e f a u l t a s p x “h t t p ：c i i r ，c s u m s s e d u ”h t t p ：m 柏o r g t r h t m l 4 0 1 2 譬；并i口蔓匹，麓zl口昱盏譬葺 第一章绪论 对于页面中的一组数据 日，d 2 ，见) ，数据项具有特征i = ( 葺，屯，) t 。数据项的特征由内容、 外观样式和在页面上的布局构成。w e b 信息抽取问题可描述为 ( 1 ) 对于数据项q ，根据其特征x 。推断数据项的语义； ( 2 ) 根据数据项之问的相互关系，寻找构成数据记录的数据集 b 。，口：，圾 。 h t m l 文档可形式化地表示为文档对象模型( d o c u m e n to b j e c tm o d e l ，d o m ) 1 3 9d 伽是种树结构模型。例 如图1 - 1 的图片及标题用h t m l 代码描述为 ， d i v 2 ) 图卜l 文档的结构化程度 4 代码所对应树的根结点为结点1 ，其子结点依次为2 和3 ，结点2 和3 的子结点分别为4 和文本结点。 对于表示为d o m 的页面，信息抽取问题可相应地描述为 ( 1 ) 对于d o m 中的数据结点口，根据其属性x 。、兄弟结点、子结点及父结点推断其语义； ( 2 ) 根据数据项所对应结点之间的相互关系，寻找构成数据记录的结点子集b ，b ：，z k 。 h t m l 文档同时具有文档结构和文本信息，因此有两类主要特征：文档结构特征。h t i l | i l 文档具有自 然语言文本所没有的层次结构( d 伽树) ，这种结构信息经浏览器解析后，呈现为数据的外观样式和布局 结构；事实信息还可能存在于文本，这时需要考虑文本特征。 与其它信息抽取任务相同，w e b 信息抽取系统也采用召回率( r e c a l l ) 、精度( p r e c i s i o n ) 和两者的 加权平均f 度量( f - m e a s u r e ) 作为评测标准。召回率( 式1 1 ) 反映了信息抽取系统的查全率；精度( 式 1 2 ) 反映了信息抽取系统的查准率：通常，召回率的提高会导致精度降低，精度提高同样会使召回率降 低，因此用f 度量( 式1 3 ) 来综合评价算法的优劣。 。抽取结果集合中正确的元素数量，1 、 ”删扣_ ；磊磊函磊霸两_ u u 抽取结果集合中正确的元素数量 ，m p 5p r e c i s 2 面两藻磊再元藕画一u 。纠 ，n r f m e a s u r e = ! 生 ( 1 3 ) p + 7 1 3 问题的提出和解决方法 w e b 信息抽取方法所针对的页面类型、目标数据类型和应用背景通常有所不同，所采用的页面特征、 处理流程和具体方法也有较大的差别。主要存在以下几方面问题：信息抽取过程中没有充分利用页面特 征如文本的主题；方法对不同页面类型的稳定性不好，这是因为相同页面的表示方法有很多种可能；模 型的特征整合能力有限。本文的研究目标就是对w e b 信息抽取中的问题进行改进，以适应不同的页面类 型、目标数据和应用背景。具体解决以下四个问题： ( 1 ) 页面特征提取。信息抽取时需要利用各类页面特征，如文本特征、基于标签树的特征和布局 特征。当前的方法通常忽略了文本主题和页面分隔线两类重要特征。针对这一情况，本文研究了文本主 题特征和页面布局特征的提取，及几类广义距离的计算。这些特征和广义距离将用于页面分块和数据的 语义标注。 ( 2 ) 页面模型复杂化。辅助设计工具使设计者不用关注具体实现( 具体代码) 而只需关心样式，这 些样式通常包含过多的代码，影响了分块和抽取方法的稳定性。本文提出一种页面外观的最简描述，通 过h t m l 的扩展子集唯一、等价地描述页面外观，以降低d o m 树结构规律性差，存在较多冗余结点这两 ”h t t p ：w w w w 3 o r g i ) ( 1 4 d o m t r 3 东南大学硕士论文 种噪声因素的影响。 ( 3 ) 页面主题混合化。例如在体育新闻页面中，笔记本电脑广告对体育内容形成了主题上的干扰。 由于页面中不同的内容块在结构、内容分布和主题上存在差异，并且有显式的分隔线或间隔，本文提出 根据分隔线和广义距离，对页面的内容进行分块和块标注。 ( 4 ) 整合各类特征抽取信息。信息抽取过程是对页面数据进行语义标注的过程，要求标注模型有 很强的特征整合和关系学习能力。本文采用条件随机域( c o n d i t i o n a lr a n d o mf i e l d s ) 模型进行w e b 信 息抽取，主要研究了特征间的关系和特征函数的定义。 1 4 内容安排和约定 本文的具体内容安排与上节中研究内容相对应。在第二章中将对常见的w e b 信息抽取方法进行简要 的介绍和总结，并在此基础对w e b 信息抽取任务进行分解。分解后的三个步骤分别对应本文的第三、四、 五章。 第三章介绍三类页面特征的表示，以及与文本主题和页面分隔线的提取方法。在这些特征的基础上， 介绍页面内容的广义距离的计算方法。其中分隔线在布局规则归一化和冗余结点去除( 页面结构调整， 第四章) 前提取，其它特征均在页面结构调整后提取。 第四章包括页面结构调整和页面分块两个相对独立的部分。前者包括布局规则归一化和冗余结点去 除两个步骤，将页面的d o m 转化为与之唯一对应的行列树( 相当于对结点进行行列标注) ；后者在行列树 的基础上对页面的内容进行分块( 相当于对结点进行块标注) 。行列和块是布局和内容上的浅语义，本文 称标注了浅语义的行列树为页面的浅语义化表示。 第五章介绍层次条件随机域的模型、参数估计、语义标注、页面特征和特征函数。在 3 7 ，4 6 ，5 5 ，5 6 的基础上结合页面的浅语义化表示进行信息抽取实验。 在本文有以f 说明和约定： ( 1 ) 同一页面的d o m 树、标签树和分析树的结构完全相同，是等价的形式化表示。d o m 包含的信 息与对应的h t m l 文档完全等价，浏览器内部h t m l 文档就是用d o m 表示。标签树通常只反应标签间的所 属和并列关系，不包含结点的属性信息。 ( 2 ) 标签、结点和元素是同一概念在不同环境下的称呼。例如，文档中的 标签，d o g 中的 t a b l e 结点，和呈现在页面上的表格元素完全对应。 ( 3 ) w e b 信息抽取在w e b 信息检索、文档分析和自然语言处理的基础上发展而来，因此本文中将 适当引用它们的定义和结论，在相关问题上对它们进行讨论。 4 第二章信息抽取技术概述 第二章信息抽取技术概述 执行信息抽取任务的程序通常称为分装器( w r a p p e r ) 3 】。它从特定的信息源中抽取相关内容，并以 特定形式加以表示。在数据库环境下，分装器是软件的组成部分，负责把数据和查询请求从一种模式转 换成另外一种模式。在w e b 环境下，分装器的目的是把网页中储存的信息用结构化的形式储存起来，以 方便进一步的处理。 本文仅讨论w e b 环境下的分装器。根据分装器生成方法的自动化程度，可以分为手工构造，半自动 化生成和全自动生成。 ( 1 ) 手工构造分装器通常需要编写专用的代码，要花很多时间理解页面的结构并将其转换成程序 代码。由于页面数量庞大，内容和结构繁杂，新的信息源不断增加并且旧的信息还会改变，因此这种手 工方法不仅烦琐而且容易出错。 ( 2 ) 半自动分装器规则生成技术得益于分装器生成辅助工具。例如，可以通过向导将需抽取信息 在页面中的位置告诉系统。通过图形界面，用户就可以通过演示编写程序，标示需要抽取的区域，方便 地得到分装器规则。这意味着在分装器编码过程中不需要专业知识，而且错误比手工编码少。但这种方 法仍需要用户重新学习新的站点，因为这种系统不能学习新的网站结构，也不能处理旧网站的结构变化。 ( 3 ) 全自动分装器的生成利用机器学习等方法，开发学习算法，设计出从非常简单到相对复杂的 分装器。即使是全自动的方法也需要人工专家的少量参与。系统必须通过学习，从例子中归纳出规则。 这个过程通需要人工指导。 本文只讨论分装器的全自动生成。全自动的分装器生成方法主要有基于归纳学习的方法、基于自然 语言理解的方法，基于h t m l 结构的方法和基于本体论( o n t o l o g y ) 的方法。其中以归纳学习为基础的方 法有基于文法推断的归纳学习、基于树自动机的归纳学习、基于统计理论的归纳学习、基于关系学习的 归纳学习。本章将分别介绍这些分装器的自动生成方法。在实验的基础上，本章还总结了影响信息抽取 效果的两个重要问题。 2 1 信息抽取技术分类 2 1 1 基于文法推断的方法 文法推断( g r a m m a r i n f e r e n c e ) 属于形式语言的归纳学习问题，它研究如何从语言的有限信息出发， 通过归纳推理得到语言的语法定义。g o l d 于1 9 6 9 年提出了语言的极限认知过程 5 ，这是文法推断的 经典理论模型。近年来，文法推断方法广泛应用于信息抽取领域 6 。 基于文法推断的学习将t f f m l 页面的半结构化特征形式化地表示为文法，其输入为人工标记的正例 样本集，输出方法可以是上下文相关文法、上下文无关文法、正则文法或自定义的其它类型的方法。如 6 提出的概率上下文无关文法( s t o c h a s t i cc o n t e x t f r e eg r a m m a r s ) 。 归纳学习一般认为，满足所有训练样例的、最简化的规则是具有可扩展性的最佳规则。因此文法学 习通常从可以满足所有训练样例的最特殊文法开始，采用替换、截断和去除重复等方法使文法一般化， 直至得到一个可以满足所有训练样例并且最简化的文法。卡耐基梅隆大学的咖删项目就是用这种方法 学习分装器规则 6 。它用上下文无关文法表示用户感兴趣的事实信息在h t m l 页面中的位置，并通过文 法泛化得到的目标文法作为分装器规则。 文法推断方法的优点是直观、完备。但是它需要对整个文本建立方法，而信息抽取中只有部分文本 是值得考察的线索；而且由于它的最小处理单元是d o m 结点，因此只有相关d o m 结点中仅包含用户目标 5 东南大学硕士论文 信息时，才能用此方法抽取信息，否则仍需结合文本信息去除相关d 叫结点中的无关信息；这种方法的 另一个不足是它需要手工标注大量的训练样例，训练结果的好坏依赖于被标注样例的相关性和设计者标 注样例的准确度。 2 1 2 基于树自动机的方法 树自动机( t r e ea u t o m a t a ) 的转换前状态和转换后状态都支持状态集合，这种特性使得树自动机能 够非常自然地处理树结构数据。由于h t m l 页面可以形式化地表示为d 删树结构，因此树自动机在基于 页面结构特征的w e b 信息抽取中逐渐被广泛使用 7 ，8 。2 0 0 4 年k u l e u v e n 大学k u l e u v e n 教授举办的 m i n iw o r k s h o pt r e ea u t o m a t a “会议中大量地讨论了树自动机理论在w e b 信息抽取领域的应用。 j u l i e nc a m e 等人将盹b 信息抽取过程看成是d o m 树路径查询过程。基于这一假设，提出了基于 树自动机理论的d o m 树查询路径生成算法n s t t ( n o d es e l e c t i n gt r e et r a n s d u c e r ) 7 。s t e f a n r a e y m a e k e r s 等人提出了一种基于树自动机的分装器学习算法，将高度为膏宽度为f 的d o m 子树作为分 装器学习的上下文 8 ，其中和的最佳大小可以通过学习算法自动获取。 2 1 3 基于统计理论的方法 隐马尔可夫模型( h i d d e nm a r k o vm o d e l ，删) 和条件随机域( c o n d i t i o n a lr a n d o mf i e l d s ，c r f ) 9 是信息抽取中应用最为广泛和成功的统计学习模型。能够整合元素特征和上下文信息为自然语言、形式 化语言以及为元素间关系建模。 m m 属于生成模犁( g e n e r a t i v em o d e l ) ，通过估计联合概率分布为对象建模。它等价于概率止规语 法或概率有限状态自动机。 嘲假设当前状态仅与其前一个状态有关( 马尔可夫假设) ；假设当前观察值 仅与当前状态有关( 独立性假设) 。学习完成后的h 删对应待抽取的域( f i e l d ) ，结束状态对应目标域， 其它状态描述目标域的上下文。 咖已成功应用于语音识别、手写体识别和中文分词，在自然语言处理领域取得了巨大成功。并且 广泛应用于自然语言文本信息抽取，可以从含有大鼍无关信息的文本抽取目标信息( 稀疏型信息) 。由丁二 h t 札半结构化文档中包含丰富的自然语言信息，因此删很自然地应用于w e b 信息抽取。 基于删的信息抽取方对新数据的具有良好的鲁棒性，并且训练耗时短：此外舢具有成熟的训练 和识别算法，训练算法可以学习拓扑结构和模型参数。其缺点是仅能考虑待抽取事实信息有限范围内的 上下文，例如b i - g r a m 或t r i - 6 r a m ，难以整合长距离的依赖，例如待抽取文本段中的语法和语义信息。 条件随机域属于判别模型( d i s c r i m i n a t i v em o d e l ) ，通过估计条件概率分布建模，是种新兴的统计 模型。与隐马尔可夫相比，条件随机域无需严格的独立性假设，可以整合长距离的复杂的依赖。但其训 练速度比舢要慢。本文的信息抽取就是通过条件随机域实现。 2 1 4 基于关系学习的方法 基于关系学习的信息抽取方法可用于结构化页面的分装器规则学习或者文本页面的模版一槽规则学 习，其输入是一组已标记相关事实信息的网页以及一组待学习的特征属性，输出为一组抽取规则。与 i h n f 类似，它通常用于从文本中抽取稀疏型信息。对于稀疏型信息，关系学习除了考虑基本的语法和句 法特征外，还考虑相关事实信息的上下文。 f o i l ( f i r s to r d e rl e a r n e r ) 1 0 是典型的自上而下的覆盖学习算法，通过不断向规则集中加入可 “h t t p ：m c s k u l e u v e ma c b e 厂s t e f a n r m w t a h t m l 6 第二章信息抽取技术概述 以满足训练样例的规则，它能够学习h o r n 子句表达的一阶谓词规则。m a r ye l a i n ec a l i f f 在 1 2 中提 到的r a p i e r 和c i i u 的咖项目中用到的s r v 算法 1 1 是两个有代表性的、基于f o i l 算法的、可用于 信息抽取的关系规则学习算法。r a p i e r 综合考虑了领域无关的词典和w e b 页面文本段中的词性特征 ( p a r t - o f - s p e e c h , p o s ) ，解决了现有信息抽取算法与领域相关的缺陷。实验证明，在最差的情况下 r a p i e r 算法能够取得精度8 5 和召回率5 4 的较好结果。s r v 算法中用到的特征包括：字串特征、关系 特征、语法或句法特征等。实验证明它能够达到9 0 的平均精度和4 0 的平均召回率。 相对于其它学习算法，关系学习算法不需要对页面结构和相关事实信息在页面中的特征做任何假 设，是一种通用的( g e n e r a l p u r p o s e ) 规则学习算法。同时它采用一阶谓词形式表示规则，不仅易于理 解还可以学习嵌套概念。与统计方法需要大量训练样例不同，此方法可以从很少的训练样例中迅速学习 有效规则。但是关系学习算法结果的好坏很大程度上取决于特征的选取的好坏和训练样例的优劣。 2 1 5 基于自然语言理解的方法 自然语言处理技术通常用于自由文本的信息抽取。基于自然语言的w e b 信息抽取技术将h 1 ，文档 视为文本进行处理。不同的是，在w e b 信息抽取中，用户通常只关心有限的感兴趣的事实信息，而不关 心文本在意义上的细微差别以及作者的写作意图等深层理解问题。因此只需进行浅层理解而不是真正的 文本理解。 基于自然语言理解的代表系统有r a p i 职 1 3 和w n i s k 1 4 。其处理分为生成抽取规则和执行抽取两 个过程。抽取规则可人工编制也可从人工标注的语料库学习得到。以w n i s k 以例进行说明。它从用户标 记的实例中学习抽取规则。w n i s k 根据分割符将源文档分割成多个实例，每个实例为一个语义相关的文 本块。例如，房地产广告的页面中的每一则广告称为一个实例。 学习过程中，w n i s k 每次将一组实例通过交互界面呈现给用户，用户图形界面中根据系统提供的实 例标记出感必趣的信息并定义模式。对于已标记样本中的每个句子，通过语法解析器和语义类解析器分 别进行语法标注和语义类标注( 如人名和机构名) ，获得用户所标记信息的语法成分和对应的语义类，由 此生成基于语法标记和语义类标记的抽取规则。 执行信息抽取时，对待抽取文本进行语法和语义标注，将标记后句子与前面得到的抽取规则进行匹 配，从而获得目标信息。其实质是根据语义项对应的语义类、语义项的上下文和语义项在句子中的成分 实现信息的定位，即根据语义和语法的双重约束实现信息抽取。例如，某个语义项只能出现在句子的关 系从句中。 基于自然语言的w e b 信息抽取技术的优势在于，可完成其它抽取技术无法完成的文本抽取信息的任 务。但它通常只适用于含有大量文本且文本合乎文法的h t m l 文档，而h t m l 文档中有大量结构不完整的 句子；其学习和抽取过程中没有利用h t m l 文档的层次特性因而不支持复杂对象的抽取，无法单独完成 w e b 信息抽取任务；此外其规则抽取过程需要大量的学习样本，速度较慢难以适应网上海量数据。 2 1 6 基于h t m l 结构的方法 基于h t m l 结构的方法的主要特点是依据h t m l 页面的结构特征来定位信息。在信息抽取之前通过解 析器将h t m l 文档解析成标签树，通过自动或半自动的方式产生抽取规则，将信息抽取转化为对语法树 的操作实现信息抽取。采用该类技术的典型系统有x w r a p 1 5 、r o a d r u n e r 1 6 、l i x t o 1 7 和w 4 f 1 8 。 r o a d r u n e r 训练时通过比较多个样本页面的结构，获得用正则表达式表示的该类页面的通用结构模 式。抽取时对样本页面和待抽取页面的结构进行比较，通过字符串不匹配和标签不匹配来归纳抽取规则。 由于比较的是一对结构相似的页面，字符串不匹配则说明该字符串可能是数据库的某个字段。若相似页 7 东南大学硕士论文 面存在标签不匹配情况，则先判断是否存在迭代项，若不存在则需要判断是否为可选项。 r o a d r u n e r 基本实现了全自动的信息抽取。但抽取结果粒度较粗，并且因缺少噪声处理而使系统健 壮性较差。研究人员对r o a d r u n e r 的方法进行了改进。 1 9 将a 1 i g n 算法中基于文档字符串流的比较改 进为基于文档标签树的比较； 2 0 提出的基于标签树的模式的匹配算法有效地提高了匹配效率； 2 1 改进了迭代结构的分析方法，只需处理单个页面而不用比较两个页面即可完成分析。但 1 9 ，2 0 ，2 1 依然 没有改变抽取出的数据缺乏语义信息的情况。 1 9 虽然提到了语义，但只是人工用后模式的方式附加。 2 1 7 基于o n t o l o g y 的方法 根据s t a n f o r d 学者t o mg r u b e r 的定义，o n t o l o g y 是帮助程序和人共享知识的概念化规范。在知 识表达和共享领域，o n t o l o g y 描述a g e n t 之间的概念和关系。基于o n t o l o g y 的系统利用对数据的描述 信息实现抽取。描述信息由专家编写，对网页结构的依赖较少。代表系统有b y u 2 2 和q u i x c r r e 2 3 ，2 4 。 b y u 系统中事先由专家人工编写其领域的o n t o l o g y 。根据o n t o l o g y 可生成信息抽取规则和存放目 标数据的数据库。系统根据边界分割符和启发信息将源文档分割为多个无结构文本块，每个文本块是对 某事物( 如汽车广告) 不同实例的描述。然后用抽取规则对每个无结构的文本块进行抽取并获得各语义项 的值。最后将抽取出的结果存入数据库中。