（计算机应用技术专业论文）基于主题的搜索引擎研究.pdf

长春工业大学硕l 学位论文 摘要 i n t e m e t 的迅速发展使其成为当今世界上最大的信息库，并日益成为人们获取所 需资源的主要来源，然而其巨大的信息量以及纷繁芜杂的内容与人们有目的的利用信 息形成了很大的矛盾。与此同时，传统的综合性搜索引擎要采集的信息以及构建索引 查询的内容不断扩大，由于其局限于试图索引全部w e b 并试图服务于所有主题的查 询请求，导致了通用搜索引擎很难再为用户提供一个全面并且更新及时的信息搜索服 务，所以如何快速、准确地从浩瀚的信息资源中找到有用的信息成为网络用户面临的 一个紧要问题。用户迫切需要一个数据分类细致、精确、全面、更新及时的搜索引擎 来获取主题资源信息。由于面向主题的搜索引擎只覆盖与特定主题相关的w e b 区域， 这样搜索可以更深，周期可以更短，因此能满足用户对获取信息资源快速、准确的性 能要求，所以成为目前研究的热点。而w e b 挖掘作为知识挖掘新的研究内容，由于 自身在信息处理中的层次较高，同时与搜索引擎的关系非常密切，对搜索引擎技术有 很大借鉴作用。所以搜索引擎通过应用w e b 挖掘技术，可以增强信息处理能力，使 得信息检索的能力满足信息化社会的发展需要。 本文首先从研究的角度对搜索引擎的产生及其发展历程进行分析，对目前综合性 通用搜索引擎的工作原理及其现状进行讨论，从而引出了传统搜索引擎面临的巨大挑 战。在此基础上对主题搜索引擎的支撑技术进行充分研究，对于导向词的使用、网页 评分、权威网页和中心网页的提取以及超链接文本分析等方面充分理解，最终确定论 文研究的主要方向为如何把w e b 挖掘领域中的研究成果应用于主题搜索引擎的设计 和实现中。本文的研究重点为以下四个方面： 1 t o p i c a l c r a w l e r 信息采集：抓住如何评价页面的主题相关性和设计高效的爬 行策略这两个关键问题。提出了基于主题策略改进网页爬行器的方法：把主 题词及相关权值、首页相关度以及基于链接的评价方法综合应用于爬行器的 改进，提高搜索引擎资源获取的主题相关度。 2 网页文本分类：采用传统的向量空间模型表示文本，采用基于词典双向最大 匹配法进行自动分词，提商文本特征抽取方面准确度，之后综合分析对比了 几种比较成熟的分类学习算法，改进了多项式朴素贝叶斯模型，提高了分类 精度。 3 基于l u c e n e 的索引与检索：在a p a c h e 开源框架l u e e n e 提供的完整的查询引 擎和索引引擎的基础上，完成索引及查询模块，对已分类的网页文本进行索 引，提高索引及查询的效率。 长备工业大学硕士学位论文 4 搜索结果聚类：研究聚类算法在搜索结果聚类的应用特性：重叠聚类、短语 表示以及简明的类定义。在进行检索时，对己检索到的结果进行聚类分析， 根据文档与用户查询的相关性聚合成相应类别，通过简明的类定义，提高查 询的准确性和实用性。 关键字：搜索引擎、爬行器、文本分类、聚类 儿 长春t 业大学硕士学位论文 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 fi n t e r a c ta st h ew o r l d sl a r g e s ti n f o r m a t i o nd a t a b a s e ， a n db e c o m et h em a i ns o u r c eo fa c c e s st on e c e s s a r yr e s o u r c e s ，h o w e v e r , i t se n o r m o u s a m o u n to fi n f o r m a t i o na n dn u m e r o u sa n dc o m p l i c a t e dc o n t e n t ，w i t hp e o p l ep u r p o s e f u l l y u t i l i z ei n f o r m a t i o n , f o r mag r e a tc o n t r a d i c t i o n m e a n w h i l e ，t h ei n f o r m a t i o nt h a tt h e t r a d i t i o n a lc o m p r e h e n s i v es e a r c he n g i n es h o u l d b eg a t h e r e da n dc o n s t r u c t i o ni n d e xi n q u i r y a r ee x p a n d i n gc o n s t a n t l y 。d u et oi t sl i m i t e dt oi n d e xa l lw e ba n da t t e m p t st os e r v et h e i n q u i r yr e q u e s to fa l lt h e m e s ，l e dt oac o m m o ns e a r c he n g i n ei sv e r yd i f f i c u l tt op r o v i d e u s e r sw i t hac o m p r e h e n s i v ea n dt i m e l yu p d a t e di n f o r m a t i o ns e a r c hs e r v i c e , s oh o wf i n d u s e f u li n f o r m a t i o nf r o mav a s tn e t w o r ko fr e s o u r c e sf a s ta n da c c u r a t eh a sb e c o m eac r i t i c a l i s s u ef a c i n gt h eu s e r u s e r s u r g e n tn e e df o rad a t ac l a s s i f i e d c a r e f u l l y ，a c c u r a t e ， c o m p r e h e n s i v ea n du p d a t e dt i m e l ys e a r c he n g i n et oo b t a i ni n f o r m a t i o nr e s o u r c e st h e m e a sw i t ht h es u b j e c t - o r i e n t e ds e a r c he n g i n eo n l yc o v e rw h i c hw e b r e g i o nr e l a t e dt os p e c i f i c t h e m e s , c a ns e a r c hd e e p e r , c y c l ec a nb es h o r t e r , i tc a l ls a t i s f yt h ei s e t sr a p i da c c e s st o i n f o r m a t i o nr e s o u r c e s ，a c c u r a t ep e r f o r m a n c er e q u i r e m e n t s ，s ob e c o m eah o tt o p i c w e b m i n i n ga san e ws t u d yo fk n o w l e d g ed i s c o v e r y ，d u et ot h e i rh i g h e rl e v e li ni n f o r m a t i o n p r o c e s s i n g ，m e a n w h i l eav e r yc l o s er e l a t i o n s h i pw i t ht h es e a r c he n g i n e ，h a v er e f e r e n c e f u n c t i o ng r e a t l yt ot h et e c h n o l o g yo ft h es e a r c he n g i n e s os e a r c he n g i n et h r o u g ht h e a p p l i c a t i o no fw e bm i n i n gt e c h n o l o g i e sw h i c hc a ne n h a n c et h ei n f o r m a t i o np r o c e s s i n g c a p a c i t ym a k i n gi n f o r m a t i o nr e t r i e v a lc a p a b i l i t i e st os a t i s f yt h ei n f o r m a t i o nn e e d so fs o c i a l d e v e l o p m e n t t h i sp a p e rf i r s t l ys t u d yf r o mt h ep o i n to f a n a l y s i so f t h ee m e r g e n c ea n dd e v e l o p m e n t o fs e a r c h e n g i n e ，d i s c u s st h ep r i n c i p l e o f g e n e r a ls e a r c he n g i n e st h e c u r r e n t c o m p r e h e n s i v ea n dt h es t a t u s ，t h u sl e a d st ot h ee n o r m o u sc h a l l e n g e sf a c i n gt h et r a d i t i o n a l s e a r c he n g i n e o nt h i sb a s i st h et h e m eo ft h es e a r c he n g i n es u p p o r tt e c h n o l o g yo ft h ef u l l s t u d y ，f o rt h eu s eo f g u i d ew o r d s ，w e b p a g eg r a d i n g ，t h ee x t r a c t i o no f t h ea n t h o r i t y sw e b s i t e a n dt h ec e n t r ew e b p a g e ，a n dt h ea n a l y s i so fh y p e r l i n kt e x tm a k ef u l lu n d e r s t a n d i n g ， u l t i m a t e l yc o n f i r mt h em a i nt h e s i st h ed i r e c t i o no fh o wt oa p p l yt h es t u d yr e s u l t so fw e b m i n i n gf i e l dt ot h ed e s i g na n dr e a l i z a t i o no ft h et h e m es e a r c he n g i n e t h ef o c u so ft h i s a r t i c l ef u rt h ef o l l o w i n gf o u ra s p e c t s ： 1 t o p i c a l c r a w l e ri n f o r m a t i o nc o l l e c t i o n ：h o wt oa p p r a i s et h i sc r a w l i n gs t r a t e g yo f t h er e l a t e dt ot h et h e m e so fp a g e sa n dd e s i g ne f f i c i e n tt w ok e yi s s u e s p u tf o r w a r dt h e m e t h o dw h i c hb a s e do nt h et h e m eo ft h es t r a t e g yt oi m p r o v ec r a w l e r ：a p p l yk e y w o r d sa n d i l l k 备工业大学硕士学位论文 r e l e v a n tr i g h tv a l u ea n dh o m ep a g er e l e v a n ta n de v a l u a t i o nm e t h o dw h i c hb a s eo nl i n k st o t h ei m p r o v e m e n to f c r a w l e ra n di m p r o v es e a r c he n g i n er e l e v a n c eo f t h et h e m e 2 w e b p a g et e x tc l a s s i f i c a t i o n ：a d o p tt h et r a d i t i o n a lv i c t o r i e ss p a c em o d e lt oe x p r e s s t h et e x t , d i c t i o n a r y - b a s e dt w o w a y m a t c h i n gt h el a r g e s tm e t h o dc a r r yo nt h ea u t o m a t i c p a r t i c i p l ew o r d s ，i m p r o v et h ea c c u r a c yo ft e x tf e a t u r ee x t r a c t i o n ，l a t e rc o m p r e h e n s i v e a n a l y s i sc o m p a r e dw i t hs e v e r a lk i n d so fr i p e rc l a s s i f i c a t i o na n ds t u d i e da l g o r i t h m s ， i m p r o v e dn a i v eb a y sp o l y n o m i a lm o d e lt oi m p r o v et h ec l a s s i f i c a t i o na c c u r a c y 3 i n d e x i n ga n dr e t r i e v a lb a s e do nl u c e n e ：o nt h eb a s i so fi n t a c ti n q u i r ye n g i n ea n d i n d e x i n ge n g i n eo f f e r e db ya p a c h el l l c e n e , c o m p l e t ei n d e x i n ga n dq u e r ym o d u l e ，i n d e x i n g t h ew e b p a g et e x tt h a th a sa l r e a d yb e e nc l a s s i f i e d ，i m p r o v et h ee f f i c i e n c yo fi n q u i r ya n d i n d e x 4 s e a r c hr e s u l t sc l u s t e r i n g ：r e s e a r c hc l u s t e r i n ga l g o r i t h mi nt h ea p p l i c a t i o no fs e a r c h r e s u l t sc l u s t e r i n g ，d u s t e ro v e r l a p ，a n dp h r a s ee x p r e s s i o na n dc o n c i s ek i n d so fd e f i n i t i o n s w h e nr e t r i e v a l ，c l u s t e ra n m y s i st h er e s u l tt h a th a sa l r e a d yb e e ns e a r c h e d , a c c o r d i n gt ot h e r e l e v a n tf i l e sa n du s e l i n q u i r i e si n t ot h ea p p r o p r i a t ec a t e g o r yc u r e db ys i m p l ec l a s s d e f i n i t i o n , i m p r o v ea c c u r a c ya n dp r a c t i c a b i l i t yo f i n q u i r e k e y w o r d s ：s e a r c he n g i n e ，s p i d e r , t e x tc l a s s i f i c a t i o n ，c l u s t e r i n g 长春1 = 业人学硕士学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经 发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本声明的法律结果由本人承担。 论文作者签名：僻 日期：问年弓月易阳 长春工业大学硕士学位论文 1 1 搜索引擎及其发展 1 1 1 搜索引擎发展简史 第1 章绪论 1 前互联网搜索时代1 - 3 1 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆炸性 的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大众信息检 索需求的专业搜索引擎便应运而生了。 现代意义上的搜索引擎的祖先是1 9 9 0 年由蒙特利尔大学学生a l a ne m t a g e 发明的 a r e h i e 。但是a r c h i e 不是真正的搜索引擎，而是第一个自动索引互联网上匿名f t p 网站文件的程序。a l a n a r c h i e 工作原理与现在的搜索引擎已经很接近。受其启发，美 国内华达s y s t e mc o m p u t i n gs e r v i c e s 大学于1 9 9 3 年开发了另一个与之非常相似的能 检索网页搜索工具。 到1 9 9 3 年底，一些搜索引擎开始纷纷涌现，其中最负盛名的三个是：s c o t l a n d 的j u m p s t a t i o n 、c o l o r a d o 大学o l i v e rm c b r y a n 的t h ew o r l dw i d ew e bw o r m 、n a s a 的r e p o s i t o r y - b a s e ds o f t w a r ee n g i n e e r i n gs p i d e r 。1 9 9 4 年4 月，互联网上第一个支持 搜索文件全部文字的全文搜索引擎w e b c r a w l e r 出现了，在它之前，用户只能通过u r l 和摘要搜索，而摘要一般来自人工评论或程序自动取正文的前1 0 0 个字。这无疑是搜 索引擎技术的一大飞跃。 2 互联网搜索时代 而最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。m i c h a e lm a u l d i n 将蜘蛛程序 接入到其索引程序中，创建了大家熟知的l y c o s 。同年，斯坦福( s t a n f o r d ) 大学的两 名博士生，d a v i d f i l o 和美籍华人杨致远( g e r r y y a n g ) 共同创办了超级目录索引y a h o o ， 并成功地使搜索引擎的概念深入人心。从此搜索引擎进入了高速发展时期。 1 9 9 5 年，第一个元搜索引擎( am e t as e a r c he n g i n er o u n d u p ) m e t a c r a w l e r 出现i 2 j 。 用户只需提交一次搜索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独 立搜索引擎，并将从各独立搜索引擎返回的所有查询结果，集中起来处理后再返回给 用户。 1 9 9 5 年1 2 月才登场亮相的a l t a v i s t a 是第一个支持自然语言搜索的搜索引擎，具 备了基于网页内容分析，智能处理的能力，第一个实现高级搜索语法的搜索引擎( 如 长春工业大学硕上学位论文 a n d ，o r ，n o t 等) ，同时还支持搜索新闻群组、搜索图片等具有划时代意义的 功能。 时至今日，搜索引擎己经成为我们日常生活中不可或缺的部分，对人们充分利用 互联网的资源起到了重要作用。 1 1 2 搜索引擎的概念及系统架构 1 搜索引擎的概念 搜索引擎f t l ( s e a r c he n g i n e ) 实际是个专用的w w w 服务器，它存有庞大的索引数 据库，收集了全世界成千上百万个w w w 主页的文字信息。为了收集这些信息，有 个自动搜索程序，沿着w w w 的超链接，经常搜索整个w w w 上的主页，然后为 这些主页上的文字建立索引并送回集中管理的索引数据库，索引信息包括文档的 w w w 地址，每个文档单字出现的频率、位置等。 2 搜索引擎的实现原理 搜索引擎的实现原理，可以看作四步：从互联网上抓取网页一建立索引数据库一 在索引数据库中搜索一对搜索结果进行处理和排序【5 j 。 1 1 从互联网上抓取网页 利用能够从互联网上自动收集网页的网络蜘蛛程序，自动访问互联网，并沿着任 何网页中的所有u r l 爬行到其它网页，重复这过程，并把爬过的所有网页收集到服 务器中吼 2 ) 建立索引数据库 由索引系统程序对收集回来的网页进行分析，提取相关网页信息( 包括网页所在 u r l 、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其它网 页的链接关系等) ，根据一定的相关度算法进行大量复杂计算，得到每一个网页针对 页面内容中及超链中每一个关键词的相关度( 或重要性) ，然后用这些相关信息建立网 页索引数据库【6 】。 3 ) 在索引数据库中搜索 当用户输入关键词搜索后，分解搜索请求，由搜索系统程序从网页索引数据库中 找到符合该关键词的所有相关网页。 4 ) 对搜索结果进行处理排序 所有相关网页针对该关键词的相关信息在索引库中都有记录，只需综合相关信息 2 和网页级别形成相关度数值，然后进行排序，相关度越高，排名越靠前。最后由页面 生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户【7 羽。图 1 - 1 是一个典型的搜索引擎系统架构图。 1 1 3 搜索引擎的分类 圉1 1 搜索引擎系统架构图 搜索引擎按其工作方式主要可分为三种，分别是目录索引类搜索引擎 ( d i r e c t o r y ) 、全文搜索引擎( f u l lt e x ts e a r c he n g i n e ) 和元搜索引擎( m e t as e a r c h e n g i n e ) 【9 】。 1 1 目录式搜索引擎 以人工方式或半自动方式搜集信息，由编辑员查看信息之后，人工形成信息摘要， 并将信息置于事先确定的分类框架中。信息大多面向网站，提供目录浏览服务和直接 检索服务。 该类搜索引擎因为加入了人的智能，所以信息准确、导航质量高，缺点是需要人 卜介入、维护量大、信息量少、信息更新不及时。这类搜索引擎的代表是：y a h o o ， o p e nd i r e c t o r y 等。 3 长存工业人学硕士学位论文 2 ) 全文搜索引擎 由一个机器人程序( r o b o t ) 以某种策略自动地在访问w e b 站点，提取站点上的网 页，并根据网页中的链接进一步提取其它网页，或转移到其它站点上。r o b o t 搜集的 网页被加入到搜索引擎的数据库中，供用户查询使用。 该类搜索引擎的优点是信息量大、更新及时、毋需人工干预，缺点是返回信息过 多，有很多无关信息，用户必须从结果中进行筛选。这类搜索引擎的代表是：a l t a v i s t a ， n o r t h e m l i g h t ，e x c i t e ，i n f o s e e k ，g o o g l e 国内代表为：天网、悠游、百度等。 3 ) 元搜索引攀 也叫做m u l t i p l es e a r c he n g i n e ，这类搜索引擎的特点是没有存放网页的数据库， 而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果经过处理后返回给用 户。服务方式为面向网页的全文检索。严格意义上来讲，元搜索引擎只能算是一种用 户代理，而不是真正的搜索引擎。 这类搜索引擎的优点是返回结果的信息量更大、更全，缺点是不能够充分使用所 使用搜索引擎的功能，用户需要做更多的筛选。这类搜索引擎的代表是w e b c r a w l e r ， i n f o m a r k e t 等。 1 1 4 搜索引擎的性能指标 搜索引擎的主要指标有响应时间、召回率、准确率、相关度等。这些指标决定搜 索引擎的技术指标【1 0 1 。搜索引擎的技术指标决定了搜索引擎的评价指标。好的搜索引 擎应该是具有较快的反应速度和高召回率、准确率的，当然这些都需要搜索引擎技术 指标来保障。 1 ) 召回率：一次搜索结果中符合用户要求的数目与其查询相关信息的总数之比 2 ) 准确率：一次搜索结果中符合用户要求的数目与该次搜索结果总数之比 3 ) 相关度：用户查询与搜索结果之间相似度的一种度量 精确度：对搜索结果的排序分级能力和对垃圾网页的抗干扰能力 召回率衡量的是检索系统( 搜索引擎) 的查全率；精度衡量的是检索系统( 搜索 引擎) 的查准率。对于一个检索系统来讲，召回率和精度不可能两全其美：召回率高 时，精度低，精度高时，召回率低。对于搜索引擎系统来讲，因为没有一个搜索引擎 系统能够搜集到所有的w e b 网页，所以召回率很难计算。目前的搜索引擎系统都非 常关心精度】。 4 长存i t 业人学硕士学位论文 1 2 主题搜索引擎 1 2 1 传统搜索引擎面临的挑战 搜索引擎历经三代发展，极大地改善了人们在网络上进行信息搜索的手段，但搜 索引擎在信息收录完备性、查全率、查准率、检索功能和用户检索界面等方面还存在 许多不足之处 1 2 】目前，搜索引擎面对的挑战主要表现在以下几个方面。 1 ) 索引擎的覆盖范围降低：搜索引擎越来越难为人们提供一个涵盖范围广泛的 信息了。最大的搜索引擎如g o o g l e ， a l t av i s t a 等也只可以索引静态网页的 小部分。 2 ) w e b 是一个动态增长的信息源， 随时会发生各种变化，搜索引擎己不能及 时反映这种变化，大量返回结果为无效的( 链接己经不存在) 或过时的( 同一个 链接己经被替换成另一个文件) 。同时，网上大量的镜像站点和简单重复拷贝 都使搜索引擎返回大量无用信息。 3 1 搜索引擎面对的用户是形形色色的，这些用户的信息需求、知识背景、兴趣 各不相同。用户检索到的结果与所需要的信息相比，感兴趣的信息常常淹没 在众多的无用信息当中。 随着i n t e m e t 信息急剧膨胀以及信息多元化的发展，目前人们对搜索引擎的首要 关注点已经从如何找到更多的信息转向如何快速找到准确、有用的信息。查准率已经 成为搜索引擎的首要目标。这种情况下，主题搜索引擎应运而生并成为发展趋势。 1 2 2 主题搜索引擎的概念及特点 所谓主题型搜索引擎就是以构筑某一专题或学科领域的i n t e m e t 网络信息资源库 为目标，智能地在互联网上搜集符合这一专题或学科需要的信息资源，能够为包括学 科信息门户、专业信息机构、特定行业领域、公司信息中心、行业专家等等在内的信 息用户，提供整套的网络信息资源解决方案【2 】。 主题搜索引擎具备有效的信息采集策略，索引更新周期大大缩短，通常能在1 2 天内提供更新的网上专业领域信息查询，甚至能根据优先划分等策略在数小时内更新 查询信息。主题搜索引擎面向某一特定的专业领域，保证了对该领域信息的完全收录 与及时更新。它能够为具有相同兴趣点的用户及时集中提供各种专业资源查询，避免 了搜索时强大的“噪音”提高了查询效率，相比较通用搜索引擎的海量信息无序化，主 题搜索引擎则显得更加专注、具体和深入。同时主题搜索引擎站点也提供了一个相互 交流、共享信息和资源、展望行业发展前景的平台。 长存工业人学硕十学位论文 1 2 3 主题搜索引擎支撑技术 1 h t t p 协议 h r r p 协议是建立在t c p i p 网络协议基础上的用于w w w 数据传输的标准协议。 通过h t p 协议，搜索引擎与w w w 服务器之间建立通信机制，向服务器提出对网页 各个特征提取的请求，并从服务器的应答中获得相应的数据。 2 c r a w l e r 技术 “网络爬虫”c r a w l e r 是一种自动运行的程序，其功能是搜索互联网上的网站和网 页，定期在互联网上漫游，通过网页间的链接顺序地搜索新的地址，当遇到新的网页 时就给该网页的某些字段或全部字段做索引并把它加入到搜索引擎的数据库中。由 此，搜索引擎的数据库得以定期的更新。 3 信息预处理技术 信息预处理技术包括信息格式的支持与转换以及信息过滤。搜索引擎应该具各信 息格式转换功能，以保证不同格式的数据均能在网络流通。同时，在互联网中存在有 大量的无用信息，一个好的搜索引擎应当能尽量减少垃圾站点的索引数量。 4 信息索引技术 信息索引就是创建文档信息的特征记录，以使用户能够快速的检索到所需要的信 息。建立索引主要涉及到以下问题：( 1 ) 信息词语切分和词语分析；( 2 ) 进行词性标注 及相关的自然语言处理；( 3 ) 建立检索项索引。 5 检索结果处理技术 搜索引擎一般应该按与查询的相关程度对检索结果进行排列，最相关的文档通常 排列在最前面。搜索引擎确定相关性的方法有概率方法、位置方法、摘要方法、分类 或聚类方法等。 此外，搜索引擎中还有自然语言理解技术、智能化、个性化的搜索引擎，x m l 可扩展标记语言技术的应用等等关键问题。 1 3 本文的工作及组织 1 3 1 本文的主要研究工作 本文首先系统介绍了搜索引擎发展的历史，从分析当前搜索引擎面临的问题入 手，提出了主题搜索引擎发展的必然性，重点探讨主题信息采集策略以及网页文本自 6 长春工业大学硕士学位论文 动分类的实现，并最终给出一种基于房地产主题的搜索引擎设计方案。 本文相关的研究和实现主要体现在以下几点： 1 ) 网络爬行器的优化改进：引入网页相关度的概念，通过对不同网页相关度的 权重计算改进网页爬行器搜索策略算法。 2 ) 文本自动分类：研究了支持向量机和朴素贝叶斯等算法，对比分析了朴素贝 叶斯算法两种模型间的实验效果。 3 ) 构建索引及搜索：研究并应用了a p a c h e 软件基金会的子项目l u c e n e 。实现 系统的索引和检索部分的功能。 4 ) 搜索结果聚类呈现：对于搜索引擎搜索到的结果，根据主题词典对主题相关 的分类结果进行聚类分析，使结果以多维的形式展现。 1 3 2 全文的组织结构 第1 章：介绍搜索引擎发展现状，概要提出主题搜索引擎使用主要的技术及系统 的整体设计思想； 第2 章：信息采集和信息抽取相关的概念以及运行机制； 第3 章w e b 挖掘技术在搜索引擎领域应用的相关技术； 第4 章主题搜索引擎架构的设计与实现，对主题信息采集、网页自动分类、搜 索及索引和结果聚类作了详细的阐述和研究； 第5 章对爬虫算法、文本分类及l u c e n e 应用的实验结果与分析； 第6 章本文主要研究工作、存在的不足及展望。 7 长春工业大学硕上学位论文 2 1 网页爬行器 2 1 1 网页爬行器的概念 第2 章信息采集与信息抽取 网页爬行器也称作网络蜘蛛，是用来在i n t e r n e t 上自动发现和搜集w e b 网页的 一个程序，它从一个起始u r l ( u n i f o r mr e s o u r c el o c a t o r ) 集合出发，沿着网页之间 的链接，按照定的搜索策略搜集相关网页，并把搜索到的网页交给网络搜索引擎 的其他执行单元进行网页解析、存储和索引等【1 3 】。 网页爬行器大体分为两种。第一种，称之为常规网页爬行器，只是简单地进行页 面寻找，搜索并获得你想要的页面内容。第二种，称之为特殊网页爬行器，只寻找页 面的特定部分。这种网页爬行器在某些特定场合很有用，例如只想获得某一个站点内 的新闻标题的情况。 目前，网页爬行器已被网络搜索引擎广泛使用( 如g o o g l e ，a l t a v i s t a ，i n f o s e e k ， e x c i t e ) ，它是网络搜索引擎系统中最重要的一个执行单元，它所搜集的网页质量和爬 行效率直接关系到一个网络搜索引擎所包含的网页质量。 ， 网页爬行器在爬行时将面对两个问题 1 4 1 6 1 ：一个是由于i n t e r a c t 上的信息量十分 巨大，一个网络搜索引擎不可能包含整个w e b 网页，当前世界上包含数据量最多的 网络搜索引擎g o o g l e 也只覆盖了整个w e b 的1 1 ；另一个是网络搜索引擎要对网页 爬行器爬行回来的网页进行处理和存储，受到硬件资源的限制，它所能存储的网页是 有限的。这就要求网页爬行器在w e b 空间中在有效的时间内尽可能搜索到高质量的 网页。因此，为了保证被搜索信息的质量，网页爬行器要具有理想的搜索策略和很高 的搜索效率。 2 1 2 网页爬行器爬行策略 网页爬行器首先从一个由起始的u r l 构成的队列出发，这些u r l 被称为种子， 它把队列中的第1 个u r l 移出队列，然后取得该u r l 所对应的网页p o ，然后从网页 p 0 中提取它所包含的所有的u r l ，把这些u r l 按照某种策略加进网页爬行器需要爬 行的u r l 队列中，网页爬行器再从u r l 队列中取下一个需要爬行的u r l ，重复如上 所述过程，直到满足要求或u r l 队列为空i 。 我们可以把网页爬行器爬行过的每个网页看成有向图中的一个节点，网页之间的 链接看成是节点之间的有向边，则网页构成的有向图如图l 所示，网页爬行器在w e b 空间中爬行网页的过程就是对由网页构成的有向图的遍历。 8 长奋工业人学硕士学位论文 图2 - 1 网页构成的有向图 网页爬行器爬行网页的策略主要有两种，一种是深度优先搜索策略。另一种是 宽度优先搜索策略，如图2 2 所示。 照答，扼取黔 溉优馓， a b c , d , e * f - h ，6 。l 。e - “ 图2 - 2 深度优先和广度优先搜索策略 9 长存工业人学硕士学位论文 广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的 一个链接网页，继续抓取在此网页中链接的所有网页。这是最常用的方式，因为这个 方法可以让网络蜘蛛并行处理，提高其抓取速度。 深度优先是指网络蜘蛛会从起始页开始，一个个链接逐个跟踪下去，处理完这条 线路之后再转入下一个起始页，继续跟踪链接。这个方法有个优点是网络蜘蛛在设计 的时候比较容易。 m a r en a j o r k 等人的研究证明，爬行器采用广度优先搜索策略爬行的网页质量要 比采用深度优先搜索策略的要好 1 7 1 9 1 ，因此，大多数网页爬行器采用宽度优先搜索策 略或者是对这种策略的某些改进。 其基本算法描述如下： b r e a d t h - f w s tc r a w l i n ga l g o r i t h m0 把种子u r l s 加入到爬行器待爬行的队列u r l s q u e u e 中。 w h i l e ( 当队列u r l $ q u e u e 不为空和没有满足某种终止条件) 从队列u r l s q u e u e 中移出一个u r l 。 取得u r l 所对应的网页p 。 对网页p 进行存储、索引并解析，取得网页p 包含的所有o r e s 。 把取得的u r l s 加入到队列u r l s q u e u e 中。 ) 此处的“没有满足某种终止条件”是指爬行器的爬行过程到目前为止没有满足系 统的要求，如爬行的网页数量不够。 2 1 3 网络蜘蛛评价方法 评价通用的爬行器的指标主要在于程序的运行效率方面，例如在多长时间爬行了 多少网页；以及对空间的占用等等。这些都已经有了很成熟的评价体系。一般是通过 机器来判断页面与主题的相关程度或是通过评价使用爬行器的应用系统来评价爬行 器。总体来说，评价爬行器系统的过程有两个方面：判断单个页面的相关程度( p a g e i m p o r t a n c e ) 和总结所有的爬行到的页面的相关程度( s u m m a r y a n a l y s i s ) 1 2 0 j 。 1 判断单个页面的相关性的方法： 1 1 网页中的k e y w o r d s ：如果一页中包含查找项中一个或所有关键词，该页 被认为是相关的。关键词在该页中出现的频率也可以考虑在内。 1 0 k 存t 业大学硕士学位论文 2 ) 与查找项的相似性：短查找项或长的查找项描述同每个己访问过的网页的 相关性可被用于判断网页相关性的标准。 3 ) 与种子页的相关性：种子页可用于测量被爬行网页的相关性。也可以将多 个种子页合成当个文本，该文本与己爬行网页的相关度可用于判断该网页 的相关性。 4 ) 分类器得分：培训一个分类器来计算网页与所需信息的相关性。培训时， 使用种子页( 或预先指定的相关度) 作为正例子。培训过的分类器将为每个 已访问过的网页计算出的布尔或连续的相关性得分。 5 ) 使用检索系统排列：n 个不同的c r a w l e r s 从同一页开始访问，直到每个 c r a w l e r 访问了p 个网页。检索系统如s m a r t 针对初始查找项或描述将 n * p 个网页分等级，该等级就作为该页的相关性成绩。 6 ) 基于链接的计算方法：可以使用p a g e r a n k t m l 算法或h i t s 算法对每个被 爬行的网页进行评价。一个较简单的方法是根据一个己访问的网页的链入 链接个数( i n - l i n k s ) 来得出相关性。许多与基于链接的方法类似的方法使用 主题权重来评价网页的相关性。 2 综合的性能评价： 类似于信息检索( i n f o r m a t i o nr e t r i e v a l ) 中的精确率( p r e c i s i o n ) 和召回率( r e c a l l ) 的方法。精确率统计爬行到的页面中有多少比例的是与主题相关的；召回率统计w e b 上有多少比例的与主题相关的页面被找到了，以下就是几个类似精确度的测量方法： 1 ) 获取率；如果是布尔相关性成绩，可以显式地计算好网页以多少速度被找 到。如：在开始的5 0 0 个被爬行网页中，有5 0 个是相关的，则可以认为 获取率为1 0 2 ) 平均相关性：如果是更常见的获取率，即相关性得分是连续的，相关性得 分可以通过简单的c o s i n e 相关度或分类器计算出。这样的平均相关性可 以在整个爬行过程中计算( 前1 0 0 页，前2 0 0 页) 。 2 2 信息抽取技术 2 2 1 信息抽取的概念 g r i s h m 给信息抽取技术下了一个清晰的定义嘲：信息抽取( i n f o r m a t i o n e x t r a c t i o n ：i e ) 系统应该是由应用领域决定，而且在进行训练之后生成的一个项集。 长春工业大学硕i ：学位论文 信息抽取的目标是把文本里包含的信息进行结构化处理，变成表格一样的组织形 式。输入信息抽取系统的是原始文本，输出的是固定格式的信息点。信息点从各种各 样的文档中被抽取出来，然后以统一的形式集成在一起。这就是信息抽取的主要任务 田】。 2 2 2 信息抽取的评测标准 信息抽取技术的评测起先采用经典的信息检索( u 评价指标，即回召率( r e c a l l ) 和 查准率( p r e c i s i o n ) ，但稍稍改变了其定义。经修订后的评价指标可以反映i e 可能产生 的过度概括现象( o v e r - g e n e r a t i o n ) ，即数据在输入中不存在，但却可能被系统错误地产 生出来( p r o d u c e d ) 【2 4 】。 就信息抽取而言，回召率可粗略地被看成是测量被正确抽取的信息的比例 ( f r a c t i o n ) ，而抽准率用来测量抽出的信息中有多少是正确的。计算公式如下： p = 抽出的正确信息点数所有抽出的信息点数 r = 抽出的正确信息点数所有正确的信息点数 两者取值在0 和1 之间，通常存在反比的关系，即p 增大会导致r 减小，反之亦 然。 评价一个系统时，应同时考虑p 和r ，但同时要比较两个数值，毕竟不能做到一 目了然。许多人提出合并两个值的办法。其中包括f 值评价方法： f 。( , f 1 2 。+ 1 ) p r 嚣。尹+ 震 其中是一个预设值，决定对p 侧重还是对r 侧重。通常设定为1 。 这样用f 一个数值就可很看出系统的好坏。 2 2 3 信息抽取基本阶段 文献1 2 2 1 提供了信息抽取技术的一个概要，列出了信息抽取