Web搜索引擎及算法.ppt

1、Web搜索引擎,概述、體系結(jié)構(gòu)、排序算法,搜索 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: 未經(jīng)專門培訓(xùn)，查詢請求短、不精確 Wide variance in users:每個用戶在needs,expectations,kno

3、wledge等各方面均不同。 Specific behavior：85%只看第一頁、78%never modify their very first query. 99%的信息對99%的用戶是沒用的。,迫切需要新一代的信息挖掘技術(shù),WEB INFORMATION RETRIEVAL!,Web信息檢索系統(tǒng)的分類,Web信息檢索系統(tǒng)的分類,Web信息檢索系統(tǒng)作為用戶層和Web信息層之間的中間層，可以進一步地劃分為三個層次，包括：搜索引擎與目錄、元搜索引擎、信息檢索agent。 在層次分類中，每一層都建立在其下各層的基礎(chǔ)之上，并向其上各層提供信息檢索服務(wù)。 這些層次分類構(gòu)成了Web信息檢索中的一條生

4、產(chǎn)消費鏈：Web信息 搜索引擎與目錄 元搜索引擎 信息檢索agent 用戶。 下面，我們對各個層次的特點、設(shè)計思想及相互關(guān)系分別加以考察。,搜索引擎與目錄,第一個搜索引擎:WWWW（World Wide Web Worm）McBryan94:Colorado大學(xué) 搜索引擎的基本設(shè)計思想是： 使用robot遍歷Web，將Web上分布的信息下載到本地文檔庫 對文檔內(nèi)容進行自動分析并建立索引 檢查索引找出與用戶查詢相匹配的文檔（或鏈接） 最為著名的搜索引擎有Google,NorthernLight，AltaVista，Infoseek等。其中，NorthernLight和AltaVista所索引的W

5、eb頁面都已經(jīng)超過了100,000,000。,目錄,目錄，例如Yahoo，OpenDirectory，Snap等，與搜索引擎的工作方式不同 由人工收集或者由Web站點的作者主動提交文檔 人工對Web站點和文檔進行評價、分類并給出簡要描述 按照主題分類并以樹狀的形式對Web信息資源進行組織（瀏覽） 對Web信息資源的分類以及描述信息建立索引（檢索） 目前Yahoo包含有指向500,000個站點的鏈接，分布在25,000個分類中。,目錄,搜索引擎與目錄,搜索引擎和目錄這兩種Web信息檢索系統(tǒng)各有所長。 通常，由于搜索引擎具有龐大的全文索引數(shù)據(jù)庫，因此適用于檢索難以查找的信息或者一些比較模糊的主題；

6、 而目錄有助于逐步縮小主題或者查找某個主題的常見的、質(zhì)量較高的信息。 由于這兩種系統(tǒng)彼此互補，因此將兩者特點結(jié)合起來的一些混合系統(tǒng)也開始出現(xiàn)LookSmart等。 現(xiàn)有的一些著名的搜索引擎和目錄也呈現(xiàn)出逐漸融合的趨勢。例如，Yahoo在目錄檢索服務(wù)的基礎(chǔ)之上，已經(jīng)開始使用Inktomi的Web全文索引數(shù)據(jù)庫提供與搜索引擎類似的Web信息全文檢索服務(wù)。,元搜索引擎,用戶經(jīng)常需要檢索多個系統(tǒng)以改善檢索的效果。各個搜索引擎的用戶接口是異構(gòu)的，有其特定且復(fù)雜的界面和查詢語法，這給用戶同時使用多個系統(tǒng)帶來了不便。 一些研究人員針對這種狀況而開發(fā)了元搜索引擎，其中比較著名的有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 關(guān)鍵問題： Translation of query Uniform result (fusion rankings, e,g, pages retrieved by several engines) Wrappers,元搜索引擎,主要工作原理： 任務(wù)分解：

8、元搜索引擎首先對用戶的查詢請求進行預(yù)處理，分別轉(zhuǎn)換為若干個底層搜索引擎能處理的格式，并將其發(fā)送給各個搜索引擎。 例如，MetaCrawler同時檢索Yahoo，LookSmart，AltaVista等九個主要的搜索引擎。 信息融合：在各個搜索引擎返回檢索結(jié)果后，元搜索引擎進行組合，并向用戶返回最終的檢索結(jié)果。 優(yōu)點： 建立在搜索引擎的基礎(chǔ)之上，因此對于設(shè)計人員而言，不需要建立和維護龐大的索引數(shù)據(jù)庫，也不需要使用復(fù)雜的檢索機制； 對于用戶而言，提供了一個能夠同時查詢多個搜索引擎的集成界面，將各個搜索引擎的位置、接口等細節(jié)屏蔽了起來，同時也有可能獲得更好的檢索效果。,信息檢索agent,搜索引擎、

9、元搜索引擎等的缺點： Web信息檢索系統(tǒng)通常作為一種大型的服務(wù)器程序運行，同時響應(yīng)多個用戶的請求。這些系統(tǒng)不能夠根據(jù)用戶的興趣需求來定制檢索結(jié)果。即使同一個用戶，在不同的時期也有所側(cè)重。 此外，上述系統(tǒng)的檢索工作是用戶驅(qū)動的，即由用戶顯式地提出檢索請求，系統(tǒng)給出響應(yīng)。在一段時間中，每個用戶的檢索需求相對穩(wěn)定，但上述系統(tǒng)缺乏對Web信息進行監(jiān)控并在出現(xiàn)用戶感興趣的新信息時主動地通知用戶的能力。因此檢索活動是一種耗時的、重復(fù)活動。,信息檢索agent,為此，Oren Etzioni等人將人工智能領(lǐng)域中的agent概念和技術(shù)應(yīng)用于到Web信息檢索，引入了信息檢索agent這種截然不同的Web信息檢索

10、系統(tǒng)Etzioni96。 信息檢索agent的功能： 能夠從用戶日常的檢索、瀏覽等行為中學(xué)習(xí)用戶的興趣、推理用戶的需求，并利用搜索引擎等系統(tǒng)提供的現(xiàn)有服務(wù)主動地從Web上檢索相應(yīng)信息，甚至能夠監(jiān)控信息源的變化，及時地報告給用戶。 例如：Carnegie Mellon大學(xué)開發(fā)的WebWatcherArmstrong95，Washington大學(xué)開發(fā)的ShopBotDoorenbos97，Stanford大學(xué)開發(fā)的FabBalabanovic97等。 在這些系統(tǒng)中，信息檢索工作的開展不需要用戶的參與，而由agent利用自身的控制機制、知識等進行任務(wù)規(guī)劃、問題求解，從而實現(xiàn)主動的、個性化的信息檢索。

11、,搜索引擎的結(jié)構(gòu),搜索引擎的結(jié)構(gòu),一般包含六個基本部分： Crawler 文檔數(shù)據(jù)庫(page repository) 索引器、索引數(shù)據(jù)庫 檢索器 用戶接口。,搜索引擎的結(jié)構(gòu),crawler ： 也稱為spider、 Robot或wander，負責(zé)將分布在不同Web服務(wù)器上的文檔收集到本地文檔數(shù)據(jù)庫中。 搜索引擎中往往會使用多個Robot進程來并行遍歷Web空間，從而提高Web文檔收集的效率Gudivada97。,搜索引擎的結(jié)構(gòu),索引器： 首先對robot下載的文檔進行預(yù)處理，然后依據(jù)所使用的Web信息檢索模型對文檔進行形式化表示，并建立索引后存儲在數(shù)據(jù)庫中以提高系統(tǒng)的檢索效率。 在建立索引后

12、，Web文檔本身就沒有用處了，因此有些系統(tǒng)會將其從文檔庫中刪除。 索引器的工作應(yīng)該在Web信息檢索系統(tǒng)的后臺執(zhí)行，不能夠影響前臺檢索任務(wù)的完成。 Web信息是動態(tài)變化的，因此索引器和Robot每隔一段時間要重復(fù)運行以更新文檔數(shù)據(jù)庫、索引數(shù)據(jù)庫SulivanC。,搜索引擎的結(jié)構(gòu),檢索器： 依據(jù)所使用的Web信息檢索模型對用戶的查詢進行分析，并檢索索引庫來查找匹配文檔，同時計算各個文檔的相關(guān)度。 最后，將相關(guān)度大于閾值的所有文檔按照相關(guān)度遞減的順序排列，并返回給用戶。,搜索引擎的結(jié)構(gòu),用戶接口： 為用戶提供可視化的查詢輸入和結(jié)果輸出界面。 在查詢輸入界面中，用戶按照搜索引擎的查詢語法指定待檢索詞條

13、及各種簡單高級檢索條件。 在輸出界面中，搜索引擎將檢索結(jié)果展現(xiàn)為一個線性的文檔列表，其中包含了文檔的標(biāo)題、摘要和超鏈等信息。 由于檢索結(jié)果中相關(guān)文檔和不相關(guān)文檔相互混雜，用戶需要逐個瀏覽以找出所需文檔。,集中式體系結(jié)構(gòu),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,分布式體系結(jié)構(gòu),Harvest: Gatherers: 周期性的從多個web server收集并提取索引信息 Brokers 一方面，為用戶提供檢索接口，另一方面，為采集的數(shù)據(jù)建立索引 從gatherers 或其他 brokers獲取信息,

15、 增量式更新索引,Harvest 體系結(jié)構(gòu),搜索引擎的排序算法,布爾和向量空間模型的變種 TF IDF plus Hyperlinks between pages 被檢索頁指向的頁面 指向檢索頁的頁面 Popularity: 指向某頁面的超鏈數(shù)目 Relatedness: 多個頁面中的共同超鏈數(shù)目，或，被同類頁面引用的頁面 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上最流行的頁面（根據(jù)Google的連接分析系統(tǒng)） 索引刷新 Updated monthly/weekly Daily for popular pages 三大數(shù)據(jù)中心同時提供查詢服務(wù) two on West Coast of the US, one on East Coast.,Google: 年輕的發(fā)明人,Larry Page, Co-founder s Clever Prototype Scientific Americ

17、an Article: ,HITS (2),權(quán)威（Authorities）: 結(jié)果集合中多個連接所指向的頁面 Hub: 具有許多外出連接的頁面,Positive two-way feedback: 好的權(quán)威頁面來自于從好的HUB指向的連接 好的權(quán)威頁面指向的頁面形成HUB頁面,Authorities and Hubs,Authorities ( blue ) Hubs (red),HITS 兩個循環(huán)處理步驟,在一組結(jié)果頁面s中的某個特定主題，分配候選hub和authorities 的初始得分 采用當(dāng)前對authorities的猜測來提高對 hubs的估計值定位所有好的 authorities

18、用更新后的hub信息來修正對 authorities的估計值找出好的hub中最頻繁指向的頁面，并將這些頁面定位好的authorities. 重復(fù)上述迭代過程，直到H(p)和A(p)收斂到結(jié)果集S的連接矩陣的 principle eigenvector, 計算結(jié)果用于判定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 獨立于查詢的方式計算排序值 快速響應(yīng)

19、. looks only in the forward direction, from link to link.,Clever 為每個搜索主題詞組合不同的根集，并在該查詢的上下文條件下對這些頁面排隊. 同時從一個權(quán)威頁面向后看，看是誰指向自己. 人類天生喜歡建立某些類似hub的東西來表示自己對某一特定主題的專長或喜好。,自治,High performance pattern matching based on Bayesian inference networks Identifies patterns in text based on usage and term frequency that correspond to