一种改进Shark-Search的主题爬虫算法

仇磊， 娄渊胜， 常民

(河海大学 计算机与信息学院,南京 211100)

一种改进Shark-Search的主题爬虫算法

仇磊， 娄渊胜， 常民

(河海大学 计算机与信息学院,南京 211100)

针对Shark-Search算法在主题爬虫中对网页全局性的考虑不足，利用PageRank算法计算待下载URL的权威值来弥补这种不足，提出了Shark-PageRank算法，依据锚文本、锚文本邻近的文本和网页的权威值来权衡URL的价值。实验结果显示，在单位时间里，该算法提高了主题爬虫的速度，并且随着网页数量的增加，该算法具有良好的准确率和稳定性。

主题爬虫； Shark-Search算法； PageRank算法； 垂直搜索

0 引言

主题爬虫作为垂直搜索引擎的核心部分,其算法的优劣对搜索引擎的查全率和查准率有直接的影响[1]。主题爬虫即是过滤与预设定主题无关的链接，依据网页文本和链接分析等算法，将与主题相关的链接放入待抓取的URL队列中，然后按照可行的过滤策略从队列中选取下一步要抓取的网页链接，并重复上述的步骤，直到爬虫系统的设置的前提满足时停止。

主题爬虫的核心部分是爬虫策略，高效的爬虫策略算法可以提高主题爬虫的性能[2]。目前围绕主题爬虫策略算法的问题，国内外已有大量研究。文献[3]将相同类的所有链接锚文本作为该类的描述文本，用描述文本计算与主题的相似程度。文献[4]从链接块、链接，以及网页页面本身3个方面上对网页的相似程度分别进行计算，然后将三者按照不同权重结合，从而确定当前页面主题的相似程度。文献[5]把Shark-Search算法融入基于Web链接评价的策略，判断网页文本的相似度，有效的解决了Hits算法的”主题漂移”问题。文献[6]针对多媒体的网页链接特点，采取“先搜索、后判断”的搜索过程，对Shark-Search主题搜索算法在待爬行链接、搜索宽度以及选取策略上进行改进。

在上述工作的基础上，文中将Shark -Search 算法与 PageRank算法结合，提出一种新的爬虫策略算Shark-PageRank，该算法克服了Shark-Search算法在网页全局性的不足，融入了网页的权威值来衡量URL的价值来筛选合适的资源，不仅提高了爬虫的查准率，也保持了爬取资源的稳定性，更提高了爬虫系统整体性能。

1 主题爬虫算法

1.1 Shark-Search算法

Shark-Search算法[3]是基于Fish-Search算法提出的，它属于启发式算法，对Fish-Search[4]算法的重要改进就是利用相似性引擎对网页进行模糊评分。他对当前页面的每一个子链接进行预测，Shark-Search算法采取相似性计算其指向的子页面与主题的相关程度。

子链接的预测相关度由以下公式(1)计算:

Potential_score(child_url)=α*Inherited(child_url)+(1-α)*Neighborhood(child_url),(0≤α<1)

(1)

在上面的公式中，inherited ()是从父节点继承的相关性评分，由主题内容和父网页的内容的相似程度计算得到，如式(2)所示[6]。

(2)

其中σ为衰减因子且在0到1之间，Φ为相关度阈。邻近链接neighbor ()的评分是与锚文本本身及其周围的文字有关联。这些锚文本与主题q的相似性程度计算[7],如式(3)。

neighbor(child_url)=β*sim(q,a)+(1-β)*sim(q,a_text)

(3)

1.2 PageRank算法

PageRank算法[5]是一种评价页面重要度的算法，它阐述了一个全局的评价模式。它通过页面间的链接关系计算页面的重要程度，一个页面的重要程度依赖于其他网页指向它的链接[8]，同时它指向其它页面的链接也影响了其它页面的重要度。所以，当计算当前网页的所有入度和出度时，页面K的PageRank值计算,如式(4)[6]。

(4)

其中A(k)代表直接指向页面k的网页的集合，即网页k的度，PageRank(k)代表页面k的PageRank数值，N(a)网页a正向链接数量；PageRank(a)/N(a)表示网页a将自己的PageRank值平均分配给自己页面指向的的链接。

2 Shark-PageRank算法

2.1 Shark-PageRank算法的基本思想

Shark-Search算法在相关页面集比较近的地方搜索时表现出良好的性能，且效率稳定，但对于全局文本来说，其缺乏“全局性”。然而PageRank算法是一种基于迭代的算法，紧密链接区域中的页面的权值必定增加，故可以将PageRank值作为网页全局性的衡量，可以克服Shark-Search算法在网页全局性考虑的不足。因此将Shark-Search和PageRank算法合并融入主题爬虫中，提出Shark-PageRank算法。算法主要分为以下三部分。

(1) Shark-Search算法部分：利用相似性引擎对网页与主题的相关性进行模糊评分，对当前页面的每一个子链接进行预测，Shark-Search算法采取相似性计算其指向的子页面与主题的相关程度。

(2) Shark-PageRank算法融合部分：在进行主题相似性计算的同时，引入PageRank值的计算，将权重值作为全局衡量的标准。

(3) PageRank算法部分：通过页面之间的链接关系来定义页面的重要性，计算URL链接的权重值。

2.2 Shark-Search与PageRank算法的衔接

文中将Shark-Search 算法与 PageRank算法结合，在计算待下载URL的价值时除了依据锚文本及其附近的文字、网页内容，外还引入了PageRank值综合计算出的网页的权威值，既弥补了前者Web全局性的不足，又消除了后者容易产生”主题漂移”的现象。计算待下载URL值，为式(5)。

Potential_score(child_url)=A*Inherited(child_url)+B*Neighborhood(child_url)+C*PageRank(child_url)

(5)

其中系数A,B,C为正数且满足A+B+C=1,其他参数的意义同前。

如果将延伸后的所有连接都放入下载队列一定导致队列过于臃肿从而影响整体爬虫的效率,所以本文将设定一个阈值β,只有隐藏价值大于β的网页链接才能加入下载队列中。β按如下计算得出式(6)。

(6)

2.3 Shark-PageRank具体算法描述

根据上文中Shark-PageRank算法的基本思想给出具体算法，描述如下[11]：

算法:主题爬虫算法(Shark-PageRank算法)输入:与主题相关的集合短语或者词语(topic),起始URL输出:有价值的URL集合1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:Shark_PageRank(theme,starting_url){foreachlink(starting_url){ set_depth(link,d) Enqueue(frontier,link);} while(visited0){ foreachoutlink(extract_link(doc)){ score=a*neighbourhood_score(outlink)+b*inherited_score(outlink)+c*PageRank(outlink)if(doc_score>=β){ set_depth(outlink,d);} else{ set_depth(outlink,depth(link)-1)} enqueue(frontier,outlink,score); } } }}

3 实验仿真与结果分析

为了验证算法的有效性，采用python的Urllib 2模块和第三方的BeautifulSoup模块在baike.baidu.com进行相关的主题。实验运行环境为:Windows8.1，JetBrains PyCharm 5.0.4，Mysql5.5，Intel core i5，8GB内存。分别利用Shark-Search算法，PageRank算法和Shark-PageRank算法对爬虫程序实现解析控制，爬取与某主题相关的网页，运行结果，如图1所示。

图1表明，任务数量和执行时间之间存在正相关关系，当任务数大于600时，随着任务数量的增加，执行时间速度明显增快，因此，有效爬取数量的多少影响执行时间的效率。同时说明Shark-PageRank算法在相同执行时间的条件下，有效爬取的数量上明显优于Shark-Search算法和PageRank算法。因此，Shark-PageRank算法有效的提高了主题爬虫的速度，如图2所示。

图1 三种算法随下载有效数量变化的时间

图2 三种算法随下载数量查准率

图2表明，当下载数量不断的增加，PageRank算法的查准率一直下降，那是因为随着所抓取的网页数量的增加，“主题漂移”现象越来越重，Shark-Search 随着下载网页数量的增加，它的查准率趋于稳定，但没考虑网页的全局性，整体网页的内容考虑不足，查准率不高，而新算法Shark-PageRank随着下载网页增多，保持了Shark-Search算法的稳定的同时也具有了较高的查准率。

4 总结

本文在深入研究 Shark-Search算法和PageRank后，针对前者对网页全局性考虑的不足和后者随着网页数量的增加，网页内容易产生“主题漂移”的现象，提出了将两种算法相结合的思路即文本相似度和链接价值度相结合的爬行策略，结果表明新策略效果明显，新算法在提高查准率的同时也增加了算法的复杂度。怎么在提高查准率的同时降低复杂度，将是下步研究的重点方向。

[1] Almpanidis G， Kotropoulos C， Pitas I. Combining text and link analysis for focused crawling—An application for vertical search engines[J]. Information Systems， 2010， 32(6):886-908.

[2] 沈盈洪, 丰翔龙, 黄荣游. 基于网页聚类的搜索结果优化算法研究[J]. 计算机应用, 2010, 30(S1):51-53.

[3] Hersovici M， Jacovi M， Maarek Y S， et al. The shark-search algorithm. An application: tailored Web site mapping[J]. Computer Networks & Isdn Systems， 1998， 30(1-7):317-326.

[4] LUO Fang-fang, CHEN Guo-long, GUO Wen-zhong. An improved “Fish-search” algorithm for information retrieval[J]. Journal of Fuzhou University, 2005, 34(2):523-528.

[5] 罗林波， 陈绮， 吴清秀. 基于Shark-Search和Hits算法的主题爬虫研究[J]. 计算机技术与发展， 2010， 20(11):76-79.

[6] 杨格兰， 涂立. 基于主题相关性和链接权重的PageRank算法[J]. 华中科技大学学报:自然科学版， 2012(S1):300-303.

[7] 黄英铭. Web结构挖掘及HITS算法分析[J]. 计算机与现代化, 2007(7):23-25.

[8] Luo L， Wang R B， Huang X X， et al. A Novel Shark-Search Algorithm for Theme Crawler[C]// Proceedings of the 2012 international conference on Web Information Systems and Mining. Springer-Verlag， 2012:603-609.

[9] Page L. The PageRank Citation Ranking: Bringing Order to the Web[C]// Stanford InfoLab. 1998:1-14.

[10] 李立耀. 基于页面链接结构Page Rank算法的改进——有向访问模型[J]. 福建师大福清分校学报， 2006(2):4-10.

[11] Prakash J， Kumar R. Web Crawling through Shark-Search using PageRank[J]. Procedia Computer Science， 2015， 48:210-216.

An Improved Shark-Search Algorithm for Theme Crawler

Qiu Lei,Lou Yuansheng,Chang Min

(College of Computer and Information,Hohai University,Nanjing 211100,China)

In the theme crawler, the Shark-Search algorithm is insufficient to consider the global web page. In this paper, the PageRank algorithm is used to calculate the URL’s authority to make up for this shortcoming, and Shark-PageRank algorithm, which adopts the anchor text, the context near the anchor text and authoritative value of web page to measure the value of the URL, is proposed in this paper. The experiment results show that the algorithm improves the speed of the theme crawler in the unit time,and with the increase of the number of pages the algorithm has good accuracy and stability.

Theme crawler; Shark-Search algorithm; PageRank algorithm; Vertical search

国家科技支撑计划项目(2013BAB06B04) 江苏水利科技项目(2013025)

仇 磊(1992-),男,硕士研究生,研究方向:数据挖掘,南京 211100 娄渊胜(1968-),男,博士,研究方向:服务调度，云计算,南京 211100 常 民(1989-),男, 硕士研究生,研究方向:数据挖掘,南京 211100

1007-757X(2017)02-0019-03

TP391.3

A

2016.03.25)