（控制理论与控制工程专业论文）智能搜索引擎理论与应用研究.pdf

摘要 随着i n t e r n e t 的广泛应用，w e b 得到了迅猛的发展，w e b 上的信息呈指数 级增长，因此，如何对这种海量w e b 信息进行自动处理成为非常重要的研究课题。 传统搜索引擎搜索的内容繁杂，导致查询结果中存在大量无关信息，降低了查询 精度。一种新的研究趋势是结合领域知识和智能技术研究搜索引擎，即基于领域 的智能搜索引擎( d o m a i n b a s e di n t e l l i g e n ts e a r c he n g i n e ) 。智能搜索引擎 采用机器学习的方法研究文本信息的自动搜集、抽取与分类等处理过程，由此可 以减少大量人力资源的需求，并提高信息处理的效率和精度。本文深入研究了智 能搜索引擎中所使用的理论、算法与实现技术，采用巩固学习、隐马尔科夫模型 ( h 埘) 、朴素贝叶斯分类模型等机器学习方法在网络蜘蛛、信息抽取、文本预处 理和信息检索等方面提出了若干新的算法，并建立了仿真平台和实验原型系统。 理论分析和实验结果表明，这些算法具有较好的性能。 网络蜘蛛是智能搜索引擎中首先需要解决的问题。本文利用w e b 网页分布 群聚性的特点，结合巩固学习方法，提出了种新的启发式搜索算法。算法根据 网页与主题的相关程度将网页分为与主题相关的网页集群与过渡型的网页集群， 利用模拟退火的算法进行评估。在与主题相关的网页集群中进行搜索时，使用立 即回报加速挖掘的进度；在过渡型的网页集群中使用未来回报拓宽探测的范围以 加快定位过程。针对四所大学计算机系网站搜索的实验表明，算法具有较高的搜 索效率。 针对w e b 上的各种网页信息，如何有效地抽取出论文标题、作者姓名、摘 要等相关内容以方便查询，是智能搜索引擎的主要任务之一。目前基于隐马尔科 夫( h m m ) 信息抽取模型一般以单词作为基本抽取单位，考虑到文本排版格式、 分隔符等信息的存在，文本实际上可以看作是由一些文本分块序列组成，同一分 块内的所有单词只可能属于同一个状态，而不同分块可以属于一个或多个状态。 结合这种分块的思想，本文提出了基于文本分块的h m m 信息抽取算法。实验结 果表明，这种方法比基于h m m 模型的信息抽取算法具有更好的性能。 文本信息处理通常采用向量空间模型表示文本信息，需要对单词进行预处 理以降低单词数量。结合对单词过滤与特征选取两类常用预处理方法的研究，本 文提出了基于最小类差异的特征过滤算法。算法通过分析文本特征的分布特性以 及区分类的情况，将文本特征划分为单类特征、多类特征与一般特征等三种类型， 按照特征在各类之间的分布差异，将类分布差异较小的特征所对应的一般特征进 行过滤，实验结果表明这种算法有效地过滤了大量的无关信息和弱相关信息，提 高了分类算法的精度。 信息检索是智能搜索引擎中的查询机制。本文结合w e b 信息表示的特点， 提出了一种n 层向量空间模型。模型将整个w e b 信息按照结构的不同划分为多 个层次，根据各层次的不同作用分别进行相似度计算。理论分析与实验结果表明， 这种模型比传统向量空间模型具有更好的查全率与查准率。 基于超链接的信息检索方法是一种新型的信息检索机制。本文针对基于超 链接的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 ) 算法，结合n 层向量空间模型的思 想，提出了一种基于锚点信息的超链接检索排序算法。算法利用n 层向量空间 模型进行相似度计算，结合网页的链接信息进行排序。与h i t s 算法、t f i d f 算 法等信息检索方法的实验结果比较，新算法在信息检索的查全率与查准率方面取 得了更好的效果。 针对w e b 信息的动态性将导致搜索引擎所采集的信息失效，而般的策略 采用固定周期的信息更新算法，本文提出了一种基于最高响应比算法的w w w 索引 信息库更新方法，利用索引信息的访问情况以及网页的更新频度计算网页的更新 周期，按照不同更新周期的情况进行信息的有效性检查，不仅减轻了系统信息维 护的工作量，而且保证了信息的有效性。 最后，本文提出了一个比较完整的搜索引擎设计模型，结合本文在网络蜘 蛛、信息抽取、文本分类、信息检索等方面的研究内容，在w i n d o w s 操作系统 平台上实现了一个简单的原型系统。 关键词：搜索引擎，文本分类，信息抽取，巩固学习，隐马尔科夫模型， 朴素贝叶斯分类算法 儿 a b s t r a c t w i t ht h e d e v e l o p m e n t o ft h ei n t e r n e t ，w e bi n f o r m a t i o n i n c r e a s e s e x p o n e n t i a l l y h o wt oa u t o m a t i c a l l yd e a lw i t ht h eh u g e i n f o r m a t i o nh a s b e c o m eav e r yi m p o r t a n tr e s e a r c ht o p i c d u et ot h ei n f o r m a t i o nr e t u r n e d b yt r a d i t i o n a ls e a r c he n g i n ev a r y i n gb r o a d l y ，t h er e s u l to fu s e r sq u e r y m a yi n c l u d eam a s so fi r r e l e v a n ti n f o r m a t i o n w h i c h1 e a d st od e g r a d a t i o n o ft h ep r e c i s i o n i no r d e rt oi m p r o v et h eq u e r yp r e c i s i o n ，d o m a i n b a s e d i n t e l l i g e n ts e a r c he n g i n ec o m b i n e dw i t ht h et o p i c d r i v e na n di n t e l l i g e n t t e c h n o l o g yh a sc o m et ob ean e wr e s e a r c ht r e n d i tu s e sm a c h i n el e a r n i n g t og u i d ed y n a m i cc o l l e c t i o no fw e bi n f o r m a t i o n ，a u t o m a t i ci n f o r m a t i o n e x t r a c t i o n ，a u t o m a t i c t e x t c l a s s i f i c a t i o n ，a n d e t c t h e r e f o r et h e e f f i c i e n c ya n dt h ep r e c i s i o no fi n f o r m a t i o np r o c e s s i o nc a ng e ti m p r o v e d i nt h i sd i s s e r t a t i o n ，f o l l o w i n gt h er e s e a r c ho ft h e o r y ，a l g o r i t h ma n d t e c h n o l o g yu s e di ni n t e l l i g e n t s e a r c h e n g i n e ，s o m e n e wa l g o r i t h ma r e p r e s e n t e d i n s p i d e r ， i n f o r m a t i o n e x t r a c t i o n ，t e x tp r e p r o c e s s i n g ， jn f o r m a t i o nr e t r i e v a l ，a n de t c f u r t h e r m o r e ，as i m u l a t i o np l a t f o r ma n d ap r o t o t y p es y s t e ma r es e tu p t h et h e o r ya n a l y s i sa n de x p e r i m e n t a l r e s u l t ss h o wt h eb e t t e rp e r f o r m a n c e h o wt og e ti n f o r m a t i o nf r o mt h ei n t e r n e ti st h ep r i m ep r o b l e mt ob e s o l v e di n i n t e l l i g e n t s e a r c h e n g i n e b a s e do n t h e s u r v e y o fc u r r e n t i n t e l l i g e n t s e a r c h e n g i n e ， c o m b i n e dw i t hr e i n f o r c e m e n t l e a r n i n g t e c h n i q u e ，t h ec h a r a c t e r i s t i co fs i m i l a rw e bp a g e s d i s t r i b u t i o ni su s e d t op r e s e n tah e u r i s t i cs e a r c ha l g o r i t h mb a s e do ns i m u l a t e da n n e a l i n g a c c o r d i n gt ot h er e l e v a n c yb e t w e e nw e bp a g e sa n dt o p i c ，t h i sa l g o r i t h m f i r s td i v i d e st h ew e b p a g e s i n t ot w o t y p e s ：t o p i c r e l e v a n t w e bp a g e 1 1 1 c l u s t e ra n dt r a n s i t i o n a lw e bp a g ec l u s t e r ，w h i c hd e t e r m i n e db ys i m u l a t e d a n n e a l i n ga l g o r i t h m d u r i n gs e a r c h i n g t h e t o p i c r e l e v a n t w e b p a g e s ， i m m e d i a t er e w a r di su s e da se v a l u a t i o nc r i t e r i o nf o re x p l o i t a t i o nt o s p e e d u pm i n i n gi n f o r m a t i o n w h i l es e a r c h i n gt h et r a n s i t i o n a lw e bp a g e s ， f u t u r er e w a r di su s e da se v a l u a t i o nc r i t e r i o nf o re x p l o r a t i o nt os p e e d u p l o c a t i n g w i t ht h ee x p e r i m e n to nf o u ru n i v e r s i t yw e bs i t e s ，t h er e s u l t s s h o wh i g h e rs e a r c he f f i c i e n c y h o wt o e f f i c i e n t l y e x t r a c tr e l e v a n ti n f o r m a t i o ns u c ha s t i t l e ， a u t h o r n a m e ，a b s t r a c ta n dr e f e r e n c ef r o mt h ew e bp a g e sf o rq u e r yi so n e o fm a i nt a s k so f i n t e l l i g e n t s e a r c h e n g i n e r e c e n t r e s e a r c hh a s d e m o n s t r a t e dt h e s t r o n gp e r f o r m a n c eo fh i d d e nm a r k o vm o d e la p p l i e d i n i n f o r m a t i o ne x t r a c t i o n h o w e v e r ，t h ei n f o r m a t i o ne x t r a c t i o nb a s e do n h i d d e nm a r k o vm o d e lg e n e r a l l yt a k e sat o k e na sab a s i ce x t r a c t i o nu n i t ， a n dt h ei n f o r m a t i o no ff o r m a ta n dl i s ts e p a r a t o r si sn o tt a k e ni n t oa c c o u n t b a s e do nt h en a t u r a ls t r u c t u r eo ft e x t ，ab l o c k b a s e dh i d d e nm a r k o vm o d e l i sp r o v i d e d t h ee x p e r i m e n tu s i n gt h i sn e wa l g o r i t h ma l s os h o w st h eb e t t e r p e r f o r m a n c et h a nt h eo r i g i n a l o n e t h et e x ti n f o r m a t i o ni s a l w a y sd e p i c t e du s i n g v e c t o r s p a c em o d e l t h e r e f o r e ，t h et e x ts h o u l db ep r e p r o c e s s e dt od e g r a d et h en u m b e ro fw o r d s w i t ht h er e s e a r c ho ft w oc o m m o nm e t h o d s ：f e a t u r ef i l t e r i n ga n df e a t u r e s e l e c t i o n ，an e wa l g o r i t h mb a s e do nm i n i m u mc l a s sd i f f e r e n c ei sp r o p o s e d u n d e rt h eo b s e r v a t i o no fd i s t r i b u t i o na n dd e v o t i o no f e a c hf e a t u r ei ne a c h c l a s s ，t h ef e a t u r ec a nb ed i v i d e di n t ot h r e et y p e s ：s i n g l e c l a s sf e a t u r e ， m u l t i c l a s sf e a t u r ea n d g e n e r a lf e a t u r e a c c o r d i n g t ot h ed i f f e r e n t d i s t r i b u t i o ni ne a c hc l a s s ，t h eg e n e r a lf e a t u r ew i t hl e s sd i f f e r e n c ea m o n g c l a s s e sw i l lb ef i i t e r e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r e c i s i o n o ft e x tc l a s s i f i c a t i o ni s i m p r o v e d d u et oe f f i c i e n tf i i t r a t i o no f s u b s t a n t i v ei r r e l e v a n to rw e a kf e a t u r e s i n f o r m a t i o nr e t r i e v a li st h eq u e r yi n t e r f a c eo fi n t e l l i g e n ts e a r c h e n g i n e u s i n gt h ec h a r a c t e ro fd e n o t a t i o no fw e bi n f o r m a t i o n ，a nn - l e v e l v e c t o rs p a c em o d e li s p r o p o s e d i tp a r t i t i o n s ad o c u m e n ti n t ont e x t p a r a g r a p h sa c c o r d i n g t ot h e i rp o s i t i o n ，t h e nt h e i rs i m i l a r i t i e sa r e c a l c u l a t e d r e s p e c t i v e l y b o t h t h e t h e o r ya n a l y s i s a n d e x p e r i m e n t a l r e s u l t ss h o wt h a ti th a sh i g h e rr e c a l la n dp r e c i s i o nu s i n gt h en e wm o d e l t h a nu s i n gt r a d i t i o n a lv e c t o rs p a c em o d e l d u et ot h eh u g ew e bi n f o r m a t i o na n d1 i m i t e ds t o r a g e ，i ti si m p o s s i b l e t od o w n l o a da llt h ew e bp a g e st or e t r i e v et h ew e bp a g e s t h e r e f o r e ，t h e h y p e r t e x t b a s e di n f o r m a t i o nr e t r i e v a lu s i n gt h ea n c h o rt e x to fw e bp a g e a p p e a r s a i m e d t ot h eh y p e r l i n k i n d u c e dt o p i cs e a r c ha n dc o m b i n e dw i t h t h en - l e v e lv e c t o r s p a c em o d e l ，a n e w h y p e r l i n k b a s e da l g o r i t h m i s p r o v i d e d i tc a l c u l a t e st h es i m i l a r i t yo fa n c h o rt e x tu s i n g n - l e v e lv e c t o r m o d e l c o m p a r e dw i t hh i t sa n dt f i d fi nt h ee x p e r i m e n t ，t h en e wa l g o r i t h m g e t st h eb e t t e rp e r f o r m a n c ei nr e c a l la n dp r e c i s i o n v o l a t i l ew e bp a g ew i l ll e a dt oi n v a l i di n d e xf o ri n f o r m a t i o nr e t r i e v a l t h ec o l m n o f ls c h e m er e f r e s h e st h ei n d i c e s p e r i o d i c a l l y w i t hs e t t l e d i n t e r v a l w i t hav i e wt ot h ec h a r a c t e r i s t i co fw w wp a g e sa n de f f e c t i v e n e s s o fi n f o r m a t i o nd a t a b a s e ，an e wi n d e x e dd a t a b a s er e f r e s h m e n ta l g o r i t h mi s p r o v i d e db a s e do nt h eh i g h e s tr e s p o n d i n gr a t i o i tc o m p u t e st h er e f r e s h c y c l eo fw e bp a g e sa c c o r d i n gt ot h ef r e q u e n c yt h ep a g ec h a n g e da n dt h e d e g r e e t h e p a g e sa c c e s s e d a c c o r d i n g t ot h er e f r e s h m e n tc y c l e ，t h e v a l i d i t yo fw e bp a g e si sc h e c k e d ，w h i c hw i l ln o to n l yr e l i e v et h eh e a v y m a n a g e m e n t o fi n d e x e di n f o r m a t i o nd a t a b a s e ，b u ta l s oi n s u r et h e i n f o r m a t i o nv a li d i t y f i n a l l y ，ar e l a t i v e l yi n t e g r a t ef r a m e w o r k o f i n t e l l i g e n t s e a r c h v e n g i n ei sp r e s e n t e d w i t ht h er e s e a r c ho ns p i d e r ，i n f o r m a t i o ne x t r a c t i o n t e x tc l a s s i f i c a t i o na n di n f o r m a t i o nr e t r i e v a l 。ap r o t o t y p es y s t e mo f d o m a i n b a s e di n t e l l i g e n ts e a r c h e n g i n e i s i m p l e m e n t e d i nw i n d o w s e n v i r o n m e n t k e yw o r d s ： s e a r c he n g i n e ，t e x tc l a s s i f i c a t i o n ，i n f o r m a t i o ne x t r a c t i o n r e i n f o r c e m e n t l e a r n i n g ，h i d d e nm a r k o vm o d e l ，n a i v eb a y e s i a n 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 游、睫 日期：哆年月，d 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 ， 不保密日。 ( 请在以上相应方框内打“”) 作者签名：j 啦兹午 聊签诽 7 7 纠乙 日期：如3 年月1 0 日 日期：，z 彬年6 月，日 第一章绪言 近十年来随著i n t e m e t 的发鼹，w e b 也得到了迅猛的发展。但传统搜索弓l 擎 由于搜索的内容比较繁杂，导致用户查询的结果存在大量的无关信息，降低了查 询的精度。基于用户查询的对象一般局限予某一特定的领域，因此出现了基于领 域的智能搜索引擎。由于智能搜索引擎在搜索过程中得到较高的精确度，因此基 于领域的智能搜索引擎得到了较广泛的应用，并且成为w e b 应用发展的新课题。 本文从机器学习的观点出发，系统地研究智能搜索引擎所涉及到的网络蜘蛛、文 本自动分类、信息抽取、信息检索、信息更新等问题。 1 1 研究背景 目前，w e b 网页信息已经拥有上1 0 0 亿的静态网页l l 】。而对于鼙前通用的接 索引擎，即使是所访问的网页数目已超过3 0 亿的g o o g l e ，也仅占整个静态网页 空闻的3 0 4 0 2 l 。与此同时，涉及w e b 后端数据库的动态网页估计为整个静态 w e b 空间的5 0 0 倍【3 】。而这些通用的搜索引擎所表现的数据信息覆盖领域广、信 息量大、数据不稳定、冗余度大等特性，导致用户查询的精度非常低。因此如何 提高用户套询结果的精度已成为w e b 应用得到进一步发展两必须要解决的一个 非常关键的问题。在这一闯题的求解过程中，由予用户查询信息一般局限于某一 特定领域，从而导致了基于领域的智能搜索引擎( d o m a i n b a s e di n t e l l i g e n t s e a r c he n g i n e ，d b i s e ) 的发展。 d b i s e 搜索引擎般从指定的与搜索内容相关的站点开始进行搜索，利用具 有一定搜索中心或特定主题的网络蜘蛛 a , s l 查找相关的网页，结合相关的机器学 习算法如支持向量机算法【6 】( s u p p o r t e dv e c t o rm a c h i n e ，s v m ) 、最大期望值算 法【7 】( e x p e c t a t i o nm a x i m u m ，e m ) 、巩固学习 8 1 ( r e i n f o r c e m e n tl e a r n i n g ，r l ) 等进行训练，过滤搏大量不相关的网页信息，从中挑选出最优路径进行搜索。由 于d b i s e 搜索引擎能够提供与搜索主题更相关的站点信息以及更好的搜索内容， 因此，可以使得针对相应领域进行查询的用户能够检索到与用户给定查询条件相 关的结果，从而使得信息检索精度得至0 较好的结果。正因为如此，基于领域的智 能搜索引擎发展非常迅速，已出现了许多基于各种领域的智能搜索引擎，如 c i t e s e e r 、c o r a 、m l 等搜索引擎主要提供计算机科学论文方面的搜索：d e a d l i n e r 提供会议信息1 9 j 的搜索；h p s e a r c h 搜索个人网站，n e w s t r a c k e r 、m o r e o v e r 搜 索最新新闻信息，f 1 i p d o g 搜索招聘信息等。随着这些网站的成功开发与研究的 更深入，d b i s e 已越来越受到重视。但由于智能搜索引擎技术在实现过程中没有 考虑到w e b 应用本身所存在的特点，从而导致智能搜索引擎的结果受到影响。因 此如何利用w e b 本身所特有的性质，结合现有机器学习的方法，更加有效地实现 搜索引擎的相关技术是目前搜索引擎得到进一步发展所迫切需要解决的问题。 1 2 研究现状 由于w e b 技术的飞速发展，网页呈指数级的增长。用户在海量的信息资源 中难以找到所需要的信息，为了帮助用户能够快速地定位到其所需要的网页信息 上，搜索引擎应运而生，并且随着用户使用搜索引擎工具对检索结果的精度与查 全率的要求，搜索引擎技术得到较充足的发展，并已成为人们查找信息必不可少 的工具。 搜索引擎一般包含网络蜘蛛与信息检索两个主要部分。网络蜘蛛主要完成 用户检索过程中所需要的原始数据信息的搜集工作，而信息检索是搜索引擎提供 给用户进行信息查询的接口，是搜索引擎技术必须实现的查询机制。复杂的搜索 引擎可能还包括信息抽取、信息分类与信息更新等其他部分。由于各网站基本上 都能够提供搜索引擎技术。由于搜索引擎搜集的信息量比较大，对系统的软硬件 环境的要求以及实现上存在相应的难度等方面的要求从而出现另一种新的简单 的搜索引擎技术元搜索引擎，这种搜索引擎只提供信息检索机制，而信息的 搜集工作则主要依赖于其他搜索引擎，因此，元搜索引擎由于减少了信息的搜集 与存储工作，从而使得元搜索引擎对系统的要求降低，另外，元搜索引擎通过将 用户的查询条件发送给其他搜索引擎，因此查询结果建立在其他搜索引擎的查询 基础上，查询的精度与查找的范围要比单个搜索引擎的查询精度与查找范围要 好。 尽管元搜索引擎要比传统搜索引擎的性能要好，但由于搜索引擎是建立在 传统搜索引擎的基础上，因此，传统搜索引擎所存在的查询精度低的问题在元搜 索引擎中同样出现。由于用户查询信息一般都是基于某个特定知识领域进行信息 检索，因此，在局限于某一特定知识领域或某一特定主题的情况下进行原始信息 的收集，可以大大提高信息检索的精确度，从而出现了基于领域的搜索引擎技术， 并且这种搜索引擎由于在特定主题的限定下进行数据的搜集与检索，要求搜索引 擎具有智能化的特性，能够识别所搜索的网页是否与其主题相关，并且在搜索的 过程中，能够沿着与主题最相关的链接进行搜索。从而使得这种基于领域的搜索 引攀具有相当的智能化的技术，形成基于领域的智能搜索引擎。 由于网络蜘蛛主要完成的工作是自动搜索w e b 空间中的相关网页信息，为 用户检索过程中提供所必须的原始数据信息。因此网络蜘蛛所搜索内容的好坏将 会影响到整个搜索引擎的性能，同时网络蜘蛛也是整个搜索引擎起作用的最关键 的一部分，因此许多研究者都在致力于网络蜘蛛的技术研究中，如文献 8 ，9 】。 基于领域的智能搜索引擎在搜集原始信息的过程中，一方面，要求能够对 相应的网页进行判别，因此出现了许多分类算法应用于网页判别过程中。如文献 1 0 简单通过将所有网页信息划分成计算机与非计算机两大类，利用分类技术判 别待识别的网页属于哪一类来进行。另一方面，要求网络蜘蛛在搜索的过程中能 够沿着与主题最相关的链接进行搜索，尽可能地避免搜索与主题不相关的网页或 搜索与主题相背离的网页信息，从而出现了许多种网络蜘蛛的搜索方法，如深度 优先算法【4 1 、i n f o s p i d e r 算法【4 l 、鲨鱼搜索算法【1 “、p a g e r a n k 4 1 等。其中巩固学 习因为可以使得网络蜘蛛具备一种学习机制能够避免在搜索过程中搜索与主题 无关的网页信息从而大量地应用在基于领域的智能搜索引擎网络蜘蛛中u “。 由于w e b 网页信息组织的非结构化或半结构化，导致信息难以检索。因此 基于w e b 网页的编制语言h t m l 脚本对各使用标志的内在含义，如 标志所 表示的信息比较重要，而 所表示的信息是一般的信息等，按照标志所起到 的作用程度不一样来抽取出网页中的重要信息，如文献 1 3 、1 4 采用斯坦福大学 提出的对象交换模型( o b j e c te x c h a n g e m o d e l ，o e m ) i l5 】将页面中各标志所对应的 数据部分抽取出来，从而形成相应的w e b 信息模型。但由于w e b 网页的结构只 是一种信息的表现形式，简单地使用这些标志进行信息的抽取所得到的精度受到 相当程度的怀疑。而只有直接从网页的内容中抽取出相应的信息才能真正抽取出 所需要的文本信息，因此出现了基于内容的信息抽取，其中一般的方式采用隐马 尔科夫模型( h m m ) 进行6 ，”j 。 文本分类主要利用其内部知识库按照预定义的分类样本库中的类别层次， 对待分类的文档进行分类。文本分类在对网页判别是否与主题相关的过程中、复 杂搜索引擎对文本的分类处理过程中以及基于目录式的搜索引擎的过程中具有 非常重要的作用。目前常用的分类算法有n a i v eb a y e s ( n b ) 1 8 , 1 9 , 2 0 , 2 1 、s u p p o s e d v e c t o r m a c h i n e ( s v m ) 2 2 1 等。这些方法需要大量的训练样本才能得到较好的分 类模型，但由于网页的数量过于庞大，大量的训练样本难以提供：e x p e c t e d m a x i m u m ( e m ) 算法等研究如何从少量样本中进行训练得到较好的分类模型， 因此这种分类算法在电子文本的分类过程中得到了较好的应用【2 3 1 。 在进行文本分类的过程中，文本分类算法一般都将文本转化为以单词为基 本元素的向量模式再进行分类判定，而在文本信息的向量表示过程中因所涉及到 的单词比较多，导致描述文本信息的向量结构非常庞大，不利于文本分类的计算。 因此在文本分类处理前必须进行分类预处理，过滤掉大量的无关特征、弱相关的 特征，或利用特征选取算法只保留有限的单词特征，以降低文本向量空间的维数 大小，加快分类算法的计算过程。常用的特征过滤算法有：禁用词表方法、稀少 特征过滤方法等。特征选取算法有：信息增益、互信息量等。 信息检索主要是根据用户的查询条件，完成对记录信息的查找过程，并将 查询结果以一定的方式呈现给用户，以方便用户对相关信息进行浏览或进行进一 步的查询。信息检索主要有两种方式：基于目录结构的检索和基于查询串的文档 检索。基于目录结构的检索方式是在用户查询时根据已分好的类别直接进行查 找，因此在这种查询模式中，用户不需要输入任何信息，直接访问该网页就可以， 但这种情况根本无法满足用户搜索具有某一特定信息的文档，而基于查询串的文 档检索通过用户所给定的查询条件进行检索。因为这种方式能够比较准确地查找 出用户所需要的文本信息，因此基于查询串的文档信息检索得到了较为广泛的应 用。 1 3 论文贡献 本文在研究传统搜索引擎技术实现的同时，结合现有的基于领域的智能搜索 引擎技术，对智能搜索引擎进行了深入系统的研究。在此基础上对智能搜索引擎 中的网络蜘蛛、信息抽取、信息预处理、文本分类、信息检索以及信息更新提出 了新的思考和见解。论文主要贡献如下： 一网络蜘蛛是智能搜索引擎中最重要的部分。在对几种大型的网络蜘蛛的 分析的基础上，利用w e b 网页分布的群聚性的特点，结合巩固学习方法， 提出了一种新的启发式搜索算法。算法根据网页与主题的相关程度将搜索 过程中所访问的网页分为与主题相关的网页集群与过渡型的网页集，利用 基于模拟退火的算法进行评估。这样在与主题相关的网页集群中进行搜索 时，使用立即回报加速发掘的进度；在过渡型的网页集中搜索时使用未来 回报进行探测。针对四所大学计算机系网站搜索的实验结果表明，算法具 有很高的搜索效率。 二目前基于h m m 信息抽取模型一般以单词作为基本抽取单位，考虑到文 4 本排版格式、分隔符等信息的存在，文本实际上可以看作是由一些文本分 块序列组成的。同一分块内的所有单词只可能属于同一个状态，而不同分 块可以属于不同的状态。在结合分块的思想上提出了基于文本分块的 h m m 信息抽取算法。实验结果表明，这种方法比基于h m m 模型的信息 抽取算法具有更好的性能。 三由于文本分类是处理大量电子文本，并将这些电子文本进行自动归类的 主要手段，而在对文本信息进行处理的过程中，首先需要对无关的特征信 息进行处理，以便降低文本的向量空间大小，加速分类算法的处理过程， 因此，在介绍常用特征选取算法的同时，结合文本特征的在各类中的分布 特性，将特征划分为单类特征、多类特征与一般特征。基于一般特征对分 类处理过程所带来的负面影响，提出了一种基于最小类差异的特征过滤算 法，算法通过计算特征在各类中的作用程度，将类间差异最小的特征作为 一般特征进行过滤。结合多组数据集与多种分类算法的测试结果表明，这 种新算法由于有效地过滤了大量的无关信息和弱相关信息，使分类精度得 到比较大的提高。 四信息检索是关系到搜索引擎整体性能，在对信息检索的研究过程中结合 基于智能搜索引擎的特点，提出了基于n 层向量空间模型来表示文本信 息，通过理论分析与实验结果表明，利用这种模型较传统的向量空间模型 的表示方法具有更好的查全率与查率；对于基于超链接的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 ) 算法，结合n 层向量空间模型的思想 对h i t s 算法进行改进，从而得到性能更好的基于超链接的算法。 五由于w e b 网页的动态变化容易导致索引信息无效，因而降低搜索引擎的 整体性能。为了有效地保证索引信息的时效性，本文提出了一种基于最高 响应比的信息更新算法。算法根据索引信息的访问情况，以及网页的更新 频度计算网页的更新周期，按照更新周期的情况进行信息的有效性检查， 从而不仅减轻了系统信息维护的工作量，而且保证了信息的时效性。 六通过综合搜索引擎中的各种技术，提出了一个比较完整的搜索引擎设计 模型，结合本文在网络蜘蛛、信息抽取、文本分类、信息检索等方面的研 究内容，在w i n d o w s 操作系统平台上实现了一个简单的原型系统。 1 4 论文组织 本文其他章节内容的整体结构是： 第二章主要介绍了传统搜索引擎的一般设计框架以及搜索引擎技术实现中 的几个主要功能部件的作用。 第三章主要介绍了网络蜘蛛的作用以及目前流行的几种网络蜘蛛的实现技 术，介绍了巩固学习方法及其在网络蜘蛛中的应用，并着重介绍了使用模拟退火 的新的启发式搜索算法。 第四章主要介绍了基于文本分块的h m m 信息抽取算法。 第五章主要介绍了文本分类过程中常用的预处理算法，并重点介绍了最小 类差异预处理过滤算法以及相关的实验结果，减少无关信息和弱相关信息对分类 过程的影响。 第六章主要介绍了在文本分类过程中常用的文本分类算法以及对分类精度 的评价方法，并利用文本分类算法实现对垃圾邮件自动过滤的应用。 第七章主要介绍了信息检索技术、基于n 层向量空问模型以及基于超链接 的改进检索排序算法h a i t s ，并给出了相应的实验结果。 第八章分析了w w w 搜索引擎信息库中的信息更新过程中所存在的问题，介 绍了基于最高响应比算法的w w w 索引信息库更新方法。 第九章在前述内容的基础上，介绍了一个完整的搜索引擎模型的实现过程。 最后对论文的研究工作进行了总结，并对进一步的研究工作做了展望。 第二章搜索引擎结构 近十年来w e b 应用得到了迅猛的发展，为了方便用户能够快速地在w e b 信 息空间中查找到其需要的信息内容，涌现了大量的搜索引擎。目前，按照信息搜 集方法和服务提供方式的不同，可以将搜索引擎分为三大类：基于查询串方式的 搜索引擎、基于目录式搜索引擎以及元搜索引擎。本章主要介绍这三种类型的搜 索引擎，并介绍了目前的一些搜索引擎的整体结构。在此基础上，设计了一个比 较完整的系统框架，并介绍了各部分所完成的工作。 2 1 基于查询串的搜索引擎 基于查询串的搜索引擎通常是由网络蜘蛛( s p i d e r ) 以某种策略自动地在互 联网中搜集和发现信息，并将搜集到的信息建立索引，形成索引库。由检索器根 据用户的查询输入检索索引库，并将查询结果返回给用户。典型的搜索引擎有： a l t av i s t a 、e x c i t e 、n o r t h e r nl i g h t 、g o o g l e 等。 2 1 1a l t av is t a 搜索引擎结构 a l t av i s t a 搜索引擎结构图如图2 1 所示： 0 查询机制 a l t av i s t a 软件结构主要包括两个部分：第一部分是用户接口和查询机制， 主要实现用户所提交的查询条件在索引库中完成搜索，并将相关的检索结果反馈 给用户的过程，索引机制采用集中式的方式应答用户的请求；第二