一種分布式中文微博熱點話題的發現方法

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

關鍵詞：微博；MapReduce；Kmeans；聚類；話題發現

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

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

1 基于MapReduce編程模型的微博熱點話題發現

1.1 隱主題建模

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

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

1.2 對建模結果進行初步聚類

然后本文采用CURE[3]算法對建模后的微博數據進行初步聚類，該算法可以得到K-means算法的輸入參數：聚類個數及其對應的初始類中心，從而緩解K-means初始聚類中心的隨機性和先驗性導致聚類結果波動的問題。其過程如下：

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

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

⑶通過隨機取樣剔除孤立點，去除增長較慢或者不增長的簇；

⑷對局部簇進行聚類；

⑸用相應的簇標簽標記相應的簇；

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

1.3 對建模結果進行聚類

1.3.1 MapReduce基本思想

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

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

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

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

⑵Repeat

⑶執行Map函數，計算每個點到簇質心的距離，標注或重新標注其所屬的類別；

⑷執行Reduce函數，計算新的簇質心，并用新計算的簇質心替代原簇中心

⑸計算兩輪簇質心的距離的平方和D

⑹Until D小于給定閾值

2 實驗分析與結果

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

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

3 結論

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

[參考文獻]

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

[2]石晶，李萬龍.基于LDA模型的主題詞抽取方法[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]江務學，張璟，王志明.MapReduce并行編程架構模型研究[J].微電子學與計算機.2011，06：168-170+175.

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