蔣 權(quán), 董亞則, 劉 凱, 龐海龍

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

?

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

蔣 權(quán), 董亞則*, 劉 凱, 龐海龍

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

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

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

0 引 言

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

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

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

1 Spark數(shù)據(jù)處理過程

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

Spark數(shù)據(jù)處理流程如圖1所示。

圖1 Spark數(shù)據(jù)處理流程

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

2 LDA模型基本思想

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

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

(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進行主題建模的實現(xiàn)。

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

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

(2)

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

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

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

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

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

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

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

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

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

3.2 特征權(quán)重計算

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

(3)

(4)

(5)

式中: N----特定文本中單詞的數(shù)量;

Nw----詞在特定文本中出現(xiàn)的頻數(shù);

D----整個語料集中文本的總數(shù);

DFi----整個語料庫中出現(xiàn)特定詞的文本總數(shù)量。

3.3 分布式LDA主題模型算法的實現(xiàn)

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

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 測試數(shù)據(jù)以及實驗環(huán)境

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

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

4.2 實驗結(jié)果分析

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

(6)

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

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

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

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

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

圖5 不同文本規(guī)模的計算時間

5 結(jié) 語

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

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

[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

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

蔣 權(quán)(1993-)，男，漢族，湖北仙桃人，長春工業(yè)大學碩士研究生，主要從事數(shù)據(jù)挖掘、主題模型方向研究,E-mail:13944878813@163.com. *通訊作者：董亞則(1982-)，女，漢族，吉林德惠人，長春工業(yè)大學講師，博士，主要從事智能計算方向研究,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