一種分布式LDA主題模型方法

蔣 權, 董亞則, 劉 凱, 龐海龍

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

?

一種分布式LDA主題模型方法

蔣 權, 董亞則*, 劉 凱, 龐海龍

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

基于Spark分布式計算框架，采用Gibbs抽樣方法研究分布式LDA主題模型挖掘方法。在Spark平臺進行大規模數據集處理實驗。

LDA主題模型； Spark； Gibbs； 分布式計算； 主題建模

0 引 言

近年來，大數據技術迅猛發展，各類信息資源的存儲量都呈現海量特征[1]，其中以文本數據的不斷增長最為顯著，文本主題分析旨在確定文本的主題以及推斷出相應的主題分布，界定主題的外延，追蹤主題的轉換等，分析結果對文本聚類分析、文本特征生成預測任務、文章自動生成等領域有著非常重要的價值。LDA(Latent Dirichlet Allocation)模型是Blei[2]等在2003年提出的一種三層貝葉斯全概率生成的主題挖掘模型，現在已經廣泛應用在信息檢索、文本分類、詞云推薦等文本相關領域。

Spark[3]是一個使用簡單的大數據處理的分布式計算框架，基于它開發的應用程序能夠很容易地運行在成百上千臺由一堆便宜的商用機器組成的超大集群上，其提出一種新的抽象數據結構RDD(Resilient Distributed Datasets)[4]以一種可靠容錯的方式能夠處理T級別的數據集,極大地簡化了分布式程序設計。

文中提出了一種分布式LDA主題模型挖掘方法，并實現了基于Spark計算框架的分布式LDA文本主題挖掘模型。通過真實數據的實驗驗證，該方法在處理大規模數據集時，不僅能獲得接近線性的加速比，而且大大提高了挖掘潛在主題信息的準確性，對主題建模效果也有所提高。

1 Spark數據處理過程

Spark不僅僅局限于Map和Reduce編程，它提供了更強大的內存計算模型，這樣用戶能夠快速在內存中對數據集進行多次迭代計算。Spark計算模型需要處理的數據都會分區存儲像Hadoop的分布式文件存儲系統HDFS以鍵值對的形式存在。

Spark數據處理流程如圖1所示。

圖1 Spark數據處理流程

Spark數據處理流程主要分兩個層面：首先，RDD實現了以操作本地集合的方式操作分布式數據集的抽象實現，并且數據集合都通過緩存到內存中，每次對RDD數據集的操作之后的結果都可以存放到內存中，省去了MapReduce框架中由于Shuffle操作所引發的大量磁盤IO。這樣的處理對于迭代運算比較常見的機器學習算法、交互式數據挖掘來說，效率提升比較大。其次，RDD上面執行的算子(Operator)主要有Transformation和Action兩大類。在轉換方面支持算子有map、join、groupBy和filter等，而在操作方面支持算子有reduce、collect、count等save。

2 LDA模型基本思想

LDA模型是一個包含詞、主題和文檔三層結構的貝葉斯無監督的概率模型，是典型的文檔主題生成模型，是一種對文本數據集潛藏的主題信息進行建模的方法[2，5],如圖2所示。

它假設文檔屬于多個隱含主題上的混合分布，各個主題之間是一個固定詞表上的混合分布。令M表示文檔數目，K表示主題數目，Nm表示第m個文檔的單詞數目，文檔的生成過程描述如下：

(1)

1)以先驗概率p(di)選擇一篇文檔di；

2)從Dirichlet分布α中取樣生成文檔di的主題分布θi；

3)從主題的多項式分布θi中取樣生成文檔di的第j個詞的主題zi,j；

4)從Dirichlet分布β中取樣生成主題zi,j對應的詞語分布φzi,j；

5)從詞語多項式φzi,j中采樣最終生成詞語wi,j。

圖2 LDA的圖模型

3 分布式LDA算法

提出的基于Spark計算框架的分布式LDA主題挖掘模型，其算法原理流程如圖3所示。

圖3 分布式LDA算法原理

首先介紹分布式LDA主題建模的思想以及如何使用Spark進行主題建模的實現。

3.1 分布式LDA主題建模的思想

通過使用Gibbs sampling抽取算法[6]，很快能夠得到目標的分布情況，但面對巨大的語料集時，數據的維度是難以想象的，并且其中一篇文檔中矩陣θ將在巨大的數據集中變化的不明顯，這樣就出現了計算的瓶頸。根據公式：

(2)

建立文檔的主題模型，其主要的思想為：

1)需要初始化各項參數，比如γ和θ；

2)數據集X被按照文檔分割成p份，例如，有m篇文檔，分割后每個小數據可以用Xi表示，其中Xi∈p；

3)對每個小數據集計算局部估計量和該結點的log函數期望；

4)對每個小數據集分別進行一次Gibbs采樣，這樣避免需要不斷對文檔-主題和主題-詞的概率中的狀態矩陣進行記錄；

5)聚合得到全局的估計量并循環估計參數γ和θ，直到模型的參數收斂；

6)輸出訓練完成的模型。

但是，不要忽略了一個問題，在Spark分布式計算平臺都是以集群的方式來處理計算分配任務的，每一個分布式處理的集群都會給RDD分配滿足全部大數據集的計算機資源，處理的單元根本就不會考慮小批處理文件是不是有效地利用了所分配的資源。Nallapati[7]等雖然在減少網絡傳輸時間開銷和網絡負載方面做了很多工作，但是他們主要的研究報告結果顯示，在4臺計算機上運行4條線程的情況下得到了大約2.0的加速比，所以算法在并行效果上也不是很理想。為了解決上面的問題，我們在分布式LDA算法設計采用了如下負載均衡策略：

1)將分割后的數據塊Xi中相同行數據塊分配到一個計算節點上，因為數據集中文檔的個數通常比詞匯表中的詞個數要多，僅僅只看是否還有未處理的文檔來進行線程調度，這樣能保證線程大致可以同時完成，節約計算資源。

3.2 特征權重計算

采用TF-IDF權重評價方式進行權重計算[8]。權重計算公式如下：

(3)

(4)

(5)

式中: N----特定文本中單詞的數量;

Nw----詞在特定文本中出現的頻數;

D----整個語料集中文本的總數;

DFi----整個語料庫中出現特定詞的文本總數量。

3.3 分布式LDA主題模型算法的實現

前面介紹了分布式LDA算法避免大量網絡傳輸和計算消耗所作出的改進，并簡單地介紹主題特征權重計算的基本方法。但是，前面的改進策略同樣會大大增加迭代的次數，所以，我們結合前面介紹的內容給出基于Spark的分布式LDA主題模型算法建立的過程(見圖3)，分布式LDA主題建模算法執行過程如下:

Input:ωm,α,β,K

Output:θ,φ

for all ducuments ωm(m∈[1,M]) do

for all words n in ωmdo

sample topic index zm,n=k～Mult(1/K)

increment counts and sums: nm+=1

nk+=1

end for

// load balance

set maximum number of executions:maxexec=3

set number of element in RDD Xi:numXi=0,sumnum=0

for all data blocks id i i∈[1,P] in Xido

compute the difference between max and min : di=maxnum-minnum

add all di: sumnum+=di

end for

select optimal solution:minsum

end for

while(parameters converge and not reach maximum number of iterations) do

for all documents ωm(m∈[1,M]) do

for all words n in ωmdo

k=p(zi|zi,w)

end for

end for

end while

4 實驗分析

4.1 測試數據以及實驗環境

實驗使用的數據是由搜狗實驗室提供的網絡新聞數據集，來自將近20個欄目的全網新聞數據SogouCA，數據大小為630 MB。在使用數據集之前，必須進行數據預處理工作：分詞處理采用的分詞工具是基于詞典的分詞算法mmseg；取出停用詞(stopwords)和在數據集中出現次數少于5次的詞。停用詞是指語氣助詞和代詞等常用詞，盡管在文本中出現的次數很多，但對于主題的發現幫助不大。

實驗環境是由3臺虛擬機來搭建集群環境，每臺虛擬機的硬件配置為8 cores、8G內存、50G磁盤，操作系統使用的是centos6.5。Spark版本為1.5.2，hadoop版本為2.6.2。

4.2 實驗結果分析

實驗采用困惑度(Perplexity)指標對實驗的結果進行度量。比較LDA模型(LDA)和分布式LDA模型(Spark-LDA)的Perplexity，它是度量概率模型性能的常用指標，同樣也是業界主題建模常用的衡量方法[9]，Perplexity定義如下：

(6)

根據上面的計算公式，我們在對數據集不同分塊個數p=(2,4,6,8)對兩模型進行對比實驗，如圖4所示。

圖4 LDA與Spark-LDA模型的困惑度對比

Perplexity表示主題模型對于觀測數據的預測能力，取值越小就表示模型的性能越好，相應的模型的推廣度越高，結果很明顯，Spark-LDA在每分塊上的困惑度都要比LDA低，并且從圖中可以看出，數據集切分塊數越多，模型的效果越好。

下面一組實驗是比較LDA和Spark-LDA算法在處理不同大小的數據集上的能力，我們分別用不同大小的文本量(100,200,300,400,500,600)/MB進行對比實驗，計算時間與文檔數的關系如圖5所示。

可以看出，在處理不同的任務量時，LDA和Spark-LDA的處理時間都是隨著任務量增加而增加的，但是，Spark-LDA所需要的時間都比LDA要少，并且是呈線性增加的，這說明Spark-LDA在處理大數據量文檔集時性能比較穩定。

圖5 不同文本規模的計算時間

5 結 語

研究并且實現了LDA主題模型建立方法在Spark分布式計算框架上的分布式實現，通過數據合理的切分和一種負載均衡的方法，在不降低主題模型的精準度前提下大幅度減少計算時間和網絡的消耗。經過真實數據的驗證，該方法在處理規模較大數據集時能夠得到較低并且接近線性的加速比，由于Spark是非常適合這種大量迭代時計算的平臺，給模型天然的賦予了比較好的可擴展性，這對于解決海量文本數據中挖掘潛在主題的問題提供了很重要的參考依據。

今后的工作將主要對LDA主題模型及其擴展模型與經典的數據挖掘算法結合，進行更深層次挖掘潛在主題信息以及主題演化分布情況。

[1] M Hirzel, H Andrade, B Gedik, et al. IBM streams processing language: analyzing big data in motion[J]. IBM Journal of Research and Development,2013,57(5):1-7.

[2] D M Blei, A Y Ng, M Jordan. Latent dirichlet dirichlet allocation[J]. The Journal of Machine Learning Research,2003,3:993-1022.

[3] M Zaharia， M Chowdhury， M J Franklin， et al. Spark: cluster computing with working sets[J]. Usenix Conference on Hot Topics in Cloud Computing,2010,15(1):1765-1773.

[4] Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, et al. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing[C]//NSDI 2012. Best Paper Award and Honorable Mention for Community Award.2012.

[5] Y A Ghassabeh, F Rudzicz, H A Moghaddam. Fast incremental LDA feature extraction[J]. Pattern Recognition,2015,48(6):1999-2012.

[6] Liu Shukui, Wu Ziyan, Zhang Yubing. Ldentification of physical parameters and damage localing with markov chain monte carlo method based on Gibbs sampling[J]. Journal of Vibration and Shock,2011,30(10):203-207.

[7] Nallapati, R Cohen, W Lafferty, et al. Parallelized variational EM for latent dirichlet allocation: an experimental evaluation of speed and scalability[C]//Proceeding of Seventh IEEE International Conference on Data Mining Workshop on High Performance Data Mining, Omaha, NE, USA,2007:349-354.

[8] H C Wu, R W P Luk, K F Wong, et al. Interpreting TF-IDF term weights as making relevance decisions[J]. Acm Transactions on Information Systems,2008,26(3):55-59.

[9] T L Griffiths, M Steyvers. Finding scientific topics[J]. Proc of the National Academy of Sciences of United States of America,2004,101:5228-5235.

A distributed LDA topic modeling

JIANG Quan, DONG Yaze*, LIU Kai, PANG Hailong

(School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012, China)

Based on spark distributed computing framework, we apply Gibbs sampling to study the distributed latent topic information (LDA) mining method. In Spark platform, experiment based on large data sets is carried.

LDA topic model; Spark; Gibbs sampling; distributed computing; topic modeling.

2016-11-22

吉林省教育廳“十二五”科學技術研究基金資助項目(2014125，2014131)； 吉林省自然科學基金資助項目(20130101060JC)

蔣 權(1993-)，男，漢族，湖北仙桃人，長春工業大學碩士研究生，主要從事數據挖掘、主題模型方向研究,E-mail:13944878813@163.com. *通訊作者：董亞則(1982-)，女，漢族，吉林德惠人，長春工業大學講師，博士，主要從事智能計算方向研究,E-mail:dongyaze@ccut.edu.cn.

10.15923/j.cnki.cn22-1382/t.2017.3.10

TP 301.6

A

1674-1374(2017)03-0265-05