劉 熱

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

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

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

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

1 相關(guān)工作

1.1 話(huà)題檢測(cè)

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

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

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

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

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

1.3 MapReduce

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

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

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

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

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

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

3 實(shí)驗(yàn)與分析

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

首先，對(duì)構(gòu)建的網(wǎng)絡(luò)進(jìn)行分析，分別分析了該網(wǎng)絡(luò)的度分布和PageRank值分布，其分布圖分別為圖4和圖5。圖4中縱軸表示節(jié)點(diǎn)的度，圖5中縱軸表示節(jié)點(diǎn)的PageRank值，這兩個(gè)圖的橫軸均表示節(jié)點(diǎn)的個(gè)數(shù)。從圖中可以看出，該網(wǎng)絡(luò)的度分布和PageRank值分布都服從冪率分布，即只有少數(shù)的計(jì)算點(diǎn)有很大的值，而大多數(shù)節(jié)點(diǎn)的度或PageR－ank值都很小，是典型的社會(huì)網(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)一步驗(yàn)證本文提出的算法對(duì)話(huà)題網(wǎng)絡(luò)的構(gòu)建的準(zhǔn)確性，本文對(duì)網(wǎng)絡(luò)的隱含話(huà)題的準(zhǔn)確性進(jìn)行了對(duì)比。本實(shí)驗(yàn)對(duì)本文提出的基于MapReduce構(gòu)建的話(huà)題網(wǎng)絡(luò)進(jìn)行了話(huà)題檢測(cè)，同時(shí)采用經(jīng)典的LDA模型對(duì)話(huà)題進(jìn)行了檢測(cè)，核對(duì)了二者在話(huà)題檢測(cè)時(shí)的查準(zhǔn)率（Precision）和召回率（Recall）。從圖6所示的實(shí)驗(yàn)結(jié)果可以看出，基于MapReduce構(gòu)建的話(huà)題網(wǎng)絡(luò)的潛在話(huà)題要優(yōu)于基于LDA模型的潛在話(huà)題。

圖6 話(huà)題檢測(cè)準(zhǔn)確性對(duì)比圖Fig.6 Accuracy comparison of topic detection

4 結(jié)語(yǔ)

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

［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.