衛(wèi)冰潔，史 亮，王 斌

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190；2. 中國(guó)科學(xué)院 信息工程研究所，北京 100093；3. 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029)

?

一種融合聚類(lèi)和時(shí)間信息的微博排序新方法

衛(wèi)冰潔1,3，史 亮3，王 斌2

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190；2. 中國(guó)科學(xué)院 信息工程研究所，北京 100093；3. 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029)

隨著微博的快速發(fā)展，微博檢索已經(jīng)成為近年來(lái)研究領(lǐng)域的熱點(diǎn)之一。微博檢索與傳統(tǒng)文本檢索在兩個(gè)方面明顯不同： 一是微博具有自己的特點(diǎn)，表現(xiàn)在文本短和內(nèi)容中具有主題概括詞(稱(chēng)為Hashtag)；二是微博排序中除了考慮文本和語(yǔ)義相似度，還需考慮時(shí)間信息。根據(jù)這兩點(diǎn)區(qū)別，該文在統(tǒng)計(jì)語(yǔ)言模型的基礎(chǔ)上，使用聚類(lèi)進(jìn)行文本擴(kuò)展，并將Hashtag信息運(yùn)用到聚類(lèi)過(guò)程中。同時(shí)，因?yàn)槲⒉?shù)據(jù)集中具有Hashtag的微博個(gè)數(shù)不超過(guò)13%，針對(duì)這一現(xiàn)象，該文還提出了一種擴(kuò)展微博Hashtag的方法，最終提出了基于聚類(lèi)的三個(gè)模型。然后通過(guò)定義文檔先驗(yàn)將時(shí)間信息加入到提出的三個(gè)檢索模型中，得到融入聚類(lèi)和時(shí)間信息的三個(gè)模型。最后基于TREC Microblog數(shù)據(jù)的實(shí)驗(yàn)結(jié)果證明，融合聚類(lèi)信息和時(shí)間信息的模型在MAP和P@30上有明顯提高，分別提高7.1%和11.6%。

微博檢索；Hashtag；聚類(lèi)；時(shí)間；語(yǔ)言模型

1 引言

微博，即微型博客(Microblog)，是區(qū)別于傳統(tǒng)博客的一種互聯(lián)網(wǎng)產(chǎn)品。用戶(hù)通過(guò)網(wǎng)絡(luò)、客戶(hù)端等即時(shí)發(fā)布信息，通常要求文本字?jǐn)?shù)不超過(guò)140個(gè)字，用戶(hù)也可以獲取他人發(fā)布的信息，實(shí)現(xiàn)信息的共享。目前全世界已有多個(gè)成熟的微博平臺(tái)，例如，Twitter、新浪微博、騰訊微博等。由于其所具有的便捷性、實(shí)時(shí)性，微博已經(jīng)成為了近年來(lái)最熱門(mén)的互聯(lián)網(wǎng)應(yīng)用之一。

隨著微博的廣泛流行，微博的用戶(hù)量和數(shù)據(jù)量均呈現(xiàn)爆發(fā)式的增長(zhǎng)。據(jù)CNNIC發(fā)布的第29次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告得知，目前國(guó)內(nèi)有近半數(shù)的網(wǎng)民在使用微博，約2.5億人。同時(shí)，Twitter、新浪微博、騰訊微博的注冊(cè)用戶(hù)總數(shù)也已超過(guò)3億。在如此巨大的用戶(hù)量的背景下，微博數(shù)據(jù)量也呈現(xiàn)指數(shù)級(jí)增長(zhǎng)。據(jù)報(bào)道指出，微博網(wǎng)站每日微博數(shù)量已經(jīng)達(dá)到億級(jí)別。在海量微博數(shù)據(jù)的背景下，用戶(hù)獲得所需信息的困難度日益增大，微博搜索的重要性不言而喻，是近年來(lái)研究領(lǐng)域的熱點(diǎn)之一。

微博搜索雖然屬于文本搜索的范疇，但是卻不同于傳統(tǒng)的文本搜索，它具有自己的特點(diǎn)，表現(xiàn)在兩個(gè)方面，第一個(gè)是搜索數(shù)據(jù)不同，第二個(gè)是排序原則不同。本文基于這兩方面區(qū)別深入對(duì)微博搜索進(jìn)行研究。

微博搜索面向的數(shù)據(jù)是微博。相較于傳統(tǒng)文本，微博具有文本短、含有主題詞(即Hashtag)等特點(diǎn)。聚類(lèi)是解決文本短、信息量不足的傳統(tǒng)方法之一[1]。 在統(tǒng)計(jì)語(yǔ)言檢索模型的基礎(chǔ)上，將聚類(lèi)結(jié)果以平滑方式加入到文檔概率計(jì)算公式中，修訂了文檔原有詞概率，擴(kuò)展了文檔未有詞概率，通過(guò)在TREC多個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，證明了加入聚類(lèi)信息對(duì)檢索效果有提高。與此同時(shí)，Hashtag是用戶(hù)為了表明該微博的主題而用兩個(gè)“#”號(hào)括起來(lái)的詞匯，統(tǒng)稱(chēng)為Hashtag，是微博的特征之一(圖1)。文獻(xiàn)[2-5]均表明Hashtag是微博檢索中有效的特征之一，加入Hashtag信息的檢索模型效果普遍優(yōu)于沒(méi)有加入Hashtag信息的檢索模型。

圖1 以“網(wǎng)絡(luò)地鐵”為Hashtag的微博

微博排序相對(duì)于傳統(tǒng)搜索排序，除了要考慮查詢(xún)和文本的語(yǔ)義相似度之外，還需要關(guān)注另一個(gè)因素即時(shí)間。Teevan, Ramage[6]對(duì)微博查詢(xún)和傳統(tǒng)查詢(xún)進(jìn)行了多維度的統(tǒng)計(jì)對(duì)比，他指出用戶(hù)進(jìn)行微博檢索時(shí)的搜索意圖均是跟時(shí)間有關(guān)的，也就是說(shuō)微博查詢(xún)大多屬于時(shí)間敏感查詢(xún)。而傳統(tǒng)搜索排序無(wú)法很好地解決這類(lèi)查詢(xún)的搜索需求，因此在針對(duì)微博搜索制定策略時(shí)，時(shí)間是不可忽略的因素。Li 和Croft[7]以及Efron 和Golovchinsky[8]等通過(guò)實(shí)驗(yàn)證明，加入時(shí)間因素可以提高微博檢索的效果。

總結(jié)前人的工作，聚類(lèi)是應(yīng)對(duì)微博文本短的一個(gè)有效辦法，Hashtag是微博的顯著特征，時(shí)間是微博排序算法中應(yīng)當(dāng)考慮的因素，這三者對(duì)于微博搜索都非常重要。但是目前尚未有相關(guān)工作，在微博排序中同時(shí)考慮這三方面因素，因此本文以統(tǒng)計(jì)語(yǔ)言檢索模型為基礎(chǔ)，研究如何融合Hashtag、聚類(lèi)、時(shí)間三因素于排序算法中，最終提出了一個(gè)融合聚類(lèi)和時(shí)間信息的排序方法，并在TREC Microblog 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證，結(jié)果表明融合多因素對(duì)微博搜索效果有明顯的提高作用。本文的貢獻(xiàn)列舉如下： 1)針對(duì)微博數(shù)據(jù)集中Hashtag存在率低的情況，本文提出了一種將微博文本作為“偽查詢(xún)”，利用其搜索結(jié)果進(jìn)行Hashtag補(bǔ)充和擴(kuò)展的方法；2)本文證明了Hashtag和時(shí)間這兩個(gè)因素對(duì)于微博檢索的重要性，有利于提高檢索的性能。

文章內(nèi)容組織如下： 第2節(jié)介紹相關(guān)工作；第3節(jié)介紹基于時(shí)間和聚類(lèi)的語(yǔ)言檢索模型；實(shí)驗(yàn)和結(jié)果分析將在第4節(jié)給出；第5節(jié)是對(duì)本文工作的總結(jié)和展望。

2 相關(guān)工作

統(tǒng)計(jì)語(yǔ)言檢索模型是利用了統(tǒng)計(jì)學(xué)和概率論理論的檢索模型，是三大信息檢索模型的一種，也是本文的研究基礎(chǔ)[9-11]?；诙囗?xiàng)式分布的查詢(xún)似然模型(Query Likelihood Model)是語(yǔ)言檢索模型的熱門(mén)模型之一[11]。設(shè)q表示查詢(xún)，d表示文檔，w表示詞， Md表示根據(jù)d構(gòu)建的語(yǔ)言模型[9]，QL模型的排序函數(shù)如式(1)所示。

(1)

其中，p(d)是指文檔的先驗(yàn)概率，tf(w,q)是指詞w在查詢(xún)q中的出現(xiàn)次數(shù)，稱(chēng)為詞頻，p(w|Md)是指詞w在文檔d所代表語(yǔ)言中的分布概率，在一元語(yǔ)言模型的假設(shè)和采用極大似然估計(jì)方法下，得到的計(jì)算公式如式(2)所示。

(2)

同時(shí)為了避免零概率事件，Zhai 和Lafferty[10]提出了多種平滑方法，本文將采用Jelinek-Mercer(簡(jiǎn)稱(chēng)JM)平滑，加入平滑后的概率計(jì)算公式為：

(3)

其中λ是平滑參數(shù)，Pml(w|Mcollection) 是整個(gè)數(shù)據(jù)集的語(yǔ)言模型概率。

Liu和Croft[1]提出了一個(gè)基于聚類(lèi)的統(tǒng)計(jì)語(yǔ)言檢索模型(CBLM，Cluster-BasedLanguageModel)。Liu和Croft首先對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)，然后使用該文檔所在的聚類(lèi)信息對(duì)文檔進(jìn)行平滑，由此給出了基于聚類(lèi)的文檔語(yǔ)言模型(CBDM，Cluster-BasedDocumentModel)，公式如下：

(4)

其中λ,β是平滑參數(shù)，Pml(w|Mcluster) 是該文檔所在聚類(lèi)的語(yǔ)言模型概率。論文在TREC的多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)證明加入聚類(lèi)信息的檢索結(jié)果優(yōu)于沒(méi)有加入聚類(lèi)信息的檢索結(jié)果。下文簡(jiǎn)稱(chēng)該方法為CBLM。

微博具有不同于傳統(tǒng)文本的多項(xiàng)特征，Hashtag是其中一項(xiàng)。Efron[2]提出了一個(gè)利用微博Hashtag的查詢(xún)擴(kuò)展方法。論文將微博語(yǔ)料庫(kù)中的Hashtag提取出來(lái)整合為Hashtag集合；然后通過(guò)含有該Hashtag的微博集合構(gòu)建該Hashtag的一元語(yǔ)言模型，記為 Mhashtag。 設(shè)查詢(xún)q的語(yǔ)言模型為 Mq， 用KL距離表明該Hashtag和查詢(xún)的相關(guān)程度，由此選擇前k個(gè)作為查詢(xún)擴(kuò)展詞。實(shí)驗(yàn)證明融入Hashtag信息有利于微博檢索。文獻(xiàn)[3-5]也在檢索模型中運(yùn)用到了Hashtag，并取得不錯(cuò)的效果。由此可知，微博的Hashtag對(duì)于微博檢索而言是很有效的可利用因素。

將時(shí)間融入統(tǒng)計(jì)語(yǔ)言模型，其中一種方法為引入文本的時(shí)間先驗(yàn)[7-8, 12]。Li和Croft[7]提出假設(shè)“文檔越新，其重要度越高”，由此定義以時(shí)間為輸入的指數(shù)分布來(lái)表示文檔的時(shí)間先驗(yàn)分值，公式如下：

(5)

其指數(shù)分布參數(shù)為α， 為人工給定，其中td代表文本的時(shí)間，tcollection代表文本集中的最新時(shí)間。最終論文通過(guò)在TREC新聞?wù)Z料集上做驗(yàn)證證明加入時(shí)間提高了搜索效果。Efron和Golovchinsky[8]在Li和Croft的基礎(chǔ)上進(jìn)行改進(jìn)，引入了查詢(xún)信息，通過(guò)查詢(xún)的偽相關(guān)反饋文檔計(jì)算指數(shù)分布的參數(shù)，公式如下：

(6)

(7)

衛(wèi)冰潔和王斌[12]在微博數(shù)據(jù)的背景下，對(duì)文獻(xiàn)[7]和文獻(xiàn)[8]進(jìn)行了更深入的研究。通過(guò)分析微博查詢(xún)的時(shí)間分布圖，定義了查詢(xún)的熱門(mén)時(shí)刻，給出新假設(shè)“文檔時(shí)間距熱門(mén)時(shí)刻越相近，文檔越重要”，提出基于熱門(mén)時(shí)刻的語(yǔ)言模型(Hot-TimeLanguageModel，HTLM)。本文將已有工作分為兩類(lèi)，一類(lèi)是與查詢(xún)無(wú)關(guān)模型P(dt)， 即Li和Croft提出的模型，一類(lèi)是查詢(xún)有關(guān)模型P(dqt)， 即Efron和Golovchinsky提出的模型以及HTLM模型，通過(guò)引入平滑思想，最終提出一個(gè)混合文檔先驗(yàn)計(jì)算方法，公式如下：

(8)

其中ω是平滑參數(shù)，取值為0～1。論文在TRECMicroblog數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)驗(yàn)證，結(jié)果表明，HTLM模型優(yōu)于已有工作，混合模型優(yōu)于單一模型。

綜上所述，聚類(lèi)有利于檢索效果的提高，融入Hashtag信息或者加入時(shí)間的排序模型在微博數(shù)據(jù)集上效果好于原有模型。但是加入聚類(lèi)信息是否利于微博搜索、如何將Hashtag信息融入聚類(lèi)中、如何克服只有少量微博具有Hashtag的困難、聚類(lèi)和時(shí)間融合是否將促進(jìn)檢索效果的提升等還尚未得到驗(yàn)證，本文將就這些問(wèn)題進(jìn)行深入研究和驗(yàn)證，最終提出一個(gè)利用時(shí)間信息和聚類(lèi)信息的語(yǔ)言檢索模型。

3 融合時(shí)間和聚類(lèi)信息的檢索模型

3.1 針對(duì)微博檢索的分析

檢索數(shù)據(jù)和用戶(hù)查詢(xún)是一個(gè)檢索過(guò)程的基本組成，這二者的特點(diǎn)也決定了檢索模型的選擇。那么我們分別從這兩方面詳細(xì)說(shuō)明微博檢索相對(duì)于傳統(tǒng)檢索的不同。

首先在微博搜索的背景下，數(shù)據(jù)不再是傳統(tǒng)網(wǎng)頁(yè)，而是新型數(shù)據(jù)： 微博。微博相較于以往的文本，具有很多獨(dú)有的特征，包括： 文本字?jǐn)?shù)限制在140個(gè)字以?xún)?nèi)和具有特殊符號(hào)“#”(稱(chēng)之為Hashtag)。文本字?jǐn)?shù)的限制帶來(lái)的是信息量的不足，而大部分傳統(tǒng)的檢索模型的前提是信息量充足，比如BM25以及語(yǔ)言模型。因此進(jìn)行微博內(nèi)容的擴(kuò)充是非常必要的，本文選擇聚類(lèi)作為擴(kuò)充方法?！?”在傳統(tǒng)網(wǎng)頁(yè)中并沒(méi)有特殊的含義，而它在微博中卻具有指定的意義： 用兩個(gè)“#”包圍著的詞通常為該用戶(hù)給出的關(guān)于這篇微博的主題詞，類(lèi)似于某些用戶(hù)給傳統(tǒng)網(wǎng)頁(yè)所打的標(biāo)簽。主題詞對(duì)于微博內(nèi)容的確定有很大關(guān)系，如果該主題詞與查詢(xún)相關(guān)，那么該篇微博內(nèi)容與主題相關(guān)的概率很高。但是在數(shù)據(jù)集中，具有Hashtag的微博個(gè)數(shù)非常少，是提出微博檢索方法時(shí)需要克服的問(wèn)題之一。

其次，針對(duì)于微博查詢(xún)的特點(diǎn)，已有多項(xiàng)研究表明微博查詢(xún)具有時(shí)間敏感性[6, 8, 12]。面向時(shí)間敏感查詢(xún)的搜索，傳統(tǒng)的檢索原則，即計(jì)算查詢(xún)和文檔的語(yǔ)義相似度，是不夠的，需要在檢索過(guò)程中引入時(shí)間的因素，從而使得一個(gè)文檔的排名不僅僅側(cè)重于它的語(yǔ)義相似度而同時(shí)與它的時(shí)間有關(guān)?？紤]微博查詢(xún)的時(shí)間特性，適用于微博的檢索模型需要引入時(shí)間信息。

基于上面從數(shù)據(jù)和查詢(xún)兩個(gè)角度分析微博的特點(diǎn)，本文分別設(shè)計(jì)了基于擴(kuò)展標(biāo)簽(Hashtag)的聚類(lèi)語(yǔ)言模型和融合時(shí)間和聚類(lèi)信息的微博檢索模型，以期得到更優(yōu)的微博檢索效果。

3.2 基于擴(kuò)展Hashtag的聚類(lèi)語(yǔ)言模型

聚類(lèi)算法是指將一系列文檔聚團(tuán)成多個(gè)子集或簇(cluster)，其目標(biāo)是找出類(lèi)內(nèi)緊密、類(lèi)間分散的多個(gè)簇。常用的聚類(lèi)方法根據(jù)其簇之間是否有關(guān)系分為扁平聚類(lèi)和層次聚類(lèi)兩類(lèi)。K-means算法[13]是扁平聚類(lèi)算法的代表方法，其基本流程為： 當(dāng)指定聚類(lèi)個(gè)數(shù)為K時(shí)，首先從N個(gè)數(shù)據(jù)量中隨機(jī)挑選K個(gè)對(duì)象作為初始的聚類(lèi)中心；然后計(jì)算N個(gè)數(shù)據(jù)量與K個(gè)聚類(lèi)中心的距離，選擇最近的作為該對(duì)象所屬類(lèi)別；接著根據(jù)新類(lèi)別重新得到K個(gè)聚類(lèi)中心；最后判斷是否達(dá)到停止條件，如果沒(méi)有則從第二步開(kāi)始迭代進(jìn)行。當(dāng)被劃分?jǐn)?shù)據(jù)為文本時(shí)，通常采用向量空間模型表示文本，tf*idf作為向量的每一維的權(quán)重，余弦相似度(cosinesimilarity)作為類(lèi)別劃分標(biāo)準(zhǔn)。

在微博數(shù)據(jù)集中，由于微博內(nèi)容短，且經(jīng)過(guò)詞干還原和去除停用詞處理之后，剩余的有效詞個(gè)數(shù)很少，比如在TRECMicroblog數(shù)據(jù)中微博ID為29742094935392256(‘Jordansare’)、31907613243351040(‘JordanHasMe!’)、34773247190892544(‘IwantsomeJordans!’)最終文本都成為了“jordan”。在本文中，我們的目的是找到與微博內(nèi)容相同或相似的結(jié)果，以此提高微博已有詞的權(quán)重并加入未有詞，也就是說(shuō)這些微博之間是有共同詞匯的，因此我們假設(shè)其聚類(lèi)形狀是以某個(gè)詞或某些詞為中心向外延伸的偏圓形，K-means聚類(lèi)是針對(duì)這類(lèi)型數(shù)據(jù)的很好的聚類(lèi)方法。與此同時(shí)，由于微博文本短，所以它的向量維度不會(huì)過(guò)高；而其微博數(shù)量過(guò)大，我們采取減少數(shù)據(jù)集，即只選擇查詢(xún)的搜索結(jié)果中的前10 000篇微博構(gòu)成新的文檔集，降低算法的運(yùn)行時(shí)間。圖2是一個(gè)聚類(lèi)結(jié)果的截圖，從圖中可以清晰的看出，這個(gè)結(jié)果是關(guān)于“Jordan”的微博集合。用該集合的語(yǔ)言模型平滑微博，可以提高“Jordan”的詞概率，同時(shí)加入michael，egypt等詞的概率，豐富了微博的原有信息，達(dá)到了我們最初的目的。也就是說(shuō)當(dāng)?shù)玫骄垲?lèi)結(jié)果之后，帶入式(3)到式(1)中，得到CBLM算法。

在確定了聚類(lèi)算法之后，核心問(wèn)題便是如何融入微博的Hashtag信息。雖然文獻(xiàn)[14]并非是針對(duì)微博排序的研究，但是可以借鑒其把Hashtag信息加入到聚類(lèi)過(guò)程的方式。Ramage,Heymann[14]認(rèn)為現(xiàn)有的很多網(wǎng)頁(yè)擁有用戶(hù)所標(biāo)注的標(biāo)簽，這些標(biāo)簽便是對(duì)這些網(wǎng)頁(yè)的主題的表明。論文中給出了多種融合網(wǎng)頁(yè)原有文本和網(wǎng)頁(yè)標(biāo)簽的方式，經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，原有文本和網(wǎng)頁(yè)標(biāo)簽同時(shí)進(jìn)行向量化的結(jié)合方式取得了較好的聚類(lèi)結(jié)果。相較于微博數(shù)據(jù)，微博的Hashtag便是用戶(hù)給定的特定微博的主題詞，因此本文也采用這種方式進(jìn)行微博文本的向量化，得到的模型稱(chēng)為CBLM+Hashtag。

同時(shí)我們發(fā)現(xiàn)文獻(xiàn)[14]所做實(shí)驗(yàn)的背景是網(wǎng)頁(yè)且都具有標(biāo)簽，而據(jù)統(tǒng)計(jì)可知，在微博數(shù)據(jù)集中，具有Hashtag的微博個(gè)數(shù)僅占13%，并且存在內(nèi)容相同的微博有的有Hashtag，有的沒(méi)有Hashtag。因此我們提出了一種擴(kuò)展微博Hashtag的方法，設(shè)給定微博d，首先將微博d的文本內(nèi)容作為查詢(xún)，在微博數(shù)據(jù)集中搜索前K篇相似文本， 構(gòu)成其相似文檔集合，記為Rset。然后抽取Rset中每篇微博的Hashtag，作為微博d的擴(kuò)展Hashtag。在本文的實(shí)驗(yàn)中，K取值300。使用擴(kuò)展后的微博數(shù)據(jù)集進(jìn)行聚類(lèi)，然后用來(lái)平滑原始微博的語(yǔ)言模型，進(jìn)行微博排序，下文稱(chēng)該算法為CBLM+ExpandHashtag。

圖2 微博數(shù)據(jù)集聚類(lèi)截圖舉例說(shuō)明

3.3 融入時(shí)間的統(tǒng)計(jì)語(yǔ)言模型

通過(guò)第2節(jié)對(duì)前人的工作介紹可知時(shí)間是微博檢索不同于傳統(tǒng)檢索的特征之一，將時(shí)間融入檢索模型的一種代表性工作便是作為文檔先驗(yàn)。衛(wèi)冰潔和王斌[12]在微博數(shù)據(jù)集的背景下，通過(guò)對(duì)微博查詢(xún)的分析，對(duì)文獻(xiàn)[7]和文獻(xiàn)[8]的工作進(jìn)行了擴(kuò)展研究，最終提出了一個(gè)混合時(shí)間文檔先驗(yàn)計(jì)算方法。根據(jù)論文中的基于混合模型的實(shí)驗(yàn)結(jié)果得知，當(dāng)MAP最高時(shí)，P(dt) 選擇的是文獻(xiàn)[7]提出的模型；P(dqt) 選擇的是HTLM系列模型，帶入式(6)中得到最終先驗(yàn)計(jì)算公式為：

(9)

其中涉及的參數(shù)取值分別為α1為0.3，α2為0.3，計(jì)算tqd過(guò)程中涉及的熱門(mén)時(shí)刻閾值參數(shù)取值為0.8，tcollection是數(shù)據(jù)集中的最新時(shí)間，取值為17。

3.4 融入聚類(lèi)和時(shí)間信息的統(tǒng)計(jì)語(yǔ)言模型

在第1節(jié)中介紹了利用Hashtag的聚類(lèi)語(yǔ)言模型，第2節(jié)中介紹了基于時(shí)間先驗(yàn)的語(yǔ)言模型，針對(duì)式(1)，前者修改的是p(w|Md) 的概率，后者修改的是P(d) 的取值，將計(jì)算公式帶入，得到了我們提出的融入聚類(lèi)和時(shí)間信息的最終模型，分別記為CBLM+Time，CBLM+Hashtag+Time，CBLM+ExpandHashtag+Time。最后我們通過(guò)在數(shù)據(jù)集上驗(yàn)證，證明加入時(shí)間之后的模型對(duì)檢索效果有進(jìn)一步的提升。

4 實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)指標(biāo)

本文實(shí)驗(yàn)所用的數(shù)據(jù)集為2011年TRECMicroblogTrack發(fā)布的從2011年1月23日至2011年2月8日共有17天的Twitter數(shù)據(jù)，我們對(duì)數(shù)據(jù)集進(jìn)行了預(yù)處理，包括去除所有的非英文及轉(zhuǎn)發(fā)微博，處理過(guò)后的微博個(gè)數(shù)為9 679 710。然后對(duì)這部分?jǐn)?shù)據(jù)集刪除了微博內(nèi)容的@信息和url信息，提取出微博的Hashtag單獨(dú)存儲(chǔ)，同時(shí)對(duì)于微博文本和Hashtag詞進(jìn)行了詞干還原和分詞處理。所用的查詢(xún)集為T(mén)RECMicroblogTrack于2011和2012年發(fā)布的共110個(gè)查詢(xún)及其標(biāo)注的相關(guān)文檔集合，共有113 926篇微博被標(biāo)注。表1列出的是本文模型涉及的參數(shù)取值。我們將110個(gè)查詢(xún)隨機(jī)分為10份，然后用其中3份用來(lái)訓(xùn)練模型的參數(shù)，最后在整個(gè)數(shù)據(jù)集上進(jìn)行效果驗(yàn)證。

表1 根據(jù)評(píng)價(jià)指標(biāo)選擇的最優(yōu)結(jié)果參數(shù)取值

4.2 評(píng)價(jià)指標(biāo)

本文選用信息檢索研究領(lǐng)域常用的評(píng)價(jià)指標(biāo)P@k和MAP用來(lái)對(duì)我們提出的檢索模型進(jìn)行性能評(píng)估。

P@k(Precision at k)，是指前k個(gè)返回結(jié)果集的正確率，如k可取值5,10等，在本文實(shí)驗(yàn)中，k取值為30。計(jì)算公式如下所示：

(10)

平均正確率(簡(jiǎn)稱(chēng)為AP)是指針對(duì)單個(gè)查詢(xún)而言，計(jì)算返回結(jié)果中在每篇相關(guān)文檔位置上的正確率的平均值[15]。MAP是指針對(duì)查詢(xún)集合的平均正確率的均值。設(shè)查詢(xún)記為qi，針對(duì)查詢(xún)的相關(guān)文檔集合為 {d1,d2…,dmi}， 設(shè)Rik是返回結(jié)果集中遇到dki時(shí)的全部文檔集合，本文的返回結(jié)果集為前1 000篇返回結(jié)果構(gòu)成。則其AP計(jì)算公式為：

(11)

根據(jù)AP的計(jì)算公式，設(shè)查詢(xún)集合為Q，則其平均正確率均值(MAP)的計(jì)算公式為：

(12)

4.3 融合聚類(lèi)和時(shí)間信息的語(yǔ)言模型實(shí)驗(yàn)結(jié)果及分析

根據(jù)第3節(jié)的介紹可知，本文需要進(jìn)行比較的模型共有8個(gè)模型，其中統(tǒng)計(jì)語(yǔ)言模型系列中的查詢(xún)似然模型是本文的基準(zhǔn)模型，記為QL；同時(shí)本文也同基于統(tǒng)計(jì)語(yǔ)言模型使用TREC數(shù)據(jù)的模型ATM進(jìn)行了對(duì)比[16]，ATM模型是基于用戶(hù)信息構(gòu)建的檢索模型，它使用用戶(hù)所發(fā)的微博構(gòu)造用戶(hù)模型，以此達(dá)到擴(kuò)充微博內(nèi)容的目的，與本文使用聚類(lèi)方法克服文本短具有對(duì)比性。表2列出了各個(gè)模型在TRECMicroblog數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，其中含有 “*”號(hào)標(biāo)記的表示該結(jié)果與QL在成對(duì)T側(cè)上(P< 0.05)具有統(tǒng)計(jì)顯著性。

表2 在TREC 2011 Microblog數(shù)據(jù)集上的檢索結(jié)果

觀(guān)察表2可得到，本文提出的模型相比于QL(基準(zhǔn)實(shí)驗(yàn))，在MAP和P@30兩個(gè)指標(biāo)上都有提高，表明了在微博檢索背景下，聚類(lèi)信息和時(shí)間信息對(duì)于排序結(jié)果有提高作用。在上文描述中，可知微博排序和傳統(tǒng)文本排序的區(qū)別在于兩點(diǎn)，第一點(diǎn)是考慮微博特征，我們主要關(guān)注的是微博文本短和具有Hashtag；第二點(diǎn)是在排序原則中考慮時(shí)間性質(zhì)。下面我們也根據(jù)這兩類(lèi)進(jìn)行具體分析。

首先分析考慮微博特征的模型，即融入聚類(lèi)和微博Hashtag。具體來(lái)看，CBLM是加入了聚類(lèi)信息的模型，檢索效果優(yōu)于沒(méi)有加入聚類(lèi)信息的，這是因?yàn)榫垲?lèi)代表與該文檔相似的文檔集合的信息，用這些信息平滑文檔會(huì)同時(shí)加重文檔本身的信息補(bǔ)充文檔未有的信息。接下來(lái)我們運(yùn)用微博的Hashtag特征，我們將微博的Hashtag加入到基于聚類(lèi)的微博排序模型中(CBLM+Hashtag)，效果較之CBLM模型效果更優(yōu)，其原因是因?yàn)槲⒉┑腍ashtag詞是用戶(hù)給出的關(guān)于該篇微博內(nèi)容的主題概括詞，是對(duì)微博內(nèi)容的高度總結(jié)，所以加入Hashtag信息后，是對(duì)微博內(nèi)容的重要補(bǔ)充，由此該模型的檢索結(jié)果更好。但是，微博數(shù)據(jù)集中具有Hashtag的個(gè)數(shù)非常少，僅占整體數(shù)據(jù)集的13%，而Hashtag信息又如此重要，因此我們提出了一個(gè)擴(kuò)展微博Hashtag的方法，得到模型CBLM+ExpandHashtag，經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，MAP和P@30均得到提高。

然后我們關(guān)注加入時(shí)間特征的模型。在我們的模型中，時(shí)間性質(zhì)是通過(guò)定義文本先驗(yàn)的方式加入統(tǒng)計(jì)語(yǔ)言模型的。通過(guò)表2中的數(shù)值可以看出來(lái)，在任何的原始模型上加入時(shí)間之后均比沒(méi)有加入時(shí)間的模型在效果上更好，再一次證明了時(shí)間對(duì)于微博檢索的重要性。加入時(shí)間之后，效果得到提高是因?yàn)槲⒉┎樵?xún)是時(shí)間敏感查詢(xún)，這部分查詢(xún)的相關(guān)文檔在某些時(shí)間段內(nèi)的分布會(huì)高于其他時(shí)間段，因此加入時(shí)間先驗(yàn)后，會(huì)提高重要時(shí)間段內(nèi)微博的分值，由此提高評(píng)價(jià)指標(biāo)的取值，得到更好的排序結(jié)果。

總體來(lái)說(shuō)，針對(duì)于原始的查詢(xún)似然模型，在微博檢索的背景下，考慮微博文本特征和時(shí)間特性的模型取得了最優(yōu)的效果。

5 總結(jié)及未來(lái)工作

近年來(lái)，隨著微博用戶(hù)量和數(shù)據(jù)量的蓬勃發(fā)展，用戶(hù)對(duì)微博檢索的精確度要求越來(lái)越高，微博檢索越來(lái)越重要。新型的數(shù)據(jù)給研究界帶來(lái)了新的挑戰(zhàn)。微博檢索不同于傳統(tǒng)文本檢索的特點(diǎn)表現(xiàn)在兩個(gè)方面： 第一個(gè)是面向的數(shù)據(jù)不同；第二個(gè)是排序原則不同。微博相對(duì)于傳統(tǒng)網(wǎng)頁(yè)，具有文本短的特點(diǎn)，并且微博內(nèi)容中具有用戶(hù)給出的關(guān)于微博的主題詞，稱(chēng)為Hashtag。同時(shí)微博檢索原則中除了考慮查詢(xún)和文本的語(yǔ)義相似度之外，還需要考慮時(shí)間特性。針對(duì)這兩點(diǎn)不同，首先本文提出運(yùn)用Hashtag的聚類(lèi)語(yǔ)言模型，并且由于微博數(shù)據(jù)集中具有Hashtag的微博僅占13%，我們也提出了一種擴(kuò)展微博Hashtag的算法。然后我們?cè)谔岢鼍垲?lèi)的模型基礎(chǔ)上，通過(guò)定義文檔的時(shí)間先驗(yàn)在檢索模型中加入時(shí)間信息，最終得到融合時(shí)間和聚類(lèi)信息的排序新方法。最后我們?cè)赥REC Microblog數(shù)據(jù)集上進(jìn)行性能驗(yàn)證，相對(duì)于基準(zhǔn)模型(查詢(xún)似然模型，簡(jiǎn)稱(chēng)為QL)，分別證明了加入聚類(lèi)信息和加入時(shí)間信息都比基準(zhǔn)模型的效果更優(yōu)，同時(shí)也驗(yàn)證進(jìn)行了微博Hashtag擴(kuò)展之后的融合聚類(lèi)和時(shí)間信息的模型在檢索效果上達(dá)到了最優(yōu)，在MAP和P@30上分別提高了7.1%和11.6%。

本文工作還存在多個(gè)可以繼續(xù)研究的問(wèn)題，包括： 1)時(shí)間信息除了通過(guò)文檔先驗(yàn)方式以外，如何在聚類(lèi)過(guò)程中融入時(shí)間信息？2)每篇微博的Hashtag的個(gè)數(shù)不同，不同的Hashtag個(gè)數(shù)是否會(huì)具有不同的文檔先驗(yàn)，有待進(jìn)行驗(yàn)證。

[1] Liu X, W B Croft. Cluster-based retrieval using language models[C]//Proceedings of the 27th annual international ACM SIGIR conference on research and development in information retrieval, ACM: Sheffield, United Kingdom,2004: 186-193.

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

[3] Rui Li B W, Kai Lu, Bin Wang. Author Model and Negative Feedback Methods on TREC 2011 Microblog Track[C]//Proceedings of the Text Retrieval Conference (TREC),2011.

[4] Donald Metzler C C. USC/ISI at TREC 2011: Microblog Track[C]//Proceedings of the Text Retrieval Conference (TREC),2011.

[5] Feng Liang R Q, Jianwu Yang. PKU_ICST at TREC 2011 Microblog Track[C]//Proceedings of the Text Retrieval Conference (TREC),2011.

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

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

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

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

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

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

[12] 衛(wèi)冰潔,王斌. 面向微博搜索的時(shí)間感知的混合語(yǔ)言模型[C]. 全國(guó)信息檢索學(xué)術(shù)會(huì)議(CCIR),2012.

[13] Berkhin P, A survey of clustering data mining techniques[C]//Proceedings of the Grouping Multidimensional Data: Recent Advances in Clustering. 2006: 25-71.

[14] Ramage D, et al., Clustering the tagged web[C]//Proceedings of the Second ACM International Conference on Web Search and Data Mining, ACM: Barcelona, Spain,2009: 54-63.

[15] 王斌. 信息檢索導(dǎo)論[M]，北京： 人民郵電出版社，2010.

[16] 李銳，王斌. 一種基于作者建模的微博檢索模型[J]. 中文信息學(xué)報(bào), 2014，28(2)： 132-143.

Combining Cluster and Temporal Information for Microblog Search

WEI BingJie1,3, SHI Liang3, WANG Bin2

(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 Technical Team/Coondination Cente of China, Beijing 100029, China)

With the rapid development of microblog, microblog retrieval has become a hot research topic in recent years. In contrast to traditional text retrieval, microblog search significantly differs in two aspects. One is that microblog has its own text features, i.e. short text and Hashtag as the theme term. The other is that microblog search should consider the time information and text and semantic similarity. This paper addresses the above issue by clustering to expand text content. The hashtag is introduced into the clustering, and, to guarantee its effect, a method to enrich the Hashtag in a microblog is described. Finally we used the time information as the document’s prior and altogether three models are examined in the experments. Experiments on TREC Microblog dataset show that our models significantly improved MAP and P@30 with 7.1% and 11.6% increase separately.

microblog search; Hashtag; cluster; temporal; language model

衛(wèi)冰潔(1987—)，博士，工程師，主要研究領(lǐng)域?yàn)槲⒉z索及數(shù)據(jù)挖掘。E?mail：weibingjie1986@163．com史亮(1986—)，博士，工程師，主要研究領(lǐng)域?yàn)樾畔z索和數(shù)據(jù)壓縮。E?mail：shiliang@ict．a(chǎn)c．cn王斌(1972—)，博士，研究員，主要研究領(lǐng)域?yàn)樾畔z索及自然語(yǔ)言處理。E?mail：wangbin@iie．a(chǎn)c．cn

1003-0077(2015)03-0177-07

2012-12-28 定稿日期： 2013-03-12

科技支撐計(jì)劃(2012BAH46B02)。

TP391

A