聚焦爬虫常见算法分析


电脑知识与技术 数据库与信息管理  聚焦爬虫常见算法分析 陈 丽 君 (浙江越秀外国语学院 浙江绍兴 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的小波系数。另 外,为了尽量避免引入噪声,还应进行一致性检测,即若C上某点 的小波系数取自源图像A,而其周围的点均取自源图像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页)
还剩1页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 2 金币 [ 分享pdf获得金币 ] 4 人已下载

下载pdf

pdf贡献者

mringg

贡献于2012-09-29

下载需要 2 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf