（计算机软件与理论专业论文）基于概念背景图的主题爬行策略研究.pdf

乙 西华大学学位论文独创性声明 f f l l r fi f f f fi l f f f l l l f l f f f f l l f l l l l l l f l l l l l l 1 1 i f y 17 5 0 4 4 6 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文作 日期：加e 本学位论文作者完全了解学校有关保留、使用学位论文的规定，在校 攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文。( 保密的论文在解 密后遵守此规定) 学位论文作者签名：锬= ：毛气龟 日期：驴c 。4 7 指导教师签名： 日期 执扒k 1 芬 眵o 戈b 弗 备，札 淑 勤 文 授 师 夕厍 撕 多朗 导期 陂 擀嗍 ：萋 2 p 汶 0 户 论 力“，阻幽 _ 、r ， 争一 ，拌 岔“ 吠 参d 华 西华大学硕士学位论文 ；摘要 近年来，随着i n t e n l e t w e b 技术的快速普及和迅猛发展，互联网上的网页每天都以 指数级别增长，目前数字信息己呈现数量庞大、类型繁多、更新迅速等发展趋势。在如 此类型繁多更新速度之快的形势下，w e b 数据挖掘已经成为现在人们信息获取的主要方 式，搜索引擎成为人们获取信息的重要工具。但是现在的通用搜索引擎采用穷尽的方式 爬行互联网上的网页，这种通用搜索引擎抓取信息的速度远远落后于真实产生的网页。 同时，互联网信息所具有的海量数据、复杂性、极强的动态性和用户的多态性等特点也 给搜索引擎造成了相当的难度。 因此，面向主题的智能检索系统应运而生并引起了研究者的极大重视。主题搜索引 擎的爬行虫，称为主题爬行虫，主题爬行虫抓取互联网上与主题相关的页面来满足用户 查询的需求，它具有花费时间少，所需存储空间小，能够满足用户个性化需求等优势。 它自动识别主题信息，快速、有选择地遍历与主题相关的区域并下载网页，有效地避开 与主题无关的区域，为面向主题的用户查询准备数据资源。但是对于w e b 自身复杂的 结构和主题爬行虫的实时性，如何提高主题爬行虫的主题识别能力? 如何在较短时间内 下载更多与主题相关的网页? 如何穿过与主题无关的网页到达与用户兴趣主题相关的 网页? 这些都是主题爬行策略需要解决的问题，也是目前主题搜索的研究焦点。 本文对现有的几种主题爬行策略进行研究，发现现有的几种主题爬行策略对待爬行 u r l s 的预测排序主要还是基于关键词的，对爬行预测还是停留在关键词层面上，没有 做到语义预测的高度。本文是通过已检索的网页的内容和链接信息来预测主题爬行的爬 行方向。引入形式概念分析，通过计算概念格中概念之间的语义相似度来进行预测，把 主题爬行方向的预测提高到语义预测的层面。 本文的主要贡献如下： ( 1 ) 将概念格引用到语义相似度的计算中来，用已经爬行到的与主题相关的网页构 建概念格，作为用户的主题背景信息，再将概念格映射到概念背景图中，通过计算网页 与背景图中的概念的语义相似度来预测待爬行u r l s 优先级。 ( 2 ) 提出了一种概念背景图的构建方法，传统的背景图的构建方法有d i l i g e n t i 在文 章 1 4 】中提出的链接背景图( l c g ) ，是完全基于网页的链接关系的；c h i n g c h i h s u 等人在 文章 1 5 】中提出的相关背景图( r c g ) ，是在网页之间的链接关系的基础上增加上一个相 似度的计算。本文的方法是在概念格的基础上，由概念属性词之间的关系把概念格中的 每一个概念映射到背景图中，形成概念背景图。 基于概念背景图的主题爬行策略研究 ( 3 ) 提出了一种基于语义分析和链接分析相结合的主题爬行策略。使用构建好的概 念背景图，对网页进行语义相似度的计算，保证爬行回来的网页更加接近主题，结合网 页的链接关系来指导爬行，使爬行虫能够选择正确的方向，快速的跳过与主题无关的区 域，到达与主题相关的区域。 ( 4 ) 构建主题搜索系统，获取网络数据，通过主题相关文档数量、召回率、精确率， 这几种评价指标来检验本文的搜索策略，并且与宽度优先的爬行策略和其它几种主流的 爬行策略在相同的数据集下进行实验比较，得出了本文提出的策略是可行的。 关键词：搜索引擎；主题爬虫；概念背景图；语义分析；链接分析 西华大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r n e ta n dw e b t e c h n o l o g y ，t h e w e bp a g e sa r ei n c r e a s i n ga te x p o n e n t i a lr a t ee v e r yd a y a c c o r d i n gt ot h ep r e s e n tt r e n do f t h ed i 百t a li n f o r m a t i o n ，w h i c hi sn u m e r o u s ，v a r i o u sa n du p d a t e dq u i c k l y ，w e bd a t am i n i n g h a sb e c o m et h ep r i n c i p l ew a yt oa c c e s st h ei n f o r m a t i o n ，w h i l ep e o p l ec h o o s es e a r c h e n g i n ea st h ei m p o r t a n tt o o lf o ro b t a i n i n gi n f o r m a t i o n t h e r ei sap r o b l e mt h a tt h e t r a d i t i o n a ls e a r c he n g i n ed o w n l o a d sw e bp a g e sb yc r a w l e ri nt h ew a yo fe x h a u s t i v e w h i c hi sn o tr e a l i s t i c ，b e c a u s ei tc a n tm e e tt h en e e d so fr a p i d l yg r o w t ho nw e b i n f o r m a t i o n s i m u l t a n e i t y , s o m ef e a t u r e so fw e bi n f o r m a t i o nm a d em i n i n gd a t ab ys e a r c h e n g i n e e rr e a l l yd i f f i c u l t ，s u c ha st h em o u n to f d a t ai sm a s s ，t h ei n f o r m a t i o ni sc o m p l e x ，t h e s i t u a t i o no fi n t e m e ti se s s e n t i a l l yd y n a m i c ，u s e r sh a v ed i v e r s ec h a r a c t e r s ，a n ds oo n t h e r e f o r e ，t o p i c s p e c i f i cs e a r c he n g i n ee m e r g ea n dc a u s eag r e a td e a lo fa t t e n t i o no f r e s e a r c h e r s t h ec r a w l e ro ft o p i c - s p e c i f i cs e a r c he n g i n ec a l l e dt o p i co r i e n t e dc r a w l e r t o p i co r i e n t e dc r a w l e rd o w n l o a d sw e bp a g e sw h i c hr e l a t e dt os p e c i f i ct h e m ef r o m i n t e m e tt om e e tu s e r s q u e r y t h ea d v a n t a g eo ft h i sm e t h o di sl e s st i m es p e n d i n g ，s m a l l e r s t o r a g es p a c ea n dc a nm e e tt h eu s e r s p e r s o n a l l yn e e d f u r t h e rm o r e ，i tc a nc h o o s et h e z o n er e l a t e dt os p e c i f i ct h e m er a p i d l yt oc r a w la n dd o w n l o a du s e f u lw e bp a g e sb y a u t o m a t i ci d e n t i f yt h et h e m ei n f o r m a t i o n i nt h i sw a y , t h i sc r a w l e rc a r le f f e c t i v e l ya v o i d c r a w l i n gu n r e l a t e dz o n ea n dp r e p a r er i c hd a t ar e s o u r c ef o rt o p i c o r i e n t e du s e r s q u e r i e s b u tc o n s i d e r e dt h ec o m p l e xo fw e bs t r u c t u r ea n dr e a l - t i m eo ft o p i c o r i e n t e dc r a w l e r ，h o w t oi m p r o v et h ec r a w l e r sa b i l i t yt oi d e n t i f yt h e m e ? h o wt od o w n l o a dm o t et h e m e - r e l a t e d w e b p a g e si nl e s st i m e ? h o wt oo v e r c o m eu n r e l a t e dw e bp a g e sa n dg e tt h eu s e ri n t e r e s t e d w e bp a g e s ? a l la b o v ep r o b l e ma r em a t t e r so nt o p i c - s p e c i f i cc r a w l i n gs t r a t e g yw h i c hn e e d t os o l v ea n dh a sb e c o m eah o tr e s e a r c hp o i n t s s t u d y i n gs e v e r a le x i s t i n gs t r a t e g i e so ft o p i c s p e c i f i cc r a w l i n g ，w ef i n dt h a tt h e s e s t r a t e g i e sa b o u tr a n ko f p r e d i c t i v eu r l sa r eb a s e do nk e y w o r d s t h a ti s ，t h ep r e d i c t i o no f c r a w l i n gd i r e c t i o nh a sn o ts u c c e e d e di np r e d i c t i n gb ya n a l y z i n gs e m a n t i c i nt h i sp a p e r ， w ep r e d i c tt h ec r a w l i n gd i r e c t i o no ft o p i c s p e c i f i cc r a w l e rb ym i n i n gt h ec o n t e n ta n dl i n k i n f o r m a t i o no ft h ed o w n l o a d e dw e bp a g e s u s i n gt h et e c h n o l o g yo ff o r m a lc o n c e p t a n a l y s i s ，w ed oc l u s t e ra n a l y s i so nt e x tc o n t e n tf i r s t l y , t h e n ，p r e d i c tt h ec r a w l i n gd i r e c t i o n b yc a l c u l a t i n gt h es e m a n t i cs i m i l a r i t yo fc o n c e p t s i nc o n c e p tl a t t i c e ，s ot h a t ，t h ep r e d i c t i o n o ft o p i c s p e c i f i cc r a w l i n gd i r e c t i o nw i l lb ei nt h el e v e lo fs e m a n t i cp r e d i c t t h ec o n t r i b u t i o n so ft h ed i s s e r t a t i o na r es u m m a r i z e da sf o l l o w i n g ： ( 1 ) w ei n t r o d u c ec o n c e p tl a t t i c ei n t os e m a n t i cs i m i l a r i t yc a l c u l a t e ，a n dc o n s t r u c t c o n c e p tl a t t i c ea su s e r sc o n t e x ti n f o r m a t i o nb yu s i n gt h et h e m e - r e l a t e dw e bp a g e sw h i c h i i i 基于概念背景图的爬行策略研究 h a v eb e e nd o w n l o a d e d ，t h e nm a pt h ec o n c e p tl a t t i c ei n t oc o n c e p tc o n t e x tg r a p h w e c a l c u l a t et h ec o n c e p ts i m i l a r i t yb e t w e e nw e bp a g e sa n dc o n c e p tc o n t e x tg r a p ht op r e d i c t t h ep r i o r i t yo fu r l sw h i c hw i l lb ec r a w l i n g ( 2 ) w ep r o p o s ean o v dm e t h o do fc o n c e p tc o n t e x tg r a p h sc o n s t r u c t i o n t h e r ea r e l o t so ft r a d i t i o n a lc o n s t r u c t i o n a p p r o a c h e s ，s u c ha sd i l i g e n t ip r o p o s e d l i n kc o n t e x t g r a p h ( l c g ) i n 【1 4 】，w h i c he n t i r eb a s e dt h el i n kr e l a t i o nb e t w e e nw e bp a g e s c h i n g c h i h s u p r o p o s e dr e l a t ec o n t e x tg r a p h ( r c g ) i n 州w h i c ha d dt h es i m i l a r i t yc a l c u l a t i o ni nt h ew e b p a g e s l i n kr e l a t i o n s h i p o u ra p p r o a c hi sb a s e do l lc o n c e p tl a t t i c e ，w h i c hm a pe v e r y c o n c e p ti n t ot h ec o n t e x tg r a p ha c c o r d i n gt h er e l a t i o n s h i po fa t t r i b u t e so ft h ec o n c e p t st o f o r m u l a t et h ec o n c e p tc o n t e x tg r a p h ( 3 ) w ep r o p o s eat o p i c - s p e c i f i cc r a w l i n gs t r a t e g yb a s e do na n a l y s i so ft e x tc o n t e n t a n dl i n ki n f o r m a t i o n t h o u g ht h ec o n c e p tc o n t e n tg r a p hw ec a l c u l a t et h ew e bp a g e s s e m a n t i cs i m i l a r i t y , a n de n s u r et h ed o w n l o a d e dw e b p a g e sc l o s e rt ot h et h e m e c o m b i n i n g t h ew e bp a g e s l i n ki n f o r m a t i o nt og u i d et h ec r a w l i n gc a nm a k es u r et h ec r a w l e rc h o o s e t h ec o r r e c tc r a w l i n gd i r e c t i o n ，a n ds k i pt h e m e u n r e l a t e dz o n et oa r r i v et h et h e m e r e l a t e d z 0 n e ( 4 ) w eo b t a i nw e bd a t ab yc o n s t r u c t i n gt o p i c - s p e c i f i cs e a r c hs y s t e m a c c o r d i n gt h e n u m b e ro ft h e m e - r e l a t e dd o c u m e n t sa n dr e c a l la sw e l la sp r e c i s i o n ，w ee v a l u a t et h e p e r f o r m a n c eo ft h es e a r c hs t r a t e g y e m p i r i c a lr e s u l t si n d i c a t e s t h a tt h i st h es t r a t e g y p r o p o s e di no u rp a p e rp r o d u c e ss i g n i f i c a n ti m p r o v e m e n t sc o m p a r e dt ow i d t h - p r i o r i t y s e a r c hs t r a t e g ya n do t h e rp o p u l a rs e a r c hs t r a t e g yo ns a m ed a t a s e t s k e yw o r d s ：s e a r c he n g i n e ；t o p i c - s p e c i f i cc r a w l e r ；c o n c e p tc o n t e n tg r a p h ；s e m a n t i c s a n a l y s i s ；l i n k sa n a l y s i s 西华大学硕士学位论文 目录 摘要i a b s t r a c t i i i 1绪论1 1 1 课题研究的背景和意义。1 1 2 国内外研究现状3 1 3 本文的主要研究内容5 2 主题爬虫的背景知识7 2 1 主题爬虫分类7 2 1 1 基于文本内容的主题爬行7 2 1 2 基于分类的主题爬虫8 2 1 3 基于链接的主题爬虫8 2 2 查询意图提取9 2 3 主题页面的分布特性1 0 2 3 1 h u b a u t h o r i t y 特性：1 0 2 3 2 l i n k a g e s i b l i n gl o c a l i t y 特性1 o 2 3 3站点的主题特性1 0 2 3 4 隧道特性10 2 4 相关性计算1 1 2 4 1 基于u r l 的相关性计算1 1 2 4 2 基于内容的相似度计算1 1 3 基于形式概念分析的概念相似背景图1 3 3 1 形式概念分析1 3 3 1 1 形式概念分析研究现状1 3 3 1 2 形式概念分析理论基础1 4 3 2 概念相似度计算15 3 2 1 概念格构建方法1 5 3 2 2 概念相似度计算17 3 3 概念相似背景图构建1 9 3 3 1 核心概念1 9 3 3 2 概念相似背景图的建立2 1 3 4 本章小结2 6 v 基于概念背景图的爬行策略研究 4 基于语义背景图和链接分析的主题爬虫策略2 7 4 1 主题爬虫的体系结构图2 7 4 2 链接分析的相关知识2 8 4 2 1 链接行为动力研究2 8 4 2 1 链接上下文分析2 9 4 3 链接与主题的相关性判定3 0 4 4 基于概念背景图和链接分析的主题爬行策略3 2 5实验3 4 5 1 系统构建3 4 5 2 实验过程3 5 5 2 1 实验数据集的介绍3 5 5 2 2 概念背景图的构建3 9 5 2 - 3 基于概念背景图和链接分析的爬行策略4 2 5 3 结果分析4 2 5 3 1 评价指标4 3 5 3 2 对比策略。4 3 5 3 3 结果分析4 3 结论。4 6 参考文献4 8 攻读硕士学位期间学术论文及科研情况。5 4 致谢5 5 v i 西华大学硕士学位论文 1绪论 随着互联网的快速发展，信息化网络服务在人们的日常生活中变得非常普遍，如何 在浩瀚无边的网络信息中找到用户所需要的信息变得越来越重要。据统计，互联网信息 每天都以指数级别增长，目前数字信息已呈现数量庞大、类型繁多、更新迅速等发展趋 势。在如此类型繁多更新速度之快的形势下，如何高效抓取和检索这些文档，以缓解信 息爆炸给人们带来的信息查找的压力，已经成为一个新的研究热点。目前，w e b 数据挖 掘已经成为现在人们信息获取的主要方式，搜索引擎成为人们获取信息的重要工具。例 如：目录结构式搜索引擎y a h o o ，全文信息检索式搜索引擎g o o g l e 、b a i d u 、s o s o 等。 但是这些还远远不能满足人们在数以万亿计的网络资源中获取想要的信息，近年来基于 w e b 的智能化、主题化信息检索研究正逐步展开，它将改变并解决目前搜索引擎中遇 到的各种问题和矛盾，提供从信息过渡到知识的检索方式。搜索引擎的智能化、个性化 发展，已经显得尤为紧迫。 1 1 课题研究的背景和意义 w e b ( 全称万维网，w w w w o r l dw i d ew e b ) n 务是目前应用最为广泛的i n t e r n e t 服 务，它能够在i n t e r n e t 上方便快捷的浏览和传递分布于网络各处的文字、图像、声音和 超文本信息。这些信息主要以h t m l 语言编写的文本，分布在世界各地的w e b 服务器 上，通过超链接将它们联系起来。随着w e b 技术的成熟，互联网的信息爆炸式发展， 人们如何快速的在互联网上找到自己想要的信息，面临着巨大的考验。信息检索 ( i n f o r m a t i o nr e t r i e v a l 简称r ) 通常是将信息按照一定的方式组织和存储起来，并根据 用户的需要找出有关信息的过程和技术【l 】。搜索引擎是互联网快速发展中信息检索的主 要工具，自i n t e r n e t 诞生，搜索引擎逐渐成为人们获取信息的主要方式，搜索引擎技术 也在不断的完善和发展，从早期的简单分类目录已经发展到具有复杂算法和庞大集群系 统的高级应用服务，一些搜索引擎已经开始引入了智能化信息检索技术来提高信息收集 和查询的质量。通用搜索引擎在过去的十多年中发挥了其巨大的潜力【2 。8 1 ，它将网络这 个充斥各种资源的、杂乱的信息源变成了一个规整的信息数据库，帮助人们方便的检索 到自己想要的信息，成了互联网上除电子邮件以外最多人使用的网上服务。 通用搜索引擎特点是尽可能多地在互联网上采集资源，甚至是整个w e b 上的资源， 而在这一过程中它并不太在意页面采集的顺序和被采集页面的相关性，希望通过索引尽 可能多的w e b 资源去满足各种用户的查询，而付出了巨大的索引维护代价。随着网络 资源的爆炸式和无规则增长，主要存在的问题如下所述： 基于概念背景图的主题爬行策略研究 ( 1 ) 网页数量以指数数量级增长，更新速度过快，超过了传统搜索引擎的处理能 力，导致信息检索不准确、不全面，更新不及时，目前通用搜索引擎仅仅只能够覆盖互 联网的5 0 7 0 w e b 页面例。 ( 2 ) 维护代价太高，为了保存爬虫抓取回来的网页需要大量的存储空间，并且索 引库中保留大量参考价值不高的页面，检索速度慢，更新速度慢。 ( 3 ) 主要采用的是关键词匹配模式的检索方式，检索过程是在原文中查找用户所 输入的关键词，没有挖掘词语之间的语义关联，没有考虑词语的近义同义关系，不可避 免地会带来实际检索结果与用户需求之间的偏差。 ( 4 ) 无法满足人们个性化的需求。用户的兴趣爱好和思维方式千差万别，即使输 入相同的查询串，所要搜索的目标网页也可能不相同，通用搜索引擎没有考虑用户的个 人兴趣爱好，导致检索准确率不够。 通用搜索引擎在信息采集的时候采用大而广的原则，即在抓取网页的时候不考虑各 个页面的下载优先级，尽可能多的采集资源，决定了它在维护的时候代价高，动态更新 的速度慢，导致用户在检索时，一些重要的信息无法被检索到。随着互联网上网页的快 速增长，通用搜索引擎的性能问题也面临着严重的考验。 为了解决以上问题，通常采用分布式并行策略，需要在爬虫进行数据采集的过程中 对资源进行评分，即优先下载和主题相关的网页，因此对智能的、主题的搜索引擎研究 成为热潮，在这些搜索引擎中，主题爬行( t o p i c s p e c i f i cw e bc r a w l e r ) 策略成为最为关键 的一个研究部分。主题爬行虫在w e b 上抓取与用户主题兴趣相关的网页，它的优点是 优先检索与主题相关性高的网页，同时尽可能少的遍历与之不相关的网页，可以有效减 小搜集的范围，提高资源的利用率，通过对用户主题兴趣进行分析学习，针对用户感兴 趣的主题进行集中、深入式的搜索，有效的提高查全率和精确率，同时只要较少的存储 空间和分析时间，能够做到实时搜索。 一个好的主题爬行虫主要包括以下三个部分： ( 1 ) 种子u r l s 。种子u r l s 与主题尽可能相关，并且它们到达的网页可以覆盖 w e b 上与主题相关的大部分资源，才有可能从这些u r l s 出发找到尽可能多的与主题相 关的网页。 ( 2 ) 用户搜索意图的准确描述。因为爬虫要将抓取回来的网页内容同用户的搜索 主题进行对比，所以要准确的提取用户的查询主题，搜索意图描述的准确性，直接影响 着搜索的质量。 ( 3 ) 待爬行u r l $ 相关性预测。在爬行之前，爬虫必须有能力对待爬行的u r l s 进行主题相关性预测，根据预测相关性的高低对u r l s 进行优先级排序，从而进行爬行。 西华大学硕士学位论文 主题爬虫和通用搜索爬虫的最大区别主要是在u r l s 的爬行预测方面，对待爬行的 网页进行主题相关性预测，对爬行回来的网页进行主题相关性评价。主题相关性评价主 要是网页与主题相似度的判定，但是大部分都是基于关键词的向量空间模型，即认为关 键词之间都是相互独立的，对爬行预测停留在关键词匹配的层面上，没有挖掘词语之间 的语义关联，也没有考虑词语之间的同义近义关系。如果将网页的语义信息加入到爬虫 的主题预测和判定中，让机器理解w c b 网页的语义信息，将会为用户提供更有效的检 索结果。 1 2 国内外研究现状 主题爬虫的特点就是在爬行的过程中，优先的去抓取与用户主题兴趣相关度高的网 页。有选择的穿过与主题不相关的区域，快速到达主题相关的区域。在爬行的过程中采 用边爬行边计算的方式，通过分析已经抓取回来的网页和用户的查询主题的相关性来对 待爬行的u r l s 进行得分预测。通用爬虫通常按照广度或深度优先原则遍历w e b 有向图， 缺乏网页内容的细致分析，过多的采集了无关和无意义的页面。因此对主题爬行的研究 成为当前的热点。 1 9 9 4 年d e b r a 等人提出的“f i s h s e a r c h ”1 1 0 】，被认为是最早的主题爬虫算法，它将主 题爬虫比喻为鱼群，当发现食物( 相关信息) 时进行繁殖( 抓取子链接) ，来继续寻找 食物；当没有食物或水( 带宽或存储资源) 时，则死掉。利用二值判定内容与查询主题 是否相关，算法的关键是根据代表用户感兴趣的种子站点和主题关键词，动态维护待爬 行u r l s 的优先级队列。1 9 9 8 年h e r s o v i c i 等人提出了“s h a r k s e a r c h ”【l ，对“f i s h s e a r c h ” 进行了两点改进，一是将相似度度量范围从二值改为连续值o 1 之间；二是相似度计算 上不但继承了双亲的值，而且充分利用了锚文本和其上下文。 1 9 9 8 年，s t a n f o r d 大学的c h o e 坦】将著名的p a g e r a n k 算法应用于爬行策略中，通过页 面p a g e r a n k 得分预测页面重要程度，较好的结合了深度优先和广度优先两种方法的优越 性，使得搜索更加高效。 c h a k r a b a r t i 等人在1 9 9 9 年设计了一个较完备的基于分类器预测方法的主题搜索引 擎模型【1 3 】。系统抓取网页的过程是，先由用户从某一开放的分类目录体系，如y a h o o 分类层次目录中选取若干个子类节点作为主题信息，这些节点包含的一些页面作为训练 集，构造一个分类器。当抓取到一个新的页面时，首先提交到分类器进行相关度判断， 如果页面是个正例，则由此页面指向的超链放入工作池作为待抓取连接；否则将此页面 去掉。 基于概念背景图的主题爬行策略研究 2 0 0 0 年，d l i g e n f i 等人提出了基于背景图( c o n t e x t 铲a p h ) 的搜索策略【l4 1 。算法认为具 有相同主题的页面具有相似的链接结构，通过构建页面的链接关系来构建背景图，最后 判断一个新页面所在背景图中的层次，来预测这个页面距离主题页面的距离，从而决定 页面中待爬行u r l s 的优先级。2 0 0 6 年h s u 等人在背景图的基础上又提出了相似背景图 【l5 1 ，主要是通过计算已经检索的文档和主题之间的距离，并且结合特定主题关键词和一 般关键词的分布来构造相似背景图，来对待爬行u r l s 进行排序。 m e n c z e r 等人在2 0 0 1 年的研究评估了几种不同搜集策略的优劣【l6 】，指出一个好的 面向主题搜索引擎应该将搜索的范围尽量保持在空间中与主题邻近的区域内。总共评估 了三种不同的搜集策略： ( 1 ) b e s t f i r s t 搜集器：优先队列中u r l s 对应的优先级是包含该链接的原网页与主题 的相关度，采用了文本信息检索中常用的向量空间模型( v s m ) 求相似度的方法。 ( 2 ) p a g e r a n k 搜集器：以网页评分( p a g e r a n k ) 的高低为顺序搜索，每搜集2 5 个网 页重新计算一次评分。 ( 3 ) i n f o s p i d e r s ：使用神经网络算法，考虑链接周围的上下文。 实验发现b e s t f i r s t 表现出性能最优，能将搜索范围始终限制在搜索主题周围。 p a g e r a n k 对于主题搜索任务来说，搜索的主题过于通用化，不能体现具体的主题。 i n f o s p i d e r s 方法则介于两者之间。 c h a k r a b a r t i 等人将页面相关性判断和页面重要性评价分开，结合了相关性反馈， 取得了不错的效果。2 0 0 3 年e h r i g 等人将基于本体的思想应用到主题爬行中【1 8 】。2 0 0 5 年r u n g s a w a n g 等人利用对已经收集到的网页进行学 - - j 1 9 】，来指导以后的爬行行为。 g u a t a m 等人【2 0 】采用支持向量机对页面分类，以三种不同的链接背景进行链接价值的预 测来指导主题爬行的方向。a l m p a n i d i s 等人【2 l 】将文本内容和超连接结合起来，通过构建 邻接矩阵进行分析来进行爬行预测。2 0 0 7 年董占到2 2 】将形式概念分析引入到主题爬行 中，提出了形式背景图，初步探讨了概念之间的距离，根据距离公式计算概念之间的相 似度。2 0 0 8 年杨月奎在文献 2 3 1q b 也将形式概念分析使用到主题爬行中，使用了形式背 景图，求概念与核心概念之间的相似度，来预测网页的相关得分来指导爬行。2 0 0 9 年吴 世杰在文献 2 4 中提出了基于支持向量机分类算法的主题爬虫策略，该方法引入了一种 偏移因子，对分类函数进行了修正，只需要计算二类分类器，减少了误分类网页数。2 0 0 9 年葛玲在文献 2 5 】中提出了基于查询词扩展的主题爬行方法，将基于共现词的语义查询 扩展算法和f d c - - t o p i es e n s i t i v ep a g e r a n k 算法应用到主题的相关性评价中来指导爬 行。 4 西华大学硕士学位论文 上面这些文献的爬行方法都是对整个页面进行分析，采取的是粗粒度，页面内的待 爬行u r l s 所赋予的权重都是一样的。另外还有一类主题爬虫，通过分析链接的上下文， 对一个页面中的不同u r l s 所赋予的权重不一样，粒度比较细。2 0 10 年郑凯在文献 2 6 】 中提出了基于动态评价u r l 链接结构的主题爬行策略，该方法在深入分析了h t m l 页 面的超链结构的基础上，加入了锚文本内容分析权重和动态评价策略，提出了算法的改 进，形成了综合动态价值的u r l 链接结构的搜索策略。改进的算法根据链接类型的不 同赋予了不同的权重因子，并结合了动态价值评价穿越”隧道”，简化了优先级的计算， 有效地降低了“短视问题和“主题漂移”现象，是一种高效实用的主题采集策略。文 献 2 7 总结对比了以上两类爬行策略，并提出了基于网页分块的策略，结合了二者的优 缺点，发现具有一定穿越遂道的能力。 2 0 0 6 年a n n af o m l i c a 【2 8 】结合领域本体的知识对概念格中概念之间的相似度进行了 分析，并且结合信息内容的方法又对其进行了改进【2 9 】。李新春【3 0 】也结合领域本体，对 概念之间，概念与概念格，概念格与概念格之间的相似度都进行了研究。 如何抽象地表示用户的主题兴趣，如何在爬行的过程中对主题进行相关性判定，如 何在爬行的过程中快速地穿越与主题无关的区域，提高爬虫预测的准确性，以及爬虫在 爬行过程中对用户兴趣的学习能力，降低计算的时间复杂度，成为主题爬行亟待解决的； 问题。 1 3 本文的主要研究内容 主题搜索引擎将通用搜索引擎的抓取和解析两个阶段合并在一起，在海量的信息资 源中快速的发现更多有效的资源，从而满足用户的需求。主题爬行在爬行的过程中，对 采集回来的网页进行分析，提取其中的信息知识和链接u r l s ，先对网页进行主题相关 性判定，通过分析计算预测其中的u r l s 得分，为下一次的爬行方向做出指导。分析的 过程包括理解用户搜索意图，页面与主题的相关性判断等。将用户搜索意图和爬行回来 的页面内容进行相关性判断，将简单的词条匹配升级为语义匹配的层面，来更好的满足 用户检索目的，提高检索的准确性。 本文就是为了解决以上问题，通过查阅文献，在以往研究的基础上，提出了基于形 式概念分析的概念相似背景图，将相似度计算提高到概念语义匹配的层次来计算网页与 主题的相关度。同时对网页的链接进行分析，提出了基于网页内容分析和链接分析的主 题爬行方法。本文主要研究内容及组织结构如下： 第一章介绍本课题的研究背景和意义，主题搜索及主题爬行的研究现状与应用。 5 基于概念背景图的主题爬行策略研究 第二章介绍主题搜索的一些理论基础和相关知识。包括爬虫的分类，用户意图的提 取，w e b 主题页面的特性和相关性的计算方法四个环节。这四个环节是一个好的主题爬 虫必不可少的，对其进行了探讨，并将在后续我们的模型中加以应用。 第三章提出基于形式概念分析的概念相似背景图模型。研究了形式概念分析的理 论，通过将抓取回来的网页构建一个形式背景，生成概念格，并通过概念格中核心概念 和其它概念的属性的关系来形成概念相似背景图，其中包括核心概念的定义和概念背景 图的构建。 第四章将网页的链接分析引入的主题爬行中来，对网页的链接进行主题相关性预 测，对链接进行剪枝处理，去掉与主题不相关的网页，预先爬行与主题相关的网页。 第五章实验，将我们提出的算法模型应用到系统中去，并通