基于动态窗口的微博突发话题检测方法

李艳红 贾丽娜 王素格 李德玉

(山西大学计算机与信息技术学院 山西 太原 030006)(计算智能与中文信息处理教育部重点实验室 山西 太原 030006)

0 引 言

近年来，微博社交平台的迅速发展，极大地影响了人们的社交方式。国外著名的微博平台Twitter自上线以来注册用户已经突破5亿，月活跃用户数已达3.35亿[1]。新浪官方网站显示，2017年新浪微博月活跃用户数已达3.76亿，日活跃用户数为1.65亿[2]。由于在微博平台上发表和转发信息迅速便捷，很多突发性话题会在微博平台上最先出现，迅速传播，并引起广泛的社会共鸣。因此针对微博文本流的突发话题检测可以为民意感知、舆情检测和应急处置提供数据支持和技术保障，具有积极的理论和现实意义[3]。

目前，微博突发话题检测方法大致分为以文档为中心的方法[4-7]和以特征为中心的方法[8-14]。以文档为中心的方法的基本思路是对文本进行聚类，将有突发状态的类簇视为突发话题。如Petrovic 等[4]提出一种基于LSH(locality sensitive hashing)的推特文本聚类算法。算法将新到达的推特文本和历史推特文本关联成推特链，通过计算每个推特文本链的增长速率来检测是否发生突发事件，在对推特流的处理速度上取得了较好的效果。Li等[5]提出一种增量时间主题模型，通过对话题的时间信息建模来检测突发话题，并能够跟踪突发话题随时间的漂移情况。随后，Li等[6]对增量时间主题模型进行改进，引入微博文本的主题标签，提高了模型的精度。Huang等[7]利用局部加权线性回归方法估计单词的新颖度和衰减度，使用LDA(Latent Dirichlet Allocation)模型对微博进行主题建模，进而发现主题的突发度和衰减度，同时可以实现突发话题的追踪。在以文档为中心的方法中，由于微博一般限制在140字以内，导致内容短小，因此容易产生数据稀疏性问题。以特征为中心的方法重点在于检测突发话题在实时数据流上随时间变化的突发特征。如Schubert等[8]使用散列技术跟踪词对频率的平均值与标准差来识别突发词对，进而对一天之内检测到的突发词对聚类形成突发话题。该方法可以在有限内存中跟踪数据流中所有词对的变化情况，缓解了内存的压力。由于微博中包含大量网络新词、口语化词或串，为了提高对这些新词和口语化串的召回率，申国伟等[9]提出了非中文分词的微博突发话题检测框架，采用高阶联合聚类算法检测突发话题，在检测突发话题的同时，能够获取话题的关联消息和话题参与的用户。郑斐然等[10]提出一种基于突发词增量聚类的微博新闻话题检测算法，利用词频和词频的增长速度确定突发词。但是增量式聚类算法对突发词输入顺序敏感，影响突发词聚类准确率。郭跇秀等[11]对文献[10]进行改进，结合词语权重和用户影响力定义词的突发度，利用凝聚式层次聚类算法对突发词聚类识别突发话题,提高了突发话题检测的准确率，但是凝聚式层次聚类算法时间复杂度较高。以上以突发特征为中心的方法采用定长滑动窗口，在滑动窗口结束时才有可能检测到突发话题，无法很好地满足突发话题检测实时性的应用需求。

研究人员针对微博突发话题检测已经开展了很多有意义的研究工作，但是仍然存在以下问题需要深入研究：(1) 由于对突发话题的检测具有实时性的应用需求，因此如何减少突发话题检测的时间延迟是当前需要解决的问题。(2) 已有的微博突发话题检测方法通常采用定长滑动窗口技术，由于这种数据流分段方法没有考虑突发话题持续范围，滑动窗口的大小难以确定，因此势必对突发话题的检测带来影响。所以，如何确定突发话题的范围也是研究难点之一。

针对以上挑战，本文提出一种基于动态窗口的微博突发话题检测方法。该方法对微博中的词对加速度进行实时检测，由于无需比较当前窗口与历史窗口中词频的变化，所以在早期就可以发现突发话题。此外，本文提出一种基于动态窗口的检测机制，根据突发词对单位时间内出现的数量，也就是突发词对的速度来确定“突发词对窗口”范围，通过合并交叉、重叠、相邻的“突发词对窗口”得到突发话题窗口。最后利用改进的非负矩阵分解[15](Nonnegative Matrix Factorization，NMF)聚类方法捕获突发话题窗口中微博的主题结构。

1 问题的形式化定义

2 突发特征和突发话题窗口

由于微博文本流中突发话题和其他一般话题是同时存在的，因此如何将突发话题和一般话题区分开来显得尤为重要。一般话题往往以平稳的速度出现在微博文本流中，而突发话题伴随着突发事件的发生而出现，相关微博出现的速度会明显增大。由于速度的变化快慢可以用“加速度”来刻画，当突发话题出现时，相关微博出现的加速度会明显增大，而一般话题的相关微博出现的加速度几乎为零，因此，使用“加速度”识别突发特征检测突发话题的出现是可行的。

传统的微博突发话题检测方法[10-11,16]通常采用单个词作为突发特征检测突发话题。由于词对可以体现某些行为发生的主谓或动宾结构[17]，与单个词比较而言，包含了更多的话题信息，例如：(贵州，发生)，(天然气，爆炸)，(发生，爆炸)。因此，本文将词对的加速度作为突发特征。下面依次给出词对频率、词对速度、词对加速度以及突发词对的定义。

定义1 微博(di,ti)中任意词对(wp,wq)的频率fi(wp,wq)计算式表示为：

(1)

式中：分母表示从di中任意选择两个词的组合数；分子表示从di中选择两个特定词的组合数。

(2)

(3)

式中：ΔT1<ΔT2,并且ΔT1和ΔT2两个时间片的终止时间均为ti时刻。

直观上，微博文本流中突发词对出现的速度在一定程度上反映了突发话题的热度。如果在一个连续时间段内，某个突发词对的速度均不小于某个阈值，那么我们称这个时间段内的微博集合为该突发词对所对应的突发词对窗口。

定义5 突发词对BWPp,q对应的突发词对窗口W的定义如下：

(4)

突发话题检测过程中，可能会出现多个交叉、重叠和相邻的突发词对窗口，则认为这些突发词对窗口中的微博关联于同一突发话题。因此，将这些突发词对窗口进行合并，得到突发话题窗口。

定义6 若存在count个交叉、重叠或者相邻的突发词对窗口W1,W2,…,Wcount，那么突发话题窗口DW的定义为：

(5)

根据定义5、定义6可知，突发话题窗口的范围是由微博文本流中突发词对的速度决定的，是动态变化的。

3 突发话题检测

3.1 检测框架

为了实时检测微博文本流中的突发话题，本文提出了一种基于动态窗口的微博突发话题检测框架，如图1所示。突发话题检测过程主要由突发特征识别、动态窗口确定和突发话题窗口聚类三个阶段组成。

图1 突发话题检测框架

突发特征识别是突发话题检测与其他话题检测的主要区别，本文将词对加速度作为突发特征。当有新的微博到达时，进行突发特征识别，即统计微博中所有词对的频率、更新词对速度表，并计算词对的加速度。如果词对的加速度超出给定阈值，该词对被标记为突发词对。

检测到突发词对后，根据突发词对的出现速度来确定该突发词对出现比较频繁的时间区间，即确定突发词对窗口。当出现多个交叉、重叠、相邻的突发词对窗口时，对这些窗口内的微博进行合并，从而得到突发话题窗口。

为了获取突发话题窗口中微博的主题结构，本文采用改进的NMF聚类方法对窗口中的微博进行聚类分析。该方法采用具有强鲁棒性特征的l2,1范数设计短文本聚类模型的优化求解目标函数，可以降低短文本噪声数据对聚类结果的影响，与传统的K-meanes和LDA方法相比，该方法具有较好的短文本聚类效果[15]。

3.2 词对速度表

图2 词对速度表

当新的微博到达时，更新词对速度表T，并计算词对的加速度，根据词对加速度的大小来确定是否出现突发词对。

3.3 检测算法

基于图1的突发话题检测框架，本文设计了一种基于动态窗口的突发话题检测算法(Bursty Topic Detection based on Dynamic Window,DW-BTD)，如算法1所示。

（二）把握调价时机，确定调价依据。调价的依据。（1）医疗服务成本变动达到10%以上时启动调价程序；（2）从上次定价截止目前，CPI累计上升8-10%时应该启动调价程序；（3）财政补助方式、标准发生变化时应该调整；（4）技术难度和风险系数增加时应该调价；（5）国家政策影响医疗机构收入或支出结构发生变化时应该调整。如医药分开核算，取消药品及卫生材料加成时。（6）医疗服务价格调整受群众支付能力、医保支付能力、社会价格水平控制等方面影响。应选择适当的时机与方式进行。选择恰当的执行时间。

算法1 突发话题检测算法

输入：微博文本流D，时间片ΔT1和ΔT2，词对加速度阈值μ，突发词对速度阈值φ，合并窗口个数阈值c，聚类数目k

输出：类中心矩阵P和文本隶属度矩阵Q

步骤2 突发词对窗口集合确定 对每一个BWPp,q，根据定义5确定突发词对窗口W，并判断突发词对窗口之间是否交叉、重叠或相邻。

步骤4 突发话题窗口聚类 使用改进的NMF聚类算法对DW内的微博聚类，得到类中心矩阵P和文本隶属度矩阵Q。

4 实验与结果分析

4.1 测试环境与实验数据

目前面向微博文本流的突发话题检测没有标准语料集和标注结果，本文使用的实验数据来自新浪微博。我们编写网络爬虫程序爬取了从2017年6月01日到2017年6月30日期间的38万余条微博，并对微博文本流中的突发话题进行了标注。

在提取微博的文本信息和发布时间、生成微博文本数据流之后，对微博文本进行了预处理，首先删除文本中的表情符号、URL、“@用户”，然后利用Python中的中文分词模块Jieba对微博文本进行分词和去除停用词处理，最后删除副本以及少于三个词的微博。预处理后得到35万余条实验数据，其中包括57个突发话题，每个话题的持续时间在0.5小时到10小时之间。将已标注的微博数据根据时间划分成三个数据集(FT_DB、MT_DB、LT_DB)进行实验，数据特征如表1所示。

表1 数据特征

4.2 突发话题检测算法性能评价

为了评价算法的性能，将本文提出的DW-BTD算法与已有的两种突发话题检测算法在上述三个数据集上作了对比实验。实验中算法DW-BTD的参数取值为：词对加速度阈值μ=0.15，突发词对速度阈值φ=5.0，突发词对窗口合并数阈值c=4，聚类数目k=8，ΔT1=15分钟，ΔT2=30分钟。本文对两种对比算法进行参数调整后与本文方法在同一环境下做对比实验。文献[10]提出了一种基于定长滑动窗口的突发话题检测算法(BIC)，实验中突发词权重阈值取30，增量聚类阈值取200，定长滑动窗口大小为3小时。文献[11]对文献[10]的检测算法进行了改进，但也是基于定长滑动窗口的检测算法INF，实验中突发词权重阈值取3.0，簇间距离阈值取600，定长滑动窗口大小为3小时。

4.2.1 DW-BTD算法的P、R和F1值

图3为本文算法与BIC、INF两种算法在三个数据集上突发话题检测准确率P、召回率R和F1三种指标的对比结果。三种指标的计算式表示为：

(6)

(7)

(8)

式中:SS是算法检测正确的突发话题个数；CC是算法检测到的突发话题个数；RR是已标注的突发话题个数。

(a) FT_DB

(b) MT_DB

(c) LT_DB图3 三种检测算法的准确率P、召回率R、F1值

由图3可知，本文提出的DW-BTD算法在三个数据集上的P、R和F1值都明显高于BIC、INF算法。通过对实验数据的分析，发现突发话题的持续时间是不可预知的，而BIC、INF算法均采用定长滑动窗口，导致滑动窗口难以与突发话题相对应。因此“滑动窗口大小”的确定是算法应用的难点。DW-BTD算法基于动态窗口技术，很好地解决了这一问题。例如实验中“伦敦高层公寓楼失火”这一突发话题持续时间为32分钟，而BIC、INF算法中滑动窗口大小为3小时，导致这两个算法均未检测到该突发话题。

由图3可知，INF算法的P、R和F1值比BIC算法均有所提升。这是由于INF算法一方面在抽取突发词时考虑了微博用户的影响力；另一方面在对突发词聚类时，采用凝聚式层次聚类，避免了对突发词输入顺序的依赖。

4.2.2 DW-BTD算法的实时性

为了评价算法的实时性，我们对比了本文提出的DW-BTD算法和BIC、INF算法对同一突发话题的检出时间。

图4给出了六个突发话题单位时间相关微博数量随时间的变化情况，以及三种算法的检出时间。可以看出，DW-BTD算法在突发话题发生的早期就可以检测到，检出时间比BIC和INF算法提前了至少30分钟。这是由于BIC和INF算法在检测突发话题时，需要检测当前窗口与历史窗口中对应词频的变化情况，所以只有在滑动窗口结束时才有可能检测到突发话题，而DW-BTD算法是对微博中词对的加速度进行实时检测，当加速度超过设定阈值时便可以发现突发话题。图4(b)中，DW-BTD算法的检出时间比BIC和INF算法提前了3小时，这是因为BIC和INF算法的滑动窗口恰好是从12:00:00到15:00:00，所以15:00:00才检测到突发话题。

(a) 唐杰忠去世

(b) 北大女硕士在美失踪

(c) 丰县幼儿园门口爆炸

(d) 第一篇高考满分作文出炉

(e) 四川茂县山体滑坡

(f) 国乒集体退赛图4 突发话题检测实时性

4.2.3 动态窗口的性能评价

突发话题窗口是由count个交叉重叠、相邻的突发词对窗口合并而成的，为了评价突发话题窗口的动态性，本文统计了DW-BTD算法检测出的六个突发话题的突发话题窗口范围。表2列举了每个突发话题(BT)的持续时间(TC)、算法检测出的合并突发词对窗口个数(count)、突发话题窗口起始时间(TS)、终止时间(TE)和突发话题窗口范围(SC)。

表2 突发话题窗口范围

从表2中可以看出，对于不同的突发话题，算法检测出的突发话题窗口起始、终止时间以及范围大小均不同。这是由于DW-BTD算法是根据突发词对速度的变化趋势动态地确定突发话题窗口范围，窗口范围与突发话题基本匹配，体现了窗口的动态性。

4.2.4 突发话题的主题结构

为了获取突发话题的主题结构，采用改进的NMF聚类算法对突发话题窗口中的微博聚类。表3列举了BIC、INF和DW-BTD三种算法在MT_DB数据集中检测出的三个突发话题。通过对突发话题窗口中的微博进行聚类分析，DW-BTD算法得到的突发话题的主题结构如表3所示。例如：对于“唐杰忠去世”这一突发话题，算法检测出了五个突发词对，合并突发词对窗口得到突发话题窗口。对突发话题窗口中的微博聚类后得到一个类中心矩阵P和一个文本隶属度矩阵Q。P中一列代表一类，即一个主题，从P中选取包含突发词对的列，得到表3所示的三个类，也就是突发话题“唐杰忠去世”的主题结构。这三类分别对应突发话题的三个主题：(1) 关于相声艺术家唐杰忠患癌去世的消息；(2) 对唐老师生前相声作品的讨论；(3) 针对如何有效预防癌症的讨论。

表3 突发话题的主题结构

4.3 参数μ对突发话题检测的影响

为了分析词对加速度阈值μ对DW-BTD算法突发话题检测准确率P、召回率R和F1的影响，本文在FT_DB、MT_DB、LT_DB三个数据集上进行了实验。

本文设置加速度阈值μ取0.05～0.25之间不同的值进行实验，DW-BTD算法的P、R和F1值如表4所示。

表4 不同μ值下的P、R和F1值

从表4中可以看出，随着μ值的增大，突发话题检测的准确率上升，召回率降低。这是由于实验数据中突发话题的强度大小不同，阈值μ增大，导致部分突发强度较低的话题被算法过滤。由表4可知，当阈值μ取0.15时，本文实验结果最优。

5 结 语

本文提出了一种基于动态窗口的微博突发话题检测方法。首先通过实时检测微博文本流中词对的加速度大小来判断是否有突发话题发生，减少了突发话题检测的时间延迟；其次基于突发词对的速度变化动态地确定突发话题窗口范围，提高了突发话题检测的准确率和召回率；最后利用改进的NMF聚类算法对窗口中的微博进行聚类，得到了突发话题的主题结构。在微博文本流上的对比实验验证了本文方法的有效性。