介飛 謝飛 李磊 吳信東

社交網(wǎng)絡(luò)深刻影響著大眾的日常生活[1],人們習(xí)慣將感興趣的事件通過社交媒體與他人進行分享和交流.伴隨著事件的發(fā)生,社交網(wǎng)絡(luò)中相關(guān)文本的發(fā)布、轉(zhuǎn)發(fā)及評論等行為會形成一個密集期,即表現(xiàn)為行為特征的一個突發(fā)性.突發(fā)性背后往往蘊含著事件信息,可用來發(fā)掘潛在的市場需求和隱含的政治傾向,進而為商業(yè)推廣或輿情監(jiān)控提供指導(dǎo).相較于傳統(tǒng)媒體,社交網(wǎng)絡(luò)的公眾參與度更高.因此,發(fā)現(xiàn)社交網(wǎng)絡(luò)中的事件突發(fā)性具有更為重要的現(xiàn)實意義.

突發(fā)性即被觀測目標(biāo)的頻數(shù)等特征值陡然上升的現(xiàn)象.隨著事件的發(fā)生,某些特征值,例如文檔頻數(shù),會急劇上升,形成事件相關(guān)突發(fā)性(Eventrelated bursts),簡稱事件突發(fā)性.Kleinberg首先構(gòu)建了基于自動機理論的突發(fā)性檢測模型[2],用于描述電子郵件中的事件信息.突發(fā)性檢測最初是應(yīng)用在新聞、電子郵件和科研論文等傳統(tǒng)媒介中[2?5],而隨著社交網(wǎng)絡(luò)的興起,為突發(fā)性檢測提供了新的應(yīng)用環(huán)境.在傳統(tǒng)的突發(fā)性檢測中,通常以關(guān)鍵詞詞頻信息等文本型特征作為依據(jù),即考慮了內(nèi)容信息;而在社交網(wǎng)絡(luò)中,可以利用行為、鏈接和情感等非文本型特征進行事件突發(fā)性檢測[1,6?8].但據(jù)我們所知,還未有研究人員開展文本型特征與社交行為特征結(jié)合的相關(guān)研究.其中,文本型特征(例如關(guān)鍵詞)可從語義上直接反映事件發(fā)生情況,能準(zhǔn)確判斷事件是否發(fā)生,但以其作為突發(fā)性檢測的特征,存在如何篩選的問題,一般只能根據(jù)用戶意圖進行人工選擇,再按選定的特征變動情況,判斷突發(fā)性,自動化程度較低;而社交行為特征用于事件突發(fā)性檢測時,由于其與事件發(fā)生的關(guān)系不明確,可能由于事件交錯,事件突發(fā)性程度較低等原因?qū)е侣z或錯檢.根據(jù)對具體數(shù)據(jù)的分析,當(dāng)前利用社交行為特征進行事件突發(fā)性檢測的方法不能準(zhǔn)確發(fā)現(xiàn)圖1中所示的事件突發(fā)性.

圖1中的數(shù)據(jù)爬取自新浪微博,對應(yīng)的時間段為2015年10月21日12時～24日0時,共60小時.圖中第一段標(biāo)注區(qū)間(9～12)內(nèi)進行了一場亞冠比賽,恒大0:0戰(zhàn)平日本柏太陽神隊;第二段標(biāo)注區(qū)間(33～36)對應(yīng)事件為恒大集團與英國相關(guān)機構(gòu)簽署協(xié)議,開展項目合作.由于該事件發(fā)生在夜晚(22日21:00左右,對應(yīng)圖中索引33),因此與之相關(guān)的微博活動在事件發(fā)生后短時間內(nèi)上升,隨后迅速下降,第二天,又呈現(xiàn)突發(fā)狀態(tài)勢(對應(yīng)區(qū)間45～48與51～57).圖1中展示四種社交行為,微博總數(shù)對應(yīng)用戶的發(fā)布行為,原創(chuàng)微博對應(yīng)用戶的原創(chuàng)發(fā)布行為,轉(zhuǎn)發(fā)微博對應(yīng)轉(zhuǎn)發(fā)行為,內(nèi)嵌網(wǎng)址對應(yīng)引用外部信息行為.對比兩個事件,兩者發(fā)生在連續(xù)兩天的同一時間段(相差24小時),從不同行為頻數(shù)特征的變動情況來看,第一個事件引起的突發(fā)性遠(yuǎn)大于第二個事件的突發(fā)性,表現(xiàn)為頻數(shù)值的驟降(圖中箭頭所示),此時,第二個事件對應(yīng)區(qū)間就易被判別為非突發(fā)狀態(tài),造成該事件突發(fā)性的漏檢.由圖1可知,第二段標(biāo)注區(qū)域所示的事件突發(fā)性本身突發(fā)模式較為顯著,但由于鄰近遠(yuǎn)高于自身突發(fā)性事件的影響,易被其他事件“掩蓋”1“掩蓋”,指當(dāng)前突發(fā)性判定受臨近事件突發(fā)性的影響,并不表明二者時間上有重疊;當(dāng)事件重疊時,相關(guān)算法會識別為一次突發(fā)性,并不會影響突發(fā)性檢測的準(zhǔn)確性,因此不必區(qū)分重疊事件.其突發(fā)性,本文稱此類事件突發(fā)性為隱式事件突發(fā)性.上述類型的隱式事件突發(fā)性的發(fā)生是由于外部事件的干擾,還有一類隱式事件突發(fā)性,則是由于事件本身引起,例如事件發(fā)生時,關(guān)注該事件的用戶數(shù)量不足,則相應(yīng)的用戶行為(例如轉(zhuǎn)發(fā)、評論、點贊等),不會發(fā)生明顯變化,但用戶討論內(nèi)容具有明顯傾向性,如某些詞語反復(fù)出現(xiàn),此時再單純以社交行為進行事件突發(fā)性檢測,則會由于相關(guān)行為突發(fā)性不足造成漏檢,引入內(nèi)容信息成為解決該問題的選項之一.

本文主要研究事件突發(fā)性中的非常規(guī)類型—隱式事件突發(fā)性,該類事件突發(fā)性由于事件本身或外部因素的影響易被漏檢,成為現(xiàn)有事件突發(fā)性檢測算法的瓶頸.針對隱式事件突發(fā)性,本文在當(dāng)前基于行為特征的事件突發(fā)性檢測方案基礎(chǔ)上,引入關(guān)鍵詞特征,伴隨時間的推進,動態(tài)改變各個時間窗口的關(guān)鍵詞候選,實現(xiàn)不同時間區(qū)間與不同關(guān)鍵詞特征綁定,進而將不同事件突發(fā)性映射到不同特征空間上,以此剔除噪音及事件之間的互相影響;隨后,將由關(guān)鍵詞特征與行為特征得到的突發(fā)性結(jié)果關(guān)聯(lián),以二者的突發(fā)性情況共同決定社交文本流的突發(fā)性,從而更為準(zhǔn)確地檢測事件突發(fā)性.本文的貢獻(xiàn)主要有兩點:1)首次將文本型(關(guān)鍵詞)特征與非文本型(社交行為)特征結(jié)合,開展事件突發(fā)性檢測研究;雖然已有相關(guān)文獻(xiàn)[9?10]開展多特征事件檢測研究,但與本文發(fā)現(xiàn)事件突發(fā)性區(qū)間的目標(biāo)有所區(qū)別,例如,文獻(xiàn)[9]只考慮結(jié)果是否處于事件發(fā)生時間前后的一定范圍,并不關(guān)注事件發(fā)生區(qū)間的確定問題;2)在進行以關(guān)鍵詞為特征的事件突發(fā)性檢測時,本文提出了各時間窗口內(nèi)候選關(guān)鍵詞的篩選方案及多關(guān)鍵詞突發(fā)性結(jié)果關(guān)聯(lián)決定當(dāng)前時間窗口突發(fā)性的策略.在兩個不同類別真實數(shù)據(jù)集上開展的相關(guān)實驗表明,上述方案可以有效提升社交網(wǎng)絡(luò)中事件突發(fā)性檢測算法的性能,對事件檢測等相關(guān)領(lǐng)域研究具有一定的參考價值.

本文結(jié)構(gòu)如下:第1節(jié)對研究的問題進行形式化表述;第2節(jié)詳細(xì)介紹綜合兩類特征的事件突發(fā)性檢測算法的步驟;第3節(jié)展示在兩個真實數(shù)據(jù)集上的實驗結(jié)果,并對結(jié)果進行詳細(xì)分析;第4節(jié)介紹事件突發(fā)性檢測研究領(lǐng)域的相關(guān)工作;第5節(jié)對本文進行總結(jié)并指出未來可能的研究方向.

1 問題表述

本文主要研究社交網(wǎng)絡(luò)中的事件突發(fā)性檢測問題,即在社交網(wǎng)絡(luò)數(shù)據(jù)中,確定由真實事件發(fā)生引起的突發(fā)性對應(yīng)的時間區(qū)間,包括確定事件突發(fā)性的開始與結(jié)束時間窗口,著重解決現(xiàn)存算法對于隱式事件突發(fā)性的漏檢問題.

事件突發(fā)性(Event-related bursts),是由某一真實事件引起的相關(guān)特征突發(fā)性對應(yīng)的一段時間區(qū)間[ts,te],ts與te分別表示事件突發(fā)區(qū)間的開始時間窗口與結(jié)束時間窗口.與特定主題相關(guān)的事件突發(fā)性一般不止一個,因此這里用集合表示為Busrts={[ts,te]|ts,te∈T,s≤e},其中,T表示時間窗口序列,s,e表示突發(fā)區(qū)間開始與結(jié)束對應(yīng)的時間窗口索引值.事件突發(fā)性與事件并非一一對應(yīng)關(guān)系,與事件內(nèi)容、用戶行為等因素有關(guān),一次事件可能引起多次事件突發(fā)性.

隱式事件突發(fā)性,指具有以下兩類特點之一的事件突發(fā)性.1)突發(fā)模式不明顯,突發(fā)程度絕對值較低;2)突發(fā)程度相對較低,突發(fā)性被鄰近突發(fā)程度更高的事件“掩蓋”.這兩類事件突發(fā)性分別根據(jù)其特點稱為真隱式事件突發(fā)性與假隱式事件突發(fā)性,合稱為隱式事件突發(fā)性.本文著力解決隱式事件突發(fā)性的檢測問題,以提高現(xiàn)有事件突發(fā)性檢測算法的效果.

本文涉及的其他概念與定義,借用文獻(xiàn)[1]中的相關(guān)表述,描述如下:

行為(Activity),指話題或事件發(fā)生時用戶進行的動作,例如微博中的發(fā)布、轉(zhuǎn)發(fā)、評論、點贊、嵌入網(wǎng)址鏈接等操作.

時間窗口序列(Time window sequence),一個長為N的時間窗口序列表示為T=(t1,t2,···,tN),ti表示第i個時間窗口.將數(shù)據(jù)集按時間排序,以等長時間粒度進行切分,即可得到時間窗口序列.

行為流(Activity stream),用數(shù)字序列H=表示在第i個時間窗口內(nèi)m類行為發(fā)生的總次數(shù),N表示時間窗口個數(shù).

詞語流(Term stream),用數(shù)字序列表示在第i個時間窗口內(nèi)詞語w的文檔頻率,N表示時間窗口個數(shù).

狀態(tài)序列(State sequence),每個時間窗口ti對應(yīng)狀態(tài)zi,由此構(gòu)成狀態(tài)序列Z=(z1,z2,···,zN),zi表示第i個時間窗口的狀態(tài)索引值,z∈{0,1,2,···,NZ?1},z取值為0時表示非突發(fā)狀態(tài),非0表示突發(fā)狀態(tài),NZ表示不同狀態(tài)數(shù)目.狀態(tài)索引值反映事件突發(fā)程度,其值越大表示突發(fā)程度越高,突發(fā)性檢測即指定每個時間窗口的狀態(tài)索引值,連續(xù)狀態(tài)索引值非零的時間窗口序列構(gòu)成一個突發(fā)區(qū)間.

上述定義示例如圖2所示,橫軸表示時間窗口,縱軸表示Activity或Term特征頻數(shù)值,圖中折線表示狀態(tài)序列,本文選用兩種狀態(tài)(z∈{0,1}),即只區(qū)分突發(fā)狀態(tài)與非突發(fā)狀態(tài).

2 方法設(shè)計

2.1 思路概述

圖2 相關(guān)定義示意圖Fig.2 A schematic diagram of related conceptions

由前文所述可知,現(xiàn)有算法不易發(fā)現(xiàn)隱式事件突發(fā)性,算法的召回率難以提升,因此對這類非常規(guī)突發(fā)性必須提出針對性解決方案,避免可能的漏檢問題.對于真隱式事件突發(fā)性,事件突發(fā)性程度本身較低,可以考慮引入新的特征表征事件;在新的特征刻畫事件時,該事件能夠表現(xiàn)出較高的突發(fā)性;關(guān)鍵詞特征與事件的發(fā)生直接相關(guān),事件發(fā)生,則關(guān)鍵詞出現(xiàn)頻數(shù)大幅上升,可以滿足要求.對于假隱式事件突發(fā)性,若只關(guān)注行為特征,事件發(fā)生時,用戶會產(chǎn)生相似的行為模式(例如轉(zhuǎn)發(fā)和評論等),易造成時間上鄰近的不同事件的“掩蓋”問題,而對于關(guān)鍵詞特征,不同事件對應(yīng)的關(guān)鍵詞集合重合度較低,可將不同的時間窗口與對應(yīng)的關(guān)鍵詞集綁定,則緊鄰的事件由于關(guān)鍵詞集的不同,被映射到不同的關(guān)鍵詞特征空間,從而避免了鄰近事件突發(fā)性的相互干擾.綜上,為應(yīng)對現(xiàn)有事件突發(fā)性檢測算法對于隱式事件突發(fā)性的漏檢問題,文本型信息的引入是一個可選的方案,本文提出的算法即基于此思路,將社交行為特征與關(guān)鍵詞特征結(jié)合,解決隱式事件突發(fā)性的漏檢問題,從而提升事件突發(fā)性檢測的整體效果.

2.2 突發(fā)性檢測方法

本文使用文獻(xiàn)[1]中提出的單目標(biāo)序列與多目標(biāo)2目標(biāo),即指特征,單目標(biāo)序列表示算法輸入為單一類別特征序列,例如行為特征,算法輸入只有一種行為流時,則為單目標(biāo),當(dāng)輸入多種行為流時,即為多目標(biāo).序列突發(fā)性檢測算法.

眾所周知,豐富的社交特征給我們提供了多樣的數(shù)據(jù)來源,但社交媒體普遍存在的噪音問題也阻礙傳統(tǒng)方法直接應(yīng)用在社交網(wǎng)絡(luò)中.因此,Zhao等根據(jù)Twitter內(nèi)容突發(fā)性的特點,提出了適用于社交網(wǎng)絡(luò)數(shù)據(jù)的單目標(biāo)序列與多目標(biāo)序列突發(fā)性檢測算法,構(gòu)建了三類成本,對社交網(wǎng)絡(luò)中的消息生成進行建模,包括生成成本、平滑成本以及跨目標(biāo)流成本[1].

生成成本(Generating cost),表示根據(jù)特定的概率分布,當(dāng)前時間窗口i在狀態(tài)下某個特定特征m(例如社交行為)出現(xiàn)次數(shù)時的成本,可取概率的對數(shù)負(fù)值,此時概率越大,對應(yīng)成本越低.概率分布可選用二項分布、泊松分布或指數(shù)分布.使用泊松分布時,概率分布函數(shù)具體形式為其中μ0表示一個時間窗口內(nèi)特征頻數(shù)的平均值,如果處于突發(fā)狀態(tài),目標(biāo)特征會以更高的速率發(fā)生,從而導(dǎo)致較高的期望μ1,可以設(shè)置μ1=μ0×ρ,ρ＞1,為參數(shù).

平滑成本(Smoothness cost),傾向于在標(biāo)注時保持突發(fā)狀態(tài)序列穩(wěn)定,實現(xiàn)剔除噪音,處理數(shù)據(jù)隨機波動的功能.通常,與事件相關(guān)的突發(fā)性會由于人們的持續(xù)關(guān)注而維持一段較長時間且波動較小,而諸如廣告等噪音信息帶來的突發(fā)性,更多時候出現(xiàn)時間較為短暫,因此可以突發(fā)性延續(xù)的時間長短判斷該突發(fā)性是由真實事件引起或由噪音引起.其中一種衡量方案為

其中,si,ei分別表示第i個狀態(tài)值相同的序列開始與結(jié)束時間窗口索引,式(1)表示將狀態(tài)序列中狀態(tài)值相同的區(qū)間長度進行平方求和.

例如,假設(shè)突發(fā)狀態(tài)為二狀態(tài),即只區(qū)分突發(fā)狀態(tài)與非突發(fā)狀態(tài),則一系列時間窗口對應(yīng)一系列狀態(tài)序列,如 “0000100000” 與“0000000000”,按式(1)計算平滑指標(biāo)分別為42(42+12+52=42)與100(102=100),平滑指標(biāo)取負(fù)值即可作為區(qū)別噪音與正常突發(fā)性的成本值,在此例中,如果指定第5個時間窗口出現(xiàn)突發(fā)狀態(tài),其維持時間僅一個時間窗口,時間較短,顯然為噪音的可能性較大,因此其平滑指標(biāo)較小(取負(fù)值為?42,與沒有突發(fā)性的序列的平滑成本?100比較,成本較大).

跨目標(biāo)流成本(Cross stream cost),借助上述思想,在具有相關(guān)性的多目標(biāo)序列中,不同目標(biāo)的突發(fā)模式類似,因此多個目標(biāo)序列的同一時間窗口的狀態(tài)也應(yīng)該趨同,否則應(yīng)給予一定的懲罰成本(即跨目標(biāo)流成本).

其中,Γ(·)為指示函數(shù)(Indicator function),m1與m2對應(yīng)任意兩類特征,若其同一時間窗口內(nèi)的狀態(tài)值不相等,則取值為1,計入成本,否則成本為0.

由上述三類成本我們可以構(gòu)建單目標(biāo)序列與多目標(biāo)序列突發(fā)性檢測的成本模型(分別記為SCost與MCost),其中多目標(biāo)序列成本模型比單目標(biāo)序列成本模型額外考慮不同目標(biāo)序列之間的成本,具體為

式(3)和式(4)中M和N分別表示特征類別與時間窗口數(shù)目,γ1和γ2為參數(shù),用于調(diào)節(jié)不同類別成本之間的權(quán)重.

構(gòu)建成本模型后,利用動態(tài)規(guī)劃算法可得總成本最小時文本流中各個時間窗口的突發(fā)狀態(tài),具體算法可參考文獻(xiàn)[1?2],處于突發(fā)狀態(tài)的連續(xù)時間窗口即可構(gòu)成突發(fā)區(qū)間,由此實現(xiàn)突發(fā)性檢測任務(wù).

2.3 算法步驟

2.3.1 文本型特征篩選

在文獻(xiàn)[1]的算法基礎(chǔ)上引入文本型(關(guān)鍵詞)特征,詞語的選擇使用文獻(xiàn)[11]中的關(guān)鍵詞選擇算法.計算公式為

WScorei,w表示詞語w在第i個時間窗口的WScore值,dfi,w表示詞語w在第i個時間窗口的文檔頻率,L表示所考慮歷史時間窗口個數(shù),為可調(diào)參數(shù).本文中,一篇文檔指時間窗口內(nèi)的一條微博,故文檔頻率dfi,w即第i個時間窗口內(nèi)包含詞語w的微博條數(shù).

式(5)中分子表示詞語在當(dāng)前時間窗口的文檔頻率,分母計算詞語在歷史時間窗口的出現(xiàn)情況,只有在當(dāng)前窗口出現(xiàn)較多,歷史窗口出現(xiàn)較少的詞語WScore值較大,故該值可較好地反映一個詞語的權(quán)重,選出對于當(dāng)前時間窗口最有代表性的詞語.

在計算得到每個詞語的WScore值后,遞減排序,抽取每個時間窗口Topn個詞語中的名詞作為關(guān)鍵詞候選.隨著時間推進,事件發(fā)生,每個時間窗口對應(yīng)的關(guān)鍵詞候選集隨之變化,關(guān)鍵詞與時間窗口的綁定,將不同事件映射到不同關(guān)鍵詞特征上,消除噪音及事件之間的互相干擾,從而提高識別效果.具體效果如圖3所示.

圖3 關(guān)鍵詞特征作用示意圖Fig.3 The schematic diagram of keyword feature relations

在得到各時間窗口的候選關(guān)鍵詞后,應(yīng)用前述突發(fā)性檢測算法,可以發(fā)現(xiàn)每個候選詞的突發(fā)區(qū)間.

2.3.2 關(guān)鍵詞區(qū)間關(guān)聯(lián)

在得到時間窗口內(nèi)各個候選關(guān)鍵詞的突發(fā)情況后,需將多個關(guān)鍵詞的突發(fā)區(qū)間關(guān)聯(lián),共同決定當(dāng)前時間窗口是否處于突發(fā)狀態(tài),最終得到文本型特征突發(fā)區(qū)間.為實現(xiàn)關(guān)鍵詞突發(fā)區(qū)間的關(guān)聯(lián),本文采用閾值法,即當(dāng)前時間窗口內(nèi)關(guān)鍵詞處于突發(fā)狀態(tài)的比例超過閾值時,則判定該時間窗口處于突發(fā)狀態(tài).使用的計算公式為

其中,zi表示第i個時間窗口的突發(fā)狀態(tài),zi,w表示詞語w在第i個時間窗口的突發(fā)狀態(tài),其值為0或1,λ為閾值,超過此值則代表當(dāng)前時間窗口處于突發(fā)狀態(tài),Γ(·)為指示函數(shù),決定是否處于突發(fā)狀態(tài),KWi表示當(dāng)前時間窗口i的候選關(guān)鍵詞集合.

2.3.3 突發(fā)區(qū)間優(yōu)化

關(guān)鍵詞作為目標(biāo)時,突發(fā)性檢測算法得到的突發(fā)區(qū)間結(jié)果會發(fā)生碎片化現(xiàn)象,原本完整的突發(fā)區(qū)間被分割為數(shù)段小區(qū)間,造成這種現(xiàn)象的原因為關(guān)鍵詞候選較多,較之行為特征易受噪音(非相關(guān)詞)影響.為應(yīng)對此現(xiàn)象,提出兩點假設(shè):1)若候選詞與特定事件相關(guān)度高,則該詞語會被反復(fù)提及,因此其突發(fā)狀態(tài)會維持一段時間,否則,對應(yīng)突發(fā)區(qū)間為噪音的可能性較大,應(yīng)予以舍棄;2)若臨近的兩個被判定為處于突發(fā)狀態(tài)的區(qū)間具有較為相似的關(guān)鍵詞集合,則表明這兩個時間區(qū)間表現(xiàn)出的突發(fā)性與同一事件相關(guān),應(yīng)予以合并,構(gòu)成新的突發(fā)區(qū)間.

上述兩點假設(shè)符合對于事件發(fā)生時用戶發(fā)布內(nèi)容行為的基本判斷.對于第一點,人們在相關(guān)事件發(fā)生時,會以較高頻率提及一些詞語并持續(xù)一段時間,因此,當(dāng)詞語的突發(fā)性區(qū)間過短時,可能只是數(shù)據(jù)的隨機波動或噪音,而突發(fā)性維持較長時間的詞語,則更有可能與用戶關(guān)注的事件相關(guān).對于第二點,在事件發(fā)生時,人們討論事件往往有特定的關(guān)注方面,這樣,同一事件在連續(xù)數(shù)個時間窗口的關(guān)鍵詞集應(yīng)該具有較高重復(fù)性,反之,連續(xù)幾個關(guān)鍵詞集具有較高重復(fù)性的區(qū)間為討論同一事件的概率亦大增,可以進行合并.基于以上兩點假設(shè),可得區(qū)間優(yōu)化算法.

輸入?yún)^(qū)間集合inputIntervals,由關(guān)鍵詞得到的突發(fā)區(qū)間組成,按時間排序,輸出集合outputIntervals為空,每個時間窗口對應(yīng)的關(guān)鍵詞集合為KWi,i為時間窗口索引,突發(fā)區(qū)間對應(yīng)的關(guān)鍵詞集合由突發(fā)區(qū)間對應(yīng)的時間窗口關(guān)鍵詞集合取并集生成,對于inputIntervals集合中的突發(fā)區(qū)間按順序逐個處理,cur,next,third分別指向inputIntervals中當(dāng)前第1,2,3個待處理的突發(fā)區(qū)間.

步驟1.若cur與next之間時間窗口間隔SEP(cur,next)≤λ1,轉(zhuǎn)步驟2,否則轉(zhuǎn)步驟3;

步驟2.若區(qū)間cur的關(guān)鍵詞集合KWcur與下一個突發(fā)區(qū)間next關(guān)鍵詞集合KWnext重合度TOR(cur,next)≥λ2,轉(zhuǎn)步驟4,否則轉(zhuǎn)步驟3;

步驟3.若當(dāng)前突發(fā)區(qū)間長度LEN(cur)≥λ3,轉(zhuǎn)步驟5,否則轉(zhuǎn)步驟6;

步驟4.合并cur與next形成新的cur,next=third,third指向隨后的一個突發(fā)區(qū)間,轉(zhuǎn)步驟1;

步驟5.將cur指向的突發(fā)區(qū)間移入outputIntervals,轉(zhuǎn)步驟6;

步驟6.cur=next,next=third,third指向隨后的突發(fā)區(qū)間,若cur指向inputIntervals中最后一個區(qū)間,則整個算法結(jié)束,此時outputIntervals即為優(yōu)化后的區(qū)間集合,否則轉(zhuǎn)步驟1繼續(xù)執(zhí)行.

區(qū)間優(yōu)化算法流程圖如圖4所示.

上述步驟中對于突發(fā)區(qū)間之間的時間窗口間隔SEP與突發(fā)區(qū)間對應(yīng)關(guān)鍵詞集合重合度TOR的閾值限制保證合并的突發(fā)區(qū)間時間相近,語義相關(guān),以滿足第二點假設(shè);突發(fā)區(qū)間的長度LEN的閾值限制保證只有較長的突發(fā)區(qū)間才能成為事件突發(fā)性,對應(yīng)第一點假設(shè).關(guān)鍵詞集合重合度TOR使用Jaccard系數(shù)衡量.

圖4 區(qū)間優(yōu)化算法流程圖Fig.4 The flow chart of interval optimization algorith m

下面介紹閾值λ1,λ2,λ3的設(shè)定,其中λ1值表示由相同事件引起的突發(fā)區(qū)間的間隔大小(以間隔時間窗口個數(shù)衡量),其值過大會將不同事件突發(fā)區(qū)間合并,造成錯誤,λ3反映事件突發(fā)性維持時間的最小值,其值過小會引入隨機波動,上述兩個參數(shù)均根據(jù)數(shù)據(jù)集取經(jīng)驗值3小時.λ2表示關(guān)鍵詞重合度,反映臨近突發(fā)區(qū)間語義相似度,本文取值為0.5.

2.3.4 關(guān)鍵詞區(qū)間與社交行為區(qū)間關(guān)聯(lián)

至此,得到分別根據(jù)社交行為與關(guān)鍵詞特征得到的突發(fā)區(qū)間,接下來介紹兩組結(jié)果的關(guān)聯(lián)策略,以得到最終的突發(fā)區(qū)間.本文提出三種方案以供實驗.

交集策略(Conjunct):如果一個突發(fā)區(qū)間與其他突發(fā)區(qū)間不重合,則忽略;如果一個突發(fā)區(qū)間與某一區(qū)間重合,則取交集.

其中,si,ei表示突發(fā)區(qū)間i的開始與結(jié)束時間窗口索引值.

并集策略(Disjunct):如果一個突發(fā)區(qū)間與其他突發(fā)區(qū)間不重合,則其單獨構(gòu)成一個突發(fā)區(qū)間;如果一個突發(fā)區(qū)間與某一區(qū)間重合,則取并集.

混合策略(Hybrid):如果一個突發(fā)區(qū)間與其他突發(fā)區(qū)間不重合,則其單獨構(gòu)成一個突發(fā)區(qū)間;如果一個突發(fā)區(qū)間與某一區(qū)間重合,則取交集.

例如,現(xiàn)有關(guān)鍵詞區(qū)間(以窗口的突發(fā)狀態(tài)序列表示,0值表示對應(yīng)窗口不發(fā)生突發(fā)性,1表示發(fā)生突發(fā)性)“001111000000”,社交行為區(qū)間“0111100011 10”.使用交集策略結(jié)果為“001110000000”;使用并集策略結(jié)果為“011111001110”;使用混合策略的結(jié)果為 “001110001110”.

當(dāng)兩類特征發(fā)現(xiàn)的突發(fā)區(qū)間區(qū)別不大時,交集策略與并集策略結(jié)果差異較小,當(dāng)兩類特征發(fā)現(xiàn)的突發(fā)區(qū)間區(qū)別較大時,交集策略與并集策略結(jié)果差異較大,因此可以根據(jù)交集策略與并集策略的實驗結(jié)果判斷兩類特征對于發(fā)現(xiàn)事件突發(fā)性的作用是否相同,從而驗證引入的文本特征是否可以彌補行為特征的缺陷,發(fā)現(xiàn)隱式事件突發(fā)性.

經(jīng)過上述步驟,得到最終的事件突發(fā)區(qū)間集合.完整的事件突發(fā)性檢測方法流程如圖5所示.

3 實驗

本節(jié)介紹實驗細(xì)節(jié),討論不同算法的實驗結(jié)果并分析原因;針對本文提出算法,對比使用不同關(guān)聯(lián)策略時的實驗結(jié)果,分析原因;指出單獨使用文本特征時效果較差的原因;解釋綜合文本與社交行為特征的算法改善事件突發(fā)性檢測效果的機制,并結(jié)合實例進行分析.

3.1 數(shù)據(jù)集

微博3http://www.weibo.com/是一種通過關(guān)注機制分享簡短實時信息的廣播式的社交網(wǎng)絡(luò)平臺,已成為目前最流行的社交平臺之一[12].本文實驗數(shù)據(jù)集以真實微博數(shù)據(jù)構(gòu)建,通過微博提供的搜索及高級搜索功能,利用網(wǎng)絡(luò)爬蟲程序定時爬取微博數(shù)據(jù),構(gòu)建實驗數(shù)據(jù)集.根據(jù)搜索關(guān)鍵字的不同,共獲得兩個數(shù)據(jù)集.

3.1.1 數(shù)據(jù)集1

以“恒大”4中國職業(yè)足球隊名稱,亦是企業(yè)恒大集團簡稱,涉及地產(chǎn)、酒店、體育及文化等產(chǎn)業(yè).作為查詢關(guān)鍵字,利用爬蟲程序爬取微博搜索頁面結(jié)果,定期(10分鐘)執(zhí)行,共獲得微博165644條,時間跨度為2015年9月16日0時～2015年11月3日0時,共48天,1152小時.在獲得的微博中,原創(chuàng)微博占比56.83%;轉(zhuǎn)發(fā)微博占比43.17%;內(nèi)嵌網(wǎng)址微博占比41.72%.

圖5 社交網(wǎng)絡(luò)中事件突發(fā)性檢測方案流程示意圖Fig.5 The flow diagram of event-related burst detection in social networks

3.1.2 數(shù)據(jù)集2

以“爸爸去哪兒”5一檔親子類綜藝真人秀節(jié)目名稱,節(jié)目有中國版與韓國版.作為查詢關(guān)鍵字,爬取微博,共獲得微博154366條,時間跨度為2015年9月22日0時～2015年11月7日0時,共46天,1104小時.在獲得的微博中,原創(chuàng)微博占比50.41%;轉(zhuǎn)發(fā)微博占比49.59%;內(nèi)嵌網(wǎng)址微博占比27.07%.

以上數(shù)據(jù)集分別記作HD與BA.數(shù)據(jù)集HD與BA涵蓋體育與娛樂類內(nèi)容,涉及人們關(guān)注的主要方面,因此數(shù)據(jù)集選取具有普遍性.關(guān)于數(shù)據(jù)集突發(fā)區(qū)間的確定,本文爬取了主要門戶網(wǎng)站(包括新浪、搜狐、網(wǎng)易)的相關(guān)專題新聞及搜索引擎(百度)特定關(guān)鍵詞加時間的搜索結(jié)果,根據(jù)這兩類數(shù)據(jù),人工選擇出較為熱門的事件,結(jié)合真實事件發(fā)生的時間區(qū)間,確定事件突發(fā)區(qū)間的開始時間與結(jié)束時間,作為實驗評價時的真實突發(fā)區(qū)間集合.

3.2 評價指標(biāo)

本文使用文獻(xiàn)[1]中的評價指標(biāo),突發(fā)區(qū)間重合率(Bursty interval overlap ration,BIOR),定義如下:

其中,f是一個突發(fā)區(qū)間,Δl(f,f′)是f′與f重合的長度,L(f)是突發(fā)區(qū)間f的長度.χ是一組突發(fā)區(qū)間,BIOR用于衡量一組突發(fā)區(qū)間χ對于突發(fā)區(qū)間f的覆蓋比例.由此可以定義準(zhǔn)確率(Precision)、召回率(Recall)和F值,計算公式如下:

其中,M為通過相關(guān)候選算法發(fā)現(xiàn)的突發(fā)區(qū)間集合,B是真實突發(fā)區(qū)間集合,Mf是在集合M中與f重合的突發(fā)區(qū)間集合.Γ(·)是指示函數(shù),當(dāng)且僅當(dāng)條件為真時函數(shù)值為1.

3.3 對比算法

本文實驗的三種算法,依次為:

SingleBurstDetector:使用概率分布及自動機理論構(gòu)建突發(fā)性檢測模型[1],不同突發(fā)狀態(tài)對應(yīng)分布的參數(shù)不同,因而不同狀態(tài)時生成同一特征序列的概率大小不同,即成本不同,通過最小化成本可得最優(yōu)的突發(fā)狀態(tài)序列,進而得到突發(fā)區(qū)間.

MultiBurstDetector:原理同SingleBurstDetector,但輸入為多類行為特征,方法考慮了不同特征的突發(fā)情況,可以應(yīng)對噪音對單一特征的干擾[1].

CombinedDetector:這是本文提出的方法,綜合了關(guān)鍵詞特征與社交行為特征,能夠發(fā)現(xiàn)隱式事件突發(fā)性,提升算法性能.

上述三種方法分別簡記為Single、Multi和Comb.

3.4 實驗步驟

3.4.1 數(shù)據(jù)預(yù)處理

預(yù)處理階段包括分詞、去停用詞和詞性標(biāo)注等操作,針對分詞和詞性標(biāo)注在微博環(huán)境中效果不佳的問題,可利用分詞器提供的新詞發(fā)現(xiàn)功能以及引入人工構(gòu)建的外部字典解決.然后對微博數(shù)據(jù)按原創(chuàng)、轉(zhuǎn)發(fā)、內(nèi)嵌網(wǎng)址、是否提到其他用戶(含“@”符號)進行分類.將微博按時間排序,時間窗口設(shè)置為1小時,統(tǒng)計每個窗口內(nèi)各類別特征出現(xiàn)的頻數(shù),構(gòu)成前述行為流(Activity stream).本文使用5種行為流,分別為:微博總數(shù)(代表用戶發(fā)布行為)、原創(chuàng)微博(代表用戶原創(chuàng)內(nèi)容發(fā)布行為)、轉(zhuǎn)發(fā)微博(代表轉(zhuǎn)發(fā)行為)、內(nèi)嵌網(wǎng)址微博(代表引入網(wǎng)址行為)、含“@”符號微博(代表提到其他用戶行為),此設(shè)置與文獻(xiàn)[1]相同.計算各時間窗口內(nèi)詞語的WScore值,提取Topn詞語中名詞性詞語作為候選詞,構(gòu)建各個候選詞的Term stream.

3.4.2 計算事件突發(fā)性

對以上Activity stream,分別應(yīng)用Single,Multi和Comb算法,其中,Single算法使用單一行為特征,Multi和Comb算法同時使用多種行為特征,得到事件突發(fā)性結(jié)果;對于Term stream,應(yīng)用單目標(biāo)突發(fā)區(qū)間檢測算法(Single)6此處使用單目標(biāo)算法,是由于多目標(biāo)算法基于假設(shè):在特定事件發(fā)生時,不同行為具有一致的突發(fā)模式,而詞語由于候選集合較大,語義多樣,相關(guān)性無法保證,因此不適用多目標(biāo)算法.進行突發(fā)性檢測,得到各個詞語的事件突發(fā)性區(qū)間,再將其與多類別行為特征的事件突發(fā)性結(jié)果關(guān)聯(lián),進行區(qū)間優(yōu)化后,最終得到Comb算法的突發(fā)性檢測結(jié)果.

3.4.3 實驗對比

根據(jù)前述評價指標(biāo)計算各個算法的準(zhǔn)確率、召回率和F值,比較不同算法的結(jié)果,分析各個算法的效果及特點.

3.5 結(jié)果及分析

運行前述算法,實驗測試不同參數(shù)設(shè)置,此處僅列出最優(yōu)結(jié)果,如表1和表2所示.各個突發(fā)性檢測算法涉及的參數(shù)較多,在此不再列出,僅給出Comb算法最優(yōu)結(jié)果時的參數(shù)設(shè)置,以供參考,n=5/5,γ1=1.9/1.9,γ2=10.5/11.5,ρ=3/8,L=5/5,λ=0.6/0.7,λ1=λ3=3,λ2=0.5(兩個數(shù)據(jù)集的參數(shù)設(shè)置以“/”分隔).針對Single算法,本文測試了前述5種社交行為,包括微博總數(shù)、原創(chuàng)、轉(zhuǎn)發(fā)、內(nèi)嵌網(wǎng)址、含“@”符號微博(分別記為all,post,repost,url,user),這5種特征基本覆蓋了典型的社交行為,具有普遍意義.對于Multi算法,同時使用3種行為特征(post,repost,url)進行實驗,F值指標(biāo)顯示Multi算法優(yōu)于前兩種算法,印證了文獻(xiàn)[1]中的相關(guān)結(jié)論.對于Comb算法,我們在多特征的基礎(chǔ)上測試前述3種關(guān)聯(lián)策略.實驗中也驗證了單獨使用文本特征時的效果,如表3所示.

表1 數(shù)據(jù)集HD上各算法實驗結(jié)果Table 1 The experimental results of different algorithms on dataset HD

表2 數(shù)據(jù)集BA上各算法實驗結(jié)果Table 2 The experimental results of different algorithms on dataset BA

表3 單獨使用關(guān)鍵詞特征時實驗結(jié)果Table 3 The experimental results with only keyword features

對比不同算法以及同一算法使用不同特征或關(guān)聯(lián)策略時的實驗結(jié)果,可得到一系列有價值的結(jié)論.

1)Single算法實驗結(jié)果分析.該算法引入了區(qū)分噪音與事件突發(fā)性的平滑成本等措施,大幅提升了事件突發(fā)性檢測的準(zhǔn)確率,在兩組數(shù)據(jù)集上準(zhǔn)確率均較高,但其召回率最低,并且算法準(zhǔn)確率波動性很大.造成此類結(jié)果的原因,在于不同行為與事件突發(fā)性的關(guān)系不同,當(dāng)某些事件發(fā)生與某一行為關(guān)系緊密時,則利用此行為特征檢測到的突發(fā)性基本都與這些事件有關(guān),即算法發(fā)現(xiàn)的突發(fā)區(qū)間是真實事件的突發(fā)區(qū)間的概率較大,此時算法的準(zhǔn)確率(P值)就會很高;但當(dāng)該行為與某類事件關(guān)系不緊密時,此類事件發(fā)生,對應(yīng)行為變化不明顯,則利用該行為進行突發(fā)性檢測,就會造成漏檢,進而拉低召回率(R值).因此,基于單一行為特征算法的效果優(yōu)劣很大程度上取決于使用的行為特征與事件的關(guān)系.圖1也可以證實此結(jié)論:在50～55區(qū)間內(nèi),事件發(fā)生(恒大集團與英國相關(guān)機構(gòu)合作),微博總數(shù)與轉(zhuǎn)發(fā)微博都有明顯的上升,而原創(chuàng)微博與內(nèi)嵌網(wǎng)址微博并無明顯變化,說明不同行為對事件的反應(yīng)不同.

2)Multi算法實驗結(jié)果分析.該算法的準(zhǔn)確率較Single算法在兩個數(shù)據(jù)集上均有所降低,但其彌補了Single算法召回率過低的缺陷,從而在衡量算法整體性能的F值指標(biāo)上優(yōu)于Single算法.分析Multi算法召回率提升的原因,在于多種行為特征加強了行為特征與事件的關(guān)系,避免單一行為特征由于與事件相關(guān)性不足或隨機波動造成的漏檢,因而召回率上升;而準(zhǔn)確率的下降是由于該算法在根據(jù)每個單一特征突發(fā)性檢測結(jié)果生成最終的突發(fā)區(qū)間時使用了并集策略[1],即只要一個特征將當(dāng)前時間窗口標(biāo)注為突發(fā)狀態(tài),就認(rèn)為這個時間窗口產(chǎn)生突發(fā)性,因而多類特征的噪音都會引入到Multi算法結(jié)果中來,使其準(zhǔn)確率下降.

3)不同關(guān)聯(lián)策略實驗結(jié)果分析.針對Comb算法,本文測試了3種關(guān)聯(lián)策略.由表1和表2可知,在進行文本特征與社交行為特征融合發(fā)現(xiàn)事件突發(fā)性時,采用并集(Disjunct)處理是進行區(qū)間關(guān)聯(lián)的最優(yōu)策略.分析不同的關(guān)聯(lián)策略,可以看出,交集(Conjunct)策略保留文本特征與社交行為特征共同的結(jié)果,因此獲得優(yōu)于Multi算法的準(zhǔn)確率,但是由于忽略了僅由單一類別特征得到的結(jié)果,召回率較差;并集策略與混合(Hybrid)策略均保留僅由單一類別特征得到的結(jié)果,因此實現(xiàn)了較高的召回率,而上述兩種策略的準(zhǔn)確率取決于關(guān)聯(lián)前兩類特征分別的準(zhǔn)確率,因而準(zhǔn)確率有升有降.并集策略取得最優(yōu),而交集結(jié)果較差說明,兩類特征在進行事件突發(fā)性檢測時的作用并不相同,后文給出具體分析.

4)單獨使用文本特征實驗結(jié)果分析.由表1、表2和表3對比可知,未進行融合,單獨使用文本特征時,實驗結(jié)果較使用行為特征的差,這是因為詞語候選集龐大,噪音詞較多,造成使用文本特征發(fā)現(xiàn)的突發(fā)區(qū)間較短,易被噪音信息割裂,引入噪音區(qū)間,發(fā)生前述的碎片化現(xiàn)象,導(dǎo)致結(jié)果較差.

5)文本與行為特征特點及融合效果分析.通過對比單獨使用文本特征與行為特征所發(fā)現(xiàn)的突發(fā)區(qū)間,我們發(fā)現(xiàn):a)行為特征屬于宏觀特征,對于引起較高關(guān)注的事件,才會表現(xiàn)出較為明顯的對應(yīng)行為的突發(fā)性(必須有大量的用戶參與,才能造成行為的突發(fā)表現(xiàn)),即行為特征對于事件的弱突發(fā)性敏感度不夠.以用戶行為作為特征時發(fā)現(xiàn)的突發(fā)區(qū)間對應(yīng)的事件關(guān)注度普遍較高,并且突發(fā)性維持的時間較長.b)文本特征屬于微觀特征,對在小范圍內(nèi)引起有限突發(fā)性的事件也會有所反映,例如用戶單位時間內(nèi)發(fā)布微博的數(shù)目波動很小,即發(fā)布行為突發(fā)性弱,此時以該行為進行突發(fā)性檢測容易失效,但只要有部分微博集中討論同一事件,則也會表現(xiàn)出相關(guān)詞語的突發(fā)性,即文本特征對事件突發(fā)性更為敏感,能夠發(fā)現(xiàn)事件的弱突發(fā)性(真隱式事件突發(fā)性).另外由于本文提出的方法將不同事件與不同的關(guān)鍵詞綁定,消除了突發(fā)程度高的事件對于突發(fā)程度低的事件的影響,從而解決假隱式事件突發(fā)性問題.綜上,兩類特征對于發(fā)現(xiàn)的事件突發(fā)性類型各有側(cè)重,社交行為特征容易忽略突發(fā)程度低的事件,而文本特征會很好地彌補此缺陷,因此本文提出的融合兩類特征的綜合方法具有較好的效果.

6)案例分析.結(jié)合上述分析,回顧圖1,具體展示本文所述方法的作用效果.圖1呈現(xiàn)了兩個引起突發(fā)性的事件A和事件B,事件A是一場足球比賽,事件B是恒大集團與英國相關(guān)機構(gòu)合作,關(guān)注同一行為特征時,事件A的突發(fā)程度遠(yuǎn)高于事件B,如圖6左側(cè)所示7出于圖表直觀考慮,圖6僅為模擬圖,具體數(shù)值與真實情況并不對應(yīng)..當(dāng)使用關(guān)鍵詞特征時,由于事件A和事件B不同的關(guān)鍵詞,如表4所示(刪除線標(biāo)注為查詢詞“恒大”),事件A的關(guān)鍵詞在事件B發(fā)生時不會突發(fā),反之亦然,如圖6右側(cè)所示,關(guān)注文本特征時,避免了事件之間的影響,發(fā)現(xiàn)由事件B所引起的隱式事件突發(fā)性,從而提高事件突發(fā)性檢測的性能.

4 相關(guān)工作

突發(fā)性檢測問題,最早在文獻(xiàn)[2]中提出,作者根據(jù)電子郵件文本流中話題出現(xiàn)時郵件數(shù)量陡增的現(xiàn)象,引出流式數(shù)據(jù)中突發(fā)性的形式化表述,并探討了流式數(shù)據(jù)中的層次結(jié)構(gòu)問題.作者借助自動機的思想,將文本流數(shù)據(jù)根據(jù)時間切分為時間窗口,根據(jù)突發(fā)程度及歷史信息確定當(dāng)前時間窗口的狀態(tài),并對突發(fā)狀態(tài)的生成與轉(zhuǎn)換成本進行建模,利用動態(tài)規(guī)劃方法求解,得到各個時間窗口的突發(fā)狀態(tài).文獻(xiàn)[4]使用卡方測試的方法,進行詞語的突發(fā)性檢測,再對發(fā)現(xiàn)的突發(fā)詞語進行聚類,獲得數(shù)據(jù)集的事件話題.文獻(xiàn)[13]提出了無需調(diào)整參數(shù)的概率方法,用于在報紙文章中尋找不同時間窗口的突發(fā)特征,確定突發(fā)事件的熱度區(qū)間.文獻(xiàn)[14]針對時序數(shù)據(jù),提出基于概率統(tǒng)計模型的變化節(jié)點發(fā)現(xiàn)方法.以上研究均在傳統(tǒng)文本(電子郵件、新聞文本和科研論文等)中進行.

圖6 Comb方法作用示意圖Fig.6 The schematic diagram of method Comb

表4 事件A,B的關(guān)鍵詞提取結(jié)果Table 4 Extracted keywords of event A and B

隨著社交網(wǎng)絡(luò)的興起,科研人員開始進行社交網(wǎng)絡(luò)中突發(fā)性檢測與應(yīng)用的工作.文獻(xiàn)[1,6?10,15]基于Twitter文本流,開展關(guān)于在社交網(wǎng)絡(luò)中的突發(fā)事件與話題的發(fā)現(xiàn).其中,文獻(xiàn)[15]應(yīng)用了詞語的突發(fā)性,但與本文的研究問題有所區(qū)別,且其僅使用了詞語,并未綜合社交行為信息;文獻(xiàn)[6]基于事件發(fā)生時頻數(shù)特征的上升下降模式確定事件突發(fā)區(qū)間,該方法易受噪音(例如廣告信息)與多事件交錯的影響,整體效果有待提高;文獻(xiàn)[7]著重利用社交網(wǎng)絡(luò)中的鏈接異常進行話題發(fā)現(xiàn),使用了概率方法進行事件發(fā)生的預(yù)測,是基于非內(nèi)容特征進行社交網(wǎng)絡(luò)挖掘的典型示例;文獻(xiàn)[8]使用情感符號作為特征,利用情感突發(fā)趨勢發(fā)現(xiàn)事件;引入鏈接與情感符號的行為與用戶的使用習(xí)慣緊密相關(guān),但不是所有事件相關(guān)的社交文本都包含此類特征,限定了這兩類方法的使用范圍;文獻(xiàn)[9]研究了異構(gòu)網(wǎng)絡(luò)挖掘問題,使用社交網(wǎng)絡(luò)中的多種信息構(gòu)建異構(gòu)網(wǎng)絡(luò),將每個特征節(jié)點視作傳感器,利用統(tǒng)計方法統(tǒng)一不同屬性的異常變化情況,最后使用改進的圖掃描算法發(fā)現(xiàn)變化最大的子圖,實現(xiàn)突發(fā)事件的檢測,發(fā)現(xiàn)事件的形式為(地點、日期),將研究任務(wù)分為預(yù)測(日期在真實事件發(fā)生之前)及發(fā)現(xiàn)(日期在真實事件發(fā)生之后),在事件發(fā)生前后7天內(nèi)的結(jié)果都視作發(fā)現(xiàn)事件,但并未強調(diào)對于事件突發(fā)區(qū)間的覆蓋,而本文研究的是如何發(fā)現(xiàn)事件發(fā)生時導(dǎo)致的突發(fā)區(qū)間,目標(biāo)是盡量使算法得到的區(qū)間覆蓋真實事件發(fā)生的區(qū)間并找到足夠多的真實區(qū)間,因此與本文研究問題有所區(qū)別;文獻(xiàn)[10]研究突發(fā)性事件的熱度預(yù)測問題,考慮了內(nèi)容特征、用戶影響力與歷史信息,對突發(fā)事件進行流行度預(yù)測,流行度預(yù)測是在已知事件發(fā)生的情況下進行的,可以在任意時刻開始,作者并不關(guān)注事件的開始與結(jié)束時間,該論文方法不能直接應(yīng)用到事件突發(fā)性發(fā)現(xiàn)任務(wù)中;文獻(xiàn)[1]改進了文獻(xiàn)[2]中基于自動機與概率方法的突發(fā)性檢測方法,首次利用社交網(wǎng)絡(luò)中的行為信息進行事件突發(fā)性檢測,引入去噪措施,指出單一行為特征在發(fā)現(xiàn)事件突發(fā)性時的不穩(wěn)定性,提出利用多類行為特征的檢測方法,在大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)集上驗證了其有效性.本文基于文獻(xiàn)[1]的算法,添加文本型(關(guān)鍵詞)信息,實現(xiàn)了社交行為與內(nèi)容兩方面信息的綜合,有利于消除事件之間的相互影響,可以發(fā)現(xiàn)前述的隱式事件突發(fā)性,從而更為完整地發(fā)現(xiàn)突發(fā)事件對應(yīng)的時間區(qū)間,改善相關(guān)算法性能.

突發(fā)性檢測算法最初用來挖掘文本流突發(fā)性背后蘊含的真實事件,因此本文也涉及事件檢測領(lǐng)域.事件檢測,最早要追溯到美國國防部發(fā)起的TDT(Topic detection and tracking)項目[16].TDT項目中事件檢測分為回溯事件檢測與新事件檢測[17],主要處理文本和音頻等傳統(tǒng)新聞媒體.最初使用的方法以文本聚類算法居多,后來,隨著以LDA[18]為代表的主題模型的提出,基于貝葉斯概率推斷的話題發(fā)現(xiàn)算法成為事件檢測領(lǐng)域研究的主流.而隨著Facebook、Twitter和微博等新型社交媒體的興起,以社交網(wǎng)絡(luò)為研究對象的事件檢測成為人們關(guān)注的熱點.文獻(xiàn)[19]將突發(fā)性特征引入到傳統(tǒng)的向量空間模型中,使文本表示既包含語義信息又包含時間信息,從而更好地進行事件檢測,但該模型僅在新聞文本中進行了實驗,應(yīng)用到社交媒體的效果未知.文獻(xiàn)[20]提出應(yīng)用于Twitter類短文本的話題發(fā)現(xiàn)算法,并利用該算法對傳統(tǒng)新聞媒體與社交媒體進行話題分析,比較二者之間的異同點,但僅考慮文本內(nèi)容分析,未涉及時間信息與事件突發(fā)性問題.文獻(xiàn)[21]將事件發(fā)生時的突發(fā)性特點融入一個變形的概率圖模型中,實現(xiàn)對突發(fā)事件的發(fā)現(xiàn),側(cè)重于對所發(fā)現(xiàn)事件的語義描述.文獻(xiàn)[22]考慮社交網(wǎng)絡(luò)中提供的地理標(biāo)注服務(wù),借助統(tǒng)計主題建模與稀疏編碼技術(shù),構(gòu)建帶位置信息的話題發(fā)現(xiàn)模型,探索事件、話題的發(fā)生與地理位置的關(guān)系.文獻(xiàn)[23]利用信號處理中的小波分析方法篩選詞語,再應(yīng)用基于模塊度的圖切割方法聚類詞語,用于發(fā)現(xiàn)社交網(wǎng)絡(luò)中的事件.文獻(xiàn)[24]提出了一種新的數(shù)據(jù)結(jié)構(gòu),處理不斷到來的在線式數(shù)據(jù),并成功應(yīng)用于Twitter趨勢發(fā)現(xiàn)及總結(jié)中;作者綜合數(shù)量與內(nèi)容變化信息,構(gòu)建話題切換的檢測模型,用來跟蹤話題的演化情況,此處的話題切換僅關(guān)注話題發(fā)生變化的起始時間節(jié)點,并未探討如何確定話題的結(jié)束時間節(jié)點.文獻(xiàn)[25?26]均采用監(jiān)督分類模型區(qū)分事件信息與非事件信息,從而發(fā)現(xiàn)目標(biāo)事件,但此類方法需要人工創(chuàng)建訓(xùn)練數(shù)據(jù)集,這在一定程度上限制其應(yīng)用領(lǐng)域的擴展.文獻(xiàn)[27]使用文本挖掘及網(wǎng)絡(luò)分析技術(shù),挖掘事件發(fā)生時的重點要素(例如時間和地點等),為輿情監(jiān)控提供指導(dǎo).文獻(xiàn)[28]基于在線LDA模型分析各時間片內(nèi)子話題的關(guān)聯(lián),定義話題的產(chǎn)生、消亡、繼承、分裂、合并等演化類型,構(gòu)建了話題的內(nèi)容與強度演化模型.

本文工作也屬于社交網(wǎng)絡(luò)挖掘范疇.在該方向,除了進行事件檢測的研究之外,科研人員也開展了其他各式各樣的挖掘工作.文獻(xiàn)[29]分析事件中公眾的情感走向;文獻(xiàn)[30]利用社交網(wǎng)絡(luò)的情感分析預(yù)測股市走勢.文獻(xiàn)[11]探討各類話題發(fā)現(xiàn)算法的優(yōu)劣,并分析數(shù)據(jù)預(yù)處理等階段對話題發(fā)現(xiàn)最終結(jié)果的影響.文獻(xiàn)[31]關(guān)注社交網(wǎng)絡(luò)中影響力分析領(lǐng)域,詳細(xì)介紹各種影響力度量方法,以及影響力分析在意見領(lǐng)袖和影響力最大化問題中的應(yīng)用.文獻(xiàn)[32]提出一種新型的社交網(wǎng)絡(luò)節(jié)點表示形式,可以有效提高各類社交網(wǎng)絡(luò)挖掘任務(wù)的效果.文獻(xiàn)[33]借助LDA模型構(gòu)建語義社會網(wǎng)絡(luò),使用標(biāo)簽傳播算法進行社區(qū)發(fā)現(xiàn),較好地解決了語義重疊社區(qū)的發(fā)現(xiàn)問題.文獻(xiàn)[34]提出半監(jiān)督算法,融合先驗信息,解決數(shù)據(jù)缺失與噪音環(huán)境中的社區(qū)發(fā)現(xiàn)問題.文獻(xiàn)[35]利用基于線性回歸的混合算法分析內(nèi)容在社交網(wǎng)絡(luò)中的傳播過程.

5 結(jié)論

通過對相關(guān)方法的分析與實驗可得,單純依靠社交行為特征,不足以區(qū)別事件交錯與噪音對于事件突發(fā)性檢測帶來的干擾,會引起隱式事件突發(fā)性的漏檢問題,因此在多次實驗的基礎(chǔ)上,本文引入文本型(關(guān)鍵詞)信息,提出了一個綜合方案,將每個時間窗口與不同的關(guān)鍵詞集合綁定,間接將事件映射到不同的關(guān)鍵詞特征空間,從而避免事件交錯及噪音的影響,在得到由關(guān)鍵詞特征確定的突發(fā)區(qū)間后,將其與由社交行為特征得到的突發(fā)區(qū)間關(guān)聯(lián),得到最終的事件突發(fā)性.在真實數(shù)據(jù)集上的實驗結(jié)果表明,加入關(guān)鍵詞信息的事件突發(fā)性檢測算法能有效改善相關(guān)算法的性能,提升事件突發(fā)性檢測任務(wù)的效果,驗證了該算法的有效性.

最后,指出一些當(dāng)前工作有待改進與提高之處,供各位讀者參考.

1)在進行突發(fā)區(qū)間計算時,本文借用了前人提出的算法,但算法并不完全適合,會出現(xiàn)區(qū)間碎片化問題.在多目標(biāo)序列建模時,其他作者僅假設(shè)所選目標(biāo)之間具有相關(guān)性,對于語義變化巨大的詞語,并不適用,因此,在進行多詞語序列突發(fā)性關(guān)聯(lián)時,可以嘗試構(gòu)建考慮詞語語義關(guān)系的突發(fā)性檢測模型.

2)在方法設(shè)計部分,本文探討了多事件緊鄰帶來的檢測困難,而對于可能的重疊事件突發(fā)性,現(xiàn)有算法僅視作一次突發(fā)性,無法區(qū)別不同事件以及分析事件之間的相互影響,因此有必要進行語義分析,構(gòu)建統(tǒng)一內(nèi)容特征與非內(nèi)容特征的事件模型,以便開展事件檢測與跟蹤工作.

3)本文僅利用行為與文本特征發(fā)現(xiàn)事件相關(guān)突發(fā)性,但對于行為、文本與事件關(guān)系的研究不夠充分,需要細(xì)化,例如事件與行為的關(guān)系,事件發(fā)生時的群體行為反應(yīng),行為與文本關(guān)聯(lián)策略的選擇等問題均值得進一步研究.

References

1 Zhao W X,Shu B H,Jiang J,Song Y,Yan H F,Li X M.Identifying event-related bursts via social media activities.In:Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning.Stroudsburg,PA,USA:ACL,2012.1466?1477

2 Kleinberg J.Bursty and hierarchical structure in streams.Data Mining and Knowledge Discovery,2003,7(4):373?397

3 Swan R,Allan J.Extracting signi ficant time varying features from text.In:Proceedings of the 8th International Conference on Information and Knowledge Management.New York,NY,USA:ACM,1999.38?45

4 Swan R,Allan J.Automatic generation of overview timelines.In:Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York,NY,USA:ACM,2000.49?56

5 Mei Q Z,Zhai C X.Discovering evolutionary theme patterns from text:an exploration of temporal text mining.In:Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.New York,NY,USA:ACM,2005.198?207

6 Marcus A,Bernstein M S,Badar O,Karger D R,Madden S,Miller R C.Twitinfo:aggregating and visualizing microblogs for event exploration.In:Proceedings of the 2011 SIGCHI Conference on Human Factors in Computing Systems.New York,NY,USA:ACM,2011.227?236

7 Takahashi T,Tomioka R,Yamanishi K.Discovering emerging topics in social streams via link-anomaly detection.IEEE Transactions on Knowledge and Data Engineering,2014,26(1):120?130

8 Zhang Lu-Min,Jia Yan,Zhou Bin,Zhao Jin-Hui,Hong Feng.Online bursty events detection based on emoticons.Chinese Journal of Computers,2013,36(8):1659?1667(張魯民,賈焰,周斌,趙金輝,洪鋒.一種基于情感符號的在線突發(fā)事件檢測方法.計算機學(xué)報,2013,36(8):1659?1667)

9 Chen F,Neill D B.Non-parametric scan statistics for event detection and forecasting in heterogeneous social media graphs.In:Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,NY,USA:ACM,2014.1166?1175

10 Zhang X M,Li Z J,Chao W H,Xia J L.Popularity prediction of burst event in microblogging.In:Proceedings of the 15th International Conference on Web-Age Information Management.Macau,China:Springer,2014.484?487

11 Aiello L M,Petkos G,Martin C,Corney D,Papadopoulos S,Skraba R,Goker A,Kompatsiaris I,Jaimes A.Sensing trending topics in twitter.IEEE Transactions on Multimedia,2013,15(6):1268?1282

12 Feng Chong,Shi Ge,Guo Yu-Hang,Gong Jing,Huang He-Yan.An entity linking method for microblog based on semantic categorization by word embeddings.Acta Automatica Sinica,2016,42(6):915?922(馮沖,石戈,郭宇航,龔靜,黃河燕.基于詞向量語義分類的微博實體鏈接方法.自動化學(xué)報,2016,42(6):915?922)

13 Fung G P C,Yu J X,Yu P S,Lu H J.Parameter free bursty events detection in text streams.In:Proceedings of the 31st International Conference on Very Large Data Bases.New York,NY,USA:ACM,2005.181?192

14 Urabe Y,Yamanishi K,Tomioka R,Iwai H.Real-time change-point detection using sequentially discounting normalized maximum likelihood coding.In:Proceedings of the 15th Paci fic-Asia Conference on Advances in Knowledge Discovery and Data Mining.Berlin,Heidelberg,Germany:Springer-Verlag,2011.185?197

15 Mathioudakis M,Koudas N.TwitterMonitor:trend detection over the twitter stream.In:Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data.New York,NY,USA:ACM,2010.1155?1158

16 Allan J,Carbonell J G,Doddington G,Yamron J,Yang Y M.Topic detection and tracking pilot study final report.In:Proceedings of the 1998 DARPA Broadcast News Transcription and Understanding Workshop.Lansdowne,Virginia,USA:DARPA,1998.194?218

17 Atefeh F,Khreich W.A survey of techniques for event detection in twitter.Computational Intelligence,2015,31(1):132?164

18 Blei D M,Ng A Y,Jordan M I.Latent dirichlet allocation.Journal of Machine Learning Research,2003,3:993?1022

19 Zhao W X,Chen R S,Fan K,Yan H F,Li X M.A novel burst-based text representation model for scalable event detection.In:Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics.Stroudsburg,PA,USA:ACL,2012,2:43?47

20 Zhao W X,Jiang J,Weng J S,He J,Lim E P,Yan H F,Li X M.Comparing twitter and traditional media using topic models.In:Proceedings of the 33rd European Conference on Advances in Information Retrieval.Berlin,Heidelberg,Germany:Springer-Verlag,2011.338?349

21 Diao Q M,Jiang J,Zhu F D,Lim E P.Finding bursty topics from microblogs.In:Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics.Stroudsburg,PA,USA:ACL,2012,1:536?544

22 Hong L J,Ahmed A,Gurumurthy S,Smola A J,Tsioutsiouliklis K.Discovering geographical topics in the twitter stream.In:Proceedings of the 21st International Conference on World Wide Web.New York,NY,USA:ACM,2012.769?778

23 Weng J S,Lee B S.Event detection in twitter.In:Proceedings of the 2011 International AAAI Conference on Web and Social Media.Palo Alto,CA,USA:AAAI,2011.401?408

24 Wang Z H,Shou L D,Chen K,Chen G,Mehrotra S.On summarization and timeline generation for evolutionary tweet streams.IEEE Transactions on Knowledge and Data Engineering,2015,27(5):1301?1315

25 Sakaki T,Okazaki M,Matsuo Y.Earthquake shakes twitter users:real-time event detection by social sensors.In:Proceedings of the 19th International Conference on World Wide Web.New York,NY,USA:ACM,2010.851?860

26 Becker H,Naaman M,Gravano L.Beyond trending topics:real-world event identi fication on twitter.In:Proceedings of the 2011 International AAAI Conference on Web and Social Media.Palo Alto,CA,USA:AAAI,2011.438?441

27 Fu Ju-Lei,Liu Wen-Li,Zheng Xiao-Long,Fan Ying,Wang Shou-Yang.Analyzing the characteristics of“east Turkistan”activities using text mining and network analysis.Acta Automatica Sinica,2014,40(11):2456?2468(付舉磊,劉文禮,鄭曉龍,樊瑛,汪壽陽.基于文本挖掘和網(wǎng)絡(luò)分析的“東突”活動主要特征研究.自動化學(xué)報,2014,40(11):2456?2468)

28 Hu Yan-Li,Bai Liang,Zhang Wei-Ming.Modeling and analyzing topic evolution.Acta Automatica Sinica,2012,38(10):1690?1697(胡艷麗,白亮,張維明.一種話題演化建模與分析方法.自動化學(xué)報,2012,38(10):1690?1697)

29 Thelwall M,Buckley K,Paltoglou G.Sentiment in twitter events.Journal of the American Society for Information Science and Technology,2011,62(2):406?418

30 Bollen J,Mao H N,Zeng X J.Twitter mood predicts the stock market.Journal of Computational Science,2011,2(1):1?8

31 Wu Xin-Dong,Li Yi,Li Lei.In fluence analysis of online social networks.Chinese Journal of Computers,2014,37(4):735?752(吳信東,李毅,李磊.在線社交網(wǎng)絡(luò)影響力分析.計算機學(xué)報,2014,37(4):735?752)

32 Perozzi B,Al-Rfou R,Skiena S.Deepwalk:online learning of social representations.In:Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,NY,USA:ACM,2014.701?710

33 Xin Yu,Yang Jing,Xie Zhi-Qiang.An overlapping semantic community structure detecting algorithm by label propagation.Acta Automatica Sinica,2014,40(10):2262?2275(辛宇,楊靜,謝志強.基于標(biāo)簽傳播的語義重疊社區(qū)發(fā)現(xiàn)算法.自動化學(xué)報,2014,40(10):2262?2275)

34 Huang Li-Wei,Li Cai-Ping,Zhang Hai-Su,Liu Yu-Chao,Li De-Yi,Liu Yan-Bo.A semi-supervised community detection method based on factor graph model.Acta Automatica Sinica,2016,42(10):1520?1531(黃立威,李彩萍,張海粟,劉玉超,李德毅,劉艷博.一種基于因子圖模型的半監(jiān)督社區(qū)發(fā)現(xiàn)方法.自動化學(xué)報,2016,42(10):1520?1531)

35 Tsur O,Rappoport A.What0s in a hashtag?:content based prediction of the spread of ideas in microblogging communities.In:Proceedings of the 5th ACM International Conference on Web Search and Data Mining.Seattle,Washington,USA:ACM,2012.643?652