微博檢索的研究進展

衛冰潔，王 斌，張 帥，李 鵬

(1. 中國科學院 計算技術研究所，北京 100190；2. 中國科學院 信息工程研究所，北京 100093；3. 國家計算機網絡應急技術處理協調中心，北京 100029)

?

微博檢索的研究進展

衛冰潔1,3，王 斌2，張 帥1，李 鵬2

(1. 中國科學院 計算技術研究所，北京 100190；2. 中國科學院 信息工程研究所，北京 100093；3. 國家計算機網絡應急技術處理協調中心，北京 100029)

隨著微博的快速發展，微博檢索已經成為近年來研究領域的熱點之一。該文首先以TREC Microblog數據為基礎，從分析微博文檔和微博查詢兩方面出發，得出微博檢索與傳統文本檢索之間的兩點不同： 一是微博文檔相較于網頁具有很多獨有的特征；二是微博查詢屬于時間敏感查詢，即在排序時除了考慮文本的語義相似度，還需要考慮時間因素，將這類方法統稱為時間感知的檢索技術。這兩點差異使得已有的信息檢索技術不能滿足微博搜索的需求。該文主要介紹了近年來這兩方面的相關研究： 首先描述了微博本身的多種特征以及基于這些特征提出的檢索方法；然后以傳統信息檢索過程為主線，分別介紹了將時間信息用于文本表示、文檔先驗、查詢擴展三方面的排序模型，最后總結了已有工作并且對未來研究內容進行了展望。

微博檢索；時間信息；微博特性；文本表示；文檔先驗；查詢擴展

1 引言

隨著Web 2.0近年來廣泛應用，“人人參與、信息共享”逐漸成為了當今網絡的主流，其中具有代表性的應用之一便是微博。微博(Microblog)，即微型博客，Wiki*http://zh.wikipedia.org/上給出的定義是“微博是一種允許用戶及時更新簡短文本(通常少于140字)并可以公開發

布的微型博客形式”。截止今日，網絡中已有多個微博平臺，例如，Twitter、新浪微博、騰訊微博、 網易微博等。微博成為了近年來發展 最 快的熱門互聯網應用之一。

微博的廣泛流行，帶來的是快速增長的用戶量和數據量。CNNIC發布的最新報告[1]指出,截止2012年底，我國微博用戶達到3.09億，同比增幅達到23.5%，有超過半數的網民在使用微博。同時，伴隨著如此巨大的用戶增長量，微博數據量也呈現出爆發式的增長趨勢。據新浪微博統計，用戶每日發博數量超過1億條。與此同時Twitter的每日微博數量已超過4億條。隨著微博的快速發展，它已不僅僅是用戶發表個人心情狀態的一個社交場所，同時已經成為網民獲取最新信息的重要渠道之一。面對如此海量的數據，用戶獲取個人所需信息的需求日益增強，微博檢索的重要性不言而喻。

微博檢索屬于信息檢索領域，更進一步說屬于文本檢索的范疇，是近年來檢索領域的研究熱點之一，相關論文在各大會議上頻頻出現。在已有的研究中，大部分工作是基于微博的某些特點提出新的檢索模型得到效果的提高，沒有對微博檢索與信息檢索的區別給予整理和總結。文獻[2]通過對微博新型數據的分析，主要分析了實體搜索、情感分析、基于用戶的元數據、時間因素等研究點，是一篇面向微博數據的相關檢索研究問題的總結性文章。本文面向的是狹義的微博檢索，即針對微博排序的研究，主要目的是通過對比微博檢索與傳統檢索的不同而對已有的研究進行總結和整理，從而對微博排序的未來研究方向提出一定的建議。

經過多年研究之后，傳統文本檢索有相對成熟的理論基礎，其檢索的基本過程為： 由大規模文檔數據構成被檢索語料庫，用戶構造出可表達其信息需求的查詢，經過檢索模型對查詢與文檔的語義相似度進行打分，最終將結果按照降序返回給用戶。文檔數據和用戶查詢是檢索模型的輸入基礎，選擇合適的檢索模型必須考慮用來檢索的文檔和用戶輸入查詢的特點。然而，面向微博的檢索從文檔集和查詢這兩方面都表現出與傳統文本檢索的差異： 1)微博文檔： 微博相對于傳統文本具有很多自己的特性，包括不超過140個字的文字長度的限制、具有特殊意義的標簽“#”和“@”、用戶信息、鏈接信息等。這些特性帶給微博不同于普通網頁的特征，如何正確使用這些特征，使之有利于檢索效果的提高，是微博檢索面臨的挑戰之一。2)微博查詢： Teevan Ramage等人[3]通過對比Twitter查詢和Web查詢，指出用戶進行微博檢索時的搜索意圖大都與時間有關的，我們將這類查詢稱之為時間敏感查詢(具體內容將在第3節中介紹)。針對時間敏感查詢，在傳統的檢索技術中，僅僅考慮查詢和文本的語義相似度是不夠的，而需要在相關技術加入時間因素，統稱為時間感知的檢索技術。如何在微博的背景下，將時間和語義相似度完美結合，是微博檢索面臨的難點。

綜上所述，微博檢索從文檔和查詢上都具有自己的特點： 微博文檔具有自己的特征、微博查詢屬于時間敏感查詢。由于這兩點區別，使得已有的檢索技術不能很好適應微博檢索的環境，對微博檢索的研究提出了新的問題和難點。已有實驗表明，在信息檢索技術的基礎上，考慮微博特性，融入時間因素均對微博的搜索性能有所提高。本文在以下章節中將從上述提到的兩個不同點出發，分別介紹基于微博特性和面向時間敏感查詢的已有研究工作，并進行整理和總結，同時列舉多個未來有待深入研究的問題。

針對微博的研究，除了微博檢索，還涉及多個方面： 1)微博網站是一個社交平臺，微博用戶是社交平臺的基礎組成?；谟脩暨M行標簽預測、關系挖掘、社區發現等是針對微博用戶的研究方向之一[4-6]。2)由于微博的實時更新性，從微博文檔中發現熱點事件或者研究事件發展的相關論文也層出不窮[7-10]?？傮w來說，微博作為新型數據，對傳統的文本技術提出了新的挑戰，針對微博的研究還有很多有待解決的問題。

本文的組織結構如下： 第3節從微博文檔和微博查詢兩方面對比微博檢索和傳統檢索的區別；第4節分別介紹關于微博特性的檢索技術相關研究和面向時間敏感查詢的檢索技術；第5節對本文進行了總結以及對未來的研究方向進行了簡單的討論。

2 微博檢索與傳統文本檢索的對比分析

通過引言中對傳統檢索過程的描述可知，被檢索文檔和用戶輸入的查詢是檢索模型的基礎，在選擇合適的檢索模型時，必須考慮文檔和查詢的特點。然而，面向微博的搜索從文檔集和查詢這兩方面都表現出與傳統文本檢索的差異，下面將進行具體說明。

2.1 微博文檔

微博，具有很多不同于網頁的特點，例如，文本短(通常不超過140個字符)、含有特殊標簽“#”和“@”、微博作者資料等。圖1顯示的是新浪微博“皓博睡吧”話題的兩條微博截圖以及微博用戶“人民日報”的資料截圖。以此為例，可以說明微博文檔具有的特點。首先，觀察“皓博睡吧”話題的兩條微博?！?”和“@”符號在微博文本中，具有特殊含義。用兩個“#”包含的文字代表該微博的主題，如“皓博睡吧”，是由發微博的作者給定的。“@”符號表示回復功能，一個用戶可以在@符號之后寫上另一個用戶的微博名字，表示是回復給該用戶的。同時，由于微博文字個數的限制，有些用戶會添加網頁的URL信息。其次，從微博用戶“人民日報”的截圖可以看出，微博作者包含關注者和粉絲。關注者是指你對這個用戶的信息感興趣，當你關注他之后，他的消息如果更新則會出現在你的微博頁面中，粉絲則相反。在用戶資料中也會有目前已發的微博數量以及個人的標簽等信息。

圖1 新浪微博“皓博睡吧”話題的相關微博和微博用戶“人民日報”的資料截圖

微博文檔具有多種不同的特征，為了更好地理解微博特性，我們定義三個類別來劃分微博的特征，分別為： 內容屬性、用戶屬性、結果屬性(或稱為鏈接屬性)。內容屬性僅僅只是微博文本內容包含的特性，如hashtag、url以及短文本等；用戶屬性是指微博作者包含的特性，如作者的關注數和粉絲數等；結構屬性，也可稱為鏈接屬性，是指以微博為統計單位用于表示微博之間的關系的特征，例如，微博hashtag信息等。利用這些特征提高檢索的相關工作將在第3節介紹。

2.2 微博查詢

文獻[3]通過對Twitter查詢和Web查詢進行多方面分析，指出微博查詢大都屬于時間敏感查詢(Topic-Sensitive Query)。通常在新聞、博客等文檔集中進行的查詢也具有相應特征。查詢屬于時間敏感查詢的一個顯式表現便是查詢的相關文檔集合在各個時刻的分布具有明顯區別，文獻[11]以來源于TREC的Web查詢301、156和165為例進行了說明。在本文中，我們將對微博查詢進行類似的分析，判斷其是否具有相似的時間特性。

我們以2011的TREC Microblog Search任務發布的108個查詢為分析對象*TREC一共發布了110個查詢，其中查詢MB050和MB076沒有標注文檔，因此忽略這兩個查詢。。文檔集中共標注文檔個數為113 829篇，其中標注為相關的文檔共有9 150篇。當給定一個查詢Q以及其標注相關微博集Dr，處理過程如下： 1)根據微博給定的唯一ID，劃分其到指定的天數中。TREC發布的文檔集是從2011年1月23日至2011年2月8日共17天的數據，因此每篇標注微博被指定了一個1-17的數字；2)統計每一天的相關微博個數，得到17個數字的統計分布；3)使用方差統計量*補充說明： 因為TREC發布的查詢具有提交時間，也就是說該時間之后的微博集合不予考慮，因此在計算方差的時候，我們會以每個查詢的提交時間作為截止時間，統計到此時間為止的時間段上的方差。表示該分布的變化差異性。也就是說如果一個分布的方差越接近0，則其越趨向于均勻分布，也就差異性越小；反之，如果一個分布的方差越大，則表明其在不同時刻的波動越大。需要說明的是，因為每個查詢標注文檔個數不同，為了避免其影響，我們對將絕對值分布轉化為百分制，即每一個時刻的數值代表其在這部分所占有的比重。表1顯示的是這108個微博查詢的方差統計信息。

從表1可以看出，大部分微博查詢的方差都處在20～500的范圍內，少部分達到了超過1 000的數值。為了方便更直觀地觀察分布，我們在圖2列出了其中四個查詢的統計分布圖。

觀察圖2，其中MB036的方差為2 500，是所有查詢的最高值；MB078的方差為2.290 7，是最低值；除了這兩個極端查詢之外，MB020和MB099作為

表1 微博查詢方差統計

圖2 TREC 查詢“MB036”，“MB078”，“MB020”，“MB099”的標注相關文檔時間分布圖

一般查詢的代表，方差分別為 69.706 7 和 185.702 4。從圖2可以看出MB036的所有相關文檔都分布在了第二天，這也是其方差最大的原因；而MB078的分布更趨向于均勻分布。而查詢MB020和MB099都具有很明顯的波峰。綜上所述，通過統計分析， 微博查詢的標注相關文檔在各個時刻的分布是不均勻的，大部分查詢都具有明顯的高峰時刻，這個觀察結果也進一步證實了文獻[3]的結論，即微博查詢是時間敏感查詢。

在從微博文檔和微博查詢兩個角度分析微博檢索與傳統檢索的區別后，我們可以了解到微博具有很多網頁中不具備的特征，并且微博查詢大都是時間敏感查詢。因此，如何利用微博文檔的獨有特征，

如何考慮微博查詢的時間敏感性，對微博檢索技術研究提出了挑戰。在下面的小節中，我們會從這兩個方面分別整理已有工作，并對未來的研究問題進行總結和展望。

3 微博檢索的相關研究

通過第2節的對比分析可以得知，微博檢索和傳統文本檢索從文檔和查詢兩方面具有不同： 微博文檔具有多種特征；微博查詢具有時間敏感性。針對這兩方面，在如下小節中，我們將分別介紹基于微博特性的檢索研究相關工作，以及對應于時間敏感查詢的時間感知檢索技術。

3.1 信息檢索模型

信息檢索定義為[12]“信息檢索是從大規模非結構化數據(通常是文本)的集合(通常保存在計算機上)中找出滿足用戶信息需求的資料(通常是文檔)的過程”。詞袋模型(Bag of Words，BOW)是常用的文本表示方法。針對一個文本，該模型假設文本中的每個詞都是獨立的，詞和詞之間不存在依賴關系，文本中的詞序、語法、句法等信息均被忽略。在本節中，我們將介紹基于BOW假設的兩種代表性模型： 經典概率模型和一元統計語言模型。

3.1.1 經典概率模型

經典概率模型是基于概率論的理論基礎提出的，其排序原則是針對一個給定查詢，估計兩個概率模型，分別為相關性模型和非相關性模型，然后基于優勢率比率對文檔打分，從而得到排序結果[12-13]。發展至今常用的基于Okapi BM25權重計算機制構建的檢索模型的公式如下所示[14]。

(1)

其中t是詞項；N是語料庫中的文檔個數；dft是該詞項在語料庫中的文檔頻率；tftd是該詞項在文檔D中的出現次數；同理，tftq是該詞項在查詢Q中的出現次數；Ld是文檔長度；Lave是語料庫的平均文檔長度；k1,k2,k3,b為模型參數，已有實驗表明，k1和k3的取值范圍通常為1.2～2，b通常取值0.75。

3.1.2 一元統計語言檢索模型

1998年,Ponte和Croft首次把統計語言建模技術(StatisticalLanguageModel,SLM)應用于信息檢索領域，并獲得了非常好的實驗效果[15]。一元語言模型忽略了詞和詞之間的關系，其排序的基本思想是認為查詢和文檔都是語言單元的序列，因此可以對其構建語言模型。最早提出的基于語言模型的是查詢似然模型(QueryLikelihoodModel)[15-17]，即給定一個查詢Q和一篇文檔D，針對文檔D構建描述該文檔的語言模型，然后將文檔D按照它與查詢Q相關的似然分值p(D|Q)排序。根據貝葉斯理論，同時使用Jelinek-Mercer(簡稱JM)平滑方法[17]，得到的最終排序函數如式(2)所示。

(2)

式(2)中的tft C是指詞項t在語料庫中的出現次數。

3.2 基于微博特性的微博檢索研究

微博文檔具有多種特征，下面所列舉的論文涉及了有關于微博特性的檢索研究工作，具體內容描述如下：

Nagmoti, Teredesai[18]針對微博搜索提出了幾個微博特性，并進行了驗證。論文中考慮的微博特性有： 微博作者發布的微博個數、微博作者的關注數和粉絲數、微博的長度、微博是否含有URL。其中，微博作者的關注數和粉絲數作為該用戶的入度出度定義函數表示作者的權重。驗證方法選擇的是對特定查詢在商業搜索引擎的top-k 結果進行重排序，判斷重排序后的結果是否有提高。最終得到的結論是，后三者特性的結合得到的效果最好。

Ferguson, O’Hare[19]驗證了傳統檢索模型中帶來提升的詞項頻率(Term Frequency，TF)和文檔長度歸一化(Document Length Normalization，DLN)對于微博檢索的影響，文中采取的排序模型為BM25模型(屬于經典概率模型)。結果表明，忽略TF時，效果僅比最優結果的P30低了0.004 8，而忽略DLN時，效果達到最優。論文最后提出，TF和DLN都是在語言模型建模過程中會涉及的因子，所以在構建語言模型時應考慮如何減少二者的負影響。Massoudi, Tsagkias[20]在對微博構建語言模型的時候，便忽略TF的影響，即將詞的出現記為1，不出現記為0，而不考慮詞項出現的次數。

Efron[21]是基于統計語言模型，利用微博的hashtag以及hashtag之間的關系，提出了新的查詢擴展方法，在數據集上證明hashtag有利于信息檢索。論文將一個微博語料庫中的hashtag提取出來，得到hashtag集合；通過含有該標簽的微博構建標簽的一元語言模型(記為Mtag)。設查詢Q的語言模型為MQ，然后用KL公式計算Mtag和MQ的距離分值，選擇出得分靠前的k個tag，用來反饋MQ。另外，論文中通過定義同時出現這兩個標簽的文本個數作為標簽之間的關系權重，修改原有得分。

李銳和王斌[22]提出了一種基于作者建模的微博檢索方法。論文首先在TRECMicroblogSearch任務的語料集中抽取作者信息，整理每個作者發布的所有微博記錄構成新“文檔”，然后基于語言模型理論構建用戶的語言模型，提出了加入用戶模型的平滑方式來估計新的微博文檔詞項概率。最后在該數據集上進行了檢索實驗。結果表明，合理使用作者信息可以提高微博檢索的效果。

TREC(TextRetrievalConference)，全稱為文本檢索會議，是文本檢索領域最權威的評測會議，涉及多個方向，如傳統Web檢索、QA等。面對發展迅猛的微博，TREC于2011年添加了MicroblogSearch評測，提供了從2011年1月23日到2011年

2月8日共17天的Twitter數據以及50個查詢(Topics)和標注的文檔集。多個參與者將自己算法所得到的搜索結果提交到TREC負責組，然后TREC負責組按照評價指標進行排序，得到各個參與者的算法排名。在這里，由于篇幅所限，我們不對TREC2011MicroblogTrack前10名參與者*有一名參與者沒有提交報告，所以共9篇報告。的相關報告進行詳細介紹，而是直接進行總結(分別對應表2中的論文23～31)。

如2.1小節所指出，在本文中，我們將微博的特征劃分到三個類別： 內容屬性、用戶屬性、結構屬性(或稱為鏈接屬性)。表2是對利用微博特征的檢索研究工作的總結，其中標記“√”表示該篇論文所提的方法中涉及或者利用這種屬性特征，這些特征的名稱在表格下方有具體解釋。

表2 利用微博特性的微博檢索研究總結

①論文29與論文22是同一個作者的文章，29是以TREC報告的形式提交的英文文檔。

(1) 內容屬性

i) Term：

TF： 詞頻，即某個詞在整個文檔集中出現的次數

DF： 文檔頻率，即某個詞出現的文檔個數

Other： 廣義的關于詞的特征： 包括語義、詞依賴、是否屬于未定義詞、句法信息、語義信息、N-Grams信息

ii) Length： 是否進行了文檔長度歸一化處理

iii) Hashtag： 是否包含Hashtag；Hashtag詞內容

iv) Url： 是否包含Url；Url所指向的網頁內容

v) Reply： 是否是另一篇微博的回復

vi) Mention(@)： 微博內容是否@某個微博用戶

(2) 用戶屬性

i) MCount： 用戶發布的微博個數(Microblog Count)

ii) Fan&Follow： 用戶的關注數和粉絲數

iii) TMT： 用戶發布的微博全部內容(Total Microblog Text)

(3) 結構屬性

B-Hashtag(Between Hashtag，即Hashtag之間的關系),使用共有Hashtag的微博個數來表示

總體來說，面向微博特性的檢索研究中，基于內容屬性的檢索研究相對較多，利用用戶信息和結構信息提高檢索效果的研究較少?？偨Y已有工作，有如下結論：

(1) 大部分論文都是基于已有檢索模型進行修改，最常用的模型為BM25和統計語言模型；

(2) TF特征涉及次數較多是由于已有檢索模型中含有TF，但是由于微博文本短，信息量不足，研究表明TF對于微博檢索效果的提升并不明顯；

(3) 微博中的Hashtag和Url特征對檢索效果有提高，而文檔長度歸一化以及為Reply則有反作用；

(4) 引入Url所代表的網頁信息用來提高微博文本，對檢索性能有提高；

(5) 用戶所發的其他微博信息被用于修改權重或者擴充文本都提高了檢索性能。

3.3 面向時間敏感查詢的檢索相關研究

我們將針對時間敏感查詢的檢索方法統稱為時間感知的信息檢索技術，目的是在傳統檢索模型中融入時間因素從而得到更優的檢索效果。在檢索過程中考慮時間特性，并不是微博檢索領域中特有的研究內容，它是近年來面向具有時間特性的文檔集(如新聞、博客、微博等)的檢索時的重要研究內容。接下來，我們將以基本的信息檢索過程為思路介紹相關工作，圖3顯示的便是基本的信息檢索過程。

圖3 信息檢索過程*圖3中實線表明在檢索過程中涉及的技術，虛線表明輸入和輸出。

如圖3所示，用戶將其需求信息表示為一個文本字符串(查詢Q)，它和語料庫中的文檔進一步分別得到查詢和文檔的文本表示，然后將其輸入到定義好的排序函數中得到查詢和文檔的相似度分值，最終將所有文檔按照得分從高到低返回給用戶。不同的文本表示方法和排序函數定義代表不同的檢索模型。

在檢索過程中，查詢擴展技術(Query Expansion)和引入文檔先驗信息(Document Prior)是期望獲得更理想檢索結果的兩種常用的方法。查詢擴展技術能解決用戶查詢和用戶信息需求不一致的問題。通常用戶查詢是其需求的不完全不準確表述，查詢擴展通過初步搜索結果調整或添加查詢詞獲得更符合描述用戶需求的查詢。文檔先驗信息是指由于語料庫本身具有的背景信息，不同的文檔具有不同的重要性，文檔的重要性會影響其在搜索結果中的排序位置。需要說明的是，這里的文檔是泛化的概念，可以指代一篇微博、一個網頁，也可以指一段視頻、一張圖片，在本文中，文檔是指文本數據。PageRank算法是文檔先驗信息的代表方法，它通過網頁之間的指入指出鏈接關系計算出每個網頁的等級，作為網頁的離線先驗信息。

目前，基于時間感知的檢索技術的相關研究非常多，以信息檢索基本過程為主線(圖3)，我們將主要介紹針對以下三方面的相關研究： 文本表示、文檔先驗、查詢擴展。

3.3.1 關于文本表示的研究

文本表示是排序模型的基礎，查詢和文檔的形式化定義決定著排序函數的定義方式。在統計語言檢索模型的背景下，文本表示便是對文本構建語言模型，即如何計算詞項生成概率P(t|MD)。據我們所知，目前在p(t|MD)中加入時間因素的方法，主要有兩種： 一種是通過引入時間因素對詞項t定義時間權重[32-33]，另一種是在對語言模型概率估計平滑的過程中引入時間[34]。

Kanhabua和Nrv?g[32]的研究中通過時間性語言模型(TemporalLanguageModel，TLM)來確定文檔時間。雖然其并不是關于文本檢索的研究，但是其中關于對詞項t引入時間的思想可以用于文本檢索。需要說明的是，此時的數據集會按照時間粒度分成多塊，記為P，時間粒度可自由選取，例如，1個月、3個月等。作者在文中針對詞項t定義了一個時間權重，稱為時間熵(TemporalEntropy，TE)，其計算公式如式(3)所示。

(3)

(4)

Efron和Golovchinsky[34]對文檔語言模型的改進在于對平滑部分的改進，論文認為平滑權重的取值應該根據文檔時間的不同而不同，文檔越新，λ的取值應該越小，也就是說應該偏向考慮文檔自身。據此假設，在平滑公式中，引入新的平滑參數λt，并給出兩種計算公式，分別為：

(5)

(6)

其中n(D,t

衛冰潔和王斌[35]提出了一個融合聚類和時間的微博排序模型。作者在文中通過對比微博檢索和傳統信息檢索得出，微博文檔屬于短文本，信息量的不夠豐富不利于構造準確的語言模型；同時微博文本中含有主題概括詞(#標簽，稱為Hashtag)，有利于確定微博與查詢的相關程度；微博查詢大都是時間敏感查詢，在計算查詢與文檔的語義相似度的同時應該考慮時間信息。這三個特點對于微博搜索都非常重要，因此，該文針對微博文檔的特征和微博查詢的時間性提出了融合多因素的檢索方法。具體地，該工作使用聚類方法達到融合微博的Hashtag信息和對微博文本進行擴充的目的，并通過定義文檔的時間先驗在排序模型中引入時間因素。實驗結果表明，與原始檢索模型相比，該文提出的方法具有更優的微博檢索性能。

3.3.2 關于文檔先驗的研究

文檔先驗是指語料庫中的文檔具有的不同重要性?？紤]語料庫背景定義不同的文檔先驗計算公式，再將計算結果用于檢索模型以期得到更好的檢索效果。目前考慮時間信息計算文檔先驗的研究工作可以分為兩種： 一種定義文檔先驗和發表時間的變化關系，一種在其中加入時間特性定義鏈接關系來修改PageRank算法。

3.3.2.1 文檔先驗—PageRank算法

PageRank算法[36]屬于鏈接分析的范疇，主要是對根據網頁之間存在的超鏈接而形成的網絡圖進行分析，確定每個網頁的重要程度。PageRank認為當網頁A頁面上存在指向網頁B的鏈接時，就說明網頁A認可網頁B，由此，根據每個網頁的指出鏈接和指入鏈接的數量和質量決定每個網頁的等級。其基本思想為，設定一個用戶從當前網頁出發，在網絡中進行如下隨機游走過程： 在每一步中，用戶會從當前網頁的鏈出鏈接中隨機挑選一個或者以一定概率直接跳轉到別的網頁，然后繼續瀏覽。計算公式如式(7)所示。

(7)

其中，T代表一個網頁；d是隨機游走概率，取值范圍為0到1；InLink(T)是指向網頁T的網頁集合；C(Ti)表示網頁Ti的鏈出網頁個數。

3.3.2.2 定義文檔與發表時間關系的方法

Li和Croft[11]認為文檔根據其發表時間不同，具有不同的先驗概率。作者假設時間新的文檔的重要度大于時間舊的文檔，將文檔重要度定義為指數分布，公式如式(8)所示。

其中TD代表文檔的時間；TC代表文檔集中的最新時間；γ是指數分布的參數，人工指定。論文以統計語言模型為基礎，將上述文檔先驗P(D)代入到語言模型排序函數中。論文在TREC的新聞語料上做實驗，結果表明，加入時間特性的排序結果優于沒有時間的排序結果。

Efron和Golovchinsky[34]對文獻[11]提出的方法進行了改進，論文指出在不同查詢的條件下每篇文本的重要性是不同的，提出了根據查詢偽相關反饋估計指數分布參數的方法，即將上面公式中的λ修改為查詢相關的參數λq。設查詢Q的偽相關反饋集合記為P={d1,d2,…,dk}，用T={t1,t2,…,tk}表示集合P中文本的時間，根據最大似然估計思想，得到計算公式(9)。

(9)

衛冰潔和王斌[37]在微博環境下，以上面兩篇論文為基礎進行了微博先驗研究。論文指出，已有方法。不論是否與查詢有關，都基于假設“文本的時間越新越重要”。作者對微博查詢的相關文檔的時間分布進行了分析，發現大多數查詢的分布圖的最高點并不在最新時間，也就是說上述假設并不符合微博查詢的特點。由此，論文定義相關文檔時間分布的高點為查詢熱門時刻(HotTime)，提出新假設“在給定查詢的背景下，時間越靠近查詢熱門時刻，文本越重要”?；谠摷僭O，當給定查詢時，用該查詢的偽相關反饋文檔集合的時間分布來模擬真實相關分布，根據指數分布參數是否固定以及查詢熱門時刻個數是否自動化提出四個基于熱門時刻的語言模型(HotTimeLanguageModel，HTLM)。最后，作者將查詢無關模型看作是文檔的背景時間信息(即文獻[11]的方法)，將查詢有關模型看作是文檔的獨立時間信息(即文獻[11]的方法和HTLM系列模型)，引入平滑思想提出混合的時間模型(MixedTimedLM)。在TRECMicroblog數據集上的實驗表明，HTLM系列模型提高了檢索效果，同時混合模型的檢索性能優于單一模型。

3.3.2.3 基于PageRank思想的方法

在信息檢索中，PageRank(簡稱PR)通過分析網頁和網頁之間的鏈接關系表示文檔的重要度。文獻[38-41]是一系列通過修改原始PR算法加入時間因素的研究工作。

Yu,Li[38]提出傳統的PageRank或者HITS算法在分析網頁鏈接時忽略了時間維度的信息，因此基于此出發點提出TimedPageRank(簡稱TPR)算法，計算公式如式(10)所示。

(10)

其中wTi=b(max time(C)-time(Ti)),maxtime(C)是文檔集C中的最新時間，time(Ti)是文檔Ti的發表時間，b是經驗常數。

Berberich,Vazirgiannis[40]改變加入時間的方式，提出了算法T-Rank。作者認為用戶從當前頁面跳轉到該頁面的鏈出網頁上時，根據鏈出網頁的不同，其跳轉概率也不同；同時，用戶隨機選擇一個頁面的概率也因為當前頁面不同而不同，由此文中定義了兩種概率，也可稱為權重： 一個是從頁面T跳轉到該頁面的鏈出網頁集中的某個頁面Ti的傳播概率，記為t(Ti,T)； 一個是當前頁面的隨機跳轉權重，記為s(T)。修改后的公式如式(11)所示。

TRank(T)= (1-d)*s(T)+

(11)

實驗結果驗證了上述方法的有效性。同理Amitay, Carmel[39]，通過分析網頁的last-modified 標簽的特性，將其加入到PageRank當中，作為網頁的之間邊的權重。

Wan 和Bai[41]提出關于網頁的一個新定義： 網頁的time-activity程度，記為TR(T)。同時根據數據集，通過分析時間特性，得到了三個根據時間計算出來的常數。根據常數代表的數值范圍，將網頁分為四類： 1)強時間性；2)弱時間性普通質量；3)弱時間性高質量；4)無時間性。這里的質量即網頁的PR值。最終的網頁先驗計算公式為式(12)所示。

(12)

3.3.3 關于查詢擴展的研究

查詢擴展是指在原查詢基礎上，加入與該查詢相關聯的新詞，從而構成新的更準確的查詢，它在一定程度上克服了查詢信息不足以及詞不匹配的缺陷，提高了信息檢索的效果。隨著網絡的發展，信息更新速度加快，使得檢索文檔的新穎性在排序中越來越重要，因此出現了在擴展查詢詞的過程中考慮時間維度的查詢擴展方法。下面介紹一些關于時間感知的查詢擴展的相關工作，根據融入時間方式的不同主要分為兩種： 一種是通過分析時間點上的文檔分布特點，選擇合適的時間點作為文檔選擇的基礎，再進行查詢詞擴展；一種是利用詞與詞之間的關系構建圖，通過迭代計算得到詞對于給定查詢的相關分值，從而選取得分高的詞項進行擴展。

3.3.3.1 查詢擴展

用戶根據其信息需求構造的查詢往往較短，導致查詢詞信息量不足，無法得到滿意的搜索結果。查詢擴展技術通過調整和添加與原始查詢相關的詞項以提高檢索結果的精度。查詢優化有多種方法，其中最常用的一種方法是偽相關反饋(PseudoRelevanceFeedback)技術。偽相關反饋是一種自動分析方法，它首先在已有語料庫中進行正常的檢索，然后得到一系列搜索出的文檔，接下來假設排名在前的k篇文檔是相關的，由此構成針對此查詢的相關文檔集合，再在這部分集合上進行分析計算得到新的更優的查詢來表達用戶的信息需求。查詢擴展是提高信息檢索效果的有效手段之一。

Rocchio相關反饋算法

Rocchio算法是Rocchio于1971年提出的[42]，是最經典的查詢擴展方法之一。Rocchio方法的主要思想是，給定一個查詢，同時該查詢的相關文檔集合和不相關文檔集合已知，那么在查詢和文檔被表示成為高維詞項空間中的向量的情況下，我們的目標是找到最優化的查詢向量，使得該向量與相關文檔相似度最大同時與不相關文檔相似度最小。根據上述描述，當相似度選擇余弦相似度時，我們可得到修改查詢的計算公式如式(13)所示[12]。

(13)

相關模型

相關模型(Relevance Model，RM)[43]是利用統計語言建模理論，采用偽相關反饋思想的查詢擴展模型。相關模型是一個多項式分布方法，最終目的是估計出在給定查詢的條件下詞項的生成概率。設Q=q1…qk表示查詢串，Dprf表示偽相關反饋文檔集合。RM的計算公式如式(14)所示。

(14)

根據上述公式，我們得到所有詞項在給定查詢Q的條件概率，由此按照得分高低排序得到最有可能用于擴展的詞項集合。然后通過線性方法，引入參數λ，結合原始查詢和擴展查詢，構造出新的查詢，得到新的詞項條件概率。

(15)

當查詢模型采用相關模型，文檔采用語言模型時，針對查詢和文檔的相似度計算變成了比較兩個概率模型之間的差別[17]。最常用的做法是采用KL距離作為模型相似程度的標準，公式如式(16)所示。

(16)

3.3.3.2 利用時間點的方法

文獻[44-45]提出的查詢擴展方法是在偽相關反饋文檔集上做統計處理，選取最終擴展詞，實驗均表明方法有利于信息檢索。

Peetz,Meij[45]是按照文檔時間T，統計在第一次搜索文檔集中出現在每個時間t的文檔個數，然后選擇在出現個數最高的時間time附近的TopN篇文檔，最后利用Rocchio算法計算每個詞項的評分選擇擴展詞。論文在數據集上驗證上述方法提高了檢索效果。

Amodeo,Amati[44]將查詢的第一次搜索文檔集(R)，根據每篇文檔D的時間T，按照指定的規則，分為突發集B(可有一個或多個)，突發集的集合記為bursts(R)，然后根據式(17)：

(17)

計算每個詞的打分。最終挑選出前TopN個作為查詢擴展詞。實驗結果表明，該方法有效。

Keikha,Gerani[46]在博客檢索的背景下，從相關模型的思想出發，定義了一個考慮時間的P(t|Q)生成式模型，計算得分，選取排序靠前的擴展詞。論文認為P(t|Q)的生成過程為，查詢Q首先選擇了一個時間T，然后，再在T和Q的條件下選擇一個t，由此得到的查詢生成詞的模型公式為式(18)。

(18)

在TREC數據集Blog08上的實驗表明該方法提高了檢索效果。

Miyanishi,Seki[47]通過對Twitter發布的微博查詢進行分析， 指出微博查詢具有兩種時間表示特性： 分別為recency和temporalvariation。前者是指相關文檔大多分布在查詢被提交的時刻的現象；后者是指相關文檔在不同時刻分布不同的現象。作

者認為這兩者屬性對于一個查詢而言是缺一不可的，由此針對這兩個屬性分別提出一種查詢擴展方法，最終通過總結這兩個查詢擴展方法得到最終的檢索結果。實驗表明，文中提出的方法有利于檢索效果的提高。

3.3.3.3 基于圖的方法

Whiting,Klampanos[48]是在微博檢索的環境下，提出了一種基于PageRank理念，計算詞權重的查詢擴展方法。首先，從初次返回結果中抽取N-grams；然后，對N-grams構建有向圖，N-grams作為點，把詞項的TF為點的先驗取值；邊表示指向關系，權重為詞和詞之間的時間特性的相關程度；最后運用PageRank隨機游走的思想，計算出每個N-gram的最終取值，選擇部分用于擴展原始查詢。實驗是基于TREC的Twitter數據集，完成的結果驗證了方法的有效性。

3.3.4 總結

表3列出的是時間感知的信息檢索相關研究的總結。我們根據信息檢索過程，主要介紹了利用時間在文檔先驗、查詢擴展和文本表示三種技術中提高檢索效果的已有工作。這些研究均表明運用時間的檢索模型普遍對檢索性能有提升，特別是針對具有時間特性的數據集上，例如,微博、新聞、博客等。與此同時，我們也發現基于時間感知的微博檢索研究尚少，還存在很多有待深入研究的問題，是一個需要挖掘的研究方向。

表3 時間感知的信息檢索研究總結

4 總結及未來工作展望

微博是當今互聯網數據的重要組成部分，微博檢索具有重要的研究和應用價值。首先，我們以TREC Microblog 數據為分析對象，從微博文檔和微博查詢兩個方面出發，對比了微博檢索與傳統檢索，提出當前的檢索技術并不能直接用于微博背景下。原因有兩個： 第一個是微博文檔不同于傳統網頁，具有很多特點；第二個是微博查詢屬于時間敏感查詢，需要在傳統檢索技術中引入這個重要因素。然后，本文對這兩部分相關研究工作進行了整理和總結。首先介紹了針對微博特性的檢索相關研究，研究表明將從微博提取出的特征用于信息檢索模型，可以提高檢索的效果。然后以信息檢索基本過程為主線，分別介紹了時間信息融入文本表示、文檔先驗和查詢擴展技術中的方法，并對相關工作進行了概括總結。研究表明，在對有時間特性的數據進行檢索時，例如,微博、新聞、博客等，在檢索模型中加入時間信息有利于優化檢索性能，提高用戶滿意度。

通過對微博檢索的國內外研究現狀的調查，我們發現有待深入研究的微博檢索問題還有很多，列舉部分如下：

1. 微博各方面屬性的研究程度尚淺，沒有進行特征的分類整理和對比分析，也沒有統一的檢索框架可以融合多方面屬性，這部分工作有待繼續挖掘。

2. 在利用時間因素的各種檢索方法中，均采用了文檔的發表時間。但是針對微博文檔，其還具有評論時間和轉發時間，這些時間構成了微博的時間段，如何利用時間段改進已有技術是一個可研究的問題。

3. 微博文檔短且口語化嚴重，如何在檢索過程中擴充文本過濾掉噪音文檔、保留更多相關文檔是微博檢索的一個難點。

4. 基于統計信息進行文本表示的前提是文本信息量足夠，而微博由于字數限制導致信息嚴重缺失，因此如何擴充微博提高文本表示的信息量是一個長期的研究課題。

5. 微博之間存在多種鏈接關系，比如用戶關注關系、微博轉發關系、微博評論關系，如何利用這些關系計算微博的重要度以期優化檢索結果有待進一步研究。

[1] 中國互聯網絡信息中心.第31次中國互聯網絡發展狀況統計報告[R].2013.

[2] Efron M. Information search and retrieval in microblogs[J]. Journal of the American Society for Information Science and Technology, 2011. 62(6):996-1008.

[3] Teevan J., Ramage D.,Morris M. R. #TwitterSearch: a comparison of microblog search and web search[C]//Proceedings of the fourth ACM international conference on Web search and data mining.Hong Kong, China.2011: 35-44.

[4] Girolami M.,Kab n A. On an equivalence between PLSI and LDA[C]//Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval.Toronto, Canada.2003: 433-434.

[5] 陳淵, 林磊, 孫承杰, 等. 一種面向微博用戶的標簽推薦方法[J].智能計算機與應用, 2011. 1(3):21-26.

[6] Spiliopoulou M.Evolution in Social Networks: A Survey, Social Network Data Analytics[C]//Social Network Data Analytics. Springer US.2011:149-175.

[7] Sakaki T., Okazaki M.,Matsuo Y. Earthquake shakes Twitter users: real-time event detection by social sensors[C]//Proceedings of the 19th international conference on World wide web.Raleigh. North Carolina, USA.2010: 851-860.

[8] Petrovic S., Osborne M.,Lavrenko V., Streaming first story detection with application to Twitter[C]//Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics. PA USA.2010: 181-189.

[9] Mathioudakis M.,Koudas N. TwitterMonitor: trend detection over the twitter stream[C]//Proceedings of the2010 International Conference on Management of Data. New York.2010: 1155-1158.

[10] Cataldi M., Caro L. D.,Schifanella C. Emerging topic detection on Twitter based on temporal and social terms evaluation[C]//Proceedings of the Tenth International Workshop on Multimedia Data Mining.Washington, D.C.2010: 1-10.

[11] Li X.,Croft W. B. Time-based language models[C]//Proceedings of the twelfth international conference on Information and knowledge management.LA, USA.2003: 469-475.

[12] 王斌, 信息檢索導論[M]. 人民郵電出版社, 2010.

[13] Zhai C. Statistical Language Models for Information Retrieval[J].Synthesis Lectures on Human Language Technologies, 2008. 1(1):1-141.

[14] Robertson S. E.,Walker S. Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval[C]//Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval.Dublin, Ireland.1994: 232-241.

[15] Ponte J. M.,Croft W. B. A language modeling approach to information retrieval[C]//Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval.Melbourne, Australia.1998: 275-281.

[16] Song F.,Croft W. B. A general language model for information retrieval[C]//Proceedings of the eighth international conference on Information and knowledge management.Missouri, United States.1999: 316-321.

[17] Zhai C.,Lafferty J. Model-based feedback in the language modeling approach to information retrieval[C]//Proceedings of the tenth international conference on Information and knowledge management.Georgia, USA.2001: 403-410.

[18] Nagmoti R., Teredesai A.,Cock M. D.Ranking Approaches for Microblog Search[C]//Proceedings of the 2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology.Washington, DC.2010: 153-157.

[19] Ferguson P., O'Hare N., Lanagan J., et al.An Investigation of Term Weighting Approaches for Microblog Retrieval[C]//Proceedings of the 34th European conference on Advances in Information Retrieval. Berlin Heidelberg. 2012: 552-555.

[20] Massoudi K., Tsagkias M., Rijke M., et al.Incorporating Query Expansion and Quality Indicators in Searching Microblog Posts[C]//Proceedings of the 33rd European conference on information retrieval. Berlin Heidelberg. 2011:362-367.

[21] Efron M. Hashtag retrieval in a microblogging environment[C]//Proceedings of the 33rd international ACM SIGIR conference on Research and development in information retrieval.Geneva, Switzerland.2010: 787-788.

[22] 李銳,王斌. 一種基于作者建模的微博檢索模型[J].中文信息學報, 2014.28(2):136-143.

[23] Metzler D.,Cai C. USC/ISI at TREC 2011: Microblog Track[R]. Text Retrieval Conference (TREC).2011.

[24] Amati G., Amodeo G., Bianchi M., et al. FUB, IASI-CNR, UNIVAQ at TREC 2011 Microblog track[R]. Text Retrieval Conference (TREC).2011.

[25] Li Y., Zhang Z., Lv W., et al. PRIS at TREC2011 Micro-blog Track[R]. Text Retrieval Conference (TREC).2011.

[26] Miyanishi T., Seki K.,Uehara K. TREC 2012 Microblog Track Experiments at Kobe University[R]. Text Retrieval Conference (TREC).2011.

[27] Ferguson P., O'Hare N., Lanagan J., et al. CLARITY at the TREC 2011 Microblog Track[R]. Text Retrieval Conference (TREC).2011.

[28] Roegiest A.,Cormack G. V. University of Waterloo at TREC 2011: Microblog Track[R]. Text Retrieval Conference (TREC).2011.

[29] Li R., Wei B., Lu K., et al. Author Model and Negative Feedback Methods on TREC 2011 Microblog Track[R]. Text Retrieval Conference (TREC).2011.

[30] Hong D., Wang Q., Zhang D., et al. Query Expansion and Message-passing Algorithms for TREC Microblog Track[R]. Text Retrieval Conference (TREC).2011.

[31] Li Y., Dong X.,Guan Y. HIT_LTRC at TREC 2011 Microblog Track[R]. Text Retrieval Conference (TREC).2011.

[32] Kanhabua N.,N rv g K., Using Temporal Language Models for Document Dating[C]//Machine Learning and Knowledge Discovery in Databases. Berlin Heidelberg. 2009:738-741.

[33] Li X., Jin P., Zhao X., et al.NTLM: A Time-Enhanced Language Model Based Ranking Approach for Web Search Web Information Systems Engineering[C]//the 1st International Symposium on Web Intelligent Systems and Services.Berlin Heidelberg. 2010:156-170.

[34] Efron M.,Golovchinsky G. Estimation methods for ranking recent information[C]//Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval.Beijing, China.2011: 495-504.

[35] 衛冰潔,王斌. 一種融合聚類和時間信息的微博排序新方法[J].中文信息學報, 已錄用.

[36] Brin S.,Page L. The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks and ISDN Systems, 1998. 30(1-7):107-117.

[37] 衛冰潔,王斌. 面向微博搜索的時間感知的混合語言模型[C]//全國信息檢索學術會議(CCIR).南昌,江西.2012.

[38] Yu P. S., Li X.,Liu B. On the temporal dimension of search[C]//Proceedings of the 13th international World Wide Web conference.New York, USA.2004: 448-449.

[39] Amitay E., Carmel D., Herscovici M., et al. Trend detection through temporal link analysis[J].Journal of the American Society for Information Science and Technology,2004. 55(14):1270-1281.

[40] Berberich K., Vazirgiannis M.,Weikum G. Time-Aware Authority Ranking[J].Internet Mathematics, 2005. 2(3):301-332.

[41] Wan J.,Bai S. An improvement of PageRank algorithm based on the time-activity-curve[C]//The 2009 IEEE International Conference on Granular Computing.2009: 549-552.

[42] Salton G.The SMART Retrieval System: Experiments in Automatic Document Processing[M].Upper Saddle River. Prentice-Hall, Inc.1971.

[43] Lavrenko V.,Croft W. B. Relevance based language models[C]//Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval.Louisiana, USA.2001: 120-127.

[44] Amodeo G., Amati G.,Gambosi G. On relevance, time and query expansion[C]//Proceedings of the 20th ACM international conference on Information and knowledge management.Scotland, UK.2011: 1973-1976.

[45] Peetz M.-H., Meij E., Rijke M. d., et al. Adaptive temporal query modeling[C]//Proceedings of the 34th European conference on Advances in Information Retrieval.Barcelona, Spain.2012: 455-458.

[46] Keikha M., Gerani S.,Crestani F. Time-based relevance models[C]//Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval.Beijing, China.2011: 1087-1088.

[47] Miyanishi T., Seki K.,Uehara K., Combining Recency and Topic-Dependent Temporal Variation for Microblog Search[C]//Advances in Information Retrieval. Berlin Heidelberg. 2013:331-343.

[48] Whiting S., Klampanos I. A.,Jose J. M. Temporal pseudo-relevance feedback in microblog retrieval[C]//Proceedings of the 34th European conference on Advances in Information Retrieval.Barcelona, Spain.2012: 522-526.

A Survey of Microblog Search

WEI Bingjie1,3, WANG Bin2, ZHANG Shuai1, LI Peng2

(1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; 3. National Computer Network Emergency Response Fechnical Team/Coordination Center of China, Bejing 100029, China)

With the rapid development of microblog, microblog retrieval has become one of the hot research areas in recent years. Firstly, in this paper, we analyze microblog documents and queries based on the TREC Microblog dataset. We found that, in contrast to traditional text retrieval, microblog search significantly differs in two ways. One is that microblog has its own characteristics compared to webpage. And the other is that microblog queries are time-sensitive, which means time information should be used in addition to traditional text similarity. According to these two differences, traditional text retrieval methods cannot be directly used in microblog search. Then, the related work on the two aspects of microblog retrieval is summarized. We described some microblog features and retrieval methods based on these features. According to the process of information retrieval, search models which use temporal information as the document priori or for query expansion or for text representation are also introduced. At last, we provide the conclusion and discuss the future work.

microblog search; temporal information; microblog feature; text representation; document priori; query expansion

衛冰潔(1987—)，博士，中級工程師，主要研究領域為微博檢索及數據挖掘。E?mail：weibingjie1986@163．com王斌(1972—)，博士，研究員，主要研究領域為信息檢索及自然語言處理。E?mail：wangbin@iie．ac．cn張帥(1987—)，碩士，工程師，主要研究領域為微博分類及信息檢索。E?mail：zhangshuai01@ict．ac．cn

1003-0077(2015)02-0010-14

2013-05-02 定稿日期： 2013-08-02

科技支撐計劃(2012BAH46B02)

TP391

A