一種改進的網(wǎng)絡(luò)突發(fā)話題檢測算法

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

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

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

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

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

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é)在讀博士，主要從事計算機技術(shù)方向研究.

E-mail:hayan1997@sina.com

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

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

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

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

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

(1)

(2)

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

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

(3)

(4)

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

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

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

(5)

(6)

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

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

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

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

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

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

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

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

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

Step 1初始化

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

Step 2解的構(gòu)造

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

在每一步k，構(gòu)建序列xk=〈c1,c2,…,ck〉后，根據(jù)如下的概率選擇下一個結(jié)點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ù)，且滿足：f(s)

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

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

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

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

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

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

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

(7)

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

(8)

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

DOI：10.3969/j.issn.1000-1565.2015.05.014

中圖分類號：TP391文獻標(biāo)志碼：A

收稿日期:2015-01-15

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

4數(shù)值實驗

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

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

4.2　實驗數(shù)據(jù)采集

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

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

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

表1　3種算法的評價指標(biāo)比較

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

圖1　F-measure性能折線

然后分別比較不同算法對于相關(guān)話題聚類需要的平均運行時間，表2為比較結(jié)果.

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

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

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

圖2　平均運行時間折線

5結(jié)論

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

參考文獻:

[1]夏火松，甄化春.大數(shù)據(jù)環(huán)境下輿情分析與決策支持研究文獻綜述[J].情報雜志,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ā)話題發(fā)現(xiàn)[J].中文信息報,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].計算機與現(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]易云飛,陳國鴻.基于 k-means 的改進粒子群算法求解TSP問題[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]桑基韜,查正軍,徐常勝.以用戶為中心的社會多媒體計算[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的最佳聚類數(shù)確定方法研究[J].電腦知識與 技術(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)顯.蟻群聚類算法中確定相鄰對象方法的改進[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é)任編輯：孟素蘭)