DOLDA模型設計與主題演化分析

蔣 權(quán)，鄭山紅，劉 凱，李萬龍

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

0 引 言

近年來，各類信息源的存儲量都呈現(xiàn)海量特征，以文本數(shù)據(jù)的增長最為顯著，從海量文本數(shù)據(jù)中及時提取熱點主題并對主題演化分析逐漸得到相關(guān)研究者的關(guān)注，由于LDA(latent dirichlet allocation)在演化領(lǐng)域具有獨特的優(yōu)勢，所以，許多基于LDA模型的擴展模型相繼被提出[1-4]。

C.Wang等[5]針對不同時間序列的主題分布，提出反映主題在時間上內(nèi)容和強度變化的TOT(topic over time)模型，其中假設模型是基于正態(tài)分布的，但正態(tài)分布與多項式分布非共軛分布，模型參數(shù)推理和估計上是比較困難的；R.Nallapati等[6]提出多時間粒度主題演化的MTTM(multinomial topic tomography)，雖然該模型采用泊松分布作為共軛先驗來建模，但不具備在線處理文本的能力；Hoffman等[7]提出的OLDA，按照數(shù)據(jù)流來劃分大數(shù)據(jù)文檔比批處理LDA算法快2-5倍，但OLDA主題建模需要包括細分的批處理文檔大小在內(nèi)的3個參數(shù)，這樣會使主題模型的精度降低，并且OLDA容易產(chǎn)生新舊主題混合而導致不能及時的發(fā)現(xiàn)新的主題；崔凱等[8]基于OLDA思想提出一種在線主題演化挖掘模型；Newman等[9]得出并行的OLDA算法比批處理LDA算法的效率快700多倍的結(jié)論；Ahmed等[10]在Yahoo基于共享內(nèi)存系統(tǒng)提出一種在多處理器提高運算速率的緩存技術(shù)。然而，這些研究都沒有很好解決OLDA模型自身的缺陷。針對OLDA模型在大量主題文檔集中計算時間長和新主題不能及時發(fā)現(xiàn)的問題，以及在并行算法中各處理器之間的通信成本很高的缺陷，提出一種分布式的DOLDA模型。

1 LDA模型與OLDA模型

1.1 LDA模型

LDA實質(zhì)是添加Dirichlet先驗的pLSA模型的貝葉斯生成模型，是將文檔中每篇文檔的主題以概率的形式表示出的一種貝葉斯無監(jiān)督的概率模型，是一種典型的詞袋模型，同時是一種對文本數(shù)據(jù)集潛藏的主題信息進行建模的方法[2]。如圖1所示，M表示文檔數(shù)目，K表示主題數(shù)目，Nm表示第m個文檔的單詞數(shù)目，文檔的生成過程如下。

圖1 LDA的圖模型表示

首先，LDA通過先驗知識選擇一篇文檔di，并從α分布中取樣生成文檔di的主題分布θi；然后從主題的多項式分布θi中取樣生成文檔di的第j個詞的主題Zi,j；接著從β分布中取樣生成主題Zi,j對應的詞語分布Φzi,j；從詞語多項式Φzi,j中采樣最終生成詞語ωi,j。因此，LDA中單詞和對應主題的聯(lián)合概率分布如式(1)所示

p(w,z|α,β)=p(w|z,β)p(z|α)=

(1)

1.2 OLDA模型

在文本處理中，通常主題具有持續(xù)性和穩(wěn)定性。固定劃分的時間片大小出現(xiàn)的主題很大程度上以固有特征出現(xiàn)在現(xiàn)有的時間片中，往往這種主題的特征是由主題-詞項概率分布來體現(xiàn)。所以，在每段文本流中每個時間片的主題的后驗分布能夠作為當前時間片主題分布先驗分布，這對于分析時間片之間的主題演化是極其重要的。

(2)

計算模型參數(shù)時，利用多項-狄利克雷(multinomial-Dirichlet)這組共軛先驗-似然分布不需要歸一化常數(shù)，只要找到與感興趣密度相成比例的分布形式，就能簡單地解決模型參數(shù)計算難題。OLDA按照文本數(shù)據(jù)流生成的先后順序給各個時間片中的文檔建模，通過不同的時間段挖掘主題可以實時在線或近似在線的分析主題演化。

2 分布式的DOLDA模型

DOLDA模型是基于Spark分布式計算平臺[11,12],模型建立主要分為3部分：分布式主題-詞項矩陣設計、新的動態(tài)負載均衡策略、潛藏主題-詞項分布傾斜權(quán)重提出。最后，給出DOLDA模型的整個算法實現(xiàn)過程。

2.1 分布式主題-詞項矩陣

Spark是基于內(nèi)存的迭代計算框架，數(shù)據(jù)之間相互操作都是基于容錯的、并行的RDD(resilient distributed datasets)。首先，zipWithIndex函數(shù)給需處理RDD每個文檔分配獨立的id，map函數(shù)通過該id僅處理一個文檔作為輸入；接著，flatMap函數(shù)產(chǎn)生新的三元組RDD(docId,wordId,frequency)。然后，wordId為關(guān)鍵字用join函數(shù)合并每個主題-詞項矩陣生成四元組矩陣RDD(docId,wordId,frequency,row)；最后，groupByKey函數(shù)通過指定的docId用map函數(shù)處理三元組RDD(row,wordId,frequency)。

經(jīng)過一系列的RDD操作，好處有兩個：一是，用一個RDD算子函數(shù)一致處理得到RDD文本集，這樣可以更加快速和準確地切分大數(shù)據(jù)集；二是，能獲得適應DOLDA模型E-step這一步操作的輸入數(shù)據(jù)。

2.2 動態(tài)負載均衡策略

以往算法都采用靜態(tài)負載均衡策略來分配全部數(shù)據(jù)集進程資源，沒有考慮到處理文檔長度不一的問題。再者，操作系統(tǒng)對線程的調(diào)度是不公平的，即使有相同線程開啟時間和等樣工作量，全部線程還是不會在同一時間結(jié)束工作，這樣會導致資源大量浪費。Nallapati等[13]在這方面做了很多工作，但他們的研究報告結(jié)果顯示，計算機上運行4條線程情況下獲得大約2.0的加速比，算法在并行效果上并不是很理想。

為了從高性能計算角度上提高系統(tǒng)使用資源率，DOLDA模型采用了一種新的動態(tài)數(shù)據(jù)分配負載均衡策略。其核心設計思想：第一，不以文檔長度的計算量來調(diào)度資源，是否還有未處理的文檔，動態(tài)線程基本能保證所有線程能最后同時完成，減少了因線程執(zhí)行的時間不一致而導致線程的計算資源浪費的情況；第二，動態(tài)分配文檔數(shù)量僅為時間片中最長文檔d動態(tài)分配K×|d|的計算資源空間，相比靜態(tài)分配數(shù)據(jù)集方法所需要的K×V節(jié)約很大的資源空間，因為整個數(shù)據(jù)集詞的數(shù)量V遠遠大于一個文檔詞量|d|。在分布式計算中，節(jié)點是先訪問Cache數(shù)據(jù)再訪問內(nèi)存，動態(tài)分配過程中對數(shù)據(jù)集的計算是連續(xù)的，這樣做的好處能大幅度提高Cache利用率。

2.3 潛藏主題-詞分布傾斜權(quán)重

根據(jù)Zipf定律[14]，在自然語言里只有小部分的高頻詞匯，大部分的詞出現(xiàn)頻率較低，并且OLDA模型表達的主題權(quán)重ω是無法根據(jù)主題在不同的時間片中相應調(diào)整的。為此我們重新設定權(quán)重，為了避免因為ω設置過小導致前后主題不能對齊；ω過大導致Zipf定律固定詞頻強制對齊并非同一主題事件，特別在當前t時間片有產(chǎn)生新的主題，但新舊主題混合一起與t-1中的相關(guān)主題產(chǎn)生對齊，會給及時發(fā)現(xiàn)新的主題帶來麻煩，考慮到主題之間的差異性，潛藏主題-詞項分布傾斜權(quán)重?。?來衡量主題的重要性，包括基準主題權(quán)重和主題遺傳強度權(quán)重兩部分。按Zipf定律在詞匯上的分布p(ω|Z)應該往詞匯集合中的一個子集偏斜,設一個Zipf主題權(quán)重Zs，p(ωi|Zs)=1/V，i∈{1,2,…V}，則潛藏主題Zk的主題-詞分布傾斜權(quán)重設定為基準主題Sbase(Zk)，其定義為Zs的詞分布與Zk詞分布的相似度，散度定義請參見文獻KL(kullback-leibler divergence)[15]所示。

基準主題Sbase(Zk)反應了潛藏主題的主題分布權(quán)重，Sbase(Zk)越小，Zk在主題分布的概率分布越平均，則基準主題的傾斜性越低，主題重要性越低。

考慮到當前時間片中主題強度越高的主題會在下個時間片出現(xiàn)并遺傳出更多的相關(guān)主題，則定義潛藏主題Zk的詞分布主題遺傳強度傾斜權(quán)重Sinher(Zk)。潛藏主題-詞分布的傾斜權(quán)重?是由基準主題權(quán)重Sbase(Zk)和主題遺傳強度Sinher(Zk)的加權(quán)和，其計算由(3)式所示

?=λ1Sbase(zk)+λ2Sinher(zk)

(3)

其中，λ1、λ2分別是權(quán)重系數(shù)。如圖2所示，DOLDA模型在主題內(nèi)容的演化。通過?控制主題遺傳度，?低的主題很有可能在下一個時間片消亡或者突變?yōu)槠渌闹黝}，相反?很高的主題可依然保持它的主題連續(xù)性，很明顯?的高低在主題演化分析上具有很大參考價值。

圖2 DOLDA模型在主題內(nèi)容演化

(4)

(5)

Spark分布式集群調(diào)用動態(tài)負載均衡算法分配線程資源給整個數(shù)據(jù)集文檔DM,V，從切分文檔Dth選擇文檔di，分布式的主題-詞項矩陣通過一系列的RDD算子方法切分數(shù)據(jù)集并且在相應的時間片內(nèi)得到新的RDD。首先從參數(shù)α的Dirichlet分布中取樣生成文檔di的主題分布θi，如果時間段t=1，通過Zipf定律計算基準主題權(quán)重，從Dirichlet分布β中取樣生成主題Zi,j對應的詞語分布Φzi,j。如果是t+1時間段，需要計算?。然后，分布式集群是從K×|d|選擇一個文檔集合并合理分配線程資源，分布式主題-詞矩陣Sd存儲RDD算子處理后的新的RDD；最后，distributed E-Step函數(shù)處理上一步新的RDD，循環(huán)計算?，詞語多項式Φzi,j中采樣最終生成詞語。并且distributed M-Step函數(shù)通過全局的主題-詞項矩陣更新主題-詞項矩陣。

綜上所述，DOLDA算法的具體過程如圖3所示。

3 主題演化分析

內(nèi)容演化和強度演化是主題演化分析的主要組成部分。本文采用何建云等[15]在相關(guān)研究來計算主題演化強度。在計算主題之間相似度方法時考慮到KL距離度量的是兩個主題在詞語集上分布的差異性，而對實時性和近實時性的要求，采用一種新的計算主題相似度方法。

(1)主題強度度量：主題的重要性主要是通過主題在文本中所占的比重的高低來度量。分析文檔的主題分布高低來賦予每篇文檔相應的權(quán)值。采用熵來度量文檔-主題分布的密集程度，并用熵估算文檔權(quán)重，計算分別由式(6)

圖3 DOLDA算法的具體過程

和式(7)所示

(6)

(7)

θm,k為估計文檔m在第k個主題的值。當權(quán)重逼近最大值1時，文檔只屬于一個主題；當權(quán)重逼近0時，文檔在K個主題上均勻分布。一個新的主題強度計算由式(8)所示

(8)

(2)主題相似性度量：本文使用Cosine距離來計算主題間相似性。首先將離散的概率分布函數(shù)Φz表示成向量，利用Cosine距離計算Φ1和Φ2的相似性，由(9)式所示

(9)

兩個主題Φi和Φj詞的概率值越相近，兩個主題相似性越大，并值得注意的是，公式中所有符號沒有像KL距離或者Jensen-Shannon距離一樣有時間上標，因為主題相似性的度量是針對任意不同或者相同的時間片的主題的。

4 實 驗

4.1 實驗準備

數(shù)據(jù)集：本文實驗采用的英文數(shù)據(jù)集NIPS，該數(shù)據(jù)集包括1988-2001年共14年會議1740篇研究論文，13 649個出現(xiàn)一次的詞匯和總共2 301 375個單詞。數(shù)據(jù)集解壓后都是文本格式，以年為單位總共劃分14個時間戳，每個文檔有一個時間戳，每個文本集包括90-250篇文檔之間。

數(shù)據(jù)預處理：數(shù)據(jù)集包含了14年的會議相關(guān)數(shù)據(jù)，在使用DOLDA模型分析之前必須進行數(shù)據(jù)預處理工作：取出停用詞(stopwords)和在數(shù)據(jù)集中出現(xiàn)次數(shù)少于5次的詞。

實驗環(huán)境：實驗由3臺虛擬機來搭建集群實驗環(huán)境，每臺虛擬機的硬件配置為8 cores、8 G內(nèi)存、50 G磁盤，操作系統(tǒng)版本為centos6.2。Spark版本為1.5.2，hadoop版本為2.6.2。實驗的集群架構(gòu)圖如圖4所示。

圖4 集群架構(gòu)

4.2 實驗結(jié)果

4.2.1 整體效果

在Spark集群上運行DOLDA模型，使用主題T=20，100輪迭代。超參數(shù)設置為α=0.1，β=0.1，模型的主題挖掘整體效果如圖5所示，總共挖掘出20個主題，每個主題標識10個最重要的10個詞語。人工篩選4個主題，各個主題對應的關(guān)鍵詞，Topic1是與GraphX相關(guān)的，Topic8是與主題模型相關(guān)，Topic10是與算法相關(guān)的，Topic15是機器學習相關(guān)的主題。從模型中挖掘出來的主題所對應的關(guān)鍵詞的準確性較高，并且主題之間內(nèi)容獨立性較強。

圖5 主題強度變化

如圖6所示，可以很直觀看清楚主題強度的變化趨勢，主題1的波動是最平緩的，主題1在nips會議中的地位每年都比較重要，猜測主題1在下一年的會議中仍會被重視。主題10的強度就有別其它主題，由主題關(guān)鍵詞概率所占的比重可以分析出主題10里詞匯有比較高的普遍性，即背景噪聲詞匯。主題8討論的內(nèi)容呈上升趨勢，說明主題8的討論越來越成為熱點話題，相對主題15的討論有所下降。

圖6 部分主題概率

主題內(nèi)容的演化也是本文研究重點。我們專門對主題12(reinforcement learning)隨著時間的變化程度分析，采用Cosine距離來計算相鄰時間塊內(nèi)的主題間相似性。如圖7所示，展現(xiàn)主題12隨著時間變化預測走勢圖，nips00、nips10、nips11和nips12的主題距離明顯高于閾值(虛線表示)，反映了會議中主題12談論的主題是重要的?？吹絥ips00->nips01之間距離突然增大，表明主題12在期間內(nèi)發(fā)生了重大的變化。通過如表1所示的相應的關(guān)鍵詞的概率分布情況，對于“強化學習”的關(guān)鍵詞的概率明顯下降，且一直低于閾值水平到nips09，其后有關(guān)“強化學習”主題的相關(guān)關(guān)鍵詞逐漸呈現(xiàn)上升趨勢，并且在nips13中的內(nèi)

圖7 主題12變化預測

容都是與“強化學習”相關(guān)的，這樣說明主題12逐漸演化成為“強化學習”。

表1 Topic12的內(nèi)容演化

4.2.2 對比實驗

DOLDA是在OLDA模型基礎(chǔ)上提出來的，OLDA模型的主題邊界比較模糊，容易造成新舊主題混合導致不能及時發(fā)現(xiàn)新主題的問題。如表2所示，DOLDA與OLDA對幾個主題檢測的對比效果。

表2 DOLDA與OLDA的主題檢測結(jié)果

從上表中可以分析出：在3個主題檢測中，OLDA模型在檢測SQL主題時檢測結(jié)果不完整，難以判別該主題是SQL，在檢測主題reinforcement learning時，出現(xiàn)主題不同程度的混合現(xiàn)象。比如在OLDA檢測中supervised learning和model learning 的共現(xiàn)與reinforcement learning主題混合在一起導致新舊主題混合。DOLDA模型中，潛藏主題-詞分布傾斜權(quán)重?，?比較低的主題會被提前預處理，給產(chǎn)生的新主題的權(quán)重相對高一點，這樣新主題和原有冷門主題就不會出現(xiàn)混淆的現(xiàn)象。

實驗進一步比較了OLDA模型和DOLDA模型的困惑度(Perplexity)這一度量概率模型性能指標[16]，Perplexity表示主題模型對于觀測數(shù)據(jù)的預測能力，取值越小就表示模型的性能越好，模型的推廣度越高。Perplexity定義如下

(10)

其中，wd為文檔d中的可觀測單詞序列；Dtest為實驗所整理的測試集；Nd為文檔d的單詞個數(shù)。為了計算p(wd)，選擇20%的文檔作為測試集，剩下80%文檔作為訓練集，需要計算預測文檔的似然度。如圖8所示，在NIPS數(shù)據(jù)集上訓練OLDA模型和DOLDA模型，在每一個時間片，比較模型困惑度。

圖8 OLDA與DOLDA模型的困惑度對比

與OLDA模型的對比實驗發(fā)現(xiàn)，在相同的實驗環(huán)境下，DOLDA模型在每一時間片的困惑度均要小于OLDA，這樣驗證了在OLDA模型基礎(chǔ)上提出的優(yōu)化方案確實能提高模型的性能和推廣性。

最后，DOLDA模型運行在Spark分布式計算平臺上，提出了一種新的動態(tài)負載均衡的調(diào)度策略，如圖9所示，在NIPS數(shù)據(jù)集上對OLDA模型和DOLDA模型的加速比進行對比。在NIPS數(shù)據(jù)集上使用6個線程，DOLDA相比OLDA的加速比提高了近16%，這表示新的調(diào)度算法更加有效地調(diào)度線程，使用動態(tài)的調(diào)度策略使線程的分配和利用更加高效和合理，隨著線程數(shù)量的增多、文檔集的分塊粒度越小，DOLDA模型在加速比上相對有優(yōu)勢。

圖9 OLDA與DOLDA在NIPS數(shù)據(jù)集上的加速比

5 結(jié)束語

綜上所述，本文基于OLDA模型提出了DOLDA模型，其不僅很好的利用Spark中RDD分布式數(shù)據(jù)結(jié)構(gòu)的特性，設計一個新的動態(tài)負載均衡的策略，提出潛藏主題-詞分布傾斜權(quán)重定義很好避免了OLDA模型新舊主題混合的問題,獲得較低的困惑度、較高的加速比以及有效的在線分析主題的演化情況。

未來的研究工作主要將從以下兩方面入手：第一，繼續(xù)優(yōu)化DOLDA模型；第二，在主題演化過程中，探索更早時間片的主題之間的影響程度。

[1]Blei DM,Ng AY,Jordan M.Latent dirichlet allocation[J].The Journal of Machine Learning Research,2003,3(3):993-1022.

[2]Chen TH,Thomas SW,Hassan AE.A survey on the use of topic models when mining software repositories[J].Empirical Software Engineering,2016,21(5):1-77.

[3]Ma HF,Sun YX.Microblog hot topic detection based on Topic model using term correlation matrix[C]//Proceedings of the 17th International Conferenceon Machine Learning and Cybernetics,2014:25-29.

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

[5]Wang C,Blei D,Heckerman D.Continuous topic models[C]//The 23rd Conference on Uncertainty in Artificial Intelligence,2012:579-586.

[6]Nallapati R,Ditmore S,Latterty JD,et al.Multiscale topic tomography[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining,2014,25(1):17-32.

[7]Hoffman M,Blei D,Bach F.Online learning for latent dirichlet allocation[C]//The 24th Annual Conference on Neural Information Processing Systems,2010:856-864.

[8]Cui Kai,ZHOU Bin,JIA Yan,et al.LDA-based model for online topic evolution mining[J].Computer Science,2010,37(11):156-159.

[9]Newman D,Asuncion A,Smyth P,et al.Distributed algorithms for topic models[J].Journal of Machine Learning Research,2009,10(12):1801-1828.

[10]Ahmed AM,Gonzalez J,Narayanamurthy S,et al.Scalable inference in latent variable models[C]//ACM International Conference on Web Search & Data Mining,2012:123-132.

[11]Zaharia M,Chowdhury M,Franklin MJ,et al.Spark:Cluster computing with working sets[C]//In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing,2010.

[12]Zhao B,Zhou H,Li G,et al.ZenLDA:An efficient and scalable topic model training system on distributed data-parallel platform[J].Computer Science,2015,5(5):46-50.

[13]Nallapati R,Cohen W,Lafferty J,et al.Parallelized variational EM for latent dirichlet allocation:An experimental eva-luation of speed and scalability[C]//IEEE International Conference on Data Mining Workshops,2007:349-354.

[14]Kalyanam J,Mantrach A,Saez-Trumper D,et al.Leveraging social context for modeling topic evolution[J].Know-ledge Discovery & Data Mining,2015,18(6):517-526.

[15]HE Jianyun,CHEN Xingshu,DU Min,et al.Topic evolution analysis based on an improved online LDA model[J].Journal of Central South University(Science and Technology),2015,7(2):547-553(in Chinese).[何建云,陳興蜀,杜敏,等,基于改進的在線LDA模型的主題演化分析[J].中南大學學報(自然科學版),2015,7(2):547-553.]

[16]Griffiths TL,Steyvers M.Finding scientific topics[J].Proc of the National Academy of Sciences of United States of America,2004,101(S11):5228-5235.