（计算机应用技术专业论文）基于相关反馈的人机对话搜索引擎系统.pdf

大连理工大学硕士学位论文 摘要 互联网的迅速发展和广泛普及导致网上信息爆炸性增长，如何在庞大的互联网上获 得有价值的信息已成为用户日益关注的问题。搜索技术的出现为用户快速找到所需信息 提供了方便。搜索引擎是种用于帮助因特网用户查询信息的搜索工具，它以一定的策 略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检 索服务，从而起至信息导航的目的。随着搜索引擎技术不断向前发展，搜索引擎成为用 户用来检索网上信息的主要工具。 然而目前的搜索引擎仍然存在不少的局限性。比如查全率低；查准率低，搜索结果 与请求相差较大；各搜索引擎的语法不统一，用户难以掌握；检索策略简单，组合检索 能力差；缺乏专门面向某学科的专题性搜索引擎；搜索引擎的智能程度还很低等。因 此，搜索引擎一直在努力进行改进，搜索引擎技术正成为计算机工业界和学术界争相研 究、开发的对象。研究目的就是在不提高用户进行检索的难度和效率的情况下，尽量使 用户得到更有相关性、包含更多信息的网页。本文正是为了这一目的所做的研究。本文 设计并开发了个基于相关反馈的人机对话搜索引擎系统，以实现用户期望的个性化查 询，提高查询的精确度。利用用户认为符合检索目的和不符合检索目的的搜索结果作为 反馈信息，依据向量空间模型的原理对用户反馈的搜索结果进行分解计算，分别得出符 合用户查询要求和不符合用户查询要求的文本特征向量，根据候补网页与他们的相关程 度得到离用户查询要求更接近的候补网页，作为再搜索的结果提交给用户。这样不仅提 高了搜索引擎系统的准确率，也避免了用户以输入关键词的形式来进行信息反馈，从而 使得查询更加智能化和人性化。 关键词：搜索引擎；向量空间模型；相关度；反馈 大连理工大学硕士学位论文 am a n m a c h i n es e a r c he n g i n es y s t e mb a s e do nt h er e l e v a n c ef e e d b a c k a b s t r a c t r a p i dd e v e l o p m e n ta n dp o p u l a r i z i n go fi n t e r n e tc a u s e so n l i n ei n f o r m a t i o nt oi n c r e a s e f a s te x t e n s i v e l y h o wt oo b t a i nv a l u a b l ei n f o r m a t i o no nh u g ei m e r n e tb e c o m e st h eq u e s t i o n t h a tu s e r sp a yc l o s ea t t e n t i o nt od a yb yd a y t h et e c h n o l o g yo fs e a r c he n g i n e sa p p e a r a n c e h a sf o u n dn e c e s s a r yi n f o r m a t i o na n dp r o v i d e dc o n v e n i e n c ef a s tf o ru s e r s t h es e a r c he n g i n e i sak i n do fs e a r c ht o o lu s e df o rh e l p i n gt h ei n t e m e tu s e rt oi n q u i r ea b o u ti n f o r m a t i o n f o rt h e p u r p o s eo fi n f o r m a t i o nn a v i g a t i o n ，i tc o l l e c t sa n df i n d si n f o r m a t i o ni ni n t e m e tw i t hc e r t a i n t a c t i c s ，u n d e r s t a n d ，d r a w ，o r g a n i z ea n dd e a lw i t hi n f o r m a t i o n ，a n do f f e rs e r v i c eo fs e a r c h i n g f o ru s e r s a st h et e c h n o l o g yo ft h es e a r c he n g i n ei sb e i n gd e v e l o p e df o r w a r dc o n s t a n t l y ，t h e s e a r c he n g i n eb e c o m e st h eu s e rm a i nt o o lu s e df o rs e a r c h i n go n l i n ei n f o r m a t i o n b u tt h es e a r c he n g i n eh a sm u c hl i m i t a t i o n ，e g t h er a t eo fq u e r yo v e r a l li sl o w ；t h er a t e o fq u e r ya c c u r a t e l yi sl o w ；t h er e s u l tu s e r ss e a r c hf o ra n da s kf o rd i f f e r e n c e b i g g e r ；t h e g r a m m a ro fe v e r ys e a r c he n g i n ei sn o tu n i f i e da n du s e r sa r ed i f f i c u l tt om a s t e rt h e m ；l a c k i n g t h es p e c i a lt o p i cs e a r c he n g i n es p e c i a l l yf a c i n gac e r t a i nd i s c i p l i n e ；t h ei n t e l l e c t u a ld e g r e eo f t h es e a r c he n g i n ei sv e r yl o w s ot h es e a r c he n g i n ek e e p sm a k i n gg r e a te f f o r t st oi m p r o v e t h et e c h n o l o g yo ft h es e a r c he n g i n ei sb e c o m i n gt h et a r g e ti n d u s t r i a lc i r c l eo ft h ec o m p u t e r a n da c a d e m i aa r ef a l l i n go v e re a c ho t h e rt os t u d y ，d e v e l o p t h ep u r p o s eo fr e s e a r c hi st h a ti n c a s eo fn o ti m p r o v i n gt h ed e g r e eo fd i f f i c u l t ya n de f f i c i e n c yu s e r ss e a r c h ，t h es e a r c he n g i n e t r i e si t sb e s tt or e t r i e v ed o c u m e n t si n c l u d i n gm o r ei n f o r m a t i o nu s e r sw a n t t h ep a p e ri sj u s t f o rt h i sr e s e a r c hp u r p o s e t h ep a p e rd e s i g na n dd e v e l o pai n t e r a c t i v es e a r c he n g i n eb a s e do n v e c t o rs p a c em o d e lt or e a l i z eu s e r s i n d i v i d u a l i z e d i n q u i r ya n d 。i m p r o v et h ea c c u r a c yo f i n q u i r y i tu s e st h es e a r c hr e s u l t su s e r st h i n ka s ”i d e a l ”a n d ”u n s a t i s f a c t o r y ”t ob ef e e d b a c k i n f o r m a t i o n ，d r a w sm o d e lb a s e do nu s e r s ”i d e a l ”a n d u n s a t i s f a c t o r y ”v e c t o ri n f o r m a t i o n ， g e tt e x tv e c t o ro ft h ec h a r a c t e r i s t i cu s e r st h i n k ”i d e a l a n d u n s a t i s f a c t o r y ”，g e tp a g e sc l o s e t ou s e r s p u r p o s ea c c o r d i n gt ot h ed e p e n d e n c eb e t w e e nt h e ma n du s e r s p u r p o s e ，a n dr e f e r t h e mt ou s e r s i ti m p r o v e st h er a t eo fa c c u r a c yo ft h es e a r c he n g i n es y s t e m ，p r e v e n t su s e r s f r o ma s s i g n i n gt h eo r d e ri nt h ef o r mo fi n p u t t i n gt h ek e y w o r d ，a n dm a k ei n q u i r ym o r e i n t e l l i g e n ta n dh u m a n i z i n g k e yw o r d s ：s e a r c he n g i n e ；v e c t o rs p a c em o d e l ；r e l e v a n td e g r e e ；f e e d b a c k 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均己在论文中做了明确的说明并表示了谢意。 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：麴盘五 导师签名 固立煎 巫年三月二日 大连理l ：大学硕士学位论文 1 绪论 1 1 搜索引擎概念 随着网络与通信技术的迅速发展，w e b 信息爆炸性的增长，已经成为一个巨大的海 量信息空间。据发表在科学杂志1 9 9 9 年7 月的文章 w e b 信息的可访问性估计， 全球目前的网页超过8 亿，有效数据超过9 t ，并且仍以每4 个月翻一番的速度增长【1 1 。 随着因特网的迅猛发展和w e b 信息的增加，用户要在信息海洋量查找信息，就像大海捞 针一样。 如何快速、准确、方便的从如此庞大的信息库中获取自己需要的信息，是互联网用 户面临的一个重要问题。搜索引擎恰好能为甩户提供一种查找所需资源的服务，并且已 经成为互联网上仅次于电子邮件的第二大服务。 搜索引擎f s e a r c hz g i e ) 是随着w e b 信息的迅速增加，从1 9 9 5 年开始逐渐发展起 来的技术。按照定的策略，搜索引擎在互联网中搜集、发现信息，对信息进行理解、 提取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的。搜索引擎提供 的导航服务已经成为互联网上非常重要的网络服务，搜索引擎站点也被美誉为”网络门 户”。搜索引擎技术因而成为计算机工业界和学术界争相研究、开发的对象。目前，搜 索引擎技术成为仅次于门户的互联网第二大核心技术，要用到信息检索、人工智能、计 算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理 论和技术，所以具有综合性和挑战性【“。伴随互联网的普及和网上信息的爆炸式增长， 它越来越引起人们的重视。 今天搜索引擎的核心是网络导航服务，搜索引擎是一个网络门户，他们提供新闻， 在线图书馆，词典，以及其它网络资源，他们提供了不仅仅是网站搜索的服务，他们的 涉及面越来越广，也越来越有用。 目前比较典型的应用有如下方面： 政府和企业内部信息检索：很多企业现在发现原来的数据库检索系统己经不能适应 信息爆增的情况了，不但文件格式越来越多( w o r d ，h t m ，a c r o b a tp d f ，j s p ，l i p s ，e x c e l 等) ，随着事务越来越复杂，权利越来越下放，各部门都会有自己的信息存储方式和存 储地点，而且经常变化，要搜索的范围除了内部局域网还有通过互联网连接的异地分支 机构网络，这种情况可以由我们的专业搜索技术来解决。 网站内容比较搜索服务：比较竞争对手的价格，并定期或实时追踪这些数据的变化 情况。 张东方：基于相关反馈的人机对话搜索引擎系统 收集商业情报：收集竞争对手的公开会员信息，其它公开的商业情报，比如竞争对 手的广告投放情况等，监视竞争对手的所有公开动态情报。 采集商业数据：收集具有合法版权的商业数据。 复杂目录管理：帮助企业的数据库工程师编制复杂的产品目录，比如化工产品光种 类就1 7 0 多万种，这些目录之间还有错综复杂的关系，光录入这些数据就是一个很头痛 的问题。当企业本身也没有足够的原始资料而需要到互联网上获取资料的时候，我们的 搜索引擎就帮助企业很轻松很快速地完成任务，这一点对电子商务网站也十分有用。 专业搜索网站：大丽全的网站，比如y a h o o ，总是出现一大堆的查询结果，现在人 们更关心专业性、准确率、地域性等，人们需要专业的医学搜索引擎、化工搜索引擎、 体育搜索引擎、汽车搜索引擎等。 多媒体搜索服务：针对图象、声音等特殊搜索。 互联网网站监控：主要是政府、公安、新闻出版和安全部门等对互联网网站的监控。 网站内部信息搜索：对于那些租用虚拟主机，不想花费购买服务器和聘请专业技术 人员费用的中小企业和政府机构来说，仍然可以得到我们利用新技术提供的搜索服务， 完全突破了传统方法。 搜索引擎是相当专业的技术，通常是指基于互联网的搜索，一般网站所具备的功能 只是自己网站内的关键字搜索，只能搜索网站内已有的内容和访问者在网站上登记过的 信息，是“搜索”而不是“搜索引擎，j l ”。 搜索引擎比传统的信息检索更为复杂，表现在：信息是分布在w e b 空间的，要求系 统的适应性很强，对平台、网络等各种复杂环境的适应能力强；信息是不稳定的，动态 性很强，因此要求系统的动态索引技术具有超级性能；信息是海量的，要求查询引擎具 有先进的查询算法，并且对相关排序的要求很高；大量冗余和垃圾信息，要求系统具有 一定的信息过滤能力：网络上的信息是多媒体的，编码不同，语言不同。 1 2 国内外搜索引擎现状 由于历史与文化、技术、资金方面的原因，目前网络上最优秀的搜索引擎几乎都来 自美国。表1 1 是国内外常用搜索引擎的总体比较。 目前搜索引擎领域的商业开发非常活跃，各大搜索引擎公司都在投巨资研制搜索引 擎系统，同时也不断地涌现出新的具有鲜明特色的搜索引擎产品，搜索引擎已经成为信 息领域的产业之一。在这种情况下，对搜索引擎技术相关领域的学术研究得到了大学和 科研机构的重视。如s t a n f o r d 大学在其数字图书馆项目中开发了g o o g l e 搜索引擎，在 大连理r 大学硕士学位论文 w e b 信息的高效搜索、文档的相关度评价、大规模索引等方面作了深入的研究，取得了 很好的成果【引。 表1 1 国内外常用搜索引擎比较 t a b 1 1t h ec o m p a r i s o no fd o m e s t i ca n di n t e r n a t i o n a ls e a r c he n g i n e g o o g l e a l t a v i s t a l y c o s y a b o o l n f o s e e k w e b c r a w l e r h o t b o t i n k t o m i 1 9 9 8 3 3 亿 美国数字设备公1 9 9 5 1 21 亿多 司 美国卡内基梅隆 大学 美国斯坦福大学 美国i n f o s e e k 公 司 华盛顿大学 1 9 9 4 5 6 6 0 0 万 1 9 9 4 5 0 0 0 万 1 9 9 5 5 0 0 0 万 l y c o sn e t w o r k 5 4 0 0 万 i n k t o m i 公司 1 9 9 6 2 2 8 0 万 m e d i c a l m a t r i xh e a l t h i t e 公司 搜狐 百度 天网 g o y n y o 爱特信公司 百度网络公司 北京大学 5 0 0 多个 医学站点 1 9 9 8 2 2 0 0 万 1 9 9 9 4 5 0 0 万 1 0 0 万 简单、高级检索、 精确检索、网站定 位 简单、高级检索、 精确检索 自然语言、布尔、 截词检索 主题，关键词检索、 布尔、精确检索 主题分类、关键词 查询 自然语言、布尔检 索 布尔运算、关键词 关键词、词根检 索；形表必用或禁 用词 分类、关键词检索 分类查询、关键 分类浏览、简单、 高级检索 简单、高级查询、 查词串查询率高 香港优联克、北1 9 9 7 2 4 万关键词、分类主题 京联克公司 标准、相关性排序、 页显示结果数可选择 标准、压缩、详细格 式、页显示条数可选 择 结果显示可选择 简短描述，检索结果 较好，但数量不多 相关性排序，结果有 描述、较详细，收费 详细的信息描述结果 显示网站打分 无相关排序 智能相关排序，有描 述：无摘要 简单、详细格式 标准、简要格式 详细格式、有描述， 相关性排序 命中率高，重复网页 多相关性排序，标准 简要 网页过滤、详细格式 张东方：基于相关反馈的人机对话搜索引擎系统 n e c 美国研究所的s t e v el a w r e n c e 和c l e eg i l e s1 9 9 8 年和1 9 9 9 年连续两年在自 然和科学杂志上撰文对搜索引擎技术的研究进行评述。著名的信息检索会议t r e c 也从1 9 9 8 年开始增加了w e bt r a c k 课题，以考察w e b 文档与其它类型文档在检索性质 上的不同之处，并将测试在大规模的w e b 库f 如1 0 0 g 字节) 上进行信息检索的算法性能 【5 1 。 由美国i n f o m o t i c s 公司主办的搜索引擎国际会议从1 9 9 6 年开始，每年举行一次， 对搜索引擎技术进行总结、讨论和展望，参加者有著名的搜索引擎公司、大学和研究机 构的学者，对搜索引擎技术起到了很好的推动作用。另外象i e e e 主办的国际万维网会 议、人机交互会议已有越来越多关于搜索引擎技术研究的文章发表。 国内先后有北京大学、清华大学、国家智能研究中心等高校和研究单位对搜索弓l 擎 技术开展研究，并开发出了几个较好的系统。如由北京大学计算机系网络研究室开发的 “天网”中英文搜索引擎( h t t p ：p c c m s p k u e d u c n ：8 0 0 0 t g b i n d e x h t m ) ，在系统规模及系统 性能方面达到了国外中型搜索引擎系统的技术水平，为国内用户提供了很好的互联网搜 索服务，受到了用户的好评。 1 3 本文的主要工作 虽然国内外搜索引擎数目众多，但由于技术各方面的原因，还存在着不少问题。 比如查准率低，智能程度低，人机交互程度不够，各搜索引擎的语法不统一，用户难以 掌握等。 本文对搜索引擎的研究主要针对以上所列举出的搜索引擎智能程度低，没有较好的 反馈机制以及无法为用户提供较好的个性化服务的这些缺陷，本文的设想和改进如下。 现在对搜索引擎的研究主要集中在提高搜索引擎对网页的搜索以及索引的编制方 面，而面向用户界面不够友好，用户检索不便正是现有搜索弓擎一个很大的缺点，搜索 引擎可以利用人机交互方法来解决这个问题，不仅可以提供给用户更友好的界面，也实 现个性化、智能化的服务。虽然目前的搜索引擎大多具备“进一步提交筛选”的功能， 在第一次搜索结果提交之后，追加关键词或者指定不可含有的关键词，对结果进行再次 搜索，这样可以达至口一定的效果，但是因为现行的搜索引擎都需要用户对其下达指令， 而指令的形式也仅限于用户在搜索引擎上输入关键词，从而导致用户必须绞尽脑汁来考 虑适当的关键词。考虑关键词的工作也就变的较为复杂，更因为用户的知识结构和教育 水平而大相径庭，有碍于互联网的大众普及。 为了解决这个问题，本文研究和实现了基于反馈信息的人机对话搜索引擎，利用用 户认为相关和不相关的搜索结果作为反馈信息，对用户反馈的这些信息建立文本特征向 大连理二l ：大学硕士学位论文 量，根据一定的反馈方法分别得出符合用户查询要求和不符合用户查询要求的文本特征 向量，根据候补网页与他们的相关性得到离用户目的网页近的候补网页，作为再搜索的 结果提交给用户。这样不仅提高了搜索引擎系统的准确率，也避免了用户以输入关键词 的形式下达指令，从而使得查询更加智能化和人性化。 1 4 本文的结构和内容 本文主要探讨了目前搜索引擎的发展状况，分析了现行的搜索引擎的缺陷，并且针 对搜索引擎人机交互程度不够的缺点，提出了一种基于相关反馈的人机对话搜索引擎。 通过对相关性及已有的反馈方法的分析，以s a l t o n 的理论为依据，设计了一种新的基于 “离用户理想的特征向量近，离不理想的特征向量远”这一理论的搜索引擎，实现很多 用户所希望的个性化查询，并且提高搜索系统的效率。同时实现了这个人机对话搜索引 擎系统来验证设计的反馈方法。 本文的结构和内容如下： 第一章为“绪论”，简要介绍搜索引擎的概念，国内外搜索引擎研究的现状，本文 对搜索引擎缺陷做出的改进。 第二章为“搜索引擎简介”，简要介绍了搜索引擎的发展历史，未来的发展方向以 及目前存在的缺陷。 第三章为“人机对话搜索引擎的设计”，详细分析了相关性在搜索引擎中的作用， 设计了人机对话搜索引擎中要采用的基于相关性的相关反馈机制，对向量空间模型进行 分析，最后给出了一种基于向量空间模型的反馈方法。 第四章为“人机对话搜索引擎的实现”，开发了一个人机对话搜索弓 擎系统来验证 上文设计的反馈方法，在数据集上对人机对话搜索引擎系统的性能做测试并根据测试结 果分析人机对话搜索引擎的优越性。 第五章为“展望”，指出了搜索引擎今后的发展趋势。 最后为“结论”，总结本文所做的工作并提出人机对话搜索引擎的发展方向。 张东方：基于相关反馈的人机对话搜索引擎系统 2 搜索引擎简介 2 1 搜索引擎的发展 所有搜索引擎的祖先。是1 9 9 0 年由m o n t r e a l 的m c g i l lu n i v e r s i t y 学生a l a ne m t a g e 、 p e t e r d e u t s c h 、b i l l w h e e l a n 发明的a r c h i e ( a r c h i e f a q ) 。a r c h i e 是第一个自动索引互联 网上匿名f t p 网站文件的程序，但它还不是真正的搜索引擎。 由于a r c h i e 深受欢迎，受其启发，n e v a d as y s t e mc o m p u t i n gs e r v i c e s 大学于1 9 9 3 年开发了一个g o p h e r ( g o p h e rf a q ) 搜索工具v e r o n i e a ( v e r o n i c af a q ) 。j u g l l e a d 是后来另 一个g o p h e r 搜索工具f 6 1 。 与w a n d e r e r 相对应，1 9 9 3 年1 0 月m a r t i j nk o s t e r 创建了a l i w e b ( m a r t i i i lk o s t c r a n n o u c e st h ea v a i l a b i l i t yo f a l i w e b ) ，它相当于a r c h i e 的h r r r p 版本。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 ( f i r s tm e n t i o no f m c b r y a n sw 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 g ( r b s e ) s p i d e r 。 1 9 9 3 年2 月，6 个s t a n f o r d ( 斯坦福1 大学生的想法是分析字词关系，以对互联网上 的大量信息作更有效的检索。这就是e x c i t e 。2 0 0 2 年5 月，被i n f o s p a c e 收购的e x c i t e 停止自己的搜索引擎，改用元搜索引擎d o g p i l e 。 1 9 9 4 年1 月，第一个既可搜索又可浏览的分类目录e i n e tg a l a x y ( t r a d e w a v eg a l a x y ) 上线。除了网站搜索，它还支持g o p h e r 和t e l n e t 搜索。 1 9 9 4 年4 月，s t a n f o r d 两名博士生，美籍华人j e r r yv a n g ( 杨致远) 和d a v i df i l o 共同 创办了y a h o o 。因为y a h o o ! 的数据是手工输入的，所以不能真正被归为搜索引擎，事实 上只是一个可搜索的目录。搜索效率明显提高。( y a h o o 以后陆续使用a l t a v i s t a 、i n k t o m i 、 g o o g l e 提供搜索引擎服务1 。 1 9 9 4 年初，w a s h i n g t o n 大学c s 学生b r i a np i n k e r t o n 开始了他的小项目 w e b c r a w l e r ( b r i a np i n k e r t o na n n o u n c e st h ea v a i l a b i l i t yo fw e b c r a w l e r ) 。1 9 9 4 年4 月2 0 日，w e b c r a w l e r 成为互联网上第一个支持搜索文件全部文字的全文搜索引擎见 l y c o s 是搜索引擎史上又一个重要的进步。1 9 9 4 年7 月2 0 日，数据量为5 4 ，0 0 0 的 l y c o s 正式发布。 i n f o s e e k 是另一个重要的搜索引擎，虽然公司声称1 9 9 4 年1 月已创立，但直到年底 它的搜索引擎才与公众见面。 大连理 大学硕士学位论文 1 9 9 5 年，一种新的搜索引擎形式出现了一一元搜索引擎( am e t as e a r c he n g i n e r o u n d u p ) 。第一个元搜索引擎，是w a s h i n g t o n 大学硕士生e r i cs e l b e r g 和o r e n e t z i o n i 的m e t a c r a w l e r 。元搜索引擎概念上好听，但搜索效果始终不理想，所以没有哪个元搜 索引擎有过强势地位。 d e c 的a l t a v i s t a 是一个迟到者，1 9 9 5 年1 2 月才登场亮相( a l t a v i s t ap u b l i cb e t ap r e s s r e l e a s e ) a 然后到来的是h o t b o t 。 1 9 9 7 年8 月，n o r t h e m l i g i l t 搜索引擎正式现身。 1 9 9 8 年1 0 月之前，g o o g l e 只是s t a n f o r d 大学的一个小项目b a c k r u b 。1 9 9 5 年博士 生t a r r yp a g e 开始学习搜索引擎设计，于1 9 9 7 年9 月1 5 日注册了g o o s e t o m 的域名， 1 9 9 7 年底，在s e r g e yb r i n 和s c o t th a s s a n 、a l a ns t e r e m b e r g 的共同参与下，b a c h r u b 开 始提供d e m o 。1 9 9 9 年2 月，g o o g l e 完成了从a l p h a 版到b e t a 版的蜕变。 f a s t ( a l l t h e w e b ) 公司创立于1 9 9 7 年，是挪威科技大学( w r r , m ) 学术研究的副产品。 1 9 9 9 年5 月，发布了自己的搜索引擎a l l t h e w e b 。 t e o m a 起源于1 9 9 8 年r u t g e r s 大学的一个项目t e o m a 的数据库目前仍偏小，但有 两个出彩的功能：支持类似自动分类的r e f i n e ；同时提供专业链接目录的r e s o u r c e s 。 w i s e n u t 由韩裔y e o 舀订y u n 创立。2 0 0 1 年春季发布b e t a 版，2 0 0 1 年9 月5 日发布 正式版，2 0 0 2 年4 月被分类目录提供商l o o k s m a r t 收购。w i s e n u t 也有两个出彩的功能： 包含类似自动分类和相关检索诃的w i s e g u i d e ；预览搜索结果的s n e a k a p e e k 。 g i g a b l a s t 由前i n f o s e e k 工程师m a t tw e l l s 创立，2 0 0 2 年3 月展示p f e - b e t a 版，2 0 0 2 年7 月2 1 日发布b e t a 版。g i g a b l a s t 的数据库目前仍偏小，但也提供网页快照，一个特 色功能是即时索引网页。 o p e n f i n d 创立于1 9 9 8 年1 月，其技术源自台湾中正大学吴升教授所领导的g a d s 实验室。 北大天网是国家九五重点科技攻关项目中文编码和分布式中英文信息发现的研究 成果，由北大计算机系网络与分布式系统研究室开发，于1 9 9 7 年1 0 月2 9 日正式在 c e r n e t 上提供服务【8 i 。 b a i d u2 0 0 0 年1 月，超链分析专利发明人、前l u f o s e e k 资深工程师李彦宏与好友徐 勇( 加州伯克利分校博士) 在北京中关村创立了百度( b a i d u ) 公司。2 0 0 1 年1 0 月2 2 日正式 发布b a i d u 搜索引擎。b a i d u 虽然只提供中文搜索，但目前收录中文网页超过9 0 0 0 万， 可能是最大的的中文数据库。 张东方：基于相关反馈的人机对话搜索引擎系统 2 2 目前搜索引擎存在的缺陷 搜索引擎发展异常迅速，到今天已经出现了很多应用于不同领域，提供各种服务的搜 索引擎。但随着网络技术的发展以及互联网的壮大，它存在的缺陷也日渐暴露出来1 4 j 。到目 前为止搜索引擎的缺陷主要有以下几点。 查全率低。只能搜索与用户输入的关键词相匹配的网页信息，不能列出含有与该词含 义相同的关键词的网页。而用户在选择检索用关键词时常常会觉得很困难，要用户掌握同 一概念的所有关键词更是不可能的事情。 查准率低，搜索结果与请求相差较大。按照用户的搜索请求列出的结果往往与用户的 本来意图相差较远，进行全文检索时搜索引擎的分词技术( 尤其是中文分词技术) 还不成熟， 搜索出来的结果往往是机械地与用户输入的关键词进行字面上的匹配，而没有从概念上加 以考虑。 各搜索引擎的语法不统一，用户难以掌握。各个搜索引擎的界面都不一样，所能提 供的检索方法也不尽相同，关键词之间的连接方式更是千差万别，没有一个统一的规范。 无论使用哪种搜索引擎，用户都必须先学习这种搜索引擎的使用方法，增加了用户的负 担。同时由于用户无法掌握好各搜索引擎的语法规则，在检索时往往采用简单的关键词 检索，无形中又降低了查全率和查准率。 检索策略简单，组合检索能力差。目前，搜索引擎所能提供的检索方式基本上都是 关键词检索，用一组关键词及逻辑运算符组成提问式，并不能完全满足用户的需求。而 且，搜索引擎还不能对自然语言的提问做出反应。某些搜索引擎虽然支持复杂检索，但 对用户来说不够友好，需要用户在检索前进行学习，缺乏交互机n 9 0 “】。 缺乏专门面向某一学科的专题性搜索引擎。对于专业人员和研究人员来说，综合性 搜索引擎由于自身的局限，信息查准率低，用户的需求与得到的检索结果相差可能很大。 而专题性搜索引擎则能比较好地解决这些问题，它不求包罗各个学科，但求本专业、本 学科最全。由于专题性搜索引擎的规模较综合性搜索引擎来说要小得多，其索引质量可 以得到较好的控制，尤其适合为学术研究所用。 搜索引擎的智能程度还很低。搜索引擎基本不对搜索结果进行过滤，同一站点下的 不同页面被排在一起输出，重复的页面信息也不断出现。现有搜索引擎基本不具备学习 功能，在用户检索的过程中搜索引擎不能与用户进行交流，没有较好的反馈机制，无法 为用户提供比较好的个性化服务。 大连理 ：大学硕士学位论文 3 人机对话搜索引擎的设计 3 1 相关性分析 3 1 1 对相关性的理解 当用户检索的时候，首先需要输入关键词，系统将对其进行语言分析，分解成多个 词或词组，在去服务器的索引数据库，根据检索词的相关性进行匹配，找到与检索词相 关度逼近的网页，按照相关度的高低进行排序输出，关键词出现了的越多的结果排得越靠 前，越知名的站点排得越靠前。这里，相关性的设计相当的重要，它直接影响着搜索的效 率。但“相关性”的概念一直非常模糊。一方面，人们观察到特定文档对特定查询而言 可以有多种“相关”的方式，比如用户输入一个关键词作为查询向系统提交，系统返回的 文档列表中的文档a 讲述与此关键词相关的事件，b 谈论与此关键词相关的人物等等， 都可以说与这个关键词“相关”，但我们显然觉得二者与查询的相关并不属于同一层次。 另一方面，由于用户本身的差异使其对检出文档是否真正相关的判断也有诸多差异。但 是在设计信息检索系统的过程中，不可避免地要用到相关性这个概念；具体地说，设计者 必须对怎样才算是“相关”有一个比较明确的想法，在没有弄清楚什么是相关性之前就 谈论怎样区别相关和不相关文档，的确令人觉得在逻辑上缺少了一个重要的环节。 3 1 2 用户角度的相关 随着检索系统日益广泛的应用，特别是由于近几年来互联网络的急剧膨胀，研究者 投向用户的目光越来越多了。人们开始更多地思索人机交互过程中人的因素。其实如前 所述，相关性判断的不确定性向来是一个众所周知的事实。这种不确定性是由多种原因 造成的，但基本上集中于用户的主观因素上。 、 s a r a c e v i c ( 1 9 7 0 ) 等人使用概念相关( c o n c e p t u a lr e l a t e d n e s s ) - - 语，强调相关匹配应当是 文档所含信息与用户需求信息两者的概念之间的匹配。这种定义相对地侧重于抽象的意 义：要取得这种相关性，从文档中提取的特征信息应该能准确表示文档的核心意义，同 时系统还要完全“领会”用户提交的查询所表达的真正需求【1 2 j 。这无疑是一个理想的状 态：系统只有在真正“理解”来自文档和用户查询两方面信息内容的前提下才谈得上“概 念”上的比较。但是这种定义仍然起不了什么作用，因为意义既然无法完全把握，究竟 怎样才算“理解”并不清楚。 张东方：基于相关反馈的人机对话搜索引擎系统 从用户角度讨论相关大体上就是观察用户对检索结果的反应，是系统输出向用户需 求的投射。相关性被认为是用户方面的属性。相关性判断就可以看作是从文档( 外部刺 激材料) 在用户内部因素中的反映，它的基本模式如图3 1 所示。 内部因素 图3 1 用户角度相关的基本模式 f i g 3 1t h e t e v a n c eo fu s e r sm o d a l 外部因素 3 1 3 搜索引擎系统角度的相关 信息检索似乎从一开始就定位为一种单方向的过程，即系统输出结果，用户是信息的 接受者。这种理解置用户于被动的地位：基于这种理解，研究的重心自然落在搜索引擎系 统本身。系统角度的相关一般有两种比较方式。其一是在文档本身固有的特征信息，如 词频等等与用户提交的查询表达式中固有的特征信息之间进行比较。典型做法是在文档 集中寻找出现了查询表达式中的索引项的文档：其二是在从文档中抽取的“主题”与用 户查询表达式中体现的“主题”之间做比较，即首先计算文档中各索引项的权值，再按 权值大小进行排序，以此为依据确定文档的主题词。这种做法比较简单明了，易于操作 而且可以直接观察，所以一真是搜索引擎努力的目标【1 3 】。 、 系统角度的相关一般有两种比较方式。其一是在文档本身固有的特征信息( f c a t u r e l 如词频等等与用户提交的查询表达式中固有的特征信息之间进行比较。典型做法是在文 档集中寻找出现了查询表达式中的索引项( i t e m ) 的文档；其二是在从文档中抽取的“主 题”( t o p i c ) 与用户查询表达式中体现的“主题”之间做比较，即首先计算文档中各索引 项的权值，再按权值大小进行排序，以此为依据确定文档的主题词。以上两种方式如下 图3 2 中所示。 1 0 大连理工大学硕士学位论文 图3 2 系统角度相关两种典型的比较方式 f i g 3 2t h ec o m p a r i s o n so ft h er e l e v a n c eo fs y s t e m 3 1 4 改进后的系统相关 从系统角度定义的相关性( 即主题性相关) 最突出的优点，就是简明和可操作性，而 至少目前的系统还无法把握人的主观感觉。这样看来，采取主题性相关的态度就是唯一 可行的做法。然而并不能把词频统计作为唯一的解决办法。f a i r t h o m 曾提出：如果允许 个人推论和个人理解介入相关性判断，那么从某种角度来看，任何文本对任何请求都是 相关的。所以，改进系统角度相关度计算方法似乎比较可以接受1 1 4 j 。基于此种看法，在 这里可以做这样一个设想：如果主题词提取能体现用户的相关性判断直觉，那么用户的 相关性判断就可以被描述，而检索系统的输出就可能更加令人满意( 见下图3 3 ) 。系统角 度相关不能解决相关性判断的不确定性。相关性判断的不确定性基本上集中于用户的主 观因素上。因此应该更多地思索人机交互过程中人的因素。 3 2 相关反馈在人机对话搜索引擎中的应用 3 2 1 相关反馈的提出 反馈是控制论中的重要手段，用输出来调整系统，调节系统中不稳定的因素。在信 息检索中，反馈一样可以发挥这样的作用。在一个信息检索系统中，文档是稳定的，检 索的方法是相对稳定的，最不稳定的是用户。每个用户构造查询的能力不同，每个用户 对相关性的判定不同，反馈就是要减小甚至消除这些不稳定的因素对系统性能的负面影 响。用户对检索出的文档进行相关性的判定，系统根据这些判定生成新的查询，从而提 张东方：基于相关反馈的人机对话搜索引擎系统 高最终结果的准确率，如果用户对结果仍不满意，可以重复这一过程，直到找到更多的 相关文档。由于反馈是由对文档相关性的判定为开始的，因此又称相关反馈【7 】a 文档的 相关性判定本身就有很大的主观成分，让机器去揣摩用户的心理是不现实的，在此就有 人提出了伪相关反馈的机制，系统默认自己检索出的结果中含有大量相关的文档，从中 取出前n 篇做为相关文档，对查询进行调整。 图3 3 文档和查询的相关表示 f i g 3 3t h er e l e v a n c eo fd o c u m e n t sa n dq u e r y 相关反馈式查询可能至少有这样两种情况： ( 1 ) 用户的后续查询( s u b s e q u e n tq u e r i e s ) 可对其不够具体的初始查询( i n i t i a lq u e r y ) 进行细化、具体化。这种情况是相关反馈技术所期望发生的。后续查询的作用大致相当 于过滤器，将已经检出的文档集不断缩小，最终得到相关度最大的文档集。 ( 2 ) 用户的查询目的并不十分明确，后续查询与初始查询相比发生了某种细微