从主题爬虫角度看数字资源建设

宋  宇

（南京中医药大学图书馆  210046）

摘  要  数字资源建设是图书馆的一个重要研究领域，通过主题爬虫自动收集网络数字资源是数字资源建设的一种重要途径；主题爬虫是主题搜索引擎的重要组成部分，主题搜索算法是主题爬虫的核心；按照评价链接价值方式的不同，对现有的主题搜索算法进行分类，系统分析、比较了每类算法的特点和优缺点。

关键词  数字资源建设  主题爬虫  搜索算法

1  引言

数字资源无论在学生学习还是教师教学、科研方面都有着举足轻重的地位，图书馆作为学校的信息中心，数字资源建设也因此成为图书馆的一个重要工作方面。万维网的迅速发展使它成为数字资源的一个重要来源，但由于它的海量、异构、半结构化、快速增长且动态更新等特点，使得人工手动搜集这些遍布在整个互联网上的数字资源变得费时费力且越来越不现实。能否通过某种技术自动来搜集这些分布在不同服务器上的数字资源呢？主题爬虫的出现解决了这一难题。主题爬虫是主题搜索引擎的一个重要组成部分，是一个网络资源自动发现和搜集程序。以何种策略访问网络，如何在合理的时间限度内，以较少的网络资源、存储资源和计算资源的消耗来获得尽量多的主题数字资源，是制约主题爬虫性能的一个重要因素，也是当今研究的一大热点。国内外学者根据自己的应用需求，结合不同的理论和技术，其中包括信息检索、并行计算、图论、数据挖掘、机器学习、文本分类与聚类、自然语言处理、网络技术等，提出了很多经典的主题搜索算法。本文对这些算法进行分类，系统分析和比较了各类算法的特点和优缺点。

2  主题爬虫搜索算法分类

网络爬虫是一个网络资源的发现与搜集程序，通常从一个“种子集”（如用户查询、种子链接或种子页面）出发，通过HTTP等协议请求并下载网络资源，分析资源并提取连接，然后以循环迭代的方式访问网络。通用搜索引擎的网络爬虫追求的是网络的覆盖率，它们通常采用宽度优先或者深度优先的方式遍历网络，而主题爬虫的目标是使爬行结果的“收获率”最大化，即爬行到尽可能多的主题相关资源，同时使不相关的资源最小化，这就需要根据主题的相关特征，制定相关的启发式策略，来预测链接的价值。不同的主题有不同的内容特征和链接结构特征，它们在网上的分布情况也不尽相同，因此在预测链接的价值时，可利用的信息也不完全相同，也就决定了链接价值的计算方法的不同，不同的链接计算方法就形成了不同的搜索算法。本文把它们分为四类：基于内容的搜索算法、基于链接结构的搜索算法、基于经验信息的搜索算法、基于增量学习的搜索算法。

2.1  基于内容的搜索算法

基于内容的搜索算法主要是根据搜索主题与锚文本和链接周围文本的相似度来计算链接的价值，以此来决定链接的访问顺序，该类算法的代表是Fish算法［1］和Shark算法［2］。

Fish算法是De Bra等人提出的主题抓取算法，他把主题爬虫搜索Web的行为模拟成鱼群在大海中觅食，算法中的每条鱼代表一个URL。当鱼找到食物（发现相关网页）时，它的繁殖能力增强（搜索宽度增加），并且它繁殖的后代寿命与它的相同（搜索深度不变）；当没有发现食物（没有发现相关网页），它的繁殖能力保持不变（搜索宽度不变），并且它后代的寿命缩短（搜索深度-1）；当进入污染区（网页不存在或者读取时间太长），这条鱼死去（放弃对该链接的爬行）。该算法的关键之处是根据输入的种子链接和查寻串等参数，动态的建立一个URL的优先级爬行列表。

Hersovici等人针对Fish算法对链接价值计算时的二值判断过于简单的缺点，对其进行改进，采用模糊相关度的记分方法，提出Shark算法，在该算法中，子节点的链接价值得分受三个因素影响：链接文本、链接周围文本和对父节点的继承，并用向量空间模型来计算页面与用户查询之间的相似度，相似度值取0～1之间的实数。

这类算法模式简便，计算量小，在距离相关页面较近的位置表现出很好的性能；但由于文本信息缺乏“全局性”，存在“近视”的缺点，搜索效率不是太高。

2.2  基于链接结构的搜索算法

基于链接结构的搜索算法根据链接之间的引用关系来确定链接的重要性，其思想来源于引文分析理论，主要利用数学（主要是统计学和拓扑学）和情报学方法，对网络链接的自身属性、链接对象、链接网络等各种现象进行分析，以揭示其数量特征和内在规律的一种研究方法；代表性的算法有两个：Page-Rank［3、4］和HITS［5、6］算法。

Page-Rank算法由Page 和Brin等人提出，是一种全局链接分析、查询主题无关的算法，最初用于搜索引擎对搜索结果的排序，近年来也被用于链接重要性的评价；该算法基于以下两个假设：

假设1：如果页面A有一个超链接指向页面B，那么可能意味着页面A的作者推荐页面B，即认为页面B的质量比较好；

假设2：如果页面A和页面B之间有超链接，那么页面A和页面B可能属于同一主题；

其基本思想是：一个页面被多次引用，则这个页面很可能是重要的；一个页面尽管没有被多次引用，但被一个重要页面引用，则这个页面很可能也是重要的；一个网页的重要性被均分且传递到它所链接的网页上。该算法的核心是PageRank值的计算，页面的PageRank值依赖于该页面的入链数和入链页面的PageRank值。设页面P的PageRank值为PR(p)，则PR(p)才有如下迭代公式计算：

           （1）

其中，T为计算中的页面总量，γ<1是阻尼因子， in(p)是页面p的人链集合，out(r)为页面r的出链集合；如果要计算网页集合中所有网页的PR值，必须利用这个公式反复迭代，初始化每个网页的PR值为1/T，当迭代到一定次数后，PR值会收敛于一个相对固定的值。

HITS（Hyperlink Induced Topic Search）算法由Kleinberg提出，与Page-Rank算法的全局链接分析、查询无关不同，该算法是一种局部链接分析、查询相关的算法，其算法模型由权威性页面（Authority）和中心页面（Hub）组成；权威页面是指与某个查询关键词相关的页面，中心页面是指它的出链页面中包含很多权威页面的页面；每个页面有两个值：Authority值和Hub值，设页面p的这两个值分别为A(p)和H(p)，其计算公式如下：

                                    （2）

其中，B（p）是所有指向页面p的链接集合，F（p）是被页面p所指向的链接集合。

该算法的基本思想是：先用基于文本内容的检索方法得到一个Web子集，称为“根集”（RootSet）R，然后将根集R内各个页面的所有出链页面和入链页面与根集R合并起来，形成基集（BaseSet）B，最后通过公式（2）为基集中的每个页面计算Authority值和Hub值，作为其重要性的依据。

这类算法只考虑链接之间的引用关系，忽略了页面与主题的相关性，容易出现“主题泛化”和“主题漂移”现象，而且计算的复杂度随着链接数量的增长呈指数级增长，因此很少有单独使用该类算法进行主题搜索的，大部分是借用其思想并对其改进后应用于主题搜索。

2.3  基于经验信息的搜索算法

前面两类算法在评价链接价值时，评价的依据主要是在线获得的信息；但近年来通过对Web资源分布特点的研究表明，同一类型网站的构建方式、同一主题网页的组织方式存在某种程度的“相似性”，因此有些学者就提出利用这种“相似性”，先对主题爬虫进行训练，使其具备一些“经验信息”，然后利用这些“经验信息”来确定链接的价值；代表性的算法有基于“巩固学习”［7］的搜索算法和基于“语境图”［8］的搜索算法。

巩固学习是指代理体在一个顺序的任务中，通过接受来自环境的奖励和惩罚来提高自身性能的学习方式，由于它在预测远期回报方面具有优势，所以McCallum等人将其引入主题搜索领域，以解决基于内容的搜索算法存在的“近视”缺点，并将主题爬虫的搜索过程表述为马尔可夫决策过程（markov decisionprocesses, MDPs）［9］，主题爬虫被看作代理体，web页面的动态结构代表状态，主题爬虫对链接的访问代表行动；搜索过程被划分为训练和搜索两个阶段；由于在巩固学习模型中，未来回报价值用Q价值表示，因而这种算法的核心是学习如何计算链接的Q价值；在训练阶段，利用巩固学习算法学习每个链接到Q价值的映射关系，并按Q价值的大小将链接分类，然后用每一类中的链接文本训练一个贝叶斯分类器；在搜索阶段，对每个未知的链接根据其链接文本，用训练好的贝叶斯分类器计算链接落在每一类中的概率，并以此为权值计算链接的Q价值。

基于巩固学习的搜索算法虽然能够确定主题爬虫的搜索方向，但无法估计距离目标页面的距离，为此，Diligenti等人提出通过构建典型页面的“语境图”（Context Graph）来解决这个问题；该算法同样将搜索过程分为训练和搜索两个阶段。在训练阶段，用某个通用搜索引擎获取关于某个主题的相关页面作为种子集，即目标页面的实例集，并从这些种子集出发，通过一些提供引链查询服务的通用搜索引擎检索出所有指向它们的页面，并以这些页面作为第一层次集（表示到目标页面的距离为1），并用这一层次集中的页面文本训练一个贝叶斯分类器C1 ；然后，再从第一层次集中的页面出发，按同样的方法得到第二层次集（表示到目标页面的距离为2）和分类器C2 ；如此重复，直到某个预先指定的层次。由此便可得到一个种子页面集和周围页面之间层次关系的“语境图”。在搜索阶段，面对一个新的页面，用训练好的贝叶斯分类器确定该页面属于哪个层次集，并将其中的超链接也放入相应的层次集中，链接的爬行优先级按照链接距离的大小确定，链接距离越小优先级越大。

这类算法提供了一个与以往算法不同的视角来进行主题搜索，对一些网站结构和网页组织方式相对固定的主题，能大大提高搜索效率；但由于其过度依赖分类器的“经验信息”且预先假定了网站的组织模式，所以这类算法适应性不强，而且由于需要对分类器预先训练，计算量也比较大。

2.4  基于增量学习的搜索算法

前三类算法在评价链接价值时，无论根据“在线信息”还是根据“经验信息”，搜索算法都是静态的，没有学习功能，在搜索的过程中得不到调整；由于网页内容以及不同主题页面的链接结构的多样化，一种算法不可能适合所有的网站，如何让主题爬虫在爬行过程中得到不断的更新和调整，以适应异构的爬行环境成为制约搜索效果的一个瓶颈；在这种想法的启发下，很多学者根据自己的应用需求提出相应具有学习功能的主题搜索算法，由于这些算法都使主题爬虫具有了在线学习功能，我们将这类算法成为基于增量学习的搜索算法。

Aggarwal［10］等人首次提出“智能爬虫”（ Intelligent crawler ）的概念，在该模型中，提出在搜索过程中动态学习超链接结构的方法，通过一个综合的概率模型将网页的内容信息、超链接信息和URL信息有机的结合起来，对候选URL进行更精确的评价和优先级排序。

Chakrabarti［11］等人提出采用两个分类器的结构，一个采用朴素贝叶斯分类的方法，一个采用增强学习的方法，并将Web文档表示成DOM(DocumentObject Model)的形式，第一个分类器的分类结果作为第二个分类器的分类样例，进行在线学习；第二个分类器从Web文档的DOM中获得链接的特征信息，根据这些特征信息，用第一个分类器计算该链接落在每一类中的概率，并以此为权值计算该链接的价值。

Ester［12］等人采用“隧道”技术指导搜索，当搜索位置距离相关页面较远时，将主题范围增大，使搜索器能够跨越无关页面，寻找到正确的搜索方向。

以上几种算法使主题爬虫在搜索时具有了增量学习的能力，但是当需要更新信息再次爬行网络时，还需要重复第一次爬行的过程，效率不是很高；Angkawattanawit［13］等人针对这个问题提出“学习型爬虫”(Learnable Crawler)的概念，使主题爬虫再次搜索时也具有增量学习的能力；他提出要为前一次爬行的结果建立三个知识库，分别用来存放：与主题相关的种子链接地址、与主题相关的关键词、能代表每个页面内容的关键词；为了使种子链接知识库中的链接既具有很高的Authority值，也就有很高的Hub值，采用BHITS算法［14］计算每个连接的Authority值和Hub值；为了建立一个能够准确刻画页面主题的关键词知识库，提取出每个主题相关页面的<Title>和<A>标签值；为了在下载页面之前对页面内容有个准确的预测，在前一次爬行时，把代表页面内容的关键词提取出来；当再次搜索时，用页面内容知识库中的内容和主题关键词知识库中的内容进行比较，以此来计算链接的价值。

这类算法能够根据搜索环境的变化动态调整搜索策略，具有增量学习的功能，适应能力很强，能够极大的提高主题搜索的查准率和查全率。

3  结束语

主题爬虫在搜集网络资源时的自动化和便捷性，使得它在网络数字资源建设方面被广泛应用。主题爬虫除了应用在数字资源建设方面外，在基于Web的行业分析、在线商业竞争分析等方面，都富有应用前景。

参考文献

1  Bra D P, Houben G, Kornatzky Y et al.Information Retrieval in Distributed Hypertexts［C］.In: Porc. of the 4th RIAO Conference，New York,1994,481 -491

2  Hersovici M, Jacov M I, MarekY, et al. The shark-search algorithm――An application: Tailored web site mapping ［J］. Computer Networks, 1998, 317 - 326

3  Page L, Brin S, Motwani R, et al. The PageRank citation ranking: Bringing order to the Web.Technical Report, Database Group, StanfordUniversity, 1998

4  Cho J,Garcia-Molina H, Page L. Efficient Crawling Through URL Ordering［J］.Computer Networks,1998, 161-172

5  Menczer F. Complementing Search Engines with Online Web Mining Agents ［J］.Decision Support Systems, 2003，35 (2):195-212

6  Bharat K,Henznger M R. Improved Algorithms for TopicDistillation in A Hyperlinked Environment［C］. In: Proc.of SIGIR Conference on Research and Development in Information Retrieval, New York, 1998, 104-111

7  Rennie J, McCallum A. Using Reinforcement Learning to Spider the WebEfficiently［C］. In: Proc. of the InternationalConference on Machine Learning (ICML 99), Bled, Slovenia, 1999, 335-343

8  Diligenti M,Coetzee F M, Lawrence S, et al. Focused Crawling Using Context graphs［C］. In: Proc. of the International Conference on Very Large Database(VLDB00), Cairo, Egypt, 2000, 527-534

9  Sutton RS, Barto A G. Reinforcement learning: anintroduction. MA:MIT Press,1998

10  Aggarwal C,Al-garawi F, YU P. Intelligent Crawling on the WorldWide Web with Arbitrary Predicates .In: Proceedings of the 10th InternationalWorld Wide Web Conference(2001).Hong Kong :ACM Press,2001,96-105

11  Chakrabarti S,Punera K et al..Acceleratedfocused crawling through online relevance feedback［C］.In Proceedings of the eleventh international conference on WorldWide Web (WWW2002), 2002, 148-159

12  Ester M, Grob M, Kriegel H. Focused Webcrawling: a generic framework for specifying the user interest and for adaptivecrawling strategies ［C］. In: Proc ofthe International Conference on Very Large Database (VLDB'01), 2001

13  NAngkawattanawit, A Rungsawang.Learnable Crawling: An Efficient Approach to Topic-Specific web ResourceDiscovery［C］. HIS 2002: 573-582

14  Bharat K,Henzinger MR. Improved algorithms for topicdistillation in a hyperlinked environment［C］. In:Proceeding of 21st annual International ACM SIGIR Conference on Research andDevelopment in Information Retrieval. Melbourne,Australia.1998, 104-111

宋  宇  男，1982年生，助理馆员，硕士研究生，发表论文4篇，参与科研项目5项。