两层相关性聚类

1、大数据环境下用于实体解析的两层相关性聚类方法汇报人：万艳红Two-Tiered Correlation Clustering Method for Entity Resolution in Big Data论文简介 该论文取自计算机研究与发展期刊2014年09期，本文作者是王宁，北京交通大学计算机与信息技术学院副教授、博士，主研方向：Web数据集成，大数据管理，数据挖掘。PPT模板下载： 行业PPT模板： 节日PPT模板： PPT素材下载： PPT图表下载： 优秀PPT下载： PPT教程： Word教程： Excel教程： 资料下载： PPT课件下载： 范文下载： 试卷下载： 教案下载： PP

2、T论坛： 目录CONTENTS研究背景Research Background01理论研究Theoretical Research02实验示例Experimental Example 05未来展望Future Prospect06基本概念Basic Conception03试验方法Experimental Method04PPT模板下载： 行业PPT模板： 节日PPT模板： PPT素材下载： PPT图表下载： 优秀PPT下载： PPT教程： Word教程： Excel教程： 资料下载： PPT课件下载： 范文下载： 试卷下载： 教案下载： PPT论坛： PARTONE研究背景研究背景5信息技术的

3、飞速发展，使得数据量以空前的速度增长，如何从海量数据中快速有效地获取有用信息，已经成为人们研究的焦点。数据集成不仅可以丰富单一数据的内容，还能够提高数据的准确性。不同于传统的数据集成，大数据环境下的数据集成具有数据量大、数据更新速度快、数据源多样和数据存在噪声四个特点，这些特点是传统的数据集成方法很难适用于大数据环境。PART ONEPART TWOPART THREE实体解析（entity resolution, ER）是数据集成的一个重要步骤，已有的实体解析方法大都基于特征匹配，这些方法通常很难适应于大数据环境。传统实体解析算法解析结果示例6图显示了一个传统实体解析算法的解析结果。其中，两

4、个节点之间有边说明这两个节点所表示的记录描述着同一个实体，无边说明两条记录描述着不同的实体。显然，此解析结果存在冲突，因为理想情况下，图中各个连通子图应该为完全图为了消除冲突，已有的方法均是在实体解析之后进行简单的传递性闭包分析，即简单地将各个连通子图作为一个类对于图，进行传递性闭包分析之后的结果为1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16。假如节点和节点之间的连边是由于噪声所导致的错误判断，那么进行传递性闭包分析将会产生40个错误判断如果我们知道实体解析算法对节点和节点的判断是错误的，那么移除节点和节点之间的连边就可以避免传递性错误。在大数据环境下传统实体解

5、析算法不足之处7传统实体解析算法计算代价比较高。算法效率模式依赖解析结果传统实体解析算法所使用的相似度函数严重依赖于模式，而大数据环境中数据的异构性要求实体解析算法尽可能淡化对模式的依赖。由于噪声数据的存在，解析结果还会出现冲突的问题。PARTTWO理论研究理论研究9 在大数据环境下，传统的实体解析算法在效率和质量方面表现较差。随着大数据观念的不断深入，越来越多的工作开始研究适用于大数据环境的实体解析算法。为解决庞大的数据量带来的问题，文献18-19提出并行和可适应分块的算法面对快速更新的数据，文献20给出增量式的实体解析方法针对异构数据，文献15扩展传统的分块算法以处理异构数据源中属性未知的

6、情况对于大数据中的噪声问题，文献21-22给出一些容错或去除噪声的方案相关性聚类100301Pivot算法每次选择一个节点作为中心，将与该节点有边的节点归到同一个类中并移除02Vote算法每次选择一个节点，并将其归到与该节点有最大关联程度的类中Two-Tiered算法采用上层预分块算法和下层调整块算法相结合n 上层预分块算法以边为中心生成可重叠的分块方案，相对于Pivot算法以点为中心，以边为中心的上层算法可以充分考虑节点之间的邻居共享关系；n 下层调整块算法引入核的概念，只有在核内的节点才有判断一个节点归属的权力，而Vote算法把类中所有节点都视为核节点，区分核节点可以提高准确率。PARTT

7、HREE基本概念基本概念12邻居相关性聚类邻居公共邻居基本概念13邻居邻居PARTFOUR试验方法试验方法15给出一个无向完全图G构建图G的一个子图G该子图包含图G的所有节点和正边构建子图G第一步第二步第三步每次选择当前邻居相似度最大的节点对，将该节点对的公共邻居的邻居作为一个类；算法每一次迭代之后，都会将当前节点的公共邻居所在的边从边序列中移除；当边序列为空时算法终止。上层预分块算法将每一个节点归到和其具有最大关联程度的类中，如果最大关联程度为负值，将该节点作为一个单独的类。下层调整块算法上层预分块算法1601邻居向量02邻居相似度上层预分块算法17在无权的情况下，统计每个节点的邻居，计算所

8、有边的邻居相似度并排序，排序结果如下：上层预分块算法18在无权的情况下，图中数据的预分块结果为：1，2，3，4，5，5，6，8，9，10，11，12，13，15，16，4，5，6，7，8，9，10，11，14，14，显然，预分块的分块结果包含重叠的部分下层调整块算法19节点与类的关联程度下层调整块算法20PARTFIVE实验示例实验设置2201在Inter Core i5-2320CPU3.00GHz、4.00GB内存、64b硬件环境，以及Windows 7旗舰版操作系统下，使用eclipse-SDK-4.2.0-win32-x86_64和jdk1.7.0_05开发工具，实现了我们的算法Two

9、-Tiered和传统算法Pivot和Vote,使用Cora数据集作为基本数据集来评估本文算法。实验环境02将记录看成词的集合，计算两个记录的相似度就等于求两个集合的Jaccard相似度。一般来说，对于两个集合S和T，Jaccard定义如下：距离函数03将相似度分为20个区间，每一个区间都随机测试10%的记录对，将其中匹配记录对所占的比例作为该区间所有记录对匹配的概率比如，在区间0.55，0.6中有1509个记录对，随机选择其中150个记录对进行测试，其中135个为匹配记录对，那么我们认为落在区间0.55，0.6内的记录对的匹配概率为135/1500.9概率和权重设置评估方法2301F-measure02ARI(Adjusted Rand Index)算法评价24图有权和无权情况下种算法的有效性对比图有权和无权情况下种算法的运行时间图两层相关性聚类算法的可扩展性PARTSIX未来展望未来展望2601提高实体解析的质量大数据时代，“人-机”合作模式越来越受到人们的关注，这就是众包；在接下来的工作中考虑将该两层相关性实体解析