论文部分内容阅读
非结构化文本的实体解析对于综合多源数据挖掘实体信息具有重要的意义。伴随着大数据时代的到来,这一问题遇到了新的挑战:如何高效有效地进行大规模的实体解析。基于现有分布式编程模型和平台是其中比较可行和实用的手段。目前主流的做法是将原问题分为3个子问题:数据分块、块内实体匹配、各块结果合并。 本文也是按照这种分解原问题逐个解决子问题的做法,但针对目前研究及解决方法在某些方面的的不足,本文进行了相关研究和改进,作了以下几个方面的贡献: 1)提出一种基于具有相关性的有序键值的数据分块算法,能有效高效地对大规模数据进行分块。目前主流的基于有序键值的数据分块方法在键值和分块算法间往往是单独设计,分块算法对键值的要求只有可比较性,没有利用到键值的其他信息,这种联系不紧密影响了分块的效果。对此,本文对键值的设计提出了一个相关性的要求,将两个键值的相关性量化成他们之间的公共前缀长度,并且设计了一种满足该要求的键值生成方法:基于实体名称转化的键值TM。基于以上具有相关性的有序键值,本文提出一种公共前缀长度优先的分块算法LCPF,为每个键值跟其最相关的键值分在一块。该算法利用了键值相关性的定义,使用动态规划的方法将其运行时间优化到线性,并且讨论该方法能很方便地在三种主流的分布式编程模型(MapReduce,BSP,RDD)实现。实验表明,本文提出的数据分块算法LCPF在12台机器的集群能在十几分钟内对千万级别的记录按照相关性进行分块,表明其能高效地对大规模数据进行分块;此外,TM+LCPF跟其他几种主流的分块算法相比,在数据对完整性上提升了几个百分点,表明了其有效性。 2)设计了一个有效的非结构化文本的实体匹配器,为后文实现大规模非结构化文本的实体解析奠定了有效性的基础。在数据分块的基础上,通过对块内数据特点的分析,选择了合适的特征进行有监督机器学习。实验表明,该实体匹配器能有效地进行块内的实体匹配,F1值达92%。 3)本文设计了一个大规模非结构化文本的实体解析流程,该流程是有效高效并且有较好的伸缩性。首先,该流程相比其他主流的流程,在数据分块层面分为逻辑分块和逻辑块切分(物理分块),这两部分的分离便于各自专注于各自要解决的问题,同时松耦合也便于后续单独改进和复用。此外,基于滑动窗口设计了逻辑块切分的方法,从理论上分析了对于线性伸缩的数据分块算法,切分后的记录对总数上界为O(N·√N),保证了后续计算的高效性;最后,本文将各块结果的合并问题转为分布式图求连通分量的问题,利用BSP的计算方式来解决,实验表明按照这种方式合并,最终结果的准确率和与召回率与未合并前的平均结果相差2个百分点,说明其有效性。结合其他实验,表明这个流程是有效高效以及有较好的伸缩性。