信息檢索-1 概論課件

第一講概論戴林2012.9《信息檢索》課程信息檢索-1概論提綱課程介紹搜索引擎發(fā)展歷程信息檢索信息檢索中的關(guān)鍵問(wèn)題搜索引擎Web搜索引擎搜索工程師信息檢索-1概論課程介紹內(nèi)容基礎(chǔ)知識(shí)、索引技術(shù)、排序技術(shù)、文本分類和文本聚類、情感計(jì)算、跨語(yǔ)言信息檢索、開(kāi)源項(xiàng)目分析……共36學(xué)時(shí)，授課36學(xué)時(shí)，約16個(gè)主題教材講義、PPT參考文獻(xiàn)：《搜索引擎：信息檢索實(shí)踐》

（美）W.BruceCroft

DonaldMetzler

TrevorStrohman

譯者：劉挺秦兵張宇車萬(wàn)翔《信息檢索導(dǎo)論》ChristopherD.Manning信息檢索-1概論課程介紹授課方式講授、課后預(yù)習(xí)考查方式及格、中、良、優(yōu)大作業(yè)回目錄信息檢索-1概論搜索引擎發(fā)展歷程回目錄信息檢索-1概論搜索引擎的鼻祖：Archie1990年由Montreal的McGillUniversity（麥吉爾大學(xué)）學(xué)生AlanEmtage、PeterDeutsch、BillWheelan發(fā)明的Archie(ArchieFAQ)實(shí)際上是一個(gè)可搜索的FTP文件名列表信息檢索-1概論現(xiàn)代搜索引擎的起源：Wanderer1993年MIT的學(xué)生MatthewGray開(kāi)發(fā)了WorldWideWebWanderer，它是世界上第一個(gè)利用網(wǎng)頁(yè)之間的鏈接關(guān)系來(lái)監(jiān)測(cè)Web發(fā)展規(guī)模的機(jī)器人（Robot）程序。最開(kāi)始只是用來(lái)統(tǒng)計(jì)互聯(lián)網(wǎng)上的服務(wù)器數(shù)量，之后發(fā)展為也能捕獲網(wǎng)址。信息檢索-1概論Yahoo1994.4美籍華人JerryYang(楊致遠(yuǎn))和DavidFilo完成了一套搜索軟件。最初Yahoo的數(shù)據(jù)是手工輸入的，實(shí)際上只是一個(gè)可搜索的目錄。1995年1月，正式成立Yahoo網(wǎng)站

信息檢索-1概論第一個(gè)現(xiàn)代意義上的搜索引擎：Lycos1994.7CarnegieMellonUniversity的MichaelMauldin將JohnLeavitt的蜘蛛程序接入到其索引程序中，創(chuàng)建了Lycos.提供了前綴匹配和字符相近限制、網(wǎng)頁(yè)自動(dòng)摘要、數(shù)據(jù)量相對(duì)較大。信息檢索-1概論Infoseek1994年底，Infoseek推出，沿襲Yahoo!和Lycos的概念。友善的用戶界面、大量附加服務(wù)使其后來(lái)者居上。1995.12與Netscape的戰(zhàn)略性協(xié)議使它變得很強(qiáng)勢(shì)2001年2月，Infoseek改用Overture的搜索結(jié)果信息檢索-1概論第一個(gè)元搜索引擎：

Metacrawler元搜索引擎(AMetaSearchEngineRoundup)。用戶提交搜索后，由元搜索引擎負(fù)責(zé)轉(zhuǎn)換處理后提交給多個(gè)預(yù)先選定的獨(dú)立搜索引擎，并將從各獨(dú)立搜索引擎返回的所有查詢結(jié)果，集中起來(lái)處理后再返回給用戶。第一個(gè)元搜索引擎，是Washington大學(xué)碩士生EricSelberg和OrenEtzioni開(kāi)發(fā)的Metacrawler（1995）。信息檢索-1概論第一個(gè)支持自然語(yǔ)言搜索的搜索引擎：

AltaVista1995年12月出現(xiàn)(AltaVistaPublicBetaPressRelease)。AltaVista是第一個(gè)支持自然語(yǔ)言搜索的搜索引擎。2003年AltaVista被Overture收購(gòu)，后者是Yahoo的子公司。信息檢索-1概論搜索引擎的后來(lái)之王：Google1995年，佩奇來(lái)到斯坦福讀博士，開(kāi)始網(wǎng)絡(luò)鏈接結(jié)構(gòu)方面的研究項(xiàng)目BackRub。之后，他和布林提出了PageRank技術(shù)，用于對(duì)網(wǎng)頁(yè)評(píng)級(jí)之后用于搜索引擎，改寫了搜索引擎的定義，建立了Google。信息檢索-1概論搜索引擎的后來(lái)之王：GoogleGoogle在斯坦福引起了人們的關(guān)注。佩奇開(kāi)始準(zhǔn)備出售該技術(shù)，但是沒(méi)有成功。Sun公司創(chuàng)始人的投資，隨后成立公司。2000年和Yahoo合作，一飛沖天。2004年7月上市，市值250億，增長(zhǎng)速度超過(guò)微軟。信息檢索-1概論Google之特點(diǎn)專注、進(jìn)取、樸素、低調(diào)、神話般的創(chuàng)業(yè)故事信息檢索-1概論中文搜索引擎老大：百度2000.1李彥宏創(chuàng)立了百度。2001.8發(fā)布百度測(cè)試版。目前是最大的中文搜索引擎MP3搜索特色信息檢索-1概論百度的特點(diǎn)專注于技術(shù)專注于中文搜索信息檢索-1概論北大天網(wǎng)由北大計(jì)算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)研究室開(kāi)發(fā)，于1997年10月29日正式在CERNET上提供服務(wù)。利用教育網(wǎng)優(yōu)勢(shì)，有強(qiáng)大的FTP搜索功能。信息檢索-1概論中國(guó)互聯(lián)網(wǎng)使用率

使用率

使用率信息渠道生活助手

網(wǎng)絡(luò)新聞77.3%

網(wǎng)絡(luò)求職15.2%搜索引擎74.8%

網(wǎng)絡(luò)教育24.0%寫博客19.1%

網(wǎng)絡(luò)購(gòu)物25.5%交流工具

網(wǎng)絡(luò)銷售4.3%即時(shí)通信69.8%

網(wǎng)上旅行預(yù)訂3.9%電子郵件55.4%網(wǎng)上銀行

20.9%娛樂(lè)工具

網(wǎng)上炒股14.1%網(wǎng)絡(luò)音樂(lè)68.5%

網(wǎng)絡(luò)影視61.1%

網(wǎng)絡(luò)游戲47.0%

回目錄信息檢索-1概論信息檢索信息檢索-1概論什么是信息檢索信息檢索（InformationRetrieval，IR）就是從數(shù)據(jù)源中找到滿足需求的信息的過(guò)程。傳統(tǒng)信息檢索根據(jù)筆畫(huà)從字典中查找某字的讀音和意思從《三國(guó)演義》中查找貂蟬出場(chǎng)的章節(jié)和地點(diǎn)從《概率論》中查找貝葉斯公式等等信息檢索-1概論電子信息時(shí)代的信息檢索從手機(jī)通信錄中查找某條短信從電子詞典中查找某單詞的例句從某個(gè)網(wǎng)頁(yè)中查找某關(guān)鍵字出現(xiàn)的地方從數(shù)據(jù)庫(kù)中查詢滿足檢索條件的記錄本書(shū)重點(diǎn)要討論的信息檢索：從互聯(lián)網(wǎng)中檢索包含某個(gè)關(guān)鍵字的最相關(guān)的網(wǎng)頁(yè)信息檢索-1概論信息檢索的定義GerardSalton’sdefinition:信息檢索是關(guān)于信息的結(jié)構(gòu)、分析、組織、存儲(chǔ)、搜索（search）和獲取（retrieval）的領(lǐng)域。“信息檢索”一詞含義非常寬泛，涵蓋了很寬范圍的信息類型和各種與搜索相關(guān)的應(yīng)用。信息檢索-1概論從20世紀(jì)50年代開(kāi)始，該領(lǐng)域的主要焦點(diǎn)一直是文本(text)和文本形式的文檔(textdocument)。網(wǎng)頁(yè)、電子郵件、學(xué)術(shù)論文、圖書(shū)和新聞報(bào)道只是文檔類型中的一部分。文檔和典型的數(shù)據(jù)庫(kù)記錄（例如銀行賬戶記錄或航班預(yù)定記錄）最重要的區(qū)別在于，文檔中的大部分信息以文本形式存放，文本是沒(méi)有結(jié)構(gòu)的。信息檢索-1概論信息檢索的另一個(gè)通俗的定義為：是從大規(guī)模非結(jié)構(gòu)化數(shù)據(jù)（通常是文本）的集合（通常保存在計(jì)算機(jī)上）中找出滿足用戶信息需求的資料（通常是文檔）的過(guò)程。術(shù)語(yǔ)“非結(jié)構(gòu)化數(shù)據(jù)”（unstructureddata）指的是那些沒(méi)有清晰和明顯語(yǔ)義結(jié)構(gòu)的數(shù)據(jù)，而計(jì)算機(jī)不易處理這類數(shù)據(jù)。信息檢索-1概論嚴(yán)格意義上的非結(jié)構(gòu)化數(shù)據(jù)在實(shí)際中并不存在:文本數(shù)據(jù)往往被認(rèn)為是典型的非結(jié)構(gòu)化數(shù)據(jù)，但是如果考慮文本中隱含的語(yǔ)言結(jié)構(gòu)信息，那么它們也不能算是“

非結(jié)構(gòu)化數(shù)據(jù)”?，F(xiàn)實(shí)中的大部分文本仍然都有其他結(jié)構(gòu)，如文本的標(biāo)題、段落、腳注等，這些結(jié)構(gòu)往往通過(guò)顯式的標(biāo)記來(lái)體現(xiàn)（如網(wǎng)頁(yè)中的格式標(biāo)簽）。我們也把網(wǎng)頁(yè)這種具有格式標(biāo)記的數(shù)據(jù)稱為“半結(jié)構(gòu)化數(shù)據(jù)”（semi-structureddata）。例如對(duì)于新聞報(bào)道。報(bào)道有一些屬性，比如標(biāo)題和新聞來(lái)源，但重要的內(nèi)容是報(bào)道本身。信息檢索-1概論對(duì)比在數(shù)據(jù)庫(kù)系統(tǒng)中:無(wú)論在格式上，還是在意義上，這兩個(gè)屬性都被非常精確地定義。要比較這些屬性的值是非常容易非結(jié)構(gòu)化情景中：對(duì)于提交給網(wǎng)絡(luò)搜索引擎的查詢，如果跟某篇報(bào)道有關(guān)，如具有“手機(jī)銀行”或“網(wǎng)銀”這樣的字眼，則被返回給用戶定義一個(gè)詞、句子、段落或者整個(gè)新聞報(bào)道相關(guān)的意義，比定義一個(gè)賬號(hào)要難得多，因此文本的比較并不容易對(duì)人們比較文本的過(guò)程進(jìn)行理解和建模，并設(shè)計(jì)計(jì)算機(jī)算法以便精確地執(zhí)行這種比較，是信息檢索的核心信息檢索-1概論檢索對(duì)象：從文本到多媒體檢索信息檢索的應(yīng)用包含了帶有結(jié)構(gòu)的多媒體文檔、有意義的文本內(nèi)容和其他媒體常見(jiàn)的信息媒體包括圖片、視頻、音頻（包括音樂(lè)和語(yǔ)音）當(dāng)前搜索非文本文檔的技術(shù)依賴于對(duì)這些內(nèi)容的文本描述，而不是這些媒體自身的內(nèi)容。對(duì)媒體內(nèi)容的直接比較技術(shù)正在不斷進(jìn)步，例如圖片的比較信息檢索-1概論信息檢索應(yīng)用通用搜索：萬(wàn)維網(wǎng)上進(jìn)行的搜索是信息檢索最常見(jiàn)的應(yīng)用垂直搜索（Verticalsearch）是網(wǎng)絡(luò)搜索的特殊形式，搜索被限制在特殊的主題上企業(yè)搜索(enterprisesearch)是在散布在企業(yè)內(nèi)部網(wǎng)中的大量計(jì)算機(jī)文件中尋找所需的信息桌面搜索(desktopsearch)是企業(yè)搜索的個(gè)人版，信息源是存儲(chǔ)在一臺(tái)個(gè)人電腦中的文件集合，包括那些被瀏覽過(guò)的郵件和網(wǎng)頁(yè)P(yáng)2P搜索(peer-to-peersearch)是在節(jié)點(diǎn)機(jī)或計(jì)算機(jī)構(gòu)成的網(wǎng)絡(luò)中搜尋信息，但沒(méi)有任何集中式的控制信息檢索-1概論信息檢索的任務(wù)基于用戶查詢的搜索(有時(shí)稱為特殊搜索(adhocsearch)，因?yàn)椴樵兊姆秶薮蠖沂孪葲](méi)有約定）是搜索引擎研究的主要任務(wù)。其他任務(wù)包括過(guò)濾(filtering)分類(classification)問(wèn)答(question

answering)“珠穆朗瑪峰的高度是多少？”、“亞馬遜河流有多長(zhǎng)？”信息檢索-1概論信息檢索-1概論按照規(guī)模分類第一個(gè)級(jí)別是以

Web搜索（websearch）為代表的大規(guī)模級(jí)別，此時(shí)需要處理存儲(chǔ)在數(shù)百萬(wàn)臺(tái)計(jì)算機(jī)上的數(shù)十億篇文檔：如何采集到這種規(guī)模的文檔？如何在這種大規(guī)模數(shù)據(jù)量的情況下建立高效運(yùn)行的系統(tǒng)？如何應(yīng)對(duì)Web特性所帶來(lái)的特殊問(wèn)題（比如欺騙）？FYI:2005年，網(wǎng)民可以在百度搜索到的網(wǎng)頁(yè)數(shù)已經(jīng)從1月份的6億上升到現(xiàn)在的8億，已經(jīng)大大超越了google的大約5億中文網(wǎng)頁(yè)信息檢索-1概論第二個(gè)級(jí)別是小規(guī)模，個(gè)人信息檢索（personalinformationretrieval）:操作系統(tǒng)中已經(jīng)融合的信息檢索的功能桌面搜索(desktopsearch)郵件程序中的搜索功能、分類問(wèn)題：如何處理個(gè)人計(jì)算機(jī)上各種格式的文檔？如何保證搜索系統(tǒng)的免維護(hù)？如何在啟動(dòng)搜索系統(tǒng)、處理信息和使用磁盤時(shí)保持簡(jiǎn)單且占用的系統(tǒng)資源足夠少而不至于對(duì)用戶的正常工作造成影響？信息檢索-1概論介于第一種大規(guī)模和第二種小規(guī)模之間的信息檢索主要面對(duì)的是中等規(guī)模的數(shù)據(jù)，包括面向企業(yè)、機(jī)構(gòu)和特定領(lǐng)域的搜索（domain-specificsearch）：公司內(nèi)部文檔專利庫(kù)或生物醫(yī)學(xué)文獻(xiàn)學(xué)術(shù)論文的搜索這種情況下，文檔往往存儲(chǔ)在集中的文件系統(tǒng)中，由一臺(tái)或者多臺(tái)計(jì)算機(jī)提供搜索服務(wù)回目錄信息檢索-1概論信息檢索中的關(guān)鍵問(wèn)題回目錄信息檢索-1概論相關(guān)性(relevance)相關(guān)性是信息檢索中的基本概念。相關(guān)文檔包含用戶把查詢發(fā)給搜索引擎后他想要找的信息。對(duì)查詢和文檔進(jìn)行簡(jiǎn)單的比較，尋找精確的匹配，那結(jié)果的相關(guān)性一定很差。蟑螂、小強(qiáng)bankmoney，bankmonkey信息檢索-1概論話題相關(guān)(topicalrelevance)和用戶相關(guān)(userrelevance)話題相關(guān)：如果一個(gè)文本與查詢是話題相關(guān)的，就意味著兩者有相同的話題。用戶相關(guān)會(huì)考慮該報(bào)道的一些附加特性?！暗卣稹庇駱?shù)地震“限行政策”信息檢索-1概論檢索模型(retrievalmodel)一個(gè)檢索模型是對(duì)查詢與文檔匹配過(guò)程的形式化表示，它是排序算法(rankingalgorithm)的基礎(chǔ)，搜索引擎利用排序算法生成文檔的有序列表一個(gè)好的檢索模型能夠找

到那些與提問(wèn)者相關(guān)的文檔。真實(shí)環(huán)境中的搜索引擎，必須使用包含了用戶相關(guān)性的排序算法。在信息檢索中，檢索模型往往對(duì)文本的統(tǒng)計(jì)特征而不是語(yǔ)言結(jié)構(gòu)建模。信息檢索-1概論評(píng)價(jià)文本排序的質(zhì)量依賴于該文本與用戶期望的匹配程度在20世紀(jì)60年代，CyrilCleverdon率先制定了評(píng)價(jià)方法，他使用的兩種評(píng)價(jià)指標(biāo)，準(zhǔn)確率(precision)和召回率(recall)，目前仍很流行準(zhǔn)確率是非常符合直覺(jué)的評(píng)價(jià)指標(biāo)，它是檢索出來(lái)的文檔中相關(guān)文檔所占比例。召回率是全部相關(guān)文檔中被檢索出來(lái)的文檔比例最知名的測(cè)試集是TREC(TextREtrievalConference，)評(píng)測(cè)會(huì)議提供的測(cè)試集檢索模型和搜索引擎的評(píng)測(cè)是一個(gè)非?；钴S的領(lǐng)域信息檢索-1概論信息需求(informationneed)：用戶交互信息需求是人們向搜索引擎發(fā)送查詢的背后動(dòng)因。用戶是搜索質(zhì)量的終極判定者。人們?cè)鯓优c搜索引擎之間進(jìn)行交互，幫助用戶表達(dá)他們的信息需求文本查詢通常是用戶實(shí)際需求的一種很糟糕的描述?！柏垺?/p>

“在哪兒能買到貓”O(jiān)R“貓王”的信息?查詢建議(querysuggestion)、查詢擴(kuò)展(queryexpansion)和相關(guān)反饋（relevancefeedback）回目錄信息檢索-1概論搜索引擎回目錄信息檢索-1概論搜索引擎是信息檢索技術(shù)在大規(guī)模文本集合上的實(shí)際應(yīng)用?！八阉饕妗币辉~原來(lái)是指為文本搜索服務(wù)的特殊的硬件。從20世紀(jì)80年代中期開(kāi)始，在描述用來(lái)比較查詢和文檔并生成文檔排序結(jié)果的軟件系統(tǒng)時(shí)，逐漸更多地使用“搜索引擎”一詞，而不是“信息檢索系統(tǒng)”或者“全文檢索系統(tǒng)”。信息檢索-1概論搜索引擎的不同結(jié)構(gòu)網(wǎng)絡(luò)搜索引擎，比如Yahoo，必須能夠捕獲，或者說(shuō)爬取(crawl)TB級(jí)的數(shù)據(jù)，并對(duì)每天收到的全世界數(shù)以百萬(wàn)計(jì)的查詢提供亞秒級(jí)的響應(yīng)時(shí)間。企業(yè)搜索引擎，比如Autonomy，必須能夠處理一個(gè)公司內(nèi)部不同類型的信息源，使用與公司有關(guān)的特殊知識(shí)作為搜索和相關(guān)任務(wù)(如數(shù)據(jù)挖掘(datamining))的一部分。數(shù)據(jù)挖掘指從數(shù)據(jù)中自動(dòng)發(fā)現(xiàn)有趣的結(jié)構(gòu)，也包括聚類(clustering)技術(shù)。桌面搜索引擎，比如google和百度的桌面搜索引擎，必須能夠在人們制作和瀏覽新文檔、網(wǎng)頁(yè)和郵件時(shí)快速地合并，同時(shí)提供非常直觀的界面來(lái)搜索這些非常異質(zhì)的混合信息。信息檢索-1概論OpenSourceSE開(kāi)源(OpenSource)搜索引擎是另外一類重要的搜索系統(tǒng)，與商業(yè)搜索引擎有不同的設(shè)計(jì)目標(biāo)Lucene是一個(gè)基于Java的流行的搜索引擎（也有C++和C#的實(shí)現(xiàn)），它已經(jīng)被用于大范圍的商業(yè)應(yīng)用中，其中使用的信息檢索技術(shù)相對(duì)簡(jiǎn)單Xapian是一個(gè)基于C++的開(kāi)源的工具包，基于STL實(shí)現(xiàn)，越來(lái)越多的應(yīng)用采用該組件信息檢索-1概論搜索引擎設(shè)計(jì)中的重要問(wèn)題搜索引擎設(shè)計(jì)中的重要問(wèn)題包括了信息檢索中的各種問(wèn)題：有效的排序算法、評(píng)價(jià)及用戶交互。大規(guī)模數(shù)據(jù)給搜索引擎帶來(lái)了其他許多難題,首要問(wèn)題是搜索引擎的性能:響應(yīng)時(shí)間(responsetime)查詢吞吐量(querythroughput)索引速度(indexingspeed)。信息檢索-1概論新數(shù)據(jù)處理能力搜索要處理動(dòng)態(tài)持續(xù)變化的信息。另一個(gè)重要的性能指標(biāo)是把新數(shù)據(jù)合并到索引中的速度。覆蓋率(coverage)衡量現(xiàn)存信息（比如在一個(gè)企業(yè)信息環(huán)境中）有多少被索引和存儲(chǔ)在搜索引擎中。新近性(recency)或時(shí)新性(freshness)衡量所存信息的年齡(age)。信息檢索-1概論可擴(kuò)充性(scalability)搜索引擎可以用在小規(guī)模數(shù)據(jù)集上，也可以用于極大規(guī)模的數(shù)據(jù)集，比如整個(gè)互聯(lián)網(wǎng)。對(duì)某個(gè)應(yīng)用可能只有很少的一些用戶，也可能有成千上萬(wàn)的用戶?？蓴U(kuò)充性(scalability)：設(shè)計(jì)應(yīng)該考慮到數(shù)據(jù)量和用戶量的增長(zhǎng)。搜索引擎必須是可定制的(customizable)或者說(shuō)是自適應(yīng)的(adaptable)。這意味著搜索引擎的許多功能，比如排序算法、界面或索引策略，能夠?yàn)闈M足新的應(yīng)用需要而調(diào)整和適應(yīng)FYI:GOOGLE的排序算法每天更新一次以上。信息檢索-1概論特殊問(wèn)題特殊問(wèn)題也會(huì)影響搜索引擎的設(shè)計(jì)，最好的例子是網(wǎng)絡(luò)搜索中的垃圾信息(spam)。垃圾信息(spam)：為某種商業(yè)利益而制作的文檔中誤導(dǎo)的、不合適的或不相關(guān)的信息。但搜索引擎必須處理的一種類型是文檔中的垃圾詞，這些詞導(dǎo)致該文檔能夠在搜索引擎響應(yīng)一些熱門查詢時(shí)被檢索出來(lái)。由于垃圾索引(spamdexing)顯著地導(dǎo)致搜索引擎排序質(zhì)量的降低，網(wǎng)絡(luò)搜索引擎的設(shè)計(jì)者不得不開(kāi)發(fā)能夠識(shí)別和刪除這些垃圾文檔的技術(shù)。信息檢索-1概論回目錄信息檢索-1概論Web搜索引擎回目錄信息檢索-1概論背景與歷史Web在很多方面都是空前的：不僅在規(guī)模上史無(wú)前例，而且其創(chuàng)建過(guò)程中協(xié)調(diào)機(jī)制的缺乏也是空前的Web參與者的背景和動(dòng)機(jī)的多樣性同樣也是空前的以上的每一個(gè)因素都使得Web搜索有別于傳統(tǒng)的文檔搜索。一般來(lái)說(shuō)Web搜索要困難得多。信息檢索-1概論人人可以制作網(wǎng)頁(yè)人們很容易就能閱讀某個(gè)URL對(duì)應(yīng)的原始HTML標(biāo)記文檔，這樣新用戶就無(wú)需太多的學(xué)習(xí)或者經(jīng)驗(yàn)便可以創(chuàng)建自己的HTML內(nèi)容，甚至可以選擇喜歡的網(wǎng)頁(yè)作為樣例直接學(xué)習(xí)。瀏覽器會(huì)忽略其不能解析的內(nèi)容，這個(gè)特點(diǎn)使得Web內(nèi)容的創(chuàng)建和使用能夠被迅速擴(kuò)散開(kāi)來(lái)。在Web上發(fā)布網(wǎng)頁(yè)已經(jīng)不是少數(shù)訓(xùn)練有素的編程人員的特權(quán)，而是上億普通網(wǎng)民參與的活動(dòng)。對(duì)于大部分的用戶和需求來(lái)說(shuō)，Web已經(jīng)迅速成為提供和消費(fèi)各種信息的重要場(chǎng)所，這些信息包括從疑難雜癥到地鐵時(shí)刻表的任何內(nèi)容。信息檢索-1概論信息發(fā)現(xiàn)的嘗試如果其他用戶不能發(fā)現(xiàn)并使用Web上發(fā)布的大量信息，那么這些信息實(shí)際上就毫無(wú)價(jià)值。有關(guān)Web信息發(fā)現(xiàn)的早期嘗試可以歸成兩類：(i)像Altavista、Excite和Infoseek一樣的基于全文索引的搜索引擎(ii)諸如Yahoo!的Web網(wǎng)頁(yè)分類體系

前者在前臺(tái)給用戶提供了關(guān)鍵詞搜索界面，而在后臺(tái)則采用前面介紹的倒排索引和排序機(jī)制。后者可以允許用戶沿樹(shù)形結(jié)構(gòu)的類別體系進(jìn)行瀏覽。信息檢索-1概論Web網(wǎng)頁(yè)分類體系Web網(wǎng)頁(yè)分類體系很多缺點(diǎn)：大部分工作都是人工編輯完成，那么隨著Web規(guī)模的擴(kuò)大這種做法很難擴(kuò)展要準(zhǔn)確發(fā)現(xiàn)Web網(wǎng)頁(yè)并把它們分到類別節(jié)點(diǎn)上去，用戶的理解必須要和分類體系的編輯人員一致當(dāng)類別體系的規(guī)模急劇增長(zhǎng)時(shí)，這一點(diǎn)也變得相當(dāng)具有挑戰(zhàn)性。Yahoo!的分類體系很早就超過(guò)了1000個(gè)的節(jié)點(diǎn)。FYI:Open

Directory

Project

（）是互聯(lián)網(wǎng)上最大的，最廣泛的人工目錄。它是由來(lái)自世界各地的志愿者共同維護(hù)與建設(shè)的最大的全球目錄社區(qū)。信息檢索-1概論第一代Web搜索引擎第一代Web搜索引擎將前面介紹的傳統(tǒng)搜索技術(shù)應(yīng)用到Web領(lǐng)域，它們主要關(guān)注規(guī)模上的挑戰(zhàn)性。最早的Web搜索引擎必須要處理包含上千萬(wàn)文檔的索引，而這個(gè)規(guī)模比以前所有的公共域IR系統(tǒng)的數(shù)據(jù)規(guī)模要高很多個(gè)數(shù)量級(jí)。第一代Web搜索引擎針對(duì)上述挑戰(zhàn)取得了巨大成功，它們能夠持續(xù)索引很大一部分Web頁(yè)面，并且能在亞秒級(jí)時(shí)間內(nèi)完成對(duì)查詢的應(yīng)答。搜索結(jié)果的質(zhì)量和相關(guān)性離期望還有很大的距離。這就亟需研發(fā)出新的排序機(jī)制和反作弊技術(shù)來(lái)提高搜索質(zhì)量。而且必須要度量文檔的權(quán)威度（authoritativeness），即計(jì)算權(quán)重度時(shí)可利用諸如其所在網(wǎng)站之類的信息。信息檢索-1概論Web的信任問(wèn)題由于網(wǎng)絡(luò)內(nèi)容的創(chuàng)作具有極大的民主化，所以這就意味著幾乎在任何一個(gè)話題上都會(huì)出現(xiàn)一些粒度更細(xì)的不同觀點(diǎn)。這也表示W(wǎng)eb中包含真理、謊言、矛盾和大量猜測(cè)。我們應(yīng)該相信哪些Web網(wǎng)頁(yè)？傳統(tǒng)的非Web出版方式下，這并不是個(gè)問(wèn)題，用戶可以自己選擇他們認(rèn)為可信的來(lái)源。需要指出的一點(diǎn)是，可能并不存在統(tǒng)一的、與用戶無(wú)關(guān)的可信度標(biāo)準(zhǔn)，對(duì)某個(gè)用戶可信的網(wǎng)頁(yè)內(nèi)容不一定對(duì)其他用戶可信。我們將基于鏈接分析技術(shù)考察理解上述問(wèn)題的方法。信息檢索-1概論Web到底有多大？Web到底有多大？“某個(gè)搜索引擎中索引的網(wǎng)頁(yè)數(shù)目是多少？”到1995年底，Altavista聲稱它采集并索引了大概三千萬(wàn)個(gè)靜態(tài)網(wǎng)頁(yè)。動(dòng)態(tài)頁(yè)面（dynamicpage）通常是由應(yīng)用服務(wù)器應(yīng)答數(shù)據(jù)庫(kù)的查詢需求時(shí)產(chǎn)生的。這種頁(yè)面的一個(gè)標(biāo)志是URL中通常包含字符“?”。在1995年時(shí)，由于大家相信每過(guò)幾個(gè)月靜態(tài)頁(yè)面的數(shù)目就會(huì)翻番，所以早期的包括Altavista在內(nèi)的Web搜索引擎必須要經(jīng)常增加硬件和帶寬來(lái)采集和索引網(wǎng)頁(yè)。信息檢索-1概論Web圖我們可以將整個(gè)靜態(tài)Web看成是靜態(tài)HTML網(wǎng)頁(yè)通過(guò)超鏈接互相連接而成的有向圖，其中每個(gè)網(wǎng)頁(yè)是圖的頂點(diǎn)，而每個(gè)超鏈接則代表一個(gè)有向邊。一個(gè)網(wǎng)頁(yè)的入鏈接數(shù)目被稱為這個(gè)網(wǎng)頁(yè)的入度（in-degree），在一系列研究中得到的網(wǎng)頁(yè)的平均入度大概從8到15左右不等。信息檢索-1概論該例子中共有6個(gè)網(wǎng)頁(yè)，網(wǎng)頁(yè)B的入度為3、出度為1。該圖不是強(qiáng)連通圖，因?yàn)锽不可能到A。信息檢索-1概論連接的分布有充分的證據(jù)表明，這些鏈接并不滿足隨機(jī)分布。如果每個(gè)網(wǎng)頁(yè)都是隨機(jī)均勻地選擇鏈接目標(biāo)時(shí)，那么鏈接到一個(gè)網(wǎng)頁(yè)的鏈接數(shù)目應(yīng)該滿足泊松分布，但是實(shí)際中的數(shù)目并不滿足預(yù)想的泊松分布。實(shí)際上，有大量研究表明這個(gè)分布滿足冪分布定律（powerlaw），具有入度為i的網(wǎng)頁(yè)總數(shù)目正比于1/iα

，研究中一個(gè)有代表性的α值是2.1。信息檢索-1概論一些研究表明，整個(gè)Web有向圖結(jié)構(gòu)是個(gè)蝴蝶結(jié)(bowtie)形：從IN中的任一網(wǎng)頁(yè)出發(fā)通過(guò)超鏈接到達(dá)SCC的任一網(wǎng)頁(yè)，從SCC中的網(wǎng)頁(yè)達(dá)到OUT中的任一網(wǎng)頁(yè)。從SCC中的任一網(wǎng)頁(yè)可以到達(dá)SCC中的其他網(wǎng)頁(yè)。不可能從SCC中的網(wǎng)頁(yè)到達(dá)IN的任一網(wǎng)頁(yè)，也不能從OUT中的網(wǎng)頁(yè)到達(dá)SCC中的任一網(wǎng)頁(yè)信息檢索-1概論IN和OUT的規(guī)模大致相當(dāng)，而SCC的規(guī)模則稍大，大部分網(wǎng)頁(yè)都落入到這三大類中。剩余的網(wǎng)頁(yè)構(gòu)成了所謂管道（tube），它由少部分SCC之外的網(wǎng)頁(yè)組成，可以直接將IN和OUT中的網(wǎng)頁(yè)相連。另外，還有一些不能從IN到達(dá)或者只能到達(dá)OUT的網(wǎng)頁(yè)構(gòu)成的所謂卷須（tendril）。信息檢索-1概論作弊網(wǎng)頁(yè)Web搜索引擎顯然是連接廣告商和顧客的一種重要途徑！例如：用戶在搜索“Chicagogolfrealestate”時(shí)，他想做的不僅僅是搜索有關(guān)Chicago的高爾夫球場(chǎng)地產(chǎn)的新聞或者娛樂(lè)信息，而且很可能要尋找并購(gòu)買這樣的地產(chǎn)。這導(dǎo)致了第一代作弊網(wǎng)頁(yè)（spam）:即通過(guò)操作網(wǎng)頁(yè)內(nèi)容來(lái)達(dá)到在某些關(guān)鍵詞的搜索結(jié)果中排名較高的目的。為了避免用戶對(duì)這些冗余和重復(fù)信息的極度反感，一些老練的作弊者還會(huì)采用一些手段和技巧，比如將這些重復(fù)的詞設(shè)置成和背景一樣的顏色。信息檢索-1概論偽裝作弊者也發(fā)展出了更多的作弊技術(shù)。一種技術(shù)被稱為偽裝（cloaking）根據(jù)http請(qǐng)求是來(lái)自搜