基于MapReduce的大规模话题网络提取分析＊

刘 热

（无锡科技职业学院软件与服务外包学院，江苏无锡 214008）

随着Web2.0技术的飞速发展，微博作为一种新兴媒体，已经成为人们信息共享和搜索的重要方式。人们不但可以利用微博发布信息，还可以在微博上搜索信息，收看各种实时新闻资讯。在Web2.0时代，微博兼有博客和即时通讯两种Web服务的优点，它允许用户在网络上实时发布信息，而发布信息的用户的关注者会实时收到该信息。Twitter，作为世界上拥有注册用户和活跃用户最多的微博平台，到2012年6月已经拥有超过5亿的注册用户，并且用户数量仍在快速增长。

由于微博平台中包含数以亿计的用户，且这些用户每天在微博上频繁地更新自己的状态信息，于是产生了海量的微博信息。在海量的微博信息中，有一部分消息是相关的，他们是对于某一事件的描述和评论，这些消息就构成了对某一热点话题的讨论。在微博平台中，面对海量的微博信息，如何发现用户所关心的话题是社会网络研究领域的热点问题。在话题发现（也叫话题检测）中，可以将微博信息看作文档，然后利用文本检索和聚类技术对话题进行检测［1－3］。由于每条微博信息只包含不到140个字符，因此采用文档模型建立起来的矩阵非常稀疏，并且聚类分析得到的结果也不能令人满意。在微博信息中，相同的话题往往包含相同的词汇，如果将每条微博信息看作一个节点，将包含相同的词汇的两个节点间建立一个链接，那么这些微博信息就可以构成一个网络，通过对该网络进行社团挖掘便可以发现系统中隐含的热点话题。

在上述话题网络的构建过程中，由于微博信息量大，传统的分布式或并行系统并不能很好地满足系统的性能要求。MapReduce编程模型［4］是Google公司提出的，其专门用于数据密集型数据处理。Hadoop［5］作为MapReduce编程模型的开源实现，近几年在工业界和学术界都引起了高度的重视和广泛的研究。本文采用Hadoop平台作为数据处理的平台，研究了如何在海量的微博数据中利用MapReduce编程模型实现话题网络的提取。

1 相关工作

1.1 话题检测

话题检测是从成千上万的用户发言中将发言内容分类，并将重要的类别识别出来的过程，是社会网络研究领域的重要内容。常用的模型有向量空间模型、差异概率模型［6］和LDA模型［7］。

向量空间模型［8－9］是将文本文档看作由一个个单词构成的序列，在这些单词序列中，单词之间是有顺序的。因此一个文档集合就可以看作一个矩阵，应用聚类方法就可以对文档进行分类，然后提取出文档所包含的话题。差异概率模型［8］是一种简单有效的分析微博中话题的模型，该模型等价于经典的带有特征选择和时序差别权重的向量空间模型。

LDA（latent dirichlet allocation）［7］模型作为文本分析模型被广泛采用在微博话题检测中［10－14］。Huang等［10］提出一种基于LDA的微博话题检测模型，并采用单趟的聚类方法。Lin等［11］提出了一种基于LDA的概率模型框架——JST（joint sentiment－topic）。区别于文献［10］的是，文献［11］不但可从微博中挖掘出用户发言内容形成的话题，还可以分析出用户的情感。文献［10］和［11］都采用了LDA模型检测微博中的话题，但是他们没有考虑时间变化对话题的影响。Zhang等［12］将时间变量引入到LDA模型中，提出了一种时变的话题检测和分解模型。Song等［13］通过对搜索引擎返回的结果根据话题进行排序，从而将更适合的内容返回给用户。Liu等［14］在检测话题时不但考虑微博内容，还考虑了用户之间的网络结构，提出了一种基于贝叶斯网络的话题——用户社团联合模型。

1.2 网络提取

网络提取是从大量信息中提取出实体及实体间的相互关系。Mori等［15］提出了一种为实体间的关系自动添加标签的社会网络提取算法。Hamasaki等［16］提出了一种混合的社会网络提取方法，该方法综合运用了user－registered Know－link networks，Web－mined Web－link networks和face－to－face Touch－link networks 3种网络提取方法。基于用户间的往来邮件，Culotta等［17］设计了一个端到端的邮件社会网络提取系统。为提取和挖掘学者间的学术社会网络，Tang等［18－19］设计了一个学术网络提取系统——ArnetMiner。Mika［20］设计了一个在线社会网络的提取、聚合和可视化系统——Flink。Matsuo等［21］设计了一个社会网络提取系统——POLYPHONET，该系统不但可提取社会网络结构，还可检测用户簇，且可获得用户的关键字。

1.3 MapReduce

MapReduce［4］是一种并行编程模型，该模型应用大规模并行计算机系统并行地处理海量的数据，其主要应用于数据密集型的批处理系统。MapReduce可以自动地实现任务的底层操作，如任务分配、数据存储、数据流动和系统的容错，它对程序员只提供简单的计算接口。

在MapReduce系统中，任务被分为Map，Shuffle和Reduce 3个部分。在Map阶段，系统从数据源读取数据，或者从上一次的Reduce结果读取一系列的键／值对，通过编程人员自定义的Mapper函数实现数据的独立并行处理，并将结果以键／值对的形式输出。对于每一个输入的键／值对，Mapper函数经过计算，输出若干个键／值对。在Shuffle阶段，系统将Mapper阶段的输出数据集按照键组合在一起，将相同键值的键／值对组成一个组合，并将不同的组合作为下一阶段的输入。在Reduce阶段，系统通过编程人员自定义的Reducer函数对每一个包含相同键值的组合进行处理，并把结果存入到磁盘，或作为下一次Map的输入。在MapReduce系统中，任务通过Map，Shuffle和Reduce 3个阶段在系统中迭代进行，直至算法终止。

2 基于MapReduce话题网络提取模型

2.1 话题网络提取模型

由于每条微博信息由多个词汇组成，且同一词汇可能包含在多个话题中，如图1中的wordp，wordq，wordr和words，它们分别包含在topic1＆topick，topic1＆topic2和topic2＆topick中。如果将微博信息作为节点，信息和信息间共享的词汇作为边，可得到图2无向网络。在这个无向网络中，节点表示用户的微博发言，节点间的边表示发言之间的共享词汇。由于两个发言可能包含多个相同词汇，故两个节点间可能有多条重复边。如果将边上的词汇去掉，用两个节点间的边的个数来表示这两个节点的边的权重，图2可进一步化为如图3所示的加权无向网络。

图1 微博信息网络结构图Fig.1 Graph of Microblog information network

图2 转化的微博信息网络结构图Fig.2 Derived graph of Microblog information network

图3 转化的加权微博信息网络结构图Fig.3 Derived weighted graph of Microblog information network

2.2 MapReduce话题网络提取算法

在MapReduce系统中，Shuffle阶段由系统内部实现，用户通过Mapper函数和Reducer函数实现海量数据的批处理。在Mapper函数中，系统将微博信息作为输入，并给每个信息一个编号，然后将每个信息的单词作为键，将信息的编号作为值发射出去；在Reducer函数中，系统将包含相同单词（Mapper函数的键）的信息编号收集起来，然后在这些信息两两之间建立一条边，并将单词作为边的属性发射出去，得到的便是一个无向的图。上述话题提取模型的算法如下。

3 实验与分析

为了对本文提出的基于MapReduce的话题网络构建方法进行验证，笔者采集了2013年2月15日到20日的数据，共收集了204 376条微博发言信息。在应用本文的方法进行网络提取后得到了一个包含3 483个节点和21 753条边的无向加权网络。

首先，对构建的网络进行分析，分别分析了该网络的度分布和PageRank值分布，其分布图分别为图4和图5。图4中纵轴表示节点的度，图5中纵轴表示节点的PageRank值，这两个图的横轴均表示节点的个数。从图中可以看出，该网络的度分布和PageRank值分布都服从幂率分布，即只有少数的计算点有很大的值，而大多数节点的度或PageR－ank值都很小，是典型的社会网络结构。

图4 网络的度分布图Fig.4 Degree distribution of network

图5 网络的PageRank值分布图Fig.5 PageRank distribution of network

为了进一步验证本文提出的算法对话题网络的构建的准确性，本文对网络的隐含话题的准确性进行了对比。本实验对本文提出的基于MapReduce构建的话题网络进行了话题检测，同时采用经典的LDA模型对话题进行了检测，核对了二者在话题检测时的查准率（Precision）和召回率（Recall）。从图6所示的实验结果可以看出，基于MapReduce构建的话题网络的潜在话题要优于基于LDA模型的潜在话题。

图6 话题检测准确性对比图Fig.6 Accuracy comparison of topic detection

4 结语

微博中包含数以亿计的用户，这些用户每天在微博中频繁发言，在这些海量的用户发言中蕴含着许多热点话题。在话题的检测过程中，可以通过向量空间模型或LDA进行检测。此外由于用户间相同的话题往往包含相同的词汇，这些词汇作为微博信息链接的桥梁可以构成话题网络。本文研究了应用MapReduce编程模型构建微博信息的话题网络。实验表明，基于MapReduce构建的话题网络符合社会网络的相关性质，并且其话题预测的准确性也高于基于LDA模型的话题检测。

［1］ SOOP M，FRYKSMARK U，KOSTER M，et al.The incidence of adverse events in Swedish hospitals：a retrospective medical record review study［J］.International Journal for Quality in Health Care，2009，21（4）：285－291.

［2］ ZHU Xingwei，MING Zhaoyan，ZHU Xiaoyan，et al. Topic hierarchy construction for the organization of multi－source user generated contents［C］／／Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM，2013：233－242.

［3］ ALLAN J，PAPKA R，LAVRENKO V.On－line new event detection and tracking［C］／／Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM，1998：37－45.

［4］ DEAN J，GHEMAWAT S.MapReduce：simplified data processing on large clusters［J］.Communications of the ACM，2008，51（1）：107－113.

［5］ SHVACHKO K，KUANG H R，RADIA S，et al. The hadoop distributed file system［C］／／Mass Storage Systems and Technologies，2010IEEE 26th Symposium on IEEE，2010：1－10.

［6］ BECKER J，KUROPKA D.Topic－based vector space model［C］／／Proceedings of the 6th International Conference on Business Information Systems，2003：7－12.

［7］ BLEI D M，NG A Y，JORDAN M I.Latent dirichlet allocation［J］.Journal of Machine Learning Research，2003，3：993－1022.

［8］ ALLAN J，WADE C，BOLIVAR A.Retrieval and novelty detection at the sentence level［C］／／Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2003：314－321.

［9］ HE Qi，CHANG Kuiyu，LIM E P，et al.Keep it simple with time：a reexamination of probabilistic topic detection models［J］.IEEE Transactions on Pattern A－nalysis and Machine Intelligence，2010，32（10）：1795－1808.

［10］ HUANG Bo，YANG Yan，MAHMOOD A，et al. Microblog topic detection based on LDA model and single－pass clustering［C］／／Rough Sets and Current Trends in Computing.Berlin and Heidelberg：Springer，2012：166－171.

［11］ LIN Chenghua，HE Yulan，EVERSON R，et al. Weakly supervised joint sentiment－topic detection from text［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24（6）：1134－1145.

［12］ ZHANG Jianwen，SONG Yangqiu，ZHANG Changshui，et al.Evolutionary hierarchical dirichlet processes for multiple correlated time－varying corpora［C］／／Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2010：1079－1088.

［13］ SONG Yangqiu，PAN Shimei，LIU Shixia，et al. Topic and keyword re－ranking for LDA－based topic modeling［C］／／Proceedings of the 18th ACM Conference on Information and Knowledge Management. ACM，2009：1757－1760.

［14］ LIU Yan，NICULESCU－MIZIL A，GRYC W.Topic－link LDA：joint models of topic and author community［C］／／Proceedings of the 26th Annual International Conference on Machine Learning.ACM，2009：665－672.

［15］ MORI J，TSUJISHITA T，MATSUO Y，et al.Extracting relations in social networks from the web using similarity between collective contexts［C］／／The Semantic Web－ISWC 2006.Berlin and Heidelberg：Springer，2006：487－500.

［16］ HAMASAKI M，MATSUO Y，ISHIDA K，et al. Community focused social network extraction［C］／／The Semantic Web－ISWC 2006.Berlin and Heidelberg：Springer，2006：155－161.

［17］ CULOTTA A，BEKKERMAN R，MCCALLUM A. Extracting social networks and contact information from email and the web［C］／／Proceedings of CEAS－1.2004：1－8.

［18］ TANG Jie，ZHANG Jing，YAO Limin，et al.Arnet－Miner：extraction and mining of academic social networks［C］／／Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2008：990－998.

［19］ TANG Jie，ZHANG Duo，YAO Limin.Social network extraction of academic researchers［C］／／Data Mining，2007.ICDM 2007.Seventh IEEE International Conference on IEEE，2007：292－301.

［20］ MIKA P.Flink：semantic web technology for the extraction and analysis of social networks［J］.Web Semantics：Science，Services and Agents on the World Wide Web，2005，3（2）：211－223.

［21］ MATSUO Y，MORI J，HAMASAKI M，et al. POLYPHONET：an advanced social network extraction system from the web［J］.Web Semantics：Science，Services and Agents on the World Wide Web，2007，5（4）：262－278.