简析主题网络爬虫搜索策略

简析主题网络爬虫搜索策略

◆牛率仁

重点分析了爬虫的策略设计以及网页主题的相关度算法研究等，分析了各个算法的实现方法以及优缺点等。

1　宽度遍历策略

宽度优先搜索[1]（Breadth-First-Search）简称 BFS，网络爬虫从初始 URL集合中，按照访问的层次逐个遍历网页，当遍历完当前层的网页包含的所有URL链接完，然后才接着对下一层级的页面进行遍历，不断断的递归这个过程，直到完成爬取任务，或者到达遍历的停止条件等。因此，宽度遍历也称为按层遍历。

宽度遍历策略是网络爬虫的常用的搜索策略。其有一个明显的优点是其保证了对当前层次的页面的优先处理，避免了当遇到一个非常深的层次分支的时候，陷入到无穷尽的页面链接中无法跳转出来。宽度优先策略实现简单，也符合通用爬虫的特点，即尽可能抓取到更多的资源。其明显的一个缺陷是有可能会丢失一些比较深层次的有效资源。

2　Fish-Search搜索策略

Fish-Search算法，顾名思义也称为鱼群算法，是De Bra等几个人上世纪90年代提出来的。在该算法中，将网络爬虫比喻成在大洋中鱼群，而网页资源则是鱼群追逐的食物。网页的链接则可以看作连接不同食物之间的通道；所以，当鱼一旦找到了食物，对应着爬虫网络的主题网页，马上快速的繁殖，鱼群的数量迅速增加，通过这样的方式找寻到更多的的食物，如果食物不够多或者减少，则会导致附件的鱼群的数量迅速的减少，甚至灭亡。

3　Shark-Search搜索策略

Shark-Search算法主要是在Fish-Search算法的做了一些改进，获得了更好的效果，其改进主要有两点：（1）相比较于Fish算法只用0和1是表示页面与主题的相关度，在同类别中无法更细的区分谁的优先级更高一些。Shark-Search算法使用0-1之间的连续值作为页面的相关度表示，用sim（a，b）来表示，表示页面与主题的相关程度。

（2）Fish-Search算法，页面下的链接直接继承了其父节点potential-score

（3）Shark-Search算法除了继承该值之外，同时还考虑了链接的上下文信息，锚文本信息等，因此其算法在相关度方面有较大的提升。

从上述的基于内容的搜索策略中可以看出，其考虑的主要是页面的主题相关度，根据相关的程度来确定爬虫的优先级，但其往往忽略了链接的本身的重要性，另外，这两者的策略都倾向于在初始种子页面的徘徊，最终可能会导致得到的局部的最优解，而不是全局性的。

下面将讲述两个基于页面链接的爬虫策略。

4　PageRank算法

PageRank算法由谢尔盖和布林在1998年提出的。之后他们以此为基础，完成了当前最成功的谷歌搜索引擎。从本质上来看PageRank是一个链接分析算法。该算法给所有的网页的页面设计了一个权值，作为该页面的重要性的衡量。

在该算法中，如果网页A有一个链接指向页面2，则网页2会得到一定的权重加权，该值取决于的网页1的重要性。若网页1有较高的影响力，如点击率高，有多个页面指向它等，则网页2可以得到较高的分。PageRank算法的策略是如果一个页面被很多

其他的页面所引用，那么这个页面可能是有较高影响力的；如果这个页面虽然没被很多页面所引用，但是它被一个重要的的页面所引用，那么该页面仍然可能是重要的。互联网的页面的重要性正是通过这种引用的关系进行共享和传播的。

PageRank的算法概念上非常清晰，也比较符合用户浏览互联网的习惯，比如我们认为，同一条消息在新浪上发布，以及在一家不知名的小网站发布，器可信度是不一样的。

一个网页的PageRank的值由其它引用该网页的所有网页的PageRank的值的平均值所确定。该值取决于以下三个重要的因素：

（1）引用该网页的页面的数量

（2）引用该网页的页面的PageRank值（3）该网页所包含链接数量

PageRank这种算法其中一个优点是可以有效防止作弊。因为一个网页通常无法将该页面的链接偷偷放到别名的网页中，因此PageRank值往往可以用来更好的表示网页的重要与否。此外，PageRank能全面的反应总体的情况，不存在近视的问题。

但是，所有网页的PageRank值是离线计算的，在爬虫的时候，是无法得到精确的pageRank值的，则只能使用近似的方法得到其pageRank方法，比如只用已抓取页面的来计算，但是一般存在数据的冷启动的问题等。

5　HITS算法

美国康奈尔大学的Kleinberg教授首先提出HITS（Hyperlink-induced Topic Seaerch）网页分类方法，该算法的思想在于认为在海量的Web页面中，按照性质可分为权威页面（Authority）和中心页面（Hub）。

使用HITS算法可以有效的评估网页的质量，页面的的权威度与自身的内容的信息相关，若被引用得次数越多，便认为其权威程度越高，这些页面如同现在新浪微博，腾讯等大网站的页面，均属于权威页面。而中心页面则与页面本身的提供的链接的质量相关，若其引用的的页面包含的高质量的链接越多，则认为其链接权威度越高，而也可认为是中心页面。

一般情况下，可认为一个权威性高的网页应该被很多中心页面所引用，同样的，一个中心网页应该包含的链接均是指向权威页面。对于爬虫系统的页面来说，权威页面和中心页面是相互依存，互相影响的关系，而这也是本算法的核心基础。

对于每个页面来说，每个页面的Authority和hub属性是互定义的，向该页面的hub值计算得到的值就是Authority值，而该页面所有链接的authority值求和即是Hub值。

PageRank算法和HITS算法是两个主要的算法超链接的评价策略。 PageRank具有一维的PageRank值网页排名，但HITS有两个参数来评价一个页面。HITS算法只处理了相对WEB文档中的一个子集，而PageRank则针对整个的WEB页面进行了计算。

引用：

[1]吴明礼，施水才.一种结合超链接分析的搜索引擎排序方法.计算机工程，2014（15）：9-15.

（平顶山市工业学校 河南 平顶山 467000）

‖167‖