一種改進(jìn)的網(wǎng)絡(luò)突發(fā)話(huà)題檢測(cè)算法

哈艷1,2,杜瑞忠2,鐘蓮3，張東琦2，李森4

(1. 河北大學(xué) 建筑工程學(xué)院，河北 保定071002；2. 河北大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河北 保定071002；

3. 河北軟件職業(yè)技術(shù)學(xué)院 軟件工程系，河北 保定071000；4. 河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定071002)

摘要：引進(jìn)文本相關(guān)度這一影響因子，提出了一種基于蟻群聚類(lèi)算法的突發(fā)話(huà)題檢測(cè)算法，該算法結(jié)合蟻群聚類(lèi)算法的優(yōu)勢(shì)，綜合考慮文本聚類(lèi)和文本相關(guān)度的影響，得到對(duì)網(wǎng)絡(luò)突發(fā)話(huà)題檢測(cè)的最優(yōu)聚類(lèi)效果，并對(duì)近年來(lái)網(wǎng)絡(luò)突發(fā)話(huà)題進(jìn)行實(shí)驗(yàn)，達(dá)到了很好的聚類(lèi)速度和聚類(lèi)效果，驗(yàn)證了算法對(duì)突發(fā)話(huà)題檢測(cè)的準(zhǔn)確性和即時(shí)性.

關(guān)鍵詞：網(wǎng)絡(luò)輿情; 突發(fā)話(huà)題檢測(cè); 文本相關(guān)度; 蟻群聚類(lèi)算法

An improved algorithm of bursty topic detection

HA Yan1,2,DU Ruizhong2,ZHONG Lian3，ZHANG Dongqi2,LI Sen4

(1.College of Civil Engineering and Architecture, Hebei University, Baoding 071002, China;

2.School of Computer Science and Technology, Hebei University, Baoding 071002, China;

3. Software Engineering Department ，Hebei Software Institute，Baoding 071000,China;

4. College of Mathematics and Information Science, Hebei University, Baoding 071002, China)

Abstract：A burst topic detection algorithm based on the ant colony clustering algorithm by introducing the text-related factor has been proposed. Combined with the advantages of ant colony clustering algorithm, this algorithm can get an optimal clustering effect on detection network of burst topic by considering the effect of text clustering and text-related degrees. Based on the experiments of network unexpected topic in recent years, it has been proved that this algorithm can achieve good effect of speed clustering and cluster, as well as the accuracy and immediacy of the algorithm topic burst detection.

Key words：online public opinion; bursty topic detection; text-related; ant colony clustering algorithm

第一作者:哈艷(1974-)，女，回族，河北肅寧人，河北大學(xué)副教授，河北大學(xué)在讀博士，主要從事計(jì)算機(jī)技術(shù)方向研究.

E-mail:hayan1997@sina.com

隨著Web 2.0技術(shù)的快速發(fā)展，以互聯(lián)網(wǎng)為載體的各種社交網(wǎng)絡(luò)平臺(tái)成為Web 2.0時(shí)代最具代表性的應(yīng)用，其中，微博已經(jīng)成為互聯(lián)網(wǎng)輿情形成的主要網(wǎng)絡(luò)媒體之一[1]，同時(shí)，對(duì)突發(fā)話(huà)題的檢測(cè)、溯源以及傳播預(yù)測(cè)是網(wǎng)絡(luò)輿情管理的重要目標(biāo)之一.目前已有學(xué)者提出諸多話(huà)題檢測(cè)算法，比如Michail Vlachos[2]將突發(fā)事件定義為由一組高相關(guān)的突發(fā)特征組成的事件.應(yīng)用OMRBD(在線(xiàn)多分辨率突發(fā)發(fā)現(xiàn)算法)發(fā)現(xiàn)不同突發(fā)持續(xù)時(shí)間的突發(fā)特征.為了用突發(fā)特征表示突發(fā)事件，本文把突發(fā)特征之間的關(guān)聯(lián)關(guān)系以及突發(fā)特征的優(yōu)先級(jí)作為輸入，使用近鄰傳播算法[3]發(fā)現(xiàn)突發(fā)事件.程學(xué)旗等[4]提出了一種基于噪聲過(guò)濾的突發(fā)話(huà)題發(fā)現(xiàn)模型，從內(nèi)容和用戶(hù)參與度2個(gè)角度發(fā)現(xiàn)網(wǎng)絡(luò)論壇中的突發(fā)話(huà)題并且能夠找到與這些突發(fā)話(huà)題相關(guān)聯(lián)的一些核心用戶(hù)以及由這些用戶(hù)所構(gòu)成的網(wǎng)絡(luò)社區(qū).Michael Mathioudakis等人[5]實(shí)現(xiàn)了一個(gè)Twitter數(shù)據(jù)流事件發(fā)現(xiàn)系統(tǒng),其首先基于排隊(duì)論識(shí)別突發(fā)詞，然后根據(jù)突發(fā)詞的共現(xiàn)關(guān)系形成事件,利用PCA，SVD和命名實(shí)體識(shí)別技術(shù)獲得描述事件的文本信息.

現(xiàn)有的微博突發(fā)話(huà)題相關(guān)的輿情研究中未考慮突發(fā)話(huà)題的形成機(jī)理，導(dǎo)致應(yīng)用到實(shí)際微博輿情監(jiān)管效果不佳.比如，Qiming Diao等人[6]基于微博消息流中同一時(shí)間的消息傾向于屬于同一話(huà)題和同一個(gè)用戶(hù)發(fā)布的消息，提出了基于LDA模型[7]的突發(fā)話(huà)題檢測(cè)模型，該方法雖然同時(shí)考慮了時(shí)態(tài)信息和個(gè)人興趣,但是其在計(jì)算所有話(huà)題的基礎(chǔ)上再進(jìn)行突發(fā)話(huà)題檢測(cè)，整體檢測(cè)時(shí)間慢，且只能針對(duì)離線(xiàn)數(shù)據(jù)進(jìn)行突發(fā)話(huà)題檢測(cè)；Mario Cataldi等人[8]通過(guò)衰老理論對(duì)字的生命周期進(jìn)行建模，進(jìn)而提出基于字的突發(fā)話(huà)題檢測(cè)模型.文中采用固定時(shí)間窗口大小的滑動(dòng)窗口機(jī)制，但是微博消息流變化迅速，在短時(shí)間內(nèi)沒(méi)有固定規(guī)律，但在長(zhǎng)時(shí)間內(nèi)表現(xiàn)出周期性，因此無(wú)法處理短時(shí)間內(nèi)的突發(fā)情況，此方法雖然考慮了用戶(hù)的屬性信息，但是采用pagerank的迭代算法計(jì)算用戶(hù)的影響力，大大增加了算法的計(jì)算復(fù)雜度.因此，本文從話(huà)題聚類(lèi)效果和速度的最優(yōu)角度出發(fā)，運(yùn)用蟻群聚類(lèi)算法(RTACC算法)的基本原理，結(jié)合文本相關(guān)度進(jìn)行聚類(lèi)優(yōu)化，達(dá)到了很好的聚類(lèi)效果.

1幾個(gè)相關(guān)向量的定義

定義1文本集合D={D1,D2,…,Dk,…,Dn},1≤k≤n.其中，Dk表示D中第k個(gè)文本，n表示D中所包含文本的總數(shù).已知輿情文本集合{D}有n個(gè)話(huà)題問(wèn)題和K個(gè)分類(lèi){Sj=j=1,2,…,K},各個(gè)輿情文本有d個(gè)特征值，見(jiàn)矩陣D：

矩陣D中，每行為一個(gè)特殊向量，Di1,Di2,…,Did為第i個(gè)特殊向量的d個(gè)特征值，要求達(dá)到各向量到聚類(lèi)中心的距離之和達(dá)最小，它的目標(biāo)函數(shù)如下：

(1)

(2)

定義2初始話(huà)題集合IT={IT1,IT2,…,ITk,…,ITm}，其中，ITi(i=1,2,…,n)表示對(duì)文本集合D中所有集合經(jīng)過(guò)去除冗雜數(shù)據(jù)和符號(hào)后的文本構(gòu)成的數(shù)據(jù)集.

定義3話(huà)題集合T={T1,T2,…,Tk,…,Tm}，其中Ti(i=1,2,…,n)表示初始數(shù)據(jù)集中話(huà)題次數(shù)比指定閾值大的集合并利用字典處理中同近義詞原則將話(huà)題中同、近義詞語(yǔ)處理后得到的數(shù)據(jù)集.有，Ti?Tj的可信度和支持度S.C,S分別如式(3)，(4)所示.

(3)

(4)

其中，|{T：Ti∪Tj?D}|表示在D中同時(shí)出現(xiàn)話(huà)題Ti和Tj的文本數(shù)目，|D|表示文本的總數(shù)目.

定義4相關(guān)度矩陣A，表示話(huà)題Ti(i=1,2,…,n)和Tj(i=1,2,…,n)之間可信度的矩陣.由定義中關(guān)聯(lián)規(guī)則Ti?Tj的可信度計(jì)算公式，遍歷T中所有話(huà)題，確定2個(gè)話(huà)題間的相關(guān)可信度，與話(huà)題間可信度有關(guān).建立nn的話(huà)題相關(guān)矩陣A：

矩陣中各元素按式(5)進(jìn)行計(jì)算

(5)

(6)

式中tfi,k的表示Di對(duì)TCj中Tk的貢獻(xiàn)度，即Tk在Di中出現(xiàn)的頻率，ni表示Di中包含的話(huà)題總數(shù).

2基于蟻群算法的網(wǎng)絡(luò)突發(fā)話(huà)題檢測(cè)流程

考慮網(wǎng)絡(luò)突發(fā)話(huà)題檢測(cè)算法一個(gè)組合優(yōu)化問(wèn)題(S,f,Ω)[9],問(wèn)題中，S是候選話(huà)題的集合，f是目標(biāo)函數(shù)，對(duì)于任意s∈S有目標(biāo)函數(shù)值f(s)；Ω是約束條件的集合，由可行解集合，突發(fā)話(huà)題檢測(cè)問(wèn)題(S,f,Ω)可以描述為以下問(wèn)題：

1)話(huà)題集合ξ=(c,c2,…,cNC)為優(yōu)化問(wèn)題的組成.

2)由可能話(huà)題序列x=〈ci,cj,…,ck,…〉來(lái)定義問(wèn)題的有限狀態(tài)話(huà)題集合χ，其中ci,cj,…,ck是ξ的話(huà)題元素.話(huà)題數(shù)目表示為|x|，表示話(huà)題中元素的個(gè)數(shù)，最大值l<∞.

3)突發(fā)話(huà)題集合S是有限狀態(tài)話(huà)題集合χ的子集，即S?χ.

4)可行狀態(tài)話(huà)題集合χ?χ，由滿(mǎn)足約束條件的話(huà)題集合Ω的序列構(gòu)成x∈χ.

5)S*是非空話(huà)題集合的最優(yōu)解，如果滿(mǎn)足S*?χ且S*?S.

關(guān)鍵詞由上可知，突發(fā)話(huà)題檢測(cè)問(wèn)題可以用一種有向圖G=(ξ,L)的思路進(jìn)行解決,問(wèn)題中，ξ為話(huà)題的集合，L為所有話(huà)題的鏈接弧集合，本文算法在檢測(cè)算法的應(yīng)用步驟如下：

Step 1初始化

關(guān)鍵詞隨機(jī)產(chǎn)生初始可行解s′，并設(shè)置=s′，?(i,j)，τij=τ0，對(duì)每一個(gè)螞蟻選擇初始c1，k=1，xk=〈c1〉；

Step 2解的構(gòu)造

While(xk∈χ且xk?S)do.

在每一步k，構(gòu)建序列xk=〈c1,c2,…,ck〉后，根據(jù)如下的概率選擇下一個(gè)結(jié)點(diǎn)l：

其中Jck表示可行域，α∈(0,+∞)為參數(shù).當(dāng)Jck為空，螞蟻停止搜索，解的構(gòu)造完成；

Step 3信息激素更新

?(i,j):τij←(1-ρn)°τij,

Iff(st)

?(i,j)∈:τij←τij+ρn°g(),

其中，0<ρn<1為信息激素發(fā)揮系數(shù)；g(s)是路徑s的函數(shù)，且滿(mǎn)足：f(s)

3引進(jìn)文本相關(guān)度的蟻群聚類(lèi)算法

關(guān)鍵詞第1步，關(guān)聯(lián)規(guī)則算法的建立.從大量的文本中挖掘出有價(jià)值的描述文本集合之間相互聯(lián)系的話(huà)題.在關(guān)聯(lián)規(guī)則中，設(shè)D=(D1,D2,…,Dk,…，Dn)是所有文本的集合，其中的元素稱(chēng)為文本項(xiàng)，T為話(huà)題項(xiàng)的集合.

假設(shè)X，Y是文本項(xiàng)集，關(guān)聯(lián)規(guī)則是一個(gè)形如X?Y的蘊(yùn)含式，這里X?T,Y?T,并且X∩Y=Φ.其中X是數(shù)據(jù)集的前文本，Y是數(shù)據(jù)集的后文本，?是相關(guān)度計(jì)算.文本集D的2個(gè)約束條件是支持度S和可信度C約束，分別代表頻度和強(qiáng)度.話(huà)題文本集D中包含項(xiàng)目集X和Y，Y的話(huà)題數(shù)與所有話(huà)題數(shù)之比，成為關(guān)聯(lián)規(guī)則X?Y的支持度S，即

S:support(X?Y)=|{T:X∪Y?T}|/|D|.

可信度C是包含文本集合X和Y的項(xiàng)目數(shù)與X總項(xiàng)目數(shù)之比

C:confidence(X?Y)=|{T:X∪Y?T}|/{T:X?T}|.

第2步，文本相關(guān)度的計(jì)算.文本相關(guān)度計(jì)算式如式(7)所示：

(7)

第3步，文本相似度和相關(guān)度的結(jié)合.利用余弦相似度計(jì)算出2個(gè)話(huà)題文本Di和Dj的相似度Si,j=sim(Di,Dj)，然后利用文本相關(guān)度來(lái)修正文本相似密度，結(jié)合算法如式(8)：

(8)

關(guān)鍵詞當(dāng)i=j時(shí)，Vi,j=1.當(dāng)|Si,j-Ri,j|≤ε時(shí)，說(shuō)明相似度與相關(guān)度并沒(méi)有對(duì)話(huà)題帶來(lái)大幅度的修正，于此0≤ε≤，γ為一種度量相關(guān)度與相似度二者之于文本相關(guān)度產(chǎn)生如何影響的因子.當(dāng)Si,j<ε且Ri,j>λ時(shí)，說(shuō)明文本相似度微小，而相關(guān)度則是給予了文本集合之間較大的影響，在此0≤λ≤1.除此之外，各種測(cè)試均能說(shuō)明相似度和相關(guān)度都會(huì)令文本聯(lián)系帶來(lái)一定的變動(dòng)，而在此之中，α為相關(guān)度之于相似度的調(diào)整.

DOI：10.3969/j.issn.1000-1565.2015.05.014

中圖分類(lèi)號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

收稿日期:2015-01-15

基金項(xiàng)目:河北省社會(huì)科學(xué)基金資助項(xiàng)目(HB14XW014); 保定市社科基金資助項(xiàng)目(20140434);河北省大學(xué)生創(chuàng)新訓(xùn)練計(jì)劃項(xiàng)目(2014047)

4數(shù)值實(shí)驗(yàn)

4.1　算法編程環(huán)境

本算法在windows7操作系統(tǒng)中，利用C#語(yǔ)言，采用Microsoft Visual Studio 2012和Microsoft SQL Server 2008軟件進(jìn)行實(shí)現(xiàn)，對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行處理，得出4.3中的實(shí)驗(yàn)結(jié)果.

4.2　實(shí)驗(yàn)數(shù)據(jù)采集

本文從實(shí)際問(wèn)題入手，編寫(xiě)網(wǎng)絡(luò)爬蟲(chóng)數(shù)據(jù)采集系統(tǒng)，對(duì)國(guó)內(nèi)各大主流媒體網(wǎng)站進(jìn)行數(shù)據(jù)采集，并對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，最后在其中選出10個(gè)話(huà)題，分別是APEC會(huì)議、米蘭世博會(huì)、全球移動(dòng)互聯(lián)網(wǎng)大會(huì)、阿里上市、埃博拉疫情、劉翔退役、十八大、財(cái)稅改革事件、養(yǎng)老金“并軌”事件、長(zhǎng)慶油田增產(chǎn)事件.為保證數(shù)目，本文對(duì)每個(gè)話(huà)題選擇 100 篇新聞報(bào)道，共計(jì)1 000篇.

4.3　實(shí)驗(yàn)運(yùn)行結(jié)果及數(shù)據(jù)分析

本文先采用F-measure評(píng)價(jià)指標(biāo)[10]對(duì)傳統(tǒng)K-means算法[11]、LF算法[12]和基于文本相關(guān)度的蟻群聚類(lèi)算法的性能進(jìn)行比較分析.K-means算法參數(shù)為K=10.LF算法和本文提出的算法參數(shù)為α=0.25，k1=0.1，k2=0.15，s=2.下表為3種算法評(píng)價(jià)指標(biāo)比較結(jié)果：

表1　3種算法的評(píng)價(jià)指標(biāo)比較

為了明顯地觀察比較結(jié)果，利用MATLAB軟件將表1數(shù)據(jù)繪制成3種算法的 F-measure 性能折線(xiàn)圖，如圖1.

圖1　F-measure性能折線(xiàn)

然后分別比較不同算法對(duì)于相關(guān)話(huà)題聚類(lèi)需要的平均運(yùn)行時(shí)間，表2為比較結(jié)果.

表2　平均執(zhí)行時(shí)間的比較

為了便于比較結(jié)果，利用MATLAB軟件將表1數(shù)據(jù)繪制為平均運(yùn)行時(shí)間折線(xiàn)圖，如圖2.

實(shí)驗(yàn)結(jié)果表明，本文所用的蟻群聚類(lèi)算法與K-means聚類(lèi)算法以及LF算法相比，其聚類(lèi)查準(zhǔn)率與聚類(lèi)查全率均高于二者.本文算法執(zhí)行時(shí)間明顯低于LF算法， K-means算法雖然執(zhí)行速度較快，但其處理效果低. 由此說(shuō)明本文算法中引進(jìn)文本相關(guān)度這一度量提高了對(duì)網(wǎng)絡(luò)突發(fā)話(huà)題的查準(zhǔn)率和查全率，表現(xiàn)出了更好的聚類(lèi)效果和聚類(lèi)速度.

圖2　平均運(yùn)行時(shí)間折線(xiàn)

5結(jié)論

本文通過(guò)引用話(huà)題文本相關(guān)度這一影響因子，結(jié)合蟻群聚類(lèi)算法的優(yōu)勢(shì)，提出的基于文本相關(guān)度的蟻群聚類(lèi)分析算法達(dá)到了網(wǎng)絡(luò)突發(fā)話(huà)題檢測(cè)的最優(yōu)聚類(lèi)效果，并對(duì)近年來(lái)網(wǎng)絡(luò)突發(fā)話(huà)題進(jìn)行實(shí)驗(yàn)，驗(yàn)證了算法對(duì)突發(fā)話(huà)題檢測(cè)的準(zhǔn)確性和即時(shí)性，表明基于文本相關(guān)度的網(wǎng)絡(luò)突發(fā)話(huà)題檢測(cè)算法對(duì)網(wǎng)絡(luò)突發(fā)話(huà)題的檢測(cè)是有效的.

參考文獻(xiàn):

[1]夏火松，甄化春.大數(shù)據(jù)環(huán)境下輿情分析與決策支持研究文獻(xiàn)綜述[J].情報(bào)雜志,2015,34(2):1-6．

XIA Huosong, ZHEN Huachun. Public opinion analysis and decision support study under big data surroundings[J].Journal of Information,2015,34(2):1-6.

[2]VLACHOS M, MEEK C,VAGENA Z. Identifying similarities, periodicities and bursts for online search queries[Z]. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, France, 2004.

[3]FREY BJ ,DUECK D. Clustering by passing messages between data points[J].Science,2007, 315(2):972-976.

[4]陳友,程學(xué)旗,楊森.面向網(wǎng)絡(luò)論壇的突發(fā)話(huà)題發(fā)現(xiàn)[J].中文信息報(bào),2010,24(3):29-36.

CHEN You, CHENG Xueqi, YANG Sen. Outburst topic detection for Web forums[J].Journal of Chinese Information Processing,2010,24(3):29-36.

[5]MATHIOUDAKIS M , KOUDAS N .TwitterMonitor: trend detection over the twitter stream[Z]. Proceeding of the 2010 International Conference on Management of Data, New York, USA, 2010.

[6]DIAO Q, JIANG J, ZHU F, et al. Finding bursty topics from microblogs [Z]. Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics, Jeju Island , Korea, 2012.

[7]歐衛(wèi),謝贊福,謝彬彬,等.基于LDA模型的社交網(wǎng)絡(luò)主題社區(qū)挖掘[J].計(jì)算機(jī)與現(xiàn)代化, 2014(8): 21-29.

OU Wei, XIE Zanfu, XIE Binbin, et al. Mining of topic communities in social networks based on LDA model[J]. Computer and Modernization, 2014(8):21-29.

[8]MARIO C, LUIGI DI C, CLAUDIO S. Emerging topic detection on twitter based on temporal and social terms valuation[Z]. Proceedings of the Tenth International Workshop on Multimedia Data Mining, New York, USA, 2010.

[9]易云飛,陳國(guó)鴻.基于 k-means 的改進(jìn)粒子群算法求解TSP問(wèn)題[J].微計(jì)算機(jī)信息,2012,28(9):475-477.

YI Yunfei,CHEN Guohong. An improved PSO algorithm based on k-means to solve TSP[J].Microcomputer Information,2012,28(9):475-477.

[10]桑基韜,查正軍,徐常勝.以用戶(hù)為中心的社會(huì)多媒體計(jì)算[J].中興通訊技術(shù),2014,20(1):29-31.

SANG Jitao, CHA Zhengjun, XU Changsheng. User-Centric social multimedia computing[J].ZTE Technology Journal,2014,20(1):29-31.

[11]李紅巖,胡林林,王江波,等.基于K-means的最佳聚類(lèi)數(shù)確定方法研究[J].電腦知識(shí)與 技術(shù),2014,10(1):110-114.

LI Hongyan, HU Linlin, WANG Jiangbo, et al. A method for determining vintage number of clusters based on K-means algorithm[J]. Computer Knowledge and Technology, 2014,10(1):110-114.

[12]陳應(yīng)顯.蟻群聚類(lèi)算法中確定相鄰對(duì)象方法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(18):144-146.

CHEN Yingxian. Improvement of identified adjacent object on ant colony clustering algorithm [J].Computer Engineering and Application,2009,45(18):144-146.

(責(zé)任編輯：孟素蘭)