（管理科学与工程专业论文）信息检索中的查询优化技术研究.pdf

信息检索中的查询优化技术研究 摘要 随着计算机网络技术的迅速发展，信息的发布与共享不再受到时间和空间 的限制，互联网上的信息急剧膨胀，在为用户提供大量信息的同时也带来了“信 息过载”的问题。网上庞大的数字化信息与人们获取所需信息能力之间的矛盾 日益突出。怎样快速准确地检索相关信息己经成为当今信息领域的一个重要研 究方向。 查询条件的构造是影响检索效果的一个重要因素。由于大部分搜索引擎用 户是普通网络用户，在检索策略和检索技巧上缺乏必要的知识，用户在进行初 次检索时提交的查询往往比较短，不能具体准确的描述查询意图，导致检索结 果偏离用户的信息需求。因此，查询优化技术的研究成为了信息检索中的一个 热点。 本文在广泛深入地查阅国内外文献的基础上，对信息检索及查询优化问题 的基础理论和基本方法进行了深入的理论研究和实验分析，主要内容如下： 本文首先介绍信息检索领域的发展，系统、详尽的介绍了信息检索的一般 模式和基本模型，以及信息检索中查询优化技术的基本理论和方法。对经典的 模型和方法作了全面的总结和分析比较，指出其应用范围、不足之处。 介绍了遗传算法的基本概念和实现步骤，对遗传算法及其在信息检索中的 应用进行研究和总结，表明了遗传算法用来解决查询优化问题的有效性，并给 出了基于遗传算法的查询优化方法的实现步骤和系统框架。最后将遗传算法与 局部共现方法相结合，在使用局部共现方法对查询词进行扩展的基础上利用遗 传算法进一步优化查询权重，并对遗传算法中的遗传操作算子和适应度函数进 行分析和改进，提出了一种新的基于局部共现和遗传算法的查询优化方法。 关键词：信息检索，查询优化，遗传算法，局部共现 t h er e s e a r c ho fq u e r yo p t i m i z a t i o nt e c h n o l o g yi n i n f o r m a t i o nr e t r iq11na t i o nr e t r i e v a li 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 fc o m p u t e rn e t w o r kt e c h n o l o g y ，t h ei s s u a n c ea n d s h a r i n go fi n f o r m a t i o nn ol o n g e rs u b je c t t ot h ec o n s t r a i n t so ft i m ea n ds p a c e ， i n f o r m a t i o no nt h ei n t e r n e ti n f l a t e sr a p i d l y ，i th a sa l s o b r o u g h tt h e ”i n f o r m a t i o n o v e r l o a d ”p r o b l e mw h i l ep r o v i d e dt h em a s s i v ei n f o r m a t i o nf o rt h eu s e r s t h e c o n t r a d i c t i o nb e t w e e nt h eh u g ed i g i t a li n f o r m a t i o na n dt h ea b i l i t yo f p e o p l et og a i n t h ei n f o r m a t i o nw h i c ht h e yn e e dh a sb e c o m e i n c r e a s i n g l yp r o m i n e n t h o wt o r e t r i e v er e l e v a n ti n f o r m a t i o nq u i c k l ya n da c c u r a t e l yh a sb e e na ni m p o r t a n ta r e ao f r e s e a r c hn o w a d a y s t h ec o n s t i t u t i o no fq u e r yi sa ni m p o r t a n tf a c t o ra f f e c t st h ee f f e c to fi n f o r m a t i o n r e t r i e v a l a sm o s ts e a r c he n g i n eu s e r sa r eo r d i n a r yi n t e r n e tu s e r s ，t h e yl a c kt h e n e c e s s a r yk n o w l e d g ea b o u tt h er e t r i e v a ls t r a t e g i e sa n ds k i l l s ，t h eq u e r yw h i c ha r e i n p u tb yu s e r sf o rt h ef i r s tt i m eu s u a l l yt ob es h o r ta n dc a nn o td e s c r i b et h e i rq u e r y i n t e n t i o ne x a c t l y t h i sp r o b l e mr e s u l t si nt h eu s e r s s e a r c hr e s u l t sd e v i a t et h e i r i n f o r m a t i o nn e e d s t h e r e f o r e ，t h er e s e a r c ho f q u e r yo p t i m i z a t i o nt e c h n o l o g y b e c o m e sah o t s p o ti ni n f o r m a t i o nr e t r i e v a l b a s e do ne x t e n s i v ea n dd e e pr e v i e w o fl i t e r a t u r e ，at h o r o u g h a n a l y s i sa n d r e s e a r c ho nm a n yt h e o r e t i c a la n da p p l i c a t i o no r i e n t e dp r o b l e m si s p r e s e n t e d t h e m a i nc o n t e n t sf o l l o w ： t h i st h e s i sp r e s e n t st h ed e v e l o p m e n to fi n f o r m a t i o nr e t r i e v a lf i r s t l y , t h eg e n e r a l p a t t e r na n dt h eb a s i cm o d e lo fi n f o r m a t i o nr e t r i e v a l ，a sw e l la st h eb a s i ct h e o r ya n d m e t h o d so ft h eq u e r yo p t i m i z a t i o nt e c h n o l o g ya r es y s t e m a t i c a l l ya n dt h o r o u g h l y i n t r o d u c e d b ya n a l y z i n go nt h ec l a s s i c a lm e t h o d s ，t h et h e s i sp o i n t so u tt h e i r s p e c i a la p p l y i n ga r e a sa n ds h o r t c o m i n g s t h i st h e s i sp r e s e n t st h eb a s i cc o n c e p ta n di m p l e m e n t a t i o ns t e p so ft h eg e n e t i c a l g o r i t h m ，c o n c l u d e st h ea p p l i c a t i o no fg e n e t i ca l g o r i t h mi ni n f o r m a t i o nr e t r i e v a l ， a n ds h o w st h a ta l g o r i t h mi sp r a c t i c a l b yi m p r o v i n gt h eg e n e t i ca l g o r i t h m ，aq u e r y o p t i m i z a t i o nb a s e do ng e n e t i ca l g o r i t h mi sp r o p o s e d f i n a l l y , w ep r o b ei n t ot h e e f f e c to ft h ec o m b i n a t i o no fg e n e t i ca l g o r i t h ma n dl o c a le o o c c u r r e n c eo nq u e r y o p t i m i z a t i o n w e u t i l i z ec o o c c u r r e n c ew i t ht h e q u e r yt e r m si nt h er e l e v a n t d o c u m e n t st o e x p a n dt h eq u e r y , t h e nu s e dg e n e t i i ：a l g o r i t h m st or e w e i g h tt h e e x p a n dq u e r yv e c t o r ，p r o p o s ean e wq u e r yo p t i m i z a t i o nm e t h o db a s e do ng e n e t i c a l g o r i t h ma n dl o c a lc o o c c u r r e n c e i i k e y w o r d s ：i n f o r m a t i o nr e t r i e v a l ，q u e r yo p t i m i z a t i o n ，g e n e t i ca l g o r i t h m ，l o c a l c o - o c t u r y e n c e u i 插图清单 信息检索模型的分类3 文档和查询在v s m 中的关系1 3 遗传算法的基本流程图2 0 基本变异算子示意图2 6 基于遗传算法的查询优化系统框架图3 0 基于局部共现和遗传算法的查询优化系统3 2 基于遗传算法的权重分配方法流程图一3 5 不同查询使用三种算法在检索出1 0 篇文档时的查全率一3 9 不同查询使用三种算法在检索出1 0 篇文档时的查准率一3 9 不同查询使用三种算法在检索出2 0 篇文档时的查全率4 0 不同查询使用三种算法在检索出2 0 篇文档时的查准率一4 0 v i i l 1 1 2 3 1 2 3 4 5 6 l互文文文乱乱乱乱乱乱 图图图图图图图图图图图 表格清单 表4 1 查询性能比较图4 0 v i l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得金月巴王些盍堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字：绦塾签字日期：沙f 年r 月叩日 学位论文版权使用授权书 本学位论文作者完全了解金壁王业太堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金目曼兰些太 兰l 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名： 绦望 签字日期：舴y 月c 7 e l 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名：露彳匀夹 签字日期：沙y 年厂月f 7 日 电话： 邮编： 致谢 值此论文完成之际，我谨向所有关心和帮助过我的老师、同学、朋友以及 家人致以最真诚的谢意。 本论文的撰写是在我的导师杜习英副教授的指导下进行的。在我的论文写 作阶段，杜老师付出了大量的心血和宝贵的时间，从论文的选题、撰写直到修 改完成的每个阶段，都得到了杜老师的指导、关心、支持和信任。杜老师除了 在课题研究上给了我悉心的指导外，更教会了我待人处事的方式以及很多做人 的道理，这些必将使我一生受益匪浅，杜老师对我的教诲我将终生铭记，衷心 的感谢杜老师! 我还要特别感谢李兴国教授在我三年读研期间的关心、指导和帮助，从论 文的选题、撰写直到论文完成的过程中，李老师严格要求、悉心指导，使我能 够顺利完成毕业论文，衷心的感谢李老师! 感谢合肥工业大学管理学院的钟金宏、顾东晓、卢光松、杨颖等老师对我 的关心、指导和帮助。还要感谢在研究生学习阶段的全体任课老师，教给我们 丰富的专业理论知识和方法，感谢合肥工业大学管理学院的领导和老师们为我 们提供了良好的工作学习环境。 感谢曾同在一个工作室的师兄刘嘉嘉、夏同胜、田春明、杨磊、杜颜，以 及杨贞、吴亦汉，感谢我的室友张伟利、王小红、章宁、吕文静，你们在学习 和生活中给予了我很大的帮助，真的很感谢你们! 感谢研2 4 班的同班同学及远在各地的好友，有了你们的支持和鼓励，我的 论文才能得以顺利完成。 感谢我的父母家人，是他们二十多年来的呵护、关心、支持和鼓励，使我 得以顺利完成学业。感谢他们给我健康的身体、上进的思想! 感谢各位评审专家在百忙之中抽出时间对论文进行了仔细的评阅! 最后，感谢所有帮助和关心过我的人们! w 徐莹 2 0 0 8 年4 月 1 1 研究背景 第一章绪论 在现代的信息社会里，计算机科学和技术的进步使得以电子形式存在的信 息迅速增长，信息的发布与共享不再受到时间和空间的限制，越来越多的人们 借助于i n t e r n e t 去获取各种各样的信息。然而，由于网络信息资源庞大丰富，真 正对自己有用的却相对匮乏。无关信息淹没了用户所需要的信息，用户试图通 过浏览w e b 来寻找信息已经变得非常困难，主要表现在以下两个方面：第一， 用户收到或下载了太多信息，却无法有效整合、组织及消化成自己所需要的信 息，即所谓的“信息过载”；第二，用户不知道如何贴切表达真正想要的网 上资源的需求，也不知道如何去更准确有效地寻找，即所谓的“信息迷向 【2 】。 查询效率成为了信息检索系统的一个突出瓶颈。 能够快速准确地获得所需要的信息是人们的迫切要求，而有力的信息检索 工具的支持将是必不可少的。在有文字记载以来，人类一直在进行着信息的组 织以利于以后的检索和使用，典型的例子就是书籍的目录。从传统的索引信息 到图书馆中的卡片信息管理系统，随着信息环境的变迁，用户需求的变化，信 息技术的进步，信息检索的内涵越来越丰富，这也使得信息检索逐渐发展成为 一门学科并成为信息学中研究热点之一。w e b 的出现更为信息检索提供了前所 未有的实现环境和应用领域。但由于w e b 信息的大容量、异构性、分布式和动 态性等特点，给信息检索领域带来了新的挑战，需要在传统的信息技术基础上 开展针对w e b 特点的研究工作。 w e b 信息检索属于信息检索的范畴，是信息检索领域较为重要的发展阶段。 w e b 信息检索的困难主要来自于两方面的原因：第一和网络信息资源组织问题 有关。用标题、文摘或全文中出现的关键词来标识网络信息资源的内容，通常 不能充分解释源信息的实质内涵，造成我们在检索结果上的遗漏误差；第二是 用户如何准确地表达自己的查询需求，有效地和信息检索系统进行交互。在信 息检索的研究与实践中，存在着这样一个问题：检索的不确定性，所谓检索的 不确定性，是指检索的试探性和模糊性。由于用户对文档集的环境和检索环境 缺乏详细了解，以及自然语言的模糊性和用户信息需求本身的随机性和动态性， 用户的信息需求不可能充分表达，总之，在进行信息查找行为时，用户的信息 需求是模糊的。在通常情况下，由用户提交的信息需求是一个短句或几个关键 词。优化用户查询，更准确、客观地表达用户的查询需求，帮助用户快速准确 地获得所需要的信息，已经成为信息检索领域的重要研究方向，因此查询优化 成为了信息检索中的一个研究热点。 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 1 3 是借鉴生物的自然选择和遗传进 化机制而开发出的一种全局优化自适应概率搜索算法。遗传算法是一种适用于 在大的求解空间上寻找最优解的有效方法。对于信息检索系统中寻求一个较优 的查询来说，也是这样一个在大的求解空间上寻找最优解的问题。本文通过对 国内外查询优化技术的研究发现：遗传算法在查询优化中效果显著，该方法能 够提高查询优化的效果。 本文针对目前查询优化方法的不足，提出了一种新的查询优化方法，希望 通过不断地优化查询能够更加准确地描述用户需求，提高信息检索的效果，达 到帮助用户快速准确地获得所需要的信息的目的。 本文主要从以下两个方面研究查询优化技术： ( 1 ) 采用基于局部共现的查询扩展方法选择扩展词对用户提供的初始查询 进行扩展。 ( 2 ) 使用遗传算法对扩展后的查询进行权重调整以进一步提高查询优化的 效果。 1 2 信息检索的研究现状 信息检索( i n f o r m a t i o nr e t r i e v a l ，简称i r ) 4 1 是2 0 世纪5 0 年代在国外兴起 的一门新兴学科，主要研究信息的表示、存储、组织和访问，即根据用户的要 求，从信息数据库中检索与之相关的信息资料。信息检索的兴起源于计算机技 术的广泛应用和网络通信技术的迅速普及。近年来，信息检索在我国有了突飞 猛进的发展，成为当前图书情报界研究的一个焦点。 信息检索是指从大量文档的集合中找到与给定的查询请求相关的、恰当数 目的文档子集1 5 1 ，是搜索引擎用来处理海量文档的重要手段之一。文档是信息 检索系统检索的对象，查询是信息检索系统据以检索的对象。信息检索在搜索 引擎中是面向用户的最后环节，也是构造搜索引擎的目的所在，无论系统如何 设计，最终是为了信息检索，为了为用户提供服务。 最初的信息检索系统是图书馆中的文献检索系统，这些检索系统大都采用 了基于文献文档内容的关键字匹配技术，这样的系统在图书馆中发挥了重要的 作用，直到今天仍然有很多图书馆采用这样的系统来管理文献，给读者提供检 索服务。这样的检索系统在文档规模较小时还能较好的完成用户的检索需求， 少量与检索不相关的文档不会对用户阅读检索结果造成太大的影响，但是w e b 的出现改变了这一切。随着网络信息资源的迅速增加，为用户提供海量信息的 同时，也带来了大量的噪声。如何在浩瀚的信息海洋中准确、方便、快速地找 到自己所需的信息，是个迫切需要解决的问题。网络信息资源的极大丰富和无 序使得网络信息检索成为当前信息领域的一个研究热点。 随着网络信息资源的日益丰富和复杂化，为满足不同用户能够检索到所需 信息，检索系统朝着自然语言检索、用户界面友好的方向发展，这给信息检索 技术提出了更高的要求。因此，当前信息检索技术的研究主要包括以下几方面 2 1 2 1 信息检索模型研究 我们把信息检索模型定义如下： 一个信息检索模型是将文档表示、查询以及它们之间关系进行建模的框架， 它由三元体f d ，q ，r iq id ) 】表示。其中，d 是文档集中的一组文档逻辑视图( 或 称为文档的表示) ；q 是一组用户信息需求的逻辑视图( 表示) ，这种视图( 表示) 被称为查询；r ( q id ，) 是一个排序函数，该函数输出一个与查询吼q 和文档表 示d ，d 有关的实数。这样就在文档之间根据查询吼定义了一个序列。 信息检索中四个传统模型是：布尔模型( b o o l e a n ) 、向量空间模型( v e c t o r s p a c em o d e l ，简称v s m ) 、概率模型( p r o b a b i l i s t i cm o d e l ) 和逻辑模型( l o g i c m o d e l ) 。近年来，研究人员对于每种传统的模型都提出了各种不同的改进模式， 如在基于集合论的检索模型中，提出了模糊布尔模型和扩展布尔模型；在向量 空间模型的基础上，衍生出广义向量模型、潜在语义索引模型和神经网络模型 等三种；在概率检索模型中，发展出推理网络模型和信念网络模型等。除了涉 及文本内容之外，模型还应该涉及文本的结构。对于文本的结构模型，主要有 两种类型：非重叠链表模型和邻近节点模型。 对这些检索模型可以用图1 1 来表示它们的层次关系【_ 7 】： 1 2 2 信息处理技术研究 图1 1 信息检索模型的分类 对信息检索的处理包括信息的自动分类、自动摘要、查询的优化，以及检 索相关性分析等几个阶段。 ( 1 ) 自动分类 自动分类研究始于2 0 世纪5 0 年代末，h p l u h n 在这一领域进行了开创性 的研究；1 9 6 0 年，m a r o n 在 j o u r n a lo fa c m ) ) 上发表了自动分类的第一篇论 文“o nr e l e v a n c e ，p r o b a b i l i s t i ci n d e x i n ga n di n f o r m a t i o nr e t r i e v a l ”；随后许多著名 的情报学家如k s p a r c h 、g s a l t o n 及r m n e e d h a m 等在这一领域都进行了卓有 成效的研究。至今，自动分类在国外已经经历了三个发展阶段：第一阶段 ( 1 9 5 8 1 9 6 4 ) 主要进行自动分类的可行性研究；第二阶段( 1 9 6 5 1 9 7 4 ) 进行自动分 类的实验研究；第三阶段( 1 9 7 5 至今) 进入实用化阶段。 ( 2 ) 自动文摘技术 自动文摘是利用计算机从文档中自动提取内容生成摘要的方法，其中摘要 应包含原文的核心内容或用户感兴趣的内容，并以语意连贯的段落乃至篇章的 形式输出，是快速获取感兴趣资源的一个准确高效的手段。近年来，人工智能、 计算机语言学的发展，以及机读形式文档的不断增加，推动了自动文摘的研究。 当前自动文摘的研究主要关注语料库技术、词法分析、句法分析、信息抽取技 术以及自动文摘技术的评价等领域的成果。 ( 3 ) 查询的优化 查询优化的目的是提高信息检索的查全率和查准率。查询优化描述了为满 足信息需求来修正查询的一系列技术。它包括将关键词加入到原始的查询中或 者从原始查询中删除不需要的关键词，以及对查询中的关键词重新计算权重。 当前主要研究对查询进行扩展和精化的一些技术，如相关反馈技术、关键词的 选择方案、各种控制词表技术、全局分析技术以及局部分析技术等。 ( 4 ) 检索相关性分析研究 自2 0 世纪5 0 年代开始，“相关性 已经成为信息科学，尤其是信息检索领域 一个历久不衰的研究课题。相关性是指文档与查询相关程度的性质。相关性是 文档满足用户需求的性质，是一个很难准确定义的概念。到目前为止，国外已 有大量的学者对信息检索中的相关性进行了深入的研究。近年来，相关性依然 是信息检索科学的研究热点。其研究课题主要包括相关性的内涵、相关性的实 证研究以及相关性的理论研究三个方面的内容。 1 2 3 信息检索技术应用研究 信息检索技术在网络信息检索系统中有着广泛的使用，由此掀起了研究网 络信息检索技术应用的高潮。 随着w e b 信息资源的迅速增加，如何准确、快速地找到自己所需的信息， 是个迫切需要解决的问题，1 9 9 5 年出现的信息检索工具一一搜索引擎很好地解 决了此问题，并且它所提供的导航服务已成为i n t e m e t 中最重要的网络服务之 一。目前搜索引擎已成为网络检索系统的核心，围绕着搜索引擎的基本概念、 分类、功能，以及实现等内容，国内外学者专家们提出了各自的见解，未来的 搜索引擎将朝着智能化、多元化、多功能化、人机交互等方向发展。 由于用户的要求越来越高，需求也朝多样化的方向发展。一年一度由美国 4 国防部和美国国家技术标准局组织的国际文本检索评测会议( t e x tr e t r i e v a l c o n f e r e n c e ，简称t r e c ) 是目前信息检索领域最活跃、引领信息检索研究方向的 著名会议之一。该会议细分为几大主要方向：问题回答、特定领域检索、传统 w e b 检索等。该会议不断的提出新的检索子任务，将用户的需求细化，以适应 这种需求的发展变化。同时，根据不同的需求，评测的标准也在不断的变化， 以更好的描述检索结果与用户需求一致的程度。 1 3 查询优化的研究现状 早在2 0 世纪7 0 年代，国外就已经有了查询优化技术的研究。研究比较多 的是查询扩展优化。查询扩展优化是解决查询过程中的查询用词与文档中词不 匹配问题的有效技术手段，它以用户的初始查询为基础，通过一定的策略向初 始查询中加入一些相关的词，以提供更多有利于判断文档相关性的信息，这在 一定程度上能弥补用户的查询表达与可能的相关文档的差别，尽可能以较小的 遗漏检索出相关文档。查询扩展仅仅是查询优化的一个手段，为了达到优化查 询的目的，不仅可以扩展查询，还可以消除或削弱查询中不相关的词。在信息 检索领域，关于查询优化方法基本上可以分为全局和局部两大类。 全局分析是较早出现的具有实际应用价值的查询优化方法，其基本思想是 对全部文档中的词或词组进行相关分析，计算每对词或词组间的关联程度。早 期的典型全局分析的方法是词聚类方法( t e r mc l u s t e r i n g ) 引，它是将文档中出现 的词按共同发生的频率先行聚类，其后根据词的不同集合对查询进行扩展。目 前常见的全局分析方法包括潜在语义索引( l a t e n ts e m a n t i ci n d e x i n g ，简称 l s i ) f 9 1 、相似性词典( s i m i l a r i t yt h e s a u r i ) 1 0 】等。但当文档集合非常大时，建立 全局的词关系词典在时间和空间上往往是不可行的，并且在文档集合改变后的 更新代价巨大。 目前流行的局部分析方法主要有相关反馈( r e l e v a n c ef e e d b a c k ) 和伪相关反 馈( p s e u d of e e d b a c k ) ，伪相关反馈是在相关反馈的基础上发展起来的。相关反 馈技术是信息检索中查询优化的一个非常重要的机制【1 1 】【1 2 】【1 3 】【i4 1 。相关反馈方 法通过增加或削减检索到的关键词的权重，一步一步地修正关键词的权重来达 到修正查询的目的，以提高检索的效果。相关反馈机制由用户对检索出的文档 进行相关性判定，判定出相关文档和不相关文档，系统根据这些判定生成新的 查询，提高最终结果的准确率。由于相关反馈的效果显著，其在信息检索方面 的应用和研究比较多，r o c c h i o 在1 9 7 1 年就提出了一种用反馈来改进查询效果 的方法，这种方法对查询同时进行扩充和缩减，其他的很多方法都由此发展而 来。典型的有i d e 的i d er e g u l a r 方法，i d ed e c h i 方法【1 4 】【1 5 儿1 6 】等。 伪相关反馈不需要与用户交互，它直接将初次查询检索出的前n 篇文档自 动认为是相关文档，以此为依据对查询进行优化。传统的伪相关反馈技术有两 大问题需要解决。一是相关文档的选择，初始检索结果中排名靠前的文档被默 认为相关文档，这个假设实际上是不成立的，只有实际相关文档对查询扩展的 贡献大于不相关文档带来的噪声时，反馈性能才会有所提高。二是相关文档中 关键词的选择，一般来说是选择权重较高的关键词进行查询扩展，这样的选择 方法保证了选取关键词的重要程度，但并不能保证关键词与主题相关。 在传统的伪相关反馈方法的基础上，许多研究者进行了一些改进工作1 1 7 1 ： 为了减少对文档相关性误判带来的负面影响，m a k o t o1 w a y a m a 提出了一种 先聚类，后反馈的方法【l 引。他认为，在初始检索结果中，相关文档是类似的， 而不相关文档则相对松散，因此可以首先对初始检索结果中前m 篇文档进行聚 类，m 一般取2 0 3 0 ，然后将每一类文档的相似度相加，在相似度之和最高的 一类中取出前n 篇文档来进行反馈。 同时，在初始检索结果中，文档相关的概率实际上是随着文档相关度的下 降而降低的。因此，p e d r oa m o 等人认为，对初始查询检索出的前n 篇文档做 同样的处理，可能会导致一部分信息的损失：即初始查询中相关度的排序关系 没有利用。他们提出了利用平滑函数来对不同排位的文档进行加权的方法，按 照随排序序数递增则权重递减，以及所有权重之和等于l 的两个原则，设计了 几个平滑函数。这样相关概率更高的文档就能在反馈中发挥更大的作用【l9 1 。 t l a ma d e s i n a 等人认为，摘要能够更好地反映文档的内容，去除更多的干 扰信息。因此，他们提出了首先对相关文档自动生成摘要，然后利用摘要进行 反馈的方法，从而对查询进行优化。这种方法与自动生成摘要的性能有很大关 系，如果生成摘要时关键词的选取也是根据关键词的区分度，那么这种方法与 直接按照权重来选取关键词的方法没有太大的差别【2 。 x u 和c r o f t 提出了局部上下文分析方法( l o c a lc o n t e x ta n a l y s i s ，简称l c a ) 【2 。它在整体上是一种局部分析方法，但利用全局分析的词共同出现频率的思 想避免了向原查询加入不相关的词。利用关键词之间的共现信息来选取扩展词 能够取得更好的扩展效果。局部上下文分析的应用效果仍然高度依赖于初次检 索的结果。如果初次检索返回的多数文档与原查询无关，该方法仍会将大量无 关的词加入新查询，从而大大降低最终的检索精度。 尽管信息检索技术取得了一定进步，但g o r d o n 等【2 2 】研究指出搜索引擎的 性能仍然不能达到用户的期望。由于检索数据集的巨大，影响检索效率因素的 多样性和复杂性，上述优化技术在实际应用中效果并不理想。遗传算法的引入 为信息检索问题提供了新的解决途径。 1 4 研究意义 查询优化是近年来在w e b 信息检索领域为解决查询关键词和文档关键词 的不匹配问题所研究的中心问题。本课题的研究目的在于得出一个能够确切表 6 达用户需求的查询向量。本文通过有效利用相关文档集合对初始查询进行扩展， 并利用遗传算法为扩展后的查询选择优化的权重，使得用户采用该查询向量进 行查询时，能够获得真正需要的信息。本课题的研究对于提高w e b 信息检索的 查全率和查准率，促进w e b 信息检索的发展具有重要意义。 1 5 论文主要内容与结构 全文共分五章，各章主要内容分述如下： 第一章是绪论。说明了论文的研究背景，对信息检索和查询优化技术的研 究现状进行了概述，给出全文的整体架构和各章的研究内容。 第二章是信息检索的一般流程和基本模型，以及信息检索中查询优化技术 的基本理论和方法。对几种经典的查询优化方法进行了全面的分析和比较，总 结了其优点以及不足之处。 第三章是遗传算法的基本概念和实现步骤，对遗传算法及其在信息检索中 的应用进行分析研究，表明了遗传算法用来解决查询优化问题的有效性。 第四章将遗传算法与局部共现的查询扩展方法相结合，首先使用局部共现 方法对查询进行扩展，再使用遗传算法对扩展后的查询进行权重分配，进一步 优化查询。并对遗传算法中的遗传操作算子和适应度函数进行分析和改进，提 出了一种新的基于局部共现和遗传算法的查询优化方法。利用c i s i 测试集对算 法进行测试，实验结果证明新方法达到了良好的效果。 第五章是总结与展望。主要对论文的研究工作进行了总结，指出其局限性， 并对今后进一步研究工作进行了展望。 7 2 1 信息检索的发展 第二章信息检索与查询优化 随着科学技术的发展，尤其是计算机的应用，信息检索经历了手工检索、 到机械检索再到计算机化检索的过程【2 3 1 。2 0 世纪中叶以前，信息存储和传播主 要是以纸质介质为载体，信息检索活动也围绕着文献的获取和控制展开。随着 计算机和网络的出现，促进了信息检索科学的发展，使用信息检索工具来查找 自己所需信息的人们越来越多，特别是网络信息检索，它已成为了继电子邮件 服务之后的网络第二大服务【2 4 1 。 2 1 1 手工检索 手工检索是指通过手工的方式利用检索工具来处理和查找文献的过程，如 利用文摘、索引、目录、参考工具书等。它是一种传统而又基础的检索方式。 手工检索因其几乎不需要特殊设备，检索方法简单、灵活，而且用户可以 边查边思考，随时修改检索策略，无检索经费或检索费用较低等优点，而今在 某些领域仍然在使用。 但是，利用手工检索往往检索速度慢，费时较多，特别是进行专题检索和 回溯检索时需要查阅大量工具书，效率低下。在进行复杂问题的多途径检索时， 需要反复查找若干检索工具，查全率也较低。 目前手工检索工具在所有的检索工具中仍占有相当大的比重，某些学科和 科研课题的检索利用手工检索也较为方便。 2 1 2 计算机信息检索 随着计算机技术、通信技术和高密度存储技术的迅猛发展，利用计算机进 行信息检索己成为人们获取文献信息的重要手段。计算机信息检索能够跨越时 空，在短时间内查阅各种数据库，而且大多数检索系统数据库中的信息更新速 度很快，检索者随时可以检索到所需的最新信息资源。计算机信息检索经历了 脱机批处理、联机检索、光盘检索与网络化检索四个阶段。 ( 1 ) 脱机批处理检索 2 0 世纪5 0 年代中期至6 0 年代中后期是信息检索的脱机批处理阶段。当时， 计算机硬件发展很快，但还没有连接通讯网，也没有远程终端装置，不能提供 问答服务的检索方式，只能进行现刊文献的定题检索和过期文献的追溯检索， 同时利用计算机编辑出版检索性刊物。所谓脱机批处理方式，是指定期由专职 检索人员把许多用户的检索提问汇总到一起，进行批量检索，然后把检索结果 通知各个用户，用户不直接接触计算机。 8 与以前的手工检索相比，脱机批处理检索有许多优点：它能同时进行多项 检索；对复杂的检索词也具有处理能力；脱机批处理具有一次输入作业，生产 多种输出的多种服务能力。因此，在生产普通印刷索引、专题书目、回溯检索 和定题检索服务等方面得到广泛应用。 但是，它也有以下不足之处：缺乏与用户的交互过程；检索结果获得不及 时；信息需求和检索结果之间存在一定误差；脱机批处理检索不能在检索的同 时修改检索策略，用户必须事先把可能的途径都考虑周全等。这些缺点限制了 脱机批处理检索的发展。 ( 2 ) 联机检索 2 0 世纪7 0 年代计算机分时系统的出现，通信技术的改进，使得多终端、 远距离两地检索信息的技术得以推广，计算机检索技术从脱机阶段进入联机信 息检索时期。所谓联机检索，就是用户使用终端设备，通过通信线路与中央计 算机连接，直接与计算机对话进行检索，结果由终端输出。 联机检索无需委托，直接面向最终用户，在检索过程中是“人机对话方 式，具有很强的交互能力，而且能及时取得检索结果，但是检索指令复杂，需 要依赖专业检索人员。 ( 3 ) 光盘检索 c d r o m 光盘是2 0 世纪8 0 年代在计算机技术、激光技术等现代新科技成 果的基础上发展起来的新型电子出版物。其具有信息存取密度高、容量大、读 取速度快、信息类型多、保存时间长、成本低等优点。 利用光盘检索系统费用大大低于联机检索，利用c d r o m 存储信息方便、 易于携带，除可提供追溯检索、定题服务外，还可用于“自建库”和做联机检 索前预处理。 ( 4 ) 网络化联机检索 联机检索和光盘检索为我们提供了大量的信息资源，但各自又都有着或多 或少的缺点。例如，联机检索费用昂贵，指令复杂，而光盘检索得到的信息又 不十分及时等。因此，极有必要产生一种新型的信息检索方式。在信息爆炸的 当今社会，单个计算机所能完成的工作和所存储的信息都极为有限，而把单机 连起来的计算机网络则能在局部或更大范围内实现通信和信息共享。网络联机 信息检索是联机信息检索的高级阶段，它的实现可以使人们在很短的时间里查 遍全球的信息资料，使人类实现信息资源共享成为可能。因特网的迅速发展和 广泛应用，改变了计算机信息检索的方式和方法，将信息检索拓展到一个更广 阔的领域。目前对网络信息的检索主要有两种检索形式：目录式检索( 也称主题 指南) 和搜索引擎。网络使计算机信息检索技术进入了一个崭新的发展阶段，而 网络信息检索又使得网上信息资源利用率提高，信息组织更为有序和高效。 9 2 2 信息检索系统的基本模型 信息检索系统一般由用户界面、搜索引擎和文档数据库三个主要部分组成。 其中，用户界面是用户与信息检索系统之间的接口，主要用来接受用户的查询， 根据用户的输入生成查询表达式，并将查询表达式送往搜索引擎。搜索引擎是 信息检索的关键部份，它主要用来查找信息，根据查询表达式在信息检索系统 中的文档数据库中查找相关的文档。文档数据库主要用于存储文档，在大型的 信息检索系统中，文档数据库一般存放在后台数据库中。信息检索的过程就是 找到与查询最相关的文档的过程。 在信息检索系统中，信息获取方式的优劣很大程度取决于信息检索模型的 建立方法。目前，大多数的信息检索系统使用布尔模型、向量空间模型、概率 模型、神经网络模型、聚类模型、基于规则的模型、模糊模型和语义模型等。 下面介绍几种典型的信息检索模型【25 j 【2 6 j ：布尔模型、向量空间模型和概率模型， 探讨它们是如何来获取信息的，并对它们的优缺点进行分析和比较。 2 2 1 布尔模型 布尔模型( b o o l e a n ) 是比较简单通用的一种检索模型，它建立在经典的集合 论和布尔代数的基础上。从最早的文献检索系统，到现在最流行的商业搜索引 擎，都有他的用武之地。它将文档表示成布尔表达式，然后再通过与用户的查 询表达式进行逻辑比较来检索相关文档。在布尔模型中，文档关键词的权重只 有0 和l 两种，分别表示文档中不包含该关键词和包含该关键词。在布尔模型 中，一篇文档通过关键词的集合来表示，这些关键词都来自一个词典。在查询 与文档匹配的过程中，主要看该文档中的词条是否满足查询的条件。若满足则 认为这篇文档与查询是相关的，若不满足则认为是不相关的。用户查询条件是 由标准逻辑操作符a n d 、o r 和n o t 将关键词连接起来构成布尔表达式。 布尔模型实现起来比较容易，而且计算的代价相对较少。布尔检索模型适 用于经验丰富的用户，通过关键词的组合，能够生成复杂的布尔表达式，精确 的找到相关文档。同时，布尔检索还不仅仅局限于文档的内容，文档的其他属 性，如作者，出版者等信息，也可以成为检索的限制条件，大量的文献检索系 统都采用了这种模式。 布尔模型的精确检索功能，恰恰是其一大缺陷。当用户对需求领域比较陌 生时，很难掌握布尔操作符的使用方法，很难将一个查询公式化。另外， 由 于布尔模型获取文档的机制是基于二进制的，当一篇文档满足查询时则认为这 篇文档与查询问的相似度为1 ，不满足查询时则认为相似度为0 。因此，不能在 查询中说明关键词的相对重要性，查询中的关键词是被对等看待的。也不能将 文档按照与查询的相关性来排序，因此经常会出现相关度高的文档却排序靠后 1 0 的现象，当文档的数目增多，查询者就很难从检索出的大量文档中选择出自己 最需要的。 2 2 2 向量空间模型 向量空间模型( v s m ) 是近年来使用较多且效果较好的一种信息检索模型。 向量空间模型是s a l t o n 等人于6 0 年代末期首先提出的，在著名的s m a r t 系统 中得到成功的应用。在向量空间模型中，将文档和查询表示为由一组正交基词 向量构成的向量，通过比较两个向量，计算它们之间的相似度，根据求得的相 似度大小对检索结果进行排序。为了避免布尔模型中使用二进制权重的局限性， 向量模型中提出了部份匹配的方法，仅仅考虑文档与查询问部分匹配。在查询 和文档中的关键词都不使用二进制权重，而使用词条权重，去计算每篇文档与 查询问的相似度，权重在o 到l 之间。 在向量空间模型中，信息检索系统如果涉及到n 个关键词，则建立n 维的 向量空间，每一维代表不同的关键词。文档以及查询都通过该空间的向量来表 示。向量是一个n 元组，其中的每个坐标都通过对应关键词的权重来表示。为 了将文档划分成向量中的这些元素，一般需要采取以下步骤： ( 1 ) 分词 这一步骤对于需要分词的语言，比如中文，是必须的。由于中文语义丰富， 表现灵活，给分词带来很大难度。分词的质量决定了检索的质量，分词的粒度 对检索也有一定的影响，粒度太大，某些长度较小的词可能会检索不到；粒度 太小，索引开销则会增大，查准率也有可能下降。而对于英文等西方语言来说， 词与词之间有明显的分界符，则这一步骤可以省略。 ( 2 ) 去停用词 有些词的使用频率很高，几乎会在所有文档中反复出现，这些词不会对检 索有任何帮助，反而会占用大量的空间。停用词指文档中出现的连词，介词， 冠词等并无太大意义的词。例如在英文中常用的停用词有t h e ，a ，i t 等。对文 档处理时应把这些词去掉