（计算机应用技术专业论文）基于结构与视觉一致性的网页新闻提取研究及应用.pdf

浙江大学硕士学位论文 摘要 摘要 随着互联网的大规模普及和持续高速发展，成千上万的新闻网站应运而生并 源源不断发布海量新闻网页。然而计算机程序并不能直接地理解新闻网页中哪些 部分是新闻标题和正文，因而无法对网页中的内容进行有效检索。因此在网络应 用背景下的信息检索对信息自动提取技术存在巨大需求。 本文中研究了两种各有特点的网页新闻提取技术，并基于这两种技术设计及 实现了一个网页新闻提取系统。1 ) 本文首先研究了一种基于新闻网页结构一致性 的网页新闻提取算法。该算法基于网页模板自动推导，并紧密结合新闻网页的结 构一致性特点：通过填充模板动态生成的网页中包含的数据尽管各不相同，但都 具有相似的网页结构。该算法在传统的模板推导算法基础上引入了重复模式归并 技术，提高了网页聚类过程的准确性。此外该算法通过有效利用少量的用户标注， 有效区分了网页模板中的重要和无关内容。2 ) 本文随后研究了一种基于新闻网 页视觉一致性的网页新闻提取算法。该算法具有与模板无关的优点，能够提取由 未知模板生成的新闻网页。该算法基于机器学习模型的泛化能力，有效地抓住了 新闻网页的视觉一致性特点：新闻网页中新闻标题和正文部分都具有符合用户阅 读习惯的版式设计。本算法为新闻标题和正文分别设计了专门的空间和内容特 征，有效表达了新闻网页设计的长期实践中积累而成的视觉一致性。最终在2 4 个中英文网站的7 5 9 4 个网页上的实验表明，本系统具有较高的提取准确率。 关键词：网络信息自动提取，分类，支持向量机，网络挖掘，封装器 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t w i t ht h em a s s i v ep o p u l a r i t yo ft h ei n t e r n e t ，t h o u s a n d so fn e w ss i t e sh a v ee m e r g e d ， w h i c hc o n t i n u o u s l yp u b l i s h e dm a s s n e w sp a g e s h o w e v e r , c o m p u t e r p r o g r a m sc a nn o t d i r e c t l yu n d e r s t a n dt h en e w sh e a d li n e sa n dn e w sb o d i e sf r o mw e bn e w sp a g e s t h e r e f o r e ，i nt h ec o n t e x to fw e bi n f o r m a t i o nr e t r i e v a l ，t h e r ei sah u g ed e m a n df o r a u t o m a t i ce x t r a c t i o nt e c h i n q u e s w ep r o p o s et w ok i n d so fw e bn e w se x t r a c t i o na l g o r i t h m s t h e nw ed e s i g na n d i m p l e m e n ta nw e bn e w se x t r a c t i o ns y s t e mw h i c he f f e c t i v e l yc o m b i n e st h e s e st w o e x t a c t i o na l g o r i t h m s 1 ) b a s e do nt h es t r u c t r u a l c o n s i s t e n c yo fn e w sp a g e s ，w e p r o p o s eat e m p l a t e - d e p e n d e n tn e w se x t r a c t i o na l g o r i t h m i ti n d u c et e m p l a t e sb y m a k i n gf u l lu s eo ft h es t r u c t r u a lc o n s i s t e n c yp r o p e r t y ：d y n a m i cp a g e sa r ep r o d u c e db y f i l l i n gs o m ep r e d e f i n e dt e m p l a t e sw i t hs t r u c t u r e dd a t a a n dw ei n t r o d u c eas m a l l n u m b e ro fu s e r sl a b e l i n gt o h e l pd i s t i n g u i s hi m p o r t a n ta n du s e l e s sp a r t si nt h e t e m p l a t e s 2 ) b a s e d o nt h ev i s u a lc o n s i s t e n c yo fn e w sp a g e s , w e p r o p o s ea t e m p l a t e i n d e p e n d e n tn e w se x t r a c t i o na l g o r i t h m 。w i t ht h eg e n e r a l i z a t i o na b i l i t yo f m a c h i n el e a r n i n g ，w ee x p l o r et h ev i s u a lc o n s i s t e n c yp r o p e r t y ：n e w sh e a d l i n e sa n d n e w sb o d i e sa r ea l w a y sd e s i g n e di n t oc o n s i s t e n ts t y l e sa n dl a y o u t s s p e c i a lf e a t u r e s a n dm o d e l sa r ed e s i g n e df o ri d e n t i f y i n gn e w sh e a d l i n e sa n dn e w sb o d i e s f i n a l l y , e x p e r i m e n t so n7 5 9 4w e bn e w sp a g e sf r o m2 4n e w ss i t e ss h o wt h a to u rn e w s e x t r a c t i o ns y s t e mh a sah i g he x t r a c t i o na c c u r a c y k e y w o r d s ： a u t o m a t i ci n f o r m a t i o ne x t r a c t i o n ，c l a s s i f i c a t i o n ，s u p p o r tv e c t o r m a c h i n e ，w e bm i n i n g ，w r a p p e r 浙江大学硕士学位论文 图目录 图目录 图2 1 树结构匹配1 1 图2 - 2 自顶向下保序匹配示意1 2 图2 3r t d m 算法主要步骤。1 3 图2 - 4 自顶向下保序简单匹配示意1 4 图2 5s t m 算法主要步骤1 5 图2 - 6 多种可能的最大匹配示意1 5 图2 7 两类数据的分类超平面示意图1 7 图2 8 分类超平面性质示意图18 图2 - 9s v m 分类超平面示意图1 9 图3 1 基于结构一致性的网页新闻提取算法整体框架2 4 图3 - 2 重复模式归并。2 7 图3 3 提取规则说明2 8 图3 _ 4 封装器标注过程2 9 图3 5 提取过程示意。3 0 图4 1 基于视觉一致性网页新闻提取算法整体框架3 2 图4 - 2 新闻标题示例3 3 图4 3 新闻标题的h t m l 代码示例3 4 图4 4 内容提要示例3 4 图4 5 文章副标题示例3 4 图4 - 6 重大新闻滚动播报示例3 4 图4 7 环绕标题的大量干扰信息示例3 5 图4 8 文本格式化元素示例3 7 图4 9 新闻正文提取算法一3 9 图4 1 0 新闻标题提取算法4 3 图4 ii 环绕标题的类别信息示例4 4 图4 1 2 环绕标题的类别信息示例4 5 图5 1 新闻提取系统结构4 6 图5 2 视觉特征不明显的新闻网页4 7 图5 3 训练数据标注软件4 8 图5 - 4 基于结构大规模提取实验结果5 0 图5 5 基于视觉大规模提取实验结果5 3 图5 - 6 新闻提取示例一5 4 图5 7 基于结构和视觉大规模提取详细实验结果5 5 图5 8 与基准方法对比实验结果5 5 浙江大学硕士学位论文 表目录 表目录 表3 1 封装器合成规则。2 7 表5 1 实验数据集4 9 表5 - 2 训练数据选取实验结果5 l 表5 3 标题特征效果衡量实验结果5 2 表5 4 正文特征效果衡量实验结果5 2 l v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得浙江太堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解逝堑太堂有权保留并向国家有关部门或机构送 交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝堑太堂可以 将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字目期：年月 日 导师签名： 签字目期：年月 日 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 研究背景 信息提取的研究起源于实际需求。信息提取最早是自然语言处理的一个分支 领域，研究从自然语言文档中提取语法和语义相关的结构化信息，如从句子中提 取名词，动词等等主要语法成分，提取命名实体及实体间的关系等。随着互联网 的大规模普及和持续高速发展，全球网站数量据统计已经过亿，网页数量据估计 达千亿。网络信息形式多样，质量参差不齐，而网页新闻是其中很重要的一类高 质量资讯。自诞生以来，浏览网页新闻就是人们上网的主要目的之一。网页新闻 因其及时性、内容多样性等传统媒体难以比拟的优势，而成为民众获取最新信息 的重要渠道。没有一家新闻网站能够覆盖所有的资讯，并满足各种用户的形形色 色需求。幸而互联网的开放性导致了网站的建设成本远低于传统媒体，因此诞生 了成千上万的新闻网站。这些网站共同源源不断发布的海量新闻网页构成了互联 网上网页的重要组成部分。 有效地自动检索、理解这些海量信息的重要性凸现出来。目前网络信息检索 服务主要由百度和g o o g l e 等搜索引擎提供。搜索引擎通过网络爬虫抓取并分析互 联网上的网页。然而由于语义网的发展情况所限，现有的网页编写规则只考虑了 页面上的h t m l 元素的版式、样式设计，而没有考虑对机器理解网页提供语义支 持，例如计算机程序并不能直接地理解新闻网页中哪一部分是新闻标题，哪一部 分是新闻正文。不能理解网页的语义，就不能区分网页中的重要信息和无关信息， 也就无法对网页中的内容进行有效的检索。因此在网络应用背景下的信息检索对 信息自动提取技术存在巨大需求。由于网页数量巨大无法通过人工一一编写，动 态网页技术应运而生并发展成为主要的网页制作技术。动态网页技术预先通过模 板指定网页结构，而后查询后台数据库并将查询结果填充入已有模板的预定位置 中动态生成网页。因而通过填充模板动态生成的网页具有相似的结构，但是包含 的数据却各不相同。这一重要特点使得有效的网页信息提取技术成为可能。 浙江大学硕士学位论文第1 章绪论 1 2 面临的挑战 信息提取在自然语言处理领域中的研究历史悠久，已经出现了较多的成熟技 术。而信息提取技术在网页中的应用研究起步不久，而网络的基础设施和网站、 网页数量迅速增长，网页信息提取技术面临着持续快速增长的挑战。 中国互联网络信息中心( c n n i c ) 发布的第2 3 次中国互联网络发展状况统计 报告中给出了中国境内登记备案的网站数及其网页数的两组统计数据：1 ) 截止 2 0 0 8 年底中国网站数达2 8 7 8 万个。2 0 0 8 年内中国网站数较上年增长9 1 4 ，这 是自2 0 0 0 年以来增速最快的一年。其中网址后缀为c n 的网站数较上一年提升十 个百分点，而网址后缀为c o m 的网站数则下降了九个百分点。2 ) 截至2 0 0 8 年底 中国网页数超过1 6 0 亿，较上年底增长9 0 ，与网站的增速基本保持一致。而互 联网调查机构n e t c r a f l 对全球新增网站的调查数据显示，2 0 0 7 年新增4 8 7 0 万个， 2 0 0 8 年新增2 9 9 0 万个，2 0 0 9 年上半年新增4 6 0 0 万个。在连续三年的高速增长 之后全球网站书己达2 3 1 5 亿。 而c n n i c 发布的社会大事件与网络媒体影响力研究报告z 显示，截至2 0 0 9 年6 月底，中国网络媒体用户规模达2 6 6 亿人，较上年同期增长3 2 0 1 万人，增 长率为1 3 7 。研究还显示，2 0 0 8 年汶川地震事件发生后，网民对网络媒体的使 用率超过了电视新闻频道：有8 7 4 的网民选择上网了解相关新闻报道。可见互 联网的开放性、信息的及时性使其成为民众获取危机事件信息的重要渠道，在社 会危机事件的发生、发展和处理过程中发挥着越来越重要的影响。报告中还显示， 2 0 0 8 年通过互联网关注社会事件的用户中有5 2 1 已将互联网作为获取新闻信息 的首选方式。2 0 0 9 年网民每天浏览网页新闻的平均时长为5 5 9 分钟。受调查的 用户中，有7 2 0 用于上网的时间比上年有所增加，有8 6 2 上网看新闻的次数 也有所增加。与此同时供用户选择的新闻网站数量日益增加，网页新闻的浏览渠 道日趋多元化。 新闻网页是海量的网络资讯中高质量信息的重要成分。从海量新闻网页中准 。h t t p ：w w w c n n i c n e t c n i n d e x 0 e 0 0 ii i n d e x h t m 2 h t t p ：r e s e a r c h c n n i c c n h t m l i2 615 5 8 815 di7 0 0 h t m l 浙江大学硕士学位论文第l 章绪论 确高效地自动提取新闻信息非常重要，这对信息提取技术提出了不少挑战。海量 网页导致了海量模板和h t m l 代码多样化的问题。s h u y iz h e n g 等人的调查发现， 即使用户看来页面设计相似的一些网页，其底层的h t m l 代码实际上也可属于多 种模板 i 】。h o n g k u nz h a o 等人调查发现，由于h t m l 规范的松散性，大部分网 页都未能严格符合h t m l 规范i 。著名的浏览器厂商o p e r a 公司抽样调查发现， 3 0 1 1 6 6 8 个领域的3 5 0 9 1 8 0 个网页中仅有4 1 3 符合h t m l 标准，。这对网页信息 提取系统的健壮性提出了很高的要求。基于机器学习的信息提取方法在实际应用 中的一个重要问题是模型学习过程常常依赖大量的人工标注。过多的人工标注费 时费力并且难以保证统一不变的标注质量。因此对训练样本的数量要求控制在合 理范围内的算法才能够投入信息提取领域的实际应用。这对基于机器学习的信息 提取技术提出了一个新的挑战。 1 3 本文工作 本文将回顾信息提取发展的历史，对信息提取研究现状及现有提取方法存在 问题进行总结，然后针对网页新闻结构一致性和视觉一致性两方面特点研究封装 器生成算法，并设计和实现将上述算法有效整合的网页新闻自动提取原型系统， 并通过在大规模的网页集上的实验对该系统进行评估。 本文的主要创新点包括如下方面：基于新闻网页结构一致性的特点，通过少 量人工标注的引导将语义分析功能自然融入到封装器中，提高了传统的基于结构 一致性的网页模板自动推导算法生成出的封装器的准确度。此后基于新闻网页视 觉一致性的特点，并利用机器学习算法的泛化能力，本文实现了模板无关的信息 提取，有效的克服了传统提取方法中常见的模板适应性不足问题。对训练数据的 需求极小，使得本提取方法的实用性大大增强。本方法实现了与网页内容所属语 言无关的信息提取，解决了传统的基于语言模型的提取方法在处理跨语言信息上 的缺陷。将信息提取与语义标注的过程自然的融为一体，解决了传统方法中将二 者的紧密结合人为割裂的缺陷。在提取系统中将基于结构一致性和基于视觉一致 h l t p ：d e v o p e r a c o m a r t i c l e s v i e w m a m a k e y f i n d i n g s 3 浙江大学硕士学位论文第l 章绪论 性的提取技术有效结合实现了比单一的方法更好的效果。 1 4 本文组织 本文第2 章主要讲述网页信息提取的相关研究现状，和树结构匹配、机器学 习等信息提取中重要的相关技术。第3 章重点阐述本文提出的通过用户标注引导 的基于结构一致性的新闻提取算法。第4 章详细介绍了本文提出的另一种基于视 觉一致性和机器学习泛化能力的新闻提取算法。第5 章设计和实现了将上述方法 有效结合的基于结构和视觉一致性的原型提取系统，并通过实验对本系统的提取 效果进行评估和分析。第6 章对本提取系统的创新点和不足进行了总结，并提出 了下一步的研究方向。 1 5 本章小结 本章作为本文的绪论章节讲述了本文的研究背景，阐述了信息提取的概念和 当前研究面临的挑战，并对本文的主要研究目标和内容作了概述。 浙江大学硕十学位论文第2 章相关工作 2 1 信息提取 第2 章相关工作 2 1 1 早期重要研究 信息提取的研究起源于2 0 世纪6 0 年代中期，当时主要是从自然语言文本中 提取结构化信息以帮助电脑理解自然语言。早期的代表性的信息提取研究包括以 下两个自然语言理解研究项目：1 ) 美国纽约大学从6 0 年代到8 0 年代建立一个 大规模英语语法计算系统的研究项目，用于从医疗机构的诊断记录中提取信息的 格式。这也就是当今信息提取研究中常见的模板( t e m p l a t e ) 这一术语的雏形。2 ) 耶鲁大学在7 0 年代进行的有关故事理解的研究项目。由r s c h a n k 及其学生g j o n g 根据故事脚本理论建立了一个信息提取系统。该系统从新闻报道中提取地 震、工人罢工等领域的信息。该系统提出的任务驱动与数据驱动相结合的研究思 路对后来的许多信息提取研究产生了影响。 2 0 世纪8 0 年代末，美国国防高级研究计划委员会( d a r p a ) 资助举办了七 届消息理解会议( 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 ) 。在其推动下信息提取研 究迅速发展成为自然语言理解的一个重要领域。消息理解会议最显著的特点在于 其独特的评测驱动机制。在每次会议前，组织者提前向与会者提供信息提取的任 务说明和待提取的消息文本样例。之后各参会系统处理消息文本测试集合，输出 结果并于人工标注的标准结果比较得出评测分数。最后由评测结果优秀的参与者 做报告交流想法。这种评测驱动的会议模式得到广泛认可，对t r e c 文本检索会 议等后续会议的举办模式产生了重大影响。消息理解系列会议对信息提取这一研 究方向的确立和发展起到了巨大的推动作用。 首届会议对海军军事情报进行了探索性的处理，没有明确定义任务和评测标 准。第二届会议处理的消息文本与首届会议类型相同，但明确地提出了模板和模 板中的插槽的概念，并将信息提取任务指定为模板填充的过程。第三届会议提取 任务是从新闻报道文本中提取恐怖事件相关信息，定义了有1 8 个槽的模板，并 浙江大学硕士学位论文第2 章相关工作 将信息检索领域常用的如召回率和准确率等引入作为信息提取的评测标准。第四 届会议任务模板的复杂度进一步增加到2 4 个槽。第五届会议定义了金融公司合 资情况和微电子技术领域中芯片制造技术进展情况两个提取任务，引入了子模板 的重要概念，并设定了包括11 个子模板、4 7 个槽的复杂模板，并尝试采用平均 填充错误率作为主要评价指标。第六届会议的提取任务是劳动争议的协商信息以 及公司管理人员职务变动信息。本次评测规则进一步细化，并首次提出提取系统 需要自适应不同领域文本的想法，对此后的模板无关信息提取的思想起了很大影 响。最后一届消息理解会议提取任务是飞机失事信息和火箭、导弹发射信息。本 次会议进一步提高了对信息提取适应性的要求，将参会系统移植到不同领域的时 间限制由往届的六个月缩短到一个月。 此后，美国国家标准技术研究所( 腾丁) 为了进步推动信息提取研究发展， 2 0 0 0 年启动了自动内容提取( a u t o m a t i cc o n t e n te x t r a c t i o n ) 评测会议。此会议旨 在研究自动内容提取技术以支持对普通文本、语音识别所得文本和光学字符识别 所得文本的自动处理。其主要提取任务是提取新闻报道文本中出现的实体、关系、 事件等。与消息理解会议相比，其评测采用基于误报( 标准答案中无而系统输出 中有) 和漏报( 标准答案中有而系统输出中无) 为基础的评价体系。 随着互联网的繁荣和海量数据的持续增长，网页信息提取的研究逐渐成为信 息提取的重要前沿方向。其中涌现出了卡耐基梅隆大学的“互联网挖掘( m i n i n g t h ew o r l dw i d ew e b ) ”为代表的一大批研究项目。该项目的目标是通过机器学习 算法自动地从互联网中提取数据来创建结构化的海量数据库。网页信息抽取是从 半结构化的网页中抽取用户感兴趣的结构化数据并理解其中语义信息的过程。在 产业界和学术界中，现有的网页信息提取研究方法主要是基于规则的信息提取和 自动信息提取两大类。以下分别予以介绍。 2 1 2 基于规则的信息提取 基于规则的信息提取技术建立在正则表达式这一成熟技术的基础上，已经成 为了产业界中常用的一种信息抽取技术。在数学家s t e p h e nk l e e n e 于五十年代提 6 浙江大学硕士学位论文第2 章相关工作 出正则表达式后， k e nt h o m p s o n 将其引入计算机行业用于u n i x 系统自带的两 个非常流行的文本处理程序中，随之产生重大影响。正则表达式在u n i x 开发者 中得到普遍支持，而近十年来在大部分w i n d o w s 开发者工具包中也得到普及。 因而正则表达式对于产业界的信息提取人员而言，是一种普及程度和开发效率都 很高的提取技术。利用正则表达式对于规律性比较强的数据能够高效而准确地编 制规则。例如自然语言中时间尽管有多种表示方法，但每一种都有规律可循。英 语中s e m p t e m b e r2 n d2 0 0 9 ，t h es e c o n d o fs e p t e m b e ri n2 0 0 9 ，2 0 0 9 0 9 0 2 ， 0 2 0 9 2 0 0 9 都表达的是同一个日期。只要对有待提取的领域相关知识有全面的了 解后便可花足够的时间针对每一种表达方式编写出对应的封装器。 但基于规则方法的最大缺陷是高度依赖于相关领域专家的知识。很多时候信 息提取的应用场景是领域相关的。一旦转换了领域，由之前领域的专家花费大量 人力编写出来的规则就失去了作用，又需要由新的领域的专家来重新编写规则， 提取软件的重用率很低，极大的影响了开发效率和系统的适用范围。此外还存在 规则的覆盖盲区和互相冲突问题。对于自然语言文本中普遍存在的难以明确界定 的边界情况，可能多条规则都起作用。但这些规则对提取结果的影响权重如何分 配，即使有了领域专家的帮助，也难以调整到最优比例。由于上述缺陷，尽管基 于模式匹配规则的封装器在产业界仍是主流的信息提取技术，但在学术界基于模 板自动推导和机器学习的方法才是研究人员探索的主要方向。 2 1 3 基于结构一致性的信息提取 基于结构一致性的信息提取方法试图从未经人工标注的海量网页数据中自 动推导出网页模板结构等有用的知识。网络时代海量文本很容易取得，计算机 c p u 运算能力以摩尔定律持续迅速增长，存储设备容量持续扩大的同时单位成本 持续下降，这些有利冈素都为此类提取方法提供了必要的运行环境。此类方法在 一些网络信息提取任务中已经达到了较好的效果1 3 丹j 。 n k u s h m e r i c k 等人于l9 9 7 年提出的w i e n 算法在学术界首次提出了封装器 自动推导问题及一种解决方法l i0 1 。这一问题在学术界激发了很大的兴趣。此后研 浙江大学硕士学位论文第2 章相关工作 究人员提出了许多基于自动推导封装器的信息提取算法。 vc r e s c e n z i 等人在2 0 0 1 年发明了r o a d r u n n e r 算法】，并提出了一个重要 的提取思想：在不断比较当前模板与一个新网页异同的过程中，如果不能够匹配 新网页，就对当前模板进行调整完善。这样确保了r o a d r u n n e r 产生出的模板总 是能匹配之前见过的所有网页。 a a r a s u 等人在2 0 0 3 年提出了e x a l g 算法1 1 2 】。其引入了等价类的概念： 在系统内的每一个网页中出现频率均相同的符号集合，就称为一个等价类。等价 类分为网页中的普通文本以及h t m l 标签文本两类。该算法首先识别出所有等价 类，然后排除部分无效等价类，最后从等价类生成提取模板。 b l i u 等人在2 0 0 3 年提出了从单个列表网页中( 如商品搜索结果) 提取数据 记录集的s t m 算法f 1 3 】。这个算法基于h t m l 树的相似性匹配进行重复模式识别， 从而解析出网页中包含的各个数据块，并把各块中的数据记录提取出来。 r e i s 等人在2 0 0 4 年提出了用于从新闻网页中提取新闻内容的算法【m 】。该算 法首先在输入的新闻网页集合上聚类，希望将同一模板生成的所有网页聚为一 类，而把不属于同一模板的网页区分开。然后在每一类中归纳得出该类网页的模 板并生成与此模板相应的封装器。对于一个待提取的网页，通过计算该网页与现 有封装器的h t m l 结构相似性，找出该网页与封装器之间的不同部分。提取出来 的这些数据是没有语义信息的，还需使用一些启发式方法识别其中的语义信息。 生成的封装器存在一定的误差，因为尽管聚成一类的网页相似度较高，但并不一 定是真正属于同一模板。 b l i u 等人在2 0 0 5 年提出了d e p t a 算法，用于从单个网页中自动提取结构 相似的多条数据记录1 15 1 。该方法主要基于d o m 树结构匹配，在包含数据记录的 多颗d o m 子树之间进行匹配并提取数据。该算法首先将数据区域与无关数抛区 分开，然后从数据区域中识别数据记录，并通过以下步骤将多个数据记录中相应 项( l t 盘t i 商品标题) 进行匹配：1 ) 一条记录的不同项( 如商品标题、价格) 可 能分布在几颗不同的d o m 子树当中，因此为每一条记录生成一颗单独的d o m 子树。2 ) 使用s t m 算法对这些子树进行p e 配。 浙汀大学硕十学位论文第2 章相关工作 s z h e n g 等人在2 0 0 7 年提出了一种新的基于d o m 树结构匹配的信息提取算 法【1 1 。该算法创新性的将传统方法中通常分开的封装器生成和模板检测两个步骤 合二为一，提高了所生成的封装器的准确度。 2 1 4 基于机器学习的信息提取 基于机器学习的方法往往要求足够数量的由人工标注的样本库来作为学习 对象。设计特征之后，从这些样本中提取出特征值，调整训练过程的参数，并训 练出统计模型。机器学习的主要优点建立在数据的统计规律之上，具有坚实的理 论支持。另一个优点是机器学习算法往往具有较强的泛化能力，为解决信息自动 提取中的模板依赖性问题提供了可行的解决之道。 h z h a o 等人研究了从搜索结果页面提取多条数据记录的问题【2 1 。通过训练 神经网络分类器，他们对网页中的装饰性标签以及文本中的模板性内容进行识别 并去除。实验证明训练得到的分类器能用于提取多个不同网站的搜索结果页面。 j z h u 等人研究了从商品列表页面和商品详细信息页面中提取商品名称、价 格等信息的提取算法【1 6 】。该算法将条件随机场( c r f ) 模型f 1 7 1 扩展为层次条件 随机场模型( h c r f ) ，并使用v i p s ( v i s i o n b a s e dp a g es e g m e n t a t i o n ) 算法【| 8 l 将 网页解析成树状结构，然后预测树节点的类别( 如商品名称、价格、描述等) 。 d c h a k r a b a r t i 等人研究了网页模板的识别问题l j9 1 。他们将网页解析为d o m 树，然后对每一个d o m 树节点预测其属于模板的概率，然后考虑父节点、子节 点的概率信息来对每一个节点的概率进行平滑处理( i s o t o n i cs m o o t h i n g ) 。 j z h u 等人提出了一种从研究人员个人主页中提取个人信息( 如姓名、地址、 e m a i l 等) 以及学术信息( 所发表论文的题目，时间等) 的提取技术1 2 0 1 。该方法 使用丫h c r f 模型对网页的结构和网页内容两方面进行建模，并从用户标注过的 网页当中训练模型。但相比实际应用的需求，条件随机场模型的训练和预测时间 复杂度偏高。 s z h e n g 等人提出了一种从新闻m 页中提取重要d o m 树叶节点的算法【2 。 该算法通过提取网页的视觉特征进行机器学习，在消除封装器的模板依赖性上做 浙江大学硕士学位论文第2 章相关工作 了有益的探索。新闻标题和正文被分割为视觉块进行提取。但此方法的缺陷在于 分割的粒度过细，导致可能只提取出新闻的一部分而其余部分在提取过程中丢失 了。此方法中使用了同样的视觉特征来同时表示标题和正文，而没有对新闻标题 给予足够的重视。另外，此方法采用的评价标准以视觉块为单位。新闻正文通常 由多个视觉块组成，但其中任何一块都被给予与标题块相同的重要性。即使提取 结果获得较高评价，也可能只是提取出了一部分视觉块而漏掉了如标题等重要的 部分。 2 2 树结构最佳匹配算法 2 2 1 树结构相似性衡量 衡量字符串相似性的一种普遍实际应用的标准是字符串编辑距离。字符串编 辑距离定义为给定两个字符串s ，和阳，将s j 上修改至与髓完全相同的最小代 价。修改操作包括以下三种：1 ) 增加一个字符，2 ) 删除一个字符，3 ) 替换一个字 符。每一次操作都需要付出代价，但这三种操作可以具有不同的代价。不过在纯 文本处理中，将这三种修改的权重都设置为相同值通常可以取得较好的结果。 字符串编辑距离只基于纯文本的比较，而没有考虑网页具有树结构这一重要 特性。如果采用字符串编辑距离衡量两个h t m l 网页的相似性，差异较大的多种 情况很可能会算出相同的编辑距离，因而不能准确反映网页结构的异同。为了解 决这一问题，引入树结构编辑距离来衡量树形结构的相似性。树结构编辑距离是 对节点顺序固定的标记树来说的。其中1 ) 对于任一个节点尸，他的所有孩子节 点的顺序是固定的，不能交换；2 ) 树的所有节点都是带有标记的，比较两个节 点是否相同即比较两个节点的标记是甭相同。 计算树结构编辑距离等吲于在两棵树之间找出一个最佳匹配的过程。树丌 和眩之间的匹配m 是有序数对f f ，夕构成的集合，其中任意两个数对r i 卜，j ， ( i 2 ，j 2 j 都具有以下性质：1 ) i t = i 2 , f h j l = j 2 互为充要条件；2 ) 丌是丌黝 的左邻节点与陀是t 2 i d 的左邻节点互为充要条件：3 ) 丌l 】是t 1 位】的父节 点与乃i 是刀历】的父节点互为充要条件。按定义7 1 中的一。个节点只能与乃 i o 浙江大学硕士学位论文 第2 章相关工作 中最多1 个节点匹配，而且匹配过程中节点的父子关系不变。如图2 - l 所示，刀 中彳j 是d 1 的父节点，而匹配之后在刀中相应地a 2 仍然是d 2 的父节点。最佳 匹配的含义随实际需要而变化，接下来的两个小节中将介绍两种不同的计算树结 构最佳匹配的算法。 图2 1 树结构匹配 2 2 2 自顶向下保序匹配算法r t 蹦 无约束的最小代价树匹配问题己被i i e n 是n p c o m p l e t e 问题【2 2 】，即使加入匹 配过程中保持父子关系这一限制后，匹配时间复杂度也高达o ( n 1 n 2 h l h 2 ) ，其 中门f 是树力的节点个数，办，是树7 了的高度。如果进一步考虑到网页信息提取背 景下的d o m 树结构匹配的特点，匹配算法的时间复杂度可以大大降低。 由模板生成网页是一个自顶向下填充数据的过程，因而由同一模板生成的任 意两颗d o m 树丌和尼之间具有如下特点：”和刀靠近树根部分的上层节点 的结构一定是相同的，而只有到了某一个分界线之后的下层节点中才出现差异。 利用这一特点可以自顶向下的顺序来逐层建立节点匹配关系。这样丌中处于第l 层的所有节点只能与死中同处于层的所有节点之间进行匹配，如图2 1 里两个 b 节点是不能旺配的。相对于允许跨层匹配的树结构映射算法，这一同层匹配的 限制大大的缩小了匹配的候选范围，也随之大大降低匹配算法的时间复杂度。用 m 表示7 了中处于第层上的任意一个节点，而t n i 表示以，为根节点的子树。 则只有当，和n 2 匹配，才能继续递归的去计算刀、，和t n 2 的匹配关系；否则 ，和n 2 的子节点问不能进行1 7 e 配，也就无需进一。步的计算，如图2 2 中，1 ) 两 浙江大学硕士学位论文第2 章相关工作 颗树中都有的e 和，节点并不能进行匹配，因为它们的父节点d 和g 已经不匹 配；2 ) 两颗树中都有b 节点，但处于不同的层次上因而不能匹配。以上便是自 顶向下保序匹配的含义。 图2 - 2 自顶向下保序匹配示意 r e i s 等人将具有最小修改代价的自顶向下保序匹配定义为丌与力的最佳匹 配，并提出了相应的动态规划算法r t d m 1 4 l 。其主要步骤如图2 3 所示。其中输 入参数n 1 ，n 2 分别表示需要计算编辑距离的两棵树丌和您的根节点，而0 表 示算法允许的最大编辑距离。若在计算过程中某一时刻编辑距离已超过0 ，由于 后续计算过程得出的编辑距离非负，因此最终计算出的编辑距离必将超过0 。故 可以立即终止计算，减少了不必要的运算时间。对于任意节点，函数d r n ) 表示 的所有后代节点集合，而c ( n j 函数表示j v 的儿子节点集合。函数d e t f u ) 、i n s ( n ) 分别表示删除和插入节点付出的代价，而r e p ( n 1 ，2 ) 则表示将节点m 替换为 n 2 的代价。 下面详细介绍r t d m 算法流程。第l 到2 行处理了j 和m 不同的情况。 根据自顶向下保序匹配的定义，最小代价匹配过程需要将整颗 子树用整颗n 2 子树替代。从第3 行开始处理n i 和n 2 相同的情况。第3 到4 行处理，是叶节 点的情况，这时最小匹配需要将n 2 的后代节点全部插入n t 下。类似地第5 到6 行处理m 非叶节点而n 2 是叶节点的情况，这时最小匹配需要将n 1 的后代节点 全部删除。如果j 和n 2 都不是叶节点，第7 到l6 行计算了c 倒，) 对应的子树 集合和c ( n 2 ) 对应的- 了树集合之问匹配的最小代价。用m i ，表示c 倒纠l 】， 浙江大学硕士学位论文第2 章相关工作 c ( n ) 朋与c o v 2 ) 1 与c o y 2 ) 时之间的编辑距离。第l o 行中假设已经求得m i - 1 刃， 那么进一步删除c o w ) f i 整颗子树可以使完成 前i 颗子树与尼前j 颗子树的匹 配，付出的代价是d e l ( c ( n 1 ) i ) + z k e d ( c ( n i ) i ) d d ( k ) 。类似，第1 1 行中假 设己经求得m i , j - 盯，那么进一步往”中插入c o y 2 ) 阱整颗子树便可完成丌前i 颗子树与 乃 前，颗子树的匹配，付出的代价是 泐f ，c f ，2 j 厂，刀+ k e d ( c ( n 2 ) j ) i n s ( k ) 。在t i 的前i - 1 颗子树和7 2 的前户，颗 子树已经匹配后，第1 2 到1 5 行中处理了刀的第i 颗子树与尼的第，颗子树的 最小匹配：1 ) 如果”的前厶j 颗子树和乃的前，- ，颗子树匹配代价在合理范围 内，则继续递归调用r t d m 算法计算；2 ) 否则不必再做计算。 r ii ) 、i ( 、1 、2 0 ) _ f 打1 ；1 ； 2t h e nr e t u r n ，d ( n l ) + ，d i v 2 i n f j ) + ，1 e t 心1 屯) 3 、f v 1i snh nf 4t h e nr e t m 1 1 f d m ) i l l 一： 5 i f | r ，( “厂 f ；t h e n r e t u l 1 1 i ”f i ) f f ) 7 l e t ， i 一( 一( 、一 s f o l j 一1t o 1 9(10f o rj lt o 2 l )( 1 ul e t ( f ，n ，d 一1j r j 一上司斗f “1 i ! ) 一，) ( ( 、1 ) ) d f ( i ) l l l e t ( 。r h t i 一1 ，! i j 一1 一j m 、f 、2 ：明j + 。d f “k j ? j jj ，。 ，j 1 2 i f 1 巧一i - j 1 = 一 1 3t h e nl e t ( 一小，一i 一id 3 1 ( + f 、+ 1 ) i c ”p l v e l s t ， 图2 - 3r t d m 算法丰要步骤 由于引入了自顶向下保序匹配的限制，r t d m 算法将计算丌和乃的最佳匹 配的最坏时间复杂度降低至0 ( n 1 n 2 ) ，其中门f 是树7 了的节点个数。由于算法中 还设定了阈值0 ，因而还能进一步减少不必要的计算，进而提高了实际运行速度。 一j r 从 一尉f “ (，0 川 k 一 ，- kl ， 卜 ”nck 浙江大学硕士学位论文 第2 章相关工作 2 2 3 自顶向下保序简单匹配算法s t m r t d m 算法中引入了自顶向下保序匹配这一重要的思想，大大降低了树结构 匹配算法的时闻复杂度并大大增强了实用性。b l i u 等人基于这一思想，针对信 息提取中模板的特点进一步提出了自顶向下保序简单匹配的动态规划算法s t m ( s i m p l et r e em a t c h i n g ) 用于计算d o m 树相似性【1 3 】。与r t d m 算法相同，s t m 算法只允许在同层节点之间进行匹配。但与r t d m 算法的区别在于，s t m 算法 在匹配过程中不会修改树结构( 包括插入、删除和替换) ，如图2 4 所示。这进一 步降低了树结构匹配算法的时间复杂度。s t m 算法比r t d m 算法更深入的体现 了信息提取中模板生成的d o m