薛行貴， 高見文， 張伯虎， 黃立勤

(1. 武警工程大學(xué)研究生管理大隊(duì)， 陜西 西安 710086； 2. 福州大學(xué)物理與信息工程學(xué)院， 福建 福州 350116)

基于MapReduce的并行LAD模型評(píng)論主題提取算法研究

薛行貴1， 高見文1， 張伯虎1， 黃立勤2

(1. 武警工程大學(xué)研究生管理大隊(duì)， 陜西 西安 710086； 2. 福州大學(xué)物理與信息工程學(xué)院， 福建 福州 350116)

針對(duì)傳統(tǒng)的潛在狄利克雷分析(LDA)模型在提取評(píng)論主題時(shí)存在著計(jì)算時(shí)間長(zhǎng)、 計(jì)算效率低的問題， 提出基于MapReduce架構(gòu)的并行LAD模型建立方法. 在文本預(yù)處理的基礎(chǔ)上， 得到文檔-主題分布和主題-特征詞分布， 分別計(jì)算主題相似度和特征詞權(quán)重， 結(jié)合k-均值聚類算法， 實(shí)現(xiàn)評(píng)論主題提取的并行化. 通過Hadoop并行計(jì)算平臺(tái)進(jìn)行實(shí)驗(yàn)， 結(jié)果表明， 該方法在處理大規(guī)模文本時(shí)能獲得接近線性的加速比， 對(duì)主題模型的建立效果也有提高.

LAD模型； MapReduce； 評(píng)論主題; k-均值聚類算法

0 引言

主題模型是一種能夠從大規(guī)模文本中發(fā)現(xiàn)文本潛在主題的概率模型， 近年來在文本挖掘領(lǐng)域逐漸成為研究的熱點(diǎn)[1]. 主題模型起源于潛在語義索引， 它的發(fā)展經(jīng)歷了向量空間模型、 潛在語義分析模型[2]、 概率潛在語義分析模型[3]、 LDA模型及LDA擴(kuò)展模型的過程. 主題模型可以形象地表達(dá)文本中語義信息， 解決了向量空間模型及其改進(jìn)算法忽略特征詞語義的不足[4]. LDA模型算法在文本檢索[5]、 機(jī)器學(xué)習(xí)[6]、 文本聚類[7]等領(lǐng)域得到了廣泛應(yīng)用. 近年來， 國(guó)內(nèi)對(duì)LDA算法的改進(jìn)和應(yīng)用取得了豐碩的成果. 文[8]通過一種高斯函數(shù)對(duì)特征詞加權(quán), 改進(jìn)LDA 主題模型的主題分布， 提高了模型在主題表達(dá)和預(yù)測(cè)性能； 文[9]將LDA算法應(yīng)用于微博主題搜索； 文[10]構(gòu)建了適用于動(dòng)態(tài)文本主題挖掘的LDA模型等.

但傳統(tǒng)的LDA模型在處理海量信息和非結(jié)構(gòu)化數(shù)據(jù)時(shí)存在著耗時(shí)長(zhǎng)、 效率低下、 準(zhǔn)確率不高等缺陷. 針對(duì)這些問題， 提出一種基于MapReduce架構(gòu)的并行LDA主題模型提取算法， 在文本信息的預(yù)處理基礎(chǔ)上， 實(shí)現(xiàn)LDA模型對(duì)大量文本數(shù)據(jù)的并行處理， 將大量信息清晰地展示出來.

1 算法介紹

1.1 LDA模型

主要主題能夠代表著評(píng)論文本的核心思想， 對(duì)主要主題進(jìn)行關(guān)鍵特征詞的填充就可以表達(dá)某種語義信息. 評(píng)論主題提取算法核心思想是對(duì)大量評(píng)論文本進(jìn)行信息抽取并簡(jiǎn)約化表達(dá)[4], 如圖1所示.

圖中顯示LDA模型的三層結(jié)構(gòu)， 箭頭表示變量之間的依賴關(guān)系， 陰影區(qū)域表示處理過程中的觀測(cè)變量.wmn表示第m篇文本中第n個(gè)特征詞，zmn表示第m篇文本中第n個(gè)特征詞的主題.θm和φk為模型兩個(gè)隱含變量， 其中θm表示第m篇文本中的主題概率分布， 該分布服從一個(gè)Dirichlet先驗(yàn)分布，α是這個(gè)先驗(yàn)分布的超參數(shù)， 用來表示主題間的相對(duì)強(qiáng)弱.φk表示第k個(gè)主題中特征詞的概率分布， 該分布服從一個(gè)Dirichlet先驗(yàn)分布，β是這個(gè)先驗(yàn)分布的超參數(shù).φk是一個(gè)服從多項(xiàng)式分布的K×V的矩陣向量集合， 行向量代表文本集中的主題個(gè)數(shù)， 列向量代表文本集中的特征詞數(shù).M、Nm分別表示文本集中文本數(shù)和第m篇文本長(zhǎng)度(特征詞規(guī)模).

LDA算法初始階段， 將針對(duì)某一事件的評(píng)論文本作為輸入， 具體過程包括以下幾個(gè)階段[4]： 1)文本預(yù)處理、 特征提?。?2)利用LDA模型對(duì)輸入的評(píng)論文本建立主題模型： 確定主題個(gè)數(shù)和模型參數(shù)估計(jì)； 3)主題相似度計(jì)算； 4)確定特征詞匯權(quán)重.

1.2MapReduce介紹

MapReduce是一個(gè)用于海量數(shù)據(jù)處理的編程模型, 它采用了分別治理的思想[11], 基本形式有Map和Reduce兩個(gè)處理階段： 其主要的方式是將海量的數(shù)據(jù)處理任務(wù)劃分為諸多子任務(wù)， 并且將這些子任務(wù)劃分給一定數(shù)量的分布式的機(jī)器來并行完成批處理作業(yè). 其中Map階段是將原始的輸入(一般是key/velue對(duì))轉(zhuǎn)換成中間結(jié)果； 而Reduce階段則將之前產(chǎn)生的中間結(jié)果合并， 排序與輸出[12].

2 算法實(shí)現(xiàn)

根據(jù)對(duì)評(píng)論主題提取算法的描述， 算法的核心主要有： 文本預(yù)處理、 模型參數(shù)估計(jì)、 主題重要度確定和特征詞權(quán)重計(jì)算等部分. 而算法的主要計(jì)算量集中在文本預(yù)處理和模型參數(shù)估計(jì)過程， 因此在文本預(yù)處理和參數(shù)估計(jì)過程引入MapReduce架構(gòu)， 實(shí)現(xiàn)主題模型提取過程的并行化.

2.1 評(píng)論文本建模

LDA模型假設(shè)文檔是詞的集合， 詞之間可以交換順序并忽略語法關(guān)系， 將文本映射到主題空間進(jìn)行處理. 設(shè)文本集合D， 特征詞集合W， 建模過程分為以下幾個(gè)步驟[5]：

1) 確定主題個(gè)數(shù)K. 主題選擇方法一般分為兩種， 第一種是利用模型評(píng)價(jià)指標(biāo)困惑度、 語料似然值等， 重復(fù)實(shí)驗(yàn)K， 選擇使評(píng)價(jià)指標(biāo)最小的主題數(shù)K作為最合適主題； 第二種是利用貝葉斯統(tǒng)計(jì)方法選擇最合適主題數(shù). 本文使用評(píng)價(jià)指標(biāo)困惑度選擇最合適主題數(shù).

困惑度計(jì)算公式如下所示：

(1)

式中：Nd為第d篇文檔長(zhǎng)度；p(wd)表示文檔d中特征詞出現(xiàn)的概率.

2)LDA模型建立. 根據(jù)上一步得到主題個(gè)數(shù)K， 特征詞集合W中第i個(gè)詞wi可以表示為：

(2)

(3)

(4)

a) 構(gòu)建馬爾科夫鏈初始狀態(tài)， 隨機(jī)為評(píng)論文本集合中每個(gè)特征詞分配一個(gè)主題；

b) 給定其它特征詞的主題不變， 對(duì)當(dāng)前特征詞重新抽樣主題并更新馬爾科夫鏈；

c) 循環(huán)操作上一步驟， 直到抽樣收斂， 此時(shí)馬爾科夫鏈接近目標(biāo)分布， 統(tǒng)計(jì)當(dāng)前主題-特征詞分布情況， 進(jìn)而計(jì)算出多項(xiàng)分布參數(shù)θ和φ.

吉布斯抽樣算法的抽樣公式如下所示：

(5)

吉布斯抽樣算法給出每個(gè)特征詞的主題估計(jì)， 通過此時(shí)主題估計(jì)可以推導(dǎo)出模型分布參數(shù)θ和φ的值， 計(jì)算公式如下：

(6)

(7)

2.2 計(jì)算主題相似度

LDA建模后， 主題空間中每篇文本對(duì)應(yīng)一個(gè)主題概率向量， 兩評(píng)論文本相似度采用向量夾角余弦表示， 計(jì)算公式[5]如下：

(8)

式中:Pi、Pj分別表示文檔i和j對(duì)應(yīng)的主題分布概率向量， 且主題概率和等于1. 夾角余弦取值范圍為0到1. sim(di,dj)越大， 兩文本相似度越高. 當(dāng)sim(di,dj)=0時(shí)， 表示兩文本相互獨(dú)立； 當(dāng)sim(di,dj)=1時(shí)， 表示兩文本語義相同.

2.3 特征詞權(quán)重計(jì)算

由式(5)得到文本中詞匯概率分布， 結(jié)合BM25算法， 進(jìn)一步定義特征詞權(quán)重計(jì)算式. 這里首先給出BM25算法的計(jì)算公式：

(9)

定義特征詞wi權(quán)重計(jì)算式為：

(10)

由式(7)可以看出，W(wi)值越大， 特征詞wi在文本中權(quán)重越大.

2.4 MapReduce框架

本研究在文本處理過程中引入MapReduce框架實(shí)現(xiàn)主題的并行提取. 其實(shí)現(xiàn)框架如圖2：

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)采用Hadoop云計(jì)算環(huán)境， 搭建Hadoop平臺(tái). 硬件配置1個(gè)主節(jié)點(diǎn)和5個(gè)從節(jié)點(diǎn). CPU采用Intel Core Quad2 Q6600 2.4 GHz CPU， 16 GB內(nèi)存； 操作系統(tǒng)內(nèi)核為L(zhǎng)inux; Java 版本為1.6.0-26; Hadoop版本為1.2.0. 每個(gè)節(jié)點(diǎn)最多可運(yùn)行2個(gè)Map操作或1個(gè)Reduce操作. 實(shí)驗(yàn)語料來自天涯社區(qū)、 新浪微博上抓取兩個(gè)2015年事件的評(píng)論， 兩個(gè)事件分別為廣東河源市群體性事件和中國(guó)游客大鬧曼谷機(jī)場(chǎng)事件. 其中, 選取廣東河源市群體性事件評(píng)論集A共9 556條; 中國(guó)游客大鬧曼谷機(jī)場(chǎng)事件評(píng)論集B共12 094條.

3.2 結(jié)果分析

利用LDA模型對(duì)評(píng)論文本進(jìn)行建模， 模型中的兩個(gè)超參數(shù)根據(jù)經(jīng)驗(yàn)值取值分別為α=50/K，β=0.01[16]. 主題個(gè)數(shù)K的選取通過計(jì)算模型困惑度得到. 根據(jù)公式(1)， 分別計(jì)算兩個(gè)事件評(píng)論文本的最優(yōu)主題數(shù)， 結(jié)果如圖3所示.

從圖3中可以看出， 事件1的主題數(shù)K1為20， 事件2的主題數(shù)K2為50. 因此在實(shí)驗(yàn)中將兩個(gè)評(píng)論集的主題個(gè)數(shù)分別設(shè)為20和50， 迭代次數(shù)10. 對(duì)兩個(gè)數(shù)據(jù)集分別選擇不同的Data Node數(shù)進(jìn)行主題建立， 其結(jié)果如圖4所示. 從圖4中可以看出對(duì)于兩個(gè)評(píng)論集， 增加Data Node數(shù)量， 數(shù)據(jù)處理的時(shí)間顯著縮短; 增加節(jié)點(diǎn)數(shù)量可以提高處理效率. 隨著節(jié)點(diǎn)數(shù)量的增加， 運(yùn)行時(shí)間接近線性減少. 這些變化說明基于MapReduce的并行LDA模型評(píng)論主題提取算法具有接近線性的加速比.

為進(jìn)一步驗(yàn)證算法的性能， 分別選取不同大小的數(shù)據(jù)集， 設(shè)置Data Node節(jié)點(diǎn)數(shù)為6， 進(jìn)行實(shí)驗(yàn). 結(jié)果如圖5, 可以看出運(yùn)行時(shí)間隨著文本規(guī)模的增加接近線性增加.

4 結(jié)論

網(wǎng)絡(luò)包中含數(shù)以萬計(jì)的用戶， 每天會(huì)發(fā)表大量的評(píng)論數(shù)據(jù)， 這些數(shù)據(jù)中蘊(yùn)含著海量、 待挖掘的信息， 在商業(yè)和安全領(lǐng)域具有重要的意義和價(jià)值. 本文通過LDA主題模型提取方法在MapReduce結(jié)構(gòu)下的并行化實(shí)現(xiàn)， 提高了LDA算法對(duì)大量網(wǎng)絡(luò)評(píng)論信息的處理. 實(shí)驗(yàn)表明， 本方法在處理較大規(guī)模數(shù)據(jù)時(shí)具有良好的加速比， 在處理不同規(guī)模數(shù)據(jù)時(shí)具有穩(wěn)定的性能和可靠的擴(kuò)展性和伸縮性.

[1] 徐戈， 王厚峰. 自然語言處理中主題模型的發(fā)展[J]. 計(jì)算機(jī)學(xué)報(bào)， 2011， 32(8)： 1 423-1 436.

[2] DEERWESTER S, DUMAIS S T, LANDAUER T K,etal. Indexing by latent semantic analysis[J]. Journal of the American Society of Information Science, 1990, 41(6): 391-407.

[3] HOFMANN T. Probabilistic latent semantic indexing[C]//Proceedings of SIGIR. Berkeley: SIGIR, 1999: 50-57.

[4] HOFMANN T. Unsupervised learning by probabilistic latent semantic analysis[J]． Machine Learning， 2001， 42(1): 177-196．

[5] XING W, CROFT W B. LDA-based document models forad-hoc retrieval[C]//Proceedings of the SIGIR. Seattle: SIGIR, 2006: 178-185．

[6] BLEI D M. Probabilistic topic models[J]. Communications of the ACM， 2012, 55(4): 77-84.

[7] DU L, BUNTINE W, JIN H D,etal. Sequential latent dirichlet allocation[J]. Knowledge and Information Systems, 2012, 31(3): 475-503.

[8] 張小平, 周雪忠, 黃厚寬, 等. 一種改進(jìn)的LDA主題模型[J]. 北京交通大學(xué)學(xué)報(bào), 2010, 34(2): 111-114.

[9] 唐曉波, 房小可. 基于文本聚類與LDA相融合的微博主題檢索模型研究[J]. 情報(bào)理論與實(shí)踐, 2013, 36(8): 85-90.

[10] 胡吉明, 陳果. 基于動(dòng)態(tài)LDA主題模型的內(nèi)容主題挖掘與演化[J]. 圖書情報(bào)工作, 2014, 58(2): 138-142.

[11] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[12] LIN J, DYER C. Data-tntensive text processing with MapReduce[J]. Synthesis Lectures on Human Language Technologies, 2010, 3(1): 177-179.

[13] JORDAN M I, GHAHRAMANI Z, JAAKKOLA T S,etal. An introduction to variational methods for graphical models[J]. Machine Learning, 1999, 37(2): 183-233.

[14] MINKA T, LAFFERTY J. Expectation-propagation for the generative aspect model[C]//Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence. Pittsburgh: Morgan Kaufmann Publishers Inc, 2002: 352-359.

[15] PORTEOUS I, NEWMAN D, IHLER A,etal. Fast collapsed gibbs sampling for latent dirichlet allocation[C]// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas: ACM, 2008: 569-577.

[16] 孫昌年， 鄭誠， 夏青松. 基于LDA的中文文本相似度計(jì)算[J]. 計(jì)算機(jī)技術(shù)與發(fā)展， 2013(1)： 217-220.

(責(zé)任編輯： 林曉)

Research on topic extraction algorithm based on MapReduce parallel LAD model

XUE Xinggui1, GAO Jianwen1, ZHANG Bohu1, HUANG Liqin2

(1. Graduate Management Unit， Engineering University of CAPF, Xi’an, Shanxi 710086, China;2. College of Physics and Information, Fuzhou University, Fuzhou, Fujian 350116， China)

Traditional latent Dirichlet analysis (LDA) model in extracting thematic reviews exist long computing time and computing efficiency is low. Aiming at this problem, proposed MapReduce framework parallel lad model building method based on, in text preprocessing based, document-topic distribution and theme-feature word distribution, topic similarity and word feature weights were calculated, withk-means clustering algorithm, achieve comment on themes were extracted from the parallel. The experimental results show that the method can achieve near linear speedup in processing large scale text, and the effect of the model is improved by Hadoop parallel computing platform.

LDA model; MapReduce; review topic

10.7631/issn.1000-2243.2016.05.0644

1000-2243(2016)05-0644-05

2016-03-11

張伯虎(1962-)， 教授， 主要從事武警特殊裝備研究， 751141701@qq.com

國(guó)家自然科學(xué)基金資助項(xiàng)目(61471124)

TP391.1

A