（计算机应用技术专业论文）中文信息检索中相关算法的研究.pdf

辽宁科技大学硕士论戈 摘要 摘要 随着网络技术的发展，网络上电子可读文本的f 益增加，呈指数膨胀的文本 信息资源，使得如何准确有效地获取用户所需要的信息成为人们关注的热点，促 进了文本处理领域的形成和发展。自动收集和整理所需要的各类信怠成为信息产 业面临新的挑战和新的发展契机，而信息检索技术是解决这些问题的关键。根据 不同的应用背景和不同的使用目的，信息检索技术已经演化为信息检索、信息过 滤、信息分类、文本摘要，和问题回答等方向。 由于信息主要是以文本形式表示，本文主要讨论中文文本检索和相关应用的 处理授术。文本检索主要研究的对象是大规模、非结构化的真实文本，进行文本 分类、文本检索、文本过滤和文本摘要等方面处理，以满足用户的信息需求。 本文主要讨论的问题包括：提高文本检索效率的索引文件系统和提高系统精 度的相关反馈技术等。 文本分类既可以作为独立应用系统，也可以作为检索系统的组件用以提高系 统的效率。作者建议在检索系统中采用层次分类方法。 关键词：文本检索，文本过滤，文本分类，文本摘要，相关反馈 辽宁科技大学硕士论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g y , t h en u m b e ro fo n l i n et e x t si s i n c r e a s i n ga ta ne x p o n e n t i a ls p e e d h o wt oa c q u i r eu s e f u li n f o r m a t i o na c c u r a t e l ya n d e f f i c i e n t l yb e c o m e st h ef o c u so fr e s e a r c h e r s ，w h i c ha c c e l e r a t e st h ed e v e l o p m e n to ft e x t p r o c e s s i n g a u t o m a t i cc o l l e c t i o na n dl i q u i d a t i o no fr e q u i r e d i n f o r m a t i o nb e c o m ea c h a l l e n g ea n dac h a n c eo fd e v e l o p m e n t a n di n t b r m a t i o nr e t r i e v a lt e c h n o l o g yi st h ek e y t ot h es o l u t i o no ft h e s ep r o b l e m s a c c o r d i n gt od i f f e r e n tb a c k g r o u n d sa n da p p l i c a t i o n p u r p o s e ，i n f o r m a t i o n r e t r i e v a lt e c h n o l o g yh a se v o l v e di n t os e v e r a ls u b a r e a s ：t e x t r e t r i e v a l ，t e x tf i l t e r i n g ，t e x tc a t e g o r i z a t i o n ，t e x ta b s t r a c t i o n ，a n dq u e s t i o na n s w e r i n g s y s t e m s ，e t c s i n c et h em a j o rf o r mo fi n f o r m a t i o ni st e x t w ed i s c u s sc h i n e s et e x ti n f o r m a t i o n r e t r i e v a la n dr e l e v a n ti s s u e si n t h i st h e s i s t h em a i no b j e c to ft e x tr e t r i e v a ls t u d yi s l a r g e s c a l e 、n o n s t r u c t u r e dr e a l w o r l dt e x t sf o rc a t e g o r i z a t i o n ，r e t r i e v a l ，f i l t e r i n g ，a n d a b s t r a c t i o nt om e e tu s e r sr e q u i r e m e n t i s s u e sd i s c u s s e di nt h i st h e s i si n c l u d ei n d e x i n gt e c h n o l o g yf o ri m p r o v i n gr e t r i e v a l e f f i c i e n c ya n dr e l e v a n c ef e e d b a c kf o ri m p r o v i n gs y s t e mp r e c i s i o n t e x tc a t e g o r i z a t i o nc a nb e u s e da s i n d e p e n d e n ta p p l i c a t i o ns y s t e m a n da sa c o m p o n e n tf o ra ni n f o r m a t i o nr e t r i e v a ls y s t e mf o ro ri m p r o v i n gr e t r i e v a le f f i c i e n c y ，t h e p r o p o s et h a tah i e r a r c h i c a lm e t h o df o rc h i n e s et e x tc a t e g o r i z a t i o nb eu s e di nar e t r i e v a l s y s t e m k e yw o r d s ：t e x tr e t r i e v a l ，t e x tf i l t e r i n g ，t e x tc a t e g o r i z a t i o n ，t e x ta b s t r a c t i o n r e l e v a n c ef e e d b a c k i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得辽宁科技大学或其它教育机构的学位或证书而使用过的材料，与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 签名：壑骜一目期：迎2 己! 擎 关于论文使用授权的说明 本人完全了解辽宁科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：聋聱导师繇垫鱼堡日眦血。； 辽宁# 技犬学硬士论文 第一章前言 第一章前言 l 。l 文本检索的背景 由于以因特网为主体的信息高速公路的不断普及和发鼹，信息技术已经渗透到 我们社会生活的各个角落，正以前所未有的速度和能力改变着我们的生活和工作方 式，我们真正处于一个“信息爆炸”的时代。一方颐，因特网上面蕴涵的海量信息远 远超过人们的想象；另一方呵，箍对信息的汪洋大海，人们往往感到束手无策，无 所适丛，出现所谓的“信息过载”帮“信息迷向”的现象。于是一个极富挑战性的 课题：如何帮助人们有效地选择和利用所感兴趣的信息，尽量易4 除不相关的信息， 同时保证人们在信息选择方面的个人隐私权利? 成为学术界和企业界所十分关注 的焦点。 随着在线文本的目益增多，其中包括新闻、电子杂志、电子邮件、技术报告、 文档以及潮上图书馆。如此众多的信息，仅仅依靠大脑柬收集和整理所需要的信息 显然是不够的。所以，自动收集和整理所需要的各类信息成为信息产业两临瓤的挑 战和新的发展契机。根据不同的应用背景和不同的使用目的，信息处理技术已经演 化为信怠检索、信息过滤、信息分类、问题回答等方向。 由于强前网上信息的表现形式大多数为文本，而且文本也是广大雳户所习惯接 受的形式。因此我们在下面主要讨论中文文本检索和相关应用的处理技术。文本处 理迅速成为业界的热点，各种相应的国际学术会议不断召开，已成为计算语言学领 域新的增长点。 1 2 信息检索的研究现状 随羞网络上电子可读文本的目益增加，人们头脑的很大部分的信息来自网络， 可是呈指数膨胀的文本信息资源，引起了人的加工处理的极大困难，如何准确有效 遗获取用户所需要的信息? 成为人们关注的热点，促进了文本处理领域的形成和发 展。它主要研究的对象是大媲模、非结构化的真实文本，进行文本分类、文本检索、 文本过滤和文本摘要等方面处理，以满足用户的信息需求。典型的应用例子有w w w 的信息搜索引擎，如g o o g l e ，y a h o o ，a l t a v i s t a ，e x c i t e ，l y c o s 等，中文搜索引擎有b a i d u ， s o h u 。y e a h 等。这些信息检索系统般通过收集系统在全球各个角落的w w w 服务 器中收集各类信息，建立索日 服务器，帮助用户快速准确缝查找所需的信息。在文 本分类方面，美国白宫的电子邮件自动分类系统将每天收到的邮件分为耀应的各 一1 一 辽宁科技大学硕士论文第一章前言 类，如外交、国防、环保、税收等方商，以便由相应的人员进行答复。 在著名的国际文本检索会议( t e x tr e t r i e v a lc o n f e r e n c e ，t r e c ) t ，有两个最 重要的研究方向1 1 - 4 ：r o u t i n gt a s k 和a dh o ct a s k 。其热点问题包括从早期的文本 检索、文本过滤、到当前的问题回答( 问答系统，q u e s t i o na n s w e r i n gs y s t e m ) 。 文本检索就是根据用户提出的具体查询，在大量相对稳定的文本源中，检索出 符合用户查询条件的文本，并按其满足查询的程度排序列出。文本检索技术的发展 已经有四十多年的历史，取得了很大的成就，产生了大批实用的检索系统，积累了 许多成熟的技术。 1 9 9 2 年，n i s t ( 美国国家标准和技术研究所) 与d a r p a 联合赞助了每年一次 的t r e c ，对于文本检索和文本过滤和问题回答等专题倾注了极大的热忱。 目前随着因特网的迅速发展，需求的不断增加，文本检索以及相关技术方面， 取得了长足的进展，成为信息产业新的增长点。b e l k i n 和c r o f t 阐述了“用户角色” ( 包括用户兴趣及兴趣表示) 在文本过滤系统中的地位及其在交互巾的作用 5 1 = y a n g a n dc h u t e 实现了基于实例和最小平方利益的线性模型文本分类器【6 】。一些文本过滤 系统也相继问世。如斯坦福大学( 1 9 9 5 ) s i f t 系统的1 7 ，卡内基梅隆大学的等 n e w s w e e d e r i8 1 。还有s m a r t , i n f o s c o p e ，g r o u p l e n 等叫“。 信息存储与检索系统，简称信息检索系统，是一个信息存储、检索、和维护系 统。它并不告知用户其所查询的信息，而是告知用户他所查询的有关文献是否存在 以及所在何处【l 。这里，信息可以是文本、图像、声音、影像以及其它多媒体对象。 尽管信息对象的形式多种多样，由于文本信息的重要性，以及技术发展的限制，信 息检索实际上仍局限于对文本文献的检索。所以，信息检索有时也被称为文献检索 ( d o c u m e n tr e t r i e v a l ) 或文本检索( t e x tr e t r i e v a l ) 。如果我们以黑箱的形式描述一 个基本的信息检索系统，将会得到如图1 1 所示的三个组成部分【1 3j ：输入、处理器、 和输出。尽管这样划分有些过于简化，但它是我们进一步研究信息检索系统的基础。 反馈 输入 图11典型的信息检索系统 f i g 1 1ac l a s s i c a li n f o r m a t i o nr e t r i e v a ls y s t e m 2 一 输出 辽宁科技大学硕士论文第一章前言 为便于描述，我们首先定义几个术浯。用户查询是用户信息需求的描述形式， 即用户输入到信息检索系统的奁询语句。文献是一个数据对象，尽管它可以有各种 形式( 图形、声音等) ，但通常是文本形式。信息检索系统将用户查询与存储在系 统内的文献进行匹配。通常文献库并不赢接存贮在信息检索系统内，而是以某种替 代形式保存在系统中。这种替代形式称为文献表示。这样做的主要目的是提高效率， 印缩小文献空间，减少查找时间。由于在信息检索系统中通常处理的都是文献表示， 所以，我们经常混用文献和文献表示。 我们首先考察输入端。这里的问题是如何将文献和用户查询表示为适合计算机 自动检索的形式。需要强调指出的是，几乎所有基于计算机的检索系统都只保存文 献的表示形式，丽不是文献本身。即，在系统对文献进行处理并抽取了其表示形式 后，便可以屏弃文献本身。文献的表示形式可以是从文献中抽取出来的一串重要词 表，或其它形式( 如加权向量) 。 对于联机用户，他可以在检索过程中不断修改检索请求，以改善后续的检索结 果。这一过程通常称之为反馈。目前，许多实用检索系统都其有相关反馈的处理功 能。 下一部分是处理器，它是检索系统中的检索处理部分，用于对文献信息和用户 查询进行特定的处理( 组织、存储、查找、更新等) 。 最后是输出部分。它通常是一组文献的标题、标号、或摘要，并具有指向文献 物理位置的指针。 信息检索系统必须支持一些基本操作，如文献的录入、修改、删除、及查找等， 并在用户需要时将文献提交给用户。各种信息检索系统对于上述操作的实现方法有 很大的不同，因此我们在下一节中简要介绍各种信息检索系统。我们根据系统的概 念模型、文件结构、及各种操作的实现方式将信息检索系统所涉及的备个侧面列表 如下： 表1 1 信息检索系统的分类 ! ! ! ! ：! 生! ! ! ! 也! ! 巫竺! ! l ! ! ! ! 巴! j ! ! ：! ! ! 堡：! ! ! z ! ! ! 翌! 概念模型文件结构查询操挥项操作 文献操作 。3 辽宁科技大学硕士论文第一章前言 各种具体的信息检索系统可以根据上述的各项的选择而进行分类。例如：f r a k e s 等 人的c 朋阪l o g 系统。其各项选择如下表1 2 所示： 从另一个角度来看，对于每个侧面的选择，系统设计人员必须根据系统要求对 其中各项进行取舍。下面我们将进一步讨论这些项。 表1 2c a t a l o g 系统的各个侧面 t a b j e12f a c e t sj 1 3c a t a i ，o g 侧匿项 文件结构 概念模型 查询操作 项操作 文献操作 倒排文件 布尔模型 分析、布尔 禁用词、词汇处理 分析、显示、摊序、标识指派 1 2 。1 摄念模型 在上述的信息检索系统分类方式中，最具概括性的侯l 面是概念模型。信怠检索 概念模型的分类方法有多种，捡索技术可分为精确匹配和非精确匹配。精确匹配类 包括文本模式匹配和布尔搜索技术。在非精确匹配类中包含概率、向量空间、和聚 类等检索技术。 目前的检索系统绝大多数是基予布尔模型和文本模式匹配技术的。后者只适用 于较小的文献集。这方面的一个例子是u n i x 中的g r e p 工具。而用于检索大文献集 的检索系统几乎都是基于布尔模型的。在稚尔检索系统中，文献用组关键词来表 示，并且通常存储在倒排文件中。尽管布尔系统受到很多批评，但要改进它却很困 难。对布尔模型的较好的改进方案是s a l t o n 等人提出的扩展布尔模型【l “。 1 2 2 文件结构 设计信息检索系统的重要决策之一是对文献库采用倪种文件结构。如表1 1 所 示，信息检索系统的各种文件结构有平面文件、倒排文件、特征文件、p a t 树、和 图。尽管理论上可以将文件结构存储在内存中，但在实践中，由于文件往往规模很 大，信息检索系统的文献库般都存储在磁盘上。 在平面文件结构中，文件中可存储一篇或多篇文本形式的文献。对平面文件的 查找通常采用文本模式匹配的方式。例如在u n i x 系统中，我们可以用g r e p 工具在 菜一目录下查找包含某一特定字符串的所有文件。 倒排文传是一种索引文件。倒摊文件结构中的各个字段通常包括关键词、文献 一d 一 辽宁科技大学硕士论文 第一章前言 标识、和段落标识。关键词是用于描述文献的索引项( 项、特征项) ，文献标谚 是 表示文献的唯一的标识符，段落标识是用于表示该关键词来自哪个文献中段落的唯 一名称。在有些系统中还包括所在句子的信息。对倒排文件的检索是通过在文件中 查找查询项完成的。 特征文件包含特征用于表示文献的位串。构造特征的方法有多种。一般情况 下，将文献划分为一些逻辑块，这些块用一组不同的重要词汇来表示。其中的每个 词汇都通过散列形成一个特征，它是有0 和1 组成的位串。通过或运算将一块中的 所以特征并置，形成块特征。将文献的所以块特征连接起来构成文献特征。对特征 文件的检索是通过比较查询特征和文献特征进行的。 p a t 树( p a t r i c i a 树) 方法将整个文本看作是一个单一的字符串，称为半无限长字 符串( s i s t r i n g ) ，并将用户查询与文本进行快速匹配。 图，也称网络，是由弧连接起来的节点集合构成的。它能够以多种形式来表示 文献。例如，语义网可以用来表示其它方法很难表示的文献内语义关系。但由于它 涉及的手工操作过多，目前此方法尚不实用。 1 2 3 查询操作 查询是用户信息需求的描述形式，即用户输入到信息检索系统的查询语句。对 查询操作的结果显然仍是查询类型。对查询的操作是检索系统的基本功能之一。对 查询的公共操作之一是分析操作，即将查询分解成它的构成元素。例如，对于布尔 检索系统，必须将查询分解为它的构成项以及相应的布尔运算符，并根据这些项进 行检索，然后根据布尔运算符确定符合用户查询的文献集。 相关反馈是一种查询修改技术，它利用以前的检索信息修改当前查询，以调整 检索结果。例如，可以从己检索到的相关文献中提取特征项加入到查询中。实验证 明，利用相关反馈技术可以大大提高检索系统的性能。 查询修改的另一种方法是查询扩展，即将与查询项相关的特征项加入查询中。 这种方法在许多实用系统中使用。 1 2 4 项操作 项( t e r m ) 在信息检索系统中，是指当文献内容被简单地看作是它所包含的基 本语言单位构成的集合时，这些基本语言单位称为项或特征项。对于项的操作有词 汇处理( 如西方语言中的词干提取和单词截取，中文的分词) 、项的加权、禁用词 处理、和同义词处理等。词汇处理对于英文包含词干提取( 删除前缀、后缀等) 和 单词截取( 将单词中的部分用通配符替代，如t r u n c a t ? 可与t r u n c a t e 、t r u n c a t e d 、 5 辽宁科技大学硕士论文第一章前言 t r u n c a t i o n 等匹配) 。对于中文系统，词汇处理指的是词汇的切分，即分词，这是由 于汉语的语句中无词汇分割符所导致的。词汇的扩展可以通过同义词典来进行。它 是查询扩展的基本方法之一。禁用词表是一组对于检索系统来说无索引意义的词。 从索引中删去禁用词可以大大缩小索引空间。检索系统对每个可能的索引项都与禁 用词表进行比较，如果发现它是禁用词则将其删除。 特征项加权是指将一个数值赋给索引项或查询项。该数值是根据该项的统计信 息得出的，例如该项在文献中的出现频率、在文献集中的出现频率等。 1 2 5 文献操作 文献是信息检索系统的主体，对于文献有许多种操作。在许多信息检索系统中， 新加入系统的文献必须被赋予一个唯一的标识符，并通过分析程序将文献分割为段 落和特征项，同时为各个段落赋予段落标识。一旦文献入库，人们有时希望屏蔽掉 某些文献或某些段落，以便于检索和显示。例如，对于某一特定的查询，用户可能 希望只检索标题和摘要段，或者在检索到的文献中只希望阅读文献的标题和作者名 称。用户可能还希望将检索结果依某种方式排序，如按作者排序。 文献操作的另一重要方面是文献的显示。信息检索系统、以及其它信息系统的用户 界面对于系统的成功与否至关重要。文献的显示还应包括文献打印。 1 2 6 信息检索系统的目标 检索系统的基本目标是使用户查找所需的信息的开销最小化。用户的查询开销 指的是从用户输入查询语句到开始阅读有关文献的全过程所用的时间( 包括查询生 成、检索、查询结果浏览、阅读非相关文献等) 。检索系统的成功与否颇具主观性， 它依赖于用户需要的信息，以及用户对查询开销的容忍程度。在某些情况下，用户 需要的信息可以定义为系统中所有与用户需求相关的信息；而在其它场合，又可定 义为系统中足以完成某一任务所需的信息。后一莘中情形的一个例子是：对于要写研 究报告的学生，只需查到足够的参考文献，即可满足教师对他的要求；他并不需要 把所有有关的参考文献全部找到。 在信息检索中，“相关文献”用于表示包含所需信息的文献。而在现实中，相关 性的概念却无法用二元分类来定义，它是一个连续函数。从用户的观点看，相关和 需要是同义词；而从系统的角度看，文献可能与查询语句相关，但并非用户所需( 例 如，用户已经了解其中的信息) 。 6 辽宁科技大学硕士论文 第一章前言 1 2 7 信息检索系统的评估 评价检索系统的两个主要指标是查准率( p r e c i s i o n ) 和查全率( r e c a l l ) 。当用户 将自己的查询提交给系统后，整个文献库在逻辑上被划分为四部分，如图1 2 所示。 图1 2 在全部文献空i 司中的检索效果 f i g 1 2 r e t r i e v a lr e s u l ti nt h ew h o l ed o c u m e n ts p a c e 文献库中包含与用户需求相关的和不相关的文献，系统根据用户提交的查询语 句进行检索，所检索到的文献集既包含相关文献，也包含不相关文献。查准率和查 全率的定义如下： 查准率= 蓑器鬻篙 查全率= 蒜裂畿 查准率从一个方面描述了检索系统的查询开销。如果某次查询的查准率是8 5 ， 则1 5 的文献是不相关文献，但用户浏览其中的内容以确定它们是否所包含所需的 信息。查全率是检索系统查找用户所需信息能力的标志。查全率是一个非常重要的 概念，但从其分母可以看出，在实际系统中它是无法计算的。图1 3 和1 4 分别是 理想的和实际能够得到的查准率查全率关系图。 对于实际系统，系统的索引速度( 即文献录入时构造索引的速度) 和检索速度 也是重要指标。尽管索引文件的构造方法有多种，如d b m s 中采用的各种方法，在 信息检索系统中较为流行的方法是倒排文件系统。本文第四章介绍了一个快速倒排 文件系统。 7 一 辽宁科技大学硕士论文第一章前言 浒 姆 船 瓣 樊 制 图1 3 理想的查准率，查全率图示 f i g 。11 3i d e a lp r e c i s i o n r e c a l ld i a g r a m 0020 40 6 0 81 商全率 圈1 4 实际的查准率查全率图示 f i g 。1 4a c m a lp r e c i s i o n r e c a l ld i a g r a m 由图1 3 和1 4 可以看出，实际系统的性能距理想情形楣差甚远。事实上，在 t r e c 测试中，绝大多数系统的平均查准率( 直观上讲，即图中曲线下面的面积) 都在0 1 至0 5 之间，最好的测试结果平均查准率也不到o 6 。根据本人的直观估计， 当前i n t e r n e t 上的著名检索工具，如y a h o o ，g o o g l e ，e x c i t e ，w e b c r a w l e r 等，它们的 平均查准率小予o 2 。这说明信息检索系统的性能还有很大的提高空间，僵提高系 统性能是非常困难的。 影响信息检索系统的性能关键是： ( 1 ) 文献的表示形式能否反映文献的内容。 ( 2 ) 查询的表示形式能否反映用户需求。 ( 3 ) 用户查询与文献表示之闯的相似度计算方法能否反映它们之间的符合程 度。 8 - 1 9 8 7 6 5 4 3 2 l 0 o o o o o o 0 o o 1 9 8 7 6 5 哇3 2 ，o o 0 0 o o 0 o 0 o 辽宁科技大学硕士论文 第一章前 言 这是因为，对于大文献集，出予检索速度的限制，我们不可能在检索时扫描整 个文献集进行查找。这就要求我们必须从各个文献中摘要拙取部分信息作为文献内 容的表示形式。显然，在信息抽取的过程中，必然要丢失文献的部分内容信息。此 外，由于语言本身的表达能力和用户对语言的操纵能力的限制，用户查询通常也不 能完全准确地表达用户的信息需求( 有时用户需求甚至是不确定黔) 。瓶检索过程 是通过计算用，、查询与文献表示之问的相似度进行的。这些因素使我们无论采用何 种方案，都不可能完全准确地计算出用户需求与文献之间的符合程度( 即，图1 3 所示的理想目标是不可能达到的) 。提高系统性能的困难主要原因就在于此。我们 所能做的是尽可能接近上述三颈的要求。 1 3 本文的组织结构 本文主要讨论的问题包括三个方面：提高文本检索效率的相关技术、中文文本 处理的特有问题中文分词技术、和问题回答系统技术。本文的基本结构如下： 第一章主要是对信息检索军n 相关闯题箍要介绍。 第二章主要介绍当前较为流行的三种文本表示模型，即布尔模型、向量空间模 型、和概率模型。它们是开发应用系统的理论基础。 第三章讨论裣索系统的基本结构问题，捕述我们构造的一个实验系统，为第谣 章的讨论建立基础。 第四章讨论检索系统的效率闯题。分类系统既可以作为独立应用系统，也可以 作为检索系统的组件提高系统的效率。检索系统的索引速度和检索速度也是重要指 标。尽管构造索引文件有多种方法，如d b m s 中流行的b 树方法，在信息检索系统 中较为流行的方法是倒排文件系统。本章介绍了两种提高分类系统效率的方法和一 个快速倒排文 牛系统的实现。 第五章提出了一种使用相关反馈来实现查询扩展以提高检索系统精度。当系 统确定了其索引形式和相似度的计算方法后，系统性能的提高，主要依赖于查询 的表示和调整。本章主要介绍如何通过相关反馈来修改查询，以提高系统性能。 第六章是本文的总结，提出来束进一步的辛慝关工作。 9 辽宁科技大学硕士论又 第二章信息检索模型 第二章信息检索模型 在信息榆索的发展过程中，人们提出了各式各样的检索模型。目前，较为广泛 应用的有布尔模型、概率模型、和向量空削模型。本章简要介绍布尔模型和概率模 型，着重介缁向量空间模型。 2 1 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 向量空间模型是f _ = is a l t o n 及其学生们在六十年代末到七十年代初期提出并发展 起来的m 】。这一模型将给定的文本( 文章、查询、或文章中的一段等) 转换成一个 维数很高的向量。它的最大特点是可以方便地计算出任意两个向量的近似程度，即 向量所对应的文本问的相似性。用信息检索的术语来说，如果两个向量是相近的， 则其对应的文本是语义相关的。将所有文献和查询以向量形式表示，则针对特定的 查询向量，比较它与所有文献向量的相似度，并依相似度将文献降序排序，这便是 现代信息检索系统中常用的方法。 s a l t o n 及其学生们还根据向量空间模型实现了s m a r t 系统。s m a r t 系统在过去 3 0 多年中，对信息检索的研究有非常重要的影响。信息检索的许多理论和技术( 如 自动索引、加权技术、相关反馈、文献聚类等) 是在s m a r t 上首先实现或测试的。 2 1 1 基本概念 、。f 面我们介绍向量空间模型的基本概念。 文献( d o c u m e n t ) ：泛指各种机器可读的记录，通常指一篇文章。 项( t e r m ) ：也称为索引项或特征项。当文献或查询的内容被简单地看作是 由它所包含的基本语言单位( 字、词、短语等) 构成的集合时，这些基本 语言单位统称为项。v s m 假定存在一个项的集合，于是文献和查询均可用 由项构成的向量来表示d = ( t l ，t 2 ，t 。) 。 项的权重( t e r mw e i g h t ) ：对于有n 个不同的项的系统，文献d = ( t l ，t 2 ，t 。) ， 项t k ( 1 s k 曼n ) 常常被赋予一个数值w k ，表示它在文献中的重要程度，称为 项t k 的权重。因此，我们一般用d = ( w l ，”2 ，w 。) 的形式表示文献。 向量空削模型：在有n 个不同的项h , t 2 ，t 。的系统中，给定文献 d = ( “l ，”2 ，w 。) ，由于t t , t 2 ，t 。互不相同，我们可以把它们看作是n 维欧 氏空间n 个举标，而把( w 一，w z ，w 。) 看作是n 维欧氏空间的向量。这样，我 们称d = ( w 1 ，”2 ，w 。) 为文献d 的向量表示。 一1 f ) 一 辽宁科技大学硕士论文 第二章信息捡索模型 相似度( s i m i l a r i t y ) ：两个文献d 】和d 2 的内容之间的相关程度( d e g r e eo f r e l e v a n c e ) 通常用相似度来表示。在向量空间模型中，我们可以借助于向量 之间的某种距离来表示文献削的相似度。通常用向量之间的内积或夹角余 弦来计算。设d l = ( w l l ，w 1 2 ，w l n ) ，d 2 = ( w z l ，w 2 2 ，w 2 n ) ，则 内积公式：s i m ( d l ，d 2 ) = w ，。w ：。 k = l w 一。 夹角余弦公式：s i m ( d l ，d 2 ) = c o s 0 2 1 等 兰- 、w 2 。w 蠢 如图2 1 所示。在实际系统中，一般多采用夹角余弦公式。 图2 1向量空间模型及文献间的相似度 f i g 21 v e c t o rs p a c em o d e la n ds i m il a r i t yb e t w e e nd o c u m e n t s 对于查询与文献问的相似度，也以同样方式计算。 2 1 2 项的选取 索引过程首先要从文献中抽取重要词汇和短语，然后把它们映射到项集中，并 进行权重计算。由于文献中不同词汇的出现频率随文章的内容和作者的习惯而不 同，因此，最初的索引系统都是从应用词频开始的。 l u h n 在他的一篇早期文章中指出 1 6 1 ，“词在文章中的出现频率为词的重要性提 供了有用的测度，进而对于具有特定重要性指标的词，它们在句子中的相对位置为 判定该句子的重要性提供了有用的测度。因此，句子的重要性应根据这两个测度的 1 1 辽宁科技大学硕士论文第二章 信息检索模型 组合来判断”。他的假设是，可以根据词频信息从文献中提取词或句子来表示文献。 事实上，如果将文献集中的词经过统计后按词频从高到低排列，则各个词的词 频特征符合z i p f 定律”1 ： 词频+ 序号= 常数 如图2 2 所示。 应用z i p f 定律，我们可以根据词频特征来估计词在文献中的重要性。早期的方 法是l u h n 给出的。 1 给定n 个文献的文献集 d i ，1 s i s n ) ，计算每个词t k 在各个文献d i 中的频率， 即文献内频率f r e q i k ，简记为t 氐。 2 计算每个词t k 在文献集中的总频率t o t a l f r e qk ， n t o t a l f r e q = t f , k j ；， 3 按t o t a l f r e q k 降序排序。选定一个合适的阈值u p p e r c u t o f f ，删去所有t o t a l f r e q k 在闽值以上的词，即删去常用词。 4 类似地，选定一个较小的阈值l o w e r c u t o f f ，删去所有t o t a l f r e q k 在阈值以下 的词，即删去罕用词。 5 将剩余的频率适中的词作为表示文献内容的索引项。 频率 图2 , 2 词频次序关系及常用词与罕用闻的确定 f i g 2 2 d e t e r m i n a t i o no ff r e q u e n c y o r d e rr e l a t i o na n dc o m m o n r a r ew o r d s 尽管这些思想在实际应用中显得有些粗糙，把高频词和低频词一刀切掉，会降 低检索的查准率和查全率，而且两个闽值的选取也比较困难；但是，这些思想为信 息检索系统中项的选取奠定了基础。有价值的索引项应具备以下特征： 一1 2 辽宁科技大学硕士论文第二章信息检索模型 1 与文献内容有关，以便在需要时进行索引项的检索。 2 能将一篇文献与其它文献区分开。 于是，人们提出了“相对频率( r e l a t i v ef r e q u e n c y ) ”，并由此衍生几个索引项的权 重计算函数。这些将在下一节中介绍。 用来表示文献内容的项可以是各种类别的语言单位。对于汉语来说，有字、词、 概念、短语、句子、段落等。其中，字、词、概念、短语等特征项在文献中的出现 频率较高，呈现一定的统计规律，更适合与信息检索、文献分类等应用系统。 词汇是文献中最基本的表示项。分别统计所有词汇的项频率和文献频率，即可 得到词汇项的权重。不同的词汇对文献的表示作用不同。一般说来，常用词在所有 文献中都有着较高的频率；罕用词在文献集中的出现次数较少，难以确定它们的统 计规律。这两类词的区分度都比较低。而中等频率的词汇常常与文献所表示的主题 相关，区分度较高，表示能力最强。因此，简单地把所有的词汇都作为文献的特征 项，检索效果并不很好。 为了提高词汇特征的表示能力，需要对词汇特征集做适当的修改，只傈留那些 对表示文献内容作用较大的词汇项。汉语中的虚词使用频率极高，如“的”、“把”、“如 果”等，这些词在所有文献中呈现相近的频率分布。如果将它f 1 列为特征项，则会增 加文献之间的相似度，给文献处理带来一定的困难。解决这个问题的方法是把这些 词组织成一个禁用词表，把表中的词从词汇特征集中滤去。 如果词典中含有语义信息，那么还可以把语义( 概念) 作为文献特征。词义相 同的词汇映射为同一个概念。而同一词汇所表示的词义也是和上下文相关的。由此 可见，概念信息比单纯的词汇信息更能反映文献的内容。词汇的概念信息可以通过 语义分析或概念标注的方法求得。 由于高频词和低频词在文献表示中发挥的作用均小于中频词，因此可以用短语 来替换高频词，用词义相近的低频词构成词汇类来替换原有的低频词。显然，把高 频词组合成短语后，短语的出现频率要低于每个组成成分的频率。而把语义上相近 的一些低频词用它们的词汇类来代替后，生成的词汇类频率为类中所有的词的频率 之和，这样，就提高了低频词的频率。 2 1 3 权重计算 当文献和查询被表示成向量形式后，我们可以很方便地计算出它们间的相似度。 这种相似度能否近似地反映用户需求与文献内容的相似性取决于如何计算索引项 的权重。适当的权重赋值能够明显提高检索系统的性能。与索引项的重要性相关的 两个重要因素是项频率t f ( 文献内频率) 和反比文献频率i d f ( i n v e r s ed o c u m e n t 1 3 辽宁辩技大学硕士论文第二章信息检索模型 f r e q u e n c y ) 。 一个项的重要性随着它在文献中的出现频率的提高而提高。因此，我们应该采 用某种依项的出现频率单调递增函数来估箕权重。项在文献中出现的次数称为项频 率( t e r mf r e q u e n c y , i f ) 。根据项频率计算项的重要性的函数称为项频率因子，简称t f 因子。常用的t f 因子如下； 1 原始t f 因子：直接用项频率t f 作为t f 因予。 2 对数t f 因子：l + i n ( t 0 。 3 二元t f 因子：不考虑项频率t f ，其值根据项是否在文献中出现为l 或0 ( 出 现时为1 ，否则为0 ) 。这种方法为我们评估其它t f 因子的作用提供了基准。 4 改进的t f 因子：0 ，5 + 0 5 4 t f 文献中的最大t 厶 5 。o k a p i t f 因子：t f ，( 2 + t o 。它与对数t f 因予的作用相近。 大规模的测试表明，对数t f 因子的效果最好。 仅仅采用t f 因子来估算权重还过于片面。在许多篇文献中出现的项的区分度小于仅 在很! _ ! 几篇文献中出现的项。这表明应该用一个依项在其中出现的文献数目单调递 减函数来评估颈的重要性。基于这个原因，人们提出反比文献频率因子，简称i d f 因子。一般用l 0 9 2 ( n n k ) 或各释交形来计算。其中，n 是文献总数，i l k 是第k 项在其 中出现的文献数，称为项的文献频率。 近年来，人们应用较多、效果较好的权重计算函数是 w i k = t f i k + i d f k 。 其中，t k 表示项t k 在文献d i 中的磺频率，i d f k 表示项t k 的反比文献频率。i d f k 的计 算方法采用 i d f k = l 0 9 2 ( n n k ) 或 i d f k 2 l 0 9 2 ( n n 0 + 1 此外，文献的长度盈素也必须考虑，否则文献越长越容易被梭索到。这可以按下述 公式规范化得以解决。 对于用户查询q = ( q 1 ，q 2 ，q 。) ，我们可以用同样的方法来表示，也可瞄采用以下的改 进形式来表示： q k = ( o 5 + 0 5 t f k m a xt ox i d f k 冀中m a xt f 是所有n 个特征项的最大频率。 一1 4 辽宁科技大学硕士论文第二章信息检索模型 2 2 布尔模型 布尔模型是一种严格匹配模型。在标准的布尔模型中，文献采用如下的表达形 式： d i = ( w i l ，w i 2 ，w i n ) 其中，n 是特征项的个数，w i k 为1 或0 ，分别表示特征项k 在文献i 中出现或 不出现。由此可见，布尔模型中的文献表示是向量空间模型中文献表示的特殊形式， 它只采用了二元权值。 布尔模型中的用户查询是由特征项和布尔运算符构成的布尔表达式表示的。布 尔运算符包括：a n d ( 与) 、o r ( 或) 、n o t ( 非) 。在实际应用中，通常将特征项的同 义关系用o r 联接，短语关系用a n d 联接，而限定关系则用a n d 或n o t 联接。 布尔模型中的检索判断，就是确定文献中的特征项能否使一个查询表达式为 真。其查询文献相似度的计算过程可以按下述两个步骤进行【”】： 1 首先将q 中的查询项哂用函数f ( d i ，o o ) 替换。如果铀在d i 中出现，则f ( d i ， 锄) 的值为1 ，否则f ( d i ，吣) 为0 。即如果q i 表示特征项j ，则f ( d i ，o j ) = w i j 。 2 设t 和s 为任意的特征项，将由上述方法得到的表达式按下面的公式计算： f ( d i ，ta n ds ) = m i n ( f ( d i ，t ) ，f ( d i ，s ) ) ； ( 2 1 ) f ( d i ，to rs ) = m a x ( f ( d i ，t ) ，f ( d i ，s ) ) ；( 2 2 ) f ( d i ，n o tt ) = 1 - f ( d 。，t ) ； ( 2 3 ) 例如，设用户查询q = ( to rs ) a n dn o tr ，文献d 包含特征项t ，但不包含s 和r 。 则 f ( d ，t ) 2 1 ；f ( d ，s ) = 0 ：f ( d ，r ) 2 0 。 于是根据步骤2 ，我们得到 f ( to rs ) 2 m a x ( f ( t ) ，f ( s ) ) 2 m a x ( 1 ，o ) = i ：f ( d ，n o tr ) 5 l f ( d ，r ) 2 l - 0 2 1 ： f ( d ，q ) = f ( d ，( to rs ) a n dn o tr ) = m i n ( f ( d ，to rs ) ，f ( d ，n o tr ) ) = m i n ( 1 ，1 ) = 1 。 这说明文献d 满足用户查询q 。 布尔模型的优点是运算速度快，简单易行。相应的缺点是： 检索结果不易控制，对于一个特定的用户查询，可能检索到许多文献、也可 能一篇也检索不到。例如，若查询词与文献中的词是相近或同义的，则无法 查到。由于匹配条件过于严格，布尔检索的漏检率较高。 只能反映定性的相关与否的判断，不能进行定量的相关程度的比较，也不能 反映出特征项在文献中的重要程度。 不能识别功能词如”有关”等。这对习惯于自然语言检索的用户很不方 一15 辽宁科技大学硕士论文 第z - 章信息检索模型 便。 针对于标准的布尔模型中文献表达形式过于简单、检索条件过于严格而出现的问 题，人们对其采取了扩充和修改，提出了扩展的布尔模型。如s a l t o n 等人在1 9 8 3 年提出的p 范式模型【1 9 】，它对文献向量