栾霞+赵晓楠

摘 要： 针对当前常用爬虫爬行策略的不足，提出结合维基百科和网页相似度分析的主题爬行策略。利用维基百科分类树的结构对主题进行描述；下载网页后对网页进行相应处理，结合文本相关性和Web链接分析来计算候选链接的优先级。实验表明，该爬虫搜索结果与主题相关度明显高于传统爬虫，爬虫爬全率有一定提高。该主题爬虫主题描述方法和爬行策略有一定的推广价值，尤其在转基因生物领域中，该爬虫中有一定的创新性。

关键词： 维基百科； 文本相关性； 链接分析； 相似度计算

中图分类号： TN911?34； TP391.4 文献标识码： A 文章编号： 1004?373X（2014）20?0035?03

Topic crawling strategies based on Wikipedia and analysis of web?page similarity

LUAN Xia1， ZHAO Xiao?nan2

（1. The Network Center， 323rd Hospital of Chinese Peoples Liberation Army， Xian 710054， China； 2. Unit 68303 of PLA， Wuwei 733000， China）

Abstract： To overcome the weakness existing in the present topic crawling strategies， a topic crawling strategy based on Wikipedia and web?page similarity analysis is put forward in this paper. The Wikipedia classification tree structure is utilized to describe the topics， and then the downloaded webs are properly handled. Finally， the priorities of the candidate links are calculated in combination with text relativity and analysis of Web links. The experimental result indicates that this new method is better than the traditional crawler in terms of searching results and topic relativity， and its climb rate has been increased. The theme description method and the crawl strategy have a certain promotion value， especially in the field of genetically modified organisms， the crawler has certain innovativeness.

Keywords： topic crawling； Wikipedia； text relativity； link analysis； similarity calculation

0 引 言

近年来随着因特网技术的发展与普及，网络上的信息量越来越大，如何高效地从网络上获得有用的资源变得至关重要。主题爬行器是解决这一问题的技术之一，它是在预定主题的指引下，在网络上选择与主题相关的网页进行爬取，并避免了非相关的网页[1]。传统的爬行策略大多都是通过与关键词机械的匹配，Ehrig等人把本体引入到主题爬行中[2]，利用本体代替了关键词，利用本体中的词汇层次关系计算出网页的主题相关度，但本体的描述方法过于复杂，直接影响了使用效率。在计算网页相关性上，传统主题爬行策略主要有两类：基于网页内容的搜索策略、基于Web链接评价的搜索策略。基于网页内容的搜索策略是对文本中的相似度进行计算，根据相似度确定URL优先级；基于Web链接评价的搜索策略是根据Web页面之间的相互引用关系来确定网页的相似度，从而确定URL优先级队列。基于网页内容的搜索策略虽然简单但忽略了链接结构信息，所以不能很好的预测链接价值；而基于Web链接评价的搜索策略只考虑了网页之间的相互引用，但忽略了页面与主题的相关性，容易出现“出题漂移”的问题[3]，因此不适合挖掘主题资源。本文在综合考虑以上问题的基础上，设计了一种新的主题爬行策略，首先通过维基百科对主题进行描述；对下载的网页进行处理后，综合基于网页内容和Web链接分析来确定URL的优先级。

1 主题爬行策略设计

本文综合维基百科、网页内容和Web链接的方法来设计主题爬行策略，新策略的处理流程图如图1所示。

1.1 基于维基百科的主题描述

在主题爬虫中如果对主题描述太为广泛就会导致搜索的网页量大而相关性就小；如果太具体就会限制爬行范围，虽然搜索的网页相关度高，但是会减少数量[4]。而维基百科[5]是一个动态的、可自由访问和编辑的全球最大的Web知识库。维基百科对其中的每个概念都给出了对应的描述文档，并以分类树[6]的形式组织在一起。分类树中上层为较泛化的概念，下层为较细化的概念。

图1 爬行策略流程图

本文通过维基百科的主题向量来描述主题，约束爬取范围，具体方法为：

（1） 完善分类树。维基百科中对属于某概念的部分下层概念并不收录进分类树中，而出现在描述文档中，这样就导致了分类树不完整，从而影响相关度计算。本文将这些概念提取出来，并加入到分类树中。例如，将出现在“转基因”描述文档中的“遗传工程”加入到“转基因”的分类树中。

（2） 从分类树中提取概念p向上一层的概念集合[Cup]和向下N层概念的集合[Cdown]，组成p的相关概念集合（Relevant Concept Mass，RCM），即[RCMp=Cup?Cdown? p] 。

（3） 对概念p的相关概念集合 中的每个概念[RCMp={c1，c2，…，ci，…，cm}m>0]计算权重 （0

（4） 将主题描述文档经过分词和去除排除词汇后映射到 [VSp]上，即将词语映射到[RCMp]中存在并且在分类树中距离主题概念p最近的概念上，然后统计[VSp]中每个概念在主题描述文档中出现的频率（f），最终计算主题向量T：

[T=wi×fi]

式中：[fi]等于属于[ci]的词的频率之和。

1.2 网页主题相关性计算

主题相关性的计算准确与否直接影响了主题爬行器的性能。本文将下载的网页进行分块后，利用改进的Shark[7]启发式搜索算法，根据爬行过的网页内容和Web链接信息来计算待爬行网页队列中的URL优先级。

1.2.1 网页内容评价

本文设计两个队列来存放待爬行的URL，分别为相关度高的优先队列PQ（Prior Queue）和相关度低的普通队列NQ（Normal Queue）；设计三类阈值来决定待爬行URL属于哪个队列，分别为页面内容阈值上限pageMaxLimit、页面阈值下限pageMinLimit，节点阈值上限nodeMaxLimit、节点阈值下限nodeMinLimit，锚文本的相关度阈值anchorLimit。其中，节点阈值上限即是PQ的最低相关度值，节点阈值下限即是NQ的最低相关度值。而网页和关键词的相似度计算仍采用向量空间模型，计算公式如下：

[simp，k=cosp，k=i=1nwij*wiqi=1nw2ij*i=1nw2iq]

式中：p指当前页面；k指主题；页面内容向量[p=w1q，w2q，…，wnq]；主题向量[k=w1j，w2j，…，wnj]；[w1j]指关键词i在页面j中的权值；[wiq]指关键词i的权值。

根据相关度可以将待爬URL放入相应的队列中，若一个页面的主题相关度大于pageMaxLimit，则将该页面的子页面放入PQ队列中；若一个页面的主题相关度值介于pageMaxLimit和pageMinLimit之间，则根据该页面的子页面的锚文字或URL字符串是否包含关键词向量中的关键词来决定是否将其加入到PQ中，如果满足任何一个条件，则将其加入到PQ中；否则由子节点的相关度值来决定加入队列的类型。

1.2.2 Web链接评价

本文采用Hits[8]算法思想来进行Web链接评价。Hits算法由Kleinberg首先提出，用来判断网页重要性，目前主要用于搜索结果排序。该算法思想是如果一个网页被其他多个网页链接，则比其他链接少的页面重要。因此引入权威（Authority）页面和中心（Hub）页面的概念。即好的Hub页面总是指向许多好的Authority页面；反之，好的Authotirty页面总是被许多好的Hub页面所链接。因此，这种相互加强的关系可以用于发现Authority页面。算法首先利用爬虫从Web上获取与用户查询相关的部分网页构成网络子图G（V，E）（V为网络子图的节点集，E为网络子图的边集），然后通过迭代计算出每个网页的权威值和中心值，迭代步骤如下：

（1） 确定与主题最相关的K（200）个页面，称为root集。

（2） 对于root集中的任一网页p，将p中所包含的链接加入到root集中，最多不超过d（50）个，扩展后称为base集。

（3） 计算base集中每个页面的中心值和权威值，计算方法如下：如果G中有n个节点，则有n维向量a，h，[ai]指节点i的权威值、[hi]指节点i的中心值，设[a0=1]，[h0=1]，然后进行迭代运算：

[ai=i∈Vhi-1， hi=i∈Vai-1]

1.2.3 改进的优先级计算

由于基于内容评价的策略忽略了链接结构信息，在预测链接价值方面存在不足；而Hits算法只考虑了Web页面之间的引用关系，忽略了页面的主题相关性，容易造成主题漂移现象。为了克服二者的不足，本文设计了基于主题敏感的链接分析方法，称为主题Hits。对于中心Hub页面只有当所指网页为主题相关时才能获得相应值，该值由所指页面的Authority值和其主题相关度决定；而Hub值由其链接到的页面的主题相关度决定。因此迭代公式如下：

[ai=i，k∈VPi-1tik=1Pjtoi-1khi-1hi=i∈V&ti-1≥thrai-1×ti-1]

式中：[ti]指网页i的主题相关度；thr为相似度阈值；[Pi]指网页i的链接个数；[oi-1k]指网页i-1的第k个链接所指的网页编号。

2 实验与分析

系统选用Java语言在Eclipse平台下开发。实验环境为微机1台，CPU为Intel Core 2，内存1 GB。软件环境为Windows XP和JDK1.6，选IIS 6.0为Internet为信息服务，数据库选用MySQL。系统选用转基因生物为主题，运行时初始种子网页包括乌有之乡，天涯网：天涯杂谈、经济论坛，凤凰网：辩论会、铿锵杂谈，新华网：发展论坛，人民网：强国论坛，百度贴吧，中华网论坛，腾讯论坛，网易论坛，新浪论坛，搜狐论坛；主要门户网站新闻及相关转载情况，主要门户网站：雅虎、搜狐、新浪、网易、腾讯等。关注人物包括： 金薇（国际先驱报）、张宏良、蒋高明、顾秀林、 郎咸平。根据上述内容，设计了一个主题爬虫，将三种爬行策略进行对比，图2是对比结果，其中，查准率=主题相关的网页数/总网页数。

图2 结果对比

上面的分析可知，新的爬行策略在查询特定主题信息方面比传统的爬行技术有着明显的优势，随着网页数量的增大，新的策略在总体上也存在优势。算法中各种参数的设置和阈值的选择对爬行结果有重要的影响，因此如何确定最有利的参数和阈值有待于进一步研究。

3 结 语

本文研究了主题爬虫中爬虫策略的选取，主要包括对关键字向量的描述、网页优先级计算，设计并实现了一个通用的主题爬虫爬行策略，实验表明本文的方法取得了良好的效果，具有较大的应用价值。

参考文献

[1] 蔡号，贾于波，黄成伟，等.Web日志挖掘中的会话识别算法[J].计算机工程与设计，2009，30（6）：1321?1324.

[2] 戴智利，王鑫昱.一种基于动态时间阈值的会话识别方法[J].计算机应用与软件，2010，27（2）：244?246.

[3] AGGARWAL C C， AL?GARAWI， YU P S. Intelligent crawling on the world wide Web with arbitrary predicates [C]// Proceedings of the 10th International Conference on World Wide Web. New York： ACM， 2001： 89?113.

[4] 史天艺，李明禄.基于维基百科的自动词义消歧方法[J].计算机工程，2009，35（18）：62?65.

[5] Anon. Wikipedia [EB/OL]. [2011?02?16]. http：//wikipedia.jaylee.cn.

[6] 赵飞，周涛，张良，等.维基百科研究综述[J].电子科技大学学报，2010，39（3）：321?334.

[7] 陈竹敏.面向垂直搜索引擎的主题爬行技术研究[D].济南：山东大学，2008.

[8] STRUBE M， PONZETTO S P. Wiki related computing semantic relatedness using Wikipedia [C]//Proceedings of the National Conference on Artificial Intelligence. Cambridge： AAAI Press， 2006： 1419?1424.

图2 结果对比

上面的分析可知，新的爬行策略在查询特定主题信息方面比传统的爬行技术有着明显的优势，随着网页数量的增大，新的策略在总体上也存在优势。算法中各种参数的设置和阈值的选择对爬行结果有重要的影响，因此如何确定最有利的参数和阈值有待于进一步研究。

3 结 语

本文研究了主题爬虫中爬虫策略的选取，主要包括对关键字向量的描述、网页优先级计算，设计并实现了一个通用的主题爬虫爬行策略，实验表明本文的方法取得了良好的效果，具有较大的应用价值。

参考文献

[1] 蔡号，贾于波，黄成伟，等.Web日志挖掘中的会话识别算法[J].计算机工程与设计，2009，30（6）：1321?1324.

[2] 戴智利，王鑫昱.一种基于动态时间阈值的会话识别方法[J].计算机应用与软件，2010，27（2）：244?246.

[3] AGGARWAL C C， AL?GARAWI， YU P S. Intelligent crawling on the world wide Web with arbitrary predicates [C]// Proceedings of the 10th International Conference on World Wide Web. New York： ACM， 2001： 89?113.

[4] 史天艺，李明禄.基于维基百科的自动词义消歧方法[J].计算机工程，2009，35（18）：62?65.

[5] Anon. Wikipedia [EB/OL]. [2011?02?16]. http：//wikipedia.jaylee.cn.

[6] 赵飞，周涛，张良，等.维基百科研究综述[J].电子科技大学学报，2010，39（3）：321?334.

[7] 陈竹敏.面向垂直搜索引擎的主题爬行技术研究[D].济南：山东大学，2008.

[8] STRUBE M， PONZETTO S P. Wiki related computing semantic relatedness using Wikipedia [C]//Proceedings of the National Conference on Artificial Intelligence. Cambridge： AAAI Press， 2006： 1419?1424.

图2 结果对比

上面的分析可知，新的爬行策略在查询特定主题信息方面比传统的爬行技术有着明显的优势，随着网页数量的增大，新的策略在总体上也存在优势。算法中各种参数的设置和阈值的选择对爬行结果有重要的影响，因此如何确定最有利的参数和阈值有待于进一步研究。

3 结 语

本文研究了主题爬虫中爬虫策略的选取，主要包括对关键字向量的描述、网页优先级计算，设计并实现了一个通用的主题爬虫爬行策略，实验表明本文的方法取得了良好的效果，具有较大的应用价值。

参考文献

[1] 蔡号，贾于波，黄成伟，等.Web日志挖掘中的会话识别算法[J].计算机工程与设计，2009，30（6）：1321?1324.

[2] 戴智利，王鑫昱.一种基于动态时间阈值的会话识别方法[J].计算机应用与软件，2010，27（2）：244?246.

[3] AGGARWAL C C， AL?GARAWI， YU P S. Intelligent crawling on the world wide Web with arbitrary predicates [C]// Proceedings of the 10th International Conference on World Wide Web. New York： ACM， 2001： 89?113.

[4] 史天艺，李明禄.基于维基百科的自动词义消歧方法[J].计算机工程，2009，35（18）：62?65.

[5] Anon. Wikipedia [EB/OL]. [2011?02?16]. http：//wikipedia.jaylee.cn.

[6] 赵飞，周涛，张良，等.维基百科研究综述[J].电子科技大学学报，2010，39（3）：321?334.

[7] 陈竹敏.面向垂直搜索引擎的主题爬行技术研究[D].济南：山东大学，2008.

[8] STRUBE M， PONZETTO S P. Wiki related computing semantic relatedness using Wikipedia [C]//Proceedings of the National Conference on Artificial Intelligence. Cambridge： AAAI Press， 2006： 1419?1424.