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

1.一种可扩展、可定制的主题集中式万维网爬虫系统设置方法，其特征是包括分 析网页的相关度和网页扩展，以Rc(P)表示网页与初始网页集的相关度，利用Ra(P)可 以建立这样的预测机制，因为Ra(P)可以通过分析有超链指向P的网页得到；向量空间 模型，以下述公式计算：
R a ( P ) = Σ k ∈ t ∩ p fkt · fkp Σ k ∈ t fkt 2 · Σ k ∈ p fkp 2
其中，t表示主题的关键字集合，p表示指向网页P的超链的锚文本及周边的文本的关 键字集合，f表示关键字在相应部分出现的频率；
每次网页扩展都将会进行一次计算调整，但计算只发生在所涉及到的网页，排序 调整也可控制在未被访问的若干网页中；
这样得到的爬行方法称之为TimelyRank即TR；TR在每次分析网页时进行调整， 公式如下：
TR(p，tp)＝TR(p，tp-1)+TR(d，td)
其中，TR(p，tp)表示网页P在时刻tp的TR值，tp＝0，1，2，...，表示网页tp的逻辑时 间，每次对网页P进行TR值计算，它的逻辑时间就增加1，ti＝0时，网页P有初始的 TR值；d表示指向网页P的网页；对网页相关度和重要度的分析使用如下公式作为选 择未访问网页的依据：
D(P，t)＝α·Ra(P)+β·Rd(P)+γ·TR(P，t)
其中，0＜α，β，γ＜1，且α+β+γ＝1，作为对不同评价的权值调整；相关的程度 用Rd(P)表示这个评价：Rd(P)＝1/d
其中，d为P与“根网页”的最近超链距离，当P属于根网页集时，则d＝1。
2.由权利要求1所述的可扩展、可定制的主题集中式万维网爬虫系统设置方法， 其特征是系统划分成网页拾取器、网页解析器、以及超链图；如果只需要将爬行到的 网页存放到文件系统上，使用相对简单的网页拾取器，如果需要将爬行到的网页保存 到数据库中，或者进行缓存、压缩，则使用相对复杂的网页拾取器；如果要个性化对 网页的分析，使用定制的网页解析器替换掉现存的网页解析器；如果对分析的中间结 果不感兴趣，且爬行量不是很大，使用在内存中展开分析数据的超链图，如果需要进 行大容量的爬行，且需要对分析结果进行分析并保存，使用基于数据库的超链图实现。

一、技术领域\n本发明涉及万维网(WWW)上对网页资源进行自动收集的机制。特别涉及对 可扩展、可定制的主题集中式万维网爬虫设置方法。\n二、技术背景\n万维网爬虫(Web Crawler)是一种在万维网上可以对网页资源进行自动收 集的软件。它主要应用在以下几个方面：\n●为搜索引擎对万维网上的网页资源进行索引提供网页来源。\n●协助特定用户收集特定的网页集。\n●协助人们进行对万维网现状进行统计分析，等等\n人们的目的不同，会导致对所使用的万维网爬虫的要求不同。人们会有这样 的需要，即对某种主题比较关注，或者人们要获取较大量的某领域下的万维网信 息，这种情况下，就需要有一种特定的爬虫来满足这种需要。\n在各种爬虫中，有一类爬虫称为主题集中式的万维网爬虫。它根据以上人们 的需要而产生。它根据一个初始网页集，利用初始网页集中的超链，采取一定的 策略，专门在网上爬行与初始网页集比较相关的网页，而对于不怎么相关的网页， 它会舍弃。\n关于这类爬虫，有关人员做了相关研究。“Fish”系统是最早的“上题集 中式爬虫”之一(P.De Bra，G.Houben，et al，Information Retrieval in Distributed Hypertexts，Proceedings of the 4th RIAO Conference，pp. 481-491，1994)。该系统采用深度优先方法对万维网资源进行游历，对网页的相 关度评价采用基于关键字和正则表达式的方法。“Shark”[M.Hersovici，M. Jacovi，et al，The Shark-Search Algorithm-An Application：Tailored Web Siite Mapping， Proceedings of 7thInternational World Wide Web Conference， 1998]搜索算法是在“Fish”基础上的改进。这种改进表现在两个方面。首先， 它采用了向量空间模型来对网页的主题的相关度进行评价，这比起“Fish”中基 于关键字和正则表达式的方法，更有弹性；其次，“Shark”算法精化了对需要爬 行的超链的评价，通过分析超链的锚文本来评价它，而不是根据包含超链的整个 网页来做判断。\nIBM的Soumen Chakrabati和他的同事也提出了一种“主题集中式的爬虫” 系统[S.Chakrabarti，M.Van Der Berg，and B.Dom，Focused Crawling：A New Approach to Topic-specific Resource Discovery，Proceeding of the 8th International World Wide Web Conference，1999]。这个系统有三个重要的部 分：分类器(classifier)，“蒸馏器”(distiller)和爬虫(crawler)，不同的 部分完成不同的工作，分别进行对网页相关性的判定，对网页重要性的判定，以 及对队列中网页的下载。\n以上，在Fish和Shark系统中，对网页的扩展是基于相关度的，而不具备 对网页重要度的考虑。IBM提出的爬虫系统，综合考虑了网页相关度和重要度， 但是在重要度的计算中，采用了一种需要进行迭代计算的HIT算法变种，有很大 的时间开销。\n另一种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 需要全局的矩阵迭代，计算量比较大，一般是每隔一段爬行时间才进行的。\n三、发明内容\n本发明的目的是：克服以上的不足，提出一种可扩展、可定制的主题集中式 万维网爬虫设计方法。\n我们发明了新的设计方法，可以据此设计可扩展、可定制的主题集中式万维 网爬虫系统。这样的系统，可以兼顾对相关网页的重要度和相关度的判断，来决 定是否采用该网页，在效率上，它不需要对网页集做全局的迭代运算，有较快的 速度表现。\n一种可扩展、可定制的主题集中式万维网爬虫系统设置方法，包括分析网页 的相关度和网页扩展，以Rc(P)表示网页与初始网页集的相关度，利用Ra(P)可以 建立这样的预测机制，因为Ra(P)可以通过分析有超链指向P的网页得到。以向 量空间模型，以下述公式计算：\n R a ( P ) = Σ k ∈ t ∩ p f kt · f kp Σ k ∈ t f kt 2 · Σ k ∈ p f kp 2 \n其中，t表示主题的关键字集合，p表示指向网页P的超链的锚文本及周边的文 本的关键字集合，f表示关键字在相应部分出现的频率；\n每次网页扩展都将会进行一次计算调整，但计算只发生在所涉及到的网页， 排序调整也可控制在未被访问的若干网页中；\n这样得到的爬行方法我们称之为TimelyRank(TR)。TR在每次分析网页时进 行调整，公式如下：\nTR(p，tp)＝TR(p，tp-1)+TR(d，td)\n其中，TR(p，t)表示网页p在时刻tp的TimelyRank值，tp＝0，1，2，…，表示 网页P的逻辑时间，每次对网页P进行TimelyRank值计算，它的逻辑时间就增 加1，tp＝0时，网页P有初始的TimelyRank值；d表示指向网页p的网页。\n在网页的相关度分析中，本方法采取的是预测方法，对网页在下载前就进行 评价，这样可避免较大的网络开销和处理时间。预测是依据是待下载的网页的被 引用的锚文本及周围相关的文本，分析他们与原始网页集的相关性，采用的方法 借鉴向量空间模型。\n在对网页的重要度分析中，本发明方法采用的是PageRank的简化方法。 PageRank算法和HITS方法(J.K1einberg，Authoritative sources in a hyperlinked environment.Proceeding of 9th ACM-SIAM Symposium on Discrete Algorithms，1998)类似，需要全局的矩阵迭代，计算量比较大，一般是每隔一 段爬行时间才进行的。本方法简化后的算法，我们称之为TimelyRank。采用这 个算法，是在每次对网页进行扩展的时候采取一次计算调整，计算只发生在所涉 及到的网页，排序调整也可控制在未被访问的若干网页中。这样的话，原有的 PageRank的迭代在我们的方法中就是在对网页扩展中无形地发生了，只不过这 种迭代不是从全局出发。\n本方法也考虑了对所爬行网页深度的评价，一般的，离原始网页集越远，也 即爬行的深度越深，那网页的相关性就可能越低。\n需要强调的是，本方法对以上的评价进行了综合，以此对待下载的网页进行 评价。而这种综合，可以根据应用的偏好进行调节，以体现哪种评价需要被着重 考虑。\n除了在评价策略上有独到的地方，系统的整体设计方法也体现了很大的可扩 展性。对于简单的应用，不需要爬行很多网页资源的情况下，可以采用直接在内 存中展开分析的方法，把获得的网页以文件的形式存放在文件系统上；而如果要 转到比较复杂的应用上，需要把网页资源保存到数据库中，并且需要对网页进行 缓存，这种情况下，只需替换掉相应的部件，就可以完成转变。\n本发明的优点\n本发明所提出的设计方法，据此设计的可扩展、可定制的主题集中式万维网 爬虫系统，有如下的优点：\n■混合策略。通过混合策略，我们兼顾了扩展中需要对网页的相关性和 重要性两方面的评价。\n■可调节性。通过调整参数，我们可以方便地进行策略调整，加强或减 弱某种策略对扩展的影响，因此具有很强的灵活性。\n■健壮性。这是混合策略带来的好处。单一策略对网页的评价比较片面，\n例如，扩展时仅考虑网页的重要性，忽略了相关性，就容易导致主题 的偏移。而混合策略下，这种片面性将被减小，这就使扩展具有比较 好的健壮性。\n■较小的网络开销。在我们系统中，是通过对网页中的超链进行综合评 价，以决定是否扩展。因此，评价低的超链被优先扩展的可能性就低 了，被优先扩展的超链都是评价较高的网页。这样就提高了网络使用 效率，减少了不必要的网络开销。\n■较小的实现代价。我们没有采用复杂的分类器，避免了采集样本，训 练分类器的麻烦。另外，在计算网页重要度时，我们做了简化，尽管 损失了一些精度，但是这样避免了定期的做全局的矩阵计算，降低了 实现难度。\n■可扩展性。这是从模块的设计角度看的。我们运用设计模式的思想， 对扩展过程中的通用操作进行提炼，将它们与抽象的扩展策略分离开 来。这样，在今后就可以方便地进行其他策略的实现，因此有很强的 扩展性。\n四、附图说明\n图1为利用混合游历策略进行网页扩展的伪代码描述\n图2为本发明Dolphin Crawler设计框架图\n图3主题初始网页集\n图4网页集的主题平均相关性实验比较\n五、具体实施方式\n我们先分别从相关度、重要度方面进行说明。\n分析网页的相关度。Rc(P)表示网页与主题(即初始网页集)的相关度，当 网页还未下载时，Rc(P)是无法知道的；而如果将网页下载下来对它进行相关度 分析，就会增加系统的开销。因为有可能下载下来的很多网页根本就不相关，这 样就降低了系统的效率。因此，有必要利用一种预测机制，对网页在下载前就进 行评价。利用Ra(P)可以建立这样的预测机制，因为Ra(P)可以通过分析有超链指 向P的网页得到。借鉴向量空间模型，可用如下公式来计算它：\n R a ( P ) = Σ k ∈ t ∩ p f kt · f kp Σ k ∈ t f kt 2 · Σ k ∈ p f kp 2 \n其中，t表示主题的关键字集合，p表示指向网页P的超链的锚文本及周边的文 本的关键字集合，f表示关键字在相应部分出现的频率。\n在考虑相关度时，还有一个因素，即对所爬行网页深度的评价，爬行深度越 深，一般来说，相关的程度就越低。用Rd(P)表示这个评价。它可用如下的公式 表示：\nRd(P)＝1/d\n其中，d为P与“根网页”的最近超链距离，当P属于根网页集时，则d＝1。\n分析网页的重要性。在讨论评价网页的重要性前，我们先介绍一下PageRank。 PageRank是从分析网页超链结构的角度入手的。一个网页，如果被若干个网页 引用，那么它的重要度就大致由那若干个网页的重要度决定。如果一个网页指向 若干个网页，那它就会把自己的重要度分布给那若干个网页。\n由于PageRank需要全局的矩阵迭代，计算量比较大，一般是每隔一段爬行 时间才进行的。我们从提高效率的角度出发，对它进行了简化。简化后的 PageRank，我们称之为TimelyRank(TR)。TR在每次分析网页时进行调整，公式 如下：\nTR(p，tp)＝TR(p，tp-1)+TR(d，td)\n其中，TR(p，t)表示网页p在时刻tp的TimelyRank值，tp＝0，1，2，…，表 示网页P的逻辑时间，每次对网页P进行TimelyRank值计算，它的逻辑时间 就增加1，tp＝0时，网页P有初始的TimelyRank值；d表示指向网页P的网页。\n从公式可见，TR继承了PageRank的思想，但在计算方式上做了变动。每次 扩展都将会进行一次计算调整，但计算只发生在所涉及到的网页，排序调整也可 控制在未被访问的若干网页中。\n综合以上对网页相关度和重要度的分析，我们设计了混合游历策略。在该策 略中，我们使用如下的公式作为选择未访问网页的依据：\nD(P，t)＝α·Ra(P)+β·Rd(P)+γ·TR(P，t)\n其中，0＜α，β，γ＜1，且α+β+γ＝1，作为对不同评价的权值调整。\n图1给出了利用混合游历策略进行网页扩展的伪代码描述。\n以上讨论了可调节的爬寻网页的综合策略。以下主要说明在使用以上策略设 计爬虫系统的可扩展的体系结构。图2即为设计框架图。\n一般的，对于一个爬虫系统来说，其运作流程大体是差不多的：首先获得要 扩展的URL，通过对它进行扩展，得到网页数据；然后，对网页数据进行解析， 分析出其中潜在需要扩展的超链和这些超链相关的信息(如锚文本)，最后将这 些超链存入一个库中。我们根据爬虫系统的这一特点，对流程进行了抽象，设计 成爬虫系统的框架。这个框架由一个具体的Crawler控制类和三个抽象的协作部 分组成，这三个抽象部分是：网页拾取器(Fetcher)、网页解析器(PageParser)、 超链图(URLGraph)。对于网页拾取器、网页解析器、以及超链图三部分的设计 扩展接口良好。例如，如果只需要将爬行到的网页简单的存放到文件系统上，可 使用简单的网页拾取器，如果需要将爬行到的网页保存到数据库中，或者进行缓 存、压缩，则可以使用复杂的网页拾取器；如果要个性化对网页的分析，可以使 用定制的网页解析器替换掉现存的网页解析器；如果对分析的中间结果不感兴 趣，且爬行量不是很大，可以使用在内存中展开分析数据的超链图，这样可以有 很好的速度表现，如果需要进行大容量的爬行，且需要对分析结果进行分析并保 存，可以使用基于数据库的超链图实现。\n网页拾取器的任务就是根据URL获得网页内容，根据具体的情况，可以有不 同的实现。比如可设计从本地数据库缓存中获得网页的拾取器(DB Fetcher)， 也可设计从万维网上直接获得网页数据的拾取器(Net Fetcher)，或者混和的拾 取器。\n网页解析器的任务就是对得到的网页进行内容上的初步分析，获得其中的超 链及相关的信息。这允许我们可以根据需要，设计特殊的网页解析器，如对超链 文本距离进行加权的网页解析器(Weighted PageParser)。\n超链图的任务就是负责维护解析到的超链的结构，并根据具体需要为 Crawler提供可扩展的URL。我们可以将超链图设计成使用外部存储介质的方式， 这样方便Crawler线程在不同的主机上分布运行；我们也可以将它设计成使用内 存方式，这样允许小规模的爬行在多线程环境下快速执行；另外，我们可以在不 同的超链图实现中采用有针对性的排序算法，以决定需要按照什么策略进行扩 展。\n我们设计了实验来验证爬虫的有效性。在实验中，我们主要从两个方面对实 验结果进行了评价。一个方面是评价Crawler在维持主题相关性方面的效果；另 一方面是评价Crawler对重要网页的挖掘能力。\n首先，分析Crawler在维持主题相关性方面的效果。我们参考了文献 (Filippo Menczer，Gautam Pant，et al，Evaluating Topic-Driven Web Crawler，In Proc.24th Annual Intl.ACM SIGIR Conf.on Research and Development in Information Retrieval，2001)的一种方法，对主题相关性进 行评价。这个方法评价网页集随时间变化的平均相关度，采用如下公式进行计算：\n sin ( q , S ( t ) ) = 1 | S ( t ) | Σ p ∈ S ( t ) Σ k ∈ p ∩ q w kq tfidf w kp tfidf Σ k ∈ p ( w kp tfidf ) 2 Σ k ∈ q ( w kq tfidf ) 2 \n其中，q表示某个主题，它由若干个该主题下具有代表性的网页构成；S(t)表示 在时刻t为止爬行到的网页集；wkd tfidf表示单词K在文档d中的tf*idf权重，它 用如下公式计算：\n w kd tfidf = f kd · ( 1 + ln ( | S | n k ) ) \n其中，fkd是单词K在文档d中出现的频度；|S|是网页集S的大小；nk是单词K 在网页集S中出现的文档频度。\n我们选择四个主题进行了实验，每个主题使用了3到4个网页作为主题的初 始网页集，如并参见图3所示。我们对每个主题进行不同策略权重的爬行，即选 择了四种不同的权重参数向量(α，β，γ)，然后对爬行结果进行如上的相关度分析， 并按照对应的权重参数对四个主题的结果进行了平均，以减少单个主题结果的随 机性。实验结果如如图所示。并参见图3主题初始网页集。\n当α＝1.0，β＝0.0，γ＝0.0时，根据公式，爬行的策略可以认为是锚文本预测 相关度优先；当α＝0.0，β＝1.0，γ＝0.0时，可以认为是广度优先策略；当 α＝0.0，β＝0.0，γ＝1.0时，爬行的策略可以认为是链接度优先；而当 α＝0.4，β＝0.3，γ＝0.3时，可以认为是综合策略。\n分析如图。在爬行初期，广度优先策略对应的网页集，它的主题相关度相 对较高，综合策略和锚文本预测相关度优先次之，而链接度优先最后。当爬行到 一定程度后，广度优先策略对应的网页集，它的相关度有较大的下降，链接度优 先也有一定的下降趋势，综合策略及锚文本预测相关度优先，它们对应的网页集 相关度尽管也在下降，但下降趋势相对比较缓慢且稳定。如图4网页集的主题 平均相关性实验比较图。\n广度优先策略在初始时相关度效果较好，而在后期效果下降很大，这是由它 的本性决定的。广度优先的本性，就是某段时间集中在一个站点的相关网页上爬 行，如果这个站点恰好是与主题相近的站点(这种情况一般发生在开始阶段)， 那么，由于同一个网站所使用的词汇都有很大相似性，因此它在这个阶段生成的 网页集就有很大的相关性。而当爬虫爬出主题网站，爬到一个不相关的网站，这 时，网页集的平均相关度呈很大的下降趋势。\n其次，分析爬虫对重要网页的挖掘能力。在进行此项评价前，有必要对“重 要网页”做个解释。如果根据人们的主观评价，来确定一个网页是否重要，以此 获得一个重要网页列表，这样显然不够客观。因此，我们是使用HITS算法(J. Kleinberg，Authoritative sources in a hyperlinked environment. Proceeding of 9th ACM-SIAM Symposium on Discrete Algorithms，1998)来获 得重要网页列表，该算法是通过网页集合中的超链结构信息来计算网页重要性 的，因此具有一定的客观性。合并每个主题下各个爬行策略获得的网页集，得到 一个综合的网页集，对该网页集进行HITS计算，我们就可获得每个主题对应的 重要网页列表，作为评价爬虫挖掘重要网页能力的依据。好的游历策略应该可以 尽可能早地访问到这些重要网页；并且，在游历过程中，应该可以尽可能多地覆 盖到这些网页。\n图5所反映的就是不同策略对重要网页的发现能力。其中可见，链接度优先 策略在这方面表现较好，综合策略次之，锚文本预测相关度策略的表现更次，而 广度优先策略的表现在初始阶段不错，但到后期效果较差。