（计算机应用技术专业论文）基于internet的个性化信息检索关键技术研究.pdf

摘要 摘要 随着i n t e r n e t 和w e b 技术的飞速发展，i n t e r n e t 己成为人们进行信息交 流的不可缺少的巨大的信息空间。面对如此巨大的海量信息，人们在寻找 自己所需的信息时常常迷失方向。如何快速、准确的从浩瀚的信息资源中 找到自己所需的信息己成为困扰用户的一大难题。本文提出了个性化的信 息检索方案，并就方案中涉及到的个性化信息检索的关键技术进行了深入 研究。 首先，介绍了信息检索及信息过滤技术。对传统信息检索方法，如对 全文本扫描、倒排文件、签名文件、以及聚类的分析。并讨论了自然语言 处理技术、神经网络技术等新的信息检索方法。 其次，对向量空间模型进行了分析。提出了改进的加权算法，并借助 辅助主题词表和个性化信息库设计了新的检索系统模型，改进了信息检索 方法。 再次，分析了分词技术在信息检索过程中的应用，并讨论了信息检索 和分词技术结合的方式，以及需要解决的关键技术问题。设计出一个无词 典分词方法。它利用统计方法避开了复杂的语法规则，不需要有庞大的词 典支持，解决了新词出现问题，且分词速度快，具有重要的实用价值。 最后，针对如何使用户获得i n t e m e t 上有用的信息，提出了一个基于 i n t e m e t 的个性化信息检索系统模型。系统采用a g e n t 技术、相关反馈学习 算法，有效地适用于i n t e m e t 中信息检索的需要，具有一定的理论价值和应 用价值。 关键词信息检索；向量空间模型；隐含语义索引；自动分词；个性化 燕山大学工学硕士学位论文 a b s t r a c t 昕坊t h ed e v e l o p m e n to fi n t e m e ta n d 蹄的t e c h n o l o g y , i n t e r n e th a sb e e na g i g a n t i cs p a c eo f i n f o r m a t i o ne x c h a n g e f a c i n gt h eg i g a n t i ci n f o r m a t i o n , p e o p l e o f t e nl o s et h e i rd i r e c t i o nw h e nt h e yl o o kf o rt h e i rr e q u i s i t ei n f o r m a t i o n h o w q u i c k l ys e a r c h i n gf o rt h e i rr e q u i s i t ei n f o r m a t i o nf r o mg i g a n t i c i n f o r m a t i o n r e s o u r c eh a sb e e nad i f f i c u l tp r o b l e mo fp e r p l e x i n gt h eu s e r s ot h i sp a p e rp u t s f o r w a r dp e r s o n a l i z e di n f o r m a t i o nr e t r i e v a la n dp u t st h ee m p h a s i so nt h e r e s e a r c ho ft h ec r u c i a lt e c h n o l o g yc o n c e r n i n gw i t l lt h ep e r s o n a l i z e di n f o r m a t i o n r e t r i e v a ls y s t e m f i r s t l y , w es u r v e yt h em a j o rt e c h n i q u e s f o ri n f o r m a t i o nr e t r i e v a la n d f i l t e r i n gm e t h o d s w ep r o v i d ea no v e r v i e wo ft h et r a d i t i o n a lo n e sf u l lt e x t s c a n n i n g ，i n v e r s i o n , s i g n a t u r ef i l e sa n dc l u s t e r i n g w ed i s c u s sa t t e m p t st o i n c l u d en a t u r a ll a n g u a g ep r o c e s s i n ga n dn e u r a ln e t w o r k s e c o n d l y ，t h i sp a p e ra n a l y z e sv e c t o rs p a c em o d e l t h i sp a p e rp u t sf o r w a r d a ni m p r o v e ds e a r c h i n gm o d e lb ya d o p t i n ga na d v a n c e dv e c t o rs p a c em o d e l b a s e do nw e i g h tc o m b i n e dw i t l lt h e m a t i cw o r d sa n di n d i v i d u a li n f o r m a t i o n d a t a b a s e t h i r d l y , t h i sp a p e rp r e s e n t st h ew o r ko ft h ew o r ds e g m e n t a t i o na n d a n a l y z e st h ew a y sa n dd i f f i c u l t i e st oc o m b i n et h e m t l i sp a p e rg i v e sam e t h o d o fe x t r a c t i n gw o r d sw i t h o u td i c t i o n a r y t h i sm e t h o da v o i d st h ec o m p l e x g r a m m a ra n dr u l e s ，w h i c hn e e d n te n o r m o u ss u p p o r tf r o md i c t i o n a r ya n d r e s o l v e st h ep r o b l e m sb r o u g h tb yt h en e ww o r d s s ow ec o n c l u d et h a tt h i s m e t h o dh a sb e t t e re x a c t n e s sa n di sv e r yp r a g m a t i ca n dp o w e r f u li np r a c t i c a l o p e r a t i o n i nt h ee n d ，t h ea b i l i t yo ff a c i l i t a t i n gu s c t st oa c h i e v eu s e f u li n f o r m a t i o ni s m o r ea n dm o r ei m p o r t a n tf o ri n f o r m a t i o n a lr e t r i e v a ls y s t e m a i m i n ga te x i s t e n t a b s l r a c t p r o b l e m s ，ap e r s o n a l i z e di n f o m m t i o n a lr e t r i e v a ls y s t e mi si n t r o d u c e d t h i s s y s t e mi si m p l e m e n t e du s i n gt h ea g e n tt e c h n i q u e sa n dt h er e l e v a n tf e e d b a c k a p p r o a c h t h i ss y s t e mg e n e r a l l yc a nb eu s e di nt h ei n f o r m a t i o nr e t r i e v a li n i n t e r n e ta n dh a v eh i g hs i g n i f i c a n c ei nt h e o r i e sa n d a p p l i c a t i o n s k e y w o r d si n f o r m a t i o nr e t r i e v a l ；v e c t o rs p a c em o d e l ；l a t e n ts e m a n t i ci n d e x ； a u t o m a t i cw o r d se x t r a c t i o n ；p e r s o n a l i z a t i o n i i i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于i n t e m e t 的个性化信 息检索关键技术研究，是本人在导师指导下，在燕山大学攻读硕士学位期 间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外 不包含他人己发表或撰写过的研究成果。对本文的研究工作做出重要贡献 的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由 本人承担。 作者签字茹奴日期：舯6 年彭月节目 燕山大学硕士学位论文使用授权书 基于i n t e m e t 的个性化信息检索关键技术研究系本人在燕山大学 攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果 归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人 员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保 留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。 本人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以 公布论文的全部或部分内容。 保密口，在 年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上相应方框内打“”) 作者签名：班 日期：捌年哪甲日 导师签名：弘移毫日期：尹多年矿月少日 第1 章绪论 1 1 研究背景和意义 第1 章绪论 由于i n t e r n e t 的飞速发展，越来越多的数据库和信息不断加入到网络之 中，网络上的各种信息正以指数级的速度增长，i n t e m e t 已经发展为当前资 料最多、门类最全、规模最大的信息库和全球范围内传播信息的主要渠道， w w w 以超文本的形式呈现给用户各种各样的信息，构成了一个异常庞大 的具有异构性、动态性和开放性的分布式数据库。 人们上网获取信息的一种普遍方式是浏览。i n t e m e t 上的文档一般都是 通过超级链接结构互相联系起来的，借助i n t e m e t 浏览器来浏览w e b 页面 的内容。这种浏览方式适合于目的不明确、时间要求不紧迫的情况，当需 要查找一个具体的内容时，效率很差，一般不能在短时间内获得所要的信 息，特别是对i n t e m e t 不太熟悉、缺乏上网经验的用户。因此，用户试图通 过浏览w e b 来发现信息已经变得非常困难，往往花费了很多时间和精力却 所获甚少，人们期待效率更高的信息获取工具的出现。 自从1 9 9 4 年4 月w e b c r a w l e r 搜索引擎在网上正式发布并开始服务以 来，援索引擎己经成为发展最快、最引人注目的网络服务之一。当时的搜 索引擎数据库容量小，查询算法简单，效率不高，但却改变了传统的检索 方式。然后，搜索引擎开始进入“容量建设期”，出现了一些著名的搜索引 擎。例如：a l t a v i s t a 、l y c o s 、h a r v e s t 等，网页数量都超过百万甚至千万。 中文搜索引擎虽然发展较晚，但是经常使用的一些搜索引擎网页数量也都 在十万以上。然而在简单的匹配算法下，这对用户来说并不是一个很好的 事情。 当前i n t e m e t 上的信息检索系统正经历着从“数量累积阶段”向“质量 精炼阶段”的变革。随着i n t e m e t 上的信息数量呈指数级增长，大量信息垃 圾也混杂其中。如何向用户提供质量好且数量适当的检索结果成为信息检 燕山大学工学硕士学位论文 索技术发展的方向之一。由于大多数搜索引擎的搜集范围是综合性的，它 们的r o b o t 尽其可能的把各类网页“抓”回来，只经过简单的加工后存放 到数据库中。另外，信息检索系统直接提供给用户的检索途径大都是基于 关键词的布尔逻辑匹配，返回给用户的就是所有包括关键词的文献。这样 的检索结果在数量上远远超出了用户的吸收和使用能力，让人感到束手无 策。这也就是现在经常谈论的“信息过载”、“信息超载”现象。 因此，为了解决丰富的信息资源和低能的信息获取能力之间的矛盾， 个性化的信息检索技术应运而生，并获得了长足的发展，正在被越来越多 的应用于w e b 空间，并成为讨论的焦点。自9 0 年代开始，相关主题的国际 会议不断举行，有力地推动了个性化的信息检索技术的不断完善和进一步 深入。 1 2 个性化信息服务系统发展概况 目前存在着许多个性化信息服务系统【，它们提出了各种思路以实现个 性化服务。个性化信息服务系统根据其所采用的技术可以分为两种：基于 规则的个性化信息服务系统和基于内容过滤的个性化信息服务系统。 基于规则的个性化信息服务系统如：i b m 的w e b s p h e r e 、b r o a d v i s i o n 、 i l o g 等，它们允许系统管理员根据用户的静态特征和动态属性来制定规 则，一个规则本质上是一个i f - t h e n 语句，规则决定了在不同的情况下如何 提供不同的服务。 基于规则的个性化信息服务系统其优点是简单、直接，缺点是规则质 量很难保证，而且不能动态更新，此外，随着规则的数量增多，系统将变 得越来越难以管理。 基于内容过滤的个性化信息服务系统如：p e r s o n a lw e bw a t c h e d 2 1 、 s y s k i l l & w e b e r t 3 1 、l e t i z i a a 、c i t e s e e r 5 1 、i f w e b l 6 、s i f t e r 、p v a i s 、 w e b m a t e 9 、w e b a c e t l 讲、e l f i f l l 】和w e b p e r s o n a l i z e r 1 2 1 等，这些基于内容 过滤的系统利用资源与用户的兴趣的相似性来过滤筛选信息。 基于内容过滤的个性化信息服务系统的优点是比较简单、有效，缺点 第1 章绪论 是它难以区分资源内容的品质和资源内容的风格，而且它不能为用户发现 新的感兴趣的资源，只能为用户发现和用户已有的兴趣相似的资源。 协作过滤的个性化信息服务系统如：w e b w a t c h e r i j 、l e t sb r o w s e 【l 、 g r o u p l e n s 15 1 、f i r e f l y 1 6 1 、s e l e c t l l7 1 、l i k e m i n d s 和s i t e s e e r l l 剐等，它们利 用用户之间的相似性来过滤信息。 基于协作过滤个性化信息服务系统的优点是能为用户发现新的感兴趣 的信息，缺点是存在两个很难解决的问题，一个是稀疏性，亦即在系统使 用初期，系统资源还未获得足够多的评价，系统很难利用这些评价来发现 相似的用户。另一个是可扩展性，亦即随着系统用户和资源的增多，系统 的性能会越来越低。还有一些个性化信息服务系统如：w e b s i f t 1 9 1 、f a b l 2 0 1 、 a n a t a g o n o m y 2 1 和d y n a m i cp r o f i l e r z 2 等，同时采用了基于内容过滤和协作 过滤这两种技术。结合这两种过滤技术可以克服各自的一些缺点，为了克 服协作过滤的稀疏性问题，可以利用用户浏览过的资源内容预期用户对其 他资源的评价，这样可以增加资源评价的密度，利用这些评价再进行协作 过滤，从而提高协作过滤的性能。 人们发展了许多个性化信息服务技术，帮助用户在w w w 上快速定位、 检索用户自己感兴趣的信息。目前已经出现的一些个性化信息服务相关的 技术研究。基于数据挖掘的个性化信息服务是当前的一个研究热点。主要 的研究有，s c h e c h t e r 2 3 】等人根据用户的访问路径模式预测用户未来可能的 请求，让代理服务器执行预取操作，将相关w e b 页放入其c a c h e 中，以加 快访问速度。c o o l e y l 2 4 1 等人和b u c h n e r 2 5 1 等人利用数据挖掘技术从访问的 l o g 文件中提取用户的访问模式，用于市场决策和智能推荐服务。n a s r a o u i 2 6 1 等人采用聚类用户访问模式方法，预测用户未来的访问行为。s h a h a b i l 2 7 1 等 人提出的使用挖掘系统依赖于客户端的数据收集，客户端的代理为服务器 返回用户请求的页面及时间等数据。 国内的学者在w e b 用户访问信息挖掘方面也开展了大量的研究工作。 如：上海交通大学尤晋元教授等人引人w e b 页面的内容链接比和页组的组 内链接度，修改了频繁访问页组支持度的计算公式，提出了基于页面内容 和站点结构的页面聚类挖掘改进算法；清华大学马少平教授等人，提出一 鳌生盔兰三兰堡圭兰垡兰茎 种利用w e b 服务器日志文件，运用n 兀( n g 删n ) 坝刹模型对用尸禾采口j 就 进行的w e b 访问请求进行预测。 1 3当前i n t e r n e t 上的个性化信息检索系统 信息检索是用户寻找、定位感兴趣信息的主要途径，i n t e m e t 信息检索 服务的质量决定了用户使用i n t e r n e t 信息的效率。现有的i n t e r n e t 检索服务 没有考虑用户的差异，对于任何用户，只要输入的关键词，相同返回的检 索结果就完全相同。而实际上，不同用户由于背景知识、兴趣爱好等方面 不同，需要的信息则往往是不同的。当我们利用搜索引擎搜索信息时，往 往会得到大量无用的信息充斥其间，而真正满足我们需要的信息则淹没在 搜索返回的信息海洋中了。这种现象已经受到用户越来越多的不满。 个性化信息检索是指根据用户的兴趣和特点进行检索，返回与用户需 求相关的检索结果。目前个性化信息检索还处于研究阶段，n e c 研究院提 出了个性化元搜索引擎原型系统i n q u i r u s 2 ，与普通的元搜索引擎不同， i n q u i r u s 2 增加了对用户偏好的描述。用户的信息需求不再仅仅通过用户输 入的查询关键词体现。而是通过查询关键词和用户偏好共同体现。用户偏 好被分为t o p i c a lr e l e v a n c e ( f a s t ) 、p e r s o n a lh o m e p a g e s 、r e s e a r c hp a p e r s 、 p r o d u c tr e v i e w s 、g u i d ef a qh o wt o 、c a l l sf o rp a p e r s 、g e n e a l o g y 和 e r g o n o m i c s ，每一类偏好对应专门的查询源选择策略、查询关键词修饰策略 和排序策略。 查询源选择策略是指对于不同的用户偏好，i n q u i r u s 2 选择不同的搜索 引擎进行搜索，以得到最佳的检索效率。查询关键词修饰策略包含三种方 式：第一种方式是利用搜索引擎特定的操作，如一些搜索引擎提供的提高 检索效率的技巧：第二种方式是将查询关键词丰富成为查询语句；第三种 方式是增加查询词。例如：如果用户查询“l i n u x ”，并选择偏好类为t o p i c a l r e l e v a n c e ，则i n q u i r u s 2 将“l i n u x ”修饰为“w h a ti sl i n u x ”或“l i n u xl i n k s p a g e ”进行查询。为保证检索质量，l n q u i r u s 2 同时按原查询关键词进行检 索，按原查询关键词检索的结果和按经修饰的查询关键词检索的结果经整 4 第1 章绪论 合后提交给用户。 国内南京大学推出了个性化信息检索智能体d o l t r j - a g e n t ，浙江大学 提出了个性化信息检索系统n e tl o o k e r 。还有一些研究者将常规搜索引擎返 回的结果进行二次挖掘和过滤，产生用户感兴趣的信息。 1 4 本文主要研究内容 介绍了信息检索及信息过滤方法。对传统信息检索方法，如全文本扫 描( f u l lt e x ts c a n n i n g ) 、倒排文件( i n v e r s i o n ) 、签名文件( s i g n a t u r ef i l e ) 、以及 聚类( c l u s t e r i n g ) 的分析。在传统信息检索方法的基础，引入自然语言处理技 术、神经网络技术等新的信息检索方法。 对向量空间模型进行了分析。提出了改进的加权算法，并借助辅助主 题词表和个性化信息库设计了新的检索系统模型，改进了信息检索方法。 汉语自动分词问题是中文信息检索的基础问题，也是阻碍其向前发展 的瓶颈问题。介绍了分词技术的发展状况，分析了分词技术在信息检索过 程中的应用，并讨论了信息检索和分词技术结合的方式，以及需要解决的 关键技术问题。设计出一个无词典分词方法。它利用统计方法避开了复杂 的语法规则，不需要有庞大的词典支持，解决了新词出现问题，且分词速 度快，具有重要的实用价值。 针对如何使用户获得i n t e m e t 上有用的信息，提出了一个基于i n t e m e t 的个性化信息检索系统模型。系统采用a g e n t 技术、相关反馈学习算法， 有效地适用于i n t e r n e t 中信息检索的需要，具有一定的理论价值和应用价值。 1 5 本文结构 全文共分五章，具体的章节内容安排如下： 第1 章为绪论，介绍了论文研究的背景和意义，概述了当前信息检索 技术的情况，最后介绍了本文的主要研究内容和论文的组织。 第2 章介绍了信息检索及信息过滤方法。对传统信息检索方法，如全 燕山大学工学硕士学位论文 文本扫描( f u ut e x ts c a n n i n g ) 、倒排文件( i n v e r s i o n ) 、签名文件( s i g n a t u r ef i l e ) 、 以及聚类( c l u s t e r i n g ) 的分析。在传统信息检索方法的基础，引入自然语言处 理技术、神经网络技术等新的信息检索方法。 第3 章对向量空间模型进行了讨论，提出了改进的加权算法，并借助 辅助主题词表和个性化信息库设计了新的检索系统模型，改进了信息检索 方法。并对隐含语义索引模型进行了深入的分析。 第4 章对自动分词技术进行了研究，设计出了一种无词典分词法，并 分别从理论上、实验上验证了无词典分词法分词的有效性。 第5 章提出了一个基于i n t e m e t 的个性化信息检索系统模型。 最后，对整个论文工作做了总结，并探讨了下步需要完善和进一步 研究的问题。 6 第2 章信息检索及信息过滤方法 第2 章信息检索及信息过滤方法 本章分成两部分，第一部分回顾了传统文本检索的方法。总结传统方 法出于两个目的：第一，传统方法对了解新进展提供了丰富的背景知识； 第二，对这些传统方法进行变形或者扩展构成新方法的中心内容。第二部 分中研究了近年来一些将自然语言处理技术和信息检索方法进行结合的尝 试，如神经网络等。最后做出总结。 2 1引言 具体分析以下几个方面了：第一，全文扫描方法及其在近似搜索方面 的进展；第二，可能在任何信息检索系统中都使用的快速倒排文件方法； 第三，签名文件方法；第四，情报学中传统使用的聚类方法。 2 2 传统文本检索 以下对传统文本检索的方法进行分析。 2 2 1全文扫描 确定某个字符串在哪些文档中出现，最直接的方法就是在所有的文档 中查找该字符串，称为字符串测试( s u b s t r i n gt e s t ) 。“字符串”是一系列字 符组成的序列，不包含通配符( d on o tc a r ec h a r a c t e r s ) 。比如我们常用 或者? 来表示通配符。如果一个查询是由多个待查字符串组成的复杂布尔表达式， 那么就需要额外的步骤来判断通过字符串测试找到的匹配是否满足该布尔 表达式，称为查询求解( q u e r yr e s o l u t i o n ) 。 本章不打算深入考查有关一般正则表达式的搜索方法，该主题可以参 照h o p c r o f t 及u l l m a n 于1 9 7 9 年撰写的自动机理论【2 8 1 。给定一个正则 7 燕山大学工学硕士学位论文 表达式，可以构造一个有限状态自动机，该自动机可以检测该正则表达式 在文档中的出现。自动机的搜索时间与文档大小成线性关系，但是自动机 的状态个数可能与正则表达式的大小成指数关系。然而，如果搜索模式仅 限于字符串，那么就可以应用比有限状态自动机更高效的方法。下面我们 就讨论这些方法。 最显而易见的字符串测试方法是，将搜索字符串与文档相应字符串进 行比较，如果不匹配，则将文档指针右移一个字符位置后，也可以说将搜 索字符串右移一个位置。重新将搜索字符串与文档当前的字符串比较，直 至找到该字符串或碰到文件结束为止。该方法虽然简单易行，但算法实现 时速度很慢。假设搜索的字符串长度为m ，文档的长度为疗，则最坏情况下 需要o ( m + 竹) 次比较。 k n u t h 、m o r r i s 及p r a t t 【2 9 】提出k r i p 算法，k m p 的主要思路就是，不论 何时，只要能够预测到字符串的不匹配，则可能将搜索字符串右移不止一 个位置。该方法需要对搜索字符串做一些预处理工作来检测递归的字母序 列。预处理的时间为o ( m ) 。 当前所知道的最快的字符串测试方法由b o y e r 与m o o r e 提出，他们提 出对字符串进行从右到左的比较。如果不匹配，搜索字符串可最多右移r n 个位置再进行匹配。最坏情况下，该方法需要m + 胛次比较，但通常情况下， 比较的次数远小于这个数目。 例如：对于一个随机的长度为5 的搜索串，该算法的典型实现需要考 查文档的f 4 个字符，i 为开始匹配的字符在文档中的位置。同样，该方法 需要o ( m ) 的预处理时间。 字符串测试的另一种方法基于自动机理论，a h o 及c o r a s i c k 于1 9 7 5 年 提出一种基于有限状态自动机的方法，该方法允许同时并行搜索多个字符 串。搜索的时间为o ( m ，建立自动机的时间与待搜索字符串的长度成线性 关系。 w u 和m a n b e r 提出了一种能够容忍键入错误的搜索方法，该方法以每 次一个字符的方式扫描数据库，并通过一种灵巧的位编码来记住当前已经 匹配的字符串。该方法速度很快，也很灵活。其源码可从a r i z o n a t u c s o n 第2 章信息检索及信息过滤方法 大学匿名下载。 总之，每种全文扫描方法的优点都在于不需要空间消耗，极小的插入 和更新的费用，缺点在于反应时间太长，该缺点在面对大数据量时表现得 尤为突出。所以，全文扫描方法常常用专用硬件实现，或者将该方法同能 够限制搜索范围的其他访问方法相结合使用。 2 2 2 签名文件 签名文件方法当前引起了广泛的关注。在本方法中，每个文档都通过 h a s h 函数及重叠编码( s u p e r i m p o s e dc o d i n 曲产生一个称为签名( s i g n a t u r e ) 的 位串。文档的签名结果顺序存入一个单独的文件( 签名文件) 中，签名文件比 原文件小得多，因此可以提供更快速的搜索。f i l e s 和h u s k e y 3 0 】将该方法用 于书目数据库。他们使用一停用词表来忽略普通的词，对非普通词则使用 一个自动过程将它们还原成词干。同时，他们使用一个数值函数而非对照 表( 1 0 0 k - u pt a b l e ) 作为h a s h 函数。 h a r r i s o n e 3 1 使用签名文件方法以加快字符串测试速度。他提出使用相邻 的连续字母( n - g r a m ) 作为h a s h 函数的输入。b a r t o n 等人【3 2 】于1 9 7 4 年提出使 用等频率文本片段( e q u i - f r e q u e n tt e x ts e g m e n t ) 代替n - g r a m 。因此，签名中 “1 ”的服从均匀( u n i f o r m ) 分布。t s i c h r i t z i a 和c h r i s t o d o u l a k i s 试图使用无重 叠编码的签名文件。他们的方法通过将文档中每个词的签名串联起来就得 到该文档的签名。这样的话，就必须保留位置信息。r a b i t t i 和z i z k a 声称该 方法预期将比重叠编码更加重c p u 的负担。 其他一些学者采用了类似的方法用于格式化的记录。一些文章中提出 了对文本检索有潜在利用价值的想法。r o b e r t s l 9 7 9 年在一个电话目录的应 用中使用了一级签名文件f 3 3 1 。他讨论了许多有趣的应用细节，其中的两个 细节可以用于文本检索。 签名文件采用一种位片( b i t s l i c e ) 的方式存储。即所有签名的头一位连 续存放，次一位再连续存放。尽管该结构使得更新很困难，但它能够减少 检索的i o 费用。他建议在构造签名时，查询中经常出现的标引项必须特殊 对待。 9 燕山大学工学硕士学位论文 然而，r o b e , s 并没有提供这个方面的任何数学分析，而文档中则对这 一点进行了尝试。文章表明，词的访问模式和出现频率事先已知，并且分 布足够偏斜的话，那么与同样大小的普通签名文件相比，该方法设计出的 签名文件，可以避免约5 0 的误选。 此外，人们还提出了具有更高搜索速度的二级签名文件口“，签名树以 及基于签名的分割也被提出，但是没有应用于真实数据库的时间结果的报 道。 重叠编码方法的设计和研究由来已久。首先将重叠编码用于文本检索 的人是c n m o o e r s 。他发明了一种很精巧的基于边缘凹口卡片和探针的机 械设备。该设备可以快速处理对书目的联合查询。关键词抽取由人工实现， 而h a s h 函数则使用对照表实现。 这种采用边缘凹口卡片的方法引起了广泛的兴趣。s t i a s s n y ”】使用字母 对来产生每个词的签名。他还证明：对于一个给定的签名长度，当文档的 签名中“1 ”的数目等于“0 ”的数目时，误选概率达到最小。o r o s z 和 t a c h a c s 3 6 】使用乔丹定律( j o r d a n st h e o r e m ) ，给出了文档签名中“1 ”的概率 分布的一个封闭形公式。k a u t z 和s i n g l e t o n f 37 讨论了设计一个没有误选的签 名系统的问题，他们从编码和信息理论的角度对该问题进行了研究。尽管 他们的方法在理论上很有意义，但在实现时有很多缺点，需要对照表，不 易处理日益增长的词汇表，签名集合的设计需要巨大的开销。 在对签名文件方法的讨论即将结束之际，需要指出的是，该方法的主 要缺点就是当文件很大时反应时间较长。优点在于实现简单，对插入的处 理效率高，能够处理词的部分查询，能够支持不断增长的文件以及对键入 和拼写错误的容错性。另外，该方法易于并行化。 2 2 3 倒排文件 每个文档都可以用系列关键词来表示，从检索目的来说，这些关键 词描述了文档的内容。只要找到文档，便可以找到文档中的关键词。反过 来，如果按关键词建立到文档的索引，便可以根据关键词快速地检索到相 关文档。具体地，关键词被存储在索引文件( i n d e xf i l e ) 中，对于每个关键词， 1 0 第2 章信息检索及信息过滤方法 都有一个指针链表，该表中的每个指针指向与该关键词相关的某个文档， 所有指针链表构成置入文件( p o s t i n gf i l e ) 。这种倒排文件的方法几乎被当前 所有的商用信息检索系统所采用。 组织索引文件可以采用更复杂的方法，例如：b 树，t r i e 树，h a s h 表 或者这些方法的变形或混合。s t a i r s 使用了二级索引文件。以相同字母对 开始的词在= 级索引中放在一起，一级索引中包含指向二级索引的指针， 每个指针指向每个字母对。l e s k 使用一张负荷过度、链分开的h a s h 表 f o v e r - l o a d e dh a s ht a b l ew i t hs e p a r a t ec h a i n i n g ) 来获得对一书目数据库的快速 检索。 倒排文件方法的缺点有，存储开销大，倒排文件【3 8 】的大小可能会达到 原文件大小的3 0 0 ，动态环境下索引文件更新和重新组织的开销大，如果 表太大，则将它们合并的开销巨大。 该方法的优点有，实现相对简单，查询速度快，很容易支持同义词查 询，例如：同义词可以在词典中组织成穿插表( t h r e a d e d l i s t ) 。由于上述原因， 倒排文件的方法在当前绝大部分的商用系统中被采用i a l o g ，b r s ， m e d l a r s ，o r b i t ，s t a i r s ) 。 近年来倒排文件方面的进展和挑战包括，置入表的分布不均匀，这就 意味着小部分词出现频率高，而大部分词只出现一次或两次。这样的话， 有些置入表很长，而大部分置入表的长度为1 或2 。为了解决问题，人们提 出了混合方法策略以及使置入表可调增长的算法。 在现实中，索引文件通常很大，可能有数兆。为了解决倒排索引存储 开销太大的问题，人们提出了一些压缩方法，z o b e l 等人将e l i a s 的压缩体 制用于置入表。最后要提到的是， “g l i m p s e ”软件包中使用一个很粗的索 引加上“a g r e p ”包来实现近似搜索。 2 2 4 聚类 聚类的基本想法就是将相似的文档聚合在一起形成类，该想法基于聚 类假设( c l u s t e r h y p o t h e s i s ) ，紧密关联的文档往往与相同的查询要求有关。通 过将相似文档聚类可以加速搜索过程。 燕山大学工学硕士学位论文 聚类在信息检索、情报学以及模式识别等领域中都引起了广泛兴趣。 虽然在模式识别中文档聚类并非重点，但模式识别中的许多方法和思想都 可以用于文档聚类。 注意聚类的对象除了文档外还可以是标引项，因此标引项也可以聚类 形成共现标引项( c o ，o c c u r r i n gt e r m s ) 类。共现标引项常常彼此相关，有时可 能是同义词。标引项的聚类对叙词词典( t h e s a u r u s ) 的自动构造和降维 ( d i m e n s i o n a l i t yr e d u c t i o n ) 很有用。叙词词典的自动构造基于统计准则，因此 它在概念上与文档聚类方法是等价的。然而，s a l t o n 声称自动标引项聚类算 法的效率值得怀疑，因此，他建议使用半自动方法。 文档聚类包括两个过程，聚类产生( c l u s t e rg e n e r a t i o n ) 及聚类搜索( c l u s t e r s e a r c h ) 。首先我们讨论聚类产生的方法并将它们分类。聚类搜索问题相对 容易，将在后面部分讨论。 聚类产生过程的操作对象是向量或者t 维空间上的点。每个文档都表 示成一个向量，该向量被分配一些关键词，即将文档表示成关键词( 可能包 含权值) 组成的向量。这个过程称为标引( i n d e x i n g ) ，可以通过手工或者自动 实现。s a l t o n 对这两种实现方式的对比表明，实验环境下实现的简单自动标 引方法至少与手工方法性能一样好。 自动标弓l 过程通常使用以下词典：一个用于去掉普通词( 如“a n d ”、 “t h e ”等等) 的负性词典( n e g a t i v ed i c t i o n a r y ) ，通常也叫停用词词表( s t o p l i s t ) ； 一个用于抽取单词词干( s t e m ) 的前缀和后缀表；一个用于将每个词干分配到 一个概念类的同义词词典。 这种方法下，每个文档表示成一个t 维向量，其中f 是允许的标引项( 概 念) 的个数。某个标引项在文档中不存在用0 标识或1 标识，反之则用1 ( 二 值文档向量) 或者某个正值( 标引项的权重) 标识，该权重反映了该标引项在 文档中的重要程度。以下是几种其他的权重函数。 f p e q 第k 个标引项出现在第f 个文档中的频率。该值很容易获得 且比二值表示的权值更有效。这个值就是通常所说的t f ( t e r mf r e q u e n c y ) ， 指t e r m 在文档中出现的频率，一般来说，t f 越大，表明该t e r m 在文档中 的重要性越大。 第2 章信息检索及信息过滤方法 标引项专指度( t e r ms p e c i f i c i t y ) 1 ”j ，l o g n 一1 0 9 ( d o c f r e q ，) + 1 ，其中 d o c f r e q 。表示包含标引项k 的文档数目，是文档的总数。该值也容易 获得，并且同样比二值表示的权值更有效。这个值实际上可以认为是i d f 计算的一个变形，表明该t e r m 在整个文档集合中的分布情况，d f 即 d o c f r e q 。越高，该值越低，越不可以用于区分。 逆文档频率( i n v e r s ed o c u m e n tf r e q u e n c y ，m f ) ，f r e q m d o c f r e q 女。 与前面的权值相似但似乎更有效。i d f 通常是指n d o c f r e q 。，t f i d f 才 是f r e q 。d o c f r e q 。 f r e q d o c f r e q 女，其中t e r m r e l = ( r - r a ) ( s i ( i - s ) ) ，称为标引 项相关因子( t e r mr e l e v a n c ef a c t o r ) 。r 为文档集合中所有相关的文档数目， 为相关文档中含有标引项k 的文档数目，i 为所有不相关的文档数目，s 。为 不相关的文档中含有标引项k 的文档数目。在某种条件下，该权值为理论 上最优的权值，试验结果似乎证实了这一点。该方法的问题在于必须对查 询和所有文档之间进行相关性评估并对每个标引项计算相应的参数，这需 要人类专家花费大量时间才能实现。t e r a m r e l 。以认为是该t e r m 在相关 文档出现的概率和在不相关文档出现的概率的比值，是概率检索模型中常 用的一个参数，现在通常通过相关反馈方式来计算。 上述过程将文档表示成t 维空问中的点。下一步就是要将这些点划分 到不同的类中。在理想情况下，划分过程应该达到两个目标，在理论上稳 定和高效。理论上的稳定性准则是指，该方法在增长情况下保持稳定，也 就是说，当插入新的文档时，划分不会显著地改变。文档描述中的细微错 误会导致划分的细微改变，该方法与文档的初始顺序无关。 高效性准则主要是指聚类的时间开销。在分析聚类生成方法的性能时， 常常忽略该方法的空间消耗。迄今为止，人们提出了许多聚类生成方法。 但不幸的是，没有哪个单一的方法同时满足稳定性准则和高效性准则。 因此，在这里将各种聚类生成方法分成两类，一类是基于文档间相似 矩阵的稳定性方法；另一类是更有效的直接来自文档向量的迭代方法。 这类方法通常需要o ( n 2 ) 多的时间费用 为文档的数目) ，且常常要用 到图论技术。该方法中，必须选择文档之间的相似性函数来度量两个文档 燕山大学工学硕士学位论文 之间的相似程度。人们提出了很多不同的相似性函数，如果对上述相似性 函数进行适当的归一化处理，则会发现它们提供几乎相同的检索性能。 给定一个文档相似矩阵，此类聚类方法的一个最简化版本运行如下： 第一步，先选定一个适当的阈值：第二步，相似度大于该阈值的文档之间 用边相连；第三步，该图的连通分量( 最大簇) 即为所要的类。 如果将类分层，即将类再聚类形成父类，父类再聚类形成父类的父类， 则常常可以加快检索的速度。一个将类分层的方法是将上述方法中的阈值 不断减小进行使用。一个更好的将类分层的方法可以参见文献 4 0 】，该文档 中使用单链聚类准则进行聚类。将该方法用于2 0 0 个文档进行实验，实验 结果表明，该算法执行需要的时间复杂度为o ( n 2 ) 。 上述方法( 也许所有的聚类生成方法) 的一个共同缺点就是它们都至少 需要一个经验常数，用于相似性度量的阈值或者一个想要的分类个数。该 常数会显著影响最后的划分结果，它会给给定的数据强加某种结构，而不 是去探测数据内在可能已经存在的结构。也就是说，划分结果可能不是实 际存在的某个结构，而是硬性划分的一个结构。 z a h n l 4 1 】提出的方法试图解决这一问题。他提出寻找给定点集合的最小 生成树，然后删除不相容边。当某条边的长度比它入边的平均长度大得多 时称该边为不相容边。结果图的连通分支即作为聚类结果。同样，该方法 基于一个经验值。 但是，该方法的结果受经验值的影响并不十分敏感