学位论文 > 优秀研究生学位论文题录展示

基于众包和两层相关性聚类的实体解析方法

作　者: 李杰
导　师: 王宁
学　校: 北京交通大学
专　业: 计算机科学与技术
关键词: 实体解析相关性聚类邻居关系众包
分类号: TP301.6
类　型: 硕士论文
年　份: 2014年
下　载: 14次
引　用: 0次
阅　读: 论文下载

内容摘要

在现实世界中,同一个实体可能被多个数据源中的记录所描述。实体解析的任务就是确定哪些记录描述着现实世界中的同一个实体。实体解析是数据集成和数据清理中的一个关键步骤,它不仅能够提高数据的质量,还能够丰富单一数据的内容。然而,随着大数据时代的到来,各式各样的数据质量问题为实体解析带来了前所未有的挑战。面对纷杂的数据质量问题,传统的实体解析算法在效率、质量,特别是抗噪声能力方面的表现并不理想。在数据存在噪声的情况下,实体解析算法经常会出现不一致的判断结果,传统的做法是在匹配结果之上进行一次传递性闭包分析,这种做法极易将错误放大和传递。相关性聚类是实体解析的一个标准方法,它以记录对的匹配程度为依据,产生最大程度支持这些依据的聚类结果。相关性聚类为NP-hard问题,很多启发式的算法被提出,但效果并不理想。本文在相关性聚类的基础上,提出一个快速有效、抗噪声能力比较强和可扩展的实体解析方法。主要研究工作如下：(1)提出一种新颖的两层相关性聚类框架。该框架上层采用预分块算法对节点进行可重叠的分块;下层则使用调整块算法去除上层算法的重叠部分。(2)首次在相关性聚类问题中引入公共邻居的概念,并基于邻居关系给出邻居相似度的计算方法。本文首先分析如何使用邻居来表示一个块,并由此提出一个启发式的上层预分块算法。(3)提出核的概念,并由此定义节点与块之间的关联程度。核的概念突出块内关联强度最大的部分,由核来决定节点与块之间的关联程度可以更加准确地判断节点的归属,进而提高实体解析的准确度。本文基于核的概念,提出一个启发式的下层调整块算法。(4)在上层预分块算法中引入众包的概念,通过众包来验证块形成时所依据的节点对。由于上层预分块算法采用顺序生成块的方式,为了减少众包验证的开销,本文提出一种并行化确认算法,并在此基础上给出它的优化算法。实验结果表明,本文提出的基于众包和两层相关性聚类的实体解析方法在解析质量、抗噪性和可扩展性方面均优于传统的算法。

全文目录

致谢  5-6
摘要  6-7
ABSTRACT  7-11
1 绪论  11-17
  1.1 研究背景与意义  11-12
  1.2 国内外相关研究现状  12-15
    1.2.1 基于实体特征的方法  13-14
    1.2.2 基于实体关系的方法  14-15
  1.3 本文完成的工作  15-16
  1.4 本文的组织结构  16-17
2 实体解析相关技术介绍  17-25
  2.1 相关性聚类  17-22
    2.1.1 问题引入  17-18
    2.1.2 形式化定义  18-19
    2.1.3 无需参数和NP-hard  19-20
    2.1.4 相关启发式算法  20-22
  2.2 Blocking技术在实体解析中的应用  22-23
  2.3 众包概念在实体解析中的应用  23-25
3 两层相关性聚类算法  25-38
  3.1 启发性示例  25-26
  3.2 邻居相关概念  26-28
  3.3 算法的提出与实现  28-38
    3.3.1 算法概述  28
    3.3.2 上层预分块算法  28-32
    3.3.3 下层调整块算法  32-38
4 基于众包的算法改进  38-45
  4.1 并行化确认算法  38-43
  4.2 优化并行化确认算法  43-45
5 实验及结果分析  45-56
  5.1 实验设置  45-46
  5.2 评估方法  46-47
  5.3 两层相关性聚类算法实验  47-51
    5.3.1 有效性验证及分析  47-49
    5.3.2 抗噪性验证及分析  49-50
    5.3.3 处理时间和可扩展性验证及分析  50-51
  5.4 基于众包的改进算法实验  51-56
    5.4.1 有效性验证及分析  52
    5.4.2 并行化确认算法优化前后对比  52-56
6 总结与展望  56-58
  6.1 论文研究工作总结  56-57
  6.2 进一步研究工作与展望  57-58
参考文献  58-61
作者简历  61-63
学位论文数据集  63

基于众包和两层相关性聚类的实体解析方法

内容摘要

全文目录

相似论文