基于Viterbi算法的网页分类排序动态爬虫策略

张鸿飞 邵玉斌 龙华 杜庆治

摘 要：Viterbi算法是一种基于图的动态规划算法，用于解决最短路径问题。针对当前网站排序算法对网站排名存在忽略网站主题、新站点排名无法超越旧站点等问题，提出了一种改进算法。改进算法利用网站入链数量以及网站內容与主题相关度两个参量，结合Viterbi算法思想，在逐层访问过程中选取综合条件最优的网站，优胜劣汰，形成Viterbi过程，提高分类网站排序的效率和准确性。实验验证了动态爬虫策略的有效性。

关键词：网页排名；爬虫策略；Viterbi算法

DOI：10.11907/rjdk.172674

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）004-0047-04

Abstract：Viterbi algorithm is a map-based dynamical programming algorithm for solving the problem of seeking the shortest route.In this paper，an improved algorithm has been proposed to solve the problems when topics are ignored in page rank and the fact that newer pages cannot defeat the elder pages in ranking.To improve the efficiency and accuracy of classified sites ranking，the new algorithm employs two parameters （link-quantity and relativity of site） by abandoning lower importance sites in drill-down process.The results of the test show that the dynamical strategy can apparently improve efficiency and accuracy of classified sites ranking.

Key Words：web page rank； crawling strategy； Viterbi algorithm

0 引言

随着互联网的飞速发展，网络信息资源急剧膨胀，信息高效、准确、全面采集成为热门的研究课题[1]。其中一个关键问题是如何高效获取分类主题网页排序信息，网络爬虫技术应运而生。互联网是一个以网页为结点、超链接为边的有向图，因此爬虫过程就可以抽象为对这个有向图的遍历过程[2]。爬虫分为两大类：普通爬虫与主题爬虫。PageRank算法[3]与Fish-Search算法[4]是与之对应的两种广泛应用的网页排序算法。

PageRank算法的核心是计算网页质量，通过计算网页被链接的次数，衡量一个网页的质量在整个互联网中的水平，从而根据质量大小找出互联网中受欢迎的网站。但是该算法忽略了网页的主体性，无法针对用户键入的主题获取相关主题的重要网站，并且还存在耗时长的缺点[5]。Fish-Search算法可以满足用户搜索相关主题信息的要求，但是只分析了子链接的文本相关程度，忽略网络链接结构信息，导致结果不准确[6]。

综合以上问题，本文采用基于Viterbi算法[7]的动态分析思想，利用网页入链数量和网页内容与主题相关度两个参量，在逐层访问的过程中选取综合条件最优的网站，优胜劣汰，形成Viterbi过程，将静态的网页评价转化为动态学习过程，提高收集分类主题网站综合重要性最高网页的效率和准确性、全面性。

1 网页分类排序动态爬虫策略模型

1.1 模型框架设计

动态网络爬虫流程如图1所示。

1.2 网页分类排序动态爬虫策略

在互联网中，任一分类主题条件下，一个网页的综合评价主要由两方面决定：入链数和主题相关度[8]。入链数代表网页在该主题互联网环境内的受欢迎程度，入链数越大表示越受欢迎，越容易被访问。主题相关度代表网页在该主题领域内的专业度，相关度越大表示越专业，在该领域越关注专业内容。本文中网页的综合评价公式如下：

其中，f是网页综合评价值；LV为网页链接价值；CV为网页内容价值；φ1与φ2分别为网页链接价值和网页内容价值的权值，设φ1=0.7，φ2=0.3。

1.2.1 网页链接价值与内容价值

网页链接价值计算公式如下：

其中，LN为网页入链数。首先获得网页的入链数，通过反余切函数对入链数进行归一化处理[9]，得到网页链接价值。

网页内容价值是通过TF-IDF算法[10]计算的。

词频统计公式如下：

其中，TF为词频，wi为某词在网页中出现的次数，ws为网页中词的总数。

逆文档频率公式如下：

其中，IDF为逆文档频率，D为文档总数，DW为某词出现的文档数。

网页内容价值计算公式如下：

其中，G为某个词的TF-IDF值，Key为网页中t个关键词的G集合，CV为网页内容价值，n为Key集合中主题词的数量，N为Key集合数量。

1.2.2 维特比过程

Viterbi算法思想为：若每个状态取概率最大路径，则最后得到最优路径。公式体现为：

起始点到每个节点的最短距离结合后则可以得到整个过程的最优路径，也为最大概率路径。将网络爬虫中每一层链接看作一个节点，若每个节点取最大概率网页簇，则可以淘汰评价较低网页，获取评价较高网页，实现最优路径。将利用Viterbi算法的网络爬虫过程称之为维特比过程，如图2所示。

其中，xN为N个爬虫节点，图2中用椭圆圈住的部分为选取的网页簇。

本文涉及到两个评价标准：第一个由式（1）表示，该标准处于网络爬虫结束后，是网页静态评价值；第二个评价标准处在维特比过程中。在维特比过程中，为了体现出网络链接结构信息以及網络结构中父代链接对子代链接的影响，引入了转移转移权值w。将转移权值与静态评价值相乘可以得到带有父代链接信息的综合评价值。

动态网页综合价值评价公式如下：

其中，wi为某节点中第i个网页的权值，fi为该网页的静态综合评价值。Wi为第i节点中的网页作为父代链接的转移权值矩阵，M为父代链接与子代链接的关系矩阵，mij（i∈m，j∈n）的取值为0或1，0代表非从属关系，1指代父子链接关系。Qi为第i个节点中由个网页静态评价值组成的静态评价矩阵，Fi为第i个节点中子代的动态网页评价值矩阵。

2 实验仿真与分析

实验系统使用Python（2.7版本）编程语言，在Eclipse（4.6.3版本）平台下开发，数据库为MySQL（5.0.22版本）。

2.1 参数选择

仿真实验中，为模拟互联网链接环境，通过python语言，在数据库中随机生成父子代网页链接关系，共5 000个网页。在真实网络环境中存在某主题流行网站，频繁被链接。通常情况下，在特定主题领域内，越被频繁链接，越能体现出其重要性。为实现仿真真实网络环境中这一现象，人工设定5个网页（下文称为候选网站）：www1330、www732、www4434、www1643、www3957，被链接频率（下文称为播撒频率）分别为3组，如表1所示。

由于互联网中任意主题的网页链接结构并不是全连通，本算法模拟用户浏览网页的动作具有局部性，这样会导致一次实验并不一定能得到目标网站，因此需要多次实验得到某主题的重要网站。

2.2 评价指标

本次实验通过得到3种不同的计算方式：①利用已知链接结构，算出所有网站的综合评价值并排序，获取前5个网站名；②利用PageRank算法，对已知链接结构进行遍历和迭代，计算出所有网站的PR值并排序，获取前5个网站名；③利用基于Viterbi算法的网页分类排序动态爬虫策略，计算出访问到网页的综合评价值并排序，获取前5个网站名。

将PageRank算法和动态爬虫算法的结果与静态计算出来的结果进行比较，计算查全率，并进行效果比较。查全率公式如下：

查全率=通过动态或PageRank算法得出的网站静态算法得出的网站 （14）

对PageRank算法和动态算法在不同播撒率下计算出结果所用的时间进行比较。

2.3 实验结果

本次实验分为两部分：①设置不同播撒频率（如Test1、Test2、Test3），通过系统中查全率的变化趋势对比不同播撒率的系统学习性能；②设置不同播撒频率，经过多次实验（仿真将Test1、Test2、Test3分别进行50次实验）得到某主题的重要网站，对比播撒频率对于得出结果的影响。

从图3、图5、图7可以看出，随着候选网站播撒频率的提高，动态爬虫系统的学习速率越大，所得结果的查全率越高。并且，当任意特定候选网站的播撒频率较小时，在系统多次学习后，可以得到候选网站外新的目标网站。这说明系统综合分析网站的链接数和网页内容与主题的相关度，得到新的网站综合评价值大于部分候选网站，避免网站评价只受链接数量的影响，得到更加公平、综合的网站。

从图4、图6、图8可以看出，经过大数量试验，系统得到的目标网站越来越接近候选网站，直到候选网站全部选出。

从表2可以看出，Test1、Test2、Test3三种试验中，随着候选网站播撒频率提高，系统单次试验耗费的时间变短。这是因为播撒频率越大，候选网站在互联网中的分布密度越大，促进主题网站链接环的形成。根据图3判断条件，减少学习节点，加速系统单次试验的完成。3种试验所消耗的时间远少于PageRank与全局静态计算所消耗的时间。

3 结语

基于Viterbi算法的网页分类排序动态爬虫策略评价网站在某一主题方面的重要性时，参考网站的入链数量以及网站内容与主题的相关度，综合地避免了PageRank算法上的缺陷。在动态爬虫过程中，结合父代链接的质量，通过转移权值矩阵，将父代链接质量信息带给子代链接，从而影响子代网页在动态学习过程中的动态综合评价值，通过淘汰低评价值，将较高评价值的网页作为下一次的爬虫父代链接，有效地提高了学习效率，减少许多不必要的访问，从而大大减少了时间消耗。在这个过程中，有效解决了PageRank耗时长、Fish-Search忽略链接关系导致查询结果不准确的问题。动态爬虫策略在查全率上比全局静态略低或相等，但是消耗时间大幅度降低，在实际应用中，这对特定主题条件下高效、准确、全面地筛选出重要网站具有实用意义。

参考文献：

[1] 孙立伟，何国辉，吴礼发.网络爬虫技术的研究[J].电脑知识与技术，2010，6（15）：4112-4115.

[2] 周立柱，林玲.聚焦爬虫技术研究综述[J].计算机应用，2005，25（9）：1965-1969.

[3] BRIN S， PAGE L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks and ISDN Systems，1998，30（4）：107-117.

[4] DE BRA P M E， POST R D J. Searching for arbitrary information in the WWW：the fish-search for mosaic[DB/OL].1994-10-06.http：//archive.ncsa.uiuc.edu/SDG/IT94/Proceedings/Searching/debra/article.html.

[5] 钱功伟，倪林，MIAO Y，等.基于网页链接和内容分析的改进PageRank算法[J].计算机工程与应用，2007，43（21）：160-164.

[6] 罗方芳，陈国龙，郭文忠.基于改进的Fish-Search算法的信息检索研究[J].福州大学学报：自然科学版，2013，49（21）：42-45.

[7] 李航.统计学习方法[M].北京：清华大学出版社，2012.

[8] 徐宁.主题爬虫搜索策略及关键技术研究[D].重庆：重庆大学，2015.

[9] 滕明鑫.回归神经网络预测模型归一化方法分析[J].电脑知识与技术，2014，10（7）：1508-1510.

[10] 周源，刘怀兰，杜鹏鹏，等.基于改进TF-IDF特征提取的文本分类模型研究[J].情报科学，2017，35（5）：111-118.

（责任编辑：何 丽）