Web搜索引擎及算法

Web搜索引擎概述、体系结构、排序算法1搜索Web三种形式Specificqueriesencyclopaedia,librariesExploithyperlinkstructureBroadquerieswebdirectoriesWebdirectories:classifywebdocumentsbysubjectsVaguequeriessearchenginesindexportionsofweb2Web信息的特点Web本身：Largevolume:8亿个页面(1999),每两年翻番。Distributed:

分布在280万个WebServer上。Dynamic：created,changed,moved,deletedNo-structure、heterogeneitiy：pictures、audio…Varietyoflanguage:morethan100Duplication:nearly30%Highlinkage:averagelymorethan8linkstoothers.用户Ill-formedqueries:未经专门培训，查询请求短、不精确Widevarianceinusers:每个用户在needs,expectations,knowledge等各方面均不同。Specificbehavior：85%只看第一页、78%nevermodifytheirveryfirstquery.99%的信息对99%的用户是没用的。迫切需要新一代的信息挖掘技术WEBINFORMATIONRETRIEVAL!!!3Web信息检索系统的分类Web搜索引擎元搜索引擎信息检索agent目录用户TheTaxonomyofWebInformationRetrievalSystems4Web信息检索系统的分类Web信息检索系统作为用户层和Web信息层之间的中间层，可以进一步地划分为三个层次，包括：搜索引擎与目录、元搜索引擎、信息检索agent。在层次分类中，每一层都建立在其下各层的基础之上，并向其上各层提供信息检索服务。这些层次分类构成了Web信息检索中的一条生产／消费链：Web信息→搜索引擎与目录→元搜索引擎→信息检索agent→用户。下面，我们对各个层次的特点、设计思想及相互关系分别加以考察。5搜索引擎与目录第一个搜索引擎:WWideWebWorm）[McBryan94]:Colorado大学搜索引擎的基本设计思想是：使用robot遍历Web，将Web上分布的信息下载到本地文档库对文档内容进行自动分析并建立索引检查索引找出与用户查询相匹配的文档（或链接）最为著名的搜索引擎有Google,NorthernLight，AltaVista，Infoseek等。其中，NorthernLight和AltaVista所索引的Web页面都已经超过了100,000,000。6目录目录，例如Yahoo，OpenDirectory，Snap等，与搜索引擎的工作方式不同由人工收集或者由Web站点的作者主动提交文档人工对Web站点和文档进行评价、分类并给出简要描述按照主题分类并以树状的形式对Web信息资源进行组织（浏览）对Web信息资源的分类以及描述信息建立索引（检索）目前Yahoo包含有指向500,000个站点的链接，分布在25,000个分类中。7目录8搜索引擎与目录搜索引擎和目录这两种Web信息检索系统各有所长。通常，由于搜索引擎具有庞大的全文索引数据库，因此适用于检索难以查找的信息或者一些比较模糊的主题；而目录有助于逐步缩小主题或者查找某个主题的常见的、质量较高的信息。由于这两种系统彼此互补，因此将两者特点结合起来的一些混合系统也开始出现LookSmart等。现有的一些著名的搜索引擎和目录也呈现出逐渐融合的趋势。例如，Yahoo在目录检索服务的基础之上，已经开始使用Inktomi的Web全文索引数据库提供与搜索引擎类似的Web信息全文检索服务。9元搜索引擎用户经常需要检索多个系统以改善检索的效果。各个搜索引擎的用户接口是异构的，有其特定且复杂的界面和查询语法，这给用户同时使用多个系统带来了不便。一些研究人员针对这种状况而开发了元搜索引擎，其中比较著名的有MetaCrawler，SavvySearch等。10元搜索第一步：WebserverthatsendsquerytoSeveralsearchenginesWebdirectoriesDatabases第二步

：Collectresults第三步

：Unifythem(Datafusion)Aim:bettercoverage关键问题：TranslationofqueryUniformresult(fusionrankings,e,g,pagesretrievedbyseveralengines)Wrappers1112元搜索引擎主要工作原理：任务分解：元搜索引擎首先对用户的查询请求进行预处理，分别转换为若干个底层搜索引擎能处理的格式，并将其发送给各个搜索引擎。例如，MetaCrawler同时检索Yahoo，LookSmart，AltaVista等九个主要的搜索引擎。信息融合：在各个搜索引擎返回检索结果后，元搜索引擎进行组合，并向用户返回最终的检索结果。优点：建立在搜索引擎的基础之上，因此对于设计人员而言，不需要建立和维护庞大的索引数据库，也不需要使用复杂的检索机制；对于用户而言，提供了一个能够同时查询多个搜索引擎的集成界面，将各个搜索引擎的位置、接口等细节屏蔽了起来，同时也有可能获得更好的检索效果。13信息检索agent搜索引擎、元搜索引擎等的缺点：Web信息检索系统通常作为一种大型的服务器程序运行，同时响应多个用户的请求。这些系统不能够根据用户的兴趣需求来定制检索结果。即使同一个用户，在不同的时期也有所侧重。此外，上述系统的检索工作是用户驱动的，即由用户显式地提出检索请求，系统给出响应。在一段时间中，每个用户的检索需求相对稳定，但上述系统缺乏对Web信息进行监控并在出现用户感兴趣的新信息时主动地通知用户的能力。因此检索活动是一种耗时的、重复活动。14信息检索agent为此，OrenEtzioni等人将人工智能领域中的agent概念和技术应用于到Web信息检索，引入了信息检索agent这种截然不同的Web信息检索系统[Etzioni96]。信息检索agent的功能：能够从用户日常的检索、浏览等行为中学习用户的兴趣、推理用户的需求，并利用搜索引擎等系统提供的现有服务主动地从Web上检索相应信息，甚至能够监控信息源的变化，及时地报告给用户。例如：CarnegieMellon大学开发的WebWatcher[Armstrong95]，Washington大学开发的ShopBot[Doorenbos97]，Stanford大学开发的Fab[Balabanovic97]等。在这些系统中，信息检索工作的开展不需要用户的参与，而由agent利用自身的控制机制、知识等进行任务规划、问题求解，从而实现主动的、个性化的信息检索。15搜索引擎的结构16搜索引擎的结构一般包含六个基本部分：Crawler文档数据库(pagerepository)索引器、索引数据库检索器用户接口。

17搜索引擎的结构crawler：也称为spider、Robot或wander，负责将分布在不同Web服务器上的文档收集到本地文档数据库中。搜索引擎中往往会使用多个Robot进程来并行遍历Web空间，从而提高Web文档收集的效率[Gudivada97]。18搜索引擎的结构索引器：首先对robot下载的文档进行预处理，然后依据所使用的Web信息检索模型对文档进行形式化表示，并建立索引后存储在数据库中以提高系统的检索效率。在建立索引后，Web文档本身就没有用处了，因此有些系统会将其从文档库中删除。索引器的工作应该在Web信息检索系统的后台执行，不能够影响前台检索任务的完成。Web信息是动态变化的，因此索引器和Robot每隔一段时间要重复运行以更新文档数据库、索引数据库[SulivanC]。

19搜索引擎的结构检索器：依据所使用的Web信息检索模型对用户的查询进行分析，并检索索引库来查找匹配文档，同时计算各个文档的相关度。最后，将相关度大于阈值的所有文档按照相关度递减的顺序排列，并返回给用户。

20搜索引擎的结构用户接口：为用户提供可视化的查询输入和结果输出界面。在查询输入界面中，用户按照搜索引擎的查询语法指定待检索词条及各种简单／高级检索条件。在输出界面中，搜索引擎将检索结果展现为一个线性的文档列表，其中包含了文档的标题、摘要和超链等信息。由于检索结果中相关文档和不相关文档相互混杂，用户需要逐个浏览以找出所需文档。21集中式体系结构Crawler-indexer(mostsearchengine)Crawler又称：Robot,spider,wanderer,walker,knowbot原理：Programthattraverseswebtosendneworupdatepagestomainserver(wheretheyareindexed)位置：RunonlocalserverandsendrequesttoremoteserversCentraliseduseofindextoanswerqueries22实例(AltaVista)InterfaceQueryengineIndexIndexerCrawler1998:20multi-processormachines 130GBofRAM,500GBdiskspace23分布式体系结构Harvest:Gatherers:周期性的从多个webserver收集并提取索引信息Brokers一方面，为用户提供检索接口，另一方面，为采集的数据建立索引从gatherers或其他brokers获取信息,增量式更新索引24Harvest体系结构UserBroker复制管理WebsiteObjectcacheGathererBroker25搜索引擎的排序算法布尔和向量空间模型的变种TFIDFplusHyperlinksbetweenpages被检索页指向的页面指向检索页的页面Popularity:指向某页面的超链数目Relatedness:多个页面中的共同超链数目，或，被同类页面引用的页面WebQueryPageRank(Google)HITS(Clever)26使用连接!27Google目前世界上最好的搜索引擎:comprehensiveandrelevantresults最大的索引580millionpagesvisitedandrecordedUseslinkdatatogettoanother500millionpages不同种类的索引用一些小型索引来管理大量的web上最流行的页面（根据Google的连接分析系统）索引刷新Updatedmonthly/weeklyDailyforpopularpages三大数据中心同时提供查询服务twoonWestCoastoftheUS,oneonEastCoast.28Google:年轻的发明人…LarryPage,Co-founder&ChiefExecutiveOfficerSergeyBrin,Co-founder&PresidentPhDstudentsatStanford29Google概述Crawlsthewebtocreateitslistings.结合传统的IR文本匹配技术和linkpopularity分析技术来对搜索结果进行排序.其他搜索引擎也采用linkpopularity分析技术，但没有谁将其发挥到Google的程度.30按引用重要性排序31Google连接URL提交:AddURLpage(noneedtodoa"deep"submit)最好的办法是建立连接，其他站点指向你越多，则越有可能被crawl到，并排在前面.CrawlingandIndexDepth:目标：按月刷新索引,Goole大量利用超链中的信息，即使不对某一页面建立索引，也能在结果中将其返回.超链中的文本与连接指向的页面相关联，即使这些页面本身并未建立索引，也能在结果中将其返回.32Google的相关性(1)Google基于“引用”排序，即根据指向该页面的连接的数量、质量、内容等方面来决定页面在结果中的位置.NumberofLinks如果一个页面被引用越多，说明它越重要.LinkQuality然而数量并不是全部。由一个重要站点来的连接胜过多个未名小站来的连接。33Google的相关性(2)LinkContent在一个连接内或周围的文本信息往往与该连接指向的页面有关。例如，一个页面要想在“travel”方面的排序好，则该页面上需要有许多与“travel”有关的连接。当然，如果该页面的内容本身就是关于“travel”的，也对排序有帮助

Rankingboostsontextstyles粗体字、标题中的字、大号字权重较高。34PageRank算法用法模拟&引用重要性排序:基于这样一个模型：一个浏览者按连接浏览，并偶尔跳出连接，以这种方式访问到某一页面的概率越高，则其引用重要度越高.Userrandomlynavigates从某一页面跳到某一随机页面的概率为p从某一页面沿某一随机连接浏览的概率1-p不用按“后退”按钮的方式返回以前访问的连接Googlefindsasingletypeofuniversally

importantpage—直觉上，即那些以随机方式访问web连接结构，所经常访问到的页面。35PageRank算法PageRank算法主要基于重要性平均分配这一朴素的思想。首先，假定Nu是页面u的出度（u包含的链出页面的数量），而Rank(u)是u的重要性；PageRank认为u通过指向v的直接链接将一部分重要性（量化为Rank(u)/Nu）传递给了v页面，这样，与u类似，所有直接链接到v的页面都将自己的一部分重要性传递给v，累积起来便形成了v的重要性，基于这个思想，通过迭代算法，可以得到所有页面（下载索引的页面）的重要性。

Rank(u)页面uNuRank(v)页面vRank(u)/NuRank(x)/Nx36PageRank算法下面用Rank来表示与所有页面对应的重要性向量，向量的条目用来存放页面重要性的量化值（简称为页面的重要度）。若N是所有Web页面（下载索引的页面）的数量，则将每个页面的重要度初始化为1/N，然后用以下的迭代公式进行Rank的计算（其中Rank的下标表示迭代次数的序号，Bv代表直接对v链接的所有页面的集合):通过数次的迭代计算将得到一个稳定的Rank值，所谓稳定是指两次迭代得到的Rank值的差距小于某个阈值t，用于计算邻近两次Rank的差值的算法很多，比较简单的是基于向量的L1-norm值的计算。（一维向量x的L1-norm值为x中所有条目的绝对值的和：）这样，当采用L1-norm算法时，便意味着Rank的值已经稳定了；不采用阈值t，而指定迭代次数n也是一种结束迭代的方法。

37PageRank算法WjWk2Wk1Wi2Wi1Wi3(1-p)W1n1mpW2n2W3n3++38Google内容管理对所有页面建立全文索引It

gathersallvisibletext.没有考虑元关键字提取页面中最相关部分自动形成页面描述Ifapagehasnodescription,itisprobablybecause

Googlehasneveractuallyvisitedit.39Google垃圾信息处理Linkpopularityranking

systemleavesitrelativelyimmunetotraditionalspamming

techniques.Goesbeyondthetextonpagesto

decidehowgoodtheyare.Nolinks,lowrank.Commonspamideacreatealotofnewpageswithinasitethatlinktoasinglepage,inan

efforttoboostthatpage'spopularity,perhapsspreadingoutthesepagesacrossanetworkof

sites.Unlikelytowork,doreallinkbuildinginsteadwithnon-competitivesitesthatarerelatedtoyours.40Site识别41AltaVista42HITS:HypertextInducedTopicSearch根据用户查询来决定排序方案考虑了指向结果集的页面或被结果集指向的页面ImplementedinIBM;sCleverPrototypeScientificAmericanArticle:43HITS(2)权威（Authorities）:结果集合中多个连接所指向的页面Hub:具有许多外出连接的页面Positivetwo-wayfeedback:好的权威页面来自于从好的HUB指向的连接好的权威页面指向的页面形成HUB页面44AuthoritiesandHubsAuthorities(blue)Hubs(red)45HITS两个循环处理步骤在一组结果页面s中的某个特定主题，分配候选hub和authorities

的初始得分采用当前对authorities的猜测来提高对hubs的估计值－－定位所有好的authorities用更新后的hub信息来修正对

authorities的估计值－－找出好的hub中最频繁指向的页面，并将这些页面定位好的authorities.重复上述迭代过程，直到H(p)和A(p)收敛到结果集S的连接矩阵的principleeigenvector,计算结果用于判定thebestauthoritiesandhubs.H(p)=uS|puA(u)A(p)=vS|vpH(u)46HITSHITS主要用于识别webcommunity47Cybercommunities48GooglevsCleverGoogle独立于查