一種分布式中文微博熱點(diǎn)話題的發(fā)現(xiàn)方法

摘 要：針對微博數(shù)據(jù)文本內(nèi)容短小、特征詞稀疏以及規(guī)模龐大的特點(diǎn)，提出了一種基于MapReduce編程模型的發(fā)現(xiàn)微博熱點(diǎn)話題的方法。該方法首先利用隱主題分析技術(shù)解決了微博內(nèi)容短小、特征詞稀疏的問題，然后利用CURE算法緩解了Kmeans算法對初始點(diǎn)敏感的問題，最后采用基于MapReduce編程模型Kmeans聚類算法，對海量微博短文本數(shù)據(jù)進(jìn)行快速聚類。實(shí)驗(yàn)結(jié)果表明該方法可以有效提高微博熱點(diǎn)話題發(fā)現(xiàn)的效率。

關(guān)鍵詞：微博；MapReduce；Kmeans；聚類；話題發(fā)現(xiàn)

微博在近兩年成為人們發(fā)表言論的重要工具，截至2013年3月，新浪微博注冊用戶總數(shù)已經(jīng)達(dá)到了5.36億，而且突發(fā)事件和熱點(diǎn)新聞在微博上的傳播速度，明顯快于電視、報紙等傳統(tǒng)媒體。因此及時發(fā)現(xiàn)微博中的熱點(diǎn)話題對輿情監(jiān)控、信息安全等領(lǐng)域有重要的意義。

傳統(tǒng)的話題檢測與追蹤（TDT）技術(shù)的研究對象主要針對篇幅較長的新聞報道。然而微博文具有本內(nèi)容短小，特證詞少且稀疏，規(guī)模龐大等特點(diǎn)，所以傳統(tǒng)的TDT技術(shù)不能有效地適用于微博消息。為此本文提出了結(jié)合潛在狄利克雷分配（Latent Dirichlet Allocation，LDA）模型和MapReduce編程模型的微博數(shù)據(jù)處理與微博熱點(diǎn)話題發(fā)現(xiàn)方法，在確保聚類精度的情況，有效的提高了聚類算法的效率。

1 基于MapReduce編程模型的微博熱點(diǎn)話題發(fā)現(xiàn)

1.1 隱主題建模

LDA（隱含狄利克雷分配）是一種三層樹狀貝葉斯概率生成模型，它基于此假設(shè)：文檔集中所有文檔均按照一定比例共享隱含主題集合，而隱含主題集則是由一系列相關(guān)特征詞組成。更多關(guān)于的LDA模型的介紹請參考文獻(xiàn)[1-2]。通過LDA主題模型建模，有效的降低了微博數(shù)據(jù)的維度，將原來高維的單詞空間降維到由一組主題構(gòu)成的相對較小的主題空間上。

本文采用的是GibbsLDA++對微博數(shù)據(jù)集建模，通過運(yùn)算后，可以得到如下5個文件：*.others—輸入?yún)?shù)、*.phi—詞匯-主題分布矩陣 、*.theta—主題-文檔分布矩陣 、*.tassign—主題分配情況和*.twords—主題。

1.2 對建模結(jié)果進(jìn)行初步聚類

然后本文采用CURE[3]算法對建模后的微博數(shù)據(jù)進(jìn)行初步聚類，該算法可以得到K-means算法的輸入?yún)?shù)：聚類個數(shù)及其對應(yīng)的初始類中心，從而緩解K-means初始聚類中心的隨機(jī)性和先驗(yàn)性導(dǎo)致聚類結(jié)果波動的問題。其過程如下：

⑴從上一步中得到的主題-文檔分布矩陣 中，隨即抽取樣本S；

⑵將樣本S劃分成等大的n份，對每個劃分進(jìn)行局部聚類；

⑶通過隨機(jī)取樣剔除孤立點(diǎn)，去除增長較慢或者不增長的簇；

⑷對局部簇進(jìn)行聚類；

⑸用相應(yīng)的簇標(biāo)簽標(biāo)記相應(yīng)的簇；

⑹分別對每個類別的所有樣本求其平均值，得到相應(yīng)的類中心。

1.3 對建模結(jié)果進(jìn)行聚類

1.3.1 MapReduce基本思想

MapReduce[4-6]是Google開發(fā)的一種用于處理大規(guī)模數(shù)據(jù)集的并行編程模型和高效的任務(wù)調(diào)度模型。MapReduce主要通過Map和Reduce兩個步驟來并行處理大規(guī)模數(shù)據(jù)，Map是一個分解的過程，它先將大數(shù)據(jù)集分解為成百上千的相護(hù)獨(dú)立的小數(shù)據(jù)集（splits），然后把每個（或若干個）數(shù)據(jù)集分配給集群中的1個節(jié)點(diǎn)（一般就是一臺普通的計算機(jī)）進(jìn)行處理；而Reduce是一個合并的過程，它將分開的數(shù)據(jù)整合到一起并返回輸出。

1.3.2 基于MapReduce編程模型的K-means聚類

K-means算法的并行化思想：對算法的每次迭代啟動一次MapReduce計算過程，即在每次迭代內(nèi)部實(shí)現(xiàn)并行計算，其中Map函數(shù)的主要任務(wù)是計算每個記錄到類中心點(diǎn)的距離并標(biāo)記或重新標(biāo)記其所屬的類別。Reduce函數(shù)的主要任務(wù)是根據(jù)Map函數(shù)得到的中間結(jié)果，計算新類的中心點(diǎn)，并把該中心點(diǎn)集傳給下一次MapReduce使用。該算法步驟如下：

⑴把CURE算法得到的k個簇類的中心點(diǎn)作為初始簇中心；

⑵Repeat

⑶執(zhí)行Map函數(shù)，計算每個點(diǎn)到簇質(zhì)心的距離，標(biāo)注或重新標(biāo)注其所屬的類別；

⑷執(zhí)行Reduce函數(shù)，計算新的簇質(zhì)心，并用新計算的簇質(zhì)心替代原簇中心

⑸計算兩輪簇質(zhì)心的距離的平方和D

⑹Until D小于給定閾值

2 實(shí)驗(yàn)分析與結(jié)果

實(shí)驗(yàn)一：通過騰訊微博API隨機(jī)獲取了2013年4月20日的21324條微博，對其按照本文方法進(jìn)行聚類，得到最熱門的3個話題為“雅安地震”、“禽流感”、“復(fù)旦研究生投毒”，通過對比騰訊話題排行榜，這三個話題均在排行榜前十名中。所以本方法基本可以準(zhǔn)確反映出當(dāng)日的熱點(diǎn)微博。

實(shí)驗(yàn)二：隨機(jī)獲取了騰訊微博2013年4月13日到2013年4月21日共9天的182162條微博文本，然后依次使用1～5節(jié)點(diǎn)測試基于MapReduce編程模型的分布式Kmeans文本聚類效率，通過實(shí)驗(yàn)可得，隨著集群中節(jié)點(diǎn)的增多，其運(yùn)行時間在逐漸減少，其加速比也在逐漸變大，說明基于MapReduce編程模型的Kmeans算法能夠提有效的高聚類效率，并且具有較好的加速比。

3 結(jié)論

本文研究了如何從海量微博消息中快速精準(zhǔn)得發(fā)現(xiàn)熱點(diǎn)話題，文中利用隱主題建模的方法，有效解決了短文本數(shù)據(jù)集稀疏性的問題，然后使用CURE算法，有效解決了K-Means算法對初始點(diǎn)選擇敏感的問題，最后利用基于MapReduce并行化的Kmeans算法，在一定程度上提高了聚類效率。

[參考文獻(xiàn)]

[1]Blei D M， Ng A Y. Latent Dirichlet Allocation [J].The Journal of Machine Learning Research.2003，3：993-1022.

[2]石晶，李萬龍.基于LDA模型的主題詞抽取方法[J].計算機(jī)工程.2010，19：81-83.

[3]Guha S，et al.CURE： An efficient clustering algorithm for large databases.In： Proc of the ACM SIGMOD Int’ l Conf on Management of Data.1998.

[4]Dean J，Ghemawat S.MapReduce： Simplified Data Processing on Large Clusters [J].Communications of the ACM.2005，51（1）：107-113.

[5]江務(wù)學(xué)，張璟，王志明.MapReduce并行編程架構(gòu)模型研究[J].微電子學(xué)與計算機(jī).2011，06：168-170+175.

[6]徐小龍，吳家興，楊庚，程春玲，王汝傳.基于大規(guī)模廉價計算平臺的海量數(shù)據(jù)處理系統(tǒng)的研究[J].計算機(jī)應(yīng)用研究.2012，02：582-585.