模型分词工具

收稿日期:20130105基金项目:国家自然科学基金资助项目(61272446);北京市属高等学校人才强教深化计划"中青年骨干人才"资助项目(PHR201008083)作者简介:王旭仁(1972—),女,博士,副教授,E-mail:wang-xuren@163.
com.
第33卷第6期2013年6月北京理工大学学报TransactionsofBeijingInstituteofTechnologyVol.
33No.
6Jun.
2013一种并行LDA主题模型建立方法研究王旭仁1,姚叶鹏1,冉春风1,何发镁2(1.
首都师范大学信息工程学院,北京100048;2.
北京理工大学图书馆,北京100081)摘要:针对潜在狄利克雷分析(LDA)模型分析大规模文档集或语料库中潜藏的主题信息计算时间较长问题,提出基于MapReduce架构的并行LDA主题模型建立方法.
利用分布式编程模型研究了LDA主题模型建立方法的并行化实现.
通过Hadoop并行计算平台进行实验的结果表明,该方法在处理大规模文本时,能获得接近线性的加速比,对主题模型的建立效果也有提高.
关键词:MapReduce架构;并行计算;潜在狄利克雷分布模型;主题建模中图分类号:TP311文献标志码:A文章编号:1001-0645(2013)06-0590-04ResearchonParallelLDATopicModelingMethodWANGXu-ren1,YAOYe-peng1,RANChun-feng1,HEFa-mei2(1.
InformationEngineeringCollege,CapitalNormalUniversity,Beijing100048,China;2.
DepartmentofLibrary,BeijingInstituteofTechnology,Beijing100081,China)Abstract:TheexistinglatentDirichletallocation(LDA)modelusedtoanalyzethethemeofinformationhiddeninthemassivesetofdocumentsorcorpushastheshortcomingoflongercomputationtime.
Toovercomesuchadisadvantage,weproposeaparallelLDAtopicmodelingmethodbasedonMapReducearchitectureusingadistributedprogrammingmodel,thatis,theparallelimplementationoftheLDAtopicmodel.
ExperimenthasbeenfulfilledbyutilizingtheHadoopparallelcomputingplatform.
Theresultsshowthat,whendealingwithlargeamountsoftext,theproposedmethodcangetnear-linearspeedupandimprovetheestablishingeffectofthetopicmodeling.
Keywords:MapReducearchitecture;parallelcomputing;latentDirichletallocation(LDA)model;topicmodeling随着信息技术和互联网技术的迅猛发展,各类信息资源的存储量都呈现海量特征,其中文本数据始终占据着重要地位[1].
文本的主题分析旨在确定一个文本的主题结构,即确定文本包含的主题,界定主题的外延,跟踪主题的转换等.
分析结果对于信息提取、文摘自动生成、文本聚类等领域有着重要的价值.
潜在狄利克雷分析(LDA)模型是Blei等[2]在2003年提出的,属于主题模型的一种.
作为一种产生式模型,LDA模型已经成功地应用到文本分类,信息检索等诸多文本相关的领域.
MapReduce模型是一个在海量数据上进行数据处理的并行分布式计算模型,主要用来组织集群来处理大规模数据集[3].
相对传统的并行分布式计算模型而言,该模型封装了底层任务分配、并行处理、负载均衡等细节问题,用户只要集中注意力在自身要解决的分布式计算任务的表述上,极大地简化了分布式程序设计.
本文设计了一种基于MapReduce架构的并行LDA文本主题模型建立方法,用于解决处理海量数据的主题分析问题.
1LDA模型基本思想LDA是一个三级层次结构的产生式全概率生成模型,是典型的有向概率图模型,是一种对文本数据的主题信息进行建模的方法[45].
如图1所示,LDA模型层次结构依次为文集层、文档层和词层.
文集是M个文档的集合,记为D={w1;w2;…;wM};文档是N个词的序列,w=[w1w2…wN],wn表示序列中的第n个词;词是描述离散数据的基本单位.
图1LDA模型Fig.
1LDAmodel给定一个文档集合,LDA模型将每个文档表示为隐含主题的集合,其组合比例由Dirichlet分布生成.
隐含主题定义为词集上词的一个多项式分布,用来表示词之间的相关信息,这些主题被所有文档所共享,每个文档有一个特定的主题比例.
LDA模型由文集层的参数(α,β)确定,α反映文档集中隐含主题间的相对强弱,β代表所有隐含主题自身的概率分布.
随机变量θ表明文档层中各隐含主题的比重,z表示文档分配在每个词上的隐含主题比例,w为文档的词向量表示形式.
2LDA算法的MapReduce并行化2.
1MapReduce计算模型介绍MapReduce是用于大规模数据集的并行计算架构,是当前主流云计算平台的基本计算模型.
该模型的概念来源于函数式编程,一个完整的MapReduce过程包括成一个Map操作和一个Reduce操作.
其中Map(映射)函数用来把一组键值对映射成一组新的键值对,然后通过指定并发的Reduce(规约)函数来保证所有映射键值对中的每一个共享相同的键组,如下所示.
Map操作:(key1,value1)→List(key2,value2);Reduce操作:(key2,List(value2))→List(key3,value3).
用户定义的Map函数接收一组输入键值对(key1,value1),经过处理产生一组中间的键值对(key2,value2).
而后MapReduce模型对具有相同中间键key2的值value2进行聚合,产生关于key2的值集合List(value2),并且将其输入至用户提供的Reduce函数进行规约,合并该中间键的值集合,最后输出规约后的结果集合List(key3,val-ue3).
2.
2并行LDA算法的设计本文提出的基于MapReduce架构的并行LDA算法分为2个并行过程实现,即文本预处理过程和主题模型建立过程.
其原理图如图2所示.
图2并行LDA算法原理图Fig.
2PrincipleofparallelLDAalgorithm2.
2.
1文本预处理过程文本预处理需要对文档分块后,生成表示该文档的词频向量.
其中,英文文档可以直接处理,中文文档需要先进行分词才可处理.
本文采用中国科学院汉语分词系统ICTCLAS作为中文文档的分词工具[6].
这部分的MapReduce过程如图3,每个Map操作接收文档分块作为输入,统计文档分块中每个词的权重,在Reduce操作中对所有Map操作传入的各个分块的词的权重进行全局统计,统计出文档的词的权重,生成表示该文档的词频向量.
图3文本预处理的MapReduce过程Fig.
3MapReduceprocessoftextpreprocessing具体计算方式如下:Wij=TFij*IDFi.
(1)式中:Wij表示在文档Dj中,词wi所占的权重.
Wij由对应的TFij和IDFi值计算得出,具体计算公式195第6期王旭仁等:一种并行LDA主题模型建立方法研究如下:TFij=0fij=0fijmax(fij|wi∈dj)fij≠ìí0.
(2)IDFi=lgD1+j|wi∈d{}è÷j.
(3)Map操作伪代码描述如下:初始化Hash表W,key是词,value是该词出现次数从文档分块读取每个词{word1;word2;…;wordN}FORALLn∈[1,N]DOW[wordn].
value++ENDFOR输出Reduce操作伪代码描述如下:统计每个词在整个文档的权重计算表示该文档的词频向量w输出2.
2.
2主题模型建立过程该部分主要用来建立文档的主题模型.
其主要思想为:①初始化γ和;②对每个结点计算局部充分估计量和该结点的对数似然函数期望;③聚合得到全局的充分估计量并重估参数γ和;④重复步骤2和3直到模型参数收敛;⑤输出训练完毕的模型.
步骤2和3采用的MapReduce过程如图4所示.
图4主题模型建立的MapReduce过程Fig.
4MapReduceprocessoftopicmodelingMap操作伪代码描述如下:初始化V*K的矩阵和K维向量γREPEATFORALLv∈[1,V]DOFORALLk∈[1,K]DO计算局部,dni=βiwnexp{Eq[lgθiγ]}对进行标准化,dni=dni∑dni计算局部γ,γdi=αi+∑Nn=1dni计算对数似然函数期望ENDFORUNTIL对数似然函数期望收敛FORALLk∈[1,K]DO输出ENDFOR输出Reduce操作伪代码描述如下:对于充分估计量,求对数和输出对于对数似然函数的期望,求算数和输出3实验分析3.
1实验环境及实验方法为测试本文提出的算法可有效处理大规模数据,使用9台服务器搭建实验平台,采用开源的Ma-pReduce实现方案Hadoop建立了一套并行计算系统,各节点CPU均为IntelXeon2.
4GHz,内存为1GB,所用操作系统是UbuntuServer12.
04,使用的Hadoop版本是0.
20.
204[7].
将Hadoop按照项目官方网站介绍的方法进行配置,选取一台机器作为NameNode和JabTracker主节点,其他8台机器做DataNode和TaskTracker从节点.
本实验使用的数据是由国内搜狗实验室提供的搜狐网新闻精简数据集,来自2008年1月至6月期间一个月的新闻数据.
总共进行了两组实验来测试提出的并行LDA算法.
在数据集使用前,去除对于本算法有影响的标记部分,去除后的文本量大约在620MB左右.
3.
2实验结果分析在传统的LDA算法中,对于相同的数据量,影响计算时间的因素主要有提取主题个数和进行主题模型建立过程的最大迭代次数.
本实验中,固定提取主题个数为10,最大迭代次数为10.
第1组实验,选择整个数据集来测试,分别选择1~8个DataNode对上述数据集进行主题模型的建立,图5记录了DataNode数量与处理速度之间的关系.
295北京理工大学学报第33卷图5不同DataNode数量的计算时间Fig.
5Graphofcomputingtimewiththenumberofdatanode第2组实验,设置DataNode个数为4个,选取不同规模的文本量进行对比实验.
计算时间与文档数的关系如图6所示.
图6不同文本规模的计算时间Fig.
6Graphofcomputingtimewithdifferenttextscale图5是不同DataNode下处理相同文档数量的计算时间.
从图中可以看出,随着数据处理节点的增加,处理时间缩短,增加计算节点可显著提高系统对相同规模数据的处理能力,说明并行LDA主题建立算法在MapReduce架构下具有接近线性的加速比.
图6是不同文本规模下,数据处理能力相同时的计算时间.
可以看出总处理时间随着任务的增加而线性增加.
4结论本文研究并实现了LDA主题模型建立方法在MapReduce编程架构下的并行化实现,使LDA算法能够适应海量数据的处理,在不降低准确度的情况下提高该算法的数据处理能力和计算效率.
经过实验表明,此方法在数据集规模较大时有较好的加速比,而且MapReduce架构相比基于普通算法的系统在可伸缩性上有了很大提升,使本方法可以切实提高系统的总体性能和扩展性.
参考文献:[1]FabrizioSebastiani,AlessandroZanasi.
Textcategorization[C]∥ProceedingsofTextMiningandItsApplications.
Southampton,UK:WITPress,2005:109129.
[2]BleiD,NgA,JordanM.
LatentDirichletallocation[J].
JournalofMachineLearningResearch,2003,3:9931022.
[3]DeanJ,GhemawatS.
MapReduce:simplifieddataprocessingonlargeclusters[J].
CommunicationsoftheACM:50thAnniversaryIssue,2008,51(1):107113.
[4]李文波,孙乐,张大鲲.
基于labeled-LDA模型的文本分类新算法[J].
计算机学报,2008,31(4):620627.
LiWenbo,SunLe,ZhangDakun.
Textclassificationbasedonlabeled-LDAmodel[J].
ChineseJournalofComputers,2008,31(4):620627.
(inChinese)[5]石晶,范猛,李万龙.
基于LDA模型的主题分析[J].
自动化学报,2009,35(12):15861592.
ShiJing,FangMeng,LiWanlong.
TopicnalysisbasedonLDAmodel[J].
ActaAutomaticaSinica,2009,35(12):15861592.
(inChinese)[6]中国科学院计算技术研究所.
ICTCLAS汉语分词系统[EB/OL].
[20110512].
http:∥ictclas.
org/.
TheInstituteofComputingTechnologyoftheChineseAcademyofSciences.
ICTCLASChinesewordsegmentationsystem[EB/OL].
[20110512].
http:∥ictclas.
org/.
(inChinese)[7]ApacheHadoop.
Welcometoapachehadoop[EB/OL].
[20110620].
http:∥hadoop.
apache.
org/.
(责任编辑:刘芳)395第6期王旭仁等:一种并行LDA主题模型建立方法研究