基于動態(tài)窗口的微博突發(fā)話題檢測方法

李艷紅 賈麗娜 王素格 李德玉

(山西大學(xué)計算機(jī)與信息技術(shù)學(xué)院 山西 太原 030006)(計算智能與中文信息處理教育部重點實驗室 山西 太原 030006)

0 引 言

近年來，微博社交平臺的迅速發(fā)展，極大地影響了人們的社交方式。國外著名的微博平臺Twitter自上線以來注冊用戶已經(jīng)突破5億，月活躍用戶數(shù)已達(dá)3.35億[1]。新浪官方網(wǎng)站顯示，2017年新浪微博月活躍用戶數(shù)已達(dá)3.76億，日活躍用戶數(shù)為1.65億[2]。由于在微博平臺上發(fā)表和轉(zhuǎn)發(fā)信息迅速便捷，很多突發(fā)性話題會在微博平臺上最先出現(xiàn)，迅速傳播，并引起廣泛的社會共鳴。因此針對微博文本流的突發(fā)話題檢測可以為民意感知、輿情檢測和應(yīng)急處置提供數(shù)據(jù)支持和技術(shù)保障，具有積極的理論和現(xiàn)實意義[3]。

目前，微博突發(fā)話題檢測方法大致分為以文檔為中心的方法[4-7]和以特征為中心的方法[8-14]。以文檔為中心的方法的基本思路是對文本進(jìn)行聚類，將有突發(fā)狀態(tài)的類簇視為突發(fā)話題。如Petrovic 等[4]提出一種基于LSH(locality sensitive hashing)的推特文本聚類算法。算法將新到達(dá)的推特文本和歷史推特文本關(guān)聯(lián)成推特鏈，通過計算每個推特文本鏈的增長速率來檢測是否發(fā)生突發(fā)事件，在對推特流的處理速度上取得了較好的效果。Li等[5]提出一種增量時間主題模型，通過對話題的時間信息建模來檢測突發(fā)話題，并能夠跟蹤突發(fā)話題隨時間的漂移情況。隨后，Li等[6]對增量時間主題模型進(jìn)行改進(jìn)，引入微博文本的主題標(biāo)簽，提高了模型的精度。Huang等[7]利用局部加權(quán)線性回歸方法估計單詞的新穎度和衰減度，使用LDA(Latent Dirichlet Allocation)模型對微博進(jìn)行主題建模，進(jìn)而發(fā)現(xiàn)主題的突發(fā)度和衰減度，同時可以實現(xiàn)突發(fā)話題的追蹤。在以文檔為中心的方法中，由于微博一般限制在140字以內(nèi)，導(dǎo)致內(nèi)容短小，因此容易產(chǎn)生數(shù)據(jù)稀疏性問題。以特征為中心的方法重點在于檢測突發(fā)話題在實時數(shù)據(jù)流上隨時間變化的突發(fā)特征。如Schubert等[8]使用散列技術(shù)跟蹤詞對頻率的平均值與標(biāo)準(zhǔn)差來識別突發(fā)詞對，進(jìn)而對一天之內(nèi)檢測到的突發(fā)詞對聚類形成突發(fā)話題。該方法可以在有限內(nèi)存中跟蹤數(shù)據(jù)流中所有詞對的變化情況，緩解了內(nèi)存的壓力。由于微博中包含大量網(wǎng)絡(luò)新詞、口語化詞或串，為了提高對這些新詞和口語化串的召回率，申國偉等[9]提出了非中文分詞的微博突發(fā)話題檢測框架，采用高階聯(lián)合聚類算法檢測突發(fā)話題，在檢測突發(fā)話題的同時，能夠獲取話題的關(guān)聯(lián)消息和話題參與的用戶。鄭斐然等[10]提出一種基于突發(fā)詞增量聚類的微博新聞話題檢測算法，利用詞頻和詞頻的增長速度確定突發(fā)詞。但是增量式聚類算法對突發(fā)詞輸入順序敏感，影響突發(fā)詞聚類準(zhǔn)確率。郭跇秀等[11]對文獻(xiàn)[10]進(jìn)行改進(jìn)，結(jié)合詞語權(quán)重和用戶影響力定義詞的突發(fā)度，利用凝聚式層次聚類算法對突發(fā)詞聚類識別突發(fā)話題,提高了突發(fā)話題檢測的準(zhǔn)確率，但是凝聚式層次聚類算法時間復(fù)雜度較高。以上以突發(fā)特征為中心的方法采用定長滑動窗口，在滑動窗口結(jié)束時才有可能檢測到突發(fā)話題，無法很好地滿足突發(fā)話題檢測實時性的應(yīng)用需求。

研究人員針對微博突發(fā)話題檢測已經(jīng)開展了很多有意義的研究工作，但是仍然存在以下問題需要深入研究：(1) 由于對突發(fā)話題的檢測具有實時性的應(yīng)用需求，因此如何減少突發(fā)話題檢測的時間延遲是當(dāng)前需要解決的問題。(2) 已有的微博突發(fā)話題檢測方法通常采用定長滑動窗口技術(shù)，由于這種數(shù)據(jù)流分段方法沒有考慮突發(fā)話題持續(xù)范圍，滑動窗口的大小難以確定，因此勢必對突發(fā)話題的檢測帶來影響。所以，如何確定突發(fā)話題的范圍也是研究難點之一。

針對以上挑戰(zhàn)，本文提出一種基于動態(tài)窗口的微博突發(fā)話題檢測方法。該方法對微博中的詞對加速度進(jìn)行實時檢測，由于無需比較當(dāng)前窗口與歷史窗口中詞頻的變化，所以在早期就可以發(fā)現(xiàn)突發(fā)話題。此外，本文提出一種基于動態(tài)窗口的檢測機(jī)制，根據(jù)突發(fā)詞對單位時間內(nèi)出現(xiàn)的數(shù)量，也就是突發(fā)詞對的速度來確定“突發(fā)詞對窗口”范圍，通過合并交叉、重疊、相鄰的“突發(fā)詞對窗口”得到突發(fā)話題窗口。最后利用改進(jìn)的非負(fù)矩陣分解[15](Nonnegative Matrix Factorization，NMF)聚類方法捕獲突發(fā)話題窗口中微博的主題結(jié)構(gòu)。

1 問題的形式化定義

2 突發(fā)特征和突發(fā)話題窗口

由于微博文本流中突發(fā)話題和其他一般話題是同時存在的，因此如何將突發(fā)話題和一般話題區(qū)分開來顯得尤為重要。一般話題往往以平穩(wěn)的速度出現(xiàn)在微博文本流中，而突發(fā)話題伴隨著突發(fā)事件的發(fā)生而出現(xiàn)，相關(guān)微博出現(xiàn)的速度會明顯增大。由于速度的變化快慢可以用“加速度”來刻畫，當(dāng)突發(fā)話題出現(xiàn)時，相關(guān)微博出現(xiàn)的加速度會明顯增大，而一般話題的相關(guān)微博出現(xiàn)的加速度幾乎為零，因此，使用“加速度”識別突發(fā)特征檢測突發(fā)話題的出現(xiàn)是可行的。

傳統(tǒng)的微博突發(fā)話題檢測方法[10-11,16]通常采用單個詞作為突發(fā)特征檢測突發(fā)話題。由于詞對可以體現(xiàn)某些行為發(fā)生的主謂或動賓結(jié)構(gòu)[17]，與單個詞比較而言，包含了更多的話題信息，例如：(貴州，發(fā)生)，(天然氣，爆炸)，(發(fā)生，爆炸)。因此，本文將詞對的加速度作為突發(fā)特征。下面依次給出詞對頻率、詞對速度、詞對加速度以及突發(fā)詞對的定義。

定義1 微博(di,ti)中任意詞對(wp,wq)的頻率fi(wp,wq)計算式表示為：

(1)

式中：分母表示從di中任意選擇兩個詞的組合數(shù)；分子表示從di中選擇兩個特定詞的組合數(shù)。

(2)

(3)

式中：ΔT1<ΔT2,并且ΔT1和ΔT2兩個時間片的終止時間均為ti時刻。

直觀上，微博文本流中突發(fā)詞對出現(xiàn)的速度在一定程度上反映了突發(fā)話題的熱度。如果在一個連續(xù)時間段內(nèi)，某個突發(fā)詞對的速度均不小于某個閾值，那么我們稱這個時間段內(nèi)的微博集合為該突發(fā)詞對所對應(yīng)的突發(fā)詞對窗口。

定義5 突發(fā)詞對BWPp,q對應(yīng)的突發(fā)詞對窗口W的定義如下：

(4)

突發(fā)話題檢測過程中，可能會出現(xiàn)多個交叉、重疊和相鄰的突發(fā)詞對窗口，則認(rèn)為這些突發(fā)詞對窗口中的微博關(guān)聯(lián)于同一突發(fā)話題。因此，將這些突發(fā)詞對窗口進(jìn)行合并，得到突發(fā)話題窗口。

定義6 若存在count個交叉、重疊或者相鄰的突發(fā)詞對窗口W1,W2,…,Wcount，那么突發(fā)話題窗口DW的定義為：

(5)

根據(jù)定義5、定義6可知，突發(fā)話題窗口的范圍是由微博文本流中突發(fā)詞對的速度決定的，是動態(tài)變化的。

3 突發(fā)話題檢測

3.1 檢測框架

為了實時檢測微博文本流中的突發(fā)話題，本文提出了一種基于動態(tài)窗口的微博突發(fā)話題檢測框架，如圖1所示。突發(fā)話題檢測過程主要由突發(fā)特征識別、動態(tài)窗口確定和突發(fā)話題窗口聚類三個階段組成。

圖1 突發(fā)話題檢測框架

突發(fā)特征識別是突發(fā)話題檢測與其他話題檢測的主要區(qū)別，本文將詞對加速度作為突發(fā)特征。當(dāng)有新的微博到達(dá)時，進(jìn)行突發(fā)特征識別，即統(tǒng)計微博中所有詞對的頻率、更新詞對速度表，并計算詞對的加速度。如果詞對的加速度超出給定閾值，該詞對被標(biāo)記為突發(fā)詞對。

檢測到突發(fā)詞對后，根據(jù)突發(fā)詞對的出現(xiàn)速度來確定該突發(fā)詞對出現(xiàn)比較頻繁的時間區(qū)間，即確定突發(fā)詞對窗口。當(dāng)出現(xiàn)多個交叉、重疊、相鄰的突發(fā)詞對窗口時，對這些窗口內(nèi)的微博進(jìn)行合并，從而得到突發(fā)話題窗口。

為了獲取突發(fā)話題窗口中微博的主題結(jié)構(gòu)，本文采用改進(jìn)的NMF聚類方法對窗口中的微博進(jìn)行聚類分析。該方法采用具有強(qiáng)魯棒性特征的l2,1范數(shù)設(shè)計短文本聚類模型的優(yōu)化求解目標(biāo)函數(shù)，可以降低短文本噪聲數(shù)據(jù)對聚類結(jié)果的影響，與傳統(tǒng)的K-meanes和LDA方法相比，該方法具有較好的短文本聚類效果[15]。

3.2 詞對速度表

圖2 詞對速度表

當(dāng)新的微博到達(dá)時，更新詞對速度表T，并計算詞對的加速度，根據(jù)詞對加速度的大小來確定是否出現(xiàn)突發(fā)詞對。

3.3 檢測算法

基于圖1的突發(fā)話題檢測框架，本文設(shè)計了一種基于動態(tài)窗口的突發(fā)話題檢測算法(Bursty Topic Detection based on Dynamic Window,DW-BTD)，如算法1所示。

（二）把握調(diào)價時機(jī)，確定調(diào)價依據(jù)。調(diào)價的依據(jù)。（1）醫(yī)療服務(wù)成本變動達(dá)到10%以上時啟動調(diào)價程序；（2）從上次定價截止目前，CPI累計上升8-10%時應(yīng)該啟動調(diào)價程序；（3）財政補(bǔ)助方式、標(biāo)準(zhǔn)發(fā)生變化時應(yīng)該調(diào)整；（4）技術(shù)難度和風(fēng)險系數(shù)增加時應(yīng)該調(diào)價；（5）國家政策影響醫(yī)療機(jī)構(gòu)收入或支出結(jié)構(gòu)發(fā)生變化時應(yīng)該調(diào)整。如醫(yī)藥分開核算，取消藥品及衛(wèi)生材料加成時。（6）醫(yī)療服務(wù)價格調(diào)整受群眾支付能力、醫(yī)保支付能力、社會價格水平控制等方面影響。應(yīng)選擇適當(dāng)?shù)臅r機(jī)與方式進(jìn)行。選擇恰當(dāng)?shù)膱?zhí)行時間。

算法1 突發(fā)話題檢測算法

輸入：微博文本流D，時間片ΔT1和ΔT2，詞對加速度閾值μ，突發(fā)詞對速度閾值φ，合并窗口個數(shù)閾值c，聚類數(shù)目k

輸出：類中心矩陣P和文本隸屬度矩陣Q

步驟2 突發(fā)詞對窗口集合確定 對每一個BWPp,q，根據(jù)定義5確定突發(fā)詞對窗口W，并判斷突發(fā)詞對窗口之間是否交叉、重疊或相鄰。

步驟4 突發(fā)話題窗口聚類 使用改進(jìn)的NMF聚類算法對DW內(nèi)的微博聚類，得到類中心矩陣P和文本隸屬度矩陣Q。

4 實驗與結(jié)果分析

4.1 測試環(huán)境與實驗數(shù)據(jù)

目前面向微博文本流的突發(fā)話題檢測沒有標(biāo)準(zhǔn)語料集和標(biāo)注結(jié)果，本文使用的實驗數(shù)據(jù)來自新浪微博。我們編寫網(wǎng)絡(luò)爬蟲程序爬取了從2017年6月01日到2017年6月30日期間的38萬余條微博，并對微博文本流中的突發(fā)話題進(jìn)行了標(biāo)注。

在提取微博的文本信息和發(fā)布時間、生成微博文本數(shù)據(jù)流之后，對微博文本進(jìn)行了預(yù)處理，首先刪除文本中的表情符號、URL、“@用戶”，然后利用Python中的中文分詞模塊Jieba對微博文本進(jìn)行分詞和去除停用詞處理，最后刪除副本以及少于三個詞的微博。預(yù)處理后得到35萬余條實驗數(shù)據(jù)，其中包括57個突發(fā)話題，每個話題的持續(xù)時間在0.5小時到10小時之間。將已標(biāo)注的微博數(shù)據(jù)根據(jù)時間劃分成三個數(shù)據(jù)集(FT_DB、MT_DB、LT_DB)進(jìn)行實驗，數(shù)據(jù)特征如表1所示。

表1 數(shù)據(jù)特征

4.2 突發(fā)話題檢測算法性能評價

為了評價算法的性能，將本文提出的DW-BTD算法與已有的兩種突發(fā)話題檢測算法在上述三個數(shù)據(jù)集上作了對比實驗。實驗中算法DW-BTD的參數(shù)取值為：詞對加速度閾值μ=0.15，突發(fā)詞對速度閾值φ=5.0，突發(fā)詞對窗口合并數(shù)閾值c=4，聚類數(shù)目k=8，ΔT1=15分鐘，ΔT2=30分鐘。本文對兩種對比算法進(jìn)行參數(shù)調(diào)整后與本文方法在同一環(huán)境下做對比實驗。文獻(xiàn)[10]提出了一種基于定長滑動窗口的突發(fā)話題檢測算法(BIC)，實驗中突發(fā)詞權(quán)重閾值取30，增量聚類閾值取200，定長滑動窗口大小為3小時。文獻(xiàn)[11]對文獻(xiàn)[10]的檢測算法進(jìn)行了改進(jìn)，但也是基于定長滑動窗口的檢測算法INF，實驗中突發(fā)詞權(quán)重閾值取3.0，簇間距離閾值取600，定長滑動窗口大小為3小時。

4.2.1 DW-BTD算法的P、R和F1值

圖3為本文算法與BIC、INF兩種算法在三個數(shù)據(jù)集上突發(fā)話題檢測準(zhǔn)確率P、召回率R和F1三種指標(biāo)的對比結(jié)果。三種指標(biāo)的計算式表示為：

(6)

(7)

(8)

式中:SS是算法檢測正確的突發(fā)話題個數(shù)；CC是算法檢測到的突發(fā)話題個數(shù)；RR是已標(biāo)注的突發(fā)話題個數(shù)。

(a) FT_DB

(b) MT_DB

(c) LT_DB圖3 三種檢測算法的準(zhǔn)確率P、召回率R、F1值

由圖3可知，本文提出的DW-BTD算法在三個數(shù)據(jù)集上的P、R和F1值都明顯高于BIC、INF算法。通過對實驗數(shù)據(jù)的分析，發(fā)現(xiàn)突發(fā)話題的持續(xù)時間是不可預(yù)知的，而BIC、INF算法均采用定長滑動窗口，導(dǎo)致滑動窗口難以與突發(fā)話題相對應(yīng)。因此“滑動窗口大小”的確定是算法應(yīng)用的難點。DW-BTD算法基于動態(tài)窗口技術(shù)，很好地解決了這一問題。例如實驗中“倫敦高層公寓樓失火”這一突發(fā)話題持續(xù)時間為32分鐘，而BIC、INF算法中滑動窗口大小為3小時，導(dǎo)致這兩個算法均未檢測到該突發(fā)話題。

由圖3可知，INF算法的P、R和F1值比BIC算法均有所提升。這是由于INF算法一方面在抽取突發(fā)詞時考慮了微博用戶的影響力；另一方面在對突發(fā)詞聚類時，采用凝聚式層次聚類，避免了對突發(fā)詞輸入順序的依賴。

4.2.2 DW-BTD算法的實時性

為了評價算法的實時性，我們對比了本文提出的DW-BTD算法和BIC、INF算法對同一突發(fā)話題的檢出時間。

圖4給出了六個突發(fā)話題單位時間相關(guān)微博數(shù)量隨時間的變化情況，以及三種算法的檢出時間?？梢钥闯?，DW-BTD算法在突發(fā)話題發(fā)生的早期就可以檢測到，檢出時間比BIC和INF算法提前了至少30分鐘。這是由于BIC和INF算法在檢測突發(fā)話題時，需要檢測當(dāng)前窗口與歷史窗口中對應(yīng)詞頻的變化情況，所以只有在滑動窗口結(jié)束時才有可能檢測到突發(fā)話題，而DW-BTD算法是對微博中詞對的加速度進(jìn)行實時檢測，當(dāng)加速度超過設(shè)定閾值時便可以發(fā)現(xiàn)突發(fā)話題。圖4(b)中，DW-BTD算法的檢出時間比BIC和INF算法提前了3小時，這是因為BIC和INF算法的滑動窗口恰好是從12:00:00到15:00:00，所以15:00:00才檢測到突發(fā)話題。

(a) 唐杰忠去世

(b) 北大女碩士在美失蹤

(c) 豐縣幼兒園門口爆炸

(d) 第一篇高考滿分作文出爐

(e) 四川茂縣山體滑坡

(f) 國乒集體退賽圖4 突發(fā)話題檢測實時性

4.2.3 動態(tài)窗口的性能評價

突發(fā)話題窗口是由count個交叉重疊、相鄰的突發(fā)詞對窗口合并而成的，為了評價突發(fā)話題窗口的動態(tài)性，本文統(tǒng)計了DW-BTD算法檢測出的六個突發(fā)話題的突發(fā)話題窗口范圍。表2列舉了每個突發(fā)話題(BT)的持續(xù)時間(TC)、算法檢測出的合并突發(fā)詞對窗口個數(shù)(count)、突發(fā)話題窗口起始時間(TS)、終止時間(TE)和突發(fā)話題窗口范圍(SC)。

表2 突發(fā)話題窗口范圍

從表2中可以看出，對于不同的突發(fā)話題，算法檢測出的突發(fā)話題窗口起始、終止時間以及范圍大小均不同。這是由于DW-BTD算法是根據(jù)突發(fā)詞對速度的變化趨勢動態(tài)地確定突發(fā)話題窗口范圍，窗口范圍與突發(fā)話題基本匹配，體現(xiàn)了窗口的動態(tài)性。

4.2.4 突發(fā)話題的主題結(jié)構(gòu)

為了獲取突發(fā)話題的主題結(jié)構(gòu)，采用改進(jìn)的NMF聚類算法對突發(fā)話題窗口中的微博聚類。表3列舉了BIC、INF和DW-BTD三種算法在MT_DB數(shù)據(jù)集中檢測出的三個突發(fā)話題。通過對突發(fā)話題窗口中的微博進(jìn)行聚類分析，DW-BTD算法得到的突發(fā)話題的主題結(jié)構(gòu)如表3所示。例如：對于“唐杰忠去世”這一突發(fā)話題，算法檢測出了五個突發(fā)詞對，合并突發(fā)詞對窗口得到突發(fā)話題窗口。對突發(fā)話題窗口中的微博聚類后得到一個類中心矩陣P和一個文本隸屬度矩陣Q。P中一列代表一類，即一個主題，從P中選取包含突發(fā)詞對的列，得到表3所示的三個類，也就是突發(fā)話題“唐杰忠去世”的主題結(jié)構(gòu)。這三類分別對應(yīng)突發(fā)話題的三個主題：(1) 關(guān)于相聲藝術(shù)家唐杰忠患癌去世的消息；(2) 對唐老師生前相聲作品的討論；(3) 針對如何有效預(yù)防癌癥的討論。

表3 突發(fā)話題的主題結(jié)構(gòu)

4.3 參數(shù)μ對突發(fā)話題檢測的影響

為了分析詞對加速度閾值μ對DW-BTD算法突發(fā)話題檢測準(zhǔn)確率P、召回率R和F1的影響，本文在FT_DB、MT_DB、LT_DB三個數(shù)據(jù)集上進(jìn)行了實驗。

本文設(shè)置加速度閾值μ取0.05～0.25之間不同的值進(jìn)行實驗，DW-BTD算法的P、R和F1值如表4所示。

表4 不同μ值下的P、R和F1值

從表4中可以看出，隨著μ值的增大，突發(fā)話題檢測的準(zhǔn)確率上升，召回率降低。這是由于實驗數(shù)據(jù)中突發(fā)話題的強(qiáng)度大小不同，閾值μ增大，導(dǎo)致部分突發(fā)強(qiáng)度較低的話題被算法過濾。由表4可知，當(dāng)閾值μ取0.15時，本文實驗結(jié)果最優(yōu)。

5 結(jié) 語

本文提出了一種基于動態(tài)窗口的微博突發(fā)話題檢測方法。首先通過實時檢測微博文本流中詞對的加速度大小來判斷是否有突發(fā)話題發(fā)生，減少了突發(fā)話題檢測的時間延遲；其次基于突發(fā)詞對的速度變化動態(tài)地確定突發(fā)話題窗口范圍，提高了突發(fā)話題檢測的準(zhǔn)確率和召回率；最后利用改進(jìn)的NMF聚類算法對窗口中的微博進(jìn)行聚類，得到了突發(fā)話題的主題結(jié)構(gòu)。在微博文本流上的對比實驗驗證了本文方法的有效性。