（计算机应用技术专业论文）基于url规则的聚焦爬虫及其应用.pdf

浙江人学硕上学位论文摘要 摘要 随着信息的不断膨胀，人们越来越离不开搜索引擎。通用搜索引擎如百度、 g o o g l e 给人们提供了很多便利，得到了极大的流行。但是随着人们需求的多样化， 和对搜索结果质量的要求越来越高，通用搜索引擎在一些专门化的领域已经不能 满足人们的要求，于是垂直搜索引擎就应运而生尽管垂直搜索引擎很多技术与 通用搜索引擎很类似，但是还是有很多自己独特的技术，和一些新的需要解决的 问题，聚焦爬虫就是其中的一个重点需要解决的问题。 本文首先基于用同一个模板产生的动态网页其内容往往是属于同一个主题 的且其u r l 是非常相似的这个规律，提出了一个基于u r l 规则的聚焦爬虫( u r l r u l eb a s e df o c u s e dc r a w l ，简称u b f c ) 的算法，即从每个主题网页相关站点中 自动学习出代表主题相关网页u r l 和主题无关网页u r l 的j 下则表达式，并用这些 正则表达式来指导聚焦爬虫的抓取。接着介绍了u b f c 在n u t c h 系统上的实现和 u r l 正则表达式学习算法最后我们对u b f c 进行了应用和分析，特别是与广度优 先搜索爬虫( b f s c ) 、基本聚焦爬虫( b l f c ) 的比较分析，表明u b f c 在收获率上 比后两者有了明显的提高，而且招回率也明显高于b l f c 。 关键词垂直搜索引擎，聚焦爬虫，u r l 正则表达式学习，n u t c h 浙江人学硕士学位论文a b s t c a c t a b s t r a c t w i t ht h e e v e r e x p a n d i n gi n f o r m a t i o n ，p e o p l eb e c o m ei n c r e a s i n g l y d e p e n d e n to ns e a r c he n g i n e s t h eg e n e r a ls e a r c he n g i n e s ，1 i k eb a i d ua n d g o o g l e ，h a v ep r o v i d e dp e o p l ew i t hal o to ff a c i l i t i e s ，a n db e c o m ev e r y p o p u l a r h o w e v e r ，a sp e o p l ew a n tt os e a r c hi n f o r m a t i o ni nm o r es p e c i a l i z e d f i e l d sa n dw a n tt h a tt h er e s u l t sr e t u r n e db yt h es e a r c he n g i n eb em o r e q u a li t y ，g e n e r a ls e a r c he n g i n e sc a nn o tm e e tt h ep e o p l e sr e q u i r e m e n t s i ns o m es p e c i a l i z e df i e l d s s ot h e r ec o m ev e r t i c a l s e a r c he n g i n e s a 1 t h o u g ht h e r ea r el o t so fs i m i l a r i t i e sb e t w e e n v e r t i c a ls e a r c he n g i n e s a n dg e n e r a ls e a r c he n g i n e s ，v e r t i c a ls e a r c he n g i n e sh a v em a n yi t so w n s p e c i f i cc h a r a c t e r sa n dn e wi s s u e s f o c u s e dc r a w li so n eo ft h ek e yi s s u e s t h a t n e e dt ob ea d d r e s s e d i nt h i sp a p e r ，w ef i r s tp r o p o s eau r lr u l eb a s e df o c u s e dc r a w l ( u b f c ) b a s e do nt h el a wt h a tt h ep a g e sw h i c hg e n e r a t e db yt h es a m et e m p l a t eo f t e n b e l o n gt ot h es a m et o p i ca n dt h e i ru r la r ev e r ys i m il a r t h e nw ei m p l e m e n t u b f c b a s e do no p e ns o u r c ep r o j e c t - - n u t c ha n da l s od e s i g na n di m p l e m e n t u r lr e g u l a re x p r e s s i o n s1 e a r n i n ga l g o r i t h mw h i c hs u p p o r t su b f c f i n a l l y ， w ei n t r o d u c et h ea p p l i c a t i o no fu b f c ，a n dh a v ed o n eal o to ft e s ta n d a n a l y s i s ，p a r t i c u l a r l yc o m p a r i n gu f b cw i t hb o t ht h eb r e a df i r s ts e a r c h c r a w l ( b f s c ) a n db a s e l i n ef o c u s e dc r a w l ( b l f c ) t h et e s ts h o w st h a tu b f c d i dar e m a r k a b l ei m p r o v e m e n tc o m p a r i n gw i t hb f s ca n db l f ci nh a r v e s t ，a n d i t sr e c a l lr a t ei sf a rb i g g e rt h a nb l f c k e y w o r d sv e r t i c a ls e a r c he n g i n e ，f o c u s e dc r a w l ，u r lr e g u l a re x p r e s s i o n l e a r n i n g ，n u t c h 渐江人学硕上学位论文 图目录 图目录 图1 - 1 主题孤岛4 图1 - 2 页面的距离5 图卜3c f c 的三个阶段6 图1 - 4 相关网页与最短路径7 图1 - 5 类l 日j 链接规律的学习转移概率矩阵的步骤8 图1 - 6i s u r f e r 系统的增量学习框架9 图2 - 1 垂直搜索引擎架构图1 2 图2 - 2 三层体系缓存架构图 图2 - 3 m a p r e d u c e 的处理框架图1 9 图2 - 4 n u t c h 架构图1 9 图3 - 1 实验爬虫阶段流程图。2 4 图3 - 2 利用讵则表达式指导聚焦爬虫j 下确的抓取网页2 6 图4 - 1 u r l 正则表达式学习器的三个阶段2 7 图4 - 2 j a v a 表示的u r l 数据结构2 8 图4 - 3 u r l 划分器工作流程图2 9 图4 - 4 静态聚合算法流程图。3 0 图4 - 5 动态聚合算法流程图3 l 图4 - 6 抽取正则表达式的流程图3 2 图4 7 实验爬虫阶段的设计图。3 3 图4 8 站点过滤器流程图。3 4 图4 - 9 u r l 数量过滤器流程图3 5 图4 - 1 0 n u t c h 爬虫流程图3 7 图4 - 1 l 实验爬虫的抓取列表产生器流程图3 7 图4 一1 2 聚焦爬虫阶段设计图3 8 图4 - 1 3 u r l 正则表达式过滤器流程图3 9 图4 一1 4 聚焦爬虫阶段的修改过的抓取列表生成器的流程图4 0 图5 - 1 b f s c 的抓取列表产生器流程图4 2 图5 - 2 b l f c 抓取列表产生器流程图4 3 图5 - 3 不同过滤阀值的招回率比较图4 8 图5 - 4 不同过滤阀值的抓取页面比较图一4 8 图5 5 不同过滤阀值的收获率比较图。4 9 图5 6 相关网页趋势比较图5 2 图5 - 7 总共抓取网页趋势比较图5 3 图5 - 8 收获率趋势比较图一5 3 图5 - 9 总体收获率比较图一5 4 n i 浙江大学硕上学位论文 图目录 图5 - 1 0 局部收获率比较图5 4 图5 - 1 1 基于u r l 规则的全网聚焦爬虫5 5 图5 - 1 2 寻找主题相关站点设计图 5 6 图5 - 1 3 候选站点发现器的设计图5 7 图5 - 1 4 主题相关站点识别器的设计图5 8 表5 - 1 实验用到的主体相关网站列表。4 4 表5 - 2 模拟数据集的统计数据4 6 表5 - 3h o s t 划分与目录划分的比较一4 7 表5 - 4 h o s t 划分与目录划分的比较二。4 7 表5 - 5 不同噪音过滤阀值对u b f c 的影响5 0 表5 - 6 b f s c ，b l f c ，u b f c 三者在各个网站上的性能表现5 1 浙江大学硕上学位论文 第1 章绪论 第1 章绪论 1 1 问题的提出 随着信息的不断膨胀，人们越来越离不丌搜索引擎。通过使用像百度、谷歌 这样的通用搜索引擎，往往我们可以迅速找到自己想要的信息。尽管通用搜索引 擎给人们提供了很多便利，得到了极大的流行，但是很多时候通用搜索引擎对一 些问题无能为力，比如你想搜索浙江大学旁边的价钱低于l o o o 月的出租房屋， 或者你想要查询哪家网上商店出售的i p o d 最便宜，等等这些问题通用搜索引擎 就无法理解了。 周立柱0 1 总结了通用搜索引擎的局限性： 1 不同领域、不同背景的用户往往具有不同的检索目的和需求，通用搜索引 擎所返回的结果包含大量用户不关心的网页 2 通用搜索引擎的目标是尽可能大的网络覆盖率，有限的搜索引擎服务器资 源与无限的网络数据资源之间的矛盾将进一步加深。 3 万维网数据形式的丰富和网络技术的不断发展，图片、数掘库、音频视频 多媒体等不同数据大量出现，通用搜索引擎往往对这些信息含量密集且具有一定 结构的数据无能为力，不能很好地发现和获取。 4 通用搜索引擎大多提供基于关键字的检索，难以支持根据语义信息提出的 查询。 而垂直搜索引擎则能较好的解决上述问题，垂直搜索引擎是相对于通用搜索 引擎而言的，通用搜索引擎覆盖整个互联网上的所有信息，而垂直搜索引擎只搜 索某一个行业或者某一个主题的信息，因此垂直搜索引擎更具有针对性，也就能 提供针对某一个行业或者某一个主题的特殊需求。垂直搜索引擎通过特定行业、 主题的领域知识，可以提供根据语义信息的查询，从而能满足用户的特殊搜索需 求；另外它更加专业，关注范围比较小，所以返回的结果也更具有针对性，并且 只需要索引一小部分互联网数据，所以可以只用很少的服务器资源覆盖互联网上 绝大部分某一特定行业、主题的数据。此外垂直搜索引擎还可以用来建立数字图 书馆。“翻。正因为上述这些原因，垂直搜索引擎越来越收到追捧，也越来越流行。 现在市面上出现了很多垂直搜索引擎，比如文学搜索、新闻搜索汹。1 、商品搜 索。“1 等。根据中国市场研究集团通过调查发现，百度有2 0 的搜索流量同其垂 直搜索引擎m p 3 搜索相关0 1 由此可见垂直搜索引擎的重要性。 浙江大学硕学位论文 第1 章绪论 随着垂直搜索引擎的出现，相应的问题随之而来，其中最重要的问题之一是 如何设计一个高效的聚焦爬虫。垂直搜索引擎的聚焦爬虫是相对于通用搜索引擎 的通用爬虫而言的。通用爬虫的页面抓取策略相对简单，主要是采用广度优先搜 索的思想不停的抓取新的页面；而聚焦爬虫却是有选择的抓取与特定主题相关的 页面。随着垂直搜索引擎的f 1 益流行，作为垂直搜索引擎的关键技术一一聚焦爬 虫也显得越来越重要。可以说如果较好的解决了聚焦爬虫，那么一个垂直搜索引 擎也就成功了一半聚焦爬虫大致有两个主要问题：一个是选择策略，表明优先 抓取哪些页面；一个是重访策略，表明什么时候重新抓取页面，看看页面是否发 生了变化本文只解决第一个问题。 1 2 研究现状 本文研究聚焦爬虫的选择策略，也就是说优先抓取哪些页面，或者只抓取哪 些页面，不抓取哪些页面。经过多年的研究，对优先选择什么页面、如何选择这 些页面的问题，很多人都提出了自己的方法。下面主要介绍一下这些方法。 1 2 1 按照重要性对u r l 进行排序 早期一些人借鉴通用搜索引擎的链接分析技术，对u r l 的重要性进行排序， 优先抓取那些重要性高的网页。比如j u n g h o oc h o 在其论文嘲中介绍了一种利用 网页的p a g e r a n k 0 1 值排序u r l ，p a g e r a n k 值高的页面将会排在前面，会被优先抓 取。 p a g e r a n k 是g o o g l e 创始人l a r yp a g e 和s e r g e yb r i n 发明的用于计算页面重 要性的算法，并且应用在其商业化的g o o g l e 搜索引擎中。这种算法可以用一个 随机网上冲浪者( s u r f e r ) 的模型来描述。冲浪者浏览一张页面后，他可以随机 选择该页面的一个链接浏览下一张页面，也可以跳到其他页面。这样如果一张页 面p 被很多网页链接，那么p 被访问的概率也就越大，也就显得p 越重要。另外 如果指向p 的网页的重要性很高，p 也应该更重要，也就是说p 的重要性不仅由 指向p 的链接数决定，还由指向p 的网页本身的重要性决定。表示成公式如下： p r ( i ) = ( 1 - d ) + d2 1 1 ： p r 0 ) n 0 ) l l j ， 其中i ，j 表示网页，函数p r 表示网页的重要性，函数n 表示网页的出去的链接数， j 为链接向i 的网页，d 为一个衰减因子，取值范围为0 到l ，一般取0 8 5 。通过递 归的使用上述公式计算每张网页的重要性，直到收敛时停止计算。 2 浙江大学硕士学位论文 第1 章绪论 p a g e r a n k 算法的一个缺点是仅仅计算待抓网页的重要性值，并没有考虑网页 与特定主题相关性，因此用这种算法引导的聚焦爬虫很容易迷失方向，抓下的网 页很少是与特定主题相关的。其实这种算法引导的爬虫不能称为聚焦爬虫，是一 种非聚焦爬虫。n o v a k 嘲在其文章中指出，实验表明非聚焦爬虫抓下来的网页中， 与主题相关的网页的比率很快就会下降为0 。 1 2 2 主题相邻性 从上面的分析我们可以知道，用p a g e r a n k 这样的算法指导聚焦爬虫，我们只 能找到重要性比较高的页面，并不能保证这些页面是与特定主题相关的。因此如 何确定待抓网页与特定主题的相关性是聚焦爬虫的关键。d a v i s o n 在其研究”1 中 发现的互联网上的主题相邻性( t o p i c a ll o c a l i t y ) 给聚焦爬虫指明了一个方向。 d a v i s o n 通过d i s c o w e b 系统收集了包括1 0 0 0 0 0 个网页的互联网子图，并用 t f - i d f 向量空问模型计算网页阐的相似性。 在一个向量空问模型中，一个文档i 由一个向量v i 表示，v 。= ( w ，- 。，霄。) ， 其中t 表示所有文档不同单词的总数，w ，表示单词j 在文档i 中的权重，w 。= t f 。， i d f j 。t f 是单词频率的意思，t f ；。表示单词j 在文档i 中出现的频率。i d f 是 逆向文档频率的意思，i d f j 表示单词j 的逆向文档频率，i d f ，= l o g ( n n ，) ， 其中n 表示所有的文档总数，n ，表示包含单词j 的文档总数。两个文档的相似性就 由表示两个文档的向量的余弦值来度量，越接近l 说明越相近，越接近0 说明差 异越大。 用上述方法对子图中的网页计算相似性后，d a v i s o n 发现用超链接连接起来的 两个网页比随机的两个网页具有更大的相似性。很多研究都是利用这一根据来预 测待抓网页的与特定主题的相关性，即如果一张页面与特定主题相关，那么它所 连出去的页面与该主题相关的可能性比较大，所以顺着与特定主题相关的页面出 去的链接更可能找到其他主题相关的页面。比如c h a k r a b a r t i 等在脚提到的 s o f t f o c u s 方法，它会把一张抓下来的页面p 中所有出去的链接u r l 放入待抓列 表，这些u r l 的抓取优先级是基于p 与主题的相关度来计算的。而页面p 与主题的 相关度使用一个分类器来计算。m u k h e r j e a “1 介绍了一个收集并分析相关网页的系 统w t m s 。w t m s 使用向量空间相似度来度量抓取下来的网页与目标主题的相关度， 一张网页如果它的与目标主题的相关度越高，那么从它出来的u r l 的优先级越高， 放入待抓队列后，将会先被抓取。另外在f i s h - s e a r c h “o 中也采用了类似的思想。 这种仅仅利用父页面与主题的相关度来预测子页面与主题的相关度，并以此作为 3 浙江大学硕上学位论文第l 章绪论 指导的聚焦爬虫，a l t i n g o v d e 等“”称为基本聚焦爬虫( b a s e l i n ef o c u s e dc r a w l ) 利用父页面与主题的相关性可以帮助预测予页面与主题的相关性，除此之外 还有其他信息可以帮助预测页面与主题的相关性，比如利用一张页面的锚文本、 兄弟结点与主题的相关性等等信息来预测其与主题的相关性 1 2 3 主题孤岛问题 借助于互联网上的主题相邻性规律，似乎聚焦爬虫的问题能够得到很好的解 决。然而实际情况并不如此，m c c a l l u m 等人“”和d i l l i g e n t i 等人认识到实际的 互联网并不总是如此，与主题相关的网页并不总是连在一起的，从一张主题相关 网页出发往往需要经过几张与主题无关的页面后才能再次到达主题相关的页面。 如果我们把相连在一起的主题相关网页称为一个主题岛，那么整个互联网就是由 无数这样的主题岛构成，各个主题岛被一些主题无关网页分隔。我们称这种现象 为芏= 笤掰。寄。如图卜1 所示，粗边的圆圈代表与主题相关的网页，细边的 图卜1 主题孤岛 圆圈代表与主题不相关的网页。相互连接在一起的主题相关网页组成一个主题孤 岛，图卜l 一共有三个主题孤岛，之所以称为孤岛是因为他们只能通过主题无关 页面才能进入这些页面。实际的互联网应该存在不计其数的这样主题孤岛，如果 我们仅仅抓取从主题相关的页面出来的u r l ，会错失很多主题孤岛，从而导致召 4 浙江大学硬1 二学位论文第1 章绪论 回率很低。因为连接主题孤岛的是主题无关页面，只有先抓取这些页面才能进入 主题孤岛。 为了解决主题孤岛问题，很多文献都提出了自己的方法。下面着重列举几个 这样的方法。 1 2 4 隧道技术 一张主题相关的页面可能需要经过几张主题不相关的页面才能到达。按照 s o f t f o c u s 的计算方法，子页面的相关性由父页面的相关性计算得到，因此如果 一张父页面的相关性很低，那么它的子页面几乎没有机会被抓取下来，这样也就 无法到达可能的主题相关页面。为了克服这个问题，b e r g m a r k 等人“1 提出了一个 简单的想法一一隧道技术，就是给每张待抓页面设置一个距离值，如果其父页面 是与主题相关的，那么它的距离为0 ，反之，它的距离是它的上一个主题相关的 祖先到它的距离。如图1 - 2 所示，圆圈代表页面，粗线圈代表主题帽关页面，细 线圈代表主题无关页面，箭头代表一张页面到另一张页面的链接。图中页面l 的 距离值为0 ，页面2 的距离值为1 ，页面3 的距离值为2 ，页面4 的距离值为0 ，页面 5 的距离值为1 系统只抓取距离小于一个阀值的页面。比如如果阀值设为2 ，那 么页面3 及其以后的页面将不会被抓取，如果阀值设为大于2 ，那么图1 - 2 中的所 有页面都将会被抓取。所以采用这个方法也能抓取那种需要经过几张主题无关网 页才熊到达的相关网页。 o 一9 0 o 图1 - 2 页面的距离 但是这种方法有一个缺点：如果阀值设置的过大，就跟广度优先搜索没区别； 如果阀值设置的过小，很多相关页面也不能到达。 1 2 5c f c c f c ( c o n t e x tf o c u s e dc r a w l e r ) “”，利用一群网页构成的上下文图来建模网络 的层次结构，并利用这种层次结构指导聚焦爬虫。如图卜3 所示，该方法大致可 以分为三步：反向爬行阶段，训练阶段，抓取阶段 5 浙江大学硕士学位论文 第l 章绪论 盘 囝辔盘 q国国 蠡 - j 三二! 图卜3c f c 的三个阶段 在反向爬行阶段，首先确定一张种子页面，利用通用搜索引擎，比如g o o g l e ， 寻找指向这张种子页面的网页，记种子页面为第0 层，新找到的页面为第l 层， 对处在第1 层的页面再寻找指向其的页面，记为第2 层，以此类推宜到找到第1 3 层，其中e 1 为预先定义的一个值。这n + l 层页面就形成了一张图，称这张图为上 下文图。把很多种子页面的上下文图归并起来( 相应的层次合并) ，就形成了一 张综合上下文图。 在训练阶段，对综合上下文图中的每一层训练一个分类器，训练使用的是一 个精简版的t f - i d f ，即只使用t f - i d f 分值最高的四十个词。 在抓取阶段，系统使用n + 2 个队列，分别对应第o 到e l 层分类器和一个o t h e r s 队列，刚开始时把种子i j r l 放入队列0 中，然后开始抓取页面，每次优先抓取序 号低豹队列中的u r l 。对于新抓的页面使用分类器把他归入n + 2 类中的一类，并 把其所有出去的u r l 放入相应的队列中。 实验结果表明使用这种方法在一段给定的时间内能比基本聚焦爬虫多抓取 5 0 - - 6 0 的相关网页。 1 2 6 决策树 j u nl i 等人“”提出了利用决策树指导聚焦爬虫具体方法如下，首先对于一 个网页图g ，用普通爬虫抓取所有的网页，并用一个训练好的s v m 分类器标识与 主题相关的网页。然后对于每张主题相关页面用d i j k s t r a 最短路径算法计算从 6 浙江大学顽t 学位论文 第1 章绪论 根页面( 进入点页面) 到这些页面的最短路径。这样的图结构如图1 - 4 所示，黑 色圆圈表示主题相关页面，黑线箭头所连成的是由根页面到主题相关页面的最短 路径，这些路径上的非主题相关页面用双线圆圈表示。有了这些数据之后，就可 以构建一棵决策树。首先以在最短路径上的页面包括主题相关页面( 黑色圆圈) 和一部分主题无关页面( 双线圆圈) 作为正例，其他页面作为反例。选择的特征 是锚文本中的单词。在碰到一个新u r l 时，取它的锚文本，然后在正例中寻找包 含这个锚文本所有单词的正例个数p 8 ，在反例中寻找包含这个锚文本所有单词的 反例个数n a 。则如果p a p n a n ，则判断其为正例，反之判断其为反例，其中 p 为所有正例个数，n 为所有反倒个数。 图1 _ 4 相关网页与最短路径 1 2 7 类问链接规律 c h a k r a b a r t i 等人在嘲中说同一类的页面不仅会连向自己类的其他页面，还会 连向其他类的页面。比如他们观察到属于“自行车”类的页面还会连向“红十字” 和“急救”类页面；属于“h i v a i d s ”的页面更可能连向“医院”类页面而不是 “h i v a i d s ”页面。基于这种情况，a l t i n g o v d e 等“”提出了利用龚獍嗡喏秘f 错旨 导聚焦爬虫。 这种方法首先是学习一个类问链接转移概率矩阵，然后再用这个概率矩阵指 导聚焦爬虫。学习类阃链接转移摄率矩阵主要分为三个步骤，如图卜5 所示； 1 从网页目录( 如d m o z “”) 得到一个类别树以及属于每一类的一些网页作为 样例，记这些样例为训练集0 ，用这些类别和样例训练一个分类器。 2 对于训练集0 中的每一类c ，抓取c 中页面指向的所有页面，抓取后的页面 7 浙江大学硕j 。学位论文第1 章绪论 称为训练集l 。把训练集l 中所有页面用第一步中训练出来的分类器进行分类得 到他们的类别。 3 于是我们就知道训练集0 中的各类页面指向其他类页面的分布情况。这个 分布情况可以用一个概率矩阵t 。来表示，每个元素t 。，表示从类别为t i 的页面连 出去的页面其类别为t j 的概率。 有了转移概率矩阵，我们就用它来指导聚焦爬虫。对于一张新抓取的页面， 首先用分类器判断它的类别，然后用矩阵t _ 来找出其所连出去的网页的类别的分 布情况。利用矩阵l 我们可以知道从这张页面出去的是与主题相关类别的页面的 概率是多大，并以这个概率来指导聚焦爬虫，概率越大越优先抓取。 纛；妻髫矧h 警斯分凳卜彳内郝模毽m 毫尘2 咧! = 匦。：。篁 龟= 。：。m。， f 嚣黧游剐一t 蝴摸翟鼢袭 _ 一7 2 髫蓊譬 同一# 嗣一叫刁 一倒一：墨乡 图1 5 类间链接规律的学习转移概率矩阵的步骤 1 2 8 增强学习 一些人“引“埘采用增强学习策略实现聚焦爬虫。y u n m i n gy e 等人n 5 1 设计了一个 系统i s u r f e r ，这是一个基于从正例中增量学习的聚焦爬虫。它的架构图如图i - 6 所示，它使用增量学习方法学习一个页面分类器和一个链接预测器，并使用一个 在线例子发现器从已抓网页中选出新的例子供页面分类器和链接预测器学习并 更新他们的模型刚开始训练集只有正例，当开始抓取时，例子发现器选出新的 例子交给页面分类器和链接预测器学习。在系统中，例子发现器的选取新的例子 的方法很重要，会直接影响页面分类器和链接预测器的表现。例子发现器选取与 主题相关性高的网页和h u b 网页。1 作为正例，其他与主题相关性低的网页作为反 例。h u b 网页就是包含很多指向与主题相关性高的页面。作者使用增量学习方法 作了一些小规模的实验，抓取1 0 0 0 张网页，发现收益率提高很多，比没有增量 学习的聚焦爬虫提高了4 0 9 。另外m c c a l i u m 等“。通过实验显示采用增强学习的爬 虫的效率是采用广度优先搜索爬虫的3 倍。 浙江丈学硕上学位论文第1 章绪论 图1 - 6i s u r f e r 系统的增营学习框架 1 2 9 分析总结 除了以上提到的各种技术外，一些人还尝试了其他技术来实现聚焦爬虫。如， 元搜索技术“目，同时从几个通用搜索引擎搜索相关的网页，并把结果组合起来作 为种子u r l 。协作爬虫，这种爬虫利用用户浏览互联网的模式来建立学习信息， 并学习出相应的模型，以此指导爬虫。 从上面的分析介绍，我们可以知道，基本聚焦爬虫由于不能解决主题孤岛问 题，导致召回率会很低。而且一般情况下，一张页面包括很多u r l ，这些u r l 往 往属于各种不同的类别，所以从同一张主题相关的页面连接出去的页面可能只有 1 。2 张页砸是与同一个主题相关的，这又会导致精确率会很低。用隧道技术可以 提高召回率，但是它基本上可以看作是一种介于通用爬虫和基本聚焦爬虫之问的 技术，在提高召回率的同时使 | 寻精确率大大降低，这将会浪费大量服务器资源 上下文图方法需要借助于通用搜索引擎，这对于一个商业搜索引擎来说可能不 好，因为要受制于其他公司，而且结果也只是比基本聚焦爬虫提高了5 0 一6 0 9 6 ， 由于原本基本聚焦爬虫的精确率就很低，所以这个提高对于商业聚焦爬虫来说还 是不够的。其他方法的提高也只是相对于基本聚焦爬虫甚至通用爬虫而言的，离 商用要求还是有一段距离。 1 3 本文的主要工作和组织结构 本文提出了一个基于u r l 规则的聚焦爬虫的算法，即从每个主题网页相关站 9 浙江丈学硕上学位论文 第1 章绪论 点中分别自动学习出代表主题相关网页u r l 和主题无关网页u r l 的正则表达式， 并用这些正则表达式指导聚焦爬虫的抓取工作。与广度优先搜索爬虫( b f s c ) 、 基本聚焦爬虫( b l f c ) 的实验比较分析表明u b f c 在收获率上比后两者有了明显 的提高，而且招回率也明显高于b l f c 。 本文后续章节组织结构如下： 第二章介绍了垂直搜索引擎与n u t c h 技术，主要是垂直搜索引擎的架构和各 个模块的相关技术，并介绍了开源搜索引擎n u t c h 及其用到的相关技术。 第三章提出了一个基于u r l 规则的聚焦爬虫( o b f c ) ，该聚焦爬虫也是本文的 创新点。 第四章在开源搜索引擎n u t c h 之上实现了u b f c ，介绍了各个模块的设计与流 程图，并设计和实现了u b f c 的关键模块u r l 正则表达式学习器。 第五章在五金行业的垂直搜索引擎中应用了u b f c ，并作了大量测试与分析， 特别是与广度优先搜索爬虫( b f s c ) 、基本聚焦爬虫( b l f c ) 的比较分析，表明 u b f c 在收获率上比后两者有了明显的提高，而且招回率也明显高于b l f c 另外， 还提出了把u b f c 应用到全网聚焦抓取的构想。 1 4 本章小结 本章首先指出了聚焦爬虫的重要性和本文所要研究的问题，即研究聚焦爬虫 的选择策略。接着详细介绍了国际上在该领域的研究现状，并对各个方法作了评 价。最后介绍了本文的所做的主要工作和组织结构。 l o 浙江大学硕士学位论文第2 章垂直搜索引擎与n u t c h 概述 第2 章垂直搜索引擎与n u t c h 概述 本章介绍了与本文所研究和开发的聚焦爬虫相关的知识：垂直搜索引擎和开 源搜索引擎n u t c h 。本文所实现的聚焦爬虫是一个五金行业垂直搜索引擎的一部 分，并且本文的聚焦爬虫的实现是建立在n u t c h 爬虫之上的，所以介绍这两部分 显得很有必要。 2 1 垂直搜索引擎 聚焦爬虫是垂直搜索引擎的一部分，了解垂直搜索引擎的架构和聚焦爬虫在 垂直搜索引擎中所处的地位，对于理解聚焦爬虫很有帮助。 2 1 1 垂直搜索引擎架构 通常一个通用搜索引擎的所有模块可以分为两大块：在线部分和离线部分。 所谓的在线部分是指不断响应用户搜索请求的部分，这部分也是用户所能接触到 的，包括搜索、缓存、网页评分等。而离线部分是为在线部分提供数据准备的部 分，这部分包括爬虫、建立索引、链接分析等。垂直搜索引擎在线部分的模块和 通用搜索引擎一致，所不同的是离线部分的模块。一个垂直搜索引擎和通用搜索 引擎离线部分最大的不同是爬虫，在这里垂直搜索引擎是一个聚焦爬虫，它的任 务是尽可能的抓取与主题相关的网页，而通用爬虫是抓取所有看到的网页。另外， 垂直搜索引擎还多了一些其他的模块，如页面分类器和信息抽取器。一个垂直搜 索引擎的架构图如图2 - 1 所示。下面将分别介绍其中各个模块。 2 1 2 聚焦爬虫 据国外媒体报道，互联网调研机构n e t c r a f t 提供的数据显示，截至2 0 0 6 年 3 月底，全球网站总数达到了8 0 6 5 万多嘲1 ，而且网站数量每天都在增加之中。每 个网站每天都在产生新的网页。由此可见互联网上的网页数量是非常庞大的。而 对于一个垂直搜索引擎来说，他只对与某个主题相关的网页感兴趣，比如一个商 品搜索引擎只对互联网上的商品网页感兴趣，而商品网页只占整个互联网网页总 数的一小部分。所以如果像通用搜索引擎一样把整个互联网上的网页都抓取下 来，是极其浪费时间和金钱的。正是在这样的情况下，聚焦爬虫才显得非常有必 要，聚焦爬虫的任务是尽可能的只抓取与主题相关的网页。目前有很多种聚焦爬 浙江大学硕t 学位论文 第2 章垂直搜索引擎与n u t c h 概述 虫的实现方法，这在第一章中已经作了介绍，在此不再赘述。 图2 - 1 垂直搜索引擎架构图 2 1 3w e b 图生成器 整个互联网就是一个有向图，图的结点是网页。如果一张网页有指向另一张 网页的链接，则对应的有向图中就有一个结点到另一个结点的一条边。对于一个 1 2 浙江大学硕l 学位论文第2 章垂直搜索r j l 擎与n u t c h 概述 搜索引擎来说，用爬虫把互联网上的网页抓下来并取出网页中的所有链接之后， 就是利用这些链接还原一个互联网图，而这个图将在链接分析中用到。还原互联 网图的任务就是由w e b 图生成器完成的。 2 1 4 链接分析 链接分析的研究内容是为了给一张网页的重要性或者权威性打分。现在已经 有很多的链接分折算法，最有名的就要数g o o g l e 的p a g e r a n k 。1 了但是现有的 链接分析算法总是存在这样那样的弊端或者漏洞。很多人看到了这些算法的漏 洞，通过采用相应的手段使得自己的网页在搜索引擎中的排名靠前。所以链接分 析的另一个重要研究内容就是发现这些利用链接作多 5 的网页。 目前有非常多的链接分析算法，其中比较著名的有p a g e r a n k 和h i t s 嗍。 p a g e r a n k 是由g o o g l e 创始人p a g e 和b r i n 提出来的。p a g e r a n k 算法在第一 章中已经作了介绍，这罩不在赘述。 h i t s 算法是由康乃尔大学的k l e i n b e r g 创立，他将网页的权值分为目录型和 权威型权值分别进行计算。目录型权值衡量网页包含重要网页链接数的程度，权 威型权值衡量网页内容的重要程度。具体的h i t s 算法如下： 1 对于每一个网页n ，令h ( n ) 代表其h u b 值，a ( n ) 代表其a u t h o r i t y 值 2 对于所有的网页n ，将h ( n ) 和a ( n ) 初始化为1 ； 3 执行操作：彳( 撑) = 目( 刀k ( 砌；( 栉) = 彳( d 【珥伽” ， 4 将a ( n ) 和h ( n ) 归一化，反复执行c 操作，直到h 和a 收敛 其中i n 。( n ) 是指向页面n 的页面。o u t 。( n ) 是页面n 指出的页面。 2 1 5 页面分类器 页面分类是文本分类的一种。文本分类所涉及的问题，是把给定的文本段落 ( 段落或者文件) 自动分配到预定的类别中去。由于文本数据的快速爆炸式增长 和使用多种方法自动组织和索引大型文本集合的需要，文本分类已经成为一个重 要的研究领域。这类技术现在应用在许多领域，包括语言辨识，作者归类，体裁 分类，专题鉴定和主观情绪分类。 许多标准的机器学习技术已经应用于自动文本分类问题中，例如贝叶斯分类 法，支持向量机算法，线性最d - 乘模型，神经网络，k 近邻分类法等。这些方法 有一个共同点是它们把文本分类作为一个标准分类问题处理，因此，学习过程简 浙江大学硕上学位论文 第2 章垂直搜索引擎与n u t c h 概述 化为两个简单的步骤：特征提取和在特征向量空间里进行分类学习。在这两个步 骤里，特征提取对文本分类得到好的性能非常重要。一旦好的特征提取出来后， 几乎任何合理的分类器学习技术都似乎可以执行得很好。 2 1 6 信息抽取器 信息抽取技术一个狭义上的定义为；自然语言文本中特定类别的事件或关系 的实例的辨认，以及该事件或关系相关参数的抽取o ”。 与通常的信息搜索不同，信息抽取主要是要从文本中抽取出特定的事实信息。 这些事实信息应该是用户所感兴趣的，而不只是大量文档集合中与用户需求相关 的文档列表。它们是系统预先设定好的领域相关的有限种类的信息。因此，信息 抽取不能采用传统搜索系统的统计及关键词匹配等技术，因为这些技术都是把文 本看成词的集合，并不会对文本进行深入分析理解信息抽取往往要借助自然语 言处理技术，通过对文本中的句子以及篇章进行分析处理后才能完成。当然，这 种理解是浅层的理解，只是把用户所关心的有限的感兴趣的事实信息抽取出来， 至于文本意义的细微差别和作者意图等深层理解问题则不予理会。 总的来说，信息抽取技术是一种面向具体任务的实用的文档理解技术与复 杂的自然语言理解技术不同，信息抽取技术通常采用浅层的文本分析技术，提取 出设计者关注的特定主题的信息“”。 2 1 7 索引构建器 通常现代的搜索引擎应付的用户请求都是关键字查询，对于一个用户的请 求，一个最简单的方法就是扫描所有抓取下来的网页，看看有哪些网页包括这些 关键字，并返回给用户这个网页列表但是这种方法的一个明显缺点就是速度太 慢，要知道一个现代的搜索引擎保存着上百亿张网页，如此庞大的数据，靠扫描 所有文件的方法是不可取的。 另一个方法就是采用某种数据结构先对这些网页建立索引，建立索引的目的 是为了提高查询的速度。目前用的最普遍的建立索引的方法是倒排索引。搜索引 擎抓取下来的网页中包括很多单词，一般的逻辑是从网页中找单词，但是这样很 慢，上面说过了。解决方法是用单词找网页，即用单词作为索引关键字，每个单 词对应的项后面跟着一个网页列表，代表包括这个单词的网页集合这就是倒捧 索引。当然搜索引擎的索引数据结构还包括单词在网页中出现的频率和位置，用 频率信息计算单词在网页中的权重，用位置信息生成摘要、组成短语等。 1 4 浙江大学硕上学位论文第2 章垂直搜索引擎与n u t c h 概述 2 1 8 搜索 有了倒排索引结构后，搜索就是一件相对轻松的事情。对于一个用户的请求 里面的每个单词，都用二分搜索找到在倒排索引结构中的位置，这样每个单词都 得到一个列表，该列表包括有该单词出现的所有网页、该单词在每张网页出现的 频率、该单词在每张网页出现的位置。最后根据每两个单词之间的关系，把每个 单词对应的列表归并处理。比如，如果是逻辑与关系就只取对应两列表的公 共部分，如果是逻辑或关系就合并两列表。这样就得到了一个网页列表，当 然这个网页列表并不能直接返回给用户，还需要对这个网页列表按照重要程度和 与用户查询的相关程度排序好，才返回给用户。排序部分就由网页评分来决定。 2 1 9 网页评分 网页评分可能是决定一个搜索引擎好坏的最重要部分了。一个好的评分算法 能使与用户查询最相关的、最重要的网页排在最前面。所以网页评分的研究内容 包括网页与用户查询的相关性度量、高性能的评分算法。 一个商业搜索引擎的评分算法是非常复杂的，要考虑非常多的因素来对一张 网页打分。但是最主要的因素有两个：网页的p a g e r a n k 值，网页与查询的相似 度一般是用网页p a g e r a n k 乘以网页和查询的相似值，然后按照这个值对网页 进行排序。网页的p a g e r a n k 值是在链接分析时候计算出来的，可以直接用。而 计算网页与查询的相似度一般采用t f * i d f 的方法。这在第一章已经讨论过还 有一个很重要的考虑因素是查询语句中包含的所有单词在网页中是否相邻出现， 一般认为这些单词在网页中靠的越近就越有可能是用户想要的网页。而这一点可 以用所有单词在网页中出现的位置信息计算出来。 与网页评分的另一个相关研究领域是反作弊。一些广告网页为了提高点击 率，就在网页中加入了很多与网页不相关的但是又比较常用的关键字，以期提高 与用户查询的相关度，从而使得网页的排名靠前。所以如何识别这些作弊页面也 是非常重要的。 2 1 1 0 缓存 搜索引擎处理一次用户查询的代价是高昂的，它需要发动几百台机器协 同工作。另一个方面，很多用户的查询是一样的，或者有部分关键字是一样的。 这个时候缓存就显得十分有必要。缓存研究的内容包括提高缓存的命中率，节约 缓存资源的占用。 1 5 浙江大学硕士学位论文第2 章垂直搜索引擎与n u t c h 概述 当l i 在搜索引擎领域内的主要缓存技术有如下一些； 1 查询结果缓存。查询结果缓存会缓存频繁出现的相同的用户查询的完整结 果。一般是直接部署在前端查询服务器上。 2 反向链表缓存。反向链表缓存会缓存出现频率高的关键字所对应的反向链 表。