Web搜索引擎及算法

Web搜索引擎概述、體系結(jié)構(gòu)、排序算法1搜索Web三種形式Specificqueriesencyclopaedia,librariesExploithyperlinkstructureBroadquerieswebdirectoriesWebdirectories:classifywebdocumentsbysubjectsVaguequeriessearchenginesindexportionsofweb2Web信息的特點(diǎn)Web本身：Largevolume:8億個(gè)頁(yè)面(1999),每?jī)赡攴?。Distributed:

分布在280萬(wàn)個(gè)WebServer上。Dynamic：created,changed,moved,deletedNo-structure、heterogeneitiy：pictures、audio…Varietyoflanguage:morethan100Duplication:nearly30%Highlinkage:averagelymorethan8linkstoothers.用戶Ill-formedqueries:未經(jīng)專門(mén)培訓(xùn)，查詢請(qǐng)求短、不精確Widevarianceinusers:每個(gè)用戶在needs,expectations,knowledge等各方面均不同。Specificbehavior：85%只看第一頁(yè)、78%nevermodifytheirveryfirstquery.99%的信息對(duì)99%的用戶是沒(méi)用的。迫切需要新一代的信息挖掘技術(shù)WEBINFORMATIONRETRIEVAL!!!3Web信息檢索系統(tǒng)的分類Web搜索引擎元搜索引擎信息檢索agent目錄用戶TheTaxonomyofWebInformationRetrievalSystems4Web信息檢索系統(tǒng)的分類Web信息檢索系統(tǒng)作為用戶層和Web信息層之間的中間層，可以進(jìn)一步地劃分為三個(gè)層次，包括：搜索引擎與目錄、元搜索引擎、信息檢索agent。在層次分類中，每一層都建立在其下各層的基礎(chǔ)之上，并向其上各層提供信息檢索服務(wù)。這些層次分類構(gòu)成了Web信息檢索中的一條生產(chǎn)／消費(fèi)鏈：Web信息→搜索引擎與目錄→元搜索引擎→信息檢索agent→用戶。下面，我們對(duì)各個(gè)層次的特點(diǎn)、設(shè)計(jì)思想及相互關(guān)系分別加以考察。5搜索引擎與目錄第一個(gè)搜索引擎:WWideWebWorm）[McBryan94]:Colorado大學(xué)搜索引擎的基本設(shè)計(jì)思想是：使用robot遍歷Web，將Web上分布的信息下載到本地文檔庫(kù)對(duì)文檔內(nèi)容進(jìn)行自動(dòng)分析并建立索引檢查索引找出與用戶查詢相匹配的文檔（或鏈接）最為著名的搜索引擎有Google,NorthernLight，AltaVista，Infoseek等。其中，NorthernLight和AltaVista所索引的Web頁(yè)面都已經(jīng)超過(guò)了100,000,000。6目錄目錄，例如Yahoo，OpenDirectory，Snap等，與搜索引擎的工作方式不同由人工收集或者由Web站點(diǎn)的作者主動(dòng)提交文檔人工對(duì)Web站點(diǎn)和文檔進(jìn)行評(píng)價(jià)、分類并給出簡(jiǎn)要描述按照主題分類并以樹(shù)狀的形式對(duì)Web信息資源進(jìn)行組織（瀏覽）對(duì)Web信息資源的分類以及描述信息建立索引（檢索）目前Yahoo包含有指向500,000個(gè)站點(diǎn)的鏈接，分布在25,000個(gè)分類中。7目錄8搜索引擎與目錄搜索引擎和目錄這兩種Web信息檢索系統(tǒng)各有所長(zhǎng)。通常，由于搜索引擎具有龐大的全文索引數(shù)據(jù)庫(kù)，因此適用于檢索難以查找的信息或者一些比較模糊的主題；而目錄有助于逐步縮小主題或者查找某個(gè)主題的常見(jiàn)的、質(zhì)量較高的信息。由于這兩種系統(tǒng)彼此互補(bǔ)，因此將兩者特點(diǎn)結(jié)合起來(lái)的一些混合系統(tǒng)也開(kāi)始出現(xiàn)LookSmart等?，F(xiàn)有的一些著名的搜索引擎和目錄也呈現(xiàn)出逐漸融合的趨勢(shì)。例如，Yahoo在目錄檢索服務(wù)的基礎(chǔ)之上，已經(jīng)開(kāi)始使用Inktomi的Web全文索引數(shù)據(jù)庫(kù)提供與搜索引擎類似的Web信息全文檢索服務(wù)。9元搜索引擎用戶經(jīng)常需要檢索多個(gè)系統(tǒng)以改善檢索的效果。各個(gè)搜索引擎的用戶接口是異構(gòu)的，有其特定且復(fù)雜的界面和查詢語(yǔ)法，這給用戶同時(shí)使用多個(gè)系統(tǒng)帶來(lái)了不便。一些研究人員針對(duì)這種狀況而開(kāi)發(fā)了元搜索引擎，其中比較著名的有MetaCrawler，SavvySearch等。10元搜索第一步：WebserverthatsendsquerytoSeveralsearchenginesWebdirectoriesDatabases第二步

：Collectresults第三步

：Unifythem(Datafusion)Aim:bettercoverage關(guān)鍵問(wèn)題：TranslationofqueryUniformresult(fusionrankings,e,g,pagesretrievedbyseveralengines)Wrappers1112元搜索引擎主要工作原理：任務(wù)分解：元搜索引擎首先對(duì)用戶的查詢請(qǐng)求進(jìn)行預(yù)處理，分別轉(zhuǎn)換為若干個(gè)底層搜索引擎能處理的格式，并將其發(fā)送給各個(gè)搜索引擎。例如，MetaCrawler同時(shí)檢索Yahoo，LookSmart，AltaVista等九個(gè)主要的搜索引擎。信息融合：在各個(gè)搜索引擎返回檢索結(jié)果后，元搜索引擎進(jìn)行組合，并向用戶返回最終的檢索結(jié)果。優(yōu)點(diǎn)：建立在搜索引擎的基礎(chǔ)之上，因此對(duì)于設(shè)計(jì)人員而言，不需要建立和維護(hù)龐大的索引數(shù)據(jù)庫(kù)，也不需要使用復(fù)雜的檢索機(jī)制；對(duì)于用戶而言，提供了一個(gè)能夠同時(shí)查詢多個(gè)搜索引擎的集成界面，將各個(gè)搜索引擎的位置、接口等細(xì)節(jié)屏蔽了起來(lái)，同時(shí)也有可能獲得更好的檢索效果。13信息檢索agent搜索引擎、元搜索引擎等的缺點(diǎn)：Web信息檢索系統(tǒng)通常作為一種大型的服務(wù)器程序運(yùn)行，同時(shí)響應(yīng)多個(gè)用戶的請(qǐng)求。這些系統(tǒng)不能夠根據(jù)用戶的興趣需求來(lái)定制檢索結(jié)果。即使同一個(gè)用戶，在不同的時(shí)期也有所側(cè)重。此外，上述系統(tǒng)的檢索工作是用戶驅(qū)動(dòng)的，即由用戶顯式地提出檢索請(qǐng)求，系統(tǒng)給出響應(yīng)。在一段時(shí)間中，每個(gè)用戶的檢索需求相對(duì)穩(wěn)定，但上述系統(tǒng)缺乏對(duì)Web信息進(jìn)行監(jiān)控并在出現(xiàn)用戶感興趣的新信息時(shí)主動(dòng)地通知用戶的能力。因此檢索活動(dòng)是一種耗時(shí)的、重復(fù)活動(dòng)。14信息檢索agent為此，OrenEtzioni等人將人工智能領(lǐng)域中的agent概念和技術(shù)應(yīng)用于到Web信息檢索，引入了信息檢索agent這種截然不同的Web信息檢索系統(tǒng)[Etzioni96]。信息檢索agent的功能：能夠從用戶日常的檢索、瀏覽等行為中學(xué)習(xí)用戶的興趣、推理用戶的需求，并利用搜索引擎等系統(tǒng)提供的現(xiàn)有服務(wù)主動(dòng)地從Web上檢索相應(yīng)信息，甚至能夠監(jiān)控信息源的變化，及時(shí)地報(bào)告給用戶。例如：CarnegieMellon大學(xué)開(kāi)發(fā)的WebWatcher[Armstrong95]，Washington大學(xué)開(kāi)發(fā)的ShopBot[Doorenbos97]，Stanford大學(xué)開(kāi)發(fā)的Fab[Balabanovic97]等。在這些系統(tǒng)中，信息檢索工作的開(kāi)展不需要用戶的參與，而由agent利用自身的控制機(jī)制、知識(shí)等進(jìn)行任務(wù)規(guī)劃、問(wèn)題求解，從而實(shí)現(xiàn)主動(dòng)的、個(gè)性化的信息檢索。15搜索引擎的結(jié)構(gòu)16搜索引擎的結(jié)構(gòu)一般包含六個(gè)基本部分：Crawler文檔數(shù)據(jù)庫(kù)(pagerepository)索引器、索引數(shù)據(jù)庫(kù)檢索器用戶接口。

17搜索引擎的結(jié)構(gòu)crawler：也稱為spider、Robot或wander，負(fù)責(zé)將分布在不同Web服務(wù)器上的文檔收集到本地文檔數(shù)據(jù)庫(kù)中。搜索引擎中往往會(huì)使用多個(gè)Robot進(jìn)程來(lái)并行遍歷Web空間，從而提高Web文檔收集的效率[Gudivada97]。18搜索引擎的結(jié)構(gòu)索引器：首先對(duì)robot下載的文檔進(jìn)行預(yù)處理，然后依據(jù)所使用的Web信息檢索模型對(duì)文檔進(jìn)行形式化表示，并建立索引后存儲(chǔ)在數(shù)據(jù)庫(kù)中以提高系統(tǒng)的檢索效率。在建立索引后，Web文檔本身就沒(méi)有用處了，因此有些系統(tǒng)會(huì)將其從文檔庫(kù)中刪除。索引器的工作應(yīng)該在Web信息檢索系統(tǒng)的后臺(tái)執(zhí)行，不能夠影響前臺(tái)檢索任務(wù)的完成。Web信息是動(dòng)態(tài)變化的，因此索引器和Robot每隔一段時(shí)間要重復(fù)運(yùn)行以更新文檔數(shù)據(jù)庫(kù)、索引數(shù)據(jù)庫(kù)[SulivanC]。

19搜索引擎的結(jié)構(gòu)檢索器：依據(jù)所使用的Web信息檢索模型對(duì)用戶的查詢進(jìn)行分析，并檢索索引庫(kù)來(lái)查找匹配文檔，同時(shí)計(jì)算各個(gè)文檔的相關(guān)度。最后，將相關(guān)度大于閾值的所有文檔按照相關(guān)度遞減的順序排列，并返回給用戶。

20搜索引擎的結(jié)構(gòu)用戶接口：為用戶提供可視化的查詢輸入和結(jié)果輸出界面。在查詢輸入界面中，用戶按照搜索引擎的查詢語(yǔ)法指定待檢索詞條及各種簡(jiǎn)單／高級(jí)檢索條件。在輸出界面中，搜索引擎將檢索結(jié)果展現(xiàn)為一個(gè)線性的文檔列表，其中包含了文檔的標(biāo)題、摘要和超鏈等信息。由于檢索結(jié)果中相關(guān)文檔和不相關(guān)文檔相互混雜，用戶需要逐個(gè)瀏覽以找出所需文檔。21集中式體系結(jié)構(gòu)Crawler-indexer(mostsearchengine)Crawler又稱：Robot,spider,wanderer,walker,knowbot原理：Programthattraverseswebtosendneworupdatepagestomainserver(wheretheyareindexed)位置：RunonlocalserverandsendrequesttoremoteserversCentraliseduseofindextoanswerqueries22實(shí)例(AltaVista)InterfaceQueryengineIndexIndexerCrawler1998:20multi-processormachines 130GBofRAM,500GBdiskspace23分布式體系結(jié)構(gòu)Harvest:Gatherers:周期性的從多個(gè)webserver收集并提取索引信息Brokers一方面，為用戶提供檢索接口，另一方面，為采集的數(shù)據(jù)建立索引從gatherers或其他brokers獲取信息,增量式更新索引24Harvest體系結(jié)構(gòu)UserBroker復(fù)制管理WebsiteObjectcacheGathererBroker25搜索引擎的排序算法布爾和向量空間模型的變種TFIDFplusHyperlinksbetweenpages被檢索頁(yè)指向的頁(yè)面指向檢索頁(yè)的頁(yè)面Popularity:指向某頁(yè)面的超鏈數(shù)目Relatedness:多個(gè)頁(yè)面中的共同超鏈數(shù)目，或，被同類頁(yè)面引用的頁(yè)面WebQueryPageRank(Google)HITS(Clever)26使用連接!27Google目前世界上最好的搜索引擎:comprehensiveandrelevantresults最大的索引580millionpagesvisitedandrecordedUseslinkdatatogettoanother500millionpages不同種類的索引用一些小型索引來(lái)管理大量的web上最流行的頁(yè)面（根據(jù)Google的連接分析系統(tǒng)）索引刷新Updatedmonthly/weeklyDailyforpopularpages三大數(shù)據(jù)中心同時(shí)提供查詢服務(wù)twoonWestCoastoftheUS,oneonEastCoast.28Google:年輕的發(fā)明人…LarryPage,Co-founder&ChiefExecutiveOfficerSergeyBrin,Co-founder&PresidentPhDstudentsatStanford29Google概述Crawlsthewebtocreateitslistings.結(jié)合傳統(tǒng)的IR文本匹配技術(shù)和linkpopularity分析技術(shù)來(lái)對(duì)搜索結(jié)果進(jìn)行排序.其他搜索引擎也采用linkpopularity分析技術(shù)，但沒(méi)有誰(shuí)將其發(fā)揮到Google的程度.30按引用重要性排序31Google連接URL提交:AddURLpage(noneedtodoa"deep"submit)最好的辦法是建立連接，其他站點(diǎn)指向你越多，則越有可能被crawl到，并排在前面.CrawlingandIndexDepth:目標(biāo)：按月刷新索引,Goole大量利用超鏈中的信息，即使不對(duì)某一頁(yè)面建立索引，也能在結(jié)果中將其返回.超鏈中的文本與連接指向的頁(yè)面相關(guān)聯(lián)，即使這些頁(yè)面本身并未建立索引，也能在結(jié)果中將其返回.32Google的相關(guān)性(1)Google基于“引用”排序，即根據(jù)指向該頁(yè)面的連接的數(shù)量、質(zhì)量、內(nèi)容等方面來(lái)決定頁(yè)面在結(jié)果中的位置.NumberofLinks如果一個(gè)頁(yè)面被引用越多，說(shuō)明它越重要.LinkQuality然而數(shù)量并不是全部。由一個(gè)重要站點(diǎn)來(lái)的連接勝過(guò)多個(gè)未名小站來(lái)的連接。33Google的相關(guān)性(2)LinkContent在一個(gè)連接內(nèi)或周?chē)奈谋拘畔⑼c該連接指向的頁(yè)面有關(guān)。例如，一個(gè)頁(yè)面要想在“travel”方面的排序好，則該頁(yè)面上需要有許多與“travel”有關(guān)的連接。當(dāng)然，如果該頁(yè)面的內(nèi)容本身就是關(guān)于“travel”的，也對(duì)排序有幫助

Rankingboostsontextstyles粗體字、標(biāo)題中的字、大號(hào)字權(quán)重較高。34PageRank算法用法模擬&引用重要性排序:基于這樣一個(gè)模型：一個(gè)瀏覽者按連接瀏覽，并偶爾跳出連接，以這種方式訪問(wèn)到某一頁(yè)面的概率越高，則其引用重要度越高.Userrandomlynavigates從某一頁(yè)面跳到某一隨機(jī)頁(yè)面的概率為p從某一頁(yè)面沿某一隨機(jī)連接瀏覽的概率1-p不用按“后退”按鈕的方式返回以前訪問(wèn)的連接Googlefindsasingletypeofuniversally

importantpage—直覺(jué)上，即那些以隨機(jī)方式訪問(wèn)web連接結(jié)構(gòu)，所經(jīng)常訪問(wèn)到的頁(yè)面。35PageRank算法PageRank算法主要基于重要性平均分配這一樸素的思想。首先，假定Nu是頁(yè)面u的出度（u包含的鏈出頁(yè)面的數(shù)量），而Rank(u)是u的重要性；PageRank認(rèn)為u通過(guò)指向v的直接鏈接將一部分重要性（量化為Rank(u)/Nu）傳遞給了v頁(yè)面，這樣，與u類似，所有直接鏈接到v的頁(yè)面都將自己的一部分重要性傳遞給v，累積起來(lái)便形成了v的重要性，基于這個(gè)思想，通過(guò)迭代算法，可以得到所有頁(yè)面（下載索引的頁(yè)面）的重要性。

Rank(u)頁(yè)面uNuRank(v)頁(yè)面vRank(u)/NuRank(x)/Nx36PageRank算法下面用Rank來(lái)表示與所有頁(yè)面對(duì)應(yīng)的重要性向量，向量的條目用來(lái)存放頁(yè)面重要性的量化值（簡(jiǎn)稱為頁(yè)面的重要度）。若N是所有Web頁(yè)面（下載索引的頁(yè)面）的數(shù)量，則將每個(gè)頁(yè)面的重要度初始化為1/N，然后用以下的迭代公式進(jìn)行Rank的計(jì)算（其中Rank的下標(biāo)表示迭代次數(shù)的序號(hào)，Bv代表直接對(duì)v鏈接的所有頁(yè)面的集合):通過(guò)數(shù)次的迭代計(jì)算將得到一個(gè)穩(wěn)定的Rank值，所謂穩(wěn)定是指兩次迭代得到的Rank值的差距小于某個(gè)閾值t，用于計(jì)算鄰近兩次Rank的差值的算法很多，比較簡(jiǎn)單的是基于向量的L1-norm值的計(jì)算。（一維向量x的L1-norm值為x中所有條目的絕對(duì)值的和：）這樣，當(dāng)采用L1-norm算法時(shí)，便意味著Rank的值已經(jīng)穩(wěn)定了；不采用閾值t，而指定迭代次數(shù)n也是一種結(jié)束迭代的方法。

37PageRank算法WjWk2Wk1Wi2Wi1Wi3(1-p)W1n1mpW2n2W3n3++38Google內(nèi)容管理對(duì)所有頁(yè)面建立全文索引It

gathersallvisibletext.沒(méi)有考慮元關(guān)鍵字提取頁(yè)面中最相關(guān)部分自動(dòng)形成頁(yè)面描述Ifapagehasnodescription,itisprobablybecause

Googlehasneveractuallyvisitedit.39Google垃圾信息處理Linkpopularityranking

systemleavesitrelativelyimmunetotraditionalspamming

techniques.Goesbeyondthetextonpagesto

decidehowgoodtheyare.Nolinks,lowrank.Commonspamideacreatealotofnewpageswithinasitethatlinktoasinglepage,inan

efforttoboostthatpage'spopularity,perhapsspreadingoutthesepagesacrossanetworkof

sites.Unlikelytowork,doreallinkbuildinginsteadwithnon-competitivesitesthatarerelatedtoyours.40Site識(shí)別41AltaVista42HITS:HypertextInducedTopicSearch根據(jù)用戶查詢來(lái)決定排序方案考慮了指向結(jié)果集的頁(yè)面或被結(jié)果集指向的頁(yè)面ImplementedinIBM;sCleverPrototypeScientificAmericanArticle:43HITS(2)權(quán)威（Authorities）:結(jié)果集合中多個(gè)連接所指向的頁(yè)面Hub:具有許多外出連接的頁(yè)面Positivetwo-wayfeedback:好的權(quán)威頁(yè)面來(lái)自于從好的HUB指向的連接好的權(quán)威頁(yè)面指向的頁(yè)面形成HUB頁(yè)面44AuthoritiesandHubsAuthorities(blue)Hubs(red)45HITS兩個(gè)循環(huán)處理步驟在一組結(jié)果頁(yè)面s中的某個(gè)特定主題，分配候選hub和authorities

的初始得分采用當(dāng)前對(duì)authorities的猜測(cè)來(lái)提高對(duì)hubs的估計(jì)值－－定位所有好的authorities用更新后的hub信息來(lái)修正對(duì)

authorities的估計(jì)值－－找出好的hub中最頻繁指向的頁(yè)面，并將這些頁(yè)面定位好的authorities.重復(fù)上述迭代過(guò)程，直到H(p)和A(p)收斂到結(jié)果集S的連接矩陣的principleeigenvector,計(jì)算結(jié)果用于判定thebestauthoritiesandhubs.H(p)=uS|puA(u)A(p)=vS|vpH(u)46HITSHITS主要用于識(shí)別webcommunity47Cybercommunities48GooglevsCleverGoogle獨(dú)立于查