基于实时词共现网络的微博话题发现

李亚星 王兆凯 冯旭鹏 刘利军 黄青松

摘要：针对微博的实时性、稀疏性和海量性特点，提出基于实时词共现网络的话题发现模型。首先，从原始语料中筛选出主题词集合，再利用时间参数计算共现主题词的关系权重以实现词共现网络的构建，通过该网络推算出与话题关联性强的潜在特征词以解决微博特征词的稀疏性； 其次，采用改进SinglePass算法实现话题增量聚类；最后，对每个话题的主题词按热度计算进行排序，获得最具代表性的话题主题词。实验结果表明，该模型与经典SinglePass聚类算法相比，话题发现准确率约提高6%，综合指标提高8%。实验结果证明所提模型的有效性和准确性。

关键词：话题发现；实时共现网络；短文本；SinglePass聚类；热度计算

中图分类号：TP391.1 文献标志码：A

Abstract：In view of the realtime， sparse and massive characteristics of microblog， a topic discovery model based on realtime cooccurrence network was proposed. Firstly， the set of keywords was extracted from the primitive data by the model， and the relationship weights was calculated on the basis of the time parameter to structure the word cooccurrence network. Then， sparsity could be reduced by finding potential features of a strong correlation based on weight adjustment coefficient. Secondly， the topic incremental clustering could be achieved by using the improved SinglePass algorithm. Finally， the feature words of each topic were sorted by heat calculation， so the most representative keywords of the topic were got. The experimental results show that the accuracy and comprehensive index of the proposed model increase 6%， 8% respectively compared with the SinglePass algorithm. The experimental results prove the validity and accuracy of the proposed model.

Key words：topic discovery； realtime cooccurrence network； short text； SinglePass cluster； hot degree calculation

0 引言

微博以其惊人的传播速度和传播范围以及积极的社会影响力吸引不少人的眼球。其中，跟踪和分享新鲜事是用户使用微博的一个很重要的目的[1]。由于微博较强的即时性和交互性，突发新闻在微博上的传播速度非常快，对于影响力较大的新闻事件，参与评论转发的用户量也很大，使得微博能够先于传统新闻媒体作出反应，成为一个信息流量相当大的平台，但是其内容非常散乱，数据噪声较大。因此及时发现微博热点话题并进行监管，对营造一个温馨、健康、稳定的社会环境有重大的作用和意义，同时，还可以为网络精准营销和广告推荐等新型营销手段奠定基础。

话题发现研究总体上包含两类：基于概率的话题模型和基于聚类算法。贺亮等[2]利用文档主题生成模型 LDA（Latent Dirichlet Allocation）抽取科技文献话题，然后计算话题的强度和影响力，最后针对冷门和热门话题以及影响力高和影响力低的话题进行了趋势分析。同时也有很多文献将作者信息或者参考文献信息等特征用于LDA实现话题发现。单斌等[3]就LDA话题模型作了一个综述，作为一种非监督方法，LDA话题模型能够自动获取海量文本信息的主题或话题，具有实际应用的前景，同时提及大多数话题演化方法都假设话题数目是固定的，无法探测新话题的产生，旧话题的消亡和分裂。

骆卫华等[4]在相对成熟算法的基础上，提出基于分治多层聚类的话题发现算法；刘星星等[5]采用SinglePass聚类算法设计了一个网络热点事件发现系统；黄九鸣等[6]基于信息流时序特征和上下文相关度，设计了基于SinglePass聚类模型的会话在线抽取算法（SinglePass based on Frequency and Correlation， SPFC）。SinglePass算法在话题检测方面成为经典[7]。同时，文献[8-11]在传统聚类的基础上进行改进。有研究使用密度函数进行聚类中心的初始化以便客观地选择初始化中心，使得结果受语料被处理顺序的影响较小，或者引入对内容结构和语义的分析，将分析结果进行聚类。聚类算法针对文本稀疏性和上下文依赖性的解决方法主要有两类[12]：第一类是借助外部文本如搜索引擎结果扩展短文本；第二类是借助知识库如WordNet和Wikipedia等，挖掘短文本中词语之间的内在联系。第一类方法消耗时间较长，且对搜索引擎的结果非常依赖；第二类方法可以发现词库里的词义关系，但是对词库里不存在的词无法解决。

为快速有效发现话题，出现了词共现网络用于话题发现的研究。蒙祖强等[13]基于小世界理论建立词共现网络模型并去除大量冗余词，然后运用极大相容块技术并基于过滤后的词共现网络实现对相交话题的提取，从而获取网络话题。但微博拥有海量数据，且更新频繁，使得此方法用于微博话题发现适用性不强。

针对上述方法存在的问题，本文提出基于实时词共现网络话题发现模型（Word Cooccurrence SinglePass Topic Model， CWSTM），有效解决主题特征词稀疏的问题，该模型基于实时词共现网络发现关联性强的潜在特征词，采用改进SinglePass算法实现话题聚类，最后为了避免词集过长，利用热度计算公式对每个话题涉及的词进行降序排列。经过多次测试表明，前55%的词基本涵盖了每一类的主要话题。

1 基于CWSTM的话题发现方法

基于CWSTM的话题发现主要分为实时词共现网络构建、话题聚类、热度排序三个子任务，其流程如图1所示。对采集到的文本通过词性标注和权重计算实现词共现网络的构建，该网络为整个CWSTM模型建立基础，目的是发现关联性强的潜在特征词。其次，采用改进SinglePass算法实现话题聚类，最后按热度计算进行排序，过滤掉话题中热度较低的词。

1.1 构建实时词共现网络

词共现网络的相关研究早期来源于复杂网络领域，应用相对广泛的是在情报学领域。文献[14-15]针对不同研究领域，给出了不同共现网络的构建过程，并对网络结构特征进行了分析。本文认为，所谓的词共现网络可以理解成一个三元带权图G=〈V，E，P〉，即最简单的共现网络的形式是两点一边一权值，例如x和y分别表示主题词，e=（x， y）表示主题词x和y同时出现在文本的一句话中， p表示一对主题词在词共现网络中的权值。

词共现网络构建在现有的词汇集合和词关系矩阵[15]的基础上引入带时间系数的权重计算。首先对语料库中的文本进行分词和词性标注。如“台风“灿鸿”被称60年来7月登陆浙江的最强台风。受“灿鸿”影响，东海南部海域已出现10～12级大风，并继续增加，台风中心风力可达14～17级。”标记为“台风/n， “/w， 灿/ag， 鸿/ag， ”/w， 被/p， 称/v， 60年/m， 来/v， 7月/m， 登陆/v， 浙江/ns， 的/uj， 最/d， 强台风/n，。/w， 受/v， “/w， 灿/ag， 鸿/ag， ”/w， 影响/vn，，/w， 东海/ns， 南部/f， 海域/n， 已/d， 出现/v， 10/m， -， 12级/m， 大风/n，，/w， 并/c， 继续/v， 增加/v，，/w， 台风/n， 中心/n， 风力/n， 可达/nz， 14/m， -， 17级/m，。/w”。然后筛选出具有实际意义名词和动词统称为主题词，作为待研究对象放入微博词汇集合，如L={f1， f2，…， fn}表示微博的集合， f={g1，g2，…，gn}表示一篇微博中词汇的集合。如图2所示。

但是，经典SinglePass中存在一些缺陷：相似度计算时需要将新微博与每一类的所有微博进行比较，计算量较大，且用于短文本聚类时特征词过于稀疏。针对以上问题，本模型首先构建实时词共现网络，发现关联性较强的潜在特征词。其次在经典SinglePass算法中引入“簇中心”思想。“簇中心”定义：簇中心C是最能代表本聚类中所有微博话题的特征词集合Ci={w1，w2，…}。新微博只与“簇中心”进行相似度比较，而不是与聚类中的每一篇文本进行相似度比较，从而减少计算量。若sim（di，dj）小于阈值θ（经典SinglePass聚类设定θ=0.25），则将其分配到相似度最大的话题聚类中；若sim（di，dj）均大于θ，则作为一个新的话题种子。新微博的特征词（Fw）与原“簇中心”（C）进行比较时，若 “簇中心”不能全面表示出类中所有微博的话题，要不断优化“簇中心”。具体方式如下：1）当新微博的特征词个数（FwN）小于等于“簇中心”特征词个数时，“簇中心”不发生改变； 2）当新微博的特征词个数大于“簇中心”时，需要拿新微博和“簇中心”分别与本类中的微博依次进行相似度计算并求和，得到新微博微博综合相似度F1和“簇中心”微博综合相似度F2，若F1

算法1 “簇中心”更新算法。

3 结语

本文提出基于CWSTM模型的微博话题发现方法，针对微博实时性和稀疏性等特点，构建实时词共现网络获得与话题关联性强的潜在特征词，采用“簇中心”的SinglePass算法实现增量聚类，然后通过热度计算对每个话题涉及的词进行降序排列，过滤掉话题中代表性不强的干扰性主题词。该方法的特点是构建实时词共现网络，实时更新并且获取与话题关联性强的潜在特征词，使短文本聚类结果的准确度有所提高。实验结果表明CWLTM模型的综合指标优于无网络的SinglePass方法约8个百分点。后续工作是研究如何更好地构建词共现网络来提高潜在特征词的质量。

参考文献：

[1]KWAK H， LEE C， PARK H. What is Twitter， a social network or a news media？[C]// WWW 2010： Proceedings of the 19th International Conference on World Wide Web. New York： ACM， 2010：591-600.

[2]贺亮， 李芳.基于话题模型的科技文献话题发现和趋势分析[J].中文信息学报， 2010， 26（2）：109-115.（HE L， LI F. Topic discovery and trend analysis in scientific literature based on topic model [J]. Journal of Chinese Information Processing， 2010， 26（2）：109-115.）

[3]单斌， 李芳.基于LDA话题演化研究方法综述[J].中文信息学报， 2010， 24（6）： 43-49.（SHAN B， LI F. A survey of topic evolution based on LDA [J]. Journal of Chinese Information Processing， 2010， 24（6）： 43-49.）

[4]骆卫华， 于满泉， 许洪波， 等.基于多策略优化的分治多层聚类算法的话题发现研究[J].中文信息学报， 2005， 20（1）：29-35.（LUO W H， YU M Q， XU H B， et al. The study of topic detection based on algorithm of division and multilevel clustering with multistrategy optimization [J]. Journal of Chinese Information Processing， 2010， 20（1）： 29-35.）.

[5]刘星星， 何婷婷， 龚海军， 等.网络热点事件发现系统的设计[J].中文信息学报， 2008， 22（6）： 80-85. （LIU X X， HE T T， GONG H J， et al. Design of hot Web event detection system [J]. Journal of Chinese Information Processing， 2008， 22（6）： 80-85.）

[6]黄九鸣， 吴泉源， 刘春阳， 等.短文本信息流的无监督会话抽取技术[J].软件学报， 2012， 23（4）：735-747. （HUANG J M， WU Q Y， LIU C Y， et al. Unsupervised conversation extraction in short text message streams[J]. Journal of Software， 2012， 23（4）： 735-747.）

[7]YANG Y M， PIERCE T， CARBONELL J. A study of retrospective and online event detection[C]// SIGIR 1998： Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 1998.28-36.

[8]雷震， 吴玲达， 雷蕾， 等.初始化类中心的增量K均值法及其在新闻事件探测中的应用[J].软件学报， 2006， 25（3）：289-295.（LEI Z， WU L D， LEI L， et al. Incremental Kmeans method based on initialisation of cluster centers and its application in news event detection [J]. Journal of Software， 2006， 25（3）： 289-295.）

[9]SALTON G， WONG A， YANG C S. A vector space model for automatic indexing [J]. Communications of the ACM， 1975， 18（11）： 613-630.

[10]洪宇， 张宇， 范基礼， 等.基于语义域语言模型的中文话题关联检测[J].软件学报， 2008， 19（9）：2265-2275.（HONG Y， ZHANG Y， FAN J L， et al. Chinese topic link detection based on semantic domain language model [J]. Journal of Software， 2008， 19（9）： 2265-2275.）

[11]刘振鹿， 王大玲， 冯时， 等.一种基于LDA的潜在语义区划分及Web文档聚类算法[J].中文信息学报， 2011， 25（1）：60-65.（LIU Z L， WANG D L， FENG S， et al. An approach of latent semantic space partition and Web document clustering [J]. Journal of Chinese Information Processing， 2011， 25（1）： 60-65.）

[12]张志飞， 苗夺谦， 高灿.基于LDA主题模型的短文本分类方法[J].计算机应用， 2013， 33（6）：1587-1590. （ZHANG Z F， MIAO D Q， GAO C. Short text classification using latent Dirichlet allocation [J]. Journal of Computer Applications， 2013， 33（6）：1587-1590.）

[13]蒙祖强， 黄柏雄.一种新的网络热点话题提取方法[J].小型微型计算机系统， 2013， 34（4）：743-748. （MENG Z Q， HUANG B X. Novel approach to Internet hot topic extraction [J]. Journal of Chinese Computer Systems， 2013， 34（4）：743-748.）

[14]杨菲， 黄柏雄.词共现网络的遗传聚类在话题发现中的应用[J].计算机工程与应用，2013， 49（14）：126-129.（YANG F， HUANG B X. Application of GCA of word cooccurrence network in topic detection [J]. Computer Engineering and Applications， 2013， 49（14）：126-129.）

[15]余传明， 周丹.情感词汇共现网络的复杂网络特性分析[J].情报学报，2010， 29（5）：906-914.（YU C M， ZHOU D. The complexity analysis of the emotional word cooccurrence network [J]. Journal of the China Society for Scientific and Technical Information， 2010， 29（5）：906-914.）

[16]PAPKA R， ALLAN J. Online new event detection using single pass clustering[EB/OL]. [20150210]. http：//maroo.cs.umass.edu/getpdf.php？id=28.