基于動態窗口的微博突發話題檢測方法

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

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

0 引 言

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

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

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

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

1 問題的形式化定義

2 突發特征和突發話題窗口

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

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

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

(1)

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

(2)

(3)

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

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

定義5 突發詞對BWPp,q對應的突發詞對窗口W的定義如下：

(4)

突發話題檢測過程中，可能會出現多個交叉、重疊和相鄰的突發詞對窗口，則認為這些突發詞對窗口中的微博關聯于同一突發話題。因此，將這些突發詞對窗口進行合并，得到突發話題窗口。

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

(5)

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

3 突發話題檢測

3.1 檢測框架

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

圖1 突發話題檢測框架

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

檢測到突發詞對后，根據突發詞對的出現速度來確定該突發詞對出現比較頻繁的時間區間，即確定突發詞對窗口。當出現多個交叉、重疊、相鄰的突發詞對窗口時，對這些窗口內的微博進行合并，從而得到突發話題窗口。

為了獲取突發話題窗口中微博的主題結構，本文采用改進的NMF聚類方法對窗口中的微博進行聚類分析。該方法采用具有強魯棒性特征的l2,1范數設計短文本聚類模型的優化求解目標函數，可以降低短文本噪聲數據對聚類結果的影響，與傳統的K-meanes和LDA方法相比，該方法具有較好的短文本聚類效果[15]。

3.2 詞對速度表

圖2 詞對速度表

當新的微博到達時，更新詞對速度表T，并計算詞對的加速度，根據詞對加速度的大小來確定是否出現突發詞對。

3.3 檢測算法

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

（二）把握調價時機，確定調價依據。調價的依據。（1）醫療服務成本變動達到10%以上時啟動調價程序；（2）從上次定價截止目前，CPI累計上升8-10%時應該啟動調價程序；（3）財政補助方式、標準發生變化時應該調整；（4）技術難度和風險系數增加時應該調價；（5）國家政策影響醫療機構收入或支出結構發生變化時應該調整。如醫藥分開核算，取消藥品及衛生材料加成時。（6）醫療服務價格調整受群眾支付能力、醫保支付能力、社會價格水平控制等方面影響。應選擇適當的時機與方式進行。選擇恰當的執行時間。

算法1 突發話題檢測算法

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

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

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

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

4 實驗與結果分析

4.1 測試環境與實驗數據

目前面向微博文本流的突發話題檢測沒有標準語料集和標注結果，本文使用的實驗數據來自新浪微博。我們編寫網絡爬蟲程序爬取了從2017年6月01日到2017年6月30日期間的38萬余條微博，并對微博文本流中的突發話題進行了標注。

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

表1 數據特征

4.2 突發話題檢測算法性能評價

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

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

圖3為本文算法與BIC、INF兩種算法在三個數據集上突發話題檢測準確率P、召回率R和F1三種指標的對比結果。三種指標的計算式表示為：

(6)

(7)

(8)

式中:SS是算法檢測正確的突發話題個數；CC是算法檢測到的突發話題個數；RR是已標注的突發話題個數。

(a) FT_DB

(b) MT_DB

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

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

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

4.2.2 DW-BTD算法的實時性

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

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

(a) 唐杰忠去世

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

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

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

(e) 四川茂縣山體滑坡

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

4.2.3 動態窗口的性能評價

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

表2 突發話題窗口范圍

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

4.2.4 突發話題的主題結構

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

表3 突發話題的主題結構

4.3 參數μ對突發話題檢測的影響

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

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

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

從表4中可以看出，隨著μ值的增大，突發話題檢測的準確率上升，召回率降低。這是由于實驗數據中突發話題的強度大小不同，閾值μ增大，導致部分突發強度較低的話題被算法過濾。由表4可知，當閾值μ取0.15時，本文實驗結果最優。

5 結 語

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