基于MapReduce的并行LAD模型评论主题提取算法研究

2016-03-15 08:31薛行贵高见文张伯虎黄立勤
关键词:特征词算法文本

薛行贵, 高见文, 张伯虎, 黄立勤

(1. 武警工程大学研究生管理大队, 陕西 西安 710086; 2. 福州大学物理与信息工程学院, 福建 福州 350116)

基于MapReduce的并行LAD模型评论主题提取算法研究

薛行贵1, 高见文1, 张伯虎1, 黄立勤2

(1. 武警工程大学研究生管理大队, 陕西 西安 710086; 2. 福州大学物理与信息工程学院, 福建 福州 350116)

针对传统的潜在狄利克雷分析(LDA)模型在提取评论主题时存在着计算时间长、 计算效率低的问题, 提出基于MapReduce架构的并行LAD模型建立方法. 在文本预处理的基础上, 得到文档-主题分布和主题-特征词分布, 分别计算主题相似度和特征词权重, 结合k-均值聚类算法, 实现评论主题提取的并行化. 通过Hadoop并行计算平台进行实验, 结果表明, 该方法在处理大规模文本时能获得接近线性的加速比, 对主题模型的建立效果也有提高.

LAD模型; MapReduce; 评论主题; k-均值聚类算法

0 引言

主题模型是一种能够从大规模文本中发现文本潜在主题的概率模型, 近年来在文本挖掘领域逐渐成为研究的热点[1]. 主题模型起源于潜在语义索引, 它的发展经历了向量空间模型、 潜在语义分析模型[2]、 概率潜在语义分析模型[3]、 LDA模型及LDA扩展模型的过程. 主题模型可以形象地表达文本中语义信息, 解决了向量空间模型及其改进算法忽略特征词语义的不足[4]. LDA模型算法在文本检索[5]、 机器学习[6]、 文本聚类[7]等领域得到了广泛应用. 近年来, 国内对LDA算法的改进和应用取得了丰硕的成果. 文[8]通过一种高斯函数对特征词加权, 改进LDA 主题模型的主题分布, 提高了模型在主题表达和预测性能; 文[9]将LDA算法应用于微博主题搜索; 文[10]构建了适用于动态文本主题挖掘的LDA模型等.

但传统的LDA模型在处理海量信息和非结构化数据时存在着耗时长、 效率低下、 准确率不高等缺陷. 针对这些问题, 提出一种基于MapReduce架构的并行LDA主题模型提取算法, 在文本信息的预处理基础上, 实现LDA模型对大量文本数据的并行处理, 将大量信息清晰地展示出来.

1 算法介绍

1.1 LDA模型

主要主题能够代表着评论文本的核心思想, 对主要主题进行关键特征词的填充就可以表达某种语义信息. 评论主题提取算法核心思想是对大量评论文本进行信息抽取并简约化表达[4], 如图1所示.

图中显示LDA模型的三层结构, 箭头表示变量之间的依赖关系, 阴影区域表示处理过程中的观测变量.wmn表示第m篇文本中第n个特征词,zmn表示第m篇文本中第n个特征词的主题.θm和φk为模型两个隐含变量, 其中θm表示第m篇文本中的主题概率分布, 该分布服从一个Dirichlet先验分布,α是这个先验分布的超参数, 用来表示主题间的相对强弱.φk表示第k个主题中特征词的概率分布, 该分布服从一个Dirichlet先验分布,β是这个先验分布的超参数.φk是一个服从多项式分布的K×V的矩阵向量集合, 行向量代表文本集中的主题个数, 列向量代表文本集中的特征词数.M、Nm分别表示文本集中文本数和第m篇文本长度(特征词规模).

LDA算法初始阶段, 将针对某一事件的评论文本作为输入, 具体过程包括以下几个阶段[4]: 1)文本预处理、 特征提取; 2)利用LDA模型对输入的评论文本建立主题模型: 确定主题个数和模型参数估计; 3)主题相似度计算; 4)确定特征词汇权重.

1.2MapReduce介绍

MapReduce是一个用于海量数据处理的编程模型, 它采用了分别治理的思想[11], 基本形式有Map和Reduce两个处理阶段: 其主要的方式是将海量的数据处理任务划分为诸多子任务, 并且将这些子任务划分给一定数量的分布式的机器来并行完成批处理作业. 其中Map阶段是将原始的输入(一般是key/velue对)转换成中间结果; 而Reduce阶段则将之前产生的中间结果合并, 排序与输出[12].

2 算法实现

根据对评论主题提取算法的描述, 算法的核心主要有: 文本预处理、 模型参数估计、 主题重要度确定和特征词权重计算等部分. 而算法的主要计算量集中在文本预处理和模型参数估计过程, 因此在文本预处理和参数估计过程引入MapReduce架构, 实现主题模型提取过程的并行化.

2.1 评论文本建模

LDA模型假设文档是词的集合, 词之间可以交换顺序并忽略语法关系, 将文本映射到主题空间进行处理. 设文本集合D, 特征词集合W, 建模过程分为以下几个步骤[5]:

1) 确定主题个数K. 主题选择方法一般分为两种, 第一种是利用模型评价指标困惑度、 语料似然值等, 重复实验K, 选择使评价指标最小的主题数K作为最合适主题; 第二种是利用贝叶斯统计方法选择最合适主题数. 本文使用评价指标困惑度选择最合适主题数.

困惑度计算公式如下所示:

(1)

式中:Nd为第d篇文档长度;p(wd)表示文档d中特征词出现的概率.

2)LDA模型建立. 根据上一步得到主题个数K, 特征词集合W中第i个词wi可以表示为:

(2)

(3)

(4)

a) 构建马尔科夫链初始状态, 随机为评论文本集合中每个特征词分配一个主题;

b) 给定其它特征词的主题不变, 对当前特征词重新抽样主题并更新马尔科夫链;

c) 循环操作上一步骤, 直到抽样收敛, 此时马尔科夫链接近目标分布, 统计当前主题-特征词分布情况, 进而计算出多项分布参数θ和φ.

吉布斯抽样算法的抽样公式如下所示:

(5)

吉布斯抽样算法给出每个特征词的主题估计, 通过此时主题估计可以推导出模型分布参数θ和φ的值, 计算公式如下:

(6)

(7)

2.2 计算主题相似度

LDA建模后, 主题空间中每篇文本对应一个主题概率向量, 两评论文本相似度采用向量夹角余弦表示, 计算公式[5]如下:

(8)

式中:Pi、Pj分别表示文档i和j对应的主题分布概率向量, 且主题概率和等于1. 夹角余弦取值范围为0到1. sim(di,dj)越大, 两文本相似度越高. 当sim(di,dj)=0时, 表示两文本相互独立; 当sim(di,dj)=1时, 表示两文本语义相同.

2.3 特征词权重计算

由式(5)得到文本中词汇概率分布, 结合BM25算法, 进一步定义特征词权重计算式. 这里首先给出BM25算法的计算公式:

(9)

定义特征词wi权重计算式为:

(10)

由式(7)可以看出,W(wi)值越大, 特征词wi在文本中权重越大.

2.4 MapReduce框架

本研究在文本处理过程中引入MapReduce框架实现主题的并行提取. 其实现框架如图2:

3 实验分析

3.1 实验环境

实验采用Hadoop云计算环境, 搭建Hadoop平台. 硬件配置1个主节点和5个从节点. CPU采用Intel Core Quad2 Q6600 2.4 GHz CPU, 16 GB内存; 操作系统内核为Linux; Java 版本为1.6.0-26; Hadoop版本为1.2.0. 每个节点最多可运行2个Map操作或1个Reduce操作. 实验语料来自天涯社区、 新浪微博上抓取两个2015年事件的评论, 两个事件分别为广东河源市群体性事件和中国游客大闹曼谷机场事件. 其中, 选取广东河源市群体性事件评论集A共9 556条; 中国游客大闹曼谷机场事件评论集B共12 094条.

3.2 结果分析

利用LDA模型对评论文本进行建模, 模型中的两个超参数根据经验值取值分别为α=50/K,β=0.01[16]. 主题个数K的选取通过计算模型困惑度得到. 根据公式(1), 分别计算两个事件评论文本的最优主题数, 结果如图3所示.

从图3中可以看出, 事件1的主题数K1为20, 事件2的主题数K2为50. 因此在实验中将两个评论集的主题个数分别设为20和50, 迭代次数10. 对两个数据集分别选择不同的Data Node数进行主题建立, 其结果如图4所示. 从图4中可以看出对于两个评论集, 增加Data Node数量, 数据处理的时间显著缩短; 增加节点数量可以提高处理效率. 随着节点数量的增加, 运行时间接近线性减少. 这些变化说明基于MapReduce的并行LDA模型评论主题提取算法具有接近线性的加速比.

为进一步验证算法的性能, 分别选取不同大小的数据集, 设置Data Node节点数为6, 进行实验. 结果如图5, 可以看出运行时间随着文本规模的增加接近线性增加.

4 结论

网络包中含数以万计的用户, 每天会发表大量的评论数据, 这些数据中蕴含着海量、 待挖掘的信息, 在商业和安全领域具有重要的意义和价值. 本文通过LDA主题模型提取方法在MapReduce结构下的并行化实现, 提高了LDA算法对大量网络评论信息的处理. 实验表明, 本方法在处理较大规模数据时具有良好的加速比, 在处理不同规模数据时具有稳定的性能和可靠的扩展性和伸缩性.

[1] 徐戈, 王厚峰. 自然语言处理中主题模型的发展[J]. 计算机学报, 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] 张小平, 周雪忠, 黄厚宽, 等. 一种改进的LDA主题模型[J]. 北京交通大学学报, 2010, 34(2): 111-114.

[9] 唐晓波, 房小可. 基于文本聚类与LDA相融合的微博主题检索模型研究[J]. 情报理论与实践, 2013, 36(8): 85-90.

[10] 胡吉明, 陈果. 基于动态LDA主题模型的内容主题挖掘与演化[J]. 图书情报工作, 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]. 计算机技术与发展, 2013(1): 217-220.

(责任编辑: 林晓)

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

国家自然科学基金资助项目(61471124)

TP391.1

A

猜你喜欢
特征词算法文本
基于Simhash改进的文本去重算法
文本联读学概括 细致观察促写作
哪种算法简便
基于类信息的TF-IDF权重分析与改进①
初中群文阅读的文本选择及组织
一种面向财务文本分类的TF-IDF改进算法
作为“文本链”的元电影
Travellng thg World Full—time for Rree
进位加法的两种算法
根据问题 确定算法