陳美英，周安民

（四川大學(xué)電子信息學(xué)院，成都 610065）

基于改進(jìn)Single-Pass算法的話題發(fā)現(xiàn)技術(shù)研究

陳美英，周安民

（四川大學(xué)電子信息學(xué)院，成都 610065）

為了在海量的移動互聯(lián)網(wǎng)數(shù)據(jù)中自動識別出新聞話題，分析經(jīng)典Single-Pass聚類算法及其不足，提出針對性改進(jìn)方法完成新聞話題發(fā)現(xiàn)。改進(jìn)算法繼承Single-Pass聚類算法的原理，通過對關(guān)鍵信息加權(quán)和引入時間因子提高算法的聚類精度；通過設(shè)置話題中心與待聚類文本比較來降低算法的計算開銷。實驗表明，改進(jìn)后的算法相比于經(jīng)典算法在準(zhǔn)確率、召回率和F值三個指標(biāo)上有所提高。

Single-Pass 聚類算法；TF-IDF；時間因子；話題中心

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展和普及，網(wǎng)絡(luò)成為人們獲取新聞資訊的重要渠道之一。根據(jù)第38次《中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告》的數(shù)據(jù)顯示，截至 2016年 6月，中國網(wǎng)民規(guī)模達(dá) 7.10億，半年共計新增網(wǎng)民 2132萬人；手機(jī)網(wǎng)民規(guī)模達(dá) 6.56億，較 2015年底增加3656萬人[1]。隨著手機(jī)流量資費(fèi)的下降、手機(jī)終端大屏化等應(yīng)用體驗的提升，以手機(jī)作為主要上網(wǎng)終端會成為更多人的選擇。網(wǎng)絡(luò)新聞作為基礎(chǔ)的互聯(lián)網(wǎng)應(yīng)用，用戶規(guī)模保持穩(wěn)健增長，使用率在80%以上。網(wǎng)絡(luò)新聞客戶端是人們在日常生活中關(guān)心國家大事和社會熱點的最簡單直接的工具，大量繁雜甚至無用的網(wǎng)絡(luò)信息也通過新聞客戶端輸送給用戶。那么，如何在海量互聯(lián)網(wǎng)信息中檢測和提取當(dāng)今社會大眾較為關(guān)注的新聞事件話題變得尤為重要。

1 話題發(fā)現(xiàn)研究現(xiàn)狀

話題檢測與跟蹤 （Topic Detection and Tracking，TDT）是一項在日益膨脹的互聯(lián)網(wǎng)新聞信息中對新話題進(jìn)行自動識別和對已知話題保持持續(xù)跟蹤的信息處理技術(shù)，最早由美國國防高級研究計劃署（DARPA）于1996年發(fā)起[2]。

從1998年開始，美國國家標(biāo)準(zhǔn)技術(shù)研究所（NIST）在DARPA的支持下舉辦話題檢測與追蹤國際會議，并進(jìn)行相應(yīng)的測評[3]。此后國外很多機(jī)構(gòu)和學(xué)者開始研究此類技術(shù)。Martijin等人很對語言模型采用話題發(fā)現(xiàn)和相似度計算的方法[4]。NewsInEssence多源新聞文摘系統(tǒng)使用聚類和多文檔自動文摘技術(shù)來發(fā)現(xiàn)話題[5]。IBM公司采用了兩層聚類策略，使用對稱的Okapi公式來對比兩篇新聞報道的相似性[6]。

國內(nèi)在TDT方面的研究起步較晚，但在學(xué)者的努力下至今也取得了豐碩的成果。2004年賈自艷等提出一種動態(tài)進(jìn)化模型的事件探測和追蹤算法[7]。2005年于滿泉等針對新聞事件的特點提出了單粒度話題識別方法，并將基于多層聚類的MLCS算法應(yīng)用在話題組織上[8]。2009年何婷婷等人提出基于兩層聚類的算法和熱度計算公式來發(fā)現(xiàn)熱點話題[9]。

TDT中話題發(fā)現(xiàn)主要針對于傳統(tǒng)聚類算法的選擇試驗和改進(jìn)，其中常用的聚類算法是Single-Pass聚類算法。該算法是一種簡單的增量聚類算法，對比依次輸入的新聞數(shù)據(jù)和已有類的匹配度，將數(shù)據(jù)歸為已有類或創(chuàng)建新的類，實現(xiàn)增量和動態(tài)聚類。

2 算法描述

2.1 Single-Pass聚類算法

Single-Pass聚類算法按文本出現(xiàn)的順序依次處理文本集合D={d1，d2，…，dn}，如果是第一個文本d1，則將該文本作為種子創(chuàng)建一個新的話題；后續(xù)出現(xiàn)的文本di與已有話題比較，并計算相似度θ。如果最大相似度沒有達(dá)到系統(tǒng)預(yù)設(shè)的閾值ε，則判定該文本di是一個新的話題；否則將文本歸到相似度最高的話題中。該算法的流程如圖1所示。了運(yùn)算開銷。另外，為了確保聚類結(jié)果的準(zhǔn)確，需要不斷調(diào)整聚類中心，不斷獲取最優(yōu)的聚類中心。

圖 1 Single-Pass算法流程圖

（3）經(jīng)過對新聞報道文本特征的深入分析，標(biāo)題、人名、地名機(jī)構(gòu)名等對新聞文本有著很高的區(qū)分度；而且新聞的第一段大多是對整片新聞的總結(jié)性概括，也很好地將自身區(qū)別于其他不同報道。因此要對相關(guān)特征詞和文本第一段內(nèi)容賦予更高的權(quán)重，才能更準(zhǔn)確地表示文檔，以此提高聚類的精度?，F(xiàn)在比較普遍的權(quán)重計算方法是TF-IDF權(quán)重表示法。

（4）因為新聞文本具有時效性特點，也許是同一個事件但是發(fā)生的時間不同，如果在聚類是不考慮時間跨度，很容易將不同時期的同一事件歸為一類。因此需要引入時間因子來更好地判斷待聚類文本是否屬于已有聚類話題。

經(jīng)典的Single-Pass聚類算法直觀又易于理解，但是仍有不足之處：

（1）對輸入次序的依賴性很高。針對相同的文本集合，因為輸入的次序不同會有不同的聚類結(jié)果。

（2）計算開銷大，系統(tǒng)效率低。新的需要聚類的文本要與已聚類的每一個文本做相似度計算，隨著后期文本增多，計算量會逐步增大，使得系統(tǒng)的效率低下。

（3）聚類精度不高。由于沒有考慮新聞報道的特殊性，例如新聞時效性特點以及一些特征詞（標(biāo)題、人名、地名、機(jī)構(gòu)名等）的權(quán)重，導(dǎo)致聚類結(jié)果的不理想。

2.2 改進(jìn)的Single-Pass算法

對于上述提出的Single-Pass聚類算法的不足，我們可以做以下的改進(jìn)：

（1）在預(yù)處理要聚類的文本時，可以根據(jù)新聞報道發(fā)布的時間對文本進(jìn)行排序，減小話題在演變過程中新聞報道的不同對話題聚類結(jié)果的影響。

（2）為了避免待聚類文本與已聚類的每一文本比較并計算相似度，首先在已聚類的話題中設(shè)定聚類中心，代表該聚類中所有文本的共有話題[10]。新的待聚類文本只需要和聚類中心比較并計算相似度，大大縮減

3 基于改進(jìn)的Single-Pass新聞話題發(fā)現(xiàn)

話題發(fā)現(xiàn)的流程包括數(shù)據(jù)采集和預(yù)處理、文本向量化、文本聚類等基本步驟。

3.1 數(shù)據(jù)采集與預(yù)處理

數(shù)據(jù)采集是指利用網(wǎng)絡(luò)爬蟲技術(shù)在網(wǎng)絡(luò)上自動獲取并存儲Web網(wǎng)頁的信息。網(wǎng)絡(luò)爬蟲從初始的URL出發(fā)，根據(jù)網(wǎng)絡(luò)之間的鏈接關(guān)系和指定的條件，不斷擴(kuò)展并獲取整個網(wǎng)絡(luò)的頁面信息。一個網(wǎng)頁的信息可以分為兩類，給用戶瀏覽的信息和給瀏覽器識別的標(biāo)記信息。將采集到的HTML源文件內(nèi)容進(jìn)行解析處理，去掉標(biāo)記信息HTML標(biāo)簽和用戶瀏覽信息中鏈接、導(dǎo)航和廣告等對于文本聚類無用的噪聲信息，提取出我們需要的新聞報道標(biāo)題、時間和正文等，最終得到純文本文檔。

為了將新聞報道字詞特征的集合又盡量保持報道本身的內(nèi)容不受影響，本文采用空間向量模型這一種簡單高效的文檔表示模型來規(guī)范地表示新聞報道，詞作為特征項。而漢語中詞和詞之間沒有明確的分隔標(biāo)識，因此要對本文分詞。中文分詞最常用的方法是基于統(tǒng)計的分詞方法和基于字符串匹配的分詞方法。中科院經(jīng)過多年研究開發(fā)出漢語詞法分析系統(tǒng)ICTCLAS（Institute of Computing Technology， Chinese Lexical Analysis System），主要包括中文分詞、此行標(biāo)注、命名實體識別等功能，分詞精度可以達(dá)到98.5%。本文即采用該方法對文本進(jìn)行分詞，隨后去掉不涉及報道內(nèi)容的停用詞。

3.2 文本的向量表示

經(jīng)預(yù)處理后的數(shù)據(jù)仍包含大量無用或重復(fù)的詞，給后續(xù)文本處理帶了難度。特征抽取的目的是在不改變文本原本傳達(dá)的核心信息的情況下識別出能夠標(biāo)識文本原有內(nèi)容、區(qū)別于其他文本的特征項，方便計算，提高處理效率。文檔頻率法是特征抽取最簡單有效的方法，特征分量高于預(yù)定閾值的特征量保留。不同特征項對文本內(nèi)容的貢獻(xiàn)度不同。針對新聞報道，人名、地名、機(jī)構(gòu)名、標(biāo)題和第一段內(nèi)容往往更重要，將被分配更高的權(quán)重。

為了將文本表示為計算機(jī)可以處理的數(shù)字化信息及進(jìn)行特征抽取和加權(quán)處理，本文采用空間向量模型（Vector Space Model，VSM）和TF-IDF算法對文本進(jìn)行處理。

設(shè)每個文檔d表示為一個特征向量公式（1）：

其中ti是該文本的特征項，wi為該特征項的權(quán)值。接下來，我們利用TF-IDF算法來計算特征項的權(quán)值。

TF-IDF（Term Frequency-Inverse Document Frequency）即詞頻-反文檔頻率，其思想是詞頻TF表示詞在文檔中出現(xiàn)的頻率，反文檔頻率IDF表示詞在整個文檔集合里出現(xiàn)的頻率。當(dāng)一個詞在該文檔中出現(xiàn)的頻率高而在其他文檔中出現(xiàn)的頻率低，表示它對該文本的獨(dú)特性貢獻(xiàn)更大，該詞的權(quán)重也應(yīng)更大。TF、IDF的計算公式分別為公式（2）、（3）：

其中fij表示該詞在文檔dj中出現(xiàn)的次數(shù)，Nj表示文檔dj中詞的總數(shù)；N為文檔合集中文檔的總數(shù)，Ni表示包含詞i的文檔的個數(shù)。權(quán)值是TF和IDF的乘積并進(jìn)行歸一化。為了調(diào)整人名、地名、機(jī)構(gòu)名、標(biāo)題和第一段內(nèi)容的權(quán)重值，引入加權(quán)因子Fm={f1，f2，f3，f4，f5}，分別表示以上五項的權(quán)重。即文檔dj中第i個詞的權(quán)重wij表示為公式（4）：

3.3 文本相似度計算

待聚類的文本d和話題T之間的相似度通過計算兩向量之間的夾角余弦值來衡量，用公式（5）表示：

其中，w表示文本或話題的特征項權(quán)重，n是文本或話題不同特征項的總數(shù)。從公式可以看出，向量d和T之間的夾角越小，余弦值就越大，兩者之間的相似度就越大，反之成立。

為了區(qū)分不同時間段的新聞報道而使聚類結(jié)果更精確，我們引入時間距離函數(shù)T（公式6）來計算文本和話題之間的時間距離。

其中，td表示文檔d的發(fā)布時間，tTs是話題T中第一篇新聞報道的時間，tTe是話題T中最新一篇新聞報道的時間。加入時間距離函數(shù)之后的相似度計算公式（7）如下：

基于以上公式，本文既考慮了文本和話題的內(nèi)容相似度，也從時間上判斷兩者是否應(yīng)該歸為一類。其中α+β=1，經(jīng)過大量試驗，α=0.8時聚類效果最好，這也印證了文本內(nèi)容相似度在聚類中更為重要的作用。

3.4 文本聚類

將第一篇新聞文本作為初始的話題中心，然后處理下一篇報道d，根據(jù)以上的流程和方法，將文本表示為空間向量模型。根據(jù)相似度公式可以計算出文本d與全部已有話題的話題中心之間的相似度，通過比較可以找到相似度最大的話題Tm，此時的相似度為Sm。系統(tǒng)在開始時已經(jīng)設(shè)定好閾值ε，如果Sm大于閾值，將文本歸于該話題Tm。反之，d作為新的話題中心設(shè)置新的話題，并參與之后的文本處理。在輸入文本d確定自身所屬聚類話題之后，需要比較新文本d與聚類中心的特征項數(shù)量，如果新文本d特征項數(shù)量大于原聚類中心，那么將新文本d作為新的聚類中心進(jìn)行接下來的聚類。重復(fù)以上過程直到文本處理完畢，聚類完成。

4 實驗結(jié)果分析

4.1 實驗數(shù)據(jù)

本文的實驗語料來自手機(jī)App騰訊新聞的數(shù)據(jù)。實驗主要爬取了騰訊新聞2016年下半年數(shù)據(jù)，包括以下10個新聞話題：中國女排奪冠、三星note7爆炸、杭州G20、阿里月餅門、網(wǎng)約車新政、美國大選、樸槿惠閨蜜門、林丹出軌、卡斯特羅去世、羅一笑事件。其中每個話題的報道100篇，并加入作為干擾的報道100篇，共計1100篇報道。

4.2 實驗評價指標(biāo)

評價實驗方法性能的常用指標(biāo)有準(zhǔn)確率P、召回率R和F值。準(zhǔn)確率是指系統(tǒng)正確識別的報道占文檔總數(shù)的比例，也就是查準(zhǔn)率；召回率是指系統(tǒng)正確識別的話題的報道數(shù)占語料庫中該話題實際的報道數(shù)的比例，也就是查全率；可以看出準(zhǔn)確率和召回率是一對矛盾的值。F值是準(zhǔn)確率P和召回率R的調(diào)和平均，如公式8所示：

4.3 實驗結(jié)果及分析

基于以上實驗方法、數(shù)據(jù)及評價方法，應(yīng)用經(jīng)典的Single-Pass算法對實驗數(shù)據(jù)進(jìn)行聚類的結(jié)果如表1所示，準(zhǔn)確率、召回率和F值分別為79.1%、80.1%和79.5%。

表 1經(jīng)典Single-Pass算法實驗結(jié)果

經(jīng)過改進(jìn)的Single-Pass算法的實驗結(jié)果如表2所示，準(zhǔn)確率、召回率和F值分別為82.6%、83.6%和83.1%。

表 2改進(jìn)Single-Pass算法實驗結(jié)果

圖2用柱狀圖清晰地表示出改進(jìn)方法相比于經(jīng)典方法在各項評價指標(biāo)上的優(yōu)勢。

圖2 兩種方法實驗指標(biāo)對比

以上實驗結(jié)果對比可知，由于在數(shù)據(jù)處理時運(yùn)用特征項加權(quán)和引入時間因子的文本向量更好地表征了文本報道要表達(dá)的語義，為文本聚類提供了更優(yōu)的條件，改進(jìn)Single-Pass算法的準(zhǔn)確率、召回率和F值均高于經(jīng)典的Single-Pass算法。

5 結(jié)語

本文以經(jīng)典的Single-Pass聚類方法為基礎(chǔ)，針對2016年騰訊新聞數(shù)據(jù)進(jìn)行話題發(fā)現(xiàn)研究。話題發(fā)現(xiàn)方法的一般流程是數(shù)據(jù)采集和預(yù)處理、文本向量化、文本聚類等。經(jīng)典的Single-Pass聚類方法雖然簡單直觀，但是仍然存在聚類精度不高的問題，本文在文本向量表示時加權(quán)各個對文本思想表達(dá)重要的特征項，并加入時間影響因子，來提高新聞聚類的精度；針對計算開銷大的問題，本文將已有話題歸納話題中心并不斷更新，文本向量與話題中心的對比取代與每個文本的對比，減小計算開銷。經(jīng)過對數(shù)據(jù)的實驗驗證，改進(jìn)的Single-Pass方法在準(zhǔn)確率、召回率、F值方面有了較好的改善，肯定了文本研究的價值。

參考文獻(xiàn)：

[1]中國互聯(lián)網(wǎng)絡(luò)信息中心 、新華網(wǎng)等綜合匯編.CNNIC發(fā)布第38次《中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告》[J].中國教育網(wǎng)絡(luò)，2016，09:16.

[2]洪宇，張宇，劉挺，李生.話題檢測與跟蹤的評測及研究綜述[J].中文信息學(xué)報，2007，06:71-87.

[3]Allan J，Lavrenko V，Connell M E.A Month to Topic Detection and Tracking in Hindi[J].ACM Transactions on Asian Language Information Processing（TALIP），2003，2（2）:85-100.

[4]Spitters M，Kraaij W.TNO at TDT2001:Language Model-Based Topic Detection[J]，2001.

[5]Fung G P C，Yu J X，Yu P S，et al.Parameter Free Bursty Events Detection in Text Streams[C].Proceedings of the 31st International Conference on Very Large Data Bases.VLDB Endowment，2005:181-192.

[6]Allan J.Introduction to Topic Detection and Tracking[M].Topic Detection and Tracking.Springer US，2002:1-16.

[7]賈自艷，何清，張海俊，李嘉佑 ，史忠植.一種基于動態(tài)進(jìn)化模型的事件探測和追蹤算法[J].計算機(jī)研究與發(fā)展，2004，07:1273-1280.

[8]于滿泉，駱衛(wèi)華，許洪波，白碩.話題識別與跟蹤中的層次化話題識別技術(shù)研究[J].計算機(jī)研究與發(fā)展，2006，03:489-495.

[9]劉星星，何婷婷，龔海軍，陳龍.網(wǎng)絡(luò)熱點事件發(fā)現(xiàn)系統(tǒng)的設(shè)計[J].中文信息學(xué)報，2008，06:80-85.

[10]馬國棟，李慧.基于改進(jìn)Single-Pass算法的BBS熱點話題發(fā)現(xiàn)[J].首都師范大學(xué)學(xué)報（自然科學(xué)版），2014,06:13-17.

Research on Topic Discovery Based on Improved Single-Pass Algorithm

CHEN Mei-ying，ZHOU An-min
（College of Electronics and Information Engineering，Sichuan University，Chengdu 610065）

Aiming at the automatic identification of news topic in massive mobile internet data,analyzes the classical single-pass clustering algorithm and its disadvantages,and puts forward the pertinent improvement method to finish the news topic detection.The improved algorithm inherits the principle of Single-Pass clustering algorithm,and improves the clustering accuracy by weighting the key information and adds the time factor,reduces the computational cost of the algorithm by setting the center of the topic to compare with the text to be clustered.Experiment results show that the improved algorithm has higher accuracy,recall and F value than the classical algorithm.

Single-Pass Clustering Algorithm;TF-IDF;Time Factor;Topic Center

1007-1423（2017）09-0018-05

10.3969/j.issn.1007-1423.2017.09.005

陳美英（1992-），女，甘肅嘉峪關(guān)人，碩士，研究方向為數(shù)據(jù)處理和Web開發(fā)

2017-01-17

2017-03-10