第一講概論戴林2012.9《信息檢索》課程信息檢索-1概論提綱課程介紹搜索引擎發展歷程信息檢索信息檢索中的關鍵問題搜索引擎Web搜索引擎搜索工程師信息檢索-1概論課程介紹內容基礎知識、索引技術、排序技術、文本分類和文本聚類、情感計算、跨語言信息檢索、開源項目分析……共36學時，授課36學時，約16個主題教材講義、PPT參考文獻：《搜索引擎：信息檢索實踐》

（美）W.BruceCroft

DonaldMetzler

TrevorStrohman

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

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

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

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

使用率

使用率信息渠道生活助手

網絡新聞77.3%

網絡求職15.2%搜索引擎74.8%

網絡教育24.0%寫博客19.1%

網絡購物25.5%交流工具

網絡銷售4.3%即時通信69.8%

網上旅行預訂3.9%電子郵件55.4%網上銀行

20.9%娛樂工具

網上炒股14.1%網絡音樂68.5%

網絡影視61.1%

網絡游戲47.0%

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

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

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

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

到那些與提問者相關的文檔。真實環境中的搜索引擎，必須使用包含了用戶相關性的排序算法。在信息檢索中，檢索模型往往對文本的統計特征而不是語言結構建模。信息檢索-1概論評價文本排序的質量依賴于該文本與用戶期望的匹配程度在20世紀60年代，CyrilCleverdon率先制定了評價方法，他使用的兩種評價指標，準確率(precision)和召回率(recall)，目前仍很流行準確率是非常符合直覺的評價指標，它是檢索出來的文檔中相關文檔所占比例。召回率是全部相關文檔中被檢索出來的文檔比例最知名的測試集是TREC(TextREtrievalConference，)評測會議提供的測試集檢索模型和搜索引擎的評測是一個非常活躍的領域信息檢索-1概論信息需求(informationneed)：用戶交互信息需求是人們向搜索引擎發送查詢的背后動因。用戶是搜索質量的終極判定者。人們怎樣與搜索引擎之間進行交互，幫助用戶表達他們的信息需求文本查詢通常是用戶實際需求的一種很糟糕的描述。“貓”

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

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

Directory

Project

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

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