基于衰退理論的Flickr熱點事件檢測方法

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

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

1 引言

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

事件檢測最初為話題檢測與追蹤（Topic Detection and Tracking，TDT）的子任務(wù)之一。在TDT中，事件定義為發(fā)生在特定時間范圍和地點的某件事。傳統(tǒng)的TDT研究目的是在連續(xù)的新聞文檔流中識別新聞事件［4－5］，其研究對象是文本文檔。這類研究對于圖像社區(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ù)據(jù)。根據(jù)事件的定義，合理地利用這些信息將有利于提高事件檢測的效果。近期，已有文獻(xiàn)專注于Flickr數(shù)據(jù)上的事件檢測研究［7－10］，但是這些研究大都只利用了與圖像相關(guān)的文本數(shù)據(jù)而沒有考慮圖像本身的內(nèi)容，并且局限于回顧式的事件檢測，即在歷史數(shù)據(jù)上檢測事件。而事件的發(fā)生和發(fā)展是隨時間變化的，需要實時、在線的檢測方法。

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

3.1 LDA基本理論

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

圖1 LDA圖模型

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

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

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

3）對于文檔m中的第n個詞：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

該向量為熱點事件檢測算法的輸入數(shù)據(jù)形式，整個數(shù)據(jù)表示處理過程如圖2（見下頁）所示。

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

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

4 基于衰退理論的熱點事件檢測

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

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

4.1 衰退理論

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

具體的，首先將時間線劃分為長度為s（本文試驗中，s為1天）的時間段（time slot），對于每個時間段，定義以下三個函數(shù)來計算和更新事件的能量值：

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

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

（a）0≤energyFunction（x）≤1

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

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

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

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

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

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

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

3）將i時間段Energyi＝energyFunction（Nutritioni）。

4.2 熱點事件檢測算法

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

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

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

4.3 相似度計算

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

4.4 結(jié)果事件表示

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

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

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

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

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

5 實驗分析

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

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

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

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

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

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

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

5.2 實驗建立

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

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

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

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

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

5.3 結(jié)果分析

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

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

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

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

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

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

圖5 事件生命周期圖

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

表2 2011年1月23日熱點事件

6 結(jié)語

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

［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.