合作式数据集成系统中基于MapReduce的实体解析.docx

1、合作式数据集成系统中基于MapReduce的实体解析毕业设计（论文）中文题目：合作式集成系统中基于MapReduce的实体解析英文题目：Entity resolution based on MapReduce in cooperative integration system学 院：计算机与信息技术学院专 业：计算机科学与技术 学生姓名：薛卉 学 号：09271113 指导教师：王宁 2013年5月27日题 目：合作式数据集成系统中基于MapReduce的实体解析 适合专业：计算机科学技术指导教师（签名）： 提交日期：2013年3月7日学院：计算机与信息技术学院 专业： 学生姓名： 学号： 毕

2、业设计（论文）基本内容和要求：一、 研究内容随着移动终端设备的迅速发展，云端存储日益用户的在生活中显得重要。本项目旨在帮助移动终端的用户更好的使用云端强大的功能。用户将表格上传云端，可以在云端实现表格的融合和整理，也可以通过云端的搜索引擎实现用户的表和寻找的表的合并，从而使用户不必纠结于表格的格式问题，从而更高效快捷地获得更多更有用的信息。本项目使用范围广泛，例如：两个企业即将合并，急需融合企业中许多格式不一致和存在冗余,差错的表格，以便共享企业间的信息，以期达到双赢；此时，本项目便是达到该目的的有效平台。本项目面向云端上传表格的用户，在基于MapReduce分布式计算的框架下，通过机器学习的

3、训练集模型分析表中实体的相似性，从而达到实体解析和合并的目的,为用户提供在大数据环境下更加便捷的云端数据库的操作。研究表格中的实体解析问题时，通常发现实体解析中存在一些问题和特点：1.实体中存在语义的二义性，需要进一步识别。2.实体解析中存在格式不一致的数据，需要进一步格式化。3.实体解析中存在需要校正的数据，需要就一步进行容错和校正。4. 在上传的海量数据的表格中进行实体解析，串行的实体解析算法已经不能满足数据规模和处理效率的要求。综上所述，在大数据进行挖掘时将面临以下几个难点： 面对越来越庞大的数据集合，设计一个高效且能在分布式的机器上并行运行的算法显得极其重要。 面对越来越庞大的规格不一

4、致的数据，如何寻求一个更加有效的训练集，以便能更加高效的实现实体解析的需要，日益显得重要。 对于庞大复杂的数据，如何寻求一个高效的相似度算法，对项目影响非常关键。二、 技术指标1. 功能指标：最终目标是探索一种灵活的、可以自动更新的、基于学习的、能够对海量的数据集合进行高效的实体解析的模型。2. 性能指标：支持海量数据，提高轨迹挖掘算法的效率和可扩展性。三、 基本要求前期准备要求：了解云计算和实体解析的相关知识。1. 熟悉云计算平台的相关知识2. 熟悉Linux下平台上的Map/Reduce编程3. 实现对于表格实体解析高效的相似度算法4. 寻求合适的训练集后期实现要求：1. 对各模块编程实现

5、2. 对各模块进行测试以确定是否达到性能指标3. 对各模块进行连接并测试性能毕业设计（论文）重点研究的问题： 重点研究问题:如何在大数据的环境下实现更加高效的相似度算法。毕业设计（论文）应完成的工作：应完成的工作：1. 研究现有实体解析的技术，熟悉其算法思路2. 设计出基于机器学习的相似度计算的模型。3. 设计的关于实体解析的算法在云计算环境下的实现编码、调试、测试。参考资料推荐：1 Hector Gonzalez Alon Halevy Anno Langen Jayant Madhavan Rod McChesney,Rebecca Shapley Warren Shen Jonathan

6、 and Goldberg-Kidon .Google Fusion Tables:Web-Centered Data Management and Collabration.In ACM SIGMOD,2010.2 Hector Gonzalez Alon Halevy Anno Langen Jayant Madhavan Rod McChesney Rebecca Shapley Warren Shen Jonathan and Goldberg-Kidon.Socializing Data with Google Fusion Tables.In IEEE Computer Socie

7、ty,2010.3 Lise Getoor. Entity Resolution:Theory,Practice & Open Challenges.In VLDB Endowment,2012.4 Lars Kolb,Andreas Thor and Erhard Rahm.Block-based load Balancing for MapReduce-based Entity Resolution.In ACM,2011.5 Anish Das Sarma, Lujun Fang, Nitin Gupta, Alon Halevy,Hongrae Lee, Fei Wu, Reynold

8、 Xin and Cong Yu. Finding Related Tables.In ACM,2012.6 Petros Venetis,Alon Halevy, Jayant Madhavan, Marius Pasca, Warren Shen, Fei Wu, Gengxin Miao, and Chung Wu.Recovering Semantics of Tables on the Web.In VLDB Endowment,2011.7 Hector Gonzalez, Alon Halevy, Christian S. Jensen,Anno Langen, Jayant M

9、adhavan, Rebecca Shapley and Warren Shen.Google Fusion Tables: Data Management, Integration and Collaboration in the Cloud.In SoCC ,2010.其他要说明的问题：题目：合作式数据集成系统中基于MapReduce的实体解析学院：计算机与信息技术学院 专业：计算机科学与技术 学生姓名：薛卉 学号： 09271113文献综述：一、 研究背景及意义随着移动设备的快速发展，用户越来越倾向于在云端上传和处理数据。这时云端承载了用户关于存储和处理大规模数据的需求，而用户对于云端功

10、能的期待也越来越大。例如：对于用户上传的表格进行初步的冗余和容错处理；提供对于用户表格的视图可视化操作，使得用户对于数据有进一步更加形象具体的解读；对于用户表格中某些缺少的表项，可以在指定的数据库或者网络中寻找，使得用户间可以实现数据共享和交互。例如：两个企业即将合并，急需融合企业中许多格式不一致和存在冗余,差错的表格，以便共享企业间的信息，以期达到双赢，此时合作式集成系统便是一个可选择的平台。而此时，对于云端来说，实体解析显得尤为重要。对于用户上传表格中的实体减少冗余，校正错误和统一格式来说，实体解析是这一切的基础，却又存在许多需要考虑的细节。故本项目将研究重点放在寻求一个基于MapRedu

11、ce框架下的高效的实体解析算法。二、 研究现状和存在问题实体解析的历程经一个一个缓慢的发展过程。由最初的针对单行的实体进行去重，到发展到多个实体间的解析，最后发展到针对海量数据的实体解析。当前的实体解析主要是基于特定方向领域的研究，如：人名，地名，或者相关机构等。通常是对非结构化的文本进行分析，利用自然语言处理方法探索文本中的词语，短句，以及实体的结构特征和内容特征，通过数据挖掘算法为这些信息建立联系，以解决实体解析中遇到的问题。而对于针对海量规模的表格数据中的实体解析，所能查到的文献和实验结果并不多。本项目旨在处理更加广泛的数据，而不局限于某一种实体。对于处理海量规模的表格数据的实体解析来说

12、，自有其特点：1. 表格中的实体属性并不多，只需要简单的自然语言处理，而且不必进行大规模的搜索匹配。2. 正是由于实体的属性并不多，所以实体很容易存在二义性。模糊的实体使得实体解析加大了难度，有时人工都难以辨别。3.海量规模的表格数据必然需要寻求高效的并行算法。在基于MapReduce框架的云计算中，如何进行分块，如何实现加载平衡。4.针对相似度计算的算法中，对于判断相似的阈值是一个难以度量和确定的值。 故在本项目中，如何将实体的属性向量化，如何寻求一个好的相似度算法，显得十分的关键。在目前的研究中，距离度量通常用于衡量个体在空间上存在的距离，距离越远说明个体间的差异越大。主要包括以下几种：1

13、.欧氏距离是最常见的距离度量，衡量的是多维空间中各个点之间的绝对距离。公式如下：因为计算是基于各维度特征的绝对数值，所以欧氏度量需要保证各维度指标在相同的刻度级别。2.明可夫斯基距离明氏距离是欧氏距离的推广，是对多个距离度量公式的概括性的表述。公式如下：这里的p值是一个变量，当p=2的时候就得到了上面的欧氏距离。3.曼哈顿距离曼哈顿距离来源于城市区块距离，是将多个维度上的距离进行求和后的结果，即当上面的明氏距离中p=1时得到的距离度量公式，如下：4.切比雪夫距离 切比雪夫距离就是当p趋向于无穷大时的明氏距离： 其实上面的曼哈顿距离、欧氏距离和切比雪夫距离都是明可夫斯基距离在特殊条件下的应用。5

14、.马哈拉诺比斯距离既然欧几里得距离无法忽略指标度量的差异，所以在使用欧氏距离之前需要对底层指标进行数据的标准化，而基于各指标维度进行标准化后再使用欧氏距离就衍生出来另外一个距离度量马哈拉诺比斯距离，简称马氏距离。而在实体解析中，相似度度量主要是计算个体间的相似程度，与距离度量相反，相似度度量的值越小，说明个体间相似度越小，差异越大。主要有以下几种相似度度量：1.向量空间余弦相似度余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。公式如下：2.皮尔森相关系数即相关分析中的相关系数r，分别对X和Y基于自

15、身总体标准化后计算空间向量的余弦夹角。公式如下：3.Jaccard相似系数Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量差异具 体值的大小，只能获得“是否相同”这个结果，所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。如果比较X与Y的Jaccard相似系 数，只比较xn和yn中相同的个数，公式如下： 以上的相似度量和距离度量，都要考虑具体的数据和算法。对于项目中选用哪一种度量方式，目前正在学习和探讨中。主要参考文献：1 Hector Gonzalez Alon Halevy Anno Lange

16、n Jayant Madhavan Rod McChesney,Rebecca Shapley Warren Shen Jonathan and Goldberg-Kidon .Google Fusion Tables:Web-Centered Data Management and Collabration.In ACM SIGMOD,2010.2 Hector Gonzalez Alon Halevy Anno Langen Jayant Madhavan Rod McChesney Rebecca Shapley Warren Shen Jonathan and Goldberg-Kid

17、on.Socializing Data with Google Fusion Tables.In IEEE Computer Society,2010.3 Lise Getoor. Entity Resolution:Theory,Practice & Open Challenges.In VLDB Endowment,2012.4 Lars Kolb,Andreas Thor and Erhard Rahm.Block-based load Balancing for MapReduce-based Entity Resolution.In ACM,2011.5 Anish Das Sarm

18、a, Lujun Fang, Nitin Gupta, Alon Halevy,Hongrae Lee, Fei Wu, Reynold Xin and Cong Yu. Finding Related Tables.In ACM,2012.6 Petros Venetis,Alon Halevy, Jayant Madhavan, Marius Pasca, Warren Shen, Fei Wu, Gengxin Miao, and Chung Wu.Recovering Semantics of Tables on the Web.In VLDB Endowment,2011.7 Hec

19、tor Gonzalez, Alon Halevy, Christian S. Jensen,Anno Langen, Jayant Madhavan, Rebecca Shapley and Warren Shen.Google Fusion Tables: Data Management, Integration and Collaboration in the Cloud.In SoCC ,2010.研究方案：本项目的主要理论基础是实体解析的相关知识与基于MapReduce下的并行处理。背景知识涉及到数据挖掘的相似度计算，部分关于训练集的机器学习，以及云计算。一、 研究方法与步骤首先，研

20、究初期应大量阅读相关文献，充分调研相关研究，对项目需要的理论基础深入理解，为下一阶段的设计和实现打下坚实的基础。有了研究初期的充分调研后，应该着手进行对各个模块的算法进行设计。具体如下：5. 熟悉Hadoop平台上的MapReduce编程6. 寻找合适的实验数据源7. 找出并实现高效的相似度计算算法8. 实现实体解析后冗余，校错和合并等工作最后对算法各模块进行代码实现，并对各模块进行连接和性能测试。二、 预期效果本项目面向云端上传表格的用户，在基于MapReduce分布式计算的框架下，通过机器学习的训练集模型分析表中实体的相似性，从而达到实体解析和合并的目的,为用户提供在大数据环境下更加便捷的

21、云端数据库的操作。毕业设计（论文）进度安排：序号毕业设计（论文）各阶段内容时间安排备注1前期相关研究调研及熟悉Map/Reduce编程03.0803.252研究基于机器学习的训练集03.2504.153设计并实现高效的相似度计算算法04.1504.254各模块算法代码实现及模块间连接测试04.2505.155撰写毕业论文05.1505.25指导教师意见：填写说明：查阅资料是否全面，提出的研究方案和计划进度是否可行，还有什么需要注意和改进的方面，是否同意按学生提出的计划进行等。指导教师签名： 审核日期： 年 月 日摘要实体解析，是指将一个实体与现实中的一个对象匹配。实体解析技术通常是对实体进行多

22、个相似计算来决定两个实体是否能够有效匹配。然而，实体解析是一个非常昂贵的过程，对于海量数据集，可能需要几个小时甚至几天。基于MapReduce的分布式处理框架，不仅能融合大规模集群的计算能力，而且能屏蔽繁复的细节，实现更加高效的大规模数据的处理。本文给出在云平台上实现实体解析的方法。一方面，提高实体解析的效率和代价；另一方面，改进实体解析的算法，使其相似度算法正确率更高。本文重点关注三个方面：一是实现具有通用性的相似性计算的选择，针对不同的属性采用不同的相似性算法，其中重点是研究基于语义的相似性算法，能较好的解决传统的相似性算法中的不准确性和较差的适应性；二是在云平台上实现节点间的负载平衡；三

23、是通过机器学习训练相似性算法的阈值，提高准确率和召回率。本文还介绍了基于上述模型针对商品数据的测试，并在测试中获得了良好的结果。关键字：MapReduce，实体解析，相似度计算，加载平衡ABSTRACTThe Entity Resolution is the task of identifying entities referring to the same real-world object. Entity Resolution techniques usually compare lots of entities by evaluating multiple similarity meas

24、ures to male effective match decisions. However, the Entity Resolution is a very expensive process for large data sets, may take several hours or even days. The distributed process framework that Based on MapRduce programing, not only can integrate a large cluster of computing capacity, and can shie

25、ld complicated details, to achieve a more efficient large-scale data processing.Considering the advantage of MapReduce, this paper aims to introduce a new way to solve the problem of Entity Resolution- on the cloud platform to implement. On one hand, to improve the efficiency and lower the cost of t

26、he Entity Resolution; On the other hand, to improve efficiency of the Entity Resolution algorithm, and higher accuracy rate of similarity algorithm.This article focuses on three aspects: First, different properties use different similarity algorithm for achieving more universal similarity calculatio

27、n .We focus on the study of a better solution- similarity algorithm that based on semantic. We could change inaccuracy and poor adaptability of traditional algorithm. Second, achieve load balancing between nodes in cloud platform; Third, use machine learning train threshold of similarity algorithm t

28、o improve the precision and recall rate.According to the performance of Entity Resolution Model, we made an initial evaluation on the data model based on the model for commodities. The results on test data extraction we get are optimistic.Keywords: MapReduce，Entity Resolution，Similarity Calculation，

29、Load Balancing目 录摘要 1ABSTRACT 2目 录 31引言 51.1 研究背景 51.1.1 实体解析面临的挑战 61.1.2 研究意义和发展方向 91.1.3 促成原因 91.2 相关概念与研究现状 101.2.1 关于实体解析相关概念 101.2.2 研究现状 101.3 研究内容 122 项目的整体框架 142.1 项目的整体流程图 142.2 项目的输入输出格式 152.3 项目的使用平台 163 相似度算法的选择和使用 163.1 语义恢复后的选择 163.1.1 语义恢复工作 173.1.2 关键词的分类方法 203.2相似度计算算法 203.2 .1编辑距离算

30、法 213.3 .2基于语义的相似度算法 233.3.3 最后实现 264 机器学习训练阈值 284.1 支持向量机的原理 284.2 最后实现 295加载平衡算法 305.1 原因和需求 305.2 解决方案 325.3效率和评价 346.云平台的搭建 356.1 MapReduce和HDFS简介 356.2如何搭建Hadoop平台 366.3使用Hadoop遇到的问题 366.4项目实验结果 377 小结与未来工作 397.1小结 397.2 未来工作 39附录1：外文文献翻译 41外文文献原文 41外文文献译文 591引言1.1 研究背景实体解析(Entity Resolution)是识

31、别，连接，分组同一个真实世界中不同实体的表现方式，又叫做对象匹配(Object matching),去除重复数据(deduplicaiton)，记录链接(linkage)等。实体解析的发展经历了复杂的过程，从单个的实体解析，到多关系多约束的实体解析，发展到现在分块的大数据的实体解析。当前，实体解析在多领域都发挥着巨大的作用，如：人口普查记录、垃圾邮件检测、机器阅读等。随着互联网和移动终端设备的迅速发展，用户的数据显得越来越庞大和复杂，而处理起来必然需要消耗更多的资源。在大数据的大背景下，实体解析面临新一轮巨大的挑战。其中主要包括以下方面：1) 低效性，据研究调查表明，在一个大数据集中，大约只有10%的数据存在实体解析的必要。2) 大规模性，数据呈现海量性。3) 非结构化性。每个用户或每个企业输入模式可能存在异构性。这种情况下，可能导致名称/属性模糊不清，即存在二义性。而另一些非结构的数据可能是