（计算机软件与理论专业论文）deep+web数据源发现相关技术研究.pdf

d e e pw e b 数据源发现相关技术研究 中文摘要 中文摘要 随着网络飞速发展和所含信息规模的日益扩大，当前w e b 中蕴含了大量的各种 各样的数据，其中很大一部分是高质量的结构化信息。而这些信息大多被保存在w e b 在线数据库中，用户只能通过查询接口来获取相关的信息，这类信息被称为d e e pw e b 信息。对这些结构化信息进行收集并集成，以提供高质量的结构化信息的检索服务， 用户就能够快速、准确地找到所想要的信息。要对d e e pw 曲信息进行收集，首先必 须解决的问题就是发现数据源。 本文对d e e pw e b 数据源发现所涉及到的相关技术进行了分析研究，并提出了相 关的算法和模型。主要研究工作包括： ( 1 ) 研究了基于d e e p w e b 的查询接口判定技术。d e e pw e b 查询接口是d e e pw e b 信息访问的入口，所以对数据源的发现其实也就是对查询接口的发现。本文提出了 一种基于表单特征图的查询接口判定算法。 ( 2 ) 采用分布式爬虫技术处理d e e pw e b 数据源发现问题，提出了一个面向查询 接口判定的爬虫框架及算法。 ( 3 ) 通过实践比较不同页面信息抽取方法的优缺点，提出一种基于d o m 树的页面 信息抽取技术，该方法在d o m 树准确定位的基础上，较好地处理了接口抽取中出现的 问题。 ( 4 ) 对收集到的数据源信息进行初步的处理，主要是去重处理，获得都是唯一的 包含查询接口的表单。 此外，本文还对文中提出的方法和技术进行了实验，通过对实验结果的分析进一 步验证本文提出的技术方法是行之有效的。 关键词：d e e pw e b ，数据源发现，特征图结构，接口判定，特征抽取 作者：李林 。 指导老师：崔志明( 教授) a b s t r a c tt h er e l e v a n tt e c h n o l o g i e sr e s e a r c ho nd e e pw e bs o u r c ed i s c o v e r y a b s t r a c t w i t hr a p i dg r o w i n go fn e t w o r ka n dg r a d u a le x p a n d i n go fi n f o r m a t i o n ss c a l e ，t h e r ei s am a s so fk i n d so fi n f o r m a t i o ni nt h ew e b ，m o s to ft h e ma reh i g h q u a l i t ys t r u c t u r e i n f o r m a t i o n i nm o s ti n s t a n c e s ，t h i si n f o r m a t i o ni ss t o r e di no n l i n ed a t a b a s e s ，u s e rc o u l d g e tt h e mo n l yb ys u b m i t t i n gq u e r i e si ns e a r c hi n t e r f a c e ，a n dw e c a l lt h e ma sd e e pw e b i n f o r m a t i o n i no r d e rt op r o v i d eh i g h q u a l i t ys e a r c hs e r v i c eo ns t r u c t u r e di n f o r m a t i o n ，t h e f i r s ts t e pi s c o l l e c t i n ga n di n t e g r a t i n gt h i si n f o r m a t i o n t h e nu s e rc o u l dr a p i d l ya n d a c c u r a t e l yf i n dt h i si n f o r m a t i o nw h i c ht h e yn e e d a n dt h ef i r s tt h i n gi sd i s c o v e r i n gd a t a s o u r c e sw h e nc o l l e c tt h ed e e pw e bi n f o r m a t i o n ， i nt h i sp a p e r , w ea n a l y z ea n dd or e s e a r c ho nt h er e l e v a n tt e c h n o l o g i e so fd a t a s o u r c e sd i s c o v e r y , a n dp r o p o s et h er e l a t e da l g o r i t h m sa n dm o d e l s t h em a i n w o r ko ft h i s p a p e ri n c l u d i n g ： ( 1 ) r e f e rt od e t e r m i n a t i o nt e c h n o l o g yo fd e e pw e bs e a r c hi n t e r f a c e d e e pw e b s e a r c hi n t e r f a c ei st h ee n t r a n c eo fa c c e s s i n gt h ed e e pw e bi n f o r m a t i o n ，d i s c o v e r i n gt h e d a t as o u r c e si nf a c ti sd i s c o v e r i n gt h es e a r c hi n t e r f a c e w ep r o p o s e das e a r c hi n t e r f a c e d e t e r m i n a t i o na l g o r i t h mb a s eo ng r a p hc o n s t r u c to ff o r mf e a t u r e ( 2 ) a d o p tad i s t r i b u t e dc r a w lt e c h n o l o g yt or e s o l v et h e s ep r o b l e m si nd i s c o v e r i n g d e e pw e bd a t as o u r c e p r o p o s eaf r a m e w o r ka n da l g o r i t h mo fc r a w l e ru s e di ns e a r c h i n t e r f a c e sd e t e r m i n a t i o n ( 3 ) c o m p a r et h ea d v a n t a g e sa n dd i s a d v a n t a g e so fd i f f e r e n ti n t e r f a c ee x t r a c t i n g t e c h n o l o g i e s ，a n dp r o p o s ea ne x t r a c t i n gt e c h n o l o g yb a s eo nd o m t r e e t h i sm e t h o dc a l l s o l v et h ep r o b l e m so c c u r r e di ni n t e r f a c ee x t r a c t i n gp r e f e r a b l y , m a k i n gu s eo fp r e c i s e l y l o c a t i o n ( 4 ) p r e l i m i n a r yp r o c e s sf o rc r u d ed a t as o u r c e ，t h em a i nw o r ki sd u p l i c a t i o nd e l e t i n g a n dg a i nt h es e a r c hf o r ms e tt h a tc o n t a i nn o n d u p l i c a t e i na d d i t i o n ，w ev e r i f yt h ee f f e c t i v e n e s so ft h em e t h o da n dt e c h n o l o g yp r o p o s e di n t h i sp a p e rt h r o u g he x p e r i m e n t i i t h er e l e v a n tt e c h n o l o g i e sr e s e a r c ho nd e e pw e bs o u r c ed i s c o v e r y a b s t r a c t k e y w o r d s ：d e e pw e b ，d a t as o u r c ed i s c o v e r y , f e a t u r eg r a p hs t r u c t u r e ，s e a r c hi n t e r f a c e d e t e r m i n a t i o n ，f e a t u r ee x t r a c t i o n i l l w r i t t e nb yl il i l l s u p e r v i s e db yc u iz h i - m i n g 图表目录 图卜1d e e pw e b 信息搜索2 图2 - 1 查询接口的集成模块7 图2 2 图书信息的查询接口8 图3 1 表单中的特征1 2 图3 2 表单特征图1 5 图3 3 生成的表单特征图的信息2 1 图3 4 表单特征图的扩展更新信息2 1 图3 - 5 查全率和查准率2 1 图4 - 1 数据源发现操作流程2 7 图4 - 2u r l 处理过程2 7 图4 3 分布式爬虫拓扑结构2 8 图4 4 爬虫程序的操作流程图2 9 图4 - 5 获得带有可查询表单的站点个数3 2 图4 6 获取数据源可查询表单的查全率和查准率3 3 图5 1h t m l 页面文档3 6 图5 2 近似的h t m l 页面的d o m 树结构3 7 图5 3 网站中包含图书信息的页面3 8 图5 - 4 网站中包含房产信息的页面3 9 图5 - 5 制定的抽取规则4 0 图5 - 6 抽取规则制定工具一l 4 1 图5 - 7 抽取规则制定工具一2 4 2 图5 - 8 抽取规则制定工具一3 4 2 图5 - 9 字段值分簇过程4 7 表3 11 7 组测试的阈值设置2 0 表4 - 18 组阈值设置3 2 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名： 羔垃日期：啦 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：日期： 期：一 d e e pw e b 数据源发现相关技术研究 第1 章绪论 第1 章绪论 本章主要介绍d e e pw 曲研究背景和研究意义，以及d e e pw 曲当前的研究现状。 同时，提出了本文的研究内容和目标一如何更好地进行数据源的发现，最后给出本文 的章节安排。 1 1 背景与意义 随着网络技术应用的发展，w e b 上的信息以爆炸式的速度在增长。根据信息的蕴 含方式，可分为两大类：s u r f a c ew e b 和d e e pw e b 。面向s u r f a c ew e b 的信息检索应 用很多，目前传统搜索引擎大部分的检索工作都是在s u r f a c ew e b 上进行的，但是其 检索到的页面都是静态的或者通过u r l 可以直接链接到的页面，对于那些较灵活的动 态页面，如以表单f o r m 作为查询接口，根据用户的输入动态地返回相应信息的页 面，传统搜索引擎的检索技术就无能为力了。而在隐藏在查询接口之后的在线数据库 往往包含大量高质量信息。 d e e pw e b 蕴含了整个w e b 中大部分的信息，而s u r f a c ew e b 蕴含的信息较之有 千百倍的差距，而且d e e pw 曲与s u r f a c ew e b 相比，具有很多优点【l 】【2 】【3 】： ( 1 ) 信息量大。根据研究调查，d e e pw 曲页面的信息大约是s u r f a c ew e b 信息的 8 0 0 倍，包含了大量传统搜索引擎搜索不到的信息。c o m p l e t e p l a n e t 网站曾对 w e b 上的6 0 个包含w e b 数据库的站点进行统计【4 】【5 1 ，发现这6 0 个站点的总 数据量达到7 5 0 0 ，0 0 0 g ，大约是s u r f a c ew e b 中数据量的4 0 倍。 ( 2 ) 信息质量高。在线数据库中的信息都是以结构化的形式保存的，并且同一个 数据库中一般只保存一个或几个领域的信息，信息的针对性强，可利用性高。 ( 3 ) 信息增长速度快。目前d e e pw e b 中的信息规模还在迅速增大，目前平均每年 的增长速度是3 7 倍。 所以，鉴于以上几个优点，充分利用d e e pw 曲中的信息就显得意义重大。但是由于 d e e pw 曲中固有的信息蕴含方式，导致了获取这些信息时存在很多困难。d e e pw e b 课题的提出，也就是为了解决或者在一定程度上解决d e e pw 曲信息检索过程中出现 型! 苎堑堡 ! ! 兰! 塑塑塑垄里型型! ! 型苎 的问题。 d e e pw e b 数据来源于w e b 在线数据库，目前获取这些在线数据库中信息的主要 途径是在查询接口上提交查询来获得所需要的信息【6 1 ，如图11 所示。因此，用户查 询信息时可能需要多次填写表单，或者同时在多个网站上提交关键字以获得需要的信 息。很显然，这个过程很繁琐且耽误时间，而且获得的信息很多都是重复冗余的，这 样使得查询效率低下。d e e pw e b 研究的重点就是收集这些在线数据库中的信息，并 对其进行集成，然后提供一个统一的查询接口给用户，使用户的查询效率更加高效。 同时还可以添加一些可供用户选择的信息处理功能，使得信息检索更贴近用户实际需 要。 蚧 一控棠引擎 w e b 搜索引擎的搜棠部分 一 _ 图1 1d e e p w e b 信息搜索 在d e e p w e b 研究中，数据源发现是首先需要解决的问题，数据源的数量、质量 直接关系到信息的集成质量的好坏。本文对d e e pw e b 数据源发现技术进行了研究与 设计，重点对其实现的关键技术进行了研究，如：d e e pw e b 查询接口的特征抽取技 术、d e e pw e b 查询接r n 的判定等，同时也提出了一种基于分卸式的d e e pw e b 聚焦爬 虫的设计。 d e e pw e b 数据源发现相关技术研究 第l 章绪论 1 2 国内外研究现状 目前，在d e e pw e b 数据源发现这个课题上，已经有很多研究人员进行了研究。 对于在w e b 上大规模地搜索可能存在的数据源，主要可分为两个途径：第一个途径就 是利用现有的搜索引擎来搜索数据源。这个方法实现相对简单，而且不需要耗费大量 的资源来遍历整个w e b ，但其对于搜索引擎的依赖性很大，不适合自主独立地进行数 据源发现操作。 另一个途径就是通过超链接遍历整个w e b ，来获得数据源。这种方法类似于自己 构建一个搜索引擎，然后利用这个搜索引擎一边遍历整个w e b 上的页面，一边判断当 前页面中是否有w e b 数据库查询接口。这样可以解决依赖性的问题，但是在检索的过 程中，遍历所有的超链接，使得其检索效率很低，代价也很高。所以有些研究在此基 础上进行了改进，如l b a r b o s a 等利用p a g ec l a s s i f i e r 矛l l l i n kc l a s s i f i e r 找到并抓取相关度 比较高的叫所指向的页面【7 】，以及后来他们改进的带有自动归纳和学习能力的方法 【8 】，使得处理效果更准确。 除以上两个途径之外，还有其他一些方法，如利用c o m p l e t e p l a n e t c o m 和 i n v i s i b l e w e b n e t 这样的网站获取数据源【9 】、遍历所有的i p 来获取数据源等。这些方法 不是缺乏在商业中运行的可行性，就是花费的时间和资源太高，甚至达到不可完成的 地步。 同时，对于d e e pw e b 查询接口的判定问题，也有很多的方法提出来。如：c o p ej 等利用c 4 5 决策树来找到真正的查询接口【10 1 。还有j p l a g e 等依据两个从实际经验中 总结出来的规则来获取大量的查询接口【1 1 1 ，但其方法有一定的局限性，效果也不是很 理想。 以上这些方法各有优缺点。本文在数据源发现问题上对上述搜索数据源的第二种 方法做了改进，使得发现效率更高，速度更快。并且在对d e e p w e b 查询接口判定的 问题上，也提出了一种基于表单特征的图结构的查询接口判定模型，使得判定更加准 确。 1 3 研究的主要内容 第1 章绪论 d e e pw e b 数据源发现相关技术研究 在研究d e e pw 曲数据源发现的过程中，需要重点解决的问题在于查询接口的判 定，以及如何提高大规模d e e pw e b 查询接口搜索的效率。其中查询接1 ：3 的判定是 d e e pw e b 数据源发现研究中最重要的部分，它直接关系到发现的是否是真正的数据 源。而对于大规模的信息检索所带的大计算量问题，目前主要的解决方法是利用分布 式计算和并行计算，其中在分布式计算网络中，多个计算节点之间结构关系和任务分 配也要视任务的需要有所改变。 在解决以上这些问题的过程中，也涉及到其他相关技术的实现，如查询接口抽取， 数据清理等，这些都直接关系到查询接口判定的准确率。查询接口抽取属于页面信息 抽取的一个应用，而页面信息抽取是w e b 信息搜索的最基本的技术之一【1 2 】，本文采 用了一种基于d o m 树的页面信息抽取方法，较准确且较灵活地解决了信息抽取时遇 到的问题；在数据清理方面，本文提出了一种基于结构化信息的去重方法，该方法有 效地对含有结构化信息的查询接口进行去重处理，从而获得不重复的查询接口样本 集。 1 4 本文组织 本文共分为七章： 第1 章介绍了d e e pw e b 及其接口判定的研究背景及意义、国内外研究现状以及 本文的结构安排。 第2 章对d e e pw e b 相关研究进行介绍，并对d e e pw e b 数据源发现研究过程中 所面临的问题进行阐述，继而引出了本文所要阐述的数据源发现方法，其中重点是对 d e e pw e b 查询接口的判定进行了介绍。 第3 章详细介绍了面向d e e pw e b 的查询接口判定的过程中遇到的问题，同时提 出一种利用表单特征的图结构进行查询接口判定的模型，并对该模型的判定方法进行 了详细的说明与分析。 第4 章介绍了一种基于分布式的面向d e e pw e b 查询接口发现的爬虫技术，接着 对该爬虫模型框架涉及的内容进行了阐述与分析。 第5 章阐述了在d e e pw e b 数据源发现过程中用到的其他的相关技术，这些技术 主要包括：接口抽取技术和结构化信息去重技术。 4 d e e pw e b 数据源发现相关技术研究 第1 章绪论 第6 章总结了本文所做的工作，说明了工作的特色与创新之处，并对今后的工作 进行了展望。 第2 章d e e p w e b 数据源发现概论d e e pw e b 数据源发现相关技术研究 第2 章d e e pw e b 数据源发现概述 本章首先介绍了d e e pw 曲的概念，然后分析了d e e pw 曲不可见的原因，同时 对d e e pw r e b 数据源发现在d e e pw e b 研究中的地位进行介绍，最后提出了d e e pw 曲 数据源发现所面临的难点。 2 1 d e e pw e b 研究现状 d e e pw e b 又称h i d d e nw 曲或i n v i s i b l ew e b ，它是一个与s u r f a c ew e b 相对应的概 念。d e e pw e b 最初由d r j i l le l l s w o r t h 于19 9 6 年提出，d e e pw e b 是指用户通过一般搜索 引擎无法获取的那一部分网络资源。这些信息资源主要是包含在在线数据库中i l 引，由 页面动态地提供n w e b 上，传统的搜索引擎不愿意或者没有能力将d e e pw e b 信息放置 在索引库中，所以通过传统搜索引擎不可能发现d e e pw 曲中的信息内容，实际上d e e p w e b 中的数据量又是十分的庞大，并具有较高的质量和权威性，也具有很高的可利用 性。但是随着爬虫能力的提高，这一解释已不能很好地界定d e e pw e b 的概念了，目 前也很难有个一致的定义。在文献【1 4 】中，也对d e e pw e b 的范畴给了一些说明：d e e p w e b 是指w e b 中可访问的在线数据库，这里简称为w e b 数据库或w d b ，其内容存储在 真正的数据库中。这些内容只有在被查询时才会由w e b 服务器动态生成页面把结果返 回给访问者，因此没有超链接指向这些页面，这是和那些可以被直接访问的静态页面 的根本区别。c n n i c 早在2 0 0 5 年7 月就进行了一次互联网的调查，并且在发布的第十 六次中国互联网信息资源数量调查报告中提到【1 5 】：中国在线数据库的总量为3 0 6 万 个，而网站中拥有在线数据库的个数是1 6 1 万个，约占全部网站的2 4 1 。由此可见， 如何对网络上的d e e pw e b 数据源进行收集，同时对收集到的信息进行有效的管理， 以满足用户不断增长的信息需求，已经成为信息领域研究人员面临的新课题。 在通常的d e e pw 曲研究中，d e e pw 曲信息集成系统的框架主要分为查询接口集 成模块和查询处理模块【1 6 】【17 1 。如图2 1 所示，在查询接口集成模块中主要包括四个部 分：数据源发现、查询接口模式抽取、数据源分类和查询接口集成。其中数据源发现 就是查询接口集成模块第一步所要做的工作。 6 d e e pw e b 数据源发现相关技术研究第2 章d e e p w e b 数据源发现概论 数据源发现 查询接口模式抽取 一 查询接1 ：3 集成 l 露忍盈i 数据源分类 l、。jl、j 图2 1 查询接e l 的集成模块 到目前为止，已经有很多研究者对查询接口集成进行了大量的研究工作。例如在 文献l 沼】中，对d e e pw 曲查询接1 2 集成中遇到的问题及可利用的技术进行了介绍，同 时对查询接1 2 集成在数据收集过程中的地位进行评定。在文献【1 9 】中提出了一种利用分 簇聚合的方式对查询接口模式进行合并的方法，该方法主要利用表单特征作为依据来 对查询接口进行聚类，从而达到数据源分类的目的。而在文献1 2 0 】中提出一种查询接口 映射的方法，该方法利用的是数据源查询接口中信息的同质性来对数据源进行分类， 然后将其映射到不同的类别中，再对其进行集成。文献川中提出一种利用组合分类器 进行多层过滤的方式来进行数据源的发现，其中每个分类器在发现过程中各有侧重 点，而组合到一起后，能够达到单个分类器不能达到的效果。进行这方面工作的研究 者还有很多，如文献 2 2 】。 2 2d e e pw e b 信息“深藏 的原因 d e e pw 曲信息“深藏”的原因，主要是由于在w e b 上没有直接指向包含d e e pw e b 信息的页面的静态链接，目前传统搜索引擎不能通过链接发现和索引这些包含d e e p w e b 信息的页面。d e e pw 曲对于传统搜素引擎之所以不可见，其原因有以下几点： ( 1 ) 技术实现困难。传统的搜索技术都是以静态链接来检索页面的，通过有限层 的或循环的链接检索来爬取页面，而d e e pw 曲中的信息都是以动态页面的形式提供 到w e b 上。网站预先提供的只是一个查询接口表单，用户在检索想要的信息前，必 须先在查询接口中填入相关的关键字并提交，然后才能通过返回结果获得相关的信 息。所以，传统搜索引擎在检索这样的信息时就显得无能为力，因为传统搜索引擎没 7 第2 章d e e p w e b 数据源发现概论 d e e pw e b 数据源发现相关技术研究 有将查询关键字自动提交给查询接口以获得返回结果的能力。 ( 2 ) 由于d e e pw 曲惟一”入口点”是查询接口( 如图2 2 所示) ，d e e pw 曲爬虫设 计面对的主要挑战是怎样对查询接口自动产生有意义的查询。目前，还没有一种比较 实用的方法能够做到产生合适的查询关键字的能力。 图2 2 图书信息的查询接口 2 3d e e pw e b 数据源发现重要性 d e e pw 曲中蕴含了大量的可供访问的信息，由于这些信息的海量性和高质量性， 其利用价值就显得尤为突出，并且d e e pw e b 中信息还在迅速地增长。尽管d e e pw e b 中蕴藏了如此丰富的信息，但是由于d e e pw 曲中数据的动态性和异构性，如何有效 地收集并利用这些信息就成了一件十分有挑战的工作。当前，越来越多的研究人员对 d e e pw e b 信息的收集和集成进行研究，在该领域已经开展了大量的研究工作，以获 得大量从s u r f a c ew e b 上获得不了的信息，来满足越来越大的信息需求。 d e e pw 曲数据源的发现作为d e e pw 曲信息收集的第一步，其作用就显得尤为重 要，其处理结果也直接影响整个d e e pw e b 信息系统。 ( 1 ) d e e pw 曲数据源发现的处理结果直接影响到收集到的数据的广度和权威性。 在发现的过程中，如果丢失大量可利用的数据源时，那么在信息抽取过程中，也将有 大量可利用的信息，其中肯定也包括大量权威性很高的信息。 ( 2 ) d e e pw 曲数据源发现的处理结果也影响到之后诸多处理过程的处理结果，如 数据的分类、聚类、集成等。在发现d e e pw 曲数据源的过程中，大多利用训练集以 8 d e e pw e b 数据源发现相关技术研究第2 章d e e p w e b 数据源发现概论 监督学习的方法对页面表单进行分类和聚类。在这些方法中，相对唯一的数据源查询 接口的模式越多，将更有利于提高查询接口的分类和聚类的准确性。同时数据集成也 将在这些分类、聚类结果的基础上进行，所以将间接地影响d e e pw e b 信息系统查询 的准确性。 2 4d e e pw e b 数据源发现难点 在d e e pw 曲数据源发现的过程中，将面临很多难题。这些难题极大地限制了数 据源发现的精度和广度，这些难题主要有： ( 1 ) 如何在w e b 上进行海量信息的检索，从而发现数据源。由于w e b 上信息量巨 大，想要从中找到对应着w e b 数据源的查询接口，需要的计算量将很巨大的。如何 根据d e e pw e b 数据源的实际情况，设计一种有效而快速的数据源发现程序就成了数 据源发现中一个重要的研究部分。 ( 2 ) 数据源发现研究中最重要的部分就是查询接1 3 的判定。因为d e e pw e b 查询 接口也是利用提交表单的形式来提交查询信息，然后再返回查询结果信息给用户。在 学界，页面表单分为“可查询表单”和“不可查询表单 ，“可查询表单就是能够通 过用户提交的查询信息返回查询结果的表单，如图书信息查询、火车票信息查询等； 而“不可查询表单 是指用户提交信息，但是没有返回信息，一般只是起到有权限的 页面跳转的作用，如用户登陆、注册用户信息等。在d e e pw e b 数据源发现的过程中， 最主要的一个部分就是判定表单是否是“可查询表单 ，目前已经有很多研究人员对 这一部分进行研究，基本上所有已提出的方法都是利用页面中的表单特征来进行查询 接口判定。但是面对当前表单特征变化迅速的情况，如何采用一种自适应的、能主动 学习的方法，就显得尤其迫切。 2 5 解决方法的介绍 在本文中，提出了一种利用表单特征图结构的模型对页面表单进行查询接口判 定。其基本思想是：利用半监督学习的方式，将表单特征提取并构建表单特征图结构， 并根据特征在样本空间中出现的次数来为每个特征和特征之间的边赋予权值。然后根 据特征图对待判定表单求权值和，该权值和依据判定表单中的特征的权值和特征之间 9 第2 章d e e p w e b 数据源发现概论d e e pw e b 数据源发现相关技术研究 边的权值确定的，再根据权值和来判定该表单是否是w e b 数据源的查询接口。 对于w e b 上进行海量信息检索所带来的大计算量的问题，本文根据d e e pw 曲数 据搜集的特有情况，提出一种基于分布式的爬虫系统来解决在这个问题。利用分布式 网络中的多个节点并行处理的特征，统一协调各个节点之间的处理，从而大大提高检 索的速度和效率。 2 6 本章小结 由于d e e pw e b 信息蕴含的方式，使得w e b 信息检索受到很多的局限。其原因主 要是d e e pw e b 是利用查询接口来进行信息的收集，而不能像s u r f a c ew e b 一样利用 叫链接直接进行信息的爬取。同样，d e e pw e b 数据源发现也受到这样的限制，只能 通过对页面表单信息进行分析，从而找到需要的数据源。在发现数据源的过程中，一 个很重要的影响因素就是查询接口判定的准确度，在当前w e b 上信息变化万端的情 况下，必须实现一个可学习的自适应方法，来对页面表单进行查询接口判定，从而提 高查询接口判定的准确度。 1 0 d e e pw e b 数据源发现相关技术研究第3 章d e e p w e b 接口的判定 第3 章d e e pw e b 接口的判定 本文采用一种基于表单特征图结构的模型来对d e e pw 曲接口进行判定。主要是 分成两个部分，一、利用表单特征来构建图；二、利用表单特征构建的图进行查询接 口判定，并且可以增量的对图进行节点和边的扩充。 3 1 引言 目前，由于d e e pw e b 信息数量大、质量高【2 3 】【2 4 】的特性，如何获取d e e pw e b 中 的信息就成为一个很有应用价值的课题。获取d e e pw e b 信息的第一步就是如何在 w e b 上发现数据源，而数据源发现的一个主要难题就是如何准确地判断一个表单是否 是d e e pw 曲数据源的查询接口，所以在d e e pw e b 研究中，一个非常重要的课题就 是d e e pw e b 查询接口判定。 在进行d e e pw e b 查询接口的判定过程中，表单模式( 包括标签特征和控件特征， 如图3 1 所示) 对于接口判定有着不同的贡献【2 5 】。同时，这些特征之间的关系往往也 会对查询接口判定有不同程度的作用，如：表单控件i n p u t t y p e = ”t e x t ”作为控件 特征对判断该表单是接口的贡献并不大，但是，如果和标签特征“密码”结合出现时， 则可以认为该表单极大可能是用户登陆的入口，而不是查询接口；如果和标签特征“图 书名 结合出现，则可以认为该表单可能是进行图书信息查询的接口，类似的情况还 很多。所以在实际的操作过程中，需要把这些特征之间的关系也考虑到接口判定的过 程中去。 本文结合以上所述情况，提出一种基于表单特征图半监督学习的方法，来判定页 面表单是否是d e e pw e b 接口。该方法利用表单特征构建的图进行查询接口判定，从 而更加准确地判断查询接口，同时还有一定的自学习能力，可对表单特征构建的图进 行一定程度的自动更新。 本文结合以上所述情况，提出一种基于表单特征图半监督学习的方法，来判定页 面表单是否是d e e p w e b 接口。该方法利用表单特征构建的图进行查询接口判定，从 第3 章d e e p w e b 接口的判定 d e e pw e b 数据源发现相关技术研究 而更加准确地判断查询接口，同时还有一定的自学习能力，可对表单特征构建的图进 行一定程度的自动更新。 3 2 相关研究 图3 1 表单中的特征 d e e pw e b 的接口判定是d e e pw e b 数据源发现的关键部分，已经获得很多研究学 者的关注。女l ：i j u l i a n op a l m i e r il a g e 等人提出的判定方法【1 1 】，该方法根据实际经验总结 出来两条规则，然后根据这两条规则来判定网页表单是否是d e e pw e b 查询接1 2 1 ，该 方法实际效果很好，可以获取大量的d e e pw e b 查询接口，但该方法不具备学习功能， 其可适应性不高，性能上具有一定的局限性。c o p e 等人【1 0 】利用一个自动特征生成技 术对表单进行描述，同时利用决策树来对这些表单进行判定和分类。另外在文献【2 6 1 2 7 】 中也都提到一种根据文本特征进行比较学习的分类判定方法。 还有一些研究者利用一些较简单的方法来判断表单是否是查询接口，如文献【2 9 1 提出了一个简单的判断页面中的表单是否是查询接口的方法。该方法其实只由三个相 当简单的部分组成：1 、在页面中搜索表示表单的f o r m 控件特征，如果没有肯定不是 含有查询接1 ：3 的页面；2 、如果页面中有f o r m 标签，则看f o r m 表单中是否有t e x t 输入 控件的控件特征，如果没有则是查询接1 2 1 的可能性大大降低；3 、如果存在输入控件 t e x t 的控件特征，则如果其对应的标签为“查询”、“搜索”之类的标签特征，则该表单 是查询接1 2 1 的可能性又大大提高。这种方法在其实验中达到9 0 以上的准确性。还有 1 2 d e e pw e b 数据源发现相关技术研究第3 章d e e p w e b 接口的判定 文献1 2 9 1 中也提出一种查询接1 2 1 的自动判定方法。 以上的这些方法往往不是忽略特征之间的关系在判断查询接口时的作用，就是在 这方面考虑得不够全面，同时其可适应性差，缺乏自主学习的功能。本文基于这方面 的考虑，为了不断完善接口判定的策略，从而提出了一种基于表单特征图结构的模型 来判定d e e p w e b 查询接口的方法。 3 3 相关概念 定义1 ：( 表单特征本图) 假设存在图w 。，并有节点集合t o 阢i = l ，z ，来表示图 中的节点，其对应的权值集合为v r o = r r f = o , i = l ，彬；边集合e o 慨矽，d u = 彬， 其对应的权值集合为吼= f r 喝 d ， = ，z ，n 为节点个数。其中节点集合r 中的节点 表示从训练样本中获取的标签特征和控件特征，边集合e 中元素表示特征之间的关系 ( 这些关系影响查询接口的判定) 。其中节点和边分别被赋予权值，权值的大小表示 在判定查询接口时的贡献程度。图w o 就叫表单特征本图。 定义2 ：( 表单特征图) 由于训练样本数过少，在表单特征本图中一些边的权值 不能较准确地反映其在接口判定中的作用，同时由于表单特征本图中边过多，导致查 询接口判定计算量太大。为了解决这个问题，在表单特征本图的基础上构建表单特征 图。设表单特征图为形，其节点集合为丁，边集合为e ，则w cw o ，丁= t o ，e c e o 。 定义3 ：( 重合度m ) 在表单特征本图向表单特征图的转化过程其实就是标签 特征节点合并的过程，在这个过程中，首先要选择合适的标签特征节点。选择的过程 主要依赖重合度h l 来进行，当两标签特征节点的重合度h l 小于某一值时，则认为 可以合并。h l 的计算主要依赖控件特征与标签特征之间的边数确定。在标签特征本 图中，大多标签特征节点都对应一个控件特征，而控件特征的个数非常少( 不会超过 f r o m 所能拥有的控件的个数) ，以控件特征节点作为参照来筛选标签特征节点，将 极大地减少比较次数，提高检索速度。重合度h l 的计算遵从以下计算方法： i 肋瓯一肋嚷 h l = ：! e d g , + e d g j ( 3 - 1 ) 其中疗为控件特征的个数，e d g a 表示第k 个控件特征节点与标签特征节点乃 1 3 第3 章d e e p w e b 接口的判定 d e e pw e b 数据源发现相关技术研究 是否有相连的边，如果有则值为1 ，否则为0 ；e d g ，表示与乃相连的控件特征的个数。 定义4 ：( 同质度册) 判断两个标签特征节点是否可以合并到一个节点中，是 由这两个标签特征的同质度h g 决定的，如果同质度h g 小于等于某个值时，则认为 可以合并。册计算方法如公式( 2 ) 所示： 一木篇”刊木鬻 b 2 ， 其中p 为常数阳辛g a 本文在实验中设置为o 2 ，1 7 为控件特征节点的个数，v e k j 表示第k 个控件特征节点与标签特征节点乃之间的边的权值。 3 4 判定方法 本文采用一种基于表单特征的图结构的模型来对d e e pw e b 查询接口进行判定。 主要是分成两个部分：一、表单特征图的构建；二、利用表单特征图进行分类，并且 可以增量的对表单特征图进行节点和边的扩充。同时，可以对相应的权值进行修正。 3 4 1 方法原理 在方法中，构建一个表单特征图( 如图3 2 ) ，该图中每个节点和边都有其相对 应的权值，节点表示表单中包含的特征( 包括表单控件特征和标签特征，其中多个相 似的标签特征可以组合成一个节点) ，其权值表示该节点对判定接口的贡献，边的权 值表示边两端节点对应的特征同时出现在表单中时，对查询接口判定的贡献，然后将 表单中的特征依次在图中进行检索来计算相应的权值和，然后根据权值和判定是否是 查询接口。 同时在检索的过程中，当出现新的特征时，将其加入到待测特征集合中，并且将 该特征所属的表单保存到扩充训练集中，当扩充训练集中的新增表单增加到一定数量 后，则对标签特征本图进行新一轮扩充。 1 4 d e e pw e b 数据源发现相关技术研究 第3 章d e e p w e b 接1 3 的判定 3 4 2 构建表单特征图 图3 - 2 表单特征图结构 在表单特征图中，不同的节点有其相应的权值。权值分为正值和负值两种，数值 大小表示特征对表单判定为查询接口的认同程度，其中负值代表否定程度，正值代表 肯定程度。构建表单特征图的第一步工作就是利用事先准备的表单训练集检索特征来 确定一个表单特征本图，然后利用这个表单特征本图来进一步提取出一个可用于查询 接口判定的表单特征图。 3 4 2 1 构建初步的表单特征本图 首先需要构建一个表单特征本图，为了构建表单特征本图，需要准备一个经过人 工标注过并去重过的表单训练集，其中包括正例也包括反例，假设训练集为释阮 i = l ，垅，m 为训练集中元素的个数。 利用训练集构建表单特征本图，对表单特征本图中节点和边赋以权值的处理过程 如下： ( 1 ) 从训练集x 中选择一个表单进行处理，如果训练集中表单都已经处理过了， 则结束。 ( 2 ) 从表单x 中提取所有的特征，包括标签特征和控件特征，同时将用于保存当 第3 章d e e p w e b 接口的判定 d e e pw e b 数据源发现相关技术研究 前表单中已处理特征的队列q 清空，然后转到( 3 ) 。 ( 3 ) 从提取出的特征集合中选择一个未处理过的特征d t i ，如果在表单x 的特征集 合中，所有的特征全部处理过，则跳到( 1 ) ，否则转到( 4 ) 。 ( 4 ) 将d t j j o n 入到队列q 中，并且将d t i 在表单特征本图节点集合丁中进行检索， 如果特征d 乃在丁中检索到并且为正例，则把特征d t i 对应的权值加1 ；如果x 为反例，则将d t i 对应的权值减1 。如果在r 中找不到对应的特征d t i ，则把特征d t i 作为节点加入到r 中，同时用与上面相同的方法修改权值。并且将在丁和q 同时出 现的