2010年5月

此文是我大四的時候一篇課程論文，現在看來，自己做的事情還真跟這篇文章里寫的關系很大。過段時間我想寫寫社交搜索與傳統搜索在實現方法上的對比，所以把此文翻出來貼上。這里粘貼圖片不方便，看有圖片的版本，請下載：第四代搜索引擎前沿綜述.pdf

最早發布于：http://www.newsmth.net/bbstcon.php?board=SearchEngineTech&gid=23434

1．介紹

隨著因特網的普及，網上信息的發展呈現兩個基本的趨勢：規模的爆炸性增長，覆蓋領域的不斷擴大。如何在海量，非結構化信息中，提取對用戶有用的信息是信息時代的核心課題。搜索引擎正是通過對信息的自動搜集，索引，在用戶發出請求時經過實時排序，為用戶呈現其最有價值的信息。

由搜索引擎衍生而來的關鍵詞廣告產生了巨大的商業價值，并造就了谷歌、百度等互聯網巨頭。但同時，谷歌以pagerank為核心的第三代搜索引擎已經不能滿足日益增長的需求，數據量的增長和數據覆蓋范圍的增加迫切呼喚第四代搜索引擎。

我認為，第四代搜索將把個性化信息及人際推薦關系疊加到鏈接分析上，大大改善搜索結果排序效果；同時，跨媒體搜索將實現諸如用圖片搜索圖片等功能，打通文字，圖片，視頻，聲音的界限，顛覆現在全部基于關鍵字的搜索方法，為用戶帶來更加直觀的搜索體驗。

2．搜索引擎發展歷史及趨勢

2.1 搜索引擎發展歷史

從Lycos和Yahoo的時代到現在，搜索引擎的發展已經經過了三代。Andrei[1]的文章中對前三代搜索引擎的特征做了描述：

第一代：頁面分析 僅使用頁面內信息，文本信息，TF/IDF等
第二代：使用鏈接信息 鏈接分析，對搜索結果點擊數據，鏈接文字
第三代：語義分析 拼寫建議，關鍵詞建議，關鍵詞優化
第四代：正在發展 結合個性化數據，人際關系數據，跨媒體搜索

其中，第一代搜索引擎以早期Yahoo為代表，第二代以Google的創立為標志，之后Google經過改進Pagerank和一系列技術，演化至第三代，而第四代搜索引擎有大量公司如Cuil,Quora探索，但還未形成成熟的產品。

下圖援引自Google創始人論文[2]，說明第二代，第三代搜索引擎的主要原理：



首先搜索引擎通過爬蟲技術（Crawler），根據網頁鏈接爬取互聯網內容；然后建立倒排索引(Inverted Index)；同時通過Pagerank技術，基于random walk的思想計算出每個網頁的Pagerank。前面幾步都是獨立于用戶查詢進行的。當用戶提交查詢關鍵詞后，搜索引擎將首先對查詢此進行分析（拼寫建議，搜索建議，中文及日文等還需要分詞），然后查詢倒排索引，根據兩項因素對網頁文檔排序：1，查詢詞語文檔的匹配程度，主要通過TF-IDF反映；2，網頁的質量，通過預先算好的Pagerank反映。其中，TF-IDF是第一代搜索引擎已經發展出來的技術。


2.2 現代搜索引擎的核心：PageRank

Google推出后即風靡全球，其對搜索質量的提升，主要就在于Pagerank基于鏈接分析的排序技術，大大提高了搜索結果質量。Pagerank自1998年提出至今10年時間，一直是第三代搜索引擎的核心，也經過了一定的改進。在孟濤[3]的文章中，對于近年來Pagerank的改進算法進行了較全面的綜述。

Pagerank的算法的基本思想是通過網頁間的互相引用（以鏈接形式表現），來區分出網頁質量高低，類似論文的引用。

如果網頁Q被共m個Pi網頁所鏈接，則其權值PR(Q)為



其中（1-λ）稱為緩沖因子，為從一個網頁隨機跳轉到另一個網頁的幾率。odpi為網頁Pi鏈向其他網頁的鏈接數量。

若將所有的網頁權值看作一個矢量，則Pagerank的矩陣表示為：



Pagerank技術很好的利用了鏈接信息，并且能夠較快收斂，因此取得了很好的的效果。在之后，出現了pagerank技術的各種改進：

Weighted Pagerank算法：Web中存在不同的塊結構: Domain, Host, Directory，等等（Host最好）塊內和塊外的鏈接應該給不同的系數。改進后公式：


Two-Layer PageRank算法: 經典PageRank算法認為網頁之間均等，隨機跳轉在網頁之間; 實際上存在網站和網頁兩極結構，應該修正馬爾科夫模型到兩級
?0?1 Block-Level PageRank算法: 網頁可以細分到Block，各個塊分量不一網頁與Block之間互有鏈接。改進之后的計算公式
網頁到塊系數?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2 塊之間的權值矩陣



網頁間的權值矩陣(Z：塊到網頁的矩陣)





2.3 第三代搜索引擎的缺陷

基于鏈接分析的第三代搜索引擎呈現出以下幾點局限性：

1，一個關鍵字查詢詞對所有用戶呈現的搜索結果均相同。但是實際上，比如一個計算機用戶搜索“樹”可能指數據結構，與其他用戶有很大區別。

2，Pagerank基于鏈接反映網頁質量的方法，只反映了網頁制作者對于網頁質量的評價，并沒有反映網頁瀏覽著對于網頁的評價。對于一些不善于進行鏈接優化的網站，雖然內容可能很優質，但是Pagerank可能并不高。同時，一些新網站很難在短期內提高Pagerank，而一些擅長優化技術的網站會用大量垃圾鏈接作弊。

3，基于關鍵詞的搜索方法是建立在用戶對于搜索有明確目的，并能清晰表述這種目的的假設上。但是實際上，用戶的搜索引擎使用水平參差不齊；并且由于存在同義詞等現象，同一個搜索請求有不同的表示方法，搜索結果也大為不同。

4，現在的圖像搜索，視頻搜索，音樂搜索也都是基于關鍵字，如圖像Tag，音樂電影介紹等，而文字對于這些信息的表現能力是很有限的，也不直觀。

5，并不是所有有價值的信息都能被搜索引擎爬取到，比如學校論壇，公司內網資料等有價值的資料就無法被搜索引擎檢索，這叫做Hidden Web現象；同時一些信息需要經過人腦的加工，這方面問答平臺更能勝任。這部分不能被爬取的信息實際上占了人類所有信息的大部分。


2.4 下一代搜索的趨勢

此處的下一代搜索即指第四代搜索引擎，一個主要的變化是從信息檢索(Information Retrieval)到信息推送（Information Supply）的轉變，信息推送將主要通過個性化搜索和社交搜索實現。

第四代搜索將呈現出以下幾個主要趨勢：

1，個性化的搜索。基于個人的網頁瀏覽歷史，搜索關鍵詞歷史，個人檔案信息，使得即使是同一個搜索關鍵詞，也能為不同用戶呈現不同的搜索結果。個性化搜索將基本解決2.3節提到的第一點局限。

2，社交搜索大大提高網頁排序質量，其影響主要在兩方面：a,網頁瀏覽者（普通用戶）對于網頁的評價（收藏行為，評分，舉報等）將可以作為排序的依據b,通過用戶的社交圈推測用戶興趣，通過用戶間的不同程度信任關系為其提供不同權重的網頁排序推薦。社交搜索也包括問答系統，用優質的設置提高信息的質量。社交搜索將基本解決2.3節中提到的2，3，5中Pagerank和關鍵字搜索的局限。

3，跨媒體搜索將打通文字，圖像，聲音，視頻間的界限，使得用圖像搜圖像，用聲音搜聲音，用圖像搜視頻等都成為可能。

本文的以下3，4，5節就將分別從個性化搜索，社交搜索，跨媒體搜索三個主要趨勢進行探討，并且嘗試探討基因搜索，移動搜索，情緒搜索。

3．個性化搜索（Personalized Search）

個性化搜索是搜索引擎根據用戶搜索的歷史記錄，包括用戶所搜索的關鍵詞，在搜索結果中的點擊情況，在各個網站的訪問情況，書簽情況等，然后對這些信息進行分析，在用戶搜索新的關鍵詞時，能返回更有針對性的搜索結果，從而提高用戶體驗

個性化搜索主要存在兩個難點：a,搜索引擎怎樣才能準確猜測用戶在特定時間的搜索目的？人的需求是不斷變更的，依據歷史記錄完全可能得出相差十萬八千里的猜測。b,如何在利用用戶信息為其提供個性化服務的同時，保護用戶的隱私？

對于第二個問題，Yabo Xu[4]等人的文章中進行了有益的探討。

首先，他們觀察到兩個有趣的現象：

a,如果能夠提供個性化的服務，用戶愿意犧牲一些隱私。

b,不一定需要用戶隱私的細節來猜測用戶興趣，實際用更普遍的信息也可推測用戶興趣。

基于這兩個觀察，作者首先為用戶建立了層次化的個人信息檔案：

第一分割后的用戶興趣檔案：?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2 第二次分割后的用戶興趣檔案：

經過隱私劃分的用戶檔案：

通過這樣的劃分，用戶可以通過調整上圖中的minDetail參數來控制他可以暴露哪些隱私，從而使個性化搜索引擎可以根據這些隱私優化搜索結果。上圖中的expRation則反映了在minDetail水平下的隱私暴露程度。

4．社交搜索 (Social Search)

隨著Facebook為代表的社交網站興起，互聯網用戶通過網絡進行社交的時間大大增加，并且在網絡上留下了真實社交關系的數字表達，這使得利用社交關系改善搜索質量成為了可能。如第2節所說，社交關系將從三個方面大大改善搜索質量。


4.1用戶對網頁評價改善搜索結果排序質量

用戶對網頁的評價包括主動評價和行為暗示。主動評價包括通過delicious收藏夾的評分，評論等，行為暗示則包括用戶對網頁的收藏等。Shenghua Bao[5]通過delicious收藏夾的數據，進行了這方面的研究。

他們引入了兩個評價指標及相應算法：SSR(SocialSimRank)評價搜索關鍵詞和用戶對收藏夾評價的關聯性，SPR(SocialPageRank)揭示了網頁在瀏覽者中的熱度。



上面這個圖揭示了通過SSR和SPR建立的搜索引擎的基本結構。

SSR算法：?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2?0?2 SPR算法：



他們的結果顯示，通過SSR和SPR建立的搜索引擎，更容易發現優質但是外鏈較少的網頁。比如這個網頁http://37signals.com/papers/introtopatterns//index雖然內容很少，但是Pagerank為0，而SPR為10，這樣有效的發掘出了內容優質但是不善于搜索引擎優化的網頁，并且新網站也更容易得到推廣。

但是Shenghua Bao等人的這篇論文也存在一定的局限性，首先數據集delicious僅有用戶對網頁的文字評論而沒有評分，因此無法對網頁質量進行較大區分。其次沒有考慮不同的社交圈子對于網站的不同評價。另外可以做的提升就是對用戶的評價進行opinion mining。



4.2 根據用戶社交圈推測用戶興趣

一個社交圈子通常有相似的喜好，在社交關系的基礎上，可以通過用戶的社交圈子來推測其興趣，從而有產生更準確的搜索結果。同時，用戶之間可以建立信任關系，也可改善搜索效果。信任關系的應用比如如下情景：A是搜索引擎專家，B是一個本科生，B通過twitter與A建立了信任關系,同時A又通過delicious對很多搜索引擎研究網站進行了評價和打分；因此，B可以聲稱在搜索引擎領域對A十分信任，從而在B搜索此領域關鍵詞時A推薦的網頁將有更高的排序權重。

David [6]等人正是在此領域做了有益的探索：



4.3 高效的問答系統

問答系統是另一個高效的獲取信息的渠道，我們熟知的問答系統包括百度知道，AskJeeves等，但是他們主要存在兩個關鍵問題：1，問答者水平參差不齊，十分缺少領域專家的參與；2，通過積分獎勵的辦法并不能吸引有價值的回答，經常看到的回答都是互聯網上的復制粘貼，而缺乏思考。

現在我發現的最好的問答系統是美國Quora.com:



Quora的優勢主要體現在：1，新用戶需要通過原有用戶的邀請才能加入，并且通過Facebook Connect登錄，自然地在問答系統內形成了社交關系；同時由于初始用戶都是硅谷的IT人士，因此從一開始就聚集了大量領域專家，保持了問答的水平。2，由于社交關系的引入，即使系統并沒有設置積分獎勵，用戶仍然十分活躍，他們的參與完全是因為對知識的渴望和分享的欲望，進一步保證了信息質量。3，良好的信息組織形式，包括類似wiki的用戶自主建立，編輯Topic,每個Topic下有一系列問題，問題之間又通過Related Question聯系起來。4，在現有Quora的信息架構上，未來還可以利用機器學習推測用戶的話題喜好等。

5．跨媒體搜索 (Cross Media Search)

傳統的文本、圖像、音頻和視頻分析與檢索技術都是相互獨立的，缺乏面向多種媒體的跨媒體搜索技術。這些多媒體信息應用的發展，要求信息搜索“必須是跨媒體的，也就是說用戶通過統一的界面和單一的提問，就能夠獲得以各種媒體形式存在的語義相似的結果。”為了提供支持多種檢索方式和多模態用戶信息需求的跨媒體檢索，跨媒體搜索技術研究涉及海量多媒體數據的智能處理、多通道信息的融合和集成、快速準確的跨媒體索引等關鍵問題研究和應用。最終，跨媒體將打通圖像，文字，聲音，視頻的界限，使得用圖像搜圖像，用聲音搜聲音，用圖像搜視頻等都成為可能。

Ritendra[7]等的文章探討了圖像搜索的發展，他們的主要目的是是的圖片搜索更加直觀，其中涉及的主要課題是圖像特征的提取和圖片相似度的計算。



6．其他趨勢

Jeonghee Yi[8]等人發現在移動用戶的搜索關鍵詞通常在2.35個詞，短于通過PC提交的關鍵詞。另外移動用戶的搜索集中在娛樂領域（44%）及旅游（7%）。移動互聯網將是新的科技周期，如何根據移動設備的特點優化搜索將是重要的課題。同時基于地理位置的廣告和聚會建議也大有可為。

生物信息的發展方興未艾，測定大眾基因序列有可能在近10年普及。當基因信息也可用時，個性化搜索將更有可為，比如根據基因的藥物建議，餐飲建議等。

NLP的發展有助于更準確理解用戶搜索意圖。

7．總結

這篇文章回顧了搜索引擎的發展歷史，提出第三代搜索引擎主要存在的弱點，主要是集中在搜索關鍵詞表達性的局限，pagerank算法未考慮瀏覽著評價的局限，搜索呈現的單一。通過第四代搜索引擎技術的個性化搜索，社交搜索及跨媒體搜索，將有效解決這些問題，使搜索引擎交互方式更加友好，信息來源更加符合用戶要求，信息質量更高。總之，第四代搜索引擎是一個激動人心的課題，并且有巨大的商業前景。

作者：222.184.28.*   回復：0   發表時間：2011-10-26 20:49:29