（计算机软件与理论专业论文）dynamicview中信息抽取系统的设计与实现.pdf

东南大学硕士学位论文d y n a m i c v i e w 中信息抽取系统的设计与实现 摘要 万维网( w w w ) 技术的不断发展促进了w e b 信息检索( w e bi n f o r m a t i o nr e t r i e v a l ，w i r ) 和 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 i e ) 的迅猛发展，如何从w e b 中抽取相关信息引 起了人们的广泛关注。 w e b 信息检索可用于从w e b 上的海量页面中找到相关信息所在的页面地址。与w e b 信息检索不 同，w e b 信息抽取可以从一个具体的w e b 页面中抽取出相关信息，并以结构化的形式描述。 现有的w e b 信息抽取算法可以分为以下两类：一是基于页面半结构化特征的信息抽取，例如h t m l 页面结构文法推断( g r a m m a ri n f e r e n c e ) 和页面分段( p a g es e g m e n t a t i o n ) ：二是基于自然语言文本 特征的抽取，例如模版槽填充( t e m p l a t ef i l l i n g ) 。与自然语言文本( f r e et e x t ) 信息抽取相比，w e b 上某个具体领域中已标记的页面数量较少，因此如何在减少手工工作量的基础上保证较高的信息抽 取系统的精度和召回率是有待解决的重要问题之一。 本文在分析现有信息抽取算法的基础上，从d y n a m i c v i e w 项目中信息抽取面i 临的问题出发，以 准确探测研究员主页中的研究兴趣为目的，设计了基于列表页面导航特性和结构模版规则参数学习 的研究员主页发现算法和基于页面分段技术的研究兴趣信息抽取算法。前者用于获取研究员的姓名 及其主页地址，它将w e b 信息检索技术和w e b 信息抽取技术结合，能够高精度地获取具有相同特征 的页面集合的问题。后者通过基于分隔符的页匠分段算法过滤无关数据，并根据本体表示的领域知 识从相关段落中抽取研究兴趣。本文将这两种方法运用到d y n a m i c v i e w 系统中，实验结果证明这种 方法是高效的、可靠的。 关键词：w e b 信息检索，w e b 信息抽取，机器学习，语义w e b 东南大学硕士学位论文d y n a m i c v i e w 中信息抽取系统的设计与实现 a b s t r a c t w i t t lt h eg r o w i n go f w o r l dw i d ew e b ( w w w xw i ra n dw i et e c h o n o l o g yh a sb e e nd e v e l o p e dr a p i d l y m o r ea n dm o r er e s e a r c h e r sa r ep a y i n ga t t a t i o nt oh o wt oe x t r a c t i o ni n f o r m a t i o nf r o mt h ew e b w l rc a l lb eu s e df o rl o c a t i n ga s p e c i f i cp a g et h a tc o n t a i n st h er e l e v a n ti n f o r m a t i o no nt h ew e b u n l i k e w i r , w i ec a ne x t r a c tm v e l a n ti n f o r m a t i o nf r o mas p e c i f i cp a g ed i r e c t l ya n dt r a n s f o r mt h er e v e l a n t i n f o r m a t i o ni n t os t r u c t u r a lf o r m a t g e n e r a l l ys p e a k i n g , w i em e t h o d se a r lb ed i v i d e di n t ot w oc a t e g o r i e s ：o n ei sb a s e do ns t r u c t u r eo f ap a g e s u c ha sp a g es t r u c t u r eg r a m m a ri n f e r e n c ea n dp a g es e g m e n t a t i o n ；t h eo t h e ri sb a s e do nl a n g u a g ef e a t u r e o fap a g e c ha st e m p l a t ef i l l i n g u n l i k ef r e et e x ti n f o r m a t i o ne x t r a c t i o n , t h en u m b e ro fa n n o t a t e dw e b p a g ef o ras p e c i f i cd o m a i no nt h ew 曲i ss m a l l h e n c e , h o wt oe x t r a c ti n f o r m a t i o nw i t hh i g l la c c u r a c y w i t h o u ti n c r e a s i n gt h et e d i o u sm a n u a lw o r ki sac r i t i c a lp r o b l e mt ob es o l v e d b a s e do nt h ea n a l y s i so fe x i s t i n gw i ra n dw i ea l g o r i t h ma n dt h et a r g e to fd y n a m i c v i e wp r o j e c t , t h i s t h e s i sp r o p o s e saw i ra l g o r i t h mb a s e do ns t r u c t u r et e m p l a t et og e tt h ef a c u l t y sh o m e p a g ef r o mt h ew 曲 a n dap a g es e g m e n t a t i o nb a s e dw i ea l g o r i t h mt oe x t r a c tt h ef a c a l t y s r e s e a r c hi n t e r e s tf r o mt h e i r h o m e p a g e s t h ew i ra l g o r i t h ma p p l i e sw i et e c h n o l o g yi n t ow i ra l g o r i t h m i nt h i sw a y , t h ew e bp a g e s w i t ht h es a m ea t t r i b u t e sc mb ef o u n de a s i l y t h ep a g es e g m e n t a t i o na l g o r i t h md e s e af i ) e l i m i t e rb a s e d s e g m e n t a t i o na l g o r i t h m ) f o rw i ec a nb eu s e dt of i l t e ri r r e l e v a n ti n f o r m a t i o no u ti naw e bp a g e a t i e rt h i s , r e s e a r c hi n t e r e s t e sc a l lb ee x t r a c t e de a s i l yf r o mt h er e l e v a n ts e g m e n t su s i n gt h ed o m a i nk n o w l e d g e e x p e r i m e n t ss h o wt h a tt h e s et w oa l g o r i t h m sf i tc o m m e n d a b l yw i t hd y n a m i c v i e w k e yw o r d s ：w e bi n f o r m a t i o nr e t r i e v a l ，w e bi n f o r m a t i o ne x t r a c t i o n ，m a c h i n el e a r n i n g , s e m a n t i cw e b 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：鱼杰自日期：罂堕生7 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：鱼董函 导师签名：b 丝 日期：幽珂 东南大学硕士学位论文 1 1 研究背景 d y n a m i c v i e v , , 中信息抽取系统的设计与实现 第一章绪言 随着万维网技术( w w w ) 的不断发展，w e b 逐渐变成重要的信息来源，如何从海量的 w e b 页面中抽取信息引起了人们的广泛关注。w 曲信息检索( w e bi n f o r m a t i o nr e t r i e v a l ，w i r ) ：手i l w e b 信息抽取( w e bl n f o r m m i o ne x t r a c t i o n ，w i e ) 正是在这种背景下产生的。 w e b 信息检索技术被广泛应用于w e b 搜索引擎领域。它以w e b 上所有页面的集合为处理 对象，仅能告知用户信息的存在性及可以从何处找到所需的信息，却无法将相关信息以结构 化的形式直接展现给用户【1 】因而w e b 信息抽取技术应运而生。w e b 信息抽取技术被广泛应 用于q a ( q u e s t i o n - a n s w e r i n g ) 系统中【3 0 】：它寻找或构造与q u e s t i o n 匹配的信息抽取模版。 并根据抽取出的事实信息自动地生成a n s w e r 。与w e b 信息检索不同，w e b 信息抽取的处理对 象是单个页面，用于从单个w e b 页面中抽取出特定的事实信息( f a c t u a li n f o r m a t i o n ) 【7 】。比 如，从新闻报道中抽取恐怖事件的详细情况：时间、地点、恐怖分子、受害者、被袭击目标、 使用的武器等；从经济新闻中抽取公司发布新产品的情况：公司名、产品名、发布时间、产 品性能等；从病人的医疗记录中抽取症状、诊断记录、检验结果、处方等。被抽取出的信息 以结构化的形式直接存入数据库中，供用户查询或进一步分析。 w e b 信息抽取系统与w e b 信息检索系统的差异主要表现在三个方面：1 ) 功能不同。w e b 信息检索系统主要用途是从大量的页面集合中找到与用户查询相关的页面列表；而w e b 信息 抽取系统则旨在从页面中直接获得用户感兴趣的事实信息；2 ) 处理技术不同。w e b 信息检 索系统的考察对象是w e b 上所有页面的集合，考察对象的最小单元是单个页面，它基于链接 分析、关键词匹配等技术，不需要对单个页面进行深入分析理解；而w e b 信息抽取的考察对 象是单个页面，考察对象的最小单元是页面块( p a g eb l o c k ) ，需要对页面的内部结构和文 本特征进行分析处理后才能完成；3 ) 适用领域不同。由于采用的技术不同，w e b 信息检索 系统通常是领域无关的；而w e b 信息抽取系统则是领域相关的，一般只能抽取预先设定好的 有限种类的事实信息。 但另一方面，w e b 信息抽取与w e b 信息检索又是互补的。为了处理海量页面，w 曲信息 抽取系统通常以w e b 信息检索系统的输出作为输入；而w e b 信息抽取技术又可以用来提高 w e b 信息检索系统的性能。二者的结合能够更好地服务于用户的信息处理需求。 1 2w e b 信息抽取 w e b 信息抽取属于信息抽取领域。信息抽取可以分为自然语言文本( f r e et e x t ) 信息抽 取、w e b 信息抽取和语音、图像、视频等其他类型的媒体数据信息抽取等。 其中自然语言文本信息抽取已有多年的发展历史，以1 9 8 7 年5 月由n r a d ( n a v a l r e s e a r c h a n dd e v e l o p m e n tg 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 n s u r v e i l l a n c ec e n t e r ) 举办的首届m u c ( m e s s a g eu n d e r s t a n d i n gc o n f e r e n c e ) 1 会议为标志， 它与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 d sa n dt e c h n o l o g y ) 在2 0 0 0 年举办的首届a c e h t t o ：w w w f u l l s e a r c h e r c o m d o w n l n f o r m a t i o n e x t m e t i o n 6 h t m l 第1 页 东南大学硕士学位论文d y n a m i c v i e w 中信息抽取系统的设计与实现 ( a u t o m a t i cc o n t e n te x t r a c t i o n ) 。、a r d a ( a d v a n e e dr e s e a r c ha n dd e v e l o p m e n ta c t i v i t y ) 和 n i s t 在2 0 0 0 年发起的d u 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 ) 三大会议起对信息抽 取研究方向的确立和发展起到了巨大的推动作用。 定义：w e h 页面具有结构化文档和自然语言文档的特征，属于半结构化文档页面。结构化 文档严格遵循事先定义的页面格式。自然语言文档由符合语法规范的完整的句子和段落组 成。半结构化文档位于结构化文档和自然语言文档之间，它没有结构化文档中严格的页面格 式，但却包含自然语言文档中不存在的与语法定义不符的不规范短语。 与自然语言文本信息抽取不同，w e b 信息抽取的出现时间较晚，2 0 世纪9 0 年代初期 w e b 的出现推动了w e b 信息抽取技术的发展。它的处理对象为半结构化页面上的文本抽取 帮壤岱匏罨媳岛。本文主要讨论对半结构化h i m 页面中特定文本事实信息的抽取，与钮羝 语言文本相比，w e b 页面位置分散、数晕多、且会动态变化，因此手工抽取半结构化h t m l 页面中的特定事实信息是不现实的。本文中提到的半结构化h t m l 页面的信息抽取都是指半 自动或自动方法的信息抽取技术。为了完成这一任务，需要考虑半结构化h t m l 页面的两个 特征： l 、从整体上看，h t m l 页面可以被形式化地表示成文档对象模型( d o c u m e n to b j e c t m o d e l ，i x ) m ) ，因此它具有自然语言文本没有的结构化特征。如果相关事实信息 以结构化形式直接存储在h t m l 页面的表格 或列表 结构中，则可以利用页 面的结构特征直接抽取；反之，如果相关的事实信息以自然语言段落的形式存在， 也可以利用这一结构特征定位事实信息所在的d o m 树节点的位置： 2 、当相关的事实信息以自然语言段落的形式存在于d o m 树节点内部时，需要利用文 本信息抽取方法抽取事实信息。 综合上述两点，如何利用页面的结构化特征，结合文本信息抽取方法，是半结构化h t m l 页面信息抽取需要解决的主要问题。 与自然语言文本信息抽取的任务类似，半结构化h t m l 页面中特定文本事实信息的抽取 任务可以分为以下几种类4 0 , 模板- 槽的填充( t e m p l a t ef i l l i n g ) ，场景模板填充( s ：e n s z j o t e m p l a t e s f i l l i n g ) 填充、命名实体识别( n a m e d e n t i t y r e c o g n i z e ) 、共指关系确定( c o r e f e r e n c e r e l a t i o nr e c o g n i z e ) 、模板元素填充( t e m p l a t ee l e m e n tf i l l i n g ) 。 类似的，半结构化h t m l 页面信息抽取系统的评测标准也采用召回率( 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 所示；精度反映了w e b 信息抽取系统的查准率，如公式1 2 所示。 通常，召回率提高会导致精度降低，同样精度提高时召回率也会降低，因此f 度量被引入 用来综合评价算法的优劣，如公式1 3 所示。 ，：r e c a l l ：堂骘堡篁型墼李塑量 ( 式1 1 ) 7 。 2 甄磊茬雨舔甄r a1 j p = = 驾蒜纂蒜群 c式12precision ， p2 2 丽丽羽獯否霸磊丽万_ l a p m e a s u r e = f r( 式1 3 ) p + ， 1 3 研究目标 本文以d y n a m i e v i e w 项目为背景，探讨如何从海量的半结构化h t m l 页面中抽取特定文 2 h t t o ：w w w n ，i s t g o v s ，o ，e e c h 。t e s t s a c , e i n d e x h f f n 3 自强业虫丝出竖蛐趔 第2 页 东南大学硕士学位论文d y n a m i c v i e w 中信息抽取系统的设计与实现 本事实信息的问题。d y n a m i c v i e w 项目是一个可供研究员查询计算机科学的研究领域分布状 况及其发展趋势的语义w e b 门户( s e m a n t i c w e b p o r t a l ) ，它参加了i s w c 2 0 0 5 ( 4 t h i n t e r n a t i o n a l s e m a n t i cw e bc o n f e r e n c e ) 4 举办的s e m a n t i cw e bc h a l l e n g e 比赛5 ，并获得前五名。其中研究 领域分类基于a c m 标准，如图1 1 所示。 图1 1 包含实例节点的a c m 学科分类标准 d y n a m i c v i e w 项目可以提供以下三点功能： 1 ) 获取基于a c m 分类标准的研究员数量的分布状况。例如，图1 2 显示了2 0 0 5 年中 美两国在i n f o r m a t i o ns y s t e m 领域的研究员数量的分布状态，地图上的突出圆点表 示大学的地理位置，圆点的面积与该学校在待查询研究领域的研究员数量成正比； 2 ) 得到中美两国2 0 0 0 2 0 0 5 年研究领域的发展趋势。例如，图1 3 显示了中美两国近 五年内“机器学习”领域的研究员数量的变化趋势； 3 ) 得到中美两国2 0 0 0 - 2 0 0 5 年的十大热门研究领域及领域中的研究员数量。例如，图 1 4 显示了中美两国2 0 0 5 年的十大热门研究领域和领域中的研究员数量。 d y n a m i c v i e w 项目通过为用户提供了以下三种查询机制实现上述三项功能： 1 ) 用户输入待查询的年份t 【2 0 0 0 ，2 0 0 5 、地理位置j 中国，美国 和感兴趣的 研究领域0 a c m 分类标准中的非实倒节点) 后，系统返回研究领域0 在 时间t 、地理位置s 的范围内的研究员数量甩； 2 ) 用户输入待查询的地理位置s 中国，美国) 和感兴趣的研究领域 o e a c m 分类标准中的非实例节点 之后，系统返回2 0 0 0 - 2 0 0 5 年在地理 位置s 的范围内研究人员的数量，从而反映了研究领域0 的发展趋势尸( 0 ) ； 垃鲤型幽签生壁鲢血星璺出熊盟k 鲤型衄磐皇苫丛翘熊 h t t t ：e h a l l e n e e s e m a n t l c w e b o r g 第3 页 东南大学硕士学位论文d y n m n i c v i e w 中信息抽取系统的设计与实现 3 ) 用户输入感兴趣的年份t 2 0 0 0 ，2 0 0 5 】和地理位置j 中国，美国) 后，系统返 回在时间f 、地理位置s 的范围内所有a c m 分类标准中非实例节点的研究领 域的研究人员数量甩。 ( a ) 美国 ( b ) 中国 图1 2 中美两国基于a c m 分类标准的“信息系统”领域的分布状况( a ：美国；b ：中国) 第4 页 东南大学硕士学位论文d y n a m i e v i e w 中信息抽取系统的设计与实现 图1 3 中美两国在“机器学习”领域五年内的发展趋势 ( a ) 美国 ( b ) 甲国 图1 4 中美两国2 0 0 5 年的十大热门计算机研究领域( a ：美国；b ：中国) 为了完成上述任务，d y n a m i e v i e w 系统通过收集并统计大学中所有研究员( f a c u l t y ) 的 第5 页 东南大学硕士学位论文d y n a m i c v i e w 中信息抽取系统的设计与实现 研究兴趣得到研究领域的人员分布状态和发展趋势。如果某个研究员的研究兴趣包含0 。那 么领域0 的研究员数量增加1 。因此是否能够精确地得到研究员的研究兴趣成为影响系统可 性度和可用性的关键，也是d y n a m l c v i e w 项目首要解决的问题之一。 本文的目标是设计并实现一种w e b 信息抽取算法，该算法能够从现存的海量w e b 页面 中抽取美国计算机系t o p 5 0 大学中计算机系所有研究员( f a c u l t y ) 的研究兴趣，在保证较高 的抽取召回率和精度的前提下，减少算法的手工工作量，从而减少手工错误，并降低算法向 其他领域扩展的复杂度。 1 。4 研究内容 为了实现上述研究目标，本文需要解决以下两个问题： l 、如前所述，为了从海量页面中抽取研究员的研究兴趣，首先必须使用信息检索技术 得到存放研究兴趣的页面地址。但是现有的信息检索系统，例如g o o g l e 、y a h o o 、a o l s e a r c h 、 t e o m a 、b a i d u 6 等，普遍存在返回结果中不相关的页面数量多、没有按照正确的相关度排序 等不足。而且直接使用现有的信息检索系统无法精确地得到具有相同特征的所有页面的集 合，例如某个大学中所有研究员的主页地址。 2 、找到信息存放的页面后，就要使用信息抽取算法从中抽取研究兴趣。观察发现，研 究员主页通常为h t m l 页面，研究兴趣以如下两种方式存储：一是以词汇列表的方式存放在 页面的表格或列表结构中；二是以自然语言文本段的方式存放在一个或多个单句中。因此需 要精确地定位研究兴趣在页面中的出现位置，并从中抽取出研究兴趣。 1 5 解决方案 本文在分析信息检索和信息抽取方法的基础上，针对d y n a m i c v i e w 的目标，使用如下 方法解决上述两个问题： 1 ) 设计并实现了基于列表页面的研究员姓名和主页地址发现方法 本文假设在研究员主页上一定会存在对其研究领域的描述，通过将信息抽取技术引入到 信息检索系统中，准确地定位研究员的主页地址：1 ) 首先找到包含某大学所有研究员姓名 及其主页地址的列表页面：2 ) 接着使用信息抽取技术从中抽取出研究员的姓名和主页地址， 即“人名链接”对。 该方法在使用g o o g l ea p i 获得列表页面的基础上，使用a n n i e ( an e a r l y - n e w i n f o r m a t i o ne x t r a c t i o ns y s t e m ) 提供的人名识别技术得到列表页面上的部分“人名一链接”对 作为训练样例，利用顺序覆盖学习算法( s e q u e n t i a lc o v e r i n ga l g o r i t h m ) 得到描述“人名一 链接”对在页面中所处位置的结构模版规则集的参数值，井利用该规则集抽取出列表页面中 的“人名链接”对。 2 ) 设计并实现了一个基于分隔符的h t m l 页面分段算法，并将该算法应用到信息抽取 过程中 对于存放在结构化段落中的研究兴趣，采用与第一个问题相似的基于结构规则集的信息 抽取算法。这种方法仅能处理在 、 、 和 、颜色线索( c o l o r c u e ) ，例如 、大小线索( s i z ec u e ) ，例如 等。它通过模拟人类理解w e b 页面的方 法，对基于结构标签的分段算法做出改进。实验证明，即使页面的结构表示信息和内容不一 致，正确的将页面分为语义一致的段落，从而为w e b 信息抽取提供基础。 2 2 3 基于文法推断的w e b 信息抽取 基于文法推断的w e b 信息抽取方法将h t m l 页面的半结构化特征形式化地表示为文法。 文法推断( g r a m m a ri n f e r e n c e ) 属于形式语言的归纳学习问题，它研究如何从语言的有限信 息出发，通过归纳推理得到语言的语法定义。最近几年，文法推断方法被广泛用于w e b 信 息抽取领域【3 8 】。它的输入由手工标记的正例样本集组成，输出文法可以是上下文相关文法、 上下文无关文法、正则文法或自定义的其它类型的文法，例如【3 8 偎出的概率上下文无关文 法( 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 ) 。式2 1 表达了概率上下文无关文法的一般格式，其中 m 是出现在集合s 中的元素，p l 代表了w i 出现的概率。 s 呻w 1 1 w 2 | | 慨，岛，】 ( 式2 2 ) 第1 1 页 东南大学硕士学位论文d y n 啪i c v j e w 中信息抽取系统的设计与实现 g o l d 于1 9 6 9 年首次提出了文法推断的经典理论模型一语言的极限认知过程【4 2 】。g o l d 同 时证明。在只提供正例的条件下，无法得到语言的正确文法描述；只有同时存在正反例，才 能够正确的完成语言的极限认知过程，成功地