一种基于深网的个性化信息爬取方法

谭涛　谭乐婷　张刚园

摘要：Deep Web蕴含海量的可供访问的信息，是数据库领域的研究热点。目前已有的多数研究主要集中在Deep Web数据集成的技术层面.数据集成虽然满足了对Deep Web信息查询的需要，但这样的查询不能学习用户的兴趣，造成时间和资源的浪费。针对这样的需求，本文将个性化推荐引入到Deep Web的数据查询中，提出了一种结构化数据细粒度管理的用户模型， 和基于树结构的Deep Web爬取方案，用树的遍历方法解决了个性化服务中分布在各个Web数据库中信息爬取的问题。最后通过实验验证了个性化推荐的执行效率及Deep Web爬取的覆盖率。

关键词：Deep Web；个性化爬取；相似度；用户兴趣模型

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）02-0008-03

Abstract： Deep Web is becoming a hot research topic in the area of database. Most of the existing researches mainly focus on Deep Web data integration technology. Deep Web data integration can partly satisfy people's needs of Deep Web information search， but it cannot learn users interest， and people search the same content online repeatedly would cause much unnecessary waste. According to this kind of demand， this paper introduced personalization recommendation to the Deep Web data query， proposed a user interest model based on fine-grained management of structured data and a crawl technology based on the tree structure is presented， with the traversal method of tree to solve the information crawl problems in the personalization service distributed in various web databases. Finally， developed a prototype recommendation system and verified the efficiency and effectiveness of the personalization recommendation and the coverage and cost of Deep Web crawl through the experiment.

Key words： Deep Web； Personalization Crawl； Similarity； User Interest Model

1 概述

互联网的飞速发展使Web成为了海量的信息中心，Web上的网站和网页数量快速增长，其信息量巨大，提供的数据携带着重要的价值，能应用于许多业务领域。这些信息按照蕴含的深度可以将整个网络分为两大部分：Surface Web和Deep Web。那些直接通过超级链接由传统搜索引擎爬取到的页面集合属于Surface Web；而广泛存在于可在线访问的Web数据库中的大量信息，通常传统的搜索引擎是索引不到的，这些内容则属于Deep Web的范畴。随着Web 2.0时代的到来，目前的整个网络至少有65万个数量级的可访问Web数据库，其信息容量覆盖了商业，教育，医学等众多领域，远远超过了Surface Web的信息含量。越来越多的国内外学者投入到对Deep Web的应用研究中。

本文提出了一种结构化数据细粒度管理的用户模型；同时，针对在Web数据库中信息的个性化爬取的问题，采用了树结构模型的爬取技术；并通过原型试验进行了验证。

2 相关原理

网站，超链接，数据库及其查询接口是构成Deep Web的基本要素。网站后台由服务器支持，包含多个网站数据库，用以存放在线访问的信息；同时网站数据库又通过HTML表单查询，表单即为查询接口。个性化服务是依据用户的浏览习惯和历史记录为其后面的访问提供个性化推荐，采用用户模型来描述用户兴趣，进行相似度匹配，将相似度高的信息推荐给用户。用户兴趣不是一成不变的，因此构造用户模型是一个不断学习更新的过程，需要跟踪用户习惯从而及时更新推荐信息。

由于Deep Web数据的动态变化，要从中准确地获取用户所需信息，在数据集成方面的研究得到了研究者们的广泛关注。至今，在该研究领域已经取得了若干成果，比如Deep Web的页面获取[5，6]、查询接口的集成[3，4]、结果数据的抽取与标注[7，8]等。而个性化推荐应用上发展也日趋成熟，比如扩展语义的用户兴趣建模及更新策略[11]，在基于Deep Web数据的个性化推荐应用上，也取得了一定的成果。

3 用户兴趣模型的构建

3.1用户兴趣模型的表示

用户的兴趣特点是多样的，并且是不断变化的，采用感兴趣和不感兴趣两类去刻画，显得过于简单，且不能有效地描述用户多个方面的兴趣特征，尤其对于那些频繁更新的短期兴趣变化，就得不到及时地跟踪更新。考虑到上述因素，本文构建了结构化数据细粒度管理方式。该用户兴趣模型依据领域本体由下到上的归纳合并，形成过程简单，描述准确；同时细化了用户兴趣，通过分门别类地描述降低了不同类别间主题的干扰程度，有利于短期兴趣的更新和推荐模型精度的提高。

本文中，用户兴趣模型被形式化描述为一个五元组M：M={S，K，L，W，T}。其中，K=（Ku，Kc）；S为用户兴趣模型建立的状态，K为对应主题的特征项，由两部分组成：Ku为更新前兴趣模型中的特征；Kc为经过动态更新后的特征。对于初始的用户模型状态S0， 由于没有反馈信息，不需对其进行更新，故Kc 为一个空集；K的语义由L代表，用招聘信息进行描述。如职位，行业，工作经验等；W表示特征项K的权重；T表示更新时间，主要用来帮助分析用户兴趣变化。例如：M={Si，Ki，Li，Wi，Ti}，Si为该用户兴趣模型在动态调整更新中产生的主题状态；对应的特征项集合Ki， Ki =（Kiu，Kic）；L={Li1，Li2，….，Lim}为对应Ki的语义；Wi代表特征Ki的权重，是一个[0，1]之间的值；Ti为对应Si的更新时间。

3.2用户兴趣模式的相似度计算

用户的初始兴趣模型建立起来后，接下来需要解决的就是相似度匹配，及根据匹配结果进行个性化推荐。基本思想是：将高相关度的信息作为种子，在其模式库中利用相似度扩展近邻，在用户兴趣库中寻找类似的兴趣信息，从而提高召回率。我们还尝试了利用统计和机器学习的方法，改进经典的相似度度量，以获得更好的效果。

定义1：用户提交的查询Q：一个Deep Web查询由一组关键字组成，Q={qi|qi∈Q，1<=i<=k}其中，Q为用户查询的关键字集合。

定义2：Web数据库的查询接口WDBI（Web Database Interface）：由属性名、所属数据类型以及相应的候选值构成，定义如下：WDBI={|Ai∈A，ADTi∈ ADT，AVAi∈AVA，1

定义3：给定查询词集合Q1：含m个数据，Q1中各数据的权重分别为：wq1，wq2，….wqm，用户兴趣模型中的状态集合S2：含n个数据， S2中个数据的权重分别为ws1，ws2，…，wsn，将Q1中的数据qi和S2中的数据sj进行相似性匹配，相似性度量方法定义为：Sim（Q1，S2）=（（max[i=1mj=1nWqi*Wsj]）*aij）*vAi其中aij的引入目的是保证wqi 与wsj 只参与一次配对的相似性匹配。当wqi 与wsj 配对时，aij=1；否则aij=0。

其中vAi表示Web数据库查询接口上不同数据类型引起的不同的属性相似性度量值。采用一个由文本关键字组成的向量表示文本类型，令Wi是用户兴趣模型Si基于属性Ai的特征向量，Wj是数据查询基于属性Ai的特征向量，通过向量之间夹角的余弦值表示，公式为：

4 Deep Web的爬取

Web数据库的爬取实质是在找到一个查询词集Q={q1，q2，…，qm}使得查询词的覆盖率在爬取代价<=常数的约束情况下取到最大值。针对查询词的覆盖率及爬取代价定义如下：

定义1.给定查询属性qi和Web数据库WDB，查询属性qi的爬取代价Exp（qi，WDB）定义为：Exp（qi，WDB）= ND（qi，WDB）/k （1）

其中ND（qi，WDB）表示Web数据库中匹配qi的结果记录数，k表示目标Web站点每个查询结果列表页面展示的最大记录数。

定义2.给定查询属性qi和Web数据库WDB，查询属性qi的覆盖率Cov（qi，WDB）定义为：Cov（qi，WDB）= ND（qi，WDB）/NWDB （2）

其中ND（qi，WDB）表示Web数据库中匹配qi的结果记录数， NWDB表示Web数据库中总的记录数。

当查询表单接口中存在一组查询属性集Q={q1，q2，…，qm}，该属性集的覆盖率Cov（q1q2 …qm，WDB）=（ND（q1，WDB）∪…∪ND（qm，WDB））/ NWDB （3）

其中ND（q1，WDB）∪…∪ND（qm，WDB）表示查询属性q1，q2，…qm 的Web数据库所有查询记录的并集的总数。

为了在有限次的查询次数限制下，找到查询词序列使其覆盖率最大化，本文提出了基于树结构的Deep Web数据爬取方法。Web数据库被看做一个关系模式的数据表。考虑如下：一个Web数据库表T：该表由定义在结果属性集AL={al1，al2，…，alm}上的记录集D={d1，d2，…，dn}组成；同时，查询表单接口中存在一组查询属性集Q={q1，q2，…，qm}。用户通过填写表单项指定查询属性的值，这些查询在底层数据库中转化为SQL查询语句。

定义3.Web数据库的划分。将一个Web数据库表T划分为若干非空子集{T1，T2，…，Tm}，T中的每个元组分属于某个子集Ti， 根据等价关系的理论，当Ti∩Tj=且T1∪T2∪…∪Tm =T时，称Ti是T的划分块。基于上述定义，一个Web数据库被划分为若干不相交的块，那么查询结果的元组就分属于其中一个特定的块。

如果结果记录集D的数量非常大，通常会依据某种排序规则进行查询的排序，只返回满足查询条件的前面k条记录（其中k为一个常数，如1000或1500）。这样就存在3种结果返回情况：

（1）当k<|T|时，向上溢出，结果记录不能全部返回；（2）当|T|=0时，向下溢出，结果记录返回为空；（3）当0<|T|

定义4.多叉树。数据库表T的层次树DT（T）是关于查询词的多叉树。构造如下：对一组查询词集Q={q1，q2，…，qm}，一个查询的属性Ai表示树中的节点，该属性的一个属性值通过从该节点出发的边表示。如果属性Ai的属性值的集合为V={v1，v2，…，vn}，Vi称为属性Ai的域，那么属性节点Ai就有n条边。树中的第m+1层为叶子节点。

根据定义4，数据库中每条记录都属于不同的叶子节点，而从根节点到叶子节点的边构成了抽取该记录的结构化查询，在此基础之上，Deep Web数据库的爬取问题就转化为树的遍历问题，即通过遍历树抽取有效叶子节点中的记录。由于考虑从根节点到叶子节点的边，采用深度优先的遍历原则。具体的遍历过程如下：

（1）从根节点中的查询词序列的任意一个查询q0开始，提交给Web数据库WDB；

（2）如果返回的结果集|T|>k（阈值）时，上溢，则继续从下一层选择一个查询，加入到查询路径中组成新的查询；循环该过程，直到找到一个叶子节点；

（3）如果找到一个叶子节点，继续利用其父节点的其他属性值构建遍历的该叶子的兄弟节点；否则，执行（2）；

（4）判断叶子节点的有效性，如果有效，则提取记录并保存，否则，丢弃该叶子节点。

5 个性化信息爬取实验

为了客观评估基于Deep Web的用户个性化爬取方法，我们实现了一个招聘系统的原型，并在真实的Web数据库上进行了验证。针对15个注册用户，每个用户5个初始选择兴趣，从用户的首次查询开始记录并返回数据，对每个兴趣，系统设置从Deep Web数据源获得的最大返回信息条目为30。 在本实验部分，我们使用三个Deep Web数据源： 智联招聘、中华英才网、前程无忧网。进行Deep Web数据的爬取。对用户的查询qi，三个数据源获得的招聘信息条目数为762，905，689条。利用前文所述的推荐原理，对上述的15个注册用户进行了推荐，分两个方面进行：（1）实时推荐：在用户查询qi提交时，在返回结果记录时根据相似度匹配进行了高相似度的信息推荐；（2）定时推荐：在用户预约的固定时间段，当服务器处于闲置状态时，集中进行计算，将爬取到的新的信息反馈给用户。采用信息检索领域的查准率P和查全率R进行衡量。针对15个注册用户，每个用户5个初始选择兴趣，构建了同类兴趣和不同类兴趣的学习，假定15个用户的初始兴趣都有“计算机”，记录了此时15个用户的学习模型，如图1所示；另一方面，每个的用户的兴趣都会发生改变，记录了某个用户UserI的学习模型的改变，如图2所示。

在图1中，对同类兴趣的学习，随着用户兴趣模型不断地累加学习，推荐的准确性和查全率不断提高。由此看出，随着学习的进行，本文的推荐算法能实时更新用户兴趣模型。在图2中，对于不断变化的同一用户兴趣，由于推荐算法是选择用户新近的兴趣主题进行匹配的，因此被模型捕捉到的兴趣主题呈现出分散的趋势。

6 结语

随着Deep Web的迅速发展，大量的Deep Web信息如浩瀚的海洋，往往导致“信息过载”和“信息迷向”，个性化服务能很好地解决这样的问题。针对现有招聘信息服务在面向不同用户的个性化推荐方面的不足，提出了将基于Deep Web个性化推荐应用到招聘服务中的解决方案，使用户在尽可能少的参与下，得到了较好的个性化的服务。但是，该工作还需要进一步的探讨：第一，对于在Deep Web爬取中设置的上溢阈值还需要在理论上做进一步分析；第二，个性化推荐算法的用户满意度和质量，还需要进一步给出更合理的评估方法。

参考文献：

[1] Chang KCC， He B， Li CK， et al.Structured databases on the Web： Observations and implications，” SIGMOD Record， 2004（33）.

[2] BrightPlanet.com， The deep Web： Surfacing hidden value， 2000， http：//brightplanet.com.

[3] 王静帆.基于文本相似度二阶段招聘信息检索[D].清华大学，2007.

[4] 马军，宋玲，韩晓晖，等.基于网页上下文的数据库分类[J].软件学报，2008，19（2）.

[5] He B， Tao T， Chang K C C.Clustering structured Web sources： A schema-based， model-differentiation approach. Springer-Verlag. Heraklion， 2004 [the 9th Intl Conf. on Extending Database Technology].

[6] Peng Q， Meng WY， He H， et al.WISE-Cluster： Clustering e-commerce search engines automatically，ACM Press. Washington， 2004 [the 6th ACM Intl Workshop Conf. on Web Information and Data Management].

[7] Wu WS， Yu C， Doan AH， et al.An interactive clustering-based approach to integrating source query interfaces on the deep Web，ACM Press. Paris， 2004 [the 24th ACM SIGMOD Intl Conf. on Management of Data].

[8] He H， Meng WY， Yu C.WISE-Integrator： An automatic integrator of Web search interfaces for e-commerce，”Morgan Kaufmann Publishers. San Fransisco， 2003 [the 29th Intl Conf. on Very Large Data Bases].

[9] Zhai YH， Liu B.Web data extraction based on partial tree alignment，” ACM Press. Chiba， 2005 [Proc. of the 14th Intl World Wide Web Conf.].

[10] Zhao H K， Meng W Y， Wu Z H， et al. Fully automatic wrapper generation for search engines，ACM Press. Chiba， 2005 [the 14th Intl World Wide Web Conf.] .

[11] 李珊.个性化服务中用户兴趣建模与更新研究[J].情报学报，2010，29（1）.