（计算机软件与理论专业论文）个性化智能新闻信息检索系统的设计与实现.pdf

摘要 信息爆炸式的增加，导致处理和使用这些庞大的信息变得越来越困难。人们 在面对“信息过载”和“资源迷向”的问题时，往往显得不知所措。 现行的网络新闻信息检索系统面临很多问题，主要是由于网络上信息的不断 更新，就要求网络新闻信息检索对庞大的动念的信息要做出快速和准确的处理。 同时通用搜索引擎很难满足不同背景，不同目的用户查询要求。为了解决这些问 题，个性化智能搜索引擎应运而生。 为了对有不同兴趣的用户准确地提供网络新闻信息，我们设计了个性化智能 搜索引擎a it i m e s 。a it i m e s 系统可以根据用户的不同兴趣返回不同的查询 结果。同时，我们提出了一些改进和创新算法。如：优化的网络爬虫算法，模拟 实验显示更新速度可以比传统的网络爬虫快6 倍。基于关键标签的信息抽取算 法，不光可以在最少的人工干预下，提取到有用信息，还同时根据重要性对文档 分类，使网络爬虫可以重点回访和更新那些重要新闻信息。通过查询扩展方法改 进了单一的向量空j 日j 模型，最后，我们提出了一个冗余信息推荐算法，模拟实验 表明该结构和算法能够有效地检索出与用户兴趣相关的信息，并且具有良好的 可适应性。 关键词：个性化：向量空间模型；冗余信息推荐；用户兴趣；a g e n t i i a b s t r a c t a st h ea v a i l a b l ei n f o r m a t i o ni n c r e a s e s ，t h ei n a b i l i t yt op r o c e s s ，a s s i m i l a t ea n d u s es u c hl a r g ea m o u n to fi n f o r m a t i o nb e c o m e sm o r ea n dm o r ea p p a r e n t t h e p r o b l e m so f t h eo v e r l o a d i n gi n f o r m a t i o n a n d t h ec o n f u s i n gr e s o u r c e s c a u s e p e o p l et of e e lh e l p l e s s c u r r e n t l ya v a i l a b l ew e bn e w sr e t r i e v a ls y s t e m sf a c ean u m b e ro fp r o b l e m si n t h a tw e b b a s e dn e w sr e t r i e v a lr e q u i r e st h ea b i l i t yt oq u i c k l ya n da c c u r a t e l yp r o c e s s a n du p d a t ev e r yl a r g ea m o u n t so fd a t at h a ti sc o n s t a n t l yb e i n gu p d a t e d i ti sv e r y d i f f i c u l tt os a t i s f yt h eu s e rf r o md i f f e r e n tb a c k g r o u n d ，d i f f e r e n ti n t e n t i o nb yg e n e r a l s e a r c he n g i n e i no r d e rt os o l v et h e s ep r o b l e m s ，t h ep e r s o n a l i z e ds e a r c he n g i n e a p p e a r s i nt h i st h e s i s ，w ep r e s e n tt h ed e s i g na n di m p l e m e n t a t i o no fa i - t i m e s ，a p e r s o n a l i z e di n t e l l i g e n ts e a r c he n g i n et h eg o a lo fw h i c hi st oa c c u r a t e l yr e t r i e v ea n d o r g a n i z et h ew e bn e w si n f o r m a t i o nf o rd i f f e r e n tu s e r sa c c o r d i n gt ot h e i ri n t e r e s t a i - t i m e sc a nr e t u r nt h es e a r c hr e s u l t sa c c o r d i n gt ot h eu s e ri n t e r e s t t h i sv e r s i o no f a i t i m e si n t r o d u c e st h ef o l l o w i n gn o v e la l g o r i t h m s ：an o v e lo p t i m i z e dc r a w l e r a l g o r i t h mw h o s ef e t c h i n g - s p e e di s6t i m e sf a s t e rt h a nt h a to ft h et r a d i t i o n a lc r a w l e r ；a k e e nt a gb a s e de x t r a c t i o na l g o r i t h mw h i c hc a ne x t r a c tt h ed a t ar i c hc o n t e n tw i t h m i n i m a lm a n u a le f f o r ta n dw h i c ha l s oa l l o w sd a t at ob ec l a s s i f i e da si m p o r t a n to rn o t i m p o r t a n ts ot h a tt h ec r a w l e rc a nr e v i s i ta n du p d a t ei m p o r t a n td a t a ；am o d i f i e dv e c t o r s p a c e m o d e l i m p r o v e du s i n gq u e r ye x p a n s i o n ar e d u n d a n c y i n f o r m a t i o n r e c o m m e n d a t i o na l g o r i t h mi sp r e s e n t e d s i m u l a t i o nt e s t sp r o v e dt h a ts u c ha r c h i t e c t u r e a n da l g o r i t h mc o u l ds e a r c hr e l e v a n ti n f o r m a t i o nf o ru s e r se f f e c t i v e l ya c c o r d i n gt o u s e r s i n t e r e s ta n dh a v ea n dh a v es u p e r i o ra d a p t a b i l i t y k e y w o r d s ：p e r s o n a l i z a t i o n ； v e c t o r s p a c em o d e l ；r e d u n d a n c yi n f o r m a t i o n r e c o m m e n d a t i o n ；u s e ri n t e r e s t ；a g e n t 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用它人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均己在文中以明确方式 标明。 本声明的法律责任由本人承担。 论文作者签名：毖逸 e l 期：迦丝e 鲷望囡 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权 归属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规 定，同意学校保存或向国家有关部门或机构送交论文的纸质版和电子 版，允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用任何复制手段保 存和汇编本学位论文。本人离校后发表、使用学位论文或与该论文直 接相关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：勉透导师签名：垫型日期：丞堕盘一翊i j 目 第l 章绪论 1 绪论 伴随着计算机技术和网络技术的发展与普及，网上信息出现了爆炸式增长， 人们可以自由获取全球范围内的信息而不受地域的限制。人们借助搜索引擎进行 信息查找。在信息搜索领域，搜索引擎的概念已不陌生，但是以“为最广泛的人 群提供信息查询服务”作为基本宗旨的“通用搜索引擎”，已经不能满足人们的信 息需求。通用搜索引擎虽然功能强大，但存在一些缺陷，如索引库更新不及时、 响应速度慢等，而且没有对检索结果根据用户的个人需求做过滤处理。通用搜索 引擎缺乏智能，所提供的检索结果中许多是与用户检索意图无关的信息。由于 i n t e m e t 是一个丌放、分布的信息空间，网上资源以指数速度增长，用户进行信 息检索经常会出现“信息过载”和“资源迷向”。现有的搜索引擎己越来越难以满足 人们高质量地获取网络信息的需求。因此，帮助i n t e m e t 用户根据个人的兴趣， 自动查找信息，屏蔽不相关信息，即提供网络环境下的个性化信息服务，已成为 当前网络信息检索的重要课题。因为个性化服务是指针对不同用户提供不同的服 务策略和服务内容的服务模式。与不区分用户的普通服务模式相比，个性化服务 显然具有更高的服务质量。因此，研究丌发一个由用户自主定制的个性化智能搜 索引擎具有重要的意义。 1 1 论文研究的背景及意义 我们f 从“信息时代”走进“信息经济时代”。“信息时代”强调信息本身的价 值，认为只要解决信息资源的短缺问题就会带来价值的提升；而“信息经济时代” 认为信息并不稀缺，相反，信息技术特别是互联网的出现f 在使信息泛滥，以前 视为宝贝的信息正在走向“垃圾化”，只有解决了信息的甄别、加工、提纯和挖掘， 只有从巨量的、形如垃圾的信息中发现真f 的知识，才能带来价值的提升。i n t e m e t 上的“信息迷失”和“资源过载”问题已经同趋严重。信息迷失即浏览者在i n t e r n e t 复杂的网状信息空间中迷失方向，不知道它们现在所处的信息空间中的位置，无 法返回某个节点，忘记了它们最初的目标。信息过载则是由于i n t e m e t 提供的信 息的复杂性、广泛性和没有考虑到浏览者的知识水平、认知能力，造成浏览者无 法正常理解和使用信息。 兰州人学硕 j 学位论文 法砸常理解和使用信息。 传统的搜索引擎为用户使用i n t e m e t 资源提供了些可行的途径。然而，相对 于巨大、无序的i n t e m e t 信息空间，每个用户真正感兴趣的信息非常有限，仅仅 是i n t e m e t 信息空间的沧海一粟。在传统搜索引擎服务模式下，为了找到真j 下感 兴趣的信息，用户要耗费大量的时间和精力。当用户输入关键词后，搜索引擎返 回的结果往往成百上千，其中包含大量与用户兴趣不相关、重复、甚至是过时的 信息。由于每个用户的兴趣不同，从中找出真f 感兴趣的信息是一个既耗时又耗 力的过程。 而且，由于每个用户感兴趣的信息不同，相应地其所关注的信息子 空间就不尽相同。然而传统搜索引擎服务没有考虑用户的差异，使得每个用户面 对同样的信息空间。显然，传统的“人找信息”【lj 的服务模式已经越来越难以适应 迅速增长的i n t e m e t 信息资源，用户迫切需要一种能够根据用户的特点自动组织 和调整信息的服务模式，个性化服务应运而生。 现在互联网已从存储、交换和处理信息为特征的信息时代，演进到以发现、 整理和抽取信息为特征的需求信息时代。这使互联网演化成一个智能的、主动的、 个性化的神经网络。人们不再满足于亲自借助传统搜索引擎和其他门户网站去找 寻自己感兴趣的信息，而是希望自动获得自己需要的信息。即从“人找信息”的模 式转变成了“信息找人”的信息提供模式。只要用户把需要的信息告诉系统，系统 就会按照要求进行操作，然后把你需要的信息发给你，而且是延续不断地提供信 息。根据用户个人独特的信息需求，从互联网上搜索出有关的信息，并将它们整 合在一起，以便有针对性地满足各种不同用户的信息需求，这种个性化智能搜索 引擎的研究已成为下一代搜索引擎的研究热点。互联网的发展正在导致信息提供 和传递的“公共化”，信息提供和传递的商业价值正在消减，事情的关键不是能否 快速、海量地提供和传递信息，而是能否在期望的时间和地点，以期望的方式和 成本，获取所期望的信息；亦就是说，商业价值的重点正在从信息的“发送端” 向“接收端”延伸和转移；或者说，在当今的互联网上，帮人有效地接收信息较之 帮人有效地发送信息至少同等重要。 这就使的互联网的搜索引擎技术要从帮助用户发现信息、信息处理，再到信 息私有，继而帮助用户到知识发现提升知识的价值。而让信息和知识从孤立、分 离到协同、整合的过程。这就是搜索引擎新的发展方向。个性化信息检索系统增 2 第l 章绪论 论文通过对具体个性化智能搜索引擎系统a it i m e s 的设计和实现，并对传统 的搜索引擎的一些算法做了改进。在前人的工作基础上，提出了成长性在用户层 面的设计模型。通过实验证明，较好地适应了用户多变和独特的个性化要求。 1 2 国内外研究现状 随着信息技术的进步和网络的不断扩大，信息资源在全球范围得到了共享。 为了更有效地利用资源，个性化的查询服务变得越来越重要。因此，i n t e m e t 上 的个性化服务系统必须具备三个能力，即用户模型能很好地反映用户的兴趣偏 好；为适应用户偏好的变化，用户模型能作适应性的改变；自动寻找相关领域信 息源，主动向用户提供推荐服务。目前，国内外已经研究出许多个性化的服务系 统，首先国外的主要有以下几种【2 】。 m e t a c r a w l e r 系统是w a s h i n g t o n 大学丌发的基于i n t e r n e t 中八个搜索引擎的 元搜索引擎系统。它提供了统一的接口，用户将查询请求提交给m e t a c r a w l e r ， 它在通过成员调度策略转给其它各个搜索引擎，最后把结果以统一的形式返回给 用户。通过在实际的信息和用户之间生成统一的用户过滤处理层，提高了系统的 灵活性。 p e r s o n a lw e b w a t c h e r 同样提供个性化服务，它通过适应用户的变化要求从而 更新了用户的偏好。通过学习用户认为感兴趣的链接和人为得到链接，如果系统 认为某些链接是用户感兴趣的，则加亮显示它们，但不足之处在于系统地建议被 限制在一个页面存在的链接上。 l e t i z i a 系统用于在用户浏览时向用户建议其可能感兴趣的链接，这些链接与 用户当前访问的页面内容相关。它主要根据用户浏览行为建立用户模型，虽然减 轻了用户的负担，但是建模的质量并不高。 a m a l t h a e a 系统是一个信息发现的个性化系统，能根据用户的兴趣从分布的 结点上发现有用的信息并进行筛选，并以摘要的形式提交给用户。在运行过程中， 如果用户的兴趣发生改变，根据用户的反馈来修改用户模型。 i n q u i r u s 2 ( n e c 研究院) 是一个元搜索引擎，只有自己的用户界面和搜索机 制，真正的搜索工作是由其它的搜索引擎完成的。与普通的元搜索引擎的不同在 于增加了用户的偏好，用户可以选择自己所需要使用的类别作为附加信息，然后 兰州人学颂j ：学位论文 制，真f 的搜索工作是由其它的搜索引擎完成的。与普通的元搜索引擎的不同在 于增加了用户的偏好，用户可以选择自己所需要使用的类别作为附加信息，然后 i n q u i r u s 2 会根据这个附加信息来选择要使用的搜索引擎并指导搜索的过程，这样 就得到比单纯的关键字搜索更有价值的搜索结果。每一个关键字都由于用户选择 的搜索类别不同可能会提交给不同的搜索引擎，最后根据这些附加的偏好信息对 搜索结果进行筛选，返回与用户偏好最为接近的结果。这种基于用户偏好的筛选 过程使得相同的关键字对于不同的用户可能会得到不同的结果。目前，i n q u i r u s 2 已经投入使用，得到了较好的搜索结果。 国内主要代表性的研究有南京大学研究的d o l t r i a g e n t 3 1 。南京大学多媒 体技术研究所经三年努力，推出了一种个性化信息搜索引擎d o l t r i a g e n t 。该 系统将主体技术应用于网络信息搜索，其主要的特征是具有学习功能，能够在信 息交互中获取用户的信息，包括用户的兴趣、爱好和思维方式，在此前提下，系 统可以主动、定期为用户查找信息，并根据用户搜索信息的变化调整“知识库” 中的通用字和关键字，使之能够有效地适应专门领域的信息管理。系统的本地信 息库还可以对搜索到的信息进行分类存储和管理，并具有与其它系统的协作功 能。 中国万网的3 6 5 a g e n t ，在竞争情报领域推出“智能信息代理人”理念。3 6 5 a g e n t 产品后来重组为“中国网络情报中心”，为麦当劳、肯德基等知名跨国企业以及国 内企业提供全程网络情报服务。强调情报的个性化色彩，每个用户都可以订制个 性化的情报需求。 近几年，个性化服务逐渐从学术研究走向实际应用，成为业界的热点概念。 很多公司纷纷推出个性化系统，提供个性化服务。很多网站，如m i c r o s o f t 、a o l 、 c n n 、l y c o s 、i b m 等，均推出了个性化功能；很多电子商务网站也注意到了个 性化服务的巨大商机，开始提供个性化服务，如a m a z o n 、e b a y 、b e s tb u y 、e x p e d i a 等：我国的部分网站( 如新浪网) 也推出了个性化服务。 i n t e m e t 的迅速发展和i n t e m e t 资源的指数增长使得个性化服务脱颖而出。个 性化服务已经成为网络技术和智能信息处理中新的研究热点。经历了多年的发 展，个性化服务虽然还不甚成熟，但已经真真切切地走进了我们的生活，为广大 用户和网络公司带来益处。 4 第l 章绪论 1 3 论文主要研究内容 论文研究的对象是一个可成长性的个性化智能搜索引擎a it i m e s 的设计实 现，同时对传统搜索引擎的一些算法做了改进，并提出了冗余信息推荐的概念， 从而使建立的用户兴趣模型更具有成长性和适应性。主要研究的内容分为两部 分： 第一部分主要介绍了个性化智能搜索引擎基础，包括： 搜索引擎的基本原理及a it i m e s 中用到的基础理论和算法； 搜索引擎传统算法的描述和缺点： 第二部分介绍了个性化智能搜索引擎a it i m e 的设计与实现，包括： a it i m e s 中的一些优化算法； 用户兴趣模型的设计： 具有冗余信息推荐功能的用户查询a g e n t 的设计。 1 4 论文研究的思路 通过对目前个性化智能搜索引擎的分析可以得出：最大程度的适应用户的独 特需求是个性化搜索引擎成功的关键。用户需求的多样性与用户要求的变化性， 就要求有一种机制可以灵活地适应系统通用性和客户需求个性化之间的矛盾。 通过对目前网络技术的分析，认为a g e n t 技术是较为容易地满足不易改变的 整体系统架构，与需要不断变化的用户需求层面之间矛盾的一种方法。因此，本 文对于a g e n t 技术在用户层面的应用问题进行了分析，提出了一种可成长的用户 兴趣模型结构。 1 5 论文结构 全文共分为5 章，具体的章节内容安排如下t 第1 章是绪论，介绍了论文研究的背景和意义，概述了当前个性化信息服务 的发展状况，最后介绍了本文的研究内容和组织结构。 兰卅1 人学硕 ：学位论义 第2 章是搜索引擎的综合研究，主要内容包括：通用搜索引擎的基本概念， 工作流程，工作原理，现有搜索引擎的缺陷等等。 第3 章是个性化智能搜索引擎a it i m e s 中应用的相关基本理论与算法，着重 分析了传统方法的一些缺陷，和自己的改进思路， 第4 章是个性化智能搜索引擎a it i m e s 的设计，重点介绍了一些优化的算法， 同时给出了系统整体框架和具体的设计步骤以及实验分析。 第5 章笔者对全文的工作进行了总结，并提出了本文进一步的研究方向。 1 6 论文创新点 1 ) 改进了一些搜索引擎的传统算法，如优化的网络爬虫，基于关键标签的 信息提取，基于查询扩展的向量空间模型： 2 ) 在用户层面应用a g e n t 技术，提出一个冗余信息推荐算法，设计出一个 具有可成长性的用户智能查询a g e n t 模型。 6 第2 章个性化智能搜索0 l 擎皋础 2 个性化智能搜索引擎基础 本文研究的是一个个性化智能搜索引擎，个性化智能搜索引擎是在传统搜索 引擎基础上改进发展而来，它依然具备通用搜索引擎的基本功能；为此，为了更 好地阐述个性化智能搜索引擎，就需要先对传统搜索引擎做一个简单的介绍。 2 1 搜索引擎概述 搜索引擎是一种在w e b 上应用的软件系统，在对网络上的信息进行处理和 组合后，为用户提供w e b 信息查询服务；帮助用户从数以亿计的网络信息中找 到自己所需要的信息；引领用户在浩瀚的网络信息资源中寻找真正所需的重要工 具。从用户角度来看，它只需通过浏览器提交一些词或短语到搜索界面，就可以 返回一个与用户输入内容相关的信息列表，列表中的每一个条目项代表一篇网 页。其中每个条目项，至少包括三个元素：标题( 指明网页内容的主题) 、u r l ( 网页对应的访问地址) 与摘要( 网页内容的浓缩与概括) 。通过这些，用户对 相应的网页做出判断，找出自己需要的条目项，点击u r l ，从而得到该网页的 全文。 1 9 9 0 年加拿大麦吉尔大学( u n i v e r s i t yo f m c g i l l ) 计算机学院的师生开发了 一个叫a r c h i e 的软件，它通过定期搜集并分析f t p 系统中存在的文件名信息， 提供查找分布在各个f t p 主机中文件的服务。由于它的工作方式，如：自动搜 集分布在广域网上的信息，建立索引，提供检索服务等与现在意义上搜索引擎的 工作方式相同，因此人们公认a r c h i e 为现代搜索引擎的鼻祖。 1 9 9 3 年m a t t h e wg r a y 丌发了世界上第一个利用h t m l 网页之间的链接关系 来监测w e b 发展规模的“机器人”( r o b o t ) 程序。这种程序有时也称为“蜘蛛” ( s p i d e r ) 。现代搜索引擎的思路源于w a n d e r r ，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 。随着信息技术的发展，不断涌现出很多著名的搜索引擎。如： g o o g l e ，h t t p ：w w w g o o g l e c o m ；a s kj e e v e s ，h t t p ：w w w a s k j e e v e s c o m ； h o t b o t ，h t t p ：w w w h o t b o t c o m ；t e o m a ，h t t p ：w w w t e o m a c o m b a i d u ( 百度) ，h t t p ：w w w b a i d u c o m ；t i a n w a n g ( 天网) ，h t t p ：e p k u e d u c n 兰州人学硕i ：学位论文 1 9 9 7 年1 0 月提供搜索服务的天网是中国最早的搜索引擎，而于2 0 0 0 年推 出的百度，是目前在中国最成功的一个商业搜索引擎。 通过检索机制可以将搜索引擎划分为目录型、检索型和混合型三种： ( 1 ) 目录型搜索引擎：目录型搜索引擎主要采用人工或者机器搜索w e b 信息， 然后依靠专业人员对搜集到的信息进行甄别、筛选、分类和加工而建立起来以分 类导航为目的的搜索引擎。这种类型的搜索引擎类似于传统信息检索中以分类法 的分类目录指导检索的方式，符合人们信息检索的概念由宽泛到专指的渐进思维 习惯，比较适合于那些对自身信息需求不是很明确，从而导致无法精确地确定概 念需求，且网络检索经验不足的用户使用。该类搜索引擎因导入了人工智能，所 以信息准确、导航质量高，但是它需要人工介入、维护量大、信息量少和信息更 新不及时，这样就造成了目录型搜索引擎所建立的数据库规模小，某些类目下收 集的信息数量有限且难以随时更新等缺陷。目录索引中最具代表性的莫过于大名 鼎鼎的y a h o o 。国内的搜狐、新浪、网易搜索也都属于这一类。 ( 2 ) 检索型搜索引擎：检索型搜索引擎与目录型搜索引擎主要依靠人工编辑 信息的工作原理不同，检索型搜索引擎主要由网络搜索器自动定期遍历各类网 站，自动收集网页信息进行检索建库并提供全文检索。此类搜索引擎利用最新网 络信息发现技术，不仅可以快速地收集分布于全球各网站的信息，还可以及时发 现新的网站网页内容并剔出已经废弃的网站网页，即时更新和完善自身的数据 库，因此主体搜索引擎的数据库规模可以做的相当庞大。数据的时效性也可以得 到有力保障，这就大大提高了用户对网络信息的查全率、及时性和有效性。检索 搜索引擎是名副其实的搜索引擎，国外代表性的有g o o g l e 、f a s ta l lt h ew e b 、 a l t a v i s t a 和i n k t o m i 等，国内著名的有百度。从搜索结果的来源角度，全文搜索 引擎又可细分为两种：一种是拥有自己的检索程序，办就是“蜘蛛”或“机器人”程 序，并自建网页数据库，搜索结果直接从自身的数据库中调用；另一种则是租用 其它搜索引擎的数据库，并按指定的各式排列搜索结果，如l y c o s 搜索引擎。 ( 3 ) 混合型搜索引擎：混合型搜索引擎兼有检索型和目录型两种检索方式， 既可输入检索词查找特定资源，又可以浏览目录了解某个范围的资源。 通过检索特性也可以将搜索引擎划分为独立型搜索引擎和元搜索引擎： 独立型搜索引擎：独立型搜索引擎一般捌有自己的索引数据库，可向用户提 8 第2 章个性化智能搜索一j i 擎基础 供基于自身索引库的查询服务，并根据数据库的内容反馈出相应的查询信息或链 接站点。上面提到的常见目录式搜索引擎，如y a h o o 、e x c i t e 和a l t a v i s t a 等均属 于独立型搜索引擎。 元搜索引擎：一般浼来，它没有自己的网页索引数据库，只给用户提供一个 集成的查询界面，用户的查询请求输入后，经它加工处理转发给相应的多个独立 的搜索引擎，真正的查询过程由它所调用或链接的多个搜索引擎完成，而从多个 多利搜索引擎查询到的结果经处理后以统一的形式返回给用户。目前著名的元搜 索引擎有d o g p i l e ( h t t p ：w w w d o g p i l e c o m ) p r o f u s i o n ( h t t p ：w w w p r o f u s i o n c o m ) 等， 中文元搜索引擎中具有代表性的有力维搜索( w w w w i d e w a y s e a r c h c o m ) 在搜索结 果排列方面，有的直接按来源引擎排列搜索结果，又得则按自定的规则将结果重 新排列组合【4 1 。 这罩要注意一点：网页搜索引擎与网站搜索引擎不同，一般来讲，前者的信 息搜索会更全面些，后者则会更准确些。除了以上的分类，还有各种如：主题搜 索引擎，个性化搜索引擎，问答式搜索引擎等不同种类的搜索引擎。 2 2 搜索引擎基本工作流程 搜索引擎大致上被分成三个功能模块( 或者三个子系统) ：网页搜集、预处 理和查询服务。在实践中这三个部分是相互独立，它们的工作形成了搜索引擎卫秽 作的三个阶段，通常分别由人工启动。从而形成通常意义所说的三段式工作流程： 如图2 1 所示。 2 3 网页搜集 图2 1 二段式i ：作流稃 f i g u r e2 1e x e c u t i o nf l o wo ft h r e es e g m e n t s 搜索引擎面对的数据源对象是动态变化的海量网页，网页的获得必须通过一 定的策略从网络上抓取。网络蜘蛛是搜索引擎的一个重要的模块，它是一个自动 9 兰州人学颁f ：学位论义 收集网页的程序。一般来说，搜集网页是有一个搜集周期，这个周期可以依据不 同的搜集策略，以及相应的搜索引擎自身特点的不同而不同。在具体搜集过程中， 采取网络蜘蛛的“爬取”方法。即：从给定起始u r l 集合s 丌始，沿着网页中的 链接，按照不同的策略来遍历，网络蜘蛛的运行可以抽象为一个有向图的遍历过 程。通常有先深、先宽等遍历策略。网络蜘蛛为实现其快速地浏览整个互联网， 通常在技术上采用抢先式多线程技术实现在网上搜索信息。通过抢先式多线程的 使用，你能索引一个基于u r l 链接的w e b 页面，启动一个新的线程跟随每个新 的u r l 链接，索引一个新的u r l 起点。当然在服务器上所开的线程也不能无限 膨胀，需要在服务器的f 常运转和快速收集网页之间找一个平衡点。 研究表明，按照先宽搜索方式得到的网页集合要比先深搜索得到的集合重 要。结合系统的特点，所以我们设计的a it i m e s 系统采用了先宽策略。 2 4 预处理 通过搜集得来的海量原始网页，还必须通过预处理形成好的数据结构，这样 才能成为用户提供查询服务的核心和关键。现行的最有效的数据结构是倒排文件 ( i n v e r t e df i l e ) 即用文档中所含的关键词做索引，文档作为索引目标的一种结构。 预处理中主要包括下面四个方面： 关键词的提取在有大量h t m l 标签的网页文件中，依照一定的规则， 提取出可以代表网页内容的关键词。即提取后得到一个关键词集p ( t l , h ，t n , ) 用这个词集代表网页内容。 排重w 曲上的信息重复现象很普遍，为了节省系统资源与丌销。要尽 可能消除内容重复或主题重复的网页，也就是说去消除通常所说的镜像网页和转 载网页，目前较成功的消重是用关键词匹配结合向量空间模型的方法来完成的。 a it i m e s 系统也使用了这种方法。 链接分析人们可以通过分析h t m l 文档中所含的指向其它文档的链接 信息，来判断网页之间的关系以及网页的内容。 网页重要程度计算这罩指的是在预处理中网页的重要性判断，与后面 要说的用户查询所得的网页重要性不同。即与用户的查询无关。例如用g o o g l e 的核心技术p a g e r a n k 就可以体现出这种重要性。 l o 第2 章个性化智能搜索哼l 擎蕞础 2 5 查询服务 在倒排文件的基础上，给出与用户提供的关键词相对应的文档集合，这罩是 最可以体现个性化和智能化的地方。我们在这里做了大量工作，后面有详细的论 述。通常的查询服务有以下几个方面： 用输入的词和短语表达信息需求，得到一个包含该词或短语的网页这是 一个通常的做法，但是要形成更确切的信息，传统的方法就无能为力，我们在 a it i m e s 系统中采用了更加灵活，可成长的基于用户兴趣向量的方法。 对结果排序列表是最常见的形式，即用查询词与结果文档的相关性形 成顺序。因为面对常常是数以十万计的返回结果，用户一般只会去点击排在前一 百位的搜索结果。因此搜索引擎最关注的不是如何返回尽可能多的结果，而是尽 可能的将最有可能与用户搜索请求相关的链接放在前一百位。通常使用词频和文 档频率结合其他的指标来确定查询结果排序。如用：p a g e r a n k 方法。 文档摘要从正文中生成的摘要是结果条目三个基本元素之一。主要有 两种方式：一种为静态方式，在预处理过程中实现，与查询项无关。另一种为动 态摘要，即在响应查询的时候，根据查询词在文档中的位置，提取周围的文字， 在显示时将查询词标亮。这是目前大多数搜索引擎采用的方式。为了保证查询的 效率，需要在预处理阶段分词的时候记住每个关键词在文档中出现的位置。 2 6 通用搜索引擎的体系结构 如图2 2 所示： 兰州人学颂l ：学位论文 己量 图2 2 通州搜索引擎体系结构 f i g u r e 2 2t h ea r c h i t e c t u r eo fg e n e r a ls e a r c he n g i n e 搜索器的功能是在i n t e r n e t 中漫游，发现和搜集信息。它要尽可能多、尽可 能快地搜集各种类型的新信息，同时因为i n t e m e t 上的信息更新很快，所以还要 定期更新已经搜集过的旧信息，以避免死链接；索引器的功能是理解搜索器所搜 索到的信息，从中抽取出索引项，用于表示文档以及生成文档集的索引表；检索 器的功能是根据用户的查询在索引库中快速检索出文档，进行文档与查询相关度 评价，对将要输出结果进行排序，并实现某种用户相关兴反馈机制；用户接口的 作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。主要目的是方 便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时地信息。 搜索引擎的工作原理简言之，即信息采集软件从个已知的文档集中读取信息， 并检查这些文档的链接指针，指出新的信息空问，然后取出这些新空间的文档， 将它们加入到索引数据库，检索器通过索引数据库为用户的查询请求提供服务。 1 2 第2 幸个性化智能搜索一j l 擎苯础 现有搜索引擎的缺陷 现在已经存在的搜索引擎本身并不够理想，它们本身有以下四个方面的缺陷。 ( 1 ) 覆盖率不高：首先，目日i 没有一个搜索引擎能够覆盖所有的w w w 资源， 而且大部分搜索引擎的索引平均只能涉及到整个w w w 资源5 2 0 左 右。 ( 2 ) 查准率不高：网上的信息相当丰富，据文献f 5 1 介绍，目前网上有6 5 亿网 页。现在搜索引擎问题不再是能找到多少文献，而是找到了太多的文献， 且很多文献不一定与用户要求相关性大。因此提高查准率是搜索引擎查 询效率的主要体现。 ( 3 ) 索引数据库往往很大而且响应时间长：为了增强搜索引擎的功能、提高 查全率和查准率，随着i n t e m e t 的迅速发展，搜索引擎的索引数据库的规 模不断扩大，以关键词检索而著称的a l t a v i s t a 宣称其索引数据库已索引 了1 4 亿个页面，容量超过2 0 0 g ，覆盖率为2 7 3 f 6 1 。可见索引数据库组 织和管理难度之大。因为它除了数据增加以外还需要有数据的删除和修 改功能。如何对大量的、非结构化的信息进行增、删、改操作也是一个 值得研究的问题。 ( 4 ) 索引数据库的索引失败：因为索引数据库的庞大，其组织与维护都较为 困难，而且有些网页的更新更快，搜索引擎的索引数据库的更新频率往 往跟不上，所以找不到搜索引擎返回结果中所指的页面，这是索引失败 的结果。 ( 5 ) 同一搜索引擎的搜索结果中存在重复内容：根据搜索引擎的结果来看， 几乎所有的搜索引擎返回的查询结果中都有重复内容，有些是因为同一 内容被不同的网站收入，搜索程序没有很好地识别；但又些甚至于在同 一返回页面中出现两条或两条以上的同一网址的内容。 ( 6 ) 对动态网页的处理能力弱：目前许多搜索引擎的查找对象仅仅为可访问 的静态页面，对于有些用于生成动态页面的后台数据库还不能访问或访 问效果不好，搜索引擎的搜索范围应扩大到动态页面。 ( 7 ) 语言理解能力差，不能满足用户个性化的需求：没有考虑用户的差异。 对于任何用户，只要输入的关键词相同，返回的检索结果就完全相同。而 兰州人学颂i j 学位论义 实际上，不同的用户由于背景知识、兴趣爱好等方面的不同，需要的信息 往往是不同的。 1 4 第3 章个性化智能搜索0 l 擎a tt i m e s 中心用的相关皋奉理论j 算法 3 个性化智能搜索引擎a it i m e s 中应用的相关基本理论与算法 3 1 新闻信息检索 在新闻信息检索上有很多学者做了大量的研究工作f 7 8 纠。如：a r i k i 和 s u g i y a m a t 7 1 提出了一个利用关键字对电视新闻主题分类的系统。r e n a l s l 8 】等人提 出了一个t h i s l 新闻信息检索系统。a g g a r w a l 9 1 提出了一个w w w 信息检索和抽 取系统。这些文献阐述了新闻信息检索的整体结构，然而，他们都没有从细节上 描述系统的核心模块如：爬虫模块，自动摘要模块等等。 3 2 数据提取 文本网页的表现形式是一种具有基于信息显示的h t m l 规范结构的非结构化 的方式，因此网页信息是一种组织上规范但内容并不规范的半结构化信息。 h t m l 有一套自己的语法，通过不同的命令标识符来表示不同的字体、颜色、 位置等版式。如何从这种半结构化的信息中抽取出用户感兴趣的信息，并以一种 结构化的形式来表征信息内容，以使用户能够在互联网上的海量w e b 信息中快速 准确地定位到其所要查找的内容上，是一项非常复杂的问题。m u k h e r j e e t l 0 】等人 提出了一个将一个h t m l 文件分为一个语义树的结构。这种方法不能处理所有类型 的网页。也有人f l l j 提出基于标签的信息抽取法则，这个法则对于大部分的h t m l 网页是有效的。 3 3 网页爬虫 b o l d i 等人【1 2 1 介绍了一些如何实现网络爬虫的方法，在这个领域做出的研究 工作有很多。b u z z i t l 3 】提出了一个并行的网络爬虫处理信息的方法。然而这种方 法需要w e b 服务器彼此协作。 网络爬虫利用网页中的超文本链接( h y p e r l i n k ) 来访问网页的，从一个事先制 订好的u r l y o 表开始，这个列表中的u r l 一般是从过去的访问记录旱提取出来 的，通常是一些比较流行的站点和新闻网页，利用h t t p 等标准协议，通过u r l 从一个页面爬行到另一个页面，直到没有满足条件的新的u r l 为止。网络爬虫访 问了一个网页后会对它进行分析，抽取出新的u r l ，将之加到访问列表中，同时， 兰州人学坝t ：q z 位论义 网络爬虫提取的网页将被放入到数据库中。 网络爬虫搜集的信息有很多种，例如h t m l 文件的u r l 、标题、长度、文件 建立的时间、链接数目以及一些多媒体信息等。这些信息都需要网络爬虫自动获 取，其中标题、文件中的超链接数目需要网络爬虫分析h t m l 文件得到，因为 h t m l 文件格式较为固定，所以这些相关信息通过分析文件内容就能获得。网络 爬虫所抓取的信息将被搜索引擎用于建立索引数据库，而它所包含的超链接将被 c r a w l e r 用于访问新文档的起始u r l ，这个过程反复进行，从而使w e b 中的信息得 到收集。 对于网络爬虫来说，抓取下来网页包括各种格式，包括：h t m l 、图片、d o c 、 p d f 、多媒体、动态网页及其它格式等。现在大量应用的是并行爬虫。但这种并 行技术应用与新闻信息检索中，往往对一些不常更新的信息不断访问，造成大量 的无意义系统开销，这里，在a it i m e s 中我们采用了一个优化的网络爬虫模式， 较大的提高了系统的整体运行效率。 3 4m a p r e d u c e 过去几年来，g o o g l e 发布了它的一些底层结构的细节。其中有两个重要的技 术，在处理大数据集上，发挥着重要的作用。一个是实现可靠的数据分布式存储 的g o o g l e 文件系统( g f s ) ，还有一个就是用来处理大数据集的m a p r e d u c e 技术。 d e a na n dg h e m a w a t ”】还专门写了一篇介绍m a p r e d u c e 技术的文章。 m a p r e d u c e 的名字源于这个模型中的两项核心操作：概念”m a p ( 映射) ”和 ”r e d u c e ( 化简) ”，简单的说来，m 印是把一组数据一对一的映射为另外的一组 数据，其映射的规则由一个函数来指定，m a p 操作是独立的对每个元素进行操作， m a p 操作将产生一组全新的数据，而原来的数据保持不变。因此，它是高度并行 的。r e d u c e 操作虽然不j t l l m a p 操作并行性那么好，但是它总会得到一个相对简单 的结果，大规模运算也相对独立，因此也是比较适合并行的。 具体而言，当前的软件实现是指定一个m a p ( 映射) 函数，用来把一组键值 对映射成一组新的键值对，指定并发的r e d u c e ( 化简) 函数，用来保证所有映射 的键值对中的每一个共享相同的键组。 g o o g l e 应用m a p r e d u c e 技术并行安排它们系统中的模块。将任务分割成若 1 6 第3 章个性化智能搜索，j f 擎a it i m e s 中心用的相关幕奉理论i 算法 干个不同的子任务。m a p r e d u c e 不是数据库，而是用于分布式处理的算法技术， 可以用来处理大数据集。由于m a p r e d u c e 在g o o g l e 上的巨大的成功，人们对于 这个技术的兴趣越来越大。一些m a p r e d u c e 的应用已经显示出它的高效性，然 而，传统的m