基于改進(jìn)Single-pass算法的新聞話題演化跟蹤算法

李天怡 應(yīng)文豪

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

關(guān)鍵詞：Single-pass算法; 網(wǎng)絡(luò)爬蟲; 聚類; 演化; 跟蹤

中圖分類號：TP311? ? ? ? 文獻(xiàn)標(biāo)識碼：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 引言

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

2 相關(guān)工作

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

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

3 基于改進(jìn)Single-pass算法的話題演化跟蹤模型

3.1文本特征建模

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

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

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

3.2 文檔聚類

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

傳統(tǒng)的Single-Pass聚類算法描述如下：

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

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

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

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

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

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

計算

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

那么[i]向量輪廓系數(shù)就為：

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

綜上，優(yōu)化后的Single-Pass算法如下：

3.3 話題演化

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

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

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

4 實驗結(jié)果

4.1數(shù)據(jù)獲取

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