基于改進Single-Pass算法的網(wǎng)絡新聞話題發(fā)現(xiàn)

孫紅光, 高 星, 孫鐵利, 楊鳳芹, 彭 楊, 馮國忠

( 1. 東北師范大學 信息科學與技術學院, 長春 130117； 2. 智能信息處理吉林省高校重點實驗室, 長春 130117； 3. 解放軍報社, 北京 100832)

互聯(lián)網(wǎng)新媒體產(chǎn)生海量的半結構化新聞數(shù)據(jù), 具有時效性短、 動態(tài)性強和結構不規(guī)范等特點. 因此如何有效地從海量數(shù)據(jù)中發(fā)現(xiàn)新聞話題, 是網(wǎng)絡新聞話題發(fā)現(xiàn)的主要問題. 話題檢測與跟蹤(topic detection and tracking ,TDT)旨在研究從大量新聞數(shù)據(jù)流中發(fā)現(xiàn)重要信息, 在無人工干預的情況下自動判斷數(shù)據(jù)流的主題[1]. 目前, 這方面的研究已取得了許多成果[2-8]. 話題發(fā)現(xiàn)的關鍵技術為文本聚類, 以話題為粒度發(fā)現(xiàn)新事件并了解事件的進展. 其算法有別于傳統(tǒng)的文本聚類算法, 需同時考慮語料的時間特性、 動態(tài)性和數(shù)據(jù)來源等因素. 雷震等[9]提出了一種改進K均值算法發(fā)現(xiàn)熱點話題, 用密度函數(shù)法進行聚類中心的初始化, 但該算法當處理新報道時需對所有文檔重新計算, 無法保證話題發(fā)現(xiàn)的實時性; 張琛等[10]基于詞項間語義信息的方法進行話題檢測; Amrutha等[11]提出了TDA和TCTR(topic clustering and tweet retrieval)方法對微博進行聚類以發(fā)現(xiàn)話題. 本文采用話題發(fā)現(xiàn)中應用最廣泛的Single-Pass算法實現(xiàn)新聞文本的聚類, 在特征權重的計算、 相似度計算和聚類中心動態(tài)更新三方面進行改進, 并應用于網(wǎng)絡新聞話題發(fā)現(xiàn)的研究中.

1 話題發(fā)現(xiàn)及模型

1.1 話題發(fā)現(xiàn)

網(wǎng)絡話題發(fā)現(xiàn)是指將大量討論同一話題的新聞報道聚合在同一個簇下, 從而更好組織信息的過程. 本文研究網(wǎng)絡新聞話題發(fā)現(xiàn)技術, 話題發(fā)現(xiàn)的處理流程如圖1所示. 話題發(fā)現(xiàn)主要包括信息采集、 文本預處理、 特征提取、 文本表示、 相似度計算、 文本聚類6個步驟.

圖1 網(wǎng)絡新聞話題發(fā)現(xiàn)處理流程Fig.1 Processing flow for network news topic discovery

1.2 數(shù)據(jù)預處理及表示模型

首先, 通過主題爬蟲系統(tǒng)從新浪新聞網(wǎng)站上爬取一段時間內(nèi)的新聞報道, 構建新聞語料庫. 本文采用中科院分詞系統(tǒng)ICTCLAS對新聞語料進行分詞并去除停用詞. 其次, 文本向量表示是基于中文分詞后的詞項作為文本的特征向量, 每個向量都是一個維度. 由于文本向量空間維度較大, 因此采用文本特征選擇方法進行降維, 降低計算的復雜度.

本文采用向量空間模型(vector space model, VSM)進行新聞文本的表示. 每個新聞文本D表示為n維向量形式：D=(t1,w1,t2,w2,…,ti,wi,tn,wn), 其中：n表示文本D中的特征詞總數(shù);ti(1

2 網(wǎng)絡新聞話題聚類算法

經(jīng)典Single-Pass算法實現(xiàn)簡單、 處理速度快, 可處理動態(tài)數(shù)據(jù). 但該算法并未考慮新聞報道的時間特性以及特征詞項在新聞標題和正文不同位置對其權重值的影響. 本文充分考慮新聞報道的特性, 即動態(tài)性和時間特性等, 對該聚類算法進行如下改進.

2.1 詞項權重計算

通常新聞標題能對事件做主要或關鍵性的描述, 基本體現(xiàn)了新聞的主題. 新聞報道標題的導向性應以具體的方法體現(xiàn). 而傳統(tǒng)的文本表示模型一般都是對新聞的正文內(nèi)容進行相關處理. 本文考慮詞項出現(xiàn)在新聞標題和正文不同的位置信息, 對詞項權重的影響也不同, 采用TF-IDF權重計算方法.

由于考慮新聞報道的標題和正文信息, 在統(tǒng)計特征項詞頻時, 對來自標題的特征項詞頻乘上一個加權系數(shù)α(α≥1), 則文本特征w的詞頻計算公式為

tfw=α×tft(w)+tfc(w),

(1)

其中tft(w)和tfc(w)分別表示特征項w在標題和正文中的詞頻.α取值太小不能突出標題中特征項的重要性, 取值太大會抑制正文中絕大部分特征項對文本主題的描述能力, 因此α取值直接影響話題的聚類質量.

本文采用網(wǎng)絡新聞報道作為語料庫, 其數(shù)據(jù)特征是增量型的. 因此引入增量df, 即將語料按時間槽分別存儲, 在第i個時間槽中詞項w的文檔頻率通過前面的(i-1)個時間槽中所有文檔和第i個時間槽的文檔中包含w的文檔數(shù)量進行計算. 采用增量文檔頻率的方式可提高文檔處理的效率, 減少資源耗費. 詞項w在時間槽i的文檔頻率計算公式為

dfi(w)=dfi-1(w)+dfci(w),

(2)

其中：ci表示在時間槽i的新聞報道數(shù)量;dfi(w)表示新聞報道集中包含詞項w的文檔數(shù);dfi-1(w)表示在時間槽i之前出現(xiàn)w的文檔數(shù)量. 由式(2)可知, 在每個時間槽能動態(tài)更新文檔頻率可體現(xiàn)出新聞語料的動態(tài)性和時間特性.

每篇報道d被表示為n維向量空間模型, 這里的n是d中含有特征詞項的數(shù)量.d中每個詞項w權重計算公式為

(3)

其中： weight(w,d)表示在報道d中詞項w的權重;tfw表示詞項w在文檔d中出現(xiàn)的頻率;Ni表示在時間i(包括i)之前的所有新聞文檔數(shù)量. 這里對詞項w的詞頻tf進行了歸一化處理, 以防止其偏向長文檔.

文本報道d與話題T之間的內(nèi)容相似度sim(d,T)采用經(jīng)典余弦公式計算, sim(d,T)的取值在0～1間, 相似度值越大, 表明報道與話題的相似性越高, 其報道就越有可能聚類到該話題下； 反之, 報道屬于話題的可能性就越小.

2.2 文本相似度計算

對于新聞報道, 發(fā)布時間是其重要因素. 在相似度計算時, 僅考慮文本內(nèi)容之間的相似度是不夠的. 通常對于某個話題中的報道將會持續(xù)一段時間, 一篇報道的時間與話題的時間越遠, 這篇報道屬于該話題的可能性就越小. 所以, 在話題生成過程中應考慮時間因素來改進相似度計算公式, 以提高聚類的精度. 基于該思想, 本文在計算相似度時考慮了時間因素, 定義為

dis=10/(10+lg(dt-tt+1)),

(4)

其中：dt表示新聞報道的發(fā)布時間;tt表示話題最后的更新時間(指通過聚類得到的話題中新聞報道最新發(fā)布時間). 因此, 本文使用的報道與話題的相似度計算公式為

similarly(d,T)=sim(d,T)×dis.

(5)

由式(5)可知, 在相似度計算中要同時考慮基于內(nèi)容和時間因素的影響.

2.3 改進的Single-Pass聚類算法

通過聚類算法得到的話題中包含有多篇報道, 采用質心向量, 即求該話題中所有文本特征向量的平均值表示該話題的中心向量. 在計算相似度時, 只需將新的報道與話題的中心向量計算相似度值, 而不需要與話題中的每篇報道都進行相似度值的計算, 這樣節(jié)省了大量時間, 提高運算效率. 本文對Single-Pass聚類算法進行改進, 改進算法流程如圖2所示.

圖2 改進的Single-Pass算法流程Fig.2 Flow chart of improved Single-Pass algorithm

3 實驗結果及分析

3.1 實驗語料及環(huán)境

實驗語料： 將基于主題的網(wǎng)絡爬蟲爬取2015-11-01—2015-11-30的新浪新聞數(shù)據(jù)作為數(shù)據(jù)集, 分別為國際、 政治、 體育等方面的新聞, 表1列出了各話題及相關新聞報道數(shù)量. 實驗環(huán)境： 操作系統(tǒng)為Windows 7及以上, 基于JAVA平臺實現(xiàn).

表1 網(wǎng)絡新聞話題語料庫

3.2 評價指標

本文采用TDT評價指標：

漏檢率

PM=C/(A+C),

(6)

錯檢率

PF=B/(B+D),

(7)

其中：A,B分別表示被檢測到的相關文檔數(shù)和不相關文檔數(shù);C,D分別表示未檢測到的相關文檔數(shù)和不相關文檔數(shù). TDT引入耗費函數(shù)對結果進行綜合評價, 定義為

Cdet=CMPMP+CFPF(1-P),

(8)

其中：PM和PF分別表示漏檢率和錯檢率；CM和CF分別表示漏檢率和錯檢率系數(shù), 根據(jù)經(jīng)驗值一般取CM=1,CF=0.1;P表示某報道屬于某話題的先驗概率, 一般取值為P=0.02.

3.3 結果分析

本文對選取的600篇新聞文檔進行實驗分析及參數(shù)調(diào)整. 實驗比較標題中特征加權系數(shù)α的不同取值對話題聚類質量的影響, 結果如圖3所示. 由圖3可見, 當α=3時, 聚類算法的PF和PM取值最小. 因此, 本文中選取α=3. Single-Pass算法中相似度閾值的選取對聚類結果的影響如圖4所示.

圖3 加權系數(shù)α對話題聚類結果的影響Fig.3 Effects of weighting coefficient α on topic clustering results

圖4 相似度閾值對聚類結果的影響Fig.4 Effects of similarity threshold on clustering results

由圖4可見, 隨著閾值的增加, 耗費代價函數(shù)在不斷減少后開始增長, 本文選取耗費函數(shù)值最小點所對應的相似度閾值0.02. 經(jīng)典Single-Pass聚類算法與改進算法的對比結果如圖5所示. 由圖5可見, 改進的Single-Pass方法比經(jīng)典方法的耗費代價小. 本文方法在耗費代價上降低了0.34%, 錯檢率降低了1.57%. 實驗結果表明, 本文方法能更有效、 更準確地實現(xiàn)話題檢測.

圖5 經(jīng)典Single-Pass算法與改進算法的對比結果Fig.5 Comparison results between classical Single-Pass algorithm and improved algorithm

綜上所述, 本文針對新聞報道的特性, 從三方面對Single-Pass算法進行了研究, 只對新增加的文本進行處理, 提高聚類的效率, 減少資源的耗費, 提高了算法實現(xiàn)話題發(fā)現(xiàn)的速度和效果. 實驗結果驗證了本文方法的可行性.

[1] Wayne C L. Multilingual Topic Detection and Tracking: Successful Research Enabled by Corpora and Evaluation [C]//Proceedings of the 2nd International Conference on Language Resources and Evaluation Conference (LREC). Paris: European Language Resources Association, 2000: 1487-1493.

[2] HE Qi, Chang K, Lim E P. A Model for Anticipatory Event Detection [C]//International Conference on Conceptual Modeling. Berlin: Springer-Verlag, 2006： 168-181.

[3] 韓忠明, 陳妮, 樂嘉錦, 等. 面向熱點話題時間序列的有效聚類算法研究 [J]. 計算機學報, 2012, 35(11)： 2337-2347. (HAN Zhongming, CHEN Ni, LE Jiajin, et al. An Efficient and Effective Clustering Algorithm for Times Series of Hot Topics [J]. Chinese Jouranl of Computers, 2012, 35(11)： 2337-2347.)

[4] ZHANG Kuo, ZI Juan, WU Ligang. New Event Detection Based on Indexing-Tree and Named Entity [C]//Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press, 2007： 215-222.

[5] Seo Y W, Sycara K. Text Clustering for Topic Detection [D]. Pittsburgh: Carnegie Mellon University, 2004.

[6] YANG Yiming, Pierce T, Carbonell J. A Study of Retrospective and Online Event Detection [C]//Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM Press, 1998： 28-36.

[7] ZHANG Zhongfeng, LI Qiudan. QuestionHolic： Hot Topic Discovery and Trend Analysis in Community Question Answering Systems [J]. Expert Systems with Applications, 2011, 38(6)： 6848-6855.

[9] 雷震, 吳玲達, 雷蕾, 等. 初始化類中心的增量K均值法及其在新聞事件探測中的應用 [J]. 情報學報, 2006, 25(3)： 289-295. (LEI Zhen, WU Lingda, LEI Lei, et al. IncrementalK-Means Method Based on Initialisation of Cluster Centers and Its Application in News Event Detection [J]. Journal of the China Society for Scientific and Technical Information, 2006, 25(3)： 289-295.)

[10] ZHANG Chen, WANG Hao, CAO Liangliang, et al. A Hybrid Term-Term Relations Analysis Approach for Topic Detection [J]. Knowledge-Based Systems, 2016, 93: 109-120.

[11] Amrutha B, Mintu P. Keyword Based Tweet Extraction and Detection of Related Topics [J]. Procedia Computer Science, 2015, 46: 364-371.