基于改进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）