2010年5月

此文是我大四的時(shí)候一篇課程論文，現(xiàn)在看來(lái)，自己做的事情還真跟這篇文章里寫(xiě)的關(guān)系很大。過(guò)段時(shí)間我想寫(xiě)寫(xiě)社交搜索與傳統(tǒng)搜索在實(shí)現(xiàn)方法上的對(duì)比，所以把此文翻出來(lái)貼上。這里粘貼圖片不方便，看有圖片的版本，請(qǐng)下載：第四代搜索引擎前沿綜述.pdf

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

1．介紹

隨著因特網(wǎng)的普及，網(wǎng)上信息的發(fā)展呈現(xiàn)兩個(gè)基本的趨勢(shì)：規(guī)模的爆炸性增長(zhǎng)，覆蓋領(lǐng)域的不斷擴(kuò)大。如何在海量，非結(jié)構(gòu)化信息中，提取對(duì)用戶有用的信息是信息時(shí)代的核心課題。搜索引擎正是通過(guò)對(duì)信息的自動(dòng)搜集，索引，在用戶發(fā)出請(qǐng)求時(shí)經(jīng)過(guò)實(shí)時(shí)排序，為用戶呈現(xiàn)其最有價(jià)值的信息。

由搜索引擎衍生而來(lái)的關(guān)鍵詞廣告產(chǎn)生了巨大的商業(yè)價(jià)值，并造就了谷歌、百度等互聯(lián)網(wǎng)巨頭。但同時(shí)，谷歌以pagerank為核心的第三代搜索引擎已經(jīng)不能滿足日益增長(zhǎng)的需求，數(shù)據(jù)量的增長(zhǎng)和數(shù)據(jù)覆蓋范圍的增加迫切呼喚第四代搜索引擎。

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

2．搜索引擎發(fā)展歷史及趨勢(shì)

2.1 搜索引擎發(fā)展歷史

從Lycos和Yahoo的時(shí)代到現(xiàn)在，搜索引擎的發(fā)展已經(jīng)經(jīng)過(guò)了三代。Andrei[1]的文章中對(duì)前三代搜索引擎的特征做了描述：

第一代：頁(yè)面分析 僅使用頁(yè)面內(nèi)信息，文本信息，TF/IDF等
第二代：使用鏈接信息 鏈接分析，對(duì)搜索結(jié)果點(diǎn)擊數(shù)據(jù)，鏈接文字
第三代：語(yǔ)義分析 拼寫(xiě)建議，關(guān)鍵詞建議，關(guān)鍵詞優(yōu)化
第四代：正在發(fā)展 結(jié)合個(gè)性化數(shù)據(jù)，人際關(guān)系數(shù)據(jù)，跨媒體搜索

其中，第一代搜索引擎以早期Yahoo為代表，第二代以Google的創(chuàng)立為標(biāo)志，之后Google經(jīng)過(guò)改進(jìn)Pagerank和一系列技術(shù)，演化至第三代，而第四代搜索引擎有大量公司如Cuil,Quora探索，但還未形成成熟的產(chǎn)品。

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



首先搜索引擎通過(guò)爬蟲(chóng)技術(shù)（Crawler），根據(jù)網(wǎng)頁(yè)鏈接爬取互聯(lián)網(wǎng)內(nèi)容；然后建立倒排索引(Inverted Index)；同時(shí)通過(guò)Pagerank技術(shù)，基于random walk的思想計(jì)算出每個(gè)網(wǎng)頁(yè)的Pagerank。前面幾步都是獨(dú)立于用戶查詢進(jìn)行的。當(dāng)用戶提交查詢關(guān)鍵詞后，搜索引擎將首先對(duì)查詢此進(jìn)行分析（拼寫(xiě)建議，搜索建議，中文及日文等還需要分詞），然后查詢倒排索引，根據(jù)兩項(xiàng)因素對(duì)網(wǎng)頁(yè)文檔排序：1，查詢?cè)~語(yǔ)文檔的匹配程度，主要通過(guò)TF-IDF反映；2，網(wǎng)頁(yè)的質(zhì)量，通過(guò)預(yù)先算好的Pagerank反映。其中，TF-IDF是第一代搜索引擎已經(jīng)發(fā)展出來(lái)的技術(shù)。


2.2 現(xiàn)代搜索引擎的核心：PageRank

Google推出后即風(fēng)靡全球，其對(duì)搜索質(zhì)量的提升，主要就在于Pagerank基于鏈接分析的排序技術(shù)，大大提高了搜索結(jié)果質(zhì)量。Pagerank自1998年提出至今10年時(shí)間，一直是第三代搜索引擎的核心，也經(jīng)過(guò)了一定的改進(jìn)。在孟濤[3]的文章中，對(duì)于近年來(lái)Pagerank的改進(jìn)算法進(jìn)行了較全面的綜述。

Pagerank的算法的基本思想是通過(guò)網(wǎng)頁(yè)間的互相引用（以鏈接形式表現(xiàn)），來(lái)區(qū)分出網(wǎng)頁(yè)質(zhì)量高低，類似論文的引用。

如果網(wǎng)頁(yè)Q被共m個(gè)Pi網(wǎng)頁(yè)所鏈接，則其權(quán)值PR(Q)為



其中（1-λ）稱為緩沖因子，為從一個(gè)網(wǎng)頁(yè)隨機(jī)跳轉(zhuǎn)到另一個(gè)網(wǎng)頁(yè)的幾率。odpi為網(wǎng)頁(yè)P(yáng)i鏈向其他網(wǎng)頁(yè)的鏈接數(shù)量。

若將所有的網(wǎng)頁(yè)權(quán)值看作一個(gè)矢量，則Pagerank的矩陣表示為：



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

Weighted Pagerank算法：Web中存在不同的塊結(jié)構(gòu): Domain, Host, Directory，等等（Host最好）塊內(nèi)和塊外的鏈接應(yīng)該給不同的系數(shù)。改進(jìn)后公式：


Two-Layer PageRank算法: 經(jīng)典PageRank算法認(rèn)為網(wǎng)頁(yè)之間均等，隨機(jī)跳轉(zhuǎn)在網(wǎng)頁(yè)之間; 實(shí)際上存在網(wǎng)站和網(wǎng)頁(yè)兩極結(jié)構(gòu)，應(yīng)該修正馬爾科夫模型到兩級(jí)
?0?1 Block-Level PageRank算法: 網(wǎng)頁(yè)可以細(xì)分到Block，各個(gè)塊分量不一網(wǎng)頁(yè)與Block之間互有鏈接。改進(jìn)之后的計(jì)算公式
網(wǎng)頁(yè)到塊系數(shù)?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 塊之間的權(quán)值矩陣



網(wǎng)頁(yè)間的權(quán)值矩陣(Z：塊到網(wǎng)頁(yè)的矩陣)





2.3 第三代搜索引擎的缺陷

基于鏈接分析的第三代搜索引擎呈現(xiàn)出以下幾點(diǎn)局限性：

1，一個(gè)關(guān)鍵字查詢?cè)~對(duì)所有用戶呈現(xiàn)的搜索結(jié)果均相同。但是實(shí)際上，比如一個(gè)計(jì)算機(jī)用戶搜索“樹(shù)”可能指數(shù)據(jù)結(jié)構(gòu)，與其他用戶有很大區(qū)別。

2，Pagerank基于鏈接反映網(wǎng)頁(yè)質(zhì)量的方法，只反映了網(wǎng)頁(yè)制作者對(duì)于網(wǎng)頁(yè)質(zhì)量的評(píng)價(jià)，并沒(méi)有反映網(wǎng)頁(yè)瀏覽著對(duì)于網(wǎng)頁(yè)的評(píng)價(jià)。對(duì)于一些不善于進(jìn)行鏈接優(yōu)化的網(wǎng)站，雖然內(nèi)容可能很優(yōu)質(zhì)，但是Pagerank可能并不高。同時(shí)，一些新網(wǎng)站很難在短期內(nèi)提高Pagerank，而一些擅長(zhǎng)優(yōu)化技術(shù)的網(wǎng)站會(huì)用大量垃圾鏈接作弊。

3，基于關(guān)鍵詞的搜索方法是建立在用戶對(duì)于搜索有明確目的，并能清晰表述這種目的的假設(shè)上。但是實(shí)際上，用戶的搜索引擎使用水平參差不齊；并且由于存在同義詞等現(xiàn)象，同一個(gè)搜索請(qǐng)求有不同的表示方法，搜索結(jié)果也大為不同。

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

5，并不是所有有價(jià)值的信息都能被搜索引擎爬取到，比如學(xué)校論壇，公司內(nèi)網(wǎng)資料等有價(jià)值的資料就無(wú)法被搜索引擎檢索，這叫做Hidden Web現(xiàn)象；同時(shí)一些信息需要經(jīng)過(guò)人腦的加工，這方面問(wèn)答平臺(tái)更能勝任。這部分不能被爬取的信息實(shí)際上占了人類所有信息的大部分。


2.4 下一代搜索的趨勢(shì)

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

第四代搜索將呈現(xiàn)出以下幾個(gè)主要趨勢(shì)：

1，個(gè)性化的搜索。基于個(gè)人的網(wǎng)頁(yè)瀏覽歷史，搜索關(guān)鍵詞歷史，個(gè)人檔案信息，使得即使是同一個(gè)搜索關(guān)鍵詞，也能為不同用戶呈現(xiàn)不同的搜索結(jié)果。個(gè)性化搜索將基本解決2.3節(jié)提到的第一點(diǎn)局限。

2，社交搜索大大提高網(wǎng)頁(yè)排序質(zhì)量，其影響主要在兩方面：a,網(wǎng)頁(yè)瀏覽者（普通用戶）對(duì)于網(wǎng)頁(yè)的評(píng)價(jià)（收藏行為，評(píng)分，舉報(bào)等）將可以作為排序的依據(jù)b,通過(guò)用戶的社交圈推測(cè)用戶興趣，通過(guò)用戶間的不同程度信任關(guān)系為其提供不同權(quán)重的網(wǎng)頁(yè)排序推薦。社交搜索也包括問(wèn)答系統(tǒng)，用優(yōu)質(zhì)的設(shè)置提高信息的質(zhì)量。社交搜索將基本解決2.3節(jié)中提到的2，3，5中Pagerank和關(guān)鍵字搜索的局限。

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

本文的以下3，4，5節(jié)就將分別從個(gè)性化搜索，社交搜索，跨媒體搜索三個(gè)主要趨勢(shì)進(jìn)行探討，并且嘗試探討基因搜索，移動(dòng)搜索，情緒搜索。

3．個(gè)性化搜索（Personalized Search）

個(gè)性化搜索是搜索引擎根據(jù)用戶搜索的歷史記錄，包括用戶所搜索的關(guān)鍵詞，在搜索結(jié)果中的點(diǎn)擊情況，在各個(gè)網(wǎng)站的訪問(wèn)情況，書(shū)簽情況等，然后對(duì)這些信息進(jìn)行分析，在用戶搜索新的關(guān)鍵詞時(shí)，能返回更有針對(duì)性的搜索結(jié)果，從而提高用戶體驗(yàn)

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

對(duì)于第二個(gè)問(wèn)題，Yabo Xu[4]等人的文章中進(jìn)行了有益的探討。

首先，他們觀察到兩個(gè)有趣的現(xiàn)象：

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

b,不一定需要用戶隱私的細(xì)節(jié)來(lái)猜測(cè)用戶興趣，實(shí)際用更普遍的信息也可推測(cè)用戶興趣。

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

第一分割后的用戶興趣檔案：?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 第二次分割后的用戶興趣檔案：

經(jīng)過(guò)隱私劃分的用戶檔案：

通過(guò)這樣的劃分，用戶可以通過(guò)調(diào)整上圖中的minDetail參數(shù)來(lái)控制他可以暴露哪些隱私，從而使個(gè)性化搜索引擎可以根據(jù)這些隱私優(yōu)化搜索結(jié)果。上圖中的expRation則反映了在minDetail水平下的隱私暴露程度。

4．社交搜索 (Social Search)

隨著Facebook為代表的社交網(wǎng)站興起，互聯(lián)網(wǎng)用戶通過(guò)網(wǎng)絡(luò)進(jìn)行社交的時(shí)間大大增加，并且在網(wǎng)絡(luò)上留下了真實(shí)社交關(guān)系的數(shù)字表達(dá)，這使得利用社交關(guān)系改善搜索質(zhì)量成為了可能。如第2節(jié)所說(shuō)，社交關(guān)系將從三個(gè)方面大大改善搜索質(zhì)量。


4.1用戶對(duì)網(wǎng)頁(yè)評(píng)價(jià)改善搜索結(jié)果排序質(zhì)量

用戶對(duì)網(wǎng)頁(yè)的評(píng)價(jià)包括主動(dòng)評(píng)價(jià)和行為暗示。主動(dòng)評(píng)價(jià)包括通過(guò)delicious收藏夾的評(píng)分，評(píng)論等，行為暗示則包括用戶對(duì)網(wǎng)頁(yè)的收藏等。Shenghua Bao[5]通過(guò)delicious收藏夾的數(shù)據(jù)，進(jìn)行了這方面的研究。

他們引入了兩個(gè)評(píng)價(jià)指標(biāo)及相應(yīng)算法：SSR(SocialSimRank)評(píng)價(jià)搜索關(guān)鍵詞和用戶對(duì)收藏夾評(píng)價(jià)的關(guān)聯(lián)性，SPR(SocialPageRank)揭示了網(wǎng)頁(yè)在瀏覽者中的熱度。



上面這個(gè)圖揭示了通過(guò)SSR和SPR建立的搜索引擎的基本結(jié)構(gòu)。

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算法：



他們的結(jié)果顯示，通過(guò)SSR和SPR建立的搜索引擎，更容易發(fā)現(xiàn)優(yōu)質(zhì)但是外鏈較少的網(wǎng)頁(yè)。比如這個(gè)網(wǎng)頁(yè)http://37signals.com/papers/introtopatterns//index雖然內(nèi)容很少，但是Pagerank為0，而SPR為10，這樣有效的發(fā)掘出了內(nèi)容優(yōu)質(zhì)但是不善于搜索引擎優(yōu)化的網(wǎng)頁(yè)，并且新網(wǎng)站也更容易得到推廣。

但是Shenghua Bao等人的這篇論文也存在一定的局限性，首先數(shù)據(jù)集delicious僅有用戶對(duì)網(wǎng)頁(yè)的文字評(píng)論而沒(méi)有評(píng)分，因此無(wú)法對(duì)網(wǎng)頁(yè)質(zhì)量進(jìn)行較大區(qū)分。其次沒(méi)有考慮不同的社交圈子對(duì)于網(wǎng)站的不同評(píng)價(jià)。另外可以做的提升就是對(duì)用戶的評(píng)價(jià)進(jìn)行opinion mining。



4.2 根據(jù)用戶社交圈推測(cè)用戶興趣

一個(gè)社交圈子通常有相似的喜好，在社交關(guān)系的基礎(chǔ)上，可以通過(guò)用戶的社交圈子來(lái)推測(cè)其興趣，從而有產(chǎn)生更準(zhǔn)確的搜索結(jié)果。同時(shí)，用戶之間可以建立信任關(guān)系，也可改善搜索效果。信任關(guān)系的應(yīng)用比如如下情景：A是搜索引擎專家，B是一個(gè)本科生，B通過(guò)twitter與A建立了信任關(guān)系,同時(shí)A又通過(guò)delicious對(duì)很多搜索引擎研究網(wǎng)站進(jìn)行了評(píng)價(jià)和打分；因此，B可以聲稱在搜索引擎領(lǐng)域?qū)十分信任，從而在B搜索此領(lǐng)域關(guān)鍵詞時(shí)A推薦的網(wǎng)頁(yè)將有更高的排序權(quán)重。

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



4.3 高效的問(wèn)答系統(tǒng)

問(wèn)答系統(tǒng)是另一個(gè)高效的獲取信息的渠道，我們熟知的問(wèn)答系統(tǒng)包括百度知道，AskJeeves等，但是他們主要存在兩個(gè)關(guān)鍵問(wèn)題：1，問(wèn)答者水平參差不齊，十分缺少領(lǐng)域?qū)＜业膮⑴c；2，通過(guò)積分獎(jiǎng)勵(lì)的辦法并不能吸引有價(jià)值的回答，經(jīng)?？吹降幕卮鸲际腔ヂ?lián)網(wǎng)上的復(fù)制粘貼，而缺乏思考。

現(xiàn)在我發(fā)現(xiàn)的最好的問(wèn)答系統(tǒng)是美國(guó)Quora.com:



Quora的優(yōu)勢(shì)主要體現(xiàn)在：1，新用戶需要通過(guò)原有用戶的邀請(qǐng)才能加入，并且通過(guò)Facebook Connect登錄，自然地在問(wèn)答系統(tǒng)內(nèi)形成了社交關(guān)系；同時(shí)由于初始用戶都是硅谷的IT人士，因此從一開(kāi)始就聚集了大量領(lǐng)域?qū)＜?，保持了?wèn)答的水平。2，由于社交關(guān)系的引入，即使系統(tǒng)并沒(méi)有設(shè)置積分獎(jiǎng)勵(lì)，用戶仍然十分活躍，他們的參與完全是因?yàn)閷?duì)知識(shí)的渴望和分享的欲望，進(jìn)一步保證了信息質(zhì)量。3，良好的信息組織形式，包括類似wiki的用戶自主建立，編輯Topic,每個(gè)Topic下有一系列問(wèn)題，問(wèn)題之間又通過(guò)Related Question聯(lián)系起來(lái)。4，在現(xiàn)有Quora的信息架構(gòu)上，未來(lái)還可以利用機(jī)器學(xué)習(xí)推測(cè)用戶的話題喜好等。

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

傳統(tǒng)的文本、圖像、音頻和視頻分析與檢索技術(shù)都是相互獨(dú)立的，缺乏面向多種媒體的跨媒體搜索技術(shù)。這些多媒體信息應(yīng)用的發(fā)展，要求信息搜索“必須是跨媒體的，也就是說(shuō)用戶通過(guò)統(tǒng)一的界面和單一的提問(wèn)，就能夠獲得以各種媒體形式存在的語(yǔ)義相似的結(jié)果?！睘榱颂峁┲С侄喾N檢索方式和多模態(tài)用戶信息需求的跨媒體檢索，跨媒體搜索技術(shù)研究涉及海量多媒體數(shù)據(jù)的智能處理、多通道信息的融合和集成、快速準(zhǔn)確的跨媒體索引等關(guān)鍵問(wèn)題研究和應(yīng)用。最終，跨媒體將打通圖像，文字，聲音，視頻的界限，使得用圖像搜圖像，用聲音搜聲音，用圖像搜視頻等都成為可能。

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



6．其他趨勢(shì)

Jeonghee Yi[8]等人發(fā)現(xiàn)在移動(dòng)用戶的搜索關(guān)鍵詞通常在2.35個(gè)詞，短于通過(guò)PC提交的關(guān)鍵詞。另外移動(dòng)用戶的搜索集中在娛樂(lè)領(lǐng)域（44%）及旅游（7%）。移動(dòng)互聯(lián)網(wǎng)將是新的科技周期，如何根據(jù)移動(dòng)設(shè)備的特點(diǎn)優(yōu)化搜索將是重要的課題。同時(shí)基于地理位置的廣告和聚會(huì)建議也大有可為。

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

NLP的發(fā)展有助于更準(zhǔn)確理解用戶搜索意圖。

7．總結(jié)

這篇文章回顧了搜索引擎的發(fā)展歷史，提出第三代搜索引擎主要存在的弱點(diǎn)，主要是集中在搜索關(guān)鍵詞表達(dá)性的局限，pagerank算法未考慮瀏覽著評(píng)價(jià)的局限，搜索呈現(xiàn)的單一。通過(guò)第四代搜索引擎技術(shù)的個(gè)性化搜索，社交搜索及跨媒體搜索，將有效解決這些問(wèn)題，使搜索引擎交互方式更加友好，信息來(lái)源更加符合用戶要求，信息質(zhì)量更高?？傊?，第四代搜索引擎是一個(gè)激動(dòng)人心的課題，并且有巨大的商業(yè)前景。

作者：222.184.28.*   回復(fù)：0   發(fā)表時(shí)間：2011-10-26 20:49:29