薛 冉，馬 軍，韓曉暉，陳竹敏

（山東大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南250101）

1 引言

數(shù)碼技術(shù)的飛速發(fā)展推動(dòng)了照片由模擬到數(shù)字化的過(guò)程。借助于社交媒體（Social Media），網(wǎng)絡(luò)用戶可以將個(gè)人拍攝的數(shù)字相片以公開(kāi)的形式上傳到圖像社區(qū)網(wǎng)站（如Flickr，Picasa，Webshots等）上，使得這類網(wǎng)站上積累了海量的圖像數(shù)據(jù)。對(duì)這些海量圖像數(shù)據(jù)的管理、解釋和分析已經(jīng)成為當(dāng)前信息檢索和數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一［1－3］。在圖像社區(qū)網(wǎng)站中，很大比重的用戶上傳數(shù)據(jù)與現(xiàn)實(shí)中的各類事件相關(guān)（即，圖片拍攝于特定事件發(fā)生時(shí)）。這些事件既包括流行的全局性事件，如世界杯足球賽、奧林匹克運(yùn)動(dòng)會(huì)等，也包括小范圍的局部性事件，如私人聚會(huì)、婚禮等?；谶@一特點(diǎn)，本文將研究在圖像社區(qū)網(wǎng)站的海量數(shù)據(jù)上進(jìn)行熱點(diǎn)事件檢測(cè)的方法。所謂熱點(diǎn)事件，指在一定事件段內(nèi)被廣泛關(guān)注的事件，在圖像社區(qū)網(wǎng)站中體現(xiàn)為用戶上傳的與之相關(guān)的數(shù)據(jù)較多的事件。本文的研究意義在于：一方面，以事件為單位對(duì)數(shù)據(jù)進(jìn)行組織，并根據(jù)熱度對(duì)事件排序，將很大程度上方便用戶對(duì)圖像數(shù)據(jù)的瀏覽和檢索；另一方面，本文的工作有助于基于Web上的信息來(lái)研究和分析現(xiàn)實(shí)事件的變化發(fā)展，在輿情分析中將會(huì)產(chǎn)生重要的作用。

事件檢測(cè)最初為話題檢測(cè)與追蹤（Topic Detection and Tracking，TDT）的子任務(wù)之一。在TDT中，事件定義為發(fā)生在特定時(shí)間范圍和地點(diǎn)的某件事。傳統(tǒng)的TDT研究目的是在連續(xù)的新聞文檔流中識(shí)別新聞事件［4－5］，其研究對(duì)象是文本文檔。這類研究對(duì)于圖像社區(qū)中的數(shù)據(jù)并不有效，這是由于圖像社區(qū)中的數(shù)據(jù)與文本文檔相比有著明顯的差別和新特性：首先，并不是每一張圖片都與事件相關(guān)聯(lián)。其次，圖像社區(qū)網(wǎng)站通常提供標(biāo)注服務(wù)，用戶可以為圖片提供文本信息，如標(biāo)簽（Tag）、標(biāo)題（Title）和描述（Description）。研究證明，由于有大量的用戶參與，這些文本標(biāo)注有一定的一致性和可信性［6］。但這些文本遠(yuǎn)稀疏于新聞文檔中的文本，并且存在噪聲。第三，很多圖像數(shù)據(jù)還包含拍攝時(shí)間、地理位置等元數(shù)據(jù)。根據(jù)事件的定義，合理地利用這些信息將有利于提高事件檢測(cè)的效果。近期，已有文獻(xiàn)專注于Flickr數(shù)據(jù)上的事件檢測(cè)研究［7－10］，但是這些研究大都只利用了與圖像相關(guān)的文本數(shù)據(jù)而沒(méi)有考慮圖像本身的內(nèi)容，并且局限于回顧式的事件檢測(cè)，即在歷史數(shù)據(jù)上檢測(cè)事件。而事件的發(fā)生和發(fā)展是隨時(shí)間變化的，需要實(shí)時(shí)、在線的檢測(cè)方法。

針對(duì)上述問(wèn)題，本文提出了一種基于衰退理論的熱點(diǎn)事件檢測(cè)方法，以Flickr數(shù)據(jù)為檢測(cè)對(duì)象。該方法首先從Flickr圖像中提取視覺(jué)詞匯并與圖像的文本信息結(jié)合構(gòu)成文檔，使用LDA模型將文檔映射到主題空間形成文檔的向量表示。使用改進(jìn)的Single－Pass算法進(jìn)行事件檢測(cè)，該算法在事件檢測(cè)過(guò)程中考慮了文檔的地理位置信息。在事件檢測(cè)過(guò)程之后，進(jìn)一步檢測(cè)出當(dāng)前時(shí)間段的熱點(diǎn)事件。熱點(diǎn)事件是一個(gè)與時(shí)間相關(guān)的概念，隨時(shí)間的變化而不斷改變。因此本文基于衰退理論（Aging Theory）對(duì)檢測(cè)到的事件進(jìn)行生命周期建模，計(jì)算事件在每個(gè)時(shí)間段的能量值，能量值反映事件的熱度。最后，根據(jù)能量值進(jìn)行事件排序，獲得給定時(shí)間段內(nèi)的熱點(diǎn)事件。

區(qū)別于以往的工作，本文的貢獻(xiàn)在于：

1）在數(shù)據(jù)表示時(shí)同時(shí)考慮了圖像本身的信息和與圖像相關(guān)的文本信息，利用LDA模型將二者融合；

2）在事件檢測(cè)中通過(guò)使用衰退理論和地理位置信息使得事件檢測(cè)算法同時(shí)在時(shí)間和空間維度進(jìn)行；

3）所提出的方法是一種實(shí)時(shí)的在線方法，將Flickr數(shù)據(jù)看作數(shù)據(jù)流，事件檢測(cè)的輸出隨時(shí)間而變化；

4）將事件按熱度排序，能使用戶優(yōu)先關(guān)注最為重要的信息，更加利于用戶瀏覽。

本文余下部分的組織結(jié)構(gòu)如下：第2節(jié)介紹與本文相關(guān)的研究工作；第3節(jié)講述Flickr數(shù)據(jù)的表示方法；基于衰退理論的事件檢測(cè)方法在第4節(jié)給出；第5節(jié)給出實(shí)驗(yàn)，分析了新方法的性能和效果；第6節(jié)總結(jié)全文并展望未來(lái)的工作。

2 相關(guān)工作

在TDT領(lǐng)域，熱點(diǎn)事件檢測(cè)研究已經(jīng)取得了很大程度的進(jìn)展。很多學(xué)者在事件發(fā)現(xiàn)過(guò)程中考慮到了特征詞和事件在時(shí)間上的突發(fā)性。文獻(xiàn)［11］認(rèn)為同一個(gè)查詢?cè)~可能與若干事件相關(guān)聯(lián)，每一個(gè)事件又可以被劃分成更小的事件。首先根據(jù)時(shí)間和文檔的內(nèi)容識(shí)別突發(fā)特征詞，然后基于時(shí)間提取與突發(fā)特征緊密相關(guān)的文檔，最后將這些文檔歸到事件，并以層次結(jié)構(gòu)組織。文獻(xiàn)［12］以主題句子表示事件，給定一個(gè)文集和查詢q，首先得到與q相關(guān)的句子集合，并確定這些句子的時(shí)間，將句子按照時(shí)間排序，計(jì)算句子的興趣度，最后得到表示事件的主題句子；文獻(xiàn)［13］將事件和特征分為：周期性和非周期性的，重要的和極少報(bào)道的。認(rèn)為事件由具有代表性的特征描述，同一事件的特征在時(shí)間上的分布相近。將特征在時(shí)間上的變化表示成向量，進(jìn)而對(duì)特征進(jìn)行分類。用分布相近的特征詞還原事件；文獻(xiàn)［14］提出了幾個(gè)新的突發(fā)向量空間模型（B－VSM）。突發(fā)向量模型考慮了文檔中候選詞在文檔發(fā)表時(shí)的突發(fā)性。一個(gè)突發(fā)的主題可以被一個(gè)突發(fā)的詞集合表示，將單個(gè)詞的突發(fā)性結(jié)合入向量表示模型，在每一時(shí)刻，對(duì)于突發(fā)詞的權(quán)重加一個(gè)突發(fā)值，可以加強(qiáng)相似突發(fā)主題的內(nèi)聚性，從而可以提高事件檢測(cè)的質(zhì)量。另有研究從仿生學(xué)角度進(jìn)行熱點(diǎn)話題發(fā)現(xiàn)，文獻(xiàn)［15］提出了事件的衰退理論，將話題的發(fā)展過(guò)程看作是一個(gè)由誕生、發(fā)展、衰退并最終消亡的過(guò)程。文獻(xiàn)［16］利用了衰退理論和TF－PDF模型，通過(guò)時(shí)間線分析和多維句子建模來(lái)識(shí)別熱點(diǎn)話題。文獻(xiàn)［17］指出用戶對(duì)于話題的關(guān)心程度也是話題熱度的一種反映，因此從衰退理論媒體報(bào)道的角度和用戶關(guān)注的角度分別模擬話題的生命狀態(tài)，將二者結(jié)合來(lái)找到熱點(diǎn)話題。

上述研究均將新聞文檔作為處理對(duì)象。近期，一些研究利用社會(huì)媒體網(wǎng)站中的數(shù)據(jù)進(jìn)行事件檢測(cè)。其中，部分研究在Flickr數(shù)據(jù)上進(jìn)行。文獻(xiàn)［7］利用Flickr用戶提供的標(biāo)記、標(biāo)題和描述信息，提出一種新的圖片分類方法，將圖片按照事件進(jìn)行分類。文獻(xiàn)［8］利用Flickr中存在的文本信息，挖掘不同類型文本特征的表示形式來(lái)學(xué)習(xí)特征之間的相似度矩陣，以此進(jìn)行事件檢測(cè)。文獻(xiàn)［9］提出了一種基于小波分析的算法對(duì)Flickr上的事件進(jìn)行檢測(cè)。該方法將圖像的元數(shù)據(jù)（時(shí)間、地理位置）映射到三維空間，通過(guò)小波分析來(lái)獲得標(biāo)簽的使用分布規(guī)律，以此進(jìn)行標(biāo)記聚類來(lái)發(fā)現(xiàn)事件。文獻(xiàn)［10］通過(guò)分析Flickr中圖像數(shù)量的變化來(lái)預(yù)測(cè)事件發(fā)展的趨勢(shì)。然而，上述方法局限于僅僅利用了與圖像相關(guān)的文本信息，而忽略了圖像本身的內(nèi)容。此外，文獻(xiàn)［9］的方法屬于回顧型的事件檢測(cè)方法，并不具有實(shí)時(shí)性。

3 融合視覺(jué)和文本信息的數(shù)據(jù)表示

本節(jié)介紹如何對(duì)Flickr中的數(shù)據(jù)進(jìn)行表示。本文將一幅圖像及與其相關(guān)的文本信息（標(biāo)記、標(biāo)題和描述）視為一篇完整的文檔，該文檔由視覺(jué)詞匯和文本詞匯構(gòu)成。視覺(jué)詞匯通過(guò)對(duì)從圖像中提取的SIFT描述子進(jìn)行聚類得到。借助LDA模型將文檔內(nèi)容映射到主題空間，每一篇文檔用其主題分布向量表示，作為事件檢測(cè)算法的輸入。

3.1 LDA基本理論

LDA（Latent Dirichlet Allocation）模型［18］假設(shè)文本集合中的每個(gè)文檔是多個(gè)隱含主題z∈［1，K］的混合，每個(gè)隱含主題是分布在詞匯表上的多項(xiàng)式分布（Multinomial Distribution），可由一組出現(xiàn)概率最高的詞匯來(lái)描述。LDA的圖模型表示如圖1所示，可觀察到的數(shù)據(jù)是每個(gè)文檔中的詞，隱含變量表示了潛在的主題結(jié)構(gòu)。文檔和詞之間沒(méi)有直接的聯(lián)系，而是通過(guò)隱含變量z鏈接。

圖1 LDA圖模型

LDA模型假設(shè)文檔中詞匯的生成過(guò)程如下：

1）從參數(shù)為α的Dirichlet先驗(yàn)分布Dir（α）中為每個(gè)文檔m∈［1，M］抽取多項(xiàng)式分布θm，共抽取M個(gè)；

2）從參數(shù)為β的Dirichlet先驗(yàn)分布Dir（β）中為每個(gè)主題k∈［1，K］抽取多項(xiàng)式分布φk，共抽取K個(gè)；

3）對(duì)于文檔m中的第n個(gè)詞：

（a）根據(jù)多項(xiàng)式分布θm確定一個(gè)主題zm，n＝k。

（b）根據(jù)多項(xiàng)式分布φk產(chǎn)生一個(gè)詞wm，n。

其中M為文檔集合中文檔的數(shù)量，K為隱含主題的數(shù)量，α、β為已知參數(shù)，θm和φk為需要估計(jì)的變量。θm為一個(gè)K 維的向量，表示文檔m在主題上的后驗(yàn)概率分布，其第k維θ（k）m表示P（z＝k｜dm）；令V為詞匯表中詞匯的數(shù)量，φk為一個(gè)V 維的向量，表示主題在詞匯上的后驗(yàn)概率分布，其第i維φk（i）表示P（wi｜z＝k）。

直接使用EM算法通過(guò)最大化整個(gè)數(shù)據(jù)集合的似然度來(lái)估計(jì)θ和φ是比較困難的，本文采用了Gibbs采樣法［19］來(lái)近似地估計(jì)參數(shù)。Gibbs采樣是馬爾可夫鏈－蒙特卡羅方法的簡(jiǎn)單實(shí)現(xiàn)形式，目的是構(gòu)造收斂于目標(biāo)概率分布的Markov鏈，從鏈中抽取被認(rèn)為接近該概率分布值的樣本。對(duì)于文檔dm中給定的觀察詞wi，通過(guò)固定dm中其他詞的主題分配（z－i），來(lái)計(jì)算wi被分配各種主題的后驗(yàn)概率P（zi＝j(luò)｜z－i，wi，α，β），計(jì)算公式如下：

其中，wi不僅代表詞匯w，而且與該詞在的文本中的位置相關(guān)，因此稱其為詞匯記號(hào)；zi＝j(luò)表示將詞匯記號(hào)wi分配給主題j，z－i表示所有wk（k≠i）的分配。是與wi相同的詞匯被分配給主題j個(gè)數(shù)是分配給主題j 的所有詞匯 的個(gè)數(shù)是文檔dm中被分配給主題j的詞匯個(gè)數(shù)是dm中所有被分配了主題的詞匯個(gè)數(shù)；所有的詞匯個(gè)數(shù)均不包括當(dāng)前zi＝j(luò)的分配。

采樣過(guò)程首先為每個(gè)詞匯指派［1，K］之間的一個(gè)隨機(jī)主題，構(gòu)成初始的Markov鏈，然后每次迭代根據(jù)式（1）為詞匯重新分配主題，得到Markov鏈的下一個(gè)狀態(tài)；迭代足夠的次數(shù)后，Markov鏈達(dá)到穩(wěn)定狀態(tài)，取zi的當(dāng)前值作為樣本記錄下來(lái)。以w表示詞匯表中一個(gè)唯一性詞，θ和φ 的值由式（2）估計(jì)：

3.2 數(shù)據(jù)的向量表示

一篇Flickr文檔由一幅圖像以及用戶標(biāo)注的文本信息組成。首先使用BOW模型（Bag of Words）建立對(duì)文檔的描述。BOW模型最初應(yīng)用于文本處理領(lǐng)域，目前已廣泛應(yīng)用在場(chǎng)景分類等計(jì)算機(jī)視覺(jué)領(lǐng)域［20］。在BOW 模型中，文檔被看作是裝滿了詞語(yǔ)的袋子，忽略詞語(yǔ)間的順序和句法，每個(gè)詞的出現(xiàn)都獨(dú)立于其他詞的出現(xiàn)。因此，一篇Flickr文檔可以看作為一個(gè)集合D＝｛VW，TW｝，其中VW為視覺(jué)詞語(yǔ)（Visual Words）的集合，TW為文本詞語(yǔ)的集合。

視覺(jué)詞語(yǔ)通過(guò)從圖像中提取SIFT（Scale Invariant Feature Transform）特征［21］描述并聚類獲得，具體過(guò)程如下：

1）對(duì)每幅圖像使用DoG（Difference－of－Gaussians）點(diǎn)檢測(cè)器在不同的尺度和位置進(jìn)行采樣，將檢測(cè)到的極值區(qū)域表示為SIFT描述子，每一個(gè)SIFT描述子為128維的特征向量。

2）設(shè)定視覺(jué)詞典的大小Vvisual，使用K－Means算法對(duì)所有描述子進(jìn)行Vvisual個(gè)簇的聚類，當(dāng)KMeans收斂時(shí)，可以得到了每一個(gè)簇最后的質(zhì)心，則這Vvisual個(gè)質(zhì)心即為視覺(jué)詞典中的詞，每個(gè)視覺(jué)詞語(yǔ)描述圖像的一個(gè)局部模式，詞典構(gòu)建完畢。

3）將圖像中的每個(gè)SIFT描述子映射到與其距離最近的視覺(jué)詞語(yǔ)，這樣每幅圖像都可以視為由一系列的視覺(jué)詞語(yǔ)構(gòu)成。

文本詞匯由與圖像關(guān)聯(lián)的文本信息獲得。這樣每幅圖像又可以表示成一個(gè)由視覺(jué)詞語(yǔ)和文本詞語(yǔ)的頻數(shù)組成的維數(shù)固定的初始向量dori。

其中，Nvi表示視覺(jué)詞匯vi在文檔中出現(xiàn)的次數(shù)，Ntj表示文本詞匯tj在文檔中出現(xiàn)次數(shù)，n為文本詞典中詞匯的個(gè)數(shù)。觀察發(fā)現(xiàn)，在一片F(xiàn)lickr文檔中，文本詞匯通常比較稀疏。雖然部分描述數(shù)據(jù)的詞匯量比較豐富，但有相當(dāng)一部分的文檔沒(méi)有描述部分。為平衡圖像信息和文本信息在事件檢測(cè)算法中的作用，這里通過(guò)對(duì)文本特征加權(quán)的方式來(lái)加強(qiáng)文本信息的影響力。對(duì)每一個(gè)文本詞匯在文檔中的出現(xiàn)次數(shù)Ntj賦予相同的權(quán)重ω，使得Ntj的值為原來(lái)的ω倍，則文檔的加權(quán)向量表示為：

這種簡(jiǎn)單的向量表示并不能很好地將兩類信息融合，本文使用LDA模型將一篇Flickr文檔中的內(nèi)容映射到主題空間來(lái)實(shí)現(xiàn)兩類信息更好的融合。過(guò)程以Flickr文檔集合的加權(quán)向量表示作為輸入，對(duì)LDA模型進(jìn)行估計(jì)。過(guò)程完成后，可以得到參數(shù)θ和φ的估計(jì)值。以每一篇文檔dm的主題分布θm作為該文檔的最終向量表示，即

該向量為熱點(diǎn)事件檢測(cè)算法的輸入數(shù)據(jù)形式，整個(gè)數(shù)據(jù)表示處理過(guò)程如圖2（見(jiàn)下頁(yè)）所示。

一個(gè)事件e為一個(gè)Flickr文檔的集合，使用e的質(zhì)心向量作為其向量表示，即：

其中向量dm表示屬于事件e的一篇文檔，Ne為屬于事件e的Flickr文檔的數(shù)量。

4 基于衰退理論的熱點(diǎn)事件檢測(cè)

本節(jié)介紹所提出的基于衰退理論的熱點(diǎn)事件檢測(cè)算法。算法是對(duì)Single－Pass聚類算法的改進(jìn)，在事件檢測(cè)過(guò)程中將地理位置信息作為判斷條件之一；同時(shí)，結(jié)合衰退理論為已檢測(cè)到的事件進(jìn)行生命周期建模，計(jì)算事件的能量值，并將能量值作為事件熱度的評(píng)價(jià)標(biāo)準(zhǔn)。基于上述兩點(diǎn)改進(jìn)，使得算法同時(shí)考慮了空間和時(shí)間維度的信息，從而能夠提高事件檢測(cè)的效果。

圖2 數(shù)據(jù)表示處理過(guò)程

4.1 衰退理論

衰退理論［15］將事件看作為一個(gè)生命體，經(jīng)歷著產(chǎn)生、成長(zhǎng)、衰退和消亡的過(guò)程。當(dāng)與事件相關(guān)的第一篇文檔出現(xiàn)時(shí)，事件產(chǎn)生。相關(guān)文檔可以視為事件生命體的“食物”，隨著這些文檔不斷地出現(xiàn)，事件生命體從這些食物中汲取“營(yíng)養(yǎng)”，伴隨著自身能量值的改變。能量值可以反映事件所處的生命階段（即，事件的熱度），高能量值表明事件處于熱門時(shí)期，低的能量值表明事件處于衰減階段。事件在通過(guò)汲取“營(yíng)養(yǎng)”增強(qiáng)能量值的同時(shí)，也會(huì)有固定值的能量自然衰減。當(dāng)相關(guān)文檔越來(lái)越少出現(xiàn)時(shí)，能量的衰減大于新獲取的能量，事件生命體處于衰退階段。當(dāng)相關(guān)文檔不再出現(xiàn)時(shí)，事件生命體走向消亡。

具體的，首先將時(shí)間線劃分為長(zhǎng)度為s（本文試驗(yàn)中，s為1天）的時(shí)間段（time slot），對(duì)于每個(gè)時(shí)間段，定義以下三個(gè)函數(shù)來(lái)計(jì)算和更新事件的能量值：

1）getNutrition（）：計(jì)算事件從一個(gè)相關(guān)文檔中獲得的營(yíng)養(yǎng)值。

2）energyFunction（）：能量函數(shù)，用于將積累的支持值轉(zhuǎn)變成能量值。該函數(shù)必須滿足三個(gè)條件約束：

（a）0≤energyFunction（x）≤1

（b）energyFunction（x）是x的一個(gè)單調(diào)遞增函數(shù)；

（c）energyFunction（∞）＝1，energyFunction（0）＝0；

能量函數(shù)將范圍無(wú)限的營(yíng)養(yǎng)值積累轉(zhuǎn)換到一個(gè)有限的能量值范圍內(nèi)［0，1］，目的是能夠更好地解釋話題所處的狀態(tài)。其反函數(shù)energyFunction－1（）將能量值轉(zhuǎn)換為營(yíng)養(yǎng)值。本文使用Sigmod函數(shù)作為能量函數(shù)：

3）eneryDecay（）：計(jì)算了在每個(gè)時(shí)間段內(nèi)話題能量的衰減。

在每一個(gè)時(shí)間段i，每一個(gè)已知事件的能量按照以下步驟進(jìn)行更新：

1）將i－1時(shí)間段的能量值轉(zhuǎn)換為營(yíng)養(yǎng)值：Nutritioni－1＝energyFunction－1（Energyi－1）；

2）將i時(shí)間段獲得的營(yíng)養(yǎng)值累加到i－1時(shí)間段的營(yíng)養(yǎng)值中：Nutritioni＝Nutritioni－1＋Nutritioni；

3）將i時(shí)間段Energyi＝energyFunction（Nutritioni）。

4.2 熱點(diǎn)事件檢測(cè)算法

根據(jù)事件的定義，與同一事件相關(guān)的Flickr文檔應(yīng)在地理位置信息上有一定的相似性，并且在時(shí)間上應(yīng)當(dāng)有相近性和連續(xù)性。本文改進(jìn)了傳統(tǒng)TDT研究中使用最多的Single－Pass算法，在事件檢測(cè)中利用了Flickr文檔中所包含的GPS地理位置信息和拍攝時(shí)間信息，以確保所檢測(cè)出的事件中的文檔都滿足上述兩個(gè)約束。此外，在算法中嵌入衰退理論的思想，可以通過(guò)計(jì)算能量值獲得給定時(shí)間段的熱點(diǎn)事件。詳細(xì)的熱點(diǎn)事件檢測(cè)過(guò)程如算法1所示。

算法1為一種實(shí)時(shí)在線的方法，將Flickr數(shù)據(jù)看作是隨時(shí)間推移而源源不斷有新文檔到達(dá)的文檔流。對(duì)時(shí)間段i到達(dá)的每一篇文檔d，算法1首先獲得d的地理信息，并將其地理位置信息與所有已檢測(cè)到事件ej的地理位置范圍進(jìn)行比較，如果二者差異小于一個(gè)閾值δ，則將ej加入候選事件集合Ecandi（算法6～11行）。如果Ecandi不為空，則在Ecandi中找到與d最相似的事件e。如果d與e之間的相似度大于一個(gè)閾值thresholddetect，則將文檔歸入事件e。更新e的向量，并按照4.1節(jié)所述方法更新e的能量值（算法15～19行）。其中，d對(duì)事件e的營(yíng)養(yǎng)值貢獻(xiàn)由其與e的相似度sim（e，d）確定；γ為轉(zhuǎn)換因子，指明新獲得的營(yíng)養(yǎng)中有多少被事件e所吸收。同時(shí)，更新e的地理位置范圍（算法21～25行）。如果相似度小于閾值thresholddetect或者Ecandi為空，則創(chuàng)建一個(gè)新的事件，將d加入新創(chuàng)建的事件（算法26～35行）。在每一個(gè)時(shí)間段內(nèi)事件的能量值減少固定的量λ（算法41行），λ稱為衰減因子。當(dāng)沒(méi)有或者只有少量圖片加入到事件中時(shí)，當(dāng)能量值為0時(shí)，事件就被認(rèn)為“消亡”并且從事件集合E中移除（算法39～47行），以此來(lái)確保相同事件中的文檔在時(shí)間上的相近性和連續(xù)性。

在每一時(shí)間段，算法在執(zhí)行完上述過(guò)程后都對(duì)當(dāng)前事件集合E中的事件根據(jù)熱度進(jìn)行排序（算法48行），然后將熱度最高的Top N個(gè)事件作為熱點(diǎn)事件輸出（算法49行）。

4.3 相似度計(jì)算

一篇Flickr文檔對(duì)于一個(gè)事件的營(yíng)養(yǎng)值貢獻(xiàn)由二者之間的相似度確定。本文利用KL散度來(lái)計(jì)算Flickr文檔與事件之間的相似度。對(duì)于Flickr文檔di和事件ej，它們的向量表示分別為θi和θj，則它們之間的相似度按照式（8）計(jì)算。

4.4 結(jié)果事件表示

為了能夠以直觀的形式展示事件檢測(cè)的結(jié)果，對(duì)于一個(gè)已檢測(cè)到的事件ei，使用四元組＜CP（ei），TT（ei），LR（ei），TR（ei）＞來(lái)對(duì)其進(jìn)行表示，其中：

1）CP（ei）（Central Photo）：與事件ei相關(guān)的Flickr文檔中距離ei的質(zhì)心最近（使用KL散度計(jì)算）的文檔中的圖像，形式化表示如式（7）所示，其中Ci是ei的質(zhì)心，為一個(gè)k維的向量。

2）TT（ei）（Top Tags）：在事件i所包含的文檔中TF－IDF值最高的N個(gè)詞的集合。

3）LR（ei）（Location Region）：事件的地理分布范 圍，即 LR（ei）＝ ｛［Minlo（ei），Maxlo（ei）］，［Minla（ei），Maxla（ei）］｝

4）TR（ei）（Time Region）：事件所經(jīng)歷的時(shí)間范圍，即TR（ei）＝［Mintime（ei），Maxtime（ei）］。

5 實(shí)驗(yàn)分析

5.1 數(shù)據(jù)集建立

由于Flickr中的圖片數(shù)量十分巨大，本文只收集了“體育”領(lǐng)域的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)集。我們以“sport”、“football”、“soccer”、“basketball”、“tennis”、“baseball”等體育常用詞匯作為查詢?cè)~，通過(guò)使用Flickr提供的API獲取了2010年6月1日～2011年3月31日之間帶有GPS信息的圖片。對(duì)于每幅圖片，除獲取圖片本身外，同時(shí)還獲取了與之相關(guān)的文本信息，包括Tags，Title和Description。所獲取的數(shù)據(jù)集共有130 897幅圖片，其詳細(xì)的統(tǒng)計(jì)信息如表1所示。

表1 數(shù)據(jù)集的統(tǒng)計(jì)信息

數(shù)據(jù)集由志愿者人工進(jìn)行事件標(biāo)注，標(biāo)注結(jié)果中共包含了325個(gè)區(qū)分度較為明顯的事件，另外有一部分圖片并不適于分派給任何事件。這些事件中相關(guān)文檔最多的事件包含4 802篇Flickr文檔，最少的包含59篇Flickr文檔；時(shí)間跨度最長(zhǎng)的事件持續(xù)217天，最短持續(xù)1天。之后數(shù)據(jù)集被分為訓(xùn)練集和測(cè)試集兩個(gè)部分。其中，訓(xùn)練集由2010年6月～2010年10月的數(shù)據(jù)組成，共包含191個(gè)事件。測(cè)試集由2011年10月～2011年3月的數(shù)據(jù)組成，共包含134個(gè)事件。訓(xùn)練集的主要作用如下：

1）提取視覺(jué)詞匯。即使用訓(xùn)練集的數(shù)據(jù)建立圖像的視覺(jué)詞典。

2）訓(xùn)練LDA模型。使用訓(xùn)練集的數(shù)據(jù)對(duì)LDA模型進(jìn)行參數(shù)估計(jì)，在獲得參數(shù)θ和φ之后，對(duì)于測(cè)試集中的數(shù)據(jù)Gibbs采樣的次數(shù)可以遠(yuǎn)低于參數(shù)估計(jì)時(shí)的采樣次數(shù)，一般20～30次迭代就足夠。因此，可以保證算法的實(shí)時(shí)性。

3）訓(xùn)練衰退模型的參數(shù)。即算法1中的γ和λ的值，采用文獻(xiàn)［15］中給出的方法解得。

5.2 實(shí)驗(yàn)建立

實(shí)驗(yàn)共分為三個(gè)步驟。第一步為數(shù)據(jù)表示和參數(shù)估計(jì)。首先使用訓(xùn)練集建立視覺(jué)詞典，視覺(jué)詞典的大小設(shè)為200。然后，建立LDA模型用來(lái)進(jìn)行圖像信息和文本信息的融合。LDA的超參數(shù)取經(jīng)驗(yàn)值α＝0.5，β＝0.1，Gibbs采樣次數(shù)設(shè)為1 000次，主題的數(shù)目K＝30。最后，使用訓(xùn)練集中的兩個(gè)事件來(lái)獲得熱點(diǎn)事件監(jiān)測(cè)算法中γ和λ的值，過(guò)程重復(fù)10次，取10次結(jié)果的平均值。

實(shí)驗(yàn)的第二步使用測(cè)試集驗(yàn)證事件檢測(cè)算法的有效性。首先，測(cè)試在算法中加入地理位置信息和衰退理論是否能夠提高事件檢測(cè)的效果。參與比較的方法有原始Single－Pass算法（標(biāo)記為SP），加入地理位置信息的算法（標(biāo)記為SP＋G），加入衰退理論的算法（標(biāo)記為SP＋A）以及本文提出的算法1（標(biāo)記為SP＋G＋A）。然后，測(cè)試融合圖像信息和文本信息的數(shù)據(jù)表示是否對(duì)事件檢測(cè)算法有效，我們采用不同方法對(duì)數(shù)據(jù)進(jìn)行表示，參與比較的方法有僅使用視覺(jué)詞匯的TF－IDF向量表示（標(biāo)記為VV），僅使用文本信息的TF－IDF向量表示（標(biāo)記為TV），同時(shí)使用圖像和文本詞匯的TF－IDF向量表示（標(biāo)記為VTV）和基于LDA的表示方法（標(biāo)記為L(zhǎng)DA）。

使用平均精確率（Precision）、召回率（Recall）和F1值作為事件檢測(cè)結(jié)果的評(píng)價(jià)測(cè)度。然而，由算法得到的事件數(shù)量與人工標(biāo)注的事件數(shù)量可能不相等，當(dāng)結(jié)果的事件數(shù)目小于人工標(biāo)注的事件數(shù)目時(shí)，對(duì)于結(jié)果中的每一個(gè)事件在人工標(biāo)注的事件中找到與該事件包含相同文檔的數(shù)量最多的一個(gè)，作為其真值事件參與評(píng)測(cè)；當(dāng)結(jié)果事件的數(shù)目大于人工標(biāo)注的事件數(shù)目時(shí)，對(duì)于每個(gè)人工標(biāo)注的事件在結(jié)果事件中找到與其包含相同文檔數(shù)量最多的事件，作為對(duì)應(yīng)的檢測(cè)結(jié)果參與評(píng)測(cè)。設(shè)有C個(gè)簇（事件）參與評(píng)測(cè)，令TPi表示分到事件i（i≤C）且結(jié)果正確的文檔數(shù)目，F(xiàn)Pi表示分到事件i但結(jié)果錯(cuò)誤的文檔數(shù)目，F(xiàn)Ni為屬于事件i但沒(méi)有被分到事件i的文檔數(shù)目，則：

準(zhǔn)確率越高，算法在該事件上的錯(cuò)誤率越小；查全率越高，則漏掉的相關(guān)文檔越少；F1值將兩者賦予同樣的重要性來(lái)綜合評(píng)價(jià)。實(shí)驗(yàn)取所有測(cè)試事件的結(jié)果平均值作為最終結(jié)果。

實(shí)驗(yàn)的第三步，通過(guò)算法在數(shù)據(jù)集上的運(yùn)行結(jié)果，驗(yàn)證使用衰退理論為事件建立生命周期模型對(duì)于熱點(diǎn)事件檢測(cè)的有效性。

5.3 結(jié)果分析

實(shí)驗(yàn)在一臺(tái)12核雙CPU，12GB內(nèi)存的服務(wù)器上完成。通過(guò)訓(xùn)練集得到的參數(shù)值分別為γ＝0.479 31，λ＝0.287 45。此外，通過(guò)多次實(shí)驗(yàn)發(fā)現(xiàn)參數(shù)ω＝2，thresholddetect＝0.231，δ＝8.0時(shí)得到的結(jié)果較好。

圖3 地理信息和衰退理論對(duì)結(jié)果的影響比較

圖3展示了是否加入地理位置信息和衰退理論對(duì)事件檢測(cè)結(jié)果的影響?？梢钥闯觯谒袦y(cè)度上，加入地理位置信息或衰退理論，得到的結(jié)果都優(yōu)于僅使用Single－Pass算法。而本文提出的熱點(diǎn)事件檢測(cè)算法取得了最優(yōu)的效果。單獨(dú)使用Sing－Pass算法在三個(gè)測(cè)度上的值都非常低，這是由于與同一類事件相關(guān)文檔在視覺(jué)和文本信息上都有很大的相似性，如與足球相關(guān)的Flickr文檔的圖像中大部分都會(huì)出現(xiàn)綠色草坪，文本中會(huì)出現(xiàn)“coach”、“Field”等詞，導(dǎo)致難以很好的區(qū)分事件。單獨(dú)加入地理位置信息，對(duì)結(jié)果有一定的提升。與SP＋A相比，SP＋G的精確率較低，這是因?yàn)橛捎跊](méi)有時(shí)間條件，SP＋G會(huì)將相隔時(shí)間很長(zhǎng)，但在內(nèi)容和地理位置上都相似的文檔歸為同一事件。而SP＋A的召回率略低，經(jīng)分析發(fā)現(xiàn)這是由于該方法容易漏掉一些屬于某事件，但在視覺(jué)上與該事件內(nèi)大部分文檔相似性較低的文檔。而本文提出的方法（SP＋G＋A）通過(guò)空間維度和時(shí)間維度的結(jié)合，精確率和召回率均優(yōu)于二者。

圖4 不同數(shù)據(jù)表示對(duì)事件檢測(cè)結(jié)果的影響

圖4展示了不同數(shù)據(jù)表示方式對(duì)于事件檢測(cè)結(jié)果的影響。可以看出，單獨(dú)使用視覺(jué)詞匯表示文檔的效果最差，原因如前面所述，這是由于與同一類事件相關(guān)的文檔在視覺(jué)上的可區(qū)分性較差。單獨(dú)使用文本詞匯得到的結(jié)果要好一些。將視覺(jué)詞匯和文本詞匯結(jié)合表示成為TF－IDF向量，所得到的結(jié)果要優(yōu)于單獨(dú)使用一種詞匯。而本文提出的數(shù)據(jù)表示方法，即通過(guò)LDA將文檔內(nèi)容映射到主題空間，在所有測(cè)度上均取得了最優(yōu)的結(jié)果。

圖5（a）展示了事件“世界杯”在2011年6月1日～2011年7月20日之間的生命周期模型變化曲線。該事件在6月11日之前的能量值非常低，在6月11日世界杯開(kāi)幕時(shí)，能量值有一個(gè)明顯的上升階段。此后，能量值的變化基本平穩(wěn)并呈逐漸趨勢(shì)，在7月11日～7月13日世界杯決賽期間，能量值達(dá)到了最大值，之后逐漸地以能量衰減為主。圖5（b）為事件“澳大利亞網(wǎng)球公開(kāi)賽”在2011年1月15日～2月7日之間的生命周期模型變化曲線。公開(kāi)賽在1月17日開(kāi)始至1月30日結(jié)束，從曲線可以看出，該事件的生命值在比賽開(kāi)始時(shí)間呈上升趨勢(shì)，隨后達(dá)到穩(wěn)定，在公開(kāi)賽全部結(jié)束后，該事件逐漸走向消亡。圖5（c）為事件“NCAA美國(guó)大學(xué)橄欖球賽”的生命周期模型變化曲線，該事件歷時(shí)5個(gè)月，在2010年9月1日開(kāi)賽后，生命值逐漸增加并達(dá)到一個(gè)長(zhǎng)期較為穩(wěn)定的狀態(tài)，在2011年1月決賽之后，事件逐漸消亡。顯然，本文提出的熱點(diǎn)事件算法可以很好地在Flickr數(shù)據(jù)上為事件的發(fā)展變化建模。從圖5中也可以看出短期事件（圖5（a）、（b））和長(zhǎng)期事件（圖5（c））在生命周期變化上的差別。短期事件的生命周期一般在經(jīng)過(guò)一個(gè)“上升—最大值—下降”的過(guò)程后結(jié)束，而長(zhǎng)期事件會(huì)經(jīng)歷一個(gè)生命值的長(zhǎng)期穩(wěn)定階段，期間伴隨著生命值的小幅波動(dòng)。

圖5 事件生命周期圖

最后，表2給出了熱點(diǎn)事件發(fā)現(xiàn)的一個(gè)結(jié)果展示。該結(jié)果列出了2011年6月4日熱點(diǎn)事件輸出結(jié)果（Top N＝5），每個(gè)事件以4.4節(jié)給出的方式進(jìn)行表示。這5個(gè)事件自上而下分別為“Hoogerheide自行車世界錦標(biāo)賽”，“2010－2011英超聯(lián)賽”，“喜力杯歐洲橄欖球聯(lián)賽”，“澳大利亞網(wǎng)球公開(kāi)賽”和“奧迪杯雪橇世界杯比賽”。由于沒(méi)有標(biāo)準(zhǔn)化的測(cè)度，因此很難評(píng)價(jià)熱點(diǎn)事件檢測(cè)結(jié)果的優(yōu)劣。盡管如此，我們請(qǐng)3位志愿者對(duì)多個(gè)時(shí)間段的熱點(diǎn)事件檢測(cè)結(jié)果進(jìn)行了人工評(píng)價(jià)，志愿者均認(rèn)為大部分的結(jié)果具有很高的合理性。

表2 2011年1月23日熱點(diǎn)事件

6 結(jié)語(yǔ)

本文提出了一種基于衰退理論的Flickr熱點(diǎn)事件檢測(cè)方法。該方法將FLickr中的圖片與用戶提供的文本信息（標(biāo)題、tag、描述）視為一篇文檔，采用加權(quán)的方式增強(qiáng)文本信息在文檔中的影響。利用LDA模型計(jì)算每個(gè)文檔的隱含主題分布，作為文檔的向量表示。提出了一種改進(jìn)的Single－Pass算法進(jìn)行事件檢測(cè)，該算法首先根據(jù)內(nèi)容相似度判斷文檔與已有事件的相似性，然后根據(jù)地理位置信息最終確定文檔是否屬于已有事件。使用衰退理論為每個(gè)事件進(jìn)行生命周期建模，從而獲得事件在每個(gè)時(shí)間段的能量值。以能量值為依據(jù)對(duì)事件進(jìn)行排序，從而輸出給定時(shí)間段內(nèi)的熱點(diǎn)事件。實(shí)驗(yàn)結(jié)果表明，通過(guò)結(jié)合內(nèi)容、視覺(jué)和空間三維的信息，可以改善事件檢測(cè)算法在Flickr數(shù)據(jù)集上的性能。此外，本文提出的方法可以有效地檢測(cè)出給定時(shí)間段內(nèi)的熱點(diǎn)事件。我們以后的研究工作將專注于對(duì)多模態(tài)信息更加有效的融合。同時(shí)，更為高效的在線事件檢測(cè)方法也是值得研究的問(wèn)題之一。

［1］Melanie Aurnhammer，Peter Hanappe，LucSteels.Integrating Collaborative Tagging and Emergent Semantics for Information Retriveal［C］／／Proceeding of WWW’06.New York：ACM Press，2006.

［2］Xirong Li，Cees G M Snoek，Marcel Worring.Learning Tage Relevance by Neighbor Voting for Social Image Retrieval［C］／／Proceeding of the 1st ACM International Conference on Multimedia Information Retrieval.New York：ACM Press，2008：180－187.

［3］Eva Horter，Rainer Lienhart，Malcolm Slaney.Image Retreival on Large－Scale Image Database［C］／／Proceeding of the 6th ACM International Conference Image and Video Retrieval.New York：ACM Press，2007：17－24.

［4］J Allan，R Papka，V Lavrenko.On－line new event detection and tracking［C］／／Proceedings of the 21st Annual International ACM SIGIR Conference，Melbourne，Australia.ACM Press，1998：37－45.

［5］T Brants，F(xiàn) Chen，A Farahat.A System for New E－vent Detection［C］／／Proceedings of the 26th Annual International ACM SIGIR Conference，New York，NY，USA.ACM Press.2003：330－337.

［6］H Halpin，V Robu，H Shepherd.The complex dynamics of collaborative tagging［C］／／Proceedings of the 16th International Conference on World Wide Web.New York：ACM Press，2007：211－220.

［7］Claudiu S Firan，Mihai Georgescu，Wolfgang Nejdl，et al.Bringing Order to Your Photos：Event－Driven Classification of Flickr Images Based on Social knowledge［C］／／Proceedings of the 19th ACM International Conference on Information and Knowledge Management.New York：ACM Press，2010：189－198.

［8］Hila Becker，Mor Naaman，Luis Gravano.Learning Similarity Metrics for Event Identification in Social Media［C］／／Proceedings of 3rd ACM International Conference on Web Search and Data Mining.New York：ACM Press，2010：291－300.

［9］Ling Chen，Abhishak Roy.Event Detection from Flickr Data through Wavelet－based Spatial Analysis［C］／／Proceedings of the 18th ACM Conference on Information and Knowledge Management.New York：ACM Press，2009：523－532.

［10］Xin Jin，Andrew Gallagher，Liangliang Cao，et al.The Wisdom of Social Multimedia：Using Flickr For Prediction and Forecast［C］／／Proceedings of the International Conference on Multimedia.New York：ACM Press，2010：1235－1244.

［11］G P C Fung，J X Yu，H Liu，et al.Time－Dependent Event Hierarchy Construction［C］／／Proceedings of KDD2007，California，USA，2007：300－309.

［12］H L Chieu，Y K Lee.Query Based Event Extraction along a Timeline［C］／／Proceedings of the 27th Annual International ACM SIGIR Conference，Sheffield，UK，ACM Press.2004：425－432.

［13］Q He，K Chang，E P Lim.Analyzing Feature Trajectories for Event Detection［C］／／Proceedings of the 30th Annual International ACM SIGIR Conference，Amsterdam，the Netherlands.ACM Press.2007：207－214.

［14］Q He，K Chang，E P Lim.Using Burstiness to Improve Clustering of Topics in News Streams［C］／／Proceedings of the 7th IEEE International Conference on Data Mining，2007：493－498.

［15］C C Chen，Y T Chen，M C Chen.An Aging Theory for Event Life－Cycle Modeling［J］.IEEE Transactions on Systems，Man，and Cybernetics－Part A：Systems and Humans，2007，Vol.37，No.2.

［16］Kuan－Yu Chen，Luesak Luesukprasert，Seng－cho T.Chou.Hot Topic Extraction Based on Timeline Analysis and Multidimensional Sentence Modeling［J］.IEEE Transactions on Knowledge and Data Engineering，IEEE Computer Society，2007：1016－1025.

［17］Canhui Wang，Min Zhang，Liyun Ru，et al.Automatic Online News Topic Ranking Using Media Focus and User Attention Based on Aging Theory［C］／／Proceeding of CIKM’08，ACM，California，USA.2008：1022－1042.

［18］D Blei，A Ng，M Jordan.Latent Dirichlet Allocation［J］.JMLR，2003，3：993－1022.

［19］T L Griffiths，M Steyvers.Finding scientific topics［C］／／Proceedings of the National Academy of Sciences of the USA.USA：PNAS Press，2004：5226－5235.

［20］Bosch A，Munoz X，Marti R.Which is the best way to organize／classiy images by content？［J］.Image and Vision Computing，2007，25（6）：778－791.

［21］Lowe DG.Distinctive image features from scale－invariant keypoints［J］.Int’1Journal of Computer Vision，2004，60（2）：91－110.