主题爬虫的综合型搜索策略研究

主题爬虫的综合型搜索策略研究 主题爬虫的综合型搜索策略研究 摘要 近年来, 伴随着互联网的快速发展, 如何有效获取网络信息和互联网资源的 增长之间的矛盾日益突出。通用搜索引擎简单的宽度优先 或 深 度 优 先 搜 索 策 略 , 由于需要遍历网络中的所有资源, 这使得网络爬虫越来越力不从心, 己经不能满 足人们对个性化信息检索服务日益增长的需要。 近年来, 面向主题的 搜索引擎应 运而生, 它能够提供分类更细致精确、 数据更全面深入的因特网搜索服务, 并且 对硬件要求低、结果更新也很及时。 面向主题搜索引擎的核心组成部分是主题爬虫。 主题爬虫是一种可以自动采 集网页的程序, 其目 标是搜索网络中属于预定主题的那一部分网页子集。 主题爬 虫的搜索策略算法 作为主题搜索引擎技术的关键, 对其进行研究不但可以扩大所 搜索主题的资源覆盖范围, 增加更新频率, 而 且还能有效地提高爬行性能和网络 带宽的利用率。 主题爬虫的关键在于其搜索策略, 其功能是 预测从已爬取页面中抽取的URL 、 与特定主题的相关性, 并提供相关的爬行策略用以指导爬虫的爬行过程。 其中的 启发信息有页面的文本内容, 锚文本, 链接结构, 兄弟链接和URL 结 构等, 它们 对于不同类型页面和不同的特征词有着不同的影响。 因此, 单一的影 响因素作为 启发信息, 其现往往不稳定, 将这些因素综合起来作为启发信息来指导我们的 爬行就变得非常有必要。 本文 在开始介绍 了搜索引擎的概念和基本功能, 分析 了搜索引擎中网络爬虫 模块的作用, 并 基于现阶段国内外网络爬虫的研究进展, 分析现有网络爬虫 不足, 针对通用爬虫的局限性和其对 互联网的迅速发展越来越力不从心, 提出了主题爬 虫的概念。 主题爬虫 的搜索策略是其核心, 也是社会研究的热点技术。 现有的主 题爬虫搜索策略在查全率, 查准率, 鲁棒性等方面存在不足, 本文在分析 这些不 足的基础上, 提出了一种主题爬虫的综合型搜索策略 。 最后, 进行了综合型搜索策略的算法验证 , 结果表明我们的搜索策略在有 较 高的命中率和鲁棒性,以此 验证了我们的综合型搜索策略的有效性。 关键字:搜索引擎;主题爬虫;搜索策略;网页内容;链接结构。 3 Abstract With the rapid development of computer networks, the contradiction between the growth speed of network information and people's ability to access information is increasingly prominent. Traditional search engines have been unable to satisfy people's demand to the growing personalized information retrieval service. In recent years, subject-oriented search engine came into being, which can provide Internet search services with a more detailed classification accuracy and the more comprehensive in-depth data, and it need lower hardware requirements, the results of updating is also very timely The core component of Subject-oriented search engine is the topic crawler. Topic crawler is a program that can automatically collect web pages, the purpose is to search the subset of web pages belong to book topic in network. The crawling algorithm of topic crawler is the key of topic search engine technology and its study can not only expand the search coverage of the topic of resources, increase the update frequency, but also can effectively improve the crawling performance and network bandwidthThe key of its search strategy, and its function is predicted to crawler to take the page from the extract of the URL, and the relevance of a specific topic and provide strategies to guide the crawling reptiles crawling process. A page of information which inspired the text, anchor text, link structure, brothers, links and URL structure, they are different for different types of feature pages and have different effects. Therefore, the single factors as heuristic information, their performance is often unstable, these factors together as heuristic information to guide our crawl becomes very necessaryAt the beginning of this paper, we describes the concept and basic functions of search engine, and based on current domestic and international network of research reptiles, reptiles insufficient analysis of existing networks, for the limitations and common reptiles The rapid development of Internet more and more powerless, put forward the concept of focused crawler. The search strategy focused crawler is its core, the hot technology of social research. Focused crawler search strategies available in4 the recall rate, precision, robustness to the deficiencies, analyzing the basis of these deficiencies, a comprehensive subject search strategy crawler Finally, for a comprehensive search strategy of the algorithms and the results show that our search strategy had a higher hit rate and robustness, this validation of our comprehensive search strategy is effectiveKeywords: search engine; topic crawler; search strategy; web content; link structure 5 目录 THESIS OF MASTER DEGREE. 0 摘要. 3 ABSTRACT. 4 第一章 绪论8 1.1 课 题 背景 及意义. 8 1.2 国 内 外研 究现状. 9 1.3 搜 索 引擎 简介 10 1.3.1 搜 索引 擎的 概念和 功能. 10 1.3.2 搜 索引 擎的 发展历 程11 1.4 课 题 研究 的主要 内 容及组 织安排. 12 第二章 主 题 爬虫 的 技术 要点 分 析13 2.1 网 络 爬虫 CRAWLER 简介 13 2.1.1 Crawler 的概念. 13 2.2 通 用爬 虫模型14 2.2.2 通 用爬 虫的 不足. 16 2.3 主 题 爬虫 模型 16 2.3.1 主 题爬 虫的 原理. 16 2.3.2 主 题爬 虫的 结构. 18 2.4 本 章 小结20 第三章 主 题 爬虫 爬 行策 略设 计 21 3.1 主 题 爬虫 的目标21 3.2 现有基于文本 内容的 爬 行算法. 21 3.2.1 Best-First-Search22 3.2.2 Fish-Search23 3.2.3 Shark search 24 3.3 现 有的基于 WEB 链接的 爬行算法. 25 3.3.1 PageRank 算法25 3.3.2 HITS 算法. 27 3.3.3 SALSA 算法28 3.4 本章小结. 30 第四章 综 合 型搜 索 策略 31 4.1 算 法总 体 设计31 4.2 锚文本模块 32 4.3 特征 向 量模 块 33 4.3.1 页 面 内容35 4.3.2 链接结构 36 4.3.3 兄弟链接39 4.4 综合型搜索策 略的设 计. 406 4.5 本章小结42 第五章 实 验 设计 及 性能 评价. 43 5.1 系统设计与实 现. 43 5.2 搜索策略的评 估. 47 5.2.1 命中率. 47 5.2.2 鲁棒性(robustness )49 5.2.3 页面新鲜度. 50 5.3 实验结果及分析51 5.4 算法的可能改 进. 53 第六章 54 参考文献 55 致 谢 59 7 第一章 绪论 1.1 课题背景及意义 目前, 随着互联网的日益普及和不断发展, 互联网上的信息量 呈 爆炸性式的 增长。 虽然通用搜索引擎的出现很大程度上解决了人们在互联网上查找信息的困 难,但随着Web的发展,通用搜索引擎越来越不能满足用户对于某一主题或学科 领域信息的越来越高的查全率和精度的需求。 主要原因在于, 通用搜索引擎 在爬 行过程中不能分辨网页主题和待访问的顺序, 过多的无关或无意义的页面被爬取 , 而 对网页的内容缺乏细致 有效的分析, 这严重浪费了系统资源和网络带 宽 , 并降 低了爬虫的爬行 效率[1],其主要体现在以下几个方面: 1索引的覆盖率较低 通用 搜索引擎需要面对海量的数据,造成它 的索引数 据 库 的 覆 盖 率 比 较低, 很难索引 到所有的Web 资源。对于用户针对特定主 题提出的特定检索需求,通用 搜索引擎就更难满足较高的覆盖率需求。 相对来说, 由于 主题搜索引擎专注于特 定的领域和技术, 保证了对该领域信息的覆盖率较高的收录与 及时更新, 在提供 专业信息方面 的优势,是大型通用搜索引擎无法比拟的 。 (2)更新频率较低 随着社会节奏的加快, 互联网上的信息增长 很快快并且更新迅速, 造成了通 用搜索引 擎的实时性难以保证。 网络上 信息的有效 在迅速缩短, 由于 通用搜索引 擎对信息漫无边际的抓取 方式, 以及维护庞大的数据信息 的沉重负担, 直接造成 了其数据较长的更新周期。这些都对通用搜索引擎的及时 性 构 成 了 极 大 的 挑 战 , 降低了页面的新鲜度, 使得通用搜索引擎返回的结果 常常是无效的 链接 己经删 除或过时的同一个URL指向的页面发生了改变, 无法满足人们对信息 及时性的 较高需求。 相对来说 主题爬虫有信息的实时性 的巨大优势。 鉴于主题 爬虫爬取的 选择性 , 其抓取的数据量 往往也较小, 因此数据的更新 相对比较容易, 更新速度 比较快。 3 较高的硬件需求 随着 互联网上信息的数量 的指数性增长, 搜索引擎对于硬件 环境的 要求也越 8 来越高。 通用搜索引擎往往需要大量的的内存, 相当数量 的机器同时爬取 才能使 得搜集呈一定规模。 而主题搜索引擎 由于其爬取的绝对 数据量较小, 数据分布集 中( 通常只限于特定领域 ),其对硬件要求 不高,便于管理。 因此, 为 满 足 搜 索 需 求 的 多 样 化 并 进 一 步 提 高 相 关 性 的 要 求 , 主 题 爬 虫 成 为人们研究的热点。 主题爬虫研究的关键在于其搜索策略的研究, 通用爬虫的搜 索策略越 来越显 示出其 局限性, 主题爬 虫的启 发式搜索 策略以 其巨大 的优越性, 越来越成为人们研究的重点。 1.2 国内外研究现状 目前, 对于主题搜索引擎的研究 迅速升温 , 已经成为搜索引擎研究的新 的研 究 热点。 下面介绍一些 国外相应系统的典型 应用: 1. 美国的国家科学数字图馆[2] 的Collection Building ProgramCBP 为数学、 科学、 工程和技术 等项目而创建 了大规模的在线数字图书馆, 并试 图研究在某一主题资源上自动建设数字图书馆的可能性。 CBP 的三个突出的特点 为: 第一, 由于CBP 项目仅仅面向教育、 教学 等领域, 其对主题精确度 (Precision 的要求 比覆盖度Recall 更高; 第二, 在存储上,CBP 并不存储 原文, 仅是提供资源的相关URL ; 第三, 用户仅需输入 关键词,CBP 系统自动将与该主题相关度最高的URL 返 回给查询者。 2.Elsevier 的Scirus系统 为了搜索相关度比较高的科学信息, 设计出了Scirus[2] 科学搜索引擎 , 并且 获得 了2001 年《搜索引擎观察》授予的 ‘最佳专 业搜索引擎’奖。Scirus以其全 面性和高度的综合型, 成为最有影响力的 科技文献门户网站之一。 它只面向包含 有科学内容的网站, 例如作者个人主页和大学以及EISevier 自己的数 据库。 3.NEC 研究院的CiteSeer CiteSeer[2] :作为web上最广泛使用的计算机领域的科学论文检索系统 。 CiteSeer 可以自动地对网上的电子文件PostscriPt 和PDF 等格式 进行索引 和 分类。 它 的核心是ACIAutomaticaly Citation Index 。 4.Berkeley 的Focused Project9 Focused Project 系统通 过两个程序来指导crawler : Classifier (分类器 ) 的功 能是计算待下载信息 与预订主题的相关度值 。Distiller (净化器) , 用 来确定那些 指向很多相关资源的页面 在HITS 算法中,称 之为中心网页 。 在国内, 越来越多的学者也加入到主题搜索引擎的研究之中 。 现在开始研究 该领域的主要是一些大学的研究机构和一些搜索引擎公司。 比如, 百 度等多家搜 索引擎提供商也相应的推出了mp3搜索、 图片搜索、 行业搜索, 北京 化工大学 推 出了关于化工方面的专业搜索引擎,其他方面 如林业、医 药 等 也 有 相 应 的 产 品 。 这些都可以看作是主题式搜索引擎的应用。 1.3 搜索引擎简介 1.3.1 搜索引擎的概 念和功能 搜索引擎search engine 是指根据一定的策略、运用特定的计算机程序搜集 互联网上的信息, 对信息进行组织和处理后, 为用户提供检索服务的系统。 其工 作流程如下图所示: 搜索引擎 主要具 有以下几个功能: (1 )抓取网页 所有的搜索引擎都 有一个网页抓取程序 (crawler ) , 它顺着网页中的超链接, 连续地抓取网页。 互联网中超链接的应用很普遍, 因此在理论上, 从一定范围的 网页出发,就能搜集到绝大多数的网页。 (2 )处理网页10 搜索引擎抓到网页后, 还要做大量的预处理工作, 才能提供检索服务。 提取 关键词, 建立索引文件就是最重要的工作。 除此之外 还包括分析超链接、 去除重 复网页、计算网页的重要度等等。 (3 )提供检索服务 用户输入关键词进行检索, 搜索引擎从索引数据库中找到匹配该关键词的 网 页; 为了用户便于判断, 除了网页标题和URL 外, 还会提供一段来自网页的摘要 和其他信息。 按照信息搜集方法和服务提供方式的不同 ,搜索引擎 大体 可以分为三大类: (1 )目录式搜索引擎 目录式搜索引擎[3] 以人 工方式或者半自动方式搜集信息,由编辑员查看信 息 后人工形成信息摘要, 最后将信息置于事先确定的分类框架中。 信息大多是面 向网站, 主要提供目录浏览服务 与直接检索服务。 (2 )机器人搜索引擎 一个称为 爬虫crawler 的机器人程序以某种策略自动地在互联网中搜集和 发现信息, 索引器为搜集到的信息建立索引, 并由检索器根据用户的查询输入检 索索引库, 最后将查询结果返回给用户。 其服务方式是面向网页的全文检索服务。 (3 )元搜索引擎 元搜索引擎[3] 没有自己 的数据,将用户的查询请求同时向多个搜索引擎递 交 , 再将返回的结果进行重复排除、 重新排序等处理后, 作为自己的结果返回给 用户。 其 服务方式为面向网页的全文检索。 1.3.2 搜索引擎的发展历程 搜索引擎 为使用者 提供一个页面, 包含有搜索框 , 使用者在搜索框 内输入词 语, 由浏览器提交给搜索引擎后, 搜索引擎就会 自动返回与用户输入的内容相关 的信息 。 对于crawler 程序, 为了 追踪互联网的发展规模,MIT Matthew Gray[4] 写出了 世界上 的 第一个crawler 程序World wide Web Wanderer 。 开始它 的 功 能 比 较 简 单 , 仅 被用来统计互联网上服务器的数量, 随着功能的扩展, 它 也具有捕获URL 的能 力 。搜索引擎由爬行器(机器人、 爬虫) ,索引生成器 和查询检索器组成。 随后出现了, 元搜索引擎(MetaSearch Engine[3] ) 。元搜索引擎的工 作模式 11 为: 用户只需提交一次搜索请求, 由元搜索引擎负责转换处理后提交给多个预先 选定的独立搜索引擎, 从各独立搜索引擎返回的所有查询结果, 由元搜索引擎 集 中起来处理后再返回给用户。 Google[7] 的诞生 极大的促进了搜索引擎的发展 ,开始它只是斯坦福大学的 一个小项目。Google 以 网页级别为基础,判断 网页的重要性,提出了著名的 PageRank 算法, 使得搜 索结果的相关性大大增强。Google 进入中文搜 索引擎领域 并迅速发展, 有了中文名称 ‘谷歌’ 。 今年,google 由于各种原因退出 中国市场。 1.4 课题研究的主要内容 及组织安排 由于互联网的迅速发展,通用搜索引擎有效的获取需要的网页已经越发困 难,如何利用基于主题的 搜索方式迅速高效的获得有用信 息 的 需 求 越 来 越 迫 切 。 本文提出一种主题爬虫的综合爬行策略, 提高了爬虫在爬取过程中的命中率,在 一定程度上降低了用户在使用搜索引擎的强度。 最后 实验验证主题爬虫 的搜索算 法。 论文的具体结构安排是: 第一章 讲述本课题研究背景及意义。介绍了搜索引擎的相关知识。提出 了本文所作的主要工作和论文的组织结构。 第二章 介绍了网络爬虫的相关知识,分析了普通网络爬虫 的工作特点和 不足, 在此基础上介绍了针对这些不足的改进 , 最后重点介绍了主题爬虫的工作 原理。 第三章 首先分析了主题爬虫需要解决的问题,分析了主题爬虫的组织结 构和系统结构模型。介绍了现有的主题爬虫的搜索策略,分析其优缺点。 第四章 基于现有的搜索策略, 在综合考虑文本内容和链接结构两大类启 发信息的基础上, 提出一种新型的综合型搜索 策略。 第五章 实验的设计, 分析了现有的网络爬虫的评价标准,并在命中率和 鲁棒性两个标准上,验证我们的搜索策略 的有效性 。 第六章 本文的总结。12 第二章 主题爬 虫的技术要点分析 搜索引擎的工作原理 是,利用网络爬虫Crawler 程序,采用多线程并发搜索 技术, 在web中访问各 个页面, 然后 根据网络 的链接结构提取url , 访问 其他网页, 并 对解析 网页, 提取 页面内容、URL 等信息, 随后由索引器对爬虫所提取的信息 进行排序 后存入索引数据库, 用户 由用户界面 输入需要的信息进行查询, 检索器 根据使用者 提交的关键词在索引数据库中 匹配 相关的信息, 并按照相关度进行排 序输出。 本章首先 介绍网络爬虫相关知识 , 然后介绍通用爬虫的工作原理和不足, 最 后在基于通用爬虫的基础上介绍主题爬虫的工作原理和结构 。 2.1 网络爬虫Crawler 简介 2.1.1 Crawler 的概念 Crawler 被翻译成网络爬 虫, 早期也被成为spider , 是一个利用网络的 链接结 构访问页面,下载保存到本地库中的程序。Crawler 的工作形式是从一 个种子页 面开始, 提取其中的URL 放入待访问队列中, 通过这些URL 到达其它 页面, 重复 以上过程,直到访问完所有页面或者满足某种结束条件为 止。Crawler 作为搜索 引擎中的一个重要部分,分为通用爬虫和主题爬虫。 网络爬虫作为搜索引擎的一个重要组成部分, 对搜索引擎的性能有重要影响。 搜索引擎对我们学习,工作 ,生活上的影响越来越大。根 据 经 验 我 们 可 以 知 道 , 搜索引擎的性能主要 反映在三个方面: 准确 、全面、快捷 [9] 。用 专业术语讲 是: 查准率 (命中率) 、 查全率 (覆盖率) 和 搜索速度 (即搜索耗时) 。 其中最易 达到的是搜索速度, 这是因为对于搜索耗时在1秒以下的系统来说,访问者 很难 辨别其快慢 了, 何况 还有网络速度的影响。 因此, 对搜索引擎的评价就集中在了 前两者:命中率(查准率) 和覆盖率。 对于 中文搜索引擎,‘全面’要求保证不遗漏某些重要的结果, 并且能找到 最新的网页, 这 就需要搜 索引擎中有一个强大的网页收集器, 一般 被 称为 ‘网络 爬虫 ’ 。 这就是本论文所研究的 对象。 把互联网比喻成一个爬虫网,那么 网络爬虫Crawler 就是在网上爬来爬 去的 爬虫。 网络爬虫通过网页的链接地址 寻找网页, 从网站 的某一个页面 (通常是首 13 页 ) 开始, 首先读取网页的内容, 找到网页中的其它链接地址, 然后通过这些地 址寻找下一网页,这样 循环下去,一直到把这 个网站所有 的 网 页 都 抓 取 完 为 止 。 如果把整个互联网 看 成一个网站, 网络爬虫就可以 利用这个原理把互联网上 的所 有 网页都抓取下来。 随着互联网的迅猛发展, 以及相对隔绝的网页的存在, 要抓取互联网上的所 有网页对于 网络爬虫 来说几乎是不可能的, 从目前公布的数据来看, 容 量最大的 搜索引擎也 只不过抓取了整个网页数量的百分之四十左 右[10] 。 其中 有两个方面 的原因: 一方面是抓取技术的瓶颈, 根本无法遍历所有的网页, 有许多网页无法从其 它网页的链接中找到 (可以形象的称之为信息孤岛) ; 另一个 方面是存储技术和处理技术的问题, 如果按照每个页面的平均大小为 20K 计算 (包含图片) , 10亿网页的容量就是10×2000G 字节, 而且即使能够存储, 下载也 会 存在问题(按照一台机器每秒下载20K 计算,则需要340台机器不停的 下载一年 的时间,才能把所有网页 都下载完毕) 。 同时,由于数据量太大,在提供搜索 服务 时也会有效率方面的影响。 因此, 许多搜索引擎的网络 爬虫只是抓取那些 比较重要的网页, 而在抓取的 时候评价重要性 就成为网络爬虫的关键 。 2.2 通用爬虫模型 2.2.1 通用爬虫的结构 网络爬虫 用来搜集搜索引擎所需的信息资源, 因此 是搜索引擎中的核心 部分。 其性能 直接影响着搜索引擎 的整体性能和处理速度。14一般网络爬虫都 需要维护一个URL 队列, 主要 用来存储在已经采集的网页中 抽取的URL 。URL 的 访 问 次 序 一 般 有 : 深 度 优 先 、 广 度 优 先 、 最 佳 优 先[11] 等。 而且 爬虫程序 为了实现其工作目的,必须有以下功能 : 首先, 由于网络信息量巨大,需要用外存来保存待访问队列,因此要有 高效的内外存数据交换功能; 其次, 为了防止已爬取页面重新进入待访问队列,必须有URL 过滤功 能; 另外, 因为需从已爬取的页面中抽取URL 进行 访问, 因此必须具备抽取URL 的功能。 通用爬虫主要由页面采集, 页面分析, 待爬取队列, 页面库等几个 模块组成 [ 图2.2] ,各模块的功能 分别为 : 1.页面采集 :该模块 利用web上页面之间的 特殊链接结构,将待爬取队列 中的首个URL 所对应页 面的下载下来, 以便对该页面进行内容分析和链接的抽取。 2.页面分析 : 页面被抓取以后,要将其内容进行分析,保存,并且抽取其 中的URL , 根据一定的 过滤机制 (例如过滤掉的URL 包含已下载的URL , 已经在 待访问队列中的URL 等 ) ,将过滤后的URL 加 入待爬取队列中。 3. 页面库:已访问页 面的页面信息要存储在页面库中,供以后处理。 4.待爬取 队列: 页面被采集以后,其中的链接被抽取和过滤,剩余超链接 被加入待爬取队列中。当待爬取队列 为空时爬虫程序终止。15 5. 初始URL : 又称种 子(seed )URL ,用来 启动爬虫程序,为首个被爬取 的页面 。 2.2.2 通用爬虫的不 足 通用搜索 引擎加 大的方 便了人们 寻找利 用网络 资源,使 人们的 检索更 有效, 网 络 上 海 量 的 资 源 真 正 对 普 通 用 户 ‘available ’ 。 然 而 , 随 着 网 络 的 迅 速 发 展 , 传 统 的 通 用 搜 索 引 擎 百 度 ,Google 等 的爬虫 , 越 来 越 表 现 出 其 局 限 性[3] , 主 要 有以下几个方面 : 1.覆盖 率的不 足,为 了方面人 们使用 整个网 络资源信 息, 搜 索引擎 总是追 求 尽可能大的网络覆盖率, 随着网络资源的迅速增长 , 爬虫爬取资源能力的有限 性 与无限的 数据资源之间的矛盾越来越 深。 2.通用 爬虫不 能区分 用户的不 同检索 需求。 我们知道 不同领 域的用 户的 检 索目的和需求 往往会有很大的不同, 通用爬虫在爬取信息时不能区分这种差异性, 当然就造成了返回大量对检索者无用的信息。 3. 网络上不同类型的信息大量发展, 不光是以前的文字格式, 音频, 视 频, 图片在网络上大量出现, 丰富了我们的网络, 可用户无法有效使用这些信息, 因 为现有的网络爬虫对这些新的数据结构不能很好的发现,辨别和采集。 4.现在 用户对 特定信 息的需求 猛增, 这种精 细化的信 息比如 ‘10万 元以内 的大众牌的汽车’ 等, 使得爬虫必须具备对特定主题的定向爬取能力, 现有的通 用爬虫无能为力。 面对互联网迅速发展所带来的这些新需求, 新问题, 人们提供了各种解决方 法。例如 百度 公司提 出 的mp3 搜索 和图片 搜索 服务,google 公司 提出 的服务专业 领域用户的学 术文献搜索, 以及现在很多的搜房网, 搜车网都很大程度上解决了 以上人们的需求。 2.3 主题爬虫模型 2.3.1 主题爬虫的原 理 主题爬虫简单来说就是具有主题识别能力的爬虫, 它能够针对某个特定主题 进行网络爬取, 下载那些与主题有关的页面, 对与主题无关的页面则丢弃掉。 这 16 种爬取由 于爬取 的信息 量相对比 较小, 会极大 的扩大相 关主题 的资源 的覆盖度, 同时提高该主题的爬行深度。 我们把互联网看作为一个有向图[12],用GV,E 表示, 其中E 表示有 向图中 的所有超链接的集合,V 为有向图中的所有节点即网络中所有页面的集合。 对于 某个 特定的主题(用特 征词表示) ,所有V 中 的 元 素 可 以 分 为 与 特 征 词 相 关 的 部 分V+ , 以及与该特征词无关的部分V- 。 主题爬虫的爬行从某个节点 (种子节点) 出发, 尽可能多且全面的收集与该特征词有关的节点, 同时又要尽可能的忽略掉 无关页 面(V- 中 的) , 整个过 程是 有向图 的一 个遍历 过程 。而主 题爬 虫就是 沿着 网络中的链接爬取尽可能多的相关页面。 主题爬虫的工作思路是, 根据已获得的或者事先给出的学习信息K , 通过对 页面的文本内容和链接结构的分析, 来预测待爬取节点是否与给定主题 (以特征 词来表示) 相关。 尽可能多的保证我们爬取的页面是与给定主题 相关的, 以提高 主题爬虫 在爬取过程中对页面的命中率。 同时这样也有一个显而易见的好处, 与 主题无关的页面被避免下载,大大节省了网络带宽,使我们的工作更加有效。 通过以上对主题爬虫的特性和工作流程的介绍, 我们可以知道, 一个 高效的 主题爬虫程序的建立,需要妥善解决好以下问题: 首先, 对于页 面是否 是与主题 有关的 判定, 我们通常 都将页 面看作 一个单 一的信息 单位。 仔细分 析发现, 里面包 含了各 种各样的 内容, 比如图 片,视频, 导航链接, 广告链接等。 这些信息丰富了页面内容, 也给网络爬虫的工作带来了 挑战, 使其摒除大量的, 异构性的噪音信息, 进而判断页面属性更加困难。 在这 里, 通常采取的是根据已经下载页面的文字内容, 利用文本挖掘技术来实现其属 性的判别。其次, 对于待爬取队列中URL 的访问次序的确 定。 通用爬虫往往是在有向图 中, 简单的按照广度优先或者深度优先进行爬取。 而主题爬虫将页面下载, 抽取 其中的超链接,过滤后加 入到待访问队列中以后,根据待爬取队列中 各个URL 的母页面内容, 母页面属性, 兄弟链接, 链接结构等相关属性, 按照一定的原则 来判断该URL 与给定主 题的相关度, 并将URL 按相关度进行排序, 优先访问与主 题最相关的URL 。 这是 主题爬虫的爬行策略, 是爬虫的核心部分, 不同的主题爬 虫其主要区别也在于此。17 最后, 是爬取过程中的隧道穿越问题。 现实中的页面出于商业竞争等各种因 素, 常常没有互相直接链接在一起, 在一个个主题团之间是通过与主题无关的页 面链接在一起。 隧道页面的存在会妨碍主题爬虫对相关页面的发现, 影响主题爬 虫的查全率。 因此要 使主题爬虫能够穿越隧道页面[14] 到达另一个与 主题有关的 页面团,提高主题的资源覆盖率。 隧道问题如图所示: 2.3.2 主题爬虫的结 构 通用爬虫的简单的深度优先或者广度优先的爬取, 已经不能适应网络的发展 和人们的需求,在此基础上主题爬虫应运而生。 最初的主题爬虫在通用爬虫的基础上发展而来, 它增加了主题判定模块, 如 果页面与主题特征词相关就存储, 反之就放弃。 这种策略的优点是实现了对主题 资源的爬取, 其缺点也是明显的: 在程序运行过程中, 爬虫仍然需要对整个web 进行遍历, 工作量并没有减少; 另外, 爬虫对最初给定的种子 页面的数量和质量 很敏感, 不同的种子URL 对爬行结果影响很 大, 表现的鲁棒性较弱; 而且在爬行 过程中大量的无关资源仍然被访问和丢弃, 对网络资源和网络带宽的浪费依然严 重。 解决以上问题的关键在于避免大量的无关页面被访问又被丢弃, 这就需要对 待访问URL 进行相关性 预测。 即, 仅访问那些与主题有关的页面。 相关的研究工 作也主要集中在对待访问URL 的主题相关性进 行预测, 并按照一定的策略进行排 序, 使得与主题相关且质量高的URL 优先爬行 。 这是主题爬虫的关键, 也是本文 18 工作的研究核心, 在接下来的第四、 五章中, 本文将详细介绍URL 相 关度 计算和 排序 策略。 下面详细介绍一下主题爬虫的组成结构,其 结构如下图所示。主题爬虫 一般包括三个关键的功能模块, 与通用爬虫相比, 虽然彼此结构类 似, 却多了主题相关性计算和URL 评价模块, 这使得主题爬虫具有了和通用爬虫 不同的目标。 通用爬虫是尽可能多的爬取页面, 需要遍历整个web网络, 主题爬虫 仅仅根 据主题相关性计算, 计算出相关度高的URL 进 行爬取, 遇到不相关的页面则不去 访问。 主题相关性计算和URL 评价模块是主题 爬虫的核心, 也使得主题爬虫比原 来的通用爬虫更加的复杂和有效。 下面介绍这三个功能模块: 第一, 页面采集模块, 这是所有爬虫程序共有的部分, 其主要功能是从待爬19 取队列中抽取URL 评价 得分最高的链接, 将其下载到本地。 其爬行过程中 的爬行 顺序 和爬行策略都由URL 评价模块决定。 该模 块是URL 评价模块与页 面分析和相 关度评价模块 相连接 的部分。 第二, 页面分析 和主题相关性计算模块, 页面被抓取以后, 要将其内容进行 分析, 保存, 并抽取其中的URL , 根据一定的 过滤机制 (例如过滤掉的 URL 包含 已下载的URL , 已经在 待访问队 列中 的URL 等 ) ,将过 滤后的URL 加 入待爬取队 列中。 主题相关性计算模块的任务是对下载页面进行主题相关性判断, 如 果相关 度大于某个阀值,将其存入页面库中,否则丢弃。 第三,URL 评价模块, 该模块 是主题爬虫的核心。URL 评价模块的功能是预 测从已爬取页面中抽取的URL 与特定主题的相 关性, 并提供相关的爬行策略用以 指导爬虫的爬行过程。 如果URL 的评价得分越 高, 其待访问优先权就越高 。 由于 待 访 问队 列中 的URL 数 量 有 一个mix-size ,每次 对 链接 进行 评分 后 ,相 关 度得 分 较低的链接被删除。 可以看出,URL 评价模块 直接决定 着爬虫的爬行效率以及爬 行质量。 2.4 本章小结 本章介绍了网络爬虫的相关 背景知识, 包括网络爬虫的基本概念和相关技术。 对比分析了通用爬虫和主题爬虫的工作流程和组织结构。 通用爬虫曾经极大的提高了人们利用网络资源的便利性和有效性。 随着网络 的发展, 网络资源信息量迅速增加, 通用爬虫的工作方式越来越不能适应迅速发 展的互联网和用户日益精细, 个性化的需求 , 主 要表现在覆盖率较低, 更新较慢 。 针对通用爬虫的问题, 主题爬虫应运而生。 主题爬虫相比于通用爬虫, 由于 只需要爬取特定主题的信息, 而不需要遍历网络上的所有页面, 因此大大减少了 工作量, 提高了相关领域的查全率。 并且由于需要重访的页面数量较少, 使得爬 虫能够以较小代价重访页面,保持了页面的新鲜度 。 主题爬虫与通用爬虫在结构上 最大的不同在于其URL 评价模块, 该模 块是主 题爬虫的核心。 其功能 在于预测从已爬取页面中抽取的URL 与特定主 题的相关性, 并提供相关的爬行策略用以指导爬虫的爬行过程。 对于主题爬虫的相关研究主要集中在该模块, 接下来本文主要针对该模块进 行研究优化。20 第三章 主题 爬虫 爬 行策 略 设计 作为主题搜索引擎中的资源收集工具, 主题爬虫能够按照选定的主题, 在巨 大的网络中, 进行有选择的爬取其中与主题有关的页面和相关链接, 进而 达到定 向爬取的目的。 这种只选择在一个较狭窄的网络区间上爬行方式, 使得爬虫的代 价较小, 并且由于需要访问的页面数量较少, 更容易维护和更新。 与通用爬虫不 同, 主题爬虫并不 追求遍历web上的所有页面 , 而是将目标定为抓取与某一特定 主题内容相关的网页,从而为面向主题的用户查询准备数据资源。 主题爬虫的这些功能来源于其结构中的URL 评 价模块, 这是爬虫程序的 关键。 它能够 预 测URL 与特定 主题的相关 性, 并提供相关的爬行策略用以指导爬虫的爬 行过程。 本章将主要讲述爬虫的相关爬行策略。 3.1 主题爬虫的目标 根据主题爬虫的模型, 主题爬虫 感兴趣的目标可以定义为一组关键词的集合。 为了实现其主题爬取的目标,关键在于 如何 决定待爬行URL 的访问次 序。 通用爬虫的爬行次序是简单的广度优先或者深度优先, 遍历互联网上的所有 页面。 主题爬虫是以相关度的大小进行访问排序, 优先访问相关度比较大的URL 。 由于已被访问的页面, 我们可以获得它的文本内容, 其相关度可以利用文本挖掘 技术判定。 而对于待访问URL , 如何预测URL 的爬行次序, 也即如何判断一个网 页与预订主题的相关度也就成为不同主题爬虫之间的主要区别。 对于主题爬虫目标的衡量 , 主要通过命中率[15] 。 即爬取的与主题相 关页面 数目与爬取页面总数的比 。 用公式表示为:已爬取的与主题相关页面数 命中率 ×100% 公式3.1 爬取的页面总数 3.2 现有基 于文 本内 容的 爬行 算法 主题爬虫 的待 爬取URL 队列的优 先级 计算 , 是 主题爬行 中 最 为核心 的 部分, 也是主题爬行算法的关键。 页面采集模块负责下载优先队列中最前面的URL 对应 21 的页面, 然后页面解析模块从该 页面中解析出新的URL 链接, 然后根 据种种启发 信息 进行URL 待访问 优 先级 的排序,即爬虫需要确定下一个被访问的URL 。 理想情况下, 主题爬行程序 的目标是将所有与主题相关 的页面下载, 并且避 免下载所有主题无关页面。 因此 ,URL 评价策 略的制定就非常重要。 对 主题爬行 的研究 大都 集中在这 一方面, 它反映了主题爬虫 的爬行策略。 爬行策略的制定主 要基于两大类启发信息:链接结构和文本内容,下面分别介绍相关爬行算法。 已访问页面的文本内容可以用来评判页面与主题的相关度, 也可以作为预测 待爬取URL 相关度的启 发信息。 基于文本内容的爬行算法充分利用页面中的文本 内容作为启发信息指导搜索, 并根据页面或者链接文本与特定主题间的相关度来 评价URL 的相关度, 进 而决定待访问的次序。 比较著名的有Best-First-Search[16] , Fish-Search 和Shark-Search[17] 算法。 3.2.1 Best-First-Search Best-First-Search 算法的 原理是 给定一个待爬行 的URL 队列, 从中挑选 最好的 URL 优先爬行。 用关键 词的集合来描述爬行的主题, 未被访问的URL 的待访问优 先级要通过 已爬取页面的文本信息和主题词集合来计算, 根据这两者之间的相关 度来评价其所指向的URL 与主题的相关程度。 相关度越大的URL , 其 所 指向的网 页的待访问优先级别就越高, 在爬虫程序中也就更加优先被爬取 。 待访问队列有 mix-size , 按照优先程 度对待访问URL 进行排 序, 只保留前mix-size 个URL , 其余 的进行删除。 网页与相关度计算如下: n ? w ×w lk mk k?l?m siml ,m公式3.2 n 2 n 2 ?? ? w w k?l lk k?m mk 这里面, m 为代表主 题主题的关键字的集合, l 为页面链接的文本内 容的集合, 集合j 中单词k对特定主题的影响程度我们用w 表示。w 的数值由下式计算[16] : jk jk tftk,p N w ?log 公式3.3 jk n ? tfti,p nk i1 其中 , 主题tk 在p 中 的 频 率 用tftk,p表示 ,N 为 文 档 集 中 的 所 有 文 档 数 ,nk 表示tk出现的文档数。22 由此我 们可 以看出 ,Best-First-Search 算法 的核 心在于 ,由 链接的 文本 内容, 关键词集合, 主题之间的相关度, 来预测URL 相关度的高低, 并进而决定爬行策 略。 这种算法的优点是具有较明了的数学理论支持, 适用于主题数量较少, 算法 的复杂度低,并 且在距离相关页面集较近的地方搜索。 Best-First-Search 算法的 缺点是页面中的 文本内容没有全局性, 并且 , 主题关 键词集合由于是全部词集的子集, 造成了所爬取的网页不能代表整个网络的情况。 J.Ccho 在提出该算法时,将URL 的待访问队列 分为related _queue 和unrelated _queue 两大类,related _queue 用来存放相关性 的, 并优先爬取 (如果 在锚文本或 者URL 字符串含有关键 词时,则认为是相关的);unrelated _queue 用 来存放普通 URL ,在程序运行中, 只有当related _queue 为 空时, 才爬行unrelated _queue 。 在 爬 行 过 程 中 , 分 别 用 来 存 储 待 访 问 URL 和已访问URL 的是uncrawled _queue 和crawled _queue 两个堆栈 。 Best-First-Search 算法影 响深远, 以后的算法往往将其作为算法性能比较的基 准。 3.2.2 Fish-Search Fish-Search 算法 是由De Bra[17] 等在早期提出 来的一种比较 有代表性 的算法。 Fish-Search 算法有一个 比较有趣的模型, 主题爬虫的初始爬取URL 需 要被提供种 子页面。Fish-Search 算 法中, 主题爬虫爬取页面的过程被模拟为海中鱼群的觅食 过程,主 题爬虫 代表鱼 群fish,主 题爬虫 寻找 到主题相 关页面 代表鱼 群寻找到了 食物, 如果经过一段时间鱼群没有寻找到食物, 即主题爬虫在某个方向上 经过几 个链接仍然没有找到主题相关页面, 鱼群就会被饿死。 水污染 (带宽限制) 等也 会造成鱼群的死亡。 假如鱼群找到了与主题相关的页面, 其子节点的遍历深度与 该页面的遍历深度相同。 假如没有找到与特定主题相关的页面, 就相当 于鱼群没 有找到自己的食物, 就会越来越弱, 这个链接子节点的遍历深度就会被设 置成母