（计算机软件与理论专业论文）面向web数据集成的数据抽取问题研究.pdf

r e s e a r c ho nw e bd a t ae x t r a c t i o n f o rw e bd a t ai n t e g r a t i o n b y d i n gy a n h u i s u p e r v i s o r ：l iq i n g z h o n g f o rt h ed e g r e eo f d o c t o ro fp h i l o s o p h y s h a n d o n gu n i v e r s i t y , j i n a ns h a n d o n g ，p r c h i n a a p r i l ，2 0 1 0 l 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：勺擞 日期： djd 上工i 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名“ l 山东大学博士学位论文 事实，状态的转换代表从一种分隔符转换到另一种分隔符的规则，包装器通 过识别事实周围的分隔符来抽取事实，即信息主体。s o f t m e a l y 能处理信息缺 失和次序变化的情况，但是为了能处理不同次序的事实，系统需要学习各种 可能的变化次序，这就增加了系统的复杂度。 n o d o s e 1 7 】提供一个交互工具供用户逐级分解半结构文本，n o d o s e 能 够处理嵌套对象。系统试图利用两个基于启发式知识挖掘模块来推断输入文 档的格式及语法。一个模块挖掘文本文件，另一个解析h t m l 代码。类似于 w i e n ，挖掘算法试图找出共同的前缀和后缀作为各种属性的定界符。尽管 它没有假设一个记录中的各字段的顺序是固定的，但是它仍然试图找到一个 记录中各字段固定的顺序。 类似于n o d o s e ，d e b y e 1 8 】也提供了一个交互的g u i ，不同的是在 d e b y e 中，用户只需要标记出原子属性值，而在n o d o s e 中，用户需要将整 个文档分解成自项向下的形式。另外，d e b y e 采用自底向上的抽取策略。这 种策略的主要特点是首先抽取原子部分，然后将它们组成一个嵌套的对象。 原子部分的抽取规则采用属性值对模式，通过上下文分析的方式确定。 i e p a d 1 9 】是第一个从未标注的网页中产生抽取规则的w e b 数据抽取方 法。这个方法利用以下事实：如果一个网页中包含多条待抽取的w 曲记录， 那么这些记录通常利用相同的模板进行展示，以便具有良好的视觉效果。因 此，当网页被编码后，重复的模式将会被发现。i e p a d 通过发现重复的模式 来学习产生包装器。i e p a d 首先把页面解析成h t m l 标签串，然后提出一种 使用p a t 树字符串匹配的方法识别数据记录并抽取数据项。但是，当数据记 录结构比较复杂，尤其是嵌套结构时，i e p a d 抽取效果不好；并且，用户需 要在所有产生的模式中选择出最好的一个：另外，i e p a d 无法处理详细页面。 o l e r a 2 0 1 是一个半监督的w e b 数据抽取系统，它从用户处获得一个粗 糙的例子来产生抽取规则。o l e r a 可以对仅包含一条数据记录的网页产生 抽取规则，而i e p a d 无法做到这一点。o l e r a 由三个主要操作组成：1 ) 用 户在页面中标注出一块包含待抽取数据记录的信息块，o l e r a 利用近似匹 配技术发现其它的相似的信息块，并将其归纳成一个提取模式；2 ) 下钻或上 卷操作g 下钻操作允许用户从一个文本片段到更详细的组成部分，而上卷操 作是将多个信息槽组合成一个有意义的信息单元；3 ) 标明相关的信息槽用于 1 4 上j 山东大学博士学位论文 模式确认。 l i x t o 2 1 , 2 2 系统首先也要求用户手工标记训练数据，然后根据标记信息， 生成相关的抽取规则，根据生成的规则进行数据抽取。该系统实现了可视化、 交互式的界面，极大地方便了用户的操作。但是，l i x t o 使用d a t a l o g 2 3 1 的 e l o g 语言来定义抽取规则，实现和优化很困难，也不容易理解。 t h r e s h e r t 2 4 1 是一个和o l e r a 相似的半监督方法。t h r e s h e r 利用一个建立 在h a y s t r a c k 浏览器上的g u i ，允许用户标记和描述待抽取信息，以产生训 练实例；然后，t h r e s h e r 通过计算这些训练实例对应的d o m 子树间的编辑 距离来产生包装器。 总的来说，半自动的w e b 数据抽取方法在用户的协助下，具有较高的抽 取准确度。面对w e b 数据集成系统中大规模w e b 数据的抽取需要，需要尽 量减少用户的参与程度，提高w 曲数据抽取方法的适应能力。 2 2 3 全自动的w e b 数据抽取方法 全自动的w e b 数据抽取方法不利用任何人工标注的训练样本，并且不需 要用户的参与来产生抽取规则。全自动的w 曲数据抽取方法包括r o a d r u n n e r 2 5 1 ，d e l a 2 6 , 2 7 1 ，v i n t s t 2 8 1 ，m d r 2 9 1 ，d e p t a t 3 0 1 ，o m i n i t 3 1 1 ，e m b l e y 3 2 1 ，e x a l g l 33 1 ，v i p e r t 3 4 1 ，v s d r 3 5 1 以及国内学者胡东东3 6 1 、杨少华【3 7 1 、刘伟 【3 8 】等提出的方法等。 r o a d r u n n e r 2 5 1 系统总结两个或多个样本页面结构所呈现出来的规律，从 中抽取出能够用一个正则表达式表示的该类页面的模板，再使用该模板进行 同类页面的数据抽取。该系统根据页面结构中h t m l 标记间的关系，以嵌套 的方式表示抽取出的数据。该系统实现了无需用户参与的全自动数据抽取， 极大地方便了用户的使用。但是该系统抽取的数据不一定都是用户需要的， 有可能包含噪音数据；另外，样本的选择直接影响模板的生成质量，对抽取 的结果也会产生深远的影响。 作为i e p a d 的扩展，d e l a t 2 6 , 2 7 除去了在抽取规则产生过程中用户的参 与过程，并且d e l a 可以处理嵌套的对象抽取。d e l a 中的包装器产生过程包 括两个步骤：第一，通过比较两个网页的d o m 树结构，获取页面中的数据丰 1 5 山东大学博士学位论文 富区域，同时过滤掉具有完全相同结构的子树节点；第二，利用后缀树发现 连续重复的模式。通过保持每个模式的最后一次出现位置，新的重复模式从 新的序列中被重复的发现，组成嵌套结构。 v i n t s t 2 8 】利用了搜索引擎结果页面的视觉特征来扑捉内容规律性，并结 合h t m l 标签结构进行抽取。为了生成包装器，需要几个正常的结果页面和 一个无记录的结果页面。v i n t s 要求正常的结果页面至少包含四个数据记录。 m d r t 2 9 1 和d e p t a 3 0 1 这两种抽取方法都是由美国i l l i n o i s 大学同一研究小 组提出，其独特的地方在于能够十分准确地在d o mt r e e 中完成对多记录页 面的抽取。它们的实现关键在于利用页面的嵌套结构和表现特征把查询结果 从整个页面中分离出来，并对结果中的多个记录进行精确的划分，其意义是 把每个记录作为现实世界的实体对待，首先从这个角度完成第一步抽取，第 二步把每一条记录从属性的角度进行分解。m d r 把标签树中节点的路径看作 一个字符串，并使用了比较字符串编辑距离的思想从数据区域中发现代表数 据记录的结点，而d e p t a 则是以树的结构信息代替标签字符串，从而达到 对数据记录更准确的识别。然而在文献 2 8 】中的实验显示它们在第三方的数 据集上的效果并不理想，另外它们也没有生成包装器。如果没有包装器，即 使是相同模板的页面也要重复执行复杂的抽取过程。 o m i n i t 3 1 1 和e m b l e y 3 2 】中提出的方法首先把输入页面解析成d o m 树，然 后通过对该d o m 树应用一组启发式规则来识别数据记录的边界。o m i n i 与 e m b l e y 的区别是它使用了更少的启发式规则，而且无需建立本体。但它们都 没有实现从数据记录中对数据项的抽取。 a r a s u 和m o l i n a t 3 3 1 提出一个有效的公式化方法用于从w e b 页面中进行 数据提取。e x a l g t 3 3 1 的输入是一组由未知模板t 产生的网页集合以及待抽 取的值。e x a l g 利用d i f f e r e n t i a l t i n gr o l e s 和e q u i v a l e n c ec l a s s e s ( e c ) 两种 技术检测并推导出模板t ，并利用模板t 从编码后的网页中抽取出这组值作 为输出。 v i p e r t 3 4 】把页面视觉信息结合到多序列排列技术中来实现数据记录的抽 取。v i p e r 通过识别链接重复和利用上下文视觉信息能够准确地抽取出单个 网页中具有重复模式的数据。而v s d r 3 5 】利用v i p s 分块技术3 9 1 将w e b 页面 分割成多个区域，然后利用基于视觉的启发式规则识别并抽取目标区域中的 1 6 l 1 一 山东大学博士学位论文 数据。 胡东东等【3 6 1 在h t m l 页面的树型结构之上，提出了基于语义块的h t m l 页面结构模型：h t m l 页面中的数据值主要存在于语义块中，不同的h t m l 页面的主要区别在于语义块的区别，提出了基于语义块结构模型的数据抽取 方法。 杨少华等3 7 1 给出了模板检测问题的形式化描述，并深入分析模板产生网 页的结构特征，提出了一种新颖的模板检测方法，并利用检测出的模板自动 地从实例网页中抽取数据。与其它已有的方法相比，该方法能够适用于列表 页面和详细页面两种类型的网页。 刘伟等【3 8 1 针对从d e e pw e b 页面中抽取结构化数据记录的问题，提出了 完全基于页面中的视觉信息来实现自动的抽取过程。刘伟等首先提出了d e e p w e b 页面中若干有效视觉特征；然后基于这些特征，把d e e pw e b 页面转化 为一棵视觉树，并在这棵树上实现了对数据记录和数据项的抽取。 总的来说，全自动的w 曲数据抽取方法无需用户的任何参与，自动化程 度最高。但是，对于一些结构复杂的页面，抽取准确度不高，总体抽取精度 不如半自动的w e b 数据抽取方法。 2 3 数据模型的相关研究 面向w e b 数据集成的数据抽取需要借助数据模型的指导，来完成对目标 网站和目标网页的选择，以及对目标数据的定位。本文中定义的w e b 实体模 型( 定义3 3 ) 是一个具体的数据模型，它定义了w e b 数据集成系统中涉及 的w 曲实体以及不同w e b 实体之间的联系。它为w 曲数据集成系统中的多 个环节提供指导，例如，指导数据源的选择，指导、e b 数据的抽取，指导数 据的存储等等。 在垂直搜索的研究中，例如，德国特里尔大学的d b l p 项目 4 0 1 ，美国威 斯康辛大学的d b l i f e 项目4 1 1 以及微软的l i b r a 和p r o d c u c ts e a r c h 4 2 】等等，都 是通过预先定义好的数据模型( 包括w e b 实体的模式信息和w 曲实体间的 联系) 来收集和组织数据。而在d e e pw e b 数据集成的研究中，例如，斯坦 福大学的h i w e 项引4 3 1 ，伊利诺伊大学的m e t a q u e r y 项目1 4 4 ，美国纽约州立 大学宾汉姆顿分校的w i s e i n t e g r a t o r 系统【4 5 1 ，华盛顿大学的s h o p b o t 项目 4 6 1 ， 1 7 山东大学博士学位论文 哥伦比亚大学的q p r o b e r 项目1 4 7 ，以及国内人民大学信息学院的“工作通” ( j o b t o n g ) 原型系统【4 8 】等等，只涉及对接口模式和结果模式进行处理，缺乏对 w 曲实体间联系的发现和管理。 与w e b 实体模型比较相近的是领域本体的研究。本体作为表达知识的 共享概念模型，已日渐成为知识工程、知识管理、信息检索和语义网等多个 母 领域的重要组成部分。当前，已建立了一系列构建本体的工程方法，涌现了 众多理论、技术、方法、表示语言和工具。本体在众多领域中的应用都是在 构建本体的基础之上实现的，但本体的构建却是一项繁琐而辛苦的任务。手 工方式构建的本体需要耗费大量的人力和时间，w o r d n e t 4 9 l 等系统需要使用 人工为本体输入大量的知识，然后系统才能使用其庞大的知识库进行推理或 是获取新的知识。这就容易导致知识获取瓶颈，无法保持本体的更新【50 1 。本 体学习技术是利用知识获取技术来降低本体构建的开销，其目标是利用机器 学习和统计等技术自动或半自动地从已有数据源中获取期望的本体。由于实 现完全自动的知识获取技术还不现实，所以，整个本体学习过程是在用户指 导下进行的一个半自动的过程1 5 1 1 。 杜小勇等【5 1 】认为不同类型的数据源需要采用不同的本体学习技术，因此 根据数据源的结构化程度，将本体学习技术分为3 大类：基于非结构化数据的 本体学习、基于半结构化数据的本体学习和基于结构化数据的本体学习。 ( 1 ) 基于非结构化数据的本体学习 非结构化数据是指没有固定结构的数据，例如纯文本、w o r d 文档和p d f 文档等。从非结构化数据中获取本体一般都是将非结构化数据源统一转换成 文本，然后采用基于文本的本体学习方法来获取本体。 目前，基于文本的本体学习方法是本体学习的主要方法和基本方法，也 是本体学习的研究重点。它的基本思路是利用自然语言处理( n a t u r a l l a n g u a g ep r o c e s s ，n l p ) 技术对文本预处理，然后利用模式抽取、语言规则、 统计和机器学习等手段从中获取本体知识，重点是从文本抽取领域概念、实 户 例，并发现概念之间的关系。需要指出的是，在目前大多数的本体学习方法 和本体学习系统中，都将w 曲数据作为非结构化数据，从w 曲页面中抽取 出纯文本后再作进一步处理的 5 2 , 5 3 。 ( 2 ) 基于半结构化数据的本体学习 1 8 山东大学博士学位论文 半结构化数据是指具有隐含结构，但缺乏固定或严格结构的数据【”】，常 见的半结构化数据包括大量的x m l 格式和h t m l 格式的网页，以及它们遵 循的文档类型定义( x m l s c h e m a 或d t d ) ，还有越来越多的用r d f 标注的网 页，另外词典也可以认为是一种特殊的半结构化数据。 对于x m l 、h t m l 和r d f 这类半结构化数据，d e i t e l 等【5 5 1 提出了一种 从r d f 标注中进行本体学 - 3 的方法。p a p a t h e o d o r o u 等【5 6 1 运用数据挖掘方法 从以x m l 或r d f 描述的领域数据仓库中构建领域本体的分类关系。m o d i c a 等【5 7 1 开发的o n t o b u i l d e r 工具能够利用用户浏览行为从x m l 和h t m l 标记 的半结构化数据源中生成本体的功能。 x m ls e h e m a 或d t d 文件，定义x m l 的元素及元素之间的层次性结构 关系，可采用一些映射规则将这些元素及其关系映像到本体中。其研究重点 是映射规则的发现，现有的方法可以分为两类：一类是基于学习的方法，即利 用一些自学习的手段自动获取，例如k a v a l e c 等人【5 8 】重点研究了利用机器学 习方法自动地得到映射规则：另外一类是基于预定义规则，即用户预先给出了 一些规则，例如，d o a n 等人【”1 和m e l l o 等人删使用预定义的规则，从d t d 中提取语义信息生成相应的概念模式，然后对这些概念模式进行语义集成得 到本体。v o l z 等【6 1 1 开发了o n t o l i f t 系统能够捕获x m l 模式语义，并将之转 换为本体的概念和角色所对应的标记，该工具己加入到k a o n 工作平台。 基于词典的本体学习，主要指从机器可读的词典中抽取本体的概念及概 念间关系。词典作为一种通过手工方式认真组织的可靠的知识资源，是一种 非常好的本体学习数据源。从词典中获取本体通常使用基于语言学的方法和 基于模板的方法。 3 ) 基于结构化数据的本体学习 结构化数据主要包括关系数据库或面向对象数据库中的数据。关系数据 库采用的是关系模型，在关系模型中，关系是元组的集合，而关系模式是用 来描述关系的结构的，即它由哪些属性构成、这些属性来自哪些域以及属性 和域之间的映像关系。 基于结构化数据的本体学习的主要任务就是分析关系模型中蕴涵的语 义信息，将其映像到本体中的相应部分。例如，s t o j a n o v i c 等【6 2 】通过考察数 据库中的表、属性、主外键和包含依赖关系，给出了一组从关系模型到本体 1 9 山东大学博士学位论文 的映像规则，在根据这些规则的基础上能够直接获取候选本体。由于关系模 式中蕴涵的语义十分有限，所以只适合构建轻量级的本体。k a s h y a p 等【6 3 】提 出首先根据关系模式得到一个初步的本体，然后基于用户查询进一步丰富该 本体中的概念和关系。由于用户查询具有很大的随机性，所以很难保证结果 的质量。a s t r o v a 6 4 】通过对数据库中的元组的分析，得到了概念间的继承关系。 6 综上所述，现有的大部分本体学习方法，都是将w 曲页面预处理成纯文 本后，再做进一步的处理【5 2 ，5 3 】，无法有效地丰富w e b 实体模型和发现w e b 实体间的潜在联系。另外，当前本体学习系统工具多是原型系统，不能大规 模实时处理、b 上海量的信息源，也缺乏对中文语料的高效处理能力【5 0 】。而 w 曲数据集成中的w 曲实体模型不仅要求能够有效地处理中文，而且需要 针对w e b 上的海量数据和模式动态变化的特点，能够自动地、逐步地进行扩 充和丰富。 2 4 面临的问题 由于互联网上数据具有海量、异构、动态变化、联系丰富等特点，导致 、b 数据抽取研究中仍然存在以下问题有待解决。 ( 1 ) 在w e b 数据集成过程中，需要将新发现的w 曲实体和属性标签丰 富至w 曲实体模式( 定义3 4 ) 中，为进一步识别、抽取和集成来自不同数 据源的w e b 数据提供指导。如何针对w e b 上广泛存在的半结构化数据的模 式动态变化的特点，有效地构建w e b 实体模式信息，是一个有待解决的问题。 本文将在第三章对这个问题进行重点讨论。 ( 2 ) 在w e b 数据抽取过程中，需要准确地从目标页面中抽取出目标数 据，并对抽取到的数据元素进行语义上的理解，为进一步整合数据奠定基础。 如何准确地抽取目标数据，并进行语义理解是另一个有待解决的问题。本文 将在第四章和第五章对这个问题进行重点讨论。 ( 3 ) 在、b 数据抽取过程中，需要建立新发现w 曲实体与w 曲实体 模型中已有w e b 实体间的联系，丰富w e b 实体模型，为进一步整合w e b 数 据奠定基础。如何有效地建立新发现w e b 实体与w e b 实体模型中已有w e b 实体间的联系，也是一个有待解决的问题。本文将在第六章对这个问题进行 重点讨论。 & l 如 山东大学博士学位论文 2 5 小结 本章论述了现有w e b 数据抽取方法和数据模型构建方面 对w e b 数据抽取面临的问题进行了总结，这些问题有待于深 2 l k -il 山东大学博士学位论文 3 1 引言 第3 章w e b 实体模式的动态构建方法 随着w w w 的快速发展，w e b 网页中已经存放了涵盖各个领域的大量有 价值的信息。w e b 页面上的数据主要以半结构化形式存在，w e b 数据对象是 由多个数据元素及可选的属性标签按照特定模式组织在一起的半结构化数据 对象f 1 0 2 1 。在不同的网站中，描述相同类型w e b 数据对象所使用的属性标签 不尽相同，如图3 1 所示，两个网站中用于描述职位信息的属性标签不完全 一样。 w e b 数据集成系统需要将来自不同数据源的w e b 数据对象有效地集成起 来。用于描述同类型w 曲数据对象所使用的属性标签集合被称为w 曲实体 模式( 见定义3 4 ) 。w 曲实体的模式信息对于识别、抽取和集成来自不同数 据源的w 曲数据对象具有重要的指导作用。 由于w e b 上广泛存在的半结构化数据模式的异构性和动态变化，导致 w 曲数据对象具有以下特点： ( 1 ) 描述w e b 数据对象所使用的属性标签丰富多样，不可能由用户事 先完全地、准确地定义出来； ( 2 ) w 曲实体模式信息的构建不是一个一蹴而就的过程，而是一个逐 步丰富、逐 现有的 次性地生成 象中新属性 上广泛存在 w 曲实体模 的属性标签 实体，利用 果表明，该 体模式与目 玉 j 矗 山东大学博士学位论文 本章的组织结构如下，第2 节介绍本章中涉及的相关概念；第3 节具体 介绍动态扩充w e b 实体模式的方法；第4 节给出综合实验结果及分析；第5 节介绍w e b 实体模式扩充的相关工作；最后是小结。 一- 黝e 廖：o ：，：= 4 ：“_ ：。：。：= ： l a ik “一蕾竹 ，t * ”。“ # ”_ - 一，”h d h 一 ，p 惭 _ _ - 一， - _ 一州瞄譬曩 ”j 。 ， ”，e 哗。ti ，4 “ j l 删，啼； o - h ” m m * 十 ，_ 2 7 ，；：“，j ，f ，? ? 一i ? 。t ? i h h m o 匝薯础l 嘲域瑚蝴州- 蜘 ，嘲坤 圈m _ m g 图3 1 描述招聘职位w e b 实体的两个w e b 数据对象 3 2 问题定义 定义3 1 一个w e b 实体代表w e b 上的一类事物，它的实例信息以w e b 数据对象的形式出现在w 曲网页中。一个w 曲实体由一组属性组成，每一 个属性拥有一个属性名称。正式地，一个w e b 实体可以被形式化表示为， e = a t t r i b u t e l ，a t t r i b u t e 一，a t t r i b u t e 。 ，a t t r i b u t e f 是该w e b 实体第f 个属性的 属性名称。例如，招聘职位是一个w 曲实体， 聘单位= 职位名称，职位类别，工作地点，工作性质 。 定义3 2 一个w e b 实体的实例，称为w e b 数据对象。例如，网页中发 布的一条j a v a 程序员招聘信息是一个w e b 数据对象。正式地，一个w e b 数 据对象可被形式化表示为e = o 。，m ) ， ，1 ，；) ，( f 。，v 。) ，和是w 曲数据 对象e 的第i 个属性的名称和值。例如，上述的w 曲数据对象可以表示为 e = ( 职位名称，剧瑚开发工程师) ，( 职位类别，研发) ，( 工作地点，北京) ， 定义3 3 一个w e b 实体模型是一个具体的数据模型，它描述了一组w e b 实体，记为w e b e n t i t i e s ，以及w e b 实体间的联系，记为r e l a t i o n s h i p s 。一个 w e b 实体模型可以被形式化为m o d e l = w e b e n t i t i e s ，r e l a t i o n s h i p s ) ， w e b e n t i t i e s = w e s ，w e i ，呱) ， r e l a t i o n s h i p s = ，其中i j ， 1 i n ，l 歹n ， 暇w e b e n t i t i e s ，舾，w e b e n t i t i e s 。呢和w e f 代表两个不同的w e b 实体， 山东大学博士学位论文 r e l a t i o n s h i p 订代表两个w e b 实体间的联系。 定义3 4 在w e b 实体模型中，每一个w e b 实体都拥有一个模式，记为 s c h e m a 。w e b 实体的模式描述了对应w e b 实体中每一个属性所使用的属性标 签集合。 一个w 曲实体( w e t ) 的模式可以被形式化为 s c h e m a s , = 厶，三，l ) ，其中t 是描述一个属性所使用的属性标签的集 合。 定义3 5 一个初始w e b 实体模式是一个特殊的w e b 实体模式，它由w e b 实体发现过程根据一组w e b 页面中的属性标签自动学习生成，它仅包含了对 于一个w e b 实体对应的所有实例的基本认识。初始w e b 实体模式仅仅覆盖 了目标实体对应的所有实例的特征知识的一个很小的子集。 w e b 实体发现过程是一个自动发现w e b 页面中新出现的w e b 实体的过 程。一个初始w e b 实体模式具有该类实体所具有的部分属性对应的属性标 签。一个初始w 曲实体模式可被形式化表示为s c h e m a 缸t = 厶，三，一，l t ，其 中v s c h e m a i m t ，3 s c h e m a ，is c h e m ai | s c h e m a “ti ，并且弘，s c h e m a i 血， 弘s c h e m a ，l i 。 基于上述相关定义，本文研究的w e b 实体模式构建问题主要包括两个方 面，可以描述为： 一方面，如何为一个新发现w 曲实体构建一个新的初始w e b 实体模式 s c h e m a 缸t ；另一方面如何将目标网页中发现的新属性标签，丰富至现 有对应w e b 实体的模式s c h e m a 中，s c h e m a = 厶，厶，乙) 。丰富的形式有 两种，一种是丰富至w e b 实体模式中对应的属性中，即厶= l iu k ，另一种 是作为一个新的属性，丰富至w e b 实体模式中，即，s c h e m a = s c h e m a u l m + l ， l m + 。= 。 。通过两种丰富形式，达到丰富w 曲实体模式的目的。 由于w e b 上广泛存在的半结构化数据的模式动态变化，w e b 实体模式的 构建是一个逐步丰富，逐步扩充的过程。一方面为新发现的w e b 实体生成对 应的初始w e b 实体模式；另一方面，随着新属性标签的逐步发现，对应w e b 实体的模式信息得到逐步地丰富。 3 3 构建w e b 实体模式 w e b 实体模式的构建主要分为两个部分：新建初始w e b 实体模式和丰富 2 4 6 j - 么 山东大学博士学位论文 w e b 实体模式。对于目标页面中新发现的w e b 实体，需要新建对应的初始 w e b 实体模式：对于w e b 实体模型中已存在的w e b 实体，需要利用目标页 面中发现的新属性标签丰富对应的w e b 实体模式。 3 3 1 新建w e b 实体模式 当一组目标页面中包含的w e b 数据对象被确定为属于新的w 曲实体 ( e 。) 时，利用现有的模式抽取方法6 7 6 8 6 引，可以有效地将这组w 曲页面 中w 曲数据对象的属性标签， ，以) ，抽取出来。为新建的初始 w e b 实体模式记为s c h e m a “t ，s c h e m a i l l i t = 厶，厶，乙 ，l i = t 。 3 3 2 丰富w e b 实体模式 由于半结构化数据模式的异构性和动态变化，导致在不同的网站中，描 述相同类型w 曲数据对象所使用的属性标签不尽相同，丰富多样。因此，需 要对w e b 实体模式进行丰富，满足w e b 数据集成和w e b 数据抽取的需要。 对于已有的w e b 实体模式，s c h e m a w z , ，s c h e m a w e = 厶，三一，乙 ，, s c h e m a w 墨描述的w 曲实体记为w e i ，w o i 是目标页面中属于w 曲实体w e i 的 一组w e b 数据对象。页面中用于描述w o i 所使用的属性标签集合记为r ， t = t a 9 1 ，嘲2 ，t a g ， 。对于w ，t a g t ，如果对于v i ，t a g ，仨厶，厶e m ， 那么将螂，丰富至s c h e m a s 中。, 本文提出一种动态丰富w 曲实体模式的方法，利用条件随机场实现已有 w 曲实体模式和目标页面中属性标签之间的模式映射，解决w 曲实体模式的 丰富问题。该方法在丰富w e b 实体模式的同时，也有效地解决了w e b 实体 模式与目标页面中w e b 数据对象的属性标签间的模式匹配问题，提高了w e b 数据集成系统的效率。 本节首先讨论w e b 实体模式丰富算法的主要思想；然后，详细介绍条件 随机场模型，包括参数估计及推理部分；最后，介绍如何利用条件随机场解 决w 曲实体模式丰富问题。 山东大学博士学位论文 3 3 2 1 主要思想 本方法的主要思想是： 首先，利用已有的w e b 实体模式和w e b 数据集成系统中已存在的数据， 识别出目标网站采样页面中包含的数据元素及属性标签。 然后，以w e b 实体模式中现有的属性标签作为标签集，以w e b 数据集 成系统中已存在的对应的w e b 数据对象信息作为训练集( 在本文实验中，为 了降低处理代价，采用中等规模数据库作为训练集) ，利用c r f 方法对目标 网站采样页面中识别出的数据元素进行标注。 最后，对于满足置信度要求的标注结果，与目标网站采样页面中自带的 属性标签建立映射关系，同时将采样页面中的属性标签添加至w 曲实体模式 中对应的属性中，丰富对应属性的属性标签集合：对于不满足置信度要求的 标注结果，将采样页面中的属性标签作为一个新增的属性丰富至w e b 实体模 式中。 整个算法是一个多次迭代的过程，随着w 曲页面中新属性标签的发现， w e b 实体模式得到逐步的丰富。 3 3 2 2c r f 模型 条件随机场是在最大熵模型和隐m a r k o v 模型的基础上提出来的一种判 别式概率无向图学习模型，由于使用全局优化技术，它克服了最大熵m a r k o v 模型的标注偏置问题，是目前处理序列数据分割与标注问题的最好的统计机 器学习模型。条件随机场的一般定义【7 0 1 如下： 定义3 6 设g = ( 矿，e ) 是一个无向图，y = y vi1 ，v 是以图g 中结点 ，为 索引的随机变量儿构成的集合。如果每个随机变量儿相对于图 p ( 儿l y 。 孵，x ) = p ( 儿i 咒，x ，( 材，v ) e ) 服从m a r k o v 属性，则称( x ，】，) 是一个 条件随机场7 0 1 。 设c = ( t ，y 。) 是图g 中所有的团构成的集合，根据随机场的基础理论 ( 由h a m m e r s l e y 和c l i f f o r d 于1 9 7 1 年提出) ，在给定观测序列x 的条件下标注 序列y 的概率分布p ( y l 曲为 ljii叫 山东大学博士学位论文 p a ( y i x ) = 去婴唧( ；五以( t ) ( 3 ) 其中，以( j ，。，以) 是特征函数，z ( x ) = n e x p ( 2 k ( y 。，t ) ) 是归一化因子， y t l 模型参数是一个由实数构成的特征函数的权重值集合a = 以) 。 当用该模型来建模序列数据时，图g = ( v ，e ) 中状态变量y 的形状最简单 且最常用的是一条一阶链。这条链中的团是其中的结点和边。因此，在整个 观测序列上可以定义两类特征函数：状态特征函数g o ，y i ，x ) 和转移特征函数 f ( i ，y “，y ，功。给定训练样本集 ( x 舶，y ) ) 和预定义的特征函数，可以从样本 集中学习一个c r f s 模型。模型参数人可以使用极大似然、极大后验或 q u a s i n e w t o n 等方法【7 11 估计。 对于一个输入测试序列x ，则可以使用训练得到的c r f s 模型来推断它 对应的标注序列，x 最可能的标注序列y 表示为， 多= a r g m a x p ( y z ) = a r g m a x z z 2 k f k ( y , ，x 。) ( 3 2 ) yy* c y 可以使用与h m m 中相同的v i t e r b i 算法来查找。 3 3 2 3 模式丰富 下面通过给出一个具体的算法，描述如何解决w e b 实体模式丰富问题。 输入：一个w e b 实体模式，s c h e m a 喝，s c h e m a s , = 厶，l s ，厶) ； w e b 数据集成系统中已存在的属于w e b 实体w e i 的w e b 数据对象集合，o ； 吣= e l yo ，e f “，p 。 是目标页面中属于w 曲实体w e i 的一组w 曲数据对象， e l e m e n t s 和t a g s 分别是w o i 中包含的数据元素集合和属性标签集合， e l e m e n t s = e l e l ，p 跆2 ，e l e f ，) ，t a g s = t lt 2 ，t j ， ( 如果i = j ，那么属性标 签t ，将用于描述数据元素p 纸) ； 输出：丰富后的w e b 实体模式，s c h e m a s ； 采样页面中的属性标签与实体模web式中属性的映射关系m a p p i n g s ； 2 7 山东大学博士学位论文 模式丰富算法： ( 1 ) 以w 曲实体模式s c h e m a 翮e = 厶，l ) ，( 1 ) 作为标, l j j m 签集合，以。作为训练集合，利用c r f 模型对采样页面中的数据元素集合 e l e m e n t s 中的每一个元素( e l e i ) 进行标注，对每一个数据元素e l e i 的标注结 果记为t a g ；： ( 2 ) 对于任意一个e l e i 及其对应的属性标签，如果标注的标签t a g ，的 置信度c o 畈。盯，( t a g ，厶，1 k m ) ，那么和魄，建立映射关系，并将 作为同义词丰富至w e b 实体模型，l k = l ku t ，； ( 3 ) 对于任意一个p 峨及其对应的属性标签，如果标注的标签t a g ，的置 信度c o n z o g 仃，( t a g ，厶，1 k m ) ，那么，l m + 1 = t f ，l = 工u k l ( 4 ) 输出被丰富后的w 曲实体模型，s c h e m a s = 。,s c h e m a s , 在算法的第1 步，主要利用c r f 的良好标注性能，对采样页面中的数据 元素进行标注；目标网站采样页面中的每一个数据元素e l e i ，都会被标注为 标签集l 中的一个标签，t a g 。： 第2 步和第3 步的目的是实现对w e b 实体模式的丰富，丰富的策略有两 个： 第一，如果c r f 方法给出的标注标签( t a g 。) 的置信度满足阈值要求， 即c o 畈。仃，那么建立采样页面中属性标签，与w 曲实体模式中相应 标签，嘲，( t a g ，厶，1 k m ) ，所在属性的映射关系，即朋孵：厶ht ， 标签丰富至w 曲实体模式中，厶= l ku t ，；同时扩充映射结果 m a p p i n g s = m a p p i n g sum a p f 第二，如果c r f 方法给出的标注标签( t a g 。) 的置信度不满足阈值要求， 即c o ，。 ，而学习得到的属性标签集合 为既。d = 厶，三，- ，l m ) ，从聚类的角度来看，对应于耐的标准聚类结果 可以写作c 酗以= 厶，l i ，厶 ，对应于瓯。删的聚类结果可以写作 巴a r n e d = 厶，三一，l m ) ，就可以利用w e i g h t e d a v e r a g e f s c o r e ( w a f s c o r e ) 来对 2 9 山东大学博士学位论文 字刿得到明属任称釜集合明质萤迓仃详佰ow a f s c o r e 经帚破用征灯聚灭绢呆 进行评估7 2 1 。本文利用它作为一类评价指标，利用相对于c g l o b 础的 w a f s c o r e ，来衡量学习得到的属性标签集合一d 的质量。相对于面 的w a f s c o r e 定义为： 兰忆1 w a f s 鸭 w a f s c o r e = 旦f 一 ( 3 3 ) 旧l i = 1 2 p r e c i s i o nrr r e c a l l ，r 苴中川椭堋厶2 爿m ，a x ，。而蕊等武。4 ) p r e c i s i o = 掣，酬k 厶= 可i l j n l , i ( 3 5 ) 为了进一步评测w e b 实体模式动态构建方法的性能，可以使用信息检索 中的评测方法，采用查全率( r e c a l l ) 和查准率( p r e c i s i o n ) 对该方法的性能进 行评价，具体定义如下： r e c a l l 啦= 焉觜n 6 ， p r e c i s i 。n 曲= 囊霎雪季耋喜器c 3 7 ， r e c 虬。= 焉鬻群p 8 ， i o n 捌= 甓蒙搿 9 ， 3 4 3 实验结果及分析 3 4 3 1 重要属性标签的识别 为了便于与y a o 等【6 6 1 提出的方法进行比较，在实验中，对于每种w e b 实体，选择5 1 0 个频繁出现的属性作为重要属性，验证属性标签的获取和 分类准确率。在图书实体中，选择萨考、出版旌，i s b n 、盅版例饲、芋我， 历雳分娄等六含属崖作为重要属性。在职位实体中，选择聊岔各荔、羼岔类 3 0 厶o 尽管两种方法在对重要属性标签的识别准确率方面性能相近，但是，二 者的方法在本质上仍然存在着明显的不同。文献【6 6 】首先利用搜索引擎从海 量网页中抽取出与目标实体对应的大量w e b 数据对象信息，并确保抽取的 w 曲数据对象中包含目标实体的重要属性信息；然后，提出一种基于最大熵 模型的聚类方法，利用收集的属性标签自动生成目标实体在w e b 网页中的重 要属性标签集合。和文献 6 6 】相比，本文的目的是为了获取w e b 页面中描述 目标实体的所有属性标签信息，而不仅仅局限于描述重要属性的属性标签。 获取目标实体所有属性标签的原因在于面向分析的w e b 数据集成系统需要 收集w e b 实体的所有相关信息，为进一步进行w 曲数据分析和挖掘等应用 提供全面和丰富的数据。另外，由于w e b 上广泛存在的半结构化数据的模式 动态变化的特点，导致w e b 实体模式的构建是一个逐步丰富的过程。相比于 文献【6 6 】提出的方法，本文采用动态构建w 曲实体模式的方法，随着目标网站 的增多，随着新属性标签的发现，w e b 实体的模式信息得到逐渐地丰富。因 此，本文提出的方法更能适合于w e b 数据集成系统。 3 4 3 2 模式信息的整体准确率 为了进一步验证本文提出的动态构建w e b 实体模式方法的性能，本文对 动态构建的职位和图书实体模式信息中的属性及属性标签的准确率情况进行 山东大学博士学位论文 验证。在实验中，首先利用训练集中的字段信息作为对应实体的初始模式， 然后利用预先获取的2 5 个目标网站采样页面中包含的模式信息动态地丰富 对应实体的模式。图3 3 和图3 4 显示了随着目标网站的增加w e b 实体模式 中属性的动态丰富情况。w e b 实体模式中属性的数量一开始增长迅速，但随 着网站数量的增加增长逐渐趋于平缓。 2b01 0 121 8 e2 0 2 2 2 4 2 6 网站效 图3 3 职位实体模式中属性的个数 岛 p 帅 伯 钟 爱牛掣薯廿帽嚣 “ 山东大学博士学位论文 布情况，导致错误地分配至同一属性而影响了准确率：另外，由于图书网站 多为商业销售网站，广告众多，导致在抽取标签过程中抽取了一些错误标签， 影响了准确率。 表3 1 构建的模式信息的准确率 实体属性属性标 r e c a l l a t 竹p r e c i s i o n 订r e c a l l , a b e l p r e c i s i o nl 曲c l 类型个数签个数 b o o k8 71 1 69 1 4 8 4 7