Web搜索引擎及算法.ppt

1、Web搜索引擎,概述、体系结构、排序算法,搜索 Web,三种形式 Specific queries encyclopaedia, libraries Exploit hyperlink structure Broad queries web directories Web directories: classify web documents by subjects Vague queries search engines index portions of web,Web信息的特点,Web本身： Large volume:8亿个页面(1999),每两年翻番。 Distributed: 分布在

2、280万个Web Server上。 Dynamic：created,changed,moved,deleted No-structure、heterogeneitiy：pictures、audio Variety of language:more than 100 Duplication :nearly 30% High linkage: averagely more than 8 links to others. 用户 Ill-formed queries: 未经专门培训，查询请求短、不精确 Wide variance in users:每个用户在needs,expectations,kno

3、wledge等各方面均不同。 Specific behavior：85%只看第一页、78%never modify their very first query. 99%的信息对99%的用户是没用的。,迫切需要新一代的信息挖掘技术,WEB INFORMATION RETRIEVAL!,Web信息检索系统的分类,Web信息检索系统的分类,Web信息检索系统作为用户层和Web信息层之间的中间层，可以进一步地划分为三个层次，包括：搜索引擎与目录、元搜索引擎、信息检索agent。 在层次分类中，每一层都建立在其下各层的基础之上，并向其上各层提供信息检索服务。 这些层次分类构成了Web信息检索中的一条生

4、产消费链：Web信息 搜索引擎与目录 元搜索引擎 信息检索agent 用户。 下面，我们对各个层次的特点、设计思想及相互关系分别加以考察。,搜索引擎与目录,第一个搜索引擎:WWWW（World Wide Web Worm）McBryan94:Colorado大学 搜索引擎的基本设计思想是： 使用robot遍历Web，将Web上分布的信息下载到本地文档库 对文档内容进行自动分析并建立索引 检查索引找出与用户查询相匹配的文档（或链接） 最为著名的搜索引擎有Google,NorthernLight，AltaVista，Infoseek等。其中，NorthernLight和AltaVista所索引的W

5、eb页面都已经超过了100,000,000。,目录,目录，例如Yahoo，OpenDirectory，Snap等，与搜索引擎的工作方式不同 由人工收集或者由Web站点的作者主动提交文档 人工对Web站点和文档进行评价、分类并给出简要描述 按照主题分类并以树状的形式对Web信息资源进行组织（浏览） 对Web信息资源的分类以及描述信息建立索引（检索） 目前Yahoo包含有指向500,000个站点的链接，分布在25,000个分类中。,目录,搜索引擎与目录,搜索引擎和目录这两种Web信息检索系统各有所长。 通常，由于搜索引擎具有庞大的全文索引数据库，因此适用于检索难以查找的信息或者一些比较模糊的主题；

6、 而目录有助于逐步缩小主题或者查找某个主题的常见的、质量较高的信息。 由于这两种系统彼此互补，因此将两者特点结合起来的一些混合系统也开始出现LookSmart等。 现有的一些著名的搜索引擎和目录也呈现出逐渐融合的趋势。例如，Yahoo在目录检索服务的基础之上，已经开始使用Inktomi的Web全文索引数据库提供与搜索引擎类似的Web信息全文检索服务。,元搜索引擎,用户经常需要检索多个系统以改善检索的效果。各个搜索引擎的用户接口是异构的，有其特定且复杂的界面和查询语法，这给用户同时使用多个系统带来了不便。 一些研究人员针对这种状况而开发了元搜索引擎，其中比较著名的有MetaCrawler，Sav

7、vySearch等。,元搜索,第一步：Web server that sends query to Several search engines Web directories Databases 第二步 ：Collect results 第三步 ：Unify them (Data fusion) Aim: better coverage 关键问题： Translation of query Uniform result (fusion rankings, e,g, pages retrieved by several engines) Wrappers,元搜索引擎,主要工作原理： 任务分解：

8、元搜索引擎首先对用户的查询请求进行预处理，分别转换为若干个底层搜索引擎能处理的格式，并将其发送给各个搜索引擎。 例如，MetaCrawler同时检索Yahoo，LookSmart，AltaVista等九个主要的搜索引擎。 信息融合：在各个搜索引擎返回检索结果后，元搜索引擎进行组合，并向用户返回最终的检索结果。 优点： 建立在搜索引擎的基础之上，因此对于设计人员而言，不需要建立和维护庞大的索引数据库，也不需要使用复杂的检索机制； 对于用户而言，提供了一个能够同时查询多个搜索引擎的集成界面，将各个搜索引擎的位置、接口等细节屏蔽了起来，同时也有可能获得更好的检索效果。,信息检索agent,搜索引擎、

9、元搜索引擎等的缺点： Web信息检索系统通常作为一种大型的服务器程序运行，同时响应多个用户的请求。这些系统不能够根据用户的兴趣需求来定制检索结果。即使同一个用户，在不同的时期也有所侧重。 此外，上述系统的检索工作是用户驱动的，即由用户显式地提出检索请求，系统给出响应。在一段时间中，每个用户的检索需求相对稳定，但上述系统缺乏对Web信息进行监控并在出现用户感兴趣的新信息时主动地通知用户的能力。因此检索活动是一种耗时的、重复活动。,信息检索agent,为此，Oren Etzioni等人将人工智能领域中的agent概念和技术应用于到Web信息检索，引入了信息检索agent这种截然不同的Web信息检索

10、系统Etzioni96。 信息检索agent的功能： 能够从用户日常的检索、浏览等行为中学习用户的兴趣、推理用户的需求，并利用搜索引擎等系统提供的现有服务主动地从Web上检索相应信息，甚至能够监控信息源的变化，及时地报告给用户。 例如：Carnegie Mellon大学开发的WebWatcherArmstrong95，Washington大学开发的ShopBotDoorenbos97，Stanford大学开发的FabBalabanovic97等。 在这些系统中，信息检索工作的开展不需要用户的参与，而由agent利用自身的控制机制、知识等进行任务规划、问题求解，从而实现主动的、个性化的信息检索。

11、,搜索引擎的结构,搜索引擎的结构,一般包含六个基本部分： Crawler 文档数据库(page repository) 索引器、索引数据库 检索器 用户接口。,搜索引擎的结构,crawler ： 也称为spider、 Robot或wander，负责将分布在不同Web服务器上的文档收集到本地文档数据库中。 搜索引擎中往往会使用多个Robot进程来并行遍历Web空间，从而提高Web文档收集的效率Gudivada97。,搜索引擎的结构,索引器： 首先对robot下载的文档进行预处理，然后依据所使用的Web信息检索模型对文档进行形式化表示，并建立索引后存储在数据库中以提高系统的检索效率。 在建立索引后

12、，Web文档本身就没有用处了，因此有些系统会将其从文档库中删除。 索引器的工作应该在Web信息检索系统的后台执行，不能够影响前台检索任务的完成。 Web信息是动态变化的，因此索引器和Robot每隔一段时间要重复运行以更新文档数据库、索引数据库SulivanC。,搜索引擎的结构,检索器： 依据所使用的Web信息检索模型对用户的查询进行分析，并检索索引库来查找匹配文档，同时计算各个文档的相关度。 最后，将相关度大于阈值的所有文档按照相关度递减的顺序排列，并返回给用户。,搜索引擎的结构,用户接口： 为用户提供可视化的查询输入和结果输出界面。 在查询输入界面中，用户按照搜索引擎的查询语法指定待检索词条

13、及各种简单高级检索条件。 在输出界面中，搜索引擎将检索结果展现为一个线性的文档列表，其中包含了文档的标题、摘要和超链等信息。 由于检索结果中相关文档和不相关文档相互混杂，用户需要逐个浏览以找出所需文档。,集中式体系结构,Crawler-indexer (most search engine) Crawler 又称：Robot, spider, wanderer, walker, knowbot 原理：Program that traverses web to send new or update pages to main server (where they are indexed) 位置：

14、Run on local server and send request to remote servers Centralised use of index to answer queries,实例 (AltaVista),1998: 20 multi-processor machines 130 GB of RAM, 500 GB disk space,分布式体系结构,Harvest: Gatherers: 周期性的从多个web server收集并提取索引信息 Brokers 一方面，为用户提供检索接口，另一方面，为采集的数据建立索引 从gatherers 或其他 brokers获取信息,

15、 增量式更新索引,Harvest 体系结构,搜索引擎的排序算法,布尔和向量空间模型的变种 TF IDF plus Hyperlinks between pages 被检索页指向的页面 指向检索页的页面 Popularity: 指向某页面的超链数目 Relatedness: 多个页面中的共同超链数目，或，被同类页面引用的页面 WebQuery PageRank (Google) HITS (Clever),使用连接!,Google,目前世界上最好的搜索引擎: comprehensive and relevant results 最大的索引 580 million pages visited an

16、d recorded Uses link data to get to another 500 million pages 不同种类的索引 用一些小型索引来管理大量的web上最流行的页面（根据Google的连接分析系统） 索引刷新 Updated monthly/weekly Daily for popular pages 三大数据中心同时提供查询服务 two on West Coast of the US, one on East Coast.,Google: 年轻的发明人,Larry Page, Co-founder s Clever Prototype Scientific Americ

17、an Article: ,HITS (2),权威（Authorities）: 结果集合中多个连接所指向的页面 Hub: 具有许多外出连接的页面,Positive two-way feedback: 好的权威页面来自于从好的HUB指向的连接 好的权威页面指向的页面形成HUB页面,Authorities and Hubs,Authorities ( blue ) Hubs (red),HITS 两个循环处理步骤,在一组结果页面s中的某个特定主题，分配候选hub和authorities 的初始得分 采用当前对authorities的猜测来提高对 hubs的估计值定位所有好的 authorities

18、用更新后的hub信息来修正对 authorities的估计值找出好的hub中最频繁指向的页面，并将这些页面定位好的authorities. 重复上述迭代过程，直到H(p)和A(p)收敛到结果集S的连接矩阵的 principle eigenvector, 计算结果用于判定the best authorities and hubs.,H(p) =,u S | p u,A(u),A(p) =,v S | v p,H(u),HITS,HITS 主要用于识别 web community,Cybercommunities,Google vs Clever,Google 独立于查询的方式计算排序值 快速响应

19、. looks only in the forward direction, from link to link.,Clever 为每个搜索主题词组合不同的根集，并在该查询的上下文条件下对这些页面排队. 同时从一个权威页面向后看，看是谁指向自己. 人类天生喜欢建立某些类似hub的东西来表示自己对某一特定主题的专长或喜好。,自治,High performance pattern matching based on Bayesian inference networks Identifies patterns in text based on usage and term frequency that correspond to