一种基于循环策略的深层网页数据获取方法

摘要

本发明公开了一种基于循环策略的深层网页数据获取方法。本发明提出使用循环策略分多次完成对所有数据源的数据获取，当获取某一数据源的效率下降到某一阈值时，停止当前数据源的数据获取，爬虫开始获取下一个数据源的数据，依次类推直到把所有待集成数据源都获取一遍；然后再重复上述过程，直到所有待集成数据源都已达到结束条件。本发明使一部分应该从一些数据源数据获取后期获得的数据，从另一些数据源数据获取的前期或中期获得。与传统一次性穷尽数据获取方法相比，本发明能减少数据源后期的数据获取，降低了数据获取的代价，同时也能减少重复数据的获取，降低数据集成的代价。

权利要求

1.一种基于循环策略的深层网页数据获取方法，其特征在于，包括以下步骤:

步骤一、分别对多个同一领域的数据源中的每一个数据源预设多个不同的查询关键词;

步骤二、依次对每一个数据源进行数据获取，其中，当对所述多个数据源中的第一个数据源进行数据获取时，计算当前数据源中的各查询关键词的查询效率，并按照查询效率对当前数据源中的查询关键词进行排序，根据查询效率从大到小的顺序依次选择各查询关键词对当前数据源进行一次又一次的数据获取，直到所述当前数据源的连续进行的α次数据获取的新数据获取率均不大于一新数据获取率阈值，则中止对当前数据源的数据获取，并对当前数据源的下一个数据源进行数据获取，直到最后一个数据源达到中止;步骤三、检验所述多个数据源的数据获取是否均满足预设结束条件，如果不满足，则重复步骤一，直至所述多个数据源的数据获取均满足预设结束条件，其中，当对所述多个数据源中的任一个数据源满足预设结束条件时，则结束对该数据源的数据获取。

2.如权利要求1所述的基于循环策略的深层网页数据获取方法，其特征在于，

所述步骤二中，对多个数据源中的任一个数据源进行数据获取，通过以下步骤实现，(1)当前数据源预设有n个查询关键词，计算各查询关键词的查询效率，并按照查询效率对查询关键词进行排序，根据查询效率从大到小的顺序选择第一个查询关键词，根据该查询关键词在当前数据源上进行第一次数据获取，所述数据获取过程为:在当前数据源上执行，从当前数据源下载与当前查询关键词匹配的数据记录;(2)重复步骤(1)，且当重复步骤(1)的次数达到rK次之后，其中，rK

1的整数，在根据第rK+1个查询关键词在当前数据源上获得与第rK+1个查询关键词匹配的数据记录之后，再从己经下载的数据记录中提取z个新的查询关键词，使得当前数据源对应的查询关键词的个数为n+z个。

3.如权利要求2所述的基于循环策略的深层网页数据获取方法，其特征在于，所述K值逐渐增大。

4.如权利要求1或2或3所述的基于循环策略的深层网页数据获取方法，其特征在于，所述查询关键词的查询效率Efficient(qi，DBj)与该查询关键词qi在当前数据源DBj上的查询回报率Reward(qi，DBj)成正比，且与该查询关键词qi在当前的数据源DBj上的数据获取代价Cost(qi，DBj)成反比。

5.如权利要求4所述的基于循环策略的深层网页数据获取方法，其特征在于，所述查询关键词qi在当前数据源上的查询回报率Reward(qi，DBj)为在当前数据源DBj中与该查询关键词qi匹配的数据记录数num(qi，DBj)中减去在当前数据源DBj中与该查询关键词qi匹配的己经下载的数据记录数num(qi，DBj，Local)，其中，DBj，local为当前数据源DBj已获取的数据集，在当前数据源中与该查询关键词匹配的数据记录数num(qi，DBj)通过以下方式得到，num(qi，DBj)=P(qi，DBj)×|DBj|，|DBj|为当前数据源的可获取的数据记录的估计值，P(qi，DBj)为在当前数据源的可获取的数据记录的估计值中与查询关键词qi匹配的数据记录数所占的比例，其中，P(qi，DBj)=P(qi，Slocal)，P(qi，Slocal)为在己经下载的数据记录数|Slocal|中与查询关键词qi匹配的数据记录数所占的比例，则num(qi，DBj)=P(qi，Slocal)×|DBj|。

6.如权利要求5所述的基于循环策略的深层网页数据获取方法，其特征在于，还有，P(q[1，...i-1]Slocal)=P(q[1，...i-1]，DBj)，P(q[1，...i-1]，DBj)为在当前数据源的可获取的数据记录的估计值中与己经执行的i-1个查询关键词q[1，...i-1]匹配的数据记录数所占的比例，P(q[1，...i-1]，Slocal)为在己经下载的数据记录数中与己经执行的i-1个查询关键词q[1，...i-1]匹配的数据记录数所占的比例，P(q[1，...i-1]，DBj)=|DBj，local|/|DBj|，|dBj，local]为当前数据源己经下载的数据记录数，则

7.如权利要求5或6所述的基于循环策略的深层网页数据获取方法，其特征在于，查询关键词qi在当前数据源DBj上的数据获取代价Cost(qi，DBj)与在当前数据源DBj中与该查询关键词qi匹配的数据记录数num(qi，DBj)具有线性关系。

8.如权利要求5或6所述的基于循环策略的深层网页数据获取方法，其特征在于，有|Slocal|=Σ|DBj，local|。

9.如权利要求7所述的基于循环策略的深层网页数据获取方法，其特征在于，所述步骤三中，所述预设结束条件为，当对多个数据源中的任一个数据源进行数据获取时，对当前数据源的数据获取次数不小于数据获取次数阈值。

10.如权利要求7所述的基于循环策略的深层网页数据获取方法，其特征在于，所述步骤三中，所述预设结束条件为，当对多个数据源中的任一个数据源进行数据获取时，对当前数据源己产生的数据获取代价Cost(DBj)不小于一数据获取代价阈值，其中

说明书

一种基于循环策略的深层网页数据获取方法

技术领域

[0001] 本发明涉及深层网页数据获取方法，尤其涉及一种基于循环策略的深层网页数据获取方法。

背景技术

[0002] 目前主流搜索引擎还只能搜索Internet表面可索引的信息，在Internet深处还隐含着大量通过主流搜索引擎少量或无法涉及的海量信息，这些信息我们称之为深层网页(Deep Web，又称为Invisible Web或Hidden Web)。Deep Web的信息一般存储在服务端Web数据库中，与静态页面相比通常信息量更大、主题更专一、信息质量和结构更好。为了方便用户快捷高效的使用DeepWeb信息，国内外学者对Deep Web数据集成进行了广泛的研究。Deep Web数据集成的一种方案是与构建传统搜索引擎一样，将Deep Web数据库里内容爬取出来，存储到本地拷贝库中并建立索引，它能在最短时间内响应用户的查询要求。目前这种方案在许多特定领域已成为Deep Web数据集成研究的主流。由于集成系统可能需要集成数十个甚至更多的Deep Web数据源，因此，该方案中一个关键并十分有挑战性问题是如何高效的获取Deep Web数据。

[0003] 目前Deep Web数据集成的实现方法为：首先独立穷尽获取每一个待集成的Deep Web数据源，然后通过数据清洗、实体识别、合并去重等步骤完成获取数据的集成。这种实现方法在数据获取方面主要存在两个缺陷：第一，每个数据源数据获取的后期代价十分巨大，花费较大的代价仅仅获取极少的新数据，同时数据集成时需要处理来自不同数据源的大量重复数据，数据集成的代价也非常巨大；第二，每个数据源数据获取独立进行，爬虫主要依据该数据源已获取数据的统计信息进行查询选择，由于统计信息缺乏和查询候选池有限，该方法存在查询选择的准确性较差、数据获取覆盖率较低等问题。

发明内容

[0004] 针对上述技术问题，本发明设计开发了一种基于循环策略的深层网页数据获取方法。

[0005] 本发明的一个目的在于，提供一种基于循环策略的深层网页数据获取方法。集成系统中待集成的数据源之间并不是相互独立的，而是相互关联。数据源之间数据相互覆盖，甚至一些数据源之间相互依赖。具体而言，就是在集成环境中，从某一数据源获取的数据，可能从另一个或一些待集成的数据源中获取，因此从某一数据源数据获取后期获取的数据，可能出现在另一个或一些数据源数据获取的前期或中期。在这一研究发现的基础之上，本发明提出使用循环策略分多次完成对所有数据源的数据获取，当获取某一数据源的效率下降到某一阈值时，中止当前数据源的数据获取，爬虫开始获取下一个数据源的数据，依次类推直到把所有待集成数据源都获取一遍；然后再重复上述过程，直到所有待集成数据源都已达到结束条件。本发明使一部分应该从一些数据源数据获取后期获得的数据，从另一些数据源数据获取的前期或中期获得。与传统一次性穷尽数据获取方法相比，本发明能减少数据源后期的数据获取，降低了数据获取的代价，同时也能减少重复数据的获取，降低数据集成的代价。

[0006] 本发明的另一个目的在于，提供一种基于循环策略的深层网页数据获取方法。集成系统中待集成的数据源之间并不是相互独立的，而是相互关联。数据源之间数据相互覆盖，甚至一些数据源之间相互依赖。基于上述情况，还发现了这样的规律，即同领域的数据源之间具有相似的属性值并且这些属性值也具有相似的分布特征。本发明利用集成系统已获取的数据动态构建知识，并在集成系统动态知识的基础之上进行查询关键词的选择。本发明丰富了查询选择的知识，提高了查询选择的准确性，同时扩展了查询候选池，可提高数据获取的覆盖率。在使用循环策略进行数据获取时，对于每个数据源可以多次利用丰富后的集成系统动态知识进行查询选择，从而有效率提高查询选择的准确性，提高数据获取的效率。

[0007] 本发明提供的技术方案为：

[0008] 一种基于循环策略的深层网页数据获取方法，包括以下步骤：

[0009] 步骤一、分别对多个同一领域的数据源中的每一个数据源预设多个不同的查询关键词；

[0010] 步骤二、依次对每一个数据源进行数据获取，其中，当对所述多个数据源中的第一个数据源进行数据获取时，计算当前数据源中的各查询关键词的查询效率，并按照查询效率对当前数据源中的查询关键词进行排序，根据查询效率从大到小的顺序依次选择各查询关键词对当前数据源进行一次又一次的数据获取，直到所述当前数据源的连续进行的α次数据获取的新数据获取率均不大于一新数据获取率阈值，则中止对当前数据源的数据获取，并对当前数据源的下一个数据源进行数据获取，直到最后一个数据源达到中止；

[0011] 步骤三、检验所述多个数据源的数据获取是否均满足预设结束条件，如果不满足，则重复步骤一，直至所述多个数据源的数据获取均满足预设结束条件，其中，当对所述多个数据源中的任一个数据源满足预设结束条件时，则结束对该数据源的数据获取。

[0012] 优选的是，所述的基于循环策略的深层网页数据获取方法中，

[0013] 所述步骤二中，对多个数据源中的任一个数据源进行数据获取，通过以下步骤实现，

[0014] (1)当前数据源预设有n个查询关键词，计算各查询关键词的查询效率，并按照查询效率对查询关键词进行排序，根据查询效率从大到小的顺序选择第一个查询关键词，根据该查询关键词在当前数据源上进行第一次数据获取，所述数据获取过程为：在当前数据源上执行，从当前数据源下载与当前查询关键词匹配的数据记录；

[0015] (2)重复步骤(1)，且当重复步骤(1)的次数达到rK次之后，其中，rK＜n，r为大于等于1的整数，在根据第rK+1个查询关键词在当前数据源上获得与第rK+1个查询关键词匹配的数据记录之后，再从已经下载的数据记录中提取z个新的查询关键词，使得当前数据源对应的查询关键词的个数为n+z个。

[0016] 优选的是，所述的基于循环策略的深层网页数据获取方法中，所述K值逐渐增大。

[0017] 优选的是，所述的基于循环策略的深层网页数据获取方法中，所述查询关键词的查询效率Efficient(qi,DBj)与该查询关键词qi在当前数据源DBj上的查询回报率Reward(qi,DBj)成正比，且与该查询关键词qi在当前的数据源DBj上的数据获取代价Cost(qi,DBj)成反比。

[0018] 优选的是，所述的基于循环策略的深层网页数据获取方法中，所述查询关键词qi在当前数据源上的查询回报率Reward(qi,DBj)为在当前数据源DBj中与该查询关键词qi匹配的数据记录数num(qi，DBj)中减去在当前数据源DBj中与该查询关键词qi匹配的已经下载的数据记录数num(qi,DBj，Local)，

[0019] 在当前数据源中与该查询关键词匹配的数据记录数num(qi,DBj)通过以下方式得到，

[0020] num(qi，DBj)＝P(qi,DBj)h|DBj|，

[0021] |DBj|为当前数据源的可获取的数据记录的估计值，P(qi，DBj)为在当前数据源的可获取的数据记录的估计值中与查询关键词qi匹配的数据记录数所占的比例，

[0022] 其中，P(qi,DBj)＝＝P(qi，Slocal)，P(qi，Slocal)为在已经下载的数据记录数|Slocal|中与查询关键词qi匹配的数据记录数所占的比例，

[0023] 则num(qi，DBj)＝P(qi,Sloocal)×|DBj|。

[0024] 优选的是，所述的基于循环策略的深层网页数据获取方法中，还有，

[0025] P(q[1，…i-1],Slocal)＝P(q[1，…i-1],DBj)，P(q[1，…i-1],DBj)为在当前数据源的可获取的数据记录的估计值中与已经执行的i-1个查询关键词q[1，…i-1]匹配的数据记录数所占的比例，P(q[1，…i-1],Slocal)为在已经下载的数据记录数中与已经执行的i-1个查询关键词q[1，…i-1]匹配的数据记录数所占的比例，

[0026] P(q[1，…i-1],DBj)=|DBj,local|/|DBj|，|DBj，local|为当前数据源已经下载的数据记录数，

[0027] 则

[0028] 优选的是，所述的基于循环策略的深层网页数据获取方法中，查询关键词qi在当前数据源DBj上的数据获取代价Cost(qi,DBj)与在当前数据源DBj中与该查询关键词qi匹配的数据记录数num(qi，DBj)具有线性关系。

[0029] 优选的是，所述的基于循环策略的深层网页数据获取方法中，有|Slocal|=∑|DBj,local|。

[0030] 优选的是，所述的基于循环策略的深层网页数据获取方法中，所述步骤三中，所述预设结束条件为，

[0031] 当对多个数据源中的任一个数据源进行数据获取时，对当前数据源的数据获取次数不小于数据获取次数阈值。

[0032] 优选的是，所述的基于循环策略的深层网页数据获取方法中，所述步骤三中，所述预设结束条件为，

[0033] 当对多个数据源中的任一个数据源进行数据获取时，对当前数据源已产生的数据获取代价Cost(DBj)不小于一数据获取代价阈值，其中，

[0034] 本发明所述的基于循环策略的深层网页数据获取方法具有以下有益效果：

[0035] (1)在集成环境中，从某一数据源获取的数据，可能从另一个或一些待集成的数据源中获取，因此从某一数据源数据获取后期获取的数据，可能出现在另一个或一些数据源数据获取的前期或中期。在这一研究发现的基础之上，本发明提出使用循环策略分多次完成对所有数据源的数据获取，当获取某一数据源的效率下降到某一阈值时，中止当前数据源的数据获取，爬虫开始获取下一个数据源的数据，依次类推直到把所有待集成数据源都获取一遍；然后再重复上述过程，直到所有待集成数据源都已达到结束条件。本发明使一部分应该从一些数据源数据获取后期获得的数据，从另一些数据源数据获取的前期或中期获得。与传统一次性穷尽数据获取方法相比，本发明能减少数据源后期的数据获取，降低了数据获取的代价，同时也能减少重复数据的获取，降低数据集成的代价。

[0036] (2)根据同领域数据源之间所存在的下述规律，即同领域的数据源之间具有相似的属性值并且这些属性值也具有相似的分布特征。本发明利用集成系统已获取的数据动态构建知识，并设计基于集成系统动态知识的查询选择方法。本发明丰富了查询选择的知识，提高了查询选择的准确性，同时扩展了查询候选池，可提高数据获取的覆盖率。在使用循环策略进行数据获取时，对于每个数据源可以多次利用丰富后的集成系统动态知识进行查询选择，从而有效率提高查询选择的准确性，提高数据获取的效率。

附图说明

[0037] 图1为基于循环策略的多个数据源的数据获取的流程示意图。

[0038] 图2为基于动态知识的多个数据源中一个数据源的数据获取的流程示意图。

[0039] 图3为本发明所述的基于循环策略的深层网页数据获取方法与现有技术的独立数据获取策略的深层网页数据获取方法的效率对比情况，图3(a)为针对第一类测试数据的效率对比情况，图3(b)为针对第二类测试数据的效率对比情况，▲代表基于循环策略的深层网页数据获取方法，●代表现有技术的独立数据获取策略的深层网页数据获取方法。

[0040] 图4为本发明所述的基于循环策略的深层网页数据获取方法的基于动态知识的查询选择方法与现有技术的查洵选择方法的效率对比情况，图4(a)为针对第一类测试数据的效率对比情况，图4(b)为针对第二类测试数据的效率对比情况，▲代表基于动态知识的查询选择方法，■代表现有技术的查询选择方法。

[0041] 图5为DK的查询间隔次数K对基于循环策略的深层网页数据获取方法的数据获取策略的影响情况，其测试数据为第一类测试数据，图5(a)为针对第一种情况，对应DK为空的情况，图5(b)为针对第二种情况，对应DK较丰富的情况，▲代表K＝1的情况，■代表K＝10的情况，代表K＝30的情况。

具体实施方式

[0042] 下面结合附图对本发明做进一步的详细说明，以令本领域技术人员参照说明书文字能够据以实施。

[0043] 如图1所示，本发明提供一种基于循环策略的深层网页数据获取方法，包括以下步骤：

[0044] 步骤一、分别对多个同一领域的数据源中的每一个数据源预设多个不同的查洵关键词；

[0045] 步骤二、依次对每一个数据源进行数据获取，其中，当对所述多个数据源中的第一个数据源进行数据获取时，计算当前数据源中的各查询关键词的查询效率，并按照查询效率对当前数据源中的查询关键词进行排序，根据查询效率从大到小的顺序依次选择各查询关键词对当前数据源进行一次又一次的数据获取，直到所述当前数据源的连续进行的α次数据获取的新数据获取率均不大于一新数据获取率阈值，则中止对当前数据源的数据获取，并对当前数据源的下一个数据源进行数据获取，直到最后一个数据源达到中止；

[0046] 步骤三、检验所述多个数据源的数据获取是否均满足预设结束条件，如果不满足，则重复步骤一，直至所述多个数据源的数据获取均满足预设结束条件，其中，当对所述多个数据源中的任一个数据源满足预设结束条件时，则结束对该数据源的数据获取。

[0047] 如图2所示，所述的基于循环策略的深层网页数据获取方法中，所述步骤二中，对多个数据源中的任一个数据源进行数据获取，通过以下步骤实现，

[0048] (1)当前数据源预设有n个查询关键词，计算各查询关键词的查询效率，并按照查询效率对查询关键词进行排序，根据查询效率从大到小的顺序选择第一个查询关键词，根据该查询关键词在当前数据源上进行第一次数据获取，所述数据获取过程为：在当前数据源上执行，从当前数据源下载与当前查询关键词匹配的数据记录；

[0049] (2)重复步骤(1)，且当重复步骤(1)的次数达到rK次之后，其中，rK＜n，r为大于等于1的整数，在根据第rK+1个查询关键词在当前数据源上获得与第rK+1个查询关键词匹配的数据记录之后，再从已经下载的数据记录中提取z个新的查询关键词，使得当前数据源对应的查询关键词的个数为n+z个。

[0050] 上述已经下载的数据记录指的Slocal。

[0051] 所述的基于循环策略的深层网页数据获取方法中，所述K值逐渐增大。

[0052] 所述的基于循环策略的深层网页数据获取方法中，所述查询关键词的查询效率Efficient(qi，DBj)与该查询关键词qi在当前数据源DBj上的查询回报率Reward(qi,DBj)成正比，且与该查询关键词qi在当前的数据源DBj上的数据获取代价Cost(qi,DBj)成反比。

[0053] 所述的基于循环策略的深层网页数据获取方法中，所述查询关键词qi在当前数据源上的查询回报率Reward(qi,DBj)为在当前数据源DBj中与该查询关键词qi匹配的数据记录数num(qi，DBj)中减去在当前数据源DBj中与该查询关键词qi匹配的已经下载的数据记录数num(qi，DBj,Local)，在当前数据源中与该查询关键词匹配的数据记录数num(qi,DBj,)通过以下方式得到，

[0054] num(qi，DBj)＝P(qi,DBj)×|DBj|，

[0055] |DBj|为当前数据源的可获取的数据记录的估计值，P(qi，DBj)为在当前数据源的可获取的数据记录的估计值中与查询关键词qi匹配的数据记录数所占的比例，其中，[0056] P(qi，DBj)＝P(qi，Slocal)，

[0057] P(qi，Slocal)为在已经下载的数据记录数|Slocal|中与查询关键词qi匹配的数据记录数所占的比例，则

[0058] num(qi，DBj)＝P(qi,Slocal)×|DBj|。

[0059] 所述的基于循环策略的深层网页数据获取方法中，还有，

[0060] P(q[1，…i-1],Slocal)＝P(q[1，…i-1],DBj)，

[0061] P(q[1，…i-1],DBj)为在当前数据源的可获取的数据记录的估计值中与已经执行的i-1个查询关键词q[1，…i-1]匹配的数据记录数所占的比例，P(q[1，…i-1],Slocal)为在已经下载的数据记录数中与已经执行的i-1个查询关键词q[1，…i-1]匹配的数据记录数所占的比例，[0062] P(q[1，…i-1],DBj)=|DBj,local|/|DBj|，

[0063] |DBj,local|为当前数据源已经下载的数据记录数，则

[0064]

[0065] 所述的基于循环策略的深层网页数据获取方法中，查询关键词qi在当前数据源DBj上的数据获取代价Cost(qi,DBj)与在当前数据源DBj中与该查询关键词qi匹配的数据记录数num(qi,DBj)具有线性关系。

[0066] 所述的基于循环策略的深层网页数据获取方法中，有|Slocal|=∑|DBj，local|。

[0067] 所述的基于循环策略的深层网页数据获取方法中，所述步骤三中，所述预设结束条件为，当对多个数据源中的任一个数据源进行数据获取时，对当前数据源的数据获取次数不小于数据获取次数阈值。

[0068] 所述的基于循环策略的深层网页数据获取方法中，所述步骤三中，所述预设结束条件为，当对多个数据源中的任一个数据源进行数据获取时，对当前数据源已产生的数据获取代价Cost(DBj)不小于一数据获取代价阈值，其中，

[0069] Deep Web数据获取方式：结构化的Web数据库可看做一张关系数据表DB，DB包含的数据记录为T＝{t1，t2，...tx}，每条记录包含y个属性A={a1,a2,…ay}。获取Deep Web中的数据只能通过从查询接口上提交查询，从返回结果页面获得Deep Web中包含该查询的记录集，对于一个潜在的查询qi，R(qi)表示在DB上执行查询qi所返回的记录集，即DB中所有包含qi的记录集合(假设不考虑返回记录限制的情况)，R(qi)为T的一个子集。

[0070] Deep Web数据获取代价模型：爬虫在DB上执行查询qi和获取qi所返回的记录集都需要一定的代价，如：时间、网络带宽等。对于一个查询qi，使用Cost(qi，DB)表示爬虫在DB上执行查询qi和获取qi所返回的记录集的各种代价总和(即：Deep Web数据获取代价)。对于结构化的Web数据库，数据获取的代价主要包括：爬虫提交查询到站点的查询代价(也即在数据源上执行一个查询关键词的代价)，爬虫与Web服务器交互的代价(也即在执行查询关键词时与数据源的交互代价)，爬虫下载结果页面的代价。

[0071] 交互次数和查询提交次数是不一样的，每个结果页面通常包含固定k个与查询关键词匹配的数据记录，每次初始连接得到至多k个数据记录。例如，在图书数据库中有104个图书记录匹配属性值“书名，Java”，并且每个结果页面显示10(k＝10)个数据记录，则获取所有结果记录集的总交互次数为[104/10]＝11次。即每获取一页的数据记录，都需要和Web服务器交互一次。执行查询qi的过程实际上就是指在数据源上执行查询关键词qi，并寻找与查询关键词qi匹配的数据记录的过程，也就是在数据源进行数据获取的过程。

[0072] 定义爬虫提交一次查询的代价为Cq，爬虫与Web服务器交互一次的代价为Cm，爬虫下载一个结果页面的数据记录的代价为Cd。对于一个查询qi，在DB上执行查询qi和获取qi所返回的记录集的各种代价总和Cost(qi,DB)可表示为：

[0073] Cost(qi,DB)＝Cq+CmM+CdN (1)

[0074] 其中Cq，Cm，Cd为常量，M为爬虫与Web服务器交互次数，N为爬虫需下载的结果页面数量。

[0075]

[0076] 其中num(qi,DB)为DB中所有与查询关键词qi匹配的数据记录数，k为一个结果页面最多可显示的数据记录数。如果DB存在最大返回记录限制，则L为DB的一次查询的最大返回记录数。爬虫需下载的结果页面数量N和爬虫与Web服务器交互次数M相等。

[0077] 单个Deep Web数据源的数据获取：对于一个Deep Web数据源DBj，DeepWeb数据获取问题可形式化定义为：寻找一组查询关键词集合Qn={q1，q2，，qn}使得P(q1∨q2∨…∨qn，DBj)值最大，其约束条件是 其中tj为爬虫获取DBj中数据可使用的最大代价。对于一个给定的查询关键词qi，P(qi,DBj)表示在DBj上执行查询关键词qi，与查询关键词qi匹配的数据记录数在当前数据源DBj的可获取的数据记录数中所占的比例。
在本发明中，一个数据源DBj的可获取的数据记录数可以表示为|DBj|，实际上是一个估计值，是一个数据源的估计大小。

[0078] 面向Deep Web数据集成的数据获取：对于一个集成系统I，S={DB1,DB2,…,DBl}为I待集成的所有Deep Web数据源的集合，面向DeepWeb数据集成的数据获取可形式化定义为：需找一组查询关键词集合Q={Q1,Q2，...,Ql}使得P(Q1∨Q2∨...∨Ql)最大，其约束条件是 其中T为集成系统I的可使用的最大代价，Qj为获取第j个数据源所提交的查询集合Qj={q1,q2，...，qn}，P(Qj)为P(q1∨q2∨...∨qn，DBj)。

[0079] 对于一个集成系统I，S={DB1,DB2,…,DBl}为I待集成的所有Deep Web数据源的集合。针对现有技术的Deep Web数据集成实现方法在数据获取方面存在的缺陷，本发明基于同领域数据源之间的关联关系，提出使用循环策略分多次完成数据源的数据获取。该过程为，首先对S中的数据源，根据其可能对集成系统I贡献的效用大小进行排序。效用评价标准可以根据数据源的大小、数据源的数据质量等，或者是由这些量组成的一个函数。然后从S中排在第一位的数据源开始进行数据获取，数据获取的策略是当前数据源的特定特征达到阈值，则中止获取当前数据源，根据达到阈值的特征判断当前数据源是继续保持在S中等待下一次获取，还是从S中删除当前数据源，结束当前数据源的获取任务；然后爬虫开始获取下一个数据源的数据，依次类推把S中的所有数据源都获取一遍；再重复上述过程，直到S为空，S中的数据源都达到获取结束条件。

[0080] S中的数据源具有不同的特征，例如：数据源的大小、数据源的质量等；另外数据源之间的覆盖率也各不相同，一些数据源之间覆盖率较高、而另一些覆盖率较低，甚至一些可能是包含另一些。因此不同的数据源对集成系统的贡献效用是有差异的。为了提高数据集成的效率，本发明在开始数据获取前首先利用排序算法SourceSort()对S中的数据源按它们可能对集成系统I贡献的效用大小进行排序，SourceSort()是一种数据源排序方法，该方法主要依据数据源可能给集成系统贡献的效用大小进行排序，这里的效用是指数据源能为集成系统新增新数据量与新数据质量(数据的完整性、一致性和冗余性等)的函数。

[0081] 完成对S中数据源的排序之后，算法开始进行数据获取，在一个数据源上的一次数据获取流程为：首先由SelectQuery()选择一个查询关键词qi，然后Query(qi,DBj)在DBj上执行查询qi，并返回结果页面记录集R(qi)，接着Dowload(R(qi))实现从结果页面下载数据记录到本地DBj，Local；最后把该次数据获取的代价Cost(qi,DBj)计入获取DBj已耗费的总代价Cost(DBj)。数据获取的过程为不断重复该流程直到满足循环停止条件。

[0082] 对于该算法停止条件的设置非常重要，该算法的停止条件可以分为两类。第一类为中止条件：对数据源DBj的数据获取暂时停止，仍然保留在S中，等待下一次获取；第二类为结束条件：结束数据源DBj的数据获取，并将当前数据源从S中删除。

[0083] 中止条件设置为，对于数据源DBj，如果SelectQuery()连续进行的α次数据获取的新数据获取率都不大于新数据获取率阈值θ，则说明SelectQuery()在目前的知识下已经不能进行有效查询选择，继续对DBj进行获取的代价将非常高，需要暂时停止对DBj的数据获取，等待下一次循环时再继续获取。在下一次获取时则可利用丰富后的动态知识进行查询选择。

[0084] 结束条件设置为，当对数据源DBj进行数据获取时，DBj的特征满足以下3种结束条件之一，即可从S中删除DBj，结束对DBj的数据获取。

[0085] (1)如果从DBj中已获取的数据量|DBj,Local|达到DBj估计大小的一定比例，即：|DBj,Local|≥|DBj|×ω，则结束DBj的数据获取。其中，ω可以设为95%。|DBj,Local|代表了DBj已经获取的数据记录数。

[0086] |DBj,Local|≥|DBj|×ω说明集成系统已经获取了DBj的绝大部分数据，剩下的少量数据对集成系统的影响较小，并且获取这部分数据的付出的代价也可能较高，所以可以结束DBj的数据获取。

[0087] (2)如 果 集 成 系 统 I分 配 给DBj 的 数 据 获 取 资 源 耗 尽，即：则结束DBj的数据获取。

[0088] (3)如果DBj被数据获取的次数uj达到阈值β，即uj≥β，则结束DBj的数据获取。

[0089] 对于数据源DBj经过了β/K次查询候选池扩展和统计知识丰富的数据获取后，从DBj中继续获取新数据的可能性也较小，同时获取数据的代价随着数据获取的次数增加也不断增大，因此可以结束DBj的数据获取。

[0090] 在基于循环策略的数据获取方法中，利用动态知识可以进一步提高数据获取的效率。集成系统的知识实际包括查询候选池以及查询关键词的统计知识两部分内容，动态知识的形成过程则是指集成系统的知识并不是固定不变的，而是可以随着集成系统的数据获取过程不断更新上述查询候选池和查询关键词的统计知识。查询候选池用来形象描述查询关键词，其中包括有集成系统所对应的若干查询关键词。根据上文，本发明中的查询候选池为Q={Q1,Q2，...,Ql}。

[0091] 根据同领域数据源之间的相关性，S中数据源之间通常具有相似的属性值并且这些属性值也具有相似的分布特征，例如：在图书领域不同图书销售网站(此处图书销售网站就是一种数据源)所销售的图书具有一定的相似性，并且图书书名出现的频率也是相似的。本发明提出利用集成系统已获取的数据构建动态知识，并在基础系统动态知识的基础之上进行查询选择。与现有技术相比，上述过程使爬虫获得更广泛的分类属性值，扩展了查询候选池，从而能避免信息孤岛问题，提高数据获取的覆盖率；同时动态知识使爬虫获得了更全面和时新的统计知识，利用动态知识可提高查询回报率估算的准确性，从而提高查询选择的效率。查询选择过程是指在对一个数据源进行数据获取过程中，对查询关键词的选择过程。

[0092] 对于一个集成系统I，S{DB1,DB2,…,DBl}为I待集成的所有Deep Web数据源的集合，在数据获取进行到某一阶段时I已获取的数据集合为：SLocal＝DB1,Local∪DB2,Local∪…∪DBl，Local，DBj，Local为集成系统I从DBj中已获取的数据，集成系统的动态知识(Dynamic Knowledge)DK可定Н为：从SLocal中得到的查询关键词以及该查询关键词在SLocal中出现的概率对的集合，即：DK＝{i|}，其中，qi代表查询关键词，P(qi，SLocal)表示qi出现在SLocal中概率——也就是在|SLocal|中与qi匹配的数据记录数所占的比例，|SLcal|为集成系统已获取的数据记录数。

[0093]

[0094] 随着数据获取工作的进行，SLocal中的数据会动态变化，因此，DK也需要根据SLocal保持动态更新，以便为查询选择提供更时新和全局的知识。理论上集成系统每执行一次查询(数据获取)都可能使SLocal变化，SLocal的每一次变化又都可能使DK改变。例如：执行一次查询qi(数据获取)都有可能改变DK中已有查询关键词qi的P(qi，SLocal)和产生新的查询关键词，因此理论上每执行一次查询的数据获取都需要更新DK。对于集成系统I和SLocal，当一个查询关键词qi被选择在数据源DBj上执行Query(qi,DBj)，返回数据记录集合为R(qi)，更新DK主要有两个方面的工作：

[0095] (1)统计分析是否有新的查询关键词产生，如果有新的查询关键词qnew产生，则向DK添加查询关键词qnew和qnew在SLocal中出现的概率对，新的查询关键词qnew在SLocal中出现的概率可由以下公式得到：

[0096]

[0097] (2)更新DK中所有的已有查询关键词在SLocal中出现的概率。对于DK中任一查询关键词qi，qi在SLocal中出现的概率更新可由以下公式计算：

[0098]

[0099] 但是如果每一次查询执行都动态维护DK，那么代价将十分巨大，随着系统集成数据规模的增加，维护DK的代价将变得无法接受。在实际应用中本发明发现对于一个集成系统I，当I所集成的数据达到一定规模S’后(即DK中知识达到一定规模后)，一次查询甚至若干次查询的执行对DK的更新结果对查询选择的影响非常小。基于上述发现本发明使用一种优化方式实现更新DK。当集成系统I所集成的数据达到一定规模S’之前，对每一次查询都更新DK。当集成系统I所集成的数据达到一定规模S’之后，执行K次查询后再更新DK，K可以随S’的变化而变化，从而在不影响查询选择效率的前提下，尽可能减小更新DK的代价。

[0100] 公式(4)可重写为：

[0101]

[0102] 公式(5)可重写为：

[0103]

[0104] 其中，R(q[1，2，...,K])为{q1,q2，...，qK}在DBj上执行所返回结果的集合。

[0105] 基于动态知识DK，爬虫拥有了一个更大的查询候选池和更全局、更时新的统计知识。对于当前数据源DBj，DK中的查询关键词可分为两类Qj，DB和QDK。Qj,DB为包含在DK中，且已出现在DBj，Local中的查询关键词；QDK为包含在DK中，但没有在DBj，Local中出现的查询关键词。对于一个查询关键词qi是否能被选择执行，一个重要的因素是执行qi能获得的查询回报，这里的查询回报指在当前数据源DBj上执行查询关键词qi所能够获取的新数据记录的数量，下面将讨论如何估计Qj,DB和QDK这两类查询关键词的查询回报率。

[0106] Qj,DB查询回报率的估计：使用从集成系统的动态知识DK来估算qi∈Qj，DB的回报率，查询回报估算公式如下：

[0107] Reward(qi，DBj)=num(qi,DBj)-num(qi，DBj，Local) (8)

[0108] num(qi，DBj,Local)是DBj，Local中与qi匹配的数据记录数，num(qi，DBj)是在数据源DBj中与qi匹配的数据记录数。

[0109] num(qi，DBj)在qi在DBj上执行之前是未知的。

[0110] num(qi，DBj)＝P(qi,DBj)×|DBj|，

[0111] |DBj|为当前数据源的可获取的数据记录的估计值，P(qi，DBj)为在当前数据源的可获取的数据记录的估计值中与查询关键词qi匹配的数据记录数所占的比例——查询关键词qi出现在DBj中的概率。

[0112] 下面我们讨论如何估算num(qi,DBj)。由于S中数据源之间通常具有相似的属性值，并且这些属性值也具有相似的分布特征，在不考虑偏差的情况下，假定qi出现在DBj的概率P(qi，DBj)等于qi在Slocal上的概率P(qi,SLocal)，P(qi，SLocal)能从DK中得到。

[0113] P(qi，Slocal)=num(qi,Slocal)/|Slocal|，

[0114] 基于这个假定，所有在DBj上已执行的i-1个查询q[1，2，...，i-1]出现的在DBj上的概率P(q[1，…i-1],DBj)与其在Slocal上的概率P(q[1，…i-1],Slocal)也相同。因此使用如下公式估算num(qi，DBj)：

[0115]

[0116] QDK的查询回报率的估计：现在讨论如何估算qi∈QDK的回报率(查询qi未出现在DBj,Local国)，则有num(qi,DBj,Local)=0。本发明假设P(qi，DBj)等于P(qi,SLocal)。因此Reward(qi,DBj)的计算公式如下：

[0117] Reward(qi，DBj)=P(qi，SLocal)×|DBj| (10)

[0118] 其中P(qi,SLocal)为查询关键词qi出现在SLocal中的概率，P(qi,SLocal)能从DK中得到。

[0119] Deep Web数据集成爬虫的目的是在一定资源约束下尽可能多的获取数据。基于这个目的，爬虫进行查询选择时必须考虑以下两个因素：第一，查询关键词qi在DBj上执行的查询回报率；第二，执行查询关键词qi获取DBj中的数据需要花费的代价。例如：存在两个查询关键词qa和qb，如果它们获取DBj的数据时需要花费的代价相同，但是qa比qb的查询回报率更高，qa应先于qb被选择；同理，如果qa和qb具有相同的查询回报率，但qa比qb花费更少的代价，qa应先于qb被选择。因此查询关键词qi的查询效率可由如下公式计算：

[0120]

[0121] Reward(qi，DBj)为查询关键词qi在DBj的查询回报率，Cost(qi,DBj)表示执行查询关键词qi获取DBj中数据需要花费的代价。

[0122] 因此，Efficient(qi)估算单位代价情况下qi能返回多少新数据记录。根据上述函数，爬虫能够估计每一个查询关键词qi的效率，从而选择一个具有最高效率的查询关键词首先执行。查询选择算法采用贪婪方法每次都选择具有最高潜在效率的查询。

[0123] 为了验证本发明方法的有效性，本发明使用两类测试数据：一类是人工构建的模拟结构化Deep Web数据源，另一类是真实的Deep Web数据源。第一类人工构建专利领域的模拟Deep Web数据源是已从七国二组织获取的63.32万条专利数据，构建5个专利领域的Deep Web数据源。为了模拟真实世界的同领域数据源之间存在一定的相关性(相互覆盖)，又避免大量覆盖导致的实验代价过大的问题，设置每个数据源随机从63.32万条数据中抽取15万—25万条不等的数据记录。同时，本发明也在真实Deep Web数据源上验证本发明方法的有效性，从BrightPlanet公司的CompletePlanet网站的音乐领域中选取5个Deep Web数据源(music.aol.com，www.chicagoreader.com，www.onlinemusicdatabase.com，www.Sheetmusicplus.com，www.bestwebbuys.com)。对于这些数据源大小通过现有技术中Arjun Dasgupta 等提出的数据源大小估计方法进行估算。

[0124] 本发明主要从以下几个方面验证本发明提出的方法的性能：(1)本发明的循环数据获取策略(Cycle-A)与现有技术中集成的独立数据获取策略(Separate-A)性能比较；(2)基于集成系统动态知识的查询关键词的选择方法(QuerySelect-DK)与现有技术中的查询关键词的选择方法(QuerySelect-T)的比较；(3)更新DK的查询间隔次数K对查询关键词的效率的影响。

[0125] 实施例一

[0126] 为了比较本发明提出的循环数据获取策略(Cycle-A)和现有技术中数据集成的独立数据获取策略(Separate-A)的性能，集成系统分别使用两种策略集成上述两类测试数据的数据源。

[0127] 根据Deep Web数据获取代价模型，针对上述两种策略，对于同一类测试数据的多个数据源而言，当数据源覆盖率相同时，查询提交次数越少，DeepWeb数据获取的代价也越小，证明该方法的数据获取效率越高。数据源覆盖率指的是对集成系统中的多个数据源所获取的数据占多个数据源估计大小的比例。

[0128] 因此在方法实施时不考虑数据获取的代价因素，通过比较两种策略数据获取时的数据源覆盖率与查询提交次数的关系，考察循环数据获取策略的效率。在本实施例中，设置中止条件为α=5，结束条件ω=95%，β＝4，数据获取时代价条件不受限制。

[0129] 图3给出了两种数据获取策略的效率对比，图3(a)为针对第一类测试数据的效率对比，图3(b)为针对第二类测试数据的效率对比。从图3(a)可见，对于第一类测试数据，Cycle-A的数据获取效率明显优于Separate-A。随着查询提交次数的增加，Cycle-A的效率优势越来越明显。当数据源覆盖率达到80%时，Separate-A策略的查询提交次数几乎为Cycle-A策略的5倍；当数据源覆盖率达到95%时，Cycle-A策略的查询提交次数约为4900次，而Separate-A策略的查询提交次数达到了13000次左右。从图3(b)中可以发现对于第二类测试数据具有相同的规律。这是因为Cycle-A能在较大程度上避免Separate-A在每个数据源数据获取后期效率迅速降低的情况，同时也得益于基于动态知识的查询选择方法。

[0130] 实施例二

[0131] 假设集成系统已获取了某一类测试数据的n-1个数据源的数据，通过比较分别使用基于集成环境动态知识的查询选择方法(QuerySelect-DK)与传统方法
(QuerySelect-T)获取第n个数据源的数据的效率，测试本文提出方法的效率。

[0132] 本实施例中实验具体设置为：对于专利和音乐领域，系统已经分别集成了两个测试数据的3个数据源，现在分别使用上述两种查询关键词的选择方法获取第4个数据源的数据。

[0133] 对于QuerySelect-DK方法的动态知识DK已根据集成系统集成的前3个数据源的数据构建。图4给出了两种查询选择方法分别获取两类测试数据中的第4个数据源的效率，其中，图4(a)为针对第一类测试数据的效率对比，图4(b)为针对第二类测试数据的效率对比。。从图4(b)可见，对于第二类测试数据，QuerySelect-DK方法提交大约1200次查询已获取第一类测试数据的第4个数据源的大约95%的数据，而QuerySelect-T方法在相同的查询提交次数的情况下，仅仅获得第4个数据源的大约70%的数据。QuerySelect-DK方法提交大约400次查询时，就可获得第4个数据源的大约80%的数据。从获得相同的数据源覆盖率需要提交的查询次数方面比较，QuerySelect-DK方法的效率也明显优于现有技术。对于第一类测试数据的实施情况与第一类测试数据的实施情况类似。因此上述过程说明在相同的查询回报率估计方法和不考虑代价的前提下，基于QuerySelect-DK方法比QuerySelect-T方法具有更高的效率。

[0134] 实施例三

[0135] 为了评估更新DK的查询间隔次数K对数据获取效率的影响，本实施例分别在DK为空和DK较丰富的两种情况进行，比较不同情况下更新DK的查询间隔次数K对数据获取效率的影响。第一种情况中，初始DK为空，从第一类测试数据的第1个数据源开始数据获取；第二种情况，已经获取第一类测试数据的前2个数据源的数据并构建了DK，开始获取第3个数据源的数据。本实施例分别比较K为1，10，30时的查询选择的效率，实施情况如图5所示，图5(a)对应第一种情况，图5(b)对应第二种情况。

[0136] 从图5(a)可见，在集成系统的数据获取的初期(初始DK为空的情况)，此时K＝1的数据获取效率明显高于K＝10和K＝30的情况，并且K值越大数据获取效率越小。在大约400次查询提交之前，随着查询提交次数的增加，不同K值的数据获取效率之间的差距逐步扩大，但扩大的幅度越来越小；在大约400次查询后三种K值对应的数据获取效率之间的差距已基本稳定，不再扩大，说明在大约400次查询之后三种K值的数据获取效率已基本相当。

[0137] 上述过程说明在DK较小时，为了高效的数据获取需要使用较小的K值，虽然这样DK的更新频率较高，但是由于此时DK较小，更新DK的代价也能接受。当随着DK的不断丰富，K的大小对数据获取效率的影响将逐步减小。从图5(b)可见，第二种情况下三种K值的数据获取效率基本相同，说明在此时这三种不同K值对数据获取效率的影响基本相同。因此，通过本实施例可得出随着集成系统的数据获取的进行，可以逐步调整K值，使集成系统在不太影响数据获取效率的前提下，尽量降低更新DK的代价。

[0138] 针对集成系统的Deep Web数据获取问题，本发明提出了一种新的数据获取策略。根据同领域数据源之间的关联性，使用循环数据获取策略减少了数据源后期数据的获取，较大程度上避免了现有技术中数据获取后期的代价巨大的问题；同时，利用集成系统的动态知识进行查询选择，扩展了查询候选池，丰富查询选择的知识，从而提高了数据获取的数据源覆盖率和查询选择的准确性。综上所述，本发明的Deep Web数据获取方法能够很好地满足DeepWeb数据集成的需要，与现有技术相比，具有较高的数据获取效率。

[0139] 尽管本发明的实施方案已公开如上，但其并不仅仅限于说明书和实施方式中所列运用，它完全可以被适用于各种适合本发明的领域，对于熟悉本领域的人员而言，可容易地实现另外的修改，因此在不背离权利要求及等同范围所限定的一般概念下，本发明并不限于特定的细节和这里示出与描述的图例。