大规模非结构化文本实体解析的研究

来源 :中国科学院大学 | 被引量 : 0次 | 上传用户:wanglin0824
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
非结构化文本的实体解析对于综合多源数据挖掘实体信息具有重要的意义。伴随着大数据时代的到来,这一问题遇到了新的挑战:如何高效有效地进行大规模的实体解析。基于现有分布式编程模型和平台是其中比较可行和实用的手段。目前主流的做法是将原问题分为3个子问题:数据分块、块内实体匹配、各块结果合并。  本文也是按照这种分解原问题逐个解决子问题的做法,但针对目前研究及解决方法在某些方面的的不足,本文进行了相关研究和改进,作了以下几个方面的贡献:  1)提出一种基于具有相关性的有序键值的数据分块算法,能有效高效地对大规模数据进行分块。目前主流的基于有序键值的数据分块方法在键值和分块算法间往往是单独设计,分块算法对键值的要求只有可比较性,没有利用到键值的其他信息,这种联系不紧密影响了分块的效果。对此,本文对键值的设计提出了一个相关性的要求,将两个键值的相关性量化成他们之间的公共前缀长度,并且设计了一种满足该要求的键值生成方法:基于实体名称转化的键值TM。基于以上具有相关性的有序键值,本文提出一种公共前缀长度优先的分块算法LCPF,为每个键值跟其最相关的键值分在一块。该算法利用了键值相关性的定义,使用动态规划的方法将其运行时间优化到线性,并且讨论该方法能很方便地在三种主流的分布式编程模型(MapReduce,BSP,RDD)实现。实验表明,本文提出的数据分块算法LCPF在12台机器的集群能在十几分钟内对千万级别的记录按照相关性进行分块,表明其能高效地对大规模数据进行分块;此外,TM+LCPF跟其他几种主流的分块算法相比,在数据对完整性上提升了几个百分点,表明了其有效性。  2)设计了一个有效的非结构化文本的实体匹配器,为后文实现大规模非结构化文本的实体解析奠定了有效性的基础。在数据分块的基础上,通过对块内数据特点的分析,选择了合适的特征进行有监督机器学习。实验表明,该实体匹配器能有效地进行块内的实体匹配,F1值达92%。  3)本文设计了一个大规模非结构化文本的实体解析流程,该流程是有效高效并且有较好的伸缩性。首先,该流程相比其他主流的流程,在数据分块层面分为逻辑分块和逻辑块切分(物理分块),这两部分的分离便于各自专注于各自要解决的问题,同时松耦合也便于后续单独改进和复用。此外,基于滑动窗口设计了逻辑块切分的方法,从理论上分析了对于线性伸缩的数据分块算法,切分后的记录对总数上界为O(N·√N),保证了后续计算的高效性;最后,本文将各块结果的合并问题转为分布式图求连通分量的问题,利用BSP的计算方式来解决,实验表明按照这种方式合并,最终结果的准确率和与召回率与未合并前的平均结果相差2个百分点,说明其有效性。结合其他实验,表明这个流程是有效高效以及有较好的伸缩性。
其他文献
心率是人体关键生理参数之一,与高血压、冠心病、脂质代谢异常等疾病密切相关,在疾病监测以及诊断中有举足轻重的地位。随着传感器技术的发展以及人们生活水平和健康意识的提高
微粒群算法源于对鸟群捕食行为的研究,它是以个体的协作与竞争来完成对复杂搜索空间内最优解的搜索,是一种基于群体智能的随机优化算法。微粒群算法的研究与应用近年来十分活
软件定义网络(Software Defined Networking,SDN)是一种新型的网络架构,它将网络的控制平面与数据平面分离,逻辑上集中式的控制平面使网络变的可编程、易管理。控制器在SDN网络中
自从第一个P2P文件共享系统Napster产生以来,出现了许多P2P文件共享系统,P2P应用已经取代Web的地位成为ISP网络上最大的带宽消耗者。然而受资源类型多样化、搜索复杂度的制约,现
“科学技术是第一生产力”已经在社会生产实践得到证明。而专利作为科研成果更是体现了一个企业乃至一个行业的科技竞争力。加入WTO后,我国企业所面临的国内外市场竞争愈发激
卫星移动通信技术是目前通信领域里的一个制高点。本文针对新一代静止轨道卫星移动通信系统——GMR-13G(GEO-Mobile Radio interface-13rd Generation,第三代静止轨道卫星)系统
贝叶斯网络作为不确定性知识表达和推理的一种方法,在很多领域都有着广泛的应用。贝叶斯网络是概率理论和图论相结合的产物,已经成为数据库知识发现和决策支持系统的有效方法。
实时系统是指不仅系统内部的行为及动作的完成与时间有关,而且对系统外部事件(如输入、中断等)的响应都要满足一定时间约束的系统。由于在国防及工业控制等领域应用广泛,因此这
学位
学位
USB总线因其高速、方便的特点,已经逐渐取代传统的低速总线,成为一种应用最为广泛的外设接口标准,越来越多的计算机外设开始采用USB接口。与此同时,共享USB设备的需求也变得越来