基于MapReduce的大規(guī)模話題網(wǎng)絡(luò)提取分析＊

劉 熱

（無錫科技職業(yè)學(xué)院軟件與服務(wù)外包學(xué)院，江蘇無錫 214008）

隨著Web2.0技術(shù)的飛速發(fā)展，微博作為一種新興媒體，已經(jīng)成為人們信息共享和搜索的重要方式。人們不但可以利用微博發(fā)布信息，還可以在微博上搜索信息，收看各種實時新聞資訊。在Web2.0時代，微博兼有博客和即時通訊兩種Web服務(wù)的優(yōu)點，它允許用戶在網(wǎng)絡(luò)上實時發(fā)布信息，而發(fā)布信息的用戶的關(guān)注者會實時收到該信息。Twitter，作為世界上擁有注冊用戶和活躍用戶最多的微博平臺，到2012年6月已經(jīng)擁有超過5億的注冊用戶，并且用戶數(shù)量仍在快速增長。

由于微博平臺中包含數(shù)以億計的用戶，且這些用戶每天在微博上頻繁地更新自己的狀態(tài)信息，于是產(chǎn)生了海量的微博信息。在海量的微博信息中，有一部分消息是相關(guān)的，他們是對于某一事件的描述和評論，這些消息就構(gòu)成了對某一熱點話題的討論。在微博平臺中，面對海量的微博信息，如何發(fā)現(xiàn)用戶所關(guān)心的話題是社會網(wǎng)絡(luò)研究領(lǐng)域的熱點問題。在話題發(fā)現(xiàn)（也叫話題檢測）中，可以將微博信息看作文檔，然后利用文本檢索和聚類技術(shù)對話題進(jìn)行檢測［1－3］。由于每條微博信息只包含不到140個字符，因此采用文檔模型建立起來的矩陣非常稀疏，并且聚類分析得到的結(jié)果也不能令人滿意。在微博信息中，相同的話題往往包含相同的詞匯，如果將每條微博信息看作一個節(jié)點，將包含相同的詞匯的兩個節(jié)點間建立一個鏈接，那么這些微博信息就可以構(gòu)成一個網(wǎng)絡(luò)，通過對該網(wǎng)絡(luò)進(jìn)行社團挖掘便可以發(fā)現(xiàn)系統(tǒng)中隱含的熱點話題。

在上述話題網(wǎng)絡(luò)的構(gòu)建過程中，由于微博信息量大，傳統(tǒng)的分布式或并行系統(tǒng)并不能很好地滿足系統(tǒng)的性能要求。MapReduce編程模型［4］是Google公司提出的，其專門用于數(shù)據(jù)密集型數(shù)據(jù)處理。Hadoop［5］作為MapReduce編程模型的開源實現(xiàn)，近幾年在工業(yè)界和學(xué)術(shù)界都引起了高度的重視和廣泛的研究。本文采用Hadoop平臺作為數(shù)據(jù)處理的平臺，研究了如何在海量的微博數(shù)據(jù)中利用MapReduce編程模型實現(xiàn)話題網(wǎng)絡(luò)的提取。

1 相關(guān)工作

1.1 話題檢測

話題檢測是從成千上萬的用戶發(fā)言中將發(fā)言內(nèi)容分類，并將重要的類別識別出來的過程，是社會網(wǎng)絡(luò)研究領(lǐng)域的重要內(nèi)容。常用的模型有向量空間模型、差異概率模型［6］和LDA模型［7］。

向量空間模型［8－9］是將文本文檔看作由一個個單詞構(gòu)成的序列，在這些單詞序列中，單詞之間是有順序的。因此一個文檔集合就可以看作一個矩陣，應(yīng)用聚類方法就可以對文檔進(jìn)行分類，然后提取出文檔所包含的話題。差異概率模型［8］是一種簡單有效的分析微博中話題的模型，該模型等價于經(jīng)典的帶有特征選擇和時序差別權(quán)重的向量空間模型。

LDA（latent dirichlet allocation）［7］模型作為文本分析模型被廣泛采用在微博話題檢測中［10－14］。Huang等［10］提出一種基于LDA的微博話題檢測模型，并采用單趟的聚類方法。Lin等［11］提出了一種基于LDA的概率模型框架——JST（joint sentiment－topic）。區(qū)別于文獻(xiàn)［10］的是，文獻(xiàn)［11］不但可從微博中挖掘出用戶發(fā)言內(nèi)容形成的話題，還可以分析出用戶的情感。文獻(xiàn)［10］和［11］都采用了LDA模型檢測微博中的話題，但是他們沒有考慮時間變化對話題的影響。Zhang等［12］將時間變量引入到LDA模型中，提出了一種時變的話題檢測和分解模型。Song等［13］通過對搜索引擎返回的結(jié)果根據(jù)話題進(jìn)行排序，從而將更適合的內(nèi)容返回給用戶。Liu等［14］在檢測話題時不但考慮微博內(nèi)容，還考慮了用戶之間的網(wǎng)絡(luò)結(jié)構(gòu)，提出了一種基于貝葉斯網(wǎng)絡(luò)的話題——用戶社團聯(lián)合模型。

1.2 網(wǎng)絡(luò)提取

網(wǎng)絡(luò)提取是從大量信息中提取出實體及實體間的相互關(guān)系。Mori等［15］提出了一種為實體間的關(guān)系自動添加標(biāo)簽的社會網(wǎng)絡(luò)提取算法。Hamasaki等［16］提出了一種混合的社會網(wǎng)絡(luò)提取方法，該方法綜合運用了user－registered Know－link networks，Web－mined Web－link networks和face－to－face Touch－link networks 3種網(wǎng)絡(luò)提取方法?；谟脩糸g的往來郵件，Culotta等［17］設(shè)計了一個端到端的郵件社會網(wǎng)絡(luò)提取系統(tǒng)。為提取和挖掘?qū)W者間的學(xué)術(shù)社會網(wǎng)絡(luò)，Tang等［18－19］設(shè)計了一個學(xué)術(shù)網(wǎng)絡(luò)提取系統(tǒng)——ArnetMiner。Mika［20］設(shè)計了一個在線社會網(wǎng)絡(luò)的提取、聚合和可視化系統(tǒng)——Flink。Matsuo等［21］設(shè)計了一個社會網(wǎng)絡(luò)提取系統(tǒng)——POLYPHONET，該系統(tǒng)不但可提取社會網(wǎng)絡(luò)結(jié)構(gòu)，還可檢測用戶簇，且可獲得用戶的關(guān)鍵字。

1.3 MapReduce

MapReduce［4］是一種并行編程模型，該模型應(yīng)用大規(guī)模并行計算機系統(tǒng)并行地處理海量的數(shù)據(jù)，其主要應(yīng)用于數(shù)據(jù)密集型的批處理系統(tǒng)。MapReduce可以自動地實現(xiàn)任務(wù)的底層操作，如任務(wù)分配、數(shù)據(jù)存儲、數(shù)據(jù)流動和系統(tǒng)的容錯，它對程序員只提供簡單的計算接口。

在MapReduce系統(tǒng)中，任務(wù)被分為Map，Shuffle和Reduce 3個部分。在Map階段，系統(tǒng)從數(shù)據(jù)源讀取數(shù)據(jù)，或者從上一次的Reduce結(jié)果讀取一系列的鍵／值對，通過編程人員自定義的Mapper函數(shù)實現(xiàn)數(shù)據(jù)的獨立并行處理，并將結(jié)果以鍵／值對的形式輸出。對于每一個輸入的鍵／值對，Mapper函數(shù)經(jīng)過計算，輸出若干個鍵／值對。在Shuffle階段，系統(tǒng)將Mapper階段的輸出數(shù)據(jù)集按照鍵組合在一起，將相同鍵值的鍵／值對組成一個組合，并將不同的組合作為下一階段的輸入。在Reduce階段，系統(tǒng)通過編程人員自定義的Reducer函數(shù)對每一個包含相同鍵值的組合進(jìn)行處理，并把結(jié)果存入到磁盤，或作為下一次Map的輸入。在MapReduce系統(tǒng)中，任務(wù)通過Map，Shuffle和Reduce 3個階段在系統(tǒng)中迭代進(jìn)行，直至算法終止。

2 基于MapReduce話題網(wǎng)絡(luò)提取模型

2.1 話題網(wǎng)絡(luò)提取模型

由于每條微博信息由多個詞匯組成，且同一詞匯可能包含在多個話題中，如圖1中的wordp，wordq，wordr和words，它們分別包含在topic1＆topick，topic1＆topic2和topic2＆topick中。如果將微博信息作為節(jié)點，信息和信息間共享的詞匯作為邊，可得到圖2無向網(wǎng)絡(luò)。在這個無向網(wǎng)絡(luò)中，節(jié)點表示用戶的微博發(fā)言，節(jié)點間的邊表示發(fā)言之間的共享詞匯。由于兩個發(fā)言可能包含多個相同詞匯，故兩個節(jié)點間可能有多條重復(fù)邊。如果將邊上的詞匯去掉，用兩個節(jié)點間的邊的個數(shù)來表示這兩個節(jié)點的邊的權(quán)重，圖2可進(jìn)一步化為如圖3所示的加權(quán)無向網(wǎng)絡(luò)。

圖1 微博信息網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.1 Graph of Microblog information network

圖2 轉(zhuǎn)化的微博信息網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.2 Derived graph of Microblog information network

圖3 轉(zhuǎn)化的加權(quán)微博信息網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.3 Derived weighted graph of Microblog information network

2.2 MapReduce話題網(wǎng)絡(luò)提取算法

在MapReduce系統(tǒng)中，Shuffle階段由系統(tǒng)內(nèi)部實現(xiàn)，用戶通過Mapper函數(shù)和Reducer函數(shù)實現(xiàn)海量數(shù)據(jù)的批處理。在Mapper函數(shù)中，系統(tǒng)將微博信息作為輸入，并給每個信息一個編號，然后將每個信息的單詞作為鍵，將信息的編號作為值發(fā)射出去；在Reducer函數(shù)中，系統(tǒng)將包含相同單詞（Mapper函數(shù)的鍵）的信息編號收集起來，然后在這些信息兩兩之間建立一條邊，并將單詞作為邊的屬性發(fā)射出去，得到的便是一個無向的圖。上述話題提取模型的算法如下。

3 實驗與分析

為了對本文提出的基于MapReduce的話題網(wǎng)絡(luò)構(gòu)建方法進(jìn)行驗證，筆者采集了2013年2月15日到20日的數(shù)據(jù)，共收集了204 376條微博發(fā)言信息。在應(yīng)用本文的方法進(jìn)行網(wǎng)絡(luò)提取后得到了一個包含3 483個節(jié)點和21 753條邊的無向加權(quán)網(wǎng)絡(luò)。

首先，對構(gòu)建的網(wǎng)絡(luò)進(jìn)行分析，分別分析了該網(wǎng)絡(luò)的度分布和PageRank值分布，其分布圖分別為圖4和圖5。圖4中縱軸表示節(jié)點的度，圖5中縱軸表示節(jié)點的PageRank值，這兩個圖的橫軸均表示節(jié)點的個數(shù)。從圖中可以看出，該網(wǎng)絡(luò)的度分布和PageRank值分布都服從冪率分布，即只有少數(shù)的計算點有很大的值，而大多數(shù)節(jié)點的度或PageR－ank值都很小，是典型的社會網(wǎng)絡(luò)結(jié)構(gòu)。

圖4 網(wǎng)絡(luò)的度分布圖Fig.4 Degree distribution of network

圖5 網(wǎng)絡(luò)的PageRank值分布圖Fig.5 PageRank distribution of network

為了進(jìn)一步驗證本文提出的算法對話題網(wǎng)絡(luò)的構(gòu)建的準(zhǔn)確性，本文對網(wǎng)絡(luò)的隱含話題的準(zhǔn)確性進(jìn)行了對比。本實驗對本文提出的基于MapReduce構(gòu)建的話題網(wǎng)絡(luò)進(jìn)行了話題檢測，同時采用經(jīng)典的LDA模型對話題進(jìn)行了檢測，核對了二者在話題檢測時的查準(zhǔn)率（Precision）和召回率（Recall）。從圖6所示的實驗結(jié)果可以看出，基于MapReduce構(gòu)建的話題網(wǎng)絡(luò)的潛在話題要優(yōu)于基于LDA模型的潛在話題。

圖6 話題檢測準(zhǔn)確性對比圖Fig.6 Accuracy comparison of topic detection

4 結(jié)語

微博中包含數(shù)以億計的用戶，這些用戶每天在微博中頻繁發(fā)言，在這些海量的用戶發(fā)言中蘊含著許多熱點話題。在話題的檢測過程中，可以通過向量空間模型或LDA進(jìn)行檢測。此外由于用戶間相同的話題往往包含相同的詞匯，這些詞匯作為微博信息鏈接的橋梁可以構(gòu)成話題網(wǎng)絡(luò)。本文研究了應(yīng)用MapReduce編程模型構(gòu)建微博信息的話題網(wǎng)絡(luò)。實驗表明，基于MapReduce構(gòu)建的話題網(wǎng)絡(luò)符合社會網(wǎng)絡(luò)的相關(guān)性質(zhì)，并且其話題預(yù)測的準(zhǔn)確性也高于基于LDA模型的話題檢測。

［1］ SOOP M，F(xiàn)RYKSMARK 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.