聚焦爬虫常见算法剖析

　　电脑知识与技术 数据库与信息管理 聚焦爬虫常见算法剖析 陈 丽 君 (浙江越秀外国语学院 浙江湖州 312000) [摘 要] 聚焦爬虫收集与特定主题相关的页面，为搜索引擎建立页面集。传统的聚焦爬虫采用向量空间模型和局部搜索算法，精确 率和召回率都比较低。文章分析了聚焦爬虫存在的问题及其相应的解决方式。最后对未来的研究方向进行了展望。 [关键词] 搜索引擎; 聚焦爬虫; 算法 不同于google、百度等通用搜索引擎，聚焦爬虫（也称为主题 爬虫）是一个能下载相关Web页的程序或自动化脚本。随着Web 页面的迅速攀升和特定领域搜索的需求，近年来，聚焦爬虫在工业 和学术界造成了广泛关注。 第一个聚焦爬虫是Chakrabarti于1999提出的[1]。聚焦爬虫一 般由两种算法来保证抓取特定领域的信息，一是Web剖析算法， 依据URL的指向判定Web页面的相关程度和质量；二是Web搜索 算法，它决定着被爬取URL的最佳顺序。 一、常见算法 1．Web页面剖析算法 目前，已出现了许多页面剖析算法，一般可以分为两大类： 基于内容的和基于链接结构的。前者通过剖析一个实际Web页的 HTML文档，来获取关于页面自身的相关性信息。

　　例如，在文档索 引技术的帮助下，可以从文档中抽取关键词或句子，依此确定该 文档是否与指定域相关。另外，也可以用VSM（向量空间模型） 与指定域的标准文档比较。对于前者，相关研究者发觉，Web链 接结构中包含有许多制作者蕴涵的信息，而这种信息对剖析文档 的相关性和质量起着重要作用。例如，当一个页面A指向另一个页 面B时，就意味着A页面的作者暗示着页面B也富含类似的内容。另 外，页面包含的接入链接越多就意味着该页面越重要。基于链接分 析的算法主要有PageRank和HITS。 2．Web搜索算法 该算法的主要目的是确定最优的URL访问顺序。与页面剖析算法 一样，搜索也有许多算法，以Breadth-first和Best-first最为流行。 2.1 Breadth-first搜索 该算法的思想比较简单，所有在当前层中的URL还会根据上一 层中它们被发觉的次序访问，其最大特征是不分辨页面的质量和主 题，所以最适合于通用搜索。但最近也有研究[2]表明，如果假定 当前层中的所有URL都是与主题相关的，那么它们的下一层URL也 会与主题相关。这样，Breadth-first就可用作收集一定质量的主题 相关页面，即聚焦搜索算法。

　　 但是，当抓取相当数目的页面后，该算法会引入许多噪声信息 （非相关信息），或形成主题甩尾现象。已有研究人员提出将此算 法与页面剖析算法相结合[4]，先用Breadth-first收集页面，再用页 面剖析算法过滤掉不相关的页面，这样即使降低了噪声信息，但降 低了算法的效率。 2.2 Best-first搜索 该算法目前比较流行。与Breadth-first不同，该算法不是简单 地根据被发觉的顺序访问，而是采用某种启发式思想（比如页面分 析的结果）来调整URL在队列中的排序，排在后面的被觉得是与主 题更接近的页面，要优先访问，反之，则推后甚至不被访问。因 此，Best-first搜索显著要比Breadth-first搜索更优越。 并且，Best-first是一个局部搜索算法，它只关心以前访问节 点周围的页面空间，因此会丧失许多相关页面，最后收集的页面质 量也不会很高。 二、存在问题 1．页面剖析算法 页面剖析是聚焦爬虫的重要组成部份，如果页面剖析算法对页 面的判定不够确切，将会影响到搜索算法，导致搜集到页面的质量 偏低。因此，实现一个高效的页面剖析算法是做好聚焦爬虫的第一 步。

　　 Web文档一般富含噪声，比如极少数的文本、图像、脚本等 对分类器没用的数据。而且，不同制作者在风格、语言、结构上 存在很大的差别。因此，采用简单的相似性函数（如tf-idf等）的 VSM很难取得令人满意的疗效。 一种解决的方式是，组合各类基于内容的相似性测度方式，可 以提升分类的准确率[4]。比如遗传算法等全局搜索模式也是一种 潜在的解决方案。 2．局部搜索算法 局部搜索算法的特征是，访问当初访问过节点周围的邻居节 点，这样假如一个相关页没有被现有URL所指向，那么聚焦爬虫就 会丧失对这个相关页面的访问。而且，如果在两个相关页面中间隔 有不相关的页面，聚焦爬虫也会舍弃对后一个相关页面的访问。因 此，采用局部搜索算法的聚焦爬虫只能够发觉围绕在起始*敏*感*词*集周 围的相关页面，它们仅仅是整个Web相关页面集的有限子集，而 丧失了该子集外的相关页面。 通过对Web结构的研究，人们发觉了Web社区[3]，也即在线 的Web页自然地按照特定的链接结构分成了不同的组，组内页面 都接近于个别主题或兴趣。聚焦爬虫的目的就是要获取所有的属于 那些相关社区的页面，然而，Web社区的以下三种特点，使得局 部搜索算法不再适用于集聚爬虫。

　　 （1）主题相像的社区之间，采用的不是直接的互相链接，而 是互相引用的关系。在商业领域，这是一个相当普遍现象。例如， Yahoo新闻、MSN新闻、Google新闻都提供相同或相像的新闻信 Algorithm Analysis of Focused Crawler Chen Lijun (Zhejiang Yuexiu University of Foreign Languages, Shaoxing Zhejing 312000, China) Abstract: Focused crawlers can selectively retrieve web documents relevant to a specific domain to build collections for domain- specific search engines. Traditional focused crawlers normally adopting the simple Vector Space Model and local Web search algorithms typically only find relevant Web pages with low precision and recall. This work describes and analyses problems associated with traditional focused crawlers and some potential solutions. The future directions are addressed. Key words: search engine; focused crawler; algorithm 笔记本知识与技术 数据库与信息管理 息，但因为竞争关系，它们并不包含彼此之间的链接。

　　因此，即使 它们都被作为相关Web社区的起始页面*敏*感*词*集，聚焦爬虫还是会 丧失一些相关的页面。 （2）相关页面之间可能被非相关的社区所隔断。有研究表 明，大多数相关域就会被起码1~12个非相关页面所分隔，平均非 相关间隔页面数为5，而聚焦爬虫在碰到非相关页面后不会继续访 问后续的页面，造成了大量相关页面的流失。 （3）虽然链接在相关页面间存在，但不是互相的单向链接， 而是双向的。也即两个相关的社区A和B，A和B之间存在着链接， 并且仅仅是一个方向的，比如只有从A到B的链接，而不存在从B到 A的链接。这样，当爬行顺序从A开始时网络爬虫算法书籍，B社区同样能被发觉，但 若爬行顺序是从B开始时，则A社区就不能从B中被发觉，造成A中 的相关页流失。 三、 解决方式 一种最简单的解决方式是提供更多的起始*敏*感*词*集，但这样也增 加了成本和时间，而且随着Web页面的迅速降低，这种解决方式 并不可取。 另一种解决方式是采用隧道技术[5]，它基于启发式方法解决 简单的全局优化问题。当聚焦爬虫遇见非相关的页面时，不是马上 舍弃继续搜索，而是在一定搜索深度（该值须要事先指定）范围内 继续搜索。

　　相关实验结果表明，隧道技术能发觉更多的相关页面， 并且，由于它没有改变局部搜索的本性，不能从根本上解决问题。 同时，噪音也被引入进来，降低了页面搜集质量。 研究人员通过对Web规模的研究发觉，主要搜索引擎之间索引 的重叠内容极少，因此，可以组合各类不同搜索引擎搜索结果中比 较靠前的结果，也就是元搜索技术，来解决局部搜索导致的问题。 四、未来展望 近些年来，研究人员发觉Web信息的分布存在一定的相似性， 因而考虑先进行训练，使爬虫具备一定的“经验知识”，通过这种 知识预测将来的回报。比如McCallum[6]引入巩固学习过程，先利 用巩固学习算法估算每位链接的回报价值Q，用Q值相同或相仿的 链接文本信息训练一个贝叶斯分类器，再对未知的链接文本，用该 分类器估算链接属于该类的机率，并借此机率为权重估算链接的综 合价值。也可以借助“智能搜索”技术，通过在线学习链接结构特 征，用于指导搜索过程。 五、结语 随着网页呈指数级的快速下降，以及人们对搜索结果精度要求的 不断提升，新的算法不断涌现，如基于机器学习的剖析算法、相似性 判定的遗传算法等。相信在研究人员的继续努力下，还会出现更多更 加确切、更加快速的新算法，不断增强人们对搜索结果的满意度。

　　 参考文献： [1] Chakrabarti, S., Berg, M.V.D., and Dom, B., Focused crawling: A New Approach to Topic-Sepcific Web Resouce Discovery. In Proceedings of the 8th International WWW Conf. 1999.Toronto, Canada. [2] Najork, M. and Wiener, J.L., Breadth-First Search Crawling Yields High-Quality Pages. In Proceedings of the 10th International WWW Conf. 2001. Hong Kong, China. [3] Flake, G.W., Lawrence, S., and Giles, C.L., Efficient Identification of Web Communities. In Proceediings of the 6 th ACM SIGKDD International Conf. 2000. Massachusetts, USA. [4] Qin, J. and Chen, H., Using Genetic Algorithm in Building Domain-Specific Collections: An Experiment in the Nanotechnology Domain. In Proceedings of the 38th Annual Hawaii International Conf. 2005. Hawaii, USA. [5] Bergmark, D., Lagoze, C., and Sbityakov, A., Focused Crawls, Tunneling, and Digital Libraries. In Porceedings of the 6th European Conf. 2002. Rome, Italy. [6] Rennie J, McCallum A. Using Reinforcement Learning to Spider the Web Efficiently. In Proc. of the International Conference on Machine Learning(ICML’99),1999. 取系数绝对值较大法适宜小波变换后的HL频带图象、LH频 带图象、HH频带图象等高频成份较丰富，亮度、对比度较高的图 象；融合图象中基本保留源图象的特点，图像对比度与源图象基本 相同。

　　小波变换的作用是对讯号解相关，并将讯号的全部信息集中 到一部分具有大幅值的小波系数中。这些大的小波系数富含的能量 远比小系数富含的能量大，从而在讯号的构建中，大的系数比小的 系数更重要。 3.3 一致性检查 图象中相邻象素点之间可能存在着空间冗余，因此空间上相邻 的点太可能属于同一图象的特点，因此应当对它们采用同一种方式 进行估算。根据这一思想，H.Li等提出用大多数原则对决策因子d 进行一致性检查。如果融合后的图象C在某个区域的中心点上的系 数来自于源图象A，而该点周围的点的系数均来自于源图象B，则 将中心点的系数替换为图象B的系数。 3.4 综合方式 源图象A，B分别进行小波分解，对小波变换后的LL频带图象 采取加权平均法，为了提升图象的质量，还可以在加权平均后采 用高斯低通滤波。对LH频带、HL频带、HH频带采用取系数绝对值 较大法，即取源图象A，B中小波系数较大的作为C的小波系数。另 *敏*感*词*的点均取自源图象B，则将该 点的小波系数改为源图象B的小波系数。 4 图像融合的现况及发展前景 近些年来，虽然图象融合技术发展迅速，但这仍是个没有统一理 论框架的新领域。

　　首先，影响图象融合疗效的诱因好多，例如，融 合算法的选定、小波基的选定以及小波分解层数的选择等；其次， 须要构建客观的图象融合技术评价标准；最后，特征级图象融和决 策级图象融合还有待长足的发展。 现有研究结果显示，对不同的频带采用了不同的融合算法结果 表明，对于低频部份采用加权方式较好，对于高频部份采用带一致 性检查的系数绝对值较大法融合疗效较好。 5 结束语 多传感图象融合技术作为信息融合研究领域的一项重要内 容网络爬虫算法书籍，将会在军事、遥感、机器人视觉和医学图象处理等领域得到广 泛应用。 参考文献： [1] 李敏，张小英，毛捷. 基于邻域残差加权平均的小波图象融合 [J]. 理论与技巧，2008，27(1)：5-6 [2] 王攀峰,杜云飞,周海芳,杨学军. 基于复小波变换的遥感图象并行 融合算法 [J]. 计算机工程与科学，2008，30(3)：35-39 [3] 闫敬文. 数字图像处理（MATLAB版）[M]. 国防工业出版社，2007. [4] 曹杰，龚声蓉，刘纯平. 一种新的基于小波变换的多聚焦图象融 合算法[J]. 计算机工程与应用，2007,43(24)：47-50 [5] 任娜，郭敏，胡丽华，张景虎. 基于图象块分割及小波空间频度 的多聚焦图象融合法[J]. 科学技术与工程，2008，8(2)：411-414 [6] 成礼智，王红霞，罗永. 小波的理论与应用[M]. 科学出版社，2006. [7] 蔡娜，姚志强，沙晋明. 基于小波变换的遥感图象融合方式[J]. 莆田学院学报，2008，15(2)：79-82 [8] 胡钢，秦新强，田径. 像素级多传感图象融合技术[J]. 沈阳工 程学院学报，2007，3(2)：148-152 (上接42页)