一种可扩展、可定制的主题集中式万维网爬虫设置方法

摘要

一种可扩展、可定制的主题集中式万维网爬虫系统设置方法，包括分析网页的相关度和网页扩展，以Rc (P)表示网页与初始网页集的相关度，利用Ra (P)可以建立这样的预测机制，因为Ra (P)可以通过分析有超链指向P的网页得到；以向量空间模型扩展。每次网页扩展都将会进行一次计算调整，但计算只发生在所涉及到的网页，排序调整也可控制在未被访问的若干网页中。当对某种主题比较关注，或者人们要获取较大量的某领域下的万维网信息，一类为主题集中式的万维网爬虫可以自动的在网上爬寻、搜集与主题相关的网页资源。本发明在万维网爬行策略中综合了网页相关度和重要度的评价，策略具有可调节的灵活性；该爬虫系统充分体现了可扩展性。

说明书

一、技术领域

本发明涉及万维网(WWW)上对网页资源进行自动收集的机制。特别涉及对可扩展、可定制的主题集中式万维网爬虫设置方法。

二、技术背景

万维网爬虫(Web Crawler)是一种在万维网上可以对网页资源进行自动收集的软件。它主要应用在以下几个方面：

●为搜索引擎对万维网上的网页资源进行索引提供网页来源。

●协助特定用户收集特定的网页集。

●协助人们进行对万维网现状进行统计分析，等等

人们的目的不同，会导致对所使用的万维网爬虫的要求不同。人们会有这样的需要，即对某种主题比较关注，或者人们要获取较大量的某领域下的万维网信息，这种情况下，就需要有一种特定的爬虫来满足这种需要。

在各种爬虫中，有一类爬虫称为主题集中式的万维网爬虫。它根据以上人们的需要而产生。它根据一个初始网页集，利用初始网页集中的超链，采取一定的策略，专门在网上爬行与初始网页集比较相关的网页，而对于不怎么相关的网页，它会舍弃。

关于这类爬虫，有关人员做了相关研究。“Fish”系统是最早的“主题集中式爬虫”之一(P.De Bra，G.Houben，et al，Information Retrieval inDistributed Hypertexts，Proceedings of the 4^th RIAO Conference，pp.481-491，1994)。该系统采用深度优先方法对万维网资源进行游历，对网页的相关度评价采用基于关键字和正则表达式的方法。“Shark”[M.Hersovici，M.Jacovi，et al，The Shark-Search Algorithm-An Application：Tailored WebSite Mapping，Proceedings of 7^th International World Wide Web Conference，1998]搜索算法是在“Fish”基础上的改进。这种改进表现在两个方面。首先，它采用了向量空间模型来对网页的主题的相关度进行评价，这比起“Fish”中基于关键字和正则表达式的方法，更有弹性；其次，“Shark”算法精化了对需要爬行的超链的评价，通过分析超链的锚文本来评价它，而不是根据包含超链的整个网页来做判断。

IBM的Soumen Chakrabati和他的同事也提出了一种“主题集中式的爬虫”系统[S.Chakrabarti，M.Van Der Berg，and B.Dom，Focused Crawling：A NewApproach to Topic-specific Resource Discovery，Proceeding of the 8thInternational World Wide Web Conference，1999]。这个系统有三个重要的部分：分类器(classifier)，“蒸馏器”(distiller)和爬虫(crawler)，不同的部分完成不同的工作，分别进行对网页相关性的判定，对网页重要性的判定，以及对队列中网页的下载。

以上，在Fish和Shark系统中，对网页的扩展是基于相关度的，而不具备对网页重要度的考虑。IBM提出的爬虫系统，综合考虑了网页相关度和重要度，但是在重要度的计算中，采用了一种需要进行迭代计算的HIT算法变种，有很大的时间开销。

另一种PageRank技术，是从分析网页超链结构的角度入手的。其分析方法是：一个网页，如果被若干个网页引用，那么它的重要度就大致由那若干个网页的重要度决定。如果一个网页指向若干个网页，那它就会把自己的重要度分布给那若干个网页。这是PageRank算法的基本思想(L.Page，S.Brin，R.Motwani，and T.Winograd.The PageRank citation ranking：Bringing order to the web.Technical Report，Stanford University，Stanford，CA.1998)。由于PageRank需要全局的矩阵迭代，计算量比较大，一般是每隔一段爬行时间才进行的。

三、发明内容

本发明的目的是：克服以上的不足，提出一种可扩展、可定制的主题集中式万维网爬虫设计方法。

我们发明了新的设计方法，可以据此设计可扩展、可定制的主题集中式万维网爬虫系统。这样的系统，可以兼顾对相关网页的重要度和相关度的判断，来决定是否采用该网页，在效率上，它不需要对网页集做全局的迭代运算，有较快的速度表现。

一种可扩展、可定制的主题集中式万维网爬虫系统设置方法，包括分析网页的相关度和网页扩展，以R_c(P)表示网页与初始网页集的相关度，利用R_a(P)可以建立这样的预测机制，因为R_a(P)可以通过分析有超链指向P的网页得到。以向量空间模型，以下述公式计算：

$>>>R>a>>>(>P>)>>=>>>>\Sigma >>k>\in >t>\cap >p>>>>f>kt>>·>>f>kp>>>>>\Sigma >>k>\in >t>>>>>f>kt>>2>>·>>\Sigma >>k>\in >p>>>>>f>kp>>2>>>>>s>$

其中，t表示主题的关键字集合，p表示指向网页P的超链的锚文本及周边的文本的关键字集合，f表示关键字在相应部分出现的频率；

每次网页扩展都将会进行一次计算调整，但计算只发生在所涉及到的网页，排序调整也可控制在未被访问的若干网页中；

这样得到的爬行方法我们称之为TimelyRank(TR)。TR在每次分析网页时进行调整，公式如下：

TR(p，t_p)＝TR(p，t_p-1)+TR(d，t_d)

其中，TR(p，t)表示网页p在时刻t_p的TimelyRank值，t_i＝0，1，2，…，表示网页i的逻辑时间，每次对网页i进行TimelyRank值计算，它的逻辑时间就增加1，t_i＝0时，网页i有初始的TimelyRank值；d表示指向网页p的网页。

在网页的相关度分析中，本方法采取的是预测方法，对网页在下载前就进行评价，这样可避免较大的网络开销和处理时间。预测是依据是待下载的网页的被引用的锚文本及周围相关的文本，分析他们与原始网页集的相关性，采用的方法借鉴向量空间模型。

在对网页的重要度分析中，本发明方法采用的是PageRank的简化方法。PageRank算法和HITS方法(J.Kleinberg，Authoritative sources in ahyperlinked environment.Proceeding of 9^th ACM-SIAM Symposium on DiscreteAlgorithms，1998)类似，需要全局的矩阵迭代，计算量比较大，一般是每隔一段爬行时间才进行的。本方法简化后的算法，我们称之为TimelyRank。采用这个算法，是在每次对网页进行扩展的时候采取一次计算调整，计算只发生在所涉及到的网页，排序调整也可控制在未被访问的若干网页中。这样的话，原有的PageRank的迭代在我们的方法中就是在对网页扩展中无形地发生了，只不过这种迭代不是从全局出发。

本方法也考虑了对所爬行网页深度的评价，一般的，离原始网页集越远，也即爬行的深度越深，那网页的相关性就可能越低。

需要强调的是，本方法对以上的评价进行了综合，以此对待下载的网页进行评价。而这种综合，可以根据应用的偏好进行调节，以体现哪种评价需要被着重考虑。

除了在评价策略上有独到的地方，系统的整体设计方法也体现了很大的可扩展性。对于简单的应用，不需要爬行很多网页资源的情况下，可以采用直接在内存中展开分析的方法，把获得的网页以文件的形式存放在文件系统上；而如果要转到比较复杂的应用上，需要把网页资源保存到数据库中，并且需要对网页进行缓存，这种情况下，只需替换掉相应的部件，就可以完成转变。

本发明的优点

本发明所提出的设计方法，据此设计的可扩展、可定制的主题集中式万维网爬虫系统，有如下的优点：

■混合策略。通过混合策略，我们兼顾了扩展中需要对网页的相关性和重要性两方面的评价。

■可调节性。通过调整参数，我们可以方便地进行策略调整，加强或减弱某种策略对扩展的影响，因此具有很强的灵活性。

■健壮性。这是混合策略带来的好处。单一策略对网页的评价比较片面，例如，扩展时仅考虑网页的重要性，忽略了相关性，就容易导致主题的偏移。而混合策略下，这种片面性将被减小，这就使扩展具有比较好的健壮性。

■较小的网络开销。在我们系统中，是通过对网页中的超链进行综合评价，以决定是否扩展。因此，评价低的超链被优先扩展的可能性就低了，被优先扩展的超链都是评价较高的网页。这样就提高了网络使用效率，减少了不必要的网络开销。

■较小的实现代价。我们没有采用复杂的分类器，避免了采集样本，训练分类器的麻烦。另外，在计算网页重要度时，我们做了简化，尽管损失了一些精度，但是这样避免了定期的做全局的矩阵计算，降低了实现难度。

■可扩展性。这是从模块的设计角度看的。我们运用设计模式的思想，对扩展过程中的通用操作进行提炼，将它们与抽象的扩展策略分离开来。这样，在今后就可以方便地进行其他策略的实现，因此有很强的扩展性。

四、附图说明

图1为利用混合游历策略进行网页扩展的伪代码描述

图2为本发明Dolphin Crawler设计框架图

图3主题初始网页集

图4网页集的主题平均相关性实验比较

五、具体实施方式

我们先分别从相关度、重要度方面进行说明。

分析网页的相关度。R_c(P)表示网页与主题(即初始网页集)的相关度，当网页还未下载时，R_c(P)是无法知道的；而如果将网页下载下来对它进行相关度分析，就会增加系统的开销。因为有可能下载下来的很多网页根本就不相关，这样就降低了系统的效率。因此，有必要利用一种预测机制，对网页在下载前就进行评价。利用R_a(P)可以建立这样的预测机制，因为R_a(P)可以通过分析有超链指向P的网页得到。借鉴向量空间模型，可用如下公式来计算它：

$>>>R>a>>>(>P>)>>=>>>>\Sigma >>k>\in >t>\cap >p>>>>f>kt>>·>>f>kp>>>>>\Sigma >>k>\in >t>>>>>f>kt>>2>>·>>\Sigma >>k>\in >p>>>>>f>kp>>2>>>>>s>$

其中，t表示主题的关键字集合，p表示指向网页P的超链的锚文本及周边的文本的关键字集合，f表示关键字在相应部分出现的频率。

在考虑相关度时，还有一个因素，即对所爬行网页深度的评价，爬行深度越深，一般来说，相关的程度就越低。用R_d(P)表示这个评价。它可用如下的公式表示：

R_d(P)＝1/d

其中，d为P与“根网页”的最近超链距离，当P属于根网页集时，则d＝1。

分析网页的重要性。在讨论评价网页的重要性前，我们先介绍一下PageRank。PageRank是从分析网页超链结构的角度入手的。一个网页，如果被若干个网页引用，那么它的重要度就大致由那若干个网页的重要度决定。如果一个网页指向若干个网页，那它就会把自己的重要度分布给那若干个网页。

由于PageRank需要全局的矩阵迭代，计算量比较大，一般是每隔一段爬行时间才进行的。我们从提高效率的角度出发，对它进行了简化。简化后的PageRank，我们称之为TimelyRank(TR)。TR在每次分析网页时进行调整，公式如下：

TR(p，t_p)＝TR(p，t_p-1)+TR(d，t_d)

其中，TR(p，t)表示网页p在时刻t_p的TimelyRank值，t_i＝0，1，2，…，表示网页i的逻辑时间，每次对网页i进行TimelyRank值计算，它的逻辑时间就增加1，t_i＝0时，网页i有初始的TimelyRank值；d表示指向网页p的网页。

从公式可见，TR继承了PageRank的思想，但在计算方式上做了变动。每次扩展都将会进行一次计算调整，但计算只发生在所涉及到的网页，排序调整也可控制在未被访问的若干网页中。

综合以上对网页相关度和重要度的分析，我们设计了混合游历策略。在该策略中，我们使用如下的公式作为选择未访问网页的依据：

D(p，t)＝α·R_a(p)+β·R_d(p)+γ·TR(p，t)

其中，0＜α，β，γ＜1，且α+β+γ＝1，作为对不同评价的权值调整。

图1给出了利用混合游历策略进行网页扩展的伪代码描述。

以上讨论了可调节的爬寻网页的综合策略。以下主要说明在使用以上策略设计爬虫系统的可扩展的体系结构。图2即为设计框架图。

一般的，对于一个爬虫系统来说，其运作流程大体是差不多的：首先获得要扩展的URL，通过对它进行扩展，得到网页数据；然后，对网页数据进行解析，分析出其中潜在需要扩展的超链和这些超链相关的信息(如锚文本)，最后将这些超链存入一个库中。我们根据爬虫系统的这一特点，对流程进行了抽象，设计成爬虫系统的框架。这个框架由一个具体的Crawler控制类和三个抽象的协作部分组成，这三个抽象部分是：网页拾取器(Fetcher)、网页解析器(PageParser)、超链图(URLGraph)。对于网页拾取器、网页解析器、以及超链图三部分的设计扩展接口良好。例如，如果只需要将爬行到的网页简单的存放到文件系统上，可使用简单的网页拾取器，如果需要将爬行到的网页保存到数据库中，或者进行缓存、压缩，则可以使用复杂的网页拾取器；如果要个性化对网页的分析，可以使用定制的网页解析器替换掉现存的网页解析器；如果对分析的中间结果不感兴趣，且爬行量不是很大，可以使用在内存中展开分析数据的超链图，这样可以有很好的速度表现，如果需要进行大容量的爬行，且需要对分析结果进行分析并保存，可以使用基于数据库的超链图实现。

网页拾取器的任务就是根据URL获得网页内容，根据具体的情况，可以有不同的实现。比如可设计从本地数据库缓存中获得网页的拾取器(DB Fetcher)，也可设计从万维网上直接获得网页数据的拾取器(Net Fetcher)，或者混和的拾取器。

网页解析器的任务就是对得到的网页进行内容上的初步分析，获得其中的超链及相关的信息。这允许我们可以根据需要，设计特殊的网页解析器，如对超链文本距离进行加权的网页解析器(Weighted PageParser)。

超链图的任务就是负责维护解析到的超链的结构，并根据具体需要为Crawler提供可扩展的URL。我们可以将超链图设计成使用外部存储介质的方式，这样方便Crawler线程在不同的主机上分布运行；我们也可以将它设计成使用内存方式，这样允许小规模的爬行在多线程环境下快速执行；另外，我们可以在不同的超链图实现中采用有针对性的排序算法，以决定需要按照什么策略进行扩展。

我们设计了实验来验证爬虫的有效性。在实验中，我们主要从两个方面对实验结果进行了评价。一个方面是评价Crawler在维持主题相关性方面的效果；另一方面是评价Crawler对重要网页的挖掘能力。

首先，分析Crawler在维持主题相关性方面的效果。我们参考了文献(Filippo Menczer，Gautam Pant，et al，Evaluating Topic-Driven WebCrawler，In Proc.24th Annual Intl.ACM SIGIR Conf.on Research andDevelopment in Information Retrieval，2001)的一种方法，对主题相关性进行评价。这个方法评价网页集随时间变化的平均相关度，采用如下公式进行计算：

$>>sim>>(>q>,>S>>(>t>)>>)>>=>>1>>|>S>>(>t>)>>|>>>>\Sigma >>p>\in >S>>(>t>)>>>>>>>\Sigma >>k>\in >p>\cap >q>>sup>>w>kq>tfidfsup>sup>>w>kp>tfidfsup>>>>>\Sigma >>k>\in >p>>>>(sup>>w>kp>tfidfsup>>>)>2>>>\Sigma >>k>\in >q>>>>>(sup>>w>kq>tfidfsup>>)>>2>>>>>>s>$

其中，q表示某个主题，它由若干个该主题下具有代表性的网页构成；S(t)表示在时刻t为止爬行到的网页集；w_kd^tfidf表示单词k在文档d中的tf*idf权重，它用如下公式计算：

$>sup>>w>kd>tfidfsup>>=>>f>kd>>·>>(>1>+>ln>>(>>>|>S>|>>>n>k>>>)>>)>>>s>$

其中，f_kd是单词k在文档d中出现的频度；|S|是网页集S的大小；n_k是单词k在网页集S中出现的文档频度。

我们选择四个主题进行了实验，每个主题使用了3到4个网页作为主题的初始网页集，如并参见图3所示。我们对每个主题进行不同策略权重的爬行，即选择了四种不同的权重参数向量(α，β，γ)，然后对爬行结果进行如上的相关度分析，并按照对应的权重参数对四个主题的结果进行了平均，以减少单个主题结果的随机性。实验结果如如图所示。并参见图3主题初始网页集。

当α＝1.0，β＝0.0，γ＝0.0时，根据公式，爬行的策略可以认为是锚文本预测相关度优先；当α＝0.0，β＝1.0，γ＝0.0时，可以认为是广度优先策略；当α＝0.0，β＝0.0，γ＝1.0时，爬行的策略可以认为是链接度优先；而当α＝0.4，β＝0.3，γ＝0.3时，可以认为是综合策略。

分析如图。在爬行初期，广度优先策略对应的网页集，它的主题相关度相对较高，综合策略和锚文本预测相关度优先次之，而链接度优先最后。当爬行到一定程度后，广度优先策略对应的网页集，它的相关度有较大的下降，链接度优先也有一定的下降趋势，综合策略及锚文本预测相关度优先，它们对应的网页集相关度尽管也在下降，但下降趋势相对比较缓慢且稳定。如图4网页集的主题平均相关性实验比较图。

广度优先策略在初始时相关度效果较好，而在后期效果下降很大，这是由它的本性决定的。广度优先的本性，就是某段时间集中在一个站点的相关网页上爬行，如果这个站点恰好是与主题相近的站点(这种情况一般发生在开始阶段)，那么，由于同一个网站所使用的词汇都有很大相似性，因此它在这个阶段生成的网页集就有很大的相关性。而当爬虫爬出主题网站，爬到一个不相关的网站，这时，网页集的平均相关度呈很大的下降趋势。

其次，分析爬虫对重要网页的挖掘能力。在进行此项评价前，有必要对“重要网页”做个解释。如果根据人们的主观评价，来确定一个网页是否重要，以此获得一个重要网页列表，这样显然不够客观。因此，我们是使用HITS算法(J.Kleinberg，Authoritative sources in a hyperlinked environment.Proceeding of 9^th ACM-SIAM Symposium on Discrete Algorithms，1998)来获得重要网页列表，该算法是通过网页集合中的超链结构信息来计算网页重要性的，因此具有一定的客观性。合并每个主题下各个爬行策略获得的网页集，得到一个综合的网页集，对该网页集进行HITS计算，我们就可获得每个主题对应的重要网页列表，作为评价爬虫挖掘重要网页能力的依据。好的游历策略应该可以尽可能早地访问到这些重要网页；并且，在游历过程中，应该可以尽可能多地覆盖到这些网页。

图5所反映的就是不同策略对重要网页的发现能力。其中可见，链接度优先策略在这方面表现较好，综合策略次之，锚文本预测相关度策略的表现更次，而广度优先策略的表现在初始阶段不错，但到后期效果较差。