《基于hadoop的中文并行lda算法及在电子病历挖掘中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
＊？＠’斯素硕±学位论文论文题目：某干ＨａｄｏｏＤ的中女并行ＬＤＡ算法及在电子病＊历巧擺中的应用Ｔ晓琳；作者挂若叶枫指导教师学科专业管理科学与王程培养类别全日制学术型硕去＿所在学院经资管理学院提交日期２０１６年１２月５日■ 浙江王业大学学位论文原创性声明的指导下，独立进行本人郑重声明；所提交的学位论文是本人在导师研究。除文中己经加Ｗ标注引用的内容外，本论文工作所取得的研究成果过的研究成果，也不含为获得浙江不包含其他个人或集体己经发表或撰写材料。对本义的研究作出工业大学或其它教育机构的学位证书而使用过的重要贡献的个人和集体，巧已在文中臥明确方式标明。本人承担本声明的法律责任。、日期；年／之月＞曰作者签名；Ｊ斯学位论文版权使用授权书，同意本学位论文作者完全了解学校有关保留、使用学位论文的规定学校保留并向国家有关部口或机构送交论文的复印件和电子版，允许论文的全部或部分内被查阅和借阅。本人授权浙江工业大学可切将本学位论文＾采用影印、缩印或扫描等复制手段保存容编入有关数据库进行检索，可和汇编本学位论文。本学位论文属于一年解密后适用本授权书。１、保密□，在Ｓ年解密后适用本授权书。２、保密□，在３、不保密囚／＂＂（请在上相应方框内打Ｖ）＾：八／（）年／之月Ｔ日日期作者签名：诚＾Ｊ邱｝年ａ导师签日期；＞〇化月Ｔ日名；心 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用摘要电子病历作为互联网医疗的基础技术，记录了病人的临床诊疗记录，是极具价值的数据资源。我国市级以上医院的病历信息系统的总数据规模估计在100TB以上，日新增数据的数量级为GB，数据类型多样，符合学术界对大数据的定义。目前对电子病历的数据挖掘实践多采用在单台计算机上运用常规的聚类分类算法和关联规则处理结构化数据的分析方法，不能较好地适应大数据环境。Hadoop是当前热门的分布式处理系统，通过组合数量巨大的廉价通用硬件形成巨大的资源池，部署简单，容错能力较高，因此本文以Hadoop为平台构建大数据分析算法的并行程序。本文选择主题模型中的LDA模型作为并行化的目标，参数估计方法为塌缩Gibbs采样法。k本文引入点互信息算法PMI对ICTCLAS分词系统增加了词库的动态更新功能，并给出了处理大规模数据集的并行框架。将输入的文档从外部和内部分块，为避免参数采集中的依赖性，采用对角线法分配数据。在塌缩吉布斯采样时统计每一个单词在所有文档中的词频，在归一化词频向量上叠加合适的随机数序列，过滤掉低于阈值的词语。I 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用本文采用复旦大学的中文语料库从准确率、困惑度、加速比三个指标分析实验结果，得到如下结论：改进后的分词算法能有效增加分词准确率和召回率；改进的并行LDA算法能显著减少模型运行时间。最后，本文以真实新生儿电子病历集为挖掘对象，采用并行LDA算法进行文档分类和特征发现。挖掘结果显示算法分类的准确率较高；算法输出的描述性的词语矩阵包含了候选特征，通过单因素方差分析检验对四种新生儿疾病患病率有显著影响的因素。关键词：医疗大数据，并行LDA，Gibbs采样，Hadoop论文类型：应用/专题研究II 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用CHINESEPARALLELLDAALGORITHMBASEDONHADOOPANDDATAMININGINELECTRONICMEDICALRECORDSABSTRACTAsthebasisofInternetmedicaltechnology,electronicmedicalrecordsarevaluableresourcecontainingthepatient'sclinicaldiagnosisandtreatmentrecords.Thetotaldatasizeofthemedicalrecordinformationsystemisabove100TB,andthenewdateisgrowingrapidlly.Thedatatypesarediverse,whichconformstothedefinitionoflargedatainacademiccircles.Atpresent,thedataminingpracticeofelectronicmedicalrecordsisbasedonthetraditionalclusteringalgorithmandassociationruleanalysis,whichprocessesstructureddataonasinglecomputerandcannotadapttothelargedataenvironment.Hadoopiscurrentlyapopulardistributedprocessingsystem,throughthecombinationofalargenumberofcheapgeneral-purposehardwaretoformahugeresourcepool.HadoopissimpletodeployandhashigherfaulttolerancecomparedtoSpark.ThispaperchoosestheLDAmodelinthetopicmodelasthegoalofparallelization,andtheparameterestimationmethodisGibbssamplingmethodInthispaper,weintroducethepointmutualinformationalgorithmPMIktoincreasethedynamicupdatefunctionofICTCLASwordsegmentationsystem,andgiveaparallelframeworktodealwithlarge-scaledatasets.Theinputdocumentsaredividedfromtheexternalandinternalsub-block,inordertoavoidthedependenceoftheacquisitionparameters,theformistheuseofdiagonaldistributionofdata.IntheGibbssamplingeverywordcountsthenormalizedwordfrequencyvectorsuperimposedontheappropriaterandomnumbersequence,thenwefilteroutthewordsbelowthethreshold.Inthispaper,theChinesecorpusofFudanUniversityisusedtoanalyzetheexperimentalresultsfromthethreeindexesofaccuracy,confusionandspeedup.Theresultsshowthattheimprovedwordsegmentationalgorithmcaneffectivelyimprovetheaccuracyandrecallrateofthewordsegmentation.TheimprovedparallelLDAalgorithmcansignificantlyreduceModelruntime.III 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用Finally,thispapertakestherealelectronicmedicalrecordsofnewbornsastheobjectofdatamining,andusestheparallelLDAalgorithmfordocumentclassificationandfeaturediscovery.Theresultsofminingshowthattheaccuracyofalgorithmclassificationishigh.Thedescriptivelexicalmatrixofthealgorithmcontainsthecandidatefeatures.Thesinglefactoranalysisofvariance(ANOVA)isusedtotestthefactorsinfluencingtheincidenceoffourneonataldiseases.KEYWORDS:Medicaldata;ParallelLDA;Gibbssampling;HadoopTYPEOFDISSERTATION/THESIS:ApplicationResearchIV 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用目录摘要....................................................IABSTRACT...........................................III1绪论..................................................11.1选题背景与意义..............................................11.2相关研究现状.................................................21.2.1LDA算法研究现状.......................................31.2.2医疗行业数据挖掘现状...................................41.3本文的研究工作...............................................51.4本文结构.....................................................62主题模型技术综述......................................72.1LDA模型简介.................................................72.2模型前提....................................................82.2.1贝叶斯法则.............................................82.2.2狄利克雷分布...........................................92.3建模........................................................92.4塌缩吉布斯采样算法.........................................122.5LDA缺点与改进..............................................162.6本章小结...................................................173基于Hadoop的中文LDA算法设计........................183.1中文文本向量化并行算法......................................183.1.1去除符号、停用词......................................183.1.2中文分词工具..........................................183.1.3中文分词并行算法......................................203.2基于Hadoop的并行LDA算法设计..............................213.2.1分布式处理系统........................................213.2.2数据分块..............................................22V 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用3.2.3过滤低频词............................................233.2.4算法处理过程..........................................243.3算法实现...................................................253.4本章小结...................................................294实验分析.............................................314.1实验环境及测试数据..........................................314.2分析指标....................................................314.3过程及结果分析..............................................324.4实验结论与存在的问题........................................374.5本章小结...................................................375并行LDA算法在新生儿疾病挖掘中的应用.................395.1新生儿疾病及诊断特征.......................................395.2影响因素分析...............................................395.3实验设计...................................................405.3.1数据来源及预处理......................................405.3.2参数设置..............................................415.3.3算法运行结果..........................................435.4挖掘结果与分析.............................................455.4.1分类准确率............................................455.4.2主题的内容倾向........................................465.4.3单因素方差分析........................................475.5本章小结...................................................506总结与展望...........................................526.1总结.......................................................526.2展望.......................................................53参考文献...............................................54致谢58攻读学位期间参加的研究工作和获得的学术成果59VI 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用图、表目录图2.1LDA图形模型.........................................................................................10图3.1数据分块与处理过程示意................................................................................23图4.1阈值变化-计算时间/困惑度曲线....................................................................33图4.2主题数-困惑度曲线............................................................................................34图4.3迭代次数-困惑度曲线.......................................................................................35图4.4Mapper数-加速比曲线.......................................................................................36图4.5Reducer数-加速比曲线......................................................................................37图5.1词典更新算法的新词.........................................................................................41图5.2阈值-困惑度曲线................................................................................................42图5.3迭代次数-困惑度曲线.......................................................................................42图5.4文档-主题多项分布............................................................................................43图5.5主题-词语多项分布............................................................................................44图5.6描述每个主题的词语.........................................................................................44图5.7*.tassign矩阵.........................................................................................................45图5.8预测新文档主题..................................................................................................45图5.9性别因素的显著性检验....................................................................................49表2.1LDA模型的参数说明...........................................................................................9表2.2算法1-LDA算法框架.......................................................................................12表2.3算法2-MCMC算法...........................................................................................13表2.4CGS算法新增参数名称....................................................................................13表2.5算法3-基于塌缩吉布斯采样的LDA算法..................................................15表3.1算法4-分词词典更新并行算法......................................................................20表3.2算法5-低频词过滤并行算法...........................................................................24表3.3并行中文LDA算法的参数说明....................................................................25表3.4算法6-并行LDA算法的总体设计...............................................................26表3.5MapperStart过程框架.........................................................................................27表3.6Map过程框架....................................................................................................28表3.7MapperFlusht过程框架......................................................................................29表3.8Reducer过程框架................................................................................................29表4.1Hadoop集群机器的配置...................................................................................31表4.2Hadoop集群机器软件环境...............................................................................31表4.3分词准确性对比..................................................................................................33VII 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用表5.1新生儿疾病数据集信息.....................................................................................40表5.2四种主题中重要性水平前十的描述性词语..............................................46表5.3四种疾病的候选影响因素.............................................................................46表5.4四种主题中重要性水平前十的描述性词语..............................................47表5.5G6PD患儿信息统计表...................................................................................48表5.6G6PD疾病因素的显著性检验.....................................................................49表5.7其他三种新生儿疾病因素的显著性检验..................................................50VIII 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用1绪论1.1选题背景与意义2015年3月，李克强总理在第12届全国人民代表大会作政府工作报告时提出“互联网＋”战略，核心思想是利用互联网平台和云计算、大数据、移动互联网、物联网等技术，推动互联网与现代产业结合，促进产业换代升级[1]。例如互联网与传统的通信、交通、金融、零售、医疗、教育等产业生态融合，已经形成即时通讯、打车拼车、P2P理财、购物网站、互联网医疗、远程教育等新产业。在这些新兴产业中，互联网医疗产业规模较为巨大且尚未出现有代表性的产品，需要研究者重点关注。2015年3月，我国颁布了《全国医疗卫生服务体系规划纲要（2015—2020年）》，明确提出积极应用移动互联网、物联网、云计算、可穿戴设备等新技术，推动惠及全民的健康信息服务和智慧医疗服务，推动健康大数据的应用。由目前一系列的试水项目可知，互联网医疗包括且不局限于自我诊断、医生远程诊疗、心理健康服务、慢性病远程监控、小型外科紧急护理、零售医疗、健康APP等，预估产业规模在万亿美元级别。据美国某个研究中心的数据表明，有75%左右的美国人在因特网上收集健康信息，其中40%的人根据收集到的信息判断自身健康情况，这种行为在互联网医疗中被称为自我诊断。发明于30多年前的远程医疗也在近期随着互联网的热潮悄然兴起，2013年美国大约有1500万人接受了远程医疗。随着技术的进步，远程医疗的服务范围必将不断扩大。从技术角度，互联网医疗涉及到大量的视频、电子病历的储存、分析、传输和各种医疗设施的支持，其中的一项基础技术是标准化电子病历。电子病历（EMR，ElectronicMedicalRecord），也称为电子医疗记录，是将病人在临床治疗中使用到的病因、病程、诊断和治疗计划、检查结果、预后等信息以多种数据形式储存在计算机中的病历记录。它包含的数据类型有文本、数字、图形、图像、视频等等。通过对病人的电子病历进行挖掘，研究者可以得到对临床有指导意义的结果，例如疾病的发病因素、病情发展、治疗方法和效果评估等。据统计，截至2014年末，我国现有的2万多家市级以上医院中超过90%拥有医疗信息系统和病历信息系统，数据规模估计在100TB以上，类型包括手写病历、费用登记记录、纸质处方、X光胶片、MRI和CT影像等非结构化数据。每天新增数据量以GB甚至TB计。在数字信息大爆炸时代，数据中蕴含的价值也被重视，通过对人工智能、机器学习、统计学、数据库的交叉研究，诞生了数据挖掘、数据分析等计算机科学，方便研究者从海量数据中提取模式和知识。但是实践中由于数据结构化和分析方1 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用法等技术原因，只有5%的数据被用作数据分析。目前医疗行业中病历系统的数据使用、分析和挖掘远远不足，在大多数市级医院，病历系统除了完成病人的登记手续、记录和查看诊治过程、查看费用、结算费用之外，仅有医院行政部门统计一些简单指标，或是医院某科室联合信息部门对本院病例进行基本数据挖掘。考虑到适用于分析的病例数目较大，病历数据又是动态关联、不断更新的，基本的数据挖掘方法亟需改进。如何有效地处理医疗大数据得到有价值的信息，是医疗行业管理者关注的焦点，也是难点。大数据具有Volume（海量）、Velocity（高速）、Variety（多样）、Value（价值）四个维度的特征，难以用普通的数据库和统计工具管理[2]。2004年谷歌实验室提出MapReduce模型，用来处理大于1TB（1TB=1012GB）数据集的并行运算。并行计算以并行方式运行程序，将原本单向计算的串行程序改造为数个程序同时计算的并行框架，在指定时间段内增加了产出。基于该模型，NUTCH搜索引擎小组开发了开源分布式基础架构系统Hadoop，这个系统可以使数量巨大的廉价通用硬件形成巨大的资源池，从而组成威力巨大的分布式集群系统，从关系型数据库和非结构化文本中尽可能快的提取数据，并且经过十多年发展，Hadoop系统已经发展成为Hadoop生态链。由于迭代计算的原因，很大一部分数据挖掘和数据分析方法需要重新设计以适应并行化环境。本文选择了一种文本挖掘中常用的通过生成概率自动提取文本隐含语义的主题模型（TopicModels）进行并行化设计与实现，采用的算法是潜在狄利克雷分布（LatentDirichletAllocation，LDA）。LDA的主要思想是在不知道被分类类别概率分布的判别式函数前提下，用聚类后的无标记训练样本集估计概率分布参数，用来识别大规模文档集或语料库。LDA算法的参数估计可以使用变分贝叶斯法或Gibbs采样法，但这两种方法都有各自的缺点。变分贝叶斯法得到的结果精度不高，且可能会陷入局部最优解；Gibbs采样法计算复杂度高，参数之间相互依赖，不能满足分析大数据的需求。因此对LDA算法的参数估计开展并行化设计和步骤优化仍需要大量研究，以便进一步提高算法对海量中文数据的适应性，快速准确的估计出模型参数。十几年来，医疗行业的研究者持续使用关联规则算法和常见的分类聚类算法对小规模的结构化数据进行数据挖掘。挖掘目标主要有发现风险因素间相互关系和权重，以及对疾病的缓急轻重和发展过程进行分类预测两大类。近年来，使用大数据挖掘方法处理电子病历的研究也逐渐增多，研究内容主要是临床知识库构建、挖掘平台架构等基础工作。在数据挖掘结果辅助临床医生诊断疾病、追踪病因、优化现有治疗方案、评价疗效等方面还需深入研究。2 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用1.2相关研究现状1.2.1LDA算法研究现状2003年，DavidBlei，AndrewNg及MichaelJordan在《机器学习研究期刊》（JournalofMachineLearningResearch）上发表了对潜在语义索引（LatentSemanticIndexing，LSI）的改进算法——LDA算法[3]。如今它已是最流行的概率主题模型之一，能够从一个大的语料库中发现实际应用中推断的主题。LDA的参数估计算法可大致分成三类：变分贝叶斯（VariationalBayes）（Bleietal.2003）、Gibbs采样[4]（GriffithsandSteyvers2004）、置信度传播[5]（BeliefPropagation，BP）（Zengetal.2012）。如果按计算方法来分类，LDA的参数估计可以分为两种类型。第一种是基于随机梯度下降（stochasticgradientdescent，SGD）的算法，采用每个单词的主题后验分布依次更新LDA参数的思想。基于SGD的算法包括吉布斯采样、塌缩变分贝叶斯法，和异步BP算法。另一种是基于坐标下降算法（coordinatedescent，CD），先设置一个参数用于估计主题-单词后验概率，然后调整推断的后验概率反复估计参数。典型的基于坐标下降算法是变分贝叶斯和同步BP算法。由于海量数据变得越来越普遍，对海量数据的主题建模技术吸引了许多研究者的兴趣。主题算法的应对策略主要可分为主题在线算法和主题并行算法两大类。在线算法是将大数据流用微型分批处理，并行架构则是使用多核处理器加快主题模型。尽管在线算法使用更少的计算资源，但是它的准确率取决于几个参数。在线算法比单机算法快2-5倍（Hoffmanetal.2010）[6]，并行算法比单机算法快700倍（Newmanetal.2009）[7]。由于并行架构被广泛使用，且部署成本较低，并行LDA算法是加速主题模型的理想选择（Zhaietal.2011）[8]。Newmanetal（2007）提出了两种LDA模型并行策略，分别是近似分布LDA（ApproximateDistributedLDA，AD-LDA）和分层分布LDA（HierachicalDistributedLDA，HD-LDA）[9]。AD-LDA的主要思想是将语料库划分为多个文档块，对每一个文档块进行吉布斯采样，词表完整复制到每块，结束一次采样后汇总并更新参数，继续下一次采样。这种采样方式被称为塌缩Gibbs采样（CollapsedGibbssampling,CGS），“塌缩”是指模型中的几个先验参数被边缘化并缩略（collapsedout）为已知量。CGS是对模型的近似实现，精度略有下降。HD-LDA则是一个四层贝叶斯概率模型，为提高精度，在标准模型的基础上对主题-词语分布再加一层，计算复杂度较高。学术界对HD-LDA的研究较少。分布式处理器上的AD-LDA算法不可避免的遇到了通信成本过高这一问题。通信成本会影响并行LDA算法的规模（Wangetal.2009）。2009年ArthurAsuncion等人开发了LDA异步算法（AsynchronousDistributedLDA，Async-LDA）[10]。特点是在任意两个完成采样过程的数据块中合并参数并进行下一次采样，改进了AD-LDA中的等待所有采样过程结束后再进行汇总与更新的处理过程，减少了3 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用等待时间。然而缺点是迭代次数会明显增加，收敛速度较慢。YiWang等人首先在2009年实现了MapReduce框架下的AD-LDA算法，它采用了MPI信息传递接口[11]。PLDA+（Liuetal.2011）采用了数据分割，流水线处理，词语绑定和优先级调度四种方法[12]。Chang（2011）设置了最长计算时间的方法来降低通信成本，减少通信瓶颈[13]。虽然较长的计算时间能掩盖通信成本，但是通信频率的降低可能会导致性能糟糕。雅虎提出了YLDA（Ahmedetal.2012），构建基于共享内存的并行方式，通信成本仍为算法的瓶颈[14]。邱卓林（2015）使用Spark框架并行化AD-LDA，Spark框架是在内部存储器（memory）中集成了MapReduce系统处理数据，对机器的内存有较高要求[15]。在相同的框架下，PGS的可扩展性和应用性比其他推导算法优秀。YangGaoetal.（2015）在MapReduce并行架构上运行PGS、PBP、PVB算法，对比发现PGS与PBP、PVB相比更具可扩展性，主要表现为内存占用率低，原因是它的采样方法更有效[16]。PGS在搜索引擎和在线广告系统方面也有最佳表现。PBP相比PGS消耗更多的内存空间，也不适用于主题较大的数据，但它适用于基于对数似然估计的预测，即具有最佳的建模性能。PVB的预测和应用性能较差，运算速度也最慢。1.2.2医疗行业数据挖掘现状随着医疗产业信息化的深入与发展，医疗信息的综合分析对决策的作用已经日益重要。如何通过对病人的电子病历进行挖掘，可以得到对临床有指导意义的结果，例如疾病的发病因素、病情发展、治疗方法和效果评估等，是当前医疗行业数据分析的热点目标。医疗数据挖掘当前主要是在生物医学、临床医学及基础医学上有应用，国内外研究主要分为以下几类：第一类是发现风险因素间相互关系和在疾病发病中的作用。使用关联规则算法挖掘病历信息，可以发现因素间的相互关联度，通过置信度和支持度筛选得到关联规则结果用于分析。在十几年前，发现关联规则的数据挖掘方法已经在医疗行业受到很高的重视，如陆建红等（2003）利用肿瘤诊断数据库中的多个属性来挖掘出关联规则[17]。张高峰等（2008）应用关联规则对医学中心的产科病数据进行了早产的危险因素分析[18]。丁卫平（2008）提出了一种基于频繁概念格的FCLattice电子病历关联规则挖掘算法，研究了不同疾病在某类病人之间的并发情况、并发规则[19]。曾勇（2014）对广东三九脑科医院电子病历数据进行挖掘分析，随机抽取癫痫病种住院病历资料，尝试采用经典关联规则Apriori算法找出癫痫病种的病因构成[20]。除了对发病因素进行关联规则分析外，还可对医生处方数据中的药物进行关联规则挖掘比较。曾逸笛等人（2015）通过对老年性痴呆的中医4 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用处方研究分析用药的关联规则，得到置信度较高的药对和三味中药[21]。第二种研究对象是对疾病进行分类，判断疾病的缓急轻重以及疾病的发展过程。粗糙集理论、人工神经网络在疾病诊断方面比较有效。粗糙集理论适用于处理数据不完整和不一致的问题，在机器学习的分类算法中被广泛使用。Wu（2015）采用粗糙集设计了一种快速健康评估算法，并使用实际数据进行仿真分析，发现该算法有较高的准确度[22]。饶静（2015）对比神经网络算法、决策树、支持向量机三种分类算法对心电信号进行分类的准确率，发现决策树算法最适合该应用场景[23]。吴生根等（2015）利用决策树方法分析重症手足口病的危险因素，并用于预测该疾病的重症病人[24]。近三年来大数据正逐渐影响医疗卫生领域。研究内容主要包括医疗数据挖掘平台构建，医疗大数据临床语料库的构建，和对地区性和季节差异性疾病、传染病的监督预警等。王冬冬（2015）将不同科室、不同系统中的临床数据整合到基于openEHR的数据仓库中，建立医疗大数据中心[25]。鞠美芝（2016）将自然语言处理技术和条件场理论用于中文病历文本处理，构建中文医疗术语语料库[26]。学术界对医疗行业大数据的应用研究方兴未艾。1.3本文的研究工作各行各业利用互联网平台、云计算和大数据等技术，推动产业升级是行业发展的大趋势。医疗行业，不论是理论上还是实践中，对大数据技术的研究远远不足。本文研究目标是对医疗行业的电子病历进行大数据挖掘，得出关于疾病防治方面的知识。考虑到电子病历多用短文本，而主题模型是一种有效的通过生成概率自动提取文本隐含语义的文本挖掘方法，本文在相关研究的基础上选择MapReduce框架下的LDA主题模型作为基本方法，并改进了分词方法和并行方式。通过实验验证了改进后的并行算法有效提高了准确性，缩短了运行时间。最后，以真实电子病历集为挖掘对象开展数据分析，并得到了若干结论与建议。本文主要工作如下：1、深入研究常见聚类分类方式的不足常见聚类分类方式的不足之处包括：不能有效处理大规模数据集，处理的数据类型不够丰富，相似性度量与主题度量不能共存，对短文本的支持力度不够等。而LDA主题模型能理解文字间的语义关系，生成的主题-词语矩阵能够描述这个主题的特征，能够支持视频图片的数据类型，更能表示短文本的特征。LDA模型不仅能发现分类规则，也能基于有效降维来度量对象间的相似性，既可以是分类算法，又可看作聚类算法。2、并行LDA算法的框架选择与改进本文采用分布式文件处理的方式处理大数据。目前实践中使用较多的分布式5 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用文件处理系统主要是Hadoop和Spark两种。本文综合比较节点内存、容错性、运行时间等各项指标，最终选择基于Hadoop的MapReduce框架作为并行框架。之后，对现有的分词算法增加了动态更新功能，使之更适用于专业领域的分词；对数据分块技术进行改进，将文档内外部分块后复制到节点中，减少参数规模；在节点的Gibbs采样算法中加入低频词过滤算法，加快算法收敛速度。最后用复旦大学的中文测试集从准确率、困惑度、加速比三个指标分析实验结果，验证了改进的并行算法的优势。3、电子病历的数据挖掘以真实新生儿疾病电子病历集为挖掘对象进行文档分类，并且利用LDA算法特征找到描述疾病的词语矩阵，选出重要性水平高单词作为候选特征，检验对新生儿疾病患病率有显著影响的因素。最终得到了若干结论与建议。1.4本文结构本文一共包含六个章节。每章的主要内容安排如下：第一章：绪论。第一部分包括本文研究背景和意义，主题模型和医疗数据挖掘算法的研究现状，最后描述了本文主要工作和结构安排。第二章：主题模型技术综述。简要介绍了LDA主题模型的建模、推导与参数估计方法，重点介绍了基于吉布斯采样的参数估计方法。第三章：基于Hadoop的中文LDA算法设计。此部分先使用中文分词工具对文本进行向量化处理，并考虑到待处理文档的专业性设计了词库更新算法。接着，在数据分块、低频词过滤方面改进现有的基于Hadoop的并行LDA算法，设计了相应计算框架与实现过程。第四章：实验分析。主要介绍了测试集来源、实验环境，从准确率、困惑度、加速比三个指标详细分析实验结果。第五章：电子病历的挖掘与分析。挖掘产妇和新生儿疾病筛查的电子病历，从疾病分类、相关影响因素两方面进行数据分析。第六章：总结与展望。总结整篇论文，针对存在的问题提出未来研究方向。6 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用2主题模型技术综述2.1LDA模型简介主题模型（TopicModels）是一种文本挖掘中常用的通过生成概率自动提取文本隐含语义，从而对大规模离散数据集有效降维的技术[27]。目前文本挖掘领域中主题模型和潜在语义索引（LatentSemanticIndexing，LSI）两种降维技术表现最为突出。LSI采用了标准的矩阵分解技术（奇向量分解）找到潜在语义空间。而主题模型提供了用于降维的主题概率框架，其类型有概率潜在语义索引（PLSI）和潜在狄利克雷分布（LDA）。LDA是由DavidBlei，AndrewNg及MichaelJordan于2003年发表在《机器学习研究期刊》（JournalofMachineLearningResearch）的概率语言模型。在PLSI的基础上，Blei增加了贝叶斯公式，在不知道被分类类别概率分布的判别式函数前提下，用聚类后的无标记训练样本集估计概率分布参数，由此开发出一种新的主题模型LDA，用来识别大规模文档集或语料库。当时Blei使用的是变分EM训练方法，该算法比较复杂并且得到的是局部最优分布，由ThomasGriffiths和MarkSteyvers在2004年时引入了Gibbs采样方法，并演化为CollapsedGibbs采样法，推导较为简洁，被广泛使用到自然语言处理、文本挖掘等领域，在社交平台话题分析、视频场景分析、人脸识别、异常检测等应用场景中发挥了巨大的作用。最近对LDA研究的进步已经使它适用于大型和动态数据集的降维，使得研究广度与深度进一步扩大。由于算法中包含了贝叶斯推断这一典型的分类算法，LDA的主要功能就是通过无监督学习分析未知类别训练集，从中发现分类规则，以此预测新数据的类别。同时，由于它拥有降维的特性，能够度量对象间的相似性，也有研究者将它用作聚类算法。作为一种分类算法，LDA的分析对象类型可以是图像、文本、视频等，目前研究的主要内容是基于LDA的文本分类。与决策树、贝叶斯、K-近邻等分类算法相比，该算法的核心优势就在于能高效处理大规模训练集，且数据类型更丰富。与SVM、人工神经网络相比，在预测率相似的情况下LDA能够解决传统分类中相似性度量与主题度量不能并存的问题[28]。并且，一项针对短文本的研究表明，LDA方法比SVM方法更能表示短文本的特征[29]。与典型聚类算法K-Means相比，LDA在处理高维数据方面具有较大优势。与LDA相比，K-Means结果好坏过分依赖于对初始聚类中心的选择，容易陷入局部最优解，对异常数据较为敏感，并且只能处理数值属性的数据。与人工神经网络方法和基于进化理论的方法（模拟退火算法、蚁群算法、遗传算法等）相比，LDA算法会建立主题-词语矩阵，这些词能够描述这个主题的特征，其他算法都7 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用没有这个功能。这相当于用这些词为隐含的主题建模，而主题为文章建模，能够由此判断两个文章的相似性。在此之前，文章的相似性比较的典型方法是采用tf-idf方法，没有考虑到文字之间的语义关系，这就是LDA区别于传统文本聚类的优势。而且，尚未出现人工神经网络方法和基于进化理论的方法在处理视频信息方面的研究。当然LDA也与这两种方法有相同的缺陷，比如过于依赖一些经验参数的选取，具有较高的计算复杂度等。2.2模型前提2.2.1贝叶斯法则贝叶斯法则是由统计学家贝叶斯推导出来的一种通过某些观察值推断概率的一种方法。它由条件概率公式变形而来。假设有两个事件A、B，事件A先发生，贝叶斯法则为：P(|)()BAPAP(|)AB（2.1）PB()公式2.1左侧P（A|B）称为A的后验概率，是事件B发生之后对A概率进行的调整。如果后验概率大于1，A事件发生的可能性变大；如果后验概率小于1，意味着事件A的可能性变小。若等于1，说明B的发生与A发生没有关系。右侧P（A）为A的先验概率，是B发生之前主观上对A的概率进行的判断。PP(|)BA（B）为标准化常量。被称为标准似然度，公式2.1也可表示为A的后PB()验概率=A的先验概率×标准似然度。P（A|B）随着P（A）和P（B|A）之积的增长而增长，如果B独立于A时被观察到的可能性越大，那B对A的支持度越小。给定数据A时集合B中可能性最大的假设被称为极大后验假设，可以用贝叶斯公式计算每个候选假设的后验概率来确定极大后验假设，计算公式如下：A_map=argmaxP（A|B）=argmaxP（B|A）*P（A）/P（B）=argmaxP（B|A）*P（A）（2.2）约去了不依赖于A的常量P（B）。某些情况下假设P（A）相同，式子可以进一步简化成求P（B|A）的最大值来寻找极大似然假设，P（B|A）常被称为给定A时B的似然度。8 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用2.2.2狄利克雷分布对于语料库中的每篇文档，LDA假想了它的生成过程：文档的产生是一个随机生成过程，文档（Document）是潜在主题（Topic）服从一定分布的样本集合，潜在主题（Topic）是单词（Word）服从一定分布的样本集合，一般认为这两种分布都是多项分布（MultinomialDistribution）。多项分布是二项分布在K维的扩展，而二项分布的先验β分布也可以扩展到K维，称为狄利克雷分布（DirichletDistribution）。狄利克雷分布是多项分布的先验分布，它与多项分布共轭（分布函数形式相同）。从狄利克雷分布上绘制出来的每个样本就是多项分布的参数向量，分布率为：k)KPp(|)Dirp(|)k1kpk1（2.3）kkk1()kk1dim1K()pk1，()k1k()k()dim（2.4）k1k1kα为狄利克雷分布的参数，写作D(。多项分布的参数向量p服从参数α的分布，所以α也被称为超参数。根据狄利克雷分布在向量p上的积分为1，得到公式kpk1dp()k（2.5）pk12.3建模LDA模型的中心思想是语料库D中的每篇文档Di是K个潜在主题的多项分布，记作θj，θj的先验概率来自于超参数为α的Dirichlet分布。每个主题k在词表V词语上的多项分布记作φk，φk的先验概率来自于超参数为β的Dirichlet分布。某文档Di的第j个词xij属于的某个主题zij来自Vθj，xij来自Vφk。模型中的参数与说明见表2.1。表2.1LDA模型的参数说明变量英文名性质带下标的变量名行列元素特征αhyperparameter狄利克雷分布//人为设的参数置9 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用续表2.1LDA模型的参数说明βhyperparameter狄利克雷分布//人为设的参数置θtopicdistributionfor文章-主题多项θi：文档D在主KxD矩阵输出document分布题上的多项分布φtermprobabilitiesfor主题-词语多项φk：主题K在KxV矩阵输出topic分布term上的多项分布ztopicofeachtoken每个词的主题zij：第i篇文档中NxK矩阵可计算第j个词的主题xtoken词语，构成主题Xij：第i篇文档DxN矩阵可计算的最小单位的第j个词Ktopicnumber主题个数/K维向量待定参数Dducumentnumber文档个数Di:第i篇文档D维向量可计算Vtermnumberin词表中词的个Vt:词表中序号V维向量可计算vocabulary数为t的词Ntokennumberin文档中的词元Ni：第i篇文档Kx2矩阵可计算document个数中词的个数LDA图形模型表示了这些随机变量是如何联系的：αθjzijβΦkxijKNjDi图2.1LDA图形模型在该图中，每一个随机变量由圆和正方形表示。圆表示连续的随机变量，长方形表示离散的随机变量。有阴影的变量表示这个结果已知（xij可以被观测到，超参数α和β是预先设置的）。如果一个变量的结果取决于第一个变量的值，则会有一个箭头从第一个变量指向另一个。长方形表示该组被重复多次，例如每10 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用个文档和每个词元。选择主题-词语的概率分布，即主题K下所有单词的概率分布是多项分布，服从参数为β的对称狄利克雷分布。x()W1KKxD(p|)x（2.6）)]v1计算每篇文章的主题分布矩阵，在一篇文章中主题服从参数为α的狄利克雷分布。狄利克雷分布抓住了每篇文章的独立性和文章内部的高耦合性这两个特征。k()kD(p|)k1kk1（2.7）iikikk1k)k1选择每个词元的主题。主题Zij是从文章-主题的分布中选择出来的。zulti(Mkpz|)（2.8）ijiijiik选择每个词元。每个词Xij从与选中主题相关的多项分布中被选择。xulti(Mpxvz|,)k（2.9）ijzijijijkx求解的最终目标为：xpzx(,kk)pzx(|)k1（2.10）pzx(|)xkpx()pz(,)kxkkk1k1该方法求解次数达到了Kx次幂之和，即使在并行化技术日趋进步的今天也很难被直接求解，因此对它的简化方法层出不穷，2.4节将会介绍一种采样简化方法。接下来解释为什么LDA算法能“理解”语义。假设即将使用LDA学习的话题i和词表中的某个词v具有较高的关联性，即P（x=v|z=i）较高。作为LDA生成过程的结果，包含术语v的任何文献d都具有升高的主题i的概率，这点在贝叶斯法则被提到，即P（z’=i|x=v）>P（z’=i）。这意味着与术语v共同发生的所有术语更可能已经由主题i生成，特别是作为共同出现的数量增加。因此，LDA结果中的主题最可能的条件经常彼此在文件共现。此外，LDA也有助于分析语言的多义性。假设某个词v在主题i和主题i’下含义不同，那么它的上下文在主题i和i’上出现的概率也会有较大不同，然后LDA将通过判断v与主题i的概率使用上下文来消除歧义的主题。极大似然函数。LDA模型训练涉及到在生成训练文档的概率最大化的情况下进行参数的优化设置。在一个给定的LDA模型里训练文档的概率被称为极大似然函数L。11 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用MNL(|,)(|)(|)(|)pxijzpzjijiiippin11（2.11）kk)kxk1k1()X1zxizkikxv（2.12）kv11)]k)k1表2.2算法1-LDA算法框架算法1LDA算法框架INPUT：预处理后的语料库D，通常一篇文章一行，已分词主题数K超参数α和βOUTPUT：文章-主题概率分布θ主题-单词概率分布φforalltopicsKdosampleφk～Dir（β）foralldocumentsDdosampleθi～Dir（α）sampledocumentlengthNi～Poiss（ξ）forallwordsinNidosamplezi,j～Mult（θi）samplexi,j～Mult（φk）2.4塌缩吉布斯采样算法吉布斯采样算法是2004年Griffiths等人提出的一种随机采样方法，当直接采样困难时，从指定的多元概率近似分布的观测序列来估计难以推断的概率模型值的分布。塌缩Gibbs采样（CGS）是将吉布斯采样算法中的几个先验参数α、β、初始Zij等简化为已知量的方法。GibbsSampling是Metropolis-Hastings（MH）算法的一种特殊情况。而MH算法来源于Metropolis等在1954年给出MarkovChainMonteCarlo（MCMC）方法。一阶马尔科夫链（MarkovChain）是一组事件的集合，上一个发生的事件将12 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用决定下一个事件的发生，即时刻t+1的状态只与时刻t的状态有关。用数学公式定义为：X=（X1,X2,X3....Xt,Xt,+1Xt+2,.....）P（Xt+1=x|Xt,Xt-1,Xt-2,,X1）=P（Xt+1=x|Xt）X可以为一个数字，一个向量或者一个矩阵。有这种方法产生的马尔科夫链具有平稳性质，当t足够大时，马尔科夫链将会平稳的收敛于同一个概率分布π（x）。它的平衡方程为：Φ（X）*P（Y|X）=Φ（Y）*P（X|Y）（2.13）MCMC方法的关键在于Q（Xt,Xt,+1）Q为下一事件发生决定函数，和ε（Xt,Xt,+1），用来判断是否收敛。假设有一个三个参数的马尔可夫链，只有它们相互的后验分布已知，那么可以一开始给三个参数赋初始值，根据三个变量的后验分布产生下一时间的三个变量，重复上述步骤就可以得到一个马尔可夫链。表2.3算法2-MCMC算法算法2MCMC算法step1:initializeX0=x0step2:fort=0,1,2,3...doXt=xtu～Uniform[0,1]//u从[0,1]均匀分布中取样ifu<α（xt,y）=p（y）q（xt|y）Xt+1=y//接受转移elseXt+1=xt由于转移率α的数值可能比较小，导致采样过程中大部分时间用于拒绝，使得整个采样过程，延长。Hastings对MCMC算法进行了改进，采用同比例放大α（xt→y）和α（xt→y）至较大值等于1的方法，加快函数的收敛速度。吉布斯采样则是基于MH算法在平面上构造出两点之间的转移矩阵yt+1～p（y|xt）和xt+1～p（x|yt+1），也能得到马尔科夫链的平稳状态。塌缩吉布斯采样算法（CollapsedGibbsSampling，CGS），CGS的特征是某些变量被边缘化，例如将θ和Φ看为基本不变的常量，仅Zij被采样。在LDA模型的各个参数基础上，CGS方法还要引入4个计数变量，其符号和含义见表2.4。13 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用表2.4CGS算法新增参数名称新增参数名称含义nik文档Di中主题k的词的个数ni文档Di中所含词的总数nkt主题k中编号为t的词的个数nk主题k中所含词的总数首先，算法将主题z0随机地分配给每个单词xij，在其他变量的固定值基础kt，根据其他所有词的主题分配z上统计ni、nk-i估计当前词分配各个主题的概[30]kt率p（zi|z-i,x）。它也被称为Gibbs采样公式。简而言之，统计的词数ni、nk不包括被采样的数据，并且在每次取样后都要进行更新。然后根据p（zi|z-i,x）的结果重新生成抽样，将主题z1，2，...随机地分配给每个单词xij，直至φ、θ收敛。该方法产生的是底层分布的无偏估计。在文档中最频繁出现的主题有一个更高的概率，也更可能对应于当前词元。LDA的联合分布写成：（2.14）pxz(|(|pxz(|)pdkv1j()t+1ztd（）zt,z（2.15）zt11k(+jz）()tv,{jj}zzt1z1（）pz(|pz(|p(|)dik1j()k+1ikdik,iik11（）（2.16）i(+ji）()kk,jni{i}k1i1（）所以得到kM(+j）(+j）zipzx(,|.（2.17）zi11（）（）即对除当前被取样的词外，其他所有词分配主题，根据得到的主题分配和被取样的单词来计算当前词所属主题的概率矩阵。14 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用pxz(,)pxz(,)pz()pz(kz|,)x.kkpz(,)xpx(|z,)(xpw)pz()kkkkk()j()jzi.(jj)()zi,,kk()ttv()()kkk()(jjkt)(t1k,tk)(jjik)(k1i,kk).(j()k)(vkj()t)(j()k)(j()k)k,kttk11k,kkti,kik()tk()(jj))ki,kkt,k.vk()tk()tk11jjki,kt)[k]1()t(j)k,tk()n()kvi,kk()tt1jk,tk)（2.18）k()k∵伽马函数具有Γ（z+1）=zΓ（z）的性质，且[k1jik]1是对K求和的结果，与主题分配无关，可消去，又因为狄利克雷分布的期望公式为E(Dir(a))=ai/∑iai，得到θ和φ的计算公式：()tnkt,kt,v()tt1nkt()kn（2.20）ikik,k()kk1nik表2.5算法3-基于塌缩吉布斯采样的LDA算法算法3基于塌缩吉布斯采样的LDA算法INPUT:D、K、α、βOUTPUT:θ、φ、Zijstep1:initializenkti，ni，nk，nk=0step2:foralldocumentsinDdoforallwordsinDidoZij=k～Mult（1/K）15 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用ni+=1nk+=1nki+=1ntk+=1step3:foralldocumentsinDdoforallwordsinDidoni-=1nk-=1n-=1nk-=1sampleZ’ij=k～p（zi|z-i,x）ni+=1nk+=1nki+=1ntk+=1lfreachthenumberofiterationsthenoutputθ,φandZij2.5LDA缺点与改进LDA具有主题建模的多种优点，包括实现较为简单并且能挖掘出潜在有用的主题。标准LDA算法无数次读取训练集，本质上是连续的，并且它倾向于广泛的学习主题，在实践中这意味着只能适用于一小部分数据的训练。然而根据最近并行算法的进步，使得该算法能合理训练和应用于非常大的文本语料库及动态数据，或者是嵌入网络的数据和其他具有特殊特征的数据，比如采用塌缩吉布斯采样法（CGS）和变分近似（VariationalApproximation）方法，也有研究者巧妙规划出并行但是不近似的LDA算法。总体上来说，在实践中更容易正确的实施和表现更好的是近似方法。目前对LDA的改进方法集中于两方面，包括用多台计算机并行LDA和改进算法以减少工作量。可以按是否共享内存为标准，将并行实现LDA划分为共享内存和不共享内存两种框架。前者出现较早，三个具有代表性的分布式LDA算法包括近似分布LDA（approximatedistributedLDA，AD-LDA），异步分布LDA（andasynchronousLDA，AS-LDA），和并行LDA（parallelLDA，PLDA）[31]。基于不共享内存的并行LDA实现主要是基于GPU的多线程处理技术对算法加速。这些方法都较好的降低了通信成本，缩短了收敛时间。改进后的LDA也适用于数据流。Yao等人构建了一个GS优化算法将现有16 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用的主题模型应用于文件流数据[32]。Hoffman开发了一个LDA的在线算法依次训练文档中的每个模型，并且由于该算法相当与随机目标函数的梯度下降，所以收敛于函数的一个固定点，不会降低模型的质量[33]。2.6本章小结本章主要介绍了LDA主题模型的思想、主要参数、参数估计方法，并给出了基于塌缩吉布斯采样方法的参数推导过程。模型的前提是贝叶斯法则和狄利克雷分布。LDA模型的总体思想是文档可看作是主题之上的多项分布，而主题是词语之上的多项分布。参数估计的方法有变分EM、Gibbs采样、BP置信度传播等。考虑到应用性及可扩展性，选择塌缩Gibbs采样方法作为LDA参数估计方法，推导了参数θ、φ的计算公式。LDA模型的主要优点是通过无监督学习分析未知类别训练集，从中发现分类规则，以此预测新数据的类别。同时，由于它适用于大型和动态数据集的降维，能够度量主题间的相似性，也可看作聚类算法。它主要使用在自然语言处理、文本挖掘等领域，在社交平台话题分析、视频场景分析、人脸识别、异常检测等应用场景中发挥了巨大的作用。17 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用3基于Hadoop的中文LDA算法设计3.1中文文本向量化并行算法LDA图形模型显示只有xij是可以直接观测到的变量，是主题最基本的组成部分，因此被称为词元（token）。它可以单独成为主题，也可以组合成某个主题。对于英文文档来说，空格号作为词语之间的间隔，没有词元选择这个问题。但是如果待处理是中文文档，则必须先进行中文分词操作。并且为了提高LDA模型的运行效率，在预处理时候要对分析文本尽可能多的进行降维。总体来说，预处理的过程是去除特殊符号、标点符号，引入停用词表，采用某种分词模型对文本分词[34]。3.1.1去除符号、停用词考虑到本文的研究目标是中文文本分类，汉语标点符号、特殊符号对分类无主要作用，有可能会影响分类结果，因此可以直接删去。所以最后文档的内容就变成了文本与数字。为了提高分类效率，还需要去除以下两种类型的词元：一是在文档中极其普遍，很少单独表达文档信息的词语，二是自身无明确意义的词语，例如语气助词、部分副词、介词、连接词等。这两种词语被称为停用词。需要注意的是第一种情况下，如果该词元能与其他词元组成一个表达文档相关信息的词语，就不能将它放入停用词表中。本文在现有停用词表基础上根据分词结果进行人工增减。3.1.2中文分词工具在处理完符号与停用词之后，词元的划分面对着词库匹配无法解决歧义，以及词性划分规则只能确定词的边界的问题。需要一种中文分词法能够较好解决以上两种问题。当前的分词算法可分为基于字典与字符串匹配、基于概率统计的两种算法。第一种算法较为机械，因此现采用基于概率统计的分词算法，如果字与字之间的联合概率高，认为它们可能组成一个词。该算法的步骤是将待处理文本按字划分，接着查找这些字所有可能的词性和这些字出现的概率，然后生成各种组合并计算它们的联合概率，保存概率最大的结果。目前热门的中文分词工具有汉语词法分析系统ICTCLAS、Stanford汉语分词工具、哈工大语言云（LTP-cloud）、庖丁解牛分词、盘古分词等。考虑字典完整性及对中英文、数字混合文本的支持，本文采用了经过改进的ICTCLAS作为分词工具进行并行化。18 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用该工具囊括了七万多个词语及词性标注工具，能基本满足一般文本分词的需求，但对专业领域的文本分析仍需改进。改进目标是让分词算法能够在大规模数据集中动态更新分词词典。为此，采用了一种点互信息（Pointwisemutualinformation，PMIk）算法，在大规模数据集中根据统计量PMIk衡量两个字符间的凝固程度，然后通过上下文的PMI计算，评估该组合的自由运用程度[35]。PMIk设置了k个联合概率因子，能够改善PMI过高的估计低频相邻字符的凝固程度。例如PMI为“彷徨”、“忐忑”等从不单独使用单字的词语赋予了过高的凝固程度，即使它们出现频率较低，也会认为其是候选新词。PMIk算法定义如下：（3.1）等式的左侧代表的是x和y的PMIk相关度，右侧分子中p（x,y）表示字符x和y的联合概率，分母中p（x）为字符x出现的频率，p（y）为字符y出现的频率字符可以随意组合，字数不限。一项对词长的研究表明，至少99%的词的词长在五字及以下。用t表示词长，先研究t=2时如何发现预备的新词种子。对于由t个字符组成的新词w1w2，寻找w1之前和w2之后的字w0、w3构成一个4字符组合w0w1w2w3。计算w0和w1的PMIk均值Ek1，和w2和w3的PMI均值E2Ekk1=（PMI（w0w1）+PMI（w1w2））/2Ekk2=（PMI（w0w1）+PMI（w2w3））/2若PMIk（wk1w2）>PMI（w0w1）+E1PMIk（wk1w2）>PMI（w2w3）+E2说明w1w2凝固程度较高，w1w2计入预备种子。与停用词表核对w1w2是否包含停用词，若是则结束之后的扩充方法。可以归纳出词长为t时扩充词长的更新方法，t为大于等于2的整数：对于由t个字符组成的新词w1...wt，寻找w1之前和wt之后的字w0、wt+1构成一个t+2字符组合wkk0w1...wt+!。计算PMI（w0...wt）和PMI（w1...wt+1）。若PMIk（wk0...wt）>PMI（w1...wt+1）说明应向wkk0扩充。E1=（PMI（w0...wt）+PMI（w1...wt））/2若PMIk（wk0...wt）+E1>PMI（w1...wt）则把w1...wt向前扩充一个字符。反之若PMIk（wkkk0...wt）≤PMI（w1...wt+1），计算E2=（PMI（w1...wt）+PMI（w1...wt+1））/219 浙江工业大学硕士论文基于Hadoop的中文并行LDA算法及在电子病历挖掘中的应用若PMIk（wk1...wt+1）+E2>PMI（w1...wt）则把w1...wt向后扩充一个字符。最后对预备种子进行阈值过滤，与已有词表核对加入新词。3.1.3中文分词并行算法对大规模语料集，考虑到数据库的规模大多在104以上，需要使用多个Mapper对数据分块处理。文档内部词语具有顺序特征，因此一个文档为分块后的最小单位，记作一条记录，文档内部不再分割。可用InputFormat控制输入的文本分块大小。Mapper过程需要计算新组合xij...xi（j+t-1）、加前一个字符组合xi（j-k的值并生成预备种子集合。执行1）...xi（j+t-1）、加后一个字符组合xij...xi（j+t）PMIni1kk存在性过滤，阈值T=PMI，得到的结果为PMI值高于均值的预备种子。ni在Reducer阶段汇总所有Mapper生成的预备种子集，去掉子字符（substring）中包括停用词的字符组合，将获得的新词加入分词字典中。可使用更新后的分词字典对字符重新进行拆分，比较两种字典下分词准确率等指标评估更新结果。表3.1算法4-分词词典更新并行算法算法4分词词典更新并行算法INPUT:语料库D，词典E，停用词表SOUTPUT：新词E’Mapper
此文档下载收益归作者所有
