（管理科学与工程专业论文）面向领域的垂直搜索引擎的研究与实现.pdf

r e s e a r c ha n di m p l e m e n t a t i o no ft h ed o m a i n - - d e p e n d e n t v e r t i c a ls e a r c hs y s t e m at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g b y q i uw e i l i n ( m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g ) t h e s i ss u p e r v i s o r ：p r o f e s s o rc a o y a n m a y 2 0 1 1 t 6 附4删46帅9 8他_哪y 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文= = 亘囱塑燮的垂直塑塞曼! 墼的硒塞墨塞现：，o 除论文中已经注 明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或 未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名：鲤垒捧 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全 文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式出版发 行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密d ( 请在以上方框内打“4 ”) 敝储签名舣导师躲 日期：2 - or 年莎月上7 日 中文摘要 摘要 伴随着w e b 2 0 的疯狂普及，网络信息资源的膨胀速度也呈指数增长，海量的 数据资源已经远远超出搜索引擎所能覆盖的范围，要想使用传统的搜索引擎技术 快速、准确地查找所需信息变得越来越困难。数据量惊人的递增速度使得通用搜 索引擎难以及时地更新索引数据库；庞大的网页资源也使得通用搜索引擎深入地 抓取信息变得更加困难。针对这些缺点，新一代搜索技术垂直搜索引擎应运 而生。 垂直搜索引擎是通用搜索引擎的细分和延伸，它只针对某一个行业或主题，为 特定人群提供有价值的信息和相关服务。主题爬行和检索服务作为两个重要环节 在很大程度上影响着垂直搜索引擎查询的准确率和检索效率。如何快速高效地判 断并预测主题相关网页，以及如何带给用户清晰、准确的检索反馈成为制约垂直 搜索引擎发展的两大难题。因此，如何改善这两个环节成为本文工作的出发点。 本文提出了基于分类法的目录式主题描述法，并以此实现了新的主题爬行策 略。使得主题爬虫不再盲目的预测主题相关网页的方向，而是通过赋予在o d p 中 不同层次位置的主题结点不同的权重值，更加准确地指导主题爬虫的爬行。在搜 索结果呈现方面，本文采用聚类搜索引擎的优点，通过基于主题短语的方法，对 文档特征项进行更加准确的提取，并以此指导聚类工作，用聚类呈现的方式给予 用户更加方便的查询体验。最后本文通过设计对比试验来验证二者的有效性。 关键词：垂直搜索；主题爬虫；主题描述：聚类 英文摘要 a b s t r a c t w i t ht h ec r a z yp o p u l a r i t yo fw e b 2 0 ，t h ee x p a n s i o ns p e e do fn e t w o r ki n f o r m a t i o n r e s o u r c e si sa l s og r o w i n ge x p o n e n t i a l l y , m a s s i v ed a t ar e s o u r c e sf a rb e y o n dt h es c o p eo f t h es e a r c he n g i n ec a i lc o v e r , i no r d e rt ou s et h et r a d i t i o n a ls e a r c he n g i n et e c h n o l o g y q u i c k l ya n da c c u r a t e l yf i n dt h er e q u i r e di n f o r m a t i o nb e c o m e si n c r e a s i n g l yd i f f i c u l t a l a r m i n gr a t eo fi n c r e a s eo ft h ea m o u n to fd a t am a k e st h eg e n e r a ls e a r c he n g i n ei s d i f f i c u l tt op r o m p t l yu p d a t et h ei n d e xd a t a b a s e ；v a s tw e br e s o u r c e st om a k et h eg e n e r a l s e a r c he n g i n e sc r a w l - d e p t hi n f o r m a t i o nb e c o m e sm o r ed i f f i c u l t i n r e s p o n s et ot h e s e s h o r t c o m i n g s ，an e wg e n e r a t i o no fs e a r c ht e c h n o l o g y v e r t i c a ls e a r c he n g i n e sc a m ei n t o b e i n g v e r t i c a ls e a r c he n g i n ei st h eb r e a k d o w no fg e n e r a ls e a r c he n g i n e sa n de x t e n s i o n ， o n l yf o rap a r t i c u l a ri n d u s t r yo rs u b j e c t ，f o rt h es p e c i f i cg r o u po fp e o p l ew i t hv a l u a b l e i n f o r m a t i o na n dr e l a t e ds e r v i c e s t o p i c sc r a w l i n ga n dr e t r i e v a ls e r v i c e sa st w o i m p o r t a n ta s p e c t st oal a r g ee x t e n ta f f e c tt h ev e r t i c a ls e a r c he n g i n eq u e r ya c c u r a c ya n d e f f i c i e n c yo fr e t r i e v a l h o wq u i c k l ya n de f f i c i e n t l yd e t e r m i n ea n dp r e d i c tt h et o p i c p a g e sa n dh o wt og i v et h eu s e rc l e a ra n da c c u r a t ef e e d b a c ka sac o n s t r a i n tt or e t r i e v et h e v e r t i c a ls e a r c he n g i n ed e v e l o p m e n tt h et w op r o b l e m s t h e r e f o r e ，h o wt oi m p r o v et h e s e t w oa s p e c t sb e c o m e st h es t a r t i n gp o i n to ft h i sa r t i c l e i nt h i sp a p e r , t h ed i r e c t o r y - t y p ec l a s s i f i c a t i o nb a s e do nt h et h e m ed e s c r i p t i o n ，a n d t h u ss u b j e c tt oa c h i e v ean e wc r a w l i n gs t r a t e g y f o c u s e dc r a w l e rm a k e sr e l e v a n tt ot h e s u b j e c tn ol o n g e rb l i n d l yp r e d i c tt h ed i r e c t i o no ft h ep a g e ，b u tb yg i v i n gt h el o c a t i o no f t h eo d pi nt h es u b j e c to fd i f f e r e n tl e v e l so fd i f f e r e n tn o d ew e i g h t sm o r ea c c u r a t e l y g u i d et h ec r a w l i n gr e p t i l et h e m e t e r m si nt h es e a r c hr e s u l t sp r e s e n t e di nt h i sp a p e rt h e a d v a n t a g e so fu s i n gc l u s t e r i n gs e a r c he n g i n e ，p h r a s e - b a s e dt o p i ca p p r o a c h ，f e a t u r ei t e m s o nt h ed o c u m e n tam o r ea c c u r a t ee x t r a c t i o na n dc l u s t e r i n gt og u i d et h ew o r k ，p r e s e n t e d w i t hac l u s t e rt og i v eu s e r sam o r ec o n v e n i e n tw a yq u e r y e x p e r i e n c e f i n a l l y , t h i sp a p e r v e r i f yt h ev a l i d i t yo ft h et w ot h r o u g ht h ed e s i g no fc o m p a r a t i v et e s t t ov e n f yt h e v a l i d i t yo ft h et w o k e yw o r d s ：v e r t i c a ls e a r c h ；f o c u s e dc r a w l e r ；t h e m ed e s c r i b e ；c l u s t e r i n g 目录 目录 第1 章引言1 1 1 课题研究背景与意义1 1 2 国内外研究现状( 相关研究) 2 1 3 本文研究的主要内容3 1 4 论文的组织结构4 第2 章垂直搜索引擎的核心技术6 2 1 搜索引擎的组成及工作原理6 2 2 垂直搜索引擎的特征一7 2 3 主题爬行技术8 2 3 1 通用爬虫与主题爬虫8 2 3 2 主题爬行的理论基础9 2 3 3 主题爬行策略研究9 2 4 文本聚类技术15 2 4 1 文本聚类的过程16 2 。4 2 传统的聚类算法17 2 5 本章小结1 9 第3 章主题爬虫搜索算法的改进2 0 3 1 主题描述方法及存在问题2 0 3 1 1 主题描述方法2 0 3 1 2 存在的问题2 2 3 2 基于分类法的目录式主题描述法2 2 3 2 1 目录式主题描述法2 2 3 2 2 主题向量表示2 5 3 3 待爬行链接优先级计算2 7 3 3 1 主题链接优先级的规范化描述2 8 3 3 2 基于锚文本的链接优先级计算2 8 3 4 自适应主题爬行算法2 9 3 4 1 不同粒度优先级计算策略顺序2 9 3 4 2 路径探测深度3 0 3 4 3 自适应主题爬行算法3 0 3 5 本章小结3 2 目录 第4 章搜索结果聚类研究3 3 4 1 网页文本预处理中文分词3 3 4 1 1 中文分词分类3 4 4 1 2 基用于垂直搜索引擎中的不足3 5 4 1 3 适用于垂直搜索引擎的分词方法3 6 4 2 基于主题短语的搜索结果聚类3 7 4 2 1 文档的特征项提取3 7 4 2 2 主题短语的提取3 8 4 2 3 改进的k m e a n s 聚类算法4 0 4 3 本章小结4 4 第5 章实验与结果分析4 5 5 1 系统设计4 5 5 1 1 基本功能需求分析4 5 5 1 2 功能模块分析4 5 5 1 3 开发环境设置4 6 5 2 系统实现4 7 5 2 1 爬虫模块实现4 7 5 2 2 信息抽取模块实现5 0 5 2 3 信息索引模块实现5 2 5 2 4 用户接口模块实现5 4 5 3 结果对比和评价5 4 第6 章总结与展望5 7 6 1 总结5 7 6 2 展望5 7 参考文献5 9 致 射6 3 面向领域的垂直搜索引擎的研究与实现 第1 章引言 1 1 课题研究背景与意义 随着网络信息时代的迅猛发展，互联网上的各种信息对我们的生活产生着越 来越深的影响，我们可以通过点击鼠标来轻松的查询我们所需的各种信息。但同 时，面对这样一个信息量急剧爆炸的时代，快速、准确的查询到我们所需要的信 息也变得越来越难。 万维网( w o 订dw i d ew e b ) 是一个高度开放、异构的、分布式的巨大的资料 空间，它没有统一的管理，信息资源杂乱无章地散布在全球各个站点，而且更新 速度极快。在查找用户真正感兴趣的信息时，无异大海捞针，为此用户需要耗费 大量的时间和精力。于是，搜索引擎应运而生。g o o s e 的巨大成功让整个世界都 把目光投入到搜索引擎这个领域中，一夜间，各种各样的搜索服务席卷而来。伴 随着w e b 2 0 的疯狂普及，网络信息的膨胀速度也呈指数增长，数据量已经远远超 出搜索引擎所能覆盖的范围。英国网络服务公司n 咖a f l 在2 0 1 1 年2 月份的一次 调查中，侦测时收到了2 8 4 ，8 4 2 ，0 7 7 个站点的反馈信息【1 】，面对目前如此海量的信 息资源，即使最著名的g o o s e 也只能覆盖全部信息的3 0 4 0 t 2 1 ，传统搜索技术 的局限性日益突出，已经难以满足用户的需求，这方面包括：无法搜集w e b 上的 全部网页；查询结果网页与用户查询信息的相关度不高；对用户的查询需求缺乏 有效的理解。可见，w e b 用户与w e b 信息资源之间出现了巨大的鸿沟：一方面， w e b 信息资源中蕴含着极其丰富有效的信息；另一方面，用户却无法高效的通过 传统搜索技术来获取这些信息。于是，垂直搜索引擎应运而生，作为一种更智能、 更专业的搜索技术，将w e b 上的信息资源更好的呈现了出来。 垂直搜索引擎( v e r t i c a ls e a r c he n 百n e ) 是面向某一个行业的专业搜索引擎， 是对w e b 中某个主题的信息进行爬行、抓取、索引并整合，定向分字段抽取出所 需的数据进行处理后，以满足w e b 用户需求的形式返回给用户，是搜索引擎的细 分和延伸【3 】。它是相对通用搜索引擎的信息量大、查询不准确、深度不够等提出来 的新的搜索引擎服务模式，更注重面向特定领域或主题。服务上具有行业色彩， 关注的信息搜索范围并非整个w e b ，而是与某个主题相关的【4 1 。特点包括： 第1 章引言 ( 1 ) 面向特定领域，主题资源覆盖度高，专业性强； ( 2 ) 是个性化服务，考虑了用户的需求； ( 3 ) 效能更高，只搜集与领域相关的信息数据； 垂直搜索引擎相对于通用搜索引擎，在某一领域可以为用户提供更为详尽、 准确的数据信息，这种差异化的服务可以更好的满足w e b 用户。例如有了电子产 品方面的垂直搜索引擎，我们可以快速的找到喜好产品的价格、配置、主要功能 等信息，而不只是谷歌、百度为我们提供的那些泛泛的介绍性网页。 1 2 国内外研究现状( 相关研究) 国外的垂直搜索引擎技术研究较早，目前其垂直搜索引擎市场已经较为成熟， 所涉及的领域也相当广泛，在美食、健康、旅游、购物、房产、求职、汽车、娱 乐等领域已经有较为成熟的产品m 】。如找房子的垂直搜索引擎z i l l o w 、 h o m e t h i n k i n g 、h o u s i n g m a p 、p a g o u 等；购物搜索引擎t h ef i n d 、p r i c e f i g h t 、m p i r e 、 w i z e 、w i s t s 等；找工作的i n d e e d 、d e e p d o 、j o b u i 等。 美国的h e a l t h l i n e 医疗垂直搜索平台使用组合语义查询技术和全面消费健康分 类学。h e a l t h l i n e 分类数据由超过8 5 0 0 0 0 项医疗相关元数据和5 0 0 0 0 条相互关联的 医疗概念组成。这些独特的资源使h e a l t h l i n e 翻译每天用户使用语言以便精确地匹 配医疗术语，使得消费者能迅速从结果中判断确切的需要信息。 与国外相比，国内相关方面的研究相对较晚，比较被人们熟悉的垂直搜索引 擎网站有以奇虎为代表的论坛搜索引擎，以酷讯为代表的生活搜索引擎，以去哪 儿为代表的旅游搜索引擎以及以搜职为代表的招聘搜索引擎等等。 赛迪网的“i t 罗盘”是以精选式r r 垂直搜索为特征的搜索引擎，它垂直定位 于i t ，分类科学，查询简捷，具备网站、网页、目录、新闻、滚动新闻等多种检 索方式，结合了网站的分类检索、和网页精确检索等方面的优势，全面、系统、 精确、完整地提供有关i t 行业领域的信息资源和服务，更贴切地满足用户需求， 是一个目前中文领域内真正意义上的i t 垂直搜索引擎。 “去哪儿 ( q u n a r c o m ) 是旅游领域被人们所熟知的垂直搜索引擎代表，为 旅游者提供国内外机票、酒店、度假和签证服务的深度搜索，帮助中国旅游者做 出更好的旅行选择。凭借其便捷、人性且先进的搜索技术，“去哪儿 对互联网 面向领域的垂直搜索引擎的研究与实现 上的机票、酒店、度假和签证等信息进行整合，为用户提供及时的旅游产品价格 查询和信息比较服务。- 虽然国内已经出现诸如上面提到的比较成功的垂直搜索引擎网站，但是所涉 及到的领域很少，并不够普及，而且由于中文词汇组合变化的复杂性，也给中文 搜索引擎带来了不少难题，所以，国内的垂直搜索引擎的发展潜力是很大的f 6 1 1 。 垂直搜索引擎的关键技术有主题爬虫和中文分词等。主题爬虫技术是垂直搜 索引擎的关键部分，直接决定了垂直搜索引擎的质量。专业网络蜘蛛从上世纪九 十年代中期的文本分类工作发展而来，到九十年代末已经成为一个热点的研究领 域。 主题爬虫技术的研究成果有：c h a k r a b a r t ie ta 1 实现了一个免定制和存储管理的 专业爬行器【5 】；r e n n i e 和m c c a l l u m 6 】将巩固学习( r e i n f o r c e m e n tl e a r n i n g ) 【7 】引入 到网络蜘蛛的学习过程，通过训练发掘出链接文本中“隐含 的结构信息来指导 爬行器工作；d i l i g e n t i 8 】提出了基于语境图的搜索策略，它通过构建典型页面的w e b “语境图来估计离目标页面的距离：为避免p a g e r a n k 算法的“主题漂移”问题， 斯坦福大学计算机科学系的t a h e rh a v e l i w a l a 提出了主题敏感t o p i cs e n s i t i v e p a g e r a i l l ( 算法【9 】等等。 中文分词技术是中文搜索引擎重要的组成部分，自从八十年代初中文信息处理 领域提出中文分词以来，中文分词研究全面兴起，取得了一些重要的进展和一些 实用性的成果。目前分词的方法主要分为三大类：机械分词方法、基于统计的分 词方法和基于理解的分词方法。机械分词方法需要分词词典的支持，具有效率高， 算法简单的特点；基于统计的分词方法根据词的频度来判断成词的概率，这种方 法能有效地识别新词，但效率往往没有机械分词方法高；基于理解的分词方法通 过让计算机模拟人对句子的理解，达到识别词的效果，由于语言知识和语言规则 过于复杂，因而这种方法尚处于研究的阶段。 1 3 本文研究的主要内容 本文在对通用搜索引擎和垂直搜索引擎工作原理及特征等各方面的分析、研究 的基础上，重点研究了主题爬虫的抓取和对搜索结果的聚类呈现技术。 首先在主题爬虫方面，对于不相关页面的处理方式是主题爬行技术要解决的关 第1 章引言 键问题，当前主流的主题爬行算法也都是基于这方面作为出发点进行研究的。本 文从主题描述这个网页相关度判断的最根本点入手，提出基于分类法的目录式主 题描述法，并以此作为主题爬行算法改进的切入点进行研究，提高主题爬虫的网 页抓取效率。 其次在搜索结果聚类之前的网页预处理，垂直搜索引擎需要一种适合于它的中 文自动分词技术。受首字哈希结构的启发，本文采用一种双哈希的索引结构，使 中文自动分词技术在垂直搜索引擎中发挥更好的效果。 最后，对搜索结果的聚类呈现，本文提出一种基于主题短语的特征项提取方法， 更加准确地提取关键短语项代表文档以便之后聚类的进行。聚类算法方面，在综 合的考虑了聚类的准确性以及算法的时间复杂度之后，本文使用一种改进的 k m e a n s 算法，在保证聚类准确性的基础上尽量缩短用户的查询等待时间，提高聚 类的效率。 1 4 论文的组织结构 本文总体分为六章，各部分的组织结构如下： 第一章，介绍搜索引擎产生的背景，通过分析通用搜索引擎的局限性，指出垂 直搜索引擎的研究意义，并对国内外相关领域较为成熟的垂直搜索引擎做一说明， 简单介绍国内外的研究现状。 第二章，对搜索引擎的相关技术进行介绍。首先，介绍搜索引擎的组成以及工 作原理，并对通用搜索引擎与垂直搜索引擎的区别进行阐述。其次从搜索引擎的 网页抓取、索引器、检索器和查询接口四个部分对各核心技术进行阐述分析，为 后续章节的扩展和改进做好铺垫。 第三章，对主题爬虫的搜索算法进行改进。摒弃传统的主题爬虫搜索策略的研 究思路，不再纠结于不相关页面如何处理这个问题，而是从主题描述法入手，提 出一种基于分类法的目录式主题描述方法，并据此给出新的主题爬虫搜索算法， 改善主题爬虫的抓取效率。 第四章，对搜索结果的聚类呈现进行研究。首先在网页文本的预处理方面，采 用一种双哈希的索引结构，使得中文自动分词在垂直搜索引擎中的效率得到更好 的发挥。其次提出一种基于主题短语的特征项提取方法，并对k m e a n s 聚类算法进 面向领域的垂直搜索引擎的研究与实现 二一一 行改进，完成对搜索结果的聚类呈现。 第五章，实验与结果分析。本章根据系统的功能需求，对系统的整体框架进行 了设计，描述了面向电脑产品领域的垂直搜索引擎的实现过程，并将前几章所研 究的内容应用到垂直搜索引擎中来。 第六章，总结与展望。对全文的工作进行了总结，并提出了在今后需要进行的 深度研究及改善的方面。 第2 章垂直搜索引擎的核心技术 第2 章垂直搜索引擎的核心技术 2 1 搜索引擎的组成及工作原理 用户在使用搜索引擎进行查询时，将查询内容提交后，搜索引擎并非立即在 互联网上搜索资源，形成相关网页并呈现给用户。实际上，搜索引擎事先会在互 联网上抓取很多网页资源，对其进行解析排序后，建立起索引数据斟4 8 1 。然后 根据用户所提交的查询条件，对检索数据库中的内容进行相关度方面的匹配后， 将匹配结果返回给用户。所以此时在接到查询指令后，只是在内部进行搜索。 现在的通用搜索引擎在工作流程上可以分为三部分：信息采集、建立索引和 检索服务f l o 】。 ( 1 ) 信息采集 搜索引擎对互联网信息资源的抓取下载是靠一个叫网络蜘蛛或网络爬虫的 程序来实现的，它能够在互联网中不间断的漫游、发现并搜集网页信息。在爬行 的过程中，系统会维护一个链接队列，网络爬虫从给定的种子结点出发，搜索并 下载相应的网页，解析之后从中抽取出新的u r l s 并加入到该队列中。如此反复， 不断重复上面的过程，直到链接队列为空或者达到预先设定的抓取数量。网络蜘 蛛在对w e b 资源进行搜寻并下载时，一般会采用某种策略以达到其抓取目标，如 广度优先策略或者深度优先策略 ( 2 ) 建立索引 网络爬虫抓取的网页资源并不能马上用于建立索引，因为抓取的网页资源使 h t m l 形式的，而建立索引的文档则要求是纯文本文档，所以信息采集过程完成 后，首先要对网络爬虫抓取到的网页资源进行预处理。在对网络资源进行模块分 析、解析网页标签、去除标点符号、去除停词等工作后，将纯文本形式的文档提 取出来后从中提取索引项，形成索引表。索引技术的好坏将对搜索引擎产生很大 的影响，高效的索引将极大的提高搜索引擎的运行效率和质量。目前常采用“倒 排序 数据结构，即将文档中包含的关键词作为索引，文档作为索引目标【1 1 】。 ( 3 ) 检索服务 在接到用户的查询条件后，首先要对w e b 用户提交的查询内容进行必须的 预处理之后，该过程与建立索引时的处理方法相同。之后，检索器将对索引库中 面向领域的垂直搜索引擎的研究与实现 的文档进行快速地检索，通过特定的算法计算出这些网页资源与查询关键词的相 关度之后，将检索结果进行排序后，按照相关度递减的顺序将搜索结果呈现给用 户以满足用户快速查阅。 2 2 垂直搜索引擎的特征 垂直搜索引擎概念的提出，就是针对性的为某一特定领域、某一特定人群或 某一特定需求提供的有一定价值的信息和相关服务【12 1 ，因此其在数据对象的处 理方面与通用搜索引擎存在着一定的差别。 ( 1 ) 关注一个特定领域的数据或对象 垂直搜索引擎可以按领域划分为租房、旅游、健康、美食、博客等，也可以 按照对象分为视频、图片、产品、文献、职位等。垂直搜索总是针对某一个领域 或者对象，面向的主题通常就是跟行业有关的。而且某一行业的信息在互联网上 的分布并不是杂乱无章，而是少而局簇的，总会有一定数量的集中。因此相对于 通用搜索引擎的巨大开销，垂直搜索引擎要小很多。 ( 2 ) 对数据的处理更加深入 我们知道，通用搜索引擎要尽可能多的抓取w e b 上的网页资源，因此网络 爬虫在抓取策略上通常选择广度优先搜索，这导致通用搜索引擎对某个单一领域 无法进行深入的数据处理。而垂直搜索引擎的优势就在于此，通过搜索它可以不 断地积累自己的行业知识，形成领域本体，并通过完善自然语言处理方法和数据 挖掘等手段，发现信息间的关联和趋势，达到数据深入处理的目标。如何为用户 提供更好的查询结果，这是垂直搜索引擎赖以生存的关键。 ( 3 ) 数据的结构化抽取 垂直搜索引擎和通用搜索引擎最大的区别是对网页信息进行了结构化信息 抽取，即将网页的非结构化数据抽取成特定的结构化信息数据【1 3 】。通常传统的 搜索引擎在进行w e b 搜索时是以网页为最小单位的，但由于垂直搜索引擎在网 页抓取量上大大少于通用搜索引擎，所以垂直搜索引擎会对数据进行例如：去重、 分类等加工处理，再以满足用户个性化需求的方式返回给用户【1 4 】。这样就大幅 度地加快了用户获取所需信息的速度。 第2 章垂直搜索引擎的核心技术 2 3 主题爬行技术 2 3 1 通用爬虫与主题爬虫 网络爬虫是一个从w e b 上自动抓取网页的程序，它为搜索引擎从互联网上 下载网页，是搜索引擎的重要组成部分，也是搜索引擎工作流程中的起点【1 5 】。 w e b 上的网页集合就像一张巨大的有向图，网络爬虫从一个或若干个种子站点开 始，利用h t t p 协议下载相应的w e b 页面，提取页面上的u r l s 并加入到队列 中，然后从队列中选择下一个u r l ，继续抓取并解析，对这些u r l s 进行判断， 查看是否已经被访问过，将未被访问的u r l s 加入到队列中。循环重复上述整个 过程，直到队列为空或满足系统的抓取要求才停止。网络爬虫的工作方式从整个 w e b 有向图来看，就像是从一开始几个离散的点，通过w e b 页面间链接形成的 边，逐步访问整个有向图的每个结点。整个抓取过程就像是网络爬虫按照深度优 先、广度优先或其他策略对w e b 这张巨大的有向图的遍历过程。 传统的网络爬虫，即通用爬虫，在抓取策略上通常采用广度优先遍历的原则， 这样可以保证从w 曲中尽可能多的抓取网页信息，以达到最大的资源获取量。 为了防止出现爬虫重复访问某个链接的情况，在下载前要查询已下载队列。查找 的时候，在线性存储的待下载链接队列中，寻找某个链接需要扫描一遍待下载队 列，而频繁的这样扫描的代价是很高的。因此，在实现中，通常还维护了一个散 列表，散列表中的元素跟队列中的元素时刻保持一致，这样做，可以加快查找速 度，但是也占用了很多的存储空间【16 1 。 随着w e b 2 0 的疯狂普及，网页数量越来越多，而且由于互联网的“蝴蝶结 形状【l7 1 ，通用爬虫越发不可能遍历w e b 上的所有网页资源，做到及时更新更要 付出难以想象的代价。于是主题爬虫技术应运而生。主题爬虫是垂直搜索引擎的 核心和基础，与通用爬虫不同的是，主题爬虫并不以尽可能多的抓取网页为目的， 而是尽可能多的抓取与主题相关的w e b 页面。在主题爬行的过程中，爬虫会根 据其特有的主题爬行算法对发现的u r l s 进行主题预测，过滤掉与预定的目标主 题无关的u r l s ，保留与主题相关的链接并加入到等待抓取的u r l s 队列中，重 复上述过程，抓取任务会在队列为空或达到系统预定条件后停止。另外，在网页 的抓取策略方面，主题爬虫往往既不采用广度优先策略，也不采用深度优先策略， 面向领域的垂直搜索引擎的研究与实现 而是按照相关度大小的最佳优先策略，即对链接队列中的u r l $ 按照相关度递减 的原则进行抓取。 2 3 2 主题爬行的理论基础 从整体上看，w e b 上的网页信息资源的分布显得杂乱无章，并无规律，但实 际上并非如此。w e b 上很多网页资源都是系统化的，网页间通过u 订链接彼此相 连，从表面上看这些链接是随意的，然而仔细研究会发现其中的规律。网站的设 计者在设置这些链接的时候并不会随意放置，网页上的每个链接指向的一定是与 当前网页内容相关的网页。这就意味着，w e b 上面向某一领域或者某一主题的网 页资源是趋向于相互链接的，这就是w e b 的主题局部性。而主题爬行的相关技 术就是基于这个重要的假设，从种子结点出发，来搜索邻近的主题相关的网页。 从理论上说，通过一个好的起始结点，我们可以找到与目标主题相关的所有网页。 2 3 3 主题爬行策略研究 通用爬虫的抓取目标是提高网页覆盖率，尽可能的搜集到w e b 上的所有网 页资源，而主题爬虫关心的只是行业相关资源，抓取时只选择目标主题的w e b 页面。在浩瀚的w e b 资源空间中，这些行业信息的网页分布是无法得知的，为 了更加有效的提高主题爬虫的抓取效率，准确的预测爬行方向，研究者们提出了 许多相关算法和策略。 1 、基于内容评价的搜索策略 这一策略的设计思想就是通过计算页面文本与主题集之间的相关度，按照相 似度高低来决定带爬行队列中链接的爬取顺序【1 8 1 。常用的主题相关度计算方法 主要有两种：布尔模型和向量空间模型。 ( 1 ) 布尔模型： 布尔模型是最容易实现的主题相关度的计算方法。在布尔模型中，经过一些 处理工作，每个文档和主题用一组关键词的集合来表示。这样要完成文档与目标 主题的相关度评估工作，只要对两个关键词集合计算即可。在两个关键词集合的 交集中，包含的元素越多，则说明该文档与主题的相关度越高。我们用d 表示 文档，t 代表主题关键词集合，二者交集的元素个数即是我们关心的主题相关度 s i m ( d ) ，公式( 2 1 ) 如下所示： 第2 章垂直搜索引擎的核心技术 s i m c 铲 亿1 ， 布尔模型的优点在于具有清楚和简单的形式，易于实现，而且计算代价较小； 缺陷则在于每个关键词的权重都一样，缺乏文档分级的概念，不支持设定关键词 的相对重要性，限制了检索功能。 ( 2 ) 向量空间模型 向量空间模型( v s m ：v e c t o rs p a c em o d e l ) 由s a l t o n 等人于二十世纪七十 年代提出，并成功地应用于著名的s m a r t 文本检索系统。它考虑了关键词的权 重，弥补了布尔逻辑模型中关键词具有相同权重的缺陷，很好地运用到主题相关 性判别中【1 9 1 。向量空间模型概念简单，它把对文本内容的处理简化为向量空间 中的向量运算，并且它以空间上的相似度表达语义的相似度，直观、易懂。它的 基本思想是，把文档看作一系列词( t e r m ) ，每一个词( t e r m ) 都有一个权重( t e r m w e i g h t ) ，不同的词根据自己在文档中的权重来影响文档相关性的打分计算。主 题关键词向量与文档向量类似，用主题关键词向量中的权重来表示对应关键词相 对于该主题的重要性。 我们把某文档中所有词的权重看作一个向量。 d o c u m e n t = t e r m1 ，t e r m2 ，t e r n 3n d o c u m e n tv e c t o r = w e i g h tl ，w e i g h t2 ，w e i g h tn 同样我们把关键词看作一个简单的文档，也用向量来表示。 q u e r y = t e r m1 ，t e r m2 ，t e r mn ) q u e r yv e c t o r = w e i g h tl ，w e i g h t2 ，w e i g h tn ) 我们把所有搜索出的文档向量及查询向量放到一个n 维空间中，每个词 ( t e r m ) 是一维。 我们认为两个向量之间的夹角越小，相关性越大。所以我们计算夹角的余弦 值作为相关性的打分，夹角越小，余弦值越大，打分越高，相关性越大。我们知 道，主题关键词一般很短，包含的词并不多，所以关键词向量的维数很小。而文 档很长，包含的词也很多，文档向量维数很大，之所以两者的维数都设成n ，是 进行计算，维数自然应该相同。不同时取二者的 重为0 。相关性计算公式( 2 2 ) 如下： 面向领域的垂直搜索引擎的研究与实现 肋嘶= 隔= 一亿2 ， 第2 章垂直搜索引擎的核心技术 咫( 彳) = ( 1 一d ) n 袱( 丁，) c ( 丁f ) ( 2 3 ) 公式2 3 中： p r ( a ) 页面a 的p a g e r a n k 值； p r ( 正) 页面z 的p a g e r a n k 值，页面i 链向页面a ； c ( z ) 页面z 链出的链接数量； d 阻尼系数，d = 0 1 ，实际应用时设为0 8 5 ； n 一互联网上所有的网页数量。 p a g e r a n k 是一个与查询无关的静态算法，所有网页的p r 值通过离线计算获 得；有效减少在线查询的计算量，降低了查询响应时间【2 4 】。但是p a g e r a n k 算法 的缺点也显而易见，它并没有考虑到与主题的关系，忽略了主题相关性，容易出 现“主题漂移”现象，即虽然得到了权威性较高的网页，但却与用户查询的主题 无关。 ( 2 ) h i t s 算法 h i t s ( h y p e r l i n k i n d u c e dt o p i cs e a r c h ) 是由k l e i n b e r g 在9 0 年代末期提出 的基于链接分析的网页排名算法。它为网页提供两个参数：权威型权值 ( a u t h o r i t y ) 和目录型权值( h u b ) 。权威型网页对于其领域的检索会提供最有 价值的链接信息，而目录型网页则提供很多指向其他高质量的权威型网页的链接 【2 5 1 。该算法的基本思想就是：第一，好的目录型网页指向好的权威型网页；第 二，好的权威型网页被好的目录型网页所指。 为了方便理解，用有向图来表示网页间的链接关系，图中的每个节点都分别 对应一张网页，而网页p 指向网页q 的链接则用有向边( p ，q ) 表示，节点的出 度、入度分别表示网页链出和被指向的网页数量。h i t s 的算法流程【2 6 1 如下： 将查询x 提交给检索系统，从返回结果的页面集合取排名前n 个网页( 通常 取2 0 0 ) ，作为根集合( r o o ts e t ) ，设该结果集为r 。 扩充根集合，主要分为两个方面，一是将r 中页面所指向的网页扩充进去； 二是从指向结果集r 中的每个网页的链接页面中，取任意d ( 通常取5 0 ) 个页 面扩充到原来的结果集r 中，形成新的基本集合b ( b a s es e t ) 。b 的数量范围通 扛 d + 面向领域的垂直搜索引擎的研究与实现 常在1 0 0 0 5 0 0 0 。 按照公式( 2 4 ) 迭代计算h u b s 和a u t h o r i t i e s 的值。 口( p ) = eh ( ，。) ”1 ( 2 4 ) n h ( p ) = 口( g 。) ，= l 其中，a ( p ) 表示页面p 的权威权重；h ( p ) 表示页面p 的中心权重；是 链接到p 的页面；q ，是页面p 链接出去的页面。 为使其能收敛，每次计算完成后都进行规范化处理，直至满足公式( 2 5 ) ： h ( p ) 2 = l p p ( 2 5 ) 3 、基于未来回报价值评价的搜索策略 通过多年来对w e b 资源的分布特点研究我们发现，w e b 信息资源在分布上， 无论是类型相同的w e b 站点构建的方式，还是相关主题页面的组织