基于改進Single-Pass算法的話題發現技術研究

陳美英，周安民

（四川大學電子信息學院，成都 610065）

基于改進Single-Pass算法的話題發現技術研究

陳美英，周安民

（四川大學電子信息學院，成都 610065）

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

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

0 引言

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

1 話題發現研究現狀

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

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

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

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

2 算法描述

2.1 Single-Pass聚類算法

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

圖 1 Single-Pass算法流程圖

（3）經過對新聞報道文本特征的深入分析，標題、人名、地名機構名等對新聞文本有著很高的區分度；而且新聞的第一段大多是對整片新聞的總結性概括，也很好地將自身區別于其他不同報道。因此要對相關特征詞和文本第一段內容賦予更高的權重，才能更準確地表示文檔，以此提高聚類的精度。現在比較普遍的權重計算方法是TF-IDF權重表示法。

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

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

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

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

（3）聚類精度不高。由于沒有考慮新聞報道的特殊性，例如新聞時效性特點以及一些特征詞（標題、人名、地名、機構名等）的權重，導致聚類結果的不理想。

2.2 改進的Single-Pass算法

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

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

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

3 基于改進的Single-Pass新聞話題發現

話題發現的流程包括數據采集和預處理、文本向量化、文本聚類等基本步驟。

3.1 數據采集與預處理

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

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

3.2 文本的向量表示

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

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

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

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

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

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

3.3 文本相似度計算

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

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

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

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

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

3.4 文本聚類

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

4 實驗結果分析

4.1 實驗數據

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

4.2 實驗評價指標

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

4.3 實驗結果及分析

基于以上實驗方法、數據及評價方法，應用經典的Single-Pass算法對實驗數據進行聚類的結果如表1所示，準確率、召回率和F值分別為79.1%、80.1%和79.5%。

表 1經典Single-Pass算法實驗結果

經過改進的Single-Pass算法的實驗結果如表2所示，準確率、召回率和F值分別為82.6%、83.6%和83.1%。

表 2改進Single-Pass算法實驗結果

圖2用柱狀圖清晰地表示出改進方法相比于經典方法在各項評價指標上的優勢。

圖2 兩種方法實驗指標對比

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

5 結語

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

參考文獻：

[1]中國互聯網絡信息中心 、新華網等綜合匯編.CNNIC發布第38次《中國互聯網絡發展狀況統計報告》[J].中國教育網絡，2016，09:16.

[2]洪宇，張宇，劉挺，李生.話題檢測與跟蹤的評測及研究綜述[J].中文信息學報，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]賈自艷，何清，張?？?，李嘉佑 ，史忠植.一種基于動態進化模型的事件探測和追蹤算法[J].計算機研究與發展，2004，07:1273-1280.

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

[9]劉星星，何婷婷，龔海軍，陳龍.網絡熱點事件發現系統的設計[J].中文信息學報，2008，06:80-85.

[10]馬國棟，李慧.基于改進Single-Pass算法的BBS熱點話題發現[J].首都師范大學學報（自然科學版），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-），女，甘肅嘉峪關人，碩士，研究方向為數據處理和Web開發

2017-01-17

2017-03-10