（计算机应用技术专业论文）基于实例学习的搜索引擎结果优化系统设计与实现.pdf

摘要 摘要 搜索引擎是网络信息检索的主要工具，它的出现方便了人们对信息的查询， 但现有搜索引擎返回的结果太多，用户很难查找到真正想要的资料。此外，人 们通常无法用简单的几个词来描述自己的信息需求。对于一个查询词，搜索引 擎往往会返回成千上万的网页，这些结果是动态而简单的，但绝大部分对于某 个特定的用户而言都是不相关的。因此，用户必须通过浏览冗长的列表才能找 到自己需要的信息。于是，信息检索中出现了“信息过载”和“信息迷失”等 问题。如何提高搜索引擎的查准率是其亟待解决的问题，而如何推断用户的查 询目的从而实现智能化搜索是未来搜索引擎的发展方向。 此外，查询词也往往具有歧义，不同用户具有不同的背景、兴趣以及使用 目的。就目前而言，对于特定的关键词查询，无论任何人得到的结果都是一样 的。人们越来越希望得到的结果能够符合自己的意愿，目前出现了各种改进的 搜索引擎，基于用户个性词典的搜索引擎、基于聚类技术的搜索引擎、面向主 题的搜索引擎等等。在一定程度上起到一定的促进作用，究其原理，实际就是 基于某种技术对通用搜索引擎搜索结果的处理，其中包括对搜索结果的过滤。 聚类、分类等处理。 实例学习是机器学习中较为成熟的分支，其基本思想是从某一概念的己给 的i f 例集合和反例集合中归纳产生出描述所有正例并排除所有反例的一般规 则，因而也被称作概念获取。本文正是基于对用户行为的跟踪，把其访问网页 分为币例和反例，通过相关算法，得到描述用户查询目的规则，从而实现网页 的过滤技术，返回与用户查询目的相关的网页，去除无关网页。从而有效的提 高搜索引擎的查找精度，为用户提供高质量的、相关度较高的查询结果。 本文在分析了通用搜索引擎和个性化搜索引擎的基础上，针对目前搜索引 擎中的“信息过载”和“信息迷失”等问题，提出一种对搜索引擎进行改进的 策略，该策略基于对用户行为的跟踪，对网页返回目录中的摘要信息进行文本 挖掘，推断用户的搜索目的，对中文w e b 搜索结果进行优化。去除垃圾信息， 返回给用户一个比较满意的结果。最后初步实现了一个简单的搜索引擎优化系 统s e o ，系统经过测试取得良好的运行效果。 关键词： 搜索引擎；实例学习；扩张矩阵；i d 3 算法；向量空间模型 a b s t r a c t a b s t r a c t s e a r c he n g i n ei sm a i nt o o lf o rs e a r c h i n gi n f o r m a t i o no ni n t e m e t ，a n di tf a c i l i t a t e t h ep e o p l ei ni n f o r m a t i o nr e t r i e v a l ，b u t ，i ti sd i f f e r e n tf o ru s e r st of i n dw h a tt h e yr e a l l y w a n tw i t ht h ee x i s t i n gs e a r c he n g i n e ，c o n s i s t i n gi nt o om a n yr e c o r dt h es e a r c he n g i n e r e t u r n e d f u r t h e r m o r e ，u s e r sc a nn o td e s c r i b et h ei n f o r m a t i o nt h e yn e e ds i m p l yw i t h t h es e v e r a ls i m p l ew o r d s g i v eaq u e r y , t h es e a r c he n g i n eu s u a l l yr e t u m st h o u s a n d s u p o nt h o u s a n d so ft e x tr e s u l t s ，w h i c ha r ed y n a m i ca n db r i e f , t h em o s tp a r t so ft h e m a r ei r r e l e v a n tt os p e c i f i cu s e r , s ot h eu s e r sh a v et ob r o w s et h r o u g hal o n gl i s tt og e t w h a tt h e yw a n t a sar e s u l t ，t h eq u e s t i o n sl i k e ”i n f o r m a t i o no v e r l o a d ”a n d i n f o r m a t i o nl o s i n g ”a p p e a r e di ni n f o r m a t i o nr e t r i e v a l h o wt oi m p r o v et h es e a r c h e n g i n e sp r e c i s i o ni sap r i m a r yp r o b l e mi nd e v e l o p m e n to fs e a r c he n g i n e ，a n dh o wt o i n f e rt h eu s e r sq u e r yp u r p o s ei no r d e rt oa c h i e v et h ei n t e l l i g e n ts e a r c hi st h e d e v e l o p m e n td i r e c t i o no fs e a r c he n g i n ei nt h ef u t u r e b e s i d e sq u e r yw o r d st e n d sh a v ed i f f e r e n tm e a n i n ga n dd i f f e r e n tu s e r sh a v e v a r i o u sb a c k g r o u n d ，i n t e r e s t sa n du s a g ei n t e n t s a tp r e s e n t ，f o rt h es p e c i f i cq u e r y w o r d ，t h es e a r c he n g i n eg i v et h es a m er e s u l tl i s tb e t w e e nt h ed i f f e r e n tu s e r s w i t ht h e h o p i n gt h a tt h er e s u l t sc a n b ec o n s i s t e n tw i t ht h e i ro w nw i s h e s ，av a r i e t yo fi m p r o v e d s e a r c h e n g i n ea p p e a r , i n c l u d i n gs e a r c he n g i n eb a s e do nt h e u s e r sp e r s o n a l i t y d i c t i o n a r y , s e a r c he n g i n eb a s e do nc l u s t e r i n gt e c h n o l o g y , s u b j e c t - o r i e n t e ds e a r c h e n g i n e ，a n ds oo n t h e yp r o m o t et h ep r o g r e s si ns e a r c he n g i n et oac e r t a i ne x t e n t i n p r i n c i p l e s ，i tc a nb er e g a r da st h ep r o c e s so fr e s u l t sw i t ht h ea c t u a lt e c h n o l o g y , i n c l u d i n gf i l t e r i n go fr e s u l t s ，c l u s t e r i n g ，c l a s s i f i c a t i o n ，a n ds oo n c a s e b a s e dl e a r n i n gi st h em o r em a t u r eb r a n c h e s ，t h eb a s i ci d e ai st oo b t a i na g e n e r a lr o l et h a tc a nb eu s e dt oe x c l u d ee v e r yn e g a t i v ee x a m p l e ，a n dw h i c hi n c l u d e a l lt h ep o s i t i v ee x a m p l e s ，b ym e a n so fi n d u c t i o na n dc o n c l u s i o no ft h es e to fp o s i t i v e a n dn e g a t i v ee x a m p l e so fc o n c e p t i o ng i v e n ，w h i c hi sa l s ok n o w na st h ec o n c e p to f a c c e s s t h i sa r t i c l ei sb a s e do nt r a c ko fu s e r sb e h a v i o r , i td i v i d et h ew e bp a g ev i s i t e d i n t on e g a t i v ea n dp o s i t i v es e t ，g e tt h er u l et h a tr e p r e s e n tu s e r sp u r p o s et h r o u g ht h e a p p l i c a t i o no fc o r r e s p o n d i n ga r i t h m e t i c ，t h e r e b yr e a l i z et h ef i l t e ro fw e bp a g e ，a n dt h e i i a b s t r a c t r e s u l ti n c l u d et h em o s tr e l a t i v er e c o r da n de x c l u d ei r r e l a t i v er e c o r d ，e f f e c t i v e l y i m p r o v et h ea c c u r a c yo fs e a r c he n g i n e ，a n dp r o v i d eu s e r sw i t hh i g h q u a l i t y , h i g h c o r r e l a t i o nr e s u l t s b a s e do nt h ea n a l y s i so ft h eg e n e r a ls e a r c he n g i n ea n dp e r s o n a l i z e ds e a r c h e n g i n e ，t h i sa r t i c l ep r e s e n t sas t r a t e g yt oi m p r o v es e a r c he n g i n ei nm a n ya s p e c t ， w h i c hb a s e do nt r a c ku s e r sb e h a v i o ri nv i s i t i n gw e bp a g e ，m i n et h ei n f o r m a t i o no f s u m m a r yo fr e t u r n e dw e bp a g e ，a n dd e d u c et h ea i mo ft h eu s e r , i nt h ee n d ，o p t i m i z e t h es e a r c hr e s u l t i tc a nr e m o v eg a r b a g ei n f o r m a t i o ni ns e a r c hr e s u l t ，r e t u mt ot h eu s e r am o r e s a t i s f a c t o r yr e s u l t s f i n a l l y , i nt h i s a r t i c l er e a l i z et h es e a r c he n g i n e o p t i m i z a t i o ns y s t e m ( s e o ) ，t h es y s t e mp e r f o r m e dw e l li nt e s t k e y w o r d ：s e a r c he n g i n e ，c a s e b a s e dl e a m i n g ，i d 3 t r e e ，e x t e n s i o nm a t r i x ， v e c t o rs p a c em o d e l i i i 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：高锄签字日期： 。孑年2 月鲴 学位论文版权使用授权书 本学位论文作者完全了解南昌大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权南昌大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：童1 磊 导师签名： 签字f 二1 期： 汐孑年，凋爿扫签字日期： 衫年，明彤日l ， 第一章绪论 第一章绪论 1 1 引言 随着计算机与网络的迅速发展，当今社会已经走向信息化，人们越来越习 惯于通过网络这个丰富而实用的平台来获取自己需要的信息。然而面对浩如烟 海的信息，如何才能方便迅速的获取有效信息，成为人们关注的问题。搜索引 擎的出现极大的缓解了这一矛盾。w e b s i d e s t o r y 公司最近的一项调查显示，使 用搜索引擎找到网站的网民比例从2 0 0 2 年前的8 提高到了2 3 ，w e b 搜索引 擎逐步成为用户搜寻相关信息的重要工具。目前搜索引擎种类繁多，比较熟悉 的如g o o g l e 、y a h o o 和百度等等。虽然在一定程度上满足了人们的要求，但是返 回的大量冗余信息也考验着人们的耐性。怎样使搜索引擎理解用户的查询目的， 使搜索返回的信息更准确，而不包含太多的无用信息，解决问题的根本办法在 于自然语言的理解技术，即机器对自然语言的理解。但是，就目前的研究来看， 自然语言理解还处于研究的初级阶段，让机器真正理解文档的内容还有很长的 一段路要走。目前，数据挖掘技术的发展则为我们提供了一条途径。虽然不能 从根本上解决问题，但其扎实的理论基础，以及在金融、证券、商贸、保险， 特别是在文本分类方面的应用，震撼着我们的神经。研究学者们提出的w e b 内 容挖掘、w e b 日志挖掘、w e b 链接挖掘等。在w e b 内容挖掘分析中，分类与聚 类等技术被用来加强w e b 文档的管理。在w e b 结构挖掘方面，w e b 页面间链 接结构被用来计算页面的“权威性 ；在w e b 日志挖掘分析中，根据用户历史 访问行为的信息来决定页面的相关性，都取得了良好的效果。但是以往的研究 往往侧重于对整个w e b 文档集的分析，忽视了对单个查询的w e b 检索结果的 分析或者说忽视了w e b 检索结果的信息与整个文档集的信息协同分析。 通常检索的结果具有以下的特征： 数据量大但很少相关：结果中通常包含几千到几百万的文档，让用户淹 没在纷繁复杂的信息中。 结果简单：搜索引擎往往只显示与查询相关的标题和文本片断 ( s n i p p e t s ) ，风格单调，交互性差。 动态性强：由于w e b 的飞速增长，查询返回结果往往更新较快，动态 第一章绪论 性很强。 多主题性：各种主题的网页混杂在同一张列表中，区分它们则成为了用 户的负担。 另一方面，用户对w e b 检索的需求主要表现在： 实时性：用户的期望值是1 2 秒，最多十几秒就想看到排在最前面的几 十条信息，对检索结果的优化也应达到比较高的时间效率。 个性化：用户具有不同的背景、兴趣及使用目的，追踪用户的使用习惯 对检索结果的优化是至关重要的。 对于目前搜索引擎存在的主要问题，其主要研究包括： ( 1 ) 搜索引擎的个性化研究，国内外存在着许多个性化搜索系统，这些系统 根所采用的过滤技术可分为基于规则的系统、基于内容过滤的系统和协作过滤 系统。基于规则的系统如i b m 的w e b s p h e r e ( w w w i b m c o m w e b s p h e r e ) 从用户的 静态特征和动态属性出发来提供个性化服务；基于内容过滤的系统如中国科学 院计算技术研究所软件室开发的天网个性化信息过滤系统 ( h t t p ：m a z e t i a n w a n g c o m ：) ；采用关键词过滤和相似度过滤相结合的策略向用 户主动推送个性化信息；协作过滤系统如c a r n e g i em e l l o n 大学开发的 w e b w a t c h e r ，则利用用户之间的相似性来过滤信息。 ( 2 ) 对搜索引擎返回结果的聚类技术，即利用文本聚类技术对搜索返回的结 果进行聚类，把结果按照内容分成几个类别，贴上类标签，以方便用户的搜索。 其中比较著名如：v i v i s i m o 、e l u s t y 。 ( 3 ) 面向主题的中文搜索引擎【1 1 ，所谓面向主题的搜索引擎就是以构筑某一 专题或领域的i n t e r a c t 网络信息资源库为目标，智能地在互联网上搜集符合这一 专题或领域需要的信息资源，能够为包括学科信息门户、专业信息机构、特定 行业领域、公司信息中心、行业专家等在内的信息用户，提供整套的网络信息 资源解决方案。 1 2 本文研究的内容 本文分析了机器学习、数据挖掘、人工智能方面的相关基础知识，针对目 前搜索引擎中的“信息过载”和“信息迷失”等问题，提出一种对搜索引擎进 行改进的策略，该策略基于对用户行为的跟踪，对网页返回目录中的摘要信息 2 第一章绪论 进行文本挖掘，推断用户的搜索目的，对中文w e b 搜索结果进行优化。去除垃 圾信息。返回给用户一个比较满意的结果。最后对该系统进行设计和实现，该 系统经过测试取得良好的运行效果。 1 3 本论文的内容安排 论文分为六章： 第一章为绪论，主要包括本文的研究背景，当前对搜索引擎进行改进的方 法及本论文研究的内容和论文的内容安排。 第二章为搜索引擎概述，主要论述了搜索引擎的实现原理与技术、现代搜 索引擎中存在的问题及未来搜索引擎的发展方向。 第三章为相关知识和技术，论述了系统设计和实现过程中所涉及到的知识 和技术，首先介绍了人类行为学的相关理论，论证了人的搜索行为是一种有目 的，有意识的行为，从而为我们策略的提出奠定了理论技术，然后介绍文本挖 掘中的相关技术。 第四章为实例学习相关技术，主要介绍了实例学习中的两种算法，即基于 扩张距阵的覆盖算法和以决策树为知识表示的i d 3 算法及其改进算法。同时通 过实例验证了实例学习应用于搜索引擎的可行性。 第五章为系统的分析与设计，对其作了总体设计和详细设计，并对其中具 体的细节做了详细的说明，分析了百度搜索引擎的u r l 格式、编码和搜索返回 结果的组成，设计一个通过访问百度并获取搜索结果的模块。在信息获取模块 利用多线程和同步机制保证信息获取的时效性。在词频统计阶段引入了哈希表， 降低了算法的时间复杂度等。 第六章是系统的实现，主要介绍了实现平台，实现中相应类的结果和部分 代码，最后介绍了系统的评价以及待改进的地方。 3 第二_ ：章搜索引擎概述 第二章搜索引擎概述 2 1 搜索引擎的发展 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网 爆炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针。这时，为 满足大众信息检索需求的专业搜索网站便应运而生了。 现代意义上的搜索引擎的祖先，是1 9 9 0 年由蒙特利尔大学学生a l a ne m t a g e 发明的a r c h i e 。虽然当时w o r l dw i d ew e b 还未出现，但网络中文件传输还是相 当频繁的，而且由于大量的文件散布在各个分散的f t p 主机中，查询起来非常 不便，因此a l a ne m t a g e 想到了开发一个可以以文件名查找文件的系统，于是便 有了a r c h i e 。a r c h i e 工作原理与现在的搜索引擎已经很接近，它依靠脚本程序自 动搜索网上的文件，然后对有关信息进行索引，供使用者以一定的表达式查询。 由于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 年开发了另一个与之非常相似的搜索工具，不过此时的搜索工具除 了索引文件外，已能检索网页。 当时，“机器人”一词在编程者中十分流行。电脑“机器人”( c o m p u t e rr o b o t ) 是指某个能以人类无法达到的速度不问断地执行某项任务的软件程序。由于专 门用于检索信息的“机器人”程序象蜘蛛一样在网络间爬来爬去，因此，搜索引擎 的“机器人”程序就被称为“蜘蛛”程序。 世界上第一个用于监测互联网发展规模的“机器人”程序是m a t t h e wg r a y 开 发的w o r l dw i d ew e bw a n d e r e r 。刚开始它只用来统计互联网上的服务器数量， 后来则发展为能够检索网站域名。与w a n d e r e r 相对应，m a r t i nk o s t e r 于1 9 9 3 年 1 0 月创建了a l l w e b ，它是a r c h i e 的h t t p 版本。a l i w e b 不使用“机器人”程 序，而是靠网站主动提交信息来建立自己的链接索引，类似于现在我们熟知的 y 撕o o 。 随着互联网的迅速发展，使得检索所有新出现的网页变得越来越困难，因 此，在m a t t h e wg r a y 的w a n d e r e r 基础上，一些编程者将传统的“蜘蛛”程序工作 原理作了些改进。其设想是，既然所有网页都可能有连向其他网站的链接，那 么从跟踪一个网站的链接开始，就有可能检索整个互联网。到1 9 9 3 年底，一些 4 第二章搜索引擎概述 基于此原理的搜索引擎开始纷纷涌现，其中以j u m p s t a t i o n 、t h ew o r l dw i d ew e b w o r m ( g o t o 的前身，也就是今天o v e r t u r e ) ，和r e p o s i t o r y - b a s e ds o f t w a r e e n g i n e e r i n g ( r b s e ) s p i d e r 最负盛名。 然而j u m p s t a t i o n 和o v e r t r u e 只是以搜索工具在数据库中找到匹配信息的先 后次序排列搜索结果，因此毫无信息关联度可言。而r b s e 是第一个在搜索结 果排列中引入关键字串匹配程度概念的引擎。 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。当时m i c h a e lm a u l d i n 将 j o h nl e a v i t t 的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的l y c o s 。同 年4 月，斯坦福( s t a n f o r d ) 大学的两名博士生，d a v i df i l o 和美籍华人杨致远( g e r r y y a n g ) 共同创办了超级目录索引y a h o o ，并成功地使搜索引擎的概念深入人心。 从此搜索引擎进入了高速发展时期。目前，互联网上有名的搜索引擎已达数百 家，其检索的信息量也与从前不可同日而语。比如最近风头正劲的g o o g l e ，其 数据库中存放的网页己达4 0 亿之巨1 2 2 搜索引擎的相关分类 搜索引擎按其工作方式主要可分为三种【2 】【3 】，分别是全文搜索引擎( f u l lt e x t s e a r c he n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和元搜索引擎 ( m e t as e a r c he n g i n e ) 。 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎【4 】，国外具代表性的有g o o g l e 、 f a s a 1 1 t h e w | e b 、a l t a v i s t a 、i n k t o m i 、t e o m a 、w i s e n u t 等，国内著名的有百度 ( b a i d u ) 。它们都是通过从互联网上提取的各个网站的信息，然后存储在相应的 数据库中，建立索引库，检索与用户查询条件匹配的相关记录，然后按一定的 排列顺序将结果返回给用户，因此他们是真正的搜索引擎。 从搜索结果来源的角度，全文搜索引擎又可细分为两种，一种是拥有自己 的检索程序( i n d e x e r ) ，俗称“蜘蛛”( s p i d e r ) 程序或“机器人”( r o b o t ) 程序， “机器人”程序是基于人工智能技术的发展而出现的一种网络爬虫，它代替手工 去搜索、加工、整理信息，其原理就是”机器人“程序以某种策略自动的在互 联网中搜集和发现信息，由索引器对搜索返回的网页建立索引，由检索器根据 用户的查询输入检索索引库，并将查询结果返还给用户。上面提到的都属于这 5 第二：章搜索，j l 擎概述 种，另一种则是租用其他引擎的数据库，并按自定的格式排列搜索结果，如l y c o s 引擎。此类搜索引擎的优点是信息量大，更新及时，不需要人工干预，缺点是 返回信息过多，包含大量的无关信息，用户必须筛选。 目录式搜索引擎 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅 仅是按目录分类的网站链接列表而己。其以人工方式或半自动方式搜集信息， 由编辑员查看信息之后，人工的形成摘要信息，并将信息置于事先确定的分类 框架中。信息大多数面向网站，提供目录浏览服务和直接检索服务。目录索引 中最具代表性的莫过于大名鼎鼎的y a h o o 雅虎。其他著名的还有o p e nd i r e c t o r y p r o j e c t ( d m o z ) 、l o o k s m a r t 、a b o u t 等。国内的搜狐、新浪、网易搜索也都属 于这一类。该类搜索引擎由于加入了人的智能，所以信息准确，导航质量高， 缺点是需要人工介入，维护量大，信息量少，信息更新不及时。 元搜索引擎( m e t a s e a r c he n g i n e ) 元搜索引擎的特点是本身没有存放网页信息的数据库，当用户进行查询时， 它把用户的查询请求转化为其搜索引擎能够接受的命令格式，并行的在其他多 个引擎上进行搜索，并将搜索引擎返回的结果经过处理后返回给用户。著名的 元搜索引擎有i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等，中文元搜索引擎中具代表性的 有搜星搜索引擎。在搜索结果排列方面，有的直接按来源引擎排列搜索结果， 如d o g p i l e ，有的则按自定的规则将结果重新排列组合，如v i v i s i m o 。这类搜索 引擎的优点是返回结果的信息量更大更全，缺点是不能够充分使用所使用搜索 引擎的功能，用户需要做更多的筛选。 2 3 搜索引擎基本原理与技术 搜索引擎的实现原理【5 1 ，可以看作四步：1 ) 从互联网抓取网页，2 ) 建立索 引数据库，3 ) 在索引库里中搜索，4 ) 对搜索结果进行处理和排序。 ( 1 ) 从互联网上抓取网页。利用能够从互联网上自动搜集网页的网络蜘蛛 ( s p i d e r ) ，自动爬行互联网，并沿着任意网页的u r l 爬到其他网页，重复这一 过程，并不断的分析u r l ，把爬过的网页搜集到数据库中。 ( 2 ) 建立索引数据库。由索引系统程序对搜集到的网页进行分析，提取相 关网页信息，根据一定的相关度算法进行大量复杂计算，得到( 每一个网页针 6 第二章搜索引擎概述 对页面内容中及超链接中每一个关键词的相关度) 网页索引( 正排或倒排) 。然 后利用这些相关信息建立网页索引数据库。 ( 3 ) 在索引数据库里搜索。用户输入关键词搜索后，分析检索请求，由检 索系统程序查询索引数据库找到所有符合该查询的所有相关网页。 ( 4 ) 对检索结果进行处理排序。所有相关网页针对该关键词的相关度信息 在索引库中都有记录，只需综合相关度信息和网页级别形成相关度数值，然后 按照相关度大小进行排序，最后有页面生成系统将搜索结果的链接地址和网页 摘要等内容组合起来返回给用户。 其主要组成部分如图2 1 图2 1 搜索引擎的工作原理 2 4 性能指标 可以将w e b 信息的搜索看作一个信息检索问题，即在由w e b 网页组成的文 档库中检索出与用户查询相关的文档。所以可以用衡量传统信息检索系统的性 能参数查全率( r e c a l l ) 和查准率( p r e c i s i o n ) 衡量一个搜索引擎的性能。我们将采用 这些评估方式对s e o 进行评估，下面对传统信息系统所需要的相关度进行介绍。 令数据集r 为w e b 资源中所有与用户输入的查询词相关的w e b 文档集合， 数据集d 为通过搜索引擎检索后返回的所用文档集合，如图2 2 所示。 准确率( p r e c i s i o n ) ：返回的相关文档数与返回文档之比。用于评价搜索返 回结果的精确度即返回结果是否都是相关的。 7 第一：章搜索引擎概述 p m 劬刀= 皆 召回率( r e c a l l ) ：返回的相关文档数与相关文档数之比。 擎返回结果的覆盖率即是否将所有相关结果都能找到。 m 训= 皆 ( 2 1 ) 用户评价搜索弓 ( 2 2 ) 图2 2 准确率和召回率 对于一个检索系统来讲，查全率和查准率不可能两全其美：查全率高时， 查准率低；查准率高时，查全率低。对于搜索引擎系统来讲，因为没有一个搜 索引擎系统能够搜集到所有的w e b 网页，所以查全率很难计算。目前的搜索引 擎系统都非常关心查准率。 2 5 现代搜索引擎中存在的问题 杜亚军等人曾在2 0 0 4 年对g o o g l e 中文、百度、天网三大中文搜索引擎智能 性问题的判断进行测试【6 j ，测试中定义了三个指标：( 1 ) 用户不能准确地用关键词 或关键词串来忠实地表达所真正需要检索内容的检索，例如用户想查询“数理 逻辑 误输为“数力逻辑”。检索结果集与用户真正表达的意义匹配程度，称之 为“容错性”。( 2 ) 在人类的自然语言中，随着时间、地域或领域的改变，同一概 念可以用不同的语言表现形式来表达，检索结果集与本概念的书面用语表达藕 8 第二章搜索引擎概述 合的程度，称之为“适语性”。例如：当一个用户需要检索“计算机”这一关键词， 由于其习惯地输入“电脑”，或“电老虎”，检索结果与使用“计算机”这一概 念检索结果耦合的程度。( 3 ) 不同的用户由于不同专业、生活环境对同一关键词 的检索，其要求检索出不同的信息，称之为“个性化”。例如计算机工程应用人 员与计算机理论研究人员都检索计算机教学，他们对检索的内容就有不同的要 求。其测试结果见图2 3 。实验表明基于关键词的搜索引擎在容错性、适语性、 个人化等的智能能力较差，三个搜索引擎在适语性、个性化上都没处理，只有 百度对误输入有判别。对现代搜索引擎的研究测试。发现现代搜索引擎的主要 问题体现在以下几个方面： ( 1 ) 没有真正的解决相关性。真正的相关性是指搜索词和页面的相关程度， 而不仅是网页中出现搜索词，有些网页中虽然没有出现搜索词，但内容和搜索 词十分相关，搜索引擎就无法搜索到这些网页。真正的相关性判断方法应该是 增加语义理解，得出搜素词和网页的相关程度。但语义的理解有待于自然语言 理解技术的发展，现在的自然语言理解技术还处于发展的初级阶段。所以真正 的语义理解还有相当长的路要走。 ( 2 ) 搜素结果的单一化，任何人搜索同一个词的结果都是一样的，各类用 户别无选择，网页搜索的个性化还有待提高。 ( 3 ) 动态网页搜索的困难。由于网络上更多的资源和有用的资料以数据库 的形式存在，而搜索引擎的蜘蛛在爬行这些动态网站的过程中很容易陷入死循 环。 ( 4 ) 搜索引擎中对多媒体( 图象和声音) 的搜索技术还仅停留于对这些文档 中文本识别的搜索，对文档的内容和情节还不能搜索。 ( 5 ) 对搜索质量的好坏没有一个统一的评价标准和搜索技术的好坏没有一 个通用的检验规范。 ( 6 ) 现有的搜索引擎在信息获取方式上，不是实时的，而是按照一定周期 从i n t e m e t 网上抓取网页。i n t e m e t 网上的巨大的信息量，现有的计算机网络速度， 要想让搜索引擎既要在很短的时间内遍历每一个网页，又要在很短的时间内向 用户响应其查询结果，显然不可能的。 9 第二章搜索引擎概述 甩户 g o o g l e 中文 百度搜索 天网搜索 查询词 n s 。nsns 数理逻辚 6 1 2 0 0 i 29 0 4 00 1 4 51 8 7 30 1 2 2 容错性致力逻辑 6 4 9 0 0o i 89 0 4 00 1 4 50o 误输入无相应闻用户是否在询无相应 的判别的处理 数理逻辑的提示 的处理 计算机 1 7 5 0 0 0 0o 0 611 8 0 0 0 0 00 0 0 l 9 6 80 3 1 7 适语性 电脑 2 1 0 0 0 0 00 0 921 8 0 0 0 0 0 0 0 0 l1 7 30 0 4 8 电老虎 2 4 6 0o 。1 66 2 9 00 t 8 6oo 汁笄桃应用 9 7 5 0 0 00 1 83 6 9 0 0 00 0 0 130 1 2 2 个性化计算机理论 3 7 7 0 0 00 1 94 3 5 0o 0 9 9l i o 1 2 1 计算机教学 5 6 5 0 0 00 3 22 1 5 0 0 00 0 0 160 0 9 9 ；查询时问( s e c o n d ) ，n 查询到的网页数；”( 实验时间2 0 0 3 3 1 9 ：1 0 ：4 0 】 图2 3 关键词搜索引擎智能测试结果表 2 6 未来搜素引擎的发展方向 搜素引擎已成为一个新的研究、开发领域，引起了世界各国计算机科学界 和信息产业界的高度关注，目前的研究、开发十分活跃，并出现了许多值得注 意的动向。其中主要是把机器学习、a g e n t 、自动推理、软计算、网格计算等方 法应用于计算机网中人类的智能和智能行为获取、加工、检索信息的理论与技 术和方法。 ( 1 ) 智能化的搜索引擎。它是搜索引擎的发展方向。它利用智能代理技术 对用户的查询、意图、兴趣方面进行推理，自动进行信息搜集过滤，自动的将 用户感兴趣的，对用户相关的信息提交给用户。 ( 2 ) 实现交叉语言的检索。对多种语言的数据库进行交叉语言信息检索。 返回能够回答用户问题的所用语言的文档。该技术目前还处于初步研发阶段， 是搜索引擎的发展方向。 ( 3 ) 多媒体搜索引擎。由于未来的互联网是多媒体数据网络。开发出可查 询图像、声音、图片和电影的搜索引擎是一个新的方向。 ( 4 ) 专业化搜索引擎。是为了专门收录某一行业、某一主题或某一地区的 信息而建立的，具有针对性强，实用性强的特点，如商务查询、企业查询、人 名查询、专业信息查询等等。 1 0 第三章相关知识和技术 第三章相关知识和技术 3 1 行为科学相关理论1 7 1 1 8 i 对人类行为这个问题的研究，是一个相当复杂而又漫长的过程，简要来说 人类行为的研究方向可以分为两部分：一、是生物学、心理学等学科着重探讨 人类的动物刺激性反应行为；二、是社会学所研究的人类行为是与他人和社会 有关的社会性行为，韦伯称之为“社会行动”( s o c i a la c t i o n ) 。 我们提出的搜索引擎优化系统( s e o ) 是部分上“结合了生物学、心理学方面 深讨人类的动物刺激性反映”，是基于用户行为的搜索引擎的优化系统。 3 1 1 人类行为的概念和种类 行为是人类日常生活所表现的一切动作。德国心理学家克特勒温【1 1 】，将 行为定义为个体与环境交互作用的结果，引入了“个体”这个变量。他提出人 的行为的基本原理可表达为b = f ( p ，e ) 式中： b 表示行为； p 表示个人的内在心理因素； e 表示环境的外界环境的影响( 自然、社会) ； 上式表示行为( b ) 是个人( p ) 与环境( e ) 交互作用所发生的函数或结果，这里的 变量“个人 和“环境”不是相互独立的，而是相互关联的两个变量。 从心理学的角度出发，人的行为起源于脑神经的相互作用，从而形成精神 状态，也就是所谓意识。由意识表现于动作时，便形成了行为，而意识本身则 成为一种内在行为。综合行为学家与心理学家研究的成果，人类行为特征至少 有以下列几方面： ( 1 ) 自发的行为：指人类的行为是自动自发的而不是被动的。外力可能影响 他的行为，但无法引发其行为，外在的权力、命令无法使其产生真正的效忠行 为。例如：人类因为饥饿而寻找食物充饥的行为，这个行为完全是自发的，外 力可能一时影响或阻碍这个行为，但是无法使“觅食行为 停止和变更。 ( 2 ) 有原因的行为：指任何一种行为的产生都是有其起因的。遗传与环境可 能是影响行为的因素，同时外在条件亦可能影响内在的动机。例如：人类受周 第三章相关知识和技术 围环境刺激所激发的行为，气候环境完全能对人类行为产生影响。环境温度高 低，直接影响人类寻求适应环境的行为( 环境温度高，人类会自觉的脱去多余衣 服，或下意识煽动周围气流从而促进气流流动，使自身得到“凉快”的满足感) 。 ( 3 ) 有目的的行为：指人类的行为不是盲目的，它不但有起因而且是有目标 的。有时候在第三者看来毫不合理的行为，对他本人来说却是合乎目标的。例 如：户检索信息的行为，用户在使用搜索引擎检索信息时，会自觉或不自觉的 为自己的用行为确定一个“目标”或确定一个“目的”。当用户通过一定的检索 动作，达到了自己即定的“目标”或“目的”后，人类得到了满足并结束检索 行为。 ( 4 ) 持久性的行为：指行为指向目标，目标没有达成之前，行为是不会终止 的。也许他会改变行为的方式，或由外显行为转为潜在行为，但还是继续不断 地向目标进行的。例如；人类在幼儿时期为自己的人生规划一个“理想”或“目 标”，人类为了达成这一“目标”往往会为之“奋斗”终生，这就是一种比较典 型的持久性行为。 ( 5 ) 可改变的行为：指人类为了谋求目标的达成，不但常变换其手段，而且 其行为是可以经过学习或训练而改变的。这与其他受本能支配的动物行为不同， 它是具有可塑性的。例如：人类之间的战争行为，人类在战争中学习“战争”， 通过学习和训练不断的改变行为的手段和方法，这与人类本能支配的动物行为 不同，它具有可塑性。 人的行为的基本单元是动作。所有的行为都是由一连串的动作所组成的。 搜索引擎优化系统就是要了解和分析用户的行为，从而预测用户搜索过程中的 动作，最终实现用户“查询精确相关 ，最大限度提高用户检索效率。 3 1 2 最小努力原则1 9 l “最小努力原则”是美国哈佛大学教授齐夫提出的，人们力图把他们可能 做出的平均工作消耗最小比，即人类行为建立在最小努力原则的基础上。这一 原则在人类检索信息的行为上体现的尤为突出：人类检索信息行为的触发和停 止，都是由精力的损耗和所得到的收益之比来决定的。用户在使用搜索引擎时， 如果觉得使用该搜索引擎检索信息要比不得到信息更耗费精力，那么这个搜索 引擎就不会被用户所使用，即用户在使用搜索引擎检索时，代价太大就不会使 用该搜索引擎。所以我们在设计本系统的过程中，对“用户行为信息”的收集 1 2 第二章相关知识和技术 是一种“隐式”，是在用户没有觉察的情况下完成的，在这种情况下最大限度的 降低了用户检索的代价，使用户能够花费相对小的代价，达到检索目的，使用 户得到满足。 3 2 实例学习 学习是人类获得知识的根本途径，机器学习是使任何计算机具有智能的主 要手段，实例学习是机器学习中较为成熟的分支。示例学习的基本思想是从某 一概念的已给的正例集合和反例集合中归纳产生出描述所有正例并排除所有反 例的一般规则，因而也被称作概念获取。 例如：教给一个程序“狗 的概念，提供程序各种动物和各种其他物体， 说明每个动物的特点，并说明他们是不是狗。这些是关于“狗”的正例和反例。 程序由此推出根据物体特征识别狗的规则。 在理论研究方面，一些示例学习算法的复杂性得到了分析和证明，例如， 洪家荣证明了示例学习中的一些问题是n p 难题【l 叭，并且提出了示例学习的扩张