（计算机应用技术专业论文）网站聚焦爬虫研究.pdf

摘要 近年来，随着互联网的快速发展，网络信息呈指数级的增长，这种信息量的 飞速增长对通用网络爬虫和搜索引擎呈现了空前的挑战，越来越多的人希望能够 快速且有效地找到白己所需要的信息。聚焦爬虫是一种面向主题的信息搜集系统， 可以根据用户需要从互联网上自动搜集到主题相关信息，在主题搜索引擎、站点 结构分析等方面取得越来越广泛的应用。 传统的聚焦爬虫抓取的目标是与某一特定主题内容相关的网页，而在有些应 用中，如网络目录，更多的是给用户提供主题相关网站。随着互联网信息的日益 增多，目前靠人工来维护的网络目录越来越显得低效和不可行。为了实现具有自 动维护功能的网络目录，将抓取目标锁定为主题网站的网站聚焦爬虫应运而生 网站聚焦爬虫是在现有聚焦爬虫的基础上加入网站选取和分类机制，从用户 提供的种子网站开始，以b e s t - f w s t 原则获取最佳候选网站并开始新一轮的爬行分 类。本文进行了面向中文网站的网站聚焦爬虫的设计与实现，详细介绍了其各部 分的功能和设计原理。实验表明该爬虫能有效的获取主题网站，为实现自动网络 目录提供了一种解决方案。 与传统网站聚集爬虫不同的是，本文介绍的网站聚集爬虫引入了一种改进的 外部爬行策略，即在传统外部爬行策略只考虑平均跨站链接权重的基础上引入网 站的跨站链接数以进行候选网站的选取。实验结果表明，改进外部爬行策略后的 网站聚集爬虫能够优先访问候选网站队列中的权威主题网站，并能进一步提高获 取主题网站的准确率。 关键词：网站聚焦爬虫网站分类w e b 挖掘 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ew o r l dw i d ew e bi nr e c e n ty e a r s ，i n f o r m a t i o ni n t h ei n t e m e tg r o w t he x p o n e n f i a l l y t h i sr a p i dg r o w t hp o s e su n p r e c e d e n t e ds c a l i n g c h a l l e n g e sf o rg e n e r a l - p u r p o s ec r a w l e r sa n ds e a r c he n g i n e s m o r ea n dm o r ep e o p l e h o p et oa c h i e v et h ei n f o r m a t i o nt h e yn e e dq u i c k l ya n de f f e c t i v e l y f o c u s e dc r a w l e ri sa s u b j e c t - o r i e n t e di n f o r m a t i o nr e t r i e v a ls y s t e m i tc a l lm e e tt h et l $ e r $ n e e da n dr e t r i e v e i n f o r m a t i o nt h a ti sr e l e v a n tt os o m e s p e c i f i cs u b j e c t sf r o mt h ew e ba u t o m a t i c a l l y t r a d i t i o n a lf o c u s e dc r a w l e ri s t a r g e t i n gw e bp a g e st h a ta r er e l e v a n tt os o m e s p e c i f i ct o p i c s b u ts o m ea p p l i c a t i o n s ，s u c ha sw e bd i r e c t o r y , a r ep r o v i d i n gu s e r sw i t h r e l e v a n tw e b s i t e s w i t ht h er a p i dg r o w t ho ft h ew w w , w e bd i r e c t o r yw h i c hm a i n t a i n e d m a n u a l l ya r eb e c o m i n gm o r ea n dm o r ei n e f f i c i e n ta n du n a v a i l a b l e t oi m p l e m e n taw e b d i r e c t o r yw h i c hc a nm a i n t a i na u t o m a t i c a l l y , f o c u s e dw e b s i t ec r a w l e rw h i c hr e t r i e v e o n l yr e l e v a n tw e b s i t ea p p e a r e d f o c u s e dw e b s i t ee r a w l e ri sb u i l to nt h ef o u n d a t i o no fat r a d i t i o n a lf o c u s e dc r a w l e r w i t hw e b s i t es e l e c t i n ga n dc l a s s i f i c a t i o ns t r a t e g y s t a r t i n gf r o mt h es e e dw e b s i t e ，t h e c r a w l e rp i c k so u tt h eb e s ts i t ef o l l o wt h eb e s t - f i r s tr u l ea n ds t a r t se a c hc r a w l i n gp r o c e s s w ed e s i g na n di m p l e m e n tac h i n e s ew e b s i t eo r i e n t e df o c u s e dw e b s i t ec r a w l e ri nt h i s p a p e ra n di n t r o d u c et h ef u n c t i o na n dp r i n c i p l eo fm a i nc o m p o n e n t s e x p e r i m e n t d e m o n s t r a t et h a tt h ef o c u s e dw e b s i t ec r a w l e rc a l lr e t r i e v er e l e v a n tw e b s i t ee f f e c t i v e l y , a n dp r o v i d e sas o l u t i o nt om a i n t a i nt h ew e bd i r e c t o r ya u t o m a t i c a l l y d i ! f f e r e n tf r o mt h et r a d i t i o n a lf o c u s e dw e b s i t ec r a w l e r , t h eo n ei n t r o d u c e di nt h i s p a p e ri n v o l v e sam o d i f i e de x t e r n a lc r a w ls t r a t e g y , w h i c hn o to n l yu s et h ea v e r a g e w e i g h to ft r a n s v e r s a ll i n kb u ta l s ot h en u m b e ro ft r a n s v e r s a ll i n kt oc h o o s ec a n d i d a t e w e b s i t e e x p e r i m e n td e m o n s t r a t e st h a tt h ea f t e rm o d i f yt h ee x t e r n a lc r a w ls t r a t e g y , f o c u s e dw e b s i t ec r a w l e rc a l lv i s i ta u t h o r i t a t i v ew e b s i t ef i r s ta n dt h e a c c u r a c yo f r e t r i e v i n gr e l e v a n tw 曲s i t ee 1 1 1 l a u c e d k e y w o r d s ：f o c u s e dw e b s i t ec r a w l e r w e b s i t ec l a s s i f i c a t i o nw e bm i n i n g 2 独创性声明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含 为获得江西财经大学或其他教育机构的学位或证书所使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 签名：到选疆日期：趟：垡丝 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阕；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后遵守此规定) 签名：盔li 查咯 导师签名：墨迓 日期：a 彰：盆：举 1 绪论 1 绪论 1 1引言 随着网络的迅速发展，互联网成为大量信息的载体，如何有效地提取并利用 这些信息成为一个巨大的挑战。搜索引擎( s e a r c he n g i n e ) ，例如传统的通用搜索引 擎百度【”、y a h o o 2 和g o o g i e 3 等，作为一个辅助人们检索信息的工具成为用户访 问互联网的入口和指南。 网络爬虫( w e bc r a w l e r ) 是一种利用w e b 图结构从一个网页访问到另一个网页 的程序，又称为“网络机器人”、“网络蜘蛛”等。网络爬虫是搜索引擎的关键模块 之一，其目的是检索网页并将它们添加到当地的库中。网络爬虫的工作过程是： 从一个初始种子页开始，利用该页的外部链接访问其他新的网页，新的网页又提 供更多的外部链接。反复该过程，直到检索了足够多的网页或者达到了某个结束 条件为此。 通用搜索引擎希望搜索到的网页所涉及的范围尽可能广，它们使用网络爬虫 来维护索引数据库。这些爬虫任意的爬行网页，他们的目标是内容全面。这就导 致通用性搜索引擎存在着一定的局限性，如： ( 1 ) 通用搜索引擎试图满足各类用户的查询需求，所搜集的网页内容广而泛 【4 】，随着信息多元化的增长，用户对信息的需求往往是针对特定主题的1 5 1 ，因此 通用搜索引擎往往包含大量用户不关心的网页。 ( 2 ) 通用搜索引擎的目标是尽可能大的网络覆盖率，有限的搜索引擎服务器 资源与无限的网络数据资源之间的矛盾将进一步加深同。 ( 3 ) 互联网数据形式的丰富和网络技术的不断发展，图片、数据库、音频视 频多媒体等不同数据大量出现，通用搜索引擎往往对这些信息含量密集且具有一 定结构的数据无能为力，不能很好地发现和获取。 针对这些情况，需要一个分类细致精确、数据全面深入、更新及时的面向主 题的搜索引擎i 一，而定向抓取相关网络资源的聚焦爬虫正是主题搜索引擎的基础 与核心阐。聚焦爬虫是一个自动下载网页的程序，它根据既定的抓取目标，有选 择的访问互联网上的网页与相关的链接，获取所需要的信息。与使用广度优先搜 索策略的通用爬虫( g e n e r a lp u r p o s e w e b c r a w l e r ) 不同，聚焦爬虫并不追求大的覆 盖，而将目标定为抓取与某或多个特定主题内容相关的网页，通过最佳优先搜 索策略，仅需访问很少一部分网络资源，即可很好的实现主题网页的收集，为面 向主题的用户查询准备数据资源。聚焦爬虫可以避免访问w e b 中不相关的网页， 从而节省硬件和网络资源。近几年在面向主题的搜索领域中，聚焦爬虫受到了极 网站聚焦爬虫研究 大的关注【9 ，1 0 ，1 1 ，1 2 ，1 3 ，通用性搜索引擎g o o g l e 、百度和y a h o o 纷纷使用 聚焦爬虫来实现其主题搜索服务。 聚焦爬虫根据搜集对象的不同而分为不同类型。目前聚焦爬虫主要的搜集对 象是主题相关网页，在有些应用中，用户更希望获取的是与某一特定主题内容相 关的网站，如网络目录。 网络目录( w e bd i r e c t o r y ) 是一个根据主题分类的网站导航。目前g o o g l e 、y a h o o 和r ) m o z t ”j 为三个主要的人工网络目录提供商，就g o o g t e 的网页目录来说，针对 某一主题，g o o g l c 仅能提供很少数量的主题网站，而且所有主题全部靠人工来实 现网站的增加、删除和更新。如图1 1 所示，g o o g l e 网页目录中“人工智能”子目 录仅包含9 个主题相关网站，用户选择度小。由于所有目录全靠人工来维护，不 免带来了更新周期长、主题网站少等问题。随着互联网信息的日益增多，光靠人 工来维护的网络目录越来越显得低效和不可行，很多时候无法满足用户的需要。 为了实现具有自动维护功能的网络目录，将抓取目标锁定为主题网站的网站聚焦 爬虫应运而生。 图1 1g o o g l e 的网络目录 网站聚焦爬虫是在现有的聚焦爬虫基础上加入网站选取和分类机制实现的。 根据预定的主题类别对网站聚焦爬虫中的分类器进行训练后，仅需提供少许主题 网站，网站聚焦爬虫即能在互联网上展开主题网站的搜索。这样可以大大缩短网 络目录的更新周期，降低维护成本。本文详细介绍了网站聚焦爬虫各部分的功能 和设计原理，并在此基础上进行了系统实现。实验表明该爬虫能有效的获取主题 网站，为实现自动网络目录提供了一种解决方案。通过系统实现笔者发现，现有 的网站聚焦爬虫在从候选网站队列选取网站时，仅通过网站的平均跨站链接权重 来确定候选网站的排名。这种外部爬行策略过于简单，导致抓取回的网站权威性 不够，并且抓取结果准确率不高。因此本文针对此问题引入一种改进的外部爬行 2 1 绪论 策略，在选取候选网站时即考虑到网站的平均跨站链接权重，又兼顾到跨站链接 数，优先抓取候选网站队列中即贴近主题又相对权威的网站。实验表明，改进后 的网站聚焦爬虫获取主题网站的准确率更高，并且更权威。 由于网站聚焦爬虫是一种以网站为抓取目标的聚焦爬虫，唯一的不同是网站 聚焦爬虫加入了网站选取和网站分类机制，它是聚焦爬虫发展到一定阶段的产物。 因此在介绍网站聚焦爬虫之前，先对聚焦爬虫的发展作个简单回顾。 1 2 聚焦爬虫的研究现状及相关工作 最早的聚焦爬虫是在【1 5 】里提出的，该论文描述了一个基于客户的实时的、 深度优先的文本检索系统。使用一池鱼作为比喻，多个线程用于跟踪网页链接。 “鱼”基于关键词和规则表达式的匹配，从相关网页跟踪更多的链接。作者认为该 类系统对网络造成了很大的负载，因此提出了各种缓存技术来解决这些问题。和 1 6 1 d p 提出的s h a r k - s e a r c h 算法一样，这两种算法都是通过关键字匹配的方法来搜 集主题网页。 1 7 】中描述了一个改进的b e s t - f i r s t 爬行策略，因为主题相关信息有时只有通 过先访问非主题相关网页才能够达到，文中提出即使遇到非主题相关网页也以一 定的策略继续爬行，也即通过使用t u n n e l i n g ”技术来克服b e s t - f i r s t 爬行策略存在 的缺陷。 【1 3 】中介绍的聚焦爬虫根据一个主题目录和用户指定的初始网页来描述抓取 目标，并在用户浏览过程中，将用户标注的感兴趣网页放入相应的主题目录，修 改主题样本。系统的两个主要部分是网页分类器和提取器( d i s t i l l e r ) 。两页分类器 负责学习抓取目标的特点，计算网页的关联度，并过滤网页。提取器负责计算网 页的重要程度，发现中心型网页( h u bp a g e ) ，并由此动态决定网页的访问顺序。 另一类聚焦爬虫在【9 】中提出。该论文里提出通过先抓取更重要的网页使爬行 更有效。他们提出了各种测量网页重要性的方法，如：网页与查找项的相关性， 指向该页的的网页个数( b a c k l i n k s ) ，该网页的p a g e 髓n k 值和该网页所处的位置。 一个网页的p a g e r a n k 被递归地定义为指向该网页的所有网页的p a g e r a n k 权值之 和。他们使用了基于这些重要性测量的排序机制实现了c r a w l e r ，该c r a w l e r 对斯 坦福大学的网站伏约2 2 5 ，0 0 0 个网页) 进行了测试。他们发现使用b a e k l i n k 重要 性测量的c r a w l e r 类似深度优先查找，在继续访问前先访问特定簇里的网页，并经 常受起始点左右。而使用p a g e r a n k 的c r a w l e r 却不受起始点影响，并结合了宽度 优先和广度优先，能更好地爬行。他们也发现在小域中，如网页的子集中，使用 b a e k l i n k 计数的c r a w l e r 执行效果不好。 1 8 】中网页相关性和u i 也访问优先级由不同的模型设定。用于评估网页相关 网站聚焦爬虫研究 性的模型能够输出分类信息，而u r l 排序模型则通过样例主题网页训练得到 【1 6 】描述了一个使用主题爬行的站点映射应用。c r a w l e r 从一个特定点开始并 跟踪相关文本的链接。它使用向量空间模型来计算特定网页和查找项的相关性， 子页继承父页的相关性成绩，并通过一些衰减系数修改。他们也使用链接周围的 文本以及链接文本本身来决定访问哪个链接。该论文是对 1 5 】里所描述的算法的 改进。 主题爬行在隐藏w e b 中的应用可见 1 0 】该应用的目标是能够访问隐藏的内 容。研究者们提出了一个任务明确，人工辅助的方法，建立了一个h 1 w e ( h i d d e n w e be x p o s e r ) 系统。他们建模了一组( 元素，域名) 对的集合，并决定了基于标签， 表单安排的合适的输入值。标签值设置使用了显式的初始化，内嵌式的分类，包 装的数据源和爬行经验。该c r a w l e r 在更大的表单中( 更多的描述性标签和有限的 域中) 执行的效果越好。 【1 9 是一篇评价不同爬行策略的文章。每一百个主题建立一个分类器，用于 评价己爬行过的网页。作者认为一个好的主题c r a w l e r 在向量空间中也应该保证主 题相关。他们画了一个随时间变化的抛物线图，根据c r a w l e r 是否能保持主题相关 来评价一个c r a w l e r 的性能。文中评价了三个不同爬行策略的c r a w l e r ，最后发现， b c s t f i r s t 执行效果最好，其次是l n f o s p i d e r s 例，最后是p a g e r a n k 。研究者认为 p a g e r a n k 在主题爬行任务中过于全面，所以效果不好。 【2 1 】提出了使用上下文图表来引导主题c r a w l e r 。作者认为该领域主要的问题 是在爬行中把任务分配给网页。例如：一些偏离主题的网页指向符合主题的网页， 结果形成页层次结构。基于这些问题，提出了基于上下文的c r a w l e r 。基于上下文 的c r a w l e r 使用一个通用的搜索引擎来获取链接到专门文本的网页，并为该文本建 立上下文图表。该上下文图表用于培训一组分类器，根据与目标的链接距离的预 测值将文本归类。每个种子页都有相应的上下文图和分类器，并能够逐层建立直 到特定的等级，这样，c r a w l e r 能够获取与目标主题直接或间接相关的内容，以及 通向目标的非常简单的路径模型。与普通的宽度优先和传统的主题c r a w l e r 相比， 上下文主题c r a w l e r ( c f c ) 的每一层都使用贝叶斯分类器，最先使用最短路径。使 用的评价机制是下载的相关网页的比率。实验表明，c f c 维护了更高的相关性。 2 2 1 中使用基于o n t o l o g y 的算法来计算网页相关度。算法通过预处理，从网 页中抽取出实体，最终网页相关度通过使用o n t o l o g y 图来预测。 【2 3 】提出了聚焦爬虫在爬行的时候学习链接结构。这包括在该网页中寻找专 门的特征，这些特征使得该网页更符合某个给定的主题。这些特征包括网页内容， u r l 结构，链接结构等。作者认为在爬行中使用链接结构学习比那些标准的预定 义的结构更通用。 4 1 绪论 2 4 1 提出了w e b 主题管理系统( w a m s ) 。他们使用了主题爬行技术，只下载相 关网页附近的网页( 如双亲，孩子和兄弟) 。这是基于对网页的向量空间表示 c r a w l e r 下载所有包含主题关键词的u r l s 。最后，它为每个特定的类固定了一个 相关性阈值，如果相关性值下降到某个特定值，将停止下载。该论文的另外一个 方面是使用基于h u b s 和a u t h o r i t i e s 对站点进行逻辑分组的方法，讲述了如何可视 化主题。 【2 5 】提出了使用加强学习的方法建立专门域的搜索引擎。贝叶斯分类器根据 整个网页的文本和链接文本对超链接进行分类。这样为每个链接计算出了奖励值， 用于通过加强学习的方法来培训c r a w l e r 。通过对计算机系站点的测试表明，与普 通的宽度优先c r a w l e r 相比，聚焦爬虫在更少的时间里发现了更多的研究论文。 在【2 6 】的研究报告里表明，宽度优先查找在爬行中能更早地发现高质量网页。 实验使用了m e r c a t o rw e bc r a w l e r 和一个链接服务器，下载了3 0 0 ，0 0 0 ，0 0 0 个网 页。如【1 1 】中提出的一样，使用p a g e r a n k 作为网页质量的测量方法，大部分重要 网页有许多来自不同主机的链接，不管起始点在哪里，这些网页被发现的时间较 早。 【2 7 】中马亮等设计的中文信息主题搜集系统在对已搜集页面的主题相关度评 价时综合考虑了页面的标题、段落标题、a n c h o r 文本等对于页面评价具有较高价 值的特征区域，并赋予了相应权重系数，以提高评价结果的准确性。 【2 8 】通过记录用户在浏览到感兴趣的网页时，点击“有用”按钮的行为，记录 下相关网页，为用户建立测览模型。之后，系统对经过标注的网页进行l s i 聚类， 根据聚类结果构建概念图，表示不同类别之间的联系。这样，系统就可以利用不 同网页间的链接关系，学习用户的浏览行为。 根据搜集目标的不同，聚焦爬虫可以进行细分，有两类重要的聚焦爬虫，即 为：面向主题网页的聚焦爬虫和面向主题网站的聚焦爬虫。前者搜集的对象仅为 主题网页，而在有些应用中，用户更希望获取的是与某一特定主题内容相关的网 站，后者即为以主题网站为搜集对象的网站聚焦爬虫。 文献【2 9 】针对网站分类这一问题提出了几种网站分类方法，它们包括：将整 个网站看作一个大h t m l 文本，然后使用现有的分类方法对它进行分类；将整个 网站视为由用户所定义主题构成的主题树，并使用马尔可夫( m a r k o v ) 树模型来进 一步分类。这些方法均要求用户事先定义好所有的主题类，并为每一类准备充足 的训练数据。这样对用户来说开销太大而不常被实际应用所采纳。并且其中没有 提出网站聚焦爬虫这一概念。 m a r t i ne s t e r 在文献【3 0 1 提出了一个基于两级体系结构的网站聚焦爬虫，内部 爬虫0 n t e m a lc r a w l e r ) 与传统聚焦爬虫相似，唯一的不同是它只在指定网站内邝根 5 网站聚焦爬虫研究 据内部爬行策略( i i l t e m a lo - a w ls t r a t e g y ) 进行主题网页的搜集。而外部爬虫将整个 w e b 视为以网站为顶点的图，它根据外部爬行策略( e x t e r n a lc r a w ls t r a t e g y ) 从该图 中挑选最佳候选网站并调用内部爬虫。 聚焦爬虫的发展很大程度上依赖于文本分类技术的发展。大多数的文本分类 算法都是基于向量空间模型的。向量空间模型将每篇文档表示为一个词频向量。 由于构成文档的词汇数量相当大，因此文本向量空间的维数也相当大，从而造成 许多基于向量空间模型的文本分类方法性能不佳。不受高维问题影响的方法在文 本分类中应用得很成功，如朴素贝叶斯方法( n a i v eb a y e s ) ，支持向量机( s v m ) 以 及中心文本分类算法( c e n t r o i d b a s e dt e x tc l a s s i f i c a t i o na l g o r i t h m ) 。 1 3 研究的目的及意义 网站聚焦爬虫主要的应用是网络目录( w e bd i r e o o r y ) 。到目前为止，g o o o e 、 y a h o o 和d m o z 等网络目录提供商都是通过人工的方式收集主题网站，随着互联 网信息的日益增多，这种靠人工来维护的网络目录越来越显得低效和不可行。就 g o o g l e 的网络目录来说，针对某一主题，g o o s e 仅能提供很少数量的主题网站， 很多时候无法满足用户的需要。而网站聚焦爬虫是在现有聚焦爬虫的基础上加入 网站选取和分类机制，使其能够自动分类并搜集主题网站。可见网站聚焦爬虫的 研究和实现将会是一个很有实用价值的课题。 本文针对传统爬虫外部爬行策略设计过于简单的问题引入了一种改进的外部 爬行策略，使得改进后的网站聚集爬虫更倾向于抓取权威网站，并且获取主题网 站的准确率也得到进一步提高，相信本文设计和实现的网站聚集爬虫是有一定的 实用价值。 1 。4 论文的主要工作和组织结构 本文详细介绍了面向中文网站的网站聚焦爬虫的设计与实现，并引入了一种 改进的外部爬行策略。系统运行结果表明，该网站聚焦爬虫能很好的用于主题网 站的自动搜集，以实现自动网络目录。通过外部爬行策略改进前后的对比实验发 现，改进后的网站聚集爬虫能够优先访问候选网站队列中的权威主题网站，并能 进一步提高获取主题网站的准确率。 本论文安排如下： 第一章主要介绍聚焦爬虫的研究背景和相关技术发展现状，以及论文的研究 目标； 第二章主要剖析聚焦爬虫的原理和结构、聚焦爬虫与通用爬虫的区别、网页 聚焦爬虫与网站聚集爬虫的区别以及聚集爬虫相关技术； 6 1 绪论 第三章详细介绍了本文的主要创新点，即改进的外部爬行策略，以及网站聚 焦爬虫各主要模块中所要用到的其它关键算法，包括内部爬行策略、网页处理与 分类算法、网站分类算法等； 第四章通过系统运行结果说明了系统的可于亍性，并通过实验再次验证了改进 的外部爬行策略优于传统的外部爬行策略这一结论。 第五章是总结与展望。 7 网站聚焦爬虫研究 2 聚焦爬虫及相关技术 最早的网络爬虫其目的是在给定爬行周期内，尽可能多地下载w e b 网页，即 所谓的通用爬虫。当面临着w e b 网页发展规模和数量成几何增长的现实时，要想 在爬行网页时既保证网页的质量和数量，又要保证网页的时效性显然已经是力不 从心了。于是，网络爬虫的设计目的就变成了在给定的爬行周期内尽可能多地爬 行高质量的网页，并且保持网页的时效性。而聚集爬虫在上述设计目的的基础上， 还考虑了网页与主题的相关度，尽可能多地下载相关网页，尽可能少地下载无关 网页，提高主题资源的覆盖度。 由于相关主题资源的规模相对整个互联网来说要小得多，也相对容易控制和 掌握，所以聚焦爬虫可以提供更精确的搜索结果。但相对通用爬虫来说，聚焦爬 虫还需要解决以下两个主要问题： ( 1 ) 为了提高爬行效率，聚焦爬虫需要解决如何从待爬行u r l 队列中挑出最 可能包含主题相关信息的网页进行爬行； ( 2 ) 对于每个已下载的网页，聚焦爬虫需要判断它与主题的相关性，用来指 导以后的爬行过程。聚焦爬虫应尽量避免爬行主题不相关的和低质量的网页。 可见，聚焦爬虫是网络爬虫的特例。下文开始对网络爬虫的发展做一个简单 的回顾，并简要介绍一下聚焦爬虫及其相关技术。 2 1 通用网络爬虫模型 2 1 1 通用网络爬虫结构 作为搜索引擎的基础组成部分，网络蜘蛛起着举足轻重的作用，它的性能好 坏直接影响着搜索引擎整体性能和处理速度。随着应用的深化和技术的发展，网 络蜘蛛越来越多的应用于站点结构分析、内容安全检测、页面有效性分析、用户 兴趣挖掘以及个性化信息获取等多种服务中。 具体来说，网络爬虫是一个自动提取网页的程序，它为搜索引擎从互联网上 下载网页。通用爬虫从一个或若干初始网页的u r l 开始，获得初始网页上的u r l ， 在抓取网页的过程中，不断从当前页面上抽取新的u r l 放入队列，直到满足系统 的一定停止条件。 通用爬虫基本流程图如图2 1 所示，体系结构如图2 2 所示。 其各个模块的主要功能介绍如下： ( 1 ) 页面采集模块：该模块是网络爬虫和互联网的接口，主要作用是通过各 种w e b 协议( 一般以册t p ，f t p 为主) 来完成对网页数据的采集，然后将采集到 8 2 聚焦爬虫及相关技术 的页面交由后续模块作进一步处理； ( 2 ) 页面分析模块：该模块的主要功能是将页面采集模块采集下来的页面进 行分析，提取其中满足用户要求的u r l ，加入到u r l 队列中。页面链接中给出 的u r l 一般是多种格式的，可能是完整的包括协议、站点和路径的，也可能是省 略了部分内容的，或者是一个相对路径。所以为处理方便，一般先将其转化成统 一的格式； ( 3 ) 链接过滤模块：该模块主要是用于对重复链接和无效链接进行过滤； ( 4 ) 页面库：用来存放己经爬行下来的页面，以备后期处理； ( 5 ) u r l 队列：用来存放经链接过滤模块过滤得到的u r l ，并不断的为页面 采集模块提供u r l ，当u r l 为空时爬虫程序终止； ( 6 ) 初始u r l ：提供u r l 种子，以启动爬虫。 图2 1 通用爬虫基本流程图 图2 2 通用爬虫体系结构 9 网站聚焦爬虫研究 2 1 2 通用网络爬虫的主要技术问题 和传统的信息媒介相比，w e b 主要有以下几个特点： ( 1 ) 信息容量的超大规模，截止到2 0 0 3 年7 月，i n t e m e t 上的网页数量就已 经超过3 0 亿，上网用户数量超过5 2 亿，而且网页还在以每天7 0 0 万的速度增加； ( 2 ) w e b 的动态性，w e b 的内容和结构每天都在变化着； ( 3 ) w e b 的异构性，w e b 中包含的文件类型各种各样，包括文本、声音、图 像、图片以及活动脚本等； ( 4 ) 页面内容的重复性，最近的研究表明，有大约3 0 的页面是重复的； ( 5 ) 链接特性，每个页面拥有超过8 个指向别的页面的链接； ( 6 ) 多语种性，现在w e b 上的页面语种超过了1 0 0 个。这些特征为w e b 信息 的有效提取，提出了巨大的难题。从技术角度来看，通用爬虫存在以下几个问题： 第一，w e b 信息容量的巨大使得通用爬虫不可能提取所有的w e b 页面，即使 能够全部提取，也没有足够大的空间来存放。如何提高页面提取的效率，即在单 位时间内采集到尽可能多的高质量页面，是通用爬虫面临的难题之一。 第二，并行页面提取的问题。页面的提取速度是通用爬虫的重要性能指标。 w e b 中的页面数量规模非常庞大，而网络的连接速度相对比较缓慢，为了提高提 取速度，必然考虑采用并行的做法，这就引入新的问题：( 1 ) 重复性，多个不同的 提取器在同时页面提取的时候增加了重复提取页面的可能性；( 2 ) 质量问题，单个 系统能够根据算法提取到全局最优的页面。而采取并行的话，每个提取器只能看 到局部页面，从而导致提取到的页面质量有所下降；( 3 ) 通信带宽代价，为了并行， 各个提取器之间不可避免的要有一些通信，这就带来通信的带宽问题，当各个页 面提取器通过i n t e r a c t 进行通讯，通信带宽的代价就显得至关重要。 第三，页面更新问题。w e b 的内容和结构每天都在变化，为了保持系统中的 页面是最新的，通用爬虫不得不对己经采集过的页面进行周期性的更新。但是， 随着w e b 规模上的爆炸性增长，这个问题似乎变得不可逾越。最近的一项报告显 示，即使是流行的w e b 搜索引擎，其页面刷新一次有时甚至会持续数月的时间。 可见，随着人们对w e b 搜索服务的种类和质量要求越来越高，加之w e b 规 模的不断扩大，面向整个互联网的信息提取也越来越显得力不从心：一方面它们 不得不为越来越庞大的数据提高页面提取速度、增加存储空间、优化提取策略， 而一方面却又越来越不能满足用户对主题化搜索的需求。因此，对聚集爬虫的研 究工作随之展开。 1 0 2 聚焦爬虫及相关技术 2 2 聚焦爬虫模型 2 2 1 聚焦爬虫的原理 假设用户的w e b 信息检索表示为一组目标主题集合：t = t l ，t 2 ，q ， 每个主题h 分别由聚焦爬虫来处理。我们可以用一组关键词k 早 k j ，k 2 ，k l 来表示一个主题的关键特征，而用一系列样本集w 来详细描述一个主题，其中 w - u i ，l p lu i 是一个样本u r l | l i = 0 或1 ，是该u r l 的正反例标号 。l 值为1 表示u i 与主题相关，为0 表示与主题不相关。聚焦爬虫一般从一组种子u r l 开 始沿着己爬行页面中的超链接遍历w e b 以搜集更多的主题相关页面。对于聚焦爬 虫来说，k 与w 是它的初始学习资源。 整个w e b 从逻辑上可以看作一个有向图g = ( v ，e ) ，其中图的节点集v 表示 页面的集合，有向边集e 表示页面之间的超链接。给定一个目标主题，根据页面 内容与目标主题的相关度，节点集v 可以分为两部分：相关集v 斗和不相关集v - 。 聚焦爬虫的爬行过程可以看作对一个有向图的遍历过程，即从一组节点( 种子节点) 出发，尽可能多地搜索到那些属于v + 集合的节点，同时尽可能避免搜集到那些 属于v - 的节点。 简单来说，聚焦爬虫就是指具有识别主题功能的爬虫，它尽可能多地爬行与 某个主题相关的w e b 资源，扩大该主题资源的覆盖度。 聚焦爬虫的基本思路是按照事先给出的主题，分析超链接和己经下载的网页 内容，来预测下一个要爬行的u r l ，保证尽可能地多下载与主题相关的网页、尽 可能少下载无关网页。因此，聚焦爬虫需主要解决以下三个关键问题： ( 1 ) 怎样判断一个已经下载的网页是否与主题相关? 对于已经下载的网页， 因为我们可以知道它的文字内容，可以采用传统的文本挖掘技术来实现。 ( 2 ) 怎样决定u r l 的访问次序? 许多聚焦爬虫是根据己下载的网页的相关 度，按照一定的原则，将相关度进行衰减，分配给该网页中的超链接，而后插入 到优先级队列中。此时的爬行次序就不是简单的以深度优先或者广度优先为序， 而是按照相关度大小排序，优先访问相关度大的u r l 。不同聚焦爬虫之间的主要 区别也就在于它是如何决定u i 也的爬行次序。 ( 3 ) 怎样提高聚焦爬虫的覆盖度呢? 这个问题要解决的就是如何穿过质量不够 好( 与主题不相关) 的网页得到我们所感兴趣的网页，从而提高主题资源的覆盖度。 2 2 2 聚焦爬虫的结构 最早的聚焦爬虫是在通用爬虫的基础上改造而成的。具体来说，其工作流程 以及体系结构如图2 3 和图2 4 所示。 ， 网站聚焦爬虫研究 图2 3 聚焦爬虫基本流程图 图2 4 聚焦爬虫体系结构 聚焦爬虫的工作流程较为复杂，需要根据一定的网页分析算法过滤与主题无 关的链接，保留有用的链接并将其放入等待抓取的u r l 队列。然后，它将根据一 定的搜索策略从队列中选择下一步要抓取的网页u r l ，并重复上述过程，直到达 到系统的某一条件时停止。另外，所有被爬虫抓取的网页将会被系统存贮，进行 一定的分析、过滤，并建立索引，以便之后的查询和检索；对于聚焦爬虫来说， 这一过程所得到的分析结果还可能对以后的抓取过程给出反馈和指导。 最初的设计者只是为爬虫提供了主题关键字，并在存储之前增加了一个主题 识别步骤( 相关度判定) ，若页面与主题相关就存储，否则就丢弃。尽管这样的爬 2 聚焦爬虫及相关技术 虫也能实现对主题资源的爬行，但它在爬行中依然要遍历整个网络，并没有提高 爬行的效率。网页爬行的数量和范围也依然严重依赖于给定种子站点的数量和质 量。同时，这种爬虫还会下载很多与主题无关的资源，然后丢弃，造成对带宽和 网络资源的严重浪费。 聚焦爬虫发展到现在，其结构要比原始的复杂得多，也有效得多。一般，一 个聚焦爬虫包括以下三个关键组成部分： ( 1 ) 页面相关度评价器。该模块主要特点是引入了文本分类的思想。在系统 爬行之初，页面相关度评价器根据用户输入的关键字和初始文本信息进行学习， 训练一个页面相关度评价模型。当一个页面被爬行下来之后，该页面就被送入页 面相关度评价器计算其主题相关度值，若该值大于或等于给定的某阈值，则该页 面就被存入页面库，否则丢弃。 ( 2 ) 超链按评价器。该模块是聚焦爬虫的核心模块，主要用于评估从主题相 关页面解析出来的u i 也与主题的相关度，并提供相关的爬行策略用以指导爬虫的 爬行过程。切也的超链接评价得分越高，爬行的优先级就越高。反之，若通过一 定的评价策略，发现某链接与主题无关，则将该u r l 及其所有隐含的子链接一并 去除，这个过程我们称之为剪枝。通过剪枝，爬虫就无需遍历与主题不相关的页 面，从而保证了爬行效率。但是，剪枝的行为也可能将潜在的与主题相关的页面 也剪掉。因此，超链接评价器所用的评价策略的好坏直接影响着爬虫的爬行效率 以及爬行质量。 ( 3 ) 爬行器( 页面采集模块) 。该模块是任何爬虫都不可或缺的通用模块。该模 块承担着连接超链接评价模块和页面相关度评价模块的重任。首先，爬行器从待 爬行u r l 队列中取出超链接得分最高的u 也，将该u i 也相应的网页爬行到本地， 然后，将该页面交由页面相关度评价器处理。在整个爬行过程中，爬行的次序和 爬行策略都有超链接评价器提供。 2 2 3 聚焦爬虫与通用爬虫的区别 相比于普通爬虫，一个聚焦爬虫需要能有效地发现主题相关的文档，并且能 通过网页内容和链接结构来指导自身的资源发现过程。图2 5 形象的展示了通用 爬虫和标准聚焦爬虫的爬行策略的不同。 如图2 5 所示，有两篇主题文档，未说明的白框代表未访问页面，黑框代表 已访问页面，细线代表失败的访问路径，粗线代表正确的访问路径。可见： ( 1 ) 普通爬虫以广度优先的策略，循着每一个链接进行爬行。假设从起始网 页到目标网页需要爬行i 步，那么在爬行目标网页前必须先将i 1 步内的网页爬行 完。 ( 2 ) 聚焦爬虫则先确定最有可能与主题相关的链接，忽略主题无关的网页。 网站聚焦爬虫研究 假设从起始网页到目标网页需要爬行i 步，那么在爬行目标网页前仅爬行i 1 步内 的网页的个子集，理想情况下只要爬行i 个链接就可以达到目标，大大节约了 爬行时间，提高了爬行效率。 图2 5 通用爬虫( 左) 和聚焦爬虫( 右) 的区别 如果同一主题相关的网页在互联网上是均匀分布的，那么聚焦爬虫相比于普 通爬虫在效率上就没有明显改善。然而，经过研究表明，互联网上的网页分布具 有主题聚合性。利用这一特性，聚焦爬虫就可以优先对主题相关网页中的超链接 进行爬行。 2 2 4 聚焦爬虫分类 从聚焦爬虫近几年的研究进展来看，聚焦爬虫大致可以分为两类：面向主题 网页的聚焦爬虫和面向主题网站的聚焦爬虫。前者是传统意义上聚焦爬虫，其搜 集的对象仅为主题网页，这类的聚焦爬虫主要是为主题类搜索引擎服务的。 - 然而在有些应用中，用户更希望获取的是与某一特定主题内容相关的网站， 因此后者即以主题网站为搜集的对象的聚焦爬虫应运而生。网站聚焦爬虫主要用 于维护网络目录( w e b d i r e c t o r y ) 。到目前为止，g o o g l e 、y a h o o 和d m o z 等网络目 录提供商都是通过人工的方式收集主题网站，随着互联网信息的日益增多，这种 靠人工来维护的网络目录越来越显得低效和不可行。就g o o g l e 的网络目录来说， 针对某一主题，o o o g l e 仅能提供很少数量的主题网站，很多时候无法满足用户的 需要。 网站聚焦爬虫是在现有聚焦爬虫的基础上加入网站选取和分类机制，使其能 够自动分类并搜集主题网站。与传统意义上的聚焦爬虫不同的是，用户提供给网 站聚焦爬虫的是主题网站，即与某个主题相关的专题型网站，由于主题网站内部 普遍存在指向其它主题网站的链接，因此网站聚焦爬虫可以从少量主题网站开始 1 4 2 ，聚焦爬虫及相关技术 在互联网上展开搜索，以获得更多主题网站。可见网站聚焦爬虫能很好弥补当前 网络目录手工维护的不足，实现主题网站的自动搜集。 2 3 相关技术 2 3 1 网页处理背景知识 2 3 1 1h t m l 基本概念 h t m l 语言是超文本标记语言( h y p e rt e x tm a r k u pl a n g u a g e