已阅读5页,还剩66页未读, 继续免费阅读
(计算机软件与理论专业论文)深度网络信息爬取关键技术研究与实现.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
浙江大学硕士学位论文 摘要 摘要 随着互联网的不断发展,网络中的信息量呈现几何级的爆炸式增长我们根 据网络信息的获取方式不同可以把互联网分为浅层网络与深度网络二部分。浅层 网络通过网页中的超链接即可以爬取。深度网络中的信息隐藏在网页搜索框背 后,用户必须以向网页表单提交查询词的形式才能获取信息。 由于深度网络明显区别于浅层网络的信息获取方式,使得传统的基于超链接 的网络爬虫无法爬取并索引深度网络中的信息。随着深度网络中的数据规模及质 量不断提高,获取其中信息对于搜索引擎来说意义重大。 本文提出一种基于最优查询词的深度网络爬虫。我们的方法解决了现有深度 网络信息爬取中自动化程度低,适用领域窄的问题。本文设计的深度网络爬取系 统包含三个核心算法:深度网络入口的智能识别方法,通过统计学 - - j 大量的表单 网页控件、文本环境、网站深度特征,实现深度网络入1 2 智能识别;最优查询种 子集生成算法,提出了将含有表单的网页划分为表单控件空间与网络文本空间二 个子空间,并在此划分的基础上对表单网页进行聚类,获得最优查询种子集;最 优查询词提交及反复迭代算法,设计了一种对最优查询词不断提交及迭代更新的 循环算法,在爬虫不断获取最新深度网络信息的基础上,同步更新最优查询词列 表。 最后是系统的设计实现及算法的测试结果。在提出理论分析的基础上完成了 系统的编码实现,并通过实验验证了算法的有效性。 关键词:搜索引擎;深度网络爬虫;网页聚类;最优查询词 浙江大学硕士学位论文a b s t r a d a b s t r a c t a st h ei n t e m e tc o n t i n u e st od e v e l o p ,t h ea m o u n to fi n f o r m a t i o ni nt h en e t w o r k g r e wr a p i d l y b a s e do nt h ed i f f e r e n c eo fa c c e s s i n gi n f o r m a t i o n ,i n t e r n e tc a l lb e d i v i d e di n t os h a l l o wn e t w o r ka n dt h ed e e pw e b w ec r a w l e ds h a l l o wn e t w o r kb y m e a n so fh y p e r l i n kw h i c hc a nb ec a r r i e do u to n ac o m m o ns e a r c he n g i n e w h i l ed e e p w e bi n f o r m a t i o nh i d d e nb e h i n dt h ew e bs e a r c hb o x ,t h eu s e rm u s ts u b m i tq u e r i e si n t h ew e bf o r mt oo b t a i nt h ei n f o r m a t i o n a st h em e t h o do fc r a w l i n gi n d e e pw e bc l e a r l yd i s t i n g u i s h e df r o ms h a l l o w n e t w o r k ,w h i c hm e a n st r a d i t i o n a lh y p e r l i n k b a s e dw e bc r a w l e rc a nn o tc r a w la n d i n d e xd e e pw e bi n f o r m a t i o n w i t ht h eg r o w t ho fu s e f u li n f o r m a t i o ni nt h ed e e pw e b , a c c e s s i n gi n t ot h ed e e pw e bi so fs i g n i f i c a n c em e a nf o rt h es e a r c he n g i n e s w ed e s i g n e dad e e pw e bc r a w l e rb a s eo nt h em o s te f f i c i e n tq u e r i e s o u rm e t h o d s o l v e dt h ep r o b l e m so fl o wl e v e la u t o m a t i ca n dd o m a i nc o n s t r a i ni nt h ed e e pw e b c r a w l i n g o u rd e e pw e bc r a w l e rc o n t a i n e dt h r e ec o r ea l g o r i t h m s r e o r g a n i z a t i o n so f e n t r yo fd e e pw e b ,t r a i n i n ga l g o r i t h m st h r o u g hal a r g en u m b e ro fh t m lp a g e sf o r m c o n t r o l ,t e x tc o n t e x ta n dd e p t hi nt h es i t e c a l c u l a t i o no ft h em o s te f f i c i e n ti n i t i a l q u e r i e s ,d i v i d i n gt h ef o r mp a g ei n t ot w os p a c e sw h i c ha r ef o r ma n dt e x tc o n t e x ts p a c e , t h e np e r f o r m e dk m e a n sa l g o r i t h mu pc r a w l e dp a g e st og e tt h ec a n d i d a t eq u e r i e s s u b m i t t i n gt h em o s te f f i c i e n tq u e r i e st os i t e ,a n a l y z e dt h er e s u l tp a g e st ou p d a t e c a n d i d a t eq u e r i e si t e r a t i v e l y f i n a l l y , w ed e s i g n e ds y s t e ma n dt e s t e da l lt h ea l g o r i t h m s w ec o m p l e t e dt h es y s t e m c o d i n gw o r kb a s e do nt h et h e o r e t i c a la n a l y z i n g e x p e r i m e n tr e s u l t sv e r i f i e dt h e e f f e c t i v e n e s so ft h ea l g o r i t h m k e y w o r d s d e e pw e b ;d e e pw e bc r a w l e r ;p a g ec l u s t e r ;m o s te f f i c i e n tq u e r i e s 浙江大学硕十学位论文图目录 图目录 图2 - 1 一个典型的爬虫体系架构9 图2 - 2 典型的分布式爬虫体系架构1 0 图2 - 3u r l 队列容器的设计架构1 0 图2 - 4 具有明显类别特征的数据集合1 1 图2 - 5 对新闻搜索的结果进行聚类1 2 图2 - 6 数据的反复聚类、选取迭代过程13 图2 - 7 聚类结果集合1 8 图2 - 8 模式实时变换技术2 1 图2 - 9 基于深度网络表面化的技术2 2 图3 - 1 深度网络爬虫的工作流程2 3 图3 - 2 一个典型的表单代码2 5 图3 - 3 二种表单的控件数量特性2 6 图3 - 4 几种分类算法的错误率2 6 图3 - 5 深度网络入口深度分布2 7 图3 - 6 表单网页过滤器2 7 图3 - 7 网页p c 、f c 部分裁剪2 9 图3 - 8 网页裁剪3 5 图3 - 9 表单模型的构建3 6 图4 - 1 垂直搜索引擎的体系结构4 1 图4 - 2z v e r ti c a1 s e a r c h 搜索引擎搜索结果4 2 图4 - 3 垂直搜索引擎的体系结构4 2 图4 - 4 爬虫的核心类i n d e x l i n k s 设计4 4 图4 - 5 爬虫的核心类l i n k 设计4 5 图4 - 6i n d e x l i n k s 类控制爬行4 5 图4 7 爬虫配置文件的设置4 6 图4 8 爬虫正在爬取网页内容4 6 图4 - 9h i 1s 文件夹,存放种子文件4 6 图4 - 10 种子文件4 7 图4 - 11 链接容器的过滤机制4 7 图4 - 12 页面解析的基本流程5 0 图4 - 13 多义词索引的构建5 0 图4 - 14 聚类算法测试方案5 1 图4 15 指定每个文件夹的类型5 2 图4 - 16 第一次生成的标准结果5 2 图4 - 17 计算聚类的正确率、召回率53 图4 - 18 所有十个类别聚类结果5 4 图4 19 聚类结果的总体e n t r o p y 值5 5 图4 2o 聚类结果的总体f - m e a s u r e 5 6 图4 - 2 1 提交表单的最优关键词数量5 6 图4 2 2 爬虫的提交效率57 v i 浙江大学硕士学位论文 表目录 表目录 表3 - 1 向量空间模型中文档与空间模型的关系2 8 表3 - 2 重要页面特征提取3 0 表4 - 1 实验中部分重要参数数据5 7 v i i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发 表或撰写过的研究成果,也不包含为获得逝姿态堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名:签字日期:年月 日 学位论文版权使用授权书 本学位论文作者完全了解逝望盘鲎 有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘,允许论文被查阅和借阅。本人授权逝至三盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播,可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名:导师签名: 签字r 期:年月日签字r 期:年月r 浙江大学硕士学位论文 致谢 致谢 首先,我要感谢导师林怀忠副教授。他渊博的学识,对学科前沿的准确把握, 治学态度科学、严谨和求是,使我受益匪浅。在研究生两年半的学习生涯中,他 谦逊随和的为人作风以及严谨的治学态度不断让我向前进步,并激励着今后的生 活与工作。 其次,我要感谢师兄赵仕峰,感谢他的帮助指导。由于他的宝贵意见使我度 过一个又一个技术难关。还要感谢师弟师妹苏晓呜、蒋雨倩、王学松,在论文时 间比较紧的情况下承担了项目的大部分工作。同时要感谢同一实验室的每个同 学,感谢他们在工作、学习和生活上给予的帮助和支持,使我能够顺利完成实习 和论文工作。 此外,我还要感谢我的父母,是他们精神上以及物质上的支持,帮助我顺利 完成了学业。 最后,我要感谢所有帮助过我的老师和同学,谢谢他们的帮助和支持。 冯明远 2 0 10 年1 月于浙大求是园 浙江大学硕士学位论文 第l 章绪论 1 1 背景 第1 章绪论 随着i n t e r n e t 的飞速发展,w e b 的信息量越来越大,人们往往需要借助搜索 引擎来帮助他们寻找特定领域的资料,现有的搜索引擎如g o o g l e 、百度等得到 了飞速的发展。在对网络的了解逐渐深入后,人们认识到现有的网络内容根据获 取方式的不同可以分为二部分:通过超链接获取的浅层网络及通过网页查询框 才能获取的深度网络。 深度网络又称隐藏网络( h i d d e nw e b ) 或不可见网络( i n v is i b l ew e b ) 。1 9 9 4 年学者儿l le 11s w o r t h 第一次提出这个概念时,意指搜索引擎商不想索引或者 现有搜索引擎技术无法索引到的网络内容。c n n i c 在2 0 0 7 年发布的第十六次中 国互联网信息资源数量调查报告显示d 1 1 :中国现有的网络数据库的总量在三十万 个以上,网站中存在数据库的网站数在十七万个以上,约占全部网站的3 0 0 以上。 最近几年网络数据库的年复合增长率在8 0 左右。可见,随着网络市场需求的快 速增长,特别是电子商务的发展,人们越来越多地使用在线数据库来进行信息的 搜索。 现有的基于超链接的搜索引擎已经对浅层网络的内容有了较好的覆盖度,而 对深度网络中的信息,由于传统的爬取方式无法获取深度网络信息,故覆盖度很 低。大部分的信息都无法通过搜索引擎获取。在这种情形下,学术界对这一难题 进行了攻关。经过六、七年的研究,国外的学者已经对深度网络的爬取技术有了 一定的成果,并且在商周系统上开试用。国内的研究也有一定的开展,2 0 0 9 年 百度提出通过“阿拉丁”计划们对暗网的搜索技术进行研究。 目前因特网上的可索引到的网页数量已超过1 1 0 亿页,世界上最大的搜索 引擎g o o g l e 也只能索引到整个w e b 的3 0 - 4 0 ,这其中大部分的数据都是来自于 浅层网络。据学者k c c c h a n g 等人的研究d 1 ,深度网络的信息量大约是浅层网 络的5 0 0 倍左右,且深度网络中的结构化信息,其数据质量要大大高于浅层网络。 搜索引擎、各种目录网站目前对深层网络信息的覆盖度在3 0 左右。 本文在这种背景下,对搜索引擎的爬虫技术进行研究,在传统的爬行策略之 浙江大学硕士学位论文 第1 章绪论 上,对深度网络信息的爬取提出了新的思路和解决方法,结合这种新思路所实现 的搜索引擎爬虫能大大改善传统搜索引擎对深度网络信息覆盖不足的缺点。 1 2 搜索引擎的发展历史 在9 0 年代互联网的早期阶段,网络中的站点较少,搜索信息相对比较容易。 随着近些年来网络中的信息量呈现爆炸式的几何级增长,在网络中精确得查找需 要的信息如同海底捞针,困难重重。在这样的背景下,网络搜索引擎得到了飞速 发展,专业的搜索网站也应运而生。 最早的搜索引擎要追溯到1 9 9 0 年蒙特利尔大学学生e m t a g e 研发的a r c h i e 系统。a r c h i e 是用来在网络中的f t p 主机中搜索信息用的,由于当时万维网还 未出现,网络中的信息交流主要由网络文件传输等任务构成,因此a r c h i e 应运 而生。 a r c h i e 系统的研发原理与近代的搜索引擎系统比较类似,它首先自动搜索 f t p 服务器上的文件,然后对文件名、文件路径、相应的服务器位置等信息进行 索引,而用户则通过一系列约定的命令进行查询。a r c h i e 系统一度非常流行。 在19 9 3 年,美国的内华达大学开发了一个新的系统,该系统除了能索引f t p 服 务器中的文件外,还能检索网页。 近代的搜索引擎出现于1 9 9 4 年,当时m i c h a e lm a u l d i n 将网络爬虫与索引 程序相融合,产生了大家熟悉的l y c o s 系统。1 9 9 4 年4 月,斯坦福大学的杨致 远成立了y a h o o 公司,y a h o o 公司成功得将搜索引擎商业化,并使得网络搜索变 得广为人知。自此以后,搜索引擎的发展变进入了快车道。 1 3 搜索引擎的未来 下一代搜索引擎将具备智能、专业、个性化的特点,其中包含的可能的未来 热点技术为: 多媒体检索:随着网络传输速度越来越快,下一代互联网将是一个多媒体时 代。音视频、图片等多媒体网页内容将取代传统的文本网页,多媒体信息的检索 将是未来研究的一个热点方向。 个性化检索:个性化搜索将用户日常的信息需求习惯于信息检索技术相结 浙江大学硕士学位论文第1 章绪论 合,通过对用户信息需求的详细分析,自动调整信息搜索的结果。因此,在个性 化搜索时代,即便是同一个搜索请求,不同的用户也会得到不同的搜索结果。个 性化搜索的本质是通过与用户的交互,提高信息搜索的准确性,是从查准率的角 度对搜苏引擎发展的推动 智能搜索:智能搜索是一个非常宽泛的概念,对于“智能”一词有众多不同 的理解。所谓智能,及搜索引擎对于网页中的内容以及用户的信息需求具备一定 的理解力及创新判断力,能够综合已有的知识推断出新的信息。智能搜索的关键 技术包括文本的智能聚类、分类、同义词技术、基于概念的搜索等。同时智能搜 索将允许用户以自然语言的方式提出信息需求,如通过语音等形式。 垂直搜索:现有的通用搜索引擎对网络中的信息搜索体现出范围广、数据泛 的特点。而随着用户信息需求的不断深入,人们逐渐希望能够搜索到专业化、精 细化的信息内容。垂直搜索的关键技术在于网络爬虫,网络爬虫需要能够识别特 定领域的信息,并在特点的网络中爬取相关的信息。这样的爬虫可以将更多的资 源集中到对于特定领域信息的爬取上。并使最终的搜索结果做到专业化、精细化。 1 4 深度网络的现状 深度网络是与可以通过超链接获取到的浅层网络相对的一个概念。其最早的 提及要追溯到1 9 9 4 年j i l l 提到的i n v is i b l ew e b 一词。深度网络的信息必须被 用户通过向网页表单提交特定查询词才能获取,传统的搜索引擎很难获取这样的 网页内容d 1 ,而通过手工方法对所有的查询表单进行分类,构建相应的知识库是 一个费时费力的任务。 深度网络的内容近些年发展迅猛,通过过去几年的调查2 7 1 研究我们可以总 结出一些概况:深度网络的信息量非常庞大,其信息量大约是浅层网络信息量的 50 0 倍,网站的规模在三十万个以上,数据库四十万个以上,查询接口一百万以 上。从2 0 0 年到2 0 0 5 年,增长在三倍以上;深度网络的分布范围非常广,涉及 多个领域,其中电子商务是其的一个重点领域;由于技术原因,目前通用搜索引 擎对于深度网络的覆盖度仍不是很理想,大概在总量的三分之一左右;深度网络 中的信息以结构化信息为主,结构化的数据是非结构化数据的三倍以上,其信息 多是由网页背后的结构化数据库生成,信息的质量较高。 浙江大学硕士学位论文第l 章绪论 目前国内外对于深度网络信息的获取已有一定的经验。目前能够提供深度网 络信息的商业机构还不多,国外比较著名的有d e e pw e b 乜引,i n v i s i b l e w e b 乜 , b r i g h t p l a n t d l 等公司,但他们所使用的方法自动化程度不是很高,无法在大规 模、多领域展开使用。 1 5 本文的工作和组织 在深度网络信息爬取的关键技术方面,本文提出了一种基于最优查询的深度 网络信息爬取技术,使用k - m e a n s 算法对网页进行聚类,同时结合网页间的链接 信息改进聚类效果。之后使用聚类簇网页生成查询表单的最优查询词,并通过多 次的迭代查询以获取深度网络的数据库中的信息。 在系统的设计方面,我们设计并开发了一个兼有深度网络与通用网络信息爬 取、索引功能的搜索引擎z v e r ti c a l s e a r c h ,除了应用深度网络信息爬取的关键 技术外,该搜索引擎还能够对于特定领域的信息进行专业化的爬取、检索。 下面是本文的章节结构: 第一章绪论 介绍了本文的研究背景及搜索引擎的历史、发展趋势,深度网络发展的现状。 介绍了当前深度网络的数据量,搜索引擎对深度网络信息的覆盖度,对比了通用 搜索引擎爬虫和深度网络爬虫的主要区别,总括全篇的研究目标和各章内容。 第二章相关技术的研究现状 本章首先介绍了搜索引擎的体系框架、工作原理、关键技术;然后重点介绍 了搜索引擎中的爬虫模块的基本特征,以及当前爬虫的基本设计架构及工作原 理;之后介绍了信息检索中的文本聚类技术,先从聚类算法当前的应用情况出发, 引出现有聚类算法的发展以及评估算法效果的几个指标;最后介绍了深度网络信 息爬取的基本工作框架,并介绍了接口集成法以及数据仓库法二种深度网络信息 爬取的基本方法。 第三章基于最优查询的深度网络信息爬取关键算法 本章主要介绍了本文提出的几个主要算法:基于最优查询的深度网络信息爬 取关键算法,该算法以表单网页的聚类为基础,为每种聚类类别生成对应的最优 查询词,并自动填写并提交,以此获取深度网络中的信息。 浙江大学硕士学位论文 第1 章绪论 第四章系统设计与实现 介绍了系统的设计原型,以及系统的相关技术实现细节。 第五章总结与展望 总结全文,提出了一些不足之处,并对下一步的研究和应用做出展望。 最后是参考文献及致谢 浙江大学硕士学位论文第2 章相关技术的研究现状 第2 章相关技术的研究现状 本章主要对网络爬虫技术、文本聚类技术和深度网络信息爬取技术的研究现 状做一个概述,并对其中一些实现细节做探讨 2 1 搜索引擎基本技术 目前主流的商业搜索引擎事实上是一种通用型搜索引擎,它不区分用户的类 别,只关注搜索关键词。本节简单介绍搜索引擎的关键模块及其原理。 搜索引擎的核心模块包括网络爬虫、分词模块、索引模块、网络查询接口等 部分心1 2 引。网络爬虫主要负责网页的爬取,在爬虫将网页爬取后,分词模块与索 引模块将会对爬取的网页内容进行清洗、标注,直至建立相关文档的倒排索引库。 网络查询界面负责接收用户的查询词,并依照用户提供的组合条件对关键词进行 交、并等组合,最后网络查询界面会把搜索的结果返回给用户。 我们以典型的g o 0 9 1 e 搜索引擎为例作说明。搜索引擎如果依照功能区分, 可以分为三部分,网络网页搜索,建立索弓i ,用户查询交互。 网页搜索网页搜索部分的主要工作就是网页的爬取,主要由u r l 服务器, 网络爬虫,缓存器,页面解析器等组成,网络爬虫是网页搜索功能中的核心部件。 建立索引引入索引的目的是为了加速用户的搜索,在对文档进行建索引 前,需要使用分词程序,网页清理程序对页面进行加工,最后再制作成倒排索引。 网页查询界面主要负责用户查询词的接受,目前主流的搜索引擎都可以接 受词语、短语、语句形式的查询词,搜索引擎将根据查询词与网页的匹配度返回 结果,结果排序算法有大名鼎鼎的p r 算法等。 g o o g l e 搜索引擎的架构如图2 - 1 所示: 6 浙江大学硕士学位论文 第2 章相关技术的研究现状 图2 - 1 通用搜索引擎体系结构 搜索引擎的主要工作流程为:首先由网络爬虫在网络中爬取网页,它可以采 取深度优先、广度优先、最佳优先等算法自定义爬取策略。抓取的网页会被缓存, 在文档积累到一定数量时进行批处理。 在爬虫爬行时,网页解析器和分词器是必不可少的配合模块,主要帮助爬虫 从网页上采集新的u r l 链接;同时他们还负责网页索引的构建。 用户在进行搜索查询时,搜索引擎会首先对用户的查询词或者语句进行分词 处理,在剔除停词等后,会将核心词汇与网页进行相似度匹配,通过计算相似度 进行结果的排序,改进的排序算法包括p r 算法,h i t 算法等。 2 2 网络爬虫技术 网络爬虫的基本任务即从网络中爬取网页,并对网页中的内容进行清洗、整 理、索引,以支持用户的信息搜索。网络爬虫总是以尽可能高的效率从网络中爬 取尽可能多的有用信息。 目前的主流网络爬虫都是基于网络超链接的。爬虫的爬取工作从一个或多个 的种子u r l s 开始。被爬取的网页会被爬虫的网页解析器模块所解析,网页被解 析为内容模块与新的网页链接二个部分,网页内容部分被索引模块进一步加工处 譬页搜索 标引入库 用户查询 浙江大学硕士学位论文第2 章相关技术的研究现状 理,通常以倒排索引的形式存在于搜索服务器中。新的链接通常会被放入一个候 选队列内等待在后面被爬取。 2 2 1 网络爬虫的基本特征 通过研究当前主流的网络爬虫,我i f 总结出了以下几个特征列: 鲁棒性:网络中的不少服务器会给网络蜘蛛在有意或者无意中生存爬取陷阱 ( t r a p ) ,在陷阱网页中,爬虫往往会陷入死循环,或者爬取大量的垃圾网页。一 个好的爬虫必须有能力处理各种爬取陷阱。 分布式:现有的网络爬虫具备在多台机器上以分布式的方式工作。 高质量:网络中的大部分网页内容质量低下,无用信息较多,大部分不能满 足用户的查询需求,一个好的爬虫必须具备识别较为优质网页的能力舶。 高效更新:好的爬虫能够及时更新已经爬取过的原有信息,及时更新索引文 件,以提供用户及时的信息。从另一个角度看,一个爬虫应该以与网页更新频率 类似的频率重新爬取网页。 可扩展性:由于目前网络技术发展较快,好的网络爬虫应该具有较好的可扩 展性,如爬取新的数据格式,适应新的网络协议等。这要求在爬虫的体系结构设 计上具备较好的模块设计结构。 2 2 2 网络爬虫的基本架构 目前主流的爬虫都采用模块化的设计结构,多个不同的模块组合在一起完成 复杂的功能,典型的结构如图2 - i 所示。 浙江大学硕士学位论文第2 章相关技术的研究现状 u r l 队列l l , 一一一 图2 - 1 一个典型的爬虫体系架构 在实际应用中,爬虫往往会以多线程的方式进行并行爬取,每一个线程都将 执行如图2 - 1 所类似的流程。 1 )u r l 队列,存放待爬取的网页链接,队列内往往会采取一定的排序算法, 根据时间、重要性等特点对待爬u r l 进行排序 2 ) d n s 解析器,它将根据指定的u r l 决定从哪个服务器去获取网页 3 )获取网页模块将根据h t t p 协议从指定的u r l 处获取网页 4 )网页解析模块,对爬取的网页内容进行清洗、整理,从中整理出要索引 的文本内容及待爬链接。文本内容会首先做一个简单的判断,是否已经 被索引过,之后经分词、停词去除后以倒排索引的形式存储在搜索引擎 服务器中; 5 )u r l 过滤器,对新从网页中获取的链接进行过滤,剔除不再被爬取的链 接。u r l 过滤器的设计比较多样,一般包括正则表达式过滤,特定域名 过滤等形式。 2 2 3 分布式爬虫的设计 分布式爬虫是大规模爬虫设计的关键技术钉5 1 。分布式爬虫需要实现多个节 点爬虫问信息的交流与共享,其中的关键技术之一即使用特定的主机区分模块向 各个节点的爬虫分派待爬u r l ,分派的u r l 将被输入其他爬虫的重复链接模块, 如图2 - 2 所示。 9 浙江大学硕士学位论文 第2 章相关技术的研究现状 广 过滤信息 接发送到其 链接u p l ? ? 皇 j j一哆 叫。j u 虬龇 b 盼嗣重羹纠 来自其他 节点的信息 u r l 队列 一 图2 - 2 典型的分布式爬虫体系架构 u r l 队列容器的设计 u r l 队列容器中的u r l 来自于爬虫的爬取过程。它将会对u r l 数据进行维护 以及作必要的排序等工作。u r l 的排序主要由二个因素决定: 第一,高质量的网页,以及更新频率高的网页u r l 具有较高的优先级,会在队列 中排到较为靠前的位置。因此网页质量、更新频率是二个决定性因素 6 | 。 第二,爬取需要遵循互联网规则,对于同一网站,避免作过多过频繁的爬取。 图2 - 3 显示了一个u r l 队列容器的实现。它能够实现 1 ) 每次只能对一个主机( h o st ) 建立一个链接 2 ) 对同一主机的连续查询必须间隔几秒钟 3 ) 高优先级的网页必须被优先爬取 厂蕊蕊 一l 一 b 趴划 每个队列 兰= = : 殷r 个= = e 帆的嗍甜 图2 - 3u r l 队列容器的设计架构 浙江大学硕士学位论文第2 章相关技术的研究现状 该容器的二个主要模块是上层的f 队列以及下层的b 队列,这二个队列都是 f i f o 队列。f 队列主要实现对于u r l 的优先级排序,而b 队列实现对主机的合规 访问。当一个u r l 被添加到容器中时,爬虫首先会为其赋一个值为i 的优先等级。 例如对于一个更新率较高的u r l ,或者一个来自新闻网站的u r l 将会被赋予较高 等级。一旦一个u r l 被赋予优先级i ,则它会被排列到f 队列的第i 个位置。b 队列维护如下信息: 1 ) 当爬虫在爬取时,它总是一个非空队列 2 ) 它只会包含来自同一网站的唯一u r l 一个辅助的表t 被用来维护主机与b 队列的信息,即表明每个主机在哪个b 队列 中。一旦一个主机的u r l 被放入一个新的b 队列,则表t 要作相应的更新。 2 3 文本聚类技术 聚类算法是一种典型的无监督学习算法,它将一个集合内的数据自动划分为 不同的类别,同一类别内的文档具有很大的相似性,而不同类别问的文档则具有 很大的区别性。如图2 - 4 所示的数据集合可以很明显得看到具有三种类别的数 据。 2 5 2 鼍 1 5 、亏 : , 1 。 : t i5 以咭气、 皇 l f l1 1 5i s22 5 图2 - 4 具有明显类别特征的数据集合 聚类算法的一个关键因素是元素间相似性的计算函数,不同的计算函数能够 引出不同的聚类算法。在图2 - 4 中,散点间的相似性可以用点间的二维距离来 描述。在文本聚类中,我们通常用文本间的欧拉距离来衡量文本间的相似性。聚 类算法通常可以区别为硬聚类与软聚类二种类别。在硬聚类算法中,每一个文档 都被确定得分配到某一个类别中,即文档相对与类别的值为o 或1 ;在软聚类算 法中,每一个文档会被赋予一个关于所有类别的所属概率分布,即文档相对类别 的值为。与1 间的任意值。此外,聚类算法也有穷尽性聚类及非穷尽性聚类,二 浙江大学碗学位论文 第2 章相关拄木的研究现状 者的区别在于是否有文档未被划分入任何一个类别 2 3 1 聚类算法在信息检索中的应用现状 在信息检索中使用聚类算法时,首先需要有一个关于聚类的基本假设:同一 个类别中的文档基本能够同时满足用户某一个信息检索需隶“。这个假设即认 为,如果某一个聚类类别内的某一篇文档与用户的一个信息搜索请求相关,则类 别内的其他文档也应该可以满足该次搜索请求从直觉上即可以判断,因为同一 类别内的文档会有较多的词组相同,则他们很有可能同时满足搜索需求。在当前 的信息检索应用中,聚类算法常见的应用包括: 搜索结果聚类:搜索引擎通常会以网页列表的形式返回搜索结果,用户必须 逐篇文章查看,以确定满足需求的网页。这种方式的最大问题是加大了用户信息 分拣的工作量。当对搜索的结果网页进行聚类处理后,相似的网页将会以集合的 形式出现,这样用户查看信息的负担被大大减轻了。目前,如图2 5 所示的新闻 以及多义词的搜索往往会采用聚类技术束优化处理初次搜索结果。 拙* t i - +e t l - on l 。女厂一墅曼l 苎妻! ! ! ! 篮 , * *! “h h 1 鬟辫竺黧= 竺= 黑。 # i i ,。础t e 嗽i i e t黜r k 月p m 目b 自d 口 # i m l i * 目m 圭= i d 自叵 ! “, d i d e i d e e i 础“i ,k e “n g t 墟,q 持j a d 料! i t 目j i = e 1 腿 ! e m 二* t t t h 。自目蛳 ”一t g = i l 1 t b 自目n i | = i i 三兰堇 ? 1 m m 二一 i t d e t t m 目t t 越 e 、1 | i i 5 t 自u 目4 i b t z n i 坦 f r5 m 5 ! # e j t b e t 址 一,2 e ik 圉2 - 5 对新闻搜索的结果进行聚类 精确化用户信息需求:一些搜索引擎通过$ c a t ie f g a t h e r “的方式来对用户 的信息需求进行精确定位。s e a t t e r g a t h e r 首先会对网络中的信息作一个韧步 的聚类,把信息分为不同的类别。用户可以对感兴趣的类别进行挑选,选中的类 别内的网页台被重新混合在一起,然后重新进行聚类操作。这一过程可以进行多 次的反复迭代,直到用尸找到需要的信息。这种形式的信息检索在用户不清楚自 己的精确信息需求时特别有用。s c a t t er g a t h er 的过程如下图2 6 所示。 浙江大学硕士学位论文第2 章相关技术的研究现状 聚类( s c a t t e r ) i 教育ii 国际il 伊拉克ll 艺术ti 体育lf 石油i l 美国| l jl ,j l 一一jl 一l 一,j l 一一+ j l j g a t i i e r r 一- l 国际事件l r 一一一j l 7 聚类( s c a t t e r ) 网网匦圈圈降倒 g a t h e r j 上一 ! 国际事件j ! 、 聚类( s c a t t c r ) 7 一 厂_ 一1 也篓l 南非jl 安簟世旦 ;印墨j塑一j 图2 - 6 数据的反复聚类、选取迭代过程 加速信息检索:通常使用v s m 模型来进行信息检索时,当文档数量过大,或 使用l s i 索引而非倒排索引时,检索的速度会呈现数量级的下降。在这样的情形 下,我们可以不再逐个计算文档与查询问的相似度,而是计算查询与聚类类别的 相似度,然后再对类别内的文档进行检索排序 。因为聚类类别及每个类别内的 文档数量都大大小于总文档的数量,故检索的速度能得到极大提高。 2 3 2 聚类算法理论发展现状 常用的聚类算法可以归结为二种类型,基于层次的聚类( h i e r a r c h i c a l c l u s t e r i n g ) 与基于划分的平面聚类( f l a tc l u s t e r i n g ) 。 基于层次的聚类算法 在基于层次的聚类算法中,数据样本以树的数据结构形式存在,树中的一个 节点即一个聚类簇,整个树即为聚类结构图。 自底向上的形成的树被称为凝聚树,自顶向下的被称为分裂式层次树。在实 际应用中,层次聚类算法的复杂度较高,但聚类效果好,且可以获得类别的不同 粒度。层次聚类的不足之处在于聚类类别的不可再分性n 引。 凝聚式层次聚类( h a c ) 算法流程: 1 :初始情况下所有的数据各自形成一个聚类类别; 2 :选择聚类类别中距离函数最近( 也即最相似的二个类别) ,合并为相同的 浙江大学硕士学位论文 第2 章相关技术的研究现状 类别; 3 :只有最后一个聚类类别,或者算法达到终止条件( 如达到聚类的目标类 别) ,算法结束,否则返回步骤2 。 在上述算法中,步骤2 中寻找最相似的两个聚类类别需要用到类别簇与类别 簇之间的距离函数,具体使用的距离可以是欧拉距离、s i n g l e 一1i n kh a c 、 a v e r a g e - 1 i n kh a c 等。上述三类算法在小型的聚类分析算法中应用较多,在大 型的聚类中应用较少,因为其本身算法复杂度较高。h a c 算法的另一个用途是为 k - m e a n s 算法计算质量较高的初始类别中心。 分裂式层次聚类算法流程: 1 :初始情况下所有的数据形成一个总的聚类类别; 2 :选择特定的算法从现有的聚类类别中选择某一种类进行分拆,即一个聚 类类别一分为二; 3 :如果所有的n 个数据项形成了n 个簇( n 为文档数) 或算法达到终止条件则 结束。 分裂式层次聚类算法与凝聚式层次聚类算法是一个相反的过程。在分裂式层 次聚类算法中,步骤2 中可以选择不同的算法进行类别拆分。最容易的方法即选 择规模最大的聚类被拆分。当然也可以一句聚类有效性分析指标( 见2 2 3 节) 选择聚类内部纯度( p u r i t y ) 最差的类别进行拆分。将选中的类别拆分的方法不同 也能够产生出不同的算法。如在叫中提到的k - m e a n sb is e c ti n g 算法就是在步骤 2 时选择最大规模的聚类类别进行分裂, 分裂算法采用k - m e a n s ,将候选的类别分裂为两个类别,文献刚的实验结果 认为k - m e a n sb i s e c t i n g 的聚类效果要比单纯的k - m e a n s 好,而与h a c 相当或者 甚至更好。 基于层次的聚类算法还有:g a c 组平均聚类n0 1 、b i r c h 乜、c u r e ( 使用 r e p r e s e n t a t i r e s 技术的聚类) n 引、c h a m e l e o n 瞳叫等,这些算法都是基于层次的聚 类算法。 在文献1 的聚类算法中,该算法采用了分治的凝聚式层次思想。它将标准凝 聚式聚类算法中的步骤2 和步骤3 修改为:( 步骤2 ) 将已有的聚类类别分成大小 为m 的块;( 步骤3 ) 在各个块里分别应用凝聚式聚类;( 步骤4 ) 把各个块的计算结 浙江大学硕士学位论文第2 章相关技术的研究现状 果综合到一起,如果算法没有达到结束条件则返回步骤2 因为算法使用中间类 别来降低运算复杂度,因而保证了聚类质量。算法的计算复杂度大于0 ( n 2 ) 。 文献n 1 1 运用了增量计算的方法来进行聚类,通过对数据树的聚类特征树来进 行预聚类。聚类特征树中的每个节点保存了聚类类别的特征。b i r c h 算法依次扫 描所有的数据项,初始一轮扫描得到一个初始的聚类,后面将会以多轮扫描增进 聚类的效果。 文献乜钉中的方法改变了聚类类别的表示,聚类类别不再是单个点、单个对象, 而是用一定数量的具有显著代表性的数据来表示类别。在标准凝聚算法的步骤2 中,当需要合并聚类类别时,利用类别间的距离来选择待合并的类别。算法通过 抽取小规模样本与分而治之的方法降低计算复杂度。这个算法的时间复杂度是 0 ( n ) ,该算法具有应用于大规模聚类的潜力。 基于划分的聚类算法 k - m e a n s 聚类算法是最常用的基于划分的聚类算法,它无需构建聚类类别间 的层次关系,只需在一个平面是对数据集进行划分。它的目标函数是每一个类别 内的文档离该类别内的聚类中心( c l u st e rc e n t e r ) 的欧拉距离的平方和取最最 小值。 算法流程: 1 :初始选取k 个聚类类别的中心( 聚类类别中心) ; 2 :分别计算所有数据与已有的k 个聚类中心的距离,将数据对象放入距离 最小( 相似度最大) 的那个类别。 3 :一轮所有数据都计算完成后,重新计算k 个聚类类别的中心,中心为该 聚类类别内所有数据向量的算术平均值。 4 :如果所有聚类类别变化不大或者满足退出条件( 最大循环次数、满足某种 目标函数( o b j e c tf u n c ti o n ) 等) ,那么结束聚类算法,否则返回2 。 k - m e a n s 聚类算法是一种算法复杂度低,聚类效果好的算法。它在文本聚类 中得到极大的应用。目前业界应用的很多系统都是以k - m e a n s 算法为基础开发 的。k - m e a n s 初始需要将聚类数据对象划分成为k 个类别,i ( 是事先确定的参数, k - m e a n s 中每个类别具有一个类别中心,该中心定义为簇中对象的平均值。 每个类别的聚类中心计算如下: 浙江大学硕士学位论文第2 章相关技术的研究现状 五( 加上1w z x 式中w 即聚类中的文档集合,x 为文档集合内的文档向量。最为理想的聚类 中心位于文本空间的球心为之,其余所有的文档位于球面之上。 k - m e d o i d s 聚类算法是与k - m e a n s 相似的一种聚类算法。二者最主要的不同 之处在于前者使用类别内的某些数据对象来代表类别,而后者使用所有数据的均 值来代表类别。文献幢钔是最早提出的k - m e d i o d s 算法之一,其算法流程与k - m e a n s 相似,将标准聚类算法中的步骤3 更改:对某个聚类类别,多次迭代计算随机的 数据点与类别中心的取代代价,从而生产新的聚类类别中心。也就是说,该算法 在所有的数据项中选择替换代价最小的数据项充当新的类别中心,并对所有的聚 类类别应用,实现聚类中心的更新。该算法的缺点是算法复杂度较高。 最近邻聚类( n n ) 算法流程: 1 :随机选择一个数据项,并以其为中心建立一个新聚类类别; 2 :选择后一
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026-2027学年南阳市邓州市八年级上册物理期末检测卷含答案
- 气管楔形切除术护理规范
- 耐蚀混凝土工安全文明竞赛考核试卷含答案
- 非织造布制造工岗后模拟考核试卷含答案
- 印后成型工安全理论竞赛考核试卷含答案
- 经济昆虫养殖员岗前诚信考核试卷含答案
- 电气值班员安全强化水平考核试卷含答案
- 钛冶炼工安全实操能力考核试卷含答案
- 塑料玩具制作工安全实操能力考核试卷含答案
- 巷修工岗位评审考核试卷含答案
- 全国智慧教育知识竞赛试题及答案
- 全国灌溉水有效利用系数测算分析技术指导细则(2024修订版)
- 学校维修资金管理办法
- 加油站防雷安全隐患排查制度
- 沙因版企业文化的课件
- DBJD25-67-2019甘肃省建筑与装饰工程预算定额地区基价含税上册
- GB/T 45355-2025无压埋地排污、排水用聚乙烯(PE)管道系统
- 视频监控系统工程监理实施细则
- 内蒙古地区历年中考作文题(2002-2024)
- 婴幼儿营养与膳食管理99课件
- 机器人操作系统(ROS)课件 1.ROS简介
评论
0/150
提交评论