网络蜘蛛搜索基本策略研究.kdh

软 件 导 刊 2009年软 件 导 刊 2009年 第 8卷 第 2期 2009年 2月 Vol.8 No.2 Feb. 2009 软 件 导 刊 Software Guide 0 引言 近年来，随着 Internet 技术的广泛应用，传统的通用搜索 引擎，如 Google、Fast、Baidu 和 Go To 等正面临巨大的挑战。 相 关研究 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明，Web 上的页面平均 50 天就有约 50％的页面发生 变化， 而目前通用搜索引擎更新的时间至少需要数星期之久。 传统的搜索引擎提供的信息检索服务，不能满足人们日益增长 的对个性化服务的需要。 面对这些挑战，各类适应特定人群需 要的“专业搜索引擎”（Topic2Specific Search Engine）应运而生 并引起研究者的重视。以何种策略访问 Web，并提高搜索效率， 是近年来专业搜索引擎网络蜘蛛研究的焦点之一。 1 网络蜘蛛的工作原理 在搜索引擎系统中，网络蜘蛛（Web spider，或称爬行者、代 理体）是一种“智能化”的软件，其任务是获取 Web 页面。 它通 常从一个“种子集”出发，通过 HTTP 协议请求并下载 Web 页 面，分析页面并提取链接，然后再以迭代的方式访问 Web。 网 络蜘蛛的搜索策略与搜索引擎的性质和任务密切相关。 为了 获得较高的 Web 覆盖率， 通用搜索引擎网络蜘蛛通常采用图 的遍历算法搜索 Web。 与通用搜索引擎不同，专业搜索引擎服 务于特定人群， 其索引的内容只限于特定主题或专门领域，因 而在搜索过程中无须对整个 Web 进行遍历， 只需选择与主题 页面相关的页面进行访问。 目前，专业搜索引擎网络蜘蛛通常 采用“最好优先”原则访问 Web，即为快速、有效地获得更多与 主题相关的页面（简称“回报”），每次选择“最有价值”的链接进 行访问。 由此可以看出，决定网络蜘蛛搜索策略的关键是如何 评价链接价值，即链接价值的计算方法。 不同的价值评价方法 计算出的链接的价值不同，表现出链接的“重要程度”不同，最 终决定了不同的搜索策略。 由于链接包含于页面之中，而通常 具有较高价值的页面包含的链接也具有较高的价值，因而对链 接价值的评价有时也转换为对页面价值的评价。 2 专业搜索引擎网络蜘蛛搜索策略研究进展 2．1 基于链接结构评价的搜索策略 考虑到 Web 页面不同于传统的文本， 它是一种半结构化 的文档，包含许多结构信息。 Web 页面不是单独存在的，页面 中的链接指示了页面之间的相互关系。有些学者尝试利用这些 结构特征来评价页面和链接的重要性， 以此决定搜索顺序。 Page2Rank 方法最初用于搜索引擎信息检索中对查询结果的 排序过程， 近年来被应用于网络蜘蛛对链接重要性的评价 。 Page2Rank 方法中， 页面的价值通常用页面的 PageRank 值表 示，若设页面 p 的 PageRank 值为 PR（p），则 PR（p）采用如下迭 代 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 计算： PR（p）＝rg 1T ＋ （1－r）g r∈in（p） Σ PR（r）out（r） （1） 其中，T 为计算中的页面总量，γ＜1 是阻尼常数因子，in（p） 为所有指向 p 的页面集合，out（r）为页面 r 出链的集合。 基于 Page2Rank 方法的网络蜘蛛在搜索过程中， 通过计算每个已访 问页面的 PageRank 值来确定页面的价值， 并每次选择 PageR- ank 值大的页面中的链接进行访问。 HITS方法也是根据链接结 构和页面之间的引用关系决定页面重要性的方法。 HITS 方法 定义了两个重要概念：Authority 和 Hub。 Authority 表示一个权 威页面被其它页面引用的数量，即该权威页面的入度值。 网页 被引用的数量越大，则该网页的 Authority 值越大。 Hub 表示一 个 Web 页面指向其它页面的数量，即该页面的出度值。 网页的 出度值越大，其 Hub 值越高。 由于通常 Hub 值高的页面都提供 网络蜘蛛搜索基本策略研究 赵 根 （中国地质大学 计算机学院，湖北 武汉 430074） 摘 要：网络蜘蛛搜索策略的研究是近年来专业搜索引擎研究的焦点之一。 按照评价链接价值所采用方法的不同， 对专业搜索引擎网络蜘蛛的搜索策略进行了分类，分析、比较了各类搜索策略的优缺点。 对未来的研究方向进行了 展望，给出了若干值得研究的问题。 关键词：专业搜索引擎；网络蜘蛛；搜索策略 中图分类号：TP393.09 文献标识码：A 文章编号：1672-7800（2009）02-0130-02 作者简介：赵根（1984-），男，湖北武穴人，中国地质大学（武汉）计算机学院硕士研究生，研究方向为多目标优化、数据挖掘。 第 2期 了指向权威页面的链接，因而起到了隐含说明某主题页面权威 性的作用。 HITS 方法对每个已访问页面计算其 Authority 权重 和 Hub权重，并以此决定页面中链接的访问顺序。 设页面 p 的 Authority 权重和 Hub 权重分别为 A［p］和 H［p］，它们分别按下 列迭代公式计算： A［p］＝ q：（q，p）∈F Σ H［q］ （2） H［p］＝ q：（q，p）∈F Σ A［q］ （3） 其中，E为所有指向页面 p的页面集合，F 为被页面 p 中的 链接指向的页面集合。两类策略的共同点是利用页面之间的引 用关系确定链接的重要性，因此称其为基于链接结构评价的搜 索策略。 这类搜索策略的优点是考虑了链接的结构特征，但也 存在一些缺陷：一是忽略了页面与主题的相关性，在某些情况 下，会出现搜索偏离主题的“主题漂移”问题；二是在搜索过程 中需要重复计算 PageRank 值或 Authority 及 Hub 权重，计算复 杂度随访问页面和链接数量的增长呈指数级增长。 2．2 基于未来回报价值评价的搜索策略 Rennie 和 McCallum 将巩固学习 （reinforcement learn2ing） 引入网络蜘蛛的学习过程。巩固学习的优势在于能够预测状态 的远期回报价值 （或称未来回报价值）。 由于在巩固学习模型 中，未来回报价值是用 Q 价值表示的，因而这种方法的核心就 是学习如何计算链接的 Q价值。 为此，搜索过程被划分成训练 和搜索两个阶段。训练阶段利用巩固学习算法计算每个链接的 Q 价值，按价值大小将链接分成若干类，并用每一类中链接的 文本信息训练一个 NaCve Bayes 分类器；在搜索阶段，面对价值 未知的链接，则根据链接文本，用 NaCveBayes 分类器计算链接 落在每一类中的概率，并以这个概率为权值计算链接的综合 Q 值。 因为 Q价值反映了对未来回报的预测值，所以即使当搜索 的页面与主题不相关时，这类网络蜘蛛也可以根据未来回报价 值确定正确的搜索方向。 基于巩固学习的网络蜘蛛能够通过链接 Q 价值的计算确 定搜索方向， 但它却无法估计距离目标页面的远近。 考虑到 Web 上主题相关页面往往具有某种层次关系， 且这些层次关 系之间存在某种相似性等特点，Diligenti 提出了基于“语境图” （context graphs）的搜索策略。 它通过构建典型页面的 Web“语 境图”来估计离目标页面的距离，距离较近的页面较早得到访 问。 该方法同样分为训练和搜索两个阶段。 训练阶段，得到了 一个表示种子页面集与周围页面之间层次关系的“语境图”。搜 索阶段，当下载完一个新的页面时，则利用训练阶段得到的分 类器判断该页面属于哪个层次集，从而估计出该页面距离目标 页面的远近，并优先访问距离目标较近的页面中的链接。 基于 未来回报的搜索策略本质上是通过训练发掘出链接文本中“隐 含”的结构信息，这些结构信息反映了距离搜索目标的远近，因 而在搜索远期回报方面具有一定优势。 然而，这类搜索策略也 存在一些不足：一是预测未来回报的能力有限。 进一步的研究 表明它们的预测距离不超过 324 层。二是这种“离线”（off2line） 的训练方式需要选择典型站点或种子集，加重了用户的负担。 3 网络蜘蛛搜索策略研究趋势 本质上说，网络蜘蛛的搜索问题是一个“多目标”规划问 题。 基于以上的分析，本文认为未来的研究主要是围绕提高链 接价值预测的准确性，降低计算的时空复杂度，以及增加网络 蜘蛛的自适应性这三个方面展开。在提高链接价值预测的准确 性方面，将各类评价方法相结合，尤其是将基于立即回报价值 评价和基于未来价值评价相结合值得进一步研究；将目信息检 索领域中的“概念检索”理论应用于链接价值的计算，是一个新 的尝试方向。 网络蜘蛛的搜索具有“重复性”，如何利用先前的 “经验信息”实现增量学习，以提高价值预测的准确性，是一个 值得研究的问题。 总之，网络蜘蛛搜索策略问题的研究还处于 发展阶段，无论是模型、搜索算法，还是实验方法都还有许多有 待解决的问题。 参考文献： ［1］ 李刚，宋伟，邱哲 ．征服 Ajax＋Lucene 构建搜索引擎［M］．北京：人 民邮电出版社，2006． ［2］ 李晓明 ．搜索引擎 ：原理 、技术与系统 ［M］．北京 ：科学出版社 ， 2005． （责任编辑：周晓辉） 赵 根：网络蜘蛛搜索基本策略研究 131- -