基于Single-Pass的網絡輿情熱點發現算法

格桑多吉，喬少杰，韓 楠，張小松，楊 燕，元昌安，康 健

(1. 西藏大學藏文信息技術研究中心 拉薩 850000; 2. 西南交通大學信息科學與技術學院 成都 610031; 3. 西南交通大學生命科學與工程學院 成都 610031; 4. 電子科技大學大數據研究中心 成都 611731; 5. 廣西師范學院科學計算與智能信息處理廣西高校重點實驗室 南寧 530023)

基于Single-Pass的網絡輿情熱點發現算法

格桑多吉1，喬少杰2，韓 楠3，張小松4，楊 燕2，元昌安5，康 健2

(1. 西藏大學藏文信息技術研究中心 拉薩 850000; 2. 西南交通大學信息科學與技術學院 成都 610031; 3. 西南交通大學生命科學與工程學院 成都 610031; 4. 電子科技大學大數據研究中心 成都 611731; 5. 廣西師范學院科學計算與智能信息處理廣西高校重點實驗室 南寧 530023)

考慮網絡事件的時間距離，基于半結構化網頁中不同位置特征項重要程度的不同，提出改進的single-pass文本聚類算法single-pass*，優勢在于對Web文本不同位置特征項的加權處理，僅需計算新文檔與同類別種子文檔間的相似度。實驗結果表明，相比single-pass，改進算法極大減少了漏檢率和錯檢率，降低了由于新文本流內文檔進行相似度計算導致系統性能的下降，平均提高Web文本聚類效率40%。將聚類后的Web文本應用于網絡輿情分析，進行主題關注度分析和話題熱度特性分析。

輿情分析; single-pass; 文本聚類; 話題發現

話題發現和跟蹤是指新聞專線和廣播新聞等來源的新聞數據流中自動地發現話題并把話題相關的內容組織到一起的技術。通過增量的文檔聚類的方法，信息流被聚集到有限的話題類簇中，類內高度相似，不同的類間相似度較低，以此進行海量數據的融合。熱點輿情話題是話題輿情中受關注度最大，影響也較為突出的輿情，旨在從半結構化海量Web數據中獲取相應的主題并進行整合，以新的熱點事件分析并了解熱點話題事件的發展。熱點話題分析對輿情分析具有較大的實際意義，可以及時向網絡監控部門提供網民關注焦點，輔助網絡輿情分析。

隨著網絡輿情及預警機制研究的廣泛深入和迫切性，話題發現和跟蹤的研究已經成為當前的研究熱點?？▋然仿〈髮W采用經典的single-pass算法識別新聞中的事件[1]。文獻[2]結合新聞要素提出了基于動態進化模型的新聞事件話題發現算法，應用基于時間距離的相似度計算模型自動對新聞資料進行組織，生成新聞專題。文獻[3]提出了利用single-pass對新聞事件在線聚類進而實現話題發現的算法。文獻[4]提出了一種基于multi-agent的思想single-pass聚類，使用分散的自底向上和自組織策略對相似的數據點進行分類。文獻[5]提出基于詞共現圖的識別中文微博新聞話題的方法，綜合相對詞頻和詞頻增加率這兩個因素抽取微博數據中的主題詞。文獻[6]基于文本重建的網絡話題發現模型，用主題區域發現話題并將其應用于整個文檔中以區分子話題。文獻[7]提出了一種中文微博熱點話題發現方法，不足之處在于僅進行了中文話題發現，不支持多語言的話題發現與跟蹤。本文研究的不同點在于：1)基于事件時間的先后引入了時間距離特性的相似度計算模型；2) 所提算法支持中、英、藏文等不同字符集的話題發現；3) 在話題發現基礎上進行網絡輿情分析工作。

1 話題發現與跟蹤

1.1 文本特征提取

文本的表征有諸多方法，如布爾模型、向量空間模型、概率模型等，其中向量空間模型是在應用中廣為采用的模型，首先被用于信息檢索系統。通常，文檔被表示為向量，每一維均對應獨立的詞。每篇文檔，均可以表示為規范化的特征向量：

式中，ti表示第i個特征項；wi表示特征項ti在文本d中的權重，所有的文本向量構成文本集的一個特征向量。文本向量中權重值的求取最為有效的方法是使用tf-idf模型，tf稱為詞頻，計算該詞描述一篇文檔內容的能力。其中，idf稱為逆文檔頻率，計算該詞區分文檔的能力。

1.2 加權詞頻因子tf

tf-idf是詞頻和逆文檔頻率兩項的乘積，有多種方法用于獲取兩種統計詞頻的精確值。使用在某篇文檔中的原始詞頻是最簡化的選擇，如詞t在文檔d中出現的次數。已知f(t, d)表示t的頻率，那么tf的計算公式是tf(t, d) = f(t, d)。值得注意的是，本文結合了出現在文檔中不同位置的詞的特性，如meta中keyword、title和description等關鍵詞在文檔中的權重，因此tf的計算公式表示為：

式中，f(body)表示特征詞t在Web文檔的body標簽位置出現的次數；f(meta)是在文檔標題與描述中特征詞出現的數目；w1、w2、w3是權重系數，取值分別表示某個事件的關鍵信息，即事件名稱、地點及組織這3個特征詞。為了保持一致，本文采用文獻[8]中權值的設置方法：

事件地點和組織的設置方法同事件名稱。w4= 3，表示網頁中meta中的keyword、title和description的權重。

1.3 逆文檔頻率idf

如果一個詞在很多文檔中出現過，則通過這個詞來區分文檔的區分度越小，可以用逆文檔頻率idf來度量，表示包含某個詞的文檔數目：

式中，n代表文檔的數量；m表示出現特征詞的文檔數量；0.01是為了防止n/m=0時對數值為1。綜上所述，特征詞的tf-idf值的計算公式如下：

1.4 話題模型和相似度計算

通常話題模型包含質心向量方法和中心向量方法。不準確中心向量的選擇極易導致后續增量聚類結果的錯誤。對于一篇新文檔，需要遍歷在某指定類別中的所有文檔，這樣隨著文檔數量的增加，算法的運行效率會降低。為此，本文提出了種子話題的概念，即在一個文檔類中，選擇若干文檔代表某一話題。此外，在文本相似度計算中，本文僅需計算新文檔和種子文檔間的余弦相似度。

式(6)和式(7)中，di表示新文檔的特征向量；dj表示某個話題的第j個種子話題的特征向量；M表示特征向量的維度；wik表示新文檔i的特征向量的第k個權重；wjk表示第j個種子話題特征向量的第k個權重；sim(di, dj)表示新文檔和一個類別中某一種子的相似度；表示新文檔特征向量和某類中第j個種子話題特征向量的平均相似度。

1.5 網絡事件的時效性

考慮到相似的事件可能在不同時間段發生的情況，本文引入報道時間距離的概念，對新聞報道與話題的相似性計算利用時間距離進行綜合衡量。對大量新聞報道研究發現，時間相距較遠的兩篇內容相似報道中出現的特征詞往往非常相似。如果不考慮這兩篇Web報道的時間距離，single-pass聚類算法會將不相關話題聚為同一類，因此引入時間距離來進一步區分文檔類別，時間距離計算方法如下：

式中，td表示報道d出現的時間；tch是與話題c相關第一篇報道時間；tce是話題c最近一篇報道時間。改進后報道d和話題c間相似度計算公式如下：

式中，sim(d, c)利用式(6)計算；dis(d, c)由式(8)求取。改進的文本相似度計算方法既考慮了文檔內容相似度的影響，又考慮了時間因素的影響，α和β是對這兩種因素所賦予的權值，其中，α+β=1。

2 基于single-pass算法的話題發現

2.1 single-pass聚類算法

single-pass算法采用增量聚類的方式將文本向量與已有話題內的報道進行比對，計算文本相似度進行匹配。若與某個話題類別匹配，則把該文本歸入該話題，若該文本域所有話題類別的相似度均小于某一閾值，則將該文本表示成新的種子話題。single-pass聚類算法步驟如下：1) 輸入新文檔d；2) 計算d與已有話題分類中每篇文檔的相似度，獲取與d相似度最大的話題并得到相似度值T；3) 若T大于閾值θ，則文檔d被分類到已知的話題類別，否則作為一個新的話題類別；4) 聚類過程結束。

2.2 single-pass*聚類算法

通過引入種子話題和在網頁中不同位置的文本信息要素加入權重，本文提出了一種改進的single-pass*聚類算法，區別在于：1) 引入了種子話題；2) 計算網頁不同位置的特征項權重，僅計算新文檔和類別種子文檔間的相似度。算法如下：

算法 1 基于single-pass的話題發現算法。輸入：Web文檔集合T，話題種子文檔集合S；輸出：聚類后的話題文檔集合T′。

Initialize T and S;

for (Ti∈T) do{

for (Sj∈S) do{

if ((S= =null) && (T != null))

}

}

if (!C.isEmpty){

sort(C);

if (S.size() ξ)

{Sk←insertSeedDoc(Ti);}

}

}

else{

create a new topic t;

t.setId(S.size()+1);

t.setTopic(Ti);

S.add(t);

}

}

output(T′);

算法基本思想為：1) 對文檔進行向量空間模型規范化處理(第1行語句)，每篇文檔都由一個對象集合組成，對新文檔集合進行遍歷，計算新文檔與每個話題類中種子文檔對象間的平均相似度(第2～5行語句)，若相似度大于已知的相似度閾值θ，將此新文檔與當前文檔類的平均相似度和類標加入到集合C中(第6～9行語句)，2) 根據平均相似度大小對C中對象進行排序，獲取平均相似度最大值所對應的類標，將新文檔加入到對應的種子文檔中(第10～11行語句)。若當前類標的種子數目與原始話題種子話題數目的比值k大于閾值ξ，并且當前種子文檔的數目小于l，將當前文檔插入到本類文檔列表中(第12～15行語句)；若C為空，說明此時沒有相應的類別與新文檔相似度大于閾值，新建文檔分類(第16～17行語句)，并將新文檔加入到此類的種子文檔集合中，根據當前新文檔對象列表循環迭代上述操作(第18～22行語句)。最后，輸出聚類后的話題文檔集合T′(第23行語句)。

3 實驗及算法性能分析

3.1 實驗評價標準

實驗中采用的評測標準包括：漏檢率M、錯檢率F和錯誤識別代價Cost[9]。

表1 話題發現評價標準

定義漏檢率M=C/(A+C)，錯檢率F=B/(B+D)。類似于F-measure，話題檢測與跟蹤引入了耗費代價函數對結果進行綜合評價，定義為：

式中，wm是漏檢率系數；wf是錯檢率系數；p是文檔歸屬某一話題的先驗概率。

3.2 實驗數據

本文設計實現了一個網頁抓取器，實驗中中文Web數據來源于新浪和搜狐網站的專欄，藏文數據來源于藏文門戶網站。其中，中文事件分為10類，藏文事件分為6類。

3.3 話題發現評價及分析

實驗利用IKAnalyzer中文分詞工具包對中文進行分詞，利用文獻[10]中使用的藏文分詞算法對藏文文本進行分詞，構建向量空間模型。single-pass算法中的閾值θ和ξ分別設置為0.02和0.15，取值依據是通過大量實驗，參數調節得到的最優值。

1) 中文話題發現評價

從中文實驗語料庫中整理出10個話題，每個話題包括90～120篇報道。實驗主要采用3.1節給出的話題檢測與跟蹤評價指標，結果如表2～表4所示。

表2 single-pass算法中文話題發現結果

表3 single-pass*算法中文話題發現結果

表2和表3分別為single-pass和single-pass*文本聚類算法的實驗結果，話題文本流被聚為10類，如馬航客機、云南昭通地震等。通過結果可以發現，single-pass*算法的性能明顯優于single-pass。

表4 中文Web文本下算法性能比較

如表4所示，在實驗參數和實驗文本數據一致的情況下，single-pass*算法的平均漏檢率和平均錯檢率均低于single-pass算法，漏檢率平均減少41.2%，錯檢率平均減少27.3%。原因在于：對Web文本不同位置的特征詞加權值使文檔的屬性標注更加準確，同時對固定維度的種子文檔進行文本相似度計算使文檔歸類更加有效，從而在漏檢率和錯檢率指標上都有所降低。

2) 藏文話題發現評價

從藏文實驗語料庫中每個話題包括86～1 441篇報道，實驗結果如表5～表7所示。

表5 single-pass算法藏文文本發現結果

表6 single-pass*算法藏文文本發現結果

表7 藏文Web文本下算法性能比較

改進算法在處理藏文Web文本上優勢依然明顯，在漏檢率和錯檢率上較single-pass算法都有較大的改善，原因與中文話題發現相同。

3.4 算法運行時間比較

本節討論single-pass*與single-pass運行時間，實驗結果如圖1所示?？梢园l現single-pass*算法的時間消耗明顯低于single-pass算法，平均降低40%。原因是改進后的算法僅需計算新文檔與指定數目的代表事件類別的種子節點的相似度，不需要與包含所有事件的文檔進行比較，減少了計算時間。

圖1 算法運行時間對比

3.5 Web話題輿情分析

對Web文本應用single-pass*算法進行文本聚類的主要目的是在聚類產生的不同主題類中進行輿情分析。主題關注度是指過去某一時間段內，輿情主題被關注的程度。時間段t1～t2內關于輿情主題S的主題關注度：

式中，rS(t)表示關于某一個輿情主題S的相關頁數隨時間的變化。

以固定時間間隔作為統計周期，主題關注度用Pi(i∈[1, 5])表示，如：P1={2009.4～2011.10}。表8顯示5個不同時間段內部分輿情的主題關注度，圖2顯示熱點話題主題關注度隨周期的變化。

表8 話題主題關注度分析

圖2 藏文新聞主題關注度趨勢分析

為了進一步驗證輿情主題關注度算法的性能，觀察隨著文本數量的增加，主題關注度分析方法的時間性能的變化如圖3所示。通過圖3可以發現，算法運行時間近似呈線性增長，與式(11)的定義吻合。

圖3 不同文本數量下主題關注度算法運行時間

4 結 束 語

IT技術與互聯網的迅猛發展，數據存儲量爆炸性地增長，并行處理與計算已經成為越來越重要的數據挖掘的問題。從大數據中發現有價值的知識需要各種高效的數據挖掘算法。single-pass聚類算法能夠高效地發現話題，通過引入話題種子的概念，本文提出了改進的single-pass聚類算法。實驗結果表明，本文提出的Web文本聚類算法不僅能夠提高聚類的質量，即在漏檢率、錯檢率和時間開銷等方面均有所改善，而且對網絡輿情分析的研究具有較好的應用價值。

[1] BAEZA-YATES R, RIBEIRO-NETO B. Modern information retrieval[M]. Boston, USA: Addison Wesley, 2000.

[2] 賈自艷, 何清, 張?？? 等. 一種基于動態進化模型的事件探測和追蹤算法[J]. 計算機研究與發展, 2004, 41(7): 1273-1280. JIA Zi-yan, HE Qing, ZHANG Hai-jun, et al. A news event detection and tracking algorithm based on dynamic evolution model[J]. Journal of Computer Research and Development, 2004, 41(7): 1273-1280.

[3] GONG Z, JIA Z, LUO S, et al. An adaptive topic tracking approach based on single-pass clustering with sliding time window[C]//Proceedings of the 2011 International Conference on Computer Science and Network Technology. Washington DC, USA: IEEE Computer Society, 2011: 1311-1314.

[4] FORESTIERO A, CLARA P, GIANDOMENICO S. A single pass algorithm for clustering evolving data streams based on swarm intelligence[J]. Data Mining and Knowledge Discovery, 2013, 26(1): 1-26.

[5] 趙文清, 侯小可. 基于詞共現圖的中文微博新聞話題識別[J]. 智能系統學報, 2012, 7(5): 444-449. ZHAO Wen-qing, HOU Xiao-ke. News topic recognition of Chinese microblog based on word co-occurrence graph[J]. CAAI Transactions on Intelligent Systems, 2012, 7(5): 444-449.

[6] ZHU Z, WANG P, JIA Z, et al. Network topic detection model based on text reconstructions[J]. Informatica, 2013, 37(4): 367-372.

[7] YANG C, YANG J, DING H, et al. A hot topic detection approach on Chinese microblogging[C]//Proceedings of the International Conference on Information Engineering and Applications (IEA) 2012. London: Springer, 2013: 411-420.

[8] 稅儀冬, 瞿有利，黃厚寬, 等. 周期分類和Single-Pass聚類相結合的話題識別與跟蹤方法[J]. 北京交通大學學報, 2009, 33(5): 85-87. SHUI Yi-dong, QU You-li, HUANG Hou-kuan, et al. A new topic detection and tracking approach combining periodic classification and single-pass clustering[J]. Journal of Beijing Jiaotong University, 2009, 33(5): 85-87.

[9] 張曉燕, 王挺. 話題發現與追蹤技術研究[J]. 計算機科學與探索, 2009, 3(4): 347-357. ZHANG Xiao-yan, WANG Ting. Research of technologies on topic detection and tracking[J]. Journal of Frontiers of Computer Science and Technology, 2009, 3(4): 347-357.

[10] 康健, 喬少杰, 格桑多吉, 等. 基于群體智能的半結構化藏文文本聚類算法[J]. 模式識別與人工智能, 2014, 27(7): 663-671. KANG Jian, QIAO Shao-qie, GESANG Duoji, et al. A semi- structured Tibetan text clustering algorithm based on swarm intelligence[J]. Pattern Recognition and Artificial Intelligence, 2014, 27(7): 663-671.

編輯蔣 曉

An Internet Public Opinion Hotspot Detection Algorithm Based on Single-Pass

GESANG Duoji1, QIAO Shao-jie2, HAN Nan3, ZHANG Xiao-song4, YANG Yan2, YUAN Chang-an5, and KANG Jian2
(1. Tibetan Information Technology Research Center, Tibet University Lasa 850000; 2. School of Information Science and Technology, Southwest Jiaotong University Chengdu 610031; 3. School of Life Science and Engineering, Southwest Jiaotong University Chengdu 610031; 4. Big Data Research Center, University of Electronic Science and Technology of China Chengdu 611731; 5. Science Computing and Intelligent Information Processing of Guangxi Higher Education Key Laboratory, Guangxi Teachers Education University Nanning 530023)

By considering the time interval of Internet events as well as the importance of different feature items from semi-structured Web documents in different locations, an improved single-pass text clustering algorithm called single-pass* is proposed. The advantage is that it assigns the weight value to different feature items from different locations on the Web pages, and only needs to calculate the similarity between the new document and its seed document. Experimental results show that, compared to the single-pass algorithm, the improved algorithm can reduce the missing rate, the error detection rate, and the degradation of system performance caused by computing the topic similarity of documents in new Web data stream, and improve the clustering efficiency at an average rate of 40%. The clustered Web texts can be used to analyze the Internet opinion including the topic relevant degree and the hot degree.

public opinion analysis; single-pass; text clustering; topic detection

TP312

A doi:10.3969/j.issn.1001-0548.2015.04.021

2014 ? 11 ? 07；

2015 ? 05 ? 13

國家自然科學基金(61100045, 61165013)；高等學校博士學科點專項科研基金(20110184120008)；中國博士后科學基金特別資助項目(201104697)；教育部人文社會科學研究青年基金(14YJCZH046)；中央高?；究蒲袠I務費專項資金(2682013BR023)；科學計算與智能信息處理廣西高校重點實驗室開放課題資助(GXSCIIP201407)；四川省教育廳資助科研項目(14ZB0458).

格桑多吉(1972 ? )，男，副教授，主要從事藏文信息處理、Web文本挖掘方面的研究.