基于改進Single-pass算法的新聞話題演化跟蹤算法

李天怡 應文豪

摘要：隨著信息技術的發展，每天都有大量的新聞文本在互聯網上發布、轉發，在這樣的海量信息環境下，如何快速定位自己感興趣的話題、追蹤其發展趨勢已成了近年來的研究熱點。面向互聯網上新聞文本，提出聚類閾值的估計方法對已有的Single-pass算法進行優化，進而基于時間片設計一個新聞文本演化算法。在新華網等四個網站上采集新聞數據并進行實驗，實驗表明所提算法可有效跟蹤新聞話題的演化過程。

關鍵詞：Single-pass算法; 網絡爬蟲; 聚類; 演化; 跟蹤

中圖分類號：TP311? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）10-0026-04

Abstract：With the development of information technology， a large number of news texts are published and forwarded on the Internet every day. In such a massive information environment， how to make people quickly locate and understand their topics of interest become a hot issue in recent years.For news texts on the Internet， a clustering threshold estimation method is proposed to optimize the existing Single-pass algorithm， and then a news text evolution algorithm is designed based on the time slice.News data on four websites including Xinhua net was collected and experimented. The experiments show that the proposed algorithm can effectively track the evolution of news topics.

Key words： single-pass algorithm; Web Crawler; clustering; evolution; track

1 引言

新聞報道是人們了解社會發展的趨向、生活演進的動態、事件變化過程的主要途徑。近年來，由于萬物互聯的互聯網高速發展，越來越多的媒體平臺把社交網絡作為新聞報道傳播的主要載體。當重大事件發生時，各大媒體網站將發布大量的相關新聞報道。對于某些熱點話題，人們相互發表不同的觀點，并對該話題加工并轉發，于是話題下的消息呈爆發式的擴散。例如2019年7月的香港《逃犯條例》風波發生后，人們紛紛評論轉發該事件的相關報道，一時間，該話題占領了各大新聞網站的頭條。對于這樣的熱點話題，從新聞媒體方來說，一般會建立新聞專題服務，實現分眾傳播模式，但專題的建立一般是通過人工方式實現，人工建立新聞專題這種模式效率低下，十分不適應新聞門戶的產出需求[1]。從用戶方來說，互聯網信息量巨大，如何找到自己需要的信息，如何快速地了解熱點話題的發展變化過程，如何持續跟進自己感興趣的熱點話題的后續，都是需要解決的問題。通常，熱點話題從產生開始就會隨著時間的推移不斷演化，有的話題會在熱度持續期內演化出其他相關的熱點事件，而有的話題會因為熱度下降從而被淹沒在互聯網的海量信息中，致使用戶很難再發現其發展過程和追蹤其子事件。基于上述問題，本文結合網絡爬蟲、文本處理、聚類等領域的方法，對已有的Single-pass算法進行優化，提出聚類閾值的估計方法，進而基于時間片設計一個新聞文本演化算法用來對新聞話題演化歷程進行追蹤。

2 相關工作

對基于文檔的話題檢測任務[2]，首先是對文本特征建模的研究，張曉艷等人[3]基于信息的劃分越細系統的性能越高這個主張，提出了多向量文本表示模型，即從每個文本中抽出十類富含信息的詞組生成十個向量，再對這十個向量整合來表示一篇新聞的文本向量。但基于向量空間模型（VSM）的特征表示忽略了詞與詞之間順序關系，實際上，詞序也蘊含了很大一部分的語義信息，屈慶濤等人[4]針對傳統的向量空間模型提出了基于N元語法（N-Gram語言模型）的特征建模。充分利用了語序信息對文本特征進行表示，有效提高了話題檢測的準確度。但是基于N元語法的模型過于消耗計算資源，需要MapReduce等大數據分布計算模型作為支撐，所以并不具有普適性。

對于話題建模，文本聚類是較為常用的發現算法。目前，適用于文本領域的分類算法主要有四種[5]，即基于劃分的聚類算法、基于層次的聚類算法、基于增量的聚類算法和基于圖模型的聚類算法。但基于新聞文本的多樣性、實時性等特點，對新話題的追蹤更多使用的是基于增量的聚類算法。陳龍等[6]針對K-means在新聞聚類里初始話題數K不確定、聚類過程不穩定等問題提出了基于話題相似性改進的K-means新聞聚類算法，該算法優化了聚類初始中心的選擇來保證初始點的差異性足夠大，從而使得算法不會收斂于局部最優，并且通過預測新聞話題覆蓋率來自動生成K值，使得該算法在話題發現任務中發揮更穩定。魏德志等[7]在Single-pass聚類的思想上提出了基于時間片劃分的方法，基于時間序列的話題模型更加接近現實話題的生命周期特性，降低主題空間隨著新詞的加入而產生的話題漂移現象。

3 基于改進Single-pass算法的話題演化跟蹤模型

3.1文本特征建模

用新聞文本代表新聞事件進行處理的前提是有合適的模型來表示新聞文本。本文將采用詞袋模型對新聞文本建模進行研究。傳統的one-hot模型使用文檔集R所有的詞作為模型的維度，使用0-1（表示文本中詞的出現與否）作為每個維度的值，將文檔D向量化表示為（其中，R[={D1，D2，…，DX，…DM}]代表文檔集，[D=w1，w2，…，ws，…，wn]代表一個文檔，R*=[W1，W2，…，WS，…，WN]代表由文檔集中所有詞組成的詞集，[ws]代表D中的詞項，[WS]代表R*中的詞項）：

但此模型忽略了詞頻對文本的影響，所以本文將使用TF-IDF權值來代替0-1值。TF-IDF實際分為兩部分：TF（Term-Frequency）詞頻、IDF（Inverse- Document-Frequency）逆文檔頻率：

詞頻表示詞在文檔中出現的次數，一般來說，詞頻越高說明該詞越能接近該文檔所表述的主題，但如果僅以詞頻作為權值的話會使得結果更偏向于那些包含更多詞的長文本，并且篩選出的詞更具有普遍性而非區分性。所以，需要引入IDF來懲罰那些更具有普遍性的詞。詞頻在文檔中代表重要性特征，而逆文檔頻率在整個空間中代表了詞的區分度特征。最后，文檔特征向量的權值表示為：

3.2 文檔聚類

話題即是一系列圍繞著相似內容的文檔集合，因此可通過信息聚類技術幫助獲得相似文檔集合。新聞話題追蹤系統的擴展性需求和性能需求要求聚類算法需要有以下兩個特征：（1）當有新文檔集加入后無須重復計算。（2）無法提前確定聚類的結果數量。所以，基于增量的聚類算法是最適合需求的，而其中最為常用的聚類算法為Single-Pass，其特點為單遍聚類，對文檔數量遞增的聚類需求極為友好。

傳統的Single-Pass聚類算法描述如下：

根據上述描述可得，基于核心操作[disDX，Di]，此算法的時間復雜度為[O（n2）]，且實際效果并不樂觀，以下將從新聞文本的特殊結構、距離函數、相似閾值、時間復雜度等方面對傳統的Single-Pass算法進行優化，使其獲得更好的聚類效果。

對于類簇[Ci]，判斷文檔是否屬于[Ci]需要與[Ci]中的每個文檔相比較，非常影響聚類算法的效率，并且如果以類簇中相似度最大的文檔作為依據的話，會使聚類中心發生偏移，影響類簇的聚合程度。所以本文將類簇的聚類中心[centroidCi]作為評判標準，通過此操作可以將聚類算法的時間復雜度降至[Onm，m=Ci?n]，且聚類中心更不易發生偏移。

可以看到，Single-Pass算法的效果極度依賴于閾值[θ]的取值。所以本文基于數據來估計[θ]值的方法。首先，引入聚類效果的評價指標——輪廓系數[8]，其計算方法如下：

對于簇中的每個向量，分別計算它們的輪廓系數;

對于其中的一個點[i]來說：

計算[ai= averagei向量到所有它屬于的簇中其它點的距離]

計算

[bi=mini向量到與它相鄰最近的一簇內的所有點的平均距離]

那么[i]向量輪廓系數就為：

將所有點的輪廓系數相加并求平均值，就得到了評估該聚類效果的總輪廓系數。輪廓系數介于[[0，1]]，其值隨著類里的聚合度的增大與類間的分離度增大而增大。即輪廓系數越接近1，聚類的效果越好。然后我們使用一個從0.1開始、1.0結束、步長為0.05的[θ]列表重復聚類，每次聚類生成本次輪廓系數，最后選擇輪廓系數最大的[θ]即可，如圖1所示。

綜上，優化后的Single-Pass算法如下：

3.3 話題演化

話題是由種子事件演化出的一系列事件的集合，而話題演化就是具體、詳細地確定這種事件演化之間的狀態轉移關系。顯然地，根據新聞的時序特征，本文設話題內第一個發生的事件為種子事件，話題內所有其他事件都直接或間接地與種子事件存在此依賴關系。再根據新聞的周期性，將話題分配到話題周期的各個時間段中。

根據以上假設，基于時間片的貪心策略，設計出以下話題演化算法：

此算法假設每個事件最多可以只有一個父事件，且每個時間片內的事件相互獨立，彼此不會發生演化（同周期內的新聞事件發生狀態轉移概率較低）。當且僅當與該事件最相似的前時間片內事件相似度超過閾值時，該事件才被分配為父事件。

4 實驗結果

4.1數據獲取

本文爬蟲模塊采用python的scrapy框架來實現，爬取cctv、新京報、新華網、環球時報這4個新聞網站。由于爬蟲爬到的網頁數據是雜亂無章且數據冗余的，所以需要對數據進行清洗。具體的清洗對象包括：（1）